Debian Codegraph @

format_docs/compression/palmdoc.txt

raw
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