Obliczanie 8-bitowego CRC za pomocą preprocesora C?

Question

Piszę kod dla małego 8-bitowego mikrokontrolera z tylko kilkoma bajtami pamięci RAM. Ma proste zadanie, które ma przesłać 7 16-bitowych słów, a następnie CRC tych słów. Wartości słów są wybierane podczas kompilacji. CRC w szczególności jest "resztą podziału słowa 0 na słowo 6 jako niepodpisaną liczbę podzieloną przez wielomian x^8 + x² + x + 1 (wartość początkowa 0xFF)."

Czy jest możliwe obliczenie CRC tych bajtów w czasie kompilacji przy użyciu preprocesora C?

#define CALC_CRC(a,b,c,d,e,f,g) /* what goes here? */ 

#define W0 0x6301 
#define W1 0x12AF 
#define W2 0x7753 
#define W3 0x0007 
#define W4 0x0007 
#define W5 0x5621 
#define W6 0x5422 
#define CRC CALC_CRC(W0, W1, W2, W3, W4, W5, W6) 

Answer 1

Algorytm najprostszym suma jest tak zwanego rozciągania wzdłużnego kontroli parzystości, który rozkłada się dane do „słowa” o stałej liczby n bitów, a następnie oblicza jedyną lub wszystkich tych słów. Wynik jest dołączany do wiadomości jako dodatkowe słowo.

Aby sprawdzić integralność wiadomości, odbiorca oblicza wyłączne lub wszystkie jego słowa, w tym sumę kontrolną; jeśli wynikiem nie jest słowo zawierające n zer, odbiornik wie, że wystąpił błąd transmisji.

(sos: wiki)

W przykładzie:

#define CALC_CRC(a,b,c,d,e,f) ((a)^(b)^(c)^(d)^(e)^(f)) 

Answer 2

Uwaga: nie jest to bezpośrednia odpowiedź, a raczej seria pytań i sugestii, które są zbyt długie dla komentarza.

Pierwsze pytanie: czy kontrolujesz oba końce protokołu, np. czy możesz wybrać algorytm sumy kontrolnej za pomocą siebie lub współpracownika kontrolującego kod na drugim końcu?

Jeśli TAK na pytanie nr 1:

