# "Fast strlen" in C using scalar bithacks

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 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 */
/* subtract 0x01 from each byte,
giving a set high bit if it
was zero */
ctr++;
/* Test for the set high bit
and if it is found exit */

/* 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?

• 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.

• By the way, shouldn't cptr - str appear in the calculations after the main loop as well? Nov 7 '19 at 20:43
• @harold Oh, of course. That explains the issue I was having. Thank you. Nov 7 '19 at 21:13

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 used &, not &&. The cast to uintptr_t was intentional. Nov 6 '19 at 21:27
• @JL2210 I see the single &. (Amended answer as part of the answer did act like && - that part was in error) The cast to uintptr_t does not yield a specified value in which bit-wise adding with (sizeof(uint32_t)-1)) results is a specified alignment test. AFAIK, this is no specified alignment test. Nov 6 '19 at 21:55
• That's a really opaque way to do alignment; I don't like the assumption that sizeof (uint32_t) must be a power of two. One can imagine an (admittedly not "common") implementation with CHAR_BIT == 12, and sizeof (uint32_t) == 3. C++ has std::align(); it might be worth creating a similar function here. Nov 7 '19 at 9:25
• @TobySpeight CHAR_BIT == 12, sizeof (uint32_t) == 3 is not possible: uint32_t cannot have padding. sizeof (uint32_t) must be a power of two. With CHAR_BIT == 12, The optional type uint32_t cannot be defined. Yet the larger issue is that an aligned pointer, when converted to an integer, is not specified to a value with lower bits of 0. That is just common implementation. Exotic example per OP's "possibly some uncommon ones?": the least significant bit of the (uintptr_t)cptr could be the parity of the address - not useful for determining alignment. Nov 7 '19 at 11:15
• I feared this when I wrote the code. I'll keep working on it. Nov 7 '19 at 17:33

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

• That solution doesn't work. Now it gives 7 for a string like "\x80It works!". Nov 7 '19 at 18:17
• @JL2210 it correctly detects zeroes. Nov 7 '19 at 18:35
• Mine correctly detects zeroes too. Nov 7 '19 at 18:37
• i - LOW_MASK & ~i & NOT_HIGH_MASK appears to evaluate as ((i - LOW_MASK) & (~i)) & NOT_HIGH_MASK. Is that your intent? Nov 7 '19 at 19:37
• @chux-ReinstateMonica yes, the original had parentheses around the subtraction but they are redundant. Nov 7 '19 at 19:48

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.

• I could've sworn that I said "For context, this is part of a standard C library implementation." Nov 5 '19 at 12:04
• @JL2210 Yeah but you never mention compiler options, so I have to assume standard C. Nov 5 '19 at 12:06
• I've added a small clarification to the question. It doesn't seem as if strict aliasing affects this at all... Nov 7 '19 at 20:29