configurable general CRC calcurator for mruby
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
contrib/libcrcea
mrblib
src
test
.travis.yml
.travis_config.rb
LICENSE
README.md
Rakefile
mrbgem.rake
test_config.rb

README.md

mruby-crc - A general CRC calcurator for mruby

利用者が定義可能な汎用 CRC 生成器です。

動的に定義可能な項目は次の通りです:

  • ビット長: 1 〜 64 ビット
  • 生成多項式: 任意の整数値
  • CRC の初期値: 任意の整数値
  • 入力ビットの順序: 順送り・逆送り (normal input / reflect input)
  • 出力ビットの順序: 順送り・逆送り (normal output / reflect output)
  • 出力の XOR 値: 任意の整数値
  • 計算アルゴリズム: bit-by-bit, bit-by-bit-fast, halfbyte-table, standard-table, slicing-by-4/8/16

必要なもの

  • C99 対応コンパイラ
  • mruby-1.2 または最新版 (?)

MRB_INT16MRB_INT64 が定義された場合の挙動の変化について

MRB_INT64 が定義された場合は、CRC#finish などの値が常に整数値となります。

MRB_INT64 が未定義の場合は、MRB_INT_MAX を越えた場合は CRC#finish などの値が hexdigest された文字列となります。

定義・未定義にかかわらず、CRC.new メソッドの引数 polynomial initial_crc xor_output には hexdigest されたものと同等の文字列を与えることが出来ます。

CRC32C = CRC.new(32, "1edc6f41", 0, true, true, ~0)

p CRC32C.crc("123456789")
## => 3808858755 (MRB_INT64 が定義された場合)
## => "e3069283" (MRB_INT64 が未定義の場合)

p CRC32C.crc("123456789" * 6)
## => 1521416889 (MRB_INT16 が未定義の場合)
## => "5aaefab9" (MRB_INT16 が定義された場合)

簡易 API 案内

  • CRC.new(bitsize, polynomial, initialcrc = 0, refin = true, refout = true, xoroutput = ~0, algorithm = CRC::STANDARD_TABLE) -> CRC generator class
  • CRC.new(bitsize, polynomial, initialcrc: 0, reflectin: true, reflectout: true, xoroutput: ~0, algorithm: CRC::STANDARD_TABLE) -> CRC generator class
  • CRC.new(previous_crc = 0, input_length = 0) -> crc generator object
  • CRC[seq, previous_crc = 0, input_length = 0] -> crc generator object
  • crc.update(seq) -> self
  • crc.reset(previous_crc = 0, input_length = 0) -> self
  • crc.finish -> crc integer
  • crc.digest -> binary digested string (liked as Digest#digest)
  • crc.hexdigest -> hexa-decimal digested string (liked as Digest#hexdigest)

既定で使われるアルゴリズムの変更

build_config.rbconf.cc.defines に追加することで、CRC.new のアルゴリズム指定を省略した場合の挙動を変更できます。 何も指定しない場合は、CRC_DEFAULT_STANDARD_TABLE が指定されたものとして扱われます。

  • CRC_DEFAULT_BITBYBIT
  • CRC_DEFAULT_BITBYBIT_FAST
  • CRC_DEFAULT_HALFBYTE_TABLE
  • CRC_DEFAULT_STANDARD_TABLE
  • CRC_DEFAULT_SLICING_BY_4
  • CRC_DEFAULT_SLICING_BY_8
  • CRC_DEFAULT_SLICING_BY_16

build_config.rb の例:

MRuby::Build.new("host") do |conf|
  .....
  conf.cc.defines << "CRC_DEFAULT_SLICING_BY_16"
  .....
end

内部処理の整数値型の固定

mruby-crc は CRC のビット長によって内部の整数値型を調整しています。具体的には、uint8_t uint16_t uint32_t uint64_t のためにそれぞれの関数を生成するようになっています。

この mruby-crc 内部で使われる整数値型を固定して僅かでもバイナリサイズを少なくしたい場合、build_config.rb 内で CRC_ONLY_INT*** を定義します。

定義名は CRC_ONLY_INT8 CRC_ONLY_INT16 CRC_ONLY_INT32 CRC_ONLY_INT64 のみが有効です。

MRuby::Build.new("host") do |conf|
  .....
  conf.cc.defines << "CRC_ONLY_INT32"
  .....
end

整数値レジスタが32ビット長であるプロセッサの場合、CRC_ONLY_INT64 を定義すると CRC-32 の計算であっても uint64_t による計算となり、計算速度が数倍遅くなります。

また、CRC_ONLY_INT8 を定義した場合、8ビット長を超える CRC の定義は出来なくなります。

ルックアップテーブルのメモリ確保量

CRC を計算する時に高速化するため、入力バイト値に対する変化を予め求めておくわけですが、この際に専有するメモリの量は algorithm の値によって決定されます。

このテーブルの確保・初期化が行われる時機は、CRC を最初に計算する直前となります。 CRC.new した段階ではメモリの確保も初期化も行われません。

algorithm メモリ使用量の求め方 (CRC-32 の場合) 確保されるメモリバイト数 (CRC-32 の場合)
CRC::BITBYBIT (N/A) 0 bytes
CRC::BITBYBIT_FAST (N/A) 0 bytes
CRC::HALFBYTE_TABLE sizeof(uint32_t[16]) 64 bytes
CRC::STANDARD_TABLE sizeof(uint32_t[256]) 1024 bytes (1 KiB)
CRC::SLICING_BY_4 sizeof(uint32_t[4][256]) 4096 bytes (4 KiB)
CRC::SLICING_BY_8 sizeof(uint32_t[8][256]) 8192 bytes (8 KiB)
CRC::SLICING_BY_16 sizeof(uint32_t[16][256]) 16384 bytes (16 KiB)

Specification