Реверс-инжиниринг целочисленного деления на константу
Так бывает, что иногда реверсишь код, который занимается какой-то рутиной, не предполагающей каких-то серьезных вычислений и тут внезапно умножение на большую константу (поплачем, что на хабре нет хайлайтера для асма): 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 в виде числа с фиксированной точкой. При этом целая часть числа будет всегда нулём, а идущие после точки нули выкидываются до первой единицы. Количество выкинутых нулей запоминается, дабы сделать потом соотв. сдвиг.
И так. Как же понять на какую константу происходит деление в исходном коде? Проделаем обратную операцию: переведем двоичное число с фиксированной точкой в десятичный формат:0×80808081 = 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-железки. Ни одной защиты программы от копирования не пострадало.
