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.
~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]);
}
update (broquaint): added <readmore>