Monthly Archives: June 2013

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.

Advertisements

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.

Building non-Windows platforms from Visual Studio

To build on Windows I am using the makefile. I have a batch file that will call make with the platform I want to build. For Windows this simply calls  make after setting up the environment. In Visual Studio I have set up an external tool on the menu for building. This tool uses the command output window and therefore parses the errors. So I can hit a button on the toolbar and build using make. Any errors are easily navigable into the source. This isn’t surprising as its using the MS compiler so the format is going to be correct. I like to be able to build on all platforms just as easily.

I do most of the development on Windows, and use VS to edit the files, even when working on OSX or Linux as I like its editor. I can’t directly compile on Windows though as I need to compile in either OSX or Linux. My setup is an OSX computer with a Windows VM and a Linux VM (using Vmware). I keep all the files I’m working on on OSX. They Linux and Windows VMs share those same folders using Vmware Shared Folders features (I could also use networking shares). I also have SSH setup from the Windows VM to OSX and Linux. To set off a build on Linux or OSX I use SSH to run make on the appropriate platform. They are all sharing the same files. The directories are simliar but have different bases.

For example on Windows the files are visible from Z:\. This maps to “~” (home directory) on OSX, and on Linux to /mnt/hgfs/osxhome. I have my Build.bat file take a command line parameter to determine which build to do. For example “Windows” to do the Windows build. “OSX” to do the OSX build. If OSX is selected it takes the directory name, and modifies it to the one used by OSX. By removing the drive letter and replacing back slashes with forward slashes. For example Z:\Code\WaterJuice\makefile becomes ~/Code/WaterJuice/makefile. In Linux it would be compe /mnt/hghs/osxhome/Code/WaterJuice/makefile.

So from Visual Studio I can press a button and call Build.bat with Windows, OSX, or Linux. When its OSX or Linux it changes the base name and then calls ssh to run make. The output is displayed in the Visual Studio command output window. This is almost perfect. I do not have to switch VMs, I stay with in Visual Studio and can build on any platform. However the output of GCC is slightly different from Visual studio so it is unable to detect the errors directly. I have a small filter I wrote in Perl that modifies the output to be Visual Studio compatible.

First the file names need to be modified. gcc will obviously output the filenames that it sees. In order for VS to open the correct file they need to be converted to the name the Windows sees. So for example when gcc outputs the file name ./lib/Md5.c (it uses relative paths), the Perl script converts this to Z:\Code\WaterJuice\lib\Md5.c. The other thing it does it change the line output of errors and warnings so that Visual studio recognises them.

Visual studio uses a line format such as:

lib\LibMd5.c(76): error C2065: 'variable' : undeclared identifier

Where as GCC would display the same error as

lib/LibMd5.c:76: error: ‘variable’ undeclared (first use in this function)

So a simple RegEx is used to convert the :nn: part to (nn):  Now with the corrected path Visual Studio will bring up the file at the line number when I press F4.

Here is the Perl script I use. I call it GccToVss.pl

$| = 1;
( $actPath ) = @ARGV;

while ( <STDIN> )
{
    # Replace UTF-8 quote marks with plain ascii
	s/\xe2\x80\x98/\'/g;
	s/\xe2\x80\x99/\'/g;

	# Convert error format and paths from gcc to vss
	s/([\w.\/]+):(\d+):(.*)/$actPath$1($2) : $3/;
    s/\//\\/g;

    print $_;
}

It takes a single parameter which is the actual Windows directory where the root of the project is (the directory containing the makefile).

The following is Build.bat, the batch file that sets off the builds. It also caters for building in Cygwin and an x86 Windows XP build.

@echo off
setlocal

set RELPATH=%~p0
set RELPATH=%RELPATH:\=/%
set ACTPATH=%~d0%~p0

set OSXBASE=~
SET OSXHOST=osxdev@10.0.1.10

set LINUXBASE=/mnt/hgfs/osxdev
SET LINUXHOST=linuxdev@10.0.1.14

SET PROJECT=%2 %3 %4 %5 %6 %7 %8 %9

%~d0
cd %~p0

if /I "%1" == "Windows" goto Windows
if /I "%1" == "WindowsXP" goto WindowsXP
if /I "%1" == "Cygwin" goto Cygwin
if /I "%1" == "OSX" goto OSX
if /I "%1" == "Linux" goto Linux
if /I "%1" == "All" goto All

