Friday, December 3, 2010

Bash named pipes

Pipes are a unix staple. They're core to the unix philosophy of modularity. Bashes named pipes just knock this up a notch.

Lets say we have two directories that should have contain the same files, but one is on a case insensitive file system, so some files might differ in case. We could do this, using normal pipes to process the directory entries.

ls dir1 | tr "[:lower:]" "[:upper:]" | sort > dir1_contents
ls dir2 | tr "[:lower:]" "[:upper:]" | sort > dir2_contents
diff dir1_contents dir2_contents

But this is kind of hacky and creates two temporary files.

Bash named pipes lets you use the output of a pipe system in place of a filename. Its almost like the pipes were written into temporary files and the files deleted afterwards, but no disk space is consumed by the files.

diff <( ls dir1 | tr "[:lower:]" "[:upper:]" | sort ) <( ls dir2 | tr "[:lower:]" "[:upper:]" | sort )

Much neater.

Mind you I haven't used these often, but if you know they exist they can make some painful multistep processes much simpler.


Monday, September 27, 2010

Abusing shared_ptr custom deleters to store data.

So you can associate a custom deleter with a boost::shared_ptr object. That deleter will get called when the last reference to the underlying object is destroyed and is responsible for cleaning up the object. You might use this to use a boost::shared_ptr to hold a mysql handle.
boost::shared_ptr mysql( mysq_init(), mysql_close );

