Commit | Line | Data |
---|---|---|
8424cc97 | 1 | /* Searching in a string. |
c0c3707f | 2 | Copyright (C) 2003, 2007-2019 Free Software Foundation, Inc. |
8424cc97 SM |
3 | |
4 | This program is free software: you can redistribute it and/or modify | |
5 | it under the terms of the GNU General Public License as published by | |
6 | the Free Software Foundation; either version 3 of the License, or | |
7 | (at your option) any later version. | |
8 | ||
9 | This program is distributed in the hope that it will be useful, | |
10 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
11 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
12 | GNU General Public License for more details. | |
13 | ||
14 | You should have received a copy of the GNU General Public License | |
c0c3707f | 15 | along with this program. If not, see <https://www.gnu.org/licenses/>. */ |
8424cc97 SM |
16 | |
17 | #include <config.h> | |
18 | ||
19 | /* Specification. */ | |
20 | #include <string.h> | |
21 | ||
22 | /* Find the first occurrence of C in S or the final NUL byte. */ | |
23 | char * | |
24 | strchrnul (const char *s, int c_in) | |
25 | { | |
26 | /* On 32-bit hardware, choosing longword to be a 32-bit unsigned | |
27 | long instead of a 64-bit uintmax_t tends to give better | |
28 | performance. On 64-bit hardware, unsigned long is generally 64 | |
29 | bits already. Change this typedef to experiment with | |
30 | performance. */ | |
31 | typedef unsigned long int longword; | |
32 | ||
33 | const unsigned char *char_ptr; | |
34 | const longword *longword_ptr; | |
35 | longword repeated_one; | |
36 | longword repeated_c; | |
37 | unsigned char c; | |
38 | ||
39 | c = (unsigned char) c_in; | |
40 | if (!c) | |
41 | return rawmemchr (s, 0); | |
42 | ||
43 | /* Handle the first few bytes by reading one byte at a time. | |
44 | Do this until CHAR_PTR is aligned on a longword boundary. */ | |
45 | for (char_ptr = (const unsigned char *) s; | |
46 | (size_t) char_ptr % sizeof (longword) != 0; | |
47 | ++char_ptr) | |
48 | if (!*char_ptr || *char_ptr == c) | |
49 | return (char *) char_ptr; | |
50 | ||
51 | longword_ptr = (const longword *) char_ptr; | |
52 | ||
53 | /* All these elucidatory comments refer to 4-byte longwords, | |
54 | but the theory applies equally well to any size longwords. */ | |
55 | ||
56 | /* Compute auxiliary longword values: | |
57 | repeated_one is a value which has a 1 in every byte. | |
58 | repeated_c has c in every byte. */ | |
59 | repeated_one = 0x01010101; | |
60 | repeated_c = c | (c << 8); | |
61 | repeated_c |= repeated_c << 16; | |
62 | if (0xffffffffU < (longword) -1) | |
63 | { | |
64 | repeated_one |= repeated_one << 31 << 1; | |
65 | repeated_c |= repeated_c << 31 << 1; | |
66 | if (8 < sizeof (longword)) | |
67 | { | |
68 | size_t i; | |
69 | ||
70 | for (i = 64; i < sizeof (longword) * 8; i *= 2) | |
71 | { | |
72 | repeated_one |= repeated_one << i; | |
73 | repeated_c |= repeated_c << i; | |
74 | } | |
75 | } | |
76 | } | |
77 | ||
78 | /* Instead of the traditional loop which tests each byte, we will | |
79 | test a longword at a time. The tricky part is testing if *any of | |
80 | the four* bytes in the longword in question are equal to NUL or | |
81 | c. We first use an xor with repeated_c. This reduces the task | |
82 | to testing whether *any of the four* bytes in longword1 or | |
83 | longword2 is zero. | |
84 | ||
85 | Let's consider longword1. We compute tmp = | |
86 | ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7). | |
87 | That is, we perform the following operations: | |
88 | 1. Subtract repeated_one. | |
89 | 2. & ~longword1. | |
90 | 3. & a mask consisting of 0x80 in every byte. | |
91 | Consider what happens in each byte: | |
92 | - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff, | |
93 | and step 3 transforms it into 0x80. A carry can also be propagated | |
94 | to more significant bytes. | |
95 | - If a byte of longword1 is nonzero, let its lowest 1 bit be at | |
96 | position k (0 <= k <= 7); so the lowest k bits are 0. After step 1, | |
97 | the byte ends in a single bit of value 0 and k bits of value 1. | |
98 | After step 2, the result is just k bits of value 1: 2^k - 1. After | |
99 | step 3, the result is 0. And no carry is produced. | |
100 | So, if longword1 has only non-zero bytes, tmp is zero. | |
101 | Whereas if longword1 has a zero byte, call j the position of the least | |
102 | significant zero byte. Then the result has a zero at positions 0, ..., | |
103 | j-1 and a 0x80 at position j. We cannot predict the result at the more | |
104 | significant bytes (positions j+1..3), but it does not matter since we | |
105 | already have a non-zero bit at position 8*j+7. | |
106 | ||
107 | The test whether any byte in longword1 or longword2 is zero is equivalent | |
108 | to testing whether tmp1 is nonzero or tmp2 is nonzero. We can combine | |
109 | this into a single test, whether (tmp1 | tmp2) is nonzero. | |
110 | ||
111 | This test can read more than one byte beyond the end of a string, | |
112 | depending on where the terminating NUL is encountered. However, | |
113 | this is considered safe since the initialization phase ensured | |
114 | that the read will be aligned, therefore, the read will not cross | |
115 | page boundaries and will not cause a fault. */ | |
116 | ||
117 | while (1) | |
118 | { | |
119 | longword longword1 = *longword_ptr ^ repeated_c; | |
120 | longword longword2 = *longword_ptr; | |
121 | ||
122 | if (((((longword1 - repeated_one) & ~longword1) | |
123 | | ((longword2 - repeated_one) & ~longword2)) | |
124 | & (repeated_one << 7)) != 0) | |
125 | break; | |
126 | longword_ptr++; | |
127 | } | |
128 | ||
129 | char_ptr = (const unsigned char *) longword_ptr; | |
130 | ||
131 | /* At this point, we know that one of the sizeof (longword) bytes | |
132 | starting at char_ptr is == 0 or == c. On little-endian machines, | |
133 | we could determine the first such byte without any further memory | |
134 | accesses, just by looking at the tmp result from the last loop | |
135 | iteration. But this does not work on big-endian machines. | |
136 | Choose code that works in both cases. */ | |
137 | ||
138 | char_ptr = (unsigned char *) longword_ptr; | |
139 | while (*char_ptr && (*char_ptr != c)) | |
140 | char_ptr++; | |
141 | return (char *) char_ptr; | |
142 | } |