3D surface using simple graphics

In yesterday’s article I wrote a simple 2D graphics library that provided lines and quadrangles as primitives. My motivation for writing it was so I could then write what I really wanted to do, which was some 3D drawing. In particular I wanted to draw a 3D surface where a function is provided that returns a Z (height) value for supplied X and Y values. I wanted to draw a ripple and view in 3D.

The first part was to create a framework that could call the function for determining Z value. I used the following prototype for my plot function.

typedef 
double
    (*PlotFunction3D)
    (
        double  X,
        double  Y
    );

This takes X and Y values between 0 and 1 and returns a Z value between 0 and 1. For my ripple function I wrote the following:

double
    RippleFunction
    (
        double  x,
        double  y
    )
{
    double pi = 3.14159265358979;
    double z;
    double dist;
    double wave;

    // Get distance of point from centre (0.5, 0.5)
    dist = sqrt( (0.5-x)*(0.5-x) + (0.5-y)*(0.5-y) );

    wave = sin( 4*(2*pi) * dist ) * 0.4;
    z = (wave / 2.0) + 0.5;

    if( dist > 0.5 ) 
    {
        z = 0.5;
    }

    return z;
}

This calculates the Z (height) value using a sine wave on the distance from the centre of the range (0.5, 0.5). The part at the end prevents the ripple continuing to the full edge and constrains it to a circle. This function is all that defines the surface, the rest of the program is generic and can draw any surface just by providing a different plot function. It is a lot of fun to experiment with different functions and see what results you can get.

By calling this function at various points over the X and Y range, a height value for a surface is found. This now needs to be displayed. To start with I wanted to draw a wire frame. By taking X and Y points at even intervals across the range 0 – 1, I calculated a matrix of Z values. To draw as a wire frame these Z values (Along with their X and Y) are used as vertices between line segments. A line segment is drawn between each set of adjacent points. However first their 3 dimensional coordinates must be converted into a 2D set for the screen.

I used a very simple method for converting the 3D points to 2D. The following code takes X,Y,Z values between 0 and 1 and returns 2D coordinates in the integer range representing pixels in the window.

SgPoint
    GetPointFrom3D
    (
        double  x,
        double  y,
        double  z
    )
{
    SgPoint point;
    double X;
    double Y;

    X = (x*0.8) + (y*0.4);
    Y = (y*0.5) + (z*0.6);

    point.X = (uint16_t) (X * (double)WINDOW_SIZE_X * 0.8);
    point.Y = WINDOW_SIZE_Y - (uint16_t) (Y * (double)WINDOW_SIZE_Y * 0.8);

    return point;
}

In my example I had a window size of 600 x 600 pixels, So the X,Y coordinate returned (SgPoint is a struct containing an x and y integer value) was in the range 0 – 599.

This is a crude 3D conversion, as it does not take perspective into consideration, nor does it allow you to change the viewing angle. This function can be replaced with a better function that would allow for these and the rest of the program could stay the same.

So now I have my matrix of vertices converted to 2D space, it is just a matter of drawing the lines

#define MESH_GRID_POINTS    50

typedef struct
{
    double mesh [MESH_GRID_POINTS+1][MESH_GRID_POINTS+1];
} MeshPoints;

