C コンパイラをつくってみる (6) ひとまず完結&総括

低レイヤを知りたい人のためのCコンパイラ作成入門 ステップ11-15を参考にしています。

前回 (5)

識別子を、[a-z] から [a-zA-Z_][a-zA-Z0-9_]* に拡張

• 参考: ステップ11
• コード差分
  • ローカル変数をスタックフレーム内にどう割り当てるか、パース時に保存し、コード生成時に読み出すように変更した。

/* 字句解析器の identifier 部分 */
if(std::isalpha(*p) || *p == '_'){  // 最初の文字は [a-zA-Z_]
  auto p_lookahead = p+1;
  while(is_alnum(*p_lookahead)){    // それ以降は [a-zA-Z0-9_] (is_alnum に実装されてる) じゃなくなるまで読む
    ++p_lookahead;
  }
  /* トークン構造体生成 (省略) */
  continue;
}

ひとつの文をたずさえた if 文, for 文, while 文を導入

• 参考: ステップ12
• コード差分
  • stmt の中でトークンを1つ読めば以後の構文が確定するのでそれほど難しいことはない。
  • 抽象構文木のノードが initialization（forの最初の式） condition（各制御構文の条件式） afterthought（forの更新式） body（本体） を指せるようにした。

# 構文の一部
stmt := "return" expression ";"
      | "if" "(" expression ")" stmt
      | "for" "(" expression ";" expression ";" expression ")" stmt
      | "while" "(" expression ")" stmt
      | expression ";"

/* for 文のコード生成 */
if(node->type == ASTNodeType::FOR){
  size_t static new_for_stmt_sequence = 0;
  auto const for_stmt_sequence = new_for_stmt_sequence;
  new_for_stmt_sequence++;
  // 雑に通し番号をつくってユニークなラベルをつくる
  std::string const loop_label = ".FOR_STMT_" + std::to_string(for_stmt_sequence) + "_LOOP";
  std::string const break_label = ".FOR_STMT_" + std::to_string(for_stmt_sequence) + "_BREAK";

  // 初期化式を生成
  gen(node->initialization);
  // ループ用ラベルを配置
  std::cout << loop_label << ":\n";
  // 条件式を生成
  gen(node->condition);
  std::cout <<
    // 条件式の評価結果をポップして
    "  ld  a0, (sp)\n"
    "  addi  sp, sp, " << sizeof_variable << "\n"
    // 0 なら body を抜けるラベルに飛ぶ
    "  beqz  a0, " << break_label << "\n";
  // body と afterthought を生成
  gen(node->body);
  gen(node->afterthought);
  std::cout <<
    // 条件式の評価に戻る
    "  j   " << loop_label << "\n"
    // 抜けるラベルを配置
    << break_label << ":\n";

  return;
}

複文（ブロック）

• 参考: ステップ13
• コード差分

# 構文の一部
stmt := "return" expression ";"
      | "if" "(" expression ")" stmt
      | "for" "(" expression ";" expression ";" expression ")" stmt
      | "while" "(" expression ")" stmt
(NEW) | "{" block_items "}"
      | expression ";"

block_items := none
             | stmt
             | stmt block_items

block_items は stmt の 0回以上の 繰り返しっていうのがミソで、1回以上にしちゃうと後で void f(){} がコンパイルできなくなる。 ここで発覚したヤバめのバグは脚注*1で…。

次のコードをコンパイルできるようになった。

{a = 0; b = 0;}
if(1){ a = 1; b = 2; }
if(0){ a = 3; b = 4; }
while(1){{return a*a*b*b;}}

関数呼び出し

• 参考: ステップ14
• コード差分

まず構文を変更して

unary := "+" funccall
       | "-" funccall
       | funccall

funccall := term
          | term "(" ")"

term := "(" expression ")"
      | number
      | identifier

構文解析器を変更

