Brainfuck 编程语言

Brainfuck 只有 8 条指令。假设 mp 为内存指针，mv 为 mp 所指内存单元的值，最初两者都为 0

• [：如果 mv == 0，则跳转到相应 ] 指令的下一条指令处；否则，执行下一条指令。
• ]：如果 mv != 0，则跳转到相应 [ 指令的下一条指令处；否则，执行下一条指令。
• +：当前内存单元值加一，即 mv += 1（模 256）。
• -：当前内存单元值减一，即 mv -= 1（模 256）。
• <：内存指针前移，即 mp -= 1
• >：内存指针后移，即 mp += 1
• .：输出当前内存单元值 mv
• ,：从用户输入读取一个字节并将其存储在当前内存单元 mp 中

例如

+[-]++.

• +：内存单元值 mv 加一，得到 mv = 1

• [：因为 mv != 0，所以执行下一条指令 -

• -：内存单元值 mv 加一，得到 mv = 0

• ]：因为 mv == 0，所以执行下一条指令 +

• +：内存单元值 mv 加一，得到 mv = 1

• +：内存单元值 mv 加一，得到 mv = 2

• .：输出当前内存单元值 mv

[+++++]+

• [：因为 mv = 0，所以跳转到相应 ] 的下一条指令 +
• +：内存单元值 mv 加一，得到 mv = 1

将 Brianfuck 程序编译为 Brainfuck 汇编程序

Brainfuck 不是一个指令集架构（ISA），因为指令不是自包含的。它们依赖于上下文，即 [ 和 ] 不包含跳转目标地址。

为了弥补这一缺陷，我们对 [ 和 ] 指令进行修改，让它们后面跟上跳转目标地址。编译器会跟踪一个栈，该栈存储尚未被匹配的 [。用 c 表示一个计数器，表示到目前位置已经执行了多少条指令。

• 当遇到 [ 符号时，a) 将 c 压栈，b) 输出指令 [0，其中 0 是跳转目标地址的占位符

• 当遇到 ] 符号时，a) 出栈，得到 i，b) 将输出序列中位置为 i 的指令 [ 的占位符设置为 i，即改为 [i，c) 输出指令 ]i+1

• 当遇到其它字符时，直接输出该字符，栈中不进行任何修改。

代码如下：

/// Initialize a Brainfuck Program from an appropriate file
pub fn from(code: &str) -> Result<Program> {
    // keeps track of loop beginnings while (potentially nested) loops are being compiled
    let mut loop_stack = vec![];
    let mut instructions = Vec::new();
    for c in code.chars() {
        // to allow skipping a loop and jumping back to the loop's beginning, the respective start and end positions
        // are recorded in the program
        if c == '[' {
            // placeholder for position of loop's end, to be filled in once position is known
            instructions.push(Instruction::decode_from(c, Some(0)));
            loop_stack.push(instructions.len() - 1);
        } else if c == ']' {
            // record loop's end in beginning
            let start_pos = loop_stack.pop().unwrap();
            instructions[start_pos].op_a = instructions.len() as u32;
            // record loop's start
            instructions.push(Instruction::decode_from(c, Some((start_pos + 1) as u32)));
        } else if c != ' ' && c != '\n' && c != '\r' {
            instructions.push(Instruction::decode_from(c, None));
        }
    }
    Ok(Self { instructions })
}

对于输入 [----]，输出为 Program { instructions: [[5, -, -, -, -, ]1] }

Brainfuck 虚拟机

Brainfuck 虚拟机的状态由两种寄存器组成：指令指针 pc 和无限个数据指针 mp ；初始值都为 0。mv 为 mp 中存储的值。

任何虚拟机都定义了一个状态转换函数。运行虚拟机会反复将此函数应用于状态，直到满足终止条件。

在 Brainfuck VM 中，当指令计数器 pc 超出程序长度时终止。

执行一条指令括取指令，执行，指令指针 pc 加一，代码如下：

/// Executes one cycle of the program, returning whether the program has finished.
#[inline]
#[allow(clippy::too_many_lines)]
fn execute_cycle(&mut self) -> Result<bool, ExecutionError> {
    // Fetch the instruction at the current program counter.
    let instruction = self.fetch();

    // Execute the instruction.
    self.execute_instruction(&instruction)?;

    // Increment the clock.
    self.state.global_clk += 1;

    let done = self.state.pc == self.program.instructions.len() as u32;
    Ok(done)
}

用 program[pc] 表示位置 pc 处的指令

状态转换函数如下：

• 如果 program[pc] 为 >，则 mp += 1，pc += 1

• 如果 program[pc] 为 <，则 mp -= 1，pc += 1

• 如果 program[pc] 为 +， 先从 mp 中读出值 mv，然后执行mv += 1，最后将新的 mv 写回 mp 中，pc += 1

• 如果 program[pc] 为 -， 先从 mp 中读出值 mv，然后执行mv -= 1，最后将新的 mv 写回 mp 中，pc += 1

• 如果 program[pc] 为 [dst_pos， 从 mp 中读出值 mv，如果 mv == 0，则进行跳转 pc = dst_pos；否则 pc += 1

• 如果 program[pc] 为 ]start_pos， 从 mp 中读出值 mv，如果 mv != 0，则进行跳转 pc = start_pos；否则 pc += 1

• 如果 program[pc] 为 ,，将输入符号写到 mp，pc += 1

• 如果 program[pc] 为 .，先从 mp 中读出值 mv，然后将 mv 写到输出流，pc += 1

repo：https://github.com/felicityin/zkvm-brainfuck