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