1 /* @(#)findbytes.c 1.7 10/08/23 Copyright 2000-2009 J. Schilling */
2 /*
3 * Find a byte with specific value in memory.
4 *
5 * Copyright (c) 2000-2009 J. Schilling
6 *
7 * Based on a strlen() idea from Torbjorn Granlund (tege@sics.se) and
8 * Dan Sahlin (dan@sics.se) and the memchr() suggestion
9 * from Dick Karpinski (dick@cca.ucsf.edu).
10 */
11 /*
12 * The contents of this file are subject to the terms of the
13 * Common Development and Distribution License, Version 1.0 only
14 * (the "License"). You may not use this file except in compliance
15 * with the License.
16 *
17 * See the file CDDL.Schily.txt in this distribution for details.
18 * A copy of the CDDL is also available via the Internet at
19 * http://www.opensource.org/licenses/cddl1.txt
20 *
21 * When distributing Covered Code, include this CDDL HEADER in each
22 * file and include the License file CDDL.Schily.txt from this distribution.
23 */
24
25 #include <schily/mconfig.h>
26 #include <schily/stdlib.h>
27 #include <schily/utypes.h>
28 #include <schily/align.h>
29 #include <schily/standard.h>
30 #include <schily/string.h>
31 #include <schily/types.h>
32 #include <schily/schily.h>
33
34 /*
35 * findbytes(p, cnt, val) is the same as memchr(p, val, cnt)
36 */
37 #ifdef PROTOTYPES
38 EXPORT char *
findbytes(const void * vp,ssize_t cnt,char val)39 findbytes(const void *vp, ssize_t cnt, char val)
40 #else
41 EXPORT char *
42 findbytes(vp, cnt, val)
43 const void *vp;
44 register ssize_t cnt;
45 char val;
46 #endif
47 {
48 register Uchar uval = (Uchar)val;
49 register const Uchar *cp = (Uchar *)vp;
50 register const Ulong *lp;
51 register Ulong lval;
52 register Ulong lmask;
53 register Ulong magic_mask;
54
55 /*
56 * Test byte-wise until cp is properly aligned for a long pointer.
57 */
58 while (--cnt >= 0 && !laligned(cp)) {
59 if (*cp++ == uval)
60 return ((char *)--cp);
61 }
62 cnt++;
63
64 /*
65 * The magic mask is a long word where all carry bits a clear.
66 * This are bits 8, 16, 24 ...
67 * In addition, the top bit is not set (e.g bit 31 or 63). The magic
68 * mask will look this way:
69 *
70 * bits: 01111110 11111110 ... 11111110 11111111
71 * bytes: AAAAAAAA BBBBBBBB ... CCCCCCCC DDDDDDDD
72 *
73 * If we add anything to this magic number, no carry bit will change if
74 * it is the first carry bit left to a 0 byte. Adding anything != 0
75 * to the magic number will just turn the carry bit left to the byte
76 * but does not propagate any further.
77 */
78 #if SIZE_LONG == 4
79 magic_mask = 0x7EFEFEFFL;
80 #else
81 #if SIZE_LONG == 8
82 magic_mask = 0x7EFEFEFEFEFEFEFFL;
83 #else
84 /*
85 * #error will not work for all compilers (e.g. sunos4)
86 * The following line will abort compilation on all compilers
87 * if none of the above is defines. And that's what we want.
88 */
89 error SIZE_LONG has unknown value
90 #endif
91 #endif
92
93 lmask = val & 0xFF;
94 lmask |= lmask << 8;
95 lmask |= lmask << 16;
96 #if SIZE_LONG > 4
97 lmask |= lmask << 32;
98 #endif
99 #if SIZE_LONG > 8
100 error SIZE_LONG has unknown value
101 #endif
102 for (lp = (const Ulong *)cp; cnt >= sizeof (long);
103 cnt -= sizeof (long)) {
104 /*
105 * We are not looking for 0 bytes so we need to xor with the
106 * long mask of repeated bytes. If any of the bytes matches our
107 * wanted char, we will create a 0 byte in the current long.
108 * But how will we find if at least one byte in a long is zero?
109 *
110 * If we add 'magic_mask' and any of the holes in the magic
111 * mask do not change, we most likely found a 0 byte in the
112 * long word. It is only a most likely match because if bits
113 * 24..30 (ot bits 56..62) are 0 but bit 31 (or bit 63) is set
114 * we will believe that we found a match but there is none.
115 * This will happen if there is 0x80nnnnnn / 0x80nnnnnnnnnnnnnn
116 */
117 lval = (*lp++ ^ lmask); /* create 0 byte on match */
118 lval = (lval + magic_mask) ^ ~lval; /* + and set unchg. bits */
119 if ((lval & ~magic_mask) != 0) { /* a magic hole was set */
120 /*
121 * If any of the hole bits did not change by addition,
122 * we most likely had a match.
123 * If this was a correct match, find the matching byte.
124 */
125 cp = (const Uchar *)(lp - 1);
126
127 if (cp[0] == uval)
128 return ((char *)cp);
129 if (cp[1] == uval)
130 return ((char *)&cp[1]);
131 if (cp[2] == uval)
132 return ((char *)&cp[2]);
133 if (cp[3] == uval)
134 return ((char *)&cp[3]);
135 #if SIZE_LONG > 4
136 if (cp[4] == uval)
137 return ((char *)&cp[4]);
138 if (cp[5] == uval)
139 return ((char *)&cp[5]);
140 if (cp[6] == uval)
141 return ((char *)&cp[6]);
142 if (cp[7] == uval)
143 return ((char *)&cp[7]);
144 #endif
145 #if SIZE_LONG > 8
146 error SIZE_LONG has unknown value
147 #endif
148 }
149 }
150
151 for (cp = (const Uchar *)lp; --cnt >= 0; ) {
152 if (*cp++ == uval)
153 return ((char *)--cp);
154 }
155 return ((char *)NULL);
156 }
157