Wiedza tam zawarta jest naprawdę bardzo ciekawa, ale jest jej za dużo... Mnie czytanie tego poradnika wprawiło jedynie w frustrację. Potrzebowałem jedynie zaimplementować CRC, a czytałem o jakiś metodach przy słowie dziesiętnym, co to jest XOR... a na końcu metody były, tylko że było ich z ~5 i nie wiedziałem którą wybrać.
Z kolei dokument Maxima w rozdziale "Cyclic Redundancy Check" zawierał to (i jedynie to) czego potrzebowałem, aby zrozumieć co mam zrobić, aby dobrze zaimplementować CRC. I to on do mnie trafił, kiedy poradnik mg101 niestety tego nie potrafił
-- 12 sie 2013, o 11:51 --
Optymalizacja przez tablicowanie
Metoda bit-po-bicie jest metodą najprostszą w implementacji, zajmującą najmniej FLASHa oraz najwolniejszą (no bo nic w życiu nie może być proste
). Obliczanie CRC można przyśpieszyć poprzez przygotowanie tablicy w której będziemy mieć wartość z którą będziemy XORować rejestr w zależności od wartości bitów, które robią "wypad".Wzorem:
Bcrc = Bo + Bp
gdzie:
Bcrc - ilość bitów rejestru CRC
Bo - ilość bitów, których "wypad" będziemy optymalizować (od MSB do LSB)
Bp - bity, które pozostaną w rejestrze (od LSB do MSD)
Należy pamiętać, że nie interesuje nas wartość bitów Bp, a jedynie wartość z jaką będą one XORowane.
Pseudokodem C można zapisać to tak:
Bcrc=0bBoBp;
Mechanizm optymalizacji opiera się na tym, że jeżeli mamy 16bitowe CRC i wprowadzamy do niego bajt (8bitów) to sekwencja XORowania rejestru kluczem jest zależna jedynie od najstarszych 8bitów rejestru (czyli tych, które zrobią "wypad"). Sekwencję tą można zoptymalizować do postaci:
XORoptymalizacji=(XOR0<<0)^(XOR1<<1)^(XOR2<<2)........
W praktyce polega to na stablicowaniu wszystkich możliwości bitów Bo za pomocą następującego algorytmu:
1. Ustawiamy rejestr CRC na wartość:
Bo - obecnie sprawdzana wartość
Bp - wszystkie na zero
2. Dodajemy do rejestru tyle "0" ile jest Bo (tak jak zwykłe dane)
3. W rejestrze czeka na nas nasz XORoptymalizacji
Podany algorytm realizuje poniższa funkcja:
[syntax=c]voidcrc_table_generator(const u08 number_of_bits)
{
for (Tcrc x=0; x<((Tcrc)1<<number_of_bits); x++)
{
crc=(Tcrc)x<<(current_length-number_of_bits+1);
for (u08 y=0; y<number_of_bits; y++) crc_add_bit(0);
{
/*
*Tutaj musimy zapisac stan rejestru (zmienna crc) dla danego indexu tablicy (zmienna x)
*/
}
}
}[/syntax]
Przed jej wywołaniem inicjalizujemy bibliotekę funkcją crc_init(...), a następnie wywołujemy naszą nową funkcję podając jako parametr ilość bitów które chcemy optymalizować.
Mądrze będzie wyrzucić wyliczone wartości na jakiś terminal, aby wygodnie skopiować je do kodu programu.
Skoro mamy już mamy naszą tablicę z wyliczonymi sekwencjami XORowania rejestru (zastępującą klucz w metodzie bit-po-bicie) musimy jeszcze przerobić funkcję dodającą bajt do CRC, tak aby była w stanie wykorzystać nową optymalizację
Zakładając, że będziemy korzystać tylko z CRC16 i przygotowaliśmy tablicę dla Bo=8, funkcja może wyglądać tak:
[syntax=c]voidcrc_add_byte(u08 byte)
{
Tcrc get_table_element (const u08 table_index)
{
Tcrc ret=0;
for (u08 x=0; x<2; x++) ret=(ret<<8)|pgm_read_byte(&tablica_z_wyliczonymi_wartosciami[table_index*2+x]);
return ret;
}
crc=(((Tcrc)crc<<8)|byte)^get_table_element(crc>>8);
}[/syntax]
Czyli do rejestru jest dodawany nowy bajt, a potem rejestr jest XORowany wartością zapisaną pod indeksem tablicy będącym bajtem, który zaliczył "wypad" z rejestru.
Kilka właściwości:
1. Możliwe jest wykorzystanie tablicy przygotowanej dla n bitów podczas dodawania m<=n bitów.
Dowód
Bo_m=3
Bo_n=5
Stan wejściowy CRC (przy generowaniu tablic dla takich ilości bitów i wartości bitów Bo = 3 (0b011)), rejestr CRC 8 bitowy:
CRC_m=0b01100000; // 3x"0"
CRC_n=0b00011000; // 5x"0"
Po dodawaniu zer tak długo, aż następnym bitem, który zrobi "wypad" będzie "1" uzyskamy
CRC_m=0b11100000; // 2x"0" - wsunęliśmy 1 bit
CRC_n=0b11100000; // 2x"0" - wsunęliśmy 3 bity, wartości rejestrów zrównały się
2. Możliwe jest stosowanie tablicy optymalizacji obliczonej dla Klucza1, dla Klucza2, jeżeli K2 ma mniej bitów niż K1 i ich wartości są identyczne z tymi klucza K1 (aż do końca bitów K2, potem bez znaczenia).
3. Szybkość konwersji skaluje się prawie liniowo do ilości bitów optymalizacji:
Szybkość=Szybkość_bit_po_bicie*Bo
Zajętość pamięci niestety rośnie wykładniczo:
FLASH=(rozmiar_rejestru)*(2^Bo)
Nowe kody:
bCRCnoInit.h (kompilator narzekał na niewykorzystane definicje i deklaracje)
[syntax=c]/*
*Cyclic Redundance Check calculation
* Created on: 10-08-2013v1
*Author: barney
*forum.atnel.pl
*/
#include "../common.h"
#ifndef BCRCNOINIT_H_
#define BCRCNOINIT_H_
typedef u16 Tcrc;// Maximum crc size
voidcrc_add_byte(u08 byte);
Tcrccrc_read(void);
#endif /* BCRCNOINIT_H_ */[/syntax]
bCRC.h
[syntax=c]/*
*Cyclic Redundance Check calculation
* Created on: 10-08-2013v1
*Author: barney
*forum.atnel.pl
*/
#include "bCRCnoInit.h"
#include <avr/pgmspace.h>
#ifndef CRC_H_
#define CRC_H_
extern const u08 crc16_table [256] [2] PROGMEM;
static inline u08 log2b (u16 x)
{
u08 ret=0;
while ((x>>=1)) ret++;
return ret;
}
#define CRC_RST0,(Tcrc)0,0,0,0
#define CRC77,(Tcrc) 0b10001001/* x^7 + x^3 + x^0 */,0,0,0
#define CRC1616,(Tcrc) 0b10001000000100001/* x^16+ x^12+ x^5+ x^0 */,crc16_table,log2b(sizeof(crc16_table)/sizeof(crc16_table[0])),sizeof(crc16_table[0])
/*
*If length==0 then only re-init.
*/
voidcrc_init(const u08 length, const Tcrc polynomial, const void const *table, const u08 table_bits, const u08 table_element_size);// If length==0 then only re-init.
//voidcrc_table_generator(u08 number_of_bits);
#endif /* CRC_H_ */[/syntax]
[syntax=c]bCRC.c
/*
*Cyclic Redundance Check calculation
* Created on: 10-08-2013v1
*Author: barney
*forum.atnel.pl
*/
#include "bCRC.h"
const u08 crc16_table [256] [2] PROGMEM =
{
{0b00000000, 0b00000000},// 000
{0b00010000, 0b00100001},// 001
{0b00100000, 0b01000010},// 002
{0b00110000, 0b01100011},// 003
{0b01000000, 0b10000100},// 004
{0b01010000, 0b10100101},// 005
{0b01100000, 0b11000110},// 006
{0b01110000, 0b11100111},// 007
{0b10000001, 0b00001000},// 008
{0b10010001, 0b00101001},// 009
{0b10100001, 0b01001010},// 010
{0b10110001, 0b01101011},// 011
{0b11000001, 0b10001100},// 012
{0b11010001, 0b10101101},// 013
{0b11100001, 0b11001110},// 014
{0b11110001, 0b11101111},// 015
{0b00010010, 0b00110001},// 016
{0b00000010, 0b00010000},// 017
{0b00110010, 0b01110011},// 018
{0b00100010, 0b01010010},// 019
{0b01010010, 0b10110101},// 020
{0b01000010, 0b10010100},// 021
{0b01110010, 0b11110111},// 022
{0b01100010, 0b11010110},// 023
{0b10010011, 0b00111001},// 024
{0b10000011, 0b00011000},// 025
{0b10110011, 0b01111011},// 026
{0b10100011, 0b01011010},// 027
{0b11010011, 0b10111101},// 028
{0b11000011, 0b10011100},// 029
{0b11110011, 0b11111111},// 030
{0b11100011, 0b11011110},// 031
{0b00100100, 0b01100010},// 032
{0b00110100, 0b01000011},// 033
{0b00000100, 0b00100000},// 034
{0b00010100, 0b00000001},// 035
{0b01100100, 0b11100110},// 036
{0b01110100, 0b11000111},// 037
{0b01000100, 0b10100100},// 038
{0b01010100, 0b10000101},// 039
{0b10100101, 0b01101010},// 040
{0b10110101, 0b01001011},// 041
{0b10000101, 0b00101000},// 042
{0b10010101, 0b00001001},// 043
{0b11100101, 0b11101110},// 044
{0b11110101, 0b11001111},// 045
{0b11000101, 0b10101100},// 046
{0b11010101, 0b10001101},// 047
{0b00110110, 0b01010011},// 048
{0b00100110, 0b01110010},// 049
{0b00010110, 0b00010001},// 050
{0b00000110, 0b00110000},// 051
{0b01110110, 0b11010111},// 052
{0b01100110, 0b11110110},// 053
{0b01010110, 0b10010101},// 054
{0b01000110, 0b10110100},// 055
{0b10110111, 0b01011011},// 056
{0b10100111, 0b01111010},// 057
{0b10010111, 0b00011001},// 058
{0b10000111, 0b00111000},// 059
{0b11110111, 0b11011111},// 060
{0b11100111, 0b11111110},// 061
{0b11010111, 0b10011101},// 062
{0b11000111, 0b10111100},// 063
{0b01001000, 0b11000100},// 064
{0b01011000, 0b11100101},// 065
{0b01101000, 0b10000110},// 066
{0b01111000, 0b10100111},// 067
{0b00001000, 0b01000000},// 068
{0b00011000, 0b01100001},// 069
{0b00101000, 0b00000010},// 070
{0b00111000, 0b00100011},// 071
{0b11001001, 0b11001100},// 072
{0b11011001, 0b11101101},// 073
{0b11101001, 0b10001110},// 074
{0b11111001, 0b10101111},// 075
{0b10001001, 0b01001000},// 076
{0b10011001, 0b01101001},// 077
{0b10101001, 0b00001010},// 078
{0b10111001, 0b00101011},// 079
{0b01011010, 0b11110101},// 080
{0b01001010, 0b11010100},// 081
{0b01111010, 0b10110111},// 082
{0b01101010, 0b10010110},// 083
{0b00011010, 0b01110001},// 084
{0b00001010, 0b01010000},// 085
{0b00111010, 0b00110011},// 086
{0b00101010, 0b00010010},// 087
{0b11011011, 0b11111101},// 088
{0b11001011, 0b11011100},// 089
{0b11111011, 0b10111111},// 090
{0b11101011, 0b10011110},// 091
{0b10011011, 0b01111001},// 092
{0b10001011, 0b01011000},// 093
{0b10111011, 0b00111011},// 094
{0b10101011, 0b00011010},// 095
{0b01101100, 0b10100110},// 096
{0b01111100, 0b10000111},// 097
{0b01001100, 0b11100100},// 098
{0b01011100, 0b11000101},// 099
{0b00101100, 0b00100010},// 100
{0b00111100, 0b00000011},// 101
{0b00001100, 0b01100000},// 102
{0b00011100, 0b01000001},// 103
{0b11101101, 0b10101110},// 104
{0b11111101, 0b10001111},// 105
{0b11001101, 0b11101100},// 106
{0b11011101, 0b11001101},// 107
{0b10101101, 0b00101010},// 108
{0b10111101, 0b00001011},// 109
{0b10001101, 0b01101000},// 110
{0b10011101, 0b01001001},// 111
{0b01111110, 0b10010111},// 112
{0b01101110, 0b10110110},// 113
{0b01011110, 0b11010101},// 114
{0b01001110, 0b11110100},// 115
{0b00111110, 0b00010011},// 116
{0b00101110, 0b00110010},// 117
{0b00011110, 0b01010001},// 118
{0b00001110, 0b01110000},// 119
{0b11111111, 0b10011111},// 120
{0b11101111, 0b10111110},// 121
{0b11011111, 0b11011101},// 122
{0b11001111, 0b11111100},// 123
{0b10111111, 0b00011011},// 124
{0b10101111, 0b00111010},// 125
{0b10011111, 0b01011001},// 126
{0b10001111, 0b01111000},// 127
{0b10010001, 0b10001000},// 128
{0b10000001, 0b10101001},// 129
{0b10110001, 0b11001010},// 130
{0b10100001, 0b11101011},// 131
{0b11010001, 0b00001100},// 132
{0b11000001, 0b00101101},// 133
{0b11110001, 0b01001110},// 134
{0b11100001, 0b01101111},// 135
{0b00010000, 0b10000000},// 136
{0b00000000, 0b10100001},// 137
{0b00110000, 0b11000010},// 138
{0b00100000, 0b11100011},// 139
{0b01010000, 0b00000100},// 140
{0b01000000, 0b00100101},// 141
{0b01110000, 0b01000110},// 142
{0b01100000, 0b01100111},// 143
{0b10000011, 0b10111001},// 144
{0b10010011, 0b10011000},// 145
{0b10100011, 0b11111011},// 146
{0b10110011, 0b11011010},// 147
{0b11000011, 0b00111101},// 148
{0b11010011, 0b00011100},// 149
{0b11100011, 0b01111111},// 150
{0b11110011, 0b01011110},// 151
{0b00000010, 0b10110001},// 152
{0b00010010, 0b10010000},// 153
{0b00100010, 0b11110011},// 154
{0b00110010, 0b11010010},// 155
{0b01000010, 0b00110101},// 156
{0b01010010, 0b00010100},// 157
{0b01100010, 0b01110111},// 158
{0b01110010, 0b01010110},// 159
{0b10110101, 0b11101010},// 160
{0b10100101, 0b11001011},// 161
{0b10010101, 0b10101000},// 162
{0b10000101, 0b10001001},// 163
{0b11110101, 0b01101110},// 164
{0b11100101, 0b01001111},// 165
{0b11010101, 0b00101100},// 166
{0b11000101, 0b00001101},// 167
{0b00110100, 0b11100010},// 168
{0b00100100, 0b11000011},// 169
{0b00010100, 0b10100000},// 170
{0b00000100, 0b10000001},// 171
{0b01110100, 0b01100110},// 172
{0b01100100, 0b01000111},// 173
{0b01010100, 0b00100100},// 174
{0b01000100, 0b00000101},// 175
{0b10100111, 0b11011011},// 176
{0b10110111, 0b11111010},// 177
{0b10000111, 0b10011001},// 178
{0b10010111, 0b10111000},// 179
{0b11100111, 0b01011111},// 180
{0b11110111, 0b01111110},// 181
{0b11000111, 0b00011101},// 182
{0b11010111, 0b00111100},// 183
{0b00100110, 0b11010011},// 184
{0b00110110, 0b11110010},// 185
{0b00000110, 0b10010001},// 186
{0b00010110, 0b10110000},// 187
{0b01100110, 0b01010111},// 188
{0b01110110, 0b01110110},// 189
{0b01000110, 0b00010101},// 190
{0b01010110, 0b00110100},// 191
{0b11011001, 0b01001100},// 192
{0b11001001, 0b01101101},// 193
{0b11111001, 0b00001110},// 194
{0b11101001, 0b00101111},// 195
{0b10011001, 0b11001000},// 196
{0b10001001, 0b11101001},// 197
{0b10111001, 0b10001010},// 198
{0b10101001, 0b10101011},// 199
{0b01011000, 0b01000100},// 200
{0b01001000, 0b01100101},// 201
{0b01111000, 0b00000110},// 202
{0b01101000, 0b00100111},// 203
{0b00011000, 0b11000000},// 204
{0b00001000, 0b11100001},// 205
{0b00111000, 0b10000010},// 206
{0b00101000, 0b10100011},// 207
{0b11001011, 0b01111101},// 208
{0b11011011, 0b01011100},// 209
{0b11101011, 0b00111111},// 210
{0b11111011, 0b00011110},// 211
{0b10001011, 0b11111001},// 212
{0b10011011, 0b11011000},// 213
{0b10101011, 0b10111011},// 214
{0b10111011, 0b10011010},// 215
{0b01001010, 0b01110101},// 216
{0b01011010, 0b01010100},// 217
{0b01101010, 0b00110111},// 218
{0b01111010, 0b00010110},// 219
{0b00001010, 0b11110001},// 220
{0b00011010, 0b11010000},// 221
{0b00101010, 0b10110011},// 222
{0b00111010, 0b10010010},// 223
{0b11111101, 0b00101110},// 224
{0b11101101, 0b00001111},// 225
{0b11011101, 0b01101100},// 226
{0b11001101, 0b01001101},// 227
{0b10111101, 0b10101010},// 228
{0b10101101, 0b10001011},// 229
{0b10011101, 0b11101000},// 230
{0b10001101, 0b11001001},// 231
{0b01111100, 0b00100110},// 232
{0b01101100, 0b00000111},// 233
{0b01011100, 0b01100100},// 234
{0b01001100, 0b01000101},// 235
{0b00111100, 0b10100010},// 236
{0b00101100, 0b10000011},// 237
{0b00011100, 0b11100000},// 238
{0b00001100, 0b11000001},// 239
{0b11101111, 0b00011111},// 240
{0b11111111, 0b00111110},// 241
{0b11001111, 0b01011101},// 242
{0b11011111, 0b01111100},// 243
{0b10101111, 0b10011011},// 244
{0b10111111, 0b10111010},// 245
{0b10001111, 0b11011001},// 246
{0b10011111, 0b11111000},// 247
{0b01101110, 0b00010111},// 248
{0b01111110, 0b00110110},// 249
{0b01001110, 0b01010101},// 250
{0b01011110, 0b01110100},// 251
{0b00101110, 0b10010011},// 252
{0b00111110, 0b10110010},// 253
{0b00001110, 0b11010001},// 254
{0b00011110, 0b11110000}// 255
};
static Tcrc crc, current_polynomial, crc_mask;
static u08 current_length, current_table_bits, current_table_element_size;
static const u08 *current_table;
static void crc_add_bit(const u08 new_bit);
//#include <stdlib.h>
//#include "../../mkUART/mkuart.h"
//voidcrc_table_generator(const u08 number_of_bits)
//{
//for (Tcrc x=0; x<((Tcrc)1<<number_of_bits); x++)
//{
//crc=(Tcrc)x<<(current_length-number_of_bits+1);
//for (u08 y=0; y<number_of_bits; y++) crc_add_bit(0);
//{// Here save 'crc' for current 'x' table position
//void uart_bin (u08 x)
//{
//uart_puts_P(PSTR("0b"));
//for (u08 y=8; --y;) if (x<((Tcrc)1<<y)) uart_putc('0');
//char buf [17];
//uart_puts(ltoa(x, buf, 2));
//}
//{
//char buf [4];
//uart_putc('{');
//uart_bin(crc>>8);
//uart_puts_P(PSTR(", "));
//uart_bin(crc);
//uart_puts_P(PSTR("},\t// "));
//if (x<100)uart_putc('0');
//if (x<10)uart_putc('0');
//uart_puts(ltoa(x, buf, 10));
//uart_puts_P(PSTR("\n\r"));
//}
//}
//}
//}
voidcrc_init(const u08 length, const Tcrc polynomial, const void const *table, const u08 table_bits, const u08 table_element_size)// If length==0 then only re-init.
{
crc=(Tcrc)0;
if (length)
{
current_length=length-1;
current_polynomial=(Tcrc)polynomial;
current_table=table;
current_table_bits=table_bits;
current_table_element_size=table_element_size;
crc_mask=(Tcrc)0;
for (u08 x=0; x<=current_length; x++) crc_mask|=(Tcrc)1<<x;
}
}
static void crc_add_bit(const u08 new_bit)
{
u08 do_xor=((Tcrc)crc>>current_length)&0b1;
crc=(Tcrc)(crc<<1)|new_bit;
if (do_xor) crc^=(Tcrc)current_polynomial;
}
voidcrc_add_byte(u08 byte)
{
if (!current_table)
for (u08 x=0; x<8; x++)
{
crc_add_bit(byte>>7);
byte<<=1;
}
else
{
Tcrc get_table_element (const u08 table_index)
{
Tcrc ret=0;
for (u08 x=0; x<current_table_element_size; x++) ret=(ret<<8)|pgm_read_byte(¤t_table[table_index*current_table_element_size+x]);
return ret;
}
//{// Universal method
//u08 bits_to_do=8;
//
//while (bits_to_do>=current_table_bits)
//{
//bits_to_do-=current_table_bits;
//crc=(((Tcrc)crc<<current_table_bits)|(byte>>(8-current_table_bits)))^get_table_element((crc>>(current_length+1-current_table_bits))&((1<<current_table_bits)-1));
//byte<<=current_table_bits;
//}
//if (bits_to_do) crc=(((Tcrc)crc<<bits_to_do)|(byte>>(8-bits_to_do)))^get_table_element((crc>>(current_length+1-bits_to_do))&((1<<bits_to_do)-1));
//}
{// 8bit method
crc=(((Tcrc)crc<<8)|byte)^get_table_element(crc>>8);
}
//{// 4bit method
//for (u08 x=0; x<2; x++)
//{
//crc=(((Tcrc)crc<<4)|(byte>>4))^get_table_element((Tcrc)crc>>12);
//byte<<=4;
//}
//}
}
}
Tcrccrc_read(void)
{
u08 bits_to_do=current_length+1;
while (bits_to_do>=8)
{
bits_to_do-=8;
crc_add_byte(0);
}
while (bits_to_do--) crc_add_bit(0);
return (Tcrc)crc&crc_mask;
}[/syntax]
Tablica wartości dla CRC16 do wykorzystania przy kartach SD w bonusie
No i kilka fotek z pogaduszek z kartą
F_CPU=8MHz
SPI=F_CPU/2 (czyli do oporu
)Dla transmisji bajtu T1-T2 to czas transmisji SPI, width to czas obliczeń (w większości).
Dla transmisji bloku T1-T2 to czas faktycznego przesyłania bloku, a width zawiera do tego "prolog" i "epilog" transmisji.
Bit-po-bicie
Optymalizacja 4bitowa
Optymalizacja 8bitowa
W kodach jest jeszcze metoda uniwersalna, ale jak to metody uniwersalne mają w zwyczaju, jej szybkość jest taka, że żal pokazywać (dla 8 bitów optymalizacji ~połowa czasu bit-po-bicie)...
Na zakończenie chciałbym podziękować Fredkowi za analizator stanów, bez niego nic nie byłoby takie proste
Statystyki: Napisane przez barney — 16 wrz 2013, o 22:14
]]>