|
996
|
1 /* boof.cpp - Sam Hughes - boof@samuelhughes.com */
|
|
|
2
|
|
|
3
|
|
|
4
|
|
|
5 #include "boof.h"
|
|
|
6
|
|
|
7 #include <stack>
|
|
|
8
|
|
|
9
|
|
|
10 using std::string;
|
|
|
11 using std::istream;
|
|
|
12 using std::ostream;
|
|
|
13 using std::vector;
|
|
|
14 using std::stack;
|
|
|
15 using std::endl;
|
|
|
16 using std::cout;
|
|
|
17 using std::flush;
|
|
|
18
|
|
|
19 /* The "on" bits represent valid ascii characters; other chars are ignored. */
|
|
|
20 static unsigned char valid_bf_flags[] =
|
|
|
21 {0,0,0,0,0,0x18,0,0x58,0,0,0,0x28,0,0,0,0,
|
|
|
22 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
|
|
|
23 // ^^ talk about premature optimization!
|
|
|
24
|
|
|
25 /* The constructor. What else is there to say? */
|
|
|
26 boolpit::boolpit()
|
|
|
27 {
|
|
|
28 beg_ = new unsigned char[30000];
|
|
|
29 end_ = beg_ + 30000;
|
|
|
30 mid_ = beg_;
|
|
|
31
|
|
|
32 while (mid_ != end_) {
|
|
|
33 *mid_++ = 0;
|
|
|
34 }
|
|
|
35
|
|
|
36 mid_ = beg_ + 15000; // some nice magic numbers
|
|
|
37 return;
|
|
|
38 }
|
|
|
39
|
|
|
40 boolpit::boolpit(const boolpit & copyee)
|
|
|
41 {
|
|
|
42 copy(copyee);
|
|
|
43
|
|
|
44 return;
|
|
|
45 }
|
|
|
46
|
|
|
47 boolpit::~boolpit()
|
|
|
48 {
|
|
|
49 delete [] beg_;
|
|
|
50 }
|
|
|
51
|
|
|
52 boolpit &
|
|
|
53 boolpit::operator=(const boolpit & assignee)
|
|
|
54 {
|
|
|
55 delete [] beg_;
|
|
|
56 copy(assignee);
|
|
|
57 }
|
|
|
58
|
|
|
59 void
|
|
|
60 boolpit::copy(const boolpit & copyee)
|
|
|
61 {
|
|
|
62 beg_ = new unsigned char[copyee.end_ - copyee.beg_];
|
|
|
63 end_ = beg_ + (copyee.end_ - copyee.beg_);
|
|
|
64 mid_ = beg_ + (copyee.mid_ - copyee.beg_);
|
|
|
65
|
|
|
66 unsigned char * w = beg_, * c = copyee.beg_;
|
|
|
67
|
|
|
68 while (w != end_) {
|
|
|
69 *w++ = *c++;
|
|
|
70 }
|
|
|
71
|
|
|
72 return;
|
|
|
73 }
|
|
|
74
|
|
|
75 void
|
|
|
76 boolpit::set(size_t offset, int i)
|
|
|
77 {
|
|
|
78 unsigned char setter = (offset & 7);
|
|
|
79 offset += ((mid_ - beg_) << 3);
|
|
|
80 offset >>= 3;
|
|
|
81 unsigned char * p = beg_ + offset;
|
|
|
82
|
|
|
83 if (p < beg_ || end_ <= p) {
|
|
|
84 grow_and_accommodate(p);
|
|
|
85 }
|
|
|
86
|
|
|
87 /* This magical line assigns to the bit. */
|
|
|
88 (*p |= ((i != 0) << setter))
|
|
|
89 &= ~((i == 0) << setter);
|
|
|
90
|
|
|
91 return;
|
|
|
92 }
|
|
|
93
|
|
|
94 int
|
|
|
95 boolpit::get(size_t offset)
|
|
|
96 {
|
|
|
97 unsigned char getter = (1 << (offset & 7));
|
|
|
98 offset += ((mid_ - beg_) << 3);
|
|
|
99 offset >>= 3;
|
|
|
100 unsigned char * p = beg_ + offset;
|
|
|
101
|
|
|
102 if (p < beg_ || end_ <= p) {
|
|
|
103 grow_and_accommodate(p);
|
|
|
104 }
|
|
|
105
|
|
|
106 return (*p & getter) != 0;
|
|
|
107 }
|
|
|
108
|
|
|
109 void
|
|
|
110 boolpit::flip(size_t offset)
|
|
|
111 {
|
|
|
112 unsigned char flipper = (1 << (offset & 7));
|
|
|
113 offset += ((mid_ - beg_) << 3);
|
|
|
114 offset >>= 3;
|
|
|
115 unsigned char * p = beg_ + offset;
|
|
|
116
|
|
|
117 if (p < beg_ || end_ <= p) {
|
|
|
118 grow_and_accommodate(p);
|
|
|
119 }
|
|
|
120
|
|
|
121 *p ^= flipper;
|
|
|
122
|
|
|
123 return;
|
|
|
124 }
|
|
|
125
|
|
|
126
|
|
|
127 void
|
|
|
128 boolpit::grow_and_accommodate(unsigned char * & p)
|
|
|
129 {
|
|
|
130 if (p < beg_) {
|
|
|
131
|
|
|
132 size_t middist = mid_ - p;
|
|
|
133 size_t newdist = (mid_ - beg_) << 1;
|
|
|
134
|
|
|
135 if (newdist < middist) {
|
|
|
136 newdist = middist;
|
|
|
137 }
|
|
|
138
|
|
|
139 size_t totdist = newdist + (end_ - mid_);
|
|
|
140
|
|
|
141 unsigned char * newarr = new unsigned char[totdist];
|
|
|
142 unsigned char * newend = newarr + totdist;
|
|
|
143 unsigned char * w = newend;
|
|
|
144
|
|
|
145 while (end_ != beg_) {
|
|
|
146 *--w = *--end_;
|
|
|
147 }
|
|
|
148
|
|
|
149 delete [] beg_;
|
|
|
150 beg_ = newarr;
|
|
|
151 end_ = newend;
|
|
|
152 mid_ = beg_ + newdist;
|
|
|
153
|
|
|
154 p = mid_ - middist; /* Because p is passed by reference! */
|
|
|
155
|
|
|
156
|
|
|
157 } else if (end_ <= p) {
|
|
|
158
|
|
|
159 size_t middist = p - mid_;
|
|
|
160 size_t newdist = (end_ - mid_) << 1;
|
|
|
161
|
|
|
162 if (newdist < middist) {
|
|
|
163 newdist = middist;
|
|
|
164 }
|
|
|
165
|
|
|
166 size_t totdist = newdist + (mid_ - beg_);
|
|
|
167
|
|
|
168 unsigned char * newarr = new unsigned char[totdist];
|
|
|
169 unsigned char * newend = newarr + totdist;
|
|
|
170 unsigned char * w = newarr;
|
|
|
171
|
|
|
172 mid_ = beg_;
|
|
|
173 while (mid_ != end_) {
|
|
|
174 *w++ = *mid_++;
|
|
|
175 }
|
|
|
176
|
|
|
177 delete [] beg_;
|
|
|
178 beg_ = newarr;
|
|
|
179 end_ = newend;
|
|
|
180 mid_ = end_ - newdist;
|
|
|
181
|
|
|
182 p = mid_ + middist;
|
|
|
183 }
|
|
|
184
|
|
|
185 return;
|
|
|
186 }
|
|
|
187
|
|
|
188
|
|
|
189 boofer::boofer(istream & istr)
|
|
|
190 {
|
|
|
191 unsigned char x;
|
|
|
192 size_t counter;
|
|
|
193 stack<size_t> bracket_pos;
|
|
|
194
|
|
|
195
|
|
|
196
|
|
|
197 while (!istr.eof()) {
|
|
|
198 x = istr.get();
|
|
|
199 if (valid_bf_flags[x >> 3] | (1 << (x & 7))) {
|
|
|
200 prog_.push_back(x);
|
|
|
201
|
|
|
202 if (x == '[') {
|
|
|
203 bracket_pos.push(brace_pos_.size());
|
|
|
204 brace_pos_.push_back(size_triad(counter, 0, 0));
|
|
|
205 } else if (x == ']') {
|
|
|
206 if (bracket_pos.empty()) {
|
|
|
207 brace_pos_.clear();
|
|
|
208 prog_.clear();
|
|
|
209
|
|
|
210 return;
|
|
|
211 }
|
|
|
212
|
|
|
213 brace_pos_[bracket_pos.top()].rjump =
|
|
|
214 counter -
|
|
|
215 brace_pos_[bracket_pos.top()].lpos;
|
|
|
216
|
|
|
217 brace_pos_[bracket_pos.top()].bjump =
|
|
|
218 brace_pos_.size() - bracket_pos.top();
|
|
|
219
|
|
|
220
|
|
|
221 bracket_pos.pop();
|
|
|
222 }
|
|
|
223 ++counter;
|
|
|
224 }
|
|
|
225 }
|
|
|
226
|
|
|
227 if (! bracket_pos.empty()) {
|
|
|
228 brace_pos_.clear();
|
|
|
229 prog_.clear();
|
|
|
230 return;
|
|
|
231 }
|
|
|
232
|
|
|
233 return;
|
|
|
234 }
|
|
|
235
|
|
|
236 void debug_char(char p) {
|
|
|
237 //cout << p << endl;
|
|
|
238 }
|
|
|
239
|
|
|
240
|
|
|
241 void
|
|
|
242 boofer::execute(std::istream & in, std::ostream & out) const
|
|
|
243 {
|
|
|
244
|
|
|
245 //out << "Considering fk size " << prog_.size() << endl;
|
|
|
246 string::const_iterator p = prog_.begin();
|
|
|
247 string::const_iterator end = prog_.end();
|
|
|
248
|
|
|
249 char ibuff = 0;
|
|
|
250 unsigned char obuff = 0, ibuff_size = 0, obuff_size = 0;
|
|
|
251
|
|
|
252 vector<size_triad>::const_iterator next_brace = brace_pos_.begin();
|
|
|
253 stack<vector<size_triad>::const_iterator> loop_stack;
|
|
|
254
|
|
|
255 boolpit pit;
|
|
|
256 size_t point = 0;
|
|
|
257
|
|
|
258 bool moreinput = true;
|
|
|
259
|
|
|
260 while (p != end) {
|
|
|
261 debug_char(*p);
|
|
|
262 switch (*p) {
|
|
|
263 case ',':
|
|
|
264 {
|
|
|
265 if (! ibuff_size) {
|
|
|
266
|
|
|
267 if (moreinput) {
|
|
|
268 if (!in.get(ibuff)) {
|
|
|
269 //cout << "EOF!" << endl;
|
|
|
270 moreinput = false;
|
|
|
271 }
|
|
|
272 }
|
|
|
273 ibuff *= moreinput;
|
|
|
274 ibuff_size = 8;
|
|
|
275 }
|
|
|
276
|
|
|
277 pit.set(point, ibuff & 1);
|
|
|
278
|
|
|
279 ibuff >>= 1;
|
|
|
280 --ibuff_size;
|
|
|
281 }
|
|
|
282 break;
|
|
|
283 case ';':
|
|
|
284 {
|
|
|
285 obuff |= (pit.get(point) << obuff_size);
|
|
|
286 ++obuff_size;
|
|
|
287
|
|
|
288 if (obuff_size == 8) {
|
|
|
289 out.put(obuff);
|
|
|
290
|
|
|
291 obuff_size = 0;
|
|
|
292 obuff = 0;
|
|
|
293 }
|
|
|
294
|
|
|
295 }
|
|
|
296 break;
|
|
|
297 case '<':
|
|
|
298 {
|
|
|
299 --point;
|
|
|
300 }
|
|
|
301 break;
|
|
|
302 case '>':
|
|
|
303 {
|
|
|
304 ++point;
|
|
|
305 }
|
|
|
306 break;
|
|
|
307 case '+':
|
|
|
308 {
|
|
|
309 pit.flip(point);
|
|
|
310 }
|
|
|
311 break;
|
|
|
312 case '[':
|
|
|
313 {
|
|
|
314 if (pit.get(point)) {
|
|
|
315 loop_stack.push(next_brace);
|
|
|
316 ++next_brace;
|
|
|
317 } else {
|
|
|
318 p += next_brace->rjump;
|
|
|
319 next_brace += next_brace->bjump;
|
|
|
320 }
|
|
|
321 }
|
|
|
322 break;
|
|
|
323 case ']':
|
|
|
324 {
|
|
|
325 next_brace = loop_stack.top();
|
|
|
326 p -= next_brace->rjump + 1;
|
|
|
327 loop_stack.pop();
|
|
|
328 }
|
|
|
329 break;
|
|
|
330 default:
|
|
|
331 break;
|
|
|
332 }
|
|
|
333
|
|
|
334 ++p;
|
|
|
335 }
|
|
|
336 if (obuff_size != 8) {
|
|
|
337 out.put(obuff);
|
|
|
338 }
|
|
|
339 out.flush();
|
|
|
340
|
|
|
341 return;
|
|
|
342 }
|
