cpp/core/src/zxing/oned/UPCEANReader.cpp

   1 /*
   2  *  UPCEANReader.cpp
   3  *  ZXing
   4  *
   5  *  Copyright 2010 ZXing authors All rights reserved.
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  *      http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 #include "UPCEANReader.h"
  21 #include <zxing/oned/OneDResultPoint.h>
  22 #include <zxing/ReaderException.h>
  23
  24 namespace zxing {
  25   namespace oned {
  26
  27     /**
  28      * Start/end guard pattern.
  29      */
  30     static const int START_END_PATTERN[3] = {1, 1, 1};
  31
  32     /**
  33      * Pattern marking the middle of a UPC/EAN pattern, separating the two halves.
  34      */
  35     static const int MIDDLE_PATTERN_LEN = 5;
  36     static const int MIDDLE_PATTERN[MIDDLE_PATTERN_LEN] = {1, 1, 1, 1, 1};
  37
  38     /**
  39      * "Odd", or "L" patterns used to encode UPC/EAN digits.
  40      */
  41     const int L_PATTERNS_LEN = 10;
  42     const int L_PATTERNS_SUB_LEN = 4;
  43     const int L_PATTERNS[L_PATTERNS_LEN][L_PATTERNS_SUB_LEN] = {
  44       {3, 2, 1, 1}, // 0
  45       {2, 2, 2, 1}, // 1
  46       {2, 1, 2, 2}, // 2
  47       {1, 4, 1, 1}, // 3
  48       {1, 1, 3, 2}, // 4
  49       {1, 2, 3, 1}, // 5
  50       {1, 1, 1, 4}, // 6
  51       {1, 3, 1, 2}, // 7
  52       {1, 2, 1, 3}, // 8
  53       {3, 1, 1, 2}  // 9
  54     };
  55
  56     /**
  57      * As above but also including the "even", or "G" patterns used to encode UPC/EAN digits.
  58      */
  59     const int L_AND_G_PATTERNS_LEN = 20;
  60     const int L_AND_G_PATTERNS_SUB_LEN = 4;
  61     const int L_AND_G_PATTERNS[L_AND_G_PATTERNS_LEN][L_AND_G_PATTERNS_SUB_LEN] = {
  62       {3, 2, 1, 1}, // 0
  63       {2, 2, 2, 1}, // 1
  64       {2, 1, 2, 2}, // 2
  65       {1, 4, 1, 1}, // 3
  66       {1, 1, 3, 2}, // 4
  67       {1, 2, 3, 1}, // 5
  68       {1, 1, 1, 4}, // 6
  69       {1, 3, 1, 2}, // 7
  70       {1, 2, 1, 3}, // 8
  71       {3, 1, 1, 2}, // 9
  72       {1, 1, 2, 3}, // 10 reversed 0
  73       {1, 2, 2, 2}, // 11 reversed 1
  74       {2, 2, 1, 2}, // 12 reversed 2
  75       {1, 1, 4, 1}, // 13 reversed 3
  76       {2, 3, 1, 1}, // 14 reversed 4
  77       {1, 3, 2, 1}, // 15 reversed 5
  78       {4, 1, 1, 1}, // 16 reversed 6
  79       {2, 1, 3, 1}, // 17 reversed 7
  80       {3, 1, 2, 1}, // 18 reversed 8
  81       {2, 1, 1, 3}  // 19 reversed 9
  82     };
  83
  84
  85     const int UPCEANReader::getMIDDLE_PATTERN_LEN() {
  86       return MIDDLE_PATTERN_LEN;
  87     }
  88
  89     const int* UPCEANReader::getMIDDLE_PATTERN() {
  90       return MIDDLE_PATTERN;
  91     }
  92
  93     UPCEANReader::UPCEANReader() {
  94     }
  95
  96
  97     Ref<Result> UPCEANReader::decodeRow(int rowNumber, Ref<BitArray> row) {
  98       int rangeStart;
  99       int rangeEnd;
 100                         if (findStartGuardPattern(row, &rangeStart, &rangeEnd)) {
 101         try {
 102           return decodeRow(rowNumber, row, rangeStart, rangeEnd);
 103         } catch (ReaderException const& re) {
 104         }
 105                         }
 106                         return Ref<Result>();
 107     }
 108
 109     Ref<Result> UPCEANReader::decodeRow(int rowNumber, Ref<BitArray> row, int startGuardBegin,
 110         int startGuardEnd) {
 111       std::string tmpResultString;
 112       std::string& tmpResultStringRef = tmpResultString;
 113       int endStart = decodeMiddle(row, startGuardBegin, startGuardEnd, tmpResultStringRef);
 114       if (endStart < 0) {
 115         return Ref<Result>();
 116       }
 117
 118       int endGuardBegin;
 119       int endGuardEnd;
 120       if (!decodeEnd(row, endStart, &endGuardBegin, &endGuardEnd)) {
 121         return Ref<Result>();
 122       }
 123
 124       // Make sure there is a quiet zone at least as big as the end pattern after the barcode.
 125       // The spec might want more whitespace, but in practice this is the maximum we can count on.
 126       size_t quietEnd = endGuardEnd + (endGuardEnd - endGuardBegin);
 127       if (quietEnd >= row->getSize() || !row->isRange(endGuardEnd, quietEnd, false)) {
 128         return Ref<Result>();
 129       }
 130
 131       if (!checkChecksum(tmpResultString)) {
 132         return Ref<Result>();
 133       }
 134
 135       Ref<String> resultString(new String(tmpResultString));
 136       float left = (float) (startGuardBegin + startGuardEnd) / 2.0f;
 137       float right = (float) (endGuardBegin + endGuardEnd) / 2.0f;
 138
 139       std::vector< Ref<ResultPoint> > resultPoints(2);
 140       Ref<OneDResultPoint> resultPoint1(new OneDResultPoint(left, (float) rowNumber));
 141       Ref<OneDResultPoint> resultPoint2(new OneDResultPoint(right, (float) rowNumber));
 142       resultPoints[0] = resultPoint1;
 143       resultPoints[1] = resultPoint2;
 144
 145       ArrayRef<unsigned char> resultBytes(1);
 146       return Ref<Result>(new Result(resultString, resultBytes, resultPoints, getBarcodeFormat()));
 147     }
 148
 149     bool UPCEANReader::findStartGuardPattern(Ref<BitArray> row, int* rangeStart, int* rangeEnd) {
 150       int nextStart = 0;
 151       while (findGuardPattern(row, nextStart, false, START_END_PATTERN,
 152           sizeof(START_END_PATTERN) / sizeof(int), rangeStart, rangeEnd)) {
 153         int start = *rangeStart;
 154         nextStart = *rangeEnd;
 155         // Make sure there is a quiet zone at least as big as the start pattern before the barcode.
 156         // If this check would run off the left edge of the image, do not accept this barcode,
 157         // as it is very likely to be a false positive.
 158         int quietStart = start - (nextStart - start);
 159         if (quietStart >= 0 && row->isRange(quietStart, start, false)) {
 160           return true;
 161         }
 162       }
 163       return false;
 164     }
 165
 166     bool UPCEANReader::findGuardPattern(Ref<BitArray> row, int rowOffset, bool whiteFirst,
 167         const int pattern[], int patternLen, int* start, int* end) {
 168       int patternLength = patternLen;
 169       int counters[patternLength];
 170       int countersCount = sizeof(counters) / sizeof(int);
 171       for (int i = 0; i < countersCount; i++) {
 172         counters[i] = 0;
 173       }
 174       int width = row->getSize();
 175       bool isWhite = false;
 176       while (rowOffset < width) {
 177         isWhite = !row->get(rowOffset);
 178         if (whiteFirst == isWhite) {
 179           break;
 180         }
 181         rowOffset++;
 182       }
 183
 184       int counterPosition = 0;
 185       int patternStart = rowOffset;
 186       for (int x = rowOffset; x < width; x++) {
 187         bool pixel = row->get(x);
 188         if (pixel ^ isWhite) {
 189           counters[counterPosition]++;
 190         } else {
 191           if (counterPosition == patternLength - 1) {
 192             if (patternMatchVariance(counters, countersCount, pattern,
 193                 MAX_INDIVIDUAL_VARIANCE) < MAX_AVG_VARIANCE) {
 194               *start = patternStart;
 195               *end = x;
 196               return true;
 197             }
 198             patternStart += counters[0] + counters[1];
 199             for (int y = 2; y < patternLength; y++) {
 200               counters[y - 2] = counters[y];
 201             }
 202             counters[patternLength - 2] = 0;
 203             counters[patternLength - 1] = 0;
 204             counterPosition--;
 205           } else {
 206             counterPosition++;
 207           }
 208           counters[counterPosition] = 1;
 209           isWhite = !isWhite;
 210         }
 211       }
 212       return false;
 213     }
 214
 215     bool UPCEANReader::decodeEnd(Ref<BitArray> row, int endStart, int* endGuardBegin,
 216         int* endGuardEnd) {
 217       return findGuardPattern(row, endStart, false, START_END_PATTERN,
 218           sizeof(START_END_PATTERN) / sizeof(int), endGuardBegin, endGuardEnd);
 219     }
 220
 221     int UPCEANReader::decodeDigit(Ref<BitArray> row, int counters[], int countersLen, int rowOffset,
 222         UPC_EAN_PATTERNS patternType) {
 223       if (!recordPattern(row, rowOffset, counters, countersLen)) {
 224         return -1;
 225       }
 226       unsigned int bestVariance = MAX_AVG_VARIANCE; // worst variance we'll accept
 227       int bestMatch = -1;
 228
 229       int max = 0;
 230       switch (patternType) {
 231         case UPC_EAN_PATTERNS_L_PATTERNS:
 232           max = L_PATTERNS_LEN;
 233           for (int i = 0; i < max; i++) {
 234             int pattern[countersLen];
 235             for(int j = 0; j< countersLen; j++){
 236               pattern[j] = L_PATTERNS[i][j];
 237             }
 238
 239             unsigned int variance = patternMatchVariance(counters, countersLen, pattern,
 240                 MAX_INDIVIDUAL_VARIANCE);
 241             if (variance < bestVariance) {
 242               bestVariance = variance;
 243               bestMatch = i;
 244             }
 245           }
 246           break;
 247         case UPC_EAN_PATTERNS_L_AND_G_PATTERNS:
 248           max = L_AND_G_PATTERNS_LEN;
 249           for (int i = 0; i < max; i++) {
 250             int pattern[countersLen];
 251             for(int j = 0; j< countersLen; j++){
 252               pattern[j] = L_AND_G_PATTERNS[i][j];
 253             }
 254
 255             unsigned int variance = patternMatchVariance(counters, countersLen, pattern,
 256                 MAX_INDIVIDUAL_VARIANCE);
 257             if (variance < bestVariance) {
 258               bestVariance = variance;
 259               bestMatch = i;
 260             }
 261           }
 262           break;
 263         default:
 264           break;
 265       }
 266       return bestMatch;
 267     }
 268
 269     /**
 270      * @return {@link #checkStandardUPCEANChecksum(String)}
 271      */
 272     bool UPCEANReader::checkChecksum(std::string s) {
 273       return checkStandardUPCEANChecksum(s);
 274     }
 275
 276     /**
 277      * Computes the UPC/EAN checksum on a string of digits, and reports
 278      * whether the checksum is correct or not.
 279      *
 280      * @param s string of digits to check
 281      * @return true iff string of digits passes the UPC/EAN checksum algorithm
 282      */
 283     bool UPCEANReader::checkStandardUPCEANChecksum(std::string s) {
 284       int length = s.length();
 285       if (length == 0) {
 286         return false;
 287       }
 288
 289       int sum = 0;
 290       for (int i = length - 2; i >= 0; i -= 2) {
 291         int digit = (int) s[i] - (int) '0';
 292         if (digit < 0 || digit > 9) {
 293           return false;
 294         }
 295         sum += digit;
 296       }
 297       sum *= 3;
 298       for (int i = length - 1; i >= 0; i -= 2) {
 299         int digit = (int) s[i] - (int) '0';
 300         if (digit < 0 || digit > 9) {
 301           return false;
 302         }
 303         sum += digit;
 304       }
 305       return sum % 10 == 0;
 306     }
 307
 308     UPCEANReader::~UPCEANReader() {
 309     }
 310   }
 311 }