CRC-32
From Rosetta Code
You are encouraged to solve this task according to the task description, using any language you may know.
Demonstrate a method of deriving the Cyclic Redundancy Check from within the language. The result should be in accordance with 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 FFFFFFFF16, and complements the final CRC.
For the purpose of this task, generate a CRC-32 checksum for the ASCII encoded string "The quick brown fox jumps over the lazy dog" (without quotes).
Contents |
[edit] Ada
with Ada.Text_IO; use Ada.Text_IO;
with GNAT.CRC32; use GNAT.CRC32;
with Interfaces; use Interfaces;
procedure TestCRC is
package IIO is new Ada.Text_IO.Modular_IO (Unsigned_32);
crc : CRC32;
num : Unsigned_32;
str : String := "The quick brown fox jumps over the lazy dog";
begin
Initialize (crc);
Update (crc, str);
num := Get_Value (crc);
IIO.Put (num, Base => 16); New_Line;
end TestCRC;
- Output:
16#414FA339#
[edit] C
[edit] Library
Using zlib's crc32:
#include <stdio.h>
#include <string.h>
#include <zlib.h>
int main()
{
const char *s = "The quick brown fox jumps over the lazy dog";
printf("%lX\n", crc32(0, (const void*)s, strlen(s)));
return 0;
}
[edit] 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.
#include <inttypes.h>
#include <stdio.h>
#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()
{
const char *s = "The quick brown fox jumps over the lazy dog";
printf("%" PRIX32 "\n", rc_crc32(0, s, strlen(s)));
return 0;
}
[edit] Common Lisp
(ql:quickload :ironclad)
(defun write-seq-base-16 (seq &key ((:stream *standard-output*)
*standard-output*)
&aux (*print-base* 16))
(map nil #'write seq))
(write-seq-base-16
(crypto:digest-sequence 'ironclad:crc32
(crypto:ascii-string-to-byte-array
"The quick brown fox jumps over the lazy dog")))
- Output:
414FA339
[edit] D
import std.stdio, std.digest.crc;
void main() {
"The quick brown fox jumps over the lazy dog"
.crc32Of().crcHexString().writeln();
}
- Output:
414FA339
[edit] Erlang
Using the built-in crc32 implementation.
-module(crc32).
-export([test/0]).
test() ->
io:fwrite("~.16#~n",[erlang:crc32(<<"The quick brown fox jumps over the lazy dog">>)]).
The output is:
16#414FA339
[edit] Factor
Like SHA-1#Factor, but with crc32.
IN: scratchpad USING: checksums checksums.crc32 ;
IN: scratchpad "The quick brown fox jumps over the lazy dog" crc32
checksum-bytes hex-string .
"414fa339"
The implementation is at core/checksums/crc32/crc32.factor.
[edit] Go
[edit] Library
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)
}
output
414FA339
[edit] Implementation
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"))
}
Output:
414fa339
[edit] 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.
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
hexcvt.icnprovides hex and hexstring printf.icnprovides formatting
Output:crc("The quick brown fox jumps over the lazy dog")=414FA339 - implementation is correct
[edit] 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
Other possible representations of this result:
(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
[edit] Java
import java.util.zip.* ;
public class CRCMaker {
public static void main( String[ ] args ) {
String toBeEncoded = new String( "The quick brown fox jumps over the lazy dog" ) ;
CRC32 myCRC = new CRC32( ) ;
myCRC.update( toBeEncoded.getBytes( ) ) ;
System.out.println( "The CRC-32 value is : " + Long.toHexString( myCRC.getValue( ) ) + " !" ) ;
}
}
Output:
The CRC-32 value is : 414fa339 !
[edit] Mathematica
IntegerString[Hash["The quick brown fox jumps over the lazy dog", "CRC32"], 16, 8]
-> "414fa339"
[edit] NetRexx
/* NetRexx */
options replace format comments java crossref symbols binary
import java.util.zip.CRC32
toBeEncoded = String("The quick brown fox jumps over the lazy dog")
myCRC = CRC32()
myCRC.update(toBeEncoded.getBytes())
say "The CRC-32 value is :" Long.toHexString(myCRC.getValue()) "!"
return
Output:
The CRC-32 value is : 414fa339 !
[edit] OCaml
let () =
let s = "The quick brown fox jumps over the lazy dog" in
let crc = Zlib.update_crc 0l s 0 (String.length s) in
Printf.printf "crc: %lX\n" crc
Running this code in interpreted mode:
$ ocaml unix.cma -I +zip zip.cma crc.ml crc: 414FA339
[edit] Perl
#!/usr/bin/perl
use 5.010 ;
use strict ;
use warnings ;
use Digest::CRC qw( crc32 ) ;
my $crc = Digest::CRC->new( type => "crc32" ) ;
$crc->add ( "The quick brown fox jumps over the lazy dog" ) ;
say "The checksum is " . $crc->hexdigest( ) ;
Output:
The checksum is 414fa339
[edit] Perl 6
[edit] Call to native function crc32 in zlib
Library name and types are platform-dependent. As written the solution has been tested on Mac OS X 10.5.8.
Note: Buf $buf would be preferable, but NativeCall does not support Buf parameters, yet.
use NativeCall;
sub crc32(int32 $crc, Str $buf, int32 $len --> int32) is native('/usr/lib/libz.dylib') { * }
my $buf = 'The quick brown fox jumps over the lazy dog';
say crc32(0, $buf, $buf.chars).fmt('%08x');
- Output:
414fa339
[edit] Pure Perl 6
A fairly generic implementation with no regard to execution speed:
sub crc(
Buf $buf,
# polynomial including leading term, default: ISO 3309/PNG/gzip
:@poly = (1,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0,1,1,1,0,1,1,0,1,1,0,1,1,1),
:$n = @poly.end, # degree of polynomial
:@init = 1 xx $n, # initial XOR bits
:@fini = 1 xx $n, # final XOR bits
:@bitorder = 0..7, # default: eat bytes LSB-first
:@crcorder = 0..$n-1, # default: MSB of checksum is coefficient of x⁰
) {
my @bit = ($buf.list X+& (1 X+< @bitorder))».so».Int, 0 xx $n;
@bit[0 .. $n-1] «+^=» @init;
@bit[$_ ..$_+$n] «+^=» @poly if @bit[$_] for 0..@bit.end-$n;
@bit[*-$n.. *-1] «+^=» @fini;
:2[@bit[@bit.end X- @crcorder]];
}
say crc('The quick brown fox jumps over the lazy dog'.encode('ascii')).base(16);
- Output:
414FA339
[edit] PHP
PHP has a built-in function crc32.
printf("%x\n", crc32("The quick brown fox jumps over the lazy dog"));
414fa339
[edit] Python
[edit] Library
zlib.crc32 and binascii.crc32 give identical results.
>>> import zlib
>>> hex(zlib.crc32('The quick brown fox jumps over the lazy dog'))
'0x414fa339'
>>> import binascii
>>> hex(binascii.crc32('The quick brown fox jumps over the lazy dog'))
'0x414fa339'
If you have Python 2.x, these functions might return a negative integer; you would need to use & 0xffffffff to get the same answer as Python 3.x.
[edit] Racket
#lang racket
(define (bytes-crc32 data)
(bitwise-xor
(for/fold ([accum #xFFFFFFFF])
([byte (in-bytes data)])
(for/fold ([accum (bitwise-xor accum byte)])
([num (in-range 0 8)])
(bitwise-xor (quotient accum 2)
(* #xEDB88320 (bitwise-and accum 1)))))
#xFFFFFFFF))
(define (crc32 s)
(bytes-crc32 (string->bytes/utf-8 s)))
(format "~x" (crc32 "The quick brown fox jumps over the lazy dog"))
Output:
"414fa339"
[edit] REXX
/*REXX program to compute the CRC-32 (Cylic Redundancy Check, 32 bit),*/
/* checksum for a given string [as described in ISO 3309, ITU-T V.42].*/
a_string = 'The quick brown fox jumps over the lazy dog'
b_string = 'Generate CRC32 Checksum For Byte Array Example'
call show a_string
call show b_string
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────SHOW subroutine─────────────────────*/
show: procedure; parse arg Xstring; say
checksum=CRC_32(Xstring) /*invoke CRC_32 to create a CRC*/
say
say center(' input string [length of' length(Xstring) "bytes] ",79,'─')
say Xstring /*show the string on its own line*/
say
checksum=bitxor(checksum,'ffFFffFF'x) /*final convolution for checksum.*/
say 'hex CRC-32 checksum =' c2x(checksum) left('',15),
"dec CRC-32 checksum =" c2d(checksum) /*show CRC-32 in hex & dec*/
return
/*──────────────────────────────────CRC_32 subroutine───────────────────*/
CRC_32: procedure; parse arg !,$ /*2nd arg is for multi-invokes. */
do i=0 to 255; z=d2c(i) /*build the 8-bit indexed table. */
r=right(z,4,'0'x) /*insure the R is 32 bits. */
do j=0 for 8 /*handle each bit of rightmost 8.*/
rb=x2b(c2x(r)) /*convert char ──► hex ──► binary*/
_=right(rb,1) /*remember right-most bit for IF.*/
r=x2c(b2x(0||left(rb,31))) /*shift it right (unsigned) 1 bit*/
if _\==0 then r=bitxor(r,'edb88320'x) /*bit XOR grunt-work.*/
end /*j*/
!.z=r
end /*i*/
$=bitxor(word($ '0000000'x,1),'ffFFffFF'x) /*use user's CRC or default.*/
do k=1 for length(!) /*start crunching the input data.*/
?=bitxor(right($,1),substr(!,k,1)); $=bitxor('0'x||left($,3),!.?)
end /*k*/
return $ /*return with da money to invoker*/
output
────────────────────── input string [length of 43 bytes] ────────────────────── The quick brown fox jumps over the lazy dog hex CRC-32 checksum = 414FA339 dec CRC-32 checksum = 1095738169 ────────────────────── input string [length of 46 bytes] ────────────────────── Generate CRC32 Checksum For Byte Array Example hex CRC-32 checksum = D1370232 dec CRC-32 checksum = 3510043186
[edit] Ruby
Use 'zlib' from standard library.
require 'zlib'
printf "0x%08x\n", Zlib.crc32('The quick brown fox jumps over the lazy dog')
# => 0x414fa339
Reimplement CRC-32 in Ruby, with comments to show the polynomials.
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
[edit] Smalltalk
the CRC32Stream utility class can do it for me:
CRC32Stream hashValueOf:'The quick brown fox jumps over the lazy dog'
Output: 1095738169 "which is 16r414FA339"
[edit] Tcl
package require Tcl 8.6
set data "The quick brown fox jumps over the lazy dog"
puts [format "%x" [zlib crc32 $data]]
Which produces this output:
414fa339
Alternatively, with older versions of Tcl:
package require crc32
puts [format "%x" [crc::crc32 $data]]
With the same input data, it produces identical output.
[edit] XPL0
code HexOut=27; \intrinsic routine
string 0; \use zero-terminated strings
func CRC32(Str, Len); \Return CRC-32 for given string
char Str; int Len; \byte array, number of bytes
int I, J, R, C;
[R:= -1; \initialize with all 1's
for J:= 0 to Len-1 do
[C:= Str(J);
for I:= 0 to 8-1 do \for each bit in byte...
[if (R xor C) and 1 then R:= R>>1 xor $EDB88320
else R:= R>>1;
C:= C>>1;
];
];
return not R;
];
HexOut(0, CRC32("The quick brown fox jumps over the lazy dog", 43))
- Output:
414FA339
