The Lazy Programmer looks at PE files

I thought I’d try and apply my bit twiddling skills against an interesting problem.  I have reason to look at PE files, or ELF, or Mach-O, and do some interesting stuff based on what I find there.  My experience dealing with these executable file formats is fairly limited.  I probably knew about the inner workings of Elf back in the day, but I’ve never had any real need to know the depts of PE files.

How hard could it be?  It’s just a bunch of bits and bytes right?

The hardest thing for such a challenge is finding a good source of information on the subject.  In the case of PE file format, I started by getting the Microsoft PE File Format Specification.  You have to accept a license agreement before you can download it.  That document is full of information.  It’s a bit cryptic in places though.  It doesn’t spell out in absolute detail what the DOS header up front looks like.  It just says “yah, it’s there, and it should start with “MZ”.

Like all things modern, I turned to the internet to get the real skinny on the format in question.  I found one really good tutorial on the PE format, presented by CodeBreakers Magazine.  This one is really interesting because it goes into intricate details about what’s in the file, how its used, how viruses are created and stashed away.  The only challenge it has is that it doesn’t reflect all forms of the PE file format.  It was written in 2006, so it’s missing some information.  Still, it makes for a good companion to the MS document because it actually explains everything.

As well as having these raw reference materials, I also found a couple of tools of use.  First was HexEdit.  This is one of those simple file viewers that allows you to see the file in Hex form, which is great when you’re trying to confirm what you’re reading.  Another tool that is very useful is PEBrowse Professional.  This tool parses the PE file, and shows you all the detailed information you could care to look at.  It includes a disassembler, and can read TYPELIB information if it’s present.  That’s great for dealing with COM interfaces.

The way I got started was to find define the meta data for important data structures that can be found in the file.  This includes things like:

• IMAGE_DOS_HEADER
• COFF
• PE32Header
• PE32PlusHeader
• IMAGE_SECTION_HEADER

and the like. The stream of code that deals with the first few pieces of information looks like this:

local buff, bufflen = copyFileToMemory("HeadsUp.exe")

local offset = 0
local dosinfo = IMAGE_DOS_HEADER(buff, bufflen, offset)
printDOSInfo(dosinfo)
offset = offset + dosinfo.ClassSize

local ntheadertype = MAGIC4(buff, bufflen, dosinfo:get_e_lfanew())
offset = ntheadertype.Offset + ntheadertype.ClassSize

local fileHeader = COFF(buff, bufflen, offset)
printCOFF(fileHeader)
offset = offset + fileHeader.ClassSize

-- Read the 2 byte magic for the optional header
local pemagic = MAGIC2(buff, bufflen, offset)

local peheader=nil
if IsPe32Header(pemagic) then
    peheader = PE32Header(buff, bufflen, offset)
elseif IsPe32PlusHeader(header) then
    peheader = PE32PlusHeader(buff, bufflen, offset)
end

printPEHeader(peheader);

That’s a start. From here, the basics are in hand, and other bits and pieces from the file can be loaded in. Not bad from not knowing anything about PE files to being able to browse the basics. Of course, Windows gives you plenty of library routines which make this trivial work, but, perhaps I want to be able to perform this little dance without using Windows at all.

The real work comes when the parsing is more involved, including relative offsets to base addressed stuff, and so on and so forth.

I like the ease of programming like this though. After rough data structures are defined, I’m left with just sliding them into the right positions along a buffer, and reading what I find there.

Serialization 104 – Pixel Packing Pugilism

Do you ever wonder what’s really going on inside that computer? I mean, you layout some data structure, all nice and neat. You pack tightly using bit fields, thinking you’ve written the most tightly packed conservative bit of code known to man. And then you go and try to access the structure, to set or get a value.

Well, truth be told, there’s no such thing as a 2-bit value, so somehow, the machine/compiler coerces that into something it can deal with, either a int8_t, or int16_t, or int32_t, or what have you. Yah, it’s only a couple of instructions, and it all happens transparently, and it’s super scalar (or not), and runs in parallel without stalling, and how many angels can dance on the head of a transistor anyway…

Often times, when you’re dealing with a protocol, you get something in the mail that describes a ‘header’ like this:

	The Rtp header has the following format:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |V=2|P|X|  CC   |M|     PT      |       sequence number         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                           timestamp                           |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |            synchronization source (SSRC) identifier           |
    +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
    |    contributing source (CSRC) identifiers  (if mixers used)   |
    |                             ....                              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

     V = Version
     P = Padding
     X = Extensions
     CC = Count of Contributing Sources
     M = Marker
     PT = Payload Type

