mBits

For any variable you use, (pb)Lua internally needs 64bit (8 full bytes!) to handle it (see The implementation of Lua 5.0 by R. Ierusalimschy, L. H. de Figueiredo and W. Celes).
No matter if you only need a byte, a word or even a bit. Eight bytes, no less.

mBits helps saving a huge amount of memory by using an arbitrary bit-width for storage (1..32) in one (pb)Lua storage unit.

• 1/32 of mem needed for bit storage
• 1/16 of mem needed for 2-bit storage
• ...
• 1/2 of mem needed for word storage

Regarding the overhead, caused by the necessary routines, it only makes sense if you have large (n > ~200 = 1.6kB, native) sums of data to store (a map, measured values, ...).

mBits uses a 2 dimensional table for storage to overcome the 2^n table rise problem:

The size of a table is always 2^n.
If you store the 129th value in a table its size will change from 128 to 256 (1024 to 2048 bytes).
If you store the 513th value, from 4096 bytes to 8192 bytes(!).

So the worst case is having e.g. 513 values in a table, which then occupies the same amount of memory as 1024 values would take (minus 1 ;-)!

To overcome this dramatic memory loss, I decided to use a 2 dimensional table, which will lessen the growth of memory a little.

As of version 18a, pbLua supports (un)loading modules to save memory. Therefore I redesigned the original mBits version to a version that does not need "nxt.math"...

Just set your bit width:

mBits.cBitWidth=<1..32>

Write values with:

mBits:set(<address>, <value>)

And read them back via:

mBits:get(<address>)

In all cases, make sure <value> does not exceed your chosen bit width and keep <address> positive...

-- mBits
-- Multiple bit storage class
--
-- Does not need nxt.math!
--
-- ASkr, 2009

mBits={}
mBits.cTabWidth=128   -- do not change!
mBits.cBitWidth=9     -- bit width to store (1, 2, 3, .. 32)


function mBits:set(address,value)
  local row=(address/self.cTabWidth)+1
  local col=1+(address%self.cTabWidth)/(32/self.cBitWidth)
  local ind=address%(32/self.cBitWidth)
  local val

  if self[row]==nil then
    self[row]={}
  end

  if self[row][col]==nil then
    self[row][col]=0
  end

  val=self[row][col]*2^(32-mBits.cBitWidth-(ind*mBits.cBitWidth))

  if val < 0 then
    val=(val-0x80000000)/(2^(32-mBits.cBitWidth))
    val=val+(2^(mBits.cBitWidth-1))
  else
    val=val/(2^(32-mBits.cBitWidth))
  end

  val=self[row][col]-val*(2^(mBits.cBitWidth*ind))
  self[row][col]=val+value*(2^(mBits.cBitWidth*ind))

end


function mBits:get(address,value)
  local row=(address/self.cTabWidth)+1
  local col=1+(address%self.cTabWidth)/(32/self.cBitWidth)
  local ind=address%(32/self.cBitWidth)
  local val

  val=self[row][col]*2^(32-mBits.cBitWidth-(ind*mBits.cBitWidth))
  if val < 0 then
    val=(val-0x80000000)/(2^(32-mBits.cBitWidth))
    val=val+(2^(mBits.cBitWidth-1))
  else
    val=val/(2^(32-mBits.cBitWidth))
  end

  return val

end

Eine klitzekleine deutsche Version kann man hier finden.