76 lines
3.0 KiB
Ruby
76 lines
3.0 KiB
Ruby
module CRC
|
|
# Divisor is a polynomial of degree 32 with coefficients modulo 2.
|
|
# We store Divisor in a 33-bit Integer; the polynomial is
|
|
# Divisor[32] + Divisor[31] * x + ... + Divisor[0] * x**32
|
|
Divisor = [0, 1, 2, 4, 5, 7, 8, 10, 11, 12, 16, 22, 23, 26, 32] \
|
|
.inject(0) {|sum, exponent| sum + (1 << (32 - exponent))}
|
|
|
|
# This table gives the crc (without conditioning) of every possible
|
|
# _octet_ from 0 to 255. Each _octet_ is a polynomial of degree 7,
|
|
# octet[7] + octet[6] * x + ... + octet[0] * x**7
|
|
# Then remainder = Table[octet] is the remainder from
|
|
# _octet_ times x**32 divided by Divisor,
|
|
# remainder[31] + remainder[30] + ... + remainder[0] * x**31
|
|
Table = Array.new(256) do |octet|
|
|
# Find remainder from polynomial long division.
|
|
# octet[ 7] * x**32 + ... + octet[0] * x**39
|
|
# Divisor[32] * x**0 + ... + Divisor[0] * x**32
|
|
remainder = octet
|
|
(0..7).each do |i|
|
|
# Find next term of quotient. To simplify the code,
|
|
# we assume that Divisor[0] is 1, and we only check
|
|
# remainder[i]. We save remainder, forget quotient.
|
|
if remainder[i].zero?
|
|
# Next term of quotient is 0 * x**(7 - i).
|
|
# No change to remainder.
|
|
else
|
|
# Next term of quotient is 1 * x**(7 - i). Multiply
|
|
# this term by Divisor, then subtract from remainder.
|
|
# * Multiplication uses left shift :<< to align
|
|
# the x**(39 - i) terms.
|
|
# * Subtraction uses bitwise exclusive-or :^.
|
|
remainder ^= (Divisor << i)
|
|
end
|
|
end
|
|
remainder >> 8 # Remove x**32 to x**39 terms.
|
|
end
|
|
|
|
module_function
|
|
|
|
def crc32(string, crc = 0)
|
|
# Pre-conditioning: Flip all 32 bits. Without this step, a string
|
|
# preprended with extra "\0" would have same crc32 value.
|
|
crc ^= 0xffff_ffff
|
|
|
|
# Iterate octets to perform polynomial long division.
|
|
string.each_byte do |octet|
|
|
|
|
# Update _crc_ by continuing its polynomial long division.
|
|
# Our current remainder is old _crc_ times x**8, plus
|
|
# new _octet_ times x**32, which is
|
|
# crc[32] * x**8 + crc[31] * x**9 + ... + crc[8] * x**31 \
|
|
# + (crc[7] + octet[7]) * x**32 + ... \
|
|
# + (crc[0] + octet[0]) * x**39
|
|
#
|
|
# Our new _crc_ is the remainder from this polynomial divided by
|
|
# Divisor. We split the terms into part 1 for x**8 to x**31, and
|
|
# part 2 for x**32 to x**39, and divide each part separately.
|
|
# Then remainder 1 is trivial, and remainder 2 is in our Table.
|
|
|
|
remainder_1 = crc >> 8
|
|
remainder_2 = Table[(crc & 0xff) ^ octet]
|
|
|
|
# Our new _crc_ is sum of both remainders. (This sum never
|
|
# overflows to x**32, so is not too big for Divisor.)
|
|
crc = remainder_1 ^ remainder_2
|
|
end
|
|
|
|
# Post-conditioning: Flip all 32 bits. If we later update _crc_,
|
|
# this step cancels the next pre-conditioning.
|
|
crc ^ 0xffff_ffff
|
|
end
|
|
end
|
|
|
|
printf "0x%08x\n", CRC.crc32("The quick brown fox jumps over the lazy dog")
|
|
# => 0x414fa339
|