Open a command prompt (run->cmd).
Type the following:

color 97
help for

Then press alt+enter. This will give a full screen white on blue gibberish messge (or appear that way and first glance) – then sit back and wait for the horror as they “realise” their computer has got a BSOD. Most people know enough about them to recognise them and know theyre bad, but not enough to be able to analyse the kernel dump messages.

Barely days after writing the first compile time hashing post, I needed to use the information in it. As I said at the time it’s ugly, and the Boost license raises some questions for its use in all locations, so I developed a better solution as a separate tool, giving the much nicer overall syntax of:

#include "file_ext.cth"
switch (Hash(szInputString))
{
	case __H(hello):
		// Do something
	case __H(there):
		// Something else
	default:
		// Other
}

Use

To use this in code is very simple. Define the string that you want to hash inside a __H macro, like so:

__H(HASH_THIS)

Then, above this point, include another file (which may well not exist yet) whose file name is:

CurrentFileName_CurrentFileExtension.cth

So the inclusion for a file “main.cpp” would be “main_cpp.cth” (cth stands for “Compile Time Hashing” if you’re wondering) (this technique is based on that used for WPP – Windows Software Trace Preprocessor). If you don’t like using __H you will have to change it in the source code of the tool (and that’s not as trivial as it sounds, I’ve written it as a very efficient, but somewhat obfuscated, state machine).

You also need to include a single file with the actual definition of the hash function (currently Bernstein as it is fast and has low collisions) into your project.

The final stage is calling the hash program on the current file, like so:

c:\path\to\file> "c:\path\to\tool\StringHashing.exe" (filename) (ext)

Collisions

If you have two strings in the same file (yes, sorry – see the limitations section) with the same hash the compiler will generate an error. This error is currently not much help as it only tells you the second string with this hash. I did try to make it give you both but apparently macros aren’t evaluated in “#error”.

Automation

The tool itself has no capability for looping through directories – you simply call it passing the name and extension of a single file, however for real use I have integrated it in to my build process in Visual Studio using a batch file to automate the calling.

To call the tool, add a pre-build event something like the following. Obviously it depends on the location of your tool – I have a very strict (and, IMHO, neat) VS solution directory layout, so things like this are in a “Tools” directory:

"$(SolutionDir)\Tools\StringHash.bat" "$(ProjectDir)"

The batch file itself that I use is:

@echo off
setlocal

if '%1' == '' echo Usage:  StringHash.bat [Directory]

set HASH_DIR=%~dp0

echo "Scanning for .cpp files."
for /f "usebackq delims=" %%i in (`dir /s /b "%~1\*.cpp"`) do call :dohash "%%i"
cd %HASH_DIR%
echo "Scanning for .c files."
for /f "usebackq delims=" %%i in (`dir /s /b "%~1\*.c"`) do call :dohash "%%i"
cd %HASH_DIR%
echo "Scanning for .h files."
for /f "usebackq delims=" %%i in (`dir /s /b "%~1\*.h"`) do call :dohash "%%i"
cd %HASH_DIR%
echo "Scanning for .hpp files."
for /f "usebackq delims=" %%i in (`dir /s /b "%~1\*.hpp"`) do call :dohash "%%i"
cd %HASH_DIR%
echo "Scanning for .def files."
for /f "usebackq delims=" %%i in (`dir /s /b "%~1\*.def"`) do call :dohash "%%i"
cd %HASH_DIR%
goto :EOF

:dohash
cd "%~p1"
"%HASH_DIR%\StringHashing.exe" %~n1 %~x1

goto :EOF

This will do all .cpp, .c, .hpp, .h and .def files with any __H appearences (technically it does them all regardless, but if you don’t include the extra files they don’t matter).

Limitations

Stupid

I wrote, tested, integrated and automated this tool inside about an hour, and have only modified it once since, so it is VERY simple and VERY stupid. If it sees the pattern “__H(TEXT)” it will convert it – regardless of other concerns such as current comment or string context. For this reason you have to be VERY careful when doing something like:

// The "__H(hello)" macro evaluates to "__H_hello".
case __H(hello):

This code has the required pattern “__H(TEXT)” TWICE – the one in comments counts, so the tool will parse both then detect a collision between the two. Stick to code like:

// The "__H" macro evaluates to "__H_hello".
case __H(hello):

Characters

Only characters valid in C symbol names may be used in the text within the brackets, unlike symbol names however numbers may be the first (and only) characters. The switch is also case sensitive.

