Оптимизация алгоритма на С, вопрос к знатокам компиляторов Опции

[singlskv]

Есть два варианта функции вычисления CRC:

Код

unsigned char code[8]={0x01,0xd0,0x5e,0x3c,0x0d,0x00,0x00,0x84};

unsigned char crc8_1(unsigned char *buff,unsigned char num)
{
    unsigned char i=0,j,tmp,data,crc=0;
    for (i=0;i<num;i++) {
        data=*buff++;
        for (j=0;j<8;j++) {
            tmp=1&(data^crc);
            crc>>=1;
            data>>=1;
            if (tmp!=0) crc^=0x8c;
        }
    }
    return crc;
}

unsigned char crc8_2(unsigned char *buff,unsigned char num)
{
    unsigned char i=num,j,tmp,data,crc=0;
    for (;i>0;i--) {
        data=*buff++;
        for (j=8;j>0;j--) {
            tmp=1&(data^crc);
            crc>>=1;
            data>>=1;
            if (tmp!=0) crc^=0x8c;
        }
    }
    return crc;
}

int main(int argc, char* argv[])
{
    unsigned char crc_;
    crc_=crc8_1(code,7);
    crc_=crc8_2(code,7);
    return 0;
}

Как видно из рисунка, это собственно один и тот же алгоритм.
Но, при компиляции под WinAVR(gcc), при любом уровне оптимизации, второй
вариант работает на 10-15% быстрее.
Собственно вопрос: а есть ли компилятор который может скомпилировать
эти две(одинаковых!) функции в одинаковый(быстрый) код ?

[defunct]

Вы уверены что у вас считается именно CRC?
Попробуйте такой код:

Код

/**********************************************************
*   Функция РАСЧЕТА CRC8 (по полиному X8 + X5 + X2 + 1)  
* Оптимизация по объему требуемой памяти и по скорости
* ---> packet - массив данных                            
* ---> size - количество байт в пакете                  
* <--- результат расчитанной CRC8                        
**********************************************************/
U8 rtm_crc8(U8 *packet, U8 size)
{
#define h_byte (1)
#define l_byte (0)
typedef union _DummyUnion
{
  U16 word;
  U8  bytes[sizeof(U16)];
} DummyUnion;

  DummyUnion tempDivisor;
  DummyUnion tempData;
  U8 i;

  if (size < 2)
    return crc8_ERROR;

  tempData.bytes[h_byte] = *packet++;
  size -= 1;
  do
  {
    tempData.bytes[l_byte] = *packet++;
    tempDivisor.word = 0x9280;  // полином X8 + X5 + X2 + 1

    i = 0x80;
    do
    {
      if (i & tempData.bytes[h_byte])
      {
        tempData.word ^= tempDivisor.word;
      }
      tempDivisor.word >>=1;
      i >>= 1;
    } while (i);

    tempData.bytes[h_byte] = tempData.bytes[l_byte];
    size -= 1;
  } while (size);
  return tempData.bytes[h_byte];
}

[KRS]

конечно 2 вариант быстрее!
дело в организации цикла!
он скомпилируется по другому примерно так:

Код

  mov r16, 8
loop:
  .....
  .....
  dec r16
  brne loop

а 1 вариант подразумевает лишнюю команду сравнения

Код

  mov r16, 0
loop:
  .....
  .....
  inc r16
  cpi r16, 8
  brcs loop

а вообще для полной потимизации я пишу такие циклы так

Код

j=8;
do {
  ....
  ....
}while(--j);

[vet]

Собственно вопрос: а есть ли компилятор который может скомпилировать
эти две(одинаковых!) функции в одинаковый(быстрый) код ?

IAR.

[Old1]

Собственно вопрос: а есть ли компилятор который может скомпилировать
эти две(одинаковых!) функции в одинаковый(быстрый) код ?

IAR.

К сожалению нет времени проверять... Вы уверены, что IAR эти функции скомпилирует одинаково оптимально? Вопрос задаю потому, что сами ИАРовцы рекомендуют (AN AVR035) для оптимизации кода по возможности использовать вычитающие циклические счетчики и предварительный декремент.

[singlskv]

Вы уверены что у вас считается именно CRC?

Да уверен.
Это CRC для 1-wire по полиному X8+X5+X4+1.

конечно 2 вариант быстрее!
дело в организации цикла!

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

Собственно вопрос: а есть ли компилятор который может скомпилировать
эти две(одинаковых!) функции в одинаковый(быстрый) код ?

IAR.

Вы проверяли ?
Если да, то сообщите пожалуйста сколько тактов получилось у каждой
функции при наилучшей оптимизации.

К сожалению нет времени проверять... Вы уверены, что IAR эти функции скомпилирует одинаково оптимально? Вопрос задаю потому, что сами ИАРовцы рекомендуют (AN AVR035) для оптимизации кода по возможности использовать вычитающие циклические счетчики и предварительный декремент.

Собственно, если кто проверит, сообщите результат.

[vet]

Скомпилировал в IAR 4.11A два цикла for с инкрементом от 0 до 8 и декрементом от 8 до 0, макс.оптимизация по скорости. Код одинаков.

Код

        RSEG CODE:CODE:NOROOT(1)
//    3 void main() {
main:
//    4 char i;

//    5   for (i=0;i<8;i++) {
        LDI    R16, 8
//    6     asm("nop");
??main_0:
        nop
//    7   }
        DEC    R16
        BRNE    ??main_0

//    8   for (i=8;i;i--) {
        LDI    R16, 8
//    9     asm("nop");
??main_1:
        nop
//   10   }
        DEC    R16
        BRNE    ??main_1

//   11 }
        RET

Выкладываю листинг компиляции вышеприведённого исходника:

Код

        RSEG CODE:CODE:NOROOT(1)
//    3 unsigned char crc8_1(unsigned char *buff,unsigned char num)
crc8_1:
//    4 {
//    5     unsigned char i=0,j,tmp,data,crc=0;
        LDI    R21, 0
//    6     for (i=0;i<num;i++) {
        LDI    R20, 0
        RJMP    ??crc8_1_0
//    7         data=*buff++;
??crc8_1_1:
        MOVW    R31:R30, R17:R16
        LD    R23, Z+
        MOVW    R17:R16, R31:R30
//    8         for (j=0;j<8;j++) {
        LDI    R19, 8
//    9             tmp=1&(data^crc);
??crc8_1_2:
        MOV    R0, R23
        BST    R0, 0
        CLR    R0
        BLD    R0, 0
        MOV    R22, R21
        ANDI    R22, 0x01
        EOR    R22, R0
        ANDI    R22, 0x01
//   10             crc>>=1;
        LSR    R21
//   11             data>>=1;
        LSR    R23
//   12             if (tmp!=0) crc^=0x8c;
        TST    R22
        BREQ    ??crc8_1_3
        LDI    R22, 140
        EOR    R21, R22
//   13         }
??crc8_1_3:
        DEC    R19
        BRNE    ??crc8_1_2
//   14     }
        INC    R20
??crc8_1_0:
        CP    R20, R18
        BRCS    ??crc8_1_1
//   15     return crc;
        MOV    R16, R21
        RET
//   16 }
//   17

        RSEG CODE:CODE:NOROOT(1)
//   18 unsigned char crc8_2(unsigned char *buff,unsigned char num)
crc8_2:
//   19 {
//   20     unsigned char i=num,j,tmp,data,crc=0;
        MOV    R19, R18
        LDI    R20, 0
        RJMP    ??crc8_2_0
//   21     for (;i>0;i--) {
//   22         data=*buff++;
??crc8_2_1:
        MOVW    R31:R30, R17:R16
        LD    R22, Z+
        MOVW    R17:R16, R31:R30
//   23         for (j=8;j>0;j--) {
        LDI    R18, 8
//   24             tmp=1&(data^crc);
??crc8_2_2:
        MOV    R23, R22
        ANDI    R23, 0x01
        MOV    R21, R20
        ANDI    R21, 0x01
        EOR    R21, R23
        ANDI    R21, 0x01
//   25             crc>>=1;
        LSR    R20
//   26             data>>=1;
        LSR    R22
//   27             if (tmp!=0) crc^=0x8c;
        TST    R21
        BREQ    ??crc8_2_3
        LDI    R21, 140
        EOR    R20, R21
