                   a few words about in-place decompression

                         Mateusz Viste, October 2024
                            Last update: 2026-10-05


There are situations where it makes sense to fill a memory buffer with a block
of compressed data, and decompress the data within the same buffer. This is
called in-place decompression.

To do so, you need to know up front the maximum size of the uncompressed data
so you can allocate a buffer that is big enough. You then copy the compressed
data to the end of the buffer and start decompressing it at the start of the
buffer:

  +--- buffer ---+
  |       CCCCCCC|   CCC... = compressed data
   0123456789ABCD

Here the compressed data is placed at offset 0x07 of the buffer. Depacking will
start writing uncompressed data at offset 0, and move forward, eventually
getting to this:

  +--- buffer ---+
  |UUUUUUUUUUUUUU|   UUU... = uncompressed data
   0123456789ABCD

The buffer usually has to be bigger than the uncompressed data, though. Two
things force that. The compressed image may itself be larger than the
uncompressed image, so it has to fit. And the write cursor can move forward
faster than the read cursor, which means the compressed bytes have to start
far enough to the right that the write cursor reaches them only after they
have been read. In practice, the buffer post-decompression is rather this:

  +---- buffer ----+
  |UUUUUUUUUUUUUUCC|  UU... = uncompressed data  CC = compressed leftovers
   0123456789ABCDEF


How big should the buffer be then?

Calculating the size of the decompression buffer that will guarantee proper
in-place MVCOMP decompression can be calculated as follows (integer division):

  DECOMP_BUF_SIZ = UNCOMP_DATA_LEN + (UNCOMP_DATA_LEN / 31) + 2

The above formula covers all worst-case scenarios. Most files need less margin
than this, and some need none. MVSIZE.C measures one already compressed file:
it reports the smallest offset at which the compressed bytes can sit. The
buffer is that offset plus the compressed length, and it is also at least the
uncompressed length.


// WHERE THE 31 COMES FROM //

A back reference is one 16-bit word in and 2 to 16 bytes out. It is what
moves the write cursor ahead of the read cursor. It is also what shrinks the
compressed image, so with a buffer sized from the uncompressed length the
compressed bytes sit further to the right and the gap grows.

A literal group goes the other way. One literal token plus its raw words emits
1 + 2*UUUU bytes and consumes exactly one more byte than that. The decoder
loads a word before writing it, so during a literal group the write cursor
stays behind the read cursor. The cost shows up as a compressed image larger
than the output:

  UUUU = 15    31 output bytes, 32 token bytes, overhead 1
  UUUU = 0     1 output byte, 2 token bytes, overhead 1

MVCOMP fills groups up to 31 bytes. A run of 31*k bytes is therefore k extra
bytes, which is the 1/31 ratio. A group length is always odd, so a non-zero
even tail is two groups (an odd group and a final one-byte group) and costs
two extra bytes, on top of the full groups of 31. Incompressible input is this
case for the whole file. The write cursor stays behind the read cursor,
because each literal word is loaded before its bytes are stored, but the
compressed image is longer than the output. A buffer of UNCOMP_DATA_LEN +
extra is exactly that image, so the compressed bytes start at offset 0 and the
gap in front of them is zero.

Highly compressible input does not add a second penalty on top of that extra.
Long back references shrink the compressed image by more than the literal
groups grew it, and the buffer falls back to the uncompressed length.


// A SMALLER EXAMPLE OF THE SAME IDEA //

Imagine a dummy compressor whose words are AAAA and BBBB. AAAA decompresses
to 3 bytes, BBBB to 6:

  +----buff----+
  |            |
  |AAAABBBBAAAA|   <-- compressed string
  |aaabbbbbbaaa|   <-- decompressed string

With no margin, by the time BBBB has been decoded the write cursor is already
on top of the second AAAA. The two AAAA words take more space in the stream
than the 3-byte strings they add to the output, and BBBB then jumps the write
cursor across the unread word.

The safe fix in that toy format is to grow the buffer by the worst word's
overhead. AAAA is 4 bytes of stream for 3 bytes of output, overhead 1/3, so
four extra bytes:

  +------buff------+
  |                |
  |    AAAABBBBAAAA|   <-- compressed string
  |aaabbbbbbaaa    |   <-- decompressed string

MVCOMP's version of "the worst word" is the literal group, and the worst
group mvslow and mvcomp emit in bulk is 32 bytes of tokens for 31
bytes of output. The extra buffer rule is that observation, plus the even tail
a single group cannot hold.
