From f88c1fde18146fd1bf543399da0f6584c3fd4a81 Mon Sep 17 00:00:00 2001
From: Daniel Friesel <derf@finalrewind.org>
Date: Fri, 5 Feb 2016 17:33:02 +0100
Subject: add (untested) Hamming forward error correction code and
 corresponding class

The system now uses a FECModem instance, which inherits the receive methods
etc. from Modem.

Up next: Make the modem's buffer read methods private and expose them in
error-corrected FECModem methods instead
---
 src/fecmodem.cc | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 src/fecmodem.h  | 20 ++++++++++++++++++++
 src/hamming.h   | 37 +++++++++++++++++++++++++++++++++++++
 src/main.cc     |  2 +-
 src/modem.cc    |  5 +++--
 src/modem.h     |  2 --
 src/system.cc   |  2 +-
 7 files changed, 111 insertions(+), 6 deletions(-)
 create mode 100644 src/fecmodem.cc
 create mode 100644 src/fecmodem.h
 create mode 100644 src/hamming.h

diff --git a/src/fecmodem.cc b/src/fecmodem.cc
new file mode 100644
index 0000000..5323135
--- /dev/null
+++ b/src/fecmodem.cc
@@ -0,0 +1,49 @@
+#include <avr/io.h>
+#include <stdlib.h>
+#include "fecmodem.h"
+
+uint8_t FECModem::parity128(uint8_t byte)
+{
+	return pgm_read_byte(&hammingParityLow[byte & 0x0f]) ^ pgm_read_byte(&hammingParityHigh[byte >> 4]);
+}
+
+uint8_t FECModem::parity2416(uint8_t byte1, uint8_t byte2)
+{
+	return parity128(byte1) | (parity128(byte2) << 4);
+}
+
+uint8_t FECModem::correct128(uint8_t *byte, uint8_t err)
+{
+	uint8_t result = pgm_read_byte(&hammingParityCheck[err & 0x0f]);
+
+	if (result != NO_ERROR) {
+		if (result == UNCORRECTABLE || byte == NULL) {
+			return 3;
+		} else {
+			if (result != ERROR_IN_PARITY) {
+				*byte ^= result;
+			}
+			return 1;
+		}
+	}
+	return 0;
+}
+
+uint8_t FECModem::hamming2416(uint8_t *byte1, uint8_t *byte2, uint8_t parity)
+{
+	uint8_t err;
+
+	if (byte1 == NULL || byte2 == NULL) {
+		return 3;
+	}
+
+	err = parity2416(*byte1, *byte2) ^ parity;
+
+	if (err) {
+		return correct128(byte1, err) + correct128(byte2, err >> 4);
+	}
+
+	return 0;
+}
+
+FECModem modem;
diff --git a/src/fecmodem.h b/src/fecmodem.h
new file mode 100644
index 0000000..dd36f68
--- /dev/null
+++ b/src/fecmodem.h
@@ -0,0 +1,20 @@
+#include <avr/io.h>
+#include <stdlib.h>
+
+#ifndef FECMODEM_H_
+#define FECMODEM_H_
+
+#include "hamming.h"
+#include "modem.h"
+
+class FECModem : public Modem {
+	private:
+		uint8_t parity128(uint8_t byte);
+		uint8_t parity2416(uint8_t byte1, uint8_t byte2);
+		uint8_t correct128(uint8_t *byte, uint8_t parity);
+		uint8_t hamming2416(uint8_t *byte1, uint8_t *byte2, uint8_t parity);
+};
+
+extern FECModem modem;
+
+#endif /* FECMODEM_H_ */
diff --git a/src/hamming.h b/src/hamming.h
new file mode 100644
index 0000000..9828baa
--- /dev/null
+++ b/src/hamming.h
@@ -0,0 +1,37 @@
+#ifndef HAMMING_H_
+#define HAMMING_H_
+
+#include <avr/pgmspace.h>
+
+enum HammingResult : uint8_t {
+	NO_ERROR = 0,
+	ERROR_IN_PARITY = 0xfe,
+	UNCORRECTABLE = 0xff,
+};
+
+const uint8_t hammingParityLow[] PROGMEM =
+{ 0,  3,  5,  6,  6,  5,  3,  0,  7,  4,  2,  1,  1,  2,  4,  7 };
+
+const uint8_t hammingParityHigh[] PROGMEM =
+{ 0,  9, 10,  3, 11,  2,  1,  8, 12,  5,  6, 15,  7, 14, 13,  4 };
+
+const uint8_t PROGMEM hammingParityCheck[] = {
+	NO_ERROR,
+	ERROR_IN_PARITY,
+	ERROR_IN_PARITY,
+	0x01,
+	ERROR_IN_PARITY,
+	0x02,
+	0x04,
+	0x08,
+	ERROR_IN_PARITY,
+	0x10,
+	0x20,
+	0x40,
+	0x80,
+	UNCORRECTABLE,
+	UNCORRECTABLE,
+	UNCORRECTABLE
+};
+
+#endif /* HAMMING_H_ */
diff --git a/src/main.cc b/src/main.cc
index 37dc8bd..ae9ebc5 100644
--- a/src/main.cc
+++ b/src/main.cc
@@ -3,7 +3,7 @@
 #include "display.h"
 #include "font.h"
 #include "storage.h"
-#include "modem.h"
+#include "fecmodem.h"
 #include "system.h"
 
 animation_t ohai;
diff --git a/src/modem.cc b/src/modem.cc
index e9cddb7..472fe04 100644
--- a/src/modem.cc
+++ b/src/modem.cc
@@ -10,8 +10,9 @@
 #include <avr/io.h>
 #include <stdlib.h>
 #include "modem.h"
+#include "fecmodem.h"
 
-Modem modem;
+extern FECModem modem;
 
 /*
  * Returns number of available bytes in ringbuffer or 0 if empty
@@ -24,7 +25,7 @@ uint8_t Modem::buffer_available() {
  * Store 1 byte in ringbuffer
  */
 inline void Modem::buffer_put(const uint8_t c) {
-	if (modem.buffer_available() != MODEM_BUFFER_SIZE) {
+	if (buffer_available() != MODEM_BUFFER_SIZE) {
 		buffer[buffer_head++ % MODEM_BUFFER_SIZE] = c;
 	}
 }
diff --git a/src/modem.h b/src/modem.h
index ea308a7..4040c92 100644
--- a/src/modem.h
+++ b/src/modem.h
@@ -70,6 +70,4 @@ class Modem {
 		void receive(void);
 };
 
-extern Modem modem;
-
 #endif /* MODEM_H_ */
diff --git a/src/system.cc b/src/system.cc
index a192b24..1a0522d 100644
--- a/src/system.cc
+++ b/src/system.cc
@@ -5,7 +5,7 @@
 #include <stdlib.h>
 
 #include "display.h"
-#include "modem.h"
+#include "fecmodem.h"
 #include "storage.h"
 #include "system.h"
 
-- 
cgit v1.2.3