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:

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

~chris 
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]);
}

[download]

update (broquaint): added <readmore>

In reply to CRC-16 algorithm by CMonster

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.