x86 strcpy implementation

Question

I got about 4 days of assembly knowledge, so I need a review on this strcpy function and if it can be done better (at least I have the feeling).

Full code (with the test included):

.data
    s:
        .asciz "Hello world!"

.bss
    .lcomm destination, 4

.text
.globl main
main:
    nop

    pushl $s
    pushl $destination
    call __strcpy
    addl $8, %esp

    pushl $destination
    call puts
    addl $4, %esp

    ret

.globl __strcpy
.type __strcpy, @function
__strcpy:
    movl $0xFFFF, %ecx
    movl 4(%esp), %edi
    movl 8(%esp), %esi

cpy:
    cmpl $0, (%esi)
    je done

    movsb
    loop cpy

done:
    ret

GitHub

Parts that I feel can be optimized:

1. Because the done label just executes the ret instruction:

   • cmpl $0, (%esi)
   • je done

2. Because the rep instruction-family seems a like better approach:

   • movsb
   • loop cpy

Answer 1

You can use Bit Twidding Hack to determine if int32 or int64 has no zero bytes: http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

If it has not you can copy whole int32 or int64. So it will be 4 operations for searching zero byte in 8 bytes (in int64 case). It looks like true optimization.

char * strcpy(char * dst, const char * src)
{
    char * origin = dst;

    while (!((((*(uint64_t *)src) - 0x0101010101010101ULL) 
           & ~(*(uint64_t *)src) & 0x8080808080808080ULL)))
    {
        *(uint64_t *)dst = *(uint64_t *)src;
        src += 8;
        dst += 8;
    }

    while (*dst++ = *src++)
       ;

    return origin;
}

Simple strcpy implementation uses 8 compares to zero and 8 byte copyings for each 8 bytes of source string. My implementation uses 4 operation for checking for zeros and 1 operation to copy for 8 bytes. So we have 5ops vs 16ops. Not all ops have same speeds so it is not easy to compare real speedup. We need some benchmarks, is anyone free?

Answer 2

Your __strcpy assembler function seems to

• copy at most 0xffff bytes
• not to copy the terminating \0

A normal string copy would copy any number of bytes and would include the \0.

It is often good to learn from what the compiler gives you from a C function. You can do this with the -S option to gcc. For example this line will compile code.c into assembler file code.s

gcc -S -o code.s -O3 -Wall code.c

The -O3 sets the optimization level (high).

Also if you omit the length check, you should be able to arrange your loop so that there is only one branch instruction (branches are expensive).

Answer 3

I apologize for my lack of GCC fluency in advance - I have only used MASM and RosAsm for x86, but I will try to translate. This review will be in top-to-bottom order, not in order of importance.

The first thing I would do is evaluate whether you really need to use cdecl calling convention. If you're only calling your function from asm, it makes sense to pass the source and destination in esi and edi, respectively, rather than putting them on the stack and then loading them.

Next, instead of movl %ecx, $0xFFFF, I would do:

xorl %ecx, %ecx
decl %ecx

xoring a register with itself is such a common idiom that some processors use it as an optimization hint. All it does is set the register to zero, with a smaller opcode & operand. The dec after the xor makes the register all 1 bits no matter how many bits your register actually has. Some day when all of our GPRs are 128 bits, some poor sap that is updating assembly code will thank you for that =D.

Alternatively, you can forget about ecx being a limit altogether. No matter what arbitrary limit you set on the size of the string, it will either (1) not be big enough for someone someday, or (2) be small enough that an access violation (or worse: no access violation) will occur before you actually reach that limit. Either way, that is really only a nominal protection of data integrity.

Now, the string. There seem to be some inconsistencies in how you're treating its terminating null character. You're using cmpl to find four bytes of 0, then using movsb to only copy/advance esi by 1. Normally, strings are only guaranteed to be terminated by a number of null bytes equal to the character size, although in practice there are probably at least 2-3 to get the next datum to be dword-aligned. What that means for you is that your code will fail to detect the end of ~3/4 of normal, null-terminated, ascii strings, and keep copying until it finally causes an access violation.

But that's not all. Notice that you're fetching a dword at esi with the cmpl instruction, and that advancing that pointer by 1 at every iteration will make the pointer not dword-aligned 3/4 of the time. Loading non-aligned data takes two fetches instead of one, so for every 4 bytes of string, your cmpl instruction alone needs 7 fetches from memory. Furthermore, after fetching the data and discarding it with cmpl, you fetch it again with movsb, a total of 11 memory loads per dword of data.

To reduce that number, you should load the data into a register, do your test for the null terminator on that register, then store the data to the destination. I see that someone else has pointed you to the bit-hack that will let you test all 4 bytes of the dword at once, so if you can follow that, do so, but here's a less efficient way that demonstrates my point very clearly:

cpy:
     lodsb          ; fetch one byte from [esi++] to al
     test %al, %al  ; set the z flag if al is 0
     stosb          ; store the byte, even if it's 0, doesn't affect flags
     jnz cpy        ; or loopnz if you still want to use a size limit in ecx

That will only require 4 fetches per dword, and is perfectly readable (as far as asm goes...). The bit twiddling hack does it with just one.

With regard to your instinct that rep family instructions would be better, I believe you're sadly incorrect. If you learn any other assembly language and try to use strings, you'll certainly appreciate the effort Intel originally put into providing special string instructions, but they haven't really optimized or extended those instructions with the same zeal as one might like. Further, you can't repnz movsb, because movsb doesn't set any flags. If you ever do end up repne scasb, remember to jecxz =D.

This might seem like a long list of complaints, but for having first seen assembly 4 days before writing this, it's remarkable that you can do anything useful. Cheers.