//   28         }
??crc8_2_3:
        DEC    R18
        BRNE    ??crc8_2_2
//   29     }
        DEC    R19
??crc8_2_0:
        TST    R19
        BRNE    ??crc8_2_1
//   30     return crc;
        MOV    R16, R20
        RET
//   31 }
//   32

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

Сообщение отредактировал vet - Aug 24 2006, 10:37

[µµC]

Да уверен.
Это CRC для 1-wire по полиному X8+X5+X4+1.

Код

U8 CRC8_1 (U8 val, U8 crc)
{
  U8 tmp;
  U8 i = 8;
  do {
    tmp = (val ^ crc) & 0x01;
    crc >>= 1;
    val >>= 1;
    if (tmp != 0) crc ^= 0x8c;
  } while (--i);
  return crc;
}

U8 CRC8_2(U8 data, U8 crc)
{
  U8 i = data ^ crc;
  crc = 0;
  if (i & 0x01) crc ^= 0x5e;
  if (i & 0x02) crc ^= 0xbc;
  if (i & 0x04) crc ^= 0x61;
  if (i & 0x08) crc ^= 0xc2;
  if (i & 0x10) crc ^= 0x9d;
  if (i & 0x20) crc ^= 0x23;
  if (i & 0x40) crc ^= 0x46;
  if (i & 0x80) crc ^= 0x8c;
  return crc;
}

CRC8_1 это твой вариант для одного байта. CRC8_2 имеет тот же полином, но работает значительно быстрее.

Сообщение отредактировал µµC - Aug 24 2006, 12:43

[Old1]

Скомпилировал в IAR 4.11A два цикла for с инкрементом от 0 до 8 и декрементом от 8 до 0, макс.оптимизация по скорости. Код одинаков.
...

Но если поставить оптимизацию по объему кода, то появляется тот эффект о котором писал автор, функция с циклом с декрементом выполняется быстрее. (Я обычно использую оптимизацию по объему, и когда спрашивал упустил, что автора интересует максимальная скорость.)

[µµC]

Но если поставить оптимизацию по объему кода, то появляется тот эффект о котором писал автор, функция с циклом с декрементом выполняется быстрее.

Человек явно ищет идеальный компилятор, а их, как известно, в природе не бывает. От программиста требуется хорошо знать какой будет код в какой ситуации, "чувствовать селезенкой", "заставлять" компилятор быть эффективным. Например:

Код

U8 CRC8_1 (U8 val, U8 crc)
{
  U8 tmp;
  U8 i = 8;
  do {
    tmp = (val ^ crc) & 0x01;
    crc >>= 1;
    val >>= 1;
    if (tmp != 0) crc ^= 0x8c;
  } while (--i);
  return crc;
}

U8 CRC8_1 (U8 val, U8 crc)
{
  U8 tmp;
  U8 i = 8;
  do {
    tmp = (val ^ crc);
    crc >>= 1;
    val >>= 1;
    if (tmp & 0x01) crc ^= 0x8c;
  } while (--i);
  return crc;
}

154 цикла к 122. А, казалось бы, от перемены мест ...

[singlskv]

Скомпилировал в IAR 4.11A два цикла for с инкрементом от 0 до 8 и декрементом от 8 до 0, макс.оптимизация по скорости. Код одинаков.

Код

        RSEG CODE:CODE:NOROOT(1)
//    3 void main() {
main:
//    4 char i;

//    5   for (i=0;i<8;i++) {
        LDI    R16, 8
   ..............................................................

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

Выкладываю листинг компиляции вышеприведённого исходника:

Код

        RSEG CODE:CODE:NOROOT(1)
//    3 unsigned char crc8_1(unsigned char *buff,unsigned char num)
crc8_1:
//    4 {
//    5     unsigned char i=0,j,tmp,data,crc=0;
        LDI    R21, 0
//    6     for (i=0;i<num;i++) {
        LDI    R20, 0
        RJMP    ??crc8_1_0
//    7         data=*buff++;
??crc8_1_1:
        MOVW    R31:R30, R17:R16
        LD    R23, Z+
        MOVW    R17:R16, R31:R30
//    8         for (j=0;j<8;j++) {
        LDI    R19, 8
//    9             tmp=1&(data^crc);
??crc8_1_2:
        MOV    R0, R23
        BST    R0, 0
        CLR    R0
        BLD    R0, 0
        MOV    R22, R21
        ANDI    R22, 0x01
        EOR    R22, R0
        ANDI    R22, 0x01
//   10             crc>>=1;
        LSR    R21
//   11             data>>=1;
        LSR    R23
//   12             if (tmp!=0) crc^=0x8c;
        TST    R22
        BREQ    ??crc8_1_3
        LDI    R22, 140
        EOR    R21, R22
//   13         }
??crc8_1_3:
        DEC    R19
        BRNE    ??crc8_1_2
//   14     }
        INC    R20
??crc8_1_0:
        CP    R20, R18
        BRCS    ??crc8_1_1
//   15     return crc;
        MOV    R16, R21
        RET
//   16 }
//   17

        RSEG CODE:CODE:NOROOT(1)
//   18 unsigned char crc8_2(unsigned char *buff,unsigned char num)
crc8_2:
//   19 {
//   20     unsigned char i=num,j,tmp,data,crc=0;
        MOV    R19, R18
        LDI    R20, 0
        RJMP    ??crc8_2_0
//   21     for (;i>0;i--) {
//   22         data=*buff++;
??crc8_2_1:
        MOVW    R31:R30, R17:R16
        LD    R22, Z+
        MOVW    R17:R16, R31:R30
//   23         for (j=8;j>0;j--) {
        LDI    R18, 8
//   24             tmp=1&(data^crc);
??crc8_2_2:
        MOV    R23, R22
        ANDI    R23, 0x01
        MOV    R21, R20
        ANDI    R21, 0x01
        EOR    R21, R23
        ANDI    R21, 0x01
//   25             crc>>=1;
        LSR    R20
//   26             data>>=1;
        LSR    R22
//   27             if (tmp!=0) crc^=0x8c;
        TST    R21
        BREQ    ??crc8_2_3
        LDI    R21, 140
        EOR    R20, R21
//   28         }
??crc8_2_3:
        DEC    R18
        BRNE    ??crc8_2_2
//   29     }
        DEC    R19
??crc8_2_0:
        TST    R19
        BRNE    ??crc8_2_1
//   30     return crc;
        MOV    R16, R20
        RET
//   31 }
//   32

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

Просимулировал Ваш код в AVR Studio.
Итого: (для семи байт)
crc8_1 986 тактов
crc8_2 774 такта
разница слегка удивила, это уже 25%.

очень повеселил этот код:

Код

        MOVW    R31:R30, R17:R16
        LD    R22, Z+
        MOVW    R17:R16, R31:R30

и так 7 раз подряд

[singlskv]

Да уверен.
Это CRC для 1-wire по полиному X8+X5+X4+1.

Код

U8 CRC8_1 (U8 val, U8 crc)
{
  U8 tmp;
  U8 i = 8;
  do {
    tmp = (val ^ crc) & 0x01;
    crc >>= 1;
    val >>= 1;
    if (tmp != 0) crc ^= 0x8c;
  } while (--i);
  return crc;
}

U8 CRC8_2(U8 data, U8 crc)
{
  U8 i = data ^ crc;
  crc = 0;
  if (i & 0x01) crc ^= 0x5e;
  if (i & 0x02) crc ^= 0xbc;
  if (i & 0x04) crc ^= 0x61;
  if (i & 0x08) crc ^= 0xc2;
  if (i & 0x10) crc ^= 0x9d;
  if (i & 0x20) crc ^= 0x23;
  if (i & 0x40) crc ^= 0x46;
  if (i & 0x80) crc ^= 0x8c;
  return crc;
}

CRC8_1 это твой вариант для одного байта. CRC8_2 имеет тот же полином, но работает значительно быстрее.

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

[µµC]

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

Код

#define U8 unsigned char

U8 code[8] = {0x01, 0xd0, 0x5e, 0x3c, 0x0d, 0x00, 0x00, 0x84};

U8 crc8_1(U8 *buff, U8 num)
{
  U8 i, tmp, val, crc = 0;
  
  do {
    val = *buff++;
    i = 8;
    do {
      tmp = (val ^ crc);
      crc >>= 1;
      val >>= 1;
      if (tmp & 0x01) crc ^= 0x8c;
    } while (--i);      
  } while (--num);
  return crc;
}

