4
\$\begingroup\$

I wrote my own implementation of strlen and strcmp from C in x86 FASM and I would like to know is there anything that should be changed or improved.

strlen needs string in eax and is returning length of that string into ebx.

strlen:
    mov ebx,0
    strlen_loop:
        cmp byte [eax+ebx],0
        je strlen_end
        inc ebx
        jmp strlen_loop
    strlen_end:
        inc ebx
        ret

strcmp needs two strings (one in eax, other in ebx) and returns into ecx 0 if strings are equal or 1/-1 if they are not.

strcmp:
    mov ecx,0
    strcmp_loop:
        mov byte dl,[eax+ecx]
        mov byte dh,[ebx+ecx]
        inc ecx
        cmp dl,0
        je strcmp_end_0
        cmp byte dl,dh
        je strcmp_loop
        jl strcmp_end_1
        jg strcmp_end_2
    strcmp_end_0:
        cmp dh,0
        jne strcmp_end_1
        xor ecx,ecx
        ret
    strcmp_end_1:
        mov ecx,1
        ret
    strcmp_end_2:
        mov ecx,-1
        ret
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Does the current code work as expected? \$\endgroup\$ – Mast Jan 1 at 13:43
  • \$\begingroup\$ Its not full code that u can compile and run, but only code of my implementations of that functions. I checked both codes and I'm getting expected results, so I think it works. \$\endgroup\$ – DeBos99 Jan 1 at 13:47
  • \$\begingroup\$ Unless I am mistaken, strcmp does not return ecx=0 for identical strings. – strlen seems to include the trailing zero in the count, which is unconventional. \$\endgroup\$ – Martin R Jan 1 at 18:03
  • \$\begingroup\$ I think that strcmp should return 0 for identical strings (quora.com/What-does-strcmp-mean-in-C++). In my implementation strlen includes trailing zero, so you don't need to add 1 to length everytime when you want to print this string \$\endgroup\$ – DeBos99 Jan 1 at 18:06
  • 1
    \$\begingroup\$ @DeBos: What I meant is that your implementation does not return zero for identical strings, but the current value of ecx. Perhaps I am overlooking something? \$\endgroup\$ – Martin R Jan 1 at 18:08
3
\$\begingroup\$

Is the implementation complete?

From the manual pages of strcmp()

The strcmp() and strncmp() functions return an integer less than, equal to, or greater than zero if s1 (or the first n bytes thereof) is found, respectively, to be less than, to match, or be greater than s2.

Now if we take your strcmp function we have

strcmp:
    mov ecx,0
    strcmp_loop:
        mov byte dl,[eax+ecx]
        mov byte dh,[ebx+ecx]
        inc ecx
        cmp dl,0
        je strcmp_end_0
        cmp byte dl,dh
        je strcmp_loop
        jl strcmp_end_1
        jg strcmp_end_2
    strcmp_end_0:
        cmp dh,0
        jne strcmp_end_1
        xor ecx,ecx
        ret
    strcmp_end_1:
        mov ecx,1
        ret
    strcmp_end_2:
        mov ecx,-1
        ret

The first string goes to eax and the second to ebx. When eax is shorter than ebx, the null byte of eax is read first so. cmp dl,0 is going to be true first. Therefore, it jumps to strcmp_end_0. At strcmp_end_0 if ebx has got any other byte than 0, the function returns 1. But if string in eax is smaller than ebx, it should return an integer less than 0.

Also suppose the strings were:

eax=[0x03,0x03,0x04,0x00] and ebx=[0x03,0x03,0x03,0x00]

cmp byte dl,dh at the third byte is +ve. Therefore,after jg strcmp_end_2 the function returns -1. Shouldn't it return 1 since eax>ebx?

A simple fix would be to move eax to dh and ebx to dl.

\$\endgroup\$
  • \$\begingroup\$ I think you are right. I'll just swap 1 and -1 and it should be good now. \$\endgroup\$ – DeBos99 Jan 1 at 19:11
2
\$\begingroup\$

