![[BACK]](/icons/back.gif){kind=icon}
Return to rf_geniq.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / dev / raidframe|
Return to rf_geniq.c CVS log | Up to [local] / sys / dev / raidframe |
1.1 nbrk 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: }