Обратные инженерные математические функции

Question

Я перевожу некоторый ассемблерный код в код C, но у меня возникают проблемы со следующим кодом:

mov    $0x51eb851f,%edx
mov    %ecx,%eax
imul   %edx
sar    $0x5,%edx
mov    %edx,%edi
mov    %ecx,%eax
sar    $0x1f,%eax
sub    %eax,%edi
imul   $0x64,%edi,%eax
sub    %eax,%ecx

%ecx хранит наш параметр, который является типом int (мы можем назвать его x) , Я понимаю, что первые три шага на самом деле делают x / 100. Но я запутался в следующих шагах.

Была бы признательна за помощь.

Answer 1

g cc 9.3.1 для x86 gcc -O3 -S -m32 преобразует следующий C -код:

int foo(int x)
{
  return x%100;
}

в следующую сборку:

foo:
    movl    4(%esp), %ecx
    movl    $1374389535, %edx
    movl    %ecx, %eax
    imull   %edx
    movl    %edx, %eax
    movl    %ecx, %edx
    sarl    $5, %eax
    sarl    $31, %edx
    subl    %edx, %eax
    imull   $100, %eax, %eax
    subl    %eax, %ecx
    movl    %ecx, %eax
    ret

, что эффективно идентичен за исключением незначительного переупорядочения и соответствия ABI x86 для всей функции.

Answer 2

Вы правы, первые три шага выполняются x / 100 - более или менее путем умножения на 1/100 - , но деление не будет завершено, пока после sub %eax, %edi.

Итак, чтобы ответить на ваш вопрос о шагах, которые следуют за первыми тремя, вот фрагмент кода, аннотированный:

  mov    $0x51eb851f,%edx   # magic multiplier for signed divide by 100
  mov    %ecx,%eax          # %ecx = x
  imul   %edx               # first step of division signed x / 100
  sar    $0x5,%edx          # q = %edx:%eax / 2^(32+5)
  mov    %edx,%edi          # %edi = q (so far)
  mov    %ecx,%eax
  sar    $0x1f,%eax         # %eax = (x < 0) ? -1 : 0
  sub    %eax,%edi          # %edi = x / 100 -- finally
  imul   $0x64,%edi,%eax    # %eax = q * 100
  sub    %eax,%ecx          # %ecx = x - ((x / 100) * 100)

Примечание:

• Как правило, в этом методе деления на умножение умножение дает результат, который увеличивается на 2 ^ (32 + n) (для 32-разрядного деления). В этом случае n = 5 . Полный результат умножения составляет %edx:%eax, а отбрасывание %eax делится на 2 ^ 32 . sar $05, %edx делится на 2 ^ n - так как это деление со знаком, требуется сдвиг арифмети c.

• , к сожалению, для подписи деление сдвинутого %edx не совсем частное. Если дивиденд равен -ve (и учитывая, что делитель равен + ve), нужно добавить 1, чтобы получить частное. Так что sar $0x1f, %eax дает -1, если x <0 </em>, и 0 в противном случае. И sub %eax, %edi завершает деление.

  Этот шаг в равной степени может быть достигнут с помощью shr $0x1f, %eax и add %eax, %edi. Или add %eax, %eax и adc $0, %edi. Или cmp $0x80000000, %ecx и sbb $-1, %edi - что мне больше нравится, но, к сожалению, сохранение mov %ecx, %eax в наши дни ничего не спасает, и в любом случае cmp $0x80000000, %ecx - длинная инструкция: - (

• непонятно, почему это тасует частное q до %edi - если бы оно оставалось в %edx, оно все равно было бы там после imul $0x64,%edx,%eax.