RFC 3320
Signaling Compression (SigComp)
RFC 3320: Signaling Compression (SigComp) 🎀
okay bestie, this is RFC 3320, and it's giving Standards Track 💅 It's titled Signaling Compression (SigComp), it came from the Network Working Group, and it's dated January 2003. The authors are R. Price (Siemens/Roke Manor), C. Bormann (TZI/Uni Bremen), J. Christoffersson (Ericsson), H. Hannu (Ericsson), Z. Liu (Nokia), and J. Rosenberg (dynamicsoft). The header doesn't list any "Obsoletes" or "Updates" RFCs, so this one isn't replacing or changing anything else 🦋
Status of this Memo 📜
This document specifies an Internet standards track protocol for the Internet community, and it asks for discussion and suggestions for improvements. For the standardization state and status of this protocol, check the current edition of the "Internet Official Protocol Standards" (STD 1). Distribution of this memo is unlimited 🌸
Copyright Notice 🔒
Copyright (C) The Internet Society (2003). All Rights Reserved.
Abstract ✨
okay so the big idea is Signaling Compression (SigComp), a way to compress messages made by application protocols like the Session Initiation Protocol (SIP) (RFC 3261) and the Real Time Streaming Protocol (RTSP) (RFC 2326) 🎀 It outlines the architecture and prerequisites of SigComp, plus the format of the SigComp message.
Decompression is handled by a Universal Decompressor Virtual Machine (UDVM), which is optimized for running decompression algorithms. It can be set up to understand the output of lots of well-known compressors, like DEFLATE (RFC-1951) 🧚
Table of Contents 🗂️
1. Introduction...................................................2
2. Terminology....................................................3
3. SigComp architecture...........................................5
4. SigComp dispatchers...........................................15
5. SigComp compressor............................................18
6. SigComp state handler.........................................20
7. SigComp message format........................................23
8. Overview of the UDVM..........................................28
9. UDVM instruction set..........................................37
10. Security Considerations.......................................56
11. IANA Considerations...........................................58
12. Acknowledgements..............................................59
13. References....................................................59
14. Authors' Addresses............................................60
15. Full Copyright Statement......................................621. Introduction ✨
so a lot of the application protocols used for multimedia calls are text-based and were built for bandwidth-rich links 🌈 That means the messages were never really optimized for size. For example, typical SIP messages run from a few hundred bytes up to two thousand bytes or more [RFC3261].
This is where it gets messy 😭 With the planned use of these protocols in wireless handsets as part of 2.5G and 3G cellular networks, those big message sizes are a real problem. Low-rate IP connectivity means transmission delays get significant. Add in retransmissions and the number of messages some flows need, and call setup and feature invocation take a hit.
SigComp fixes this by offering robust, lossless compression of application messages 💖
This document walks through the architecture and prerequisites of the SigComp solution, the format of the SigComp message, and the Universal Decompressor Virtual Machine (UDVM) that handles decompression 🦋
SigComp sits as a layer between the application and an underlying transport. The service it gives you is that transport plus compression. It supports a wide range of transports, including TCP, UDP and SCTP [RFC-2960] 🫶
2. Terminology 💅
okay the key words here are "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL". In this document, they're interpreted as described in BCP 14, RFC 2119 [RFC-2119]. It's the official rulebook for these words, so use it 📖
Now the vocab list, bestie 🌸
Application
Entity that invokes SigComp and performs the following tasks:
- Supplying application messages to the compressor dispatcher
- Receiving decompressed messages from the decompressor dispatcher
- Determining the compartment identifier for a decompressed message.
Bytecode
Machine code that can be executed by a virtual machine.
Compressor
Entity that encodes application messages using a certain compression algorithm, and keeps track of state that can be used for compression. The compressor is responsible for ensuring that the messages it generates can be decompressed by the remote UDVM 🎀
Compressor Dispatcher
Entity that receives application messages, invokes a compressor, and forwards the resulting SigComp compressed messages to a remote endpoint.
UDVM Cycles
A measure of the amount of "CPU power" required to execute a UDVM instruction. The simplest UDVM instructions require a single UDVM cycle. An upper limit is placed on the number of UDVM cycles that can be used to decompress each bit in a SigComp message ⚡
Decompressor Dispatcher
Entity that receives SigComp messages, invokes a UDVM, and forwards the resulting decompressed messages to the application.
Endpoint
One instance of an application, a SigComp layer, and a transport layer for sending and/or receiving SigComp messages.
Message-based Transport
A transport that carries data as a set of bounded messages.
Compartment
An application-specific grouping of messages that relate to a peer endpoint. Depending on the signaling protocol, this grouping may relate to application concepts such as "session", "dialog", "connection", or "association". The application allocates state memory on a per-compartment basis, and decides when a compartment should be created or closed 🧚
Compartment Identifier
An identifier (in a locally chosen format) that uniquely references a compartment.
SigComp
The overall compression solution, made up of the compressor, UDVM, dispatchers and state handler 💜
SigComp Message
A message sent from the compressor dispatcher to the decompressor dispatcher. With a message-based transport such as UDP, a SigComp message corresponds to exactly one datagram. For a stream-based transport such as TCP, the SigComp messages are separated by reserved delimiters 🦋
Stream-based transport
A transport that carries data as a continuous stream with no message boundaries.
Transport
Mechanism for passing data between two endpoints. SigComp is capable of sending messages over a wide range of transports, including TCP, UDP and SCTP [RFC-2960].
Universal Decompressor Virtual Machine (UDVM)
The machine architecture described in this document. The UDVM is used to decompress SigComp messages 🌈
State
Data saved for retrieval by later SigComp messages.
State Handler
Entity responsible for accessing and storing state information once permission is granted by the application.
State Identifier
Reference used to access a previously created item of state.
3. SigComp Architecture ✨
okay so bestie, this is where SigComp gets its whole vibe 💅 compression and decompression happen at two communicating endpoints, and the layout of a single endpoint is shown in Figure 1 🦋
+-------------------------------------------------------------------+
| |
| Local application |
| |
+-------------------------------------------------------------------+
| ^ |
Application message & | Decompressed | | Compartment
compartment identifier | message | | identifier
| | |
+-- -- -- -- -- -- -- --|-- -- -- -- -- -- -- --|--|-- -- -- -- -- -+
v | v
| +------------------------+ +----------------------+ |
| | | |
| +--| Compressor | | Decompressor |<-+ |
| | dispatcher | | dispatcher | |
| | | | | | | |
| +------------------------+ +----------------------+ |
| | ^ ^ ^ | |
| | | | |
| | | v | | |
| | +--------------+ +---------------+ | |
| | | | | | +-------+ | v | |
| | | Compressor 1 |<----->|State 1| | +--------------+ |
| | | | | | +-------+ | | | | |
| | +--------------+ | | | Decompressor | |
| | | | State handler |<-->| | | |
| | +--------------+ | | | (UDVM) | |
| | | | | | +-------+ | | | | |
| +->| Compressor 2 |<----->|State 2| | +--------------+ |
| | | | | +-------+ | | |
| +--------------+ +---------------+ SigComp layer |
| | | |
+-| -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --|-+
| |
| SigComp SigComp |
| message message |
v |
+-------------------------------------------------------------------+
| |
| Transport layer |
| |
+-------------------------------------------------------------------+Figure 1: High-level architectural overview of one SigComp endpoint
Note that SigComp is offered to applications as a layer between the application and the underlying transport, so Figure 1 is an endpoint when viewed from a transport layer perspective 🌸 From the perspective of multi-hop application layer protocols however, SigComp is applied on a per-hop basis 🧚
The SigComp layer is further decomposed into the following entities 👑
- Compressor dispatcher - the interface from the application. The application supplies the compressor dispatcher with an application message and a compartment identifier (see Section 3.1 for further details). The compressor dispatcher invokes a particular compressor, which returns a SigComp message to be forwarded to the remote endpoint.
- Decompressor dispatcher - the interface towards the application. The decompressor dispatcher receives a SigComp message and invokes an instance of the Universal Decompressor Virtual Machine (UDVM). It then forwards the resulting decompressed message to the application, which may return a compartment identifier if it wishes to allow state to be saved for the message.
- One or more compressors - the entities that convert application messages into SigComp messages. Distinct compressors are invoked on a per-compartment basis, using the compartment identifiers supplied by the application. A compressor receives an application message from the compressor dispatcher, compresses the message, and returns a SigComp message to the compressor dispatcher. Each compressor chooses a certain algorithm to encode the data (e.g., DEFLATE) 🍓
- UDVM - the entity that decompresses SigComp messages. Note that since SigComp can run over an unsecured transport layer, a separate instance of the UDVM is invoked on a per-message basis. However, during the decompression process the UDVM may invoke the state handler to access existing state or create new state 💜
- State handler - the entity that can store and retrieve state. State is information that is stored between SigComp messages, avoiding the need to upload the data on a per-message basis. For security purposes it is only possible to create new state with the permission of the application. State creation and retrieval are further described in Chapter 6 🔥
When compressing a bidirectional application protocol, the choice to use SigComp can be made independently in both directions, and compression in one direction does not necessarily imply compression in the reverse direction. Moreover, even when two communicating endpoints send SigComp messages in both directions, there is no need to use the same compression algorithm in each direction 🎀
Note that a SigComp endpoint can decompress messages from multiple remote endpoints at different locations in a network, as the architecture is designed to prevent SigComp messages from one endpoint interfering with messages from a different endpoint. A consequence of this design choice is that it is difficult for a malicious user to disrupt SigComp operation by inserting false compressed messages on the transport layer 🛡️ it's giving secure, no cap 🫶
3.1. Requirements on the Application
From an application perspective, the SigComp layer appears as a new transport, with similar behavior to the original transport used to carry uncompressed data (for example, SigComp/UDP behaves similarly to native UDP) 🦋
Mechanisms for discovering whether an endpoint supports SigComp are beyond the scope of this document 🙈
All SigComp messages contain a prefix (the five most-significant bits of the first byte are set to one) that does not occur in UTF-8 encoded text messages [RFC-2279], so for applications which use this encoding (or ASCII encoding) it is possible to multiplex uncompressed application messages and SigComp messages on the same port. Applications can still reserve a new port specifically for SigComp however (e.g., as part of the discovery mechanism) ✨
If a particular endpoint wishes to be stateful, then it needs to partition its decompressed messages into "compartments" under which state can be saved. SigComp relies on the application to provide this partition. So for stateful endpoints, a new interface is required to the application in order to leverage the authentication mechanisms used by the application itself 💖
When the application receives a decompressed message, it maps the message to a certain compartment and supplies the compartment identifier to SigComp. Each compartment is allocated a separate compressor and a certain amount of memory to store state information, so the application must assign distinct compartments to distinct remote endpoints. However, it is possible for a local endpoint to establish several compartments that relate to the same remote endpoint (this should be avoided where possible as it may waste memory and reduce the overall compression ratio, but it does not cause messages to be incorrectly decompressed). In this case, reliable stateful operation is possible only if the decompressor does not lump several messages into one compartment when the compressor expected them to be assigned different compartments 🧠
The exact format of the compartment identifier is unimportant provided that different identifiers are given to different compartments 🌈
Applications that wish to communicate using SigComp in a stateful fashion should use an authentication mechanism to securely map decompressed messages to compartment identifiers. They should also agree on any limits to the lifetime of a compartment, to avoid the case where an endpoint accesses state information that has already been deleted 😭 bestie, that last bit is so important, don't skip it fr fr
3.2. SigComp feedback mechanism ✨
okay so bestie, this part is lowkey my favourite 🫶 If a signaling protocol sends SigComp messages in both directions and each application on both ends has its own compartment, paired one-to-one (those are called "peer compartments" 🦋), the two endpoints can team up way more closely. Now they can send feedback that keeps an eye on how an endpoint is behaving and helps the overall compression ratio get better 📈 SigComp does feedback as a request and response thing, so a compressor asks for feedback and gets some feedback data back. Here's the whole flow in Figure 2 🎀
+---------------------+ +---------------------+
| +-----------------+ | | +-----------------+ |
-->| Compressor |------------------------>| UDVM |<->
| | sending to B | | SigComp message | | | |2
| +-----------------+ | requesting feedback | +-----------------+ |
| ^ 1,9 | | 3 | |
| | | | v |
| +-----------------+ | | +-----------------+ |
| | State | | | | State | |
| | handler | | | | handler | |
| +-----------------+ | | +-----------------+ |
| ^ 8 | | 4 | |
| | | | v |
| +-----------------+ | | +-----------------+ |
| | UDVM | | | | Compressor | |
<->| |<------------------------| sending to A |<--
6| +-----------------+ | SigComp message | +-----------------+ |
| 7 | returning feedback | 5 |
| Endpoint A | | Endpoint B |
+---------------------+ +---------------------+
Figure 2: Steps involved in the transmission of feedback datangl the dispatchers, the application and the transport layer got left out of the diagram so it stays clean 💅 Just know that decompressed messages go through the decompressor dispatcher to the application 🌸 And SigComp messages heading from the compressor to the remote UDVM go through the compressor dispatcher first, then the transport layer, and finally the decompressor dispatcher 🧚
Here are the steps for asking for and sending back feedback, in more detail 💖
- The compressor that sends messages to Endpoint B piggybacks a feedback request onto a SigComp message. 🦋
- When the application receives the decompressed message, it may return the compartment identifier for the message.
- The UDVM in Endpoint B forwards the requested feedback data to the state handler.
- If the UDVM can supply a valid compartment identifier, then the state handler forwards the feedback data to the appropriate compressor (namely the compressor sending to Endpoint A).
- The compressor returns the requested feedback data to Endpoint A piggybacked onto a SigComp message. ✨
- When the application receives the decompressed message, it may return the compartment identifier for the message.
- The UDVM in Endpoint A forwards the returned feedback data to the state handler.
- If the UDVM can supply a valid compartment identifier, then the state handler forwards the feedback data to the appropriate compressor (namely the compressor sending to Endpoint B).
- The compressor makes use of the returned feedback data. 👑
The detailed role each entity plays in sending feedback gets explained in the later chapters 🌈
3.3. SigComp Parameters 🎀
the best part about using a virtual machine for decompression is that almost all the implementation flexibility lives on the SigComp compressor side 🧚 When an endpoint receives SigComp messages, it generally acts in a predictable way 💜
BUT (and this is a big but 😭) endpoints that implement SigComp usually have a wide range of capabilities, each with a different amount of working memory, processing power, etc. So to handle all that variation, the following parameters are provided to change how SigComp behaves when it receives SigComp messages:
- decompression_memory_size
- state_memory_size
- cycles_per_bit
- SigComp_version
- locally available state (a set containing 0 or more state items)
Each parameter has a minimum value that MUST be offered by all receiving SigComp endpoints. Endpoints MAY also offer extra resources if they have them, and those resources can be advertised to remote endpoints using the SigComp feedback mechanism 🌸
Particular applications may also agree ahead of time to offer additional resources as mandatory. For example, SigComp for SIP offers a dictionary of common SIP phrases as a mandatory state item 🍓
Each of the SigComp parameters gets a closer look below 👀
3.3.1. Memory Size and UDVM Cycles 💅
The decompression_memory_size parameter tells you how much memory is available to decompress one SigComp message. (Quick note: "amount of memory" is used conceptually here, to describe how the decompressor behaves and to help the compressor plan its resources. An implementation could need some extra, bounded amount of real memory, or it could even organize its memory in a totally different way, as long as that doesn't cause decompression failures where the conceptual model wouldn't. 🙈) A portion of this memory is used to buffer a SigComp message before it gets decompressed, and the rest goes to the UDVM. The memory is allocated per message and can be reclaimed once that message has been decompressed. All endpoints implementing SigComp MUST offer a decompression_memory_size of at least 2048 bytes 🔥
The state_memory_size parameter is the number of bytes offered to a particular compartment for creating state. It's set to 0 if the endpoint is stateless 🦋
Unlike the other SigComp parameters, state_memory_size is offered per compartment, so it can be different for different compartments 🌈 A compartment's memory gets reclaimed when the application decides that compartment isn't needed anymore 🧹
The cycles_per_bit parameter tells you how many "UDVM cycles" are available to decompress each bit of a SigComp message. Running a UDVM instruction costs a certain number of UDVM cycles. You can find the full list of UDVM instructions and what they cost in cycles in Chapter 9 📖 An endpoint MUST offer a minimum of 16 cycles_per_bit ✨
Each of the three parameter values MUST be picked from the limited set below, so the parameters can be encoded efficiently for transmission using the SigComp feedback mechanism 💖
The cycles_per_bit parameter is encoded with 2 bits, while decompression_memory_size and state_memory_size are each encoded with 3 bits. The bit encodings and their values look like this:
Encoding: cycles_per_bit: Encoding: state_memory_size (bytes):
00 16 000 0
01 32 001 2048
10 64 010 4096
11 128 011 8192
100 16384
101 32768
110 65536
111 131072decompression_memory_size is encoded the same way as state_memory_size, except that the bit pattern 000 can't be used, because an endpoint can't offer a decompression_memory_size of 0 bytes 🙅♀️
3.3.2. SigComp Version 🌸
The SigComp_version parameter says whether only the basic version of SigComp is available, or whether an upgraded version is too, with extra instructions and such 🧚 Inside the UDVM, it shows up as a 2-byte value, made by zero-extending the 1-byte SigComp_version parameter. In other words, the first byte of that 2-byte value is always zero 🔢
The basic version of SigComp is Version 0x01, which is the version described in this document 💜
To keep things backwards compatible: if a SigComp message gets successfully decompressed by Version 0x01 of SigComp, then it will also be successfully decompressed on upgraded versions. Likewise, if the message triggers a manual decompression failure (see Section 8.7), then it will keep doing that too 🫶
Messages that cause an unexpected decompression failure on Version 0x01 of SigComp might still get successfully decompressed by upgraded versions though 🌈
the simplest way to upgrade SigComp in a backwards-compatible way is to add extra UDVM instructions, since that won't change how SigComp messages that work with Version 0x01 get decompressed 💅 Reserved addresses in the UDVM memory (Useful Values, see Section 7.2) may also get assigned values in future versions of SigComp 🎀
3.3.3. Locally Available State Items 🧚✨
okay so bestie, a SigComp state item is basically a little chunk of data that sticks around between SigComp messages 💅 and it can get pulled into UDVM memory during decompression. this is lowkey huge for compression ratio because the same info doesn't have to get re-uploaded in every single message 🫶 it's giving efficiency, no cap.
each endpoint keeps a set of state items, and every item has these fields:
Name: Type of data:
state_identifier 20-byte value
state_length 2-byte value
state_address 2-byte value
state_instruction 2-byte value
minimum_access_length 2-byte value from 6 to 20 inclusive
state_value String of state_length consecutive bytesstate items usually get created at an endpoint once a SigComp message decompresses successfully 🎀 the remote compressor makes a state creation request by invoking the right UDVM instruction, and the state only gets saved once the application gives permission ✨ very much a "ask before you save" kinda vibe 🌸
now here's the twist 🙈 an endpoint MAY also want to offer a set of locally available state items that were never uploaded as part of a SigComp message 🦋 like well-known decompression algorithms, or dictionaries of common phrases used in a specific signaling protocol, etc. 💜
because these get set up locally without any input from a remote endpoint, they're most useful when they're publicly documented 📚 that way a wide range of remote endpoints can figure out what's inside each item and how to use it. further Internet Documents and RFCs may be published to describe particular locally available state items 🌈
no locally available state item is mandatory for every SigComp endpoint 💀 BUT certain state items can be made mandatory in a specific environment (e.g., the dictionary of common phrases for a specific signaling protocol could be made mandatory for that signaling protocol's usage of SigComp) 🔥 and remote endpoints can show interest in getting a list of some of the locally available state items at an endpoint through the SigComp feedback mechanism ✨
it is a local decision what locally available state an endpoint advertises 👑 this choice has no influence on interoperability, but it may increase or decrease how efficient the compression is between the endpoints 🍓
4. SigComp Dispatchers 💖
okay this chapter defines how the compressor and decompressor dispatchers behave 🫶 their whole job is to be the interface between SigComp and its environment, so integrating SigComp into an existing protocol stack is way less effort 💅✨
4.1. Compressor Dispatcher 🎀
the compressor dispatcher gets messages from the application and passes the compressed version of each message down to the transport layer 🦋
quick note 📝 SigComp runs compressors per compartment 💜 so when the application hands over a message to compress, it also has to provide a compartment identifier 🧚 the compressor dispatcher then forwards that message to the correct compressor based on the compartment identifier, and if it sees a brand new compartment identifier it invokes a new compressor for it 🌸 the compressor returns a SigComp message that can be passed to the transport layer ✨
also, the application should tell the compressor dispatcher when it wants to close a particular compartment 🙈 that way the resources the compressor was using can be reclaimed 🔥
4.2. Decompressor Dispatcher 💜
the decompressor dispatcher receives messages from the transport layer and passes the decompressed version of each message up to the application 🦋
so SigComp can run over an unsecured transport layer 🔐 the decompressor dispatcher invokes a new instance of the UDVM for every new SigComp message 💅 and the UDVM resources get released as soon as that message is decompressed 🫶
the dispatcher MUST NOT make more than one SigComp message available to a given instance of the UDVM 💀 and it MUST NOT concatenate two SigComp messages into one message 💀 absolutely not, bestie 🙅♀️
4.2.1. Decompressor Dispatcher Strategies 🌈
once the UDVM is invoked, it gets initialized using the SigComp message of Chapter 7 🧚 then the UDVM decompresses the message, hands it back to the decompressor dispatcher, and the dispatcher passes it on to the receiving application 🎀 the UDVM has zero awareness of whether the transport is message-based or stream-based, so it always outputs decompressed data as a stream 🌊 it's the dispatcher's responsibility to give the application the decompressed message in the form it expects, either as a stream or as a distinct, bounded message ✨ the dispatcher knows a decompressed message has ended when the UDVM instruction END-MESSAGE is invoked (see Section 9.4.9) 💖
for a stream-based transport, there are two strategies the decompressor dispatcher can use 👑
- the dispatcher collects a complete SigComp message and then invokes the UDVM 💅 the upside is that, even in implementations with multiple incoming compressed streams, only one instance of the UDVM is ever needed 🫶
- the dispatcher collects the SigComp header (see Section 7) and invokes the UDVM 🦋 the UDVM stays active while the rest of the message arrives 🌸 the upside is no need to buffer the rest of the message, since it can be decompressed as it arrives and any decompressed output can go to the application right away 🔥
in general, which strategy gets used is an implementation choice 🍓
BUT the compressor may want to take advantage of strategy 2 🧚 by expecting that some of the application message gets passed on to the application before the SigComp message ends 💜 for example, by keeping the UDVM active while the application keeps receiving decompressed output 🌈 this approach is called "continuous mode" 🙈 and it invalidates some assumptions of the SigComp security model, so it can only be used if the transport itself can provide the required protection against denial of service attacks 💀 also, since only strategy 2 works with this approach, using continuous mode requires previous agreement between the two endpoints 🤝✨
4.2.2. Record Marking 🎀
for a stream-based transport, the dispatcher splits messages apart by parsing the compressed data stream for instances of 0xFF and taking the following actions 🦋
Occurs in data stream: Action:
0xFF 00 one 0xFF byte in the data stream
0xFF 01 same, but the next byte is quoted (could
be another 0xFF)
: :
0xFF 7F same, but the next 127 bytes are quoted
0xFF 80 to 0xFF FE (reserved for future standardization)
0xFF FF end of SigComp messagethe combinations 0xFF01 to 0xFF7F are useful for limiting the worst case expansion of the record marking scheme 💅 the 1 (0xFF01) to 127 (0xFF7F) bytes after the combination get copied literally by the decompressor, without any special action on 0xFF 🫶 (note that 0xFF00 is just a special case of this, where zero following bytes are copied literally 🙈)
in UDVM version 0x01, any occurrence of the combinations 0xFF80 to 0xFFFE that aren't protected by quoting causes decompression failure 😭 and the decompressor SHOULD close the stream-based transport in this case 💀
4.3. Returning a Compartment Identifier 🧚
after receiving a decompressed message, the application may give the dispatcher a compartment identifier ✨ supplying this identifier grants permission for two things 👑
- state items that come with the decompressed message can be saved in the state memory reserved for that compartment 💖
- the feedback data that comes with the decompressed message can be trusted enough to be used when sending SigComp messages related to the compressor's equivalent for that compartment 🌸
the dispatcher passes the compartment identifier to the UDVM, where it gets used as part of the END-MESSAGE instruction (see Section 9.4.9) 🦋
the application uses a suitable authentication mechanism to figure out whether the decompressed message belongs to a legitimate compartment 🔐 if the application can't authenticate the message with enough confidence to save state or trust feedback data, it gives the dispatcher a "no valid compartment" error 🙅♀️ and the UDVM is terminated without creating any state or forwarding any feedback data 😭
5. SigComp Compressor ✨
okay bestie so the big flex of SigComp is that decompression is handled by a Universal Decompressor Virtual Machine (UDVM) 🧚. that means the compressor can literally pick ANY algorithm it wants to squish a message, and then it uploads the bytecode for the matching decompression algorithm right inside the SigComp message 💅 main character energy fr.
to help people implement and test a SigComp endpoint, more Internet Documents and RFCs may get published describing particular compression algorithms 📚🫶
the overall vibe the compressor has to follow is transparency 🪞. the compressor MUST NOT send bytecode that makes the UDVM decompress a SigComp message incorrectly 😭 no cap, that's the whole rule.
there are also some more specific requirements (they're basically different flavors of transparency 💖):
- for robustness, it is recommended that the compressor supply some kind of integrity check (not necessarily cryptographic strength) over the application message, so that successful decompression has actually happened 🔍. there's a UDVM instruction for CRC verification, and another instruction can be used to compute a SHA-1 cryptographic hash 🧮
- the compressor MUST make sure the message can be decompressed using the resources available at the remote endpoint 🎀
- if the transport is message-based, the compressor MUST map each application message to exactly one SigComp message 📦
- if the transport is stream-based but the application defines its own internal message boundaries, the compressor SHOULD map each application message to exactly one SigComp message 🌸
message boundaries should be preserved over a stream-based transport so that accidental or malicious damage to one SigComp message does not affect the decompression of subsequent messages 🛡️ (ngl this one is so important)
also, if the state handler passes along some requested feedback to the compressor, it SHOULD be returned in the next SigComp message the compressor generates. the only exception is if the state handler passes newer requested feedback before the older feedback has been sent, because then the older feedback gets deleted 🗑️
if there's a requested feedback item, it SHOULD be copied unmodified into the returned_feedback_item field provided in the SigComp message 💅. and there's no need to send any requested feedback item more than once 🙅♀️ efficient queen behavior
the compressor SHOULD also upload the local SigComp parameters to the remote endpoint, unless the endpoint has said it doesn't want them, or the compressor works out that the parameters already arrived successfully (see Section 5.1 for how that can be achieved) ✨. the parameters get uploaded into the UDVM memory at the remote endpoint the way Section 9.4.9 describes 🧚
5.1. Ensuring Successful Decompression
okay this part is giving "be certain or don't bother" energy 🫣. the compressor MUST be certain that all of the data needed to decompress a SigComp message is available at the receiving endpoint. one way to guarantee that is to send all of the needed info in every SigComp message (bytecode to decompress the message included). the catch? the compression ratio for this method is pretty low 📉
to get the best overall compression ratio, the compressor needs to request the creation of new state items at the remote endpoint 🧠. the info saved in these state items can then be accessed by later SigComp messages, so you don't have to upload the data on every single message ✨ galaxy brain move
before the compressor can access saved state, though, it must make sure the SigComp message carrying the state creation request arrived successfully at the receiving endpoint 📬. for a reliable transport (like TCP or SCTP) this is guaranteed 🙌. for an unreliable transport, though, the compressor must provide a suitable mechanism itself (see [RFC-3321] for more details) 🫠
the compressor also must make sure the state item it wants to access hasn't been rejected because of a lack of state memory. it can check this by looking at the state_memory_size parameter using the SigComp feedback mechanism (see Section 9.4.9 for further details) 👀
5.2. Compression Failure
the compressor SHOULD make every effort to successfully compress an application message 💪, but sometimes that just isn't possible (especially when resources are scarce at the receiving endpoint). in that case, a "compression failure" is called 💀
if a compression failure happens, the compressor informs the dispatcher and takes no further action 🤷♀️. the dispatcher MUST report this failure to the application so the app can try other methods to deliver the message 📣
6. State Handling and Feedback 🫧
this chapter defines how the SigComp state handler behaves 🧁. its job is to hold onto information between received SigComp messages. it is the only SigComp entity that can do this, which is why it's a really big deal from a security perspective 🔐👑
6.1. Creating and Accessing State
so, to protect against malicious insertion or modification of SigComp messages, a separate instance of the UDVM gets invoked to decompress each message 🛡️. this way, damaged SigComp messages can't stop later valid messages from decompressing successfully 💖
BUT the overall compression ratio is often way higher if messages can be compressed relative to info from previous messages 📈. that's why it's possible to create state items for access while a later message is being decompressed ✨. both creating and accessing state are designed to be secure against malicious tampering with the compressed data 🔒. the UDVM can only create a state item once a complete message has been successfully decompressed AND the application has returned a compartment identifier under which the state can be saved 🗂️
state access can't be protected by relying on the application alone, since the authentication mechanism may need info from the decompressed message (which obviously isn't available until after the state has been accessed) 🙃. so instead, SigComp protects state access by creating a state identifier that is a hash over the item of state to be retrieved 🧾. this state_identifier must be supplied to retrieve an item of state from the state handler 🔑
also, state is not deleted when it's accessed 👏. so even if a malicious sender manages to access some state info, later messages compressed relative to that state can still be decompressed successfully 🙌
each state item contains a state_identifier that's used to access the state 🪪. one state identifier can be supplied in the SigComp message header to initialize the UDVM (see Chapter 7), and additional state items can be retrieved using the STATE-ACCESS instruction 🧚. the UDVM can also request the creation of a new state item by using the STATE-CREATE and END-MESSAGE instructions (see Chapter 9 for further details) 💅
6.2. Memory Management 🧠
okay so the state handler is basically the bouncer of state memory 💅 and it keeps track of everything on a per-compartment basis. Each compartment gets its own cap, called state_memory_size, and the application can give different compartments different values for it. Bestie, that's giving flexibility 🦋
The state handler doesn't just store the state items. It also keeps a list of which state items each compartment created, and it makes sure no compartment goes over its state_memory_size. For the math, every state item costs state_length + 64 bytes. So the 64 is like a flat fee per item, lowkey 😭
Each UDVM instance can send up to four state creation requests to the state handler, plus up to four state free requests. A free request basically says "please free the memory for this state item in this compartment" 🧹 When the state handler gets a creation request from the UDVM, it goes through these steps:
- The state handler MUST reject all state creation requests that don't come with a valid compartment identifier, or if the compartment has been given 0 bytes of state memory. Heads up though: if a creation request fails because there isn't enough state memory, that does NOT mean the SigComp message is damaged 🙈 Compressors often make creation requests in the very first SigComp message of a compartment, before they've figured out the
state_memory_sizethrough the SigComp feedback mechanism. Totally normal, no cap. - If the creation request needs more state memory than the compartment's total
state_memory_size, the state handler deletes everything except the first (state_memory_size - 64) bytes of thestate_value. It then setsstate_lengthto (state_memory_size - 64) and recalculates thestate_identifieras defined in Section 9.4.9 ✨ - If the creation request has a
state_identifierthat already exists, the state handler checks whether the requested state item is identical to the one already there. If it is, the request counts as successful 🎉 If it isn't, the request is unsuccessful. (This is only going to happen with a vanishingly small probability, so don't stress 💀) - If the creation request goes over the state memory allocated to the compartment, the state handler frees enough state items created by that same compartment until there's room for the new state. When a state item gets freed, it's removed from the compartment's list, and its memory cost stops counting toward the compartment's total. Here's the tea though: identical state items can be created by several different compartments, so a state item must not be physically deleted unless the state handler figures out that no compartment needs it anymore 👀
- The order of freeing is decided by
state_retention_priority, which gets set when the state items are created. Astate_retention_priorityof65535is reserved for locally available states, and those always get freed first, no exceptions 🫶 Apart from that special case, the state items with the loweststate_retention_priorityget freed first. If there's a tie, the state item that was created first in the compartment is the first one to go.
The state_retention_priority is always stored per compartment, as part of the list of state items each compartment created. That means the same state item might end up with several priority values if several compartments created it. Iconic multitasking 👑
Quick reminder that locally available state items (see Section 3.3.3) don't have to belong to any particular compartment. But if they are created per compartment, they must not mess with the state the remote endpoint asked for. That's exactly why 65535 is reserved for them 🌈
The UDVM can also ask the state handler to free one specific state item in a compartment. When that happens, the state handler removes the item from the compartment's list. As before, the item itself must not be physically deleted unless the state handler decides no compartment needs it anymore 🍓
Finally, the application should tell the state handler when it wants to close a compartment, so the resources held by that compartment's state can be reclaimed. Clean up after yourself, bestie 🧚
6.3. Feedback Data 💌
The SigComp feedback mechanism lets a UDVM receive feedback data and then pass it along, through the state handler, to the right compressor. Slay routing 🦋
This feedback data sticks around between SigComp messages, so it counts as part of the overall state. That means it can only be forwarded if it comes with a valid compartment identifier. When it does, the state handler forwards the feedback to the compressor that's responsible for sending messages to the peer compartment of the specified compartment. Everyone gets their message ✨
7. SigComp Message Format 📨
This chapter is all about what a SigComp message looks like and how that message sets up the UDVM memory 🎀
Here's a fun detail: the SigComp message doesn't get copied into UDVM memory the second it arrives. Instead, the UDVM says when it needs compressed data, using a specific instruction. Then it pauses and waits for that info before running the next instruction. So the UDVM can start decompressing before the whole message has even arrived. Main character energy 💅
Because of that, the UDVM memory size depends on whether the transport is stream-based or message-based when the UDVM gets invoked. If the transport is message-based, there has to be enough memory to buffer the whole SigComp message before it's handed to the UDVM. So if the message is n bytes long, the UDVM memory size is set to (decompression_memory_size - n), capped at a maximum of 65536 bytes 🧮
If the transport is stream-based, though, you need a fixed-size input buffer to hold the stream, no matter how big each SigComp message is. To keep things simple, the UDVM memory size is set to (decompression_memory_size / 2) in that case 🌸
A separate UDVM instance gets invoked for every message, so each SigComp message has to say explicitly which decompression algorithm it's using. It also needs to include any extra info required to decompress it, like one or more previously received messages, or a dictionary of common SIP phrases. That info can either be uploaded as part of the SigComp message, or it can be pulled from an item of state 🧚
A SigComp message comes in one of two forms, depending on whether it accesses a state item at the receiving endpoint. Both variants are shown in Figure 3. (The T-bit controls the format of the returned feedback item, and you can read all about it in Section 7.1 🫶)
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| 1 1 1 1 1 | T | len | | 1 1 1 1 1 | T | 0 |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | |
: returned feedback item : : returned feedback item :
| | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | code_len |
: partial state identifier : +---+---+---+---+---+---+---+---+
| | | code_len | destination |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | |
: remaining SigComp message : : uploaded UDVM bytecode :
| | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| |
: remaining SigComp message :
| |
+---+---+---+---+---+---+---+---+Figure 3: Format of a SigComp message 🍑
Decompression failure happens if the SigComp message is too short to hold the fields it's supposed to have (see Section 8.7 for the deets 🙈).
Every field except for the "remaining SigComp message" is called the "SigComp header". (Heads up, the header can also include uploaded UDVM bytecode 👀)
7.1. Returned feedback item 🔁
For both variants of the SigComp message, the T-bit gets set to 1 whenever the message includes a returned feedback item. The layout of that item is in Figure 4 💖
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| 0 | returned_feedback_field | | 1 | returned_feedback_length |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| |
: returned_feedback_field :
| |
+---+---+---+---+---+---+---+---+Figure 4: Format of returned feedback item 🌿
Here's the vibe: the returned_feedback_length tells you how big the returned_feedback_field is, anywhere from 0 to 127 bytes. So the whole returned feedback item is somewhere between 1 and 128 bytes long 📏
The returned feedback item doesn't get copied into UDVM memory. It just sits in a buffer until the UDVM has successfully decompressed the SigComp message. Then it gets forwarded to the state handler with the rest of the feedback data (see Section 9.4.9 for more 🦋).
7.2. Accessing Stored State ✨
Okay bestie, the len field is what decides what comes after the returned feedback item 💅. If len is non-zero, the SigComp message carries a state identifier so the receiver can grab a state item 🦋. Every state item has a 20-byte state identifier (see Section 3.3.3), but you can send as few as 6 bytes of it if the sender thinks that's enough to match one unique item at the receiving end 🧚.
The len field tells you how many bytes got sent:
Encoding: Length of partial state identifier
01 6 bytes
10 9 bytes
11 12 bytesThen the partial identifier goes to the state handler, which checks it against the most significant bytes of the state_identifier in every state item that's currently stored 🔍. If nothing matches, or if more than one thing matches, that's a decompression failure 💀.
It's also a decompression failure if exactly one item matches but that item has a minimum_access_length bigger than the length of the partial identifier. This is so the super sensitive state items can't be brute-forced by guessing at the state_identifier 🔒 protect the vibes!
If the access works, the state_value byte string gets copied into UDVM memory starting at state_address 🧠.
Next, the first 32 bytes of UDVM memory get set to special values, as shown 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 get filled with values that might be handy for the UDVM bytecode. We call these Useful Values 💖. Heads up: these are for information only, and the bytecode can overwrite them without any effect on the endpoint 🙅. The MSBs of each 2-byte word are stored before the LSBs.
Addresses 0 to 5 tell you what resources the receiving endpoint has available 👑. The UDVM memory size is expressed in bytes modulo 2^16, so if it's 65536 bytes it gets set to 0 (the math is iconic 🤓). cycles_per_bit is a 2-byte integer that's 16, 32, 64 or 128. SigComp_version is a 2-byte value as per Section 3.3.2.
Addresses 6 to 9 get the length of the partial state identifier, followed by the state_length from the retrieved state item. Both are 2-byte values 🎀.
Addresses 10 to 31 are reserved and get initialized to 0 for Version 0x01 of SigComp. Future versions could use these spots for more Useful Values, so a decompressor MUST NOT rely on these values being zero 🚫.
Any remaining addresses in UDVM memory that haven't been initialized yet MUST be set to 0 💯.
The UDVM then starts executing instructions at the memory address in state_instruction (which is part of the retrieved state item). The rest of the SigComp message is held by the decompressor dispatcher until the UDVM asks for it 📦.
(Quick note: the Useful Values only get set at UDVM startup. After that, that memory area has no special significance. So the bytecode is free to use those locations for any other purpose, it just has to know they aren't necessarily 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 inside the message itself 🎁. The 12-bit code_len field specifies the size of the uploaded UDVM bytecode (anywhere from 0 to 4095 bytes inclusive). The eight most significant bits go in the first byte, followed by the four least significant bits in the most significant bits of the second byte. The remaining bits in the second byte are a 4-bit destination field that says which starting memory address the bytecode gets copied to 📍. Here's how that destination field is encoded:
Encoding: Destination address:
0000 reserved
0001 2 * 64 = 128
0010 3 * 64 = 196
0011 4 * 64 = 256
: :
1111 16 * 64 = 1024Note that the encoding 0000 is reserved for future SigComp versions, and it 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 the UDVM needs it 🌈.
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 give you 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 gets 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 gap is guaranteed to be zero at UDVM startup and is efficiently addressable in operand types reference ($) and multitype (%) 🧸.)
8.2. Requesting Additional Compressed Data 💅
okay so the decompressor dispatcher is basically holding onto the compressed data from the SigComp message until the UDVM asks for it with one of the INPUT instructions 🧚. when the UDVM bytecode first runs, the dispatcher has whatever's left of the SigComp message after the header, because the header already set up the UDVM as per Chapter 7 ✨.
ngl the INPUT-BITS and INPUT-HUFFMAN instructions pull out a stream of individual compressed bits from the dispatcher 🫶. to be bitwise compatible with various well-known compression algorithms, the input_bit_order register can change the order that individual bits get 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 it's set to 0, the bits inside each byte go to the INPUT instructions in MSB to LSB order. If it's set to 1, they go in LSB to MSB order. main character energy 👑
Bytes themselves always arrive in the same order they occur in the SigComp message, so the input_bit_order register can't change that part at all 🙈.
Here's a diagram of how bits get passed 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 = 1After one or more INPUT instructions, the dispatcher may be holding a fraction of a byte (the LSBs if P = 0, or the MSBs if P = 1) 🍓. If an INPUT instruction shows up and the P-bit has changed since the last INPUT instruction, any leftover fraction of a byte the dispatcher is holding MUST be discarded (even if that INPUT instruction asks for zero bits) 💀. The first bit passed to the INPUT instruction then comes from the next byte.
When an INPUT instruction requests n bits of compressed data, it reads them as an integer between 0 and 2^n - 1 🔥. The F-bit and the H-bit decide whether the bits in those integers arrive in MSB to LSB order (bit set to 0) or LSB to MSB order (bit set to 1) 💜.
If the F-bit is 0, INPUT-BITS treats the bits as arriving MSBs first, and if it's 1, it treats them as arriving LSBs first 🎀. The H-bit does the same job for INPUT-HUFFMAN. It's totally possible to set these two bits to different values so the two instructions use different bit orders (some algorithms actually need this, e.g., DEFLATE [RFC-1951]) 🌈. (Also, there are no special rules for changing the F- or H-bit between INPUT instructions, unlike that discard rule for the P-bit we just talked about 🙌.)
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 use a stack of 2-byte words that lives at the memory address given by the 2-byte word stack_location 🧚. The stack looks like this:
Name: Starting memory address:
stack_fill stack_location
stack[0] stack_location + 2
stack[1] stack_location + 4
stack[2] stack_location + 6
: :stack_location is shorthand for the contents of the stack_location register, which is the 2-byte word at locations 70 and 71 💖. stack_fill is shorthand for the 2-byte word at stack_location and stack_location+1. Similarly, stack[n] is shorthand 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. obsessed with this 😭.)
The stack is used by the CALL, RETURN, PUSH and POP instructions 🫶.
"Pushing" a value on the stack is shorthand 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 shorthand 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 start of a popping operation. POP and RETURN pop values from the stack.
For both of these abstract operations, the UDVM first notes the current value of stack_location and uses that value for both sub-operations (accessing the stack and manipulating stack_fill) 🙈. So overwriting stack_location partway through the operation doesn't matter to it at all, periodt 💅.
8.4. Byte copying 🌈
A bunch of UDVM instructions need a string of bytes copied to and from areas of UDVM memory 🎀. This section explains how the byte copying operation should work 🔥.
The string of bytes is copied in ascending order of memory address, while respecting the bounds set by byte_copy_left and byte_copy_right 🦋. More precisely, if a byte is copied from or to Address m, then the next byte is copied from or to Address n, where n is worked out like this:
Set k := m + 1 (modulo 2^16)
If k = byte_copy_right then set n := byte_copy_left, else set n := kDecompression failure occurs if a byte is copied from or to an address beyond the UDVM memory 💀.
The string gets copied one byte at a time, so some of the later bytes might have already been written into UDVM memory by the very byte copying operation that's running right now 🧚.
It's also possible for a byte copying operation to overwrite the instruction that started the byte copy. If that happens, the byte copying operation MUST be completed as if the original instruction were still sitting in UDVM memory (this also applies if byte_copy_left or byte_copy_right gets 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 ✨
okay bestie, every UDVM instruction is just one byte 🦋, and then it's followed by 0 or more bytes holding the operands it needs. tiny and efficient, I'm obsessed 💅
when an instruction runs, the UDVM conceptually grabs that first byte, figures out how many operands it needs and what types they are, then decodes all of them in order before doing anything. (ngl the design is clever here: it's written so that this step stays conceptual in any case where doing it for real would be an unreasonable burden on the implementation 🫶)
to keep typical bytecode small, every operand is compressed with variable-length encoding. the vibe is: common values take fewer bytes, rare values take more 🌸
there are four operand types: the literal, the reference, the multitype and the address. Chapter 9 has the full list of instructions and which operand types follow each one 📚
Figure 8 to Figure 10 show the bytecode for each operand type, along with the integer values it represents.
a quick reading guide 🔍: the MSBs are drawn before the LSBs. And any run of bits marked with k consecutive "n"s is an integer N from 0 to 2^k - 1 inclusive (MSBs of n first, LSBs last).
the decoded integer can mean two different things. sometimes it is the actual operand value. other times it's a memory address where the 2-byte operand value lives (MSBs at the given address, LSBs at the next one). those second cases are written as memory[X], where X is the address and memory[X] is the 2-byte value starting at Address X 🧚
the literal (#) is the simplest type. it encodes a constant integer from 0 to 65535 inclusive, and it can take 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 - 65535Figure 8: Bytecode for a literal (#) operand
the reference ($) is the second type, and it's always used to access a 2-byte value somewhere else in UDVM memory. its bytecode decodes to a constant integer from 0 to 65535 inclusive, and that integer is the memory address holding the actual operand value 🎀
Bytecode: Operand value: Range:
0nnnnnnn memory[2 * N] 0 - 65535
10nnnnnn nnnnnnnn memory[2 * N] 0 - 65535
11000000 nnnnnnnn nnnnnnnn memory[N] 0 - 65535Figure 9: Bytecode for a reference ($) operand
the range of a reference operand is ALWAYS 0 - 65535, no matter how many bits are used to encode it, since it always points at a 2-byte value in memory. (the range is always 0 - 65535 🌈 same vibe, just a reminder!)
wait, correction for the record: the original says this in plain words, so here it is, as written: 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 multitype (%) is the third type. it can hold actual values and memory addresses, and it's extra good at encoding small integers (positive and negative) and 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 - 65535Figure 10: Bytecode for a multitype (%) operand
the address (@) is the fourth type, and it's a sneaky one 🙈. it's decoded as a multitype operand plus one extra step: the memory address of the UDVM instruction containing the address operand gets added in. so if the operand value from Figure 10 is D, the actual operand value of an address is calculated like this:
operand_value = (memory_address_of_instruction + D) modulo 2^16address operands are only used in instructions that control program flow. why? because they make the UDVM bytecode position-independent code (aka it runs no matter where it's placed in UDVM memory) 🦋 iconic design, honestly.
8.6. UDVM Cycles ⏱️
once the UDVM is invoked, it runs the instructions in its memory one after another, unless something says otherwise (like when it hits a JUMP instruction). if the next instruction to run is outside the available memory, then decompression failure happens (see Section 8.7) 💀
so a SigComp message can't eat all the processing power, SigComp caps the number of "UDVM cycles" each message gets. the number of available UDVM cycles starts at 1000 plus the number of bits in the SigComp header (as described in Section 7). then that sum gets multiplied by cycles_per_bit. every time an instruction runs, the available cycles go down by the amount listed in Chapter 9. and there's a bonus 🎁: if the UDVM successfully requests n bits of compressed data using one of the INPUT instructions, the available cycles go UP by n * cycles_per_bit once that instruction has been executed.
so the maximum number of UDVM cycles for an n-byte SigComp message works out to:
maximum_UDVM_cycles = (8 * n + 1000) * cycles_per_bitwhy not just hand over this whole total when the UDVM starts? because the UDVM can start decompressing a message that's only partly been received 🧩 so the total message size might not be known yet when the UDVM is set up.
one more thing: the number of UDVM cycles MUST NOT be increased if a request for additional compressed data fails. (no cheating allowed, bestie 🙅♀️)
the UDVM stops running instructions when it hits an END-MESSAGE instruction, or when decompression failure happens (see Section 8.7 for the details) 🛑
8.7. Decompression Failure 💔
if a compressed message given to the UDVM is corrupted, whether by accident or on purpose, then the UDVM may end with a decompression failure.
reasons for decompression failure include the following 👀:
- A SigComp message contains an invalid header as per Chapter 7.
- A SigComp message is larger than the decompression_memory_size.
- An instruction costs more than the number of remaining UDVM cycles.
- The UDVM attempts to read from or write to a memory address beyond its memory size.
- An unknown instruction is encountered.
- An unknown operand is encountered.
- 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).
- A request to access some state information fails.
- A manual decompression failure is triggered using the DECOMPRESSION-FAILURE instruction.
if a decompression failure happens while a message is being decompressed, the UDVM tells the dispatcher and takes no further action. it's the dispatcher's job to decide how to deal with it 🫶 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 already been output but not yet passed to the application. the dispatcher really is the one holding the bag here, so it's on them to clean up the mess 🧹✨
9. UDVM Instruction Set ✨
okay bestie, the UDVM understands 36 instructions 🦋 they were picked to cover the widest range of compression algorithms while adding the least possible overhead. it's giving efficient 💅
Figure 11 lists every instruction, its bytecode value, and its cost in UDVM cycles 🌸
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_lengthFigure 11: UDVM instructions and corresponding bytecode values
every instruction costs a minimum of 1 UDVM cycle ⏱️ some can cost extra depending on the values of their operands. in the cost formulas, the named variables just mean the values of the operands with those names 🧚
quick note for the SORT instructions: ceiling(log2(k)) gives you the smallest value i where k <= 2^i. math nerd moment, I'm obsessed 🤓
the instruction set is a mix of low-level and high-level instructions 🎀 the high-level ones can all be built out of combinations of low-level ones, but given the choice, it's generally better to use one single instruction instead of a pile of general-purpose ones. the bytecode ends up more compact (so a higher compression ratio, periodt ✨), and decompression is typically faster because the high-level instructions are easier to optimise 🚀
every instruction is encoded as one byte for the instruction type, followed by 0 or more bytes of operands. the instruction decides which of the four operand types from Section 8.5 gets used for each operand. for example, ADD takes two operands:
ADD ($operand_1, %operand_2)when it becomes bytecode, the number of bytes ADD needs depends on each operand's value, and on whether the multitype operand holds the value itself or a memory address where the value lives 🧩
each instruction gets its own deep dive below 💖
Whenever an instruction's description says "and then", it means the effect before "and then" finishes before the effect after it starts 🫶
9.1. Mathematical Instructions
these instructions do a bunch of maths stuff: bit manipulation, arithmetic, and sorting 🔥
9.1.1. Bit Manipulation
AND, OR, NOT, LSHIFT and RSHIFT do 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)once the operation is done, the first operand gets overwritten with the result. (since that operand is a reference, it's really the 2-byte word at the memory address it points to that gets overwritten 👀)
here are the exact definitions of LSHIFT and RSHIFT. m and n are the 2-byte values the operands encode, and floor(x) gives the largest integer that isn't greater than x 🧠
LSHIFT (m, n) := m * 2^n (modulo 2^16)
RSHIFT (m, n) := floor(m / 2^n)9.1.2. Arithmetic
ADD, SUBTRACT, MULTIPLY, DIVIDE and REMAINDER do 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, the first operand is overwritten with the result 🌈
here's the precise definition of each one 🎀
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)⚠️ bestie, watch out: decompression failure happens if a DIVIDE or REMAINDER instruction runs into an operand_2 that is zero. dividing by zero is a total no-go 💀
9.1.3. Sorting
SORT-ASCENDING and SORT-DESCENDING sort lists of 2-byte words 📋
SORT-ASCENDING (%start, %n, %k)
SORT-DESCENDING (%start, %n, %k)the start operand is the starting memory address of the block of data to sort 🗂️
that block is split into n lists, and each list holds k 2-byte words. SORT-ASCENDING applies a permutation to the lists so that the first list ends up sorted in ascending order (each 2-byte word is treated as an unsigned integer) 🦄 the same permutation is applied to all n lists, which means the lists other than the first won't necessarily be sorted. plot twist 😭
when two words have the same value, their original order stays the same 🫶
for example, the first list could hold integers that need sorting, while the second list tracks where each integer ends up after sorting 👑
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 1SORT-DESCENDING works the same way, except the first list gets sorted into descending order 🔽
9.1.4. SHA-1
the SHA-1 instruction calculates a 20-byte SHA-1 hash [RFC-3174] over the area of UDVM memory you point at 🔐
SHA-1 (%position, %length, %destination)the position and length operands give the starting memory address and the length of the byte string the SHA-1 hash is calculated over. the byte copying rules from Section 8.4 get enforced here 📏
the destination operand gives the starting address where the resulting 20-byte hash gets copied to. the same byte copying rules apply 🧚
9.2. Memory Management Instructions
these instructions set up UDVM memory and copy byte strings from one spot to another 🧸
9.2.1. LOAD
LOAD sets a 2-byte word to a specific value 💖 the format looks like this:
LOAD (%address, %value)the first operand is the starting address of a 2-byte word, and the second operand is the value that goes into that word. as usual, MSBs are stored before LSBs in UDVM memory 🌸
9.2.2. MULTILOAD
MULTILOAD sets a contiguous block of 2-byte words in UDVM memory to specified values 🎀
MULTILOAD (%address, #n, %value_0, ..., %value_n-1)the first operand is the starting address of the contiguous 2-byte words. the operands value_0 through value_n-1 are the values to load into those words, in the same order they appear in the instruction 🦋
decompression failure happens if the 2-byte words this instruction sets would overlap the memory locations holding the instruction itself (operands included). in other words, if it would modify itself 🙈 this rule makes MULTILOAD simpler to implement one step at a time, rather than decoding every operand before copying anything, which is what the conceptual model of instruction execution would otherwise imply.
9.2.3. PUSH and POP
PUSH and POP read from and write to the UDVM stack (as defined in Section 8.3) 📚
PUSH (%value)
POP (%address)PUSH pushes its operand's value onto the stack 🥞
POP pops a value off the stack and then copies that value to the specified memory address. (the "and then" here means the copy doesn't matter for the stack operation itself, since the stack bit happens first 🫠)
check Section 8.3 for possible error conditions 🔍
9.2.4. COPY
COPY copies a string of bytes from one part of UDVM memory to another 📦
COPY (%position, %length, %destination)the position operand is the memory address of the first byte to copy, and the length operand is how many bytes to copy 🌷
the destination operand is the address where that first byte gets copied to 💌
byte copying follows the rules in Section 8.4 🫶
9.2.5. COPY-LITERAL
here's a modified version of COPY 🎀
COPY-LITERAL (%position, %length, $destination)COPY-LITERAL behaves like COPY, except that once the copying is done, the destination operand's value gets replaced by the address where the next byte of data would be copied to. more precisely, it gets replaced by the value n, derived as in Section 8.4 with m set to the destination address of the last byte copied (if there's one). if the length operand is zero, the destination operand doesn't change at all 🧩
9.2.6. COPY-OFFSET
one more version of COPY-LITERAL, bestie 🦋
COPY-OFFSET (%offset, %length, $destination)COPY-OFFSET behaves like COPY-LITERAL, except it takes an offset operand instead of a position operand 💫
to work out the position operand, the UDVM starts at the memory address given by destination and counts backwards a total of offset memory addresses 🔙
if the memory address specified in byte_copy_left gets reached, the next memory address is taken to be (byte_copy_right - 1) modulo 2^16 🌀
then COPY-OFFSET behaves like COPY-LITERAL, using the last memory address reached in that step as the value of the position operand 👑
9.2.7. MEMSET 🧚
okay so MEMSET is the instruction that fills a chunk of UDVM memory with a pattern of values. bestie, it's giving paint-by-numbers 🎨 The format is:
MEMSET (%address, %length, %start_value, %offset)The values come from this formula, and I'm obsessed with how tidy it is 😭
Seq[n] := (start_value + n * offset) modulo 256So the values Seq[0] to Seq[length - 1] (inclusive, so yes, both ends count 💅) are each treated as a single byte. Then they get stuck together into a byte string, where the first byte is Seq[0], the second is Seq[1], and so on up to Seq[length - 1]. Iconic pattern-making ✨
Next, that byte string gets byte copied into UDVM memory, starting at the address given as the first operand. The copy follows the rules in Section 8.4. ngl this is where it gets a little spicy 🌶️ The byte string is allowed to overwrite the MEMSET instruction itself or its operands. As Section 8.5 explains, the MEMSET instruction has to act as if its original operands were still sitting in UDVM memory. Main character energy, the instruction keeps its own receipts 🧾
9.3. Program Flow Instructions 🦋
these instructions change where the UDVM code goes next. each one jumps to one of a few memory addresses, depending on some criterion.
note that certain I/O instructions (see Section 9.4) can also change program flow, so keep an eye on those too 👀
9.3.1. JUMP
the JUMP instruction moves execution to the memory address you give it. simple, clean, no drama 💖
JUMP (@address)decompression failure happens if the address operand points beyond the overall UDVM memory size. not me trying to jump off the edge of the map 💀
9.3.2. COMPARE
COMPARE takes two operands, compares them, and then jumps to one of three addresses based on the result. it's like a little sorting hat 🎀
COMPARE (%value_1, %value_2, @address_1, @address_2, @address_3)if value_1 < value_2, the UDVM keeps going at the memory address given by address 1. if value_1 = value_2, it jumps to address_2. and if value_1 > value_2, it jumps to address_3. ✨ the logic is literally that clean
9.3.3. CALL and RETURN
these two are the power couple for compression algorithms that have a nested structure 🌈 they're built to work together, so I'm treating them as one unit.
CALL (@address)
RETURNboth instructions use the UDVM stack from Section 8.3. when the UDVM hits a CALL, it finds the memory address of the instruction right after the CALL. then it pushes that 2-byte value onto the stack so it can grab it later. after that, it carries on at the address in the address operand 🧚
when the UDVM hits a RETURN, it pops a value off the stack and continues at the memory address it just popped. it always comes back to where it left off 🫶
see Section 8.3 for the error conditions. don't skip that part, bestie 🙈
9.3.4. SWITCH
SWITCH is a conditional jump that depends on the value of one of its operands. think of it as a choose-your-own-adventure page 📖
SWITCH (#n, %j, @address_0, @address_1, ... , @address_n-1)when a SWITCH shows up, the UDVM reads the value of j. then it continues at the address specified by address j. ngl that's it, that's the whole move 💅
decompression failure happens if j is a value of n or more, or if the address lies beyond the overall UDVM memory size. so basically, don't pick a door that doesn't exist 🚪
9.3.5. CRC
the CRC instruction checks a string of bytes using a 2-byte CRC. it's giving data integrity glow-up ✨
CRC (%value, %position, %length, @address)the actual CRC calculation uses the generator polynomial x^16 + x^12 + x^5 + 1. fun fact, this is the same as the 2-byte Frame Check Sequence (FCS) of PPP [RFC-1662] 🤝
the position and length operands define the string of bytes the CRC gets evaluated over. the 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]. no freestyling here, it's the same recipe 🍓
the value operand holds the expected integer value of the 2-byte CRC. if the calculated CRC matches the expected value, the UDVM keeps going at the following instruction. if not, it jumps to the memory address in the address operand. so the check either passes and moves on, or it gets rerouted 🦋
9.4. I/O instructions 🌸
these instructions let the UDVM talk to the outside world. the thing to know is that in the overall SigComp architecture, all of these interfaces pass through the decompressor dispatcher or the state handler 📬
9.4.1. DECOMPRESSION-FAILURE
DECOMPRESSION-FAILURE does exactly what it says: it triggers a manual decompression failure. it's super useful if the UDVM bytecode works out that it can't decompress the message, for example by using the CRC instruction 🙅♀️
this instruction has no operands. zero drama, zero extras ✨
9.4.2. INPUT-BYTES
INPUT-BYTES asks the decompressor dispatcher for a certain number of bytes of compressed data 🍰
INPUT-BYTES (%length, %destination, @address)the length operand is the number of bytes of compressed data you're requesting. the destination operand is the starting memory address where they get copied. byte copying follows the rules in Section 8.4 💜
if the instruction asks for data that goes past the end of the SigComp message, no data comes back. instead, the UDVM jumps to the address in the address operand 🚫
if INPUT-BYTES comes after an INPUT-BITS or an INPUT-HUFFMAN instruction, and the dispatcher is currently holding a fraction of a byte, then that fraction MUST be discarded before any data is passed to the UDVM. the first byte passed along is the byte right after the discarded data. this one is non-negotiable, bestie 🙏
9.4.3. INPUT-BITS
INPUT-BITS asks the decompressor dispatcher for a certain number of bits of compressed data 🧁
INPUT-BITS (%length, %destination, @address)the length operand is how many bits you want. decompression failure happens if this operand isn't between 0 and 16 inclusive. the destination operand is the memory address where the compressed data gets copied to.
the requested bits come back as a 2-byte integer, ranging from 0 to 2^length - 1. Section 8.2 explains the details 🌿
if the instruction asks for data past the end of the SigComp message, no data is returned. the UDVM jumps to the address in the address operand instead 🫠
9.4.4. INPUT-HUFFMAN
INPUT-HUFFMAN asks for a variable number of bits. it starts by requesting a small number of bits, then checks the result against a criterion. if the criterion isn't met, it keeps asking for more bits until it is 🧩
the instruction takes three mandatory operands, plus n extra sets of operands. every extra set has four operands, like this:
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)if n = 0, the INPUT-HUFFMAN instruction is ignored, and execution just resumes at the following instruction. decompression failure happens if (bits_1 + ... + bits_n) > 16. 😤
in all other cases, the behaviour goes like this:
- set j := 1 and set H := 0.
- 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. - set H := H * 2^bits_j + k.
- if data is requested that lies beyond the end of the SigComp message, end the INPUT-HUFFMAN instruction and move execution to the memory address in the address operand 🏃♀️
- if (H < lower_bound_j) or (H > upper_bound_j), set j := j + 1. then go back to Step 2, unless j > n, in which case decompression failure occurs. bestie this loop has a clear exit, so no infinite spiral 🌀
- copy
(H + uncompressed_j - lower_bound_j) modulo 2^16to the memory address in the destination operand. ta-da ✨
9.4.5. STATE-ACCESS
STATE-ACCESS retrieves some state information that was stored earlier 📦
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 show where the partial state identifier is. this identifier does the same job as the partial state identifier sent in the SigComp message, as per Section 7.2 🔑
decompression failure happens if partial_identifier_length isn't between 6 and 20 inclusive. it also happens if no state item matches the partial state identifier, if more than one state item matches, or if partial_identifier_length is less than the minimum_access_length of the matched state item. otherwise, a state item gets returned from the state handler 🙌
if any of the state_address, state_instruction or state_length operands is set to 0, its value is taken from the returned state item instead. so 0 means "use the stored value" 🧠
note that when working out the number of UDVM cycles, STATE-ACCESS costs (1 + state_length) cycles. the value of state_length MUST be taken from the returned item of state if the state_length operand is set to 0. ✨ serious rule, no skipping it
the state_begin and state_length operands define the starting byte and the number of bytes to copy from the state_value in the returned item of state. decompression failure happens if bytes get copied from beyond the end of the state_value. decompression failure will always happen if state_length is 0 but state_begin isn't 0 💀
the state_address operand holds a UDVM memory address. the requested part of the state_value is byte copied to that address, following the rules in Section 8.4 📝
then program execution resumes at the memory address in state_instruction. the exception is if that address is 0. in that case, execution resumes at the instruction right after STATE-ACCESS. this only happens when both the state_instruction operand and the state_instruction value from the requested state are 0 🌙
9.4.6. STATE-CREATE
STATE-CREATE requests that a state item gets created at the receiving endpoint 🏗️
STATE-CREATE (%state_length, %state_address, %state_instruction,
%minimum_access_length, %state_retention_priority)note that the new state item can't be created until the application returns a valid compartment identifier. so when a STATE-CREATE instruction shows up, the UDVM just buffers the five operands it was given until END-MESSAGE is reached. the steps at that point are 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. this one is a hard limit, bestie 🚧
decompression failure also happens if minimum_access_length doesn't lie between 6 and 20 inclusive, or if state_retention_priority is 65535. the vibe is strict but fair 🎀
9.4.7. STATE-FREE ✨
okay bestie, so the STATE-FREE instruction is how the sender tells the receiving endpoint "hey, I'm done with this state item, I'm not using it anymore" 💅🫶
STATE-FREE (%partial_identifier_start, %partial_identifier_length)BUT here's the tea 🍵: STATE-FREE does not actually delete the state item right away. It just reclaims the memory that item was taking up inside a certain compartment, and we usually don't know which compartment until we hit END-MESSAGE 🧚 So, same as STATE-CREATE, when the UDVM sees a STATE-FREE it just holds onto the two operands and waits until END-MESSAGE shows up. The actual steps happen there, and they're 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. 💀 Also, decompression failure happens if partial_identifier_length isn't between 6 and 20 inclusive. So keep your numbers in range, bestie 🙈
9.4.8. OUTPUT 🦋
the OUTPUT instruction is the moment the UDVM hands the successfully decompressed data over to the dispatcher 🎀
OUTPUT (%output_start, %output_length)The operands tell it the starting memory address and the length of the byte string that goes to the dispatcher. Iconic part: OUTPUT can be used more than once, so you can send a partially decompressed message 🌸 Every time it runs, it gives the dispatcher a fresh byte string, and the dispatcher just tacks it onto the end of whatever it already got from earlier OUTPUT instructions. Main character energy 👑
The bytes get copied out of UDVM memory following the rules in Section 8.4 📦
Decompression failure occurs if the total number of bytes handed to the dispatcher goes over 65536 bytes. ngl that's a lot of bytes, but it's a hard cap 😭
Now, this part is lowkey so specific and I'm obsessed 🫠 There's a real difference between outputting a 0-byte decompressed message and not outputting a decompressed message at all, so OUTPUT has to tell those two apart. If the UDVM terminates before it ever hits an OUTPUT instruction, that counts as not outputting a decompressed message. But if it runs one or more OUTPUT instructions and every single one of them gives 0 bytes to the dispatcher, then it counts as having outputted a 0-byte decompressed message 🌈 Tiny detail, huge difference 💜
9.4.9. END-MESSAGE ✨
okay bestie, END-MESSAGE is the grand finale 🎀 It 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 END-MESSAGE shows up, the decompressor dispatcher tells the application that a complete message has been decompressed 🎉 The application can hand back a compartment identifier, and the UDVM forwards it to the state handler along with the state creation and state free requests and any supplied feedback data 🧚
The decompressed message itself gets outputted separately using the OUTPUT instruction 💖 This is lowkey genius because it saves memory at the UDVM. There's no need to buffer a whole decompressed message before it gets passed to the dispatcher 🌸
END-MESSAGE can pass up to four state creation requests and up to four state free requests to the state handler ✨ The requests go over in the same order they were made. So yes, state creation and state free requests can be interleaved 🦋
State creation requests are made by the STATE-CREATE instruction 🎀 But END-MESSAGE can also make one state creation request on its own, using its supplied operands 👑 If the specified minimum_access_length does not lie between 6 and 20 inclusive, or if the state_retention_priority is 65535, then END-MESSAGE fails to make its own state creation request 😭 Don't panic though: decompression failure does not occur in that case, and the state creation requests made by STATE-CREATE are still valid 💜
There's a hard limit of four state creation requests per instance of the UDVM 🚨 So decompression failure occurs if END-MESSAGE makes a state creation request and four instances of STATE-CREATE have already been encountered. Not cute, bestie 💀
When you create a state item, you need to give the state_length, state address, state_instruction and minimum_access_length 🌈 These are supplied as operands in STATE-CREATE (or END-MESSAGE). A complete item of state also needs a state_value and a state_identifier, and here's how those get derived 🧚
The UDVM byte copies a string of state_length bytes from UDVM memory, beginning at state_address (obeying the rules of Section 8.4). That's your state_value 💖
Then the UDVM calculates a 20-byte SHA-1 hash [RFC-3174] over the byte string formed by concatenating the state_length, state_address, state_instruction, minimum_access_length and state_value, in that order. That's your state_identifier 🔥
The state_retention_priority is not part of the state item itself 🍓 It decides the order in which state gets deleted when the compartment goes over its allocated state memory. It's supplied as an operand in STATE-CREATE or END-MESSAGE, and it's passed to the state handler as part of each state creation request ✨
State free requests are made by the STATE-FREE instruction 🦋 Each STATE-FREE instruction supplies partial_identifier_start and partial_identifier_length. When END-MESSAGE is reached, those values get used to byte copy a partial state identifier from UDVM memory. If no state item matches that partial state identifier, or if more than one state item in the compartment matches it, the state free request is ignored (and no decompression failure happens, so chill 🙈). Otherwise, the state handler frees the matched state item as specified in Section 6.2 ✨
END-MESSAGE can also pass feedback data to the state handler, on top of forwarding the state creation and state free requests 🫶 Feedback data tells the receiving endpoint about the capabilities of the sending endpoint. That can help improve the overall compression ratio and reduce the working memory requirements of the endpoints. Iconic 👑
There are two types of feedback data: requested feedback and returned feedback 💜 The format of requested feedback data is in Figure 12. As outlined in Section 3.2, the requested feedback data can be used to influence the contents of the returned feedback data in the reverse direction 🔁
Returned feedback data is split into a returned feedback item and a list of returned SigComp parameters 🎀 The returned feedback item is important enough to get its own field in the SigComp header, as described in Section 7.1. The returned SigComp parameters are illustrated in Figure 13 🌸
Heads up: the formats in Figure 12 and Figure 13 are only for local presentation of the feedback data on the interface between the UDVM and state handler 💅 They don't mandate any bits on the wire. The compressor can transmit the data in any form, as long as it's loaded into UDVM memory at the correct addresses ✨
Also, the responsibility for making sure feedback data arrives successfully over an unreliable transport lies with the sender 😭 The receiving endpoint always uses the last received value for each field in the feedback data, even if those values are out of date because of packet loss or misordering 🙈
If the requested_feedback_location operand is set to 0, then no feedback request is made 🧚 Otherwise, it points to the starting memory address of the requested feedback data, as shown in Figure 12 🍓
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| reserved | Q | S | I | requested_feedback_location
+---+---+---+---+---+---+---+---+
| |
: requested feedback item : if Q = 1
| |
+---+---+---+---+---+---+---+---+
Figure 12: Format of requested feedback dataThe reserved bits may be used in future versions of SigComp, and they're set to 0 in Version 0x01 🔮 Non-zero values should be ignored by the receiving endpoint 🚫
The Q-bit tells you whether a requested feedback item is present or not 🌈 The compressor can set the requested feedback item to an arbitrary value, which then gets transmitted unmodified in the reverse direction as a returned feedback item. See Chapter 5 for further details on how the requested feedback item is returned 🦋
The format of the requested feedback item is identical to the format of the returned feedback item shown in Figure 4 💖
The compressor sets the S-bit to 1 if it does not wish (or no longer wishes) to save state information at the receiving endpoint, and also doesn't wish to access state information it has previously saved 🫶 So if S is 1, the receiving endpoint can reclaim the state memory allocated to the remote compressor and set the state_memory_size for the compartment to 0 🧹
The compressor may change its mind and switch the S-bit back to 0 in a later message ✨ But the receiving endpoint is under no obligation to use the original state_memory_size for the compartment. It may choose to allocate less memory to the compartment, or possibly none at all 🤷♀️
Similarly, the compressor sets the I-bit to 1 if it does not wish (or no longer wishes) to access any of the locally available state items offered by the receiving endpoint 🎀 This can help conserve bandwidth, because the list of locally available state items no longer needs to be returned in the reverse direction. It may also conserve memory at the receiving endpoint, since the state handler can delete any locally available state items it determines are no longer required by any remote endpoint 🧠 Note that the compressor can set the I-bit back to 0 in a later message, but it can't access any locally available state items that were previously offered by the receiving endpoint unless they're subsequently re-announced 📣
If the returned_parameters_location operand is set to 0, then no SigComp parameters are returned 🌸 Otherwise, it points to the starting memory address of the returned parameters, as shown in Figure 13 ✨
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| cpb | dms | sms | returned_parameters_location
+---+---+---+---+---+---+---+---+
| SigComp_version |
+---+---+---+---+---+---+---+---+
| length_of_partial_state_ID_1 |
+---+---+---+---+---+---+---+---+
| |
: partial_state_identifier_1 :
| |
+---+---+---+---+---+---+---+---+
: :
+---+---+---+---+---+---+---+---+
| length_of_partial_state_ID_n |
+---+---+---+---+---+---+---+---+
| |
: partial_state_identifier_n :
| |
+---+---+---+---+---+---+---+---+
Figure 13: Format of returned SigComp parametersThe first byte encodes the SigComp parameters cycles_per_bit, decompression_memory_size and state_memory_size, as per Section 3.3.1 🧮 The byte can be set to 0 if the three parameters aren't included in the feedback data. (This can be useful for saving bits in the compressed message if the remote endpoint is already satisfied that all necessary information has reached the endpoint receiving the message 🫶)
The second byte encodes the SigComp_version, as per Section 3.3.2 🔢 Just like the first byte, it can be set to 0 if the parameter isn't included in the feedback data 🙌
The remaining bytes encode a list of partial state identifiers for the locally available state items offered by the sending endpoint 🧩 Each state item is encoded as a 1-byte length field, followed by a partial state identifier containing as many bytes as the length field indicates. The sender can choose to send as few as 6 bytes if it believes that's enough for the receiver to figure out which state item is being offered 🕵️♀️
The list of state identifiers is terminated by a byte in the position where the next length field would be expected, and that byte is set to a value below 6 or above 20 🛑 Note that upgraded SigComp versions may append additional items of data after the final length field 🌈
10. Security Considerations 🔐
10.1. Security Goals
The overall security goal of the SigComp architecture is to not create risks that are in addition to those already present in the application protocols 💅 SigComp isn't meant to enhance the security of the application, because it can always be circumvented by not using compression 🙃 More specifically, the high-level security goals are:
- Do not worsen security of existing application protocol
- Do not create any new security issues
- Do not hinder deployment of application security.
10.2. Security Risks and Mitigation
This section identifies the potential security risks associated with SigComp, and explains how each risk is minimized by the scheme 🛡️💜
10.2.1. Confidentiality Risks 🔐✨
- okay so the first worry: snooping on other users' state 👀
State gets accessed by handing over a state identifier, which is basically a cryptographic hash of the state you're pointing at 🧁. That means the message doing the referencing already has to know about the state. To enforce this, a state item can't be accessed unless you supply a minimum of 48 bits from the hash 🔒. That also keeps accidental state collisions super unlikely. A compressor can use the minimum_access_length operand of the STATE-CREATE and END-MESSAGE instructions to make it need even more bits to access the state, which ups the protection against attacks 💅.
Honestly, anyone who can learn the state identifier (say, through passive attacks) will usually be able to learn the referenced state too, so no new vulnerability results 🙄.
Bestie rule: an endpoint needs to handle state identifiers with the same care it would handle the state itself 🫶.
10.2.2. Integrity Risks 🛡️
The SigComp approach assumes there's appropriate integrity protection below and/or above the SigComp layer 🧱. The state creation mechanism gives some extra potential to mess with the integrity of messages, but this would most likely be detectable at the application layer 🔍.
- attacking SigComp by faking state or making unauthorized changes to state 🥷
State can't be destroyed by a malicious sender unless they can send messages that the application identifies as belonging to the same compartment the state was created under. This adds extra security risks only when the application allows the installation of SigComp state from a message where it would not have installed state itself 😬.
Faking or changing state is only possible if the hash allows intentional collision 🌀.
10.2.3. Availability Risks (Avoiding DoS Vulnerabilities) 🚫
- using SigComp as a tool in a DoS attack on another target 💣
SigComp can't easily be used as an amplifier in a reflection attack, since it only generates one decompressed message per incoming compressed message 🙅♀️. That message then gets handed to the application, so the utility as a reflection amplifier is limited by how useful the application is for that purpose.
Okay but here's the tea ☕: SigComp can be used to generate larger messages as input to the application than the malicious sender had to send. So they can send smaller messages (at a lower bandwidth) than are delivered to the application. Depending on the reflection characteristics of the application, this can be considered a mild form of amplification 📈.
The application MUST limit the number of packets reflected to a potential target, even if SigComp is used to generate a large amount of information from a small incoming attack packet 🚧.
- attacking SigComp as the DoS target by filling it with state 🗑️
Excessive state can only be installed by a malicious sender (or a set of malicious senders) with the consent of the application. So the system made of SigComp and the application is about as vulnerable as the application itself, unless it allows the installation of SigComp state from a message where it would not have installed application state itself 🤷♀️.
If you want this to boost the compression ratio, the effect can be mitigated by using feedback at the application level that indicates whether the requested state was actually installed. This lets a system under attack gracefully degrade by no longer installing compressor state that isn't matched by application state 🌸.
Obviously, if a stream-based transport is used, the streams themselves count as state, and they have to be handled the same way the application itself would handle a stream-based transport. If an application isn't equipped for stream-based transport, it should not allow SigComp connections on a stream-based transport 🙅♀️.
For the alternative SigComp usage described as "continuous mode" in Section 4.2.1, an attacker could create any number of active UDVMs, unless there's some DoS protection at a lower level (e.g., by using TLS in appropriate configurations) 😱.
- attacking the UDVM by faking state or making unauthorized changes to state 🎭
This is covered in Section 10.2.2 🔁.
- attacking the UDVM by sending it looping code 🔄
The application sets an upper limit on the number of "UDVM cycles" that can be used per compressed message and per input bit in the compressed message. So the damage from sending packets with looping code is limited, although it may still be substantial if a large number of UDVM cycles are offered by the UDVM 🥲. But honestly, this would be true for any decompressor that can receive packets over an unsecured transport 🔓.
11. IANA Considerations 📋
SigComp requires a 1-byte name space, the SigComp_version, which has been created by the IANA 🧾. Upgraded versions of SigComp must be backwards-compatible with Version 0x01, described in this document. Adding additional UDVM instructions and assigning values to the reserved UDVM memory addresses are two possible upgrades where this is the case ✨.
Following the policies outlined in [RFC-2434], the IANA policy for assigning a new value for the SigComp_version shall require a Standards Action. So values are only assigned for Standards Track RFCs approved by the IESG 🏅.
12. Acknowledgements 🫶
Huge thanks to these legends for valuable input and review 🥰:
Abigail Surtees
Mark A West
Lawrence Conroy
Christian Schmidt
Max Riegel
Lars-Erik Jonsson
Stefan Forsgren
Krister Svanbro
Miguel Garcia
Christopher Clanton
Khiem Le
Ka Cheong Leung
Robert Sugar13. References 📚
13.1. Normative References
[RFC-1662] Simpson, W., "PPP in HDLC-like Framing", STD 51, RFC
1662, July 1994.
[RFC-2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC-3174] Eastlake, 3rd, D. and P. Jones, "US Secure Hash Algorithm
1 (SHA1)", RFC 3174, September 2001.13.2. Informative References
[RFC-1951] Deutsch, P., "DEFLATE Compressed Data Format
Specification version 1.3", RFC 1951, May 1996.
[RFC-2026] Bradner, S., "The Internet Standards Process - Revision
3", BCP 9, RFC 2026, October 1996.
[RFC-2279] Yergeau, F., "UTF-8, a transformation format of ISO
10646", RFC 2279, January 1998.
[RFC-2326] Schulzrinne, H., Rao, A. and R. Lanphier, "Real Time
Streaming Protocol (RTSP)", RFC 2326, April 1998.
[RFC-2434] Alvestrand, H. and T. Narten, "Guidelines for Writing an
IANA Considerations Section in RFCs", BCP 26, RFC 2434,
October 1998.
[RFC-2960] Stewart, R., Xie, Q., Morneault, K., Sharp, C.,
Schwartzbauer, H., Taylor, T., Rytina, I., Kalla, M.,
Zhang, L. and V. Paxson, "Stream Control Transmission
Protocol", RFC 2960, October 2000.
[RFC-3261] Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston,
A., Peterson, J., Sparks, R., Handley, M. and E.
Schooler, "SIP: Session Initiation Protocol", RFC 3261,
June 2002.
[RFC-3321] Hannu, H., Christoffersson, J., Forsgren, S., Leung,
K.-C., Liu, Z. and R. Price, "Signaling Compression
(SigComp) - Extended Operations", RFC 3321, January
2003.14. Authors' Addresses 💌
Richard Price
Roke Manor Research Ltd
Romsey, Hants, SO51 0ZN
United Kingdom
Phone: +44 1794 833681
EMail: richard.price@roke.co.uk
Carsten Bormann
Universitaet Bremen TZI
Postfach 330440
D-28334 Bremen, Germany
Phone: +49 421 218 7024
EMail: cabo@tzi.org
Jan Christoffersson
Box 920
Ericsson AB
SE-971 28 Lulea, Sweden
Phone: +46 920 20 28 40
EMail: jan.christoffersson@epl.ericsson.se
Hans Hannu
Box 920
Ericsson AB
SE-971 28 Lulea, Sweden
Phone: +46 920 20 21 84
EMail: hans.hannu@epl.ericsson.se
Zhigang Liu
Nokia Research Center
6000 Connection Drive
Irving, TX 75039
Phone: +1 972 894-5935
EMail: zhigang.c.liu@nokia.com
Jonathan Rosenberg
dynamicsoft
72 Eagle Rock Avenue
First Floor
East Hanover, NJ 07936
EMail: jdrosen@dynamicsoft.com15. Full Copyright Statement 🎀
Okay, the legal bit, and I'm keeping it word-for-word so nothing gets lost 📜:
Copyright (C) The Internet Society (2003). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.Acknowledgement 🌈
Funding for the RFC Editor function is currently provided by the Internet Society 💖✨
📦 where this page comes from
- ietf: rfc3320 2003-01
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms