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