Integerüberlauf bei Hash-Funktion

[cltom]

Hallo,

folgende Funktion wird seit 15+ Jahren in einem Projekt verwendet, ohne dass da je ein Problem aufgetaucht wäre. Es stammt aus der Hash-Library von Ciaran McCreesh. Man kann sicher darüber nachdenken, ob man die heute noch braucht, sie zu ersetzen würde allerdings einige bedeutende Änderungen mitbringen, die ich nicht (auf die Schnelle) lostreten wollte.

Nun wirft die Funktion aber einen Integer-Überlauf mit einem Argument, das seit ebenso 15 Jahren auf diese Funktion trifft.

Delphi-Quellcode:

  function HashThis(const s: string): cardinal;
  var
    h, g, i: cardinal;
  begin
    if (s = '') then
      raise EHashInvalidKeyError.Create('Key cannot be an empty string');
    h := $12345670;
    for i := 1 to Length(s) do begin
      h := (h shl 4) + ord(s[i]);
      g := h and $f0000000;
      if (g > 0) then
        h := h or (g shr 24) or g;
    end;
    result := h;
  end;

Augenscheinlich ist der Schritt

h := (h shl 4) + ord(s[i]); der Auslöser.

Was die Suche ergeben hat ist, dass in einem alten Backup des Projekts der Fehler nicht auftritt. Da waren Überlaufswarnungen deaktiviert, auch wenn ich dort aber die Überlaufswarnungen aktiviere, tritt kein Fehler auf!? Da kann ich die Funktion mit einem Problemstring schrittweise durchgehen, und es kommt kein Fehler.
Wenn man ein neues Projekt startet und einen Problemstring übergibt, tritt der Fehler ebenfalls auf.
Umgekehrt, wenn ich in der neuen Fassung des Projekts (mit neuer Projektdatei) die Überlaufswarnungen deaktiviere, kommt der Fehler dennoch (alles unter 32 bit debug, wo ich mal auch kompiliere).

Es liegt also am String und Projekteinstellungen, die sich mir noch nicht erschlossen haben.

Die eigentliche Frage: warum ergibt diese Funktion bei gewissen Strings einen Überlauf? Längere Strings sind anfälliger, aber ein einziger Buchstabe verschoben von einem "Problemstring" ergibt schon keinen Fehler mehr. Die Strings ändern ist keine echte Option (auch wenn es leicht wäre), da die Strings im Dateiformat zum speichern/öffnen verwendet werden - wieder größerer Umbau. Warum aber hängt das von irgendwelchen Projekteinstellungen ab?

hat jemand einen Blick, wie man an das reparieren könnte?

Danke!

[himitsu]

In "neuen" Delphi-Projekten sind, seit einer Weile im Delphi, standardmäßig die Index- und die Bereichsprüfung aktiv.

Bei sowas direkt in der betreffenden Unit dieses deaktivieren, wenn dort "absichtlich" mit Überläufen gerechnet wird, wie z.B. bei Verschlüsselung und Hash.
{$OVERFLOWCHECKS OFF}



Das Schlimme ist auch, dass es in der Hilfe "falsch" drin steht.
https://docwiki.embarcadero.com/RADS...ecking_(Delphi)

OK, für den Compiler ist es per Default off, aber in den neuen DPROJ nun per Default on.



Muß es unbedingt dieser Hash sein?
Im Delphi werden standardmäßig ein paar Hash-Funktionen mitgeliefert. (nutzt Delphi z.B. im TDictionary)

z.B. BobJenkinsHash in Generics.Defaults
Ich glaub im aktuellen Delphi steht dort ein Kommentar, dass es dafür nun auch irgendwo eine Klasse gibt.

[cltom]

Danke für Deine Rückmeldung!

Zitat von himitsu:

In "neuen" Delphi-Projekten sind, seit einer Weile im Delphi, standardmäßig die Index- und die Bereichsprüfung aktiv.
Bei sowas direkt in der betreffenden Unit dieses deaktivieren, wenn dort "absichtlich" mit Überläufen gerechnet wird, wie z.B. bei Verschlüsselung und Hash.
{$OVERFLOWCHECKS OFF}

Das Schlimme ist auch, dass es in der Hilfe "falsch" drin steht.
https://docwiki.embarcadero.com/RADS...ecking_(Delphi)

OK, für den Compiler ist es per Default off, aber in den neuen DPROJ nun per Default on.

Erklärt das, warum ich bei den Projektoptionen des alten (funktionierenden) Projekts die Überlaufsprüfung aktivieren kann und es trotzdem klappt als auch beim neuen Projekt die Überlaufsprüfung deaktivieren kann und es trotzdem nicht geht? bedeutet das auch, dass ich die nötigen Einstellungen gar nicht in den Projekteinstellungen selber ändern kann?

Zitat von himitsu:

Muß es unbedingt dieser Hash sein?
Im Delphi werden standardmäßig ein paar Hash-Funktionen mitgeliefert. (nutzt Delphi z.B. im TDictionary)

