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.

Clone this repository (size: 30.4 KB): HTTPS / SSH
$ hg clone http://bitbucket.org/seths/bitunwise/
commit 3: fcdebccc9f5a
parent 2: a1d466277f4a
branch: default
add support for memset. Also make it very clear that uninitialized memory is being read *intentionally*
Seth Schroeder
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)

Up to file-list Makefile:

1
1
SRCS=$(wildcard *.c)
2
2
OBJS=$(SRCS:.c=.o)
3
CFLAGS=-Wall -g -Wextra
3
CFLAGS=-Wall -g
4
4
5
5
.PHONY: run
6
6
run: a.out

Up to file-list bitunwise.c:

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
        struct match_params *match;
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
        struct match_params params, *ptr;
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
        return write(dst, NULL, NULL, len, op_never);
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
        return write(dst, NULL, NULL, len, op_always);
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
        return write(dst, src, NULL, len, op_left);
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
        return write(dst, src, NULL, len, op_not_left);
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
/******************************************************************************/

Up to file-list bitunwise.h:

@@ -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
  //  extern void* bu_memset(void *dst, int val, size_t n);
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 len);
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
}