#1 2016-05-24 23:24:19

necrozlover
Учасник
Зареєстрований: 2016-04-25
Повідомлень: 9

Подсчет 1-Wire crc

Уже неделю пытаюсь понять алгоритм и вообще что делать для подсчета избыточной циклической суммы. Дело в том что я пишу библиотеку для связи по протоколу 1-Wire.... Собственно мне нужно понимать алгоритм подсчета CRC
Полином CRC=X^8+X^5+X4+1
Циклическая сумма высчитывается из 7 байт
Допустим моё сообщение "10110101000000000000000000000110011011000000101111101000"
Мне нужно моё сообщение поделить по модулю - 2 моё сообщение на двоичное число. Какое это число ?? Как мне перевести в двоичное число X^8+X^5+X4+1 ?
Это 2^8+2^5+2^4+1 выходит ? Выходит 305 в десятичном или 100110001 в двоичном ?
Пытался делить в ручную - не совпало.

Полином:100110001
CRC сумма от приёмника:00101000
Моё сообщение (56 бит или 7 байт):
10110101000000000000000000000110011011000000101111101000
остача от деления:01101011 (не совпадает с CRC от приёмника)
1011010100000000000000000000011001101100000010111110100000000000		
100110001........................~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
---------........................
 010110110.......................
 000000000.......................
 ---------.......................
  101101100......................
  100110001......................
  ---------......................
   010111010.....................
   000000000.....................
   ---------.....................
    101110100....................
    100110001....................
    ---------....................
     010001010...................
     000000000...................
     ---------...................
      100010100..................
      100110001..................
      ---------..................
       001001010.................
       000000000.................
       ---------.................
        010010100................
	000000000................
	---------................
	 100101000...............
	 100110001...............
	 ---------...............
	  000110010..............
	  000000000..............
	  ---------..............
	   001100100.............
	   000000000.............
	   ---------.............
	    011001000............
	    000000000............
	    ---------............
	     110010000...........
	     100110001...........
	     ---------...........
	      101000010..........
	      100110001..........
	      ---------..........
	       011100110.........
	       000000000.........
	       ---------.........
	        111001100........
		100110001........
		---------........
		 111111010.......
		 100110001.......
		 ---------.......
		  110010110......
		  100110001......
		  ---------......
		   101001110.....
		   100110001.....
		   ---------.....
		    011111110....
		    000000000....
		    ---------....
		     111111101...
		     100110001...
		     ---------...
		      110011001..
		      100110001..
		      ---------..
		       101010000.
		       100110001.
		       ---------.
		        011000010
			000000000
			---------
			 110000101
			 100110001
			 ---------
			  101101011
			  100110001
			  ---------
			   010110100
			   000000000
			   ---------
			    101101001
			    100110001
			    ---------
			     010110001
			     000000000
			     ---------
			      101100010
			      100110001
			      ---------
			       010100110
			       000000000
			       ---------
			        101001100
				100110001
				---------
				 011111010
				 000000000
				 ---------
				  111110100
				  100110001
				  ---------
				   110001010
				   100110001
				   ---------
				    101110111
				    100110001
				    ---------
				     010001100
				     000000000
				     ---------
				      100011001
	    			      100110001
				      ---------
				       001010001
				       000000000
				       ---------
				        010100011
					000000000
					---------
					 101000111
					 100110001
					 ---------
					  011101101
					  000000000
					  ---------
					   111011010
					   100110001
					   ---------
					    111010111
					    100110001
					    ---------
					     111001100
					     100110001
					     ---------
					      111111010
					      100110001
					      ---------
					       110010110
					       100110001
					       ---------
					        101001110
						100110001
						---------
						 011111110
						 000000000
						 ---------
						  111111100
						  100110001
						  ---------
						   110011010
						   100110001
						   ---------
						    101010110
						    100110001
						    ---------
						     011001110
						     000000000
						     ---------
						      110011100
						      100110001
						      ---------
						       101011010
						       100110001
						       ---------
							01101011
					   
				  
		  

Остання редакція necrozlover (2016-05-24 23:25:33)

Неактивний

#2 2016-05-25 09:29:26

NoName
Customer
З Київ
Зареєстрований: 2014-07-08
Повідомлень: 1,446

Неактивний

#3 2016-05-25 09:32:24

