[Docs] [txt|pdf] [Tracker] [WG] [Email] [Nits]

Versions: 00 draft-ietf-rohc-sigcomp

Network Working Group                  Richard Price, Siemens/Roke Manor
INTERNET-DRAFT                           Jonathan Rosenberg, dynamicsoft
Expires: May 2002                    Abigail Surtees, Siemens/Roke Manor
                                         Mark A West, Siemens/Roke Manor
                                     Lawrence Conroy, Siemens/Roke Manor

                                                       14 November, 2001

                     Universal Decompression Algorithm
                <draft-ietf-rohc-sigcomp-algorithm-00.txt>

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of [RFC-2026].

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups. Note that other
   groups may also distribute working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time. It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This document is a submission to the IETF ROHC WG. Comments should be
   directed to the mailing list of ROHC, rohc@cdt.luth.se.

Abstract

   This specification defines a "universal decompressor" capable of
   interoperating with a wide range of compression algorithms. Using the
   basic techniques of Huffman compression and LZ77-style string
   substitution, the decompressor can be configured to understand the
   output of many well-known compressors including [DEFLATE] and [LZW].














Price et al.                                                  [PAGE 1]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

Revision history

   Changes from <draft-ietf-rohc-sigcomp-01.txt>

     New COPY-LITERAL and COPY-OFFSET tokens added to reduce complexity
     for LZ77-based algorithms.

     COMPARE token modified to allow it to be used without a SWITCH
     token.

     HUFFMAN token modified to require fewer parameters.

     Support added for literal parameters (see Section 4.3).

     Example token sets added for decompression of LZ77, [DEFLATE] and
     [LZW] compressed messages.


Table of contents

   1.  Introduction.................................................3
   2.  Terminology..................................................3
   3.  Requirements on underlying transport protocol................3
   4.  Description of the universal decompressor....................4
   4.1.  Structure of universal decompressor dictionary.............5
   4.2.  Important entries in the byte buffer.......................5
   4.3.  Token parameters...........................................5
   4.4.  Decompressor actions upon receiving a compressed message...6
   4.5.  Decompression failure......................................7
   5.  Library of tokens............................................8
   5.1.  COPY.......................................................9
   5.2.  ADD / SUBTRACT.............................................10
   5.3.  LSHIFT / RSHIFT............................................10
   5.4.  COMPARE....................................................11
   5.5.  SWITCH.....................................................11
   5.6.  CALL / RETURN..............................................11
   5.7.  HUFFMAN....................................................12
   6.  Security considerations......................................14
   7.  References...................................................15
   8.  Authors' addresses...........................................15
   A.  Example sets of tokens.......................................16
   A.1.  Mnemonic language..........................................16
   A.2.  Example token set for simple LZ77 decompression............17
   A.3.  Example token set for DEFLATE decompression................17
   A.4.  Example token set for LZW decompression....................20










Price et al.                                                  [PAGE 2]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

1.  Introduction

   This draft introduces the concept of a "universal decompressor".

   The goal of the document is to standardize a decompressor capable of
   interoperating with a wide range of compression algorithms.
   Consequently this draft describes the decompressor operation only,
   i.e. the actions which the decompressor takes upon receiving a
   certain instruction from the compressor.

2.  Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC-2119].

   Byte buffer

     The universal decompressor maintains a byte buffer containing any
     previously received text strings that might be useful for future
     compression.

   Token

     A token is an instruction transmitted from the compressor to the
     decompressor.


3.  Requirements on underlying transport protocol

   The universal decompressor takes as its input a sequence of
   compressed messages, which are processed and then outputted as a
   sequence of uncompressed messages. This chapter lists the
   requirements on the transport protocol used to carry compressed
   messages to the universal decompressor.

   Note that the universal decompressor outputs an uncompressed message
   when it encounters an explicit end-of-message character.
   Consequently there is no need for one uncompressed message to
   correspond to exactly one compressed message. Two or more compressed
   messages can be sent to reconstruct a single uncompressed message,
   which is very useful for segmenting compressed messages that are
   larger than the MTU of the transport protocol.

   Conversely, one compressed message can be sent to reconstruct
   several uncompressed messages. In particular, messages can be
   successfully decompressed even when the transport protocol provides
   data as a byte stream with no framing.

   Note however that the universal decompressor can make use of
   previously received messages to improve the overall compression
   ratio (see [V-J] for an example of a compression algorithm which
   uses previously received messages in this manner).


