Быстрое вычисление 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 циклов. Может я чего не понимаю, или полиномы неправильные?

[IgorKossak]

=GM=, почитайте внимательно о методах оптимизации у IAR, проникнитесь их изощрённостью и больше не удивляйтесь. Примите как есть и пользуйтесь на здоровье

[pitt]

Код для onewire от Texas Instruments avr-gcc. Перенос на любой другой компилятор не должн быть проблемой.

Код

#include <avr/pgmspace.h>
typedef unsigned char byte;

byte crc_tab [256] PROGMEM = {
    0,  94, 188, 226,  97,  63, 221, 131, 194, 156, 126,  32, 163, 253,  31,  65,
  157, 195,  33, 127, 252, 162,  64,  30,  95,   1, 227, 189,  62,  96, 130, 220,
   35, 125, 159, 193,  66,  28, 254, 160, 225, 191,  93,   3, 128, 222,  60,  98,
  190, 224,   2,  92, 223, 129,  99,  61, 124,  34, 192, 158,  29,  67, 161, 255,
   70,  24, 250, 164,  39, 121, 155, 197, 132, 218,  56, 102, 229, 187,  89,   7,
  219, 133, 103,  57, 186, 228,   6,  88,  25,  71, 165, 251, 120,  38, 196, 154,
  101,  59, 217, 135,   4,  90, 184, 230, 167, 249,  27,  69, 198, 152, 122,  36,
  248, 166,  68,  26, 153, 199,  37, 123,  58, 100, 134, 216,  91,   5, 231, 185,
  140, 210,  48, 110, 237, 179,  81,  15,  78,  16, 242, 172,  47, 113, 147, 205,
   17,  79, 173, 243, 112,  46, 204, 146, 211, 141, 111,  49, 178, 236,  14,  80,
  175, 241,  19,  77, 206, 144, 114,  44, 109,  51, 209, 143,  12,  82, 176, 238,
   50, 108, 142, 208,  83,  13, 239, 177, 240, 174,  76,  18, 145, 207,  45, 115,
  202, 148, 118,  40, 171, 245,  23,  73,   8,  86, 180, 234, 105,  55, 213, 139,
   87,   9, 235, 181,  54, 104, 138, 212, 149, 203,  41, 119, 244, 170,  72,  22,
  233, 183,  85,  11, 136, 214,  52, 106,  43, 117, 151, 201,  74,  20, 246, 168,
  116,  42, 200, 150,  21,  75, 169, 247, 182, 232,  10,  84, 215, 137, 107,  53
};

// One-wire device routines - single slave, external power

byte crc8 ( byte *ptr, byte cnt ) { // pointer to & length of the string
  byte crc;

  for ( crc = 0; cnt--; ) crc = pgm_read_byte ( &crc_tab[crc ^ *ptr++]);
  return crc;
}

Сообщение отредактировал pitt - Sep 1 2006, 13:00

[=GM=]

=GM=, почитайте внимательно о методах оптимизации у IAR, проникнитесь их изощрённостью и больше не удивляйтесь. Примите как есть и пользуйтесь на здоровье

Да какая ж там изощренность, если на ОДИН байт тратится 75 циклов, а у моего собственного кода - 11 циклов на тот же самый ОДИН байт!

Как тут не удивляться! Попробую переложить собственный асм-код на си и опубликовать.

[aaarrr]

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

Похоже, что что-то у Вас не так - одних сдвигов получается на 56 тактов...

[singlskv]

=GM=, почитайте внимательно о методах оптимизации у IAR, проникнитесь их изощрённостью и больше не удивляйтесь. Примите как есть и пользуйтесь на здоровье

Да какая ж там изощренность, если на ОДИН байт тратится 75 циклов, а у моего собственного кода - 11 циклов на тот же самый ОДИН байт!

Как тут не удивляться! Попробую переложить собственный асм-код на си и опубликовать.

Так опубликуйте на ASM, здесь его многие знают.

[=GM=]

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

Похоже, что что-то у Вас не так - одних сдвигов получается на 56 тактов...

Хорошо, давайте начнем с расчета ЦКС8. Вот такой код для расчета ЦКС8 одного байта, только на ассемблере, у меня занимает 16/32 цикла для двух вариантов.

