[cfe-dev] Fixed Point Arithmetic Proposal

[Leonard Chan via cfe-dev]

Sorry about the formatting in the previous one. Here's an updated one in
plain text.

The C extensions to support embedded processors defined in chapter 4 of
ISO/IEC TR 18037 [1] defines support for fixed-point arithmetic and fixed
point data types in C. Fixed-point data values are either fractional data
values, or data values with an integral part and a fractional part. Typical
usage of fixed-point data values and operations can be found in
applications that convert analogue values to digital representations and
subsequently apply some filtering algorithm. This is especially common in
digital signal processing.

GNU C Compiler (GCC) already implements this extension [2]. We would like
to support fixed-point arithmetic in Fuchsia [3], where it could be
beneficial in components like drivers which perform signal processing.
However, Fuchsia uses Clang/LLVM as its C/C++ toolchain where the
fixed-point arithmetic extensions are not yet implemented.

We would like to implement support for fixed-point arithmetic in Clang.
Initially we would like to modify the frontend to add support for
fixed-point data types, compiler headers (i.e. stdfix.h) and lowering the
fixed-point arithmetic to integer. In the future, we might also extend the
backend to support fixed-point data types natively in the LLVM IR which
would enable more optimizations including lowering to hardware targets that
have native support for fixed-point arithmetic.

# C Frontend Changes

The following high level changes would be made to Clang:

- Addition of the following fixed-point types (clause 4.1.1):

```
(Primary fixed-point types)
unsigned short _Fract .8 unsigned short _Accum 8.8
unsigned _Fract .16 unsigned _Accum 16.16
unsigned long _Fract .32 unsigned long _Accum 32.32
signed short _Fract s.7 signed short _Accum s8.7
signed _Fract s.15 signed _Accum s16.15
signed long _Fract s.31 signed long _Accum s32.31

(Aliased fixed-point types: these are aliases for the corresponding signed
types)
short _Fract short _Accum
_Fract _Accum
long _Fract long _Accum

(Saturated fixed-point types)
_Sat unsigned short _Fract _Sat unsigned short _Accum
_Sat unsigned _Fract _Sat unsigned _Accum
_Sat unsigned long _Fract _Sat unsigned long _Accum
_Sat signed short _Fract _Sat signed short _Accum
_Sat signed _Fract _Sat signed _Accum
_Sat signed long _Fract _Sat signed long _Accum
```
   - The above bit formats are the recommended formats for a typical desktop
processor (Annex A.3), though the integral and fractional bit lengths can
be adjusted with the macros under clause 7.18a.3.

   - The standard does not explicitly require equivalent fixed-point support
for the `long long` type (Annex A.1.1.3). We would need to decide on a
minimal bit format for the corresponding `long long` types.

   - The underlying bits of each type are divided into padding, fractional,
integral, and sign bits. Represented in Q notation [4], the minimal number
of bits assigned to each type are given above. The number of integral and
fractional bits can be assigned through preprocessor macros (clause
7.18a.3). Recommended bit layouts are provided in Annex A.3. Specific
restrictions on any other custom layouts for these types are given in
clause 6.2.6.3.

- Natural spelling of the keywords _Fract (fract), _Accum (accum), and _Sat
(sat) defined in <stdfix.h> (clause 4.1.8).

- Support for pragmas FX_FRACT_OVERFLOW and FX_ACCUM_OVERFLOW for
controlling overflow in the absence of an explicit saturating fixed-point
type (clause 4.1.3). The states of these pragmas are SAT and DEFAULT where
SAT enables saturated rounding for the default _Fract and _Accum types.
DEFAULT is implementation specific and will simply be a modular wraparound.

- Support for conversion between signed/unsigned fixed-point types and
integral or floating point types (clause 4.1.4).
   - Signed fixed-point + unsigned fixed-point = signed fixed-point
   - Fixed-point + integral = fixed-point
   - Fixed-point + floating-point = floating-point
     - Conversion from a fixed point to floating point is unspecified and