/* 構文解析の funccall (= 関数呼び出しか term) 解析部分 */
ASTNode* funccall(std::vector<Token>::const_iterator& token_itr){
  ASTNode* node = term(token_itr);
  if(consume(TokenType::BEGIN_PAREN, token_itr)){
    // term 直後の開きカッコ ( をみつけたら
    ASTNode* callnode = new ASTNode();
    callnode->type = ASTNodeType::FUNCTION_CALL;
    callnode->lhs = node;
    if(consume(TokenType::END_PAREN, token_itr)){
      // term () の場合
      callnode->inner_nodes = {};
    }else{
      // term ( argument_list ) の場合
      callnode->inner_nodes = argument_list(token_itr);
      require_token(TokenType::END_PAREN, token_itr);
    }
    return callnode;
  }
  return node;
}
std::vector<ASTNode const*> argument_list(std::vector<Token>::const_iterator& token_itr){
  std::vector<ASTNode const*> arguments;
  // 式を解析・コンマを消費 を繰り返す （コンマがなくなったら終わり）
  do{
    arguments.push_back(expression(token_itr));
  }while (consume(TokenType::COMMA, token_itr));
  return arguments;
}

コード生成は… 各実引数を評価してレジスタに積む。

/* グローバル定数においてあるレジスタ一覧 */
std::array<std::string, 8> const static
  argument_registers{ "a0", "a1", "a2", "a3", "a4", "a5", "a6", "a7" };

/* コード生成の FUNCTION_CALL 部分 */
size_t const num_of_args = std::min(argument_registers.size(), node->inner_nodes.size());
for(size_t i=0; i<num_of_args; ++i){
  // 実引数を左から順番に評価（スタックに積まれる）
  gen(node->inner_nodes.at(i));
}
for(size_t i=0; i<num_of_args; ++i){
  // sp からのオフセットを考えて、評価した実引数をスタックから取り出し、レジスタにロード
  ptrdiff_t const offset = sizeof_variable * (num_of_args-i-1);
  std::cout <<
    "  ld   " << argument_registers.at(i) << ", " << offset << "(sp)\n";
}
std::cout <<
  // 使った分は sp を始末しておきましょう
  "  addi  sp, sp, " <<  sizeof_variable * num_of_args << "\n"
  // 自分の戻り先アドレスが失くなってしまわないように保存しておきましょう
  "  addi  sp, sp, -" << sizeof_variable << "\n"
  "  sd    ra, (sp)\n"
  // 識別子名をそのまま call に発行します（アセンブラありがとう）
  "  call  ra, " << callee->id_name << "\n"
  // 戻り先アドレスを復元
  "  ld    ra, (sp)\n";
return;

このとき、スタックポインタ sp は 16 バイト境界に align しないといけないみたい で、面倒なので各 push, pop を16バイトにした。

関数定義

• 参考: ステップ15
• コード差分

ここが一番バグった（&バグを顕在化させた）…。

ソースコード全体は 関数定義の0回以上の繰り返し になるように文法を変更。

program := funcdef program
         | none

funcdef := identifier "("                ")" "{" block_items "}"
         | identifier "(" parameter_list ")" "{" block_items "}"

parameter_list := identifier "," parameter_list

構文解析器も変更して、各関数定義に通し番号を振って、ローカル変数のオフセットなどが相互に影響しないようにした。（コード省略）

コード生成。関数の突入時には ベースポインタの退避・新規設定 と スタックフレームの取得をして

size_t const stackframe_size =
  variables_info.num_of_variables(generating_funcdef_function_id)  * sizeof_variable;

std::cout <<
  "# prologue\n"
  // ベースポインタをスタックに退避
  "  addi  sp, sp, -" << sizeof_variable << "\n"
  "  sd    s0, (sp)\n"
  // 現在のスタックポインタをベースポインタにコピー
  "  mv    s0, sp\n"
  // スタックフレームを確保
  "  addi  sp, sp, -" << stackframe_size << "\n";

