ft_mem* and ft_strlen optimization

14 files changed, 238 insertions, 103 deletions

diff --git a/src/mem/ft_memccpy.c b/src/mem/ft_memccpy.c
index 8ce656a..0f52242 100644
--- a/src/mem/ft_memccpy.c
+++ b/src/mem/ft_memccpy.c
@@ -12,20 +12,56 @@
 
 #include "libft.h"
 
+#define HIMAGIC 0x8080808080808080L
+#define LOMAGIC 0x0101010101010101L
+
 void	*ft_memccpy(void *dest, const void *src, int c, size_t n)
 {
-	size_t		i;
-	t_ftbyte	*cast_dest;
-	t_ftbyte	*cast_src;
+	uint64_t	buf;
+	uint64_t	lw;
 
-	cast_dest = (t_ftbyte*)dest;
-	cast_src = (t_ftbyte*)src;
-	i = -1;
-	while (++i < n)
+	if (dest == src)
+		return (dest);
+	c = (uint8_t)c;
+	while ((n & 0b111) != 0)
+	{
+		*(uint8_t*)dest = *(uint8_t*)src;
+		if (*(uint8_t*)dest == c)
+			return ((uint8_t*)dest + 1);
+		src++;
+		dest++;
+		n--;
+	}
+	buf = (uint64_t)c | (uint64_t)c << 8 | (uint64_t)c << 16
+		| (uint64_t)c << 24 | (uint64_t)c << 32 | (uint64_t)c << 40
+		| (uint64_t)c << 48 | (uint64_t)c << 56;
+	while (n > 0)
 	{
-		cast_dest[i] = cast_src[i];
-		if (cast_dest[i] == (unsigned char)c)
-			return (cast_dest + i + 1);
+		lw = *(uint64_t*)src ^ buf;
+		if ((lw - LOMAGIC) & ~lw & HIMAGIC)
+		{
+			if ( (((uint8_t*)dest)[0] = ((uint8_t*)src)[0]) == (uint8_t)c)
+				return ((uint8_t*)dest + 1);
+			if ( (((uint8_t*)dest)[1] = ((uint8_t*)src)[1]) == (uint8_t)c)
+				return ((uint8_t*)dest + 2);
+			if ( (((uint8_t*)dest)[2] = ((uint8_t*)src)[2]) == (uint8_t)c)
+				return ((uint8_t*)dest + 3);
+			if ( (((uint8_t*)dest)[3] = ((uint8_t*)src)[3]) == (uint8_t)c)
+				return ((uint8_t*)dest + 4);
+			if ( (((uint8_t*)dest)[4] = ((uint8_t*)src)[4]) == (uint8_t)c)
+				return ((uint8_t*)dest + 5);
+			if ( (((uint8_t*)dest)[5] = ((uint8_t*)src)[5]) == (uint8_t)c)
+				return ((uint8_t*)dest + 6);
+			if ( (((uint8_t*)dest)[6] = ((uint8_t*)src)[6]) == (uint8_t)c)
+				return ((uint8_t*)dest + 7);
+			if ( (((uint8_t*)dest)[7] = ((uint8_t*)src)[7]) == (uint8_t)c)
+				return ((uint8_t*)dest + 8);
+		}
+		else
+			*(uint64_t*)dest = *(uint64_t*)src;
+		n -= 8;
+		dest += 8;
+		src += 8;
 	}
 	return (NULL);
 }
diff --git a/src/mem/ft_memchr.c b/src/mem/ft_memchr.c
index 4fd8689..54780fe 100644
--- a/src/mem/ft_memchr.c
+++ b/src/mem/ft_memchr.c
@@ -12,15 +12,45 @@
 
 #include "libft.h"
 
