helm/software/matita/contribs/ng_assembly/num/word32.ma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||         The HELM team.                                      *)
   8 (*      ||A||         http://helm.cs.unibo.it                             *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU General Public License Version 2                  *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 (* ********************************************************************** *)
  16 (*                          Progetto FreeScale                            *)
  17 (*                                                                        *)
  18 (*   Sviluppato da: Ing. Cosimo Oliboni, oliboni@cs.unibo.it              *)
  19 (*   Ultima modifica: 05/08/2009                                          *)
  20 (*                                                                        *)
  21 (* ********************************************************************** *)
  22
  23 include "num/word16.ma".
  24
  25 (* ***** *)
  26 (* DWORD *)
  27 (* ***** *)
  28
  29 nrecord word32 : Type ≝
  30  {
  31  w32h: word16;
  32  w32l: word16
  33  }.
  34
  35 (* \langle \rangle *)
  36 notation "〈x.y〉" non associative with precedence 80
  37  for @{ 'mk_word32 $x $y }.
  38 interpretation "mk_word32" 'mk_word32 x y = (mk_word32 x y).
  39
  40 (* operatore = *)
  41 ndefinition eq_w32 ≝ λdw1,dw2.(eq_w16 (w32h dw1) (w32h dw2)) ⊗ (eq_w16 (w32l dw1) (w32l dw2)).
  42
  43 (* operatore < *)
  44 ndefinition lt_w32 ≝
  45 λdw1,dw2:word32.
  46  (lt_w16 (w32h dw1) (w32h dw2)) ⊕
  47  ((eq_w16 (w32h dw1) (w32h dw2)) ⊗ (lt_w16 (w32l dw1) (w32l dw2))).
  48
  49 (* operatore ≤ *)
  50 ndefinition le_w32 ≝
  51 λdw1,dw2:word32.
  52  (lt_w16 (w32h dw1) (w32h dw2)) ⊕
  53  ((eq_w16 (w32h dw1) (w32h dw2)) ⊗ (le_w16 (w32l dw1) (w32l dw2))).
  54
  55 (* operatore > *)
  56 ndefinition gt_w32 ≝
  57 λdw1,dw2:word32.
  58  (gt_w16 (w32h dw1) (w32h dw2)) ⊕
  59  ((eq_w16 (w32h dw1) (w32h dw2)) ⊗ (gt_w16 (w32l dw1) (w32l dw2))).
  60
  61 (* operatore ≥ *)
  62 ndefinition ge_w32 ≝
  63 λdw1,dw2:word32.
  64  (gt_w16 (w32h dw1) (w32h dw2)) ⊕
  65  ((eq_w16 (w32h dw1) (w32h dw2)) ⊗ (ge_w16 (w32l dw1) (w32l dw2))).
  66
  67 (* operatore and *)
  68 ndefinition and_w32 ≝
  69 λdw1,dw2:word32.mk_word32 (and_w16 (w32h dw1) (w32h dw2)) (and_w16 (w32l dw1) (w32l dw2)).
  70
  71 (* operatore or *)
  72 ndefinition or_w32 ≝
  73 λdw1,dw2:word32.mk_word32 (or_w16 (w32h dw1) (w32h dw2)) (or_w16 (w32l dw1) (w32l dw2)).
  74
  75 (* operatore xor *)
  76 ndefinition xor_w32 ≝
  77 λdw1,dw2:word32.mk_word32 (xor_w16 (w32h dw1) (w32h dw2)) (xor_w16 (w32l dw1) (w32l dw2)).
  78
  79 (* operatore rotazione destra con carry *)
  80 ndefinition rcr_w32 ≝
  81 λdw:word32.λc:bool.match rcr_w16 (w32h dw) c with
  82  [ pair wh' c' ⇒ match rcr_w16 (w32l dw) c' with
  83   [ pair wl' c'' ⇒ pair … (mk_word32 wh' wl') c'' ]].
  84
  85 (* operatore shift destro *)
  86 ndefinition shr_w32 ≝
  87 λdw:word32.match rcr_w16 (w32h dw) false with
  88  [ pair wh' c' ⇒ match rcr_w16 (w32l dw) c' with
  89   [ pair wl' c'' ⇒ pair … (mk_word32 wh' wl') c'' ]].
  90
  91 (* operatore rotazione destra *)
  92 ndefinition ror_w32 ≝
  93 λdw:word32.match rcr_w16 (w32h dw) false with
  94  [ pair wh' c' ⇒ match rcr_w16 (w32l dw) c' with
  95   [ pair wl' c'' ⇒ match c'' with
  96    [ true ⇒ mk_word32 (or_w16 (mk_word16 (mk_byte8 x8 x0) (mk_byte8 x0 x0)) wh') wl'
  97    | false ⇒ mk_word32 wh' wl' ]]].
  98
  99 (* operatore rotazione destra n-volte *)
 100 nlet rec ror_w32_n (dw:word32) (n:nat) on n ≝
 101  match n with
 102   [ O ⇒ dw
 103   | S n' ⇒ ror_w32_n (ror_w32 dw) n' ].
 104
 105 (* operatore rotazione sinistra con carry *)
 106 ndefinition rcl_w32 ≝
 107 λdw:word32.λc:bool.match rcl_w16 (w32l dw) c with
 108  [ pair wl' c' ⇒ match rcl_w16 (w32h dw) c' with
 109   [ pair wh' c'' ⇒ pair … (mk_word32 wh' wl') c'' ]].
 110
 111 (* operatore shift sinistro *)
 112 ndefinition shl_w32 ≝
 113 λdw:word32.match rcl_w16 (w32l dw) false with
 114  [ pair wl' c' ⇒ match rcl_w16 (w32h dw) c' with
 115   [ pair wh' c'' ⇒ pair … (mk_word32 wh' wl') c'' ]].
 116
 117 (* operatore rotazione sinistra *)
 118 ndefinition rol_w32 ≝
 119 λdw:word32.match rcl_w16 (w32l dw) false with
 120  [ pair wl' c' ⇒ match rcl_w16 (w32h dw) c' with
 121   [ pair wh' c'' ⇒ match c'' with
 122    [ true ⇒ mk_word32 wh' (or_w16 (mk_word16 (mk_byte8 x0 x0) (mk_byte8 x0 x1)) wl')
 123    | false ⇒ mk_word32 wh' wl' ]]].
 124
 125 (* operatore rotazione sinistra n-volte *)
 126 nlet rec rol_w32_n (dw:word32) (n:nat) on n ≝
 127  match n with
 128   [ O ⇒ dw
 129   | S n' ⇒ rol_w32_n (rol_w32 dw) n' ].
 130
 131 (* operatore not/complemento a 1 *)
 132 ndefinition not_w32 ≝
 133 λdw:word32.mk_word32 (not_w16 (w32h dw)) (not_w16 (w32l dw)).
 134
 135 (* operatore somma con data+carry → data+carry *)
 136 ndefinition plus_w32_dc_dc ≝
 137 λdw1,dw2:word32.λc:bool.
 138  match plus_w16_dc_dc (w32l dw1) (w32l dw2) c with
 139   [ pair l c ⇒ match plus_w16_dc_dc (w32h dw1) (w32h dw2) c with
 140    [ pair h c' ⇒ pair … 〈h.l〉 c' ]].
 141
 142 (* operatore somma con data+carry → data *)
 143 ndefinition plus_w32_dc_d ≝
 144 λdw1,dw2:word32.λc:bool.
 145  match plus_w16_dc_dc (w32l dw1) (w32l dw2) c with
 146   [ pair l c ⇒ 〈plus_w16_dc_d (w32h dw1) (w32h dw2) c.l〉 ].
 147
 148 (* operatore somma con data+carry → c *)
 149 ndefinition plus_w32_dc_c ≝
 150 λdw1,dw2:word32.λc:bool.
 151  plus_w16_dc_c (w32h dw1) (w32h dw2) (plus_w16_dc_c (w32l dw1) (w32l dw2) c).
 152
 153 (* operatore somma con data → data+carry *)
 154 ndefinition plus_w32_d_dc ≝
 155 λdw1,dw2:word32.
 156  match plus_w16_d_dc (w32l dw1) (w32l dw2) with
 157   [ pair l c ⇒ match plus_w16_dc_dc (w32h dw1) (w32h dw2) c with
 158    [ pair h c' ⇒ pair … 〈h.l〉 c' ]].
 159
 160 (* operatore somma con data → data *)
 161 ndefinition plus_w32_d_d ≝
 162 λdw1,dw2:word32.
 163  match plus_w16_d_dc (w32l dw1) (w32l dw2) with
 164   [ pair l c ⇒ 〈plus_w16_dc_d (w32h dw1) (w32h dw2) c.l〉 ].
 165
 166 (* operatore somma con data → c *)
 167 ndefinition plus_w32_d_c ≝
 168 λdw1,dw2:word32.
 169  plus_w16_dc_c (w32h dw1) (w32h dw2) (plus_w16_d_c (w32l dw1) (w32l dw2)).
 170
 171 (* operatore Most Significant Bit *)
 172 ndefinition MSB_w32 ≝ λdw:word32.eq_ex x8 (and_ex x8 (b8h (w16h (w32h dw)))).
 173
 174 (* operatore predecessore *)
 175 ndefinition pred_w32 ≝
 176 λdw:word32.match eq_w16 (w32l dw) (mk_word16 (mk_byte8 x0 x0) (mk_byte8 x0 x0)) with
 177  [ true ⇒ mk_word32 (pred_w16 (w32h dw)) (pred_w16 (w32l dw))
 178  | false ⇒ mk_word32 (w32h dw) (pred_w16 (w32l dw)) ].
 179
 180 (* operatore successore *)
 181 ndefinition succ_w32 ≝
 182 λdw:word32.match eq_w16 (w32l dw) (mk_word16 (mk_byte8 xF xF) (mk_byte8 xF xF)) with
 183  [ true ⇒ mk_word32 (succ_w16 (w32h dw)) (succ_w16 (w32l dw))
 184  | false ⇒ mk_word32 (w32h dw) (succ_w16 (w32l dw)) ].
 185
 186 (* operatore neg/complemento a 2 *)
 187 ndefinition compl_w32 ≝
 188 λdw:word32.match MSB_w32 dw with
 189  [ true ⇒ succ_w32 (not_w32 dw)
 190  | false ⇒ not_w32 (pred_w32 dw) ].
 191
 192 (*
 193    operatore moltiplicazione senza segno: b*b=[0x00000000,0xFFFE0001]
 194    ... in pratica (〈a:b〉*〈c:d〉) = (a*c)<<16+(a*d)<<8+(b*c)<<8+(b*d)
 195 *)
 196 ndefinition mul_w16 ≝
 197 λw1,w2:word16.match w1 with
 198 [ mk_word16 b1h b1l ⇒ match w2 with
 199 [ mk_word16 b2h b2l ⇒ match mul_b8 b1l b2l with
 200 [ mk_word16 t1_h t1_l ⇒ match mul_b8 b1h b2l with
 201 [ mk_word16 t2_h t2_l ⇒ match mul_b8 b2h b1l with
 202 [ mk_word16 t3_h t3_l ⇒ match mul_b8 b1h b2h with
 203 [ mk_word16 t4_h t4_l ⇒
 204  plus_w32_d_d
 205   (plus_w32_d_d
 206    (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〉〉
 207 ]]]]]].
 208
 209 (* divisione senza segno (secondo la logica delle ALU): (quoziente resto) overflow *)
 210 nlet rec div_w16_aux (divd:word32) (divs:word32) (molt:word16) (q:word16) (c:nat) on c ≝
 211   let w' ≝ plus_w32_d_d divd (compl_w32 divs) in
 212    match c with
 213    [ O ⇒ match le_w32 divs divd with
 214     [ true ⇒ triple … (or_w16 molt q) (w32l w') (⊖ (eq_w16 (w32h w') 〈〈x0,x0〉:〈x0,x0〉〉))
 215     | false ⇒ triple … q (w32l divd) (⊖ (eq_w16 (w32h divd) 〈〈x0,x0〉:〈x0,x0〉〉)) ]
 216    | S c' ⇒ match le_w32 divs divd with
 217     [ true ⇒ div_w16_aux w' (ror_w32 divs) (ror_w16 molt) (or_w16 molt q) c'
 218     | false ⇒ div_w16_aux divd (ror_w32 divs) (ror_w16 molt) q c' ]].
 219
 220 ndefinition div_w16 ≝
 221 λw:word32.λb:word16.match eq_w16 b 〈〈x0,x0〉:〈x0,x0〉〉 with
 222 (*
 223    la combinazione n/0 e' illegale, segnala solo overflow senza dare risultato
 224 *)
 225  [ true ⇒ triple … 〈〈xF,xF〉:〈xF,xF〉〉 (w32l w) true
 226  | false ⇒ match eq_w32 w 〈〈〈x0,x0〉:〈x0,x0〉〉.〈〈x0,x0〉:〈x0,x0〉〉〉 with
 227 (* 0 diviso qualsiasi cosa diverso da 0 da' q=0 r=0 o=false *)
 228   [ true ⇒ triple … 〈〈x0,x0〉:〈x0,x0〉〉 〈〈x0,x0〉:〈x0,x0〉〉 false
 229 (* 1) e' una divisione sensata che produrra' overflow/risultato *)
 230 (* 2) parametri: dividendo, divisore, moltiplicatore, quoziente, contatore *)
 231 (* 3) ad ogni ciclo il divisore e il moltiplicatore vengono scalati di 1 a dx *)
 232 (* 4) il moltiplicatore e' la quantita' aggiunta al quoziente se il divisore *)
 233 (*    puo' essere sottratto al dividendo *)
 234   | false ⇒ div_w16_aux w (rol_w32_n 〈〈〈x0,x0〉:〈x0,x0〉〉.b〉 nat15) 〈〈x8,x0〉:〈x0,x0〉〉 〈〈x0,x0〉:〈x0,x0〉〉 nat15 ]].
 235
 236 (* operatore x in [inf,sup] *)
 237 ndefinition inrange_w32 ≝
 238 λx,inf,sup:word32.(le_w32 inf x) ⊗ (le_w32 x sup).
 239
 240 (* iteratore sulle word *)
 241 ndefinition forall_w32 ≝
 242  λP.
 243   forall_w16 (λbh.
 244   forall_w16 (λbl.
 245    P (mk_word32 bh bl ))).