レジスタに入っている（実引数の）値を、スタックに割り当てた仮引数にコピーする。これで関数内でローカル変数と同列に扱える。

size_t const num_of_parameters = node->call_list.size();
for(size_t i=0; i<num_of_parameters; ++i){
  ASTNode const* const param = node->call_list.at(i);
  ptrdiff_t const offset = variables_info.offset_of(generating_funcdef_function_id, param->id_name);
  std::cout <<
    "  # copy " << param->id_name << "\n"
    "  sd   " << argument_registers.at(i) << ", -" << offset << "(s0)\n";
}

以下のようなコードがコンパイルできる*2。

absprod(x, y, z){
  return labs(x * y * z);   // libc の関数を呼ぶ
}
main(){
  return absprod(2, 3, 4);  // -> 24
}

FizzBuzz できました。

自作処理系でコンパイル:

fizz(){
  putchar(70);   // F
  putchar(105);  // i （以下略）
  putchar(122);
  putchar(122);
}
buzz(){
  putchar(66);
  putchar(117);
  putchar(122);
  putchar(122);
}
judge(x){
  f =  x % 3 == 0;
  b =  x % 5 == 0;
  if(f) fizz();
  if(b) buzz();
  if(f + b == 0) print_ld(x);
  putchar(10);   // 改行コード 0x0a
  return 0;
}
main(){
  for(i = 1; i <= 30; i = i + 1){
    judge(i);
  }
  return 0;
}

GCC でコンパイル:

#include <stdio.h>
#include <stdlib.h>
void print_ld(int64_t x){
  printf("%ld", x);
}

実行結果:

  1
  2
  Fizz
  4
  Buzz
  Fizz
  7
  8
  Fizz
  Buzz
  11
  Fizz
  13
  14
  FizzBuzz
（後略）

本記事に対応するコード差分 ← ここ

総括

知れたこと

• 「文脈自由文法」
• 再帰下降構文解析、LL(1) 解析
  • 再帰下降は構文規則と実際の解析コードの見た目が近く、編集しやすい。他はこうもいかないだろう。
  • 遷移表とか全然書いてない。
  • 文法のネストが関数呼び出しのスタックと各関数の仕事によってキレイに表現されてるの美しいなぁ…。
  • First Set、FollowSet、Director Set とかの理論的な部分？と結びつけるのはまだだけど、そういう本も読みやすくなる素地を作れた気がする。
• 字句解析 → 構文解析 → コード生成 の流れの肌感
  • 「フロントエンド」「バックエンド」と言いたくなる理由もわかってきた。
  • 抽象構文木のトラバースたのしい。
  • 今後拡張していった場合、たとえば break; のコード生成をするときに、「自分がどの while 文に所属するのか」という 文脈 が必要になるのでは？
  • Token にソースからの情報を保存して、 ASTNode はそれを覚えたり、ASTNode から Token を指したりしないと、「何行目でエラー」といったメッセージすら出せない！

知れなかったこと

• LL(1) 再帰下降以外の解析法
• 型
  • そもそも、型ってコンパイラの中でどうなってんの？というところにも興味があった。
  • 型とか計算理論の本読むか…。どうやって探そう。 TaPL ってどれくらい良いんですかね…。
• LL(1) の限界
  • C の実装をやっていくうちに、どこかで無理が来て解析法を変更しましょうねっていう流れになると思っていた。
• C のツライ部分
  • 「宣言文」「型」に手を出していないので。
  • typedef 怖そう。
  • ポインタ・関数型系の構文も。
• パーサジェネレータ、パーサコンビネータ
  • 一回なにか触ってみてもいいのかもしれない。
• LLVM
  • 同上。

参考文献

• 低レイヤを知りたい人のためのCコンパイラ作成入門
• RISC-V 原典
• RISC-V ELF psABI specification

