コグノスケ

CRCの計算方法 - その1

目次: ベンチマーク

令和の時代に今更ですがCRCについて調べてました。CRCのベースになる数学理論である有限体（ガロア体）は、興味深い性質をもちますが、私は説明できるほど詳しくないので、とりあえずCRCだけに着目します。

CRCはたくさんのバリエーションがあり、ビット数（CRC-8とかCRC-16とか）の違いといくつかのパラメータがあります。CRCの種類、パラメータ、結果のサンプルはCatalogue of parametrised CRC algorithmsが有名です。

良く見るパラメータは初期値（init）、出力へのXOR値（xorout）、順序（refin）、生成多項式（poly）です。

• 初期値: CRCの計算を始めるときの値
• 出力へのXOR値: CRCの計算後にXORする値
• 順序: MSBから演算 or LSBから演算のどちらか
• 生成多項式: 入力を割って余りを求めるのに使う多項式の2進数表現、最上位の1ビットが必ず1なので省略して書くことがほとんど

以降の説明ではCRC-8を例にしますので、CRC-8のパラメータを挙げておきます。

• CRC-8
• 初期値: 0
• XOR値: 0
• 順序: 逆転なし（MSB→LSB）
• 生成多項式: 0x1d5 = 0b1_11010101 (x^8 + x^7 + x^6 + x^4 + x^2 + 1)、最上位を省略するなら0xd5

初期値やXOR値が0で一番シンプルなCRCだと思います。

筆算で計算

CRC-8の入力と結果の一例を示します。入力が0xb3 0xb7だとすると結果は0xfeになります。

• 入力: 0xb3 0xb7（= 0b10110011_10110111）
• 結果: 0xfe = 0b11111110

筆算でCRC-8を計算する過程を全て書くと下記のようになります。

入力  : 10110011 10110111 00000000
初期値: 00000000

入力と初期値をXOR（今回は0なので値は変わらず）

10110011 10110111 00000000
11101010 1
 1011001 00110111 00000000
 1110101 01
  101100 01110111 00000000
  111010 101
   10110 11010111 00000000
   11101 0101
    1011 10000111 00000000
    1110 10101
     101 00101111 00000000
     111 010101
      10 01111011 00000000
      11 1010101
       1 11010001 00000000
       1 11010101
              100 00000000
              111 010101
               11 01010100
               11 1010101
                  11111110 = 0xfe

MSB→LSBの順に書いています。MSB側から生成多項式で割った余りがCRCの値です。入力データの最後（16ビット目以降）には生成多項式のビット数 - 1（9ビット - 1 = 8ビット）を0パディングします。パディングする理由がいまいちわからなかったのですが、パディングしないと8ビット以下の入力の場合に、入力 = CRCになってしまうからでしょうか？

プログラムで計算

プログラムで処理するときも筆算とほぼ一緒なんですが、入力をMSB側に寄せていくと考えるとわかりやすいと思います。

  10110011 10110111 00000000

#### 入力のMSBが1なら、1ビット左シフトして生成多項式をxorする = 余りを取る

1 01100111 01101110 0000000_
  11010101
  10110010 01101110 0000000_
| |
|  `--- 最上位を除く上位8ビットだけレジスタに保持する
`--- 左シフトであふれたビットは消す

#### 入力のMSBが0なら、1ビット左シフトする

  00100000 00000___ ________
0 01000000 0000____ ________
0 10000000 000_____ ________

#### 以降は上記の繰り返し

1 00000000 00______ ________
  11010101
  11010101 00______ ________

#### 全ビットを左シフトしたら終わり

  11111110 ________ ________ = 0xfe

MSB側に寄せていって計算する場合を1ステップずつ書くと下記のようになります。

1 01100111 01101110 0000000_
  11010101
  10110010 01101110 0000000_

1 01100100 11011100 000000__
  11010101
  10110001 11011100 000000__

1 01100011 10111000 00000___
  11010101
  10110110 10111000 00000___

1 01101101 01110000 0000____
  11010101
  10111000 01110000 0000____

1 01110000 11100000 000_____
  11010101
  10100101 11100000 000_____

1 01001011 11000000 00______
  11010101
  10011110 11000000 00______

1 00111101 10000000 0_______
  11010101
  11101000 10000000 0_______

1 11010001 00000000 ________
  11010101
       100 00000000 ________

1 00000000 00______ ________
  11010101
  11010101 00______ ________

1 10101010 0_______ ________
  11010101
  01111111 0_______ ________

  11111110 ________ ________ = 0xfe

先程の筆算が左側に寄っただけで、同じ値が計算途中に出現していることがわかると思います。

ドラクエ1リメイク、トロフィーコンプ

目次: ゲーム

Steamでドラクエ1＆2 HDリメイクを購入したまま完全放置でドラクエ3やってましたが、やっと戻ってきました。ドラクエ1の分のトロフィーコンプ（たぶん）しました。

ドラクエ1 HDリメイク、（ドラクエ1の分）トロフィーコンプ

ドラクエ1＆2の名の通り、トロフィーはドラクエ1とドラクエ2の分を合わせた表示でコンプかどうかよくわからないですね。まあいいか。一番ありがたかったのはドラクエ1にやりこみ要素がほぼないことでしょうか。やりこみ必要なトロフィーがあったら取れなかったと思います。

ドラクエ1リメイクの感想

ドラクエ1＆2リメイクは、ドラクエ3リメイクとほぼ一緒の制作陣（スクエニ、ARTDINK）です。画面のデザインやゲームのシステムも再利用されているらしくほぼ一緒で、ドラクエ3リメイクを知る人は見慣れた画面だと思います。

ドラクエ1リメイクは敵がやたら強いです。ドラクエ1はずっと1人旅をします。ファミコン版は敵も常に1人（=タイマン戦闘）でしたが、リメイク版は敵多数なのでいつも集団リンチされます。しかも敵から喰らうダメージがデカく、雑魚敵相手でさえ運が悪いと1ターンKOされ、耐えても回復が追いつかずジリ貧の末にKOされます。システムによる救済が格段に親切＆優しいので、全滅してもほぼデメリットないのは唯一の救いです。

私は岩泣き島と竜王の城辺りで、幾度も1ターンKOされて、嫌になってやめました。一応エンディングだけは見ましたよ。道中は「しのびあし」で全部ガン無視、竜王は「楽ちんプレイ」でガン無視した、やる気ゼロスタイルですけど。

ドラクエ3も1もどちらもストーリーの味付けやゲームの出来はとても良かったし、ドラクエ3とシステム共通点の多さを考えると、なぜドラクエ3と1のリメイクでこれほど楽しさの感じ方に差が出たのか？不思議です。

たぶんドラクエ1リメイクのレベルデザインが肌に合わなかっただけだろう、と予想してます。もしかするとLv上げまくったら程よい感じになったのかも？？とは思いますが、今はもう嫌なので、いつか暇だったらやるかも程度です。