Calculs d'intervalles d'entiers, opérations logiques (projet no. 2)

C possède 8 types entiers: int, char, short, long qui sont des types signés, et leurs équivalents non signés, précédés du mot-clé unsigned. (Bon, en réalité char n'est pas spécifié en ANSI C comme étant signé ou non; on suppose ici qu'il est signé. On a fait d'autres hypothèses ici, comme le fait que les entiers étaient représentés en complément à deux.)

Les entiers d'un type entier T signé sont des entiers dans l'intervalle [-2^N-1, 2^N-1-1], où N est le nombre de bits du type T. Par exemple, int est typiquement 32 bits sur les ordinateurs actuels. Les entiers d'un type entier T non signé sont eux dans l'intervalle [0, 2^N-1], où N est encore le nombre de bits de T.

Les types C T sont définis sous forme du type Caml q_ctype dans le module cparse.ml. Les types entier sont TINT, ..., TUNSIGNED_LONG. Un autre module fournissant des fonctions utiles à ce projet est arith.ml. Notamment, Arith.int_type_info T retourne un record, de type int_type, dont les champs sont:

it_signed: true si type signé, false sinon;
it_nbits: le nombre de bits du type;
it_max: le plus grand entier représentable, soit 2^N-1-1 en signé, 2^N-1 en non signé;
it_min: le plus petit entier représentable, soit -2^N-1 en non signé, 0 en non signé;
it_range: le nombre d'entiers représentables, soit 2^N.

Ces constantes sont de type float en OCaml, et non int comme on aurait pu s'y attendre. La raison principale est que le type int de OCaml ne permet pas de représenter tous les entiers machines: ils ne vont que de -2³⁰ à 2³⁰-1 sur une architecture 32 bits.

Remarque Il faut faire attention à certains aspects du calcul en flottant en OCaml (en fait, en général). En premier, il y a deux nombres flottants nuls, 0.0 et -0.0; si vous voulez tester qu'un nombre flottant x est nul, utilisez la fonction float_is_zero du module Arith, n'écrivez pas ``x=0.0''. Ensuite, quand vous effectuez des calculs en flottants pour représenter des calculs d'entiers, n'oubliez pas que la division entière calcule le quotient de la division réelle, c'est-à-dire la partie entière de la division réelle.

La fonction round_to_int arrondit un flottant en entier, et effectue le cast y = (int)x où x est un flottant (de type C float ou double). Les débordements ne sont pas vérifiés; pour vérifier les débordements, utiliser round_to_int_range, qui calcule modulo la largeur du type entier considéré: round_to_int_range it x, où it est un int_type et x un float, retourne le résultat du cast de x à un entier décrit par it.

Remarque L'intervalle [a,b] est représenté par la valeur Caml ITV (a,b), si a£ b; sinon, par ITV_EMPTY. La fonction itv, du module Intervalle, prend a et b en argument et retourne la bonne représentation de l'intervalle [a,b]: utilisez-la donc, de préférence au constructeur ITV, pour construire des intervalles.

Votre but est de réaliser les fonctions décrites dans itv_int_log.mli. La sémantique des opérations logiques de C est la suivante. Tout entier est vu comme un tableau de bits (0 ou 1).

La négation ~x change les bits 0 en 1 et réciproquement. Une astuce, valable uniquement dans les représentations en complément à deux, est que, au moins quand le type est signé, ~x = -x-1. Quand le type est non signé, on pourra par exemple passer par un type signé en étape intermédiaire.

Les opérations x << n et x >> n calculent respectivement x.2ⁿ^mod^N et la partie entière de x/2ⁿ^mod^N respectivement, où N est le nombre de bits dans le type de x. Noter que même si n est d'un type signé, le modulo N ci-dessus est compris comme si n était non signé (donc 0£ n mod N < N). Dans le cas de x >> n, la partie entière n'est pas la même en général que celle utilisée dans le calcul de la division entière, on ne peut donc pas utiliser itv_int_div, du projet 1. Formellement, l'arrondi est ici fait vers le bas quel que soit le signe de x: c'est la partie entière au sens mathématique, contrairement a itv_int_div. Par exemple, 31 / 4 = 7 et 31 >> 2 = 7 (pareil, car 31 est positif); -31 / 4 = -7 et -31 >> 2 = -8 (arrondi différent).

Les opérations et, ou exclusif et ou sont effectuées bit à bit, comme la négation. Il ne semble par contre pas y avoir d'astuce similaire à celle de la négation pour les calculer. Vous devrez donc cogiter suffisamment pour construire des approximations correctes et suffisamment précises de ces opérations sur les intervalles d'entiers.

This document was translated from L^AT_EX by H^EV^EA.