tree: 10886d7cdeedd2257c6e09a95aa17bd381acfa32 [path history] [tgz]

zircon/system/ulib/ffl/README.md

FFL is a C++ template library for fixed-point arithmetic. The library is primarily intended to support the Zircon kernel scheduler however, it is sufficiently general to be useful wherever fixed-point computations are needed.

FFL is motivated by the following requirements:

- Availability: Fixed-point support is not yet ratified in the standard library. We need a solution today.
- Dependency: Many alternatives require additional dependencies. We prefer to depend only on the standard library.
- Rounding: Many alternatives, including the proposal for the standard library, have poor or ill-defined rounding behavior. We need well-defined rounding with reasonable general-purpose stability, such as convergent rounding.

The main user-facing type in FFL is the value template type `ffl::Fixed<typename Integer, size_t FractionalBits>`

. This template accepts an integer type for the underlying value and the number of bit to use to represent the fractional component. Naturally, the range of the integer component of the fixed-point value is defined by the difference between the number of bits of the underlying integer type and the number of bits reserved for the fractional part.

`ffl::Fixed`

behaves similarly to plain integers. The type supports most of the same arithmetic operators: addition, subtraction, negation, multiplication, and division, as well as all of the comparison operators.

#include <ffl/fixed.h> using ffl::Fixed; Fixed<int32_t, 31> UnitaryRatio(Fixed<int32_t, 0> a, Fixed<int32_t, 0> b) { if (a > b) return b / a; else return a / b; } Fixed<uint8_t, 0> Blend(Fixed<uint8_t, 0> color0, Fixed<uint8_t, 0> color1, Fixed<uint8_t, 8> alpha) { return alpha * color0 + (Fixed<uint8_t, 8>{1} - alpha) * color1; }

FFL supports arithmetic and comparisons with mixed precisions. These operations may consider both the source and destination precisions at compile time to select an appropriate strategy for intermediate computations.

In order to consider the destination precision, the evaluation of an expression involving `ffl::Fixed`

values is deferred until the expression is assigned to a `ffl::Fixed`

variable. To facilitate this deferred evaluation, the arithmetic operators return instances of the template type `ffl::Expression`

, which captures the arithmetic operation and the arguments involved. The arguments may be instances of `ffl::Fixed`

, plain integers, or other instances of `ffl::Expression`

returned by other operators and utility functions. With this approach, compound expressions result in expression trees that follow the C++ order of operations.

In many cases the use of expression trees is transparent to the user, as in the following example:

#include <ffl/fixed.h> using ffl::Fixed; struct Point2d { Fixed<int16_t, 0> x; Fixed<int16_t, 0> y; }; Point2d LinearInterpolate(Point2d p0, Point2d p1, Fixed<int32_t, 16> t) { return {p0.x + t * (p1.x - p0.x), p0.y + t * (p1.y - p0.y)}; }

In this example the arithmetic expressions and assignments happen together and there is no need to consider the intermediate Expression objects.

In some cases it is useful to be aware of the intermediate Expression objects. The following example uses intermediate expressions to make the overall computation more readable:

#include <ffl/fixed.h> using ffl::Fixed; // TODO

FFL uses the following rules when performing mixed precision arithmetic:

- Addition and subtraction convert to the greatest precision and least resolution of the two operands before computing an intermediate result.
- Multiplication produces an intermediate result with precision and resolution sufficient to hold the sum of both the fractional and integral bit depths of the operands.
- Division produces an intermediate result with the resolution of the target format.

Comparisons convert to the least resolution of the two operands before performing the comparison. However, when comparing a fixed-point value with a plain integer, the values are converted to an intermediate type with sufficient precision and the resolution of the fixed-point argument.

Saturation is one important difference between fixed-point arithmetic in FFL and regular integer arithmetic. Regular integer arithmetic over or underflows when the result exceeds the range of the integral type. In contrast, FFL uses intermediate values with sufficient range for the computation. When an intermediate value is finally assigned to a fixed-point variable the value is clamped to precision of the destination type.

Some arithmetic operations take the target resolution into account when computing intermediate values (only division at the time of this writing). The target resolution may be influenced using the `ToResolution<FractionalBits>()`

utility function. This utility functions by inserting a resolution node into the expression tree at the point of invocation; deeper nodes that consider target resolution will consider the resolution given by this node instead of the final resolution.

#include <ffl/fixed.h> using ffl::Fixed; using ffl::Round; using ffl::ToResolution; constexpr int32_t Divide(int32_t numerator, int32_t denominator) { const Fixed<int32_t, 0> fixed_numerator{numerator}; const Fixed<int32_t, 0> fixed_denominator{denominator}; // Perform division with 2bit fractional resolution for optimum convergent // rounding of the quotient. return Round<int32_t>(ToResolution<2>(fixed_numerator / fixed_denominator)); }