[Cryptography] Introducing the world's worst hash function

[Peter Gutmann]

Modern hash function are designed to be as efficient as possible on pipelined,
superscalar processors, but what if you wanted one that was the exact
opposite?  I needed a function to create small random delays but couldn't just
Sleep() or usleep() or nanosleep() or whatever since that's too granular.
What I needed was a fine-grained delay function, which led to MurMurHash's
mutant cousin MerdeMerdeHash, the one they keep locked in the basement and
only let out once the guest have left.

MerdeMerdeHash uses the slowest and most unpredictable data-manipulation
instructions available, combined with endless data dependencies and pipeline
stalls.  Multiplies, while they often have a single-cycle throughput,
typically have a multiple-cycle latency, which we enforce with data
dependencies.  The magic instruction for poor performance though is the
divide, which is typically microcoded and with a huge, data-dependent,
latency. 

Comments and further pessimisations welcome.

int merdeMerdeHash( const int value1, const int value2 )
	{
	MACHINE_WORD l = value1, r = value2;
	int fineDelay, i;

	/* Create the initial coarse-grained delay via the world's worst hash 
	   function, full of data dependencies and pipeline stalls */
	for( i = 0; i < value1; i++ )
		{
		/* Fill up both l and r with bits */
		l *= r + CONST1;
		r *= l + CONST2;

		/* Since we're about to divide by r, make sure that it's not zero, 
		   as well as adding a number of unpredictable branches to the code 
		   flow */
		while( !( r & 0x800 ) )
			r += CONST3;

		/* Perform a slow divide.  We actually apply it as a mod operation 
		   (still done via a divide instruction, only the remainder is 
		   what's preserved) since a divide would reduce l to a small 
		   integer value, and zero with 50% probability.  However we also 
		   have to be careful with the mod operation for the same reason as 
		   the problem with divides, at least half the time it'll be a 
		   no-op, so we shift it four bits to increase the chances of it 
		   doing something.  Finally, once we've done the divide, we refill 
		   l since the mod by a smaller amount has decreased its magnitude */
		l %= r >> 4;
		l += ROTL( r, 13 );

		/* As before, this time with r and l */
		while( !( l & 0x800 ) )
			l += CONST4;
		r %= l >> 4;
		r += ROTL( l, 13 );
		}

	/* Finish off with a fine-grained delay */
	fineDelay = ( int ) ( l & 0x7FFF );
	for( i = 0; i < fineDelay; i++ )
		{
		l += ROTL( r, 23 );
		r += ROTL( l, 23 );
		}

	return( ( r + l ) & 0x7FFF );
	}