CRC8Maxim with CRCBIT doesn't seem to compare with Online CRC Calculators

Bob Drury · 2021-09-02 17:12

CRC still confusing me. The idea that it is a division appears to be very inacurate and should not be the first focus for explaination. XOR being used avoiding standard division. Attached document is using two sites that seem to generate a different result for CRC8MAXIM using x8+x5+x4+1. Something else is going on when calculating this value . I have tried several values . For the value of data $1 = 1 , one calculator generates 94 the other generates 98 and CRCBIT program generates 94. What I would like to be able to
do is a hand calculation that would actually match wha the CRCBIT program is doing.
Any help would be apreciated.
Regards and Thanks
Bob (WRD)

rogloh · 2021-09-02 22:11

I feel your pain... explaining CRCs using binary division with polynomials, residues and Galois fields etc etc, is just never really that helpful to a software engineer's brain, only to a pure mathematician's writing a paper. The LFSR shift register hardware circuit with simple XOR gates tapping off bit positions based on the polynomial and feeding the next bit for the shift register is the way to go IMO. The problem with most of these confusing mathematical type descriptions they typically don't cover the practical intricacies such as complementing the data initially or at the end of the computation, and what the initial CRC register seed value to use is, whether the bits are shifted left or right in the register and this is why the results don't ever seem to match practical real world expected values.

Bob Drury · 2021-09-03 14:56

Thanks for response I am going to keep at this. I found it interesting that you mentioned complementing the data prior to the calculation. Do you have a site I can go
look at this.
Again Thanks
Regards
Bob (WRD)

rogloh · 2021-09-03 15:42

Unfortunately I do not have a definitive site but there's probably lots of resources available.
I found this which you may have encountered...
https://pdfserv.maximintegrated.com/en/an/AN27.pdf

Here's a catalogue of CRC's I found that shows the range of different types and seeds, polynomials, whether to xor final result etc.
https://reveng.sourceforge.io/crc-catalogue/all.htm#crc.cat-summary
Actually I'm not especially sure if any CRC's do complement the data before going in, or optionally just on output (see "xorout" in model parameters section of that catalogue, plus the other items). You'll see there are quite a few variations amongst these different CRCs, that's the key point here. The basic CRC XOR+shift operation itself is only one part of it. You have to do it the particular way they specify for it to match up.

Rayman · 2021-09-03 19:04

CRC is tough to figure out... Sometimes they use the reverse of the polynomial, sometimes they flip all the input bits before starting, sometimes they flip all the bits when done, and sometimes the XOR some value at the end too...

I think the polynomial reversal is related to if the bits are fed in MSb or LSb first...

Rayman · 2021-09-03 19:11

This page helped me out:
http://www.sunshine2k.de/coding/javascript/crc/crc_js.html

It's javascript, so you can view the source code yourself.

Also, you can just use the look up table it generates instead of coding it up...

This page also looks good for a check
https://crccalc.com/

Bob Drury · 2021-09-04 00:56

