bfc_rs/parser/
cto.rs

1#[cfg(test)]
2mod tests;
3
4use super::BrainfuckInstr;
5
6/// Optimizes a list of Brainfuck instructions to be less repetitive.
7pub fn optimize(code: &mut Vec<BrainfuckInstr>) {
8    optimize_arithmetic(code);
9    // dbg!(&code);
10    /* this helped us while fixing
11    a buggy interaction between the arithmetic and print passes
12    the reason was we didn't push the last instruction
13    to the instruction vector if it wasn't arithmetic 🤷
14    see lines 119-122 */
15    optimize_printing(code);
16}
17
18fn optimize_printing(code: &mut Vec<BrainfuckInstr>) -> () {
19    use BrainfuckInstr::{PointerInc, PutByte, Print};
20    let mut last_op = match code.get(0) {
21        Some(op) => op.clone(),
22        None => return // no instructions to optimize
23    };
24    let mut print_lvl = 0u16;
25    let mut opt = Vec::new();
26    for op in code.iter() {
27        match op {
28            PutByte => {
29                if print_lvl == 0 {
30                    print_lvl += 1;
31                } else {
32                    match last_op {
33                        PointerInc  => print_lvl += 1,
34                        _ => {
35                            opt.push(PutByte);
36                            print_lvl = 1
37                        }
38                    }
39                }
40            },
41            PointerInc => {
42                match last_op {
43                    PutByte => (),
44                    _ => {
45                        opt.push(PointerInc);
46                        print_lvl = 0;
47                    }
48                }
49            }
50            other => {
51                match print_lvl {
52                    0 => {
53                        opt.push(other.clone());
54                        print_lvl = 0;
55                    },
56                    1 => {
57                        opt.push(PutByte);
58                        opt.push(other.clone());
59                        print_lvl = 0;
60                    },
61                    n => {
62                        opt.push(Print(n));
63                        opt.push(other.clone());
64                        print_lvl = 0;
65                    }
66                }
67            }
68        }
69        last_op = op.clone();
70    }
71    match print_lvl {
72        0 => (),
73        1 => {
74            opt.push(PutByte);
75        },
76        n => {
77            opt.push(Print(n));
78        }
79    }
80    *code = opt;
81}
82/// Arithmetic optimization pass.
83fn optimize_arithmetic(code: &mut Vec<BrainfuckInstr>) {
84    use BrainfuckInstr::*;
85    // new, optimized output:
86    let mut opt = Vec::new(); /* Yes, we're cheating to keep the same function signature.
87    We're going to just replace `code` with the new vector.
88    We could optimize things in place, but I tried, believe me, I did. */
89    // How many times the last instruction has been repeated.
90    let mut repeats: u16 = 0;
91    // Instruction last seen.
92    let mut last_op = match code.get(0) {
93        Some(op) => op.clone(),
94        None => return // no instructions to optimize
95    };
96    let last = code.len() - 1;
97    for (index, op) in code.iter().enumerate() {
98        if *op == last_op {
99            repeats += 1;
100        }
101        if *op != last_op || index == last {
102            if repeats > 1 {
103                match last_op {
104                    DataDec | DataInc | PointerDec | PointerInc => {
105                        opt.push(squash_arithmetic(&last_op, repeats));
106                        repeats = 1;
107                    },
108                    _ => {
109                        repeats = 1;
110                    }
111                }
112            } else {
113                opt.push(last_op.clone());
114                repeats = 1;
115            }
116        }
117        last_op = op.clone();
118    }
119    match last_op {
120        DataDec | DataInc | PointerDec | PointerInc => (),
121        _ => opt.push(last_op)   
122    };
123    *code = opt;
124}
125/// "Compress" standard Brainfuck arithmetic operations repeated `x` times into our own virtual ones.
126fn squash_arithmetic(op: &BrainfuckInstr, x: u16) -> BrainfuckInstr {
127    use BrainfuckInstr::*;
128    use std::cmp::min;
129    let max_u16 = std::u16::MAX;
130    match op {
131        PointerDec => PointerSub(min(max_u16, x)),
132        PointerInc => PointerAdd(min(max_u16, x)),
133        DataDec => DataSub(min(255, x) as u8),
134        DataInc => DataAdd(min(255, x) as u8),
135        _ => {
136            panic!("Tried to convert the non-arithmetic instruction {:?} into a virtual arithmetic instruction!", op)
137        }
138    }
139}
bfc_rs/parser/cto.rs

bfc_rs/parser/
cto.rs
