Introduction

我们从brainfsck 解释器开始我们的教程:

#include <stdio.h>
#include <stdlib.h>

#define TAPE_SIZE 30000
#define MAX_NESTING 100

typedef struct bf_state
{
  unsigned char* tape;
  unsigned char (*get_ch)(struct bf_state*);
  void (*put_ch)(struct bf_state*, unsigned char);
} bf_state_t;

#define bad_program(s) exit(fprintf(stderr, "bad program near %.16s: %s\n", program, s))

static void bf_interpret(const char* program, bf_state_t* state)
{
  const char* loops[MAX_NESTING];
  int nloops = 0;
  int n;
  int nskip = 0;
  unsigned char* tape_begin = state->tape - 1;
  unsigned char* ptr = state->tape;
  unsigned char* tape_end = state->tape + TAPE_SIZE - 1;
  for(;;) {
    switch(*program++) {
    case '<':
      for(n = 1; *program == '<'; ++n, ++program);
      if(!nskip) {
        ptr -= n;
        while(ptr <= tape_begin)
          ptr += TAPE_SIZE;
      }
      break;
    case '>':
      for(n = 1; *program == '>'; ++n, ++program);
      if(!nskip) {
        ptr += n;
        while(ptr > tape_end)
          ptr -= TAPE_SIZE;
      }
      break;
    case '+':
      for(n = 1; *program == '+'; ++n, ++program);
      if(!nskip)
        *ptr += n;
      break;
    case '-':
      for(n = 1; *program == '-'; ++n, ++program);
      if(!nskip)
        *ptr -= n;
      break;
    case ',':
      if(!nskip)
        *ptr = state->get_ch(state);
      break;
    case '.':
      if(!nskip)
        state->put_ch(state, *ptr);
      break;
    case '[':
      if(nloops == MAX_NESTING)
        bad_program("Nesting too deep");
      loops[nloops++] = program;
      if(!*ptr)
        ++nskip;
      break;
    case ']':
      if(nloops == 0)
        bad_program("] without matching [");
      if(*ptr)
        program = loops[nloops-1];
      else
        --nloops;
      if(nskip)
        --nskip;
      break;
    case 0:
      if(nloops != 0)
        program = "<EOF>", bad_program("[ without matching ]");
      return;
    }
  }
}

static void bf_putchar(bf_state_t* s, unsigned char c)
{
  putchar((int)c);
}

static unsigned char bf_getchar(bf_state_t* s)
{
  return (unsigned char)getchar();
}

static void bf_run(const char* program)
{
  bf_state_t state;
  unsigned char tape[TAPE_SIZE] = {0};
  state.tape = tape;
  state.get_ch = bf_getchar;
  state.put_ch = bf_putchar;
  bf_interpret(program, &state);
}

int main(int argc, char** argv)
{
  if(argc == 2) {
    long sz;
    char* program;
    FILE* f = fopen(argv[1], "r");
    if(!f) {
      fprintf(stderr, "Cannot open %s\n", argv[1]);
      return 1;
    }
    fseek(f, 0, SEEK_END);
    sz = ftell(f);
    program = (char*)malloc(sz + 1);
    fseek(f, 0, SEEK_SET);
    program[fread(program, 1, sz, f)] = 0;
    fclose(f);
    bf_run(program);
    return 0;
  } else {
    fprintf(stderr, "Usage: %s INFILE.bf\n", argv[0]);
    return 1;
  }
}

我们在这个教程里, 用 DynASM 将这个 brainfuck 解释器编写成 brainfuck JIT 编译器. 来看看是否会提升运行速度.

首先, clone 这个 repo, 然后从bf_c.c开始:

git clone https://github.com/corsix/dynasm-doc.git
cd dynasm-doc
git submodule update --init
cp bf_c.c tutorial.c

我们通过运行这个程序来演示功能, 这个程序会缓慢的渲染曼德博集合(Mandelbrot set):

gcc -o tutorial tutorial.c
./tutorial mandelbrot.bf

(译者我的CPU是 Intel(R) Xeon(R) CPU E5-2680 v2 @ 2.80GHz, 最高 3.5GHz, 下面是输出结果, 渲染需要35.4s)

