GetText MO-Dateien können einen Hashtable zum schnellen Suchen von Übersetzungen enthalten. Ab der Version 0.6 des WPPP wird dieser auch verwendet (und ist zumindest ein klein wenig schneller als die binäre Suche), aber der Weg dahin war etwas schwierig. Schuld ist PHP.

Der GetText Hashtable verwendet HashPJW (PJW steht für Peter J. Weinberger). Hier der GetText Code aus hash-string.c:

unsigned long int __hash_string (const char *str_param)
{
	unsigned long int hval, g;
	const char *str = str_param;

	/* Compute the hash value for the given string. */
	hval = 0;
	while (*str != '\0')
	{
		hval <<= 4;
		hval += (unsigned char) *str++;
		g = hval & ((unsigned long int) 0xf << (HASHWORDBITS - 4));
		if (g != 0)
		{
			hval ^= g >> (HASHWORDBITS - 8);
			hval ^= g;
		}
	}
	return hval;
}

An sich ein simpler Hash-Algorithmus. Aber nicht in PHP. Denn er wird nicht von Haus aus unterstützt.

Problem eins: PHP kennt kein unsigned int. Da (eigentlich) nur Bit-Operationen ausgeführt werden, ist das zunächst kein Problem, aber das Endergebnis kann ein negativer Wert sein, wenn der unsigned Wert größer als 2147483647 wäre. Für alles darüber verwendet PHP float.

Die „Lösung“ für das Problem: printf bzw. sprintf. Da die Funktionen quasi eins zu eins aus C übernommen wurden, kann man mit ihnen auch PHP-Integer als unsigned behandeln. Der Format-Specifier %u interpretiert den entsprechenden Wert als unsigend int. Der so ausgegebene String lässt sich dann wieder als Zahl verwenden, von PHP intern als float repräsentiert.

return (float) sprintf('%u', $hval);

Oder besser:

if ($hval>=0)
	return $hval;
else
	return (float) sprintf('%u', $hval);

Problem gelöst.

Oder auch nicht. Denn trotz dieser Anpassung lieferte meine PHP-Version von HashPJW immernoch manchmal falsche Werte. Es hat eine ganze Weile gedauert, bis ich endlich die Ursache dafür gefunden hatte, womit wir zu Problem zwei kommen:

Die Bit-Shift-Operatoren von PHP arbeiten nicht logisch, sondern arithmetisch. D.h. ist das Vorzeichenbit gesetzt, bleibt es auch nach einem Rechts-Shift gesetzt (PHP scheint einfach den Wert durch zwei zu teilen). Soviel also zu „es werden ja nur Bit-Operationen ausgeführt, also macht es nichts, dass PHP kein unsigned kennt“.

Zum Glück lieferte der Kommentar auf php.net auch gleich die Lösung: Bei „negativem“ Wert das Vorzeichen-Bit löschen, dann verschieben und danach an entsprechender Stelle das (ehemals Vorzeichen-)Bit wieder setzen. Das sieht dann so aus:

function lshiftright($var,$amt)
{
	$mask = 0x40000000;
	if($var < 0)
	{
		$var &= 0x7FFFFFFF;
		$mask = $mask >> ($amt-1);
		return ($var >> $amt) | $mask;
	}
	return $var >> $amt;
}

Und siehe da, jetzt klappte es auch mit dem Hash-Wert-Berechnen. Das ganze (optimiert) sieht dann so aus:

function hashPJW ($key) {
	$hval = 0;
	for ($i = 0, key_len = strlen( $key ); $i < $key_len; $i++ ) {
		$hval = ( $hval << 4 ) + ord( $key{$i} );
		$g = $hval & 0xF0000000;
		if( $g !== 0 ){
			if ( $g < 0 )
				$hval ^= ( ( ($g & 0x7FFFFFFF) >> 24 ) | 0x80 ); // shift wordaround
			else
				$hval ^= ( $g >> 24 );
			$hval ^= $g;
		}
	}

	if ( $hval >= 0 )
		return $hval;
	else
		return (float) sprintf('%u', $hval); // unsigned workaround
}

Eines ist dann aber doch noch zu beachten: Werden im folgenden mit dem Hash-Wert Modulo-Berechnungen vorgenommen, dann ist entweder immer fmod statt des Modulo-Operators % zu verwenden, oder es muss anhand des Typs unterschieden werden.

Bei MO-Dynamic habe ich die Hash-Berechnung nicht als eigenständige Funktion sondern direkt an der entsprechenden Stelle im Code integriert. So konnte ich zusätzliche Modulo-Berechnungen direkt in der abschließenden $hval >= 0 Unterscheidung einbinden.

Bei alle dem ist es fast schon erstaunlich, dass trotz des ganzen Gefrickels die Hash-Suche einen Tick schneller ist als die binäre Suche.