GetFilePath

[Vortex]

Hi Grincheux,

You are right, I should probably explain how the algo works. OK, let me try to explain. Our procedure is supposed to copy the file path to the destination buffer and determine the last \ character to mark the end of the path pointing the file :

Code Select Expand

mov  cl,BYTE PTR [esi+edx]
mov BYTE PTR [edi+edx],cl
add edx,1

It's clear that the characters are copied to the destination buffer pointed by edi. The most crucial part of the algo is to filter all the characters except the path terminator slash \ and the NULL ASCII string terminator. We create a lookup table to determine the candidates to be filtered by the algo :

Code Select Expand

cmp  BYTE PTR [ebp+ecx],0

ebp points our lookup table and ecx holds the current character fetched from the source pointed by esi+edx The cmp instruction compares the element stored in ebp having the index ecx against zero. ecx is an ASCII value pointed by esi+edx so if this member ( BYTE PTR [ebp+ecx] ) is marked as NULL in the array then the ZERO flag is set to FALSE and then this ASCII character is skipped and the following jump instruction redirects the execution to the nearest anonymous label @@ Let's have a look at the lookup table, there are two exceptions : The first is the NULL terminator character ( ASCII 0 ) and the other is the slash character \ ( ASCII 92 ) Both of them are marked as 1 If ecx holds one of those values then the element located by ebp+ecx should match a TRUE value ( = 1 ) This means that the ZERO flag is going to be set to TRUE and we determined that ecx is equal to 0 or 92. The rest is easy : quit the loop if cl is NULL or go back if cl == 92

You may me ask why I used the lookup table method. It simplifies the design of conditional jumps in the loops and eliminates the forward jump in my previous version of my algo.

[Grincheux]

Did you compare the number of bytes and cycles from the first algo and the new one ?
If all the programs were written with keeping in mind the need of speed with very good algos did we need to often change our cpus ? Did we need to have very big memories quantities on our PCs ? This is not specially for Windows ?

Thanks

[MichaelW]

The first version was taking about 200 cycles on my P3 to process a 17-character string, including the call overhead, but I did not try to compare this to other similar string functions, or to the second version.

[Vortex]

Grincheux,

Compared to the previous one, this new version runs faster. Testing a string sized 38 bytes :

The old version   : 321 cycles
The new version : 280 cyles

This example code was a modest attempt to optimize the algo. You don't need to renew periodically your hardware or to buy expensive components. All what you need is to use the force of the assembly language where it's required.

[ramguru]

using: (46 bytes string)
         timer_begin 10000000, REALTIME_PRIORITY_CLASS
         invoke(call) GetFilePath....
         timer_end

I got:
1445 - Vortex_version_1  :(
1349 - Vortex_version_2  ::)
766 - Lingo's  :wink

Using: counter_begin/end instead I got
275
273
151
Accordingly ...

[Grincheux]

This example code was a modest attempt to optimize the algo. You don't need to renew periodically your hardware or to buy expensive components. All what you need is to use the force of the assembly language where it's required.

Excatly what I am thinking. :boohoo:

Not any windows function called. It can be used by the pinguins...

When do you create an "OPTIMIZED LIBRARY" including this function ?

Writing such functions could be a challenge  :dance: ?

[ramguru]

OK I cannot let win anyone of you...  :U

Check out this kick-ass algo:

One disadvantage in my algo: destination size should be as large as source

Code Select Expand


GetFilePathR proc sour:DWORD, dest:DWORD

mov    ecx, sour
mov    edx, dest
@@:
mov    al, BYTE PTR [ecx]
cmp    al, 0
jz     @F
mov    BYTE PTR [edx], al
inc    ecx
inc    edx
jmp    @B
@@:
cmp    al, '\'
jz     @F
dec    edx
mov    al, BYTE PTR [edx]
jmp    @B
@@:
mov    BYTE PTR [edx+1], 0
ret

GetFilePathR endp


Tested speed:
with timer_begin:
1469 - Vortex_v1
1431 - Vortex_v2
764 - Lingo's
652 - mine  :8)

with counter_begin:
279 - Vortex_v1
275 - Vortex_v2
152 - Lingo's
130 - mine  :8)

[Grincheux]

There could be a problem if using this function on a network path. \\Server\Dir1\SubDri\File.txt

The second '\' is not detected because the corresponding byte of the table is equal to '0'. Don't need to modify the function, just indicate that it cannot be used for network path.

Am I right ? :dazzled:

[Grincheux]

RamGuru, you don not preserver ESI and EDI.

[ramguru]

fixed  :P

[Vortex]

Ramguru,

Compliments, nice idea but you must to be carefull with long file names giving different timing results.  :wink

d:\source\GetFilePath.asm

Grincheux,

Writing optimized algos is a nice idea but this task should not cross the aim of this forum. Regarding optimized algos, your ideas will be welcomed.

[ramguru]

You're right vortex, further tests  :U

Order: mine, lingo's, vortex_v2, vortex_v1

14 bytes - 48 39 89 129
28 bytes - 96 98 155 217
46 bytes - 129 151 273 262
83 bytes - 255 322 505 481

[Grincheux]

I've just modify RamGuru code and I got :

eax = 100,  cycles
----------------------------------------
eax = 610,  ms
----------------------------------------

GrincheuxGetFilePath proc sour:DWORD, dest:DWORD

      push   edi
      push   esi

   mov    esi, sour
   mov    edi, dest
   mov      edx,1
   mov      ah,'\'

@@:
   mov    al, BYTE PTR [esi]

   test   al,al
   jz     @F

   mov    BYTE PTR [edi], al
   add    esi,edx
   add    edi,edx
   jmp    @B

@@:   

   cmp    al,ah
   jz     @F

   sub    edi,edx
   mov    al, BYTE PTR [edi]
   jmp    @B

@@:

   mov    BYTE PTR [edi+1], 0
   pop      edi
   pop      esi
   ret
GrincheuxGetFilePath endp

[ramguru]

damn I wrote kick-ass algo to kick someone's ass with it, not my own...   :eek

[Vortex]

Ramguru,

Believe me, it can be sometimes difficult to find the last step of those optimizations. :wink The collaboration of you and Grincheux gave a nice idea regarding code design. Thanks Grincheux and Ramguru.