CRC16 ccitt 1021 - Part 2

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

CRC16 ccitt 1021 - Part 2

Russell Haley
Hi,

I have a working C hash function that I turned into a Lua module:

int16_t crc_1021_c(int16_t old_crc, int8_t data)
{
    int16_t crc;
    int16_t x;

    x = ((old_crc>>8) ^ data) & 0xff;
    x ^= x>>4;
    crc = (old_crc << 8) ^ (x << 12) ^ (x << 5) ^ x;

    crc &= 0xffff; //disable this on 16 bit processors
    return crc;
}

I run it in a script like this:

local sf = require 'libsf'
print('Lua Calling C hash:')
local crc = 0xffff
local data = {0x00,0x00,0x0a,0x00, 0x00, 0x00, 0x0d, 0x00}
for i = 1, 8,1 do
--~ print(data[i])
    crc = sf.crc1021(crc, data[i])
end

I happened to be looking at the Lua 5.3 Bitwise Operators reference and the C code looked like I could convert it to Lua, but I get a different number when running the same data through the different codes. My attempted Lua conversion of the C hash:

function ccitt_16_c(byte_array)

    local function hash(orig_crc, byte)
        local crc
        local x;

        x = ((orig_crc >> 8) ~ byte) & 0xff;
        x = x ~ (x >> 4);
        crc = (orig_crc << 8) ~ (x << 12) ~ (x << 5) ~ x;

        crc = crc & 0xffff;
        return crc
    end

    local crc = 0xffff
    for i in ipairs(byte_array) do
        crc = hash(crc, byte_array[i])
    end

    return crc & 0xffff
end

I get a much different number from the two code bases even though they are run on the same table. Here is my test script:

test-crc.lua:

local sf = require 'libsf'
local lcrc = require 'crc1021'

print('Lua Calling C hash:')
local crc = 0xffff
local data = {0x00,0x00,0x0a,0x00, 0x00, 0x00, 0x0d, 0x00}
for i = 1, 8,1 do
--~ print(data[i])
crc = sf.crc1021(crc, data[i])
end

print(crc)

local pl = string.pack('<I<I',0x000a0000,0x000d0000)
print('C on packed string')
local crc = sf.crc16(pl)
print(crc)

print('Lua Clark Li:')
print('Disabled, my variant didn\'t work')
--~ print(lcrc.ccitt_16_l(data))

print('Lua converted C:')
print(lcrc.ccitt_16_c(data))

Results: 

C:\Users\russh\projects\NLuaSerialScripts> lua .\test-crc.lua
Lua Calling C hash:
-16032.0
C on packed string
-16032.0
Lua Clark Li:
Disabled, my variant didn't work
Lua converted C:
49504

Any ideas why I get a different number? All input greatly appreciated.

Russ
Reply | Threaded
Open this post in threaded view
|

Re: CRC16 ccitt 1021 - Part 2

Jonathan Goble
On Thu, Oct 24, 2019 at 12:03 AM Russell Haley <[hidden email]> wrote:

>
> Results:
>
> C:\Users\russh\projects\NLuaSerialScripts> lua .\test-crc.lua
> Lua Calling C hash:
> -16032.0
> C on packed string
> -16032.0
> Lua Clark Li:
> Disabled, my variant didn't work
> Lua converted C:
> 49504
>
> Any ideas why I get a different number? All input greatly appreciated.
>
> Russ

You're actually getting the same number. The difference is that the
original C code is using signed 16-bit integers and 49504 has an MSB
of 1, so two's complement is used, while Lua is using 64-bit integers,
so two's complement doesn't come into play (MSB is 0). If you put
49504 into an unsigned 16-bit integer in C and then cast it to signed,
the result will be -16032.

Reply | Threaded
Open this post in threaded view
|

Re: CRC16 ccitt 1021 - Part 2

Russell Haley


On Wed, Oct 23, 2019 at 10:08 PM Jonathan Goble <[hidden email]> wrote:
On Thu, Oct 24, 2019 at 12:03 AM Russell Haley <[hidden email]> wrote:
>
> Results:
>
> C:\Users\russh\projects\NLuaSerialScripts> lua .\test-crc.lua
> Lua Calling C hash:
> -16032.0
> C on packed string
> -16032.0
> Lua Clark Li:
> Disabled, my variant didn't work
> Lua converted C:
> 49504
>
> Any ideas why I get a different number? All input greatly appreciated.
>
> Russ

