From 9fe4d4ea9c054e539ab679ed2e9c076c35beb69d Mon Sep 17 00:00:00 2001 From: etobi Date: Tue, 3 Sep 2013 09:48:45 +0200 Subject: Imported Upstream version 1.1.1+rev1355 --- util/alevt/hamm.c | 229 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 229 insertions(+) create mode 100644 util/alevt/hamm.c (limited to 'util/alevt/hamm.c') diff --git a/util/alevt/hamm.c b/util/alevt/hamm.c new file mode 100644 index 0000000..c44a902 --- /dev/null +++ b/util/alevt/hamm.c @@ -0,0 +1,229 @@ +#include "vt.h" +#include "hamm.h" + +// table to decode hamm8/4 encoded bytes. +// the low 4 bits are the (corrected) data bits +// bit 8 is set if there was a single bit error +// bit 12 is set if there was an uncorrectable error + +// the idea: you may add up to 15 words and get the +// number of single bit errors in b8-b11 and the number +// of double errors in b12-b15 + + +static unsigned short hammtab[256] = +{ + 0x0101, 0x100f, 0x0001, 0x0101, 0x100f, 0x0100, 0x0101, 0x100f, + 0x100f, 0x0102, 0x0101, 0x100f, 0x010a, 0x100f, 0x100f, 0x0107, + 0x100f, 0x0100, 0x0101, 0x100f, 0x0100, 0x0000, 0x100f, 0x0100, + 0x0106, 0x100f, 0x100f, 0x010b, 0x100f, 0x0100, 0x0103, 0x100f, + 0x100f, 0x010c, 0x0101, 0x100f, 0x0104, 0x100f, 0x100f, 0x0107, + 0x0106, 0x100f, 0x100f, 0x0107, 0x100f, 0x0107, 0x0107, 0x0007, + 0x0106, 0x100f, 0x100f, 0x0105, 0x100f, 0x0100, 0x010d, 0x100f, + 0x0006, 0x0106, 0x0106, 0x100f, 0x0106, 0x100f, 0x100f, 0x0107, + 0x100f, 0x0102, 0x0101, 0x100f, 0x0104, 0x100f, 0x100f, 0x0109, + 0x0102, 0x0002, 0x100f, 0x0102, 0x100f, 0x0102, 0x0103, 0x100f, + 0x0108, 0x100f, 0x100f, 0x0105, 0x100f, 0x0100, 0x0103, 0x100f, + 0x100f, 0x0102, 0x0103, 0x100f, 0x0103, 0x100f, 0x0003, 0x0103, + 0x0104, 0x100f, 0x100f, 0x0105, 0x0004, 0x0104, 0x0104, 0x100f, + 0x100f, 0x0102, 0x010f, 0x100f, 0x0104, 0x100f, 0x100f, 0x0107, + 0x100f, 0x0105, 0x0105, 0x0005, 0x0104, 0x100f, 0x100f, 0x0105, + 0x0106, 0x100f, 0x100f, 0x0105, 0x100f, 0x010e, 0x0103, 0x100f, + 0x100f, 0x010c, 0x0101, 0x100f, 0x010a, 0x100f, 0x100f, 0x0109, + 0x010a, 0x100f, 0x100f, 0x010b, 0x000a, 0x010a, 0x010a, 0x100f, + 0x0108, 0x100f, 0x100f, 0x010b, 0x100f, 0x0100, 0x010d, 0x100f, + 0x100f, 0x010b, 0x010b, 0x000b, 0x010a, 0x100f, 0x100f, 0x010b, + 0x010c, 0x000c, 0x100f, 0x010c, 0x100f, 0x010c, 0x010d, 0x100f, + 0x100f, 0x010c, 0x010f, 0x100f, 0x010a, 0x100f, 0x100f, 0x0107, + 0x100f, 0x010c, 0x010d, 0x100f, 0x010d, 0x100f, 0x000d, 0x010d, + 0x0106, 0x100f, 0x100f, 0x010b, 0x100f, 0x010e, 0x010d, 0x100f, + 0x0108, 0x100f, 0x100f, 0x0109, 0x100f, 0x0109, 0x0109, 0x0009, + 0x100f, 0x0102, 0x010f, 0x100f, 0x010a, 0x100f, 0x100f, 0x0109, + 0x0008, 0x0108, 0x0108, 0x100f, 0x0108, 0x100f, 0x100f, 0x0109, + 0x0108, 0x100f, 0x100f, 0x010b, 0x100f, 0x010e, 0x0103, 0x100f, + 0x100f, 0x010c, 0x010f, 0x100f, 0x0104, 0x100f, 0x100f, 0x0109, + 0x010f, 0x100f, 0x000f, 0x010f, 0x100f, 0x010e, 0x010f, 0x100f, + 0x0108, 0x100f, 0x100f, 0x0105, 0x100f, 0x010e, 0x010d, 0x100f, + 0x100f, 0x010e, 0x010f, 0x100f, 0x010e, 0x000e, 0x100f, 0x010e, +}; + +#if 0 // this information is contained in hamm24par bit 5 +// simple parity table (sum of 1 bits modulo 2) + + +static char odd_parity[256] = +{ + 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, + 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, + 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, + 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, + 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, + 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, + 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, + 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, + 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, + 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, + 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, + 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, + 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0 +}; +#endif + +// this table generates the parity checks for hamm24/18 decoding. +// bit 0 is for test A, 1 for B, ... +// thanks to R. Gancarz for this fine table *g* + + +static char hamm24par[3][256] = +{ + { // parities of first byte + 0, 33, 34, 3, 35, 2, 1, 32, 36, 5, 6, 39, 7, 38, 37, 4, + 37, 4, 7, 38, 6, 39, 36, 5, 1, 32, 35, 2, 34, 3, 0, 33, + 38, 7, 4, 37, 5, 36, 39, 6, 2, 35, 32, 1, 33, 0, 3, 34, + 3, 34, 33, 0, 32, 1, 2, 35, 39, 6, 5, 36, 4, 37, 38, 7, + 39, 6, 5, 36, 4, 37, 38, 7, 3, 34, 33, 0, 32, 1, 2, 35, + 2, 35, 32, 1, 33, 0, 3, 34, 38, 7, 4, 37, 5, 36, 39, 6, + 1, 32, 35, 2, 34, 3, 0, 33, 37, 4, 7, 38, 6, 39, 36, 5, + 36, 5, 6, 39, 7, 38, 37, 4, 0, 33, 34, 3, 35, 2, 1, 32, + 40, 9, 10, 43, 11, 42, 41, 8, 12, 45, 46, 15, 47, 14, 13, 44, + 13, 44, 47, 14, 46, 15, 12, 45, 41, 8, 11, 42, 10, 43, 40, 9, + 14, 47, 44, 13, 45, 12, 15, 46, 42, 11, 8, 41, 9, 40, 43, 10, + 43, 10, 9, 40, 8, 41, 42, 11, 15, 46, 45, 12, 44, 13, 14, 47, + 15, 46, 45, 12, 44, 13, 14, 47, 43, 10, 9, 40, 8, 41, 42, 11, + 42, 11, 8, 41, 9, 40, 43, 10, 14, 47, 44, 13, 45, 12, 15, 46, + 41, 8, 11, 42, 10, 43, 40, 9, 13, 44, 47, 14, 46, 15, 12, 45, + 12, 45, 46, 15, 47, 14, 13, 44, 40, 9, 10, 43, 11, 42, 41, 8 + }, { // parities of second byte + 0, 41, 42, 3, 43, 2, 1, 40, 44, 5, 6, 47, 7, 46, 45, 4, + 45, 4, 7, 46, 6, 47, 44, 5, 1, 40, 43, 2, 42, 3, 0, 41, + 46, 7, 4, 45, 5, 44, 47, 6, 2, 43, 40, 1, 41, 0, 3, 42, + 3, 42, 41, 0, 40, 1, 2, 43, 47, 6, 5, 44, 4, 45, 46, 7, + 47, 6, 5, 44, 4, 45, 46, 7, 3, 42, 41, 0, 40, 1, 2, 43, + 2, 43, 40, 1, 41, 0, 3, 42, 46, 7, 4, 45, 5, 44, 47, 6, + 1, 40, 43, 2, 42, 3, 0, 41, 45, 4, 7, 46, 6, 47, 44, 5, + 44, 5, 6, 47, 7, 46, 45, 4, 0, 41, 42, 3, 43, 2, 1, 40, + 48, 25, 26, 51, 27, 50, 49, 24, 28, 53, 54, 31, 55, 30, 29, 52, + 29, 52, 55, 30, 54, 31, 28, 53, 49, 24, 27, 50, 26, 51, 48, 25, + 30, 55, 52, 29, 53, 28, 31, 54, 50, 27, 24, 49, 25, 48, 51, 26, + 51, 26, 25, 48, 24, 49, 50, 27, 31, 54, 53, 28, 52, 29, 30, 55, + 31, 54, 53, 28, 52, 29, 30, 55, 51, 26, 25, 48, 24, 49, 50, 27, + 50, 27, 24, 49, 25, 48, 51, 26, 30, 55, 52, 29, 53, 28, 31, 54, + 49, 24, 27, 50, 26, 51, 48, 25, 29, 52, 55, 30, 54, 31, 28, 53, + 28, 53, 54, 31, 55, 30, 29, 52, 48, 25, 26, 51, 27, 50, 49, 24 + }, { // parities of third byte + 63, 14, 13, 60, 12, 61, 62, 15, 11, 58, 57, 8, 56, 9, 10, 59, + 10, 59, 56, 9, 57, 8, 11, 58, 62, 15, 12, 61, 13, 60, 63, 14, + 9, 56, 59, 10, 58, 11, 8, 57, 61, 12, 15, 62, 14, 63, 60, 13, + 60, 13, 14, 63, 15, 62, 61, 12, 8, 57, 58, 11, 59, 10, 9, 56, + 8, 57, 58, 11, 59, 10, 9, 56, 60, 13, 14, 63, 15, 62, 61, 12, + 61, 12, 15, 62, 14, 63, 60, 13, 9, 56, 59, 10, 58, 11, 8, 57, + 62, 15, 12, 61, 13, 60, 63, 14, 10, 59, 56, 9, 57, 8, 11, 58, + 11, 58, 57, 8, 56, 9, 10, 59, 63, 14, 13, 60, 12, 61, 62, 15, + 31, 46, 45, 28, 44, 29, 30, 47, 43, 26, 25, 40, 24, 41, 42, 27, + 42, 27, 24, 41, 25, 40, 43, 26, 30, 47, 44, 29, 45, 28, 31, 46, + 41, 24, 27, 42, 26, 43, 40, 25, 29, 44, 47, 30, 46, 31, 28, 45, + 28, 45, 46, 31, 47, 30, 29, 44, 40, 25, 26, 43, 27, 42, 41, 24, + 40, 25, 26, 43, 27, 42, 41, 24, 28, 45, 46, 31, 47, 30, 29, 44, + 29, 44, 47, 30, 46, 31, 28, 45, 41, 24, 27, 42, 26, 43, 40, 25, + 30, 47, 44, 29, 45, 28, 31, 46, 42, 27, 24, 41, 25, 40, 43, 26, + 43, 26, 25, 40, 24, 41, 42, 27, 31, 46, 45, 28, 44, 29, 30, 47 + } +}; + +// table to extract the lower 4 bit from hamm24/18 encoded bytes + + +static char hamm24val[256] = +{ + 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, + 2, 2, 2, 2, 3, 3, 3, 3, 2, 2, 2, 2, 3, 3, 3, 3, + 4, 4, 4, 4, 5, 5, 5, 5, 4, 4, 4, 4, 5, 5, 5, 5, + 6, 6, 6, 6, 7, 7, 7, 7, 6, 6, 6, 6, 7, 7, 7, 7, + 8, 8, 8, 8, 9, 9, 9, 9, 8, 8, 8, 8, 9, 9, 9, 9, + 10, 10, 10, 10, 11, 11, 11, 11, 10, 10, 10, 10, 11, 11, 11, 11, + 12, 12, 12, 12, 13, 13, 13, 13, 12, 12, 12, 12, 13, 13, 13, 13, + 14, 14, 14, 14, 15, 15, 15, 15, 14, 14, 14, 14, 15, 15, 15, 15, + 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, + 2, 2, 2, 2, 3, 3, 3, 3, 2, 2, 2, 2, 3, 3, 3, 3, + 4, 4, 4, 4, 5, 5, 5, 5, 4, 4, 4, 4, 5, 5, 5, 5, + 6, 6, 6, 6, 7, 7, 7, 7, 6, 6, 6, 6, 7, 7, 7, 7, + 8, 8, 8, 8, 9, 9, 9, 9, 8, 8, 8, 8, 9, 9, 9, 9, + 10, 10, 10, 10, 11, 11, 11, 11, 10, 10, 10, 10, 11, 11, 11, 11, + 12, 12, 12, 12, 13, 13, 13, 13, 12, 12, 12, 12, 13, 13, 13, 13, + 14, 14, 14, 14, 15, 15, 15, 15, 14, 14, 14, 14, 15, 15, 15, 15 +}; + +// mapping from parity checks made by table hamm24par to error +// results return by hamm24. +// (0 = no error, 0x0100 = single bit error, 0x1000 = double error) + + +static short hamm24err[64] = +{ + 0x0000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, + 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, + 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, + 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, + 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, + 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, + 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, + 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, +}; + +// mapping from parity checks made by table hamm24par to faulty bit +// in the decoded 18 bit word. + + +static int hamm24cor[64] = +{ + 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, + 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, + 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, + 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, + 0x00000, 0x00000, 0x00000, 0x00001, 0x00000, 0x00002, 0x00004, 0x00008, + 0x00000, 0x00010, 0x00020, 0x00040, 0x00080, 0x00100, 0x00200, 0x00400, + 0x00000, 0x00800, 0x01000, 0x02000, 0x04000, 0x08000, 0x10000, 0x20000, + 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, +}; + + +int hamm8(u8 *p, int *err) +{ + int a = hammtab[p[0]]; + *err += a; + return a & 15; +} + + +int hamm16(u8 *p, int *err) +{ + int a = hammtab[p[0]]; + int b = hammtab[p[1]]; + *err += a; + *err += b; + return (a & 15) | (b & 15) * 16; +} + + +int hamm24(u8 *p, int *err) +{ + int e = hamm24par[0][p[0]] ^ hamm24par[1][p[1]] ^ hamm24par[2][p[2]]; + int x = hamm24val[p[0]] + p[1] % 128 * 16 + p[2] % 128 * 2048; + *err += hamm24err[e]; + return x ^ hamm24cor[e]; +} + + +int chk_parity(u8 *p, int n) +{ + int err; + for (err = 0; n--; p++) + if (hamm24par[0][*p] & 32) + *p &= 0x7f; + else + *p = BAD_CHAR, err++; + return err; +} -- cgit v1.2.3