Blog. Just Blog

Быстрый поиск

Введите фрагмент названия статьи для поиска

Замена деления умножением на Ассемблере

07.07.2013 | Категория: Образ мышления: Assembler | Автор: ManHunter

Замена деления умножением на Ассемблере

При написании на Ассемблере алгоритмов, использующих деление на константу, операции деления можно заменять на операции умножения. Зачем это надо? Дело в том, что процессор выполняет операцию умножения в несколько раз быстрее, чем операцию деления. К примеру, на умножение тратится 5-9 тактов процессора (знаковое умножение) или 4-8 (беззнаковое умножение), тогда как для деления необходимо 22-47 тактов (знаковое деление) или 17-41 тактов (беззнаковое деление). В высокооптимизированных алгоритмах, таких как шифрование, математические расчеты, архивация больших объемов данных, подсчет контрольных сумм и других подобных задачах, экономия каждого такта процессора может дать значительный прирост общей скорости работы программы.

В руководстве по оптимизации "AMD Athlon Processor x86 Code Optimization Guide" вопрос замены деления умножением расписан очень подробно. Рассмотрены частные случаи деления, такие как деление на степень двойки, описан выбор алгоритма для знакового и беззнакового деления и приведен код для вычисления вспомогательных корректирующих значений. Кроме этого, в руководстве описаны методы оптимизации и других математических операций. Даже если вы никогда не будете использовать на практике замену деления умножением, почитать о других способах оптимизации будет очень полезно.

Читать статью целиком »
Просмотров: 12005 | Комментариев: 4

Расчет энтропии на Ассемблере

29.06.2012 | Категория: Образ мышления: Assembler | Автор: ManHunter
Энтропия - это количество информации, приходящейся на одно элементарное сообщение источника, вырабатывающего статистически независимые сообщения. Говоря проще, это условный коэффициент, показывающий распределение уникальных элементов в массиве данных. На практике, к примеру, анализаторы исполняемых файлов используют подсчет энтропии секции кода как часть эвристики, для определения насколько упакованы или зашифрованы файлы. Чем выше показатель энтропии - тем выше вероятность, что данные уже упакованы или зашифрованы, и тем меньше они могут быть подвергнуты повторной компрессии. Математическая формула расчета энтропии следующая:


Формула расчета энтропии

Где p(i) - количество каждого уникального символа в строке, разделенное на общую длину строки. Программно это легко реализуется. Так, строка '012345' имеет показатель энтропии 2.58, строка '001122', так же как и '222200001111' - 1.58, а строка любой длины, состоящая из одинаковых символов, имеет нулевую энтропию. Я написал такую функцию на Ассемблере для расчета энтропии произвольного блока памяти:
  1. ;-----------------------------------------------------------------------
  2. ; Функция расчета энтропии блока памяти
  3. ; by ManHunter / PCL
  4. ; http://www.manhunter.ru
  5. ;
  6. ; Параметры:
  7. ; szStr - указатель на блок памяти для расчета
  8. ; dLen  - размер блока в байтах
  9. ; lpRes - указатель на приемник результата (DWORD)
  10. ;-----------------------------------------------------------------------
  11. proc    CalcEntropy szStr:DWORD, dLen:DWORD, lpRes:DWORD
  12.         locals
  13.         count   dd ?            ; Количество символов
  14.         cnt     rd 256          ; Счетчики символов
  15.         endl
  16.  
  17.         pusha
  18.  
  19.         ; Инициализация сопроцессора
  20.         finit
  21.  
  22.         ; Обнулить счетчики символов
  23.         lea     edi,[cnt]
  24.         mov     ecx,256
  25.         xor     eax,eax
  26.         rep     stosd
  27.  
  28.         ; Подсчет количества символов
  29.         mov     esi,[szStr]
  30.         mov     ecx,[dLen]
  31. .loc_count_chars:
  32.         xor     eax,eax
  33.         lodsb
  34.         shl     eax,2
  35.         inc     dword [cnt+eax]
  36.         loop    .loc_count_chars
  37.  
  38.         ; Начальное значение энтропии
  39.         fldz
  40.  
  41.         ; Расчет энтропии для каждого символа
  42.         mov     ecx,256
  43. .loc_calc_entr:
  44.         dec     ecx
  45.  
  46.         ; Получить количества символов
  47.         mov     eax,ecx
  48.         shl     eax,2
  49.         mov     eax,[cnt+eax]
  50.         ; Нулевые количества пропускаем
  51.         or      eax,eax
  52.         jz      @f
  53.  
  54.         mov     [count],eax
  55.  
  56.         fild    [dLen]  ; Длина строки
  57.         fild    [count] ; Количество символов
  58.         fdiv    st0,st1 ; P(i) = SUM(i)/total
  59.         fst     st1     ; Скопировать st0 в st1
  60.         fchs            ; Изменить знак
  61.         fxch    st1     ; Поменять местами регистры
  62.         fyl2x           ; H(i) = -P(i)*log2(P(i))
  63.         fadd    st1,st0 ; H = H+H(i)
  64.         ffree   st0
  65.         fincstp         ; Почистить стек
  66. @@:
  67.         ; Все символы обработали?
  68.         or      ecx,ecx
  69.         jnz     .loc_calc_entr
  70.  
  71.         ; Записать значение в ячейку памяти
  72.         mov     eax,[lpRes]
  73.         fstp    dword [eax]
  74.  
  75.         ffree   st0
  76.         fincstp         ; Почистить стек
  77.  
  78.         popa
  79.         ret
  80. endp