Price et al.                                                  [PAGE 3]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

   Consequently, the main requirement on the underlying protocol is
   that it MUST ensure that the contents of the decompressor byte
   buffer are as expected by the next message to be decompressed.

   This requirement can be supported in a number of ways. If the
   underlying transport protocol is reliable (for example TCP or
   [SCTP]) then the compressed messages are provided to the universal
   decompressor in the correct order and free from bit errors. In this
   case the byte buffer is automatically updated correctly between
   messages.

   If the underlying transport protocol is unreliable (for example UDP)
   then the byte buffer MUST be reset to a known state between
   compressed messages. This ensures that messages are not compressed
   relative to text that has not yet been received by the universal
   decompressor.

   The "known state" of the byte buffer can be negotiated a-priori: for
   example a set of tokens can be downloaded from the compressor to the
   decompressor when the universal decompressor is being set up. All
   messages are then compressed relative to these tokens. Alternatively
   the transport protocol can indicate to the decompressor how the byte
   buffer should be set up before each message is decompressed.

4.  Description of the universal decompressor

   An important feature of the universal decompressor is that it can
   interoperate with a wide range of compression algorithms. The
   precise method for compression is left as an implementation
   decision, and in fact the standard decompressor can interoperate
   with any of the following classes of algorithm:

   *    Generic text compressor (for example [DEFLATE] or a similar
        algorithm).

   *    Protocol-aware compressor offering excellent performance for
        one type of text message (for example the text messages
        generated by [SIP]).

   *    Hybrid compressor with similar performance to [DEFLATE] for
        generic text strings and superior performance for certain types
        of text message.

   The choice of which tokens to send to the decompressor is left as a
   local implementation decision at the compressor. The only
   requirement is that of transparency, i.e. the compressor MUST NOT
   send tokens which cause the decompressor to incorrectly decompress a
   given message.

   Note however that it is perfectly acceptable for the compressor to
   send tokens which update the byte buffer at the decompressor, but
   which cause no decompressed message to be outputted. Indeed, this is
   a useful technique for pre-populating the dictionary with well-known
   text strings.

Price et al.                                                  [PAGE 4]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

4.1.  Structure of universal decompressor dictionary

   The universal decompressor dictionary consists of a simple byte
   buffer designed to hold the current uncompressed message, the
   current compressed message, and any other previously received text
   strings that might be useful for future compression.

   The size buffer_size of the byte buffer can be negotiated by an
   externally defined mechanism (e.g. by the underlying protocol used
   to transport the compressed messages). Entries in the byte buffer
   are referred to as buffer[n] where 0 =< n < buffer_size.

   As all of the tokens currently use 2-byte indices into the byte
   buffer, the maximum size of the buffer is 64K.

4.2.  Important entries in the byte buffer

   The first few bytes in the byte buffer are used to store some
   important 2-byte integers. These integers are given the following
   names:

   Position in buffer:          Name:

        0 - 1                   first_token
        2 - 3                   uncompressed_start
        4 - 5                   uncompressed_end
        6 - 7                   circular_buffer
        8 - 9                   compressed_start
        10 - 11                 compressed_end
        12 - 13                 compressed_pointer
        14 - 15                 stack_free
        16 - 17                 stack[0]
        18 - 19                 stack[1]
        20 - 21                 stack[2]
           :                        :

   The MSBs of the integer are always stored before the LSBs. So, for
   example, the MSBs of first_token are stored in buffer[0] whilst the
   LSBs are stored in buffer[1].

   The use of each integer is described in the following sections of
   the draft.

4.3.  Token parameters

   Each of the tokens is followed by 0 or more bytes containing the
   parameters required by the token. At present all parameters are
   stored as 2-byte integers with MSBs stored in the byte preceding the
   LSBs in the byte buffer.

   The most significant bit of the 2-byte integer has a special
   meaning: it is used to determine whether the parameter is a literal
   value or an index pointing to a literal value.


Price et al.                                                  [PAGE 5]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

   If the most significant bit is 0 then the 2-byte integer is
   interpreted as a literal value from 0 to 32767.

   If the most significant bit is 1 then the 2-byte integer is
   interpreted as an index from 0 to 32767 (the most significant bit
   itself is ignored). This index points to the location in the buffer
   containing the literal value of the parameter (MSBs stored in
   buffer[index] and LSBs stored in buffer[index + 1]). If the index
   references a location beyond the size of the byte buffer then a bad
   compressed message has been received and decompression failure
   occurs (see Section 4.5.).