NoName
Customer
З Київ
Зареєстрований: 2014-07-08
Повідомлень: 1,446

Re: Подсчет 1-Wire crc

DALLAS 1-Wire CRC8?
я правильно угадал ?

/* Подсчет CRC8 массива mas длиной Len */
unsigned char calc_crc( unsigned char *mas, unsigned char Len )
{
  unsigned char i,dat,crc,fb,st_byt;
  st_byt=0; crc=0;
  do{
    dat=mas[st_byt];
    for( i=0; i<8; i++) {  // счетчик битов в байте
      fb = crc ^ dat;
      fb &= 1;
      crc >>= 1;
      dat >>= 1;
      if( fb == 1 ) crc ^= 0x8c; // полином
    }
    st_byt++;
  } while( st_byt < Len ); // счетчик байтов в массиве
  return crc;
}

http://www.microchip.su/showthread.php?t=11678

Неактивний

#4 2016-05-25 12:51:01

necrozlover
Учасник
Зареєстрований: 2016-04-25
Повідомлень: 9

Re: Подсчет 1-Wire crc

Спасибо ребята, попробую код ваш использовать. Я бывал на всех этих ссылках - но толком для себя ничё не понял sad

Неактивний

#5 2016-05-25 13:07:24

NoName
Customer
З Київ
Зареєстрований: 2014-07-08
Повідомлень: 1,446

Re: Подсчет 1-Wire crc

много информации по crc ну и бардака там тоже дофига  )
http://www.info-system.ru/library/algo/crc1.pdf

доступно описан принцип
http://www.piclist.ru/S-CRC16-RUS/CRC16.html

Неактивний

#6 2016-05-25 17:09:28

necrozlover
Учасник
Зареєстрований: 2016-04-25
Повідомлень: 9

Re: Подсчет 1-Wire crc

Да у меня даже онлайн подсчет что то не то выдает или (скорее всего) я ему неправильно подаю данные.
У меня есть датчик: DS18B20 (Hex код: 28). Я сам написал пару функций которые смогли считать последовательность байт.

Я уже пробовал отправлять на онлайн подчет - и сумма не сходится с моей sad
Видимо я не правильные данные подаю.
Вот сообщение с моего датчика, 8 байт. Последний байт - CRC
00101000111010000000101101101100000001100000000000000000010110101
Его я переводил в HEX и проверял (без последнего байта, конечно) - ничё.
Пробовал тоже самое, но без лишних нулей в старших разрядах байтов:
10100011101000101111011001100010110101
Тоже не считает, так как надо.
Подкажите что именно я должен передавать в онлайн калькулятор что бы получить верный ответ.
101000             =28    (1-й байт)
11101000         =E8     (2-й байт)
1011                =B     (3-й байт)
1101100           =6C   (4-й байт)
110                  =6     (5-й байт)
0                      =0     (6-й байт)
0                      =0     (7-й байт)
10110101          =B5   (8-й байт) - собственно сам CRC

Неактивний

#7 2016-05-25 17:22:38

necrozlover
Учасник
Зареєстрований: 2016-04-25
Повідомлень: 9

Re: Подсчет 1-Wire crc

NoName пише:

много информации по crc ну и бардака там тоже дофига  )
http://www.info-system.ru/library/algo/crc1.pdf

Прочитал половину и понял только половину
А за вторую ссылку - спасибо. Буду читать

Неактивний

#8 2016-05-25 17:50:32

NoName
Customer
З Київ
Зареєстрований: 2014-07-08
Повідомлень: 1,446

Re: Подсчет 1-Wire crc

https://github.com/PaulStoffregen/OneWi … neWire.cpp

если подходит  - разберите его

