Ref<Result> Code93Reader::decodeRow(int rowNumber, Ref<BitArray> row, zxing::DecodeHints /*hints*/) {
  Range start (findAsteriskPattern(row));
  // Read off white space    
  int nextStart = row->getNextSet(start[1]);
  int end = row->getSize();

  vector<int>& theCounters (counters);
  { // Arrays.fill(counters, 0);
    int size = theCounters.size();
    theCounters.resize(0);
    theCounters.resize(size); }
  string& result (decodeRowResult);
  result.clear();

  char decodedChar;
  int lastStart;
  do {
    recordPattern(row, nextStart, theCounters);
    int pattern = toPattern(theCounters);
    if (pattern < 0) {
      throw NotFoundException();
    }
    decodedChar = patternToChar(pattern);
    result.append(1, decodedChar);
    lastStart = nextStart;
    for(int i=0, e=theCounters.size(); i < e; ++i) {
      nextStart += theCounters[i];
    }
    // Read off white space
    nextStart = row->getNextSet(nextStart);
  } while (decodedChar != '*');
  result.resize(result.length() - 1); // remove asterisk

  // Look for whitespace after pattern:
  int lastPatternSize = 0;
  for (int i = 0, e = theCounters.size(); i < e; i++) {
    lastPatternSize += theCounters[i];
  }
  
  // Should be at least one more black module
  if (nextStart == end || !row->get(nextStart)) {
    throw NotFoundException();
  }

  if (result.length() < 2) {
    // false positive -- need at least 2 checksum digits
    throw NotFoundException();
  }

  checkChecksums(result);
  // Remove checksum digits
  result.resize(result.length() - 2);

  Ref<String> resultString = decodeExtended(result);

  float left = (float) (start[1] + start[0]) / 2.0f;
  float right = lastStart + lastPatternSize / 2.0f;

  ArrayRef< Ref<ResultPoint> > resultPoints (2);
  resultPoints[0] = 
    Ref<OneDResultPoint>(new OneDResultPoint(left, (float) rowNumber));
  resultPoints[1] =
    Ref<OneDResultPoint>(new OneDResultPoint(right, (float) rowNumber));
  
  return Ref<Result>(new Result(
                       resultString,
                       ArrayRef<byte>(),
                       resultPoints,
                       BarcodeFormat::CODE_93));
}

CharacterSetECI* CharacterSetECI::getCharacterSetECIByValue(int value) {
  if (value < 0 || value >= 900) {
    std::ostringstream oss;
    oss << "Bad ECI value: " << value;
    throw IllegalArgumentException(oss.str().c_str());
  }
  return VALUE_TO_ECI[value];
}

/**
 * Skip all whitespace until we get to the first black line.
 *
 * @param row row of black/white values to search
 * @return index of the first black line.
 * @throws ReaderException Throws exception if no black lines are found in the row
 */
int ITFReader::skipWhiteSpace(Ref<BitArray> row) {
	int width = row->getSize();
	int endStart = row->getNextSet(0);
	if (endStart == width) {
		throw NotFoundException();
	}
	return endStart;
}

char Code93Reader::patternToChar(int pattern)  {
  for (int i = 0; i < CHARACTER_ENCODINGS_LENGTH; i++) {
    if (CHARACTER_ENCODINGS[i] == pattern) {
      return ALPHABET[i];
    }
  }
  throw NotFoundException();
}