4.4.  Decompressor actions upon receiving a compressed message

   When the universal decompressor is initialized all entries in the
   byte buffer are set to 0. Upon receiving a compressed message, the
   decompressor strips off the underlying protocol header and then
   performs the following actions:

   1.)   The message is copied directly into the byte buffer beginning
   at the byte specified in compressed_start.

   The underlying protocol MUST NOT pass a compressed message of more
   than 1460 bytes to the universal decompressor. If a larger
   compressed message is received, the underlying protocol passes only
   the first 1460 bytes to the decompressor, and provides additional
   working memory to store the bytes that are not currently being
   decompressed. The remainder of the compressed message is passed to
   the decompressor in blocks of 1460 bytes (or less if it is the last
   block in the compressed message).

   The decompressor MUST NOT concatenate two messages to form a single
   compressed message. This is because compressed messages are
   typically padded with trailing zero bits so that they are a whole
   number of bytes long. Concatenating two messages would cause these
   padding bits to be incorrectly interpreted as compressed data.

   Note that the buffer is circular, so once a byte is copied into
   buffer[buffer_size - 1], the next byte is copied into
   buffer[circular_buffer]. The parameter circular_buffer (see Section
   4.2) can be set to prevent the first part of the buffer from being
   overwritten by new messages. Typically this area of the buffer is
   used to hold important tokens and text strings that should be kept
   from one compressed message to the next. If circular_buffer lies
   beyond the size of the byte buffer then decompression failure occurs
   (see Section 4.5).

   After the message has been copied into the byte buffer, the position
   of the last byte in the compressed message is copied into
   compressed_end. Also, the value in compressed_start is copied into
   compressed_pointer.

   2.)   Next, the tokens contained within the byte buffer are executed
   beginning at the byte specified in first_token. The tokens are

Price et al.                                                  [PAGE 6]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

   executed consecutively unless indicated explicitly (for example when
   the decompressor encounters a SWITCH token). If the next token to be
   executed lies outside the byte buffer then decompression failure
   occurs (see Section 4.5).

   3.)   The decompressor stops token execution when it reaches
   buffer[0] or buffer[1]. Depending on which buffer entry is reached,
   the following actions are then taken:

   If the decompressor reaches buffer[0], instead of executing the
   token contained within buffer[0] it stops token execution and
   outputs the uncompressed message. The location of the uncompressed
   message is from uncompressed_start up to, but not including
   uncompressed_end. After the uncompressed message has been outputted,
   the value in uncompressed_end is then copied into
   uncompressed_start. If uncompressed_start = uncompressed_end then no
   uncompressed message is outputted.

   As stated before the buffer is circular, so once a byte is copied
   from buffer[buffer_size - 1], the next byte is copied from
   buffer[circular_buffer]. If either uncompressed_start or
   uncompressed_end lie outside the circular buffer then decompression
   failure occurs.

   If buffer[1] is reached then token execution stops but no
   uncompressed message is outputted.

   When the next compressed message becomes available, the universal
   decompressor continues at Step 1.) above. Note that if the
   underlying transport protocol does not provide reliable, in-order
   message delivery then the contents of the byte buffer MUST be reset
   to the state expected by the next compressed message. This state can
   be negotiated a-priori, or the transport protocol can indicate to
   the decompressor how the byte buffer should be set up before the
   next message is decompressed.

4.5.  Decompression failure

   If the compressed messages received by the decompressor are
   corrupted (either accidentally or maliciously) then one of three
   possibilities might occur:

   *    A decompressed message is outputted that is incorrect.

   *    A token is encountered that cannot be processed successfully by
        the decompressor (for example a RETURN token when no CALL token
        has previously been encountered).

   *    The decompressor never finishes decompressing a message.

   To counter the first possibility the underlying protocol SHOULD
   include a checksum to verify either the compressed message or the
   uncompressed message. If a message fails the checksum then
   "decompression failure" has occurred. The decompressor does not

Price et al.                                                  [PAGE 7]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

   output an uncompressed message, and ignores any future compressed
   message until the byte buffer is reset.

   If a token is encountered that cannot be successfully processed then
   decompression failure occurs automatically.

   To counter the third possibility, decompression failure SHOULD also
   occur after a certain number of tokens have been processed for a
   given compressed message. The maximum number of tokens to process is
   currently left as an implementation decision (but might in future be
   negotiated).