implementation specific. Since our changes are to the C frontend and the
underlying representation of these fixed point types are integers,
conversion to a float can simply be dividing the fixed point type, as an
integer, by the 2^(the number of fractional bits) as a float. ie.
`fixed_as_short / ((1 << SACCUM_FBIT) * 1.0)`

- Addition of the following fixed-point suffixes (clause 4.1.5):
```
hr: short _Fract
uhr: unsigned short _Fract
r: _Fract ur unsigned _Fract
lr: long _Fract
ulr: unsigned long _Fract
hk: short _Accum
uhk: unsigned short _Accum
k: _Accum
uk: unsigned _Accum
lk: long _Accum
ulk: unsigned long _Accum
```

- Support for operations involving fixed-point types (clause 4.1.6)
   - Unary (++, --, +, -, !)
     - ++ and -- have their usual meaning of incrementing/decrementing the
integral part
     - The 2s complement of a fixed point type is taken with `+` if it is
negative or `-` if it is positive.
     - The result of logical negation (!) on a fixed point type is 0 if the
the operand compares unequal to 0 and 1 if the operand compares equal to 0,
with the result as an int.
   - Binary (+, -, *, /, <<, >>)
     - Addition and subtraction are done normally like with integers.
       - `a + b`, `a - b`
     - Multiplication is done normally like with integers, but the resulting
value is bit shifted right by the number of fractional bits used. Casting
to a larger type is necessary to account for storage of the larger
resulting value
       - `(short)(((int)a * (int)b) >> SACCUM_FBIT)`
     - Division is done normally like with integers, but the dividend is bit
shifted left by the number of fractional bits used.
       - `(short)(((int)a << SACCUM_FBIT) / b)`
     - `<<` and `>>` are defined to be equivalent to multiplication or
division by a power of 2.
   - Comparison (<, <=, >=, >, ==, !=)
     - All comparisons are done normally as if the types were integers.
   - Assignment (+=, -=, *=, /=, <<=, >>=)
   - Bitwise NOT (~) and modulo (%) are not supported for fixed-point types.
   - For conversion between different ranked/sized fixed point numbers, the
smaller ranked/sized fixed point type is promoted to the higher
ranked/sized type.
   - Overflow is calculated according to clause 4.1.3. If the fixed point
types are saturated, then the 2 added values are temporarily stored as
larger values to account for overflow and rounding to the highest or lowest
possible value for that fixed point type.

- Fixed point functions (to be defined under <stdfix.h>) (clause 4.1.7,
4.1.8)
   - mulifx, divifx, fxdivi and idivfx (where fx stands for one of the fixed
point suffixes)
   - absfx
   - roundfx
   - countlsfx
   - bitsfx (and the respective integer types int_fx_t/uint_fx_t)
   - fxbits
   - strtofxfx

- Format specifiers for fixed-point arguments (clause 4.1.9):
```
r: signed fract types
R: unsigned fract types
k: signed accum types
K: unsigned accum types
```
   - Formatting to and from the appropriate decimal notation ([-]ddd.ddd)
will be similar to that of formatting a floating point number.

# Implementation Details

Expected changes include:
- _Fract, _Accum, and _Sat will need to be added as tokens.
- The lexer and parser will need to accept these tokens.
- Type nodes will need to be created to represent _Fract, _Accum, and _Sat.
- Underlying logic for builtin operations between fixed-point types and
other types (addition, multiplication, etc.).
- The <stdfix.h> header which will include helper functions and natural
spelling for fixed-point types.
- Formatted IO functions in libc to support the new format specifies for
fixed point arguments.

All changes will also be made to Clang only. Expanding this into LLVM will
be considered down the road.


[1] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1169.pdf
[2] https://gcc.gnu.org/wiki/FixedPointArithmetic
[3] https://fuchsia.googlesource.com
[4] https://en.wikipedia.org/wiki/Q_(number_format)