zircon/system/ulib/ffl/include/ffl/fixed.h

// Copyright 2018 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 FFL_FIXED_H_
#define FFL_FIXED_H_

//
// Fuchsia Fixed-point Library (FFL):
//
// An efficient header-only multi-precision fixed point math library with well-
// defined rounding.
//

#include <cstddef>
#include <type_traits>

#include <ffl/expression.h>
#include <ffl/fixed_format.h>
#include <ffl/saturating_arithmetic.h>
#include <ffl/utility.h>

namespace ffl {

// Represents a fixed-point value using the given integer base type |Integer|
// and the given number of fractional bits |FractionalBits|. This type supports
// standard arithmetic operations and comparisons between the same type, fixed-
// point types with different precision/resolution, and integer values.
//
// Arithmetic operations are not immediately computed. Instead, arithmetic
// expressions involving fixed-point types are assembled into intermediate
// expression trees (via the Expression template type) that capture operands and
// order of operations. The value of the expression tree is evaluated when it is
// assigned to a fixed-point variable. Using this approach the precision and
// resolution of intermediate values are selected at compile time, based on the
// final precision and resolution of the destination variable.
//
// See README.md for a more detailed discussion of fixed-point arithmetic,
// rounding, precision, and resolution in this library.
//
template <typename Integer, size_t FractionalBits>
class Fixed {
 public:
  // Alias of the FixedFormat type describing traits and low-level operations
  // on the fixed-point representation of this type.
  using Format = FixedFormat<Integer, FractionalBits>;

  // Returns the given raw integer as a fixed-point value in this format.
  static constexpr Fixed FromRaw(Integer value) {
    return ValueExpression<Integer, FractionalBits>{value};
  }

  // Returns the minimum value of this fixed point format.
  static constexpr Fixed Min() { return FromRaw(Format::Min); }

  // Returns the maximum value of this fixed point format.
  static constexpr Fixed Max() { return FromRaw(Format::Max); }

  // Fixed is default constructible without a default value, which is the same
  // as for plain integer types. This is permitted in constexpr contexts as
  // long as the underling integer member |value_| is initialized before use.
  constexpr Fixed() = default;

  // Fixed is copy constructible and assignable.
  constexpr Fixed(const Fixed&) = default;
  constexpr Fixed& operator=(const Fixed&) = default;

  // Explicit conversion from an integer value. The value is saturated to fit
  // within the integer precision defined by Format::IntegerBits.
  explicit constexpr Fixed(Integer value) : Fixed{ToExpression<Integer>{value}} {}

  // Implicit conversion from an intermediate expression. The value is converted
  // to the precision and resolution of this type, if necessary.
  template <Operation Op, typename... Args>
  constexpr Fixed(Expression<Op, Args...> expression)
      : Fixed{Format::Convert(expression.Evaluate(Format{}))} {}

  // Explicit conversion from another fixed point type. The value is converted
  // to the precision and resolution of this type, if necessary.
  template <typename OtherInteger, size_t OtherFractionalBits,
            typename = std::enable_if_t<!std::is_same_v<Integer, OtherInteger> ||
                                        FractionalBits != OtherFractionalBits>>
  explicit constexpr Fixed(const Fixed<OtherInteger, OtherFractionalBits>& other)
      : Fixed{Format::Convert(other.value())} {}

  // Assignment from an intermediate expression. The value is rounded and
  // saturated to fit within the precision and resolution of this type, if
  // necessary.
  template <Operation Op, typename... Args>
  constexpr Fixed& operator=(Expression<Op, Args...> expression) {
    return *this = Fixed{expression};
  }

  // Implicit conversion from an intermediate value of the same format.
  constexpr Fixed(Value<Format> value) : value_{Format::Saturate(value)} {}

  // Assignment from an intermediate value of the same format.
  constexpr Fixed& operator=(Value<Format> value) { return *this = Fixed{value}; }

  // Returns the raw fixed-point value as the underling integer type.
  constexpr Integer raw_value() const { return value_; }

  // Returns the fixed-point value as an intermediate value type.
  constexpr Value<Format> value() const { return Value<Format>{value_}; }

  // Returns the closest integer value greater-than or equal-to this fixed-
  // point value.
  constexpr Integer Ceiling() const {
    const Integer value = value_ / Format::AdjustmentFactor;
    const Integer power = Format::AdjustedPower;
    const auto saturated_value = Format::IsUnsigned || value >= 0
                                     ? SaturateAddAs<Integer>(value, Format::AdjustedFractionalMask)
                                     : value;
    return static_cast<Integer>(saturated_value / power);
  }