void
    DrawPlotFunction3DWireMesh
    (
        PlotFunction3D  Function
    )
{
    MeshPoints* meshXCoord;
    MeshPoints* meshYCoord;
    MeshPoints* meshZCoord;
    int ix;
    int iy;

    SgPoint prevPoint;
    SgPoint point;

    meshXCoord = malloc( sizeof(MeshPoints) );
    meshYCoord = malloc( sizeof(MeshPoints) );
    meshZCoord = malloc( sizeof(MeshPoints) );

    // Calculate mesh coordinates
    CalculateMeshCoordinates( Function, meshXCoord, meshYCoord, meshZCoord );

    // Draw mesh lines along X
    for( ix=0; ix<=MESH_GRID_POINTS; ix+=1 )
    {
        for( iy=1; iy<=MESH_GRID_POINTS; iy+=1 )
        {
            // Draw line segment from previous point to this one
            prevPoint = GetPointFrom3D(
                meshXCoord->mesh[ix][iy-1],
                meshYCoord->mesh[ix][iy-1],
                meshZCoord->mesh[ix][iy-1] );
            point = GetPointFrom3D(
                meshXCoord->mesh[ix][iy],
                meshYCoord->mesh[ix][iy],
                meshZCoord->mesh[ix][iy] );

            SgDrawLine( prevPoint, point, SgRGB(0,0,0) );
        }
    }

    // Draw mesh lines along Y
    for( iy=0; iy<=MESH_GRID_POINTS; iy+=1 )
    {
        for( ix=1; ix<=MESH_GRID_POINTS; ix+=1 )
        {
            // Draw line segment from previous point to this one
            prevPoint = GetPointFrom3D(
                meshXCoord->mesh[ix-1][iy],
                meshYCoord->mesh[ix-1][iy],
                meshZCoord->mesh[ix-1][iy] );
            point = GetPointFrom3D(
                meshXCoord->mesh[ix][iy],
                meshYCoord->mesh[ix][iy],
                meshZCoord->mesh[ix][iy] );

            SgDrawLine( prevPoint, point, SgRGB(0,0,0) );
        }
    }

    free( meshXCoord );
    free( meshYCoord );
    free( meshZCoord );
}

And now the result:

ripple_wireframe.png

This looks interesting, but rather messy because its a wireframe you can see through it. I wanted to have something that looked like a surface rather than something made of chicken wire. Instead of drawing lines between the vertices I drew quadrangles between sets of 4 vertices. The quadrangles were drawn as filled white quadrangles with black edges. By drawing the quadrangles starting from the back row and working forward, the front quadrangles overwrite the ones behind. By putting a delay in the drawing loop you could watch the surface being drawing which looked rather interesting.

I changed the above routine to use the following to draw the quadrangles

    // Draw quadrangles between sets of 4 points
    for( iy=MESH_GRID_POINTS; iy>1; iy-=1 )
    {
        for( ix=1; ix<=MESH_GRID_POINTS; ix+=1 )
        {
            points[0] = GetPointFrom3D(
                meshXCoord->mesh[ix-1][iy-1],
                meshYCoord->mesh[ix-1][iy-1],
                meshZCoord->mesh[ix-1][iy-1] );
            points[1] = GetPointFrom3D(
                meshXCoord->mesh[ix][iy-1],
                meshYCoord->mesh[ix][iy-1],
                meshZCoord->mesh[ix][iy-1] );
            points[2] = GetPointFrom3D(
                meshXCoord->mesh[ix][iy],
                meshYCoord->mesh[ix][iy],
                meshZCoord->mesh[ix][iy] );
            points[3] = GetPointFrom3D(
                meshXCoord->mesh[ix-1][iy],
                meshYCoord->mesh[ix-1][iy],
                meshZCoord->mesh[ix-1][iy] );

            SgFillQuadrangle(
                points[0], points[1], points[2], points[3],
                SgRGB(255,255,255) );
            SgDrawQuadrangle(
                points[0], points[1], points[2], points[3],
                SgRGB(0,0,0) );
        }
    }

The result looks much better than before:
ripple_surface.pngBy having smaller quadrangles a smoother effect is given, but if they are too small then the the lines get drawn too close or on top of each other and you can’t make out a shape. By getting rid of the edges and instead using shading it is possible to use much smaller quadrangles, as long as the shading makes them different colours, otherwise it will be a solid colour and no shape will be seen.

Ideally the shading would be based on some lighting effect using the angle of the quadrangles to the viewer. However I found I got quite reasonable effect just by using the Z value to determine the shading colour for each quadrangle.

By changing the SgFillQuadrant line with

colour = SgRGB(50+(double)meshZCoord->mesh[ix][iy]*255,0,0);
SgFillQuadrangle( points[0], points[1], points[2], points[3], colour );

and removing the SgDrawQuadrangle the surface could be quite nicely rendered using a much smaller quadrangles. I increased the number from 50 per row to 500.

The now for the final result:

ripple_solid.png

Finally, if you would like the source code to play around with it is available here

3dSurface.zip – Contains source code for the above examples along with LibSimpleGraphics (0.1.0 non stable version). As always this is free and unencumbered software released into the public domain.

