Вообще-то, я пишу под MFC, но мне хотелось узнать алгоритм, который использует метод CString::Find. Воспользовавшись автотрассировкой я дошла до этого (внизу) ужаса:
title strstr - search for one string inside another
;***
;strstr.asm - search for one string inside another
;
; Copyright (c) 1985-1997, Microsoft Corporation. All rights reserved.
;
;Purpose:
; defines strstr() - search for one string inside another
;
;*******************************************************************************
.xlist
include cruntime.inc
.list
page
;***
;char *strstr(str1, str2) - search for str2 in str1
;
;Purpose:
; finds the first occurrence of str2 in str1
;
;Entry:
; char *str1 - string to search in
; char *str2 - string to search for
;
;Exit:
; returns a pointer to the first occurrence of string2 in
; string1, or NULL if string2 does not occur in string1
;
;Uses:
;
;Exceptions:
;
;*******************************************************************************
__from_strstr_to_strchr proto
CODESEG
public strstr
strstr proc
mov ecx,[esp + 8] ; str2 (the string to be searched for)
push edi ; Preserve edi, ebx and esi
push ebx
push esi
mov dl,[ecx] ; dl contains first char from str2
mov edi,[esp + 10h] ; str1 (the string to be searched)
test dl,dl ; is str2 empty?
jz empty_str2
mov dh,[ecx + 1] ; second char from str2
test dh,dh ; is str2 a one-character string?
jz strchr_call ; if so, go use strchr code
; length of str2 is now known to be > 1 (used later)
; dl contains first char from str2
; dh contains second char from str2
; edi holds str1
findnext:
mov esi,edi ; esi = edi = pointers to somewhere in str1
mov ecx,[esp + 14h] ; str2
;use edi instead of esi to eliminate AGI
mov al,[edi] ; al is next char from str1
inc esi ; increment pointer into str1
cmp al,dl
je first_char_found
test al,al ; end of str1?
jz not_found ; yes, and no match has been found
loop_start:
mov al,[esi] ; put next char from str1 into al
inc esi ; increment pointer in str1
in_loop:
cmp al,dl
je first_char_found
test al,al ; end of str1?
jnz loop_start ; no, go get another char from str1
not_found:
pop esi
pop ebx
pop edi
xor eax,eax
ret
; recall that dh contains the second char from str2
first_char_found:
mov al,[esi] ; put next char from str1 into al
inc esi
cmp al,dh ; compare second chars
jnz in_loop ; no match, continue search
two_first_chars_equal:
lea edi,[esi - 1] ; store position of last read char in str1
compare_loop:
mov ah,[ecx + 2] ; put next char from str2 into ah
test ah,ah ; end of str2?
jz match ; if so, then a match has been found
mov al,[esi] ; get next char from str1
add esi,2 ; bump pointer into str1 by 2
cmp al,ah ; are chars from str1 and str2 equal?
jne findnext ; no
; do one more iteration
mov al,[ecx + 3] ; put the next char from str2 into al
test al,al ; end of str2
jz match ; if so, then a match has been found
mov ah,[esi - 1] ; get next char from str1
add ecx,2 ; bump pointer in str1 by 2
cmp al,ah ; are chars from str1 and str2 equal?
je compare_loop
; no match. test some more chars (to improve execution time for bad strings).
jmp findnext
; str2 string contains only one character so it's like the strchr functioin
strchr_call:
xor eax,eax
pop esi
pop ebx
pop edi
mov al,dl
jmp __from_strstr_to_strchr
;
;
; Match! Return (ebx - 1)
;
match:
lea eax,[edi - 1]
pop esi
pop ebx
pop edi
ret
empty_str2: ; empty target string, return src (ANSI mandated)
mov eax,edi
pop esi
pop ebx
pop edi
ret
strstr endp
end
С ассемблером я не знакома. Все, что мне требуется знать — выполняет ли мой "ужас" простой поиск (т.е. сдвиг = 1 символ при любом несовпадении искомой подстроки с той, в которой ищут) или нет. Будьте добры, подскажите!!! Благодарю заранее
Здравствуйте, Последний Чайник, Вы писали:
ПЧ>Вообще-то, я пишу под MFC, но мне хотелось узнать алгоритм, который использует метод CString::Find. Воспользовавшись автотрассировкой я дошла до этого (внизу) ужаса:
наверное проще указать путь до исходников MFC и посмотреть не на этот страшный ассемблерный код?
... << RSDN@Home 1.1 beta 2 >>
Здравствуйте, Последний Чайник, Вы писали:
ПЧ>Вообще-то, я пишу под MFC, но мне хотелось узнать алгоритм, который использует метод CString::Find. Воспользовавшись автотрассировкой я дошла до этого (внизу) ужаса:
ПЧ>
ПЧ>strstr endp
***
ПЧ> end
ПЧ>
ПЧ>С ассемблером я не знакома. Все, что мне требуется знать — выполняет ли мой "ужас" простой поиск (т.е. сдвиг = 1 символ при любом несовпадении искомой подстроки с той, в которой ищут) или нет. Будьте добры, подскажите!!! Благодарю заранее
выполняет. если справа один символ то поиск идет по урощенной схеме (strchr), если не один то ищется первый сивол, после него смотрится второй символ, если совпало то проверка продолжается, если нет — дальнейший поиск первого символа
а нафига все это надо?
Здравствуйте, Valerio, Вы писали:
V>наверное проще указать путь до исходников MFC и посмотреть не на этот страшный ассемблерный код?
Со-огласна!
Пишу: vc98\mfc\strex.cpp. Только он не ищет, а зовет tchar.h, этот — mbssr.c, а последний в свою очередь содержит незабвенную строку return strstr(str1, str2). А вот "ужас" — это последний в цепочке strstr.asm.
Мдя. Печально как все. А заглянуть в статьи на сайте лень?
http://www.rsdn.ru/?article/alg/textsearch.xmlАвтор(ы): Андрей Боровский
Дата: 28.01.2002
ПЧ>P.S. А что такое упрощенная схема (Бойер-Мур?)
