  lua-l archive

• Subject: Re: [FUN] Compress number in 2 bytes
• From: Xmilia Hermit <xmilia.hermit@...>
• Date: Fri, 2 Jul 2021 14:03:08 +0200

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