From 5d69a524f81f234b3fbc41d49ba18d6f6886baba Mon Sep 17 00:00:00 2001
From: jcorgan
Date: Thu, 3 Aug 2006 04:51:51 +0000
Subject: Houston, we have a trunk.

git-svn-id: http://gnuradio.org/svn/gnuradio/trunk@3122 221aa14e-8319-0410-a670-987f0aec2ac5
---
 gnuradio-core/src/lib/reed-solomon/decode_rs.c | 262 +++++++++++++++++++++++++
 1 file changed, 262 insertions(+)
 create mode 100644 gnuradio-core/src/lib/reed-solomon/decode_rs.c

(limited to 'gnuradio-core/src/lib/reed-solomon/decode_rs.c')

diff --git a/gnuradio-core/src/lib/reed-solomon/decode_rs.c b/gnuradio-core/src/lib/reed-solomon/decode_rs.c
new file mode 100644
index 000000000..ca409782f
--- /dev/null
+++ b/gnuradio-core/src/lib/reed-solomon/decode_rs.c
@@ -0,0 +1,262 @@
+/* Reed-Solomon decoder
+ * Copyright 2002 Phil Karn, KA9Q
+ * May be used under the terms of the GNU General Public License (GPL)
+ */
+
+#ifdef DEBUG
+#include <stdio.h>
+#endif
+
+#include <string.h>
+
+#define NULL ((void *)0)
+#define	min(a,b)	((a) < (b) ? (a) : (b))
+
+#ifdef FIXED
+#include "fixed.h"
+#elif defined(BIGSYM)
+#include "int.h"
+#else
+#include "char.h"
+#endif
+
+int DECODE_RS(
+#ifndef FIXED
+void *p,
+#endif
+DTYPE *data, int *eras_pos, int no_eras){
+
+#ifndef FIXED
+  struct rs *rs = (struct rs *)p;
+#endif
+  int deg_lambda, el, deg_omega;
+  int i, j, r,k;
+  DTYPE u,q,tmp,num1,num2,den,discr_r;
+  DTYPE lambda[NROOTS+1], s[NROOTS];	/* Err+Eras Locator poly
+					 * and syndrome poly */
+  DTYPE b[NROOTS+1], t[NROOTS+1], omega[NROOTS+1];
+  DTYPE root[NROOTS], reg[NROOTS+1], loc[NROOTS];
+  int syn_error, count;
+
+  /* form the syndromes; i.e., evaluate data(x) at roots of g(x) */
+  for(i=0;i<NROOTS;i++)
+    s[i] = data[0];
+
+  for(j=1;j<NN;j++){
+    for(i=0;i<NROOTS;i++){
+      if(s[i] == 0){
+	s[i] = data[j];
+      } else {
+	s[i] = data[j] ^ ALPHA_TO[MODNN(INDEX_OF[s[i]] + (FCR+i)*PRIM)];
+      }
+    }
+  }
+
+  /* Convert syndromes to index form, checking for nonzero condition */
+  syn_error = 0;
+  for(i=0;i<NROOTS;i++){
+    syn_error |= s[i];
+    s[i] = INDEX_OF[s[i]];
+  }
+
+  if (!syn_error) {
+    /* if syndrome is zero, data[] is a codeword and there are no
+     * errors to correct. So return data[] unmodified
+     */
+    count = 0;
+    goto finish;
+  }
+  memset(&lambda[1],0,NROOTS*sizeof(lambda[0]));
+  lambda[0] = 1;
+
+  if (no_eras > 0) {
+    /* Init lambda to be the erasure locator polynomial */
+    lambda[1] = ALPHA_TO[MODNN(PRIM*(NN-1-eras_pos[0]))];
+    for (i = 1; i < no_eras; i++) {
+      u = MODNN(PRIM*(NN-1-eras_pos[i]));
+      for (j = i+1; j > 0; j--) {
+	tmp = INDEX_OF[lambda[j - 1]];
+	if(tmp != A0)
+	  lambda[j] ^= ALPHA_TO[MODNN(u + tmp)];
+      }
+    }
+
+#if DEBUG >= 1
+    /* Test code that verifies the erasure locator polynomial just constructed
+       Needed only for decoder debugging. */
+    
+    /* find roots of the erasure location polynomial */
+    for(i=1;i<=no_eras;i++)
+      reg[i] = INDEX_OF[lambda[i]];
+
+    count = 0;
+    for (i = 1,k=IPRIM-1; i <= NN; i++,k = MODNN(k+IPRIM)) {
+      q = 1;
+      for (j = 1; j <= no_eras; j++)
+	if (reg[j] != A0) {
+	  reg[j] = MODNN(reg[j] + j);
+	  q ^= ALPHA_TO[reg[j]];
+	}
+      if (q != 0)
+	continue;
+      /* store root and error location number indices */
+      root[count] = i;
+      loc[count] = k;
+      count++;
+    }
+    if (count != no_eras) {
+      printf("count = %d no_eras = %d\n lambda(x) is WRONG\n",count,no_eras);
+      count = -1;
+      goto finish;
+    }
+#if DEBUG >= 2
+    printf("\n Erasure positions as determined by roots of Eras Loc Poly:\n");
+    for (i = 0; i < count; i++)
+      printf("%d ", loc[i]);
+    printf("\n");
+#endif
+#endif
+  }
+  for(i=0;i<NROOTS+1;i++)
+    b[i] = INDEX_OF[lambda[i]];
+  
+  /*
+   * Begin Berlekamp-Massey algorithm to determine error+erasure
+   * locator polynomial
+   */
+  r = no_eras;
+  el = no_eras;
+  while (++r <= NROOTS) {	/* r is the step number */
+    /* Compute discrepancy at the r-th step in poly-form */
+    discr_r = 0;
+    for (i = 0; i < r; i++){
+      if ((lambda[i] != 0) && (s[r-i-1] != A0)) {
+	discr_r ^= ALPHA_TO[MODNN(INDEX_OF[lambda[i]] + s[r-i-1])];
+      }
+    }
+    discr_r = INDEX_OF[discr_r];	/* Index form */
+    if (discr_r == A0) {
+      /* 2 lines below: B(x) <-- x*B(x) */
+      memmove(&b[1],b,NROOTS*sizeof(b[0]));
+      b[0] = A0;
+    } else {
+      /* 7 lines below: T(x) <-- lambda(x) - discr_r*x*b(x) */
+      t[0] = lambda[0];
+      for (i = 0 ; i < NROOTS; i++) {
+	if(b[i] != A0)
+	  t[i+1] = lambda[i+1] ^ ALPHA_TO[MODNN(discr_r + b[i])];
+	else
+	  t[i+1] = lambda[i+1];
+      }
+      if (2 * el <= r + no_eras - 1) {
+	el = r + no_eras - el;
+	/*
+	 * 2 lines below: B(x) <-- inv(discr_r) *
+	 * lambda(x)
+	 */
+	for (i = 0; i <= NROOTS; i++)
+	  b[i] = (lambda[i] == 0) ? A0 : MODNN(INDEX_OF[lambda[i]] - discr_r + NN);
+      } else {
+	/* 2 lines below: B(x) <-- x*B(x) */
+	memmove(&b[1],b,NROOTS*sizeof(b[0]));
+	b[0] = A0;
+      }
+      memcpy(lambda,t,(NROOTS+1)*sizeof(t[0]));
+    }
+  }
+
+  /* Convert lambda to index form and compute deg(lambda(x)) */
+  deg_lambda = 0;
+  for(i=0;i<NROOTS+1;i++){
+    lambda[i] = INDEX_OF[lambda[i]];
+    if(lambda[i] != A0)
+      deg_lambda = i;
+  }
+  /* Find roots of the error+erasure locator polynomial by Chien search */
+  memcpy(&reg[1],&lambda[1],NROOTS*sizeof(reg[0]));
+  count = 0;		/* Number of roots of lambda(x) */
+  for (i = 1,k=IPRIM-1; i <= NN; i++,k = MODNN(k+IPRIM)) {
+    q = 1; /* lambda[0] is always 0 */
+    for (j = deg_lambda; j > 0; j--){
+      if (reg[j] != A0) {
+	reg[j] = MODNN(reg[j] + j);
+	q ^= ALPHA_TO[reg[j]];
+      }
+    }
+    if (q != 0)
+      continue; /* Not a root */
+    /* store root (index-form) and error location number */
+#if DEBUG>=2
+    printf("count %d root %d loc %d\n",count,i,k);
+#endif
+    root[count] = i;
+    loc[count] = k;
+    /* If we've already found max possible roots,
+     * abort the search to save time
+     */
+    if(++count == deg_lambda)
+      break;
+  }
+  if (deg_lambda != count) {
+    /*
+     * deg(lambda) unequal to number of roots => uncorrectable
+     * error detected
+     */
+    count = -1;
+    goto finish;
+  }
+  /*
+   * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo
+   * x**NROOTS). in index form. Also find deg(omega).
+   */
+  deg_omega = 0;
+  for (i = 0; i < NROOTS;i++){
+    tmp = 0;
+    j = (deg_lambda < i) ? deg_lambda : i;
+    for(;j >= 0; j--){
+      if ((s[i - j] != A0) && (lambda[j] != A0))
+	tmp ^= ALPHA_TO[MODNN(s[i - j] + lambda[j])];
+    }
+    if(tmp != 0)
+      deg_omega = i;
+    omega[i] = INDEX_OF[tmp];
+  }
+  omega[NROOTS] = A0;
+  
+  /*
+   * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
+   * inv(X(l))**(FCR-1) and den = lambda_pr(inv(X(l))) all in poly-form
+   */
+  for (j = count-1; j >=0; j--) {
+    num1 = 0;
+    for (i = deg_omega; i >= 0; i--) {
+      if (omega[i] != A0)
+	num1  ^= ALPHA_TO[MODNN(omega[i] + i * root[j])];
+    }
+    num2 = ALPHA_TO[MODNN(root[j] * (FCR - 1) + NN)];
+    den = 0;
+    
+    /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */
+    for (i = min(deg_lambda,NROOTS-1) & ~1; i >= 0; i -=2) {
+      if(lambda[i+1] != A0)
+	den ^= ALPHA_TO[MODNN(lambda[i+1] + i * root[j])];
+    }
+    if (den == 0) {
+#if DEBUG >= 1
+      printf("\n ERROR: denominator = 0\n");
+#endif
+      count = -1;
+      goto finish;
+    }
+    /* Apply error to data */
+    if (num1 != 0) {
+      data[loc[j]] ^= ALPHA_TO[MODNN(INDEX_OF[num1] + INDEX_OF[num2] + NN - INDEX_OF[den])];
+    }
+  }
+ finish:
+  if(eras_pos != NULL){
+    for(i=0;i<count;i++)
+      eras_pos[i] = loc[i];
+  }
+  return count;
+}
-- 
cgit 


From 38ea3a576a20820e574c6cb37607aeafe07f34b4 Mon Sep 17 00:00:00 2001
From: eb
Date: Wed, 30 Apr 2008 02:24:06 +0000
Subject: Tweaks for gcc 4.3 based on patch from Marek Mahut
 <mmahut@fedoraproject.org>.

git-svn-id: http://gnuradio.org/svn/gnuradio/trunk@8292 221aa14e-8319-0410-a670-987f0aec2ac5
---
 gnuradio-core/src/lib/reed-solomon/decode_rs.c | 1 +
 1 file changed, 1 insertion(+)

(limited to 'gnuradio-core/src/lib/reed-solomon/decode_rs.c')

diff --git a/gnuradio-core/src/lib/reed-solomon/decode_rs.c b/gnuradio-core/src/lib/reed-solomon/decode_rs.c
index ca409782f..27ddd8532 100644
--- a/gnuradio-core/src/lib/reed-solomon/decode_rs.c
+++ b/gnuradio-core/src/lib/reed-solomon/decode_rs.c
@@ -8,6 +8,7 @@
 #endif
 
 #include <string.h>
+#include <strings.h>
 
 #define NULL ((void *)0)
 #define	min(a,b)	((a) < (b) ? (a) : (b))
-- 
cgit 


