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

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

    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-железки. Ни одной защиты программы от копирования не пострадало.

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 63

      +7
      Кому интересна данная тема рекомендую «Алгоритмические трюки для программистов»
        0
        Второе издание намного отличается от первого?
          0
          Я только 2-е читал, да и то очень выборочно. По ссылке в описании есть список добавленных глав.
            0
            А, точно.
            Да и по объему 500 страниц против тоненькой первой редакции.
          0
          Ещё вот этот труд можно почитать (на английском).
          +1
          И как же в эти рассуждения вписываются команды
          lea     eax, [edx+ecx]
          
          и
          sar     eax, 1Fh
          sub     edx, eax
          
          ?

          Без их объяснения трудно гарантировать, что это именно деление на 255, а не какая-нибудь более хитрая операция.
            0
            То что это не какая-нибудь хитрая более операция, а деление, я вам гарантирую. Сомнения могут быть только в том, что это 255 )

            Цитрованный вами код — это и есть обработка напильником ) На самом деле она такая сложная потому что используется знаковое деление. Когда деление беззнаковое, то оно заменяется беззнаковым умножением, и там работа с результатом гораздо проще и понятнее (и быстрее). Необходимости использовать именно знаковое деление в данном коде абсолютно нет, оно произошло банально от того, что исходный код оперировал int'ами, а не unsigned. Кстати, если будете использовать целочисленное деление на константы (не степени двойки) в своем коде, то имейте ввиду, что беззнаковое будет работать быстрее. При этом упаси Вас Галилей, самому имплементировать такой трюк — это успешно делает любой современный компилятор.

            Без приведенных вами операций (используя только сдвиг вправо на 7), получаемый результат может отличаться от реального на единицу. Это как бы аналог округления в арифметике с фиксированной запятой.

            Вот здесь немножечко подробнее об этом. При этом прошу обратить внимание, что у автора похоже произошла ошибка и под делителем в некоторых местах надо понимать делимое.
              0
              Кстати, проверить это довольно просто. Достаточно написать функцию на С и скомпилировать с сохранением листинга ассемблера.
                0
                В кратце смотрите: 1/255 нельзя представить в фиксированной точке абсолютно точно. Придется обрезать по какому-то кол-ву разрядов. И останется некий хвост. Так вот этот хвост на самом деле тоже иногда играет роль, но он может сыграть исключительно в виде ±1 для некоторых значений делимого. Вот этот код, который вы процитировали и занимается этим.

                Но для целей определения делителя, которая являлось целью данной статьи, это абсолютно не играет роли.
                  +1
                  Хвост на ±1 в этом примере (да и в других, которые я видел) не влияет, множитель подбирают так, чтобы для положительных чисел после сдвига результат был правильным. Второй блок команд используется, чтобы скорректировать значение для отрицательных чисел (для них и только для них результат будет на 1 меньше, чем нужно). А вот первая команда возникла из-за того, что 0x80808081 — отрицательное число, и умножение в действительности шло не на 128/255, а на -127/255.
                  0
                  Я обычно под дебагером такие моменты пробегаю. быстрее, да и проще.
                  Даже зная о том, какая математика стоит за такими преобразованиями, вычисления могут занять больше времени, чем проверка.
                    0
                    Допустим, в моем случае для любого размер буфера от 255 до 507, я бы всегда в результате данного кода получал 1, будь это деление на 255 или на 254. А мне нужно написать код, который в точности эмулирует поведение оригинала. Как же мне узнать, что в оригинале с помощью дебагера?
                      0
                      Да, именно операции с потерей информации так не посмотришь.
                        0
                        Поэтому я и написал данную статью )
                    0
                    потом окажется, что знаковый тип там и не был нужен, а еще чуть позже — что делить надо было на 256, и весь код сворачивался бы до сдвига на 8 разрядов.
                      0
                      Знаковый тип там стопудово не нужен, на счёт деления на 256 — сомневаюсь. Девайсу передаётся размер буфера в одном байте, то есть максимум 255.

                      Вообще даже по ассемблеру видно, что код писан какой-то школотой ) Например, в функции передаётся буфер, в который надо прочитать данные с устройства. Вместо того, чтобы отдать этот же буфер функции, которая коммуницирует с девайсом, коммуницирующей функции отдается локальный буфер на стеке, а после вызова он копируется memcpy() в оригинальный. И драйвер похоже собран без оптимизации даже )
                        0
                        Вообще‐то такие операции имеют смысл, если при некоторых условиях (например, если коммуницирующая функция завершается с ошибкой) нужно сохранить оригинальный буфер нетронутым, потому что нетронутое содержимое при этих условиях как‐то используется. (Но в большинстве случаев можно и нужно всё‐таки передать буфер, т.к. он изначально не содержит ничего полезного.)

                        Кстати, gcc без оптимизации всё равно переделевает деление. А clang использует деление без оптимизации. Pcc же использует деление даже с оптимизацией.
                          0
                          > нужно сохранить оригинальный буфер нетронутым, потому что нетронутое содержимое при этих условиях как‐то используется

                          Явно не тот случай. Явно. Поверьте )

                          Про когорту компиляторов: MS VC, ЕМНИП, заменяет умножением.
                      +1
                      А вот что у меня получилось из одного деления. Что была за константа? :) (на входе и выходе ecx)
                      	mov	eax, 4198405				; 00401005H
                      	mul	ecx
                      	sub	ecx, edx
                      	shr	ecx, 1
                      	add	ecx, edx
                      	shr	ecx, 9
                      

                        0
                        1,047,552?

                        Хотя весьма странно выглядит постобработка. Для беззнакового умножения в ней нет нужды.
                          0
                          Неправильно… Число небольшое, но за одно умножение+сдвиг не берётся. Мне было интересно, что сделает компилятор в этой ситуации.
                            0
                            да, вы правы, это 1023
                              0
                              Вообще интересный случай. Вы его случайно получили, или аналитически вывели?
                                +1
                                Можно сказать, что аналитически. Я искал число X такое, чтобы K=2^N/X было чуть больше степени двойки (поэтому в качестве множителя пришлось бы брать число K, чуть большее 2^31), и чтобы остаток от деления 2^N на X был как можно меньше (тогда при округлении вверх мы проигрываем больше всего). Получилось, что X надо искать в виде 2^k-1, так, чтобы остаток от деления 31 на k был поменьше. Попробовал 1023 — получилось: для 2^32-5 ответ на единичку больше, чем надо.
                                  +1
                                  отличное упражнение )
                                    +1
                                    На самом деле, сейчас осознал, что в статье ещё не хватает кусочка про остаток от деления.
                            0
                            Прием известный. Но то были времена 386… Не думал, что сейчас кто-то так заморачивается на реальном текущем железе. Молодцы, чего уж там. Или это уже компиляторы научились?

                            Еще один известный трюк, как множить любое число на любое число быстрее, чем аппаратно, но не по таблице: www.reenigne.org/blog/multiplying-faster-with-squares
                              +2
                              Да, это компиляторы научились. Речь идет о реверсе компилированных программ, а не писанных ручным асмом )
                                0
                                > но не по таблице
                                А что тогда вот это?
                                    mov si,offset table
                                
                                  0
                                  Действительно o_O
                                    0
                                    Так это таблица квадратов. Но ведь не полная таблица умножения!
                                    Правда, «быстрее, чем аппаратно» — это про слабые процессоры. У мощных умножение работает гораздо быстрее обращения к памяти.
                                      0
                                      На неё бы целый сегмент памяти ушел! По тем временам роскошь не позволительная )
                                        0
                                        Зависит от диапазона множителей.
                                  0
                                  >> представить… в виде числа с фиксированной точкой
                                  Целое число это частный случай числа с фиксированной точкой. Просто она зафиксирована за младшим битом.
                                    0
                                    Математически — да. На практике — нет.
                                    0
                                    Я обычно сам в коде так и пишу
                                    var subradius = 1 / radius;
                                    ...
                                    x = lon * subradius // вместо lon / radius
                                    

                                    И читается хорошо, и на оптимизации компиляторов не надо полагаться.
                                      0
                                      Только вы по факту имеете дело с floating point, а статья про integer'ы ) А у вас один сплошной var ))
                                        0
                                        С интами мало что меняется.
                                        int subradius = round(double(1 << 20) / radius)
                                        ...
                                        x = (lon * subradius) >> 20;
                                        

                                        Цифра (20) выбирается из желаемой точности (ну и чтобы не было переполнения).
                                          +1
                                          А это уже очень может оказаться антиоптимизацией. Компилятор сделает это за вас, да ещё и абсолютно точно, и с большой вероятностью более оптимально.
                                            0
                                            А можно где-то почитать относительно «абсолютно точно»? В какой международной конвенции записано, что компилятор должен оптимизировать деление?
                                            Что касается «более оптимально», то я это с трудом себе представляю. Компилятор абсолютно точно оптимизирует деление на константу, но не абсолютно точно оптимизирует умножение на неё?
                                              0
                                              Абсолютно точно в том смысле что результат будет точный, а не приближенный.

                                              Хотя вероятно насчет оптимальности я наверное погорячился. Если мы допускаем погрешность, то и код может быть быстрее.
                                                0
                                                Ну это да. Выигрыш в производительности и достигается за счет утраты точности.
                                                  0
                                                  В примере в статье компилятор делает оптимизацию без утраты точности. Более того, в каментах уважаемый Mrrl показал, что не всё так тупо и линейно и ваши две строчки кода будут работать не всегда эквивалентно целочисленному делению.
                                                    0
                                                    > В примере в статье компилятор делает оптимизацию без утраты точности.

                                                    А расскажите, пожалуйста, как можно поделить 1 на произвольное целое число без утраты точности? Мне казалось, что для чисел, не являющихся степенью двойки, этого сделать вовсе нельзя.
                                                      0
                                                      Вы немного путаете тёплое с мягким. Поделить 1 без утраты точности на произвольное целое число действительно нельзя. Однако оптимизировать без потери точности целочисленное деление с остатком заменой на умножение и сдвиг(и) можно.
                                                        –2
                                                        Если и делимое, и делитель заранее известны — то да. Можно. Просто заменив на результат.

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

                                                        Вообще не всякую пару чисел можно делить друг на друга, даже без всяких оптимизаций в виде умножения на обратное.
                                                          +2
                                                          Диапазон значений делимого известен — от -2^31 до 2^31-1 для знаковых и от 0 до 2^32-1 для беззнаковых чисел. Множитель и сдвиг подбирают так, чтобы для всех чисел из этого диапазона результат был таким же, как и при обычном целочисленном делении.
                                                            0
                                                            > Если же один из параметров неизвестен, то такая оптимизация возможно только при знании диапазона возможных значений и того, и другого.

                                                            Казалось бы, откуда бы компилятору статически типизированного языка, узнать диапазон возможных значений переменной?
                                                              0
                                                              Статическая типизация сама по себе никак не гарантирует знание диапозона возможных значений. Это возможно только в C, ассемблере и подобных им языкам, где нет ничего, кроме примитивных типов (указатели тут же) и структур из них, и нет переопределения операторов: диапозон возможных значений известен только из‐за и примитивности типов, и статической типизации.

                                                              Если взять что‐то вроде C++ или Rust, где в ряде случаев деление будет вызываться через таблицу методов, то никто ничего знать не будет. Но типизация у них тоже статическая.
                                                                0
                                                                Out of context вы правы, но мы здесь ведем дискуссию о примитивных типах.

                                                                Но если вы хотите поговорить о высоком, то ежели оператор деления переопределен, то компилятору вообще нет нужды думать о том, как это деление оптимизировать: достаточно вызвать тело переопределенного оператора, а следовательно и на диапазон возможных значений можно забить болт. Но в конечном итоге всё, так или иначе, сведется к действиям над элементарными типами. И если там будет уже настоящее целочисленное деление на константу, то мы опять вернемся сюда.
                                              0
                                              Ээээ…
                                              round(double(1 << 20) / radius)
                                              


                                              Вы предлагаете оптимизорвать целочисленное деление, через деление даблов?
                                                0
                                                Если бы этот коммент написал не автор статьи, я бы предложил ему перечитать заголовок статьи. Однако теперь я в затруднении.
                                                  0
                                                  Давайте поговорим об этом?
                                                    0
                                                    Ну давайте. В данном случае subradius — минус первая степень от той самой константы, на которую нужно делить. Её вычисление в любой схеме будет производиться честным делением (возможно, предрассчитанным). Выигрыш здесь за счёт того, что многократное деление на одно и тоже число заменяется комбинацией однократного деления и многократного умножения.
                                                      0
                                                      Если вы производите деление много-много раз, то безусловно такой выигрыш будет. Однако в вашем случае без дополнительных мер, возможна потеря точности для некоторых значений делителей.

                                                      В статье же описан код, сгенерированный реальным компилятором для однократного деления на целочисленную константу. Если бы делитель не был известной константой, то любые подобные оптимизации не дали бы никакого выигрыша. Хоть ручные, хоть автоматические.
                                                        0
                                                        Это какой-то фейспалм.

                                                        В данном случае оптимизация произошла за счёт того, что компилятор умеет предвычислять константы, т.е. производит фактический расчёт на этапе компиляции, а не исполнения. То же самое — сюрприз-сюрприз! — произойдёт и с предложенным мной кодом, компилятор точно так же рассчитает subradius и запишет его числом, а не выражением.

                                                        Оптимизировать же однократное деление — это вообще из пушки по воробьям стрелять, уж лет пятьдесят как такая оптимизация ни на что не влияет.

                                                        > Однако в вашем случае без дополнительных мер, возможна потеря точности для некоторых значений делителей.

                                                        А в вашем, будто, нет.

                                                        > Если бы делитель не был известной константой, то любые подобные оптимизации не дали бы никакого выигрыша.

                                                        Ничего подобного. Достаточно того, чтобы происходило два или более деления на одно и то же число.

                                                        Слушайте, завязывайте этот спор. Не стоит.
                                                          0
                                                          А в вашем, будто, нет.


                                                          Еще раз: тот способ, что рассматривается в статье, даёт абсолютно точный результат для любого агрумента (в пределах разрядности его типа, например от 0 до 2^32). В отличие от вашего упрощенного метода.

                                                          Скорее, это вам не стоит :-)
                                                            0
                                                            > То же самое — сюрприз-сюрприз! — произойдёт и с предложенным мной кодом, компилятор точно так же рассчитает subradius и запишет его числом, а не выражением.

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

                                                            > > Однако в вашем случае без дополнительных мер, возможна потеря точности для некоторых значений делителей.

                                                            > А в вашем, будто, нет.

                                                            В нашем, это в каком? Когда это делает компилятор? Не будто, а 100% нет.

                                                            > Достаточно того, чтобы происходило два или более деления на одно и то же число.

                                                            Вы кажется читаете не внимательно. Я писал только об однократном делении. А о многократном я написал, что эффект будет.
                                                            +1
                                                            Если делитель — не константа, но деление на одно и то же значение используется часто, можно было бы подобрать множитель и сдвиг во время выполнения, и, если удастся, действовать так же, код, созданный компилятором. Мешать будет только то, что нам нужна операция, эквивалентая (int)((__int64)a*b)>>32) — получение старшего слова произведения. Если она не выведена в качестве спецфункции, то либо придётся надеяться, что компилятор догадается обойтись одним умножением, либо мы проиграем.
                                                              +1
                                                              Дополнение. Операция (int)((__int64)a*b)>>32) работает как надо (Visual Studio превратил её в один mul с дальнейшим использованием edx). Так что для делителей из какого-то диапазона оптимизация runtime возможна.
                                              0
                                              Я помню, были формулы и код калькулятора в официальном руководстве по оптимизации кода от AMD. А вообще в последних поколениях процессоров целочисление деление оптимизировали и необходимости в подобных трюках больше нет.
                                                +1
                                                > Я помню, были формулы и код калькулятора в официальном руководстве по оптимизации кода от AMD.

                                                В руководстве по оптимизации AMD есть код получению множителя из делителя, но не наоборот. Математика процесса там не объяснена.

                                                > А вообще в последних поколениях процессоров целочисление деление оптимизировали и необходимости в подобных трюках больше нет.

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

                                              Only users with full accounts can post comments. Log in, please.