Blog. Just Blog

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

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

Расчет CRC8 на Ассемблере

25.09.2011 | Категория: Образ мышления: Assembler | Автор: ManHunter
Контрольная сумма CRC8 применяется в основном для коротких сетевых пакетов и в микроконтроллерах. Из-за большой вероятности появления коллизий, использовать ее можно или для контроля целостности небольших объемах данных (оптимально - до 15 байт информации), или в случаях, когда возможность появления искажений исходных данных крайне мала. Алгоритм расчета CRC8 реализуется очень просто, работает очень быстро, из-за чего до сих пор находит свое применение. Первый вариант - прямой расчет.
  1. ;-----------------------------------------------------------------------
  2. ; Функция вычисления хеша CRC8
  3. ; by ManHunter / PCL
  4. ; http://www.manhunter.ru
  5. ;-----------------------------------------------------------------------
  6. ; Параметры:
  7. ;       lpData - указатель на строку
  8. ;       dSize  - длина строки
  9. ; На выходе:
  10. ;       AL = полученный хеш
  11. ;-----------------------------------------------------------------------
  12. proc    CRC8 lpData:DWORD, dSize:DWORD
  13.         push    ebx ecx edx esi edi
  14.  
  15.         CRC8_POLYNOM = 31h
  16.  
  17.         ; Инициализация
  18.         mov     al,0FFh
  19.  
  20.         ; Длина строки
  21.         cmp     [dSize],0
  22.         je      .loc_ret
  23.  
  24.         ; Указатель на начало строки
  25.         xor     ecx,ecx
  26. @@:
  27.         ; Получить символ из строки
  28.         mov     ebx,[lpData]
  29.         xor     al,byte [ebx+ecx]
  30.  
  31.         xor     esi,esi
  32. .loc_cycle:
  33.         test    al,80h
  34.         jz      .loc_1
  35.  
  36.         shl     al,1
  37.         xor     al,CRC8_POLYNOM
  38.         jmp     .loc_next
  39. .loc_1:
  40.         shl     al,1
  41. .loc_next:
  42.         inc     esi
  43.         cmp     esi,8
  44.         jb      .loc_cycle
  45.  
  46.         ; Следующий символ
  47.         inc     ecx
  48.         cmp     ecx,[dSize]
  49.         jb      @b
  50.  
  51. .loc_ret:
  52.         and     eax,0FFh
  53.  
  54.         pop     edi esi edx ecx ebx
  55.         ret
  56. endp
Этот вариант компактный, но не самый быстрый по скорости вычисления. Более скоростной алгоритм расчета CRC8 - с использованием заранее подготовленной таблицы.

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

Расчет хеша Adler-32 на Ассемблере

12.07.2011 | Категория: Образ мышления: Assembler | Автор: ManHunter
Adler-32 - хеш-функция, разработанная Марком Адлером, хорошо известным по его работам в области компрессии данных. Этот хеш используется в библиотеке zlib, соавтором которой и является Марк Адлер. По скорости работы Adler-32 превосходит CRC32, однако уступает ей по качеству обнаружения ошибок контрольной суммы, особенно на коротких строках. Есть несколько вариантов реализации алгоритма на разных языках и с разной степенью эффективности, мой вариант на Ассемблере такой:
  1. ;-----------------------------------------------------------------------
  2. ; Функция вычисления хеша Adler-32
  3. ; by ManHunter / PCL
  4. ; http://www.manhunter.ru
  5. ;-----------------------------------------------------------------------
  6. ; Параметры:
  7. ;       lpData - указатель на строку
  8. ;       dSize  - длина строки
  9. ; На выходе:
  10. ;       EAX = полученный хеш
  11. ;-----------------------------------------------------------------------
  12. proc    Adler32 lpData:DWORD, dSize:DWORD
  13.         push    ebx ecx edx esi edi
  14.  
  15.         ; Инициализация
  16.         mov     edi,1           ; s1 = 1
  17.         xor     esi,esi         ; s2 = 0
  18.  
  19.         ; Длина строки
  20.         cmp     [dSize],0
  21.         je      .loc_ret
  22.  
  23.         mov     ebx,65521       ; base
  24.         xor     ecx,ecx
  25. @@:
  26.         ; Получить символ из строки
  27.         mov     eax,[lpData]
  28.         movzx   eax,byte [eax+ecx]
  29.  
  30.         add     eax,edi         ; s1 = (s1 + buf[i]) % 65521
  31.         xor     edx,edx
  32.         div     ebx
  33.         mov     edi,edx
  34.  
  35.         add     edx,esi         ; s2 = (s2 + s1) % 65521
  36.         mov     eax,edx
  37.         xor     edx,edx
  38.         div     ebx
  39.         mov     esi,edx
  40.  
  41.         ; Следующий символ
  42.         inc     ecx
  43.         cmp     ecx,[dSize]
  44.         jb      @b
  45. .loc_ret:
  46.         mov     eax,esi        ; adler32 = (s2 << 16) + s1
  47.         rol     eax,16
  48.         add     eax,edi
  49.  
  50.         pop     edi esi edx ecx ebx
  51.         ret
  52. endp
