1 /**
2 * libdmtx - Data Matrix Encoding/Decoding Library
3 * Copyright 2011 Mike Laughton. All rights reserved.
4 * Copyright 2012-2016 Vadim A. Misbakh-Soloviov. All rights reserved.
5 *
6 * See LICENSE file in the main project directory for full
7 * terms of use and distribution.
8 *
9 * ---------------------------------------------------------
10 * Portions of this file were derived from the Reed-Solomon
11 * encoder/decoder released by Simon Rockliff in June 1991.
12 * ---------------------------------------------------------
13 *
14 * Contact:
15 * Vadim A. Misbakh-Soloviov <dmtx@mva.name>
16 * Mike Laughton <mike@dragonflylogic.com>
17 *
18 * \file dmtxreedsol.c
19 */
20
21 /**
22 * TODO:
23 * o try doxygen using using the JavaDoc style and JAVADOC_AUTOBRIEF = YES
24 * o switch doxygen to simplified syntax, and using "\file" instead of "@file"
25 */
26
27 #define NN 255
28 #define MAX_ERROR_WORD_COUNT 68
29
30 /* GF add (a + b) */
31 #define GfAdd(a,b) \
32 ((a) ^ (b))
33
34 /* GF multiply (a * b) */
35 #define GfMult(a,b) \
36 (((a) == 0 || (b) == 0) ? 0 : antilog301[(log301[(a)] + log301[(b)]) % NN])
37
38 /* GF multiply by antilog (a * alpha**b) */
39 #define GfMultAntilog(a,b) \
40 (((a) == 0) ? 0 : antilog301[(log301[(a)] + (b)) % NN])
41
42 /* GF(256) log values using primitive polynomial 301 */
43 static DmtxByte log301[] =
44 { 255, 0, 1, 240, 2, 225, 241, 53, 3, 38, 226, 133, 242, 43, 54, 210,
45 4, 195, 39, 114, 227, 106, 134, 28, 243, 140, 44, 23, 55, 118, 211, 234,
46 5, 219, 196, 96, 40, 222, 115, 103, 228, 78, 107, 125, 135, 8, 29, 162,
47 244, 186, 141, 180, 45, 99, 24, 49, 56, 13, 119, 153, 212, 199, 235, 91,
48 6, 76, 220, 217, 197, 11, 97, 184, 41, 36, 223, 253, 116, 138, 104, 193,
49 229, 86, 79, 171, 108, 165, 126, 145, 136, 34, 9, 74, 30, 32, 163, 84,
50 245, 173, 187, 204, 142, 81, 181, 190, 46, 88, 100, 159, 25, 231, 50, 207,
51 57, 147, 14, 67, 120, 128, 154, 248, 213, 167, 200, 63, 236, 110, 92, 176,
52 7, 161, 77, 124, 221, 102, 218, 95, 198, 90, 12, 152, 98, 48, 185, 179,
53 42, 209, 37, 132, 224, 52, 254, 239, 117, 233, 139, 22, 105, 27, 194, 113,
54 230, 206, 87, 158, 80, 189, 172, 203, 109, 175, 166, 62, 127, 247, 146, 66,
55 137, 192, 35, 252, 10, 183, 75, 216, 31, 83, 33, 73, 164, 144, 85, 170,
56 246, 65, 174, 61, 188, 202, 205, 157, 143, 169, 82, 72, 182, 215, 191, 251,
57 47, 178, 89, 151, 101, 94, 160, 123, 26, 112, 232, 21, 51, 238, 208, 131,
58 58, 69, 148, 18, 15, 16, 68, 17, 121, 149, 129, 19, 155, 59, 249, 70,
59 214, 250, 168, 71, 201, 156, 64, 60, 237, 130, 111, 20, 93, 122, 177, 150 };
60
61 /* GF(256) antilog values using primitive polynomial 301 */
62 static DmtxByte antilog301[] =
63 { 1, 2, 4, 8, 16, 32, 64, 128, 45, 90, 180, 69, 138, 57, 114, 228,
64 229, 231, 227, 235, 251, 219, 155, 27, 54, 108, 216, 157, 23, 46, 92, 184,
65 93, 186, 89, 178, 73, 146, 9, 18, 36, 72, 144, 13, 26, 52, 104, 208,
66 141, 55, 110, 220, 149, 7, 14, 28, 56, 112, 224, 237, 247, 195, 171, 123,
67 246, 193, 175, 115, 230, 225, 239, 243, 203, 187, 91, 182, 65, 130, 41, 82,
68 164, 101, 202, 185, 95, 190, 81, 162, 105, 210, 137, 63, 126, 252, 213, 135,
69 35, 70, 140, 53, 106, 212, 133, 39, 78, 156, 21, 42, 84, 168, 125, 250,
70 217, 159, 19, 38, 76, 152, 29, 58, 116, 232, 253, 215, 131, 43, 86, 172,
71 117, 234, 249, 223, 147, 11, 22, 44, 88, 176, 77, 154, 25, 50, 100, 200,
72 189, 87, 174, 113, 226, 233, 255, 211, 139, 59, 118, 236, 245, 199, 163, 107,
73 214, 129, 47, 94, 188, 85, 170, 121, 242, 201, 191, 83, 166, 97, 194, 169,
74 127, 254, 209, 143, 51, 102, 204, 181, 71, 142, 49, 98, 196, 165, 103, 206,
75 177, 79, 158, 17, 34, 68, 136, 61, 122, 244, 197, 167, 99, 198, 161, 111,
76 222, 145, 15, 30, 60, 120, 240, 205, 183, 67, 134, 33, 66, 132, 37, 74,
77 148, 5, 10, 20, 40, 80, 160, 109, 218, 153, 31, 62, 124, 248, 221, 151,
78 3, 6, 12, 24, 48, 96, 192, 173, 119, 238, 241, 207, 179, 75, 150, 0 };
79
80 /**
81 * Encode xyz.
82 * More detailed description.
83 * \param message
84 * \param sizeIdx
85 * \return Function success (DmtxPass|DmtxFail)
86 */
87 #undef CHKPASS
88 #define CHKPASS { if(passFail == DmtxFail) return DmtxFail; }
89 static DmtxPassFail
RsEncode(DmtxMessage * message,int sizeIdx)90 RsEncode(DmtxMessage *message, int sizeIdx)
91 {
92 int i, j;
93 int blockStride, blockIdx;
94 int blockErrorWords, symbolDataWords, symbolErrorWords, symbolTotalWords;
95 DmtxPassFail passFail;
96 DmtxByte val, *eccPtr;
97 DmtxByte genStorage[MAX_ERROR_WORD_COUNT];
98 DmtxByte eccStorage[MAX_ERROR_WORD_COUNT];
99 DmtxByteList gen = dmtxByteListBuild(genStorage, sizeof(genStorage));
100 DmtxByteList ecc = dmtxByteListBuild(eccStorage, sizeof(eccStorage));
101
102 blockStride = dmtxGetSymbolAttribute(DmtxSymAttribInterleavedBlocks, sizeIdx);
103 blockErrorWords = dmtxGetSymbolAttribute(DmtxSymAttribBlockErrorWords, sizeIdx);
104 symbolDataWords = dmtxGetSymbolAttribute(DmtxSymAttribSymbolDataWords, sizeIdx);
105 symbolErrorWords = dmtxGetSymbolAttribute(DmtxSymAttribSymbolErrorWords, sizeIdx);
106 symbolTotalWords = symbolDataWords + symbolErrorWords;
107
108 /* Populate generator polynomial */
109 RsGenPoly(&gen, blockErrorWords);
110
111 /* For each interleaved block... */
112 for(blockIdx = 0; blockIdx < blockStride; blockIdx++)
113 {
114 /* Generate error codewords */
115 dmtxByteListInit(&ecc, blockErrorWords, 0, &passFail); CHKPASS;
116 for(i = blockIdx; i < symbolDataWords; i += blockStride)
117 {
118 val = GfAdd(ecc.b[blockErrorWords-1], message->code[i]);
119
120 for(j = blockErrorWords - 1; j > 0; j--)
121 {
122 DMTX_CHECK_BOUNDS(&ecc, j); DMTX_CHECK_BOUNDS(&ecc, j-1); DMTX_CHECK_BOUNDS(&gen, j);
123 ecc.b[j] = GfAdd(ecc.b[j-1], GfMult(gen.b[j], val));
124 }
125
126 ecc.b[0] = GfMult(gen.b[0], val);
127 }
128
129 /* Copy to output message */
130 eccPtr = ecc.b + blockErrorWords;
131 for(i = symbolDataWords + blockIdx; i < symbolTotalWords; i += blockStride)
132 message->code[i] = *(--eccPtr);
133
134 assert(ecc.b == eccPtr);
135 }
136
137 return DmtxPass;
138 }
139
140 /**
141 * Decode xyz.
142 * More detailed description.
143 * \param code
144 * \param sizeIdx
145 * \param fix
146 * \return Function success (DmtxPass|DmtxFail)
147 */
148 #undef CHKPASS
149 #define CHKPASS { if(passFail == DmtxFail) return DmtxFail; }
150 static DmtxPassFail
RsDecode(unsigned char * code,int sizeIdx,int fix)151 RsDecode(unsigned char *code, int sizeIdx, int fix)
152 {
153 int i;
154 int blockStride, blockIdx;
155 int blockDataWords, blockErrorWords, blockMaxCorrectable;
156 // int blockDataWords, blockErrorWords, blockTotalWords, blockMaxCorrectable;
157 int symbolDataWords, symbolErrorWords, symbolTotalWords;
158 DmtxBoolean error, repairable;
159 DmtxPassFail passFail;
160 unsigned char *word;
161 DmtxByte elpStorage[MAX_ERROR_WORD_COUNT];
162 DmtxByte synStorage[MAX_ERROR_WORD_COUNT+1];
163 DmtxByte recStorage[NN];
164 DmtxByte locStorage[NN];
165 DmtxByteList elp = dmtxByteListBuild(elpStorage, sizeof(elpStorage));
166 DmtxByteList syn = dmtxByteListBuild(synStorage, sizeof(synStorage));
167 DmtxByteList rec = dmtxByteListBuild(recStorage, sizeof(recStorage));
168 DmtxByteList loc = dmtxByteListBuild(locStorage, sizeof(locStorage));
169
170 blockStride = dmtxGetSymbolAttribute(DmtxSymAttribInterleavedBlocks, sizeIdx);
171 blockErrorWords = dmtxGetSymbolAttribute(DmtxSymAttribBlockErrorWords, sizeIdx);
172 blockMaxCorrectable = dmtxGetSymbolAttribute(DmtxSymAttribBlockMaxCorrectable, sizeIdx);
173 symbolDataWords = dmtxGetSymbolAttribute(DmtxSymAttribSymbolDataWords, sizeIdx);
174 symbolErrorWords = dmtxGetSymbolAttribute(DmtxSymAttribSymbolErrorWords, sizeIdx);
175 symbolTotalWords = symbolDataWords + symbolErrorWords;
176
177 /* For each interleaved block */
178 for(blockIdx = 0; blockIdx < blockStride; blockIdx++)
179 {
180 /* Data word count depends on blockIdx due to special case at 144x144 */
181 blockDataWords = dmtxGetBlockDataSize(sizeIdx, blockIdx);
182 // blockTotalWords = blockErrorWords + blockDataWords;
183
184 /* Populate received list (rec) with data and error codewords */
185 dmtxByteListInit(&rec, 0, 0, &passFail); CHKPASS;
186
187 /* Start with final error word and work backward */
188 word = code + symbolTotalWords + blockIdx - blockStride;
189 for(i = 0; i < blockErrorWords; i++)
190 {
191 dmtxByteListPush(&rec, *word, &passFail); CHKPASS;
192 word -= blockStride;
193 }
194
195 /* Start with final data word and work backward */
196 word = code + blockIdx + (blockStride * (blockDataWords - 1));
197 for(i = 0; i < blockDataWords; i++)
198 {
199 dmtxByteListPush(&rec, *word, &passFail); CHKPASS;
200 word -= blockStride;
201 }
202
203 /* Compute syndromes (syn) */
204 error = RsComputeSyndromes(&syn, &rec, blockErrorWords);
205
206 /* Error(s) detected: Attempt repair */
207 if(error)
208 {
209 /* Find error locator polynomial (elp) */
210 repairable = RsFindErrorLocatorPoly(&elp, &syn, blockErrorWords, blockMaxCorrectable);
211 if(!repairable)
212 return DmtxFail;
213
214 /* Find error positions (loc) */
215 repairable = RsFindErrorLocations(&loc, &elp);
216 if(!repairable)
217 return DmtxFail;
218
219 /* Find error values and repair */
220 RsRepairErrors(&rec, &loc, &elp, &syn);
221 }
222
223 /*
224 * Overwrite output with correct/corrected values
225 */
226
227 /* Start with first data word and work forward */
228 word = code + blockIdx;
229 for(i = 0; i < blockDataWords; i++)
230 {
231 *word = dmtxByteListPop(&rec, &passFail); CHKPASS;
232 word += blockStride;
233 }
234
235 /* Start with first error word and work forward */
236 word = code + symbolDataWords + blockIdx;
237 for(i = 0; i < blockErrorWords; i++)
238 {
239 *word = dmtxByteListPop(&rec, &passFail); CHKPASS;
240 word += blockStride;
241 }
242 }
243
244 return DmtxPass;
245 }
246
247 /**
248 * Populate generator polynomial.
249 * More detailed description.
250 * \param gen
251 * \param errorWordCount
252 * \return Function success (DmtxPass|DmtxFail)
253 */
254 #undef CHKPASS
255 #define CHKPASS { if(passFail == DmtxFail) return DmtxFail; }
256 static DmtxPassFail
RsGenPoly(DmtxByteList * gen,int errorWordCount)257 RsGenPoly(DmtxByteList *gen, int errorWordCount)
258 {
259 int i, j;
260 DmtxPassFail passFail;
261
262 /* Initialize all coefficients to 1 */
263 dmtxByteListInit(gen, errorWordCount, 1, &passFail); CHKPASS;
264
265 /* Generate polynomial */
266 for(i = 0; i < gen->length; i++)
267 {
268 for(j = i; j >= 0; j--)
269 {
270 gen->b[j] = GfMultAntilog(gen->b[j], i+1);
271 if(j > 0)
272 gen->b[j] = GfAdd(gen->b[j], gen->b[j-1]);
273 }
274 }
275
276 return DmtxPass;
277 }
278
279 /**
280 * Populate generator polynomial.
281 * Assume we have received bits grouped into mm-bit symbols in rec[i],
282 * i=0..(nn-1), and rec[i] is index form (ie as powers of alpha). We first
283 * compute the 2*tt syndromes by substituting alpha**i into rec(X) and
284 * evaluating, storing the syndromes in syn[i], i=1..2tt (leave syn[0] zero).
285 * \param syn
286 * \param rec
287 * \param blockErrorWords
288 * \return Are error(s) present? (DmtxPass|DmtxFail)
289 */
290 /* XXX this CHKPASS isn't doing what we want ... really need a error reporting strategy */
291 #undef CHKPASS
292 #define CHKPASS { if(passFail == DmtxFail) return DmtxTrue; }
293 static DmtxBoolean
RsComputeSyndromes(DmtxByteList * syn,const DmtxByteList * rec,int blockErrorWords)294 RsComputeSyndromes(DmtxByteList *syn, const DmtxByteList *rec, int blockErrorWords)
295 {
296 int i, j;
297 DmtxPassFail passFail;
298 DmtxBoolean error = DmtxFalse;
299
300 /* Initialize all coefficients to 0 */
301 dmtxByteListInit(syn, blockErrorWords + 1, 0, &passFail); CHKPASS;
302
303 for(i = 1; i < syn->length; i++)
304 {
305 /* Calculate syndrome at i */
306 for(j = 0; j < rec->length; j++) /* alternatively: j < blockTotalWords */
307 syn->b[i] = GfAdd(syn->b[i], GfMultAntilog(rec->b[j], i*j));
308
309 /* Non-zero syndrome indicates presence of error(s) */
310 if(syn->b[i] != 0)
311 error = DmtxTrue;
312 }
313
314 return error;
315 }
316
317 /**
318 * Find the error location polynomial using Berlekamp-Massey.
319 * More detailed description.
320 * \param elpOut
321 * \param syn
322 * \param errorWordCount
323 * \param maxCorrectable
324 * \return Is block repairable? (DmtxTrue|DmtxFalse)
325 */
326 /* XXX this CHKPASS isn't doing what we want ... really need a error reporting strategy */
327 #undef CHKPASS
328 #define CHKPASS { if(passFail == DmtxFail) return DmtxFalse; }
329 static DmtxBoolean
RsFindErrorLocatorPoly(DmtxByteList * elpOut,const DmtxByteList * syn,int errorWordCount,int maxCorrectable)330 RsFindErrorLocatorPoly(DmtxByteList *elpOut, const DmtxByteList *syn, int errorWordCount, int maxCorrectable)
331 {
332 int i, iNext, j;
333 int m, mCmp, lambda;
334 DmtxByte disTmp, disStorage[MAX_ERROR_WORD_COUNT+1];
335 DmtxByte elpStorage[MAX_ERROR_WORD_COUNT+2][MAX_ERROR_WORD_COUNT];
336 DmtxByteList dis, elp[MAX_ERROR_WORD_COUNT+2];
337 DmtxPassFail passFail;
338
339 dis = dmtxByteListBuild(disStorage, sizeof(disStorage));
340 dmtxByteListInit(&dis, 0, 0, &passFail); CHKPASS;
341
342 for(i = 0; i < MAX_ERROR_WORD_COUNT + 2; i++)
343 {
344 elp[i] = dmtxByteListBuild(elpStorage[i], sizeof(elpStorage[i]));
345 dmtxByteListInit(&elp[i], 0, 0, &passFail); CHKPASS;
346 }
347
348 /* iNext = 0 */
349 dmtxByteListPush(&elp[0], 1, &passFail); CHKPASS;
350 dmtxByteListPush(&dis, 1, &passFail); CHKPASS;
351
352 /* iNext = 1 */
353 dmtxByteListPush(&elp[1], 1, &passFail); CHKPASS;
354 dmtxByteListPush(&dis, syn->b[1], &passFail); CHKPASS;
355
356 for(iNext = 2, i = 1; /* explicit break */; i = iNext++)
357 {
358 if(dis.b[i] == 0)
359 {
360 /* Simple case: Copy directly from previous iteration */
361 dmtxByteListCopy(&elp[iNext], &elp[i], &passFail); CHKPASS;
362 }
363 else
364 {
365 /* Find earlier iteration (m) that provides maximal (m - lambda) */
366 for(m = 0, mCmp = 1; mCmp < i; mCmp++)
367 if(dis.b[mCmp] != 0 && (mCmp - elp[mCmp].length) >= (m - elp[m].length))
368 m = mCmp;
369
370 /* Calculate error location polynomial elp[i] (set 1st term) */
371 for(lambda = elp[m].length - 1, j = 0; j <= lambda; j++)
372 elp[iNext].b[j+i-m] = antilog301[(NN - log301[dis.b[m]] +
373 log301[dis.b[i]] + log301[elp[m].b[j]]) % NN];
374
375 /* Calculate error location polynomial elp[i] (add 2nd term) */
376 for(lambda = elp[i].length - 1, j = 0; j <= lambda; j++)
377 elp[iNext].b[j] = GfAdd(elp[iNext].b[j], elp[i].b[j]);
378
379 elp[iNext].length = max(elp[i].length, elp[m].length + i - m);
380 }
381
382 lambda = elp[iNext].length - 1;
383 if(i == errorWordCount || i >= lambda + maxCorrectable)
384 break;
385
386 /* Calculate discrepancy dis.b[i] */
387 for(disTmp = syn->b[iNext], j = 1; j <= lambda; j++)
388 disTmp = GfAdd(disTmp, GfMult(syn->b[iNext-j], elp[iNext].b[j]));
389
390 assert(dis.length == iNext);
391 dmtxByteListPush(&dis, disTmp, &passFail); CHKPASS;
392 }
393
394 dmtxByteListCopy(elpOut, &elp[iNext], &passFail); CHKPASS;
395
396 return (lambda <= maxCorrectable) ? DmtxTrue : DmtxFalse;
397 }
398
399 /**
400 * Find roots of the error locator polynomial (Chien Search).
401 * If the degree of elp is <= tt, we substitute alpha**i, i=1..n into the elp
402 * to get the roots, hence the inverse roots, the error location numbers.
403 * If the number of errors located does not equal the degree of the elp, we
404 * have more than tt errors and cannot correct them.
405 * \param loc
406 * \param elp
407 * \return Is block repairable? (DmtxTrue|DmtxFalse)
408 */
409 #undef CHKPASS
410 #define CHKPASS { if(passFail == DmtxFail) return DmtxFalse; }
411 static DmtxBoolean
RsFindErrorLocations(DmtxByteList * loc,const DmtxByteList * elp)412 RsFindErrorLocations(DmtxByteList *loc, const DmtxByteList *elp)
413 {
414 int i, j;
415 int lambda = elp->length - 1;
416 DmtxPassFail passFail;
417 DmtxByte q, regStorage[MAX_ERROR_WORD_COUNT];
418 DmtxByteList reg = dmtxByteListBuild(regStorage, sizeof(regStorage));
419
420 dmtxByteListCopy(®, elp, &passFail); CHKPASS;
421 dmtxByteListInit(loc, 0, 0, &passFail); CHKPASS;
422
423 for(i = 1; i <= NN; i++)
424 {
425 for(q = 1, j = 1; j <= lambda; j++)
426 {
427 reg.b[j] = GfMultAntilog(reg.b[j], j);
428 q = GfAdd(q, reg.b[j]);
429 }
430
431 if(q == 0)
432 {
433 dmtxByteListPush(loc, NN - i, &passFail); CHKPASS;
434 }
435 }
436
437 return (loc->length == lambda) ? DmtxTrue : DmtxFalse;
438 }
439
440 /**
441 * Find the error values and repair.
442 * Solve for the error value at the error location and correct the error. The
443 * procedure is that found in Lin and Costello.
444 * For the cases where the number of errors is known to be too large to
445 * correct, the information symbols as received are output (the advantage of
446 * systematic encoding is that hopefully some of the information symbols will
447 * be okay and that if we are in luck, the errors are in the parity part of
448 * the transmitted codeword).
449 * \param rec
450 * \param loc
451 * \param elp
452 * \param syn
453 */
454 #undef CHKPASS
455 #define CHKPASS { if(passFail == DmtxFail) return DmtxFail; }
456 static DmtxPassFail
RsRepairErrors(DmtxByteList * rec,const DmtxByteList * loc,const DmtxByteList * elp,const DmtxByteList * syn)457 RsRepairErrors(DmtxByteList *rec, const DmtxByteList *loc, const DmtxByteList *elp, const DmtxByteList *syn)
458 {
459 int i, j, q;
460 int lambda = elp->length - 1;
461 DmtxPassFail passFail;
462 DmtxByte zVal, root, err;
463 DmtxByte zStorage[MAX_ERROR_WORD_COUNT+1];
464 DmtxByteList z = dmtxByteListBuild(zStorage, sizeof(zStorage));
465
466 /* Form polynomial z(x) */
467 dmtxByteListPush(&z, 1, &passFail); CHKPASS;
468 for(i = 1; i <= lambda; i++)
469 {
470 for(zVal = GfAdd(syn->b[i], elp->b[i]), j = 1; j < i; j++)
471 zVal= GfAdd(zVal, GfMult(elp->b[i-j], syn->b[j]));
472 dmtxByteListPush(&z, zVal, &passFail); CHKPASS;
473 }
474
475 for(i = 0; i < lambda; i++)
476 {
477 /* Calculate numerator of error term */
478 root = NN - loc->b[i];
479
480 for(err = 1, j = 1; j <= lambda; j++)
481 err = GfAdd(err, GfMultAntilog(z.b[j], j * root));
482
483 if(err == 0)
484 continue;
485
486 /* Calculate denominator of error term */
487 for(q = 0, j = 0; j < lambda; j++)
488 {
489 if(j != i)
490 q += log301[1 ^ antilog301[(loc->b[j] + root) % NN]];
491 }
492 q %= NN;
493
494 err = GfMultAntilog(err, NN - q);
495 rec->b[loc->b[i]] = GfAdd(rec->b[loc->b[i]], err);
496 }
497
498 return DmtxPass;
499 }
500