Size optimizations for Golay decoder and code/file cleanup

(~242 byte arm library for decode)
szabolor · Sep 7, 2015 · d08266b · d08266b
1 parent 2b7e81f
commit d08266b
Show file tree

Hide file tree

Showing 7 changed files with 56 additions and 31 deletions.
diff --git a/.gitignore b/.gitignore
@@ -3,4 +3,4 @@
 !*/
 
 *.o
-
+private
diff --git a/smog_uplink/golay_test b/smog_uplink/golay_test
diff --git a/smog_uplink/libgolayarm.o b/smog_uplink/libgolayarm.o
diff --git a/smog_uplink/ref_encdec b/smog_uplink/ref_encdec
diff --git a/smog_uplink/ref_encdec.c b/smog_uplink/ref_encdec.c
@@ -1,8 +1,21 @@
+/*
+ * This work based on Hank Wallace article (http://www.aqdi.com/golay.htm) on Golay code
+ */
+
+/*
+ * Revised and modified by szabolor
+ * 2015
+ */
+
 #include <stdio.h>
 #include <stdlib.h>
 #include <stdint.h>
+#include "ref_encdec.h"
+
+// compile with: arm-none-eabi-gcc -o libgolay_arm_2.o -c -fPIC -Os -mcpu=cortex-m3 -mthumb --specs=nosys.specs -Wall -Wextra ref_encdec.c
 
 // Cyclic code: generator polynomial 0xC75 (or 0xAE3 bitwise reverse)
+//#define GEN_POLY       (0xAE3U)
 #define GEN_POLY       (0xAE3U)
 #define PARITY_MASK (0x800000U)
 #define DATA_MASK      (0xfffU)
@@ -11,7 +24,7 @@
 
 /* This function calculates and returns the syndrome
    of a [23,12] Golay codeword. */
-static uint32_t syndrome(uint32_t cw) {
+uint32_t syndrome(uint32_t cw) {
   uint8_t i;
 
   cw &= LSB23BIT;
@@ -26,16 +39,23 @@ static uint32_t syndrome(uint32_t cw) {
 
 // TODO: try with simple `x ^= x >> 2**n` for size optimization
 static inline uint8_t parity(uint32_t x) {
-  x ^= x >> 1;
+/*  x ^= x >> 1;
   x ^= x >> 2;
   x = (x & 0x11111111U) * 0x11111111U;
   return (x >> 28) & 1;
+*/
+  x ^= x >> 16;
+  x ^= x >> 8;
+  x ^= x >> 4;
+  x ^= x >> 2;
+  x ^= x >> 1;
+  return (x & 1);
 }
 
 static inline uint8_t weight(uint32_t cw) {
-  uint8_t c; // c accumulates the total bits set in v
+  uint8_t c; // c accumulates the total bits set in c
 
-  for (c = 0; cw; c++) {
+  for (c = 0; cw; ++c) {
     cw &= cw - 1; // clear the least significant bit set
   }
 
@@ -44,43 +64,40 @@ static inline uint8_t weight(uint32_t cw) {
 
 static uint32_t correct(uint32_t cw, uint8_t *errs) {
   uint8_t    w;                /* current syndrome limit weight, 2 or 3 */
-  uint32_t   mask;             /* mask for bit flipping */
   int8_t     i,j;              /* index */
   uint32_t   s;                /* calculated syndrome */
   uint32_t   cwsaver;          /* saves initial value of cw */
 
-  cwsaver = cw;         /* save */
+  cwsaver = cw & LSB23BIT;     /* save */
   *errs = 0;
   w = 3;                /* initial syndrome weight threshold */
   j = -1;               /* -1 = no trial bit flipping on first pass */
-  mask = 1;
-  while (j < 23) { /* flip each trial bit */
-    if (j != -1) { /* toggle a trial bit */
-      cw = cwsaver ^ mask; /* flip next trial bit */
-      mask <<= 1;
+  while (j < 23) {      /* flip each trial bit */
+    if (j != -1) {
+      cw = cwsaver ^ (1 << j);  /* toggle a trial bit */ /* flip next trial bit */
       w = 2; /* lower the threshold while bit diddling */
     }
 
     s = syndrome(cw); /* look for errors */
-    if (s) { /* errors exist */
-      for (i = 0; i < 23; ++i) { /* check syndrome of each cyclic shift */
-        if ( ( (*errs) = weight(s) ) <= w ) { /* syndrome matches error pattern */
-          cw ^= s;              /* remove errors */
-          cw = ((cw >> i | cw << (23 - i)) & LSB23BIT);  /* unrotate (right) data */
-
-          if (j >= 0) /* count toggled bit (per Steve Duncan) */
-            ++(*errs);
-
-          return cw;
-        } else {
-          cw = ((cw << 1 | cw >> 22) & LSB23BIT);   /* rotate left to next pattern */
-          s = syndrome(cw);         /* calc new syndrome */
-        }
-      }
-      ++j; /* toggle next trial bit */
-    } else {
+    if (!s) 
       return cw; /* return corrected codeword */
+
+    /* errors exist */
+    for (i = 0; i < 23; ++i) { /* check syndrome of each cyclic shift */
+      (*errs) = weight(s);
+      if ( (*errs) <= w ) { /* syndrome matches error pattern */
+        cw ^= s;              /* remove errors */
+        cw = ((cw >> i | cw << (23 - i)) & LSB23BIT);  /* unrotate (right) data */
+
+        if (j != -1) /* count toggled bit (per Steve Duncan) */
+          ++(*errs);
+
+        return cw;
+      }
+      cw = ((cw << 1 | cw >> 22) & LSB23BIT);   /* rotate left to next pattern */
+      s = syndrome(cw);         /* calc new syndrome */
     }
+    ++j; /* toggle next trial bit */
   }
 
   return cwsaver; /* return original if no corrections */
@@ -89,23 +106,25 @@ static uint32_t correct(uint32_t cw, uint8_t *errs) {
 uint8_t golay_decode(uint32_t *cw, uint8_t *errs) {
   uint8_t parity_bit;
 
-  parity_bit = (*cw) & PARITY_MASK ? 1 : 0;
+  parity_bit = ((*cw) & PARITY_MASK) >> 23;
   (*cw) &= ~PARITY_MASK;
   (*cw) = correct(*cw, errs);
   if (parity_bit)
     (*cw) |= PARITY_MASK;
 
-  // 4 bit error checking: 0 - no error; 1 - 4 bit error
+  // 4-error checking: 0 - no error; 1 - 4 bit error
   return parity(*cw);
 }
 
+#if (DECODER_ONLY == 0)
 uint32_t golay_encode(uint32_t cw) {
   cw &= DATA_MASK; // maybe unnecessary, data side validation also made (* to be make)
   cw |= syndrome(cw);
   cw |= (parity(cw) << 23);
 
   return cw;    /* assemble codeword */
 }
+#endif
 /*
 int main () {
 

diff --git a/smog_uplink/ref_encdec.h b/smog_uplink/ref_encdec.h
@@ -1,7 +1,13 @@
 #ifndef REF_ENCDEC_H
 #define REF_ENCDEC_H
 
+#define DECODER_ONLY 1
+
 uint8_t golay_decode(uint32_t *cw, uint8_t *errs);
+//uint32_t syndrome(uint32_t cw);
+
+#if (DECODER_ONLY == 0)
 uint32_t golay_encode(uint32_t cw);
+#endif
 
 #endif
diff --git a/smog_uplink/golay_test.c → smog_uplink/test/golay_test.c b/smog_uplink/golay_test.c → smog_uplink/test/golay_test.c