Home | History | Annotate | Line # | Download | only in raidframe
rf_geniq.c revision 1.3
      1 /*	$NetBSD: rf_geniq.c,v 1.3 1999/02/05 00:06:12 oster 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 #define RF_UTILITY 1
     35 #include "rf_pqdeg.h"
     36 
     37 /*
     38    five bit lfsr
     39    poly - feedback connections
     40 
     41    val  = value;
     42 */
     43 int
     44 lsfr_shift(val, poly)
     45 	unsigned val, poly;
     46 {
     47 	unsigned new;
     48 	unsigned int i;
     49 	unsigned high = (val >> 4) & 1;
     50 	unsigned bit;
     51 
     52 	new = (poly & 1) ? high : 0;
     53 
     54 	for (i = 1; i <= 4; i++) {
     55 		bit = (val >> (i - 1)) & 1;
     56 		if (poly & (1 << i))	/* there is a feedback connection */
     57 			new = new | ((bit ^ high) << i);
     58 		else
     59 			new = new | (bit << i);
     60 	}
     61 	return new;
     62 }
     63 /* generate Q matricies for the data */
     64 
     65 RF_ua32_t rf_qfor[32];
     66 
     67 void
     68 main()
     69 {
     70 	unsigned int i, j, l, a, b;
     71 	unsigned int val;
     72 	unsigned int r;
     73 	unsigned int m, p, q;
     74 
     75 	RF_ua32_t k;
     76 
     77 	printf("/*\n");
     78 	printf(" * rf_invertq.h\n");
     79 	printf(" */\n");
     80 	printf("/*\n");
     81 	printf(" * GENERATED FILE -- DO NOT EDIT\n");
     82 	printf(" */\n");
     83 	printf("\n");
     84 	printf("#ifndef _RF__RF_INVERTQ_H_\n");
     85 	printf("#define _RF__RF_INVERTQ_H_\n");
     86 	printf("\n");
     87 	printf("/*\n");
     88 	printf(" * rf_geniq.c must include rf_archs.h before including\n");
     89 	printf(" * this file (to get VPATH magic right with the way we\n");
     90 	printf(" * generate this file in kernel trees)\n");
     91 	printf(" */\n");
     92 	printf("/* #include \"rf_archs.h\" */\n");
     93 	printf("\n");
     94 	printf("#if (RF_INCLUDE_PQ > 0) || (RF_INCLUDE_RAID6 > 0)\n");
     95 	printf("\n");
     96 	printf("#define RF_Q_COLS 32\n");
     97 	printf("RF_ua32_t rf_rn = {\n");
     98 	k[0] = 1;
     99 	for (j = 0; j < 31; j++)
    100 		k[j + 1] = lsfr_shift(k[j], 5);
    101 	for (j = 0; j < 32; j++)
    102 		printf("%d, ", k[j]);
    103 	printf("};\n");
    104 
    105 	printf("RF_ua32_t rf_qfor[32] = {\n");
    106 	for (i = 0; i < 32; i++) {
    107 		printf("/* i = %d */ { 0, ", i);
    108 		rf_qfor[i][0] = 0;
    109 		for (j = 1; j < 32; j++) {
    110 			val = j;
    111 			for (l = 0; l < i; l++)
    112 				val = lsfr_shift(val, 5);
    113 			rf_qfor[i][j] = val;
    114 			printf("%d, ", val);
    115 		}
    116 		printf("},\n");
    117 	}
    118 	printf("};\n");
    119 	printf("#define RF_Q_DATA_COL(col_num) rf_rn[col_num],rf_qfor[28-(col_num)]\n");
    120 
    121 	/* generate the inverse tables. (i,j,p,q) */
    122 	/* The table just stores a. Get b back from the parity */
    123 	printf("#ifdef KERNEL\n");
    124 	printf("RF_ua1024_t rf_qinv[1];        /* don't compile monster table into kernel */\n");
    125 	printf("#elif defined(NO_PQ)\n");
    126 	printf("RF_ua1024_t rf_qinv[29*29];\n");
    127 	printf("#else /* !KERNEL && NO_PQ */\n");
    128 	printf("RF_ua1024_t rf_qinv[29*29] = {\n");
    129 	for (i = 0; i < 29; i++) {
    130 		for (j = 0; j < 29; j++) {
    131 			printf("/* i %d, j %d */{ ", i, j);
    132 			if (i == j)
    133 				for (l = 0; l < 1023; l++)
    134 					printf("0, ");
    135 			else {
    136 				for (p = 0; p < 32; p++)
    137 					for (q = 0; q < 32; q++) {
    138 						/* What are a, b such that a ^
    139 						 * b =  p; and qfor[(28-i)][a
    140 						 * ^ rf_rn[i+1]] ^
    141 						 * qfor[(28-j)][b ^
    142 						 * rf_rn[j+1]] =  q. Solve by
    143 						 * guessing a. Then testing. */
    144 						for (a = 0; a < 32; a++) {
    145 							b = a ^ p;
    146 							if ((rf_qfor[28 - i][a ^ k[i + 1]] ^ rf_qfor[28 - j][b ^ k[j + 1]]) == q)
    147 								break;
    148 						}
    149 						if (a == 32)
    150 							printf("unable to solve %d %d %d %d\n", i, j, p, q);
    151 						printf("%d,", a);
    152 					}
    153 			}
    154 			printf("},\n");
    155 		}
    156 	}
    157 	printf("};\n");
    158 	printf("\n#endif /* (RF_INCLUDE_PQ > 0) || (RF_INCLUDE_RAID6 > 0) */\n\n");
    159 	printf("#endif /* !KERNEL && NO_PQ */\n");
    160 	printf("#endif /* !_RF__RF_INVERTQ_H_ */\n");
    161 	exit(0);
    162 }
    163