Introduction to "fiction point" logic.
=============================
One of most common tasks wich is included in 1000s basic and complex alorithms
is to scan for some basic datatype (byte,word,dword) element .
Mostly we have given condition:
1. Address to start from
2. Length (wich with address and direction determins range start-end)
3. Value we need to scan memory for
4. Direction
---------------------------
History

In the old days of xx86 the most used way to accomplish the task was several
opcodes united by mnemonic SCAS
(scasb(scan for byte),scasw(scan for word),scasd(scasd))
like:
mov al,ByteToSearch
mov edi,address
mov ecx,length
repne scasb
jne notfound
;if z flag set edi = address of byte searched +1
All of you of course know it, I write this section only for that looking though different ways we
keep in mind such things as pointer,size,address ect.
----------
However since days of Pentium this method is far from fastest one.
Faster way became creating a loop, incrementing pointer (if we search forward) decreamenting counter
and comparing both if current element from the pointer is what we are searching for and check if counter
is zero.
There are numerous ways how to do it, for example (just to see logic):

mov edi,offset String-1
mov ecx,LengthToSearh
mov al,ByteToSearch
@@: inc edi
cmp ,al
je Found
dec ecx
jne @B
;here is code for notfound case
....
....
found:

It may be done it other way all I want you to pay attention to is that in this logic we need to do:
1. Increment pointer
2. Decrement counter
3. Check if element from current pointer = searched element
4. Check if counter = 0
----------------------------------------------------------------------------------------------------------
The second step of progress is to remove one of this for basic operations - incrementing the pointer.
'Cause we already decrementing the counter we can use the counter as index to the pointer to shift
current address by one element.
It's obvious when we need to search backwardly:
mov edi,offset of string-1
mov ecx,length
mov al,ByteToSearch
@@: cmp byte ptr ,al ;start from the last byte
je found
dec ecx ;dec index & counter in ecx to shift pointer to 1 element lower address
jne @B
the same would be with words or dword the only difference is that we mastab (mul) index by the size of
the operand cmp ecx*4],eax - for dwords.

To understand how to use this method searching forward consider to things that address
is a sum of mul. index * sizeof operand and base adress.
Let base adress = A
Size of operand = 1
Index = B
Then
B*1 = B
B-B = 0
A+B-B = A
in code:
mov ecx,Size ;ecx = Size = last index B
mov edi,offset string ;edi = A
add edi,ecx ;edi = A+B
neg ecx ;ecx = - B
Then now = offset string
And now we can increment ecx until it 0, shifting at the same time pointer forward with each incremenation.

mov ecx,Size
mov edi,offset string
mov al,ByteToSearch
@@: cmp byte ptr ,al
je found
inc ecx
jne @B
....

found: add edi,ecx ;edi = address of searched byte
This way we elimenate needs for incrementing the poiner.

All the above was written to prepare us to final part: "fiction point logic"
Let's ask ourself - what if we knew for sure that there IS searched byte in a given range?

Obviously in that case we wouldn't need the counter at all!
And here "fiction point" logic will help us.
We can simply insert the byte in address wich serve us as boundry.
It may be last byte or first byte out of range:


.data?
temp db ?
...
.code
mov edi,offset string-1
mov ecx,Size
mov al,[edi][ecx][1] ;save the byte we a going to replace
mov temp,al
mov al,ByteToSearch
mov [edi][ecx][1],al ;insert searched byte

@@: cmp [edi],al
lea edi,[edi+1]
jne @B
dec edi ;edi = addr of found byte
add ecx,offset string ;address of inserted byte
cmp ecx,edi ;cmp addr of inserted byte with address of found byte
mov [ecx],al ; mov back the replaced byte
jne found ; if not equal we found the byte else there was no such a byte in the range

.... ; here is code if the byte was not found
found: ;edi = addr of found byte

Though you can see some more code in prologue and epilogue the code is very little clocks
consuming. And we remove one instruction form the loop wich is much more important.
Of course, implementation of the "fiction point" logic may be quite different.
I recommend try it with your own ideas.

I started "Basics of Asm32" again.
Posted on 2001-09-18 07:04:34 by The Svin