1 /*
2 * This file has been modified for the cdrkit suite.
3 *
4 * The behaviour and appearence of the program code below can differ to a major
5 * extent from the version distributed by the original author(s).
6 *
7 * For details, see Changelog file distributed with the cdrkit package. If you
8 * received this file from another source then ask the distributing person for
9 * a log of modifications.
10 *
11 */
12
13 /* @(#)findbytes.c 1.2 03/06/15 Copyright 2000-2003 J. Schilling */
14 /*
15 * Find a byte with specific value in memory.
16 *
17 * Copyright (c) 2000-2003 J. Schilling
18 *
19 * Based on a strlen() idea from Torbjorn Granlund (tege@sics.se) and
20 * Dan Sahlin (dan@sics.se) and the memchr() suggestion
21 * from Dick Karpinski (dick@cca.ucsf.edu).
22 */
23 /*
24 * This program is free software; you can redistribute it and/or modify
25 * it under the terms of the GNU General Public License version 2
26 * as published by the Free Software Foundation.
27 *
28 * This program is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 * GNU General Public License for more details.
32 *
33 * You should have received a copy of the GNU General Public License along with
34 * this program; see the file COPYING. If not, write to the Free Software
35 * Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
36 */
37
38 #include <mconfig.h>
39 #include <stdxlib.h>
40 #include <utypes.h>
41 #include <align.h>
42 #include <standard.h>
43 #include <strdefs.h>
44 #include <schily.h>
45
46 #ifdef PROTOTYPES
47 EXPORT char *
findbytes(const void * vp,int cnt,char val)48 findbytes(const void *vp, int cnt, char val)
49 #else
50 EXPORT char *
51 findbytes(vp, cnt, val)
52 const void *vp;
53 register int cnt;
54 char val;
55 #endif
56 {
57 register Uchar uval = (Uchar)val;
58 register const Uchar *cp = (Uchar *)vp;
59 register const Ulong *lp;
60 register Ulong lval;
61 register Ulong lmask;
62 register Ulong magic_mask;
63
64 /*
65 * Test byte-wise until cp is properly aligned for a long pointer.
66 */
67 while (--cnt >= 0 && !laligned(cp)) {
68 if (*cp++ == uval)
69 return ((char *)--cp);
70 }
71 cnt++;
72
73 /*
74 * The magic mask is a long word where all carry bits a clear.
75 * This are bits 8, 16, 24 ...
76 * In addition, the top bit is not set (e.g bit 31 or 63). The magic
77 * mask will look this way:
78 *
79 * bits: 01111110 11111110 ... 11111110 11111111
80 * bytes: AAAAAAAA BBBBBBBB ... CCCCCCCC DDDDDDDD
81 *
82 * If we add anything to this magic number, no carry bit will change if
83 * it is the first carry bit left to a 0 byte. Adding anything != 0
84 * to the magic number will just turn the carry bit left to the byte
85 * but does not propagate any further.
86 */
87 #if SIZE_LONG == 4
88 magic_mask = 0x7EFEFEFFL;
89 #else
90 #if SIZE_LONG == 8
91 magic_mask = 0x7EFEFEFEFEFEFEFFL;
92 #else
93 /*
94 * #error will not work for all compilers (e.g. sunos4)
95 * The following line will abort compilation on all compilers
96 * if none of the above is defines. And that's what we want.
97 */
98 error SIZE_LONG has unknown value
99 #endif
100 #endif
101
102 lmask = val & 0xFF;
103 lmask |= lmask << 8;
104 lmask |= lmask << 16;
105 #if SIZE_LONG > 4
106 lmask |= lmask << 32;
107 #endif
108 #if SIZE_LONG > 8
109 error SIZE_LONG has unknown value
110 #endif
111 for (lp = (const Ulong *)cp; cnt >= sizeof (long); cnt -= sizeof (long)) {
112 /*
113 * We are not looking for 0 bytes so we need to xor with the
114 * long mask of repeated bytes. If any of the bytes matches our
115 * wanted char, we will create a 0 byte in the current long.
116 * But how will we find if at least one byte in a long is zero?
117 *
118 * If we add 'magic_mask' and any of the holes in the magic
119 * mask do not change, we most likely found a 0 byte in the
120 * long word. It is only a most likely match because if bits
121 * 24..30 (ot bits 56..62) are 0 but bit 31 (or bit 63) is set
122 * we will believe that we found a match but there is none.
123 * This will happen if there is 0x80nnnnnn / 0x80nnnnnnnnnnnnnn
124 */
125 lval = (*lp++ ^ lmask); /* create 0 byte on match */
126 lval = (lval + magic_mask) ^ ~lval; /* set bits unchanged by +*/
127 if ((lval & ~magic_mask) != 0) { /* a magic hole was set */
128 /*
129 * If any of the hole bits did not change by addition,
130 * we most likely had a match.
131 * If this was a correct match, find the matching byte.
132 */
133 cp = (const Uchar *)(lp - 1);
134
135 if (cp[0] == uval)
136 return ((char *)cp);
137 if (cp[1] == uval)
138 return ((char *)&cp[1]);
139 if (cp[2] == uval)
140 return ((char *)&cp[2]);
141 if (cp[3] == uval)
142 return ((char *)&cp[3]);
143 #if SIZE_LONG > 4
144 if (cp[4] == uval)
145 return ((char *)&cp[4]);
146 if (cp[5] == uval)
147 return ((char *)&cp[5]);
148 if (cp[6] == uval)
149 return ((char *)&cp[6]);
150 if (cp[7] == uval)
151 return ((char *)&cp[7]);
152 #endif
153 #if SIZE_LONG > 8
154 error SIZE_LONG has unknown value
155 #endif
156 }
157 }
158
159 for (cp = (const Uchar *)lp; --cnt >= 0; ) {
160 if (*cp++ == uval)
161 return ((char *)--cp);
162 }
163 return ((char *)NULL);
164 }
165