Projects/Liberty/Appendix 3
Appendix 3 - HUS/VIP Decompression
In the .hus and .vip format files, the attribute, X displacement, and Y displacement of each stitch are held compressed using a version of the ARJ compression. An attribute has the values: 0x80 (stitch), 0x81 (jump), 0x84 (thread stop), and 0x90 (end stop); that is bit 7 is always set, bit 0 indicates jump without stitch, bit 2 indicates thread change stop, and bit 4 end of pattern stop; bits 1, 3, 5, 6 appear unused.
The compression uses a sliding window of past uncompressed values to source repeated strings of bytes, instead of outputting the string of bytes, a pointer (and length) back to an earlier version of the string is (coded and) output. A feature of this is, a self repeating string can be copied before it is fully output, for example, if 'ABC' has just been output and there is now a string 'ABCABCABC', the length would be 9, but the pointer would only point back 3 bytes (to the 'A') as the 'ABC' is copied to the output, they become available to copy again.
When there are no bytes to copy in the recent output, the new byte has to be output as is, a length of zero (or less than 3) indicates verbatim byte and no pointer. This is encoded as values 0 to 255 indicate verbatim byte and no pointer, values 256 or greater indicate length, but the true length is the value minus 256 plus 3.
How to Decompress
Allocate an output buffer of enough bytes to hold the uncompressed data, access is needed to some of the past decoded bytes. Either fetch bytes and add them to the output, or fetch length and pointer, then copy past bytes to the output. Repeat until output buffer is full.
Pseudo-code of Sliding Window Decompression:
Let uncompressed := new vector[0 to uncompressed-size - 1] of byte
-- allocate output buffer
Let count := 0 -- the number of bytes output, index to output buffer
While count < uncompressed-size Do
Let code := Fetch-Byte-or-Length
If code < 256 Then -- is byte
Let uncompressed[count] := code
Let count := count + 1
Else
Let length := code - 256 + 3 -- min length is 3
Let pointer := Fetch-Pointer
For length Times Do
If count < uncompressed-size Then -- not buffer overrun
If count > pointer Then -- not buffer under-run
Let uncompressed[count] :=
uncompressed[count - pointer - 1]
Else
Let uncompressed[count] := 0
End if
End if
Let count := count + 1
End for
End if
End while
Huffman Coding of Bytes or Lengths and Pointers
The sliding-window byte/length and pointer codes are packaged, the first 16 bits gives the package length in sliding-window codes.
To reduce the bit length of the byte or length symbols and the pointers, they are Huffman coded to reduce the length of the most frequent values. The Huffman tree is passed to the compressed output by sending the length of the Huffman code for each symbol in the symbol-set, run of zero encoding is used to fill in the length table of the many unused codes (of zero length). For the byte/length symbol Huffman code lengths, these are themselves Huffman coded.
The number of Huffman code byte/length symbol lengths is given in the next 5 bits (value 0 to 31, but actually limited to 19). If the number is zero then there is only one symbol which is contained in the next 5 bits and its code length is zero. After the third symbol, the next 2 bits provide a 0 to 3 length run of zeros. After the 'number' of symbols the rest of the lengths are set to zero.
Each symbol is processed thus, the next 3 bits give a value 0 to 7; the values 0 to 6 are used directly, but if the value is 7, then a series of next bits, up to 13. The series ends after the first 0 value bit or after the 13th bit, each 1 value bit increments the (length) value (giving a range 7 to 20); I suspect any value over 18 is an error, so a maximum of eleven 1 bits followed by a twelfth bit of 0. The value 0 to 18 is used to set the length of the next code.
A (virtual) Huffman tree is built using these 19 ordered length and symbol values. The next variable length codes can be used to uniquely identify a value.
The next 9 bits give the number byte/length symbols defined (and is typically 511 since the end code is coded as 510 - a bug?), again a 'number' of zero implies the next 9 bits give the only code used and its Huffman code does not need to be transmitted. For 'number' of times, a variable length Huffman code appear in the next bits and gives a value 0 to 18.
There are up to 19 symbols used to compress the byte/length symbol lengths. The symbol values 0 to 2 allow for a run of zeros: 0 implies run-length of one, 1 implies 3 plus the value of the next 4 bits, and 2 implies 20 plus the value of the next 9 bits. The remaining 16 values give the Huffman code length 1 to 16 bits (that is symbol value minus 2).
A (virtual) Huffman tree is built using these 511 ordered length and symbol values.
There are 511 byte/length symbols, byte ranges from 0 to 255 and usable length ranges from 3 to 256, where a length of 257 marks the end of the compressed data.
The pointer values are Huffman encoded and appear next, similar to above, the next 5 bits gives the number pointer symbols ranging from 0 to 19 (or 15). Again, 0 implies there is only one symbol and it is in the next 5 bits. Otherwise, the next 3 bits give a code length 0 to 6, and 7 again is used to increment length by each 1 bit until a 0 bit. The end of the table is filled with 0.
Fetch Byte or Length
Use the next variable length code to find the value of the Byte or Length, by descending the Huffman tree.
Fetch Pointer
Use the next variable length code to find the value of the Pointer, by descending the Huffman tree.
Huffman Style Processing
Initialize
Let NT = 19 Let NC = 511 Let NP = 15 Let package-remaining := 0 -- symbol/length code-length code-lengths Let T-len := new vector[0 to NT - 1] of (0 to 16) -- symbol/length code-lengths Let C-len := new vector[0 to NC - 1] of (0 to 16) -- pointer code-lengths Let P-len := new vector[0 to NP - 1] of (0 to 16)
Decode Sliding-window Byte/Length
-- prepare Huffman decoding trees If package-remaining = 0 Then Let package-remaining := Get-Bits( 16 ) Let T-tree := Build-T-tree Let C-tree := Build-C-tree( T-tree ) Let P-tree := Build-P-tree End if Let package-remaining := package-remaining - 1 Let byte-length := Huff-Decode( C-tree ) Return byte-length
Decode Sliding-window Pointer
Let pointer := Huff-Decode( P-tree ) Return pointer
Build T tree
T-tree.Delete-All
Let n := Get-Bits( 5 )
Let n := Min( n, NT )
If n = 0 Then
Let c := Get-Bits( 5 )
T-tree.Append( length := 0, bits := 0, symbol := c )
Else
Let i := 0
While i < n Do
Let c := Get-Bits( 3 )
If c = 7 Then
Let b := Get-Bits( 1 )
While b = 1 Do
Let c := c + 1
Let b := Get-Bits( 1 )
End while
End if
Let T-len[i] := c
Let i := i + 1
If i = 3 Then
Let c := Get-Bits( 2 )
While c > 0 Do
Let T-len[i] := 0
Let i := i + 1
Let c := c - 1
End while
End if
End while
While i < NT Do
Let T-len[i] := 0
Let i := i + 1
End while
Let b := 0
For len := 1 to 16 Do
Let b := b * 2 -- shift a 0 into LSB
For c := 0 to NT-1 Do
If T-len[c] = len Then
T-tree.Append( length := len, bits := b, symbol := c )
Let b := b + 1
End If
End for
End for
End If
Return T-tree
Build C tree ( T-tree )
C-tree.Delete-All
Let n := Get-Bits( 9 )
Let n := Min( n, NC )
If n = 0 Then
Let c := Get-Bits( 9 )
C-tree.Append( length := 0, bits := 0, symbol := c )
Else
Let i := 0
While i < n Do
Let c := Huff-Decode( T-tree )
If c <= 2 Then
If c = 0 Then
Let c := 1
Else If c = 1 Then
Let c := 3 + Get-Bits( 4 )
Else
Let c := 20 + Get-Bits( 9 )
End if
While c > 0 Do
Let C-len[i] := 0
Let i := i + 1
Let c := c - 1
End while
Else
Let C-len[i] := c - 2
Let i := i + 1
End if
End while
While i < NC Do
Let C-len[i] := 0
Let i := i + 1
End while
Let b := 0
For len := 1 to 16 Do
Let b := b * 2 -- shift a 0 into LSB
For c := 0 to NC-1 Do
If C-len[c] = len Then
C-tree.Append( length := len, bits := b, symbol := c )
Let b := b + 1
End If
End for
End for
End If
T-tree.Delete-All
Return C-tree
Build P tree
P-tree.Delete-All
Let n := Get-Bits( 5 )
Let n := Min( n, NP )
If n = 0 Then
Let c := Get-Bits( 5 )
P-tree.Append( length := 0, bits := 0, symbol := c )
Else
Let i := 0
While i < n Do
Let c := Get-Bits( 3 )
If c = 7 Then
Let b := Get-Bits( 1 )
While b = 1 Do
Let c := c + 1
Let b := Get-Bits( 1 )
End while
End if
Let P-len[i] := c
Let i := i + 1
End while
While i < NP Do
Let P-len[i] := 0
Let i := i + 1
End while
Let b := 0
For len := 1 to 16 Do
Let b := b * 2 -- shift a 0 into LSB
For c := 0 to NP-1 Do
If P-len[c] = len Then
P-tree.Append( length := len, bits := b, symbol := c )
Let b := b + 1
End If
End for
End for
End If
Return P-tree
Huff Decode ( tree )
Let sym := 0
Let b := 0 -- bits
Let i := 0 -- current tree entry
Let n := tree.length
Let l := 0 -- code length
For i := 0 to n - 1
If l < tree[i].length Then
Let b := b * 2^(tree[i].length - l)
Let b := b + Get-Bits( tree[i].length - l )
Let l := tree[i].length
End if
If tree[i].length = l And tree[i].bits = b Then
Let sym := tree[i].symbol
Exit for
End if
End for
Return sym