[sf9 0]

Всем доброе время суток!

Прошу помочь мне разобраться в С коде.Сам только недавно начал осваивать.

нужно реализовать CRC16 для ModBus.

Я знаю,что есть куча готовых реализаций.Простым(последовательным) и табличным способом.

Но хочу реализовать сам.

У меня проблема в том,что для вычисления CRC нужно смотреть на состояние младшого бита. Если "1" - то выполнять XOR,если нет,то крутить дальше.

 

Вот мой код:

 

int crc16 (unsigned char a) // a - 8-bit data for calculation CRC

{

unsigned int reg, tmp;

int i;

 

reg = 0xFFFF; // step1: initial loading of 16-bit register

reg ^= (unsigned int)a; // step2: a XOR reg

 

for(i = 0;i<8;i++) //step3: 8-iteration to calculate CRC

{

reg >>= 1;

tmp = reg;

tmp <<= 15;

if(tmp == 0x8000) reg ^= 0xA001; // checking: if LSB = "1" reg=reg^0xA001

}

return reg;

}

 

проверку я выолняю поразрядным сдвигом 16-битного reg влево, и, если там "1",то xor.

 

ниже преведена другая реализация CRC16 и она работет корректно!!!!

 

int crc16 (unsigned char a)

{

unsigned int reg;

unsigned char i, tmp;

 

reg = 0xFFFF;

reg ^= (unsigned int)a;

for(i = 0;i<8;i++)

{

tmp = (unsigned char)(reg&0x0001);

reg >>= 1;

if(tmp) reg ^= 0xA001;

}

return reg;

}

 

Поясните,что не так в первой реализачии. :smile3046:

[Sat360 0]

В первой реализации регистр сдвигается ДО анализа бита. Следовательно, младший бит теряется.

[Сергей Борщ 123]

В работающей программе сначала запоминается младший бит, потом делается сдвиг вправо (при этом в сдвинутом числе этот бит уже потерян). Вы же сначала сдвигаете вправо, потом делаете проверку. Т.е. проверяете не младший, а следующий бит. Ваш сдвиг влево на 15 разрядов не нужен:

    tmp <<= 15;
    if(tmp == 0x8000)
эквивалентно 
    if(tmp & 1)

Этот код более красиво можно записать так:

int crc16 (uinsigned int crc, unsigned char a)         // a - 8-bit data for calculation CRC
{
            int i;
    
    crc ^= (unsigned int)a;    // step2: a XOR reg
    
    for(i = 0;i<8;i++)           //step3: 8-iteration to calculate CRC   
    {
        if(crc & 1)
        {
            crc >>= 1; reg ^= 0xA001;
        }
        else
        {
            crc >>= 1;
        }
    }
    return crc;
}

Обратите внимание, что 0xFFFF заносится в crc один раз перед обсчетом всего массива.

 

P.S. В форме ввода сообщения есть кнопочка для оформления кода. Она обозначена символом "#". Используйте ее, пожалуйста, при публикации кода. Иначе портится форматирование и ваш исходник становится трудночитаемым.

[sf9 0]

СПАСИБО ОГРОМНОЕ!!! :a14:

Я понял,просто дело в том,что я не соблюдал порядок выполнения кода.

Свой корявый вариант я подправил:

int crc16 (unsigned char a)
{
    unsigned int reg,tmp;
    unsigned int i;
    
    reg = 0xFFFF;                 
    reg ^= (unsigned int)a;    
    
    for(i = 0;i<8;i++) 
    {
        tmp = reg;
        reg >>= 1;        
        if((tmp <<=15)==0x8000) reg ^= 0xA001;
    }
    return reg;
}

 

А если с Вашими комментариями получилось расчудесно:

        if((tmp <<=15)==0x8000) reg ^= 0xA001;
меняем на
        if(tmp&1) reg ^= 0xA001;

 

