git.sesse.net Git - hamming/blob - hamming64.c

   1 #include <stdio.h>
   2 #include <time.h>
   3 #include <stdlib.h>
   4
   5 #define DATA_BITS    64
   6 #define PARITY_BITS  8
   7 #define CODE_BITS    (DATA_BITS + PARITY_BITS)
   8 #define SAMPLE_SIZE  1000000
   9 #define SAMPLE_PROGRESS  100000
  10
  11 /*
  12  * Needed since we store all the parity at the end of the word, not at the expected
  13  * power-of-two bit positions.
  14  */
  15 int permutation_table[CODE_BITS + 1] = {
  16         -1, -1, -1, 63, -1, 62, 61, 60, -1, 59, 58, 57, 56, 55, 54, 53, -1, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, -1, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, -1, 6, 5, 4, 3, 2, 1, 0
  17 };
  18
  19 unsigned find_parity_8(unsigned x)
  20 {
  21         x ^= x >> 4;
  22         x &= 0xf;
  23         return (0x6996 >> x) & 1;
  24 }
  25
  26 unsigned find_parity_64(unsigned long long x)
  27 {
  28         unsigned y = (x ^ (x >> 32)) & 0xFFFFFFFFULL;
  29         y ^= y >> 16;
  30         y ^= y >> 8;
  31         return find_parity_8(y);
  32 }
  33
  34 unsigned generate_parity(unsigned long long data)
  35 {
  36         unsigned parity1 = find_parity_64(data & 0xDAB5556AAAAAAAD5ULL);
  37         unsigned parity2 = find_parity_64(data & 0xB66CCCD9999999B3ULL);
  38         unsigned parity3 = find_parity_64(data & 0x71E3C3C78787878FULL);
  39         unsigned parity4 = find_parity_64(data & 0x0FE03FC07F807F80ULL);
  40         unsigned parity5 = find_parity_64(data & 0x001FFFC0007FFF80ULL);
  41         unsigned parity6 = find_parity_64(data & 0x0000003FFFFFFF80ULL);
  42         unsigned parity7 = find_parity_64(data & 0x000000000000007FULL);
  43         unsigned parity8 = find_parity_64(data & 0xED3A65B4CB4B34E9ULL);
  44
  45         return parity8 | (parity7 << 1) | (parity6 << 2) | (parity5 << 3) | (parity4 << 4) | (parity3 << 5) | (parity2 << 6) | (parity1 << 7);
  46 }
  47
  48 /* can detect all single or double bit errors */
  49 int has_error(unsigned long long data, unsigned parity)
  50 {
  51         return (generate_parity(data) != parity);
  52 }
  53
  54 int has_double_error(unsigned long long data, unsigned parity)
  55 {
  56         return (generate_parity(data) != parity) && (find_parity_64(data) == find_parity_8(parity));
  57 }
  58
  59 /* Correct any single-bit error -- assumes there are no double-bit errors */
  60 unsigned long long correct_single_bit_error(unsigned long long data, unsigned parity)
  61 {
  62         unsigned parity_diff = generate_parity(data) ^ parity;
  63         unsigned bp = 0, i;
  64
  65         for (i = 0; i < PARITY_BITS - 1; ++i) {
  66                 if (parity_diff & (1 << (PARITY_BITS - 1 - i))) {
  67                         bp |= (1 << i);
  68                 }
  69         }
  70
  71         /* flip the wrong bit, if it's in the data */
  72         if (permutation_table[bp] != -1) {
  73                 data ^= (1ULL << permutation_table[bp]);
  74         }
  75
  76         return data;
  77 }
  78
  79 void check_zero_bit_detection()
  80 {
  81         unsigned i;
  82         printf("Checking zero bit detection.");
  83         fflush(stdout);
  84
  85         for (i = 0; i < SAMPLE_SIZE; ++i) {
  86                 unsigned long long data =
  87                         ((unsigned long long)(rand()) << 40) ^
  88                         ((unsigned long long)(rand()) << 20) ^
  89                         ((unsigned long long)(rand()));
  90                 unsigned long long parity =
  91                         generate_parity(data);
  92
  93                 if ((i % SAMPLE_PROGRESS) == 0) {
  94                         printf(".");
  95                         fflush(stdout);
  96                 }
  97
  98                 if (has_error(data, parity)) {
  99                         printf("ERROR: Failed zero-bit test 1 for %llx\n", data);
 100                 }
 101                 if (has_double_error(data, parity)) {
 102                         printf("ERROR: Failed zero-bit test 2 for %llx\n", data);
 103                 }
 104         }
 105
 106         printf("\n");
 107 }
 108
 109 void check_single_bit_detection()
 110 {
 111         unsigned i, j;
 112         printf("Checking single bit detection and correction.");
 113         fflush(stdout);
 114
 115         for (i = 0; i < SAMPLE_SIZE; ++i) {
 116                 unsigned long long data =
 117                         ((unsigned long long)(rand()) << 40) ^
 118                         ((unsigned long long)(rand()) << 20) ^
 119                         ((unsigned long long)(rand()));
 120                 unsigned long long parity =
 121                         generate_parity(data);
 122
 123                 if ((i % SAMPLE_PROGRESS) == 0) {
 124                         printf(".");
 125                         fflush(stdout);
 126                 }
 127
 128                 for (j = 0; j < CODE_BITS; ++j) {
 129                         unsigned long long corrupted_data = data;
 130                         unsigned corrupted_parity = parity;
 131
 132                         if (j < DATA_BITS) {
 133                                 corrupted_data ^= (1ULL << j);
 134                         } else {
 135                                 corrupted_parity ^= (1 << (j - DATA_BITS));
 136                         }
 137
 138                         if (!has_error(corrupted_data, corrupted_parity)) {
 139                                 printf("ERROR: Failed single-bit test 1 for %llx with bit %u flipped\n", data, j);
 140                         }
 141                         if (has_double_error(corrupted_data, corrupted_parity)) {
 142                                 printf("ERROR: Failed single-bit test 2 for %llx with bit %u flipped\n", data, j);
 143                         }
 144                         if (correct_single_bit_error(corrupted_data, corrupted_parity) != data) {
 145                                 printf("ERROR: Failed single-bit correction test for %llx with bit %u flipped\n", data, j);
 146                         }
 147                 }
 148         }
 149
 150         printf("\n");
 151 }
 152
 153 void check_double_bit_detection()
 154 {
 155         unsigned i, j, k;
 156         printf("Checking double bit detection.");
 157         fflush(stdout);
 158
 159         for (i = 0; i < SAMPLE_SIZE; ++i) {
 160                 unsigned long long data =
 161                         ((unsigned long long)(rand()) << 40) ^
 162                         ((unsigned long long)(rand()) << 20) ^
 163                         ((unsigned long long)(rand()));
 164                 unsigned long long parity =
 165                         generate_parity(data);
 166
 167                 if ((i % SAMPLE_PROGRESS) == 0) {
 168                         printf(".");
 169                         fflush(stdout);
 170                 }
 171
 172                 for (j = 0; j < CODE_BITS; ++j) {
 173                         for (k = j + 1; k < CODE_BITS; ++k) {
 174                                 unsigned long long corrupted_data = data;
 175                                 unsigned corrupted_parity = parity;
 176                                 if (j < DATA_BITS) {
 177                                         corrupted_data ^= (1ULL << j);
 178                                 } else {
 179                                         corrupted_parity ^= (1 << (j - DATA_BITS));
 180                                 }
 181                                 if (k < DATA_BITS) {
 182                                         corrupted_data ^= (1ULL << k);
 183                                 } else {
 184                                         corrupted_parity ^= (1 << (k - DATA_BITS));
 185                                 }
 186
 187                                 if (!has_error(corrupted_data, corrupted_parity)) {
 188                                         printf("ERROR: Failed double-bit test 1 for %llx with bit %u and %u flipped\n", data, j, k);
 189                                 }
 190                                 if (!has_double_error(corrupted_data, corrupted_parity)) {
 191                                         printf("ERROR: Failed double-bit test 2 for %llx with bit %u and %u flipped\n", data, j, k);
 192                                 }
 193                         }
 194                 }
 195         }
 196
 197         printf("\n");
 198 }
 199
 200 int main()
 201 {
 202         srand(time(NULL));
 203         check_zero_bit_detection();
 204         check_single_bit_detection();
 205         check_double_bit_detection();
 206
 207         return 0;
 208 }