And it looks just like that, complete with ASCII art and everything. Take a look at some of the internet standards if you don’t believe me.

What this is telling me, is that in order to communicate using the Rtp protocol (which I really want to do), I will receive a packet off the networking wire that can be described by this header. It gets a bit dicey after CSRC, but essentially the header is all I’d care about up front. In particular, I’m interested in the sequence number, timestamp, and Payload Type.

Since I have trained myself to describe my data structures in a more abstract form, it looks like this:

RTPHeader_Info = {
    name = "RTPHeader";
    fields = {
	{name = "Version", basetype = "uint8_t", subtype="bit", repeating = 2};
	{name = "Padding", basetype = "uint8_t", subtype="bit", repeating = 1};
	{name = "Extensions", basetype = "uint8_t", subtype="bit", repeating = 1};
	{name = "ContributingCount", basetype = "uint8_t", subtype="bit", repeating=4};
	{name = "Marker", basetype = "uint8_t", subtype="bit", repeating=1};
	{name = "PayloadType", basetype = "uint8_t", subtype="bit", repeating=7};
	{name = "SequenceNumber", basetype = "uint16_t"};
	{name = "TimeStamp", basetype = "uint32_t"};
	{name = "SSRC", basetype = "uint32_t"};
    };
};

Armed with the previously developed CStructFromTypeInfo(info) function, I can easily create the following structure:

typedef struct RTPHeader {
    uint8_t Version : 2;
    uint8_t Padding : 1;
    uint8_t Extensions : 1;
    uint8_t ContributingCount : 4;
    uint8_t Marker : 1;
    uint8_t PayloadType : 7;
    uint16_t SequenceNumber;
    uint32_t TimeStamp;
    uint32_t SSRC;
} RTPHeader;

I can even create easy serialize/deserializers which can go from a stream to this structure and back. But, wait a second. Should I?

The way networking traffic works, you are handed a chunk of data, and even if you are “streaming”, you get a certain amount of data in a fixed sized buffer. Depending on your application, you may choose to copy that data, or just look at values and take some actions based on what you see. If you’re doing something like playing audio, you’re probably going to copy the buffer into another part of the system that deals with playing audio. If you’re just doing some filtering, or some simple command where the buffer isn’t needed, you’ll take take what you want and let it return back to the system unharmed.

So, let’s assume you don’t really want to copy the buffer at all, but you need to get values out of it, or perhaps set some values in it before passing it along. Or, perhaps you’re at the head end, and you want to construct a header package, right there inside the buffer that some other part of the system has handed you. You don’t want to cons up a structure, just for the convenience of being able to use a function to write a value into a memory location, just so you can copy that whole structure into the buffer. And what about the endianness of it all!!

OK. So, clearly there must be another mechanism that can be employed to achieve the following flow:

• Create a buffer of a specific size
• Write values into the buffer at specific bit locations
• Send the buffer into the networking stack without any copying

Well, from the previous expose on bit banging, two functions were created:

setbitstobytes(bytes, startbit, bitcount, value, bigendian)
getbitsfrombytes(bytes, startbit, bitcount)

With these two functions, that’s all you need to be able to set a value at any location anywhere in a buffer. That is, any value up to an int32_t. Going beyond that is not impossible as you can always just break it up.

At any rate, this looks like another opportunity to do some codegen. So, given the same exact meta information that was used to create that typedef, and the serializers, I could create an offsets table. Basically, I need a table that contains the following information for each field:

name, offset, number of bits

Easy enough, and the BitOffsetsFromTypeInfo(desc) can do the trick. Given the previous header description, the following table can be generated:

0	2	Version
2	1	Padding
3	1	Extensions
4	4	ContributingCount
8	1	Marker
9	7	PayloadType
16	16	SequenceNumber
32	32	TimeStamp
64	32	SSRC

It is pretty printed here, but in reality, it’s just a standard Lua table where each entry is itself a table containing the essential information we need.

With that, it looks like everyting is in place to auto gen up some field accessors. Those are just simply assembled strings that look like this:

function CreateBufferFieldWriter(field)
    return string.format([[
function set_%s(bytes, value)
    setbitstobytes(bytes, %d, %d, value);
end
]], field.name, field.offset, field.size);
end