You're actually getting the same number. The difference is that the
original C code is using signed 16-bit integers and 49504 has an MSB
of 1, so two's complement is used, while Lua is using 64-bit integers,
so two's complement doesn't come into play (MSB is 0). If you put
49504 into an unsigned 16-bit integer in C and then cast it to signed,
the result will be -16032.

Ah ha! Thank you, Johnathan, crc & 0xffff solved it. I'll work on the Li variant tomorrow. 

Regards, 
Russell  
Reply | Threaded
Open this post in threaded view
|

Re: CRC16 ccitt 1021 - Part 2

Phil Leblanc
In reply to this post by Russell Haley
On Thu, Oct 24, 2019 at 4:03 AM Russell Haley <[hidden email]> wrote:

>
> I have a working C hash function that I turned into a Lua module:
>
> int16_t crc_1021_c(int16_t old_crc, int8_t data)
> {
>     int16_t crc;
>     int16_t x;
>
>     x = ((old_crc>>8) ^ data) & 0xff;
>     x ^= x>>4;
[. . . ]
>
> Any ideas why I get a different number? All input greatly appreciated.

I _think_ (but didn't check or test)  there is an issue in your
original C code. The function crc_1021_c() and parameter old_crc
should be declared as _unsigned_ and not _signed_ short integers (ie.
uint16_t instead of int16_t.  -- parameter 'data' should also be
unsigned, but it should not make a difference.

The key issue here is that in C, I _think_ that right shift is
undefined behavior for signed integers. It is often implemented by
compilers as an _arithmetic shift_ (ie. a shift "with sign extension"
-- google arithmetic shift vs. logical shift)

Lua right shift is always a logical shift, without sign extension. So
the C line " x ^= x>>4;" and the Lua line "x = x ~ (x >> 4)" do not
compute the same result when 'x' happens to be negative.

This may explain that you get different results. As I said before, I
didn't checked.

HTH

Phil

Reply | Threaded
Open this post in threaded view
|

Re: CRC16 ccitt 1021 - Part 2

Gé Weijers
I typically implement this CRC (CRC-16-CCITT) like this:

uint16_t update_crc(uint16_t crc, uint8_t b)
{
  crc ^= b;
  crc = (crc >> 4) ^ (0x1081 * (crc & 0xf));
  crc = (crc >> 4) ^ (0x1081 * (crc & 0xf));
  return crc;
}

The difference: this CRC is reflected, i.e. the bit order is reversed. This is the way it's used in protocols like HDLC, Bluetooth, PPP and a lot more. In serial communications the CRC is sent out most significant bit first, and because UARTs send out bytes least significant bit first you have to calculate a reflected CRC.
The reason this is done is to improve burst error detection.

On a processor that does not have fast multiplication instructions you're better off with the classical lookup table. This should produce the same results:

const uint16_t lut[] = {
    0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
    0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,
    0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,
    0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,
    0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,
    0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,
    0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,
    0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,
    0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,
    0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,
    0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,
    0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,
    0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,
    0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,
    0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,
    0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,
    0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,
    0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,
    0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,
    0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,
    0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,
    0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,
    0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,
    0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,
    0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,
    0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,
    0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,
    0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,
    0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,
    0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,
    0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,
    0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78,
};

uint16_t update_crc(uint16_t crc, uint8_t b)
{
  crc ^= b;
  return (crc >> 8) ^ lut[(crc & 0xff)];
}

(note that entry 128 in this table (0x8408) is you polynomial 0x1021 bit-reversed. This is not a coincidence)



On Thu, Oct 24, 2019 at 11:21 AM Phil Leblanc <[hidden email]> wrote:
On Thu, Oct 24, 2019 at 4:03 AM Russell Haley <[hidden email]> wrote:
>
> I have a working C hash function that I turned into a Lua module:
>
> int16_t crc_1021_c(int16_t old_crc, int8_t data)
> {
>     int16_t crc;
>     int16_t x;
>
>     x = ((old_crc>>8) ^ data) & 0xff;
>     x ^= x>>4;
[. . . ]
>
> Any ideas why I get a different number? All input greatly appreciated.

I _think_ (but didn't check or test)  there is an issue in your
original C code. The function crc_1021_c() and parameter old_crc
should be declared as _unsigned_ and not _signed_ short integers (ie.
uint16_t instead of int16_t.  -- parameter 'data' should also be
unsigned, but it should not make a difference.

The key issue here is that in C, I _think_ that right shift is
undefined behavior for signed integers. It is often implemented by
compilers as an _arithmetic shift_ (ie. a shift "with sign extension"
-- google arithmetic shift vs. logical shift)

Lua right shift is always a logical shift, without sign extension. So
the C line " x ^= x>>4;" and the Lua line "x = x ~ (x >> 4)" do not
compute the same result when 'x' happens to be negative.

This may explain that you get different results. As I said before, I
didn't checked.

HTH

Phil



--

Reply | Threaded
Open this post in threaded view
|

Re: CRC16 ccitt 1021 - Part 2

Roberto Ierusalimschy
In reply to this post by Phil Leblanc
> >     int16_t x;
> >
> >     x = ((old_crc>>8) ^ data) & 0xff;
> >     x ^= x>>4;
> [. . . ]
> The key issue here is that in C, I _think_ that right shift is
> undefined behavior for signed integers. It is often implemented by
> compilers as an _arithmetic shift_ (ie. a shift "with sign extension"
> -- google arithmetic shift vs. logical shift)
>
> Lua right shift is always a logical shift, without sign extension. So
> the C line " x ^= x>>4;" and the Lua line "x = x ~ (x >> 4)" do not
> compute the same result when 'x' happens to be negative.

After a bitwise-and with 0xff, a 16-bit integer will never be
negative.

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: CRC16 ccitt 1021 - Part 2

Tim Hill
In reply to this post by Phil Leblanc


> On Oct 24, 2019, at 10:52 AM, Phil Leblanc <[hidden email]> wrote:
>
>
> I _think_ (but didn't check or test)  there is an issue in your
> original C code. The function crc_1021_c() and parameter old_crc
> should be declared as _unsigned_ and not _signed_ short integers (ie.
> uint16_t instead of int16_t.  -- parameter 'data' should also be
> unsigned, but it should not make a difference.
>
> The key issue here is that in C, I _think_ that right shift is
> undefined behavior for signed integers. It is often implemented by
> compilers as an _arithmetic shift_ (ie. a shift "with sign extension"
> -- google arithmetic shift vs. logical shift)
>

In this case it won’t make any difference, since in all cases the bits shifted “in” from the left are never significant and are discarded (via the various masking steps), so regardless if they are 0 or 1 the code will work. Stylistically, however, I agree that I would code this using unsigned ints to avoid any confusion.

—Tim



Reply | Threaded
Open this post in threaded view
|

Re: CRC16 ccitt 1021 - Part 2

Russell Haley


On Thu, Oct 24, 2019 at 4:03 PM Tim Hill <[hidden email]> wrote:


> On Oct 24, 2019, at 10:52 AM, Phil Leblanc <[hidden email]> wrote:
>
>
> I _think_ (but didn't check or test)  there is an issue in your
> original C code. The function crc_1021_c() and parameter old_crc
> should be declared as _unsigned_ and not _signed_ short integers (ie.
> uint16_t instead of int16_t.  -- parameter 'data' should also be
> unsigned, but it should not make a difference.
>
> The key issue here is that in C, I _think_ that right shift is
> undefined behavior for signed integers. It is often implemented by
> compilers as an _arithmetic shift_ (ie. a shift "with sign extension"
> -- google arithmetic shift vs. logical shift)
>

In this case it won’t make any difference, since in all cases the bits shifted “in” from the left are never significant and are discarded (via the various masking steps), so regardless if they are 0 or 1 the code will work. Stylistically, however, I agree that I would code this using unsigned ints to avoid any confusion.

—Tim



Thanks everyone. The C code is the reference implementation for a project so I'll leave it as is. I'm going to drop the Li implementation in Part 1 and move on to building the messages. Thank you Ge for the alternative crcs. I'll keep those around for later.

Oooh, I have a fun project at work. I'mna ask another question...

Russ
Reply | Threaded
Open this post in threaded view
|

Re: CRC16 ccitt 1021 - Part 2

Phil Leblanc
In reply to this post by Roberto Ierusalimschy
On Thu, Oct 24, 2019 at 8:57 PM Roberto Ierusalimschy
<[hidden email]> wrote:
> . . .
> After a bitwise-and with 0xff, a 16-bit integer will never be
> negative.

Yes indeed!  :-)