Reverse string

[lostcauz]

Here's my attempt at a quick string reversal.

Code Select Expand

str1 db 'abcdefghijklmnopqrstuvwxyzabc',0
str2 db 64 dup(0)

start:   

    lea esi,str1           
    lea edi,str2
    mov ecx,[sizeof str1-1]
    mov ebx,ecx
    cmp ecx,4
    jb l1
    and ebx,3               ; test for alignment
    jz l2
    cmp ebx,3
    jnz @f
    sub ecx,1
    mov al,[esi+ecx]
    sub ebx,1
    mov [edi],al
    add edi,1

@@: cmp ebx,2
    jnz @f
    sub ecx,1
    mov al,[esi+ecx]
    sub ebx,1
    mov [edi],al
    add edi,1

@@: cmp ebx,1
    jnz l1
    sub ecx,1
    mov al,[esi+ecx]
    mov [edi],al
    add edi,1
    jmp l2
   
l1: sub ecx,1               ; string is less than 4 characters
    mov al,[esi+ecx]
    mov [edi],al
    add edi,1
    or ecx,ecx
    jz l3
    jmp l1
   
l2: sub ecx,4
    jnz @f
    mov eax,[esi+ecx]     
    bswap eax
    mov [edi],eax
    jmp l3
       
@@: mov eax,[esi+ecx]       ; 4 byte aligned string
    bswap eax
    mov [edi],eax
    add edi,4
    sub ecx,4
    jnz @b               
    mov eax,[esi]     
    bswap eax
    mov [edi],eax
l3:                         ; result in str2


[Larry Hammick]

This looks like a job fer BSWAP. Something like

Code Select Expand


.data
inputstring db "abcdef"
inputstring_ equ $-offset teststring  ;or, say, inputstring_ dd $-inputstring
outputbuff db 10h dup (?)
.code
reverse_string:
    mov esi,offset inputstring
    mov ecx,inputstring_
    mov edi,offset outputbuff
    lea edi,[edi+ecx-1]
    and ecx,3
    jz zero_mod_4
@@: lodsb
    std
    stosb
    cld
    loop @B
zero_mod_4:
    sub edi,3
    mov ecx,inputstring_
    shr ecx,2
    jz no_whole_dwords
@@: lodsd
    bswap_eax
    std
    stosd
    cld
    loop @B
no_whole_dwords:     ;done


[NightWare]

here the one i use :

Code Select Expand


ALIGN 4
ReverseString PROC StrAddr:DWORD
push edx
push esi
push edi
mov esi,StrAddr
mov edi,esi
sub edi,4
Label1: add edi,4
mov eax,DWORD PTR [edi]
lea edx,[eax-01010101h]
xor eax,edx
and eax,80808080h
jz Label1
and eax,edx
jz Label1
bsf edx,eax
sub edx,4
shr edx,3
add edi,edx
mov eax,edi
sub eax,esi
Label3: sub edi,1
mov dh,BYTE PTR [edi]
mov dl,BYTE PTR [esi]
mov BYTE PTR [esi],dh
mov BYTE PTR [edi],dl
add esi,1
cmp esi,edi
jb Label3
Label4: pop edi
pop esi
pop edx
ret
ReverseString ENDP


or this one, it's faster but the string have to be 4 bytes long mini  :red :

Code Select Expand


ALIGN 4
FastReverseString PROC StrAddr:DWORD
push edx
push esi
push edi
mov esi,StrAddr
mov edi,esi
sub edi,4
Label1: add edi,4
mov eax,DWORD PTR [edi]
lea edx,[eax-01010101h]
xor eax,edx
and eax,80808080h
jz Label1
and eax,edx
jz Label1
bsf edx,eax
sub edx,4
shr edx,3
add edi,edx
mov eax,edi
sub eax,esi
Label3: sub edi,4
mov edx,DWORD PTR [edi]
mov ecx,DWORD PTR [esi]
bswap ecx
bswap edx
mov DWORD PTR [esi],edx
mov DWORD PTR [edi],ecx
add esi,4
cmp esi,edi
jb Label3
Label4: pop edi
pop esi
pop edx
ret
FastReverseString ENDP


[Ratch]

To the Ineffable All,
     Here is my contribution to a reverse byte string program.  Eight bytes get transferred with every iteration through the loop.  Works for all string lengths too.  It does not try to figure out the string length as there are many programs to do that.  Why duplicate?  By the way, the FastReverseString routine gives false results on string 'ABCDEFGHI' .  Ratch

Code Select Expand


