• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /* Common code for intializing a Reed-Solomon control block (char or int symbols)
2  * Copyright 2004 Phil Karn, KA9Q
3  * May be used under the terms of the GNU Lesser General Public License (LGPL)
4  */
5 #undef NULL
6 #define NULL ((void *)0)
7 
8 {
9   int i, j, sr,root,iprim;
10 
11   rs = NULL;
12   /* Check parameter ranges */
13   if(symsize < 0 || symsize > 8*(int)sizeof(data_t)){
14     goto done;
15   }
16 
17   if(fcr < 0 || fcr >= (1<<symsize))
18     goto done;
19   if(prim <= 0 || prim >= (1<<symsize))
20     goto done;
21   if(nroots < 0 || nroots >= (1<<symsize))
22     goto done; /* Can't have more roots than symbol values! */
23   if(pad < 0 || pad >= ((1<<symsize) -1 - nroots))
24     goto done; /* Too much padding */
25 
26   rs = (struct rs *)calloc(1,sizeof(struct rs));
27   if(rs == NULL)
28     goto done;
29 
30   rs->mm = symsize;
31   rs->nn = (1<<symsize)-1;
32   rs->pad = pad;
33 
34   rs->alpha_to = (data_t *)malloc(sizeof(data_t)*(rs->nn+1));
35   if(rs->alpha_to == NULL){
36     free(rs);
37     rs = NULL;
38     goto done;
39   }
40   rs->index_of = (data_t *)malloc(sizeof(data_t)*(rs->nn+1));
41   if(rs->index_of == NULL){
42     free(rs->alpha_to);
43     free(rs);
44     rs = NULL;
45     goto done;
46   }
47 
48   /* Generate Galois field lookup tables */
49   rs->index_of[0] = A0; /* log(zero) = -inf */
50   rs->alpha_to[A0] = 0; /* alpha**-inf = 0 */
51   sr = 1;
52   for(i=0;i<rs->nn;i++){
53     rs->index_of[sr] = i;
54     rs->alpha_to[i] = sr;
55     sr <<= 1;
56     if(sr & (1<<symsize))
57       sr ^= gfpoly;
58     sr &= rs->nn;
59   }
60   if(sr != 1){
61     /* field generator polynomial is not primitive! */
62     free(rs->alpha_to);
63     free(rs->index_of);
64     free(rs);
65     rs = NULL;
66     goto done;
67   }
68 
69   /* Form RS code generator polynomial from its roots */
70   rs->genpoly = (data_t *)malloc(sizeof(data_t)*(nroots+1));
71   if(rs->genpoly == NULL){
72     free(rs->alpha_to);
73     free(rs->index_of);
74     free(rs);
75     rs = NULL;
76     goto done;
77   }
78   rs->fcr = fcr;
79   rs->prim = prim;
80   rs->nroots = nroots;
81 
82   /* Find prim-th root of 1, used in decoding */
83   for(iprim=1;(iprim % prim) != 0;iprim += rs->nn)
84     ;
85   rs->iprim = iprim / prim;
86 
87   rs->genpoly[0] = 1;
88   for (i = 0,root=fcr*prim; i < nroots; i++,root += prim) {
89     rs->genpoly[i+1] = 1;
90 
91     /* Multiply rs->genpoly[] by  @**(root + x) */
92     for (j = i; j > 0; j--){
93       if (rs->genpoly[j] != 0)
94 	rs->genpoly[j] = rs->genpoly[j-1] ^ rs->alpha_to[modnn(rs,rs->index_of[rs->genpoly[j]] + root)];
95       else
96 	rs->genpoly[j] = rs->genpoly[j-1];
97     }
98     /* rs->genpoly[0] can never be zero */
99     rs->genpoly[0] = rs->alpha_to[modnn(rs,rs->index_of[rs->genpoly[0]] + root)];
100   }
101   /* convert rs->genpoly[] to index form for quicker encoding */
102   for (i = 0; i <= nroots; i++)
103     rs->genpoly[i] = rs->index_of[rs->genpoly[i]];
104  done:;
105 
106 }
107