strlen

  • We generally prefer smaller instructions. To zero the EBX register we normally use xor ebx, ebx. This is a 2-byte instruction where mov ebx, 0 is a 5-byte instruction.
  • Loops get faster if they include less jumping. Your strlen_loop has 2 jump-instructions per iteration. You can easily do this with a single conditional jump-instruction.

Next code does exactly what your code does. Notice that by placing the inc ebx instruction early in the loop, you no longer need the separate inc ebx to include the terminating zero in the returned count.

; IN (eax) OUT (ebx=1+)
strlen:
    xor     ebx, ebx
  strlen_loop:
    inc     ebx
    cmp     byte [eax+ebx-1], 0  ; Zero-terminator ?
    jne     strlen_loop
    ret

Usually the returned count does not contain the terminating zero. Next code will deal with that situation:

; IN (eax) OUT (ebx=0+)
strlen:
    xor     ebx, ebx
    dec     ebx
  strlen_loop:
    inc     ebx
    cmp     byte [eax+ebx], 0    ; Zero-terminator ?
    jne     strlen_loop
    ret

The 2 instructions xor ebx, ebx and dec ebx in a row are still shorter than mov ebx, -1.


strcmp

  • Characters in a string are to be considered as unsigned quantities. Therefore you should not use the jl (jump if less) nor the jg (jump if greater) instructions.
    For unsigned comparisons we use jb (jump if below) and ja (jump if above).
  • To check if a register holds a zero you can test the register with itself. This produces smaller code.
  • In a sequence like je ... jl ... jg ..., the 3rd conditional jump is redundant as it is always true. This is the perfect occasion to just fall through in the program.

Next code applies these recommendations:

; IN (eax,ebx) OUT (ecx={-1,0,1}) MOD (edx)
strcmp:
    xor     ecx, ecx
  strcmp_loop:
    mov     dl, [eax+ecx]
    mov     dh, [ebx+ecx]
    inc     ecx
    test    dl, dl
    jz      strcmp_end_s1
    cmp     dl, dh
    je      strcmp_loop
    jb      strcmp_below
  strcmp_above:
    xor     ecx, ecx          ; s1 bigger than s2
    inc     ecx
    ret                       ; ECX = 1
  strcmp_below:
    xor     ecx, ecx          ; s1 smaller than s2
    dec     ecx
    ret                       ; ECX = -1
  strcmp_end_s1:
    test    dh, dh
    jnz     strcmp_below      ; s1 shorter than s2
    xor     ecx, ecx          ; s1 same as s2
    ret                       ; ECX = 0

mov byte dl,[eax+ecx]
mov byte dh,[ebx+ecx]
cmp byte dl,dh

FASM, like most assemblers, does not require you to write these redundant size tags. The name of the register DL/DH already says that the size is byte.

mov     dl, [eax+ecx]
mov     dh, [ebx+ecx]
cmp     dl, dh

It's always a good idea to write some comments in the program.
See how describing the 3 possible exits on strcmp makes for a more readable code!

\$\endgroup\$
1
\$\begingroup\$