U8 crc8_2(U8 *buff, U8 num)
{
  U8 val, crc = 0;
  
  do {
    val = *buff++;
    val ^= crc;
    crc = 0;
    if(val & 0x01) crc ^= 0x5e;
    if(val & 0x02) crc ^= 0xbc;
    if(val & 0x04) crc ^= 0x61;
    if(val & 0x08) crc ^= 0xc2;
    if(val & 0x10) crc ^= 0x9d;
    if(val & 0x20) crc ^= 0x23;
    if(val & 0x40) crc ^= 0x46;
    if(val & 0x80) crc ^= 0x8c;    
  } while (--num);
  return crc;
}

volatile U8 result[4];

void main(void)
{
   while (1) {
    result[0] = crc8_1(code, 7); //649
    result[1] = crc8_2(code, 7); //265
    result[2] = crc8_1(code, 7);
    result[3] = crc8_2(code, 7);
   }
}

IAR, opt = max speed, остальные опции выкл.

649 циклов к 265.

[singlskv]

Человек явно ищет идеальный компилятор, а их, как известно, в природе не бывает.

Лучший компилятор это человек.
на ASM у меня получилось 530 тактов:

Код

crc8:    ;Input: X - buffer; r17 - number of bytes    
    ;Output: r16 = CRC

    ldi    r16,0    ;CRC
    ldi    r20,0x8c
crc8_1:
    ld    r18,X+
    ldi    r19,8
crc8_2:
    lsr    r16
    brbc    0,crc8_3
    eor    r16,r20
crc8_3:
    sbrc    r18,0
    eor    r16,r20
    lsr    r18
crc8_4:
    dec    r19
    brne    crc8_2
    dec    r17
    brne    crc8_1

    ret

НО, надо отдать должное WinAVR(gcc)

ИТОГО:

Код

                    CRC8_1    CRC8_2
WinAVR(-o1)        620           556
WinAVR(-o2)        620           556
WinAVR(-o3)        606           544

IAR                986           774

ASM                       530

У WinAVR(-o3) удалось украсть всего 14 тактов, то есть по 2 такта на основной цикл.
Приятно удививший результат

А с IAR просто какая-то лабудень, возможно Вы vet там чего-то не то указали при
оптимизации?

[µµC]

Лучший компилятор это человек.

Не спорю, лучший. Только слишком дорогой и медленный, а в остальном ... лучший.

[singlskv]

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

Код

#define U8 unsigned char

U8 code[8] = {0x01, 0xd0, 0x5e, 0x3c, 0x0d, 0x00, 0x00, 0x84};

U8 crc8_1(U8 *buff, U8 num)
{
  U8 i, tmp, val, crc = 0;
  
  do {
    val = *buff++;
    i = 8;
    do {
      tmp = (val ^ crc);
      crc >>= 1;
      val >>= 1;
      if (tmp & 0x01) crc ^= 0x8c;
    } while (--i);      
  } while (--num);
  return crc;
}

U8 crc8_2(U8 *buff, U8 num)
{
  U8 val, crc = 0;
  
  do {
    val = *buff++;
    val ^= crc;
    crc = 0;
    if(val & 0x01) crc ^= 0x5e;
    if(val & 0x02) crc ^= 0xbc;
    if(val & 0x04) crc ^= 0x61;
    if(val & 0x08) crc ^= 0xc2;
    if(val & 0x10) crc ^= 0x9d;
    if(val & 0x20) crc ^= 0x23;
    if(val & 0x40) crc ^= 0x46;
    if(val & 0x80) crc ^= 0x8c;    
  } while (--num);
  return crc;
}

volatile U8 result[4];

void main(void)
{
   while (1) {
    result[0] = crc8_1(code, 7); //649
    result[1] = crc8_2(code, 7); //265
    result[2] = crc8_1(code, 7);
    result[3] = crc8_2(code, 7);
   }
}

IAR, opt = max speed, остальные опции выкл.

649 циклов к 265.

649 уже намного ближе к правде (если не сложно, листинг в студию), но у WinAVR 544.
265 - отличный результат, но мы обсуждаем алгоритм(оптимизацию компилятором)
в общем виде (таблицой из 256 значений как в даташите "1-wire" все равно быстрее).

[zltigo]

Лучший компилятор это человек.

Не спорю, лучший. Только слишком дорогой и медленный..

и 'ломается' на больших кусках кода :-(

в общем виде (таблицой из 256 значений как в даташите "1-wire" все равно быстрее).

Быстрее :-) сопроцессор поставить....

Код

//---------------------------------------------------------------------------
// Verilog module containing a synthesizable CRC8 function
//   - Polynomial: (8 5 4 0)
//   - Data width: 8
//   - CRC width : 8
//   - Mirror
//---------------------------------------------------------------------------
module CRC8_8540;

  function [7:0] nextCRC;

    input [7:0] Data;
    input [7:0] CRC;

    reg [7:0] D;
    reg [7:0] C;
    reg [7:0] xCRC;


      begin

    D = Data;
    C = CRC;

    // Mirror DATA and final CRC
    xCRC[7] = D[1]^D[3]^D[4]^D[7]^C[7]^C[4]^C[3]^C[1];
    xCRC[6] = D[0]^D[2]^D[3]^D[6]^C[6]^C[3]^C[2]^C[0];
    xCRC[5] = D[1]^D[2]^D[5]^C[5]^C[2]^C[1];
    xCRC[4] = D[0]^D[1]^D[4]^C[4]^C[1]^C[0];
    xCRC[3] = D[0]^D[1]^D[4]^D[7]^C[7]^C[4]^C[1]^C[0];
    xCRC[2] = D[0]^D[1]^D[4]^D[6]^D[7]^C[7]^C[6]^C[4]^C[1]^C[0];
    xCRC[1] = D[0]^D[3]^D[5]^D[6]^C[6]^C[5]^C[3]^C[0];
    xCRC[0] = D[2]^D[4]^D[5]^C[5]^C[4]^C[2];

    nextCRC = xCRC;

      end

  endfunction

endmodule

Извините :-( Настроение сегодня такое :-).
А верилоговский код рабочий под Dallas - вдруг кому пригодится. Использую я его, поскольку полином хорош для любых небольших пакетов.

[µµC]

если не сложно, листинг в студию

NAME crc8

RSEG CSTACK:DATA:NOROOT(0)
RSEG RSTACK:DATA:NOROOT(0)

EXTERN ?need_segment_init

PUBWEAK `?<Segment init: TINY_I>`
PUBWEAK `?<Segment init: TINY_Z>`
PUBWEAK __?EEARL
PUBWEAK __?EECR
PUBWEAK __?EEDR
PUBLIC code
PUBLIC crc8_1
PUBLIC crc8_2
PUBLIC main
PUBLIC result

RSEG TINY_I:DATA:NOROOT(0)
REQUIRE `?<Segment init: TINY_I>`
// 49 U8 code[8] = {0x01, 0xd0, 0x5e, 0x3c, 0x0d, 0x00, 0x00, 0x84};
code:
DS 8
REQUIRE `?<Initializer for code>`
// 50

RSEG CODE:CODE:NOROOT(1)
// 51 U8 crc8_1(U8 *buff, U8 num)
crc8_1:
// 52 {
// 53 U8 i, tmp, val, crc = 0;
LDI R19, 0
// 54
// 55 do {
// 56 val = *buff++;
??crc8_1_0:
MOV R30, R16
LD R21, Z+
MOV R16, R30
// 57 i = 8;
LDI R18, 8
// 58 do {
// 59 tmp = (val ^ crc);
??crc8_1_1:
MOV R20, R19
EOR R20, R21
// 60 crc >>= 1;
LSR R19
// 61 val >>= 1;
LSR R21
// 62 if (tmp & 0x01) crc ^= 0x8c;
BST R20, 0
BRTC ??crc8_1_2
LDI R20, 140
EOR R19, R20
// 63 } while (--i);
??crc8_1_2:
DEC R18
BRNE ??crc8_1_1
// 64 } while (--num);
DEC R17
BRNE ??crc8_1_0
// 65 return crc;
MOV R16, R19
RET
// 66 }
// 67

