flight/libraries/rscode/galois.c

   1 /*****************************
   2  * Copyright Henry Minsky (hqm@alum.mit.edu) 1991-2009
   3  *
   4  * This software library is licensed under terms of the GNU GENERAL
   5  * PUBLIC LICENSE
   6  *
   7  * RSCODE is free software: you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation, either version 3 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * RSCODE is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Rscode.  If not, see <http://www.gnu.org/licenses/>.
  19
  20  * Commercial licensing is available under a separate license, please
  21  * contact author for details.
  22  *
  23  * Source code is available at http://rscode.sourceforge.net
  24  *
  25  *
  26  * Multiplication and Arithmetic on Galois Field GF(256)
  27  *
  28  * From Mee, Daniel, "Magnetic Recording, Volume III", Ch. 5 by Patel.
  29  *
  30  *
  31  ******************************/
  32
  33
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36 #include "ecc.h"
  37
  38 /* This is one of 14 irreducible polynomials
  39  * of degree 8 and cycle length 255. (Ch 5, pp. 275, Magnetic Recording)
  40  * The high order 1 bit is implicit */
  41 /* x^8 + x^4 + x^3 + x^2 + 1 */
  42 #define PPOLY 0x1D
  43
  44
  45 const int gexp[512] = {
  46           1,   2,   4,   8,  16,  32,  64, 128,  29,  58, 116, 232, 205, 135,  19,  38,
  47          76, 152,  45,  90, 180, 117, 234, 201, 143,   3,   6,  12,  24,  48,  96, 192,
  48         157,  39,  78, 156,  37,  74, 148,  53, 106, 212, 181, 119, 238, 193, 159,  35,
  49          70, 140,   5,  10,  20,  40,  80, 160,  93, 186, 105, 210, 185, 111, 222, 161,
  50          95, 190,  97, 194, 153,  47,  94, 188, 101, 202, 137,  15,  30,  60, 120, 240,
  51         253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163,  91, 182, 113, 226,
  52         217, 175,  67, 134,  17,  34,  68, 136,  13,  26,  52, 104, 208, 189, 103, 206,
  53         129,  31,  62, 124, 248, 237, 199, 147,  59, 118, 236, 197, 151,  51, 102, 204,
  54         133,  23,  46,  92, 184, 109, 218, 169,  79, 158,  33,  66, 132,  21,  42,  84,
  55         168,  77, 154,  41,  82, 164,  85, 170,  73, 146,  57, 114, 228, 213, 183, 115,
  56         230, 209, 191,  99, 198, 145,  63, 126, 252, 229, 215, 179, 123, 246, 241, 255,
  57         227, 219, 171,  75, 150,  49,  98, 196, 149,  55, 110, 220, 165,  87, 174,  65,
  58         130,  25,  50, 100, 200, 141,   7,  14,  28,  56, 112, 224, 221, 167,  83, 166,
  59          81, 162,  89, 178, 121, 242, 249, 239, 195, 155,  43,  86, 172,  69, 138,   9,
  60          18,  36,  72, 144,  61, 122, 244, 245, 247, 243, 251, 235, 203, 139,  11,  22,
  61          44,  88, 176, 125, 250, 233, 207, 131,  27,  54, 108, 216, 173,  71, 142,   1,
  62           2,   4,   8,  16,  32,  64, 128,  29,  58, 116, 232, 205, 135,  19,  38,  76,
  63         152,  45,  90, 180, 117, 234, 201, 143,   3,   6,  12,  24,  48,  96, 192, 157,
  64          39,  78, 156,  37,  74, 148,  53, 106, 212, 181, 119, 238, 193, 159,  35,  70,
  65         140,   5,  10,  20,  40,  80, 160,  93, 186, 105, 210, 185, 111, 222, 161,  95,
  66         190,  97, 194, 153,  47,  94, 188, 101, 202, 137,  15,  30,  60, 120, 240, 253,
  67         231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163,  91, 182, 113, 226, 217,
  68         175,  67, 134,  17,  34,  68, 136,  13,  26,  52, 104, 208, 189, 103, 206, 129,
  69          31,  62, 124, 248, 237, 199, 147,  59, 118, 236, 197, 151,  51, 102, 204, 133,
  70          23,  46,  92, 184, 109, 218, 169,  79, 158,  33,  66, 132,  21,  42,  84, 168,
  71          77, 154,  41,  82, 164,  85, 170,  73, 146,  57, 114, 228, 213, 183, 115, 230,
  72         209, 191,  99, 198, 145,  63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227,
  73         219, 171,  75, 150,  49,  98, 196, 149,  55, 110, 220, 165,  87, 174,  65, 130,
  74          25,  50, 100, 200, 141,   7,  14,  28,  56, 112, 224, 221, 167,  83, 166,  81,
  75         162,  89, 178, 121, 242, 249, 239, 195, 155,  43,  86, 172,  69, 138,   9,  18,
  76          36,  72, 144,  61, 122, 244, 245, 247, 243, 251, 235, 203, 139,  11,  22,  44,
  77          88, 176, 125, 250, 233, 207, 131,  27,  54, 108, 216, 173,  71, 142,   1,   0,
  78 };
  79 const int glog[256] = {
  80           0,   0,   1,  25,   2,  50,  26, 198,   3, 223,  51, 238,  27, 104, 199,  75,
  81           4, 100, 224,  14,  52, 141, 239, 129,  28, 193, 105, 248, 200,   8,  76, 113,
  82           5, 138, 101,  47, 225,  36,  15,  33,  53, 147, 142, 218, 240,  18, 130,  69,
  83          29, 181, 194, 125, 106,  39, 249, 185, 201, 154,   9, 120,  77, 228, 114, 166,
  84           6, 191, 139,  98, 102, 221,  48, 253, 226, 152,  37, 179,  16, 145,  34, 136,
  85          54, 208, 148, 206, 143, 150, 219, 189, 241, 210,  19,  92, 131,  56,  70,  64,
  86          30,  66, 182, 163, 195,  72, 126, 110, 107,  58,  40,  84, 250, 133, 186,  61,
  87         202,  94, 155, 159,  10,  21, 121,  43,  78, 212, 229, 172, 115, 243, 167,  87,
  88           7, 112, 192, 247, 140, 128,  99,  13, 103,  74, 222, 237,  49, 197, 254,  24,
  89         227, 165, 153, 119,  38, 184, 180, 124,  17,  68, 146, 217,  35,  32, 137,  46,
  90          55,  63, 209,  91, 149, 188, 207, 205, 144, 135, 151, 178, 220, 252, 190,  97,
  91         242,  86, 211, 171,  20,  42,  93, 158, 132,  60,  57,  83,  71, 109,  65, 162,
  92          31,  45,  67, 216, 183, 123, 164, 118, 196,  23,  73, 236, 127,  12, 111, 246,
  93         108, 161,  59,  82,  41, 157,  85, 170, 251,  96, 134, 177, 187, 204,  62,  90,
  94         203,  89,  95, 176, 156, 169, 160,  81,  11, 245,  22, 235, 122, 117,  44, 215,
  95          79, 174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168,  80,  88, 175,
  96 };
  97
  98
  99 //static void init_exp_table (void);
 100
 101
 102 void
 103 init_galois_tables (void)
 104 {
 105   /* initialize the table of powers of alpha */
 106   //init_exp_table();
 107 }
 108
 109
 110 #ifdef NEVER
 111 static void
 112 init_exp_table (void)
 113 {
 114   int i, z;
 115   int pinit,p1,p2,p3,p4,p5,p6,p7,p8;
 116
 117   pinit = p2 = p3 = p4 = p5 = p6 = p7 = p8 = 0;
 118   p1 = 1;
 119
 120   gexp[0] = 1;
 121   gexp[255] = gexp[0];
 122   glog[0] = 0;                  /* shouldn't log[0] be an error? */
 123
 124   for (i = 1; i < 256; i++) {
 125     pinit = p8;
 126     p8 = p7;
 127     p7 = p6;
 128     p6 = p5;
 129     p5 = p4 ^ pinit;
 130     p4 = p3 ^ pinit;
 131     p3 = p2 ^ pinit;
 132     p2 = p1;
 133     p1 = pinit;
 134     gexp[i] = p1 + p2*2 + p3*4 + p4*8 + p5*16 + p6*32 + p7*64 + p8*128;
 135     gexp[i+255] = gexp[i];
 136   }
 137
 138   for (i = 1; i < 256; i++) {
 139     for (z = 0; z < 256; z++) {
 140       if (gexp[z] == i) {
 141         glog[i] = z;
 142         break;
 143       }
 144     }
 145   }
 146 }
 147 #endif
 148
 149 /* multiplication using logarithms */
 150 int gmult(int a, int b)
 151 {
 152   int i,j;
 153   if (a==0 || b == 0) return (0);
 154   i = glog[a];
 155   j = glog[b];
 156   return (gexp[i+j]);
 157 }
 158
 159
 160 int ginv (int elt)
 161 {
 162   return (gexp[255-glog[elt]]);
 163 }
 164