strlen
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.
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?
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.
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.
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).
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.
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.
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?