(or something like that .. can't remember the exact function names)
But you can also "hide" objects with the shared_ptr that will get destroyed with it... I'm not sure quite why you might want to do it, but someone was asking how to do somethign similar in StackOverflow.

Here's how you do it.


Friday, September 24, 2010

Graphing include dependencies

Sometimes it's nice to get a higher level view of what files are including which other files.
This becomes tricky as your projects get larger .. So I wrote a little python script to help me visualise it...
You can find the script here

It takes a list of files to analyse on stdin and produces a dot graph file that you can render using the graphviz tools (I find dot and neato to be the most useful for this task)

Heres an example of what I get when I run it over a filtered subset of one of my projects:
(Original is a PDF so its easy to zoom in to see filenames, but you only get a PNG to protect the innocent)


Thursday, September 9, 2010

Fixing whitespace issues with git rebase

We're using a rebase and merge style approach for getting topic branches into our master branch.

Typical usage looks like this:
# Get the topic branch
git checkout topicbranch
# Sit it ontop of master
git rebase master
# Clean up all the commits so its nice and tidy
git rebase -i master
git checkout master
git merge topicbranch
Now if you add a --whitespace=fix to the first rebase stage, git will clean up all the odd whitespace at end of line stuff that git complains about and that editors can leave in there accidentally.

However this only works if your branch is not already branched off master. If your branch already contains the master head you'll just get the message:
Current branch topicbranch is up to date.

It turns out its easy to make the rebase happen:
git rebase -f master --whitespace=fix

Friday, June 25, 2010

Smashing the Stack: Storing per class information

This stack overflow question demonstrated some issues with storing per class metadata in templated info classes. In particular it boils down to something like this:

Original Code


template<typename T>
struct MetaData
{
  static std::string data;
};
With thre requirement that you add something like this to a source file for every class you require metadata for. Failing to do this will generate a link time error.
std::string MetaData<int>::data;
std::string MetaData<MyClass>::data;
The original code using this kind of method would look something like this:
template <class T>
static void OpenLib(lua_State* L)
{
  if (MetaData<T>::myTable && MetaData<T>::myTableName)
  {
    luaL_openlib(L, MetaData<T>::myTableName, MetaData<T>::myTable, 0);
  }
}

Template sepcialisation

Personally I don't like link time errors and prefer compile time errors, so we could try using template specialisation to get a similar result.
template<typename T>
struct MetaData
{
};
template<>
struct MetaData<int>
{   static std::string data() { return "foo"; }
}
template<>
struct MetaData<int>
{   static std::string data() { return "bar"; }
}
This time you'll get a compile time failure if you fail to define the MetaData for a class that you are using. However there's still a lot of boilerplate code, which I don't like. Secondly the values can't be changed at runtime, which was a requirement of the original post. The code would then look something like this:
template <class T>
static void OpenLib(lua_State* L)
{
  if (MetaData<T>::myTable() && MetaData<T>::myTableName())
  {
    luaL_openlib(L, MetaData<T>::myTableName(), MetaData<T>::myTable(), 0);
  }
}

Singleton

Another trick we can use to avoid needing to define static variables in a .cpp file is to use metadata that uses singleton functions for each variable. Then the function static variable is created inside the function, (on first function use I think) and lives until the end of the application.
template<typename T>
struct MetaData
{
  static std::string& data()
  {
    static std::string data_("");
    return data_;
  }
};
As we return a non-const reference we can still change the value at run-time, like this:
MetaData<int>::data() = "Omg Froobles";
However some people, (myself included) dont really like the use of singletons (or global variables) as they can make code quite hard to test. The code would then look something like this:
template <class T>
static void OpenLib(lua_State* L)
{
  if (MetaData<T>::myTable() && MetaData<T>::myTableName())
  {
    luaL_openlib(L, MetaData<T>::myTableName(), MetaData<T>::myTable(), 0);
  }
}

(Almost) Template free type map.

There's an alternative to using templates as a way into the C++ type system, and that is type_info (Well there's also polymorphism, but we'll ignore that option for now). If we go down that route we can reduce the usage of templates and global/singleton variables significantly.
struct ClassMetaData
{
  std::string data;
};

struct TypeInfoCompare
{
  bool operator()(const std::type_info* i1, const std::type_info* i2) const
  {
    return i1->before(*i2);
  }
};

std::map<const std::type_info*, ClassMetaData, TypeInfoCompare> metaDataMap;
Using this design I'd probably produce code that looks like this:
typedef std::map<const std::type_info*, ClassMetaData, TypeInfoCompare> MetaDataMap;
template<typename T>
static void OpenLib( const MetaDataMap & metadata, lua_State* L)
{
  return OpenLibCore( metadata[ &typeinfo(T) ] );
}
static void OpenLibCore( ClassMetaData & m, lua_State *L )
{
  if ( m.myTable && m.myTableName )
  {
    luaL_openlib(L, m.myTableName, m.myTable, 0);
  }
}
And while you now need to pass in an additional parameter to the OpenLib function, these functions are now easily testable. And if you really hate that additional member you can make the MetaDataMap a global variable or singleton.

Monday, March 1, 2010

float comparison and POD equality

I found an interesting discussion on why there is no default comparison operator (operator==) on PODs even though there is a default assignment (operator=). 

operator= can be trivial for PODs as byte=by-byte copy will produce an equivalent result to an element by element copy. Essentially memcpy will work as operator= for PODs. At first you might think that operator== could work the same way, lets just use memcmp.

However theres a spanner in the works - floats cause us some problems. And not in the usual "floating point comparison for numbers that are very close together not showing up as equal" - but something a little more subtle. 

For most floats the bit patterns being equal means the floats are equal and vice versa. However theres a couple of exceptions. -0.0 == 0.0 even though the bit patterns are different. Also NaN != NaN even though the bit patterns are the same.

This means that a bit by bit POD operator== can never work the same way as an element by elememt comparison when floats (or doubles) are in the mix. And that means no default operator==. A sad loss, but maybe a little more understandable to me now.

Friday, February 26, 2010

Smashing The Stack : What is a neat way of breaking out of many for loops at once?

A Problem that has been posted and reposted on StackOverflow boils down to "What is a neat way of breaking out of many for loops at once?" An ugly solution looks like this:
Context context;
bool flag = false;

for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
for (int k = 0; k < 100; k++) {
  updateContext(i,j,k,context);   if ( shouldBreak( context, i,j,k) ) {
    flag = true;
    break;
  }
}
if (flag) break;
}
if (flag) break;
}
Here we've wrapped all other data that is changing into a context object that is updated every iteration, and is tested against. So how can we make this "neat" .. here's one kind of solution.
void loopfn(Context & context)
{
  for (int i = 0; i < 100; i++) {
  for (int j = 0; j < 100; j++) {
  for (int k = 0; k < 100; k++) {
  updateContext(i,j,k,context);
  if ( shouldBreak( context, i,j,k) ) return;
  }
  }
  }
}
};

