path: root/utility/hamming.c

/* ----------------------------------------------------------------------------
 *         ATMEL Microcontroller Software Support 
 * ----------------------------------------------------------------------------
 * Copyright (c) 2008, Atmel Corporation
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * - Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the disclaimer below.
 *
 * Atmel's name may not be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * DISCLAIMER: THIS SOFTWARE IS PROVIDED BY ATMEL "AS IS" AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT ARE
 * DISCLAIMED. IN NO EVENT SHALL ATMEL BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * ----------------------------------------------------------------------------
 */

//------------------------------------------------------------------------------
//         Headers
//------------------------------------------------------------------------------

#include "hamming.h"
#include <utility/trace.h>
#include <utility/assert.h>

//------------------------------------------------------------------------------
//         Internal function
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
/// Counts and return the number of bits set to '1' in the given byte.
/// \param byte  Byte to count.
//------------------------------------------------------------------------------
static unsigned char CountBitsInByte(unsigned char byte)
{
    unsigned char count = 0;
    while (byte > 0) {

        if (byte & 1) {

            count++;
        }
        byte >>= 1;
    }

    return count;
}

//------------------------------------------------------------------------------
/// Counts and return the number of bits set to '1' in the given hamming code.
/// \param code  Hamming code.
//------------------------------------------------------------------------------
static unsigned char CountBitsInCode256(unsigned char *code)
{
    return CountBitsInByte(code[0])
           + CountBitsInByte(code[1])
           + CountBitsInByte(code[2]);
}

//------------------------------------------------------------------------------
/// Calculates the 22-bit hamming code for a 256-bytes block of data.
/// \param data  Data buffer to calculate code for.
/// \param code  Pointer to a buffer where the code should be stored.
//------------------------------------------------------------------------------
static void Compute256(const unsigned char *data, unsigned char *code)
{
    unsigned int i;
    unsigned char columnSum = 0;
    unsigned char evenLineCode = 0;
    unsigned char oddLineCode = 0;
    unsigned char evenColumnCode = 0;
    unsigned char oddColumnCode = 0;

    // Xor all bytes together to get the column sum;
    // At the same time, calculate the even and odd line codes
    for (i=0; i < 256; i++) {

        columnSum ^= data[i];

        // If the xor sum of the byte is 0, then this byte has no incidence on
        // the computed code; so check if the sum is 1.
        if ((CountBitsInByte(data[i]) & 1) == 1) {

            // Parity groups are formed by forcing a particular index bit to 0
            // (even) or 1 (odd).
            // Example on one byte:
            // 
            // bits (dec)  7   6   5   4   3   2   1   0    
            //      (bin) 111 110 101 100 011 010 001 000    
            //                            '---'---'---'----------.
            //                                                   |
            // groups P4' ooooooooooooooo eeeeeeeeeeeeeee P4     |
            //        P2' ooooooo eeeeeee ooooooo eeeeeee P2     |
            //        P1' ooo eee ooo eee ooo eee ooo eee P1     |
            //                                                   |
            // We can see that:                                  |
            //  - P4  -> bit 2 of index is 0 --------------------'
            //  - P4' -> bit 2 of index is 1.
            //  - P2  -> bit 1 of index if 0.
            //  - etc...
            // We deduce that a bit position has an impact on all even Px if
            // the log2(x)nth bit of its index is 0
            //     ex: log2(4) = 2, bit2 of the index must be 0 (-> 0 1 2 3)
            // and on all odd Px' if the log2(x)nth bit of its index is 1
            //     ex: log2(2) = 1, bit1 of the index must be 1 (-> 0 1 4 5)
            // 
            // As such, we calculate all the possible Px and Px' values at the
            // same time in two variables, evenLineCode and oddLineCode, such as
            //     evenLineCode bits: P128  P64  P32  P16  P8  P4  P2  P1
            //     oddLineCode  bits: P128' P64' P32' P16' P8' P4' P2' P1'
            // 
            evenLineCode ^= (255 - i);
            oddLineCode ^= i;
        }
    }

    // At this point, we have the line parities, and the column sum. First, We
    // must caculate the parity group values on the column sum.
    for (i=0; i < 8; i++) {

        if (columnSum & 1) {

            evenColumnCode ^= (7 - i);
            oddColumnCode ^= i;
        }
        columnSum >>= 1;
    }

    // Now, we must interleave the parity values, to obtain the following layout:
    // Code[0] = Line1
    // Code[1] = Line2
    // Code[2] = Column
    // Line = Px' Px P(x-1)- P(x-1) ...
    // Column = P4' P4 P2' P2 P1' P1 PadBit PadBit 
    code[0] = 0;
    code[1] = 0;
    code[2] = 0;

    for (i=0; i < 4; i++) {

        code[0] <<= 2;
        code[1] <<= 2;
        code[2] <<= 2;

        // Line 1
        if ((oddLineCode & 0x80) != 0) {

            code[0] |= 2;
        }
        if ((evenLineCode & 0x80) != 0) {

            code[0] |= 1;
        }

        // Line 2
        if ((oddLineCode & 0x08) != 0) {

            code[1] |= 2;
        }
        if ((evenLineCode & 0x08) != 0) {

            code[1] |= 1;
        }

        // Column
        if ((oddColumnCode & 0x04) != 0) {

            code[2] |= 2;
        }
        if ((evenColumnCode & 0x04) != 0) {

            code[2] |= 1;
        }

        oddLineCode <<= 1;
        evenLineCode <<= 1;
        oddColumnCode <<= 1;
        evenColumnCode <<= 1;
    }

    // Invert codes (linux compatibility)
    code[0] = ~code[0];
    code[1] = ~code[1];
    code[2] = ~code[2];

    TRACE_DEBUG("Computed code = %02X %02X %02X\n\r",
              code[0], code[1], code[2]);
}

