Реверс-инжиниринг целочисленного деления на константу +33


Так бывает, что иногда реверсишь код, который занимается какой-то рутиной, не предполагающей каких-то серьезных вычислений и тут внезапно умножение на большую константу (поплачем, что на хабре нет хайлайтера для асма):

mov     edx, [ebp+end_of_buffer]
mov     eax, [ebp+src]
mov     ecx, edx
sub     ecx, eax
mov     edx, 80808081h
mov     eax, ecx
imul    edx
lea     eax, [edx+ecx]
mov     edx, eax
sar     edx, 7
mov     eax, ecx
sar     eax, 1Fh
sub     edx, eax
mov     eax, edx


Для тех, кто не знает ассемблера x86, поясню:

mov     edx, [ebp+end_of_buffer]
mov     eax, [ebp+src]
mov     ecx, edx
sub     ecx, eax        ; ecx = размер буфера
mov     edx, 80808081h  ; edx = -2 139 062 143
mov     eax, ecx        ; eax = ecx
imul    edx             ; знаковое умножение eax*edx
                        ;  с результатом в edx:eax

На первый взгляд, это удивительно, особенно для новичка, однако моя цель не озадачить, а объяснить, поэтому раскрываю карты: таким образом происходит оптимизация целочисленного деления на константу. Да-да. Целочисленное деление на заранее известную костанту можно заменить на целочисленное умножение на другую константу и обработкой результата напильником. Это будет быстрее, так как умножение занимает где-то в районе пяти тактов процессора, а деление около 25.

В гугле меня не забанили, но как найти исходный делитель я сходу не нашел, найдя при этом несколько руководств по оптимизации, где сообщалось как вычислить множитель для такой замены. Впрочем сообщалось в виде готового алгоритма, без пояснения стоящей за этим математикой.

Математика, связанная с возможностью подобной замены, заключается в замене делителя b на обратное число 1/b и умножения на него. Но как быть, если мы имеем дело с целочисленной арифетикой и 1/b будет окруляться до нуля всегда, когда b > 1? Очень просто: для этого необходимо представить число 1/b в виде числа с фиксированной точкой. При этом целая часть числа будет всегда нулём, а идущие после точки нули выкидываются до первой единицы. Количество выкинутых нулей запоминается, дабы сделать потом соотв. сдвиг.

И так. Как же понять на какую константу происходит деление в исходном коде? Проделаем обратную операцию: переведем двоичное число с фиксированной точкой в десятичный формат:
0x80808081 = 2^(-1) + 2^(-9) + 2^(-17) + 2^(-25) + 2^(-31) = A
Получаем обратное число B=1/A.

Далее в листинге мы видим, что происходит сдвиг вправо на 7 разрядов:

sar     edx, 7

Это и есть компенсация выкидывания лидирующих нулей. Она соответствует делению на 2^7 степени, то есть на 128. Делаем обратную операцию:

X = B*128 ~ 255.

Впрочем можно решить и по другому:
X ~ 1 / (2^(-1 — 7) + 2^(-9 — 7) + 2^(-17 — 7) + 2^(-25 — 7) + 2^(-31 — 7))

Округление в данном случае не страшно, так как целочисленное деление так же выполняется с округлением.

Таким образом, в моём случае авторы делили размер буфера на 255.

P.S.: В данном случае производилось исследование драйвера одной закрытой USB-железки. Ни одной защиты программы от копирования не пострадало.




К сожалению, не доступен сервер mySQL