Иллюстрированный самоучитель по задачам и примерам Assembler

Обработка цепочек элементов

В такой постановке задачи возникает проблема – необходимо отслеживать наступление одного из двух событий: обнаружение первого символа образца или обнаружение первого из пары символов 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 большой размерности (потоковые данные для приложений мультимедиа) прямые алгоритмы поиска могут быть неэффективными. Положение можно исправить рассмотренными ниже алгоритмами поиска с предварительным анализом искомой подстроки.

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.