本文轉自公眾號,歡迎關注

Micrium全家桶之uC-CRC: 0x01 ECC (qq.com)

前言

我們這一篇來講講Micrium全家桶的uC-CRC。該代碼庫提供了CRC算法進行錯誤檢測EDC,使用HAMMING算法實現ECC錯誤糾正。ECC算法在NAND的TFL中使用。

下載代碼

git clone https://github.com/weston-embedded/uC-CRC.git

修改版本,去掉對uC-LIB,uC-CPU等的依賴,可以直接單獨使用,方便移植。

https://github.com/qinyunti/uC-CRC.git

文件介紹

│  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

添加代碼到自己的工程

添加uC-CRC\\Cfg\\Template\\crc_cfg.h

uC-CRC\\Source下所有文件到自己的工程目錄uC-CRC下

并配置頭文件包含路徑uC-CRC

依賴

修改代碼

注釋掉crc_util.h下的

#include < cpu.h >


#include < cpu_core.h >

改為

#include < crc_cfg.h >

注釋掉ecc.h下的

#include < cpu.h >


#include < cpu_core.h >

注釋掉ecc_hamming.h下的

#include < cpu.h >


#include < cpu_core.h >


#include < lib_def.h >


#include < lib_mem.h >

注釋掉edc_crc.h下的

#include < cpu.h >


#include < cpu_core.h >


#include < lib_def.h >

注釋掉

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 < string.h >

crc_cfg.h中實現以下依賴

/*
*********************************************************************************************************
*                                                 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”

調用以下接口

Hamming_Calc

Hamming_Chk

Hamming_Correct

詳見test.c

#include < stdio.h >
#include < stdint.h >
#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;
  }

  /* 打印原始數據 */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");

  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\\r\\n",err);
    return -1;
  }
  printf("Hamming_Calc:ecc %#x %#x %#x %#x\\r\\n",s_ecc[0],s_ecc[1],s_ecc[2],s_ecc[3]);

/*
 *  1位數據錯誤
 */
  /* DATA注入錯誤 */
  printf("\\r\\n[DATA err test]\\r\\n");
  s_buffer[0] ^= 0x80;

  /* 打印錯誤數據 */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");

  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\\r\\n",err);
    return -2;
  }
  printf("Hamming_Chk:loc B[%d].b[%d] B[%d].b[%d]\\r\\n",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);
  /* 打印修復后的數據 */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");
  printf("Hamming_Correct:ecc %#x %#x %#x %#x\\r\\n",s_ecc[0],s_ecc[1],s_ecc[2],s_ecc[3]);
  printf("%s",s_err_str[err].str);
/*
 *  1位ECC錯誤
 */
  /* DATA注入錯誤 */
  printf("\\r\\n[ECC err test]\\r\\n");
  s_ecc[1] ^= 0x02;

  /* 打印錯誤數據 */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");

  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\\r\\n",err);
    return -2;
  }
  printf("Hamming_Chk:loc B[%d].b[%d] B[%d].b[%d]\\r\\n",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);


  /* 打印修復后的數據 */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");
  printf("Hamming_Correct:ecc %#x %#x %#x %#x\\r\\n",s_ecc[0],s_ecc[1],s_ecc[2],s_ecc[3]);
  printf("%s",s_err_str[err].str);
/*
 *  2位數據錯誤
 */
  /* DATA注入錯誤 */
  printf("\\r\\n[2DATA err test]\\r\\n");
  s_buffer[2] ^= 0x04;
  s_buffer[5] ^= 0x10;

  /* 打印錯誤數據 */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");

  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\\r\\n",err);
    return -2;
  }
  printf("Hamming_Chk:loc B[%d].b[%d] B[%d].b[%d]\\r\\n",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);
  /* 打印修復后的數據 */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");
  printf("Hamming_Correct:ecc %#x %#x %#x %#x\\r\\n",ecc[0],ecc[1],ecc[2],ecc[3]);
  printf("%s",s_err_str[err].str);
  return 0;
}

測試結果如下可以看到,1位的數據錯誤校正過來了,ECC編碼本身的1位錯誤認為是不可校正錯誤,兩位數據錯誤也是不可校正錯誤

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

漢明碼

冗余位

假設有m位數據,至少要添加n位冗余位才能檢測出錯誤(只考慮只有1個bit錯誤的情況)。

m位數據,n位冗余數據錯1位的情況有m+n種,還有一種情況是無錯。

需要用n位冗余位去標志是哪一位錯了,所以要滿足2^n >= m+n+1。

奇偶校驗

奇校驗:數據和校驗位一起,1的個數為奇數

偶校驗:數據和校驗位一起,1的個數為偶數

奇偶校驗只能發現奇數個位翻轉,因為偶數個位翻轉奇偶性不變。

漢明碼

即奇偶校驗的升級,組合。

先根據2^n >= m+n+1計算需要多少個校驗位,

然后確認校驗位的位置在2^n索引位上(索引從1開始)。

比如7位數據需要4位校驗位,2^4 >= 7+4+1,一共11位,從1~11編號索引

寫為二進制

