Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris

CRC-16 algorithm

by CMonster (Scribe)
on May 20, 2003 at 18:39 UTC ( #259538=perlquestion: print w/replies, xml ) Need Help??
CMonster has asked for the wisdom of the Perl Monks concerning the following question:

Monks, I've been banging my head against this one for days, and I know there has to be a better way.

I'm coding a serial connection module for a project at work, but I've had a devil of a time finding a simple, working CRC-16 generation algorithm in Perl. I've found a reference to the algorithms, a routine in C, and a bit of mangled Perl (cleaned up and included below), but so far no example CRC-16 values to check against.

To be specific, I need a perl algorithm which takes an arbitrary string of bytes and generates a 16-bit CRC using the polynomial x^16 + x^15 + x^2 + 1. I also need a set of values I can use to check the algorithm. The algorithm does not need to be fast; the strings I'm dealing with are a dozen bytes at the most.

Once I am able to produce a working algorithm in Perl, I pledge to:

  • post an Acme::CRC16 module to CPAN with the working code and documentation;
  • post the module, documentation, and a full set of example CRC values to my Web site;
  • post the module (and kudos) as a reply to this node.

Any help you can provide in the form of code snippets, algorithmic hints, or example CRC-16 values would be greatly appreciated.

use 5.6.1; use strict; use warnings; my $message = $ARGV[0]; # my $message = pack('H*', '06030bb90001'); my $crc16 = generate_crc16($message); print "CRC16 in hex:\n ", unpack('H*', $crc16), "\n"; exit; # Usage: my $crc = generate_crc16($message); # # generates a 16-bit Cyclical Redundancy Check (CRC-16) # using the polynomial x^16 + x^15 + x^2 + 1 # for any given message # # NOTE: The message should ONLY contain characters which # should be included in the CRC. # sub generate_crc16 { my $message = shift(@_); my $binary_message = unpack('B*', $message); my @G = ('1','0','0','0','0','0','0','0', '0','0','0','0','0','1','0','1'); my @shift_register = ('1','1','1','1','1','1','1','1', '1','1','1','1','1','1','1','1'); print "Binary message:\n $binary_message\n"; my @data = split (//, $binary_message); while (scalar(@data) > 0) { my $next_bit = shift(@data); next unless ($next_bit eq "0" or $next_bit eq "1"); if ($next_bit eq shift(@shift_register)) { push(@shift_register, '0'); } else { push(@shift_register, '0'); @shift_register = xor16(@shift_register, @G); } } # create the CRC value from the binary digits my $crc16_binary = ''; # invert shift register to generate CRC field foreach my $bit (@shift_register) { if ($bit eq "1") { $crc16_binary .= '0'; } else { $crc16_binary .= '1'; } } print "CRC16 binary:\n $crc16_binary\n"; my $crc16_bytes = pack('B*', $crc16_binary); return $crc16_bytes; } # Usage: my @result = xor16(@first, @second); # # perform a 16-bit XOR on two arrays of 16 bits each # sub xor16 { my @x = @_[0..15]; my @y = @_[16..31]; my @results16; for my $j (0..15) { if ( shift(@x) eq shift(@y) ) { push(@results16, '0'); } else { push(@results16, '1'); } } return(@results16[0..15]); }

update (broquaint): added <readmore>

Replies are listed 'Best First'.
Re: CRC-16 algorithm
by Mr. Muskrat (Canon) on May 20, 2003 at 18:51 UTC

      Thanks! OK, got it and tried it. The documentation is a bit sparse, but using String::CRC gives rise to a program like so:

      use strict; use warnings; use String::CRC; my $message = $ARGV[0]; my $crc16 = crc($message); print "CRC16 in decimal: $crc16\n"; print "CRC16 in hex:\n ", unpack('H*', pack('S', $crc16)), "\n";

      Running the program gives this output:

      cradcliff% ./ foo CRC16 in decimal: 1736882148 CRC16 in hex: b7e4 cradcliff% ./ foobar CRC16 in decimal: 3375757715 CRC16 in hex: f993 cradcliff% ./ foobaz CRC16 in decimal: 3375757723 CRC16 in hex: f99b

      More simply:

      'foo'    => 0xb7e4
      'foobar' => 0xf993
      'foobaz' => 0xf99b

      Can anyone verify that these are correct values for a CRC-16 checksum, assuming the conditions I specified earlier? Alternately, can anyone supply sample string-checksum pairs I can use to test this program?

      Thanks, ~c

        Try crc($message,16); because the default is 32 (like the pod says).

        MJD says you can't just make shit up and expect the computer to know what you mean, retardo!
        I run a Win32 PPM repository for perl 5.6x+5.8x. I take requests.
        ** The Third rule of perl club is a statement of fact: pod is sexy.

Re: CRC-16 algorithm
by Thelonius (Priest) on May 20, 2003 at 20:29 UTC

      Unfortunately this stuff is gone to Nirvana:

      Best regards, Karl

      «The Crux of the Biscuit is the Apostrophe»

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://259538]
Approved by Enlil
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (13)
As of 2017-01-19 11:15 GMT
Find Nodes?
    Voting Booth?
    Do you watch meteor showers?

    Results (170 votes). Check out past polls.