Обработка цепочек элементов
В такой постановке задачи возникает проблема – необходимо отслеживать наступление одного из двух событий: обнаружение первого символа образца или обнаружение первого из пары символов OdOah, обозначающих конец строки. Вариант использования цепочечных команд из предыдущей программы не подходит, так как сканировать строку можно на предмет наличия только одного символа. Поэтому данную задачу можно реализовать двумя способами. Первый способ заключается в последовательном чтении и проверке каждого символа строки на предмет удовлетворения их одному из обозначенных выше событий. При втором способе каждая строка файла сканируется два раза. На первом проходе определяется размер очередной строки, а затем эта строка сканируется второй раз на предмет наличия в ней искомой подстроки. Достоинство второго способа состоит в том, что его можно реализовать только использованием цепочечных команд.
Какой из способов будет работать быстрее, можно определить с помощью профайлера. Мы выберем второй способ по двум причинам: во-первых, в этом разделе нас интересуют варианты использования цепочечных команд; во-вторых, в одной программе мы продемонстрируем приемы работы со строкой, размер которой определяется динамически двумя способами: со служебным символом в конце (им будет Odh) и извлекаемым из байта в начале строки. В нашей программе байт со значением длины очередной строки будет эмулироваться первым проходом.
start proc near:точка входа в программу: ;для размещения файла используем кучу, выделяемую процессу по умолчанию (1 Мбайт) ;HANDLE GetProcessHeap (VOID); call GetProcessHeap inov Hand_Head.eax сохраняем дескриптор ;читаем файл в динамически выделяемую область памяти ;открываем файл :HANDLE CreateFiIeCLPCTSTR ipFileName.DWORD dwDesiredAccess.DWORD; dwShareMode.LPSECURITY_ATTRIBUTES 1pSecuri tyAttributes.DWORD :dwCreationDisposition.DWORD:dwFlagsAndAttributes.HANDLE hTemplateFi1e): call CreateFileA cmp eax.Offffffffh je exit:если неуспех mov hFile.eax:дескриптор файла определим размер файла :DWORD GetFi1eSize(HANDLE hFile.LPDWORD ipFileSizeHigh); call GetFileSize cmp eax.O jz exit:если неуспех mov FileSize.eax:сохраним размер файла:запрашиваем блок памяти из кучи: :LPVOID HeapAlloc(HANDLE hHeap. DWORD dwFlags, DWORD dwBytes):;……… call HeapAlloc mov buf_start,eax:адрес блока с текстом программы из общей кучи процесса:читаем файл :BOOL ReadFile(HANDLE hFile.LPVOID ipBuffer.DWORD nNumberOfBytesToRead. ;LPDWORD lpNumberOfBytesRead.LPOVERLAPPED lpOverlapped): :……… call ReadFile cmp eax.O jz exit:если неуспех push ds pop es eld mov ecx.FileSize movedi.buf_start:адрес буфера с текстом файла в edi cycll: push ecx push edi mov ebx.ecx moval.Odh: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 mov ecx.len_p-l repe empsb jz eq_substr:строка р <> подстроке в s mov edx.len_p-l sub edx.ecx sub ecx.edx:учли пройденное при сравнении empsb jmp next_search end_str: incedi xchg ebx.ecx преобразуем в символьное представление счетчик вхождений count :вывод на экран строки mes call WriteConsoleA mov count.0 обнуляем счетчик вхождений в строку pop ecx:1 – восстанавливаем sub ecx.len_p-учли пройденное при сравнении empsb inc count jmp next_search exit: pop ecx ;выход из программы – задержим ввод до нажатия любой клавиши
Этой программой мы проиллюстрировали оба варианта поиска с динамическим определением размера строки.
Алгоритмы, реализованные в этих программах, можно использовать для организации поиска в строке S небольшой длины, так как попытки повысить эффективность приведут к излишним накладным расходам. Для строки S большой размерности (потоковые данные для приложений мультимедиа) прямые алгоритмы поиска могут быть неэффективными. Положение можно исправить рассмотренными ниже алгоритмами поиска с предварительным анализом искомой подстроки.