Алгоритм Верхеффа на Ассемблере
Алгоритм Верхеффа на Ассемблере
В мире цифровых идентификаторов, где человек вручную вводит длинные последовательности цифр, ошибки неизбежны. При этом даже одна опечатка может привести к финансовым потерям, особенно если речь идет о номерах банковских карт, персональных идентификаторах или серийных номерах оборудования. Чтобы обнаруживать такие ошибки, а в идеале и предотвращать их последствия, были разработаны специальные алгоритмы контрольных сумм. Среди них особенно выделяется алгоритм Верхеффа, предложенный голландским математиком Якобом Верхеффом (Jacobus Verhoeff) в 1969 году.
До появления алгоритма Верхеффа большинство систем использовали простые контрольные суммы: сложение цифр по модулю 10 или алгоритм Луна (применяемый в номерах кредитных карт). В отличие от более известного алгоритма Луна (Luhn), который пропускает некоторые типы ошибок (например, перестановку соседних цифр "09" <--> "90"), алгоритм Верхеффа обнаруживает 100% одиночных ошибок и 100% транспозиций соседних цифр, а также многие другие распространенные виды человеческих ошибок.
Миллионы документов со старыми номерами будут действительны еще годы и десятилетия, а для систем, где важен человеческий ввод, алгоритм остается актуальным. Современные системы все чаще используют криптографические подписи вместо контрольных сумм. Но там, где нужна легкость проверки "на глаз" или в уме, Верхефф по-прежнему вне конкуренции.
Вот пример реализации алгоритма Верхеффа на языке Ассемблер для проверки контрольной цифры. Например: проверка паспорта старого образца. Это целое 10-значное число, часто его проверяют как комбинацию серия (4 цифры) + номер (6 цифр) как. Последняя 10-я цифра - контрольная, находится в номере бланка, но проверяется вся связка. При замене паспорта номер меняется, но алгоритм проверки остается тем же, математическая константа в меняющемся документообороте.
Code (Assembler) : Убрать нумерацию
- ;---------------------------------------------
- ; Компактная проверка Верхеффа
- ; Copyright (C) ManHunter / PCL
- ; https://www.manhunter.ru
- ;---------------------------------------------
- ; Параметры:
- ; lpData - указатель на строку
- ; На выходе:
- ; EAX = 1 - VALID
- ; EAX = 0 - INVALID
- ;---------------------------------------------
- proc verhoeff_check lpData:DWORD
- push edx ebx ecx esi edi
- ; Указатель на входную строку
- mov esi,[lpData]
- ; Перейти на окончание строки
- mov edi,esi
- .find_end:
- cmp byte[edi],0
- je @f
- inc edi
- jmp .find_end
- @@:
- ; На последнюю цифру
- dec edi
- xor eax,eax
- xor ecx,ecx
- .loc_loop:
- cmp edi,esi
- ; Вышли за начало
- jb .loc_done
- ; Проверить только символы 0..9
- mov bl,[edi]
- cmp bl,'0'
- jb .loc_skip
- cmp bl,'9'
- ja .loc_skip
- sub bl,'0'
- ; pos*10 + digit
- movzx edx,cl
- ; pos*8
- shl edx,3
- ; pos*10
- lea edx,[edx+ecx*2]
- ; digit
- movzx ebx,bl
- ; pos*10 + digit
- add edx,ebx
- ; p[pos][digit]
- mov dl,[.p_table+edx]
- ; d[c][p]
- movzx ebx,al
- ; c*8
- shl ebx,3
- ; c*10
- lea ebx,[ebx+eax*2]
- movzx eax,dl
- ; c*10 + p
- add ebx,eax
- mov al,[.d_table+ebx]
- ; pos = (pos+1) & 7
- inc cl
- and cl,7
- .loc_skip:
- ; Следующая цифра слева
- dec edi
- jmp .loc_loop
- .loc_done:
- cmp al, 0
- sete al
- pop edi esi ecx ebx edx
- ret
- ; Перестановка p[8][10]
- .p_table:
- db 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
- db 1, 5, 7, 6, 2, 8, 3, 0, 9, 4
- db 5, 8, 0, 3, 7, 9, 6, 1, 4, 2
- db 8, 9, 1, 6, 0, 4, 3, 5, 2, 7
- db 9, 4, 5, 3, 1, 2, 6, 8, 7, 0
- db 4, 2, 8, 6, 5, 7, 3, 9, 0, 1
- db 2, 7, 9, 3, 8, 0, 6, 4, 1, 5
- db 7, 0, 4, 6, 9, 1, 3, 2, 5, 8
- ; Умножение d[10][10]
- .d_table:
- db 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
- db 1, 2, 3, 4, 0, 6, 7, 8, 9, 5
- db 2, 3, 4, 0, 1, 7, 8, 9, 5, 6
- db 3, 4, 0, 1, 2, 8, 9, 5, 6, 7
- db 4, 0, 1, 2, 3, 9, 5, 6, 7, 8
- db 5, 9, 8, 7, 6, 0, 4, 3, 2, 1
- db 6, 5, 9, 8, 7, 1, 0, 4, 3, 2
- db 7, 6, 5, 9, 8, 2, 1, 0, 4, 3
- db 8, 7, 6, 5, 9, 3, 2, 1, 0, 4
- db 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
- endp
Пример программы с исходным текстом (FASM)
Просмотров: 355 | Комментариев: 0
Комментарии
Отзывы посетителей сайта о статье
Комментариeв нет
Добавить комментарий
Заполните форму для добавления комментария
Материалы, опубликованные на этом сайте, не рекомендуются к просмотру лицам в возрасте до 16 лет без присутствия взрослых.
Вам помог этот сайт?
Поблагодарили 37,851 раз
Поблагодарили 37,851 раз
Буду очень благодарен, если размеcтите мою кнопочку:
 |
Яндекс ИКС: 330 |
 |
 |