strlen

  1. Correctness (Return Value): You are violating the convention for the strlen function, which is documented as returning the number of characters between the beginning of the string and the terminating null character without including the terminating NUL character. Your code includes the terminating NUL, given the position of the inc ebx instruction.

    This may be fine if you control both the function's implementation and its usage, but it is confusing because it defies programmers' expectations and will be a recurring source of bugs. If you're going to return a length that includes the terminating NUL, you should consider calling your function something different than strlen.

  2. Interface (ABI): All x86 calling conventions return a function's result in the eax register. Although you have documented your function as returning the result in ebx, this is utterly bizarre and is guaranteed to trip up every programmer who ever uses your code. When writing everything in assembly, you are of course free to define your own custom calling conventions, but you should only do so when there is a good reason (like an optimization possibility). I can't see a good reason here. It would be just as easy for you to arrange for your code to produce the result in eax, right where programmers will expect it to be.

    It is also somewhat unusual to pass an argument in the eax register, but calling conventions vary in which registers they use to pass arguments, so this isn't flying in the face of every convention ever and is therefore more excusable. However, when you're writing in assembly and you have the opportunity to make these types of decisions, you should consider your choices carefully: what makes the most sense? what will be the easiest to use? what will be the most flexible? what will be the most efficient? Have a good reason for your choice! In this case, passing a pointer in eax makes little sense, since eax is almost universally used for return values, and pointers are almost never going to be the return value of a function. By choosing eax as the input register, you've virtually guaranteed that every caller will need an extra mov instruction to shuffle the input parameter into the appropriate register. Why create this situation when you don't have to?

  3. Style (Indentation): The way you've indented the code, with the labels at the same level as the instructions, makes it difficult to read because all of the instructions aren't lined up. Instead, consider outdenting the internal labels (branch targets) so that they match the function name (external symbols). That will allow all instructions in the function to be lined up at the same vertical column, and thus allow anyone reading the code to skim it easily.

    (The only drawback of this is that it makes it a bit harder to determine what is a function label and what is an internal label. Judicious use of whitespace is the most effective way to combat this. I also use a naming convention that allows me to recognize the difference at a glance.)

    Also, use variable numbers of spaces between the opcode and the operands to ensure that all operands line up in vertical columns.

  4. Style (Documentation): Maybe you have extensive external documentation that accompanies these functions, but probably not. Even if you do, documentation right in the code is extremely useful, easier to maintain, and should not be forsaken without a very good reason.

    When writing functions in assembly, I use kind of a standard header containing a description, the inputs, the outputs, and the clobbers. If there are any assumptions made by the function, I will also call those out explicitly. So, in this case, following what you had documented in the question (even though I just called it into question), I'd write something like this:

    ; Determines the length of a C-style NUL-terminated string.
    ; 
    ; Inputs:   EAX = address of beginning of string buffer
    ; Outputs:  EBX = length of the string, including the NUL terminator
    ; Clobbers: <none>
    

    You should feel free to develop your own style. The important thing is having this information at the ready. Especially when programming in assembly where you can (and should) invent your own per-function custom calling conventions.

  5. Optimization (Register Clearing): There is only one circumstance in which you should use mov reg, 0, and that's when you're trying to avoid clobbering the flags (e.g., in a sequence that contains a CMOVxx or a SETxx). In all other cases, you should clear a register by XORing it with itself: xor reg, reg. Peter Cordes has written a comprehensive explanation of the reasons why here, but it's enough to just remember the rule. Basically, it's shorter (and thus faster) and it breaks dependencies (which is sometimes important, and never hurts).

  6. Optimization (Reduce Branching): When you want performance, avoid branching. That means that you should minimize branching as much as possible inside tight inner loops. strlen is the canonical example of a tight loop. You've got two branches inside of the loop, a conditional je and an unconditional jmp. Consider rearranging the code so that you only have one. This is almost always possible. Ideally, you want the common case to fall through and the unusual case to branch, but even if that's not possible, it's still better to have a single branch than several of 'em.

  7. Optimization (Elide Repeated Instructions): You've repeated the inc ebx instruction. Consider how the code can be rearranged to avoid the need to do this. This isn't just the standard DRY advice, but a potential optimization opportunity. However, sometimes this trades off with the previous advice about reducing branching. Repeating a simple instruction in order to avoid a branch is virtually always worth it. As is arranging code so that you, say, speculatively increment inside of the loop, only to undo it by decrementing outside of the loop.

  8. Optimization (Memory Access): In C terms, your code is maintaining an "index" into the string. That means you have to do a complex load-and-compare (cmp byte [eax+ebx], 0). You could instead maintain a "pointer" into the string, which would allow you to just do cmp byte [eax], 0. This is not only 1 byte shorter, but may execute more quickly.

Consider:

; Determines the length of a C-style NUL-terminated string.
; 
; Inputs:   EBX = address of beginning of string buffer
; Outputs:  EAX = length of the string, including the NUL terminator
; Clobbers: CL, flags
strlen:
    lea    eax, [ebx + 1]

strlen_loop:
    mov    cl, byte [eax]
    inc    eax
    test   cl, cl
    jnz    strlen_loop

    sub    eax, ebx
    ret

