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

[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 у него нет.