]>
Commit | Line | Data |
---|---|---|
8424cc97 | 1 | /* Searching in a string. |
dc6c21da | 2 | Copyright (C) 2008-2022 Free Software Foundation, Inc. |
8424cc97 | 3 | |
dc6c21da TT |
4 | This file is free software: you can redistribute it and/or modify |
5 | it under the terms of the GNU Lesser General Public License as | |
6 | published by the Free Software Foundation; either version 2.1 of the | |
7 | License, or (at your option) any later version. | |
8424cc97 | 8 | |
dc6c21da | 9 | This file is distributed in the hope that it will be useful, |
8424cc97 SM |
10 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
dc6c21da | 12 | GNU Lesser General Public License for more details. |
8424cc97 | 13 | |
dc6c21da | 14 | You should have received a copy of the GNU Lesser 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 | ||
dc6c21da TT |
22 | /* A function definition is only needed if HAVE_RAWMEMCHR is not defined. */ |
23 | #if !HAVE_RAWMEMCHR | |
24 | ||
25 | # include <limits.h> | |
26 | # include <stdalign.h> | |
27 | # include <stdint.h> | |
28 | ||
29 | # include "verify.h" | |
30 | ||
8424cc97 SM |
31 | /* Find the first occurrence of C in S. */ |
32 | void * | |
33 | rawmemchr (const void *s, int c_in) | |
34 | { | |
dc6c21da TT |
35 | /* Change this typedef to experiment with performance. */ |
36 | typedef uintptr_t longword; | |
37 | /* If you change the "uintptr_t", you should change UINTPTR_WIDTH to match. | |
38 | This verifies that the type does not have padding bits. */ | |
39 | verify (UINTPTR_WIDTH == UCHAR_WIDTH * sizeof (longword)); | |
8424cc97 SM |
40 | |
41 | const unsigned char *char_ptr; | |
dc6c21da | 42 | unsigned char c = c_in; |
8424cc97 SM |
43 | |
44 | /* Handle the first few bytes by reading one byte at a time. | |
45 | Do this until CHAR_PTR is aligned on a longword boundary. */ | |
46 | for (char_ptr = (const unsigned char *) s; | |
dc6c21da | 47 | (uintptr_t) char_ptr % alignof (longword) != 0; |
8424cc97 SM |
48 | ++char_ptr) |
49 | if (*char_ptr == c) | |
50 | return (void *) char_ptr; | |
51 | ||
dc6c21da | 52 | longword const *longword_ptr = s = char_ptr; |
8424cc97 SM |
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. */ | |
dc6c21da TT |
57 | longword repeated_one = (longword) -1 / UCHAR_MAX; |
58 | longword repeated_c = repeated_one * c; | |
59 | longword repeated_hibit = repeated_one * (UCHAR_MAX / 2 + 1); | |
8424cc97 SM |
60 | |
61 | /* Instead of the traditional loop which tests each byte, we will | |
dc6c21da TT |
62 | test a longword at a time. The tricky part is testing if any of |
63 | the bytes in the longword in question are equal to | |
8424cc97 | 64 | c. We first use an xor with repeated_c. This reduces the task |
dc6c21da TT |
65 | to testing whether any of the bytes in longword1 is zero. |
66 | ||
67 | (The following comments assume 8-bit bytes, as POSIX requires; | |
68 | the code's use of UCHAR_MAX should work even if bytes have more | |
69 | than 8 bits.) | |
8424cc97 SM |
70 | |
71 | We compute tmp = | |
dc6c21da | 72 | ((longword1 - repeated_one) & ~longword1) & (repeated_one * 0x80). |
8424cc97 SM |
73 | That is, we perform the following operations: |
74 | 1. Subtract repeated_one. | |
75 | 2. & ~longword1. | |
76 | 3. & a mask consisting of 0x80 in every byte. | |
77 | Consider what happens in each byte: | |
78 | - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff, | |
79 | and step 3 transforms it into 0x80. A carry can also be propagated | |
80 | to more significant bytes. | |
81 | - If a byte of longword1 is nonzero, let its lowest 1 bit be at | |
82 | position k (0 <= k <= 7); so the lowest k bits are 0. After step 1, | |
83 | the byte ends in a single bit of value 0 and k bits of value 1. | |
84 | After step 2, the result is just k bits of value 1: 2^k - 1. After | |
85 | step 3, the result is 0. And no carry is produced. | |
86 | So, if longword1 has only non-zero bytes, tmp is zero. | |
87 | Whereas if longword1 has a zero byte, call j the position of the least | |
88 | significant zero byte. Then the result has a zero at positions 0, ..., | |
89 | j-1 and a 0x80 at position j. We cannot predict the result at the more | |
90 | significant bytes (positions j+1..3), but it does not matter since we | |
91 | already have a non-zero bit at position 8*j+7. | |
92 | ||
93 | The test whether any byte in longword1 is zero is equivalent | |
94 | to testing whether tmp is nonzero. | |
95 | ||
96 | This test can read beyond the end of a string, depending on where | |
97 | C_IN is encountered. However, this is considered safe since the | |
98 | initialization phase ensured that the read will be aligned, | |
99 | therefore, the read will not cross page boundaries and will not | |
100 | cause a fault. */ | |
101 | ||
102 | while (1) | |
103 | { | |
104 | longword longword1 = *longword_ptr ^ repeated_c; | |
105 | ||
dc6c21da | 106 | if ((((longword1 - repeated_one) & ~longword1) & repeated_hibit) != 0) |
8424cc97 SM |
107 | break; |
108 | longword_ptr++; | |
109 | } | |
110 | ||
dc6c21da | 111 | char_ptr = s = longword_ptr; |
8424cc97 SM |
112 | |
113 | /* At this point, we know that one of the sizeof (longword) bytes | |
dc6c21da | 114 | starting at char_ptr is == c. If we knew endianness, we |
8424cc97 SM |
115 | could determine the first such byte without any further memory |
116 | accesses, just by looking at the tmp result from the last loop | |
dc6c21da TT |
117 | iteration. However, the following simple and portable code does |
118 | not attempt this potential optimization. */ | |
8424cc97 | 119 | |
8424cc97 SM |
120 | while (*char_ptr != c) |
121 | char_ptr++; | |
122 | return (void *) char_ptr; | |
123 | } | |
dc6c21da TT |
124 | |
125 | #endif |