src/HOL/Word/Bit_Representation.thy
changeset 46001 0b562d564d5f
parent 46000 871bdab23f5c
child 46008 c296c75f4cf4
child 46023 fad87bb608fc
equal deleted inserted replaced
46000:871bdab23f5c 46001:0b562d564d5f
   324 lemma bin_sign_rest [simp]: 
   324 lemma bin_sign_rest [simp]: 
   325   "bin_sign (bin_rest w) = bin_sign w"
   325   "bin_sign (bin_rest w) = bin_sign w"
   326   by (cases w rule: bin_exhaust) auto
   326   by (cases w rule: bin_exhaust) auto
   327 
   327 
   328 primrec bintrunc :: "nat \<Rightarrow> int \<Rightarrow> int" where
   328 primrec bintrunc :: "nat \<Rightarrow> int \<Rightarrow> int" where
   329   Z : "bintrunc 0 bin = Int.Pls"
   329   Z : "bintrunc 0 bin = 0"
   330 | Suc : "bintrunc (Suc n) bin = bintrunc n (bin_rest bin) BIT (bin_last bin)"
   330 | Suc : "bintrunc (Suc n) bin = bintrunc n (bin_rest bin) BIT (bin_last bin)"
   331 
   331 
   332 primrec sbintrunc :: "nat => int => int" where
   332 primrec sbintrunc :: "nat => int => int" where
   333   Z : "sbintrunc 0 bin = 
   333   Z : "sbintrunc 0 bin = (case bin_last bin of (1::bit) \<Rightarrow> -1 | (0::bit) \<Rightarrow> 0)"
   334     (case bin_last bin of (1::bit) => Int.Min | (0::bit) => Int.Pls)"
       
   335 | Suc : "sbintrunc (Suc n) bin = sbintrunc n (bin_rest bin) BIT (bin_last bin)"
   334 | Suc : "sbintrunc (Suc n) bin = sbintrunc n (bin_rest bin) BIT (bin_last bin)"
   336 
   335 
   337 lemma [code]:
   336 lemma sign_bintr: "bin_sign (bintrunc n w) = 0"
   338   "sbintrunc 0 bin = 
       
   339     (case bin_last bin of (1::bit) => - 1 | (0::bit) => 0)"
       
   340   "sbintrunc (Suc n) bin = sbintrunc n (bin_rest bin) BIT (bin_last bin)"
       
   341   apply simp_all
       
   342   apply (simp only: Pls_def Min_def)
       
   343   done
       
   344 
       
   345 lemma sign_bintr: "bin_sign (bintrunc n w) = Int.Pls"
       
   346   by (induct n arbitrary: w) auto
   337   by (induct n arbitrary: w) auto
   347 
   338 
   348 lemma bintrunc_mod2p: "bintrunc n w = (w mod 2 ^ n)"
   339 lemma bintrunc_mod2p: "bintrunc n w = (w mod 2 ^ n)"
   349   apply (induct n arbitrary: w)
   340   apply (induct n arbitrary: w)
   350   apply (simp add: Pls_def)
   341   apply simp
   351   apply (simp add: bin_last_def bin_rest_def Bit_def zmod_zmult2_eq)
   342   apply (simp add: bin_last_def bin_rest_def Bit_def zmod_zmult2_eq)
   352   done
   343   done
   353 
   344 
   354 lemma sbintrunc_mod2p: "sbintrunc n w = (w + 2 ^ n) mod 2 ^ (Suc n) - 2 ^ n"
   345 lemma sbintrunc_mod2p: "sbintrunc n w = (w + 2 ^ n) mod 2 ^ (Suc n) - 2 ^ n"
   355   apply (induct n arbitrary: w)
   346   apply (induct n arbitrary: w)
   356    apply clarsimp
   347    apply clarsimp
   357    apply (subst mod_add_left_eq)
   348    apply (subst mod_add_left_eq)
   358    apply (simp add: bin_last_def)
   349    apply (simp add: bin_last_def)
   359    apply (simp add: number_of_eq)
   350   apply simp
   360   apply (simp add: Pls_def)
   351   apply (simp add: bin_last_def bin_rest_def Bit_def)
   361   apply (simp add: bin_last_def bin_rest_def Bit_def 
       
   362               cong: number_of_False_cong)
       
   363   apply (clarsimp simp: mod_mult_mult1 [symmetric] 
   352   apply (clarsimp simp: mod_mult_mult1 [symmetric] 
   364          zmod_zdiv_equality [THEN diff_eq_eq [THEN iffD2 [THEN sym]]])
   353          zmod_zdiv_equality [THEN diff_eq_eq [THEN iffD2 [THEN sym]]])
   365   apply (rule trans [symmetric, OF _ emep1])
   354   apply (rule trans [symmetric, OF _ emep1])
   366      apply auto
   355      apply auto
   367   apply (auto simp: even_def)
   356   apply (auto simp: even_def)
   368   done
   357   done
   369 
   358 
   370 subsection "Simplifications for (s)bintrunc"
   359 subsection "Simplifications for (s)bintrunc"
   371 
   360 
   372 lemma bintrunc_n_0 [simp]: "bintrunc n 0 = 0"
   361 lemma bintrunc_n_0 [simp]: "bintrunc n 0 = 0"
   373   by (induct n) (auto simp add: Int.Pls_def)
   362   by (induct n) auto
   374 
   363 
   375 lemma sbintrunc_n_0 [simp]: "sbintrunc n 0 = 0"
   364 lemma sbintrunc_n_0 [simp]: "sbintrunc n 0 = 0"
   376   by (induct n) (auto simp add: Int.Pls_def)
   365   by (induct n) auto
   377 
   366 
   378 lemma sbintrunc_n_minus1 [simp]: "sbintrunc n -1 = -1"
   367 lemma sbintrunc_n_minus1 [simp]: "sbintrunc n -1 = -1"
   379   by (induct n) (auto, simp add: number_of_is_id)
   368   by (induct n) auto
   380 
   369 
   381 lemma bintrunc_Suc_numeral:
   370 lemma bintrunc_Suc_numeral:
   382   "bintrunc (Suc n) 1 = 1"
   371   "bintrunc (Suc n) 1 = 1"
   383   "bintrunc (Suc n) -1 = bintrunc n -1 BIT 1"
   372   "bintrunc (Suc n) -1 = bintrunc n -1 BIT 1"
   384   "bintrunc (Suc n) (number_of (Int.Bit0 w)) = bintrunc n (number_of w) BIT 0"
   373   "bintrunc (Suc n) (number_of (Int.Bit0 w)) = bintrunc n (number_of w) BIT 0"
   387 
   376 
   388 lemma sbintrunc_0_numeral [simp]:
   377 lemma sbintrunc_0_numeral [simp]:
   389   "sbintrunc 0 1 = -1"
   378   "sbintrunc 0 1 = -1"
   390   "sbintrunc 0 (number_of (Int.Bit0 w)) = 0"
   379   "sbintrunc 0 (number_of (Int.Bit0 w)) = 0"
   391   "sbintrunc 0 (number_of (Int.Bit1 w)) = -1"
   380   "sbintrunc 0 (number_of (Int.Bit1 w)) = -1"
   392   by (simp_all, unfold Pls_def number_of_is_id, simp_all)
   381   by simp_all
   393 
   382 
   394 lemma sbintrunc_Suc_numeral:
   383 lemma sbintrunc_Suc_numeral:
   395   "sbintrunc (Suc n) 1 = 1"
   384   "sbintrunc (Suc n) 1 = 1"
   396   "sbintrunc (Suc n) (number_of (Int.Bit0 w)) = sbintrunc n (number_of w) BIT 0"
   385   "sbintrunc (Suc n) (number_of (Int.Bit0 w)) = sbintrunc n (number_of w) BIT 0"
   397   "sbintrunc (Suc n) (number_of (Int.Bit1 w)) = sbintrunc n (number_of w) BIT 1"
   386   "sbintrunc (Suc n) (number_of (Int.Bit1 w)) = sbintrunc n (number_of w) BIT 1"
   401   "(b = (b' = (1::bit))) = (b' = (if b then (1::bit) else (0::bit)))"
   390   "(b = (b' = (1::bit))) = (b' = (if b then (1::bit) else (0::bit)))"
   402   by (cases b') auto
   391   by (cases b') auto
   403 
   392 
   404 lemmas bit_bool1 [simp] = refl [THEN bit_bool [THEN iffD1], symmetric]
   393 lemmas bit_bool1 [simp] = refl [THEN bit_bool [THEN iffD1], symmetric]
   405 
   394 
   406 lemma bin_sign_lem: "(bin_sign (sbintrunc n bin) = Int.Min) = bin_nth bin n"
   395 lemma bin_sign_lem: "(bin_sign (sbintrunc n bin) = -1) = bin_nth bin n"
   407   apply (induct n arbitrary: bin)
   396   apply (induct n arbitrary: bin)
   408    apply (case_tac bin rule: bin_exhaust, case_tac b, auto)+
   397    apply (case_tac bin rule: bin_exhaust, case_tac b, auto)+
   409   done
   398   done
   410 
   399 
   411 lemma nth_bintr: "bin_nth (bintrunc m w) n = (n < m & bin_nth w n)"
   400 lemma nth_bintr: "bin_nth (bintrunc m w) n = (n < m & bin_nth w n)"
   514 
   503 
   515 lemmas sbintrunc_0_BIT_B1 [simp] = 
   504 lemmas sbintrunc_0_BIT_B1 [simp] = 
   516   sbintrunc.Z [where bin="w BIT (1::bit)", 
   505   sbintrunc.Z [where bin="w BIT (1::bit)", 
   517                simplified bin_last_simps bin_rest_simps bit.simps] for w
   506                simplified bin_last_simps bin_rest_simps bit.simps] for w
   518 
   507 
   519 lemma sbintrunc_0_Bit0 [simp]: "sbintrunc 0 (Int.Bit0 w) = Int.Pls"
   508 lemma sbintrunc_0_Bit0 [simp]: "sbintrunc 0 (Int.Bit0 w) = 0"
   520   using sbintrunc_0_BIT_B0 by simp
   509   using sbintrunc_0_BIT_B0 by simp
   521 
   510 
   522 lemma sbintrunc_0_Bit1 [simp]: "sbintrunc 0 (Int.Bit1 w) = Int.Min"
   511 lemma sbintrunc_0_Bit1 [simp]: "sbintrunc 0 (Int.Bit1 w) = -1"
   523   using sbintrunc_0_BIT_B1 by simp
   512   using sbintrunc_0_BIT_B1 by simp
   524 
   513 
   525 lemmas sbintrunc_0_simps =
   514 lemmas sbintrunc_0_simps =
   526   sbintrunc_Pls sbintrunc_Min sbintrunc_0_BIT_B0 sbintrunc_0_BIT_B1
   515   sbintrunc_Pls sbintrunc_Min sbintrunc_0_BIT_B0 sbintrunc_0_BIT_B1
   527   sbintrunc_0_Bit0 sbintrunc_0_Bit1
   516   sbintrunc_0_Bit0 sbintrunc_0_Bit1
   542 lemmas sbintrunc_minus_simps = 
   531 lemmas sbintrunc_minus_simps = 
   543   sbintrunc_Sucs [THEN [2] sbintrunc_minus [symmetric, THEN trans]]
   532   sbintrunc_Sucs [THEN [2] sbintrunc_minus [symmetric, THEN trans]]
   544 
   533 
   545 lemma bintrunc_n_Pls [simp]:
   534 lemma bintrunc_n_Pls [simp]:
   546   "bintrunc n Int.Pls = Int.Pls"
   535   "bintrunc n Int.Pls = Int.Pls"
   547   by (induct n) (auto simp: BIT_simps)
   536   unfolding Pls_def by simp
   548 
   537 
   549 lemma sbintrunc_n_PM [simp]:
   538 lemma sbintrunc_n_PM [simp]:
   550   "sbintrunc n Int.Pls = Int.Pls"
   539   "sbintrunc n Int.Pls = Int.Pls"
   551   "sbintrunc n Int.Min = Int.Min"
   540   "sbintrunc n Int.Min = Int.Min"
   552   by (induct n) (auto simp: BIT_simps)
   541   unfolding Pls_def Min_def by simp_all
   553 
   542 
   554 lemmas thobini1 = arg_cong [where f = "%w. w BIT b"] for b
   543 lemmas thobini1 = arg_cong [where f = "%w. w BIT b"] for b
   555 
   544 
   556 lemmas bintrunc_BIT_I = trans [OF bintrunc_BIT thobini1]
   545 lemmas bintrunc_BIT_I = trans [OF bintrunc_BIT thobini1]
   557 lemmas bintrunc_Min_I = trans [OF bintrunc_Min thobini1]
   546 lemmas bintrunc_Min_I = trans [OF bintrunc_Min thobini1]
   821   [THEN rco_lem [THEN fun_cong], unfolded o_def]
   810   [THEN rco_lem [THEN fun_cong], unfolded o_def]
   822 
   811 
   823 subsection {* Splitting and concatenation *}
   812 subsection {* Splitting and concatenation *}
   824 
   813 
   825 primrec bin_split :: "nat \<Rightarrow> int \<Rightarrow> int \<times> int" where
   814 primrec bin_split :: "nat \<Rightarrow> int \<Rightarrow> int \<times> int" where
   826   Z: "bin_split 0 w = (w, Int.Pls)"
   815   Z: "bin_split 0 w = (w, 0)"
   827   | Suc: "bin_split (Suc n) w = (let (w1, w2) = bin_split n (bin_rest w)
   816   | Suc: "bin_split (Suc n) w = (let (w1, w2) = bin_split n (bin_rest w)
   828         in (w1, w2 BIT bin_last w))"
   817         in (w1, w2 BIT bin_last w))"
   829 
   818 
   830 lemma [code]:
   819 lemma [code]:
   831   "bin_split (Suc n) w = (let (w1, w2) = bin_split n (bin_rest w) in (w1, w2 BIT bin_last w))"
   820   "bin_split (Suc n) w = (let (w1, w2) = bin_split n (bin_rest w) in (w1, w2 BIT bin_last w))"