RSEG CODE:CODE:NOROOT(1)
// 68 U8 crc8_2(U8 *buff, U8 num)
crc8_2:
// 69 {
// 70 U8 val, crc = 0;
LDI R18, 0
// 71
// 72 do {
// 73 val = *buff++;
??crc8_2_0:
MOV R30, R16
LD R20, Z+
MOV R16, R30
// 74 val ^= crc;
EOR R20, R18
// 75 crc = 0;
LDI R18, 0
// 76 if(val & 0x01) crc ^= 0x5e;
BST R20, 0
BRTC ??crc8_2_1
LDI R18, 94
// 77 if(val & 0x02) crc ^= 0xbc;
??crc8_2_1:
BST R20, 1
BRTC ??crc8_2_2
LDI R19, 188
EOR R18, R19
// 78 if(val & 0x04) crc ^= 0x61;
??crc8_2_2:
BST R20, 2
BRTC ??crc8_2_3
LDI R19, 97
EOR R18, R19
// 79 if(val & 0x08) crc ^= 0xc2;
??crc8_2_3:
BST R20, 3
BRTC ??crc8_2_4
LDI R19, 194
EOR R18, R19
// 80 if(val & 0x10) crc ^= 0x9d;
??crc8_2_4:
BST R20, 4
BRTC ??crc8_2_5
LDI R19, 157
EOR R18, R19
// 81 if(val & 0x20) crc ^= 0x23;
??crc8_2_5:
BST R20, 5
BRTC ??crc8_2_6
LDI R19, 35
EOR R18, R19
// 82 if(val & 0x40) crc ^= 0x46;
??crc8_2_6:
BST R20, 6
BRTC ??crc8_2_7
LDI R19, 70
EOR R18, R19
// 83 if(val & 0x80) crc ^= 0x8c;
??crc8_2_7:
BST R20, 7
BRTC ??crc8_2_8
LDI R19, 140
EOR R18, R19
// 84 } while (--num);
??crc8_2_8:
DEC R17
BRNE ??crc8_2_0
// 85 return crc;
MOV R16, R18
RET
// 86 }
// 87

RSEG TINY_Z:DATA:NOROOT(0)
REQUIRE `?<Segment init: TINY_Z>`
// 88 volatile U8 result[4];
result:
DS 4
// 89

RSEG CODE:CODE:NOROOT(1)
// 90 void main(void)
main:
??main_0:
// 91 {
// 92 while (1) {
// 93 result[0] = crc8_1(code, 7); //649
LDI R17, 7
LDI R16, code
RCALL crc8_1
LDI R30, result
ST Z, R16
// 94 result[1] = crc8_2(code, 7); //265
LDI R17, 7
LDI R16, code
RCALL crc8_2
LDI R30, result
STD Z+1, R16
// 95 result[2] = crc8_1(code, 7);
LDI R17, 7
LDI R16, code
RCALL crc8_1
LDI R30, result
STD Z+2, R16
// 96 result[3] = crc8_2(code, 7);
LDI R17, 7
LDI R16, code
RCALL crc8_2
LDI R30, result
STD Z+3, R16
RJMP ??main_0
// 97 }
// 98 }

ASEGN ABSOLUTE:DATA:NOROOT,01cH
__?EECR:

ASEGN ABSOLUTE:DATA:NOROOT,01dH
__?EEDR:

ASEGN ABSOLUTE:DATA:NOROOT,01eH
__?EEARL:

RSEG TINY_ID:CODE:NOROOT(0)
`?<Initializer for code>`:
DB 1, 208, 94, 60, 13, 0, 0, 132

RSEG INITTAB:CODE:NOROOT(0)
`?<Segment init: TINY_I>`:
DB SFE(TINY_I) - SFB(TINY_I)
DB SFB(TINY_I)
DW SFB(TINY_ID)
REQUIRE ?need_segment_init

RSEG INITTAB:CODE:NOROOT(0)
`?<Segment init: TINY_Z>`:
DB SFE(TINY_Z) - SFB(TINY_Z)
DB SFB(TINY_Z)
DW 0
REQUIRE ?need_segment_init

END

[singlskv]

если не сложно, листинг в студию

.....................
.....................
LDI R20, 140
EOR R19, R20
.....................
.....................

Ну вот она, похоже основная ошибка IAR, он загружает 0x8c много раз подряд.
И еще какие-то лишние mov делает.


Это код WinAVR(-o3):

Код

