Miracle #03 16 июля 1999

Программирование

Кто там кодит? - Приближенный поиск заданной последовательности байт!

    (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'.

   Ссылка  на  автора  при  перепечатывании обязательно, при
использовании желательна.


              ---===Питательной вам пищи===---