-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathFpuProperties.v
1880 lines (1788 loc) · 74.6 KB
/
FpuProperties.v
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
Require Import Kami.AllNotations FpuKami.Definitions FpuKami.Classify FpuKami.ModClassify.
Section Compat.
Set Implicit Arguments.
End Compat.
Section Properties.
Variable expWidthMinus2 sigWidthMinus2: nat.
Local Notation expWidthMinus1 := (expWidthMinus2 + 1).
Local Notation expWidth := (expWidthMinus1 + 1).
Local Notation sigWidthMinus1 := (sigWidthMinus2 + 1).
Local Notation sigWidth := (sigWidthMinus1 + 1).
Variable expWidth_prop: expWidthMinus2 >= 2.
Variable expWidthMinus2_plus4_gt_sigWidth: 2 ^ expWidthMinus2 + 4 > sigWidth.
Lemma expWidth_ge_sigWidth:
2 ^ expWidthMinus1 > sigWidth.
Proof.
rewrite ?Nat.pow_add_r; simpl.
assert (sth: 2 ^ expWidthMinus2 >= 4). {
pose proof (@Nat.pow_le_mono_r 2 _ _ ltac:(lia) expWidth_prop).
assumption.
}
lia.
Qed.
Section FN.
Variable fn: FN expWidthMinus2 sigWidthMinus2 @# type.
Ltac simplifyEvalExpr :=
cbn [evalExpr map evalCABool evalUniBool evalUniBit fold_left Vector.nth Vector.caseS snd evalConstT
Vector_nth_map2_r Vector_nth_map2_r' Fin.t_rect projT2 evalCABit pack evalBinBit combine isEq projT1 Kind_rect
ZeroExtend countLeadingZeros ConstExtract
nth_Fin nth_Fin_map2 eq_add_S f_equal (* map_length_red hedberg *)
getRecFN_from_FN getRawFloat_from_RecFN getRawFloat_from_FN getRecFN_from_RawFloat
sign infOrNaN isZeroExpIn isZeroFractIn isNaN fracMsb isSNaN
normDist subnormFract adjustedExp isZero isSpecialMsb isSpecialLsb isSpecial
isZeroNaNInf0 isZeroNaNInf1 isZeroNaNInf2 isZeroRecFN isNaN_or_Inf get_exp_from_RecFN
sExp_expWidth sExp_expWidthMinus1 sExp_expWidthMinus2
isFiniteNonzero isSubnormal isSigNaNRawFloat_frac isSigNaNRawFloat
];
repeat rewrite ?andb_true_l, ?andb_true_r, ?andb_false_r, ?andb_false_l.
Ltac simplifyEvalExpr_hyp H :=
cbn [evalExpr map evalCABool evalUniBool evalUniBit fold_left Vector.nth Vector.caseS snd evalConstT
Vector_nth_map2_r Vector_nth_map2_r' Fin.t_rect projT2 evalCABit pack evalBinBit combine isEq projT1 Kind_rect
ZeroExtend countLeadingZeros ConstExtract
nth_Fin nth_Fin_map2 eq_add_S f_equal (* map_length_red hedberg *)
getRecFN_from_FN getRawFloat_from_RecFN getRawFloat_from_FN getRecFN_from_RawFloat
sign infOrNaN isZeroExpIn isZeroFractIn isNaN fracMsb isSNaN
normDist subnormFract adjustedExp isZero isSpecialMsb isSpecialLsb isSpecial
isZeroNaNInf0 isZeroNaNInf1 isZeroNaNInf2 isZeroRecFN isNaN_or_Inf get_exp_from_RecFN
sExp_expWidth sExp_expWidthMinus1 sExp_expWidthMinus2
isFiniteNonzero isSubnormal isSigNaNRawFloat_frac isSigNaNRawFloat
] in H;
repeat rewrite ?andb_true_l, ?andb_true_r, ?andb_false_r, ?andb_false_l in H.
Lemma isSpecial_infOrNaN: evalExpr (isSpecial fn) = evalExpr (infOrNaN fn).
Proof.
pose proof expWidth_ge_sigWidth as expWidth_ge_sigWidth.
simpl.
match goal with
| |- _ = getBool ?P => destruct P; [rewrite e; simpl in *|]
end.
- simpl.
destruct (@weq _ (wones expWidth) (natToWord expWidth 0)); simpl.
+ pose proof (@wzero_wones expWidth ltac:(lia)).
congruence.
+ (* unfold wzero. *)
rewrite wplus_unit.
simpl.
(* a dirty solution, but a solution... *)
assert (ZToWord 0 0 = natToWord 0 0) by auto; rewrite !H; clear H.
assert (ZToWord 1 0 = natToWord 1 0) by auto; rewrite !H; clear H.
(* assert (ZToWord 1 1 = natToWord 1 1) by auto; rewrite !H; clear H. *)
(* assert (ZToWord expWidthMinus1 1 = natToWord _ 1) by auto; rewrite !H; clear H. *)
rewrite combine_wones_WO; [|unfold wzero; intro].
* simpl.
rewrite split1_combine_wplus.
match goal with
| |- getBool (@weq _ (truncMsb (_ ^+ ?P)) _) = true => rewrite <- (natToWord_wordToNat _ P)
end.
rewrite !wordToNat_combine; try lia.
rewrite Nat.pow_0_r, Nat.mul_1_l.
simpl.
rewrite Nat.mul_1_r.
rewrite wordToNat_natToWord_idempotent'.
-- rewrite wones_natToWord.
rewrite <- natToWord_plus.
simpl.
assert (sth: 2 ^ expWidth - 1 + S (2 ^ expWidthMinus1) = 2 ^ expWidth + 2 ^ expWidthMinus1) by (pose proof (one_le_pow2 expWidth); lia).
rewrite sth.
match goal with
| |- getBool (@weq _ ?P _) = true =>
rewrite <- (natToWord_wordToNat _ P)
end.
rewrite wordToNat_split2.
assert (sth2: 2 ^ expWidth + 2 ^ expWidthMinus1 = 2 ^ expWidthMinus1 + 2 ^ expWidth) by lia.
rewrite sth2.
rewrite natToWord_pow2_add.
rewrite wordToNat_natToWord_idempotent'.
** rewrite Nat.div_same; auto.
pose proof (pow2_zero expWidthMinus1).
lia.
** apply (Nat.pow_lt_mono_r 2 expWidthMinus1 expWidth); try lia.
-- assert (sth: expWidthMinus2 + 1 = S expWidthMinus2) by lia.
rewrite sth.
apply one_lt_pow2.
* apply (f_equal (@truncMsb 1 _)) in H.
rewrite split2_combine in *.
rewrite split2_zero in *.
unfold natToWord in H; simpl in *.
discriminate.
- simpl.
cbn [natToWord].
rewrite ?wplus_unit.
match goal with
| |- context [@weq _ ?P (natToWord expWidth 0)] => remember P as f; simpl in f
end.
assert (sth3: @wordToNat _ f <> 2 ^ expWidth - 1). {
intro.
apply (f_equal (natToWord expWidth)) in H.
rewrite natToWord_wordToNat in H.
rewrite <- wones_natToWord in H.
subst.
tauto.
}
assert (sth: @wordToNat _ f < 2 ^ expWidth - 1). {
pose proof (wordToNat_bound f).
lia.
}
clear sth3 Heqf.
destruct (@weq _ f (natToWord expWidth 0)); subst; simpl.
+ unfold normDist.
rewrite ?evalExpr_countLeadingZeros.
simpl.
rewrite andb_false_iff; left.
assert (sth2: 2 ^ expWidthMinus1 > sigWidthMinus1) by lia.
assert (sth2_5: 2 ^ (expWidth + 1) > sigWidthMinus1) by (assert (helper: expWidth + 1 = 2 + expWidthMinus1) by lia; rewrite helper; simpl; lia).
match goal with
| |- context[countLeadingZerosWord _ _ ?P] =>
pose proof (countLeadingZerosWord_le_len _ _ sth2_5 P)
end.
match goal with
| |- getBool (@weq _ ?P _) = false => rewrite <- (natToWord_wordToNat _ P)
end.
rewrite ?wordToNat_split2; simpl.
repeat match goal with
| |- context [wconcat ?P ?Q] => rewrite <- (natToWord_wordToNat _ (wconcat P Q)); rewrite wordToNat_combine; simpl
end.
rewrite ?Nat.mul_1_r, ?Nat.mul_0_r, ?Nat.add_0_r.
rewrite ?wordToNat_natToWord_idempotent'.
* rewrite Nat.div_small; simpl; auto.
(* simpl; rewrite Z.mod_small; try split; try lia; simpl.
2:{ rewrite <- Z.pow_1_r at 1.
apply Z.pow_lt_mono_r; lia. } *)
(* pre_word_omega. *)
match goal with
| |- context [@weq _ ?w1 ?w2] => destruct (@weq _ w1 w2); simpl
end.
** assert (sth3: 2 ^ (expWidth+1) = 2 ^ (expWidthMinus1) + 2 ^ (expWidthMinus1) + 2 ^ expWidth) by (rewrite ?Nat.add_1_r; simpl; lia).
rewrite wplus_comm.
rewrite wneg_wnot.
rewrite wminus_def.
rewrite <- wneg_wplus_distr.
replace (ZToWord (expWidth + 1) 1) with (natToWord (expWidth + 1) 1); auto.
rewrite <- natToWord_plus.
(* assert (sth_tmp : (1 = Z.of_nat 1)%Z) by auto.
rewrite sth_tmp; rewrite <- Nat2Z.inj_add; clear sth_tmp.*)
rewrite <- wminus_def.
rewrite wminus_minus.
(* rewrite Nat2Z_ZToWord.*)
apply lt_minus'.
rewrite ?wordToNat_natToWord_idempotent'; lia.
rewrite wordToNat_natToWord_idempotent'.
rewrite Nat.pow_add_r; simpl; lia.
do 2 rewrite Nat.pow_add_r; simpl. lia.
rewrite wordToNat_natToWord_idempotent'.
assert (sth4: 2 ^ expWidth = 2 ^ (expWidthMinus1) + 2 ^ (expWidthMinus1) ).
rewrite ?Nat.add_1_r; simpl; lia.
rewrite sth4.
lia.
lia.
simpl.
unfold wltu. unfold natToWord.
rewrite !wordToZ_ZToWord; try split; try rewrite <- Zpow_of_nat; try lia.
apply Z.ltb_lt; apply Nat2Z.inj_lt; lia.
** unfold wleu, natToWord in H.
rewrite wordToZ_ZToWord in H by (rewrite <- Zpow_of_nat; lia).
assert (sth3: sigWidthMinus1 < 2 ^ expWidthMinus1 - 1) by lia.
rewrite wordToNat_wplus.
rewrite wordToNat_wnot.
rewrite wordToNat_natToWord_idempotent'.
-- simpl in *.
apply Z.leb_le in H.
apply Z2Nat.inj_le in H; try apply wordVal_pos; try lia.
rewrite Nat2Z.id in H.
unfold wordToNat.
match type of H with
| ?P <= _ => remember P as rem
end.
assert (sth4: 2 ^ (expWidth + 1) > rem). {
assert (helper: expWidth + 1 = 2 + expWidthMinus1) by lia.
rewrite helper.
simpl; lia.
}
pose proof (one_le_pow2 (expWidth + 1)) as sth5.
assert (sth6: rem < 2 ^ expWidthMinus1) by lia.
assert (sth7: 2 ^ (expWidth + 1) - rem - 1 + S (S (2 ^ expWidthMinus1)) = 2 ^ (expWidth + 1) + (S (2 ^ expWidthMinus1) - rem)) by lia.
rewrite sth7.
rewrite Nat.Div0.add_mod by lia.
rewrite Nat.Div0.mod_same by lia; simpl.
destruct rem; simpl; rewrite ?Nat.Div0.mod_mod by lia; rewrite Nat.mod_small;
rewrite ?(Nat.pow_add_r _ expWidthMinus1 1); simpl; try nia.
++ assert (sth8: expWidth + 1 = 2 + expWidthMinus1) by lia; rewrite sth8; simpl; nia.
++ assert (sth8: expWidth + 1 = 2 + expWidthMinus1) by lia; rewrite sth8; simpl; nia.
-- rewrite ?Nat.pow_add_r; simpl.
pose proof (zero_lt_pow2 expWidthMinus2).
lia.
* rewrite <- Nat.pow_1_r at 1.
apply Nat.pow_lt_mono_r; lia.
* unfold wordToNat. simpl.
apply Nat2Z.inj_lt.
rewrite Z2Nat.id.
rewrite Zpow_of_nat.
apply Z_mod_lt.
rewrite <- Zpow_of_nat. lia.
apply Z.mod_pos_bound.
rewrite <- Zpow_of_nat. lia.
* unfold wordToNat. simpl.
rewrite Z2Nat.id by (apply Z.mod_pos_bound; apply Z.pow_pos_nonneg; lia).
rewrite Z.mod_mod by (apply Z.pow_nonzero; lia).
rewrite Z.mod_small.
++ rewrite !pow2_add_mul.
simpl.
assert (sth3: 2 < 2 ^ expWidthMinus2). {
rewrite <- Nat.pow_1_r at 1.
apply Nat.pow_lt_mono_r; lia.
}
lia.
++ split; try lia.
apply Z2Nat.inj_lt; try lia.
rewrite <- Zpow_of_nat, Nat2Z.id.
assert (th: Z.to_nat 2 = 2) by (auto; rewrite th; clear th).
rewrite <- Nat.pow_1_r at 1.
apply Nat.pow_lt_mono_r; lia.
* auto.
* auto.
* auto.
+ rewrite <- (natToWord_wordToNat _ (wconcat (natToWord 1 0) f)).
rewrite <- (natToWord_wordToNat _ (wconcat (ZToWord 1 0)
(wconcat (ZToWord 1 1) (wconcat (ZToWord expWidthMinus1 1) (ZToWord 0 0))))).
rewrite ?wordToNat_combine; auto.
simpl.
rewrite ?Nat.mul_0_r, ?Nat.add_0_r, ?Nat.mul_1_r.
rewrite wordToNat_natToWord_idempotent' with (n := 1) by lia.
rewrite <- natToWord_plus.
match goal with
| |- getBool (@weq _ ?P _) && getBool (@weq _ ?Q _) = false => rewrite <- (natToWord_wordToNat _ P);
rewrite <- (natToWord_wordToNat _ Q)
end.
rewrite ?wordToNat_split2; simpl.
rewrite wordToNat_split1; simpl.
assert (sth1: 2 ^ expWidth >= 1) by lia.
assert (sth2: @wordToNat _ f + S (2 ^ expWidthMinus1) < 2 ^ (expWidth + 1)). {
assert (sth3: S expWidth = expWidth + 1) by lia; rewrite <- sth3; simpl.
assert (sth4: 2 ^ (S expWidthMinus1) = 2 ^ expWidth) by (f_equal; lia).
rewrite <- sth4 in *; simpl.
simpl in *.
lia.
}
rewrite ?wordToNat_natToWord_idempotent' by auto.
rewrite andb_false_iff.
assert (sth3: 2 ^ expWidthMinus1 >= 1) by lia.
assert (sth4: 2 ^ expWidth = 2 ^ (S expWidthMinus1)) by (f_equal; lia).
destruct (Compare_dec.le_lt_dec (2 ^ expWidthMinus1-1) (@wordToNat _ f)); [ right | left ].
* rewrite mod_sub'; simpl; rewrite ?Nat.add_0_r; try nia.
-- rewrite Nat.div_small; simpl; auto.
rewrite sth4 in *; simpl in *.
nia.
-- rewrite sth4; simpl.
nia.
* rewrite Nat.div_small; simpl; auto.
rewrite sth4; simpl.
lia.
Qed.
Lemma isZero_not_isNaN: evalExpr (isZero fn) = true -> evalExpr (isNaN fn) = false.
Proof.
pose proof expWidth_ge_sigWidth as expWidth_ge_sigWidth.
intros.
apply andb_prop in H; dest.
apply andb_false_intro1.
simpl in *.
match goal with
| H: getBool (@weq _ ?P ?Q) = true |- getBool (@weq _ ?P ?R) = false => destruct (@weq _ P Q) as [p|q]; [rewrite p; simpl |]
end.
- destruct (@weq _ (natToWord expWidth 0) (wones expWidth)); auto.
exfalso.
apply wzero_wones in e; auto.
lia.
- simpl in *; discriminate.
Qed.
Lemma isZero_not_infOrNaN: evalExpr (isZero fn) = true -> evalExpr (infOrNaN fn) = false.
Proof.
pose proof expWidth_ge_sigWidth as expWidth_ge_sigWidth.
simpl.
intros.
apply andb_prop in H; dest.
match type of H with
| getBool ?P = true => destruct P; [| discriminate]
end.
rewrite e.
match goal with
| |- getBool ?P = false => destruct P; auto
end.
pose proof (@wzero_wones expWidth ltac:(lia)).
tauto.
Qed.
Lemma infOrNaN_not_isZero: evalExpr (infOrNaN fn) = true -> evalExpr (isZero fn) = false.
Proof.
pose proof isZero_not_infOrNaN.
intros.
destruct (evalExpr (isZero fn)); [|auto].
specialize (H eq_refl).
congruence.
Qed.
Lemma evalExprStructField n fsk exprs idx:
evalExpr (BuildStruct (n := n) fsk exprs) idx =
evalExpr (exprs idx).
Proof.
auto.
Qed.
Definition typeCast k1 k2 (heq: k1 = k2) (v1: type k1) : type k2 :=
match heq in (_ = y) return type y with
| eq_refl => v1
end.
Lemma infOrNaN_sExp_expWidthMinus2':
evalExpr (infOrNaN fn) = true -> getBool (@weq _ (evalExpr (sExp_expWidthMinus2 (getRawFloat_from_FN fn))) WO~0) = true.
Proof.
pose proof expWidth_ge_sigWidth as expWidth_ge_sigWidth.
cbn.
unfold getRawFloat_from_FN, getStructVal.
rewrite evalExprStructField.
cbn.
unfold evalExpr.
cbn [evalExpr].
cbn [evalExpr infOrNaN nth_Fin evalConstT eq_add_S].
unfold eq_add_S.
simpl.
rewrite ?split1_combine.
intros.
match type of H with
| getBool ?P = _ => destruct P
end; simpl in *; [clear H; rewrite e; clear e| discriminate].
destruct (@weq _ (wones expWidth) (natToWord expWidth 0)); simpl; [pose proof (@wzero_wones expWidth ltac:(lia)); congruence| clear n].
rewrite wzero_wplus.
match goal with
| |- getBool (@weq _ (@truncMsb _ _ (@truncLsb _ _ (@truncLsb _ _ ?P))) _) = true =>
rewrite <- (natToWord_wordToNat _ P)
end.
rewrite wordToNat_wplus.
rewrite ?wordToNat_combine.
simpl.
rewrite ?Nat.mul_0_r, ?Nat.add_0_r, ?Nat.mul_1_r.
rewrite wones_pow2_minus_one.
rewrite wordToNat_natToWord_idempotent' by lia.
assert (sth0: expWidth + 1 = S expWidth) by lia.
assert (sth1: expWidth = S expWidthMinus1) by lia.
assert (sth2: 2 ^ expWidth >= 1) by (rewrite sth1; pose proof (one_lt_pow2 expWidthMinus1); lia).
assert (sth3: 2 ^ expWidth - 1 + (1 + 2 ^ expWidthMinus1) = 2 ^ expWidth + 2 ^ expWidthMinus1) by lia.
rewrite sth3.
rewrite Nat.mod_small by (rewrite sth0, sth1; simpl; lia).
match goal with
| |- getBool (@weq _ (@truncMsb _ _ (@truncLsb _ _ ?P)) _) = _ =>
rewrite <- (natToWord_wordToNat _ P)
end.
rewrite wordToNat_split1.
rewrite wordToNat_natToWord_idempotent' by (rewrite sth0, sth1; simpl; lia).
assert (sth4: 2 ^ expWidth + 2 ^ expWidthMinus1 = 2 ^ expWidthMinus1 + 1 * 2 ^ expWidth) by lia.
rewrite sth4.
rewrite Nat.Div0.mod_add by lia.
rewrite Nat.mod_small by (rewrite sth1; simpl; lia).
match goal with
| |- getBool (@weq _ (@truncMsb _ _ ?P) _) = _ =>
rewrite <- (natToWord_wordToNat _ P)
end.
rewrite wordToNat_split1.
rewrite wordToNat_natToWord_idempotent' by (rewrite sth1; simpl; lia).
rewrite Nat.Div0.mod_same by lia.
match goal with
| |- getBool (@weq _ ?P _) = _ =>
rewrite <- (natToWord_wordToNat _ P)
end.
rewrite wordToNat_split2.
rewrite wordToNat_natToWord_idempotent' by lia.
rewrite Nat.Div0.div_0_l by (pose proof (zero_lt_pow2 expWidthMinus2); lia).
auto.
auto.
auto.
auto.
auto.
Qed.
Lemma evalExprStructReadField n fk exprs idx:
evalExpr (ReadStruct (BuildStruct (n := n) fk exprs) idx) =
evalExpr (exprs idx).
Proof.
auto.
Qed.
Lemma evalExprStructReadFieldBetter ls idx:
evalExpr (ReadStruct (getStructVal ls) idx) =
evalExpr (nth_Fin_map2 (@projT1 _ _) (fun x => Expr type (SyntaxKind (snd x))) ls idx
(projT2 (nth_Fin ls (Fin.cast idx (map_length_red (@projT1 _ _) ls))))).
Proof.
auto.
Qed.
Lemma infOrNaN_sExp_expWidthMinus2:
evalExpr (infOrNaN fn) = true -> evalExpr (sExp_expWidthMinus2 (getRawFloat_from_FN fn)) = WO~0.
Proof.
intros H.
apply infOrNaN_sExp_expWidthMinus2' in H.
destruct (@weq _ (evalExpr (sExp_expWidthMinus2 (getRawFloat_from_FN fn))) WO~0); [auto|discriminate].
Qed.
Lemma evalExprStructNotation ls idx:
evalExpr (getStructVal ls) idx =
evalExpr
(nth_Fin_map2 (@projT1 _ _) _ ls idx
(projT2 (nth_Fin ls (Fin.cast idx (map_length_red (@projT1 _ _) ls))))).
Proof.
auto.
Qed.
Lemma wzero_wplus_nop sz (x: word sz): wzero sz ^+ x = x.
Proof.
rewrite wplus_comm.
apply wplus_wzero.
Qed.
Opaque isZeroFractIn normDist subnormFract isZeroExpIn isZeroRecFN isSigNaNRawFloat
isSigNaNRawFloat_frac isSNaN sExp_expWidthMinus2 get_exp_from_RecFN.
Lemma isNaN_or_Inf_infOrNaN:
evalExpr (isNaN_or_Inf (getRecFN_from_FN fn)) = evalExpr (infOrNaN fn).
Proof.
pose proof isZero_not_infOrNaN as sth.
rewrite <- isSpecial_infOrNaN in *.
simpl.
simpl in sth.
match type of sth with
| ?P = true -> ?Q => case_eq P; simpl in *; intros H; [specialize (sth H); auto| clear sth; rewrite ?wzero_wplus]
end.
reflexivity.
Qed.
Transparent isZeroFractIn normDist subnormFract isZeroExpIn isZeroRecFN isSigNaNRawFloat
isSigNaNRawFloat_frac isSNaN sExp_expWidthMinus2 get_exp_from_RecFN.
Lemma evalExprStructReadFieldFull ls idx (x: type _):
evalExpr (@ReadStruct type _ _ (@getStructVal type ls) idx) = x <->
evalExpr
(nth_Fin_map2 (projT1 (P:=fun x : string * Kind => Expr type (SyntaxKind (snd x))))
(fun x : string * Kind => Expr type (SyntaxKind (snd x))) ls idx
(projT2
(nth_Fin ls
(Fin.cast idx (map_length_red (projT1 (P:=fun x : string * Kind => Expr type (SyntaxKind (snd x)))) ls))))) = x.
Proof.
simpl.
tauto.
Qed.
Lemma wones_wconcat:
forall sz, sz > 0 -> wones sz = wconcat WO~1 (wones (pred sz)).
Proof.
induction sz; intros; try lia.
destruct sz; simpl.
- reflexivity.
- assert (l: S sz > 0) by lia.
specialize (IHsz l).
simpl in IHsz.
unfold wones, wconcat.
f_equal.
rewrite wordToZ_ZToWord by lia.
rewrite wordToZ_ZToWord by lia.
rewrite Z.mul_1_l.
rewrite Z.add_sub_assoc.
rewrite Z.add_diag.
f_equal.
rewrite <- Z.pow_succ_r by lia.
f_equal.
lia.
Qed.
Lemma infOrNaN_isZeroNaNInf2_0_isZeroFractIn_helper:
evalExpr (infOrNaN fn) = true ->
(evalExpr (isZeroFractIn fn) = true ->
evalExpr (isZeroNaNInf2 (getRecFN_from_FN fn)) = WO~0).
Proof.
intros sth1 sth2.
cbv delta [isZeroNaNInf2 getRecFN_from_FN].
cbv delta [getRecFN_from_RawFloat getRawFloat_from_FN].
cbv beta.
cbv zeta.
cbv iota.
match goal with
| |- evalExpr
(@ReadStruct type ?n ?fk (@getStructVal type ?ls) ?idx) = ?x =>
rewrite (@evalExprStructReadFieldFull ls idx x)
end.
simpl.
simpl in sth1.
simpl in sth2.
rewrite sth2.
rewrite andb_true_r.
apply getBool_weq in sth1.
rewrite sth1.
clear sth1 sth2.
rewrite wzero_wplus.
assert (sth: getBool (weq (wones expWidth) $0) = false). {
destruct (weq (wones expWidth) $0); simpl; auto.
assert (sth3: expWidth >= 1) by lia.
pose proof (wzero_wones sth3) as sth4.
rewrite e in sth4.
tauto.
}
rewrite sth.
simpl.
rewrite andb_false_r.
rewrite wor_wzero.
rewrite wzero_wor.
rewrite split1_combine_wplus.
rewrite wones_wconcat by lia.
assert (Heq: Init.Nat.pred expWidth = expWidthMinus1) by lia.
rewrite Heq.
rewrite split1_combine_wplus.
rewrite wconcat_w_0.
rewrite wones_natToWord.
rewrite <- natToWord_plus.
pose proof (@Nat.sub_add 1 (2^expWidthMinus1) (one_le_pow2 _)) as sth2.
rewrite sth2.
unfold natToWord.
rewrite Zpow_of_nat.
unfold truncMsb.
simpl.
rewrite Z_mod_same_full.
rewrite Zdiv_0_l.
auto.
Qed.
Lemma SomeLemma0: (forall a b, b > 0 -> b < a -> (a + b)/a = 1)%Z.
Proof.
intros.
assert (Heq1: (a = 1*a)%Z) by lia.
rewrite Heq1 at 1.
rewrite Z_div_plus_full_l by lia.
rewrite Z.div_small by lia.
lia.
Qed.
Lemma SomeLemma1: truncMsb (outSz := expWidth + 1) (wconcat WO~0 (wones expWidth) ^+ wconcat (lsb := expWidth) WO~0 (wconcat (lsb := expWidthMinus1) WO~1 $ (1))) = natToWord 1 1.
Proof.
- unfold natToWord at 2; simpl.
unfold wones; simpl.
unfold wconcat at 3.
unfold natToWord.
assert (ez: wordVal 1 WO~1 = 1%Z) by auto.
rewrite ez; clear ez.
rewrite Z.mul_1_l.
rewrite getWordVal.
+ simpl.
rewrite ? wconcat_0_sz1_w; simpl.
rewrite Zmod_small by lia.
rewrite Zmod_small.
* rewrite <- ZToWord_plus.
simpl.
rewrite Z.sub_add_simpl_r_r.
unfold truncMsb; simpl.
rewrite Zmod_small.
-- rewrite Nat.add_sub.
rewrite SomeLemma0; auto; try lia.
rewrite (Nat2Z.inj_add expWidthMinus1 1).
rewrite Z.pow_add_r by lia.
simpl.
unfold Z.pow_pos; simpl.
lia.
-- rewrite (Nat2Z.inj_add expWidth 1).
rewrite Z.pow_add_r by lia.
simpl.
unfold Z.pow_pos; simpl.
split; [lia|].
rewrite <- Zred_factor1.
apply Zplus_lt_compat_l.
rewrite (Nat2Z.inj_add expWidthMinus1 1).
rewrite Z.pow_add_r by lia.
lia.
* split; [lia|].
rewrite (Nat2Z.inj_add expWidthMinus1 1).
rewrite Z.pow_add_r by lia.
simpl.
unfold Z.pow_pos; simpl.
rewrite <- Zred_factor1.
apply Zplus_lt_compat_l.
rewrite Nat2Z.inj_add.
rewrite Z.pow_add_r by lia; simpl.
unfold Z.pow_pos; simpl.
lia.
+ simpl.
assert ((Z.of_nat expWidthMinus1 >= 1)%Z) by lia.
split; [lia|].
apply Z.pow_gt_1; lia.
Qed.
Lemma SomeLemma2:
@truncMsb 1 expWidth (wones expWidth ^+ @wconcat 1 expWidthMinus1 expWidth WO~1 $1) = $1.
Proof.
unfold wones.
unfold wconcat.
assert (ez: wordVal 1 WO~1 = 1%Z) by auto.
rewrite ez; clear ez.
rewrite <- ZToWord_plus.
assert (ez: wordVal expWidthMinus1 $1 = 1%Z). {
unfold natToWord, wordVal; simpl.
rewrite Zmod_small; [lia|].
split; [lia|].
rewrite Nat2Z.inj_add.
simpl.
rewrite (Z.pow_add_r 2 (Z.of_nat expWidthMinus2) 1) by lia.
lia.
}
rewrite ez.
rewrite Z.sub_add_simpl_r_r.
rewrite Z.mul_1_l.
unfold ZToWord, truncMsb; simpl.
rewrite Z.add_mod by lia.
rewrite Z_mod_same_full; simpl.
rewrite Z.mod_mod by lia.
rewrite (Zmod_small (2^Z.of_nat expWidthMinus1) (2^Z.of_nat expWidth)).
- assert (Heq: expWidth - 1 = expWidthMinus1) by lia.
rewrite Heq.
rewrite Z.div_same by lia; auto.
- split; [lia|].
rewrite (Nat2Z.inj_add expWidthMinus1 1).
rewrite Z.pow_add_r by lia.
simpl.
unfold Z.pow_pos; simpl.
rewrite <- Zred_factor1.
lia.
Qed.
Lemma HsthEasy:
forall (w1 w2: word 1), w2 = WO~1 -> w1 ^| w2 = WO~1.
Proof.
intros.
subst.
unfold wor.
simpl.
destruct w1; simpl.
unfold Z.pow, Z.of_nat, Z.pow_pos in *.
simpl in *.
unfold Z.modulo; simpl.
assert (sth2: wordVal = 0%Z \/ wordVal = 1%Z). {
pose proof (Zmod_odd wordVal).
destruct (Z.odd wordVal); rewrite <- wordBound; auto.
}
destruct sth2; subst; auto.
Qed.
Lemma HsthEasy2:
getBool (weq (wones expWidth) $0) = false.
Proof.
destruct (weq (wones expWidth) $0); simpl; auto.
assert (sth3: expWidth >= 1) by lia.
pose proof (wzero_wones sth3) as sth4.
rewrite e in sth4.
tauto.
Qed.
Lemma infOrNaN_isZeroNaNInf2_1_isZeroFractIn_helper:
evalExpr (infOrNaN fn) = true ->
(evalExpr (isZeroFractIn fn) = false ->
evalExpr (isZeroNaNInf2 (getRecFN_from_FN fn)) = WO~1).
Proof.
intros sth1 sth2.
cbv delta [isZeroNaNInf2 getRecFN_from_FN].
cbv delta [getRecFN_from_RawFloat getRawFloat_from_FN].
cbv beta.
cbv zeta.
cbv iota.
match goal with
| |- evalExpr
(@ReadStruct type ?n ?fk (@getStructVal type ?ls) ?idx) = ?x =>
rewrite (@evalExprStructReadFieldFull ls idx x)
end.
simpl.
simpl in sth1.
simpl in sth2.
rewrite sth2.
rewrite andb_false_r.
apply getBool_weq in sth1.
rewrite sth1.
clear sth1 sth2.
rewrite wzero_wplus.
rewrite HsthEasy2.
simpl.
rewrite andb_true_r.
rewrite wor_wzero.
rewrite split1_combine_wplus.
rewrite wones_wconcat at 1 by lia.
apply HsthEasy.
match goal with
| |- ?Full =>
match Full with
| (if (getBool (weq ?A $1) && getBool (weq ?B $1)) then ?P else ?Q) = ?P =>
let silly := fresh "silly" in
assert (silly: A = $1 /\ B = $1 -> Full)
end
end. {
intros [H1 H2].
rewrite H1, H2.
auto.
}
apply silly; clear silly.
rewrite wconcat_w_0; simpl.
split.
- apply SomeLemma1.
- apply SomeLemma2.
Qed.
Lemma infOrNaN_isZeroNaNInf2_0_isZeroFractIn:
evalExpr (infOrNaN fn) = true -> getBool (@weq _ (evalExpr (isZeroNaNInf2 (getRecFN_from_FN fn))) WO~0) = evalExpr (isZeroFractIn fn).
Proof.
intros h1.
pose proof (infOrNaN_isZeroNaNInf2_0_isZeroFractIn_helper h1) as sth1.
pose proof (infOrNaN_isZeroNaNInf2_1_isZeroFractIn_helper h1) as sth2.
case_eq (evalExpr (isZeroFractIn fn)); intros h.
- specialize (sth1 h).
rewrite sth1; auto.
- specialize (sth2 h).
rewrite sth2; auto.
Qed.
Lemma infOrNaN_isZeroNaNInf2_1_isZeroFractIn:
evalExpr (infOrNaN fn) = true -> getBool (@weq _ (evalExpr (isZeroNaNInf2 (getRecFN_from_FN fn))) WO~1) = negb (evalExpr (isZeroFractIn fn)).
Proof.
intros h1.
pose proof (infOrNaN_isZeroNaNInf2_0_isZeroFractIn_helper h1) as sth1.
pose proof (infOrNaN_isZeroNaNInf2_1_isZeroFractIn_helper h1) as sth2.
case_eq (evalExpr (isZeroFractIn fn)); intros h.
- specialize (sth1 h).
rewrite sth1; auto.
- specialize (sth2 h).
rewrite sth2; auto.
Qed.
Opaque isNaN_or_Inf isZeroFractIn subnormFract
isZeroRecFN isSigNaNRawFloat isSigNaNRawFloat_frac isSNaN sExp_expWidth sExp_expWidthMinus1
isZeroNaNInf1 isZeroNaNInf0 get_exp_from_RecFN.
Lemma RawFloat_RecFN_FN_isNaN:
evalExpr (getRawFloat_from_RecFN (getRecFN_from_FN fn)) Fin.F1 = evalExpr (getRawFloat_from_FN fn) Fin.F1.
Proof.
pose proof isNaN_or_Inf_infOrNaN as sth1.
pose proof infOrNaN_isZeroNaNInf2_0_isZeroFractIn as sth2.
pose proof isSpecial_infOrNaN as sth3.
Opaque isNaN_or_Inf infOrNaN isZeroNaNInf2 isZeroFractIn isSpecial.
simpl.
rewrite sth1, sth3.
destruct (evalExpr (infOrNaN fn)); simpl; auto.
unfold natToWord; simpl.
rewrite <- sth2; auto.
match goal with
| |- getBool ?P = negb (getBool ?Q) => case_eq P; case_eq Q; intros; simpl in *; auto
end.
- clear - e e0; rewrite e in e0; discriminate.
- clear - n n0. exfalso; eapply word1_neq; eauto.
Qed.
Transparent isNaN_or_Inf infOrNaN isZeroNaNInf2 isZeroFractIn isSpecial.
Lemma RawFloat_RecFN_FN_isInf:
evalExpr (getRawFloat_from_RecFN (getRecFN_from_FN fn)) (Fin.FS Fin.F1) = evalExpr (getRawFloat_from_FN fn) (Fin.FS Fin.F1).
Proof.
pose proof isNaN_or_Inf_infOrNaN as sth1.
pose proof infOrNaN_isZeroNaNInf2_0_isZeroFractIn as sth2.
pose proof isSpecial_infOrNaN as sth3.
Opaque isNaN_or_Inf infOrNaN isZeroNaNInf2 isZeroFractIn isSpecial.
simpl.
rewrite sth1, sth3.
destruct (evalExpr (infOrNaN fn)); simpl; auto.
Qed.
Transparent isNaN_or_Inf infOrNaN isZeroNaNInf2 isZeroFractIn isSpecial.
Lemma RawFloat_RecFN_FN_sign:
evalExpr (getRawFloat_from_RecFN (getRecFN_from_FN fn)) (Fin.FS (Fin.FS (Fin.FS Fin.F1))) = evalExpr (getRawFloat_from_FN fn) (Fin.FS (Fin.FS (Fin.FS Fin.F1))).
Proof.
auto.
Qed.
Transparent isNaN_or_Inf isZeroFractIn subnormFract
isZeroRecFN isSigNaNRawFloat isSigNaNRawFloat_frac isSNaN sExp_expWidth sExp_expWidthMinus1
isZeroNaNInf1 isZeroNaNInf0 get_exp_from_RecFN.
(* copy-pasted from bbv, commit b98e19b *)
Lemma isZeroRecFN_isZero:
evalExpr (isZeroRecFN (getRecFN_from_FN fn)) = evalExpr (isZero fn).
Proof.
Opaque isNaN_or_Inf infOrNaN isZeroFractIn isSpecial normDist subnormFract isZeroExpIn.
simpl in *.
match goal with
| |- _ = ?P => case_eq P; intros; simpl; auto
end.
- rewrite isSpecial_infOrNaN.
pose proof isZero_not_infOrNaN as hyp2.
simpl in *.
specialize (hyp2 H).
rewrite hyp2.
auto.
- rewrite wor_wzero.
rewrite ?split1_combine.
rewrite isSpecial_infOrNaN.
case_eq (evalExpr (isZeroExpIn fn)); intros hyp; rewrite hyp in *; simpl in *.
+ rewrite H in *; simpl; rewrite andb_true_r.
rewrite ?wzero_wplus.
Transparent isZeroExpIn infOrNaN.
simpl in *.
match type of hyp with
| getBool ?P = true => destruct P; [|discriminate]
end.
rewrite e.
pose proof (@wzero_wones expWidth ltac:(lia)).
match goal with
| |- context [if getBool ?P then _ else _] => destruct P; [tauto|simpl; rewrite wzero_wor]
end.
match goal with
| |- context [@wnot _ ?P] => rewrite <- (natToWord_wordToNat _ (@wnot _ P))
end.
rewrite ?wordToNat_wnot.
match goal with
| |- context [wconcat ?P ?Q] => (rewrite <- (natToWord_wordToNat _ (wconcat P Q)))
end.
rewrite ?wordToNat_combine; simpl.
rewrite ?Nat.mul_1_r, ?Nat.mul_0_r, ?Nat.add_0_r.
rewrite wordToNat_natToWord_idempotent'.
* rewrite <- ?natToWord_plus.
match goal with
| |- context[?A - @wordToNat _ (?B) - 1 + (2 + ?P)] => pose proof (wordToNat_bound B) as sth0;
assert (sth1: A > @wordToNat _ B) by lia;
assert (sth2: A - @wordToNat _ B - 1 + (2 + P) = A + P + 1 - @wordToNat _ B) by lia; rewrite ?sth2;
remember B as val
end.
Transparent normDist.
unfold normDist in Heqval.
simpl in Heqval.
match goal with
| [H: val = if getBool (@weq _ ?w1 ?w2) then _ else _ |- _] => destruct (@weq _ w1 w2); simpl in *
end.
***
subst.
assert (sth3: 2 ^ (expWidth + 1) + 2 ^ expWidthMinus1 + 1 - sigWidthMinus2 = 2 ^ (expWidth + 1) + (2 ^ expWidthMinus1 + 1 - sigWidthMinus2)). {
pose proof expWidth_ge_sigWidth.
rewrite Nat.add_sub_assoc; lia.
}
assert (sigWidthMinus2 < 2 ^ (expWidth + 1)). {
rewrite ?Nat.pow_add_r; simpl.
rewrite ?Nat.pow_add_r; simpl.
pose proof (pow2_zero expWidthMinus2).
nia.
}
destruct Compare_dec.le_lt_dec with sigWidthMinus2 1 as [sig_le_2 | sig_gt_2].
apply andb_false_intro1.
apply andb_false_intro2.
rewrite <- wmsb_true_split2_wones with (b:=false).
simpl; auto.
rewrite wordToNat_natToWord_idempotent'; auto.
rewrite sth3.
rewrite natToWord_plus.
rewrite pow2_wzero.
rewrite wzero_wplus.
rewrite split1_fits_natToWord.
rewrite Nat.add_1_r.
apply wmsb_1_natToWord.
split; auto.
lia.
pose proof expWidth_ge_sigWidth.
apply lt_minus'; lia.
pose proof expWidth_ge_sigWidth.
apply lt_minus'. lia.
rewrite Nat.add_1_r.
simpl; lia.
rewrite ?Nat.add_1_r.
rewrite <- Nat.add_1_r.
simpl.
apply -> Nat.add_lt_mono_l.
rewrite ?Nat.add_0_r.
rewrite <- mul2_add.
replace (2 ^ expWidthMinus2 * 2) with (2 ^ expWidthMinus2 * 2 ^ 1) by (simpl;reflexivity).
rewrite <- Nat.pow_add_r.
lia.
apply andb_false_intro2.
rewrite <- wmsb_true_split2_wones with (b:=false).
simpl; auto.
rewrite wordToNat_natToWord_idempotent'; auto.
rewrite sth3.
rewrite natToWord_plus.
rewrite pow2_wzero.
rewrite wzero_wplus.
rewrite split1_fits_natToWord.
rewrite Nat.add_1_r.
assert (sth4: 2 ^ (S expWidthMinus2) + 1 - sigWidthMinus2 < 2 * 2 ^ expWidthMinus2). {
rewrite Nat.add_comm.
rewrite <- Nat.add_sub_assoc.
rewrite Nat.add_comm.
assert (sth4: 2 * 2 ^ expWidthMinus2 = 2 ^ (S expWidthMinus2)). {
assert (2 ^ 1 = 2). auto.
rewrite <- H2 at 1.
rewrite <- pow2_add_mul.
rewrite <- Nat.add_1_r. auto.
}
destruct sigWidthMinus2 as [| sigWidthMinus3] eqn:Heq; [inversion sig_gt_2|].
destruct sigWidthMinus3 as [| sigWidthMinus4] eqn:Heq1; [lia|].
rewrite sth4.
replace (S (S sigWidthMinus4)) with (sigWidthMinus4 + 1 + 1) by lia.
rewrite Nat.sub_add_distr.
replace (2 ^ (S expWidthMinus2) - (sigWidthMinus4 + 1) - 1 + 1) with (2 ^ (S expWidthMinus2) - (sigWidthMinus4 + 1)) by lia.
rewrite <- Heq in *.
pose proof expWidth_ge_sigWidth.
apply Nat.sub_lt; lia.
pose proof expWidth_ge_sigWidth.
rewrite ?Nat.pow_add_r; simpl.
lia.
}
rewrite split1_fits_natToWord; auto.
apply wmsb_1_natToWord.
split; auto.
simpl.
assert (sth5:
2 ^ expWidthMinus2 + (2 ^ expWidthMinus2 + 0) + 1 - sigWidthMinus2 =
2 ^ expWidthMinus2 + ((2 ^ expWidthMinus2 + 0) + 1 - sigWidthMinus2)). {
pose proof expWidth_ge_sigWidth.
rewrite Nat.add_sub_assoc; lia.
}
rewrite sth5.
rewrite <- Nat.add_0_r at 1.
apply -> Nat.add_le_mono_l.
lia.
apply lt_minus'; try lia.
rewrite Nat.add_1_r.
simpl.
rewrite ?Nat.add_1_r.
simpl.
lia.
rewrite ?Nat.add_1_r.
simpl.
lia.
*** rewrite evalExpr_countLeadingZeros in Heqval.
pose proof expWidth_ge_sigWidth as sth3.
assert (sth4: 2 ^ (expWidth + 1) > sigWidthMinus1). {
rewrite ?Nat.pow_add_r; simpl.
pose proof (pow2_zero expWidthMinus2).
nia.