lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


Calculations should be completed in a reasonable amount of time.

Here is a solution with tunable number of slots used.

-- compressor.lua
local num_bits = 64
local num_slots = 4

local bits_per_slot = (num_bits + num_slots - 1) // num_slots
local max_value_per_slot = 1 << bits_per_slot

local function Encode(what)
    local tab = {}
    local offset = 0.5

    for i = 1, num_slots do
        local v = (what >> ((i - 1) * bits_per_slot)) & (max_value_per_slot - 1)
        tab[offset + v] = true
        offset = offset + max_value_per_slot
    end

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

return Encode(...)

-- decompressor.lua
local num_bits = 64
local num_slots = 4

local bits_per_slot = (num_bits + num_slots - 1) // num_slots
local max_value_per_slot = 1 << bits_per_slot

local function FindValue(tab, offset, max)
    for i = 0, max - 1 do
        if pcall(next, tab, offset+ i) then
            return i
        end
    end
    error("No value found")
end

local function Decode(tab)
    local num = 0
    local offset = 0.5

    for i = 1, num_slots do
        local v = FindValue(tab, offset, max_value_per_slot)
        offset = offset + max_value_per_slot
        num = num | (v << ((i - 1) * bits_per_slot))
    end

    return num
end

return Decode(...)

Regards,
Xmilia