2017-03-08

Length at compile time

How do you get the length of a string literal in C?

The sizeof operator does its work at compile time, as we would prefer, being that we are dealing with a string literal, so we know its length already, but of course we don't want to count it by hand and hardencode it (of course; it would be a pain to maintain).

So you would write e.g.

  sizeof ("this is a string");

wherever you need the length of the string, with the obvious caveat that the sizeof operator gives the actual memory size of the string (array of chars), not its length as a C string (i.e. a NUL terminated array of chars) as strlen would do. So we need to decrease it by one, if we really want the same result of strlen.

If you need that length in several places, you likely will use a define for the string, or, maybe better, you would assign the result to a variable (type size_t, if you care) and use it consistently. Likely you will need the string itself too, not only its length; so, you have several options, some better, some worse.

But sizeof works if it deals with string literals, not with pointers to string literals, since in this case it will give the size of the pointer for your machine. The following piece of code is wrong (unless we really want the size of a pointer):

const char *p = "this is a string";
size_t len = sizeof (p);

Therefore in this case we must use strlen:

const char *p = "this is a string";
size_t len = strlen(p) + 1;

But we know that in this case the compiler could replace the function call and the sum with the result: it could know the value of strlen(p) at compile time — provided that it knows what strlen does or is supposed to do (recent gcc versions have -foptimize-strlen; what happens if you have the bad idea to use the strlen name for a function that does something different?). It is, however, something the compiler could know if it “tracks” p and confirms it is not reassigned:

const char *p = "this is a string";
// use p
p = "another string";
size_t len = strlen(p) + 1;

Perhaps this is why the compiler can't replace easily strlen with just a number. It should be a whole different situation if we had this one:

const char *const p = "this is a string";

Here we are not just saying that p is a pointer to something that is constant (a string literal won't change): we are also saying that p itself won't change, that is, the pointer will be pointing at the same thing (at least until p goes out of scope). But gcc version 5.2 without any option won't optimize it anyway. Take this code:

#include <stdio.h>
#include <string.h>

int main(void)
{
  const char *const p = "this is a string";
  printf("%zu\n", strlen(p));

  return 0;
}

and the disassembled main:

   0x0000000000400578 <+0>:     push   %rbp
   0x0000000000400579 <+1>:     mov    %rsp,%rbp
   0x000000000040057c <+4>:     sub    $0x10,%rsp
   0x0000000000400580 <+8>:     movq   $0x40069c,-0x8(%rbp)
   0x0000000000400588 <+16>:    mov    -0x8(%rbp),%rax
   0x000000000040058c <+20>:    mov    %rax,%rdi
   0x000000000040058f <+23>:    callq  0x4003f8 <strlen@plt>
   0x0000000000400594 <+28>:    mov    %rax,%rsi
   0x0000000000400597 <+31>:    mov    $0x4006ad,%edi
   0x000000000040059c <+36>:    mov    $0x0,%eax
   0x00000000004005a1 <+41>:    callq  0x4003d8 <printf@plt>
   0x00000000004005a6 <+46>:    mov    $0x0,%eax
   0x00000000004005ab <+51>:    leaveq 
   0x00000000004005ac <+52>:    retq

(On an Intel x86-64 machine, running RedHat — but this is not important — gcc version 5.2.)

If you add the -O option, the strlen will be optimized into a single mov $0x10, %esi (x86-64 ABI calling conventions for “Unix” at work here):

   0x0000000000400528 <+0>:     sub    $0x8,%rsp
   0x000000000040052c <+4>:     mov    $0x10,%esi
   0x0000000000400531 <+9>:     mov    $0x40063c,%edi
   0x0000000000400536 <+14>:    mov    $0x0,%eax
   0x000000000040053b <+19>:    callq  0x4003a0 <printf@plt>
   0x0000000000400540 <+24>:    mov    $0x0,%eax
   0x0000000000400545 <+29>:    add    $0x8,%rsp
   0x0000000000400549 <+33>:    retq   

But we obtain the same result if we remove our promise of p constantness (keeping const char *p only); this could be because the optimization realizes that p hasn't changed, even if it could have. Let's consider this. Once an intermediate code (whatever it is) gets generated, all the constantnesses are not needed anymore: something is modified, or it is not. But I want to know what the compiler does at compile time, before optimizations take place. This could be hard, because Stricto sensu, the GCC compiler middle-end is made of a sequence […] of optimization passes, so if GCC did no optimization, it won't be able to emit any code. (I don't know if the conclusion is totally true, but it is someway sound, I think.)

  char *p = "this is a string";
  printf("%zu\n", strlen(p));
  printf("%zu\n", strlen("a string"));