Функция самодостаточная, не требует никаких дополнительных переменных в сегменте данных. Единственная проблема может возникнуть в том случае, если количество каких-нибудь символов превысит размерность DWORD.

Читать статью целиком »
Просмотров: 5001 | Комментариев: 1

Преобразование строки в вещественное число на Ассемблере

31.05.2012 | Категория: Образ мышления: Assembler | Автор: ManHunter
Про преобразование строки в обычное число я уже писал, теперь задача посложнее - надо преобразовать строку в вещественное число с плавающей запятой (float). Для этого я написал вот такую функцию преобразования:
  1. ;------------------------------------------------------------
  2. ; Функция преобразования строки в вещественное число
  3. ; by ManHunter / PCL
  4. ; http://www.manhunter.ru
  5. ;
  6. ; Параметры:
  7. ;   lpStr - указатель на исходную строку в формате ASCIIZ
  8. ;   lpResult - указатель на переменную-приемник значения
  9. ; На выходе:
  10. ;   EAX = 1 - строка успешно преобразована
  11. ;   EAX = 0 - строка не может быть преобразована в число
  12. ;
  13. ; Примечание: переменная-приемник может иметь размер DWORD
  14. ; или QWORD, в зависимости от этого должна изменяться и
  15. ; функция (см. комментарии в конце кода). По умолчанию
  16. ; считается, что переменная имеет размер DWORD
  17. ;------------------------------------------------------------
  18. proc    string2float lpStr:DWORD, lpResult:DWORD
  19.         ; Локальные переменные
  20.         locals
  21.           dot    dd ?   ; Указатель на дробную часть
  22.           exp    dd ?   ; Указатель на экспоненту
  23.  
  24.           digit  dd ?   ; Цифра
  25.         endl
  26.  
  27.         pusha
  28.  
  29.         ; Проверка строки на валидность
  30.         mov     [digit],1
  31.  
  32.         mov     [exp],0
  33.         mov     [dot],0
  34.         mov     esi,[lpStr]
  35.         ; Минус или плюс может быть только в начале
  36.         cmp     byte [esi],'-'
  37.         je      @f
  38.         cmp     byte [esi],'+'
  39.         jne     .loc_chk_loop
  40. @@:
  41.         inc     esi
  42.  
  43.         ; После знака не может быть нуля
  44.         cmp     byte [esi],0
  45.         je      .loc_chk_error
  46. .loc_chk_loop:
  47.         ; В строке должны быть цифр, экспонента и не более одной точки
  48.         lodsb
  49.         or      al,al
  50.         jz      .loc_chk_complete
  51.         cmp     al,'e'
  52.         je      .loc_chk_exp
  53.         cmp     al,'E'
  54.         je      .loc_chk_exp
  55.         cmp     al,'.'
  56.         je      .loc_chk_dot
  57.         cmp     al,'0'
  58.         jb      .loc_chk_error
  59.         cmp     al,'9'
  60.         ja      .loc_chk_error
  61.         jmp     .loc_chk_loop
  62.  
  63. .loc_chk_dot:
  64.         ; Точка в строке уже есть?
  65.         cmp     [dot],0
  66.         ; Строка имеет некорректный формат
  67.         jne     .loc_chk_error
  68.  
  69.         ; Экспонента уже есть?
  70.         cmp     [exp],0
  71.         ; Строка имеет некорректный формат
  72.         jne     .loc_chk_error
  73.  
  74.         ; Указатель на дробную часть
  75.         mov     [dot],esi
  76.  
  77.         jmp     .loc_chk_loop
  78.  
  79. .loc_chk_exp:
  80.         ; Экспонента уже есть?
  81.         cmp     [exp],0
  82.         ; Строка имеет некорректный формат
  83.         jne     .loc_chk_error
  84.  
  85.         ; Указатель на начало экспоненты
  86.         mov     [exp],esi
  87.  
  88.         ; Сразу после экспоненты не может быть нуля
  89.         cmp     byte [esi],0
  90.         je      .loc_chk_error
  91.  
  92.         ; После экспоненты может быть знак
  93.         cmp     byte [esi],'-'
  94.         je      @f
  95.         cmp     byte [esi],'+'
  96.         jne     .loc_chk_loop
  97. @@:
  98.         inc     esi
  99.  
  100.         ; Сразу после минуса не может быть нуля
  101.         cmp     byte [esi],0
  102.         je      .loc_chk_error
  103.  
  104.         ; Проверить следующий символ
  105.         jmp     .loc_chk_loop
  106.  
  107. .loc_chk_error:
  108.         ; Строка не является числом
  109.         mov     [digit],0
  110.         jmp     .loc_ret
  111.  
  112. .loc_chk_complete:
  113.         ; Инициализация сопроцессора
  114.         finit
  115.  
  116.         ; Начальное значение числа
  117.         fldz
  118.  
  119.         ; Множитель и делитель
  120.         mov     [digit],10
  121.         fild    dword [digit]
  122.  
  123.         ; Запись значений до запятой
  124.         mov     esi,[lpStr]
  125.  
  126.         ; В начале строки минус?
  127.         cmp     byte [esi],'-'
  128.         je      @f
  129.         cmp     byte [esi],'+'
  130.         jne     .loc_before_dot
  131. @@:
  132.         inc     esi
  133.         ; Преобразование числа до запятой
  134. .loc_before_dot:
  135.         lodsb
  136.         ; Конец строки?
  137.         or      al,al
  138.         jz      .loc_complete
  139.  
  140.         cmp     al,'.'
  141.         je      .loc_complete_before_dot
  142.         cmp     al,'e'
  143.         je      .loc_exp
  144.         cmp     al,'E'
  145.         je      .loc_exp
  146.  
  147.         ; Очередная цифра
  148.         sub     al,'0'
  149.         movzx   eax,al
  150.         mov     [digit],eax
  151.  
  152.         ; Записать
  153.         fild    dword [digit]
  154.         fxch    st2
  155.         fmul    st0,st1
  156.         fxch    st2
  157.         fadd    st2,st0
  158.  
  159.         ffree   st0     ; Почистить стек
  160.         fincstp
  161.  
  162.         jmp     .loc_before_dot
  163.  
  164.         ; Преобразование дробной части числа
  165. .loc_complete_before_dot:
  166.         ; Дробная часть есть?
  167.         cmp     [dot],0
  168.         je      .loc_complete_after_dot
  169.  
  170.         ; Экспонента есть?
  171.         cmp     [exp],0
  172.         je      @f
  173.  
  174.         ; Указатель на начало экспоненты
  175.         mov     esi,[exp]
  176.         jmp     .loc_start_after_dot
  177. @@:
  178.         ; Иначе перенести указатель на конец строки
  179.         xor     ecx,ecx
  180.         dec     ecx
  181.         xor     eax,eax
  182.         mov     edi,esi
  183.         repne   scasb
  184.  
  185.         mov     esi,edi
  186.  
  187. .loc_start_after_dot:
  188.         std
  189.         dec     esi
  190.         dec     esi
  191.  
  192.         ; Дробная часть
  193.         fldz
  194.         fxch    st1
  195. .loc_after_dot:
  196.         lodsb
  197.         ; Конец дробной части?
  198.         cmp     al,'.'
  199.         je      .loc_complete_after_dot
  200.  
  201.         ; Очередная цифра
  202.         sub     al,'0'
  203.         movzx   eax,al
  204.         mov     [digit],eax
  205.  
  206.         ; Записать
  207.         fild    dword [digit]
  208.         fadd    st2,st0
  209.         fxch    st2
  210.         fdiv    st0,st1
  211.         fxch    st2
  212.  
  213.         ffree   st0     ; Почистить стек
  214.         fincstp
  215.  
  216.         jmp     .loc_after_dot
  217.  
  218. .loc_complete_after_dot:
  219.         ; Сбросить флаг направления
  220.         cld
  221.  
  222.         ffree   st0     ; Почистить стек
  223.         fincstp
  224.  
  225.         ; Сложить дробную и целую часть
  226.         fadd    st1,st0
  227.  
  228. .loc_exp:
  229.         ; Экспонента есть?
  230.         cmp     [exp],0
  231.         je      .loc_complete
  232.  
  233.         ; Получить значение экспоненты
  234.         xor     ecx,ecx
  235.  
  236.         mov     esi,[exp]
  237.         ; В начале строки минус?
  238.         cmp     byte [esi],'-'
  239.         je      @f
  240.         cmp     byte [esi],'+'
  241.         jne     .loc_start_exp
  242. @@:
  243.         inc     esi
  244. .loc_start_exp:
  245.         lodsb
  246.         or      al,al
  247.         jz      .loc_end_exp
  248.  
  249.         sub     al,'0'
  250.         movzx   eax,al
  251.         imul    ecx,10
  252.         add     ecx,eax
  253.  
  254.         jmp     .loc_start_exp
  255. .loc_end_exp:
  256.  
  257.         or      ecx,ecx
  258.         jz      .loc_complete
  259.  
  260.         ffree   st0     ; Почистить стек
  261.         fincstp
  262.  
  263.         mov     [digit],10
  264.         fild    dword [digit]
  265.  
  266.         ; Делить или умножать?
  267.         mov     esi,[exp]
  268.         cmp     byte [esi],'-'
  269.         je      .loc_exp_divide
  270.  
  271. .loc_exp_multiple:
  272.         fmul    st1,st0
  273.         loop    .loc_exp_multiple
  274.         jmp     .loc_complete
  275.  
  276. .loc_exp_divide:
  277.         fdiv    st1,st0
  278.         loop    .loc_exp_divide
  279.  
  280. .loc_complete:
  281.         ffree   st0     ; Почистить стек
  282.         fincstp
  283.  
  284.         ; В начале строки минус?
  285.         mov     esi,[lpStr]
  286.         cmp     byte [esi],'-'
  287.         jne     @f
  288.  
  289.         ; Изменить знак числа
  290.         fchs
  291. @@:
  292.         ; Записать значение в ячейку памяти
  293.         mov     eax,[lpResult]
  294.         ; Если требуется повышенная точность, то приемник
  295.         ; должен иметь размер QWORD, а следующую команду
  296.         ; надо заменить на fstp qword [eax]
  297.         fstp    dword [eax]
  298.  
  299.         ; Успешное преобразование
  300.         mov     [digit],1
  301. .loc_ret:
  302.         popa
  303.  
  304.         ; Результат преобразования
  305.         mov     eax,[digit]
  306.  
  307.         ret
  308. endp
