ft_mem* and ft_strlen optimization

8 files changed, 90 insertions, 53 deletions

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));