File Scope

The parser generates ONE inclusion per file, so this is invalid code, despite looking fine:

#include "main_cpp.cth"
switch (Hash(a))
{
	case __H(hello):
		break;
}
switch (Hash(b))
{
	case __H(hello):
		break;
}

However, there are ways around this problem, but they’re ugly:

// Include the hashes.
#include "main_cpp.cth"
// Redefine the macros (see "advanced" for wierd syntax).
#undef __H
#define __H(\
	m)
#define HASH(m) __H_##m
// Generate all the hashes in valid code.
__H(hello)
__H(hi)
// Now use the hashes.
switch (Hash(a))
{
	case HASH(hello):
		break;
}
switch (Hash(b))
{
	case HASH(hello):
		break;
}

That undefines the __H macro so that appearences of it in code will not generate any code that the compiler will see. It then defines a new macro to the old definition of __H so that you can still use the hashes, and use them multiple times. Finally it includes all the “__H(TEXT)” macros ONCE so that the will not collide.

The alternate method is using the syntax from the advanced section:

#include "main_cpp.cth"
switch (Hash(a))
{
	case __H(hello):
		break;
}
switch (Hash(b))
{
	case __H(\
		hello):
		break;
}

Advanced

Spacing

Note that despite being quite stupid, the tool does have the ability to recognise different spacings, so if you want spaces before or after your brackets on the “__H”, you can do.

Overriding

If for some reason you need to override the “__H” macro, or use it’s syntax without being parsed by the tool (as in the previous example) you can use the line continuation operator to write valid code without the tool picking it up:

switch (Hash(b))
{
	case __H(\
		hello):
		break;
}

This will be correctly interpreted by the compiler, but it ignored by the tool. I mentioned that I have only modified the tool once, and this is why. Originally this code did work and was ignored by the tool, but it complained about a bad macro format, so I added code to ignore just this case quietly.

Linux/Non-VS

I have not written anything for any of these systems. The tool was written in as close to pure C as I could manage to quickly knock out off the top of my head with no checking, so should recompile. I have no doubt Perl and possibly Python would be vastly better for this on Linux (and Windows if you have it on there), but I’ve written the code now so it’s a moot point. I don’t know how to integrate calling the tool into other tool chains, but I can’t see it being hard if they’re any good at all.

Download

I have included a VS solution with both the tool’s project and an example project using said tool here

Footnote

I just installed this syntax highligher as my code was VERY hard to read on here. Hopefully it will be better now. Next step – a decent theme…

Update: I changed to this highlighter – it’s much nicer.

switch (szInputString)
{
	case "hello":
		// Do something
	case "there":
		// Something else
	default:
		// Other
}

This has always seemed quite an arbitrary limitation to me, especially given that it would not be hard – all you need is a standard hash function to convert the strings to unique numbers in both code and the compiler. The compiler can then generate the following (the only problem comes from collisions on inputs):

switch (hash(szInputString))
{
	case HASH("hello"):
		// Do something
	case HASH("there"):
		// Something else
	default:
		// Other
}

I just happened upon a method of doing this today so I had to post it! It’s pretty ugly and limited, but it’s an improvement over the current situation:
boost compile time string hashing
As I said it’s ugly, and I’m not lying:

switch (hash_of(szInputString))
{
	case Compile<'h', 'e', 'l', 'l', 'o'>::hash:
		// Do something
	case Compile<'t', 'h', 'e', 'r', 'e'>::hash:
		// Something else
	default:
		// Other
}

But this can be improved upon slightly:

#define HASH(...) \
	Compile<__VA_ARGS__>::hash

switch (hash_of(szInputString))
{
	case HASH('h','e','l','l','o'):
		// Do something
	case HASH('t','h','e','r','e'):
		// Something else
	default:
		// Other
}

Maths

First, the maths. Let’s assume there are two objects, A and B, and a point P. The distance between A and P and B and P are then:

Dpa = sqrt( (Px - Ax)^2 + (Py - Ay)^2 + (Pz - Az)^2 )
Dpb = sqrt( (Px - Bx)^2 + (Py - By)^2 + (Pz - Bz)^2 )

This is basic and was covered in the last post.
It is obvious that:

Bx = Ax + (Bx - Ax)

If you don’t believe me, rearrange the formula and A will disappear.
So we can now get:

Dpa = sqrt( (Px - Ax)^2 + (Py - Ay)^2 + (Pz - Az)^2 )
Dpb = sqrt( (Px - (Ax + (Bx - Ax)))^2 + (Py - (Ay + (By - Ay)))^2 + (Pz - (Az + (Bz - Az)))^2 )