echo Syntax:
echo    Build ^<target^>
echo      ^<target^> options:
echo        Windows   - Windows x64 Vista Build
echo        WindowsXP - Windows x86 XP Build
echo        Cygwin    - Cygwin Build
echo        OSX       - Remote OSX Build
echo        Linux     - Remote Linux Build
echo        All       - Builds ALL the above
goto :eof

:All
set ALL=1

:Windows
call "c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\vcvarsall.bat" amd64
set CL=/link /LIBPATH:C:\WinDdk\7600.16385.1\lib\wlh\amd64 /LIBPATH:C:\WinDdk\7600.16385.1\lib\crt\amd64 /subsystem:console,6.0
echo.
echo ::::::::::::: Building for Windows x64 Vista :::::::::::::::::
make
echo ---- Build complete for Windows x64 Vista
if "%ALL%" == "" goto :eof
echo.

:WindowsXP
call "c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\vcvarsall.bat" x86
set CL=/link /LIBPATH:C:\WinDdk\7600.16385.1\lib\wxp\i386 /LIBPATH:C:\WinDdk\7600.16385.1\lib\crt\i386 /subsystem:console,5.1
echo ::::::::::::: Building for Windows x86 XP :::::::::::::::::
make
echo ---- Build complete for Windows x86 XP
if "%ALL%" == "" goto :eof
echo.

:Cygwin
echo ::::::::::::: Building for Cygwin :::::::::::::::::
make 2>&1 | tools\GccToVss.pl %ACTPATH%
echo ---- Build complete for Cygwin
if "%ALL%" == "" goto :eof
echo.

:OSX
echo ::::::::::::: Building for OSX :::::::::::::::::
ssh %OSXHOST% "cd %OSXBASE%%RELPATH%; make %PROJECT%" 2>&1 | tools\GccToVss.pl %ACTPATH%
echo ---- Build complete for OSX
if "%ALL%" == "" goto :eof
echo.

:Linux
echo ::::::::::::: Building for Linux :::::::::::::::::
ssh %LINUXHOST% "cd %LINUXBASE%%RELPATH%; make %PROJECT%" 2>&1 | tools\GccToVss.pl %ACTPATH%
echo ---- Build complete for Linux
if "%ALL%" == "" goto :eof

The batch file contains a few hardcoded paths. They should be easy enough to modify to suit your environment.

This is as close as I can get to building directly from Windows itself. There is the possibility of using cross platform compilers on Cygwin to produce OSX and Linux binaries, but they are very complicated to setup. Plus I prefer to build on the native platform itself using the compilers provided.

Hopefully this article helps other people build Linux and OSX binaries from within Visual Studio.

Adding Linux and command line building

Originally I wrote the projects here for Windows and OSX only. That was because I wanted to use Visual Studio and XCode IDEs and produce project files for them. Linux doesn’t really have an equivalent IDE, the standard way to build is via the command line using make. I didn’t like missing out building Linux, as it is part of the main 3 desktop OSes (Windows, OSX, and Linux). So I created a makefile that would work for Linux. It also worked for OSX as that has make.

I also decided I didn’t really like XCode’s IDE environment for building. It was rather tedious, and I was only using it to build, I use Visual Studio to edit the files. So I decided to scrap the XCode project files. I also didn’t like the way they were directories when viewing in Windows.

Now I had a convenient makefile for building in OSX and Linux, I decided I wanted to include Windows in that. Visual Studio comes with nmake, which is not very compatible with gnu make which Linux and OSX has. So I decided to ignore it and use make from Cygwin. Additionally this allowed me to easily compile using the Windows DDK libraries rather than the SDK ones with Visual Studio. I like to do this for the following reason: msvcrt.dll

Back with Visual Studio 6, when you compiled against the DLL version of the C Run-time library (CRT) it linked against msvcrt.dll. This is a DLL that has been shipped with almost every version of Windows, and still is in Windows 8. However after Visual Studio 6, Microsoft decided that you shouldn’t do this, and instead link to specific versions of the CRT that come with Visual Studio. The problem is these DLLs are not shipped standard with the Operating System. Microsoft says to distribute them with its “handy” tool. However I like single .exe programs that don’t depend on anything. For that reason I link with the static runtime library when using Visual Studio. That way it doesn’t not depend on a DLL, it does however increase the executable size. I also like small exe files.