function CreateBufferFieldReader(field)
    return string.format([[
function get_%s(bytes)
    return getbitsfrombytes(bytes, %d, %d);
end
]], field.name, field.offset, field.size);
end

As a simple example, dealing with the Marker field would look like this:

function set_Marker(bytes, value)
    setbitstobytes(bytes, 8, 1, value);
end

function get_Marker(bytes)
    return getbitsfrombytes(bytes, 8, 1);
end

There is another function that just kind of ties all this together. The CreateBufferAccessor(desc) function takes our structure descriptor, and autogens all those appropriate accessors.

function CreateBufferAccessor(desc)
    local funcs = {}

    -- first create the offsets structure
    local offsets = BitOffsetsFromTypeInfo(desc)

    -- go through field by field and create the
    -- bit of code that will write to the buffer
    for _,field in ipairs(offsets) do
        table.insert(funcs, CreateBufferFieldWriter(field))
        table.insert(funcs, CreateBufferFieldReader(field))
    end

    return funcs
end

At this point we have a table that is full of strings that represent the functions that are used to set and get values on our buffer. And now, finally, to put it to use.

function test_BufferClass()
    local funcs = CreateBufferAccessor(RTPHeader_Info)
    local funcstr = table.concat(funcs)

    -- Now that we have the functions, compile them
    -- so we can try to use them
    local f = loadstring(funcstr)
    f()

    -- Finally, try to set some values
    -- Create a buffer first to act as the header storage
    local buff = ffi.new("uint8_t[2048]")

    set_Version(buff, 2)
    set_Padding(buff,0)
    set_Extensions(buff,1)
    set_ContributingCount(buff, 3)
    set_Marker(buff, 1)
    set_PayloadType(buff, 15)
    set_SequenceNumber(buff, 127)
    set_TimeStamp(buff, 523)
    set_SSRC(buff, 722)

    print("Version: ", get_Version(buff))
    print("Padding: ", get_Padding(buff))
    print("Extensions: ", get_Extensions(buff))
    print("Count: ", get_ContributingCount(buff))
    print("Marker: ", get_Marker(buff))
    print("Payload Type: ", get_PayloadType(buff))
    print("Sequence: ", get_SequenceNumber(buff))
    print("Timestamp: ", get_TimeStamp(buff))
    print("SSRC: ", get_SSRC(buff))
end

The output of running this is:

Version: 	2
Padding: 	0
Extensions: 	1
Count: 	3
Marker: 	1
Payload Type: 	15
Sequence: 	127
Timestamp: 	523
SSRC: 	722

And that’s exactly what I would have expected it to be. It appears that I can in fact round trip values into and out of the buffer. Now, if I were a true nutter, I’d benchmark this, and compare to the case where I’m consing up a structure and doing copying back and forth. But, my gut tells me I could better spend my time optimizing this technique and only optimize if it’s not meeting my needs. The easy of programming is just too tremendous to pass up.

I wrote Rtp code way long back, and it was a lot nastier looking with funny symbols such as ‘~^&|’ littered all over the place, with hard coded constants, and all manner of other bug inducing nasties laying about. With this version of things, I feel much more relaxed, and confident that the implementation is correct. Even when it is not correct, there are only a couple of places to look in order to change things. This also isolates all the endianness into one place as well, so I don’t have to deal with that anywhere in my higher level code.

There are a couple of nifty tricks here that are good from Lua. Since I can execute new code from a string on the fly at any time, I can construct the serialization code on the fly, and just execute it, without every having to actually have the code laying around anywhere in my environment. I know when using other technologies such as protocol buffers, it becomes a pain to change things because you do have to “compile” code, and distribute it. That makes for a very fragile system indeed. In the code here, the description can change, and can even come from another trusted source, and the serialization will just change automatically, as new serialization code can be constructed automatically. That’s a fairly powerful construct, and solves a very challenging maintencance problem. If you add versioning, you can deal with the versioning as well. Just use the proper serializer for the specific version of the header that comes in. It would only be brought in if a header of a new type is seen. Otherwise, you’re never bothered with it.

The last thing has to do with the convenience functions constructed. In the code here, I just created the functions in the global namespace. They could just as easily be stuffed into a list, or into a ‘class’. That’s the beauty of autogen’d code. It’s very small and easy to change to get a maximal effect.

