1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 (* ********************************************************************** *)
18 (* Cosimo Oliboni, oliboni@cs.unibo.it *)
20 (* ********************************************************************** *)
22 include "freescale/word16.ma".
28 nrecord word32 : Type ≝
34 ndefinition word32_ind : ΠP:word32 → Prop.(Πw:word16.Πw1:word16.P (mk_word32 w w1)) → Πdw:word32.P dw ≝
35 λP:word32 → Prop.λf:Πw:word16.Πw1:word16.P (mk_word32 w w1).λdw:word32.
36 match dw with [ mk_word32 (w:word16) (w1:word16) ⇒ f w w1 ].
38 ndefinition word32_rec : ΠP:word32 → Set.(Πw:word16.Πw1:word16.P (mk_word32 w w1)) → Πdw:word32.P dw ≝
39 λP:word32 → Set.λf:Πw:word16.Πw1:word16.P (mk_word32 w w1).λdw:word32.
40 match dw with [ mk_word32 (w:word16) (w1:word16) ⇒ f w w1 ].
42 ndefinition word32_rect : ΠP:word32 → Type.(Πw:word16.Πw1:word16.P (mk_word32 w w1)) → Πdw:word32.P dw ≝
43 λP:word32 → Type.λf:Πw:word16.Πw1:word16.P (mk_word32 w w1).λdw:word32.
44 match dw with [ mk_word32 (w:word16) (w1:word16) ⇒ f w w1 ].
46 ndefinition w32h ≝ λdw:word32.match dw with [ mk_word32 x _ ⇒ x ].
47 ndefinition w32l ≝ λdw:word32.match dw with [ mk_word32 _ x ⇒ x ].
50 notation "〈x.y〉" non associative with precedence 80
51 for @{ 'mk_word32 $x $y }.
52 interpretation "mk_word32" 'mk_word32 x y = (mk_word32 x y).
55 ndefinition eq_w32 ≝ λdw1,dw2.(eq_w16 (w32h dw1) (w32h dw2)) ⊗ (eq_w16 (w32l dw1) (w32l dw2)).
59 λdw1,dw2:word32.match lt_w16 (w32h dw1) (w32h dw2) with
61 | false ⇒ match gt_w16 (w32h dw1) (w32h dw2) with
63 | false ⇒ lt_w16 (w32l dw1) (w32l dw2) ]].
66 ndefinition le_w32 ≝ λdw1,dw2:word32.(eq_w32 dw1 dw2) ⊕ (lt_w32 dw1 dw2).
69 ndefinition gt_w32 ≝ λdw1,dw2:word32.⊖ (le_w32 dw1 dw2).
72 ndefinition ge_w32 ≝ λdw1,dw2:word32.⊖ (lt_w32 dw1 dw2).
76 λdw1,dw2:word32.mk_word32 (and_w16 (w32h dw1) (w32h dw2)) (and_w16 (w32l dw1) (w32l dw2)).
80 λdw1,dw2:word32.mk_word32 (or_w16 (w32h dw1) (w32h dw2)) (or_w16 (w32l dw1) (w32l dw2)).
84 λdw1,dw2:word32.mk_word32 (xor_w16 (w32h dw1) (w32h dw2)) (xor_w16 (w32l dw1) (w32l dw2)).
86 (* operatore rotazione destra con carry *)
88 λdw:word32.λc:bool.match rcr_w16 (w32h dw) c with
89 [ pair wh' c' ⇒ match rcr_w16 (w32l dw) c' with
90 [ pair wl' c'' ⇒ pair ?? (mk_word32 wh' wl') c'' ]].
92 (* operatore shift destro *)
94 λdw:word32.match rcr_w16 (w32h dw) false with
95 [ pair wh' c' ⇒ match rcr_w16 (w32l dw) c' with
96 [ pair wl' c'' ⇒ pair ?? (mk_word32 wh' wl') c'' ]].
98 (* operatore rotazione destra *)
100 λdw:word32.match rcr_w16 (w32h dw) false with
101 [ pair wh' c' ⇒ match rcr_w16 (w32l dw) c' with
102 [ pair wl' c'' ⇒ match c'' with
103 [ true ⇒ mk_word32 (or_w16 (mk_word16 (mk_byte8 x8 x0) (mk_byte8 x0 x0)) wh') wl'
104 | false ⇒ mk_word32 wh' wl' ]]].
106 (* operatore rotazione destra n-volte *)
107 nlet rec ror_w32_n (dw:word32) (n:nat) on n ≝
110 | S n' ⇒ ror_w32_n (ror_w32 dw) n' ].
112 (* operatore rotazione sinistra con carry *)
113 ndefinition rcl_w32 ≝
114 λdw:word32.λc:bool.match rcl_w16 (w32l dw) c with
115 [ pair wl' c' ⇒ match rcl_w16 (w32h dw) c' with
116 [ pair wh' c'' ⇒ pair ?? (mk_word32 wh' wl') c'' ]].
118 (* operatore shift sinistro *)
119 ndefinition shl_w32 ≝
120 λdw:word32.match rcl_w16 (w32l dw) false with
121 [ pair wl' c' ⇒ match rcl_w16 (w32h dw) c' with
122 [ pair wh' c'' ⇒ pair ?? (mk_word32 wh' wl') c'' ]].
124 (* operatore rotazione sinistra *)
125 ndefinition rol_w32 ≝
126 λdw:word32.match rcl_w16 (w32l dw) false with
127 [ pair wl' c' ⇒ match rcl_w16 (w32h dw) c' with
128 [ pair wh' c'' ⇒ match c'' with
129 [ true ⇒ mk_word32 wh' (or_w16 (mk_word16 (mk_byte8 x0 x0) (mk_byte8 x0 x1)) wl')
130 | false ⇒ mk_word32 wh' wl' ]]].
132 (* operatore rotazione sinistra n-volte *)
133 nlet rec rol_w32_n (dw:word32) (n:nat) on n ≝
136 | S n' ⇒ rol_w32_n (rol_w32 dw) n' ].
138 (* operatore not/complemento a 1 *)
139 ndefinition not_w32 ≝
140 λdw:word32.mk_word32 (not_w16 (w32h dw)) (not_w16 (w32l dw)).
142 (* operatore somma con data+carry → data+carry *)
143 ndefinition plus_w32_dc_dc ≝
144 λdw1,dw2:word32.λc:bool.
145 match plus_w16_dc_dc (w32l dw1) (w32l dw2) c with
146 [ pair l c ⇒ match plus_w16_dc_dc (w32h dw1) (w32h dw2) c with
147 [ pair h c' ⇒ pair ?? 〈h.l〉 c' ]].
149 (* operatore somma con data+carry → data *)
150 ndefinition plus_w32_dc_d ≝
151 λdw1,dw2:word32.λc:bool.
152 match plus_w16_dc_dc (w32l dw1) (w32l dw2) c with
153 [ pair l c ⇒ 〈plus_w16_dc_d (w32h dw1) (w32h dw2) c.l〉 ].
155 (* operatore somma con data+carry → c *)
156 ndefinition plus_w32_dc_c ≝
157 λdw1,dw2:word32.λc:bool.
158 plus_w16_dc_c (w32h dw1) (w32h dw2) (plus_w16_dc_c (w32l dw1) (w32l dw2) c).
160 (* operatore somma con data → data+carry *)
161 ndefinition plus_w32_d_dc ≝
163 match plus_w16_d_dc (w32l dw1) (w32l dw2) with
164 [ pair l c ⇒ match plus_w16_dc_dc (w32h dw1) (w32h dw2) c with
165 [ pair h c' ⇒ pair ?? 〈h.l〉 c' ]].
167 (* operatore somma con data → data *)
168 ndefinition plus_w32_d_d ≝
170 match plus_w16_d_dc (w32l dw1) (w32l dw2) with
171 [ pair l c ⇒ 〈plus_w16_dc_d (w32h dw1) (w32h dw2) c.l〉 ].
173 (* operatore somma con data → c *)
174 ndefinition plus_w32_d_c ≝
176 plus_w16_dc_c (w32h dw1) (w32h dw2) (plus_w16_d_c (w32l dw1) (w32l dw2)).
178 (* operatore Most Significant Bit *)
179 ndefinition MSB_w32 ≝ λdw:word32.eq_ex x8 (and_ex x8 (b8h (w16h (w32h dw)))).
181 (* word → naturali *)
182 ndefinition nat_of_word32 ≝ λdw:word32. (256 * 256 * (nat_of_word16 (w32h dw))) + (nat_of_word16 (w32l dw)).
184 (* operatore predecessore *)
185 ndefinition pred_w32 ≝
186 λdw:word32.match eq_w16 (w32l dw) (mk_word16 (mk_byte8 x0 x0) (mk_byte8 x0 x0)) with
187 [ true ⇒ mk_word32 (pred_w16 (w32h dw)) (pred_w16 (w32l dw))
188 | false ⇒ mk_word32 (w32h dw) (pred_w16 (w32l dw)) ].
190 (* operatore successore *)
191 ndefinition succ_w32 ≝
192 λdw:word32.match eq_w16 (w32l dw) (mk_word16 (mk_byte8 xF xF) (mk_byte8 xF xF)) with
193 [ true ⇒ mk_word32 (succ_w16 (w32h dw)) (succ_w16 (w32l dw))
194 | false ⇒ mk_word32 (w32h dw) (succ_w16 (w32l dw)) ].
196 (* operatore neg/complemento a 2 *)
197 ndefinition compl_w32 ≝
198 λdw:word32.match MSB_w32 dw with
199 [ true ⇒ succ_w32 (not_w32 dw)
200 | false ⇒ not_w32 (pred_w32 dw) ].
203 operatore moltiplicazione senza segno: b*b=[0x00000000,0xFFFE0001]
204 ... in pratica (〈a:b〉*〈c:d〉) = (a*c)<<16+(a*d)<<8+(b*c)<<8+(b*d)
206 ndefinition mul_w16 ≝
207 λw1,w2:word16.match w1 with
208 [ mk_word16 b1h b1l ⇒ match w2 with
209 [ mk_word16 b2h b2l ⇒ match mul_b8 b1l b2l with
210 [ mk_word16 t1_h t1_l ⇒ match mul_b8 b1h b2l with
211 [ mk_word16 t2_h t2_l ⇒ match mul_b8 b2h b1l with
212 [ mk_word16 t3_h t3_l ⇒ match mul_b8 b1h b2h with
213 [ mk_word16 t4_h t4_l ⇒
216 (plus_w32_d_d 〈〈〈x0,x0〉:t3_h〉.〈t3_l:〈x0,x0〉〉〉 〈〈〈x0,x0〉:t2_h〉.〈t2_l:〈x0,x0〉〉〉) 〈〈t4_h:t4_l〉.〈〈x0,x0〉:〈x0,x0〉〉〉)〈〈〈x0,x0〉:〈x0,x0〉〉.〈t1_h:t1_l〉〉
219 (* divisione senza segno (secondo la logica delle ALU): (quoziente resto) overflow *)
220 nlet rec div_w16_aux (divd:word32) (divs:word32) (molt:word16) (q:word16) (c:nat) on c ≝
221 let w' ≝ plus_w32_d_d divd (compl_w32 divs) in
223 [ O ⇒ match le_w32 divs divd with
224 [ true ⇒ triple ??? (or_w16 molt q) (w32l w') (⊖ (eq_w16 (w32h w') 〈〈x0,x0〉:〈x0,x0〉〉))
225 | false ⇒ triple ??? q (w32l divd) (⊖ (eq_w16 (w32h divd) 〈〈x0,x0〉:〈x0,x0〉〉)) ]
226 | S c' ⇒ match le_w32 divs divd with
227 [ true ⇒ div_w16_aux w' (ror_w32 divs) (ror_w16 molt) (or_w16 molt q) c'
228 | false ⇒ div_w16_aux divd (ror_w32 divs) (ror_w16 molt) q c' ]].
230 ndefinition div_w16 ≝
231 λw:word32.λb:word16.match eq_w16 b 〈〈x0,x0〉:〈x0,x0〉〉 with
233 la combinazione n/0 e' illegale, segnala solo overflow senza dare risultato
235 [ true ⇒ triple ??? 〈〈xF,xF〉:〈xF,xF〉〉 (w32l w) true
236 | false ⇒ match eq_w32 w 〈〈〈x0,x0〉:〈x0,x0〉〉.〈〈x0,x0〉:〈x0,x0〉〉〉 with
237 (* 0 diviso qualsiasi cosa diverso da 0 da' q=0 r=0 o=false *)
238 [ true ⇒ triple ??? 〈〈x0,x0〉:〈x0,x0〉〉 〈〈x0,x0〉:〈x0,x0〉〉 false
239 (* 1) e' una divisione sensata che produrra' overflow/risultato *)
240 (* 2) parametri: dividendo, divisore, moltiplicatore, quoziente, contatore *)
241 (* 3) ad ogni ciclo il divisore e il moltiplicatore vengono scalati di 1 a dx *)
242 (* 4) il moltiplicatore e' la quantita' aggiunta al quoziente se il divisore *)
243 (* puo' essere sottratto al dividendo *)
244 | false ⇒ div_w16_aux w (rol_w32_n 〈〈〈x0,x0〉:〈x0,x0〉〉.b〉 15) 〈〈x8,x0〉:〈x0,x0〉〉 〈〈x0,x0〉:〈x0,x0〉〉 15 ]].
246 (* operatore x in [inf,sup] *)
247 ndefinition in_range ≝
248 λx,inf,sup:word32.(le_w32 inf sup) ⊗ (ge_w32 x inf) ⊗ (le_w32 x sup).
250 (* iteratore sulle word *)
251 ndefinition forall_word32 ≝
255 P (mk_word32 bh bl ))).