← Back to branch summary

~linaro-toolchain-dev/cortex-strings/trunk

« back to all changes in this revision

Viewing changes to reference/glibc/memchr.c

  • Committer: Michael Hope
  • Date: 2012-06-12 03:20:30 UTC
  • Revision ID: michael.hope@linaro.org-20120612032030-5ceelkcw4zi300y4
Updated the GLIBC routines and shifted the C only routines out.

Show diffs side-by-side

added added

removed removed

Lines of Context:
reference/glibc/memchr.c
1
 
/* Copyright (C) 1991,93,96,97,99,2000,2003 Free Software Foundation, Inc.
2
 
   This file is part of the GNU C Library.
3
 
   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
4
 
   with help from Dan Sahlin (dan@sics.se) and
5
 
   commentary by Jim Blandy (jimb@ai.mit.edu);
6
 
   adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
7
 
   and implemented by Roland McGrath (roland@ai.mit.edu).
8
 
 
9
 
   The GNU C Library is free software; you can redistribute it and/or
10
 
   modify it under the terms of the GNU Lesser General Public
11
 
   License as published by the Free Software Foundation; either
12
 
   version 2.1 of the License, or (at your option) any later version.
13
 
 
14
 
   The GNU C Library is distributed in the hope that it will be useful,
15
 
   but WITHOUT ANY WARRANTY; without even the implied warranty of
16
 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17
 
   Lesser General Public License for more details.
18
 
 
19
 
   You should have received a copy of the GNU Lesser General Public
20
 
   License along with the GNU C Library; if not, write to the Free
21
 
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
22
 
   02111-1307 USA.  */
23
 
 
24
 
#undef __ptr_t
25
 
# define __ptr_t void *
26
 
# define reg_char char
27
 
 
28
 
# include <string.h>
29
 
# include <stdlib.h>
30
 
# include <limits.h>
31
 
 
32
 
#define LONG_MAX_32_BITS 2147483647
33
 
 
34
 
#ifndef LONG_MAX
35
 
#define LONG_MAX LONG_MAX_32_BITS
36
 
#endif
37
 
 
38
 
/* Search no more than N bytes of S for C.  */
39
 
__ptr_t
40
 
memchr (s, c_in, n)
41
 
     const __ptr_t s;
42
 
     int c_in;
43
 
     size_t n;
44
 
