Быстрое вычисление CRC-8, Потенциальные возможности не табличных методов Опции

[=GM=]

Недавно поднимался вопрос об оптимизации сишного кода, в частности был представлен такой код (немного отрихтовал для приличия)

Приятный алгоритм, возьму на вооружение. IAR - 515 циклов.

Код

U8 crc8_3(U8 *buff, U8 num)
{
U8 i, crc=0;
do
{
  crc^=*buff++;
   i=8;
   do
   {  
     if(crc&0x01)
     {
       crc>>=1;
       crc^=0x8C;
     }
     else crc>>=1;
   }
  } while(--i);  
} while(--num);
return crc;
}

Для семи байтов ИАР-код выполняется за 525 циклов, т.е. вгрубе 75 циклов на байт.
У меня весь ASM-код (не табличный) для 7 байт выполняется за 80 циклов. Может я чего не понимаю, или полиномы неправильные?

[aaarrr]

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

удачи.

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

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

Код

    Указатель на начало буфера - Y,
    длина - e.
    Результат возвращается в c

crc8:
    ldi    ZH, high(crc8_tba * 2)
    ldi    c, 0x00
crc8_0:
    ld     a, Y+
    eor    a, c
    mov    ZL, a
    swap   ZL
    andi   ZL, 0x0f
    lpm
    mov    c, r0
    mov    ZL, a
    andi   ZL, 0x0f
    ori    ZL, 0x10
    lpm
    eor    c, r0
    dec    e
    brne   crc8_0
    ret


    .org    0xf00

crc8_tba:
    .db    0x00, 0x9d
    .db    0x23, 0xbe
    .db    0x46, 0xdb
    .db    0x65, 0xf8
    .db    0x8c, 0x11
    .db    0xaf, 0x32
    .db    0xca, 0x57
    .db    0xe9, 0x74

crc8_tbb:
    .db    0x00, 0x5e
    .db    0xbc, 0xe2
    .db    0x61, 0x3f
    .db    0xdd, 0x83
    .db    0xc2, 0x9c
    .db    0x7e, 0x20
    .db    0xa3, 0xfd
    .db    0x1f, 0x41

и PIC16:

Код

    FSR - Адрес
    tmp0 - количество данных

crc8
    movlw   high(crc_tba)
    movwf   PCLATH
    clrf    tmp1
crc8_0
    movf    tmp1, w
    xorwf   INDF, w
    movwf   tmp2
    andlw   0fh
    call    crc_tbb
    movwf   tmp1
    swapf   tmp2, w
    andlw   0fh
    call    crc_tba
    xorwf   tmp1, f
    incf    FSR, f
    decfsz  tmp0, f
    goto    crc8_0
    return

crc_tba
    addwf    PCL, f
    dt    00h, 9dh, 23h, 0beh, 46h, 0dbh, 65h, 0f8h
    dt    8ch, 11h, 0afh, 32h, 0cah, 57h, 0e9h, 74h

crc_tbb
    addwf    PCL, f
    dt    00h, 5eh, 0bch, 0e2h, 61h, 3fh, 0ddh, 83h
    dt    0c2h, 9ch, 7eh, 20h, 0a3h, 0fdh, 1fh, 41h

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

[Oldring]

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

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

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

Код

    Указатель на начало буфера - Y,
    длина - e.
    Результат возвращается в c

crc8:
    ldi    ZH, high(crc8_tba * 2)
    ldi    c, 0x00
crc8_0:
    ld     a, Y+
    eor    a, c
    mov    ZL, a
    swap   ZL
    andi   ZL, 0x0f
    lpm
    mov    c, r0
    mov    ZL, a
    andi   ZL, 0x0f
    ori    ZL, 0x10
    lpm
    eor    c, r0
    dec    e
    brne   crc8_0
    ret


    .org    0xf00

crc8_tba:
    .db    0x00, 0x9d
    .db    0x23, 0xbe
    .db    0x46, 0xdb
    .db    0x65, 0xf8
    .db    0x8c, 0x11
    .db    0xaf, 0x32
    .db    0xca, 0x57
    .db    0xe9, 0x74

crc8_tbb:
    .db    0x00, 0x5e
    .db    0xbc, 0xe2
    .db    0x61, 0x3f
    .db    0xdd, 0x83
    .db    0xc2, 0x9c
    .db    0x7e, 0x20
    .db    0xa3, 0xfd
    .db    0x1f, 0x41

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

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

Код

    mov    ZL, c
    andi    ZL, 0x0f
    ld    r0, Z
    eor    c, r0
    swap    c

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

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

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