Porting a CRC function to ruby

ruby-talk
1

Hello,

I’m a bit new to Ruby and I’m having trouble porting a CRC function from C++
to Ruby. The problem seems to be that Fixnums are signed while the data type
used in the C function is an unsigned short. I guess I could compile the C++
function into a shared object and load that in Ruby, but I would like to
avoid that if possible as it is currently over my head.

The correct CRC for the two bytes 0x6 0x0 is 0x5b97. My Ruby implementation
returns a CRC value of 0xf5b97. It looks like I could mask off the top
nibble and get the value I want, but would this work for all cases?

Here is the C++ source:

#include
#include

using namespace std;

typedef unsigned short word;

word get_crc(unsigned char *bufptr, word len, word seed);

int main() {

// A clear screen packet.
unsigned char packet[] = “\006\000”;

word crc = get_crc( packet, 2, 0xFFFF );

cout << hex << (crc & 0x00FF) << ’ ’ // lsb little-endian order
<< hex << (crc >> 8) << endl // msb
<< crc << endl;

return 0;
}

// Use 0xFFFF as a seed.
word get_crc(unsigned char *bufptr, word len, word seed) {

//CRC lookup table to avoid bit-shifting loops.
static const word crcLookupTable[256] =
{0x00000,0x01189,0x02312,0x0329B,0x04624,0x057AD,0x06536,0x074BF,
0x08C48,0x09DC1,0x0AF5A,0x0BED3,0x0CA6C,0x0DBE5,0x0E97E,0x0F8F7,
0x01081,0x00108,0x03393,0x0221A,0x056A5,0x0472C,0x075B7,0x0643E,
0x09CC9,0x08D40,0x0BFDB,0x0AE52,0x0DAED,0x0CB64,0x0F9FF,0x0E876,
0x02102,0x0308B,0x00210,0x01399,0x06726,0x076AF,0x04434,0x055BD,
0x0AD4A,0x0BCC3,0x08E58,0x09FD1,0x0EB6E,0x0FAE7,0x0C87C,0x0D9F5,
0x03183,0x0200A,0x01291,0x00318,0x077A7,0x0662E,0x054B5,0x0453C,
0x0BDCB,0x0AC42,0x09ED9,0x08F50,0x0FBEF,0x0EA66,0x0D8FD,0x0C974,
0x04204,0x0538D,0x06116,0x0709F,0x00420,0x015A9,0x02732,0x036BB,
0x0CE4C,0x0DFC5,0x0ED5E,0x0FCD7,0x08868,0x099E1,0x0AB7A,0x0BAF3,
0x05285,0x0430C,0x07197,0x0601E,0x014A1,0x00528,0x037B3,0x0263A,
0x0DECD,0x0CF44,0x0FDDF,0x0EC56,0x098E9,0x08960,0x0BBFB,0x0AA72,
0x06306,0x0728F,0x04014,0x0519D,0x02522,0x034AB,0x00630,0x017B9,
0x0EF4E,0x0FEC7,0x0CC5C,0x0DDD5,0x0A96A,0x0B8E3,0x08A78,0x09BF1,
0x07387,0x0620E,0x05095,0x0411C,0x035A3,0x0242A,0x016B1,0x00738,
0x0FFCF,0x0EE46,0x0DCDD,0x0CD54,0x0B9EB,0x0A862,0x09AF9,0x08B70,
0x08408,0x09581,0x0A71A,0x0B693,0x0C22C,0x0D3A5,0x0E13E,0x0F0B7,
0x00840,0x019C9,0x02B52,0x03ADB,0x04E64,0x05FED,0x06D76,0x07CFF,
0x09489,0x08500,0x0B79B,0x0A612,0x0D2AD,0x0C324,0x0F1BF,0x0E036,
0x018C1,0x00948,0x03BD3,0x02A5A,0x05EE5,0x04F6C,0x07DF7,0x06C7E,
0x0A50A,0x0B483,0x08618,0x09791,0x0E32E,0x0F2A7,0x0C03C,0x0D1B5,
0x02942,0x038CB,0x00A50,0x01BD9,0x06F66,0x07EEF,0x04C74,0x05DFD,
0x0B58B,0x0A402,0x09699,0x08710,0x0F3AF,0x0E226,0x0D0BD,0x0C134,
0x039C3,0x0284A,0x01AD1,0x00B58,0x07FE7,0x06E6E,0x05CF5,0x04D7C,
0x0C60C,0x0D785,0x0E51E,0x0F497,0x08028,0x091A1,0x0A33A,0x0B2B3,
0x04A44,0x05BCD,0x06956,0x078DF,0x00C60,0x01DE9,0x02F72,0x03EFB,
0x0D68D,0x0C704,0x0F59F,0x0E416,0x090A9,0x08120,0x0B3BB,0x0A232,
0x05AC5,0x04B4C,0x079D7,0x0685E,0x01CE1,0x00D68,0x03FF3,0x02E7A,
0x0E70E,0x0F687,0x0C41C,0x0D595,0x0A12A,0x0B0A3,0x08238,0x093B1,
0x06B46,0x07ACF,0x04854,0x059DD,0x02D62,0x03CEB,0x00E70,0x01FF9,
0x0F78F,0x0E606,0x0D49D,0x0C514,0x0B1AB,0x0A022,0x092B9,0x08330,
0x07BC7,0x06A4E,0x058D5,0x0495C,0x03DE3,0x02C6A,0x01EF1,0x00F78};

//Initial CRC value is 0x0FFFF.
register word newCrc;
newCrc=seed;

//This algorithim is based on the IrDA LAP example.
while(len–)
newCrc = (newCrc >> 8) ^ crcLookupTable[(newCrc ^ *bufptr++) & 0xff];

//Make this crc match the one’s complement that is sent in the packet.
return(~newCrc);
}

