Прямой поиск в текстовой строке (asm x86)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:56, 9 августа 2015.

Цель поиска некоторой строки в строке большего размера — определить первый индекс элемента в строке , начиная с которого все символы совпадают с символами строки . Для этого алгоритм поиска последовательно просматривает символы строки , проводя одновременное сравнение ее очередного символа с первым символом строки . После возникновения такого совпадения алгоритм производит последовательное сравнение соответствующих элементов строк и до возникновения одного из следующих условий:

  • в процессе поиска соответствия достигнут конец строки — это означает, что строка совпадает с некоторой подстрокой строки ;
  • достигнут конец строки при незавершенном или не начатом просмотре строки — это означает, что строке не соответствует ни одна из подстрок .

Одна из главных проблем, которую приходится решать при написании программы обработки символьной строки, — определение конца строки . Здесь возможны два варианта:

  • статический — размер строки фиксирован некоторым значением ;
  • динамический (характерен для обработки массивов символьных строк) — длина строки определяется значением, являющимся либо первым элементом очередной строки, либо концевым (служебным) символом, значение которого заранее определено и не может совпадать ни с одним символом строки.

Начнем обсуждение прямого способа поиска с программы поиска в строке с фиксированной длиной. Для экономии места ограничим число вхождений в единицей.

;+---------------------------------------------------------------------------+
;| Программа: prg4_67_f.asm. Поиск строки P в строке S. Длина S фиксирована. |
;+---------------------------------------------------------------------------+				
;| Вход: S и P - массивы символов размером N и M байтов(M=<N).               |
;+---------------------------------------------------------------------------+
;| Выход: сообщение о количестве вхождений строки P в строку S.              |
;+---------------------------------------------------------------------------+
.data
s	         db      "Ах, какой был яркий день!"
 	         db      "Лодка, солнце, блеск и тень."
 	         db       везде цвела сирень."        ; задаем массив S
                 Len_S=$-s
                 db       "$"
mes              db      "Вхождений строки - "
p                db      "ень"                          ; задаем массив P - аргумент поиска
                 Len_P=$-p
                 db      " - "
Count            db      0. "$"                         ; счетчик вхождений P в S
.code   
                 ; ...
                 cld
                 mov     cx. len_s
                 lea     di. s
                 mov     al. p                          ; P[0]->al
next_search:     lea     si. p
                 inc     si                             ; на следующий символ
                 repne   scasb
                 jcxz    exit
                 push    cx
                 mov     cx. len_p - 1
                 repe    cmpsb
                 jz      eq_substr                      ; строка p <> подстроке в s
                 mov     bx. len_p - 1
                 sub     bx. cx
                 pop     cx
                 sub     cx. bx                         ; учли пройденное при сравнении cmpsb
                 jmp     next_search
          ;------ далее можно выйти если поиск однократный.
          ;       но мы упорные поэтому продолжаем...
eq_substr:       pop     cx
                 sub     cx. len_p - 1                  ; учли пройденное при сравнении cmpsb
                 inc     count
                 jmp     next_search
exit:            add     count 30h
          ;------ вывод сообщения mes на экран
                 ;...

Из программы видно, что когда размер строки фиксирован, то проблема ее конца решается просто. Но чаще приходится иметь дело с задачами, выполняющими поиск подстроки в строке, длина которой заранее не известна. Это характерно, в частности, для приложений обработки файлов. Но и с файлами не так все просто. Для текстовых ASCII-файлов особых проблем нет — в них строки заканчиваются символами 0dh, 0ah. Сложнее дело обстоит с обработкой двоичных файлов, где с равной степенью вероятности могут встретиться любые символы кодовой таблицы. В подобных случаях проблему локализации места в файле, где осуществляется поиск, нужно решать исходя из постановки конкретной задачи. Несмотря на это сами приемы поиска не сильно отличаются от рассмотренных в этом разделе.

В случае когда поиск осуществляется в строке или в массиве строк в памяти, длина которых заранее не известна, то для обозначения их окончаний нужно ввести некоторый служебный символ. Например, в ряде языков существует понятие строки ASCIIZ, представляющей собой обычную символьную строку с завершающим нулевым символом. По этому символу и определяется конец строки. Подобные служебные символы можно использовать и для обработки строк в памяти. Другая возможность задания границы строки — введение в структуру строки специального поля, обычно первого байта (2 байтов), содержащего длину этой строки.

Следующая программа демонстрирует возможную организацию поиска в текстовом файле. Для этого содержимое файла читается в динамически выделяемую область памяти. После небольшой модернизации данную программу можно рассматривать как основу для других программ поиска в строках памяти, ограниченных некоторым служебным символом, как это обсуждалось выше. Программа производит поиск слова «шалтай» в строках файла. На экран выводится номер строки, в которой встретилось это слово, и количество повторений этого слова в файле. В такой постановке задачи возникает проблема — необходимо отслеживать наступление одного из двух событий; обнаружение первого символа образца или обнаружение первого из пары символов 0d0ah, обозначающих конец строки. Данную задачу можно реализовать двумя способами. Первый заключается в последовательном чтении и проверке каждого символа строки на предмет удовлетворения их одному из обозначенных выше событий. При втором способе каждая строка файла сканируется два раза. На первом проходе определяется размер очередной строки, а затем эта строка сканируется второй раз на предмет наличия в ней искомой подстроки. Достоинство второй схемы состоит в том, что ее можно реализовать только использованием цепочечных команд. Какой из вариантов будет работать быстрее, можно определить с помощью профайлера. Мы выберем второй способ по двум причинам: во-первых, в этом разделе нас интересуют варианты использования цепочечных команд; во-вторых, в одной программе мы продемонстрируем приемы работы со строкой, размер которой определяется динамически двумя способами: со служебным символом в конце (им будет 0dh) и извлекаемым из байта в начале строки. В нашей программе байт со значением длины очередной строки будет эмулироваться первым проходом.