Код

uchar crc8 (uchar crc, uchar byte)
{
  byte^=crc;
  crc=0;
  if(byte&0x01) crc =0x5E;
  if(byte&0x02) crc^=0xBC;
  if(byte&0x04) crc^=0x61;
  if(byte&0x08) crc^=0xC2;
  if(byte&0x10) crc^=0x9D;
  if(byte&0x20) crc^=0x23;
  if(byte&0x40) crc^=0x46;
  if(byte&0x80) crc^=0x8C;
  return crc;
}

Проверьте, правильно считает(:-)?
Ещё было бы любопытно, если бы кто-нибудь представил ассемблерный листинг для ИАР-компилера. У меня он есть, но не установлен, заглушка куда-то делась(:-). Интересно, насколько ИАР оптимизирует код.

[singlskv]

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

Похоже, что что-то у Вас не так - одних сдвигов получается на 56 тактов...

Хорошо, давайте начнем с расчета ЦКС8. Вот такой код для расчета ЦКС8 одного байта, только на ассемблере, у меня занимает 16/32 цикла для двух вариантов.

Код

uchar crc8 (uchar crc, uchar byte)
{
  byte^=crc;
  crc=0;
  if(byte&0x01) crc =0x5E;
  if(byte&0x02) crc^=0xBC;
  if(byte&0x04) crc^=0x61;
  if(byte&0x08) crc^=0xC2;
  if(byte&0x10) crc^=0x9D;
  if(byte&0x20) crc^=0x23;
  if(byte&0x40) crc^=0x46;
  if(byte&0x80) crc^=0x8C;
  return crc;
}

Проверьте, правильно считает(:-)?
Ещё было бы любопытно, если бы кто-нибудь представил ассемблерный листинг для ИАР-компилера. У меня он есть, но не установлен, заглушка куда-то делась(:-). Интересно, насколько ИАР оптимизирует код.

Перечитайте еще раз ту ветку, такой вариант там был

Это ПолуТабличный способ.

[=GM=]

Перечитайте еще раз ту ветку, такой вариант там был
Это ПолуТабличный способ.

Прошу пардону, не заметил. Хоть и не претендую на первооткрывателя(:-), но горжусь, что сам до этого додумался. Даже потом нашел в сети. Но это только первый шаг в вычислении срс, а вот второго шага почему-то никто не сделал(:-)! Значит, я первый буду!

Что такое полутабличный способ, я не совсем понимаю. Это ваше определение?

Так что, никто не поможет с листингом компилированного варианта?

[pitt]

Чего я не понял, так это мы о скорости говорим или о чем? Или цена таблицы во флеше слишком высока?

[singlskv]

Или цена таблицы во флеше слишком высока?

Иногда высока, а иногда нет.
Скомпилируйте Ваш код для AVR, напишите сколько байтов(слов) у Вас получилось,
сколько памяти FLASH заняла Ваша таблица, и т.д., и т.п.
И тогда обсудим ...

Чего я не понял, так это мы о скорости говорим или о чем?

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

Код

uchar crc8 (uchar crc, uchar byte)
{
  byte^=crc;
  crc=0;
  if(byte&0x01) crc =0x5E;
  if(byte&0x02) crc^=0xBC;
  if(byte&0x04) crc^=0x61;
  if(byte&0x08) crc^=0xC2;
  if(byte&0x10) crc^=0x9D;
  if(byte&0x20) crc^=0x23;
  if(byte&0x40) crc^=0x46;
  if(byte&0x80) crc^=0x8C;
  return crc;
}

Я думаю, что по размеру/скорости такой вариант окажется лучше чем табличный на 256 значений.

[singlskv]

Но это только первый шаг в вычислении срс, а вот второго шага почему-то никто не сделал(:-)! Значит, я первый буду!

Ну например, вторым шагом может быть, запоминание всех этих
констант 0x5E,0xBC,0x61,0xC2,0x9D,0x23,0x46,0x8C
в регистрах, типа чтобы для каждого байта их не грузить.
Ну или еще что-то в том же духе.

Опубликуйте код на ASM, и тогда обсудим.

[=GM=]

Ну например, вторым шагом может быть, запоминание всех этих
констант 0x5E,0xBC,0x61,0xC2,0x9D,0x23,0x46,0x8C
в регистрах, типа чтобы для каждого байта их не грузить.
Ну или еще что-то в том же духе.
Опубликуйте код на ASM, и тогда обсудим.

Ну вот, отдаю на суд общественности.

Код

z – указатель на входной массив
bytcnt – счетчик байт минус 1
byte – рабочий регистр
temp – рабочий регистр
calcrc – рассчитанная КЦК

crc8:
    ld    byte,z+
    ldi    bytcnt,8-1;счетчик байт минус 1
orbit:
    ld    temp,x+
    eor    byte,temp
    dec    bitcnt
    brne    orbit
    clr    calcrc
    ldi    temp,0x5E
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0xBC
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0x61
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0xC2
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0x9D
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0x23
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0x46
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0x8C
    sbrc    byte,0
    ret

Всего 69 МЦ. Кстати, КЦК одного байта считается за 24 МЦ и если использовать расчет КЦК для каждого байта, то получится 24*7=161 МЦ. Сравните с 525 МЦ(:-).

[Oldring]

Код

    sbrc    byte,0
    ret

Это круто ))

P.S. Соревноваться в крутости оптимизации с сишным компилятором глупо, так как результат заранее очевиден.

P.P.S. Предлагаемый алгоритм - 3 таста на бит - не дает никаких преимуществ по сравнению с просто развернутым побитовым циклом со сдвигами. Ускорение примерно в два раза может дать обработка по нибблам - при этом таблицу констант размером 16 байт следует предварительно скопировать в RAM и разместить в начале или конце 256-байтной страницы. См. инструкцию SWAP.

[pitt]

Ускорение примерно в два раза может дать обработка по нибблам - при этом таблицу констант размером 16 байт следует предварительно скопировать в RAM и разместить в начале или конце 256-байтной страницы. См. инструкцию SWAP.

А вот RAM, как раз очень жалко, a 256 байт флеша - нисколько!

[_artem_]

Ну например, вторым шагом может быть, запоминание всех этих
констант 0x5E,0xBC,0x61,0xC2,0x9D,0x23,0x46,0x8C
в регистрах, типа чтобы для каждого байта их не грузить.
Ну или еще что-то в том же духе.
Опубликуйте код на ASM, и тогда обсудим.

Ну вот, отдаю на суд общественности.

Код

z – указатель на входной массив
bytcnt – счетчик байт минус 1
byte – рабочий регистр
temp – рабочий регистр
calcrc – рассчитанная КЦК

crc8:
    ld    byte,z+
    ldi    bytcnt,8-1;счетчик байт минус 1
orbit:
    ld    temp,x+
    eor    byte,temp
    dec    bitcnt
    brne    orbit
    clr    calcrc
    ldi    temp,0x5E
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0xBC
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0x61
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0xC2
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0x9D
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0x23
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0x46
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0x8C
    sbrc    byte,0
    ret

Всего 69 МЦ. Кстати, КЦК одного байта считается за 24 МЦ и если использовать расчет КЦК для каждого байта, то получится 24*7=161 МЦ. Сравните с 525 МЦ(:-).

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

удачи.

[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, можно сэкономить еще три такта на обрабатываемый байт.

[=GM=]

Код

    sbrc    byte,0
    ret

Это круто ))
P.S. Соревноваться в крутости оптимизации с сишным компилятором глупо, так как результат заранее очевиден.
P.P.S. Предлагаемый алгоритм - 3 такта на бит - не дает никаких преимуществ по сравнению с просто развернутым побитовым циклом со сдвигами. Ускорение примерно в два раза может дать обработка по нибблам - при этом таблицу констант размером 16 байт следует предварительно скопировать в RAM и разместить в начале или конце 256-байтной страницы. См. инструкцию SWAP.

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

Код

crc8:
    ld    byte,z+
    ldi    bytcnt,8-1;счетчик байт минус 1
orbit:
    ld    temp,x+
    eor    byte,temp
    dec    bitcnt
    brne    orbit
    clr    calcrc
    ldi    temp,0x5E
    sbrc    byte,0
    eor    calcrc,temp
    ldi    temp,0xBC
    sbrc    byte,1
    eor    calcrc,temp
    ldi    temp,0x61
    sbrc    byte,2
    eor    calcrc,temp
    ldi    temp,0xC2
    sbrc    byte,3
    eor    calcrc,temp
    ldi    temp,0x9D
    sbrc    byte,4
    eor    calcrc,temp
    ldi    temp,0x23
    sbrc    byte,5
    eor    calcrc,temp
    ldi    temp,0x46
    sbrc    byte,6
    eor    calcrc,temp
    ldi    temp,0x8C
    sbrc    byte,7
    eor    calcrc,temp
    ret

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

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

[Oldring]

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

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

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

[singlskv]

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

без учета ret - да. Только это - не CRC

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

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


Вот так:

Код

crc8:        ;Input: r31:r30 buffer; r18 - number of bytes    
             ;Output: r16 = CRC
        ldi        r16,0x5e
        mov        r8,r16
        ldi        r16,0xbc
        mov        r9,r16
        ldi        r16,0x61
        mov        r10,r16
        ldi        r16,0xc2
        mov        r11,r16
        ldi        r16,0x9d
        mov        r12,r16
        ldi        r16,0x23
        mov        r13,r16
        ldi        r16,0x46
        mov        r14,r16
        ldi        r16,0x8c
        mov        r15,r16
        clr        r16

crc8_0:
        ld        r17,z+
        eor        r17,r16
        clr        r16
        sbrc    r17,0
        eor        r16,r8
        sbrc    r17,1
        eor        r16,r9
        sbrc    r17,2
        eor        r16,r10
        sbrc    r17,3
        eor        r16,r11
        sbrc    r17,4
        eor        r16,r12
        sbrc    r17,5
        eor        r16,r13
        sbrc    r17,6
        eor        r16,r14
        sbrc    r17,7
        eor        r16,r15

        dec        r18
        brne    crc8_0
        ret

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

[Oldring]

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

[ivstech]

Вот мой код расчета 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

[_Bill]

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

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

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

[aaarrr]

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

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

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

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

[_Bill]

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

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

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

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

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

[Oldring]

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

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

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

Код

    mov r17, r16
    swap r16
    andi r17, 0x0f
    eor r16, r17
    lsl r17
    eor r16, r17

    mov r17, r16
    swap r16
    andi r17, 0x0f
    eor r16, r17
    lsl r17
    eor r16, r17

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

[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 позволяют обойтись минимальным количеством вложений.

[Oldring]

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

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

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

[aaarrr]

Зависит, но это не имеет большого значения.

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

[_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+              ; Выбрать очередной элемент таблицы

[aaarrr]

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

Как нет и в AVR времен PIC16

[_Bill]

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

Как нет и в AVR времен PIC16

Само собой. Они там (в AVR) немного меньше.

[=GM=]

Это точно не CRC

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

Тем не менее считаю, что дискуссия была полезной, мне-то уж точно(:-). Спасибо всем участникам.

[Smen]

Дяденьки, подскажите, плиз!
Если у меня принимаются байты (по UART, если что), в которых, только семь младших битов информационные, а старший - служебный (определяет начало посылки), то какой алгоритм брать, CRC-8, или CRC-7?
Нашёл тут расчёт CRC-7, но там всё-равно "обрабатываются" все восемь битов, а затем старший бит принудительно обнуляется.

[zombi]

какой алгоритм брать, CRC-8, или CRC-7?

Считайте CRC-8 и не морочьте себе голову.
Но учтите что :

Назначение CRC это гарантированное обнаружение одинарных, двойных, тройных и нечетных ошибок при максимальной длине блока: 15, 4095, 268435455 байт, соответственно для CRC 8, 16, 32.

[Smen]

Считайте CRC-8 и не морочьте себе голову.

Так, а будет ли CRC-8, у которого обрезан старший бит выполнять свои функции?

Назначение CRC это гарантированное обнаружение одинарных, двойных, тройных и нечетных ошибок при максимальной длине блока: 15, 4095, 268435455 байт, соответственно для CRC 8, 16, 32.

А разве это не от полинома зависит?
Я правильно понял, что для CRC-8 максимальная длинна блока 8 байт (что б все ошибки гарантированно обнаруживались)?