講講Micrium全家桶的uC-CRC算法
前言
我們這一篇來講講Micrium全家桶的uC-CRC。該代碼庫提供了CRC算法進(jìn)行錯(cuò)誤檢測EDC,使用HAMMING算法實(shí)現(xiàn)ECC錯(cuò)誤糾正。ECC算法在NAND的TFL中使用。
修改版本,去掉對uC-LIB,uC-CPU等的依賴,可以直接單獨(dú)使用,方便移植。
文件介紹
│ LICENSE │ NOTICE │ readme.md │ ├─Cfg │ └─Template │ crc_cfg.h │ ├─Ports │ ├─ARM │ │ └─IAR │ │ ecc_hamming_a.asm │ │ edc_crc_a.asm │ │ │ └─ARM-Cortex-M3 │ └─IAR │ ecc_hamming_a.asm │ edc_crc_a.asm │ └─Source crc_util.c crc_util.h ecc.h ecc_hamming.c ecc_hamming.h edc_crc.c edc_crc.h
| 文件 | 說明 |
| LICENSE/NOTICE/readme.md | LICENSE使用的APACHE-2.0 |
| crc_cfg.h | 配置文件 |
| ecc_hamming_a.asm |
使用匯編實(shí)現(xiàn) Hamming_ParCalcBitWord_32 默認(rèn)提供了ARM和ARM-Cortex-M3架構(gòu)IAR編譯器的版本 crc_cfg.h中#defineEDC_CRC_CFG_OPTIMIZE_ASM_ENDEF_ENABLED時(shí)使用,默認(rèn)不使 |
| edc_crc_a.asm |
使用匯編實(shí)現(xiàn) CRC_ChkSumCalcTbl_16Bit CRC_ChkSumCalcTbl_16Bit_ref CRC_ChkSumCalcTbl_32Bit CRC_ChkSumCalcTbl_32Bit_ref 默認(rèn)提供了ARM和ARM-Cortex-M3架構(gòu)IAR編譯器的版本 crc_cfg.h中#defineEDC_CRC_CFG_OPTIMIZE_ASM_ENDEF_ENABLED時(shí)使用,默認(rèn)不使用 |
| crc_util.c/h |
實(shí)現(xiàn)CRCUtil_PopCnt_32 算法來自于http://en.wikipedia.org/wiki/Hamming_weight |
| ecc_hamming.c/h | Ecc算法代碼 |
| edc_crc.c/h | Crc算法代碼 |
添加代碼到自己的工程
添加uC-CRCCfgTemplatecrc_cfg.h
uC-CRCSource下所有文件到自己的工程目錄uC-CRC下
并配置頭文件包含路徑uC-CRC
依賴
| 文件 | 內(nèi)容 |
|
cpu.h cpu_core.h lib_def.h lib_mem.h |
CPU_BOOLEAN CPU_INT08U CPU_INT16U CPU_INT32U CPU_ADDR CPU_DATA CPU_SIZE_T CPU_WORD_SIZE_32 DEF_NO DEF_YES DEF_DISABLED DEF_ENABLED DEF_INVALID DEF_VALID DEF_OCTET_NBR_BITS DEF_BIT DEF_BIT_00~DEF_BIT_12 DEF_BIT_13 DEF_BIT_15 DEF_BIT_17 DEF_BIT_19 DEF_BIT_21 DEF_BIT_23 DEF_BIT_25 DEF_BIT_27 DEF_BIT_29 DEF_BIT_31 DEF_BIT_SET DEF_BIT_IS_SET CPU_SW_EXCEPTION MEM_VAL_COPY_GET_INT32U MEM_VAL_COPY_GET_INTU MEM_VAL_COPY_SET_INT32U Mem_Clr |
修改代碼
注釋掉crc_util.h下的
#include#include
改為
#include
注釋掉ecc.h下的
#include#include
注釋掉ecc_hamming.h下的
#include#include #include #include
注釋掉edc_crc.h下的
#include#include #include
注釋掉
ecc_hamming.c下的
Mem_Clr((void *)p_ecc, HAMMING_LEN_OCTET_ECC); /* Init ECC buf for err(s) (see Note #6). */
改為
memset((void *)p_ecc, 0, HAMMING_LEN_OCTET_ECC);
前面添加
#include
crc_cfg.h中實(shí)現(xiàn)以下依賴
/*
*********************************************************************************************************
* PORT
*
* Note(s) : (1) 以下添加依賴部分移植
*
*
*********************************************************************************************************
*/
/* ------------------ CPU WORD-ENDIAN ORDER ------------------- */
#define CPU_ENDIAN_TYPE_NONE 0u
#define CPU_ENDIAN_TYPE_BIG 1u /* Big- endian word order (see Note #1a). */
#define CPU_ENDIAN_TYPE_LITTLE 2u /* Little-endian word order (see Note #1b). */
#define CPU_CFG_ENDIAN_TYPE CPU_ENDIAN_TYPE_LITTLE
typedef unsigned char CPU_BOOLEAN; /* 8-bit boolean or logical */
typedef unsigned char CPU_INT08U; /* 8-bit unsigned integer */
typedef unsigned short CPU_INT16U; /* 16-bit unsigned integer */
typedef unsigned int CPU_INT32U; /* 32-bit unsigned integer */
typedef CPU_INT32U CPU_ADDR; /* CPU address type based on address bus size. */
typedef CPU_INT32U CPU_DATA; /* CPU data type based on data bus size. */
typedef CPU_ADDR CPU_SIZE_T; /* Defines CPU standard 'size_t' size. */
#define CPU_WORD_SIZE_32 4u /* 32-bit word size (in octets). */
/* ----------------- BOOLEAN DEFINES ------------------ */
#define DEF_NO 0u
#define DEF_YES 1u
#define DEF_DISABLED 0u
#define DEF_ENABLED 1u
#define DEF_INVALID 0u
#define DEF_VALID 1u
#define DEF_OCTET_NBR_BITS 8u
#define DEF_BIT(bit) (1uL << (bit))
/* ------------------- BIT DEFINES -------------------- */
#define DEF_BIT_00 0x01u
#define DEF_BIT_01 0x02u
#define DEF_BIT_02 0x04u
#define DEF_BIT_03 0x08u
#define DEF_BIT_04 0x10u
#define DEF_BIT_05 0x20u
#define DEF_BIT_06 0x40u
#define DEF_BIT_07 0x80u
#define DEF_BIT_08 0x0100u
#define DEF_BIT_09 0x0200u
#define DEF_BIT_10 0x0400u
#define DEF_BIT_11 0x0800u
#define DEF_BIT_12 0x1000u
#define DEF_BIT_13 0x2000u
#define DEF_BIT_15 0x8000u
#define DEF_BIT_17 0x00020000u
#define DEF_BIT_19 0x00080000u
#define DEF_BIT_21 0x00200000u
#define DEF_BIT_23 0x00800000u
#define DEF_BIT_25 0x02000000u
#define DEF_BIT_27 0x08000000u
#define DEF_BIT_29 0x20000000u
#define DEF_BIT_31 0x80000000u
#define DEF_BIT_SET(val, mask) ((val) = ((val) | (mask)))
#define DEF_BIT_IS_SET(val, mask) (((((val) & (mask)) == (mask)) && ((mask) != 0u)) ? (DEF_YES) : (DEF_NO))
#define CPU_SW_EXCEPTION(err_rtn_val) do {
;
} while (1)
#define MEM_VAL_COPY_GET_INT32U(addr_dest, addr_src) do {
CPU_INT08U *destptr = (CPU_INT08U *)(addr_dest);
CPU_INT08U *srcptr = (CPU_INT08U *)(addr_src);
(*((destptr) + 0)) = (*((srcptr) + 0));
(*((destptr) + 1)) = (*((srcptr) + 1));
(*((destptr) + 2)) = (*((srcptr) + 2));
(*((destptr) + 3)) = (*((srcptr) + 3)); } while (0)
#define MEM_VAL_COPY_GET_INTU(addr_dest, addr_src, val_size) do {
CPU_SIZE_T _i;
for (_i = 0; _i < (val_size); _i++) {
(*(((CPU_INT08U *)(addr_dest)) + _i)) = (*(((CPU_INT08U *)(addr_src)) + _i));
}
} while (0)
#define MEM_VAL_COPY_SET_INT32U(addr_dest, addr_src) MEM_VAL_COPY_GET_INT32U(addr_dest, addr_src)
測試
ECC
用戶代碼中#include ”ecc_hamming.h”
調(diào)用以下接口
Hamming_Calc
Hamming_Chk
Hamming_Correct
詳見test.c
#include#include #include "ecc_hamming.h" typedef struct { ECC_ERR err; char* str; }err_str; err_str s_err_str[]= { {ECC_ERR_NONE,"No error."}, {ECC_ERR_CORRECTABLE,"Correctable error detected in data."}, {ECC_ERR_ECC_CORRECTABLE,"Correctable error detected in ECC."}, {ECC_ERR_INVALID_ARG,"Argument passed invalid value. "}, {ECC_ERR_INVALID_LEN,"Len argument passed invalid length."}, {ECC_ERR_NULL_PTR,"Pointer argument passed NULL pointer."}, {ECC_ERR_UNCORRECTABLE,"Uncorrectable error detected in data."} }; uint8_t s_buffer[33]; uint8_t s_ecc[4]; int ecc_main(int argc, char* argv[]) { CPU_INT08U ecc[4]; ECC_ERR_LOC err_loc[2]={{0,0},{0,0}}; ECC_ERR err; for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { s_buffer[i] = i+1; } /* 打印原始數(shù)據(jù) */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); CPU_SIZE_T len = (sizeof(s_buffer)/sizeof(s_buffer[0])); CPU_SIZE_T len_buf = (len / 32)*32; CPU_SIZE_T len_buf_ext = len % 32; CPU_INT08U* p_buf_ext = (CPU_INT08U *)s_buffer + len_buf; Hamming_Calc(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,&err); if(ECC_ERR_NONE != err) { printf("Hamming_Calc err:%d ",err); return -1; } printf("Hamming_Calc:ecc %#x %#x %#x %#x ",s_ecc[0],s_ecc[1],s_ecc[2],s_ecc[3]); /* * 1位數(shù)據(jù)錯(cuò)誤 */ /* DATA注入錯(cuò)誤 */ printf(" [DATA err test] "); s_buffer[0] ^= 0x80; /* 打印錯(cuò)誤數(shù)據(jù) */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); if(ECC_FAULT == Hamming_Chk(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,err_loc,sizeof(err_loc)/sizeof(err_loc[0]),&err)) { printf("Hamming_Chk err:%d ",err); return -2; } printf("Hamming_Chk:loc B[%d].b[%d] B[%d].b[%d] ",err_loc[0].LocOctet,err_loc[0].LocBit,err_loc[1].LocOctet,err_loc[1].LocBit); printf("%s",s_err_str[err].str); Hamming_Correct(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,&err); /* 打印修復(fù)后的數(shù)據(jù) */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); printf("Hamming_Correct:ecc %#x %#x %#x %#x ",s_ecc[0],s_ecc[1],s_ecc[2],s_ecc[3]); printf("%s",s_err_str[err].str); /* * 1位ECC錯(cuò)誤 */ /* DATA注入錯(cuò)誤 */ printf(" [ECC err test] "); s_ecc[1] ^= 0x02; /* 打印錯(cuò)誤數(shù)據(jù) */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); if(ECC_FAULT == Hamming_Chk(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,err_loc,sizeof(err_loc)/sizeof(err_loc[0]),&err)) { printf("Hamming_Chk err:%d ",err); return -2; } printf("Hamming_Chk:loc B[%d].b[%d] B[%d].b[%d] ",err_loc[0].LocOctet,err_loc[0].LocBit,err_loc[1].LocOctet,err_loc[1].LocBit); printf("%s",s_err_str[err].str); Hamming_Correct(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,&err); /* 打印修復(fù)后的數(shù)據(jù) */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); printf("Hamming_Correct:ecc %#x %#x %#x %#x ",s_ecc[0],s_ecc[1],s_ecc[2],s_ecc[3]); printf("%s",s_err_str[err].str); /* * 2位數(shù)據(jù)錯(cuò)誤 */ /* DATA注入錯(cuò)誤 */ printf(" [2DATA err test] "); s_buffer[2] ^= 0x04; s_buffer[5] ^= 0x10; /* 打印錯(cuò)誤數(shù)據(jù) */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); if(ECC_FAULT == Hamming_Chk(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,err_loc,sizeof(err_loc)/sizeof(err_loc[0]),&err)) { printf("Hamming_Chk err:%d ",err); return -2; } printf("Hamming_Chk:loc B[%d].b[%d] B[%d].b[%d] ",err_loc[0].LocOctet,err_loc[0].LocBit,err_loc[1].LocOctet,err_loc[1].LocBit); printf("%s",s_err_str[err].str); Hamming_Correct(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,&err); /* 打印修復(fù)后的數(shù)據(jù) */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); printf("Hamming_Correct:ecc %#x %#x %#x %#x ",ecc[0],ecc[1],ecc[2],ecc[3]); printf("%s",s_err_str[err].str); return 0; }
測試結(jié)果如下可以看到,1位的數(shù)據(jù)錯(cuò)誤校正過來了,ECC編碼本身的1位錯(cuò)誤認(rèn)為是不可校正錯(cuò)誤,兩位數(shù)據(jù)錯(cuò)誤也是不可校正錯(cuò)誤
CRC
接口如下,下篇再單講
CRC_Open_16Bit CRC_WrBlock_16Bit CRC_WrOctet_16Bit CRC_Close_16Bit CRC_Open_32Bit CRC_WrBlock_32Bit CRC_WrOctet_32Bit CRC_Close_32Bit CRC_Reflect_08Bit CRC_Reflect_16Bit CRC_Reflect_32Bit CRC_ChkSumCalc_16Bit CRC_ChkSumCalc_32Bit
漢明碼
冗余位
假設(shè)有m位數(shù)據(jù),至少要添加n位冗余位才能檢測出錯(cuò)誤(只考慮只有1個(gè)bit錯(cuò)誤的情況)。
m位數(shù)據(jù),n位冗余數(shù)據(jù)錯(cuò)1位的情況有m+n種,還有一種情況是無錯(cuò)。
需要用n位冗余位去標(biāo)志是哪一位錯(cuò)了,所以要滿足2^n >= m+n+1。
奇偶校驗(yàn)
奇校驗(yàn):數(shù)據(jù)和校驗(yàn)位一起,1的個(gè)數(shù)為奇數(shù)
偶校驗(yàn):數(shù)據(jù)和校驗(yàn)位一起,1的個(gè)數(shù)為偶數(shù)
奇偶校驗(yàn)只能發(fā)現(xiàn)奇數(shù)個(gè)位翻轉(zhuǎn),因?yàn)榕紨?shù)個(gè)位翻轉(zhuǎn)奇偶性不變。
漢明碼
即奇偶校驗(yàn)的升級,組合。
先根據(jù)2^n >= m+n+1計(jì)算需要多少個(gè)校驗(yàn)位,
然后確認(rèn)校驗(yàn)位的位置在2^n索引位上(索引從1開始)。
比如7位數(shù)據(jù)需要4位校驗(yàn)位,2^4 >= 7+4+1,一共11位,從1~11編號索引
寫為二進(jìn)制
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011
將bit0是1的劃分為一組 0001 0011 0101 0111 1001 1011
即1 3 57 9 11, 將對應(yīng)數(shù)據(jù)位奇校驗(yàn),放在2^0校驗(yàn)位
將bit1是1的劃分為一組 0010 0011 0110 0111 1010 1011
即2 3 6 7 10 11, 將對應(yīng)數(shù)據(jù)位奇校驗(yàn),放在2^1校驗(yàn)位
將bit2是1的劃分為一組 0100 0101 0110 0111
即4 56 7, 將對應(yīng)數(shù)據(jù)位奇校驗(yàn),放在2^2校驗(yàn)位
將bit3是1的劃分為一組 0100 0101 0110 0111
即8 9 10 11, 將對應(yīng)數(shù)據(jù)位奇校驗(yàn),放在2^3校驗(yàn)位
糾錯(cuò),如果2^0校驗(yàn)位不對bit0寫1,如果2^1校驗(yàn)位不對bit1寫1,得到的二進(jìn)制數(shù)就是出錯(cuò)位的的索引。
比如以上如果bit5翻轉(zhuǎn)了,索引5是在2^0和2^2組的所以,是101,即索引5的數(shù)據(jù)有錯(cuò)。
漢明距離
在一個(gè)碼組集合中，任意兩個(gè)碼字之間對應(yīng)位上碼元取值不同的位的數(shù)目定義為這兩個(gè)碼字之間的漢明距離d。例如：(00)與(01)的距離是1，(110)和(101)的距離是2。在一個(gè)碼組集合中，任意兩個(gè)編碼之間漢明距離的最小值稱為這個(gè)碼組的最小漢明距離。最小漢明距離越大，碼組越具有抗干擾能力,即差異越大,冗余越多。即編碼只用了一部分,剩余的空著,如果出現(xiàn)了錯(cuò)誤則肯定是變成了空著的編碼。
比如兩位的編碼實(shí)際可以編碼為00 01 10 11,但是我們只用00代表A,10代表B,
那么收到01后,我們知道出錯(cuò)了,那么是哪個(gè)出錯(cuò)了呢，00變?yōu)?1需要變化1位,10變?yōu)?1需要變化2位,所以所以我們更傾向于是00變化了一位即是A出錯(cuò)了,
所以我們可以認(rèn)為00和01都代表A
10 11 都代表B
這樣實(shí)際就是用冗余來提高抗干擾能力,我們粗暴的發(fā)兩次也是冗余,但是冗余太多了浪費(fèi)空間,所以可以選擇不冗余這么多,這個(gè)漢明距離d就是冗余的多少,d越大冗余越大,d越小冗余越小。
l當(dāng)碼組用于檢測錯(cuò)誤時(shí)，設(shè)可檢測e個(gè)位的錯(cuò)誤，則d ≥ e + 1
l若碼組用于糾錯(cuò)，設(shè)可糾錯(cuò)t個(gè)位的錯(cuò)誤，則 d ≥ 2 ? t + 1
即AB之間的距離至少是1才能區(qū)分AB, 剩余的空間2t劃分一半,靠近A的一半t認(rèn)為是A,靠近B的一半t認(rèn)為是B。
l如果碼組用于糾正t個(gè)錯(cuò)，檢測e個(gè)錯(cuò)，則d ≥ e + t + 1
NAND中的硬件ECC
這里以W25N01GVZEIG芯片為例,不同芯片略有差異
一個(gè)PAGE大大小是2112字節(jié)其中用戶區(qū)域2048字節(jié)+額外區(qū)域64字節(jié)
將PAGE的用戶區(qū)域和額外區(qū)域都分成4份即Sector,
則512字節(jié)用戶區(qū)域?qū)?yīng)16字節(jié)額外區(qū)域。
16字節(jié)額外區(qū)域如上圖
0- 1 :2字節(jié)位壞塊標(biāo)記
2- 3 :2字節(jié)用戶數(shù)據(jù)II
4-7 : 4字節(jié)用戶數(shù)據(jù)I
8-D: 6字節(jié)前面Sector數(shù)據(jù)的ECC校驗(yàn)值
E-F:4-D對應(yīng)的10字節(jié)的ECC校驗(yàn)值
問題:ECC for Sector 0本身有誤碼可以通過ECC for Spare檢測出來,但是如果ECC for Spare本身有誤碼呢?
芯片自帶的ECC校驗(yàn)使能通過寄存器配置(有些型號是默認(rèn)使能的)
寫數(shù)據(jù)時(shí)自動(dòng)計(jì)算ECC并更新到64字節(jié)額外區(qū)域,讀數(shù)據(jù)時(shí)自動(dòng)校驗(yàn)ECC并進(jìn)行校正,返回校正完后的正確值。
讀數(shù)據(jù)時(shí)可以讀狀態(tài)寄存器確認(rèn)ECC狀態(tài)
NAND中的軟件ECC
256字節(jié)2048位,檢測1位錯(cuò)誤理論上只需要12位校驗(yàn)位即可,
2^12 >= 2048 + 12 + 1。
但是實(shí)際一半是糾正1位錯(cuò)誤,檢測2位錯(cuò)誤
所以d ≥ e + t + 1=4
漢明距離至少要是4.
NAND實(shí)際應(yīng)用中是按照行列分別校驗(yàn)的
按照一個(gè)字節(jié)8位x256字節(jié)
組成256x8,256行8列的矩陣
256行 16個(gè)校驗(yàn)位
8列 6個(gè)校驗(yàn)位
總共22位,3個(gè)字節(jié),剩余兩個(gè)bit未用放在高位
如下所示
待辦
以上Micrium和Linux的實(shí)現(xiàn)實(shí)際都沒有實(shí)現(xiàn)檢測ECC碼自身錯(cuò)誤的情況,都只能校正數(shù)據(jù)的1位錯(cuò)誤,對于ECC碼本身錯(cuò)誤一位認(rèn)為是不可校正錯(cuò)誤,這里后續(xù)可以考慮優(yōu)化。
總結(jié)
以上介紹了Micrium全家桶的uC-CRC組件,并修改成無其他依賴,比較好移植使用。其中的ECC在NAND中使用,所以重點(diǎn)進(jìn)行了介紹。不僅僅介紹代碼庫的使用,同時(shí)也分析了原理,只有理論結(jié)合實(shí)踐才能真的用好。CRC部分下次可以單獨(dú)再講講。
審核編輯：劉清
-
ECC
+關(guān)注
關(guān)注
0文章
97瀏覽量
20556 -
CRC算法
+關(guān)注
關(guān)注
0文章
15瀏覽量
8849 -
EDC
+關(guān)注
關(guān)注
0文章
8瀏覽量
3782
原文標(biāo)題：Micrium全家桶之uC-CRC: 0x01 ECC
文章出處：【微信號：麥克泰技術(shù)，微信公眾號：麥克泰技術(shù)】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
Micrium全家桶之uC-FS: 0x02 NAND FTL算法原理詳解
Micrium全家桶之uC-FS: 0x01 NAND FTL
Micrium全家桶之uC-CRC: 0x02 CRC
這段CRC算法是什么意思
CRC算法原理及C語言實(shí)現(xiàn)
LTE系統(tǒng)的CRC校驗(yàn)算法及DSP實(shí)現(xiàn)
基于SATAⅡ協(xié)議的CRC32并行算法的研究
在FPGA上實(shí)現(xiàn)CRC算法的程序
嵌入式開發(fā)的crc算法知識(shí)精選
加拿大肯德基推出比特幣全家桶顧客可以用比特幣支付
如何使用SMART編寫CRC的校驗(yàn)算法程序
工商網(wǎng)監(jiān)
評論