----------------------------------------------------------------------------------
-- The author of LibDeflate does NOT write this file (LibCompress.lua)
-- The official website of LibCompress is
-- https://www.wowace.com/projects/libcompress/files
-- This file comes from r84-release, as listed on the URL below.
-- https://www.wowace.com/projects/libcompress/files/2578977
-- (The origin author forgot to bump version number. So you can see
-- "Revision: $Revision: 83 $" in the comments below.)
--
-- However, since LibCompress calls several World of Warcraft APIs, the author
-- of LibDeflate does a small modification to this file,
-- so this file can be run in a standard Lua 5.1.5 or LuaJIT interpreter.
--
-- Note that this file does NOT support Lua 5.2 and Lua 5.3.
--
-- LibDeflate does not use LibCompress to check the correctness of LibDeflate.
-- LibCompress is used for performance evaluation purposes.
----------------------------------------------------------------------------------
----------------------------------------------------------------------------------
--
-- LibCompress.lua
--
-- Authors: jjsheets and Galmok of European Stormrage (Horde)
-- Email : sheets.jeff@gmail.com and galmok@gmail.com
-- Licence: GPL version 2 (General Public License)
-- Revision: $Revision: 83 $
-- Date: $Date: 2018-07-03 14:33:48 +0000 (Tue, 03 Jul 2018) $
----------------------------------------------------------------------------------
-- local LibCompress = LibStub:NewLibrary("LibCompress", 90000 + tonumber(("$Revision: 83 $"):match("%d+")))
-- if not LibCompress then return end
local LibCompress = {}

-- list of codecs in this file:
-- \000 - Never used
-- \001 - Uncompressed
-- \002 - LZW
-- \003 - Huffman

-- local is faster than global
-- local CreateFrame = CreateFrame
local type = type
local tostring = tostring
local select = select
local next = next
local loadstring = loadstring
local setmetatable = setmetatable
local rawset = rawset
local assert = assert
local table_insert = table.insert
local table_remove = table.remove
local table_concat = table.concat
local table_sort = table.sort
local string_char = string.char
local string_byte = string.byte
local string_len = string.len
local string_sub = string.sub
local unpack = unpack
local pairs = pairs
local math_modf = math.modf

local bit = require("bit")
local bit_band = bit.band
local bit_bor = bit.bor
local bit_bxor = bit.bxor
local bit_bnot = bit.bnot
local bit_lshift = bit.lshift
local bit_rshift = bit.rshift

--------------------------------------------------------------------------------
-- Cleanup

local tables = {} -- tables that may be cleaned have to be kept here
local tables_to_clean = {} -- list of tables by name (string) that may be reset to {} after a timeout

-- tables that may be erased
local function cleanup()
  for k, v in pairs(tables_to_clean) do
    tables[k] = {}
    tables_to_clean[k] = nil
  end
end

local timeout = -1
local function onUpdate(frame, elapsed)
  -- frame:Hide()
  timeout = timeout - elapsed
  if timeout <= 0 then cleanup() end
end

-- LibCompress.frame = LibCompress.frame or CreateFrame("frame", nil, UIParent) -- reuse the old frame
-- LibCompress.frame:SetScript("OnUpdate", onUpdate)
-- LibCompress.frame:Hide()

local function setCleanupTables(...)
  timeout = 15 -- empty tables after 15 seconds
  -- if not LibCompress.frame:IsShown() then
  -- LibCompress.frame:Show()
  -- end
  for i = 1, select("#", ...) do tables_to_clean[(select(i, ...))] = true end
end

----------------------------------------------------------------------
----------------------------------------------------------------------
--
-- compression algorithms

--------------------------------------------------------------------------------
-- LZW codec
-- implemented by sheets.jeff@gmail.com

