release/src-rt-6.x.4708/cfe/cfe/dev/hamming.c

   1 /*
   2  * Hamming ecc algorithm for NAND flash.
   3  *
   4  * Copyright (C) 2011, Broadcom Corporation. All Rights Reserved.
   5  *
   6  * Permission to use, copy, modify, and/or distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  13  * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
  15  * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
  16  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  *
  18  * $Id:  $
  19  * ftp://ftp.be.netbsd.org/pub/NetBSD/NetBSD-release-6/src/sys/dev/nand/hamming.c
  20  */
  21 /*
  22  * Copyright (c) 2008, Atmel Corporation
  23  *
  24  * All rights reserved.
  25  *
  26  * Redistribution and use in source and binary forms, with or without
  27  * modification, are permitted provided that the following conditions are met:
  28  *
  29  * - Redistributions of source code must retain the above copyright notice,
  30  * this list of conditions and the disclaimer below.
  31  *
  32  * Atmel's name may not be used to endorse or promote products derived from
  33  * this software without specific prior written permission.
  34  *
  35  * DISCLAIMER: THIS SOFTWARE IS PROVIDED BY ATMEL "AS IS" AND ANY EXPRESS OR
  36  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  37  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT ARE
  38  * DISCLAIMED. IN NO EVENT SHALL ATMEL BE LIABLE FOR ANY DIRECT, INDIRECT,
  39  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  40  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
  41  * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  42  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  43  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  44  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  45  */
  46
  47
  48 #include <typedefs.h>
  49
  50 enum {
  51 /* Multiple bits are incorrect in the data and they cannot be corrected. */
  52         HAMMING_ERROR_MULTIPLEBITS = -2,
  53         HAMMING_ERROR_ECC,
  54         HAMMING_ECC_OK,
  55 /* The original code has been corrupted. */
  56         HAMMING_ERROR_SINGLEBIT
  57 };
  58
  59
  60 unsigned int popcount32(uint32 v);
  61 void hamming_compute_256(const uint8 *data, uint8 *code);
  62 int8
  63 hamming_correct_256(uint8 *data, const uint8 *original_code,
  64     const uint8 *computed_code);
  65 /**
  66  * Calculates the 22-bit hamming code for a 256-bytes block of data.
  67  * \param data  Data buffer to calculate code for.
  68  * \param code  Pointer to a buffer where the code should be stored.
  69  */
  70 void
  71 hamming_compute_256(const uint8 *data, uint8 *code)
  72 {
  73         unsigned int i;
  74         uint8 column_sum = 0;
  75         uint8 even_line_code = 0;
  76         uint8 odd_line_code = 0;
  77         uint8 even_column_code = 0;
  78         uint8 odd_column_code = 0;
  79
  80         /*
  81          * Xor all bytes together to get the column sum;
  82          * At the same time, calculate the even and odd line codes
  83          */
  84         for (i = 0; i < 256; i++) {
  85                 column_sum ^= data[i];
  86
  87                 /*
  88                  * If the xor sum of the byte is 0, then this byte has no
  89                  * incidence on the computed code; so check if the sum is 1.
  90                  */
  91         if ((popcount32((uint32)data[i]) & 1) == 1) {
  92                         /*
  93                          * Parity groups are formed by forcing a particular
  94                          * index bit to 0 (even) or 1 (odd).
  95                          * Example on one byte:
  96                          *
  97                          * bits (dec)  7   6   5   4   3   2   1   0
  98                          *      (bin) 111 110 101 100 011 010 001 000
  99                          *                            '---'---'---'----------.
 100                          *                                                   |
 101                          * groups P4' ooooooooooooooo eeeeeeeeeeeeeee P4     |
 102                          *        P2' ooooooo eeeeeee ooooooo eeeeeee P2     |
 103                          *        P1' ooo eee ooo eee ooo eee ooo eee P1     |
 104                          *                                                   |
 105                          * We can see that:                                  |
 106                          *  - P4  -> bit 2 of index is 0 --------------------'
 107                          *  - P4' -> bit 2 of index is 1.
 108                          *  - P2  -> bit 1 of index if 0.
 109                          *  - etc...
 110                          * We deduce that a bit position has an impact on all
 111                          * even Px if the log2(x)nth bit of its index is 0
 112                          *     ex: log2(4) = 2,
 113                          * bit2 of the index must be 0 (-> 0 1 2 3)
 114                          * and on all odd Px' if the log2(x)nth bit
 115                          * of its index is 1
 116                          *     ex: log2(2) = 1,
 117                          * bit1 of the index must be 1 (-> 0 1 4 5)
 118                          *
 119                          * As such, we calculate all the possible Px and Px'
 120                          * values at the same time in two variables,
 121                          * even_line_code and odd_line_code, such as
 122                          *     even_line_code bits: P128  P64  P32
 123                          *                        P16  P8  P4  P2  P1
 124                          *     odd_line_code  bits: P128' P64' P32' P16'
 125                          *                        P8' P4' P2' P1'
 126                          */
 127                         even_line_code ^= (255 - i);
 128                         odd_line_code ^= i;
 129                 }
 130         }
 131
 132         /*
 133          * At this point, we have the line parities, and the column sum.
 134          * First, We must caculate the parity group values on the column sum.
 135          */
 136         for (i = 0; i < 8; i++) {
 137                 if (column_sum & 1) {
 138                         even_column_code ^= (7 - i);
 139                         odd_column_code ^= i;
 140                 }
 141                 column_sum >>= 1;
 142         }
 143
 144         /*
 145          * Now, we must interleave the parity values,
 146          * to obtain the following layout:
 147          * Code[0] = Line1
 148          * Code[1] = Line2
 149          * Code[2] = Column
 150          * Line = Px' Px P(x-1)- P(x-1) ...
 151          * Column = P4' P4 P2' P2 P1' P1 PadBit PadBit
 152          */
 153         code[0] = 0;
 154         code[1] = 0;
 155         code[2] = 0;
 156
 157         for (i = 0; i < 4; i++) {
 158                 code[0] <<= 2;
 159                 code[1] <<= 2;
 160                 code[2] <<= 2;
 161
 162                 /* Line 1 */
 163                 if ((odd_line_code & 0x80) != 0) {
 164
 165                         code[0] |= 2;
 166                 }
 167                 if ((even_line_code & 0x80) != 0) {
 168
 169                         code[0] |= 1;
 170                 }
 171
 172                 /* Line 2 */
 173                 if ((odd_line_code & 0x08) != 0) {
 174
 175                         code[1] |= 2;
 176                 }
 177                 if ((even_line_code & 0x08) != 0) {
 178
 179                         code[1] |= 1;
 180                 }
 181
 182                 /* Column */
 183                 if ((odd_column_code & 0x04) != 0) {
 184
 185                         code[2] |= 2;
 186                 }
 187                 if ((even_column_code & 0x04) != 0) {
 188
 189                         code[2] |= 1;
 190                 }
 191
 192                 odd_line_code <<= 1;
 193                 even_line_code <<= 1;
 194                 odd_column_code <<= 1;
 195                 even_column_code <<= 1;
 196         }
 197
 198         /* Invert codes (linux compatibility) */
 199         code[0] = ~code[0];
 200         code[1] = ~code[1];
 201         code[2] = ~code[2];
 202 }
 203
 204 /**
 205  * Verifies and corrects a 256-bytes block of data using the given 22-bits
 206  * hamming code.
 207  * Returns 0 if there is no error, otherwise returns a HAMMING_ERROR code.
 208  * param data  Data buffer to check.
 209  * \param original_code  Hamming code to use for verifying the data.
 210  */
 211 int8
 212 hamming_correct_256(uint8 *data, const uint8 *original_code,
 213     const uint8 *computed_code)
 214 {
 215         /* Calculate new code */
 216         /* we allocate 4 bytes so we can use popcount32 in one step */
 217         uint8 correction_code[4];
 218
 219         /* this byte should remain zero all the time */
 220         correction_code[3] = 0;
 221
 222         /* Xor both codes together */
 223         correction_code[0] = computed_code[0] ^ original_code[0];
 224         correction_code[1] = computed_code[1] ^ original_code[1];
 225         correction_code[2] = computed_code[2] ^ original_code[2];
 226
 227         /* If all bytes are 0, there is no error */
 228         if (*(uint32 *)correction_code == 0) {
 229                 return 0;
 230         }
 231         /* If there is a single bit error, there are 11 bits set to 1 */
 232         if (popcount32(*(uint32 *)correction_code) == 11) {
 233                 /* Get byte and bit indexes */
 234                 uint8 byte = correction_code[0] & 0x80;
 235                 byte |= (correction_code[0] << 1) & 0x40;
 236                 byte |= (correction_code[0] << 2) & 0x20;
 237                 byte |= (correction_code[0] << 3) & 0x10;
 238
 239                 byte |= (correction_code[1] >> 4) & 0x08;
 240                 byte |= (correction_code[1] >> 3) & 0x04;
 241                 byte |= (correction_code[1] >> 2) & 0x02;
 242                 byte |= (correction_code[1] >> 1) & 0x01;
 243
 244                 uint8 bit = (correction_code[2] >> 5) & 0x04;
 245                 bit |= (correction_code[2] >> 4) & 0x02;
 246                 bit |= (correction_code[2] >> 3) & 0x01;
 247
 248                 /* Correct bit */
 249                 data[byte] ^= (1 << bit);
 250
 251                 return HAMMING_ERROR_SINGLEBIT;
 252         }
 253         /* Check if ECC has been corrupted */
 254         if (popcount32(*(uint32 *)correction_code) == 1) {
 255                 return HAMMING_ERROR_ECC;
 256         } else {
 257                 /* Otherwise, this is a multi-bit error */
 258                 return HAMMING_ERROR_MULTIPLEBITS;
 259         }
 260 }