The trouble with storing binary data structures

To start off our series of Programming posts, I’d like to start you off on a technical issue we bumped into yesterday. This isn’t a new issue for us, but running into it again made us think ‘Hey, this would be a great topic for our first technical article’.

Assumptions: You know some C, You know what a struct in C is.

So, as we were working yesterday on a patch for Majesty, we bumped into an issue

We had the following data structure (this is an abbreviation, the real structure is code we aren’t really allowed to just post on a website!)

struct datastruct
{
  char ltr;
  short key;
  int value;
};

Now, we were using this to read in a blob of binary data from the games datafiles. These data blobs had been stored from Windows when the game was made, and on testing, loaded just fine into Windows.

On Linux, however, reading the data failed.

struct datastruct datastuff;

//src is a data stream that is the same on Windows and Linux
memcpy(&datastuff,src,sizeof(datastuff));

The same code on Windows and Linux produces different results! Why can this be?

The Answer

The answer lies in how the struct is stored.

Windows was being told to ‘pack’ its data structures, to save memory. So the data in the structure was held as follows

Byte     0    1    2    3    4    5    6
Data  |-ltr-||--key--||-----value--------|

When we were using Linux to read this data back in, it was not packed in the same way. On Linux, the default alignment of a 32 bit machine is to align values on 32 bit boundaries, like so

Byte     0    1    2    3    4    5    6    7    8    9    10   11
Data   |-ltr-|              |--key--|          |-----value--------|

As you can see, if you are simply reading in a data stream, you will find that the ltr will be correct, the key will be reading bytes from the middle of the value, and the value could be absolutely anything!

So, how do you fix this?

gcc uses a pragma to resolve this. Use

#pragma pack(n)

on a line of itsown before the struct is defined, where n is the number of bytes you want to pack to. n must be a power of 2 (so 1,2,4,8,16…).

When you are finished defining things that need to be packed in a certain way restore it using

#pragma pack()

So, if you did, at the start of the file defining the structure

#pragma pack(1)

Then the datastructure will look the same as in the first example, all scrunched up into 7 bytes. If you use

#pragma pack(2)

Then the data structure will be aligned so that each element starts on a 2 byte boundry. This means that it will take up 8 bytes, and there will be a 1 byte gap between ltr and key, which would again cause problems.

The second packing example (the one with all the gaps) is a

#pragma pack(4)

example.

So, how do you detect this when you find your data is corrupted?

It isnt that hard to detect when this has happened. If your data is not the same when you read it in, and you are reading a whole struct in from a binary stream or blob, then chances are, it is a packing issue. Look at the bytes in the stream, try and match them up with the bytes you see in your struct, and see if you can see a pattern, see where bits are missing from the data stream when you look in your struct.

If the data in the struct matches the data in the stream, but the data when you read is different from the data you have saved, don’t forget that packing works both ways. If you have a struct that is packed using 32 bit (4 byte) boundries, and you write this to a stream, it will look like this

Byte     0    1    2    3    4    5    6    7    8    9    10   11
Data   |-ltr-|              |--key--|          |-----value--------|

The bits in the gaps (bytes 1,2,3,6,7) will still be saved, but they can be ANYTHING. Do not rely on them being 0, it isnt always the case.

So if you read this into a packed data structure, you will find that you read in the first byte correctly, you then read the key as 2 completely random bytes, and the value will be made up of bits of the key and random bytes!

We hope that this little tutorial has been helpful to you, and given you a bit of an understanding of this problem. If you spot any mistakes, or see ways to improve it, please drop us a comment on the article!

  • Share/Bookmark

Tags: , , , , ,

8 Responses to “The trouble with storing binary data structures”

  1. Eric says:

    Hi Michael,

    That’s very interesting. It means also we will get a new patch for Majesty ? I love this game, I continue to play it from time to time.

    I hope to read more programming articles in your blog.

    Regards,
    Eric

  2. basement cat says:

    I believe the best way to handle this is by writing an abstraction layer that takes care of reading and writing file data, and does so in a way which is consistent across different platforms.

    This library seems to be a pretty good example of how the issue can be solved: http://www.leonerd.org.uk/code/libpack/

  3. michael says:

    Yep, it means we have a new majesty patch on the way, its been on the way for a while, but its closer now.

  4. good article, I’m going to appreciate this blog, and now another use-case

    I have X2-The Threat on Linux (your product) and on Mac OS X (PPC – ported by VP).
    If I save a game on Linux, I can load it into the Mac OS X game and proceed.
    If I save the game on Mac OS X and load it into the Linux Version, X2 crashes. Can you provide a bug fix? to improve the alignmen ;-))
    I can send you a saved gamed from Mac OS X……

  5. doomwarriorx says:

    hopefully this sounds not to harsh. How could you port several games without not knowing this issue? It is a common problem for e.g. opensource games which were closed source before.
    Your solution isn’t good at all, because there are several cpu architectures which doesn’t support “packing” of data. It’s more a works for me, hopefully nobody other have to port my stuff to some exotic platform. So for platform independent communication it is a bad practice to memset into a structure and vice versa.

  6. michael says:

    We do know this issue, as we said at the start, this is something we solved ages ago, but we thought it would make an interesting read for people. we bumped into it again yesterday when we had some bad data reads, and that turned out to be the issue.

    I could’t agree more about the idea of saving data as a raw dump of a struct, it is a terrible idea if you ever want portability, but when something has been written without portability originally, and you have to then port it, this is the kind of thing you have to live with.

    The solution offered is the only one that makes sense, in our case, as if packed data has been saved into a datafile which cannot be changed, well, the only other option would be to memcpy into each element of the array one at a time. This is fine, but slower, and the example was for use in porting where you really do not want to change the original code too much. And if, for example, you are reading in a data structure with 300 elements (they exist) you really do not want to do sit there for 3 hours writing 300 memcpy instructions! If you are copying to an architecture that does not handle packed data, then you are going to have to do that, but the idea of the article was to illustrate the problem, and how we solved it for the architecture we are porting to, rather than to be all things to all people.

  7. I do not begrudge the LGP folks for porting the quick&dirty stuff, which rules the windows world.

    @doomwarriorx: I don’t think that there much space to change things without breaking compatibility with existing windows version (a saved game on linux should be playable on windows)..
    @michael: and a mac saved game on linux ;-)

    besides this is very unlikely that a commercial game will have a more exotic plattform than Linux/x86

  8. Mike Phillips says:

    Actually, that problem was the very first major problem in the Majesty port “Way Back When” — a packing/alignment issue was causing a crash because the data was being used as an index. (…and I could tell you stories about some similar fun at Loki :-) )

    Glad to see the torch was picked up and the binary will be updated :-)

Leave a Reply

To stop spam, please answer this simple question
What OS do we make games for

Please note: This site is fully moderated