//------------------------------------------------------------------------------
/// Verifies and corrects a 256-bytes block of data using the given 22-bits
/// hamming code.
/// Returns 0 if there is no error, otherwise returns a HAMMING_ERROR code.
/// \param data  Data buffer to check.
/// \param originalCode  Hamming code to use for verifying the data.
//------------------------------------------------------------------------------
static unsigned char Verify256(
    unsigned char *data,
    const unsigned char *originalCode)
{
    // Calculate new code
    unsigned char computedCode[3];
    unsigned char correctionCode[3];
    Compute256(data, computedCode);

    // Xor both codes together
    correctionCode[0] = computedCode[0] ^ originalCode[0];
    correctionCode[1] = computedCode[1] ^ originalCode[1];
    correctionCode[2] = computedCode[2] ^ originalCode[2];

    TRACE_DEBUG("Correction code = %02X %02X %02X\n\r",
              correctionCode[0], correctionCode[1], correctionCode[2]);

    // If all bytes are 0, there is no error
    if ((correctionCode[0] == 0)
        && (correctionCode[1] == 0)
        && (correctionCode[2] == 0)) {

        return 0;
    }
    // If there is a single bit error, there are 11 bits set to 1
    if (CountBitsInCode256(correctionCode) == 11) {

        // Get byte and bit indexes
        unsigned char byte = correctionCode[0] & 0x80;
        byte |= (correctionCode[0] << 1) & 0x40;
        byte |= (correctionCode[0] << 2) & 0x20;
        byte |= (correctionCode[0] << 3) & 0x10;

        byte |= (correctionCode[1] >> 4) & 0x08;
        byte |= (correctionCode[1] >> 3) & 0x04;
        byte |= (correctionCode[1] >> 2) & 0x02;
        byte |= (correctionCode[1] >> 1) & 0x01;

        unsigned char bit = (correctionCode[2] >> 5) & 0x04;
        bit |= (correctionCode[2] >> 4) & 0x02;
        bit |= (correctionCode[2] >> 3) & 0x01;

        // Correct bit
        TRACE_DEBUG("Correcting byte #%d at bit %d\n\r", byte, bit);
        data[byte] ^= (1 << bit);

        return Hamming_ERROR_SINGLEBIT;
    }
    // Check if ECC has been corrupted
    if (CountBitsInCode256(correctionCode) == 1) {

        return Hamming_ERROR_ECC;
    }
    // Otherwise, this is a multi-bit error
    else {

        return Hamming_ERROR_MULTIPLEBITS;
    }
}

//------------------------------------------------------------------------------
//         Exported functions
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
/// Computes 3-bytes hamming codes for a data block whose size is multiple of
/// 256 bytes. Each 256 bytes block gets its own code.
/// \param data  Data to compute code for.
/// \param size  Data size in bytes.
/// \param code  Codes buffer.
//------------------------------------------------------------------------------
void Hamming_Compute256x(
    const unsigned char *data,
    unsigned int size,
    unsigned char *code)
{
    TRACE_DEBUG("Hamming_Compute256x()\n\r");

    while (size > 0) {

        Compute256(data, code);
        data += 256;
        code += 3;
        size -= 256;
    }
}

//------------------------------------------------------------------------------
/// Verifies 3-bytes hamming codes for a data block whose size is multiple of
/// 256 bytes. Each 256-bytes block is verified with its own code.
/// Returns 0 if the data is correct, Hamming_ERROR_SINGLEBIT if one or more
/// block(s) have had a single bit corrected, or either Hamming_ERROR_ECC
/// or Hamming_ERROR_MULTIPLEBITS.
/// \param data  Data buffer to verify.
/// \param size  Size of the data in bytes.
/// \param code  Original codes.
//------------------------------------------------------------------------------
unsigned char Hamming_Verify256x(
    unsigned char *data,
    unsigned int size,
    const unsigned char *code)
{
    unsigned char error;
    unsigned char result = 0;

    TRACE_DEBUG("Hamming_Verify256x()\n\r");

    while (size > 0) {

        error = Verify256(data, code);
        if (error == Hamming_ERROR_SINGLEBIT) {

            result = Hamming_ERROR_SINGLEBIT;
        }
        else if (error) {

            return error;
        }

        data += 256;
        code += 3;
        size -= 256;
    }

    return result;
}