[原创]快速CRC16算法，32字节查表法的改进优化版，速度提高60%（比512字节查表法还是慢些）

snoopyzz · 发表于 2010-8-5 09:46:50

先给出我早先参照网上CRC16查表法写的代码（速度慢呀~）
// crc16.h
#ifndef _H_CRC16
#define _H_CRC16

#include "main.h"

typedef struct
{
u16 Result;
} CRC16_T;
extern CRC16_T CRC16;

#define CRC16_Init() { CRC16.Result=0x00; }
extern void CRC16_Update(u8 data);
extern void CRC16_Calc(u8* p_buffer,u16 count);

#endif

// crc16.c
#include "crc16.h"

CRC16_T CRC16;

static const u16 table[]=
{
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,
0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,
};

#define crc (CRC16.Result)
void CRC16_Update(u8 data)
{
static u8 tmp;  // 对于cosmic for stm8，这里用静态变量能使运算快些，其它编译器也许可以用register来修饰提高速度
tmp = (u8)(crc>>8);
tmp ^= data;
tmp >>= 4;
crc <<= 4;
crc ^= table[tmp];
//
tmp = (u8)(crc>>8);
tmp >>=4;
tmp ^= data;
tmp &= 0x0f;
crc <<= 4;
crc ^= table[tmp];
}

void CRC16_Calc(u8* p_buffer,u16 count)
{
CRC16.Result = 0x0000; // 适需要更改为其它多项式

while(count)
{
      count--;
      CRC16_Update(*p_buffer++);
      // 适情况添加清看门狗
}
}

=========================================
以下是改进过的表格和CRC16_Update
#define table1_H(n) (u8)(0x02*(n))
#define table1_L(n) (u8)(0x10*(n))

static const u8 table2_H[]=
{
0x00, 0x10, 0x20, 0x30, 0x40, 0x50, 0x60, 0x70, 0x81, 0x91, 0xA1, 0xB1, 0xC1, 0xD1, 0xE1, 0xF1,
};

static const u8 table2_L[]=
{
0x00, 0x21, 0x42, 0x63, 0x84, 0xA5, 0xC6, 0xE7, 0x08, 0x29, 0x4A, 0x6B, 0x8C, 0xAD, 0xCE, 0xEF,
};

#define crc (CRC16.Result)
void CRC16_Update(u8 data)
{
static u8 tmp1,tmp2;  // 对于cosmic for stm8，这里用静态变量能使运算快些，其它编译器也许可以用register来修饰提高速度
tmp2 = (u8)(data^H8BIT(crc));
tmp1 = (u8)(tmp2>>4);
tmp2^= tmp1;
tmp2&= 0x0f;
//
PTR_BYTE(crc)[BYTE_H] = (u8)(table1_H(tmp1)^table2_H[tmp2]^L8BIT(crc));
PTR_BYTE(crc)[BYTE_L] = (u8)(table1_L(tmp1)^table2_L[tmp2]);
}

====================
以下是用到的定义

typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned long u32;

#define H8BIT(word) ( (u8)((word)>>8) )
#define L8BIT(word) ( (u8)((word)) )
#define PTR_BYTE(var)  ( (u8*)(&var) )

// stm8是大端模式，小端模式请把 0和 1对调
#define BYTE_H (0)
#define BYTE_L (1)

stm8s103 · 发表于 2010-8-5 10:07:28

mark,
顶

snoopyzz · 发表于 2010-8-5 10:12:41

原本查表法的原理就不讲述了，这里只说下优化的原理

设当前16位crc值为ABCD，待计算data值为XY（每个字母代表4bit数字）

第一次查表结果为EFGH，第二次查表结果为IJKL

则原算法等同如下描述如下

static const u16 table[]=
{
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,
0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,
};

void CRC16_Update(u8 data)
{
static u8 tmp;
tmp = (u8)(crc>>8);
tmp ^= data;
tmp >>= 4; // tmp = A^X
crc <<= 4; // crc = BCD0
crc ^= table[tmp]; // crc = BCD0^EFGH
//
tmp = (u8)(crc>>8);
tmp >>=4;
tmp ^= data;
tmp &= 0x0f;// tmp = B^E^Y
crc <<= 4; // crc = CD00^FGH0
crc ^= table[tmp]; // crc = CD00^FGH0^IJKL，这是最终需要的结果，以下改进中分高低计算，crc_H = CD^FG^IJ，crc_L = H0^KL
}

至此，思路就清晰了，我本意是为FGH0构造一个新表，
但构造完之后，发现了规律，新表的高低字节符合
#define table1_H(n) (u8)(0x02*(n))
#define table1_L(n) (u8)(0x10*(n))
所以省了这个表，而且我试下来这样计算比查表更快

A^X做为第一次查表下标好计算，但第二次查表下标B^E^Y中的E如果是查表移位得来就慢了，不难发现E==A^X的规律，
所以改进后的算法就简单了，把表格拆分成高位和低位两个表
static const u8 table2_H[]=
{
0x00, 0x10, 0x20, 0x30, 0x40, 0x50, 0x60, 0x70, 0x81, 0x91, 0xA1, 0xB1, 0xC1, 0xD1, 0xE1, 0xF1,
};

static const u8 table2_L[]=
{
0x00, 0x21, 0x42, 0x63, 0x84, 0xA5, 0xC6, 0xE7, 0x08, 0x29, 0x4A, 0x6B, 0x8C, 0xAD, 0xCE, 0xEF,
};

void CRC16_Update(u8 data)
{
static u8 tmp1,tmp2;
tmp2 = (u8)(data^H8BIT(crc));// data^crc_H
tmp1 = (u8)(tmp2>>4);//第一次查表用下标tmp1 = A^X
tmp2^= tmp1;
tmp2&= 0x0f; //第二次查表用下标tmp2 = (B^Y)^(A^X)
//
PTR_BYTE(crc)[BYTE_H] = (u8)(table1_H(tmp1)^table2_H[tmp2]^L8BIT(crc)); // crc_H = FG^IJ^CD
PTR_BYTE(crc)[BYTE_L] = (u8)(table1_L(tmp1)^table2_L[tmp2]); // crc_L = H0^KL
}

snoopyzz · 发表于 2010-8-5 10:31:03

2L有优化原理
果然，我发技术贴总是冷，等中午再来瞧瞧。。。

lrzxc · 发表于 2010-8-5 10:45:16

我先记号一下

dreampet · 发表于 2010-8-5 10:48:53

不错顶楼主

RENMA · 发表于 2010-8-5 10:52:57

楼主有测试结果吗？

定性，还要定量

有实际的测试数据说明问题吗

snoopyzz · 发表于 2010-8-5 10:59:52

回6L，我对比过用cosmic在stm8s中生成的汇编，代码的确精简了，60%的速度提高也不是空穴来风，是用软仿得到的结果。
具体数据，有兴趣的可以自己试嘛，不同编译器，不同优化程度，不同芯片和结果可能都不大相同，所以我也就没给出具体数据。

关于计算结果是否正确，我分别计算过
12字节，6732字节，8192字节，我项目中需要计算的数据，CRC16结果与原算法完全相同，证明我的优化无误

速度的提高主要在原算法两次左移4位crc上，生成的汇编看到是循环做的，效率当然就低了，新的算法完全避免了16位数移位的过程

Fire_cow · 发表于 2010-8-5 11:11:17

RENMA · 发表于 2010-8-5 11:16:08

回复【7楼】snoopyzz
回6l，我对比过用cosmic在stm8s中生成的汇编，代码的确精简了，60%的速度提高也不是空穴来风，是用软仿得到的结果。
具体数据，有兴趣的可以自己试嘛，不同编译器，不同优化程度，不同芯片和结果可能都不大相同，所以我也就没给出具体数据。
关于计算结果是否正确，我分别计算过
12字节，6732字节，8192字节，我项目中需要计算的数据，crc16结果与原算法完全相同，证明我的优化无误
速度的提高主要在原算法两次左移4位crc上，生成的汇编看到是循环做的，效率当然就低了，新的算法完全避免了16位数移位的过程

-----------------------------------------------------------------------

处理器做移位速度应该是非常快的吧，可以忽略了

snoopyzz · 发表于 2010-8-5 11:26:36

RENMA你看汇编就知道了，用循环移4次，又移4次，很担误事了，还多余

不看汇编凭想像，当然不知其中奥妙，事实就是快了60%，不可否认这点

cosmic for stm8编译后，新算法省了30bytes，

软件仿真cpu在4MHz时，计算6732字节，
原算法是166.6ms
优化算法耗时是69ms

512字节查表法，耗时是52.18ms

kanprin · 发表于 2010-8-5 11:34:04

顶你到钻研精神

snoopyzz · 发表于 2010-8-5 11:37:18

