lzs.py

# Lempel-Ziv-Stac (LZS) decompression
# Implementation found in sciw.exe

class LZSBitReader:
    def __init__(self, bytes):
        self.bytes = bytes
        self.gen = self.generator(bytes)

    def generator(self, bts):
        for b in bts:
            bi = ord(b)
            for i in xrange(8):
                yield int((bi >> (7 - i)) & 1)

    def getBit(self):
        return next(self.gen)

    def getBits(self, num):
        res = 0
        for i in xrange(0, num):
            res += self.getBit() << num - 1 - i
        return res
        
    def getLen(self):
        length = 2
        while True:
            bits = self.getBits(2)
            length += bits
            if bits != 3 or length >= 8:
                break
        if length == 8:
            while True:
                bits = self.getBits(4)
                length += bits
                if bits != 15:
                    break
        return length

def lzs_unpack(data):
    out = ""
    reader = LZSBitReader(data)
    while True:
        if reader.getBit() == 0:            # Uncompressed byte
            out += chr(reader.getBits(8))
        else:
            if reader.getBit() == 1:        # 7-bit offset
                offset = reader.getBits(7)
                if offset == 0:             # End Of Stream
                    break
            else:
                offset = reader.getBits(11) # 11-bit offset
            length = reader.getLen()
            if offset > len(out):
                raise ValueError("[LZS]: Dictionary underflow")
            for i in xrange(0, length):     # dic
                out += out[-offset]
    return out