I am planning on finishing the LibSimpleGraphics library sometime soon, at which point I’ll put it on GitHub.

Advertisements

Simple Graphics

SimpleGraphics.zip – Public domain C source code for SimpleGraphics library.

When I first started programming in DOS, the languages I used (Modula-2, and C) had basic graphics capabilities. My first C compiler was Microsoft Quick C, it had a graphics library “graph.h”. This provided a few basic primitives for drawing and changing the screen mode into graphics mode. As DOS was a single threaded operating system things were pretty easy. In your main function you could set the video mode to graphics and then draw some shapes with a few lines of code. There were no event loops and callbacks to worry about, and the graphics primitives were very simple.

With Windows (and other modern OSes) things become more difficult and easier at the same time. Doing complex things is easier because there are far more capabilities provided by the system. On the other hand however doing simple things takes longer to setup. With Quick C I could set video mode with one call and then draw a line with another call and my simple program was done. To write a Windows program that just draws one line takes a lot more setup.

I enjoyed playing around with the graphics functions back in the DOS days, and I sometimes feel nostalgic and want to relive some of those moments. I had a look around on the Internet for a very basic graphic library that was cross platform and did not require many dependencies. I wanted to be able to write a simple program that drew shapes with only a few lines of code. Unfortunately I could not find what I was looking for on the Internet. Typically the libraries out there are large and can do all sorts of fancy things. Also I did not find any that had a license I like (I like Public Domain). So I set about writing my own one.

I had the following goals for the library

  1. Must be contained within one single C file and one corresponding H file
  2. Must not required extra modules that do not come standard with a system
  3. Must work for Windows, OSX, and Linux
  4. Needs to provide basic drawing primitives: Lines, simple polygons both filled and non-filled.
  5. Public Domain!

Point 5 is pretty easy, I wrote it so I can do what I want with it and I only like public domain.

Drawing graphics in any system is not my speciality, in fact I have never done it in Windows nor OSX nor Linux before! For Windows I used GDI to do the drawing. I have written Win32 GUI apps before so am familiar with the windows message loop. I found OSX to be difficult because I wanted to write it only using C, and OSX likes to use Objective C as its main interfaces. However, OSX comes with OpenGL and GLUT standard, these have C interfaces. So I wrote the OSX version using OpenGL which I have never used before. I choose to use OpenGL for Linux too because I didn’t want to have to do a third implementation.

OSX has a limitation I found out which is the graphics calls all have to come from the main thread. This messed up my initial implementation design. I wanted the graphics library to create a thread to perform all the graphics functions in the background. So I redesigned it so that instead the main “run” function creates a thread for the main application to continue its work in, and it takes over the main thread. Its not as I would prefer it, and unnecessary for Windows, but I wanted it to be consistent across platforms.

I am quite pleased with the end result, not that it quite is an end result yet. It has been a lot of fun writing it, but the main reason I did it is because of the next thing I want to work on which needs this as base. I am releasing the source code of the library, but with a warning that it should not be consider complete or even stable. As I use it more I will fix it up more, but right now it works for the examples, but it has not been tested particularly well. It doesn’t really handle the window being closed particular well for example.

The following code is an example program which shows how simple it is to use.

////////////////////////////////////////////////////////////////////////////////
//  SimpleGraphicsTest
//
//  Test program for SimpleGraphics
//
//  This is free and unencumbered software released into the public domain
//  July 2013 waterjuice.org
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
//  IMPORTS
////////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include "LibSimpleGraphics.h"

