strchr - AugustinLopez/libft GitHub Wiki
From The Open Group Base Specifications issue 7, 2018:
#include <string.h>
void *strchr(const char *s, int c);
- The strchr() function shall locate the first occurrence of c (converted to a char) in the string pointed to by s.
- Upon completion, strchr() shall return a pointer to the byte, or a null pointer if the byte was not found.
- No errors are defined.
Relevant concepts: Operator precedence, type casting, const keyword
#include <string.h>
char *ft_strchr(const char *s, int c)
{
if (*s == c)
return ((char *)s);
while (*(s++))
if (*s == c)
return ((char *)s);
return (NULL);
}
For more information, please refer to the Optimization Concepts page.
#include <string.h>
#include <stdint.h>
char *ft_strchr(const char *s, int c)
{
const uint64_t *pll;
uint64_t one_each_byte;
uint64_t c_each_byte;
uint64_t zero_mask;
while ((uintptr_t)s & 0x7)
{
if (*s == (char)c)
return ((char *)s);
if (!*s++)
return (NULL);
}
pll = (const uint64_t *)s;
one_each_byte = 0x0101010101010101L;
c_each_byte = c | (c << 8);
c_each_byte |= c_each_byte << 16;
c_each_byte |= c_each_byte << 32;
while (1)
{
zero_mask = *pll ^ c_each_byte;
if (((zero_mask - one_each_byte) & ~zero_mask) & (one_each_byte << 7))
break ;
else if (((*pll - one_each_byte) & ~*pll) & (one_each_byte << 7))
break ;
++pll;
}
s = (char *)pll;
if (*s == c)
return (s)
while (*(s++))
if (*s == c)
return (s);
return (NULL);
}
- Results are a percentage of the performance against a glibc strchr.
- Compiler is gcc [Apple LLVM version 10.0.1 (clang-1001.0.46.4)].
- for each size the test runtime is 5 seconds.
| Size\flag | -O3 -fno-builtin | -O2 | -Os | (none) |
|---|---|---|---|---|
| 1 | 98% | 100% | 101% | 99% |
| 10 | 100% | 100% | 100% | 97% |
| 100 | 94% | 93% | 90% | 73% |
| 1K | 64% | 63% | 63% | 22% |
| 10K | 21% | 21% | 21% | 4% |
| 100K | 11% | 11% | 11% | 2% |
| 1M | 13% | 13% | 13% | 2% |
| Size\flag | -O3 -fno-builtin | -O2 | -Os | (none) |
|---|---|---|---|---|
| 1 | 100% | 99% | 98% | 98% |
| 10 | 102% | 99% | 99% | 95% |
| 100 | 96% | 97% | 97% | 87% |
| 1K | 81% | 81% | 81% | 60% |
| 10K | 41% | 42% | 41% | 19% |
| 100K | 26% | 26% | 26% | 10% |
| 1M | 30% | 30% | 31% | 12% |
# include <time.h>
# include <string.h>
# include <stdlib.h>
size_t strchr_speed_test(int len, int second, char *(str)(const char *, int))
{
clock_t chrono = 0;
clock_t start = 0;
size_t i = 0;
void *buff;
if (!(buff = malloc(len + 1)))
exit(1);
memset(buff, 2, len + 1);
((char *)buff)[len] = 1;
((char *)buff)[len + 1] = 0;
start = clock();
while (chrono < second * CLOCKS_PER_SEC)
{
str(buff, 1);
i++;
chrono = clock() - start;
}
free(buff);
return (i);
}