1 | include "ASM/AssemblyProofSplit.ma". |
---|
2 | include "common/LabelledObjects.ma". |
---|
3 | |
---|
4 | lemma short_jump_cond_ok: |
---|
5 | ∀v1, v2: Word. |
---|
6 | ∀is_possible, offset. |
---|
7 | 〈is_possible, offset〉 = short_jump_cond v1 v2 → |
---|
8 | is_possible → v2 = add 16 v1 (sign_extension offset). |
---|
9 | #v1 #v2 #is_possible #offset |
---|
10 | whd in match short_jump_cond; normalize nodelta |
---|
11 | @pair_elim #result #flags #sub16_refl |
---|
12 | @pair_elim #upper #lower #vsplit_refl |
---|
13 | inversion (get_index' bool ???) #get_index_refl normalize nodelta |
---|
14 | #relevant destruct(relevant) #relevant |
---|
15 | [1: |
---|
16 | @(sub_16_to_add_16_8_1 … flags) |
---|
17 | |2: |
---|
18 | @(sub_16_to_add_16_8_0 … flags) |
---|
19 | ] |
---|
20 | try assumption >sub16_refl |
---|
21 | <(eq_bv_eq … relevant) |
---|
22 | >(vsplit_ok … (sym_eq … vsplit_refl)) % |
---|
23 | qed. |
---|
24 | |
---|
25 | lemma absolute_jump_cond_ok: |
---|
26 | ∀v1, v2: Word. |
---|
27 | ∀is_possible, offset, v1_upper, v1_lower. |
---|
28 | 〈is_possible, offset〉 = absolute_jump_cond v1 v2 → |
---|
29 | 〈v1_upper, v1_lower〉 = vsplit ? 5 11 v1 → |
---|
30 | is_possible → v2 = v1_upper @@ offset. |
---|
31 | #v1 #v2 #is_possible #offset #v1_upper #v1_lower |
---|
32 | whd in match absolute_jump_cond; normalize nodelta |
---|
33 | @pair_elim #fst_5_addr #rest_addr #vsplit_v2_refl |
---|
34 | @pair_elim #fst_5_pc #rest_pc #vsplit_v1_refl |
---|
35 | #relevant destruct(relevant) normalize nodelta #relevant |
---|
36 | destruct(relevant) #relevant |
---|
37 | <(vsplit_ok … (sym_eq … vsplit_v2_refl)) |
---|
38 | >(eq_bv_eq … relevant) % |
---|
39 | qed. |
---|
40 | |
---|
41 | lemma ticks_of_instruction_AJMP: |
---|
42 | ∀address. ticks_of_instruction (AJMP (ADDR11 address)) = 2. |
---|
43 | try % #addr @(vsplit_elim … 3 8 addr) #vl #vm #EQ >EQ |
---|
44 | @(bitvector_3_elim_prop … vl) % |
---|
45 | qed. |
---|
46 | |
---|
47 | lemma ticks_of_instruction_ACALL: |
---|
48 | ∀address. ticks_of_instruction (ACALL (ADDR11 address)) = 2. |
---|
49 | try % #addr @(vsplit_elim … 3 8 addr) #vl #vm #EQ >EQ |
---|
50 | @(bitvector_3_elim_prop … vl) % |
---|
51 | qed. |
---|
52 | |
---|
53 | theorem main_thm: |
---|
54 | ∀M, M': internal_pseudo_address_map. |
---|
55 | ∀program: pseudo_assembly_program. |
---|
56 | ∀program_in_bounds: |\snd program| ≤ 2^16. |
---|
57 | let 〈labels, costs〉 ≝ create_label_cost_map (\snd program) in |
---|
58 | let addr_of ≝ λid.λ_.bitvector_of_nat 16 (lookup_def ASMTag ℕ labels id O) in |
---|
59 | ∀is_well_labelled: is_well_labelled_p (\snd program). |
---|
60 | ∀sigma: Word → Word. |
---|
61 | ∀policy: Word → bool. |
---|
62 | ∀sigma_policy_specification_witness: sigma_policy_specification program sigma policy. |
---|
63 | ∀ps: PseudoStatus program. |
---|
64 | ∀program_counter_in_bounds: nat_of_bitvector 16 (program_counter … ps) < |\snd program|. |
---|
65 | next_internal_pseudo_address_map M program addr_of ps program_counter_in_bounds = Some … M' → |
---|
66 | ∃n. execute n … (status_of_pseudo_status M … ps sigma policy) = |
---|
67 | status_of_pseudo_status M' … |
---|
68 | (execute_1_pseudo_instruction program (ticks_of program (λid. addr_of id ps) sigma policy) ps program_counter_in_bounds) sigma policy. |
---|
69 | #M #M' * #preamble #instr_list #program_in_bounds |
---|
70 | @pair_elim #labels #cost #create_label_cost_refl |
---|
71 | #is_well_labelled_witness #sigma #policy #sigma_policy_witness #ps |
---|
72 | letin ppc ≝ (program_counter pseudo_assembly_program ? ps) #ppc_in_bounds |
---|
73 | change with (next_internal_pseudo_address_map0 ?????? = ? → ?) |
---|
74 | generalize in match (fetch_assembly_pseudo2 〈preamble,instr_list〉 program_in_bounds sigma policy sigma_policy_witness ppc ppc_in_bounds) in ⊢ ?; |
---|
75 | >create_label_cost_refl normalize nodelta |
---|
76 | @pair_elim #assembled #costs' #assembly_refl normalize nodelta |
---|
77 | lapply (pair_destruct_1 ????? (sym_eq ??? assembly_refl)) #EQassembled |
---|
78 | @pair_elim #pi #newppc #fetch_pseudo_refl normalize nodelta |
---|
79 | @(pose … (λx. bitvector_of_nat ? (lookup_def … labels x 0))) #lookup_labels #EQlookup_labels |
---|
80 | @(pose … (λx. lookup_def … (construct_datalabels preamble) x (zero 16))) #lookup_datalabels #EQlookup_datalabels |
---|
81 | whd in match execute_1_pseudo_instruction; normalize nodelta |
---|
82 | whd in match ticks_of; normalize nodelta >fetch_pseudo_refl normalize nodelta |
---|
83 | lapply (snd_fetch_pseudo_instruction instr_list ppc ppc_in_bounds) >fetch_pseudo_refl #EQnewppc >EQnewppc |
---|
84 | lapply (snd_assembly_1_pseudoinstruction_ok 〈preamble,instr_list〉 … sigma policy sigma_policy_witness … ppc … pi … lookup_labels lookup_datalabels) |
---|
85 | [1: assumption |2: assumption] >create_label_cost_refl |
---|
86 | #X lapply (X EQlookup_labels EQlookup_datalabels ?) -X |
---|
87 | [1: >fetch_pseudo_refl %] |
---|
88 | #assm1 #assm2 #assm3 generalize in match assm2; generalize in match assm3; |
---|
89 | generalize in match assm1; -assm1 -assm2 -assm3 |
---|
90 | normalize nodelta |
---|
91 | inversion pi |
---|
92 | [2,3: |
---|
93 | #arg #_ |
---|
94 | (* XXX: we first work on sigma_increment_commutation *) |
---|
95 | #sigma_increment_commutation |
---|
96 | normalize in match (assembly_1_pseudoinstruction ??????) in sigma_increment_commutation; |
---|
97 | (* XXX: we work on the maps *) |
---|
98 | whd in ⊢ (??%? → ?); @Some_Some_elim #map_refl_assm <map_refl_assm |
---|
99 | (* XXX: we assume the fetch_many hypothesis *) |
---|
100 | #fetch_many_assm |
---|
101 | (* XXX: we give the existential *) |
---|
102 | %{0} |
---|
103 | whd in match execute_1_pseudo_instruction0; normalize nodelta |
---|
104 | change with (status_of_pseudo_status ????? = ?) |
---|
105 | whd in ⊢ (??%%); @split_eq_status try % |
---|
106 | [ >set_clock_set_program_counter ] |
---|
107 | >program_counter_set_program_counter >sigma_increment_commutation @add_zero |
---|
108 | |6: (* Mov *) |
---|
109 | #arg1 #arg2 #_ |
---|
110 | (* XXX: we first work on sigma_increment_commutation *) |
---|
111 | #sigma_increment_commutation |
---|
112 | normalize in match (assembly_1_pseudoinstruction ??????) in sigma_increment_commutation; |
---|
113 | (* XXX: we work on the maps *) |
---|
114 | whd in ⊢ (??%? → ?); @Some_Some_elim #map_refl_assm <map_refl_assm |
---|
115 | (* XXX: we assume the fetch_many hypothesis *) |
---|
116 | #fetch_many_assm |
---|
117 | (* XXX: we give the existential *) |
---|
118 | %{1} |
---|
119 | whd in match (execute_1_pseudo_instruction0 ?????); |
---|
120 | (* XXX: work on the left hand side of the equality *) |
---|
121 | whd in ⊢ (??%?); whd in match (program_counter ???); |
---|
122 | (* XXX: execute fetches some more *) |
---|
123 | whd in match code_memory_of_pseudo_assembly_program; normalize nodelta |
---|
124 | whd in fetch_many_assm; |
---|
125 | >EQassembled in fetch_many_assm; |
---|
126 | cases (fetch ??) * #instr #newpc #ticks normalize nodelta * |
---|
127 | #eq_instr |
---|
128 | #fetch_many_assm whd in fetch_many_assm; |
---|
129 | lapply (eq_bv_eq … fetch_many_assm) -fetch_many_assm #EQnewpc |
---|
130 | destruct |
---|
131 | (* XXX: now we start to work on the mk_PreStatus equality *) |
---|
132 | (* XXX: lhs *) |
---|
133 | change with (set_arg_16 ????? = ?) |
---|
134 | @set_arg_16_status_of_pseudo_status |
---|
135 | [3: @(subaddressing_mode_elim … arg1) % |
---|
136 | |2: % |
---|
137 | | @sym_eq @set_clock_status_of_pseudo_status |
---|
138 | [ @sym_eq @set_program_counter_status_of_pseudo_status [<EQnewpc % | %] |
---|
139 | | % ]] |
---|
140 | |1: (* Instruction *) |
---|
141 | #instr #pi_refl |
---|
142 | change with (execute_1_preinstruction ???????) in match (execute_1_pseudo_instruction0 ?????); |
---|
143 | >EQassembled whd in match address_of_word_labels; normalize nodelta |
---|
144 | >create_label_cost_refl in ⊢ (? → ? → ? → %); |
---|
145 | @(main_lemma_preinstruction M M' preamble instr_list 〈preamble, instr_list〉 (refl …) ? sigma policy sigma_policy_witness |
---|
146 | ps ppc ? ? labels cost create_label_cost_refl newppc lookup_labels EQlookup_labels lookup_datalabels EQlookup_datalabels |
---|
147 | EQnewppc instr ? ? (refl …) ? (refl …) |
---|
148 | (set_program_counter pseudo_assembly_program 〈preamble, instr_list〉 ps (add 16 ppc (bitvector_of_nat 16 1))) |
---|
149 | (refl …) ? (refl …)) |
---|
150 | try % try assumption >fetch_pseudo_refl assumption |
---|
151 | |4: (* Jmp *) |
---|
152 | #arg1 #pi_refl |
---|
153 | (* XXX: we first work on sigma_increment_commutation *) |
---|
154 | whd in match (assembly_1_pseudoinstruction ??????) in ⊢ (% → ?); |
---|
155 | whd in match (expand_pseudo_instruction ??????); |
---|
156 | whd in match (ticks_of0 ??????); |
---|
157 | inversion (short_jump_cond ??) #sj_possible #offset #sjc_refl normalize nodelta |
---|
158 | inversion (sj_possible ∧ ¬ policy ?) #sj_possible_refl normalize nodelta |
---|
159 | [2: |
---|
160 | inversion (absolute_jump_cond ??) #mj_possible #address #mjc_refl normalize nodelta |
---|
161 | inversion (mj_possible ∧ ¬ policy ?) #mj_possible_refl normalize nodelta |
---|
162 | ] |
---|
163 | #sigma_increment_commutation |
---|
164 | normalize in sigma_increment_commutation:(???(???(??%))); |
---|
165 | (* XXX: we work on the maps *) |
---|
166 | whd in ⊢ (??%? → ?); @Some_Some_elim #map_refl_assm <map_refl_assm |
---|
167 | (* XXX: we assume the fetch_many hypothesis *) |
---|
168 | * #fetch_refl #fetch_many_assm |
---|
169 | (* XXX: we give the existential *) |
---|
170 | %{1} |
---|
171 | (* XXX: work on the left hand side of the equality *) |
---|
172 | whd in ⊢ (??%?); whd in match (program_counter ???); |
---|
173 | (* XXX: execute fetches some more *) |
---|
174 | whd in match code_memory_of_pseudo_assembly_program; normalize nodelta |
---|
175 | whd in fetch_many_assm; |
---|
176 | >EQassembled in fetch_refl; #fetch_refl <fetch_refl |
---|
177 | lapply (eq_bv_eq … fetch_many_assm) -fetch_many_assm #EQnewpc |
---|
178 | change with (set_program_counter ???? = |
---|
179 | status_of_pseudo_status ?? (set_program_counter ????) ??) |
---|
180 | @set_program_counter_status_of_pseudo_status |
---|
181 | [2,4,6: @sym_eq @set_clock_status_of_pseudo_status try % |
---|
182 | [1,3,4: @sym_eq @set_program_counter_status_of_pseudo_status try % |
---|
183 | @sigma_increment_commutation |
---|
184 | | @eq_f2 try % @ticks_of_instruction_AJMP ]] |
---|
185 | whd in ⊢ (??%%); normalize nodelta whd in match address_of_word_labels; |
---|
186 | normalize nodelta |
---|
187 | [ inversion (vsplit bool ???) #pc_bu #pc_bl #vsplit_refl normalize nodelta |
---|
188 | >EQlookup_labels in mjc_refl; >create_label_cost_refl #mjc_refl |
---|
189 | @(absolute_jump_cond_ok ????? pc_bl (sym_eq … mjc_refl)) |
---|
190 | [2: >(andb_true_l … mj_possible_refl) % |
---|
191 | | <vsplit_refl @eq_f <EQnewpc % ] |
---|
192 | | >EQlookup_labels >create_label_cost_refl % |
---|
193 | | inversion (half_add ???) #carry #new_pc #half_add_refl normalize nodelta |
---|
194 | >create_label_cost_refl |
---|
195 | >EQlookup_labels in sjc_refl; #sjc_refl |
---|
196 | >(pair_destruct_2 ????? (sym_eq … half_add_refl)) |
---|
197 | >(short_jump_cond_ok ???? (sym_eq … sjc_refl)) |
---|
198 | [2: >(andb_true_l … sj_possible_refl) % |
---|
199 | | >EQnewpc % ]] |
---|
200 | |5: (* Call *) |
---|
201 | #arg1 #pi_refl |
---|
202 | (* XXX: we first work on sigma_increment_commutation *) |
---|
203 | whd in match (assembly_1_pseudoinstruction ??????) in ⊢ (% → ?); |
---|
204 | whd in match (expand_pseudo_instruction ??????); |
---|
205 | whd in match (execute_1_pseudo_instruction0 ?????); |
---|
206 | whd in match (ticks_of0 ??????); |
---|
207 | inversion (absolute_jump_cond ??) #aj_possible #offset #ajc_refl normalize nodelta |
---|
208 | inversion (aj_possible ∧ ¬ policy ?) #aj_possible_refl normalize nodelta |
---|
209 | @pair_elim #carry #new_sp #carry_new_sp_refl lapply (refl_to_jmrefl ??? carry_new_sp_refl) -carry_new_sp_refl #carry_new_sp_refl |
---|
210 | @pair_elim #pc_bu #pc_bl #pc_bu_bl_refl lapply (refl_to_jmrefl ??? pc_bu_bl_refl) -pc_bu_bl_refl #pc_bu_bl_refl |
---|
211 | @pair_elim #carry' #new_sp' #carry_new_sp_refl' lapply (refl_to_jmrefl ??? carry_new_sp_refl') -carry_new_sp_refl' #carry_new_sp_refl' |
---|
212 | #sigma_increment_commutation |
---|
213 | normalize in sigma_increment_commutation:(???(???(??%))); |
---|
214 | (* XXX: we work on the maps *) |
---|
215 | whd in ⊢ (??%? → ?); |
---|
216 | @pair_elim #callM #accM #Mrefl |
---|
217 | @Some_Some_elim #map_refl_assm <map_refl_assm |
---|
218 | (* XXX: we assume the fetch_many hypothesis *) |
---|
219 | * #fetch_refl #fetch_many_assm |
---|
220 | (* XXX: we give the existential *) |
---|
221 | %{1} |
---|
222 | (* XXX: work on the left hand side of the equality *) |
---|
223 | whd in ⊢ (??%?); whd in match (program_counter ???); |
---|
224 | (* XXX: execute fetches some more *) |
---|
225 | whd in match code_memory_of_pseudo_assembly_program; normalize nodelta |
---|
226 | whd in fetch_many_assm; |
---|
227 | >EQassembled in fetch_refl; #fetch_refl <fetch_refl |
---|
228 | lapply (eq_bv_eq … fetch_many_assm) -fetch_many_assm #EQnewpc |
---|
229 | whd in ⊢ (??%?); |
---|
230 | [1: |
---|
231 | @(pair_replace ????? carry new_sp ??? carry_new_sp_refl) |
---|
232 | [ @eq_f2 try % @sym_eq |
---|
233 | @(pose … (set_clock ????)) #status #status_refl @sym_eq >status_refl |
---|
234 | /demod nohyps/ |
---|
235 | (*CSC: mess with get_8051_sfr_set_program_counter + missing high level lemmas*) |
---|
236 | cut (∀A,B:Type[0]. ∀f,g:A → B. ∀a:A. f=g → f a = g a) [#A #B #f #f #a * %] #eq_fun |
---|
237 | >(eq_fun ???? ? (get_8051_sfr_set_program_counter (BitVectorTrie Byte 16) … SFR_SP …)) |
---|
238 | >(eq_fun ???? ? (get_8051_sfr_set_program_counter pseudo_assembly_program … SFR_SP …)) |
---|
239 | whd in match get_8051_sfr; normalize nodelta whd in match status_of_pseudo_status; |
---|
240 | normalize nodelta whd in match sfr_8051_of_pseudo_sfr_8051; normalize nodelta |
---|
241 | cases accM try % normalize nodelta #ul #addr cases (vsplit bool ???) |
---|
242 | normalize nodelta #v1 #v2 cases (eq_upper_lower ul upper) normalize nodelta |
---|
243 | >get_index_v_set_index_miss try % #abs normalize in abs; destruct(abs) |
---|
244 | ] whd in ⊢ (??%?); |
---|
245 | @pair_elim #pc_bu' #pc_bl' #pc_bu_bl_refl' |
---|
246 | @(pair_replace ????? ?? ??? carry_new_sp_refl') |
---|
247 | [ @eq_f2 try % @sym_eq |
---|
248 | @(pose … (write_at_stack_pointer ????)) #status #status_refl @sym_eq |
---|
249 | @(get_8051_sfr_status_of_pseudo_status … 〈callM,accM〉 … status) >status_refl -status_refl try % |
---|
250 | @sym_eq cases daemon (*CSC: write_at_stack_pointer_status_of_pseudo_status*) |
---|
251 | ] |
---|
252 | whd in ⊢ (??%?); |
---|
253 | @pair_elim #fiv #thr' #fiv_thr_refl' |
---|
254 | change with (set_program_counter ???? = ?) |
---|
255 | @set_program_counter_status_of_pseudo_status |
---|
256 | [2: @sym_eq cases daemon (*CSC: missing @write_at_stack_pointer_status_of_pseudo_status try % |
---|
257 | [1,3,4: @sym_eq @set_program_counter_status_of_pseudo_status try % |
---|
258 | @sigma_increment_commutation |
---|
259 | | @eq_f2 try % @ticks_of_instruction_AJMP ]*)] |
---|
260 | whd in ajc_refl:(??%?); lapply ajc_refl -ajc_refl -map_refl_assm -Mrefl |
---|
261 | >EQlookup_labels normalize nodelta |
---|
262 | @vsplit_elim #fst_5_addr #rest_addr #fst_5_rest_refl |
---|
263 | >fst_5_rest_refl normalize nodelta |
---|
264 | @vsplit_elim #fst_5_pc #rest_pc #fst_5_rest_pc_refl normalize nodelta |
---|
265 | #pair_true_refl destruct(pair_true_refl) |
---|
266 | <EQnewpc in fst_5_rest_pc_refl; |
---|
267 | lapply pc_bu_bl_refl' -pc_bu_bl_refl' |
---|
268 | >program_counter_set_8051_sfr >set_clock_set_program_counter |
---|
269 | >program_counter_set_program_counter #relevant2 |
---|
270 | <(vsplit_ok ?????? (sym_eq … relevant2)) |
---|
271 | <(vsplit_ok ?????? (sym_eq … fiv_thr_refl')) |
---|
272 | >(vector_associative_append bool 5 3 8) #relevant3 |
---|
273 | >(? : fiv = fst_5_addr) |
---|
274 | [1: <fst_5_rest_refl whd in match address_of_word_labels; normalize nodelta |
---|
275 | >create_label_cost_refl % |
---|
276 | |2: cases (bv_append_eq_to_eq … relevant3) #H #_ >H |
---|
277 | cases (conjunction_true … aj_possible_refl) #K #_ @sym_eq |
---|
278 | @eq_bv_eq assumption ] |
---|
279 | | @(pair_replace ????? carry new_sp ??? carry_new_sp_refl) |
---|
280 | [ @eq_f2 try % |
---|
281 | @sym_eq @(pose … (set_clock ????)) #status #status_refl @sym_eq |
---|
282 | @(get_8051_sfr_status_of_pseudo_status … 〈callM,accM〉 … status) |
---|
283 | >status_refl -status_refl try % |
---|
284 | @sym_eq @set_clock_status_of_pseudo_status try % |
---|
285 | @sym_eq @set_program_counter_status_of_pseudo_status try % assumption ] |
---|
286 | @pair_elim #pc_bu' #pc_bl' #pc_bu_bl_refl' |
---|
287 | @(pair_replace ????? carry' new_sp' ??? carry_new_sp_refl') |
---|
288 | [ @eq_f2 try % @sym_eq |
---|
289 | @(pose … (write_at_stack_pointer ????)) #status #status_refl @sym_eq |
---|
290 | @(get_8051_sfr_status_of_pseudo_status … 〈callM,accM〉 … status) >status_refl -status_refl try % |
---|
291 | @sym_eq cases daemon (*CSC: write_at_stack_pointer_status_of_pseudo_status*) ] |
---|
292 | change with (set_program_counter ???? = ?) |
---|
293 | @set_program_counter_status_of_pseudo_status |
---|
294 | [ >EQlookup_labels whd in match address_of_word_labels; normalize nodelta |
---|
295 | >create_label_cost_refl % ] |
---|
296 | cut(pc_bu' @@ pc_bl' = sigma (pc_bu @@ pc_bl)) |
---|
297 | [1: |
---|
298 | >(vsplit_ok ?????? (sym_eq … pc_bu_bl_refl')) |
---|
299 | >(vsplit_ok ?????? (sym_eq … pc_bu_bl_refl)) |
---|
300 | >add_commutative |
---|
301 | >program_counter_set_8051_sfr >set_clock_set_program_counter |
---|
302 | >program_counter_set_program_counter >add_commutative |
---|
303 | >program_counter_set_8051_sfr >set_clock_set_program_counter |
---|
304 | >program_counter_set_program_counter assumption ] #sigma_pc_bu_pc_bl_refl |
---|
305 | @sym_eq (*CSC: write_at_stack_pointer_status_of_pseudo_status*) |
---|
306 | cases daemon |
---|
307 | ] |
---|
308 | ] |
---|
309 | qed. |
---|