1 | /* Find the length of STRING, but scan at most MAXLEN characters. |
2 | Copyright (C) 1991-2022 Free Software Foundation, Inc. |
3 | |
4 | Based on strlen written by Torbjorn Granlund (tege@sics.se), |
5 | with help from Dan Sahlin (dan@sics.se); |
6 | commentary by Jim Blandy (jimb@ai.mit.edu). |
7 | |
8 | The GNU C Library is free software; you can redistribute it and/or |
9 | modify it under the terms of the GNU Lesser General Public License as |
10 | published by the Free Software Foundation; either version 2.1 of the |
11 | License, or (at your option) any later version. |
12 | |
13 | The GNU C Library is distributed in the hope that it will be useful, |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
16 | Lesser General Public License for more details. |
17 | |
18 | You should have received a copy of the GNU Lesser General Public |
19 | License along with the GNU C Library; see the file COPYING.LIB. If |
20 | not, see <https://www.gnu.org/licenses/>. */ |
21 | |
22 | #include <string.h> |
23 | #include <stdlib.h> |
24 | |
25 | /* Find the length of S, but scan at most MAXLEN characters. If no |
26 | '\0' terminator is found in that many characters, return MAXLEN. */ |
27 | |
28 | #ifdef STRNLEN |
29 | # define __strnlen STRNLEN |
30 | #endif |
31 | |
32 | size_t |
33 | __strnlen (const char *str, size_t maxlen) |
34 | { |
35 | const char *char_ptr, *end_ptr = str + maxlen; |
36 | const unsigned long int *longword_ptr; |
37 | unsigned long int longword, himagic, lomagic; |
38 | |
39 | if (maxlen == 0) |
40 | return 0; |
41 | |
42 | if (__glibc_unlikely (end_ptr < str)) |
43 | end_ptr = (const char *) ~0UL; |
44 | |
45 | /* Handle the first few characters by reading one character at a time. |
46 | Do this until CHAR_PTR is aligned on a longword boundary. */ |
47 | for (char_ptr = str; ((unsigned long int) char_ptr |
48 | & (sizeof (longword) - 1)) != 0; |
49 | ++char_ptr) |
50 | if (*char_ptr == '\0') |
51 | { |
52 | if (char_ptr > end_ptr) |
53 | char_ptr = end_ptr; |
54 | return char_ptr - str; |
55 | } |
56 | |
57 | /* All these elucidatory comments refer to 4-byte longwords, |
58 | but the theory applies equally well to 8-byte longwords. */ |
59 | |
60 | longword_ptr = (unsigned long int *) char_ptr; |
61 | |
62 | /* Bits 31, 24, 16, and 8 of this number are zero. Call these bits |
63 | the "holes." Note that there is a hole just to the left of |
64 | each byte, with an extra at the end: |
65 | |
66 | bits: 01111110 11111110 11111110 11111111 |
67 | bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD |
68 | |
69 | The 1-bits make sure that carries propagate to the next 0-bit. |
70 | The 0-bits provide holes for carries to fall into. */ |
71 | himagic = 0x80808080L; |
72 | lomagic = 0x01010101L; |
73 | if (sizeof (longword) > 4) |
74 | { |
75 | /* 64-bit version of the magic. */ |
76 | /* Do the shift in two steps to avoid a warning if long has 32 bits. */ |
77 | himagic = ((himagic << 16) << 16) | himagic; |
78 | lomagic = ((lomagic << 16) << 16) | lomagic; |
79 | } |
80 | if (sizeof (longword) > 8) |
81 | abort (); |
82 | |
83 | /* Instead of the traditional loop which tests each character, |
84 | we will test a longword at a time. The tricky part is testing |
85 | if *any of the four* bytes in the longword in question are zero. */ |
86 | while (longword_ptr < (unsigned long int *) end_ptr) |
87 | { |
88 | /* We tentatively exit the loop if adding MAGIC_BITS to |
89 | LONGWORD fails to change any of the hole bits of LONGWORD. |
90 | |
91 | 1) Is this safe? Will it catch all the zero bytes? |
92 | Suppose there is a byte with all zeros. Any carry bits |
93 | propagating from its left will fall into the hole at its |
94 | least significant bit and stop. Since there will be no |
95 | carry from its most significant bit, the LSB of the |
96 | byte to the left will be unchanged, and the zero will be |
97 | detected. |
98 | |
99 | 2) Is this worthwhile? Will it ignore everything except |
100 | zero bytes? Suppose every byte of LONGWORD has a bit set |
101 | somewhere. There will be a carry into bit 8. If bit 8 |
102 | is set, this will carry into bit 16. If bit 8 is clear, |
103 | one of bits 9-15 must be set, so there will be a carry |
104 | into bit 16. Similarly, there will be a carry into bit |
105 | 24. If one of bits 24-30 is set, there will be a carry |
106 | into bit 31, so all of the hole bits will be changed. |
107 | |
108 | The one misfire occurs when bits 24-30 are clear and bit |
109 | 31 is set; in this case, the hole at bit 31 is not |
110 | changed. If we had access to the processor carry flag, |
111 | we could close this loophole by putting the fourth hole |
112 | at bit 32! |
113 | |
114 | So it ignores everything except 128's, when they're aligned |
115 | properly. */ |
116 | |
117 | longword = *longword_ptr++; |
118 | |
119 | if ((longword - lomagic) & himagic) |
120 | { |
121 | /* Which of the bytes was the zero? If none of them were, it was |
122 | a misfire; continue the search. */ |
123 | |
124 | const char *cp = (const char *) (longword_ptr - 1); |
125 | |
126 | char_ptr = cp; |
127 | if (cp[0] == 0) |
128 | break; |
129 | char_ptr = cp + 1; |
130 | if (cp[1] == 0) |
131 | break; |
132 | char_ptr = cp + 2; |
133 | if (cp[2] == 0) |
134 | break; |
135 | char_ptr = cp + 3; |
136 | if (cp[3] == 0) |
137 | break; |
138 | if (sizeof (longword) > 4) |
139 | { |
140 | char_ptr = cp + 4; |
141 | if (cp[4] == 0) |
142 | break; |
143 | char_ptr = cp + 5; |
144 | if (cp[5] == 0) |
145 | break; |
146 | char_ptr = cp + 6; |
147 | if (cp[6] == 0) |
148 | break; |
149 | char_ptr = cp + 7; |
150 | if (cp[7] == 0) |
151 | break; |
152 | } |
153 | } |
154 | char_ptr = end_ptr; |
155 | } |
156 | |
157 | if (char_ptr > end_ptr) |
158 | char_ptr = end_ptr; |
159 | return char_ptr - str; |
160 | } |
161 | #ifndef STRNLEN |
162 | libc_hidden_def (__strnlen) |
163 | weak_alias (__strnlen, strnlen) |
164 | #endif |
165 | libc_hidden_def (strnlen) |
166 | |