rf_geniq.c revision 1.4 1 1.4 lukem /* $NetBSD: rf_geniq.c,v 1.4 2001/11/13 07:11:14 lukem Exp $ */
2 1.1 oster /*
3 1.1 oster * Copyright (c) 1995 Carnegie-Mellon University.
4 1.1 oster * All rights reserved.
5 1.1 oster *
6 1.1 oster * Author: Daniel Stodolsky
7 1.1 oster *
8 1.1 oster * Permission to use, copy, modify and distribute this software and
9 1.1 oster * its documentation is hereby granted, provided that both the copyright
10 1.1 oster * notice and this permission notice appear in all copies of the
11 1.1 oster * software, derivative works or modified versions, and any portions
12 1.1 oster * thereof, and that both notices appear in supporting documentation.
13 1.1 oster *
14 1.1 oster * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
15 1.1 oster * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
16 1.1 oster * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
17 1.1 oster *
18 1.1 oster * Carnegie Mellon requests users of this software to return to
19 1.1 oster *
20 1.1 oster * Software Distribution Coordinator or Software.Distribution (at) CS.CMU.EDU
21 1.1 oster * School of Computer Science
22 1.1 oster * Carnegie Mellon University
23 1.1 oster * Pittsburgh PA 15213-3890
24 1.1 oster *
25 1.1 oster * any improvements or extensions that they make and grant Carnegie the
26 1.1 oster * rights to redistribute these changes.
27 1.1 oster */
28 1.1 oster
29 1.1 oster /* rf_geniq.c
30 1.1 oster * code which implements Reed-Solomon encoding for RAID level 6
31 1.1 oster */
32 1.1 oster
33 1.4 lukem
34 1.4 lukem #include <sys/cdefs.h>
35 1.4 lukem __KERNEL_RCSID(0, "$NetBSD: rf_geniq.c,v 1.4 2001/11/13 07:11:14 lukem Exp $");
36 1.1 oster
37 1.1 oster #define RF_UTILITY 1
38 1.1 oster #include "rf_pqdeg.h"
39 1.1 oster
40 1.1 oster /*
41 1.1 oster five bit lfsr
42 1.1 oster poly - feedback connections
43 1.1 oster
44 1.1 oster val = value;
45 1.1 oster */
46 1.3 oster int
47 1.3 oster lsfr_shift(val, poly)
48 1.3 oster unsigned val, poly;
49 1.1 oster {
50 1.3 oster unsigned new;
51 1.3 oster unsigned int i;
52 1.3 oster unsigned high = (val >> 4) & 1;
53 1.3 oster unsigned bit;
54 1.3 oster
55 1.3 oster new = (poly & 1) ? high : 0;
56 1.3 oster
57 1.3 oster for (i = 1; i <= 4; i++) {
58 1.3 oster bit = (val >> (i - 1)) & 1;
59 1.3 oster if (poly & (1 << i)) /* there is a feedback connection */
60 1.3 oster new = new | ((bit ^ high) << i);
61 1.3 oster else
62 1.3 oster new = new | (bit << i);
63 1.3 oster }
64 1.3 oster return new;
65 1.1 oster }
66 1.1 oster /* generate Q matricies for the data */
67 1.1 oster
68 1.1 oster RF_ua32_t rf_qfor[32];
69 1.1 oster
70 1.3 oster void
71 1.3 oster main()
72 1.1 oster {
73 1.3 oster unsigned int i, j, l, a, b;
74 1.3 oster unsigned int val;
75 1.3 oster unsigned int r;
76 1.3 oster unsigned int m, p, q;
77 1.3 oster
78 1.3 oster RF_ua32_t k;
79 1.3 oster
80 1.3 oster printf("/*\n");
81 1.3 oster printf(" * rf_invertq.h\n");
82 1.3 oster printf(" */\n");
83 1.3 oster printf("/*\n");
84 1.3 oster printf(" * GENERATED FILE -- DO NOT EDIT\n");
85 1.3 oster printf(" */\n");
86 1.3 oster printf("\n");
87 1.3 oster printf("#ifndef _RF__RF_INVERTQ_H_\n");
88 1.3 oster printf("#define _RF__RF_INVERTQ_H_\n");
89 1.3 oster printf("\n");
90 1.3 oster printf("/*\n");
91 1.3 oster printf(" * rf_geniq.c must include rf_archs.h before including\n");
92 1.3 oster printf(" * this file (to get VPATH magic right with the way we\n");
93 1.3 oster printf(" * generate this file in kernel trees)\n");
94 1.3 oster printf(" */\n");
95 1.3 oster printf("/* #include \"rf_archs.h\" */\n");
96 1.3 oster printf("\n");
97 1.3 oster printf("#if (RF_INCLUDE_PQ > 0) || (RF_INCLUDE_RAID6 > 0)\n");
98 1.3 oster printf("\n");
99 1.3 oster printf("#define RF_Q_COLS 32\n");
100 1.3 oster printf("RF_ua32_t rf_rn = {\n");
101 1.3 oster k[0] = 1;
102 1.3 oster for (j = 0; j < 31; j++)
103 1.3 oster k[j + 1] = lsfr_shift(k[j], 5);
104 1.3 oster for (j = 0; j < 32; j++)
105 1.3 oster printf("%d, ", k[j]);
106 1.3 oster printf("};\n");
107 1.3 oster
108 1.3 oster printf("RF_ua32_t rf_qfor[32] = {\n");
109 1.3 oster for (i = 0; i < 32; i++) {
110 1.3 oster printf("/* i = %d */ { 0, ", i);
111 1.3 oster rf_qfor[i][0] = 0;
112 1.3 oster for (j = 1; j < 32; j++) {
113 1.3 oster val = j;
114 1.3 oster for (l = 0; l < i; l++)
115 1.3 oster val = lsfr_shift(val, 5);
116 1.3 oster rf_qfor[i][j] = val;
117 1.3 oster printf("%d, ", val);
118 1.3 oster }
119 1.3 oster printf("},\n");
120 1.1 oster }
121 1.3 oster printf("};\n");
122 1.3 oster printf("#define RF_Q_DATA_COL(col_num) rf_rn[col_num],rf_qfor[28-(col_num)]\n");
123 1.3 oster
124 1.3 oster /* generate the inverse tables. (i,j,p,q) */
125 1.3 oster /* The table just stores a. Get b back from the parity */
126 1.3 oster printf("#ifdef KERNEL\n");
127 1.3 oster printf("RF_ua1024_t rf_qinv[1]; /* don't compile monster table into kernel */\n");
128 1.3 oster printf("#elif defined(NO_PQ)\n");
129 1.3 oster printf("RF_ua1024_t rf_qinv[29*29];\n");
130 1.3 oster printf("#else /* !KERNEL && NO_PQ */\n");
131 1.3 oster printf("RF_ua1024_t rf_qinv[29*29] = {\n");
132 1.3 oster for (i = 0; i < 29; i++) {
133 1.3 oster for (j = 0; j < 29; j++) {
134 1.3 oster printf("/* i %d, j %d */{ ", i, j);
135 1.3 oster if (i == j)
136 1.3 oster for (l = 0; l < 1023; l++)
137 1.3 oster printf("0, ");
138 1.3 oster else {
139 1.3 oster for (p = 0; p < 32; p++)
140 1.3 oster for (q = 0; q < 32; q++) {
141 1.3 oster /* What are a, b such that a ^
142 1.3 oster * b = p; and qfor[(28-i)][a
143 1.3 oster * ^ rf_rn[i+1]] ^
144 1.3 oster * qfor[(28-j)][b ^
145 1.3 oster * rf_rn[j+1]] = q. Solve by
146 1.3 oster * guessing a. Then testing. */
147 1.3 oster for (a = 0; a < 32; a++) {
148 1.3 oster b = a ^ p;
149 1.3 oster if ((rf_qfor[28 - i][a ^ k[i + 1]] ^ rf_qfor[28 - j][b ^ k[j + 1]]) == q)
150 1.3 oster break;
151 1.3 oster }
152 1.3 oster if (a == 32)
153 1.3 oster printf("unable to solve %d %d %d %d\n", i, j, p, q);
154 1.3 oster printf("%d,", a);
155 1.3 oster }
156 1.3 oster }
157 1.3 oster printf("},\n");
158 1.3 oster }
159 1.1 oster }
160 1.3 oster printf("};\n");
161 1.3 oster printf("\n#endif /* (RF_INCLUDE_PQ > 0) || (RF_INCLUDE_RAID6 > 0) */\n\n");
162 1.3 oster printf("#endif /* !KERNEL && NO_PQ */\n");
163 1.3 oster printf("#endif /* !_RF__RF_INVERTQ_H_ */\n");
164 1.3 oster exit(0);
165 1.1 oster }
166