Bill Yi | 4e213d5 | 2015-06-23 13:53:11 -0700 | [diff] [blame] | 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 */ |
Sami Tolvanen | 5767f2c | 2015-06-24 09:35:22 +0100 | [diff] [blame] | 13 | if(symsize < 0 || symsize > 8*(int)sizeof(data_t)){ |
Bill Yi | 4e213d5 | 2015-06-23 13:53:11 -0700 | [diff] [blame] | 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 | } |