Быстрое вычисление 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]

Накладные расходы невелики и не зависят от расположения таблицы.

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

Код

ldi    ZH, high(table * 2)
mov    ZL, offset
lpm
...

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

Код

ldi    ZH, high(table * 2)
ldi    ZL, low(table * 2)
add    ZL, offset
lpm
...

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

Код

ldi    ZH, high(table * 2)
ldi    ZL, low(table * 2)
add    ZL, offset
brcc   PC+0x02
inc    ZH
lpm
...

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

А насчет стека могу сказать, что в PIC16 его необходимо расходовать очень экономно...

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

[_Bill]

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

Код

ldi    ZH, high(table * 2)
mov    ZL, offset
lpm
...

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

Код

ldi    ZH, high(table * 2)
ldi    ZL, low(table * 2)
add    ZL, offset
lpm
...

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

Код

ldi    ZH, high(table * 2)
ldi    ZL, low(table * 2)
add    ZL, offset
brcc   PC+0x02
inc    ZH
lpm
...

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


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

Если расчитывать на определенное размещение таблицы в памяти, тогда согласен. Но в случае использования линкера, расположение таблицы обычно заранее неизвестно, и расчитывать на это не стоит. Поэтому нужно использовать наиболее общий случай, только я бы сделал код для этого чуточку проще:

Код

     mov  ZL,  offset          ; offset, offset+1 - регистры для смещения (индекса)
     mov  ZH, offset+1             ;
     sbi  ZL, -low(table*2)    ; Вычислить точку входа в таблицу.
     sbci ZH, -high(table*2)       ;
     lpm  R16                  ; Выбрать байт

Необходимо только 4 такта накладных расходов. Но доступ по индексу требует больше накладных расходов и, соответственно времени. Поэтому при последовательном доступе к элементам таблицы лучше воспользоваться методом доступа по указателю, чего в PIC16 вообще нет:

Код

     ldi  ZH, high(table*2)    ; Установить указатель таблицы
     ldi  ZL. low(table*2)           ;
............
     lpm  R16, Z+              ; Выбрать очередной элемент таблицы