tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search

RFC 3320

 
 
 

Signaling Compression (SigComp)

Part 3 of 3, p. 37 to 62
Prev RFC Part

 


prevText      Top      Up      ToC       Page 37 
9.  UDVM Instruction Set

   The UDVM currently understands 36 instructions, chosen to support the
   widest possible range of compression algorithms with the minimum
   possible overhead.

   Figure 11 lists the different instructions and the bytecode values
   used to encode the instructions.  The cost of each instruction in
   UDVM cycles is also given:

Top      Up      ToC       Page 38 
   Instruction:       Bytecode value:   Cost in UDVM cycles:

   DECOMPRESSION-FAILURE     0          1
   AND                       1          1
   OR                        2          1
   NOT                       3          1
   LSHIFT                    4          1
   RSHIFT                    5          1
   ADD                       6          1
   SUBTRACT                  7          1
   MULTIPLY                  8          1
   DIVIDE                    9          1
   REMAINDER                 10         1
   SORT-ASCENDING            11         1 + k * (ceiling(log2(k)) + n)
   SORT-DESCENDING           12         1 + k * (ceiling(log2(k)) + n)
   SHA-1                     13         1 + length
   LOAD                      14         1
   MULTILOAD                 15         1 + n
   PUSH                      16         1
   POP                       17         1
   COPY                      18         1 + length
   COPY-LITERAL              19         1 + length
   COPY-OFFSET               20         1 + length
   MEMSET                    21         1 + length
   JUMP                      22         1
   COMPARE                   23         1
   CALL                      24         1
   RETURN                    25         1
   SWITCH                    26         1 + n
   CRC                       27         1 + length
   INPUT-BYTES               28         1 + length
   INPUT-BITS                29         1
   INPUT-HUFFMAN             30         1 + n
   STATE-ACCESS              31         1 + state_length
   STATE-CREATE              32         1 + state_length
   STATE-FREE                33         1
   OUTPUT                    34         1 + output_length
   END-MESSAGE               35         1 + state_length

      Figure 11: UDVM instructions and corresponding bytecode values

   Each UDVM instruction costs a minimum of 1 UDVM cycle.  Certain
   instructions may cost additional cycles depending on the values of
   the instruction operands.  Named variables in the cost expressions
   refer to the values of the instruction operands with these names.

   Note that for the SORT instructions, the formula ceiling(log2(k))
   calculates the smallest value i such that k <= 2^i.

Top      Up      ToC       Page 39 
   The UDVM instruction set offers a mix of low-level and high-level
   instructions.  The high-level instructions can all be emulated using
   combinations of low-level instructions, but given a choice it is
   generally preferable to use a single instruction rather than a large
   number of general-purpose instructions.  The resulting bytecode will
   be more compact (leading to a higher overall compression ratio) and
   decompression will typically be faster because the implementation of
   the high-level instructions can be more easily optimized.

   All instructions are encoded as a single byte to indicate the
   instruction type, followed by 0 or more bytes containing the operands
   required by the instruction.  The instruction specifies which of the
   four operand types of Section 8.5 is used in each case. For example
   the ADD instruction is followed by two operands:

   ADD ($operand_1, %operand_2)

   When converted into bytecode the number of bytes required by the ADD
   instruction depends on the value of each operand, and whether the
   multitype operand contains the operand value itself or a memory
   address where the actual value of the operand can be found.

   Each instruction is explained in more detail below.

   Whenever the description of an instruction uses the expression "and
   then", the intended semantics is that the effect explained before
   "and then" is completed before work on the effect explained after the
   "and then" is commenced.

9.1.  Mathematical Instructions

   The following instructions provide a number of mathematical
   operations including bit manipulation, arithmetic and sorting.

9.1.1.  Bit Manipulation

   The AND, OR, NOT, LSHIFT and RSHIFT instructions provide simple bit
   manipulation on 2-byte words.

   AND ($operand_1, %operand_2)
   OR ($operand_1, %operand_2)
   NOT ($operand_1)
   LSHIFT ($operand_1, %operand_2)
   RSHIFT ($operand_1, %operand_2)

Top      Up      ToC       Page 40 
   After the operation is complete, the value of the first operand is
   overwritten with the result.  (Note that since this operand is a
   reference, it is the 2-byte word at the memory address specified by
   the operand that is overwritten.)

   The precise definitions of LSHIFT and RSHIFT are given below.  Note
   that m and n are the 2-byte values encoded by the operands, and that
   floor(x) calculates the largest integer not greater than x:

   LSHIFT (m, n) := m * 2^n (modulo 2^16)
   RSHIFT (m, n) := floor(m / 2^n)

9.1.2.  Arithmetic

   The ADD, SUBTRACT, MULTIPLY, DIVIDE and REMAINDER instructions
   perform arithmetic on 2-byte words.

   ADD ($operand_1, %operand_2)
   SUBTRACT ($operand_1, %operand_2)
   MULTIPLY ($operand_1, %operand_2)
   DIVIDE ($operand_1, %operand_2)
   REMAINDER ($operand_1, %operand_2)

   After the operation is complete, the value of the first operand is
   overwritten with the result.

   The precise definition of each instruction is given below:

   ADD (m, n)       := m + n (modulo 2^16)
   SUBTRACT (m, n)  := m - n (modulo 2^16)
   MULTIPLY (m, n)  := m * n (modulo 2^16)
   DIVIDE (m, n)    := floor(m / n)
   REMAINDER (m, n) := m - n * floor(m / n)

   Decompression failure occurs if a DIVIDE or REMAINDER instruction
   encounters an operand_2 that is zero.