;*******************************************************************************
; REVBSTR:   Reverses the bytes of an ASCII string.                            *
;                                                                              *
; Called by: PUSH <address of string>                                          *
;            PUSH <string length>                                              *
;            CALL REVBSTR                                                      *
;                                                                              *
; Returns:   Nothing                                                           *
;                                                                              *
; Notes:     This subroutine conforms with WIN32 conventions regarding         *
;            register preservation and stack balancing.                        *
;                                                                              *
; Coder:     Ratch                                                             *
;*******************************************************************************
REVBS$ STRUC
  RETURN    DWORD ?
RV1$ = $
  STRLEN    DWORD ?
  SADR      DWORD ?
RV2$ = $
REVBS$ ENDS

RVBS$ EQU ESP.REVBS$    ;save some typing

REVBSTR:                ;it all begins here
PUSH ESI               ;save register
PUSH EDI               ;save register
MOV ESI,[RVBS$.SADR+2*DWORD]   ;string start address
MOV EAX,[RVBS$.STRLEN+2*DWORD] ;string length
MOV EDI,ESI            ;string start address
PUSH EBX               ;save register
ADD ESI,EAX            ;string end address
SHRD EDX,EAX,3         ;1st part of MOD operation
SUB ESI,DWORD          ;back up string end address one DWORD
SHR EAX,3              ;EAX = (string length) divided by 8
SHR EDX,32-3           ;2nd part of MOD operation EDX = (string length) MOD 8

.IF EDX > 4            ;modify loop counter and remainder
   INC EAX              ;increment loop counter for below
   XOR EDX,EDX          ;set remainder to zero for below
.ENDIF

.WHILE EAX             ;8 bytes moved each time through loop
   MOV ECX,[ESI]        ;pick up 4 bytes
   MOV EBX,[EDI]        ;pick up 4 bytes
   BSWAP ECX
   BSWAP EBX
   MOV [EDI],ECX        ;put down 4 bytes
   MOV [ESI],EBX        ;put down 4 bytes
   SUB ESI,DWORD        ;move string end pointer
   ADD EDI,DWORD        ;move string beginning pointer
   DEC EAX              ;loop counter
.ENDW

.IF EDX                ;move remaining 3,2, or 1 bytes
   MOV EBX,[EDI]        ;pick'em up
   BSWAP EBX            ;swap'em around

   .IF     EDX == 3     ;EDX = (string length) MOD 8
     ROR EBX,1*8        ;shift around
   .ELSEIF EDX == 2
     XOR BH,BL          ;\
     XOR BL,BH          ; > these three XORs swap the values of BL & BH (XCHG)
     XOR BH,BL          ;/
     ROR EBX,2*8        ;shift around
   .ELSEIF EDX == 1
      BSWAP EBX         ;swap'em around
   .ENDIF

   MOV [EDI],EBX        ;put 'em down
.ENDIF

POP ESI                ;restore register
POP EDI                ;restore register
POP EBX                ;restore register
RET RV2$-RV1$          ;return home


[lostcauz]

Thanks for the responses!  :U
Did yall time the different methods? Using my alphabet+abc test string and a P4 I got 47 cycles for the one I posted and 88 for Ratch's. The others were slower. I started out using string instructions but they seemed to slow things down. I had also tried the direction flag bit which also seemed slow.

[NightWare]

the FastReverseString routine gives false results on string 'ABCDEFGHI' .  Ratch