{
45
 
  const unsigned char *char_ptr;
46
 
  const unsigned long int *longword_ptr;
47
 
  unsigned long int longword, magic_bits, charmask;
48
 
  unsigned reg_char c;
49
 
 
50
 
  c = (unsigned char) c_in;
51
 
 
52
 
  /* Handle the first few characters by reading one character at a time.
53
 
     Do this until CHAR_PTR is aligned on a longword boundary.  */
54
 
  for (char_ptr = (const unsigned char *) s;
55
 
       n > 0 && ((unsigned long int) char_ptr
56
 
                 & (sizeof (longword) - 1)) != 0;
57
 
       --n, ++char_ptr)
58
 
    if (*char_ptr == c)
59
 
      return (__ptr_t) char_ptr;
60
 
 
61
 
  /* All these elucidatory comments refer to 4-byte longwords,
62
 
     but the theory applies equally well to 8-byte longwords.  */
63
 
 
64
 
  longword_ptr = (unsigned long int *) char_ptr;
65
 
 
66
 
  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
67
 
     the "holes."  Note that there is a hole just to the left of
68
 
     each byte, with an extra at the end:
69
 
 
70
 
     bits:  01111110 11111110 11111110 11111111
71
 
     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
72
 
 
73
 
     The 1-bits make sure that carries propagate to the next 0-bit.
74
 
     The 0-bits provide holes for carries to fall into.  */
75
 
 
76
 
  if (sizeof (longword) != 4 && sizeof (longword) != 8)
77
 
    abort ();
78
 
 
79
 
#if LONG_MAX <= LONG_MAX_32_BITS
80
 
  magic_bits = 0x7efefeff;
81
 
#else
82
 
  magic_bits = ((unsigned long int) 0x7efefefe << 32) | 0xfefefeff;
83
 
#endif
84
 
 
85
 
  /* Set up a longword, each of whose bytes is C.  */
86
 
  charmask = c | (c << 8);
87
 
  charmask |= charmask << 16;
88
 
#if LONG_MAX > LONG_MAX_32_BITS
89
 
  charmask |= charmask << 32;
90
 
#endif
91
 
 
92
 
  /* Instead of the traditional loop which tests each character,
93
 
     we will test a longword at a time.  The tricky part is testing
94
 
     if *any of the four* bytes in the longword in question are zero.  */
95
 
  while (n >= sizeof (longword))
96
 
    {
97
 
      /* We tentatively exit the loop if adding MAGIC_BITS to
98
 
         LONGWORD fails to change any of the hole bits of LONGWORD.
99
 
 
100
 
         1) Is this safe?  Will it catch all the zero bytes?
101
 
         Suppose there is a byte with all zeros.  Any carry bits
102
 
         propagating from its left will fall into the hole at its
103
 
         least significant bit and stop.  Since there will be no
104
 
         carry from its most significant bit, the LSB of the
105
 
         byte to the left will be unchanged, and the zero will be
106
 
         detected.
107
 
 
108
 
         2) Is this worthwhile?  Will it ignore everything except
109
 
         zero bytes?  Suppose every byte of LONGWORD has a bit set
110
 
         somewhere.  There will be a carry into bit 8.  If bit 8
111
 
         is set, this will carry into bit 16.  If bit 8 is clear,
112
 
         one of bits 9-15 must be set, so there will be a carry
113
 
         into bit 16.  Similarly, there will be a carry into bit
114
 
         24.  If one of bits 24-30 is set, there will be a carry
115
 
         into bit 31, so all of the hole bits will be changed.
116
 
 
117
 
         The one misfire occurs when bits 24-30 are clear and bit
118
 
         31 is set; in this case, the hole at bit 31 is not
119
 
         changed.  If we had access to the processor carry flag,
120
 
         we could close this loophole by putting the fourth hole
121
 
         at bit 32!
122
 
 
123
 
         So it ignores everything except 128's, when they're aligned
124
 
         properly.
125
 
 
126
 
         3) But wait!  Aren't we looking for C, not zero?
127
 
         Good point.  So what we do is XOR LONGWORD with a longword,
128
 
         each of whose bytes is C.  This turns each byte that is C
129
 
         into a zero.  */
130
 
 
131
 
      longword = *longword_ptr++ ^ charmask;
132
 
 
133
 
      /* Add MAGIC_BITS to LONGWORD.  */
134
 
      if ((((longword + magic_bits)
135
 
 
136
 
            /* Set those bits that were unchanged by the addition.  */
137
 
            ^ ~longword)
138
 
 
139
 
           /* Look at only the hole bits.  If any of the hole bits
140
 
              are unchanged, most likely one of the bytes was a
141
 
              zero.  */
142
 
           & ~magic_bits) != 0)
143
 
        {
144
 
          /* Which of the bytes was C?  If none of them were, it was
145
 
             a misfire; continue the search.  */
146
 
 
147
 
          const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
148
 
 
149
 
          if (cp[0] == c)
150
 
            return (__ptr_t) cp;
151
 
          if (cp[1] == c)
152
 
            return (__ptr_t) &cp[1];
153
 
          if (cp[2] == c)
154
 
            return (__ptr_t) &cp[2];
155
 
          if (cp[3] == c)
156
 
            return (__ptr_t) &cp[3];
157
 
#if LONG_MAX > 2147483647
158
 
          if (cp[4] == c)
159
 
            return (__ptr_t) &cp[4];
160
 
          if (cp[5] == c)
161
 
            return (__ptr_t) &cp[5];
162
 
          if (cp[6] == c)
163
 
            return (__ptr_t) &cp[6];
164
 
          if (cp[7] == c)
165
 
            return (__ptr_t) &cp[7];
166
 
#endif
167
 
        }
168
 
 
169
 
      n -= sizeof (longword);
170
 
    }
171
 
 
172
 
  char_ptr = (const unsigned char *) longword_ptr;
173
 
 
174
 
  while (n-- > 0)
175
 
    {
176
 
      if (*char_ptr == c)
177
 
        return (__ptr_t) char_ptr;
178
 
      else
179
 
        ++char_ptr;
180
 
    }
181
 
 
182
 
  return 0;
183
 
}