И ещё хотел бы узнать,как можно напрямую обращаться к биту в байте на языке С?

??

Изменено 17 сентября, 2008 пользователем sf9

[Rst7 5]

А меня вот последнее время поперло по-другому CRC16 для модбаса считать. Оптимизированно под IAR AVR (чтобы все в регистрах было)

__z UREG CRC16stage2(UINT8 uchCRCLo, UINT8 uchCRCHi, UREG l, UREG write, UINT8 *puchMsg, UREG i64, UREG i128, UREG i1, UREG i192);

UREG CRC16(UINT8 *puchMsg, UREG usDataLen, UREG write )
{
  return CRC16stage2(0xFF,0xFF,usDataLen,write,puchMsg,64,128,1,192);
}

#pragma optimize=no_inline
__z UREG CRC16stage2(UINT8 uchCRCLo, UINT8 uchCRCHi, UREG l, UREG write, UINT8 *puchMsg, UREG i64, UREG i128, UREG i1, UREG i192)
{
  do
  {
    UINT8 parity;
    UINT16 tmp16;
    parity=(uchCRCLo ^= *puchMsg++);
    uchCRCLo=uchCRCHi;
    tmp16=__multiply_unsigned(parity,i64);
    uchCRCHi=tmp16>>8;
    uchCRCLo^=tmp16;
    tmp16=__multiply_unsigned(parity,i128);
    uchCRCHi^=tmp16>>8;
    uchCRCLo^=tmp16;
    parity^=__swap_nibbles(parity);
    parity^=parity>>1;
    if (!(parity & 4)) parity--;
    if (!(parity&1))
    {
      uchCRCLo^=i1;
      uchCRCHi^=i192;
    }
  }
  while(--l);
  if (write)
  {
    *puchMsg++=uchCRCLo;
    *puchMsg++=uchCRCHi;
  }
  else
  {
    UREG k;
    if ((k=*puchMsg++-uchCRCLo)) return k;
    return *puchMsg++-uchCRCHi;
  }
  return 0;  
}

 

и результат

        RSEG CODE:CODE:NOROOT(1)
//   74 UREG CRC16(UINT8 *puchMsg, UREG usDataLen, UREG write )
CRC16:
//   75 {
        MOVW    R31:R30, R17:R16
//   76   return CRC16stage2(0xFF,0xFF,usDataLen,write,puchMsg,64,128,1,192);
        LDI     R23, 192
        LDI     R22, 1
        LDI     R21, 128
        LDI     R20, 64
        LDI     R17, 255
        LDI     R16, 255
        REQUIRE CRC16stage2
       ;               // Fall through to label CRC16stage2
//   77 }
//   78 
//   79 #pragma optimize=no_inline

        RSEG CODE:CODE:NOROOT(1)
//   80 __z UREG CRC16stage2(UINT8 uchCRCLo, UINT8 uchCRCHi, UREG l, UREG write, UINT8 *puchMsg, UREG i64, UREG i128, UREG i1, UREG i192)
CRC16stage2:
//   81 {
        ST      -Y, R24
        MOV     R3, R16
        MOV     R2, R17
        MOV     R24, R22
//   82   do
//   83   {
//   84     UINT8 parity;
//   85     UINT16 tmp16;
//   86     parity=(uchCRCLo ^= *puchMsg++);
??CRC16stage2_0:
        LD      R16, Z+
        EOR     R3, R16
        MOV     R22, R3
//   87     uchCRCLo=uchCRCHi;
        MOV     R3, R2
//   88     tmp16=__multiply_unsigned(parity,i64);
        MUL     R22, R20
//   89     uchCRCHi=tmp16>>8;
        MOV     R2, R1
//   90     uchCRCLo^=tmp16;
        EOR     R3, R0
//   91     tmp16=__multiply_unsigned(parity,i128);
        MUL     R22, R21
//   92     uchCRCHi^=tmp16>>8;
        EOR     R2, R1