Das ist wohl sicher die Antwort, diesen Teil rauszunehmen. Im Kern wird das letztlich wie ein Dictionary verwendet. Als der Code geschrieben wurde, gab es keine Generics und ich hab den Teil bis dato nicht angerührt. Aber ja, das wird mal fällig. Vielleicht ist das Thema der Weckruf, das mal anzugehen. Schön wäre es, wenn es nicht ganz so erzwungen kommt und ich das mal testen kann.

[himitsu]

Direkt in der Unit (vor diesem Code oder irgendwo am Anfang) müsste es sich deakivieren lassen.

Zitat:

Erklärt das, warum ich bei den Projektoptionen des alten

"wo" aktivieren?

Es gibt ja mehrere Configs/Platforms und es muß in der Aktiven gesetzt/abgeschaltet sein. (oder in Einer irgendwo drüber, wenn es in der Linie nirgendwo ab dort überschrieben wurde)

[hoika]

Hallo,
ein paar Gedanken dazu.

s[i]
Du nimmst immer den gleichen "Problemstring" bei den gleichen Projekten?

Wann genau (bei welchem i) kommt der Überlauf,
welcher Buchstabe steht dort?

Bei den Projektoptionen fällt mir noch das Alignment ein,
was aber hier nicht der Grund sein sollte, aber naja ...

Die Projekte benutzen die gleiche Delphi-Version?

[cltom]

Zitat von hoika:

Hallo,
ein paar Gedanken dazu.

s[i]
Du nimmst immer den gleichen "Problemstring" bei den gleichen Projekten?

Wann genau (bei welchem i) kommt der Überlauf,
welcher Buchstabe steht dort?

Bei den Projektoptionen fällt mir noch das Alignment ein,
was aber hier nicht der Grund sein sollte, aber naja ...

Die Projekte benutzen die gleiche Delphi-Version?

Danke für die Überlegungen! Ja, hab gerade auf 12.1 aktualisiert. Die alten Projekt-Dateien funktionieren (offenbar mit anderen Einstellungen), ein neues Projekt mit genau der Funktion ergibt den Fehler.

Was meinst Du mit Alignment?

Ja, es ist immer der gleiche Problemstring, ich hab durch Probieren noch andere gefunden, es scheint aber zahlreiche/unbegrenzt Problemstrings zu geben: ich hab hier immer mehr vom Original-String durch x ersetzt, die werfen allesamt einen Fehler:

lbl_xxxxxx_xxxxxxxxxxxxxxx_xxx

je mehr x, desto früher in der Schleife kommt der Fehler. Der "Original-Problemstring" erzeugt erst an Stelle 30 den Fehler.

Dh im Grunde reicht schon

xxx_xxxxxx_x

Völlig eigen, dass das 15 Jahre lang nur aufgrund der Compiler-Projekt-Einstellungen unbemerkt geblieben ist

[himitsu]

Wie gesagt, in neueren Delphis sind in neuen Projekten diese Optionen jetzt aktiv.
Genauer ist es in der Basis-"Debug"-Config gesetzt.
Nach "check" in der DPROJ suchen.

Es macht auch einen Unterschied, ob das Projekt neu erstellt wird, oder ob die DPROJ gelöscht und anhand der DPR neu generiert wird.
Also allgemein, aber hierbei nicht, wenn in selber DelphiVersion, aber natürlich wenn uralte DPROJ gelöscht und in neuem Delphi neu generiert.

[Stevie]

Viele Algorithmen und gerade Hashfunktionen basieren darauf, dass ein Überlauf keinen Fehler erzeugt.
In der Zeile hier wird ja auf den laufenden Wert von h immer der Ordinalwert des aktuellen Zeichens addiert und das wird kann nunmal irgendwann in einer bestimmten Konstellation zu einem Overflow führen.

Ohne diese für diesen Code explizit abzuschalten, war das schon immer eine tickende Zeitbombe.

[cltom]

Zitat von Stevie:

Viele Algorithmen und gerade Hashfunktionen basieren darauf, dass ein Überlauf keinen Fehler erzeugt.
In der Zeile hier wird ja auf den laufenden Wert von h immer der Ordinalwert des aktuellen Zeichens addiert und das wird kann nunmal irgendwann in einer bestimmten Konstellation zu einem Overflow führen.

Ohne diese für diesen Code explizit abzuschalten, war das schon immer eine tickende Zeitbombe.

das ist wohl eine sehr treffende und letztlich entscheidende Zusammenfassung. Ganz glücklich war ich mit dem Ding nie, jetzt muss ich es wohl "schneller" (nach 15 Jahren) als geplant umbauen.

[himitsu]

Zitat von himitsu:

Bei sowas direkt in der betreffenden Unit dieses deaktivieren, wenn dort "absichtlich" mit Überläufen gerechnet wird, wie z.B. bei Verschlüsselung und Hash.
{$OVERFLOWCHECKS OFF}