How to use CRCBIT and/or CRCNIB for CRC7 (for MMC)?

Rayman · 2020-06-01 19:02

For uSD, you can ignore the CRC, but eMMC is making me use it...

I tried for a second to use the assembly commands CRCNIB and CRCBIT to speed it up.
But, I can't figure it out...

Anybody know how to do this?

Here's my Spin2 version that works:

PUB crc7(buffer,count):r | crc, c,i, j,n 'calculate crc of series of bytes for MMC
    crc := 0
    repeat j from 1 to count
        c := byte[buffer++]        
        'Number of loops is 8 for first bytes, 7 for last byte
        if j==count
            n:=7
        else
            n:=8               
        repeat i from 1 to n
            crc <<= 1
            if c&$80
                crc+=1
            if crc&$80
                crc^=$9
            c<<=1
        crc:=crc & $7F
    r := (crc<<1)+1
    return r

Rayman · 2020-06-01 20:48

Looking at @JonnyMac code, I see what I think is the reverse of the polynomial... Maybe that is the trick I was missing.
http://forums.parallax.com/discussion/171293/crc8

From this page: http://doitwireless.com/2015/05/31/crc-routines/

Cluso99 · 2020-06-01 21:11

Ray,
Your polynomial is $9.
You may have to reverse the byte c before running the rep loop, and the last loop will need to be 7
You should be able to do something like this

  rep     @.done, #8
  shr     c, #1       wc
  crcbit  crc, #$9
.done

Sorry, dont have time to test atm.

or using the crcnib

  shl     c, #24 'get into top byte
  setq    c
  crcnib  crc, #$9
  crcnib  crc, #$9

dartof · 2020-06-01 23:37

The polynomial does indeed need to be reversed since CRCBIT does right shifts instead of left shifts towards the msb. Also, the result is bit-reversed.
With the traditional way of shifting in bits, there needs to be preliminary shifts to load the data into the crc result. Not so with CRCBIT since the
incoming bit and the outgoing bit are xor'd to see if the poly needs xor'ing into the result.

Rayman · 2020-06-02 00:38

Ok, I'm slowly figuring this out...
This website is helpful: http://www.sunshine2k.de/coding/javascript/crc/crc_js.html
I see SMBus is "CRC8_MAXIM" there. The actual polynomial is $31, but we need to use the reversed version, $8C, with the CRCBIT routine, as shown by @JonnyMac
Also, that page says both the input and the output are bit reversed. But, this seems to be done automatically by CRCBIT somehow...

Also, I see a lot of people are using a table to do this... Maybe that's the way to go. I'll just use the LUT, once I figure out how to translate CRC8_MAXIM into CRC7 for MMC...

Or, maybe I can just make the table without actually figuring anything out...

Cluso99 · 2020-06-02 04:56

Ray,
Just use the crcbit or crcnib. You'll be glad you did! Sorry I'm busy at work so I can't get it done for you just now but perhaps later.

