Konsistente Hashing SHA1 Modulo-Operation

Question

Ich hoffe, dass einige Guru hier mich

Ich schreibe eine C/C++ Code Konsistente Hashing zu implementieren unter Verwendung von SHA1 als Hashing-Algorithmus helfen könnte.

muss ich den Betrieb des Moduls wie folgt umzusetzen:

0100 0011....0110 100 mod 0010 1001 = ?

Wenn der Divisor (0000 1111) eine Potenz von 2 pow(2,n) ist, dann wäre es leicht, als der letzte n Bit der Dividende ist das Ergebnis .

SHA1 Länge ist 160 Bit (oder 40 Hexa). Meine Frage ist, wie implementiere ich eine Modulo-Operation einer langen Bitfolge in eine andere beliebige Bitfolge?

Vielen Dank.

Answer 1

Als Benutzer stark weist darauf hin (unhöflicher als notwendig, denke ich) in Kommentaren, das ist nur eine lange Teilung in der Basis 2^32. Oder in der Basis 2, mit mehr Ziffern. Und Sie können den Algorithmus für lange Division verwenden, die Sie in der Schule für Basis 10 gelernt haben.

Es gibt schickere Algorithmen für die Division auf viel größere Zahlen, aber für Ihre Anwendung vermute ich, dass Sie es sich leisten können, es sehr einfach und ineffizient zu tun entlang der folgenden Zeilen (dies ist die Basis-2-Version, die zum Abzug aus nach links verschobenen Versionen des Nenners nur Beträge bis Sie nicht mehr so ​​tun können):

// Treat x,y as 160-bit numbers, where [0] is least significant and 
// [4] is most significant. Compute x mod y, and put the result in out. 
void mod160(unsigned int out[5], const unsigned int x[5], const unsigned y[5]) { 
    unsigned int temp[5]; 
    copy160(out, x); 
    copy160(temp, y); 
    int n=0; 
    // Find first 1-bit in quotient. 
    while (lessthanhalf160(temp, x)) { lshift160(temp); ++n; } 
    while (n>=0) { 
    if (!less160(out, temp)) sub160(out, temp); // quotient bit is 1 
    rshift160(temp); --n; // proceed to next bit of quotient 
    } 
} 

zur Klarstellung wird darauf hingewiesen, die oben ist nur eine grobe Skizze:

• Es kann voller Fehler sein.
• Ich habe nicht die Implementierungen der Building-Block-Funktionen wie less160 geschrieben.
• Eigentlich würden Sie wahrscheinlich nur den Code für diese Inline setzen, anstatt separate Funktionen zu haben. Zum Beispiel sind copy160 nur fünf Zuweisungen oder eine kurze Schleife oder eine memcpy.

Es könnte sicherlich effizienter gemacht werden; Beispielsweise könnte dieser erste Schritt besser dazu dienen, führende 0-Bits zu zählen und dann eine einzige Verschiebung durchzuführen, anstatt sich jeweils um eine Stelle zu verschieben. (Die rechte Verschiebung möchte das wahrscheinlich nicht, weil die Hälfte der Zeit nur eine einzige Schicht ist.)

Die "base-2^32" -Version mag zwar schneller sein, aber die Die Implementierung wird etwas komplizierter.