vector<Ref<GenericGFPoly> > ReedSolomonDecoder::runEuclideanAlgorithm(Ref<GenericGFPoly> a,
                                                                      Ref<GenericGFPoly> b,
                                                                      int R) {
  // Assume a's degree is >= b's
  if (a->getDegree() < b->getDegree()) {
    Ref<GenericGFPoly> tmp = a;
    a = b;
    b = tmp;
  }

  Ref<GenericGFPoly> rLast(a);
  Ref<GenericGFPoly> r(b);
  Ref<GenericGFPoly> tLast(field->getZero());
  Ref<GenericGFPoly> t(field->getOne());

  // Run Euclidean algorithm until r's degree is less than R/2
  while (r->getDegree() >= R / 2) {
    Ref<GenericGFPoly> rLastLast(rLast);
    Ref<GenericGFPoly> tLastLast(tLast);
    rLast = r;
    tLast = t;

    // Divide rLastLast by rLast, with quotient q and remainder r
    if (rLast->isZero()) {
      // Oops, Euclidean algorithm already terminated?
      throw ReedSolomonException("r_{i-1} was zero");
    }
    r = rLastLast;
    Ref<GenericGFPoly> q = field->getZero();
    int denominatorLeadingTerm = rLast->getCoefficient(rLast->getDegree());
    int dltInverse = field->inverse(denominatorLeadingTerm);
    while (r->getDegree() >= rLast->getDegree() && !r->isZero()) {
      int degreeDiff = r->getDegree() - rLast->getDegree();
      int scale = field->multiply(r->getCoefficient(r->getDegree()), dltInverse);
      q = q->addOrSubtract(field->buildMonomial(degreeDiff, scale));
      r = r->addOrSubtract(rLast->multiplyByMonomial(degreeDiff, scale));
    }

    t = q->multiply(tLast)->addOrSubtract(tLastLast);

    if (r->getDegree() >= rLast->getDegree()) {
      throw IllegalStateException("Division algorithm failed to reduce polynomial?");
    }
  }

  int sigmaTildeAtZero = t->getCoefficient(0);
  if (sigmaTildeAtZero == 0) {
    throw ReedSolomonException("sigmaTilde(0) was zero");
  }

  int inverse = field->inverse(sigmaTildeAtZero);
  Ref<GenericGFPoly> sigma(t->multiply(inverse));
  Ref<GenericGFPoly> omega(r->multiply(inverse));
  vector<Ref<GenericGFPoly> > result(2);
  result[0] = sigma;
  result[1] = omega;
  return result;
}

ECI* ECI::getECIByValue(int value) {
  if (value < 0 || value > 999999) {
    throw IllegalArgumentException("Bad ECI value: " + value);
  }
  if (value < 900) { // Character set ECIs use 000000 - 000899
    return CharacterSetECI::getCharacterSetECIByValue(value);
  }
  return 0;
}

Point LinesSampler::intersection(Line a, Line b) {
  float dxa = a.start.x - a.end.x;
  float dxb = b.start.x - b.end.x;
  float dya = a.start.y - a.end.y;
  float dyb = b.start.y - b.end.y;

  float p = a.start.x * a.end.y - a.start.y * a.end.x;
  float q = b.start.x * b.end.y - b.start.y * b.end.x;
  float denom = dxa * dyb - dya * dxb;
  if(abs(denom) < 1e-12)  // Lines don't intersect (replaces "denom == 0")
    return Point(std::numeric_limits<float>::infinity(),
                 std::numeric_limits<float>::infinity());

  float x = (p * dxb - dxa * q) / denom;
  float y = (p * dyb - dya * q) / denom;

  return Point(x, y);
}

ECI* ECI::getECIByValue(int value) {
  if (value < 0 || value > 999999) {
    std::ostringstream oss;
    oss << "Bad ECI value: " << value;
    throw IllegalArgumentException(oss.str().c_str());
  }
  if (value < 900) { // Character set ECIs use 000000 - 000899
    return CharacterSetECI::getCharacterSetECIByValue(value);
  }
  return 0;
}

Ref<Result> UPCEANReader::decodeRow(int rowNumber,
                                    Ref<BitArray> row,
                                    Range const& startGuardRange) {
  string& result = decodeRowStringBuffer;
  result.clear();
  int endStart = decodeMiddle(row, startGuardRange, result);

  Range endRange = decodeEnd(row, endStart);

  // Make sure there is a quiet zone at least as big as the end pattern after the barcode.
  // The spec might want more whitespace, but in practice this is the maximum we can count on.

  int end = endRange[1];
  int quietEnd = end + (end - endRange[0]);
  if (quietEnd >= row->getSize() || !row->isRange(end, quietEnd, false)) {
    throw NotFoundException();
  }

  // UPC/EAN should never be less than 8 chars anyway
  if (result.length() < 8) {
    throw FormatException();
  }

  Ref<String> resultString (new String(result));
  if (!checkChecksum(resultString)) {
    throw ChecksumException();
  }
  
  float left = (float) (startGuardRange[1] + startGuardRange[0]) / 2.0f;
  float right = (float) (endRange[1] + endRange[0]) / 2.0f;
  BarcodeFormat format = getBarcodeFormat();
  ArrayRef< Ref<ResultPoint> > resultPoints(2);
  resultPoints[0] = Ref<ResultPoint>(new OneDResultPoint(left, (float) rowNumber));
  resultPoints[1] = Ref<ResultPoint>(new OneDResultPoint(right, (float) rowNumber));
  Ref<Result> decodeResult (new Result(resultString, ArrayRef<char>(), resultPoints, format));
  // Java extension and man stuff
  return decodeResult;
}

/**
 * The start & end patterns must be pre/post fixed by a quiet zone. This
 * zone must be at least 10 times the width of a narrow line.  Scan back until
 * we either get to the start of the barcode or match the necessary number of
 * quiet zone pixels.
 *
 * Note: Its assumed the row is reversed when using this method to find
 * quiet zone after the end pattern.
 *
 * ref: http://www.barcode-1.net/i25code.html
 *
 * @param row bit array representing the scanned barcode.
 * @param startPattern index into row of the start or end pattern.
 * @throws ReaderException if the quiet zone cannot be found, a ReaderException is thrown.
 */
void ITFReader::validateQuietZone(Ref<BitArray> row, int startPattern) {
	int quietCount = this->narrowLineWidth * 10; // expect to find this many pixels of quiet zone

	for (int i = startPattern - 1; quietCount > 0 && i >= 0; i--) {
		if (row->get(i)) {
			break;
		}
		quietCount--;
	}
	if (quietCount != 0) {
		// Unable to find the necessary number of quiet zone pixels.
		throw NotFoundException();
	}
}

void Code93Reader::checkOneChecksum(string const& result,
                                    int checkPosition,
                                    int weightMax) {
  int weight = 1;
  int total = 0;
  for (int i = checkPosition - 1; i >= 0; i--) {
    total += weight * ALPHABET_STRING.find_first_of(result[i]);
    if (++weight > weightMax) {
      weight = 1;
    }
  }
  if (result[checkPosition] != ALPHABET[total % 47]) {
    throw ChecksumException();
  }
}

int CodaBarReader::findStartPattern() {
  for (int i = 1; i < counterLength; i += 2) {
    int charOffset = toNarrowWidePattern(i);
    if (charOffset != -1 && arrayContains(STARTEND_ENCODING, ALPHABET[charOffset])) {
      // Look for whitespace before start pattern, >= 50% of width of start pattern
      // We make an exception if the whitespace is the first element.
      int patternSize = 0;
      for (int j = i; j < i + 7; j++) {
        patternSize += counters[j];
      }
      if (i == 1 || counters[i-1] >= patternSize / 2) {
        return i;
      }
    }
  }
  throw NotFoundException();
}

UPCEANReader::Range UPCEANReader::findGuardPattern(Ref<BitArray> row,
                                                   int rowOffset,
                                                   bool whiteFirst,
                                                   vector<int> const& pattern,
                                                   vector<int>& counters) {
  // cerr << "fGP " << rowOffset  << " " << whiteFirst << endl;
  if (false) {
    for(int i=0; i < (int)pattern.size(); ++i) {
      std::cerr << pattern[i];
    }
    std::cerr << std::endl;
  }
  int patternLength = (int)pattern.size();
  int width = row->getSize();
  bool isWhite = whiteFirst;
  rowOffset = whiteFirst ? row->getNextUnset(rowOffset) : row->getNextSet(rowOffset);
  int counterPosition = 0;
  int patternStart = rowOffset;
  for (int x = rowOffset; x < width; x++) {
    // std::cerr << "rg " << x << " " << row->get(x) << std::endl;
    if (row->get(x) ^ isWhite) {
      counters[counterPosition]++;
    } else {
      if (counterPosition == patternLength - 1) {
        if (patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE) < MAX_AVG_VARIANCE) {
          return Range(patternStart, x);
        }
        patternStart += counters[0] + counters[1];
        for (int y = 2; y < patternLength; y++) {
          counters[y - 2] = counters[y];
        }
        counters[patternLength - 2] = 0;
        counters[patternLength - 1] = 0;
        counterPosition--;
      } else {
        counterPosition++;
      }
      counters[counterPosition] = 1;
      isWhite = !isWhite;
    }
  }
  throw NotFoundException();
}

