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