+/*
+** Determining if a long word contain byte n
+**
+** xor all bytes with n, then check for zero byte like in ft_strlen.
+*/
+
+#define HIMAGIC 0x8080808080808080L
+#define LOMAGIC 0x0101010101010101L
+
 void	*ft_memchr(const void *s, int c, size_t n)
 {
-	size_t		i;
-	t_ftbyte	*cast_s;
+	uint64_t	buf;
+	uint64_t	lw;
 
-	cast_s = (t_ftbyte*)s;
-	i = -1;
-	while (++i < n)
-		if (cast_s[i] == (unsigned char)c)
-			return (cast_s + i);
+	c = (uint8_t)c;
+	while (((uint64_t)s & 0b111) != 0)
+	{
+		n--;
+		if (*(uint8_t*)s == (uint8_t)c)
+			return ((uint8_t*)s);
+		s++;
+	}
+	buf = (uint64_t)c | (uint64_t)c << 8 | (uint64_t)c << 16
+		| (uint64_t)c << 24 | (uint64_t)c << 32 | (uint64_t)c << 40
+		| (uint64_t)c << 48 | (uint64_t)c << 56;
+	while (n >= 8)
+	{
+		lw = *(uint64_t*)s ^ buf;
+		if ((lw - LOMAGIC) & ~lw & HIMAGIC)
+			break;
+		n -= 8;
+		s += 8;
+	}
+	while (n > 0)
+	{
+		if (*(uint8_t*)s == (uint8_t)c)
+			return ((uint8_t*)s);
+		n--;
+		s++;
+	}
 	return (NULL);
 }
diff --git a/src/mem/ft_memcmp.c b/src/mem/ft_memcmp.c
index 233d796..c61ca9a 100644
--- a/src/mem/ft_memcmp.c
+++ b/src/mem/ft_memcmp.c
@@ -11,20 +11,42 @@
 /* ************************************************************************** */
 
 #include "libft.h"
+#include "libft_mem.h"
 
 int	ft_memcmp(const void *s1, const void *s2, size_t n)
 {
-	size_t		i;
-	t_ftbyte	*cast_s1;
-	t_ftbyte	*cast_s2;
-
-	cast_s1 = (t_ftbyte*)s1;
-	cast_s2 = (t_ftbyte*)s2;
-	if (n == 0)
-		return (0);
-	i = -1;
-	while (++i < n)
-		if (cast_s1[i] != cast_s2[i])
-			return (cast_s1[i] - cast_s2[i]);
+	while ((n & 0b111) != 0)
+	{
+		n--;
+		if (*(uint8_t*)s1 != *(uint8_t*)s2)
+			return (*(uint8_t*)s1 - *(uint8_t*)s2);
+		s1++;
+		s2++;
+	}
+	while (n > 0)
+	{
+		if (*(uint64_t*)s1 != *(uint64_t*)s2)
+		{
+			if (((uint8_t*)s1)[0] != ((uint8_t*)s2)[0])
+				return (((uint8_t*)s1)[0] - ((uint8_t*)s2)[0]);
+			if (((uint8_t*)s1)[1] != ((uint8_t*)s2)[1])
+				return (((uint8_t*)s1)[1] - ((uint8_t*)s2)[1]);
+			if (((uint8_t*)s1)[2] != ((uint8_t*)s2)[2])
+				return (((uint8_t*)s1)[2] - ((uint8_t*)s2)[2]);
+			if (((uint8_t*)s1)[3] != ((uint8_t*)s2)[3])
+				return (((uint8_t*)s1)[3] - ((uint8_t*)s2)[3]);
+			if (((uint8_t*)s1)[4] != ((uint8_t*)s2)[4])
+				return (((uint8_t*)s1)[4] - ((uint8_t*)s2)[4]);
+			if (((uint8_t*)s1)[5] != ((uint8_t*)s2)[5])
+				return (((uint8_t*)s1)[5] - ((uint8_t*)s2)[5]);
+			if (((uint8_t*)s1)[6] != ((uint8_t*)s2)[6])
+				return (((uint8_t*)s1)[6] - ((uint8_t*)s2)[6]);
+			if (((uint8_t*)s1)[7] != ((uint8_t*)s2)[7])
+				return (((uint8_t*)s1)[7] - ((uint8_t*)s2)[7]);
+		}
+		n -= 8;
+		s1 += 8;
+		s2 += 8;
+	}
 	return (0);
 }
diff --git a/src/mem/ft_memcpy.c b/src/mem/ft_memcpy.c
index d0ef008..1f84bfd 100644
--- a/src/mem/ft_memcpy.c
+++ b/src/mem/ft_memcpy.c
@@ -11,18 +11,19 @@
 /* ************************************************************************** */
 
 #include "libft.h"
