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

[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