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

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

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

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

[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