Add README.md
[pdp8.git] / sw / kermit / k12 / k12enc.doc
CommitLineData
81e70d48
PH
1From: Charles Lasner <lasner@watsun.cc.columbia.edu>
2Subject: ENCODE/DECODE format description
3
4 The latest KERMIT-12 binary files are encoded in a specialized format.
5This document will describe the internal encoding and related subjects.
6
7OS/8 file considerations.
8
9 All OS/8 files are contiguous multiples of PDP-8 double-page sized logical
10records. These are sometimes known as blocks, but are more accurately known
11as records. (The term block is associated with various hardware descriptions,
12and means different things to different people, such as DECtape blocks or RK05
13blocks, where the first means a physical block which just happens to be 1/2
14the size of the OS/8 logical record, and the second means a physical sector
15which is the same size as the OS/8 logical record, but only if the drive is
16attached to an RK8E. We will therefore avoid this term!)
17
18 Since PDP-8 pages are 128 12-bit words each, the OS/8 record consists of
19256 12-bit words, which can also be viewed as 384 8-bit bytes. For the
20benefit of various existing utilities, there is a standard method of unpacking
21the 8-bit bytes yielding a stream of coherent 8-bit bytes. The PDP-8
22convention is to number bits from left to right starting with bit[0]. This is
23INCOMPATIBLE with the notation commonly used in other architectures, which is
24usually given as what power of 2 the bit represents. The PDP-8 notation is
25used to denote bit position in a manner consistent with significence of the
26bit, and arbitrarily uses origin 0, which is the usually assembly-language
27orientation. Using this notation, the first byte (byte #0) to be unpacked is
28taken from word[0] bits[4-11]. The second byte (byte #1) to be unpacked is
29taken from word[1] bits[4-11]. The third byte (byte #2) to be unpacked is
30taken from word[0] bits[0-3] concatenated with word[1] bits[0-3]. All bits
31are taken left to right as stated. This method is usually referred to as "3
32for 2," and repeated accordingly will yield the correct stream of bytes for
33ASCII OS/8 files. OS/8 absolute binary files are images of 8-bit paper-tape
34frames packed in the same format. Although the high-order bit "matters" in
35absolute binary files, the high-bit is untrustworthy in ASCII files. Both
36types of files end with a ^Z character which will have the high-order bit set
37in the case of the absolute binary files. The reason it succeeds in the
38binary case is that the paper-tape format treats the high-bit present as
39leader or trailer, not loadable data, etc., so the loader ignores all leading
40high-bit set bytes, and finishes on the first trailing high-bit set byte. The
41binary file contains several leader bytes of 0200 octal, and several trailer
42bytes of 0200 followed by 232, the code for ^Z. There is no "fool-proof" way
43to derive these formats, rather these are usually given by the extensions .BN
44for binary, and various extensions (.LS, .PA, .MA, .DI, .BI, .TX, .DC, etc.)
45for ASCII files. If the file is "known" to be either ASCII or absolute
46binary, then these conventions can be used to ignore extraneous trailing
47bytes. If the file type is unknown, then it must be treated as an "image"
48file, where all data must be preserved. The most typical image file is a .SV
49file, which is an image of files organized as pages and double-pages, with
50some trivial absolute loading instructions in a "header" block. Each record
51of the file is always "paired" off, i.e., the record has an implied
52double-page boundary of main memory it is meant to load into. If the loading
53instructions indicate a single-page load, then the first page must be loaded;
54the second half of the record is IGNORED. Notice it is impossible to specify
55singular loading of the "odd" page. OS/8 also supports various other formats,
56so it is difficult to obtain useful knowledge of the "inner" format of the
57file.
58
59Encoding considerations.
60
61 If the 8-bit bytes of an OS/8 file are unpacked and packed faithfully,
62the resultant file will be an accurate copy of the original data. This is the
63basis for an alternate encoding format, perhaps more universal in scope, but
64it is NOT the method used currently. The method chosen here is to treat the
65entire file as a contiguous stream of 5-bit bytes spanning words as necessary.
66This means that bits are taken from left to right, five at a time, and each
67encoded into a "printable" character for inclusion into the encoded file.
68This means that data will form 60-bit groups of 12 5-bit characters
69representing five 12-bit words. The 5-bit encoding is accomplished using the
70ASCII coding for an extension to hexadecimal, which can be called
71bi-hexadecimal, or base 32 notation. In this base, the values are 0-9, and
72A-V (just the "natural" extension of hexadecimal's 0-9, A-F). The alphabetic
73characters can be upper or lower case as necessary. This method is
74theoretically 25% more efficient than hexadecimal ASCII since each character
75holds 5-bit data rather than 4-bit data.
76
77 Since the 5-bit data has no "good" boundary for most computers, we will
78use the "best" case for PDP-8 image data, the 60-bit group as described above.
79Once started, a 60-bit group must be completed, thus there are boundaries
80throughout the file every 12 characters.
81
82 At any boundary, the file may have compressed data. Compressed fields are
83indicated by X (or x) followed by a four character field. The format is
84basically a truncation of the "normal" 60-bit group, but only contains 20 bits
85of data. The first 12 bits are the value of the data to be repeated. The
86last eight bits are the repeat count. Values of the repeat count range from
871-256, where 256 is implied if the value is zero. Practical values range from
883-255, since one or two values would take less file space uncompressed. Due
89to the boundary requirements, compression fields are independent of the data
90preceeding them. The repeat count limitation to a maximum of 256 was felt to
91be a reasonable compromise between compressed field length and adequate repeat
92count. Making the repeat count even only double the current maximum would
93require six character compression fields instead of five (including the X).
94As an implementation restriction, the encoding program only reads one OS/8
95record at a time, thus the case of 256 maximum repetitions occurs only at a
96double-page boundary. The added complexity required to achieve infrequent and
97minimal improvement was considered to be unimportant, but could be added
98later. Thus adjacent repeated values split across boundaries, or split across
99logical records will not contribute to a (single) compression field.
100
101 Note that compression is achieved by locating repeating strings of 12-bit
102values; if the file were viewed as repeating strings of 8-bit bytes, then
103compression would be less likely, except for cases like 0000 octal, which due
104to "symmetry" are compressible via either method. Many PDP-8 image files
105contain "filler" words, i.e., otherwise unloaded areas which are "pre-filled"
106with constant data such as 0000 octal, or 7402 octal, which is the PDP-8 HLT
107instruction. Image files filled with "large" regions of repeating strings of
1087402 will not compress using 8-bit byte orientation.
109
110Reliability considerations.
111
112 Even with the safeguards of a "robust" character set, file validity must
113be tested to maintain data integrity. Towards this end, the encoding format
114has several additional features. Unlike other "popular" formats, there is an
115explicit "command" structure to the encoded file format. All lines of data
116start with < and end with >. This prevents the characters from being
117"massaged" into unwanted alternates. Various systems are known to "destroy"
118files which have lines starting with "from", etc. By enclosing the data
119lines, we prevent these problems. Additionally, a class of explicit commands
120exist which start with ( and end with ). Instead of implied positioning,
121there is a command called (FILE filename.ext), where the filename.ext is the
122"suggested" name for the decoded file. The encoding program uses the original
123un-encoded file's file name in this field. After the data, there is another
124command (END filename.ext) which can be used to validate the data, since the
125same file name should be in both commands (as implemented in the encoding
126program). Several (REMARK {anything}) commands are inserted into the file at
127various points to assist in reconstructing the original file, or in
128documenting the fact that the file is an encoded "version" of another file.
129Several "frill" REMARK commands are implemented to indicate the original file
130date, and the date of encoded file creation. Today's date is always used for
131the encoded file creation date. The original file date may be omitted, if the
132system doesn't support Additional Information Words (AIWs), since this
133optional feature must be present in order for the files to have creation
134dates. The overall encoding format theoretically can be a concatenated series
135of encoded files, each with its own (FILE ) and (END ) commands, but the
136decoding program only supports single-file decoding as an implementation
137restriction.
138
139 The file must always end with a good boundary condition. If the last
140field is an X (compression) field, then this is already satisfied. If the
141last field is ordinary data, then 1-4 12-bit words of 0000 octal will be added
142at the end of the last field if necessary to ensure a good boundary. The end
143of file is signified by a single Z (or z) character. At this point, an
144extraneous record may be in progress. If it consists of four or less 12-bit
145words of 0000 octal, it is discarded. Any other situation regarding a partial
146record indicates defective data in the received encoded file.
147
148 After the single Z (z) character, there are 12 more characters: an entire
14960-bit group. This is the file checksum. It is accomplished with
150pentuple-precision arithmetic. It is the sum of all 12-bit data values with
151carry into a total of five 12-bit words. Repeat compression data values are
152also added, but only once for each compression field. The compression field's
153repeat count is also added, but it is first multiplied by 16. (The repeat
154count was expressed originally as *16 so it would have its eight significant
155bits left-justified). The entire 60-bit quantity is expressed in two's
156complement notation by negating it and encoding the group as any other 60-bit
157group. Since most files are relatively short, the high-order bits are
158generally zero, so most two's complement checksums start with 7777,7777 octal.
159The five 12-bit quantities holding the checksum are encoded low-order first,
160so the right-most characters in the checksum field tend to be V (v). This
161order is used merely to accomodate multi-precision arithmetic, as anyone
162attempting to observe "backwards bytes" on other machines is familiar with.
163
164Future considerations.
165
166 This format is by no means "perfect," but it is more robust than most,
167with a minimum of efficiency loss, given the tradeoffs involved. The data
168bracketing characters can be changed if required. The characters W (w) and Y
169(y) are available for this purpose. Files could incorporate a word or
170character count, or other validation technique, etc. Each line could
171incorporate a local count. These and other considerations could create a
172"compromise" format that could be more generic and "pallatable" to other
173systems. The checksum could be limited to 48 bits, which is more amenable to
1748 and 16 bit architectures. Perhaps opening parameters could govern the
175contents of the rest of the file, such as whether the checksum was present,
176etc.
177[end of file]