/*      $NetBSD: rf_geniq.c,v 1.6 2009/03/18 10:22:41 cegger Exp $      */
/*
* Copyright (c) 1995 Carnegie-Mellon University.
* All rights reserved.
*
* Author: Daniel Stodolsky
*
* Permission to use, copy, modify and distribute this software and
* its documentation is hereby granted, provided that both the copyright
* notice and this permission notice appear in all copies of the
* software, derivative works or modified versions, and any portions
* thereof, and that both notices appear in supporting documentation.
*
* CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
* CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
* FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
*
* Carnegie Mellon requests users of this software to return to
*
*  Software Distribution Coordinator  or  [email protected]
*  School of Computer Science
*  Carnegie Mellon University
*  Pittsburgh PA 15213-3890
*
* any improvements or extensions that they make and grant Carnegie the
* rights to redistribute these changes.
*/

/* rf_geniq.c
*  code which implements Reed-Solomon encoding for RAID level 6
*/


#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: rf_geniq.c,v 1.6 2009/03/18 10:22:41 cegger Exp $");

#define RF_UTILITY 1
#include "rf_pqdeg.h"

/*
  five bit lfsr
  poly - feedback connections

  val  = value;
*/
int
lsfr_shift(unsigned val, unsigned poly)
{
       unsigned new;
       unsigned int i;
       unsigned high = (val >> 4) & 1;
       unsigned bit;

       new = (poly & 1) ? high : 0;

       for (i = 1; i <= 4; i++) {
               bit = (val >> (i - 1)) & 1;
               if (poly & (1 << i))    /* there is a feedback connection */
                       new = new | ((bit ^ high) << i);
               else
                       new = new | (bit << i);
       }
       return new;
}
/* generate Q matricies for the data */

RF_ua32_t rf_qfor[32];

void
main(void)
{
       unsigned int i, j, l, a, b;
       unsigned int val;
       unsigned int r;
       unsigned int m, p, q;

       RF_ua32_t k;

       printf("/*\n");
       printf(" * rf_invertq.h\n");
       printf(" */\n");
       printf("/*\n");
       printf(" * GENERATED FILE -- DO NOT EDIT\n");
       printf(" */\n");
       printf("\n");
       printf("#ifndef _RF__RF_INVERTQ_H_\n");
       printf("#define _RF__RF_INVERTQ_H_\n");
       printf("\n");
       printf("/*\n");
       printf(" * rf_geniq.c must include rf_archs.h before including\n");
       printf(" * this file (to get VPATH magic right with the way we\n");
       printf(" * generate this file in kernel trees)\n");
       printf(" */\n");
       printf("/* #include \"rf_archs.h\" */\n");
       printf("\n");
       printf("#if (RF_INCLUDE_PQ > 0) || (RF_INCLUDE_RAID6 > 0)\n");
       printf("\n");
       printf("#define RF_Q_COLS 32\n");
       printf("RF_ua32_t rf_rn = {\n");
       k[0] = 1;
       for (j = 0; j < 31; j++)
               k[j + 1] = lsfr_shift(k[j], 5);
       for (j = 0; j < 32; j++)
               printf("%d, ", k[j]);
       printf("};\n");

       printf("RF_ua32_t rf_qfor[32] = {\n");
       for (i = 0; i < 32; i++) {
               printf("/* i = %d */ { 0, ", i);
               rf_qfor[i][0] = 0;
               for (j = 1; j < 32; j++) {
                       val = j;
                       for (l = 0; l < i; l++)
                               val = lsfr_shift(val, 5);
                       rf_qfor[i][j] = val;
                       printf("%d, ", val);
               }
               printf("},\n");
       }
       printf("};\n");
       printf("#define RF_Q_DATA_COL(col_num) rf_rn[col_num],rf_qfor[28-(col_num)]\n");

       /* generate the inverse tables. (i,j,p,q) */
       /* The table just stores a. Get b back from the parity */
       printf("#ifdef KERNEL\n");
       printf("RF_ua1024_t rf_qinv[1];        /* don't compile monster table into kernel */\n");
       printf("#elif defined(NO_PQ)\n");
       printf("RF_ua1024_t rf_qinv[29*29];\n");
       printf("#else /* !KERNEL && NO_PQ */\n");
       printf("RF_ua1024_t rf_qinv[29*29] = {\n");
       for (i = 0; i < 29; i++) {
               for (j = 0; j < 29; j++) {
                       printf("/* i %d, j %d */{ ", i, j);
                       if (i == j)
                               for (l = 0; l < 1023; l++)
                                       printf("0, ");
                       else {
                               for (p = 0; p < 32; p++)
                                       for (q = 0; q < 32; q++) {
                                               /* What are a, b such that a ^
                                                * b =  p; and qfor[(28-i)][a
                                                * ^ rf_rn[i+1]] ^
                                                * qfor[(28-j)][b ^
                                                * rf_rn[j+1]] =  q. Solve by
                                                * guessing a. Then testing. */
                                               for (a = 0; a < 32; a++) {
                                                       b = a ^ p;
                                                       if ((rf_qfor[28 - i][a ^ k[i + 1]] ^ rf_qfor[28 - j][b ^ k[j + 1]]) == q)
                                                               break;
                                               }
                                               if (a == 32)
                                                       printf("unable to solve %d %d %d %d\n", i, j, p, q);
                                               printf("%d,", a);
                                       }
                       }
                       printf("},\n");
               }
       }
       printf("};\n");
       printf("\n#endif /* (RF_INCLUDE_PQ > 0) || (RF_INCLUDE_RAID6 > 0) */\n\n");
       printf("#endif /* !KERNEL && NO_PQ */\n");
       printf("#endif /* !_RF__RF_INVERTQ_H_ */\n");
       exit(0);
}