lua-users home
lua-l archive

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


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(...)