Miracle #03
16 июля 1999

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

<b>Кто там кодит?</b> - Приближенный поиск заданной последовательности байт!
    (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'.

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


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




Другие статьи номера:

От редакции - Предисловие: С какой целью мы выпускаем журнал?

От редакции - Оболочка: описание новой оболчки к журналу.

От редакции - письма в журнал: Dr.Sioux/Phantom Family, Fistsoft, Mr.Z/HardWave, Куров Н., Eagle/Computer Ratz Group, Rom Corp/Virtual Vision Group.

От редакции - в этом номере: содержание номера.

Проект года - презентация версии игры Robo от KT-soft/ETC.

Проект года - презентация игры от группы Spark: Городки.

Проект года - презентация игры "12 Тайных книг".

Проект года - несколько слов о готовящейся к выходу игре Chip & Dale.

Проект года - потрясающая новелла к игре "Навигатор".

Проект года - Мир тьмы: описание новой real-time strategy.

Погремушки - свежие и не очень, но смачные читы.

Погремушки - крематорий: игра Сталкер - описание всех предметов.

Погремушки - крематорий: Страна мифов - советы спеца.

Основы SWAP'А - информация для начинающих, а также несколько хитрых извратов, которые можно провернуть с почтой.

Кто там кодит? - Быстрая графика: несколько рецептов от Zetter'а (печать спрайтов, обновление экрана).

Кто там кодит? - Packer'ы и Depacker'ы: вся правда о паковщиках, или разглагольствования сэра Kot'а.

Кто там кодит? - Работаем с MS-DOS: Все о mod файлах - полное описание структуры mod-файла, а также описание всех эффектов.

Кто там кодит? - Работаем с MS-DOS: Ms-Dos дискеты - описание структуры Ms-Dos диска.

Кто там кодит? - Chanky flame: описание алгоритма чанкового огня.

Кто там кодит? - Attribute bump mapping: bump mapping для тех кто не въехал.

Кто там кодит? - Гуру медитирует: оптимизация программ по времени исполнения и по размеру.

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

Кто там кодит? - Fast 42 print: быстрая процедура печати 42 символов в строке.

Party zone - KidSoft'98: репортаж с Воронежского фестиваля компьютерного искусства.

Party zone - EarthQuake'99: репортаж с Челябинского фестиваля компьютерного искусства.

Я сама - 128 цветов на Spectrum: схема доработки до 128 цветов от донецкой группы Spark.

Я сама - Чайникам: подключение General Sound к Profi через системный разъем.

Я сама - Бесперебойные блоки питания: информация об UPS-технологии.

Я сама - General Sound Filter: рассказ о новой примочке к GS.

Я сама - Модемы: Схемы, схемы! Схемы Г.Шепелева и М.Кондратьева подключения Hayes модема.

Я сама - Модемы: Описание команд - описание команд терминала.

Я сама - Модемы: Тотальная модемизация - призыв к подключению момедов.

Системный софт - FastCopy 3.0: полное описание навороченного турбо-копировщика.

Системный софт - Pro Tracker глюки!!! несколько глючков в ProTracker'ах.

Системный софт - Pro Tracker 3.4 final презентация ремикса Pro Tracker из Самары.

Новости - Челябинск: X-Raizor вернулся на спектрум, Wocen пишет boot, Blade отдахыет, Steelzer вступил в Triumph, Crite доделал альфа версию "Мира тьмы", Bytic купил GS, Edison делает сайт, Ironman хочет купить спектрум.

Новости - Омск: полный состав и ожидаемы продукты от группы U98.

Новости - Калининград: громкая смерть или тихая жизнь Spectrum в Калининграде.

Techno-nature - Электронная музыка: Dj.Ironman рассказывает о техно (часть 1).

Techno-nature - Электронная музыка: Dj.Ironman рассказывает о техно (часть 2).

Techno-nature - Internet music-sites: куча адресов,где можно узнать нового об электронной музыке.

Techno-nature - Наркомания XX: байка от Dj.Ironman'а.

Без четверти четыре - рассказ из повседневной жизни от X-Raizor'а.

Комната смеха - Запахи вокруг и внутри: прикольный рассказ из журнала ПТЮЧ.

Комната смеха - Пердмен: убийственный рассказ из все того-же ПТЮЧ'а.

Комната смеха - Фитиль: неколько сценариев из киножурнала ФИТИЛЬ.

Комната смеха - Ореол: окончание рассказа опубликованного во втором номере.

Прокламация - реклама и обьявления о поиске друзей на спектруме.

Прокламация - реклама и обьявления о поиске друзей на спектруме.


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Информация - "круглый стол" организаторов Фестиваля FunTop98.
Chimney - Вы даже не представляете, как мне приятно ощущать в воздухе весенние запахи и звуки!
заключение - авторы и т.д.
Версии - 3 версии игры: MULTI PLAYER SOCCER MANAGER.
TOP TEN - Десяточка лучших игр.

В этот день...   27 сентября