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