seths / bitunwise (http://blogs.foognostic.net/)
Bitunwise is an algorithm which slowly reads and writes bits in useful ways. Currently just a single C file.
| commit 4: | 01e05336247a |
| parent 3: | fcdebccc9f5a |
| branch: | default |
actually, um, tested bu_memset. added bu_isset. primitive debugging output by setting bu_dbg_flag = 1
Seth Schroeder
15 months ago
Changed (Δ1.5 KB):
raw changeset »
bitunwise.c (64 lines added, 31 lines removed)
bitunwise.h (3 lines added, 0 lines removed)
main.c (10 lines added, 0 lines removed)
19 |
19 |
*/ |
20 |
20 |
|
21 |
21 |
#include "bitunwise.h" |
22 |
#include <stdio.h> |
|
22 |
23 |
|
23 |
24 |
/******************************************************************************/ |
24 |
25 |
|
41 |
42 |
#define EMIT 0 |
42 |
43 |
#define MATCH 1 |
43 |
44 |
|
45 |
int bu_dbg_flag = 0; |
|
46 |
||
44 |
47 |
/******************************************************************************/ |
45 |
48 |
|
46 |
49 |
typedef u08(*bytegetter)(const void *src, size_t byte); |
| … | … | @@ -72,7 +75,16 @@ typedef struct match_params { |
72 |
75 |
|
73 |
76 |
/******************************************************************************/ |
74 |
77 |
|
75 |
void process(const stream *left, const stream *right, size_t len, |
|
78 |
#define trace(val, pat) \ |
|
79 |
do { \ |
|
80 |
if (!bu_dbg_flag) { (val); } \ |
|
81 |
else { printf("%s:%d: " pat "\n", \ |
|
82 |
__FILE__, __LINE__, (val)); } \ |
|
83 |
} while (0) |
|
84 |
||
85 |
/******************************************************************************/ |
|
86 |
||
87 |
void process(const stream *left, const stream *right, size_t n, |
|
76 |
88 |
int op, int type, void **rc) { |
77 |
89 |
|
78 |
90 |
size_t i, j; |
| … | … | @@ -84,11 +96,11 @@ void process(const stream *left, const s |
84 |
96 |
else if (type == MATCH) |
85 |
97 |
match = *rc; |
86 |
98 |
|
87 |
for (i = 0; i < |
|
99 |
for (i = 0; i < n; i++) { |
|
88 |
100 |
unsigned char lc, rc, dc; |
89 |
101 |
|
90 |
lc = left->reader(left->src, i); |
|
91 |
rc = right->reader(right->src, i); |
|
102 |
trace(lc = left->reader(left->src, i), "%02X"); |
|
103 |
trace(rc = right->reader(right->src, i), "%02X"); |
|
92 |
104 |
|
93 |
105 |
for (j = 0; j < 8; j++) { |
94 |
106 |
const int flag = 1 << j; |
| … | … | @@ -97,40 +109,40 @@ void process(const stream *left, const s |
97 |
109 |
int test = 0; |
98 |
110 |
|
99 |
111 |
if (!lbit && !rbit) |
100 |
t |
|
112 |
trace(test = op & L0R0, "%d"); |
|
101 |
113 |
else if (lbit && !rbit) |
102 |
t |
|
114 |
trace(test = op & L1R0, "%d"); |
|
103 |
115 |
else if (!lbit && rbit) |
104 |
t |
|
116 |
trace(test = op & L0R1, "%d"); |
|
105 |
117 |
else |
106 |
t |
|
118 |
trace(test = op & L1R1, "%d"); |
|
107 |
119 |
|
108 |
120 |
if (type == EMIT) { |
109 |
121 |
if (test) |
110 |
|
|
122 |
trace(dc |= flag, "%02x"); |
|
111 |
123 |
else |
112 |
|
|
124 |
trace(dc &= ~flag, "%02x"); |
|
113 |
125 |
} |
114 |
126 |
else if (type == MATCH) { |
115 |
127 |
if ((!test && match->expect) || |
116 |
128 |
(test && !match->expect)) { |
117 |
|
|
129 |
trace(match->result = 0, "%d"); |
|
118 |
130 |
return; |
119 |
131 |
} |
120 |
132 |
} |
121 |
133 |
} |
122 |
134 |
|
123 |
135 |
if (type == EMIT) |
124 |
|
|
136 |
trace(((u08*)dst)[i] = dc, "%02x"); |
|
125 |
137 |
} |
126 |
138 |
|
127 |
139 |
if (type == MATCH) |
128 |
|
|
140 |
trace(match->result = 1, "%d"); |
|
129 |
141 |
} |
130 |
142 |
|
131 |
143 |
/******************************************************************************/ |
132 |
144 |
|
133 |
int match(const void *left, const void *right, size_t |
|
145 |
int match(const void *left, const void *right, size_t n, int op, int expect) { |
|
134 |
146 |
match_params params, *ptr; |
135 |
147 |
stream lstream, rstream; |
136 |
148 |
|
| … | … | @@ -141,7 +153,7 @@ int match(const void *left, const void * |
141 |
153 |
lstream.src = left; |
142 |
154 |
rstream.src = right; |
143 |
155 |
|
144 |
process(&lstream, &rstream, |
|
156 |
process(&lstream, &rstream, n, op, MATCH, (void**)&ptr); |
|
145 |
157 |
|
146 |
158 |
return params.result; |
147 |
159 |
} |
| … | … | @@ -149,42 +161,42 @@ int match(const void *left, const void * |
149 |
161 |
/******************************************************************************/ |
150 |
162 |
/* Begin implementation of external functions */ |
151 |
163 |
|
152 |
void* bu_bzero(void *dst, size_t |
|
164 |
void* bu_bzero(void *dst, size_t n) { |
|
153 |
165 |
stream lstream, rstream; |
154 |
166 |
|
155 |
167 |
lstream.reader = rstream.reader = something; |
156 |
168 |
|
157 |
process(&lstream, &rstream, |
|
169 |
process(&lstream, &rstream, n, op_never, EMIT, &dst); |
|
158 |
170 |
return dst; |
159 |
171 |
} |
160 |
172 |
|
161 |
173 |
/******************************************************************************/ |
162 |
174 |
|
163 |
void* bu_fill(void *dst, size_t |
|
175 |
void* bu_fill(void *dst, size_t n) { |
|
164 |
176 |
stream lstream, rstream; |
165 |
177 |
|
166 |
178 |
lstream.reader = rstream.reader = something; |
167 |
179 |
|
168 |
process(&lstream, &rstream, |
|
180 |
process(&lstream, &rstream, n, op_always, EMIT, &dst); |
|
169 |
181 |
return dst; |
170 |
182 |
} |
171 |
183 |
|
172 |
184 |
/******************************************************************************/ |
173 |
185 |
|
174 |
void* bu_memcpy(void *dst, const void *src, size_t |
|
186 |
void* bu_memcpy(void *dst, const void *src, size_t n) { |
|
175 |
187 |
stream lstream, rstream; |
176 |
188 |
|
177 |
189 |
lstream.reader = nthbyte; |
178 |
190 |
rstream.reader = something; |
179 |
191 |
lstream.src = src; |
180 |
192 |
|
181 |
process(&lstream, &rstream, |
|
193 |
process(&lstream, &rstream, n, op_left, EMIT, &dst); |
|
182 |
194 |
return dst; |
183 |
195 |
} |
184 |
196 |
|
185 |
197 |
/******************************************************************************/ |
186 |
198 |
|
187 |
void *bu_memset(void *dst, int val, size_t |
|
199 |
void *bu_memset(void *dst, int val, size_t n) { |
|
188 |
200 |
stream lstream, rstream; |
189 |
201 |
u08 src; |
190 |
202 |
|
| … | … | @@ -194,13 +206,13 @@ void *bu_memset(void *dst, int val, size |
194 |
206 |
|
195 |
207 |
rstream.reader = something; |
196 |
208 |
|
197 |
process(&lstream, &rstream, |
|
209 |
process(&lstream, &rstream, n, op_left, EMIT, &dst); |
|
198 |
210 |
return dst; |
199 |
211 |
} |
200 |
212 |
|
201 |
213 |
/******************************************************************************/ |
202 |
214 |
|
203 |
void* bu_invert(void *dst, const void *src, size_t |
|
215 |
void* bu_invert(void *dst, const void *src, size_t n) { |
|
204 |
216 |
stream lstream, rstream; |
205 |
217 |
|
206 |
218 |
lstream.reader = nthbyte; |
| … | … | @@ -208,24 +220,45 @@ void* bu_invert(void *dst, const void *s |
208 |
220 |
|
209 |
221 |
rstream.reader = something; |
210 |
222 |
|
211 |
process(&lstream, &rstream, |
|
223 |
process(&lstream, &rstream, n, op_not_left, EMIT, &dst); |
|
212 |
224 |
return dst; |
213 |
225 |
} |
214 |
226 |
|
215 |
227 |
/******************************************************************************/ |
216 |
228 |
|
217 |
int bu_memcmp(const void *left, const void *right, size_t len) { |
|
218 |
return !match(left, right, len, op_same, 1); |
|
229 |
int bu_memcmp(const void *left, const void *right, size_t n) { |
|
230 |
return !match(left, right, n, op_same, 1); |
|
219 |
231 |
} |
220 |
232 |
|
221 |
233 |
/******************************************************************************/ |
222 |
234 |
|
223 |
int bu_equal(const void *left, const void *right, size_t len) { |
|
224 |
return match(left, right, len, op_same, 1); |
|
235 |
int bu_equal(const void *left, const void *right, size_t n) { |
|
236 |
return match(left, right, n, op_same, 1); |
|
225 |
237 |
} |
226 |
238 |
|
227 |
239 |
/******************************************************************************/ |
228 |
240 |
|
229 |
int bu_opposite(const void *left, const void *right, size_t len) { |
|
230 |
return match(left, right, len, op_different, 1); |
|
241 |
int bu_opposite(const void *left, const void *right, size_t n) { |
|
242 |
return match(left, right, n, op_different, 1); |
|
231 |
243 |
} |
244 |
||
245 |
/******************************************************************************/ |
|
246 |
||
247 |
int bu_isset(const void *src, int val, size_t n) { |
|
248 |
stream lstream, rstream; |
|
249 |
match_params params, *ptr; |
|
250 |
u08 pat; |
|
251 |
||
252 |
lstream.reader = nthbyte; |
|
253 |
lstream.src = src; |
|
254 |
||
255 |
pat = val; |
|
256 |
rstream.reader = onebyte; |
|
257 |
rstream.src = &pat; |
|
258 |
||
259 |
params.expect = 1; |
|
260 |
ptr = ¶ms; |
|
261 |
||
262 |
process(&lstream, &rstream, n, op_same, MATCH, (void**)&ptr); |
|
263 |
return params.result; |
|
264 |
} |
| … | … | @@ -46,6 +46,9 @@ extern "C" { |
46 |
46 |
|
47 |
47 |
extern int bu_equal(const void *lhs, const void *rhs, size_t n); |
48 |
48 |
extern int bu_opposite(const void *lhs, const void *rhs, size_t n); |
49 |
extern int bu_isset(const void *src, int val, size_t n); |
|
50 |
||
51 |
extern int bu_dbg_flag; |
|
49 |
52 |
|
50 |
53 |
#ifdef __cplusplus |
51 |
54 |
} |
24 |
24 |
int main(int argc, char **argv) { |
25 |
25 |
|
26 |
26 |
u08 dst, src; |
27 |
int dsti, srci; |
|
27 |
28 |
|
28 |
29 |
dst = 1; |
29 |
30 |
bu_bzero(&dst, 1); |
| … | … | @@ -59,6 +60,15 @@ int main(int argc, char **argv) { |
59 |
60 |
assert(0 != bu_memcmp(&src, &dst, 1)); |
60 |
61 |
assert(1 != bu_equal(&src, &dst, 1)); |
61 |
62 |
assert(1 == bu_opposite(&src, &dst, 1)); |
63 |
||
64 |
srci = 0x35; |
|
65 |
dsti = 0; |
|
66 |
bu_memset(&dsti, srci, 4); |
|
67 |
assert(0x35353535 == dsti); |
|
68 |
||
69 |
assert(bu_isset(&dsti, srci, 4)); |
|
70 |
dsti = 0x35000035; |
|
71 |
assert(!bu_isset(&dsti, srci, 4)); |
|
62 |
72 |
|
63 |
73 |
argc = argc; |
64 |
74 |
argv = argv; |