the INPUT-BYTES instruction.
Additionally, all memory addresses between Address 0 and Address 31
inclusive are initialized to endpoint-specific values by the UDVM, so
they must be specified as padding in the bytecode, or the standard
SigComp header cannot be used. Memory addresses from Address 32 to
Address (destination - 1) inclusive are initialized to 0, so they
must be specified either as padding or as 0s if the bytecode is to be
successfully uploaded using the standard SigComp header.
The code_len field should be set to the smallest value such that all
memory addresses beginning at Address (destination + code_len) are
either as initialised by the UDVM (to 0) or as set by the bytecode at
runtime.
The "uploaded UDVM bytecode" should be set to contain the segment of
bytecode that lies between Address (destination) and Address
(destination + code_len - 1) inclusive.
4. Compression Algorithms
This section describes a number of compression algorithms that can be
used by a SigComp compressor. In each case, the document provides
UDVM bytecode for the corresponding decompression algorithm, which
can be uploaded to the receiving endpoint as part of a SigComp
message. Each algorithm (as written in this section) assumes that
there is a 16K decompression memory size, there are 16 cycles per
bit, and there is an 8K state memory size. Decompression will
succeed with a smaller value for state memory size; however, the full
state will not be created.
Section 4.1.1 covers a simple algorithm in some detail, including the
steps required to compress and decompress a SigComp message. The
remaining sections cover well-known compression algorithms that can
be adapted for use in SigComp with minimal modification.
4.1. Well-known Compression Algorithms
4.1.1. LZ77
This section describes how to implement a very simple compression
algorithm based on LZ77 [5].
A compressed message generated by the simplified LZ77 scheme consists
of a sequence of 4-byte characters, where each character contains a
2-byte position value followed by a 2-byte length value. Each pair
of integers identifies a byte string in the UDVM memory; when
concatenated, these byte strings form the decompressed message.
When implementing a bytecode decompressor for the simplified LZ77
scheme, the UDVM memory is partitioned into five distinct areas, as
shown below:
0 64 128 256 512
| scratch-pad | variables | bytecode | dictionary | circular buffer |
+-------------+-----------+----------+------------+-----------------+
<-----------> <---------> <--------> <----------> <--------------->
64 bytes 64 bytes 128 bytes 256 bytes 512+ bytes
The first 128 bytes are used to hold the 2-byte variables needed by
the LZ77 decompressor. Within this memory, the first 64 bytes are
used as a scratch-pad, holding the 2-byte variables that can be
discarded between SigComp messages. In contrast, the next 64 bytes
(and in fact all of the UDVM memory starting from Address 64) should
be saved after decompressing a SigComp message to improve the
compression ratio of subsequent messages.
The bytecode for the LZ77 decompressor is stored beginning at Address
128. A total of 128 bytes are reserved for the bytecode although the
LZ77 decompressor requires less; this allows room for adding
additional features to the decompressor at a later stage.
The next 256 bytes are initialized by the bytecode to contain the
integers 0 to 255 inclusive. The purpose of this memory area is to
provide a dictionary of all possible uncompressed characters; this is
important to ensure that the compressor can always generate a
sequence of position/length pairs that encode a given message. For
example, a byte with value 0x41 (corresponding to the ASCII character
"A") can be found at Address 0x0141 of the UDVM memory, so the
compressed character 0x0141 0001 will decompress to give this ASCII
character. Note that encoding each byte in the application message
as a separate 4-byte compressed character is not recommended,
however, as the resulting "compressed" message is four times as large
as the original uncompressed message.
The compression ratio of LZ77 is improved by the remaining UDVM
memory, which is used to store a history buffer containing the
previously decompressed messages. Compressed characters can point to
strings that have previously been decompressed and stored in the
buffer, so the overall compression ratio of the LZ77 algorithm
improves as the decompressor "learns" more text strings and is able
to encode longer strings using a single compressed character. The
buffer is circular, so older messages are overwritten by new data
when the buffer becomes full.
The steps required to implement an LZ77 compressor and decompressor
are similar, although compression is more processor-intensive as it
requires a searching operation to be performed. Assembly for the
simplified LZ77 decompressor is given below:
; Variables that do not need to be stored after decompressing each
; SigComp message are stored here:
at (32)
:position_value pad (2)
:length_value pad (2)
at (42)
set (requested_feedback_location, 0)
; The UDVM registers must be stored beginning at Address 64:
at (64)
; Variables that should be stored after decompressing a message are
; stored here. These variables will form part of the SigComp state
; item created by the bytecode:
:byte_copy_left pad (2)
:byte_copy_right pad (2)
:decompressed_pointer pad (2)
set (returned_parameters_location, 0)
align (64)
:initialize_memory
set (udvm_memory_size, 8192)
set (state_length, (udvm_memory_size - 64))
; The UDVM registers byte_copy_left and byte_copy_right are set to
; indicate the bounds of the circular buffer in the UDVM memory. A
; variable decompressed_pointer is also created and set pointing to
; the start of the circular buffer:
MULTILOAD (64, 3, circular_buffer, udvm_memory_size, circular_buffer)
; The "dictionary" area of the UDVM memory is initialized to contain
; the values 0 to 255 inclusive:
MEMSET (static_dictionary, 256, 0, 1)
:decompress_sigcomp_message
:next_character
; The next character in the compressed message is read by the UDVM
; and the position and length integers are stored in the variables
; position_value and length_value, respectively. If no more
; compressed data is available, the decompressor jumps to the
; "end_of_message" subroutine:
INPUT-BYTES (4, position_value, end_of_message)
; The position_value and length_value point to a byte string in the
; UDVM memory, which is copied into the circular buffer at the
; position specified by decompressed_pointer. This allows the string
; to be referenced by later characters in the compressed message:
COPY-LITERAL ($position_value, $length_value, $decompressed_pointer)
; The byte string is also outputted onto the end of the decompressed
; message:
OUTPUT ($position_value, $length_value)
; The decompressor jumps back to consider the next character in the
; compressed message:
JUMP (next_character)
:end_of_message
; The decompressor saves the UDVM memory and halts:
END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0)
at (256)
; Memory for the dictionary and the circular buffer are reserved by
; the following statements:
:static_dictionary pad (256)
:circular_buffer
The task of an LZ77 compressor is simply to discover a sequence of
4-byte compressed characters that the above bytecode will decompress
to give the desired application message. As an example, a message
compressed using the simplified LZ77 algorithm is given below:
0x0154 0001 0168 0001 0165 0001 0120 0001 0152 0001 0165 0001 0173
0x0002 0161 0001 0175 0001 0172 0001 0161 0001 016e 0001 0174 0001
0x0120 0001 0161 0001 020d 0002 0174 0001 0201 0003 0145 0001 016e
0x0001 0164 0001 0120 0001 016f 0001 0166 0001 0211 0005 0155 0001
0x016e 0001 0169 0001 0176 0001 0165 0001 0172 0002 0165 0001 010a
0x0001
The uncompressed message is "The Restaurant at the End of the
Universe\n".
The bytecode for the LZ77 decompressor can be uploaded as part of the
compressed message, as specified in Section 3.3. However, in order
to improve the overall compression ratio, it is important to avoid
uploading bytecode in every compressed message. For this reason,
SigComp allows the UDVM to save an area of its memory as a state item
between compressed messages. Once a state item has been created, it
can be retrieved by sending the corresponding state identifier using
the following SigComp message format:
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 1 1 1 1 | T | 1 |
+---+---+---+---+---+---+---+---+
| |
: returned feedback item : if T = 1
| |
+---+---+---+---+---+---+---+---+
| |
: partial state identifier :
| |
+---+---+---+---+---+---+---+---+
| |
: remaining SigComp message :
| |
+---+---+---+---+---+---+---+---+
The partial_state_identifier field must contain the first 6 bytes of
the state identifier for the state item to be accessed (see [2] for
details of how state identifiers are derived).
Note that the partial_state_identifier field could be 9 or 12 bytes
and that in these cases, bits 6 and 7 of the first byte of the
message would be 10 or 11, respectively.
4.1.2. LZSS
This section provides UDVM bytecode for the simple but effective LZSS
compression algorithm [6].
The principal improvement offered by LZSS over LZ77 is that each
compressed character begins with a 1-bit indicator flag to specify
whether the character is a literal or an offset/length pair. A
literal value is simply a single uncompressed byte that is appended
directly to the decompressed message.
An offset/length pair contains a 12-bit offset value from 1 to 4096
inclusive, followed by a 4-bit length value from 3 to 18 inclusive.
Taken together, these values specify one of the previously received
text strings in the circular buffer, which is then appended to the
end of the decompressed message.
Assembly for an LZSS decompressor is given below:
at (32)
readonly (0)
:index pad (2)
:length_value pad (2)
:old_pointer pad (2)
at (42)
set (requested_feedback_location, 0)
at (64)
:byte_copy_left pad (2)
:byte_copy_right pad (2)
:input_bit_order pad (2)
:decompressed_pointer pad (2)
set (returned_parameters_location, 0)
align (64)
readonly (1)
:initialize_memory
set (udvm_memory_size, 8192)
set (state_length, (udvm_memory_size - 64))
MULTILOAD (64, 4, circular_buffer, udvm_memory_size, 0,
circular_buffer)
:decompress_sigcomp_message
:next_character
INPUT-HUFFMAN (index, end_of_message, 2, 9, 0, 255, 16384, 4, 4096,
8191, 1)
COMPARE ($index, 8192, length, end_of_message, literal)
:literal
set (index_lsb, (index + 1))
OUTPUT (index_lsb, 1)
COPY-LITERAL (index_lsb, 1, $decompressed_pointer)
JUMP (next_character)
:length
INPUT-BITS (4, length_value, !)
ADD ($length_value, 3)
LOAD (old_pointer, $decompressed_pointer)
COPY-OFFSET ($index, $length_value, $decompressed_pointer)
OUTPUT ($old_pointer, $length_value)
JUMP (next_character)
:end_of_message
END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0)
readonly (0)
:circular_buffer
An example of a message compressed using the LZSS algorithm is given
below:
0x279a 0406 e378 b200 6074 1018 4ce6 1349 b842
The uncompressed message is "Oh no, not again!".
4.1.3. LZW
This section provides UDVM bytecode for the well-known LZW
compression algorithm LZW [7]. This algorithm is used in a number of
standards including the GIF image format.
LZW compression operates in a similar manner to LZ77 in that it
maintains a circular buffer of previously received decompressed data,
and each compressed character references exactly one byte string from
the circular buffer. However, LZW also maintains a "codebook"
containing 1024 position/length pairs that point to byte strings that
LZW believes are most likely to occur in the uncompressed data.
The byte strings stored in the LZW codebook can be referenced by
sending a single 10-bit value from 0 to 1023 inclusive. The UDVM
extracts the corresponding text string from the codebook and appends
it to the end of the decompressed message. It then creates a new
codebook entry containing the current text string and the next
character to occur in the decompressed message.
Assembly for an LZW decompressor is given below:
at (32)
:length_value pad (2)
:position_value pad (2)
:index pad (2)
at (42)
set (requested_feedback_location, 0)
at (64)
:byte_copy_left pad (2)
:byte_copy_right pad (2)
:input_bit_order pad (2)
:codebook_next pad (2)
:current_length pad (2)
:decompressed_pointer pad (2)
set (returned_parameters_location, 0)
align (64)
:initialize_memory
set (udvm_memory_size, 8192)
set (state_length, (udvm_memory_size - 64))
MULTILOAD (64, 6, circular_buffer, udvm_memory_size, 0, codebook, 1,
static_dictionary)
:initialize_codebook
; The following instructions are used to initialize the first 256
; entries in the LZW codebook with single ASCII characters:
set (index_lsb, (index + 1))
set (current_length_lsb, (current_length + 1))
COPY-LITERAL (current_length_lsb, 3, $codebook_next)
COPY-LITERAL (index_lsb, 1, $decompressed_pointer)
ADD ($index, 1)
COMPARE ($index, 256, initialize_codebook, next_character, 0)
:decompress_sigcomp_message
:next_character
; The following INPUT-BITS instruction extracts 10 bits from the
; compressed message:
INPUT-BITS (10, index, end_of_message)
; The following instructions interpret the received bits as an index
; into the LZW codebook and extract the corresponding
; position/length pair:
set (length_value_lsb, (length_value + 1))
MULTIPLY ($index, 3)
ADD ($index, codebook)
COPY ($index, 3, length_value_lsb)
; The following instructions append the selected text string to the
; circular buffer and create a new codebook entry pointing to this
; text string:
LOAD (current_length, 1)
ADD ($current_length, $length_value)
COPY-LITERAL (current_length_lsb, 3, $codebook_next)
COPY-LITERAL ($position_value, $length_value, $decompressed_pointer)
; The following instruction outputs the text string specified by the
; position/length pair:
OUTPUT ($position_value, $length_value)
JUMP (next_character)
:end_of_message
END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0)
:static_dictionary pad (256)
:circular_buffer
at (4492)
:codebook
An example of a message compressed using the LZW algorithm is given
below:
0x14c6 f080 6c1b c6e1 9c20 1846 e190 201d 0684 206b 1cc2 0198 6f1c
0x9071 b06c 42c6 8195 111a 4731 a021 02bf f0
The uncompressed message is "So long and thanks for all the fish!\n".
4.1.4. DEFLATE
This section provides UDVM bytecode for the DEFLATE compression
algorithm. DEFLATE is the algorithm used in the well-known "gzip"
file format.
The following bytecode will decompress the DEFLATE compressed data
format [8] with the following modifications:
1. The DEFLATE compressed data format separates blocks of compressed
data by transmitting 7 consecutive zero bits. Each SigComp
message is assumed to contain a separate block of compressed
data, so the end-of-block bits are implicit and do not need to be
transmitted at the end of a SigComp message.
2. This bytecode supports only DEFLATE block type 01 (data
compressed with fixed Huffman codes).
Assembly for the DEFLATE decompressor is given below:
at (32)
readonly (0)
:index pad (2)
:extra_length_bits pad (2)
:length_value pad (2)
:extra_distance_bits pad (2)
:distance_value pad (2)
at (42)
set (requested_feedback_location, 0)
at (64)
:byte_copy_left pad (2)
:byte_copy_right pad (2)
:input_bit_order pad (2)
:decompressed_pointer pad (2)
:length_table pad (116)
:distance_table pad (120)
set (returned_parameters_location, 0)
align (64)
readonly (1)
:initialize_memory
set (udvm_memory_size, 8192)
set (state_length, (udvm_memory_size - 64))
set (length_table_start, (((length_table - 4) + 65536) / 4))
set (length_table_mid, (length_table_start + 24))
set (distance_table_start, (distance_table / 4))
MULTILOAD (64, 122, circular_buffer, udvm_memory_size, 5,
circular_buffer,
0, 3, 0, 4, 0, 5,
0, 6, 0, 7, 0, 8,
0, 9, 0, 10, 1, 11,
1, 13, 1, 15, 1, 17,
2, 19, 2, 23, 2, 27,
2, 31, 3, 35, 3, 43,
3, 51, 3, 59, 4, 67,
4, 83, 4, 99, 4, 115,
5, 131, 5, 163, 5, 195,
5, 227, 0, 258,
0, 1, 0, 2, 0, 3,
0, 4, 1, 5, 1, 7,
2, 9, 2, 13, 3, 17,
3, 25, 4, 33, 4, 49,
5, 65, 5, 97, 6, 129,
6, 193, 7, 257, 7, 385,
8, 513, 8, 769, 9, 1025,
9, 1537, 10, 2049, 10, 3073,
11, 4097, 11, 6145, 12, 8193,
12, 12289, 13, 16385, 13, 24577)
:decompress_sigcomp_message
INPUT-BITS (3, extra_length_bits, !)
:next_character
INPUT-HUFFMAN (index, end_of_message, 4,
7, 0, 23, length_table_start,
1, 48, 191, 0,
0, 192, 199, length_table_mid,
1, 400, 511, 144)
COMPARE ($index, length_table_start, literal, end_of_message,
length_distance)
:literal
set (index_lsb, (index + 1))
OUTPUT (index_lsb, 1)
COPY-LITERAL (index_lsb, 1, $decompressed_pointer)
JUMP (next_character)
:length_distance
; this is the length part
MULTIPLY ($index, 4)
COPY ($index, 4, extra_length_bits)
INPUT-BITS ($extra_length_bits, extra_length_bits, !)
ADD ($length_value, $extra_length_bits)
; this is the distance part
INPUT-HUFFMAN (index, !, 1, 5, 0, 31, distance_table_start)
MULTIPLY ($index, 4)
COPY ($index, 4, extra_distance_bits)
INPUT-BITS ($extra_distance_bits, extra_distance_bits, !)
ADD ($distance_value, $extra_distance_bits)
LOAD (index, $decompressed_pointer)
COPY-OFFSET ($distance_value, $length_value, $decompressed_pointer)
OUTPUT ($index, $length_value)
JUMP (next_character)
:end_of_message
END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0)
readonly (0)
:circular_buffer
An example of a message compressed using the DEFLATE algorithm is
given below:
0xf3c9 4c4b d551 28c9 4855 08cd cb2c 4b2d 2a4e 5548 cc4b 5170 0532
0x2b4b 3232 f3d2 b900
The uncompressed message is "Life, the Universe and Everything\n".
4.1.5. LZJH
This section provides UDVM bytecode for the LZJH compression
algorithm. LZJH is the algorithm adopted by the International
Telecommunication Union (ITU-T) Recommendation V.44 [9].
Assembly for the LZJH decompressor is given below:
at (32)
readonly (0)
; The following 2-byte variables are stored in the scratch-pad memory
; area because they do not need to be saved after decompressing a
; SigComp message:
:length_value pad (2)
:position_value pad (2)
:index pad (2)
:extra_extension_bits pad (2)
:codebook_old pad (2)
at (42)
set (requested_feedback_location, 0)
at (64)
; UDVM_registers
:byte_copy_left pad (2)
:byte_copy_right pad (2)
:input_bit_order pad (2)
; The following 2-byte variables are saved as state after
; decompressing a SigComp message:
:current_length pad (2)
:decompressed_pointer pad (2)
:ordinal_length pad (2)
:codeword_length pad (2)
:codebook_next pad (2)
set (returned_parameters_location, 0)
align (64)
readonly (1)
:initialize_memory
; The following constants can be adjusted to configure the LZJH
; decompressor. The current settings are as recommended in the V.44