5.  Library of tokens

   The universal decompressor currently understands twelve types of
   token, chosen to support the widest possible range of compression
   algorithms with the minimum possible overhead.

   All tokens are stored as a single byte to indicate the token type,
   followed by 0 or more bytes containing the parameters required by
   the token. At present all parameters are 2-byte integers with MSBs
   stored before LSBs. For example, the COPY token is followed by three
   parameters as shown below:

   COPY (position, length, destination)

   In the byte buffer a COPY token is stored as the following 7 bytes:

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |0 0 0 0 0 0 0 0| Position MSB  | Position LSB  |  Length MSB   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Length LSB   |Destination MSB|Destination LSB|
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Twelve token types are currently available to the universal
   decompressor. The following table lists the different token types
   and the byte values used to transmit the tokens to the decompressor:

   Token type:                  Corresponding byte value:

   COPY                                     0
   COPY-LITERAL                             1
   COPY-OFFSET                              2
   ADD                                      3
   SUBTRACT                                 4
   LSHIFT                                   5
   RSHIFT                                   6
   COMPARE                                  7
   SWITCH                                   8
   CALL                                     9
   RETURN                                   10
   HUFFMAN                                  11

Price et al.                                                  [PAGE 8]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

   Each token is explained in more detail below:

5.1.  COPY

   The COPY token instructs the decompressor to copy a string of bytes
   from one part of the byte buffer to another.

   A COPY token is stored in the byte buffer as 7 consecutive bytes as
   follows:

   COPY (position, length, destination)

   As with all tokens currently defined, the COPY token translates into
   a single byte for the token type followed by 2 bytes for each of the
   parameters.

   The meaning of the three parameters is explained below:

   Position:    2-byte integer indicating the location of the first
                byte in the string to be copied.

   Length:      2-byte integer indicating the number of bytes to be
                copied.

   Destination: 2-byte integer indicating the location to which the
                first byte in the string will be copied.

   Note that the copying function is performed on a byte-by-byte basis,
   with the position parameter indicating the first byte to be copied.
   In particular, some of the later bytes to be copied may themselves
   have been written into the byte buffer by the COPY token currently
   being executed.

   Equally, it is possible for a COPY token to overwrite itself or its
   parameters. If this occurs then the COPY token MUST continue to
   execute as if the parameters were still in place in the byte buffer.

   If the source or destination of the next byte to be copied is larger
   than (buffer_size - 1) then sufficient multiples of (buffer_size -
   circular_buffer) are subtracted until it is not. So for example,
   once a byte is copied into buffer[buffer_size - 1] the next byte is
   copied into buffer[circular_buffer]. If circular_buffer equals or
   exceeds buffer_size then a bad compressed message has been received
   and decompression failure occurs (see Section 4.5).

   A modified version of the COPY token is given below:

   COPY-LITERAL (position, length, destination)

   The COPY-LITERAL token is identical to COPY except that after
   copying, the destination parameter is replaced with the value
   (destination + length). If the destination parameter is a literal
   value then it is updated directly. If the destination parameter is
   an index then the literal value it references is updated instead.

Price et al.                                                  [PAGE 9]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

   As above, if (destination + length) is larger than (buffer_size - 1)
   then sufficient multiples of (buffer_size - circular_buffer) are
   subtracted until it is not.

   A further version of the COPY-LITERAL token is given below:

   COPY-OFFSET (offset, length, destination)

   The COPY-OFFSET token is identical to COPY-LITERAL except that an
   offset parameter is given instead of a position parameter. The two
   parameters are related by position = (destination - offset).

   If (destination - offset) does not lie between circular_buffer and
   (buffer_size - 1) inclusive then sufficient multiples of
   (buffer_size - circular_buffer) are added or subtracted until it
   does.

5.2.  ADD / SUBTRACT

   The ADD token instructs the decompressor to add two 2-byte integers
   (addition performed modulo 2^16) and to store the result in the
   location of the first parameter.

   The format of the ADD token is given below:

   ADD (parameter_1, parameter_2)

   Note that as per Section 4.3, depending on how the MSB is set the
   parameters can be interpreted as literal values or indices to
   literal values. If parameter_1 is a literal value then it is
   overwritten with the result of the addition. If parameter_1 is an
   index to a literal value then the literal value is overwritten (not
   parameter_1 itself).

   The SUBTRACT token is the same as the ADD token except that the
   second integer is subtracted from the first (subtraction performed
   modulo 2^16):

   SUBTRACT (parameter_1, parameter_2)

5.3.  LSHIFT / RSHIFT

   The LSHIFT token instructs the decompressor to left shift a 2-byte
   value by the specified number of bits:

   LSHIFT (parameter, no_of_bits)

   The value to be shifted is stored in parameter, and the number of
   bits to shift is stored in no_of_bits. As usual both can be stored
   either as a literal value or as an index to a literal value.

   If the value of no_of_bits does not lie between 0 and 15 inclusive
   then a bad compressed message has been received and decompression
   failure occurs.

Price et al.                                                 [PAGE 10]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

   The RSHIFT token is the same as the LSHIFT token except that the
   bits are right shifted:

   RSHIFT (parameter, no_of_bits)

