source: Deliverables/D2.2/8051/src/common/intValue.ml @ 630

Last change on this file since 630 was 630, checked in by ayache, 9 years ago

Paris update in D2.2.

File size: 7.9 KB
Line 
1
2(** This module defines functions to manipulate bounded integers. They can be
3    used to represent sequences of bits. *)
4
5open Big_int
6
7
8(* Integers, whatever their size, will be represented using the Big_int
9   module. This allows immediate conversion, and allows the representation of
10   any integer (that fits into memory). *)
11
12type int_repr = Big_int.big_int
13
14(* The parameter module. Bounded integers are characterized by the number of
15   bits used to represent them. *)
16   
17module type INTTYPE = 
18sig
19  val size : int (* in bytes *)
20end
21
22(* The signature provided to manipulate bounded integers. *)
23
24module type S = sig
25
26  type t = Big_int.big_int
27
28  val compare   : t -> t -> int
29  val to_string : t -> string
30  val zero      : t
31  val one       : t
32
33  val succ    : t -> t
34  val pred    : t -> t
35  val add     : t -> t -> t
36  (** [add_of i1 i2] returns [true] iff adding [i1] and [i2] overflows. *)
37  val add_of  : t -> t -> bool
38  val sub     : t -> t -> t
39  (** [sub_uf i1 i2] returns [true] iff substracting [i1] and [i2]
40      underflows. *)
41  val sub_uf  : t -> t -> bool
42  val mul     : t -> t -> t
43  val div     : t -> t -> t
44  val divu    : t -> t -> t
45  val modulo  : t -> t -> t
46  val modulou : t -> t -> t
47  val eq      : t -> t -> bool
48  val neq     : t -> t -> bool
49  val lt      : t -> t -> bool
50  val ltu     : t -> t -> bool
51  val le      : t -> t -> bool
52  val leu     : t -> t -> bool
53  val gt      : t -> t -> bool
54  val gtu     : t -> t -> bool
55  val ge      : t -> t -> bool
56  val geu     : t -> t -> bool
57  val neg     : t -> t
58  val lognot  : t -> t
59  val logand  : t -> t -> t
60  val logor   : t -> t -> t
61  val logxor  : t -> t -> t
62  val shl     : t -> t -> t
63  val shr     : t -> t -> t
64  val shrl    : t -> t -> t
65  val max     : t -> t -> t
66  val maxu    : t -> t -> t
67  val min     : t -> t -> t
68  val minu    : t -> t -> t
69  val cast    : int_repr -> t
70  val of_int  : int -> t
71  val to_int  : t -> int
72
73  (** [zero_ext n a] performs zero extension on [a] where [n] bits are
74      significant. *)
75  val zero_ext : int -> t -> t
76  (** [sign_ext n a] performs sign extension on [a] where [n] bits are
77      significant. *)
78  val sign_ext : int -> t -> t
79
80  (** [break i n] cuts [i] in [n] parts. In the resulting list, the first
81      element is the high bits, and the last is the low bits. *)
82  val break : t -> int -> t list
83  (** [merge l] creates the integer where the first element of [l] is its
84      high bits, etc, and the last element of [l] is its low bits. *)
85  val merge : t list -> t
86
87end
88
89
90module Make (IntType: INTTYPE) : S = 
91struct
92
93  type t = Big_int.big_int
94
95  let size = IntType.size * 8 (* real size, i.e. in bits *)
96
97  let compare = compare_big_int
98  let to_string = string_of_big_int
99  let zero = zero_big_int
100  let one = unit_big_int
101  let two = succ_big_int unit_big_int
102
103  (* Integers will all be taken modulo the following value. *)
104  let _mod = power_int_positive_int 2 size
105
106  (* The lower bound (inclusive). *)
107  let lower_bound = zero
108  (* The upper bound (inclusive). *)
109  let upper_bound = pred_big_int _mod
110
111  (* [cast a] returns a modulo of [a] such that the result fits in the interval
112     of representation. *)
113  let cast a = mod_big_int a _mod
114
115  (* Half bound (exclusive), i.e. upper bound of signed integers. *)
116  let half_bound = power_int_positive_int 2 (size-1)
117
118  (* Signed value of [a]. *)
119  let signed a =
120    let a = cast a in
121    if lt_big_int a half_bound then a
122    else sub_big_int a _mod
123
124  let signed_op op a b = op (signed a) (signed b)
125
126  let succ a = cast (succ_big_int a)
127  let pred a = cast (pred_big_int a)
128  let add a b = cast (add_big_int a b)
129
130  (* [add_of i1 i2] returns [true] iff adding [i1] and [i2] overflows. *)
131  let add_of a b = gt_big_int (add_big_int a b) upper_bound
132
133  let sub a b = cast (sub_big_int a b)
134
135  let cast_op op a b = op (cast a) (cast b)
136
137  let mul a b = cast (mult_big_int a b)
138  let div a b = cast (signed_op div_big_int a b)
139  let divu a b = cast_op div_big_int a b
140  let modulo a b = cast (signed_op mod_big_int a b)
141  let modulou a b = cast_op mod_big_int a b
142
143  let eq = eq_big_int
144  let neq a b = not (eq a b)
145  let lt a b = signed_op lt_big_int a b
146  let le a b = signed_op le_big_int a b
147  let gt a b = signed_op gt_big_int a b
148  let ge a b = signed_op ge_big_int a b
149  let ltu a b = cast_op lt_big_int a b
150  let leu a b = cast_op le_big_int a b
151  let gtu a b = cast_op gt_big_int a b
152  let geu a b = cast_op ge_big_int a b
153
154  (* [sub_uf i1 i2] returns [true] iff substracting [i1] and [i2] underflows. *)
155  let sub_uf a b = lt_big_int (sub_big_int a b) zero
156
157  let of_int i = cast (big_int_of_int i)
158  let to_int i = int_of_big_int (cast i)
159
160  let neg a = cast (minus_big_int a)
161
162  let lognot = sub upper_bound
163
164  let shl a b =
165    let pow = power_int_positive_big_int 2 (cast b) in
166    cast (mult_big_int a pow)
167
168  let shr a b =
169    let a = cast a in
170    let b = cast b in
171    let added =
172      if lt_big_int a half_bound then zero
173      else half_bound in
174    let rec aux acc b =
175      if eq b zero then acc
176      else
177        let cont_acc = add added (divu acc two) in
178        let cont_b = pred b in
179        aux cont_acc cont_b
180    in
181    cast (aux a b)
182
183  let shrl a b =
184    let pow = power_int_positive_big_int 2 (cast b) in
185    cast (div_big_int (cast a) pow)
186
187  let max a b = if lt a b then b else a
188  let min a b = if gt a b then b else a
189  let maxu a b = if ltu a b then b else a
190  let minu a b = if gtu a b then b else a
191
192  let is_odd a = eq (modulou a two) one
193  (* [to_bits a] returns the list of bits (0 or 1) that [a] represents. *)
194  let to_bits a =
195    let rec aux acc a i =
196      if i >= size then acc
197      else aux ((is_odd a) :: acc) (divu a two) (i+1)
198    in
199    aux [] (cast a) 0
200
201  (* [from_bits bits] returns the integer that the list of bits [bits]
202     represents. *)
203  let from_bits bits =
204    let rec aux acc = function
205      | [] -> acc
206      | b :: bits ->
207        let next_acc = mul acc two in
208        let next_acc = if b then succ next_acc else next_acc in
209        aux next_acc bits
210    in
211    aux zero bits
212
213  (* [binary_log_op f a b] applies the binary boolean operation [f]
214     pointwisely to the bits that [a] and [b] represent. *)
215  let binary_log_op f a b =
216    from_bits (List.map2 f (to_bits a) (to_bits b))
217
218  let xor a b = (a || b) && (not (a && b))
219
220  let logand = binary_log_op (&&)
221  let logor = binary_log_op (||)
222  let logxor = binary_log_op xor
223
224
225  (* [zero_ext n a] performs zero extension on [a] where [n] bits are
226     significant. *)
227  let zero_ext n a =
228    let pow2 = power_int_positive_int 2 n in
229    cast (mod_big_int a pow2)
230
231  (* [sign_ext n a] performs sign extension on [a] where [n] bits are
232     significant. *)
233  let sign_ext n a =
234    let a' = zero_ext n a in
235    let pow2 = power_int_positive_int 2 (n-1) in
236    let sign = divu a pow2 in
237    if is_odd sign then
238      let added = shr half_bound (of_int (n-1)) in
239      add a' added
240    else a'
241
242
243  (* [break i n] cuts [i] in [n] parts. In the resulting list, the first element
244     is the high bits, and the last is the low bits. *)
245  let break a n =
246    let chunk_size = size / n in
247    let pow2_chunk_size = power_int_positive_int 2 chunk_size in
248    let rec aux acc a i =
249      if i = 0 then acc
250      else
251        let (next, chunk) = quomod_big_int a pow2_chunk_size in
252        aux ((cast chunk) :: acc) next (i-1)
253    in
254    aux [] (cast a) n
255
256  (* [merge l] creates the integer where the first element of [l] is its high
257     bits, etc, and the last element of [l] is its low bits. *)
258  let merge = function
259    | [] -> zero
260    | al ->
261      let al = List.rev al in
262      let nb_chunks = List.length al in
263      let chunk_size = size / nb_chunks in
264      let pow2_chunk_size = power_int_positive_int 2 chunk_size in
265      let rec aux pow2 = function
266        | [] -> zero
267        | a :: al -> add (mul a pow2) (aux (mul pow2 pow2_chunk_size) al)
268      in
269      aux one al
270
271end
272
273
274module Int8  : S = Make (struct let size = 1 end)
275module Int16 : S = Make (struct let size = 2 end)
276module Int32 : S = Make (struct let size = 4 end)
277
278type int8  = Int8.t
279type int16 = Int16.t
280type int32 = Int32.t
Note: See TracBrowser for help on using the repository browser.