A little-known trick with C switches

March 3rd, 2009 by Michael Simms (CEO and head of Development)

OK, so this little programming post is nothing like rocket science, it really isn’t. It is, however, REALLY useful, and something that almost nobody knows about the C language. We came across it when we were porting a game a few years ago, and none of us had ever seen it before. We tried it, and it works!

So, lets take a C switch statement

switch (somenumber)
{
case 1:
case 2:
case 3:
  do_something();
  break;
case 4:
case 5:
case 6:
  do_something else();
  break;
}

Fairly standard, nothing too unusual here. However there is another way to do it!

switch (somenumber)
{
case 1 ... 3:
  do_something();
  break;
case 4 ... 6:
  do_something else();
  break;
}

Unfortunately, it doesn’t seem to work on anything other than C/C++, which is a shame!

Enjoy!

  • Share/Bookmark

Answering the LGP DRM questions

February 27th, 2009 by Michael Simms (CEO and head of Development)

Our new DRM system has probably generated as much debate as anything we have ever done. So, I thought that I should try and dispel some of the myths and rumours that have been going about, and give you some of the positive aspects of the system.

The first and most important issue I would like to address is that no, you do NOT require internet access to install or to play the games, you do not need a disc in your drive, and you do not need to enter in your key or password every time you play. These are all myths. You need to enter a key and password (and optionally your email address) when you install the game, and that is it. You do not need to worry about it again.

Our system uses a policy of ‘Innocent until proven guilty’ which means that you can ALWAYS play your game, unless the system knows for a fact that there is a reason you shouldn’t. This is the opposite to most DRM systems, which assume you do not have the right to, unless you prove you can.

Unfortunately, no system is foolproof, and, yes there is a small chance that a legitimate user could be locked out of their game, but the chance is rather low. It would require that the user lose their key AND to have not set an email address for their game, and are trying to reinstall it. Just forgetting your password is not enough to lose you access to the game, unless you did not set an email address.

We acknowledge that some users dislike ANY DRM, and you know what, so do we, but we have little choice when we have proved that more copies are pirated of our games than purchased. As a small company, we do not do DRM to try and rip people off, we add it because it is going to help keep us in business.

However bear in mind that this DRM works in your favour too. As well as the obvious, helps us keep making games, it also allows us to provide a method to allow you the customer to exert your rights as granted by the LGP license. When you buy any game from any company, you buy a license to install and use the software. The box and disc is just a delivery system. If you lose your copy of a Windows game, good luck getting it replaced for free (or for the cost of time and materials to send you a replacement at the most). But the thing is, you should. We fully believe that as you bought a license, then you have the right to play the game for as long as that license is valid. This is why, using our DRM system, we have now completed a new system that will allow users to get a new downloadable version of any game they have legitimately purchased. So if you lose all of your games somehow, the DRM’d ones will actually be MORE replaceable than the non-DRM’d ones, as they are the ones you can prove you have a license for.

Unlike other DRM systems that pretty much prevent you from selling on your license, the LGP system is set up to allow you to do so. In fact we have devised a system at http://keyserver.linuxgamepublishing.com which allows the seller of a game to transfer their license safely to a new owner, and for a potential buyer to check that a game they are being offered has a valid license key. This means that our DRM offers security for players that they are buying a real game that is playable, rather than with other DRM systems where you can buy a game on Ebay, and find out when it arrives it has a locked out key and the company that licenses the game will not unlock it.

We think that our system provides us with a bit of security, but it also gives you, the customer, benefits that counterbalance the fact we had to add in the DRM in the first place. It is thanks to the discussions we had with the community that we took out the requirement to be online when yiou register, and the requirement to be online when you start the game.

When all is said and done, we tried for years to stop people copying our games by asking nicely and appealing to peoples better natures. That didn’t work, and so we are left with DRM.

  • Share/Bookmark

How to search a data tree efficiently

February 23rd, 2009 by Michael Simms (CEO and head of Development)

This nice little method is one we used for PenguinPlay.

Assumptions: You know some C, and understand tree structures

If you have a whole load of data, lets say a hierarchy of categories with items in them, like in an online store, it is common to store this data in a tree. This allows you to move up and down the tree logically to access the data in the same way it is visualised.

With the logical way of doing this, there comes a problem of scalability. How do you find all of the categories that are below a certain point in the tree. Lets take a tree as an example

            +----(2)Windows