This is about the most efficient way of implementing a standard strlen function:

  • The lea is used as a super-mov, allowing the value in ebx to be copied into eax, while simultaneously incrementing it by 1. (Although mov+inc would have been the same length in terms of bytes, lea might be slightly more efficient on certain processors.) ebx will remain a pointer to the beginning of the string, while eax will be a pointer to the current location in the string.
  • Inside of the loop, the CISC-style cmp instruction that took a memory operand has been split up into separate RISC-style mov+test instructions for improved scheduling. In particular, this means we can do an inc of the pointer after loading the value that it pointed to. We couldn't do the inc after the cmp, because the inc would clobber the flags (in particular, the zero flag) that we were going to try and read. In this arrangement, the test can also macro-fuse with the jnz instruction.
  • I've written jnz instead of jne even though they result in identical opcodes because I think it's a better mnemonic in this case. We are testing the value, and then jumping if it is not zero (i.e., if the current character is not the NUL character).
  • Outside of the loop, we do a final subtraction of the current pointer from the starting pointer, which gives us the length of the string, not including the terminating null.

The biggest drawback is that we've introduced the use of an additional register (the 8-bit cl), which expands our "Clobbers" list in the documentation. See why documenting this is important? The only reason why this would be a drawback, of course, is if the caller/consumer of this function needed to preserve the value in cl, as that would require an extra instruction or two. However, those instructions would be outside of the loop, and thus off the critical path, so it's almost certainly worth it for the optimizations gained.

Interestingly, this is basically the same code that Microsoft's C compiler will emit for a strlen operation when you have intrinsics enabled (otherwise, it'll generate a call to the strlen standard library function, which has essentially this same code inside of it).

This is better than Sep Roland's optimized implementation because it avoids the AGI stall introduced by this sequence of instructions in Sep's code:

inc     ebx
cmp     byte [eax+ebx-1], 0

Sep is being similarly clever here, doing the inc first and then undoing it inside of the cmp to avoid clobbering flags, but modifying ebx immediately before you use it in the addressing operands list for cmp results in a potential stall. Reordering the instructions avoids the stall; even though we had to add one extra instruction, the performance improvement more than makes up for it (unless you're optimizing for size, which you aren't, unless you're code-golfing—it's only a 1-byte difference).

So, this looks pretty good, right? Indeed, it is. As I said, it's about the best you're going to do for a straightforward, literal translation of strlen into assembly. But if you stretch your mind a bit, you can do better.

The slowest part of this code is the mov cl, byte [eax] instruction that accesses memory at the beginning of every iteration of the loop. There's nothing we can do about the fact that we have to access memory, but notice that we're only reading 1 byte at a time here. Under the hood, the processor only does DWORD-sized reads, so it's actually reading 4 bytes and then throwing away all but the lowest-order byte. Why don't we just read 4 bytes at a time? Then, we can parallelize the code to actually deal with 4 bytes at a time, effectively unrolling the loop by a factor of 4.

The trick to parallelizing the code is figuring out an efficient way of checking all 4 of the bytes that we load in each iteration of the loop for NUL characters.

One possible attempt is the following (MASM syntax, sorry):

; Determines the length of a C-style NUL-terminated string.
; 
; Inputs:   EBX = address of beginning of string buffer
; Outputs:  EAX = length of the string, including the NUL terminator
; Clobbers: ECX, flags
strlen:
  mov   ecx, ebx

ALIGN 16
CountChars:
  mov   eax, DWORD PTR [ecx]   

  test  al,  al                
  jz    SHORT ReturnLength     
  inc   ecx

  test  ah,  ah                
  jz    SHORT ReturnLength     
  inc   ecx

  test  eax, 0x00FF0000        
  jz    SHORT ReturnLength     
  inc   ecx

  test  eax, 0xFF000000        
  jnz   SHORT CountChars    

ReturnLength:
  sub   ecx, ebx               
  mov   eax, ecx  
  ret             