////////////////////////////////////////////////////////////////////////////////
//  FUNCTIONS
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
//  GraphicsMain
//
//  Graphics function
////////////////////////////////////////////////////////////////////////////////
void
    GraphicsMain
    (
        void*   Unused
    )
{
    char buffer [100];
    char* ptr;
    (void) Unused;

    SgFillRectangle( SgXY(100,100), SgXY(200, 200), SgRGB(250, 200, 0) );
    SgDrawRectangle( SgXY(100,100), SgXY(200, 200), SgRGB(0, 0, 0) );

    SgFillRectangle( SgXY(130, 130), SgXY(135, 135), SgRGB(100, 100, 240) );
    SgDrawRectangle( SgXY(130, 130), SgXY(135, 135), SgRGB(0, 0, 0) );

    SgFillRectangle( SgXY(165, 130), SgXY(170, 135), SgRGB(100, 100, 240) );
    SgDrawRectangle( SgXY(165, 130), SgXY(170, 135), SgRGB(0, 0, 0) );

    SgDrawLine( SgXY(120, 160), SgXY(130, 170), SgRGB(0, 0, 0) );
    SgDrawLine( SgXY(130, 170), SgXY(170, 170), SgRGB(0, 0, 0) );
    SgDrawLine( SgXY(170, 170), SgXY(180, 160), SgRGB(0, 0, 0) );

    // Wait for user to press enter before returning and closing window
    ptr = fgets( buffer, sizeof(buffer), stdin );
    (void)ptr;
}

////////////////////////////////////////////////////////////////////////////////
//  main
//
//  Entry point
////////////////////////////////////////////////////////////////////////////////
int
    main
    (
        void
    )
{
    SimpleGraphicsRun( 300, 300, "Hello World", GraphicsMain, 0 );

    return 0;
}

The function SimpleGraphicsRun needs to be run from the main thread (because of OSX requirements). The first 2 parameters are the window size, the third is the window title, the fourth is the function where execution will continue, the final parameter is a context pointer that is passed to the function specified before. SimpleGraphicsRun will create the window and create a new thread which is passed to the specified function. When that function returns the window will be closed.

The results of the above example are:

Example1_Windows-280x300.png
Windows

Example1_OSX-281x300.png

OSX

Example1_Linux-275x300.png

Linux (Ubuntu)

The results look the same in all three platforms. Goal achieved!

A fancier example:

example2

With this example I put delays into the drawing so that it looked more interesting.

SimpleGraphics.zip – This has the C source code for the SimpleGraphics library and the example code for the above two examples. SimpleGraphics is a cross platform very basic graphics library using GDI and OpenGL. The zip file also contains compiled binaries for Windows, OSX, and Linux. This is free and unencumbered software released into the public domain.

Be careful using MOD with random numbers

The C function rand is terrible source of random numbers for almost any application, just don’t use it ever. I’m particular fond of RC4 as a source as it is easy to implement and takes very little code. A simple method of generating random numbers with RC4 is to first gather some entropy values. These are values that should be different each time you gather them, and between computers. The nice property about entropy is that it only increases. So as long as you mix in some good high entropy values you can’t “dilute” it by mixing in low entropy ones (unless you do something stupid with the way you mix them). If you have less than 256 bytes of entropy values and you want to keep code size down to a minimum then you can feed those values in as the key to the RC4 stream. However it is better and more flexible to use a hash function on the entropy values and use the resulting hash as the key to the RC4 stream. High precision timers are a good source of entropy, as are various input sources such as mouse position, memory usage, process lists etc. Just keep on feeding more entropy values into the hash function. As long as you have some pretty good values in there you should be okay. For extra points run the hash function multiple times before using the final value as the key (ie hash the hash and repeat). This makes it much more difficult for someone to determine the initial state of the RC4 stream.

Now you have an RC4 stream that has been keyed by a random value. Remember to throw away the first 256 bytes and now you have a very good source of random bytes. RC4 produces one byte per iteration. This makes it very easy to get random values of bytes, or larger words. If you want a 32 bit random number, just output four bytes, you don’t even have to worry about endianness.

Sometimes, however, you need a range of random values that is not a multiple of bytes. If for example you need random numbers in the range 0-31, this is easily produced. For each value take an output byte from RC4 and then chop off the top 3 bits. This can be easily done with an AND operation (with value 0x1f), or alternatively a MOD 32 operation.

newValue = randValue & 0x1f;
newValue = randValue % 32;

The new value is now a random value in the range 0-31 and still has a nice flat distribution. This is because each bit in the RC4 stream has a random distribution and we can take any 5 bits out of the 8 bit output. Another (more complicated) method would be to treat the RC4 as a bitstream and take 5 bits at a time. This requires more both programatically and computationally and provides no advantage, its not as if you are “wasting” the 3 bits produced by the first method and this is more efficient!.