@00000045: crc8_2
20:       {
+00000045:   2FF9        MOV     R31,R25          Copy register
+00000046:   2FE8        MOV     R30,R24          Copy register
21:           unsigned char i=num,j,tmp,data,crc=0;
+00000047:   E090        LDI     R25,0x00         Load immediate
22:           for (;i>0;i--) {
+00000048:   2366        TST     R22              Test for Zero or Minus
+00000049:   F069        BREQ    PC+0x0E          Branch if equal
+0000004A:   E84C        LDI     R20,0x8C         Load immediate
23:               data=*buff++;
+0000004B:   9121        LD      R18,Z+           Load indirect and postincrement
24:               for (j=8;j>0;j--) {
+0000004C:   E038        LDI     R19,0x08         Load immediate
25:                   tmp=1&(data^crc);
+0000004D:   2F82        MOV     R24,R18          Copy register
+0000004E:   2789        EOR     R24,R25          Exclusive OR
26:                   crc>>=1;
+0000004F:   9596        LSR     R25              Logical shift right
27:                   data>>=1;
+00000050:   9526        LSR     R18              Logical shift right
28:                   if (tmp!=0) crc^=0x8c;
+00000051:   FD80        SBRC    R24,0            Skip if bit in register cleared
+00000052:   2794        EOR     R25,R20          Exclusive OR
+00000053:   5031        SUBI    R19,0x01         Subtract immediate
+00000054:   F7C1        BRNE    PC-0x07          Branch if not equal
+00000055:   5061        SUBI    R22,0x01         Subtract immediate
+00000056:   F7A1        BRNE    PC-0x0B          Branch if not equal
32:       }
+00000057:   2F89        MOV     R24,R25          Copy register
+00000058:   2799        CLR     R25              Clear Register
+00000059:   9508        RET                      Subroutine return

[singlskv]

Быстрее :-) сопроцессор поставить....

Код

//---------------------------------------------------------------------------
// Verilog module containing a synthesizable CRC8 function
//   - Polynomial: (8 5 4 0)
//   - Data width: 8
//   - CRC width : 8
//   - Mirror
//---------------------------------------------------------------------------
module CRC8_8540;

  function [7:0] nextCRC;

    input [7:0] Data;
    input [7:0] CRC;

    reg [7:0] D;
    reg [7:0] C;
    reg [7:0] xCRC;


      begin

    D = Data;
    C = CRC;

    // Mirror DATA and final CRC
    xCRC[7] = D[1]^D[3]^D[4]^D[7]^C[7]^C[4]^C[3]^C[1];
    xCRC[6] = D[0]^D[2]^D[3]^D[6]^C[6]^C[3]^C[2]^C[0];
    xCRC[5] = D[1]^D[2]^D[5]^C[5]^C[2]^C[1];
    xCRC[4] = D[0]^D[1]^D[4]^C[4]^C[1]^C[0];
    xCRC[3] = D[0]^D[1]^D[4]^D[7]^C[7]^C[4]^C[1]^C[0];
    xCRC[2] = D[0]^D[1]^D[4]^D[6]^D[7]^C[7]^C[6]^C[4]^C[1]^C[0];
    xCRC[1] = D[0]^D[3]^D[5]^D[6]^C[6]^C[5]^C[3]^C[0];
    xCRC[0] = D[2]^D[4]^D[5]^C[5]^C[4]^C[2];

    nextCRC = xCRC;

      end

  endfunction

endmodule

Ну, это уже из пушки по воробьям
Хотя, если есть свободные ресурсы, то почему бы и нет

[Guest_Serg79_*]

В таких случаях поступают намного проше, пишут функцию на ASM и не ломают голову на счет компилятора.

Код

/** \ingroup util_crc
    Optimized Dallas (now Maxim) iButton 8-bit CRC calculation.

    Polynomial: x^8 + x^5 + x^4 + 1 (0x8C)<br>
    Initial value: 0x0

    See http://www.maxim-ic.com/appnotes.cfm/appnote_number/27

    The following is the equivalent functionality written in C.

    \code
    uint8_t
    _crc_ibutton_update(uint8_t crc, uint8_t data)
    {
    uint8_t i;

    crc = crc ^ data;
    for (i = 0; i < 8; i++)
    {
        if (crc & 0x01)
            crc = (crc >> 1) ^ 0x8C;
        else
            crc >>= 1;
    }

    return crc;
    }
    \endcode
*/

static __inline__ uint8_t
_crc_ibutton_update(uint8_t __crc, uint8_t __data)
{
    uint8_t __i, __pattern;
    __asm__ __volatile__ (
        "    eor    %0, %4" "\n\t"
        "    ldi    %1, 8" "\n\t"
        "    ldi    %2, 0x8C" "\n\t"
        "1:    bst    %0, 0" "\n\t"
        "    lsr    %0" "\n\t"
        "    brtc    2f" "\n\t"
        "    eor    %0, %2" "\n\t"
        "2:    dec    %1" "\n\t"
        "    brne    1b" "\n\t"
        : "=r" (__crc), "=d" (__i), "=d" (__pattern)
        : "0" (__crc), "r" (__data));
    return __crc;
}

И я так думаю, что эта функция будет работать быстрее приведенных выше.

Реализация функции взята из заголовочного файла "crc16.h" компилятора WinAVR.

А принцип простой: не изобретай велосипед. Лучше направить свои усилия на что то новое, чем пытаться заново писать стандартные функции, реализованные в библиотеках идущих вместе с компилятором.

[Rst7]

очень повеселил этот код:

Код

        MOVW    R31:R30, R17:R16
        LD    R22, Z+
        MOVW    R17:R16, R31:R30

и так 7 раз подряд

Хорошо поможет

Код

__z unsigned char crc8_2(unsigned char *buff,unsigned char num)

А циклы ОЧЕНЬ желательно делать

Код

do{}while(--var);

это помогает почти всем компиляторам и процессорам, обычно архитектура процессора позволяет изготовить нечто такое:

Код

DEC var
JUMP_IF_NZ label

[TomaT]

Эх... у 51-го чудная инструкция есть -- DJNZ

[SpiritDance]

Она особенно чудна для конвееров.

[Rst7]

Эх... у 51-го чудная инструкция есть -- DJNZ

Ну не только 51, есть еще Z80, да много таких, но идея инструкции все равно DEC и JUMP_IF_NZ

[singlskv]

В таких случаях поступают намного проше, пишут функцию на ASM и не ломают голову на счет компилятора.

Код

/** \ingroup util_crc
    Optimized Dallas (now Maxim) iButton 8-bit CRC calculation.

    Polynomial: x^8 + x^5 + x^4 + 1 (0x8C)<br>
    Initial value: 0x0

    See http://www.maxim-ic.com/appnotes.cfm/appnote_number/27

    The following is the equivalent functionality written in C.

    \code
    uint8_t
    _crc_ibutton_update(uint8_t crc, uint8_t data)
    {
    uint8_t i;

    crc = crc ^ data;
    for (i = 0; i < 8; i++)
    {
        if (crc & 0x01)
            crc = (crc >> 1) ^ 0x8C;
        else
            crc >>= 1;
    }

    return crc;
    }
    \endcode
*/

static __inline__ uint8_t
_crc_ibutton_update(uint8_t __crc, uint8_t __data)
{
    uint8_t __i, __pattern;
    __asm__ __volatile__ (
        "    eor    %0, %4" "\n\t"
        "    ldi    %1, 8" "\n\t"
        "    ldi    %2, 0x8C" "\n\t"
        "1:    bst    %0, 0" "\n\t"
        "    lsr    %0" "\n\t"
        "    brtc    2f" "\n\t"
        "    eor    %0, %2" "\n\t"
        "2:    dec    %1" "\n\t"
        "    brne    1b" "\n\t"
        : "=r" (__crc), "=d" (__i), "=d" (__pattern)
        : "0" (__crc), "r" (__data));
    return __crc;
}

И я так думаю, что эта функция будет работать быстрее приведенных выше.

Реализация функции взята из заголовочного файла "crc16.h" компилятора WinAVR.

А принцип простой: не изобретай велосипед. Лучше направить свои усилия на что то новое, чем пытаться заново писать стандартные функции, реализованные в библиотеках идущих вместе с компилятором.

Думать не нужно, надо пробовать (С).
Выполните Ваш код для 7 байтов, а потом внимательно перечитайте весь топик.

очень повеселил этот код:

Код

        MOVW    R31:R30, R17:R16
        LD    R22, Z+
        MOVW    R17:R16, R31:R30

и так 7 раз подряд

Хорошо поможет

Код

__z unsigned char crc8_2(unsigned char *buff,unsigned char num)

Вот это ОЧЕНЬ ценный совет

А циклы ОЧЕНЬ желательно делать

Код

do{}while(--var);

это помогает почти всем компиляторам и процессорам, обычно архитектура процессора позволяет изготовить нечто такое:

Код

DEC var
JUMP_IF_NZ label

Ну с этим никто и не спорит, только это уже получается не "оптимизирующий" компилятор,
а "оптимизируемый пользователем" компилятор.

[Rst7]

Ну с этим никто и не спорит, только это уже получается не "оптимизирующий" компилятор,
а "оптимизируемый пользователем" компилятор.

А вдруг завтра прийдется что-то написать для другого проца с совсем другим компилятором? А? Это в крови должно быть О чем многие тут и толкуют... Почитайте темы про "идеальные компиляторы"...

PS Кстати, IAR 4.40 для ARM такие циклы for переделывает в do{}while как 2 пальца... А вот для AVR видно старый оптимизатор внутри, хоть и 4.20... Переделка эта ведь перед code-генератором происходит, так что вполне мог бы и на AVR делать такое...

Сообщение отредактировал Rst7 - Aug 25 2006, 08:43

[_Bill]

Человек явно ищет идеальный компилятор, а их, как известно, в природе не бывает.

Лучший компилятор это человек.
на ASM у меня получилось 530 тактов:

Код

crc8:;Input: X - buffer; r17 - number of bytes    
;Output: r16 = CRC

    ldi    r16,0;CRC
    ldi    r20,0x8c
crc8_1:
    ld    r18,X+
    ldi    r19,8
crc8_2:
    lsr    r16
    brbc    0,crc8_3
    eor    r16,r20
crc8_3:
    sbrc    r18,0
    eor    r16,r20
    lsr    r18
crc8_4:
    dec    r19
    brne    crc8_2
    dec    r17
    brne    crc8_1

    ret

НО, надо отдать должное WinAVR(gcc)

ИТОГО:

Код

                    CRC8_1    CRC8_2
WinAVR(-o1)        620           556
WinAVR(-o2)        620           556
WinAVR(-o3)        606           544

IAR                986           774

ASM                       530

У WinAVR(-o3) удалось украсть всего 14 тактов, то есть по 2 такта на основной цикл.
Приятно удививший результат

А с IAR просто какая-то лабудень, возможно Вы vet там чего-то не то указали при
оптимизации?

Вся проблема в том, что компилятор использует определенные соглашения по передаче параметров и использованию регистров. Ваша функция под соглашения, принятые, например, в IAR, не попадает. Для стыковки с Си-шными функциями ее потребуется изменить с принятыми в компиляторе соглашениями. А это приведет к увеличению и размера кода, и увеличением времени его выполнения.

Сообщение отредактировал _Bill - Aug 25 2006, 11:33

[singlskv]

Человек явно ищет идеальный компилятор, а их, как известно, в природе не бывает.

Лучший компилятор это человек.
на ASM у меня получилось 530 тактов:

Код

crc8:;Input: X - buffer; r17 - number of bytes    
;Output: r16 = CRC

    ldi    r16,0;CRC
    ldi    r20,0x8c
crc8_1:
    ld    r18,X+
    ldi    r19,8
crc8_2:
    lsr    r16
    brbc    0,crc8_3
    eor    r16,r20
crc8_3:
    sbrc    r18,0
    eor    r16,r20
    lsr    r18
crc8_4:
    dec    r19
    brne    crc8_2
    dec    r17
    brne    crc8_1

    ret

НО, надо отдать должное WinAVR(gcc)

ИТОГО:

Код

                    CRC8_1    CRC8_2
WinAVR(-o1)        620           556
WinAVR(-o2)        620           556
WinAVR(-o3)        606           544

IAR                986           774

ASM                       530

У WinAVR(-o3) удалось украсть всего 14 тактов, то есть по 2 такта на основной цикл.
Приятно удививший результат

А с IAR просто какая-то лабудень, возможно Вы vet там чего-то не то указали при
оптимизации?

Вся проблема в том, что компилятор использует определенные соглашения по передаче параметров и использованию регистров. Ваша функция под соглашения, принятые, например, в IAR, не попадает. Для стыковки с Си-шными функциями ее потребуется изменить с принятыми в компиляторе соглашениями. А это приведет к увеличению и размера кода, и увеличением времени его выполнения.

Человек явно ищет идеальный компилятор, а их, как известно, в природе не бывает.

Лучший компилятор это человек.
на ASM у меня получилось 530 тактов:

Код

crc8:;Input: X - buffer; r17 - number of bytes    
;Output: r16 = CRC

    ldi    r16,0;CRC
    ldi    r20,0x8c
crc8_1:
    ld    r18,X+
    ldi    r19,8
crc8_2:
    lsr    r16
    brbc    0,crc8_3
    eor    r16,r20
crc8_3:
    sbrc    r18,0
    eor    r16,r20
    lsr    r18
crc8_4:
    dec    r19
    brne    crc8_2
    dec    r17
    brne    crc8_1

    ret

НО, надо отдать должное WinAVR(gcc)

ИТОГО:

Код

                    CRC8_1    CRC8_2
WinAVR(-o1)        620           556
WinAVR(-o2)        620           556
WinAVR(-o3)        606           544

IAR                986           774

ASM                       530

У WinAVR(-o3) удалось украсть всего 14 тактов, то есть по 2 такта на основной цикл.
Приятно удививший результат

А с IAR просто какая-то лабудень, возможно Вы vet там чего-то не то указали при
оптимизации?

Вся проблема в том, что компилятор использует определенные соглашения по передаче параметров и использованию регистров. Ваша функция под соглашения, принятые, например, в IAR, не попадает. Для стыковки с Си-шными функциями ее потребуется изменить с принятыми в компиляторе соглашениями. А это приведет к увеличению и размера кода, и увеличением времени его выполнения.

такты я считал по возможности честно, т.е. не учитывая такты потраченные на передачу
параметров.
А мой ASM код можно легко переписать под нужные регистры.
Да и разница в тактах что-то великовата, что бы ее объяснять только передачей
параметров.

Сообщение отредактировал singlskv - Aug 25 2006, 11:39

[_Bill]

такты я считал по возможности честно, т.е. не учитывая такты потраченные на передачу
параметров.
А мой ASM код можно легко переписать под нужные регистры.

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

[singlskv]

такты я считал по возможности честно, т.е. не учитывая такты потраченные на передачу
параметров.
А мой ASM код можно легко переписать под нужные регистры.

В свое время я написал небольшой опус на эту тему. К сожалению, он и сейчас далек от завершения.

Несколько месяцев назад прочитал Ваш опус, очень понравилось
Так что Вас можно считать идейным вдохновителем данного топика

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

Вот код для IAR (если я ничего не напутал):

Код

crc8iar:            ;Input: r17:r16 buffer; r18 - number of bytes    
                    ;Output: r16 = CRC

        movw    r31:r30,r17:r16
        ldi        r16,0            ;CRC
        ldi        r19,0x8c
crc8iar_1:
        ld        r20,Z+
        ldi        r21,8
crc8iar_2:
        lsr        r16
        brbc    0,crc8iar_3
        eor        r16,r19
crc8iar_3:
        sbrc    r20,0
        eor        r16,r19
        lsr        r20
crc8iar_4:
        dec        r21
        brne    crc8iar_2
        dec        r18
        brne    crc8iar_1

        ret

Добавилась всего одна инструкция:

Код

        movw    r31:r30,r17:r16

[_Bill]

Вот код для IAR (если я ничего не напутал):

Код

crc8iar:;Input: r17:r16 buffer; r18 - number of bytes    
        ;Output: r16 = CRC

        movw    r31:r30,r17:r16
        ldi        r16,0;CRC
        ldi        r19,0x8c
crc8iar_1:
        ld        r20,Z+
        ldi        r21,8
crc8iar_2:
        lsr        r16
        brbc    0,crc8iar_3
        eor        r16,r19
crc8iar_3:
        sbrc    r20,0
        eor        r16,r19
        lsr        r20
crc8iar_4:
        dec        r21
        brne    crc8iar_2
        dec        r18
        brne    crc8iar_1

        ret

Добавилась всего одна инструкция:

Код

        movw    r31:r30,r17:r16

Вроде все правильно. Только я думаю, что если Вы переведете ваш код на Си, то компилятор сделает код, аналогичный вашему. Лично я добавил бы еще одну переменную - указатель:

Код

#define BIT_0   (1<<0)
unsigned char crc8iar(char *buffer, char nbytes)
    {
    char   *bp = buffer;
    char   crc = 0, tmp, x8C = 0x8C;
    char   i;

    do    {
         tmp = *bp++;
         i     = 8;
         do   {
            if ((crc >>= 1) & BIT_0)
                crc ^= x8C;
            if (tmp & BIT_0)
                crc ^= x8C;
            tmp >>= 1;
            }
        while (--i);
        }
    while (--nbytes);
    return crc;
    }

Вроде так, если я нигде не ошибся.

Сообщение отредактировал _Bill - Aug 25 2006, 13:22

[_Bill]

Вот код для IAR (если я ничего не напутал):

Код

crc8iar:;Input: r17:r16 buffer; r18 - number of bytes    
    ;Output: r16 = CRC

        movw    r31:r30,r17:r16
        ldi        r16,0;CRC
        ldi        r19,0x8c
crc8iar_1:
        ld        r20,Z+
        ldi        r21,8
crc8iar_2:
        lsr        r16
        brbc    0,crc8iar_3
        eor        r16,r19
crc8iar_3:
        sbrc    r20,0
        eor        r16,r19
        lsr        r20
crc8iar_4:
        dec        r21
        brne    crc8iar_2
        dec        r18
        brne    crc8iar_1

        ret

Добавилась всего одна инструкция:

Код

        movw    r31:r30,r17:r16

Вот результат трансляции. Можете сравнить.

Код

     70          #define BIT_0   (1<<0)

   \                                 In segment CODE, align 2, keep-with-next
     71          unsigned char crc8iar(char *buffer, char nbytes)
   \                     crc8iar:
     72              {
     73              char   *bp = buffer;
   \   00000000   01F8               MOVW    R31:R30, R17:R16
     74              char   crc = 0, tmp, x8C = 0x8C;
   \   00000002   E000               LDI     R16, 0
     75              char   i;
     76          
     77              do    {
     78                   tmp = *bp++;
   \                     ??crc8iar_0:
   \   00000004   9141               LD      R20, Z+
     79                   i     = 8;
   \   00000006   E018               LDI     R17, 8
     80                   do   {
     81                      if ((crc >>= 1) & BIT_0)
   \                     ??crc8iar_1:
   \   00000008   9506               LSR     R16
   \   0000000A   FB00               BST     R16, 0
   \   0000000C   F416               BRTC    ??crc8iar_2
     82                          crc ^= x8C;
   \   0000000E   E83C               LDI     R19, 140
   \   00000010   2703               EOR     R16, R19
     83                      if (tmp & BIT_0)
   \                     ??crc8iar_2:
   \   00000012   FB40               BST     R20, 0
   \   00000014   F416               BRTC    ??crc8iar_3
     84                          crc ^= x8C;
   \   00000016   E83C               LDI     R19, 140
   \   00000018   2703               EOR     R16, R19
     85                      tmp >>= 1;
   \                     ??crc8iar_3:
   \   0000001A   9546               LSR     R20
     86                      }
     87                  while (--i);
   \   0000001C   951A               DEC     R17
   \   0000001E   F7A1               BRNE    ??crc8iar_1
     88                  }
     89              while (--nbytes);
   \   00000020   952A               DEC     R18
   \   00000022   F781               BRNE    ??crc8iar_0
     90              return crc;
   \   00000024   9508               RET
     91              }

[singlskv]

Вот результат трансляции. Можете сравнить.

Код

     70          #define BIT_0   (1<<0)

   \                                 In segment CODE, align 2, keep-with-next
     71          unsigned char crc8iar(char *buffer, char nbytes)
   \                     crc8iar:
     72              {
     73              char   *bp = buffer;
   \   00000000   01F8               MOVW    R31:R30, R17:R16
     74              char   crc = 0, tmp, x8C = 0x8C;
   \   00000002   E000               LDI     R16, 0
     75              char   i;
     76          
     77              do    {
     78                   tmp = *bp++;
   \                     ??crc8iar_0:
   \   00000004   9141               LD      R20, Z+
     79                   i     = 8;
   \   00000006   E018               LDI     R17, 8
     80                   do   {
     81                      if ((crc >>= 1) & BIT_0)
   \                     ??crc8iar_1:
   \   00000008   9506               LSR     R16
   \   0000000A   FB00               BST     R16, 0
   \   0000000C   F416               BRTC    ??crc8iar_2
     82                          crc ^= x8C;
   \   0000000E   E83C               LDI     R19, 140
   \   00000010   2703               EOR     R16, R19
     83                      if (tmp & BIT_0)
   \                     ??crc8iar_2:
   \   00000012   FB40               BST     R20, 0
   \   00000014   F416               BRTC    ??crc8iar_3
     84                          crc ^= x8C;
   \   00000016   E83C               LDI     R19, 140
   \   00000018   2703               EOR     R16, R19
     85                      tmp >>= 1;
   \                     ??crc8iar_3:
   \   0000001A   9546               LSR     R20
     86                      }
     87                  while (--i);
   \   0000001C   951A               DEC     R17
   \   0000001E   F7A1               BRNE    ??crc8iar_1
     88                  }
     89              while (--nbytes);
   \   00000020   952A               DEC     R18
   \   00000022   F781               BRNE    ??crc8iar_0
     90              return crc;
   \   00000024   9508               RET
     91              }

696 тактов однако ???

Код

   \   0000000E   E83C               LDI     R19, 140
   \   00000010   2703               EOR     R16, R19
     83                      if (tmp & BIT_0)
   \                     ??crc8iar_2:
   \   00000012   FB40               BST     R20, 0
   \   00000014   F416               BRTC    ??crc8iar_3
     84                          crc ^= x8C;
   \   00000016   E83C               LDI     R19, 140

А не слишком ли мы часто загружаем константу 140 (0x8c).

[µµC]

Приятный алгоритм, возьму на вооружение. 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;
}