RENMA请看下10L
这里再附上汇编对比
===========================
优化前
6433                   ; 98 void CRC16_Update(u8 data)
6433                   ; 99 {
6435                   .text: section .text,new
6436  0000             _CRC16_Update:
6438    00000000    OFST: set 0
6441                   ; 101 tmp = (u8)(crc>>8);
6443  0000 450100         mov L7064_tmp,_CRC16
6444  0003 88             push a
6445                   ; 102 tmp ^= data;
6447  0004 b800       xor a,L7064_tmp
6448                   ; 103 tmp >>= 4;
6450  0006 4e             swap a
6451  0007 a40f       and a,#15
6452  0009 b700       ld L7064_tmp,a
6453                   ; 104 crc <<= 4;
6455  000b a604       ld a,#4
6456  000d             L6:
6457  000d 3802       sll _CRC16+1
6458  000f 3901       rlc _CRC16
6459  0011 4a             dec a
6460  0012 26f9       jrne L6
6461                   ; 105 crc ^= table[tmp];
6463  0014 b600       ld a,L7064_tmp
6464  0016 5f             clrw x
6465  0017 97             ld xl,a
6466  0018 58             sllw x
6467  0019 de0000         ldw x,(L5064_table,x)
6468  001c 01             rrwa x,a
6469  001d b802       xor a,_CRC16+1
6470  001f 01             rrwa x,a
6471  0020 b801       xor a,_CRC16
6472  0022 01             rrwa x,a
6473  0023 bf01       ldw _CRC16,x
6474                   ; 107 tmp = (u8)(crc>>8);
6476  0025 b601       ld a,_CRC16
6477                   ; 108 tmp >>=4;
6479  0027 4e             swap a
6480                   ; 109 tmp ^= data;
6482  0028 1801       xor a,(OFST+1,sp)
6483                   ; 110 tmp &= 0x0f;
6485  002a a40f       and a,#15
6486  002c b700       ld L7064_tmp,a
6487                   ; 111 crc <<= 4;
6489  002e a604       ld a,#4
6490  0030             L01:
6491  0030 3802       sll _CRC16+1
6492  0032 3901       rlc _CRC16
6493  0034 4a             dec a
6494  0035 26f9       jrne L01
6495                   ; 112 crc ^= table[tmp];
6497  0037 b600       ld a,L7064_tmp
6498  0039 5f             clrw x
6499  003a 97             ld xl,a
6500  003b 58             sllw x
6501  003c de0000         ldw x,(L5064_table,x)
6502  003f 01             rrwa x,a
6503  0040 b802       xor a,_CRC16+1
6504  0042 01             rrwa x,a
6505  0043 b801       xor a,_CRC16
6506  0045 01             rrwa x,a
6507  0046 bf01       ldw _CRC16,x
6508                   ; 113 }
6511  0048 84             pop a
6512  0049 81             ret
===========================
优化后
6462                   ; 105 void CRC16_Update(u8 data)
6462                   ; 106 {
6464                   .text: section .text,new
6465  0000             _CRC16_Update:
6469                   ; 108 tmp2 = (u8)(data^H8BIT(crc));
6471  0000 b802       xor a,_CRC16
6472  0002 b700       ld L3164_tmp2,a
6473                   ; 109 tmp1 = (u8)(tmp2>>4);
6475  0004 4e             swap a
6476  0005 a40f       and a,#15
6477  0007 b701       ld L1164_tmp1,a
6478                   ; 110 tmp2^= tmp1;
6480  0009 b800       xor a,L3164_tmp2
6481                   ; 111 tmp2&= 0x0f;
6483  000b a40f       and a,#15
6484  000d b700       ld L3164_tmp2,a
6485                   ; 113 PTR_BYTE(crc)[BYTE_H] = (u8)(table1_H(tmp1)^table2_H[tmp2]^L8BIT(crc));
6487  000f 5f             clrw x
6488  0010 97             ld xl,a
6489  0011 b601       ld a,L1164_tmp1
6490  0013 48             sll a
6491  0014 d80000         xor a,(L5064_table2_H,x)
6492  0017 b803       xor a,_CRC16+1
6493  0019 b702       ld _CRC16,a
6494                   ; 114 PTR_BYTE(crc)[BYTE_L] = (u8)(table1_L(tmp1)^table2_L[tmp2]);
6496  001b 5f             clrw x
6497  001c b600       ld a,L3164_tmp2
6498  001e 97             ld xl,a
6499  001f b601       ld a,L1164_tmp1
6500  0021 4e             swap a
6501  0022 a4f0       and a,#240
6502  0024 d80010         xor a,(L7064_table2_L,x)
6503  0027 b703       ld _CRC16+1,a
6504                   ; 115 }
6507  0029 81             ret