Context context;
loopfn(context);
One further step that can be helpful in further refactoring is:
class Looper
{
  Looper(Context & c) : context(c) {}
  Context context;
  bool shouldBreak(int i,int k,int k);
  void updateContext(int i,int k,int k);
  void loop()
  {
    for (int i = 0; i < 100; i++) {
    for (int j = 0; j < 100; j++) {
    for (int k = 0; k < 100; k++) {
    updateContext();
    if ( shouldBreak(i,j,k) ) return;
    }
    }
    }
  }
};

Context context;
Looper l(context);
l.loop();
IMHO this is easier to maintain than the original loop with flags and breaks. This is usually handy as we can make the updateContext and shouldBreak functions members of the Looper class. Of course in most cases this can be refactored to be even neater, depending on what your context is.

Wednesday, February 10, 2010

One aspect of game balance in Domain Of Heroes

Domain of Heroes is a strange little indie game that gets a lot of things right (in my opinion).

Its a fairly standard RPG style game. You kill monsters to get items to get more powerful to kill harder monsters. "The Grind" is central to this game. What I'm going to talk about is how its stat system works and what this means for minmaxer style players.

Items come in different rarities. Each item rarity has a different number of attribute slots. When an item is found these slots are filled with random attributes. Here's an example:

Burning Plate Glass of Snagging [unique]
(Chest) Base Defense: 40
[1] Multiplies Fire damage by 6.9%,
[2] 4.6% chance of entangling opponent,
[3] Increases MND by 5.6%,
[4] Adds 24.0 to END

In the glorious tradition of RPGs the prefix and suffix of the item are determined by the first two attributes and the colour of the item is the rarity, in this case unique. All unique items will have 4 slots

Here's the number of slots per item by rarity
common0
uncommon1
notable2
rare3
unique4
legendary5
mythical6

The enchantments come in 3 tiers.
TierAdds(+)Increases(%)
1 12.5 1.9%
2 25.0 3.8%
3 37.5 5.6%

Next players can replace attributes with attributes of their choosing, with a couple of key limitations.
The one we're interested in here is that players cant create the % increase attributes, only the + increase attributes.


This means that valuable items are the items with higher rarity with t3% or multiple t3% enchants. The non-% slots are then typically filled with t3+ enchants.


For example A player might convert the item above into something like this:

Genius Plate Glass of the Professor [unique]
(Chest) Base Defense: 40,
[1] Adds 37.5 to MND,
[2] Adds 37.5 to MND,
[3] Increases MND by 5.6%,
[4] Adds 37.5 to MND

This would be refered to as a t3% MND unique. A common question is whether a t3% MND unique is better than a no-% MND mythical item
For example
Genius Plate Glass of the Professor [unique]
(Chest) Base Defense: 40,
[1] Adds 37.5 to MND,
[2] Adds 37.5 to MND,
[3] Adds 37.5 to MND,
[4] Adds 37.5 to MND,
[5] Adds 37.5 to MND,
[6] Adds 37.5 to MND

What's interesting about this question is that "it depends"
If you already have a high base MND value you will gain more from 5.6% than the extra 75. If you have a low MND base value you will get more from the myth. We can actually work out the cross over, the maths is quite easy. However I might leave that for another post.


The interesting thing in my opinion is how the multiplicative nature of the two bonuses means that stacking too much of either one gives you a sub optimal result. i.e. +490% MND if you've only got 10 MND gives you only 59 MND, +10%MND if you have 490 MND gives you 539 MND which is better, but +250%MND with 250MND gives over 875 MND which is vastly superior. This also means that different people will value items differently resulting in a potentially "richer" system.


Wow that feels like a lot of cruft to read through to get to a relatively simple (but deep) point. I'll delve more into the maths behind this balance in another post.

Isn't sed great

Search and replace using regex in multiple files from the command line. What more could a serious coder want.
sed -i.bak 's/foo/bar/g' *.cpp



ADDITION:

I Often find I want to just replace whole words. The way you do this will depend on the version of sed you're using.

This works for me on OS X
sed -i.bak 's/[[:<:]]foo[[:>:]]/bar/g' *.cpp
While on linux you can use the slighly neater
sed -i.bak 's/\<foo\>/bar/g' *.cpp

Tuesday, January 26, 2010

Smashing The Stack (continued)

In the last post i looked at one way of handling exceptions that come out of C++ when wrapping classes to be called from C. On the upside this code looks very similar to how I'd wrap exception free code. On the downside the exception handling callbacks aren't very flexible and result in an uglier interface.