From d0a611585d3a44d1a432f3e5692feeb984ad0123 Mon Sep 17 00:00:00 2001
From: Josh Blum
Date: Wed, 20 Jul 2011 18:05:06 -0700
Subject: core: removed files that included <strings.h>

---
 gnuradio-core/src/lib/reed-solomon/decode_rs.c | 1 -
 1 file changed, 1 deletion(-)

(limited to 'gnuradio-core/src/lib/reed-solomon/decode_rs.c')

diff --git a/gnuradio-core/src/lib/reed-solomon/decode_rs.c b/gnuradio-core/src/lib/reed-solomon/decode_rs.c
index 27ddd8532..ca409782f 100644
--- a/gnuradio-core/src/lib/reed-solomon/decode_rs.c
+++ b/gnuradio-core/src/lib/reed-solomon/decode_rs.c
@@ -8,7 +8,6 @@
 #endif
 
 #include <string.h>
-#include <strings.h>
 
 #define NULL ((void *)0)
 #define	min(a,b)	((a) < (b) ? (a) : (b))
-- 
cgit 


From 8abd6a443e72439f4c7e77bc0c6f5b54bb70f8e7 Mon Sep 17 00:00:00 2001
From: Josh Blum
Date: Wed, 3 Aug 2011 00:12:43 -0700
Subject: rs: reasonable workaround for compiling reed-solomon under MSVC

