Navigation
Login/Logout
NUB
Magic Mêlée™
Make The Change
MongoDB Drivers
Windows Template Library (WTL)
Sandbox
Wiki Markup
Fire One
Main Page
Random Page
Create a new Page
All Pages
Categories
Administration
File Management
Language Selection
Your Profile
Create Account
Quick Search
Advanced Search »
Back
History
deLZW
The FAST System (core to [Monster Bash|Monster Bash] and [http://www.mobygames.com/game/dos/scubaventure-the-search-for-pirates-treasure|ScubaVenture]) uses a custom method to pack data files that is based on the LZW algorithm (See [http://en.wikipedia.org/wiki/LZW|LZW on Wikipedia)]). SEA, Inc. developed the original master compression algorithm and file format (.ARC). It is called LZW compression (Limpel-Ziv-Welch: the scientists who cooperated to create/invent it). CompuServe, Inc. used LZW as the basis of their .GIF design. I call LZW and ZIP "masterful" because they foregoe the "compression lookup table" required by Huffman encoding which was boss before LZW. This made this kind of compression king of the hill for quite a while. After I had written the resource file code for Monster Bash, the LZW algorithm was bought by UniSys, Inc. and patented. At this time, I am pretty sure that THAT particular patent has expired. I adapted the LZW algorithm for FAST somewhat, but a standard decoder for it might decompress the files to the form that they are used internally by Monster Bash. Note that, in addition, each of the file types has it own compression/interpretation scheme also (adapted to the particular type of data). Look here for information on [Monster Bash|Hacking Monster Bash]. Monster Bash is actually a HUGE game (well, certainly big for its time anyway). Incredible that we managed to squeeze each of the chapters onto single floppies. (toot, toot!). You can find a good discussion of the LZW algorithm and commented C code here: [http://www.dogma.net/markn/articles/lzw/lzw.htm]. <hr> This is a conversion from 8086 machine code to C of deLZW: {{{{ /* 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]. */ <nowiki> 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 WORD[0x3D02/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(); } </nowiki>}}}}