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


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

Где p(i) - количество каждого уникального символа в строке, разделенное на общую длину строки. Программно это легко реализуется. Так, строка '012345' имеет показатель энтропии 2.58, строка '001122', так же как и '222200001111' - 1.58, а строка любой длины, состоящая из одинаковых символов, имеет нулевую энтропию. Я написал такую функцию на Ассемблере для расчета энтропии произвольного блока памяти:

;-----------------------------------------------------------------------
; Функция расчета энтропии блока памяти
; by ManHunter / PCL
; http://www.manhunter.ru
;
; Параметры:
; szStr - указатель на блок памяти для расчета
; dLen  - размер блока в байтах
; lpRes - указатель на приемник результата (DWORD)
;-----------------------------------------------------------------------
proc    CalcEntropy szStr:DWORD, dLen:DWORD, lpRes:DWORD
        locals
        count   dd ?            ; Количество символов
        cnt     rd 256          ; Счетчики символов
        endl
 
        pusha
 
        ; Инициализация сопроцессора
        finit
 
        ; Обнулить счетчики символов
        lea     edi,[cnt]
        mov     ecx,256
        xor     eax,eax
        rep     stosd
 
        ; Подсчет количества символов
        mov     esi,[szStr]
        mov     ecx,[dLen]
.loc_count_chars:
        xor     eax,eax
        lodsb
        shl     eax,2
        inc     dword [cnt+eax]
        loop    .loc_count_chars
 
        ; Начальное значение энтропии
        fldz
 
        ; Расчет энтропии для каждого символа
        mov     ecx,256
.loc_calc_entr:
        dec     ecx
 
        ; Получить количества символов
        mov     eax,ecx
        shl     eax,2
        mov     eax,[cnt+eax]
        ; Нулевые количества пропускаем
        or      eax,eax
        jz      @f
 
        mov     [count],eax
 
        fild    [dLen]  ; Длина строки
        fild    [count] ; Количество символов
        fdiv    st0,st1 ; P(i) = SUM(i)/total
        fst     st1     ; Скопировать st0 в st1
        fchs            ; Изменить знак
        fxch    st1     ; Поменять местами регистры
        fyl2x           ; H(i) = -P(i)*log2(P(i))
        fadd    st1,st0 ; H = H+H(i)
        ffree   st0
        fincstp         ; Почистить стек
@@:
        ; Все символы обработали?
        or      ecx,ecx
        jnz     .loc_calc_entr
 
        ; Записать значение в ячейку памяти
        mov     eax,[lpRes]
        fstp    dword [eax]
 
        ffree   st0
        fincstp         ; Почистить стек
 
        popa
        ret
endp

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

Добавлено: 14 Сентября 2013 12:05:46 Добавил: Андрей Ковальчук Нравится 0

Добавить