0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011

將bit0是1的劃分為一組 0001 0011 0101 0111 1001 1011

即1 3 5 7 9 11, 將對應數據位奇校驗,放在2^0校驗位

將bit1是1的劃分為一組 0010 0011 0110 0111 1010 1011

即2 3 6 7 10 11, 將對應數據位奇校驗,放在2^1校驗位

將bit2是1的劃分為一組 0100 0101 0110 0111

即4 5 6 7, 將對應數據位奇校驗,放在2^2校驗位

將bit3是1的劃分為一組 0100 0101 0110 0111

即8 9 10 11, 將對應數據位奇校驗,放在2^3校驗位

糾錯,如果2^0校驗位不對bit0寫1,如果2^1校驗位不對bit1寫1,得到的二進制數就是出錯位的的索引。

比如以上如果bit5翻轉了,索引5是在2^0和2^2組的所以,是101,即索引5的數據有錯。

漢明距離

在一個碼組集合中，任意兩個碼字之間對應位上碼元取值不同的位的數目定義為這兩個碼字之間的漢明距離d。例如：(00)與(01)的距離是1，(110)和(101)的距離是2。在一個碼組集合中，任意兩個編碼之間漢明距離的最小值稱為這個碼組的最小漢明距離。最小漢明距離越大，碼組越具有抗干擾能力,即差異越大,冗余越多。即編碼只用了一部分,剩余的空著,如果出現了錯誤則肯定是變成了空著的編碼。

比如兩位的編碼實際可以編碼為00 01 10 11,但是我們只用00代表A,10代表B,

那么收到01后,我們知道出錯了,那么是哪個出錯了呢，00變為01需要變化1位,10變為01需要變化2位,所以所以我們更傾向于是00變化了一位即是A出錯了,

所以我們可以認為00和01都代表A

10 11 都代表B

這樣實際就是用冗余來提高抗干擾能力,我們粗暴的發兩次也是冗余,但是冗余太多了浪費空間,所以可以選擇不冗余這么多,這個漢明距離d就是冗余的多少,d越大冗余越大,d越小冗余越小。

l當碼組用于檢測錯誤時，設可檢測e個位的錯誤，則d ≥ e + 1

l若碼組用于糾錯，設可糾錯t個位的錯誤，則 d ≥ 2 ? t + 1

即AB之間的距離至少是1才能區分AB, 剩余的空間2t劃分一半,靠近A的一半t認為是A,靠近B的一半t認為是B。

l如果碼組用于糾正t個錯，檢測e個錯，則d ≥ e + t + 1

NAND中的硬件ECC

這里以W25N01GVZEIG芯片為例,不同芯片略有差異

一個PAGE大大小是2112字節其中用戶區域2048字節+額外區域64字節

將PAGE的用戶區域和額外區域都分成4份即Sector,

則512字節用戶區域對應16字節額外區域。

16字節額外區域如上圖

0- 1 :2字節位壞塊標記

2- 3 :2字節用戶數據II

4-7 : 4字節用戶數據I

8-D: 6字節前面Sector數據的ECC校驗值

E-F:4-D對應的10字節的ECC校驗值

問題:ECC for Sector 0本身有誤碼可以通過ECC for Spare檢測出來,但是如果ECC for Spare本身有誤碼呢?

芯片自帶的ECC校驗使能通過寄存器配置(有些型號是默認使能的)

寫數據時自動計算ECC并更新到64字節額外區域,讀數據時自動校驗ECC并進行校正,返回校正完后的正確值。

讀數據時可以讀狀態寄存器確認ECC狀態

NAND中的軟件ECC

256字節2048位,檢測1位錯誤理論上只需要12位校驗位即可,

2^12 >= 2048 + 12 + 1。

但是實際一半是糾正1位錯誤,檢測2位錯誤

所以d ≥ e + t + 1=4

漢明距離至少要是4.

NAND實際應用中是按照行列分別校驗的

按照一個字節8位x256字節

組成256x8,256行8列的矩陣

256行 16個校驗位

8列 6個校驗位

總共22位,3個字節,剩余兩個bit未用放在高位

如下所示

參考

tn2963_ecc_in_slc_nand.pdf

samsung_ecc_algorithm_for_256b.pdf

Linux中的實現

參考以下鏈接,不再詳述

http://lxr.linux.no/linux+v2.6.27/drivers/mtd/nand/nand_ecc.c#L103

https://www.kernel.org/doc/html/latest/driver-api/mtd/nand_ecc.html

待辦

以上Micrium和Linux的實現實際都沒有實現檢測ECC碼自身錯誤的情況,都只能校正數據的1位錯誤,對于ECC碼本身錯誤一位認為是不可校正錯誤,這里后續可以考慮優化。

總結

以上介紹了Micrium全家桶的uC-CRC組件,并修改成無其他依賴,比較好移植使用。其中的ECC在NAND中使用,所以重點進行了介紹。不僅僅介紹代碼庫的使用,同時也分析了原理,只有理論結合實踐才能真的用好。CRC部分下次可以單獨再講講。

審核編輯：湯梓紅