32-Bit-Multiplikation ohne Vorzeichen auf 64-Bit, was zu undefiniertem Verhalten führt?

Lesezeit: 5 Minuten

Benutzeravatar von Jubatian
Jubatisch

Also habe ich ungefähr diesen Code:

uint32_t s1 = 0xFFFFFFFFU;
uint32_t s2 = 0xFFFFFFFFU;
uint32_t v;
...
v = s1 * s2; /* Only need the low 32 bits of the result */

Im Folgenden gehe ich davon aus, dass der Compiler keine vorgefassten Meinungen über den Bereich von haben konnte s1 oder s2die Initialisierer dienen oben nur als Beispiel.

Wenn ich dies auf einem Compiler mit einer Integer-Größe von 32 Bit kompiliert habe (z. B. beim Kompilieren für x86), kein Problem. Der Compiler würde einfach verwenden s1 und s2 wie uint32_t typisierte Werte (nicht in der Lage, sie weiter zu fördern), und die Multiplikation würde einfach das Ergebnis liefern, wie der Kommentar sagt (modulo UINT_MAX + 1 was in diesem Fall 0x100000000 ist).

Wenn ich dies jedoch auf einem Compiler mit einer ganzzahligen Größe von 64 Bit (z. B. für x86-64) kompiliert habe, kann es zu undefiniertem Verhalten kommen, was ich aus dem C-Standard ableiten kann. Integer-Promotion würde sehen uint32_t befördert werden kann int (64 Bit mit Vorzeichen), die Multiplikation würde dann versuchen, zwei zu multiplizieren int‘s, die, wenn sie zufällig die im Beispiel gezeigten Werte haben, einen ganzzahligen Überlauf verursachen würden, was ein undefiniertes Verhalten ist.

Liege ich damit richtig und wenn ja, wie würden Sie es auf vernünftige Weise vermeiden?

Ich habe diese Frage entdeckt, die ähnlich ist, aber C++ abdeckt: Was ist der beste C++-Weg, um vorzeichenlose Ganzzahlen sicher modular zu multiplizieren?. Hier möchte ich eine auf C anwendbare Antwort erhalten (vorzugsweise C89-kompatibel). Ich würde jedoch nicht in Betracht ziehen, eine schlechte 32-Bit-Maschine zu machen, die möglicherweise eine 64-Bit-Multiplikation ausführt, eine akzeptable Antwort (normalerweise in Code, in dem dies von Bedeutung wäre, könnte die 32-Bit-Leistung kritischer sein, da dies normalerweise die langsameren Maschinen sind).

Beachten Sie, dass das gleiche Problem für 16-Bit-Ints ohne Vorzeichen auftreten kann, wenn sie mit einem Compiler mit einer Int-Größe von 32 Bit kompiliert werden, oder für unsigned Chars, wenn sie mit einem Compiler mit einer Int-Größe von 16 Bit kompiliert werden (letzteres kann bei Compilern für 8-Bit-CPUs üblich sein). : Der C-Standard erfordert, dass Ganzzahlen mindestens 16 Bit lang sind, daher ist ein konformer Compiler wahrscheinlich betroffen).

  • int ist 32 Bit, selbst auf den meisten modernen 64-Bit-Architekturen en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models

    – phuklv

    18. November 2014 um 18:56 Uhr

  • Ach komm schon. Ist irgendetwas sogar in C definiert?

    – Harald

    18. November 2014 um 19:09 Uhr

  • @harold, ja: __STDC__ ist.

    – fuz

    18. November 2014 um 19:14 Uhr

  • @Tim: Ich habe es extra dafür gepostet, obwohl ich jetzt sogar merke, dass ich es eigentlich könnte brauchen durch ein ganzes Projekt zu schlendern, das so eingerichtet ist, dass es unabhängig von der Compiler-Int-Größe ist (derzeit sowohl auf 32- als auch auf 64-Bit gut funktioniert), um nach solchen Multiplikationen und anderen Dingen zu suchen, die ich für selbstverständlich hielt. Beweist, dass man nie alle Bestien kennen kann, die in den Schatten von C lauern …

    – Jubatisch

    18. November 2014 um 19:55 Uhr

  • @TimSeguine Die Beförderung von uint zu int ist akzeptabel, wenn einer der Operanden ein breiteres int ist, aber zwei uints, die in int konvertiert werden, sind böse.

    – 2501

    18. November 2014 um 19:56 Uhr


