搜索字符串中最有效的代码 [英] Most effective code to search character in string

问题描述

假设我们有一个给定的字符字符串

Let's say we have a given string of chars

DataString DB 'AGIJKSZ', 0FFH ; 

在其中找到J的最有效的过程是什么? 节省时间是指最少的时钟滴答声.

What would be the most time-effective procedure to find let's say J in it? By time-effective I mean least amount of clock ticks.

这是具有以下指令集的x86处理器:

It's a x86 processor with these instruction sets:

MMX, SSE, SSE2, SSE3, SSSE3, SSE4.1, SSE4.2, EM64T, VT-x, AES, AVX, AVX2, FMA3, TSX

让我们假设可以更改字符串和搜索到的字符，但是只能通过编辑代码来进行更改，并且我们一直在寻找单个字符.字符串是ASCII.字符串的结尾用FF

Let's assume that both string and searched character can be changed but only via editing the code, and we're always looking for a single character. The string is ASCII. End of string is marked by FF

答案应该只是将EAX设置为找到1/找不到0.

Answer should be just setting EAX to found 1 / not found 0.

这是我能想到的

FindChar_1 PROC
 MOV ESI, OFFSET DataString ; 
SI
 MOV AH, 'J' ; 
Check_End:
 CMP BYTE PTR [ESI], 0FFH ; 
 JE Not_Find ; 
 CMP AH, [ESI] ; 
'DataString'
 JE Got_Equal ;
 ADD ESI, 1 ; 
 JMP Check_End ;
Got_Equal:
 MOV DL, [ESI] ; 
 JMP Done
Not_Find:
 MOV EAX,0 ; 
 RET ;
Done:
 MOV EAX,1 ; 
 RET ; 
FindChar_1 ENDP

现在我意识到我还有其他我应该提到的地方.我正在使用masm32，因此我可以使用的指令仅限于非常基本的指令.

Now I realize that there I something else I should have mentioned. I'm using masm32 so instructions I can use are limited to the very basic ones.

推荐答案

当您需要快速编写代码时，请避免内存访问，跳转和复杂的指令.我将扫描字符串两次:一次找到结束标记，然后找到搜索到的字符:

When you need the code be fast, avoid memory access, jumps and complex instructions. I would scan the string twice: once to find the end marker, and then to find the searched character:

FindChar_2 PROC
MOV ESI, OFFSET DataString
XOR EAX,EAX
XOR ECX,ECX
XOR EDX,EDX
NOT EAX ; Let AL=EndOfString marker.
NOT ECX ; Let ECX=Max.integer.
MOV EDI,ESI
CLD
REPNE SCASB ; ECX -= String size (-9 in this example).
NOT ECX ; ECX= String size (8).
MOV AL,'J' ; The searched needle.
MOV EDI,ESI ; Restore the haystack pointer.
REPNE SCASB ; The actual search. 
  ; It returns CF if not found, because the needle is below 0FFH.
CMC ; Invert the logic.
MOV EAX,EDX ; Return false.
ADC EAX,EDX ; Return true if found.
RET
FindChar_2 ENDP

这篇关于搜索字符串中最有效的代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！