Пример использования:
  1. ; Сегмент данных
  2. section '.data' data readable writeable  
  3. ...
  4. somedata db 'Yeah! I like Flat Assembler!',0 ; Исходные данные для хеширования
  5.  
  6. ; Сегмент кода
  7. section '.code' code readable executable
  8.         ...
  9.         ; Расчет длины строки. Для бинарных данных lstrlen лучше не использовать
  10.         invoke  lstrlen,somedata
  11.         ; Расчет Adler-32 
  12.         stdcall Adler32,somedata,eax
  13.         ; EAX = 82E0095Dh
Как указано в описании, самый эффективный по скорости способ расчета Adler-32 представлен авторским алгоритмом в исходниках библиотеки zlib. Но для небольших объемов данных вполне сгодится и приведенный выше вариант.

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

Расчет хеша SHA1 на Ассемблере

08.06.2011 | Категория: Образ мышления: Assembler | Автор: ManHunter
Алгоритм криптографического хеширования SHA1 (Secure Hash Algorithm 1) используется во многих криптографических приложениях и протоколах. В его основе лежат методы, очень похожие на MD5. В Интернете есть много реализаций этого алгоритма на разных языках программирования, но я не нашел ни одного нормального решения на Ассемблере. Пришлось разбираться самому и в результате у меня получилась достаточно быстрая функция расчета SHA1 участка памяти произвольной длины. Для работы в сегменте данных потребуются некоторые дополнительные переменные и массивы, они вынесены в глобальную область видимости, чтобы не загромождать код.
  1. section '.data' data readable writeable
  2.  
  3. SHA1_h0         dd ?  ; Переменные, в которых будет создан хеш SHA1
  4. SHA1_h1         dd ?
  5. SHA1_h2         dd ?
  6. SHA1_h3         dd ?
  7. SHA1_h4         dd ?
  8.  
  9. SHA1_a          dd ?  ; Вспомогательные переменные для промежуточных
  10. SHA1_b          dd ?  ; вычислений
  11. SHA1_c          dd ?
  12. SHA1_d          dd ?
  13. SHA1_e          dd ?
  14.  
  15. SHA1_W          rd 80  ; Массивы для промежуточных данных
  16. SHA1_Buff       rb 64
Я постарался сохранить оригинальные названия переменных, которые используются в описании алгоритма, так что с этим вопросов возникнуть не должно.

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

Расчет CRC16 на Ассемблере

30.11.2010 | Категория: Образ мышления: Assembler | Автор: ManHunter
CRC (Cyclic Redundancy Code - циклический избыточный код) - алгоритм расчета контрольной суммы для передаваемого сообщения, основанный на полиномиальной арифметике. Основная идея алгоритма CRC состоит в представлении сообщения в виде огромного двоичного числа, делении его на другое фиксированное двоичное число и использовании остатка от этого деления в качестве контрольной суммы. Получив сообщение, приемник должен выполнить аналогичное действие и сравнить полученный результат с принятой контрольной суммой. Сообщение считается достоверным, выполняется это равенство. Классический алгоритм CRC16 часто используется в архиваторах для контроля целостности данных служебных заголовков архивов, также его удобно использовать для сравнения строки с каким-либо значением, когда по соображениям безопасности сравниваемое значение не хранится в открытом виде. Для контроля целостности файлов функцию CRC16 лучше не использовать, так как из-за небольшой длины ее научились подделывать. Чтобы выполнить расчет CRC16 требуется сперва подготовить так называемую таблицу инициализации. В сегменте данных таблица резервируется как 256 слов, по одному word на каждый возможный байт:
  1. ; Сегмент данных
  2. section '.data' data readable writeable
  3.  
  4. ; Таблица инициализации для расчета CRC16
  5. crc16table rw 256
