| 1 |
About |
| 2 |
----- |
| 3 |
|
| 4 |
PalmDOC uses LZ77 compression techniques. DOC files can contain only compressed |
| 5 |
text. The format does not allow for any text formatting. This keeps files |
| 6 |
small, in keeping with the Palm philosophy. However, extensions to the format |
| 7 |
can use tags, such as HTML or PML, to include formatting within text. These |
| 8 |
extensions to PalmDoc are not interchangeable and are the basis for most eBook |
| 9 |
Reader formats on Palm devices. |
| 10 |
|
| 11 |
LZ77 algorithms achieve compression by replacing portions of the data with |
| 12 |
references to matching data that has already passed through both encoder and |
| 13 |
decoder. A match is encoded by a pair of numbers called a length-distance pair, |
| 14 |
which is equivalent to the statement "each of the next length characters is |
| 15 |
equal to the character exactly distance characters behind it in the |
| 16 |
uncompressed stream." (The "distance" is sometimes called the "offset" instead.) |
| 17 |
|
| 18 |
In the PalmDoc format, a length-distance pair is always encoded by a two-byte |
| 19 |
sequence. Of the 16 bits that make up these two bytes, 11 bits go to encoding |
| 20 |
the distance, 3 go to encoding the length, and the remaining two are used to |
| 21 |
make sure the decoder can identify the first byte as the beginning of such a |
| 22 |
two-byte sequence. |
| 23 |
|
| 24 |
PalmDoc combines LZ77 with a simple kind of byte pair compression. |
| 25 |
|
| 26 |
|
| 27 |
PalmDoc files are decoded as follows: |
| 28 |
------------------------------------- |
| 29 |
|
| 30 |
Read a byte from the compressed stream. If the byte is |
| 31 |
|
| 32 |
0x00: "1 literal" copy that byte unmodified to the decompressed stream. |
| 33 |
|
| 34 |
0x09 to 0x7f: "1 literal" copy that byte unmodified to the decompressed stream. |
| 35 |
|
| 36 |
0x01 to 0x08: "literals": the byte is interpreted as a count from 1 to 8, and |
| 37 |
that many literals are copied unmodified from the compressed stream to the |
| 38 |
decompressed stream. |
| 39 |
|
| 40 |
0x80 to 0xbf: "length, distance" pair: the 2 leftmost bits of this byte ('10') |
| 41 |
are discarded, and the following 6 bits are combined with the 8 bits of the |
| 42 |
next byte to make a 14 bit "distance, length" item. Those 14 bits are broken |
| 43 |
into 11 bits of distance backwards from the current location in the |
| 44 |
uncompressed text, and 3 bits of length to copy from that point |
| 45 |
(copying n+3 bytes, 3 to 10 bytes). |
| 46 |
|
| 47 |
0xc0 to 0xff: "byte pair": this byte is decoded into 2 characters: a space |
| 48 |
character, and a letter formed from this byte XORed with 0x80. |
| 49 |
|
| 50 |
Repeat from the beginning until there is no more bytes in the compressed file. |
| 51 |
|
| 52 |
PalmDOC data is always divided into 4096 byte blocks and the blocks are acted |
| 53 |
upon independently. |
| 54 |
|