(1)Games----|               +----(5)Strategy
            +----(3)Linux---|                       +----(7)Action
            |               +----(6)First Person----|
            +----(4)Mac                             +----(8)RPG

Now to find all categories that are children of Linux, how do you do this?

Well, most of the time, the simplest way to write some code for this will find all of the categories that are children of Linux (5,6) and then for each of these find all of the children of these (7,8) and so on and so forth down the hierarchy.

This isn’t too inefficient in smaller trees, but imagine having ten levels, each with five branches at each level. You very quickly get an impossible number of items to deal with using this method.

So, how do we do this efficiently?

The solution is quite simple. It takes a moment to understand, and then it just makes you think ‘Why didn’t I think of that!’

Initially lets draw the above example again, but in a different way

+----------+
|          |
|          +------------+
|          | (2)Windows |
|          +------------+
|          |
|          +------------+
|          |            |
|          |            +-----------------+
|          |            | (5)Strategy     |
|          |            +-----------------+
|          |            |
|          |            +-----------------+
|          |            |                 |
|          |            |                 +-----------+
|          | (3)Linux   |                 | (7)Action |
| (1)Games |            | (6)First Person +-----------+
|          |            |                 |
|          |            |                 +-----------+
|          |            |                 | (8)RPG    |
|          |            |                 +-----------+
|          |            |                 |
|          |            +-----------------+
|          |            |
|          +------------+
|          |
|          +------------+
|          | (4)Mac     |
|          +------------+
|          |
+----------+

As you can see, if you look at it, the layout above shows the exact same data that is shown in the first tree, just displayed differently.

So, now onto how this helps us. Firstly, take your first category, (1)Games. We assign each category a minimum and maximum number. As we are starting, we use 1 and 2

1 +---------+
  | (1)Game |
2 +---------+

Simple enough. Now, lets add the first child, the (2)Windows. Now, as this is a child of (1)Game, then its minimum and maximum must be inside of the min and max for its parent. So, we simply change the maximum of (1)Game to 4, and set the min of (2)Windows to be 2 and the max to be 3

1  +----------+
   |          |
2  |          2------------+
   | (1)Games | (2)Windows |
3  |          3------------+
   |          |
4  +----------+

Now, lets add  in category 3 and 4, in each case, we insert the categories with min and max values that are inside of the parents, and not overlapping with any other children of that parent. Like so.

1  1----------+
   |          |
2  |          2------------+
   |          | (2)Windows |
3  |          3------------+
   |          |
4  |          4------------+
   | (1)Games | (3)Linux   |
5  |          5------------+
   |          |
6  |          6------------+
   |          | (4)Mac     |
7  |          7------------+
   |          |
8  8----------+

Simple enough, but what does that get us? Not a lot yet. Lets go a bit further down the tree, and add some children to the Linux category, and see what happens.

So, using the same rule, any child we add  must have a min and max inside its parents, and its parent must expand to accommodate it. Lets add (5)strategy in as a child of Linux.

1  1----------+
   |          |
2  |          2------------+
   |          | (2)Windows |
3  |          3------------+
   |          |
4  |          4------------+
   |          |            |
5  |          |            5-------------+
   | (1)Games | (3)Linux   | (5)Strategy |
6  |          |            6-------------+
   |          |            |
7  |          7------------+
   |          |
8  |          8------------+
   |          | (4)Mac     |
9  |          9------------+
   |          |
10 10---------+

Now, by adding the child to Linux, you have to change lots of mins and maxes. It looks like it would be a real pain to keep track of, but simply, you can just go through a flat list of all categories, and add 2 to each min and max that are greater than or equal to the old maximum of the parent. So in this case, the Linux category min/max were previously 4 and 5, so anything higher than a 4, add 2 to it, and then you have 2 spare numbers for the min/max for the new category. Simple enough. Now we can add in the final categories, and the tree looks like it did in the example further up, but with each category given a min and max number

 1 1----------+
   |          |
 2 |          2------------+
   |          | (2)Windows |
 3 |          3------------+
   |          |
 4 |          4------------+
   |          |            |
 5 |          |            5-----------------+
   |          |            | (5)Strategy     |
 6 |          |            6-----------------+
   |          |            |
 7 |          |            7-----------------+
   |          |            |                 |
 8 |          |            |                 8-----------+
   |          | (3)Linux   |                 | (7)Action |
 9 | (1)Games |            | (6)First Person 9-----------+
   |          |            |                 |
10 |          |            |                 10----------+
   |          |            |                 | (8)RPG    |
11 |          |            |                 11----------+
   |          |            |                 |
12 |          |            12----------------+
   |          |            |
13 |          13-----------+
   |          |
14 |          14-----------+
   |          | (4)Mac     |
15 |          15-----------+
   |          |
16 16---------+

OK, so there we have it, we have a tree, showing a hierarchy, and all of the categories have numbers for a min and a max value. All numbers are unique, and all numbers belonging to a child are inside the scope of their parents. Great, but how does this help us?

Take a look. If you want a list of all categories that are children of Linux (min=4, max=13) then simply, get a list of all categories whose min is more than 4 and whose max is less than 13

Simple. In a single pass through a flat list of categories, you obtain a full list of all children. No matter how deep the tree system goes, as long as you keep to the rules of calculating the min and max values, this will always work.

It also works the other way. If say, you want a list of all parents of the RPG category (min=10,max=11), simply look for all categories whose min is less than 10 and whose max is more than 11, and you get the entire ancestry of that category. All in one pass.

This all comes in especially useful if you combine it with SQL. Complete tree segments can be obtained from a single efficient SQL query. Queries are easy to generate that can find, using the above tree as an example, all Linux games of any category!

I hope some people found this useful, and I hope that some of you had the reaction I had when someone first introduced this to me several years ago – ‘Thats very cool!’

  • Share/Bookmark

Enabling online gaming

February 18th, 2009 by Eskild Hustvedt (Community Manager and Junior Developer)

We recently released PenguinPlay, a multi player matchmaking service for Linux. Part of our motivation to do this was the fact that it could, at times, be very hard to actually find someone to play online Linux games with, our community not being as large as the gaming communities on other platforms, as well as the fact that none of the other matchmaking services had proper Linux support. One of the main reasons for this, of course, is the fact that most games aren’t compatible across platforms, usually because they use a proprietary network layer that only works on one platform. PenguinPlay on the other hand is built around the LGP networking library, Grapple, which both makes support for PenguinPlay quite easy to implement, as well as giving support for platform-independent multiplayer. The service itself had been in the making for quite some time before its recent release.

Although it still is relatively new, there’s already quite a few nifty features available, such as in-game lobby, live information about ongoing games on the web site, as well as highscores for all games. Sadly though it can still at times be somewhat hard to find someone to play with, which is why we added a new feature to PenguinPlay this week, namely e-mail notifications. This lets you subscribe to notifications for games, then PenguinPlay sends you an e-mail when a multiplayer game that you can join is started. In order to enable this feature you need only log in to your PenguinPlay account, edit your account settings and then select that you wish to edit notification settings. From there you can subscribe and unsubscribe to new game notifications for the various games available on PenguinPlay.

To compliment the notification service and the on-site forums we have also started an IRC channel where PenguinPlay games can chat and schedule games in. Join #PenguinPlay on the irc.freenode.net IRC network.

One of the primary things that separates PenguinPlay from the many others similar services out there (apart from the obvious support for Linux) is that it is available, very cheaply, for developers of Free/Open source games. The Grapple library is already open, so they need only pay a (nominal) fee for hosting services, and then we take care of the rest (no proprietary code needed). The library itself is multi-platform and runs on Linux, BSD, MacOS X and Windows. Our goal is that a multi-platform online gaming community is built up around it, in particular, one where Linux gamers are real full-time members of the community and treated at least as well as gamers from other platforms.

As of this writing, the games that are available are only Linux versions, and only commercial games. There is no technical reason why the developers of the games for other platforms shouldn’t be able to patch their games to work with PenguinPlay. The games that are available are currently available for online play are Ballistics and Knights & Merchants both of which needs to be patched to the latest version, as well as high score support for Jets’n'Guns, which was the first LGP game to ship with PenguinPlay support out-of-the-box, and Candy Cruncher (which also requires a patch). The upcoming LGP game Sacred: Gold will also ship with PenguinPlay support out-of-the-box, enabling Linux gamers to adventure together, and our beta team has already done so. I for one can’t wait to quest along with fellow Linux gamers.

We are hoping that the service improves the multiplayer experience for Linux gamers, making it easier for the gamers to find people to play with, and games developers to have full multi-platform multiplayer support in their games. Keep checking this blog and the PenguinPlay website for news about more upcoming PenguinPlay features and games.

