zxing-cpp 0.5.1

/*
* Copyright 2016 Nu-book Inc.
* Copyright 2016 ZXing authors
* Copyright 2022 Axel Waggershauser
*/
// SPDX-License-Identifier: Apache-2.0

#include "AZDetector.h"

#include "AZDetectorResult.h"
#include "BitArray.h"
#include "BitMatrix.h"
#include "ConcentricFinder.h"
#include "GenericGF.h"
#include "GridSampler.h"
#include "LogMatrix.h"
#include "Pattern.h"
#include "ReedSolomonDecoder.h"
#include "ZXAlgorithms.h"

#include <algorithm>
#include <bit>
#include <ranges>
#include <optional>
#include <vector>

namespace ZXing::Aztec {

static bool IsAztecCenterPattern(const PatternView& view)
{
	// find min/max of all subsequent black/white pairs and check that they 'close together'
	auto m = view[0] + view[1];
	auto M = m;
	for (int i = 1; i < Size(view) - 1; ++i) {
		int v = view[i] + view[i + 1];
		UpdateMinMax(m, M, v);
	}
	return M <= m * 4 / 3 + 1 && view[-1] >= view[Size(view) / 2] - 2 && view[Size(view)] >= view[Size(view) / 2] - 2;
};

// specialized version of FindLeftGuard to find the '1,1,1,1,1,1,1' pattern of a compact Aztec center pattern
static PatternView FindAztecCenterPattern(const PatternView& view)
{
	constexpr int minSize = 8; // Aztec runes
	auto window = view.subView(0, 7);
	for (auto end = view.end() - minSize; window.data() < end; window.skipPair())
		if (IsAztecCenterPattern(window))
			return window;

	return {};
};

static int CheckSymmetricAztecCenterPattern(BitMatrixCursorI& cur, int range, bool updatePosition)
{
	range *= 2; // tilted symbols may have a larger vertical than horizontal range

	FastEdgeToEdgeCounter curFwd(cur), curBwd(cur.turnedBack());

	int centerFwd = curFwd.stepToNextEdge(range / 7);
	if (!centerFwd)
		return 0;
	int centerBwd = curBwd.stepToNextEdge(range / 7);
	if (!centerBwd)
		return 0;
	int center = centerFwd + centerBwd - 1; // -1 because the starting pixel is counted twice
	if (center > range / 7 || center < range / (4 * 7))
		return 0;

	int spread = center;
	int m = 0;
	int M = 0;
	for (auto c : {&curFwd, &curBwd}) {
		int lastS = center;
		for (int i = 0; i < 3; ++i) {
			int s = c->stepToNextEdge(range - spread);
			if (s == 0)
				return 0;
			int v = s + lastS;
			if (m == 0)
				m = M = v;
			else
				UpdateMinMax(m, M, v);
			if (M > m * 4 / 3 + 1)
				return 0;
			spread += s;
			lastS = s;
		}
	}

	if (updatePosition)
		cur.step(centerFwd - centerBwd);

	return spread;
}

static std::optional<ConcentricPattern> LocateAztecCenter(const BitMatrix& image, PointF center, int spreadH)
{
	auto cur = BitMatrixCursor(image, PointI(center), {});
	int minSpread = spreadH, maxSpread = 0;
	for (auto d : {PointI{0, 1}, {1, 0}, {1, 1}, {1, -1}}) {
		int spread = CheckSymmetricAztecCenterPattern(cur.setDirection(d), spreadH, d.x == 0);
		if (!spread)
			return {};
		UpdateMinMax(minSpread, maxSpread, spread);
	}

	return ConcentricPattern{centered(cur.p), (maxSpread + minSpread) / 2};
}

static std::vector<ConcentricPattern> FindPureFinderPattern(const BitMatrix& image)
{
	int left, top, width, height;
	if (!image.findBoundingBox(left, top, width, height, 11)) {  // 11 is the size of an Aztec Rune, see ISO/IEC 24778:2008(E) Annex A
		// Runes 68 and 223 have none of their bits set on the bottom row
		if (image.findBoundingBox(left, top, width, height, 10) && (width == 11) && (height == 10))
			height = 11;
		else
			return {};
	}	

	// Symbols can have a blank row or column at the edge (in particular, top and left)
	if (width < height && image.width() >= height) {
		left = std::max(0, left - (height - width + 1) / 2); // No real net effect if right edge blank
		width = height;
	} else if (height < width && image.height() >= width) {
		top = std::max(0, top - (width - height + 1) / 2); // No real net effect if bottom edge blank
		height = width;
	}

	PointF p(left + width / 2, top + height / 2);
	constexpr auto PATTERN = FixedPattern<7, 7>{1, 1, 1, 1, 1, 1, 1};
	if (auto pattern = LocateConcentricPattern(image, PATTERN, p, width))
		return {*pattern};
	else
		return {};
}

static std::vector<ConcentricPattern> FindFinderPatterns(const BitMatrix& image, bool tryHarder)
{
	std::vector<ConcentricPattern> res;

	[[maybe_unused]] int N = 0;

#if 0 // reference algorithm for finding aztec center candidates
	constexpr auto PATTERN = FixedPattern<7, 7>{1, 1, 1, 1, 1, 1, 1};
	auto l0 = image.row(0);
	std::vector<uint8_t> line(l0.begin(), l0.end());
	const int width = image.width();

	int skip = tryHarder ? 1 : std::clamp(image.height() / 100, 1, 3);
	int margin = skip;
	for (int y = margin; y < image.height() - margin; y += skip) {
		auto lc = image.row(y).begin() + 1;
		auto lp = image.row(y - skip).begin() + 1;
		line.front() = image.get(0, y);
		// update line and swipe right
		for (int x = 1; x < image.width(); ++x) {
			line[x] += *lc++ != *lp++;
			while (line[x] > line[x - 1] + 1)
				line[x] -= 2;
		}
		// swipe left
		line.back() = image.get(width - 1, y);
		for (int x = width - 2; x > 0; --x)
			while (line[x] > line[x + 1] + 1)
				line[x] -= 2;

		int first = 0, last = 0;
		for (int x = 1; x < width - 5; ++x) {
			if (line[x] > line[x - 1] && line[x] >= 5 && line[x] % 2 == 1)
				first = x;
			else
				continue;
			while (line[x] == line[x + 1])
				++x;
			last = x;
			if (line[last + 1] < line[last]) {
				auto p = centered(PointI((first + last) / 2, y));
				// make sure p is not 'inside' an already found pattern area
				if (FindIf(res, [p](const auto& old) { return distance(p, old) < old.size / 2; }) == res.end()) {
					++N;
					auto pattern = LocateConcentricPattern(image, PATTERN, p, image.width() / 3);
					if (pattern){
						log(*pattern, 2);
						res.push_back(*pattern);
					}
				}
			}
		}
	}
#else // own algorithm based on PatternRow processing (between 0% and 100% faster than reference algo depending on input)
	int skip = tryHarder ? 1 : std::clamp(image.height() / 2 / 100, 1, 5);
	int margin = tryHarder ? 5 : image.height() / 4;

	PatternRow row;

	for (int y = margin; y < image.height() - margin; y += skip)
	{
		GetPatternRow(image, y, row, false);
		PatternView next = row;
		next.shift(1); // the center pattern we are looking for starts with white and is 7 wide (compact code)

#if 1
		while (next = FindAztecCenterPattern(next), next.isValid()) {
#else
		constexpr auto PATTERN = FixedPattern<7, 7>{1, 1, 1, 1, 1, 1, 1};
		while (next = FindLeftGuard(next, 0, PATTERN, 0.5), next.isValid()) {
#endif
			PointF p(next.pixelsInFront() + next[0] + next[1] + next[2] + next[3] / 2.0, y + 0.5);

			// make sure p is not 'inside' an already found pattern area
			bool found = false;
			for (auto& old : std::ranges::reverse_view(res)) {
				// search from back to front, stop once we are out of range due to the y-coordinate
				if (p.y - old.y > old.size / 2)
					break;
				if (distance(p, old) < old.size / 2) {
					found = true;
					break;
				}
			}

			if (!found) {
				++N;
				log(p, 1);

				auto pattern = LocateAztecCenter(image, p, next.sum());
				if (pattern) {
					log(*pattern, 3);
					assert(image.get(*pattern));
					res.push_back(*pattern);
				}
			}

			next.skipPair();
			next.extend();
		}
	}
#endif

#ifdef PRINT_DEBUG
	printf("\n# checked centers: %d, # found centers: %d\n", N, Size(res));
#endif
	return res;
}

static int FindRotation(uint32_t bits, bool mirror)
{
	const uint32_t mask = mirror ? 0b111'000'001'110 : 0b111'011'100'000;
	for (int i = 0; i < 4; ++i) {
		if (std::popcount(mask ^ bits) <= 2) // at most 2 bits may be wrong (24778:2008(E) 14.3.3 says 3 but that is wrong)
			return i;
		bits = ((bits << 3) & 0xfff) | ((bits >> 9) & 0b111); // left shift/rotate, see RotatedCorners(Quadrilateral)
	}
	return -1;
}

// read 4*3=12 bits from the 4 corners of the finder pattern at radius
static uint32_t SampleOrientationBits(const BitMatrix& image, const PerspectiveTransform& mod2Pix, int radius)
{
	uint32_t bits = 0;
	for (auto d : {PointI{-1, -1}, {1, -1}, {1, 1}, {-1, 1}}) {
		auto corner = radius * d;
		auto cornerL = corner + PointI{0, -d.y};
		auto cornerR = corner + PointI{-d.x, 0};
		if (d.x != d.y)
			std::swap(cornerL, cornerR);
		for (auto ps : {cornerL, corner, cornerR}) {
			auto p = mod2Pix(PointF(ps));
			if (!image.isIn(p))
				return 0;
			log(p);
			AppendBit(bits, image.get(p));
		}
	}
	return bits;
}

static int ModeMessage(const BitMatrix& image, const PerspectiveTransform& mod2Pix, int radius, bool& isRune)
{
	const bool compact = radius == 5;
	isRune = false;

	// read the bits between the corner bits along the 4 edges
	uint64_t bits = 0;
	for (auto d : {PointI{-1, -1}, {1, -1}, {1, 1}, {-1, 1}}) {
		auto corner = radius * d;
		auto next = (d.x == d.y) ? PointI{-d.x, 0} : PointI{0, -d.y};
		for (int i = 2; i <= 2 * radius - 2; ++i) {
			if (!compact && i == 7)
				continue; // skip the timing pattern
			auto p = mod2Pix(PointF(corner + i * next));
			log(p);
			if (!image.isIn(p))
				return -1;
			AppendBit(bits, image.get(p));
		}
	}

	// error correct bits
	int numCodewords = compact ? 7 : 10;
	int numDataCodewords = compact ? 2 : 4;
	int numECCodewords = numCodewords - numDataCodewords;

	std::vector<int> words(numCodewords);
	for (int i = numCodewords - 1; i >= 0; --i) {
		words[i] = narrow_cast<int>(bits & 0xF);
		bits >>= 4;
	}

	bool decodeResult = ReedSolomonDecode(GenericGF::AztecParam(), words, numECCodewords);

	if ((!decodeResult) && compact) {
		// Is this a Rune?
		for (auto& word : words)
			word ^= 0b1010;
		
		decodeResult = ReedSolomonDecode(GenericGF::AztecParam(), words, numECCodewords);

		if (decodeResult)
			isRune = true;
	}

	if (!decodeResult)
		return -1;

	int res = 0;
	for (int i = 0; i < numDataCodewords; i++)
		res = (res << 4) + words[i];

	return res;
}

static void ExtractParameters(int modeMessage, bool compact, int& nbLayers, int& nbDataBlocks, bool& readerInit)
{
	readerInit = false;
	if (compact) {
		// 8 bits:  2 bits layers and 6 bits data blocks
		nbLayers = (modeMessage >> 6) + 1;
		if (nbLayers == 1 && (modeMessage & 0x20)) { // ISO/IEC 24778:2008 Section 9 MSB artificially set
			readerInit = true;
			modeMessage &= ~0x20;
		}
		nbDataBlocks = (modeMessage & 0x3F) + 1;
	} else {
		// 16 bits:  5 bits layers and 11 bits data blocks
		nbLayers = (modeMessage >> 11) + 1;
		if (nbLayers <= 22 && (modeMessage & 0x400)) { // ISO/IEC 24778:2008 Section 9 MSB artificially set
			readerInit = true;
			modeMessage &= ~0x400;
		}
		nbDataBlocks = (modeMessage & 0x7FF) + 1;
	}
}

DetectorResult Detect(const BitMatrix& image, bool isPure, bool tryHarder)
{
	return FirstOrDefault(Detect(image, isPure, tryHarder, 1));
}

DetectorResults Detect(const BitMatrix& image, bool isPure, bool tryHarder, int maxSymbols)
{
#ifdef PRINT_DEBUG
	LogMatrixWriter lmw(log, image, 5, "az-log.pnm");
#endif

	DetectorResults res;
	auto fps = isPure ? FindPureFinderPattern(image) : FindFinderPatterns(image, tryHarder);
	for (const auto& fp : fps) {
		auto fpQuad = FindConcentricPatternCorners(image, fp, fp.size, 3);
		if (!fpQuad)
			continue;

		auto srcQuad = CenteredSquare(7);
		auto mod2Pix = PerspectiveTransform(srcQuad, *fpQuad);
		if (!mod2Pix.isValid())
			continue;

		int radius; // 5 or 7 (compact vs. full)
		int mirror; // 0 or 1
		int rotate; // [0..3]
		int modeMessage = -1;
		bool isRune = false;
		[&]() {
			// 24778:2008(E) 14.3.3 reads:
			// In the outer layer of the Core Symbol, the 12 orientation bits at the corners are bitwise compared against the specified
			// pattern in each of four possible orientations and their four mirror inverse orientations as well. If in any of the 8
			// cases checked as many as 9 of the 12 bits correctly match, that is deemed to be the correct orientation, otherwise
			// decoding fails.
			// Unfortunately, this seems to be wrong: there are 12-bit patterns in those 8 cases that differ only in 4 bits like
			// 011'100'000'111 (rot90 && !mirror) and 111'000'001'110 (rot0 && mirror), meaning if two of those are wrong, both cases
			// have a hamming distance of 2, meaning only 1 bit errors can be reliable recovered from. The following code therefore
			// incorporates the complete set of mode message bits to help determine the orientation of the symbol. This is still not
			// sufficient for the ErrorInModeMessageZero test case in AZDecoderTest.cpp but good enough for the author.
			for (radius = 5; radius <= 7; radius += 2) {
				uint32_t bits = SampleOrientationBits(image, mod2Pix, radius);
				if (bits == 0)
					continue;
				for (mirror = 0; mirror <= 1; ++mirror) {
					rotate = FindRotation(bits, mirror);
					if (rotate == -1)
						continue;
					modeMessage = ModeMessage(image, PerspectiveTransform(srcQuad, RotatedCorners(*fpQuad, rotate, mirror)), radius, isRune);
					if (modeMessage != -1)
						return;
				}
			}
		}();

		if (modeMessage == -1)
			continue;

#if 1
		// improve prescision of sample grid by extrapolating from outer square of white pixels (5 edges away from center)
		if (radius == 7) {
			if (auto fpQuad5 = FindConcentricPatternCorners(image, fp, fp.size * 5 / 3, 5)) {
				if (auto mod2Pix = PerspectiveTransform(CenteredSquare(11), *fpQuad5); mod2Pix.isValid()) {
					int rotate5 = FindRotation(SampleOrientationBits(image, mod2Pix, radius), mirror);
					if (rotate5 != -1) {
						srcQuad = CenteredSquare(11);
						fpQuad = fpQuad5;
						rotate = rotate5;
					}
				}
			}
		}
#endif
		*fpQuad = RotatedCorners(*fpQuad, rotate, mirror);

		int nbLayers = 0;
		int nbDataBlocks = 0;
		bool readerInit = false;
		if (!isRune) {
			ExtractParameters(modeMessage, radius == 5, nbLayers, nbDataBlocks, readerInit);
		}

		int dim = radius == 5 ? 4 * nbLayers + 11 : 4 * nbLayers + 2 * ((2 * nbLayers + 6) / 15) + 15;
		double low = dim / 2.0 + srcQuad[0].x;
		double high = dim / 2.0 + srcQuad[2].x;

		auto bits = SampleGrid(image, dim, dim, PerspectiveTransform{{PointF{low, low}, {high, low}, {high, high}, {low, high}}, *fpQuad});
		if (!bits.isValid())
			continue;

		res.emplace_back(std::move(bits), radius == 5, nbDataBlocks, nbLayers, readerInit, mirror != 0, isRune ? modeMessage : -1);

		if (Size(res) == maxSymbols)
			break;
	}

	return res;
}

} // namespace ZXing::Aztec