I've introduced an alignment of the branch target (CountChars) because aligned branch targets are more efficient, and it makes a measurable difference here because we're branching to that location a lot (each time we loop). When optimizing for code speed over size, this is a no-brainer.

There are obvious variations on this theme, especially with regard to register assignment. You might ask, why not use eax for the pointer to the current location in the string buffer, as that would eliminate the need for the penultimate mov instruction. There is a good reason I didn't, though: using eax to hold the character being tested inside of the loop makes the latter two test instructions (the ones that use immediate operands) 1 byte shorter than if any other register had been used. (Certain x86 instructions have optimized encodings when eax is the destination register for legacy reasons.) This doesn't normally matter too much, but it can help to ensure that a loop fits entirely within the cache. A 2-byte mov outside of the loop is a small price to pay for a 2-byte size reduction of the code inside the loop.

Details aside, this does get the job done with respect to testing 4 bytes at a time. But is it efficient? It feels like it might not be, because there's so much branching. Indeed, our "avoid branches in inner loops" intuition is right on, as this version is not significantly faster than the original. On modern architectures like Haswell, it's slightly faster; on older architectures, like Pentium 4 (where branch mispredictions are extremely expensive due to extremely long pipelines), it is slightly slower. In either case, the time delta is not even enough to matter. So this appears to be a dead-end. We bought ourselves a little bit of performance by reading a DWORD at a time, instead of a single byte, but any advantage gained is lost to all of the conditional branches that need to be executed each iteration of the loop.

In order to gain a real performance improvement, we need to take a different tack. And it needs to be one that reduces the number of branches. If we can find a branchless way to test all 4 bytes of the DWORD at once to see if any of them are 0 (a NUL byte), then we can reduce the number of branches in all but one iteration of the loop by a factor of 4. As it turns out, there is a solution for this, as described on the Bit Twiddling Hacks page.

Consider the following implementation (again in MASM syntax). It retrieves a DWORD and performs a series of bit manipulations on that value to determine if any of its byte are zero (i.e., contain NUL characters). If not, it branches back to the top and starts over with another DWORD-sized chunk of the string. If so, then it falls through and tests each of the four individual bytes (or, more accurately, three of the individual bytes, since if the low-order three bytes are non-zero, then we know the highest-order byte must be zero).

; Determines the length of a C-style NUL-terminated string.
; 
; Inputs:   EBX = address of beginning of string buffer
; Outputs:  EAX = length of the string, including the NUL terminator
; Clobbers: ECX, flags
strlen:
  mov  ecx, ebx               ; save pointer to beginning of string for later

ALIGN 16
CountChars:
  mov  eax, DWORD PTR [ebx]   ; load DWORD value from current offset
  add  ebx, 4                 ; increment offset by number of bytes processed
  and  eax, 0x7F7F7F7F        ; mask out highest bit of each byte
  sub  eax, 0x01010101 
  test eax, 0x80808080        ; TEST to ensure macro-op fusion with JZ
  jz   SHORT CountChars       ; if none of these 4 bytes were 0, start again with 4 more

  mov  eax, DWORD PTR [ebx-4] ; load previous 4 bytes (the ones we were just testing),
                              ;   using an immediate offset to compensate for eager
                              ;   increment in the loop while avoiding an AGI stall

  test al, al                 ; test low byte for NUL
  jz   SHORT ReturnLength
  inc  ebx                    ; wasn't the first byte, so increment byte count

  test ah, ah                 ; test the second byte for NUL
  jz   SHORT ReturnLength
  inc  ebx                    ; wasn't the second byte, so increment byte count

  test eax, 0x00FF0000        ; test the third byte for NUL
  jz   SHORT ReturnLength
  inc  ebx                    ; wasn't the third byte, so has to be the fourth (high) byte

ReturnLength:
  lea  eax, [ebx - 4]         ; undo the eager 4-byte increment; put result in EAX
  sub  eax, ecx               ; subtract starting pointer from current pointer
  ret

As it turns out, this is precisely the parallelization strategy taken by GLIBC (the C standard library implementation used by the GNU project, including the GCC compiler). The relevant code, including extensive descriptive comments, is available here; see also http://stackoverflow.com/q/20021066 and http://stackoverflow.com/q/11787810. This parallelized implementation is significantly faster on all x86 architectures than our previous "best" code—you're looking at around a 2× speedup.

