code128.c

00001 /*------------------------------------------------------------------------
00002  *  Copyright 2007-2009 (c) Jeff Brown <spadix@users.sourceforge.net>
00003  *
00004  *  This file is part of the ZBar Bar Code Reader.
00005  *
00006  *  The ZBar Bar Code Reader is free software; you can redistribute it
00007  *  and/or modify it under the terms of the GNU Lesser Public License as
00008  *  published by the Free Software Foundation; either version 2.1 of
00009  *  the License, or (at your option) any later version.
00010  *
00011  *  The ZBar Bar Code Reader is distributed in the hope that it will be
00012  *  useful, but WITHOUT ANY WARRANTY; without even the implied warranty
00013  *  of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014  *  GNU Lesser Public License for more details.
00015  *
00016  *  You should have received a copy of the GNU Lesser Public License
00017  *  along with the ZBar Bar Code Reader; if not, write to the Free
00018  *  Software Foundation, Inc., 51 Franklin St, Fifth Floor,
00019  *  Boston, MA  02110-1301  USA
00020  *
00021  *  http://sourceforge.net/projects/zbar
00022  *------------------------------------------------------------------------*/
00023 
00024 #include "../config.h"
00025 #include <string.h>     /* memmove */
00026 
00027 #ifdef ENABLE_CODE128
00028 
00029 #include <zbar.h>
00030 #include "../decoder.h"
00031 
00032 #ifdef DEBUG_CODE128
00033 # define DEBUG_LEVEL (DEBUG_CODE128)
00034 #endif
00035 #include "../debug.h"
00036 
00037 #define NUM_CHARS 108           /* total number of character codes */
00038 
00039 typedef enum code128_char_e {
00040     FNC3        = 0x60,
00041     FNC2        = 0x61,
00042     SHIFT       = 0x62,
00043     CODE_C      = 0x63,
00044     CODE_B      = 0x64,
00045     CODE_A      = 0x65,
00046     FNC1        = 0x66,
00047     START_A     = 0x67,
00048     START_B     = 0x68,
00049     START_C     = 0x69,
00050     STOP_FWD    = 0x6a,
00051     STOP_REV    = 0x6b,
00052     FNC4        = 0x6c,
00053 } code128_char_t;
00054 
00055 static const unsigned char characters[NUM_CHARS] = {
00056     0x5c, 0xbf, 0xa1,                                           /* [00] 00 */
00057     0x2a, 0xc5, 0x0c, 0xa4,                                     /* [03] 01 */
00058     0x2d, 0xe3, 0x0f,                                           /* [07] 02 */
00059     0x5f, 0xe4,                                                 /* [0a] 03 */
00060 
00061     0x6b, 0xe8, 0x69, 0xa7, 0xe7,                               /* [0c] 10 */
00062     0xc1, 0x51, 0x1e, 0x83, 0xd9, 0x00, 0x84, 0x1f,             /* [11] 11 */
00063     0xc7, 0x0d, 0x33, 0x86, 0xb5, 0x0e, 0x15, 0x87,             /* [19] 12 */
00064     0x10, 0xda, 0x11,                                           /* [21] 13 */
00065 
00066     0x36, 0xe5, 0x18, 0x37,                                     /* [24] 20 */
00067     0xcc, 0x13, 0x39, 0x89, 0x97, 0x14, 0x1b, 0x8a, 0x3a, 0xbd, /* [28] 21 */
00068     0xa2, 0x5e, 0x01, 0x85, 0xb0, 0x02, 0xa3,                   /* [32] 22 */
00069     0xa5, 0x2c, 0x16, 0x88, 0xbc, 0x12, 0xa6,                   /* [39] 23 */
00070 
00071     0x61, 0xe6, 0x56, 0x62,                                     /* [40] 30 */
00072     0x19, 0xdb, 0x1a,                                           /* [44] 31 */
00073     0xa8, 0x32, 0x1c, 0x8b, 0xcd, 0x1d, 0xa9,                   /* [47] 32 */
00074     0xc3, 0x20, 0xc4,                                           /* [4e] 33 */
00075 
00076     0x50, 0x5d, 0xc0,       /* [51] 0014 0025 0034 */
00077     0x2b, 0xc6,             /* [54] 0134 0143 */
00078     0x2e,                   /* [56] 0243 */
00079     0x53, 0x60,             /* [57] 0341 0352 */
00080     0x31,                   /* [59] 1024 */
00081     0x52, 0xc2,             /* [5a] 1114 1134 */
00082     0x34, 0xc8,             /* [5c] 1242 1243 */
00083     0x55,                   /* [5e] 1441 */
00084 
00085     0x57, 0x3e, 0xce,       /* [5f] 4100 5200 4300 */
00086     0x3b, 0xc9,             /* [62] 4310 3410 */
00087     0x6a,                   /* [64] 3420 */
00088     0x54, 0x4f,             /* [65] 1430 2530 */
00089     0x38,                   /* [67] 4201 */
00090     0x58, 0xcb,             /* [68] 4111 4311 */
00091     0x2f, 0xca,             /* [6a] 2421 3421 */
00092 };
00093 
00094 static const unsigned char lo_base[8] = {
00095     0x00, 0x07, 0x0c, 0x19, 0x24, 0x32, 0x40, 0x47
00096 };
00097 
00098 static const unsigned char lo_offset[0x80] = {
00099     0xff, 0xf0, 0xff, 0x1f, 0xff, 0xf2, 0xff, 0xff,     /* 00 [00] */
00100     0xff, 0xff, 0xff, 0x3f, 0xf4, 0xf5, 0xff, 0x6f,     /* 01 */
00101     0xff, 0xff, 0xff, 0xff, 0xf0, 0xf1, 0xff, 0x2f,     /* 02 [07] */
00102     0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f, 0x4f,     /* 03 */
00103     0xff, 0x0f, 0xf1, 0xf2, 0xff, 0x3f, 0xff, 0xf4,     /* 10 [0c] */
00104     0xf5, 0xf6, 0xf7, 0x89, 0xff, 0xab, 0xff, 0xfc,     /* 11 */
00105     0xff, 0xff, 0x0f, 0x1f, 0x23, 0x45, 0xf6, 0x7f,     /* 12 [19] */
00106     0xff, 0xff, 0xff, 0xff, 0xf8, 0xff, 0xf9, 0xaf,     /* 13 */
00107 
00108     0xf0, 0xf1, 0xff, 0x2f, 0xff, 0xf3, 0xff, 0xff,     /* 20 [24] */
00109     0x4f, 0x5f, 0x67, 0x89, 0xfa, 0xbf, 0xff, 0xcd,     /* 21 */
00110     0xf0, 0xf1, 0xf2, 0x3f, 0xf4, 0x56, 0xff, 0xff,     /* 22 [32] */
00111     0xff, 0xff, 0x7f, 0x8f, 0x9a, 0xff, 0xbc, 0xdf,     /* 23 */
00112     0x0f, 0x1f, 0xf2, 0xff, 0xff, 0x3f, 0xff, 0xff,     /* 30 [40] */
00113     0xf4, 0xff, 0xf5, 0x6f, 0xff, 0xff, 0xff, 0xff,     /* 31 */
00114     0x0f, 0x1f, 0x23, 0xff, 0x45, 0x6f, 0xff, 0xff,     /* 32 [47] */
00115     0xf7, 0xff, 0xf8, 0x9f, 0xff, 0xff, 0xff, 0xff,     /* 33 */
00116 };
00117 
00118 static inline signed char decode_lo (int sig)
00119 {
00120     unsigned char offset = (((sig >> 1) & 0x01) |
00121                             ((sig >> 3) & 0x06) |
00122                             ((sig >> 5) & 0x18) |
00123                             ((sig >> 7) & 0x60));
00124     unsigned char idx = lo_offset[offset];
00125     if(sig & 1)
00126         idx &= 0xf;
00127     else
00128         idx >>= 4;
00129     if(idx == 0xf)
00130         return(-1);
00131 
00132     unsigned char base = (sig >> 11) | ((sig >> 9) & 1);
00133     zassert(base < 8, -1, "sig=%x offset=%x idx=%x base=%x\n",
00134             sig, offset, idx, base);
00135     idx += lo_base[base];
00136 
00137     zassert(idx <= 0x50, -1, "sig=%x offset=%x base=%x idx=%x\n",
00138             sig, offset, base, idx);
00139     unsigned char c = characters[idx];
00140     dprintf(2, " %02x(%x(%02x)/%x(%02x)) => %02x",
00141             idx, base, lo_base[base], offset, lo_offset[offset],
00142             (unsigned char)c);
00143     return(c);
00144 }
00145 
00146 static inline signed char decode_hi (int sig)
00147 {
00148     unsigned char rev = (sig & 0x4400) != 0;
00149     if(rev)
00150         sig = (((sig >> 12) & 0x000f) |
00151                ((sig >>  4) & 0x00f0) |
00152                ((sig <<  4) & 0x0f00) |
00153                ((sig << 12) & 0xf000));
00154     dprintf(2, " rev=%x", rev != 0);
00155 
00156     unsigned char idx;
00157     switch(sig) {
00158     case 0x0014: idx = 0x0; break;
00159     case 0x0025: idx = 0x1; break;
00160     case 0x0034: idx = 0x2; break;
00161     case 0x0134: idx = 0x3; break;
00162     case 0x0143: idx = 0x4; break;
00163     case 0x0243: idx = 0x5; break;
00164     case 0x0341: idx = 0x6; break;
00165     case 0x0352: idx = 0x7; break;
00166     case 0x1024: idx = 0x8; break;
00167     case 0x1114: idx = 0x9; break;
00168     case 0x1134: idx = 0xa; break;
00169     case 0x1242: idx = 0xb; break;
00170     case 0x1243: idx = 0xc; break;
00171     case 0x1441: idx = 0xd; rev = 0; break;
00172     default: return(-1);
00173     }
00174     if(rev)
00175         idx += 0xe;
00176     unsigned char c = characters[0x51 + idx];
00177     dprintf(2, " %02x => %02x", idx, c);
00178     return(c);
00179 }
00180 
00181 static inline unsigned char calc_check (unsigned char c)
00182 {
00183     if(!(c & 0x80))
00184         return(0x18);
00185     c &= 0x7f;
00186     if(c < 0x3d)
00187         return((c < 0x30 && c != 0x17) ? 0x10 : 0x20);
00188     if(c < 0x50)
00189         return((c == 0x4d) ? 0x20 : 0x10);
00190     return((c < 0x67) ? 0x20 : 0x10);
00191 }
00192 
00193 static inline signed char decode6 (zbar_decoder_t *dcode)
00194 {
00195     /* build edge signature of character */
00196     unsigned s = dcode->code128.s6;
00197     dprintf(2, " s=%d", s);
00198     if(s < 5)
00199         return(-1);
00200     /* calculate similar edge measurements */
00201     int sig = (get_color(dcode) == ZBAR_BAR)
00202         ? ((decode_e(get_width(dcode, 0) + get_width(dcode, 1), s, 11) << 12) |
00203            (decode_e(get_width(dcode, 1) + get_width(dcode, 2), s, 11) << 8) |
00204            (decode_e(get_width(dcode, 2) + get_width(dcode, 3), s, 11) << 4) |
00205            (decode_e(get_width(dcode, 3) + get_width(dcode, 4), s, 11)))
00206         : ((decode_e(get_width(dcode, 5) + get_width(dcode, 4), s, 11) << 12) |
00207            (decode_e(get_width(dcode, 4) + get_width(dcode, 3), s, 11) << 8) |
00208            (decode_e(get_width(dcode, 3) + get_width(dcode, 2), s, 11) << 4) |
00209            (decode_e(get_width(dcode, 2) + get_width(dcode, 1), s, 11)));
00210     if(sig < 0)
00211         return(-1);
00212     dprintf(2, " sig=%04x", sig);
00213     /* lookup edge signature */
00214     signed char c = (sig & 0x4444) ? decode_hi(sig) : decode_lo(sig);
00215     if(c == -1)
00216         return(-1);
00217 
00218     /* character validation */
00219     unsigned bars = (get_color(dcode) == ZBAR_BAR)
00220         ? (get_width(dcode, 0) + get_width(dcode, 2) + get_width(dcode, 4))
00221         : (get_width(dcode, 1) + get_width(dcode, 3) + get_width(dcode, 5));
00222     bars = bars * 11 * 4 / s;
00223     unsigned char chk = calc_check(c);
00224     dprintf(2, " bars=%d chk=%d", bars, chk);
00225     if(chk - 7 > bars || bars > chk + 7)
00226         return(-1);
00227 
00228     return(c & 0x7f);
00229 }
00230 
00231 static inline unsigned char validate_checksum (zbar_decoder_t *dcode)
00232 {
00233     code128_decoder_t *dcode128 = &dcode->code128;
00234     if(dcode128->character < 3)
00235         return(1);
00236 
00237     /* add in irregularly weighted start character */
00238     unsigned idx = (dcode128->direction) ? dcode128->character - 1 : 0;
00239     unsigned sum = dcode->buf[idx];
00240     if(sum >= 103)
00241         sum -= 103;
00242 
00243     /* calculate sum in reverse to avoid multiply operations */
00244     unsigned i, acc = 0;
00245     for(i = dcode128->character - 3; i; i--) {
00246         zassert(sum < 103, -1, "dir=%x i=%x sum=%x acc=%x %s\n",
00247                 dcode128->direction, i, sum, acc,
00248                 _zbar_decoder_buf_dump(dcode->buf, dcode128->character));
00249         idx = (dcode128->direction) ? dcode128->character - 1 - i : i;
00250         acc += dcode->buf[idx];
00251         if(acc >= 103)
00252             acc -= 103;
00253         zassert(acc < 103, -1, "dir=%x i=%x sum=%x acc=%x %s\n",
00254                 dcode128->direction, i, sum, acc,
00255                 _zbar_decoder_buf_dump(dcode->buf, dcode128->character));
00256         sum += acc;
00257         if(sum >= 103)
00258             sum -= 103;
00259     }
00260 
00261     /* and compare to check character */
00262     idx = (dcode128->direction) ? 1 : dcode128->character - 2;
00263     unsigned char check = dcode->buf[idx];
00264     dprintf(2, " chk=%02x(%02x)", sum, check);
00265     unsigned char err = (sum != check);
00266     if(err)
00267         dprintf(1, " [checksum error]\n");
00268     return(err);
00269 }
00270 
00271 /* expand and decode character set C */
00272 static inline unsigned postprocess_c (zbar_decoder_t *dcode,
00273                                       unsigned start,
00274                                       unsigned end,
00275                                       unsigned dst)
00276 {
00277     /* expand buffer to accomodate 2x set C characters (2 digits per-char) */
00278     unsigned delta = end - start;
00279     unsigned newlen = dcode->code128.character + delta;
00280     size_buf(dcode, newlen);
00281 
00282     /* relocate unprocessed data to end of buffer */
00283     memmove(dcode->buf + start + delta, dcode->buf + start,
00284             dcode->code128.character - start);
00285     dcode->code128.character = newlen;
00286 
00287     unsigned i, j;
00288     for(i = 0, j = dst; i < delta; i++, j += 2) {
00289         /* convert each set C character into two ASCII digits */
00290         unsigned char code = dcode->buf[start + delta + i];
00291         dcode->buf[j] = '0';
00292         if(code >= 50) {
00293             code -= 50;
00294             dcode->buf[j] += 5;
00295         }
00296         if(code >= 30) {
00297             code -= 30;
00298             dcode->buf[j] += 3;
00299         }
00300         if(code >= 20) {
00301             code -= 20;
00302             dcode->buf[j] += 2;
00303         }
00304         if(code >= 10) {
00305             code -= 10;
00306             dcode->buf[j] += 1;
00307         }
00308         zassert(dcode->buf[j] <= '9', delta,
00309                 "start=%x end=%x i=%x j=%x %s\n", start, end, i, j,
00310                 _zbar_decoder_buf_dump(dcode->buf, dcode->code128.character));
00311         zassert(code <= 9, delta,
00312                 "start=%x end=%x i=%x j=%x %s\n", start, end, i, j,
00313                 _zbar_decoder_buf_dump(dcode->buf, dcode->code128.character));
00314         dcode->buf[j + 1] = '0' + code;
00315     }
00316     return(delta);
00317 }
00318 
00319 /* resolve scan direction and convert to ASCII */
00320 static inline unsigned char postprocess (zbar_decoder_t *dcode)
00321 {
00322     code128_decoder_t *dcode128 = &dcode->code128;
00323     dprintf(2, "\n    postproc len=%d", dcode128->character);
00324     unsigned i, j;
00325     unsigned char code = 0;
00326     if(dcode128->direction) {
00327         /* reverse buffer */
00328         dprintf(2, " (rev)");
00329         for(i = 0; i < dcode128->character / 2; i++) {
00330             unsigned j = dcode128->character - 1 - i;
00331             code = dcode->buf[i];
00332             dcode->buf[i] = dcode->buf[j];
00333             dcode->buf[j] = code;
00334         }
00335         zassert(dcode->buf[dcode128->character - 1] == STOP_REV, 1,
00336                 "dir=%x %s\n", dcode128->direction,
00337                 _zbar_decoder_buf_dump(dcode->buf, dcode->code128.character));
00338     }
00339     else
00340         zassert(dcode->buf[dcode128->character - 1] == STOP_FWD, 1,
00341                 "dir=%x %s\n", dcode128->direction,
00342                 _zbar_decoder_buf_dump(dcode->buf, dcode->code128.character));
00343 
00344     code = dcode->buf[0];
00345     zassert(code >= START_A && code <= START_C, 1, "%s\n",
00346             _zbar_decoder_buf_dump(dcode->buf, dcode->code128.character));
00347 
00348     unsigned char charset = code - START_A;
00349     unsigned cexp = (code == START_C) ? 1 : 0;
00350     dprintf(2, " start=%c", 'A' + charset);
00351 
00352     for(i = 1, j = 0; i < dcode128->character - 2; i++) {
00353         unsigned char code = dcode->buf[i];
00354         zassert(!(code & 0x80), 1,
00355                 "i=%x j=%x code=%02x charset=%x cexp=%x %s\n",
00356                 i, j, code, charset, cexp,
00357                 _zbar_decoder_buf_dump(dcode->buf, dcode->code128.character));
00358 
00359         if((charset & 0x2) && (code < 100))
00360             /* defer character set C for expansion */
00361             continue;
00362         else if(code < 0x60) {
00363             /* convert character set B to ASCII */
00364             code = code + 0x20;
00365             if((!charset || (charset == 0x81)) && (code >= 0x60))
00366                 /* convert character set A to ASCII */
00367                 code -= 0x60;
00368             dcode->buf[j++] = code;
00369             if(charset & 0x80)
00370                 charset &= 0x7f;
00371         }
00372         else {
00373             dprintf(2, " %02x", code);
00374             if(charset & 0x2) {
00375                 /* expand character set C to ASCII */
00376                 zassert(cexp, 1, "i=%x j=%x code=%02x charset=%x cexp=%x %s\n",
00377                         i, j, code, charset, cexp,
00378                         _zbar_decoder_buf_dump(dcode->buf,
00379                                                 dcode->code128.character));
00380                 unsigned delta = postprocess_c(dcode, cexp, i, j);
00381                 i += delta;
00382                 j += delta * 2;
00383                 cexp = 0;
00384             }
00385             if(code < CODE_C) {
00386                 if(code == SHIFT)
00387                     charset |= 0x80;
00388                 else if(code == FNC2)
00389                     /* FIXME FNC2 - message append */;
00390                 else if(code == FNC3)
00391                     /* FIXME FNC3 - initialize */;
00392             }
00393             else if(code == FNC1)
00394                 /* FIXME FNC1 - Code 128 subsets or ASCII 0x1d */;
00395             else if(code >= START_A) {
00396                 dprintf(1, " [truncated]\n");
00397                 return(1);
00398             }
00399             else {
00400                 zassert(code >= CODE_C && code <= CODE_A, 1,
00401                         "i=%x j=%x code=%02x charset=%x cexp=%x %s\n",
00402                         i, j, code, charset, cexp,
00403                         _zbar_decoder_buf_dump(dcode->buf,
00404                                                 dcode->code128.character));
00405                 unsigned char newset = CODE_A - code;
00406                 if(newset != charset)
00407                     charset = newset;
00408                 else
00409                     /* FIXME FNC4 - extended ASCII */;
00410             }
00411             if(charset & 0x2)
00412                 cexp = i + 1;
00413         }
00414     }
00415     if(charset & 0x2) {
00416         zassert(cexp, 1, "i=%x j=%x code=%02x charset=%x cexp=%x %s\n",
00417                 i, j, code, charset, cexp,
00418                 _zbar_decoder_buf_dump(dcode->buf,
00419                                         dcode->code128.character));
00420         j += postprocess_c(dcode, cexp, i, j) * 2;
00421     }
00422     dcode->buflen = j;
00423     dcode->buf[j] = '\0';
00424     dcode->code128.character = j;
00425     return(0);
00426 }
00427 
00428 zbar_symbol_type_t _zbar_decode_code128 (zbar_decoder_t *dcode)
00429 {
00430     code128_decoder_t *dcode128 = &dcode->code128;
00431 
00432     /* update latest character width */
00433     dcode128->s6 -= get_width(dcode, 6);
00434     dcode128->s6 += get_width(dcode, 0);
00435 
00436     if(/* process every 6th element of active symbol */
00437        (dcode128->character >= 0 &&
00438         (++dcode128->element) != 6) ||
00439        /* decode color based on direction */
00440        (get_color(dcode) != dcode128->direction))
00441         return(0);
00442     dcode128->element = 0;
00443 
00444     dprintf(2, "      code128[%c%02d+%x]:",
00445             (dcode128->direction) ? '<' : '>',
00446             dcode128->character, dcode128->element);
00447 
00448     signed char c = decode6(dcode);
00449     if(dcode128->character < 0) {
00450         dprintf(2, " c=%02x", c);
00451         if(c < START_A || c > STOP_REV || c == STOP_FWD) {
00452             dprintf(2, " [invalid]\n");
00453             return(0);
00454         }
00455         unsigned qz = get_width(dcode, 6);
00456         if(qz && qz < (dcode->code128.s6 * 3) / 4) {
00457             dprintf(2, " [invalid qz %d]\n", qz);
00458             return(0);
00459         }
00460         /* lock shared resources */
00461         if(get_lock(dcode, ZBAR_CODE128)) {
00462             dprintf(2, " [locked %d]\n", dcode->lock);
00463             dcode128->character = -1;
00464             return(0);
00465         }
00466         /* decoded valid start/stop */
00467         /* initialize state */
00468         dcode128->character = 0;
00469         if(c == STOP_REV) {
00470             dcode128->direction = ZBAR_BAR;
00471             dcode128->element = 7;
00472         }
00473         else
00474             dcode128->direction = ZBAR_SPACE;
00475         dprintf(2, " dir=%x [valid start]", dcode128->direction);
00476     }
00477     else if((c < 0) ||
00478             ((dcode128->character >= BUFFER_MIN) &&
00479              size_buf(dcode, dcode128->character + 1))) {
00480         dprintf(1, (c < 0) ? " [aborted]\n" : " [overflow]\n");
00481         dcode->lock = 0;
00482         dcode128->character = -1;
00483         return(0);
00484     }
00485 
00486     zassert(dcode->buf_alloc > dcode128->character, 0,
00487             "alloc=%x idx=%x c=%02x %s\n",
00488             dcode->buf_alloc, dcode128->character, c,
00489             _zbar_decoder_buf_dump(dcode->buf, dcode->buf_alloc));
00490 
00491     dcode->buf[dcode128->character++] = c;
00492 
00493     if(dcode128->character > 2 &&
00494        ((dcode128->direction)
00495         ? c >= START_A && c <= START_C
00496         : c == STOP_FWD)) {
00497         /* FIXME STOP_FWD should check extra bar (and QZ!) */
00498         zbar_symbol_type_t sym = ZBAR_CODE128;
00499         if(validate_checksum(dcode) || postprocess(dcode))
00500             sym = ZBAR_NONE;
00501         else if(dcode128->character < CFG(*dcode128, ZBAR_CFG_MIN_LEN) ||
00502                 (CFG(*dcode128, ZBAR_CFG_MAX_LEN) > 0 &&
00503                  dcode128->character > CFG(*dcode128, ZBAR_CFG_MAX_LEN))) {
00504             dprintf(2, " [invalid len]\n");
00505             sym = ZBAR_NONE;
00506         }
00507         else
00508             dprintf(2, " [valid end]\n");
00509         dcode128->character = -1;
00510         if(!sym)
00511             dcode->lock = 0;
00512         return(sym);
00513     }
00514 
00515     dprintf(2, "\n");
00516     return(0);
00517 }
00518  #endif