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@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
lsfr_shift(unsigned val,unsigned poly)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
main(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