Bit Twiddling Again? – How I finally came to my senses

Right after I published my last little missive, I saw an announcement that VNC is available on the Chrome browser. Go figure…

It’s been almost a year since I wrote about stuff related to serialization: Serialization Series

Oh, what a difference a year makes!  I was recently implementing code to support WebSocket client and server, so I had reason to revisit this topic.  For WebSocket, the protocol specifies things at the bit level, and in bigendian order.  This poses some challenges for the little-endian machines that I use.  That’s some extreme bit twiddling, and although I did revise my low level BitBang code, that’s not what I’m writing about today.

I have another bit of code that just deals with bytes as the smallest element.  This is the BinaryStream object.  BinaryStream allows me to simply read numeric values out of a stream.  It takes care of handling the big/littleendian nature of things.  The BinaryStream wrapps any other stream, so you can do things like this:

local mstream = MemoryStream.new(1024);
local bstream = BinaryStream.new(mstream, true);

bstream:WriteInt16(0x00ff);
bstream:WriteInt16(0xff00);

mstream:Seek(0);

print(bstream:ReadInt16())
print(bstream:ReadInt16())

This quite handy for doing all the things related to packing/unpacking bytes of memory. Of course there are plenty of libraries that do this sort of thing, but this is the one that I use.

The revelation for me this time around had to do with the nature of my implementation. In my first incarnation of these routines, I was doing byte swapping manually, like this:

function BinaryStream:ReadInt16()

  -- Read two bytes
  -- return nil if two bytes not read
  if (self.Stream:ReadBytes(types_buffer.bytes, 2, 0) <2)
    then return nil
  end

  -- if we don't need to do any swapping, then
  -- we can just return the Int16 right away
  if not self.NeedSwap then
    return types_buffer.Int16;
  end

  local tmp = types_buffer.bytes[0]
  types_buffer.bytes[0] = types_buffer.bytes[1]
  types_buffer.bytes[1] = tmp

  return types_buffer.Int16;
end

Well, this works, but… It’s the kind of code I would teach to someone who was new to programming, not necessarily the best, but shows all the detail.

Given Lua’s nature, I could have done the byte swapping like this:

types_buffer.bytes[0], type_buffer.bytes[1] = types_buffer.bytes[1], types_buffer.bytes[0]

Yep, yes sir, that would work. But, it’s still a bit clunky.

I have recently also been implementing some TLS related stuff, and in TLS there are 24-bit (3 byte) integers. In order to read them, I really want a generic integer reader:

function BinaryStream:ReadIntN(n)
  local value = 0;

  if self.BigEndian then
    for i=1,n do
      value = lshift(value,8) + self:ReadByte()
    end
  else
    for i=1,n do
      value = value + lshift(self:ReadByte(),8*(i-1))
    end
  end

  return value;
end

print(bstream:ReadIntN(3))

Well, this will work if there’s 1, 2, 3, or 4 byte integers. Can’t work beyond that because the bit operations only work up to 32 bits. But, ok, that makes things a lot easier, and reduces the amount of code I have to write, and puts all the endian stuff in one place.

Then there’s 64-bit, float, and double.

In these cases, the easiest thing is to use a union structure:

ffi.cdef[[
typedef union  {
  int64_t		Int64;
  uint64_t	UInt64;
  float 		Single;
  double 		Double;
  uint8_t bytes[8];
} bstream_types_t

function BinaryStream:ReadBytesN(buff, n, reverse)
  if reverse then
    for i=n,1,-1 do
      buff[i-1] = self:ReadByte()
    end
  else
    for i=1,n do
      buff[i-1] = self:ReadByte()
    end
  end
end

function BinaryStream:ReadInt64()
  self:ReadBytesN(self.valunion.bytes, 8, self.NeedSwap)
  return tonumber(self.valunion.Int64);
end

function BinaryStream:ReadSingle()
  self:ReadBytesN(self.valunion.bytes, 4, self.NeedSwap)
  return tonumber(self.valunion.Single);
end

function BinaryStream:ReadDouble()
  self:ReadBytesN(self.valunion.bytes, 8, self.NeedSwap)
  return tonumber(self.valunion.Double);
end

Of course, with Lua, the 64-bit int is limited to only 52 bits, but the technique will work in general. The Single and Double, you just need to get the bytes in the right order and everything is fine. Whether this is compatible with another ordering of the bytes or not depends on the other application, but at least this is self consistant.

This incarnation uses functions a lot more than the last incarnation. This is the big revelation for me. In the past, I was thinking like a ‘C’ programmer, and essentially trying to do what I would do in assembly language. Well, I realize this is not necessarily the best way to go with LuaJIT. Also, I was trying to optimize by getting stuff into a buffer, and messing around with it from there, assuming getting stuff from the underlying stream is expensive. Well, that simply might not be a good assumption, so I relaxed it.

With this newer implementation, I was able to drop 200 lines of code, out of 428. That’s a pretty good savings. This in and of itself might be worthwhile because the code will be more easily maintained, due to smaller and simpler implementation.

So, every day, I see and hear things about either my own code, or someone else’s and I try to apply what I’ve learned to my own cases. I’m happy to rewrite code, when it results in smaller tighter, more accurate coding.

And there you have it.

---