[root@m01 dynasm-doc]# time ./tutorial mandelbrot.bf
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDEGFFEEEEDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
A                                                                                                 PLJHGGFFEEEDDDDDDDCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB

real	0m35.466s
user	0m35.462s
sys	0m0.002s

---

Groundwork

好戏上演之前, 我们先要做一些基础工作.

---

Includes

首先, 我们需要 #include DynASM 的头文件:

#include "luajit-2.0/dynasm/dasm_proto.h"
#include "luajit-2.0/dynasm/dasm_x86.h"

正如参考文档中写的, dasm_proto.h 定义 DynASM API, dasm_x86.h 则包含了上述 API 的实现 (x86/ x64).

---

Types

接下来, 我们将 bf_interpret 重命名为 bf_compile, 并更改它的类型定义:

static void bf_interpret(const char* program, bf_state_t* state)
static void(* bf_compile(const char* program) )(bf_state_t*)

修改前 bf_interpret 可以接受参数 const char* 和 bf_state_t*, 修改后的 bf_compile 只接受参数 const char* 部分, 并且返回 JIT 编译后的代码的函数指针.

bf_interpret 函数也需要修改:

bf_interpret(program, &state);
bf_compile(program)(&state);

---

Initialisation

搞定基础工作后, 下一步就是创建和初始化一个 DynASM state.

---

Variables

我们需要一个类型为 dasm_State* 的变量包含 DynASM state, 还需要两个其他的我们一会再解释. 并且还需要移除一个解释器变量:

int nskip = 0;
dasm_State* d;
unsigned npc = 8;
unsigned nextpc = 0;

---

.arch

现在我们将第一次接触 DynASM 指令, 这个是 DynASM 预处理器指令. 在这里我们定义生成目标机器码的平台架构, x86 或 x64:

|.if X64
|.arch x64
|.else
|.arch x86
|.endif

开头的竖线会被 DynASM 预处理器识别. .if, .else, 和 .endif 指令会被 DynASM 的预处理器处理, 处理方式与 C 语言预处理中的 #if, #else, 和 #endif. 相似, 执行结果就是只有一个 .arch 指令会生效.

---

dasm_init

我们定义了 dasm_State*, 现在我们要分配内存空间把它装进去. 调用 dasm_init即可:

|.section code
dasm_init(&d, DASM_MAXSECTION);

注意跟 dasm_State** 一样, dasm_init 需要一个 integer 参数, 定义生成的机器码的 section. 我们只需要一个 code section, 所以我们传入一个参数给 .section , 这样 DynASM 预处理器就会处理成 #define DASM_MAXSECTION 1 (amongst other things). 也许给 dasm_init 传 DASM_MAXSECTION 没有直接传 1 那么直观, 但是这是个好的实践, 因为说不定将来我们就会需要更多的 section.

---

dasm_setupglobal

dasm_init 将会分配 dasm_State, 但这并不是完全的初始化. 想要初始化 state 我们还需要调用几个函数. 第一个就是 dasm_setupglobal:

|.globals lbl_
void* labels[lbl__MAX];
dasm_setupglobal(&d, labels, lbl__MAX);

带者参数 lbl_ 的 .globals 指令会被 DynASM 预处理为一个包含一些结构的 enum 类型, 其中一个是 lbl__MAX. 这个值必须与相同长度的 void* 数组传入到 dasm_setupglobal, 后续我们将使用 labels 数组.

---

dasm_setup

接下来在初始化过程调用的是 dasm_setup:

|.actionlist bf_actions
dasm_setup(&d, bf_actions);

带 bf_actions 参数的 .actionlist 指令会被 DynASM 预处理器重写为 bf_actions 变量, 并且需要传入到 dasm_setup.

---

dasm_growpc

正常情况下 dasm_State 在这个节点已经完全初始化. 不过由于我们还要用动态 labels, 所以还要调用 dasm_growpc 再初始化一下:

dasm_growpc(&d, npc);

我们传入了之前定义的 npc 参数, 这个参数代表动态 lable 的数量. 还有个依赖的变量叫 nextpc 是用来记录我们使用的 lable 的数量的. 这些动态 lable 将在我们编译 [ 和 ] 时起作用.

---

Abstractions

在我们执行机器码之前, 先定义一些抽象(abstraction), 先定义一些让寄存器更具有意义的抽象概念:

Abstraction	Corresponding Interpreter Variable	Definition
aState	state	ebx or rbx
aPtr	ptr	ebp or r12
aTapeBegin	tape_begin	esi or rsi or r13
aTapeEnd	tape_end	edi or rdi or r14

接下来再定义一些函数调用:

Abstraction	Description
prologue	Set up the stack frame, and set aState from the passed parameter.
prepcall1 arg1	Prepare to call a function with one argument, arg1.
prepcall2 arg1, arg2	Prepare to call a function with two arguments, arg1 and arg2.
postcall n	Do cleanup after a call to a function with n arguments.
epilogue	Tear down the stack frame.

这些定义都是通过 .define (通常情况下) 或 .macro (更复杂情况下), 并且 x86, x64 POSIX, x64 Windows 下的定义也有所不同:

|.if X64
  |.define aPtr, rbx
  |.define aState, r12
  |.if WIN
    |.define aTapeBegin, rsi
    |.define aTapeEnd, rdi
    |.define rArg1, rcx
    |.define rArg2, rdx
  |.else
    |.define aTapeBegin, r13
    |.define aTapeEnd, r14
    |.define rArg1, rdi
    |.define rArg2, rsi
  |.endif
  |.macro prepcall1, arg1
    | mov rArg1, arg1
  |.endmacro
  |.macro prepcall2, arg1, arg2
    | mov rArg1, arg1
    | mov rArg2, arg2
  |.endmacro
  |.define postcall, .nop
  |.macro prologue
    | push aPtr
    | push aState
    | push aTapeBegin
    | push aTapeEnd
    | push rax
    | mov aState, rArg1
  |.endmacro
  |.macro epilogue
    | pop rax
    | pop aTapeEnd
    | pop aTapeBegin
    | pop aState
    | pop aPtr
    | ret
  |.endmacro
|.else
  |.define aPtr, ebx
  |.define aState, ebp
  |.define aTapeBegin, esi
  |.define aTapeEnd, edi
  |.macro prepcall1, arg1
    | push arg1
  |.endmacro
  |.macro prepcall2, arg1, arg2
    | push arg2
    | push arg1
  |.endmacro
  |.macro postcall, n
    | add esp, 4*n
  |.endmacro
  |.macro prologue
    | push aPtr
    | push aState
    | push aTapeBegin
    | push aTapeEnd
    | mov aState, [esp+20]
  |.endmacro
  |.macro epilogue
    | pop aTapeEnd
    | pop aTapeBegin
    | pop aState
    | pop aPtr
    | ret 4
  |.endmacro
|.endif

为 DynASM 定义了所有这些体系结构和系统有关的定义之后, 还需要检查这些为 DynASM 指定的体系结构和系统是否与 C 预处理器已知的这些是否相匹配:

||#if ((defined(_M_X64) || defined(__amd64__)) != X64) || (defined(_WIN32) != WIN)
#error "Wrong DynASM flags used: pass `-D X64` and/or `-D WIN` to dynasm.lua as appropriate"
#endif

这些以两条竖线开头的将由 DynASM 预处理器替换为 .define (同样如果有的话也可以替换为 .macro), 但其他的不会被 DynASM 预处理器更改. 在特定情况下, 如果 X64 和/或 WIN 在 DynASM 预处理时被定义 (这里为 1) 那么就会被替换成 1.如果在 DynASM 预处理时没有被定义, 那就会保持原样, 并由 C 预处理器替换为 0 .

---

Emitting Code

完成所有这些操作之后，我们终于可以执行一些机器码了.

---

Prologue

我们首先要执行的是一些初始化代码, 这些代码替换了一部分之前的解释器的代码:

unsigned char* tape_begin = state->tape - 1;
unsigned char* ptr = state->tape;
unsigned char* tape_end = state->tape + TAPE_SIZE - 1;
|.type state, bf_state_t, aState

dasm_State** Dst = &d;
|.code
|->bf_main:
| prologue
| mov aPtr, state->tape
| lea aTapeBegin, [aPtr-1]
| lea aTapeEnd, [aPtr+TAPE_SIZE-1]

我们首先看 .type 指令, 这个指令可以让我们用 state->tape 作为速记符来表达 [aState + offsetof(bf_state_t,tape)].

