"Fast strlen" in C using scalar bithacks

Question

I've translated an implementation of strlen in x86 assembly to C and added alignment checking:

#include <strings.h>
#include <string.h>
#include <stdint.h>

#define NOT_HIGH_MASK 0x080808080
#define HIGH_MASK 0x7f7f7f7f
#define LOW_MASK 0x01010101
#define mul4(x) ((x) << 2)
#define div8(x) ((x) >> 3)

size_t strlen(const char *str)
{
    const char *cptr = str;
    uint32_t i, *s;
    size_t ctr = 0;

    /* Satisfy alignment requirements */
    while((uintptr_t)cptr & (sizeof(uint32_t)-1))
    {
        if(!*cptr)
            return cptr - str;
        cptr++;
    }

    s = (uint32_t *)cptr;

    do {
        i = s[ctr];
        /* Mask off high bit */
        i &= HIGH_MASK;
        /* subtract 0x01 from each byte,
           giving a set high bit if it
           was zero */
        i -= LOW_MASK;
        ctr++;
            /* Test for the set high bit
               and if it is found exit */
    } while(!(i &= NOT_HIGH_MASK));

    /* Find the first high bit set and
       create the corresponding byte index */
    i = div8(ffs(i));
    /* Remove the counter increment from the
       loop and multiply it by 4 to find the
       rest of the byte index */
    ctr = mul4(ctr - 1);

    /* Return the combined byte index with 1
       removed so it doesn't include the null
       terminator itself */
    return i + ctr - 1;
}

I'm looking for general critique, but I'd also like additional information in these areas:

• Portability. Is this portable? Will it work on all common platforms (x86, arm, etc.) and possibly some uncommon ones?

• Comments. The comments I've put here seem to already document the code well enough, but is there any additional information I could add?

• Hidden Bugs. This definitely works (and has a noticeable improvement in speed), but are there any hidden bugs relating to alignment requirements or otherwise (such as extended ASCII)? For context, this is part of a standard C/POSIX library implementation.

I might note that I'm relying on my header to use the builtin version of ffs. This may be an issue on non-GNU compilers.

If a GCC-compatible compiler (gcc, clang, icc, etc.) is detected during the build process, the flags -std=gnu99 -O2 are appended to the build flags.

Answer 1

Bug

strlen("\x80\x80\x80\x80\x80\x80\x80") does not return the expected 7. The do loop does not distinguish between '\0' and '\x80'.

strlen("\x80\x80\x80") returns 0, 1, 2 or 3 depending on alignment.

These render the function broken.

Why int32_t?

Certainly int32_t* marches down the sting at a 4x clip rather than a plodding char *. Yet for a 16-bit int machine, int32_t* may be slower. For a 64-bit machine, int64_t* could even be faster. I'd expect a unsigned * to work fast or even fastest. I guess that is why strlen() is a library function - each implementation is expected to use its own optimal approach.

Minor: Clearly use unsigned mask constants

With bit masking, shifts and subtraction, using unsigned math has less review concerns.

0x01010101 --> 0x01010101u.

Portability

while(... & (sizeof(uint32_t)-1)) is a reasonable alignment test but not a specified correct one. Conversion of a pointer to an integer need not follow the usual linear expectations. I do not know of any implementation where this will not work, but it is not C specified.

Notes:
uint32_t is an optional type. A unicorn platform may not have it defined.
uintptr_t is also an optional type.

Could use something like

#include <stdint.h>
#ifndef UINTPTR_MAX
  #error "You are kidding me? An implementation without uintptr_t!" 
#endif

Comment nit

Mask off high bit should be "Mask off high bits" or "Mask off each byte high bit", ...

/* Mask off high bit */
i &= HIGH_MASK;

Answer 2

As noted, the zero detection trick would also detect any 0x80 bytes (€ in CP1252, various different characters in UTF-8 contain 0x80 as continuation byte, for example Hiragana mu: む = "\xE3\x82\x80") as if they were zero-terminators. There are slightly more expensive "contains zero byte" checks that avoid this, for example (sprinkle with parenteses as desired):

i = i - LOW_MASK & ~i & NOT_HIGH_MASK;

That replaces 3 operations from the original, so it's not that costly, and additionally it could be used as fallback test after the simpler test thinks it has found a zero (though that is not favourable for strings with many 0x80 in them). It's not a straight upgrade, so it's for you to weigh the trade-off.

This uses the definition #define NOT_HIGH_MASK 0x80808080 as used in this question, not HIGH_MASK = 0x80808080 as may be expected.

This trick operates on the same basic principle as the trick in the question: subtracting 1 from 0 sets the high bit of that byte, because it can borrow all the way through, but any set bit would stop the borrow from reaching the top. However, it fixes the problem of "what if the top bit was already set" by ANDing with ~i afterwards, rather than by ANDing with HIGH_MASK = 0x7f7f7f7f beforehand (which also turns 0x80 into zero).

Answer 3

You cannot write this kind of code in standard C. It will have to be library-level code compiled with non-standard extensions.

Notably, s = (uint32_t *)cptr; is a strict aliasing violation. It invokes undefined behavior and may cause strange, subtle bugs during optimization etc. In order to get this to work reliably, you have to use non-standard options such as gcc -fno-strict-aliasing.

When dereferencing the pointed-at string as uint32_t you must also ensure that the 32-bit access doesn't go out of bounds of the allocated array.

Pedantically, you should cast the result of ffs to uint32_t, because it returns an int type which is signed and you don't want to bit shift signed numbers, even though it will always be positive in this specific case. I'd probably rewrite the macros more type-safe, along the lines of this:

#define mul4_32(x) ((uint32_t)(x) << 2)

Or, if C11 is an option:

#define mul4(x) _Generic((x), uint32_t: (x) << 2)

In either case it shouldn't affect performance.

Also please note that ffs and strings.h are POSIX but not standard C.