memccpy - AugustinLopez/libft GitHub Wiki
From The Open Group Base Specifications issue 7, 2018:
#include <string.h>
void *memccpy(void *restrict s1, const void *restrict s2, int c, size_t n);
- The memccpy() function shall copy bytes from memory area s2 into s1, stopping after the first occurrence of byte c (converted to an unsigned char) is copied, or after n bytes are copied, whichever come first. If copying takes place between objects that overlap, the behavior is undefined.
- The memccpy() function shall return a pointer to the byte after the copy if c in s1, or a null pointer if c was not found in the first n bytes of s2.
- No errors are defined.
Relevant wiki: memcpy, memchr.
Relevant concepts: Operator precedence, type casting, const keyword, restrict keyword. The use of the restrict keyword if forbidden by the libft subject.
#include <string.h>
void *ft_memccpy(void *s1, const void *s2, int c, size_t n)
{
unsigned char *cs1;
unsigned char *cs2;
cs1 = (unsigned char *)s1;
cs2 = (unsigned char *)s2;
while (n--)
{
if ((*cs1 = *cs2) == (unsigned char)c)
return (cs1 + 1);
++cs1;
++cs2;
}
return (NULL);
}
For more information, please refer to the Optimization Concepts page.
#include <string.h>
#include <stdint.h>
void *ft_memccpy(void *s1, const void *s2, int c, size_t n)
{
unsigned char *cs1;
unsigned char *cs2;
uint64_t *lls1;
uint64_t *lls2;
uint64_t one_each_byte;
uint64_t c_each_byte;
uint64_t zero_mask;
cs1 = (unsigned char *)s1;
cs2 = (unsigned char *)s2;
if ((n >= 8) && (((uintptr_t)s1 & 0x7) == ((uintptr_t)s2 & 0x7)))
{
while ((uintptr_t)cs1 & 0x7)
{
if ((*cs1 = *cs2) == (unsigned char)c)
return (cs1 + 1);
++cs1;
++cs2;
--n;
}
lls1 = (uint64_t *)cs1;
lls2 = (uint64_t *)cs2;
one_each_byte = 0x0101010101010101L;
c_each_byte = (unsigned char)c | ((unsigned char)c << 8);
c_each_byte |= c_each_byte << 16;
c_each_byte |= c_each_byte << 32;
while (n >= 8)
{
zero_mask = *lls2 ^ c_each_byte;
if (((zero_mask - one_each_byte) & ~zero_mask) & (one_each_byte << 7))
break ;
*lls1++ = *lls2++;
n -= 8;
}
cs1 = (unsigned char *)lls1;
cs2 = (unsigned char *)lls2;
}
while (n--)
{
if ((*cs1 = *cs2) == (unsigned char)c)
return (cs1 + 1);
++cs1;
++cs2;
}
return (NULL);
}
- Result are a percentage of the performance against a glibc memccpy [ldd (Ubuntu GLIBC 2.27-3ubuntu1) 2.27].
- Compiler is gcc [(Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0].
- for each size the test runtime is 5 seconds.
- Memory is aligned.
| Size\flag | -O3 -fno-builtin | -O2 | -Os | (none) |
|---|---|---|---|---|
| 1 | 100% | 100% | 101% | 100% |
| 10 | 100% | 99% | 101% | 97% |
| 100 | 96% | 96% | 96% | 85% |
| 1K | 72% | 71% | 73% | 36% |
| 10K | 25% | 25% | 25% | 7% |
| 100K | 13% | 13% | 13% | 3% |
| 1M | 15% | 14% | 14% | 3% |
| Size\flag | -O3 -fno-builtin | -O2 | -Os | (none) |
|---|---|---|---|---|
| 1 | 99% | 100% | 101% | 100% |
| 10 | 99% | 99% | 100% | 99% |
| 100 | 99% | 99% | 99% | 95% |
| 1K | 92% | 92% | 93% | 75% |
| 10K | 63% | 63% | 62% | 30% |
| 100K | 49% | 49% | 48% | 16% |
| 1M | 59% | 59% | 58% | 18% |
# include <time.h>
# include <string.h>
# include <stdlib.h>
size_t memccpy_speed_test(int len, int second, void *(mem)(void *, const void *, int, size_t))
{
clock_t chrono = 0;
clock_t start = 0;
size_t i = 0;
void *dst;
void *src1;
void *src2;
dst = malloc(len + 1);
src1 = malloc(len + 1);
src2 = malloc(len + 1);
if (!dst || !src1 || !src2)
exit(1);
memset(src1, 0xff, len + 1);
memset(src2, 0, len + 1);
memset(dst, 0, len + 1);
((char *)src1)[len] = 0;
((char *)src2)[len] = 0xff;
start = clock();
while (chrono < second * CLOCKS_PER_SEC)
{
if (i % 2)
mem(dst, src1, 0, len + 1);
else
mem(dst, src2, 0xff, len + 1);
i++;
chrono = clock() - start;
}
free(dst);
free(src1);
free(src2);
return (i);
}