Функция универсальная, понимает положительные и отрицательные, нормализованные и денормализованные числа, с любой мантиссой и экспонентой. Например, "123.45", "-1.67e+4", "99.999e-99", "45e004" и т.п. Также выполняется проверка на корректность исходной строки. Заведения дополнительных переменных в сегменте данных не требуется. Параметры вызова: lpStr - указатель на строку для преобразования, lpResult - указатель на переменную-приемник для записи результата, ее размер может быть DWORD или QWORD, в зависимости от желаемой точности результата. Соответственно, вы должны изменить команду (строка 297 в листинге) на fstp dword [eax] или fstp qword [eax].

Читать статью целиком »
Просмотров: 7330 | Комментариев: 12

Замена подстроки в строке на Ассемблере

28.03.2012 | Категория: Образ мышления: Assembler | Автор: ManHunter
Во всех языках высокого уровня среди функций работы со строками присутствуют функции замены заданной подстроки в строке. В Ассемблере такой функции нет, как нет ее и среди функций стандартных библиотек. Замена подстроки на строку такой же длины обычно сложностей не составляет, так как ее можно выполнить прямо в исходной строке без выделения дополнительной памяти. Замена на строку произвольной длины, в том числе и пустую, будет посложнее. Для этого я написал следующую функцию.
  1. ;-----------------------------------------------------
  2. ; Функция замены подстроки в строке
  3. ;-----------------------------------------------------
  4. ; lpSrc - указатель на исходную строку
  5. ; lpDst - указатель на буфер для полученной строки
  6. ; lpPattern - указатель на заменяемую подстроку
  7. ; lpReplace - указатель на строку для замены
  8. ; dNum - количество замен (0 - заменить все)
  9. ;-----------------------------------------------------
  10. proc    _replace lpSrc:DWORD, lpPattern:DWORD, lpReplace:DWORD,\
  11.                  lpDst:DWORD, dNum:DWORD
  12.  
  13.         pusha
  14.  
  15.         ; Указатель на буфер-приемник
  16.         mov     edx,[lpDst]
  17.  
  18.         ; Счетчик замен
  19.         xor     ebx,ebx
  20.  
  21.         ; Исходная строка не пустая?
  22.         mov     ecx,[lpSrc]
  23.         cmp     byte [ecx],0
  24.         jz      .loc_ret
  25.  
  26.         ; Заменяемая строка не пустая?
  27.         mov     eax,[lpPattern]
  28.         cmp     byte [eax],0
  29.         jz      .loc_copy_all
  30.  
  31. .loc_scan:
  32.         mov     esi,ecx
  33.         mov     edi,[lpPattern]
  34.  
  35.         ; Исходная строка закончилась?
  36.         cmp     byte [esi],0
  37.         je      .loc_end_replace
  38. @@:
  39.         ; Строки совпали с паттерном?
  40.         cmp     byte [edi],0
  41.         je      .loc_move_replace
  42.  
  43.         ; Символ совпадает с
  44.         lodsb
  45.  
  46.         ; Заменять все вхождения?
  47.         cmp     [dNum],0
  48.         je      .loc_skip_counter
  49.  
  50.         ; Уже заменили нужное количество?
  51.         cmp     ebx,[dNum]
  52.         je      .loc_move_one_char
  53. .loc_skip_counter:
  54.         cmp     al,byte [edi]
  55.         jne     .loc_move_one_char
  56.  
  57.         inc     edi
  58.         jmp     @b
  59.  
  60. .loc_move_replace:
  61.         ; Увеличить счетчик замен
  62.         inc     ebx
  63.  
  64.         mov     ecx,esi
  65.  
  66.         ; Записать заменяющую строку
  67.         mov     esi,[lpReplace]
  68.         mov     edi,edx
  69. @@:
  70.         lodsb
  71.         or      al,al
  72.         jz      .loc_scan
  73.         stosb
  74.         inc     edx
  75.         jmp     @b
  76.  
  77. .loc_move_one_char:
  78.         ; Скопировать один символ
  79.         mov     al,byte [ecx]
  80.         mov     byte [edx],al
  81.         inc     edx
  82.         inc     ecx
  83.         jmp     .loc_scan
  84.  
  85. .loc_end_replace:
  86.         ; Записать финальный 0 в строку
  87.         mov     byte [edx],0
  88.  
  89.         jmp     .loc_ret
  90. .loc_copy_all:
  91.         ; Просто скопировать исходную строку
  92.         mov     esi,[lpSrc]
  93.         mov     edi,[lpDst]
  94. @@:
  95.         lodsb
  96.         stosb
  97.         or      al,al
  98.         jnz     @b
  99. .loc_ret:
  100.         popa
  101.         ret
  102. endp
