const type: msbHuffmanDecoder

Type to describe Huffman decoding from a msbInBitStream. This Huffman encoding is used by JPEG files.

const type: lsbHuffmanDecoder

Type to describe Huffman decoding from a lsbInBitStream. This Huffman decoding is used by the inflate (deflate) algorithm.

const type: huffmanEncoding

Type to describe the Huffman encoding of one symbol.

const type: huffmanEncoder

Type to describe a Huffman encoder. The Huffman encoder can be used for writing in MSB-First or LSB-First order. This Huffman encoding is used by JPEG files and by the deflate compression algorithm.

const func symbolsWithCodeLengthType: computeSymbolsWithCodeLength (in array integer: codeLengths)

Compute lists of symbols (index of codeLength) ordered by code langth. The result is a two-dimensional array where the first index is a code length.

symbolsWithCodeLength := computeSymbolsWithCodeLength(codeLengths);
# Now symbolsWithCodeLength[2] is an array of symbols with length 2.

Parameters:

codeLengths - Array to map the symbols (index) to the number of bits used to encode this symbol. Zero means: This symbol is not used.

Returns:

an array of symbol arrays with the code length as first index.

const func msbHuffmanDecoder: createMsbHuffmanDecoder (in integer: maximumCodeLength, in array integer: numberOfCodesWithLength, in string: huffmanSymbols)

Create a Huffman decoder for reading in MSB-First order. This Huffman encoding is used by JPEG files. It can happen that huffmanSymbols contains the same value twice. In that case the same symbol is encoded in two ways. This makes absolutely no sense but it can happen. For that reason it is necessary to use decoder.codeLengths with the same index as decoder.symbols.

Parameters:

maximumCodeLength - Maximum Huffman code length used.

numberOfCodesWithLength - Array to map bit width (index) to the number of symbols encoded with this bit width.

huffmanSymbols - String with symbols ordered by the bit width.

const func msbHuffmanDecoder: createMsbHuffmanDecoder (in array integer: codeLengths)

Create a Huffman decoder for reading in MSB-First order. This Huffman decoding is used by the BZIP2 algorithm. Non-optimal Huffman encodings, where symbols are encoded with more bits than necessary, are accepted as well. The decoder is created as follows: E.g.: The code lengths (in bits) of

4 0 0 6 5 3 3 3 3 3 4 3 0 0 0 0 5 5 6

describe that 0 is encoded with 4 bits, 3 with 6 bits, etc. This leads to the following encoding lengths:

length 3: (5, 6, 7, 8, 9, 11)
length 4: (0, 10)
length 5: (4, 16, 17)
length 6: (3, 18)

Beginning with the lowest length the following encodings are generated:

000: 5
001: 6
...
101: 11

For the next length (4 instead of 3) the value is incremented and shifted:

1100: 0

The decoder should be able fetch the maximum length of bits and to use it as index. In order to allow that the data must be transformed. The bits must be left shifted and all variants of lower bits must be added:

000000 encodes 5
...
000111 encodes 5
001000 encodes 6
...
101000 encodes 11
...
101111 encodes 11
110000 encodes 0
...
110011 encodes 0
...

Parameters:

codeLengths - Array to map the symbols (index) to the number of bits used to encode this symbol. Zero means: This symbol is not used.

const func integer: getHuffmanSymbol (inout msbInBitStream: inBitStream, in msbHuffmanDecoder: decoder)

Get a Huffman symbol from a msbInBitStream using the Huffman decoder. The read direction is from MSB (most significant bit) to LSB (least significant bit). The function peeks bits from inBitStream. By default inBitStream appends some '\16#ff;' bytes to allow that bits can be peeked always.

aSymbol := getHuffmanSymbol(compressedStream, huffmanDecoder);

Parameters:

inBitStream - MSB orderd bit stream from which the bits are skipped.

decoder - Huffman decoder defining the bit sequences that encode the symbols.

const func lsbHuffmanDecoder: createLsbHuffmanDecoder (in array integer: codeLengths)

