core/src/com/google/zxing/oned/rss/RSS14Reader.java

   1 /*
   2  * Copyright 2009 ZXing authors
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 package com.google.zxing.oned.rss;
  18
  19 import com.google.zxing.BarcodeFormat;
  20 import com.google.zxing.DecodeHintType;
  21 import com.google.zxing.NotFoundException;
  22 import com.google.zxing.Result;
  23 import com.google.zxing.ResultPoint;
  24 import com.google.zxing.ResultPointCallback;
  25 import com.google.zxing.common.BitArray;
  26
  27 import java.util.Enumeration;
  28 import java.util.Hashtable;
  29 import java.util.Vector;
  30
  31 /**
  32  * Decodes RSS-14, including truncated and stacked variants. See ISO/IEC 24724:2006.
  33  */
  34 public final class RSS14Reader extends AbstractRSSReader {
  35
  36   private static final int[] OUTSIDE_EVEN_TOTAL_SUBSET = {1,10,34,70,126};
  37   private static final int[] INSIDE_ODD_TOTAL_SUBSET = {4,20,48,81};
  38   private static final int[] OUTSIDE_GSUM = {0,161,961,2015,2715};
  39   private static final int[] INSIDE_GSUM = {0,336,1036,1516};
  40   private static final int[] OUTSIDE_ODD_WIDEST = {8,6,4,3,1};
  41   private static final int[] INSIDE_ODD_WIDEST = {2,4,6,8};
  42
  43   private static final int[][] FINDER_PATTERNS = {
  44       {3,8,2,1},
  45       {3,5,5,1},
  46       {3,3,7,1},
  47       {3,1,9,1},
  48       {2,7,4,1},
  49       {2,5,6,1},
  50       {2,3,8,1},
  51       {1,5,7,1},
  52       {1,3,9,1},
  53   };
  54
  55   private final Vector possibleLeftPairs;
  56   private final Vector possibleRightPairs;
  57
  58   public RSS14Reader() {
  59     possibleLeftPairs = new Vector();
  60     possibleRightPairs = new Vector();
  61   }
  62
  63   public Result decodeRow(int rowNumber, BitArray row, Hashtable hints) throws NotFoundException {
  64     Pair leftPair = decodePair(row, false, rowNumber, hints);
  65     addOrTally(possibleLeftPairs, leftPair);
  66     row.reverse();
  67     Pair rightPair = decodePair(row, true, rowNumber, hints);
  68     addOrTally(possibleRightPairs, rightPair);
  69     row.reverse();
  70     int numLeftPairs = possibleLeftPairs.size();
  71     int numRightPairs = possibleRightPairs.size();
  72     for (int l = 0; l < numLeftPairs; l++) {
  73       Pair left = (Pair) possibleLeftPairs.elementAt(l);
  74       if (left.getCount() > 1) {
  75         for (int r = 0; r < numRightPairs; r++) {
  76           Pair right = (Pair) possibleRightPairs.elementAt(r);
  77           if (right.getCount() > 1) {
  78             if (checkChecksum(left, right)) {
  79               return constructResult(left, right);
  80             }
  81           }
  82         }
  83       }
  84     }
  85     throw NotFoundException.getNotFoundInstance();
  86   }
  87
  88   private static void addOrTally(Vector possiblePairs, Pair pair) {
  89     if (pair == null) {
  90       return;
  91     }
  92     Enumeration e = possiblePairs.elements();
  93     boolean found = false;
  94     while (e.hasMoreElements()) {
  95       Pair other = (Pair) e.nextElement();
  96       if (other.getValue() == pair.getValue()) {
  97         other.incrementCount();
  98         found = true;
  99         break;
 100       }
 101     }
 102     if (!found) {
 103       possiblePairs.addElement(pair);
 104     }
 105   }
 106
 107   public void reset() {
 108     possibleLeftPairs.setSize(0);
 109     possibleRightPairs.setSize(0);
 110   }
 111
 112   private static Result constructResult(Pair leftPair, Pair rightPair) {
 113     long symbolValue = 4537077L * leftPair.getValue() + rightPair.getValue();
 114     String text = String.valueOf(symbolValue);
 115
 116     StringBuffer buffer = new StringBuffer(14);
 117     for (int i = 13 - text.length(); i > 0; i--) {
 118       buffer.append('0');
 119     }
 120     buffer.append(text);
 121
 122     int checkDigit = 0;
 123     for (int i = 0; i < 13; i++) {
 124       int digit = buffer.charAt(i) - '0';
 125       checkDigit += (((i & 0x01) == 0) ? 3 * digit : digit);
 126     }
 127     checkDigit = 10 - (checkDigit % 10);
 128     if (checkDigit == 10) {
 129       checkDigit = 0;
 130     }
 131     buffer.append(checkDigit);
 132
 133     ResultPoint[] leftPoints = leftPair.getFinderPattern().getResultPoints();
 134     ResultPoint[] rightPoints = rightPair.getFinderPattern().getResultPoints();
 135     return new Result(
 136         String.valueOf(buffer.toString()),
 137         null,
 138         new ResultPoint[] { leftPoints[0], leftPoints[1], rightPoints[0], rightPoints[1], },
 139         BarcodeFormat.RSS14);
 140   }
 141
 142   private static boolean checkChecksum(Pair leftPair, Pair rightPair) {
 143     int leftFPValue = leftPair.getFinderPattern().getValue();
 144     int rightFPValue = rightPair.getFinderPattern().getValue();
 145     if ((leftFPValue == 0 && rightFPValue == 8) ||
 146         (leftFPValue == 8 && rightFPValue == 0)) {
 147     }
 148     int checkValue = (leftPair.getChecksumPortion() + 16 * rightPair.getChecksumPortion()) % 79;
 149     int targetCheckValue =
 150         9 * leftPair.getFinderPattern().getValue() + rightPair.getFinderPattern().getValue();
 151     if (targetCheckValue > 72) {
 152       targetCheckValue--;
 153     }
 154     if (targetCheckValue > 8) {
 155       targetCheckValue--;
 156     }
 157     return checkValue == targetCheckValue;
 158   }
 159
 160   private Pair decodePair(BitArray row, boolean right, int rowNumber, Hashtable hints) {
 161     try {
 162       int[] startEnd = findFinderPattern(row, 0, right);
 163       FinderPattern pattern = parseFoundFinderPattern(row, rowNumber, right, startEnd);
 164
 165       ResultPointCallback resultPointCallback = hints == null ? null :
 166         (ResultPointCallback) hints.get(DecodeHintType.NEED_RESULT_POINT_CALLBACK);
 167
 168       if (resultPointCallback != null) {
 169         float center = (startEnd[0] + startEnd[1]) / 2.0f;
 170         if (right) {
 171           // row is actually reversed
 172           center = row.getSize() - 1 - center;
 173         }
 174         resultPointCallback.foundPossibleResultPoint(new ResultPoint(center, rowNumber));
 175       }
 176
 177       DataCharacter outside = decodeDataCharacter(row, pattern, true);
 178       DataCharacter inside = decodeDataCharacter(row, pattern, false);
 179       return new Pair(1597 * outside.getValue() + inside.getValue(),
 180                       outside.getChecksumPortion() + 4 * inside.getChecksumPortion(),
 181                       pattern);
 182     } catch (NotFoundException re) {
 183       return null;
 184     }
 185   }
 186
 187   private DataCharacter decodeDataCharacter(BitArray row, FinderPattern pattern, boolean outsideChar)
 188       throws NotFoundException {
 189
 190     int[] counters = dataCharacterCounters;
 191     counters[0] = 0;
 192     counters[1] = 0;
 193     counters[2] = 0;
 194     counters[3] = 0;
 195     counters[4] = 0;
 196     counters[5] = 0;
 197     counters[6] = 0;
 198     counters[7] = 0;
 199
 200     if (outsideChar) {
 201       recordPatternInReverse(row, pattern.getStartEnd()[0], counters);
 202     } else {
 203       recordPattern(row, pattern.getStartEnd()[1] + 1, counters);
 204       // reverse it
 205       for (int i = 0, j = counters.length - 1; i < j; i++, j--) {
 206         int temp = counters[i];
 207         counters[i] = counters[j];
 208         counters[j] = temp;
 209       }
 210     }
 211
 212     int numModules = outsideChar ? 16 : 15;
 213     float elementWidth = (float) count(counters) / (float) numModules;
 214
 215     int[] oddCounts = this.oddCounts;
 216     int[] evenCounts = this.evenCounts;
 217     float[] oddRoundingErrors = this.oddRoundingErrors;
 218     float[] evenRoundingErrors = this.evenRoundingErrors;
 219
 220     for (int i = 0; i < counters.length; i++) {
 221       float value = (float) counters[i] / elementWidth;
 222       int count = (int) (value + 0.5f); // Round
 223       if (count < 1) {
 224         count = 1;
 225       } else if (count > 8) {
 226         count = 8;
 227       }
 228       int offset = i >> 1;
 229       if ((i & 0x01) == 0) {
 230         oddCounts[offset] = count;
 231         oddRoundingErrors[offset] = value - count;
 232       } else {
 233         evenCounts[offset] = count;
 234         evenRoundingErrors[offset] = value - count;
 235       }
 236     }
 237
 238     adjustOddEvenCounts(outsideChar, numModules);
 239
 240     int oddSum = 0;
 241     int oddChecksumPortion = 0;
 242     for (int i = oddCounts.length - 1; i >= 0; i--) {
 243       oddChecksumPortion *= 9;
 244       oddChecksumPortion += oddCounts[i];
 245       oddSum += oddCounts[i];
 246     }
 247     int evenChecksumPortion = 0;
 248     int evenSum = 0;
 249     for (int i = evenCounts.length - 1; i >= 0; i--) {
 250       evenChecksumPortion *= 9;
 251       evenChecksumPortion += evenCounts[i];
 252       evenSum += evenCounts[i];
 253     }
 254     int checksumPortion = oddChecksumPortion + 3*evenChecksumPortion;
 255
 256     if (outsideChar) {
 257       if ((oddSum & 0x01) != 0 || oddSum > 12 || oddSum < 4) {
 258         throw NotFoundException.getNotFoundInstance();
 259       }
 260       int group = (12 - oddSum) / 2;
 261       int oddWidest = OUTSIDE_ODD_WIDEST[group];
 262       int evenWidest = 9 - oddWidest;
 263       int vOdd = RSSUtils.getRSSvalue(oddCounts, oddWidest, false);
 264       int vEven = RSSUtils.getRSSvalue(evenCounts, evenWidest, true);
 265       int tEven = OUTSIDE_EVEN_TOTAL_SUBSET[group];
 266       int gSum = OUTSIDE_GSUM[group];
 267       return new DataCharacter(vOdd * tEven + vEven + gSum, checksumPortion);
 268     } else {
 269       if ((evenSum & 0x01) != 0 || evenSum > 10 || evenSum < 4) {
 270         throw NotFoundException.getNotFoundInstance();
 271       }
 272       int group = (10 - evenSum) / 2;
 273       int oddWidest = INSIDE_ODD_WIDEST[group];
 274       int evenWidest = 9 - oddWidest;
 275       int vOdd = RSSUtils.getRSSvalue(oddCounts, oddWidest, true);
 276       int vEven = RSSUtils.getRSSvalue(evenCounts, evenWidest, false);
 277       int tOdd = INSIDE_ODD_TOTAL_SUBSET[group];
 278       int gSum = INSIDE_GSUM[group];
 279       return new DataCharacter(vEven * tOdd + vOdd + gSum, checksumPortion);
 280     }
 281
 282   }
 283
 284   private int[] findFinderPattern(BitArray row, int rowOffset, boolean rightFinderPattern)
 285       throws NotFoundException {
 286
 287     int[] counters = decodeFinderCounters;
 288     counters[0] = 0;
 289     counters[1] = 0;
 290     counters[2] = 0;
 291     counters[3] = 0;
 292
 293     int width = row.getSize();
 294     boolean isWhite = false;
 295     while (rowOffset < width) {
 296       isWhite = !row.get(rowOffset);
 297       if (rightFinderPattern == isWhite) {
 298         // Will encounter white first when searching for right finder pattern
 299         break;
 300       }
 301       rowOffset++;
 302     }
 303
 304     int counterPosition = 0;
 305     int patternStart = rowOffset;
 306     for (int x = rowOffset; x < width; x++) {
 307       boolean pixel = row.get(x);
 308       if (pixel ^ isWhite) {
 309         counters[counterPosition]++;
 310       } else {
 311         if (counterPosition == 3) {
 312           if (isFinderPattern(counters)) {
 313             return new int[]{patternStart, x};
 314           }
 315           patternStart += counters[0] + counters[1];
 316           counters[0] = counters[2];
 317           counters[1] = counters[3];
 318           counters[2] = 0;
 319           counters[3] = 0;
 320           counterPosition--;
 321         } else {
 322           counterPosition++;
 323         }
 324         counters[counterPosition] = 1;
 325         isWhite = !isWhite;
 326       }
 327     }
 328     throw NotFoundException.getNotFoundInstance();
 329
 330   }
 331
 332   private FinderPattern parseFoundFinderPattern(BitArray row, int rowNumber, boolean right, int[] startEnd)
 333       throws NotFoundException {
 334     // Actually we found elements 2-5
 335     boolean firstIsBlack = row.get(startEnd[0]);
 336     int firstElementStart = startEnd[0] - 1;
 337     // Locate element 1
 338     while (firstElementStart >= 0 && firstIsBlack ^ row.get(firstElementStart)) {
 339       firstElementStart--;
 340     }
 341     firstElementStart++;
 342     int firstCounter = startEnd[0] - firstElementStart;
 343     // Make 'counters' hold 1-4
 344     int[] counters = decodeFinderCounters;
 345     for (int i = counters.length - 1; i > 0; i--) {
 346       counters[i] = counters[i-1];
 347     }
 348     counters[0] = firstCounter;
 349     int value = parseFinderValue(counters, FINDER_PATTERNS);
 350     int start = firstElementStart;
 351     int end = startEnd[1];
 352     if (right) {
 353       // row is actually reversed
 354       start = row.getSize() - 1 - start;
 355       end = row.getSize() - 1 - end;
 356     }
 357     return new FinderPattern(value, new int[] {firstElementStart, startEnd[1]}, start, end, rowNumber);
 358   }
 359
 360   /*
 361   private static int[] normalizeE2SEValues(int[] counters) {
 362     int p = 0;
 363     for (int i = 0; i < counters.length; i++) {
 364       p += counters[i];
 365     }
 366     int[] normalized = new int[counters.length - 2];
 367     for (int i = 0; i < normalized.length; i++) {
 368       int e = counters[i] + counters[i+1];
 369       float eRatio = (float) e / (float) p;
 370       float E = ((eRatio * 32.0f) + 1.0f) / 2.0f;
 371       normalized[i] = (int) E;
 372     }
 373     return normalized;
 374   }
 375    */
 376
 377   private void adjustOddEvenCounts(boolean outsideChar, int numModules) throws NotFoundException {
 378
 379     int oddSum = count(oddCounts);
 380     int evenSum = count(evenCounts);
 381     int mismatch = oddSum + evenSum - numModules;
 382     boolean oddParityBad = (oddSum & 0x01) == (outsideChar ? 1 : 0);
 383     boolean evenParityBad = (evenSum & 0x01) == 1;
 384
 385     boolean incrementOdd = false;
 386     boolean decrementOdd = false;
 387     boolean incrementEven = false;
 388     boolean decrementEven = false;
 389
 390     if (outsideChar) {
 391       if (oddSum > 12) {
 392         decrementOdd = true;
 393       } else if (oddSum < 4) {
 394         incrementOdd = true;
 395       }
 396       if (evenSum > 12) {
 397         decrementEven = true;
 398       } else if (evenSum < 4) {
 399         incrementEven = true;
 400       }
 401     } else {
 402       if (oddSum > 11) {
 403         decrementOdd = true;
 404       } else if (oddSum < 5) {
 405         incrementOdd = true;
 406       }
 407       if (evenSum > 10) {
 408         decrementEven = true;
 409       } else if (evenSum < 4) {
 410         incrementEven = true;
 411       }
 412     }
 413
 414     /*if (mismatch == 2) {
 415       if (!(oddParityBad && evenParityBad)) {
 416         throw ReaderException.getInstance();
 417       }
 418       decrementOdd = true;
 419       decrementEven = true;
 420     } else if (mismatch == -2) {
 421       if (!(oddParityBad && evenParityBad)) {
 422         throw ReaderException.getInstance();
 423       }
 424       incrementOdd = true;
 425       incrementEven = true;
 426     } else */if (mismatch == 1) {
 427       if (oddParityBad) {
 428         if (evenParityBad) {
 429           throw NotFoundException.getNotFoundInstance();
 430         }
 431         decrementOdd = true;
 432       } else {
 433         if (!evenParityBad) {
 434           throw NotFoundException.getNotFoundInstance();
 435         }
 436         decrementEven = true;
 437       }
 438     } else if (mismatch == -1) {
 439       if (oddParityBad) {
 440         if (evenParityBad) {
 441           throw NotFoundException.getNotFoundInstance();
 442         }
 443         incrementOdd = true;
 444       } else {
 445         if (!evenParityBad) {
 446           throw NotFoundException.getNotFoundInstance();
 447         }
 448         incrementEven = true;
 449       }
 450     } else if (mismatch == 0) {
 451       if (oddParityBad) {
 452         if (!evenParityBad) {
 453           throw NotFoundException.getNotFoundInstance();
 454         }
 455         // Both bad
 456         if (oddSum < evenSum) {
 457           incrementOdd = true;
 458           decrementEven = true;
 459         } else {
 460           decrementOdd = true;
 461           incrementEven = true;
 462         }
 463       } else {
 464         if (evenParityBad) {
 465           throw NotFoundException.getNotFoundInstance();
 466         }
 467         // Nothing to do!
 468       }
 469     } else {
 470       throw NotFoundException.getNotFoundInstance();
 471     }
 472
 473     if (incrementOdd) {
 474       if (decrementOdd) {
 475         throw NotFoundException.getNotFoundInstance();
 476       }
 477       increment(oddCounts, oddRoundingErrors);
 478     }
 479     if (decrementOdd) {
 480       decrement(oddCounts, oddRoundingErrors);
 481     }
 482     if (incrementEven) {
 483       if (decrementEven) {
 484         throw NotFoundException.getNotFoundInstance();
 485       }
 486       increment(evenCounts, oddRoundingErrors);
 487     }
 488     if (decrementEven) {
 489       decrement(evenCounts, evenRoundingErrors);
 490     }
 491
 492   }
 493
 494 }