Just run a single known character thru the crcnib once (just a nibble( and compare the result with your spin code. Retry with the crc initialised to 0 or $FF, try reversing the characters bits, and the reverse of the polynomial ($31 and $8C). There are not a lot of combinations here and you should find one that matches your spin. BTW Are you sure your spin is correct?

Rayman · 2020-06-02 15:14

The Spin code is correct. The eMMC chip won't talk unless it is correct.

Cluso99 · 2020-06-02 18:38

It’s quite unusual that the last char only uses 7 bits to accumulate in the crc.
I’ll try and find some time to test it with the crcbit crcnib instructions.

Rayman · 2020-06-02 18:48

I think I'm seeing that I need to use the crc with bits inverted and also the result has bits inverted. Maybe that's the clue we need...

Cluso99 · 2020-06-02 22:21

@Rayman
Spent quite some time on this this morning.
I cannot get your code to give the correct results. If you want me to spend any more time on it I need a working program that I can compile with serial output that I can test with. Either pnut or fastspin is fine.

This sequence is a know valid one for SD cards
$40 $00 $00 $00 $00 $95
where $95 is the crc value.
From what I've been able to research, the final crc value calculated is $4A which is then shl #1 and add #1 to give $95.

In hindsight I probably should have gone back to study the algorithm again. I haven't done it since the 80's.

I found this c code but I cannot run it to verify if it works and i don;t understand the "for" statement

#include <stdbool.h>

crc_t crc_update(crc_t crc, const void *data, size_t data_len)
{
    const unsigned char *d = (const unsigned char *)data;
    unsigned int i;
    bool bit;
    unsigned char c;

    while (data_len--) {
        c = *d++;
        for (i = 0x80; i > 0; i >>= 1) {
            bit = crc & 0x40;
            if (c & i) {
                bit = !bit;
            }
            crc <<= 1;
            if (bit) {
                crc ^= 0x09;
            }
        }
        crc &= 0x7f;
    }
    return crc & 0x7f;
}

Cluso99 · 2020-06-02 22:23

This is supposed to be the lookup table, but again I cannot see that it gives the correct results either

/*
 * Table for CRC-7 (polynomial x^7 + x^3 + 1).
 * This is a big-endian CRC (msbit is highest power of x),
 * aligned so the msbit of the byte is the x^6 coefficient
 * and the lsbit is not used.
 */
const u8 crc7_be_syndrome_table[256] = {
	0x00, 0x12, 0x24, 0x36, 0x48, 0x5a, 0x6c, 0x7e,
	0x90, 0x82, 0xb4, 0xa6, 0xd8, 0xca, 0xfc, 0xee,
	0x32, 0x20, 0x16, 0x04, 0x7a, 0x68, 0x5e, 0x4c,
	0xa2, 0xb0, 0x86, 0x94, 0xea, 0xf8, 0xce, 0xdc,
	0x64, 0x76, 0x40, 0x52, 0x2c, 0x3e, 0x08, 0x1a,
	0xf4, 0xe6, 0xd0, 0xc2, 0xbc, 0xae, 0x98, 0x8a,
	0x56, 0x44, 0x72, 0x60, 0x1e, 0x0c, 0x3a, 0x28,
	0xc6, 0xd4, 0xe2, 0xf0, 0x8e, 0x9c, 0xaa, 0xb8,
	0xc8, 0xda, 0xec, 0xfe, 0x80, 0x92, 0xa4, 0xb6,
	0x58, 0x4a, 0x7c, 0x6e, 0x10, 0x02, 0x34, 0x26,
	0xfa, 0xe8, 0xde, 0xcc, 0xb2, 0xa0, 0x96, 0x84,
	0x6a, 0x78, 0x4e, 0x5c, 0x22, 0x30, 0x06, 0x14,
	0xac, 0xbe, 0x88, 0x9a, 0xe4, 0xf6, 0xc0, 0xd2,
	0x3c, 0x2e, 0x18, 0x0a, 0x74, 0x66, 0x50, 0x42,
	0x9e, 0x8c, 0xba, 0xa8, 0xd6, 0xc4, 0xf2, 0xe0,
	0x0e, 0x1c, 0x2a, 0x38, 0x46, 0x54, 0x62, 0x70,
	0x82, 0x90, 0xa6, 0xb4, 0xca, 0xd8, 0xee, 0xfc,
	0x12, 0x00, 0x36, 0x24, 0x5a, 0x48, 0x7e, 0x6c,
	0xb0, 0xa2, 0x94, 0x86, 0xf8, 0xea, 0xdc, 0xce,
	0x20, 0x32, 0x04, 0x16, 0x68, 0x7a, 0x4c, 0x5e,
	0xe6, 0xf4, 0xc2, 0xd0, 0xae, 0xbc, 0x8a, 0x98,
	0x76, 0x64, 0x52, 0x40, 0x3e, 0x2c, 0x1a, 0x08,
	0xd4, 0xc6, 0xf0, 0xe2, 0x9c, 0x8e, 0xb8, 0xaa,
	0x44, 0x56, 0x60, 0x72, 0x0c, 0x1e, 0x28, 0x3a,
	0x4a, 0x58, 0x6e, 0x7c, 0x02, 0x10, 0x26, 0x34,
	0xda, 0xc8, 0xfe, 0xec, 0x92, 0x80, 0xb6, 0xa4,
	0x78, 0x6a, 0x5c, 0x4e, 0x30, 0x22, 0x14, 0x06,
	0xe8, 0xfa, 0xcc, 0xde, 0xa0, 0xb2, 0x84, 0x96,
	0x2e, 0x3c, 0x0a, 0x18, 0x66, 0x74, 0x42, 0x50,
	0xbe, 0xac, 0x9a, 0x88, 0xf6, 0xe4, 0xd2, 0xc0,
	0x1c, 0x0e, 0x38, 0x2a, 0x54, 0x46, 0x70, 0x62,
	0x8c, 0x9e, 0xa8, 0xba, 0xc4, 0xd6, 0xe0, 0xf2

Rayman · 2020-06-02 23:05

I found the c++ code I copied from on this page: https://www.eetimes.com/heres-the-answer-to-crc-7-algorithm-for-the-sd-card/

filename is crc7expl.zip

It seems this kind of thing is ancient history and not so many people still remember how to do it by hand

There is a left shift and a +1 at the very end.
I think that 1 at the end is actually the stop bit, which is why it is not included in the above...

Here is the important part:

/****************/
static unsigned char Encode(unsigned char Seed, unsigned char Input, unsigned char Depth)
/* --
   Produce a 7 bit CRC value Msb first.
  Seed is last round or initial round shift register
	value (lower 7 bits significant).
  Input is an 8 bit value from byte stream being CRCd.
  CRC register is seeded initially with the value 0 prior
   to mixing in the variable packet data.
  Depth is usually 8, but the last time is 7 to shift in
	the augment string of 7 zeros.
*****************/
{
	/*begin-Encode. -
		  local defs: */
	register unsigned char regval;      // shift register byte.
	register unsigned char count;
	register unsigned char cc;          // data to manipulate.
#define POLYNOM (0x9)        // polynomical value to XOR when 1 pops out.

/*BODY*/

	regval = Seed;    // get prior round's register value.
	cc = Input;       // get input byte to generate CRC, MSB first.

	/* msb first of byte for Depth elements */
	for (count = Depth     // set count to 8 or 7.
		; count--        // for count # of bits.
		;  cc <<= 1     // shift input value towards MSB to get next bit.
		)
	{
		// Shift seven bit register left and put in MSB value of input to LSB.
		regval = (regval << 1) + ((cc & 0x80) ? 1 : 0);
		// Test D7 of shift register as MSB of byte, test if 1 and therefore XOR.
		if (regval & 0x80)
			regval ^= POLYNOM;
	} // end byte loop.
	return (regval & 0x7f);    // return lower 7 bits of CRC as value to use.
}
/*...
end-Encode.
.....*/

void CCRC7Dlg::OnBnClickedButton1()
{
	char* cp;     // pointer into command line argument list.
	int walker;    // index into argv parameter list.
	int value, nuval;    // temporary values from cmd line and CRC generator.
	unsigned char CrcAccum; // local storage of each round of CRC.
	UpdateData(true);
	
	//fake command line input
	int argc;
	char argv[100];
	argc = 5;+32;  //#characters  6 +payload
	argv[1] = 64;// +1;  //64==CMD0, 64+1=CMD1
	for (int i=2;i<40;i++)
		argv[i] = 0;  




	// 7 bit shift register CRC computation across 5 byte SD message field
	//   with 6th byte of message being the CRC field generated herein.
	if (argc != (1 + 5))
	{
		//fprintf(stderr, "\nCRC_7 command line syntax error.\n");
		//fprintf(stderr, "Requires 5 argument(s) to encode w/crc value\n");
		//fprintf(stderr, "Usage is :\nCRC_7 0 0 0 0 0\n");
		//fprintf(stderr, " or similar with decimal value for each byte.\n");
		//fprintf(stderr, "  Use CRC_7 64 0 0 0 0\n   to generate example run.\n\n");
		//return 1;
		// EARLY EXIT, CMND LINE SYNTAX ERROR
	}

	// start w/seed of 0 per algorithm.
	CrcAccum = 0;

	// loop through 5 command line decimal values. Display in HEX to
	//  stdout, can be captured via >> on cmdline.
	for (walker = 1; walker < argc; walker++)
	{
		//cp = &argv[walker]; //RJA added &
		value = argv[walker];//RJA changing text to char for input cp;// atoi(cp);
		nuval = Encode(CrcAccum, value, 8);
		//printf(" CRC remainder of 0x%02X for 0x%02X input byte.\n"
		//	, nuval
		//	, value
		//);
		CrcAccum = nuval;    // reload crc accum.
	}

	// mix in last 7 bits of 0s to augment, and then shift final CRC
	//  remainder left and OR in fixed 1 LSB.
	nuval = Encode(CrcAccum, 0, 7);
	value = (nuval << 1) + 1;
	//printf("CRC remainder after augment is 0x%02X with FINAL CRC byte of 0x%02X.\n"
	//	, nuval
	//	, value
	//);
	return;//0;
}

Cluso99 · 2020-06-02 23:12

From discussions I see, it seems that the crc7 implementation was botched. That's not uncommon as Microcom botched the implementation of the CCITT16. I've coded it many times before but I just cannot seem to get this one right. I'm not a c programmer so I cannot be sure I'm converting the c to spin to see how it is working. I'm looking at the basics again to see if I can just do it in pasm.

You need to verify a spin program that takes $40 $00 $00 $00 $00 and gives $65. I can then convert it to pasm and then use the crcbit/crcnib instructions.

Rayman · 2020-06-02 23:25

See above
I think you had it
The shift and 1 at end is the stop bit

Dave Hein · 2020-06-03 00:10

Here's some C code that generates the correct CRC.

#include <stdio.h>

unsigned char crc7(unsigned char *buf, int len)
{
    int i, j;
    unsigned char crc, val;

    crc = 0;
    for (i = 0; i < len; i++)
    {
        val = buf[i];
        for (j = 0; j < 8; j++)
        {
            crc <<= 1;
            if ((val & 0x80) ^ (crc & 0x80))
                crc ^=0x09;
            val <<= 1; 
        }
    }
    crc = (crc << 1) | 1;

    return(crc);
} 

int main()
{
    unsigned char sample1[] = {0x40, 0x00, 0x00, 0x00, 0x00, 0x95};
    unsigned char sample2[] = {0x48, 0x00, 0x00, 0x01, 0xAA, 0x87};

    printf("CRC = %x\n", crc7(sample1, 5));
    printf("CRC = %x\n", crc7(sample2, 5));

    return 0;
}

Rayman · 2020-06-03 00:23

Nice. Looks like a much more compact version of the C code I found...

Dave Hein · 2020-06-03 00:39

Here's the crc7 routine in Spin. I converted it using cspin, but I haven't verified that it generates the correct values.

EDIT: I replaced byte[@crc] with just crc, and masked it to 8 bits at the end.
EDIT2: I also replaced byte[@val] with just val. cspin was trying very hard to maintain 8-bit values.

PUB crc7(buf, len) | i, j, crc, val
  crc := 0
  i := 0
  repeat while (i < len)
    val := byte[buf][i]
    j := 0
    repeat while (j < 8)
      crc <<= 1
      if ((val & $80) ^ (crc & $80))
        crc ^= $09
      val <<= 1
      j++
    i++
  crc := (crc << 1) | 1
  return crc & 255

Rayman · 2020-06-03 00:44

There is working spin2 code in the top post...

Like to make it faster with new crcnib instruction ...

rogloh · 2020-06-03 00:55

Here is something that may help if you want to use CRCBIT (untested, so you may need to validate it, I just took Dave Hein's CRC code and translated it to PASM2). CRCNIB could be faster if that can be used instead. If the FIFO is free that could speed it up instead of the rdbyte too.

    mov     len, ##LENGTH
    mov     ptra, ##STARTADDR
    mov     crc, #0 wc
loop
    rdbyte  data, ptra++
    rep     #2, #8     
    shr     data, #1 wc
    crcbit  crc, #$90 ' reverse of 09 for opposite CRCBIT working order
    djnz    len, #loop
    rev     crc
    shr     crc, #24
    or      crc, #1
EDIT:
    and     crc, #$FF ' for just 7 bit crc shifted after stop bit included.   EDIT2: actually redundant

Cluso99 · 2020-06-03 00:58

@Rayman
The spin code at the top post is not giving the correct result for the initial command 0 which must be $95 but it returns $93

    crc := crc7(@buf2, 5)
    ser.TxHex8(crc)
    ser.TxCR()




PUB crc7(buff,count):r | crc, c,i, j,n 'calculate crc of series of bytes for MMC
    crc := 0
    repeat j from 1 to count
        c := byte[buff++]        
        'Number of loops is 8 for first bytes, 7 for last byte
        if j==count
            n:=7
        else
            n:=8               
        repeat i from 1 to n
            crc <<= 1
            if c&$80
                crc+=1
            if crc&$80
                crc^=$9
            c<<=1
        crc:=crc & $7F
    r := (crc<<1)+1
    return r

DAT
buf2        byte    $40,0,0,0,0,$95

What is happening is that it is getting the wrong input characters

Found a bug in my code - just retrying.

Yes, the crc generated is wrong:(

It also generates the wrong value $1B which should be $87 for the command8

buf8        byte    $48,$00,$00,$01,$AA,$87

Rayman · 2020-06-03 01:00

I think the first byte is actually $40+0

Rayman · 2020-06-03 01:03

I promise it works... Here's the code that calls it:

    'Send command and sometimes get response
    'first, need to calculate CRC7
    cmdout[0]:=$40+op
    cmdout[1]:=(parm>>24)&$FF
    cmdout[2]:=(parm>>16)&$FF
    cmdout[3]:=(parm>>8)&$FF
    cmdout[4]:=(parm>>0)&$FF
    cmdout[5]:=0
    c:=crc7(@cmdout,6)

Rayman · 2020-06-03 01:14

@rogloh That looks like it might work.
I’ll try tomorrow ...
Late here...

Dave Hein · 2020-06-03 01:21

@Rayman, I also got $93 with your code, until I realized that it needs an extra zero at the end. I cleaned up my spin code, and it only needs 5 bytes, and not 6.

PUB crc7(buf, len) : crc | val
  repeat len
    val := byte[buf++]
    repeat 8
      crc <<= 1
      if (val ^ crc) & $80
        crc ^= $09
      val <<= 1
  crc := ((crc << 1) | 1) & 255

Rayman · 2020-06-03 01:22

The sixth byte is always zero and it only does 7 bits of crc on it...

Dave Hein · 2020-06-03 01:31

Yes, I see that, but it's a little less efficient to do it that way.

rogloh · 2020-06-03 01:34

Yeah give it a go if you want try to use inline PASM2 in your SPIN2 for this. Only 22 clocks plus rdbyte delay per byte (unless you can use the fifo which would speed it up to perhaps 24 clocks per byte total in the main loop one the fifo is primed.

An alternate CRCNIB may speed this up even more. I'm just not 100% sure what the xx values are. Maybe they are just the same as the single bit case and the HW just figures it out for you. This could then be as fast as 14 clocks per byte if the fifo is used.

    mov     len, ##LENGTH
    mov     ptra, ##STARTADDR
    mov     crc, #0 wc
loop
    rdbyte  data, ptra++
    rev     data
    setq    data
    crcnib  crc, #xx ' what constant value to use?
    crcnib  crc, #xx
    djnz    len, #loop
    rev     crc
    shr     crc, #24
    or      crc, #1

Cluso99 · 2020-06-03 02:10

That 6th $0 byte was it. Spent hours on this

I'll try crcnib now

Rayman · 2020-06-03 14:45

@rogloh I can't make this last code work... I'll try the first...

Ariba · 2020-06-03 19:07

This Spin2 code seems to work:

PUB crc7(buf, len) : crc | i,val
    repeat i from 0 to len-1
        val := byte[buf][i] << 24
        org
            setq    val
            crcnib  crc,#$90>>1
            crcnib  crc,#$90>>1
        end
    return (crc rev 6) << 1 | 1

or with the outer loop also in PASM:

PUB crc7(buf, len) : crc | val
  org
  cr7lp   rdbyte  val,buf
          add     buf,#1
          shl     val,#24
          setq    val
          crcnib  crc,#$90>>1
          crcnib  crc,#$90>>1
          djnz    len,#cr7lp
  end
  return (crc rev 6) << 1 | 1

Andy

Rayman · 2020-06-03 20:24

Thanks Andy, I'll try that.

I think I'm seeing that I got hung up by the code I found and that last 7 bits of zero it does.
Although it works, it is unlike all the other code...

Now, I have code that just works on the first 5 bytes and doesn't have that dummy 6th byte:

PUB crc7_c(buffer,count):r | crc, c,i, j,n,len 'calculate crc of series of bytes for MMC
    crc := 0
    repeat j from 1 to count-1
        c := byte[buffer++]               
        repeat i from 1 to 8
            crc <<= 1
            if ((c^crc)&$80)>0
                crc^=$9
            c<<=1
        crc:=crc & $7F
    r := (crc<<1)+1
    return r

Was just about to figure this all out, but maybe Andy beat me to it...
Or, maybe @"Dave Hein" or @rogloh would work this way too...

How to use CRCBIT and/or CRCNIB for CRC7 (for MMC)?

Comments