(c) Wocen/Triumph
------------------
Приближенный поиск заданной последовательности байт !!!
Недавно ломая какую-то защиту, или что-то еще, столкнулся
с небольшой проблемой. Нужно было найти заданный стринг
(последовательность байт). Ну и что за проблема, скажет
уважаемый читатель, сравнивай побайтово и все, вплоть до
получения результата. А вся проблема в том, что я не знал на
100% есть ли заданная последовательность в исходном файле. И
вот тогда, то и пришла в голову идейка написать поиск
последовательности максимально приближенной к заданной. Суть
метода очень проста.
1) Берем исходный текст:
Исходный текст : I'am wocen !
Шестнадцатиричное: #49,#27,#61,#6D,#20,#77,#6F,#63,#65,#6E
2) Задаем последовательность которую нужно найти:
Заданная последовательность: Wocen
В шестнадцатиричной системе: #57,#6F,#63,#65,#6E
Видно что простейшее побайтовое сравнение ничего не даст.
3) Берем заданный стринг и проксориваем его по тексту (с
начала текста). Имеем:
#57 #6F #63 #65 #6E
XOR
#49 #27 #61 #6D #20
= -------------------
#1E #48 #02 #08 #4E
4) Суммируем количество оставшихся бит равных единице !
#1E = 4 бита
+ #48 = 2 бита
+ #02 = 1 бит
+ #08 = 1 бит
+ #4E = 4 бита
= --------------
12 бит (единичек), ошибок.
5) Запоминаем адрес в тексте с которого было сравнение и
сохраняем число ошибок = 12.
Далее мы повторяем те же операции но только уже не с
начала текста, а со смещением 1. Т.е. будет:
#57 #6F #63 #65 #6E
XOR
#27 #61 #6D #20 #77
= -------------------
#48 #02 #08 #4E #19
11 бит (единичек)
6) В этот раз мы смотрим: ага количество единичек меньше,
чем в первый раз, значит вероятность того, что нашли нужную
последовательность выше! Сохраняем адрес из текста, и коли-
чество ошибок.
Так повторяем для всего текста. Подробнее остановимся,
когда адрес в тексте показывает на стринг "wocen" который
отличается от заданного "Wocen" только первой буквой.
#57 #6F #63 #65 #6E = "Wocen"
XOR
#77 #6F #63 #65 #6E = "wocen"
= -------------------
#20 #00 #00 #00 #00
Количество ошибок = 1, т.к. только 1 бит равен 1. Так как
количество ошибок меньше предыдущего то, сохраняем адрес в
тексте, и ошибки.
По окончании текста берем адрес который нашли в процессе
работы и выдаем его пользователю!!!
Где можно еще использовать эту програмку ?
Да где угодно. Например в том же ассемблере, разумеется
не вместо побайтового сравнения, а дополнительно (в
нагрузку >;-)) Так как по своему опыту знаю, при наличии
уже 4 файлов исходного текста, метки имееют свойство
забываться а вспомнить ее точное/полное название уже и не в
силах. Вот здесь-то конкретно и пригодится приближенный
поиск.
Кроме того приближенный поиск можно использовать в
программах для перегонки 'Экран' в 'Текст'. Кстати на мой
субъективный взгляд наилучшей из существующих подобных
программ является программа "Screen to text transformer" by
Death Moroz/Сланцы. У меня еще есть пара аналогичных прог,
но они настолько убоги, что о них лучше вообще умолчать. В
"Screen to text transformer" использован обычный побайтовый
сравнитель, и когда пришлось им воспользоватся, было
довольно неприятно учить программу что буква "а" с
утолщением, одно и то-же, что "а" без утолщения, и так почти
со всеми символами. А если-бы был использован побитовый
метод то к клавиатуре вообще можно было не прикасаться, уча
программу. Хотя возможно какие-то буквочки были-бы заменены
другими :-) Так что на будущее, если кто захочет написать
класный перекодировщик из картинки в текст, то пусть учтет
несколько моментов:
1 - Должна быть возможность перекодировать цветные и ч/б
экраны,с кодом цвета 16 (#10) и после него сам цвет.
2 - Порядок загрузки должен идти согласно пометке файлов.
3 - Шрифтов для сравнения должно-быть 2-3, для каждого
размера шрифта, т.е. 3 шрифта размером 4x8, 6x8, 8x8
ну и можно сделать 3 шрифта размером 5x8.
4 - Буфер под получаемый текст 16 кб, с контролем пере-
полнения.
5 - Муза просто необходима.
6 - Ну и наконец кроме задания одного какого-то размера
шрифта на картинку, должна быть возможность комбини-
рованной работы. Как определить каким шрифтом напеча-
тано? Элементарно!!! Смотрим вертикальный столбик,
если он нулевой то с вероятностью 90% можно утвер-
ждать что это граница символа. Далее пододвигаем оче-
редной символ, смотрим его длину и ищем среди теку-
щего размера.
А теперь сам исходник приближенного поиска с комментари-
ями. Исходник писан в Alasm'e с использованием его специфи-
ческих команд.
;-----------------------------------------------------------
;WRITTEN BY WOCEN/ORION/TRIUMPH - МАЙ 1998
;СКОРОСТЬ ПОИСКА ЗАДАННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ПРИМЕРНО:
;3270 БАЙТ В 1 СЕКУНДУ (БЕЗ ТУРБЫ), НА 5 БАЙТ
;1630 БАЙТ В 1 СЕКУНДУ (БЕЗ ТУРБЫ), НА 10 БАЙТ
; 850 БАЙТ В 1 СЕКУНДУ (БЕЗ ТУРБЫ), НА 20 БАЙТ
;4680 БАЙТ В 1 СЕКУНДУ (В ТУРБЕ, СКОРПИОНОВСКОЙ), НА 5 БАЙТ
;2520 БАЙТ В 1 СЕКУНДУ (В ТУРБЕ), НА 10 БАЙТ
;1260 БАЙТ В 1 СЕКУНДУ (В ТУРБЕ), НА 20 БАЙТ
ORG #8000
ADR_TXT EQU #0000 ;АДРЕС НАЧАЛА ПОИСКА
LEN_TXT EQU 32768 ;ДЛИНА ПОИСКА
LEN EQU 5 ;ДЛИНА ЗАДАННОГО СТРИНГА
DI
XOR A
DEC A ;СТАВИМ ПРИ СТАРТЕ МАКС.
LD (OLD+1),A ;ОШИБКУ = 255 (#FF)
LD BC,LEN_TXT ;ДЛИНА ПОИСКА
EXX
LD DE,ADR_TXT ;НАЧАЛЬНЫЙ АДРЕС ПОИСКА
L1 LD B,LEN ;ДЛИНА ПОСЛЕДОВАТЕЛЬНОСТИ
LD HL,TEXT ;НАЧАЛО ПОСЛЕДОВАТЕЛЬНОСТИ
PUSH DE ;СОХРАНИЛИ ТЕКУЩИЙ АДРЕС
;ТЕКСТА
L2 LD A,(DE) ;БАЙТ ДАННЫХ
XOR (HL) ;СВЕРЯЕМ
ERRORS LD C,0 ;КОЛИЧЕСТВО ОШИБОК
;Команда DUP повторяет кусок кода после себя до директивы
;EDUP заданное в DUP раз.
;В этом случае раскрытие цикла позволило немного ускорить
;одну из _ДОХРЕНА_ВРЕМЯ_СЪЕДАЮЩИХ_ подпрограмм для работы.
DUP 8 ;ПРОВЕРЯЕМ ВСЕ 8 БИТ
RRA ;БИТ = 0 ?, (Т.Е. СОВПАЛ)
JR NC,$+2+1;ПЕРЕХОД ЕСЛИ СОВПАЛ
INC C ;УВЕЛИЧИВАЕМ КОЛИЧЕСТВО НЕ
EDUP ;СОВПАДЕНИЙ (ОШИБОК)
LD A,C
LD (ERRORS+1),A ;СОХРАНЯЕМ НЕ СОВПАДЕНИЯ
INC HL ;УВЕЛИЧИВАЕМ АДРЕС ЗАДАННОГО
;СТРИНГА
INC DE ;УВЕЛИЧИВАЕМ АДРЕС ТЕКСТА
DJNZ L2 ;ПОВТОР
POP DE ;ВОССТАНОВИЛИ АДРЕС ТЕКСТА
OLD LD A,#FF ;СТАРЫЙ РЕЗУЛЬТАТ
CP C ;МЕНЬШЕ ЧЕМ НОВЫЙ ?
JR C,L3 ;ДА !
JR Z,L3 ;РАВЕН ! => ОСТАВЛЯЕМ СТАРЫЙ
;РЕЗУЛЬТАТ
LD А,C ;ВЗЯЛИ НОВЫЙ РЕЗУЛЬТАТ
LD (OLD+1),A ;СОХРАНЯЕМ ЕГО
LD (ADRES+1),DE ;СОХРАНЯЕМ ЕГО АДРЕС В
;ТЕКСТЕ
AND A ;НОВЫЙ РЕЗУЛЬТАТ СОВПАЛ БЕЗ
;ОШИБОК ?
JR Z,ADRES ;ПЕРЕХОД ЕСЛИ ДА !
;Сюда можно будет вставить кусок программы приведенный ниже
L3 XOR A
LD (ERRORS+1),A ;ОБНУЛЯЕМ ОШИБКИ
INC DE ;УВЕЛИЧИВАЕМ АДРЕС В ТЕКСТЕ
EXX
DEC BC ;УМЕНЬШАЕМ ОБРАБАТЫВАЕМУЮ
LD A,B ;ДЛИНУ
OR C
EXX
JR NZ,L1 ;ПЕРЕХОД ЕСЛИ НЕ ЗАВЕРШИЛИ
ADRES LD HL,0 ;НА ВЫХОДЕ ЗДЕСЬ АДРЕС В
;ТЕКСТЕ,
LD A,(OLD+1) ;А ЗДЕСЬ КОЛИЧЕСТВО ОШИБОК !
RET
TEXT DEFB "Wocen" ;ЗАДАННЫЙ СТРИНГ
Ну как вы видно из исходника выход из процедурки
осуществиться только если будет 100% совпадение или пока не
перелопатим всю заданную память. Поэтому можно вставить
следущий кусок программы перед меткой 'L3':
ERROR EQU 4 ;ПРЕДЕЛ ДЛЯ ОШИБКИ
;Т.Е. ЕСЛИ МЕНЬШЕ ЭТОГО
;ВСТРЕТИТЬСЯ ОШИБКА, ТО
;БУДЕМ СЧИТАТЬ ЧТО ЭТО
;НОРМАЛЬНО. ТЕМ САМЫМ
;РЕГУЛИРУЕМ ЧУВСТВИТЕЛЬНОСТЬ
...
CP ERROR ;ПРОВЕРКА НА ПРЕДЕЛ ОШИБКИ
JR C,ADRES ;ЕСЛИ МЕНЬШЕ ЗАДАННОГО
;ПРЕДЕЛА, ТО ПЕРЕХОД
L3 ... ;ПРОДОЛЖЕНИЕ ПРОГИ
Разумеется этот код не претендует на крутость и наверняка
можно ускорить его применив чтение байт из памяти стеком, ну
и наверное заменив все 'JR' на 'JP'.
Ссылка на автора при перепечатывании обязательно, при
использовании желательна.
---===Питательной вам пищи===---