*1: expression ; という文はスタックに1つ結果を残すので、ここまでは、 stmt の評価後はスタックを1段棄てることにしていた。if や for が入り、その expression ; が評価されるか不確定になったり、空の複文 {} があったりして、スタックを余計に棄てたりするバグが起こった。スタックマシン風をやっている限り、「そこで確実に評価する文」＝「expression ;」は他の文と別に扱う必要があるのかも…？ 今は stmt のコード生成で「IFじゃなくてFORじゃなくてWHILEじゃなくて…」という対症療法をしたけど、それはそれで「expression ;」をbodyにもつ制御構文 stmt の評価後に1段余計にスタックを残す。治ってないぞ！

*2:ここで、UNIX に渡される返り値が uchar 幅相当なのを忘れて、でかい数を返して「テスト合わない！！」っていうヘマをしました…

C コンパイラをつくってみる (5)

低レイヤを知りたい人のためのCコンパイラ作成入門 ステップ9-10を参考にしています。

前回 (4)

次回 (6) 仮完結編

ローカル変数

変数を使うには、代入 a = 1 とそれを使った計算 a + 1 などができないと話にならないので、先に文法に 文はセミコロンで終端される 規則を入れた*1。

stmt := assignment ";"

アルファベット小文字1文字トークンからなるローカル変数を実現するために、スタックフレームの大きさを（a から z までの分で）固定。 s0 レジスタ（x86でいうところのebp）*2 からのオフセットでアクセスする。

スタックフレームは、main の開始時に確保（sp からフレームサイズを引く）し、ret する直前に解放（sp を戻す）する。

（抽象構文木中の）変数ノードは、「そのアドレスを計算してスタックにプッシュする」アセンブリを生成する。

size_t const offset = ('z' - id_name + 1) * sizeof_variable;
std::cout <<
  // ローカル変数のアドレスを s0 からのオフセットで計算
  "  mv   a0, s0\n"
  "  addi a0, a0, -" << offset << "\n"
  // スタックにプッシュ
  "  addi sp, sp, -" << sizeof_variable << "\n"
  "  sd   a0, (sp)\n";

変数の値がほしい場面ではデリファレンスする。

std::cout <<
  // スタックからアドレスをポップ
  "  ld  a0, (sp)\n"
  // そのアドレスから値をロード
  "  ld  a0, (a0)\n"
  // スタックの同じ箇所に上書き
  "  sd  a0, (sp)\n";

（抽象構文木中の）代入演算子ノードは、上記のアドレス計算と、右辺の値の計算を終わらせ、スタックからオペランドを2つとってストアする。

std::cout <<
  // 2つポップ (a0: ストア先アドレス, a1: ストアされる値)
  "  ld  a1, (sp)\n"
  "  ld  a0, " << sizeof_variable << "(sp)\n"
  "  addi sp, sp, " <<  sizeof_variable*2 << "\n"
  // ストアする
  "  sd  a1, (a0)\n"
  // おなじ値をスタックにプッシュ(多重代入 e.g. a=b=1 のため)
  "  addi sp, sp, -" << sizeof_variable << "\n"
  "  sd  a1, (sp)\n";

以下のような計算ができるようになった。

a = 2; c = 3; z = 4; a + c + z + 1;   => 10

return 文

文の定義を
stmt := assignment ";" から
stmt := "return" assignment ";" | assignment ";" に変更し、
字句解析側で return[^a-zA-Z0-9] *3 をみつけて、ひとつのトークンとして扱うことで、return 文を実装した。

コード生成としては、 return なにか; が来たらすぐさま、main の終わり方と同じく ret 命令を含む コードを出力する。

以下のように、一度目の return 以後は評価されないことを確かめられた。

return 1; return 2;    => 1

---

コード差分はこちら

余談

デバッグ環境が欲しくなったけれど、 riscv64-linux-gnu で GDB のネイティブデバッグ機能はまだ無いようだし、 gdbserver もビルド中に Not Supported と言われてしまう。

basic Linux application support (中略) will be in the next (8.3) release. https://riscv.org/software-status/#debugging