5.4.  COMPARE

   The COMPARE token instructs the decompressor to compare two 2-byte
   values and then to jump to one of three specified indices depending
   on the result.

   COMPARE (parameter_1, parameter_2, index_1, index_2, index_3)

   If the parameter_1 < parameter_2 then the decompressor continues
   token execution at the byte position specified by index 1. If
   parameter_1 = parameter_2 then it jumps to index_2. If parameter_1 >
   parameter_2 then it jumps to index_3.

   If an index is specified which is beyond the size of the byte
   buffer, a bad compressed message has been received and decompression
   failure occurs.

5.5.  SWITCH

   The SWITCH token performs a conditional jump based on the value of
   its first parameter.

   SWITCH (j, index_0, index_1, ... , index_n-1)

   When a SWITCH token is encountered the decompressor reads the value
   of j. It then continues token execution at the byte position
   specified by index j.

   If j specifies an index which is beyond the size of the byte buffer,
   a bad compressed message has been received and decompression failure
   occurs.

5.6.  CALL / RETURN

   The CALL and RETURN tokens provide support for compression
   algorithms with a nested structure.

   CALL (index)

   RETURN

   When the decompressor reaches a CALL token, it finds the byte
   position of the token immediately following the CALL token and
   copies this 2-byte integer into stack[stack_free] ready for later
   retrieval. It then increases stack_free by 1 and continues token
   execution at the byte position specified by index.




Price et al.                                                 [PAGE 11]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

   When the decompressor reaches a RETURN token it decreases stack_free
   by 1, and then continues token execution at the byte position stored
   in stack[stack_free].

   If stack_free ever becomes more than buffer_size - 1 or less than 0
   then a bad compressed message has been received and decompression
   failure occurs (see Section 4.5).

5.7.  HUFFMAN

   The HUFFMAN token maps a shorthand Huffman code onto its
   uncompressed equivalent.

   The format of a HUFFMAN token is as follows:

   HUFFMAN (position, bit_offset, destination, n, bits_1, uncomp_1,
   code_1, bits_2, uncomp_2, code_2, ... , bits_n-1, uncomp_n-1,
   code_n-1, bits_n, uncomp_n)

   The HUFFMAN token is followed by four mandatory parameters plus n
   additional sets of parameters. Every set contains three parameters
   except the nth set, which contains two. The nth set of parameters
   omits the parameter code_n, as the decompressor can always work out
   what the correct value of code_n should be.

   The meaning of the four mandatory parameters is explained below:

   Position:    Indicates the byte location of the Huffman code to be
                decompressed.

   Bit Offset:  Indicates the bit offset at which the Huffman code
                begins within the byte specified above.

   Destination: Indicates the location to which the uncompressed value
                will be copied.

   n:           Indicates the number of additional sets of parameters
                that follow. If n = 0 then the HUFFMAN token is ignored
                by the decompressor.

   The remaining parameters specify the actual Huffman codes and their
   uncompressed equivalents. Each set of 3 parameters specifies a block
   of Huffman codes with the same length and (when treated as integers)
   with values that increase by 1 for each additional Huffman code. The
   precise meaning of the parameters is given below:

   bits_j:      Indicates the additional length in bits of the Huffman
                codes in block j, compared to the Huffman codes in
                block j-1. Note that the total length of the Huffman
                codes in set j is (bits_1 + bits_2 + ... + bits_j).

   uncomp_j:    Indicates the uncompressed value of the first Huffman
                code in set j.


