; specification (given that a total of 8K UDVM memory is available):
set (udvm_memory_size, 8192) ; sets the total memory for LZJH
set (max_extension_length, 8) ; sets the maximum string extension
set (min_ordinal_length, 7) ; sets the minimum ordinal length
set (min_codeword_length, 6) ; sets the minimum codeword length
set (codebook_start, 4492)
set (first_codeword, (codebook_start - 12))
set (state_length, (udvm_memory_size - 64))
MULTILOAD (64, 8, circular_buffer, udvm_memory_size, 7, 0,
circular_buffer, min_ordinal_length, min_codeword_length,
codebook_start)
:decompress_sigcomp_message
:standard_prefix
; The following code decompresses the standard 1-bit LZJH prefix
; that specifies whether the next character is an ordinal or a
; codeword/control value:
INPUT-BITS (1, index, end_of_message)
COMPARE ($index, 1, ordinal, codeword_control, codeword_control)
:prefix_after_codeword
; The following code decompresses the special LZJH prefix that only
; occurs after a codeword. It specifies whether the next character
; is an ordinal, a codeword/control value, or a string extension:
INPUT-HUFFMAN (index, end_of_message, 2, 1, 1, 1, 2, 1, 0, 1, 0)
COMPARE ($index, 1, ordinal, string_extension, codeword_control)
:ordinal
; The following code decompresses an ordinal character and creates
; a new codebook entry consisting of the ordinal character and the
; next character to be decompressed:
set (index_lsb, (index + 1))
set (current_length_lsb, (current_length + 1))
INPUT-BITS ($ordinal_length, index, !)
OUTPUT (index_lsb, 1)
LOAD (current_length, 2)
COPY-LITERAL (current_length_lsb, 3, $codebook_next)
COPY-LITERAL (index_lsb, 1, $decompressed_pointer)
JUMP (standard_prefix)
:codeword_control
; The following code decompresses a codeword/control value:
INPUT-BITS ($codeword_length, index, !)
COMPARE ($index, 3, control_code, initialize_memory, codeword)
:codeword
; The following code interprets a codeword as an index into the LZJH
; codebook. It extracts the position/length pair from the specified
; codebook entry; the position/length pair points to a byte string
; in the circular buffer, which is then copied to the end of the
; decompressed message. The code also creates a new codebook entry
; consisting of the byte string plus the next character to be
; decompressed:
set (length_value_lsb, (length_value + 1))
MULTIPLY ($index, 3)
ADD ($index, first_codeword)
COPY ($index, 3, length_value_lsb)
LOAD (current_length, 1)
ADD ($current_length, $length_value)
LOAD (codebook_old, $codebook_next)
COPY-LITERAL (current_length_lsb, 3, $codebook_next)
COPY-LITERAL ($position_value, $length_value, $decompressed_pointer)
OUTPUT ($position_value, $length_value)
JUMP (prefix_after_codeword)
:string_extension
; The following code decompresses a Huffman-encoded string extension:
INPUT-HUFFMAN (index, !, 4, 1, 1, 1, 1, 2, 1, 3, 2, 1, 1, 1, 13, 3,
0, 7, 5)
COMPARE ($index, 13, continue, extra_bits, extra_bits)
:extra_bits
INPUT-BITS (max_extension_length, extra_extension_bits, !)
ADD ($index, $extra_extension_bits)
:continue
; The following code extends the most recently created codebook entry
; by the number of bits specified in the string extension:
COPY-LITERAL ($position_value, $length_value, $position_value)
COPY-LITERAL ($position_value, $index, $decompressed_pointer)
OUTPUT ($position_value, $index)
ADD ($index, $length_value)
COPY (index_lsb, 1, $codebook_old)
JUMP (standard_prefix)
:control_code
; The code can handle all of the control characters in V.44 except
; for ETM (Enter Transparent Mode), which is not required for
; message-based protocols such as SigComp.
COMPARE ($index, 1, !, flush, stepup)
:flush
; The FLUSH control character jumps to the beginning of the next
; complete byte in the compressed message:
INPUT-BYTES (0, 0, 0)
JUMP (standard_prefix)
:stepup
; The STEPUP control character increases the number of bits used to
; encode an ordinal value or a codeword:
INPUT-BITS (1, index, !)
COMPARE ($index, 1, stepup_ordinal, stepup_codeword, 0)
:stepup_ordinal
ADD ($ordinal_length, 1)
JUMP (ordinal)
:stepup_codeword
ADD ($codeword_length, 1)
JUMP (codeword_control)
: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 LZJH algorithm is given
below:
0x5c09 e6e0 cadc c8d2 dcce 40c2 40f2 cac2 e440 c825 c840 ccde 29e8
0xc2f0 40e0 eae4 e0de e6ca e65c 1403
The uncompressed message is "...spending a year dead for tax
purposes.\n".
4.2. Adapted Algorithms
4.2.1. Modified DEFLATE
Alternative algorithms can also be used with SigComp. This section
shows a modified version of the DEFLATE [8] algorithm. The two-stage
encoding of DEFLATE is replaced by a single step with a discrete
Huffman code for each symbol. The literal/length symbol
probabilities are dependent upon whether the previous symbol was a
literal or a match. Bit handling is also simpler, in that all bits
are input using the INPUT-HUFFMAN instruction and the value of the H
bit does not change so all bits are input, read, and interpreted in
the same order.
Assembly for the algorithm is given below. String matching rules are
the same as for the other LZ-based algorithms, with the alternative
encoding of the literals and length/distance pairs.
at (32)
readonly (0)
:index pad (2)
:distance_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)
at (128)
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
:character_after_literal
INPUT-HUFFMAN (index, end_of_message, 16,
5, 0, 11, 46,
0, 12, 12, 256,
1, 26, 32, 257,
1, 66, 68, 32,
0, 69, 94, 97,
0, 95, 102, 264,
0, 103, 103, 511,
2, 416, 426, 35,
0, 427, 465, 58,
0, 466, 481, 272,
1, 964, 995, 288,
3, 7968, 7988, 123,
0, 7989, 8115, 384,
1, 16232, 16263, 0,
0, 16264, 16327, 320,
1, 32656, 32767, 144)
COMPARE ($index, 256, literal, distance, distance)
:character_after_match
INPUT-HUFFMAN (index, end_of_message, 16,
4, 0, 0, 511,
1, 2, 9, 256,
1, 20, 22, 32,
0, 23, 30, 264,
1, 62, 73, 46,
0, 74, 89, 272,
2, 360, 385, 97,
0, 386, 417, 288,
1, 836, 874, 58,
0, 875, 938, 320,
1, 1878, 1888, 35,
0, 1889, 2015, 384,
1, 4032, 4052, 123,
1, 8106, 8137, 0,
1, 16276, 16379, 144,
1, 32760, 32767, 248)
COMPARE ($index, 256, literal, distance, distance)
:literal
set (index_lsb, (index + 1))
OUTPUT (index_lsb, 1)
COPY-LITERAL (index_lsb, 1, $decompressed_pointer)
JUMP (character_after_literal)
:distance
SUBTRACT ($index, 253)
INPUT-HUFFMAN (distance_value, !, 9,
9, 0, 7, 9,
0, 8, 63, 129,
1, 128, 135, 1,
0, 136, 247, 17,
0, 248, 319, 185,
1, 640, 1407, 257,
2, 5632, 6655, 1025,
1, 13312, 15359, 2049,
2, 61440, 65535, 4097)
LOAD (old_pointer, $decompressed_pointer)
COPY-OFFSET ($distance_value, $index, $decompressed_pointer)
OUTPUT ($old_pointer, $index)
JUMP (character_after_match)
: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 modified DEFLATE
algorithm is given below:
0xd956 b132 cd68 5424 c5a9 6215 8a70 a64d af0a 5499 3621 509b 3e4c
0x28b4 a145 b362 653a d0a6 498b 5a6d 2970 ac4c 930a a4ca 74a4 c268
0x0c
The uncompressed message is "Arthur leapt to his feet like an author
hearing the phone ring".
5. Additional SigComp Mechanisms
This section covers the additional mechanisms that can be employed by
SigComp to improve the overall compression ratio, including the use
of acknowledgements, dictionaries, and sharing state between two
directions of a compressed message flow.
An example of assembly code is provided for these mechanisms.
Depending on the mechanism and basic algorithm in use, the assembly
code for either the mechanism or the basic algorithm may require
modification (e.g., if the algorithm uses ’no more input’ to jump to
end_of_message, following end_of_message with an input instruction
for CRC will not work). In any case, these are examples and there
may be alternative ways to make use of the mechanisms.
When each of the compression algorithms described in Section 4 has
successfully decompressed the current SigComp message, the contents
of the UDVM memory are saved as a SigComp state item. Subsequent
messages can access this state item by uploading the correct state
identifier to the receiving endpoint, which avoids the need to upload
the bytecode for the compression algorithm on a per-message basis.
However, before a state item can be accessed, the compressor must
first ensure that it is available at the receiving endpoint.
For each SigComp compartment, the receiving endpoint maintains a list
of currently available states (where the total amount of state saved
does not exceed the state_memory_size for the compartment). The
SigComp compressor should maintain a similar list containing the
states that it has instructed the receiving endpoint to save.
As well as tracking the list of state items that it has saved at the
remote endpoint, the compressor also maintains a flag for each state
item indicating whether or not the state can safely be accessed.
State items should not be accessed until they have been acknowledged
(e.g., by using the SigComp feedback mechanism as per Section 5.1).
State items are deleted from the list when adding a new piece of
state when the total state_memory_size for the compartment is full.
The state to be deleted is determined according to age and retention
priority as discussed in SigComp [2]. The SigComp compressor should
not attempt to access any state items that have been deleted in this
manner, as they may no longer be available at the receiving endpoint.
5.1. Acknowledging a State Item
SigComp [2] defines a feedback mechanism to allow the compressor to
request feedback from the decompressor, to give the compressor
indication that a message has been received and correctly
decompressed and that state storage has been attempted. (Note: This
mechanism cannot convey the success or failure of individual state
creation requests.) In order to invoke the feedback mechanism, the
following fields must be reserved in the UDVM memory:
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| reserved | Q | S | I | requested_feedback_location
+---+---+---+---+---+---+---+---+
| 1 | requested_feedback_length | if Q = 1
+---+---+---+---+---+---+---+---+
| |
: requested_feedback_field : if Q = 1
| |
+---+---+---+---+---+---+---+---+
These fields can be reserved in any of the algorithms of Section 4 by
replacing the line "set (requested_feedback_location, 0)" with the
following assembly:
:requested_feedback_location pad (1)
:requested_feedback_length pad (1)
:requested_feedback_field pad (12)
:hash_start pad (8)
When a SigComp message is successfully decompressed and saved as
state, the following bytecode instructs the receiving endpoint to
return the first 6 bytes of the corresponding state identifier. The
bytecode can be added to any of the compression algorithms of Section
4 immediately following the ":end_of_message" label:
:end_of_message
set (hash_length, (state_length + 8))
LOAD (requested_feedback_location, 1158)
MULTILOAD (hash_start, 4, state_length, 64,
decompress_sigcomp_message, 6)
SHA-1 (hash_start, hash_length, requested_feedback_field)
The receiving endpoint then returns the state identifier in the
"returned feedback field" of the next SigComp message to be
transmitted in the reverse direction.
When the state identifier is returned, the compressor can set the
availability flag for the corresponding state to 1.
5.2. Static Dictionary
Certain protocols that can be compressed using SigComp offer a fixed,
mandatory state item known as a static dictionary. This dictionary
contains a number of text strings that commonly occur in messages
generated by the protocol in question. The overall compression ratio
can often be improved by accessing the text phrases from this static
dictionary rather than by uploading them as part of the compressed
message.
As an example, a static dictionary is provided for the protocols SIP
and SDP, RFC 3485 [4]. This dictionary is designed for use by a wide
range of compression algorithms including all of the ones covered in
Section 4.
In any of the compression algorithms of Section 4, the static
dictionary can be accessed by inserting the following instruction
immediately after the ":initialize_memory" label:
STATE-ACCESS (dictionary_id, 6, 0, 0, 1024, 0)
The parameters of STATE-ACCESS instruction will depend on the
compression algorithm in use.
The following lines should also be inserted immediately after the
END-MESSAGE instruction:
:dictionary_id
byte (0xfb, 0xe5, 0x07, 0xdf, 0xe5, 0xe6)
The text strings contained in the static dictionary can then be
accessed in exactly the same manner as the text strings from
previously decompressed messages (see Section 5.1 for further
details).
Note that in some cases it is sufficient to load only part of the
static dictionary into the UDVM memory. Further information on the
contents of the SIP and SDP static dictionary can be found in the
relevant document, RFC 3485 [4].
5.3. CRC Checksum
The acknowledgement scheme of Section 5.1 is designed to indicate the
successful decompression of a message. However, it does not
guarantee that the decompressed message is identical to the original
message, since decompression of a corrupted message could succeed but
with some characters being incorrect. This could lead to an
incorrect message being passed to the application or unexpected
contents of state to be stored. In order to prevent this happening,
a CRC check could be used.
If an additional CRC check is required, then the following bytecode
can be inserted after the ":end_of_message" label:
INPUT-BYTES (2, index, !)
CRC ($index, 64, state_length, !)
The bytecode extracts a 2-byte CRC from the end of the SigComp
message and compares it with a CRC calculated over the UDVM memory.
Decompression failure occurs if the two CRC values do not match.
A definition of the CRC polynomial used by the CRC instruction can be
found in SigComp [2].
5.4. Announcing Additional Resources
If a particular endpoint is able to offer more processing or memory
resources than the mandatory minimum, the SigComp feedback mechanism
can be used to announce that these resources are available to the
remote endpoint. This may help to improve the overall compression
ratio between the two endpoints.
Additionally, if an endpoint has any pieces of state that may be
useful for the remote endpoint to reference, it can advertise the
identifiers for the states. The remote endpoint can then make use of
any that it also knows about (i.e., knows the contents of), for
example, a dictionary or shared mode state (see Section 5.5).
The values of the following SigComp parameters can be announced using
the SigComp advertisement mechanism:
cycles_per_bit
decompression_memory_size
state_memory_size
SigComp_version
state identifiers
As explained in SigComp, in order to announce the values of these
parameters, the following fields must be reserved in the UDVM memory:
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| cpb | dms | sms | returned_parameters_location
+---+---+---+---+---+---+---+---+
| SigComp_version |
+---+---+---+---+---+---+---+---+
| length_of_partial_state_ID_1 |
+---+---+---+---+---+---+---+---+
| |
: partial_state_identifier_1 :
| |
+---+---+---+---+---+---+---+---+
: :
+---+---+---+---+---+---+---+---+
| length_of_partial_state_ID_n |
+---+---+---+---+---+---+---+---+
| |
: partial_state_identifier_n :
| |
+---+---+---+---+---+---+---+---+
These fields can be reserved in any of the algorithms of Section 4 by
replacing the line "set (returned_parameters_location, 0)" with the
following piece of assembly:
:adverts_len pad (1)
:adverts_len_lsb pad (1)
:returned_parameters_location pad (1)
:returned_sigcomp_version pad (1)
:state_ids pad (x)
where x is enough space for the number state identifiers that the
endpoint wishes to advertise.
When a SigComp message is successfully decompressed and saved as
state, the following bytecode announces to the receiving endpoint
that additional resources and pieces of state are available at the
sending endpoint:
:end_of_message
LOAD (returned_parameters_location, N)
INPUT-BYTES (1, adverts_len_lsb, done)
INPUT-BYTES ($adverts_len, state_ids, done)
:done
Note that the integer value "N" should be set equal to the amount of
resources available at the sending endpoint. N should be expressed
as a 2-byte integer with the most significant bits corresponding to
the cycles_per_bit parameter and the least significant bits
corresponding to the SigComp_version parameter.
The length of the state identifiers followed by the state identifiers
in the format shown are appended to the end of the compressed
message.
5.5. Shared Compression
This section provides bytecode for implementing the SigComp shared
compression mechanism, RFC 3321 [3]. If two endpoints A and B are
communicating via SigComp, shared compression allows the messages
sent from Endpoint A to Endpoint B to be compressed relative to the
messages sent from Endpoint B to Endpoint A (and vice versa). This
may improve the overall compression ratio by reducing the need to
transmit the same information in both directions.
As described in RFC 3321 [3], two steps must be taken to implement
shared compression at an endpoint.
First, it is necessary to announce to the remote endpoint that shared
compression is available. This is done by announcing the state
identifier as an available piece of state. This can be done using
the returned_parameters_location announcement as in Section 5.4.
Second, assuming that such an announcement is received from the
remote endpoint, then the state created by shared compression needs
to be accessed by the message sent in the opposite direction. This
can be done in a similar way to accessing the static dictionary (see
Section 5.2), but using the appropriate state identifier, for
example, by using the INPUT-BYTES instruction as below:
:shared_state_id pad (6)
:access_shared_state
INPUT-BYTES (6, shared_state_id, !)
STATE-ACCESS (shared_state_id, 6, 0, 0, $decompressed_start, 0)
6. Security Considerations
This document describes implementation options for the SigComp
protocol [2]. Consequently, the security considerations for this
document match those of SigComp.
7. Acknowledgements
Thanks to Richard Price, Carsten Bormann, Adam Roach, Lawrence
Conroy, Christian Schmidt, Max Riegel, Lars-Erik Jonsson, Jonathan
Rosenberg, Stefan Forsgren, Krister Svanbro, Miguel Garcia,
Christopher Clanton, Khiem Le, Ka Cheong Leung, and Zoltan Barczikay
for valuable input and review.
Special thanks to Pekka Pessi and Cristian Constantin, who served as
committed working group document reviewers.
8. Intellectual Property Right Considerations
The IETF has been notified of intellectual property rights claimed in
regard to some or all of the specification contained in this
document. For more information consult the online list of claimed
rights.
9. Normative References
[1] Crocker, D. and P. Overell, "Augmented BNF for Syntax
Specifications: ABNF", RFC 4234, October 2005.
[2] Price, R., Bormann, C., Christoffersson, J., Hannu, H., Liu,
Z., and J. Rosenberg, "Signaling Compression (SigComp)", RFC
3320, January 2003.
[3] Hannu, H., Christoffersson, J., Forsgren, S., Leung, K.-C.,
Liu, Z., and R. Price, "Signaling Compression (SigComp) -
Extended Operations", RFC 3321, January 2003.
[4] Garcia-Martin, M., Bormann, C., Ott, J., Price, R., and A.B.
Roach, "The Session Initiation Protocol (SIP) and Session
Description Protocol (SDP) Static Dictionary for Signaling
Compression (SigComp)", RFC 3485, February 2003.
[5] Ziv, J. and A. Lempel, "A universal algorithm for sequential
data compression", IEEE 23:337-343, 1977.
[6] Storer, J., "Data Compression: Methods and Theory", Computer
Science Press ISBN 0-88175-161-8, 1998.
[7] Nelson, M., "LZW Data Compression", Dr Dobb’s Journal,
October 1989.
[8] Deutsch, P., "DEFLATE Compressed Data Format Specification
version 1.3", RFC 1951, May 1996.
[9] "Data Compression Procedures", ITU-T Recommendation V.44,
November 2000.
Appendix A. UDVM Bytecode for the Compression Algorithms
The following sections list the UDVM bytecode generated for each
compression algorithm of Section 4.
Note that the different assemblers can output different bytecode for
the same piece of assembly code, so a valid assembler can produce
results different from those presented below. However, the following
bytecode should always generate the same decompressed messages on any
UDVM.
A.1. Well-known Algorithms
A.1.1. LZ77
0x0f86 0389 8d89 1588 8800 011c 0420 0d13 5051 2222 5051 16f5 2300
0x00bf c086 a08b 06
A.1.2. LZSS
0x0f86 04a0 c48d 00a0 c41e 2031 0209 00a0 ff8e 048c bfff 0117 508d
0x0f23 0622 2101 1321 0123 16e5 1d04 22e8 0611 030e 2463 1450 5123
0x2252 5116 9fd2 2300 00bf c086 a089 06
A.1.3. LZW
0x0f86 06a1 ce8d 00b1 8f01 a0ce 13a0 4903 2313 2501 2506 1201 1752
0x88f4 079f 681d 0a24 2508 1203 0612 b18f 1252 0321 0ea0 4801 0624
0x5013 a049 0323 1351 5025 2251 5016 9fde 2300 00bf c086 a09f 06
A.1.4. DEFLATE
0x0f86 7aa2 528d 05a2 5200 0300 0400 0500 0600 0700 0800 0900 0a01
0x0b01 0d01 0f01 1102 1302 1702 1b02 1f03 2303 2b03 3303 3b04 a043