gdb-8.3 には入るのかな？ どう発表されたら native デバッグができることになるのか、よく分からない。

参考文献

• 低レイヤを知りたい人のためのCコンパイラ作成入門
• RISC-V 原典

*1:if 文 や for 文 で破綻しそう

*2:Calling Convention には s0/fp と表記があるが、fp ではアセンブルできなかった。fp のほうが役割を表していてわかりやすいのだが…

*3:の、"return" の部分

C コンパイラをつくってみる (4)

低レイヤを知りたい人のためのCコンパイラ作成入門 ステップ5-6を参考にしています。

前回 (3)

次回 (5)

単項 +, - 演算子

結合順として乗算 * と項 (...) の間に、単項演算子を入れる。生成規則

unary := term | "+" term | "-" term

として、構文解析のロジックを書き下す。

これまで書いてきた mul := term | mul "*" term ... のように自己再帰的な、「0回以上の繰り返し」を表す生成規則に対応するコードとはすこし景色が違った（無条件forによる繰り返しがない・次トークンを見る前にはじめに決め打ちで解析するルールがない）。

ASTNode* unary(std::vector<Token>::const_iterator& token_itr){
  if(consume(TokenType::PLUS, token_itr)){
    // 単項 + はそのままオペランドを使う
    return term(token_itr);
  }else if(consume(TokenType::MINUS, token_itr)){
    // 単項 - は、「0 - オペランド」の減算を生成する。
    auto const zeroNode = newNodeNumber(0);
    auto const subtractionNode = newNodeBinary(ASTNodeType::BINARY_SUB, zeroNode, term(token_itr));
    return subtractionNode;
  }else{
    return term(token_itr);
  }
}

比較演算子

加減算より結合の弱い演算子として大小比較の演算子群 <= < >= > を入れ、さらにそれより結合の弱い演算子として等値比較の演算子群 == != を入れた*1。

トークナイザを変更する際には、 <= と >= は、 < > より先にマッチさせる ことに留意した。

これまで同様に、結合順位を考慮して生成規則を変更した。

比較演算子の RV32I におけるアセンブリコードは以下のように書いた。（スタックマシン風の枠組みによって a0 に左オペランド、 a1 に右オペランドがロードされている。）

# ==
sub  a0, a0, a1  # 減算して
seqz a0, a0      # 0と等しければ1
# !=
sub  a0, a0, a1  # 減算して
snez a0, a0      # 0と異なれば1
# <
slt a0, a0, a1
# <=
sub a2, a0, a1   # 減算して
seqz a2, a2      # 0と等しいか
slt a0, a0, a1   # < が成り立つ
or  a0, a0, a2

<= に関しては他にやり方*2がありそうだけどわかりやすさ重視でこうなった。

以下のような演算ができるようになった。

1 <  1    => 0
1 <= 1    => 1
5 == 2+3  => 1

差分はこちら

参考文献

• 低レイヤを知りたい人のためのCコンパイラ作成入門
• RISC-V 原典

*1:条件が成り立つとき整数の1、成り立たなければ整数の0になる演算

*2:片方に1を加えて slt するとか

C コンパイラをつくってみる (3)

低レイヤを知りたい人のためのCコンパイラ作成入門 ステップ4を参考にしています。

前回 (2)

次回 (4)

構文木の導入

1+2*3 を 1+(2*3) として計算するためには、トークンを左から消費していくだけではいけない。

加減算と乗除算の生成規則を階層立てて定義し、トークンを再帰的に処理していくことで、演算子の結合順位を実現する。

# 加減算・乗除算の階層を分けた生成規則
add := mul | add "+" mul | add "-" mul
mul := num | mul "*" num | mul "/" num

トークン列の左から消費して、トップダウンに構文解析をすることを LL 法 というらしい。今回はトークン1つを見て生成規則を決めるので、 LL(1) 。