9.1.3.  Sorting

   The SORT-ASCENDING and SORT-DESCENDING instructions sort lists of 2-
   byte words.

   SORT-ASCENDING (%start, %n, %k)
   SORT-DESCENDING (%start, %n, %k)

   The start operand specifies the starting memory address of the block
   of data to be sorted.

Top      Up      ToC       Page 41 
   The block of data itself is divided into n lists each containing k
   2-byte words.  The SORT-ASCENDING instruction applies a certain
   permutation to the lists, such that the first list is sorted into
   ascending order (treating each 2-byte word as an unsigned integer).
   The same permutation is applied to all n lists, so lists other than
   the first will not necessarily be sorted into order.

   In the case that two words have the same value, the original ordering
   of the list is preserved.

   For example, the first list might contain a set of integers to be
   sorted whilst the second list might be used to keep track of where
   the integers appear in the sorted list:

            Before sorting              After sorting

         List 1        List 2        List 1        List 2

            8             1             1             2
            1             2             1             3
            1             3             3             4
            3             4             8             1

   The SORT-DESCENDING instruction behaves as above, except that the
   first list is sorted into descending order.

9.1.4.  SHA-1

   The SHA-1 instruction calculates a 20-byte SHA-1 hash [RFC-3174] over
   the specified area of UDVM memory.

   SHA-1 (%position, %length, %destination)

   The position and length operands specify the starting memory address
   and the length of the byte string over which the SHA-1 hash is
   calculated.  Byte copying rules are enforced as per Section 8.4.

   The destination operand gives the starting address to which the
   resulting 20-byte hash will be copied.  Byte copying rules are
   enforced as above.

9.2.  Memory Management Instructions

   The following instructions are used to set up the UDVM memory, and to
   copy byte strings from one memory location to another.

Top      Up      ToC       Page 42 
9.2.1.  LOAD

   The LOAD instruction sets a 2-byte word to a certain specified value.
   The format of a LOAD instruction is as follows:

   LOAD (%address, %value)

   The first operand specifies the starting address of a 2-byte word,
   whilst the second operand specifies the value to be loaded into this
   word.  As usual, MSBs are stored before LSBs in the UDVM memory.

