Fragen? Antworten! Siehe auch: Alternativlos
0000003d <y>: 3d: 55 push %ebp 3e: 89 e5 mov %esp,%ebp 40: 8b 4d 08 mov 0x8(%ebp),%ecx 43: ba cd cc cc cc mov $0xcccccccd,%edx 48: 89 c8 mov %ecx,%eax 4a: f7 e2 mul %edx 4c: c1 ea 06 shr $0x6,%edx 4f: 89 d0 mov %edx,%eax 51: c1 e0 02 shl $0x2,%eax 54: 01 d0 add %edx,%eax 56: c1 e0 04 shl $0x4,%eax 59: 29 c1 sub %eax,%ecx 5b: 89 ca mov %ecx,%edx 5d: 89 d0 mov %edx,%eax 5f: 5d pop %ebp 60: c3 retWas tut diese Funktion? Hmm, eine Multiplikation mit einer Konstanten, dann ein paar Shifts. Komisch.
Nun, mir fiel auf, dass die Konstante merkwürdig aussah. Das ist die Art von Konstante, die auftaucht, wenn man eine Division als Multiplikation zu optimieren versucht.
Nehmen wir mal an, man will durch 3 teilen. Das ist äquivalent mit einer Multiplikation mit einem Drittel, aber Integer können keine Werte zwischen 0 und 1 abbilden, als geht 1/3 nicht.
Allerdings ist die Multiplikation auf Intel-Prozessoren so, dass man zwei 32-bit-Register multipliziert, und es kommt ein 64-bit-Wert raus.
Jetzt folgt mir mal unauffällig bei dem Gedankengang. Was ist denn ein Drittel, wenn man das Ergebnis mal 0x100000000 nimmt? Probieren wir doch mal aus:
$ gdb (gdb) p/x 0x100000000/3 $1 = 0x555555550x100000000 ist, wenn man es als 64-bit-Wert nimmt und die untere Hälfte wegschmeißt, 1. Seht ihr, wo ich hinwill? Um also einen Integer durch drei zu teilen, multipliziert man ihn mit 0x55555555 und schmeißt vom 64-bit-Ergebnis die untere Hälfte weg. Probieren wir mal aus:
(gdb) p (0x55555555*16)>>32 $2 = 0Das hat nicht geklappt, weil 0x55555555 ohne Typ-Dazusagen ein int ist, und der ist 32-bit (auch auf 64-bit Plattformen). Also ist auch das Ergebnis in C ein 32-bit Wert. Wenn ich den dann 32 Bit nach rechts shifte, bleibt nichts übrig. Wir müssen also dazusagen, dass wir einen 64-bit-Wert meinen.
(gdb) p (0x55555555ull*16)>>32 $3 = 5Und in der Tat, ein Drittel von 16 ist 5. Erfolg!
OK, also ein Drittel ist das hier schon mal nicht. Wenn man nach 0xcccccccd googelt, findet man heraus, dass das für Division mit 10 genommen wird. Probieren wir doch mal aus:
$ cat > t.c unsigned int div10(unsigned int x) { return x/10; } $ gcc -m32 -c t.c $ objdump -dr t.o […] 00000000 <div10>: 0: 55 push %ebp 1: 89 e5 mov %esp,%ebp 3: 8b 45 08 mov 0x8(%ebp),%eax 6: ba cd cc cc cc mov $0xcccccccd,%edx b: f7 e2 mul %edx d: 89 d0 mov %edx,%eax f: c1 e8 03 shr $0x3,%eax 12: 5d pop %ebp 13: c3 retA-Ha! In unserem Code oben war aber ein shr 6 und hier ist nur ein shr 3. Jedes zusätzlich nach Rechts geshiftete Bit ist eine Verdoppelung des Divisors, wir haben es hier also nicht Durch 10 sondern mit Durch 80 zu tun.
OK. Haben wir den Teil geklärt. Aber wieso shiftet der danach wieder zurück nach links? Und gucken wir mal genau hin. Der nimmt (x + (x << 2)) << 4. Das sieht irgendwie redundant aus, oder? Schauen wir doch mal, was das tut. Zwei nach links shiften ist Mal 4. x + x * 4 ist x * 5. Das ganze viermal nach Links geshiftet ist x * 5 * 16 oder … x * 80!
Wenn wir das mit obiger Erkenntnis zusammenführen, haben wir also ein x = x - (x / 80) * 80. Wer in Mathe aufgepasst hat, dem fällt auf, dass das äquivalent ist zu x % 80. Und jetzt die Auflösung:
unsigned int y(unsigned int x) { return x%80; }Diesen ganzen Obskuro-Code hat gcc für ein Modulo 80 erzeugt. Ohne Zutun des Users, und im Übrigen auch ohne Anschalten des Optimizers!
Wie kommt das, werdet ihr euch jetzt fragen? x86 hat doch eine prima Divisions-Instruktion, und die liefert auch den Rest zurück? Stimmt, aber die div-Instruktion kann schon mal 100 Taktzyklen verbraten, während obige Instruktionskette je nach Ziel-CPU deutlich unter 20 braucht.
Krass, wa?