If you have any input, suggestions or questions for me, feel free to ask them here in the comments, on IRC, or via e-mail (to eskild at the domain linuxgamepublishing dot com).

  • Share/Bookmark

The LGP community

February 13th, 2009 by Eskild Hustvedt (Community Manager and Junior Developer)

Greetings! My name is Eskild Hustvedt (aka. Zero_Dogg), and I’m a junior developer and community manager at Linux Game Publishing. This is the first of hopefully many (community-related or otherwise) blog posts from me. This time I’ll be writing a bit about the LGP community.

One of the great strengths of Linux in general is the strong communites that has been built up around it. Linux gaming is no exception, and we at LGP are very proud of the community that surrounds us, not merely because it is the community that pays our bills, but also because it is very friendly and helpful, and as such a great motivation while we are working on bringing great commercial games to Linux.

One of our most active community communication channels is IRC. We have one rather active IRC channel on the irc.freenode.net IRC network, namely #LGP, our general chat channel. Recently we have also started a channel for our new PenguinPlay games matchmaking service on the same network called (quite obviously) #PenguinPlay. The latter is still in its infancy, and as such not as active as the primary #LGP channel. In both of them you will be able to communicate with other members of the community, as well as numerous LGP employees. You will find our beloved dictator CEO Michael Simms (as lgp-michael), and yours truly (as Zero_Dogg) idling there pretty much 24/7, and most other LGP employees regulary (pretty much daily) stopping by, not to mention the large croud of friendly regulars that are usually more than happy to help, or just chat (about Linux games of course, though we *cough* some times tend to drift somewhat off topic). IRC is also a great way to quickly get support concerning our games (although it should be noted that it is not an official support channel). Not only is our IRC community helpful in answering questions about our games, but it also deserves our gratitude for assisting us. Just this week we recieved numerous reports about our recent Candy Cruncher patch breaking sound for many players, as a result of this we were quickly able to diagnose and subsequently issue another patch that fixed the issue.

Another good example as to how our community can affect our decisions is how we treated the community reactions to our announcement of the addition of DRM to our new games. The community had strong feelings and opinions concerning the subject (and rightfully so), but we felt that at this point adding a form of DRM was something we had to do. What followed was a storm of feedback from our community, which we greatly appreciated. Because of you we made large changes to the DRM scheme, in order to ensure that the rightful owners of our games would not be blocked from using their own game, even during very long periods of no internet connection. The input was received primarily via e-mail and on our public IRC channels (but also partly through comments on articles concerning the subject).

In the end, the community and our love for gaming in general, and on Linux in particular, is the reason we keep doing what we do. Without all of you, there would not be any LGP.

If you have any input, suggestions or questions for me, feel free to ask them here in the comments, on IRC, or via e-mail (to eskild at the domain linuxgamepublishing dot com).

  • Share/Bookmark

64 bit games on the horizon, but not here yet.

February 11th, 2009 by Michael Simms (CEO and head of Development)

As modern machines are moving more and more towards 64 bit, we are receiving a growing number of requests for 64 bit binaries of our games. This semi-technical article will illustrate how we do plan to create 64 bit binaries in the end, and to give you an overview as to why we haven’t done so before.

The first stumbling block to 64 bit, is the build environment. The build environment is absolutely essential, and it is what allows us to create a game that works on all Linux distros. Over many years, we have tuned our 32 bit system to find a set of libraries and build tools that are cross-distro compatible with pretty much any Linux distro out there. The discussion of this in detail will be for another day, but finding a comparable cross-distro environment for 64 bit is the work of many months of solid research, costing tens of thousands of pounds.

The second problem is the code itself. Only in the last 12 months or so have a few games started to come out for Windows with 64 and 32 bit versions. Most games, even today, are 32 bit only. This means that assumptions have been made about the sizes of pointers, and sizes of various data types, that do not hold true for 64 bit. The biggest issue there is the size of pointers. Various aspects of the game rely on a pointer being 4 bytes in size, and suddenly throwing an 8 byte pointer into the mix is guaranteed to cause problems. This is something that, depending on the way the program is written, is incredibly hard to work around.

Data types such as long int, are easier to work around. Simply replacing all long int variables to be an int32_t will solve that issue with no problem – unless of course the game uses pointer arithmetic. I have never seen a game that does not use pointer arithmetic. This means we cannot make blanket substitutions, every variable in the whole program, sometimes millions of lines, tens of thousands of variables, needs to be examined in depth.