Price et al.                                                 [PAGE 12]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

   code_j:      Indicates the compressed value (when read as an
                integer) of the last Huffman code in set j.

   Note that the compressed value of the first Huffman code in set j is
   not specified explicitly, but instead is taken to be 0 when j = 1 or
   (2^bits_j) x (1 + code_j-1) when j > 1. This simply means that the
   Huffman code is 1 greater than the largest Huffman code in set j-1,
   but padded with enough zeroes to give it the correct length in bits.

   For example, suppose that bits_1 = 2, uncomp_1 = 15 and code_1 = 1.
   This defines a set of 2 Huffman codes (00 and 01) with corresponding
   values 15 and 16.

   Suppose also that bits_2 = 1, uncomp_2 = 4 and code_2 = 7. This
   defines an additional set of 4 Huffman codes (100, 101, 110 and 111)
   with corresponding values 4, 5, 6 and 7.

   Huffman code:                Uncompressed value:

   00                                   15
   01                                   16
   100                                   4
   101                                   5
   110                                   6
   111                                   7

   The motivation for downloading Huffman codes to the decompressor in
   this form is that it is very easy to convert a compressed Huffman
   code into its uncompressed equivalent. This can be achieved by
   taking the following steps:

   1.)   Set j = 1, set code_0 = 65535 and set code_n = 65535.

   2.)   Read a total of (bits_1 + bits_2 + ... + bits_j) bits starting
   from the specified position and bit_offset. Interpret these bits as
   an integer H, with the first bit to be read as the MSB and the last
   bit to be read as the LSB.

   3.)   If (H > code_j) then set j = j + 1 and goto 2.

   4.)   Output (H + uncomp_j - (2^bits_j) x (1 + code_j-1)), with the
   arithmetic operations calculated modulo 2^16.

   Note that as the HUFFMAN token reads individual bits from within a
   byte, to avoid ambiguity it is necessary to define the order in
   which these bits are read. This draft specifies that a bit offset of
   0 indicates the least significant bit of a byte, whilst a bit offset
   of 7 indicates the most significant bit.

   For example, suppose that an 8-bit Huffman code begins at byte
   position 0 and bit offset 2. In this case the 8 bits of the Huffman
   code can be found in the following locations (Bit 0 is the first bit
   in the Huffman code and Bit 7 is the last bit):


Price et al.                                                 [PAGE 13]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

    MSB         LSB MSB         LSB

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |5 4 3 2 1 0    |            7 6|
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

        Byte 0          Byte 1

   If the parameter bit offset does not take a value between 0 and 7
   inclusive then a bad compressed message has been received and
   decompression failure occurs (see Section 4.5.). Decompression
   failure also occurs if a total of more than 16 bits are read from
   the specified position and bit offset.


6.  Security considerations

   Note that this initial version raises the issues, without detailing
   a specific solution to resolve them.

   Introduction:

   In effect, a compressed message is a program; the tokens are
   instructions that are executed by the decompressor. This presents
   particular risks to the operation of the node on which the
   decompressor is running. This is the case for any compression
   algorithm, and so affects the operation of a node using this one.

   Transport Mechanism Requirements:

   The algorithm itself has no security issues, but does place
   requirements on any transport mechanism used to deliver the
   messages.

   If such requirements are not met, then the operation of the system
   can be exposed to attack ranging from indirect reduction in service,
   direct denial of service, and modification of subsequent messages.

   An initial list of requirements on the transport mechanism is:

   - messages should be delivered reliably to avoid corruption - for
   some uses of this algorithm, this corruption may have longer lasting
   effects.

   - messages should be not be duplicated - to ensure that operations
   implied by those messages are executed once only.

   - potentially, the message source should be identified and/or
   validated - to restrict possible insinuation of "attack" messages by
   third parties and to allow "blacklisting" of individual sources that
   "behave badly".




Price et al.                                                 [PAGE 14]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

7.  References

   [DEFLATE]    "DEFLATE Compressed Data Format Specification version
                1.3", RFC 1951, P. Deutsch, May 1996

   [V-J]        "Compressing TCP/IP Headers for Low-Speed Serial
                Links", V. Jacobson, Internet Engineering Task Force,
                February 1990

   [LZW]        "LZW Data Compression", Mark Nelson, Dr. Dobb's
                Journal, October 1989

   [SCTP]       "Stream Control Transmission Protocol", Stewart et al,
                RFC 2960, Internet Engineering Task Force, October 2000

   [SIP]        "SIP: Session Initiation Protocol", Handley et al,
                RFC 2543, Internet Engineering Task Force, March 1999


8.  Authors' addresses

   Richard Price        Tel: +44 1794 833681
   Email:               richard.price@roke.co.uk

   Abigail Surtees      Tel: +44 1794 833131
   Email:               abigail.surtees@roke.co.uk

   Mark A West          Tel: +44 1794 833311
   Email:               mark.a.west@roke.co.uk

   Lawrence Conroy      Tel: +44 1794 833666
   Email:               lwc@roke.co.uk

   Roke Manor Research Ltd
   Romsey, Hants, SO51 0ZN
   United Kingdom


   Jonathan Rosenberg
   dynamicsoft
   72 Eagle Rock Avenue
   First Floor
   East Hanover, NJ 07936
   Email: jdrosen@dynamicsoft.com











Price et al.                                                 [PAGE 15]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

Appendix A.  Example sets of tokens

   This appendix gives three example sets of tokens which can be
   downloaded to the universal decompressor. The first set of tokens
   can be used to decompress a very simple variant of LZ77, which
   illustrates how the different token types are intended to be used.

   The next two examples show how the universal decompressor can be
   configured to understand the output of existing compression
   algorthms. One set of tokens allows the decompressor to understand
   [DEFLATE] compressed messages, whilst the other set allows the
   decompressor to understand [LZW] compressed messages.