ok, here the correction (i've tested different size this time  :red ), it's just a mix of my previous code :

Code Select Expand


ALIGN 4
FastReverseString PROC StrAddr:DWORD
push ecx
push edx
push esi
push edi

; finding final 0
mov esi,StrAddr
mov edi,esi
sub edi,4
Label1: add edi,4
mov eax,DWORD PTR [edi]
lea edx,[eax-01010101h]
xor eax,edx
and eax,80808080h
jz Label1
and eax,edx
jz Label1
bsf edx,eax
sub edx,4
shr edx,3
add edi,edx
mov eax,edi
sub eax,esi
; something to reverse ?
cmp eax,2
jb Label4
; big or small string ?
cmp eax,9
jb Label3
; treatment for the big one
Label2: sub edi,4
mov edx,DWORD PTR [edi]
mov ecx,DWORD PTR [esi]
bswap ecx
bswap edx
mov DWORD PTR [esi],edx
mov DWORD PTR [edi],ecx
add esi,4
cmp esi,[edi+8]
jb Label2
; treatment for the small one
Label3: sub edi,1
mov dh,BYTE PTR [edi]
mov dl,BYTE PTR [esi]
mov BYTE PTR [esi],dh
mov BYTE PTR [edi],dl
add esi,1
cmp esi,edi
jb Label3
Label4:
pop edi
pop esi
pop edx
pop ecx
ret
FastReverseString ENDP


It does not try to figure out the string length as there are many programs to do that.  Why duplicate?

lol, maybe because i don't want to see an extra line to get lenght, and another one to store the result...  :bg

[Ratch]

NightWare,
     Your routine still needs work.  Did you test it?  I tried it with 'ABCDEFGHI' and it did NOT reverse the characters.  Also it cycled through the dword loop 9 times when it only needs to cycle once for this string.

     You do not need to save EDX because that is not a essential Windows register.  A little documentation would also be helpful.

lol, maybe because i don't want to see an extra line to get lenght, and another one to store the result...

     Ok, but you have lots of lines within the subroutine that duplicate the code of a STRLEN program.  Ratch

[Ratch]

lostcauz,
     The string instructions are notorious for being slow.  Timing can be tricky, especially with cache effects.  What you think you see is not always what is so.  You should make your routine into a subroutine so I can test it.  That means storing the essential Windows registers, clearing the parameters from the stack when finished, and putting a RET instruction at the end.  Some documentation would help too.  Ratch

[lostcauz]

Hi Ratch,

You are correct, after adding the additional overhead yours is slightly quicker.  :U Thanks for your input. I commented the attached code.

[attachment deleted by admin]

[lingo]

 :lol

Code Select Expand


StrRev:
mov ecx, sizeof str1-1
xor eax,eax
cmp ecx, 4
jl Bytes3
push ebx
@@:
mov edx, dword ptr [str1+eax]
add eax, 4
add ecx, -8
mov ebx, dword ptr [str1+eax+ecx]
bswap edx
mov dword ptr [str2+eax +ecx], edx
bswap ebx
mov dword ptr [str2+eax-4], ebx
jg @b
pop ebx
ret
Bytes3:
movzx edx, byte  ptr [str1]
cmp ecx, 1
mov byte ptr [str2+ecx-1], dl
jle End3
mov dl, byte  ptr [str1+1]
cmp ecx, 2
mov byte ptr [str2+ecx-2], dl
jle End3
mov dl, byte  ptr [str1+2]
mov byte ptr [str2+ecx-3], dl
End3:
ret
Regards,
Lingo

[lostcauz]

Hi lingo,

Very nice! I attached the code (from MichaelW I think) I used for timing. Is this the accepted method used for speed comparisons?

[attachment deleted by admin]

[BoR0]

This is my piece of code. Bit old though, but still works :lol

Code Select Expand

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
; usage strrev(buffer, buffer2);
; reverts a string from buffer2 and places it into the buffer

strrev PROC uses esi edi lpBuffer:DWORD, lpSource:DWORD
mov edi, lpBuffer
mov esi, lpSource

invoke strlen, edi
dec eax

mov ecx, -1

@@:
inc ecx

push eax
sub eax, ecx

mov al, byte ptr [edi+eax]
mov byte ptr [esi+ecx], al

pop eax

cmp eax, ecx
je @F

jmp @B
@@:

ret
strrev ENDP
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

Good luck!  :U

[Ratch]

lingo,
     Back to the coding desk for your subroutine.  I tested your code, and it returned a string of HGFEDCBA given ABCDEFGHI.  In fact, it truncated a character off every string submitted.  It would be more useful if it used the same buffer for both output and input, but if it outputs to a different buffer, it should tack on a zero byte at the end.   Code also needs indentation, documentation, and inputing parameters from the stack or registers.  Ratch

[Ratch]

lostcauz,
     Before you do timing tests, code should be tested for correctness.  That comes first.  Strange that your code truncates the last string character just like lingo's did.  Also, you need to write a zero byte at the end of the string.  Don't depend on the buffer to be initialially zeroed out.  You still need to save the essential Window registers that you used, and either put the input parameters on the stack or define them in a register.  You have a good start on documentation, now try some indentation to highlight the loops and conditional clauses.  Ratch

[lingo]

lostcauz  :lol
Here is my times (P4 3.6GHz and WinXP SP2):

Code Select Expand


Please terminate any high-priority tasks and press ENTER to begin.


ReverseStr  Tests:

ReverseStr - lostcauz  : 35 clocks
ReverseStr - lingo     : 26 clocks

Press ENTER to exit...


[attachment deleted by admin]