Функция самодостаточная, не использует никаких внешних функций и не требует для своей работы дополнительных переменных в памяти. Параметры: lpSrc - указатель на исходную строку в формате ASCIIZ, lpPattern - указатель на искомую подстроку в формате ASCIIZ, lpReplace - указатель на строку для замены в формате ASCIIZ, может быть пустая строка, lpDst - указатель на буфер-приемник полученной после замены строки, его размер должен быть зарезервирован с учетом замененных строк, dNum - количество замен, которое надо выполнить (0 - заменять все вхождения). Я постарался оптимизировать функцию замены по скорости, но, наверное, можно ее ускорить как-нибудь еще.

Читать статью целиком »
Просмотров: 9204 | Комментариев: 8

Несколько полезных функций на Ассемблере

21.05.2011 | Категория: Образ мышления: Assembler | Автор: ManHunter
За время программирования на Ассемблере у меня накопилось несколько полезных решений. Выделять под каждое из них отдельную статью не хочется, а держать под рукой пригодится. Поэтому все сложу сюда, по мере надобности буду пополнять.

Начну с функции очень быстрого копирования одного участка памяти в другой. Фишка в том, что основная часть строки копируется по 4 байта DWORD'ами, а остаток дописывается побайтно. Это дает нехилый выигрыш в скорости.
  1. ;-----------------------------------------------------
  2. ; Функция быстрого копирования участка памяти
  3. ;-----------------------------------------------------
  4. ; lpDst - указатель на приемник
  5. ; lpSrc - указатель на источник
  6. ; dSize - размер копируемого блока
  7. ;-----------------------------------------------------
  8. proc    _memcopy lpDst:DWORD, lpSrc:DWORD, dSize:DWORD
  9.         pusha
  10.  
  11.         ; Установить указатели на источник и приемник
  12.         cld
  13.         mov     edi,[lpDst]
  14.         mov     esi,[lpSrc]
  15.  
  16.         mov     ecx,[dSize]
  17.         push    ecx
  18.         ; Разделить на 4 и получить длину в DWORD
  19.         shr     ecx,2
  20.         ; Скопировать основную часть строки DWORD'ами
  21.         rep     movsd
  22.         pop     ecx
  23.         ; Получить остаток от деления на 4
  24.         and     ecx,3
  25.         ; Скопировать остаток строки байтами
  26.         rep     movsb
  27.  
  28.         popa
  29.         ret
  30. endp
Функция копирует любые данные, в том числе и нулевые байты, поэтому для нее обязательно указывать размер копируемого блока.

Читать статью целиком »
Просмотров: 24445 | Комментариев: 29

Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2020
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.1 сек. / MySQL: 3 (0.0239 сек.) / Память: 4.75 Mb
Наверх