Well, there you have it. I’m able to meet my goals. When I need to write out a new RtpHeader, I just take a buffer (probably from a circular queue), and write in the appropriate header values. Then, I can use the same buffer to fill in the payload information, and finally use the same buffer to write out to the network interface. Assuming the buffer was allocated from the system heap, and I have turned off send buffering in my networking code, this will go straight out without additional copying. And that’s very good indeed.

I like programming like this. I get to be fully lazy, assured that things will just work the way they are supposed to. I can read specs, and code them up fairly painlessly. The next step is to encode the actual protocol itself. It might be that Lua itself is the way to encapsulate the protocol description. No abstraction necessary. We’ll see.

The Existential Program

In roughtly 1990, I wrote this program called “Who’s Calling?” for the Nascent NeXT computer.  The program itself was one of those early day PIM type programs, you know, contacts, calendar, etc.  The most interesting thing about it at the time was the ‘security’ mechanism I used to prevent random copying.  Basically, it had this little routine it ran when you installed it.  It would find a bit of unique information about your machine, and use that as key information to create a digest.  Once installed, every time the program launched, it would check that digest, and try to decode based on the bit of information from the currently executing machine.  If it got back what it expected, it would continue running.

It was a fairly simple process, that prevented casual copying.  In the end, it was probably more trouble than it was worth, but while coming up with that little trick, I headed down this path of exploring identity.  I asked myself questions such as “how can a program know when it has been tampered with”?  “Does a program have an identity?”.  At the same time, I was writing some collaboration apps, and other questions of authorization and authentication came up there as well.  If I’m collaborating with several people in a session, who has the right to take over the pen?  Does a new user requesting entrance into the collaboration have the right permissions to do so?  How do I know who they are?

This was all pre-internet boom, so it was very interesting.  Then the internet came along, and we went through a round of Berkeley style “free love, free information, free sharing…”, and then it all came crashing down.

But, now we find ourselves at the internet trough again, and those old questions of identity and authorization are coming back, but it a much more serious way.  People are exchanging banking information, and they really don’t want that shared or used by unauthorized entities.

So, I find myself contemplating identity and authorization in a big way, and I find myself going back to the very same old questions.  Does a program have an identity?  What is the smallest unit of existance?  As far as computers are concerned, I can tie this to the idea of the computicle.  Does a computicle have an identity?  The answer to me is yes, and in fact, this is part of what defines a computicle in the first place.

Looking back, I defined a computicle as having a few key traits:

• Ability to receive input
• Ability to perform some operations
• Ability to communicate with other computicles

There is an implied identity in here.  You have to ask the question, “What has the Ability to…?”

You wouldn’t believe how this comes up in some of the most esoteric and mundane places.  For example, once I create multiple cooperating threads in my super computer simulator, I have to answer the question “Who’s responsible for managing chunks of memory?”

The scenario is simple.  Let’s say I have one computicle which does nothing more than generate keyboard/mouse events, and hands them off to other computicles to deal with.  Every time it creates an event, it allocates a chunk of memory, to hand off to the other threads.  Now, once that chunk of memory is created, who owns it?  The keyboard/mouse generator could retain ownership, but for how long?  Does a recipient have a guarantee as to when it might be freed or reused?  Should the recipient copy it?  How long do they have to copy it before it is stale?  Can they share this chunk of memory with others, or what?  It’s such a simple thing, but it seems so hard to deal with the combinatoric explosion.

Well, there are a certainly a few ways to deal with things.  First, I can go back and look at memory allocation.  I created a couple of simple heap structures a while back, and I recently revisited and updated them based on my work with the multiple threads.  One of the questions I was trying to answer is, can the memory chunk deal with its own destiny?  Said in less philosophical terms, can I use the GC system of Lua to manage the life of a chunk of memory in a reasonable and predictable way.

 
So, here’s a couple of data structures to deal with Heap allocated memory (Win32):

ffi.cdef[[
typedef struct {
    void *    Data;
    int32_t   Size;
    HANDLE    HeapHandle;
    DWORD     owningthread;
} HeapBlob;

typedef struct {
    HANDLE  Handle;
    int     Options;
    size_t  InitialSize;
    size_t  MaximumSize;
    DWORD	owningthread;
} HEAP;
]]

There are a couple of ways to allocate stuff in Lua. The regular way, without doing anything fancy, is to just create your thing, and start using it:

local myList = {}
myList.name = "William"
myList.job = "Programmer"

Eventually, once there are no references to your little list, it will magically disappear, being swept away by the garbage collection system.

