Why does the FreeBSD memchr implementation increase its pointer in its state?

Question

General implementation of FreeBSD memchr :

 void * memchr(const void *s, int c, size_t n) { if (n != 0) { const unsigned char *p = s; do { if (*p++ == (unsigned char)c) return ((void *)(p - 1)); } while (--n != 0); } return (NULL); } 

which seems unnecessarily complicated to me; an initial test of n != 0 with do - while , to avoid declaring p , seems completely pointless. However, I am particularly interested in why the body of the loop:

 if (*p++ == (unsigned char)c) return ((void *)(p - 1)); 

instead of simpler:

 if (*p == (unsigned char)c) return ((void *) p); ++p; 

Does the incremental post subject to some optimization for some compilers / platforms?

Answer 1

The case of pointer-to-pointer is to allow era compilers (like PCC) to use automatic incremental addressing on DEC machines (like Mark Plotnick mentions in a comment).

Since all DEC machines support auto-increment addressing, this method of encoding loops was once very common (BTW, m68k supports the same optimization).

The do-while , on the other hand, is simply because it tends to give better code in the naïf compiler, rather than just not setting p .

No difference should be different from a modern compiler.

Answer 2

First: This is pure speculation. I have not written this code and cannot confirm my guess.

There is one very important semantic difference between these two versions of code:

 // Version A if (*p++ == (unsigned char)c) return ((void *)(p - 1)); // Version B if (*p == (unsigned char)c) return ((void *) p); ++p; 

In version A, the increment is sequenced before the code block of this if , while in version B it is sequenced after this block.

Thus, in version A, the increment code will be placed before the jump command, which is most likely generated from if . At least we can assume that such a relatively direct translation from C code to assembly from compilers of the time the code was written (1988?).

Does the conditional increment nest have some optimizations for some compiler / platform?

Having incremented before the branch allows for relatively simple optimization on architectures that have a delay slot in the branch instructions: you can move the increment to this delay slot instead of having a NOP.

Thus, version A requires one less instruction for each iteration of the loop than version B, due to one decrement when the function returns. This is (micro) optimization.