And the Ruby implementation:

#!/usr/local/bin/ruby

class Packet

Create a new packet of some type containing the data to send.

def initialize( packetType, packetData )

@type = packetType
@data = packetData

end

Set or read the packets data string.

attr_accessor :data

Calculate and return the CRC for this packet.

def crc

packet = form_packet()

print packet.unpack('C*').join(','), "\n"

aCrc = 0xFFFF

for c in packet.unpack('C*')

  aCrc = (aCrc >> 8) ^ CRC_LOOKUP[(aCrc ^ c) & 0xFF]
end

return ~aCrc

end

private

CRC_LOOKUP =
[0x00000,0x01189,0x02312,0x0329B,0x04624,0x057AD,0x06536,0x074BF,
0x08C48,0x09DC1,0x0AF5A,0x0BED3,0x0CA6C,0x0DBE5,0x0E97E,0x0F8F7,
0x01081,0x00108,0x03393,0x0221A,0x056A5,0x0472C,0x075B7,0x0643E,
0x09CC9,0x08D40,0x0BFDB,0x0AE52,0x0DAED,0x0CB64,0x0F9FF,0x0E876,
0x02102,0x0308B,0x00210,0x01399,0x06726,0x076AF,0x04434,0x055BD,
0x0AD4A,0x0BCC3,0x08E58,0x09FD1,0x0EB6E,0x0FAE7,0x0C87C,0x0D9F5,
0x03183,0x0200A,0x01291,0x00318,0x077A7,0x0662E,0x054B5,0x0453C,
0x0BDCB,0x0AC42,0x09ED9,0x08F50,0x0FBEF,0x0EA66,0x0D8FD,0x0C974,
0x04204,0x0538D,0x06116,0x0709F,0x00420,0x015A9,0x02732,0x036BB,
0x0CE4C,0x0DFC5,0x0ED5E,0x0FCD7,0x08868,0x099E1,0x0AB7A,0x0BAF3,
0x05285,0x0430C,0x07197,0x0601E,0x014A1,0x00528,0x037B3,0x0263A,
0x0DECD,0x0CF44,0x0FDDF,0x0EC56,0x098E9,0x08960,0x0BBFB,0x0AA72,
0x06306,0x0728F,0x04014,0x0519D,0x02522,0x034AB,0x00630,0x017B9,
0x0EF4E,0x0FEC7,0x0CC5C,0x0DDD5,0x0A96A,0x0B8E3,0x08A78,0x09BF1,
0x07387,0x0620E,0x05095,0x0411C,0x035A3,0x0242A,0x016B1,0x00738,
0x0FFCF,0x0EE46,0x0DCDD,0x0CD54,0x0B9EB,0x0A862,0x09AF9,0x08B70,
0x08408,0x09581,0x0A71A,0x0B693,0x0C22C,0x0D3A5,0x0E13E,0x0F0B7,
0x00840,0x019C9,0x02B52,0x03ADB,0x04E64,0x05FED,0x06D76,0x07CFF,
0x09489,0x08500,0x0B79B,0x0A612,0x0D2AD,0x0C324,0x0F1BF,0x0E036,
0x018C1,0x00948,0x03BD3,0x02A5A,0x05EE5,0x04F6C,0x07DF7,0x06C7E,
0x0A50A,0x0B483,0x08618,0x09791,0x0E32E,0x0F2A7,0x0C03C,0x0D1B5,
0x02942,0x038CB,0x00A50,0x01BD9,0x06F66,0x07EEF,0x04C74,0x05DFD,
0x0B58B,0x0A402,0x09699,0x08710,0x0F3AF,0x0E226,0x0D0BD,0x0C134,
0x039C3,0x0284A,0x01AD1,0x00B58,0x07FE7,0x06E6E,0x05CF5,0x04D7C,
0x0C60C,0x0D785,0x0E51E,0x0F497,0x08028,0x091A1,0x0A33A,0x0B2B3,
0x04A44,0x05BCD,0x06956,0x078DF,0x00C60,0x01DE9,0x02F72,0x03EFB,
0x0D68D,0x0C704,0x0F59F,0x0E416,0x090A9,0x08120,0x0B3BB,0x0A232,
0x05AC5,0x04B4C,0x079D7,0x0685E,0x01CE1,0x00D68,0x03FF3,0x02E7A,
0x0E70E,0x0F687,0x0C41C,0x0D595,0x0A12A,0x0B0A3,0x08238,0x093B1,
0x06B46,0x07ACF,0x04854,0x059DD,0x02D62,0x03CEB,0x00E70,0x01FF9,
0x0F78F,0x0E606,0x0D49D,0x0C514,0x0B1AB,0x0A022,0x092B9,0x08330,
0x07BC7,0x06A4E,0x058D5,0x0495C,0x03DE3,0x02C6A,0x01EF1,0x00F78]

