www.pudn.com > efs.rar > fs_hc.c
/******************************************************************************
* fs_hc.c
*
* This function implements the Hamming Code ECC algorithm for 4 bytes
*
* Copyright (C) 2006 Qualcomm, Inc. All Rights Reserved
*
*****************************************************************************/
/*=============================================================================
EDIT HISTORY FOR MODULE
This section contains comments describing changes made to the module.
Notice that changes are listed in reverse chronological order.
$Header: //depot/asic/MSMSHARED/services/efs/MSM_EFS.01.02/fs_hc.c#1 $
$DateTime: 2006/06/08 10:00:24 $
$Author: davidb $
when who what, where, why
-------- --- ----------------------------------------------------------
2006-03-30 yg Implemented Hamming Code correction algorithm for 4 bytes
=============================================================================*/
#include "fs_hc.h"
/*
* with n bit ECC Parity bits, 2**n bits can be covered
* This implementation implements 5 bits parity.
*/
#define ECC_BIT_COUNT 5
/******************************************************************************
FUNCTION bit_count
DESCRIPTION Count number of bits set in the integer passed.
DEPENDENCIES None
RETURN VALUE Number of bits set.
******************************************************************************/
static uint16 bit_count (uint32 data)
{
uint16 temp;
data = (((data >> 1) & 0x55555555) + (data & 0x55555555));
data = (((data >> 2) & 0x33333333) + (data & 0x33333333));
data = (((data >> 4) & 0x0F0F0F0F) + (data & 0x0F0F0F0F));
data = (((data >> 8) & 0x00FF00FF) + (data & 0x00FF00FF));
temp = (((data >> 16) & 0xFFFF) + (data & 0xFFFF));
return temp;
}
/******************************************************************************
FUNCTION parity_1
DESCRIPTION Calculates the parity_1, parity_1' for the passed data
DEPENDENCIES None
RETURN VALUE parity_1, parity_1'
******************************************************************************/
static unsigned parity_1 (uint32 data)
{
uint16 par, ppar;
ppar = bit_count(data & 0x55555555);
par = bit_count(data & 0xAAAAAAAA);
return (par & 0x01) | ((ppar & 0x01) << ECC_BIT_COUNT);
}
/******************************************************************************
FUNCTION parity_2
DESCRIPTION Calculates the parity_2, parity_2' for the passed data
DEPENDENCIES None
RETURN VALUE parity_2, parity_2'
******************************************************************************/
static unsigned parity_2 (uint32 data)
{
uint16 par, ppar;
ppar = bit_count(data & 0x33333333);
par = bit_count(data & 0xCCCCCCCC);
return ((par & 0x01) << 1) | ((ppar & 0x01) << (ECC_BIT_COUNT + 1));
}
/******************************************************************************
FUNCTION parity_4
DESCRIPTION Calculates the parity_4, parity_4' for the passed data
DEPENDENCIES None
RETURN VALUE parity_4, parity_4'
******************************************************************************/
static unsigned parity_4 (uint32 data)
{
uint16 par, ppar;
ppar = bit_count(data & 0x0F0F0F0F);
par = bit_count(data & 0xF0F0F0F0);
return ((par & 0x01) << 2) | ((ppar & 0x01) << (ECC_BIT_COUNT + 2));
}
/******************************************************************************
FUNCTION parity_8
DESCRIPTION Calculates the parity_8, parity_8' for the passed data
DEPENDENCIES None
RETURN VALUE parity_8, parity_8'
******************************************************************************/
static unsigned parity_8 (uint32 data)
{
uint16 par, ppar;
ppar = bit_count(data & 0x00FF00FF);
par = bit_count(data & 0xFF00FF00);
return ((par & 0x01) << 3) | ((ppar & 0x01) << (ECC_BIT_COUNT + 3));
}
/******************************************************************************
FUNCTION parity_16
DESCRIPTION Calculates the parity_16, parity_16' for the passed data
DEPENDENCIES None
RETURN VALUE parity_16, parity_16'
******************************************************************************/
static unsigned parity_16 (uint32 data)
{
uint16 par, ppar;
ppar = bit_count(data & 0x0000FFFF);
par = bit_count(data & 0xFFFF0000);
return ((par & 0x01) << 4) | ((ppar & 0x01) << (ECC_BIT_COUNT + 4));
}
/******************************************************************************
FUNCTION hc_encode
DESCRIPTION Encode 22 bits of data passed in with Hamming code ECC
DEPENDENCIES None
RETURN VALUE 10 bits HC ECC parity data.
******************************************************************************/
uint16 hc_encode (uint32 edata)
{
uint16 par;
/* our data is divided in this manner
33222222 22221111 11111100 00000000
10987654 32109876 54321098 76543210
pppppPPP PPDDDDDD DDDDDDDD DDDDDDDD
Where:
ppppp => Parity prime (P16'P8'P4'P2'P1')
PPPPP => Parity (P16P8P4P2P1)
DD..D => Data bits
*/
/* Extract only the data part, which is 22 bits now */
edata = edata & 0x003FFFFF;
par = parity_1(edata);
par |= parity_2(edata);
par |= parity_4(edata);
par |= parity_8(edata);
par |= parity_16(edata);
/* Return the Parity and Parity Prime in the following format
xxxPPPPP xxxppppp
*/
return par;
}
/******************************************************************************
FUNCTION hc_decode
DESCRIPTION Decode the stored number after calcuating HC ECC and correcting
the data if necessary and possible.
Returns only the data without parity bytes. So is in usable form.
DEPENDENCIES MSB 10 bits being ECC that was calculated.
RETURN VALUE
DECODE_OK : If there was no error or corrected data properly
DECODE_ERROR : Error in correction (possibly multibit errors).
*dptr : Corrected data in the destination location.
******************************************************************************/
uint16 hc_decode (uint32 *dptr)
{
uint32 dat;
uint16 stored_parity, calculated_parity, parity_diff, result = DECODE_OK;
stored_parity = (*dptr) >> 22;
*dptr = *dptr & 0x003FFFFF;
dat = *dptr;
calculated_parity = hc_encode(dat);
parity_diff = stored_parity ^ calculated_parity;
if (parity_diff == 0)
{
return result;
}
switch (bit_count(parity_diff))
{
case ECC_BIT_COUNT:
{
int pos;
pos = parity_diff & ((1 << ECC_BIT_COUNT) - 1);
*dptr = dat ^ (1 << pos);
}
break;
case 1:
/* 1 bit error in ECC data only so its still ok */
break;
default:
/* Multiple errors cannot fix... fatal case... */
result = DECODE_ERROR;
break;
} /* Switch */
return result;
}
#ifdef HC_TEST
/******************************************************************************
FUNCTION main
DESCRIPTION Test run on PC
When this test is run, there should be no messages printed
on the output. If any errors occurred, then the algorithm is
not working. Define SIM while compiling..
DEPENDENCIES SIM should be defined in the command line while compiling
RETURN VALUE Number of errors
******************************************************************************/
int main(int argc, char* argv[])
{
uint16 par, res;
uint32 i, ul, j, k, mod, errors;
errors = 0;
for (i=0x0; i < (1 << 22); ++i) /* for 22 bits */
{
ul = i;
par = hc_encode(ul);
ul = ul | (par << 22);
for (j=0; j < 32; ++j)
{
mod = ul ^ (1 << j); /* Introduce 1 bit error */
res = hc_decode(&mod);
/* Check if corrected to original data */
if (res != DECODE_OK)
{
printf("FATAL Error in decoding\n");
errors++;
}
else
{
if (mod != i)
{
printf("FATAL Error in correction\n");
errors++;
}
}
for (k=j+1; k < 32; ++k)
{
/* Now introduce 2 bit errors */
mod = ul ^ ((1 << j) | (1 << k));
if (hc_decode(&mod) != DECODE_ERROR)
{
printf("FATAL: Incorrectly corrected 2 bit error...!!\n");
errors++;
}
#ifdef CHECK_3_BIT_ERRORS
/* 3 bit errors would appear as a wrongly corrected data... */
for (l=k+1; l<32; ++l)
{
/* Introduce 3 bit errors */
mod = ul ^ ((1 << j) | (1 << k) | (1 << l));
if (hc_decode(&mod) != DECODE_ERROR)
{
printf("FATAL: Incorrect correction for 3 bit error "
"%8X %2d %2d %2d\n", i, j, k, l);
errors++;
}
}
#endif /* CHECK_3_BIT_ERRORS */
}
}
}
if (errors == 0)
{
printf("Test completed successfully without any errors....\n");
}
return errors;
}
#endif