В классическом варианте для расчета CRC16 используется полином 0a001h, на его основе таблица слов заполняется значениями. Для этого используется следующая вспомогательная функция:
  1. ;-----------------------------------------------------------------------
  2. ; Функция создания таблицы инициализации для расчета CRC16
  3. ;-----------------------------------------------------------------------
  4. proc init_CRC16
  5.         push    eax ebx ecx edi
  6.  
  7.         ; Указатель на выделенную под таблицу память
  8.         mov     edi,crc16table
  9.         ; Расчитать значения для всех 256 слов
  10.         xor     edx,edx
  11. CRC16_Polynom:
  12.         mov     eax,edx
  13.         mov     ecx,8
  14. CRC16_NL:
  15.         shr     ax,1
  16.         jae     CRC16_NoXOR
  17.         ; Magic Number!
  18.         xor     ax,0a001h
  19. CRC16_NoXOR:
  20.         loop    CRC16_NL
  21.         ; Записать значение в таблицу полиномов
  22.         stosw
  23.         inc     edx            ; Счетчик +1
  24.         cmp     edx,256        ; Всю таблицу сгенерировали?
  25.         jne     CRC16_Polynom  ; Нет, работаем дальше
  26.  
  27.         ; Восстановить измененные регистры
  28.         pop     edi ecx ebx eax
  29.         ret
  30. endp
Таблица инициализации получается всегда одинаковой (при условии неизменности полинома), так что ее можно даже не раcчитывать, а хранить в виде массива констант. Если требуется таблица инициализации CRC16 отдельно для использования в других проектах или языках программирования, то она приведена ниже. Для некоторых других разновидностей алгоритма CRC16, например, CRC-CCITT или CRC16-IBM, полином будет другим, и, соответственно, таблица также будет другой.

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

Расчет CRC32 на Ассемблере

27.04.2009 | Категория: Образ мышления: Assembler | Автор: ManHunter
Алгоритм вычисления контрольной суммы (CRC, англ. cyclic redundancy code, циклический избыточный код) - способ цифровой идентификации некоторой последовательности данных, который заключается в вычислении контрольного значения ее циклического избыточного кода. Алгоритм CRC32 основан на примитивном полиноме 0EDB88320h и применяется в архиваторах, системах шифрования, протекторах исполняемых файлов и многих других программах. Он прост в реализации и с большой вероятностью может подтверждать неизменность данных, причем чем меньше размер контролируемой информации, тем выше эта вероятность. Для расчета CRC32 требуется сперва подготовить так называемую таблицу инициализации. В сегменте данных таблица резервируется как 256 двойных слов, по одному dword на каждый возможный байт:
  1. ; Сегмент данных
  2. section '.data' data readable writeable
  3.  
  4. ; Таблица инициализации для расчета CRC32
  5. crc32table rd 256
После этого таблица заполняется данными, это делается при помощи следующей функции. Она вызывается только один раз до первого вызова функции расчета CRC32.
  1. ;-----------------------------------------------------------------------
  2. ; Функция создания таблицы инициализации для расчета CRC32
  3. ;-----------------------------------------------------------------------
  4. proc init_CRC32
  5.         push    eax ebx ecx edi
  6.  
  7.         mov     edi,crc32table      ; Указатель на выделенную под таблицу память
  8.         xor     ebx,ebx             ; Расчитать значения для всех 256 байт
  9. calc_crc32table:
  10.         mov     eax,ebx
  11.         mov     ecx,8
  12. do_polynom:
  13.         shr     eax,1               ; Проверить четность байта
  14.         jnc     @f                  ; XOR выполняется только если байт нечетный
  15.         xor     eax,0EDB88320h 
  16. @@:
  17.         loop    do_polynom          ; Следующий бит
  18.  
  19.         stosd                       ; Записать полученный dword в таблицу
  20.         inc     ebx
  21.         cmp     ebx,256
  22.         jb      calc_crc32table     ; Следующий байт
  23.  
  24.         pop     edi ecx ebx eax
  25.         ret
  26. endp
Таблица инициализации получается всегда одинаковой (при условии неизменности полинома), так что ее можно даже не расчитывать, а хранить в виде массива констант. Если требуется таблица инициализации CRC32 отдельно для использования в других проектах или языках программирования, то она приведена ниже. Под синтаксис вашего языка программирования адаптируйте ее самостоятельно.

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

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