kernel-lib/mktables.c

   1 /* -*- linux-c -*- ------------------------------------------------------- *
   2  *
   3  *   Copyright 2002-2007 H. Peter Anvin - All Rights Reserved
   4  *
   5  *   This file is part of the Linux kernel, and is made available under
   6  *   the terms of the GNU General Public License version 2 or (at your
   7  *   option) any later version; incorporated herein by reference.
   8  *
   9  * ----------------------------------------------------------------------- */
  10
  11 /*
  12  * mktables.c
  13  *
  14  * Make RAID-6 tables.  This is a host user space program to be run at
  15  * compile time.
  16  */
  17
  18 /*
  19  * Btrfs-progs port, with following minor fixes:
  20  * 1) Use "kerncompat.h"
  21  * 2) Get rid of __KERNEL__ related macros
  22  */
  23
  24 #include <stdio.h>
  25 #include <string.h>
  26 #include <inttypes.h>
  27 #include <stdlib.h>
  28 #include <time.h>
  29
  30 static uint8_t gfmul(uint8_t a, uint8_t b)
  31 {
  32         uint8_t v = 0;
  33
  34         while (b) {
  35                 if (b & 1)
  36                         v ^= a;
  37                 a = (a << 1) ^ (a & 0x80 ? 0x1d : 0);
  38                 b >>= 1;
  39         }
  40
  41         return v;
  42 }
  43
  44 static uint8_t gfpow(uint8_t a, int b)
  45 {
  46         uint8_t v = 1;
  47
  48         b %= 255;
  49         if (b < 0)
  50                 b += 255;
  51
  52         while (b) {
  53                 if (b & 1)
  54                         v = gfmul(v, a);
  55                 a = gfmul(a, a);
  56                 b >>= 1;
  57         }
  58
  59         return v;
  60 }
  61
  62 int main(int argc, char *argv[])
  63 {
  64         int i, j, k;
  65         uint8_t v;
  66         uint8_t exptbl[256], invtbl[256];
  67
  68         printf("#include \"kerncompat.h\"\n");
  69
  70         /* Compute multiplication table */
  71         printf("\nconst u8  __attribute__((aligned(256)))\n"
  72                 "raid6_gfmul[256][256] =\n"
  73                 "{\n");
  74         for (i = 0; i < 256; i++) {
  75                 printf("\t{\n");
  76                 for (j = 0; j < 256; j += 8) {
  77                         printf("\t\t");
  78                         for (k = 0; k < 8; k++)
  79                                 printf("0x%02x,%c", gfmul(i, j + k),
  80                                        (k == 7) ? '\n' : ' ');
  81                 }
  82                 printf("\t},\n");
  83         }
  84         printf("};\n");
  85
  86         /* Compute vector multiplication table */
  87         printf("\nconst u8  __attribute__((aligned(256)))\n"
  88                 "raid6_vgfmul[256][32] =\n"
  89                 "{\n");
  90         for (i = 0; i < 256; i++) {
  91                 printf("\t{\n");
  92                 for (j = 0; j < 16; j += 8) {
  93                         printf("\t\t");
  94                         for (k = 0; k < 8; k++)
  95                                 printf("0x%02x,%c", gfmul(i, j + k),
  96                                        (k == 7) ? '\n' : ' ');
  97                 }
  98                 for (j = 0; j < 16; j += 8) {
  99                         printf("\t\t");
 100                         for (k = 0; k < 8; k++)
 101                                 printf("0x%02x,%c", gfmul(i, (j + k) << 4),
 102                                        (k == 7) ? '\n' : ' ');
 103                 }
 104                 printf("\t},\n");
 105         }
 106         printf("};\n");
 107
 108         /* Compute power-of-2 table (exponent) */
 109         v = 1;
 110         printf("\nconst u8 __attribute__((aligned(256)))\n"
 111                "raid6_gfexp[256] =\n" "{\n");
 112         for (i = 0; i < 256; i += 8) {
 113                 printf("\t");
 114                 for (j = 0; j < 8; j++) {
 115                         exptbl[i + j] = v;
 116                         printf("0x%02x,%c", v, (j == 7) ? '\n' : ' ');
 117                         v = gfmul(v, 2);
 118                         if (v == 1)
 119                                 v = 0;  /* For entry 255, not a real entry */
 120                 }
 121         }
 122         printf("};\n");
 123
 124         /* Compute inverse table x^-1 == x^254 */
 125         printf("\nconst u8 __attribute__((aligned(256)))\n"
 126                "raid6_gfinv[256] =\n" "{\n");
 127         for (i = 0; i < 256; i += 8) {
 128                 printf("\t");
 129                 for (j = 0; j < 8; j++) {
 130                         invtbl[i + j] = v = gfpow(i + j, 254);
 131                         printf("0x%02x,%c", v, (j == 7) ? '\n' : ' ');
 132                 }
 133         }
 134         printf("};\n");
 135
 136         /* Compute inv(2^x + 1) (exponent-xor-inverse) table */
 137         printf("\nconst u8 __attribute__((aligned(256)))\n"
 138                "raid6_gfexi[256] =\n" "{\n");
 139         for (i = 0; i < 256; i += 8) {
 140                 printf("\t");
 141                 for (j = 0; j < 8; j++)
 142                         printf("0x%02x,%c", invtbl[exptbl[i + j] ^ 1],
 143                                (j == 7) ? '\n' : ' ');
 144         }
 145         printf("};\n");
 146
 147         return 0;
 148 }