Squinch format

This document specifies version 1 of the Squinch byte format.

Every Squinch stream starts with this 16-byte header:

Offset Size Value
0 7 ASCII SQUINCH
7 1 Format version. Version 1 is current; version 0 is reserved.
8 2 Big-endian history-window size. Zero represents 65536.
10 6 Big-endian uncompressed size. Its leading byte is zero.

The uncompressed-size field stores a known total through 2^40 - 1. All six bytes are zero when the size is unknown or larger than 2^40 - 1.

Encoded bytes

After the header, each byte is interpreted as either a literal value or an instruction.

Bytes Meaning
0x00 through 0xF4 Output the byte.
0xF5 y Repeat the most recently output byte y times. y values 0 through 2 are reserved.
0xF5 0x01 yy Repeat the most recently output byte yy + 255 times. yy is a 16-bit big-endian value and must be in the range 1 through 65535, an yy value of 0 is reserved.
0xF6 x If x <= 248, copy 3 bytes from offset x + 1. If x >= 249, output byte (x - 249) + 0xF5; this allows encoding the verbatim bytes 0xF5 through 0xFB.
0xF7 x Copy four bytes from offset x + 1.
0xF8 x Copy five bytes from offset x + 1.
0xF9 x Copy six bytes from offset x + 1.
0xFA x Copy seven bytes from offset x + 1.
0xFB y x Copy y bytes from offset x + 1. Values 0 through 7 for y are reserved.
0xFB 0x01 abc Copy bytes using a 12-bit length followed by a 12-bit offset minus 1, packed into the big-endian value abc. Length 0 is reserved.
0xFB 0x02 y xx Copy y bytes from offset xx + 1. y is an 8-bit value, and xx is a 16-bit big-endian value. Value 0 for y is reserved.
0xFB 0x03 yy xx Copy yy + 255 bytes from offset xx + 1. Both yy and xx are 16-bit big-endian values. Value 0 for yy is reserved.
0xFC through 0xFF Output the byte.

"Output" means adding data to the uncompressed byte sequence. "Copy" means adding bytes from the history window to that sequence.

History window

The history window contains the most recent literal and copied bytes, with offset 0 selecting the newest byte and offset windowSize - 1 selecting the oldest. Every copy operation has a minimum offset of 1. A decoder must reject a copy whose initial offset is not available in the history.

Every literal or copied byte is appended to the history immediately after it is output. A copy can therefore read bytes that the same copy has already output. RLE operations only add repeated bytes to the uncompressed sequence; they do not modify the history.

The implementation details of history storage, copy processing, and streaming decoding are described in Algorithm.md.