#!/usr/bin/env python3
from pprint import pprint as P
import struct

def test(data_in, data_out):
    print("==========================")
    print("IN: %s"%data_in)
    try:
        r = decode(data_in)
    except:
        print("ERR: exception during decoding")
    else:
        print("FINAL OUT: %s"%r)
        if r == data_out:
            print("MATCH")
        else:
            print("ERR: decompressed output doesnt match %d %d"%(len(r), len(data_out)))

def main():

    test(bytes.fromhex(" ff ff ff 1f 61 62 63 17 00 0f ff 26 01"),
         b'abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc'+
         b'abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc'+
         b'abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc'+
         b'abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc'+
         b'abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc')

    test(bytes.fromhex('ff ff ff 7f ff 07 00 0f ff 00 00 fc ff 01 00'),
         b'\xff'*(1024*128))

def decode(ibuf):
    obuf = bytearray()
    BufferedFlags = 0
    BufferedFlagCount = 0
    InputPosition = 0
    OutputPosition = 0
    LastLengthHalfByte = 0

    def output(x):
        obuf.append(x)
        #print("OUT: %02x"%x)
    
    while True:
        if BufferedFlagCount == 0:
            # Read 4 bytes at InputPosition
            BufferedFlags = struct.unpack_from('<I', ibuf, InputPosition)[0] 
            InputPosition += 4
            BufferedFlagCount = 32
        BufferedFlagCount = BufferedFlagCount - 1
        if (BufferedFlags & (1 << BufferedFlagCount)) == 0:
            # Copy 1 byte from InputPosition to OutputPosition.  Advance both.
            output(ibuf[InputPosition])
            InputPosition += 1
            OutputPosition += 1
        else:
            if InputPosition == len(ibuf):
                # Decompression is complete.  Return with success.
                return obuf
            # Read 2 bytes from InputPosition
            MatchBytes = struct.unpack_from('<H', ibuf, InputPosition)[0]
            InputPosition += 2
            MatchLength = MatchBytes % 8
            MatchOffset = (MatchBytes // 8) + 1
            if MatchLength == 7:
                if LastLengthHalfByte == 0:
                    #read 1 byte from InputPosition
                    MatchLength = ibuf[InputPosition]
                    MatchLength = MatchLength % 16
                    LastLengthHalfByte = InputPosition
                    InputPosition += 1
                else:
                    # read 1 byte from LastLengthHalfByte position
                    MatchLength = ibuf[LastLengthHalfByte]
                    MatchLength = MatchLength / 16
                    LastLengthHalfByte = 0
                if MatchLength == 15:
                    # read 1 byte from InputPosition
                    MatchLength = ibuf[InputPosition]
                    InputPosition += 1
                    if MatchLength == 255:
                        # read 2 bytes from InputPosition
                        MatchLength = struct.unpack_from('<H', ibuf, InputPosition)[0]
                        InputPosition += 2
                        if MatchLength < 15 + 7:
                           raise Exception("error")
                        MatchLength -= (15 + 7)
                    MatchLength += 15
                MatchLength += 7
            MatchLength += 3
            for i in range(MatchLength):# i = 0 to MatchLength - 1:
                # Copy 1 byte from OutputBuffer[OutputPosition - MatchOffset]
                output(obuf[OutputPosition-MatchOffset])
                OutputPosition += 1
        
if __name__ == '__main__':
    main()
