Page History: deLZW

Compare Page Revisions

« Older Revision - Back to Page History - Newer Revision »

Page Revision: 2009/01/19 01:45

This is a conversion from 8086 machine code to C of the decompression code used by the FAST System (Monster Bash)

The compression algorithm is based on LZW data compression. You can find a good discussion of the algorithm and commented C code here: http://www.dogma.net/markn/articles/lzw/lzw.htm.

/* File: deLZW.c
   I know this is REAL fugly code with all the globals and no comments,
   but, for one, it is an adaption of a highly optimized piece of hand-coded
   8086 assembly code {circa 1992, the machine code for all of this 'C' code
   is only 378 bytes (eat your heart out, GCC and Visual C++ ;) }.
   For two, you can reference a commented copy of the LZW source from
   http://www.dogma.net/markn/articles/lzw/lzw.htm . */ 

typedef          int       BOOL;
typedef unsigned char      BYTE;
typedef unsigned short int WORD;
typedef unsigned long      DWORD;

static bool   eof, rep90;
static DWORD* src;   // input  cursor
static BYTE*  dst;   // output cursor
static BYTE*  edst;  // end of dst (original dst + dstSize)
static DWORD  buf;   // input bit buffer
static int    size;  // current number of bits per input code
static DWORD  mask;  // current mask to AND input bits with (== size**2 - 1)
static int    bufSize;  // number of good bits still in buf
static WORD*  table;
static WORD*  lastTableEntry;
static WORD*  newCode;  // points into table where the next bump
                        //   in code size will occur.

BOOL
initLZW() {
  table = new WORD0x3D02/2;
  return (int)table;
}

void
exitLZW() {
  delete table; table = 0;
}

static void
put(int code) {
  if (rep90) {
    rep90 = false;
    *dst++ = (BYTE)code;
  } else if (dst-1 != 0x90)
    *dst++ = (BYTE)code;
  else if (code == 0)
    rep90 = true;
  else {
    BYTE* d = dst-2;
    BYTE rep = *d++;
    while (--code)
      *d++ = rep;
    dst = d;
  }
}

static void
putCode(int code) {
  if (code <= 0x100)
    put(code);
  else {
    WORD* entryp = (WORD*)((BYTE*)table+code);
    putCode(*entryp++);
    code = *entryp;
    while (code > 0x100)
      code = *(WORD*)((BYTE*)table+code);
    put(code);
  }
}

static int reset();

static int
get() {
  int code;
  if (bufSize < size) {
    DWORD d = *src++;
    code = d << bufSize | buf;
    buf = d >> size - bufSize;
    bufSize += 32 - size;
  } else {
    code = buf;
    buf >>= size;
    bufSize -= size;
  }
  if ((code &= mask) > 0x100)
    code = code * 4 - 0x300;
  else if (code == 0x100) {
    if (lastTableEntry != table + (0x3D00/2)) {
      putCode(*lastTableEntry);
      if (dst == edst) {
        eof = true;
        return 0;
      }
    }
    code = reset();
  }
  return code;
}

static int
reset() {
  mask = 0x1FF;
  newCode = table + 0x500/2;
  buf = 0;
  size = 9; bufSize = 0;
  int code = get();
  *(lastTableEntry = table + 0x104/2) = (WORD)code;
  return code;
}

void
deLZW(void* _src, void *_dst, int dstSize) {
  bool preallocated = table != 0;
  if (!preallocated && !initLZW()) return;
  edst = (dst = (BYTE*)_dst) + dstSize;
  src = (DWORD*)_src;
  rep90 = true;
  eof = false;
  reset();
  do {
    int code = get();
    if (eof) break;
    if (lastTableEntry == table + (0x3D00/2)) {
      *lastTableEntry = (WORD)code;
      putCode(code);
    } else {
      putCode(*lastTableEntry++);
      *lastTableEntry++ = (WORD)code;
      *lastTableEntry   = (WORD)code;
      if (lastTableEntry == newCode)
        if (size == 12)
          putCode(*lastTableEntry);
        else {
          size++;
          mask = (mask << 1) + 1;
          newCode = (WORD*)((BYTE*)table + (1 << size + 2) - 0x300);
        }
    }
  } while (dst != edst);
  if (!preallocated) exitLZW();
}