1 /*------------------------------------------------------------------------
2 * Copyright 2010 (c) Jeff Brown <spadix@users.sourceforge.net>
3 *
4 * This file is part of the ZBar Bar Code Reader.
5 *
6 * The ZBar Bar Code Reader is free software; you can redistribute it
7 * and/or modify it under the terms of the GNU Lesser Public License as
8 * published by the Free Software Foundation; either version 2.1 of
9 * the License, or (at your option) any later version.
10 *
11 * The ZBar Bar Code Reader is distributed in the hope that it will be
12 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
13 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser Public License
17 * along with the ZBar Bar Code Reader; if not, write to the Free
18 * Software Foundation, Inc., 51 Franklin St, Fifth Floor,
19 * Boston, MA 02110-1301 USA
20 *
21 * http://sourceforge.net/projects/zbar
22 *------------------------------------------------------------------------*/
23
24 #include <config.h>
25 #include <zbar.h>
26
27 #ifdef DEBUG_DATABAR
28 # define DEBUG_LEVEL (DEBUG_DATABAR)
29 #endif
30 #include "debug.h"
31 #include "decoder.h"
32
33 #define GS ('\035')
34
35 enum { SCH_NUM, SCH_ALNUM, SCH_ISO646 };
36
37 static const signed char finder_hash[0x20] = {
38 0x16, 0x1f, 0x02, 0x00, 0x03, 0x00, 0x06, 0x0b,
39 0x1f, 0x0e, 0x17, 0x0c, 0x0b, 0x14, 0x11, 0x0c,
40 0x1f, 0x03, 0x13, 0x08, 0x00, 0x0a, -1, 0x16,
41 0x0c, 0x09, -1, 0x1a, 0x1f, 0x1c, 0x00, -1,
42 };
43
44 /* DataBar character encoding groups */
45 struct group_s {
46 unsigned short sum;
47 unsigned char wmax;
48 unsigned char todd;
49 unsigned char teven;
50 } groups[] = {
51 /* (17,4) DataBar Expanded character groups */
52 { 0, 7, 87, 4 },
53 { 348, 5, 52, 20 },
54 { 1388, 4, 30, 52 },
55 { 2948, 3, 10, 104 },
56 { 3988, 1, 1, 204 },
57
58 /* (16,4) DataBar outer character groups */
59 { 0, 8, 161, 1 },
60 { 161, 6, 80, 10 },
61 { 961, 4, 31, 34 },
62 { 2015, 3, 10, 70 },
63 { 2715, 1, 1, 126 },
64
65 /* (15,4) DataBar inner character groups */
66 { 1516, 8, 81, 1 },
67 { 1036, 6, 48, 10 },
68 { 336, 4, 20, 35 },
69 { 0, 2, 4, 84 },
70 };
71
72 static const unsigned char exp_sequences[] = {
73 /* sequence Group 1 */
74 0x01,
75 0x23,
76 0x25, 0x07,
77 0x29, 0x47,
78 0x29, 0x67, 0x0b,
79 0x29, 0x87, 0xab,
80 /* sequence Group 2 */
81 0x21, 0x43, 0x65, 0x07,
82 0x21, 0x43, 0x65, 0x89,
83 0x21, 0x43, 0x65, 0xa9, 0x0b,
84 0x21, 0x43, 0x67, 0x89, 0xab
85 };
86
87 /* DataBar expanded checksum multipliers */
88 static const unsigned char exp_checksums[] = {
89 1, 189, 62, 113, 46, 43, 109, 134, 6, 79, 161, 45
90 };
91
92 static inline void
append_check14(unsigned char * buf)93 append_check14 (unsigned char *buf)
94 {
95 unsigned char chk = 0, d;
96 int i;
97 for(i = 13; --i >= 0; ) {
98 d = *(buf++) - '0';
99 chk += d;
100 if(!(i & 1))
101 chk += d << 1;
102 }
103 chk %= 10;
104 if(chk)
105 chk = 10 - chk;
106 *buf = chk + '0';
107 }
108
109 static inline void
decode10(unsigned char * buf,unsigned long n,int i)110 decode10 (unsigned char *buf,
111 unsigned long n,
112 int i)
113 {
114 buf += i;
115 while(--i >= 0) {
116 unsigned char d = n % 10;
117 n /= 10;
118 *--buf = '0' + d;
119 }
120 }
121
122 #define VAR_MAX(l, i) ((((l) * 12 + (i)) * 2 + 6) / 7)
123
124 #define FEED_BITS(b) \
125 while(i < (b) && len) { \
126 d = (d << 12) | (*(data++) & 0xfff); \
127 i += 12; \
128 len--; \
129 dbprintf(2, " %03lx", d & 0xfff); \
130 }
131
132 #define PUSH_CHAR(c) \
133 *(buf++) = (c)
134
135 #define PUSH_CHAR4(c0, c1, c2, c3) do { \
136 PUSH_CHAR(c0); \
137 PUSH_CHAR(c1); \
138 PUSH_CHAR(c2); \
139 PUSH_CHAR(c3); \
140 } while(0);
141
142 static inline int
databar_postprocess_exp(zbar_decoder_t * dcode,int * data)143 databar_postprocess_exp (zbar_decoder_t *dcode,
144 int *data)
145 {
146 int i = 0, enc;
147 unsigned n;
148 unsigned char *buf;
149 unsigned long d = *(data++);
150 int len = d / 211 + 4, buflen;
151
152 /* grok encodation method */
153 d = *(data++);
154 dbprintf(2, "\n len=%d %03lx", len, d & 0xfff);
155 n = (d >> 4) & 0x7f;
156 if(n >= 0x40) {
157 i = 10;
158 enc = 1;
159 buflen = 2 + 14 + VAR_MAX(len, 10 - 2 - 44 + 6) + 2;
160 }
161 else if(n >= 0x38) {
162 i = 4;
163 enc = 6 + (n & 7);
164 buflen = 2 + 14 + 4 + 6 + 2 + 6 + 2;
165 }
166 else if(n >= 0x30) {
167 i = 6;
168 enc = 2 + ((n >> 2) & 1);
169 buflen = 2 + 14 + 4 + 3 + VAR_MAX(len, 6 - 2 - 44 - 2 - 10) + 2;
170 }
171 else if(n >= 0x20) {
172 i = 7;
173 enc = 4 + ((n >> 3) & 1);
174 buflen = 2 + 14 + 4 + 6;
175 }
176 else {
177 i = 9;
178 enc = 0;
179 buflen = VAR_MAX(len, 9 - 2) + 2;
180 }
181 dbprintf(2, " buflen=%d enc=%d", buflen, enc);
182 zassert(buflen > 2, -1, "buflen=%d\n", buflen);
183
184 if(enc < 4) {
185 /* grok variable length symbol bit field */
186 if((len ^ (d >> (--i))) & 1)
187 /* even/odd length mismatch */
188 return(-1);
189 if(((d >> (--i)) & 1) != (len > 14))
190 /* size group mismatch */
191 return(-1);
192 }
193 len -= 2;
194 dbprintf(2, " [%d+%d]", i, len);
195
196 if(size_buf(dcode, buflen))
197 return(-1);
198 buf = dcode->buf;
199
200 /* handle compressed fields */
201 if(enc) {
202 PUSH_CHAR('0');
203 PUSH_CHAR('1');
204 }
205
206 if(enc == 1) {
207 i -= 4;
208 n = (d >> i) & 0xf;
209 if(i >= 10)
210 return(-1);
211 PUSH_CHAR('0' + n);
212 }
213 else if(enc)
214 PUSH_CHAR('9');
215
216 if(enc) {
217 int j;
218 for(j = 0; j < 4; j++) {
219 FEED_BITS(10);
220 i -= 10;
221 n = (d >> i) & 0x3ff;
222 if(n >= 1000)
223 return(-1);
224 decode10(buf, n, 3);
225 buf += 3;
226 }
227 append_check14(buf - 13);
228 buf++;
229 }
230
231 switch(enc)
232 {
233 case 2: /* 01100: AI 392x */
234 FEED_BITS(2);
235 i -= 2;
236 n = (d >> i) & 0x3;
237 PUSH_CHAR4('3', '9', '2', '0' + n);
238 break;
239
240 case 3: /* 01101: AI 393x */
241 FEED_BITS(12);
242 i -= 2;
243 n = (d >> i) & 0x3;
244 PUSH_CHAR4('3', '9', '3', '0' + n);
245 i -= 10;
246 n = (d >> i) & 0x3ff;
247 if(n >= 1000)
248 return(-1);
249 decode10(buf, n, 3);
250 buf += 3;
251 break;
252
253 case 4: /* 0100: AI 3103 */
254 FEED_BITS(15);
255 i -= 15;
256 n = (d >> i) & 0x7fff;
257 PUSH_CHAR4('3', '1', '0', '3');
258 decode10(buf, n, 6);
259 buf += 6;
260 break;
261
262 case 5: /* 0101: AI 3202/3203 */
263 FEED_BITS(15);
264 i -= 15;
265 n = (d >> i) & 0x7fff;
266 dbprintf(2, " v=%d", n);
267 PUSH_CHAR4('3', '2', '0', (n >= 10000) ? '3' : '2' );
268 if(n >= 10000)
269 n -= 10000;
270 decode10(buf, n, 6);
271 buf += 6;
272 break;
273 }
274 if(enc >= 6) {
275 /* 0111000 - 0111111: AI 310x/320x + AI 11/13/15/17 */
276 PUSH_CHAR4('3', '1' + (enc & 1), '0', 'x');
277 FEED_BITS(20);
278 i -= 20;
279 n = (d >> i) & 0xfffff;
280 dbprintf(2, " [%d+%d] %d", i, len, n);
281 if(n >= 1000000)
282 return(-1);
283 decode10(buf, n, 6);
284 *(buf - 1) = *buf;
285 *buf = '0';
286 buf += 6;
287
288 FEED_BITS(16);
289 i -= 16;
290 n = (d >> i) & 0xffff;
291 if(n < 38400) {
292 int dd, mm, yy;
293 dd = n % 32;
294 n /= 32;
295 mm = n % 12 + 1;
296 n /= 12;
297 yy = n;
298 PUSH_CHAR('1');
299 PUSH_CHAR('0' + ((enc - 6) | 1));
300 decode10(buf, yy, 2);
301 buf += 2;
302 decode10(buf, mm, 2);
303 buf += 2;
304 decode10(buf, dd, 2);
305 buf += 2;
306 }
307 else if(n > 38400)
308 return(-1);
309 }
310
311 if(enc < 4) {
312 /* remainder is general-purpose data compaction */
313 int scheme = SCH_NUM;
314 while(i > 0 || len > 0) {
315 FEED_BITS(8);
316 dbprintf(2, " [%d+%d]", i, len);
317
318 if(scheme == SCH_NUM) {
319 int n1;
320 i -= 4;
321 if(i < 0)
322 break;
323 if(!((d >> i) & 0xf)) {
324 scheme = SCH_ALNUM;
325 dbprintf(2, ">A");
326 continue;
327 }
328 if(!len && i < 3) {
329 /* special case last digit */
330 n = ((d >> i) & 0xf) - 1;
331 if(n > 9)
332 return(-1);
333 *(buf++) = '0' + n;
334 break;
335 }
336 i -= 3;
337 zassert(i >= 0, -1, "\n");
338 n = ((d >> i) & 0x7f) - 8;
339 n1 = n % 11;
340 n = n / 11;
341 dbprintf(2, "N%d%d", n, n1);
342 *(buf++) = (n < 10) ? '0' + n : GS;
343 *(buf++) = (n1 < 10) ? '0' + n1 : GS;
344 }
345 else {
346 unsigned c = 0;
347 i -= 3;
348 if(i < 0)
349 break;
350 if(!((d >> i) & 0x7)) {
351 scheme = SCH_NUM;
352 continue;
353 }
354 i -= 2;
355 if(i < 0)
356 break;
357 n = (d >> i) & 0x1f;
358 if(n == 0x04) {
359 scheme ^= 0x3;
360 dbprintf(2, ">%d", scheme);
361 }
362 else if(n == 0x0f)
363 c = GS;
364 else if(n < 0x0f)
365 c = 43 + n;
366 else if(scheme == SCH_ALNUM) {
367 i--;
368 if(i < 0)
369 return(-1);
370 n = (d >> i) & 0x1f;
371 if(n < 0x1a)
372 c = 'A' + n;
373 else if(n == 0x1a)
374 c = '*';
375 else if(n < 0x1f)
376 c = ',' + n - 0x1b;
377 else
378 return(-1);
379 }
380 else if(scheme == SCH_ISO646 && n < 0x1d) {
381 i -= 2;
382 if(i < 0)
383 return(-1);
384 n = (d >> i) & 0x3f;
385 if(n < 0x1a)
386 c = 'A' + n;
387 else if(n < 0x34)
388 c = 'a' + n - 0x1a;
389 else
390 return(-1);
391 }
392 else if(scheme == SCH_ISO646) {
393 i -= 3;
394 if(i < 0)
395 return(-1);
396 n = ((d >> i) & 0x1f);
397 dbprintf(2, "(%02x)", n);
398 if(n < 0xa)
399 c = '!' + n - 8;
400 else if(n < 0x15)
401 c = '%' + n - 0xa;
402 else if(n < 0x1b)
403 c = ':' + n - 0x15;
404 else if(n == 0x1b)
405 c = '_';
406 else if(n == 0x1c)
407 c = ' ';
408 else
409 return(-1);
410 }
411 else
412 return(-1);
413
414 if(c) {
415 dbprintf(2, "%d%c", scheme, c);
416 *(buf++) = c;
417 }
418 }
419 }
420 /* FIXME check pad? */
421 }
422
423 i = buf - dcode->buf;
424 zassert(i < dcode->buf_alloc, -1, "i=%02x %s\n", i,
425 _zbar_decoder_buf_dump(dcode->buf, i));
426
427 *buf = 0;
428 dcode->buflen = i;
429 if(i && *--buf == GS) {
430 *buf = 0;
431 dcode->buflen--;
432 }
433
434 dbprintf(2, "\n %s", _zbar_decoder_buf_dump(dcode->buf, dcode->buflen));
435 return(0);
436 }
437 #undef FEED_BITS
438
439 /* convert from heterogeneous base {1597,2841}
440 * to base 10 character representation
441 */
442 static inline void
databar_postprocess(zbar_decoder_t * dcode,unsigned d[4])443 databar_postprocess (zbar_decoder_t *dcode,
444 unsigned d[4])
445 {
446 databar_decoder_t *db = &dcode->databar;
447 int i;
448 unsigned c, chk = 0;
449 unsigned char *buf = dcode->buf;
450 *(buf++) = '0';
451 *(buf++) = '1';
452 buf += 15;
453 *--buf = '\0';
454 *--buf = '\0';
455
456 dbprintf(2, "\n d={%d,%d,%d,%d}", d[0], d[1], d[2], d[3]);
457 unsigned long r = d[0] * 1597 + d[1];
458 d[1] = r / 10000;
459 r %= 10000;
460 r = r * 2841 + d[2];
461 d[2] = r / 10000;
462 r %= 10000;
463 r = r * 1597 + d[3];
464 d[3] = r / 10000;
465 dbprintf(2, " r=%ld", r);
466
467 for(i = 4; --i >= 0; ) {
468 c = r % 10;
469 chk += c;
470 if(i & 1)
471 chk += c << 1;
472 *--buf = c + '0';
473 if(i)
474 r /= 10;
475 }
476
477 dbprintf(2, " d={%d,%d,%d}", d[1], d[2], d[3]);
478 r = d[1] * 2841 + d[2];
479 d[2] = r / 10000;
480 r %= 10000;
481 r = r * 1597 + d[3];
482 d[3] = r / 10000;
483 dbprintf(2, " r=%ld", r);
484
485 for(i = 4; --i >= 0; ) {
486 c = r % 10;
487 chk += c;
488 if(i & 1)
489 chk += c << 1;
490 *--buf = c + '0';
491 if(i)
492 r /= 10;
493 }
494
495 r = d[2] * 1597 + d[3];
496 dbprintf(2, " d={%d,%d} r=%ld", d[2], d[3], r);
497
498 for(i = 5; --i >= 0; ) {
499 c = r % 10;
500 chk += c;
501 if(!(i & 1))
502 chk += c << 1;
503 *--buf = c + '0';
504 if(i)
505 r /= 10;
506 }
507
508 /* NB linkage flag not supported */
509 if(TEST_CFG(db->config, ZBAR_CFG_EMIT_CHECK)) {
510 chk %= 10;
511 if(chk)
512 chk = 10 - chk;
513 buf[13] = chk + '0';
514 dcode->buflen = buf - dcode->buf + 14;
515 }
516 else
517 dcode->buflen = buf - dcode->buf + 13;
518
519 dbprintf(2, "\n %s", _zbar_decoder_buf_dump(dcode->buf, 16));
520 }
521
522 static inline int
check_width(unsigned wf,unsigned wd,unsigned n)523 check_width (unsigned wf,
524 unsigned wd,
525 unsigned n)
526 {
527 unsigned dwf = wf * 3;
528 wd *= 14;
529 wf *= n;
530 return(wf - dwf <= wd && wd <= wf + dwf);
531 }
532
533 static inline void
merge_segment(databar_decoder_t * db,databar_segment_t * seg)534 merge_segment (databar_decoder_t *db,
535 databar_segment_t *seg)
536 {
537 unsigned csegs = db->csegs;
538 int i;
539 for(i = 0; i < csegs; i++) {
540 databar_segment_t *s = db->segs + i;
541 if(s != seg && s->finder == seg->finder && s->exp == seg->exp &&
542 s->color == seg->color && s->side == seg->side &&
543 s->data == seg->data && s->check == seg->check &&
544 check_width(seg->width, s->width, 14)) {
545 /* merge with existing segment */
546 unsigned cnt = s->count;
547 if(cnt < 0x7f)
548 cnt++;
549 seg->count = cnt;
550 seg->partial &= s->partial;
551 seg->width = (3 * seg->width + s->width + 2) / 4;
552 s->finder = -1;
553 dbprintf(2, " dup@%d(%d,%d)",
554 i, cnt, (db->epoch - seg->epoch) & 0xff);
555 }
556 else if(s->finder >= 0) {
557 unsigned age = (db->epoch - s->epoch) & 0xff;
558 if(age >= 248 || (age >= 128 && s->count < 2))
559 s->finder = -1;
560 }
561 }
562 }
563
564 static inline zbar_symbol_type_t
match_segment(zbar_decoder_t * dcode,databar_segment_t * seg)565 match_segment (zbar_decoder_t *dcode,
566 databar_segment_t *seg)
567 {
568 databar_decoder_t *db = &dcode->databar;
569 unsigned csegs = db->csegs, maxage = 0xfff;
570 int i0, i1, i2, maxcnt = 0;
571 databar_segment_t *smax[3] = { NULL, };
572
573 if(seg->partial && seg->count < 4)
574 return(ZBAR_PARTIAL);
575
576 for(i0 = 0; i0 < csegs; i0++) {
577 databar_segment_t *s0 = db->segs + i0;
578 if(s0 == seg || s0->finder != seg->finder || s0->exp ||
579 s0->color != seg->color || s0->side == seg->side ||
580 (s0->partial && s0->count < 4) ||
581 !check_width(seg->width, s0->width, 14))
582 continue;
583
584 for(i1 = 0; i1 < csegs; i1++) {
585 databar_segment_t *s1 = db->segs + i1;
586 int chkf, chks, chk;
587 unsigned age1;
588 if(i1 == i0 || s1->finder < 0 || s1->exp ||
589 s1->color == seg->color ||
590 (s1->partial && s1->count < 4) ||
591 !check_width(seg->width, s1->width, 14))
592 continue;
593 dbprintf(2, "\n\t[%d,%d] f=%d(0%xx)/%d(%x%x%x)",
594 i0, i1, seg->finder, seg->color,
595 s1->finder, s1->exp, s1->color, s1->side);
596
597 if(seg->color)
598 chkf = seg->finder + s1->finder * 9;
599 else
600 chkf = s1->finder + seg->finder * 9;
601 if(chkf > 72)
602 chkf--;
603 if(chkf > 8)
604 chkf--;
605
606 chks = (seg->check + s0->check + s1->check) % 79;
607
608 if(chkf >= chks)
609 chk = chkf - chks;
610 else
611 chk = 79 + chkf - chks;
612
613 dbprintf(2, " chk=(%d,%d) => %d", chkf, chks, chk);
614 age1 = (((db->epoch - s0->epoch) & 0xff) +
615 ((db->epoch - s1->epoch) & 0xff));
616
617 for(i2 = i1 + 1; i2 < csegs; i2++) {
618 databar_segment_t *s2 = db->segs + i2;
619 unsigned cnt, age2, age;
620 if(i2 == i0 || s2->finder != s1->finder || s2->exp ||
621 s2->color != s1->color || s2->side == s1->side ||
622 s2->check != chk ||
623 (s2->partial && s2->count < 4) ||
624 !check_width(seg->width, s2->width, 14))
625 continue;
626 age2 = (db->epoch - s2->epoch) & 0xff;
627 age = age1 + age2;
628 cnt = s0->count + s1->count + s2->count;
629 dbprintf(2, " [%d] MATCH cnt=%d age=%d", i2, cnt, age);
630 if(maxcnt < cnt ||
631 (maxcnt == cnt && maxage > age)) {
632 maxcnt = cnt;
633 maxage = age;
634 smax[0] = s0;
635 smax[1] = s1;
636 smax[2] = s2;
637 }
638 }
639 }
640 }
641
642 if(!smax[0])
643 return(ZBAR_PARTIAL);
644
645 unsigned d[4];
646 d[(seg->color << 1) | seg->side] = seg->data;
647 for(i0 = 0; i0 < 3; i0++) {
648 d[(smax[i0]->color << 1) | smax[i0]->side] = smax[i0]->data;
649 if(!--(smax[i0]->count))
650 smax[i0]->finder = -1;
651 }
652 seg->finder = -1;
653
654 if(size_buf(dcode, 18))
655 return(ZBAR_PARTIAL);
656
657 if(acquire_lock(dcode, ZBAR_DATABAR))
658 return(ZBAR_PARTIAL);
659
660 databar_postprocess(dcode, d);
661 dcode->modifiers = MOD(ZBAR_MOD_GS1);
662 dcode->direction = 1 - 2 * (seg->side ^ seg->color ^ 1);
663 return(ZBAR_DATABAR);
664 }
665
666 static inline unsigned
lookup_sequence(databar_segment_t * seg,int fixed,int seq[22])667 lookup_sequence (databar_segment_t *seg,
668 int fixed,
669 int seq[22])
670 {
671 unsigned n = seg->data / 211, i;
672 const unsigned char *p;
673 i = (n + 1) / 2 + 1;
674 n += 4;
675 i = (i * i) / 4;
676 dbprintf(2, " {%d,%d:", i, n);
677 p = exp_sequences + i;
678
679 fixed >>= 1;
680 seq[0] = 0;
681 seq[1] = 1;
682 for(i = 2; i < n; ) {
683 int s = *p;
684 if(!(i & 2)) {
685 p++;
686 s >>= 4;
687 }
688 else
689 s &= 0xf;
690 if(s == fixed)
691 fixed = -1;
692 s <<= 1;
693 dbprintf(2, "%x", s);
694 seq[i++] = s++;
695 seq[i++] = s;
696 }
697 dbprintf(2, "}");
698 seq[n] = -1;
699 return(fixed < 1);
700 }
701
702 #define IDX(s) \
703 (((s)->finder << 2) | ((s)->color << 1) | ((s)->color ^ (s)->side))
704
705 static inline zbar_symbol_type_t
match_segment_exp(zbar_decoder_t * dcode,databar_segment_t * seg,int dir)706 match_segment_exp (zbar_decoder_t *dcode,
707 databar_segment_t *seg,
708 int dir)
709 {
710 databar_decoder_t *db = &dcode->databar;
711 int bestsegs[22], i = 0, segs[22], seq[22];
712 int ifixed = seg - db->segs, fixed = IDX(seg), maxcnt = 0;
713 int iseg[DATABAR_MAX_SEGMENTS];
714 unsigned csegs = db->csegs, width = seg->width, maxage = 0x7fff;
715
716 bestsegs[0] = segs[0] = seq[1] = -1;
717 seq[0] = 0;
718
719 dbprintf(2, "\n fixed=%d@%d: ", fixed, ifixed);
720 for(i = csegs, seg = db->segs + csegs - 1; --i >= 0; seg--) {
721 if(seg->exp && seg->finder >= 0 &&
722 (!seg->partial || seg->count >= 4))
723 iseg[i] = IDX(seg);
724 else
725 iseg[i] = -1;
726 dbprintf(2, " %d", iseg[i]);
727 }
728
729 for(i = 0; ; i--) {
730 if(!i)
731 dbprintf(2, "\n ");
732 for(; i >= 0 && seq[i] >= 0; i--) {
733 int j;
734 dbprintf(2, " [%d]%d", i, seq[i]);
735
736 if(seq[i] == fixed) {
737 seg = db->segs + ifixed;
738 if(segs[i] < 0 && check_width(width, seg->width, 14)) {
739 dbprintf(2, "*");
740 j = ifixed;
741 }
742 else
743 continue;
744 }
745 else {
746 for(j = segs[i] + 1; j < csegs; j++) {
747 if(iseg[j] == seq[i] &&
748 (!i || check_width(width, db->segs[j].width, 14))) {
749 seg = db->segs + j;
750 break;
751 }
752 }
753 if(j == csegs)
754 continue;
755 }
756
757 if(!i) {
758 if(!lookup_sequence(seg, fixed, seq)) {
759 dbprintf(2, "[nf]");
760 continue;
761 }
762 width = seg->width;
763 dbprintf(2, " A00@%d", j);
764 }
765 else {
766 width = (width + seg->width) / 2;
767 dbprintf(2, " %c%x%x@%d",
768 'A' + seg->finder, seg->color, seg->side, j);
769 }
770 segs[i++] = j;
771 segs[i++] = -1;
772 }
773 if(i < 0)
774 break;
775
776 seg = db->segs + segs[0];
777 unsigned cnt = 0, chk = 0, age = (db->epoch - seg->epoch) & 0xff;
778 for(i = 1; segs[i] >= 0; i++) {
779 seg = db->segs + segs[i];
780 chk += seg->check;
781 cnt += seg->count;
782 age += (db->epoch - seg->epoch) & 0xff;
783 }
784
785 unsigned data0 = db->segs[segs[0]].data;
786 unsigned chk0 = data0 % 211;
787 chk %= 211;
788
789 dbprintf(2, " chk=%d ?= %d", chk, chk0);
790 if(chk != chk0)
791 continue;
792
793 dbprintf(2, " cnt=%d age=%d", cnt, age);
794 if(maxcnt > cnt || (maxcnt == cnt && maxage <= age))
795 continue;
796
797 dbprintf(2, " !");
798 maxcnt = cnt;
799 maxage = age;
800 for(i = 0; segs[i] >= 0; i++)
801 bestsegs[i] = segs[i];
802 bestsegs[i] = -1;
803 }
804
805 if(bestsegs[0] < 0)
806 return(ZBAR_PARTIAL);
807
808 if(acquire_lock(dcode, ZBAR_DATABAR_EXP))
809 return(ZBAR_PARTIAL);
810
811 for(i = 0; bestsegs[i] >= 0; i++)
812 segs[i] = db->segs[bestsegs[i]].data;
813
814 if(databar_postprocess_exp(dcode, segs)) {
815 release_lock(dcode, ZBAR_DATABAR_EXP);
816 return(ZBAR_PARTIAL);
817 }
818
819 for(i = 0; bestsegs[i] >= 0; i++)
820 if(bestsegs[i] != ifixed) {
821 seg = db->segs + bestsegs[i];
822 if(!--seg->count)
823 seg->finder = -1;
824 }
825
826 /* FIXME stacked rows are frequently reversed,
827 * so direction is impossible to determine at this level
828 */
829 dcode->direction = (1 - 2 * (seg->side ^ seg->color)) * dir;
830 dcode->modifiers = MOD(ZBAR_MOD_GS1);
831 return(ZBAR_DATABAR_EXP);
832 }
833 #undef IDX
834
835 static inline unsigned
calc_check(unsigned sig0,unsigned sig1,unsigned side,unsigned mod)836 calc_check (unsigned sig0,
837 unsigned sig1,
838 unsigned side,
839 unsigned mod)
840 {
841 unsigned chk = 0;
842 int i;
843 for(i = 4; --i >= 0; ) {
844 chk = (chk * 3 + (sig1 & 0xf) + 1) * 3 + (sig0 & 0xf) + 1;
845 sig1 >>= 4;
846 sig0 >>= 4;
847 if(!(i & 1))
848 chk %= mod;
849 }
850 dbprintf(2, " chk=%d", chk);
851
852 if(side)
853 chk = (chk * (6561 % mod)) % mod;
854 return(chk);
855 }
856
857 static inline int
calc_value4(unsigned sig,unsigned n,unsigned wmax,unsigned nonarrow)858 calc_value4 (unsigned sig,
859 unsigned n,
860 unsigned wmax,
861 unsigned nonarrow)
862 {
863 unsigned v = 0;
864 n--;
865
866 unsigned w0 = (sig >> 12) & 0xf;
867 if(w0 > 1) {
868 if(w0 > wmax)
869 return(-1);
870 unsigned n0 = n - w0;
871 unsigned sk20 = (n - 1) * n * (2 * n - 1);
872 unsigned sk21 = n0 * (n0 + 1) * (2 * n0 + 1);
873 v = sk20 - sk21 - 3 * (w0 - 1) * (2 * n - w0);
874
875 if(!nonarrow && w0 > 2 && n > 4) {
876 unsigned k = (n - 2) * (n - 1) * (2 * n - 3) - sk21;
877 k -= 3 * (w0 - 2) * (14 * n - 7 * w0 - 31);
878 v -= k;
879 }
880
881 if(n - 2 > wmax) {
882 unsigned wm20 = 2 * wmax * (wmax + 1);
883 unsigned wm21 = (2 * wmax + 1);
884 unsigned k = sk20;
885 if(n0 > wmax) {
886 k -= sk21;
887 k += 3 * (w0 - 1) * (wm20 - wm21 * (2 * n - w0));
888 }
889 else {
890 k -= (wmax + 1) * (wmax + 2) * (2 * wmax + 3);
891 k += 3 * (n - wmax - 2) * (wm20 - wm21 * (n + wmax + 1));
892 }
893 k *= 3;
894 v -= k;
895 }
896 v /= 12;
897 }
898 else
899 nonarrow = 1;
900 n -= w0;
901
902 unsigned w1 = (sig >> 8) & 0xf;
903 if(w1 > 1) {
904 if(w1 > wmax)
905 return(-1);
906 v += (2 * n - w1) * (w1 - 1) / 2;
907 if(!nonarrow && w1 > 2 && n > 3)
908 v -= (2 * n - w1 - 5) * (w1 - 2) / 2;
909 if(n - 1 > wmax) {
910 if(n - w1 > wmax)
911 v -= (w1 - 1) * (2 * n - w1 - 2 * wmax);
912 else
913 v -= (n - wmax) * (n - wmax - 1);
914 }
915 }
916 else
917 nonarrow = 1;
918 n -= w1;
919
920 unsigned w2 = (sig >> 4) & 0xf;
921 if(w2 > 1) {
922 if(w2 > wmax)
923 return(-1);
924 v += w2 - 1;
925 if(!nonarrow && w2 > 2 && n > 2)
926 v -= n - 2;
927 if(n > wmax)
928 v -= n - wmax;
929 }
930 else
931 nonarrow = 1;
932
933 unsigned w3 = sig & 0xf;
934 if(w3 == 1)
935 nonarrow = 1;
936 else if(w3 > wmax)
937 return(-1);
938
939 if(!nonarrow)
940 return(-1);
941
942 return(v);
943 }
944
945 static inline zbar_symbol_type_t
decode_char(zbar_decoder_t * dcode,databar_segment_t * seg,int off,int dir)946 decode_char (zbar_decoder_t *dcode,
947 databar_segment_t *seg,
948 int off,
949 int dir)
950 {
951 databar_decoder_t *db = &dcode->databar;
952 unsigned s = calc_s(dcode, (dir > 0) ? off : off - 6, 8);
953 int n, i, emin[2] = { 0, }, sum = 0;
954 unsigned sig0 = 0, sig1 = 0;
955
956 if(seg->exp)
957 n = 17;
958 else if(seg->side)
959 n = 15;
960 else
961 n = 16;
962 emin[1] = -n;
963
964 dbprintf(2, "\n char[%c%d]: n=%d s=%d w=%d sig=",
965 (dir < 0) ? '>' : '<', off, n, s, seg->width);
966 if(s < 13 || !check_width(seg->width, s, n))
967 return(ZBAR_NONE);
968
969 for(i = 4; --i >= 0; ) {
970 int e = decode_e(pair_width(dcode, off), s, n);
971 if(e < 0)
972 return(ZBAR_NONE);
973 dbprintf(2, "%d", e);
974 sum = e - sum;
975 off += dir;
976 sig1 <<= 4;
977 if(emin[1] < -sum)
978 emin[1] = -sum;
979 sig1 += sum;
980 if(!i)
981 break;
982
983 e = decode_e(pair_width(dcode, off), s, n);
984 if(e < 0)
985 return(ZBAR_NONE);
986 dbprintf(2, "%d", e);
987 sum = e - sum;
988 off += dir;
989 sig0 <<= 4;
990 if(emin[0] > sum)
991 emin[0] = sum;
992 sig0 += sum;
993 }
994
995 int diff = emin[~n & 1];
996 diff = diff + (diff << 4);
997 diff = diff + (diff << 8);
998
999 sig0 -= diff;
1000 sig1 += diff;
1001
1002 dbprintf(2, " emin=%d,%d el=%04x/%04x", emin[0], emin[1], sig0, sig1);
1003
1004 unsigned sum0 = sig0 + (sig0 >> 8);
1005 unsigned sum1 = sig1 + (sig1 >> 8);
1006 sum0 += sum0 >> 4;
1007 sum1 += sum1 >> 4;
1008 sum0 &= 0xf;
1009 sum1 &= 0xf;
1010
1011 dbprintf(2, " sum=%d/%d", sum0, sum1);
1012
1013 if(sum0 + sum1 + 8 != n) {
1014 dbprintf(2, " [SUM]");
1015 return(ZBAR_NONE);
1016 }
1017
1018 if(((sum0 ^ (n >> 1)) | (sum1 ^ (n >> 1) ^ n)) & 1) {
1019 dbprintf(2, " [ODD]");
1020 return(ZBAR_NONE);
1021 }
1022
1023 i = ((n & 0x3) ^ 1) * 5 + (sum1 >> 1);
1024 zassert(i < sizeof(groups) / sizeof(*groups), -1,
1025 "n=%d sum=%d/%d sig=%04x/%04x g=%d",
1026 n, sum0, sum1, sig0, sig1, i);
1027 struct group_s *g = groups + i;
1028 dbprintf(2, "\n g=%d(%d,%d,%d/%d)",
1029 i, g->sum, g->wmax, g->todd, g->teven);
1030
1031 int vodd = calc_value4(sig0 + 0x1111, sum0 + 4, g->wmax, ~n & 1);
1032 dbprintf(2, " v=%d", vodd);
1033 if(vodd < 0 || vodd > g->todd)
1034 return(ZBAR_NONE);
1035
1036 int veven = calc_value4(sig1 + 0x1111, sum1 + 4, 9 - g->wmax, n & 1);
1037 dbprintf(2, "/%d", veven);
1038 if(veven < 0 || veven > g->teven)
1039 return(ZBAR_NONE);
1040
1041 int v = g->sum;
1042 if(n & 2)
1043 v += vodd + veven * g->todd;
1044 else
1045 v += veven + vodd * g->teven;
1046
1047 dbprintf(2, " f=%d(%x%x%x)", seg->finder, seg->exp, seg->color, seg->side);
1048
1049 unsigned chk = 0;
1050 if(seg->exp) {
1051 unsigned side = seg->color ^ seg->side ^ 1;
1052 if(v >= 4096)
1053 return(ZBAR_NONE);
1054 /* skip A1 left */
1055 chk = calc_check(sig0, sig1, side, 211);
1056 if(seg->finder || seg->color || seg->side) {
1057 i = (seg->finder << 1) - side + seg->color;
1058 zassert(i >= 0 && i < 12, ZBAR_NONE,
1059 "f=%d(%x%x%x) side=%d i=%d\n",
1060 seg->finder, seg->exp, seg->color, seg->side, side, i);
1061 chk = (chk * exp_checksums[i]) % 211;
1062 }
1063 else if(v >= 4009)
1064 return(ZBAR_NONE);
1065 else
1066 chk = 0;
1067 }
1068 else {
1069 chk = calc_check(sig0, sig1, seg->side, 79);
1070 if(seg->color)
1071 chk = (chk * 16) % 79;
1072 }
1073 dbprintf(2, " => %d val=%d", chk, v);
1074
1075 seg->check = chk;
1076 seg->data = v;
1077
1078 merge_segment(db, seg);
1079
1080 if(seg->exp)
1081 return(match_segment_exp(dcode, seg, dir));
1082 else if(dir > 0)
1083 return(match_segment(dcode, seg));
1084 return(ZBAR_PARTIAL);
1085 }
1086
1087 static inline int
alloc_segment(databar_decoder_t * db)1088 alloc_segment (databar_decoder_t *db)
1089 {
1090 unsigned maxage = 0, csegs = db->csegs;
1091 int i, old = -1;
1092 for(i = 0; i < csegs; i++) {
1093 databar_segment_t *seg = db->segs + i;
1094 unsigned age;
1095 if(seg->finder < 0) {
1096 dbprintf(2, " free@%d", i);
1097 return(i);
1098 }
1099 age = (db->epoch - seg->epoch) & 0xff;
1100 if(age >= 128 && seg->count < 2) {
1101 seg->finder = -1;
1102 dbprintf(2, " stale@%d (%d - %d = %d)",
1103 i, db->epoch, seg->epoch, age);
1104 return(i);
1105 }
1106
1107 /* score based on both age and count */
1108 if(age > seg->count)
1109 age = age - seg->count + 1;
1110 else
1111 age = 1;
1112
1113 if(maxage < age) {
1114 maxage = age;
1115 old = i;
1116 dbprintf(2, " old@%d(%u)", i, age);
1117 }
1118 }
1119
1120 if(csegs < DATABAR_MAX_SEGMENTS) {
1121 dbprintf(2, " new@%d", i);
1122 i = csegs;
1123 csegs *= 2;
1124 if(csegs > DATABAR_MAX_SEGMENTS)
1125 csegs = DATABAR_MAX_SEGMENTS;
1126 if(csegs != db->csegs) {
1127 databar_segment_t *seg;
1128 db->segs = realloc(db->segs, csegs * sizeof(*db->segs));
1129 db->csegs = csegs;
1130 seg = db->segs + csegs;
1131 while(--seg, --csegs >= i) {
1132 seg->finder = -1;
1133 seg->exp = 0;
1134 seg->color = 0;
1135 seg->side = 0;
1136 seg->partial = 0;
1137 seg->count = 0;
1138 seg->epoch = 0;
1139 seg->check = 0;
1140 }
1141 return(i);
1142 }
1143 }
1144 zassert(old >= 0, -1, "\n");
1145
1146 db->segs[old].finder = -1;
1147 return(old);
1148 }
1149
1150 static inline zbar_symbol_type_t
decode_finder(zbar_decoder_t * dcode)1151 decode_finder (zbar_decoder_t *dcode)
1152 {
1153 databar_decoder_t *db = &dcode->databar;
1154 databar_segment_t *seg;
1155 unsigned e0 = pair_width(dcode, 1);
1156 unsigned e2 = pair_width(dcode, 3);
1157 unsigned e1, e3, s, finder, dir;
1158 int sig, iseg;
1159 dbprintf(2, " databar: e0=%d e2=%d", e0, e2);
1160 if(e0 < e2) {
1161 unsigned e = e2 * 4;
1162 if(e < 15 * e0 || e > 34 * e0)
1163 return(ZBAR_NONE);
1164 dir = 0;
1165 e3 = pair_width(dcode, 4);
1166 }
1167 else {
1168 unsigned e = e0 * 4;
1169 if(e < 15 * e2 || e > 34 * e2)
1170 return(ZBAR_NONE);
1171 dir = 1;
1172 e2 = e0;
1173 e3 = pair_width(dcode, 0);
1174 }
1175 e1 = pair_width(dcode, 2);
1176
1177 s = e1 + e3;
1178 dbprintf(2, " e1=%d e3=%d dir=%d s=%d", e1, e3, dir, s);
1179 if(s < 12)
1180 return(ZBAR_NONE);
1181
1182 sig = ((decode_e(e3, s, 14) << 8) | (decode_e(e2, s, 14) << 4) |
1183 decode_e(e1, s, 14));
1184 dbprintf(2, " sig=%04x", sig & 0xfff);
1185 if(sig < 0 ||
1186 ((sig >> 4) & 0xf) < 8 ||
1187 ((sig >> 4) & 0xf) > 10 ||
1188 (sig & 0xf) >= 10 ||
1189 ((sig >> 8) & 0xf) >= 10 ||
1190 (((sig >> 8) + sig) & 0xf) != 10)
1191 return(ZBAR_NONE);
1192
1193 finder = (finder_hash[(sig - (sig >> 5)) & 0x1f] +
1194 finder_hash[(sig >> 1) & 0x1f]) & 0x1f;
1195 dbprintf(2, " finder=%d", finder);
1196 if(finder == 0x1f ||
1197 !TEST_CFG((finder < 9) ? db->config : db->config_exp, ZBAR_CFG_ENABLE))
1198 return(ZBAR_NONE);
1199
1200 zassert(finder >= 0, ZBAR_NONE, "dir=%d sig=%04x f=%d\n",
1201 dir, sig & 0xfff, finder);
1202
1203 iseg = alloc_segment(db);
1204 if(iseg < 0)
1205 return(ZBAR_NONE);
1206
1207 seg = db->segs + iseg;
1208 seg->finder = (finder >= 9) ? finder - 9 : finder;
1209 seg->exp = (finder >= 9);
1210 seg->color = get_color(dcode) ^ dir ^ 1;
1211 seg->side = dir;
1212 seg->partial = 0;
1213 seg->count = 1;
1214 seg->width = s;
1215 seg->epoch = db->epoch;
1216
1217 int rc = decode_char(dcode, seg, 12 - dir, -1);
1218 if(!rc)
1219 seg->partial = 1;
1220 else
1221 db->epoch++;
1222
1223 int i = (dcode->idx + 8 + dir) & 0xf;
1224 zassert(db->chars[i] == -1, ZBAR_NONE, "\n");
1225 db->chars[i] = iseg;
1226 return(rc);
1227 }
1228
1229 zbar_symbol_type_t
_zbar_decode_databar(zbar_decoder_t * dcode)1230 _zbar_decode_databar (zbar_decoder_t *dcode)
1231 {
1232 databar_decoder_t *db = &dcode->databar;
1233 databar_segment_t *seg, *pair;
1234 zbar_symbol_type_t sym;
1235 int iseg, i = dcode->idx & 0xf;
1236
1237 sym = decode_finder(dcode);
1238 dbprintf(2, "\n");
1239
1240 iseg = db->chars[i];
1241 if(iseg < 0)
1242 return(sym);
1243
1244 db->chars[i] = -1;
1245 seg = db->segs + iseg;
1246 dbprintf(2, " databar: i=%d part=%d f=%d(%x%x%x)",
1247 iseg, seg->partial, seg->finder, seg->exp, seg->color, seg->side);
1248 zassert(seg->finder >= 0, ZBAR_NONE, "i=%d f=%d(%x%x%x) part=%x\n",
1249 iseg, seg->finder, seg->exp, seg->color, seg->side, seg->partial);
1250
1251 if(seg->partial) {
1252 pair = NULL;
1253 seg->side = !seg->side;
1254 }
1255 else {
1256 int jseg = alloc_segment(db);
1257 pair = db->segs + iseg;
1258 seg = db->segs + jseg;
1259 seg->finder = pair->finder;
1260 seg->exp = pair->exp;
1261 seg->color = pair->color;
1262 seg->side = !pair->side;
1263 seg->partial = 0;
1264 seg->count = 1;
1265 seg->width = pair->width;
1266 seg->epoch = db->epoch;
1267 }
1268
1269 sym = decode_char(dcode, seg, 1, 1);
1270 if(!sym) {
1271 seg->finder = -1;
1272 if(pair)
1273 pair->partial = 1;
1274 }
1275 else
1276 db->epoch++;
1277 dbprintf(2, "\n");
1278
1279 return(sym);
1280 }
1281