//   93     uchCRCLo^=tmp16;
        EOR     R3, R0
//   94     parity^=__swap_nibbles(parity);
        MOV     R16, R22
        SWAP    R16
        EOR     R22, R16
//   95     parity^=parity>>1;
        MOV     R16, R22
        LSR     R16
        EOR     R22, R16
//   96     if (!(parity & 4)) parity--;
        BST     R22, 2
        BRTS    ??CRC16stage2_1
        DEC     R22
//   97     if (!(parity&1))
??CRC16stage2_1:
        BST     R22, 0
        BRTS    ??CRC16stage2_2
//   98     {
//   99       uchCRCLo^=i1;
        EOR     R3, R24
//  100       uchCRCHi^=i192;
        EOR     R2, R23
//  101     }
//  102   }
//  103   while(--l);
??CRC16stage2_2:
        DEC     R18
        BRNE    ??CRC16stage2_0
//  104   if (write)
        TST     R19
        BREQ    ??CRC16stage2_3
//  105   {
//  106     *puchMsg++=uchCRCLo;
        ST      Z+, R3
//  107     *puchMsg++=uchCRCHi;
        ST      Z, R2
//  108   }
//  109   else
//  110   {
//  111     UREG k;
//  112     if ((k=*puchMsg++-uchCRCLo)) return k;
//  113     return *puchMsg++-uchCRCHi;
//  114   }
//  115   return 0;  
        LDI     R16, 0
        RJMP    ??CRC16stage2_4
??CRC16stage2_3:
        LD      R16, Z+
        SUB     R16, R3
        BRNE    ??CRC16stage2_4
        LD      R16, Z
        SUB     R16, R2
??CRC16stage2_4:
        LD      R24, Y+
        RET
//  116 }

 

Итого - 29 тактов на байт. И без всяких таблиц.

 

Кстати, вариант

__x UREG CRC16stage2(UINT8 uchCRCLo, UINT8 uchCRCHi, UREG l, UREG write, UINT8 *puchMsg, UREG i64, UREG i128, UREG i1, UREG i192);

__x UREG CRC16(UINT8 *puchMsg, UREG usDataLen, UREG write )
{
  return CRC16stage2(0xFF,0xFF,usDataLen,write,puchMsg,64,128,1,192);
}

#pragma optimize=no_inline
__x UREG CRC16stage2(UINT8 uchCRCLo, UINT8 uchCRCHi, UREG l, UREG write, UINT8 *puchMsg, UREG i64, UREG i128, UREG i1, UREG i192)
...

сохранит 1 байт CSTACK, но может ухудшить верхний код.

[sf9 0]

Кстати,в компиляторах и САПРах для МСs как можно подсчитать кол-во тактов,оптимизацию и пр.?

В частности,AVRstudio???????

Изменено 17 сентября, 2008 пользователем sf9

[Rst7 5]

Никак. Только ручками. Ну или в симуляторе выполнить код и посмотреть.

 

А вот "подсчитать оптимизацию" - это Вы что имели в виду?

[sf9 0]

Никак. Только ручками. Ну или в симуляторе выполнить код и посмотреть.

 

А вот "подсчитать оптимизацию" - это Вы что имели в виду?

 

Согласен,некорректно выразился.

Хотел спросить следующее:"Есть ли настройки в компиляторах или САПРах для МК,которые позволяют оптимизировать проект в той или иной области - памяти программ или данных?"

Или всё же только ручками?

:smile3046:

[Rst7 5]

Есть ли настройки в компиляторах или САПРах для МК,которые позволяют оптимизировать проект

 

Ну обычно говорят не САПР, а среда разработки. Но то не суть.

 

У всех вменяемых компиляторов есть возможность настройки уровня и типа оптимизации. Как для всего проекта, так и для отдельных функций (например в моем примере #pragma optimize=no_inline - это для того, чтобы функция никогда не включалась во внутрь другой).

 

Кроме того, зная особенности поведения компилятора, можно помочь ему руками - написав соответствующий код, но тут только опыт поможет ;)

