collect_lzw.lua

   1 QuestHelper_File["collect_lzw.lua"] = "Development Version"
   2
   3 local Merger
   4
   5 local function QH_LZW_Bitstreamer_Output(outbits)
   6   return {
   7     r = {},
   8     cbits = 0,
   9     cval = 0,
  10
  11     append = function (self, value, bits)
  12       self.cbits = self.cbits + bits
  13       self.cval = bit.lshift(self.cval, bits)
  14       self.cval = self.cval + value
  15       while self.cbits >= outbits do
  16         Merger.Add(self.r, strchar(bit.rshift(self.cval, self.cbits - outbits)))
  17         self.cbits = self.cbits - outbits;
  18         self.cval = bit.band(self.cval, bit.lshift(1, self.cbits) - 1)
  19       end
  20     end,
  21     finish = function (self)
  22       if self.cbits > 0 then self:append(0, outbits - self.cbits) end
  23       return Merger.Finish(self.r)
  24     end
  25   }
  26 end
  27
  28 local function QH_LZW_Bitstreamer_Input(indata, outbits)
  29   return {
  30     cbits = 0,
  31     cval = 0,
  32     coffset = 1,
  33
  34     depend = function (self, bits)
  35       while self.cbits < bits do
  36         self.cbits = self.cbits + outbits
  37         self.cval = bit.lshift(self.cval, outbits) + strbyte(indata, self.coffset)
  38         self.coffset = self.coffset + 1
  39       end
  40       local rv = bit.rshift(self.cval, self.cbits - bits)
  41       self.cbits = self.cbits - bits;
  42       self.cval = bit.band(self.cval, bit.lshift(1, self.cbits) - 1)
  43       return rv
  44     end,
  45   }
  46 end
  47
  48 local function QH_LZW_Decompress(input, tokens, outbits)
  49   local d = {}
  50   local i
  51   for i = 0, tokens-1 do
  52     d[i] = string.char(i)
  53   end
  54
  55   local dsize = tokens + 1  -- we use the "tokens" value as an EOF marker
  56
  57   local bits = 1
  58   local nextbits = 2
  59
  60   while nextbits < dsize do bits = bits + 1; nextbits = nextbits * 2 end
  61
  62   local i = QH_LZW_Bitstreamer_Input(input, outbits)
  63   local rv = {}
  64
  65   local idlect = 0
  66
  67   local tok = i:depend(bits)
  68   if tok == tokens then return "" end -- Okay. There's nothing. We get it.
  69
  70   Merger.Add(rv, d[tok])
  71   local w = d[tok]
  72   while true do
  73     if idlect == 100 then
  74       QH_Timeslice_Yield()
  75       idlect = 0
  76     else
  77       idlect = idlect + 1
  78     end
  79
  80     dsize = dsize + 1 -- We haven't actually added the next element yet. However, we could in theory include it in the stream, so we need to adjust the number of bits properly.
  81     if dsize > nextbits then
  82       bits = bits + 1
  83       nextbits = nextbits * 2
  84     end
  85
  86     tok = i:depend(bits)
  87     if tok == tokens then break end -- we're done!
  88
  89     local entry
  90     if d[tok] then
  91       entry = d[tok]
  92     elseif tok == dsize - 1 then
  93       entry = w .. w:sub(1, 1)
  94     else
  95       QuestHelper: Assert(false, "faaaail")
  96     end
  97     Merger.Add(rv, entry)
  98
  99     d[dsize - 1] = w .. entry:sub(1, 1) -- Naturally, we're writing to one *less* than dsize, since we already incremented.
 100
 101     w = entry
 102   end
 103
 104   return Merger.Finish(rv)
 105 end
 106
 107 local function QH_LZW_Compress(input, tokens, outbits)
 108   -- shared init code
 109   local d = {}
 110   local i
 111   for i = 0, tokens-1 do
 112     d[string.char(i)] = i
 113   end
 114
 115   local dsize = tokens + 1  -- we use the "tokens" value as an EOF marker
 116
 117   local bits = 1
 118   local nextbits = 2
 119
 120   while nextbits < dsize do bits = bits + 1; nextbits = nextbits * 2 end
 121
 122   local r = QH_LZW_Bitstreamer_Output(outbits)
 123
 124   local idlect = 0
 125
 126   local w = ""
 127   for ci = 1, #input do
 128     if idlect == 100 then
 129       QH_Timeslice_Yield()
 130       idlect = 0
 131     else
 132       idlect = idlect + 1
 133     end
 134
 135     local c = input:sub(ci, ci)
 136     local wcp = w .. c
 137     if d[wcp] then
 138       w = wcp
 139     else
 140       r:append(d[w], bits)
 141       d[wcp] = dsize
 142       dsize = dsize + 1
 143       if dsize > nextbits then
 144         bits = bits + 1
 145         nextbits = nextbits * 2
 146       end
 147       w = c
 148     end
 149   end
 150   if w ~= "" then r:append(d[w], bits) end
 151
 152   dsize = dsize + 1   -- Our decompressor doesn't realize we're ending here, so it will have added a table entry for that last token. Sigh.
 153   if dsize > nextbits then
 154     bits = bits + 1
 155     nextbits = nextbits * 2
 156   end
 157   r:append(tokens, bits)
 158
 159   local rst = r:finish()
 160   QuestHelper: Assert(QH_LZW_Decompress(rst, tokens, outbits) == input) -- yay
 161
 162   return rst
 163 end
 164
 165 local function QH_LZW_Compress_Dicts(input, inputdict, outputdict)
 166   local inproc = input
 167   if inputdict then
 168     local idc = {}
 169     for i = 1, #inputdict do idc[inputdict:sub(i, i)] = strchar(i - 1) end
 170     local im = {}
 171     for i = 1, #input do Merger.Add(im, idc[input:sub(i, i)]) end
 172     inproc = Merger.Finish(im)
 173   end
 174
 175   local bits, dsize = 1, 2
 176   if not outputdict then bits = 8 else while dsize < #outputdict do bits = bits + 1 ; dsize = dsize * 2 end end
 177   QuestHelper: Assert(not outputdict or #outputdict == dsize)
 178
 179   local comp = QH_LZW_Compress(inproc, inputdict and #inputdict or 256, bits)
 180
 181   if outputdict then
 182     local origcomp = comp
 183     local im = {}
 184     for i = 1, #origcomp do Merger.Add(im, outputdict:sub(strbyte(origcomp:sub(i, i)) + 1)) end
 185     comp = Merger.Finish(im)
 186   end
 187
 188   return comp
 189 end
 190
 191 function QH_Collect_LZW_Init(_, API)
 192   Merger = API.Utility_Merger
 193   QuestHelper: Assert(Merger)
 194
 195   API.Utility_LZW = {Compress = QH_LZW_Compress, Decompress = QH_LZW_Decompress, Compress_Dicts = QH_LZW_Compress_Dicts}
 196 end
 197
 198 -- old debug code :)
 199
 200 --[[
 201 print("hello")
 202
 203 QH_LZW_Compress("TOBEORNOTTOBEORTOBEORNOT", 256, 8)
 204 ]]
 205
 206 --[[
 207 QuestHelper:TextOut("lulz")
 208
 209 local inq = "ABABABABA"
 210 local alpha = 253
 211 local bits = 7
 212
 213 str = QH_LZW_Compress(inq, alpha, bits)
 214 tvr = ""
 215 for i = 1, #str do
 216   tvr = tvr .. string.format("%d ", strbyte(str, i))
 217 end
 218 QuestHelper:TextOut(tvr)
 219
 220 ret = QH_LZW_Decompress(str, alpha, bits)
 221 QuestHelper:TextOut(ret)
 222
 223 QuestHelper: Assert(inq == ret)
 224 ]]