Fixed-point number

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

Principe

To understand the principle, just imagine a program that needs the meter as its final unit, but at some point needs to be able to move an object of less than one unit, say 0.2 m (20 cm). Since it would be far too heavy for our venerable MSX to work with real floating-point numbers (like C's float), the trick might simply be to store the numbers and do the calculations in centimeter (cm = meters * 100), then convert to meters when necessary (meters = cm / 100).

So, to add 0.2 m, we'd add the integer value 0.2 * 100 (= 20). Conversely, the integer 4213 would actually represent 42.13 m.

Such a format would be a fixed-point number with 2 decimal places (100).

Format Qm.n

Comme les divisions/multiplications par 100 sont coûteuses, on va plutôt utiliser des facteurs puissance de 2 (1, 2, 4, 8, 16, etc.) comme base pour la partie fractionnelle. Du coup, les divisions/multiplications peuvent être remplacés par des décalages de bits qui sont énormément moins coûteux. Sur un entier 8 ou 16-bits (les 32-bits sont souvent trop coûteux pour nos Z80), on va donc décider du nombre de bits qui serviront à coder la partie entière et de ceux (le reste) qui serviront à coder la partie fractionnelle. C’est le format Q ! Ou plutôt « Qm.n ». (cf. Article "Q" sur Wikipédia)

Par ex., un nombre 8-bits codé au format Q4.4, utilise 4-bits pour l’entier et 4-bits pour la fraction. Pour convertir une valeur en Q4.4, il suffit de décaler le nombre 4 fois vers la gauche (x << 4), Pour convertir un Q4.4 en valeur, il suffit de décaler le nombre 4 fois vers la droite (x >> 4). Si on l’utilise pour stocker un nombre non signé, on pourra coder dans un Q4.4 des nombres allant de 0 à 15,9375 (255/16) avec une précision de 0,0625 (1/16). On peut utiliser avec le Q4.4 n’importe quelles opérations mathématiques de base tant que tous les termes sont au même format.

A noter que pour les entiers signés, certains excluent le bit de signe dans la notation. Du coup, Q7.8 ⇒ 1-bit de signe, 7-bits entier, 8-bits fractionnel.

Examples

There are as many Qs as there are bit combinations.

Here are a few examples I use:

• Q2.6 : 8-bit integer for encoding digits 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-bit integer and fractional parts. Very efficient when used with an unsigned number. Otherwise, a few precautions should be taken.
• Q6.10 : 16-bit integer with 6-bit integer part and 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

Of course, you can switch from one Q format to another by simply shifting bits.

For example:

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

Note: In the case of a negative signed value, it's a little more complicated as the sign must be preserved.

Full list

Here is the 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

Langage C

Et pour les utilisateurs de C, il est conseillé de passer par des macros de conversion.

Par ex. : Code C :

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

On laisse les multiplications/divisions par 64 pour permettre au compilateur de pouvoir adapter ses opérations en fonction du type de data qu'on lui donne. Si on prend une variable int16 x qui contient un nombre au format Q10.6, on peux faire ce genre d'opérations : Code C :

#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;

L'autre gros avantage, c'est qu'on peux ainsi changer la précision de son unité sans devoir retoucher tout son code.