📄 bch_hm.c
字号:
/* */
/* description: */
/* */
/* Fast calculation of discrete log over GF(2^14), */
/* Log is searched from the end to the begining */
/* */
/* Perfomance in accelerated by flat coding the function */
/* */
/* Input: */
/* */
/* nsbeta - A 14 bits finite field polynomial in GF(2^14) */
/* */
/* retuned value - Log(nsbeta), such that, alfa ^ (Log(nsbeta)) = nsbeta */
/* */
/* wPowerTable1, wPowerTable2 and wAlfajmNeg are global constants arrays */
/* */
/* */
static FLSNative ECC_BCH_LogDown(FLSNative nsbeta)
{
FLSNative nsi = 63 ; /* Giant step iterator */
FLSNative nsj ; /* Baby step iterator */
FLSNative nsbetaalfa ; /* Discrete log ( element in GF( 2 ^ 14 ) ) */
while ( nsi >= 0 ) /* Giant step iteration starting from the end */
{
nsbetaalfa = ECC_BCH_Mul(nsbeta, wAlfajmNeg[nsi]) ; /* Giant step */
nsj = 128 ; /* Initial value for Baby step ( binary search ) */
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 1'st search */
nsj = nsj + 64 ;
else
nsj = nsj - 64 ;
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 2'nd search */
nsj = nsj + 32 ;
else
nsj = nsj - 32 ;
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 3'rd search */
nsj = nsj + 16 ;
else
nsj = nsj - 16 ;
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 4'th search */
nsj = nsj + 8 ;
else
nsj = nsj - 8 ;
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 5'th search */
nsj = nsj + 4 ;
else
nsj = nsj - 4 ;
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 6'th search */
nsj = nsj + 2 ;
else
nsj = nsj - 2 ;
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 7'th search */
nsj = nsj + 1 ;
else
nsj = nsj - 1 ;
/* End of baby step search */
/* Decide if Log found and return Log in case of a match */
if ( nsbetaalfa == wPowerTable1[nsj] )
return wPowerTable2[nsj] + nsi * 256 ;
if ( nsbetaalfa == wPowerTable1[nsj-1] )
return wPowerTable2[nsj-1] + nsi * 256 ;
nsi-- ;
}
return 0 ;
}
/* ------------------------------------------------------------------------- */
/* */
/* function: FLSNative ECC_BCH_LogUp(FLSNative beta) */
/* */
/* description: */
/* */
/* Fast calculation of discrete log over GF(2^14) */
/* Log is searched from the begining to the end. */
/* */
/* Performance in accelerated by flat coding the function. */
/* */
/* Input: */
/* */
/* nsbeta - A 14 bits finite field polynomial in GF(2^14) */
/* */
/* retuned value - Log(nsbeta), such that, alfa ^ (Log(nsbeta)) = nsbeta */
/* */
/* wPowerTable1, wPowerTable2 and wAlfajmNeg are global constants arrays */
/* */
/* */
static FLSNative ECC_BCH_LogUp(FLSNative nsbeta)
{
FLSNative nsi = 0 ; /* Giant step iterator */
FLSNative nsj ; /* Baby step iterator */
FLSNative nsbetaalfa ; /* Discrete log ( element in GF( 2 ^ 14 ) ) */
while ( nsi < 64 ) /* Giant step iteration from the end */
{
if ( nsi == 0 ) /* No need for finite field multiplication */
nsbetaalfa = nsbeta ;
else
nsbetaalfa = ECC_BCH_Mul(nsbeta, wAlfajmNeg[nsi]) ; /* Giant step */
nsj = 128 ; /* Initial value for Baby step ( binary search ) */
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 1'st search */
nsj = nsj + 64 ;
else
nsj = nsj - 64 ;
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 2'nd search */
nsj = nsj + 32 ;
else
nsj = nsj - 32 ;
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 3'rd search */
nsj = nsj + 16 ;
else
nsj = nsj - 16 ;
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 4'th search */
nsj = nsj + 8 ;
else
nsj = nsj - 8 ;
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 5'th search */
nsj = nsj + 4 ;
else
nsj = nsj - 4 ;
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 6'th search */
nsj = nsj + 2 ;
else
nsj = nsj - 2 ;
if ( nsbetaalfa >= wPowerTable1[nsj] ) /* 7'th search */
nsj = nsj + 1 ;
else
nsj = nsj - 1 ;
/* End of baby step search */
/* Decide if Log found and return Log in case of a match */
if ( nsbetaalfa == wPowerTable1[nsj] )
return wPowerTable2[nsj] + nsi * 256 ;
if ( nsbetaalfa == wPowerTable1[nsj-1] )
return wPowerTable2[nsj-1] + nsi * 256 ;
nsi++ ;
}
return 0 ;
}
/* ------------------------------------------------------------------------- */
/* */
/* function: FLSNative ECC_BCH_Mul(FLSNative nsa, FLSNative nsb) */
/* */
/* description: */
/* */
/* Fast finite field multiplication of GF(2^14) finite field elements */
/* */
/* Performance in accelerated by flat coding the function */
/* */
/* Input: */
/* */
/* nsa - The multiplier, a 14 bits finite field element in GF(2^14) */
/* */
/* nsb - The multiplicand, a 14 bits finite field element in GF(2^14) */
/* */
/* Returned value : */
/* */
/* nsa * nsb mod p(X) */
/* */
/* Global variable: wFi1Table[] constant array */
/* */
static FLSNative ECC_BCH_Mul(FLSNative nsa, FLSNative nsb)
{
FLNative nm = 0 ; /* Initial value of result */
/* This multiplication function runs faster when at least 32 bits compiler */
/* is avialiable and wo'nt work under 16 bits compiler */
#ifndef FL_ASSUME_NATIVE_IS_32BITS
if ( nsa & 0x0001 ) nm ^= nsb ; /* 1'st multiplier bit */
nm = nm & 0x0001 ? Px ^ ( nm >> 1 ) : nm >> 1 ; /* 2'nd multiplier bit */
if ( nsa & 0x0002 ) nm ^= nsb ;
nm = nm & 0x0001 ? Px ^ ( nm >> 1 ) : nm >> 1 ; /* 3'rd multiplier bit */
if ( nsa & 0x0004 ) nm ^= nsb ;
nm = nm & 0x0001 ? Px ^ ( nm >> 1 ) : nm >> 1 ; /* 4'th multiplier bit */
if ( nsa & 0x0008 ) nm ^= nsb ;
nm = nm & 0x0001 ? Px ^ ( nm >> 1 ) : nm >> 1 ; /* 5'th multiplier bit */
if ( nsa & 0x0010 ) nm ^= nsb ;
nm = nm & 0x0001 ? Px ^ ( nm >> 1 ) : nm >> 1 ; /* 6'th multiplier bit */
if ( nsa & 0x0020 ) nm ^= nsb ;
nm = nm & 0x0001 ? Px ^ ( nm >> 1 ) : nm >> 1 ; /* 7'th multiplier bit */
if ( nsa & 0x0040 ) nm ^= nsb ;
nm = nm & 0x0001 ? Px ^ ( nm >> 1 ) : nm >> 1 ; /* 8'th multiplier bit */
if ( nsa & 0x0080 ) nm ^= nsb ;
nm = nm & 0x0001 ? Px ^ ( nm >> 1 ) : nm >> 1 ; /* 9'th multiplier bit */
if ( nsa & 0x0100 ) nm ^= nsb ;
nm = nm & 0x0001 ? Px ^ ( nm >> 1 ) : nm >> 1 ; /* 10'th multiplier bit */
if ( nsa & 0x0200 ) nm ^= nsb ;
nm = nm & 0x0001 ? Px ^ ( nm >> 1 ) : nm >> 1 ; /* 11'th multiplier bit */
if ( nsa & 0x0400 ) nm ^= nsb ;
nm = nm & 0x0001 ? Px ^ ( nm >> 1 ) : nm >> 1 ; /* 12'th multiplier bit */
if ( nsa & 0x0800 ) nm ^= nsb ;
nm = nm & 0x0001 ? Px ^ ( nm >> 1 ) : nm >> 1 ; /* 13'th multiplier bit */
if ( nsa & 0x1000 ) nm ^= nsb ;
nm = nm & 0x0001 ? Px ^ ( nm >> 1 ) : nm >> 1 ; /* 14'th multiplier bit */
if ( nsa & 0x2000 ) nm ^= nsb ;
#else /* FL_ASSUME_NATIVE_IS_32BITS */
/* This multiplication function will run under any ANSI C compiler */
if ( nsa & 0x0001 ) nm ^= nsb ; /* 1'st multiplier bit */
if ( nsa & 0x0002 ) nm ^= ( nsb << 1 ) ; /* 2'nd multiplier bit */
if ( nsa & 0x0004 ) nm ^= ( nsb << 2 ) ; /* 3'rd multiplier bit */
if ( nsa & 0x0008 ) nm ^= ( nsb << 3 ) ; /* 4'th multiplier bit */
if ( nsa & 0x0010 ) nm ^= ( nsb << 4 ) ; /* 5'th multiplier bit */
if ( nsa & 0x0020 ) nm ^= ( nsb << 5 ) ; /* 6'th multiplier bit */
if ( nsa & 0x0040 ) nm ^= ( nsb << 6 ) ; /* 7'th multiplier bit */
if ( nsa & 0x0080 ) nm ^= ( nsb << 7 ) ; /* 8'th multiplier bit */
if ( nsa & 0x0100 ) nm ^= ( nsb << 8 ) ; /* 9'th multiplier bit */
if ( nsa & 0x0200 ) nm ^= ( nsb << 9 ) ; /* 10'th multiplier bit */
if ( nsa & 0x0400 ) nm ^= ( nsb << 10 ) ; /* 11'th multiplier bit */
if ( nsa & 0x0800 ) nm ^= ( nsb << 11 ) ; /* 12'th multiplier bit */
if ( nsa & 0x1000 ) nm ^= ( nsb << 12 ) ; /* 13'th multiplier bit */
if ( nsa & 0x2000 ) nm ^= ( nsb << 13 ) ; /* 14'th multiplier bit */
/* Perform modulo operation */
nm = ( nm >> 8 ) ^ wFi1Table[ ( FLByte ) nm ] ;
nm = ( nm >> 5 ) ^ wFi1Table[ 0x00f8 & ( nm << 3 ) ] ;
#endif /* FL_ASSUME_NATIVE_IS_32BITS */
return (FLSNative) nm ;
}
/* ------------------------------------------------------------------------- */
/* function: FLSNative ECC_BCH_Inv(FLSNative a) */
/* */
/* description: */
/* */
/* Fast finite field inversion of a GF(2^14) finite field element */
/* */
/* Input: */
/* */
/* nsa - A 14 bits finite field element in GF(2^14) */
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -