CRC32 program logic problem

zhespelt has asked for the wisdom of the Perl Monks concerning the following question:

I'm trying to write a program to calculate a 32-bit CRC from an imput file by emulating the hardware representation on pg. 195 of Data & Computer Communications (8th ed. Stallings). There's a problem in my program's logic in at least one spot. Am I iterating an array in the wrong direction or popping when I should unshift?
Here's my code thus far:

#!/usr/bin/perl -w

use strict;
use warnings;
use String::CRC32;

# Poly: X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^
+1+1
# Gen: 100000100110000010001110110110111

my @msg;
my @bin_msg;
my @gen = qw(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);
my @crc = qw(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0);
my $crc = 0;
my $old_crc = 0;
my $built_in_crc = 0;

get_input();
my_crc();
built_in_crc();
display();

sub get_input {
    local $/ = undef;
    my $file = <>;
    my @file = split(/0x/, $file);
    @msg = split(//, $file[0]);
    if ($file[1]) { $old_crc = sprintf('0x%s', $file[1]); }
    else { $old_crc = 0; }
    $built_in_crc = built_in_crc($file[0]);
}

sub my_crc {
    foreach (@msg) {
        push(@bin_msg, split(//, sprintf('%08b', ord($_))));
    }

    print "\n";

    while (@bin_msg) {
        my $bit = shift(@bin_msg);
        print "bit: $bit\t\t";
        push(@crc, $bit);
        shift(@crc);

        if ($bit == 1) {
            for (my $i = 0; $i < 32; $i++) {
                if ($gen[$i] == 1) { $crc[$i] ^= 1; }
            }
        }
        print @crc, "\n";
    }
}

sub built_in_crc { my $tmp = $_[0] || warn "$!\n"; return crc32($tmp);
+ }

sub display {
    my $x = '';
    foreach (@crc) { $x .= $_; }

    print "Msg:\t\t\'", @msg, "\'\n";
    print "Gen:\t\t", @gen, "\n";
    printf "Old CRC:\t%s\n", $old_crc;
    printf "New CRC:\t%s", `python -c "print hex(0b$x)"`;
    printf "Lib CRC:\t%#x\t(String::CRC32)\n\n", $built_in_crc;
}
[download]

And the output:

bit: 0        00000000000000000000000000000000
bit: 1        00000100110000010001110110110110
bit: 0        00001001100000100011101101101100
bit: 1        00010111110001010110101101101110
bit: 0        00101111100010101101011011011100
bit: 1        01011011110101001011000000001110
bit: 1        10110011011010000111110110101010
bit: 0        01100110110100001111101101010100

Msg:        'V'
Gen:        00000100110000010001110110110111
Old CRC:    0x500a1b4c
New CRC:    0x66d0fb54
Lib CRC:    0x500a1b4c    (String::CRC32)
[download]

Old, New and Lib CRC should match...but my result (New CRC) doesn't.
Update: I worked out the same message 'V' by hand and got the same result as my program '0x66d0fb54'. This means that the program is doing exactly what I expected it to do. So my problem must be in my interpretation of the hardware's logic.
I think I should be feeding the bit-string representation of the message, MSB first into the crc array, if the current bit is a 1, then I iterate through the crc and gen arrays, xoring the the corresponding index in crc whenever I encounter a 1 in the gen array.
Any insights?

Comment on CRC32 program logic problem Select or Download Code

Replies are listed 'Best First'.
Re: CRC32 program logic problem by BrowserUk (Patriarch) on Jul 23, 2009 at 14:16 UTC
See Re: String::CRC32 Pure Perl Implementation & String::CRC32. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. RIP PCW	[reply]
Re: CRC32 program logic problem by 5mi11er (Deacon) on Jul 23, 2009 at 19:45 UTC
I'm throwing out a non-researched guess, so, please use this only as a suggested pointer toward the real answer. I would question how your current hardware represents data. Is it little endian or big endian? And I believe the CRC engine would need to re-arrange things as needed depending on the endian-ness so that either type of hardware would come up with the same answer to a given input. Update: Nevermind, you're using string representation of binary numbers, so my attempt at helpfulness falls well short of the mark. -Scott	[reply]
Re: CRC32 program logic problem by ig (Vicar) on Aug 17, 2009 at 23:01 UTC
The following modification of your my_crc function produces the same CRC 32 as String::CRC32. sub my_crc { # Within each byte the bits are read LSB to MSB # A quirk of Ethernet CRC32 foreach (@msg) { push(@bin_msg, reverse split(//, sprintf('%08b', ord($_)))); } # Augment the message buffer so all message bits # will be shifted out of the remainder push(@bin_msg, (0)x32); # Invert the first 32 bits of the augmented buffer # Another quirk of the Ethernet CRC 32 $bin_msg[$_] ^= 1 for(0..31); print "\n"; while (@bin_msg) { my $bit = shift(@bin_msg); print "bit: $bit\t\t"; push(@crc, $bit); # shift the remainder and subtract the generator if # the bit shifted off was a 1 if (shift(@crc) == 1) { for (my $i = 0; $i < 32; $i++) { if ($gen[$i] == 1) { $crc[$i] ^= 1; } } } print @crc, "\n"; } # Reverse the remainder: another quirk of Ethernet CRC32 @crc = reverse @crc; # Invert the remainder: another quirk of Ethernet CRC32 $crc[$_] ^= 1 for(0..31); } [download]	[reply] [d/l]