[singlskv]

Приятный алгоритм, возьму на вооружение. 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;
}

а листинг можно в студию ? (ну не стоит у меня IAR)

Приятный алгоритм, возьму на вооружение. 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;
}

а листинг можно в студию ? (ну не стоит у меня IAR)

[µµC]

а листинг можно в студию ? (ну не стоит у меня IAR)

Код

        NAME crc8

        RSEG CSTACK:DATA:NOROOT(0)
        RSEG RSTACK:DATA:NOROOT(0)

        EXTERN ?need_segment_init

        PUBWEAK `?<Segment init: TINY_I>`
        PUBWEAK `?<Segment init: TINY_Z>`
        PUBWEAK __?EEARL
        PUBWEAK __?EECR
        PUBWEAK __?EEDR
        PUBLIC code
        PUBLIC crc8_3
        PUBLIC main
        PUBLIC result

// C:\1z\CRC8\crc8.c
//    1 #define U8 unsigned char
//    2

        RSEG TINY_I:DATA:NOROOT(0)
        REQUIRE `?<Segment init: TINY_I>`
//    3 U8 code[8] = {0x01, 0xd0, 0x5e, 0x3c, 0x0d, 0x00, 0x00, 0x84};
code:
        DS 8
        REQUIRE `?<Initializer for code>`
