lkml.org 
[lkml]   [2008]   [Dec]   [25]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 22/35] ocfs2: Don't hand-code xor in ocfs2_hamming_encode().
    Date
    From: Joel Becker <joel.becker@oracle.com>

    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>
    ---
    fs/ocfs2/blockcheck.c | 67 ++++++++++++++----------------------------------
    1 files changed, 20 insertions(+), 47 deletions(-)

    diff --git a/fs/ocfs2/blockcheck.c b/fs/ocfs2/blockcheck.c
    index 2ce6ae5..1d5083c 100644
    --- a/fs/ocfs2/blockcheck.c
    +++ b/fs/ocfs2/blockcheck.c
    @@ -31,7 +31,6 @@
    #include "blockcheck.h"


    -
    /*
    * We use the following conventions:
    *
    @@ -39,26 +38,6 @@
    * 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
    @@ -109,10 +88,9 @@ static unsigned int calc_code_bit(unsigned int i)
    */
    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;

    - BUG_ON(!p);
    + BUG_ON(!d);

    /*
    * 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
    */
    b = calc_code_bit(nr + i);

    - 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
    @@ -174,10 +148,9 @@ u32 ocfs2_hamming_encode_block(void *data, unsigned int blocksize)
    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
    --
    1.5.6


    \
     
     \ /
      Last update: 2008-12-25 19:15    [W:0.034 / U:0.444 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site