sys/dev/raidframe/rf_geniq.c

   1 /*      $NetBSD: rf_geniq.c,v 1.5 2009/03/14 21:04:22 dsl Exp $ */
   2 /*
   3  * Copyright (c) 1995 Carnegie-Mellon University.
   4  * All rights reserved.
   5  *
   6  * Author: Daniel Stodolsky
   7  *
   8  * Permission to use, copy, modify and distribute this software and
   9  * its documentation is hereby granted, provided that both the copyright
  10  * notice and this permission notice appear in all copies of the
  11  * software, derivative works or modified versions, and any portions
  12  * thereof, and that both notices appear in supporting documentation.
  13  *
  14  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  15  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
  16  * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  17  *
  18  * Carnegie Mellon requests users of this software to return to
  19  *
  20  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  21  *  School of Computer Science
  22  *  Carnegie Mellon University
  23  *  Pittsburgh PA 15213-3890
  24  *
  25  * any improvements or extensions that they make and grant Carnegie the
  26  * rights to redistribute these changes.
  27  */
  28
  29 /* rf_geniq.c
  30  *  code which implements Reed-Solomon encoding for RAID level 6
  31  */
  32
  33
  34 #include <sys/cdefs.h>
  35 __KERNEL_RCSID(0, "$NetBSD: rf_geniq.c,v 1.5 2009/03/14 21:04:22 dsl Exp $");
  36
  37 #define RF_UTILITY 1
  38 #include "rf_pqdeg.h"
  39
  40 /*
  41    five bit lfsr
  42    poly - feedback connections
  43
  44    val  = value;
  45 */
  46 int
  47 lsfr_shift(unsigned val, unsigned poly)
  48 {
  49         unsigned new;
  50         unsigned int i;
  51         unsigned high = (val >> 4) & 1;
  52         unsigned bit;
  53
  54         new = (poly & 1) ? high : 0;
  55
  56         for (i = 1; i <= 4; i++) {
  57                 bit = (val >> (i - 1)) & 1;
  58                 if (poly & (1 << i))    /* there is a feedback connection */
  59                         new = new | ((bit ^ high) << i);
  60                 else
  61                         new = new | (bit << i);
  62         }
  63         return new;
  64 }
  65 /* generate Q matricies for the data */
  66
  67 RF_ua32_t rf_qfor[32];
  68
  69 void
  70 main(void)
  71 {
  72         unsigned int i, j, l, a, b;
  73         unsigned int val;
  74         unsigned int r;
  75         unsigned int m, p, q;
  76
  77         RF_ua32_t k;
  78
  79         printf("/*\n");
  80         printf(" * rf_invertq.h\n");
  81         printf(" */\n");
  82         printf("/*\n");
  83         printf(" * GENERATED FILE -- DO NOT EDIT\n");
  84         printf(" */\n");
  85         printf("\n");
  86         printf("#ifndef _RF__RF_INVERTQ_H_\n");
  87         printf("#define _RF__RF_INVERTQ_H_\n");
  88         printf("\n");
  89         printf("/*\n");
  90         printf(" * rf_geniq.c must include rf_archs.h before including\n");
  91         printf(" * this file (to get VPATH magic right with the way we\n");
  92         printf(" * generate this file in kernel trees)\n");
  93         printf(" */\n");
  94         printf("/* #include \"rf_archs.h\" */\n");
  95         printf("\n");
  96         printf("#if (RF_INCLUDE_PQ > 0) || (RF_INCLUDE_RAID6 > 0)\n");
  97         printf("\n");
  98         printf("#define RF_Q_COLS 32\n");
  99         printf("RF_ua32_t rf_rn = {\n");
 100         k[0] = 1;
 101         for (j = 0; j < 31; j++)
 102                 k[j + 1] = lsfr_shift(k[j], 5);
 103         for (j = 0; j < 32; j++)
 104                 printf("%d, ", k[j]);
 105         printf("};\n");
 106
 107         printf("RF_ua32_t rf_qfor[32] = {\n");
 108         for (i = 0; i < 32; i++) {
 109                 printf("/* i = %d */ { 0, ", i);
 110                 rf_qfor[i][0] = 0;
 111                 for (j = 1; j < 32; j++) {
 112                         val = j;
 113                         for (l = 0; l < i; l++)
 114                                 val = lsfr_shift(val, 5);
 115                         rf_qfor[i][j] = val;
 116                         printf("%d, ", val);
 117                 }
 118                 printf("},\n");
 119         }
 120         printf("};\n");
 121         printf("#define RF_Q_DATA_COL(col_num) rf_rn[col_num],rf_qfor[28-(col_num)]\n");
 122
 123         /* generate the inverse tables. (i,j,p,q) */
 124         /* The table just stores a. Get b back from the parity */
 125         printf("#ifdef KERNEL\n");
 126         printf("RF_ua1024_t rf_qinv[1];        /* don't compile monster table into kernel */\n");
 127         printf("#elif defined(NO_PQ)\n");
 128         printf("RF_ua1024_t rf_qinv[29*29];\n");
 129         printf("#else /* !KERNEL && NO_PQ */\n");
 130         printf("RF_ua1024_t rf_qinv[29*29] = {\n");
 131         for (i = 0; i < 29; i++) {
 132                 for (j = 0; j < 29; j++) {
 133                         printf("/* i %d, j %d */{ ", i, j);
 134                         if (i == j)
 135                                 for (l = 0; l < 1023; l++)
 136                                         printf("0, ");
 137                         else {
 138                                 for (p = 0; p < 32; p++)
 139                                         for (q = 0; q < 32; q++) {
 140                                                 /* What are a, b such that a ^
 141                                                  * b =  p; and qfor[(28-i)][a
 142                                                  * ^ rf_rn[i+1]] ^
 143                                                  * qfor[(28-j)][b ^
 144                                                  * rf_rn[j+1]] =  q. Solve by
 145                                                  * guessing a. Then testing. */
 146                                                 for (a = 0; a < 32; a++) {
 147                                                         b = a ^ p;
 148                                                         if ((rf_qfor[28 - i][a ^ k[i + 1]] ^ rf_qfor[28 - j][b ^ k[j + 1]]) == q)
 149                                                                 break;
 150                                                 }
 151                                                 if (a == 32)
 152                                                         printf("unable to solve %d %d %d %d\n", i, j, p, q);
 153                                                 printf("%d,", a);
 154                                         }
 155                         }
 156                         printf("},\n");
 157                 }
 158         }
 159         printf("};\n");
 160         printf("\n#endif /* (RF_INCLUDE_PQ > 0) || (RF_INCLUDE_RAID6 > 0) */\n\n");
 161         printf("#endif /* !KERNEL && NO_PQ */\n");
 162         printf("#endif /* !_RF__RF_INVERTQ_H_ */\n");
 163         exit(0);
 164 }