Blog. Just Blog

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

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: 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.

Пример программы с исходным текстом (FASM)Пример программы с исходным текстом (FASM)

Entropy.Demo.zip (2,446 bytes)


Поделиться ссылкой ВКонтакте Поделиться ссылкой на Facebook Поделиться ссылкой на LiveJournal Поделиться ссылкой в Мой Круг Добавить в Мой мир Добавить на ЛиРу (Liveinternet) Добавить в закладки Memori Добавить в закладки Google
Просмотров: 4189 | Комментариев: 1

Внимание! Статья опубликована больше года назад, информация могла устареть!

Комментарии

Отзывы посетителей сайта о статье
Never (29.06.2012 в 11:11):
Неожиданно!

Добавить комментарий

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2017
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.21 сек. / MySQL: 2 (0.0043 сек.) / Память: 4.5 Mb
Наверх