  // Returns the closest integer value less-than or equal-to this fixed-point
  // value.
  constexpr Integer Floor() const {
    const Integer value = value_ / Format::AdjustmentFactor;
    const Integer power = Format::AdjustedPower;
    const Integer masked_value = value & Format::AdjustedIntegralMask;
    return static_cast<Integer>(masked_value / power);
  }

  // Returns the rounded value of this fixed-point value as an integer.
  constexpr Integer Round() const {
    const Integer value = value_ / Format::AdjustmentFactor;
    const Integer power = Format::AdjustedPower;
    const Integer rounded_value = Format::Round(value, ToPlace<Format::AdjustedFractionalBits>);
    return Format::Saturate(static_cast<Integer>(rounded_value / power));
  }

  // Returns the integral component of this fixed-point value. The result retains
  // the sign of this value. For example, Fixed{-2.5}.Integral() == -2.
  //
  // This preserves the following invariant:
  //
  //   Fixed f;
  //   f.Integral() + f.Fraction() == f
  //
  constexpr Fixed Integral() const {
    if constexpr (Format::IntegralBits == 0) {
      if constexpr (Format::IsSigned) {
        if (*this <= Fixed{-1}) {
          return Fixed{-1};
        }
      }
      return Fixed{0};
    } else {
      return Fixed(value_ / static_cast<Integer>(Format::Power));
    }
  }

  // Returns the fractional component of this fixed-point value. The result retains
  // the sign of this value. For example, Fixed(-2.5).Fraction() == -0.5.
  //
  // See Integral().
  constexpr Fixed Fraction() const { return *this - Integral(); }

  // Returns the absolute value of this fixed-point value.
  constexpr Fixed Absolute() const {
    // Compute a mask and bit to conditionally convert |value_| to positive.
    // When |value_| is negative, then |mask| = -1 and |one| = 1, otherwise both
    // are zero.
    const Integer mask = static_cast<Integer>(-(value_ < 0));
    const Integer one = mask & 1;

    // Find the absolute value by computing the clamped two's complement. This
    // is a no-op when |value_| is positive because |mask| and |one| are zero.
    // Note that this will always return a positive value by clamping to Max.
    Integer absolute = 0;
    if (__builtin_add_overflow(value_ ^ mask, one, &absolute)) {
      absolute = Format::Max;
    }
    return FromRaw(absolute);
  }

  // Relational operators for same-typed values.
  constexpr bool operator<(Fixed other) const { return value_ < other.value_; }
  constexpr bool operator>(Fixed other) const { return value_ > other.value_; }
  constexpr bool operator<=(Fixed other) const { return value_ <= other.value_; }
  constexpr bool operator>=(Fixed other) const { return value_ >= other.value_; }
  constexpr bool operator==(Fixed other) const { return value_ == other.value_; }
  constexpr bool operator!=(Fixed other) const { return value_ != other.value_; }

  // Compound assignment operators.
  template <typename T, typename Enabled = EnableIfUnaryExpression<T>>
  constexpr Fixed& operator+=(T expression) {
    *this = *this + expression;
    return *this;
  }
  template <typename T, typename Enabled = EnableIfUnaryExpression<T>>
  constexpr Fixed& operator-=(T expression) {
    *this = *this - expression;
    return *this;
  }
  template <typename T, typename Enabled = EnableIfUnaryExpression<T>>
  constexpr Fixed& operator*=(T expression) {
    *this = *this * expression;
    return *this;
  }
  template <typename T, typename Enabled = EnableIfUnaryExpression<T>>
  constexpr Fixed& operator/=(T expression) {
    *this = *this / expression;
    return *this;
  }