While in the above example using MOD is equivalent to using the AND function, it can give the wrong impression that you can use the MOD operation more flexibly to get ranges that are not a whole number of bits. For example if you want the range of values to be 0-29, it looks like this could easily be produced by using the MOD function with a value 30. Don’t do this, not ever. The problem is that the MOD function is a mapping of the 256 values into 30 values. 256 does not evenly divide into 30.

The following original 8 bit values become a 0 when MOD 30 is applied: 0, 30, 60, 90, 120, 150, 180, 210, 240. That is 9 original values map to a 0. Similarly there are 9 values that map to 1 (1, 31, 61, 91, 121, 151, 181, 211, 241). So far so good, but look what happens for the values that map to 16: 16, 46, 76, 106, 136, 166, 196, 226. This is only 8 values. So in the final output the values from 0-15 have 9 original input values, whereas the values 16-29 have 8 original input values. This is not a flat distribution, instead of each value 0-29 having a probability for selection of 3.3333%, half of them have a probability of 3.5156% and the other half have a lower probability of 3.125%. This is bad for any application, and tragic for encryption.

There is fortunately a very simple solution which will produce a flat distribution of any desired range. First truncate the value to the next whole number of bits for the range wanted. In the case of the range 0-29 this is 32 (5 bits). If the value is larger than 8 bits, then produce larger values by outputting multiple bytes at a time, filling the word, and then mask the required bits. Next check to see if the value is within the desired range (eg 0-29). If it is then output it, if it is not, then throw it away and repeat the process until one is found within the range. This will produce a flat distribution of values. The function will take a variable amount of time to process as it may have to repeat several times before it gets a value within the range, however because we have truncated the bits to start with, there will always be more than a 50% chance of a value being in the range desired on each try, so it shouldn’t have to repeat much. You could skip the first step, but then you would be throwing away a lot more values and therefore repeating a lot more, but the output will still be just as good.

Coins

I recently decided to collect coins. In particular I want to collect one of every type of circulated $1 Australian coin. According to the Royal Australian Mint, there are 17 commemorative $1 coin designs in circulation, and 15 different years for the standard “kangaroos” design. So a complete set of one of each would make 32 coins. I later discovered there is an error on the RAM website and there is in fact no 1992 standard $1 coin in circulation. I am not counting all the special non circulated coins as they make dozens of designs each year, I wanted ones that could be collected just from regular change.

Getting the first few coins is easy as there is a high chance that you’ll get a coin that you haven’t already got. Getting that last coin of course will be the hardest as there is much more chance that any subsequent coin you get will be one of the other 30 already acquired. I was curious about the probability of getting the coins. Unfortunately it has been too many years since I studied maths and I couldn’t come up with the appropriate equations. Instead I decided to work it out by brute force, using the computer as a handy calculator.

For my initial trial I assumed that there was an equal distribution of coins of each design, and that there were 32. I wrote a program that just randomly picked numbers between 0 and 31 and placed them in “buckets”. Each time it added a coin to a previously empty bucket it would print out the number of coins it had selected up until that point.

I ran this program a few times and gave some good results, but of course it was random trials. I wanted to get the statistical probabilities of coins required to complete the set, so I adapted the program to run multiple trials. Half a million trials in fact. It calculated the mean and standard deviation for the number of coins required to fill n buckets. The random number generator I used was an RC4 stream which produces good statistical random. The results it printed out are:

1 after 1.0 coins  (sd: 0.0)
2 after 2.0 coins  (sd: 0.2)
3 after 3.1 coins  (sd: 0.3)
4 after 4.2 coins  (sd: 0.5)
5 after 5.3 coins  (sd: 0.6)
6 after 6.5 coins  (sd: 0.8)
7 after 7.8 coins  (sd: 0.9)
8 after 9.0 coins  (sd: 1.1)
9 after 10.4 coins  (sd: 1.3)
10 after 11.8 coins  (sd: 1.5)
11 after 13.2 coins  (sd: 1.7)
12 after 14.7 coins  (sd: 1.9)
13 after 16.3 coins  (sd: 2.2)
14 after 18.0 coins  (sd: 2.4)
15 after 19.8 coins  (sd: 2.7)
16 after 21.7 coins  (sd: 3.0)
17 after 23.7 coins  (sd: 3.3)
18 after 25.8 coins  (sd: 3.6)
19 after 28.1 coins  (sd: 4.0)
20 after 30.6 coins  (sd: 4.4)
21 after 33.2 coins  (sd: 4.9)
22 after 36.1 coins  (sd: 5.5)
23 after 39.3 coins  (sd: 6.1)
24 after 42.9 coins  (sd: 6.8)
25 after 46.9 coins  (sd: 7.6)
26 after 51.5 coins  (sd: 8.6)
27 after 56.8 coins  (sd: 9.9)
28 after 63.2 coins  (sd: 11.5)
29 after 71.2 coins  (sd: 13.7)
30 after 81.9 coins  (sd: 17.0)
31 after 97.9 coins  (sd: 23.0)
32 after 129.9 coins  (sd: 39.0)

