--- /dev/null
+/*
+ * Copyright (C) 2010 ZXing authors
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/*
+ * These authors would like to acknowledge the Spanish Ministry of Industry,
+ * Tourism and Trade, for the support in the project TSI020301-2008-2
+ * "PIRAmIDE: Personalizable Interactions with Resources on AmI-enabled
+ * Mobile Dynamic Environments", led by Treelogic
+ * ( http://www.treelogic.com/ ):
+ *
+ * http://www.piramidepse.com/
+ */
+
+package com.google.zxing.oned.rss.expanded;
+
+import java.util.Hashtable;
+import java.util.Vector;
+
+import com.google.zxing.BarcodeFormat;
+import com.google.zxing.NotFoundException;
+import com.google.zxing.Result;
+import com.google.zxing.ResultPoint;
+import com.google.zxing.common.BitArray;
+import com.google.zxing.oned.rss.AbstractRSSReader;
+import com.google.zxing.oned.rss.DataCharacter;
+import com.google.zxing.oned.rss.FinderPattern;
+import com.google.zxing.oned.rss.RSSUtils;
+import com.google.zxing.oned.rss.expanded.decoders.AbstractExpandedDecoder;
+
+/**
+ * @author Pablo Orduña, University of Deusto (pablo.orduna@deusto.es)
+ * @author Eduardo Castillejo, University of Deusto (eduardo.castillejo@deusto.es)
+ */
+public final class RSSExpandedReader extends AbstractRSSReader{
+
+ private static final int[] SYMBOL_WIDEST = {7, 5, 4, 3, 1};
+ private static final int[] EVEN_TOTAL_SUBSET = {4, 20, 52, 104, 204};
+ private static final int[] GSUM = {0, 348, 1388, 2948, 3988};
+
+ private static final int[][] FINDER_PATTERNS = {
+ {1,8,4,1}, // A
+ {3,6,4,1}, // B
+ {3,4,6,1}, // C
+ {3,2,8,1}, // D
+ {2,6,5,1}, // E
+ {2,2,9,1} // F
+ };
+
+ private static final int[][] WEIGHTS = {
+ { 1, 3, 9, 27, 81, 32, 96, 77},
+ { 20, 60, 180, 118, 143, 7, 21, 63},
+ {189, 145, 13, 39, 117, 140, 209, 205},
+ {193, 157, 49, 147, 19, 57, 171, 91},
+ { 62, 186, 136, 197, 169, 85, 44, 132},
+ {185, 133, 188, 142, 4, 12, 36, 108},
+ {113, 128, 173, 97, 80, 29, 87, 50},
+ {150, 28, 84, 41, 123, 158, 52, 156},
+ { 46, 138, 203, 187, 139, 206, 196, 166},
+ { 76, 17, 51, 153, 37, 111, 122, 155},
+ { 43, 129, 176, 106, 107, 110, 119, 146},
+ { 16, 48, 144, 10, 30, 90, 59, 177},
+ {109, 116, 137, 200, 178, 112, 125, 164},
+ { 70, 210, 208, 202, 184, 130, 179, 115},
+ {134, 191, 151, 31, 93, 68, 204, 190},
+ {148, 22, 66, 198, 172, 94, 71, 2},
+ { 6, 18, 54, 162, 64, 192,154, 40},
+ {120, 149, 25, 75, 14, 42,126, 167},
+ { 79, 26, 78, 23, 69, 207,199, 175},
+ {103, 98, 83, 38, 114, 131, 182, 124},
+ {161, 61, 183, 127, 170, 88, 53, 159},
+ { 55, 165, 73, 8, 24, 72, 5, 15},
+ { 45, 135, 194, 160, 58, 174, 100, 89}
+ };
+
+ private static final int FINDER_PAT_A = 0;
+ private static final int FINDER_PAT_B = 1;
+ private static final int FINDER_PAT_C = 2;
+ private static final int FINDER_PAT_D = 3;
+ private static final int FINDER_PAT_E = 4;
+ private static final int FINDER_PAT_F = 5;
+
+ private static final int [][] FINDER_PATTERN_SEQUENCES = {
+ { FINDER_PAT_A, FINDER_PAT_A },
+ { FINDER_PAT_A, FINDER_PAT_B, FINDER_PAT_B },
+ { FINDER_PAT_A, FINDER_PAT_C, FINDER_PAT_B, FINDER_PAT_D },
+ { FINDER_PAT_A, FINDER_PAT_E, FINDER_PAT_B, FINDER_PAT_D, FINDER_PAT_C },
+ { FINDER_PAT_A, FINDER_PAT_E, FINDER_PAT_B, FINDER_PAT_D, FINDER_PAT_D, FINDER_PAT_F },
+ { FINDER_PAT_A, FINDER_PAT_E, FINDER_PAT_B, FINDER_PAT_D, FINDER_PAT_E, FINDER_PAT_F, FINDER_PAT_F },
+ { FINDER_PAT_A, FINDER_PAT_A, FINDER_PAT_B, FINDER_PAT_B, FINDER_PAT_C, FINDER_PAT_C, FINDER_PAT_D, FINDER_PAT_D },
+ { 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 },
+ { 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 },
+ { 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 },
+ };
+
+ private static final int LONGEST_SEQUENCE_SIZE = FINDER_PATTERN_SEQUENCES[FINDER_PATTERN_SEQUENCES.length - 1].length;
+
+ private static final int MAX_PAIRS = 11;
+ private final Vector pairs = new Vector(MAX_PAIRS);
+ private final int [] startEnd = new int[2];
+ private final int [] currentSequence = new int[LONGEST_SEQUENCE_SIZE];
+
+ public Result decodeRow(int rowNumber, BitArray row, Hashtable hints) throws NotFoundException {
+ this.reset();
+ decodeRow2pairs(rowNumber, row);
+ return constructResult(this.pairs);
+ }
+
+ public void reset() {
+ this.pairs.setSize(0);
+ }
+
+ // Not private for testing
+ Vector decodeRow2pairs(int rowNumber, BitArray row) throws NotFoundException {
+ while(true){
+ ExpandedPair nextPair = retrieveNextPair(row, this.pairs, rowNumber);
+ this.pairs.add(nextPair);
+
+ if(nextPair.mayBeLast()){
+ if(checkChecksum()) {
+ return this.pairs;
+ }
+ if(nextPair.mustBeLast()) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ }
+ }
+ }
+
+ private static Result constructResult(Vector pairs) throws NotFoundException{
+ BitArray binary = BitArrayBuilder.buildBitArray(pairs);
+
+ AbstractExpandedDecoder decoder = AbstractExpandedDecoder.createDecoder(binary);
+ String resultingString = decoder.parseInformation();
+
+ ResultPoint [] firstPoints = ((ExpandedPair)pairs.get(0)).getFinderPattern().getResultPoints();
+ ResultPoint [] lastPoints = ((ExpandedPair)pairs.lastElement()).getFinderPattern().getResultPoints();
+
+ return new Result(
+ resultingString,
+ null,
+ new ResultPoint[]{firstPoints[0], firstPoints[1], lastPoints[0], lastPoints[1]},
+ BarcodeFormat.RSS_EXPANDED
+ );
+ }
+
+ private boolean checkChecksum(){
+ ExpandedPair firstPair = (ExpandedPair)this.pairs.get(0);
+ DataCharacter checkCharacter = firstPair.getLeftChar();
+ DataCharacter firstCharacter = firstPair.getRightChar();
+
+ int checksum = firstCharacter.getChecksumPortion();
+ int S = 2;
+
+ for(int i = 1; i < this.pairs.size(); ++i){
+ ExpandedPair currentPair = (ExpandedPair)this.pairs.get(i);
+ checksum += currentPair.getLeftChar().getChecksumPortion();
+ S++;
+ if(currentPair.getRightChar() != null){
+ checksum += currentPair.getRightChar().getChecksumPortion();
+ S++;
+ }
+ }
+
+ checksum %= 211;
+
+ int checkCharacterValue = 211 * (S - 4) + checksum;
+
+ return checkCharacterValue == checkCharacter.getValue();
+ }
+
+ private static int getNextSecondBar(BitArray row, int initialPos){
+ int currentPos = initialPos;
+ boolean current = row.get(currentPos);
+
+ while(currentPos < row.size && row.get(currentPos) == current) {
+ currentPos++;
+ }
+
+ current = !current;
+ while(currentPos < row.size && row.get(currentPos) == current) {
+ currentPos++;
+ }
+
+ return currentPos;
+ }
+
+ // not private for testing
+ ExpandedPair retrieveNextPair(BitArray row, Vector previousPairs, int rowNumber) throws NotFoundException{
+ boolean isOddPattern = previousPairs.size() % 2 == 0;
+
+ FinderPattern pattern;
+
+ boolean keepFinding = true;
+ int forcedOffset = -1;
+ do{
+ this.findNextPair(row, previousPairs, forcedOffset);
+ pattern = parseFoundFinderPattern(row, rowNumber, isOddPattern);
+ if(pattern == null){
+ forcedOffset = getNextSecondBar(row, this.startEnd[0]);
+ }else {
+ keepFinding = false;
+ }
+ }while(keepFinding);
+
+ boolean mayBeLast = checkPairSequence(previousPairs, pattern);
+
+ DataCharacter leftChar = this.decodeDataCharacter(row, pattern, isOddPattern, true);
+ DataCharacter rightChar;
+ try{
+ rightChar = this.decodeDataCharacter(row, pattern, isOddPattern, false);
+ }catch(NotFoundException nfe){
+ if(mayBeLast) {
+ rightChar = null;
+ } else {
+ throw nfe;
+ }
+ }
+
+ return new ExpandedPair(leftChar, rightChar, pattern, mayBeLast);
+ }
+
+ private boolean checkPairSequence(Vector previousPairs, FinderPattern pattern) throws NotFoundException{
+ int currentSequenceLength = previousPairs.size() + 1;
+ if(currentSequenceLength > this.currentSequence.length) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+
+ for(int pos = 0; pos < previousPairs.size(); ++pos) {
+ this.currentSequence[pos] = ((ExpandedPair) previousPairs.get(pos)).getFinderPattern().getValue();
+ }
+
+ this.currentSequence[currentSequenceLength - 1] = pattern.getValue();
+
+ for(int i = 0; i < FINDER_PATTERN_SEQUENCES.length; ++i){
+ int [] validSequence = FINDER_PATTERN_SEQUENCES[i];
+ if(validSequence.length >= currentSequenceLength){
+ boolean valid = true;
+ for(int pos = 0; pos < currentSequenceLength; ++pos) {
+ if (this.currentSequence[pos] != validSequence[pos]) {
+ valid = false;
+ break;
+ }
+ }
+
+ if(valid) {
+ return currentSequenceLength == validSequence.length;
+ }
+ }
+ }
+
+ throw NotFoundException.getNotFoundInstance();
+ }
+
+ private void findNextPair(BitArray row, Vector previousPairs, int forcedOffset) throws NotFoundException{
+ int[] counters = this.decodeFinderCounters;
+ counters[0] = 0;
+ counters[1] = 0;
+ counters[2] = 0;
+ counters[3] = 0;
+
+ int width = row.getSize();
+
+ int rowOffset;
+ if (forcedOffset >= 0) {
+ rowOffset = forcedOffset;
+ } else if (previousPairs.isEmpty()) {
+ rowOffset = 0;
+ } else{
+ ExpandedPair lastPair = ((ExpandedPair)previousPairs.lastElement());
+ rowOffset = lastPair.getFinderPattern().getStartEnd()[1];
+ }
+ boolean searchingEvenPair = previousPairs.size() % 2 != 0;
+
+ boolean isWhite = false;
+ while (rowOffset < width) {
+ isWhite = !row.get(rowOffset);
+ if (!isWhite) {
+ break;
+ }
+ rowOffset++;
+ }
+
+ int counterPosition = 0;
+ int patternStart = rowOffset;
+ for (int x = rowOffset; x < width; x++) {
+ boolean pixel = row.get(x);
+ if (pixel ^ isWhite) {
+ counters[counterPosition]++;
+ } else {
+ if (counterPosition == 3) {
+ if (searchingEvenPair) {
+ reverseCounters(counters);
+ }
+
+ if (isFinderPattern(counters)){
+ this.startEnd[0] = patternStart;
+ this.startEnd[1] = x;
+ return;
+ }
+
+ if (searchingEvenPair) {
+ reverseCounters(counters);
+ }
+
+ patternStart += counters[0] + counters[1];
+ counters[0] = counters[2];
+ counters[1] = counters[3];
+ counters[2] = 0;
+ counters[3] = 0;
+ counterPosition--;
+ } else {
+ counterPosition++;
+ }
+ counters[counterPosition] = 1;
+ isWhite = !isWhite;
+ }
+ }
+ throw NotFoundException.getNotFoundInstance();
+ }
+
+ private static void reverseCounters(int [] counters){
+ int length = counters.length;
+ for(int i = 0; i < length / 2; ++i){
+ int tmp = counters[i];
+ counters[i] = counters[length - i - 1];
+ counters[length - i - 1] = tmp;
+ }
+ }
+
+ private FinderPattern parseFoundFinderPattern(BitArray row, int rowNumber, boolean oddPattern) {
+ // Actually we found elements 2-5.
+ int firstCounter;
+ int start;
+ int end;
+
+ if(oddPattern){
+ // If pattern number is odd, we need to locate element 1 *before* the current block.
+
+ int firstElementStart = this.startEnd[0] - 1;
+ // Locate element 1
+ while (firstElementStart >= 0 && !row.get(firstElementStart)) {
+ firstElementStart--;
+ }
+
+ firstElementStart++;
+ firstCounter = this.startEnd[0] - firstElementStart;
+ start = firstElementStart;
+ end = this.startEnd[1];
+
+ }else{
+ // If pattern number is even, the pattern is reversed, so we need to locate element 1 *after* the current block.
+
+ start = this.startEnd[0];
+
+ int firstElementStart = this.startEnd[1] + 1;
+ while(row.get(firstElementStart) && firstElementStart < row.size) {
+ firstElementStart++;
+ }
+
+ end = firstElementStart;
+ firstCounter = end - this.startEnd[1];
+ }
+
+ // Make 'counters' hold 1-4
+ int [] counters = this.decodeFinderCounters;
+ for (int i = counters.length - 1; i > 0; i--) {
+ counters[i] = counters[i - 1];
+ }
+
+ counters[0] = firstCounter;
+ int value;
+ try {
+ value = parseFinderValue(counters, FINDER_PATTERNS);
+ } catch (NotFoundException nfe) {
+ return null;
+ }
+ return new FinderPattern(value, new int[] {start, end}, start, end, rowNumber);
+ }
+
+ DataCharacter decodeDataCharacter(BitArray row, FinderPattern pattern, boolean isOddPattern, boolean leftChar)
+ throws NotFoundException {
+ int[] counters = this.dataCharacterCounters;
+ counters[0] = 0;
+ counters[1] = 0;
+ counters[2] = 0;
+ counters[3] = 0;
+ counters[4] = 0;
+ counters[5] = 0;
+ counters[6] = 0;
+ counters[7] = 0;
+
+ if (leftChar) {
+ recordPatternInReverse(row, pattern.getStartEnd()[0], counters);
+ } else {
+ recordPattern(row, pattern.getStartEnd()[1] + 1, counters);
+ // reverse it
+ for (int i = 0, j = counters.length - 1; i < j; i++, j--) {
+ int temp = counters[i];
+ counters[i] = counters[j];
+ counters[j] = temp;
+ }
+ }//counters[] has the pixels of the module
+
+ int numModules = 17; //left and right data characters have all the same length
+ float elementWidth = (float) count(counters) / (float) numModules;
+
+ int[] oddCounts = this.oddCounts;
+ int[] evenCounts = this.evenCounts;
+ float[] oddRoundingErrors = this.oddRoundingErrors;
+ float[] evenRoundingErrors = this.evenRoundingErrors;
+
+ for (int i = 0; i < counters.length; i++) {
+ float value = 1.0f * counters[i] / elementWidth;
+ int count = (int) (value + 0.5f); // Round
+ if (count < 1) {
+ count = 1;
+ } else if (count > 8) {
+ count = 8;
+ }
+ int offset = i >> 1;
+ if ((i & 0x01) == 0) {
+ oddCounts[offset] = count;
+ oddRoundingErrors[offset] = value - count;
+ } else {
+ evenCounts[offset] = count;
+ evenRoundingErrors[offset] = value - count;
+ }
+ }
+
+ adjustOddEvenCounts(numModules);
+
+ int weightRowNumber = 4 * pattern.getValue() + (isOddPattern?0:2) + (leftChar?0:1) - 1;
+
+ int oddSum = 0;
+ int oddChecksumPortion = 0;
+ for (int i = oddCounts.length - 1; i >= 0; i--) {
+ if(isNotA1left(pattern, isOddPattern, leftChar)){
+ int weight = WEIGHTS[weightRowNumber][2 * i];
+ oddChecksumPortion += oddCounts[i] * weight;
+ }
+ oddSum += oddCounts[i];
+ }
+ int evenChecksumPortion = 0;
+ int evenSum = 0;
+ for (int i = evenCounts.length - 1; i >= 0; i--) {
+ if(isNotA1left(pattern, isOddPattern, leftChar)){
+ int weight = WEIGHTS[weightRowNumber][2 * i + 1];
+ evenChecksumPortion += evenCounts[i] * weight;
+ }
+ evenSum += evenCounts[i];
+ }
+ int checksumPortion = oddChecksumPortion + evenChecksumPortion;
+
+ if ((oddSum & 0x01) != 0 || oddSum > 13 || oddSum < 4) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+
+ int group = (13 - oddSum) / 2;
+ int oddWidest = SYMBOL_WIDEST[group];
+ int evenWidest = 9 - oddWidest;
+ int vOdd = RSSUtils.getRSSvalue(oddCounts, oddWidest, true);
+ int vEven = RSSUtils.getRSSvalue(evenCounts, evenWidest, false);
+ int tEven = EVEN_TOTAL_SUBSET[group];
+ int gSum = GSUM[group];
+ int value = vOdd * tEven + vEven + gSum;
+
+ return new DataCharacter(value, checksumPortion);
+ }
+
+ private static boolean isNotA1left(FinderPattern pattern, boolean isOddPattern, boolean leftChar) {
+ // A1: pattern.getValue is 0 (A), and it's an oddPattern, and it is a left char
+ return !(pattern.getValue() == 0 && isOddPattern && leftChar);
+ }
+
+ private void adjustOddEvenCounts(int numModules) throws NotFoundException {
+
+ int oddSum = count(this.oddCounts);
+ int evenSum = count(this.evenCounts);
+ int mismatch = oddSum + evenSum - numModules;
+ boolean oddParityBad = (oddSum & 0x01) == 1;
+ boolean evenParityBad = (evenSum & 0x01) == 0;
+
+ boolean incrementOdd = false;
+ boolean decrementOdd = false;
+
+ if (oddSum > 13) {
+ decrementOdd = true;
+ } else if (oddSum < 4) {
+ incrementOdd = true;
+ }
+ boolean incrementEven = false;
+ boolean decrementEven = false;
+ if (evenSum > 13) {
+ decrementEven = true;
+ } else if (evenSum < 4) {
+ incrementEven = true;
+ }
+
+ if (mismatch == 1) {
+ if (oddParityBad) {
+ if (evenParityBad) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ decrementOdd = true;
+ } else {
+ if (!evenParityBad) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ decrementEven = true;
+ }
+ } else if (mismatch == -1) {
+ if (oddParityBad) {
+ if (evenParityBad) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ incrementOdd = true;
+ } else {
+ if (!evenParityBad) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ incrementEven = true;
+ }
+ } else if (mismatch == 0) {
+ if (oddParityBad) {
+ if (!evenParityBad) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ // Both bad
+ if (oddSum < evenSum) {
+ incrementOdd = true;
+ decrementEven = true;
+ } else {
+ decrementOdd = true;
+ incrementEven = true;
+ }
+ } else {
+ if (evenParityBad) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ // Nothing to do!
+ }
+ } else {
+ throw NotFoundException.getNotFoundInstance();
+ }
+
+ if (incrementOdd) {
+ if (decrementOdd) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ increment(this.oddCounts, this.oddRoundingErrors);
+ }
+ if (decrementOdd) {
+ decrement(this.oddCounts, this.oddRoundingErrors);
+ }
+ if (incrementEven) {
+ if (decrementEven) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ increment(this.evenCounts, this.oddRoundingErrors);
+ }
+ if (decrementEven) {
+ decrement(this.evenCounts, this.evenRoundingErrors);
+ }
+ }
+}