-- encode is used to uniquely encode a number into a sequence of bytes that can be decoded using decode()
-- the bytes returned by this do not contain "\000"
local bytes = {}
local function encode(x)
  for k = 1, #bytes do bytes[k] = nil end

  bytes[#bytes + 1] = x % 255
  x = math.floor(x / 255)

  while x > 0 do
    bytes[#bytes + 1] = x % 255
    x = math.floor(x / 255)
  end
  if #bytes == 1 and bytes[1] > 0 and bytes[1] < 250 then
    return string_char(bytes[1])
  else
    for i = 1, #bytes do bytes[i] = bytes[i] + 1 end
    return string_char(256 - #bytes, unpack(bytes))
  end
end

-- decode converts a unique character sequence into its equivalent number, from ss, beginning at the ith char.
-- returns the decoded number and the count of characters used in the decode process.
local function decode(ss, i)
  i = i or 1
  local a = string_byte(ss, i, i)
  if a > 249 then
    local r = 0
    a = 256 - a
    for n = i + a, i + 1, -1 do r = r * 255 + string_byte(ss, n, n) - 1 end
    return r, a + 1
  else
    return a, 1
  end
end

-- Compresses the given uncompressed string.
-- Unless the uncompressed string starts with "\002", this is guaranteed to return a string equal to or smaller than
-- the passed string.
-- the returned string will only contain "\000" characters in rare circumstances, and will contain none if the
-- source string has none.
local dict = {}
function LibCompress:CompressLZW(uncompressed)
  if type(uncompressed) == "string" then
    local dict_size = 256
    for k in pairs(dict) do dict[k] = nil end

    local result = {"\002"}
    local w = ''
    local ressize = 1

    for i = 0, 255 do dict[string_char(i)] = i end

    for i = 1, #uncompressed do
      local c = uncompressed:sub(i, i)
      local wc = w .. c
      if dict[wc] then
        w = wc
      else
        dict[wc] = dict_size
        dict_size = dict_size + 1
        local r = encode(dict[w])
        ressize = ressize + #r
        result[#result + 1] = r
        w = c
      end
    end

    if w then
      local r = encode(dict[w])
      ressize = ressize + #r
      result[#result + 1] = r
    end

    if (#uncompressed + 1) > ressize then
      return table_concat(result)
    else
      return string_char(1) .. uncompressed
    end
  else
    return nil, "Can only compress strings"
  end
end

-- if the passed string is a compressed string, this will decompress it and return the decompressed string.
-- Otherwise it return an error message
-- compressed strings are marked by beginning with "\002"
function LibCompress:DecompressLZW(compressed)
  if type(compressed) == "string" then
    if compressed:sub(1, 1) ~= "\002" then
      return nil,
             "Can only decompress LZW compressed data (" ..
               tostring(compressed:sub(1, 1)) .. ")"
    end

    compressed = compressed:sub(2)
    local dict_size = 256

    for k in pairs(dict) do dict[k] = nil end

    for i = 0, 255 do dict[i] = string_char(i) end

    local result = {}
    local t = 1
    local delta, k
    k, delta = decode(compressed, t)
    t = t + delta
    result[#result + 1] = dict[k]

    local w = dict[k]
    local entry
    while t <= #compressed do
      k, delta = decode(compressed, t)
      t = t + delta
      entry = dict[k] or (w .. w:sub(1, 1))
      result[#result + 1] = entry
      dict[dict_size] = w .. entry:sub(1, 1)
      dict_size = dict_size + 1
      w = entry
    end
    return table_concat(result)
  else
    return nil, "Can only uncompress strings"
  end
end

--------------------------------------------------------------------------------
-- Huffman codec
-- implemented by Galmok of European Stormrage (Horde), galmok@gmail.com

local function addCode(tree, bcode, length)
  if tree then
    tree.bcode = bcode
    tree.blength = length
    if tree.c1 then
      addCode(tree.c1, bit_bor(bcode, bit_lshift(1, length)), length + 1)
    end
    if tree.c2 then addCode(tree.c2, bcode, length + 1) end
  end
end

local function escape_code(code, length)
  local escaped_code = 0
  local b
  local l = 0
  for i = length - 1, 0, -1 do
    b = bit_band(code, bit_lshift(1, i)) == 0 and 0 or 1
    escaped_code = bit_lshift(escaped_code, 1 + b) + b
    l = l + b
  end
  if length + l > 32 then
    return nil, "escape overflow (" .. (length + l) .. ")"
  end
  return escaped_code, length + l
end

tables.Huffman_compressed = {}
tables.Huffman_large_compressed = {}

local compressed_size = 0
local remainder
local remainder_length
local function addBits(tbl, code, length)
  if remainder_length + length >= 32 then
    -- we have at least 4 bytes to store; bulk it
    remainder = remainder + bit_lshift(code, remainder_length) -- this overflows! Top part of code is lost (but we handle it below)
    -- remainder now holds 4 full bytes to store. So lets do it.
    compressed_size = compressed_size + 1
    tbl[compressed_size] = string_char(bit_band(remainder, 255)) ..
                             string_char(bit_band(bit_rshift(remainder, 8), 255)) ..
                             string_char(
                               bit_band(bit_rshift(remainder, 16), 255)) ..
                             string_char(
                               bit_band(bit_rshift(remainder, 24), 255))
    remainder = 0
    code = bit_rshift(code, 32 - remainder_length)
    length = remainder_length + length - 32
    remainder_length = 0
  end
  if remainder_length + length >= 16 then
    -- we have at least 2 bytes to store; bulk it
    remainder = remainder + bit_lshift(code, remainder_length)
    remainder_length = length + remainder_length
    -- remainder now holds at least 2 full bytes to store. So lets do it.
    compressed_size = compressed_size + 1
    tbl[compressed_size] = string_char(bit_band(remainder, 255)) ..
                             string_char(bit_band(bit_rshift(remainder, 8), 255))
    remainder = bit_rshift(remainder, 16)
    code = remainder
    length = remainder_length - 16
    remainder = 0
    remainder_length = 0
  end
  remainder = remainder + bit_lshift(code, remainder_length)
  remainder_length = length + remainder_length
  if remainder_length >= 8 then
    compressed_size = compressed_size + 1
    tbl[compressed_size] = string_char(bit_band(remainder, 255))
    remainder = bit_rshift(remainder, 8)
    remainder_length = remainder_length - 8
  end
end

-- word size for this huffman algorithm is 8 bits (1 byte).
-- this means the best compression is representing 1 byte with 1 bit, i.e. compress to 0.125 of original size.
function LibCompress:CompressHuffman(uncompressed)
  if type(uncompressed) ~= "string" then
    return nil, "Can only compress strings"
  end
  if #uncompressed == 0 then return "\001" end

  -- make histogram
  local hist = {}
  -- don't have to use all data to make the histogram
  local uncompressed_size = string_len(uncompressed)
  local c
  for i = 1, uncompressed_size do
    c = string_byte(uncompressed, i)
    hist[c] = (hist[c] or 0) + 1
  end

  -- Start with as many leaves as there are symbols.
  local leafs = {}
  local leaf
  local symbols = {}
  for symbol, weight in pairs(hist) do
    leaf = {symbol = string_char(symbol), weight = weight}
    symbols[symbol] = leaf
    table_insert(leafs, leaf)
  end

  -- Enqueue all leaf nodes into the first queue (by probability in increasing order,
  -- so that the least likely item is in the head of the queue).
  table_sort(leafs, function(a, b)
    if a.weight < b.weight then
      return true
    elseif a.weight > b.weight then
      return false
    else
      return nil
    end
  end)

  local nLeafs = #leafs

  -- create tree
  local huff = {}
  -- While there is more than one node in the queues:
  local length, height, li, hi, leaf1, leaf2
  local newNode
  while (#leafs + #huff > 1) do
    -- Dequeue the two nodes with the lowest weight.
    -- Dequeue first
    if not next(huff) then
      li, leaf1 = next(leafs)
      table_remove(leafs, li)
    elseif not next(leafs) then
      hi, leaf1 = next(huff)
      table_remove(huff, hi)
    else
      li, length = next(leafs)
      hi, height = next(huff)
      if length.weight <= height.weight then
        leaf1 = length
        table_remove(leafs, li)
      else
        leaf1 = height
        table_remove(huff, hi)
      end
    end

    -- Dequeue second
    if not next(huff) then
      li, leaf2 = next(leafs)
      table_remove(leafs, li)
    elseif not next(leafs) then
      hi, leaf2 = next(huff)
      table_remove(huff, hi)
    else
      li, length = next(leafs)
      hi, height = next(huff)
      if length.weight <= height.weight then
        leaf2 = length
        table_remove(leafs, li)
      else
        leaf2 = height
        table_remove(huff, hi)
      end
    end

    -- Create a new internal node, with the two just-removed nodes as children (either node can be either child) and the sum of their weights as the new weight.
    newNode = {c1 = leaf1, c2 = leaf2, weight = leaf1.weight + leaf2.weight}
    table_insert(huff, newNode)
  end

  if #leafs > 0 then
    li, length = next(leafs)
    table_insert(huff, length)
    table_remove(leafs, li)
  end
  huff = huff[1]

  -- assign codes to each symbol
  -- c1 = "0", c2 = "1"
  -- As a common convention, bit '0' represents following the left child and bit '1' represents following the right child.
  -- c1 = left, c2 = right

  addCode(huff, 0, 0)
  if huff then
    huff.bcode = 0
    huff.blength = 1
  end

  -- READING
  -- bitfield = 0
  -- bitfield_len = 0
  -- read byte1
  -- bitfield = bitfield + bit_lshift(byte1, bitfield_len)
  -- bitfield_len = bitfield_len + 8
  -- read byte2
  -- bitfield = bitfield + bit_lshift(byte2, bitfield_len)
  -- bitfield_len = bitfield_len + 8
  -- (use 5 bits)
  --	word = bit_band( bitfield, bit_lshift(1,5)-1)
  --	bitfield = bit_rshift( bitfield, 5)
  --	bitfield_len = bitfield_len - 5
  -- read byte3
  -- bitfield = bitfield + bit_lshift(byte3, bitfield_len)
  -- bitfield_len = bitfield_len + 8

  -- WRITING
  remainder = 0
  remainder_length = 0

  local compressed = tables.Huffman_compressed
  -- compressed_size = 0

  -- first byte is version info. 0 = uncompressed, 1 = 8 - bit word huffman compressed
  compressed[1] = "\003"

  -- Header: byte 0 = #leafs, bytes 1-3 = size of uncompressed data
  -- max 2^24 bytes
  length = string_len(uncompressed)
  compressed[2] = string_char(bit_band(nLeafs - 1, 255)) -- number of leafs
  compressed[3] = string_char(bit_band(length, 255)) -- bit 0-7
  compressed[4] = string_char(bit_band(bit_rshift(length, 8), 255)) -- bit 8-15
  compressed[5] = string_char(bit_band(bit_rshift(length, 16), 255)) -- bit 16-23
  compressed_size = 5

  -- create symbol/code map
  local escaped_code, escaped_code_len, success, msg
  for symbol, leaf in pairs(symbols) do
    addBits(compressed, symbol, 8)
    escaped_code, escaped_code_len = escape_code(leaf.bcode, leaf.blength)
    if not escaped_code then return nil, escaped_code_len end
    addBits(compressed, escaped_code, escaped_code_len)
    addBits(compressed, 3, 2)
  end

  -- create huffman code
  local large_compressed = tables.Huffman_large_compressed
  local large_compressed_size = 0
  local ulimit
  for i = 1, length, 200 do
    ulimit = length < (i + 199) and length or (i + 199)

    for sub_i = i, ulimit do
      c = string_byte(uncompressed, sub_i)
      addBits(compressed, symbols[c].bcode, symbols[c].blength)
    end

    large_compressed_size = large_compressed_size + 1
    large_compressed[large_compressed_size] =
      table_concat(compressed, "", 1, compressed_size)
    compressed_size = 0
  end

  -- add remaining bits (if any)
  if remainder_length > 0 then
    large_compressed_size = large_compressed_size + 1
    large_compressed[large_compressed_size] = string_char(remainder)
  end
  local compressed_string = table_concat(large_compressed, "", 1,
                                         large_compressed_size)

  -- is compression worth it? If not, return uncompressed data.
  if (#uncompressed + 1) <= #compressed_string then
    return "\001" .. uncompressed
  end

  setCleanupTables("Huffman_compressed", "Huffman_large_compressed")
  return compressed_string
end

-- lookuptable (cached between calls)
local lshiftMask = {}
setmetatable(lshiftMask, {
  __index = function(t, k)
    local v = bit_lshift(1, k)
    rawset(t, k, v)
    return v
  end
})

-- lookuptable (cached between calls)
local lshiftMinusOneMask = {}
setmetatable(lshiftMinusOneMask, {
  __index = function(t, k)
    local v = bit_lshift(1, k) - 1
    rawset(t, k, v)
    return v
  end
})

local function bor64(valueA_high, valueA, valueB_high, valueB)
  return bit_bor(valueA_high, valueB_high), bit_bor(valueA, valueB)
end

local function band64(valueA_high, valueA, valueB_high, valueB)
  return bit_band(valueA_high, valueB_high), bit_band(valueA, valueB)
end

local function lshift64(value_high, value, lshift_amount)
  if lshift_amount == 0 then return value_high, value end
  if lshift_amount >= 64 then return 0, 0 end
  if lshift_amount < 32 then
    return bit_bor(bit_lshift(value_high, lshift_amount),
                   bit_rshift(value, 32 - lshift_amount)),
           bit_lshift(value, lshift_amount)
  end
  -- 32-63 bit shift
  return bit_lshift(value, lshift_amount), -- builtin modulus 32 on shift amount
  0
end

local function rshift64(value_high, value, rshift_amount)
  if rshift_amount == 0 then return value_high, value end
  if rshift_amount >= 64 then return 0, 0 end
  if rshift_amount < 32 then
    return bit_rshift(value_high, rshift_amount),
           bit_bor(bit_lshift(value_high, 32 - rshift_amount),
                   bit_rshift(value, rshift_amount))
  end
  -- 32-63 bit shift
  return 0, bit_rshift(value_high, rshift_amount)
end

local function getCode2(bitfield_high, bitfield, field_len)
  if field_len >= 2 then
    -- [bitfield_high..bitfield]: bit 0 is right most in bitfield. bit <field_len-1> is left most in bitfield_high
    local b1, b2, remainder_high, remainder
    for i = 0, field_len - 2 do
      b1 = i <= 31 and bit_band(bitfield, bit_lshift(1, i)) or
             bit_band(bitfield_high, bit_lshift(1, i)) -- for shifts, 32 = 0 (5 bit used)
      b2 = (i + 1) <= 31 and bit_band(bitfield, bit_lshift(1, i + 1)) or
             bit_band(bitfield_high, bit_lshift(1, i + 1))
      if not (b1 == 0) and not (b2 == 0) then
        -- found 2 bits set right after each other (stop bits) with i pointing at the first stop bit
        -- return the two bitfields separated by the two stopbits (3 values for each: bitfield_high, bitfield, field_len)
        -- bits left: field_len - (i+2)
        remainder_high, remainder = rshift64(bitfield_high, bitfield, i + 2)
        -- first bitfield is the lower part
        return
          (i - 1) >= 32 and bit_band(bitfield_high, bit_lshift(1, i) - 1) or 0,
          i >= 32 and bitfield or bit_band(bitfield, bit_lshift(1, i) - 1), i,
          remainder_high, remainder, field_len - (i + 2)
      end
    end
  end
  return nil
end

local function unescape_code(code, code_len)
  local unescaped_code = 0
  local b
  local l = 0
  local i = 0
  while i < code_len do
    b = bit_band(code, lshiftMask[i])
    if not (b == 0) then
      unescaped_code = bit_bor(unescaped_code, lshiftMask[l])
      i = i + 1
    end
    i = i + 1
    l = l + 1
  end
  return unescaped_code, l
end

tables.Huffman_uncompressed = {}
tables.Huffman_large_uncompressed = {} -- will always be as big as the largest string ever decompressed. Bad, but clearing it every time takes precious time.

function LibCompress:DecompressHuffman(compressed)
  if not type(compressed) == "string" then
    return nil, "Can only uncompress strings"
  end

  local compressed_size = #compressed
  -- decode header
  local info_byte = string_byte(compressed)
  -- is data compressed
  if info_byte == 1 then
    return compressed:sub(2) -- return uncompressed data
  end
  if not (info_byte == 3) then
    return nil, "Can only decompress Huffman compressed data (" ..
             tostring(info_byte) .. ")"
  end

  local num_symbols = string_byte(string_sub(compressed, 2, 2)) + 1
  local c0 = string_byte(string_sub(compressed, 3, 3))
  local c1 = string_byte(string_sub(compressed, 4, 4))
  local c2 = string_byte(string_sub(compressed, 5, 5))
  local orig_size = c2 * 65536 + c1 * 256 + c0
  if orig_size == 0 then return "" end

  -- decode code -> symbol map
  local bitfield = 0
  local bitfield_high = 0
  local bitfield_len = 0
  local map = {} -- only table not reused in Huffman decode.
  setmetatable(map, {
    __index = function(t, k)
      local v = {}
      rawset(t, k, v)
      return v
    end
  })

  local i = 6 -- byte 1-5 are header bytes
  local c, cl
  local minCodeLen = 1000
  local maxCodeLen = 0
  local symbol, code_high, code, code_len, temp_high, temp, _bitfield_high,
        _bitfield, _bitfield_len
  local n = 0
  local state = 0 -- 0 = get symbol (8 bits),  1 = get code (varying bits, ends with 2 bits set)
  while n < num_symbols do
    if i > compressed_size then return nil, "Cannot decode map" end

    c = string_byte(compressed, i)
    temp_high, temp = lshift64(0, c, bitfield_len)
    bitfield_high, bitfield = bor64(bitfield_high, bitfield, temp_high, temp)
    bitfield_len = bitfield_len + 8

    if state == 0 then
      symbol = bit_band(bitfield, 255)
      bitfield_high, bitfield = rshift64(bitfield_high, bitfield, 8)
      bitfield_len = bitfield_len - 8
      state = 1 -- search for code now
    else
      code_high, code, code_len, _bitfield_high, _bitfield, _bitfield_len =
        getCode2(bitfield_high, bitfield, bitfield_len)
      if code_high then
        bitfield_high, bitfield, bitfield_len = _bitfield_high, _bitfield,
                                                _bitfield_len
        if code_len > 32 then
          return nil, "Unsupported symbol code length (" .. code_len .. ")"
        end
        c, cl = unescape_code(code, code_len)
        map[cl][c] = string_char(symbol)
        minCodeLen = cl < minCodeLen and cl or minCodeLen
        maxCodeLen = cl > maxCodeLen and cl or maxCodeLen
        -- print("symbol: "..string_char(symbol).."  code: "..tobinary(c, cl))
        n = n + 1
        state = 0 -- search for next symbol (if any)
      end
    end
    i = i + 1
  end

  -- don't create new subtables for entries not in the map. Waste of space.
  -- But do return an empty table to prevent runtime errors. (instead of returning nil)
  local mt = {}
  setmetatable(map, {__index = function(t, k) return mt end})

  local uncompressed = tables.Huffman_uncompressed
  local large_uncompressed = tables.Huffman_large_uncompressed
  local uncompressed_size = 0
  local large_uncompressed_size = 0
  local test_code
  local test_code_len = minCodeLen
  local dec_size = 0
  compressed_size = compressed_size + 1
  local temp_limit = 200 -- first limit of uncompressed data. large_uncompressed will hold strings of length 200
  temp_limit = temp_limit > orig_size and orig_size or temp_limit

  while true do
    if test_code_len <= bitfield_len then
      test_code = bit_band(bitfield, lshiftMinusOneMask[test_code_len])
      symbol = map[test_code_len][test_code]

      if symbol then
        uncompressed_size = uncompressed_size + 1
        uncompressed[uncompressed_size] = symbol
        dec_size = dec_size + 1
        if dec_size >= temp_limit then
          if dec_size >= orig_size then -- checked here for speed reasons
            break
          end
          -- process compressed bytes in smaller chunks
          large_uncompressed_size = large_uncompressed_size + 1
          large_uncompressed[large_uncompressed_size] =
            table_concat(uncompressed, "", 1, uncompressed_size)
          uncompressed_size = 0
          temp_limit = temp_limit + 200 -- repeated chunk size is 200 uncompressed bytes
          temp_limit = temp_limit > orig_size and orig_size or temp_limit
        end

        bitfield = bit_rshift(bitfield, test_code_len)
        bitfield_len = bitfield_len - test_code_len
        test_code_len = minCodeLen
      else
        test_code_len = test_code_len + 1
        if test_code_len > maxCodeLen then
          return nil, "Decompression error at " .. tostring(i) .. "/" ..
                   tostring(#compressed)
        end
      end
    else
      c = string_byte(compressed, i)
      bitfield = bitfield + bit_lshift(c or 0, bitfield_len)
      bitfield_len = bitfield_len + 8
      if i > compressed_size then break end
      i = i + 1
    end
  end

  setCleanupTables("Huffman_uncompressed", "Huffman_large_uncompressed")
  return table_concat(large_uncompressed, "", 1, large_uncompressed_size) ..
           table_concat(uncompressed, "", 1, uncompressed_size)
end

--------------------------------------------------------------------------------
-- Generic codec interface

function LibCompress:Store(uncompressed)
  if type(uncompressed) ~= "string" then
    return nil, "Can only compress strings"
  end
  return "\001" .. uncompressed
end

function LibCompress:DecompressUncompressed(data)
  if type(data) ~= "string" then return nil, "Can only handle strings" end
  if string_byte(data) ~= 1 then
    return nil, "Can only handle uncompressed data"
  end
  return data:sub(2)
end

local compression_methods = {
  [2] = LibCompress.CompressLZW,
  [3] = LibCompress.CompressHuffman
}

local decompression_methods = {
  [1] = LibCompress.DecompressUncompressed,
  [2] = LibCompress.DecompressLZW,
  [3] = LibCompress.DecompressHuffman
}

-- try all compression codecs and return best result
function LibCompress:Compress(data)
  local method = next(compression_methods)
  local result = compression_methods[method](self, data)
  local n
  method = next(compression_methods, method)
  while method do
    n = compression_methods[method](self, data)
    if #n < #result then result = n end
    method = next(compression_methods, method)
  end
  return result
end

function LibCompress:Decompress(data)
  local header_info = string_byte(data)
  if decompression_methods[header_info] then
    return decompression_methods[header_info](self, data)
  else
    return nil, "Unknown compression method (" .. tostring(header_info) .. ")"
  end
end

----------------------------------------------------------------------
----------------------------------------------------------------------
--
-- Encoding algorithms

--------------------------------------------------------------------------------
-- Prefix encoding algorithm
-- implemented by Galmok of European Stormrage (Horde), galmok@gmail.com

--[[
	Howto: Encode and Decode:

	3 functions are supplied, 2 of them are variants of the first.  They return a table with functions to encode and decode text.

	table, msg = LibCompress:GetEncodeTable(reservedChars, escapeChars,  mapChars)

		reservedChars: The characters in this string will not appear in the encoded data.
		escapeChars: A string of characters used as escape-characters (don't supply more than needed). #escapeChars >= 1
		mapChars: First characters in reservedChars maps to first characters in mapChars.  (#mapChars <= #reservedChars)

	return value:
		table
			if nil then msg holds an error message, otherwise use like this:

			encoded_message = table:Encode(message)
			message = table:Decode(encoded_message)

	GetAddonEncodeTable: Sets up encoding for the addon channel (\000 is encoded)
	GetChatEncodeTable: Sets up encoding for the chat channel (many bytes encoded, see the function for details)

	Except for the mapped characters, all encoding will be with 1 escape character followed by 1 suffix, i.e. 2 bytes.
]]
-- to be able to match any requested byte value, the search string must be preprocessed
-- characters to escape with %:
-- ( ) . % + - * ? [ ] ^ $
-- "illegal" byte values:
-- 0 is replaces %z
local gsub_escape_table = {
  ['\000'] = "%z",
  [('(')] = "%(",
  [(')')] = "%)",
  [('.')] = "%.",
  [('%')] = "%%",
  [('+')] = "%+",
  [('-')] = "%-",
  [('*')] = "%*",
  [('?')] = "%?",
  [('[')] = "%[",
  [(']')] = "%]",
  [('^')] = "%^",
  [('$')] = "%$"
}

local function escape_for_gsub(str)
  return str:gsub("([%z%(%)%.%%%+%-%*%?%[%]%^%$])", gsub_escape_table)
end

function LibCompress:GetEncodeTable(reservedChars, escapeChars, mapChars)
  reservedChars = reservedChars or ""
  escapeChars = escapeChars or ""
  mapChars = mapChars or ""

  -- select a default escape character
  if escapeChars == "" then return nil, "No escape characters supplied" end

  if #reservedChars < #mapChars then
    return nil,
           "Number of reserved characters must be at least as many as the number of mapped chars"
  end

  if reservedChars == "" then return nil, "No characters to encode" end

  -- list of characters that must be encoded
  local encodeBytes = reservedChars .. escapeChars .. mapChars

  -- build list of bytes not available as a suffix to a prefix byte
  local taken = {}
  for i = 1, string_len(encodeBytes) do
    taken[string_sub(encodeBytes, i, i)] = true
  end

  -- allocate a table to hold encode/decode strings/functions
  local codecTable = {}

  -- the encoding can be a single gsub, but the decoding can require multiple gsubs
  local decode_func_string = {}

  local encode_search = {}
  local encode_translate = {}
  local encode_func
  local decode_search = {}
  local decode_translate = {}
  local decode_func
  local c, r, to, from
  local escapeCharIndex, escapeChar = 0

  -- map single byte to single byte
  if #mapChars > 0 then
    for i = 1, #mapChars do
      from = string_sub(reservedChars, i, i)
      to = string_sub(mapChars, i, i)
      encode_translate[from] = to
      table_insert(encode_search, from)
      decode_translate[to] = from
      table_insert(decode_search, to)
    end
    codecTable["decode_search" .. tostring(escapeCharIndex)] =
      "([" .. escape_for_gsub(table_concat(decode_search)) .. "])"
    codecTable["decode_translate" .. tostring(escapeCharIndex)] =
      decode_translate
    table_insert(decode_func_string,
                 "str = str:gsub(self.decode_search" ..
                   tostring(escapeCharIndex) .. ", self.decode_translate" ..
                   tostring(escapeCharIndex) .. ");")

  end

  -- map single byte to double-byte
  escapeCharIndex = escapeCharIndex + 1
  escapeChar = string_sub(escapeChars, escapeCharIndex, escapeCharIndex)
  r = 0 -- suffix char value to the escapeChar
  decode_search = {}
  decode_translate = {}
  for i = 1, string_len(encodeBytes) do
    c = string_sub(encodeBytes, i, i)
    if not encode_translate[c] then
      -- this loop will update escapeChar and r
      while r >= 256 or taken[string_char(r)] do
        r = r + 1
        if r > 255 then -- switch to next escapeChar
          codecTable["decode_search" .. tostring(escapeCharIndex)] =
            escape_for_gsub(escapeChar) .. "([" ..
              escape_for_gsub(table_concat(decode_search)) .. "])"
          codecTable["decode_translate" .. tostring(escapeCharIndex)] =
            decode_translate
          table_insert(decode_func_string,
                       "str = str:gsub(self.decode_search" ..
                         tostring(escapeCharIndex) .. ", self.decode_translate" ..
                         tostring(escapeCharIndex) .. ");")

          escapeCharIndex = escapeCharIndex + 1
          escapeChar = string_sub(escapeChars, escapeCharIndex, escapeCharIndex)

          if escapeChar == "" then -- we are out of escape chars and we need more!
            return nil, "Out of escape characters"
          end

          r = 0
          decode_search = {}
          decode_translate = {}
        end
      end
      encode_translate[c] = escapeChar .. string_char(r)
      table_insert(encode_search, c)
      decode_translate[string_char(r)] = c
      table_insert(decode_search, string_char(r))
      r = r + 1
    end
  end

  if r > 0 then
    codecTable["decode_search" .. tostring(escapeCharIndex)] =
      escape_for_gsub(escapeChar) .. "([" ..
        escape_for_gsub(table_concat(decode_search)) .. "])"
    codecTable["decode_translate" .. tostring(escapeCharIndex)] =
      decode_translate
    table_insert(decode_func_string,
                 "str = str:gsub(self.decode_search" ..
                   tostring(escapeCharIndex) .. ", self.decode_translate" ..
                   tostring(escapeCharIndex) .. ");")
  end

  -- change last line from "str = ...;" to "return ...;";
  decode_func_string[#decode_func_string] =
    decode_func_string[#decode_func_string]:gsub("str = (.*);", "return %1;")
  decode_func_string = "return function(self, str) " ..
                         table_concat(decode_func_string) .. " end"

  encode_search = "([" .. escape_for_gsub(table_concat(encode_search)) .. "])"
  decode_search = escape_for_gsub(escapeChars) .. "([" ..
                    escape_for_gsub(table_concat(decode_search)) .. "])"

  encode_func = assert(loadstring(
                         "return function(self, str) return str:gsub(self.encode_search, self.encode_translate); end"))()
  decode_func = assert(loadstring(decode_func_string))()
  codecTable.encode_search = encode_search
  codecTable.encode_translate = encode_translate
  codecTable.Encode = encode_func
  codecTable.decode_search = decode_search
  codecTable.decode_translate = decode_translate
  codecTable.Decode = decode_func

  codecTable.decode_func_string = decode_func_string -- to be deleted
  return codecTable
end

-- Addons: Call this only once and reuse the returned table for all encodings/decodings.
function LibCompress:GetAddonEncodeTable(reservedChars, escapeChars, mapChars)
  reservedChars = reservedChars or ""
  escapeChars = escapeChars or ""
  mapChars = mapChars or ""
  -- Following byte values are not allowed:
  -- \000
  if escapeChars == "" then escapeChars = "\001" end
  return self:GetEncodeTable((reservedChars or "") .. "\000", escapeChars,
                             mapChars)
end

-- Addons: Call this only once and reuse the returned table for all encodings/decodings.
function LibCompress:GetChatEncodeTable(reservedChars, escapeChars, mapChars)
  reservedChars = reservedChars or ""
  escapeChars = escapeChars or ""
  mapChars = mapChars or ""
  -- Following byte values are not allowed:
  -- \000, s, S, \010, \013, \124, %
  -- Because SendChatMessage will error if an UTF8 multibyte character is incomplete,
  -- all character values above 127 have to be encoded to avoid this. This costs quite a bit of bandwidth (about 13-14%)
  -- Also, because drunken status is unknown for the received, strings used with SendChatMessage should be terminated with
  -- an identifying byte value, after which the server MAY add "...hic!" or as much as it can fit(!).
  -- Pass the identifying byte as a reserved character to this function to ensure the encoding doesn't contain that value.
  --  or use this: local message, match = arg1:gsub("^(.*)\029.-$", "%1")
  --  arg1 is message from channel, \029 is the string terminator, but may be used in the encoded datastream as well. :-)
  -- This encoding will expand data anywhere from:
  -- 0% (average with pure ascii text)
  -- 53.5% (average with random data valued zero to 255)
  -- 100% (only encoding data that encodes to two bytes)
  local r = {}

  for i = 128, 255 do table_insert(r, string_char(i)) end

  reservedChars = "sS\000\010\013\124%" .. table_concat(r) ..
                    (reservedChars or "")
  if escapeChars == "" then escapeChars = "\029\031" end

  if mapChars == "" then mapChars = "\015\020"; end
  return self:GetEncodeTable(reservedChars, escapeChars, mapChars)
end

--------------------------------------------------------------------------------
-- 7 bit encoding algorithm
-- implemented by Galmok of European Stormrage (Horde), galmok@gmail.com

-- The encoded data holds values from 0 to 127 inclusive. Additional encoding may be necessary.
-- This algorithm isn't exactly fast and be used with care and consideration

tables.encode7bit = {}

function LibCompress:Encode7bit(str)
  local remainder = 0
  local remainder_length = 0
  local tbl = tables.encode7bit
  local encoded_size = 0
  local length = #str
  for i = 1, length do
    local code = string_byte(str, i)
    remainder = remainder + bit_lshift(code, remainder_length)
    remainder_length = 8 + remainder_length
    while remainder_length >= 7 do
      encoded_size = encoded_size + 1
      tbl[encoded_size] = string_char(bit_band(remainder, 127))
      remainder = bit_rshift(remainder, 7)
      remainder_length = remainder_length - 7
    end
  end

  if remainder_length > 0 then
    encoded_size = encoded_size + 1
    tbl[encoded_size] = string_char(remainder)
  end
  setCleanupTables("encode7bit")
  return table_concat(tbl, "", 1, encoded_size)
end

tables.decode8bit = {}

function LibCompress:Decode7bit(str)
  local bit8 = tables.decode8bit
  local decoded_size = 0
  local ch
  local i = 1
  local bitfield_len = 0
  local bitfield = 0
  local length = #str
  while true do
    if bitfield_len >= 8 then
      decoded_size = decoded_size + 1
      bit8[decoded_size] = string_char(bit_band(bitfield, 255))
      bitfield = bit_rshift(bitfield, 8)
      bitfield_len = bitfield_len - 8
    end
    ch = string_byte(str, i)
    bitfield = bitfield + bit_lshift(ch or 0, bitfield_len)
    bitfield_len = bitfield_len + 7
    if i > length then break end
    i = i + 1
  end
  setCleanupTables("decode8bit")
  return table_concat(bit8, "", 1, decoded_size)
end

----------------------------------------------------------------------
----------------------------------------------------------------------
--
-- Checksum/hash algorithms

--------------------------------------------------------------------------------
-- FCS16/32 checksum algorithms
-- converted from C by Galmok of European Stormrage (Horde), galmok@gmail.com
-- usage:
-- 	code = LibCompress:fcs16init()
--	code = LibCompress:fcs16update(code, data1)
--	code = LibCompress:fcs16update(code, data2)
--	code = LibCompress:fcs16update(code, data...)
--	code = LibCompress:fcs16final(code)
--
--	data = string
--	fcs16 provides a 16 bit checksum, fcs32 provides a 32 bit checksum.

--[[/* The following copyright notice concerns only the FCS hash algorithm
---------------------------------------------------------------------------
Copyright (c) 2003, Dominik Reichl <dominik.reichl@t-online.de>, Germany.
All rights reserved.

Distributed under the terms of the GNU General Public License v2.

This software is provided 'as is' with no explicit or implied warranties
in respect of its properties, including, but not limited to, correctness
and/or fitness for purpose.
---------------------------------------------------------------------------
*/]]
-- // FCS-16 algorithm implemented as described in RFC 1331
local FCSINIT16 = 65535
-- // Fast 16 bit FCS lookup table
local fcs16tab = {
  [0] = 0,
  4489,
  8978,
  12955,
  17956,
  22445,
  25910,
  29887,
  35912,
  40385,
  44890,
  48851,
  51820,
  56293,
  59774,
  63735,
  4225,
  264,
  13203,
  8730,
  22181,
  18220,
  30135,
  25662,
  40137,
  36160,
  49115,
  44626,
  56045,
  52068,
  63999,
  59510,
  8450,
  12427,
  528,
  5017,
  26406,
  30383,
  17460,
  21949,
  44362,
  48323,
  36440,
  40913,
  60270,
  64231,
  51324,
  55797,
  12675,
  8202,
  4753,
  792,
  30631,
  26158,
  21685,
  17724,
  48587,
  44098,
  40665,
  36688,
  64495,
  60006,
  55549,
  51572,
  16900,
  21389,
  24854,
  28831,
  1056,
  5545,
  10034,
  14011,
  52812,
  57285,
  60766,
  64727,
  34920,
  39393,
  43898,
  47859,
  21125,
  17164,
  29079,
  24606,
  5281,
  1320,
  14259,
  9786,
  57037,
  53060,
  64991,
  60502,
  39145,
  35168,
  48123,
  43634,
  25350,
  29327,
  16404,
  20893,
  9506,
  13483,
  1584,
  6073,
  61262,
  65223,
  52316,
  56789,
  43370,
  47331,
  35448,
  39921,
  29575,
  25102,
  20629,
  16668,
  13731,
  9258,
  5809,
  1848,
  65487,
  60998,
  56541,
  52564,
  47595,
  43106,
  39673,
  35696,
  33800,
  38273,
  42778,
  46739,
  49708,
  54181,
  57662,
  61623,
  2112,
  6601,
  11090,
  15067,
  20068,
  24557,
  28022,
  31999,
  38025,
  34048,
  47003,
  42514,
  53933,
  49956,
  61887,
  57398,
  6337,
  2376,
  15315,
  10842,
  24293,
  20332,
  32247,
  27774,
  42250,
  46211,
  34328,
  38801,
  58158,
  62119,
  49212,
  53685,
  10562,
  14539,
  2640,
  7129,
  28518,
  32495,
  19572,
  24061,
  46475,
  41986,
  38553,
  34576,
  62383,
  57894,
  53437,
  49460,
  14787,
  10314,
  6865,
  2904,
  32743,
  28270,
  23797,
  19836,
  50700,
  55173,
  58654,
  62615,
  32808,
  37281,
  41786,
  45747,
  19012,
  23501,
  26966,
  30943,
  3168,
  7657,
  12146,
  16123,
  54925,
  50948,
  62879,
  58390,
  37033,
  33056,
  46011,
  41522,
  23237,
  19276,
  31191,
  26718,
  7393,
  3432,
  16371,
  11898,
  59150,
  63111,
  50204,
  54677,
  41258,
  45219,
  33336,
  37809,
  27462,
  31439,
  18516,
  23005,
  11618,
  15595,
  3696,
  8185,
  63375,
  58886,
  54429,
  50452,
  45483,
  40994,
  37561,
  33584,
  31687,
  27214,
  22741,
  18780,
  15843,
  11370,
  7921,
  3960
}

function LibCompress:fcs16init() return FCSINIT16 end

function LibCompress:fcs16update(uFcs16, pBuffer)
  local length = string_len(pBuffer)
  for i = 1, length do
    uFcs16 = bit_bxor(bit_rshift(uFcs16, 8), fcs16tab[bit_band(
                        bit_bxor(uFcs16, string_byte(pBuffer, i)), 255)])
  end
  return uFcs16
end

function LibCompress:fcs16final(uFcs16) return bit_bxor(uFcs16, 65535) end
-- END OF FCS16

--[[/*
---------------------------------------------------------------------------
Copyright (c) 2003, Dominik Reichl <dominik.reichl@t-online.de>, Germany.
All rights reserved.

Distributed under the terms of the GNU General Public License v2.

This software is provided 'as is' with no explicit or implied warranties
in respect of its properties, including, but not limited to, correctness
and/or fitness for purpose.
---------------------------------------------------------------------------
*/]]

-- // FCS-32 algorithm implemented as described in RFC 1331

local FCSINIT32 = -1

-- // Fast 32 bit FCS lookup table
local fcs32tab = {
  [0] = 0,
  1996959894,
  -301047508,
  -1727442502,
  124634137,
  1886057615,
  -379345611,
  -1637575261,
  249268274,
  2044508324,
  -522852066,
  -1747789432,
  162941995,
  2125561021,
  -407360249,
  -1866523247,
  498536548,
  1789927666,
  -205950648,
  -2067906082,
  450548861,
  1843258603,
  -187386543,
  -2083289657,
  325883990,
  1684777152,
  -43845254,
  -1973040660,
  335633487,
  1661365465,
  -99664541,
  -1928851979,
  997073096,
  1281953886,
  -715111964,
  -1570279054,
  1006888145,
  1258607687,
  -770865667,
  -1526024853,
  901097722,
  1119000684,
  -608450090,
  -1396901568,
  853044451,
  1172266101,
  -589951537,
  -1412350631,
  651767980,
  1373503546,
  -925412992,
  -1076862698,
  565507253,
  1454621731,
  -809855591,
  -1195530993,
  671266974,
  1594198024,
  -972236366,
  -1324619484,
  795835527,
  1483230225,
  -1050600021,
  -1234817731,
  1994146192,
  31158534,
  -1731059524,
  -271249366,
  1907459465,
  112637215,
  -1614814043,
  -390540237,
  2013776290,
  251722036,
  -1777751922,
  -519137256,
  2137656763,
  141376813,
  -1855689577,
  -429695999,
  1802195444,
  476864866,
  -2056965928,
  -228458418,
  1812370925,
  453092731,
  -2113342271,
  -183516073,
  1706088902,
  314042704,
  -1950435094,
  -54949764,
  1658658271,
  366619977,
  -1932296973,
  -69972891,
  1303535960,
  984961486,
  -1547960204,
  -725929758,
  1256170817,
  1037604311,
  -1529756563,
  -740887301,
  1131014506,
  879679996,
  -1385723834,
  -631195440,
  1141124467,
  855842277,
  -1442165665,
  -586318647,
  1342533948,
  654459306,
  -1106571248,
  -921952122,
  1466479909,
  544179635,
  -1184443383,
  -832445281,
  1591671054,
  702138776,
  -1328506846,
  -942167884,
  1504918807,
  783551873,
  -1212326853,
  -1061524307,
  -306674912,
  -1698712650,
  62317068,
  1957810842,
  -355121351,
  -1647151185,
  81470997,
  1943803523,
  -480048366,
  -1805370492,
  225274430,
  2053790376,
  -468791541,
  -1828061283,
  167816743,
  2097651377,
  -267414716,
  -2029476910,
  503444072,
  1762050814,
  -144550051,
  -2140837941,
  426522225,
  1852507879,
  -19653770,
  -1982649376,
  282753626,
  1742555852,
  -105259153,
  -1900089351,
  397917763,
  1622183637,
  -690576408,
  -1580100738,
  953729732,
  1340076626,
  -776247311,
  -1497606297,
  1068828381,
  1219638859,
  -670225446,
  -1358292148,
  906185462,
  1090812512,
  -547295293,
  -1469587627,
  829329135,
  1181335161,
  -882789492,
  -1134132454,
  628085408,
  1382605366,
  -871598187,
  -1156888829,
  570562233,
  1426400815,
  -977650754,
  -1296233688,
  733239954,
  1555261956,
  -1026031705,
  -1244606671,
  752459403,
  1541320221,
  -1687895376,
  -328994266,
  1969922972,
  40735498,
  -1677130071,
  -351390145,
  1913087877,
  83908371,
  -1782625662,
  -491226604,
  2075208622,
  213261112,
  -1831694693,
  -438977011,
  2094854071,
  198958881,
  -2032938284,
  -237706686,
  1759359992,
  534414190,
  -2118248755,
  -155638181,
  1873836001,
  414664567,
  -2012718362,
  -15766928,
  1711684554,
  285281116,
  -1889165569,
  -127750551,
  1634467795,
  376229701,
  -1609899400,
  -686959890,
  1308918612,
  956543938,
  -1486412191,
  -799009033,
  1231636301,
  1047427035,
  -1362007478,
  -640263460,
  1088359270,
  936918000,
  -1447252397,
  -558129467,
  1202900863,
  817233897,
  -1111625188,
  -893730166,
  1404277552,
  615818150,
  -1160759803,
  -841546093,
  1423857449,
  601450431,
  -1285129682,
  -1000256840,
  1567103746,
  711928724,
  -1274298825,
  -1022587231,
  1510334235,
  755167117
}

function LibCompress:fcs32init() return FCSINIT32 end

function LibCompress:fcs32update(uFcs32, pBuffer)
  local length = string_len(pBuffer)
  for i = 1, length do
    uFcs32 = bit_bxor(bit_rshift(uFcs32, 8), fcs32tab[bit_band(
                        bit_bxor(uFcs32, string_byte(pBuffer, i)), 255)])
  end
  return uFcs32
end

function LibCompress:fcs32final(uFcs32) return bit_bnot(uFcs32) end

return LibCompress