Create a Huffman decoder for reading in LSB-First order. This Huffman decoding is used by the inflate (deflate) algorithm. Non-optimal Huffman encodings, where symbols are encoded with more bits than necessary, are accepted as well. The decoder is created as follows: E.g.: The code lengths (in bits) of

4 0 0 6 5 3 3 3 3 3 4 3 0 0 0 0 5 5 6

describe that 0 is encoded with 4 bits, 3 with 6 bits, etc. This leads to the following encoding lengths:

length 3: (5, 6, 7, 8, 9, 11)
length 4: (0, 10)
length 5: (4, 16, 17)
length 6: (3, 18)

Beginning with the lowest length the following encodings are generated:

000: 5
001: 6
...
101: 11

For the next length (4 instead of 3) the value is incremented and shifted:

1100: 0

The decoder should be able fetch the maximum length of bits and to use it as index. In order to allow that the data must be transformed. The bits must be flipped and all variants of higher bits must be added:

000000 encodes 5
000001 encodes 9
000010 encodes 7
000011 encodes 0
000100 encodes 6
...
001000 encodes 5
001001 encodes 9
001010 encodes 7
...

Parameters:

codeLengths - Array to map the symbols (index) to the number of bits used to encode this symbol. Zero means: This symbol is not used.

const func integer: getHuffmanSymbol (inout lsbInBitStream: inBitStream, in lsbHuffmanDecoder: decoder)

Get a Huffman symbol from a lsbInBitStream using the Huffman decoder. The read direction is from LSB (least significant bit) to MSB (most significant bit). The function peeks bits from inBitStream. By default inBitStream appends some '\16#ff;' bytes to allow that bits can be peeked always.

aSymbol := getHuffmanSymbol(compressedStream, huffmanDecoder);

Parameters:

inBitStream - LSB orderd bit stream from which the bits are skipped.

decoder - Huffman decoder defining the bit sequences that encode the symbols.

const proc: putHuffmanSymbol (inout lsbOutBitStream: outBitStream, in huffmanEncoding: encoding)

Write a huffman symbol to a lsbOutBitStream using the huffman outNode. The write direction is from LSB (least significant bit) to MSB (most significant bit).

putHuffmanSymbol(compressedStream, encoder[huffmanSymbol]);

Parameters:

outBitStream - LSB orderd bit stream to which the bits are written.

encoding - Huffman encoding which defines the actual huffmanCode and the codeLength.

const proc: putHuffmanSymbol (inout msbOutBitStream: outBitStream, in huffmanEncoding: encoding)

Write a huffman symbol to a msbOutBitStream using the huffman encoding. The write direction is from MSB (most significant bit) to LSB (least significant bit).

putHuffmanSymbol(compressedStream, encoder[huffmanSymbol]);

Parameters:

outBitStream - MSB orderd bit stream to which the bits are written.

encoding - Huffman encoding which defines the actual huffmanCode and the codeLength.

const func array integer: getHuffmanCodeLengths (in array integer: symbolCount)

Create an array of code lengths from the array symbolCount. The indices of the symbolCount array are the symbols to be huffman encoded. The indices of the returned code lengths array are the symbols to be huffman encoded.

Parameters:

symbolCount - Array of occurances of the corresponding symbol (index).

Returns:

an array of code lengths of the corresponding symbol (index).

const proc: reduceMaximumHuffmanCodeLength (inout array integer: codeLengths, in integer: allowedMaximum)

Reduce the maximum code length of an Huffman encoding to allowedMaximum. The given codeLengths array is changed to fit to the allowedMaximum.

Parameters:

codeLengths - Array to map the symbols (index) to the number of bits used to encode this symbol. Zero means: This symbol is not used.

allowedMaximum - Target maximum code length of the Huffman encoding.

const func huffmanEncoder: createHuffmanEncoder (in array integer: codeLengths)

Create a huffmanEncoder from the given codeLengths array. The Huffman encoder can be used for writing in MSB-First or LSB-First order. This Huffman encoding is used by JPEG files and by the deflate compression algorithm.

Parameters:

codeLengths - Array to map the symbols (index) to the number of bits used to encode this symbol. Zero means: This symbol is not used.