it is buffered until the UDVM has successfully decompressed the
SigComp message. It is then forwarded to the state handler with the
rest of the feedback data (see Section 9.4.9 for further details).
7.2. Accessing Stored State
The len field of the SigComp message determines which fields follow
the returned feedback item. If the len field is non-zero, then the
SigComp message contains a state identifier to access a state item at
the receiving endpoint. All state items include a 20-byte state
identifier as per Section 3.3.3, but it is possible to transmit as
few as 6 bytes from the identifier if the sender believes that this
is sufficient to match a unique state item at the receiving endpoint.
The len field encodes the number of transmitted bytes as follows:
Encoding: Length of partial state identifier
01 6 bytes
10 9 bytes
11 12 bytes
The partial state identifier is passed to the state handler, which
compares it with the most significant bytes of the state_identifier
in every currently stored state item. Decompression failure occurs
if no state item is matched or if more than one state item is
matched.
Decompression failure also occurs if exactly one state item is
matched but the state item contains a minimum_access_length greater
than the length of the partial state identifier. This prevents
especially sensitive state items from being accessed maliciously by
brute force guessing of the state_identifier.
If a state item is successfully accessed then the state_value byte
string is copied into the UDVM memory beginning at state_address.
The first 32 bytes of UDVM memory are then initialized to special
values as illustrated in Figure 5.
0 7 8 15
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| UDVM_memory_size | 0 - 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| cycles_per_bit | 2 - 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SigComp_version | 4 - 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| partial_state_ID_length | 6 - 7
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| state_length | 8 - 9
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
: reserved : 10 - 31
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 5: Initializing Useful Values in UDVM memory
The first five 2-byte words are initialized to contain some values
that might be useful to the UDVM bytecode (Useful Values). Note that
these values are for information only and can be overwritten when
executing the UDVM bytecode without any effect on the endpoint. The
MSBs of each 2-byte word are stored preceding the LSBs.
Addresses 0 to 5 indicate the resources available to the receiving
endpoint. The UDVM memory size is expressed in bytes modulo 2^16, so
in particular, it is set to 0 if the UDVM memory size is 65536 bytes.
The cycles_per_bit is expressed as a 2-byte integer taking the value
16, 32, 64 or 128. The SigComp_version is expressed as a 2-byte
value as per Section 3.3.2.
Addresses 6 to 9 are initialized to the length of the partial state
identifier, followed by the state_length from the retrieved state
item. Both are expressed as 2-byte values.
Addresses 10 to 31 are reserved and are initialized to 0 for Version
0x01 of SigComp. Future versions of SigComp can use these locations
for additional Useful Values, so a decompressor MUST NOT rely on
these values being zero.
Any remaining addresses in the UDVM memory that have not yet been
initialized MUST be set to 0.
The UDVM then begins executing instructions at the memory address
contained in state_instruction (which is part of the retrieved item
of state). Note that the remaining SigComp message is held by the
decompressor dispatcher until requested by the UDVM.
(Note that the Useful Values are only set at UDVM startup; there is
no special significance to this memory area afterwards. This means
that the UDVM bytecode is free to use these locations for any other
purpose a memory location might be used for; it just has to be aware
they are not necessarily initialized to zero.)
7.3. Uploading UDVM bytecode
If the len field is set to 0 then the bytecode needed to decompress
the SigComp message is supplied as part of the message itself. The
12-bit code_len field specifies the size of the uploaded UDVM
bytecode (from 0 to 4095 bytes inclusive); eight most significant
bits are in the first byte, followed by the four least significant
bits in the most significant bits in the second byte. The remaining
bits in the second byte are interpreted as a 4-bit destination field
that specifies the starting memory address to which the bytecode is
copied. The destination field is encoded as follows:
Encoding: Destination address:
0000 reserved
0001 2 * 64 = 128
0010 3 * 64 = 196
0011 4 * 64 = 256
: :
1111 16 * 64 = 1024
Note that the encoding 0000 is reserved for future SigComp versions,
and causes a decompression failure in Version 0x01.
The UDVM memory is initialized as per Figure 5, except that addresses
6 to 9 inclusive are set to 0 because no state item has been
accessed. The UDVM then begins executing instructions at the memory
address specified by the destination field. As above, the remaining
SigComp message is held by the decompressor dispatcher until needed
by the UDVM.
8. Overview of the UDVM
Decompression functionality for SigComp is provided by a Universal
Decompressor Virtual Machine (UDVM). The UDVM is a virtual machine
much like the Java Virtual Machine but with a key difference: it is
designed solely for the purpose of running decompression algorithms.
The motivation for creating the UDVM is to provide flexibility when
choosing how to compress a given application message. Rather than
picking one of a small number of pre-negotiated algorithms, the
compressor implementer has the freedom to select an algorithm of
their choice. The compressed data is then combined with a set of
UDVM instructions that allow the original data to be extracted, and
the result is outputted as a SigComp message. Since the UDVM is
optimized specifically for running decompression algorithms, the code
size of a typical algorithm is small (often sub 100 bytes).
Moreover, the UDVM approach does not add significant extra processing
or memory requirements compared to running a fixed preprogrammed
decompression algorithm.
Figure 6 gives a detailed view of the interfaces between the UDVM and
its environment.
+----------------+ +----------------+
| | Request compressed data | |
| |-------------------------------->| |
| |<--------------------------------| |
| | Provide compressed data | |
| | | |
| | Output decompressed data | Decompressor |
| |-------------------------------->| dispatcher |
| | | |
| | Indicate end of message | |
| |-------------------------------->| |
| |<--------------------------------| |
| UDVM | Provide compartment identifier | |
| | +----------------+
| |
| | +----------------+
| | Request state information | |
| |-------------------------------->| |
| |<--------------------------------| |
| | Provide state information | State |
| | | handler |
| | Make state creation request | |
| |-------------------------------->| |
| | Forward feedback information | |
+----------------+ +----------------+
Figure 6: Interfaces between the UDVM and its environment
Note that once the UDVM has been initialized, additional compressed
data and state information are only provided at the request of a
specific UDVM instruction.
This chapter describes the basic features of the UDVM including the
UDVM registers and the format of UDVM bytecode.
8.1. UDVM Registers
The UDVM registers are 2-byte words in the UDVM memory that have
special tasks, for example specifying the location of the stack used
by the CALL and RETURN instructions.
The UDVM registers are illustrated in Figure 7.
0 7 8 15
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| byte_copy_left | 64 - 65
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| byte_copy_right | 66 - 67
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| input_bit_order | 68 - 69
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| stack_location | 70 - 71
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 7: Memory addresses of the UDVM registers
The MSBs of each register are always stored before the LSBs. So, for
example, the MSBs of byte_copy_left are stored at Address 64 whilst
the LSBs are stored at Address 65.
The use of each UDVM register is defined in the following sections.
(Note that the UDVM registers start at Address 64, that is 32 bytes
after the area reserved for Useful Values. The intention is that the
gap, i.e., the area between Address 32 and Address 63, will often be
used as scratch-pad memory that is guaranteed to be zero at UDVM
startup and is efficiently addressable in operand types reference ($)
and multitype (%).)
8.2. Requesting Additional Compressed Data
The decompressor dispatcher stores the compressed data from the
SigComp message before it is requested by the UDVM via one of the
INPUT instructions. When the UDVM bytecode is first executed, the
dispatcher contains the remaining SigComp message after the header
has been used to initialize the UDVM as per Chapter 7.
Note that the INPUT-BITS and INPUT-HUFFMAN instructions retrieve a
stream of individual compressed bits from the dispatcher. To provide
bitwise compatibility with various well-known compression algorithms,
the input_bit_order register can modify the order in which individual
bits are passed within a byte.
The input_bit_order register contains the following three flags:
0 7 8 15
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| reserved |F|H|P| 68 - 69
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The P-bit controls the order in which bits are passed from the
dispatcher to the INPUT instructions. If set to 0, it indicates that
the bits within an individual byte are passed to the INPUT
instructions in MSB to LSB order. If it is set to 1, the bits are
passed in LSB to MSB order.
Note that the input_bit_order register cannot change the order in
which the bytes themselves are passed to the INPUT instructions
(bytes are always passed in the same order as they occur in the
SigComp message).
The following diagram illustrates the order in which bits are passed
to the INPUT instructions for both cases:
MSB LSB MSB LSB MSB LSB MSB LSB
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 1 2 3 4 5 6 7|8 9 ... | |7 6 5 4 3 2 1 0| ... 9 8|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Byte 0 Byte 1 Byte 0 Byte 1
P = 0 P = 1
Note that after one or more INPUT instructions the dispatcher may
hold a fraction of a byte (what used to be the LSBs if P = 0, or, the
MSBs, if P = 1). If an INPUT instruction is encountered and the P-
bit has changed since the last INPUT instruction, any fraction of a
byte still held by the dispatcher MUST be discarded (even if the
INPUT instruction requests zero bits). The first bit passed to the
INPUT instruction is taken from the subsequent byte.
When an INPUT instruction requests n bits of compressed data, it
interprets the received bits as an integer between 0 and 2^n - 1.
The F-bit and the H-bit specify whether the bits in these integers
are considered to arrive in MSB to LSB order (bit set to 0) or in LSB
to MSB order (bit set to 1).
If the F-bit is set to 0, the INPUT-BITS instruction interprets the
received bits as arriving MSBs first, and if it is set to 1, it
interprets the bits as arriving LSBs first. The H-bit performs the
same function for the INPUT-HUFFMAN instruction. Note that it is
possible to set these two bits to different values in order to use
different bit orders for the two instructions (certain algorithms
actually require this, e.g., DEFLATE [RFC-1951]). (Note that there
are no special considerations for changing the F- or H-bit between
INPUT instructions, unlike the discard rule for the P-bit described
above.)
Decompression failure occurs if an INPUT-BITS or an INPUT-HUFFMAN
instruction is encountered and the input_bit_order register does not
lie between 0 and 7 inclusive.
8.3. UDVM Stack
Certain UDVM instructions make use of a stack of 2-byte words stored
at the memory address specified by the 2-byte word stack_location.
The stack contains the following words:
Name: Starting memory address:
stack_fill stack_location
stack[0] stack_location + 2
stack[1] stack_location + 4
stack[2] stack_location + 6
: :
The notation stack_location is an abbreviation for the contents of
the stack_location register, i.e., the 2-byte word at locations 70
and 71. The notation stack_fill is an abbreviation for the 2-byte
word at stack_location and stack_location+1. Similarly, the notation
stack[n] is an abbreviation for the 2-byte word at
stack_location+2*n+2 and stack_location+2*n+3. (As always, the
arithmetic is modulo 2^16.)
The stack is used by the CALL, RETURN, PUSH and POP instructions.
"Pushing" a value on the stack is an abbreviation for copying the
value to stack[stack_fill] and then increasing stack_fill by 1. CALL
and PUSH push values on the stack.
"Popping" a value from the stack is an abbreviation for decreasing
stack_fill by 1, and then using the value stored in
stack[stack_fill]. Decompression failure occurs if stack_fill is
zero at the commencement of a popping operation. POP and RETURN pop
values from the stack.
For both of these abstract operations, the UDVM first takes note of
the current value of stack_location and uses this value for both
sub-operations (accessing the stack and manipulating stack_fill),
i.e., overwriting stack_location in the course of the operation is
inconsequential for the operation.
8.4. Byte copying
A number of UDVM instructions require a string of bytes to be copied
to and from areas of the UDVM memory. This section defines how the
byte copying operation should be performed.
The string of bytes is copied in ascending order of memory address,
respecting the bounds set by byte_copy_left and byte_copy_right.
More precisely, if a byte is copied from/to Address m then the next
byte is copied from/to Address n where n is calculated as follows:
Set k := m + 1 (modulo 2^16)
If k = byte_copy_right then set n := byte_copy_left, else set n := k
Decompression failure occurs if a byte is copied from/to an address
beyond the UDVM memory.
Note that the string of bytes is copied one byte at a time. In
particular, some of the later bytes to be copied may themselves have
been written into the UDVM memory by the byte copying operation
currently being performed.
Equally, it is possible for a byte copying operation to overwrite the
instruction that invoked the byte copy. If this occurs, then the
byte copying operation MUST be completed as if the original
instruction were still in place in the UDVM memory (this also applies
if byte_copy_left or byte_copy_right are overwritten).
Byte copying is used by the following UDVM instructions:
SHA-1, COPY, COPY-LITERAL, COPY-OFFSET, MEMSET, INPUT-BYTES, STATE-
ACCESS, OUTPUT, END-MESSAGE
8.5. Instruction operands and UDVM bytecode
Each of the UDVM instructions in a piece of UDVM bytecode is
represented by a single byte, followed by 0 or more bytes containing
the operands required by the instruction.
During instruction execution, conceptually the UDVM first fetches the
first byte of the instruction, determines the number and types of
operands required for this instruction, and then decodes all the
operands in sequence before starting to act on the instruction.
(Note that the UDVM instructions have been designed in such a way
that this sequence remains conceptual in those cases where it would
result in an unreasonable burden on the implementation.)
To reduce the size of typical UDVM bytecode, each operand for a UDVM
instruction is compressed using variable-length encoding. The aim is
to store more common operand values using fewer bytes than rarely
occurring values.
Four different types of operand are available: the literal, the
reference, the multitype and the address. Chapter 9 gives a complete
list of UDVM instructions and the operand types that follow each
instruction.
The UDVM bytecode for each operand type is illustrated in Figure 8 to
Figure 10, together with the integer values represented by the
bytecode.
Note that the MSBs in the bytecode are illustrated as preceding the
LSBs. Also, any string of bits marked with k consecutive "n"s is to
be interpreted as an integer N from 0 to 2^k - 1 inclusive (with the
MSBs of n illustrated as preceding the LSBs).
The decoded integer value of the bytecode can be interpreted in two
ways. In some cases it is taken to be the actual value of the
operand. In other cases it is taken to be a memory address at which
the 2-byte operand value can be found (MSBs found at the specified
address, LSBs found at the following address). The latter cases are
denoted by memory[X] where X is the address and memory[X] is the 2-
byte value starting at Address X.
The simplest operand type is the literal (#), which encodes a
constant integer from 0 to 65535 inclusive. A literal operand may
require between 1 and 3 bytes depending on its value.
Bytecode: Operand value: Range:
0nnnnnnn N 0 - 127
10nnnnnn nnnnnnnn N 0 - 16383
11000000 nnnnnnnn nnnnnnnn N 0 - 65535
Figure 8: Bytecode for a literal (#) operand
The second operand type is the reference ($), which is always used to
access a 2-byte value located elsewhere in the UDVM memory. The
bytecode for a reference operand is decoded to be a constant integer
from 0 to 65535 inclusive, which is interpreted as the memory address
containing the actual value of the operand.
Bytecode: Operand value: Range:
0nnnnnnn memory[2 * N] 0 - 65535
10nnnnnn nnnnnnnn memory[2 * N] 0 - 65535
11000000 nnnnnnnn nnnnnnnn memory[N] 0 - 65535
Figure 9: Bytecode for a reference ($) operand
Note that the range of a reference operand is always 0 - 65535
independently of how many bits are used to encode the reference,
because the operand always references a 2-byte value in the memory.
The third kind of operand is the multitype (%), which can be used to
encode both actual values and memory addresses. The multitype
operand also offers efficient encoding for small integer values (both
positive and negative) and for powers of 2.
Bytecode: Operand value: Range:
00nnnnnn N 0 - 63
01nnnnnn memory[2 * N] 0 - 65535
1000011n 2 ^ (N + 6) 64 , 128
10001nnn 2 ^ (N + 8) 256 , ... , 32768
111nnnnn N + 65504 65504 - 65535
1001nnnn nnnnnnnn N + 61440 61440 - 65535
101nnnnn nnnnnnnn N 0 - 8191
110nnnnn nnnnnnnn memory[N] 0 - 65535
10000000 nnnnnnnn nnnnnnnn N 0 - 65535
10000001 nnnnnnnn nnnnnnnn memory[N] 0 - 65535
Figure 10: Bytecode for a multitype (%) operand
The fourth operand type is the address (@). This operand is decoded
as a multitype operand followed by a further step: the memory address
of the UDVM instruction containing the address operand is added to
obtain the correct operand value. So if the operand value from
Figure 10 is D then the actual operand value of an address is
calculated as follows:
operand_value = (memory_address_of_instruction + D) modulo 2^16
Address operands are always used in instructions that control program
flow, because they ensure that the UDVM bytecode is position-
independent code (i.e., it will run independently of where it is
placed in the UDVM memory).
8.6. UDVM Cycles
Once the UDVM has been invoked it executes the instructions contained
in its memory consecutively unless otherwise indicated (for example
when the UDVM encounters a JUMP instruction). If the next
instruction to be executed lies outside the available memory then
decompression failure occurs (see Section 8.7).
To ensure that a SigComp message cannot consume excessive processing
resources, SigComp limits the number of "UDVM cycles" allocated to
each message. The number of available UDVM cycles is initialized to
1000 plus the number of bits in the SigComp header (as described in
Section 7); this sum is then multiplied by cycles_per_bit. Each time
an instruction is executed the number of available UDVM cycles is
decreased by the amount specified in Chapter 9. Additionally, if the
UDVM successfully requests n bits of compressed data using one of the
INPUT instructions then the number of available UDVM cycles is
increased by n * cycles_per_bit once the instruction has been
executed.
This means that the maximum number of UDVM cycles available for
processing an n-byte SigComp message is given by the formula:
maximum_UDVM_cycles = (8 * n + 1000) * cycles_per_bit
The reason that this total is not allocated to the UDVM when it is
invoked is that the UDVM can begin to decompress a message that has
only been partially received. So the total message size may not be
known when the UDVM is initialized.
Note that the number of UDVM cycles MUST NOT be increased if a
request for additional compressed data fails.
The UDVM stops executing instructions when it encounters an END-
MESSAGE instruction or if decompression failure occurs (see Section
8.7 for further details).
8.7. Decompression Failure
If a compressed message given to the UDVM is corrupted (either
accidentally or maliciously), then the UDVM may terminate with a
decompression failure.
Reasons for decompression failure include the following:
1. A SigComp message contains an invalid header as per Chapter 7.
2. A SigComp message is larger than the decompression_memory_size.
3. An instruction costs more than the number of remaining UDVM
cycles.
4. The UDVM attempts to read from or write to a memory address beyond
its memory size.
5. An unknown instruction is encountered.
6. An unknown operand is encountered.
7. An instruction is encountered that cannot be processed
successfully by the UDVM (for example a RETURN instruction when no
CALL instruction has previously been encountered).
8. A request to access some state information fails.
9. A manual decompression failure is triggered using the
DECOMPRESSION-FAILURE instruction.
If a decompression failure occurs when decompressing a message then
the UDVM informs the dispatcher and takes no further action. It is
the responsibility of the dispatcher to decide how to cope with the
decompression failure. In general a dispatcher SHOULD discard the
compressed message (or the compressed stream if the transport is
stream-based) and any decompressed data that has been outputted but
not yet passed to the application.
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:
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.
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)
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.
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.
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.
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.
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.
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.
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)
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:
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
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.
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.
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