I will rearrange one of these sections, the x, y and z parts are all identical:

X = (Px - Bx)^2

X = (Px - Ax)^2 + ((Ax - Bx)^2 - 2Ax(Ax - Bx)) + Px(2(Ax - Bx))

So what does this prove? Well we started with the equation for the distance between P and B, and ended up with the equation between P and A with some extra bits. These extra bits look complicated and wierd, but they are actually very simple. Firstly:

(Ax - Bx)^2 - 2Ax(Ax - Bx)

That ONLY contains A and B, which are static objects, so this number is a constant for two items! What’s more, this is a constant for X, Y and Z, so these can all be combined in to a single value. Secondly:

Px(2(Ax - Bx))

Here, P is used, which is our dynamic position, but the rest of it is also a constant for two objects. So we can make out final equation:

Dpb = Dpa + Cab + PxABX + PyABy + PzABz

This excludes the square root action, but that’s often not needed.

Use

If, as is often the case, you wish to compare one point (P) to a large collection of other points (A, B, C etc), and those other points are all known in advance, you can use this method to pre-compute certain values. This is best demonstrated with a code example:

struct obj
{
	objinfo info;
	float x, y, z;
	float ow;
	float ox, oy, oz;
};

struct obj g_objects[10];

int g_count = -1;

// This function very basically adds a new object to the array.
void AddObj(float x, float y, float z)
{
	float ox, oy, oz;
	// Get the offset from the last object.
	if (g_count == -1)
	{
		ox = 0.0f;
		oy = 0.0f;
		oz = 0.0f;
	}
	else
	{
		dx = g_objects[g_count].x;
		dy = g_objects[g_count].y;
		dz = g_objects[g_count].z;
	}
	float
		dx = ox - x,
		dy = oy - y,
		dz = oz - z;
	++g_count;
	// Store the offsets.
	g_objects[g_count].ox = 2 * dx;
	g_objects[g_count].oy = 2 * dy;
	g_objects[g_count].oz = 2 * dz;
	// Calculate the main constant.
	g_objects[g_count].ow =
		(dx * dx + dy * dy + dz * dz) - 2 *
		(ox * dx + oy * dy + oz * dz);
	// Store the other data.
	g_objects[g_count].x = x;
	g_objects[g_count].y = y;
	g_objects[g_count].z = z;
}

// This function takes a position and checks which objects are in range.
void CheckAll(float x, float y, float z, float range)
{
	float
		offset = x * x + y * y + z * z;
	struct obj *
		cur = g_objects;
	for (int i = 0; i <= g_count; ++i)
	{
		// Calculate the distance to the object.
		offset = offset + cur.ow + x * cur.ox + y * cur.oy + z * cur.oz;
		// We now have the SQUARED distance to this object.
		if (offset < range * range)
		{
			printf("This object is in range");
		}
		++cur;
	}
}

Future

I am trying to determine wether the dot-product can be optimised (if you were to write custom assembler there it would be awesome), but I don’t know if it is possible to use some method so that all those multiplies in the inner loop can be combined. For reference, this is the dot product:

PxABX + PyABy + PzABz

If something can be done with that the code will become:

Distance = Last Distance + Constant + Dot Product


Conclusion

I intend to use this somehow, I already use a version of this code in my current research and it has HALVED the time taken for my code to run – so that has to be a good thing!

Update

There is some interesting information here:
How fast can we compute the dot product?
I decided to look into the SSE stuff to help this out. The good thing is that we can combine the Constant in to the dot product to by adding a W component of 1 to the Point’s vector – this will mean that both position and offset can be stored as SSE 128bit values in the structure. It will require some very tricky coding to actually be able to use this information and frankly I’m not sure any greater improvement is worth it, especially not the code to interleave the calculations – especially given the amount of other stuff any function using this data will need to do.

This code would also restrict who can use the code based on SSE availability.

I’ve never seen this detailed anywhere else, though it likely has been, so I’m going over it here as a semi-official location.

When getting the distance between two points, you use pythagoras (or a generalisation in many dimensions). The regular formula is:

distance = sqrt ( (x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2 )

With:

position1 = x1, y1, z1
position2 = x2, y2, z2

This formula is perfectly fine if you just want the distance between two points. But what about when you have a huge number of points? One common use case I have come accross is where you have two sets of points and you want the distances between everything in the first set and everything in the second set. In a multiplayer object system there may be 100 players and 10,000 objects – that’s 1,000,000 calculations. Or in a molecular visualisation system could could have a grid of size 500×500 with 200 atoms randomly spread – to calculate the effect of every atom on every grid point would require 50,000,000 calculations!

Obviously in standard pythagorean calculations the square root is the slow part, but for many applications this can be moved or removed entirely (for example checking if two objects are within a certain radius of each other can use the square of the radius for comparison instead). But when you’re talking on the order of millions of calculations, any improvement will be very useful!

A simple rearrangement follows:

distance = sqrt ( (x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2 )
distance^2 = (x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2
distance^2 = x1^2 + x2^2 - 2x1x2 + y1^2 + y2^2 - 2y1y2 + z1^2 + z2^2 - 2z1z2
distance^2 = x1^2 + y1^2 + z1^2 + x2^2 + y2^2 + z2^2 - 2x1x2 - 2y1y2 - 2z1z2
distance^2 = (x1^2 + y1^2 + z1^2) + (x2^2 + y2^2 + z2^2) - 2(x1x2 + y1y2 + z1z2)
distance = sqrt ( c1 + c2 - 2(x1x2 + y1y2 + z1z2) )

Where:

c1 = x1^2 + y1^2 + z1^2
c2 = x2^2 + y2^2 + z2^2

It should now be fairly obvious where this is going. For any point (x, y, z), clearly (x^2, y^2, z^2) is a constant, so can be precomputed and stored – saving operations for every point combination.

If you will only be doing distance comparisons, for which the exact distance is not required, this can be optimised further. To compare two distances, the squares can be compared to give the correct result, futher, half the squares compared will still give the correct result. This gives:

distance^2 / 2 = c1 + c2 - x1x2 - y1y2 - z1z2

Where:

c1 = (x1^2 + y1^2 + z1^2) / 2
c2 = (x2^2 + y2^2 + z2^2) / 2

Now the only calculation performed differently for every point pair is the end subtracted multiplications.

:: %1 - Path
:: %2 - Filename

::D:

cd "%1"

mkdir %2

:: Set a load of basic variables to make commands easier.
set aux=
::-aux-directory="%1\auxfiles"
set job=-job-name "%1\%2\%2"
set inc=-include-directory "C:\Documents and Settings\<User>\Application Data\MiKTeX\fuzz"
set src=-src-specials

:: Convert all local .PNG files to .EPS files for easy insertion.  Ideally this
:: would only convert images which have not already been converted, but I can't
:: see how to do that easily with ImageMagick, and that does preclude the
:: possibility of changing images and getting the new versions.  UPDATE:  I now
:: move all the .PNG files to the working directory after converting them.
:: This means they still exist for editing and you can update the .EPS file by
:: copying the .PNG back to the main directory but means that images are
:: generally only converted once each.
"C:\Program Files\ImageMagick-6.5.9-Q16\mogrify.exe" -format eps *.png

:: Move all the .PNG files to the working directory.
move /Y *.png %2

:: Compile the first pass in LaTeX.
:: Make sure all output files go to the same place and all input files are
:: searched for in the same place.
"C:\Program Files\MiKTeX 2.8\miktex\bin\latex.exe" %job% %aux% %inc% %src% "%1\%2"

:: Compile the references in BiBTeX.
"C:\Program Files\MiKTeX 2.8\miktex\bin\bibtex.exe" %aux% %inc% "%1\%2"

:: Run LaTeX twice more (who knows why...).
"C:\Program Files\MiKTeX 2.8\miktex\bin\latex.exe" %job% %aux% %inc% %src% "%1\%2"
"C:\Program Files\MiKTeX 2.8\miktex\bin\latex.exe" %job% %aux% %inc% %src% "%1\%2"

:: Create the PDF file.
::"C:\Program Files\MiKTeX 2.8\miktex\bin\pdflatex.exe" %job% %aux% %inc% "%1\%2"

:: Create a postscript file.
"C:\Program Files\MiKTeX 2.8\miktex\bin\dvips.exe" -Ppdf -o "%1\%2\%2.ps" "%1\%2\%2.dvi"

:: Convert to a PDF.
"C:\Program Files\MiKTeX 2.8\miktex\bin\ps2pdf.exe" "%1\%2\%2.ps" "%1\%2.pdf"

:: View it.
"%1\%2.pdf"

Most of the lines are commented, but I’ll go over what it does anyway.

Firstly it reads the directory with your .tex file in and converts all found .PNGs to .EPS, this is because LaTeX can’t use PNGs but I tend to make them. It then moves all the original PNGs to a child directory with the same name as the output file. This allows you to modify the files and reconvert them by putting them back in the parent directory, but saves reconverting the files every time you produce output.

Secondly it generates the .DVI file. There are quite a few lines to this as it is designed to work with Bibliotex, which requires multiple passes over a file to first collect and then fill out the required references.

Finally it generates a .PDF file and opens it for viewing. You could just use the normal DVI viewer, but I don’t.

Note that this is written specifically for my use with the “FUZZ” type, if you don’t want to use this remove the include line. If you do, update the “<User>” part.

I also use Notepad++, in which I have configured “alt+shift+m” to run this command using:


"C:\Documents and Settings\<User>\Application Data\MiKTeX\compile.bat" $(CURRENT_DIRECTORY) $(NAME_PART)


Again, adjust <User> to your user name.

yavascript.org

Example 1 – CSS tooltips:

http://yavascript.org/css/tooltip.html

Note: CAN be dodgy in IE6 if you don’t make the offset big enough to appear under the link.

Example 2 – CSS lightbox:

http://yavascript.org/css/lightbox.html

Note: Currently only works in Firefox 3.

One of the things added to the yavascript compiler, but not completed by the time I had to hand the project in to uni, was a debug mode. Because the compiler reads all the code in syntactically it can output it in whatever form it likes, including an experimental full debug mode. Basically your code goes from:

a += /search/i;

To:

$Y._addAss(
	/* target */
	$Y._ref(
		/* name */
		'a',
		/* original code */
		'a',
		/* original line */
		42,
		/* original file */
		'my_code.js'),
	/* expression */
	$Y._regex(
		/* pattern */
		'search',
		/* modifiers */
		'i',
		/* original code */
		'/search/i',
		/* original line */
		43,
		/* original file */
		'my_code.js'),
	/* original code */
	'a +=\n\t/search/i;',
	/* original line */
	42,
	/* original file */
	'my_code.js');

The obvious question is WHY? But if you examine this code carefully you will see that it makes run-time debugging information a snap to collect and use to find problems.

Use

Given that this mode uses the compiler to generate it’s code, using this would be no more complicated than writing regular code and compiling, just compiling to a format different to minified code. It could even be written to output all the required functions in the same file, though the more sensible option would be to get the user to include a second script in the html:

<script type="text/javascript" charset=”UTF-8” src="yavascript/debug.js"></script>
<script type="text/javascript" charset=”UTF-8” src="my_code_in_debug_mode.js"></script>

To compile in debug mode would simply require the addition of an extra command line switch “-d”, so to compile the following:

var a = window['console'];

In debug mode would require:

yavascript.exe -f input_filename.ys -o output_filename.js -t web -d

_DEBUG

The introduction of debug mode adds one of the most obvious uses of the preprocessor: debug outputs. Although, given the verbose nature of the information output in debug mode, debug outputs will be less needed, there are still some things compilers can’t guess that you want to know. Debug mode in the compiler and development mode in the browser (or other development environment) will both add an internal define called “_DEBUG” allowing code such as:

a += 10;
#ifdef _DEBUG
	console.log('Did the addition at: ' + Date.now());
#endif

That code will then be included or excluded depending on the compile mode, and included in development.

Implementation

Obviously using function calls instead of standard operators requires re-writing most of javascript with additional checks for things like null objects or missing and invalid properties. One example for part of the addition function would be:

$Y =
	{
		toString :
			function (obj)
			{
				return Object.prototype.toString.call(obj);
			},
		isRegex :
			function (obj)
			{
				return this.toString(obj) === '[object RegExp]';
			},
		_add :
			function (first, second)
			{
				if (this.isRegex(first))
				{
					this.error('Can't add regular expressions:);
					this.error('first parameter: ' + first);
				}
				if (this.isRegex(second))
				{
					this.error('Can't add regular expressions:);
					this.error('second parameter: ' + second);
				}
				// Additional checks
				return first + second;
			}
	};

Functions are prefixed with ‘_’ to distinguish keywords from their debug equivalent, but this will probably be changed to something else.

Obviously far more checks than just regex can be included, such as trying to add an object to a number, or NaN to anything, but it’s just a short example.

Bugs

I’m still working on getting closures to work, but I have an idea for them. Apart from that there aren’t any bugs as the system isn’t done yet!