Home | History | Annotate | Line # | Download | only in raidframe 
      1 /*	$NetBSD: rf_geniq.c,v 1.6 2009/03/18 10:22:41 cegger 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 (at) 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.6 2009/03/18 10:22:41 cegger 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 }
    165