#if ONEWIRE_CRC8_TABLE
// This table comes from Dallas sample code where it is freely reusable,
// though Copyright (C) 2000 Dallas Semiconductor Corporation
static const uint8_t PROGMEM dscrc_table[] = {
      0, 94,188,226, 97, 63,221,131,194,156,126, 32,163,253, 31, 65,
    157,195, 33,127,252,162, 64, 30, 95,  1,227,189, 62, 96,130,220,
     35,125,159,193, 66, 28,254,160,225,191, 93,  3,128,222, 60, 98,
    190,224,  2, 92,223,129, 99, 61,124, 34,192,158, 29, 67,161,255,
     70, 24,250,164, 39,121,155,197,132,218, 56,102,229,187, 89,  7,
    219,133,103, 57,186,228,  6, 88, 25, 71,165,251,120, 38,196,154,
    101, 59,217,135,  4, 90,184,230,167,249, 27, 69,198,152,122, 36,
    248,166, 68, 26,153,199, 37,123, 58,100,134,216, 91,  5,231,185,
    140,210, 48,110,237,179, 81, 15, 78, 16,242,172, 47,113,147,205,
     17, 79,173,243,112, 46,204,146,211,141,111, 49,178,236, 14, 80,
    175,241, 19, 77,206,144,114, 44,109, 51,209,143, 12, 82,176,238,
     50,108,142,208, 83, 13,239,177,240,174, 76, 18,145,207, 45,115,
    202,148,118, 40,171,245, 23, 73,  8, 86,180,234,105, 55,213,139,
     87,  9,235,181, 54,104,138,212,149,203, 41,119,244,170, 72, 22,
    233,183, 85, 11,136,214, 52,106, 43,117,151,201, 74, 20,246,168,
    116, 42,200,150, 21, 75,169,247,182,232, 10, 84,215,137,107, 53};

//
// Compute a Dallas Semiconductor 8 bit CRC. These show up in the ROM
// and the registers.  (note: this might better be done without to
// table, it would probably be smaller and certainly fast enough
// compared to all those delayMicrosecond() calls.  But I got
// confused, so I use this table from the examples.)
//
uint8_t OneWire::crc8(const uint8_t *addr, uint8_t len)
{
	uint8_t crc = 0;

	while (len--) {
		crc = pgm_read_byte(dscrc_table + (crc ^ *addr++));
	}
	return crc;
}
#else
//
// Compute a Dallas Semiconductor 8 bit CRC directly.
// this is much slower, but much smaller, than the lookup table.
//
uint8_t OneWire::crc8(const uint8_t *addr, uint8_t len)
{
	uint8_t crc = 0;

	while (len--) {
#if defined(__AVR__)
		crc = _crc_ibutton_update(crc, *addr++);
#else
		uint8_t inbyte = *addr++;
		for (uint8_t i = 8; i; i--) {
			uint8_t mix = (crc ^ inbyte) & 0x01;
			crc >>= 1;
			if (mix) crc ^= 0x8C;
			inbyte >>= 1;
		}
#endif
	}
	return crc;
}
#endif

полином 0x8C
этот код разбирали?

Неактивний

#9 2016-05-25 17:54:06

NoName
Customer
З Київ
Зареєстрований: 2014-07-08
Повідомлень: 1,446

Re: Подсчет 1-Wire crc

00101000
11101000
00001011
01101100
00000110
00000000
000000000
10110101

входные данные неверны

Неактивний

#10 2016-05-25 18:11:51

necrozlover
Учасник
Зареєстрований: 2016-04-25
Повідомлень: 9

Re: Подсчет 1-Wire crc

NoName пише:

00101000
11101000
00001011
01101100
00000110
00000000
000000000
10110101

входные данные неверны

Спасибо за ответ...... Пожалуй отдохну денек и начну всё заново копать

Неактивний

#11 2021-01-13 11:41:27

tolyan23
Учасник
Зареєстрований: 2021-01-13
Повідомлень: 1

Re: Подсчет 1-Wire crc

В общем была такая же проблема. Может кому то пригодится, а может потом забуду и тут опять найду)
Итак, есть подробная статья https://www.maximintegrated.com/en/design/technical-documents/app-notes/2/27.html
Полином X^8+X^5+X4+1  равен 0b100110001 в двоичной форме. Старший бит отбрасывают получаем 0х31
Если мы побитно считаем, сдвигаем влево данные - получаем бит, сдвигаем влево CRC (для даласа crc изначально заполнено нулями) получаем еще один бит. Теперь между битами производим xor (логическое или) и если результат 1 (это будет когда один бит 1 а второй 0) то делаем CRC xor полином, но полином для даласа нужно вывернуть задом наперед и 0x31=0b00110001 превращается в 0b10001100. (если мы начальное значение CRC ставим не нулевое оно тоже выворачивается)
Вы берете со старшего бита а надо с младшего. в итоге последовательности бит 0 0 0 1 0 1 1 1
0 CRC=0 вот тут внимание если CRC мы инициализируем не нулем (0x71 например мы выворачиваем 0x71 и пишем CRC=0x8F)
0 CRC=0
0 CRC=0
1 CRC=0b10001100 выполняем xor входной бит 1 перенос 0
0 CRC=0b01000110
1 CRC=0b10101111 xor не выполняет оба бита =1
1 CRC=0b01010111 xor не выполняет оба бита =1
1 CRC=0b00101011 xor не выполняет оба бита =1
Для того чтобы посчитать на онлайн калькуляторе ставим crc8 полином 0x31 инициализация CRC 0x00 и две галочики инвертировать чего то там и чего то там.

