rf_geniq.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10

    1 /*      $NetBSD: rf_geniq.c,v 1.4 2001/11/13 07:11:14 lukem 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.4 2001/11/13 07:11:14 lukem 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 
   47 lsfr_shift(val, poly)
   48         unsigned val, poly;
   49 {
   50         unsigned new;
   51         unsigned int i;
   52         unsigned high = (val >> 4) & 1;
   53         unsigned bit;
   54 
   55         new = (poly & 1) ? high : 0;
   56 
   57         for (i = 1; i <= 4; i++) {
   58                 bit = (val >> (i - 1)) & 1;
   59                 if (poly & (1 << i))    /* there is a feedback connection */
   60                         new = new | ((bit ^ high) << i);
   61                 else
   62                         new = new | (bit << i);
   63         }
   64         return new;
   65 }
   66 /* generate Q matricies for the data */
   67 
   68 RF_ua32_t rf_qfor[32];
   69 
   70 void 
   71 main()
   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 _RF__RF_INVERTQ_H_\n");
   88         printf("#define _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 (RF_INCLUDE_PQ > 0) || (RF_INCLUDE_RAID6 > 0)\n");
   98         printf("\n");
   99         printf("#define RF_Q_COLS 32\n");
  100         printf("RF_ua32_t rf_rn = {\n");
  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 */ { 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 RF_Q_DATA_COL(col_num) rf_rn[col_num],rf_qfor[28-(col_num)]\n");
  123 
  124         /* generate the inverse tables. (i,j,p,q) */
  125         /* The table just stores a. Get b back from the parity */
  126         printf("#ifdef KERNEL\n");
  127         printf("RF_ua1024_t rf_qinv[1];        /* don't compile monster table into kernel */\n");
  128         printf("#elif defined(NO_PQ)\n");
  129         printf("RF_ua1024_t rf_qinv[29*29];\n");
  130         printf("#else /* !KERNEL && NO_PQ */\n");
  131         printf("RF_ua1024_t rf_qinv[29*29] = {\n");
  132         for (i = 0; i < 29; i++) {
  133                 for (j = 0; j < 29; j++) {
  134                         printf("/* i %d, j %d */{ ", i, j);
  135                         if (i == j)
  136                                 for (l = 0; l < 1023; l++)
  137                                         printf("0, ");
  138                         else {
  139                                 for (p = 0; p < 32; p++)
  140                                         for (q = 0; q < 32; q++) {
  141                                                 /* What are a, b such that a ^
  142                                                  * b =  p; and qfor[(28-i)][a
  143                                                  * ^ rf_rn[i+1]] ^
  144                                                  * qfor[(28-j)][b ^
  145                                                  * rf_rn[j+1]] =  q. Solve by
  146                                                  * guessing a. Then testing. */
  147                                                 for (a = 0; a < 32; a++) {
  148                                                         b = a ^ p;
  149                                                         if ((rf_qfor[28 - i][a ^ k[i + 1]] ^ rf_qfor[28 - j][b ^ k[j + 1]]) == q)
  150                                                                 break;
  151                                                 }
  152                                                 if (a == 32)
  153                                                         printf("unable to solve %d %d %d %d\n", i, j, p, q);
  154                                                 printf("%d,", a);
  155                                         }
  156                         }
  157                         printf("},\n");
  158                 }
  159         }
  160         printf("};\n");
  161         printf("\n#endif /* (RF_INCLUDE_PQ > 0) || (RF_INCLUDE_RAID6 > 0) */\n\n");
  162         printf("#endif /* !KERNEL && NO_PQ */\n");
  163         printf("#endif /* !_RF__RF_INVERTQ_H_ */\n");
  164         exit(0);
  165 }

Cache object: e857a8bd948339db9ce6a0245fd60080

[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.

FreeBSD/Linux Kernel Cross Reference sys/dev/raidframe/rf_geniq.c

FreeBSD/Linux Kernel Cross Reference
sys/dev/raidframe/rf_geniq.c