付録 C. 疑似コード

CBOR 項目の整形式性は、図 1 の疑似コードで検査できます。データが整形式であるのは、次の場合かつその場合に限ります:

疑似コードが "fail" しないこと。
疑似コードの実行後、入力にバイトが残っていないこと (ストリーミングアプリケーションを除く)

疑似コードには次の前提条件があります:

take(n) は入力データから n バイトを読み取り、それらをバイト文字列として返します。n バイトがもはや利用できない場合、take(n) は失敗します。
uint() は、バイト文字列をネットワークバイトオーダーで解釈することにより、バイト文字列を符号なし整数に変換します。
演算は C 言語と同様に機能します。
すべての変数は十分な範囲を持つ符号なし整数です。

well_formed (breakable = false) {
  // process initial bytes
  ib = uint(take(1));
  mt = ib >> 5;
  val = ai = ib & 0x1f;
  switch (ai) {
    case 24: val = uint(take(1)); break;
    case 25: val = uint(take(2)); break;
    case 26: val = uint(take(4)); break;
    case 27: val = uint(take(8)); break;
    case 28: case 29: case 30: fail();
    case 31:
      return well_formed_indefinite(mt, breakable);
  }
  // process content
  switch (mt) {
    // case 0, 1, 7 do not have content; just use val
    case 2: case 3: take(val); break; // bytes/UTF-8
    case 4: for (i = 0; i < val; i++) well_formed(); break;
    case 5: for (i = 0; i < val*2; i++) well_formed(); break;
    case 6: well_formed(); break;     // 1 embedded data item
  }
  return mt;                    // finite data item
}

well_formed_indefinite(mt, breakable) {
  switch (mt) {
    case 2: case 3:
      while ((it = well_formed(true)) != -1)
        if (it != mt)           // need finite embedded
          fail();               //    of same type
      break;
    case 4: while (well_formed(true) != -1); break;
    case 5: while (well_formed(true) != -1) well_formed(); break;
    case 7:
      if (breakable)
        return -1;              // signal break out
      else fail();              // no enclosing indefinite
    default: fail();            // wrong mt
  }
  return 0;                     // no break out
}

図 1: 整形式性検査の疑似コード

完全な CBOR デコーダーの残りの複雑さは、解析済みのデータをアプリケーションに適切な形で提示することに関するものであることに注意してください。

主タイプ 0 および 1 は、正/負の判定のための if-then-else を実際には行わずに、C 言語で符号付き整数からエンコードできるように設計されています (図 2)。これは、主タイプ 1 の変換である (-1-n) が C の符号なし演算における ~n (ビットごとの補数) と同じであるという事実を利用しています。すると ~n は負の場合に (-1)^n と表現でき、一方 0^n は非負の場合に n をそのままにします。数値の符号は、その数値をその数値のビット長より 1 ビット少ない分だけ算術シフトすること (例えば 64 ビット数では 63) により、負の場合は -1、非負 (0 または正) の場合は 0 に変換できます。

void encode_sint(int64_t n) {
  uint64t ui = n >> 63;    // extend sign to whole length
  mt = ui & 0x20;          // extract major type
  ui ^= n;                 // complement negatives
  if (ui < 24)
    *p++ = mt + ui;
  else if (ui < 256) {
    *p++ = mt + 24;
    *p++ = ui;
  } else
       ...

図 2: 符号付き整数をエンコードする疑似コード