и так далее

necrozlover пише:

Уже неделю пытаюсь понять алгоритм и вообще что делать для подсчета избыточной циклической суммы. Дело в том что я пишу библиотеку для связи по протоколу 1-Wire.... Собственно мне нужно понимать алгоритм подсчета CRC
Полином CRC=X^8+X^5+X4+1
Циклическая сумма высчитывается из 7 байт
Допустим моё сообщение "10110101000000000000000000000110011011000000101111101000"
Мне нужно моё сообщение поделить по модулю - 2 моё сообщение на двоичное число. Какое это число ?? Как мне перевести в двоичное число X^8+X^5+X4+1 ?
Это 2^8+2^5+2^4+1 выходит ? Выходит 305 в десятичном или 100110001 в двоичном ?
Пытался делить в ручную - не совпало.

Полином:100110001
CRC сумма от приёмника:00101000
Моё сообщение (56 бит или 7 байт):
10110101000000000000000000000110011011000000101111101000
остача от деления:01101011 (не совпадает с CRC от приёмника)
1011010100000000000000000000011001101100000010111110100000000000		
100110001........................~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
---------........................
 010110110.......................
 000000000.......................
 ---------.......................
  101101100......................
  100110001......................
  ---------......................
   010111010.....................
   000000000.....................
   ---------.....................
    101110100....................
    100110001....................
    ---------....................
     010001010...................
     000000000...................
     ---------...................
      100010100..................
      100110001..................
      ---------..................
       001001010.................
       000000000.................
       ---------.................
        010010100................
	000000000................
	---------................
	 100101000...............
	 100110001...............
	 ---------...............
	  000110010..............
	  000000000..............
	  ---------..............
	   001100100.............
	   000000000.............
	   ---------.............
	    011001000............
	    000000000............
	    ---------............
	     110010000...........
	     100110001...........
	     ---------...........
	      101000010..........
	      100110001..........
	      ---------..........
	       011100110.........
	       000000000.........
	       ---------.........
	        111001100........
		100110001........
		---------........
		 111111010.......
		 100110001.......
		 ---------.......
		  110010110......
		  100110001......
		  ---------......
		   101001110.....
		   100110001.....
		   ---------.....
		    011111110....
		    000000000....
		    ---------....
		     111111101...
		     100110001...
		     ---------...
		      110011001..
		      100110001..
		      ---------..
		       101010000.
		       100110001.
		       ---------.
		        011000010
			000000000
			---------
			 110000101
			 100110001
			 ---------
			  101101011
			  100110001
			  ---------
			   010110100
			   000000000
			   ---------
			    101101001
			    100110001
			    ---------
			     010110001
			     000000000
			     ---------
			      101100010
			      100110001
			      ---------
			       010100110
			       000000000
			       ---------
			        101001100
				100110001
				---------
				 011111010
				 000000000
				 ---------
				  111110100
				  100110001
				  ---------
				   110001010
				   100110001
				   ---------
				    101110111
				    100110001
				    ---------
				     010001100
				     000000000
				     ---------
				      100011001
	    			      100110001
				      ---------
				       001010001
				       000000000
				       ---------
				        010100011
					000000000
					---------
					 101000111
					 100110001
					 ---------
					  011101101
					  000000000
					  ---------
					   111011010
					   100110001
					   ---------
					    111010111
					    100110001
					    ---------
					     111001100
					     100110001
					     ---------
					      111111010
					      100110001
					      ---------
					       110010110
					       100110001
					       ---------
					        101001110
						100110001
						---------
						 011111110
						 000000000
						 ---------
						  111111100
						  100110001
						  ---------
						   110011010
						   100110001
						   ---------
						    101010110
						    100110001
						    ---------
						     011001110
						     000000000
						     ---------
						      110011100
						      100110001
						      ---------
						       101011010
						       100110001
						       ---------
							01101011
					   
				  
		  

