aboutsummaryrefslogtreecommitdiffstats
path: root/fs/ocfs2/blockcheck.c
diff options
context:
space:
mode:
authorJoel Becker <joel.becker@oracle.com>2008-12-15 20:13:48 -0500
committerMark Fasheh <mfasheh@suse.com>2009-01-05 11:40:34 -0500
commite798b3f8a920c82a8e556dd54df97f0d3d0f9144 (patch)
tree1f9c19ba29f65e44c10d77597a746224e0e72c72 /fs/ocfs2/blockcheck.c
parent9d28cfb73f3abccce001daf2d247b16bf20e2248 (diff)
ocfs2: Don't hand-code xor in ocfs2_hamming_encode().
When I wrote ocfs2_hamming_encode(), I was following documentation of the algorithm and didn't have quite the (possibly still imperfect) grasp of it I do now. As part of this, I literally hand-coded xor. I would test a bit, and then add that bit via xor to the parity word. I can, of course, just do a single xor of the parity word and the source word (the code buffer bit offset). This cuts CPU usage by 53% on a mostly populated buffer (an inode containing utmp.h inline). Joel Signed-off-by: Joel Becker <joel.becker@oracle.com> Signed-off-by: Mark Fasheh <mfasheh@suse.com>
Diffstat (limited to 'fs/ocfs2/blockcheck.c')
-rw-r--r--fs/ocfs2/blockcheck.c67
1 files changed, 20 insertions, 47 deletions
diff --git a/fs/ocfs2/blockcheck.c b/fs/ocfs2/blockcheck.c
index 2ce6ae5e4b8c..1d5083cef3a2 100644
--- a/fs/ocfs2/blockcheck.c
+++ b/fs/ocfs2/blockcheck.c
@@ -31,7 +31,6 @@
31#include "blockcheck.h" 31#include "blockcheck.h"
32 32
33 33
34
35/* 34/*
36 * We use the following conventions: 35 * We use the following conventions:
37 * 36 *
@@ -39,26 +38,6 @@
39 * p = # parity bits 38 * p = # parity bits
40 * c = # total code bits (d + p) 39 * c = # total code bits (d + p)
41 */ 40 */
42static int calc_parity_bits(unsigned int d)
43{
44 unsigned int p;
45
46 /*
47 * Bits required for Single Error Correction is as follows:
48 *
49 * d + p + 1 <= 2^p
50 *
51 * We're restricting ourselves to 31 bits of parity, that should be
52 * sufficient.
53 */
54 for (p = 1; p < 32; p++)
55 {
56 if ((d + p + 1) <= (1 << p))
57 return p;
58 }
59
60 return 0;
61}
62 41
63/* 42/*
64 * Calculate the bit offset in the hamming code buffer based on the bit's 43 * Calculate the bit offset in the hamming code buffer based on the bit's
@@ -109,10 +88,9 @@ static unsigned int calc_code_bit(unsigned int i)
109 */ 88 */
110u32 ocfs2_hamming_encode(u32 parity, void *data, unsigned int d, unsigned int nr) 89u32 ocfs2_hamming_encode(u32 parity, void *data, unsigned int d, unsigned int nr)
111{ 90{
112 unsigned int p = calc_parity_bits(nr + d); 91 unsigned int i, b;
113 unsigned int i, j, b;
114 92
115 BUG_ON(!p); 93 BUG_ON(!d);
116 94
117 /* 95 /*
118 * b is the hamming code bit number. Hamming code specifies a 96 * b is the hamming code bit number. Hamming code specifies a
@@ -131,27 +109,23 @@ u32 ocfs2_hamming_encode(u32 parity, void *data, unsigned int d, unsigned int nr
131 */ 109 */
132 b = calc_code_bit(nr + i); 110 b = calc_code_bit(nr + i);
133 111
134 for (j = 0; j < p; j++) 112 /*
135 { 113 * Data bits in the resultant code are checked by
136 /* 114 * parity bits that are part of the bit number
137 * Data bits in the resultant code are checked by 115 * representation. Huh?
138 * parity bits that are part of the bit number 116 *
139 * representation. Huh? 117 * <wikipedia href="http://en.wikipedia.org/wiki/Hamming_code">
140 * 118 * In other words, the parity bit at position 2^k
141 * <wikipedia href="http://en.wikipedia.org/wiki/Hamming_code"> 119 * checks bits in positions having bit k set in
142 * In other words, the parity bit at position 2^k 120 * their binary representation. Conversely, for
143 * checks bits in positions having bit k set in 121 * instance, bit 13, i.e. 1101(2), is checked by
144 * their binary representation. Conversely, for 122 * bits 1000(2) = 8, 0100(2)=4 and 0001(2) = 1.
145 * instance, bit 13, i.e. 1101(2), is checked by 123 * </wikipedia>
146 * bits 1000(2) = 8, 0100(2)=4 and 0001(2) = 1. 124 *
147 * </wikipedia> 125 * Note that 'k' is the _code_ bit number. 'b' in
148 * 126 * our loop.
149 * Note that 'k' is the _code_ bit number. 'b' in 127 */
150 * our loop. 128 parity ^= b;
151 */
152 if (b & (1 << j))
153 parity ^= (1 << j);
154 }
155 } 129 }
156 130
157 /* While the data buffer was treated as little endian, the 131 /* While the data buffer was treated as little endian, the
@@ -174,10 +148,9 @@ u32 ocfs2_hamming_encode_block(void *data, unsigned int blocksize)
174void ocfs2_hamming_fix(void *data, unsigned int d, unsigned int nr, 148void ocfs2_hamming_fix(void *data, unsigned int d, unsigned int nr,
175 unsigned int fix) 149 unsigned int fix)
176{ 150{
177 unsigned int p = calc_parity_bits(nr + d);
178 unsigned int i, b; 151 unsigned int i, b;
179 152
180 BUG_ON(!p); 153 BUG_ON(!d);
181 154
182 /* 155 /*
183 * If the bit to fix has an hweight of 1, it's a parity bit. One 156 * If the bit to fix has an hweight of 1, it's a parity bit. One