Mercurial > hg > octave-kai > gnulib-hg

comparison lib/memchr.c @ 5159:a535859efd14

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge from coreutils.
author Paul Eggert <eggert@cs.ucla.edu>
date Sat, 07 Aug 2004 00:09:38 +0000
parents 42147e1c0cee
children a48fb0e98c8c
comparison
equal deleted inserted replaced
5158:c710d6c89900 5159:a535859efd14
1 /* Copyright (C) 1991, 1993, 1996, 1997, 1999, 2000, 2003 Free 1 /* Copyright (C) 1991, 1993, 1996, 1997, 1999, 2000, 2003, 2004 Free
2 Software Foundation, Inc. 2 Software Foundation, Inc.
3 3
4 Based on strlen implementation by Torbjorn Granlund (tege@sics.se), 4 Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
5 with help from Dan Sahlin (dan@sics.se) and 5 with help from Dan Sahlin (dan@sics.se) and
6 commentary by Jim Blandy (jimb@ai.mit.edu); 6 commentary by Jim Blandy (jimb@ai.mit.edu);
29 # include <config.h> 29 # include <config.h>
30 #endif 30 #endif
31 31
32 #include <string.h> 32 #include <string.h>
33 33
34 #include <stddef.h>
35
34 #if defined _LIBC 36 #if defined _LIBC
35 # include <memcopy.h> 37 # include <memcopy.h>
36 #else 38 #else
37 # define reg_char char 39 # define reg_char char
38 #endif 40 #endif
39 41
40 #include <limits.h> 42 #include <limits.h>
41 #include <stdlib.h> 43
42
43 #define LONG_MAX_32_BITS 2147483647
44
45 #include <sys/types.h>
46 #if HAVE_BP_SYM_H || defined _LIBC 44 #if HAVE_BP_SYM_H || defined _LIBC
47 # include <bp-sym.h> 45 # include <bp-sym.h>
48 #else 46 #else
49 # define BP_SYM(sym) sym 47 # define BP_SYM(sym) sym
50 #endif 48 #endif
58 { 56 {
59 const unsigned char *char_ptr; 57 const unsigned char *char_ptr;
60 const unsigned long int *longword_ptr; 58 const unsigned long int *longword_ptr;
61 unsigned long int longword, magic_bits, charmask; 59 unsigned long int longword, magic_bits, charmask;
62 unsigned reg_char c; 60 unsigned reg_char c;
61 int i;
63 62
64 c = (unsigned char) c_in; 63 c = (unsigned char) c_in;
65 64
66 /* Handle the first few characters by reading one character at a time. 65 /* Handle the first few characters by reading one character at a time.
67 Do this until CHAR_PTR is aligned on a longword boundary. */ 66 Do this until CHAR_PTR is aligned on a longword boundary. */
68 for (char_ptr = (const unsigned char *) s; 67 for (char_ptr = (const unsigned char *) s;
69 n > 0 && ((unsigned long int) char_ptr 68 n > 0 && (size_t) char_ptr % sizeof longword != 0;
70 & (sizeof (longword) - 1)) != 0;
71 --n, ++char_ptr) 69 --n, ++char_ptr)
72 if (*char_ptr == c) 70 if (*char_ptr == c)
73 return (void *) char_ptr; 71 return (void *) char_ptr;
74 72
75 /* All these elucidatory comments refer to 4-byte longwords, 73 /* All these elucidatory comments refer to 4-byte longwords,
76 but the theory applies equally well to 8-byte longwords. */ 74 but the theory applies equally well to any size longwords. */
77 75
78 longword_ptr = (unsigned long int *) char_ptr; 76 longword_ptr = (const unsigned long int *) char_ptr;
79 77
80 /* Bits 31, 24, 16, and 8 of this number are zero. Call these bits 78 /* Bits 31, 24, 16, and 8 of this number are zero. Call these bits
81 the "holes." Note that there is a hole just to the left of 79 the "holes." Note that there is a hole just to the left of
82 each byte, with an extra at the end: 80 each byte, with an extra at the end:
83 81
85 bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD 83 bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
86 84
87 The 1-bits make sure that carries propagate to the next 0-bit. 85 The 1-bits make sure that carries propagate to the next 0-bit.
88 The 0-bits provide holes for carries to fall into. */ 86 The 0-bits provide holes for carries to fall into. */
89 87
90 if (sizeof (longword) != 4 && sizeof (longword) != 8) 88 /* Set MAGIC_BITS to be this pattern of 1 and 0 bits.
91 abort (); 89 Set CHARMASK to be a longword, each of whose bytes is C. */
92 90
93 #if LONG_MAX <= LONG_MAX_32_BITS 91 magic_bits = 0xfefefefe;
94 magic_bits = 0x7efefeff;
95 #else
96 magic_bits = ((unsigned long int) 0x7efefefe << 32) | 0xfefefeff;
97 #endif
98
99 /* Set up a longword, each of whose bytes is C. */
100 charmask = c | (c << 8); 92 charmask = c | (c << 8);
101 charmask |= charmask << 16; 93 charmask |= charmask << 16;
102 #if LONG_MAX > LONG_MAX_32_BITS 94 #if 0xffffffffU < ULONG_MAX
95 magic_bits |= magic_bits << 32;
103 charmask |= charmask << 32; 96 charmask |= charmask << 32;
104 #endif 97 if (8 < sizeof longword)
98 for (i = 64; i < sizeof longword * 8; i *= 2)
99 {
100 magic_bits |= magic_bits << i;
101 charmask |= charmask << i;
102 }
103 #endif
104 magic_bits = (ULONG_MAX >> 1) & (magic_bits | 1);
105 105
106 /* Instead of the traditional loop which tests each character, 106 /* Instead of the traditional loop which tests each character,
107 we will test a longword at a time. The tricky part is testing 107 we will test a longword at a time. The tricky part is testing
108 if *any of the four* bytes in the longword in question are zero. */ 108 if *any of the four* bytes in the longword in question are zero. */
109 while (n >= sizeof (longword)) 109 while (n >= sizeof longword)
110 { 110 {
111 /* We tentatively exit the loop if adding MAGIC_BITS to 111 /* We tentatively exit the loop if adding MAGIC_BITS to
112 LONGWORD fails to change any of the hole bits of LONGWORD. 112 LONGWORD fails to change any of the hole bits of LONGWORD.
113 113
114 1) Is this safe? Will it catch all the zero bytes? 114 1) Is this safe? Will it catch all the zero bytes?
166 return (void *) &cp[1]; 166 return (void *) &cp[1];
167 if (cp[2] == c) 167 if (cp[2] == c)
168 return (void *) &cp[2]; 168 return (void *) &cp[2];
169 if (cp[3] == c) 169 if (cp[3] == c)
170 return (void *) &cp[3]; 170 return (void *) &cp[3];
171 #if LONG_MAX > 2147483647 171 if (4 < sizeof longword && cp[4] == c)
172 if (cp[4] == c)
173 return (void *) &cp[4]; 172 return (void *) &cp[4];
174 if (cp[5] == c) 173 if (5 < sizeof longword && cp[5] == c)
175 return (void *) &cp[5]; 174 return (void *) &cp[5];
176 if (cp[6] == c) 175 if (6 < sizeof longword && cp[6] == c)
177 return (void *) &cp[6]; 176 return (void *) &cp[6];
178 if (cp[7] == c) 177 if (7 < sizeof longword && cp[7] == c)
179 return (void *) &cp[7]; 178 return (void *) &cp[7];
180 #endif 179 if (8 < sizeof longword)
180 for (i = 8; i < sizeof longword; i++)
181 if (cp[i] == c)
182 return (void *) &cp[i];
181 } 183 }
182 184
183 n -= sizeof (longword); 185 n -= sizeof longword;
184 } 186 }
185 187
186 char_ptr = (const unsigned char *) longword_ptr; 188 char_ptr = (const unsigned char *) longword_ptr;
187 189
188 while (n-- > 0) 190 while (n-- > 0)