Mercurial > hg > octave-kai > gnulib-hg
annotate lib/memchr2.c @ 10690:01f3623813da
Split winsock.c into many smaller files.
* lib/close.c: Add _gl_close_fd_maybe_socket from winsock.c.
* lib/accept.c: New file, based on winsock.c.
* lib/bind.c: New file, based on winsock.c.
* lib/connect.c: New file, based on winsock.c.
* lib/getpeername.c: New file, based on winsock.c.
* lib/getsockname.c: New file, based on winsock.c.
* lib/getsockopt.c: New file, based on winsock.c.
* lib/ioctl.c: New file, based on winsock.c.
* lib/listen.c: New file, based on winsock.c.
* lib/recv.c: New file, based on winsock.c.
* lib/recvfrom.c: New file, based on winsock.c.
* lib/send.c: New file, based on winsock.c.
* lib/sendto.c: New file, based on winsock.c.
* lib/setsockopt.c: New file, based on winsock.c.
* lib/shutdown.c: New file, based on winsock.c.
* lib/socket.c: New file, based on winsock.c.
* lib/w32sock.h: New file, based on winsock.c.
* lib/winsock.c: Remove file.
* modules/accept: Likewise.
* modules/bind: Likewise.
* modules/connect: Likewise.
* modules/getpeername: Likewise.
* modules/getsockname: Likewise.
* modules/getsockopt: Likewise.
* modules/ioctl: Likewise.
* modules/listen: Likewise.
* modules/recv: Likewise.
* modules/recvfrom: Likewise.
* modules/send: Likewise.
* modules/sendto: Likewise.
* modules/setsockopt: Likewise.
* modules/shutdown: Likewise.
* modules/socket: Use socket.c instead of winsock.c.
* modules/sys_socket: Remove (unneeded?) dependency on winsock.c.
* doc/posix-functions/accept.texi: Doc fix.
* doc/posix-functions/bind.texi: Doc fix.
* doc/posix-functions/close.texi: Doc fix.
* doc/posix-functions/connect.texi: Doc fix.
* doc/posix-functions/getpeername.texi: Doc fix.
* doc/posix-functions/getsockname.texi: Doc fix.
* doc/posix-functions/getsockopt.texi: Doc fix.
* doc/posix-functions/ioctl.texi: Doc fix.
* doc/posix-functions/listen.texi: Doc fix.
* doc/posix-functions/recv.texi: Doc fix.
* doc/posix-functions/recvfrom.texi: Doc fix.
* doc/posix-functions/send.texi: Doc fix.
* doc/posix-functions/sendto.texi: Doc fix.
* doc/posix-functions/setsockopt.texi: Doc fix.
* doc/posix-functions/shutdown.texi: Doc fix.
* doc/posix-functions/socket.texi: Doc fix.
| author | Simon Josefsson <simon@josefsson.org> |
|---|---|
| date | Tue, 21 Oct 2008 12:17:19 +0200 |
| parents | 901b50b38fae |
| children | e8d2c6fc33ad |
| rev | line source |
|---|---|
| 9742 | 1 /* Copyright (C) 1991, 1993, 1996, 1997, 1999, 2000, 2003, 2004, 2006, |
| 2 2008 Free Software Foundation, Inc. | |
| 3 | |
| 4 Based on strlen implementation by Torbjorn Granlund (tege@sics.se), | |
| 5 with help from Dan Sahlin (dan@sics.se) and | |
| 6 commentary by Jim Blandy (jimb@ai.mit.edu); | |
| 7 adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu), | |
| 8 and implemented in glibc by Roland McGrath (roland@ai.mit.edu). | |
| 9 Extension to memchr2 implemented by Eric Blake (ebb9@byu.net). | |
| 10 | |
| 11 This program is free software: you can redistribute it and/or modify it | |
| 12 under the terms of the GNU General Public License as published by the | |
| 13 Free Software Foundation; either version 3 of the License, or any | |
| 14 later version. | |
| 15 | |
| 16 This program is distributed in the hope that it will be useful, | |
| 17 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 19 GNU General Public License for more details. | |
| 20 | |
| 21 You should have received a copy of the GNU General Public License | |
| 22 along with this program. If not, see <http://www.gnu.org/licenses/>. */ | |
| 23 | |
| 24 #include <config.h> | |
| 25 | |
| 26 #include "memchr2.h" | |
| 27 | |
| 28 #include <limits.h> | |
| 29 #include <stdint.h> | |
| 30 #include <string.h> | |
| 31 | |
| 32 /* Return the first address of either C1 or C2 (treated as unsigned | |
| 33 char) that occurs within N bytes of the memory region S. If | |
| 34 neither byte appears, return NULL. */ | |
| 35 void * | |
| 36 memchr2 (void const *s, int c1_in, int c2_in, size_t n) | |
| 37 { | |
| 9967 | 38 /* On 32-bit hardware, choosing longword to be a 32-bit unsigned |
| 39 long instead of a 64-bit uintmax_t tends to give better | |
| 40 performance. On 64-bit hardware, unsigned long is generally 64 | |
| 41 bits already. Change this typedef to experiment with | |
| 42 performance. */ | |
| 9995 | 43 typedef unsigned long int longword; |
| 9967 | 44 |
| 9742 | 45 const unsigned char *char_ptr; |
| 9967 | 46 const longword *longword_ptr; |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
47 longword repeated_one; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
48 longword repeated_c1; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
49 longword repeated_c2; |
| 9742 | 50 unsigned char c1; |
| 51 unsigned char c2; | |
| 52 | |
| 53 c1 = (unsigned char) c1_in; | |
| 54 c2 = (unsigned char) c2_in; | |
| 55 | |
| 56 if (c1 == c2) | |
| 57 return memchr (s, c1, n); | |
| 58 | |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
59 /* Handle the first few bytes by reading one byte at a time. |
| 9742 | 60 Do this until CHAR_PTR is aligned on a longword boundary. */ |
| 61 for (char_ptr = (const unsigned char *) s; | |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
62 n > 0 && (size_t) char_ptr % sizeof (longword) != 0; |
| 9742 | 63 --n, ++char_ptr) |
| 64 if (*char_ptr == c1 || *char_ptr == c2) | |
| 65 return (void *) char_ptr; | |
| 66 | |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
67 longword_ptr = (const longword *) char_ptr; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
68 |
| 9742 | 69 /* All these elucidatory comments refer to 4-byte longwords, |
| 70 but the theory applies equally well to any size longwords. */ | |
| 71 | |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
72 /* Compute auxiliary longword values: |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
73 repeated_one is a value which has a 1 in every byte. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
74 repeated_c1 has c1 in every byte. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
75 repeated_c2 has c2 in every byte. */ |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
76 repeated_one = 0x01010101; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
77 repeated_c1 = c1 | (c1 << 8); |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
78 repeated_c2 = c2 | (c2 << 8); |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
79 repeated_c1 |= repeated_c1 << 16; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
80 repeated_c2 |= repeated_c2 << 16; |
| 9995 | 81 if (0xffffffffU < (longword) -1) |
|
9951
03b212920228
Work around preprocessors that don't handle UINTMAX_MAX.
Eric Blake <ebb9@byu.net>
parents:
9745
diff
changeset
|
82 { |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
83 repeated_one |= repeated_one << 31 << 1; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
84 repeated_c1 |= repeated_c1 << 31 << 1; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
85 repeated_c2 |= repeated_c2 << 31 << 1; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
86 if (8 < sizeof (longword)) |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
87 { |
| 9984 | 88 size_t i; |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
89 |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
90 for (i = 64; i < sizeof (longword) * 8; i *= 2) |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
91 { |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
92 repeated_one |= repeated_one << i; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
93 repeated_c1 |= repeated_c1 << i; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
94 repeated_c2 |= repeated_c2 << i; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
95 } |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
96 } |
|
9951
03b212920228
Work around preprocessors that don't handle UINTMAX_MAX.
Eric Blake <ebb9@byu.net>
parents:
9745
diff
changeset
|
97 } |
| 9742 | 98 |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
99 /* Instead of the traditional loop which tests each byte, we will test a |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
100 longword at a time. The tricky part is testing if *any of the four* |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
101 bytes in the longword in question are equal to c1 or c2. We first use |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
102 an xor with repeated_c1 and repeated_c2, respectively. This reduces |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
103 the task to testing whether *any of the four* bytes in longword1 or |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
104 longword2 is zero. |
| 9967 | 105 |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
106 Let's consider longword1. We compute tmp1 = |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
107 ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7). |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
108 That is, we perform the following operations: |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
109 1. Subtract repeated_one. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
110 2. & ~longword1. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
111 3. & a mask consisting of 0x80 in every byte. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
112 Consider what happens in each byte: |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
113 - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff, |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
114 and step 3 transforms it into 0x80. A carry can also be propagated |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
115 to more significant bytes. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
116 - If a byte of longword1 is nonzero, let its lowest 1 bit be at |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
117 position k (0 <= k <= 7); so the lowest k bits are 0. After step 1, |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
118 the byte ends in a single bit of value 0 and k bits of value 1. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
119 After step 2, the result is just k bits of value 1: 2^k - 1. After |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
120 step 3, the result is 0. And no carry is produced. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
121 So, if longword1 has only non-zero bytes, tmp1 is zero. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
122 Whereas if longword1 has a zero byte, call j the position of the least |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
123 significant zero byte. Then the result has a zero at positions 0, ..., |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
124 j-1 and a 0x80 at position j. We cannot predict the result at the more |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
125 significant bytes (positions j+1..3), but it does not matter since we |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
126 already have a non-zero bit at position 8*j+7. |
| 9967 | 127 |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
128 Similary, we compute tmp2 = |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
129 ((longword2 - repeated_one) & ~longword2) & (repeated_one << 7). |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
130 |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
131 The test whether any byte in longword1 or longword2 is zero is equivalent |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
132 to testing whether tmp1 is nonzero or tmp2 is nonzero. We can combine |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
133 this into a single test, whether (tmp1 | tmp2) is nonzero. */ |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
134 |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
135 while (n >= sizeof (longword)) |
| 9742 | 136 { |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
137 longword longword1 = *longword_ptr ^ repeated_c1; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
138 longword longword2 = *longword_ptr ^ repeated_c2; |
| 9742 | 139 |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
140 if (((((longword1 - repeated_one) & ~longword1) |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
141 | ((longword2 - repeated_one) & ~longword2)) |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
142 & (repeated_one << 7)) != 0) |
| 9967 | 143 break; |
| 144 longword_ptr++; | |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
145 n -= sizeof (longword); |
| 9742 | 146 } |
| 147 | |
| 148 char_ptr = (const unsigned char *) longword_ptr; | |
| 149 | |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
150 /* At this point, we know that either n < sizeof (longword), or one of the |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
151 sizeof (longword) bytes starting at char_ptr is == c1 or == c2. On |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
152 little-endian machines, we could determine the first such byte without |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
153 any further memory accesses, just by looking at the (tmp1 | tmp2) result |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
154 from the last loop iteration. But this does not work on big-endian |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
155 machines. Choose code that works in both cases. */ |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
156 |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
157 for (; n > 0; --n, ++char_ptr) |
| 9742 | 158 { |
| 159 if (*char_ptr == c1 || *char_ptr == c2) | |
| 160 return (void *) char_ptr; | |
| 161 } | |
| 162 | |
| 9967 | 163 return NULL; |
| 9742 | 164 } |