+#include "libft_mem.h"
 
 void	*ft_memcpy(void *dest, const void *src, size_t n)
 {
-	long int		*long_dest;
-	const long int	*long_src;
+	uint64_t		*long_dest;
+	const uint64_t	*long_src;
 
 	if (dest == src)
 		return (dest);
 	while (n % 8 > 0)
 	{
 		n--;
-		((t_ftbyte*)dest)[n] = ((t_ftbyte*)src)[n];
+		((uint8_t*)dest)[n] = ((uint8_t*)src)[n];
 	}
 	long_dest = dest;
 	long_src = src;
diff --git a/src/mem/ft_memmove.c b/src/mem/ft_memmove.c
index 2f794fd..142b761 100644
--- a/src/mem/ft_memmove.c
+++ b/src/mem/ft_memmove.c
@@ -11,11 +11,12 @@
 /* ************************************************************************** */
 
 #include "libft.h"
+#include "libft_mem.h"
 
 void	*ft_memmove(void *dst, const void *src, size_t len)
 {
-	long int		*long_dst;
-	const long int	*long_src;
+	uint64_t		*dst64;
+	const uint64_t	*src64;
 	void			*dst_copy;
 
 	if (dst >= src)
@@ -24,12 +25,12 @@ void	*ft_memmove(void *dst, const void *src, size_t len)
 	while (len % 8 > 0)
 	{
 		len--;
-		*(t_ftbyte*)dst++ = *(t_ftbyte*)src++;
+		*(uint8_t*)dst++ = *(uint8_t*)src++;
 	}
-	long_dst = dst;
-	long_src = src;
+	dst64 = dst;
+	src64 = src;
 	len /= 8;
 	while (len-- > 0)
-		*long_dst++ = *long_src++;
+		*dst64++ = *src64++;
 	return (dst_copy);
 }
diff --git a/src/mem/ft_memset.c b/src/mem/ft_memset.c
index 89f53ff..ce471a5 100644
--- a/src/mem/ft_memset.c
+++ b/src/mem/ft_memset.c
@@ -11,21 +11,29 @@
 /* ************************************************************************** */
 
 #include "libft.h"
+#include "libft_mem.h"
 
 void	*ft_memset(void *s, int c, size_t n)
 {
-	long int	buf;
-	long int	*long_s;
+	uint64_t	buf;
+	void *cpy;
 
-	c = (unsigned char)c;
-	while (n % 8 > 0)
-		*((t_ftbyte*)s + --n) = c;
-	buf = (long int)c | (long int)c << 8 | (long int)c << 16
-			| (long int)c << 24 | (long int)c << 32 | (long int)c << 40
-			| (long int)c << 48 | (long int)c << 56;
-	n /= 8;
-	long_s = s;
+	cpy = s;
+	c = (uint8_t)c;
+	buf = (uint64_t)c | (uint64_t)c << 8 | (uint64_t)c << 16
+		| (uint64_t)c << 24 | (uint64_t)c << 32 | (uint64_t)c << 40
+		| (uint64_t)c << 48 | (uint64_t)c << 56;
+	while (n > 8)
+	{
+		*(uint64_t*)s = buf;
+		n -= 8;
+		s += 8;
+	}
 	while (n > 0)
-		long_s[--n] = buf;
-	return (s);
+	{
+		*(uint8_t*)s = c;
+		s++;
+		n--;
+	}
+	return (cpy);
 }
diff --git a/src/str/ft_strcat.c b/src/str/ft_strcat.c
index d5bc7e0..faed515 100644
--- a/src/str/ft_strcat.c
+++ b/src/str/ft_strcat.c
@@ -11,6 +11,7 @@
 /* ************************************************************************** */
 
 #include "libft.h"
+#include "libft_mem.h"
 
 char	*ft_strcat(char *dest, const char *src)
 {
diff --git a/src/str/ft_strcmp.c b/src/str/ft_strcmp.c
index aced711..25d2972 100644
--- a/src/str/ft_strcmp.c
+++ b/src/str/ft_strcmp.c
@@ -14,10 +14,5 @@
 
 int	ft_strcmp(const char *s1, const char *s2)
 {
-	while (*s1 && *s2 && *s1 == *s2)
-	{
-		s1++;
-		s2++;
-	}
-	return (*s1 - *s2);
+	return (ft_memcmp(s1, s2, ft_strlen(s1) + 1));
 }
diff --git a/src/str/ft_strdup.c b/src/str/ft_strdup.c
index b248272..9493d82 100644
--- a/src/str/ft_strdup.c
+++ b/src/str/ft_strdup.c
@@ -11,12 +11,15 @@
 /* ************************************************************************** */
 
 #include "libft.h"
+#include "libft_str.h"
 
 char	*ft_strdup(const char *s)
 {
 	char	*clone;
+	size_t	size;
 
-	if ((clone = (char*)malloc(sizeof(char) * (ft_strlen(s) + 1))) == NULL)
+	size = ft_strlen(s) + 1;
+	if ((clone = (char*)malloc(sizeof(char) * size)) == NULL)
 		return (NULL);
-	return (ft_strcpy(clone, s));
+	return (ft_memcpy(clone, s, size));
 }
diff --git a/src/str/ft_strlen.c b/src/str/ft_strlen.c
index 0d593e1..72405c4 100644
--- a/src/str/ft_strlen.c
+++ b/src/str/ft_strlen.c
@@ -11,31 +11,79 @@
 /* ************************************************************************** */
 
 #include "libft.h"
+#include <stdint.h>
+
+/*
+** Determining if one byte of a long word is 0
+**
+** ~((((lw & 0x7F7F7F7F) + 0x7F7F7F7F) | lw) | 0x7F7F7F7F)
+**
+** where `lw` is a long word
+**
+** 0x7F -> 0b 0111 1111
+**
+** null_high = lw & 0x7F7F7F7F        // will set the high bit of each byte to 0
+** overflow = null_high + 0x7F7F7F7F  // addition will overflow the high bit is one of the other bits was 1.
+**
+** oring = overflow | lw              // the high bit of a byte is set iff any bit in the byte was set
+** ones = oring | 0x7F7F7F7F          // the high bits and ones everywhere else
+** has_no_zero_byte = ~ones           // the ones become zeros, if no high bit was set, there was no zero
+**
+**
+** (lw - 0x01010101) & ~lw & 0x80808080
+**
+** overflow = lw - 0x01010101         // overflow the high bit if one was 0 or > 0x80 (0b 1000 0000)  0 || >0x80
+** no_high_bit = ~lw & 0x80808080     // high bit set if the high bit was 0 (i.e < 0x80)              0 || <0x80
+** has_zero = overflow & no_high_bit  // (0 || >0x80) && (0 || <0x80) -> 0 && 0
+**
+**
+** libc's strlen only filter out < 0x80 bytes by omitting the ~lw & 0x80808080
+**   part because most string only contain ascii characters.
+**
+** sources:
+** - https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord
+** - https://stackoverflow.com/questions/20021066
+*/
+
+#define HIMAGIC 0x8080808080808080L
+#define LOMAGIC 0x0101010101010101L
 
 size_t	ft_strlen(const char *s)
 {
-	unsigned long int	*ptr;
-	const char			*cpy;
+	uint64_t	*ptr;
+	const char	*cpy;
+	uint64_t	lw;
 
-	ptr = (unsigned long int*)s;
-	while (TRUE)
+	cpy = s;
+	while (((uint64_t)cpy & 0b111) != 0)
 	{
-		cpy = (const char*)ptr++;
-		if (cpy[0] == '\0')
+		if (*cpy == 0)
 			return (cpy - s);
-		if (cpy[1] == '\0')
-			return (cpy + 1 - s);
-		if (cpy[2] == '\0')
-			return (cpy + 2 - s);
-		if (cpy[3] == '\0')
-			return (cpy + 3 - s);
-		if (cpy[4] == '\0')
-			return (cpy + 4 - s);
-		if (cpy[5] == '\0')
-			return (cpy + 5 - s);
-		if (cpy[6] == '\0')
-			return (cpy + 6 - s);
-		if (cpy[7] == '\0')
-			return (cpy + 7 - s);
+		cpy++;
+	}
+	ptr = (uint64_t*)cpy;
+	while (TRUE)
+	{
+		lw = *ptr++;
+		if (((lw - LOMAGIC) & HIMAGIC) != 0)
+		{
+			cpy = (const char*)(ptr - 1);
+			if (cpy[0] == '\0')
+				return (cpy - s);
+			if (cpy[1] == '\0')
+				return (cpy - s + 1);
+			if (cpy[2] == '\0')
+				return (cpy - s + 2);
+			if (cpy[3] == '\0')
+				return (cpy - s + 3);
+			if (cpy[4] == '\0')
+				return (cpy - s + 4);
+			if (cpy[5] == '\0')
+				return (cpy - s + 5);
+			if (cpy[6] == '\0')
+				return (cpy - s + 6);
+			if (cpy[7] == '\0')
+				return (cpy - s + 7);
+		}
 	}
 }
diff --git a/src/str/ft_strncat.c b/src/str/ft_strncat.c
index d68db0a..4686d59 100644
--- a/src/str/ft_strncat.c
+++ b/src/str/ft_strncat.c
@@ -14,16 +14,14 @@
 
 char	*ft_strncat(char *dest, const char *src, size_t n)
 {
-	size_t	i;
-	size_t	j;
+	size_t	dest_len;
+	size_t	src_len;
 
-	i = ft_strlen(dest);
-	j = 0;
-	while (j < n && src[j])
-	{
-		dest[i + j] = src[j];
-		j++;
-	}
-	dest[i + j] = '\0';
+	dest_len = ft_strlen(dest);
+	src_len = ft_strlen(src);
+	if (n < src_len)
+		src_len = n;
+	ft_memcpy(dest + dest_len, src, src_len);
+	dest[dest_len + src_len] = '\0';
 	return (dest);
 }
diff --git a/src/str/ft_strncmp.c b/src/str/ft_strncmp.c
index caa052b..a0371e4 100644
--- a/src/str/ft_strncmp.c
+++ b/src/str/ft_strncmp.c
@@ -11,16 +11,12 @@
 /* ************************************************************************** */
 
 #include "libft.h"
-#include "libft_types.h"
+#include "libft_str.h"
 
 int	ft_strncmp(const char *s1, const char *s2, size_t n)
 {
-	size_t	i;
+	size_t len;
 
-	if (n == 0)
-		return (0);
-	i = 0;
-	while (i + 1 < n && s1[i] == s2[i] && s1[i])
-		i++;
-	return ((t_ftuchar)s1[i] - (t_ftuchar)s2[i]);
+	len = ft_strlen(s1);
+	return (ft_memcmp(s1, s2, n < len ? n : len + 1));
 }
diff --git a/src/str/ft_strstr.c b/src/str/ft_strstr.c
index 4d4d403..893ae1e 100644
--- a/src/str/ft_strstr.c
+++ b/src/str/ft_strstr.c
@@ -11,6 +11,7 @@
 /* ************************************************************************** */
 
 #include "libft.h"
+#include "libft_str.h"
 
 char	*ft_strstr(const char *haystack, const char *needle)
 {
@@ -19,11 +20,5 @@ char	*ft_strstr(const char *haystack, const char *needle)
 	needle_len = ft_strlen(needle);
 	if (needle_len == 0)
 		return ((char*)haystack);
-	while (*haystack)
-	{
-		if (ft_strnequ(haystack, needle, needle_len))
-			return ((char*)haystack);
-		haystack++;
-	}
-	return (NULL);
+	return (ft_memmem(haystack, ft_strlen(haystack), needle, needle_len));
 }
diff --git a/src/str/ft_substr.c b/src/str/ft_substr.c
index ad9c706..59fe3f2 100644
--- a/src/str/ft_substr.c
+++ b/src/str/ft_substr.c
@@ -20,6 +20,7 @@ char	*ft_substr(char const *s, unsigned int start, size_t len)
 		return (NULL);
 	if ((sub = (char*)malloc(sizeof(char) * (len + 1))) == NULL)
 		return (NULL);
+	sub[len] = '\0';
 	if (start > ft_strlen(s))
 		return (sub);
 	return (ft_strncpy(sub, s + start, len));