Ich möchte eine Crypto-Funktion von C nach Java portieren. Die Funktion muss in konstanter Zeit ausgeführt werden, daher sind keine bedingten Verzweigungen (und keine Tabellensuchen basierend auf x) zulässig.
Der ursprüngliche C-Code lautet:
%Vor%Also ist 'result' auf 1 gesetzt, wenn 'x == 7' und sonst auf 0. Die Variable 'result' wird dann in weiteren Berechnungen verwendet.
Ich suche jetzt nach der besten Möglichkeit, dies auf Java zu übertragen. Da in Java Ausdrücke zu Booleschen Werten und nicht zu ganzen Zahlen ausgewertet werden, muss man das obige mit Operatoren simulieren.
Ich verwende derzeit
%Vor%was für mich gut funktioniert, da mein x im Bereich {0, ..., 15} liegt. (Beachten Sie, dass die Shift-Funktion nur die unteren 5 Bits verwendet, so dass Sie falsche Positive erhalten, wenn x zu groß ist.)
Der Ausdruck wird millionenfach ausgewertet. Wenn es beispielsweise eine clevere Lösung gibt, die nur zwei anstelle von drei Operatoren verwendet, würde dies die Gesamtberechnung beschleunigen.
Die beste Option von @ Hosch250 ist der ternäre Operator. Werfen wir einen Blick auf den Assembler, der vom JIT-Compiler für diese Methode generiert wurde:
%Vor% Es hängt tatsächlich von der Profilerstellung ab. Wenn Ihr x ziemlich oft den Wert 7 hat, ist es wie folgt kompiliert:
Sehen Sie, dass ternary durch cmovne ersetzt wurde, was nicht die Verzweigungsinstruktion ist.
Wenn Sie andererseits in sehr seltenen Fällen 7 übergeben (z. B. einmal in 5000 Aufrufen), dann ist die Verzweigung hier:
Jetzt wird fast nie verzweigt, also ist es umso schneller, die Bedingung zu halten, da der CPU-Verzweigungs-Prädiktor fast immer korrekt ist. Beachten Sie, dass <slowpath> nicht nur return 1; ist, sondern auch das Zweigprofil aktualisiert. Wenn also das Muster während der Programmausführung geändert wird ( 7 wird häufiger angezeigt), wird die Methode erneut an die erste Version.
Versuchen Sie im Allgemeinen nicht, in so einfachen Fällen schlauer zu sein als der JIT-Compiler.
OK, ich denke, der Grund dafür ist folgender: Wenn die Ausführungszeit einer Krypto-Funktion von den Eingaben der Funktion abhängt, kann ein Angreifer durch Messen der Ausführungszeit Hinweise auf diese Eingaben erhalten. (Daher gelten die normalen Vorschläge "vorzeitige Optimierung" und "Versuch, den Compiler nicht zu überlisten" nicht wirklich.)
In Anbetracht dessen, hier sind meine Vorschläge:
Wenn x zur Kompilierzeit (oder JIT-Kompilierzeit) eine Konstante ist, besteht die Möglichkeit, dass der Code für beide optimiert wird
result = true; oder result = false;
Wenn x keine Konstante ist, aber es gibt einen kleinen Bereich möglicher Werte, dann wird wahrscheinlich einer der folgenden Ansätze funktionieren:
Das Problem ist, dass bei jedem denkbaren Ansatz der JIT-Compiler nicht-verzweigenden Code rechtlich in Verzweigungscode optimieren könnte. Wenn dies sicherheitskritisch ist, müssen Sie den tatsächlich ausgegebenen systemeigenen Code für jede zu zertifizierende Plattform untersuchen.
Der andere Ansatz ist:
Natürlich ist die andere Sache, die es zu beachten gilt, dass dies sowieso egal sein kann; z.B. Wenn result dann in einem anderen Teil der Crypto-Funktion verwendet wird, um zu entscheiden, ob der Ausführungspfad zu übernehmen ist.
Und ...
Der Ausdruck wird millionenfach ausgewertet. Wenn es beispielsweise eine clevere Lösung gibt, die nur zwei anstelle von drei Operatoren verwendet, würde dies die Gesamtberechnung beschleunigen.
Wenn das Ihre wahre Motivation ist ... dann ist mein Ratschlag Do not Bother . Dies ist eine vorzeitige Optimierung. Überlassen Sie es dem JIT-Compiler.
Da ist das Ziel,
zu erreichen %Vor%in einer Art algebraischer Art ohne Verzweigung,
%Vor%Aber das funktioniert nicht, weil die Rechtsverschiebung nur auf ein paar Bits maskiert ist. Was Sie also tun können, ist
%Vor%aber es ist immer noch maskiert für den Fall von -6 (alle Bits sind im Fall von -6 ^ 7 gesetzt), also,
%Vor%Also, wie viel langsamer ist es als eine Verzweigung bedingt? Obige Lösung, die bitCount () verwendet, um den gesamten Bereich int mehr als einmal zu vergleichen,
%Vor%Verzweigung verwenden, (x == 7? 1: 0),
%Vor%Es ist also nicht so schlimm, wenn man einen konstanten Zeitvergleich hat, der für jeden Wert funktioniert, 7 nur ein Beispiel. Ja, Integer.bitCount () ist auch eine konstante Zeit.
Unter Ausnutzung des extrem begrenzten Bereichs von x, der in [0,15] liegt, schlage ich vor, eine In-Register-Tabelle zu verwenden, die ein Bit pro Tabelleneintrag verwendet. In der Tabelle ist Bit i für die Eingänge festgelegt, die eine 1 und andernfalls null ergeben sollen. Dies bedeutet, dass unsere Tabelle die Literalkonstante 2 7 = 128:
ist %Vor%Tags und Links java performance bit-manipulation constant-time