class CRC
This is a generic CRC
calculator.
When you want to use CRC-32 model, there are following ways:
-
Calculate CRC-32'd value at direct:
CRC.crc32("123456789") # => 3421780262
-
Calculate CRC-32'd hex-digest at direct:
CRC::CRC32.hexdigest("123456789") # => "CBF43926"
-
Streaming process:
crc32 = CRC::CRC32.new # => #<CRC::CRC32:00000000> IO.foreach("/boot/kernel/kernel", nil, 262144, mode: "rb") do |s| crc32 << s end p crc32 # => #<CRC::CRC32:6A632AA5> p crc32.crc # => 1784883877 p crc32.digest # => "jc*\xA5" p crc32.hexdigest # => "6A632AA5"
* * * * * * * *
Pure ruby implemented generic CRC
calculator. It's used slice-by-16 algorithm with byte-order free. This is based on the Intel's slice-by-eight algorithm.
It's faster than about 50% (CRC-32) and about 30% (CRC-64) of lookup-table algorithm. But need more memory.
reference:
-
xz-utils
-
xz-5.2.2/src/liblzma/check/crc32_fast.c
-
xz-5.2.2/src/liblzma/check/crc32_tablegen.c
Constants
- ALGORITHM_BITBYBIT
- ALGORITHM_BITBYBIT_FAST
- ALGORITHM_HALFBYTE_TABLE
- ALGORITHM_SLICING_BY_16
- ALGORITHM_SLICING_BY_4
- ALGORITHM_SLICING_BY_8
- ALGORITHM_STANDARD_TABLE
- CRC
- Calcurator
NOTE: “Calcurator” は typo ですが、後方互換のため一時的に残します。 TODO:
CRC::Calcurator
はいずれ削除されます。- IMPLEMENT
- LIST
- MODEL_TABLE
- SLICING_SIZE
- VERSION
Attributes
size[RW]
state[RW]
Public Class Methods
crc(modelname, seq, crc = nil)
click to toggle source
# File lib/crc.rb, line 256 def crc(modelname, seq, crc = nil) lookup(modelname).crc(seq, crc) end
digest(modelname, seq, crc = nil)
click to toggle source
# File lib/crc.rb, line 260 def digest(modelname, seq, crc = nil) lookup(modelname).digest(seq, crc) end
dump_to_c(func_name = nil, header_name = nil, source_name = nil, indent: 4, visible: true, algorithm: ALGORITHM_SLICING_BY_16)
click to toggle source
# File lib/crc/codegen.rb, line 14 def self.dump_to_c(func_name = nil, header_name = nil, source_name = nil, indent: 4, visible: true, algorithm: ALGORITHM_SLICING_BY_16) func_name ||= self.to_s.slice(/\w+$/).downcase #func_name ||= self.name.gsub(/[\W]+/, "_").gsub(/_{2,}/, "_").gsub(/^_|_$/, "").downcase header_name ||= "#{func_name}.h" source_name ||= "#{func_name}.c" indentunit = " " * Integer(indent.to_i) indent = ->(level) { indentunit * level } visibility = visible ? "" : "static " case when bitsize <= 8 type = "uint8_t" sizeof = 1 suffix = "u" when bitsize <= 16 type = "uint16_t" sizeof = 2 suffix = "u" when bitsize <= 32 type = "uint32_t" sizeof = 4 suffix = "ul" else type = "uint64_t" sizeof = 8 suffix = "ull" end typesize = sizeof * 8 alignedbytes = (bitsize + 7) / 8 alignedbits = (bitsize + 7) & ~0x07 # 8 bit alignmented bitsize bitreflect = func_name + "_bitreflect" hexnum = ->(n) { "0x%0#{sizeof * 2}X%s" % [n, suffix] } hexbyte = ->(n) { "0x%02Xu" % n } if reflect_input? getleadbyte = ->(expr, off = 0) { "(uint8_t)(#{expr} >> %2d)" % (off * 8) } getheadbit_from_byte = ->(expr, off = 0) { "((#{expr} >> #{off}) & 1)" } getleadbit = ->(expr, off = 0, width = 1) { "((%s >> %2d) & 0x%02X)" % [expr, off, ~(~0 << width)] } slideinput = ->(expr) { "#{expr}" } slidestate1 = ->(expr) { "(#{expr} >> 1)" } slidestate4 = ->(expr) { "(#{expr} >> 4)" } slidestate8 = ->(expr) { "(#{expr} >> 8)" } slideslicing = ->(expr) { "(#{expr} >> #{algorithm * 8})" } padding = depadding = nil workpoly = hexnum[Utils.bitreflect(polynomial, bitsize)] if algorithm >= 0 table = Utils.build_reflect_table(bitsize, polynomial, true, slice: (algorithm < 1 ? 1 : algorithm)) end else getleadbyte = ->(expr, off = 0) { "(uint8_t)(#{expr} >> %2d)" % (alignedbits - (off + 1) * 8) } getheadbit_from_byte = ->(expr, off = 0) { "((#{expr} >> #{8 - (off + 1)}) & 1)" } getleadbit = ->(expr, off = 0, width = 1) { "((%s >> %2d) & 0x%02X)" % [expr, (alignedbits - (off + 1) - (width - 1)), ~(~0 << width)] } slideinput = ->(expr) { "((#{type})#{expr} << #{alignedbits - 8})" } slidestate1 = ->(expr) { "(#{expr} << 1)" } slidestate4 = ->(expr) { "(#{expr} << 4)" } slidestate8 = ->(expr) { "(#{expr} << 8)" } slideslicing = ->(expr) { "(#{expr} << #{algorithm * 8})" } if (pad = (alignedbits - bitsize)) > 0 padding = " << #{pad}" depadding = " >> #{pad}" workpoly = "#{func_name.upcase}_POLYNOMIAL << #{pad}" else padding = depadding = nil workpoly = "#{func_name.upcase}_POLYNOMIAL" end if algorithm >= 0 table = Utils.build_table(bitsize, polynomial, true, slice: (algorithm < 1 ? 1 : algorithm)) end end case algorithm when ALGORITHM_BITBYBIT comment = " /* bit reflected */" if reflect_input? prepare = <<-PREPARE_BITBYBIT static const #{type} workpoly = #{workpoly};#{comment} PREPARE_BITBYBIT update = <<-UPDATE_BITBYBIT for (; p < pp; p ++) { int i; s ^= #{slideinput["*p"]}; for (i = 0; i < 8; i ++) { s = #{slidestate1["s"]} ^ (workpoly & -(#{type})#{getleadbit["s"]}); } } UPDATE_BITBYBIT when ALGORITHM_BITBYBIT_FAST comment = " /* bit reflected */" if reflect_input? tspc = " " * type.size prepare = <<-PREPARE_BITBYBIT_FAST static const #{type} workpoly = #{workpoly};#{comment} static const #{type} g0 = workpoly, #{tspc} g1 = #{slidestate1["g0"]} ^ (workpoly & -(#{type})#{getleadbit["g0"]}), #{tspc} g2 = #{slidestate1["g1"]} ^ (workpoly & -(#{type})#{getleadbit["g1"]}), #{tspc} g3 = #{slidestate1["g2"]} ^ (workpoly & -(#{type})#{getleadbit["g2"]}), #{tspc} g4 = #{slidestate1["g3"]} ^ (workpoly & -(#{type})#{getleadbit["g3"]}), #{tspc} g5 = #{slidestate1["g4"]} ^ (workpoly & -(#{type})#{getleadbit["g4"]}), #{tspc} g6 = #{slidestate1["g5"]} ^ (workpoly & -(#{type})#{getleadbit["g5"]}), #{tspc} g7 = #{slidestate1["g6"]} ^ (workpoly & -(#{type})#{getleadbit["g6"]}); PREPARE_BITBYBIT_FAST update = <<-UPDATE_BITBYBIT_FAST for (; p < pp; p ++) { const uint8_t s1 = #{getleadbit["s", 0, 8]} ^ *p; s = #{slidestate8["s"]} ^ (g7 & -(#{type})#{getheadbit_from_byte["s1", 0]}) ^ (g6 & -(#{type})#{getheadbit_from_byte["s1", 1]}) ^ (g5 & -(#{type})#{getheadbit_from_byte["s1", 2]}) ^ (g4 & -(#{type})#{getheadbit_from_byte["s1", 3]}) ^ (g3 & -(#{type})#{getheadbit_from_byte["s1", 4]}) ^ (g2 & -(#{type})#{getheadbit_from_byte["s1", 5]}) ^ (g1 & -(#{type})#{getheadbit_from_byte["s1", 6]}) ^ (g0 & -(#{type})#{getheadbit_from_byte["s1", 7]}); } UPDATE_BITBYBIT_FAST when ALGORITHM_HALFBYTE_TABLE table = table[0] if reflect_input? table = 16.times.map { |i| table[i * 16] } else table = 16.times.map { |i| table[i] } end prepare = <<-PREPARE_HALFBYTE_TABLE static const #{type} table[16] = { #{Aux.export_slicing_table(table, " ", 4, nil, nil, nil, nil, sizeof > 2 ? 4 : 8, &hexnum)} }; PREPARE_HALFBYTE_TABLE update = <<-UPDATE_HALFBYTE_TABLE for (; p < pp; p ++) { s ^= #{slideinput["(#{type})*p"]}; s = table[#{getleadbit["s", 0, 4]}] ^ #{slidestate4["s"]}; s = table[#{getleadbit["s", 0, 4]}] ^ #{slidestate4["s"]}; } UPDATE_HALFBYTE_TABLE when ALGORITHM_STANDARD_TABLE prepare = <<-PREPARE_STANDARD_TABLE static const #{type} table[256] = { #{Aux.export_slicing_table(table[0], " ", 4, nil, nil, nil, nil, sizeof > 2 ? 4 : 8, &hexnum)} }; PREPARE_STANDARD_TABLE update = <<-UPDATE_STANDARD_TABLE for (; p < pp; p ++) { s ^= #{slideinput["(#{type})*p"]}; s = table[(uint8_t)#{getleadbit["s", 0, 8]}] ^ #{slidestate8["s"]}; } UPDATE_STANDARD_TABLE when ALGORITHM_SLICING_BY_4, ALGORITHM_SLICING_BY_8, ALGORITHM_SLICING_BY_16, 2 .. 999 if algorithm > 100 slicing_format = "table[%3d][p[%3d] %20s]" else slicing_format = "table[%2d][p[%2d] %20s]" end slicing = algorithm.times.map { |off| ioff = (algorithm - 1) - off slicing_format % [ ioff, off, off >= alignedbytes ? nil : "^ #{getleadbyte["s", off]}"] } if algorithm < alignedbytes slicing.insert 0, slideslicing["s"] end slicing = slicing.join(" ^\n ") prepare = <<-PREPARE_SLICING_TABLE static const #{type} table[#{algorithm}][256] = { #{Aux.export_slicing_table(table, " ", 4, nil, nil, "{", "}", sizeof > 2 ? 4 : 8, &hexnum)} }; PREPARE_SLICING_TABLE update = <<-UPDATE_SLICING_TABLE const uint8_t *ppby = p + (len / #{algorithm} * #{algorithm}); for (; p < ppby; p += #{algorithm}) { s = #{slicing}; } for (; p < pp; p ++) { s = table[0][*p ^ #{getleadbyte["s"]}] ^ #{slidestate8["s"]}; } UPDATE_SLICING_TABLE else raise ArgumentError, "wrong algorithm code - #{algorithm}" end if reflect_output? ^ reflect_input? slideleft = (typesize == bitsize) ? nil : "\n" << <<-SLIDELEFT.chomp! n <<= #{typesize - bitsize}; SLIDELEFT swapby32 = (sizeof < 8) ? nil : "\n" << <<-SWAPBY32.chomp! n = ((n & 0X00000000FFFFFFFF#{suffix}) << 32) | (n >> 32); SWAPBY32 swapby16 = (sizeof < 4) ? nil : "\n" << <<-SWAPBY16.chomp! n = ((n & 0x#{"0000FFFF" * (sizeof / 4)}#{suffix}) << 16) | ((n >> 16) & 0x#{"0000FFFF" * (sizeof / 4)}#{suffix}); SWAPBY16 swapby8 = (sizeof < 2) ? nil : "\n" << <<-SWAPBY8.chomp! n = ((n & 0x#{"00FF" * (sizeof / 2)}#{suffix}) << 8) | ((n >> 8) & 0x#{"00FF" * (sizeof / 2)}#{suffix}); SWAPBY8 func_bitreflect = "\n" << <<-BITREFLECT static #{type} #{bitreflect}(#{type} n) {#{slideleft}#{swapby32}#{swapby16}#{swapby8} n = ((n & 0x#{"0F" * sizeof}#{suffix}) << 4) | ((n >> 4) & 0x#{"0F" * sizeof}#{suffix}); n = ((n & 0x#{"33" * sizeof}#{suffix}) << 2) | ((n >> 2) & 0x#{"33" * sizeof}#{suffix}); n = ((n & 0x#{"55" * sizeof}#{suffix}) << 1) | ((n >> 1) & 0x#{"55" * sizeof}#{suffix}); return n; } BITREFLECT else bitreflect = nil end { header: <<-CHEADER, source: <<-CSOURCE } /* #{Aux.dump_banner(" *", "#{self.name}{#{to_str}}", algorithm)} */ #ifndef #{func_name.upcase}_H__ #define #{func_name.upcase}_H__ 1 #include <stdlib.h> #include <stdint.h> #define #{func_name.upcase}_TYPE #{type} #define #{func_name.upcase}_BITSIZE #{bitsize} #define #{func_name.upcase}_BITMASK #{hexnum[bitmask]} #define #{func_name.upcase}_POLYNOMIAL #{hexnum[polynomial]} #define #{func_name.upcase}_INITIAL_CRC #{hexnum[initial_crc]} #define #{func_name.upcase}_XOR_OUTPUT #{hexnum[xor_output]} #define #{func_name.upcase}_REFLECT_INPUT #{reflect_input? ? 1 : 0} #define #{func_name.upcase}_REFLECT_OUTPUT #{reflect_output? ? 1 : 0} #ifdef __cplusplus extern "C" #{visibility}#{type} #{func_name}(const void *ptr, size_t len, #{type} crc = #{func_name.upcase}_INITIAL_CRC); #else #{visibility}#{type} #{func_name}(const void *ptr, size_t len, #{type} crc); #endif #endif /* #{func_name.upcase}_H__ */ CHEADER /* #{Aux.dump_banner(" *", "#{self.name}{#{to_str}}", algorithm)} */ #include "#{header_name}" #{func_bitreflect} #{visibility}#{type} #{func_name}(const void *ptr, size_t len, #{type} crc) { #{prepare} #{type} s = ((#{bitreflect}(crc) & #{func_name.upcase}_BITMASK) ^ #{func_name.upcase}_XOR_OUTPUT)#{padding}; const uint8_t *p = (const uint8_t *)ptr; const uint8_t *pp = p + len; #{update} return #{bitreflect}((s#{depadding}) & #{func_name.upcase}_BITMASK) ^ #{func_name.upcase}_XOR_OUTPUT; } CSOURCE end
dump_to_javascript(class_name = nil)
click to toggle source
# File lib/crc/codegen.rb, line 539 def self.dump_to_javascript(class_name = nil) class_name ||= self.to_s.slice(/\w+$/).downcase name = class_name.split("::") name.map! { |nm| nm.gsub!(/[\W]+/m, "_"); nm.sub!(/^_+/, ""); nm } case when bitsize <= 8 sizeof = 1 when bitsize <= 16 sizeof = 2 when bitsize <= 32 sizeof = 4 else sizeof = 8 end pack = "" typebits = sizeof * 8 hexnum = ->(n) { "0x%0*X" % [sizeof * 2, n] } if reflect_input? table1 = Utils.build_reflect_table(bitsize, polynomial, slice: 16) headstate = "(s & 0xFF)" slidestate = "(s >>> 8)" slicing = ->(off) { t = "t%X" % (15 - off) getbyte = off > 0 ? "+ %2d" % off : "" shiftstate = off < sizeof ? "^ (s %6s) & 0xFF" % (off > 0 ? ">>> %2d" % (off * 8) : "") : "" "%s[(0xFF & seq.charCodeAt(i %4s)) %19s]" % [t, getbyte, shiftstate] } else table1 = Utils.build_table(bitsize, polynomial, true, slice: 16) bitpad = typebits - bitsize #table1.each { |t| t.map! { |tt| tt << bitpad } } headstate = "((s >>> #{typebits - 8}) & 0xFF)" slidestate = "((s & #{hexnum[~(~0 << typebits) >> 8]}) << 8)" slicing = ->(off) { t = "t%X" % (15 - off) getbyte = off > 0 ? "+ %2d" % off : "" shiftstate = off < sizeof ? "^ (s %6s) & 0xFF" % (off + 1 < sizeof ? ">>> %2d" % ((sizeof - off) * 8 - 8) : "") : "" "%s[(0xFF & seq.charCodeAt(i %4s)) %19s]" % [t, getbyte, shiftstate] } end typename = name.join(".") code = <<-EOS /* #{Aux.dump_banner(" *", "#{self.name}{#{to_str}}", ALGORITHM_SLICING_BY_16)} * * Required ECMASCript version: 6th edition * * *** IMPORTANT BUG! *** * * This can not be calculated correctly, * if string included with 0x100+ codepointed character. */ "use strict"; /* * #{typename}(prevcrc = null) * #{typename}(seq, prevcrc = null) * new #{typename}(prevcrc = null) * new #{typename}(seq, prevcrc = null) */ (function(root, undefined) { if (typeof(module) != "undefined") { // case node-js root = global; } var BITSIZE = #{bitsize}; var BITMASK = #{hexnum[bitmask]} >>> 0; var POLYNOMIAL = #{hexnum[polynomial]} >>> 0; var INITIAL_CRC = #{hexnum[initial_crc]} >>> 0; var REFLECT_INPUT = #{reflect_input?.inspect}; var REFLECT_OUTPUT = #{reflect_output?.inspect}; var XOR_OUTPUT = #{hexnum[xor_output]} >>> 0; var #{typename} = function() { if(!(this instanceof #{typename})) { return new #{typename}(...arguments).crc; } var seq, prevcrc; switch (arguments.length) { case 0: seq = null; prevcrc = null; break; case 1: if (typeof(arguments[0]) == "string") { seq = arguments[0]; } else { prevcrc = arguments[0]; } break; case 2: seq = arguments[0]; prevcrc = arguments[1]; break; default: throw `wrong number of argument (given ${arguments.size}, expect 0..2)`; } this.reset(prevcrc); if (seq) { this.update(seq); } }; var proto = #{typename}.prototype; proto.reset = function(prevcrc = null) { this.state = #{typename}.setup(prevcrc || INITIAL_CRC); return this; }; proto.update = function(seq) { this.state = #{typename}.update(seq, this.state); return this; }; // proto.operator << = proto.update; proto.finish = function() { return #{typename}.finish(this.state); }; Object.defineProperty(proto, "crc", { get: proto.finish }); Object.defineProperty(proto, "hexdigest", { get: function() { var s = this.crc.toString(16); for (var i = s.length; i < #{sizeof * 2}; i ++) { s = "0" + s; } return s; } }); proto.toString = function() { return `#<#{typename}:${this.hexdigest}>`; }; #{typename}.setup = function(crc = INITIAL_CRC) { return #{ s = "(BITMASK & crc ^ XOR_OUTPUT)" if reflect_output? ^ reflect_input? s = "bitreflect#{s}" end if !reflect_input? && typebits > bitsize s << " << #{typebits - bitsize}" end s }; }; #{typename}.init = #{typename}.setup; #{typename}.finish = function(state) { return (#{ if !reflect_input? && typebits > bitsize state = "(state >>> #{typebits - bitsize})" else state = "state" end if reflect_output? ^ reflect_input? "bitreflect(BITMASK & #{state} ^ XOR_OUTPUT)" else "BITMASK & #{state} ^ XOR_OUTPUT" end }) >>> 0; }; /* * update(seq, state) -> state */ #{typename}.update = function(seq, s) { var i = 0; var ii = seq.length; var ii16 = ii & ~15; var t0 = TABLE[ 0], t1 = TABLE[ 1], t2 = TABLE[ 2], t3 = TABLE[ 3], t4 = TABLE[ 4], t5 = TABLE[ 5], t6 = TABLE[ 6], t7 = TABLE[ 7], t8 = TABLE[ 8], t9 = TABLE[ 9], tA = TABLE[10], tB = TABLE[11], tC = TABLE[12], tD = TABLE[13], tE = TABLE[14], tF = TABLE[15]; for (; i < ii16; i += 16) { s = #{slicing[ 0]} ^ #{slicing[ 1]} ^ #{slicing[ 2]} ^ #{slicing[ 3]} ^ #{slicing[ 4]} ^ #{slicing[ 5]} ^ #{slicing[ 6]} ^ #{slicing[ 7]} ^ #{slicing[ 8]} ^ #{slicing[ 9]} ^ #{slicing[10]} ^ #{slicing[11]} ^ #{slicing[12]} ^ #{slicing[13]} ^ #{slicing[14]} ^ #{slicing[15]}; } for (; i < ii; i ++) { s = t0[(0xFF & seq.charCodeAt(i)) ^ #{headstate}] ^ #{slidestate} } return s; } #{typename}.crc = function(seq, initcrc = INITIAL_CRC) { return #{typename}.finish(#{typename}.update(seq, #{typename}.setup(initcrc))); }; #{typename}.hexdigest = function(seq, initcrc = INITIAL_CRC) { var s = #{typename}.crc(seq, initcrc).toString(16); for (var i = s.length; i < #{sizeof * 2}; i ++) { s = "0" + s; } return s; }; EOS if reflect_output? ^ reflect_input? code << <<-EOS #{typename}.bitreflect = function(n) { EOS if typebits > bitsize code << <<-EOS n <<= #{typebits - bitsize} EOS end if typebits > 32 code << <<-EOS n = ((n >>> 32) & 0x00000000ffffffff) | ((n & 0x00000000ffffffff) << 32) EOS end if typebits > 16 code << <<-EOS n = ((n >>> 16) & 0x#{"0000ffff" * (sizeof / 4)}) | ((n & 0x#{"0000ffff" * (sizeof / 4)}) << 16) EOS end if typebits > 8 code << <<-EOS n = ((n >>> 8) & 0x#{"00ff" * (sizeof / 2)}) | ((n & 0x#{"00ff" * (sizeof / 2)}) << 8) EOS end code << <<-EOS n = ((n >>> 4) & 0x#{"0f" * sizeof}) | ((n & 0x#{"0f" * sizeof}) << 4) n = ((n >>> 2) & 0x#{"33" * sizeof}) | ((n & 0x#{"33" * sizeof}) << 2) n = ((n >>> 1) & 0x#{"55" * sizeof}) | ((n & 0x#{"55" * sizeof}) << 1) return n; } EOS end code << <<-EOS var TABLE = [ #{Aux.export_slicing_table(table1, " ", 2, nil, nil, "[", "]", sizeof > 2 ? 4 : 8, &hexnum)} ]; root.#{typename} = #{typename}; Object.defineProperty(#{typename}, "BITSIZE", { get: function() { return BITSIZE } }); Object.defineProperty(#{typename}, "BITMASK", { get: function() { return BITMASK } }); Object.defineProperty(#{typename}, "POLYNOMIAL", { get: function() { return POLYNOMIAL } }); Object.defineProperty(#{typename}, "INITIAL_CRC", { get: function() { return INITIAL_CRC } }); Object.defineProperty(#{typename}, "REFLECT_INPUT", { get: function() { return REFLECT_INPUT } }); Object.defineProperty(#{typename}, "REFLECT_OUTPUT", { get: function() { return REFLECT_OUTPUT } }); Object.defineProperty(#{typename}, "XOR_OUTPUT", { get: function() { return XOR_OUTPUT } }); return #{typename}; })(this); EOS ({ source: code }) end
dump_to_ruby(class_name = nil)
click to toggle source
# File lib/crc/codegen.rb, line 275 def self.dump_to_ruby(class_name = nil) class_name ||= self.to_s.slice(/\w+$/) name = class_name.split("::") name.map! { |nm| nm.gsub!(/[\W]+/m, "_"); nm.sub!(/^_+/, ""); nm.sub!(/^[a-z]/) { |m| m.upcase! }; nm } case when bitsize <= 8 sizeof = 1 pack = "C" when bitsize <= 16 sizeof = 2 pack = "n" when bitsize <= 32 sizeof = 4 pack = "N" else sizeof = 8 pack = "Q>" end typebits = sizeof * 8 hexnum = ->(n) { "0x%0*X" % [sizeof * 2, n] } if reflect_input? table1 = Utils.build_reflect_table(bitsize, polynomial, slice: 16) headstate = "(s & 0xFF)" slidestate = "(s >> 8)" slicing = ->(off) { t = "t%X" % (15 - off) getbyte = off > 0 ? "+ %2d" % off : "" shiftstate = off < sizeof ? "^ (s %5s) & 0xFF" % (off > 0 ? ">> %2d" % (off * 8) : "") : "" "%s[seq.getbyte(i %4s) %18s]" % [t, getbyte, shiftstate] } else table1 = Utils.build_table(bitsize, polynomial, true, slice: 16) bitpad = typebits - bitsize headstate = "((s >> #{typebits - 8}) & 0xFF)" slidestate = "((s & #{hexnum[~(~0 << typebits) >> 8]}) << 8)" slicing = ->(off) { t = "t%X" % (15 - off) getbyte = off > 0 ? "+ %2d" % off : "" shiftstate = off < sizeof ? "^ (s %5s) & 0xFF" % (off + 1 < sizeof ? ">> %2d" % ((sizeof - off) * 8 - 8) : "") : "" "%s[seq.getbyte(i %4s) %18s]" % [t, getbyte, shiftstate] } end code = <<-EOS #!ruby # #{Aux.dump_banner("#", "#{self.name}{#{to_str}}", ALGORITHM_SLICING_BY_16)} # # for ruby-1.8 unless String.method_defined?(:getbyte) class String alias getbyte [] end end # for mruby unless Array.method_defined?(:freeze) class Array def freeze self end end end class #{name.join("::")} BITSIZE = #{bitsize} BITMASK = #{hexnum[bitmask]} POLYNOMIAL = #{hexnum[polynomial]} INITIAL_CRC = #{hexnum[initial_crc]} REFLECT_INPUT = #{reflect_input?.inspect} REFLECT_OUTPUT = #{reflect_output?.inspect} XOR_OUTPUT = #{hexnum[xor_output]} attr_accessor :state # # call-seq: # initialize(prevcrc = nil) # def initialize(prevcrc = nil) reset(prevcrc) end def reset(prevcrc = nil) @state = self.class.setup(prevcrc || INITIAL_CRC) self end def update(seq) @state = self.class.update(seq, state) self end alias << update def crc self.class.finish(state) end alias finish crc def digest [crc].pack(#{pack.inspect}) end def hexdigest "%0#{sizeof * 2}X" % crc end def inspect "#<\#{self.class}:\#{hexdigest}>" end def pretty_print(q) q.text inspect end class << self def [](seq, prevcrc = nil) crc = new(prevcrc) crc << seq crc end def setup(crc = INITIAL_CRC) #{ s = "(BITMASK & crc ^ XOR_OUTPUT)" if reflect_output? ^ reflect_input? s = "bitreflect#{s}" end if !reflect_input? && typebits > bitsize s << " << #{typebits - bitsize}" end s } end alias init setup def finish(state) #{ if !reflect_input? && typebits > bitsize state = "(state >> #{typebits - bitsize})" else state = "state" end if reflect_output? ^ reflect_input? "bitreflect(BITMASK & #{state} ^ XOR_OUTPUT)" else "BITMASK & #{state} ^ XOR_OUTPUT" end } end # # call-seq: # update(seq, state) -> state # def update(seq, s) i = 0 ii = seq.bytesize ii16 = ii & ~15 t0 = TABLE[ 0]; t1 = TABLE[ 1]; t2 = TABLE[ 2]; t3 = TABLE[ 3] t4 = TABLE[ 4]; t5 = TABLE[ 5]; t6 = TABLE[ 6]; t7 = TABLE[ 7] t8 = TABLE[ 8]; t9 = TABLE[ 9]; tA = TABLE[10]; tB = TABLE[11] tC = TABLE[12]; tD = TABLE[13]; tE = TABLE[14]; tF = TABLE[15] while i < ii16 s = #{slicing[ 0]} ^ #{slicing[ 1]} ^ #{slicing[ 2]} ^ #{slicing[ 3]} ^ #{slicing[ 4]} ^ #{slicing[ 5]} ^ #{slicing[ 6]} ^ #{slicing[ 7]} ^ #{slicing[ 8]} ^ #{slicing[ 9]} ^ #{slicing[10]} ^ #{slicing[11]} ^ #{slicing[12]} ^ #{slicing[13]} ^ #{slicing[14]} ^ #{slicing[15]} i += 16 end while i < ii s = t0[seq.getbyte(i) ^ #{headstate}] ^ #{slidestate} i += 1 end s end def crc(seq, initcrc = INITIAL_CRC) finish(update(seq, setup(initcrc))) end def digest(seq, initcrc = INITIAL_CRC) [crc(seq, initcrc)].pack(#{pack.inspect}) end def hexdigest(seq, initcrc = INITIAL_CRC) "%0#{sizeof * 2}X" % crc(seq, initcrc) end EOS if reflect_output? ^ reflect_input? code << <<-EOS def bitreflect(n) EOS if typebits > bitsize code << <<-EOS n <<= #{typebits - bitsize} EOS end if typebits > 32 code << <<-EOS n = ((n >> 32) & 0x00000000ffffffff) | ((n & 0x00000000ffffffff) << 32) EOS end if typebits > 16 code << <<-EOS n = ((n >> 16) & 0x#{"0000ffff" * (sizeof / 4)}) | ((n & 0x#{"0000ffff" * (sizeof / 4)}) << 16) EOS end if typebits > 8 code << <<-EOS n = ((n >> 8) & 0x#{"00ff" * (sizeof / 2)}) | ((n & 0x#{"00ff" * (sizeof / 2)}) << 8) EOS end code << <<-EOS n = ((n >> 4) & 0x#{"0f" * sizeof}) | ((n & 0x#{"0f" * sizeof}) << 4) n = ((n >> 2) & 0x#{"33" * sizeof}) | ((n & 0x#{"33" * sizeof}) << 2) n = ((n >> 1) & 0x#{"55" * sizeof}) | ((n & 0x#{"55" * sizeof}) << 1) end EOS end code << <<-EOS end TABLE = [ #{Aux.export_slicing_table(table1, " ", 2, nil, nil, "[", "].freeze", sizeof > 2 ? 4 : 8, &hexnum)} ].freeze end EOS ({ source: code }) end
find(crc, seq, bitsize, polynomial, initstate = [0, ~0, 1], xor = [0, ~0, 1])
click to toggle source
# File lib/crc/finder.rb, line 6 def self.find(crc, seq, bitsize, polynomial, initstate = [0, ~0, 1], xor = [0, ~0, 1]) bitsize0 = bitsize.to_i if bitsize0 < 1 || bitsize0 > 128 raise ArgumentError, "wrong bitsize (expect 1..128, but given #{bitsize})" end bitmask = ~(~0 << bitsize0) crc &= bitmask results = [] poly = Array(polynomial) poly.each do |poly| poly &= bitmask [false, true].each do |refin| [false, true].each do |refout| Array(xor).each do |xormask| xormask &= bitmask Array(initstate).each do |init| init &= bitmask mod = CRC.new(bitsize0, poly, init, refin, refout, xormask) results << mod if mod.crc(seq) == crc end end end end end results end
hexdigest(modelname, seq, crc = nil)
click to toggle source
# File lib/crc.rb, line 264 def hexdigest(modelname, seq, crc = nil) lookup(modelname).hexdigest(seq, crc) end
lookup(modelname)
click to toggle source
# File lib/crc.rb, line 248 def lookup(modelname) modelname1 = modelname.to_s.gsub(/[\W_]+/, "") modelname1.downcase! MODEL_TABLE[modelname1] or raise NameError, "modelname is not matched (for #{modelname})" end
Also aliased as: []
initialize(initial_crc = nil, size = 0)
click to toggle source
# File lib/crc.rb, line 159 def initialize(initial_crc = nil, size = 0) m = get_crc_model @state = m.setup((initial_crc || m.initial_crc).to_i) @size = size.to_i end
new(bitsize, polynomial, initial_crc = 0, reflect_input = true, reflect_output = true, xor_output = ~0, name = nil) → new crc model class (CRC based class)
click to toggle source
new(initial_crc = nil, size = 0) → new crc calculator (CRC instance)
# File lib/crc/_byruby.rb, line 33 def new(bitsize, polynomial, initial_crc = 0, reflect_input = true, reflect_output = true, xor_output = ~0, name = nil) bitsize = bitsize.to_i if bitsize < 1 || bitsize > 64 raise ArgumentError, "wrong bitsize (except 1..64, but given #{bitsize})" end bitmask = ~(~0 << bitsize) polynomial = bitmask & polynomial initial_crc = bitmask & initial_crc xor_output = bitmask & xor_output name = (name.nil? || ((name = String(name)).empty?)) ? nil : name ::Class.new(self) do @bitsize = bitsize @bitmask = bitmask @polynomial = polynomial @initial_crc = initial_crc @table = nil @reflect_input = !!reflect_input @reflect_output = !!reflect_output @xor_output = xor_output @name = name # CRC クラスを普通に派生させた場合でも、CRC.new の基底メソッドが呼ばれるための細工 define_singleton_method(:new, &Class.instance_method(:new).bind(self)) extend CRC::Calculator end end
table()
click to toggle source
# File lib/crc/_byruby.rb, line 228 def table if SLICING_SIZE if reflect_input @table = CRC.build_reflect_table(bitsize, polynomial, slice: SLICING_SIZE) else @table = CRC.build_table(bitsize, polynomial, slice: SLICING_SIZE) end else @table = nil end singleton_class.class_eval "attr_reader :table" @table end
update_with_lookup_table(seq, state)
click to toggle source
# File lib/crc/_byruby.rb, line 87 def update_with_lookup_table(seq, state) t = table[0] if reflect_input String(seq).each_byte do |ch| state = t[state & 0xff ^ ch] ^ (state >> 8) end state else Aux.slide_to_head(bitsize, state, polynomial, bitmask) do |s, poly, csh, head, carries| carries8 = carries >> 7 String(seq).each_byte do |ch| s = t[(s >> csh) ^ ch] ^ ((carries8 & s) << 8) end s end end end
Also aliased as: update
update_with_reference(seq, state)
click to toggle source
# File lib/crc/_byruby.rb, line 63 def update_with_reference(seq, state) if reflect_input poly = CRC.bitreflect(polynomial, bitsize) seq.each_byte do |ch| state ^= ch 8.times { state = (state[0] == 0) ? (state >> 1) : ((state >> 1) ^ poly) } # 8.times { state = (state >> 1) ^ (poly & -state[0]) } # NOTE: ruby だと、分岐したほうが2割くらい高速 end state else Aux.slide_to_head(bitsize, state, polynomial, bitmask) do |s, poly, csh, head, carries| seq.each_byte do |ch| s ^= ch << csh 8.times { s = (s[head] == 0) ? (s << 1) : (((carries & s) << 1) ^ poly) } end s end end end
Also aliased as: update
update_with_slice_by_16(seq, s)
click to toggle source
# File lib/crc/_byruby.rb, line 106 def update_with_slice_by_16(seq, s) tX = table t0 = tX[ 0]; t1 = tX[ 1]; t2 = tX[ 2]; t3 = tX[ 3] t4 = tX[ 4]; t5 = tX[ 5]; t6 = tX[ 6]; t7 = tX[ 7] t8 = tX[ 8]; t9 = tX[ 9]; tA = tX[10]; tB = tX[11] tC = tX[12]; tD = tX[13]; tE = tX[14]; tF = tX[15] i = 0 ii = seq.bytesize ii16 = ii & ~15 if reflect_input case when bitsize > 32 i = 0 while i < ii16 s = tF[seq.getbyte(i ) ^ (s ) & 0xff] ^ tE[seq.getbyte(i + 1) ^ (s >> 8) & 0xff] ^ tD[seq.getbyte(i + 2) ^ (s >> 16) & 0xff] ^ tC[seq.getbyte(i + 3) ^ (s >> 24) & 0xff] ^ tB[seq.getbyte(i + 4) ^ (s >> 32) & 0xff] ^ tA[seq.getbyte(i + 5) ^ (s >> 40) & 0xff] ^ t9[seq.getbyte(i + 6) ^ (s >> 48) & 0xff] ^ t8[seq.getbyte(i + 7) ^ (s >> 56) ] ^ t7[seq.getbyte(i + 8) ] ^ t6[seq.getbyte(i + 9) ] ^ t5[seq.getbyte(i + 10) ] ^ t4[seq.getbyte(i + 11) ] ^ t3[seq.getbyte(i + 12) ] ^ t2[seq.getbyte(i + 13) ] ^ t1[seq.getbyte(i + 14) ] ^ t0[seq.getbyte(i + 15) ] i += 16 end when bitsize > 16 # speed improvement for 32-bits CRC i = 0 while i < ii16 s = tF[seq.getbyte(i ) ^ (s ) & 0xff] ^ tE[seq.getbyte(i + 1) ^ (s >> 8) & 0xff] ^ tD[seq.getbyte(i + 2) ^ (s >> 16) & 0xff] ^ tC[seq.getbyte(i + 3) ^ (s >> 24) ] ^ tB[seq.getbyte(i + 4) ] ^ tA[seq.getbyte(i + 5) ] ^ t9[seq.getbyte(i + 6) ] ^ t8[seq.getbyte(i + 7) ] ^ t7[seq.getbyte(i + 8) ] ^ t6[seq.getbyte(i + 9) ] ^ t5[seq.getbyte(i + 10) ] ^ t4[seq.getbyte(i + 11) ] ^ t3[seq.getbyte(i + 12) ] ^ t2[seq.getbyte(i + 13) ] ^ t1[seq.getbyte(i + 14) ] ^ t0[seq.getbyte(i + 15) ] i += 16 end else # when bitsize <= 16 # speed improvement for 16-bits CRC i = 0 while i < ii16 s = tF[seq.getbyte(i ) ^ (s ) & 0xff] ^ tE[seq.getbyte(i + 1) ^ (s >> 8) ] ^ tD[seq.getbyte(i + 2) ] ^ tC[seq.getbyte(i + 3) ] ^ tB[seq.getbyte(i + 4) ] ^ tA[seq.getbyte(i + 5) ] ^ t9[seq.getbyte(i + 6) ] ^ t8[seq.getbyte(i + 7) ] ^ t7[seq.getbyte(i + 8) ] ^ t6[seq.getbyte(i + 9) ] ^ t5[seq.getbyte(i + 10) ] ^ t4[seq.getbyte(i + 11) ] ^ t3[seq.getbyte(i + 12) ] ^ t2[seq.getbyte(i + 13) ] ^ t1[seq.getbyte(i + 14) ] ^ t0[seq.getbyte(i + 15) ] i += 16 end end (i...ii).each do |n| s = t0[seq.getbyte(n) ^ s & 0xff] ^ (s >> 8) end s else Aux.slide_to_head(bitsize, s, polynomial, bitmask) do |s, poly, csh, head, carries| case when bitsize > 32 sh = 64 - (head + 1) while i < ii16 s <<= sh s = tF[seq.getbyte(i ) ^ (s >> 56) ] ^ tE[seq.getbyte(i + 1) ^ (s >> 48) & 0xff] ^ tD[seq.getbyte(i + 2) ^ (s >> 40) & 0xff] ^ tC[seq.getbyte(i + 3) ^ (s >> 32) & 0xff] ^ tB[seq.getbyte(i + 4) ^ (s >> 24) & 0xff] ^ tA[seq.getbyte(i + 5) ^ (s >> 16) & 0xff] ^ t9[seq.getbyte(i + 6) ^ (s >> 8) & 0xff] ^ t8[seq.getbyte(i + 7) ^ (s ) & 0xff] ^ t7[seq.getbyte(i + 8) ] ^ t6[seq.getbyte(i + 9) ] ^ t5[seq.getbyte(i + 10) ] ^ t4[seq.getbyte(i + 11) ] ^ t3[seq.getbyte(i + 12) ] ^ t2[seq.getbyte(i + 13) ] ^ t1[seq.getbyte(i + 14) ] ^ t0[seq.getbyte(i + 15) ] i += 16 end when bitsize > 16 # speed improvement for 32-bits CRC sh = 32 - (head + 1) while i < ii16 s <<= sh s = tF[seq.getbyte(i ) ^ (s >> 24) ] ^ tE[seq.getbyte(i + 1) ^ (s >> 16) & 0xff] ^ tD[seq.getbyte(i + 2) ^ (s >> 8) & 0xff] ^ tC[seq.getbyte(i + 3) ^ (s ) & 0xff] ^ tB[seq.getbyte(i + 4) ] ^ tA[seq.getbyte(i + 5) ] ^ t9[seq.getbyte(i + 6) ] ^ t8[seq.getbyte(i + 7) ] ^ t7[seq.getbyte(i + 8) ] ^ t6[seq.getbyte(i + 9) ] ^ t5[seq.getbyte(i + 10) ] ^ t4[seq.getbyte(i + 11) ] ^ t3[seq.getbyte(i + 12) ] ^ t2[seq.getbyte(i + 13) ] ^ t1[seq.getbyte(i + 14) ] ^ t0[seq.getbyte(i + 15) ] i += 16 end else # when bitsize <= 16 # speed improvement for 16-bits CRC sh = 16 - (head + 1) while i < ii16 s <<= sh s = tF[seq.getbyte(i ) ^ (s >> 8) ] ^ tE[seq.getbyte(i + 1) ^ (s ) & 0xff] ^ tD[seq.getbyte(i + 2) ] ^ tC[seq.getbyte(i + 3) ] ^ tB[seq.getbyte(i + 4) ] ^ tA[seq.getbyte(i + 5) ] ^ t9[seq.getbyte(i + 6) ] ^ t8[seq.getbyte(i + 7) ] ^ t7[seq.getbyte(i + 8) ] ^ t6[seq.getbyte(i + 9) ] ^ t5[seq.getbyte(i + 10) ] ^ t4[seq.getbyte(i + 11) ] ^ t3[seq.getbyte(i + 12) ] ^ t2[seq.getbyte(i + 13) ] ^ t1[seq.getbyte(i + 14) ] ^ t0[seq.getbyte(i + 15) ] i += 16 end end carries8 = carries >> 7 (i...ii).each do |n| s = t0[(s >> csh) ^ seq.getbyte(n)] ^ ((carries8 & s) << 8) end s end end end
Also aliased as: update
Public Instance Methods
+(crc2)
click to toggle source
# File lib/crc.rb, line 184 def +(crc2) m1 = get_crc_model m2 = crc2.get_crc_model raise ArgumentError, "not a CRC instance (#{crc2.inspect})" unless m2 unless m2.variant_for?(m1) raise ArgumentError, "different CRC model (#{m1.inspect} and #{m2.inspect})" end m1.new(m1.combine(crc, crc2.crc, crc2.size), size + crc2.size) end
==(a)
click to toggle source
Calls superclass method
# File lib/crc.rb, line 194 def ==(a) case a when CRC if variant_for?(a) && state == a.state true else false end when Integer crc == a else super end end
crc()
click to toggle source
# File lib/crc.rb, line 180 def crc get_crc_model.finish(state) end
digest()
click to toggle source
# File lib/crc.rb, line 216 def digest Aux.digest(crc, get_crc_model.bitsize) end
digest!()
click to toggle source
return digest as internal state
# File lib/crc.rb, line 221 def digest! Aux.digest(state, get_crc_model.bitsize) end
file(path)
click to toggle source
# File lib/crc/_file.rb, line 2 def file(path) File.open(path, "rb") do |file| buf = "".b update(buf) while file.read(65536, buf) end self end
hexdigest()
click to toggle source
# File lib/crc.rb, line 225 def hexdigest Aux.hexdigest(crc, get_crc_model.bitsize) end
hexdigest!()
click to toggle source
return hex-digest as internal state
# File lib/crc.rb, line 230 def hexdigest! Aux.hexdigest(state, get_crc_model.bitsize) end
inspect()
click to toggle source
# File lib/crc.rb, line 237 def inspect "\#<#{get_crc_model}:#{hexdigest}>" end
magicdigest()
click to toggle source
# File lib/crc/_magic.rb, line 90 def magicdigest crc.to_magicdigest_for(get_crc_model) end
pretty_inspect(q)
click to toggle source
# File lib/crc.rb, line 241 def pretty_inspect(q) q.text inspect end
reset(initial_crc = nil, size = 0)
click to toggle source
# File lib/crc.rb, line 165 def reset(initial_crc = nil, size = 0) m = get_crc_model @state = m.setup((initial_crc || m.initial_crc).to_i) @size = size.to_i self end
to_a()
click to toggle source
# File lib/crc.rb, line 212 def to_a [crc] end
update(seq)
click to toggle source
# File lib/crc.rb, line 172 def update(seq) @state = get_crc_model.update(seq, state) @size += seq.bytesize self end
Also aliased as: <<