/**
 * Attempts to decode a sequence of ITF black/white lines into single
 * digit.
 *
 * @param counters the counts of runs of observed black/white/black/... values
 * @return The decoded digit
 * @throws ReaderException if digit cannot be decoded
 */
int ITFReader::decodeDigit(vector<int>& counters){

  int bestVariance = MAX_AVG_VARIANCE; // worst variance we'll accept
  int bestMatch = -1;
  int max = sizeof(PATTERNS)/sizeof(PATTERNS[0]);
  for (int i = 0; i < max; i++) {
    int const* pattern = PATTERNS[i];
    int variance = patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE);
    if (variance < bestVariance) {
      bestVariance = variance;
      bestMatch = i;
    }
  }
  if (bestMatch >= 0) {
    return bestMatch;
  } else {
    throw NotFoundException();
  }
}

/**
 * Records the size of all runs of white and black pixels, starting with white.
 * This is just like recordPattern, except it records all the counters, and
 * uses our builtin "counters" member for storage.
 * @param row row to count from
 */
void CodaBarReader::setCounters(Ref<BitArray> row)  {
  counterLength = 0;
  // Start from the first white bit.
  int i = row->getNextUnset(0);
  int end = row->getSize();
  if (i >= end) {
    throw NotFoundException();
  }
  bool isWhite = true;
  int count = 0;
  for (; i < end; i++) {
    if (row->get(i) ^ isWhite) { // that is, exactly one is true
      count++;
    } else {
      counterAppend(count);
      count = 1;
      isWhite = !isWhite;
    }
  }
  counterAppend(count);
}

Ref<Result> ITFReader::decodeRow(int rowNumber, Ref<BitArray> row) {
	// Find out where the Middle section (payload) starts & ends

	Range startRange = decodeStart(row);
	Range endRange = decodeEnd(row);

	std::string result;
	decodeMiddle(row, startRange[1], endRange[0], result);
	Ref<String> resultString(new String(result));

	ArrayRef<int> allowedLengths;
	// Java hints stuff missing
	if (!allowedLengths) {
		allowedLengths = DEFAULT_ALLOWED_LENGTHS;
	}

	// To avoid false positives with 2D barcodes (and other patterns), make
	// an assumption that the decoded string must be 6, 10 or 14 digits.
	int length = resultString->size();
	bool lengthOK = false;
	for (int i = 0, e = allowedLengths->size(); i < e; i++) {
		if (length == allowedLengths[i]) {
			lengthOK = true;
			break;
		}
	}

	if (!lengthOK) {
		throw FormatException();
	}

	ArrayRef<Ref<ResultPoint> > resultPoints(2);
	resultPoints[0] = Ref<OneDResultPoint>(
			new OneDResultPoint(float(startRange[1]), float(rowNumber)));
	resultPoints[1] = Ref<OneDResultPoint>(
			new OneDResultPoint(float(endRange[0]), float(rowNumber)));
	return Ref<Result>(
			new Result(resultString, ArrayRef<char>(), resultPoints,
					BarcodeFormat::ITF));
}

