Re: [FUN] Compress number in 2 bytes

[Paul Ducklin <pducklin@...>]

Not sure if I have misunderstood the subject line or the goal of this exercise, but how does turning a number (any number) into a Lua table compress it into two bytes?

In 16 bits you can uniquely encode 2^16 different values, and that’s the end of the discussion,surely?

On 4 Jul 2021, at 09:17, Xmilia Hermit <xmilia.hermit@gmail.com> wrote:

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