src/HOL/Word/Word.thy
changeset 45995 b16070689726
parent 45958 c28235388c43
child 45998 d7cc533ae60d
equal deleted inserted replaced
45987:9ba44b49859b 45995:b16070689726
   630 lemma sint_number_of: "sint (number_of b :: 'a :: len word) = (number_of b + 
   630 lemma sint_number_of: "sint (number_of b :: 'a :: len word) = (number_of b + 
   631     2 ^ (len_of TYPE('a) - 1)) mod 2 ^ len_of TYPE('a) -
   631     2 ^ (len_of TYPE('a) - 1)) mod 2 ^ len_of TYPE('a) -
   632     2 ^ (len_of TYPE('a) - 1)"
   632     2 ^ (len_of TYPE('a) - 1)"
   633   unfolding word_number_of_alt by (rule int_word_sint)
   633   unfolding word_number_of_alt by (rule int_word_sint)
   634 
   634 
   635 lemma word_of_int_0: "word_of_int 0 = 0"
   635 lemma word_of_int_0 [simp]: "word_of_int 0 = 0"
   636   unfolding word_0_wi ..
   636   unfolding word_0_wi ..
   637 
   637 
   638 lemma word_of_int_1: "word_of_int 1 = 1"
   638 lemma word_of_int_1 [simp]: "word_of_int 1 = 1"
   639   unfolding word_1_wi ..
   639   unfolding word_1_wi ..
   640 
   640 
   641 lemma word_of_int_bin [simp] : 
   641 lemma word_of_int_bin [simp] : 
   642   "(word_of_int (number_of bin) :: 'a :: len0 word) = (number_of bin)"
   642   "(word_of_int (number_of bin) :: 'a :: len0 word) = (number_of bin)"
   643   unfolding word_number_of_alt by auto
   643   unfolding word_number_of_alt by auto
  1104   *)
  1104   *)
  1105 lemma word_0_wi_Pls: "0 = word_of_int Int.Pls"
  1105 lemma word_0_wi_Pls: "0 = word_of_int Int.Pls"
  1106   by (simp only: Pls_def word_0_wi)
  1106   by (simp only: Pls_def word_0_wi)
  1107 
  1107 
  1108 lemma word_0_no: "(0::'a::len0 word) = Numeral0"
  1108 lemma word_0_no: "(0::'a::len0 word) = Numeral0"
  1109   by (simp add: word_number_of_alt word_0_wi)
  1109   by (simp add: word_number_of_alt)
  1110 
  1110 
  1111 lemma int_one_bin: "(1 :: int) = (Int.Pls BIT 1)"
  1111 lemma int_one_bin: "(1 :: int) = (Int.Pls BIT 1)"
  1112   unfolding Pls_def Bit_def by auto
  1112   unfolding Pls_def Bit_def by auto
  1113 
  1113 
  1114 lemma word_1_no: 
  1114 lemma word_1_no: 
  1120 
  1120 
  1121 lemma word_m1_wi_Min: "-1 = word_of_int Int.Min"
  1121 lemma word_m1_wi_Min: "-1 = word_of_int Int.Min"
  1122   by (simp add: word_m1_wi number_of_eq)
  1122   by (simp add: word_m1_wi number_of_eq)
  1123 
  1123 
  1124 lemma word_0_bl [simp]: "of_bl [] = 0" 
  1124 lemma word_0_bl [simp]: "of_bl [] = 0" 
  1125   unfolding word_0_wi of_bl_def by (simp add : Pls_def)
  1125   unfolding of_bl_def by (simp add: Pls_def)
  1126 
  1126 
  1127 lemma word_1_bl: "of_bl [True] = 1" 
  1127 lemma word_1_bl: "of_bl [True] = 1" 
  1128   unfolding word_1_wi of_bl_def
  1128   unfolding of_bl_def
  1129   by (simp add : bl_to_bin_def Bit_def Pls_def)
  1129   by (simp add: bl_to_bin_def Bit_def Pls_def)
  1130 
  1130 
  1131 lemma uint_eq_0 [simp] : "(uint 0 = 0)" 
  1131 lemma uint_eq_0 [simp] : "(uint 0 = 0)" 
  1132   unfolding word_0_wi
  1132   unfolding word_0_wi
  1133   by (simp add: word_ubin.eq_norm Pls_def [symmetric])
  1133   by (simp add: word_ubin.eq_norm Pls_def [symmetric])
  1134 
  1134 
  1135 lemma of_bl_0 [simp] : "of_bl (replicate n False) = 0"
  1135 lemma of_bl_0 [simp]: "of_bl (replicate n False) = 0"
  1136   by (simp add : word_0_wi of_bl_def bl_to_bin_rep_False Pls_def)
  1136   by (simp add: of_bl_def bl_to_bin_rep_False Pls_def)
  1137 
  1137 
  1138 lemma to_bl_0 [simp]:
  1138 lemma to_bl_0 [simp]:
  1139   "to_bl (0::'a::len0 word) = replicate (len_of TYPE('a)) False"
  1139   "to_bl (0::'a::len0 word) = replicate (len_of TYPE('a)) False"
  1140   unfolding uint_bl
  1140   unfolding uint_bl
  1141   by (simp add : word_size bin_to_bl_Pls Pls_def [symmetric])
  1141   by (simp add : word_size bin_to_bl_Pls Pls_def [symmetric])
  1165 
  1165 
  1166 lemma unat_gt_0: "(0 < unat x) = (x ~= 0)"
  1166 lemma unat_gt_0: "(0 < unat x) = (x ~= 0)"
  1167 by (auto simp: unat_0_iff [symmetric])
  1167 by (auto simp: unat_0_iff [symmetric])
  1168 
  1168 
  1169 lemma ucast_0 [simp]: "ucast 0 = 0"
  1169 lemma ucast_0 [simp]: "ucast 0 = 0"
  1170   unfolding ucast_def by (simp add: word_of_int_0)
  1170   unfolding ucast_def by simp
  1171 
  1171 
  1172 lemma sint_0 [simp]: "sint 0 = 0"
  1172 lemma sint_0 [simp]: "sint 0 = 0"
  1173   unfolding sint_uint by simp
  1173   unfolding sint_uint by simp
  1174 
  1174 
  1175 lemma scast_0 [simp]: "scast 0 = 0"
  1175 lemma scast_0 [simp]: "scast 0 = 0"
  1176   unfolding scast_def by (simp add: word_of_int_0)
  1176   unfolding scast_def by simp
  1177 
  1177 
  1178 lemma sint_n1 [simp] : "sint -1 = -1"
  1178 lemma sint_n1 [simp] : "sint -1 = -1"
  1179   unfolding word_m1_wi by (simp add: word_sbin.eq_norm)
  1179   unfolding word_m1_wi by (simp add: word_sbin.eq_norm)
  1180 
  1180 
  1181 lemma scast_n1 [simp]: "scast -1 = -1"
  1181 lemma scast_n1 [simp]: "scast -1 = -1"
  1182   unfolding scast_def by simp
  1182   unfolding scast_def by simp
  1183 
  1183 
  1184 lemma uint_1 [simp]: "uint (1::'a::len word) = 1"
  1184 lemma uint_1 [simp]: "uint (1::'a::len word) = 1"
  1185   unfolding word_1_wi
  1185   unfolding word_1_wi
  1186   by (simp add: word_ubin.eq_norm bintrunc_minus_simps)
  1186   by (simp add: word_ubin.eq_norm bintrunc_minus_simps del: word_of_int_1)
  1187 
  1187 
  1188 lemma unat_1 [simp]: "unat (1::'a::len word) = 1"
  1188 lemma unat_1 [simp]: "unat (1::'a::len word) = 1"
  1189   unfolding unat_def by simp
  1189   unfolding unat_def by simp
  1190 
  1190 
  1191 lemma ucast_1 [simp]: "ucast (1::'a::len word) = 1"
  1191 lemma ucast_1 [simp]: "ucast (1::'a::len word) = 1"
  1192   unfolding ucast_def by (simp add: word_of_int_1)
  1192   unfolding ucast_def by simp
  1193 
  1193 
  1194 (* now, to get the weaker results analogous to word_div/mod_def *)
  1194 (* now, to get the weaker results analogous to word_div/mod_def *)
  1195 
  1195 
  1196 lemmas word_arith_alts = 
  1196 lemmas word_arith_alts = 
  1197   word_sub_wi [unfolded succ_def pred_def]
  1197   word_sub_wi [unfolded succ_def pred_def]
  1210   word_succ_pred: "word_succ (word_pred a) = a" and
  1210   word_succ_pred: "word_succ (word_pred a) = a" and
  1211   word_mult_succ: "word_succ a * b = b + a * b"
  1211   word_mult_succ: "word_succ a * b = b + a * b"
  1212   by (rule word_uint.Abs_cases [of b],
  1212   by (rule word_uint.Abs_cases [of b],
  1213       rule word_uint.Abs_cases [of a],
  1213       rule word_uint.Abs_cases [of a],
  1214       simp add: pred_def succ_def add_commute mult_commute 
  1214       simp add: pred_def succ_def add_commute mult_commute 
  1215                 ring_distribs new_word_of_int_homs)+
  1215                 ring_distribs new_word_of_int_homs
       
  1216            del: word_of_int_0 word_of_int_1)+
  1216 
  1217 
  1217 lemma uint_cong: "x = y \<Longrightarrow> uint x = uint y"
  1218 lemma uint_cong: "x = y \<Longrightarrow> uint x = uint y"
  1218   by simp
  1219   by simp
  1219 
  1220 
  1220 lemmas uint_word_ariths = 
  1221 lemmas uint_word_ariths = 
  1785 lemma Abs_fnat_hom_Suc:
  1786 lemma Abs_fnat_hom_Suc:
  1786   "word_succ (of_nat a) = of_nat (Suc a)"
  1787   "word_succ (of_nat a) = of_nat (Suc a)"
  1787   by (simp add: word_of_nat word_of_int_succ_hom add_ac)
  1788   by (simp add: word_of_nat word_of_int_succ_hom add_ac)
  1788 
  1789 
  1789 lemma Abs_fnat_hom_0: "(0::'a::len word) = of_nat 0"
  1790 lemma Abs_fnat_hom_0: "(0::'a::len word) = of_nat 0"
  1790   by (simp add: word_of_nat word_0_wi)
  1791   by simp
  1791 
  1792 
  1792 lemma Abs_fnat_hom_1: "(1::'a::len word) = of_nat (Suc 0)"
  1793 lemma Abs_fnat_hom_1: "(1::'a::len word) = of_nat (Suc 0)"
  1793   by (simp add: word_of_nat word_1_wi)
  1794   by simp
  1794 
  1795 
  1795 lemmas Abs_fnat_homs = 
  1796 lemmas Abs_fnat_homs = 
  1796   Abs_fnat_hom_add Abs_fnat_hom_mult Abs_fnat_hom_Suc 
  1797   Abs_fnat_hom_add Abs_fnat_hom_mult Abs_fnat_hom_Suc 
  1797   Abs_fnat_hom_0 Abs_fnat_hom_1
  1798   Abs_fnat_hom_0 Abs_fnat_hom_1
  1798 
  1799 
  1800   "a + b = of_nat (unat a + unat b)" 
  1801   "a + b = of_nat (unat a + unat b)" 
  1801   by simp
  1802   by simp
  1802 
  1803 
  1803 lemma word_arith_nat_mult:
  1804 lemma word_arith_nat_mult:
  1804   "a * b = of_nat (unat a * unat b)"
  1805   "a * b = of_nat (unat a * unat b)"
  1805   by (simp add: Abs_fnat_hom_mult [symmetric])
  1806   by (simp add: of_nat_mult)
  1806     
  1807     
  1807 lemma word_arith_nat_Suc:
  1808 lemma word_arith_nat_Suc:
  1808   "word_succ a = of_nat (Suc (unat a))"
  1809   "word_succ a = of_nat (Suc (unat a))"
  1809   by (subst Abs_fnat_hom_Suc [symmetric]) simp
  1810   by (subst Abs_fnat_hom_Suc [symmetric]) simp
  1810 
  1811 
  2065   apply (clarsimp simp add : uno_simps)
  2066   apply (clarsimp simp add : uno_simps)
  2066   done
  2067   done
  2067 
  2068 
  2068 lemma word_of_int_power_hom: 
  2069 lemma word_of_int_power_hom: 
  2069   "word_of_int a ^ n = (word_of_int (a ^ n) :: 'a :: len word)"
  2070   "word_of_int a ^ n = (word_of_int (a ^ n) :: 'a :: len word)"
  2070   by (induct n) (simp_all add: word_of_int_hom_syms)
  2071   by (induct n) (simp_all add: wi_hom_mult [symmetric])
  2071 
  2072 
  2072 lemma word_arith_power_alt: 
  2073 lemma word_arith_power_alt: 
  2073   "a ^ n = (word_of_int (uint a ^ n) :: 'a :: len word)"
  2074   "a ^ n = (word_of_int (uint a ^ n) :: 'a :: len word)"
  2074   by (simp add : word_of_int_power_hom [symmetric])
  2075   by (simp add : word_of_int_power_hom [symmetric])
  2075 
  2076 
  2594   by (simp only: word_number_of_def shiftl1_def)
  2595   by (simp only: word_number_of_def shiftl1_def)
  2595 
  2596 
  2596 lemma shiftl1_def_s: "shiftl1 w = number_of (sint w BIT 0)"
  2597 lemma shiftl1_def_s: "shiftl1 w = number_of (sint w BIT 0)"
  2597   by (rule trans [OF _ shiftl1_number]) simp
  2598   by (rule trans [OF _ shiftl1_number]) simp
  2598 
  2599 
  2599 lemma shiftr1_0 [simp] : "shiftr1 0 = 0"
  2600 lemma shiftr1_0 [simp]: "shiftr1 0 = 0"
  2600   unfolding shiftr1_def 
  2601   unfolding shiftr1_def by simp
  2601   by simp (simp add: word_0_wi)
  2602 
  2602 
  2603 lemma sshiftr1_0 [simp]: "sshiftr1 0 = 0"
  2603 lemma sshiftr1_0 [simp] : "sshiftr1 0 = 0"
  2604   unfolding sshiftr1_def by simp
  2604   apply (unfold sshiftr1_def)
       
  2605   apply simp
       
  2606   apply (simp add : word_0_wi)
       
  2607   done
       
  2608 
  2605 
  2609 lemma sshiftr1_n1 [simp] : "sshiftr1 -1 = -1"
  2606 lemma sshiftr1_n1 [simp] : "sshiftr1 -1 = -1"
  2610   unfolding sshiftr1_def by auto
  2607   unfolding sshiftr1_def by auto
  2611 
  2608 
  2612 lemma shiftl_0 [simp] : "(0::'a::len0 word) << n = 0"
  2609 lemma shiftl_0 [simp] : "(0::'a::len0 word) << n = 0"
  3100   apply (fast intro!: lt2p_lem)
  3097   apply (fast intro!: lt2p_lem)
  3101   done
  3098   done
  3102 
  3099 
  3103 lemma and_mask_dvd: "2 ^ n dvd uint w = (w AND mask n = 0)"
  3100 lemma and_mask_dvd: "2 ^ n dvd uint w = (w AND mask n = 0)"
  3104   apply (simp add: dvd_eq_mod_eq_0 and_mask_mod_2p)
  3101   apply (simp add: dvd_eq_mod_eq_0 and_mask_mod_2p)
  3105   apply (simp add: word_uint.norm_eq_iff [symmetric] word_of_int_homs)
  3102   apply (simp add: word_uint.norm_eq_iff [symmetric] word_of_int_homs
       
  3103     del: word_of_int_0)
  3106   apply (subst word_uint.norm_Rep [symmetric])
  3104   apply (subst word_uint.norm_Rep [symmetric])
  3107   apply (simp only: bintrunc_bintrunc_min bintrunc_mod2p [symmetric] min_def)
  3105   apply (simp only: bintrunc_bintrunc_min bintrunc_mod2p [symmetric] min_def)
  3108   apply auto
  3106   apply auto
  3109   done
  3107   done
  3110 
  3108 
  4277   "uint x < 0 = False"
  4275   "uint x < 0 = False"
  4278   by (simp add: linorder_not_less)
  4276   by (simp add: linorder_not_less)
  4279 
  4277 
  4280 lemma shiftr1_1 [simp]: 
  4278 lemma shiftr1_1 [simp]: 
  4281   "shiftr1 (1::'a::len word) = 0"
  4279   "shiftr1 (1::'a::len word) = 0"
  4282   by (simp add: shiftr1_def word_0_wi)
  4280   unfolding shiftr1_def by simp
  4283 
  4281 
  4284 lemma shiftr_1[simp]: 
  4282 lemma shiftr_1[simp]: 
  4285   "(1::'a::len word) >> n = (if n = 0 then 1 else 0)"
  4283   "(1::'a::len word) >> n = (if n = 0 then 1 else 0)"
  4286   by (induct n) (auto simp: shiftr_def)
  4284   by (induct n) (auto simp: shiftr_def)
  4287 
  4285