=GM=, по моему небольшая ошибка есть кроме той на которую указал Oldring. В каждом sbrc , кроме того, который проверяет нулевой бит, вам надо поменять номер бита в возрастаюшем порядке, по которому вы проверяете установлен ли бит или нет.

удачи.

А если присмотреться повнимательнее, обнаруживается, что выставленный на суд общественности код в принципе нерабочий

Вот вариант с полубайтовыми таблицами для AVR:


и PIC16:


В порядке разжигания религиозной розни замечу, что код для PIC'a получается гораздо эстетичнее за счет более красивой реализации работы с таблицами.

Ну не в принципе - но не рабочий. Студенту явно нужно начинать учиться отлаживать свой код на симуляторе



В порядке защиты AVR замечу, что для него можно написать красивше и только с одной таблицей. Умножение на x^8 по модулю порождающего полинома кода должно выглядеть как дважды повторенный участок кода, реализующий модульное умножение на x^4:



Кому нравится, может использовать lpm, вместо ld. Данный код приведен для LSB-first варианта алгоритма, как и первоначальный сишный код. Преобразовать его в MSB-first просто, переместив swap в начало последовательности инструкций.

Таблицу вычислять не буду.

P.S. Правда, при использовании двух 16-байтных таблиц, хранящихся в RAM, можно сэкономить еще три такта на обрабатываемый байт.

Да, спасибо за замеченные опечатки и ошибки (копи-паст, понимаете ли(:-(). Вот исправленный вариант.

Oldring, здесь на 7*8=56 бит расходуется 69 машинных циклов или вгрубе по 69/56=1.23 МЦ на бит.

Сообщение отредактировал =GM= - Sep 3 2006, 20:35

без учета ret - да. Только это - не CRC Вот теперь я понял, что имел в виду aaarrr когда писал про неработоспособность кода в принципе. Цикл по байтам в самом начале я и не заметил за остальными ошибками

Добавлю. Кодовое расстояние получившегося кода равно 2. Вероятность необнаружения этим кодом случайных ошибок практически не отличается от вычисления контрольного байта как простого исключающего или всех семи байт передаваемого блока. Так ради чего было так мучаться?

Это точно не CRC.

ИМХО, проблемма в том что у Вас не обнуляеться временное
значение CRC при переходе к следующему байту.


Вот так:


Получаем 177 тактов (не учитывая ret)
НО, используем 8 лишних регистров

Для тех кто интересуется добавлю, что рассматриваемый CRC-8 для блоков до 127 бит имеет кодовое расстояние 4. Длина 127 бит ограничивает длину блока данных, для которой код эффективен, 14 байтами. Если же длина блока данных ограничена 7 байтами, как в данном случае, то можно применить CRC-7 с кодовым расстоянием также равным 4. При этом освободившийся бит проверочного байта можно использовать произвольным образом - но помня что он не контролируется кодом. CRC-7 также имеет в два раза большую вероятность необнаружения сильного искажения блока - 1/128 против 1/256 для CRC-8. Это может быть существенно, например, если высока вероятность потери винхронизации в середине блока. C другой стороны, как показывает практика, при заметной вероятности сильного искажения вероятность 1/256 все равно слишком высока и нужно закладывать существенно большее количество проверочных бит. При этом оба кода, являясь кодами Хэмминга, дополненными проверкой на четность, позволяют детектировать все тройные ошибки, либо детектировать все двойные ошибки и легко исправлять все одиночные ошибки.

Вот мой код расчета CRC16,
не скажу, что я придумал такой алгоритм, т.к. видел аналог для другого полинома, но это и не таблица и не цикл

; По модулю 0x11021
; IN R18 - DATA
; IN, OUT R4, R5 - аккумулятор
CRC16Update:
push R18
push R19
eor R4, R18
ldi R18, 0x00
mov R19, R4
andi R19, 0xF0
eor R18, R19
swap R19
eor R4, R19
add R19, R19
eor R5, R19
mov R19, R4
andi R19, 0x0F
eor R18, R19
swap R19
eor R5, R19
add R19, R19
brcc CRC16Skip
clr R4
inc R4
eor R5, R4
CRC16Skip:
eor R18, R19
mov R4, R5
mov R5, R18
pop R19
pop R18
ret

Сообщение отредактировал ivstech - Sep 4 2006, 05:28

Без всякого разжигания религиозной розни хочу заметить, что обращение к таблицам выполняется посредством инструкций call - retlw, в результате чего время выполнения функции существенно увеличивается. Другой неприятностью является необходимость использования стека, размер которого в PIC16 очень небольшой.

Сообщение отредактировал _Bill - Sep 4 2006, 07:42

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


Очень небольшой, но вполне достаточный для построения любой разумной программы.

Накладные расходы невелики и не зависят от расположения таблицы. В AVR отсутствует понятие страницы памяти. Но я говорю, в первую очередь, об увеличении скорости вычислений. А насчет стека могу сказать, что в PIC16 его необходимо расходовать очень экономно. Особенно при использовании прерываний. Поэтому при программировании на PIC16 я старался использовать подпрограммы лишь там, где это действительно было необходимо, например, при доступе к таблицам. В других случаях там, где можно было бы использовать подпрограммы, мне приходилось вставлять фрагменты одного и того же кода. Это неизбежно приводило к разрастанию программного кода. И тогда появлялись другие проблемы, связанные с ипользованием нескольких страниц программной памяти. Ну, да Вам эти проблемы известны не хуже меня.

Ах да, точно. Спасибо. Про такие варианты я уже забыл.

Легко найти, что для рассматриваемого полинома вычисление модульного умножения на x^8 можно выполнить за 15 тактов. Если же использовать код с взаимным полиномом (0x119), то то вообще за 12. Это конечно не 9 тактов - но и вообще без таблиц. Если я нигде не ошибся, вот так:



С накладными расходами на прокрутку цикла получаем 18 тактов на байт данных.
Напоминаю, что это LSB-first код.

Как это не зависят?
Одно дело, когда таблица выровнена по границе 256 байт, и не пересекает следующую:

другое, когда таблица не выровнена по границе 256 байт:

и совсем другое, когда не выровнена по границе 256 байт, и пересекает следующую:


Разница по скорости почти в 2 раза: 5 и 8 тактов.


"Расход" стека случается только при использовании вложенных подпрограмм. Как правило, программы уровня PIC16 позволяют обойтись минимальным количеством вложений.

Зависит, но это не имеет большого значения. У иаровского ассемблера есть директива размещения сегмента с произвольным выравниванием, равным степени двойки. Например, 256.

Большого не имеет. Мне просто показалось, что в этом топике готовы удавиться за такт, вот и стараюсь