blob: 999763e0f03fc27e01283e713542f56c1dd9ab19 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* ft_strlen.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/10/07 10:32:48 by cacharle #+# #+# */
/* Updated: 2020/04/01 21:45:38 by charles ### ########.fr */
/* */
/* ************************************************************************** */
#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)
{
uint64_t *ptr;
const char *cpy;
const char *found;
cpy = s;
while (((uint64_t)cpy & 0b111) != 0)
if (*cpy++ == '\0')
return (cpy - s - 1);
ptr = (uint64_t*)cpy;
while (TRUE)
if (((*ptr++ - LOMAGIC) & HIMAGIC) != 0)
{
cpy = (const char*)(ptr - 1);
if ((found = ft_memchr(cpy, '\0', sizeof(uint64_t))) != NULL)
return (found - s);
}
}
|