//    4 /*

//  100 */

        RSEG CODE:CODE:NOROOT(1)
//  101 U8 crc8_3(U8 *buff, U8 num)
crc8_3:
//  102 {
//  103   U8 i, crc = 0;
        LDI    R18, 0
//  104  
//  105   do {
//  106     crc ^= *buff++;
??crc8_3_0:
        MOV    R30, R16
        LD    R19, Z+
        MOV    R16, R30
        EOR    R18, R19
//  107     i   = 8;
        LDI    R19, 8
//  108     do {  
//  109       if (crc & 0x01) {
??crc8_3_1:
        BST    R18, 0
        LSR    R18
        BRTC    ??crc8_3_2
//  110         crc >>= 1;
//  111         crc ^= 0x8C;
        MOV    R20, R18
        LDI    R18, 140
        EOR    R18, R20
//  112       } else {
//  113         crc >>= 1;
//  114       }
//  115     } while (--i);  
??crc8_3_2:
        DEC    R19
        BRNE    ??crc8_3_1
//  116   } while (--num);
        DEC    R17
        BRNE    ??crc8_3_0
//  117   return crc;
        MOV    R16, R18
        RET
//  118 }
//  119

        RSEG TINY_Z:DATA:NOROOT(0)
        REQUIRE `?<Segment init: TINY_Z>`
//  120 volatile U8 result[4];
result:
        DS 4
//  121

        RSEG CODE:CODE:NOROOT(1)
//  122 void main(void)
main:
??main_0:
//  123 {
//  124   while (1) {
//  125     result[0] = 0;
        LDI    R16, 0
        LDI    R30, result
        ST    Z, R16
//  126  /*  
    
//  147  */  
//  148    
//  149 //result[0] = crc8_2(code, 7);
//  150     result[1] = crc8_3(code, 7);
        LDI    R17, 7
        LDI    R16, code
        RCALL    crc8_3
        LDI    R30, result
        STD    Z+1, R16
//  151 //    result[2] = crc8_2(code, 7);
//  152     result[3] = crc8_3(code, 7);
        LDI    R17, 7
        LDI    R16, code
        RCALL    crc8_3
        LDI    R30, result
        STD    Z+3, R16
        RJMP    ??main_0
//  153    
//  154   }
//  155 }

        ASEGN ABSOLUTE:DATA:NOROOT,01cH
__?EECR:

        ASEGN ABSOLUTE:DATA:NOROOT,01dH
__?EEDR:

        ASEGN ABSOLUTE:DATA:NOROOT,01eH
__?EEARL:

        RSEG TINY_ID:CODE:NOROOT(0)
`?<Initializer for code>`:
        DB 1, 208, 94, 60, 13, 0, 0, 132

        RSEG INITTAB:CODE:NOROOT(0)
`?<Segment init: TINY_I>`:
        DB    SFE(TINY_I) - SFB(TINY_I)
        DB    SFB(TINY_I)
        DW    SFB(TINY_ID)
        REQUIRE ?need_segment_init

        RSEG INITTAB:CODE:NOROOT(0)
`?<Segment init: TINY_Z>`:
        DB    SFE(TINY_Z) - SFB(TINY_Z)
        DB    SFB(TINY_Z)
        DW    0
        REQUIRE ?need_segment_init

        END
//  156
//  157 //IAR, opt = max speed, остальные опции выкл.

[singlskv]

Приятный алгоритм, возьму на вооружение. 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;
}

Вот, ЭТО уже по настоящему КРУТОЙ алгоритм ,
НО, если уже пошла такая пьянка, то ВОТ:

Код

crc8new:            ;Input: r17:r16 buffer; r18 - number of bytes    
                    ;Output: r16 = CRC

        movw    r31:r30,r17:r16

    ldi    r16,0x00
    ldi    r19,0x8c
crc8new_1:
    ld        r17,Z+
    eor        r16,r17
    ldi        r17,0x08
    rjmp    crc8new_3
crc8new_2:
    lsr        r16
    eor        r16,r19
    dec        r17
    breq    crc8new_4
crc8new_3:
    sbrc    r16,0
    rjmp    crc8new_2
    lsr        r16
    dec        r17
    brne    crc8new_3
crc8new_4:
    dec        r18
    brne    crc8new_1

Всего 427 тактов.

[Rst7]

Чето слабовато:

Код

__z char crc8_3(char *buff, char num, char poly)
{
  char i, crc = 0;
  do
  {
    crc ^= *buff++;
    i   = 8;
    do
    {
      crc >>=1;
      if (SREG_Bit0) crc^=poly;
    }
    while (--i);
  }
  while (--num);
  return crc;
}