Despite Microsoft saying you shouldn’t like to msvcrt.dll anymore, it turns out that they do for all their tools. The WinDDK (or WinWDK) libraries bind to msvcrt.dll for its usermode building. While WinDDK is used for Kerenl mode development, it also has a lot of usermode libraries. Personally I like to use the Visual Studio compiler, but with the WinDDK libraries, and falling back to the VS ones for the libraries that the DDK does not have.

This can be setup in the IDE using the include paths and library paths in the project files. However I want to keep those simple and standard. Not everyone is going to install the WinDDK. So I am leaving the project files using static linking with Visual studio libraries. However I extended the makefile to build using WinDDK libraries when building in Windows.

Seen I was using Cygwin for the make tool (and I always have cygwin installed), I thought I’d add the option of compiling using gcc in Cygwin, and producing Cygwin .exe files. These however are 32bit files as Cygwin is still only 32 bit. I also added to the make file the option to create 32bit Windows exe targeted for Windows XP. The x64 ones are targeted for Vista. When I release projects here in the future I will include x64 binaries for Windows, OSX, and now Linux. I won’t include either cygwin or x86 Windows, I just like to verify I can compile for them.

The following is my template makefile. This is fairly rough at this stage. For Windows it looks to see if the Visual Studio environment variables are set (which are set if you run the VS command prompt). Otherwise it uses Cygwin

OUTDIR = Bin/$(PLATFORM)
INCLUDES = -I ./lib

all: Md5String Sha1String

Md5String: dir
	$(COMPILE) projects/Md5String/Md5String.c lib/LibMd5.c lib/LibSha1.c lib/LibSha256.c lib/LibSha512.c $(TAIL)
	$(STRIP)

Sha1String: dir
	$(COMPILE) projects/Sha1String/Sha1String.c lib/LibSha1.c $(TAIL)
	$(STRIP)

dir:
	@mkdir -p $(OUTDIR)

###### Setup build parameters #####
ifeq ($(OS),Windows_NT)
    ifdef VSINSTALLDIR
        ifeq ($(Platform),X64)
            PLATFORM = Windows
        else
            PLATFORM = WindowsX86
        endif
        INTDIR = Build/$(PLATFORM)/$@
        COMPILE = @echo & echo ::::: Building $(PLATFORM) $@ & mkdir -p $(INTDIR) & cl $(INCLUDES) /nologo /Ox /Oi /Ot /GL /MD /W4 /WX /Fe$(OUTDIR)/$@ /D_CRT_SECURE_NO_WARNINGS /Fo$(INTDIR)/ 
		TAIL=/link /RELEASE
    else ifneq (,$findstring /cygwin/,$(PATH))
        PLATFORM = Cygwin
        COMPILE = @echo ::::: Building $(PLATFORM) $@ & gcc $(INCLUDES) -O3 -Wall -Werror -o $(OUTDIR)/$@
        STRIP = @strip $(OUTDIR)/$@
    else
        PLATFORM = None
        COMPILE = echo
        STRIP = 
        $(error Windows requires VS environment, or Cygwin)
    endif
else
    PLATFORM = $(shell uname)
    ifeq ($(PLATFORM),Darwin)
        PLATFORM=OSX
    else ifeq ($(PLATFORM),Linux)
        PLATFORM=Linux
	else
        $(error Unsupported platform. Non Windows platform support: OSX and Linux)
    endif       
    COMPILE = @echo ::::: Building $(PLATFORM) $@ & gcc $(INCLUDES) -O3 -Wall -Werror -pthread -o $(OUTDIR)/$@
    STRIP = @strip $(OUTDIR)/$@
    TAIL = -lm
endif

In order to build Windows, you need to a command prompt that is setup correctly. I made a little batch file that calls the VS batch file for setting up environment variables, then sets the CL environment variable to include link path to WinDDK libraries. The batch file assume the default locations for Visual Studio 2010, and WinDDK 7.1

@echo off
call "c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\vcvarsall.bat" amd64
set CL=/link /LIBPATH:C:\WinDdk\7600.16385.1\lib\wlh\amd64 /LIBPATH:C:\WinDdk\7600.16385.1\lib\crt\amd64 /subsystem:console,6.0
cmd /k title Build Environment for Windows Vista x64

I moved the Visual Studio project files (.vcxproj and .vcxproj.filters) into a seperate directory called VsProjectFiles. This keeps the source directories completely free of extra files that aren’t .c or .h. The property files are also in there. When compiling with Visual Studio from the sln file it uses purely the Visual Studio libraries, and statically links against the CRT.

 

Type 3 and 5 GUIDs

