Unsigned Integers

C#:

void CalculateCRC32(byte[] rawData, int offset, int crcLastIndex, ref uint crc)
{
    try
    {
        crc = 0xFFFFFFFF;
        //Calculating the CRC 32
        for (int i = 0; i < crcLastIndex; i++)
        {
            crc = (crc >> 8) ^ crc32Table[(crc & 0xFF) ^ rawData[i + offset]];
        }
        crc ^= 0xFFFFFFFF;
    }
    catch
    {
        crc = 0xFFFFFFFF;
    }
}

byte[] buffer = new byte[] { 0, 1, 2, 3 };
uint crc = 0;
CalculateCRC32(buffer, 0, 4, ref crc);

Monkey C:

function calculateCRC32(rawData, offset, crcLastIndex)
    {    	
    	var bytes = [0xFF, 0xFF, 0xFF, 0xFF]b;
    	var options = {};
    	var crc = bytes.decodeNumber(Lang.NUMBER_FORMAT_UINT32, options);
        //Calculating the CRC 32
        for (var i = 0; i < crcLastIndex; i++)
        {
        	crc = (crc >> 8) ^ crc32Table[((crc & 0xFF) ^ rawData[i + offset]).toNumber()];
        }  
        crc ^= bytes.decodeNumber(Lang.NUMBER_FORMAT_UINT32, options);
		return crc;
    }
    
    var array = [0, 1, 2, 3];
	calculateCRC32(array, 0, 4);

I'm getting 2336654867 in Monkey C, and a value of 2344191507 in C#. Why is this?

0 FlowState over 2 years ago

There's two issues here:

1) The Monkey C code in the OP produces an incorrect answer, because ">>" is arithmetical right shift which will extend the sign bit (which we don't want, since the calculation of crc32 is supposed to be done using unsigned bitwise operations).

2) Even if the Monkey C code is changed to produce the correct answer, the answer given by C# (interpreted as an unsigned int) will sometimes differ from the answer given by the Monkey C code (interpreted as a signed int). (Of course the correct answers will match when printed as hexadecimal, regardless of sign.)

