Fixed-point number

A fixed-point number is simply a real number (e.g., 3.14) that is encoded as an integer by applying a factor (a multiplier). The aim is to manipulate numbers with a precision of less than 1, while maintaining the performance benefits of integer processing.

Principe

To understand the principle, imagine a program that uses meters as its final unit but needs to move an object by less than one unit, say 0.2 m (20 cm). Since working with real floating-point numbers (like C's float) would be too resource-intensive for our venerable MSX, the trick is to store numbers and perform calculations in centimeters (cm = meters × 100), then convert back to meters when necessary (meters = cm / 100).

So, to add 0.2 m, you would add the integer value 0.2 × 100 (= 20).

Conversely, the integer 4213 would represent 42.13 m.

This format is a fixed-point number with 2 decimal places (100).

Qm.n format

Since division/multiplication by 100 is computationally expensive, we instead use powers of 2 (1, 2, 4, 8, 16, etc.) as the basis for the fractional part. As a result, divisions/multiplications can be replaced with bit shifts, which are far less costly. For an 8- or 16-bit integer (32-bit is often too expensive for our Z80s), we decide how many bits will encode the integer part and how many bits (the remainder) will encode the fractional part. This is the Q format! Or more precisely, the "Qm.n" format: "m" is the number of bits for the integer part, and "n" is the number of bits for the fractional part (see the "Q" article on Wikipedia).

For example, an 8-bit number in Q4.4 format uses 4 bits for the integer part and 4 bits for the fractional part. To convert a final unit value to Q4.4, simply shift the number 4 places to the left (x << 4). To convert a Q4.4 value back to the final unit, shift the number 4 places to the right (x >> 4). If used to store an unsigned number, Q4.4 can encode values from 0 to 15.9375 (255/16) with a precision of 0.0625 (1/16). Q4.4 can be used for any basic mathematical operation, as long as all terms are in the same format.

Note that for signed integers, some notations exclude the sign bit. Thus, Q7.8 ⇒ 1-bit sign, 7-bit integer, 8-bit fractional.

Examples

There are as many Q formats as there are bit combinations.

Here are a few examples I use:

• Q2.6: 8-bit integer for encoding values between -1.0 and 1.0 with a precision of 0.015625. Very useful for storing direction vectors, for example.
• Q8.8: 16-bit integer with 8 bits each for the integer and fractional parts. Very efficient when used with unsigned numbers. Otherwise, some precautions are needed.
• Q6.10: 16-bit integer with a 6-bit integer part and a 10-bit fractional part. Allows data to be manipulated in KB (with a factor of 1024). Useful for small numbers requiring very high precision (~0.001).

Conversion

You can switch between Q formats by simply shifting bits.

For example:

• Q4.4 << 2 ⇒ Q2.6
• Q8.8 >> 4 ⇒ Q12.4

Note: For negative signed values, it’s a bit more complicated because the sign must be preserved.

Full list

Here is the complete set of possible Qm.n formats for 8- and 16-bit integers, with their precision values and bounds:

Also available in PDF format: Qm.n.pdf.

Exemple d'utilisation

Imaginons qu'on doive calculer l'expression 'a x cos(b)', avec 'a' un entier 8 bits.

On sait que cos(b) est un nombre réel compris entre -1 et 1. On va utiliser une simple table qui va nous donner la valeur de cos(b) pour b. Partons du principe que les valeurs exactes -1 et 1 seront gérées séparément (par exemple à l'aide d'un test avant le calcul), et que l'on ne gère que les angles de 0° à 90°. Donc, on doit stocker des valeurs comprises entre 0 et 0,999999. Pour stocker ce genre de valeurs, le format Q0.8 non signé est parfait.

Prenons par exemple cos(45°) = racine carrée (2)/2 = 0.70710678118 Pour coder ce nombre en Q0.8 non signé, il suffit de le multiplier par 256 : 0.70710678118 x 256 = 181.019335984 On ne peut évidemment pas prendre les décimales, donc on ne stocke que la valeur entière : 181 (entier 8 bit).

Plaçons nous au moment du calcul, lorsqu'on veux faire, par exemple, 33 x cos(45°) = 23.3345237792 :

• on prend la valeur de la table pour 45° (181)
• on la multiplies par 33
• on obtient donc un entier 16 bits dont la valeur est 5973

Cet entier 16 bits est le résultat, codé en Q8.8. Normal, puisqu'en fait, on a multiplié les 2 membres de lexpression par 256 : a x (256 x cos(b)) = 256 x résultat 5973 / 256 = 23.33203125, on a donc une erreur de 0,002, ce qui est acceptable.

Et pour obtenir la valeur entière, il suffit de garder l'octet haut du résultat. 5973d = 1723h, la valeur entière est donc : 17h = 23d.

Assembleur

Exemple

Par ex., lorsqu'un programmeur voudra récupérer la valeur d'un entier 8-bits au format Q4.4, il lui suffit de faire >>4 sur la valeur. Avec en bonus, la possibilité d'utiliser le dernier bit sorti vers la droite pour faire l'arrondi.

Imaginons que le résultat d'une série d'opérations donne le nombre 58, soit en format binaire 00111010b. Ce nombre est en fait la représentation de 3,625 en Q4.4 (puisque 58/16=3,625). Lorsque l'on va faire >>4 sur cette valeur pour récupérer la valeur entière, il restera bien 3 dans le nombre (0011b), et le dernier bit sorti à droite sera 1. Ce qui peut être alors utilisé pour décider de faire l'arrondi vers l'entier supérieur (ou pas).

Exemple de l'arrondi vers l'entier supérieur en Q4.4 d'une valeur contenue dans 'a' :

Code:

; valeur de a >> 4
srl     a
srl     a
srl     a
srl     a
; ajout du carry (qui contient le dernier bit sorti à droite)
adc     0

Optimal code

Here are the optimal ways (in number of t-states) to do bit shifts in Z80 for 8-bit fixed-point number.

Right-shift:

; a >> 1 (10 ts)
srl    a
; a >> 2 (18 ts)
rrca
rrca
and a, #0x3F
; a >> 3 (23 ts)
rrca
rrca
rrca
and a, #0x1F
; a >> 4 (28 ts)
rlca
rlca
rlca
rlca
and a, #0x0F
; a >> 5 (23 ts)
rlca
rlca
rlca
and a, #0x07
; a >> 6 (18 ts)
rlca
rlca
and a, #0x03
; a >> 7 (13 ts)
rlca
and a, #0x01

Left-shift:

; a << 1 (5 ts)
add a, a
; a << 2 (10 ts)
add a, a
add a, a
; a << 3 (15 ts)
add a, a
add a, a
add a, a
; a << 4 (20 ts)
add a, a
add a, a
add a, a
add a, a
; a << 5 (23 ts)
rrca
rrca
rrca
and a, #0xE0
; a << 6 (18 ts)
rrca
rrca
and a, #0xC0
; a << 7 (13 ts)
rrca
and a, #0x80

Each Qm.n format therefore has a different conversion time.

In/out conversion time:

• Q7.1 : 15 ts
• Q6.2 : 28 ts
• Q5.3 : 38 ts
• Q4.4 : 48 ts
• Q3.5 : 46 ts
• Q2:6 : 36 ts
• Q1:7 : 26 ts

C Language

For C users, it is recommended to use conversion macros.

For example:

// Unit conversion (Pixel <> Q10.6)
#define UNIT_TO_PX(a)                (u8)((a) / 64)
#define PX_TO_UNIT(a)                (i16)((a) * 64)

We leave the multiplications/divisions by 64 to allow the compiler to optimize operations based on the data type provided. If we have an int16 x variable containing a number in Q10.6 format, we can perform operations like this:

#define PI PX_TO_UNIT(3.14159265f) // Le compilateur va faire la conversion en float, puis convertir en int (précision optimale)
uint8 nbPixel = 10;
x += PX_TO_UNIT(nbPixel); // Le compilateur va faire la conversion via des décalages de bits (vitesse optimale)
if(x > 2*PI) // A noter une petite perte de précision car le x2 va être fait après la conversion en int
    x = PI;

The other major advantage is that you can change the precision of your unit without having to rewrite all your code.