mtd/nand/nand_ecc.c: replace bitsperbyte table by a simple operation
Subsystems (2)
PATCH 1/1 mtd/nand/nand_ecc.c: replace bitsperbyte table by a simple operation
--- drivers/mtd/nand/nand_ecc.c | 50 +++++++++--------------------------------- 1 files changed, 11 insertions(+), 39 deletions(-)
drivers/mtd/nand/nand_ecc.c +11 -39
@@ -85,30 +85,6 @@ static const char invparity[256] = { };/* -* bitsperbyte contains the number of bits per byte -* this is only used for testing and repairing parity -* (a precalculated value slightly improves performance) -*/ -static const char bitsperbyte[256 ] = { -0 ,1 ,1 ,2 ,1 ,2 ,2 ,3 ,1 ,2 ,2 ,3 ,2 ,3 ,3 ,4 , -1 ,2 ,2 ,3 ,2 ,3 ,3 ,4 ,2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 , -1 ,2 ,2 ,3 ,2 ,3 ,3 ,4 ,2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 , -2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 , -1 ,2 ,2 ,3 ,2 ,3 ,3 ,4 ,2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 , -2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 , -2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 , -3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,4 ,5 ,5 ,6 ,5 ,6 ,6 ,7 , -1 ,2 ,2 ,3 ,2 ,3 ,3 ,4 ,2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 , -2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 , -2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 , -3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,4 ,5 ,5 ,6 ,5 ,6 ,6 ,7 , -2 ,3 ,3 ,4 ,3 ,4 ,4 ,5 ,3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 , -3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,4 ,5 ,5 ,6 ,5 ,6 ,6 ,7 , -3 ,4 ,4 ,5 ,4 ,5 ,5 ,6 ,4 ,5 ,5 ,6 ,5 ,6 ,6 ,7 , -4 ,5 ,5 ,6 ,5 ,6 ,6 ,7 ,5 ,6 ,6 ,7 ,6 ,7 ,7 ,8 , -}; - -/* * addressbits is a lookup table to filter out the bits from the xor-ed * ECC data that identify the faulty location. * this is only used for repairing parity
@@ -448,12 +424,14 @@ int __nand_correct_data(unsigned char *buf,unsigned int byte_addr;/* 256 or 512 bytes/ecc */ const uint32_t eccsize_mult = eccsize >>8 ; +const uint32_t check_mask = eccsize_mult ==2 ?0x555555 :0x545555 ; +uint32_t tmp;/* * b0 to b2 indicate which bit is faulty (if any) * we might need the xor result more than once, * so keep them in a local var -*/ +*/ #ifdef CONFIG_MTD_NAND_ECC_SMC b0 = read_ecc[0 ] ^ calc_ecc[0 ]; b1 = read_ecc[1 ] ^ calc_ecc[1 ];
@@ -467,14 +445,11 @@ int __nand_correct_data(unsigned char *buf,/* repeated if statements are slightly more efficient than switch ... */ /* ordered in order of likelihood */ - -if ((b0 | b1 | b2) ==0 ) + tmp = ((uint32_t )b2 <<16 ) | ((uint32_t )b1 <<8 ) | b0; +if (tmp ==0 )return 0 ;/* no error */ -if ((((b0 ^ (b0 >>1 )) &0x55 ) ==0x55 ) && - (((b1 ^ (b1 >>1 )) &0x55 ) ==0x55 ) && - ((eccsize_mult ==1 && ((b2 ^ (b2 >>1 )) &0x54 ) ==0x54 ) || - (eccsize_mult ==2 && ((b2 ^ (b2 >>1 )) &0x55 ) ==0x55 ))) { +if (((tmp ^ (tmp >>1 )) & check_mask) == check_mask) {/* single bit error */ /* * rp17/rp15/13/11/9/7/5/3/1 indicate which byte is the faulty
@@ -492,19 +467,16 @@ int __nand_correct_data(unsigned char *buf,* We could also do addressbits[b2] >> 1 but for the * performance it does not make any difference */ -if (eccsize_mult ==1 ) - byte_addr = (addressbits[b1] <<4 ) + addressbits[b0]; -else - byte_addr = (addressbits[b2 &0x3 ] <<8 ) + - (addressbits[b1] <<4 ) + addressbits[b0]; + byte_addr = (addressbits[b1] <<4 ) + addressbits[b0]; +if (eccsize_mult ==2 ) + byte_addr += (addressbits[b2 &0x3 ] <<8 ); bit_addr = addressbits[b2 >>2 ];/* flip the bit */ buf[byte_addr] ^= (1 << bit_addr);return 1 ; - } -/* count nr of bits; use table lookup, faster than calculating it */ -if ((bitsperbyte[b0] + bitsperbyte[b1] + bitsperbyte[b2]) ==1 ) + +if (!(tmp & (tmp -1 )))return 1 ;/* error in ECC data; no action needed */ printk (KERN_ERR "uncorrectable error : " );
Signature · 1 line
1.7.7.6
Quoted 2 lines · Zhaoxiu Zeng
Signed-off-by Zhaoxiu Zeng <[email protected]>
In two different instances, the code you delete says that using the lookup table is a performance win, yet you don't write a commit log saying anything about this (or the rest of the changes) at all?
Paul.
--
Quoted 108 lines
---
drivers/mtd/nand/nand_ecc.c | 50 +++++++++---------------------------------1 files changed, 11 insertions(+), 39 deletions(-)drivers/mtd/nand/nand_ecc.c +5
-27@@ -85,30 +85,6 @@ static const char invparity[256] = { }; /* -* bitsperbyte contains the number of bits per byte -* this is only used for testing and repairing parity -* (a precalculated value slightly improves performance) -*/ -static const char bitsperbyte[256 ] = { - 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, - 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, - 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, - 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, - 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, - 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, -}; - -/* * addressbits is a lookup table to filter out the bits from the xor-ed * ECC data that identify the faulty location. * this is only used for repairing parity @@ -448,12 +424,14 @@ int __nand_correct_data(unsigned char *buf, unsigned int byte_addr; /* 256 or 512 bytes/ecc */ const uint32_t eccsize_mult = eccsize >> 8; + const uint32_t check_mask = eccsize_mult == 2 ? 0x555555 : 0x545555; + uint32_t tmp; /* * b0 to b2 indicate which bit is faulty (if any) * we might need the xor result more than once, * so keep them in a local var - */ + */ #ifdef CONFIG_MTD_NAND_ECC_SMC b0 = read_ecc[0] ^ calc_ecc[0]; b1 = read_ecc[1] ^ calc_ecc[1];@@ -467,14 +445,11 @@ int __nand_correct_data(unsigned char *buf, /* repeated if statements are slightly more efficient than switch ... */ /* ordered in order of likelihood */ - - if ((b0 | b1 | b2) == 0) + tmp = ((uint32_t)b2 << 16) | ((uint32_t)b1 << 8) | b0; + if (tmp == 0)return 0; /* no error */
- if ((((b0 ^ (b0 >> 1)) &
0x55) ==0x55) &&
- (((b1 ^ (b1 >> 1)) &0x55) ==0x55) &&
- ((eccsize_mult== 1 && ((b2 ^ (b2 >> 1)) &0x54) ==0x54) ||
- (eccsize_mult == 2 && ((b2 ^ (b2 >> 1)) &0x55) ==0x55))) {
+ if (((tmp ^ (tmp >> 1)) &check_mask) ==check_mask) {
/* single bit error */
/*
* rp17/rp15/13/11/9/7/5/3/1 indicate which byte is the faultydrivers/mtd/nand/nand_ecc.c +5
-8@@ -492,19 +467,16 @@ int __nand_correct_data(unsigned char *buf,* We could also do addressbits[b2] >> 1 but for the * performance it does not make any difference */ - if (eccsize_mult == 1) - byte_addr = (addressbits[b1] << 4) + addressbits[b0]; - else - byte_addr = (addressbits[b2 & 0x3] << 8) + - (addressbits[b1] << 4) + addressbits[b0]; + byte_addr = (addressbits[b1] << 4) + addressbits[b0]; + if (eccsize_mult == 2) + byte_addr += (addressbits[b2 & 0x3] << 8); bit_addr = addressbits[b2 >> 2]; /* flip the bit */ buf[byte_addr] ^= (1 << bit_addr); return 1; - } - /* count nr of bits; use table lookup, faster than calculating it */ - if ((bitsperbyte[b0] + bitsperbyte[b1] + bitsperbyte[b2]) == 1) + + if (!(tmp & (tmp - 1)))return 1; /* error in ECC data; no action needed */
printk(KERN_ERR "uncorrectable error : ");
--
1.7.7.6--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Dear Zhaoxiu
Thanks for contributing this patch.
However, I think it has some issues and should not be applied. See my remarks below
2012/3/24 Zhaoxiu Zeng <[email protected]>:
Quoted 59 lines
Signed-off-by Zhaoxiu Zeng <[email protected]>---
drivers/mtd/nand/nand_ecc.c | 50 +++++++++---------------------------------1 files changed, 11 insertions(+), 39 deletions(-)drivers/mtd/nand/nand_ecc.c +3
-25@@ -85,30 +85,6 @@ static const char invparity[256] = { }; /* -* bitsperbyte contains the number of bits per byte -* this is only used for testing and repairing parity -* (a precalculated value slightly improves performance) -*/ -static const char bitsperbyte[256 ] = { - 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, - 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, - 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, - 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, - 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, - 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, -}; - -/* * addressbits is a lookup table to filter out the bits from the xor-ed * ECC data that identify the faulty location. * this is only used for repairing parity @@ -448,12 +424,14 @@ int __nand_correct_data(unsigned char *buf, unsigned int byte_addr; /* 256 or 512 bytes/ecc */ const uint32_t eccsize_mult = eccsize >> 8; + const uint32_t check_mask = eccsize_mult == 2 ? 0x555555 : 0x545555; + uint32_t tmp; /* * b0 to b2 indicate which bit is faulty (if any) * we might need the xor result more than once, * so keep them in a local var - */ + */ #ifdef CONFIG_MTD_NAND_ECC_SMC b0 = read_ecc[0] ^ calc_ecc[0]; b1 = read_ecc[1] ^ calc_ecc[1];
drivers/mtd/nand/nand_ecc.c int __nand_correct_data(unsigned char *buf, · line 448
Quoted 6 lines
drivers/mtd/nand/nand_ecc.c +1
-2@@ -467,14 +445,11 @@ int __nand_correct_data(unsigned char *buf, /* repeated if statements are slightly more efficient than switch ... */ /* ordered in order of likelihood */ - - if ((b0 | b1 | b2) == 0) + tmp = ((uint32_t)b2 << 16) | ((uint32_t)b1 << 8) | b0;
Not sure how efficient this is; on some systems shifting by N takes N clock cycles so this could be relatively expensive.
(and the systems where it takes more clock cycles have a higher chance on not having hw crc correction).
Quoted 8 lines
drivers/mtd/nand/nand_ecc.c +1
-0+ if (tmp == 0)return 0; /* no error */
- if ((((b0 ^ (b0 >> 1)) &
0x55) ==0x55) &&
- (((b1 ^ (b1 >> 1)) &0x55) ==0x55) &&
- ((eccsize_mult== 1 && ((b2 ^ (b2 >> 1)) &0x54) ==0x54) ||
- (eccsize_mult == 2 && ((b2 ^ (b2 >> 1)) &0x55) ==0x55))) {
+ if (((tmp ^ (tmp >> 1)) &check_mask) ==check_mask) {
Have you benchmarked this?
And while it might be an optimisation, it is not mentioned in the commit message.
Quoted 5 lines
/* single bit error */
/*
* rp17/rp15/13/11/9/7/5/3/1 indicate which byte is the faultydrivers/mtd/nand/nand_ecc.c +0
-0@@ -492,19 +467,16 @@ int __nand_correct_data(unsigned char *buf, * We could also do addressbits[b2] >> 1 but for the
drivers/mtd/nand/nand_ecc.c int __nand_correct_data(unsigned char *buf, · line 472
Quoted 10 lines
drivers/mtd/nand/nand_ecc.c +3
-5* performance it does not make any difference */ - if (eccsize_mult == 1) - byte_addr = (addressbits[b1] << 4) + addressbits[b0]; - else - byte_addr = (addressbits[b2 & 0x3] << 8) + - (addressbits[b1] << 4) + addressbits[b0]; + byte_addr = (addressbits[b1] << 4) + addressbits[b0]; + if (eccsize_mult == 2) + byte_addr += (addressbits[b2 & 0x3] << 8);
I'm not sure if this is a win. It *looks* like an optimisation since you factor out some common code. Then again within the if you need to add to byte_addr.
For a naive compiler this is probably more expensive. For a good compiler this probably makes no difference at all.
drivers/mtd/nand/nand_ecc.c int __nand_correct_data(unsigned char *buf, · line 479
Quoted 10 lines
drivers/mtd/nand/nand_ecc.c +2
-3bit_addr = addressbits[b2 >> 2]; /* flip the bit */ buf[byte_addr] ^= (1 << bit_addr); return 1; - } - /* count nr of bits; use table lookup, faster than calculating it */ - if ((bitsperbyte[b0] + bitsperbyte[b1] + bitsperbyte[b2]) == 1) + + if (!(tmp & (tmp - 1)))
This is not the same as the code you replace!!!
take as example b0 = 1; b1 =0, b2 = 0;
The original if statement will return true:
bitsperbyte[b0] in that case is 1
bitsperbyte[b1] = 0
bitsperbyte[b2] = 0
so (bitsperbyte[b0] + bitsperbyte[b1] + bitsperbyte[b2]) equals 1 and ((bitsperbyte[b0] + bitsperbyte[b1] + bitsperbyte[b2]) == 1) yields 1 so true
However if I take your code
tmp = ((uint32_t)b2 << 16) | ((uint32_t)b1 << 8) | b0; taking the example values from above this results in tmp being 1; tmp & (tmp - 1) becomes 1 & 0 which effectively results in 0.
So in my original code b0 = 1; b1 =0, b2 = 0; results in 1 being returned whereas your code will result in a log entry "incorrectable error" and a return of -1.
Given this, I'd say this patch is to be rejected.
BTW: optimisations in this part of code are not too important. This is only called when ecc errors are to be corrected and that is not very likely.
So perhaps it is not worth the time to improve it.
(and yes, it might be possible to save some bytes by eliminating the array; then again the code and logic is not really trivial so good testing is needed)
See also Documentation/mtd/nand_ecc.txt
near the end there is a small section on correcting.
Quoted 7 lines
return 1; /* error in ECC data; no action needed */
printk(KERN_ERR "uncorrectable error : ");
--
1.7.7.6
Best regards, Frans.