draft-ietf-rohc-sigcomp-user-guide-02.txt   draft-ietf-rohc-sigcomp-user-guide-03.txt 
Robust Header Compression A. Surtees Robust Header Compression A. Surtees
Internet-Draft M. West Internet-Draft M. West
Expires: January 19, 2006 Siemens/Roke Manor Research Expires: April 1, 2006 Siemens/Roke Manor Research
July 18, 2005 September 28, 2005
SigComp Users' Guide SigComp Users' Guide
draft-ietf-rohc-sigcomp-user-guide-02.txt draft-ietf-rohc-sigcomp-user-guide-03.txt
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79. aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
skipping to change at page 1, line 34 skipping to change at page 1, line 34
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on January 19, 2006. This Internet-Draft will expire on April 1, 2006.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2005). Copyright (C) The Internet Society (2005).
Abstract Abstract
This document provides an informational guide for users of the This document provides an informational guide for users of the
SigComp protocol. The aim of the document is to assist users when SigComp protocol. The aim of the document is to assist users when
making SigComp implementation decisions; for example the choice of making SigComp implementation decisions; for example the choice of
skipping to change at page 3, line 23 skipping to change at page 3, line 23
compressed data. compressed data.
The basic SigComp RFC describes the actions that an endpoint must The basic SigComp RFC describes the actions that an endpoint must
take upon receiving a SigComp message. However the entity take upon receiving a SigComp message. However the entity
responsible for generating new SigComp messages (the SigComp responsible for generating new SigComp messages (the SigComp
compressor) is left as an implementation decision; any compressor can compressor) is left as an implementation decision; any compressor can
be used provided that it generates SigComp messages that can be be used provided that it generates SigComp messages that can be
successfully decompressed by the receiving endpoint. successfully decompressed by the receiving endpoint.
This document offers a number of different compressors that can be This document offers a number of different compressors that can be
used by the SigComp protocol. It also describes how standard stream- used by the SigComp protocol. It also gives examples of how to use
based compressors can be modified for robustness against lost and/or some of the mechanisms (such as acknowledgements) described in RFC
misordered packets over an unreliable transport such as UDP. 3321 [5].
2. Overview of the User Guide 2. Overview of the User Guide
When implementing a SigComp compressor the first step is to choose a When implementing a SigComp compressor the first step is to choose a
compression algorithm that can encode the application messages into a compression algorithm that can encode the application messages into a
(hopefully) smaller form. Since SigComp can upload bytecode for new (hopefully) smaller form. Since SigComp can upload bytecode for new
algorithms to the receiving endpoint, arbitrary compression algorithms to the receiving endpoint, arbitrary compression
algorithms can be supported provided that bytecode has been written algorithms can be supported provided that bytecode has been written
for the corresponding decompressor. for the corresponding decompressor.
This document provides bytecode for the following algorithms: This document provides example bytecode for the following algorithms:
1. Simplified LZ77 1. Simplified LZ77
2. LZSS 2. LZSS
3. LZW 3. LZW
4. DEFLATE 4. DEFLATE
5. LZJH 5. LZJH
Any of the above algorithms may be useful depending on the desired Any of the above algorithms may be useful depending on the desired
compression ratio, processing and memory requirements, code size, compression ratio, processing and memory requirements, code size,
implementation complexity and Intellectual Property (IPR) implementation complexity and Intellectual Property (IPR)
considerations. considerations.
As well as encoding the application messages using the chosen As well as encoding the application messages using the chosen
algorithm, the SigComp compressor is responsible for ensuring that algorithm, the SigComp compressor is responsible for ensuring that
messages can be correctly decompressed even if packets are lost or messages can be correctly decompressed even if packets are lost or
misordered during transmission. The SigComp feedback mechanism can misordered during transmission. The SigComp feedback mechanism can
be used to acknowledge successful decompression over an unreliable be used to acknowledge successful decompression at the remote
transport such as UDP. endpoint.
The following robustness techniques and other mechanisms specific to The following robustness techniques and other mechanisms specific to
the SigComp environment are covered in this document: the SigComp environment are covered in this document:
1. Acknowledgements using the SigComp feedback mechanism 1. Acknowledgements using the SigComp feedback mechanism
2. Static dictionary 2. Static dictionary
3. CRC checksum 3. CRC checksum
4. Announcing additional resources 4. Announcing additional resources
5. Shared compression 5. Shared compression
Any or all of the above mechanisms can be implemented in conjunction Any or all of the above mechanisms can be implemented in conjunction
skipping to change at page 5, line 6 skipping to change at page 5, line 6
On a lexical level, a string of assembly consists of zero or more On a lexical level, a string of assembly consists of zero or more
tokens optionally separated by whitespace. Each token can be a text tokens optionally separated by whitespace. Each token can be a text
name, an instruction opcode, a delimiter, or an integer (specified as name, an instruction opcode, a delimiter, or an integer (specified as
decimal, binary or hex). decimal, binary or hex).
The following ABNF description RFC-2234 [3] specifies the syntax of a The following ABNF description RFC-2234 [3] specifies the syntax of a
token: token:
token = (name / opcode / delimiter / dec / bin / hex) token = (name / opcode / delimiter / dec / bin / hex)
name = (lowercase / "_") 1*(lowercase / digit / "_") name = (lowercase / "_") 0*(lowercase / digit / "_")
opcode = uppercase *(uppercase / digit / "-") opcode = uppercase *(uppercase / digit / "-")
delimiter = "." / "," / "!" / "$" / ":" / "(" / ")" / delimiter = "." / "," / "!" / "$" / ":" / "(" / ")" /
operator operator
dec = 1*(digit) dec = 1*(digit)
bin = "0b" 1*("0" / "1") bin = "0b" 1*("0" / "1")
hex = "0x" 1*(hex_digit) hex = "0x" 1*(hex_digit)
hex_digit = digit / %x41-46 / %x61-66 hex_digit = digit / %x41-46 / %x61-66
digit = %x30-39 digit = %x30-39
uppercase = %x41-5a uppercase = %x41-5a
lowercase = %x61-7a lowercase = %x61-7a
skipping to change at page 6, line 28 skipping to change at page 6, line 28
; that specifies the total number of ; that specifies the total number of
; operands for the instruction. ; operands for the instruction.
; When "$" is prepended to an operand, ; When "$" is prepended to an operand,
; the corresponding integer is an ; the corresponding integer is an
; address rather than the actual operand ; address rather than the actual operand
; value. This symbol is mandatory for ; value. This symbol is mandatory for
; reference operands, optional for ; reference operands, optional for
; multitypes and addresses, and ; multitypes and addresses, and
; disallowed for literals. ; disallowed for literals.
label = ":" name label = ":" name
directive = padding / data / set / readonly directive = padding / data / set / readonly /
; note that directive names are unknown_directive
; syntactically of category <name>; all unknown_directive = name ["(" expression *("," expression) ")"]
; directives are intended to syntactically ; The parser can ignore unknown
; match: name ["(" expression *("," ; directives. The resulting bytecode
; expression) ")"] ; may or may not generate the expected
; results.
padding = ("pad" / "align" / "at") "(" expression ")" padding = ("pad" / "align" / "at") "(" expression ")"
data = ("byte" / "word") "(" expression *("," data = ("byte" / "word") "(" expression *(","
expression) ")" expression) ")"
readonly = "readonly" "(" "0" / "1" ")" readonly = "readonly" "(" "0" / "1" ")"
set = "set" "(" name "," expression ")" set = "set" "(" name "," expression ")"
expression = value / "(" expression operator expression ")" expression = value / "(" expression operator expression ")"
value = dec / bin / hex / name / "." / "!" value = dec / bin / hex / name / "." / "!"
; "." is the location of this ; "." is the location of this
; instruction/directive, whereas "!" is ; instruction/directive, whereas "!" is
; the location of the closest ; the location of the closest
skipping to change at page 7, line 47 skipping to change at page 7, line 47
decompression failure, for example: decompression failure, for example:
INPUT-BYTES (1, temp, !) INPUT-BYTES (1, temp, !)
The above instruction causes a decompression failure to occur if it The above instruction causes a decompression failure to occur if it
tries to input data from beyond the end of the compressed message. tries to input data from beyond the end of the compressed message.
N.B. When using "!" in the assembly language to generate bytecode, N.B. When using "!" in the assembly language to generate bytecode,
care must be taken to ensure that the address of the zero used at care must be taken to ensure that the address of the zero used at
bytecode generation time will still contain zero when the bytecode is bytecode generation time will still contain zero when the bytecode is
run. run. The readonly directive (see Section 3.2.3) can be used to do
this.
It is also possible to assign integer values to text names: when a It is also possible to assign integer values to text names: when a
text name is encountered in an expression it is replaced by the text name is encountered in an expression it is replaced by the
integer value assigned to it. Section 3.2.3 explains how to assign integer value assigned to it. Section 3.2.3 explains how to assign
integer values to text names. integer values to text names.
3.2.2 Instructions 3.2.2 Instructions
A UDVM instruction is specified by the instruction opcode followed by A UDVM instruction is specified by the instruction opcode followed by
zero or more operands. The instruction operands are enclosed in zero or more operands. The instruction operands are enclosed in
parentheses and separated by commas, for example: parentheses and separated by commas, for example:
ADD (3, 4) ADD (3, 4)
When generating the bytecode the parser should replace the When generating the bytecode the parser should replace the
instruction opcode with the corresponding 1-byte value as per Figure instruction opcode with the corresponding 1-byte value as per Figure
11 of SigComp RFC-3320 [4]. 11 of SigComp [4].
Each operand consists of an expression which evaluates to an integer, Each operand consists of an expression which evaluates to an integer,
optionally preceded by the symbol "$". This symbol indicates that optionally preceded by the symbol "$". This symbol indicates that
the supplied integer value must be interpreted as the memory address the supplied integer value must be interpreted as the memory address
at which the operand value can be found, rather than the actual at which the operand value can be found, rather than the actual
operand value itself. operand value itself.
When converting each instruction operand to bytecode, the parser When converting each instruction operand to bytecode, the parser
first determines whether the instruction expects the operand to be a first determines whether the instruction expects the operand to be a
literal, a reference, a multitype or an address. If the operand is a literal, a reference, a multitype or an address. If the operand is a
literal then as per Figure 8 of SigComp, the parser inserts the literal then as per Figure 8 of SigComp, the parser inserts bytecode
shortest bytecode capable of encoding the supplied operand value. (usually the shortest) capable of encoding the supplied operand
value.
Since literal operands are used to indicate the total number of Since literal operands are used to indicate the total number of
operands for an instruction, it is possible to leave a literal operands for an instruction, it is possible to leave a literal
operand blank and allow its value to be inferred automatically by the operand blank and allow its value to be inferred automatically by the
assembler. For example: assembler. For example:
MULTILOAD (64, , 1, 2, 3, 4) MULTILOAD (64, , 1, 2, 3, 4)
The missing operand should be given the value 4 because it is The missing operand should be given the value 4 because it is
followed by a total of 4 operands. followed by a total of 4 operands.
If the operand is a reference then as per Figure 9 of SigComp, the If the operand is a reference then as per Figure 9 of SigComp, the
parser inserts the shortest bytecode capable of encoding the supplied parser inserts bytecode (ususally the shortest) capable of encoding
memory address. Note that reference operands will always be preceded the supplied memory address. Note that reference operands will
by the symbol "$" in assembly because they always encode memory always be preceded by the symbol "$" in assembly because they always
addresses rather than actual operand values. encode memory addresses rather than actual operand values.
If the operand is a multitype then the parser first checks whether If the operand is a multitype then the parser first checks whether
the symbol "$" is present. If so then, as per Figure 10 of SigComp, the symbol "$" is present. If so then, as per Figure 10 of SigComp,
it inserts the shortest bytecode capable of encoding the supplied it inserts bytecode (usually the shortest) capable of encoding the
integer as a memory address. If not then, as per Figure 10 of supplied integer as a memory address. If not then, as per Figure 10
SigComp, it inserts the shortest bytecode that encodes the supplied of SigComp, it inserts bytecode (usually the shortest) that encodes
integer as an operand value. the supplied integer as an operand value.
If the operand is an address then the parser checks whether the If the operand is an address then the parser checks whether the
symbol "$" is present. If so then the supplied integer is encoded as symbol "$" is present. If so then the supplied integer is encoded as
a memory address, just as for the multitype instruction above. If a memory address, just as for the multitype instruction above. If
not then the byte position of the opcode is subtracted from the not then the byte position of the opcode is subtracted from the
supplied integer modulo 16, and the result is encoded as an operand supplied integer modulo 16, and the result is encoded as an operand
value as per Figure 10 of SigComp. value as per Figure 10 of SigComp.
The length of the resulting bytecode is dependent on the parser in
use. There can be several correct and useable representations of the
same instruction.
3.2.3 Directives 3.2.3 Directives
The assembly language provides a number of directives for evaluating The assembly language provides a number of directives for evaluating
expressions, moving instructions to a particular memory address etc. expressions, moving instructions to a particular memory address etc.
The directives "pad", "align" and "at" can be used to add padding to The directives "pad", "align" and "at" can be used to add padding to
the bytecode. the bytecode.
The directive "pad (n)" appends n consecutive padding bytes to the The directive "pad (n)" appends n consecutive padding bytes to the
bytecode. The actual value of the padding bytes is unimportant, so bytecode. The actual value of the padding bytes is unimportant, so
skipping to change at page 10, line 6 skipping to change at page 10, line 13
which evaluate to give integers n[0],..., n[k-1] from 0 to 65535. which evaluate to give integers n[0],..., n[k-1] from 0 to 65535.
The directive "set (name, n)" assigns an integer value n to a The directive "set (name, n)" assigns an integer value n to a
specified text name. The integer value can be supplied in the form specified text name. The integer value can be supplied in the form
of an expression. of an expression.
The directive "readonly (n)" where n is 0 or 1 can be used to The directive "readonly (n)" where n is 0 or 1 can be used to
indicate that an area of memory could be changed (0) or will not be indicate that an area of memory could be changed (0) or will not be
changed (1) during the execution of the UDVM. This directive could changed (1) during the execution of the UDVM. This directive could
be used, for example, in conjunction with "!" to ensure that the be used, for example, in conjunction with "!" to ensure that the
address of the nearest zero will still contain zero when the bytecode address of the zero used will still contain zero when the bytecode is
is executed. executed. If no readonly directive is used, then any address
containing zero can be used by "!" (i.e. by default there is assumed
to be readonly(1) directive at address 0) and it is up to the author
of the assembly code to ensure that the address in question will
still contain zero when the bytecode is executed. If the readonly
directive is used, then bytes between a readonly (0) and readonly (1)
pair are NOT to be used by "!". When a readonly directive has been
used, the bytes obey that directive from that address to either
another readonly directive or the end of UDVM memory, whichever comes
first.
3.2.4 Labels 3.2.4 Labels
A label is a special directive used to assign memory addresses to A label is a special directive used to assign memory addresses to
text names. text names.
Labels are specified by giving a single colon followed by the text Labels are specified by giving a single colon followed by the text
name to be defined. The (absolute) position of the byte immediately name to be defined. The (absolute) position of the byte immediately
following the label is evaluated and assigned to the text name. For following the label is evaluated and assigned to the text name. For
example: example:
skipping to change at page 12, line 12 skipping to change at page 12, line 18
The "uploaded UDVM bytecode" should be set to contain the segment of The "uploaded UDVM bytecode" should be set to contain the segment of
bytecode that lies between Address (destination) and Address bytecode that lies between Address (destination) and Address
(destination + code_len - 1) inclusive. (destination + code_len - 1) inclusive.
4. Compression algorithms 4. Compression algorithms
This chapter describes a number of compression algorithms that can be This chapter describes a number of compression algorithms that can be
used by a SigComp compressor. In each case the document provides used by a SigComp compressor. In each case the document provides
UDVM bytecode for the corresponding decompression algorithm, which UDVM bytecode for the corresponding decompression algorithm, which
can be uploaded to the receiving endpoint as part of a SigComp can be uploaded to the receiving endpoint as part of a SigComp
message. message. Each algorithm (as written in this chapter) assumes that
there is 16K decompression memory size, 16 cycles per bit and 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 Section 4.1.1 covers a simple algorithm in some detail, including the
steps required to compress and decompress a SigComp message. The steps required to compress and decompress a SigComp message. The
remaining sections cover well-known compression algorithms that can remaining sections cover well-known compression algorithms that can
be adapted for use in SigComp with minimal modification. be adapted for use in SigComp with minimal modification.
4.1 Well-known Compression Algorithms 4.1 Well-known Compression Algorithms
4.1.1 Simplified LZ77 4.1.1 Simplified LZ77
skipping to change at page 13, line 31 skipping to change at page 13, line 40
The compression ratio of LZ77 is improved by the remaining UDVM The compression ratio of LZ77 is improved by the remaining UDVM
memory, which is used to store a history buffer containing the memory, which is used to store a history buffer containing the
previously decompressed messages. Compressed characters can point to previously decompressed messages. Compressed characters can point to
strings that have previously been decompressed and stored in the strings that have previously been decompressed and stored in the
buffer; so the overall compression ratio of the LZ77 algorithm buffer; so the overall compression ratio of the LZ77 algorithm
improves as the decompressor "learns" more text strings and is able improves as the decompressor "learns" more text strings and is able
to encode longer strings using a single compressed character. The to encode longer strings using a single compressed character. The
buffer is circular, so older messages are overwritten by new data buffer is circular, so older messages are overwritten by new data
when the buffer becomes full. when the buffer becomes full.
Note that the actual size of this circular buffer depends on the
total amount of memory available to the UDVM. The minimum size of
the UDVM memory is 1K, so the circular buffer will always contain at
least 512 bytes.
The steps required to implement an LZ77 compressor and decompressor The steps required to implement an LZ77 compressor and decompressor
are similar, although compression is more processor-intensive as it are similar, although compression is more processor-intensive as it
requires a searching operation to be performed. Assembly for the requires a searching operation to be performed. Assembly for the
simplified LZ77 decompressor is given below: simplified LZ77 decompressor is given below:
; Variables that do not need to be stored after decompressing each ; Variables that do not need to be stored after decompressing each
; SigComp message are stored here: ; SigComp message are stored here:
at (32) at (32)
:index pad (2) :index pad (2)
:length_value pad (2) :length_value pad (2)
at (42) at (42)
set (requested_feedback_location, 0) set (requested_feedback_location, 0)
; The UDVM registers must be stored beginning at Address 64: ; The UDVM registers must be stored beginning at Address 64:
at (64) at (64)
; Variables that should be stored after decompressing a message are ; Variables that should be stored after decompressing a message are
; stored here. These variables will form part of the SigComp state ; stored here. These variables will form part of the SigComp state
; item created by the bytecode: ; item created by the bytecode:
skipping to change at page 16, line 32 skipping to change at page 16, line 37
| | | |
: partial state identifier : : partial state identifier :
| | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | |
: remaining SigComp message : : remaining SigComp message :
| | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
The partial_state_identifier field must contain the first 6 bytes of The partial_state_identifier field must contain the first 6 bytes of
the state identifier for the state item to be accessed (see [RFC- the state identifier for the state item to be accessed (see [4] for
3320] for details of how state identifiers are derived). details of how state identifiers are derived).
4.1.2 LZSS 4.1.2 LZSS
This section provides UDVM bytecode for the simple but effective LZSS This section provides UDVM bytecode for the simple but effective LZSS
compression algorithm [8]. compression algorithm [8].
The principal improvement offered by LZSS over LZ77 is that each The principal improvement offered by LZSS over LZ77 is that each
compressed character begins with a 1-bit indicator flag to specify compressed character begins with a 1-bit indicator flag to specify
whether the character is a literal or an offset/length pair. A whether the character is a literal or an offset/length pair. A
literal value is simply a single uncompressed byte that is appended literal value is simply a single uncompressed byte that is appended
skipping to change at page 17, line 4 skipping to change at page 17, line 9
The principal improvement offered by LZSS over LZ77 is that each The principal improvement offered by LZSS over LZ77 is that each
compressed character begins with a 1-bit indicator flag to specify compressed character begins with a 1-bit indicator flag to specify
whether the character is a literal or an offset/length pair. A whether the character is a literal or an offset/length pair. A
literal value is simply a single uncompressed byte that is appended literal value is simply a single uncompressed byte that is appended
directly to the decompressed message. directly to the decompressed message.
An offset/length pair contains a 12-bit offset value from 1 to 4096 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. inclusive, followed by a 4-bit length value from 3 to 18 inclusive.
Taken together these values specify one of the previously received Taken together these values specify one of the previously received
text strings in the circular buffer, which is then appended to the text strings in the circular buffer, which is then appended to the
end of the decompressed message. end of the decompressed message.
Assembly for an LZSS decompressor is given below: Assembly for an LZSS decompressor is given below:
at (32) at (32)
readonly (0)
:index pad (2) :index pad (2)
:length_value pad (2) :length_value pad (2)
:old_pointer pad (2) :old_pointer pad (2)
at (42) at (42)
set (requested_feedback_location, 0) set (requested_feedback_location, 0)
at (64) at (64)
:byte_copy_left pad (2) :byte_copy_left pad (2)
:byte_copy_right pad (2) :byte_copy_right pad (2)
:input_bit_order pad (2) :input_bit_order pad (2)
:decompressed_pointer pad (2) :decompressed_pointer pad (2)
set (returned_parameters_location, 0) set (returned_parameters_location, 0)
align (64) align (64)
readonly (1)
:initialize_memory :initialize_memory
set (udvm_memory_size, 8192) set (udvm_memory_size, 8192)
set (state_length, (udvm_memory_size - 64)) set (state_length, (udvm_memory_size - 64))
MULTILOAD (64, 4, circular_buffer, udvm_memory_size, 0, MULTILOAD (64, 4, circular_buffer, udvm_memory_size, 0,
circular_buffer) circular_buffer)
:decompress_sigcomp_message :decompress_sigcomp_message
skipping to change at page 18, line 22 skipping to change at page 18, line 30
COPY-OFFSET ($index, $length_value, $decompressed_pointer) COPY-OFFSET ($index, $length_value, $decompressed_pointer)
OUTPUT ($old_pointer, $length_value) OUTPUT ($old_pointer, $length_value)
JUMP (next_character) JUMP (next_character)
:end_of_message :end_of_message
END-MESSAGE (requested_feedback_location, END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64, returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0) decompress_sigcomp_message, 6, 0)
readonly (0)
:circular_buffer :circular_buffer
An example message compressed using the LZSS algorithm is given An example message compressed using the LZSS algorithm is given
below: below:
0x279a 0406 e378 b200 6074 1018 4ce6 1349 b842 0x279a 0406 e378 b200 6074 1018 4ce6 1349 b842
The uncompressed message is "Oh no, not again!". The uncompressed message is "Oh no, not again!".
4.1.3 LZW 4.1.3 LZW
skipping to change at page 21, line 29 skipping to change at page 21, line 36
data by transmitting 7 consecutive zero bits. Each SigComp data by transmitting 7 consecutive zero bits. Each SigComp
message is assumed to contain a separate block of compressed 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 data, so the end-of-block bits are implicit and do not need to be
transmitted at the end of a SigComp message. transmitted at the end of a SigComp message.
2. This bytecode supports only DEFLATE block type 01 (data 2. This bytecode supports only DEFLATE block type 01 (data
compressed with fixed Huffman codes). compressed with fixed Huffman codes).
Assembly for the DEFLATE decompressor is given below: Assembly for the DEFLATE decompressor is given below:
at (32) at (32)
readonly (0)
:index pad (2) :index pad (2)
:extra_length_bits pad (2) :extra_length_bits pad (2)
:length_value pad (2) :length_value pad (2)
:extra_distance_bits pad (2) :extra_distance_bits pad (2)
:distance_value pad (2) :distance_value pad (2)
at (42) at (42)
set (requested_feedback_location, 0) set (requested_feedback_location, 0)
skipping to change at page 21, line 41 skipping to change at page 22, line 4
:extra_length_bits pad (2) :extra_length_bits pad (2)
:length_value pad (2) :length_value pad (2)
:extra_distance_bits pad (2) :extra_distance_bits pad (2)
:distance_value pad (2) :distance_value pad (2)
at (42) at (42)
set (requested_feedback_location, 0) set (requested_feedback_location, 0)
at (64) at (64)
:byte_copy_left pad (2) :byte_copy_left pad (2)
:byte_copy_right pad (2) :byte_copy_right pad (2)
:input_bit_order pad (2) :input_bit_order pad (2)
:decompressed_pointer pad (2) :decompressed_pointer pad (2)
:length_table pad (116) :length_table pad (116)
:distance_table pad (120) :distance_table pad (120)
set (returned_parameters_location, 0) set (returned_parameters_location, 0)
align (64) align (64)
readonly (1)
:initialize_memory :initialize_memory
set (udvm_memory_size, 8192) set (udvm_memory_size, 8192)
set (state_length, (udvm_memory_size - 64)) set (state_length, (udvm_memory_size - 64))
set (length_table_start, (((length_table - 4) + 65536) / 4)) set (length_table_start, (((length_table - 4) + 65536) / 4))
set (length_table_mid, (length_table_start + 24)) set (length_table_mid, (length_table_start + 24))
set (distance_table_start, (distance_table / 4)) set (distance_table_start, (distance_table / 4))
MULTILOAD (64, 122, circular_buffer, udvm_memory_size, 5, MULTILOAD (64, 122, circular_buffer, udvm_memory_size, 5,
circular_buffer, circular_buffer,
skipping to change at page 23, line 39 skipping to change at page 24, line 4
LOAD (index, $decompressed_pointer) LOAD (index, $decompressed_pointer)
COPY-OFFSET ($distance_value, $length_value, $decompressed_pointer) COPY-OFFSET ($distance_value, $length_value, $decompressed_pointer)
OUTPUT ($index, $length_value) OUTPUT ($index, $length_value)
JUMP (next_character) JUMP (next_character)
:end_of_message :end_of_message
END-MESSAGE (requested_feedback_location, END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64, returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0) decompress_sigcomp_message, 6, 0)
readonly (0)
:circular_buffer :circular_buffer
An example message compressed using the DEFLATE algorithm is given An example message compressed using the DEFLATE algorithm is given
below: below:
0xf3c9 4c4b d551 28c9 4855 08cd cb2c 4b2d 2a4e 5548 cc4b 5170 0532 0xf3c9 4c4b d551 28c9 4855 08cd cb2c 4b2d 2a4e 5548 cc4b 5170 0532
0x2b4b 3232 f3d2 b900 0x2b4b 3232 f3d2 b900
The uncompressed message is "Life, the Universe and Everything\n". The uncompressed message is "Life, the Universe and Everything\n".
4.1.5 LZJH 4.1.5 LZJH
This section provides UDVM bytecode for the LZJH compression This section provides UDVM bytecode for the LZJH compression
algorithm. LZJH is the algorithm adopted by the International algorithm. LZJH is the algorithm adopted by the International
Telecommunication Union (ITU-T) Recommendation V.44 LZJH [11]. Telecommunication Union (ITU-T) Recommendation V.44 LZJH [11].
Assembly for the LZJH decompressor is given below: Assembly for the LZJH decompressor is given below:
at (32) at (32)
readonly (0)
; The following 2-byte variables are stored in the scratch-pad memory ; The following 2-byte variables are stored in the scratch-pad memory
; area because they do not need to be saved after decompressing a ; area because they do not need to be saved after decompressing a
; SigComp message: ; SigComp message:
:length_value pad (2) :length_value pad (2)
:position_value pad (2) :position_value pad (2)
:index pad (2) :index pad (2)
:extra_extension_bits pad (2) :extra_extension_bits pad (2)
:codebook_old pad (2) :codebook_old pad (2)
skipping to change at page 24, line 50 skipping to change at page 25, line 15
:current_length pad (2) :current_length pad (2)
:decompressed_pointer pad (2) :decompressed_pointer pad (2)
:ordinal_length pad (2) :ordinal_length pad (2)
:codeword_length pad (2) :codeword_length pad (2)
:codebook_next pad (2) :codebook_next pad (2)
set (returned_parameters_location, 0) set (returned_parameters_location, 0)
align (64) align (64)
readonly (1)
:initialize_memory :initialize_memory
; The following constants can be adjusted to configure the LZJH ; The following constants can be adjusted to configure the LZJH
; decompressor. The current settings are as recommended in the V.44 ; decompressor. The current settings are as recommended in the V.44
; specification (given that a total of 8K UDVM memory is available): ; specification (given that a total of 8K UDVM memory is available):
set (udvm_memory_size, 8192) ; sets the total memory for LZJH set (udvm_memory_size, 8192) ; sets the total memory for LZJH
set (max_extension_length, 8) ; sets the maximum string extension set (max_extension_length, 8) ; sets the maximum string extension
set (min_ordinal_length, 7) ; sets the minimum ordinal length set (min_ordinal_length, 7) ; sets the minimum ordinal length
set (min_codeword_length, 6) ; sets the minimum codeword length set (min_codeword_length, 6) ; sets the minimum codeword length
set (codebook_start, 4492) set (codebook_start, 4492)
skipping to change at page 28, line 4 skipping to change at page 28, line 15
ADD ($ordinal_length, 1) ADD ($ordinal_length, 1)
JUMP (ordinal) JUMP (ordinal)
:stepup_codeword :stepup_codeword
ADD ($codeword_length, 1) ADD ($codeword_length, 1)
JUMP (codeword_control) JUMP (codeword_control)
:end_of_message :end_of_message
END-MESSAGE (requested_feedback_location, END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64, returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0) decompress_sigcomp_message, 6, 0)
readonly (0)
:circular_buffer :circular_buffer
An example message compressed using the LZJH algorithm is given An example message compressed using the LZJH algorithm is given
below: below:
0x5c09 e6e0 cadc c8d2 dcce 40c2 40f2 cac2 e440 c825 c840 ccde 29e8 0x5c09 e6e0 cadc c8d2 dcce 40c2 40f2 cac2 e440 c825 c840 ccde 29e8
0xc2f0 40e0 eae4 e0de e6ca e65c 1403 0xc2f0 40e0 eae4 e0de e6ca e65c 1403
The uncompressed message is "...spending a year dead for tax The uncompressed message is "...spending a year dead for tax
purposes.\n". purposes.\n".
skipping to change at page 28, line 38 skipping to change at page 29, line 6
literal or a match. Bit-handling is also simpler, in that all bits 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 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 bit does not change so all bits are input, read and interpreted in
the same order. the same order.
Assembly for the algorithm is given below. String matching rules are Assembly for the algorithm is given below. String matching rules are
the same as for the other LZ-based algorithms, with the alternative the same as for the other LZ-based algorithms, with the alternative
encoding of the literals and length/distance pairs. encoding of the literals and length/distance pairs.
at (32) at (32)
readonly (0)
:index pad (2) :index pad (2)
:distance_value pad (2) :distance_value pad (2)
:old_pointer pad (2) :old_pointer pad (2)
at (42) at (42)
set (requested_feedback_location, 0) set (requested_feedback_location, 0)
at (64) at (64)
skipping to change at page 29, line 4 skipping to change at page 29, line 17
:index pad (2) :index pad (2)
:distance_value pad (2) :distance_value pad (2)
:old_pointer pad (2) :old_pointer pad (2)
at (42) at (42)
set (requested_feedback_location, 0) set (requested_feedback_location, 0)
at (64) at (64)
:byte_copy_left pad (2) :byte_copy_left pad (2)
:byte_copy_right pad (2) :byte_copy_right pad (2)
:input_bit_order pad (2) :input_bit_order pad (2)
:decompressed_pointer pad (2) :decompressed_pointer pad (2)
set (returned_parameters_location, 0) set (returned_parameters_location, 0)
at (128) at (128)
readonly (1)
:initialize_memory :initialize_memory
set (udvm_memory_size, 8192) set (udvm_memory_size, 8192)
set (state_length, (udvm_memory_size - 64)) set (state_length, (udvm_memory_size - 64))
MULTILOAD (64, 4, circular_buffer, udvm_memory_size, 0, MULTILOAD (64, 4, circular_buffer, udvm_memory_size, 0,
circular_buffer) circular_buffer)
:decompress_sigcomp_message :decompress_sigcomp_message
skipping to change at page 31, line 4 skipping to change at page 31, line 17
LOAD (old_pointer, $decompressed_pointer) LOAD (old_pointer, $decompressed_pointer)
COPY-OFFSET ($distance_value, $index, $decompressed_pointer) COPY-OFFSET ($distance_value, $index, $decompressed_pointer)
OUTPUT ($old_pointer, $index) OUTPUT ($old_pointer, $index)
JUMP (character_after_match) JUMP (character_after_match)
:end_of_message :end_of_message
END-MESSAGE (requested_feedback_location, END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64, returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0) decompress_sigcomp_message, 6, 0)
readonly (0)
:circular_buffer :circular_buffer
An example message compressed using the modified DEFLATE algorithm is An example message compressed using the modified DEFLATE algorithm is
given below: given below:
0xd956 b132 cd68 5424 c5a9 6215 8a70 a64d af0a 5499 3621 509b 3e4c 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 0x28b4 a145 b362 653a d0a6 498b 5a6d 2970 ac4c 930a a4ca 74a4 c268
0x0c 0x0c
The uncompressed message is "Arthur leapt to his feet like an author The uncompressed message is "Arthur leapt to his feet like an author
hearing the phone ring". hearing the phone ring".
5. Additional SigComp mechanisms 5. Additional SigComp mechanisms
The following chapter covers the additional mechanisms that can be The following chapter covers the additional mechanisms that can be
employed by SigComp to improve the overall compression ratio; employed by SigComp to improve the overall compression ratio;
including the acknowledgment of SigComp state over an unreliable including the use of acknowledgements, dictionaries and sharing state
link, sharing state between two directions of a compressed message between two directions of a compressed message flow.
flow etc.
When each of the compression algorithms described in Chapter 4 has When each of the compression algorithms described in Chapter 4 has
successfully decompressed the current SigComp message, the contents successfully decompressed the current SigComp message, the contents
of the UDVM memory are saved as a SigComp state item. Subsequent of the UDVM memory are saved as a SigComp state item. Subsequent
messages can access this state item by uploading the correct state messages can access this state item by uploading the correct state
identifier to the receiving endpoint, which avoids the need to upload identifier to the receiving endpoint, which avoids the need to upload
the bytecode for the compression algorithm on a per-message basis. the bytecode for the compression algorithm on a per-message basis.
However, before a state item can be accessed the compressor must However, before a state item can be accessed the compressor must
first ensure that it is available at the receiving endpoint. first ensure that it is available at the receiving endpoint.
skipping to change at page 32, line 7 skipping to change at page 32, line 20
(e.g. by using the SigComp feedback mechanism as per Section 5.1). (e.g. by using the SigComp feedback mechanism as per Section 5.1).
State items are deleted from the list when the total State items are deleted from the list when the total
state_memory_size for the compartment is used up by states of a state_memory_size for the compartment is used up by states of a
higher priority. The SigComp compressor should not attempt to access higher priority. The SigComp compressor should not attempt to access
any state items that have been deleted in this manner, as they may no any state items that have been deleted in this manner, as they may no
longer be available at the receiving endpoint. longer be available at the receiving endpoint.
5.1 Acknowledging a state item 5.1 Acknowledging a state item
The simplest method for acknowledging a SigComp state item is to SigComp [4] defines a feedback mechanism to allow the compressor to
employ a reliable transport layer such as TCP or SCTP. request feedback from the decompressor, to give the compressor
Alternatively, over an unreliable transport such as UDP the SigComp indication that a message has been received, correctly decompressed
feedback mechanism can be used to acknowledge that a state item has and state storage attempted. (Note, this mechanism cannot convey the
been successfully created at the receiving endpoint. success or failure of individual state creation requests.) In order
to invoke the feedback mechanism the following fields must be
As explained in SigComp RFC-3320 [4], in order to invoke the feedback reserved in the UDVM memory:
mechanism the following fields must be reserved in the UDVM memory:
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| reserved | Q | S | I | requested_feedback_location | reserved | Q | S | I | requested_feedback_location
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| 1 | requested_feedback_length | if Q = 1 | 1 | requested_feedback_length | if Q = 1
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | |
: requested_feedback_field : if Q = 1 : requested_feedback_field : if Q = 1
| | | |
skipping to change at page 34, line 34 skipping to change at page 34, line 40
can be inserted after the ":end_of_message" label: can be inserted after the ":end_of_message" label:
INPUT-BYTES (2, index, !) INPUT-BYTES (2, index, !)
CRC ($index, 64, state_length, !) CRC ($index, 64, state_length, !)
The bytecode extracts a 2-byte CRC from the end of the SigComp 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. message and compares it with a CRC calculated over the UDVM memory.
Decompression failure occurs if the two CRC values do not match. Decompression failure occurs if the two CRC values do not match.
A definition of the CRC polynomial used by the CRC instruction can be A definition of the CRC polynomial used by the CRC instruction can be
found in SigComp RFC-3320 [4]. found in SigComp [4].
5.4 Announcing additional resources 5.4 Announcing additional resources
If a particular endpoint is able to offer more processing or memory If a particular endpoint is able to offer more processing or memory
resources than the mandatory minimum, the SigComp feedback mechanism resources than the mandatory minimum, the SigComp feedback mechanism
can be used to announce that these resources are available to the can be used to announce that these resources are available to the
remote endpoint. This may help to improve the overall compression remote endpoint. This may help to improve the overall compression
ratio between the two endpoints. ratio between the two endpoints.
Additionally, if an endpoint has any pieces of state that may be Additionally, if an endpoint has any pieces of state that may be
useful for the remote endpoing to reference, it can advertise the useful for the remote endpoint to reference, it can advertise the
identifiers for the states. The remote endpoint can then make use of identifiers for the states. The remote endpoint can then make use of
any that it also knows about (i.e. knows the contents of) e.g. a any that it also knows about (i.e. knows the contents of) e.g. a
dictionary or shared mode state (see Section 5.5). dictionary or shared mode state (see Section 5.5).
The values of the following SigComp parameters can be announced using The values of the following SigComp parameters can be announced using
the SigComp advertisement mechanism: the SigComp advertisement mechanism:
cycles_per_bit cycles_per_bit
decompression_memory_size decompression_memory_size
state_memory_size> state_memory_size>
skipping to change at page 37, line 15 skipping to change at page 37, line 25
:shared_state_id pad (6) :shared_state_id pad (6)
:access_shared_state :access_shared_state
INPUT-BYTES (6, shared_state_id, !) INPUT-BYTES (6, shared_state_id, !)
STATE-ACCESS (shared_state_id, 6, 0, 0, $decompressed_start, 0) STATE-ACCESS (shared_state_id, 6, 0, 0, $decompressed_start, 0)
6. Security considerations 6. Security considerations
This draft describes implementation options for the SigComp protocol This document describes implementation options for the SigComp
RFC-3320 [4]. Consequently the security considerations for this protocol [4]. Consequently the security considerations for this
draft match those of SigComp. document match those of SigComp.
7. Acknowledgements 7. Acknowledgements
Thanks to Thanks to Richard Price, Carsten Bormann, Adam Roach, Lawrence
Richard Price Conroy, Christian Schmidt, Max Riegel, Lars-Erik Jonsson, Jonathan
Carsten Bormann Rosenberg, Stefan Forsgren, Krister Svanbro, Miguel Garcia,
Adam Roach Christopher Clanton, Khiem Le, Ka Cheong Leung, Zoltan Barczikay for
Lawrence Conroy valuable input and review.
Christian Schmidt
Max Riegel
Lars-Erik Jonsson
Jonathan Rosenberg
Stefan Forsgren
Krister Svanbro
Miguel Garcia
Christopher Clanton
Khiem Le
Ka Cheong Leung
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 8. Intellectual Property Right Considerations
The IETF has been notified of intellectual property rights claimed in The IETF has been notified of intellectual property rights claimed in
regard to some or all of the specification contained in this regard to some or all of the specification contained in this
document. For more information consult the online list of claimed document. For more information consult the online list of claimed
rights. rights.
9. References 9. References
skipping to change at page 38, line 27 skipping to change at page 38, line 27
[4] Price, R., Borman, C., Christoffersson, J., Hannu, H., Liu, Z., [4] Price, R., Borman, C., Christoffersson, J., Hannu, H., Liu, Z.,
and J. Rosenberg, "Signaling Compression (SigComp)", RFC 3320, and J. Rosenberg, "Signaling Compression (SigComp)", RFC 3320,
January 2003. January 2003.
[5] Hannu, H., Christoffersson, J., Forsgren, S., Leung, K., Liu, [5] Hannu, H., Christoffersson, J., Forsgren, S., Leung, K., Liu,
Z., and R. Price, "Signaling Compression (SigComp) - Extended Z., and R. Price, "Signaling Compression (SigComp) - Extended
Operations", RFC 3321, January 2003. Operations", RFC 3321, January 2003.
[6] Garcia-Martin, M., Borman, C., Ott, J., Price, R., and A. [6] Garcia-Martin, M., Borman, C., Ott, J., Price, R., and A.
Roach, "The Session Initiation Protocol (SIP) and Session Roach, "The Session Initiation Protocol (SIP) and Session
Description Protocol (SDP) Statc Dictionary for Signaling Description Protocol (SDP) Static Dictionary for Signaling
Compression (SigComp)", RFC 3485, February 2003. Compression (SigComp)", RFC 3485, February 2003.
[7] Ziv, J. and A. Lempel, "A universal algorithm for sequential [7] Ziv, J. and A. Lempel, "A universal algorithm for sequential
data compression", IEEE 23:337-343, 1977. data compression", IEEE 23:337-343, 1977.
[8] Storer, J., "Data Compression: Methods and Theory", Computer [8] Storer, J., "Data Compression: Methods and Theory", Computer
Science Press ISBN 0-88175-161-8, 1998. Science Press ISBN 0-88175-161-8, 1998.
[9] Nelson, M., "LZW Data Compression", Dr Dobb's Journal, [9] Nelson, M., "LZW Data Compression", Dr Dobb's Journal,
October 1989. October 1989.
skipping to change at page 42, line 50 skipping to change at page 42, line 50
Copyright (C) The Internet Society (2005). This document is subject Copyright (C) The Internet Society (2005). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights. except as set forth therein, the authors retain all their rights.
Acknowledgment Acknowledgment
Funding for the RFC Editor function is currently provided by the Funding for the RFC Editor function is currently provided by the
Internet Society. Internet Society.
This Internet-Draft will expire on January 19, 2006. This Internet-Draft will expire on April 1, 2006.
 End of changes. 47 change blocks. 
76 lines changed or deleted 94 lines changed or added

This html diff was produced by rfcdiff 1.27, available from http://www.levkowetz.com/ietf/tools/rfcdiff/