collect_lzw.lua

   1 QuestHelper_File["collect_lzw.lua"] = "Development Version"
   2 QuestHelper_Loadtime["collect_lzw.lua"] = GetTime()
   3
   4 local Merger
   5 local Bitstream
   6
   7 local function cleanup(tab)
   8   for _, v in pairs(tab) do
   9     QuestHelper:ReleaseTable(v)
  10   end
  11   QuestHelper:ReleaseTable(tab)
  12 end
  13
  14 local function QH_LZW_Decompress(input, tokens, outbits, inputstatic)
  15   local d = QuestHelper:CreateTable("lzw")
  16   local i
  17   for i = 0, tokens-1 do
  18     d[i] = QuestHelper:CreateTable("lzw")
  19     d[i][0] = string.char(i)
  20   end
  21
  22   local dsize = tokens + 1  -- we use the "tokens" value as an EOF marker
  23
  24   if inputstatic then
  25     local used = QuestHelper:CreateTable("lzw")
  26     for _, v in ipairs(inputstatic) do
  27       for i = #v, 2, -1 do
  28         local subi = v:sub(1, i)
  29         if not used[subi] then
  30           used[subi] = true
  31
  32           d[bit.mod(dsize, tokens)][math.floor(dsize / tokens)] = subi
  33           dsize = dsize + 1
  34         else
  35           break
  36         end
  37       end
  38     end
  39     QuestHelper:ReleaseTable(used)
  40   end
  41
  42   local bits = 1
  43   local nextbits = 2
  44
  45   while nextbits < dsize do bits = bits + 1; nextbits = nextbits * 2 end
  46
  47   local i = Bitstream.Input(input, outbits)
  48   local rv = {}
  49
  50   local idlect = 0
  51
  52   local tok = i:depend(bits)
  53   if tok == tokens then cleanup(d) return "" end -- Okay. There's nothing. We get it.
  54
  55   Merger.Add(rv, d[bit.mod(tok, tokens)][math.floor(tok / tokens)])
  56   local w = d[bit.mod(tok, tokens)][math.floor(tok / tokens)]
  57   while true do
  58     if idlect == 25 then
  59       QH_Timeslice_Yield()
  60       idlect = 0
  61     else
  62       idlect = idlect + 1
  63     end
  64
  65     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.
  66     if dsize > nextbits then
  67       bits = bits + 1
  68       nextbits = nextbits * 2
  69     end
  70
  71     tok = i:depend(bits)
  72     if tok == tokens then break end -- we're done!
  73
  74     local entry
  75     if d[bit.mod(tok, tokens)][math.floor(tok / tokens)] then
  76       entry = d[bit.mod(tok, tokens)][math.floor(tok / tokens)]
  77     elseif tok == dsize - 1 then
  78       entry = w .. w:sub(1, 1)
  79     else
  80       QuestHelper: Assert(false, "faaaail")
  81     end
  82     Merger.Add(rv, entry)
  83
  84     d[bit.mod(dsize - 1, tokens)][math.floor((dsize - 1) / tokens)] = w .. entry:sub(1, 1) -- Naturally, we're writing to one *less* than dsize, since we already incremented.
  85
  86     w = entry
  87   end
  88
  89   cleanup(d)
  90
  91   return Merger.Finish(rv)
  92 end
  93
  94 local function QH_LZW_Compress(input, tokens, outbits, inputstatic)
  95   -- shared init code
  96   local d = {}
  97   local i
  98   for i = 0, tokens-1 do
  99     d[string.char(i)] = {[""] = i}
 100   end
 101
 102   local dsize = tokens + 1  -- we use the "tokens" value as an EOF marker
 103
 104   if inputstatic then
 105     for _, v in ipairs(inputstatic) do
 106       local da = d[v:sub(1, 1)]
 107       for i = #v, 2, -1 do
 108         local b = v:sub(2, i)
 109         if not da[b] then
 110           da[b] = dsize
 111           dsize = dsize + 1
 112         else
 113           break
 114         end
 115       end
 116     end
 117   end
 118
 119   local bits = 1
 120   local nextbits = 2
 121
 122   while nextbits < dsize do bits = bits + 1; nextbits = nextbits * 2 end
 123
 124   local r = Bitstream.Output(outbits)
 125
 126   local idlect = 0
 127
 128   local w = ""
 129   for ci = 1, #input do
 130     if idlect == 100 then
 131       QH_Timeslice_Yield()
 132       idlect = 0
 133     else
 134       idlect = idlect + 1
 135     end
 136
 137     local c = input:sub(ci, ci)
 138     local wcp = w .. c
 139     if d[wcp:sub(1, 1)][wcp:sub(2)] then
 140       w = wcp
 141     else
 142       r:append(d[w:sub(1, 1)][w:sub(2)], bits)
 143       d[wcp:sub(1, 1)][wcp:sub(2)] = dsize
 144       dsize = dsize + 1
 145       if dsize > nextbits then
 146         bits = bits + 1
 147         nextbits = nextbits * 2
 148       end
 149       w = c
 150     end
 151   end
 152
 153   if w ~= "" then
 154     r:append(d[w:sub(1, 1)][w:sub(2)], bits)
 155
 156     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.
 157     if dsize > nextbits then
 158       bits = bits + 1
 159       nextbits = nextbits * 2
 160     end
 161   end
 162
 163   r:append(tokens, bits)
 164
 165   local rst = r:finish()
 166   QuestHelper: Assert(QH_LZW_Decompress(rst, tokens, outbits, inputstatic) == input) -- yay
 167
 168   return rst
 169 end
 170
 171 local function mdict(inputdict)
 172   local idc = QuestHelper:CreateTable("lzw mdict")
 173   for i = 1, #inputdict do idc[inputdict:sub(i, i)] = strchar(i - 1) end
 174   return idc
 175 end
 176
 177 local function dictize(idcl, stt)
 178   local im = QuestHelper:CreateTable("lzw dictize")
 179   for i = 1, #stt do
 180     local subl = idcl[stt:sub(i, i)]
 181     QuestHelper: Assert(subl)
 182     Merger.Add(im, subl)
 183   end
 184   local result = Merger.Finish(im)
 185   QuestHelper:ReleaseTable(im)
 186   return result
 187 end
 188
 189 local function QH_LZW_Prepare(inputdict, inputstatic)
 190   QuestHelper: Assert(inputdict and inputstatic)
 191
 192   local idc = mdict(inputdict)
 193
 194   local inpstat = {}
 195   for _, v in ipairs(inputstatic) do
 196     table.insert(inpstat, dictize(idc, v))
 197   end
 198
 199   return idc, #inputdict, inpstat
 200 end
 201
 202 local function QH_LZW_Compress_Dicts_Prepared(input, idprepped, idpreppedsize, outputdict, isprepped)
 203   input = dictize(idprepped, input)
 204
 205   local bits, dsize = 1, 2
 206   if not outputdict then bits = 8 else while dsize < #outputdict do bits = bits + 1 ; dsize = dsize * 2 end end
 207   QuestHelper: Assert(not outputdict or #outputdict == dsize)
 208
 209   local comp = QH_LZW_Compress(input, idpreppedsize, bits, isprepped)
 210
 211   if outputdict then
 212     local origcomp = comp
 213     local im = {}
 214     for i = 1, #origcomp do Merger.Add(im, outputdict:sub(strbyte(origcomp:sub(i, i)) + 1)) end
 215     comp = Merger.Finish(im)
 216   end
 217
 218   return comp
 219 end
 220
 221 local function QH_LZW_Compress_Dicts(input, inputdict, outputdict, inputstatic)
 222   local inproc = input
 223   local inpstat = inputstatic
 224   if inputdict then
 225     local idc = mdict(inputdict)
 226
 227     inproc = dictize(idc, input)
 228
 229     if inputstatic then
 230       inpstat = {}
 231       for _, v in ipairs(inputstatic) do
 232         table.insert(inpstat, dictize(idc, v))
 233       end
 234     end
 235
 236     QuestHelper:ReleaseTable(idc)
 237   end
 238
 239   local bits, dsize = 1, 2
 240   if not outputdict then bits = 8 else while dsize < #outputdict do bits = bits + 1 ; dsize = dsize * 2 end end
 241   QuestHelper: Assert(not outputdict or #outputdict == dsize)
 242
 243   local comp = QH_LZW_Compress(inproc, inputdict and #inputdict or 256, bits, inpstat)
 244
 245   if outputdict then
 246     local origcomp = comp
 247     local im = {}
 248     for i = 1, #origcomp do Merger.Add(im, outputdict:sub(strbyte(origcomp:sub(i, i)) + 1)) end
 249     comp = Merger.Finish(im)
 250   end
 251
 252   return comp
 253 end
 254
 255 local function QH_LZW_Decompress_Dicts_Prepared(compressed, inputdict, outputdict, ispreppred) -- this is kind of backwards - we assume that "outputdict" is the dictionary that "compressed" is encoded in
 256   QuestHelper: Assert(not outputdict)
 257   QuestHelper: Assert(inputdict)
 258
 259   local decomp = QH_LZW_Decompress(compressed, #inputdict, 8, ispreppred)
 260
 261   local ov = {}
 262   for i = 1, #decomp do
 263     Merger.Add(ov, inputdict:sub(decomp:byte(i) + 1, decomp:byte(i) + 1))
 264   end
 265   return Merger.Finish(ov)
 266 end
 267
 268 local function QH_LZW_Decompress_Dicts(compressed, inputdict, outputdict, inputstatic) -- this is kind of backwards - we assume that "outputdict" is the dictionary that "compressed" is encoded in
 269   QuestHelper: Assert(not outputdict)
 270   QuestHelper: Assert(inputdict)
 271
 272   local inpstat = inputstatic
 273   if inputdict and inputstatic then
 274     local idc = mdict(inputdict)
 275
 276     inpstat = {}
 277     for _, v in ipairs(inputstatic) do
 278       table.insert(inpstat, dictize(idc, v))
 279     end
 280
 281     QuestHelper:ReleaseTable(idc)
 282   end
 283
 284   local decomp = QH_LZW_Decompress(compressed, #inputdict, 8, inpstat)
 285
 286   local ov = {}
 287   for i = 1, #decomp do
 288     Merger.Add(ov, inputdict:sub(decomp:byte(i) + 1, decomp:byte(i) + 1))
 289   end
 290   return Merger.Finish(ov)
 291 end
 292
 293 QH_LZW_Prepare_Arghhacky = QH_LZW_Prepare -- need to rig up a better mechanism for this really
 294 QH_LZW_Decompress_Dicts_Arghhacky = QH_LZW_Decompress_Dicts -- need to rig up a better mechanism for this really
 295 QH_LZW_Decompress_Dicts_Prepared_Arghhacky = QH_LZW_Decompress_Dicts_Prepared -- need to rig up a better mechanism for this really
 296
 297 function QH_Collect_LZW_Init(_, API)
 298   Merger = API.Utility_Merger
 299   QuestHelper: Assert(Merger)
 300
 301   Bitstream = API.Utility_Bitstream
 302   QuestHelper: Assert(Bitstream)
 303
 304   API.Utility_LZW = {Compress = QH_LZW_Compress, Decompress = QH_LZW_Decompress, Compress_Dicts = QH_LZW_Compress_Dicts, Decompress_Dicts = QH_LZW_Decompress_Dicts, Prepare = QH_LZW_Prepare, Compress_Dicts_Prepared = QH_LZW_Compress_Dicts_Prepared, Decompress_Dicts_Prepared = QH_LZW_Decompress_Dicts_Prepared}
 305 end
 306
 307 -- old debug code :)
 308
 309 --[[
 310 print("hello")
 311
 312 QH_LZW_Compress("TOBEORNOTTOBEORTOBEORNOT", 256, 8)
 313 ]]
 314
 315 --[[
 316 QuestHelper:TextOut("lulz")
 317
 318 local inq = "ABABABABA"
 319 local alpha = 253
 320 local bits = 7
 321
 322 str = QH_LZW_Compress(inq, alpha, bits)
 323 tvr = ""
 324 for i = 1, #str do
 325   tvr = tvr .. string.format("%d ", strbyte(str, i))
 326 end
 327 QuestHelper:TextOut(tvr)
 328
 329 ret = QH_LZW_Decompress(str, alpha, bits)
 330 QuestHelper:TextOut(ret)
 331
 332 QuestHelper: Assert(inq == ret)
 333 ]]