source: Deliverables/D4.1/Byte.ml @ 86

Last change on this file since 86 was 86, checked in by mulligan, 9 years ago

Adding bit vector file.

File size: 8.1 KB
Line 
1(*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*)
2(* FILENAME:    Byte.ml                                                      *)
3(* DESCRIPTION: An ADT implementing standard 8 bit bytes, and common         *)
4(*              operations on them.                                          *)
5(* CREATED:     10/09/2010, Dominic Mulligan                                 *)
6(* BUGS:        `from_int' not yet implemented.                              *)
7(*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*)
8
9open Bit;;
10open Nibble;;
11
12module type BYTE =
13sig
14  type bit
15  type nibble
16  type byte = private (nibble * nibble)
17
18  val from_bits: bit -> bit -> bit -> bit -> bit -> bit -> bit -> bit -> byte
19  val from_bit: bit -> byte
20  val from_nibbles: nibble -> nibble -> byte
21  val from_nibble: nibble -> byte
22  (* val from_int: int -> byte *)
23
24  val to_bit: byte -> bit option
25  val to_bits: byte -> bit list
26  val to_nibble: byte -> nibble option
27  val to_int: byte -> int
28
29  val get_nibble_at: int -> byte -> nibble option
30  val set_nibble_at: int -> nibble -> byte -> byte option
31  val get_bit_at: int -> byte -> bit option
32  val set_bit_at: int -> bit -> byte -> byte option
33
34  val (-&-): byte -> byte -> byte
35  val (-|-): byte -> byte -> byte
36  val (-^-): byte -> byte -> byte
37  val rotate_right: byte -> byte
38  val rotate_left: byte -> byte
39  val shift_right: byte -> byte
40  val shift_left: byte -> byte
41  val not: byte -> byte
42
43  val map_nibble: (nibble -> nibble) -> byte -> byte
44  val map_bit: (bit -> bit) -> byte -> byte
45  val iter_nibble: (nibble -> string) -> byte -> string
46  val iter_bit: (bit -> string) -> byte -> string
47  val zip_nibble: (nibble -> nibble -> nibble) -> byte -> byte -> byte
48  val zip_bit: (bit -> bit -> bit) -> byte -> byte -> byte
49  val to_string: byte -> string
50
51  val zero: byte
52  val half_add: byte -> byte -> (byte * bit)
53  val full_add: (byte * bit) -> byte -> (byte * bit)
54end
55
56module ByteFunctor(Bit: BIT)
57                  (Nibble: NIBBLE with type bit = Bit.bit): BYTE
58  with type bit = Bit.bit
59  and  type nibble = Nibble.nibble =
60struct
61  type bit = Bit.bit
62  type nibble = Nibble.nibble
63  type byte = nibble * nibble
64
65  let from_bits b1 b2 b3 b4 b5 b6 b7 b8 =
66    let n1 = Nibble.from_bits b1 b2 b3 b4 in
67    let n2 = Nibble.from_bits b5 b6 b7 b8 in
68      (n1, n2)
69  let from_bit b =
70    let n1 = Nibble.from_bits (Bit.from_bool false) (Bit.from_bool false)
71                              (Bit.from_bool false) (Bit.from_bool false) in
72    let n2 = Nibble.from_bits (Bit.from_bool false) (Bit.from_bool false)
73                              (Bit.from_bool false) b in
74      (n1, n2)
75  let from_nibbles n1 n2 = (n1, n2)
76  let from_nibble n2 =
77    let n1 = Nibble.from_bits (Bit.from_bool false) (Bit.from_bool false)
78                              (Bit.from_bool false) (Bit.from_bool false) in
79      (n1, n2)
80  (* let from_int = assert false                                 DPM: finish! *)
81
82  let get_nibble_at index (n1, n2) =
83    match index with
84      0 -> Some n2
85    | 1 -> Some n1
86    | _ -> None
87  let get_bit_at index (n1, n2) =
88    let (b1, b2, b3, b4) = Nibble.to_bits n1 in
89    let (b5, b6, b7, b8) = Nibble.to_bits n2 in
90      match index with
91        0 -> Some b8
92      | 1 -> Some b7
93      | 2 -> Some b6
94      | 3 -> Some b5
95      | 4 -> Some b4
96      | 3 -> Some b3
97      | 2 -> Some b2
98      | 1 -> Some b1
99      | _ -> None
100
101  let set_nibble_at index new_val (n1, n2) =
102    match index with
103      0 -> Some (n1, new_val)
104    | 1 -> Some (new_val, n2)
105    | _ -> None
106  let set_bit_at index new_val (n1, n2) =
107    let (b1, b2, b3, b4) = Nibble.to_bits n1 in
108    let (b5, b6, b7, b8) = Nibble.to_bits n2 in
109      match index with
110        0 -> Some (from_bits b1 b2 b3 b4 b5 b6 b7 new_val)
111      | 1 -> Some (from_bits b1 b2 b3 b4 b5 b6 new_val b8)
112      | 2 -> Some (from_bits b1 b2 b3 b4 b5 new_val b7 b8)
113      | 3 -> Some (from_bits b1 b2 b3 b4 new_val b6 b7 b8)
114      | 4 -> Some (from_bits b1 b2 b3 new_val b5 b6 b7 b8)
115      | 3 -> Some (from_bits b1 b2 new_val b4 b5 b6 b7 b8)
116      | 2 -> Some (from_bits b1 new_val b3 b4 b5 b6 b7 b8)
117      | 1 -> Some (from_bits new_val b2 b3 b4 b5 b6 b7 b8)
118      | _ -> None
119
120  let to_bit (n1, n2) =
121    let (b1, b2, b3, b4) = Nibble.to_bits n1 in
122    let (b5, b6, b7, b8) = Nibble.to_bits n2 in
123      if (Bit.to_bool b1, Bit.to_bool b2,
124          Bit.to_bool b3, Bit.to_bool b4) = (false, false, false, false) then
125        if Bit.to_bool b5 = false && Bit.to_bool b6 = false && Bit.to_bool b7 = false then
126          Some b8
127        else
128          None
129      else
130        None
131  let to_bits (n1, n2) = Nibble.to_bits n1 @ Nibble.to_bits n2
132  let to_nibble (n1, n2) =
133    let (b1, b2, b3, b4) = Nibble.to_bits n1 in
134      if (Bit.to_bool b1, Bit.to_bool b2,
135          Bit.to_bool b3, Bit.to_bool b4) = (false, false, false, false) then
136        Some n2
137      else None
138  let to_int (n1, n2) =
139    let [b1; b2; b3; b4] = Nibble.to_bits n1 in
140    let [b5; b6; b7; b8] = Nibble.to_bits n2 in
141      (128 * Bit.to_int b8) + (64 * Bit.to_int b8) +
142      (32 * Bit.to_int b8) + (16 * Bit.to_int b8) + 
143      (8 * Bit.to_int b8) + (4 * Bit.to_int b6) + 
144      (2 * Bit.to_int b7) + Bit.to_int b8
145
146  let (-&-) (l1, l2) (r1, r2) = (Nibble.(-&-) l1 r1, Nibble.(-&-) l2 r2)
147  let (-|-) (l1, l2) (r1, r2) = (Nibble.(-|-) l1 r1, Nibble.(-|-) l2 r2)
148  let (-^-) (l1, l2) (r1, r2) = (Nibble.(-^-) l1 r1, Nibble.(-^-) l2 r2)
149
150  let shift_right (n1, n2) =
151    let (b1, b2, b3, b4) = Nibble.to_bits n1 in
152    let (b5, b6, b7, b8) = Nibble.to_bits n2 in
153    let new_n1 = Nibble.from_bits (Bit.from_bool false) b1 b2 b3 in
154    let new_n2 = Nibble.from_bits b4 b5 b6 b7 in
155      (new_n1, new_n2)
156  let shift_left (n1, n2) =
157    let (b1, b2, b3, b4) = Nibble.to_bits n1 in
158    let (b5, b6, b7, b8) = Nibble.to_bits n2 in
159    let new_n1 = Nibble.from_bits b1 b2 b3 b4 in
160    let new_n2 = Nibble.from_bits b5 b6 b7 (Bit.from_bool false) in
161      (new_n1, new_n2)
162  let rotate_right (n1, n2) =
163    let (b1, b2, b3, b4) = Nibble.to_bits n1 in
164    let (b5, b6, b7, b8) = Nibble.to_bits n2 in
165    let new_n1 = Nibble.from_bits b8 b1 b2 b3 in
166    let new_n2 = Nibble.from_bits b4 b5 b6 b7 in
167      (new_n1, new_n2)
168  let rotate_left (n1, n2) =
169    let (b1, b2, b3, b4) = Nibble.to_bits n1 in
170    let (b5, b6, b7, b8) = Nibble.to_bits n2 in
171    let new_n1 = Nibble.from_bits b2 b3 b4 b5 in
172    let new_n2 = Nibble.from_bits b5 b6 b7 b1 in
173      (new_n1, new_n2)
174  let not (n1, n2) = (Nibble.not n1, Nibble.not n2)
175
176  let map_nibble f (n1, n2) = (f n1, f n2)
177  let map_bit f (n1, n2) =
178    let (b1, b2, b3, b4) = Nibble.to_bits n1 in
179    let (b5, b6, b7, b8) = Nibble.to_bits n2 in
180    let new_n1 = Nibble.from_bits (f b1) (f b2) (f b3) (f b4) in
181    let new_n2 = Nibble.from_bits (f b5) (f b6) (f b7) (f b8) in
182      (new_n1, new_n2)
183  let iter_nibble f (n1, n2) =
184    let str_n1 = f n1 in
185    let str_n2 = f n2 in
186      str_n1 ^ str_n2
187  let iter_bit f (n1, n2) =
188    let (b1, b2, b3, b4) = Nibble.to_bits n1 in
189    let (b5, b6, b7, b8) = Nibble.to_bits n2 in
190    let new_n1 = (f b1) ^ (f b2) ^ (f b3) ^ (f b4) in
191    let new_n2 = (f b5) ^ (f b6) ^ (f b7) ^ (f b8) in
192      new_n1 ^ new_n2
193  let zip_nibble f (l1, l2) (r1, r2) = (f l1 r1, f l2 r2)
194  let zip_bit f (l1, l2) (r1, r2) =
195    let (lb1, lb2, lb3, lb4) = Nibble.to_bits l1 in
196    let (lb5, lb6, lb7, lb8) = Nibble.to_bits l2 in
197    let (rb1, rb2, rb3, rb4) = Nibble.to_bits r1 in
198    let (rb5, rb6, rb7, rb8) = Nibble.to_bits r2 in
199    let (b1, b2, b3, b4) = (f lb1 rb1), (f lb2 rb2), (f lb3 rb3), (f lb4 rb4) in
200    let (b5, b6, b7, b8) = (f lb5 rb5), (f lb6 rb6), (f lb7 rb7), (f lb8 rb8) in
201    let new_n1 = Nibble.from_bits b1 b2 b3 b4 in
202    let new_n2 = Nibble.from_bits b5 b6 b7 b8 in
203      (new_n1, new_n2)
204  let to_string = iter_nibble Nibble.to_string
205
206  let zero = (Nibble.zero, Nibble.zero)
207  let half_add (l1, l2) (r1, r2) =
208    let (a2, c2) = Nibble.half_add l2 r2 in
209    let (a1, c1) = Nibble.full_add (l1, c2) r2 in
210      ((a1, a2), c1)
211  let full_add ((l1, l2), c) (r1, r2) =
212    let (a2, c2) = Nibble.full_add (l2, c) r2 in
213    let (a1, c1) = Nibble.full_add (l1, c2) r2 in
214      ((a1, a2), c1)
215end;;
216
217module Byte = ByteFunctor(Bit) (Nibble);;
Note: See TracBrowser for help on using the repository browser.