;+-----------------------------------------------------------------------------+
;| Программа: prg4_67_d.asm. Поиск строки P в массиве строк(файле).            |
;|            Длина строк определяется динамически.                            |
;+-----------------------------------------------------------------------------+				
;| Вход: Текстовый файл shaltai.txt и строка P ("Шалтай").                     |
;+-----------------------------------------------------------------------------+
;| Выход: сообщение о количестве вхождений строки P в строки файла shaltai.txt |
;+-----------------------------------------------------------------------------+
 	         db       везде цвела сирень."        ; задаем массив S




.data
mes	         db      "Вхождений строки - "
р	         db      "Балта"	                ; аргумент поиска - слово "Балта"
                                                        ; в файле shaltai.txt
                 db       строку файла"
                 db      0	                        ; старшая часть преобразования номера строки
n_str_f	         db      0	                        ; младшая часть преобразования номера строки
                 db      " - "
count	         db      0	                        ; счетчик вхождений Р в S. от 0 до 9
                                                        ; для упрощения алгоритма преобразования
                 Len_di р = $ - mes 
.stack	         256
.code
start	         ргос     near	                        ; точка входа в программу
          ;------ для размещения файла используем кучу, выделяемую процессу
          ;       по умолчанию (1 Мбайт): HANDLE GetProcessHeap (VOID): 
                 call     GetProcessHeap
                 mov      Hand_Head. eax                ; сохраняем идентификатор
          ;------ читаем файл в динамически выделяемую область памяти
          ;------ открываем файл
          ;       HANDLE   CreateFile(LPCTSTR IpFileName. DWORD dwDesiredAccess 
          ;                DWORD dwShareMode. LPSECURITY AHRIBUTES 
          ;                lpSecurityAttributes.DWORD dwCreationDisposition.
          ;                DWORD dwFlagsAndAttributes. HANDLE hTemplateFile);
                 ;...
                 call    CreateFileA
                 cmp     eax. 0ffffffffh 
                 je      exit                           ; если не успех
                 mov     hFile. eax                     ; файловый манипулятор
          ;------ определим размер файла 
          ;       DWORD GetFileSize(HANDLE hFile. LPDWORD lpFileSizeHigh);
                 ;...
                 call    GetFileSize 
                 test    eax. eax
                 jz exit	                        ; если неуспех
                 mov     FileSize. eax                  ; сохраним размер файла
          ;------ запрашиваем блок памяти из кучи
          ;       LPVOID HeapAlloc(HANDLE hHeap. DWORD dwFlags. DWORD dwBytes);
                 ;...
                call     HeapAlloc
                mov      buf start. eax                 ; адрес блока с текстом программы 
                                                        ; из общей кучи процесса 
          ;----- читаем файл
          ;      BOOL ReadFileCHANDLE hFile. LPVOID IpBuffer.
          ;      DWORD nNumberOfBytesToRead.
          ;      LPDWORD lpNumberOfBytesRead.LPOVERLAPPED lpOverlapped);
                 ;...
                 call    ReadFile 
                 test    eax. eax 
                 jz      exit                           ; если неуспех

                 push    ds 
                 pop     es 
                 cld
                 mov     ecx. FileSize 
                 mov     edi. buf start                 ; адрес буфера с текстом файла edi 
cycl1:           push    ecx
                 push    edi
                 mov     ebx. ecx
                 mov     al. 0dh                        ; 0dh->al
                 repne   scasb
                 jcxz    e_exit
                 jmp     $+7
e_exit:          ;...
                 jmp     exit
                 pop     edi
                 sub     ebx. ecx
                 xchg    ebx. ecx 
                 mov     al. p                         ; P[0]->al
next_search:     repne   scasb 
                 jcxz    end str                       ; достигнут конец строки
           ;----- проверяем возможное совпадение
                 push    ecx
                 lea     esi. p
                 inc     esi
                 mov     ecx. len_p-1
                 repe    cmpsb
                 jz      eq_substr                     ; строка p <> подстроке в s
                 mov     edx. len_p-1
                 sub     edx. ecx
                 pop     ecx
                 sub     ecx. edx                      ; учли пройденное при сравнении cmpsb
                 jmp     next_search
end_str:         inc     edi
                 inc     ebx
                 xchg    ebx. ecx
          ;------ преобразуем в символьное представление 
          ;       счетчик вхождений count
                ;...
          ;------ вывод на экран строки mes
                ;...
                call     WriteConsoleA
                ;...
                mov      count. 0                     ; обнуляем счетчик вхождений в строку 
                pop      ecx                          ; восстанавливаем
                jmp      cycl1
eq_substr:      pop      ecx
                sub      ecx. len_p-1                 ; учли пройденное при сравнении cmpsb
                inc      count
                jmp      next_search
exit:           pop      ecx
         ;------ выход из программы - задержим ввод до нажатия любой клавиши
                ;...

Этой программой мы проиллюстрировали оба варианта поиска с динамическим определением размера строки.

Алгоритмы, реализованные выше, можно использовать для организации поиска в строке небольшой длины, так как попытки повысить эффективность приведут к излишним накладным расходам. Для строки большой размерности (потоковые данные для приложений мультимедиа) прямые алгоритмы поиска могут быть неэффективными. Положение можно исправить рассмотренными ниже алгоритмами поиска с предварительным анализом искомой подстроки.