int UPCEANReader::decodeDigit(Ref<BitArray> row,
                              vector<int> & counters,
                              int rowOffset,
                              vector<int const*> const& patterns) {
  recordPattern(row, rowOffset, counters);
  int bestVariance = MAX_AVG_VARIANCE; // worst variance we'll accept
  int bestMatch = -1;
  int max = (int)patterns.size();
  for (int i = 0; i < max; i++) {
    int const* pattern (patterns[i]);
    int variance = patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE);
    if (variance < bestVariance) {
      bestVariance = variance;
      bestMatch = i;
    }
  }
  if (bestMatch >= 0) {
    return bestMatch;
  } else {
    throw NotFoundException();
  }
}

Code93Reader::Range Code93Reader::findAsteriskPattern(Ref<BitArray> row)  {
  int width = row->getSize();
  int rowOffset = row->getNextSet(0);

  { // Arrays.fill(counters, 0);
    int size = counters.size();
    counters.resize(0);
    counters.resize(size); }
  vector<int>& theCounters (counters);

  int patternStart = rowOffset;
  bool isWhite = false;
  int patternLength = theCounters.size();

  int counterPosition = 0;
  for (int i = rowOffset; i < width; i++) {
    if (row->get(i) ^ isWhite) {
      theCounters[counterPosition]++;
    } else {
      if (counterPosition == patternLength - 1) {
        if (toPattern(theCounters) == ASTERISK_ENCODING) {
          return Range(patternStart, i);
        }
        patternStart += theCounters[0] + theCounters[1];
        for (int y = 2; y < patternLength; y++) {
          theCounters[y - 2] = theCounters[y];
        }
        theCounters[patternLength - 2] = 0;
        theCounters[patternLength - 1] = 0;
        counterPosition--;
      } else {
        counterPosition++;
      }
      theCounters[counterPosition] = 1;
      isWhite = !isWhite;
    }
  }
  throw NotFoundException();
}

/**
 * @param row       row of black/white values to search
 * @param rowOffset position to start search
 * @param pattern   pattern of counts of number of black and white pixels that are
 *                  being searched for as a pattern
 * @return start/end horizontal offset of guard pattern, as an array of two
 *         ints
 * @throws ReaderException if pattern is not found
 */
ITFReader::Range ITFReader::findGuardPattern(Ref<BitArray> row, int rowOffset,
		vector<int> const& pattern) {
	// TODO: This is very similar to implementation in UPCEANReader. Consider if they can be
	// merged to a single method.
	int patternLength = pattern.size();
	vector<int> counters(patternLength);
	int width = row->getSize();
	bool isWhite = false;

	int counterPosition = 0;
	int patternStart = rowOffset;
	for (int x = rowOffset; x < width; x++) {
		if (row->get(x) ^ isWhite) {
			counters[counterPosition]++;
		} else {
			if (counterPosition == patternLength - 1) {
				if (patternMatchVariance(counters, &pattern[0],
						MAX_INDIVIDUAL_VARIANCE) < MAX_AVG_VARIANCE) {
					return Range(patternStart, x);
				}
				patternStart += counters[0] + counters[1];
				for (int y = 2; y < patternLength; y++) {
					counters[y - 2] = counters[y];
				}
				counters[patternLength - 2] = 0;
				counters[patternLength - 1] = 0;
				counterPosition--;
			} else {
				counterPosition++;
			}
			counters[counterPosition] = 1;
			isWhite = !isWhite;
		}
	}
	throw NotFoundException();
}

