                         The MVCOMP compression format
                                 Mateusz Viste

                            Last update: 2026-10-07


MVCOMP is a minimalist compression format. A decompressor fits in under 20
lines of C, and the method is meant for machines with little memory, such as
an 8086 with 16K of RAM.

A compressed file is a list of 16-bit words. There is no header, no stored
length and no checksum.

Each word is stored little-endian, the 8086 order: the low byte first, then
the high byte.

The files are usually a little larger than ZIP at its strongest setting,
typically by less than 10 percentage points.


=== HOW TO READ A WORD ========================================================

The decoder keeps an internal counter, starting at zero. It is the number of
raw data words still to come. The decoder reads 16-bit words from the input
and classifies them in this order:

  1. If the counter is not zero, the word is raw data (TYPE 3), whatever its
     bits are. The counter is then decreased by one.
  2. Otherwise, if the top four bits are zeroed, the word starts a run of new
     raw-data bytes (TYPE 2).
  3. Otherwise the word is a back reference (TYPE 1): a copy of bytes already
     written.

Only a TYPE 2 word sets the counter. While the counter is not zero, the top
four bits are not tested, and both bytes of the word are raw data.


=== TOKEN TYPE 1: "BACK REFERENCE" ============================================

Token format is LLLL OOOO OOOO OOOO

bits 15..12   LLLL            how many bytes to copy, minus one (1 .. 15)
bits 11..0    OOOO OOOO OOOO  how far back to start, minus one (0 .. 4095)

  copy length = LLLL + 1     is 2 .. 16 bytes
  distance    = OOOO + 1     is 1 .. 4096 bytes

The copy starts (distance) bytes before the next byte to be written, and it
must start inside the output produced so far. A decoder keeps the last 4096
output bytes. LLLL is never zero (a one-byte copy is not a valid token
because a top nibble of zero is a TYPE 2 token).

The copy may be longer than the distance. The source and the destination then
overlap. Copy one byte at a time, forward. Each new byte becomes part of the
source, so the string repeats itself.

Once the output ends in "hello", a copy of length 10 and distance 5 appends
"hellohello". The fifteen bytes "hellohellohello" are the result. The first
five bytes of the copy are the word already written. The next five are that
same word again, read from the bytes the copy has just written.

The same idea works with one letter: a single "a", then a copy of length 4 and
distance 1, is "aaaaa". Such case is a form of run-length encoding.

"hellohellohello" on disk, hex:

  68 02     word 0x0268   TYPE 2, the byte 'h', two raw words follow
  65 6c     word 0x6c65   TYPE 3, the bytes 'e', 'l'
  6c 6f     word 0x6f6c   TYPE 3, the bytes 'l', 'o'
  04 90     word 0x9004   TYPE 1, LLLL = 9, OOOO = 4
                          length 10, distance 5

"aaaaa" on disk, hex:

  61 00     word 0x0061   TYPE 2, the byte 'a', no raw word follows
  00 30     word 0x3000   TYPE 1, LLLL = 3, OOOO = 0
                          length 4, distance 1


=== TOKEN TYPE 2: "LITERAL STRING START" ======================================

Token format is 0000 UUUU BBBB BBBB

This word starts a run of bytes stored as-is (raw data).

bits 15..12   0000           the top nibble is zero, so this is TYPE 2
bits 11..8    UUUU           how many raw words (TYPE 3) follow
bits 7..0     BBBB BBBB      the first new byte

The entire run is (2 * UUUU) + 1 bytes long. That length is always odd, and it
is at most 31 (UUUU = 15). The bytes are written in the order they appear.


=== TOKEN TYPE 3: "LITERAL STRING CONTINUATION" ===============================

A TYPE 3 word is not a bit field. Both bytes are raw data, the low byte first,
then the high byte. These two bytes may be anything, including a top nibble of
zero. Exactly UUUU such words follow the TYPE 2 token. The next word is
classified again, with the counter back at zero.


===============================================================================