enum class ASTNodeType{
  BINARY_ADD,
  BINARY_SUB,
  BINARY_MUL,
  BINARY_DIV,
  NUMBER
};
struct ASTNode{
  ASTNodeType type;
  ASTNode const* lhs;
  ASTNode const* rhs;
  int value;
};

こんな感じで構文木のノードを定義し、

ASTNode* add(std::vector<Token>::const_iterator& token_itr){
  ASTNode* node = mul(token_itr);
  for(;;){
    if(consume(TokenType::PLUS, token_itr)){
      node = newNodeBinary(ASTNodeType::BINARY_ADD, node, mul(token_itr));
    }else if(consume(TokenType::MINUS, token_itr)){
      node = newNodeBinary(ASTNodeType::BINARY_SUB, node, mul(token_itr));
    }else{
      return node;
    }
  }
}

1つのトークンを見て再帰的に解析関数を呼び出す。

構文木からスタックマシン風アセンブリの生成

木構造になった計算順序を実際に実現するために、スタックポインタを使ってスタックマシン風に計算する。

RV32I で即値 (node->value) の push はこんな感じで作った。

std::cout <<
  "  addi sp, sp, -" << stack_size << "\n"
  "  li   a0, " << node->value << "\n"
  "  sw   a0, 0(sp)\n";

二項演算子が出てきたら、2つの値をポップ（a0, a1 にロード）して…

std::cout <<
  "  lw  a1, 0(sp)\n"
  "  lw  a0, " << stack_size << "(sp)\n"
  "  addi sp, sp, " <<  stack_size*2 << "\n";

構文木ノードのタイプに応じて命令を発行する。

if(node->type == ASTNodeType::BINARY_ADD){
  std::cout << "  add a0, a0, a1\n";
}else if ...

構文木のルートノードから再帰的に 「lhs, rhs, 自分」 の命令を出力していくことで、計算順序を考慮した四則演算のプログラムを出力できる。

成功したテストケースはこんな感じ。

 5    + 20            - 4 => 21
 3*2 => 6
 18/3 => 6
 1+3*2 => 7
 1+10/2*4-1 => 20
 (1+2)*3 => 9  // 括弧も実装された

差分はこちら

参考文献

• 低レイヤを知りたい人のためのCコンパイラ作成入門
• RISC-V 原典

C コンパイラをつくってみる (2)

低レイヤを知りたい人のためのCコンパイラ作成入門 ステップ1-3を参考にしています。

前回 (1)

次回 (3)

整数1つからなる言語

前回の、整数1つを a0 レジスタに入れて OS に返すアセンブリをもとにする。

ソースコード（ここではコマンドライン引数）として整数1つを受け取り、それを返すことのできる RISC-V アセンブリを出力する。

  std::cout <<
    ".global main\n"
    "\n"
    "main:\n"
    "  li   a0, " << argv[1] << "\n"
    "  ret\n" << std::endl;

こんな感じにした。

全体はこちら

整数の加算・減算

この言語の機能に、加算と減算を入れる。

• はじめに1つ整数を読み込み、それを a0 レジスタに入れる。
• つづいて、 + か - を期待し、その後続く整数を a0 レジスタに加えたり引いたりする。

加算と減算には、 RV32I の即値加算 addi を使う。即値減算はない *1 。

// p は、ソースとなる文字列中の文字へのポインタ
if(*p == '+'){
  p++;
  std::cout << "  addi  a0, a0, " << std::strtol(p, &p, 10) << "\n";
  continue;
}
if(*p == '-'){
  p++;
  std::cout << "  addi  a0, a0, -" << std::strtol(p, &p, 10) << "\n";
  continue;
}

差分はこちら

Tokenizer を導入する

空白が構文に影響しないように、整数を1つ、 + のようなオペレータを1つといった単位（トークン）として扱うようにする。

上記の加算・減算もトークン単位で扱う。

