#include "blockcheck.h"
-
/*
* We use the following conventions:
*
* p = # parity bits
* c = # total code bits (d + p)
*/
-static int calc_parity_bits(unsigned int d)
-{
- unsigned int p;
-
- /*
- * Bits required for Single Error Correction is as follows:
- *
- * d + p + 1 <= 2^p
- *
- * We're restricting ourselves to 31 bits of parity, that should be
- * sufficient.
- */
- for (p = 1; p < 32; p++)
- {
- if ((d + p + 1) <= (1 << p))
- return p;
- }
- return 0;
-}
/*
* Calculate the bit offset in the hamming code buffer based on the bit's
* so it's a parity bit. 2 is a power of two (2^1), so it's a parity bit.
* 3 is not a power of two. So bit 1 of the data buffer ends up as bit 3
* in the code buffer.
+ *
+ * The caller can pass in *p if it wants to keep track of the most recent
+ * number of parity bits added. This allows the function to start the
+ * calculation at the last place.
*/
-static unsigned int calc_code_bit(unsigned int i)
+static unsigned int calc_code_bit(unsigned int i, unsigned int *p_cache)
{
- unsigned int b, p;
+ unsigned int b, p = 0;
/*
* Data bits are 0-based, but we're talking code bits, which
*/
b = i + 1;
+ /* Use the cache if it is there */
+ if (p_cache)
+ p = *p_cache;
+ b += p;
+
/*
* For every power of two below our bit number, bump our bit.
*
- * We compare with (b + 1) becuase we have to compare with what b
+ * We compare with (b + 1) because we have to compare with what b
* would be _if_ it were bumped up by the parity bit. Capice?
+ *
+ * p is set above.
*/
- for (p = 0; (1 << p) < (b + 1); p++)
+ for (; (1 << p) < (b + 1); p++)
b++;
+ if (p_cache)
+ *p_cache = p;
+
return b;
}
*/
u32 ocfs2_hamming_encode(u32 parity, void *data, unsigned int d, unsigned int nr)
{
- unsigned int p = calc_parity_bits(nr + d);
- unsigned int i, j, b;
+ unsigned int i, b, p = 0;
- BUG_ON(!p);
+ BUG_ON(!d);
/*
* b is the hamming code bit number. Hamming code specifies a
* i is the offset in this hunk, nr + i is the total bit
* offset.
*/
- b = calc_code_bit(nr + i);
+ b = calc_code_bit(nr + i, &p);
- for (j = 0; j < p; j++)
- {
- /*
- * Data bits in the resultant code are checked by
- * parity bits that are part of the bit number
- * representation. Huh?
- *
- * <wikipedia href="http://en.wikipedia.org/wiki/Hamming_code">
- * In other words, the parity bit at position 2^k
- * checks bits in positions having bit k set in
- * their binary representation. Conversely, for
- * instance, bit 13, i.e. 1101(2), is checked by
- * bits 1000(2) = 8, 0100(2)=4 and 0001(2) = 1.
- * </wikipedia>
- *
- * Note that 'k' is the _code_ bit number. 'b' in
- * our loop.
- */
- if (b & (1 << j))
- parity ^= (1 << j);
- }
+ /*
+ * Data bits in the resultant code are checked by
+ * parity bits that are part of the bit number
+ * representation. Huh?
+ *
+ * <wikipedia href="http://en.wikipedia.org/wiki/Hamming_code">
+ * In other words, the parity bit at position 2^k
+ * checks bits in positions having bit k set in
+ * their binary representation. Conversely, for
+ * instance, bit 13, i.e. 1101(2), is checked by
+ * bits 1000(2) = 8, 0100(2)=4 and 0001(2) = 1.
+ * </wikipedia>
+ *
+ * Note that 'k' is the _code_ bit number. 'b' in
+ * our loop.
+ */
+ parity ^= b;
}
/* While the data buffer was treated as little endian, the
void ocfs2_hamming_fix(void *data, unsigned int d, unsigned int nr,
unsigned int fix)
{
- unsigned int p = calc_parity_bits(nr + d);
unsigned int i, b;
- BUG_ON(!p);
+ BUG_ON(!d);
/*
* If the bit to fix has an hweight of 1, it's a parity bit. One
* nr + d is the bit right past the data hunk we're looking at.
* If fix after that, nothing to do
*/
- if (fix >= calc_code_bit(nr + d))
+ if (fix >= calc_code_bit(nr + d, NULL))
return;
/*
* start b at the offset in the code buffer. See hamming_encode()
* for a more detailed description of 'b'.
*/
- b = calc_code_bit(nr);
+ b = calc_code_bit(nr, NULL);
/* If the fix is before this hunk, nothing to do */
if (fix < b)
return;
projects / linux-2.6-omap-h63xx.git / blobdiff