Commit | Line | Data |
---|---|---|
8424cc97 | 1 | /* Searching in a string. |
5e8754f9 | 2 | Copyright (C) 2008-2016 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 | |
5e8754f9 | 15 | along with this program. If not, see <http://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. */ | |
23 | void * | |
24 | rawmemchr (const void *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 | ||
41 | /* Handle the first few bytes by reading one byte at a time. | |
42 | Do this until CHAR_PTR is aligned on a longword boundary. */ | |
43 | for (char_ptr = (const unsigned char *) s; | |
44 | (size_t) char_ptr % sizeof (longword) != 0; | |
45 | ++char_ptr) | |
46 | if (*char_ptr == c) | |
47 | return (void *) char_ptr; | |
48 | ||
49 | longword_ptr = (const longword *) char_ptr; | |
50 | ||
51 | /* All these elucidatory comments refer to 4-byte longwords, | |
52 | but the theory applies equally well to any size longwords. */ | |
53 | ||
54 | /* Compute auxiliary longword values: | |
55 | repeated_one is a value which has a 1 in every byte. | |
56 | repeated_c has c in every byte. */ | |
57 | repeated_one = 0x01010101; | |
58 | repeated_c = c | (c << 8); | |
59 | repeated_c |= repeated_c << 16; | |
60 | if (0xffffffffU < (longword) -1) | |
61 | { | |
62 | repeated_one |= repeated_one << 31 << 1; | |
63 | repeated_c |= repeated_c << 31 << 1; | |
64 | if (8 < sizeof (longword)) | |
65 | { | |
66 | size_t i; | |
67 | ||
68 | for (i = 64; i < sizeof (longword) * 8; i *= 2) | |
69 | { | |
70 | repeated_one |= repeated_one << i; | |
71 | repeated_c |= repeated_c << i; | |
72 | } | |
73 | } | |
74 | } | |
75 | ||
76 | /* Instead of the traditional loop which tests each byte, we will | |
77 | test a longword at a time. The tricky part is testing if *any of | |
78 | the four* bytes in the longword in question are equal to NUL or | |
79 | c. We first use an xor with repeated_c. This reduces the task | |
80 | to testing whether *any of the four* bytes in longword1 is zero. | |
81 | ||
82 | We compute tmp = | |
83 | ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7). | |
84 | That is, we perform the following operations: | |
85 | 1. Subtract repeated_one. | |
86 | 2. & ~longword1. | |
87 | 3. & a mask consisting of 0x80 in every byte. | |
88 | Consider what happens in each byte: | |
89 | - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff, | |
90 | and step 3 transforms it into 0x80. A carry can also be propagated | |
91 | to more significant bytes. | |
92 | - If a byte of longword1 is nonzero, let its lowest 1 bit be at | |
93 | position k (0 <= k <= 7); so the lowest k bits are 0. After step 1, | |
94 | the byte ends in a single bit of value 0 and k bits of value 1. | |
95 | After step 2, the result is just k bits of value 1: 2^k - 1. After | |
96 | step 3, the result is 0. And no carry is produced. | |
97 | So, if longword1 has only non-zero bytes, tmp is zero. | |
98 | Whereas if longword1 has a zero byte, call j the position of the least | |
99 | significant zero byte. Then the result has a zero at positions 0, ..., | |
100 | j-1 and a 0x80 at position j. We cannot predict the result at the more | |
101 | significant bytes (positions j+1..3), but it does not matter since we | |
102 | already have a non-zero bit at position 8*j+7. | |
103 | ||
104 | The test whether any byte in longword1 is zero is equivalent | |
105 | to testing whether tmp is nonzero. | |
106 | ||
107 | This test can read beyond the end of a string, depending on where | |
108 | C_IN is encountered. However, this is considered safe since the | |
109 | initialization phase ensured that the read will be aligned, | |
110 | therefore, the read will not cross page boundaries and will not | |
111 | cause a fault. */ | |
112 | ||
113 | while (1) | |
114 | { | |
115 | longword longword1 = *longword_ptr ^ repeated_c; | |
116 | ||
117 | if ((((longword1 - repeated_one) & ~longword1) | |
118 | & (repeated_one << 7)) != 0) | |
119 | break; | |
120 | longword_ptr++; | |
121 | } | |
122 | ||
123 | char_ptr = (const unsigned char *) longword_ptr; | |
124 | ||
125 | /* At this point, we know that one of the sizeof (longword) bytes | |
126 | starting at char_ptr is == c. On little-endian machines, we | |
127 | could determine the first such byte without any further memory | |
128 | accesses, just by looking at the tmp result from the last loop | |
129 | iteration. But this does not work on big-endian machines. | |
130 | Choose code that works in both cases. */ | |
131 | ||
132 | char_ptr = (unsigned char *) longword_ptr; | |
133 | while (*char_ptr != c) | |
134 | char_ptr++; | |
135 | return (void *) char_ptr; | |
136 | } |