[lib][affine] Port timeline transformations to the zircon level.
Port the majority of the functionality of the media TimelineTransform
library down to the zircon level. The library is not technically time
specific. Instead it implements a specific representation of
one-dimentional affine transformations, so rename to libaffine in the
process.
This is all preparing to make use of the library functionality in the
kernel as part of the implementation of kernel clock objects. Make
sure to use the same fundamental representation of the transformations
so that the core of the transformations maintain compatibility with
what is currently being used in the media code.
Also:
++ Write unit tests. The old library didn't have any, and probably
could use some.
++ Fix a few small edge case bugs which were found by inspection while
thinking up test vectors.
Change-Id: I0841ac5f53b9f8bf77a7fd903c97c2f8af3c3df8
diff --git a/zircon/system/ulib/affine/BUILD.gn b/zircon/system/ulib/affine/BUILD.gn
new file mode 100644
index 0000000..abeda61
--- /dev/null
+++ b/zircon/system/ulib/affine/BUILD.gn
@@ -0,0 +1,24 @@
+# Copyright 2019 The Fuchsia Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+library("affine") {
+ sdk = "source"
+ sdk_headers = [
+ "lib/affine/ratio.h",
+ "lib/affine/transform.h",
+ ]
+
+ host = true
+ kernel = true
+ static = true
+
+ sources = [
+ "ratio.cpp",
+ "transform.cpp",
+ ]
+
+ public_deps = [
+ "$zx/third_party/ulib/safemath",
+ ]
+}
diff --git a/zircon/system/ulib/affine/include/lib/affine/ratio.h b/zircon/system/ulib/affine/include/lib/affine/ratio.h
new file mode 100644
index 0000000..456357c
--- /dev/null
+++ b/zircon/system/ulib/affine/include/lib/affine/ratio.h
@@ -0,0 +1,119 @@
+// Copyright 2019 The Fuchsia Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef LIB_AFFINE_RATIO_H_
+#define LIB_AFFINE_RATIO_H_
+
+#include <stdint.h>
+#include <limits>
+#include <type_traits>
+#include <zircon/assert.h>
+
+namespace affine {
+
+class Transform; // fwd decl for friendship
+
+class Ratio {
+public:
+ enum class Exact { No, Yes };
+
+ // Used to indicate overflow/underflow of scaling operations.
+ static constexpr int64_t kOverflow = std::numeric_limits<int64_t>::max();
+ static constexpr int64_t kUnderflow = std::numeric_limits<int64_t>::min();
+
+ // Reduces the ratio of N/D
+ //
+ // Defined only for uint32_t and uint64_t
+ template <typename T>
+ static void Reduce(T* numerator, T* denominator);
+
+ // Produces the product two 32 bit ratios. If exact is true, ASSERTs on loss
+ // of precision.
+ static void Product(uint32_t a_numerator,
+ uint32_t a_denominator,
+ uint32_t b_numerator,
+ uint32_t b_denominator,
+ uint32_t* product_numerator,
+ uint32_t* product_denominator,
+ Exact exact = Exact::Yes);
+
+ // Produces the product of a 32 bit ratio and the int64_t as an int64_t. Returns
+ // a saturated value (either kOverflow or kUnderflow) on overflow/underflow.
+ static int64_t Scale(int64_t value, uint32_t numerator, uint32_t denominator);
+
+ // Returns the product of the ratios. If exact is true, ASSERTs on loss of
+ // precision.
+ static Ratio Product(Ratio a, Ratio b, Exact exact = Exact::Yes) {
+ uint32_t result_numerator;
+ uint32_t result_denominator;
+ Product(a.numerator(), a.denominator(),
+ b.numerator(), b.denominator(),
+ &result_numerator, &result_denominator,
+ exact);
+ return Ratio(result_numerator, result_denominator, NoReduce::Tag);
+ }
+
+ Ratio() = default;
+ Ratio(uint32_t numerator, uint32_t denominator)
+ : numerator_(numerator), denominator_(denominator) {
+ Reduce(&numerator_, &denominator_);
+ }
+
+ uint32_t numerator() const { return numerator_; }
+ uint32_t denominator() const { return denominator_; }
+ bool invertible() const { return numerator_ != 0; }
+
+ Ratio Inverse() const {
+ ZX_ASSERT(invertible());
+ return Ratio{denominator_, numerator_, NoReduce::Tag};
+ }
+
+ int64_t Scale(int64_t value) const {
+ return Scale(value, numerator_, denominator_);
+ }
+
+private:
+ friend class Transform;
+ enum class NoReduce { Tag };
+
+ Ratio(uint32_t numerator, uint32_t denominator, NoReduce)
+ : numerator_(numerator), denominator_(denominator) {}
+
+ uint32_t numerator_ = 1;
+ uint32_t denominator_ = 1;
+};
+
+// Tests two ratios for equality.
+inline bool operator==(Ratio a, Ratio b) {
+ return a.numerator() == b.numerator() &&
+ a.denominator() == b.denominator();
+}
+
+// Tests two ratios for inequality.
+inline bool operator!=(Ratio a, Ratio b) { return !(a == b); }
+
+// Returns the ratio of the two ratios.
+inline Ratio operator/(Ratio a, Ratio b) {
+ return Ratio::Product(a, b.Inverse());
+}
+
+// Returns the product of the two ratios.
+inline Ratio operator*(Ratio a, Ratio b) {
+ return Ratio::Product(a, b);
+}
+
+// Returns the product of the rate and the int64_t.
+inline int64_t operator*(Ratio a, int64_t b) { return a.Scale(b); }
+
+// Returns the product of the rate and the int64_t.
+inline int64_t operator*(int64_t a, Ratio b) { return b.Scale(a); }
+
+// Returns the the int64_t divided by the rate.
+inline int64_t operator/(int64_t a, Ratio b) {
+ return b.Inverse().Scale(a);
+}
+
+} // namespace affine
+
+#endif // LIB_AFFINE_RATIO_H_
diff --git a/zircon/system/ulib/affine/include/lib/affine/transform.h b/zircon/system/ulib/affine/include/lib/affine/transform.h
new file mode 100644
index 0000000..69d25b4
--- /dev/null
+++ b/zircon/system/ulib/affine/include/lib/affine/transform.h
@@ -0,0 +1,163 @@
+// Copyright 2019 The Fuchsia Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef LIB_AFFINE_TRANSFORM_H_
+#define LIB_AFFINE_TRANSFORM_H_
+
+#include <lib/affine/ratio.h>
+#include <safemath/clamped_math.h>
+
+namespace affine {
+
+// A small helper class which represents a 1 dimensional affine transformation
+// from a signed 64 bit space A, to a signed 64 bit space B. Conceptually, this
+// is the function...
+//
+// f(a) = b = (a * scale) + offset
+//
+// Internally, however, the exact function used is
+//
+// f(a) = b = (((a - A_offset) * B_scale) / A_scale) + B_offset
+//
+// Where the offsets involved are 64 bit signed integers, and the scale factors
+// are 32 bit unsigned integers.
+//
+// Overflow/Underflow saturation behavior is as follows.
+// The transformation operation is divided into three stages.
+//
+// 1) Offset by A_offset
+// 2) Scale by (B_scale / A_scale)
+// 3) Offset by B_offset
+//
+// Each stage is saturated indepenedently. That is to say, if the result of
+// stage #1 is clamped at int64::min, this is the input value which will be fed
+// into stage #2. The calculations are *not* done with infinite precision and
+// then clamped at the end.
+//
+// TODO(johngro): Reconsider this. Clamping at intermediate stages can make it
+// more difficult to understand that saturation happened at all, and might be
+// important to a client. It may be better to either signal explicitly that
+// this happened, or to extend the precision of the operation in the rare slow
+// path so that saturation behavior occurs only at the end of the op, and
+// produces a correct result if the transform would have saturated at an
+// intermediate step, but got brought back into range by a subsequent operation.
+//
+// Saturation is enabled by default, but may be disabled by choosing the
+// Saturate::No form of Apply/ApplyInverse. When saturation behavior is
+// disabled, the results of a transformation where over/underflow occurs at any
+// stage is undefined.
+//
+class Transform {
+public:
+ using Exact = Ratio::Exact;
+ enum class Saturate { No, Yes };
+
+ // Applies a transformation from A -> B
+ template <Saturate SATURATE = Saturate::Yes>
+ static int64_t Apply(int64_t a_offset,
+ int64_t b_offset,
+ Ratio ratio, // Ratio of B_scale:A_scale
+ int64_t val) {
+ if constexpr (SATURATE == Saturate::Yes) {
+ return safemath::ClampAdd(ratio.Scale(safemath::ClampSub(val, a_offset)), b_offset);
+ } else {
+ // TODO(johngro) : the multiplication by the ratio operation here
+ // actually implements saturation behavior. If we want this
+ // operation to actually perform no saturation checks at all, we
+ // need to make a Saturate::No version of Ratio::Scale.
+ return ((val - a_offset) * ratio) + b_offset;
+ }
+ }
+
+ // Applies the inverse transformation B -> A
+ template <Saturate SATURATE = Saturate::Yes>
+ static int64_t ApplyInverse(int64_t a_offset,
+ int64_t b_offset,
+ Ratio ratio, // Ratio of B_scale:A_scale
+ int64_t val) {
+ return Apply<SATURATE>(b_offset, a_offset, ratio.Inverse(), val);
+ }
+
+ // Default construction is identity
+ Transform() = default;
+
+ // Explicit construction
+ Transform(int64_t a_offset,
+ int64_t b_offset,
+ Ratio ratio) : a_offset_(a_offset), b_offset_(b_offset), ratio_(ratio) {}
+
+ // Construct a linear transformation (zero offsets) from a ratio
+ explicit Transform(Ratio ratio)
+ : a_offset_(0), b_offset_(0), ratio_(ratio) {}
+
+ bool invertible() const { return ratio_.invertible(); }
+ int64_t a_offset() const { return a_offset_; }
+ int64_t b_offset() const { return b_offset_; }
+ Ratio ratio() const { return ratio_; }
+ uint32_t numerator() const { return ratio_.numerator(); }
+ uint32_t denominator() const { return ratio_.denominator(); }
+
+ // Construct and return a transform which is the inverse of this transform.
+ Transform Inverse() const {
+ return Transform(b_offset_, a_offset_, ratio_.Inverse());
+ }
+
+ // Applies the transformation
+ template <Saturate SATURATE = Saturate::Yes>
+ int64_t Apply(int64_t val) const {
+ return Apply<SATURATE>(a_offset_, b_offset_, ratio_, val);
+ }
+
+ // Applies the inverse transformation
+ template <Saturate SATURATE = Saturate::Yes>
+ int64_t ApplyInverse(int64_t subject_input) const {
+ ZX_DEBUG_ASSERT(ratio_.denominator() != 0u);
+ return ApplyInverse<SATURATE>(a_offset_, b_offset_, ratio_, subject_input);
+ }
+
+ // Applies the transformation using functor operator notation.
+ template <Saturate SATURATE = Saturate::Yes>
+ int64_t operator()(int64_t val) const {
+ return Apply<SATURATE>(val);
+ }
+
+ // Composes two timeline functions B->C and A->B producing A->C. If exact is
+ // Exact::Yes, DCHECKs on loss of precision.
+ //
+ // During composition, the saturation behavior is as follows
+ //
+ // 1) The intermediate offset (bc.a_offset - ab.b_offset) will be saturated
+ // before distribution to the offsets ac.
+ // 2) Both offsets of ac will be saturated as ab.a_offset and bc.b_offset
+ // are combined with the distributed intermediate offset.
+ //
+ static Transform Compose(const Transform& bc, const Transform& ab, Exact exact = Exact::Yes);
+
+private:
+ int64_t a_offset_ = 0;
+ int64_t b_offset_ = 0;
+ Ratio ratio_{1, 1, Ratio::NoReduce::Tag};
+};
+
+// Tests two transforms for equality.
+inline bool operator==(const Transform& a, const Transform& b) {
+ return (a.a_offset() == b.a_offset()) &&
+ (a.b_offset() == b.b_offset()) &&
+ (a.ratio() == b.ratio());
+}
+
+// Tests two transforms for inequality.
+inline bool operator!=(const Transform& a, const Transform& b) {
+ return !(a == b);
+}
+
+// Composes two timeline functions B->C and A->B producing A->C. DCHECKs on
+// loss of precision.
+inline Transform operator*(const Transform& bc, const Transform& ab) {
+ return Transform::Compose(bc, ab);
+}
+
+} // namespace affine
+
+#endif // LIB_AFFINE_TRANSFORM_H_
diff --git a/zircon/system/ulib/affine/ratio.cpp b/zircon/system/ulib/affine/ratio.cpp
new file mode 100644
index 0000000..ce789e2
--- /dev/null
+++ b/zircon/system/ulib/affine/ratio.cpp
@@ -0,0 +1,238 @@
+// Copyright 2019 The Fuchsia Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <lib/affine/ratio.h>
+#include <type_traits>
+#include <zircon/assert.h>
+
+namespace affine {
+namespace {
+
+// Calculates the greatest common denominator (factor) of two values.
+template <typename T>
+T BinaryGcd(T a, T b) {
+ ZX_DEBUG_ASSERT(a && b);
+
+ // Remove and count the common factors of 2.
+ uint8_t twos;
+ for (twos = 0; ((a | b) & 1) == 0; ++twos) {
+ a >>= 1;
+ b >>= 1;
+ }
+
+ // Get rid of the non-common factors of 2 in a. a is non-zero, so this
+ // terminates.
+ while ((a & 1) == 0) {
+ a >>= 1;
+ }
+
+ do {
+ // Get rid of the non-common factors of 2 in b. b is non-zero, so this
+ // terminates.
+ while ((b & 1) == 0) {
+ b >>= 1;
+ }
+
+ // Apply the Euclid subtraction method.
+ if (a > b) {
+ std::swap(a, b);
+ }
+
+ b = b - a;
+ } while (b != 0);
+
+ // Multiply in the common factors of two.
+ return a << twos;
+}
+
+enum class RoundDirection { Down, Up };
+
+// Scales a uint64_t value by the ratio of two uint32_t values. If round_up is
+// true, the result is rounded up rather than down. overflow is set to indicate
+// overflow.
+template <RoundDirection ROUND_DIR, uint64_t OVERFLOW_LIMIT_64>
+uint64_t ScaleUInt64(uint64_t value, uint32_t numerator, uint32_t denominator) {
+ constexpr uint64_t kLow32Bits = 0xffffffffu;
+
+ // high and low are the product of the numerator and the high and low halves
+ // (respectively) of value.
+ uint64_t high = numerator * (value >> 32u);
+ uint64_t low = numerator * (value & kLow32Bits);
+
+ // Ignoring overflow and remainder, the result we want is:
+ // ((high << 32) + low) / denominator.
+
+ // Move the high end of low into the low end of high.
+ high += low >> 32u;
+ low = low & kLow32Bits;
+
+ // Ignoring overflow and remainder, the result we want is still:
+ // ((high << 32) + low) / denominator.
+
+ // Compute the divmod of high/D
+ uint64_t high_q = high / denominator;
+ uint64_t high_r = high % denominator;
+
+ // If high is larger than the overflow limit, then we can just get out now.
+ // The overflow limit will be different depending on whether we are scaling
+ // a non-negative number (0x7FFFFFFF) or a negative number (0x80000000)
+ constexpr uint64_t OVERFLOW_LIMIT_32 = OVERFLOW_LIMIT_64 >> 32;
+ if (high > OVERFLOW_LIMIT_32) {
+ return OVERFLOW_LIMIT_64;
+ }
+
+ // The remainder of high/D are the high bits of low. Or them in, and do the
+ // divmod for the low portion
+ low |= high_r << 32u;
+
+ uint64_t low_q = low / denominator;
+ __UNUSED uint64_t low_r = low % denominator;
+
+ uint64_t result = (high_q << 32u) | low_q;
+
+ if constexpr (ROUND_DIR == RoundDirection::Up) {
+ if (result >= OVERFLOW_LIMIT_64) {
+ return OVERFLOW_LIMIT_64;
+ }
+ if (low_r) {
+ ++result;
+ }
+ }
+
+ return result;
+}
+
+constexpr bool FitsIn32Bits(uint64_t numerator, uint64_t denominator) {
+ return ((numerator <= std::numeric_limits<uint32_t>::max()) &&
+ (denominator <= std::numeric_limits<uint32_t>::max()));
+}
+
+} // namespace
+
+template <typename T>
+void Ratio::Reduce(T* numerator, T* denominator) {
+ ZX_DEBUG_ASSERT(numerator != nullptr);
+ ZX_DEBUG_ASSERT(denominator != nullptr);
+ ZX_ASSERT(*denominator != 0);
+
+ if (*numerator == 0) {
+ *denominator = 1;
+ return;
+ }
+
+ T gcd = BinaryGcd(*numerator, *denominator);
+ if constexpr (std::is_same_v<uint32_t, T>) {
+ ZX_DEBUG_ASSERT_MSG(gcd != 0, "Bad GCD (N/D) == (%u/%u)\n", *numerator, *denominator);
+ } else {
+ ZX_DEBUG_ASSERT_MSG(gcd != 0, "Bad GCD (N/D) == (%lu/%lu)\n", *numerator, *denominator);
+ }
+
+ if (gcd == 1) {
+ return;
+ }
+
+ *numerator = *numerator / gcd;
+ *denominator = *denominator / gcd;
+}
+
+void Ratio::Product(uint32_t a_numerator, uint32_t a_denominator,
+ uint32_t b_numerator, uint32_t b_denominator,
+ uint32_t* product_numerator, uint32_t* product_denominator,
+ Exact exact) {
+ ZX_DEBUG_ASSERT(product_numerator != nullptr);
+ ZX_DEBUG_ASSERT(product_denominator != nullptr);
+
+ uint64_t numerator = static_cast<uint64_t>(a_numerator) * b_numerator;
+ uint64_t denominator = static_cast<uint64_t>(a_denominator) * b_denominator;
+
+ Ratio::Reduce(&numerator, &denominator);
+
+ if (!FitsIn32Bits(numerator, denominator)) {
+ ZX_ASSERT(exact == Exact::No);
+
+ // Try to find the best approximation of the ratio that we can. Our
+ // approach is as follows. Figure out the number of bits to the right
+ // we need to shift the numerator and denominator, rounding up or down
+ // in the process, such that the result can be reduced to fit into 32
+ // bits.
+ //
+ // This approach tends to beat out a just-shift-until-it-fits approach,
+ // as well as an always-shift-then-reduce approach, but _none_ of these
+ // approaches always finds the best solution.
+ //
+ // TODO(johngro) : figure out if it is reasonable to actually compute
+ // the best solution. Alternatively, consider implementing a "just
+ // shift until it fits" solution if the approximate results are good
+ // enough.
+ //
+ for (uint32_t i = 1; i <= 32; ++i) {
+ // Produce a version of the numerator and denominator which have
+ // each been divided by 2^i, rounding up/down as appropriate
+ // (instead of truncating).
+ uint64_t rounded_numerator = (numerator + (static_cast<uint64_t>(1) << (i - 1))) >> i;
+ uint64_t rounded_denominator =
+ (denominator + (static_cast<uint64_t>(1) << (i - 1))) >> i;
+
+ if (rounded_denominator == 0) {
+ // Product is larger than we can represent. Return the largest value we
+ // can represent.
+ *product_numerator = std::numeric_limits<uint32_t>::max();
+ *product_denominator = 1;
+ return;
+ }
+
+ if (rounded_numerator == 0) {
+ // Product is smaller than we can represent. Return 0.
+ *product_numerator = 0;
+ *product_denominator = 1;
+ return;
+ }
+
+ Ratio::Reduce(&rounded_numerator, &rounded_denominator);
+ if (FitsIn32Bits(rounded_numerator, rounded_denominator)) {
+ *product_numerator = static_cast<uint32_t>(rounded_numerator);
+ *product_denominator = static_cast<uint32_t>(rounded_denominator);
+ return;
+ }
+ }
+ }
+
+ *product_numerator = static_cast<uint32_t>(numerator);
+ *product_denominator = static_cast<uint32_t>(denominator);
+}
+
+int64_t Ratio::Scale(int64_t value, uint32_t numerator, uint32_t denominator) {
+ ZX_ASSERT(denominator != 0u);
+
+ if (value >= 0) {
+ // LIMIT == 0x7FFFFFFFFFFFFFFF
+ constexpr uint64_t LIMIT = static_cast<uint64_t>(std::numeric_limits<int64_t>::max());
+ return static_cast<int64_t>(ScaleUInt64<RoundDirection::Down, LIMIT>(
+ static_cast<uint64_t>(value), numerator, denominator));
+ } else {
+ // LIMIT == 0x8000000000000000
+ //
+ // Note: We are attempting to pass the unsigned disaance from zero into
+ // our ScaleUInt64 function. In the case of negative numbers, we pass
+ // the twos compliment into the scale function, and then flip the sign
+ // again on the way out.
+ //
+ // We are taking the advantage of the fact that the twos compliment of
+ // MIN is itself for any signed integer type, and that casting this
+ // value to an unsigned integer of the same size properly produces the
+ // original value's distance from zero. Clamping the limit to the
+ // disance of MIN from zero means that saturated results will likewise
+ // get properly flipped back to MIN during the return.
+ //
+ constexpr uint64_t LIMIT = static_cast<uint64_t>(std::numeric_limits<int64_t>::min());
+ return -static_cast<int64_t>(ScaleUInt64<RoundDirection::Up, LIMIT>(
+ static_cast<uint64_t>(-value), numerator, denominator));
+ }
+}
+
+// Explicit instantiation of the two supported types of Ratio
+template void Ratio::Reduce<uint32_t>(uint32_t*, uint32_t*);
+template void Ratio::Reduce<uint64_t>(uint64_t*, uint64_t*);
+
+} // namespace affine
diff --git a/zircon/system/ulib/affine/test/BUILD.gn b/zircon/system/ulib/affine/test/BUILD.gn
new file mode 100644
index 0000000..65f42aa
--- /dev/null
+++ b/zircon/system/ulib/affine/test/BUILD.gn
@@ -0,0 +1,23 @@
+# Copyright 2019 The Fuchsia Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+group("test") {
+ testonly = true
+ deps = [
+ ":affine",
+ ]
+}
+
+test("affine") {
+ sources = [
+ "ratio.cpp",
+ "transform.cpp",
+ ]
+ deps = [
+ "$zx/system/ulib/affine",
+ "$zx/system/ulib/fdio",
+ "$zx/system/ulib/fit",
+ "$zx/system/ulib/zxtest",
+ ]
+}
diff --git a/zircon/system/ulib/affine/test/ratio.cpp b/zircon/system/ulib/affine/test/ratio.cpp
new file mode 100644
index 0000000..feb6986
--- /dev/null
+++ b/zircon/system/ulib/affine/test/ratio.cpp
@@ -0,0 +1,420 @@
+// Copyright 2019 The Fuchsia Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <array>
+#include <lib/affine/ratio.h>
+#include <lib/fit/function.h>
+#include <type_traits>
+#include <zxtest/zxtest.h>
+
+namespace {
+
+enum class Fatal { No, Yes };
+
+template <typename T>
+struct ReductionTestVector {
+ T initial_n, initial_d;
+ T expected_n, expected_d;
+ Fatal expect_fatal;
+};
+
+template <typename T, size_t VECTOR_COUNT>
+void ReductionHelper(const std::array<ReductionTestVector<T>, VECTOR_COUNT>& vectors) {
+ const char* tag;
+ if (std::is_same_v<T, uint32_t>) {
+ tag = "uint32_t";
+ } else
+ if (std::is_same_v<T, uint64_t>) {
+ tag = "uint64_t";
+ } else {
+ tag = "<unknown>";
+ }
+
+ // Test reduction using the static method
+ for (const auto& V : vectors) {
+ T N = V.initial_n;
+ T D = V.initial_d;
+
+ if (V.expect_fatal == Fatal::No) {
+ affine::Ratio::Reduce<T>(&N, &D);
+
+ ASSERT_TRUE((N == V.expected_n) && (D == V.expected_d),
+ "Expected %s %lu/%lu to reduce to %lu/%lu; got %lu/%lu instead.",
+ tag,
+ static_cast<uint64_t>(V.initial_n),
+ static_cast<uint64_t>(V.initial_d),
+ static_cast<uint64_t>(V.expected_n),
+ static_cast<uint64_t>(V.expected_d),
+ static_cast<uint64_t>(N),
+ static_cast<uint64_t>(D));
+ } else {
+ ASSERT_DEATH([&V]() {
+ T N = V.initial_n;
+ T D = V.initial_d;
+ affine::Ratio::Reduce<T>(&N, &D);
+ });
+ }
+ }
+}
+} // namespace
+
+TEST(RatioTestCase, Construction) {
+ struct TestVector {
+ uint32_t N, D;
+ Fatal expect_fatal;
+ };
+
+ constexpr std::array TEST_VECTORS {
+ TestVector{ 0, 1, Fatal::No },
+ TestVector{ 1, 1, Fatal::No },
+ TestVector{ 23, 41, Fatal::No },
+ TestVector{ 1, 0, Fatal::Yes },
+ };
+
+ // Test that explicit construction and the numerator/denominator accessors
+ // are working properly.
+ for (const auto& V : TEST_VECTORS) {
+ if (V.expect_fatal == Fatal::No) {
+ affine::Ratio R{ V.N, V.D };
+ ASSERT_EQ(R.numerator(), V.N);
+ ASSERT_EQ(R.denominator(), V.D);
+ } else {
+ ASSERT_DEATH(([&V]() { affine::Ratio R{ V.N, V.D }; }));
+ }
+ }
+
+ // Test that the default constructor produces 1/1
+ {
+ affine::Ratio R;
+ ASSERT_EQ(R.numerator(), 1);
+ ASSERT_EQ(R.denominator(), 1);
+ }
+
+ // Test that reduction is automatically performed. Note; this is a trivial
+ // test of reduction. There are more thorough tests later on.
+ {
+ affine::Ratio R{9, 21};
+ ASSERT_EQ(R.numerator(), 3);
+ ASSERT_EQ(R.denominator(), 7);
+ }
+}
+
+TEST(RatioTestCase, Equality) {
+ enum class Expected { Same = 0, Different };
+
+ struct TestVector {
+ affine::Ratio ratio;
+ Expected expected;
+ };
+
+ const std::array TEST_VECTORS {
+ TestVector{ {1, 4}, Expected::Same },
+ TestVector{ {1, 4}, Expected::Same },
+ TestVector{ {2, 8}, Expected::Same },
+ TestVector{ {1, 5}, Expected::Different },
+ };
+
+ for (const auto& a : TEST_VECTORS) {
+ for (const auto& b : TEST_VECTORS) {
+ // These test vectors should match if they are both in the "same"
+ // class, or if they are literally the same test vector.
+ if ((&a == &b) || ((a.expected == Expected::Same) && (b.expected == Expected::Same))) {
+ ASSERT_TRUE (a.ratio == b.ratio);
+ ASSERT_FALSE(a.ratio != b.ratio);
+ } else {
+ ASSERT_FALSE(a.ratio == b.ratio);
+ ASSERT_TRUE (a.ratio != b.ratio);
+ }
+ }
+ }
+}
+
+TEST(RatioTestCase, Reduction) {
+ constexpr std::array Vectors32 {
+ ReductionTestVector<uint32_t>{ 1, 1, 1, 1, Fatal::No },
+ ReductionTestVector<uint32_t>{ 10, 10, 1, 1, Fatal::No },
+ ReductionTestVector<uint32_t>{ 10, 2, 5, 1, Fatal::No },
+ ReductionTestVector<uint32_t>{ 0, 1, 0, 1, Fatal::No },
+ ReductionTestVector<uint32_t>{ 0, 500, 0, 1, Fatal::No },
+ ReductionTestVector<uint32_t>{ 48000, 44100, 160, 147, Fatal::No },
+ ReductionTestVector<uint32_t>{ 44100, 48000, 147, 160, Fatal::No },
+ ReductionTestVector<uint32_t>{ 1000007, 1000000, 1000007, 1000000, Fatal::No },
+ ReductionTestVector<uint32_t>{ 0, 0, 0, 0, Fatal::Yes },
+ ReductionTestVector<uint32_t>{ 1, 0, 0, 0, Fatal::Yes },
+ ReductionTestVector<uint32_t>{ std::numeric_limits<uint32_t>::max(), 0, 0, 0, Fatal::Yes },
+ };
+
+ constexpr std::array Vectors64 {
+ ReductionTestVector<uint64_t>{ 1, 1, 1, 1, Fatal::No },
+ ReductionTestVector<uint64_t>{ 10, 10, 1, 1, Fatal::No },
+ ReductionTestVector<uint64_t>{ 10, 2, 5, 1, Fatal::No },
+ ReductionTestVector<uint64_t>{ 0, 1, 0, 1, Fatal::No },
+ ReductionTestVector<uint64_t>{ 0, 500, 0, 1, Fatal::No },
+ ReductionTestVector<uint64_t>{ 48000, 44100, 160, 147, Fatal::No },
+ ReductionTestVector<uint64_t>{ 44100, 48000, 147, 160, Fatal::No },
+ ReductionTestVector<uint64_t>{ 1000007, 1000000, 1000007, 1000000, Fatal::No },
+ ReductionTestVector<uint64_t>{ 48000336000, 44100000000, 1000007, 918750, Fatal::No },
+ ReductionTestVector<uint64_t>{ 0, 0, 0, 0, Fatal::Yes },
+ ReductionTestVector<uint64_t>{ 1, 0, 0, 0, Fatal::Yes },
+ ReductionTestVector<uint64_t>{ std::numeric_limits<uint64_t>::max(), 0, 0, 0, Fatal::Yes },
+ };
+
+ ReductionHelper(Vectors32);
+ ReductionHelper(Vectors64);
+}
+
+TEST(RatioTestCase, Product) {
+ using Exact = affine::Ratio::Exact;
+ struct TestVector {
+ uint32_t a_n, a_d;
+ uint32_t b_n, b_d;
+ uint32_t expected_n, expected_d;
+ Exact exact;
+ Fatal expect_fatal;
+ };
+
+ constexpr std::array TEST_VECTORS {
+ // Straight-forward cases with exact solutions.
+ TestVector{ 1, 1, 1, 1, 1, 1, Exact::Yes, Fatal::No },
+ TestVector{ 0, 1, 1, 1, 0, 1, Exact::Yes, Fatal::No },
+ TestVector{ 0, 500, 1, 1, 0, 1, Exact::Yes, Fatal::No },
+ TestVector{ 3, 4, 5, 9, 5, 12, Exact::Yes, Fatal::No },
+ TestVector{48000, 44100, 1000007, 1000000, 1000007, 918750, Exact::Yes, Fatal::No },
+
+ // cases with a zero denominator. These should be fatal
+ TestVector{ 0, 0, 0, 0, 0, 0, Exact::Yes, Fatal::Yes },
+ TestVector{ 10, 0, 200, 300, 0, 0, Exact::Yes, Fatal::Yes },
+ TestVector{ 10, 20, 200, 0, 0, 0, Exact::Yes, Fatal::Yes },
+
+ // Test a case which lacks a precise solution. We should either get a
+ // degraded form, or panic, depending on whether we demand an exact
+ // solution.
+ //
+ // Note that this is a particularly brutal test case. Both of the
+ // fractions involved are pushing the limits of 32 bit storage, and none
+ // of the numerators nor denominators share _any_ prime factors.
+ //
+ // Finally, the test for the approximate solution given here is
+ // algorithm specific. If the algorithm is changed, either to increase
+ // accuracy, or to increase performance, this test vector will need to be
+ // updated.
+ //
+ // 739 * 829 * 5657 2999 * 127 * 3391 3465653567 1291540343
+ // ------------------- * ------------------- = ------------ * ------------
+ // 997 * 1609 * 1451 149 * 6173 * 4021 2327655023 3698423317
+ //
+ // 4476031396642353481
+ // = ---------------------
+ // 8608653610995371291
+ //
+ TestVector{ 3465653567, 2327655023, 1291540343, 3698423317, 0, 0, Exact::Yes, Fatal::Yes },
+ TestVector{ 3465653567, 2327655023, 1291540343, 3698423317, 317609835, 610852072,
+ Exact::No, Fatal::No},
+
+ // Test cases where the result is just a massive under or overflow.
+ TestVector{ 0xFFFFFFFF, 1, 0xFFFFFFFF, 1, 0, 0, Exact::Yes, Fatal::Yes },
+ TestVector{ 0xFFFFFFFF, 1, 0xFFFFFFFF, 1, 0xFFFFFFFF, 1, Exact::No, Fatal::No },
+ TestVector{ 1, 0xFFFFFFFF, 1, 0xFFFFFFFF, 0, 0, Exact::Yes, Fatal::Yes },
+ TestVector{ 1, 0xFFFFFFFF, 1, 0xFFFFFFFF, 0, 1, Exact::No, Fatal::No },
+ };
+
+ for (const auto& V : TEST_VECTORS) {
+ // Exercise the static Product method which takes just raw integers.
+ uint32_t N, D;
+ if (V.expect_fatal == Fatal::No) {
+ affine::Ratio::Product(V.a_n, V.a_d, V.b_n, V.b_d, &N, &D, V.exact);
+ ASSERT_TRUE((N == V.expected_n) && (D == V.expected_d),
+ "Expected %u/%u * %u/%u to produce %u/%u; got %u/%u instead.",
+ V.a_n, V.a_d, V.b_n, V.b_d, V.expected_n, V.expected_d, N, D);
+ } else {
+ ASSERT_DEATH(([&V]() {
+ uint32_t N, D;
+ affine::Ratio::Product(V.a_n, V.a_d, V.b_n, V.b_d, &N, &D, V.exact);
+ }));
+ }
+
+ // Exercise the static Product method which takes Ratio objects, along
+ // with the * and / operator. Verify that the operation is commutative
+ // as well. Skip any operations which involve a zero denominator.
+ // These will fail during construction of the ratio object (and are
+ // tested independently in the constructor tests)
+ if ((V.a_d == 0) || (V.b_d == 0)) {
+ continue;
+ }
+
+ affine::Ratio A{ V.a_n, V.a_d };
+ affine::Ratio B{ V.b_n, V.b_d };
+
+ enum class Method { StaticAB = 0,
+ StaticBA,
+ MulOperatorAB,
+ MulOperatorBA,
+ DivOperatorAB,
+ DivOperatorBA };
+ constexpr std::array METHODS = { Method::StaticAB,
+ Method::StaticBA,
+ Method::MulOperatorAB,
+ Method::MulOperatorBA,
+ Method::DivOperatorAB,
+ Method::DivOperatorBA };
+
+ for (auto method : METHODS) {
+ fit::function<void()> func;
+ affine::Ratio res;
+
+ // The operator forms demand exact results. Skip test vectors which
+ // expect non-exact results.
+ if ((V.exact == Exact::No) &&
+ (method != Method::StaticAB) &&
+ (method != Method::StaticBA)) {
+ continue;
+ }
+
+ // Division tests use the inversion operation to save some test
+ // vector space. Make sure to expect death instead of success if
+ // this would produce division by zero.
+ Fatal expect_fatal = ((method == Method::DivOperatorAB) && (B.numerator() == 0)) ||
+ ((method == Method::DivOperatorBA) && (A.numerator() == 0))
+ ? Fatal::Yes
+ : V.expect_fatal;
+
+ switch (method) {
+ case Method::StaticAB:
+ func = [&A, &B, &V, &res]() { res = affine::Ratio::Product(A, B, V.exact); };
+ break;
+ case Method::StaticBA:
+ func = [&A, &B, &V, &res]() { res = affine::Ratio::Product(B, A, V.exact); };
+ break;
+ case Method::MulOperatorAB: func = [&A, &B, &res]() { res = A * B; }; break;
+ case Method::MulOperatorBA: func = [&A, &B, &res]() { res = B * A; }; break;
+ case Method::DivOperatorAB: func = [&A, &B, &res]() { res = A / B.Inverse(); }; break;
+ case Method::DivOperatorBA: func = [&A, &B, &res]() { res = B / A.Inverse(); }; break;
+ }
+
+ if (expect_fatal == Fatal::No) {
+ func();
+ ASSERT_TRUE((res.numerator() == V.expected_n) &&
+ (res.denominator() == V.expected_d),
+ "Expected %u/%u * %u/%u to produce %u/%u; "
+ "got %u/%u instead (method %u).",
+ A.numerator(), A.denominator(),
+ B.numerator(), B.denominator(),
+ V.expected_n, V.expected_d,
+ res.numerator(), res.denominator(),
+ static_cast<uint32_t>(method));
+ } else {
+ ASSERT_DEATH(std::move(func), "Expected Death: %u/%u * %u/%u (method %u).",
+ A.numerator(), A.denominator(),
+ B.numerator(), B.denominator(),
+ static_cast<uint32_t>(method));
+ }
+ }
+ }
+}
+
+TEST(RatioTestCase, Scale) {
+ using Ratio = affine::Ratio;
+
+ struct TestVector {
+ int64_t val;
+ uint32_t n, d;
+ int64_t expected;
+ Fatal expect_fatal;
+ };
+
+ enum class Method { Static,
+ MulOperatorRatioVal,
+ MulOperatorValRatio,
+ DivOperator };
+
+ constexpr std::array TEST_VECTORS {
+ TestVector{ 0, 0, 1, 0, Fatal::No },
+ TestVector{ 1234567890, 0, 1, 0, Fatal::No },
+ TestVector{ 0, 1, 1, 0, Fatal::No },
+ TestVector{ 1234567890, 1, 1, 1234567890, Fatal::No },
+ TestVector{ 0, 1, 0, 0, Fatal::Yes },
+ TestVector{ 1234567890, 1, 0, 0, Fatal::Yes },
+ TestVector{ 198, 48000, 44100, 215, Fatal::No },
+ TestVector{ -198, 48000, 44100, -216, Fatal::No },
+ TestVector{ (49 * 198), 48000, 44100, 10560, Fatal::No },
+ TestVector{ -(49 * 198), 48000, 44100, -10560, Fatal::No },
+
+ // Overflow
+ TestVector{ std::numeric_limits<int64_t>::max(),
+ 1000001, 1000000, Ratio::kOverflow, Fatal::No },
+
+ // Underflow where we spill into the upper [64, 96) bit range
+ TestVector{ std::numeric_limits<int64_t>::min(),
+ 1000001, 1000000, Ratio::kUnderflow, Fatal::No },
+
+ // Underflow where bit 63 ends up set, and not all of the rest of the
+ // bits are zero.
+ TestVector{ -0x2000000000000001, 4, 1, Ratio::kUnderflow, Fatal::No },
+ };
+
+ constexpr std::array METHODS = { Method::Static,
+ Method::MulOperatorRatioVal,
+ Method::MulOperatorValRatio,
+ Method::DivOperator };
+
+ for (const auto& V : TEST_VECTORS) {
+ for (auto method : METHODS) {
+ fit::function<void()> func;
+ int64_t res;
+
+ // Expect failure if we plan to divide by a ratio with a zero
+ // numerator.
+ Fatal expect_fatal = (method == Method::DivOperator) && (V.n == 0)
+ ? Fatal::Yes
+ : V.expect_fatal;
+
+ switch (method) {
+ case Method::Static:
+ func = [&V, &res]() { res = Ratio::Scale(V.val, V.n, V.d); };
+ break;
+ case Method::MulOperatorRatioVal:
+ func = [&V, &res]() { res = Ratio{V.n, V.d} * V.val; };
+ break;
+ case Method::MulOperatorValRatio:
+ func = [&V, &res]() { res = V.val * Ratio{V.n, V.d}; };
+ break;
+ case Method::DivOperator:
+ func = [&V, &res]() { res = V.val / Ratio{V.d, V.n}; };
+ break;
+ }
+
+ if (expect_fatal == Fatal::No) {
+ func();
+ ASSERT_TRUE(res == V.expected,
+ "Expected %ld * %u/%u to produce %ld; got %ld instead (method %u).",
+ V.val, V.n, V.d, V.expected, res, static_cast<uint32_t>(method));
+ } else {
+ ASSERT_DEATH(std::move(func),
+ "Expected Death; %ld * %u/%u (method %u).",
+ V.val, V.n, V.d, static_cast<uint32_t>(method));
+ }
+ }
+ }
+}
+
+TEST(RatioTestCase, Inverse) {
+ struct TestVector { uint32_t N, D; };
+ constexpr std::array TEST_VECTORS {
+ TestVector{ 0, 1 },
+ TestVector{ 1, 1 },
+ TestVector{ 123456, 987654 },
+ };
+
+ for (const auto& V : TEST_VECTORS) {
+ affine::Ratio R{ V.N, V.D };
+
+ if (R.invertible()) {
+ affine::Ratio res = R.Inverse();
+ ASSERT_EQ(res.numerator(), R.denominator());
+ ASSERT_EQ(res.denominator(), R.numerator());
+ } else {
+ ASSERT_DEATH(([&R]() { R.Inverse(); }));
+ }
+ }
+}
diff --git a/zircon/system/ulib/affine/test/transform.cpp b/zircon/system/ulib/affine/test/transform.cpp
new file mode 100644
index 0000000..e6f377b
--- /dev/null
+++ b/zircon/system/ulib/affine/test/transform.cpp
@@ -0,0 +1,502 @@
+// Copyright 2019 The Fuchsia Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <array>
+#include <lib/affine/ratio.h>
+#include <lib/affine/transform.h>
+#include <lib/fit/function.h>
+#include <zxtest/zxtest.h>
+
+namespace {
+enum class Fatal { No, Yes };
+} // namespace
+
+TEST(TransformTestCase, Construction) {
+ // Default constructor should produce the identitiy transformation
+ {
+ affine::Transform transform;
+ ASSERT_EQ(transform.a_offset(), 0);
+ ASSERT_EQ(transform.b_offset(), 0);
+ ASSERT_EQ(transform.numerator(), 1);
+ ASSERT_EQ(transform.denominator(), 1);
+ ASSERT_TRUE(transform.ratio() == affine::Ratio(1, 1));
+ }
+
+ struct TestVector {
+ int64_t a_offset, b_offset;
+ uint32_t N, D;
+ Fatal expect_fatal;
+ };
+
+ constexpr std::array TEST_VECTORS {
+ TestVector{ 12345, 98764, 3, 2, Fatal::No },
+ TestVector{ -12345, 98764, 247, 931, Fatal::No },
+ TestVector{ -12345, -98764, 48000, 44100, Fatal::No },
+ TestVector{ 12345, -98764, 1000007, 1000000, Fatal::No },
+ TestVector{ 12345, 98764, 0, 1000000, Fatal::No },
+ TestVector{ 12345, 98764, 1000007, 0, Fatal::Yes },
+ };
+
+ for (const auto& V : TEST_VECTORS) {
+ // Check the linear form (no offsets)
+ if (V.expect_fatal == Fatal::No) {
+ affine::Ratio ratio{ V.N, V.D };
+ affine::Transform transform{ ratio };
+
+ ASSERT_EQ(transform.a_offset(), 0);
+ ASSERT_EQ(transform.b_offset(), 0);
+ ASSERT_EQ(transform.numerator(), ratio.numerator());
+ ASSERT_EQ(transform.denominator(), ratio.denominator());
+ ASSERT_TRUE(transform.ratio() == ratio);
+ } else {
+ ASSERT_DEATH(([&V]() { affine::Transform transform{ affine::Ratio{V.N, V.D} }; }));
+ }
+
+ // Check the affine form (yes offsets)
+ if (V.expect_fatal == Fatal::No) {
+ affine::Ratio ratio{ V.N, V.D };
+ affine::Transform transform{ V.a_offset, V.b_offset, ratio };
+
+ ASSERT_EQ(transform.a_offset(), V.a_offset);
+ ASSERT_EQ(transform.b_offset(), V.b_offset);
+ ASSERT_EQ(transform.numerator(), ratio.numerator());
+ ASSERT_EQ(transform.denominator(), ratio.denominator());
+ ASSERT_TRUE(transform.ratio() == ratio);
+ } else {
+ ASSERT_DEATH(([&V]() { affine::Transform transform{ V.a_offset,
+ V.b_offset,
+ affine::Ratio{V.N, V.D} };
+ }));
+ }
+ }
+}
+
+TEST(TransformTestCase, Equality) {
+ enum class Expected { Same = 0, Different };
+
+ struct TestVector {
+ affine::Transform transform;
+ Expected expected;
+ };
+
+ const std::array TEST_VECTORS {
+ TestVector{ { 10, 20, {1, 4}}, Expected::Same },
+ TestVector{ { 10, 20, {1, 4}}, Expected::Same },
+ TestVector{ { 10, 20, {2, 8}}, Expected::Same },
+ TestVector{ { 10, 20, {1, 5}}, Expected::Different },
+ TestVector{ { 11, 20, {1, 4}}, Expected::Different },
+ TestVector{ { 10, 19, {1, 4}}, Expected::Different },
+ };
+
+ for (const auto& a : TEST_VECTORS) {
+ for (const auto& b : TEST_VECTORS) {
+ // These test vectors should match if they are both in the "same"
+ // class, or if they are literally the same test vector.
+ if ((&a == &b) || ((a.expected == Expected::Same) && (b.expected == Expected::Same))) {
+ ASSERT_TRUE (a.transform == b.transform);
+ ASSERT_FALSE(a.transform != b.transform);
+ } else {
+ ASSERT_FALSE(a.transform == b.transform);
+ ASSERT_TRUE (a.transform != b.transform);
+ }
+ }
+ }
+}
+
+TEST(TransformTestCase, Inverse) {
+ struct TestVector {
+ int64_t a_offset, b_offset;
+ uint32_t N, D;
+ };
+
+ constexpr std::array TEST_VECTORS {
+ TestVector{ 12345, 98764, 3, 2 },
+ TestVector{ -12345, 98764, 247, 931 },
+ TestVector{ -12345, -98764, 48000, 44100 },
+ TestVector{ 12345, -98764, 1000007, 1000000 },
+ TestVector{ 12345, 98764, 0, 1000000 },
+ };
+
+ for (const auto& V : TEST_VECTORS) {
+ affine::Ratio ratio{ V.N, V.D };
+ affine::Transform transform{ V.a_offset, V.b_offset, ratio };
+
+ if (transform.invertible()) {
+ affine::Transform res = transform.Inverse();
+ ASSERT_EQ(transform.a_offset(), res.b_offset());
+ ASSERT_EQ(transform.b_offset(), res.a_offset());
+ ASSERT_EQ(transform.numerator(), res.denominator());
+ ASSERT_EQ(transform.denominator(), res.numerator());
+ ASSERT_TRUE(transform.ratio().Inverse() == res.ratio());
+ } else {
+ ASSERT_DEATH(([&transform]() { transform.Inverse(); }));
+ }
+ }
+}
+
+TEST(TransformTestCase, Apply) {
+ using Transform = affine::Transform;
+ using Saturate = affine::Transform::Saturate;
+
+ enum class Method { Static = 0, Object, Operator };
+ enum class Ovfl { No = 0, Yes };
+
+ struct TestVector {
+ int64_t a_offset, b_offset;
+ uint32_t N, D;
+ int64_t val;
+ int64_t expected;
+ Ovfl expect_ovfl;
+ };
+
+ constexpr int64_t kMinI64 = std::numeric_limits<int64_t>::min();
+ constexpr int64_t kMaxI64 = std::numeric_limits<int64_t>::max();
+ constexpr std::array TEST_VECTORS {
+ TestVector{ 0, 0, 1, 1, 12345, 12345, Ovfl::No },
+ TestVector{ 50, 0, 1, 1, 12345, 12295, Ovfl::No },
+ TestVector{ 0, -50, 1, 1, 12345, 12295, Ovfl::No },
+ TestVector{ 50, -50, 1, 1, 12345, 12245, Ovfl::No },
+ TestVector{ 50, 50, 1, 1, 12345, 12345, Ovfl::No },
+
+ TestVector{ 0, 0, 48000, 44100, 12345, 13436, Ovfl::No },
+ TestVector{ 50, 0, 48000, 44100, 12345, 13382, Ovfl::No },
+ TestVector{ 0, -54, 48000, 44100, 12345, 13382, Ovfl::No },
+ TestVector{ 50, -54, 48000, 44100, 12345, 13328, Ovfl::No },
+ TestVector{ 50, 54, 48000, 44100, 12345, 13436, Ovfl::No },
+
+ // Overflow/underflow during the A_offset stage.
+ TestVector{ -100, -17, 1, 1, kMaxI64 - 1, kMaxI64 - 17, Ovfl::Yes },
+ TestVector{ 100, 17, 1, 1, kMinI64 + 1, kMinI64 + 17, Ovfl::Yes },
+
+ // Overflow/underflow during the Scaling stage.
+ TestVector{ 0, -17, 3, 1, kMaxI64 / 2, kMaxI64 - 17, Ovfl::Yes },
+ TestVector{ 0, 17, 3, 1, kMinI64 / 2, kMinI64 + 17, Ovfl::Yes },
+
+ // Overflow/underflow during the B_offset stage.
+ TestVector{ 0, 17, 1, 1, kMaxI64 - 10, kMaxI64, Ovfl::Yes },
+ TestVector{ 0, -17, 1, 1, kMinI64 + 10, kMinI64, Ovfl::Yes },
+ };
+
+ constexpr std::array METHODS {
+ Method::Static,
+ Method::Object,
+ Method::Operator,
+ };
+
+ for (const auto& V : TEST_VECTORS) {
+ for (auto method : METHODS) {
+ // Test the forward transformation
+ Transform T{ V.a_offset, V.b_offset, { V.N, V.D } };
+ int64_t res_sat, res_nosat;
+
+ switch (method) {
+ case Method::Static:
+ res_sat = Transform::Apply(T.a_offset(), T.b_offset(), T.ratio(), V.val);
+ res_nosat = Transform::Apply<Saturate::No>(T.a_offset(),
+ T.b_offset(),
+ T.ratio(),
+ V.val);
+ break;
+
+ case Method::Object:
+ res_sat = T.Apply(V.val);
+ res_nosat = T.Apply<Saturate::No>(V.val);
+ break;
+
+ case Method::Operator:
+ res_sat = T(V.val);
+ res_nosat = T.operator()<Saturate::No>(V.val);
+ break;
+ }
+
+ auto CheckExpected = [&](int64_t actual,
+ const TestVector& V,
+ const Transform& T,
+ Method method) {
+ ASSERT_EQ(actual, V.expected,
+ "((%ld - %ld) * (%u/%u)) + %ld should be %ld; "
+ "got %ld instead (method %u)\n",
+ V.val,
+ T.a_offset(),
+ T.numerator(),
+ T.denominator(),
+ T.b_offset(),
+ V.expected,
+ actual,
+ static_cast<uint32_t>(method));
+
+ };
+
+ // Make sure the saturated result matches our expectations.
+ CheckExpected(res_sat, V, T, method);
+
+ // If we don't expect this test vector to overflow, then check to
+ // make sure that the non-saturated result matches the saturated
+ // result.
+ if (V.expect_ovfl == Ovfl::No) {
+ CheckExpected(res_nosat, V, T, method);
+ }
+
+ // Test inverse transformations operations, but only if the
+ // transformation is invertible. Otherwise test for death.
+ fit::function<void()> func_sat;
+ fit::function<void()> func_nosat;
+ switch (method) {
+ case Method::Static:
+ func_sat = [&T, &V, &res_sat]() {
+ if (T.invertible()) {
+ auto T_inv = T.Inverse();
+ res_sat = Transform::ApplyInverse(
+ T_inv.a_offset(), T_inv.b_offset(), T_inv.ratio(), V.val);
+ } else {
+ Transform::ApplyInverse(
+ T.a_offset(), T.b_offset(), T.ratio(), V.val);
+ }
+ };
+
+ func_nosat = [&T, &V, &res_nosat]() {
+ if (T.invertible()) {
+ auto T_inv = T.Inverse();
+ res_nosat = Transform::ApplyInverse<Saturate::No>(
+ T_inv.a_offset(), T_inv.b_offset(), T_inv.ratio(), V.val);
+ } else {
+ Transform::ApplyInverse<Saturate::No>(
+ T.a_offset(), T.b_offset(), T.ratio(), V.val);
+ }
+ };
+ break;
+
+ case Method::Object:
+ func_sat = [&T, &V, &res_sat]() {
+ if (T.invertible()) {
+ auto T_inv = T.Inverse();
+ res_sat = T_inv.ApplyInverse(V.val);
+ } else {
+ T.ApplyInverse(V.val);
+ }
+ };
+
+ func_nosat = [&T, &V, &res_nosat]() {
+ if (T.invertible()) {
+ auto T_inv = T.Inverse();
+ res_nosat = T_inv.ApplyInverse<Saturate::No>(V.val);
+ } else {
+ T.ApplyInverse<Saturate::No>(V.val);
+ }
+ };
+ break;
+
+ // Note: that the functor operator method has no inverse, so we skip
+ // the test in that case.
+ case Method::Operator:
+ continue;
+ }
+
+ if (T.invertible()) {
+ func_sat();
+ CheckExpected(res_sat, V, T, method);
+
+ if (V.expect_ovfl == Ovfl::No) {
+ CheckExpected(res_nosat, V, T, method);
+ }
+ } else {
+ auto CheckDeath = [](fit::function<void()> func,
+ const TestVector& V,
+ const Transform& T,
+ Method method) {
+ ASSERT_DEATH(std::move(func),
+ "((%ld - %ld) * (%u/%u)) + %ld should have resulted in death "
+ "(method %u)\n",
+ V.val,
+ T.a_offset(),
+ T.numerator(),
+ T.denominator(),
+ T.b_offset(),
+ static_cast<uint32_t>(method));
+ };
+ CheckDeath(std::move(func_sat), V, T, method);
+ CheckDeath(std::move(func_nosat), V, T, method);
+ }
+ }
+ }
+}
+
+TEST(TransformTestCase, Compose) {
+ using Transform = affine::Transform;
+
+ enum class Method { Static = 0, Operator };
+ enum class Exact { No = 0, Yes };
+
+ constexpr int64_t kMinI64 = std::numeric_limits<int64_t>::min();
+ constexpr int64_t kMaxI64 = std::numeric_limits<int64_t>::max();
+
+ struct TestVector {
+ Transform ab;
+ Transform bc;
+ Transform ac;
+ Exact is_exact;
+ };
+
+ // TODO(johngro) : If we ever make the Ratio/Transform constructors
+ // constexpr, then come back and make this constexpr. Right now, they are
+ // not because of the automatic reduction behavior of the Ratio constructor.
+ const std::array TEST_VECTORS {
+ // Identity(Identity(a)) == Identity(a)
+ TestVector{
+ { 0, 0, { 1, 1 } },
+ { 0, 0, { 1, 1 } },
+ { 0, 0, { 1, 1 } },
+ Exact::Yes
+ },
+
+ // F(Identity(a)) == F(a)
+ //
+ // TODO(MTWN-6): Note that this does not currently produce the exact
+ // same result, or even an equivalent result. The intermediate offset
+ // of the composition of bc(ab(a)) is -12345, and the current
+ // composition implementation always attempts to move this to the
+ // b_offset side of the composed function. In this case, that means
+ // running the -12345 through the 17/7 ratio, which results in some
+ // offset rounding error. For now, however, this is the expected
+ // behavior of the current implementation. If/when MTWN-6 is resolved,
+ // this test vector will start to fail and will need to be updated.
+ TestVector{
+ { 0, 0, { 1, 1 } },
+ { 12345, 98765, { 17, 7 } },
+ { 0, 68784, { 17, 7 } },
+ Exact::Yes
+ },
+
+ // Identity(F(a)) == F(a)
+ TestVector{
+ { 12345, 98765, { 17, 7 } },
+ { 0, 0, { 1, 1 } },
+ { 12345, 98765, { 17, 7 } },
+ Exact::Yes
+ },
+
+ // A moderately complicated example, but still an exact one.
+ // BC(AB(a)) == AC(a)
+ TestVector{
+ { 34327, 86539, { 1000007, 1000000 } },
+ { 728376, -34265, { 48000, 44100 } },
+ { 34327, -732864, { 1000007, 918750 } },
+ Exact::Yes
+ },
+
+ // Overflow saturation of the intermediate offset before distribution.
+ TestVector{
+ { 0, kMaxI64 - 5, { 1, 1 } },
+ { -100, 0, { 1, 1 } },
+ { 0, kMaxI64, { 1, 1 } },
+ Exact::Yes
+ },
+
+ // Underflow saturation of the intermediate offset before distribution.
+ TestVector{
+ { 0, kMinI64 + 5, { 1, 1 } },
+ { 100, 0, { 1, 1 } },
+ { 0, kMinI64, { 1, 1 } },
+ Exact::Yes
+ },
+
+ // Overflow saturation AC.b_offset after distribution.
+ TestVector{
+ { 0, 100, { 1, 1 } },
+ { 0, kMaxI64 - 5, { 1, 1 } },
+ { 0, kMaxI64, { 1, 1 } },
+ Exact::Yes
+ },
+
+ // Underflow saturation AC.b_offset after distribution.
+ TestVector{
+ { 0, -100, { 1, 1 } },
+ { 0, kMinI64 + 5, { 1, 1 } },
+ { 0, kMinI64, { 1, 1 } },
+ Exact::Yes
+ },
+
+ // TODO(MTWN-6): Right now, it is impossible to under/overflow saturate
+ // the AC.a_offset side of the composed function, because the current
+ // implementation always distributes the intermediate offset entirely to
+ // the C side of the equation. When this changes, we need to add test
+ // vectors to make sure that these cases behave properly.
+
+ // Composition of the ratio which requires a loss of precision. Note
+ // that these fractions were taken from the Ratio tests. Each numerator
+ // and denominator is made up of 3 prime numbers, none of them in
+ // common.
+ TestVector{
+ { 0, 0, { 3465653567, 2327655023 } },
+ { 0, 0, { 1291540343, 3698423317 } },
+ { 0, 0, { 317609835, 610852072 } },
+ Exact::No
+ },
+
+ // Same idea, but this time, include an intermediate offset. The offset
+ // should be distributed before the ratios are combined, resulting in no
+ // loss of precision (in this specific case) of the intermediate
+ // distribution.
+ TestVector{
+ { 0, 20, { 3465653567, 2327655023 } },
+ { -3698423317 + 20, 5, { 1291540343, 3698423317 } },
+ { 0, 1291540343 + 5, { 317609835, 610852072 } },
+ Exact::No
+ },
+ };
+
+ constexpr std::array METHODS {
+ Method::Static,
+ Method::Operator,
+ };
+
+ for (const auto& V : TEST_VECTORS) {
+ for (auto method : METHODS) {
+ fit::function<void()> func;
+ Transform result;
+
+ switch (method) {
+ case Method::Static:
+ func = [&result, &V]() { result = Transform::Compose(V.bc, V.ab); };
+ break;
+ case Method::Operator:
+ func = [&result, &V]() { result = V.bc * V.ab; };
+ break;
+ }
+
+ auto VerifyResult = [](const TestVector& V, const Transform& result, Method method) {
+ ASSERT_TRUE(result == V.ac,
+ "[ %ld : %u/%u : %ld ] <--> [ %ld : %u/%u : %ld ] should produce "
+ "[ %ld : %u/%u : %ld ] ; got [ %ld : %u/%u : %ld ] instead (method %u)",
+ V.ab.a_offset(), V.ab.numerator(), V.ab.denominator(), V.ab.b_offset(),
+ V.bc.a_offset(), V.bc.numerator(), V.bc.denominator(), V.bc.b_offset(),
+ V.ac.a_offset(), V.ac.numerator(), V.ac.denominator(), V.ac.b_offset(),
+ result.a_offset(), result.numerator(), result.denominator(),
+ result.b_offset(), static_cast<uint32_t>(method));
+ };
+
+ // If the composition is expected to produce an exact result, then
+ // compute and validate the result. Otherwise, assert that the
+ // composition operation produces death as expected.
+ if (V.is_exact == Exact::Yes) {
+ func();
+ VerifyResult(V, result, method);
+ } else {
+ ASSERT_DEATH(std::move(func), "Expected death during composition : "
+ "[ %ld : %u/%u : %ld ] <--> [ %ld : %u/%u : %ld ] (method %u)",
+ V.ab.a_offset(), V.ab.numerator(), V.ab.denominator(), V.ab.b_offset(),
+ V.bc.a_offset(), V.bc.numerator(), V.bc.denominator(), V.bc.b_offset(),
+ static_cast<uint32_t>(method));
+ }
+
+ // If this is not the operator form of composition, test the inexact
+ // version of composition. The expected result in the test vector
+ // should match the inexact result.
+ if (method == Method::Static) {
+ result = Transform::Compose(V.bc, V.ab, Transform::Exact::No);
+ VerifyResult(V, result, method);
+ }
+ }
+ }
+}
diff --git a/zircon/system/ulib/affine/transform.cpp b/zircon/system/ulib/affine/transform.cpp
new file mode 100644
index 0000000..aeac81b
--- /dev/null
+++ b/zircon/system/ulib/affine/transform.cpp
@@ -0,0 +1,16 @@
+// Copyright 2019 The Fuchsia Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <lib/affine/transform.h>
+
+namespace affine {
+
+Transform Transform::Compose(const Transform& bc, const Transform& ab, Exact exact) {
+ // TODO(MTWN-6)
+ return Transform(ab.a_offset(),
+ bc.Apply(ab.b_offset()),
+ Ratio::Product(ab.ratio(), bc.ratio(), exact));
+}
+
+} // namespace affine
diff --git a/zircon/system/utest/BUILD.gn b/zircon/system/utest/BUILD.gn
index 7ec4c46..1381f2f 100644
--- a/zircon/system/utest/BUILD.gn
+++ b/zircon/system/utest/BUILD.gn
@@ -67,6 +67,7 @@
"$zx/system/uapp/disk-pave:install-disk-image-test",
"$zx/system/uapp/nand-util:nand-util-test",
"$zx/system/uapp/thermal-cli:thermal-cli-test",
+ "$zx/system/ulib/affine/test",
"$zx/system/ulib/async-loop/test",
"$zx/system/ulib/async-testutils/test",
"$zx/system/ulib/async/test",
