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 import com.google.zxing.oned.OneDReader;
  27
  28 import java.util.Enumeration;
  29 import java.util.Hashtable;
  30 import java.util.Vector;
  31
  32 /**
  33  * Decodes RSS-14, including truncated and stacked variants. See ISO/IEC 24724:2006.
  34  */
  35 public final class RSS14Reader extends OneDReader {
  36
  37   private static final int MAX_AVG_VARIANCE = (int) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.2f);
  38   private static final int MAX_INDIVIDUAL_VARIANCE = (int) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.4f);
  39
  40   private static final float MIN_FINDER_PATTERN_RATIO = 9.5f / 12.0f;
  41   private static final float MAX_FINDER_PATTERN_RATIO = 12.5f / 14.0f;
  42
  43   private static final int[] OUTSIDE_EVEN_TOTAL_SUBSET = {1,10,34,70,126};
  44   private static final int[] INSIDE_ODD_TOTAL_SUBSET = {4,20,48,81};
  45   private static final int[] OUTSIDE_GSUM = {0,161,961,2015,2715};
  46   private static final int[] INSIDE_GSUM = {0,336,1036,1516};
  47   private static final int[] OUTSIDE_ODD_WIDEST = {8,6,4,3,1};
  48   private static final int[] INSIDE_ODD_WIDEST = {2,4,6,8};
  49
  50   private static final int[][] FINDER_PATTERNS = {
  51       {3,8,2,1},
  52       {3,5,5,1},
  53       {3,3,7,1},
  54       {3,1,9,1},
  55       {2,7,4,1},
  56       {2,5,6,1},
  57       {2,3,8,1},
  58       {1,5,7,1},
  59       {1,3,9,1},
  60   };
  61
  62   private final int[] decodeFinderCounters;
  63   private final int[] dataCharacterCounters;
  64   private final float[] oddRoundingErrors;
  65   private final float[] evenRoundingErrors;
  66   private final int[] oddCounts;
  67   private final int[] evenCounts;
  68   private final Vector possibleLeftPairs;
  69   private final Vector possibleRightPairs;
  70
  71   public RSS14Reader() {
  72     decodeFinderCounters = new int[4];
  73     dataCharacterCounters = new int[8];
  74     oddRoundingErrors = new float[4];
  75     evenRoundingErrors = new float[4];
  76     oddCounts = new int[dataCharacterCounters.length / 2];
  77     evenCounts = new int[dataCharacterCounters.length / 2];
  78     possibleLeftPairs = new Vector();
  79     possibleRightPairs = new Vector();
  80   }
  81
  82   public Result decodeRow(int rowNumber, BitArray row, Hashtable hints) throws NotFoundException {
  83     Pair leftPair = decodePair(row, false, rowNumber, hints);
  84     addOrTally(possibleLeftPairs, leftPair);
  85     row.reverse();
  86     Pair rightPair = decodePair(row, true, rowNumber, hints);
  87     addOrTally(possibleRightPairs, rightPair);
  88     row.reverse();
  89     int numLeftPairs = possibleLeftPairs.size();
  90     int numRightPairs = possibleRightPairs.size();
  91     for (int l = 0; l < numLeftPairs; l++) {
  92       Pair left = (Pair) possibleLeftPairs.elementAt(l);
  93       if (left.getCount() > 1) {
  94         for (int r = 0; r < numRightPairs; r++) {
  95           Pair right = (Pair) possibleRightPairs.elementAt(r);
  96           if (right.getCount() > 1) {
  97             if (checkChecksum(left, right)) {
  98               return constructResult(left, right);
  99             }
 100           }
 101         }
 102       }
 103     }
 104     throw NotFoundException.getNotFoundInstance();
 105   }
 106
 107   private static void addOrTally(Vector possiblePairs, Pair pair) {
 108     if (pair == null) {
 109       return;
 110     }
 111     Enumeration e = possiblePairs.elements();
 112     boolean found = false;
 113     while (e.hasMoreElements()) {
 114       Pair other = (Pair) e.nextElement();
 115       if (other.getValue() == pair.getValue()) {
 116         other.incrementCount();
 117         found = true;
 118         break;
 119       }
 120     }
 121     if (!found) {
 122       possiblePairs.addElement(pair);
 123     }
 124   }
 125
 126   public void reset() {
 127     possibleLeftPairs.setSize(0);
 128     possibleRightPairs.setSize(0);
 129   }
 130
 131   private static Result constructResult(Pair leftPair, Pair rightPair) {
 132     long symbolValue = 4537077L * leftPair.getValue() + rightPair.getValue();
 133     String text = String.valueOf(symbolValue);
 134
 135     StringBuffer buffer = new StringBuffer(14);
 136     for (int i = 13 - text.length(); i > 0; i--) {
 137       buffer.append('0');
 138     }
 139     buffer.append(text);
 140
 141     int checkDigit = 0;
 142     for (int i = 0; i < 13; i++) {
 143       int digit = buffer.charAt(i) - '0';
 144       checkDigit += (((i & 0x01) == 0) ? 3 * digit : digit);
 145     }
 146     checkDigit = 10 - (checkDigit % 10);
 147     if (checkDigit == 10) {
 148       checkDigit = 0;
 149     }
 150     buffer.append(checkDigit);
 151
 152     ResultPoint[] leftPoints = leftPair.getFinderPattern().getResultPoints();
 153     ResultPoint[] rightPoints = rightPair.getFinderPattern().getResultPoints();
 154     return new Result(
 155         String.valueOf(buffer.toString()),
 156         null,
 157         new ResultPoint[] { leftPoints[0], leftPoints[1], rightPoints[0], rightPoints[1], },
 158         BarcodeFormat.RSS14);
 159   }
 160
 161   private static boolean checkChecksum(Pair leftPair, Pair rightPair) {
 162     int leftFPValue = leftPair.getFinderPattern().getValue();
 163     int rightFPValue = rightPair.getFinderPattern().getValue();
 164     if ((leftFPValue == 0 && rightFPValue == 8) ||
 165         (leftFPValue == 8 && rightFPValue == 0)) {
 166     }
 167     int checkValue = (leftPair.getChecksumPortion() + 16 * rightPair.getChecksumPortion()) % 79;
 168     int targetCheckValue =
 169         9 * leftPair.getFinderPattern().getValue() + rightPair.getFinderPattern().getValue();
 170     if (targetCheckValue > 72) {
 171       targetCheckValue--;
 172     }
 173     if (targetCheckValue > 8) {
 174       targetCheckValue--;
 175     }
 176     return checkValue == targetCheckValue;
 177   }
 178
 179   private Pair decodePair(BitArray row, boolean right, int rowNumber, Hashtable hints) {
 180     try {
 181       int[] startEnd = findFinderPattern(row, 0, right);
 182       FinderPattern pattern = parseFoundFinderPattern(row, rowNumber, right, startEnd);
 183
 184       ResultPointCallback resultPointCallback = hints == null ? null :
 185         (ResultPointCallback) hints.get(DecodeHintType.NEED_RESULT_POINT_CALLBACK);
 186
 187       if (resultPointCallback != null) {
 188         float center = (startEnd[0] + startEnd[1]) / 2.0f;
 189         if (right) {
 190           // row is actually reversed
 191           center = row.getSize() - 1 - center;
 192         }
 193         resultPointCallback.foundPossibleResultPoint(new ResultPoint(center, rowNumber));
 194       }
 195
 196       DataCharacter outside = decodeDataCharacter(row, pattern, true);
 197       DataCharacter inside = decodeDataCharacter(row, pattern, false);
 198       return new Pair(1597 * outside.getValue() + inside.getValue(),
 199                       outside.getChecksumPortion() + 4 * inside.getChecksumPortion(),
 200                       pattern);
 201     } catch (NotFoundException re) {
 202       return null;
 203     }
 204   }
 205
 206   private DataCharacter decodeDataCharacter(BitArray row, FinderPattern pattern, boolean outsideChar)
 207       throws NotFoundException {
 208
 209     int[] counters = dataCharacterCounters;
 210     counters[0] = 0;
 211     counters[1] = 0;
 212     counters[2] = 0;
 213     counters[3] = 0;
 214     counters[4] = 0;
 215     counters[5] = 0;
 216     counters[6] = 0;
 217     counters[7] = 0;
 218
 219     if (outsideChar) {
 220       recordPatternInReverse(row, pattern.getStartEnd()[0], counters);
 221     } else {
 222       recordPattern(row, pattern.getStartEnd()[1] + 1, counters);
 223       // reverse it
 224       for (int i = 0, j = counters.length - 1; i < j; i++, j--) {
 225         int temp = counters[i];
 226         counters[i] = counters[j];
 227         counters[j] = temp;
 228       }
 229     }
 230
 231     int numModules = outsideChar ? 16 : 15;
 232     float elementWidth = (float) count(counters) / (float) numModules;
 233
 234     int[] oddCounts = this.oddCounts;
 235     int[] evenCounts = this.evenCounts;
 236     float[] oddRoundingErrors = this.oddRoundingErrors;
 237     float[] evenRoundingErrors = this.evenRoundingErrors;
 238
 239     for (int i = 0; i < counters.length; i++) {
 240       float value = (float) counters[i] / elementWidth;
 241       int count = (int) (value + 0.5f); // Round
 242       if (count < 1) {
 243         count = 1;
 244       } else if (count > 8) {
 245         count = 8;
 246       }
 247       int offset = i >> 1;
 248       if ((i & 0x01) == 0) {
 249         oddCounts[offset] = count;
 250         oddRoundingErrors[offset] = value - count;
 251       } else {
 252         evenCounts[offset] = count;
 253         evenRoundingErrors[offset] = value - count;
 254       }
 255     }
 256
 257     adjustOddEvenCounts(outsideChar, numModules);
 258
 259     int oddSum = 0;
 260     int oddChecksumPortion = 0;
 261     for (int i = oddCounts.length - 1; i >= 0; i--) {
 262       oddChecksumPortion *= 9;
 263       oddChecksumPortion += oddCounts[i];
 264       oddSum += oddCounts[i];
 265     }
 266     int evenChecksumPortion = 0;
 267     int evenSum = 0;
 268     for (int i = evenCounts.length - 1; i >= 0; i--) {
 269       evenChecksumPortion *= 9;
 270       evenChecksumPortion += evenCounts[i];
 271       evenSum += evenCounts[i];
 272     }
 273     int checksumPortion = oddChecksumPortion + 3*evenChecksumPortion;
 274
 275     if (outsideChar) {
 276       if ((oddSum & 0x01) != 0 || oddSum > 12 || oddSum < 4) {
 277         throw NotFoundException.getNotFoundInstance();
 278       }
 279       int group = (12 - oddSum) / 2;
 280       int oddWidest = OUTSIDE_ODD_WIDEST[group];
 281       int evenWidest = 9 - oddWidest;
 282       int vOdd = RSSUtils.getRSSvalue(oddCounts, oddWidest, false);
 283       int vEven = RSSUtils.getRSSvalue(evenCounts, evenWidest, true);
 284       int tEven = OUTSIDE_EVEN_TOTAL_SUBSET[group];
 285       int gSum = OUTSIDE_GSUM[group];
 286       return new DataCharacter(vOdd * tEven + vEven + gSum, checksumPortion);
 287     } else {
 288       if ((evenSum & 0x01) != 0 || evenSum > 10 || evenSum < 4) {
 289         throw NotFoundException.getNotFoundInstance();
 290       }
 291       int group = (10 - evenSum) / 2;
 292       int oddWidest = INSIDE_ODD_WIDEST[group];
 293       int evenWidest = 9 - oddWidest;
 294       int vOdd = RSSUtils.getRSSvalue(oddCounts, oddWidest, true);
 295       int vEven = RSSUtils.getRSSvalue(evenCounts, evenWidest, false);
 296       int tOdd = INSIDE_ODD_TOTAL_SUBSET[group];
 297       int gSum = INSIDE_GSUM[group];
 298       return new DataCharacter(vEven * tOdd + vOdd + gSum, checksumPortion);
 299     }
 300
 301   }
 302
 303   private int[] findFinderPattern(BitArray row, int rowOffset, boolean rightFinderPattern)
 304       throws NotFoundException {
 305
 306     int[] counters = decodeFinderCounters;
 307     counters[0] = 0;
 308     counters[1] = 0;
 309     counters[2] = 0;
 310     counters[3] = 0;
 311
 312     int width = row.getSize();
 313     boolean isWhite = false;
 314     while (rowOffset < width) {
 315       isWhite = !row.get(rowOffset);
 316       if (rightFinderPattern == isWhite) {
 317         // Will encounter white first when searching for right finder pattern
 318         break;
 319       }
 320       rowOffset++;
 321     }
 322
 323     int counterPosition = 0;
 324     int patternStart = rowOffset;
 325     for (int x = rowOffset; x < width; x++) {
 326       boolean pixel = row.get(x);
 327       if (pixel ^ isWhite) {
 328         counters[counterPosition]++;
 329       } else {
 330         if (counterPosition == 3) {
 331           if (isFinderPattern(counters)) {
 332             return new int[]{patternStart, x};
 333           }
 334           patternStart += counters[0] + counters[1];
 335           counters[0] = counters[2];
 336           counters[1] = counters[3];
 337           counters[2] = 0;
 338           counters[3] = 0;
 339           counterPosition--;
 340         } else {
 341           counterPosition++;
 342         }
 343         counters[counterPosition] = 1;
 344         isWhite = !isWhite;
 345       }
 346     }
 347     throw NotFoundException.getNotFoundInstance();
 348
 349   }
 350
 351   private static boolean isFinderPattern(int[] counters) {
 352     int firstTwoSum = counters[0] + counters[1];
 353     int sum = firstTwoSum + counters[2] + counters[3];
 354     float ratio = (float) firstTwoSum / (float) sum;
 355     if (ratio >= MIN_FINDER_PATTERN_RATIO && ratio <= MAX_FINDER_PATTERN_RATIO) {
 356       // passes ratio test in spec, but see if the counts are unreasonable
 357       int minCounter = Integer.MAX_VALUE;
 358       int maxCounter = Integer.MIN_VALUE;
 359       for (int i = 0; i < counters.length; i++) {
 360         int counter = counters[i];
 361         if (counter > maxCounter) {
 362           maxCounter = counter;
 363         }
 364         if (counter < minCounter) {
 365           minCounter = counter;
 366         }
 367       }
 368       return maxCounter < 10 * minCounter;
 369     }
 370     return false;
 371   }
 372
 373   private FinderPattern parseFoundFinderPattern(BitArray row, int rowNumber, boolean right, int[] startEnd)
 374       throws NotFoundException {
 375     // Actually we found elements 2-5
 376     boolean firstIsBlack = row.get(startEnd[0]);
 377     int firstElementStart = startEnd[0] - 1;
 378     // Locate element 1
 379     while (firstElementStart >= 0 && firstIsBlack ^ row.get(firstElementStart)) {
 380       firstElementStart--;
 381     }
 382     firstElementStart++;
 383     int firstCounter = startEnd[0] - firstElementStart;
 384     // Make 'counters' hold 1-4
 385     int[] counters = decodeFinderCounters;
 386     for (int i = counters.length - 1; i > 0; i--) {
 387       counters[i] = counters[i-1];
 388     }
 389     counters[0] = firstCounter;
 390     int value = parseFinderValue(counters);
 391     int start = firstElementStart;
 392     int end = startEnd[1];
 393     if (right) {
 394       // row is actually reversed
 395       start = row.getSize() - 1 - start;
 396       end = row.getSize() - 1 - end;
 397     }
 398     return new FinderPattern(value, new int[] {firstElementStart, startEnd[1]}, start, end, rowNumber);
 399   }
 400
 401   private static int parseFinderValue(int[] counters) throws NotFoundException {
 402     for (int value = 0; value < FINDER_PATTERNS.length; value++) {
 403       if (patternMatchVariance(counters, FINDER_PATTERNS[value], MAX_INDIVIDUAL_VARIANCE) <
 404           MAX_AVG_VARIANCE) {
 405         return value;
 406       }
 407     }
 408     throw NotFoundException.getNotFoundInstance();
 409   }
 410
 411   /*
 412   private static int[] normalizeE2SEValues(int[] counters) {
 413     int p = 0;
 414     for (int i = 0; i < counters.length; i++) {
 415       p += counters[i];
 416     }
 417     int[] normalized = new int[counters.length - 2];
 418     for (int i = 0; i < normalized.length; i++) {
 419       int e = counters[i] + counters[i+1];
 420       float eRatio = (float) e / (float) p;
 421       float E = ((eRatio * 32.0f) + 1.0f) / 2.0f;
 422       normalized[i] = (int) E;
 423     }
 424     return normalized;
 425   }
 426    */
 427
 428   private static int count(int[] array) {
 429     int count = 0;
 430     for (int i = 0; i < array.length; i++) {
 431       count += array[i];
 432     }
 433     return count;
 434   }
 435
 436   private static void increment(int[] array, float[] errors) {
 437     int index = 0;
 438     float biggestError = errors[0];
 439     for (int i = 1; i < array.length; i++) {
 440       if (errors[i] > biggestError) {
 441         biggestError = errors[i];
 442         index = i;
 443       }
 444     }
 445     array[index]++;
 446   }
 447
 448   private static void decrement(int[] array, float[] errors) {
 449     int index = 0;
 450     float biggestError = errors[0];
 451     for (int i = 1; i < array.length; i++) {
 452       if (errors[i] < biggestError) {
 453         biggestError = errors[i];
 454         index = i;
 455       }
 456     }
 457     array[index]--;
 458   }
 459
 460   private void adjustOddEvenCounts(boolean outsideChar, int numModules) throws NotFoundException {
 461
 462     int oddSum = count(oddCounts);
 463     int evenSum = count(evenCounts);
 464     int mismatch = oddSum + evenSum - numModules;
 465     boolean oddParityBad = (oddSum & 0x01) == (outsideChar ? 1 : 0);
 466     boolean evenParityBad = (evenSum & 0x01) == 1;
 467
 468     boolean incrementOdd = false;
 469     boolean decrementOdd = false;
 470     boolean incrementEven = false;
 471     boolean decrementEven = false;
 472
 473     if (outsideChar) {
 474       if (oddSum > 12) {
 475         decrementOdd = true;
 476       } else if (oddSum < 4) {
 477         incrementOdd = true;
 478       }
 479       if (evenSum > 12) {
 480         decrementEven = true;
 481       } else if (evenSum < 4) {
 482         incrementEven = true;
 483       }
 484     } else {
 485       if (oddSum > 11) {
 486         decrementOdd = true;
 487       } else if (oddSum < 5) {
 488         incrementOdd = true;
 489       }
 490       if (evenSum > 10) {
 491         decrementEven = true;
 492       } else if (evenSum < 4) {
 493         incrementEven = true;
 494       }
 495     }
 496
 497     /*if (mismatch == 2) {
 498       if (!(oddParityBad && evenParityBad)) {
 499         throw ReaderException.getInstance();
 500       }
 501       decrementOdd = true;
 502       decrementEven = true;
 503     } else if (mismatch == -2) {
 504       if (!(oddParityBad && evenParityBad)) {
 505         throw ReaderException.getInstance();
 506       }
 507       incrementOdd = true;
 508       incrementEven = true;
 509     } else */if (mismatch == 1) {
 510       if (oddParityBad) {
 511         if (evenParityBad) {
 512           throw NotFoundException.getNotFoundInstance();
 513         }
 514         decrementOdd = true;
 515       } else {
 516         if (!evenParityBad) {
 517           throw NotFoundException.getNotFoundInstance();
 518         }
 519         decrementEven = true;
 520       }
 521     } else if (mismatch == -1) {
 522       if (oddParityBad) {
 523         if (evenParityBad) {
 524           throw NotFoundException.getNotFoundInstance();
 525         }
 526         incrementOdd = true;
 527       } else {
 528         if (!evenParityBad) {
 529           throw NotFoundException.getNotFoundInstance();
 530         }
 531         incrementEven = true;
 532       }
 533     } else if (mismatch == 0) {
 534       if (oddParityBad) {
 535         if (!evenParityBad) {
 536           throw NotFoundException.getNotFoundInstance();
 537         }
 538         // Both bad
 539         if (oddSum < evenSum) {
 540           incrementOdd = true;
 541           decrementEven = true;
 542         } else {
 543           decrementOdd = true;
 544           incrementEven = true;
 545         }
 546       } else {
 547         if (evenParityBad) {
 548           throw NotFoundException.getNotFoundInstance();
 549         }
 550         // Nothing to do!
 551       }
 552     } else {
 553       throw NotFoundException.getNotFoundInstance();
 554     }
 555
 556     if (incrementOdd) {
 557       if (decrementOdd) {
 558         throw NotFoundException.getNotFoundInstance();
 559       }
 560       increment(oddCounts, oddRoundingErrors);
 561     }
 562     if (decrementOdd) {
 563       decrement(oddCounts, oddRoundingErrors);
 564     }
 565     if (incrementEven) {
 566       if (decrementEven) {
 567         throw NotFoundException.getNotFoundInstance();
 568       }
 569       increment(evenCounts, oddRoundingErrors);
 570     }
 571     if (decrementEven) {
 572       decrement(evenCounts, evenRoundingErrors);
 573     }
 574
 575   }
 576
 577 }