Reversing a String in (ARM64) Assembly

In my last post, I showed that I could modify a single character in a string. I want to build upon that to perform more complext string manipulations. Lets start with something simple.

First, lets change a character other than the first. Since we want to reverse the string, changing the last character is a good next step. Insert this into the middle of the previous example.

    add X4, x1, x2
    sub X4, X4, #2
    strb w3, [X4]
    mov  w8, #64
    svc  #0

This produces the following output.

$ make reversed ;  ./reversed 
as -g -o reversed.o reversed.s
ld -o reversed reversed.o
Hello, WorldA

Now I need to store the value before writing it. I am going to keep two pointers, one to the start of the string, one to the end of the string. The values from those pointers will get pulled into registers and swapped.

At this point, I need to be clear about what means what. I need a clear convention for relating pointers and values. As I see it, I have two options. One, I could put all of the pointers first, and then all of the values. Two, I could put pointer s and values sequentially. Which should I chose?

I am going to put pointers and values sequentially. That way, if I decide to work on an algorithm with more than two pointers, I have a convention that scales.

  • X4 will be the pointer to the start of the string
  • X5 will be the value from that pointer
  • X6 will be the pointer to the end of the string
  • X7 will be the value from that pointer.

I am going to reorganize my current code to support that convention. The body of the code now looks like this:

    mov  x0, #1   /* fd := STDOUT_FILENO */
    ldr  x1, =msg  /* buf := msg */
    ldr  x2, =len  /* count = lent */
 
    mov  w5, #65
 
    add X6, x1, x2
    sub X6, X6, #2
    strb w5, [X6]
 
    mov  w8, #64
    svc  #0

Now, instead of hardcoding the #65 letter A, lets pull that value from the pointer.

Replace mov w5, #65 with these two lines.

    add  X4, X1, 0    
    ldrb w5, [x4]

Which produce

$ make reversed ;  ./reversed 
as -g -o reversed.o reversed.s
ld -o reversed reversed.o
Hello, WorldH

Next, lets loop through the entire string and replace it with the H from the above example. First split the sub #2 into two sub#1 commands. The first will go outside the loop, the second will go inside the loop.

To run the loop, we compare the end pointer to the start pointer. If they are pointing to the same location, we are done. If not, branch back to the start of the loop.

The portion of the code that does the loop now looks like this:

    sub X6, X6, #1
 
loop:
    sub X6, X6, #1
    strb w5, [X6]
 
    cmp X4, X6
    b.ne loop

If we advance the end pointer at the same time, we can copy over only half of the string. But….the comparison of Not equal will fail if the two pointers pass each other. Instead, we can use a branch if less than.

    cmp X4, X6
    b.lt loop

The comparison checks that the first value is less than the second. That will only stop branching when the two pointers equal each other. Since we don’t need to swap the middle character of a string, this is our correct logic.

Now, before we write the characters, we want to pull the second value out and store it. As we said before, this goes into the register one higher than the pointer for that register. So The value from the start of the string goes in w5 and the value from the end of the string goes in w7.

Where do we increment the pointer to the start of the string? At the end of the loop. However, we don’t want to split up the comparison and branch operators. Is it OK to increment before jumping to the start of the loop? Yes. Lets walk through why.

Lets write out two short versions of our string. The first will be four characters long, and will cover all of the cases where we have an even number of characters in the string:

[A][B][C][D]

In the first case, the pointer to the start of the string starts with index 0, the Character A, and the pointer to the end of the string starts with the index 4, acharacter after (A Null by convention, not shown) The first instruction inside the loop subtracts one from the pointer, to index 3 which points to the character D .

At the end of the loop, we increment the start pointer to the index 1. 1 is still less than 3, and so we branch. The end index is decremented to 2. The characters are again swapped. We increment the start point, which now also equals 2. At this point, the compare indicates we should not branch, and we exit the loop.

The second case will be three characters long, but will cover all of the cases where we have an odd number of characters in the string.

[A][B][C]

Counting through the indexs, we start with X4=3, X6=0. Enter the loop, and decrement X4=2. Swap characters, increment X6 to 1.

1 < 2 so we jump to the head of the loop. Decrement X4 to 1.

We end up swapping the middle character with itself. This is redundant.

Increment X6 to 2. The comparison of 2 < 1 fails and we break out of the loop. Our loop now looks like this.

    sub X6, X6, #1
 
loop:
    sub X6, X6, #1
 
    ldrb w5, [x4] 
    ldrb w7, [x6] 
 
    strb w5, [X6]
    strb w7, [X4]
 
 
    add X4, X4, #1
    cmp X4, X6
    b.lt loop
$ make reversed ;  ./reversed 
as -g -o reversed.o reversed.s
ld -o reversed reversed.o
!dlroW ,olleH

I can modify the string in the text section to show that both of these work. I set it to be “ABC\n” in order to get:

$ make reversed ;  ./reversed 
as -g -o reversed.o reversed.s
ld -o reversed reversed.o
CBA

In my next post, I am going to try and make it possible to run our code with several different strings to prove this.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.