LzwEncoder module

[wilbert]

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 .

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
  
EndModule

Version history :

v0.0.3 Fixed an issue with clearing the code table.

[netmaestro]

Excellent work Wilbert! I plugged this into my Gif Workshop project and tested with several images and animations. Output is perfect and the speed (depending on the task) ranges from 2x faster than my code up to 5 times faster. Nice clean fast work, as always.