---
 gnuradio-core/src/lib/reed-solomon/decode_rs.c | 8 ++++++++
 1 file changed, 8 insertions(+)

(limited to 'gnuradio-core/src/lib/reed-solomon/decode_rs.c')

diff --git a/gnuradio-core/src/lib/reed-solomon/decode_rs.c b/gnuradio-core/src/lib/reed-solomon/decode_rs.c
index ca409782f..ba60b89ee 100644
--- a/gnuradio-core/src/lib/reed-solomon/decode_rs.c
+++ b/gnuradio-core/src/lib/reed-solomon/decode_rs.c
@@ -31,11 +31,19 @@ DTYPE *data, int *eras_pos, int no_eras){
 #endif
   int deg_lambda, el, deg_omega;
   int i, j, r,k;
+#ifdef MAX_ARRAY
+  DTYPE u,q,tmp,num1,num2,den,discr_r;
+  DTYPE lambda[MAX_ARRAY], s[MAX_ARRAY];	/* Err+Eras Locator poly
+					 * and syndrome poly */
+  DTYPE b[MAX_ARRAY], t[MAX_ARRAY], omega[MAX_ARRAY];
+  DTYPE root[MAX_ARRAY], reg[MAX_ARRAY], loc[MAX_ARRAY];
+#else
   DTYPE u,q,tmp,num1,num2,den,discr_r;
   DTYPE lambda[NROOTS+1], s[NROOTS];	/* Err+Eras Locator poly
 					 * and syndrome poly */
   DTYPE b[NROOTS+1], t[NROOTS+1], omega[NROOTS+1];
   DTYPE root[NROOTS], reg[NROOTS+1], loc[NROOTS];
+#endif
   int syn_error, count;
 
   /* form the syndromes; i.e., evaluate data(x) at roots of g(x) */
-- 
cgit 


From 9c853b962d73565f2980789a32f347309bcc605f Mon Sep 17 00:00:00 2001
From: Tom Rondeau
Date: Tue, 25 Oct 2011 14:50:14 -0400
Subject: reed-solomon: fixed the signed/unsigned warnings in the RS code.

Some of these had to be done through type-casting since changing
the actual data type would cause the tests to fail. make test
still passes.
---
 gnuradio-core/src/lib/reed-solomon/decode_rs.c | 26 +++++++++++++-------------
 1 file changed, 13 insertions(+), 13 deletions(-)

(limited to 'gnuradio-core/src/lib/reed-solomon/decode_rs.c')

diff --git a/gnuradio-core/src/lib/reed-solomon/decode_rs.c b/gnuradio-core/src/lib/reed-solomon/decode_rs.c
index ba60b89ee..4b7d27cec 100644
--- a/gnuradio-core/src/lib/reed-solomon/decode_rs.c
+++ b/gnuradio-core/src/lib/reed-solomon/decode_rs.c
@@ -30,7 +30,7 @@ DTYPE *data, int *eras_pos, int no_eras){
   struct rs *rs = (struct rs *)p;
 #endif
   int deg_lambda, el, deg_omega;
-  int i, j, r,k;
+  int i, j, r, k;
 #ifdef MAX_ARRAY
   DTYPE u,q,tmp,num1,num2,den,discr_r;
   DTYPE lambda[MAX_ARRAY], s[MAX_ARRAY];	/* Err+Eras Locator poly
@@ -47,11 +47,11 @@ DTYPE *data, int *eras_pos, int no_eras){
   int syn_error, count;
 
   /* form the syndromes; i.e., evaluate data(x) at roots of g(x) */
-  for(i=0;i<NROOTS;i++)
+  for(i=0;(unsigned int)i<NROOTS;i++)
     s[i] = data[0];
 
-  for(j=1;j<NN;j++){
-    for(i=0;i<NROOTS;i++){
+  for(j=1;(unsigned int)j<NN;j++){
+    for(i=0;(unsigned int)i<NROOTS;i++){
       if(s[i] == 0){
 	s[i] = data[j];
       } else {
@@ -62,7 +62,7 @@ DTYPE *data, int *eras_pos, int no_eras){
 
   /* Convert syndromes to index form, checking for nonzero condition */
   syn_error = 0;
-  for(i=0;i<NROOTS;i++){
+  for(i=0;(unsigned int)i<NROOTS;i++){
     syn_error |= s[i];
     s[i] = INDEX_OF[s[i]];
   }
@@ -125,7 +125,7 @@ DTYPE *data, int *eras_pos, int no_eras){
 #endif
 #endif
   }
-  for(i=0;i<NROOTS+1;i++)
+  for(i=0;(unsigned int)i<NROOTS+1;i++)
     b[i] = INDEX_OF[lambda[i]];
   
   /*
@@ -134,7 +134,7 @@ DTYPE *data, int *eras_pos, int no_eras){
    */
   r = no_eras;
   el = no_eras;
-  while (++r <= NROOTS) {	/* r is the step number */
+  while ((unsigned int)(++r) <= NROOTS) {	/* r is the step number */
     /* Compute discrepancy at the r-th step in poly-form */
     discr_r = 0;
     for (i = 0; i < r; i++){
@@ -150,7 +150,7 @@ DTYPE *data, int *eras_pos, int no_eras){
     } else {
       /* 7 lines below: T(x) <-- lambda(x) - discr_r*x*b(x) */
       t[0] = lambda[0];
-      for (i = 0 ; i < NROOTS; i++) {
+      for (i = 0 ; (unsigned int)i < NROOTS; i++) {
 	if(b[i] != A0)
 	  t[i+1] = lambda[i+1] ^ ALPHA_TO[MODNN(discr_r + b[i])];
 	else
@@ -162,7 +162,7 @@ DTYPE *data, int *eras_pos, int no_eras){
 	 * 2 lines below: B(x) <-- inv(discr_r) *
 	 * lambda(x)
 	 */
-	for (i = 0; i <= NROOTS; i++)
+	for (i = 0; (unsigned int)i <= NROOTS; i++)
 	  b[i] = (lambda[i] == 0) ? A0 : MODNN(INDEX_OF[lambda[i]] - discr_r + NN);
       } else {
 	/* 2 lines below: B(x) <-- x*B(x) */
@@ -175,7 +175,7 @@ DTYPE *data, int *eras_pos, int no_eras){
 
   /* Convert lambda to index form and compute deg(lambda(x)) */
   deg_lambda = 0;
-  for(i=0;i<NROOTS+1;i++){
+  for(i=0;(unsigned int)i<NROOTS+1;i++){
     lambda[i] = INDEX_OF[lambda[i]];
     if(lambda[i] != A0)
       deg_lambda = i;
@@ -183,7 +183,7 @@ DTYPE *data, int *eras_pos, int no_eras){
   /* Find roots of the error+erasure locator polynomial by Chien search */
   memcpy(&reg[1],&lambda[1],NROOTS*sizeof(reg[0]));
   count = 0;		/* Number of roots of lambda(x) */
-  for (i = 1,k=IPRIM-1; i <= NN; i++,k = MODNN(k+IPRIM)) {
+  for (i = 1,k=IPRIM-1; (unsigned int)i <= NN; i++,k = MODNN(k+IPRIM)) {
     q = 1; /* lambda[0] is always 0 */
     for (j = deg_lambda; j > 0; j--){
       if (reg[j] != A0) {
@@ -218,7 +218,7 @@ DTYPE *data, int *eras_pos, int no_eras){
    * x**NROOTS). in index form. Also find deg(omega).
    */
   deg_omega = 0;
-  for (i = 0; i < NROOTS;i++){
+  for (i = 0; (unsigned int)i < NROOTS;i++){
     tmp = 0;
     j = (deg_lambda < i) ? deg_lambda : i;
     for(;j >= 0; j--){
@@ -245,7 +245,7 @@ DTYPE *data, int *eras_pos, int no_eras){
     den = 0;
     
     /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */
-    for (i = min(deg_lambda,NROOTS-1) & ~1; i >= 0; i -=2) {
+    for (i = (int)min((unsigned int)deg_lambda,NROOTS-1) & ~1; i >= 0; i -=2) {
       if(lambda[i+1] != A0)
 	den ^= ALPHA_TO[MODNN(lambda[i+1] + i * root[j])];
     }
-- 
cgit 


From f919f9dcbb54a08e6e26d6c229ce92fb784fa1b2 Mon Sep 17 00:00:00 2001
From: Tom Rondeau
Date: Fri, 13 Apr 2012 18:36:53 -0400
Subject: Removed whitespace and added dtools/bin/remove-whitespace as a tool
 to do this in the future.

The sed script was provided by Moritz Fischer.
---
 gnuradio-core/src/lib/reed-solomon/decode_rs.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

(limited to 'gnuradio-core/src/lib/reed-solomon/decode_rs.c')

diff --git a/gnuradio-core/src/lib/reed-solomon/decode_rs.c b/gnuradio-core/src/lib/reed-solomon/decode_rs.c
index 4b7d27cec..f9438cf26 100644
--- a/gnuradio-core/src/lib/reed-solomon/decode_rs.c
+++ b/gnuradio-core/src/lib/reed-solomon/decode_rs.c
@@ -92,7 +92,7 @@ DTYPE *data, int *eras_pos, int no_eras){
 #if DEBUG >= 1
     /* Test code that verifies the erasure locator polynomial just constructed
        Needed only for decoder debugging. */
-    
+
     /* find roots of the erasure location polynomial */
     for(i=1;i<=no_eras;i++)
       reg[i] = INDEX_OF[lambda[i]];
@@ -127,7 +127,7 @@ DTYPE *data, int *eras_pos, int no_eras){
   }
   for(i=0;(unsigned int)i<NROOTS+1;i++)
     b[i] = INDEX_OF[lambda[i]];
-  
+
   /*
    * Begin Berlekamp-Massey algorithm to determine error+erasure
    * locator polynomial
@@ -230,7 +230,7 @@ DTYPE *data, int *eras_pos, int no_eras){
     omega[i] = INDEX_OF[tmp];
   }
   omega[NROOTS] = A0;
-  
+
   /*
    * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
    * inv(X(l))**(FCR-1) and den = lambda_pr(inv(X(l))) all in poly-form
@@ -243,7 +243,7 @@ DTYPE *data, int *eras_pos, int no_eras){
     }
     num2 = ALPHA_TO[MODNN(root[j] * (FCR - 1) + NN)];
     den = 0;
-    
+
     /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */
     for (i = (int)min((unsigned int)deg_lambda,NROOTS-1) & ~1; i >= 0; i -=2) {
       if(lambda[i+1] != A0)
-- 
cgit