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 QH_LZW_Decompress(input, tokens, outbits)
   8   local d = {}
   9   local i
  10   for i = 0, tokens-1 do
  11     d[i] = {[0] = string.char(i)}
  12   end
  13
  14   local dsize = tokens + 1  -- we use the "tokens" value as an EOF marker
  15
  16   local bits = 1
  17   local nextbits = 2
  18
  19   while nextbits < dsize do bits = bits + 1; nextbits = nextbits * 2 end
  20
  21   local i = Bitstream.Input(input, outbits)
  22   local rv = {}
  23
  24   local idlect = 0
  25
  26   local tok = i:depend(bits)
  27   if tok == tokens then return "" end -- Okay. There's nothing. We get it.
  28
  29   Merger.Add(rv, d[bit.mod(tok, tokens)][math.floor(tok / tokens)])
  30   local w = d[bit.mod(tok, tokens)][math.floor(tok / tokens)]
  31   while true do
  32     if idlect == 100 then
  33       QH_Timeslice_Yield()
  34       idlect = 0
  35     else
  36       idlect = idlect + 1
  37     end
  38
  39     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.
  40     if dsize > nextbits then
  41       bits = bits + 1
  42       nextbits = nextbits * 2
  43     end
  44
  45     tok = i:depend(bits)
  46     if tok == tokens then break end -- we're done!
  47
  48     local entry
  49     if d[bit.mod(tok, tokens)][math.floor(tok / tokens)] then
  50       entry = d[bit.mod(tok, tokens)][math.floor(tok / tokens)]
  51     elseif tok == dsize - 1 then
  52       entry = w .. w:sub(1, 1)
  53     else
  54       QuestHelper: Assert(false, "faaaail")
  55     end
  56     Merger.Add(rv, entry)
  57
  58     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.
  59
  60     w = entry
  61   end
  62
  63   return Merger.Finish(rv)
  64 end
  65
  66 local function QH_LZW_Compress(input, tokens, outbits)
  67   -- shared init code
  68   local d = {}
  69   local i
  70   for i = 0, tokens-1 do
  71     d[string.char(i)] = {[""] = i}
  72   end
  73
  74   local dsize = tokens + 1  -- we use the "tokens" value as an EOF marker
  75
  76   local bits = 1
  77   local nextbits = 2
  78
  79   while nextbits < dsize do bits = bits + 1; nextbits = nextbits * 2 end
  80
  81   local r = Bitstream.Output(outbits)
  82
  83   local idlect = 0
  84
  85   local w = ""
  86   for ci = 1, #input do
  87     if idlect == 100 then
  88       QH_Timeslice_Yield()
  89       idlect = 0
  90     else
  91       idlect = idlect + 1
  92     end
  93
  94     local c = input:sub(ci, ci)
  95     local wcp = w .. c
  96     if d[wcp:sub(1, 1)][wcp:sub(2)] then
  97       w = wcp
  98     else
  99       r:append(d[w:sub(1, 1)][w:sub(2)], bits)
 100       d[wcp:sub(1, 1)][wcp:sub(2)] = dsize
 101       dsize = dsize + 1
 102       if dsize > nextbits then
 103         bits = bits + 1
 104         nextbits = nextbits * 2
 105       end
 106       w = c
 107     end
 108   end
 109   if w ~= "" then r:append(d[w:sub(1, 1)][w:sub(2)], bits) end
 110
 111   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.
 112   if dsize > nextbits then
 113     bits = bits + 1
 114     nextbits = nextbits * 2
 115   end
 116   r:append(tokens, bits)
 117
 118   local rst = r:finish()
 119   QuestHelper: Assert(QH_LZW_Decompress(rst, tokens, outbits) == input) -- yay
 120
 121   return rst
 122 end
 123
 124 local function QH_LZW_Compress_Dicts(input, inputdict, outputdict)
 125   local inproc = input
 126   if inputdict then
 127     local idc = {}
 128     for i = 1, #inputdict do idc[inputdict:sub(i, i)] = strchar(i - 1) end
 129     local im = {}
 130     for i = 1, #input do Merger.Add(im, idc[input:sub(i, i)]) end
 131     inproc = Merger.Finish(im)
 132   end
 133
 134   local bits, dsize = 1, 2
 135   if not outputdict then bits = 8 else while dsize < #outputdict do bits = bits + 1 ; dsize = dsize * 2 end end
 136   QuestHelper: Assert(not outputdict or #outputdict == dsize)
 137
 138   local comp = QH_LZW_Compress(inproc, inputdict and #inputdict or 256, bits)
 139
 140   if outputdict then
 141     local origcomp = comp
 142     local im = {}
 143     for i = 1, #origcomp do Merger.Add(im, outputdict:sub(strbyte(origcomp:sub(i, i)) + 1)) end
 144     comp = Merger.Finish(im)
 145   end
 146
 147   return comp
 148 end
 149
 150 function QH_Collect_LZW_Init(_, API)
 151   Merger = API.Utility_Merger
 152   QuestHelper: Assert(Merger)
 153
 154   Bitstream = API.Utility_Bitstream
 155   QuestHelper: Assert(Bitstream)
 156
 157   API.Utility_LZW = {Compress = QH_LZW_Compress, Decompress = QH_LZW_Decompress, Compress_Dicts = QH_LZW_Compress_Dicts}
 158 end
 159
 160 -- old debug code :)
 161
 162 --[[
 163 print("hello")
 164
 165 QH_LZW_Compress("TOBEORNOTTOBEORTOBEORNOT", 256, 8)
 166 ]]
 167
 168 --[[
 169 QuestHelper:TextOut("lulz")
 170
 171 local inq = "ABABABABA"
 172 local alpha = 253
 173 local bits = 7
 174
 175 str = QH_LZW_Compress(inq, alpha, bits)
 176 tvr = ""
 177 for i = 1, #str do
 178   tvr = tvr .. string.format("%d ", strbyte(str, i))
 179 end
 180 QuestHelper:TextOut(tvr)
 181
 182 ret = QH_LZW_Decompress(str, alpha, bits)
 183 QuestHelper:TextOut(ret)
 184
 185 QuestHelper: Assert(inq == ret)
 186 ]]