1mod memory;
2pub use memory::BrainfuckTape;
3
4use std::{fmt, ops::Not};
5
6#[derive(Debug, PartialEq, Clone, Copy)]
7pub enum BfOpKind {
8 InvalidOp,
9 IncPtr,
10 DecPtr,
11 IncData,
12 DecData,
13 ReadStdin,
14 WriteStdout,
15 LoopSetToZero,
16 LoopMovePtr,
17 LoopMoveData,
18 JumpIfDataZero,
19 JumpIfDataNotZero,
20}
21
22impl BfOpKind {
23 fn from_character(instruction: u8) -> BfOpKind {
24 match instruction as char {
25 '>' => BfOpKind::IncPtr,
26 '<' => BfOpKind::DecPtr,
27 '+' => BfOpKind::IncData,
28 '-' => BfOpKind::DecData,
29 ',' => BfOpKind::ReadStdin,
30 '.' => BfOpKind::WriteStdout,
31 '[' => BfOpKind::JumpIfDataZero,
32 ']' => BfOpKind::JumpIfDataNotZero,
33 _ => BfOpKind::InvalidOp,
34 }
35 }
36
37 pub fn to_character(&self) -> char {
38 match self {
39 BfOpKind::IncPtr => '>',
40 BfOpKind::DecPtr => '<',
41 BfOpKind::IncData => '+',
42 BfOpKind::DecData => '-',
43 BfOpKind::ReadStdin => ',',
44 BfOpKind::WriteStdout => '.',
45 BfOpKind::JumpIfDataZero => '[',
46 BfOpKind::JumpIfDataNotZero => ']',
47 _ => '?',
48 }
49 }
50}
51
52impl Not for BfOpKind {
53 type Output = BfOpKind;
54
55 fn not(self) -> Self {
56 match self {
57 BfOpKind::IncData => BfOpKind::DecData,
58 BfOpKind::DecData => BfOpKind::IncData,
59 BfOpKind::DecPtr => BfOpKind::IncPtr,
60 BfOpKind::IncPtr => BfOpKind::DecPtr,
61 kind => kind,
62 }
63 }
64}
65
66pub struct BfOp {
67 kind: BfOpKind,
68 argument: isize,
69}
70
71impl fmt::Debug for BfOp {
72 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
73 f.write_str(format!("{} {:?}", self.argument, self.kind).as_str())
74 }
75}
76
77impl PartialEq for BfOp {
78 fn eq(&self, other: &Self) -> bool {
79 self.kind == other.kind
80 }
81}
82
83impl BfOp {
84 pub fn to_string(&self) -> String {
85 let c = self.kind.to_character();
86
87 match c {
88 '?' | '[' | ']' => String::from(c),
89 other => String::from(other).repeat(self.argument as usize)
90 }
91 }
92}
93
94fn optimize_loop(ops: &Vec<BfOp>, loop_start: isize) -> Vec<BfOp> {
95 let mut new_ops: Vec<BfOp> = Vec::new();
96
97 if ops.len() as isize - loop_start == 2 {
98 let repeated_op = &ops[loop_start as usize + 1];
99 if repeated_op.kind == BfOpKind::IncData || repeated_op.kind == BfOpKind::DecData {
100 new_ops.push(BfOp {
101 kind: BfOpKind::LoopSetToZero,
102 argument: 0,
103 });
104 } else if repeated_op.kind == BfOpKind::IncPtr {
105 new_ops.push(BfOp {
106 kind: BfOpKind::LoopMovePtr,
107 argument: repeated_op.argument,
108 });
109 } else if repeated_op.kind == BfOpKind::DecPtr {
110 new_ops.push(BfOp {
111 kind: BfOpKind::LoopMovePtr,
112 argument: -repeated_op.argument,
113 });
114 } else if ops.len() as isize - loop_start == 5 {
115 if ops[loop_start as usize + 1].kind == BfOpKind::DecData
116 && ops[loop_start as usize + 3].kind == BfOpKind::IncData
117 && ops[loop_start as usize + 1].argument == 1
118 && ops[loop_start as usize + 3].argument == 1
119 {
120 if ops[loop_start as usize + 2].kind == BfOpKind::IncPtr
121 && ops[loop_start as usize + 4].kind == BfOpKind::DecPtr
122 && ops[loop_start as usize + 2].argument
123 == ops[loop_start as usize + 4].argument
124 {
125 new_ops.push(BfOp {
126 kind: BfOpKind::LoopMoveData,
127 argument: ops[loop_start as usize + 2].argument,
128 });
129 } else if ops[loop_start as usize + 2].kind == BfOpKind::DecPtr
130 && ops[loop_start as usize + 4].kind == BfOpKind::IncPtr
131 && ops[loop_start as usize + 2].argument
132 == ops[loop_start as usize + 4].argument
133 {
134 new_ops.push(BfOp {
135 kind: BfOpKind::LoopMoveData,
136 argument: -ops[loop_start as usize + 2].argument,
137 });
138 }
139 }
140 }
141 }
142
143 new_ops
144}
145
146pub fn parse_bytes(code: &Vec<u8>, optimize_loops: bool) -> Vec<BfOp> {
147 let mut ptr = 0;
148 let code_size = code.len();
149 let mut ops = Vec::new();
150 let mut open_bracket_stack: Vec<isize> = Vec::new();
151
152 while ptr < code_size {
153 let instruction = code[ptr];
154 if instruction == '[' as u8 {
155 open_bracket_stack.push(ops.len() as isize);
156 ops.push(BfOp {
157 kind: BfOpKind::JumpIfDataZero,
158 argument: -1,
159 });
160 ptr += 1;
161 } else if instruction == ']' as u8 {
162 if !open_bracket_stack.is_empty() {
163 let open_bracket_offset = open_bracket_stack[open_bracket_stack.len() - 1];
164 open_bracket_stack.pop();
165
166 let mut optimized_loop = if optimize_loops {
167 optimize_loop(&ops, open_bracket_offset)
168 } else {
169 Vec::new()
170 };
171
172 if optimized_loop.is_empty() {
173 ops[open_bracket_offset as usize].argument = ops.len() as isize;
174 ops.push(BfOp {
175 kind: BfOpKind::JumpIfDataNotZero,
176 argument: open_bracket_offset,
177 });
178 } else {
179 let ops_len: usize = ops.len();
180 ops.drain(open_bracket_offset as usize..ops_len);
181 ops.append(&mut optimized_loop);
182 }
183 }
184 ptr += 1;
185 } else {
186 let mut kind = BfOpKind::from_character(instruction);
187 let mut count: isize = 1;
188
189 loop {
190 ptr += 1;
191 if ptr >= code_size {
192 break;
193 }
194
195 let next_kind = BfOpKind::from_character(code[ptr]);
196 if next_kind == BfOpKind::InvalidOp {
197 continue;
198 } else if next_kind == kind {
199 count += 1;
200 } else if next_kind == !kind {
201 count -= 1;
202 } else {
203 break;
204 }
205 }
206
207 if count < 0 {
208 count = count.abs();
209 kind = !kind;
210 }
211 if count > 0 {
212 match kind {
213 BfOpKind::InvalidOp => {}
214 BfOpKind::IncData | BfOpKind::DecData => {
215 ops.push(BfOp {
216 kind: kind,
217 argument: count % 256,
218 });
219 }
220 _ => ops.push(BfOp {
221 kind: kind,
222 argument: count,
223 }),
224 }
225 }
226 }
227 }
228
229 ops
230}
231
232pub fn parse(s: String, optimize_loops: bool) -> Vec<BfOp> {
233 parse_bytes(&s.into_bytes(), optimize_loops)
234}
235
236pub fn execute(
237 ops: &Vec<BfOp>,
238 mut input: impl FnMut() -> u8,
239 mut output: impl FnMut(u8),
240 should_stop: impl Fn(u128) -> bool,
241) -> u128 {
242 let mut ticks: u128 = 0;
243 let mut code_ptr: usize = 0;
244 let mut data = BrainfuckTape::new();
245
246 while code_ptr < ops.len() && !should_stop(ticks) {
247 let op = &ops[code_ptr];
248 let kind = &op.kind;
249
250 match kind {
251 &BfOpKind::IncPtr => data.increase_pointer(op.argument),
252 &BfOpKind::DecPtr => data.decrease_pointer(op.argument),
253 &BfOpKind::IncData => data.increase_cell(op.argument as u8),
254 &BfOpKind::DecData => data.decrease_cell(op.argument as u8),
255 &BfOpKind::ReadStdin => {
256 for _ in 0..op.argument {
257 data.set_cell(input());
258 }
259 }
260 &BfOpKind::WriteStdout => {
261 for _ in 0..op.argument {
262 output(data.get_cell());
263 }
264 }
265 &BfOpKind::LoopSetToZero => data.set_cell(0),
266 &BfOpKind::LoopMovePtr => {
267 while data.get_cell() != 0 {
268 data.move_ptr(op.argument);
269 }
270 }
271 &BfOpKind::LoopMoveData => data.move_data(op.argument),
272 &BfOpKind::JumpIfDataZero => {
273 if data.get_cell() == 0 && op.argument >= 0 {
274 code_ptr = op.argument as usize;
275 }
276 }
277 &BfOpKind::JumpIfDataNotZero => {
278 if data.get_cell() != 0 && op.argument >= 0 {
279 code_ptr = op.argument as usize;
280 }
281 }
282 &BfOpKind::InvalidOp => {}
283 }
284 code_ptr += 1;
285 ticks += 1;
286 }
287
288 ticks
289}