接下来这一行定义了 Dst, 并且用 &d 初始化. 这样做是因为DynASM预处理器将把后续行重写为 dasm_put(Dst, ...)形式的调用, 并且跟我们之前处理那些 dasm_ 函数一样, 第一个参数需要是 &d.

接下来是包含 .code 这一行. 这里指代的指令由先前的 .section code 指令引入, 并且执行的 states 需要放到 code section (这也正好是我们在处理的部分).

再之后我们定义了 ->bf_main. 当我们执行完机器码后, 就可以获取这个 global lable 的地址, 并且转换为函数指针.

然后, 我们调用前面定义的 prologue 宏, 执行那些指令.

最后这几行是 mov 和 lea 指令, 对应删掉的那几行解释器的代码. 像刚才说的那样, state->tape 变成操作数 mov 最终执行的是 [aState + offsetof(bf_state_t,tape)]. 注意 offsetof(bf_state_t,tape) 和 TAPE_SIZE-1 (lea 操作数的一部分) 是所谓的编码时常量: DynASM 并不知道这是什么, 所以到 C 编译器中才会计算. 这两个值都是 C 语言中的编译时常量, 编码时常量不必是编译时常量 (稍后有例子解释).

---

Tape Movement

现在进入解释器阶段, 首要任务是将解释 < 部分的代码替换掉:

if(!nskip) {
  ptr -= n;
  while(ptr <= tape_begin)
    ptr += TAPE_SIZE;
}
| sub aPtr, n%TAPE_SIZE
| cmp aPtr, aTapeBegin
| ja >1
| add aPtr, TAPE_SIZE
|1:

注意，编译器没有像解释器那样跳过代码的概念, 所以把上面的 if 部分完全删除了. ptr -= n; 和下面的循环都变成了 | sub aPtr, n%TAPE_SIZE. Note that n%TAPE_SIZE 则是一个 编码阶段常量, 不是一个C编译阶段常量:DynASM 也不理解操作数的意义. 但是在这种情况下，当 bf_compile 最终运行时会计算操作数的最终值.

编译时当循环过 %TAPE_SIZE, 定义的周期后, 在运行时可能仍然需要执行一次迭代, 这是因为还有 cmp, ja, 和 add 指令. 注意语句 >1 跳转到定义 lable 1 的位置, 即 add 的下一行.

> 操作符也一样, 只不过是 add 和 sub 这部分倒过来:

if(!nskip) {
  ptr += n;
  while(ptr > tape_end)
    ptr -= TAPE_SIZE;
}
| add aPtr, n%TAPE_SIZE
| cmp aPtr, aTapeEnd
| jbe >1
| sub aPtr, TAPE_SIZE
|1:

---

Arithmetic

接下来要改写的指令是 +, 相对简单:

if(!nskip)
  *ptr += n;
| add byte [aPtr], n

值得注意的只有内存操作符 [aPtr] 前面的内存大小描述符 byte. 因为内存操作数和立即操作数都不具有真实的操作数大小, 所以需要明确告知 DynASM. 请注意，我们先前使用的内存操作数不需要内存大小说明符: lea 指令并不需要, 内存操作数并不是内存访问. 并且 mov aPtr, state->tape 也不需要, 因为可以根据寄存器操作数的大小推断出内存操作数的大小. 他们是相等的.

- 指令也一样:

if(!nskip)
  *ptr -= n;
| sub byte [aPtr], n

---

I/O

接下来是 , (read char) 和 . (write char), 值得注意的是它们需要调用其他函数. 首先是 ,:

if(!nskip)
  *ptr = state->get_ch(state);
| prepcall1 aState
| call aword state->get_ch
| postcall 1
| mov byte [aPtr], al

注意调用的抽象定义 prepcall1 和 postcall 我们之前定义过了. 同时也要注意 state->get_ch 是 [aState + offsetof(bf_state_t,get_ch)] 的速记表述, 之前介绍 .type 的时候我们说过了. 并且使用这些速记符号的时候仍然需要内存大小说明符. 内存操作数的大小不会自动推断为同等大小的 C 语言同名结构体成员. aword (address-sized word) 说明符指的是 4 字节 x86 或 8 字节 x64.

. 的转换也一样:

if(!nskip)
  state->put_ch(state, *ptr);