Der einfachste Weg, die Multiplikation in einem vorzeichenlosen Typ auszuführen, ist mindestens uint32_tund auch mindestens unsigned intsoll einen Ausdruck des Typs beinhalten unsigned int.

v = 1U * s1 * s2;

Diese konvertiert entweder 1U zu uint32_toder s1 und s2 zu unsigned intje nachdem, was für Ihre spezielle Plattform geeignet ist.

@Deduplicator kommentiert, dass einige Compiler, wo uint32_t ist schmaler als unsigned intkann vor der impliziten Konvertierung in der Zuweisung warnen und weist darauf hin, dass solche Warnungen wahrscheinlich unterdrückt werden können, indem die Konvertierung explizit gemacht wird:

v = (uint32_t) (1U * s1 * S2);

Sieht meiner Meinung nach aber etwas weniger elegant aus.

  • @Deduplicator Das passiert implizit, da v ist definiert als uint32_t.

    Benutzer743382

    18. November 2014 um 19:22 Uhr

  • @Deduplicator Ich bin mir nicht sicher, ob ich zustimme, dass es für einen Compiler unbedingt gut ist, davor zu warnen, aber ich stimme zu, dass es wahrscheinlich Compiler gibt, die davor warnen. Werde eine Anmerkung hinzufügen.

    Benutzer743382

    18. November 2014 um 19:24 Uhr

  • @hvd Das funktioniert, weil multiplizieren von links nach rechts ist, oder? Wenn 1U ganz rechts wäre, wäre die erste Multiplikation immer noch s1 * s2 und in int umgewandelt.

    – 2501

    18. November 2014 um 19:27 Uhr


  • @2501 Das ist richtig. 1U * s1 * s2 bedeutet immer (1U * s1) * s2und s1 * s2 * 1U bedeutet immer (s1 * s2) * 1U. Eine Alternative, die möglicherweise etwas besser lesbar ist, da der Leser nicht wissen muss, wie * bindet, wäre s1 * 1U * s2.

    Benutzer743382

    18. November 2014 um 19:29 Uhr

  • Oh Mist, jetzt muss ich auch plattformübergreifende Makros für die Multiplikation schreiben.

    – Groo

    22. August 2017 um 20:57 Uhr

Herzlichen Glückwunsch, Sie haben einen Reibungspunkt gefunden.

Ein möglicher Weg:

v = (uint32_t) (UINT_MAX<=0xffffffff
  ? s1 * s2
  : (unsigned)s1 * (unsigned)s2);

Wie auch immer, sieht aus wie das Hinzufügen einiger Typedefs zu <stdint.h> für Typen, die garantiert nicht kleiner sind als int wäre in ordnung ;-).

  • Braucht es überhaupt die Bedingung? Ich nehme an, es würde so einfach spielen OK v = (unsigned)s1 * (unsigned)s2;die Art von v würde sowieso für das richtige Abschneiden sorgen, während es bei 32 Bit immer noch eine 32-Bit-Multiplikation ist. Zumindest wenn ich ausnehme unsigned mindestens 32 Bit sein … Warte, sind solche Typen nicht bereits definiert?

    – Jubatisch

    18. November 2014 um 19:18 Uhr

  • Das Problem ist, int muss nicht mehr als 16 Bit haben … Und nein, solche Typen gibt es nicht.

    – Deduplizierer

    18. November 2014 um 19:19 Uhr


  • Äh, entschuldigen Sie die vage Formulierung, ich meinte einen 32-Bit-Int-Compiler … Nun, der Typ, den ich meine, ist uint_least32_t in stdint.hein geeigneter Ersatz könnte sogar für C89 vorhanden sein, denke ich.

    – Jubatisch

    18. November 2014 um 19:21 Uhr


  • Funktioniert das mit dem 1er-Komplement oder der Vorzeichengröße?

    – phuklv

    19. November 2014 um 8:04 Uhr

  • @LưuVĩnhPhúc: Für vorzeichenlose Zahlen sind diese Begriffe bedeutungslos.

    – Deduplizierer

    19. November 2014 um 16:42 Uhr

1400210cookie-check32-Bit-Multiplikation ohne Vorzeichen auf 64-Bit, was zu undefiniertem Verhalten führt?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy