RFC 4464
Signaling Compression (SigComp) Users' Guide
Part 1 of 7 💖 more parts coming, bestie!
RFC 4464: Signaling Compression (SigComp) Users' Guide 🎀
Okay, so this is RFC 4464, the Signaling Compression (SigComp) Users' Guide. It's from May 2006 and was written by A. Surtees and M. West, both at Siemens/Roke Manor Research. It's an Informational document, which means it's a helpful guide and not an Internet standard. The header doesn't list any RFCs it obsoletes or updates, so it doesn't replace or change anything else. Super clean 🫶
Status of This Memo ✨
This memo gives information to the Internet community. It doesn't specify an Internet standard of any kind, and it can be distributed without limits. 🌸
Copyright Notice 💜
Copyright (C) The Internet Society (2006).
Abstract 🦋
This doc is an informational guide for people using the Signaling Compression (SigComp) protocol. Its whole goal is to help you make SigComp implementation choices, like which compression algorithm to pick and how much robustness you want against packets that get lost or arrive out of order. It's giving decision-making support 💅
Table of Contents 🧚
1. Introduction ....................................................3
2. Overview of the User Guide ......................................3
3. UDVM Assembly Language ..........................................4
3.1. Lexical Level ..............................................4
3.2. Syntactic Level ............................................5
3.2.1. Expressions .........................................7
3.2.2. Instructions ........................................8
3.2.3. Directives ..........................................9
3.2.4. Labels .............................................10
3.3. Uploading the Bytecode to the UDVM ........................11
4. Compression Algorithms .........................................12
4.1. Well-known Compression Algorithms .........................12
4.1.1. LZ77 ...............................................12
4.1.2. LZSS ...............................................16
4.1.3. LZW ................................................18
4.1.4. DEFLATE ............................................21
4.1.5. LZJH ...............................................24
4.2. Adapted Algorithms ........................................28
4.2.1. Modified DEFLATE ...................................28
5. Additional SigComp Mechanisms ..................................31
5.1. Acknowledging a State Item ................................32
5.2. Static Dictionary .........................................33
5.3. CRC Checksum ..............................................34
5.4. Announcing Additional Resources ...........................35
5.5. Shared Compression ........................................37
6. Security Considerations ........................................38
7. Acknowledgements ...............................................38
8. Intellectual Property Right Considerations .....................38
9. Informative References .........................................38
Appendix A. UDVM Bytecode for the Compression Algorithms ..........40
A.1. Well-known Algorithms .....................................40
A.1.1. LZ77 ..............................................40
A.1.2. LZSS ..............................................40
A.1.3. LZW ...............................................40
A.1.4. DEFLATE ...........................................40
A.1.5. LZJH ..............................................41
A.2. Adapted Algorithms ........................................41
A.2.1. Modified DEFLATE ...................................411. Introduction 🌈
Okay, so this doc is a user's guide for SigComp, which is defined in RFC 3320 [2]. The big idea is that SigComp standardizes a Universal Decompressor Virtual Machine (UDVM) 🤯 It can be programmed to understand the output of lots of well-known compressors, including DEFLATE [8] and LZW [7]. The bytecode for whichever compression algorithm you choose gets uploaded to the UDVM as part of the compressed data. Iconic behavior 👑
The basic SigComp RFC explains what an endpoint must do when it receives a SigComp message. But the part that makes the messages, the SigComp compressor, is up to the implementation. You can use any compressor you want, as long as the messages it makes can be successfully decompressed by the receiving endpoint. Main character energy 💅
This doc shows examples of a bunch of different compressors that work with SigComp. It also shows how to use some of the mechanisms, like acknowledgements, that are described in RFC 3321 [3]. ✨
2. Overview of the User Guide 🎀
When you're building a SigComp compressor, your first move is to pick a compression algorithm that can squish the application messages into a (hopefully) smaller form 🍓 SigComp can upload new bytecode for algorithms to the receiving endpoint, so you can support basically any compression algorithm, as long as someone has written the matching decompressor bytecode.
This document gives example bytecode for these algorithms:
- LZ77
- LZSS
- LZW
- DEFLATE
- LZJH
Any of these might be the right pick, depending on what you care about: the compression ratio, processing and memory needs, code size, implementation complexity, and Intellectual Property (IPR) considerations. Pick your fighter 🥊
On top of encoding the messages with your chosen algorithm, the compressor also has to make sure messages can still be decompressed correctly even when packets get lost or arrive out of order. The SigComp feedback mechanism can be used to acknowledge successful decompression at the remote endpoint. Honestly the most important part, no cap 🫶
The following robustness techniques and SigComp-specific mechanisms are covered in this document:
- Acknowledgements using the SigComp feedback mechanism
- Static dictionary
- Cyclic redundancy code (CRC) checksum
- Announcing additional resources
- Shared compression
You can use any or all of these mechanisms together with your chosen compression algorithm. Each mechanism comes with an example UDVM bytecode subroutine, and you can add those subroutines to the bytecode for one of the basic compression algorithms. (Note: The subroutine or the basic algorithm may require minor modification to ensure they work together correctly.) Heads up, bestie, you might have to tweak things so they play nicely together 🙈
3. UDVM Assembly Language 🦋
Writing UDVM programs straight in bytecode would be an absolute nightmare 😭 So the doc gives you a simple assembly language to make creating new decompression algorithms way easier. It has mnemonic codes for each UDVM instruction, plus simple directives for evaluating integer expressions, padding the bytecode, and so on.
The UDVM assembly language uses the customary two-level description technique, which splits the grammar into a lexical level and a syntactic level. Two layers, very organized 🧚
3.1. Lexical Level 💖
At the lexical level, a string of assembly is just zero or more tokens, optionally separated by whitespace. Each token can be a text name, an instruction opcode, a delimiter, or an integer, written in decimal, binary, or hex.
The following ABNF description, from RFC 4234 [1], defines the syntax of a token:
token = (name / opcode / delimiter / dec / bin / hex)
name = (lowercase / "_") 0*(lowercase / digit / "_")
opcode = uppercase *(uppercase / digit / "-")
delimiter = "." / "," / "!" / "$" / ":" / "(" / ")" /
operator
dec = 1*(digit)
bin = "0b" 1*("0" / "1")
hex = "0x" 1*(hex-digit)
hex-digit = digit / %x41-46 / %x61-66
digit = %x30-39
uppercase = %x41-5a
lowercase = %x61-7a
operator = "+" / "-" / "*" / "/" / "%" / "&" / "|" /
"^" / "~" / "<<" / ">>"When you're parsing for tokens, the longest match wins. In other words, a token is the longest string that matches the <token> rule above. Greedy but make it make sense 🍒
The syntax of whitespace and comments is defined by this ABNF:
ws = *(%x09 / %x0a / %x0d / %x20 / comment)
comment = ";" *(%x00-09 / %x0b-0c / %x0e-ff)
(%x0a / %x0d)Whitespace that matches <ws> gets skipped between tokens, but it also serves to end the longest match for a token. Those are the rules, babe 🎀
Comments start with the symbol ";" and run until the end of the line, like this:
LOAD (temp, 1) ; This is a comment.Any other input is a syntax error. No vibes allowed 🚫
When you parse at the lexical level, split the assembly string into a list of successive tokens, and delete the whitespace and comments. After that, the assembly gets parsed at the syntactic level, which is explained in Section 3.2. Next stop: the syntactic level 🧚
3.2. Syntactic Level ✨
okay so once the assembly is chopped up into tokens like we did in Section 3.1, the next step is turning it into a string of UDVM bytecode 🎀
at the syntax level, a bit of assembly is zero or more instructions, directives, or labels, and each one is built from one or more lexical tokens. it's giving LEGO bricks 🧱
this ABNF describes the assembly language's syntax. the lexical parsing step is assumed to be done already, so the token boundaries are known and the comments and whitespace are gone 💅
assembly = *(instruction / directive / label)
instruction = opcode ["(" operand *("," operand) ")"]
operand = [["$"] expression]
; Operands can be left blank if they can
; be automatically inferred by the
; compiler, e.g., a literal operand
; that specifies the total number of
; operands for the instruction.
; When "$" is prepended to an operand,
; the corresponding integer is an
; address rather than the actual operand
; value. This symbol is mandatory for
; reference operands, optional for
; multitypes and addresses, and
; disallowed for literals.
label = ":" name
directive = padding / data / set / readonly /
unknown-directive
unknown-directive = name ["(" expression *("," expression) ")"]
; The parser can ignore unknown
; directives. The resulting bytecode
; may or may not generate the expected
; results.
padding = ("pad" / "align" / "at") "(" expression ")"
data = ("byte" / "word") "(" expression *(","
expression) ")"
readonly = "readonly" "(" "0" / "1" ")"
set = "set" "(" name "," expression ")"
expression = value / "(" expression operator expression ")"
value = dec / bin / hex / name / "." / "!"
; "." is the location of this
; instruction/directive, whereas "!" is
; the location of the closest
; DECOMPRESSION-FAILUREthe next bit explains how to turn the instructions, labels, and directives into UDVM bytecode 🦋
3.2.1. Expressions
operand values for instructions and directives can be written as expressions 🧮 an expression can have one or more values written in decimal, binary, or hex (binary starts with "0b" and hex starts with "0x"). it can also use these operators:
"+" Addition
"-" Subtraction
"*" Multiplication
"/" Integer division
"%" Modulo arithmetic (a%b := a modulo b)
"&" Binary AND
"|" Binary OR
"^" Binary XOR
"~" Binary XNOR
"<<" Binary LSHIFT
">>" Binary RSHIFTevery operator's operands have to be wrapped in parentheses so it's super clear what order things get evaluated in 🎀 for example, ((1 + (2 * 3)) & (0xabcd - 0b00101010)) gives the result 3. ✨
expressions can also use the special values "." and "!" 🌸 when the parser sees ".", it gets swapped for the bytecode location of the current instruction or directive. when it sees "!", it gets swapped for the bytecode location of the closest DECOMPRESSION-FAILURE instruction (aka the closest zero byte). this is handy when you're writing UDVM instructions that trigger a decompression failure, like this:
INPUT-BYTES (1, temp, !)that instruction causes a decompression failure if it tries to read data from past the end of the compressed message 💀
Note: when you use "!" in assembly to generate bytecode, you have to make sure the address of the zero used at bytecode generation time will still contain zero when the bytecode runs 🙈 the readonly directive (see Section 3.2.3) can be used to do this.
you can also give integer values to text names 💜 when a text name shows up in an expression, it gets replaced by the integer value assigned to it. Section 3.2.3 explains how to assign integer values to text names.
3.2.2. Instructions
a UDVM instruction is the instruction opcode followed by zero or more operands. the operands go inside parentheses and are separated by commas, like this:
ADD ($3, 4)when generating bytecode, the parser should replace the instruction opcode with its corresponding 1-byte value from Figure 11 of SigComp [2] 🧚
each operand is an expression that evaluates to an integer, and it can optionally start with "$". that "$" means the integer has to be read as the memory address where the operand value lives, not the actual operand value itself 🍓
when converting each operand to bytecode, the parser first figures out whether the instruction expects a literal, a reference, a multitype, or an address. if the operand is a literal, the parser inserts bytecode (usually the shortest) that can encode the operand value, as per Figure 8 of SigComp.
literal operands are used to say how many operands an instruction has in total, so you can leave a literal operand blank and let the assembler infer its value automatically 🫶 for example:
MULTILOAD (64, , 1, 2, 3, 4)the missing operand should get the value 4, because it's followed by a total of 4 operands.
if the operand is a reference, the parser inserts bytecode (usually the shortest) that can encode the memory address, as per Figure 9 of SigComp. reference operands always get a "$" in assembly, because they always encode memory addresses rather than actual operand values 👑
if the operand is a multitype, the parser first checks whether "$" is there. if it is, the parser inserts bytecode (usually the shortest) that encodes the integer as a memory address, as per Figure 10 of SigComp. if it isn't, the parser inserts bytecode (usually the shortest) that encodes the integer as an operand value, also as per Figure 10 of SigComp.
if the operand is an address, the parser checks whether "$" is there. if it is, the integer is encoded as a memory address, just like the multitype case above. if it isn't, the byte position of the opcode is subtracted from the supplied integer modulo 16, and the result is encoded as an operand value as per Figure 10 of SigComp 🦋
the length of the resulting bytecode depends on which parser you use. there can be several correct and usable representations of the same instruction, so you've got options 🌈
3.2.3. Directives
the assembly language has a bunch of directives for evaluating expressions, moving instructions to a specific memory address, and more 🎀
the directives "pad", "align", and "at" can add padding to the bytecode 🌸
"pad (n)" appends n consecutive padding bytes to the bytecode. the actual value of the padding bytes doesn't matter, so when the bytecode is uploaded to the UDVM, the padding bytes can be set to the initial values that are already in UDVM memory. this helps shrink the size of a SigComp message, which is so smart 🧠✨
"align (n)" appends the minimum number of padding bytes needed so that the total number of bytes of bytecode generated so far is a multiple of n bytes. if the bytecode is already aligned to a multiple of n bytes, no padding bytes get added.
"at (n)" appends enough padding bytes that the total number of bytes of bytecode generated so far is exactly n bytes. if more than n bytes have already been generated when the "at" directive shows up, the assembly code has an error 😭
the directives "byte" and "word" add specific data strings to the bytecode 💜
"byte (n[0],..., n[k-1])" appends k consecutive bytes to the bytecode. the byte string is given as expressions that evaluate to integers n[0],..., n[k-1] from 0 to 255.
"word (n[0],..., n[k-1])" appends k consecutive 2-byte words to the bytecode. the word string is given as expressions that evaluate to integers n[0],..., n[k-1] from 0 to 65535.
"set (name, n)" assigns the integer value n to a specified text name. the integer value can be written as an expression.
"readonly (n)", where n is 0 or 1, says whether an area of memory could be changed (0) or won't be changed (1) while the UDVM is running 🔥 this could be used, for example, together with "!" to make sure the address of the zero used will still contain zero when the bytecode runs. if there's no readonly directive, any address containing zero can be used by "!" (by default, there's a readonly (1) directive assumed at Address 0), and it's up to the assembly author to make sure that address still contains zero when the bytecode runs. if a readonly directive is used, then bytes between a readonly (0) and readonly (1) pair are NOT to be used by "!". once a readonly directive has been used, the bytes follow that directive from that address until either another readonly directive or the end of UDVM memory, whichever comes first 👑
3.2.4. Labels
a label is a special directive that assigns memory addresses to text names 🏷️
labels are written as a single colon followed by the text name to be defined. the (absolute) position of the byte right after the label is worked out and assigned to the text name. for example:
:start
LOAD (temp, 1)since the label "start" is at the very beginning of the bytecode, it gets the integer value 0 🌈
writing the label ":name" does exactly the same thing as writing the directive "set (name, .)" ✨
3.3. Uploading the Bytecode to the UDVM 🚀
okay bestie, once the parser has turned your assembly string into bytecode, it must be copied into UDVM memory starting at Address 0 🧚 and then executed, beginning with the first UDVM instruction in the bytecode. ✨
SigComp gives us this message format for uploading bytecode to the UDVM 💌:
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 1 1 1 1 | T | 0 |
+---+---+---+---+---+---+---+---+
| |
: returned feedback item : if T = 1
| |
+---+---+---+---+---+---+---+---+
| code_len |
+---+---+---+---+---+---+---+---+
| code_len | destination |
+---+---+---+---+---+---+---+---+
| |
: uploaded UDVM bytecode :
| |
+---+---+---+---+---+---+---+---+
| |
: remaining SigComp message :
| |
+---+---+---+---+---+---+---+---+The destination field should be set to the memory address of the first UDVM instruction 🎯. Note that if this address can't be represented by the destination field, then the bytecode can't be uploaded to the UDVM using the standard SigComp header. In particular, the memory address of the first UDVM instruction must always be a multiple of 64 bytes, or the standard SigComp header can't be used. Of course, there may be other ways to upload the bytecode to the UDVM, such as retrieving it directly via the INPUT-BYTES instruction. 🙌
Also, all memory addresses between Address 0 and Address 31 inclusive are initialized to endpoint-specific values by the UDVM 🧠. So they must be specified as padding in the bytecode, or the standard SigComp header can't be used. Memory addresses from Address 32 to Address (destination - 1) inclusive are initialized to 0, so they must be specified either as padding or as 0s if the bytecode is going to be successfully uploaded using the standard SigComp header. 💅
The code_len field should be set to the smallest value such that all memory addresses beginning at Address (destination + code_len) are either as initialised by the UDVM (to 0) or as set by the bytecode at runtime. Lowkey a very precise little rule 🥹.
The "uploaded UDVM bytecode" should be set to contain the segment of bytecode that lies between Address (destination) and Address (destination + code_len - 1) inclusive. ✨
4. Compression Algorithms 💜
This section describes a number of compression algorithms that a SigComp compressor can use 🦋. In each case, the document provides UDVM bytecode for the matching decompression algorithm, which can be uploaded to the receiving endpoint as part of a SigComp message. Each algorithm (as written in this section) assumes there is a 16K decompression memory size, 16 cycles per bit, and an 8K state memory size. Decompression will succeed with a smaller value for state memory size, but the full state won't be created. 🌈
Section 4.1.1 covers a simple algorithm in some detail, including the steps required to compress and decompress a SigComp message. The remaining sections cover well-known compression algorithms that can be adapted for use in SigComp with minimal modification. It's giving "build on what you already know" 🍓.
4.1. Well-known Compression Algorithms 🌸
4.1.1. LZ77 ✨
This section describes how to implement a very simple compression algorithm based on LZ77 [5]. Iconic. 👑
A compressed message generated by the simplified LZ77 scheme is a sequence of 4-byte characters, where each character contains a 2-byte position value followed by a 2-byte length value. Each pair of integers identifies a byte string in the UDVM memory. When concatenated, these byte strings form the decompressed message. 🧩
When implementing a bytecode decompressor for the simplified LZ77 scheme, the UDVM memory is partitioned into five distinct areas, as shown below 🗺️:
0 64 128 256 512
| scratch-pad | variables | bytecode | dictionary | circular buffer |
+-------------+-----------+----------+------------+-----------------+
<-----------> <---------> <--------> <----------> <--------------->
64 bytes 64 bytes 128 bytes 256 bytes 512+ bytesThe first 128 bytes hold the 2-byte variables the LZ77 decompressor needs 💖. Within that memory, the first 64 bytes are used as a scratch-pad, holding the 2-byte variables that can be discarded between SigComp messages. The next 64 bytes (and in fact all of the UDVM memory starting from Address 64) should be saved after decompressing a SigComp message, so later messages compress better. Main character energy for the saved state 🫶.
The bytecode for the LZ77 decompressor is stored beginning at Address 128. A total of 128 bytes are reserved for the bytecode, even though the LZ77 decompressor needs less. This leaves room for adding extra features to the decompressor at a later stage 🎀.
The next 256 bytes are initialized by the bytecode to contain the integers 0 to 255 inclusive. The purpose of this area is to provide a dictionary of all possible uncompressed characters 📖. This matters because it ensures the compressor can always generate a sequence of position/length pairs that encodes a given message. For example, a byte with value 0x41 (the ASCII character "A") can be found at Address 0x0141 of the UDVM memory, so the compressed character 0x0141 0001 will decompress to give this ASCII character. Note that encoding each byte of the application message as a separate 4-byte compressed character is not recommended, though, because the resulting "compressed" message is four times as large as the original uncompressed message. 🙈
The compression ratio of LZ77 is improved by the remaining UDVM memory, which stores a history buffer containing previously decompressed messages. Compressed characters can point to strings that were previously decompressed and stored in the buffer. So the overall compression ratio improves as the decompressor "learns" more text strings and can encode longer strings using a single compressed character. The buffer is circular, so older data gets overwritten by new data once the buffer is full 🔄.
The steps required to implement an LZ77 compressor and decompressor are similar, although compression is more processor-intensive because it requires a searching operation. Here's the assembly for the simplified LZ77 decompressor 🤓:
; Variables that do not need to be stored after decompressing each
; SigComp message are stored here:
at (32)
:position_value pad (2)
:length_value pad (2)
at (42)
set (requested_feedback_location, 0)
; The UDVM registers must be stored beginning at Address 64:
at (64)
; Variables that should be stored after decompressing a message are
; stored here. These variables will form part of the SigComp state
; item created by the bytecode:
:byte_copy_left pad (2)
:byte_copy_right pad (2)
:decompressed_pointer pad (2)
set (returned_parameters_location, 0)
align (64)
:initialize_memory
set (udvm_memory_size, 8192)
set (state_length, (udvm_memory_size - 64))
; The UDVM registers byte_copy_left and byte_copy_right are set to
; indicate the bounds of the circular buffer in the UDVM memory. A
; variable decompressed_pointer is also created and set pointing to
; the start of the circular buffer:
MULTILOAD (64, 3, circular_buffer, udvm_memory_size, circular_buffer)
; The "dictionary" area of the UDVM memory is initialized to contain
; the values 0 to 255 inclusive:
MEMSET (static_dictionary, 256, 0, 1)
:decompress_sigcomp_message
:next_character
; The next character in the compressed message is read by the UDVM
; and the position and length integers are stored in the variables
; position_value and length_value, respectively. If no more
; compressed data is available, the decompressor jumps to the
; "end_of_message" subroutine:
INPUT-BYTES (4, position_value, end_of_message)
; The position_value and length_value point to a byte string in the
; UDVM memory, which is copied into the circular buffer at the
; position specified by decompressed_pointer. This allows the string
; to be referenced by later characters in the compressed message:
COPY-LITERAL ($position_value, $length_value, $decompressed_pointer)
; The byte string is also outputted onto the end of the decompressed
; message:
OUTPUT ($position_value, $length_value)
; The decompressor jumps back to consider the next character in the
; compressed message:
JUMP (next_character)
:end_of_message
; The decompressor saves the UDVM memory and halts:
END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0)
at (256)
; Memory for the dictionary and the circular buffer are reserved by
; the following statements:
:static_dictionary pad (256)
:circular_bufferThe task of an LZ77 compressor is simply to find a sequence of 4-byte compressed characters that the bytecode above will decompress into the desired application message 🔍. As an example, a message compressed using the simplified LZ77 algorithm looks like this 👀:
0x0154 0001 0168 0001 0165 0001 0120 0001 0152 0001 0165 0001 0173
0x0002 0161 0001 0175 0001 0172 0001 0161 0001 016e 0001 0174 0001
0x0120 0001 0161 0001 020d 0002 0174 0001 0201 0003 0145 0001 016e
0x0001 0164 0001 0120 0001 016f 0001 0166 0001 0211 0005 0155 0001
0x016e 0001 0169 0001 0176 0001 0165 0001 0172 0002 0165 0001 010a
0x0001The uncompressed message is "The Restaurant at the End of the Universe\n". 🌌 (Iykyk, and if you don't, go read it 📚.)
The bytecode for the LZ77 decompressor can be uploaded as part of the compressed message, as specified in Section 3.3. However, to improve the overall compression ratio, it's important to avoid uploading bytecode in every compressed message 💸. For this reason, SigComp lets the UDVM save an area of its memory as a state item between compressed messages. Once a state item has been created, it can be retrieved by sending its corresponding state identifier, using the following SigComp message format 🔑:
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 1 1 1 1 | T | 1 |
+---+---+---+---+---+---+---+---+
| |
: returned feedback item : if T = 1
| |
+---+---+---+---+---+---+---+---+
| |
: partial state identifier :
| |
+---+---+---+---+---+---+---+---+
| |
: remaining SigComp message :
| |
+---+---+---+---+---+---+---+---+The partial_state_identifier field must contain the first 6 bytes of the state identifier for the state item being accessed (see [2] for details of how state identifiers are derived). 🪄
Note that the partial_state_identifier field could be 9 or 12 bytes, and in those cases, bits 6 and 7 of the first byte of the message would be 10 or 11, respectively. Bit-level vibes 🦋💜
4.1.2. LZSS ✨
okay bestie, this section gives you UDVM bytecode for LZSS 🦋. it's simple but literally so effective 💅 [6].
the big glow-up LZSS has over LZ77 is that every compressed character starts with a 1-bit indicator flag 🚩. that flag says whether the character is a literal or an offset/length pair. a literal is just one uncompressed byte that gets tacked straight onto the decompressed message 🌸.
an offset/length pair has a 12-bit offset value from 1 to 4096 inclusive, followed by a 4-bit length value from 3 to 18 inclusive ✨. together they point at one of the text strings you already received in the circular buffer, and that string gets appended to the end of the decompressed message 💖.
here's the assembly for an LZSS decompressor 👀:
at (32)
readonly (0)
:index pad (2)
:length_value pad (2)
:old_pointer pad (2)
at (42)
set (requested_feedback_location, 0)
at (64)
:byte_copy_left pad (2)
:byte_copy_right pad (2)
:input_bit_order pad (2)
:decompressed_pointer pad (2)
set (returned_parameters_location, 0)
align (64)
readonly (1)
:initialize_memory
set (udvm_memory_size, 8192)
set (state_length, (udvm_memory_size - 64))
MULTILOAD (64, 4, circular_buffer, udvm_memory_size, 0,
circular_buffer)
:decompress_sigcomp_message
:next_character
INPUT-HUFFMAN (index, end_of_message, 2, 9, 0, 255, 16384, 4, 4096,
8191, 1)
COMPARE ($index, 8192, length, end_of_message, literal)
:literal
set (index_lsb, (index + 1))
OUTPUT (index_lsb, 1)
COPY-LITERAL (index_lsb, 1, $decompressed_pointer)
JUMP (next_character)
:length
INPUT-BITS (4, length_value, !)
ADD ($length_value, 3)
LOAD (old_pointer, $decompressed_pointer)
COPY-OFFSET ($index, $length_value, $decompressed_pointer)
OUTPUT ($old_pointer, $length_value)
JUMP (next_character)
:end_of_message
END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0)
readonly (0)
:circular_bufferhere's an example of a message compressed with LZSS 🎀:
0x279a 0406 e378 b200 6074 1018 4ce6 1349 b842the uncompressed message is "Oh no, not again!" 😭
4.1.3. LZW
this section gives you UDVM bytecode for the well-known LZW compression algorithm, LZW [7] 🧚. it's used in a bunch of standards, including the GIF image format 🌈.
LZW works a lot like LZ77 🔁. it keeps a circular buffer of previously received decompressed data, and each compressed character references exactly one byte string from that buffer. the twist is that LZW also keeps a "codebook" 📖 with 1024 position/length pairs. those point at byte strings that LZW thinks are most likely to show up in the uncompressed data 👑.
you can reference the byte strings in the LZW codebook by sending a single 10-bit value from 0 to 1023 inclusive 🍓. the UDVM pulls out the matching text string from the codebook and appends it to the end of the decompressed message. then it creates a new codebook entry holding the current text string and the next character to occur in the decompressed message 💅.
here's the assembly for an LZW decompressor 🔮:
at (32)
:length_value pad (2)
:position_value pad (2)
:index pad (2)
at (42)
set (requested_feedback_location, 0)
at (64)
:byte_copy_left pad (2)
:byte_copy_right pad (2)
:input_bit_order pad (2)
:codebook_next pad (2)
:current_length pad (2)
:decompressed_pointer pad (2)
set (returned_parameters_location, 0)
align (64)
:initialize_memory
set (udvm_memory_size, 8192)
set (state_length, (udvm_memory_size - 64))
MULTILOAD (64, 6, circular_buffer, udvm_memory_size, 0, codebook, 1,
static_dictionary)
:initialize_codebook
; The following instructions are used to initialize the first 256
; entries in the LZW codebook with single ASCII characters:
set (index_lsb, (index + 1))
set (current_length_lsb, (current_length + 1))
COPY-LITERAL (current_length_lsb, 3, $codebook_next)
COPY-LITERAL (index_lsb, 1, $decompressed_pointer)
ADD ($index, 1)
COMPARE ($index, 256, initialize_codebook, next_character, 0)
:decompress_sigcomp_message
:next_character
; The following INPUT-BITS instruction extracts 10 bits from the
; compressed message:
INPUT-BITS (10, index, end_of_message)
; The following instructions interpret the received bits as an index
; into the LZW codebook and extract the corresponding
; position/length pair:
set (length_value_lsb, (length_value + 1))
MULTIPLY ($index, 3)
ADD ($index, codebook)
COPY ($index, 3, length_value_lsb)
; The following instructions append the selected text string to the
; circular buffer and create a new codebook entry pointing to this
; text string:
LOAD (current_length, 1)
ADD ($current_length, $length_value)
COPY-LITERAL (current_length_lsb, 3, $codebook_next)
COPY-LITERAL ($position_value, $length_value, $decompressed_pointer)
; The following instruction outputs the text string specified by the
; position/length pair:
OUTPUT ($position_value, $length_value)
JUMP (next_character)
:end_of_message
END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0)
:static_dictionary pad (256)
:circular_buffer
at (4492)
:codebookhere's an example of a message compressed with LZW 🫶:
0x14c6 f080 6c1b c6e1 9c20 1846 e190 201d 0684 206b 1cc2 0198 6f1c
0x9071 b06c 42c6 8195 111a 4731 a021 02bf f0the uncompressed message is "So long and thanks for all the fish!\n" 🐟
4.1.4. DEFLATE
this section gives you UDVM bytecode for the DEFLATE compression algorithm 🎁. DEFLATE is the algorithm behind the famous "gzip" file format, so you've literally been using it and didn't even know 🙈.
this bytecode decompresses the DEFLATE compressed data format [8], with the following two modifications 💜:
- the DEFLATE compressed data format separates blocks of compressed data by sending 7 consecutive zero bits. each SigComp message is assumed to contain a separate block of compressed data, so the end-of-block bits are implicit and don't need to be sent at the end of a SigComp message 🧁.
- this bytecode only supports DEFLATE block type 01 (data compressed with fixed Huffman codes) 🎯.
here's the assembly for the DEFLATE decompressor 🌷:
at (32)
readonly (0)
:index pad (2)
:extra_length_bits pad (2)
:length_value pad (2)
:extra_distance_bits pad (2)
:distance_value pad (2)
at (42)
set (requested_feedback_location, 0)
at (64)
:byte_copy_left pad (2)
:byte_copy_right pad (2)
:input_bit_order pad (2)
:decompressed_pointer pad (2)
:length_table pad (116)
:distance_table pad (120)
set (returned_parameters_location, 0)
align (64)
readonly (1)
:initialize_memory
set (udvm_memory_size, 8192)
set (state_length, (udvm_memory_size - 64))
set (length_table_start, (((length_table - 4) + 65536) / 4))
set (length_table_mid, (length_table_start + 24))
set (distance_table_start, (distance_table / 4))
MULTILOAD (64, 122, circular_buffer, udvm_memory_size, 5,
circular_buffer,
0, 3, 0, 4, 0, 5,
0, 6, 0, 7, 0, 8,
0, 9, 0, 10, 1, 11,
1, 13, 1, 15, 1, 17,
2, 19, 2, 23, 2, 27,
2, 31, 3, 35, 3, 43,
3, 51, 3, 59, 4, 67,
4, 83, 4, 99, 4, 115,
5, 131, 5, 163, 5, 195,
5, 227, 0, 258,
0, 1, 0, 2, 0, 3,
0, 4, 1, 5, 1, 7,
2, 9, 2, 13, 3, 17,
3, 25, 4, 33, 4, 49,
5, 65, 5, 97, 6, 129,
6, 193, 7, 257, 7, 385,
8, 513, 8, 769, 9, 1025,
9, 1537, 10, 2049, 10, 3073,
11, 4097, 11, 6145, 12, 8193,
12, 12289, 13, 16385, 13, 24577)
:decompress_sigcomp_message
INPUT-BITS (3, extra_length_bits, !)
:next_character
INPUT-HUFFMAN (index, end_of_message, 4,
7, 0, 23, length_table_start,
1, 48, 191, 0,
0, 192, 199, length_table_mid,
1, 400, 511, 144)
COMPARE ($index, length_table_start, literal, end_of_message,
length_distance)
:literal
set (index_lsb, (index + 1))
OUTPUT (index_lsb, 1)
COPY-LITERAL (index_lsb, 1, $decompressed_pointer)
JUMP (next_character)
:length_distance
; this is the length part
MULTIPLY ($index, 4)
COPY ($index, 4, extra_length_bits)
INPUT-BITS ($extra_length_bits, extra_length_bits, !)
ADD ($length_value, $extra_length_bits)
; this is the distance part
INPUT-HUFFMAN (index, !, 1, 5, 0, 31, distance_table_start)
MULTIPLY ($index, 4)
COPY ($index, 4, extra_distance_bits)
INPUT-BITS ($extra_distance_bits, extra_distance_bits, !)
ADD ($distance_value, $extra_distance_bits)
LOAD (index, $decompressed_pointer)
COPY-OFFSET ($distance_value, $length_value, $decompressed_pointer)
OUTPUT ($index, $length_value)
JUMP (next_character)
:end_of_message
END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0)
readonly (0)
:circular_bufferhere's an example of a message compressed with DEFLATE 🌸:
0xf3c9 4c4b d551 28c9 4855 08cd cb2c 4b2d 2a4e 5548 cc4b 5170 0532
0x2b4b 3232 f3d2 b900the uncompressed message is "Life, the Universe and Everything\n" 🌌✨
4.1.5. LZJH ✨
Okay bestie, this is the LZJH section 🫶 LZJH is the algorithm the ITU-T picked for Recommendation V.44 [9], so it's basically a celebrity in the compression world 💅
Here's the assembly for the LZJH decompressor 🧚
at (32)
readonly (0)
; The following 2-byte variables are stored in the scratch-pad memory
; area because they do not need to be saved after decompressing a
; SigComp message:
:length_value pad (2)
:position_value pad (2)
:index pad (2)
:extra_extension_bits pad (2)
:codebook_old pad (2)
at (42)
set (requested_feedback_location, 0)
at (64)
; UDVM_registers
:byte_copy_left pad (2)
:byte_copy_right pad (2)
:input_bit_order pad (2)
; The following 2-byte variables are saved as state after
; decompressing a SigComp message:
:current_length pad (2)
:decompressed_pointer pad (2)
:ordinal_length pad (2)
:codeword_length pad (2)
:codebook_next pad (2)
set (returned_parameters_location, 0)
align (64)
readonly (1)
:initialize_memory
; The following constants can be adjusted to configure the LZJH
; decompressor. The current settings are as recommended in the V.44
; specification (given that a total of 8K UDVM memory is available):
set (udvm_memory_size, 8192) ; sets the total memory for LZJH
set (max_extension_length, 8) ; sets the maximum string extension
set (min_ordinal_length, 7) ; sets the minimum ordinal length
set (min_codeword_length, 6) ; sets the minimum codeword length
set (codebook_start, 4492)
set (first_codeword, (codebook_start - 12))
set (state_length, (udvm_memory_size - 64))
MULTILOAD (64, 8, circular_buffer, udvm_memory_size, 7, 0,
circular_buffer, min_ordinal_length, min_codeword_length,
codebook_start)
:decompress_sigcomp_message
:standard_prefix
; The following code decompresses the standard 1-bit LZJH prefix
; that specifies whether the next character is an ordinal or a
; codeword/control value:
INPUT-BITS (1, index, end_of_message)
COMPARE ($index, 1, ordinal, codeword_control, codeword_control)
:prefix_after_codeword
; The following code decompresses the special LZJH prefix that only
; occurs after a codeword. It specifies whether the next character
; is an ordinal, a codeword/control value, or a string extension:
INPUT-HUFFMAN (index, end_of_message, 2, 1, 1, 1, 2, 1, 0, 1, 0)
COMPARE ($index, 1, ordinal, string_extension, codeword_control)
:ordinal
; The following code decompresses an ordinal character and creates
; a new codebook entry consisting of the ordinal character and the
; next character to be decompressed:
set (index_lsb, (index + 1))
set (current_length_lsb, (current_length + 1))
INPUT-BITS ($ordinal_length, index, !)
OUTPUT (index_lsb, 1)
LOAD (current_length, 2)
COPY-LITERAL (current_length_lsb, 3, $codebook_next)
COPY-LITERAL (index_lsb, 1, $decompressed_pointer)
JUMP (standard_prefix)
:codeword_control
; The following code decompresses a codeword/control value:
INPUT-BITS ($codeword_length, index, !)
COMPARE ($index, 3, control_code, initialize_memory, codeword)
:codeword
; The following code interprets a codeword as an index into the LZJH
; codebook. It extracts the position/length pair from the specified
; codebook entry; the position/length pair points to a byte string
; in the circular buffer, which is then copied to the end of the
; decompressed message. The code also creates a new codebook entry
; consisting of the byte string plus the next character to be
; decompressed:
set (length_value_lsb, (length_value + 1))
MULTIPLY ($index, 3)
ADD ($index, first_codeword)
COPY ($index, 3, length_value_lsb)
LOAD (current_length, 1)
ADD ($current_length, $length_value)
LOAD (codebook_old, $codebook_next)
COPY-LITERAL (current_length_lsb, 3, $codebook_next)
COPY-LITERAL ($position_value, $length_value, $decompressed_pointer)
OUTPUT ($position_value, $length_value)
JUMP (prefix_after_codeword)
:string_extension
; The following code decompresses a Huffman-encoded string extension:
INPUT-HUFFMAN (index, !, 4, 1, 1, 1, 1, 2, 1, 3, 2, 1, 1, 1, 13, 3,
0, 7, 5)
COMPARE ($index, 13, continue, extra_bits, extra_bits)
:extra_bits
INPUT-BITS (max_extension_length, extra_extension_bits, !)
ADD ($index, $extra_extension_bits)
:continue
; The following code extends the most recently created codebook entry
; by the number of bits specified in the string extension:
COPY-LITERAL ($position_value, $length_value, $position_value)
COPY-LITERAL ($position_value, $index, $decompressed_pointer)
OUTPUT ($position_value, $index)
ADD ($index, $length_value)
COPY (index_lsb, 1, $codebook_old)
JUMP (standard_prefix)
:control_code
; The code can handle all of the control characters in V.44 except
; for ETM (Enter Transparent Mode), which is not required for
; message-based protocols such as SigComp.
COMPARE ($index, 1, !, flush, stepup)
:flush
; The FLUSH control character jumps to the beginning of the next
; complete byte in the compressed message:
INPUT-BYTES (0, 0, 0)
JUMP (standard_prefix)
:stepup
; The STEPUP control character increases the number of bits used to
; encode an ordinal value or a codeword:
INPUT-BITS (1, index, !)
COMPARE ($index, 1, stepup_ordinal, stepup_codeword, 0)
:stepup_ordinal
ADD ($ordinal_length, 1)
JUMP (ordinal)
:stepup_codeword
ADD ($codeword_length, 1)
JUMP (codeword_control)
:end_of_message
END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0)
readonly (0)
:circular_bufferHere's an example of a message compressed with LZJH, so you can see it in action 👀
0x5c09 e6e0 cadc c8d2 dcce 40c2 40f2 cac2 e440 c825 c840 ccde 29e8
0xc2f0 40e0 eae4 e0de e6ca e65c 1403And the uncompressed message is "...spending a year dead for tax purposes.\n". Iconic 💀✨
4.2. Adapted Algorithms 🦋
Okay so SigComp isn't limited to the algorithms we've already seen. You can also use alternative algorithms with it 🌈 This next bit is a modified version of DEFLATE [8] 🎀
4.2.1. Modified DEFLATE 💜
The main glow-up is that the two-stage encoding of DEFLATE gets swapped for a single step, with a discrete Huffman code for each symbol 🔥 The literal/length symbol probabilities depend on whether the previous symbol was a literal or a match. Bit handling is simpler too: every bit gets input with the INPUT-HUFFMAN instruction, and the value of the H bit doesn't change, so all bits get input, read, and interpreted in the same order 🫶
Here's the assembly. String matching rules are the same as for the other LZ-based algorithms, with the alternative encoding of the literals and length/distance pairs 🍓
at (32)
readonly (0)
:index pad (2)
:distance_value pad (2)
:old_pointer pad (2)
at (42)
set (requested_feedback_location, 0)
at (64)
:byte_copy_left pad (2)
:byte_copy_right pad (2)
:input_bit_order pad (2)
:decompressed_pointer pad (2)
set (returned_parameters_location, 0)
at (128)
readonly (1)
:initialize_memory
set (udvm_memory_size, 8192)
set (state_length, (udvm_memory_size - 64))
MULTILOAD (64, 4, circular_buffer, udvm_memory_size, 0,
circular_buffer)
:decompress_sigcomp_message
:character_after_literal
INPUT-HUFFMAN (index, end_of_message, 16,
5, 0, 11, 46,
0, 12, 12, 256,
1, 26, 32, 257,
1, 66, 68, 32,
0, 69, 94, 97,
0, 95, 102, 264,
0, 103, 103, 511,
2, 416, 426, 35,
0, 427, 465, 58,
0, 466, 481, 272,
1, 964, 995, 288,
3, 7968, 7988, 123,
0, 7989, 8115, 384,
1, 16232, 16263, 0,
0, 16264, 16327, 320,
1, 32656, 32767, 144)
COMPARE ($index, 256, literal, distance, distance)
:character_after_match
INPUT-HUFFMAN (index, end_of_message, 16,
4, 0, 0, 511,
1, 2, 9, 256,
1, 20, 22, 32,
0, 23, 30, 264,
1, 62, 73, 46,
0, 74, 89, 272,
2, 360, 385, 97,
0, 386, 417, 288,
1, 836, 874, 58,
0, 875, 938, 320,
1, 1878, 1888, 35,
0, 1889, 2015, 384,
1, 4032, 4052, 123,
1, 8106, 8137, 0,
1, 16276, 16379, 144,
1, 32760, 32767, 248)
COMPARE ($index, 256, literal, distance, distance)
:literal
set (index_lsb, (index + 1))
OUTPUT (index_lsb, 1)
COPY-LITERAL (index_lsb, 1, $decompressed_pointer)
JUMP (character_after_literal)
:distance
SUBTRACT ($index, 253)
INPUT-HUFFMAN (distance_value, !, 9,
9, 0, 7, 9,
0, 8, 63, 129,
1, 128, 135, 1,
0, 136, 247, 17,
0, 248, 319, 185,
1, 640, 1407, 257,
2, 5632, 6655, 1025,
1, 13312, 15359, 2049,
2, 61440, 65535, 4097)
LOAD (old_pointer, $decompressed_pointer)
COPY-OFFSET ($distance_value, $index, $decompressed_pointer)
OUTPUT ($old_pointer, $index)
JUMP (character_after_match)
:end_of_message
END-MESSAGE (requested_feedback_location,
returned_parameters_location, state_length, 64,
decompress_sigcomp_message, 6, 0)
readonly (0)
:circular_bufferAnd here's an example of a message compressed with the modified DEFLATE algorithm 🌸
0xd956 b132 cd68 5424 c5a9 6215 8a70 a64d af0a 5499 3621 509b 3e4c
0x28b4 a145 b362 653a d0a6 498b 5a6d 2970 ac4c 930a a4ca 74a4 c268
0x0cThe uncompressed message is "Arthur leapt to his feet like an author hearing the phone ring". Literally the best plot twist of the whole section 📚💖
5. Additional SigComp Mechanisms ✨
okay so this section is the glow-up 💅 It covers the extra mechanisms SigComp can use to squeeze out a better compression ratio: acknowledgements, dictionaries, and sharing state between the two directions of a compressed message flow. 🦋
There's assembly code for these mechanisms too. Heads up though: depending on the mechanism and the basic algorithm you're using, the assembly for either one might need tweaking. For example, if your algorithm uses 'no more input' to jump to end_of_message, then putting an input instruction for CRC after end_of_message won't work. 🙈 These are examples, not the only way to do it. There could be other ways to make these mechanisms work, so get creative bestie 🌈
Once each of the compression algorithms from Section 4 has successfully decompressed the current SigComp message, the contents of the UDVM memory get saved as a SigComp state item. 💜 Later messages can reach that state item by uploading the right state identifier to the receiving endpoint, which means you don't have to upload the bytecode for the compression algorithm with every single message. Iconic. But first, the compressor needs to make sure the state is actually available at the receiving endpoint, bc otherwise it's giving nothing 💀
For each SigComp compartment, the receiving endpoint keeps a list of the states it currently has available. The total amount of saved state can't go over the state_memory_size for that compartment. The SigComp compressor should keep a similar list, containing the states it has told the receiving endpoint to save. 🎀
The compressor also tracks the state items it has saved at the remote endpoint, and it keeps a flag for each one that says whether the state can safely be accessed. State items should not be accessed until they've been acknowledged (for example, through the SigComp feedback mechanism in Section 5.1). 🫶
When a new piece of state needs to be added and the total state_memory_size for the compartment is already full, some state items get deleted from the list. Which ones? That's decided by age and retention priority, as discussed in SigComp [2]. The SigComp compressor should not try to access any state items that were deleted this way, because they may no longer be available at the receiving endpoint. Don't be that person 😭
5.1. Acknowledging a State Item
SigComp [2] defines a feedback mechanism that lets the compressor request feedback from the decompressor. This tells the compressor that a message has been received and correctly decompressed, and that state storage has been attempted. (Note: This mechanism cannot convey the success or failure of individual state creation requests.) 📝 To invoke the feedback mechanism, the following fields must be reserved in the UDVM memory:
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| reserved | Q | S | I | requested_feedback_location
+---+---+---+---+---+---+---+---+
| 1 | requested_feedback_length | if Q = 1
+---+---+---+---+---+---+---+---+
| |
: requested_feedback_field : if Q = 1
| |
+---+---+---+---+---+---+---+---+These fields can be reserved in any of the algorithms from Section 4. Just swap out the line "set (requested_feedback_location, 0)" for the following assembly:
:requested_feedback_location pad (1)
:requested_feedback_length pad (1)
:requested_feedback_field pad (12)
:hash_start pad (8)When a SigComp message is successfully decompressed and saved as state, the following bytecode tells the receiving endpoint to return the first 6 bytes of the matching state identifier. ✨ You can add this bytecode to any of the compression algorithms in Section 4, right after the ":end_of_message" label:
:end_of_message
set (hash_length, (state_length + 8))
LOAD (requested_feedback_location, 1158)
MULTILOAD (hash_start, 4, state_length, 64,
decompress_sigcomp_message, 6)
SHA-1 (hash_start, hash_length, requested_feedback_field)Then the receiving endpoint sends back the state identifier in the "returned feedback field" of the next SigComp message going the other way. 🦋
Once that state identifier comes back, the compressor can set the availability flag for the matching state to 1. Green light, go ahead and use it 🚦💖
5.2. Static Dictionary
Some protocols that SigComp can compress come with a fixed, mandatory state item called a static dictionary. 📖 It's a collection of text strings that show up a lot in messages from that protocol. If you pull those phrases from the static dictionary instead of uploading them as part of the compressed message, the overall compression ratio can often get better. Main character energy 👑
As an example, there's a static dictionary for the protocols SIP and SDP, from RFC 3485 [4]. It's designed to work with a wide range of compression algorithms, including every one covered in Section 4. 🌸
In any of the compression algorithms from Section 4, you can access the static dictionary by putting the following instruction right after the ":initialize_memory" label:
STATE-ACCESS (dictionary_id, 6, 0, 0, 1024, 0)The parameters of the STATE-ACCESS instruction depend on which compression algorithm you're using. ⚙️
The following lines should also go right after the END-MESSAGE instruction:
:dictionary_id
byte (0xfb, 0xe5, 0x07, 0xdf, 0xe5, 0xe6)After that, the text strings in the static dictionary can be accessed in exactly the same way as text strings from previously decompressed messages (see Section 5.1 for the details). 🧚
Also, in some cases it's enough to load only part of the static dictionary into UDVM memory. If you want more info on what's inside the SIP and SDP static dictionary, check out the relevant document, RFC 3485 [4]. 💜
5.3. CRC Checksum
The acknowledgement scheme in Section 5.1 is built to show that a message was decompressed successfully. 😬 But here's the tea: it doesn't guarantee the decompressed message matches the original. A corrupted message could still decompress "successfully" while some characters are wrong. That could mean an incorrect message gets passed up to the application, or unexpected contents get stored as state. Yikes. To stop that from happening, you can use a CRC check. 🔍
If you need an additional CRC check, you can insert the following bytecode after the ":end_of_message" label:
INPUT-BYTES (2, index, !)
CRC ($index, 64, state_length, !)This bytecode pulls a 2-byte CRC from the end of the SigComp message and compares it with a CRC calculated over the UDVM memory. If the two CRC values don't match, decompression fails. 💀
You can find the definition of the CRC polynomial used by the CRC instruction in SigComp [2]. 📚
5.4. Announcing Additional Resources
If an endpoint can offer more processing or memory resources than the mandatory minimum, it can use the SigComp feedback mechanism to announce that those resources are available to the remote endpoint. This may help improve the overall compression ratio between the two endpoints. 🚀
An endpoint can also advertise identifiers for any state it has that might be useful for the remote endpoint to reference. The remote endpoint can then use any of those states that it also knows about (meaning it knows what the contents are). For example, that could be a dictionary or shared mode state (see Section 5.5). 🫶
You can announce the values of the following SigComp parameters using the SigComp advertisement mechanism:
cycles_per_bitdecompression_memory_sizestate_memory_sizeSigComp_version- state identifiers
As SigComp explains, to announce these parameter values, the following fields must be reserved in the UDVM memory:
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| cpb | dms | sms | returned_parameters_location
+---+---+---+---+---+---+---+---+
| SigComp_version |
+---+---+---+---+---+---+---+---+
| length_of_partial_state_ID_1 |
+---+---+---+---+---+---+---+---+
| |
: partial_state_identifier_1 :
| |
+---+---+---+---+---+---+---+---+
: :
+---+---+---+---+---+---+---+---+
| length_of_partial_state_ID_n |
+---+---+---+---+---+---+---+---+
| |
: partial_state_identifier_n :
| |
+---+---+---+---+---+---+---+---+These fields can be reserved in any of the algorithms from Section 4. Swap the line "set (returned_parameters_location, 0)" for the following piece of assembly:
:adverts_len pad (1)
:adverts_len_lsb pad (1)
:returned_parameters_location pad (1)
:returned_sigcomp_version pad (1)
:state_ids pad (x)Here, x should be enough space for the number of state identifiers the endpoint wants to advertise. 🦋
When a SigComp message is successfully decompressed and saved as state, the following bytecode lets the receiving endpoint know that extra resources and pieces of state are available at the sending endpoint:
:end_of_message
LOAD (returned_parameters_location, N)
INPUT-BYTES (1, adverts_len_lsb, done)
INPUT-BYTES ($adverts_len, state_ids, done)
:doneThe integer value "N" should be set equal to the amount of resources available at the sending endpoint. N should be written as a 2-byte integer, where the most significant bits match the cycles_per_bit parameter and the least significant bits match the SigComp_version parameter. 🔢
The length of the state identifiers, followed by the state identifiers in the format shown above, gets appended to the end of the compressed message. 💅
5.5. Shared Compression
This section gives you the bytecode for the SigComp shared compression mechanism, from RFC 3321 [3]. 🤝 If two endpoints, A and B, are talking over SigComp, shared compression lets the messages Endpoint A sends to Endpoint B get compressed relative to the messages Endpoint B sends to Endpoint A (and the other way around). That can improve the overall compression ratio, because you don't have to send the same info in both directions. Smart, right? 🧠
As RFC 3321 [3] describes, there are two steps to implement shared compression at an endpoint. 📋
The first step is to tell the remote endpoint that shared compression is available. You do this by announcing the state identifier as an available piece of state, using the returned_parameters_location announcement from Section 5.4. 📣
The second step: once that announcement comes in from the remote endpoint, the state created by shared compression has to be accessed by the message sent in the opposite direction. You can do this similarly to how you access the static dictionary (see Section 5.2), just using the appropriate state identifier. For example, you can use the INPUT-BYTES instruction like this:
:shared_state_id pad (6)
:access_shared_state
INPUT-BYTES (6, shared_state_id, !)
STATE-ACCESS (shared_state_id, 6, 0, 0, $decompressed_start, 0)6. Security Considerations 🔒
okay bestie, this section is short but it matters. This document describes implementation options for the SigComp protocol [2], so the security considerations for this document are exactly the same as SigComp's. no cap, you get the whole security story by reading [2] 🫶
7. Acknowledgements 💖
shoutout to Richard Price, Carsten Bormann, Adam Roach, Lawrence Conroy, Christian Schmidt, Max Riegel, Lars-Erik Jonsson, Jonathan Rosenberg, Stefan Forsgren, Krister Svanbro, Miguel Garcia, Christopher Clanton, Khiem Le, Ka Cheong Leung, and Zoltan Barczikay for giving valuable input and review ✨
and a special big hug 🤗 to Pekka Pessi and Cristian Constantin, who were the committed working group document reviewers. literally the MVPs 👑
8. Intellectual Property Right Considerations 📜
the IETF has been notified of intellectual property rights claimed about some or all of the specification in this document. for more info, check the online list of claimed rights 🦋
9. Normative References 📚
[1] Crocker, D. and P. Overell, "Augmented BNF for Syntax Specifications: ABNF", RFC 4234, October 2005. 🌸
[2] Price, R., Bormann, C., Christoffersson, J., Hannu, H., Liu, Z., and J. Rosenberg, "Signaling Compression (SigComp)", RFC 3320, January 2003. 💅
[3] Hannu, H., Christoffersson, J., Forsgren, S., Leung, K.-C., Liu, Z., and R. Price, "Signaling Compression (SigComp) - Extended Operations", RFC 3321, January 2003. ✨
[4] Garcia-Martin, M., Bormann, C., Ott, J., Price, R., and A.B. Roach, "The Session Initiation Protocol (SIP) and Session Description Protocol (SDP) Static Dictionary for Signaling Compression (SigComp)", RFC 3485, February 2003. 🎀
[5] Ziv, J. and A. Lempel, "A universal algorithm for sequential data compression", IEEE 23:337-343, 1977. 🧚
[6] Storer, J., "Data Compression: Methods and Theory", Computer Science Press ISBN 0-88175-161-8, 1998. 🍓
[7] Nelson, M., "LZW Data Compression", Dr Dobb's Journal, October 1989. 🌈
[8] Deutsch, P., "DEFLATE Compressed Data Format Specification version 1.3", RFC 1951, May 1996. 💜
[9] "Data Compression Procedures", ITU-T Recommendation V.44, November 2000. 🦋
Appendix A. UDVM Bytecode for the Compression Algorithms 🧮
okay so these sections list the UDVM bytecode generated for each compression algorithm from Section 4. ngl it's giving main character energy ✨
different assemblers can output different bytecode for the same assembly code, so a valid assembler can produce results that look different from what's below. BUT the bytecode below should always generate the same decompressed messages on any UDVM. so the outputs match even when the bytes don't 💖
A.1. Well-known Algorithms 🌸
A.1.1. LZ77 💅
0x0f86 0389 8d89 1588 8800 011c 0420 0d13 5051 2222 5051 16f5 2300
0x00bf c086 a08b 06A.1.2. LZSS 🔥
0x0f86 04a0 c48d 00a0 c41e 2031 0209 00a0 ff8e 048c bfff 0117 508d
0x0f23 0622 2101 1321 0123 16e5 1d04 22e8 0611 030e 2463 1450 5123
0x2252 5116 9fd2 2300 00bf c086 a089 06A.1.3. LZW 🦋
0x0f86 06a1 ce8d 00b1 8f01 a0ce 13a0 4903 2313 2501 2506 1201 1752
0x88f4 079f 681d 0a24 2508 1203 0612 b18f 1252 0321 0ea0 4801 0624
0x5013 a049 0323 1351 5025 2251 5016 9fde 2300 00bf c086 a09f 06A.1.4. DEFLATE 🌈
0x0f86 7aa2 528d 05a2 5200 0300 0400 0500 0600 0700 0800 0900 0a01
0x0b01 0d01 0f01 1102 1302 1702 1b02 1f03 2303 2b03 3303 3b04 a043
0x04a0 5304 a063 04a0 7305 a083 05a0 a305 a0c3 05a0 e300 a102 0001
0x0002 0003 0004 0105 0107 0209 020d 0311 0319 0421 0431 05a0 4105
0xa061 06a0 8106 a0c1 07a1 0107 a181 08a2 0108 a301 09a4 0109 a601
0x0aa8 010a ac01 0bb0 010b b801 0c80 2001 0c80 3001 0d80 4001 0d80
0x6001 1d03 229f b41e 20a0 6504 0700 1780 4011 0130 a0bf 0000 a0c0
0xa0c7 8040 2901 a190 a1ff a090 1750 8040 1109 a046 1322 2101 1321
0x0123 169f d108 1004 1250 0422 1d51 229f d706 1251 1e20 9fcf 0105
0x001f 2f08 1004 1250 0426 1d53 26f6 0614 530e 2063 1454 5223 2250
0x5216 9f9e 2300 00bf c086 a1de 06A.1.5. LZJH 🧁
0x0f86 08a1 5b8d 0700 a15b 0706 b18f 1d01 24a0 c317 5201 1a31 311e
0x24a0 b802 0101 0102 0100 0100 1752 0107 a04e 1e1d 6524 f822 2501
0x0ea0 4602 13a0 4703 2713 2501 2416 9fcd 1d66 24e1 1752 03a0 639f
0xb808 0812 0306 12b1 8312 5203 210e a046 0106 2350 0e28 6713 a047
0x0327 1351 5024 2251 5016 9fa8 1e24 9fb1 0401 0101 0102 0103 0201
0x0101 0d03 0007 0517 520d 0d06 061d 0826 f706 1253 1351 5011 1351
0x5224 2251 5206 1250 1225 0154 169f 6617 5201 9fdb 070f 1c00 009e
0xce16 9f57 1d01 24fa 1752 0107 0d9e c206 2501 169f 6506 2601 169f
0x7623 0000 bfc0 86a0 8e06A.2. Adapted Algorithms 🎀
A.2.1. Modified DEFLATE 💖
0x0f86 04a1 d38d 00a1 d31e 20a1 4010 0500 0b2e 000c 0c88 011a 20a1
0x0101 a042 a044 2000 a045 a05e a061 00a0 5fa0 66a1 0800 a067 a067
0xa1ff 02a1 a0a1 aa23 00a1 aba1 d13a 00a1 d2a1 e1a1 1001 a3c4 a3e3
0xa120 03bf 20bf 34a0 7b00 bf35 bfb3 a180 0180 3f68 803f 8700 0080
0x3f88 803f c7a1 4001 807f 9080 7fff a090 1750 88a0 79a0 83a0 831e
0x20a0 c810 0400 00a1 ff01 0209 8801 1416 2000 171e a108 013e a049
0x2e00 a04a a059 a110 02a1 68a1 81a0 6100 a182 a1a1 a120 01a3 44a3
0x6a3a 00a3 6ba3 aaa1 4001 a756 a760 2300 a761 a7df a180 01af c0af
0xd4a0 7b01 bfaa bfc9 0001 803f 9480 3ffb a090 0180 7ff8 807f ffa0
0xf817 5088 0610 1022 2101 1321 0123 169f 1107 10a0 fd1e 229f d909
0x0900 0709 0008 3fa0 8101 87a0 8701 00a0 88a0 f711 00a0 f8a1 3fa0
0xb901 a280 a57f a101 02b6 00b9 ffa4 0101 8034 0080 3bff a801 0290
0x00ff b001 0e24 6314 5150 2322 5250 169f 3b23 0000 bfc0 86a0 8906Authors' Addresses 🏡
Abigail Surtees
Siemens/Roke Manor Research
Roke Manor Research Ltd.
Romsey, Hants SO51 0ZN
UK
Phone: +44 (0)1794 833131
EMail: abigail.surtees@roke.co.uk
URI: http://www.roke.co.ukMark A. West
Siemens/Roke Manor Research
Roke Manor Research Ltd.
Romsey, Hants SO51 0ZN
UK
Phone: +44 (0)1794 833311
EMail: mark.a.west@roke.co.uk
URI: http://www.roke.co.ukFull Copyright Statement ⭐
Copyright (C) The Internet Society (2006).
This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.
This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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.
Intellectual Property 🧠
The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org.
Acknowledgement 🌷
Funding for the RFC Editor function is provided by the IETF Administrative Support Activity (IASA). 💜
📦 where this page comes from
- ietf: rfc4464 2006-05
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms