Assembler (UDVM)

Assembler (UDVM) is the assembly language for the Universal Decompressor Virtual Machine, a small bytecode processor specified by the IETF in RFC 3320 in January 2003 as the decompression engine of SigComp (Signaling Compression). It exists to solve one narrowly-defined problem, and its design follows from that problem with unusual directness.

The problem was this. Mobile networks in the early 2000s were about to carry SIP, a text-based signaling protocol whose messages commonly run to a kilobyte or more. On the slow radio bearers of the day, sending those messages verbatim was understood to add noticeable delay to call setup — the concern RFC 3322 records as the motivation for the work. Compression was the obvious answer, but compression requires both ends to agree on an algorithm — and negotiating that agreement across handsets, network vendors, and a decade of firmware revisions is exactly the kind of coordination problem that standards bodies are bad at solving quickly.

SigComp’s answer was to refuse to choose. Instead of standardizing a compression algorithm, it standardized a virtual machine and let each compressed message carry the bytecode for its own decompressor. A sender that invents a better algorithm on Tuesday can use it on Wednesday, because the receiver does not need to know the algorithm — it only needs to run the program. The UDVM is what that program is written for, and UDVM assembly is what it is written in.

History & Origins

The SIP Compression Problem (2000-2002)

The IETF’s ROHC (Robust Header Compression) working group, chartered around header compression for IP over wireless links, took on the problem of compressing signaling message payloads rather than headers. The requirements were collected in what became RFC 3322: compression had to be lossless, had to work over TCP, UDP, and SCTP, had to survive message loss and reordering, and had to be implementable on the memory budget of a mobile handset.

Richard Price of Siemens/Roke Manor Research proposed the virtual-machine approach and submitted draft-ietf-rohc-sigcomp-udvm-00, titled Universal Decompressor Virtual Machine, on 28 January 2002. The draft was subsequently merged into the main SigComp specification rather than proceeding separately.

RFC 3320 (2003)

RFC 3320 was published in January 2003, authored by R. Price, C. Bormann, J. Christoffersson, H. Hannu, Z. Liu, and J. Rosenberg — a group spanning Siemens, the University of Bremen, Ericsson, Nokia, and dynamicsoft. It defines the SigComp message format, the state handler, and the UDVM itself: memory model, register layout, instruction set, operand encodings, and the cycle accounting that bounds how much work a decompressor can be made to do.

Two companion documents appeared the same month. RFC 3321 (Extended Operations) describes how to build the mechanisms that make compression actually efficient across a session — dynamic compression, shared compression, checkpointing — using only the instructions RFC 3320 already provides. RFC 3322 records the requirements. In February 2003, RFC 3485 added a static dictionary of common SIP and SDP strings, so that the very first message of a session can be compressed against shared text rather than against nothing.

Clarification and Consolidation (2005-2007)

The UDVM specification turned out to be difficult to implement identically. Corner cases in memory wraparound, operand decoding, and state handling were read differently by different vendors, and mismatched interpretations produce decompression failures rather than graceful degradation.

The response was a run of remedial documents. RFC 4077 (May 2005) added a negative acknowledgement mechanism carrying a specific failure reason, so an endpoint could say why decompression failed instead of silently dropping the message. RFC 4464 (May 2006), the SigComp Users’ Guide by A. Surtees and M. West, defined a readable assembly notation for the UDVM and published complete worked decompressors for LZ77, LZSS, LZW, DEFLATE, and LZJH. RFC 4465 (June 2006) published torture tests exercising every instruction at its boundaries. RFC 4896 (June 2007) collected the accumulated corrections and formally updated RFC 3320, RFC 3321, and RFC 3485. RFC 5049 (December 2007) specified how SIP in particular should apply the whole thing.

That sequence — specification, then guide, then torture tests, then corrections — is a fair summary of the language’s practical history. The idea was elegant; getting thirty-six instructions to mean the same thing to everyone took four more years.

Design Philosophy

Carry the algorithm with the data. The central bet is that shipping a decompressor is cheaper than agreeing on one. Bytecode is a few hundred bytes; a standards negotiation is a few years. Once a compressor and decompressor have exchanged messages, the bytecode can be retained as state and referenced by identifier instead of re-sent.

Decompression only. The UDVM has no ambition to be general-purpose. There is no compressor VM, no I/O beyond reading the compressed message and emitting decompressed bytes, no networking, no arbitrary system access. The compressor side is entirely unspecified — implementers may do whatever they like, so long as they can emit bytecode that reverses it.

Bounded by construction. A decompressor executes untrusted code supplied by a remote party, so the machine is designed so that hostile bytecode cannot consume unbounded resources. Memory is a fixed, pre-declared array with no allocation. Every instruction has a published cycle cost, and the total cycle budget is a function of the compressed message length. There are no unbounded loops that the machine cannot detect, because running out of cycles is itself a defined failure.

Fail loudly, never wrongly. Every error condition in the specification results in decompression failure — the message is discarded and, with RFC 4077, a reason code is returned. There is no undefined behaviour to exploit and no partial output to misinterpret.

Compact encoding above all. Because bytecode travels inside the message it decompresses, every byte of program is a byte not spent on payload. This drives the most distinctive feature of the language: its variable-length operand encodings, which spend as little as six bits on a small constant.

Key Features

Memory Model

UDVM memory is a single flat byte array, addressed with 16-bit values, with no distinction between code and data — bytecode is uploaded into the same array it operates on, and self-modifying decompressors are entirely legal.

Memory size is declared by the endpoint and announced during negotiation. RFC 3320 requires every endpoint to offer a decompression_memory_size of at least 2,048 bytes, and the 3-bit encoding of that parameter covers powers of two up to 131,072 bytes. The UDVM memory itself is capped at 65,536 bytes, since addresses are 16-bit.

Multi-byte values are stored big-endian (most significant byte first).

The low addresses are reserved. Addresses 0-31 hold read-only useful values that the machine initialises before execution:

Above them sit the four UDVM registers, which are ordinary 16-bit memory locations that instructions consult implicitly:

Uploaded bytecode is placed at an address that is a multiple of 64, encoded in a 4-bit destination field in the SigComp message header covering addresses 128 through 1024. The code_len field is 12 bits, capping a single uploaded program at 4,095 bytes.

The Byte Copying Rules

The byte_copy_left and byte_copy_right registers turn a region of memory into a circular buffer, and this single mechanism is what lets the UDVM implement the LZ77 family of algorithms in almost no code.

When a copy operation walks past byte_copy_right - 1, the next address is byte_copy_left rather than the next byte. Crucially, copies proceed one byte at a time, so a copy whose source and destination overlap will read bytes it has just written. That is not a bug to be worked around; it is the run-length mechanism. A back-reference of “go back 3 bytes, copy 100 bytes” — the fundamental operation of LZ77, DEFLATE, and LZW — falls out of this rule for free, with no special case anywhere in the machine.

Three instructions honour these rules: COPY, COPY-LITERAL, and COPY-OFFSET. COPY-OFFSET expresses the back-reference directly, taking a distance backwards from the destination rather than an absolute source address.

Operand Types

The UDVM has four operand kinds, distinguished in assembly notation by a sigil, and this is where the language’s obsession with compactness shows:

• Literal (#) — a constant. One byte for values 0-127, two for 0-16383, three for the full 16-bit range.
• Reference ($) — a memory address, decoded exactly like a literal but denoting the location holding the value. Used for destinations.
• Multitype (%) — either a constant or a memory reference, resolved by the encoding itself.
• Address (@) — a jump target, decoded as a literal but added to the memory address of the current instruction, modulo 2¹⁶. This makes bytecode position-independent: a program assembled once can be uploaded to any legal destination address without relocation.

The multitype encoding is the cleverest part. It is a variable-length prefix code covering, among other cases:

A small positive constant costs six bits. A small negative constant — encoded as its 16-bit wraparound, hence the 111nnnnn row — also costs six bits. A power of two costs one byte. A reference to one of the first 128 bytes of memory, which is where all the registers live, costs one byte. The common cases in a decompressor are exactly the cases the encoding makes cheap, which is not an accident.

Instruction Set

Thirty-six instructions, bytecodes 0 through 35:

Several are unusual for an assembly language, and each earns its place:

INPUT-HUFFMAN decodes a Huffman-coded value in a single instruction, taking a variable-length list of bit-lengths with lower and upper bounds per length class. Huffman decoding is the inner loop of DEFLATE; implementing it in INPUT-BITS and branches would cost both program bytes and cycles, so the machine absorbs it.

SHA-1 is present because SigComp identifies retained state by the SHA-1 hash of its contents. State identifiers are not assigned; they are computed, so that two endpoints independently arrive at the same name for the same bytes.

SORT-ASCENDING / SORT-DESCENDING sort a list of 16-bit values, needed to reconstruct Huffman code tables from code lengths.

CRC verifies integrity in one instruction rather than a loop.

MULTILOAD writes a run of constants into consecutive memory in one instruction — the compact way to initialise a table without a LOAD per entry.

Instruction operands are written in the specification with their sigils attached, which makes the signatures self-documenting:

COPY-OFFSET (%offset, %length, $destination)
INPUT-HUFFMAN (%destination, @address, #n, %bits_1, %lower_bound_1,
               %upper_bound_1, %uncompressed_1, ...)
COMPARE (%value_1, %value_2, @address_1, @address_2, @address_3)
STATE-ACCESS (%partial_identifier_start, %partial_identifier_length,
              %state_begin, %state_length, %state_address,
              %state_instruction)

COMPARE is worth a second look: it is a three-way branch, taking separate targets for less-than, equal, and greater-than. One instruction, three outcomes, no condition-code register — again, program bytes are the scarce resource.

Cycle Accounting

Because the code is supplied by a remote and possibly hostile party, the UDVM meters execution. Every instruction has a defined cost — one cycle for simple operations, 1 + length for copies and hashes, 1 + n for the variable-length forms.

The budget for decompressing a message is:

available_cycles = (8 * n + 1000) * cycles_per_bit

where n is the length of the SigComp message in bytes and cycles_per_bit is an endpoint parameter with a specified minimum of 16. The allowance is therefore proportional to the compressed input, with a fixed grant of 1000 bits’ worth of headroom for setup. A program that exhausts it triggers decompression failure.

This is a specification limit, not a measured benchmark — it bounds work per byte received, so that an attacker cannot send a small message that costs a great deal to decompress.

State

The UDVM starts each message with clean memory apart from the useful values, which makes decompression of a single message self-contained and loss-tolerant. Persistent context is handled explicitly by the three state instructions.

STATE-CREATE and END-MESSAGE ask the state handler to retain a block of memory, keyed by its SHA-1 hash. STATE-ACCESS retrieves a previously retained block by a partial identifier — a prefix of the hash, since sending all 20 bytes on every message would defeat the purpose. STATE-FREE releases it. State lives in compartments scoped to an application-level association, so one peer’s retained bytecode cannot be accessed by another.

The pay-off is that after the first exchange, a sender can reference the decompressor it uploaded earlier rather than re-sending it, and can reference previously-sent message text as compression context. RFC 3485’s static dictionary is the same mechanism with a well-known identifier: a block of common SIP and SDP strings that every implementation is assumed to hold from the start.

Writing UDVM Assembly

RFC 3320 defines bytecode, not source syntax. The assembly notation came three years later in RFC 4464, which specifies a two-level language — a lexical level of names, opcodes, delimiters, and integers in decimal, binary, or hex, and a syntactic level of instructions, labels, directives (pad, data, readonly), and arithmetic and bitwise expressions.

The assembler carries real responsibility. It decides for each operand whether a literal or a reference encoding is cheaper, chooses among the multitype patterns, resolves @ operands into instruction-relative offsets, and lays out the reserved regions so the uploaded image lands correctly. Because the encoding is variable-length and address operands are relative, changing one constant can change the size of an instruction and shift every offset after it.

The Users’ Guide also publishes complete decompressors in its appendix — for LZ77, LZSS, LZW, DEFLATE, and LZJH — which is how most people learned the language:

• LZSS, using a single flag bit per token to distinguish a literal byte from an offset/length pair
• DEFLATE, decoding Huffman-coded blocks via INPUT-HUFFMAN
• LZW, maintaining a codebook indexed by variable-width codes

These are short programs. The published bytecode for a working decompressor runs to a few hundred bytes — which it must, because it travels inside the message. The code_len field caps any single uploaded program at 4,095 bytes regardless.

Evolution

The instruction set itself never changed. Everything after RFC 3320 either explains it, tests it, or corrects the ways it was misread — which is a reasonable outcome for a specification whose whole purpose was to avoid ever having to change.

Current Relevance

The UDVM is dormant rather than dead, and its status is tied to the fortunes of the deployment that motivated it.

IMS deployments. SigComp remains part of the 3GPP IMS specifications; per 3GPP TS 24.229 it is mandatory between the UE and the P-CSCF for certain access types, from Release 5 onward. Where IMS is deployed with SIP compression enabled, UDVM bytecode is executing in handsets and P-CSCF nodes today. What undercut it is that the pressure that created it eased: on LTE and later radio bearers, a kilobyte-scale SIP message is reportedly no longer the setup-latency problem it was on GPRS, and many operators are said not to enable compression at all.

Protocol analysis. Wireshark ships a complete UDVM interpreter in its SigComp dissector. It will show the uploaded bytecode, run it to recover the plaintext SIP message, and — with the detail level turned up — trace execution instruction by instruction. For anyone debugging IMS signaling, this is the practical face of the language.

Open-source stacks. Doubango Telecom’s libSigComp, first released in beta under LGPLv3 in 2009, provides a UDVM implementation intended to be dropped into existing SIP/IMS stacks and P-CSCF or push-to-talk-over-cellular clients, with DEFLATE as the default compressor and a plug-in interface for others.

Conformance testing. The RFC 4465 torture tests remain the reference for validating a UDVM implementation, and they are the reason anyone writes UDVM assembly by hand today.

Nobody is inventing new UDVM programs for fun. The language has no general-purpose toolchain, no package ecosystem, and no community outside telecom protocol work. But it is fully specified, fully implemented in at least one tool that anyone can install, and still running in production networks.

Why It Matters

The UDVM is a small language with a genuinely original answer to a recurring problem.

It inverts the standardization problem. The usual approach to “which algorithm shall we both use?” is a negotiation protocol: enumerate the options, exchange capability lists, pick an intersection, and repeat the whole exercise whenever someone invents something better. SigComp replaced negotiation with transmission — don’t tell me which algorithm you used, send me the code. The same instinct shows up elsewhere, in PostScript sending programs rather than pages and in eBPF sending programs into the kernel rather than adding syscalls, but the UDVM is one of the cleanest instances precisely because its scope is so tight.

It shows what a security-first VM looks like. The UDVM’s entire job is to execute untrusted code from the network on a device that cannot afford to be wedged. Every design decision follows: fixed memory with no allocation, no syscalls, no unbounded loops, published cycle costs per instruction, an execution budget proportional to input size, and a single well-defined failure mode. Those constraints were adopted in 2003, and they read today like a checklist that later designs for executing untrusted code — eBPF’s verifier, WebAssembly’s linear memory model — arrived at independently for their own reasons.

It is a case study in encoding density. Most instruction sets optimise for decode speed or for regularity. The UDVM optimises for program size, because the program is transmission overhead subtracted from the payload it exists to shrink. The multitype operand encoding, the instruction-relative address operands, the three-way COMPARE, the single-instruction Huffman decoder — every one of these trades machine simplicity for bytes on the wire. It is a rare example of an ISA designed under a constraint that no CPU has.

And it is a reminder of how specifications fail. Thirty-six instructions, one document, and it still took a users’ guide, a torture-test suite, and a corrections RFC over four years before implementations reliably agreed. The UDVM’s afterlife is a decent argument that a specification is not finished when the syntax is defined — it is finished when there is a test suite that disagrees with you.