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-железки. Ни одной защиты программы от копирования не пострадало.
Комментарии (63)
Mrrl
28.04.2015 12:45+1И как же в эти рассуждения вписываются команды
иlea eax, [edx+ecx]
?sar eax, 1Fh sub edx, eax
Без их объяснения трудно гарантировать, что это именно деление на 255, а не какая-нибудь более хитрая операция.
dmitrmax Автор
28.04.2015 13:52То что это не какая-нибудь хитрая более операция, а деление, я вам гарантирую. Сомнения могут быть только в том, что это 255 )
Цитрованный вами код — это и есть обработка напильником ) На самом деле она такая сложная потому что используется знаковое деление. Когда деление беззнаковое, то оно заменяется беззнаковым умножением, и там работа с результатом гораздо проще и понятнее (и быстрее). Необходимости использовать именно знаковое деление в данном коде абсолютно нет, оно произошло банально от того, что исходный код оперировал int'ами, а не unsigned. Кстати, если будете использовать целочисленное деление на константы (не степени двойки) в своем коде, то имейте ввиду, что беззнаковое будет работать быстрее. При этом упаси Вас Галилей, самому имплементировать такой трюк — это успешно делает любой современный компилятор.
Без приведенных вами операций (используя только сдвиг вправо на 7), получаемый результат может отличаться от реального на единицу. Это как бы аналог округления в арифметике с фиксированной запятой.
Вот здесь немножечко подробнее об этом. При этом прошу обратить внимание, что у автора похоже произошла ошибка и под делителем в некоторых местах надо понимать делимое.
dmitrmax Автор
28.04.2015 13:56Кстати, проверить это довольно просто. Достаточно написать функцию на С и скомпилировать с сохранением листинга ассемблера.
dmitrmax Автор
28.04.2015 14:06В кратце смотрите: 1/255 нельзя представить в фиксированной точке абсолютно точно. Придется обрезать по какому-то кол-ву разрядов. И останется некий хвост. Так вот этот хвост на самом деле тоже иногда играет роль, но он может сыграть исключительно в виде ±1 для некоторых значений делимого. Вот этот код, который вы процитировали и занимается этим.
Но для целей определения делителя, которая являлось целью данной статьи, это абсолютно не играет роли.Mrrl
28.04.2015 14:44+1Хвост на ±1 в этом примере (да и в других, которые я видел) не влияет, множитель подбирают так, чтобы для положительных чисел после сдвига результат был правильным. Второй блок команд используется, чтобы скорректировать значение для отрицательных чисел (для них и только для них результат будет на 1 меньше, чем нужно). А вот первая команда возникла из-за того, что 0x80808081 — отрицательное число, и умножение в действительности шло не на 128/255, а на -127/255.
mark_ablov
28.04.2015 14:25
mark_ablov
28.04.2015 13:59Я обычно под дебагером такие моменты пробегаю. быстрее, да и проще.
Даже зная о том, какая математика стоит за такими преобразованиями, вычисления могут занять больше времени, чем проверка.dmitrmax Автор
28.04.2015 14:03Допустим, в моем случае для любого размер буфера от 255 до 507, я бы всегда в результате данного кода получал 1, будь это деление на 255 или на 254. А мне нужно написать код, который в точности эмулирует поведение оригинала. Как же мне узнать, что в оригинале с помощью дебагера?
propell-ant
28.04.2015 14:54потом окажется, что знаковый тип там и не был нужен, а еще чуть позже — что делить надо было на 256, и весь код сворачивался бы до сдвига на 8 разрядов.
dmitrmax Автор
28.04.2015 15:03Знаковый тип там стопудово не нужен, на счёт деления на 256 — сомневаюсь. Девайсу передаётся размер буфера в одном байте, то есть максимум 255.
Вообще даже по ассемблеру видно, что код писан какой-то школотой ) Например, в функции передаётся буфер, в который надо прочитать данные с устройства. Вместо того, чтобы отдать этот же буфер функции, которая коммуницирует с девайсом, коммуницирующей функции отдается локальный буфер на стеке, а после вызова он копируется memcpy() в оригинальный. И драйвер похоже собран без оптимизации даже )
ZyXI
28.04.2015 23:17Вообще?то такие операции имеют смысл, если при некоторых условиях (например, если коммуницирующая функция завершается с ошибкой) нужно сохранить оригинальный буфер нетронутым, потому что нетронутое содержимое при этих условиях как?то используется. (Но в большинстве случаев можно и нужно всё?таки передать буфер, т.к. он изначально не содержит ничего полезного.)
Кстати, gcc без оптимизации всё равно переделевает деление. А clang использует деление без оптимизации. Pcc же использует деление даже с оптимизацией.dmitrmax Автор
28.04.2015 23:47> нужно сохранить оригинальный буфер нетронутым, потому что нетронутое содержимое при этих условиях как?то используется
Явно не тот случай. Явно. Поверьте )
Про когорту компиляторов: MS VC, ЕМНИП, заменяет умножением.
Mrrl
28.04.2015 20:26+1А вот что у меня получилось из одного деления. Что была за константа? :) (на входе и выходе ecx)
mov eax, 4198405 ; 00401005H mul ecx sub ecx, edx shr ecx, 1 add ecx, edx shr ecx, 9dmitrmax Автор
28.04.2015 20:501,047,552?
Хотя весьма странно выглядит постобработка. Для беззнакового умножения в ней нет нужды.Mrrl
28.04.2015 20:53Неправильно… Число небольшое, но за одно умножение+сдвиг не берётся. Мне было интересно, что сделает компилятор в этой ситуации.
dmitrmax Автор
28.04.2015 21:12Вообще интересный случай. Вы его случайно получили, или аналитически вывели?
Mrrl
28.04.2015 21:23+1Можно сказать, что аналитически. Я искал число X такое, чтобы K=2^N/X было чуть больше степени двойки (поэтому в качестве множителя пришлось бы брать число K, чуть большее 2^31), и чтобы остаток от деления 2^N на X был как можно меньше (тогда при округлении вверх мы проигрываем больше всего). Получилось, что X надо искать в виде 2^k-1, так, чтобы остаток от деления 31 на k был поменьше. Попробовал 1023 — получилось: для 2^32-5 ответ на единичку больше, чем надо.
dmitrmax Автор
29.04.2015 00:24+1На самом деле, сейчас осознал, что в статье ещё не хватает кусочка про остаток от деления.
tronix286
28.04.2015 21:01Прием известный. Но то были времена 386… Не думал, что сейчас кто-то так заморачивается на реальном текущем железе. Молодцы, чего уж там. Или это уже компиляторы научились?
Еще один известный трюк, как множить любое число на любое число быстрее, чем аппаратно, но не по таблице: www.reenigne.org/blog/multiplying-faster-with-squaresdmitrmax Автор
28.04.2015 21:02+2Да, это компиляторы научились. Речь идет о реверсе компилированных программ, а не писанных ручным асмом )
dmitrmax Автор
28.04.2015 21:06> но не по таблице
А что тогда вот это?
mov si,offset tableMrrl
28.04.2015 21:26Так это таблица квадратов. Но ведь не полная таблица умножения!
Правда, «быстрее, чем аппаратно» — это про слабые процессоры. У мощных умножение работает гораздо быстрее обращения к памяти.
forgotten
29.04.2015 09:38Я обычно сам в коде так и пишу
var subradius = 1 / radius; ... x = lon * subradius // вместо lon / radius
И читается хорошо, и на оптимизации компиляторов не надо полагаться.dmitrmax Автор
29.04.2015 11:31Только вы по факту имеете дело с floating point, а статья про integer'ы ) А у вас один сплошной var ))
forgotten
29.04.2015 11:34С интами мало что меняется.
int subradius = round(double(1 << 20) / radius) ... x = (lon * subradius) >> 20;
Цифра (20) выбирается из желаемой точности (ну и чтобы не было переполнения).encyclopedist
29.04.2015 12:56+1А это уже очень может оказаться антиоптимизацией. Компилятор сделает это за вас, да ещё и абсолютно точно, и с большой вероятностью более оптимально.
forgotten
29.04.2015 13:06А можно где-то почитать относительно «абсолютно точно»? В какой международной конвенции записано, что компилятор должен оптимизировать деление?
Что касается «более оптимально», то я это с трудом себе представляю. Компилятор абсолютно точно оптимизирует деление на константу, но не абсолютно точно оптимизирует умножение на неё?encyclopedist
29.04.2015 13:15Абсолютно точно в том смысле что результат будет точный, а не приближенный.
Хотя вероятно насчет оптимальности я наверное погорячился. Если мы допускаем погрешность, то и код может быть быстрее.forgotten
29.04.2015 13:16Ну это да. Выигрыш в производительности и достигается за счет утраты точности.
dmitrmax Автор
29.04.2015 13:36В примере в статье компилятор делает оптимизацию без утраты точности. Более того, в каментах уважаемый Mrrl показал, что не всё так тупо и линейно и ваши две строчки кода будут работать не всегда эквивалентно целочисленному делению.
forgotten
29.04.2015 13:42> В примере в статье компилятор делает оптимизацию без утраты точности.
А расскажите, пожалуйста, как можно поделить 1 на произвольное целое число без утраты точности? Мне казалось, что для чисел, не являющихся степенью двойки, этого сделать вовсе нельзя.dmitrmax Автор
29.04.2015 13:53Вы немного путаете тёплое с мягким. Поделить 1 без утраты точности на произвольное целое число действительно нельзя. Однако оптимизировать без потери точности целочисленное деление с остатком заменой на умножение и сдвиг(и) можно.
forgotten
29.04.2015 14:00-2Если и делимое, и делитель заранее известны — то да. Можно. Просто заменив на результат.
Если же один из параметров неизвестен, то такая оптимизация возможно только при знании диапазона возможных значений и того, и другого.
Вообще не всякую пару чисел можно делить друг на друга, даже без всяких оптимизаций в виде умножения на обратное.Mrrl
29.04.2015 14:07+2Диапазон значений делимого известен — от -2^31 до 2^31-1 для знаковых и от 0 до 2^32-1 для беззнаковых чисел. Множитель и сдвиг подбирают так, чтобы для всех чисел из этого диапазона результат был таким же, как и при обычном целочисленном делении.
dmitrmax Автор
29.04.2015 15:00> Если же один из параметров неизвестен, то такая оптимизация возможно только при знании диапазона возможных значений и того, и другого.
Казалось бы, откуда бы компилятору статически типизированного языка, узнать диапазон возможных значений переменной?ZyXI
30.04.2015 00:41Статическая типизация сама по себе никак не гарантирует знание диапозона возможных значений. Это возможно только в C, ассемблере и подобных им языкам, где нет ничего, кроме примитивных типов (указатели тут же) и структур из них, и нет переопределения операторов: диапозон возможных значений известен только из?за и примитивности типов, и статической типизации.
Если взять что?то вроде C++ или Rust, где в ряде случаев деление будет вызываться через таблицу методов, то никто ничего знать не будет. Но типизация у них тоже статическая.dmitrmax Автор
30.04.2015 12:14Out of context вы правы, но мы здесь ведем дискуссию о примитивных типах.
Но если вы хотите поговорить о высоком, то ежели оператор деления переопределен, то компилятору вообще нет нужды думать о том, как это деление оптимизировать: достаточно вызвать тело переопределенного оператора, а следовательно и на диапазон возможных значений можно забить болт. Но в конечном итоге всё, так или иначе, сведется к действиям над элементарными типами. И если там будет уже настоящее целочисленное деление на константу, то мы опять вернемся сюда.
dmitrmax Автор
29.04.2015 12:59Ээээ…
round(double(1 << 20) / radius)
Вы предлагаете оптимизорвать целочисленное деление, через деление даблов?forgotten
29.04.2015 13:04Если бы этот коммент написал не автор статьи, я бы предложил ему перечитать заголовок статьи. Однако теперь я в затруднении.
dmitrmax Автор
29.04.2015 13:33Давайте поговорим об этом?
forgotten
29.04.2015 13:37Ну давайте. В данном случае subradius — минус первая степень от той самой константы, на которую нужно делить. Её вычисление в любой схеме будет производиться честным делением (возможно, предрассчитанным). Выигрыш здесь за счёт того, что многократное деление на одно и тоже число заменяется комбинацией однократного деления и многократного умножения.
dmitrmax Автор
29.04.2015 13:41Если вы производите деление много-много раз, то безусловно такой выигрыш будет. Однако в вашем случае без дополнительных мер, возможна потеря точности для некоторых значений делителей.
В статье же описан код, сгенерированный реальным компилятором для однократного деления на целочисленную константу. Если бы делитель не был известной константой, то любые подобные оптимизации не дали бы никакого выигрыша. Хоть ручные, хоть автоматические.forgotten
29.04.2015 13:57Это какой-то фейспалм.
В данном случае оптимизация произошла за счёт того, что компилятор умеет предвычислять константы, т.е. производит фактический расчёт на этапе компиляции, а не исполнения. То же самое — сюрприз-сюрприз! — произойдёт и с предложенным мной кодом, компилятор точно так же рассчитает subradius и запишет его числом, а не выражением.
Оптимизировать же однократное деление — это вообще из пушки по воробьям стрелять, уж лет пятьдесят как такая оптимизация ни на что не влияет.
> Однако в вашем случае без дополнительных мер, возможна потеря точности для некоторых значений делителей.
А в вашем, будто, нет.
> Если бы делитель не был известной константой, то любые подобные оптимизации не дали бы никакого выигрыша.
Ничего подобного. Достаточно того, чтобы происходило два или более деления на одно и то же число.
Слушайте, завязывайте этот спор. Не стоит.encyclopedist
29.04.2015 14:18А в вашем, будто, нет.
Еще раз: тот способ, что рассматривается в статье, даёт абсолютно точный результат для любого агрумента (в пределах разрядности его типа, например от 0 до 2^32). В отличие от вашего упрощенного метода.
Скорее, это вам не стоит :-)
dmitrmax Автор
29.04.2015 14:56> То же самое — сюрприз-сюрприз! — произойдёт и с предложенным мной кодом, компилятор точно так же рассчитает subradius и запишет его числом, а не выражением.
В том-то и дело, что когда это делает компилятор, он делает это для разных констант немного по-разному. Я вам уже в третий раз пишу об этом, а вы всё ленитесь почитать каменты выше. Для разных констант существуют разные варианты. В частности, выше показано, что если делитель будет равен 1023, то ваш код будет работать, не так, как если бы Вы производили деление.
> > Однако в вашем случае без дополнительных мер, возможна потеря точности для некоторых значений делителей.
> А в вашем, будто, нет.
В нашем, это в каком? Когда это делает компилятор? Не будто, а 100% нет.
> Достаточно того, чтобы происходило два или более деления на одно и то же число.
Вы кажется читаете не внимательно. Я писал только об однократном делении. А о многократном я написал, что эффект будет.
Mrrl
29.04.2015 14:13+1Если делитель — не константа, но деление на одно и то же значение используется часто, можно было бы подобрать множитель и сдвиг во время выполнения, и, если удастся, действовать так же, код, созданный компилятором. Мешать будет только то, что нам нужна операция, эквивалентая (int)((__int64)a*b)>>32) — получение старшего слова произведения. Если она не выведена в качестве спецфункции, то либо придётся надеяться, что компилятор догадается обойтись одним умножением, либо мы проиграем.
Mrrl
29.04.2015 14:21+1Дополнение. Операция (int)((__int64)a*b)>>32) работает как надо (Visual Studio превратил её в один mul с дальнейшим использованием edx). Так что для делителей из какого-то диапазона оптимизация runtime возможна.
alexeibs
05.05.2015 22:54Я помню, были формулы и код калькулятора в официальном руководстве по оптимизации кода от AMD. А вообще в последних поколениях процессоров целочисление деление оптимизировали и необходимости в подобных трюках больше нет.
dmitrmax Автор
05.05.2015 23:02+1> Я помню, были формулы и код калькулятора в официальном руководстве по оптимизации кода от AMD.
В руководстве по оптимизации AMD есть код получению множителя из делителя, но не наоборот. Математика процесса там не объяснена.
> А вообще в последних поколениях процессоров целочисление деление оптимизировали и необходимости в подобных трюках больше нет.
Вы говорите про x86. Но мир не кончается на интеле. В других архитектурах такая оптимизация тоже имеет право на жизнь. Даже там, где вообще нет инструкции деления, например, но есть умножение. Заменить надо только мнемоники инструкций.
Fil
Кому интересна данная тема рекомендую «Алгоритмические трюки для программистов»
mark_ablov
Второе издание намного отличается от первого?
Fil
Я только 2-е читал, да и то очень выборочно. По ссылке в описании есть список добавленных глав.
mark_ablov
А, точно.
Да и по объему 500 страниц против тоненькой первой редакции.
lany
Ещё вот этот труд можно почитать (на английском).