Image Map Image Map
View RSS Feed

DOS / IBM PC Programming

Fast String Reverse in Assembler

Rate this Entry
I became interested in string reversal, a common interview question I remember getting, while investigating methods of converting integers to strings. In the discussion thread I started [1] I used disassembled code from MSC 5.1's itoa() routine. I always feel guilty using someone else's code verbatim in projects written from scratch, even if it was assembly code. Below is the inner loop (14 bytes) assuming a load address of 0x100 using DEBUG.

Code:
0100 DEC DI
0101 LODSB
0102 XCHG AL, [DI]
0104 MOV [SI-01], AL
0107 LEA AX, [SI+01]
010A CMP AX, DI
010C JB 0100
I learned a lot from this, the first being that LEA is supported on the 8088/86 whereas I had made a (bad) assumption that it was added in the 286. But its presence here was curious since it was simply being used to put SI+1 in AX and use that to compare against DI.

Forum member dreNorteR noted just that: the extra instruction and comparison was entirely unnecessary. Of course, I had to test this for myself. Sure enough, if you change the code very slightly, reducing its length to 11 bytes, it runs fine!

Code:
0100 DEC DI
0101 LODSB
0102 XCHG AL, [DI]
0104 MOV [SI-01], AL
0107 CMP SI, DI
0109 JB 0100
To use this and the previous code fragment, set SI to the first character of the string and DI to the null terminator (SI+length).

There are still ways to speed this up, though. I could sacrifice a bit of code size and the CX register to combine the CMP/JB ...

Code:
0100 MOV CX, DI
0102 SUB CX, SI
0104 SHR CX, 1
0106 DEC DI
0107 LODSB
0108 XCHG AL, [DI]
010A MOV [SI-01], AL
010D LOOP 0106
That adds quite a few setup cycles though, about 24 cycles if you consider an empty prefetch queue and each instruction byte takes 4 cycles to be fetched. This would be faster on longer strings but probably not the two or three digit numbers used by itoa().

Let me know if you have your own ideas to speed this up!

Footnotes:
[1]. http://www.vcfed.org/forum/showthrea...thods-for-8088

Submit "Fast String Reverse in Assembler" to Digg Submit "Fast String Reverse in Assembler" to del.icio.us Submit "Fast String Reverse in Assembler" to StumbleUpon Submit "Fast String Reverse in Assembler" to Google

Categories
Asm

Comments