I fixed the Monkey C code by simulating logical right shift (https://stackoverflow.com/a/8248336), and I changed the C# code to return a 32-bit signed integer, so that both answers match when doing a simple conversion to string.

I also added test code which prints the answer in 3 formats: signed int, unsigned int and hex.

TL;DR:

replace:

(crc >> 8)

with crc_shifted_8 below:

            // stackoverflow.com/.../implementing-logical-right-shift-in-c
            var mask = ~(-1 << 8) << (32 - 8);
            var crc_shifted_8 = ~mask & ((crc >> 8) | mask);

---

I used the following sites to validate my results, with the test case "1234" (0x31, 0x32, 0x33, 0x34):

https://crc32.online/ (returns signed int)

https://simplycalc.com/crc32-text.php (returns unsigned int)

C# code (validated at https://dotnetfiddle.net/):

using System;
					
public class Program
{
	public  void Main()
	{
		//byte[] buffer = new byte[] { 0, 1, 2, 3 };
		byte[] buffer = new byte[] { 0x31, 0x32, 0x33, 0x34 };
		//byte[] buffer = new byte[] { 0x31 };

			
		int crc = CalculateCRC32(buffer, 0, 4);
		Console.WriteLine("CRC32 (as signed integer) = " + crc);
		Console.WriteLine("CRC32 (as unsigned integer) = " + (uint)crc);
		Console.WriteLine("CRC32 (as hexadecimal = 0X" + String.Format("{0:X}", crc));
	}
	
	 int CalculateCRC32(byte[] rawData, int offset, int crcLastIndex)
	 {
		 uint crc = 0xffffffff;
		 try
		 {
			 
			 //Calculating the CRC 32
			 for (int i = 0; i < crcLastIndex; i++)
			 {
				 crc = (crc >> 8) ^ crc32Table[(crc & 0xFF) ^ rawData[i + offset]];
			 }
			 crc ^= 0xFFFFFFFF;
		 }
		 catch
		 {
			 crc = 0xFFFFFFFF;
		 }
		 return (int)crc;
	 }

	
	  uint[]  crc32Table = new uint[] {
		0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
		0xe963a535, 0x9e6495a3,	0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
		0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
		0xf3b97148, 0x84be41de,	0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
		0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,	0x14015c4f, 0x63066cd9,
		0xfa0f3d63, 0x8d080df5,	0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
		0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,	0x35b5a8fa, 0x42b2986c,
		0xdbbbc9d6, 0xacbcf940,	0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
		0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
		0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
		0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,	0x76dc4190, 0x01db7106,
		0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
		0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
		0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
		0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
		0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
		0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
		0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
		0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
		0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
		0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
		0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
		0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
		0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
		0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
		0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
		0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
		0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
		0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
		0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
		0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
		0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
		0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
		0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
		0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
		0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
		0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
		0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
		0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
		0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
		0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
		0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
		0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
	};    
}

C# output:

CRC32 (as signed integer) = -1679564637
CRC32 (as unsigned integer) = 2615402659
CRC32 (as hexadecimal = 0X9BE3E0A3

Monkey C code

    function calculateCRC32(rawData, offset, crcLastIndex) {
        var crc = 0xffffffff;
        for (var i = 0; i < crcLastIndex; i++) {
            // https://stackoverflow.com/questions/5253194/implementing-logical-right-shift-in-c
            var mask_8 = ~(-1 << 8) << (32 - 8);
            var crc_shifted_8 = ~mask_8 & ((crc >> 8) | mask_8);

            crc = crc_shifted_8 ^ crc32Table[((crc & 0xFF) ^ rawData[i + offset])];
        }
        crc ^= 0xffffffff;
		return crc;
    }

    function test() {
        // var array = [0, 1, 2, 3];
        var array = [0x31, 0x32, 0x33, 0x34];
        var crc = calculateCRC32(array, 0, 4);
        System.println("crc (as signed integer) = " + crc);
        // https://stackoverflow.com/questions/29811702/convert-signed-to-unsigned-integer-mathematically
        // NOTE: this trick also could've been used to calculate crc_shifted_8...
        System.println("crc (as unsigned integer) = " + ((crc.toLong() + 0x100000000L) % 0x100000000L));
        System.println("crc (as hexadecimal) = 0x" + crc.format("%08X"));
    }
    
    var crc32Table = [
    	0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
    	0xe963a535, 0x9e6495a3,	0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
    	0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
    	0xf3b97148, 0x84be41de,	0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
    	0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,	0x14015c4f, 0x63066cd9,
    	0xfa0f3d63, 0x8d080df5,	0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
    	0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,	0x35b5a8fa, 0x42b2986c,
    	0xdbbbc9d6, 0xacbcf940,	0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
    	0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
    	0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
    	0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,	0x76dc4190, 0x01db7106,
    	0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
    	0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
    	0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
    	0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
    	0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
    	0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
    	0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
    	0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
    	0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
    	0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
    	0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
    	0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
    	0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
    	0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
    	0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
    	0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
    	0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
    	0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
    	0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
    	0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
    	0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
    	0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
    	0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
    	0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
    	0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
    	0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
    	0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
    	0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
    	0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
    	0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
    	0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
    	0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
    ];

Monkey C output:

crc (as signed integer) = -1679564637
crc (as unsigned integer) = 2615402659
crc (as hexadecimal) = 0x9BE3E0A3

0 FlowState over 2 years ago in reply to FlowState

In a perfect world, Monkey C would just implement the unsigned right shift operator >>>, but ¯\_(ツ)_/¯

EDIT: Sorry the example code I posted above is kind of a mess. I tried to edit it further, but the forum got upset with me and claimed I was "blocked". Never change, Garmin/Garmin-adjacent software.

EDIT2:

Not to state the obvious, but the following code in the OP

       var bytes = [0xFF, 0xFF, 0xFF, 0xFF]b;
       var options = {};
       var crc = bytes.decodeNumber(Lang.NUMBER_FORMAT_UINT32, options);

can be replaced with

var crc = 0xffffffff;

0xffffffff is just a bit pattern (32 1s), so it doesn't matter how you assign it to the crc variable (and the fact that the crc variable is a signed 32-bit integer also doesn't matter here, as long as it has enough bits to hold 0xffffffff, which it does.)

The signed vs unsigned integer issue only comes into play when:

- Doing arithmetic/comparisons on the integer (e.g. +, -, *, /, %, >>, <, >, etc.).

- Printing out the value of the integer.

As a counterexample, the following bitwise operations don't care whether a number is signed or unsigned: ^, |, &

EDIT3:

I used the following code as a source for the CRC32 table: https://web.mit.edu/freebsd/head/sys/libkern/crc32.c

(It's the same as what was used in the OP, as the answers for [0, 1, 2, 3] match in the OP and in the code I posted.)

0 Justin over 2 years ago in reply to FlowState

Thanks FlowState. This help is invaluable.

I'll have to study lines five, six, and twenty-one in the Garmin code you wrote. Assigning 0xFFFFFFFF to 'crc' yielded a value of negative one in a console because of the sign bit. The complicated decodeNumber method output the correct decimal value instead of negative one, so I stuck with it even though the bit patterns are the same as you said just interpreted differently.

0 FlowState over 2 years ago in reply to Justin

No worries!

Justin said:
Assigning 0xFFFFFFFF to 'crc' yielded a value of negative one in a console because of the sign bit. The complicated decodeNumber method output the correct decimal value instead of negative one, so I stuck with it even though the bit patterns are the same as you said just interpreted differently.

That's because ByteArray.decodeNumber() returns a Number, Long or Float depending on the specified format. In the case of your original code, it was almost certainly returning a Long (signed 64-bit), in order to accommodate an unsigned 32-bit value.

You could've achieved the same result as the decodeNumber() code by using a Long constant (with the "L" suffix - developer.garmin.com/.../):

var crc = 0xFFFFFFFFL; // crc is a Long (signed 64-bit)

Here's an alternate solution which uses that approach. I probably wouldn't use it because it could be slower, as a Long is an object rather than a primitive in Monkey C (roughly speaking). In Monkey C, everything is an "object", but some objects act like value types ("primitives" like Number and Float) while other objects act like reference types (Long and Double).

(Plus you'd also be calling toNumber() for every loop iteration.)

(Then again, I haven't benchmarked either method, so I can't say for sure which one is faster.)

    function calculateCRC32_B(rawData, offset, crcLastIndex) {
        var crc = 0xffffffffL;
        for (var i = 0; i < crcLastIndex; i++) {
            crc = (crc >> 8) ^ crc32Table[((crc & 0xFF) ^ rawData[i + offset]).toNumber()] & 0xffffffffL;
        }
        crc ^= 0xffffffff;
        return crc.toNumber();
    }

(The "L" suffix in "& 0xffffffffL" is necessary. so that crc remains a Long until the final answer is returned.)

Speaking of optimization, in my original answer, obviously the calculation of mask_8 can be moved out of the for loop, since it's a constant.