Вычисление 8-битного CRC с препроцессором C?

Question

Я пишу код для крошечного 8-битного микроконтроллера с несколькими байтами оперативной памяти. У него простая задача - передать 7 16-битных слов, а затем CRC этих слов. Значения слов выбираются во время компиляции. КПР конкретно является «остатком от деления от 0 до 6 как число без знака, деленное на многочлен x ^ 8 + x² + x + 1 (начальное значение 0xFF). "

Можно ли рассчитать CRC этих байтов во время компиляции, используя препроцессор 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

Можно разработать макрос, который будет выполнять вычисление CRC во время компиляции.Что-то вроде

 // 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))

, вероятно, должно работать и будет очень эффективно, если (n) может быть оценено как константа времени компиляции;он просто оценит саму константу.С другой стороны, если n является выражением, это выражение будет пересчитано восемь раз.Даже если n простая переменная, результирующий код, вероятно, будет значительно больше, чем самый быстрый способ записи без таблиц, и может быть медленнее, чем самый компактный способ его записи.

Кстати, одна вещь, которую я действительно хотел бы видеть в стандарте C и C ++, это средство определения перегрузок, которые будут использоваться для функций, объявленных как inline, только если конкретные параметры могут быть оценены как константы времени компиляции.Семантика будет такой, что не будет «гарантии», что любая такая перегрузка будет использоваться в каждом случае, когда компилятор сможет определить значение, но будет гарантия, что (1) такая перегрузка не будет использоватьсяв любом случае, когда параметр «compile-time-const» должен оцениваться во время выполнения, и (2) любой параметр, который считается константой в одной такой перегрузке, будет считаться константой в любых вызываемых из него функциях.Есть много случаев, когда функция может быть написана для вычисления константы времени компиляции, если ее параметр постоянен, но когда оценка во время выполнения будет абсолютно ужасной.Например:

#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))

Простой рендеринг нецикличной однобайтовой функции обратного бита в C на PIC будет примерно 17-19 однократных инструкций;обратный бит слова будет 34 или около 10 плюс функция обратного байта (которая будет выполняться дважды).Оптимальный ассемблерный код должен составлять около 15 однократных инструкций для реверсирования байтов или 17 для реверсирования слов.Вычисление bit_reverse_byte(b) для некоторой байтовой переменной b заняло бы много десятков инструкций, что составляет множество десятков циклов.Вычисление bit_reverse_word( w ) for some 16-bit word w`, вероятно, потребовало бы сотен инструкций, выполняемых сотнями или тысячами циклов.Было бы очень хорошо, если бы можно было пометить функцию, которая должна быть развернута в строке, используя что-то похожее на приведенную выше формулировку в сценарии, где она будет расширена до четырех инструкций (в основном, просто загружая результат), но использовать вызов функции в сценариях, где встроенарасширение было бы отвратительным.

Answer 2

Самым простым алгоритмом контрольной суммы является так называемая продольная проверка на четность, которая разбивает данные на «слова» с фиксированным числом n битов, а затем вычисляет исключение или все эти слова. Результат добавляется к сообщению как дополнительное слово.

Для проверки целостности сообщения получатель вычисляет исключение или все его слова, включая контрольную сумму; если результат не является словом с n нулями, получатель знает, что произошла ошибка передачи.

(souce: wiki)

В вашем примере:

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

Answer 3

Отказ от ответственности: это на самом деле не прямой ответ, а скорее серия вопросов и предложений, которые слишком длинны для комментария.

Первый вопрос: У вас есть контроль над обоими сторонамипротокол, например, можете ли вы выбрать алгоритм контрольной суммы с помощью вас или коллеги, управляющего кодом на другом конце?

Если ДА, ответьте на вопрос № 1:

Вам необходимо оценить, зачем вам нужна контрольная сумма, какая контрольная сумма подходит, и последствия получения искаженного сообщения с действительной контрольной суммой (которая учитывает как то, что и почему).

Какая у вас среда передачи, протокол, битрейт и т. Д.?Вы ожидаете / наблюдаете ошибки в битах?Так, например, с SPI или I2C от одного чипа к другому на одной плате, если у вас есть битовые ошибки, это, вероятно, ошибка инженеров HW, или вам нужно снизить тактовую частоту, или и то, и другое.Контрольная сумма не может повредить, но на самом деле не должна быть необходимой.С другой стороны, при наличии инфракрасного сигнала в шумной обстановке вероятность ошибки значительно выше.

Последствия плохого сообщения - всегда самый важный вопрос здесь.Таким образом, если вы пишете контроллер для цифрового комнатного термометра и отправляете сообщение для обновления дисплея 10 раз в секунду, одно плохое значение на 1000 сообщений будет очень мало, если вообще будет реальным вредом.Никакой контрольной суммы или слабой контрольной суммы не должно быть хорошо.

Если эти 6 байтов запускают ракету, устанавливают положение скальпеля-робота или вызывают перевод денег, вам лучше быть чертовски уверенным, что вы имеете правильную контрольную сумму, и, возможно, даже захотите заглянуть в криптографический хеш(для этого может потребоваться больше оперативной памяти, чем у вас).

Для промежуточных вещей, с заметным ущербом для производительности / удовлетворенности продуктом, но без реального вреда, это ваш вызов.Например, телевизор, который иногда изменяет громкость, а не канал, может раздражать клиентов до чертиков - больше, чем просто сбросить команду, если хороший CRC обнаружит ошибку, но если вы собираетесь делать дешево /Подберите телевизоры, которые могут быть в порядке, если он выводит продукт на рынок быстрее.

Так какая контрольная сумма вам нужна?

Если на одном или обоих концах есть поддержка HW для контрольной суммы, встроенной в периферийное устройство(довольно часто встречается в SPI, например), это может быть мудрым выбором.Тогда он становится более или менее свободным для вычисления.

LRC, как следует из ответа Вулканино, является самым простым алгоритмом.

В Википедии есть некоторая приличная информация о том, как / почему выбрать полином, есливам действительно нужен CRC: http://en.wikipedia.org/wiki/Cyclic_redundancy_check

Если НЕТ на вопрос № 1:

Какой алгоритм / полином CRC требуется другому концу?Это то, с чем вы застряли, но, сообщив нам, вы получите лучший / более полный ответ.

Мысли о реализации:

Большинство алгоритмов довольно легкие- вес с точки зрения ОЗУ / регистров, требующий только пару дополнительных байтов.В общем, функция приведет к получению лучшего, более чистого, более читабельного и дружественного к отладчику кода.

Вы должны думать о макро-решении как о приеме оптимизации, и, как и обо всех приемах оптимизации, переходите к ним на ранних этапах.быть пустой тратой времени на разработку и причиной большего количества проблем, чем стоит.

Использование макроса также имеет некоторые странные последствия, которые вы, возможно, еще не рассмотрели:
Вы знаете, что препроцессор может выполнять вычисления, только если все байты в сообщении фиксированы во время компиляции, верно?Если у вас есть переменная, компилятор должен сгенерировать код.Без функции этот код будет вставляться при каждом использовании (да, это может означать много использования ПЗУ).Если все байты являются переменными, этот код может быть хуже, чем просто написание функции на C. Или с хорошим компилятором, это может быть лучше.Трудно сказать наверняка.С другой стороны, если различное количество байтов является переменным в зависимости от отправляемого сообщения, вы можете получить несколько версий кода, каждая из которых оптимизирована для этого конкретного использования.