[Frage in Fettdruck unten]

Wenn ein Assembler eine Binärcodierung generiert, muss er entscheiden, ob jeder Zweig lang oder kurz sein soll, wobei kurz besser ist, wenn möglich. Dieser Teil des Assemblers heißtBranch Displacement Optimization (BDO) -Algorithmus. Ein typischer Ansatz ist, dass der Assemblerall Wenn die Verzweigungscodierungen kurz sind (wenn sie unter einem bestimmten Schwellenwert liegen), werden alle Sprünge von Verzweigungen zu Longs, die nicht erreicht werden, iterativ erhöht. Dies kann natürlich dazu führen, dass andere Zweige in Weitsprünge umgewandelt werden. Daher muss der Assembler die Sprungliste so lange durchgehen, bis keine weitere Vergrößerung erforderlich ist. Dieser quadratische Zeitansatz scheint mir ein optimaler Algorithmus zu sein, aber angeblich ist BDO NP-vollständig und dieser Ansatz ist eigentlich nicht optima

Randall Hyde lieferte ein Gegenbeispiel:

                  .386 
                  .model  flat, syscall
00000000          .code
00000000          _HLAMain        proc


00000000  E9 00000016          jmpLbl:         jmp     [near ptr] target
00000005 = 00000005            jmpSize         =       $-jmpLbl
00000005  00000016 [                           byte    32 - jmpSize*2
dup
(0)
            00
           ]
0000001B                       target:
0000001B                       _HLAMain        endp
                                                end

Beim Hinzufügen des Teils in Klammern "[near ptr]" und Erzwingen einer 5-Byte-Codierung wird die Binärdatei kürzer, da das zugewiesene Array um das Doppelte der Sprunggröße kleiner ist. Wenn Sie also eine Sprungcodierung kürzer machen, ist der endgültige Code tatsächlich länger.

Dies scheint mir ein äußerst pathologischer Fall zu sein und nicht wirklich relevant, da die Verzweigungscodierungen immer noch kleiner sind. Es ist nur dieser bizarre Nebeneffekt auf einen nicht verzweigten Teil des Programms, der bewirkt, dass die Binärdatei größer wird. Da die Verzweigungskodierungen selbst noch kleiner sind, halte ich das nicht für ein gültiges Gegenbeispiel zum Algorithmus "klein anfangen".

Kann ich den Start-Small-Algorithmus als optimalen BDO-Algorithmus betrachten oder gibt es einenrealistisc Falls es nicht für alle Zweige eine minimale Codierungsgröße gibt?