This table shows that if you have a even distribution of 32 types of coins, then the mean number of coins required to collect is about 130. This means there is a 50% chance of getting a complete set from 130 coins. Using the standard deviation we can make some more predictions. Using the old 65-95-99.7 rule from statistics we can say that there is a 95% chance that a complete set will be found between 52 and 208 coins. Or another way of looking at it is that if you collect 208 coins there is only 2.5% chance of not getting a complete set.

I got a bag of 20 $1 coins from the bank, it had 15 unique coins in it which was bang on for the stats as shown in the table. However the coins are not uniformly distributed. The first $1 coin minted was in 1984 and 186.3 million were produced. This actually represents slightly over 1 in 5 of all $1 coins put into circulation. I also learnt that there are in fact only 31 coins. The number of coins produced with each design varies greatly. The rarest is a 2003 coin where only 4.1 million were made. I’m going to update the program to use the proportions of coins in circulation for a more accurate estimation. Although this reminded me of an interesting thing about distribution of random numbers which I want to talk about in the next article.

As of now I have 24 of the 31 coins, so 7 more to go. It also reminds me of the proof of work concept. Just as the number of first bits being zero increases the number of trials required to find one by chance, the same applies with the coins. Getting the first fire coins are easy, but getting the 31st one will take the most work. Like the proof of work scheme, it is easy for someone to verify that you have a complete set compared to the work required to acquire the set in the first place.

I haven’t made the modifications to do the correct proportions yet, but here is the source code of the current version. I’m not going to bother putting up binaries for this, as it basically prints an almost static table. But in case anyone is interested here it is. Note it links in with LibMd5 and LibRc4 from previous projects.

//////////////////////////////////////////////////////////////////////////////////
//  CoinProb
//
//  Program to attempt to show odds of getting a complete set of 32 unique coins.
//  This is free and unencumbered software released into the public domain
//  June 2013 waterjuice.org
//////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////
//  IMPORTS
//////////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <sys/timeb.h>
#include <math.h>
#include <memory.h>
#include "LibRc4.h"
#include "LibMd5.h"

//////////////////////////////////////////////////////////////////////////////////
//  CONSTANTS
//////////////////////////////////////////////////////////////////////////////////

#define COIN_TYPES      32
#define NUM_ITERATIONS  500000

//////////////////////////////////////////////////////////////////////////////////
//  TYPES
//////////////////////////////////////////////////////////////////////////////////
typedef struct
{
    uint64_t        ReachedAfterThisManyCoins [COIN_TYPES];
} StatSet;

//////////////////////////////////////////////////////////////////////////////////
//  FUNCTIONS
//////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////
//  SeedStreamWithRandom
//
//  Initialises an RC4 stream with a random key
//////////////////////////////////////////////////////////////////////////////////
static
void
    SeedStreamWithRandom
    (
        Rc4Context*         Context,
        uint8_t             ThreadNum
    )
{
    struct
    {
        uint8_t             threadNum;
        struct timeb        time;
        void*               address;
    } seedValues;
    MD5_HASH                hash;
    Md5Context              md5Context;

    seedValues.threadNum = ThreadNum;
    ftime( &seedValues.time );
    seedValues.address = Context;

    Md5Initialise( &md5Context );
    Md5Update( &md5Context, &seedValues, sizeof(seedValues) );
    Md5Finalise( &md5Context, &hash );

    Rc4Initialise( Context, &hash, sizeof(hash), 0 );
}

