LzwEncoder module
Posted: Wed Jan 15, 2014 7:28 am
A small lzw encoder module.
The return value of the Encode procedure is the number of bytes written to the output buffer.
You have to make sure yourself the output buffer is big enough since there are no checks.
I've read somewhere the theoretical worst case output is 1.41*(number of input bytes)+3 .
Version history :
v0.0.3 Fixed an issue with clearing the code table.
The return value of the Encode procedure is the number of bytes written to the output buffer.
You have to make sure yourself the output buffer is big enough since there are no checks.
I've read somewhere the theoretical worst case output is 1.41*(number of input bytes)+3 .
Code: Select all
DeclareModule LzwEncoder; v0.0.3r
Declare.i Encode(*input.Ascii, *output.Unicode, bytes, min_codesize = 8)
EndDeclareModule
Module LzwEncoder
Global Dim CodeTree.u(1048831)
Procedure InitCodeTree()
Protected a.a
For a = 0 To 255
CodeTree(1048576 + a) = a
Next
EndProcedure
InitCodeTree()
Macro OutputCode(outcode)
bits | outcode << bitcount : bitcount + codesize
If bitcount >= 16
*output\u = bits : *output + 2
bits >> 16
bitcount - 16
EndIf
EndMacro
Macro FlushOutput()
*output\u = bits
*output + (bitcount + 7) >> 3
EndMacro
Procedure.i Encode(*input.Ascii, *output.Unicode, bytes, min_codesize = 8)
Protected *o = *output
Protected.i codesize = min_codesize + 1
Protected.i clrcode = 1 << min_codesize
Protected.i endcode = clrcode + 1, nextcode = clrcode + 2
Protected.i bits, bitcount, a, idx, node = 4096
OutputCode(clrcode)
FillMemory(@CodeTree(), 2097152, 16)
While bytes
a = *input\a : *input + 1
idx = CodeTree(node << 8 | a)
If idx > 4096
CodeTree(node << 8 | a) = nextcode
idx = a
OutputCode(node)
codesize + nextcode >> codesize
nextcode + 1
If codesize > 12
codesize = 12
OutputCode(clrcode)
FillMemory(@CodeTree(), 2097152, 16)
codesize = min_codesize + 1
nextcode = clrcode + 2
EndIf
EndIf
node = idx
bytes - 1
Wend
OutputCode(node)
OutputCode(endcode)
FlushOutput()
ProcedureReturn *output - *o
EndProcedure
EndModulev0.0.3 Fixed an issue with clearing the code table.
