Сообщение Re[2]: A Simple, Linear-Time Algorithm for x86 Jump Encoding от 30.11.2021 2:56
Изменено 30.11.2021 4:43 Эйнсток Файр
Тут вот есть мессага:
https://groups.google.com/g/alt.lang.asm/c/UokHytkRUMQ#a49af5f25dd15296
в которой говорится, что
In fact, there have been some mathematical proofs that show that this problem is "NP-Complete", which means that the only way to guarantee you've got an optimal solution is to try all possible combinations of short and long displacements in the object file and select the (or one of the) combination(s) that is the shortest.
А в работе по ссылке вводится допущение.
Собственно, во второй работе тоже ссылаются на существование доказательства.
Которое приводится где-то тут:
https://dl.acm.org/doi/10.1145/359460.359474
Тут вот есть мессага:
https://groups.google.com/g/alt.lang.asm/c/UokHytkRUMQ#a49af5f25dd15296
в которой говорится, что
In fact, there have been some mathematical proofs that show that this problem is "NP-Complete", which means that the only way to guarantee you've got an optimal solution is to try all possible combinations of short and long displacements in the object file and select the (or one of the) combination(s) that is the shortest.
А в работе по ссылке вводится допущение.
Собственно, во второй работе тоже ссылаются на существование доказательства.
Которое приводится где-то тут:
https://dl.acm.org/doi/10.1145/359460.359474
Но у них там особый случай использования памяти (сегментами), и поэтому:
The resulting algorithm, therefore, will not return the least fixed point, as it
might have too many long jumps.