Fallout 1 LZ decompressor

fo1_lz77.c

#include <stdint.h>
#include <stddef.h>

size_t lz77_decode(const uint8_t *src, uint8_t *dst) {

  // size of ring buffer
  static const uint32_t N = 4096;
  // upper limit for match_length
  static const uint32_t F = 18;
  // wrap mask for ring buffer
  static const uint32_t WRAP = N - 1;
  // encode string into position and length if match length > than this
  static const uint32_t THRESHOLD = 2;
  // ring buffer of size N with extra F-1 bytes for string comparison
  uint8_t text_buf[N + F - 1];

  uint32_t i, j;
  // dst base used later to recover bytes written
  const uint8_t *base = dst;

  // clear ring buffer
  for (i = 0; i < N - F; i++) {
    text_buf[i] = ' ';
  }

  // set initial ring position
  uint32_t r = N - F;
  // clear flags
  uint16_t flags = 0;

  // loop until all is decoded
  for (;;) {
    // shift flags down 1 bit
    flags >>= 1;
    // if high byte of flags is 0
    if ((flags & 0xff00) == 0) {
      // read byte
      const uint8_t c = *src++;
      if (!c) break;
      // use high bytes to loop 8 times
      flags = c | 0xff00;
    }
    // if LSB in flags is 1
    if (flags & 1) {
      // read byte
      const uint8_t c = *src++;
      if (!c) break;
      // write byte directly to output
      *(dst++) = c;
      // insert into ring buffer
      text_buf[r++] = c;
      r &= WRAP;
    // if LSB in flags is 0
    } else {
      // read two src byte
      i = *src++;
      j = *src++;
      // high nibble has ring offset high nibble
      i |= (j & 0xf0) << 4;
      // low nibble has entry match count
      j  = (j & 0x0f) + THRESHOLD;
      // loop for byte count
      for (int k = 0; k <= j; k++) {
        // read byte from ring buffer
        const uint8_t c = text_buf[(i + k) & WRAP];
        // put byte into output file
        *(dst++) = c;
        // insert into ring buffer
        text_buf[r++] = c;
        r &= WRAP;
      } // for
    }
  } // for
  // number of bytes written
  return dst - base;
}