Posts Tagged ‘C’

Getting gcc to warn you when you mess up stdargs

Wednesday, January 20th, 2010

Sometimes, you may write functions in C that do things in the same way as printf, using stdargs.

An example of this would be something like this short debug function

int ptf(const char *fmt,...)
{
  va_list varlist;
  FILE *fp=fopen("/tmp/debug","a");
  va_start(varlist,fmt);
  vfprintf(fp,fmt,varlist);
  va_end(varlist);
  fclose(fp);
}

This function isn’t rocket science, it just simply appends your string into a file. It is a simple time saver utility.

However, using it can be a problem. You can do something like this

int x=1;
ptf("Error %s\n",x);

And gcc will say ’sure, no problem’.

But running the code will always crash. It tries to interpret the integer as a string.

This is the kind of thing that should be picked up on by the compiler. And in fact it can be, quite easily.

In your prototype for the function, you would have something like

extern int ptf(const char *,...);

This is pretty standard, and no surprises there. However, gcc has the capability to be given a hint as to how this function should be handled. You can instead prototype the function using

extern int ptf(const char *,...) __attribute__ ((format (printf, 1, 2)));

This tells gcc to treat the parameters 1 and 2 as the parameters to printf (which it knows how to check for errors). It will then check parameter 1 (the format string) against what is passed in starting at parameter 2 (the …). If an incorrect data type is used, this will now be detected and flagged up as a warning, in exactly the same way as an incorrect type used in a printf.

  • Share/Bookmark

argv and argc, and just how to get them

Monday, October 12th, 2009

argv and argc. They are vital parts of many programs. For the uninitiated, in many programming languages, they are the variables that hold the values typed into the commandline by the user. This article is about a particular problem we ran into trying to use them in a way that wasn’t really forseen. It really only applies to C and C++

Now most C/C++ programmers are probably thinking ‘what is so hard, you get them when you start main, right’…

int main(int argc,char **argv,char **envp)

That’s true, and in virtually all cases, you can store these values, either in a class, a global variable, a function, whatever your programming style uses. And from then on, you can simply access them from anywhere in the program. Its really simple, and something that most programmers know how to do in their sleep.

But what do you do before main happens? Or what about if you don’t have a main()

I know, you always have a main and nothing runs before it.

But that is very not true. Lets take two examples

Firstly, in C++

class gamedata
{
public:
  gamedata()
  {
    commandline=get_argv();
  }
  char **commandline;
}

static gamedata datastore;

int main(int argc,char **argv)
{
   set_argv(argv);
   ...
}

To start, this looks OK. Sure, Ive missed out a whole bunch of things, assumed what the user functions set_argv and get_argv do. But it looks fine. Until you look again. That static class instantiation will run its constructor before main runs. How on earth can you POSSIBLY get argv at this stage??

Lets look at an example in C now

If you are creating a shared object, you will very often need to initialise it to ensure that its state is known for the first call into the objects functions.

static char **commandline;

void __attribute__ ((constructor)) localinit()
{
  commandline=get_argv();
}

Again, you try this, and you get a big nothing. This function is called before main runs, before you ever have access to the values.

So, what is the answer?

The answer is, unfortunately, ugly. There is, in Linux, no good way of doing this. There are two perfectly good symbols inside libc which do the job perfectly, __libc_argv and __libc_argc, which are defined way before the program gets to any user-created code. Unfortunately they are declared private and you as a user are not permitted to see them. So, another way is needed.

We came up with two ways to make it work. Neither are portable, and one of them, while it works just fine, does make me go ewww. I’ll leave it to your imagination which one makes me go ewww the most.

char **get_argv()
{
  static char **preset_argv=NULL;

  if (!preset_argv)
  {
    FILE *fp;
    fp=fopen("/proc/self/cmdline","r");
    if (fp)
    {
      //Your implimentation to take the commandline as typed from this
      //file and turn it into argv. Its fairly basic
    }
  }
  return preset_argv;
}
char **get_argv()
{
  static char **preset_argv=NULL;

  if (!preset_argv)
  {
    extern char **environ;
    char ***argvp;
    void *p;
    asm ("mov %%esp, %0" : "=r" (p));
    argvp = p;
    while (*argvp != environ)
      argvp++;
    argvp--;
    preset_argv = *argvp;
  }
  return preset_argv;
}

So, a little explaination

The first example relies on /proc, the part of the filesystem that you can get all sorts of interesting information from. /proc/self/cmdline is always an exact duplicate of the command typed to execute the application, or the exact value passed in from the menu option you clicked to get it working. I haven’t bothered to create the bit of code to separate out the commandline parts onto their components. Partly because that code is fairly straightforwards, and partly because it is quite long and dull (remember it isn’t just a case of separating by spaces, you have to take into account things grouped in quotes, and other fun stuff). This is not portable beyond Linux, and people keep telling me that not all Linux distros have /proc either.

The second example requires a tiny bit of assembler knowledge. It is portable across most unix flavours, but I expect trying it outside of unix will cause you much pain. It relies on the fact that a unix standard is to push the argc and argv values right onto the top of the stack when a program starts. The example reads from the top of the stack until it finds the environ value (which is globally available at all times), and then reads back one value to get the pointer to argv. This way has the advantage that the values are correctly parsed for quotes and the like already. It makes the assumption that environ is the next thing on the stack after argv. I have seen many reports claiming this is always true, but I cannot find the location of an authoritative piece of documentation saying that it is specified true and will not change in future.

It isn’t often that you will need to do this. Most of the time, argv and argc are perfectly usable in the way you will probably have been using them for years. Even the examples above can be ‘worked around’ using initialisers called immediately after main() starts. But if one day, you come up against a problem where you need your argv where you usually don’t have access, I hope you find this post useful.

  • Share/Bookmark

A little-known trick with C switches

Tuesday, March 3rd, 2009

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

How to search a data tree efficiently

Monday, February 23rd, 2009

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

The trouble with storing binary data structures

Thursday, January 29th, 2009

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