//////////////////////////////////////////////////////////////////////////////////
//  AcquireEntireSet
//
//  Gets an entire set of coins.
//////////////////////////////////////////////////////////////////////////////////
static
void
    AcquireEntireSet
    (
        Rc4Context*      RandContext,
        StatSet*         Statistics
    )
{
    int         totalCoins = 0;
    int         uniqueCoins = 0;
    uint32_t    value;
    int         sets [COIN_TYPES] = {0};

    memset( Statistics, 0, sizeof(StatSet) );

    while( uniqueCoins < COIN_TYPES )
    {
        // Get next random coin
        Rc4Output( RandContext, &value, sizeof(value) );
        value %= COIN_TYPES;

        totalCoins += 1;
        sets[value] += 1;
        if( 1 == sets[value] )
        {
            // First time we have seen this coin
            Statistics->ReachedAfterThisManyCoins[uniqueCoins] = totalCoins;
            uniqueCoins += 1;
        }
    }
}

//////////////////////////////////////////////////////////////////////////////////
//  main
//
//  Entry point
//////////////////////////////////////////////////////////////////////////////////
int
    main
    (
        void
    )
{
    Rc4Context  randContext;
    int         iteration;
    StatSet     stats;
    StatSet     statsTotals = {{0}};
    StatSet     statsSquares = {{0}};
    int         i;

    SeedStreamWithRandom( &randContext, 1 );

    for( iteration=0; iteration<NUM_ITERATIONS; iteration++ )
    {
        AcquireEntireSet( &randContext, &stats );
        for( i=0; i<COIN_TYPES; i++ )
        {
            statsTotals.ReachedAfterThisManyCoins[i] 
                += stats.ReachedAfterThisManyCoins[i];
            statsSquares.ReachedAfterThisManyCoins[i] 
                += ( stats.ReachedAfterThisManyCoins[i] 
                    * stats.ReachedAfterThisManyCoins[i] );
        }
    }

    // Display results
    printf( "%u Iterations\n", NUM_ITERATIONS );

    for( i=0; i<COIN_TYPES; i++ ) 
    {
        double  mean;
        double  sigma;
        double  sd;

        mean = (double)statsTotals.ReachedAfterThisManyCoins[i] 
            / (double)NUM_ITERATIONS;
        sigma = ( (double)statsSquares.ReachedAfterThisManyCoins[i] 
            / (double)NUM_ITERATIONS ) - ( mean * mean );
        sd = sqrt( sigma );

        printf( "%u after %.1f coins  (sd: %.1f)\n", i+1, mean, sd );
    }

    return 0;
}

This is one of the things I love the best about programming. While most of the time I am writing programs for specific things at work, its nice to be able to write a program to solve some problem as a hobby. After all the computer is a fantastic calculator and being able to control it to do what you wish is a very handy skill.

Personal GUIDs

I’ve always liked GUIDs, and I have always liked the idea of having “personal guids”. While everyone on the planet could be assigned a GUID, it would require some central authority to ensure each person only has one GUID rather than just generating a whole bunch. I like the idea that a GUID can be specifically for someone based on their details, not just freshly generated.

Type 5 GUIDs are perfect for this type of GUID use. A Type 5 GUID is based on a SHA1 hash of some arbitrary namespace ID, and then whatever values make sense for that namespace. So I shall create my own standard for assigning a GUID for everyone.

First I make an ID string that is flexible enough to include everyone, but unique for each person. Also it should be readily repeatable exactly the same way each time for the same person.

My ID format is simple: Its a UTF8 string in uppercase withe semi colons seperating the fields. There are 6 fields. The format is:

Surname;GivenNames;Gender;CountryOfBirth;PlaceOfBirth;DateOfBirth

All values should be uppercase. DateOfBirth is of the format YYYYMMDD in 8 decimal digits. Gender is either ‘M’ or ‘F’. GivenNames may have multiple names, separated by a single space between names. There must be no padding within the fields.

An example ID string is:

DOE;JOHN;M;AUSTRALIA;SYDNEY;19700101

Next I need an Namespace ID for this namespace I have created. A namespace ID is a GUID itself. I am assigning the GUID:  {5b390b3f-9a62-508a-b235-6e6e8d270720}. I could have generated any new GUID. However I decided to make a Type 5 GUID itself for the Namespace ID. The name GUID is the type 5 GUID of the URL of this article (http://waterjuice.org/2013/06/personal-guids/).

So the Type 5 GUID created from that Namespace ID and the ID string example above is {18448b15-02cc-58f2-857d-c7a2c07728d2}. This is a GUID that is specific to that ID and recreateable at anytime, as long as the name and birthdate and place doesn’t change!

I have modified the program I wrote to create the Type 5 GUIDs for URLs into creating personal GUIDs using this format.

PersonalGuid.zip – C Source Code and Binaries for Windows, OSX, and Linux. This is free and unencumbered software released into the public domain.

Example usage:

>PersonalGuid.exe Doe John m Australia Sydney 19700101
ID: DOE;JOHN;M;AUSTRALIA;SYDNEY
{18448b15-02cc-58f2-857d-c7a2c07728d2}

So download and find your own personal GUID. Perhaps one day this will become the basis of an RFC defining this as a standard :-)

GitHub

I’ve put the CryptLib up on GitHub, as I thought that might be a useful way for people to find and get source code.

https://github.com/WaterJuice/CryptLib

This contains the C source code for MD5, SHA1, SHA256, SHA512, and RC4, along with the projects Md5String, Sha1String, Sha256String, Sha512String, and Rc4Output.

The current version (1.0.0) is now on GitHub, the zip can also be downloaded here.

CryptLib_1.0.0.zip

This is free and unencumbered software released into the public domain.

stdbool.h

The built in types of C are not useful enough on their own as they vary between compilers. For example a long is 32 bits on Windows, but 64 bits on OSX. This makes using them in function prototypes problematic if word size is important. A lot of libraries define their own types, but again I don’t want to have this dependency. Fortunately there are some standard .h files that come with most C compilers now. C99 defines several standard files, one is stdint.h. This file defines data types such as uint32_t, which specifies an exact type. Microsoft’s C compilers are not C99 compliant, however they do include a subset. Fortunately they do include stdint.h. Which means I can use those without any problems on Windows. Both Linux and OSX (and probably most other gcc compilers) have stdint.h as well.

While stdint.h provides most of the base types that I want to use, there is one obvious one that is missing. C itself does not define a boolean type, but C99 defines stdbool.h which has the type bool and the value true and false. These are very basic types that I wish were built directly into the compiler. Unfortunately MS C does not come with stdbool.h. Even though its only a couple of lines in length. I’ve seen arguments on the Internet about whether a boolean type is required or useful. Some people think not, but I personally like them. Although the type is nothing special, its in fact just an int or a char probably, the usage of the type is different from a regular integer. Having an explicit type makes code clearer what its use is. For example if I have a function that returns a success that can only have two states (success, or not success), then having the return type a bool is far more clear than having the return an int. If its an int I’m going to wonder what possible values it could return are, maybe it returns different error codes. With a bool return type I can see that it simply returns a true/false state.

Because MSVC doesn’t contain stdbool.h I resisted using it initially with these projects. But I have decided its just too useful to ignore. So I have extended my build environment to have my own version of stdbool.h which is only used on Windows builds. Most of the core library cryptographic functions won’t use bool anyway, but some of the other projects will. This does mean there is one slight dependency when working in Windows, and thats the stdbool.h file I’ve added. It will be very easy for anyone to remove that dependency though. Simply replace bool with int, false with 0, true with 1, and remove #include <stdbool.h>. This could even be done with a very simple script.

The contents of my stdbool.h file are as follows:

#ifndef _STDBOOL_H_
#define _STDBOOL_H_

#ifndef __cplusplus
#ifndef __bool_true_false_are_defined

typedef int     bool;
#define true    1
#define false   0

#define __bool_true_false_are_defined

#endif //__bool_true_false_are_defined
#endif //__cplusplus

#endif //_STDBOOL_H_

The __bool_true_false_are_defined definition is part of the C99 standard. So I check that and don’t redefine if its already set. Additionally I make a check that its not C++ because C++ natively has bool, false, and true.