Return a String representing the packet minus the CRC field.

def form_packet

packet = sprintf( "%c%c", @type, @data.length );
packet += @data;

return packet

end
end

p = Packet.new( 6, “” )
crc = p.crc

printf( “%x\n”, crc )
print crc

I’m certain that 0x5b97 is the correct CRC because the lcd module correctly
responds to the hand made packet 0x6 0x0 0x97 0x5b.

Thanks for any help.

Matthew

···

–
“One sir, two sir, three sir, four sir, five sir, six sir,
seven sir, eight. ‘Tenser’, said the Tensor. ‘Tenser’, said the Tensor.
Tension apprehension, and dissension have begun.”
– Alfred Bester, “The Demolished Man”

2

Hi Matthew,

The problem is not signed vs unsigned. The problem is, given an int, the
Ruby Fixnum is obtained by left shifting the int by one (and setting the
least significant bit to 1). Therefore, before you do your CRC, you have
to right shift the Fixnum. (Just be careful that the right shifted
version of the Fixnum may not be a valid Ruby object, so “don’t interact
with Ruby” using the right shifted version.)

The problem is probably more complicated if the data type used in the C
function is unsigned int or unsigned long. In this case probably you have
to use Bignum (and know how Bignum is implemented internally in
Ruby). However, as Ruby performs conversion between Bignum and Fixnum
automatically, you have to be careful too.

Finally, because when you are dealing with communication packets the Ruby
Fixnum is not really “clean”, probably it is better and easier to use Ruby
BitVector instead of Fixnum.

Regards,

Bill

···

===========================================================================
Matthew Miller namille2@vt.edu wrote:

Hello,

I’m a bit new to Ruby and I’m having trouble porting a CRC function from C++
to Ruby. The problem seems to be that Fixnums are signed while the data type
used in the C function is an unsigned short. I guess I could compile the C++
function into a shared object and load that in Ruby, but I would like to
avoid that if possible as it is currently over my head.

3

Hello Matthew,

Wednesday, October 16, 2002, 3:41:55 AM, you wrote:

the problem is that this code:

register word newCrc;
return(~newCrc);

cannot be translated as:

return ~aCrc

instead, use “return 65535-aCrc”

of course, types which don’t have any particular word size, must not
implement “invert ALL bits” operation :slight_smile:

···

–
Best regards,
Bulat mailto:bulatz@integ.ru

4

Hi Bill,

In article aoiqu8$ib8$1@grapevine.wam.umd.edu, William Djaja Tjokroaminata
wrote:

Hi Matthew,

The problem is not signed vs unsigned. The problem is, given an int, the
Ruby Fixnum is obtained by left shifting the int by one (and setting the
least significant bit to 1). Therefore, before you do your CRC, you have
to right shift the Fixnum. (Just be careful that the right shifted
version of the Fixnum may not be a valid Ruby object, so “don’t interact
with Ruby” using the right shifted version.)

The problem is probably more complicated if the data type used in the C
function is unsigned int or unsigned long. In this case probably you have
to use Bignum (and know how Bignum is implemented internally in
Ruby). However, as Ruby performs conversion between Bignum and Fixnum
automatically, you have to be careful too.

Finally, because when you are dealing with communication packets the Ruby
Fixnum is not really “clean”, probably it is better and easier to use Ruby
BitVector instead of Fixnum.

Thanks for the insight. I tried my suggestion of masking off all but the
lower two bytes and the CRC works with the packets I’ve tested it with.
Still I wish that ruby had an unsigned integer class.

BTW, why does Fixnum left shift by one the integer it stores? I can’t think
of any reason why that would be done.

Thanks, Matthew

···

–
“Man könnte froh sein, wenn die Luft so rein wäre wie das Bier”
“One could be happy if the air were as pure as the beer”

5

Hi Matthew,

I think in Ruby it is for efficiency purpose. Ruby internal C
implementation distinguishes objects (which are represented as VALUE,
which is an alias for unsigned long) as either a pointer or an immediate
object. Fixnum, which is an immediate object, is not allocated on Ruby gc
heap, so it is “cheaper” to deal with Fixnum’s; the only cost is that
Fixnum is now only 31-bit significant instead of full 32-bit significant.

You can also browse -talk starting at 53043 regarding the left shift and
the least significant bit.

Regards,

Bill

···

============================================================================
Matthew Miller namille2@vt.edu wrote:

Thanks for the insight. I tried my suggestion of masking off all but the
lower two bytes and the CRC works with the packets I’ve tested it with.
Still I wish that ruby had an unsigned integer class.

BTW, why does Fixnum left shift by one the integer it stores? I can’t think
of any reason why that would be done.