I was pretty proud of this, until I thought some more and realized that there's no need to retest each of the 4 bytes. They were already tested in the initial bit-twiddling, and our answer about which of those 4 bytes contains the 0 is already available in the result of that bit-twiddling—we just need to extract it! This is great, because it eliminates three more branches, the three least likely to be correctly predicted (which of the 4 bytes actually contains the NUL is essentially random), and also the three most likely to enact a performance cost (since they are all back-to-back). It also saves us from having to reload the same 4 bytes again from memory.

; Determines the length of a C-style NUL-terminated string.
; 
; Inputs:   EBX = address of beginning of string buffer
; Outputs:  EAX = length of the string, including the NUL terminator
; Clobbers: ECX, flags
strlen:
  mov  ebx, DWORD PTR [psz]
  xor  ecx, ecx

ALIGN 16
CountChars:
  mov  eax, DWORD PTR [ebx+ecx]
  add  ecx, 4  
  and  eax, 0x7F7F7F7F
  sub  eax, 0x01010101
  and  eax, 0x80808080 ; must be AND here b/c we need result (but may not fuse)
  jz   SHORT CountChars

  ; At this point, EAX will contain one of the following values:
  ;  - 0x80808080 (if the low byte---byte 0---contained the 0)
  ;  - 0x80808000 (if byte 1 contained the 0)
  ;  - 0x80800000 (if byte 2 contained the 0)
  ;  - 0x80000000 (if the high byte, byte 3, contained the 0)
  bsf  eax, eax        ; find the first set bit, which gives either 7, 15, 23, or 31
  sub  ecx, 4          ; undo the eager increment by 4 from the loop
  shr  eax, 3          ; shift right by 3 (7 => 0, 15 => 1, 23 => 2, 31 => 3),
                       ;   thus giving the index of the NUL byte
  add  eax, ecx        ; add that byte index to the length, thus giving total length
  ret

This doesn't actually save a whole lot of time compared to the branching version, since the compare-and-branch sequence only gets executed once for each string. But, it does generally provide a minor performance boost, and it is never slower. This is true for all string lengths; there's no hidden overhead. Most of the cost comes from the relatively-expensive BSF operation. And, note that BSF is slower on AMD processors than Intel, so this code may be slightly less optimal on AMD, especially since AMD tends to use shorter pipelines and thus have less expensive branch mispredictions.

Now, I won't say that this is the fastest possible implementation, because there ain't no such thing as the fastest code, but it's pretty respectable. I'd even say it's about as good as you're going to get with bog-standard x86 instructions.

There is another frontier, and that is to use SIMD instructions (whether MMX, SSE 2, or SSE 4.2). This makes possible further substantial speed improvements, but my answer is much too long already, so I'll have to leave this stone unturned, since it is even more complicated to explain.

[NOTE: There's a fair amount of hand-waving in this answer with regards to which optimizations are sensible and what the performance differences are. I've actually done extensive benchmarking of this exact code before, on a variety of different x86 family architectures (mostly Intel), but I've left those details out of this answer for brevity (hah!). You'll just have to take my word for it. Or ask a question about it on Stack Overflow.]


strcmp

Aren't you tired of reading yet?

\$\endgroup\$
  • \$\begingroup\$ Thanks for review @Cody Gray. I'm very thankful for this big piece of advice for me. \$\endgroup\$ – DeBos99 Feb 16 at 23:45
  • \$\begingroup\$ Already an impressive review but I found several problems with the presented code snippets. The 1st snippet will not digest an empty string because the first byte of the buffer is never read. This could lead to memory access problems as well. The 2nd snippet does not traverse the buffer in steps of 4 bytes because there're but 3 inc ecx 's. You'll want the extra inc ecx right before test al, al. The 3rd and 4th snippets don't return the length including the terminating zero as is stated under "Outputs: ... ". \$\endgroup\$ – Sep Roland Feb 21 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.