wzavr · 发表于 2010-8-5 11:51:40

mark 新crc16

blueagle · 发表于 2010-8-5 12:04:18

mark

cht-rtos · 发表于 2010-8-5 12:33:10

标记备查

snoopyzz · 发表于 2010-8-5 17:02:27

自已顶一下

QZDZ · 发表于 2010-8-5 18:48:15

不错，帮忙顶一下。

lihuyong · 发表于 2010-8-5 19:09:31

先mark,过两天空了再尝试

bad_fpga · 发表于 2010-8-5 19:22:58

MARK

NJ8888 · 发表于 2010-8-5 19:58:35

现在FLASH都不小，为何不就用512字节的？

snoopyzz · 发表于 2010-8-6 09:19:09

我这之前很多用AVR的产品，空间都很接近4K了。。。现在换了stm8的8K flash芯片，容量剩的多的自不必说，
但个别型号，已经用到了近7K，日本客户仍在不停的修改增加功能，
有时1分钱就难倒英雄好汉，何况近500字节。

63502925 · 发表于 2010-8-6 09:27:45

mark

snoopyzz · 发表于 2010-8-6 10:03:05

对于没有硬件乘法的MCU，编译器又烂的不像话的，以下宏
#define table1_H(n) (u8)(0x02*(n))
#define table1_L(n) (u8)(0x10*(n))

可以更改为
#define table1_H(n) (u8)((n)<<1)
#define table1_L(n) (u8)((n)<<4)

事实上cosmic就优化成了移位和交换高低半字节来做的。。。

liangyurongde · 发表于 2010-8-6 10:13:00

mark

add0 · 发表于 2010-8-6 10:29:07

MARK 新crc16

jusan520 · 发表于 2011-4-14 19:45:44

lz 好样的！

Mark for learning...

phone · 发表于 2011-5-25 14:27:50

mark

CC2530 · 发表于 2011-5-25 16:56:57

//初值 crc：ABCD  data:XY
//下标 temp1 : A^X
//下标 temp2 : A^B^X^Y
//TAB[temp1] : EFGH FG:temp1*2  H0=temp1*16
//TAB[temp2] : IJKL
//CRC_H=CD^FG^IJ
//CRC_L=H0^KL
const uint16 __pgm crc16_itut_table[16] ={
   0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,
   0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,
  };

uint16 crc16_itut_update(uint16 crc, uint8 data)
{
uint8  temp1,temp2;
uint8  crc_h,crc_l;
uint16 __IJKL;

temp2 = data^(crc/256);    //temp2=AB^XY
temp1 = temp2>>4;          //temp1=A^X
temp2^= temp1;             //temp2=AB^XY^A^X
temp2&= 0x0f;                //temp2=A^B^X^Y

#ifdef __AVR_GCC__
__IJKL=pgm16(crc16_itut_table[temp2]);
#else
__IJKL=crc16_itut_table[temp2];
#endif

crc_h = 2*temp1;             //crc_h=FG
crc_h^= crc%256;             //crc_h=FG^CD;
crc_h^= __IJKL/256;  //crc_h=FG^CD^IJ;

crc_l = __IJKL%256;  //crc_l=KL
crc_l^= temp1*16;                   //crc_l=KL^H0

return crc_h*256+crc_l;
}

kevin_ares · 发表于 2011-5-26 22:34:26

mark

fanwt · 发表于 2011-5-26 22:47:51

CRC16 MARK

shizt · 发表于 2011-5-26 22:52:20

crc16 mark!!

rafd · 发表于 2011-5-26 22:55:07

支持

shunda · 发表于 2011-5-27 08:44:01

收藏学习

utopiaprince · 发表于 2011-5-27 12:28:26

MARK，好东西要顶上去

szy19811114 · 发表于 2011-6-10 09:35:34

gaoyi3052 · 发表于 2011-6-10 19:19:41

好贴

hlswx · 发表于 2011-6-10 22:57:36

标记一下~谢谢楼主

ljqlaq · 发表于 2011-6-10 23:31:03

好帖！！！！

radar_12345 · 发表于 2011-7-4 16:02:03

lz 好样的！

Mark for learning...

bingshuihuo888 · 发表于 2011-7-4 16:17:24

现在FLASH都不小，为何不就用512字节的？

