Overview
This appendix describes the squeezed relocatable-module format emitted by riscos-modsqz. It is a space-saving representation of a normal relocatable module image, intended to be expanded by the module loader before execution.
The description here is derived from the compressor implementation in this source tree. It documents the on-disc layout emitted by the tool and the encoding algorithm it uses for the compressed body.
Compression format reference
Overall layout
A squeezed module starts with a compact header, followed by the encoded module body, the encoded decode tables, padding to a word boundary, and a trailing compression header.
The compact header retains only the fields needed by the squeezed-module loader together with inline copies of the title and help strings, and optionally the module flags words.
| Offset | Size | Field | Contents |
|---|---|---|---|
| 0 | 4 | startoffset | Reserved. The compressor writes zero here. |
| 4 | 4 | initoffset | Total squeezed image length in bytes, with bit 31 set to mark the module as squeezed. |
| 8 | 4 | dieoffset | Unused in the compact header. |
| 12 | 4 | serviceoffset | Unused in the compact header. |
| 16 | 4 | titleoffset | Offset to the title string within the compact header. |
| 20 | 4 | helpoffset | Offset to the help string within the compact header. |
| 24-48 | 24 | optional header words | Either omitted, or occupied by the original fields from commandtable through flagsoffset (six 4-byte words: commandtable, swichunk, swihandler, swidecodetable, swidecodecode, flagsoffset). |
| variable | titlestring/help/flags | Inline title string, inline help string, and optional flags-word block. | |
| variable | encoded body | Compressed representation of the original module image, rounded up to an even number of words before encoding. | |
| variable | encoded tables | Encoded full-word and upper-24-bit decode tables. | |
| variable | padding | Zero bytes to align the trailing compression header to 4 bytes. | |
| variable | 20 | compression header | Five-word trailer describing the sizes of the encoded data and tables. |
Compact module header
The input module is first copied to a temporary buffer with a fresh header area placed in front of it. The title string and help string are copied into this fresh header. If the original module has a valid flags-word block, that block is copied after the help string.
If no flags-word block is present, the compact header omits the six optional header words from commandtable through flagsoffset shown in the offset-table above. This saves 24 bytes.
The original module body is otherwise compressed as a whole, starting from the original startoffset word of the unsqueezed image.
Trailing compression header
The compressed body ends with a five-word trailer:
| Offset | Size | Field | Contents |
|---|---|---|---|
| 0 | 4 | decodedsize | Size in bytes of the original module image after it has been rounded up to an even number of words. |
| 4 | 4 | encodedsize | Size in bytes of the encoded word stream. |
| 8 | 4 | encodedtabs | Combined size in bytes of the encoded full-word and upper-24-bit tables, including any alignment padding before this trailer. |
| 12 | 4 | nshorts | Number of entries in the full-word table. |
| 16 | 4 | nlongs | Number of entries in the upper-24-bit table. |
Word stream model
The unsqueezed module image is rounded up by 8 bytes and then treated as a sequence of 32-bit words in the target byte order. The compressor encodes two words at a time. For each pair it emits the payload bytes for the second word first, then the payload bytes for the first word, followed by a single tag byte containing two 4-bit nibbles.
The low nibble describes the first word in the pair; the high nibble describes the second word.
Nibble codes
Four classes of word encoding are used:
| Nibble | Meaning |
|---|---|
| 0 | Zero word. No payload bytes follow for this word. |
| 1 | Literal 32-bit word. Four payload bytes follow. |
| 2-8 | Upper-24-bit table reference. The low byte of the original word is emitted first, followed by an 8-bit table index; the nibble value minus 2 supplies the upper 3 bits of the table index. |
| 9-15 | Full-word table reference. One 8-bit table index follows; the nibble value minus 9 supplies the upper 3 bits of the table index. |
Each table can therefore contain up to 7 × 256 = 1792 entries.
Table construction
The compressor counts occurrences of every non-zero 32-bit word and counts zero words separately. The most frequent non-zero 32-bit words are placed into the full-word table, sorted into ascending numeric order. Up to 1792 values are retained.
Values not selected for the full-word table are then reduced to their upper 24 bits by discarding the low byte. Frequencies of identical upper-24-bit values are merged, and the most frequent merged values are placed into the upper-24-bit table, again sorted into ascending numeric order. Up to 1792 values are retained.
Table serialisation
Both decode tables are serialised as ascending sequences of deltas from the previous table value, with the previous value initialised to &FFFFFFFF. The same delta encoder is used for both tables, except that the upper-24-bit table omits the highest byte in the longest literal form.
Repeated delta-1 runs are packed specially. Runs of 1 to 9 consecutive +1 deltas are emitted as a single byte whose value is the run length.
Other deltas are encoded as follows:
| Byte sequence | Meaning |
|---|---|
| 1-9 | Run of that many consecutive delta-1 values. |
| 12-91 | Single-byte encoding for deltas 2 to 81. The stored byte is the delta plus 10. |
| 92-173 plus 1 byte | Two-byte encoding for deltas 82 to 20991. The first byte stores the top part plus 92, followed by the low byte. |
| 174-255 plus 2 bytes | Three-byte encoding for deltas 20992 to 5373951. The first byte stores the top part plus 174, followed by the low and middle bytes. |
| 0 plus 3 or 4 bytes | Literal delta. Three bytes are used for the upper-24-bit table, four bytes for the full-word table. |
Compression heuristics
Before encoding, the tool estimates the compressed size from the number of zero words, full-word hits, upper-24-bit hits, remaining literals, the sizes of both tables, and a fixed safety margin of 1024 bytes for the decompressor and estimation slack.
Compression is normally attempted only when this estimate is at most 90% of the original image size. With the -f option, the encoder will still proceed provided the real encoded output does not exceed the input size.
Worked example
Interpreting a nibble byte
If the tag byte is &A4, the low nibble is &4 and the high nibble is &A. The first word therefore uses the upper-24-bit table with top index bits 2, while the second word uses the full-word table with top index bits 1.
A complete synthetic decode
riscos-modsqz currently segfaults on every module tested, a known bug awaiting a fix. The worked decode below is therefore synthetic: a two-word body chosen to be small enough to trace by hand.
Take an unsqueezed body of just two words, &00000003 followed by &00000000, with no flags-word block (so the six optional header words are omitted) and a full-word table holding the single entry &00000003 at index 0.
Encoding the pair: the compressor emits the payload for the second word first. The second word is zero, so its nibble is 0 and no payload byte is emitted for it. The first word matches the one full-word table entry at index 0, so its nibble is 9 (full-word reference, top index bits 0) and its payload is a single index byte, &00. The tag byte combines the two nibbles, second word in the high nibble and first word in the low nibble: (0<<4)|9 = &09. The encoded body is therefore the two bytes &00 &09 (index byte, then tag byte), 2 bytes encoding an 8-byte decoded body.
Encoding the full-word table's single entry: the previous value starts at &FFFFFFFF, so the first delta is &00000003 - &FFFFFFFF = 4 using the same wraparound 32-bit subtraction the compressor uses. A delta of 4 falls in the 12-91 single-byte range (deltas 2 to 81), stored as the delta plus 10, giving the single table byte 14 (&0E). The upper-24-bit table is empty, contributing no bytes. One padding byte is then needed to align the trailing compression header to a 4-byte boundary, since the encoded body (2 bytes) plus the encoded table (1 byte) is 3 bytes.
The trailing compression header for this example is therefore: decodedsize=8 (the two-word body), encodedsize=2 (the body bytes above), encodedtabs=2 (the 1 table byte plus the 1 padding byte), nshorts=1 (one full-word table entry), and nlongs=0 (no upper-24-bit table entries). Decoding this trailer alone, before even reaching the body, already tells a loader exactly how many bytes to read back for each section.