Trzeba ocenić, dlaczego trzeba sumy kontrolnej, co suma kontrolna jest właściwe, a konsekwencje otrzymania uszkodzonej wiadomości z poprawną sumą kontrolną (które czynniki pod zarówno co jest powodem dlaczego.

Jaki jest twój nośnik transmisji, protokół, przepływność, itp? Czy spodziewasz się/obserwujesz błędy bitowe? Na przykład, z SPI lub I2C z jednego układu do drugiego na tej samej płytce, jeśli masz błędy bitowe, prawdopodobnie jest to błąd inżyniera HW lub musisz zwolnić częstotliwość taktowania, lub oba. Suma kontrolna nie zaszkodzi, ale nie powinna być konieczna. Z drugiej strony, z sygnałem podczerwieni w hałaśliwym otoczeniu, a będziesz miał znacznie większe prawdopodobieństwo błędu.

Konsekwencje złej wiadomości to zawsze najważniejsze pytanie. Więc jeśli piszesz kontroler do cyfrowego termometru pokojowego i wysyłasz wiadomość, aby zaktualizować ekran 10x na sekundę, jedna zła wartość, kiedykolwiek 1000 wiadomości ma bardzo małą, a nawet prawdziwą szkodę. Brak sumy kontrolnej lub słabej sumy kontrolnej.

Jeśli te 6 bajtów wystrzeliwuje pocisk, ustawia położenie zrobotyzowanego skalpela lub powoduje transfer pieniędzy, lepiej mieć pewność, że masz odpowiednią sumę kontrolną, a może nawet zajrzeć do kryptograficznego skrótu (który może wymagać więcej pamięci RAM niż masz).

Dla produktów pośrednich, z zauważalną szkodą dla wydajności/zadowolenia z produktu, ale bez prawdziwej szkody, jest to jego wezwanie.Na przykład telewizor, który od czasu do czasu zmienia głośność zamiast kanału, może zdenerwować wszystkich klientów - bardziej niż porzucenie polecenia, jeśli dobry CRC wykryje błąd, ale jeśli jesteś w branży taniego/podróbki telewizorów, które mogą być w porządku, jeśli szybciej wprowadzą produkt na rynek.

Jaką sumę kontrolną potrzebujesz?

Jeśli jeden lub oba końce mają obsługę HW dla sumy kontrolnej wbudowanej w urządzenie peryferyjne (dość powszechne w SPI na przykład), może to być mądry wybór. Wtedy obliczenie staje się mniej lub bardziej swobodne.

LRC, jak sugeruje odpowiedź vulkanina, jest najprostszym algorytmem.

Wikipedia ma jakiś przyzwoity informacji o tym, jak/dlaczego wybierać wielomian jeśli naprawdę potrzebujemy CRC: http://en.wikipedia.org/wiki/Cyclic_redundancy_check

Jeżeli NIE na pytanie nr 1:

Co algorytm CRC/wielomian robi inny koniec wymaga? To jest to, z czym utknąłeś, ale mówienie nam może dać ci lepszą/bardziej kompletną odpowiedź.

Myśli o realizacji:

Większość algorytmów są dość lekkie pod względem RAM/rejestrów, wymagając jedynie kilka dodatkowych bajtów. Ogólnie rzecz biorąc, funkcja spowoduje lepszy, czystszy, bardziej czytelny kod przyjazny dla debuggera.

Powinieneś pomyśleć o rozwiązaniu makro jako sztuczce optymalizacyjnej i, podobnie jak wszystkie triki optymalizacyjne, przeskakiwanie do nich na wczesnym etapie może być stratą czasu rozwoju i przyczyną więcej problemów niż jest to warte.

Korzystanie makro też ma jakieś dziwne konsekwencje nie mogą jeszcze wziąć pod uwagę:
jesteś świadomy, że preprocesor może tylko wykonać obliczenia, jeśli wszystkie bajty w wiadomości są stałe w czasie kompilacji, prawda? Jeśli masz tam zmienną, kompilator musi wygenerować kod. Bez funkcji kod ten będzie wstawiany za każdym razem, gdy zostanie użyty (tak, może to oznaczać dużo użycia pamięci ROM). Jeśli wszystkie bajty są zmienne, ten kod może być gorszy niż napisanie funkcji w C. Lub z dobrym kompilatorem, może być lepiej. Trudno powiedzieć na pewno. Z drugiej strony, jeśli inna liczba bajtów jest zmienna, w zależności od wysyłanej wiadomości, możesz skończyć z kilkoma wersjami kodu, z których każdy jest zoptymalizowany pod kątem konkretnego zastosowania.

Answer 3

Możliwe jest zaprojektowanie makra, które wykona obliczenie CRC w czasie kompilacji. Coś takiego, jak

 
// Choosing names to be short and hopefully unique. 
#define cZX((n),b,v) (((n) & (1 << b)) ? v : 0) 
#define cZY((n),b, w,x,y,z) (cZX((n),b,w)^CzX((n),b+1,x)^CzX((n),b+2,y)^cZX((n),b+3,z)) 
#define CRC(n) (cZY((n),0,cZ0,cZ1,cZ2,cZ3)^cZY((n),4,cZ4,cZ5,cZ6,cZ7)) 

powinno prawdopodobnie działać, i będzie bardzo wydajne, jeśli (n) może być ocenione jako stała czasu kompilacji; po prostu oceni się jako stałą. Z drugiej strony, jeśli wyrażenie to jest wyrażeniem, to będzie ono osiemkrotnie uzyskiwane ponownie. Nawet jeśli n jest zmienną prostą, wynikowy kod będzie prawdopodobnie znacznie większy niż najszybszy sposób jego zapisu bez tabeli i może być wolniejszy niż najbardziej kompaktowy sposób jego zapisu.

Przy okazji, jedno, co naprawdę chciałbym zobaczyć w standardzie C i C++, byłby sposób określania przeciążeń, które byłyby stosowane dla funkcji zadeklarowanych w linii tylko wtedy, gdy poszczególne parametry mogłyby być ocenione jako stałe kompilacyjne.Semantyka byłaby taka, że ​​nie byłoby żadnej "gwarancji", że takie przeciążenie byłoby używane w każdym przypadku, w którym kompilator mógłby być w stanie określić wartość, ale byłaby gwarancja, że ​​(1) żadne takie przeciążenie nie zostanie użyte w każdym przypadku, gdy parametr "czas kompilacji" musiałby być oceniany w czasie wykonywania, oraz (2) dowolny parametr, który jest uważany za stały w jednym takim przeciążeniu, będzie uważany za stałą w jakichkolwiek wywołanych z niego funkcjach. Istnieje wiele przypadków, w których funkcja mogłaby zostać zapisana w celu oceny stałej kompilacji, gdyby jej parametr był stały, ale gdzie ocena czasu pracy byłaby absolutnie okropna. Np

 
#define bit_reverse_byte(n) ((((n) & 128)>>7)|(((n) & 64)>>5)|(((n) & 32)>>3)|(((n) & 16)>>1)| 
    (((n) & 8)<<1)|(((n) & 4)<<3)|(((n) & 2)<<5)|(((n) & 1)<<7)) 
#define bit_reverse_word(n) (bit_reverse_byte((n) >> 8) | (bit_reverse_byte(n) << 8)) 

prosty trójwymiarowa non-pętli funkcji bitów odwróconych jednobajtowych w C na PIC będzie około 17-19 instrukcje pojedynczym cyklu; słowo bit-reverse będzie wynosić 34, lub około 10 plus funkcja powrotu do bajtu (która byłaby wykonywana dwukrotnie). Optymalny kod montażowy to około 15 instrukcji jednokrokowych dla odwrotnego bajtu lub 17 dla słowa-odwrotnego. Obliczanie bit_reverse_byte(b) dla pewnej zmiennej bajtowej b wymagałoby wykonania wielu dziesiątek instrukcji w sumie na wiele dziesiątek cykli. W tym przypadku prawdopodobnie wykonano by setki instrukcji wykonujących setki lub tysiące cykli. Byłoby naprawdę fajnie, gdyby można było oznaczyć funkcję, która ma być rozwinięta inline, używając czegoś podobnego do powyższego sformułowania w scenariuszu, w którym rozszerzyłaby się ona do czterech instrukcji (zasadniczo po prostu załadowanie wyniku), ale użyła wywołania funkcji w scenariuszach, gdzie inline ekspansja byłaby ohydna.