Then, there’s allocating stuff using LuaJIT FFI:

local myChunk = ffi.new("char[256]")

Something allocated in this way will also be garbage collected, when the ‘myChunk’ variable no longer has any references to it. As long as you’re running with a single threaded environment, and you’re not passing your variables off to any other thread to deal with, this will work just fine. But, what if you need to have your chunk of memory last longer, even if you lose all references to it from the creating side.

The third way of creating a chunk of memory is to use a direct system memory allocation call. In the case of Windows, I could do the following:

local ptr = kernel32.HeapAlloc(self.Handle, flags, nbytes)

Ignoring for the moment where that ‘kernel32′ and self.Handle came from, essentially, you’ll get back a pointer to a chunk of memory that Windows knows about. Lua doesn’t know anything about this as a chunk of memory though. I could use ffi and tell the gc about it, and what function to call once ptr is no longer referenced, but really, if that is what you need, then you can just use the previous method of ffi.new(…).

So, here we have a lonely pointer, all allocated, and ready to use. I’d like to capture a bit of information about the creation event. Back to that existential programming, and back to the HeapBlob data structure.

I could do the following to assign the pointer to one of my HelpBlob data structures:

local blob = ffi.new("HeapBlob", ptr)

In this case, I have a HeapBlob struct, with the Data element initialized to the value the pointer held. So far, nothing has changed over the plain old ordinary ffi.new(), expect for the fact that I’ve just introduced a nice memory leak, wrapped up in an object. I need a bit more meat on the bones of the HeapBlob object. I want it to get in on the act of memory management. Specifically, when there are no more references to the object, I want the HeapBlob to deallocate the chunk of memory, thus, eliminating the memory leak:

So, I create a metatype to associate some functions with this simple data structure:

HeapBlob = nil
HeapBlob_mt = {
    __gc = function(self)
        if self.HeapHandle == nil or self.owningthread == 0 then return nil end

        if self.owningthread == kernel32.GetCurrentThreadId() then
            local success = kernel32.HeapFree(self.HeapHandle, 0, self.Data) ~= 0
        end
    end;

    __tostring = function(self)
        return string.format("Blob: Size: %d  Thread: %d",
            self.Size, self.owningthread);
    end;

    __index = {
        GetSize = function(self, flags)
            flags = flags or 0

            if self.HeapHandle == nil then return 0 end

            local result = kernel32.HeapSize(self.HeapHandle, flags, self.Data)

            return result
        end,

    IsValid = function(self, flags)
        flags = flags or 0
        if self.HeapHandle == nil then return false end
        local isValid = kernel32.HeapValidate(self.HeapHandle, flags, self.Data)
        return isValid
    end,

    ReaAlloc = function(self, nbytes, flags)
        flags = flags or 0
        if self.Heap == nil then return false end
        local ptr = kernel32.HeapReAlloc(self.HeapHandle, flags, self.Data, nbytes)
        if ptr == nil then return false end
        self.Data = ptr;
        self.Size = nbytes;
        return true
    end,
    }
}
HeapBlob = ffi.metatype("HeapBlob", HeapBlob_mt)

There’s a few functions in here, but the __gc function is the one that gets called whenever an instance of the HeapBlob goes out of scope, and has no further references to it. So, in the simplest case, you clould do the following:

HeapBlob(ptr)

And we’re back to having a handle on a piece of memory, and nothing will occur at __gc time, because we have not set an owningthreadid, and our self.HeapHandle is nil. Well, this is actually a good thing. This can be seen in a two thread scenario.

-- Thread 1
local ptr = Heap:Alloc(256)
passMemoryPointerToThread(ptr, 256, takeownership=false, heaphandle=nil)

-- Thread 2
local ptr = ReceiveMemoryPointerFromThread(ptr, size, takeownership, heaphandle)
local threadid = 0
if takeownership then threaid = Sys.GetCurrentThreadId() end
local blob = HeapBlob(ptr,size,heaphandle, 0, threadid)

In this scenario, thread 1 will retain responsibility for the allocated memory. It communicates this information first, by not giving the handle to the heap that was used to allocate the chunk of memory, and second by giving a flag indicating its desire. Really the witholding of the heaphandle is enough of a hint.

Thread 2 is free to go ahead and use the HeapBlob, pass it amongst its friends, etc. Then, when it’s no longer using the blob, the structure will be garbage collected, and nothing will happen to the bit of memory.