Even without the -O option, the second line won't be compiled into a call to strlen. By the way, I've removed every const, but it doesn't mean it makes sense (writing into the memory of a string literal usually triggers segmentation fault — usually, not always: it wouldn't happen on classical Amiga as I knew it); anyway I'm not going to execute the code, I'm just interested in the generated final code, and if const may change it or not. In this case I've tried constantness of the string pointed by p (it is what it should be on many systems), constantness of p itself (it can't be reassigned), and also static. The strlen(p) isn't optimized. So far, it seems the compiler can recognize only the case when the argument of strlen is a string literal (it's when your intention is clear and can't be misunderstood), but this is also the case when you could use sizeof (-1).

If I have a static array of constant strings I will need the length of, what could I do?

static struct {
  const char *s;
  size_t l;
} a[] = {
  { "a string 1", strlen("a string 1") },
  { "shorter", strlen("shorter") },
  { "this is longer", strlen("this is longer") }
};

This works as expected, nowhere you will see a call to strlen and nonetheless the struct member l will contain the correct value (in this case a macro is useful to avoid the manual repetition of the string, which is a bad and error prone practice). If you remove the #include <string.h>, the compiler will complain for the implicit declaration of strlen. Let's provide it by ourselves just to silence the compiler:

size_t strlen(const char *);

Everything goes fine. Let's give a wrong prototype, e.g. write int instead of size_t. The compiler will complain about conflicting types for built-in function ‘strlen’. But it will also complain for each strlen, saying initializer element is not constant. This is what we would expect if gcc weren't able to “optimize” strlen, because in fact it can't initialize data calling a function — but if the call doesn't happen because it gets replaced by a constant value, then it's ok. So strlen behaves in a special way. If we replace every strlen with mystrlen and declare

size_t mystrlen(const char *s)
{
  return strlen(s);
}

we obtain the same error (not a surprise). In gcc we could obtain what we want using a macro (see here) like this:

#define mystrlen(s) (__extension__ (__builtin_constant_p(s)  \
 ? sizeof (s) - 1 \
 : 0 )) 

Which of course gives the correct answer only when s is a string literal. When it is not, we give 0, but the compiler won't complain with initializer element is not constant.

char ss[] = "hello";

static struct {
  const char *s;
  size_t l;
} a[] = {
  // ... 
  { ss, mystrlen(ss) }
};

This will compile (with the mystrlen above), but l will be 0 for the last element; anyway when you use the real strlen, the compiler complains, as expected. As far as I know, in C there isn't a way to add behaviours on constants at compile time, namely, to do computations of any kind at compile time; e.g. given a literal string, convert it to uppercase, or lowercase. It should be done by the preprocessor, but this lacks the features to make it easily possible. Which doesn't mean it's impossible, and in fact it seems you can do interesting things with a carefully crafted set of macros. C++11's user defined literals could do these and other tricks in a more natural way. Metaprogramming is fun and powerful, but it's not carved into the nature of C or its preprocessor, thus doing it is harder than it should be.

These examples show that when you don't see the call to strlen in the generated code, it must be the effect of an optimization, unless you called it with a string literal as argument; in the latter case the “computation” could be done in the preprocessing pass, as shown by the definition of strlen according to this answer on SO.

We can check it with the -E option. It turns out we still can read strlen: on the system in use, no macro involved:

extern size_t strlen (__const char *__s)
     __attribute__ ((__nothrow__))
     __attribute__ ((__pure__))
     __attribute__ ((__nonnull__ (1)));

But the compiler doesn't get annoyed by the strlen, that is, it manages a way to compute strlen and obtain constant values suitable for an initialization. Therefore the compiler, and not the preprocessor, handles the special case when the (special) function strlen has a string literal as argument. So it seems, but we should take a look at the gears to be sure.

Is everything clear?

Then let's try another thing or two.

#include <stdio.h>
#include <string.h>

#define A_STRING "this is super"

int main(void)
{
  char super[] = A_STRING;

  printf("%zu %zu %zu\n",
    sizeof (super) / sizeof (super[0]),
    sizeof (A_STRING),
    strlen(super));

  return 0;
}

As expected, the fourth parameter to printf is compiled into a call to strlen. As expected, if we add -O or other level of optimization, the call to strlen disappears. In the generated code there's extra noise due to the fact that the code must copy the read only string into the local variable (writable) memory1.

Now let's change how super is defined.

  static const char super[] = A_STRING;

The call to strlen disappears. It is not enough to add const only, and it is not enough to add static only (this is more obvious). Both together do it. The same result is not achieved with one of the following (unless we add the optimization option):

  static const char *super = A_STRING;
  // or
  static const char *const super = A_STRING;