[sf9 0]

:07:

Спасибо большое!

Побрёл я наращивать головные мышцы.И извилины развивать.

[ReAl 0]

А меня вот последнее время поперло по-другому CRC16 для модбаса считать. Оптимизированно под IAR AVR (чтобы все в регистрах было)

У avr-gcc в util/crc16.h есть под несколько разных полиномов такие быстрые алгоритмы в виде асм-вставок для добавления к crc одного байта, хорошо вставляются внутрь своего цикла.

А у альтеры апнота была на тему fast crc calculation, где разрисовано красиво откуда ноги растут у такой оптимизации и по той апноте можно сделать для любого полинома.

 

 

 

У avr-gcc в util/crc16.h есть под несколько разных полиномов такие быстрые алгоритмы в виде асм-вставок для добавления к crc одного байта, хорошо вставляются внутрь своего цикла.

Хм.. там сдвиги не умножением сделаны, а впрямую, но всё равно в зависимости от полинома уже находящийся в регистре байт добавляется к находящейся на регистрах CRC за 17..25 тактов в зависимости от полинома. В цикле будет плюс загрузка очередного байта и организация цикла, в итоге по времени выйдет на приблизительно то же, что и с умножением. Но будет работать и на мелких кристаллах.

[singlskv 0]

У avr-gcc в util/crc16.h есть под несколько разных полиномов такие быстрые алгоритмы в виде асм-вставок для добавления к crc одного байта, хорошо вставляются внутрь своего цикла.

Хм.. там сдвиги не умножением сделаны, а впрямую, но всё равно в зависимости от полинома уже находящийся в регистре байт добавляется к находящейся на регистрах CRC за 17..25 тактов в зависимости от полинома.

+1 Оптимальнее чем в avr-gcc для crc16 и не сделать, поэтому всегда пользуюсь встроенным...

[sf9 0]

По поводу crc16.h абсолютно согласен,вчера проверял,тестировал,всё работает быстрее,чем другие реализации. Ну и,естественно,удобно. ;)

[Rst7 5]

+1 Оптимальнее чем в avr-gcc для crc16 и не сделать

 

Не кажи "гоп" ;)

 

__z UREG CRC16stage2(UINT8 uchCRCLo, UINT8 uchCRCHi, UREG l, UREG write, UINT8 *puchMsg, UREG i128,UREG i1, UREG i192);

UREG CRC16(UINT8 *puchMsg, UREG usDataLen, UREG write )
{
  return CRC16stage2(0xFF,0xFF,usDataLen,write,puchMsg,128,1,192);
}

#pragma optimize=no_inline
__z UREG CRC16stage2(UINT8 uchCRCLo, UINT8 uchCRCHi, UREG l, UREG write, UINT8 *puchMsg, UREG i128, UREG i1, UREG i192)
{
  do
  {
    UINT8 parity;
    UINT16 tmp16;
    parity=*puchMsg++;
    parity^=uchCRCLo;
    uchCRCLo=uchCRCHi;
    tmp16=__multiply_unsigned(parity,i128);
    uchCRCHi=tmp16>>8;
    uchCRCLo^=tmp16;
    tmp16>>=1;
    uchCRCHi^=tmp16>>8;
    uchCRCLo^=tmp16;
    parity^=tmp16>>8;
    parity^=parity>>1;
    parity^=__swap_nibbles(parity);
    if (parity&1)
    {
      uchCRCLo^=i1;
      uchCRCHi^=i192;
    }
  }
  while(--l);
  if (write)
  {
    *puchMsg++=uchCRCLo;
    *puchMsg++=uchCRCHi;
  }
  else
  {
    UREG k;
    if ((k=*puchMsg++-uchCRCLo)) return k;
    return *puchMsg++-uchCRCHi;
  }
  return 0;  
}

 

        RSEG CODE:CODE:NOROOT(1)