| movzx r0, byte [aPtr]
| prepcall2 aState, r0
| call aword state->put_ch
| postcall 2

注意 r0 用作寄存器操作数: 指的是 eax x86 或 rax x64.

---

Loops

现在轮到了最有趣的指令: [ 和 ]. 其中 [ 相当复杂:

loops[nloops++] = program;
if(!*ptr)
  ++nskip;
if(program[0] == '-' && program[1] == ']') {
  program += 2;
  | xor eax, eax
  | mov byte [aPtr], al
} else {
  if(nextpc == npc) {
    npc *= 2;
    dasm_growpc(&d, npc);
  }
  | cmp byte [aPtr], 0
  | jz =>nextpc+1
  |=>nextpc:
  loops[nloops++] = nextpc;
  nextpc += 2;
}

首先, 我们识别指令 [-] 并为其生成优化后的机器码. 但要排除特殊情况, 一般情况下需要两个动态标签: 一个需要从 [ 跳到 ] 的后面 (之前是通过解释器中的 nskip 实现的), 另一个是从 ] 跳到 [ 的后面 (之前是通过 loops 的栈实现的).

如果我们已经用了我们分配的数量的动态 lable, 还可以调用 dasm_growpc 继续分配.然后我们发出 cmp 指令, 它的作用正如其字面意义. 如果 [aPtr] 中的 byte 是 0, 我们跳到动态 =>nextpc+1 (我们在稍后的 ] 操作符的逻辑中定义). 然后, 我们定义动态 label =>nextpc (] 需要跳回的地方). 注意 nextpc+1 和 nextpc 是编码时常量.

然后是 ]:

if(*ptr)
  program = loops[nloops-1];
else
  --nloops;
if(nskip)
  --nskip;
--nloops;
| cmp byte [aPtr], 0
| jnz =>loops[nloops]
|=>loops[nloops]+1:

注意条件跳转到动态 label =>loops[nloops] (相应的在 [ 的定义是跳转到 =>nextpc), 然后动态 label =>loops[nloops]+1 (相应的在 [ 中的定义是跳转到 jz =>nextpc+1).

---

Epilogue

涵盖了所有指令之后，剩下的就是收尾并从 DynASM 中提取函数指针:

return;
| epilogue
link_and_encode(&d);
dasm_free(&d);
return (void(*)(bf_state_t*))labels[lbl_bf_main];

第一行调用了我们定义的 epilogue 宏. 下一行调用 link_and_encode, 一会给出. 然后调用 dasm_free, 用来释放 DynASM state. 最后, 我们将之前定义的 labels 数组传递到 dasm_setupglobal, 数组的索引是 lbl_bf_main (由 .globals lbl_ 定义, 并与全局标签 ->bf_main 对应), 并将其转换为函数指针.

link_and_encode 函数的定义如下:

#if _WIN32
#include <Windows.h>
#else
#include <sys/mman.h>
#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
#define MAP_ANONYMOUS MAP_ANON
#endif
#endif

static void* link_and_encode(dasm_State** d)
{
  size_t sz;
  void* buf;
  dasm_link(d, &sz);
#ifdef _WIN32
  buf = VirtualAlloc(0, sz, MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE);
#else
  buf = mmap(0, sz, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
#endif
  dasm_encode(d, buf);
#ifdef _WIN32
  {DWORD dwOld; VirtualProtect(buf, sz, PAGE_EXECUTE_READ, &dwOld); }
#else
  mprotect(buf, sz, PROT_READ | PROT_EXEC);
#endif
  return buf;
}

值得注意的是dasm_link 和 dasm_encode 调用. 其余的函数调用使用操作系统功能来分配一个 读-写 内存块, 然后将其转换为 读-执行. 注意, 我们可以分配一个 读-写-执行 内存块, 但是通常同时具有可写和可执行的内存不是好的的形式.

---

Compiling

根据上面的教程, 现在 tutorial.c 是这个样子的:

||#if ((defined(_M_X64) || defined(__amd64__)) != X64) || (defined(_WIN32) != WIN)
#error "Wrong DynASM flags used: pass `-D X64` and/or `-D WIN` to dynasm.lua as appropriate"
#endif
#include <stdio.h>
#include <stdlib.h>
#include "luajit-2.0/dynasm/dasm_proto.h"
#include "luajit-2.0/dynasm/dasm_x86.h"
#if _WIN32
#include <Windows.h>
#else
#include <sys/mman.h>
#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
#define MAP_ANONYMOUS MAP_ANON
#endif
#endif

static void* link_and_encode(dasm_State** d)
{
  size_t sz;
  void* buf;
  dasm_link(d, &sz);
#ifdef _WIN32
  buf = VirtualAlloc(0, sz, MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE);
#else
  buf = mmap(0, sz, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
#endif
  dasm_encode(d, buf);
#ifdef _WIN32
  {DWORD dwOld; VirtualProtect(buf, sz, PAGE_EXECUTE_READ, &dwOld); }
#else
  mprotect(buf, sz, PROT_READ | PROT_EXEC);
#endif
  return buf;
}

#define TAPE_SIZE 30000
#define MAX_NESTING 100

typedef struct bf_state
{
  unsigned char* tape;
  unsigned char (*get_ch)(struct bf_state*);
  void (*put_ch)(struct bf_state*, unsigned char);
} bf_state_t;

#define bad_program(s) exit(fprintf(stderr, "bad program near %.16s: %s\n", program, s))

static void(* bf_compile(const char* program) )(bf_state_t*)
{
  unsigned loops[MAX_NESTING];
  int nloops = 0;
  int n;
  dasm_State* d;
  unsigned npc = 8;
  unsigned nextpc = 0;
  |.if X64
  |.arch x64
  |.else
  |.arch x86
  |.endif
  |.section code
  dasm_init(&d, DASM_MAXSECTION);
  |.globals lbl_
  void* labels[lbl__MAX];
  dasm_setupglobal(&d, labels, lbl__MAX);
  |.actionlist bf_actions
  dasm_setup(&d, bf_actions);
  dasm_growpc(&d, npc);
  |.if X64
    |.define aPtr, rbx
    |.define aState, r12
    |.if WIN
      |.define aTapeBegin, rsi
      |.define aTapeEnd, rdi
      |.define rArg1, rcx
      |.define rArg2, rdx
    |.else
      |.define aTapeBegin, r13
      |.define aTapeEnd, r14
      |.define rArg1, rdi
      |.define rArg2, rsi
    |.endif
    |.macro prepcall1, arg1
      | mov rArg1, arg1
    |.endmacro
    |.macro prepcall2, arg1, arg2
      | mov rArg1, arg1
      | mov rArg2, arg2
    |.endmacro
    |.define postcall, .nop
    |.macro prologue
      | push aPtr
      | push aState
      | push aTapeBegin
      | push aTapeEnd
      | push rax
      | mov aState, rArg1
    |.endmacro
    |.macro epilogue
      | pop rax
      | pop aTapeEnd
      | pop aTapeBegin
      | pop aState
      | pop aPtr
      | ret
    |.endmacro
  |.else
    |.define aPtr, ebx
    |.define aState, ebp
    |.define aTapeBegin, esi
    |.define aTapeEnd, edi
    |.macro prepcall1, arg1
      | push arg1
    |.endmacro
    |.macro prepcall2, arg1, arg2
      | push arg2
      | push arg1
    |.endmacro
    |.macro postcall, n
      | add esp, 4*n
    |.endmacro
    |.macro prologue
      | push aPtr
      | push aState
      | push aTapeBegin
      | push aTapeEnd
      | mov aState, [esp+20]
    |.endmacro
    |.macro epilogue
      | pop aTapeEnd
      | pop aTapeBegin
      | pop aState
      | pop aPtr
      | ret 4
    |.endmacro
  |.endif

  |.type state, bf_state_t, aState
  
  dasm_State** Dst = &d;
  |.code
  |->bf_main:
  | prologue
  | mov aPtr, state->tape
  | lea aTapeBegin, [aPtr-1]
  | lea aTapeEnd, [aPtr+TAPE_SIZE-1]
  for(;;) {
    switch(*program++) {
    case '<':
      for(n = 1; *program == '<'; ++n, ++program);
      | sub aPtr, n%TAPE_SIZE
      | cmp aPtr, aTapeBegin
      | ja >1
      | add aPtr, TAPE_SIZE
      |1:
      break;
    case '>':
      for(n = 1; *program == '>'; ++n, ++program);
      | add aPtr, n%TAPE_SIZE
      | cmp aPtr, aTapeEnd
      | jbe >1
      | sub aPtr, TAPE_SIZE
      |1:
      break;
    case '+':
      for(n = 1; *program == '+'; ++n, ++program);
      | add byte [aPtr], n
      break;
    case '-':
      for(n = 1; *program == '-'; ++n, ++program);
      | sub byte [aPtr], n
      break;
    case ',':
      | prepcall1 aState
      | call aword state->get_ch
      | postcall 1
      | mov byte [aPtr], al
      break;
    case '.':
      | movzx r0, byte [aPtr]
      | prepcall2 aState, r0
      | call aword state->put_ch
      | postcall 2
      break;
    case '[':
      if(nloops == MAX_NESTING)
        bad_program("Nesting too deep");
      if(program[0] == '-' && program[1] == ']') {
        program += 2;
        | xor eax, eax
        | mov byte [aPtr], al
      } else {
        if(nextpc == npc) {
          npc *= 2;
          dasm_growpc(&d, npc);
        }
        | cmp byte [aPtr], 0
        | jz =>nextpc+1
        |=>nextpc:
        loops[nloops++] = nextpc;
        nextpc += 2;
      }
      break;
    case ']':
      if(nloops == 0)
        bad_program("] without matching [");
      --nloops;
      | cmp byte [aPtr], 0
      | jnz =>loops[nloops]
      |=>loops[nloops]+1:
      break;
    case 0:
      if(nloops != 0)
        program = "<EOF>", bad_program("[ without matching ]");
      | epilogue
      link_and_encode(&d);
      dasm_free(&d);
      return (void(*)(bf_state_t*))labels[lbl_bf_main];
    }
  }
}

static void bf_putchar(bf_state_t* s, unsigned char c)
{
  putchar((int)c);
}

static unsigned char bf_getchar(bf_state_t* s)
{
  return (unsigned char)getchar();
}

static void bf_run(const char* program)
{
  bf_state_t state;
  unsigned char tape[TAPE_SIZE] = {0};
  state.tape = tape;
  state.get_ch = bf_getchar;
  state.put_ch = bf_putchar;
  bf_compile(program)(&state);
}

int main(int argc, char** argv)
{
  if(argc == 2) {
    long sz;
    char* program;
    FILE* f = fopen(argv[1], "r");
    if(!f) {
      fprintf(stderr, "Cannot open %s\n", argv[1]);
      return 1;
    }
    fseek(f, 0, SEEK_END);
    sz = ftell(f);
    program = (char*)malloc(sz + 1);
    fseek(f, 0, SEEK_SET);
    program[fread(program, 1, sz, f)] = 0;
    fclose(f);
    bf_run(program);
    return 0;
  } else {
    fprintf(stderr, "Usage: %s INFILE.bf\n", argv[0]);
    return 1;
  }
}

如果没跟上, 还可以从这里获取代码:

git clone https://github.com/corsix/dynasm-doc.git
cd dynasm-doc
git submodule update --init
cp bf_dynasm.c tutorial.c

为了编译 tutorial.c, 我们首先需要通过 DynASM 预处理程序运行它. 预处理器是用 Lua 编写的, 因此我们首先编译一个 minimal Lua 解释器 (如果有luajit也可以直接用luajit运行dynasm.lua, 就可以省略这一步):

gcc -o minilua luajit-2.0/src/host/minilua.c

然后运行 DynASM 预处理器:

./minilua luajit-2.0/dynasm/dynasm.lua -o tutorial.posix64.c -D X64 tutorial.c

完成预处理后, 调用 C 编译器:

gcc -o tutorial tutorial.posix64.c

然后, 我们可以运行生成的可执行文件, 该可执行文件将很快运行 Mandelbrot set:

./tutorial mandelbrot.bf

(译者我的运行结果, 2.129s, 源程序是 35.466s, 耗时是原来的 6%, 性能提升了17倍)

[root@m01 dynasm-doc]# time ./tutorial mandelbrot.bf
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDEGFFEEEEDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
A                                                                                                 PLJHGGFFEEEDDDDDDDCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
real 0m2.129s
user 0m2.126s
sys 0m0.003s