📄 bch_hm.c
字号:
/* should be in range 1 <= nsa < 0x4000 */
/* */
/* Returned value : */
/* */
/* nsa^(-1) mod p(X) ( finite field modular inverse of nsa ) */
/* */
static FLSNative ECC_BCH_Inv(FLSNative nsa)
{
FLSNative nsn1 = 0x6111 ; /* p(X), modulo polynomial */
FLSNative nsn2 = nsa << 1 ; /* nsn2 = 2 * nsa */
FLSNative nsa1 = 0 ; /* Initial value of nsa1 */
FLSNative nsa2 = 0x2000 ; /* Initial value of nsa2, */
/* '1' in big endian representation */
FLSNative nsa2q ; /* nsa2 * q */
/* differnece between positions of MSbit of nsn1 and nsn2 */
FLSNative nbnumbits ;
FLSNative nbmask = 0x0001 ; /* points to LS bit */
FLSNative nbt ; /* temporary variable */
while( nsn2 ) /* do until termination */
{
/* Find number of leading zeros in nsn2 */
nbnumbits = 1 ;
while ( ( ( nsn2 >> nbnumbits ) & nbmask ) == 0 ) nbnumbits++ ;
nsa2q = nsa2 ; /* Initial value of nsa2q */
/* Initial subtraction of shifted nsn2 from nsn1 */
nsn1 ^= ( nsn2 >> nbnumbits ) ;
/* perform nbnumbits subtraction of shifted nsn2 from nsn1 */
while ( nbnumbits-- > 0 )
{
nbmask <<= 1 ; /* Advance nbmask */
if ( nsn1 & nbmask )
{
nsn1 ^= ( nsn2 >> nbnumbits );
/* shifted nsn2 is subtracted from nsn1 */
nsa2q = nsa2 ^ ( nsa2q >> 1 ) ;
/* next value of nsa2q = nsa2 * q */
}
else
nsa2q >>= 1 ; /* next value of nsa2q = nsa2 * q */
}
/* Advance nsn1 and nsn2 */
nbt = nsn1 ;
nsn1 = nsn2 ;
nsn2 = nbt ;
/* Advance nsa1 and nsa2 */
nbt = nsa2 ;
nsa2 = nsa1 ^ nsa2q ;
nsa1 = nbt ;
}
return nsa1 ;
}
/* ------------------------------------------------------------------------- */
/* Error Location Function */
/* */
/* Algorithms and programming were written by : */
/* */
/* Itai Dror */
/* */
/* Fortress Security Division, Omer */
/* M - Systems, Flash Disk Pioneers */
/* email: itaid@m-sys.com */
/* */
/* version 1.0, Feb. 2, 2002 */
/* */
/* All finite field elements are stored and treated in big endian format */
/* */
/* For example: */
/* */
/* 0x3088 represents: 1 + X + X ^ 6 + X ^ 10 + X ^ 14 */
/* */
/* Coefficient of X ^ 14 is an hidden bit */
/* */
/* ------------------------------------------------------------------------- */
/* */
/* function: */
/* FLSNative ECC_BCH_FindLocator( */
/* FLSNative nsS[], FLSNative nsd1, FLSNative nsLocator[] ) */
/* */
/* description: */
/* */
/* The following routine finds the error location polynomial */
/* from the syndrome components. The method is according to Chen */
/* and is the binary version of Berlekamp algorithm */
/* */
/* C. L. Chen, "High Speed Decoding of BCH Codes," */
/* IEEE Transactions on Information Theory, vol. IT-27, no. 2, march 1981. */
/* Algorithm is described in the following book: */
/* Shu Lin & Daniel J. Costelo, "Error Control Coding", Chapter 6, */
/* Prentice Hall, 1983. */
/* */
/* */
/* Input: */
/* nsS[] - Array of syndrome components */
/* nsd1 - First discrpacny factor */
/* */
/* Output: */
/* nsLocator[] - Error location polynomial */
/* 1 + nsLocator[0] * X + nsLocator[1] * X ^ 2 + nsLocator[2] * X ^ 3 + */
/* nsLocator[3] * X ^ 4 */
/* */
/* returned value - */
/* */
/* 2, 3, 4 - Number of errors and degree of location polynomial */
/* 5 - more then 4 errors, code can not correct data */
/* */
/* ------------------------------------------------------------------------- */
static FLSNative ECC_BCH_FindLocator( FLSNative nsS[], FLSNative nsd1,
FLSNative nsLocator[] )
{
/* nsS is an array of the syndrome components */
FLSNative nsSigma[MAXERRORS+2][MAXERRORS] ;
FLSNative nsd[MAXERRORS+2] ; /* Discrepancy factor at each iteration */
FLSNative nsL[MAXERRORS+2] ; /* Maximum power of Sigma at each iteration */
/* (2 * nsu - nsL) parameter at each iteration */
FLSNative nsdiff[MAXERRORS+2] ;
FLSNative nsmaxdiff ; /* Maximum nsdiff */
FLSNative nsu ; /* Berlekamp algorithm iterator */
FLSNative nsi, nsj ; /* iterators */
FLSNative nsro ; /* Index of correction factor */
FLSNative nsdinvro ; /* nsd[nsro] ^ -1 */
FLSNative nsdudro ; /* nsd[nsu] * nsd[nsro] ^ -1 */
FLSNative nsdiffdegree ; /* 2 * ( nsu - nsro ) */
FLSNative nsnextdegree ; /* Next nsL */
FLSNative nsSind ; /* Index for nsS */
FLSNative nstemp ;
/* Initialize the Berlekamp algorithm table */
nsd[0] = 0x2000 ; /* Discrepancy factor for nsu == 1/2 */
nsd[1] = nsS[1] ; /* Discrepancy factor for nsu == 0 */
nsd[2] = nsd1 ; /* Discrepancy factor for nsu == 1 */
nsL[0] = 0 ; /* Power of Location polynomial at nsu == -1/2 is 0 */
nsL[1] = 0 ; /* Power of Location polynomial at nsu == 0 is 0 */
nsdiff[0] = -1 ; /* 2 * nsu - nsL parameter for nsu == 1/2 */
nsdiff[1] = 0 ; /* 2 * nsu - nsL parameter for nsu == 0 */
/* Initialize Sigma matrix */
for ( nsi = 0 ; nsi < MAXERRORS + 2 ; nsi++ )
for ( nsj = 0 ; nsj < MAXERRORS ; nsj++ )
nsSigma[nsi][nsj] = 0 ;
nsSigma[2][0] = nsS[1] ; /* nsSigma at nsu == 1 */
if ( nsS[1] ) nsL[2] = 1 ; /* nsL at nsu == 1 */
else nsL[2] = 0 ;
nsdiff[2] = 2 - nsL[2] ; /* 2 * nsu - nsL parameter for nsu == 1 */
/* Iterate on degrees of polynomial */
for ( nsu = 1; nsu < MAXERRORS ; nsu++ )
{
if ( nsd[nsu+1] ) /* If next discrepancy factor is not 0 */
{
/* Locate maximum value of 2nsu - lnsu */
nsmaxdiff = -1 ; /* Initial value of nsmaxdiff */
nsro = 0 ; /* Initial value of nsro */
/* Iterate from first row to current row */
for ( nsi = 1 ; nsi < nsu + 1 ; nsi++ )
if ( (nsdiff[nsi] > nsmaxdiff) && nsd[nsi] )
{
nsmaxdiff = nsdiff[nsi] ;
nsro = nsi ;
}
nsdinvro = ECC_BCH_Inv(nsd[nsro]) ; /* nsdinvro = dro ^ -1 */
nsdudro = ECC_BCH_Mul(nsdinvro,nsd[nsu+1]) ; /* du * dro ^ -1 */
nsdiffdegree = ( ( nsu-(nsro-1) ) << 1) ; /* 2 * ( nsu - nsro ) */
if ( nsro == 0 ) nsdiffdegree-- ; /* Compensate for nsu == -1/2 */
/* Calculate next nsL */
nsnextdegree = nsdiffdegree + nsL[nsro] ;
/* if nsnextdegree is more then 4 then code only detect that are */
/* more then 4 errors */
if ( nsnextdegree > MAXERRORS ) return 5 ;
if ( nsL[nsu+1] > nsnextdegree ) nsL[nsu+2] = nsL[nsu+1] ;
else nsL[nsu+2] = nsnextdegree ;
/* Calculate next nsSigma */
for ( nsi = 0 ; nsi < nsdiffdegree-1 ; nsi++ )
nsSigma[nsu+2][nsi] = nsSigma[nsu+1][nsi] ;
nsSigma[nsu+2][nsdiffdegree-1] =
nsSigma[nsu+1][nsdiffdegree-1] ^ nsdudro ;
for ( nsi = nsdiffdegree ; nsi < nsL[nsro]+nsdiffdegree ; nsi++ )
nsSigma[nsu+2][nsi] = nsSigma[nsu+1][nsi] ^
ECC_BCH_Mul( nsSigma[nsro][nsi - nsdiffdegree], nsdudro ) ;
for ( nsi = nsL[nsro] + nsdiffdegree ; nsi < nsL[nsu+1] ; nsi++ )
nsSigma[nsu+2][nsi] = nsSigma[nsu+1][nsi] ;
}
else /* if ( nsd[nsu] ) */
{
for ( nsi = 0 ; nsi < nsL[nsu+1] ; nsi++ )
nsSigma[nsu+2][nsi] = nsSigma[nsu+1][nsi] ;
nsL[nsu+2] = nsL[nsu+1] ;
}
if ( nsu < MAXERRORS - 1 ) /* Calculate next discrepancy factor */
{
/* Calculate next nsdiff, 2 nsu - l nsu */
nsdiff[nsu+2] = ( ( nsu + 1 ) << 1 ) - nsL[nsu+2] ;
/* Calculate next nsd */
nsSind = ( nsu << 1 ) + 3 ;
nstemp = nsS[nsSind] ;
for ( nsi = 0 ; nsi < nsL[nsu+2] ; nsi++ )
nstemp ^= ECC_BCH_Mul(nsSigma[nsu+2][nsi], nsS[nsSind-nsi-1] ) ;
nsd[nsu+2] = nstemp ;
}
} ; /* next nsu */
for ( nsi = 0 ; nsi < nsL[nsu+1] ; nsi++ )
nsLocator[nsi] = nsSigma[nsL[nsu+1]+1][nsi] ;
return nsL[nsu+1] ; /* Number of errors */
}
/* ------------------------------------------------------------------------- */
/* */
/* Functions that calculate roots of polynomial */
/* of 2-4 degree in GF(2) field. */
/* */
/* Written by Boris Dolgunov and Itai Dror */
/* Fortress Security Division, Omer */
/* M - Systems, Flash Disk Pioneers */
/* borisd@m-sys.com */
/* */
/* version 1.0, Feb. 2, 2002 */
/* */
/* ------------------------------------------------------------------------- */
/* */
/* */
/* function: FLSNative ECC_SQRT( FLSNative nsA ) */
/* */
/* */
/* description: */
/* */
/* Calculate square root polynomial */
/* */
/* Input: */
/* nsA - finite field element */
/* */
/* returned value - */
/* */
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -