core/src/com/google/zxing/oned/rss/expanded/RSSExpandedReader.java

   1 /*
   2  * Copyright (C) 2010 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 /*
  18  * These authors would like to acknowledge the Spanish Ministry of Industry,
  19  * Tourism and Trade, for the support in the project TSI020301-2008-2
  20  * "PIRAmIDE: Personalizable Interactions with Resources on AmI-enabled
  21  * Mobile Dynamic Environments", led by Treelogic
  22  * ( http://www.treelogic.com/ ):
  23  *
  24  *   http://www.piramidepse.com/
  25  */
  26
  27 package com.google.zxing.oned.rss.expanded;
  28
  29 import java.util.Hashtable;
  30 import java.util.Vector;
  31
  32 import com.google.zxing.BarcodeFormat;
  33 import com.google.zxing.NotFoundException;
  34 import com.google.zxing.Result;
  35 import com.google.zxing.ResultPoint;
  36 import com.google.zxing.common.BitArray;
  37 import com.google.zxing.oned.rss.AbstractRSSReader;
  38 import com.google.zxing.oned.rss.DataCharacter;
  39 import com.google.zxing.oned.rss.FinderPattern;
  40 import com.google.zxing.oned.rss.RSSUtils;
  41 import com.google.zxing.oned.rss.expanded.decoders.AbstractExpandedDecoder;
  42
  43 /**
  44  * @author Pablo Orduña, University of Deusto (pablo.orduna@deusto.es)
  45  * @author Eduardo Castillejo, University of Deusto (eduardo.castillejo@deusto.es)
  46  */
  47 public final class RSSExpandedReader extends AbstractRSSReader{
  48
  49   private static final int[] SYMBOL_WIDEST = {7, 5, 4, 3, 1};
  50   private static final int[] EVEN_TOTAL_SUBSET = {4, 20, 52, 104, 204};
  51   private static final int[] GSUM = {0, 348, 1388, 2948, 3988};
  52
  53   private static final int[][] FINDER_PATTERNS = {
  54     {1,8,4,1}, // A
  55     {3,6,4,1}, // B
  56     {3,4,6,1}, // C
  57     {3,2,8,1}, // D
  58     {2,6,5,1}, // E
  59     {2,2,9,1}  // F
  60   };
  61
  62   private static final int[][] WEIGHTS = {
  63     {  1,   3,   9,  27,  81,  32,  96,  77},
  64     { 20,  60, 180, 118, 143,   7,  21,  63},
  65     {189, 145,  13,  39, 117, 140, 209, 205},
  66     {193, 157,  49, 147,  19,  57, 171,  91},
  67     { 62, 186, 136, 197, 169,  85,  44, 132},
  68     {185, 133, 188, 142,   4,  12,  36, 108},
  69     {113, 128, 173,  97,  80,  29,  87,  50},
  70     {150,  28,  84,  41, 123, 158,  52, 156},
  71     { 46, 138, 203, 187, 139, 206, 196, 166},
  72     { 76,  17,  51, 153,  37, 111, 122, 155},
  73     { 43, 129, 176, 106, 107, 110, 119, 146},
  74     { 16,  48, 144,  10,  30,  90,  59, 177},
  75     {109, 116, 137, 200, 178, 112, 125, 164},
  76     { 70, 210, 208, 202, 184, 130, 179, 115},
  77     {134, 191, 151,  31,  93,  68, 204, 190},
  78     {148,  22,  66, 198, 172,   94, 71,   2},
  79     {  6,  18,  54, 162,  64,  192,154,  40},
  80     {120, 149,  25,  75,  14,   42,126, 167},
  81     { 79,  26,  78,  23,  69,  207,199, 175},
  82     {103,  98,  83,  38, 114, 131, 182, 124},
  83     {161,  61, 183, 127, 170,  88,  53, 159},
  84     { 55, 165,  73,   8,  24,  72,   5,  15},
  85     { 45, 135, 194, 160,  58, 174, 100,  89}
  86   };
  87
  88   private static final int FINDER_PAT_A = 0;
  89   private static final int FINDER_PAT_B = 1;
  90   private static final int FINDER_PAT_C = 2;
  91   private static final int FINDER_PAT_D = 3;
  92   private static final int FINDER_PAT_E = 4;
  93   private static final int FINDER_PAT_F = 5;
  94
  95   private static final int [][] FINDER_PATTERN_SEQUENCES = {
  96     { FINDER_PAT_A, FINDER_PAT_A },
  97     { FINDER_PAT_A, FINDER_PAT_B, FINDER_PAT_B },
  98     { FINDER_PAT_A, FINDER_PAT_C, FINDER_PAT_B, FINDER_PAT_D },
  99     { FINDER_PAT_A, FINDER_PAT_E, FINDER_PAT_B, FINDER_PAT_D, FINDER_PAT_C },
 100     { FINDER_PAT_A, FINDER_PAT_E, FINDER_PAT_B, FINDER_PAT_D, FINDER_PAT_D, FINDER_PAT_F },
 101     { FINDER_PAT_A, FINDER_PAT_E, FINDER_PAT_B, FINDER_PAT_D, FINDER_PAT_E, FINDER_PAT_F, FINDER_PAT_F },
 102     { FINDER_PAT_A, FINDER_PAT_A, FINDER_PAT_B, FINDER_PAT_B, FINDER_PAT_C, FINDER_PAT_C, FINDER_PAT_D, FINDER_PAT_D },
 103     { FINDER_PAT_A, FINDER_PAT_A, FINDER_PAT_B, FINDER_PAT_B, FINDER_PAT_C, FINDER_PAT_C, FINDER_PAT_D, FINDER_PAT_E, FINDER_PAT_E },
 104     { FINDER_PAT_A, FINDER_PAT_A, FINDER_PAT_B, FINDER_PAT_B, FINDER_PAT_C, FINDER_PAT_C, FINDER_PAT_D, FINDER_PAT_E, FINDER_PAT_F, FINDER_PAT_F },
 105     { FINDER_PAT_A, FINDER_PAT_A, FINDER_PAT_B, FINDER_PAT_B, FINDER_PAT_C, FINDER_PAT_D, FINDER_PAT_D, FINDER_PAT_E, FINDER_PAT_E, FINDER_PAT_F, FINDER_PAT_F },
 106   };
 107
 108   private static final int LONGEST_SEQUENCE_SIZE = FINDER_PATTERN_SEQUENCES[FINDER_PATTERN_SEQUENCES.length - 1].length;
 109
 110   private static final int MAX_PAIRS = 11;
 111   private final Vector pairs = new Vector(MAX_PAIRS);
 112   private final int [] startEnd = new int[2];
 113   private final int [] currentSequence = new int[LONGEST_SEQUENCE_SIZE];
 114
 115   public Result decodeRow(int rowNumber, BitArray row, Hashtable hints) throws NotFoundException {
 116     this.reset();
 117     decodeRow2pairs(rowNumber, row);
 118     return constructResult(this.pairs);
 119   }
 120
 121   public void reset() {
 122     this.pairs.setSize(0);
 123   }
 124
 125   // Not private for testing
 126   Vector decodeRow2pairs(int rowNumber, BitArray row) throws NotFoundException {
 127     while(true){
 128       ExpandedPair nextPair = retrieveNextPair(row, this.pairs, rowNumber);
 129       this.pairs.addElement(nextPair);
 130
 131       if(nextPair.mayBeLast()){
 132         if(checkChecksum()) {
 133           return this.pairs;
 134         }
 135         if(nextPair.mustBeLast()) {
 136           throw NotFoundException.getNotFoundInstance();
 137         }
 138       }
 139     }
 140   }
 141
 142   private static Result constructResult(Vector pairs) throws NotFoundException{
 143     BitArray binary = BitArrayBuilder.buildBitArray(pairs);
 144
 145     AbstractExpandedDecoder decoder = AbstractExpandedDecoder.createDecoder(binary);
 146     String resultingString = decoder.parseInformation();
 147
 148     ResultPoint [] firstPoints = ((ExpandedPair)pairs.elementAt(0)).getFinderPattern().getResultPoints();
 149     ResultPoint [] lastPoints  = ((ExpandedPair)pairs.lastElement()).getFinderPattern().getResultPoints();
 150
 151     return new Result(
 152           resultingString,
 153           null,
 154           new ResultPoint[]{firstPoints[0], firstPoints[1], lastPoints[0], lastPoints[1]},
 155           BarcodeFormat.RSS_EXPANDED
 156       );
 157   }
 158
 159   private boolean checkChecksum(){
 160     ExpandedPair firstPair = (ExpandedPair)this.pairs.elementAt(0);
 161     DataCharacter checkCharacter = firstPair.getLeftChar();
 162     DataCharacter firstCharacter = firstPair.getRightChar();
 163
 164     int checksum = firstCharacter.getChecksumPortion();
 165     int S = 2;
 166
 167     for(int i = 1; i < this.pairs.size(); ++i){
 168       ExpandedPair currentPair = (ExpandedPair)this.pairs.elementAt(i);
 169       checksum += currentPair.getLeftChar().getChecksumPortion();
 170       S++;
 171       if(currentPair.getRightChar() != null){
 172         checksum += currentPair.getRightChar().getChecksumPortion();
 173         S++;
 174       }
 175     }
 176
 177     checksum %= 211;
 178
 179     int checkCharacterValue = 211 * (S - 4) + checksum;
 180
 181     return checkCharacterValue == checkCharacter.getValue();
 182   }
 183
 184   private static int getNextSecondBar(BitArray row, int initialPos){
 185     int currentPos = initialPos;
 186     boolean current = row.get(currentPos);
 187
 188     while(currentPos < row.size && row.get(currentPos) == current) {
 189       currentPos++;
 190     }
 191
 192     current = !current;
 193     while(currentPos < row.size && row.get(currentPos) == current) {
 194       currentPos++;
 195     }
 196
 197     return currentPos;
 198   }
 199
 200   // not private for testing
 201   ExpandedPair retrieveNextPair(BitArray row, Vector previousPairs, int rowNumber) throws NotFoundException{
 202     boolean isOddPattern  = previousPairs.size() % 2 == 0;
 203
 204     FinderPattern pattern;
 205
 206     boolean keepFinding = true;
 207     int forcedOffset = -1;
 208     do{
 209       this.findNextPair(row, previousPairs, forcedOffset);
 210       pattern = parseFoundFinderPattern(row, rowNumber, isOddPattern);
 211       if (pattern == null){
 212         forcedOffset = getNextSecondBar(row, this.startEnd[0]);
 213       } else {
 214         keepFinding = false;
 215       }
 216     }while(keepFinding);
 217
 218     boolean mayBeLast = checkPairSequence(previousPairs, pattern);
 219
 220     DataCharacter leftChar  = this.decodeDataCharacter(row, pattern, isOddPattern, true);
 221     DataCharacter rightChar;
 222     try{
 223       rightChar = this.decodeDataCharacter(row, pattern, isOddPattern, false);
 224     }catch(NotFoundException nfe){
 225       if(mayBeLast) {
 226         rightChar = null;
 227       } else {
 228         throw nfe;
 229       }
 230     }
 231
 232     return new ExpandedPair(leftChar, rightChar, pattern, mayBeLast);
 233   }
 234
 235   private boolean checkPairSequence(Vector previousPairs, FinderPattern pattern) throws NotFoundException{
 236     int currentSequenceLength = previousPairs.size() + 1;
 237     if(currentSequenceLength > this.currentSequence.length) {
 238       throw NotFoundException.getNotFoundInstance();
 239     }
 240
 241     for(int pos = 0; pos < previousPairs.size(); ++pos) {
 242       this.currentSequence[pos] = ((ExpandedPair) previousPairs.elementAt(pos)).getFinderPattern().getValue();
 243     }
 244
 245     this.currentSequence[currentSequenceLength - 1] = pattern.getValue();
 246
 247     for(int i = 0; i < FINDER_PATTERN_SEQUENCES.length; ++i){
 248       int [] validSequence = FINDER_PATTERN_SEQUENCES[i];
 249       if(validSequence.length >= currentSequenceLength){
 250         boolean valid = true;
 251         for(int pos = 0; pos < currentSequenceLength; ++pos) {
 252           if (this.currentSequence[pos] != validSequence[pos]) {
 253             valid = false;
 254             break;
 255           }
 256         }
 257
 258         if(valid) {
 259           return currentSequenceLength == validSequence.length;
 260         }
 261       }
 262     }
 263
 264     throw NotFoundException.getNotFoundInstance();
 265   }
 266
 267   private void findNextPair(BitArray row, Vector previousPairs, int forcedOffset) throws NotFoundException{
 268     int[] counters = this.decodeFinderCounters;
 269     counters[0] = 0;
 270     counters[1] = 0;
 271     counters[2] = 0;
 272     counters[3] = 0;
 273
 274     int width = row.getSize();
 275
 276     int rowOffset;
 277     if (forcedOffset >= 0) {
 278       rowOffset = forcedOffset;
 279     } else if (previousPairs.isEmpty()) {
 280       rowOffset = 0;
 281     } else{
 282       ExpandedPair lastPair = ((ExpandedPair)previousPairs.lastElement());
 283       rowOffset = lastPair.getFinderPattern().getStartEnd()[1];
 284     }
 285     boolean searchingEvenPair = previousPairs.size() % 2 != 0;
 286
 287     boolean isWhite = false;
 288     while (rowOffset < width) {
 289       isWhite = !row.get(rowOffset);
 290       if (!isWhite) {
 291         break;
 292       }
 293       rowOffset++;
 294     }
 295
 296     int counterPosition = 0;
 297     int patternStart = rowOffset;
 298     for (int x = rowOffset; x < width; x++) {
 299       boolean pixel = row.get(x);
 300       if (pixel ^ isWhite) {
 301         counters[counterPosition]++;
 302       } else {
 303         if (counterPosition == 3) {
 304           if (searchingEvenPair) {
 305             reverseCounters(counters);
 306           }
 307
 308           if (isFinderPattern(counters)){
 309             this.startEnd[0] = patternStart;
 310             this.startEnd[1] = x;
 311             return;
 312           }
 313
 314           if (searchingEvenPair) {
 315             reverseCounters(counters);
 316           }
 317
 318           patternStart += counters[0] + counters[1];
 319           counters[0] = counters[2];
 320           counters[1] = counters[3];
 321           counters[2] = 0;
 322           counters[3] = 0;
 323           counterPosition--;
 324         } else {
 325           counterPosition++;
 326         }
 327         counters[counterPosition] = 1;
 328         isWhite = !isWhite;
 329       }
 330     }
 331     throw NotFoundException.getNotFoundInstance();
 332   }
 333
 334   private static void reverseCounters(int [] counters){
 335     int length = counters.length;
 336     for(int i = 0; i < length / 2; ++i){
 337       int tmp = counters[i];
 338       counters[i] = counters[length - i - 1];
 339       counters[length - i - 1] = tmp;
 340     }
 341   }
 342
 343   private FinderPattern parseFoundFinderPattern(BitArray row, int rowNumber, boolean oddPattern) {
 344     // Actually we found elements 2-5.
 345     int firstCounter;
 346     int start;
 347     int end;
 348
 349     if(oddPattern){
 350       // If pattern number is odd, we need to locate element 1 *before* the current block.
 351
 352       int firstElementStart = this.startEnd[0] - 1;
 353       // Locate element 1
 354       while (firstElementStart >= 0 && !row.get(firstElementStart)) {
 355         firstElementStart--;
 356       }
 357
 358       firstElementStart++;
 359       firstCounter = this.startEnd[0] - firstElementStart;
 360       start = firstElementStart;
 361       end = this.startEnd[1];
 362
 363     }else{
 364       // If pattern number is even, the pattern is reversed, so we need to locate element 1 *after* the current block.
 365
 366       start = this.startEnd[0];
 367
 368       int firstElementStart = this.startEnd[1] + 1;
 369       while(row.get(firstElementStart) && firstElementStart < row.size) {
 370         firstElementStart++;
 371       }
 372
 373       end = firstElementStart;
 374       firstCounter = end - this.startEnd[1];
 375     }
 376
 377     // Make 'counters' hold 1-4
 378     int [] counters = this.decodeFinderCounters;
 379     for (int i = counters.length - 1; i > 0; i--) {
 380       counters[i] = counters[i - 1];
 381     }
 382
 383     counters[0] = firstCounter;
 384     int value;
 385     try {
 386       value = parseFinderValue(counters, FINDER_PATTERNS);
 387     } catch (NotFoundException nfe) {
 388       return null;
 389     }
 390     return new FinderPattern(value, new int[] {start, end}, start, end, rowNumber);
 391   }
 392
 393   DataCharacter decodeDataCharacter(BitArray row, FinderPattern pattern, boolean isOddPattern, boolean leftChar)
 394     throws NotFoundException {
 395     int[] counters = this.dataCharacterCounters;
 396     counters[0] = 0;
 397     counters[1] = 0;
 398     counters[2] = 0;
 399     counters[3] = 0;
 400     counters[4] = 0;
 401     counters[5] = 0;
 402     counters[6] = 0;
 403     counters[7] = 0;
 404
 405     if (leftChar) {
 406       recordPatternInReverse(row, pattern.getStartEnd()[0], counters);
 407     } else {
 408       recordPattern(row, pattern.getStartEnd()[1] + 1, counters);
 409       // reverse it
 410       for (int i = 0, j = counters.length - 1; i < j; i++, j--) {
 411         int temp = counters[i];
 412         counters[i] = counters[j];
 413         counters[j] = temp;
 414       }
 415     }//counters[] has the pixels of the module
 416
 417     int numModules = 17; //left and right data characters have all the same length
 418     float elementWidth = (float) count(counters) / (float) numModules;
 419
 420     int[] oddCounts = this.oddCounts;
 421     int[] evenCounts = this.evenCounts;
 422     float[] oddRoundingErrors = this.oddRoundingErrors;
 423     float[] evenRoundingErrors = this.evenRoundingErrors;
 424
 425     for (int i = 0; i < counters.length; i++) {
 426       float value = 1.0f * counters[i] / elementWidth;
 427       int count = (int) (value + 0.5f); // Round
 428       if (count < 1) {
 429         count = 1;
 430       } else if (count > 8) {
 431         count = 8;
 432       }
 433       int offset = i >> 1;
 434       if ((i & 0x01) == 0) {
 435         oddCounts[offset] = count;
 436         oddRoundingErrors[offset] = value - count;
 437       } else {
 438         evenCounts[offset] = count;
 439         evenRoundingErrors[offset] = value - count;
 440       }
 441     }
 442
 443     adjustOddEvenCounts(numModules);
 444
 445     int weightRowNumber = 4 * pattern.getValue() + (isOddPattern?0:2) + (leftChar?0:1) - 1;
 446
 447     int oddSum = 0;
 448     int oddChecksumPortion = 0;
 449     for (int i = oddCounts.length - 1; i >= 0; i--) {
 450       if(isNotA1left(pattern, isOddPattern, leftChar)){
 451         int weight = WEIGHTS[weightRowNumber][2 * i];
 452         oddChecksumPortion += oddCounts[i] * weight;
 453       }
 454       oddSum += oddCounts[i];
 455     }
 456     int evenChecksumPortion = 0;
 457     int evenSum = 0;
 458     for (int i = evenCounts.length - 1; i >= 0; i--) {
 459       if(isNotA1left(pattern, isOddPattern, leftChar)){
 460         int weight = WEIGHTS[weightRowNumber][2 * i + 1];
 461         evenChecksumPortion += evenCounts[i] * weight;
 462       }
 463       evenSum += evenCounts[i];
 464     }
 465     int checksumPortion = oddChecksumPortion + evenChecksumPortion;
 466
 467     if ((oddSum & 0x01) != 0 || oddSum > 13 || oddSum < 4) {
 468       throw NotFoundException.getNotFoundInstance();
 469     }
 470
 471     int group = (13 - oddSum) / 2;
 472     int oddWidest = SYMBOL_WIDEST[group];
 473     int evenWidest = 9 - oddWidest;
 474     int vOdd = RSSUtils.getRSSvalue(oddCounts, oddWidest, true);
 475     int vEven = RSSUtils.getRSSvalue(evenCounts, evenWidest, false);
 476     int tEven = EVEN_TOTAL_SUBSET[group];
 477     int gSum = GSUM[group];
 478     int value = vOdd * tEven + vEven + gSum;
 479
 480     return new DataCharacter(value, checksumPortion);
 481   }
 482
 483   private static boolean isNotA1left(FinderPattern pattern, boolean isOddPattern, boolean leftChar) {
 484     // A1: pattern.getValue is 0 (A), and it's an oddPattern, and it is a left char
 485     return !(pattern.getValue() == 0 && isOddPattern && leftChar);
 486   }
 487
 488   private void adjustOddEvenCounts(int numModules) throws NotFoundException {
 489
 490     int oddSum = count(this.oddCounts);
 491     int evenSum = count(this.evenCounts);
 492     int mismatch = oddSum + evenSum - numModules;
 493     boolean oddParityBad = (oddSum & 0x01) == 1;
 494     boolean evenParityBad = (evenSum & 0x01) == 0;
 495
 496     boolean incrementOdd = false;
 497     boolean decrementOdd = false;
 498
 499     if (oddSum > 13) {
 500       decrementOdd = true;
 501     } else if (oddSum < 4) {
 502       incrementOdd = true;
 503     }
 504     boolean incrementEven = false;
 505     boolean decrementEven = false;
 506     if (evenSum > 13) {
 507       decrementEven = true;
 508     } else if (evenSum < 4) {
 509       incrementEven = true;
 510     }
 511
 512     if (mismatch == 1) {
 513       if (oddParityBad) {
 514         if (evenParityBad) {
 515           throw NotFoundException.getNotFoundInstance();
 516         }
 517         decrementOdd = true;
 518       } else {
 519         if (!evenParityBad) {
 520           throw NotFoundException.getNotFoundInstance();
 521         }
 522         decrementEven = true;
 523       }
 524     } else if (mismatch == -1) {
 525       if (oddParityBad) {
 526         if (evenParityBad) {
 527           throw NotFoundException.getNotFoundInstance();
 528         }
 529         incrementOdd = true;
 530       } else {
 531         if (!evenParityBad) {
 532           throw NotFoundException.getNotFoundInstance();
 533         }
 534         incrementEven = true;
 535       }
 536     } else if (mismatch == 0) {
 537       if (oddParityBad) {
 538         if (!evenParityBad) {
 539           throw NotFoundException.getNotFoundInstance();
 540         }
 541         // Both bad
 542         if (oddSum < evenSum) {
 543           incrementOdd = true;
 544           decrementEven = true;
 545         } else {
 546           decrementOdd = true;
 547           incrementEven = true;
 548         }
 549       } else {
 550         if (evenParityBad) {
 551           throw NotFoundException.getNotFoundInstance();
 552         }
 553         // Nothing to do!
 554       }
 555     } else {
 556       throw NotFoundException.getNotFoundInstance();
 557     }
 558
 559     if (incrementOdd) {
 560       if (decrementOdd) {
 561         throw NotFoundException.getNotFoundInstance();
 562       }
 563       increment(this.oddCounts, this.oddRoundingErrors);
 564     }
 565     if (decrementOdd) {
 566       decrement(this.oddCounts, this.oddRoundingErrors);
 567     }
 568     if (incrementEven) {
 569       if (decrementEven) {
 570         throw NotFoundException.getNotFoundInstance();
 571       }
 572       increment(this.evenCounts, this.oddRoundingErrors);
 573     }
 574     if (decrementEven) {
 575       decrement(this.evenCounts, this.evenRoundingErrors);
 576     }
 577   }
 578 }