zircon/system/ulib/affine/include/lib/affine/transform.h

// 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/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 independently.  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 utils::ClampAdd(ratio.Scale(utils::ClampSub(val, a_offset)), b_offset);
    }
    if constexpr (SATURATE == Saturate::No) {
      // 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 AddUnchecked((SubUnchecked(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) : 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);

 private:
  static inline int64_t AddUnchecked(int64_t a, int64_t b) { return a + b; }

  static inline int64_t SubUnchecked(int64_t a, int64_t b) { return a - b; }

  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

#endif  // LIB_AFFINE_TRANSFORM_H_