Looks like a lot of people are hitting this page while looking for a CRC-16 algorithm. That's not what this page is about. If you want a CRC-16 implementation in C, try this one. If you want one in 6502 assembly, skip down to the end of this document.
Apple II
File Type Notes
_____________________________________________________________________________
Developer Technical Support
File Type: $E0 (224)
Auxiliary Type: $8002
Full Name: NuFile Exchange Archival Library
Short Name: ShrinkIt (NuFX) document
Revised by: Andy Nicholas and Matt Deatherage July 1990
Written by: Matt Deatherage July 1989
Files of this type and auxiliary type contain NuFX Archival Libraries.
Changes since July 1989: Rewrote major portions to reflect Master Version
$0002 of the NuFX standard.
_____________________________________________________________________________
Introduction
NuFX is a robust, full-featured archival standard for the Apple II family.
The standard, as presented in this Note, allows for full archival of ProDOS
and GS/OS files while keeping all file attributes with each file, as well as
providing necessary archival functions such as multiple compression schemes
and multiple archival implementations of the same standard. NuFX is
implemented in the application ShrinkIt, a free archival utility program for
enhanced IIe, IIc and IIgs computers. (Versions for earlier Apple II models
are also available.)
The NuFX standard was developed by Andrew Nicholas for Paper Bag Productions.
Comments or suggestions on the NuFX standard, or comments and suggestions on
ShrinkIt are welcome at:
Paper Bag Productions
8415 Thornberry Drive East
Upper Marlboro, MD 20772
Attn: NuFX Technical Support
America Online: ShrinkIt
GEnie: ShrinkIt
CompuServe: 70771,2615
History
The Apple II community has always lacked a well-defined method for archiving
files. NuFX is an attempt to rectify the situation by providing a flexible,
consistent standard for archiving files, disks, and other computer media.
Although many files are archived using the Binary II standard (see Apple II
File Type Note, File Type $E0, Auxiliary Type $8000), it was not designed as
an archival standard and its continued use as such creates problems. More
people are using Binary II as an archival standard than as a way to keep
attributes with a file when transferred, and this use is causing the original
intent of Binary II to become lost and unused.
NuFX, developed as an archival standard for the days of GS/OS, allows:
o Filenames longer than 64 characters (GS/OS can create 8,000-
character filenames).
o A convenient way to add to, remove from, and work on an archive.
o Including GS/OS files which contain resource forks.
o Including entire disk images.
o Including comments with a file.
o A convenient way to represent a file compressed or encrypted by a
specific application.
o A true archive standard. Binary IIs original intent was to make
transfer of Apple II files from local machines to large
information services possible; otherwise, a file's attribute
information would be lost. Use of Binary II to archive files
rather than simply maintain their attributes stretches it beyond
its original intent.
Adding all of these features to the existing Binary II standard would be
nearly impossible without violating the existing standard and causing a great
deal of confusion. Although Binary II is flexible, it is simply unable to
address all of these concerns without alienating existing Binary II extraction
programs.
To provide some differentiation between standards and provide a better
functioning format, this Note presents a new standard called NuFX (NuFile
eXchange for the Apple II; pronounced new-F-X). NuFX fixes the problems that
Apple IIgs users would soon be experiencing as other filing systems become
available for GS/OS. NuFX attempts to stem a set of problems before they have
a chance to develop. NuFX provides all of the features of Binary II, but goes
further to allow the user the ultimate in flexibility, usefulness and
performance.
Additional Date/Time Data type:
Date/Time (8 Bytes):
+000 second Byte The second, 0 through 59.
+001 minute Byte The minute, 0 through 59.
+002 hour Byte The hour, 0 through 23.
+003 year Byte The current year minus 1900.
+004 day Byte The day, 0 through 30.
+005 month Byte The month, 0 through 11 (0 = January).
+006 filler Byte Reserved, must be zero.
+007 weekDay Byte The day of the week, 1 through 7 (1 = Sunday).
The format of the Date/Time field is identical to that described for the
ReadTimeHex call in the Apple IIgs Toolbox Reference Manual.
Implementation
Figure 1 illustrates the basic structure of a NuFX archive.
| First Record | Next Record |
_______________|_______________________|_______________________|
| Master Header | Header | Data | Header | Data |
|_______________|________|______________|________|______________|
Figure 1-NuFX Archive Structure
A single master header block contains values which describe the entire archive
(those with knowledge of structured programming may consider them archive
globals). Each of the succeeding header blocks contains only information
about the record it precedes (consider each an archive local).
Each header block is followed by a list of threads, which is followed by the
actual threads. The data for each thread may be a data fork, resource fork,
message, control sequence for a NuFX utility program, or almost any kind of
sequential data.
Possible Block Combinations:
The blocks must occur in the following fashion:
Master Header Block containing N entries
Header Block
Threads list:
filename_thread (16 bytes)
message_thread (16 bytes)
data thread (16 bytes)
.
.
.
filename_thread's data (filename_thread's comp_thread_eof # of bytes)
message_thread's data (message_thread's comp_thread_eof # of bytes)
data_thread's data (data_thread's comp_thread_eof # of bytes)
.
.
.
Next Header Block (notice no second Master Header block)
Threads list (message, control, data or resource)
.
.
.
Nth Header Block
Threads list (message, control, data or resource)
Master Header Block Contents
+000 nufile_id 6 Bytes These six bytes spell the word "NuFile" in
alternating ASCII (low, then high) for
uniqueness. The six bytes are $4E $F5 $46
$E9 $6C $E5.
+006 master_crc Word A 16-bit cyclic redundancy check
(CRC) of the remaining fields in this
block (bytes +008 through +047). Any
programs which modify the master header
block must recalculate the CRC for the
master header. (see the section "A Sample
CRC Algorithm") The initial value of this
CRC is $0000.
+008 total_records Long The total number of records in this
archive file. It is possible to chain
multiple records (files or disks)
together, as it is possible to chain
different types of records together (mixed
files and disks).
+012 archive_create_when
Date/Time The date and time on which this archive
was initially created. This field should
never be changed once initially written.
If the date is not known, or is unable to
be calculated, this field should be set to
zero. If the weekday is not known, or is
unable to be calculated, this field should
be set to null.
+020 archive_mod_when
Date/Time The date of the last modification to this
archive. This field should be changed
every time a change is made to any of the
records in the archive. If the date is
not known, or is unable to be calculated,
this field should be set to zero. If the
weekday is not known, or is unable to be
calculated, this field should be set to
null.
+028 master_version
Word The master version number of the NuFX
archive. This Note describes
master_version $0002, for which the next
eight bytes are zeroed.
+030 reserved 8 Bytes Must be null ($00000000).
+038 master_eof Long The length of the NuFX archive, in
bytes. Any programs which modify the
length of an archive, either increasing it
or decreasing it in size, must change this
field in the master header to reflect the
new size.
Header Block Contents:
Following the Master Header block is a regular Header Block, which precedes
each record within the NuFX archive. A cyclic redundancy check (CRC) has been
provided to detect archives which have possibly been corrupted. The only time
the CRC should be included in a block is for the Master Header and for each of
the regular Header Blocks. The CRC ensures reliability and data integrity.
+000 nufx_id 4 Bytes These four bytes spell the word "NuFX" in
alternating ASCII (low, then high) for
uniqueness. The four bytes are $4E $F5
$46 $D8.
+004 header_crc Word The 16-bit CRC of the remaining
fields of this block (bytes +006 through
the end of the header block and any
threads following it). This field is used
to verify the integrity of the rest of the
block. Programs which create NuFX
archives must include this in every
header. It is up to the discretion of the
extracting program to check the validity
of this CRC. Any programs which might
modify the header of a particular record
must recalculate the CRC for the header
block. The initial value for this CRC is
zero ($0000).
+006 attrib_count Word This field describes the length of
the attribute section of each record in
bytes. This count measures the distance
in bytes from the first field (offset
+000) up to and including the
filename_length field. By convention, the
filename_length field will always be the
last 2 bytes of the attribute section
regardless of what has preceded it.
+008 version_number
Word Version of this record. If version_number
is $0000, no option_list fields are
present. If the version_number is $0001
option_list fields may be present. If the
version_number is $0002 then option_list
fields may be present and a valid CRC-16
exists for the compressed data in the data
threads of this record. If the
version_number is $0003 then option_list
fields may be present and a valid CRC-16
exists for the uncompressed data in the
data threads of this record. The current
version number is $0003 and should always
be used when making archives.
+010 total_threads Long The number of thread subrecords
which should be expected immediately
following the filename or pathname at the
end of this header block. This field is
extremely important as it contains the
information about the length of the last
third of the header.
+014 file_sys_id Word The native file system identifier:
$0000 reserved
$0001 ProDOS/SOS
$0002 DOS 3.3
$0003 DOS 3.2
$0004 Apple II Pascal
$0005 Macintosh HFS
$0006 Macintosh MFS
$0007 Lisa File System
$0008 Apple CP/M
$0009 reserved, do not use (The
GS/OS Character FST returns
this value)
$000A MS-DOS
$000B High Sierra
$000C ISO 9660
$000D AppleShare
$000E-$FFFF Reserved, do not use
If the file system of a disk being
archived is not known, it should be set to
zero.
+016 file_sys_info Word Information about the current filing
system. The low byte of this word (offset
+016) is the native file system separator.
For ProDOS, this is the slash (/ or $2F).
For HFS and GS/OS, the colon (: or $3F) is
used, and for MS-DOS, the separator is the
backslash (\ or $5C). This separator is
provided so archival utilities may know
how to parse a valid file or pathname from
the filename field for the receiving file.
GS/OS archival utilities should not
attempt to parse pathnames, as it is not
possible to build in syntax rules for file
systems not currently defined. Instead,
pass the pathname directory to GS/OS and
attempt translation (asking the user for
suggestions) only if GS/OS returns an
"Invalid Path Name Syntax" error. The
high byte of this word is reserved and
should remain zero.
+018 access Flag Long Bits 31-8 reserved, must be zero
Bit 7 (D) 1 = destroy enabled
Bit 6 (R) 1 = rename enabled
Bit 5 (B) 1 = file needs to be
backed up
Bits 4-3 reserved, must be zero
Bit 2 (I) 1 = file is invisible
Bit 1 (W) 1 = write enabled
Bit 0 (R) 1 = read enabled
+022 file_type Long The file type of the file being archived.
For ProDOS 8 or GS/OS, this field should
always be what the operating system
returns when asked. For disks being
archived, this field should be zero.
+026 extra_type Long The auxiliary type of the file being
archived. For ProDOS 8 or GS/OS, this
field should always be what the operating
system returns when asked. For disks
being archived, this field should be the
total number of blocks on the disk.
+030 storage_type Word For Files: The storage type of the
file. Types $1 through $3 are standard
(one-forked) files, type $5 is an extended
(two-forked) file, and type $D is a
subdirectory.
file_sys_block_size
Word For Disks: The block size used by the
device should be placed in this field.
For example, under ProDOS, this field will
be 512, while for HFS it might be 524.
The GS/OS Volume call will return this
information if asked.
+032 create_when Date/Time The date and time on which
this record was initially created. If the
creation date and time are available from
a disk device, this information should be
included. If the date is not known, or is
unable to be calculated, this field should
be set to zero. If the weekday is not
known, or is unable to be calculated, this
field should be set to zero.
+040 mod_when Date/Time The date and time on which this record was
last modified. If the modification date
and time are available from a disk device,
this information should be included. If
the date is not known, or is unable to be
calculated, this field should be set to
zero. If the weekday is not known, or is
unable to be calculated, this field should
be set to zero.
+048 archive_when Date/Time The date and time on which
this record was placed in this archive.
If the date is not known, or is unable to
be calculated, this field should be set to
zero. If the weekday is not known, or is
unable to be calculated, this field should
be set to zero.
The following option_list information is only present if the NuFX version
number for this record is $0001 or greater.
+056 option_size Word The length of the FST-specific
portion of a GS/OS option_list returned by
GS/OS. This field may be $0000,
indicating the absence of a valid
option_list.
A GS/OS option_list is formatted as follows:
+000 buffer_size
Word Size of the buffer for GS/OS to
place the option_list in, including
this count word. This must be at
least $2E.
+002 list_size
Word The number of bytes of information
returned by GS/OS.
+004 file_sys_ID
Word A file system ID word (see list
above) identifying the FST owning
the file in question.
+006 option_bytes
Bytes The bytes returned by the FST.
There are (buffer_size - 6) of them.
The option_list contains information specific to native file systems that
GS/OS doesn't normally use (such as true creator_type, file_type, and access
privileges for AppleShare). Other FSTs released in the future will follow
similar conventions to return native file system specific parameters in the
option_list. Information in the option_list should always be copied from file
to file.
The value option_size in the NuFX header is the value of list_size minus two.
Immediately following the option_size count word are (list_size - 2) bytes.
To pass these values back to the destination file system, construct an
option_list with a suitably large buffer_size, a list_size of the NuFX
option_size + 2, the file_sys_id of the source file, and the FST-returned
option_bytes.
+058 list_bytes Bytes FST-specific bytes returned in an
option_list. These are the bytes in the
GS/OS option_list not including the FST ID
word. There are option_size of them. If
option_size is an odd number, one zero
byte of padding is added to keep the block
size an even number.
Because the attributes section does not have a fixed size, the next field must
be found by looking two bytes before the offset indicated by attrib_count
(+006).
+attrib_count - 2
filename_length
Word Obsolete, should be set to zero. In
previous versions of NuFX, this field was
the length of a file name or pathname
immediately following this field.
To allow the inclusion of future
additional parameters in the attributes
section, NuFX utility programs should rely
on the attribs_count field to find the
filename_length field.
Current convention is to zero this field
when building an archive and put the file
or pathname into a filename thread so the
record can be renamed in the archive.
Archival programs should recognize both
methods to find a valid file name or
pathname.
+attrib_count
filename Bytes Filename or partial pathname if
applicable. If this is a disk being
archived, then the volume_name should be
included in this field. If a volume name
is included in this field, a separator
should not be included in, or precede the
name. If a volume name is not available,
then this field should be zeros.
If a partial pathname is specified, the
directories to which the current pathname
refers need not have preceded this
particular record. The extraction program
must test each referenced directory
individually. If the directory in
question does not exist, the extracting
program should create it.
Any utility which extracts file from a
NuFX archive must not assume that this
field will be in a format it is able to
handle. In particular, extraction
programs should check for syntax
unacceptable to the operating system under
which they run and perform whatever
conversions are necessary to parse a legal
filename or pathname. In general, assume
nothing. (GS/OS programs should pass the
filename or pathname directly to GS/OS,
and only attempt to convert the name if
GS/OS returns an "invalid pathname syntax"
error.)
Both high and low ASCII values are valid
but may not mean the same to each file
system (for example, all eight bits are
significant in AppleShare pathnames while
only seven are significant in ProDOS
pathnames).
Threads
Thread Records are 16-byte records which immediately follow the Header Block
(composed of the attributes and file name of the current record) and describe
the types of data structures which are included with a given record. The
number of Thread Records is described in the attribute section by a Word,
total_threads.
Each Thread Record should be checked for the type of information that a given
utility program can extract. If a utility is incapable of extracting a
particular thread, that thread should be skipped (with the exception of
extended files under ProDOS 8, which should be dearchived into AppleSingle
format, or both threads should be skipped). If a utility finds a redundancy
in a Thread Record, it must decide whether to skip the record or to do
something with that particular thread (i.e., if a utility finds two
message_thread threads it can either ignore the second one or display it.
Likewise, if a utility finds two data_thread threads for the same file, it
should inspect the thread_kind of each. If they match, it can either
overwrite the first thread extracted, or warn the user and skip the second
thread).
Thread records can be represented as follows:
+000 thread_class Word The classification of the thread:
$0000 message_thread
$0001 control_thread
$0002 data_thread
$0003 filename_thread
+002 thread_format Word The format of the data within the thread:
$0000 Uncompressed
$0001 Huffman Squeeze
$0002 Dynamic LZW/1 (ShrinkIt
specific)
$0003 Dynamic LZW/2 (ShrinkIt
specific)
$0004 Unix 12-bit Compress
$0005 Unix 16-bit Compress
+004 thread_kind Word Describes the kind of data within
the thread.
thread_kind must be interpreted on the basis of thread_class. See the table
below for the currently defined thread_kind interpretations:
class $0000 class $0001 class $0002 class $0003
----------- ---------------- --------------------- -----------
kind $0000 ASCII text create directory data fork of file filename
kind $0001 see below undefined disk image undefined
kind $0002 see below undefined resource fork of file undefined
+006 thread_crc Word For version_number $0003, this field
is the CRC of the original data before it
was compressed or otherwise transformed.
The CRC-16's initial value is set to $FFFF.
+008 thread_eof Long The length of the thread when uncompressed.
+012 comp_thread_eof
Long The length of the thread when compressed.
Class $0000 with kind $0000 is obsolete and should not be used.
Class $0000 with kind $0001 has a predefined comp_thread_eof and a thread_eof
whose length may change. This way, a certain amount of space may be allocated
when a record is created and edited later.
Class $0000 with kind $0002 is a standard Apple IIgs icon. comp_thread_eof is
the length of the icon image; thread_eof is ignored.
Class $0003 with kind $0000 has a predefined comp_thread_eof and a thread_eof
whose length may change. After this record is placed into the archive, the
thread_eof can be changed if the name is changed, but the length of the name
may not extend beyond the space allocated for it, comp_thread_eof.
A thread_format of $0001 indicates Huffman Squeeze. NuFX's Huffman is the
same Huffman used by ARC v5.x, SQ and USQ, the source of which is publicly
available and was originally written by Richard Greenlaw. The first word of
the thread data is the number of nodes followed by the Huffman tree and the
actual data. This is also the same algorithm decoded by the Apple II version
of USQ written by Don Elton. The C source to this is widely available.
A thread_format of $0002 indicates a special variant of LZW (LZW/1) used by
ShrinkIt. The first two bytes of this thread are a CRC-16 of the uncompressed
data within the thread. This CRC-16 is initialized to zero ($0000). The third
byte is the low-level volume number used by the eight-bit version of ShrinkIt
to format 5.25" disks. The fourth byte is the run-length character used to
decode the rest of the thread. The data which comprises the compressed file
or disk immediately follows the RLE character.
When ShrinkIt compresses a file, it reads 4096-byte chunks of the file until
it reaches the file's EOF. The last 4096-byte chunk is padded with zeroes if
the file's length is not an exact multiple of 4096. Compressing a disk is
also done by reading sequential blocks of 4096-bytes.
Each 4K chunk is first compressed with RLE compression. The RLE character is
determined by reading the fourth byte of the thread. The RLE character which
is used by most current versions of ShrinkIt is $DB. A run of characters is
represented by three bytes, consisting of the run character, the number of
characters in the run and the character in the run. If the 4K chunk expands
after being compressed with RLE then the uncompressed 4K chunk is passed to
the LZW compressor. If the 4K chunk shrinks after being compressed with RLE
then the RLE-compressed image of the 4K chunk is passed to the LZW compressor.
ShrinkIt's LZW compressor individually compresses each 4K chunk passed to it
by using variable length (9 to 12 bits) codes. The way that ShrinkIt's LZW
compressor functions is almost identical to the algorithm used in the public
domain utility Compress. The first code is $0101. The LZW string table is
cleared before compressing each 4K chunk. If the compressed chunk increases
in size, then the previous 4K chunk (which may be run-length-encoded or just
uncompressed data) is written to the file.
The first word of every 4K chunk is aligned to a byte boundary within the file
and is the length which resulted from the attempt at compressing the chunk
with RLE. If the value of this word is 4096, then RLE was not successful at
compressing the chunk. A single byte follows the word and indicates whether
or not LZW was performed on this chunk. A value of zero indicates that LZW
was not used, while a value of one indicates that LZW was used and that the
chunk must first be decompressed with LZW before doing any further processing.
To decompress a file, each 4K chunk must first be expanded if it was
compressed by LZW. If the 4K chunk wasn't compressed with LZW, then the word
which appears at the beginning of each chunk must be used to determine if the
data for the current chunk needs to be processed by the run-length decoder.
If the value of the word is 4096, then run-length decoding does not need to
occur because the data is uncompressed.
If the word indicates that the length of the chunk after being decompressed by
LZW is 4096-bytes long, then no run-length decoding needs to take place. If
value of the word is less than 4096 then the chunk must be run-length decoded
to 4096 bytes.
There are four varying degrees of compression which can occur with a chunk: it
can be uncompressed data. It can be run-length-encoded data without LZW
compression. It can also be uncompressed data on which RLE was attempted (but
failed) and then was subsequently compressed with LZW. Or, finally, the chunk
can be compressed with RLE and then also compressed with LZW.
A thread_format of $0003 indicates a special variant of LZW (LZW/2) used by
ShrinkIt. The first byte is the low-level volume number used by the eight-bit
version of ShrinkIt to format 5.25" disks. The second byte is the run-length
character used to decode the rest of the thread. The data which comprises the
compressed file or disk immediately follows the second byte of the thread.
The format of LZW/2 is almost the same as LZW/1 with a few exceptions. Unlike
LZW/1, where the LZW string table is automatically cleared before each 4K
chunk is processed, the LZW string table used by LZW/2 is only cleared when
the table becomes full, indicating a change in the redundancy of the source
text. Not clearing the string table almost always yields improved compression
ratios because the compressor's dictionary is not being depleted every 4K and
larger strings are allowed to accumulate. The clear code used by ShrinkIt is
$100. Whenever the decompressor sees a $100 code, it must clear the string
table.
The string table is also cleared when the compressor has to "back track"
because a 4K chunk became larger. Whenever a chunk that is not compressed by
LZW is seen by the decompressor, the LZW string table must be cleared. Bits
0-12 of the first word of each chunk in a LZW/2 thread indicate the size of
the chunk after being compressed with RLE. The high bit (bit 15) indicates
whether or not LZW was used on the chunk. If LZW was not used (bit 15 = 0),
the data for the chunk immediately follows the first word. If LZW was used
(bit 15 = 1), a second word which is a count of the total number of bytes used
by the current chunk follows the first word. The mark of the next chunk can
be found by taking the mark at the beginning of the current chunk and adding
the second word to it, using that as an offset for a ProDOS 8 or GS/OS SetMark
call. This is not normally necessary because the next chunk is processed
immediately after the current chunk.
This second word is an improvement over LZW/1 because if a chunk becomes
corrupted, but the second word is valid, the next chunk can be found and most
of the file recovered. The second word is not needed (and not present) when
LZW is not used on the chunk because the first word is also a count of the
number of bytes which follow that word.
A thread_format of $0004 indicates that a maximum of 12 bits per LZW code by
Compress was used to build this thread. The actual thread data contains
Compress's usual three-byte signature, the third byte of which contains the
actual number of bits per LZW code that was actually used. The number of bits
may be less than or equal to 12. Optimally, this requires (at 12 bits) a 16K
hash table to decode and should be used only for transferring to machines with
limited amounts of memory. The C source to Compress is in the public domain
and is widely available.
A thread_format of $0005 indicates that a maximum of 16 bits per LZW code by
Compress was used to build this thread. The actual thread data contains
Compress's usual three-byte signature, the third byte of which contains the
actual number of bits per LZW code that was actually used. The number of bits
may be less than or equal to 16. Optimally, this requires (at 16 bits) a 256K
hash table to decode. The C source to Compress is in the public domain and is
widely available.
If a control_thread indicates that a directory should be created on the
destination device, the path to be created must take the form of a ProDOS
partial pathname. That is, the path must not be preceded with a volume name.
For example, /Stuff/SubDir is an invalid path for this control_thread, while
SubDir/AnotherSubDir is valid.
If a control_thread indicates that a path is to be created, all subdirectories
that are contained in the pathname must be created.
control_thread threads will eventually be used to control the execution of
utility programs by allowing them to create, rename, and delete directories
and files and to move and modify files. A form of scripting language will
eventually be able to allow utility programs to perform these actions
automatically. control_thread threads will allow extraction programs to
perform operations similar to those of the Apple IIgs Installer, allowing
updates to program sets dependent on such things as creation or modification
dates and version numbers.
Extra Information
If the file system of a particular disk is not known, the file_sys_id field
should be set to zero, the volume name should also be zeroed, and all the
other fields pertaining only to files should be set to zero.
If the file system of a particular disk is known, as many of the fields as
possible should be filled with the correct information. Fields which do not
pertain to an archived disk should remain set to zero.
If an entire disk is added to the archive without some form of compression
(i.e., record_format = uncompressed), then the blocks which comprise the disk
image must be added sequentially from the first through the last block. Since
there will be no character included in the data stream to mark the end or
beginning of a block, extraction programs should rely on the
file_sys_block_size field to determine how many bytes to read from the record
to properly fill a block.
Some Useful Thread Algorithms:
The beginning of the thread records can be found with the following algorithm:
Threads := (mark at beginning of header) + (attrib_count) +
(filename_length)
The end of the thread records can be found with the following algorithm:
endOfThreads := Threads + (16 * total_threads)
The beginning of a data_thread can be found with the following formula:
Data Mark := endOfThreads + (comp_thread_eof of all threads in the thread
list which are not data prior to finding a data_thread)
The beginning of a resource_thread may be found with the following algorithm:
Resource Mark := endOfThreads + (comp_thread_eof of all threads in the
thread list which are not data prior to finding a
resource_thread)
The next record can be found using the following algorithm:
Next Mark := endOfThreads + (comp_thread_eof of each thread)
The file name and its length can be found with the following algorithm:
if (filename_length > 0)
then
length of filename is filename_length;
filename is found at attrib_count;
else
look through list of threads for a filename_thread;
if you find one, then length of filename is thread_eof;
if you don't find one, then you don't have a filename.
Directories
Directories are handled almost the same way that normal files are handled with
the exception that there will be no data in the thread which follows the
entry. A Thread Record must exist to inform a utility that a directory is to
be created through the use of the proper control_thread value.
Directories do not necessarily have to precede a record which references a
directory. For example, if a record contains Stuff/MyStuff, the directory
Stuff need not exist for the extracting program to properly extract the
record. The extracting program must check to see if each of the directories
referenced exist, and if one does not exist, create it. While this method
places a great burden on the abilities of the extraction program, it avoids
the anomalies associated with the deletion of directories within an archive.
A Sample CRC Algorithm
Paper Bag Productions provides the source code to a very fast routine which
does the CRC calculation as needed for NuFX archives. The routine makeLookup
needs to be called only once. After the first call, the routine doByte should
be called repeatedly with each new byte in succession to generate the
cumulative CRC for the block. The CRC word should be reset to null ($0000)
before beginning each new CRC.
This is the same CRC calculation which is done for CRC/Xmodem and Ymodem. The
code is easily portable to a 16-bit environment like the Apple IIgs. The only
detrimental factor with this routine is that it requires 512 bytes of main
memory to operate. If you can spare the space, this is one of the fastest
routines Paper Bag Productions knows to generate a CRC-16 on a 6502-type
machine.
The CRC word should be reset to $0000 for normal CRC-16 and to $FFFF before
generating the CRC on the unpacked data for each data thread.
*-------------------------------
* fast crc routine based on table lookups by
* Andy Nicholas - 03/30/88 - 65C02 - easily portable to nmos 6502 also.
* easily portable into orca/m format, just snip and save.
* Modified for generic EDAsm type assemblers - MD 6/19/89
X6502 turn 65c02 opcodes on
*-------------------------------
* routine to make the lookup tables
*-------------------------------
makeLookup
LDX #0 zero first page
zeroLoop STZ crclo,x zero crc lo bytes
STZ crchi,x zero crc hi bytes
INX
BNE zeroLoop
*-------------------------------
* the following is the normal bitwise computation
* tweeked a little to work in the table-maker
docrc
LDX #0 number to do crc for
fetch TXA
EOR crchi,x add byte into high
STA crchi,x of crc
LDY #8 do 8 bits
loop ASL crclo,x shift current crc-16 left
ROL crchi,x
BCC loop1
* if previous high bit wasn't set, then don't add crc
* polynomial ($1021) into the cumulative crc. else add it.
LDA crchi,x add hi part of crc poly into
EOR #$10 cumulative crc hi
STA crchi,x
LDA crclo,x add lo part of crc poly into
EOR #$21 cumulative crc lo
STA crclo,x
loop1 DEY do next bit
BNE loop done? nope, loop
INX do next number in series (0-255)
BNE fetch didn't roll over, so fetch more
RTS done
crclo ds 256 space for low byte of crc table
crchi ds 256 space for high bytes of crc table
*-------------------------------
* do a crc on 1 byte/fast
* on initial entry, CRC should be initialized to 0000
* on entry, A = byte to be included in CRC
* on exit, CRC = new CRC
*-------------------------------
doByte
EOR crc+1 add byte into crc hi byte
TAX to make offset into tables
LDA crc get previous lo byte back
EOR crchi,x add it to the proper table entry
STA crc+1 save it
LDA crclo,x get new lo byte
STA crc save it back
RTS all done
crc dw 0000 cumulative crc for all data
The following CRC check is written in APW assembler format for an Apple IIgs
with 16-bit memory and registers on entry.
crcByte start
crc equ $0
crca equ $2
crcx equ $4
crctemp equ $6
sta crca 4
stx crcx 4
eor crc+1 on entry, number to add to CRC 4
and #$00ff is in (A) 3
asl a 2
tax 2
lda crc16Table,x 5
and #$00ff 3
sta crcTemp 4
lda crc-1 4
eor crc16Table,x 5
and #$ff00 3
ora crcTemp 4
sta crc 4
lda crca 4
ldx crcx 4
rts cycles = 59
;
; CRC-16 Polynomial = $1021
;
crc16table anop
dc i'$0000, $1021, $2042, $3063, $4084, $50a5, $60c6, $70e7'
dc i'$8108, $9129, $a14a, $b16b, $c18c, $d1ad, $e1ce, $f1ef'
dc i'$1231, $0210, $3273, $2252, $52b5, $4294, $72f7, $62d6'
dc i'$9339, $8318, $b37b, $a35a, $d3bd, $c39c, $f3ff, $e3de'
dc i'$2462, $3443, $0420, $1401, $64e6, $74c7, $44a4, $5485'
dc i'$a56a, $b54b, $8528, $9509, $e5ee, $f5cf, $c5ac, $d58d'
dc i'$3653, $2672, $1611, $0630, $76d7, $66f6, $5695, $46b4'
dc i'$b75b, $a77a, $9719, $8738, $f7df, $e7fe, $d79d, $c7bc'
dc i'$48c4, $58e5, $6886, $78a7, $0840, $1861, $2802, $3823'
dc i'$c9cc, $d9ed, $e98e, $f9af, $8948, $9969, $a90a, $b92b'
dc i'$5af5, $4ad4, $7ab7, $6a96, $1a71, $0a50, $3a33, $2a12'
dc i'$dbfd, $cbdc, $fbbf, $eb9e, $9b79, $8b58, $bb3b, $ab1a'
dc i'$6ca6, $7c87, $4ce4, $5cc5, $2c22, $3c03, $0c60, $1c41'
dc i'$edae, $fd8f, $cdec, $ddcd, $ad2a, $bd0b, $8d68, $9d49'
dc i'$7e97, $6eb6, $5ed5, $4ef4, $3e13, $2e32, $1e51, $0e70'
dc i'$ff9f, $efbe, $dfdd, $cffc, $bf1b, $af3a, $9f59, $8f78'
dc i'$9188, $81a9, $b1ca, $a1eb, $d10c, $c12d, $f14e, $e16f'
dc i'$1080, $00a1, $30c2, $20e3, $5004, $4025, $7046, $6067'
dc i'$83b9, $9398, $a3fb, $b3da, $c33d, $d31c, $e37f, $f35e'
dc i'$02b1, $1290, $22f3, $32d2, $4235, $5214, $6277, $7256'
dc i'$b5ea, $a5cb, $95a8, $8589, $f56e, $e54f, $d52c, $c50d'
dc i'$34e2, $24c3, $14a0, $0481, $7466, $6447, $5424, $4405'
dc i'$a7db, $b7fa, $8799, $97b8, $e75f, $f77e, $c71d, $d73c'
dc i'$26d3, $36f2, $0691, $16b0, $6657, $7676, $4615, $5634'
dc i'$d94c, $c96d, $f90e, $e92f, $99c8, $89e9, $b98a, $a9ab'
dc i'$5844, $4865, $7806, $6827, $18c0, $08e1, $3882, $28a3'
dc i'$cb7d, $db5c, $eb3f, $fb1e, $8bf9, $9bd8, $abbb, $bb9a'
dc i'$4a75, $5a54, $6a37, $7a16, $0af1, $1ad0, $2ab3, $3a92'
dc i'$fd2e, $ed0f, $dd6c, $cd4d, $bdaa, $ad8b, $9de8, $8dc9'
dc i'$7c26, $6c07, $5c64, $4c45, $3ca2, $2c83, $1ce0, $0cc1'
dc i'$ef1f, $ff3e, $cf5d, $df7c, $af9b, $bfba, $8fd9, $9ff8'
dc i'$6e17, $7e36, $4e55, $5e74, $2e93, $3eb2, $0ed1, $1ef0'
end
Further Reference
_____________________________________________________________________________
o ProDOS 8 Technical Reference Manual
o GS/OS Reference
o Apple IIgs Toolbox Reference Manual
o Apple II File Type Note, File Type $E0, Auxiliary Type $8000
o Apple II Miscellaneous Technical Note #14, Guidelines for
Telecommunication Programs
o "A Technique for High-Performance Data Compression," T. Welch,
IEEE Computer, Vol. 17, No.6, June 1984, pp. 8-19.