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 if math.fmod(i, 100) == 0 then QH_Timeslice_Yield() end 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   local ct = 0
 196   for _, v in ipairs(inputstatic) do
 197     ct = ct + 1
 198     if ct == 10 then QH_Timeslice_Yield() ct = 0 end
 199     table.insert(inpstat, dictize(idc, v))
 200   end
 201
 202   return idc, #inputdict, inpstat
 203 end
 204
 205 local function QH_LZW_Compress_Dicts_Prepared(input, idprepped, idpreppedsize, outputdict, isprepped)
 206   input = dictize(idprepped, input)
 207
 208   local bits, dsize = 1, 2
 209   if not outputdict then bits = 8 else while dsize < #outputdict do bits = bits + 1 ; dsize = dsize * 2 end end
 210   QuestHelper: Assert(not outputdict or #outputdict == dsize)
 211
 212   local comp = QH_LZW_Compress(input, idpreppedsize, bits, isprepped)
 213
 214   if outputdict then
 215     local origcomp = comp
 216     local im = {}
 217     for i = 1, #origcomp do Merger.Add(im, outputdict:sub(strbyte(origcomp:sub(i, i)) + 1)) end
 218     comp = Merger.Finish(im)
 219   end
 220
 221   return comp
 222 end
 223
 224 local function QH_LZW_Compress_Dicts(input, inputdict, outputdict, inputstatic)
 225   local inproc = input
 226   local inpstat = inputstatic
 227   if inputdict then
 228     local idc = mdict(inputdict)
 229
 230     inproc = dictize(idc, input)
 231
 232     if inputstatic then
 233       inpstat = {}
 234       for _, v in ipairs(inputstatic) do
 235         table.insert(inpstat, dictize(idc, v))
 236       end
 237     end
 238
 239     QuestHelper:ReleaseTable(idc)
 240   end
 241
 242   local bits, dsize = 1, 2
 243   if not outputdict then bits = 8 else while dsize < #outputdict do bits = bits + 1 ; dsize = dsize * 2 end end
 244   QuestHelper: Assert(not outputdict or #outputdict == dsize)
 245
 246   local comp = QH_LZW_Compress(inproc, inputdict and #inputdict or 256, bits, inpstat)
 247
 248   if outputdict then
 249     local origcomp = comp
 250     local im = {}
 251     for i = 1, #origcomp do Merger.Add(im, outputdict:sub(strbyte(origcomp:sub(i, i)) + 1)) end
 252     comp = Merger.Finish(im)
 253   end
 254
 255   return comp
 256 end
 257
 258 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
 259   QuestHelper: Assert(not outputdict)
 260   QuestHelper: Assert(inputdict)
 261
 262   local decomp = QH_LZW_Decompress(compressed, #inputdict, 8, ispreppred)
 263
 264   local ov = {}
 265   for i = 1, #decomp do
 266     Merger.Add(ov, inputdict:sub(decomp:byte(i) + 1, decomp:byte(i) + 1))
 267   end
 268   return Merger.Finish(ov)
 269 end
 270
 271 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
 272   QuestHelper: Assert(not outputdict)
 273   QuestHelper: Assert(inputdict)
 274
 275   local inpstat = inputstatic
 276   if inputdict and inputstatic then
 277     local idc = mdict(inputdict)
 278
 279     inpstat = {}
 280     for _, v in ipairs(inputstatic) do
 281       table.insert(inpstat, dictize(idc, v))
 282     end
 283
 284     QuestHelper:ReleaseTable(idc)
 285   end
 286
 287   local decomp = QH_LZW_Decompress(compressed, #inputdict, 8, inpstat)
 288
 289   local ov = {}
 290   for i = 1, #decomp do
 291     Merger.Add(ov, inputdict:sub(decomp:byte(i) + 1, decomp:byte(i) + 1))
 292   end
 293   return Merger.Finish(ov)
 294 end
 295
 296 QH_LZW_Prepare_Arghhacky = QH_LZW_Prepare -- need to rig up a better mechanism for this really
 297 QH_LZW_Decompress_Dicts_Arghhacky = QH_LZW_Decompress_Dicts -- need to rig up a better mechanism for this really
 298 QH_LZW_Decompress_Dicts_Prepared_Arghhacky = QH_LZW_Decompress_Dicts_Prepared -- need to rig up a better mechanism for this really
 299
 300 function QH_Collect_LZW_Init(_, API)
 301   Merger = API.Utility_Merger
 302   QuestHelper: Assert(Merger)
 303
 304   Bitstream = API.Utility_Bitstream
 305   QuestHelper: Assert(Bitstream)
 306
 307   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}
 308 end
 309
 310 -- old debug code :)
 311
 312 --[[
 313 print("hello")
 314
 315 QH_LZW_Compress("TOBEORNOTTOBEORTOBEORNOT", 256, 8)
 316 ]]
 317
 318 --[[
 319 QuestHelper:TextOut("lulz")
 320
 321 local inq = "ABABABABA"
 322 local alpha = 253
 323 local bits = 7
 324
 325 str = QH_LZW_Compress(inq, alpha, bits)
 326 tvr = ""
 327 for i = 1, #str do
 328   tvr = tvr .. string.format("%d ", strbyte(str, i))
 329 end
 330 QuestHelper:TextOut(tvr)
 331
 332 ret = QH_LZW_Decompress(str, alpha, bits)
 333 QuestHelper:TextOut(ret)
 334
 335 QuestHelper: Assert(inq == ret)
 336 ]]