MASM string reversal

Question

Alright, Im going about this, with what is probably a really complicated solution, but its the first thing that popped into my head.

I need to write an assembly language program that reverses a "source" string, without using a "target" string ( a temp variable ) .. this is my attempt at it.

INCLUDE Irvine32.inc
.data
source BYTE "This is the source string", 0
count DWORD ? 

.code
main PROC

 mov ecx, LENGTHOF source 

L1: 
 mov count, ecx     ; save our outer loop count
 mov al,[source+0]    ; get the first character in the string

 mov ecx,LENGTHOF source  ; set out inner loop count
 mov esi, OFFSET source
 inc esi
L2:


 mov bl,[esi]
 dec esi
 mov [esi],bl
 add esi, 2
 loop L2

 mov ecx, count
 loop L1


 mov  edx,OFFSET source
 call WriteString

 exit
main ENDP

END main

Now.. the "algorithm" for this is basically this: Take the first character out of the string, move all of the other characters down one space in the character array, put the character you first took out into the back of the array. Now, I'm to the point where this is much too complicated. Infact, how do I get to the back of the array.. I think I would need another loop? I certainly don't need three loops or even want to deal with that.

Maybe I'm on the right track and don't even know it. any suggestions, tips, code or a different algorithm would help!

Answer 1

You could do it your way with two loops. After doing your first loop, you then have to do it again but with the length reduced by one, so that the current first (originally second) character gets put at the second-last position, leaving the current last (originally first) character alone. Then keep going until the length drops to zero.

But that's pretty inefficient since you have the nested loops, O(n²). Here's a better algorithm that uses just one loop, O(n):

set spointer to point to the first character
set epointer to point to the last character
while epointer is greater than spointer:
    save away [spointer] (the character pointed to by spointer) somewhere
    copy [epointer] to [spointer]
    copy the saved character to [epointer]
    add one to spointer
    subtract one from epointer

It basically maintains a start and end pointer which initially swaps the first and last character, then the pointers are moved towards each other.

So the second time through the loop, you swap the second and second-last character, the third time the third and third-last character and so on.

This process stops when the pointers are equal (for an odd-length string) or the start pointer is greater than the end pointer (for an even-length string).

Since this may be homework (and you seem up to speed with x86 anyway), you should perform the exercise of converting that to assembler.

---

If it turns out not to be homework, you can use the masm32 code below as a baseline. Please don't try to pass this off as your own work for education since you'll almost certainly be caught out. You'll learn a great deal more (as homework or non-homework) if you tackle the conversion yourself, I'm just providing some fall-back code if you have trouble nutting it out.

.586
.model flat

.data
source byte "This is the source string", 0

.code
_main proc
    mov     esi, offset source   ; load up start pointer.

    mov     edi, offset source   ; set end pointer by finding zero byte.
    dec     edi
find_end:
    inc     edi                  ; advance end pointer.
    mov     al, [edi]            ; look for end of string.
    cmp     al, 0
    jnz     find_end             ; no, keep looking.
    dec     edi                  ; yes, adjust to last character.

swap_loop:
    cmp     esi, edi             ; if start >= end, then we are finished.
    jge     finished

    mov     bl, [esi]            ; swap over start and end characters.
    mov     al, [edi]
    mov     [esi], al
    mov     [edi], bl

    inc     esi                  ; move pointers toward each other and continue.
    dec     edi
    jmp     swap_loop

finished:
    int     3                    ; trap to enter debugger and check string.
                                 ; replace with whatever you need.
_main endp
end _main