![[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: }