A.1.  Mnemonic language

   Presenting the example set of tokens as a set of bytes would not be
   very informative, so they are written instead using a simple
   mnemonic language. Most importantly, the language allows the
   parameters of a token to be specified as text references rather than
   as 2-byte integers.

   The mnemonic language is translated into bytes as follows:

   Tokens:     Token names are given in capitals. Replace each
               name with the corresponding 1-byte value as per
               Chapter 5.

   Labels:     Label names are given as a colon followed by lowercase
               text. They are deleted when converting the mnemonics to
               bytes.

   References: These are indicated by a label name without the
               colon. Replace each reference with a 2-byte value
               specifying the location of the byte immediately
               following the label. Moreover if the reference is
               preceded by a "$" symbol then it is interpreted as an
               pointer rather than a literal value, and hence the MSB
               of the 2-byte value is set to 1.

   .short:     Each decimal number following ".short" is interpreted as
               a 2-byte integer with MSBs preceding LSBs. Unless
               otherwise specified, this is the default.

   .byte:      Each decimal number following ".byte" is interpreted as
               a single byte.

   Whitespace: All whitespace, brackets and commas just delimit the
               tokens. Delete.

   Comments:   These are indicated by a semicolon and continue
               to the end of the line. Delete.




Price et al.                                                 [PAGE 16]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

A.2.  Example token set for simple LZ77 decompression

   The first example gives the tokens required to support a very simple
   LZ77-based algorithm. The decompressor is instructed to interpret a
   compressed message as a set of 4-byte characters, where each
   character contains a 2-byte position integer followed by a 2-byte
   length integer. Taken together these integers point to a previously
   received text string in the byte buffer, which is then copied to the
   end of the uncompressed message.

   Since the compressor can only send references to strings already
   present in the byte buffer, before the first message is decompressed
   the buffer must be initialized with a static dictionary containing
   the 256 ASCII characters.

   :first_token            unpack_static_dictionary
   :uncompressed_start     1792
   :uncompressed_end       2048
   :circular_buffer        2048
   :compressed_start       compressed_message_start
   :compressed_end         0
   :compressed_pointer     0

   :bit_offset             0
   :position               0
   :length                 0
   :token_start            next_character

   :unpack_static_dictionary

   COPY-LITERAL (17, 1, $uncompressed_start)
   ADD ($position, 1)
   COMPARE ($position, 256, unpack_static_dictionary, continue, 0)

   ; The above tokens are used to initialize the static dictionary.

   :continue

   COPY (token_start, 2, first_token)

   :next_character

   HUFFMAN ($compressed_pointer, $bit_offset, position, 1, 16, 0)
   HUFFMAN ($compressed_pointer, $bit_offset, length, 1, 16, 0)
   COPY-LITERAL ($position, $length, $uncompressed_end)
   COMPARE ($compressed_pointer, $compressed_end, next_character, 0, 0)

   :compressed_message_start

A.3.  Example token set for DEFLATE decompression

   This example gives the tokens required to understand [DEFLATE]
   compressed messages as defined in RFC 1951. Note that the example


Price et al.                                                 [PAGE 17]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

   only covers static Huffman codes (Block Type 01); dynamic Huffman
   codes will be added in a future version.

   Note also that the order in which the HUFFMAN token decompresses
   bits within a byte differs from that specified in RFC 1951. An
   alternative version of the HUFFMAN token may be introduced to
   support the exact bit order of [DEFLATE] in future (although this is
   not an urgent issue, as the order in which bits are decompressed
   does not affect the overall compression ratio).

   :first_token            next_character
   :uncompressed_start     2048
   :uncompressed_end       2048
   :circular_buffer        2048
   :compressed_start       compressed_message_start
   :compressed_end         0
   :compressed_pointer     0

   :bit_offset             0
   :index                  0
   :extra_length_bits      0
   :length_value           0
   :extra_distance_bits    0
   :distance_value         0

   :next_character

   HUFFMAN ($compressed_pointer, $bit_offset, index, 4, 7, 16428, 23,
            1, 0, 191, 0, 16452, 199, 1, 144)

   ; The above HUFFMAN token decompresses a Huffman code from the
   ; length/literal alphabet.

   COMPARE ($index, 16428, literal, 0, length)

   ; The COMPARE token is used to determine whether the decoded
   ; character should be interpreted as a length value, a literal value
   ; or an end-of-block character. In the latter case the decompressor
   ; stops and outputs the uncompressed message.

   :literal

   COPY-LITERAL (17, 1, $uncompressed_end)
   COMPARE ($compressed_pointer, $compressed_end, next_character, 1, 1)

   ; If the decoded character is to be interpreted as a literal value
   ; then it is copied directly to the uncompressed message. The
   ; decompressor then checks whether more compressed characters are
   ; available. If it has run out then it pauses and waits for some
   ; more.

   :length

   LSHIFT ($index, 2)

