aboutsummaryrefslogtreecommitdiff
path: root/src/golay23.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/golay23.c')
-rw-r--r--src/golay23.c311
1 files changed, 311 insertions, 0 deletions
diff --git a/src/golay23.c b/src/golay23.c
new file mode 100644
index 0000000..158a099
--- /dev/null
+++ b/src/golay23.c
@@ -0,0 +1,311 @@
+/*---------------------------------------------------------------------------*\
+
+ FILE........: golay23.c
+ AUTHOR......: Tomas Härdin & David Rowe
+ DATE CREATED: 3 March 2013
+
+ To test:
+
+ src$ gcc golay23.c -o golay23 -Wall -O3 -DGOLAY23_UNITTEST && ./golay23
+ src$ gcc golay23.c -o golay23 -Wall -O3 -DGOLAY23_UNITTEST -DRUN_TIME_TABLES && ./golay23
+ src$ gcc golay23.c -o golay23 -Wall -O3 -DGOLAY23_UNITTEST -DNO_TABLES && ./golay23
+
+ To generate tables:
+ src$ gcc golay23.c -o golay23 -Wall -O3 -DGOLAY23_MAKETABLES && ./golay23
+
+\*---------------------------------------------------------------------------*/
+
+/*
+ Copyright (C) 2016 Tomas Härdin & David Rowe
+
+ All rights reserved.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU Lesser General Public License version 2.1, as
+ published by the Free Software Foundation. This program is
+ distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
+ License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with this program; if not,see <http://www.gnu.org/licenses/>.
+*/
+
+#include <assert.h>
+
+#ifdef GOLAY23_MAKETABLES
+#define RUN_TIME_TABLES
+#endif
+
+#ifndef NO_TABLES
+#ifdef RUN_TIME_TABLES
+int static encoding_table[4096];
+int static decoding_table[2048];
+static int inited = 0;
+#else
+//default is to use precomputed tables
+#include "golayenctable.h"
+#include "golaydectable.h"
+#endif
+#endif
+
+//since we want to avoid bit-reversing inside syndrome() we bit-reverse the polynomial instead
+#define GOLAY_POLYNOMIAL 0xC75 //AE3 reversed
+
+int golay23_syndrome(int c) {
+ //could probably be done slightly smarter, but works
+ int x;
+ for (x = 11; x >= 0; x--) {
+ if (c & ((1<<11) << x)) {
+ c ^= GOLAY_POLYNOMIAL << x;
+ }
+ }
+ return c;
+}
+
+#ifdef __GNUC__
+#define popcount __builtin_popcount
+#elif defined(__MSC_VER)
+#include <intrin.h>
+#define popcount __popcnt
+#else
+static int popcount(unsigned int c) {
+ int ret = 0;
+ while (c) {
+ if (c & 1) {
+ ret++;
+ }
+ c >>= 1;
+ }
+ return ret;
+}
+#endif
+
+#if defined(NO_TABLES) || defined(RUN_TIME_TABLES)
+static int golay23_encode_no_tables(int c) {
+ c <<= 11;
+ return golay23_syndrome(c) | c;
+}
+#endif
+
+#ifdef NO_TABLES
+static int unrotate(unsigned int c, int x) {
+ return ((c << x) & 0x7FFFFF) | (c >> (23 - x));
+}
+
+static int golay23_decode_no_tables(int c) {
+ //TODO: optimize?
+ int x;
+ c = unrotate(c, 12);
+
+ for (x = 0; x < 23; x++) {
+ int t;
+ int s = golay23_syndrome(c);
+
+ if (popcount(s) <= 3) {
+ return unrotate(c ^ s, x) & 0xFFF;
+ }
+
+ for (t = 0; t < 23; t++) {
+ int c2 = c ^ (1 << t);
+ int s = golay23_syndrome(c2);
+
+ if (popcount(s) <= 2) {
+ return unrotate(c2 ^ s, x) & 0xFFF;
+ }
+ }
+
+ //rotate
+ c = (c >> 1) | ((c & 1) << 22);
+ }
+
+ //shouldn't reach here..
+ assert("Something is wrong with golay23_decode_no_tables()..");
+ return c & 0xFFF;
+}
+#endif
+
+void golay23_init(void) {
+#ifdef RUN_TIME_TABLES
+ int x, y, z;
+ inited = 1;
+ for (x = 0; x < 4096; x++) {
+ encoding_table[x] = golay23_encode_no_tables(x);
+ }
+
+ decoding_table[0] = 0;
+ //1-bit errors
+ for (x = 0; x < 23; x++) {
+ int d = 1<<x;
+ decoding_table[golay23_syndrome(d)] = d;
+ }
+ //2-bit errors
+ for (x = 0; x < 22; x++) {
+ for (y = x+1; y < 23; y++) {
+ int d = (1<<x) | (1<<y);
+ decoding_table[golay23_syndrome(d)] = d;
+ }
+ }
+ //3-bit errors
+ for (x = 0; x < 21; x++) {
+ for (y = x+1; y < 22; y++) {
+ for (z = y+1; z < 23; z++) {
+ int d = (1<<x) | (1<<y) | (1<<z);
+ decoding_table[golay23_syndrome(d)] = d;
+ }
+ }
+ }
+#endif
+}
+
+int golay23_encode(int c) {
+ assert(c >= 0 && c <= 0xFFF);
+#ifdef RUN_TIME_TABLES
+ assert(inited);
+#endif
+
+#ifdef NO_TABLES
+ return golay23_encode_no_tables(c);
+#else
+ return encoding_table[c];
+#endif
+}
+
+int golay23_decode(int c) {
+ assert(c >= 0 && c <= 0x7FFFFF);
+#ifdef RUN_TIME_TABLES
+ assert(inited);
+#endif
+
+#ifdef NO_TABLES
+ //duplicate old golay23_decode()'s shift
+ return unrotate(golay23_decode_no_tables(c), 11);
+#else
+ //message is shifted 11 places left in the return value
+ return c ^ decoding_table[golay23_syndrome(c)];
+#endif
+}
+
+int golay23_count_errors(int recd_codeword, int corrected_codeword) {
+ return popcount(recd_codeword ^ corrected_codeword);
+}
+
+/**
+ * Table generation and testing code below
+ */
+
+#ifdef GOLAY23_MAKETABLES
+#include <stdio.h>
+
+int main() {
+ int x;
+ //generate and dump
+ golay23_init();
+
+ FILE *enc = fopen("golayenctable.h", "w");
+ FILE *dec = fopen("golaydectable.h", "w");
+
+ fprintf(enc, "/* Generated by golay23.c -DGOLAY23_MAKETABLE */\n\
+\n\
+const int static encoding_table[]={\n");
+ for (x = 0; x < 4096; x++) {
+ fprintf(enc, x < 4095 ? " 0x%x,\n" : " 0x%x\n", encoding_table[x]);
+ }
+ fprintf(enc, "};\n");
+
+ fprintf(dec, "/* Generated by golay23.c -DGOLAY23_MAKETABLE */\n\
+\n\
+const int static decoding_table[]={\n");
+ for (x = 0; x < 2048; x++) {
+ fprintf(dec, x < 2047 ? " 0x%x,\n" : " 0x%x\n", decoding_table[x]);
+ }
+ fprintf(dec, "};\n");
+
+ fclose(enc);
+ fclose(dec);
+
+ return 0;
+}
+
+#elif defined(GOLAY23_UNITTEST)
+#include <stdio.h>
+#include <stdlib.h>
+#include <memory.h>
+
+int main() {
+ int c;
+
+ golay23_init();
+
+ //keep track of whether every single codeword has been checked
+ char *checkmask = malloc(1<<23);
+ memset(checkmask, 0, 1<<23);
+
+ //step through all possible messages
+ for (c = 0; c < (1<<12); c++) {
+ int g23 = golay23_encode(c);
+ int x,y,z;
+ checkmask[g23] = 1;
+ int c2 = golay23_decode(g23) >> 11;
+
+ printf("%03x -> %06x %03x\n", c, g23, c2);
+
+ if (c != c2) {
+ printf("Bad!\n");
+ exit(1);
+ }
+
+ //test the code by flipping every combination of one, two and three bits
+ for (x = 0; x < 23; x++) {
+ int flipped = g23 ^ (1<<x);
+ checkmask[flipped] = 1;
+ int c2 = golay23_decode(flipped) >> 11;
+ if (c != c2) {
+ printf("Bad!\n");
+
+ exit(1);
+ }
+ }
+
+ for (x = 0; x < 22; x++) {
+ for (y = x+1; y < 23; y++) {
+ int flipped = g23 ^ (1<<x) ^ (1<<y);
+ checkmask[flipped] = 1;
+ int c2 = golay23_decode(flipped) >> 11;
+ if (c != c2) {
+ printf("Bad!\n");
+
+ exit(1);
+ }
+ }
+ }
+
+ for (x = 0; x < 21; x++) {
+ for (y = x+1; y < 22; y++) {
+ for (z = y+1; z < 23; z++) {
+ int flipped = g23 ^ (1<<x) ^ (1<<y) ^ (1<<z);
+ checkmask[flipped] = 1;
+ int c2 = golay23_decode(flipped) >> 11;
+ if (c != c2) {
+ printf("Bad!\n");
+ exit(1);
+ }
+ }
+ }
+ }
+ }
+
+ //did we check every codeword?
+ for (c = 0; c < (1<<23); c++) {
+ if (checkmask[c] != 1) {
+ printf("%06x unchecked!\n", c);
+ exit(1);
+ }
+ }
+
+ printf("Everything checks out\n");
+ free(checkmask);
+ return 0;
+}
+#endif
generated by cgit v1.2.3 (git 2.46.0) at 2026-01-27 03:26:39 +0000