By restructuring the C interface slightly we can get what I think is a much cleaner interface.
In summary all C functions return an int indicating success/failure, this means the old return values must be passed in as a pointer. We also add a function to return the error message if the call fails. Anyway here's the new header

 1 #pragma once
 2
 3 typedef struct 
 4 {
 5   int x;
 6   int y;
 7 } CLocation;
 8
 9 typedef struct HMyMap HMyMap;
10
11 int MyMap_create( HMyMap**  );
12 void MyMap_destroy( HMyMap *h );
13
14 int MyMap_addKV( HMyMap *h, const char *k, CLocation v );
15 int MyMap_getV( HMyMap *h, const char *k, CLocation *v);
16 char* MyMap_getErrorMessage( HMyMap *h );

And heres example code using this:
#include "simpletest.h"
#include <stdio.h>
#include <string.h>
#include <assert.h>

int main()
{
  HMyMap *h;

  if( ! MyMap_create(&h) )
  {
    printf("ERROR: FAILURE TO CREATE\n");
    return 1;
  }

  CLocation loc = {2, 3};
  if( ! MyMap_addKV(h, "test", loc) )
  {
    printf("ERROR: FAILURE %s\n", MyMap_getErrorMessage(h) );
    return 1;
  }
  if( ! MyMap_addKV(h, "test", loc) )
  {
    printf("THIS SHOULD FAIL : FAILURE %s\n", MyMap_getErrorMessage(h) );
  }

  CLocation v;
  if( ! MyMap_getV(h, "test", &v) )
  {
    printf("ERROR: FAILURE %s\n", MyMap_getErrorMessage(h) );
    return 1;
  }
  printf("%s : (%d, %d)\n", "test", v.x, v.y );
  CLocation w;
  if( ! MyMap_getV(h, "monkey", &w) )
  {
    printf("THIS SHOULD FAIL: FAILURE %s\n", MyMap_getErrorMessage(h) );
  }

  MyMap_destroy(h);
  return 0;
}

And finally an extract from the implementation:
18 struct HMyMap : public MyMap
19 {
20   HMyMap() : MyMap(), error_message() {}
21   std::string error_message;
22 };
23
24 int MyMap_create( HMyMap**h )
25 {
26   *h = new HMyMap();
27   return 1;
28 }
29
30 void MyMap_destroy( HMyMap *h )
31 {
32   delete h;
33 }
34
35 int MyMap_addKV( HMyMap *h, const char *k, CLocation v )
36   try
37 {
38   h->addKV( k, pair_from_cloc(v) );
39   return 1;
40 }
41 catch( MyMap::Exception & e )
42 {
43   h->error_message = e.mesg_;
44   return 0;
45 }
46
47 int MyMap_getV( HMyMap *h, const char *k, CLocation *v)
48   try
49 {
50   *v = cloc_from_pair( h->getV(k) );
51   return 1;
52 }
53 catch( MyMap::Exception & e )
54 {
55   h->error_message = e.mesg_;
56   return 0;
57 }
58
59 char * MyMap_getErrorMessage( HMyMap * h )
60 {
61   return const_cast<char*>(h->error_message.c_str());
62 }

So not much trickier than the other implementation, and now that I've built them both I consider this way of doing the wrapping to be easier to work with.

Sorry theres not much discussion of the code this time. But hopefully it will still be helpful to someone.

Monday, January 18, 2010

Smashing The Stack

This is the first post in a "series" I'll be writing. It's primarily going to be a pointer to a post I find interesting on StackOverflow. Often this will be a post that I've answered or asked, but hey thats just my bias ;)
So this first article is about calling C++ functions and classes from C. So this solution covers the simple case. Usesr asked about how we can handle exceptions and allocating small objects on the stack rather than the heap. I'm going to show you a way that these can be addressed.
There's a few key issues.
  1. Any exception that hits the C++/C bridge will crash your application
  2. You can only catch exceptions in C++
  3. Catching _all_ exceptions by catch(...) can leave your application in an invalid/unrecoverable state. Some compilers (VC++) will allow catch(...) to catch things like segmentation faults etc. The only sane  thing to do in that case is immediately exit. 
  4. Other exception may be recoverable, and we need a way to handle this.
