1 /* $OpenBSD: rf_geniq.c,v 1.5 2002/12/16 07:01:04 tdeval Exp $ */
2 /* $NetBSD: rf_geniq.c,v 1.3 1999/02/05 00:06:12 oster Exp $ */
3
4 /*
5 * Copyright (c) 1995 Carnegie-Mellon University.
6 * All rights reserved.
7 *
8 * Author: Daniel Stodolsky
9 *
10 * Permission to use, copy, modify and distribute this software and
11 * its documentation is hereby granted, provided that both the copyright
12 * notice and this permission notice appear in all copies of the
13 * software, derivative works or modified versions, and any portions
14 * thereof, and that both notices appear in supporting documentation.
15 *
16 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
17 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
18 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
19 *
20 * Carnegie Mellon requests users of this software to return to
21 *
22 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
23 * School of Computer Science
24 * Carnegie Mellon University
25 * Pittsburgh PA 15213-3890
26 *
27 * any improvements or extensions that they make and grant Carnegie the
28 * rights to redistribute these changes.
29 */
30
31 /*
32 * rf_geniq.c -- Code which implements Reed-Solomon encoding for RAID level 6.
33 */
34
35
36 #define RF_UTILITY 1
37 #include "rf_pqdeg.h"
38
39 /*
40 * five bit lfsr
41 * poly - feedback connections
42 *
43 * val = value;
44 */
45 int
46 lsfr_shift(unsigned val, unsigned poly)
47 {
48 unsigned new;
49 unsigned int i;
50 unsigned high = (val >> 4) & 1;
51 unsigned bit;
52
53 new = (poly & 1) ? high : 0;
54
55 for (i = 1; i <= 4; i++) {
56 bit = (val >> (i - 1)) & 1;
57 if (poly & (1 << i)) /* There is a feedback connection. */
58 new = new | ((bit ^ high) << i);
59 else
60 new = new | (bit << i);
61 }
62 return new;
63 }
64
65
66 /* Generate Q matrices for the data. */
67
68 RF_ua32_t rf_qfor[32];
69
70 int
71 main(void)
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\t_RF__RF_INVERTQ_H_\n");
88 printf("#define\t_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\t(RF_INCLUDE_PQ > 0) || (RF_INCLUDE_RAID6 > 0)\n");
98 printf("\n");
99 printf("#define\tRF_Q_COLS\t32\n");
100 printf("RF_ua32_t rf_rn = {");
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 */\t{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\tRF_Q_DATA_COL(col_num)\trf_rn[col_num],"
123 " rf_qfor[28-(col_num)]\n");
124
125 /* generate the inverse tables. (i,j,p,q) */
126 /* The table just stores a. Get b back from the parity */
127 printf("#ifdef\t_KERNEL\n");
128 printf("RF_ua1024_t rf_qinv[1];\t/* don't compile monster table"
129 " into kernel */\n");
130 printf("#elif\tdefined(NO_PQ)\n");
131 printf("RF_ua1024_t rf_qinv[29*29];\n");
132 printf("#else\t/* !_KERNEL && NO_PQ */\n");
133 printf("RF_ua1024_t rf_qinv[29*29] = {\n");
134 for (i = 0; i < 29; i++) {
135 for (j = 0; j < 29; j++) {
136 printf("/* i %d, j %d */\t{", i, j);
137 if (i == j)
138 for (l = 0; l < 1023; l++)
139 printf("0, ");
140 else {
141 for (p = 0; p < 32; p++)
142 for (q = 0; q < 32; q++) {
143 /*
144 * What are a, b such that a ^
145 * b == p; and qfor[(28-i)][a
146 * ^ rf_rn[i+1]] ^
147 * qfor[(28-j)][b ^
148 * rf_rn[j+1]] == q. Solve by
149 * guessing a. Then testing.
150 */
151 for (a = 0; a < 32; a++) {
152 b = a ^ p;
153 if ((rf_qfor[28 - i]
154 [a ^ k[i + 1]] ^
155 rf_qfor[28 - j]
156 [b ^ k[j + 1]]) ==
157 q)
158 break;
159 }
160 if (a == 32)
161 printf("unable to solve"
162 " %d %d %d %d\n",
163 i, j, p, q);
164 printf("%d, ", a);
165 }
166 }
167 printf("},\n");
168 }
169 }
170 printf("};\n");
171 printf("\n#endif\t/* (RF_INCLUDE_PQ > 0) || (RF_INCLUDE_RAID6 > 0) */"
172 "\n\n");
173 printf("#endif\t/* !_KERNEL && NO_PQ */\n");
174 printf("#endif\t/* !_RF__RF_INVERTQ_H_ */\n");
175 exit(0);
176 }