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