//   74 UREG CRC16(UINT8 *puchMsg, UREG usDataLen, UREG write )
CRC16:
//   75 {
        MOVW    R31:R30, R17:R16
//   76   return CRC16stage2(0xFF,0xFF,usDataLen,write,puchMsg,128,1,192);
        LDI     R22, 192
        LDI     R21, 1
        LDI     R20, 128
        LDI     R17, 255
        LDI     R16, 255
        REQUIRE CRC16stage2
       ;               // Fall through to label CRC16stage2
//   77 }
//   78 
//   79 #pragma optimize=no_inline

        RSEG CODE:CODE:NOROOT(1)
//   80 __z UREG CRC16stage2(UINT8 uchCRCLo, UINT8 uchCRCHi, UREG l, UREG write, UINT8 *puchMsg, UREG i128, UREG i1, UREG i192)
CRC16stage2:
//   81 {
        MOV     R2, R16
        MOV     R23, R17
//   82   do
//   83   {
//   84     UINT8 parity;
//   85     UINT16 tmp16;
//   86     parity=*puchMsg++;
??CRC16stage2_0:
        LD      R3, Z+
//   87     parity^=uchCRCLo;
        EOR     R3, R2
//   88     uchCRCLo=uchCRCHi;
        MOV     R2, R23
//   89     tmp16=__multiply_unsigned(parity,i128);
        MUL     R3, R20
//   90     uchCRCHi=tmp16>>8;
        MOV     R23, R1
//   91     uchCRCLo^=tmp16;
        EOR     R2, R0
//   92     tmp16>>=1;
        LSR     R1
        ROR     R0
        EOR     R23, R1
//   93     uchCRCHi^=tmp16>>8;
//   94     uchCRCLo^=tmp16;
        EOR     R2, R0
//   95     parity^=tmp16>>8;
        EOR     R3, R1
//   96     parity^=parity>>1;
        MOV     R16, R3
        LSR     R16
        EOR     R3, R16
//   97     parity^=__swap_nibbles(parity);
        MOV     R16, R3
        SWAP    R16
        EOR     R3, R16
//   98     if (parity&1)
        BST     R3, 0
        BRTC    ??CRC16stage2_1
//   99     {
//  100       uchCRCLo^=i1;
        EOR     R2, R21
//  101       uchCRCHi^=i192;
        EOR     R23, R22
//  102     }
//  103   }
//  104   while(--l);
??CRC16stage2_1:
        DEC     R18
        BRNE    ??CRC16stage2_0
//  105   if (write)
        TST     R19
        BREQ    ??CRC16stage2_2
//  106   {
//  107     *puchMsg++=uchCRCLo;
        ST      Z+, R2
//  108     *puchMsg++=uchCRCHi;
        ST      Z, R23
//  109   }
//  110   else
//  111   {
//  112     UREG k;
//  113     if ((k=*puchMsg++-uchCRCLo)) return k;
//  114     return *puchMsg++-uchCRCHi;
//  115   }
//  116   return 0;  
        LDI     R16, 0
        RET
??CRC16stage2_2:
        LD      R16, Z+
        SUB     R16, R2
        BRNE    ??CRC16stage2_3
        LD      R16, Z
        SUB     R16, R23
??CRC16stage2_3:
        RET
//  117 }

 

20.5 тактов против 23 на собственно расчет следующего значения CRC16.

[singlskv 0]

Не кажи "гоп" ;)

Ok, согласен

умножение здесь рулит...

Только в любом случае в предыдущем варианте было хуже чем в winavr...

Ну и еще, этот вариант просто непременим в winavr, поэтому никогда и не задумывался

об улучшении с 23 тактов...

 

а в чистом асм возможно 1-2 такта можно было-бы еще выиграть, но нужно много думать...