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 3: | fcdebccc9f5a |
| parent 2: | a1d466277f4a |
| branch: | default |
add support for memset. Also make it very clear that uninitialized memory is being read *intentionally*
15 months ago
Changed (Δ1.4 KB):
raw changeset »
Makefile (1 lines added, 1 lines removed)
bitunwise.c (85 lines added, 24 lines removed)
bitunwise.h (6 lines added, 6 lines removed)
1 |
1 |
SRCS=$(wildcard *.c) |
2 |
2 |
OBJS=$(SRCS:.c=.o) |
3 |
CFLAGS=-Wall -g |
|
3 |
CFLAGS=-Wall -g |
|
4 |
4 |
|
5 |
5 |
.PHONY: run |
6 |
6 |
run: a.out |
41 |
41 |
#define EMIT 0 |
42 |
42 |
#define MATCH 1 |
43 |
43 |
|
44 |
struct match_params { |
|
45 |
int result; |
|
46 |
int expect; |
|
47 |
}; |
|
44 |
/******************************************************************************/ |
|
45 |
||
46 |
typedef u08(*bytegetter)(const void *src, size_t byte); |
|
47 |
||
48 |
u08 something(const void *src, size_t byte) { |
|
49 |
u08 random_byte_on_the_stack; |
|
50 |
return random_byte_on_the_stack; |
|
51 |
} |
|
52 |
||
53 |
u08 onebyte(const void *src, size_t byte) { |
|
54 |
return *(const u08*)src; |
|
55 |
} |
|
56 |
||
57 |
u08 nthbyte(const void *src, size_t byte) { |
|
58 |
return ((const u08*)src)[byte]; |
|
59 |
} |
|
48 |
60 |
|
49 |
61 |
/******************************************************************************/ |
50 |
62 |
|
51 |
void process(const void *left, const void *right, size_t len, |
|
63 |
typedef struct stream { |
|
64 |
bytegetter reader; |
|
65 |
const void *src; |
|
66 |
} stream; |
|
67 |
||
68 |
typedef struct match_params { |
|
69 |
int result; |
|
70 |
int expect; |
|
71 |
} match_params; |
|
72 |
||
73 |
/******************************************************************************/ |
|
74 |
||
75 |
void process(const stream *left, const stream *right, size_t len, |
|
52 |
76 |
int op, int type, void **rc) { |
53 |
77 |
|
54 |
78 |
size_t i, j; |
55 |
79 |
void *dst; |
56 |
|
|
80 |
match_params *match; |
|
57 |
81 |
|
58 |
82 |
if (type == EMIT) |
59 |
83 |
dst = *rc; |
| … | … | @@ -63,10 +87,8 @@ void process(const void *left, const voi |
63 |
87 |
for (i = 0; i < len; i++) { |
64 |
88 |
unsigned char lc, rc, dc; |
65 |
89 |
|
66 |
if (left) |
|
67 |
lc = ((const u08*)left)[i]; |
|
68 |
if (right) |
|
69 |
rc = ((const u08*)right)[i]; |
|
90 |
lc = left->reader(left->src, i); |
|
91 |
rc = right->reader(right->src, i); |
|
70 |
92 |
|
71 |
93 |
for (j = 0; j < 8; j++) { |
72 |
94 |
const int flag = 1 << j; |
| … | … | @@ -108,20 +130,18 @@ void process(const void *left, const voi |
108 |
130 |
|
109 |
131 |
/******************************************************************************/ |
110 |
132 |
|
111 |
void* write(void *dst, const void *left, const void *right, size_t len, int op) { |
|
112 |
process(left, right, len, op, EMIT, &dst); |
|
113 |
return dst; |
|
114 |
} |
|
115 |
||
116 |
||
117 |
/******************************************************************************/ |
|
118 |
||
119 |
133 |
int match(const void *left, const void *right, size_t len, int op, int expect) { |
120 |
|
|
134 |
match_params params, *ptr; |
|
135 |
stream lstream, rstream; |
|
121 |
136 |
|
122 |
137 |
params.expect = expect; |
123 |
138 |
ptr = ¶ms; |
124 |
process(left, right, len, op, MATCH, (void**)&ptr); |
|
139 |
||
140 |
lstream.reader = rstream.reader = nthbyte; |
|
141 |
lstream.src = left; |
|
142 |
rstream.src = right; |
|
143 |
||
144 |
process(&lstream, &rstream, len, op, MATCH, (void**)&ptr); |
|
125 |
145 |
|
126 |
146 |
return params.result; |
127 |
147 |
} |
| … | … | @@ -130,25 +150,66 @@ int match(const void *left, const void * |
130 |
150 |
/* Begin implementation of external functions */ |
131 |
151 |
|
132 |
152 |
void* bu_bzero(void *dst, size_t len) { |
133 |
|
|
153 |
stream lstream, rstream; |
|
154 |
||
155 |
lstream.reader = rstream.reader = something; |
|
156 |
||
157 |
process(&lstream, &rstream, len, op_never, EMIT, &dst); |
|
158 |
return dst; |
|
134 |
159 |
} |
135 |
160 |
|
136 |
161 |
/******************************************************************************/ |
137 |
162 |
|
138 |
163 |
void* bu_fill(void *dst, size_t len) { |
139 |
|
|
164 |
stream lstream, rstream; |
|
165 |
||
166 |
lstream.reader = rstream.reader = something; |
|
167 |
||
168 |
process(&lstream, &rstream, len, op_always, EMIT, &dst); |
|
169 |
return dst; |
|
140 |
170 |
} |
141 |
171 |
|
142 |
172 |
/******************************************************************************/ |
143 |
173 |
|
144 |
174 |
void* bu_memcpy(void *dst, const void *src, size_t len) { |
145 |
|
|
175 |
stream lstream, rstream; |
|
176 |
||
177 |
lstream.reader = nthbyte; |
|
178 |
rstream.reader = something; |
|
179 |
lstream.src = src; |
|
180 |
||
181 |
process(&lstream, &rstream, len, op_left, EMIT, &dst); |
|
182 |
return dst; |
|
183 |
} |
|
184 |
||
185 |
/******************************************************************************/ |
|
186 |
||
187 |
void *bu_memset(void *dst, int val, size_t len) { |
|
188 |
stream lstream, rstream; |
|
189 |
u08 src; |
|
190 |
||
191 |
src = val; |
|
192 |
lstream.reader = onebyte; |
|
193 |
lstream.src = &src; |
|
194 |
||
195 |
rstream.reader = something; |
|
196 |
||
197 |
process(&lstream, &rstream, len, op_left, EMIT, &dst); |
|
198 |
return dst; |
|
146 |
199 |
} |
147 |
200 |
|
148 |
201 |
/******************************************************************************/ |
149 |
202 |
|
150 |
203 |
void* bu_invert(void *dst, const void *src, size_t len) { |
151 |
|
|
204 |
stream lstream, rstream; |
|
205 |
||
206 |
lstream.reader = nthbyte; |
|
207 |
lstream.src = src; |
|
208 |
||
209 |
rstream.reader = something; |
|
210 |
||
211 |
process(&lstream, &rstream, len, op_not_left, EMIT, &dst); |
|
212 |
return dst; |
|
152 |
213 |
} |
153 |
214 |
|
154 |
215 |
/******************************************************************************/ |
| … | … | @@ -36,16 +36,16 @@ extern "C" { |
36 |
36 |
typedef unsigned char u08; |
37 |
37 |
|
38 |
38 |
extern void* bu_memcpy(void *dst, const void *src, size_t n); |
39 |
|
|
39 |
extern void* bu_memset(void *dst, int val, size_t n); |
|
40 |
40 |
extern void* bu_bzero(void *dst, size_t n); |
41 |
41 |
|
42 |
extern int bu_memcmp(const void *lhs, const void *rhs, size_t |
|
42 |
extern int bu_memcmp(const void *lhs, const void *rhs, size_t n); |
|
43 |
43 |
|
44 |
extern void* bu_fill(void *dst, size_t len); |
|
45 |
extern void* bu_invert(void *dst, const void *src, size_t len); |
|
44 |
extern void* bu_fill(void *dst, size_t n); |
|
45 |
extern void* bu_invert(void *dst, const void *src, size_t n); |
|
46 |
46 |
|
47 |
extern int bu_equal(const void *lhs, const void *rhs, size_t len); |
|
48 |
extern int bu_opposite(const void *lhs, const void *rhs, size_t len); |
|
47 |
extern int bu_equal(const void *lhs, const void *rhs, size_t n); |
|
48 |
extern int bu_opposite(const void *lhs, const void *rhs, size_t n); |
|
49 |
49 |
|
50 |
50 |
#ifdef __cplusplus |
51 |
51 |
} |