Why2? About clang (version 3.0), it does it differently and generates the call to strlen no matter how you defined super. Hence I daresay it depends “only” on how that kind of optimization works in gcc (while in clang I must use -O to have the strlen call replaced with the constant value).

What if I create my strlen-like function with attributes nothrow, pure and nonnull? Nothing. It gets called and not optimized out (save when I use -O2 or -O3).

Something more about it

Here it is explained that in gcc strlen has its builtin version, __builtin_strlen. It is also expained the __builtin_constant_p we used in the macro mystrlen to check if its argument was constant. Quoting:

You can use the built-in function __builtin_constant_p to determine if a value is known to be constant at compile time and hence that GCC can perform constant-folding on expressions involving that value. The argument of the function is the value to test. The function returns the integer 1 if the argument is known to be a compile-time constant and 0 if it is not known to be a compile-time constant. A return of 0 does not indicate that the value is not a constant, but merely that GCC cannot prove it is a constant with the specified value of the -O option.

I think with the specified value of the -O option saves all the cases. E.g. consider the following excerpt:

    const char *const p = A_STRING;          // (1)
    printf("%d\n", __builtin_constant_p(p));

The program outputs 0, even if const char *const says that p is a pointer that doesn't change to something that doesn't change. So, why __builtin_constant_p gives 0? Because it “cannot prove it is a constant with the specified value of the -O option. Even if with the same specified value of the -O option it raises the error assignment of read-only variable if I try to assign to p something else, e.g. p = "hello";, and guess what? It also raises assignment of read-only location if I try p[0] = '\0';. Therefore with the specified value of the -O option (zero) it stops me when I try to change it, and this should prove that it is a constant.

Caveat:

void modify(char *p)
{
    *p = 0;
}

gives a warning (discards ‘const’ qualifier from pointer target type), therefore it can't prove it is kept constant; but if I turns warnings into errors with -Werror, it should become provable — unless I use a cast, or link to an object containing a function whose prototype makes the compiler happy, but the code breaks the promise… Ok, it is right, it can't prove it. With the specified value of the -O option. But I've tried -O2 and -O3 too, and the __builtin_constant_p still gives 0.

This question is about C++11, but one answer remembers us strlen being a builtin, and suggests a test with -fno-builtin (without the final s, it exists in gcc 5.2 still). It worked as expected: if you add -fno-builtin, even strlen("hello") is compiled into a call to strlen, and it will be so even with -O3!

Conclusion: the magic is because of the nature of the builtin. No builtin, no special treatment — then it's better to write sizeof ("hello")-1, if you care. The compiler clang has a similar behaviour and accepts and complies to the -fno-builtin option.


  1. It is done moving immediate values into memory, e.g. mov $0x73696874, (%rsp). Here we see we are on a little endian CPU. In fact “this” is 74 68 69 73 (hex), but to obtain those bytes in memory on a little endian CPU, you must write the 32 bit integer 0x73696874 (that is 'shit'!)

  2. A possible late explanation: sizeof would operate correctly on char x[] — while it can't give the desired result on char *x (unless, again, we want the size of a pointer). This means sizeof is the hidden main character behind the scenes of the act when strlen disappears.

3 comments:

  1. Hi, Mauro,

    An interesting post, and the most comprehensive I've read on the web, on the subject of compile-time strlen.

    Just to offer my experiences, I'm using ARM GCC 4.9.3, as provided with the latest Infineon DAVE development platform, version 4.3.2, targetting their XMC4300 CPU.

    I tried -foptimize-strlen and/or __builtin_strlen, but unfortunately neither stopped the compile-time calls to strlen, for the following code (I need to copy a string minus it's terminating nul):

    const char *FOO = "Bar";
    strncpy( pDest, FOO, strlen(Text);

    I the end I threw in the towel, and went for the following. This removed the strlen calls, and reduced the code size as strlen library function no longer needed.

    #define FOO "Bar"
    strncpy( pDest, FOO, strlen(Text);

    So much for the benefits of const char strings!

    Best regards,

    David

    ReplyDelete
    Replies
    1. Hi, thanks for the comment.

      Have you tried `const char *const FOO = "Bar"`? (Since you are fine with a define, I suppose you don't need to reassign the pointer.)

      Anyway, notice that your code looks sospicious (maybe wrong, if it is really how you did it): the third arg to strncpy should be the size of the destination buffer (or anything shorter, for whatever reason).

      It doesn't make sense to give the len of FOO, since strncpy would stop anyway at the '\0'. If your aim is to copy the string without the trailing '\0' (hence ignoring if the dest buffer can hold the string), I think you should find other ways, at least because they can make your intentions clearer.

      Delete
  2. Oops, typo, strlen(Text); should read strlen(FOO);

    David

    ReplyDelete