source: trunk/poppler/mypoppler/poppler/strtok_r.cpp @ 461

Last change on this file since 461 was 461, checked in by Silvan Scherrer, 11 years ago

poppler update to 0.14.2

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