author | huffman |
Tue, 10 Jan 2012 14:48:42 +0100 | |
changeset 46172 | c06e868dc339 |
parent 46064 | 88ef116e0522 |
child 46173 | 5cc700033194 |
permissions | -rw-r--r-- |
24441 | 1 |
(* |
2 |
Author: Gerwin Klein, NICTA |
|
3 |
||
4 |
Examples demonstrating and testing various word operations. |
|
5 |
*) |
|
6 |
||
25262
d0928156e326
Added reference to Jeremy Dawson's paper on the word library.
kleing
parents:
24465
diff
changeset
|
7 |
header "Examples of word operations" |
d0928156e326
Added reference to Jeremy Dawson's paper on the word library.
kleing
parents:
24465
diff
changeset
|
8 |
|
29629 | 9 |
theory WordExamples |
44762 | 10 |
imports "../Word" |
24441 | 11 |
begin |
12 |
||
42463 | 13 |
type_synonym word32 = "32 word" |
14 |
type_synonym word8 = "8 word" |
|
15 |
type_synonym byte = word8 |
|
29640 | 16 |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
17 |
text "modulus" |
24441 | 18 |
|
19 |
lemma "(27 :: 4 word) = -5" by simp |
|
20 |
||
21 |
lemma "(27 :: 4 word) = 11" by simp |
|
22 |
||
23 |
lemma "27 \<noteq> (11 :: 6 word)" by simp |
|
24 |
||
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
25 |
text "signed" |
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
26 |
|
24441 | 27 |
lemma "(127 :: 6 word) = -1" by simp |
28 |
||
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
29 |
text "number ring simps" |
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
30 |
|
24441 | 31 |
lemma |
24465 | 32 |
"27 + 11 = (38::'a::len word)" |
24441 | 33 |
"27 + 11 = (6::5 word)" |
24465 | 34 |
"7 * 3 = (21::'a::len word)" |
35 |
"11 - 27 = (-16::'a::len word)" |
|
36 |
"- -11 = (11::'a::len word)" |
|
37 |
"-40 + 1 = (-39::'a::len word)" |
|
24441 | 38 |
by simp_all |
39 |
||
40 |
lemma "word_pred 2 = 1" by simp |
|
41 |
||
42 |
lemma "word_succ -3 = -2" by simp |
|
43 |
||
44 |
lemma "23 < (27::8 word)" by simp |
|
45 |
lemma "23 \<le> (27::8 word)" by simp |
|
46 |
lemma "\<not> 23 < (27::2 word)" by simp |
|
47 |
lemma "0 < (4::3 word)" by simp |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
48 |
lemma "1 < (4::3 word)" by simp |
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
49 |
lemma "0 < (1::3 word)" by simp |
24441 | 50 |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
51 |
text "ring operations" |
24441 | 52 |
|
53 |
lemma "a + 2 * b + c - b = (b + c) + (a :: 32 word)" by simp |
|
54 |
||
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
55 |
text "casting" |
24441 | 56 |
|
57 |
lemma "uint (234567 :: 10 word) = 71" by simp |
|
58 |
lemma "uint (-234567 :: 10 word) = 953" by simp |
|
59 |
lemma "sint (234567 :: 10 word) = 71" by simp |
|
60 |
lemma "sint (-234567 :: 10 word) = -71" by simp |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
61 |
lemma "uint (1 :: 10 word) = 1" by simp |
24441 | 62 |
|
63 |
lemma "unat (-234567 :: 10 word) = 953" by simp |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
64 |
lemma "unat (1 :: 10 word) = 1" by simp |
24441 | 65 |
|
66 |
lemma "ucast (0b1010 :: 4 word) = (0b10 :: 2 word)" by simp |
|
67 |
lemma "ucast (0b1010 :: 4 word) = (0b1010 :: 10 word)" by simp |
|
68 |
lemma "scast (0b1010 :: 4 word) = (0b111010 :: 6 word)" by simp |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
69 |
lemma "ucast (1 :: 4 word) = (1 :: 2 word)" by simp |
24441 | 70 |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
71 |
text "reducing goals to nat or int and arith:" |
24465 | 72 |
lemma "i < x ==> i < (i + 1 :: 'a :: len word)" by unat_arith |
73 |
lemma "i < x ==> i < (i + 1 :: 'a :: len word)" by uint_arith |
|
24441 | 74 |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
75 |
text "bool lists" |
24441 | 76 |
|
24465 | 77 |
lemma "of_bl [True, False, True, True] = (0b1011::'a::len word)" by simp |
24441 | 78 |
|
79 |
lemma "to_bl (0b110::4 word) = [False, True, True, False]" by simp |
|
80 |
||
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
81 |
text "this is not exactly fast, but bearable" |
24441 | 82 |
lemma "of_bl (replicate 32 True) = (0xFFFFFFFF::32 word)" by simp |
83 |
||
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
84 |
text "this works only for replicate n True" |
24441 | 85 |
lemma "of_bl (replicate 32 True) = (0xFFFFFFFF::32 word)" |
86 |
by (unfold mask_bl [symmetric]) (simp add: mask_def) |
|
87 |
||
88 |
||
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
89 |
text "bit operations" |
24441 | 90 |
|
91 |
lemma "0b110 AND 0b101 = (0b100 :: 32 word)" by simp |
|
92 |
lemma "0b110 OR 0b011 = (0b111 :: 8 word)" by simp |
|
93 |
lemma "0xF0 XOR 0xFF = (0x0F :: byte)" by simp |
|
94 |
lemma "NOT (0xF0 :: 16 word) = 0xFF0F" by simp |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
95 |
lemma "0 AND 5 = (0 :: byte)" by simp |
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
96 |
lemma "1 AND 1 = (1 :: byte)" by simp |
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
97 |
lemma "1 AND 0 = (0 :: byte)" by simp |
46064
88ef116e0522
add simp rules for bitwise word operations with 1
huffman
parents:
46015
diff
changeset
|
98 |
lemma "1 AND 5 = (1 :: byte)" by simp |
88ef116e0522
add simp rules for bitwise word operations with 1
huffman
parents:
46015
diff
changeset
|
99 |
lemma "1 OR 6 = (7 :: byte)" by simp |
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
100 |
lemma "1 OR 1 = (1 :: byte)" by simp |
46064
88ef116e0522
add simp rules for bitwise word operations with 1
huffman
parents:
46015
diff
changeset
|
101 |
lemma "1 XOR 7 = (6 :: byte)" by simp |
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
102 |
lemma "1 XOR 1 = (0 :: byte)" by simp |
46064
88ef116e0522
add simp rules for bitwise word operations with 1
huffman
parents:
46015
diff
changeset
|
103 |
lemma "NOT 1 = (254 :: byte)" by simp |
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
104 |
lemma "NOT 0 = (255 :: byte)" apply simp oops |
46064
88ef116e0522
add simp rules for bitwise word operations with 1
huffman
parents:
46015
diff
changeset
|
105 |
(* FIXME: "NOT 0" rewrites to "max_word" instead of "-1" *) |
24441 | 106 |
|
107 |
lemma "(-1 :: 32 word) = 0xFFFFFFFF" by simp |
|
108 |
||
109 |
lemma "(0b0010 :: 4 word) !! 1" by simp |
|
110 |
lemma "\<not> (0b0010 :: 4 word) !! 0" by simp |
|
111 |
lemma "\<not> (0b1000 :: 3 word) !! 4" by simp |
|
46172 | 112 |
lemma "\<not> (1 :: 3 word) !! 2" by simp |
24441 | 113 |
|
114 |
lemma "(0b11000 :: 10 word) !! n = (n = 4 \<or> n = 3)" |
|
26086
3c243098b64a
New simpler representation of numerals, using Bit0 and Bit1 instead of BIT, B0, and B1
huffman
parents:
25262
diff
changeset
|
115 |
by (auto simp add: bin_nth_Bit0 bin_nth_Bit1) |
24441 | 116 |
|
24465 | 117 |
lemma "set_bit 55 7 True = (183::'a::len0 word)" by simp |
118 |
lemma "set_bit 0b0010 7 True = (0b10000010::'a::len0 word)" by simp |
|
119 |
lemma "set_bit 0b0010 1 False = (0::'a::len0 word)" by simp |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
120 |
lemma "set_bit 1 3 True = (0b1001::'a::len0 word)" apply simp? oops |
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
121 |
lemma "set_bit 1 0 False = (0::'a::len0 word)" apply simp? oops |
24441 | 122 |
|
24465 | 123 |
lemma "lsb (0b0101::'a::len word)" by simp |
124 |
lemma "\<not> lsb (0b1000::'a::len word)" by simp |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
125 |
lemma "lsb (1::'a::len word)" by simp |
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
126 |
lemma "\<not> lsb (0::'a::len word)" by simp |
24441 | 127 |
|
128 |
lemma "\<not> msb (0b0101::4 word)" by simp |
|
129 |
lemma "msb (0b1000::4 word)" by simp |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
130 |
lemma "\<not> msb (1::4 word)" apply simp? oops |
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
131 |
lemma "\<not> msb (0::4 word)" apply simp? oops |
24441 | 132 |
|
24465 | 133 |
lemma "word_cat (27::4 word) (27::8 word) = (2843::'a::len word)" by simp |
24441 | 134 |
lemma "word_cat (0b0011::4 word) (0b1111::6word) = (0b0011001111 :: 10 word)" |
135 |
by simp |
|
136 |
||
24465 | 137 |
lemma "0b1011 << 2 = (0b101100::'a::len0 word)" by simp |
24441 | 138 |
lemma "0b1011 >> 2 = (0b10::8 word)" by simp |
139 |
lemma "0b1011 >>> 2 = (0b10::8 word)" by simp |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
140 |
lemma "1 << 2 = (0b100::'a::len0 word)" apply simp? oops |
24441 | 141 |
|
142 |
lemma "slice 3 (0b101111::6 word) = (0b101::3 word)" by simp |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
143 |
lemma "slice 3 (1::6 word) = (0::3 word)" apply simp? oops |
24441 | 144 |
|
145 |
lemma "word_rotr 2 0b0110 = (0b1001::4 word)" by simp |
|
146 |
lemma "word_rotl 1 0b1110 = (0b1101::4 word)" by simp |
|
147 |
lemma "word_roti 2 0b1110 = (0b1011::4 word)" by simp |
|
148 |
lemma "word_roti -2 0b0110 = (0b1001::4 word)" by simp |
|
46015
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
149 |
lemma "word_rotr 2 0 = (0::4 word)" by simp |
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
150 |
lemma "word_rotr 2 1 = (0b0100::4 word)" apply simp? oops |
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
151 |
lemma "word_rotl 2 1 = (0b0100::4 word)" apply simp? oops |
713c1f396e33
add several new tests, most of which don't work yet
huffman
parents:
44762
diff
changeset
|
152 |
lemma "word_roti -2 1 = (0b0100::4 word)" apply simp? oops |
24441 | 153 |
|
154 |
lemma "(x AND 0xff00) OR (x AND 0x00ff) = (x::16 word)" |
|
155 |
proof - |
|
156 |
have "(x AND 0xff00) OR (x AND 0x00ff) = x AND (0xff00 OR 0x00ff)" |
|
157 |
by (simp only: word_ao_dist2) |
|
158 |
also have "0xff00 OR 0x00ff = (-1::16 word)" |
|
159 |
by simp |
|
160 |
also have "x AND -1 = x" |
|
161 |
by simp |
|
162 |
finally show ?thesis . |
|
163 |
qed |
|
164 |
||
165 |
end |