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

[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% быстрее.
Собственно вопрос: а есть ли компилятор который может скомпилировать
эти две(одинаковых!) функции в одинаковый(быстрый) код ?

[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 с переменной делать. Так что это тоже шаманство

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

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