This HeapBlob could have additional information, such as a ref count, which can be incremented any time there is a new reference to it, but then it starts to look like a COM program.

If you want to pass along the Heap blob, and allow the second thread to take ownership, thread 1 would simply supply the heap handle. In that scenario, thread2 would have all the information it needs to manage the chunk of memory in ways that it deems appropriate, and it has received an explicit handoff from thread1 imploring it to do so.

This starts to give me better control of memory, which allows me to more strictly control the mechanisms between collaborating threads.

Getting back to Existence, if I can isolate and define one bit of existence, then I’m improving my ability to write fairly independent programs. I haven’t answered the question “who am I”, and “how am I different from another” as yet. But, at least now I have a way to communicate that I can control. I suspect answering the “who am I” thing will involve some GUID or other mechanisms, including ‘claims’ and possibly certificates. That will be an interesting exploration.

Serialization 102 – CodeGen

Emboldened by the possibilities offered by simple BitRead/BitWrite, and a streaming interface, I’ve taken on the next step of the serialization process. Being the lazy error prone coder that I am, I’m looking for a way to have the machine do as much of the coding as possible. The machine is pretty dumb though. You have to very explicitly describe things to it before it will give you any help.

There are many ways to describe a data structure. One of the earlier stated design goals of Lua was for it to be a data description language. Tada! Since my primary goal is to stay within the confines of Lua as much as possible, it makes sense to use Lua itself to describe data structures.

My simplest example:

moveto = {
    name = "MoveTo";
    fields = {
        {name="x", basetype="int32_t", ordinal=1},
        {name="y", basetype="int32_t", ordinal=2},
    };
};

This is intended to represent a command in my drawing system. Since I’m in Lua, I could just use this structure as it is, but it would be kind of clunky. This type of structure is what you might see with XML Schema and the like. Very verbose, lots of curly braces, very complete, but very unfriendly to the programmer.

But, my data structures don’t change much, so I don’t mind writing it in this form initially, because once in this form, I can easily transform it into other forms. If I want it to show up as a C structure, I have a function call for that:

cstruct = CStructFromTypeInfo(moveto )

print(cstruct);

typedef struct MoveTo {
	int32_t x;
	int32_t y;
} MoveTo;

Well, that’s convenient. If I wrap that in a ffi.cdev[[]], I will have a structure that I can pass back and forth between the two worlds. If I do:

MoveTo = ffi.typeof("MoveTo");

Then I’ll have a data structure that I can easily access from the Lua side as well. Then my code can easily look like:

myStruct = MoveTo(10,20);
graphics:Deliver(myStruct);

Or what have you. But, this is about serialization isn’t it? Well, Serialization starts with a data definition. Depending on what system you’re on, that data is readily available, or it needs to be augmented in some way. In Lua, there really isn’t much of a data type system. Only a solitary type of number, string, null, table, bool, string, and that’s about it. So, you lose out on the other data types, and bitfields, and enums, date… If you were using C++, there’s the Runtime Type Information (RTTI), and that’s a big hairy beast that bloats your code, but gives you some type information at runtime. Similar for Objective-C. C# has a great type system, where you can get all information for any field, fairly easily.

Given enough type information, you should be able to serialize an object/structure, at least at a superficial level. So, what can I do with what I’ve defined here so far? Well, I don’t want to write the serializer, even though it’s only a couple lines of code, so I do the following:

local ser = CTypeSerializer(EMRTypes[EMR_MOVETOEX])
print(ser);

function write_MoveTo_ToStream(stream, value)
	stream:WriteInt32(value.x);
	stream:WriteInt32(value.y);
end

And similar for the deserializer. Of course, this is just a raw function to hydrate a structure from a stream. It is up to a ‘protocol’ to determine when this particular object is to be deserialized, vs any other. Typically, the protocol will place a marker, perhaps the name of the type, in the stream to be read out later.

This is great. I can even describe fairly complex structures with things like bitfields. Here’s a couple from the networking world:

IPv4Header_Info = {
    name = "IPv4Header";
    fields = {
    {name = "version", basetype = "uint8_t", subtype="bit", repeating = 4, ordinal =1};
    {name = "headerlength", basetype = "uint8_t", subtype="bit", repeating = 4, ordinal =2};
    {name = "typeofservice", basetype = "uint8_t", repeating = 1, ordinal =3};
    {name = "totallength", basetype = "uint16_t", repeating = 1, ordinal =4};
    {name = "identification", basetype = "uint16_t", repeating = 1, ordinal =5};
    {name = "blank", basetype = "uint16_t", subtype="bit", repeating = 1, ordinal =6};
    {name = "DF", basetype = "uint16_t", subtype="bit", repeating = 1, ordinal =7};
    {name = "MF", basetype = "uint16_t", subtype="bit", repeating = 1, ordinal =8};
    {name = "fragmentoffset", basetype = "uint16_t", subtype="bit", repeating = 13, ordinal =9};
    {name = "ttl", basetype = "uint8_t", repeating = 1, ordinal =10};
    {name = "protocol", basetype = "uint8_t", repeating = 1, ordinal =11};
    {name = "headerchecksum", basetype = "uint16_t", repeating = 1, ordinal =12};
    {name = "source", basetype = "uint32_t", repeating = 1, ordinal =13};
    {name = "destination", basetype = "uint32_t", repeating = 1, ordinal =14};
    };
};

IPv6Header_Info = {
    name = "IPv6Header";
    fields = {
    {name = "version", basetype = "uint32_t", subtype="bit", repeating = 4};
    {name = "priority", basetype = "uint32_t", subtype="bit", repeating = 4};
    {name = "flowlabel", basetype = "uint32_t", subtype="bit", repeating = 24};
    {name = "payloadlength", basetype = "uint16_t"};
    {name = "nextheader", basetype = "uint8_t"};
    {name = "hoplimit", basetype = "uint8_t"};
    {name = "source", basetype = "uint8_t", repeating = 16};
    {name = "destination", basetype = "uint8_t", repeating = 16};
    };
};

In the case of the Ipv4Header, I use all the bells and whistles (except enum). There are different types, bitfields, repeatings, and ordinals. I left out the “required” attribute, because the default is ‘true’. In the IPv6 case, I even left out the ordinals, as it assumes they are in the order specified (must iterate using ipairs). Depending on what you’re doing, even the field name might not be necessary. For example, if you’re implementing a stream processor, you just need to know the type, not the name.

The following data structures are created from these type info lists.

typedef struct IPv4Header {
	uint8_t version : 4;
	uint8_t headerlength : 4;
	uint8_t typeofservice;
	uint16_t totallength;
	uint16_t identification;
	uint16_t blank : 1;
	uint16_t DF : 1;
	uint16_t MF : 1;
	uint16_t fragmentoffset : 13;
	uint8_t ttl;
	uint8_t protocol;
	uint16_t headerchecksum;
	uint32_t source;
	uint32_t destination;
} IPv4Header;

typedef struct IPv6Header {
	uint32_t version : 4;
	uint32_t priority : 4;
	uint32_t flowlabel : 24;
	uint16_t payloadlength;
	uint8_t nextheader;
	uint8_t hoplimit;
	uint8_t source[16];
	uint8_t destination[16];
} IPv6Header;

And of course, their equivalent (de)serializers can be auto generated in the same way the first one was.

The amount of code needed to auto gen the structure, or the serializers is trivial. That means, it’s just as easy to do the same for any language you care to use. Many serialization schemes in use today use this mechanism. It’s quick and dirty, but it’s a bit bloated, and fragile when it comes to versioning things.

Google has this serialization technology called Protocol Buffers. Their flavor for communicating with things. I found this one project (came from within Google apparently) where they do streaming based Protocol Buffer parsing, instead of filling up existant objects. The upb project follows the same methodology as the old SAX XML parser. That is, register callbacks, and when the parser sees something in the stream, it calls your callback, and you do whatever you want with the results. Thus, the protocol does not force you to use structures, if that’s not appropriate for your usage pattern.

In my case here, I could utilize something like a upb parser, and either fill my structures, or not.  The code is trivial to change, so it’s not a design choice I have to make up front.  I can simply do what’s natural for whatever the situation is.

With these mechanisms in hand, it starts to become interesting as to what can be done automatically.  These are just raw structures though.  Typically, when trying to deserialize something, like an image, things get more complicated.  The data structure alone is not enough to tell you how to get stuff out of the stream.  If there’s compression involved, for example, you need to know about that and do something.  So, this technique is useful, and it’s a good downpayment on more complex mechanisms, but it’s just the beginning.

This is good enough though for most typical communications between threads in a multi-threaded program.  Now I can trivially create some “commands”, serialize them into memory packets, and send those packets between threads.  A no brainer!