This article talks about GUIDs, and in particular type/version 3 and 5 GUIDs (or UUIDs).

UrlGuid.zip – Public domain C source code for generating type/version 3 and 5 GUIDs. Includes x64 executables for OSX and Windows. This is free and unencumbered software released into the public domain.

I love the concept of GUIDs (or UUIDs). They are 128 bit IDs in a standardised format that are unique across all namespaces. It is somewhat unclear as to whether the name is actually GUID (Globally Unique Identifier) or UUID (Universally Unique Identifier). The best explanation of the difference is that Microsoft use the term GUID, and generally UUID used else where. But they both refer to the format as defined by RFC4122 (“A Universally Unique IDentifier (UUID) URN Namespace“). Microsofts main contribution seems to have been to add the curly braces around the string that is commonly seen. I am going to use the term GUID from now on.

Most people have probably seen a GUID, they look like this: {855273c6-bca6-439e-8880-7a875c4394ed}. Sometimes they don’t have curly braces, and sometimes they are uppercase, and occasionally mixed case. In all cases they are just a string representing a 128 bit number in big endian format. Due to the fact it was designed by committee it has a lot more irrelevant complexity than is required. They could have simply displayed the GUID as one long hex string, instead they decided to break it up into groups of 4, 2, 2, 2, and 6 bytes. RFC4122 defines the 128 bit structure into various elements. However the fields really only make sense in a type 1 GUID. For the most part no one cares about any of the fields and it should be treated as one single 128 bit number.

The interesting thing about the GUID is that every GUID created should be unique without requiring a central registration authority. It gets this property mainly from the fact that 128 bits make up a large space and that if you randomly pick a 128 bit number it is incredibly unlikely anyone else will pick the same. The most common GUIDs seen are type (or version) 4 GUIDs. 122 bits of a type 4 GUID are purely randomly generated. There are 4 bits set as the type number, and another 2 bits set as the RFC4122 variant. The version/type number of every GUID can easily be seen, it is the 13th hex digit (or the 1st digit in the 3rd group). As you can see from the example GUID I showed before {855273c6-bca6-439e-8880-7a875c4394ed}, the version value is 4.

Type 1 GUIDs, identified by a 1 value in the 13th digit, have a more structured format. Rather than use pure random to hope that the same GUID is not generated twice, a more defined procedure is used. The last block of 12 digits is set as the 48 bit MAC address of the computer that generated the GUID. As MAC addresses are supposed to be unique, this partitions the space into unique groups for each computer. Additionally a high precision time value is used to partition the space based on time. Then there are some random bits as well as sequence values to ensure the same computer doesn’t accidentally generate the same GUID twice even if its clock gets messed up.

While Type 1 GUIDs use a good scheme to avoid collisions, they are unpopular because they give away information. In particular they give away when the GUID was generated and, more significantly, the MAC address of the computer that generated it. In fact it was the use of Type 1 GUIDs in Microsoft Office documents that helped lead to the arrest of the “Melissa Worm” author over a decade ago. That was a high profile case and made people very uneasy about the use of GUIDs which could track people. For example I may use my computer for two distinctively different roles and not wish to have things produced for one role in any way relatable to the second role.

After the Melissa Worm incident MS changed to using Type 4 GUIDs. As these are completely randomly generated, it can not be determined if two GUIDs were created by the same computer or person.

The most common use of GUIDs is to have a unique ID for some new item just created. It could be a database entry, it could be a ticket number, or anything. For this use a Type 1 or Type 4 GUID is perfect, and almost all the literature on the Internet refers only two these two types. However there are cases where you want a unique, but repeatable, identifier for an object. For example URLs.

A URL is a unique Id. However because its size is variable, it may not be convenient to use as an UD. The obvious thing to do is to take a hash of the URL and use that as an ID value, now you have a fixed size ID. There are two versions of GUIDs that do exactly this. The advantage of using these over straight hashes is that it remains in the same namespace as the rest of GUIDs, while guaranteeing not to clash with Type 1 and 4 ones. The two versions are 3 and 5.

To create a version 3 or 5 GUID you first need a namespace ID. This is a GUID itself. You can generate your own GUID to represent your name space. This is to prevent items in different name spaces but having the same name generating the same GUID. For example I might want a namespace which has colours as the values. eg my name space consists values from the set { red, blue, green, yellow }. Another name space may be that of all English words, which clearly would contain the values in my colour set. The same GUID should only be generated for “red” when used in the same namespace.

