blob: d7909f14e76520afff4ef19fbbe14592cc5499d7 [file] [log] [blame]
// Copyright 2018 The Fuchsia Authors
//
// Use of this source code is governed by a MIT-style
// license that can be found in the LICENSE file or at
// https://opensource.org/licenses/MIT
#pragma once
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <ffl/utility.h>
namespace ffl {
// Forward declaration.
template <typename Integer, size_t FractionalBits>
struct FixedFormat;
// Type representing an intermediate value of a given FixedFormat.
template <typename>
struct Value;
template <typename Integer, size_t FractionalBits>
struct Value<FixedFormat<Integer, FractionalBits>> {
using Format = FixedFormat<Integer, FractionalBits>;
using Intermediate = typename Format::Intermediate;
explicit constexpr Value(Intermediate value)
: value{value} {}
const Intermediate value;
};
// Type representing the format of a fixed-point value in terms of the
// underlying integer type and fractional precision. Provides key constants and
// operations for fixed-point computation and format manipulation.
template <typename Integer_, size_t FractionalBits_>
struct FixedFormat {
// The underlying integral type of the fixed-point values in this format.
using Integer = Integer_;
// The intermediate integral type used by computations in this format.
using Intermediate = typename IntermediateType<Integer>::Type;
// Numeric constants for fixed-point computations.
static constexpr size_t Bits = sizeof(Integer) * 8;
static constexpr size_t IntermediateBits = sizeof(Intermediate) * 8;
static constexpr size_t FractionalBits = FractionalBits_;
static constexpr size_t IntegralBits = Bits - FractionalBits;
static constexpr size_t Power = 1 << FractionalBits;
static constexpr Integer One = 1; // Typed constant used in shifts below.
static constexpr Integer FractionalMask = Power - 1;
static constexpr Integer IntegralMask = ~FractionalMask;
static constexpr Integer SignBit = std::is_signed_v<Integer> ? One << (Bits - 1) : 0;
static constexpr Integer BinaryPoint = FractionalBits > 0 ? One << (FractionalBits - 1) : 0;
static constexpr Integer OnesPlace = One << FractionalBits;
static constexpr Integer Min = std::numeric_limits<Integer>::min();
static constexpr Integer Max = std::numeric_limits<Integer>::max();
static constexpr Integer IntegralMin = static_cast<Integer>(Min / Power);
static constexpr Integer IntegralMax = static_cast<Integer>(Max / Power);
// Assert that the template arguments are valid.
static_assert(std::is_integral_v<Integer>,
"The Integer template parameter must be an integral type!");
static_assert((std::is_signed_v<Integer> && FractionalBits < Bits) ||
(!std::is_signed_v<Integer> && FractionalBits <= Bits),
"The number of fractional bits must fit within the positive bits!");
// Trivially converts from Integer to Intermediate type.
static constexpr Intermediate ToIntermediate(Intermediate value) {
return value;
}
// Saturates an intermediate value to the valid range of the base type.
static constexpr Integer Saturate(Intermediate value) {
const Intermediate clamped = std::clamp(value, Intermediate{Min}, Intermediate{Max});
return static_cast<Integer>(clamped);
}
static constexpr Integer Saturate(Value<FixedFormat> value) {
return Saturate(value.value);
}
// Rounds |value| to the given significant bit |Place| using the convergent,
// or round-half-to-even, method to eliminate positive/negative and
// towards/away from zero biases. This is the default rounding mode used in
// IEEE 754 computing functions and operators.
//
// References:
// https://en.wikipedia.org/wiki/Rounding#Round_half_to_even
// https://en.wikipedia.org/wiki/Nearest_integer_function
//
// Optimization Analysis:
// https://godbolt.org/z/Cozc9r
//
// For example, rounding an 8bit value to bit 4 produces these values in the
// constants defined below:
//
// uint8_t value = vvvphmmm
//
// PlaceBit = 00010000 -> 000p0000
// PlaceMask = 11110000 -> vvvp0000
// HalfBit = 00001000 -> 0000h000
// HalfMask = 00000111 -> 00000mmm
// PlaceShift = 2
//
// Rounding half to even is computed as follows:
//
// PlaceBit = 00010000
// value = vvvvvvvv
// & -------------------
// 000p0000
// PlaceShift 2
// >> -------------------
// odd_bit 00000p00
// HalfMask 00000111
// value vvvvvvvv
// + -------------------
// rrrrxxxx
// PlaceMask 11110000
// & -------------------
// rounded rrrr0000
//
template <size_t Place>
static constexpr Intermediate Round(Intermediate value, Bit<Place>) {
// Bit of the significant figure to round to and mask of the significant
// bits after rounding.
const Intermediate PlaceBit = 1 << Place;
const Intermediate PlaceMask = ~(PlaceBit - 1);
// Bit representing one half of the significant figure to round to
// and mask of the bits below it, if any.
const Intermediate HalfBit = 1 << (Place - 1);
const Intermediate HalfMask = Place > 1 ? HalfBit - 1 : 0;
// Shift representing where to add the odd bit when rounding to even.
const size_t PlaceShift = Place > 1 ? 2 : 1;
// 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. This optimizes out when |value| is unsigned.
const Intermediate mask = static_cast<Intermediate>(-(value < 0));
const Intermediate one = mask & 1;
// Compute the absolute value of |value| using two's complement. This
// optimizes out when |value| is unsigned.
const auto absolute = static_cast<Intermediate>((value ^ mask) + one);
// Round half to even.
const Intermediate odd_bit = (absolute & PlaceBit) >> PlaceShift;
const auto rounded = static_cast<Intermediate>((absolute + HalfMask + odd_bit) & PlaceMask);
// Restore original sign. This optimizes out when |value| is unsigned.
return static_cast<Intermediate>((rounded ^ mask) + one);
}
// Rounding to the 0th bit is a no-op.
static constexpr Intermediate Round(Intermediate value, Bit<0>) {
return value;
}
// Rounds the intermediate |value| around the integer position.
static constexpr Intermediate Round(Intermediate value) {
return Round(value, ToPlace<FractionalBits>);
}
// Converts an intermediate value in SourceFormat to this format, rounding
// as necessary.
template <typename SourceFormat>
static constexpr Value<FixedFormat> Convert(Value<SourceFormat> value) {
using IntermediateFormat = std::conditional_t<SourceFormat::Bits >= Bits,
SourceFormat, FixedFormat>;
using ValueType = typename IntermediateFormat::Intermediate;
if constexpr (SourceFormat::FractionalBits >= FractionalBits) {
const size_t delta = SourceFormat::FractionalBits - FractionalBits;
const ValueType power = ValueType{1} << delta;
const ValueType converted_value =
IntermediateFormat::Round(value.value, ToPlace<delta>) / power;
return Value<FixedFormat>{static_cast<Intermediate>(converted_value)};
} else {
const size_t delta = FractionalBits - SourceFormat::FractionalBits;
const ValueType power = ValueType{1} << delta;
const ValueType converted_value = static_cast<ValueType>(value.value * power);
return Value<FixedFormat>{static_cast<Intermediate>(converted_value)};
}
}
// Converting to the same format is a no-op.
static constexpr Value<FixedFormat> Convert(Value<FixedFormat> value) {
return value;
}
};
} // namespace ffl