vector<vector<Ref<FinderPattern> > > MultiFinderPatternFinder::selectBestPatterns(){
  vector<Ref<FinderPattern> > possibleCenters = possibleCenters_;
  
  int size = possibleCenters.size();

  if (size < 3) {
    // Couldn't find enough finder patterns
    throw ReaderException("No code detected");
  }
  
  vector<vector<Ref<FinderPattern> > > results;

  /*
   * Begin HE modifications to safely detect multiple codes of equal size
   */
  if (size == 3) {
    results.push_back(possibleCenters_);
    return results;
  }

  // Sort by estimated module size to speed up the upcoming checks
  //TODO do a sort based on module size
  sort(possibleCenters.begin(), possibleCenters.end(), compareModuleSize);

  /*
   * Now lets start: build a list of tuples of three finder locations that
   *  - feature similar module sizes
   *  - are placed in a distance so the estimated module count is within the QR specification
   *  - have similar distance between upper left/right and left top/bottom finder patterns
   *  - form a triangle with 90° angle (checked by comparing top right/bottom left distance
   *    with pythagoras)
   *
   * Note: we allow each point to be used for more than one code region: this might seem
   * counterintuitive at first, but the performance penalty is not that big. At this point,
   * we cannot make a good quality decision whether the three finders actually represent
   * a QR code, or are just by chance layouted so it looks like there might be a QR code there.
   * So, if the layout seems right, lets have the decoder try to decode.
   */

  for (int i1 = 0; i1 < (size - 2); i1++) {
    Ref<FinderPattern> p1 = possibleCenters[i1];
    for (int i2 = i1 + 1; i2 < (size - 1); i2++) {
      Ref<FinderPattern> p2 = possibleCenters[i2];
      // Compare the expected module sizes; if they are really off, skip
      float vModSize12 = (p1->getEstimatedModuleSize() - p2->getEstimatedModuleSize()) / min(p1->getEstimatedModuleSize(), p2->getEstimatedModuleSize());
      float vModSize12A = abs(p1->getEstimatedModuleSize() - p2->getEstimatedModuleSize());
      if (vModSize12A > DIFF_MODSIZE_CUTOFF && vModSize12 >= DIFF_MODSIZE_CUTOFF_PERCENT) {
        // break, since elements are ordered by the module size deviation there cannot be
        // any more interesting elements for the given p1.
        break;
      }
      for (int i3 = i2 + 1; i3 < size; i3++) {
        Ref<FinderPattern> p3 = possibleCenters[i3];
        // Compare the expected module sizes; if they are really off, skip
        float vModSize23 = (p2->getEstimatedModuleSize() - p3->getEstimatedModuleSize()) / min(p2->getEstimatedModuleSize(), p3->getEstimatedModuleSize());
        float vModSize23A = abs(p2->getEstimatedModuleSize() - p3->getEstimatedModuleSize());
        if (vModSize23A > DIFF_MODSIZE_CUTOFF && vModSize23 >= DIFF_MODSIZE_CUTOFF_PERCENT) {
          // break, since elements are ordered by the module size deviation there cannot be
          // any more interesting elements for the given p1.
          break;
        }
        vector<Ref<FinderPattern> > test;
        test.push_back(p1);
        test.push_back(p2);
        test.push_back(p3);
        test = FinderPatternFinder::orderBestPatterns(test);
        // Calculate the distances: a = topleft-bottomleft, b=topleft-topright, c = diagonal
        Ref<FinderPatternInfo> info = Ref<FinderPatternInfo>(new FinderPatternInfo(test));
        float dA = FinderPatternFinder::distance(info->getTopLeft(), info->getBottomLeft());
        float dC = FinderPatternFinder::distance(info->getTopRight(), info->getBottomLeft());
        float dB = FinderPatternFinder::distance(info->getTopLeft(), info->getTopRight());
        // Check the sizes
        float estimatedModuleCount = (dA + dB) / (p1->getEstimatedModuleSize() * 2.0f);
        if (estimatedModuleCount > MAX_MODULE_COUNT_PER_EDGE || estimatedModuleCount < MIN_MODULE_COUNT_PER_EDGE) {
          continue;
        }
        // Calculate the difference of the edge lengths in percent
        float vABBC = abs((dA - dB) / min(dA, dB));
        if (vABBC >= 0.1f) {
          continue;
        }
        // Calculate the diagonal length by assuming a 90° angle at topleft
        float dCpy = (float) sqrt(dA * dA + dB * dB);
        // Compare to the real distance in %
        float vPyC = abs((dC - dCpy) / min(dC, dCpy));
        if (vPyC >= 0.1f) {
          continue;
        }
        // All tests passed!
        results.push_back(test);
      } // end iterate p3
    } // end iterate p2
  } // end iterate p1
  if (results.empty()){
    // Nothing found!
    throw ReaderException("No code detected");    
  }
  return results;
}