9.2.2.  MULTILOAD

   The MULTILOAD instruction sets a contiguous block of 2-byte words in
   the UDVM memory to specified values.

   MULTILOAD (%address, #n, %value_0, ..., %value_n-1)

   The first operand specifies the starting address of the contiguous
   2-byte words, whilst the operands value_0 through to value_n-1
   specify the values to load into these words (in the same order as
   they appear in the instruction).

   Decompression failure occurs if the set of 2-byte words set by the
   instruction would overlap the memory locations held by the
   instruction (including its operands) itself, i.e., if the instruction
   would be self-modifying.  (This restriction makes it simpler to
   implement MULTILOAD step-by-step instead of having to decode all
   operands before being able to copy data, as is implied by the
   conceptual model of instruction execution.)

9.2.3.  PUSH and POP

   The PUSH and POP instructions read from and write to the UDVM stack
   (as defined in Section 8.3).

   PUSH (%value)
   POP (%address)

   The PUSH instruction pushes the value specified by its operand on the
   stack.

   The POP instruction pops a value from the stack and then copies the
   value to the specified memory address.  (Note that the expression
   "and then" implies that the copying of the value is inconsequential
   for the stack operation itself, which happens beforehand.)

   See Section 8.3 for possible error conditions.

Top      Up      ToC       Page 43 
9.2.4.  COPY

   The COPY instruction is used to copy a string of bytes from one part
   of the UDVM memory to another.

   COPY (%position, %length, %destination)

   The position operand specifies the memory address of the first byte
   in the string to be copied, and the length operand specifies the
   number of bytes to be copied.

   The destination operand gives the address to which the first byte in
   the string will be copied.

   Byte copying is performed as per the rules of Section 8.4.

9.2.5.  COPY-LITERAL

   A modified version of the COPY instruction is given below:

   COPY-LITERAL (%position, %length, $destination)

   The COPY-LITERAL instruction behaves as a COPY instruction except
   that after copying is completed, the value of the destination operand
   is replaced by the address to which the next byte of data would be
   copied.  More precisely it is replaced by the value n, derived as per
   Section 8.4 with m set to the destination address of the last byte to
   be copied, if any (i.e., if the value of the length operand is zero,
   the value of the destination operand is not changed).

9.2.6.  COPY-OFFSET

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

   COPY-OFFSET (%offset, %length, $destination)

   The COPY-OFFSET instruction behaves as a COPY-LITERAL instruction
   except that an offset operand is given instead of a position operand.

   To derive the value of the position operand, starting at the memory
   address specified by destination, the UDVM counts backwards a total
   of offset memory addresses.

   If the memory address specified in byte_copy_left is reached, the
   next memory address is taken to be (byte_copy_right - 1) modulo 2^16.

Top      Up      ToC       Page 44 
   The COPY-OFFSET instruction then behaves as a COPY-LITERAL
   instruction, taking the value of the position operand to be the last
   memory address reached in the above step.

9.2.7.  MEMSET

   The MEMSET instruction initializes an area of UDVM memory to a
   specified sequence of values. The format of a MEMSET instruction is
   as follows:

   MEMSET (%address, %length, %start_value, %offset)

   The sequence of values used by the MEMSET instruction is specified by
   the following formula:

   Seq[n] := (start_value + n * offset) modulo 256

   The values Seq[0] to Seq[length - 1] inclusive are each interpreted
   as a single byte, and then concatenated to form a byte string where
   the first byte has value Seq[0], the second byte has value Seq[1] and
   so on up to the last byte which has value Seq[length - 1].

   The string is then byte copied into the UDVM memory beginning at the
   memory address specified as an operand to the MEMSET instruction,
   obeying the rules of Section 8.4.  (Note that the byte string may
   overwrite the MEMSET instruction or its operands; as explained in
   Section 8.5, the MEMSET instruction must be executed as if the
   original operands were still in place in the UDVM memory.)

9.3.  Program Flow Instructions

   The following instructions alter the flow of UDVM code.  Each
   instruction jumps to one of a number of memory addresses based on a
   certain specified criterion.

   Note that certain I/O instructions (see Section 9.4) can also alter
   program flow.

9.3.1.  JUMP

   The JUMP instruction moves program execution to the specified memory
   address.

   JUMP (@address)

   Decompression failure occurs if the value of the address operand lies
   beyond the overall UDVM memory size.

Top      Up      ToC       Page 45 
9.3.2.  COMPARE

   The COMPARE instruction compares two operands and then jumps to one
   of three specified memory addresses depending on the result.

   COMPARE (%value_1, %value_2, @address_1, @address_2, @address_3)

   If value_1 < value_2 then the UDVM continues instruction execution at
   the memory address specified by address 1. If value_1 = value_2 then
   it jumps to the address specified by address_2. If value_1 > value_2
   then it jumps to the address specified by address_3.

9.3.3.  CALL and RETURN

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

   CALL (@address)
   RETURN

   Both instructions use the UDVM stack of Section 8.3.  When the UDVM
   reaches a CALL instruction, it finds the memory address of the
   instruction immediately following the CALL instruction and pushes
   this 2-byte value on the stack, ready for later retrieval.  It then
   continues instruction execution at the memory address specified by
   the address operand.

   When the UDVM reaches a RETURN instruction it pops a value from the
   stack and then continues instruction execution at the memory address
   just popped.

   See Section 8.3 for error conditions.

9.3.4.  SWITCH

   The SWITCH instruction performs a conditional jump based on the value
   of one of its operands.

   SWITCH (#n, %j, @address_0, @address_1, ... , @address_n-1)

   When a SWITCH instruction is encountered the UDVM reads the value of
   j. It then continues instruction execution at the address specified
   by address j.

   Decompression failure occurs if j specifies a value of n or more, or
   if the address lies beyond the overall UDVM memory size.

Top      Up      ToC       Page 46 
9.3.5.  CRC

   The CRC instruction verifies a string of bytes using a 2-byte CRC.

   CRC (%value, %position, %length, @address)

   The actual CRC calculation is performed using the generator
   polynomial x^16 + x^12 + x^5 + 1, which coincides with the 2-byte
   Frame Check Sequence (FCS) of PPP [RFC-1662].

   The position and length operands define the string of bytes over
   which the CRC is evaluated.  Byte copying rules are enforced as per
   Section 8.4.

   The CRC value is computed exactly as defined for the 16-bit FCS
   calculation in [RFC-1662].

   The value operand contains the expected integer value of the 2-byte
   CRC.  If the calculated CRC matches the expected value then the UDVM
   continues instruction execution at the following instruction.
   Otherwise the UDVM jumps to the memory address specified by the
   address operand.

9.4.  I/O instructions

   The following instructions allow the UDVM to interface with its
   environment.  Note that in the overall SigComp architecture all of
   these interfaces pass to the decompressor dispatcher or to the state
   handler.

9.4.1.  DECOMPRESSION-FAILURE

   The DECOMPRESSION-FAILURE instruction triggers a manual decompression
   failure.  This is useful if the UDVM bytecode discovers that it
   cannot successfully decompress the message (e.g., by using the CRC
   instruction).

   This instruction has no operands.

9.4.2.  INPUT-BYTES

   The INPUT-BYTES instruction requests a certain number of bytes of
   compressed data from the decompressor dispatcher.

   INPUT-BYTES (%length, %destination, @address)

Top      Up      ToC       Page 47 
   The length operand indicates the requested number of bytes of
   compressed data, and the destination operand specifies the starting
   memory address to which they should be copied.  Byte copying is
   performed as per the rules of Section 8.4.

   If the instruction requests data that lies beyond the end of the
   SigComp message, no data is returned.  Instead the UDVM moves program
   execution to the address specified by the address operand.

   If the INPUT-BYTES is encountered after an INPUT-BITS or an INPUT-
   HUFFMAN instruction has been used, and the dispatcher currently holds
   a fraction of a byte, then the fraction MUST be discarded before any
   data is passed to the UDVM.  The first byte to be passed is the byte
   immediately following the discarded data.

9.4.3.  INPUT-BITS

   The INPUT-BITS instruction requests a certain number of bits of
   compressed data from the decompressor dispatcher.

   INPUT-BITS (%length, %destination, @address)

   The length operand indicates the requested number of bits.
   Decompression failure occurs if this operand does not lie between 0
   and 16 inclusive.

   The destination operand specifies the memory address to which the
   compressed data should be copied.  Note that the requested bits are
   interpreted as a 2-byte integer ranging from 0 to 2^length - 1, as
   explained in Section 8.2.

   If the instruction requests data that lies beyond the end of the
   SigComp message, no data is returned.  Instead the UDVM moves program
   execution to the address specified by the address operand.

9.4.4.  INPUT-HUFFMAN

   The INPUT-HUFFMAN instruction requests a variable number of bits of
   compressed data from the decompressor dispatcher.  The instruction
   initially requests a small number of bits and compares the result
   against a certain criterion; if the criterion is not met, then
   additional bits are requested until the criterion is achieved.

   The INPUT-HUFFMAN instruction is followed by three mandatory operands
   plus n additional sets of operands.  Every additional set contains
   four operands as shown below:

Top      Up      ToC       Page 48 
   INPUT-HUFFMAN (%destination, @address, #n, %bits_1, %lower_bound_1,
   %upper_bound_1, %uncompressed_1, ... , %bits_n, %lower_bound_n,
   %upper_bound_n, %uncompressed_n)

   Note that if n = 0 then the INPUT-HUFFMAN instruction is ignored and
   program execution resumes at the following instruction.
   Decompression failure occurs if (bits_1 + ... + bits_n) > 16.

   In all other cases, the behavior of the INPUT-HUFFMAN instruction is
   defined below:

   1. Set j := 1 and set H := 0.

   2. Request bits_j compressed bits.  Interpret the returned bits as an
      integer k from 0 to 2^bits_j - 1, as explained in Section 8.2.

   3. Set H := H * 2^bits_j + k.

   4. If data is requested that lies beyond the end of the SigComp
      message, terminate the INPUT-HUFFMAN instruction and move program
      execution to the memory address specified by the address operand.

   5. If (H < lower_bound_j) or (H > upper_bound_j) then set j := j + 1.
      Then go back to Step 2, unless j > n in which case decompression
      failure occurs.

   6. Copy (H + uncompressed_j - lower_bound_j) modulo 2^16 to the
      memory address specified by the destination operand.

9.4.5.  STATE-ACCESS

   The STATE-ACCESS instruction retrieves some previously stored state
   information.

   STATE-ACCESS (%partial_identifier_start, %partial_identifier_length,
   %state_begin, %state_length, %state_address, %state_instruction)

   The partial_identifier_start and partial_identifier_length operands
   specify the location of the partial state identifier used to retrieve
   the state information.  This identifier has the same function as the
   partial state identifier transmitted in the SigComp message as per
   Section 7.2.

   Decompression failure occurs if partial_identifier_length does not
   lie between 6 and 20 inclusive.  Decompression failure also occurs if
   no state item matching the partial state identifier can be found, if

Top      Up      ToC       Page 49 
   more than one state item matches the partial identifier, or if
   partial_identifier_length is less than the minimum_access_length of
   the matched state item. Otherwise, a state item is returned from the
   state handler.

   If any of the operands state_address, state_instruction or
   state_length is set to 0 then its value is taken from the returned
   item of state instead.

   Note that when calculating the number of UDVM cycles the STATE-ACCESS
   instruction costs (1 + state_length) cycles.  The value of
   state_length MUST be taken from the returned item of state in the
   case that the state_length operand is set to 0.

   The state_begin and state_length operands define the starting byte
   and number of bytes to copy from the state_value contained in the
   returned item of state.  Decompression failure occurs if bytes are
   copied from beyond the end of the state_value.  Note that
   decompression failure will always occur if the state_length operand
   is set to 0 but the state_begin operand is non-zero.

   The state_address operand contains a UDVM memory address.  The
   requested portion of the state_value is byte copied to this memory
   address using the rules of Section 8.4.

   Program execution then resumes at the memory address specified by
   state_instruction, unless this address is 0 in which case program
   execution resumes at the next instruction following the STATE-ACCESS
   instruction.  Note that the latter case only occurs if both the
   state_instruction operand and the state_instruction value from the
   requested state are set to 0.

9.4.6.  STATE-CREATE

   The STATE-CREATE instruction requests the creation of a state item at
   the receiving endpoint.

   STATE-CREATE (%state_length, %state_address, %state_instruction,
   %minimum_access_length, %state_retention_priority)

   Note that the new state item cannot be created until a valid
   compartment identifier has been returned by the application.
   Consequently, when a STATE-CREATE instruction is encountered the UDVM
   simply buffers the five supplied operands until the END-MESSAGE
   instruction is reached.  The steps taken at this point are described
   in Section 9.4.9.

Top      Up      ToC       Page 50 
   Decompression failure MUST occur if more than four state creation
   requests are made before the END-MESSAGE instruction is encountered.
   Decompression failure also occurs if the minimum_access_length does
   not lie between 6 and 20 inclusive, or if the
   state_retention_priority is 65535.

9.4.7.  STATE-FREE

   The STATE-FREE instruction informs the receiving endpoint that the
   sender no longer wishes to use a particular state item.

   STATE-FREE (%partial_identifier_start, %partial_identifier_length)

   Note that the STATE-FREE instruction does not automatically delete a
   state item, but instead reclaims the memory taken by the state item
   within a certain compartment, which is generally not known before the
   END-MESSAGE instruction is reached.  So just as for the STATE-CREATE
   instruction, when a STATE-FREE instruction is encountered the UDVM
   simply buffers the two supplied operands until the END-MESSAGE
   instruction is reached.  The steps taken at this point are described
   in Section 9.4.9.

   Decompression failure MUST occur if more than four state free
   requests are made before the END-MESSAGE instruction is encountered.
   Decompression failure also occurs if partial_identifier_length does
   not lie between 6 and 20 inclusive.

9.4.8.  OUTPUT

   The OUTPUT instruction provides successfully decompressed data to the
   dispatcher.

   OUTPUT (%output_start, %output_length)

   The operands define the starting memory address and length of the
   byte string to be provided to the dispatcher.  Note that the OUTPUT
   instruction can be used to output a partially decompressed message;
   each time the instruction is encountered it provides a new byte
   string that the dispatcher appends to the end of any bytes previously
   passed to the dispatcher via the OUTPUT instruction.

   The string of data is byte copied from the UDVM memory obeying the
   rules of Section 8.4.

   Decompression failure occurs if the cumulative number of bytes
   provided to the dispatcher exceeds 65536 bytes.

Top      Up      ToC       Page 51 
   Since there is technically a difference between outputting a 0-byte
   decompressed message, and not outputting a decompressed message at
   all, the OUTPUT instruction needs to distinguish between the two
   cases.  Thus, if the UDVM terminates before encountering an OUTPUT
   instruction it is considered not to have outputted a decompressed
   message.  If it encounters one or more OUTPUT instructions, each of
   which provides 0 bytes of data to the dispatcher, then it is
   considered to have outputted a 0-byte decompressed message.

9.4.9.  END-MESSAGE

   The END-MESSAGE instruction successfully terminates the UDVM and
   forwards the state creation and state free requests to the state
   handler together with any supplied feedback data.

   END-MESSAGE (%requested_feedback_location,
   %returned_parameters_location, %state_length, %state_address,
   %state_instruction, %minimum_access_length,
   %state_retention_priority)

   When the END-MESSAGE instruction is encountered, the decompressor
   dispatcher indicates to the application that a complete message has
   been decompressed.  The application may return a compartment
   identifier, which the UDVM forwards to the state handler together
   with the state creation and state free requests and any supplied
   feedback data.

   The actual decompressed message is outputted separately using the
   OUTPUT instruction; this conserves memory at the UDVM because there
   is no need to buffer an entire decompressed message before it can be
   passed to the dispatcher.

   The END-MESSAGE instruction may pass up to four state creation
   requests and up to four state free requests to the state handler.
   The requests are passed to the state handler in the same order as
   they are made; in particular it is possible for the state creation
   requests and the state free requests to be interleaved.

   The state creation requests are made by the STATE-CREATE instruction.
   Note however that the END-MESSAGE can make one state creation request
   itself using the supplied operands. If the specified
   minimum_access_length does not lie between 6 and 20 inclusive, or if
   the state_retention_priority is 65535 then the END-MESSAGE
   instruction fails to make a state creation request of its own
   (however decompression failure does not occur and the state creation
   requests made by the STATE-CREATE instruction are still valid).

Top      Up      ToC       Page 52 
   Note that there is a maximum limit of four state creation requests
   per instance of the UDVM.  Therefore, decompression failure occurs if
   the END-MESSAGE instruction makes a state creation request and four
   instances of the STATE-CREATE instruction have already been
   encountered.

   When creating a state item it is necessary to give the state_length,
   state address, state_instruction and minimum_access_length; these are
   supplied as operands in the STATE-CREATE instruction (or the END-
   MESSAGE instruction).  A complete item of state also requires a
   state_value and a state_identifier, which are derived as follows:

   The UDVM byte copies a string of state_length bytes from the UDVM
   memory beginning at state_address (obeying the rules of Section 8.4).
   This is the state_value.

   The UDVM then calculates a 20-byte SHA-1 hash [RFC-3174] over the
   byte string formed by concatenating the state_length, state_address,
   state_instruction, minimum_access_length and state_value (in the
   order given).  This is the state_identifier.

   The state_retention_priority is not part of the state item itself,
   but instead determines the order in which state will be deleted when
   the compartment exceeds its allocated state memory.  The
   state_retention_priority is supplied as an operand in the STATE-
   CREATE or END-MESSAGE instruction and is passed to the state handler
   as part of each state creation request.

   The state free requests are made by the STATE-FREE instruction. Each
   STATE-FREE instruction supplies the values partial_identifier_start
   and partial_identifier_length; upon reaching the END-MESSAGE
   instruction these values are used to byte copy a partial state
   identifier from the UDVM memory.  If no state item matching the
   partial state identifier can be found or if more than one state item
   in the compartment matches the partial state identifier, then the
   state free request is ignored (this does not cause decompression
   failure to occur).  Otherwise, the state handler frees the matched
   state item as specified in Section 6.2.

   As well as forwarding the state creation and state free requests, the
   END-MESSAGE instruction may also pass feedback data to the state
   handler.  Feedback data is used to inform the receiving endpoint
   about the capabilities of the sending endpoint, which can help to
   improve the overall compression ratio and to reduce the working
   memory requirements of the endpoints.

Top      Up      ToC       Page 53 
   Two types of feedback data are available: requested feedback and
   returned feedback.  The format of the requested feedback data is
   given in Figure 12.  As outlined in Section 3.2, the requested
   feedback data can be used to influence the contents of the returned
   feedback data in the reverse direction.

   The returned feedback data is itself subdivided into a returned
   feedback item and a list of returned SigComp parameters.  The
   returned feedback item is of sufficient importance to warrant its own
   field in the SigComp header as described in Section 7.1.  The
   returned SigComp parameters are illustrated in Figure 13.

   Note that the formats of Figure 12 and Figure 13 are only for local
   presentation of the feedback data on the interface between the UDVM
   and state handler.  The formats do not mandate any bits on the wire;
   the compressor can transmit the data in any form provided that it is
   loaded into the UDVM memory at the correct addresses.

   Moreover, the responsibility for ensuring that feedback data arrives
   successfully over an unreliable transport lies with the sender.  The
   receiving endpoint always uses the last received value for each field
   in the feedback data, even if the values are out of date due to
   packet loss or misordering.

   If the requested_feedback_location operand is set to 0, then no
   feedback request is made; otherwise, it points to the starting memory
   address of the requested feedback data as shown in Figure 12.

        0   1   2   3   4   5   6   7
      +---+---+---+---+---+---+---+---+
      |     reserved      | Q | S | I |  requested_feedback_location
      +---+---+---+---+---+---+---+---+
      |                               |
      :    requested feedback item    :  if Q = 1
      |                               |
      +---+---+---+---+---+---+---+---+

               Figure 12: Format of requested feedback data

   The reserved bits may be used in future versions of SigComp, and are
   set to 0 in Version 0x01.  Non-zero values should be ignored by the
   receiving endpoint.

   The Q-bit indicates whether a requested feedback item is present or
   not.  The compressor can set the requested feedback item to an
   arbitrary value, which will then be transmitted unmodified in the
   reverse direction as a returned feedback item.  See Chapter 5 for
   further details of how the requested feedback item is returned.

Top      Up      ToC       Page 54 
   The format of the requested feedback item is identical to the format
   of the returned feedback item illustrated in Figure 4.

   The compressor sets the S-bit to 1 if it does not wish (or no longer
   wishes) to save state information at the receiving endpoint and also
   does not wish to access state information that it has previously
   saved.  Consequently, if the S-bit is set to 1 then the receiving
   endpoint can reclaim the state memory allocated to the remote
   compressor and set the state_memory_size for the compartment to 0.

   The compressor may change its mind and switch the S-bit back to 0 in
   a later message.  However, the receiving endpoint is under no
   obligation to use the original state_memory_size for the compartment;
   it may choose to allocate less memory to the compartment or possibly
   none at all.

   Similarly the compressor sets the I-bit to 1 if it does not wish (or
   no longer wishes) to access any of the locally available state items
   offered by the receiving endpoint.  This can help to conserve
   bandwidth because the list of locally available state items no longer
   needs to be returned in the reverse direction.  It may also conserve
   memory at the receiving endpoint, as the state handler can delete any
   locally available state items that it determines are no longer
   required by any remote endpoint.  Note that the compressor can set
   the I-bit back to 0 in a later message, but it cannot access any
   locally available state items that were previously offered by the
   receiving endpoint unless they are subsequently re-announced.

   If the returned_parameters_location operand is set to 0, then no
   SigComp parameters are returned; otherwise, it points to the starting
   memory address of the returned parameters as shown in Figure 13.

Top      Up      ToC       Page 55 
        0   1   2   3   4   5   6   7
      +---+---+---+---+---+---+---+---+
      |  cpb  |    dms    |    sms    |  returned_parameters_location
      +---+---+---+---+---+---+---+---+
      |        SigComp_version        |
      +---+---+---+---+---+---+---+---+
      | length_of_partial_state_ID_1  |
      +---+---+---+---+---+---+---+---+
      |                               |
      :  partial_state_identifier_1   :
      |                               |
      +---+---+---+---+---+---+---+---+
              :               :
      +---+---+---+---+---+---+---+---+
      | length_of_partial_state_ID_n  |
      +---+---+---+---+---+---+---+---+
      |                               |
      :  partial_state_identifier_n   :
      |                               |
      +---+---+---+---+---+---+---+---+

             Figure 13: Format of returned SigComp parameters

   The first byte encodes the SigComp parameters cycles_per_bit,
   decompression_memory_size and state_memory_size as per Section 3.3.1.
   The byte can be set to 0 if the three parameters are not included in
   the feedback data.  (This may be useful to save bits in the
   compressed message if the remote endpoint is already satisfied all
   necessary information has reached the endpoint receiving the
   message.)

   The second byte encodes the SigComp_version as per Section 3.3.2.
   Similar to the first byte, the second byte can be set to 0 if the
   parameter is not included in the feedback data.

   The remaining bytes encode a list of partial state identifiers for
   the locally available state items offered by the sending endpoint.
   Each state item is encoded as a 1-byte length field, followed by a
   partial state identifier containing as many bytes as indicated in the
   length field.  The sender can choose to send as few as 6 bytes if it
   believes that this is sufficient for the receiver to determine which
   state item is being offered.

   The list of state identifiers is terminated by a byte in the position
   where the next length field would be expected that is set to a value
   below 6 or above 20.  Note that upgraded SigComp versions may append
   additional items of data after the final length field.

Top      Up      ToC       Page 56 
10. Security Considerations

10.1.  Security Goals

   The overall security goal of the SigComp architecture is to not
   create risks that are in addition to those already present in the
   application protocols.  There is no intention for SigComp to enhance
   the security of the application, as it always can be circumvented by
   not using compression.  More specifically, the high-level security
   goals can be described as:

   1. Do not worsen security of existing application protocol

   2. Do not create any new security issues

   3. Do not hinder deployment of application security.

10.2.  Security Risks and Mitigation

   This section identifies the potential security risks associated with
   SigComp, and explains how each risk is minimized by the scheme.

10.2.1.  Confidentiality Risks

   - Attacking SigComp by snooping into state of other users:

   State is accessed by supplying a state identifier, which is a
   cryptographic hash of the state being referenced.  This implies that
   the referencing message already needs knowledge about the state.  To
   enforce this, a state item cannot be accessed without supplying a
   minimum of 48 bits from the hash.  This also minimizes the
   probability of an accidental state collision.  A compressor can,
   using the minimum_access_length operand of the STATE-CREATE and END-
   MESSAGE instructions, increase the number of bits that need to be
   supplied to access the state, increasing the protection against
   attacks.

   Generally, ways to obtain knowledge about the state identifier (e.g.,
   passive attacks) will also easily provide knowledge about the
   referenced state, so no new vulnerability results.

   An endpoint needs to handle state identifiers with the same care it
   would handle the state itself.

Top      Up      ToC       Page 57 
10.2.2.  Integrity Risks

   The SigComp approach assumes that there is appropriate integrity
   protection below and/or above the SigComp layer.  The state creation
   mechanism provides some additional potential to compromise the
   integrity of the messages; however, this would most likely be
   detectable at the application layer.

   - Attacking SigComp by faking state or making unauthorized changes to
     state:

   State cannot be destroyed by a malicious sender unless it can send
   messages that the application identifies as belonging to the same
   compartment the state was created under; this adds additional
   security risks only when the application allows the installation of
   SigComp state from a message where it would not have installed state
   itself.

   Faking or changing state is only possible if the hash allows
   intentional collision.

10.2.3.  Availability Risks (Avoiding DoS Vulnerabilities)

   - Use of SigComp as a tool in a DoS attack to another target:

   SigComp cannot easily be used as an amplifier in a reflection attack,
   as it only generates one decompressed message per incoming compressed
   message.  This message is then handed to the application; the utility
   as a reflection amplifier is therefore limited by the utility of the
   application for this purpose.

   However, it must be noted that SigComp can be used to generate larger
   messages as input to the application than have to be sent from the
   malicious sender; this therefore can send smaller messages (at a
   lower bandwidth) than are delivered to the application.  Depending on
   the reflection characteristics of the application, this can be
   considered a mild form of amplification.  The application MUST limit
   the number of packets reflected to a potential target - even if
   SigComp is used to generate a large amount of information from a
   small incoming attack packet.

Top      Up      ToC       Page 58 
   - Attacking SigComp as the DoS target by filling it with state:

   Excessive state can only be installed by a malicious sender (or a set
   of malicious senders) with the consent of the application.  The
   system consisting of SigComp and application is thus approximately as
   vulnerable as the application itself, unless it allows the
   installation of SigComp state from a message where it would not have
   installed application state itself.

   If this is desirable to increase the compression ratio, the effect
   can be mitigated by making use of feedback at the application level
   that indicates whether the state requested was actually installed -
   this allows a system under attack to gracefully degrade by no longer
   installing compressor state that is not matched by application state.

   Obviously, if a stream-based transport is used, the streams
   themselves constitute state that has to be handled in the same way
   that the application itself would handle a stream-based transport; if
   an application is not equipped for stream-based transport, it should
   not allow SigComp connections on a stream-based transport.  For the
   alternative SigComp usage described as "continuous mode" in Section
   4.2.1, an attacker could create any number of active UDVMs unless
   there is some DoS protection at a lower level (e.g., by using TLS in
   appropriate configurations).

   - Attacking the UDVM by faking state or making unauthorized changes
     to state:

   This is covered in Section 10.2.2.

   - Attacking the UDVM by sending it looping code:

   The application sets an upper limit to the number of "UDVM cycles"
   that can be used per compressed message and per input bit in the
   compressed message.  The damage inflicted by sending packets with
   looping code is therefore limited, although this may still be
   substantial if a large number of UDVM cycles are offered by the UDVM.
   However, this would be true for any decompressor that can receive
   packets over an unsecured transport.

11. IANA Considerations

   SigComp requires a 1-byte name space, the SigComp_version, which has
   been created by the IANA.  Upgraded versions of SigComp must be
   backwards-compatible with Version 0x01, described in this document.
   Adding additional UDVM instructions and assigning values to the
   reserved UDVM memory addresses are two possible upgrades for which
   this is the case.

Top      Up      ToC       Page 59 
   Following the policies outlined in [RFC-2434], the IANA policy for
   assigning a new value for the SigComp_version shall require a
   Standards Action.  Values are thus assigned only for Standards Track
   RFCs approved by the IESG.

12. Acknowledgements

   Thanks to

      Abigail Surtees
      Mark A West
      Lawrence Conroy
      Christian Schmidt
      Max Riegel
      Lars-Erik Jonsson
      Stefan Forsgren
      Krister Svanbro
      Miguel Garcia
      Christopher Clanton
      Khiem Le
      Ka Cheong Leung
      Robert Sugar

   for valuable input and review.

13. References

13.1. Normative References

   [RFC-1662]  Simpson, W., "PPP in HDLC-like Framing", STD 51, RFC
               1662, July 1994.

   [RFC-2119]  Bradner, S., "Key words for use in RFCs to Indicate
               Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC-3174]  Eastlake, 3rd, D. and P. Jones, "US Secure Hash Algorithm
               1 (SHA1)", RFC 3174, September 2001.

13.2. Informative References

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

   [RFC-2026]  Bradner, S., "The Internet Standards Process - Revision
               3", BCP 9, RFC 2026, October 1996.

   [RFC-2279]  Yergeau, F., "UTF-8, a transformation format of ISO
               10646", RFC 2279, January 1998.

Top      Up      ToC       Page 60 
   [RFC-2326]  Schulzrinne, H., Rao, A. and R. Lanphier, "Real Time
               Streaming Protocol (RTSP)", RFC 2326, April 1998.

   [RFC-2434]  Alvestrand, H. and T. Narten, "Guidelines for Writing an
               IANA Considerations Section in RFCs", BCP 26, RFC 2434,
               October 1998.

   [RFC-2960]  Stewart, R., Xie, Q., Morneault, K., Sharp, C.,
               Schwartzbauer, H., Taylor, T., Rytina, I., Kalla, M.,
               Zhang, L. and V. Paxson, "Stream Control Transmission
               Protocol", RFC 2960, October 2000.

   [RFC-3261]  Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston,
               A., Peterson, J., Sparks, R., Handley, M. and E.
               Schooler, "SIP: Session Initiation Protocol", RFC 3261,
               June 2002.

   [RFC-3321]  Hannu, H., Christoffersson, J., Forsgren, S., Leung,
               K.-C., Liu, Z. and R. Price, "Signaling Compression
               (SigComp) - Extended Operations", RFC 3321, January
               2003.

14. Authors' Addresses

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

   Phone: +44 1794 833681
   EMail: richard.price@roke.co.uk


   Carsten Bormann
   Universitaet Bremen TZI
   Postfach 330440
   D-28334 Bremen, Germany

   Phone: +49 421 218 7024
   EMail: cabo@tzi.org

Top      Up      ToC       Page 61 
   Jan Christoffersson
   Box 920
   Ericsson AB
   SE-971 28 Lulea, Sweden

   Phone: +46 920 20 28 40
   EMail: jan.christoffersson@epl.ericsson.se


   Hans Hannu
   Box 920
   Ericsson AB
   SE-971 28 Lulea, Sweden

   Phone: +46 920 20 21 84
   EMail: hans.hannu@epl.ericsson.se


   Zhigang Liu
   Nokia Research Center
   6000 Connection Drive
   Irving, TX 75039

   Phone: +1 972 894-5935
   EMail: zhigang.c.liu@nokia.com


   Jonathan Rosenberg
   dynamicsoft
   72 Eagle Rock Avenue
   First Floor
   East Hanover, NJ 07936

   EMail: jdrosen@dynamicsoft.com

Top      Up      ToC       Page 62 
15.  Full Copyright Statement

   Copyright (C) The Internet Society (2003).  All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works.  However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process must be
   followed, or as required to translate it into languages other than
   English.

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on an
   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
   TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
   BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
   HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Acknowledgement

   Funding for the RFC Editor function is currently provided by the
   Internet Society.