14e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi/* Common code for intializing a Reed-Solomon control block (char or int symbols) 24e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * Copyright 2004 Phil Karn, KA9Q 34e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * May be used under the terms of the GNU Lesser General Public License (LGPL) 44e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi */ 54e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#undef NULL 64e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#define NULL ((void *)0) 74e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 84e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi{ 94e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi int i, j, sr,root,iprim; 104e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 114e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs = NULL; 124e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Check parameter ranges */ 135767f2ce4658e4207ffacd88a268f79fa7ed0d50Sami Tolvanen if(symsize < 0 || symsize > 8*(int)sizeof(data_t)){ 144e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto done; 154e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 164e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 174e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(fcr < 0 || fcr >= (1<<symsize)) 184e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto done; 194e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(prim <= 0 || prim >= (1<<symsize)) 204e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto done; 214e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(nroots < 0 || nroots >= (1<<symsize)) 224e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto done; /* Can't have more roots than symbol values! */ 234e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(pad < 0 || pad >= ((1<<symsize) -1 - nroots)) 244e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto done; /* Too much padding */ 254e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 264e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs = (struct rs *)calloc(1,sizeof(struct rs)); 274e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(rs == NULL) 284e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto done; 294e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 304e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->mm = symsize; 314e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->nn = (1<<symsize)-1; 324e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->pad = pad; 334e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 344e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->alpha_to = (data_t *)malloc(sizeof(data_t)*(rs->nn+1)); 354e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(rs->alpha_to == NULL){ 364e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi free(rs); 374e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs = NULL; 384e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto done; 394e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 404e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->index_of = (data_t *)malloc(sizeof(data_t)*(rs->nn+1)); 414e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(rs->index_of == NULL){ 424e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi free(rs->alpha_to); 434e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi free(rs); 444e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs = NULL; 454e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto done; 464e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 474e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 484e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Generate Galois field lookup tables */ 494e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->index_of[0] = A0; /* log(zero) = -inf */ 504e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->alpha_to[A0] = 0; /* alpha**-inf = 0 */ 514e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi sr = 1; 524e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(i=0;i<rs->nn;i++){ 534e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->index_of[sr] = i; 544e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->alpha_to[i] = sr; 554e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi sr <<= 1; 564e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(sr & (1<<symsize)) 574e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi sr ^= gfpoly; 584e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi sr &= rs->nn; 594e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 604e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(sr != 1){ 614e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* field generator polynomial is not primitive! */ 624e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi free(rs->alpha_to); 634e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi free(rs->index_of); 644e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi free(rs); 654e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs = NULL; 664e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto done; 674e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 684e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 694e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Form RS code generator polynomial from its roots */ 704e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->genpoly = (data_t *)malloc(sizeof(data_t)*(nroots+1)); 714e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(rs->genpoly == NULL){ 724e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi free(rs->alpha_to); 734e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi free(rs->index_of); 744e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi free(rs); 754e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs = NULL; 764e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto done; 774e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 784e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->fcr = fcr; 794e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->prim = prim; 804e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->nroots = nroots; 814e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 824e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Find prim-th root of 1, used in decoding */ 834e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(iprim=1;(iprim % prim) != 0;iprim += rs->nn) 844e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi ; 854e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->iprim = iprim / prim; 864e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 874e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->genpoly[0] = 1; 884e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (i = 0,root=fcr*prim; i < nroots; i++,root += prim) { 894e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->genpoly[i+1] = 1; 904e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 914e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Multiply rs->genpoly[] by @**(root + x) */ 924e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (j = i; j > 0; j--){ 934e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (rs->genpoly[j] != 0) 944e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->genpoly[j] = rs->genpoly[j-1] ^ rs->alpha_to[modnn(rs,rs->index_of[rs->genpoly[j]] + root)]; 954e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi else 964e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->genpoly[j] = rs->genpoly[j-1]; 974e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 984e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* rs->genpoly[0] can never be zero */ 994e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->genpoly[0] = rs->alpha_to[modnn(rs,rs->index_of[rs->genpoly[0]] + root)]; 1004e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1014e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* convert rs->genpoly[] to index form for quicker encoding */ 1024e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (i = 0; i <= nroots; i++) 1034e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi rs->genpoly[i] = rs->index_of[rs->genpoly[i]]; 1044e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi done:; 1054e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 1064e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi} 107