Thanks for the reply. On the internet there is two CRC calculators I have found "https://crccalc.com/" and "https://www.ghsi.de/pages/subpages/Online CRC Calculation/" If CRCMaxim Divisor 100110001 is used with Data $7778797A the first calculator (https://crccalc.com) generates CRC =102 decimal and the second calculator generates
CRC = 156 decimal . I tried a single byte of data $C2 the firs calculator gives CRC = 0x76 = 118 and the second calculator gave CRC = 0x25 = 37 . Using a hand calculation dividing 10011001 into the value of
$C200 the value for CRC = 0x25 = 37 . Using CRCBIT parallax program with data = $C2 resulting CRC = 0x76 = 118 . There must be something different being done for the calculation. A while ago I was asking about the $8C = %10001100 value in the CRCBIT parallax program this looks very similar to CRCMaxim = 100110001 but you have to add a 1 bit after the $8C byte and reverse the bit order, so does the parallax program use a dfferent procedure? Does the parallax program change the CRCMAXIM generating Poynomial? Haven't given up to solve this yet. I would like to be able to do a hand calculation for my notes that does not depend on the calculators or parallax program.
Regards
Bob (WRD)

Yanomani · 2021-09-04 03:23

There is a bit/(nibble)-order reversal affecting the comparison between both online calculators:

Using (https://crccalc.com/)
CRC polynomial bit sequence is implicit when you click at "CRC-8/MAXIM"-algorithm
data = $7778797A results $66;
(01110111_01111000_01111001_01111010) > (01100110)

Using (https://ghsi.de/pages/subpages/Online%20CRC%20Calculation/index.php:
CRC polynomial bit sequence = "100110001" (binary, and can be tweaked)
data = $EE1E9E5E results $66 too.
(11101110_00011110_10011110_01011110) > (01100110)

P.S. Those results ($66) can be misleading, due the possibility of a nibble-reversal being masked. Need to chose values whose results can't be misinterpreted, in any sense... (damm endianness)

Bob Drury · 2021-09-04 14:00

Thanks for response. Tried the following:

C2 = 110000010 = 194 CRC(firstOnline Calculator) = 118 CRC(secondOnlineCalculator) 37
42 = 01000011 = 66 CRC(firstOnline Calculator) = 250 CRC(secondOnlineCalculator) 95 (reversed bits of C2)
2C = 00101100 = 44 CRC(firstOnline Calculator) = 128 CRC(secondOnlineCalculator) 251 (reversed nibble)

I verified reversing individulal bytes7778797A (EE1E9E5E) and got 102 as you did which seems to be a coincidence given the above information but that I agree that seems highly unlikely .
The individual byte values I don't believe can ever be effectedby endianess. My understanding is that unsigned values wil always have the LSB on the right and MSB always on the left for all byte memory locations. What is the normal nethod of transmitting the byte bits ? I guess you could send either LSB to MSB or MSB to LSB. But I would assume it would only make sense to keep LSB on the right.
Regards
Bob (WRD)

Rayman · 2021-09-04 14:08

I see this code on Github that looks very simple for this:
https://github.com/nickandrew/avr-onewire/blob/master/maxim-crc8.c

uint8_t crc8_update(uint8_t crc, uint8_t data) {
    uint8_t i;

    crc = crc ^ data;

    for (i = 0; i < 8; ++i) {
        if (crc & 0x01) {
            crc = (crc >> 1) ^ 0x8c;
        } else {
            crc >>= 1;
        }
    }

    return crc;
}

But, maybe you need to flip the bits before and after calling this...

Yanomani · 2021-09-04 15:29

There are way more subtleties involved, than we usually perceive, so I'll keep representing them only in Hex and Binary; it's a little "bit" closer to my brain's lone twins (flippy and floppy) (pun intended).

First Online Calculator = (https://crccalc.com/)
Input: C2 (Hex) -> 11000010
Output: CRC-8/MAXIM 0x76 -> 01110110 <-> 01101110 -> 6E (Hex)
Second Online Calculator = (https://ghsi.de/pages/subpages/Online%20CRC%20Calculation/index.php)
Input: 43 (Hex) -> 01000011
Output: 6E -> 01101110 <-> 01110110 -> 76 (Hex)

Now, the results had also "flipped' (or "flopped")...

Too much scratching overhead; just needs a meal, and lots of coffee, for sure...

Rayman · 2021-09-04 16:35

Is the Maxim CRC the one used in 1-wire stuff? If so, the Spin2 code from the P2 Library probably does the right thing:
(the second version looks a lot like the C version from a few posts ago)

pub crc8(p_src, n) : crc | b

'' Returns CRC8 of n bytes at p_src                                

  org
.loop           rdbyte    b, p_src
                add       p_src, #1
                rev       b
                setq      b
                crcnib    crc, #$8C
                crcnib    crc, #$8C
                djnz      n, #.loop
  end                


pri crc8x(p_src, n) : crc | b                                     

'' Returns CRC8 of n bytes at p_src                                
'' -- implementation by Micah Dowty
'' -- for reference only                               

  repeat n                                                        
    b := byte[p_src++]                                            
    repeat 8                                                      
      if (crc ^ b) & 1                                            
        crc := (crc >> 1) ^ $8C                                   
      else                                                        
        crc >>= 1
      b >>= 1

Bob Drury · 2021-09-04 19:54

I believe the CRC8 Dallas/Maxiin x8+x5+x4+1 is being used .There are two propeller II programs one using CRCBIT and one ussing CRCNIB (can be found in this forum) both using #8C 10001100 wichi is 1 bit off from the polynomial generated divisor 10011001 they both generate the the same values as the online calculator "https://crccalc.com/". I have found on internet a paper discussing dropping 1 bit before using divisor "https://quickbirdstudios.com/blog/validate-data-with-crc/ " I have not been able to make this work. I am trying to get an example of a hand generated example .
Regards
Bob (WRD)

Rayman · 2021-09-04 20:57

If you want to do it by hand, this page looks great (although for 32 bits):
https://www.anintegratedworld.com/how-to-calculate-crc32-by-hand/

The Excel spreadsheet goes through the steps...

Rayman · 2021-09-04 22:25

I just did it by hand (see attached) and got the right answer
Just a little eraser work...

As you probably know by now, the polynomial is 0x31, but they all start with a 1 to make it 9 bits.

A good description is here: http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html

The only trick with CRC8_Maxim is that you have to reflect (reverse) both the input and the output.
But, there is no flipping of bits with this one though.

Rayman · 2021-09-04 22:39

Here's another one. This is kind of fun now...

Bob Drury · 2021-09-05 01:41

Rayman
The result looks right! Wonder why the use term reflect rather than Reverse. Thanks for looking into this I have been struggling with different videos dropping bits
adding zero's etc. This seems to match the CRC calculator "https://crccalc.com/" which means it matches the propeller II code for CRC.
Again Thanks
Bob (WRD)

Rayman · 2021-09-05 15:49

Great! I still like this page the best: http://www.sunshine2k.de/coding/javascript/crc/crc_js.html

It shows you explicitly if input and output are reflected (I don't know why they don't call it reversed either) and it shows the initial and final XOR values.
Also, it gives you a table to use, which might be worth it if we didn't have CRCNIB as an instruction.

For CRC8_MAXIM the initial and final XOR values are both zero, meaning you don't need to handle it.
For some others, these values are 0xFF, meaning you need to flip all the bits on the input or output or both.

Bob Drury · 2021-09-05 21:53

I have added to the notes I made for single byte conversion (C2 and BC) but when I tried two Bytes I got the wrong answer. If you wouldn't mind try to find $C2BC by hand .
I have attached notes I made so far.
Regards
Bob (WRD)

Rayman · 2021-09-05 23:08

Wonder which byte you do first...

Bob Drury · 2021-09-05 23:46

I thought you would put them together C2BC = 11000010_10111100 reversing 00111101_01000011 then divide by 100110001
Regards
Bob (WRD)

Rayman · 2021-09-05 23:58

Maybe you have to do one byte at a time and xor the next byte with the previous result?

Rayman · 2021-09-06 00:07

Yes, I think that's it. With this calculator, I get 0x76 from 0xC2 alone. XOR that with 0xBC to get 0xCA. Putting 0xCA in calculator gives 0xB4, same result as two bytes together.

Yanomani · 2021-09-06 00:48

Using the "reverse" result from the processing of C2 as an input (initial value), the right result for processing BC comes clear (calculator linked):

sunshine2k.de/coding/javascript/crc/crc_js.html

Yanomani · 2021-09-06 01:30

From V35 Instruction set document:
"CRCNIB" -> "Iterate CRC value in D using Q[31:28] and polynomial in S. Like CRCBIT x 4. Q = Q << 4. Use 'REP #n,#1'+SETQ+CRCNIB+CRCNIB+CRCNIB..."

This means that the starting value needs to be preset on D, and up to FOUR bytes can be processed in a row, by "stuffing" Q beforehand.

It's important to note that CRCNIB uses Q[31:28] and also updates Q[31:00] by shifting its contents (Q = Q<<4), by the end of each if its iterations.

Since SETQ also shields the next instruction from being interrupted, it's also important to remember that "Instruction Shielding Against Interrupts" should be understood as "besides protecting the current instruction from any interrupts to hit WHILE it executes, the TRANSITION towards the next intruction IS ALSO shielded from any interrupts to " hit in between" them"; it seems a bit obvious, but the implications need to be taken in account, as to don't foul any "casual" reader.

That said, for a single execution of a REP-loop, if it relyes on using SETQ at the beggining of the instructions group, it's irrelevant if it is within the loop, or if it's taken out of the loop, BEFORE the REP instruction itself.

So, rewriting a CRCNIB loop for byte-processing:
'

' on entry, "byte_value" should have been previously processed, according to any "CRC-recipe";
'
        SETQ     #(byte_value)<<24   'positioning the byte to be processed, at the top-bits of Q;
        AND        D,#0    'for a clean starting value;
'
        REP        #2, #1
        CRCNIB
        CRCNIB
'
'  Resultings now at D, ready for further processing, according to any "CRC-recipe"

Important: ATM, I'm unable to test it, so take it as is, with LOTS of SALT!

Sorry for any (many) mistakes...

Henrique

Bob Drury · 2021-09-06 03:25

Thanks for reply will try out a little later. Getting cold up in Canada my boss (ie wife) has told me to close the pool tomorrow.
Regards
Bob (WRD)

Bob Drury · 2021-09-06 21:32

Tried $7778797A
a) CRC($7778) = CRC(CRC($77) Ꚛ $78)
CRC($77) Ꚛ $78 = $7B Ꚛ $78 = 01111011
01111000
00000011 =$03
CRC($7778) = CRC($03) = $E2 =226

b) CRC($777879) = CRC(CRC($7778) Ꚛ $79)
CRC($7778) Ꚛ $79 = $E2 Ꚛ $79 = 11100010
01111001
10011011 =$9B
CRC($777879) = CRC($9B) = $31 = 49

b) CRC($7778797A) = CRC(CRC($777879) Ꚛ $7A)
CRC($777879) Ꚛ $7A = $31 Ꚛ $7A = 00110001
01111010
01001011 =$4B
CRC($7778797A) = CRC($4B) = $66 = 102
Bottom line this works! A a little convoluted too excluxive OR previous CRC value with the next data byte and then taking that to calculate the CRC for that byte sequence.
Not intuitive at all. I guess this leads to maybe using a look up table for the single bytes eliminating calculating. I guess trade off between time or memory.
Thanks for your help.
Regards
Bob (WRD)

Yanomani · 2021-09-06 23:06

@"Bob Drury" said:

Not intuitive at all. I guess this leads to maybe using a look up table for the single bytes eliminating calculating. I guess trade off between time or memory.
Thanks for your help.
Regards
Bob (WRD)

You are always welcome!

For my own use, I prefer the hardware-alike, bitwise shift/bolean algebra aproach; taken step by step while following the appliable "recipe", and one catches its meanning, as fast it can be written on a sheet of paper.

Tables are good when you have lots of memory space available, and, if not resident (ROM-alike), way more bandwidth, only to set up things before proceeding to any calculation at all.

Can also be someway misleading, from a learning/teaching perspective; they tend to "hide" all the underlying concepts, wrapping all of it inside an indexed table operation, and a bit of "easy-boolean-tricks".

Na good, at all! Brains are convoluted by nature, so, trainning or taming, what an option for the mentored ones...

Yanomani · 2021-09-06 23:45

Better late, than never...

Excellent document; due credits goes to the author(s):

https://electgon.com/publications/digital/crc-hardware/

"That's The Way I Like it" (tks KC & The Sunshine Band)

https://youtube.com/watch?v=aIVkZVDXY_M

CRC8Maxim with CRCBIT doesn't seem to compare with Online CRC Calculators

Comments