CRC-32

CRC-32 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Implement the Cyclic Redundancy Check from ISO 3309, ITU-T V.42, Gzip and PNG. Algorithms are described on Computation of CRC in Wikipedia. This variant of CRC-32 uses LSB-first order, sets the initial CRC to FFFFFFFF₁₆, and complements the final CRC.

Use this CRC-32 to generate a checksum for the following ASCII encoded string of bytes: "The quick brown fox jumps over the lazy dog"

C

Library

Using zlib's crc32: <lang c>#include <stdio.h>

1. include <string.h>
2. include <zlib.h>

int main() { char *s = "The quick brown fox jumps over the lazy dog"; printf("%lX\n", crc32(0, (void*)s, strlen(s)));

return 0; }</lang>

Implementation

This code is a translation from Ruby, with an adjustment to use 32-bit integers. This code happens to resemble the examples from RFC 1952 section 8 and from PNG annex D, because those examples use an identical table.

<lang c>#include <inttypes.h>

1. include <stdio.h>
2. include <string.h>

uint32_t rc_crc32(uint32_t crc, const char *buf, size_t len) { static uint32_t table[256]; static int have_table = 0; uint32_t rem, octet; int i, j; const char *p, *q;

/* This check is not thread safe; there is no mutex. */ if (have_table == 0) { /* Calculate CRC table. */ for (i = 0; i < 256; i++) { rem = i; /* remainder from polynomial division */ for (j = 0; j < 8; j++) { if (rem & 1) { rem >>= 1; rem ^= 0xedb88320; } else rem >>= 1; } table[i] = rem; } have_table = 1; }

crc = ~crc; q = buf + len; for (p = buf; p < q; p++) { octet = *p; /* Cast to unsigned octet. */ crc = (crc >> 8) ^ table[(crc & 0xff) ^ octet]; } return ~crc; }

int main() { char *s = "The quick brown fox jumps over the lazy dog"; printf("%" PRIX32 "\n", rc_crc32(0, (void*)s, strlen(s)));

return 0; }</lang>

Go

Library

<lang go>package main

import (

   "fmt"
   "hash/crc32"

)

func main() {

   s := []byte("The quick brown fox jumps over the lazy dog")
   result := crc32.ChecksumIEEE(s)
   fmt.Printf("%X\n", result)

}</lang> output

414FA339

Implementation

<lang go>package main

import "fmt"

var table [256]uint32

func init() {

   for i := range table {
       word := uint32(i)
       for j := 0; j < 8; j++ {
           if word&1 == 1 {
               word = (word >> 1) ^ 0xedb88320
           } else {
               word >>= 1
           }
       }
       table[i] = word
   }

}

func crc32(s string) uint32 {

   crc := ^uint32(0)
   for i := 0; i < len(s); i++ {
       crc = table[byte(crc)^s[i]] ^ (crc >> 8)
   }
   return ^crc

}

func main() {

   fmt.Printf("%0x\n", crc32("The quick brown fox jumps over the lazy dog"))

}</lang> Output:

414fa339

Icon and Unicon

There is no library function for this so we implement one. Icon/Unicon binary operations apply to large integers so we need to mask to the desired unsigned word size. This also only applies to full bytes. <lang Icon>link hexcvt,printf

procedure main()

  s := "The quick brown fox jumps over the lazy dog"
  a := "414FA339"
  printf("crc(%i)=%s - implementation is %s\n",
         s,r := crc32(s),if r == a then "correct" else "in error")

end

procedure crc32(s) #: return crc-32 (ISO 3309, ITU-T V.42, Gzip, PNG) of s static crcL,mask initial {

  crcL := list(256)                            # crc table
  p := [0,1,2,4,5,7,8,10,11,12,16,22,23,26]    # polynomial terms 
  mask := 2^32-1                               # word size mask   
  every (poly := 0) := ior(poly,ishift(1,31-p[1 to *p]))
  every c := n := 0 to *crcL-1 do {            # table 
     every 1 to 8 do 
        c := iand(mask, 
                  if iand(c,1) = 1 then
                     ixor(poly,ishift(c,-1)) 
                  else 
                     ishift(c,-1)
                 )
     crcL[n+1] := c
     }
  }
  
  crc := ixor(0,mask)                          # invert bits
  every crc := iand(mask,
                    ixor(crcL[iand(255,ixor(crc,ord(!s)))+1],ishift(crc,-8)))               
  return hexstring(ixor(crc,mask))             # return hexstring

end</lang>

Library: Icon Programming Library

hexcvt.icnprovides hex and hexstring printf.icnprovides formatting

Output:

crc("The quick brown fox jumps over the lazy dog")=414FA339 - implementation is correct

J

<lang j> ((i.32) e. 32 26 23 22 16 12 11 10 8 7 5 4 2 1 0) 128!:3 'The quick brown fox jumps over the lazy dog' _3199229127</lang>

Other possible representations of this result:

<lang j> (2^32x)|((i.32) e. 32 26 23 22 16 12 11 10 8 7 5 4 2 1 0) 128!:3 'The quick brown fox jumps over the lazy dog' 1095738169

  require'convert'
  hfd (2^32x)|((i.32) e. 32 26 23 22 16 12 11 10 8 7 5 4 2 1 0) 128!:3 'The quick brown fox jumps over the lazy dog'

414FA339</lang>

PHP

PHP has a built-in function crc32.

<lang php>printf("%x\n", crc32("The quick brown fox jumps over the lazy dog"));</lang>

414fa339

Python

Library

<lang python>>>> import zlib >>> hex(zlib.crc32('The quick brown fox jumps over the lazy dog')) '0x414fa339'</lang>

Ruby

<lang 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")

1. => 0x414fa339</lang>

Tcl

<lang tcl>package require Tcl 8.6

set data "The quick brown fox jumps over the lazy dog" puts [format "%x" [zlib crc32 $data]]</lang> Which produces this output:

414fa339

Alternatively, with older versions of Tcl:

Library: Tcllib (Package: crc32)

<lang tcl>package require crc32 puts [format "%x" [crc::crc32 $data]]</lang> With the same input data, it produces identical output.