elfhash int32 problem

[mindthegap]

Hi,

ich muß einen in c geschriebenen elfhash algo in php umsetzen. Das problem dabei ist daß in c mit uint gearbeitet wird, die uint stehen mir in php nicht zur verfügung.

bei dem elfhash werden die bits nach rechts und links geschobene... dabei gibt es konflikte mit dem vorzeichenbit beim linkschieben der bits...

jetzt habe ich leider nicht den wahnsinnsplan von php. das mit bcmath umzusetzen scheint mir recht aufwändig. ich könnte noch mit exec extern was ausführen.

was würdet ihr mir empfehlen.

den code kann ich euch gerne posten.

grüße dietmar

[Runnerle]

Ich weiß nicht wie gut der Ansatz ist, aber kannst du die Zahl nicht in eine Binärzahl umwandeln, und dann mit eigenen links bzw. rechts shift funktionen Operationen an der Zahl vornehmen ?

mfg

[Chriz]

Hallo Dietmar, willkommen im Forum,

bcmath ist vor allem langsam, aber poste doch einfach mal den Algorithmus und dann sehen wir weiter. Auch ganz hilfreich wäre es zu wissen, wie groß der Werte-Bereich von uint in C ist bzw. auf was für einem System das ganze dann (plattform-unabhängig?) geschrieben ist/lauffähig sein muss (32/64-Bit). crc32 (32!) ist beispielsweise in einigen PHP-Versionen noch abhängig vom System. Ein paar Referenzergebnisse zu bestimmten Eingaben würden das ganze dann noch vereinfachen.

[nikosch]

dabei gibt es konflikte mit dem vorzeichenbit beim linkschieben der bits

Das dürfte wohl eher der Wertebereich von INT sein. Vorzeichenbits wären wmir neu unter PHP.

aber kannst du die Zahl nicht in eine Binärzahl umwandeln

Diesen Datentyp gibt es in PHP nicht. DU arbeitest entweder mit Strings aus Nullen und Eisen ([MAN]decbin[/MAN]) oder eben mit der INT-Zahl (evtl. unter Angabe des Zahlensystems).

[Runnerle]

Diesen Datentyp gibt es in PHP nicht. DU arbeitest entweder mit Strings aus Nullen und Eisen ([MAN]decbin[/MAN]) oder eben mit der INT-Zahl (evtl. unter Angabe des Zahlensystems).

Ich hab das glaub etwas blöd ausgedrückt, ich meinte schon den typ string.

mfg

[mindthegap]

hallo,

erstmal danke für die bisherigen anregungen!

hier das script.

function ELFHash($str)  {

    $hash = 0;
    $x =  0;
    
    $n = strlen($str);
    
    for ($i = 0; $i < $n; $i++) {
            
            $hash = ($hash << 4) + ord($str[$i]);
        
             $x = $hash & 0xF0000000;
        
           if($x != 0) {
        
                $hash ^= ($x >> 24);   
            $hash &= ~$x;
        }
          
     }

    return $hash;
} 

hier noch ein paar kombinationen und dazu passende antworten:
"This is Elf hash test" 98082196
"The quick brown fox jumps over the lazy dog" 69733463
"Zajac Jan" 7680254

den c programmierer erreiche ich leider im moment nicht. ich habe das aber in actionscript 3 mit uint 32bit ans laufen bekommen.

hier noch die c funktion

UINT ElfHash(CString _str)
{
UINT rV = 0, x;
for (int i = 0; i < _str.GetLength() ; i++)
{
rV = (rV << 4) + (0xff & _str[i]);
x = rV & 0xF0000000;
if ( x )
rV ^= (x >> 24);
rV &= ~x;
};
return rV;
}

grüße

[Griffith]

So gehts:

function ELFHash($str)
{
    if( !is_string($str) ) return false;

    $hash = $x = 0;
    $n = strlen($str);

    for($i=0; $i<$n; $i++)
    {
        $hash <<= 4;
        $hash += ord($str[$i]);
        $x = $hash & 0xf0000000;
        if($x !== 0) {
            $hash ^= ($x >> 24) & 0xff;
            $hash &= ~$x;
        }
    }

    return $hash;
} 

Im Prinzip ist es auch egal, ob man die beiden letzten Anweisungen in der Schleife in einen If-Block packt oder nicht. Denn wenn $x=0, dann haben diese Anweisungen einfach keine Auswirkung.

function ELFHash($str)
{
    if( !is_string($str) ) return false;

    $hash = $x = 0;
    $n = strlen($str);

    for($i=0; $i<$n; $i++)
    {
        $hash <<= 4;
        $hash += ord($str[$i]);
        $x = $hash & 0xf0000000;
        $hash ^= ($x >> 24) & 0xff;
        $hash &= ~$x;
    }

    return $hash;
} 

Welche Variante man nimmt ist egal. Ich kann in der Ausführungszeit nicht wirklich einen Unterschied messen.

Der Fehler steckte nur in dieser Zeile: $hash ^= $x >> 24;
Aus irgendeinen Grund schiebt PHP bei negativen Ausgangzahlen lauter Einsen links ran, statt Nullen. Einfach eine Und-Verknüpfung anhängen und du bist das Problem los.

//EDIT: Parameter-Überprüfung hinzugefügt.

[ChrisB]

Aus irgendeinen Grund schiebt PHP bei negativen Ausgangzahlen lauter Einsen links ran, statt Nullen.

PHP: Bitwise Operators - Manual:

Right shifts have copies of the sign bit shifted in on the left, meaning the sign of an operand is preserved.

[Griffith]

Jopp, wunderte mich nur, weil es das erste mal war, dass ich so einer Regelung beim Shift-Right begegnet bin.

Ich bin nicht wirklich sicher, ob sich die Funktion auf alle Platformen (anderer Prozessor, evtl 64-Bit) so verhält, wie sie soll.
Eventuell ist es sinnvoll eine Klasse zu verwenden, die beim ersten Aufruf der Hash-Funktion diese testet.
Bei einem Fehler würde eine Exception geworfen.

elfhash.class.php

<?php

final class ELFHash
{
    private static $tested = false;

    public static function hash($str)
    {
        if( !is_string($str) ) return false;
        if( self::$tested !== true ) self::test();

        $hash = $x = 0;
        $n = strlen($str);

        for($i=0; $i<$n; $i++)
        {
            $hash <<= 4;
            $hash += ord($str[$i]);
            $x = $hash & 0xf0000000;
            if($x !== 0) {
                $hash ^= ($x >> 24) & 0xff;
                $hash &= ~$x;
            }
        }

        return $hash;  // 28-Bit Hash
    }

    private static function test()
    {
        self::$tested = true;

        $result = self::hash("This is Elf hash test") === 98082196;
        $result = $result && self::hash("The quick brown fox jumps over the lazy dog") === 69733463;
        $result = $result && self::hash("Zajac Jan") === 7680254;

        if($result !== true)
            throw new Exception("ELFHash::hash() liefert falsche Ergebnisse.");
    }
}

?>

beispiel.php

require "elfhash.class.php";

$hash = ELFHash::hash("Blubb"); 

[mindthegap]

hi,

auf das wäre ich niemals gekommen! danke. werde das gleich testen.

grüße