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