Re: [FUN] Compress number in 2 bytes

[Xmilia Hermit <xmilia.hermit@...>]

> This problem is just for fun.
Thank you, nice problem. It was fun to play around with it.

> What value of N can you reach with your own compressor and decompressor?

I'm certain I have a solution for N = 0x7FFFFFFFFFFFFFFF. If lua would 
allow larger values these would be no problem too. However, I don't want 
to wait years to test every posibility.

This code abuses ordering in the hash part of the table and quirks in 
locating a slot if a key needs to be put outside of their main slot.
The basic idea is to allocate every second slot and the slots between 
them are allocated based on the bits we want to send.
Before sending every value is set to nil so that the check is happy.
The decoder restores every second slot and then allocates values that 
would go into a slot that is occupied. These values won't go into slots 
that where set in the encoder and so we can transmit bits.

However, this abuses undefined behaviour and might not work on other 
implementations of lua.

-- compressor.lua
local num_bits = 64

function Encode(what)
    local tab = {}
    for i = 3, num_bits * 4 + 4, 2 do
        tab[i] = 1
    end
    local top = num_bits * 4 - 2
    for i = 1, num_bits do
        if (what & (1 << (i - 1))) ~= 0 then
            tab[top] = 1
        end
        top = top - 2
    end
    for k, v in pairs(tab) do
        tab[k] = nil
    end
    return tab
end

return Encode(...)

-- decompressor.lua
local num_bits = 64

function Decode(tab)
    for i = 3, num_bits * 4 + 4, 2 do
        tab[i] = 1
    end
    local top = num_bits * 4 - 3
    local step = (num_bits * 4) - 1
    tab[step * 2] = 1
    tab[step * 3] = 2
    local num = 0
    for i = 1, num_bits do
        local k, v = next(tab, top)
        if v == 1 then
            num = num | (1 << (i - 1))
        else
            tab[step * (i + 3)] = 2
        end
        top = top - 2
    end
    return num
end

return Decode(...)