 private:
  Integer value_;
};

// Utility to round an expression to the given Integer.
template <typename Integer, typename T, typename Enabled = EnableIfUnaryExpression<T>>
inline constexpr auto Round(T expression) {
  const Fixed<Integer, 0> value{ToExpression<T>{expression}};
  return value.Round();
}

// Utility to create an Expression node from an integer value.
template <typename Integer, typename Enabled = std::enable_if_t<std::is_integral_v<Integer>>>
inline constexpr auto FromInteger(Integer value) {
  return ToExpression<Integer>{value};
}

// Utility to create an Expression node from an integer ratio. May be used to
// initialize a Fixed variable from a ratio.
template <typename Integer, typename Enabled = std::enable_if_t<std::is_integral_v<Integer>>>
inline constexpr auto FromRatio(Integer numerator, Integer denominator) {
  return DivisionExpression<Integer, Integer>{numerator, denominator};
}

// Utility to coerce an expression to the given resolution.
template <size_t FractionalBits, typename T>
inline constexpr auto ToResolution(T expression) {
  return ResolutionExpression<FractionalBits, T>{Init{}, expression};
}

// Utility to create a value Expression from a raw integer value already in the
// fixed-point format with the given number of fractional bits.
template <size_t FractionalBits, typename Integer>
inline constexpr auto FromRaw(Integer value) {
  return ValueExpression<Integer, FractionalBits>{value};
}

// Relational operators.
//
// Fixed-to-fixed comparisons convert to an intermediate type with suitable
// precision and the least resolution of the two operands, using convergent
// rounding to reduce resolution and avoid bias.
//
// Fixed-to-integer comparisons convert to an intermediate type with suitable
// precision and the resolution of the fixed-point type. This is less
// less surprising when comparing a fixed-point type to zero and other integer
// constants.
template <typename Left, typename Right,
          typename Enabled = EnableIfComparisonExpression<Left, Right>>
inline constexpr bool operator<(Left left, Right right) {
  using Traits = ComparisonTraits<Left, Right>;
  return Traits::Left(left) < Traits::Right(right);
}
template <typename Left, typename Right,
          typename Enabled = EnableIfComparisonExpression<Left, Right>>
inline constexpr bool operator>(Left left, Right right) {
  using Traits = ComparisonTraits<Left, Right>;
  return Traits::Left(left) > Traits::Right(right);
}
template <typename Left, typename Right,
          typename Enabled = EnableIfComparisonExpression<Left, Right>>
inline constexpr bool operator<=(Left left, Right right) {
  using Traits = ComparisonTraits<Left, Right>;
  return Traits::Left(left) <= Traits::Right(right);
}
template <typename Left, typename Right,
          typename Enabled = EnableIfComparisonExpression<Left, Right>>
inline constexpr bool operator>=(Left left, Right right) {
  using Traits = ComparisonTraits<Left, Right>;
  return Traits::Left(left) >= Traits::Right(right);
}
template <typename Left, typename Right,
          typename Enabled = EnableIfComparisonExpression<Left, Right>>
inline constexpr bool operator==(Left left, Right right) {
  using Traits = ComparisonTraits<Left, Right>;
  return Traits::Left(left) == Traits::Right(right);
}
template <typename Left, typename Right,
          typename Enabled = EnableIfComparisonExpression<Left, Right>>
inline constexpr bool operator!=(Left left, Right right) {
  using Traits = ComparisonTraits<Left, Right>;
  return Traits::Left(left) != Traits::Right(right);
}

// Arithmetic operators. These operators accept any combination of Fixed,
// integer, and Expression (excluding integer/integer which is handled by the
// language). The return type and value captures the operation and operands as
// an Expression for later evaluation. Evaluation is performed when the
// Expression tree is assigned to a Fixed variable. This can be composed in
// multiple stages and assignments.
//
// Example:
//
//     const int32_t value = ...;
//     cosnt int32_t offset = ...;
//
//     const auto quotient = FromRatio(value, 3);
//     const Fixed<int32_t, 1> low_precision = quotient;
//     const Fixed<int64_t, 10> high_precision = quotient;
//
//     const auto with_offset = quotient + ToResolution<10>(offset);
//     const Fixed<int64_t, 10> high_precision_with_offset = with_offset;
//
template <typename Left, typename Right, typename Enabled = EnableIfBinaryExpression<Left, Right>>
inline constexpr auto operator+(Left left, Right right) {
  return AdditionExpression<Left, Right>{left, right};
}
template <typename T, typename Enabled = EnableIfUnaryExpression<T>>
inline constexpr auto operator-(T value) {
  return NegationExpression<T>{Init{}, value};
}
template <typename Left, typename Right, typename Enabled = EnableIfBinaryExpression<Left, Right>>
inline constexpr auto operator-(Left left, Right right) {
  return SubtractionExpression<Left, Right>{left, right};
}
template <typename Left, typename Right, typename Enabled = EnableIfBinaryExpression<Left, Right>>
inline constexpr auto operator*(Left left, Right right) {
  return MultiplicationExpression<Left, Right>{left, right};
}
template <typename Left, typename Right, typename Enabled = EnableIfBinaryExpression<Left, Right>>
inline constexpr auto operator/(Left left, Right right) {
  return DivisionExpression<Left, Right>{left, right};
}

}  // namespace ffl

#endif  // FFL_FIXED_H_