__z char crc8(char *buff, char num)
{
  return crc8_3(buff, num, 0x8C);
}

Зовем конечно crc8

Код

   \                                 In segment CODE, align 2, keep-with-next
     58          __z char crc8_3(char *buff, char num, char poly)
   \                     crc8_3:
     59          {
     60            char i, crc = 0;
   \   00000000   E030               LDI     R19, 0
     61            do
     62            {
     63              crc ^= *buff++;
   \                     ??crc8_3_0:
   \   00000002   9121               LD      R18, Z+
   \   00000004   2732               EOR     R19, R18
     64              i   = 8;
   \   00000006   E028               LDI     R18, 8
     65              do
     66              {
     67                crc >>=1;
   \                     ??crc8_3_1:
   \   00000008   9536               LSR     R19
     68                if (SREG_Bit0) crc^=poly;
   \   0000000A   F408               BRBC    0, ??crc8_3_2
   \   0000000C   2731               EOR     R19, R17
     69              }
     70              while (--i);
   \                     ??crc8_3_2:
   \   0000000E   952A               DEC     R18
   \   00000010   F7D9               BRNE    ??crc8_3_1
     71            }
     72            while (--num);
   \   00000012   950A               DEC     R16
   \   00000014   F7B1               BRNE    ??crc8_3_0
     73            return crc;
   \   00000016   2F03               MOV     R16, R19
   \   00000018   9508               RET
     74          }
     75          

   \                                 In segment CODE, align 2, keep-with-next
     76          __z char crc8(char *buff, char num)
   \                     crc8:
     77          {
     78            return crc8_3(buff, num, 0x8C);
   \   00000000   E81C               LDI     R17, 140
   \   00000002   ....               RJMP    crc8_3
     79          }

[singlskv]

Чето слабовато:

НО, если уже пошла такая пьянка, то ВОТ:

Код

crc8new:           ;Input: r17:r16 buffer; r18 - number of bytes    
                   ;Output: r16 = CRC

        movw    r31:r30,r17:r16

    ldi    r16,0x00
    ldi    r19,0x8c
crc8new_1:
    ld        r17,Z+
    eor        r16,r17
    ldi        r17,0x08
    rjmp    crc8new_3
crc8new_2:
    lsr        r16
    eor        r16,r19
    dec        r17
    breq    crc8new_4
crc8new_3:
    sbrc    r16,0
    rjmp    crc8new_2
    lsr        r16
    dec        r17
    brne    crc8new_3
crc8new_4:
    dec        r18
    brne    crc8new_1

Всего 427 тактов.

Дык это Вообще не мой код, это код сгенерированный WinAVR(-o3) из:

Код

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;
}

алгоритма предложенного µµC и просто тупо переведенный мною для IAR.
Свой код не готов был уже сгенерить :cheers для данного алгоритма.

Код

__z char crc8_3(char *buff, char num, char poly)
{
  char i, crc = 0;
  do
  {
    crc ^= *buff++;
    i   = 8;
    do
    {
      crc >>=1;
      if (SREG_Bit0) crc^=poly;
    }
    while (--i);
  }
  while (--num);
  return crc;
}

__z char crc8(char *buff, char num)
{
  return crc8_3(buff, num, 0x8C);
}

Вот это мне очень понравилось , незнал что так можно писать:

Код

      crc >>=1;
      if (SREG_Bit0) crc^=poly;

КРУТО!!!
Но, это уже какой-то асемблерный код
Хотя так и не понял зачем там лишняя функция:

Код

__z char crc8(char *buff, char num)
{
  return crc8_3(buff, num, 0x8C);
}

типа для общности???

ИТОГО: (типа подводим итоги): (как автор данного топика кажись мне это можно )
1. компиляторам нужно подсказывать как они должны компилировать.
2. алгоритм имеет значительно большее влияние на производительность
чем просто тупое улучшение неудачного алгоритма.
3. учим матчасть:

Код

__z

Код

      crc >>=1;
      if (SREG_Bit0) crc^=poly;

ИТОГО N 2:

µµC за оригинальный алгоритм.
Rst7 за "__z".
Rst7 за очень грамонтную реализацию предложенного алгоритма :

Код

__z char crc8_3(char *buff, char num, char poly)
{
  char i, crc = 0;
  do
  {
    crc ^= *buff++;
    i   = 8;
    do
    {
      crc >>=1;
      if (SREG_Bit0) crc^=poly;
    }
    while (--i);
  }
  while (--num);
  return crc;
}

__z char crc8(char *buff, char num)
{
  return crc8_3(buff, num, 0x8C);
}

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

[Rst7]

Хотя так и не понял зачем там лишняя функция:

Код

__z char crc8(char *buff, char num)
{
  return crc8_3(buff, num, 0x8C);
}

типа для общности???

Нет, тут хитрость, без этого IAR психует и грузит 0x8C непосредственно перед выполнением xor, т.е. каждый раз в цикле, итого +1*8*sizeof по тактам. Чето там у него не срослось с отделением инвариантного кода. А так лечим, заставляем его принципиально xor с переменной делать. Так что это тоже шаманство

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

Лишь бы на здоровье

[Rst7]

В досыл...

Вот это мне очень понравилось , незнал что так можно писать:

Код

      crc >>=1;
      if (SREG_Bit0) crc^=poly;

КРУТО!!!
Но, это уже какой-то асемблерный код

Ну с этим надо поаккуратнее, а то в следующий раз может переоптимизировать нафиг все, например местами поменять сдвиг и проверку. А вообще-то эта идея родилась при реализации TCP/IP стека, там надо считать контрольные суммы с учетом переноса при прибавлении к 16-битному инту, его надо добавлять к сумме. А код, как вы понимаете, все время кривой. В результате родилось такое:

Код

unsigned int rxcrc; //Контрольная сумма в принимаемом пакете

#pragma optimize=no_inline
void subrxcrc(unsigned int i)
{
i=rxcrc-i;
if (_CARRY) i--;
rxcrc=i;
}

Быстро и качественно:

Код

     98          #pragma optimize=no_inline

   \                                 In segment CODE, align 2, keep-with-next
     99          void subrxcrc(unsigned int i)
   \                     subrxcrc:
    100          {
   \   00000000                      REQUIRE __RSTACK_in_external_ram
    101           i=rxcrc-i;
   \   00000000   ....               LDI     R30, LOW(rxcrc)
   \   00000002   ....               LDI     R31, (rxcrc) >> 8
   \   00000004                      REQUIRE ?Subroutine0
   \   00000004                     ;               // Fall through to label ?Subroutine0
    102           if (_CARRY) i--;
    103           rxcrc=i;
    104          }

   \                                 In segment CODE, align 2, keep-with-next
   \                     ?Subroutine0:
   \   00000000   8120               LD      R18, Z
   \   00000002   8131               LDD     R19, Z+1
   \   00000004   1B20               SUB     R18, R16
   \   00000006   0B31               SBC     R19, R17
   \   00000008   0189               MOVW    R17:R16, R19:R18
   \   0000000A   F410               BRBC    0, ??Subroutine0_0
   \   0000000C   5001               SUBI    R16, 1
   \   0000000E   4010               SBCI    R17, 0
   \                     ??Subroutine0_0:
   \   00000010   8300               ST      Z, R16
   \   00000012   8311               STD     Z+1, R17
   \   00000014   9508               RET

Тоже гон, конечно (MOVW там совсем лишний), но намного лучше других способов...

[µµC]

А что такое "__z"? Что нужно сделать чтоб этим пользоваться, где почитать? WinAVR 2006421 пишет: * crc8.c, line 104: error: syntax error before "unsigned"
В описании упоминаний не нашел.

[Rst7]

А что такое "__z"? Что нужно сделать чтоб этим пользоваться, где почитать? WinAVR 2006421 пишет: * crc8.c, line 104: error: syntax error before "unsigned"
В описании упоминаний не нашел.

Это IAR-овская фича, в GNU такого нет. В IAR-е этот модификатор говорит, что первый указатель будет передан через регистр Z. Еще есть модификаторы __x, __z_x, __x_z, соответственно использование X для передачи первого указателя, использование Z для первого, X для второго и наоборот.

[µµC]

Понял. спасибо. В IAR этим пользуюсь. Просто мне почему-то показалось, что singlskv тоже может, а IAR у него нет.