std::vector<Token> tokenize(char const* p){
  std::vector<Token> tokens;

  while(*p){
    if(isspace(*p)){
      p++;
      continue;
    }

    if(*p == '+'){
      Token token;
      token.type = TokenType::OPERATOR_PLUS;
      token.input = p;
      tokens.push_back(token);
      p++;
      continue;
    }
    ....

トークンを消費する（アセンブリを吐く）ほうはこんな感じ

for(size_t i=1; i<tokens.size() && tokens.at(i).type != TokenType::EOS; ){
  if(tokens.at(i).type == TokenType::OPERATOR_PLUS){
    i++;
    if(tokens.at(i).type != TokenType::NUMBER){
      error("予期しないトークン: %s", tokens.at(i).input);
    }
    std::cout << "  addi a0, a0, " << tokens.at(i).value << "\n";
    i++;
    continue;
  }
  ....

10 + 13 - 4 のように空白を含んでいてもコンパイルできるようになった。

差分はこちら

参考文献

• 低レイヤを知りたい人のためのCコンパイラ作成入門

*1:「即値は常に符号拡張される。必要なら、負の値を取れるようにするためである。したがって sub の即値版は必要ない」 RISC-V 原典 p.21

C コンパイラをつくってみる (1)

純粋にコンパイラの構成に興味が出てきたので挑戦。 低レイヤを知りたい人のためのCコンパイラ作成入門 を参考にしてみようと思う。

ターゲットはせっかくなので RISC-V (64bit)。

環境構築

Ubuntu 18.04

先日リリースされた 19.04 を入れてみていたが、壊れていたので再インストール。

ツールチェイン

1回ビルドしてみたけど長くて少し懲りた。

$ apt search riscv

で、 gcc-8-riscv64-linux-gnu やら g++-8-riscv64-linux-gnu が見つかるのでインストールした。

エミュレータ

QEMU の公式 から、最新の 4.0.0 のソースを落としてきてビルドした。

Linux イメージ

エミュレータで動かす Linux イメージを調達する。 QEMU の Wiki に、Fedora を動かす方法が詳しくかいてあったのでイメージをダウンロードし、起動用コマンドラインをコピペした。

Welcome to Fedora 28 (Rawhide)!

動いた。ユーザー root, PW riscv でログインできた。

整数1つを返すプログラム

まずはクロスビルド環境が動いているか確認したい。

参考サイト における「整数1個をコンパイルする言語」の出力となるようなシンプルなプログラムを動かしてみる。

適当な .c をコンパイルした結果や、RISC-V 原典の Hello, World を見比べながら下のようなアセンブリを書いた。

.global main

main:
    li  a0, 42
    ret

クロスビルドする。

$ riscv64-linux-gnu-gcc-8 single_int.s -o single_int

QEMU の中に転送する。

$ scp -P10000 single_int root@localhost:single_int

QEMU 内で実行する。

[root@stage4 ~]# ./single_int
[root@stage4 ~]# echo $?
42

OS に返り値を渡すことに成功した。

次回 (2)

参考文献

• 低レイヤを知りたい人のためのCコンパイラ作成入門
• Documentation/Platforms/RISCV - QEMU
• RISC-V 原典

長い MIDI System Exclusive に迫る罠 (JUCE on macOS での1バイト欠落問題の原因)

sigboost ソフトウェアエンジニア @skb_apos です。 midiglue を作っています。

記事の概要

• MIDI Exclusive を濫用応用してファイルを送信するプロトコルを作って実装したら
• macOS でのみ「周期的に 1バイト欠ける 」問題が起きた
• ユーザーコード → JUCE フレームワーク → CoreMidi ライブラリ → USB MIDI ドライバ
  と手渡されていく中での原因を突き止めた

MIDI System Exclusive とは

基礎編～システムエクスクルーシヴ - DTMゼミ

MIDI の共通規格を超えた制御信号(など)を送りたい場合に、MIDI 機器のベンダが独自に定めることのできる MIDI メッセージの種類。

DIN を使う従来の MIDI でも、 USB MIDI でも共通に使える。

SC-88Pro という音源の場合の例がこちら。 「リバーブレベル」のメッセージ内容を以下に引用する。

Rev Level: F0 41 10 42 12 40 01 33 (00-7F) sum F7

0xF0 で始まり、 0xF7 で終わる可変長のメッセージ。上記の例はリバーブレベルを 0x00 から 0x7F の 128 段階で変更できるよう。

1バイトのうち、MSB側の1ビット (ビットマスク 0b1000'0000) のビットは、特別な意味を持つのでメッセージ内 (開始・終了バイト以外) のバイトは使用できない。

長い System Exclusive を送ったときに起きたこと

問題の検証のために、uint8_t で連番を記録したファイルを転送した。このときの System Exclusive メッセージの長さは 1038 バイト。

上の画像でハイライトされている箇所は、よく見ると 連番の規則性を崩している 。何が起きたかというと、 一定間隔で MIDI メッセージの1バイト*1が欠落する ということのよう。

原因は何か

手元で作った System Exclusive メッセージが通過する箇所をそれぞれ見ていこう。

ユーザーが1000バイトの System Exclusive メッセージを作る。

サウンドを扱うフレームワーク(今回はJUCE) は、 macOS の CoreMIDI の最大メッセージ長 256 バイト に合わせるため、メッセージを 256 バイトごとに分割する

USB MIDI ドライバは、4バイト固定長 USB MIDI イベントパケット (1バイトヘッダ + 3バイト MIDI ペイロード) を作るため、最大 256 バイトのメッセージをさらに 3 バイトごとに分割する

ここで図の「255」のバイトは、1 バイトの断片となってしまった。

ところが、USB MIDI イベントパケットのヘッダには、System Exclusive 関連のものは以下のものしかない。

CIN	MIDI_x サイズ	説明
0x04	3	システム・エクスクルーシブ始端 / 中間
0x05	1	1 バイト・システムコモン・メッセージ/システム・エクスクルーシブ終端 (1 バイト)
0x06	2	システム・エクスクルーシブ終端 (2 バイト)
0x07	3	システム・エクスクルーシブ終端 (3 バイト)

(シンセ・アンプラグド USB-MIDI (10) より抜粋引用)

つまり、 「System Exclusive の中間」 0x04 のヘッダが使われるのはいつでも残りメッセージ長が 3 を超える ときであり、メッセージが1バイトに断片化することは (MIDIの) 規格上想定されていない。

ここから先は推測でしかないが、ドライバは、3 バイトすべて書き込まれたときか、1 バイト・2 バイトのそれぞれで System Exclusive が終端されるときのみメッセージを送信する。断片化した 1 バイトは送信されず欠落してしまう。

要するに

「256 バイトごと (CoreMIDI) 、 3 バイトごと (MIDI/USB MIDI) というそれぞれの都合によるメッセージの断片化が、規格の想定を超えた断片を作ってしまい、うまく送れなかったよ！！」

誰のバグであるとも結論づけにくい。

System Exclusive メッセージは 256 バイトを超えないようにしようね、っていうのが今回の結論であったが、 "macOS + JUCE" という限られた環境での解決策でしかない *2。

先達はあらまほしきことなり

• Midibox というプロダクトを作っているチームがあり、System Exclusive によるファームウェアアップデートをやっていた。その中でこの問題はかねてから障害になっていて、「うまく送れる組み合わせホワイトリスト」「無理な組み合わせブラックリスト」が作られている そうな……。
• JUCE の GitHub Issue にも既出だが対応される気配なし。

*1:前述のようにMIDIメッセージ内では7ビットしか自由にできないので、任意ファイルの1バイトを2バイトに分割する処理を事前にしている。画像では4ビット欠落しているが、これをMIDIメッセージに換算すると1バイトの欠落。

*2:限られた環境でしか起きてないのだから、まぁ、いいのか…。