Once we have all of these factors addressed, we will be in a position to produce a 64 bit version of a game. An estimated 3-6 months advance work making a build environment template, probably 25% extra development time increase for the project, and we end up with a speed increase that is not large enough to warrant the extra development time. Our research shows that 64 bit versions of games would run around 5% faster than 32 bit, and you would get more of a performance increase by closing down your web browser when playing, than by running 64 bit.

With the impatience our customers have for new games, we have for now made the call to bring the game to release earlier, than to have a 64 bit version. As and when we license a game that is available as source for 64 and 32 bit, we will certainly spend the time doing the work to build an appropriate build environment, so that we can take advantage of the source, but the costs and risks of doing this to an entire source base that is not designed for it are too high to justify.

  • Share/Bookmark

Our new way to meet the LGPL

February 8th, 2009 by Michael Simms (CEO and head of Development)

Hi again, and welcome to our next technical article. This is a mix of technical and legal, but as I know many of us in the open source community are very serious about the licences we work under, I thought you would like a little background reading to lead you up to a really neat and little-known feature of the GNU linker (ld) that we have just adopted.

For years, LGP has been working with libraries such as SDL, ffmpeg, and others that are licensed under the LGPL (GNU Lesser General Public License). Without these invaluable tools from the open source community, LGP would not exist, and nor would hundreds of open source projects.

The LGPL states that an application that links against an LGPL library is not bound by the LGPL itself, but then goes on to qualify this, and make exceptions, and even itself states that the boundaries between what counts as simply linking against a library, and what counts as a derivative work, are ‘not precisely defined by law’.

The problem we have always faced is finding a way to make sure the game is portable. To do this you MUST make sure that you are using a known version of as many libraries as you possibly can. There is no point in exhaustively testing a game against SDL 1.2.12 when next week SDL 1.2.13 comes out, changes a few of our assumptions, and means the game crashes. Multiply the problem by the number of versions a library has, multiplied by the number of libraries a game links against, and you can see why this is a big problem. And so, we like to make sure we build the game, test the game, and run the game, all against exactly the same libraries as the end user will use, in as many cases as is possible.

Since the beginning of commercial Linux games, the common practice has been to create a release of each game such that there was a static and a dynamic linked version of the game in each release. The dynamic version of the game would be completely in compliance with the word and spirit of the LGPL, using the users own system libraries, while the static linked version of the game was released because linking the libraries directly into the game ensured we knew which libraries were being used. The statically linked executable though, was really not very much in the spirit of the LGPL. We always got away with it because we included the exact same game in full LGPL compliance,and because of the wording of the LGPL, it was fairly ambiguous as to whether this was allowed. But even so, we were never happy with it. Loopholes are not something to be proud of using.

There was another method of course. The other method involved forcing the game, via the LD_LIBRARY_PATH to use libraries in a certain directory. However that had issues of its own. To do this you either have to tell the user ‘before you start your game type this long command into the commandline’ or you start the game from a shellscript. Shellscripts are all well and good, but they bring problems of their own, such as (for security) making changes to the euid, resetting values from /etc/profile, and of course, assuming that the shell in use has exactly the same syntax as the shell at the time of release. It was decided that because of this, and many other issues, starting from a shellscript was too much of a risk for portability and was ruled out.

And so, we were left with the method that has been being used for the last 12 or so years. That is until recently, when we found a nice new way to fix this problem once and for all.

Most people are probably unaware of the linker option, -rpath. Most of you don’t ever need to be. This option lets you tell an application where to look for libraries. It works just like adding a new path into the LD_LIBRARY_PATH. Great, but it doesn’t really help like that. It is set at compile time and so we would need to restrict installation to a known directory on everyone’s machine. Obviously unacceptable for most users.

And so the problem remained until one of our devteam discovered a neat little trick that isn’t even documented in the manual for the linker. You can use a special keyword $ORIGIN to say ‘relative to the actual location of the executable’. Suddenly we found we could use -rpath $ORIGIN/lib and it worked. The game was loading the correct libraries, and so was stable and portable, but was also now completely in the spirit of the LGPL as well as the letter!

For those of you a little newer to compiling under Linux, some of you may not even be aware you use the ld linker. It is done automatically by gcc for you. If you are simply using gcc in a Makefile, it is a little more difficult in syntax, but as a hint you would change an example Makefile line that started like this