Остання редакція tolyan23 (2021-01-13 11:43:30)

Неактивний

#12 2021-01-13 21:23:12

Honey
Учасник
З Київ
Зареєстрований: 2020-09-26
Повідомлень: 412

Re: Подсчет 1-Wire crc

В 1-wire есть две разные контрольные суммы, одна 8-битная, используется на сетевом уровне (для адресов устройств), а вторая 16-битная, используется на прикладном уровне (для данных).

Посмотрите в заголовочном файле /usr/avr/include/util/crc16.h
8-битная называется _crc_ibutton_update(), 16-битная называется _crc16_update(), там есть и код на C и оптимизированый код на ASM для AVR.

Пример использования кода на C:

#include <stdio.h>
#include <stdint.h>

uint8_t crc8(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;
}

int main() {
    uint8_t addr[8] = {0x28, 0xe8, 0x0b, 0x6c, 0x06, 0x00, 0x00};
    uint8_t i, crc = 0;

    for (i = 0; i < 7; i++)
        crc = crc8(crc, addr[i]);
    addr[i] = crc;

    printf("%02x%02x%02x%02x%02x%02x%02x%02xn",
        addr[0], addr[1], addr[2], addr[3], addr[4], addr[5], addr[6], addr[7]);
}

Т.к. фактически алгоритм производит преобразование над результатом (crc ^ data), то можно заранее просчитать для всех значений и сделать табличный вариант:

#include <stdio.h>
#include <stdint.h>

uint8_t crc_tab[256] = {
      0, 94,188,226, 97, 63,221,131,194,156,126, 32,163,253, 31, 65,
    157,195, 33,127,252,162, 64, 30, 95,  1,227,189, 62, 96,130,220,
     35,125,159,193, 66, 28,254,160,225,191, 93,  3,128,222, 60, 98,
    190,224,  2, 92,223,129, 99, 61,124, 34,192,158, 29, 67,161,255,
     70, 24,250,164, 39,121,155,197,132,218, 56,102,229,187, 89,  7,
    219,133,103, 57,186,228,  6, 88, 25, 71,165,251,120, 38,196,154,
    101, 59,217,135,  4, 90,184,230,167,249, 27, 69,198,152,122, 36,
    248,166, 68, 26,153,199, 37,123, 58,100,134,216, 91,  5,231,185,
    140,210, 48,110,237,179, 81, 15, 78, 16,242,172, 47,113,147,205,
     17, 79,173,243,112, 46,204,146,211,141,111, 49,178,236, 14, 80,
    175,241, 19, 77,206,144,114, 44,109, 51,209,143, 12, 82,176,238,
     50,108,142,208, 83, 13,239,177,240,174, 76, 18,145,207, 45,115,
    202,148,118, 40,171,245, 23, 73,  8, 86,180,234,105, 55,213,139,
     87,  9,235,181, 54,104,138,212,149,203, 41,119,244,170, 72, 22,
    233,183, 85, 11,136,214, 52,106, 43,117,151,201, 74, 20,246,168,
    116, 42,200,150, 21, 75,169,247,182,232, 10, 84,215,137,107, 53
};

int main() {
    uint8_t addr[8] = {0x28, 0xe8, 0x0b, 0x6c, 0x06, 0x00, 0x00};
    uint8_t i, crc = 0;

    for (i = 0; i < 7; i++)
        crc = crc_tab[crc ^ addr[i]];
    addr[i] = crc;

    printf("%02x%02x%02x%02x%02x%02x%02x%02xn",
        addr[0], addr[1], addr[2], addr[3], addr[4], addr[5], addr[6], addr[7]);
}

Оба кода выводят одинаковый результат для Вашего примера:
28e80b6c060000b5

При компиляции для МК просто подключаете заголовочный файл и используете готовую функцию.

Неактивний

Швидке повідомлення

Введіть повідомлення і натисніть Надіслати

Підвал форуму