Add gray code rank tests

2 files changed, 163 insertions, 1 deletions

diff --git a/Makefile b/Makefile
index 58def9b..437ca31 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 CXXFLAGS += -I. -std=c++14 -Wall -Wextra -Wno-unused-parameter
 
 HEADERS = $(wildcard chilbert/*.hpp)
-TESTS = test/test_bitvec
+TESTS = test/test_bitvec test/test_gray_code_rank
 
 all: $(TESTS)
 
diff --git a/test/test_gray_code_rank.cpp b/test/test_gray_code_rank.cpp
new file mode 100644
index 0000000..c52bab6
--- /dev/null
+++ b/test/test_gray_code_rank.cpp
@@ -0,0 +1,162 @@
+/*
+  Copyright (C) 2018 David Robillard <d@drobilla.net>
+
+  This program is free software: you can redistribute it and/or modify it under
+  the terms of the GNU General Public License as published by the Free Software
+  Foundation, either version 2 of the License, or (at your option) any later
+  version.
+
+  This program is distributed in the hope that it will be useful, but WITHOUT
+  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+  FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
+  details.
+
+  You should have received a copy of the GNU General Public License along with
+  this program.  If not, see <https://www.gnu.org/licenses/>.
+*/
+
+#undef NDEBUG
+
+#include "test_utils.hpp"
+
+#include "chilbert/BigBitVec.hpp"
+#include "chilbert/FixBitVec.hpp"
+#include "chilbert/GrayCodeRank.hpp"
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <cstddef>
+#include <cstdint>
+#include <iostream>
+#include <iterator>
+
+/// Return an array of D precisions with sum at most N
+template <size_t N, size_t D>
+std::array<size_t, D>
+make_random_precisions(Context& ctx)
+{
+	std::array<size_t, D> ms;
+	size_t                bits_left = N;
+	for (size_t i = 0; i < D; ++i) {
+		ms[i] = rand_between(ctx, 1, bits_left / (D - i) + 1);
+		bits_left -= ms[i];
+	}
+
+	return ms;
+}
+
+template <class T, size_t N, size_t D>
+T
+get_mask(const std::array<size_t, D>& ms, const size_t d, const size_t step)
+{
+	T      mask = make_zero_bitvec<T, N>();
+	size_t b;
+	chilbert::extractMask(ms.data(), D, d, step, mask, b);
+
+	assert(b == mask.count());
+
+	return mask;
+}
+
+template <class T, size_t N, size_t D>
+void
+test_extract_mask(Context& ctx)
+{
+	for (size_t d = 0; d < D; ++d) {
+		const auto   ms    = make_random_precisions<N, D>(ctx);
+		const auto   max_m = *std::max_element(std::begin(ms), std::end(ms));
+		const size_t step  = rand_between(ctx, 0, max_m);
+		const auto   mask  = get_mask<T, N>(ms, d, step);
+
+		for (size_t i = 0; i < D; ++i) {
+			assert(mask.test(i) == (ms[(d + i) % D] > step));
+		}
+	}
+}
+
+template <class T, size_t N, size_t D>
+void
+test_gray_code_rank(Context& ctx)
+{
+	for (size_t d = 0; d < D; ++d) {
+		// Generate random mask
+		const auto   ms    = make_random_precisions<N, D>(ctx);
+		const auto   max_m = *std::max_element(std::begin(ms), std::end(ms));
+		const size_t step  = rand_between(ctx, 0, max_m);
+		const auto   mask  = get_mask<T, N>(ms, d, step);
+
+		// Generate two random values and their gray codes
+		const auto a = make_random_bitvec<T, N>(ctx);
+		const auto b = make_random_bitvec<T, N>(ctx);
+
+		auto ga = a;
+		grayCode(ga);
+
+		auto gb = b;
+		grayCode(gb);
+
+		// Calculate gray code ranks
+		auto ra = make_zero_bitvec<T, N>();
+		chilbert::grayCodeRank(mask, ga, D, ra);
+
+		auto rb = make_zero_bitvec<T, N>();
+		chilbert::grayCodeRank(mask, gb, D, rb);
+
+		// Ensure ranks have at most mask.count() bits
+		if (mask.count() < N) {
+			auto max = make_zero_bitvec<T, N>();
+			setBit(max, mask.count(), 1);
+			assert(ra < max);
+			assert(rb < max);
+		}
+
+		// Test fundamental property of gray code ranks
+		const auto mga = ga & mask;
+		const auto mgb = gb & mask;
+		assert((mga < mgb) == (ra < rb));
+
+		// Test inversion
+		const auto pat     = ~mask;
+		auto       ga_out  = make_zero_bitvec<T, N>();
+		auto       gag_out = make_zero_bitvec<T, N>();
+		grayCodeRankInv(mask, pat, ra, D, mask.count(), gag_out, ga_out);
+		assert((ga_out & mask) == (ga & mask));
+
+		auto gag_check = ga_out;
+		grayCode(gag_check);
+		assert(gag_check == gag_out);
+	}
+}
+
+template <class T, size_t N, size_t D>
+void
+test(Context& ctx)
+{
+	test_extract_mask<T, N, D>(ctx);
+	test_gray_code_rank<T, N, D>(ctx);
+}
+
+int
+main()
+{
+	Context ctx;
+
+	test<chilbert::CFixBitVec, 64, 1>(ctx);
+	test<chilbert::CFixBitVec, 64, 31>(ctx);
+	test<chilbert::CFixBitVec, 64, 32>(ctx);
+	test<chilbert::CFixBitVec, 64, 33>(ctx);
+	test<chilbert::CFixBitVec, 64, 60>(ctx);
+	test<chilbert::CFixBitVec, 64, 64>(ctx);
+
+	test<chilbert::CBigBitVec, 64, 1>(ctx);
+	test<chilbert::CBigBitVec, 64, 31>(ctx);
+	test<chilbert::CBigBitVec, 64, 32>(ctx);
+	test<chilbert::CBigBitVec, 64, 33>(ctx);
+	test<chilbert::CBigBitVec, 64, 60>(ctx);
+	test<chilbert::CBigBitVec, 64, 64>(ctx);
+	test<chilbert::CBigBitVec, 128, 65>(ctx);
+	test<chilbert::CBigBitVec, 1024, 997>(ctx);
+
+	return 0;
+}