gcc obj1.o obj2.o -o my_application

to be

gcc -Wl,-rpath,\$$ORIGIN/lib/ obj1.o obj2.o -o my_application

So, that’s the neat little trick I thought I’d like to share with you, maybe it will help some of you out there to organise the way your projects run, as of course it isn’t just useful for closed source, this is useful for any project that has to use a specific library version in order to work properly!

  • Share/Bookmark

Beta testing for LGP

February 3rd, 2009 by Michael Simms (CEO and head of Development)

We have announced today that we are opening the beta test for Shadowgrounds Survivor. People who want to be part of the beta test should apply at our betas website.

We always have people disappointed when they do not get accepted into our beta test, so I thought that today I would say a little about the process.

For each beta test we have up to 3,000 applicants. For each beta test we accept around 30 or 40 testers. This is already an indication that tests will be hard to get into.

When we look at who to accept into a beta test, we make a list of the targets we need to cover. This is a list of distros, processors, graphics cards, sound cards, and other things we feel will affect a game.

We then look at a list of beta testers to see who fits each target. Our list is ordered by number of ‘points’ the beta tester has. Testers that have previously tested with us before, who have done well and found problems and been helpful, will have more points. Testers that have previously been accepted and who just treated the beta test as a way to play the game for free for a while, will have points deducted and will most likely never be accepted again. People who apply for tests, but who aren’t accepted, will be given a small number of points for enthusiasm, and after a number of applications will likely be accepted. However beware, if you just apply for everything, and then get accepted into a game you don’t test, you will blow your score for future betas.

So, when we have found a number of beta testers to cover each target area, we then look at other beta testers with high scores who will be accepted for ‘general good tester record’. We then accept a number of new testers who have never tested before, but who have shown enthusiasm for getting into a test. We finally then accept a couple of testers who have never applied before.

Finally, we allow people to short-cut the beta test application system and send us their receipt for pre-ordering the game. This is partially, I will happily admit, to make people buy the game. Why shouldn’t we, after all, its our job as a publisher to sell copies of the games we publish. It is also partially to give those who are enthusiastic to beta test a chance to prove they can help. As with any other beta tester, those who use this short-cut and do not do any testing, will be less likely to be accepted into future tests.

For every test, we get emails from people who are ‘disgusted’ that we didn’t accept them. Sure, I’m sorry that we cant accept everyone, but we only have enough space to accept one in every 50 (or more) or so testers, and swearing at us really won’t make us change our mind. ‘Wow, you swore at us, that’s great, we’d LOVE you to test for us now’…

we also get emails from people who are ‘better than other beta testers so we should accept them’. The testers we accept have usually already proven themselves, or have shown enough enthusiasm for testing that we accept them based on that. Just because you have a whole lab of computers to test on, doesn’t mean you will be a good tester, and certainly doesn’t make you better than a tester who has a single computer, but who reports many bugs on each beta they are part of. If you feel you can help, keep on applying, you will get in in the end, or do what many do and pre-order, and prove how good you are! Some of our best beta testers who now get accepted into every beta test started out by pre-ordering a game.

  • Share/Bookmark

Jets’n'Guns just arrived!

January 30th, 2009 by Michael Simms (CEO and head of Development)

Well, me and one of the guys just spent some time out in the cold helping a truck driver unload boxes of Jets’n'Guns from the back of a truck. So, I guess this is the announcement to the blog that the game is in!

Jets’n'Guns is just like the old space shooters, like R-Type, that kind of thing, but with modern graphics, and a soundtrack that, well, Ive added the intro music to my playlist on my mp3 player!

We’ve also added an extra bonus over the Windows version, with PenguinPlay highscore tables. For those of you that don’t know what PenguinPlay is, it is our online game matchmaking and highscore service, designed to bring Linux gamers a little closer together.

In Jets’n'Guns you take the part of an ex war-hero with no wars left to fight. Hiring out your services for pay, you must fly your ship through over 40 levels of enemies, some in space, some around planets. Your ship is fully customisable, with dozens of weapons and upgrades. As the game progresses, a storyline unfolds, and by the end, you aren’t just a mercenary, you are saving the whole universe!

But I won’t spoil the ending for you. You’ll just have to play it to find out how it ends!

  • Share/Bookmark

The trouble with storing binary data structures

January 29th, 2009 by Michael Simms (CEO and head of Development)

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