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

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

[singlskv]

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

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

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

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

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

IAR.

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

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

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

[µµ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

[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]

Если несложно, то просимулируйте для 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" все равно быстрее).

[µµ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