SDbeijixing · 发表于 2011-7-4 16:18:03

MARK

zhesiniya · 发表于 2011-7-4 20:33:13

留个记号。

guoermvp · 发表于 2011-8-5 11:07:59

有时间好好看看额...

zhangjinxing · 发表于 2011-8-6 02:34:17

mark

373518122 · 发表于 2011-8-7 17:33:52

mark crc16优化

zhangliang · 发表于 2011-11-16 21:14:04

mark CRC

get500wan · 发表于 2011-11-16 22:13:47

mark, crc16

uc_efm32zg103 · 发表于 2012-1-15 14:16:03

C语言代码：

const uint8 __pgm iar8051_crc16_itut_table[32] ={
  0x00,0x00,
  0x21,0x10,
  0x42,0x20,
  0x63,0x30,
  0x84,0x40,
  0xa5,0x50,
  0xc6,0x60,
  0xe7,0x70,
  0x08,0x81,
  0x29,0x91,
  0x4a,0xa1,
  0x6b,0xb1,
  0x8c,0xc1,
  0xad,0xd1,
  0xce,0xe1,
  0xef,0xf1,
};

uint16 crc16_itut_update (uint16 crc, uint8 data)
{

uint8  temp1;
uint8  crc_h,crc_l;

  crc_h =crc/256;
  crc_l=crc%256;

  crc_h = data^(crc_h);       //crc_h=AB^XY
  temp1 = crc_h>>4;          //temp1=A^X
  crc_h^= temp1;             //crc_h=AB^XY^A^X
  crc_h&= 0x0f;                //crc_h=A^B^X^Y

  crc_l=crc16_itut_table[crc_h*2]; //KL
  crc_h=crc16_itut_table[crc_h*2+1]; //IJ

  crc_h^= 2*temp1;             //crc_h=IJ^FG
  crc_h^= crc%256;             //crc_h=IJ^FG^CD;

  crc_l^= temp1*16;          //crc_l=KL^H0

  return crc_h*256+crc_l;
}

uint16 crc16_itut_check (const uint8 *data , uint16 size)
{
  uint16 crc=0;

  for(uint16 i=0;i<size;i++)
  {
crc=crc16_itut_update(crc,data);
  }

  return crc;
}

jacky2011 · 发表于 2012-2-8 11:27:22

这个必须顶！！！

haigerl · 发表于 2012-2-8 11:46:00

mark CRC16

cecwxf · 发表于 2012-5-15 11:32:09

不错确实

mcu_lover · 发表于 2012-5-15 11:43:24

学习了，在资源受限时候确实很有用处。

hzpyl · 发表于 2012-5-15 11:52:50

很好！！！！

huyang27 · 发表于 2012-5-15 12:29:01

，很好，支持一下

laohuang868 · 发表于 2012-5-15 18:07:59

嘿嘿，我正好要呢！

leoyang · 发表于 2012-10-16 11:43:04

正在探索STM32的32位CRC怎么用在MODBUS的16位CRC上，看到了楼主的贴，过来膜拜一番，谢谢分享。
之前也做过查表的CRC，不太理想。

32MCU · 发表于 2012-10-16 20:26:54

好东西。

myxiaonia · 发表于 2014-8-26 13:27:45

leoyang 发表于 2012-10-16 11:43
正在探索STM32的32位CRC怎么用在MODBUS的16位CRC上，看到了楼主的贴，过来膜拜一番，谢谢分享。
之前也做过 ...

这个就不要想了，多项式都不一样的，用不回去的

lhaoyue · 发表于 2016-11-3 13:38:37

mark 新CRC16算法

jianplx · 发表于 2016-11-3 13:50:27

顶一下

wenqingli · 发表于 2016-11-3 15:38:48

顶一下

zj_871112 · 发表于 2016-11-3 16:13:10

CRC16快速算法，收藏了~~

litrtleway · 发表于 2016-11-17 23:40:49

mark， CRC16. 感谢楼主！！！

jyrpxj · 发表于 2016-11-18 09:57:58

好算法....赞

mndsoft2012 · 发表于 2016-11-18 10:01:34

crc16 mark ，谢谢

yanyanyan168 · 发表于 2016-11-18 10:19:49

mark 新crc16

mypc16888 · 发表于 2016-11-23 22:20:39

crc16快速算法

[原创]快速CRC16算法，32字节查表法的改进优化版，速度提高60%（比512字节查表法还是慢些）

阿莫论坛20周年了！感谢大家的支持与爱护！！