Price et al.                                                 [PAGE 18]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

   COPY ($index, 4, extra_length_bits)

   ; If the decoded character is to be interpreted as a length value
   ; then as specified in [DEFLATE], the decompressor must first add a
   ; certain number of additional bits from the compressed message to
   ; this length value.

   HUFFMAN ($compressed_pointer, $bit_offset, extra_length_bits, 1,
            $extra_length_bits, 0)

   ; The above HUFFMAN token obtains the correct number of additional
   ; length bits from the compressed message.

   ADD ($length_value, $extra_length_bits)

   :distance

   HUFFMAN ($compressed_pointer, $bit_offset, index, 1, 5, 74)

   ; In [DEFLATE] a length code is always followed by a distance code.
   ; The above HUFFMAN token decompresses this character.

   LSHIFT ($index, 2)
   COPY ($index, 4, extra_distance_bits)
   HUFFMAN ($compressed_pointer, $bit_offset, extra_distance_bits, 1,
            $extra_distance_bits, 0)

   ; The above HUFFMAN token obtains the correct number of additional
   ; distance bits from the compressed message.

   ADD ($distance_value, $extra_distance_bits)
   COPY-OFFSET ($distance_value, $length_value, $uncompressed_end)

   ; The text string specified by the length and distance codes is then
   ; copied to the end of the uncompressed message.

   COMPARE ($compressed_pointer, $compressed_end, next_character, 1, 1)

   .byte 0 0 0 .short    ; 3 bytes worth of padding

   :length_table

   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

   ; This is the length table from Page 11 of [DEFLATE].

Price et al.                                                 [PAGE 19]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

   :distance_table

   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       767     9       1025
   9       1537    10      2049    10      3073
   11      4097    11      6145    12      8193
   12      12289   13      16385   13      24577

   ; This is the distance table from Page 11 of [DEFLATE].

   :compressed_message_start

   ; The compressed messages are stored in the byte buffer following
   ; the above set of tokens.

A.4.  Example token set for LZW decompression

   This example gives the tokens required to understand [LZW]
   compressed messages. This particular variant of LZW uses a codebook
   containing up to 1024 entries, and so each compressed character is a
   10-bit value referencing one of the entries in the codebook.

   :first_token            unpack_static_dictionary
   :uncompressed_start     5888
   :uncompressed_end       1
   :circular_buffer        6144
   :compressed_start       compressed_message_start
   :compressed_end         0
   :compressed_pointer     0

   :bit_offset             0
   :index                  0
   :position_value         0
   :length_value           0
   :codebook_next          2048
   :token_start            next_character

   :unpack_static_dictionary

   COPY-LITERAL (uncompressed_start, 4, $codebook_next)
   COPY-LITERAL (17, 1, $uncompressed_start)
   ADD ($index, 1)
   COMPARE ($index, 256, unpack_static_dictionary, continue, 0)

   ; The above tokens are used to initialize the first 256 entries in
   ; the LZW codebook with single ASCII characters.

   :continue


Price et al.                                                 [PAGE 20]


INTERNET-DRAFT          Universal Decompressor       14 November, 2001

   COPY (circular_buffer, 2, uncompressed_end)
   COPY (token_start, 2, first_token)

   :next_character

   HUFFMAN ($compressed_pointer, $bit_offset, index, 1, 10, 512)

   ; The above HUFFMAN token extracts 10 bits from the compressed
   ; message.

   LSHIFT ($index, 2)
   COPY ($index, 4, position_value)

   ; The contents of the corresponding codebook entry is retrieved by
   ; the above COPY token.

   COPY-LITERAL (uncompressed_end, 2, $codebook_next)
   COPY-LITERAL ($position_value, $length_value, $uncompressed_end)

   ; The above COPY-LITERAL token appends the selected text string to
   ; the end of the uncompressed message.

   ADD ($length_value, 1)
   COPY-LITERAL (length_value, 2, $codebook_next)

   ; As per the LZW algorithm, a new entry is added to the codebook
   ; containing the text string copied to the end of the uncompressed
   ; message, plus the next character in the uncompressed message.

   COMPARE ($compressed_pointer, $compressed_end, next_character, 0, 0)

   :compressed_message_start























Price et al.                                                 [PAGE 21]


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/