blob: a6a98088c84eb4337718b2c3713bb414be8816c7 [file] [log] [blame]
// 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/assert.h>
#include <lib/affine/ratio.h>
#include <lib/affine/utils.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 {
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 utils::ClampAdd(ratio.Scale(utils::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 {
internal::DebugAssert(ratio_.denominator() != 0);
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);
int64_t a_offset_ = 0;
int64_t b_offset_ = 0;
Ratio ratio_{1, 1};
// 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