memchr - AugustinLopez/libft GitHub Wiki

Introduction

From The Open Group Base Specifications issue 7, 2018:

#include <string.h>

void *memchr(const void *s, int c, size_t n);
  • The memchr() function shall locate the first occurrence of c (converted to an unsigned char) in the initial n bytes (each interpreted as unsigned char) pointed to by s.
  • Implementations shall behave as if they read the memory byte by byte from the beginning of the bytes pointed to by s and stop at the first occurrence of c (if it is found in the initial n bytes).
  • The memchr() function shall return a pointer to the located byte, or a null pointer if the byte is not found.
  • No errors are defined.

Implementation

Relevant concepts: Operator precedence, type casting, const keyword

Basic implementation

#include <string.h>

void	*ft_memchr(const void *s, int c, size_t n)
{
	const unsigned char	*pc;

	pc = (const unsigned char *)s;
	while (n--)
	{
		if (*pc == (unsigned char)c)
			return ((void *)pc);
		++pc;
	}
	return (NULL);
}

Improved implementation

For more information, please refer to the Optimization Concepts page.

#include <string.h>
#include <stdint.h>

void	*memchr(const void *s, int c, size_t n)
{
	const unsigned char	*pc;
	uint64_t	*pll;
	uint64_t	one_each_byte;
	uint64_t	c_each_byte;
	uint64_t	zero_mask;

	pc = (const unsigned char *)s;
	while ((uintptr_t)pc & 0x7)
	{
		if (*pc == (unsigned char)c)
			return ((void *)pc);
		++pc;
		if (!--n)
			return (NULL);
	}
	if (n >= 8)
	{
		pll = (uint64_t *)pc;
		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 (*n >= 8)
		{
			zero_mask = *pll ^ c_each_byte;
			if (((zero_mask - one_each_byte) & ~zero_mask) & (one_each_byte << 7))
				break ;
			pll++;
			*n -= 8;
		}
		pc = (const unsigned char *)pll;
	}
	while (n--)
	{
		if (*pc == (unsigned char)c)
			return ((void *)pc);
		++pc;
	}
	return (NULL);
}

Speed tests

  • Results are a percentage of the performance against a glibc memchr [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.

Basic implementation

Size\flag -O3 -fno-builtin -O2 -Os (none)
1 100% 101% 100% 99%
10 99% 101% 100% 99%
100 96% 96% 95% 87%
1K 80% 81% 74% 40%
10K 32% 32% 24% 7%
100K 9% 9% 6% 1%
1M 8% 9% 6% 1%

Improved implementation

Size\flag -O3 -fno-builtin -O2 -Os (none)
1 99% 99% 101% 99%
10 100% 100% 101% 99%
100 99% 99% 99% 97%
1K 93% 92% 92% 77%
10K 62% 61% 62% 28%
100K 25% 25% 26% 7%
1M 26% 26% 27% 7%

Test function

# include <time.h>
# include <string.h>
# include <stdlib.h>

size_t	memchr_speed_test(int len, int second, void *(mem)(const void *, int, size_t))
{
	clock_t			chrono = 0;
	clock_t			start = 0;
	size_t			i = 0;
	void			*buff;

	if (!(buff = malloc(len + 1)))
		exit(1);
	memset(buff, 0, len + 1);
	((char *)buff)[len] = 1;
	start = clock();
	while (chrono < second * CLOCKS_PER_SEC)
	{
		mem(buff, 1, len + 1);
		i++;
		chrono = clock() - start;
	}
	free(buff);
	return (i);
}

Other implementations

Further Reading

Back to the repository.

⚠️ **GitHub.com Fallback** ⚠️