The 128 bits of the name space ID is prepended to the named value (eg “red”) and either an MD5 or a SHA1 hash performed. Note the named value does not have to be text. It is whatever the name space ID represents, it can be of any form including a hash itself, or a GUID. The output of the hash is used mostly as the GUID. However only 122 bits of the GUID value can be arbitrarily set. The 13th hex digit of the hash is replaced by the version/type value. If the hash is MD5 then the value 3 is used, if the hash is SHA1 then the value 5 is used. Additionally the top two bits of the 17th hex digit (1st digit in 4th group) are set to 10 (in binary). This defines the “variant” of the GUID as RFC4122 compliant. This means that the 17th hex digit of any RFC4122 GUID (ie almost all of them) will only have 4 possible values: 8, 9, a, b.

RFC4122 defines four standard name space IDs.

NameSpace_DNS = {6ba7b810-9dad-11d1-80b4-00c04fd430c8}
NameSpace_URL = {6ba7b811-9dad-11d1-80b4-00c04fd430c8}
NameSpace_OID = {6ba7b812-9dad-11d1-80b4-00c04fd430c8}
NameSpace_X500 = {6ba7b814-9dad-11d1-80b4-00c04fd430c8}

So for example, to make a type 3 GUID from the dns name waterjuice.org, the 128 bit value of NameSpace_DNS (in big endian) is prepended to the ascii string “waterjuice.org” and then a MD5 hash calculation made. This results in the MD5 hash: bed9e1fe7b92c85c82aa104c8c45bccf. The 13th digit is replaced with a 3, and the top 2 bits of the 17th digit are set to 10 binary (In this case those bits already were set that way). The final result, displayed as a GUID, is:

{bed9e1fe-7b92-385c-82aa-104c8c45bccf}

Using SHA1 instead of MD5 the following type 5 GUID represents waterjuice.org:

{c1a7f72b-f2ee-5455-990c-308ae1450a0e}

Unfortunately RFC4122 contains an error in the example it provides for creating a type 3 GUID. Appendix B gives an example of a type 3 GUID from the DNS name “www.widgets.com”. It incorrectly displays the result as {e902893a-9d22-3c7e-a7b8-d6e313b71d9f}. This was corrected in errata 1428. The correct result is {3d813cbb-47fb-32ba-91df-831e1593ac29}. Unfortunately the incorrect value is often requoted on other sites on the internet.

There are countless programs that generate type 1 and type 4 GUIDS. There are many online generators that you can use. Additionally OSX comes with uuidgen which is a command line tool to create a type 4 GUID. While Visual Studio has a uuidgen.exe which will generate type 1 or type 4 GUIDs. There are, however, very few examples of generators for type 3 and type 5. So I have written a program in C to create type 3 and type 5 GUIDs from either a DNS name or a URL.

UrlGuid.zip – Public domain C source code for generating type/version 3 and 5 GUIDs (UUID). Includes x64 executables for OSX and Windows.

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

Example usage:

>UrlGuid.exe http://waterjuice.org/2013/06/type-3-and-5-guids/
{cf0aff65-65c3-35a2-b04f-923e1f8bf1f3}
{3a8df732-bc01-57ab-bf7f-94461ee1057b}

As there are few examples on the internet (and some of them are wrong) I will include some type 3 and 5 GUIDs for some common DNS names and URLs.

google.com

    {9a74c83e-2c09-3513-a74b-91d679be82b8}
    {64ee70a4-8cc1-5d25-abf2-dea6c79a09c8}

www.wikipedia.org

    {ea68c8dd-6a38-39ac-8fa4-d55bfb7018fd}
    {02c295f5-54a8-5d29-8d1f-b619216b20c0}

unlicense.org

    {a209c2da-4d39-395e-97b3-38e58d800777}
    {d89fa53a-36cb-5b1c-819a-8b3327182ced}

http://en.wikipedia.org/wiki/Globally_unique_identifier

    {734d5d9c-ea54-3ef9-8d40-fa7db2281e24}
    {d18e9b50-d196-558d-ade3-6f54da5608fb}

https://www.google.com/webhp?hl=en&tab=ww

    {5404423a-b81e-323c-be9b-d3446d606b35}
    {c2b80bf8-7e38-54d2-b0d7-d842eb3e173d}

http://unlicense.org/UNLICENSE

    {456e7994-3b66-316f-839c-68b4b30b5b85}
    {b889eec7-f11a-592e-899b-382086d69067}