Here's the source of the C++ class we're going to access from C
 1 #pragma once
 2
 3 #include <iostream>
 4 #include <map>
 5
 6 class MyMap
 7 {
 8   public:
 9     struct Exception
10     {
11       explicit Exception(const std::string & mesg) : mesg_(mesg) {}
12       std::string mesg_;
13     };
14
15   void addKV( const std::string & key, const std::pair<int,int> & value );
16   std::pair<int,int> getV( const std::string & key ) const;
17   std::map<std::string,std::pair<int,int> > map_;
18 };

Heres what my C header looks like

 1 #pragma once
 2
 3 typedef struct
 4 {
 5   int x;
 6   int y;
 7 } CLocation;
 8
 9 typedef struct HMyMap HMyMap;
10
11 HMyMap* MyMap_create( void(*handler)(const char*) );
12 void MyMap_destroy( HMyMap *h );
13
14 void MyMap_addKV( HMyMap *h, const char *k, CLocation v );
15 CLocation MyMap_getV( HMyMap *h, const char *k );

And the implementation:

 1 extern "C"
 2 {
 3 #include "simpletest.h"
 4 }
 5 #include "MyClass.h"
 6
 7 std::pair<int,int> pair_from_cloc( const CLocation & loc )
 8 {
 9   return std::make_pair(loc.x,loc.y);
10 }
11
12 CLocation cloc_from_pair( const std::pair<int,int> & loc )
13 {
14   CLocation cloc = { loc.first, loc.second };
15   return cloc;
16 }
17
18 struct HMyMap : public MyMap
19 {
20   HMyMap( void(*eh)(const char*) ) : MyMap(), handler(eh) {}
21   void(*handler)(const char*);
22 };
23
24 HMyMap* MyMap_create( void(*eh)(const char*) )
25 {
26   return new HMyMap(eh);
27 }
28
29 void MyMap_destroy( HMyMap *h )
30 {
31   delete h;
32 }
33
34 void MyMap_addKV( HMyMap *h, const char *k, CLocation v )
35   try
36 {
37   h->addKV( k, pair_from_cloc(v) );
38 }
39 catch( MyMap::Exception & e )
40 {
41   if( ! h->handler ) throw;
42   h->handler( e.mesg_.c_str() );
43 }
44
45 CLocation MyMap_getV( HMyMap *h, const char *k )
46   try
47 {
48   return cloc_from_pair( h->getV(k) );
49 }
50 catch( MyMap::Exception & e )
51 {
52   if( ! h->handler ) throw;
53   h->handler( e.mesg_.c_str() );
54   return cloc_from_pair(std::make_pair<int,int>(0,0));
55 }
Things to note are exposing std::pair<int,int> as CLocation struct, (rather than opaque handle). Allowing specification of an exception handler in the HMyMap class.
I'm not 100% happy with the way the exception handling is done, and will show another option in another post.

Monday, January 11, 2010

Debugging non-xcode code in xcode

We have some C++ code that we build using makefile system. We even use this on OS X where we could build using XCode instead, but we prefer a uniformity of build methods.

Now when a nasty and hard to trace bug crops up on an OS X build box we could try to track down the bug using good old GDB. However while I feel everyone should be able to use GDB I get sick of constantly making GDB give me what info I want. XCodes built in debugger does this nicely - in fact its just a front end to GDB. The question is how do we get our non-xcode binary to be debugged under XCode.

Turns out its EASY. (Well 90% easy).

  1. Create an empty project. ( XCode > File > New Project... )
  2. Add your binary as the default executable. (XCode > Project > New Custom Executable... )


Now you should be able to run your app through the debugger. But how do you set breakpoints? You can add your source files to the project by dragging them from finder into the XCode project sidebar. Then double click the file to open it in the XCode editor, and click in the left side by the line numbers to set breakpoints.

This worked for me most of the time. However I still had some issues setting certain breakpoints. On clicking in certain files I would get the error message
"Warning - No location found for "foo.cpp:12"
The reason for this was the file was being built from a subdirectory - its real name was autogen/foo.cpp.
So to get around this we can set the breakpoint from the gdb console. (XCode > Run > Console )
Typing "break foo.cpp:12" into the console works, presumably due to the lack of quote marks around the file/line pair.