MythTV  master
hamm.c
Go to the documentation of this file.
1 #include "vt.h"
2 #include "hamm.h"
3 
4 // table to decode hamm8/4 encoded bytes.
5 // the low 4 bits are the (corrected) data bits
6 // bit 8 is set if there was a single bit error
7 // bit 12 is set if there was an uncorrectable error
8 
9 // the idea: you may add up to 15 words and get the
10 // number of single bit errors in b8-b11 and the number
11 // of double errors in b12-b15
12 
13 static unsigned short hammtab[256] =
14 {
15  0x0101, 0x100f, 0x0001, 0x0101, 0x100f, 0x0100, 0x0101, 0x100f,
16  0x100f, 0x0102, 0x0101, 0x100f, 0x010a, 0x100f, 0x100f, 0x0107,
17  0x100f, 0x0100, 0x0101, 0x100f, 0x0100, 0x0000, 0x100f, 0x0100,
18  0x0106, 0x100f, 0x100f, 0x010b, 0x100f, 0x0100, 0x0103, 0x100f,
19  0x100f, 0x010c, 0x0101, 0x100f, 0x0104, 0x100f, 0x100f, 0x0107,
20  0x0106, 0x100f, 0x100f, 0x0107, 0x100f, 0x0107, 0x0107, 0x0007,
21  0x0106, 0x100f, 0x100f, 0x0105, 0x100f, 0x0100, 0x010d, 0x100f,
22  0x0006, 0x0106, 0x0106, 0x100f, 0x0106, 0x100f, 0x100f, 0x0107,
23  0x100f, 0x0102, 0x0101, 0x100f, 0x0104, 0x100f, 0x100f, 0x0109,
24  0x0102, 0x0002, 0x100f, 0x0102, 0x100f, 0x0102, 0x0103, 0x100f,
25  0x0108, 0x100f, 0x100f, 0x0105, 0x100f, 0x0100, 0x0103, 0x100f,
26  0x100f, 0x0102, 0x0103, 0x100f, 0x0103, 0x100f, 0x0003, 0x0103,
27  0x0104, 0x100f, 0x100f, 0x0105, 0x0004, 0x0104, 0x0104, 0x100f,
28  0x100f, 0x0102, 0x010f, 0x100f, 0x0104, 0x100f, 0x100f, 0x0107,
29  0x100f, 0x0105, 0x0105, 0x0005, 0x0104, 0x100f, 0x100f, 0x0105,
30  0x0106, 0x100f, 0x100f, 0x0105, 0x100f, 0x010e, 0x0103, 0x100f,
31  0x100f, 0x010c, 0x0101, 0x100f, 0x010a, 0x100f, 0x100f, 0x0109,
32  0x010a, 0x100f, 0x100f, 0x010b, 0x000a, 0x010a, 0x010a, 0x100f,
33  0x0108, 0x100f, 0x100f, 0x010b, 0x100f, 0x0100, 0x010d, 0x100f,
34  0x100f, 0x010b, 0x010b, 0x000b, 0x010a, 0x100f, 0x100f, 0x010b,
35  0x010c, 0x000c, 0x100f, 0x010c, 0x100f, 0x010c, 0x010d, 0x100f,
36  0x100f, 0x010c, 0x010f, 0x100f, 0x010a, 0x100f, 0x100f, 0x0107,
37  0x100f, 0x010c, 0x010d, 0x100f, 0x010d, 0x100f, 0x000d, 0x010d,
38  0x0106, 0x100f, 0x100f, 0x010b, 0x100f, 0x010e, 0x010d, 0x100f,
39  0x0108, 0x100f, 0x100f, 0x0109, 0x100f, 0x0109, 0x0109, 0x0009,
40  0x100f, 0x0102, 0x010f, 0x100f, 0x010a, 0x100f, 0x100f, 0x0109,
41  0x0008, 0x0108, 0x0108, 0x100f, 0x0108, 0x100f, 0x100f, 0x0109,
42  0x0108, 0x100f, 0x100f, 0x010b, 0x100f, 0x010e, 0x0103, 0x100f,
43  0x100f, 0x010c, 0x010f, 0x100f, 0x0104, 0x100f, 0x100f, 0x0109,
44  0x010f, 0x100f, 0x000f, 0x010f, 0x100f, 0x010e, 0x010f, 0x100f,
45  0x0108, 0x100f, 0x100f, 0x0105, 0x100f, 0x010e, 0x010d, 0x100f,
46  0x100f, 0x010e, 0x010f, 0x100f, 0x010e, 0x000e, 0x100f, 0x010e,
47 };
48 
49 
50 
51 #if 0 // this information is contained in hamm24par bit 5
52 // simple parity table (sum of 1 bits modulo 2)
53 
54 static char odd_parity[256] =
55 {
56  0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
57  1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
58  1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
59  0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
60  1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
61  0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
62  0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
63  1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
64  1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
65  0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
66  0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
67  1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
68  0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
69  1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
70  1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
71  0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0
72 };
73 #endif
74 
75 
76 
77 // this table generates the parity checks for hamm24/18 decoding.
78 // bit 0 is for test A, 1 for B, ...
79 // thanks to R. Gancarz for this fine table *g*
80 
81 static char hamm24par[3][256] =
82 {
83  { // parities of first byte
84  0, 33, 34, 3, 35, 2, 1, 32, 36, 5, 6, 39, 7, 38, 37, 4,
85  37, 4, 7, 38, 6, 39, 36, 5, 1, 32, 35, 2, 34, 3, 0, 33,
86  38, 7, 4, 37, 5, 36, 39, 6, 2, 35, 32, 1, 33, 0, 3, 34,
87  3, 34, 33, 0, 32, 1, 2, 35, 39, 6, 5, 36, 4, 37, 38, 7,
88  39, 6, 5, 36, 4, 37, 38, 7, 3, 34, 33, 0, 32, 1, 2, 35,
89  2, 35, 32, 1, 33, 0, 3, 34, 38, 7, 4, 37, 5, 36, 39, 6,
90  1, 32, 35, 2, 34, 3, 0, 33, 37, 4, 7, 38, 6, 39, 36, 5,
91  36, 5, 6, 39, 7, 38, 37, 4, 0, 33, 34, 3, 35, 2, 1, 32,
92  40, 9, 10, 43, 11, 42, 41, 8, 12, 45, 46, 15, 47, 14, 13, 44,
93  13, 44, 47, 14, 46, 15, 12, 45, 41, 8, 11, 42, 10, 43, 40, 9,
94  14, 47, 44, 13, 45, 12, 15, 46, 42, 11, 8, 41, 9, 40, 43, 10,
95  43, 10, 9, 40, 8, 41, 42, 11, 15, 46, 45, 12, 44, 13, 14, 47,
96  15, 46, 45, 12, 44, 13, 14, 47, 43, 10, 9, 40, 8, 41, 42, 11,
97  42, 11, 8, 41, 9, 40, 43, 10, 14, 47, 44, 13, 45, 12, 15, 46,
98  41, 8, 11, 42, 10, 43, 40, 9, 13, 44, 47, 14, 46, 15, 12, 45,
99  12, 45, 46, 15, 47, 14, 13, 44, 40, 9, 10, 43, 11, 42, 41, 8
100  }, { // parities of second byte
101  0, 41, 42, 3, 43, 2, 1, 40, 44, 5, 6, 47, 7, 46, 45, 4,
102  45, 4, 7, 46, 6, 47, 44, 5, 1, 40, 43, 2, 42, 3, 0, 41,
103  46, 7, 4, 45, 5, 44, 47, 6, 2, 43, 40, 1, 41, 0, 3, 42,
104  3, 42, 41, 0, 40, 1, 2, 43, 47, 6, 5, 44, 4, 45, 46, 7,
105  47, 6, 5, 44, 4, 45, 46, 7, 3, 42, 41, 0, 40, 1, 2, 43,
106  2, 43, 40, 1, 41, 0, 3, 42, 46, 7, 4, 45, 5, 44, 47, 6,
107  1, 40, 43, 2, 42, 3, 0, 41, 45, 4, 7, 46, 6, 47, 44, 5,
108  44, 5, 6, 47, 7, 46, 45, 4, 0, 41, 42, 3, 43, 2, 1, 40,
109  48, 25, 26, 51, 27, 50, 49, 24, 28, 53, 54, 31, 55, 30, 29, 52,
110  29, 52, 55, 30, 54, 31, 28, 53, 49, 24, 27, 50, 26, 51, 48, 25,
111  30, 55, 52, 29, 53, 28, 31, 54, 50, 27, 24, 49, 25, 48, 51, 26,
112  51, 26, 25, 48, 24, 49, 50, 27, 31, 54, 53, 28, 52, 29, 30, 55,
113  31, 54, 53, 28, 52, 29, 30, 55, 51, 26, 25, 48, 24, 49, 50, 27,
114  50, 27, 24, 49, 25, 48, 51, 26, 30, 55, 52, 29, 53, 28, 31, 54,
115  49, 24, 27, 50, 26, 51, 48, 25, 29, 52, 55, 30, 54, 31, 28, 53,
116  28, 53, 54, 31, 55, 30, 29, 52, 48, 25, 26, 51, 27, 50, 49, 24
117  }, { // parities of third byte
118  63, 14, 13, 60, 12, 61, 62, 15, 11, 58, 57, 8, 56, 9, 10, 59,
119  10, 59, 56, 9, 57, 8, 11, 58, 62, 15, 12, 61, 13, 60, 63, 14,
120  9, 56, 59, 10, 58, 11, 8, 57, 61, 12, 15, 62, 14, 63, 60, 13,
121  60, 13, 14, 63, 15, 62, 61, 12, 8, 57, 58, 11, 59, 10, 9, 56,
122  8, 57, 58, 11, 59, 10, 9, 56, 60, 13, 14, 63, 15, 62, 61, 12,
123  61, 12, 15, 62, 14, 63, 60, 13, 9, 56, 59, 10, 58, 11, 8, 57,
124  62, 15, 12, 61, 13, 60, 63, 14, 10, 59, 56, 9, 57, 8, 11, 58,
125  11, 58, 57, 8, 56, 9, 10, 59, 63, 14, 13, 60, 12, 61, 62, 15,
126  31, 46, 45, 28, 44, 29, 30, 47, 43, 26, 25, 40, 24, 41, 42, 27,
127  42, 27, 24, 41, 25, 40, 43, 26, 30, 47, 44, 29, 45, 28, 31, 46,
128  41, 24, 27, 42, 26, 43, 40, 25, 29, 44, 47, 30, 46, 31, 28, 45,
129  28, 45, 46, 31, 47, 30, 29, 44, 40, 25, 26, 43, 27, 42, 41, 24,
130  40, 25, 26, 43, 27, 42, 41, 24, 28, 45, 46, 31, 47, 30, 29, 44,
131  29, 44, 47, 30, 46, 31, 28, 45, 41, 24, 27, 42, 26, 43, 40, 25,
132  30, 47, 44, 29, 45, 28, 31, 46, 42, 27, 24, 41, 25, 40, 43, 26,
133  43, 26, 25, 40, 24, 41, 42, 27, 31, 46, 45, 28, 44, 29, 30, 47
134  }
135 };
136 
137 
138 
139 // table to extract the lower 4 bit from hamm24/18 encoded bytes
140 
141 static char hamm24val[256] =
142 {
143  0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1,
144  2, 2, 2, 2, 3, 3, 3, 3, 2, 2, 2, 2, 3, 3, 3, 3,
145  4, 4, 4, 4, 5, 5, 5, 5, 4, 4, 4, 4, 5, 5, 5, 5,
146  6, 6, 6, 6, 7, 7, 7, 7, 6, 6, 6, 6, 7, 7, 7, 7,
147  8, 8, 8, 8, 9, 9, 9, 9, 8, 8, 8, 8, 9, 9, 9, 9,
148  10, 10, 10, 10, 11, 11, 11, 11, 10, 10, 10, 10, 11, 11, 11, 11,
149  12, 12, 12, 12, 13, 13, 13, 13, 12, 12, 12, 12, 13, 13, 13, 13,
150  14, 14, 14, 14, 15, 15, 15, 15, 14, 14, 14, 14, 15, 15, 15, 15,
151  0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1,
152  2, 2, 2, 2, 3, 3, 3, 3, 2, 2, 2, 2, 3, 3, 3, 3,
153  4, 4, 4, 4, 5, 5, 5, 5, 4, 4, 4, 4, 5, 5, 5, 5,
154  6, 6, 6, 6, 7, 7, 7, 7, 6, 6, 6, 6, 7, 7, 7, 7,
155  8, 8, 8, 8, 9, 9, 9, 9, 8, 8, 8, 8, 9, 9, 9, 9,
156  10, 10, 10, 10, 11, 11, 11, 11, 10, 10, 10, 10, 11, 11, 11, 11,
157  12, 12, 12, 12, 13, 13, 13, 13, 12, 12, 12, 12, 13, 13, 13, 13,
158  14, 14, 14, 14, 15, 15, 15, 15, 14, 14, 14, 14, 15, 15, 15, 15
159 };
160 
161 
162 
163 // mapping from parity checks made by table hamm24par to error
164 // results return by hamm24.
165 // (0 = no error, 0x0100 = single bit error, 0x1000 = double error)
166 
167 static short hamm24err[64] =
168 {
169  0x0000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000,
170  0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000,
171  0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000,
172  0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000,
173  0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100,
174  0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100,
175  0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100, 0x0100,
176  0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000, 0x1000,
177 };
178 
179 
180 
181 // mapping from parity checks made by table hamm24par to faulty bit
182 // in the decoded 18 bit word.
183 
184 static int hamm24cor[64] =
185 {
186  0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000,
187  0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000,
188  0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000,
189  0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000,
190  0x00000, 0x00000, 0x00000, 0x00001, 0x00000, 0x00002, 0x00004, 0x00008,
191  0x00000, 0x00010, 0x00020, 0x00040, 0x00080, 0x00100, 0x00200, 0x00400,
192  0x00000, 0x00800, 0x01000, 0x02000, 0x04000, 0x08000, 0x10000, 0x20000,
193  0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000, 0x00000,
194 };
195 
196 
197 
198 int
199 hamm8(const unsigned char *p, int *err)
200 {
201  int a = hammtab[p[0]];
202  *err += a;
203  return a & 15;
204 }
205 
206 int
207 hamm16(const unsigned char *p, int *err)
208 {
209  int a = hammtab[p[0]];
210  int b = hammtab[p[1]];
211  *err += a;
212  *err += b;
213  return (a & 15) | (b & 15) * 16;
214 }
215 
216 int
217 hamm24(const unsigned char *p, int *err)
218 {
219  int e = hamm24par[0][p[0]] ^ hamm24par[1][p[1]] ^ hamm24par[2][p[2]];
220  int x = hamm24val[p[0]] + p[1] % 128 * 16 + p[2] % 128 * 2048;
221 
222  *err += hamm24err[e];
223  return x ^ hamm24cor[e];
224 }
225 
226 int
227 chk_parity(unsigned char *p, int n)
228 {
229  int err;
230 
231  for (err = 0; n--; p++)
232  if (hamm24par[0][*p] & 32)
233  *p &= 0x7f;
234  else
235  *p = BAD_CHAR, err++;
236  return err;
237 }
238 
int hamm8(const unsigned char *p, int *err)
Definition: hamm.c:199
#define BAD_CHAR
Definition: vt.h:6
int chk_parity(unsigned char *p, int n)
Definition: hamm.c:227
static char hamm24par[3][256]
Definition: hamm.c:81
unsigned char b
Definition: ParseText.cpp:329
static short hamm24err[64]
Definition: hamm.c:167
int hamm16(const unsigned char *p, int *err)
Definition: hamm.c:207
static char hamm24val[256]
Definition: hamm.c:141
static unsigned short hammtab[256]
Definition: hamm.c:13
int hamm24(const unsigned char *p, int *err)
Definition: hamm.c:217
static int hamm24cor[64]
Definition: hamm.c:184