tree checksum vpatch file split hunks
all signers: bvt diana_coman asciilifeform
antecedents: ffa_ch16_miller_rabin.kv ffa_ch15_gcd.kv ffa_ch20d_litmus_nested_fix.kv
press order:
patch:
(22 . 3)(22 . 4)
5 611775 ffa_ch20b_litmus_legacy_hashes "Support for certain ancient hash algos in Litmus."
6 612395 ffa_ch20c_litmus_clearsigned "Support for 'clearsigned' GPG texts in Litmus."
7 612828 ffa_ch20d_litmus_nested_fix "Fix for bug where nested 'clearsigned' sigs were rejected."
8 629424 ffa_ch21a_bis_fix_ch15_gcd "Fix for lethal flaw in Ch.15's Greatest Common Divisor."
- A685AE297E995254762E5D2AE4A7FB4180391E26803C6DE1761F0CF6023062BEFA31A00892A12E035BE0526A8536B91AD29F03BD451711665B968CF4084DB6F0(24 . 6)(24 . 4)
13
14 Questions?
15
16 http://webchat.freenode.net/?channels=#trilema&nick=from_ffa
17
18 Privmsg one of the people speaking and ask politely for 'voice'.
19 http://webchat.freenode.net/?channels=#asciilifeform&nick=from_ffa
- D6E1B802991B5A601E4253D419E72B22ADD215ACE76B8CDD8449C7587D7C6BBDB3A90074D67DDD33C5B7FA9A2584CAEC81DB4A658B817B7659CD3F92AF3491D7(45 . 7)(45 . 7)
24 --- Current 'deg. Kelvin' Version of FFA
25 ----------------------------------------------------------------------------
26
27 FFA_K_Version : constant Natural := 253;
28 FFA_K_Version : constant Natural := 200;
29
30 ----------------------------------------------------------------------------
31 --- Fundamental Types and Sizes
- 46157DCF363B52695F6EC10671307155E62702A1EA79861A067F56716B03ACB8573988BED3E2350401AD8222F7351F96D22383F2B7B5FC8EBC1D9901E24B6F63(21 . 6)(21 . 7)
36 with FZ_Shift; use FZ_Shift;
37 with FZ_QShft; use FZ_QShft;
38 with FZ_Arith; use FZ_Arith;
39 with FZ_BitOp; use FZ_BitOp;
40 with FZ_Pred; use FZ_Pred;
41
42
(36 . 15)(37 . 18)
44 subtype Width is Word_Index range X'Range;
45
46 -- Working buffers for GCD computation, initially equal to the inputs
47 A : FZ(Width) := X; -- GCD will appear in A in the end
48 A : FZ(Width) := X;
49 B : FZ(Width) := Y;
50
51 -- Evenness (negation of lowest bit) of A and B respectively
52 Ae, Be : WBool;
53
54 -- Common power-of-2 factor
55 -- Common power-of-2 factor: incremented when Ae and Be are both 1
56 Twos : Word := 0;
57
58 -- This flag is set when A and B are BOTH ODD
59 OO : WBool;
60
61 -- |A - B|
62 D : FZ(Width);
63
(53 . 35)(57 . 42)
65
66 begin
67
68 -- For convergence, requires number of shots equal to 2 * FZ_Bitness:
69 for i in 1 .. 2 * FZ_Bitness(X) loop
70 -- To converge, requires number of shots equal to (2 * FZ_Bitness) - 1:
71 for i in 1 .. (2 * FZ_Bitness(X)) - 1 loop
72
73 -- Whether A and B are currently BOTH ODD :
74 OO := FZ_OddP(A) and FZ_OddP(B);
75
76 -- D := |A - B|
77 FZ_Sub_Abs(X => A, Y => B, Difference => D, Underflow => A_lt_B);
78
79 -- IFF A,B both ODD, and A < B : B' := A ; otherwise no change :
80 FZ_Mux(X => B, Y => A, Result => B, Sel => OO and A_lt_B);
81
82 -- IFF A,B both ODD: A' := |A - B| ; otherwise no change :
83 FZ_Mux(X => A, Y => D, Result => A, Sel => OO);
84
85 -- If A is even, A := A >> 1; otherwise A := A
86 -- If A is now EVEN: A := A >> 1; otherwise no change
87 Ae := 1 - FZ_OddP(A);
88 FZ_ShiftRight(A, A, WBit_Index(Ae));
89
90 -- If B is even, B := B >> 1; otherwise B := B
91 -- If B is now EVEN: B := B >> 1; otherwise no change
92 Be := 1 - FZ_OddP(B);
93 FZ_ShiftRight(B, B, WBit_Index(Be));
94
95 -- If both A and B were even, increment the common power-of-two
96 Twos := Twos + (Ae and Be);
97
98 -- D := |A - B|
99 FZ_Sub_Abs(X => A, Y => B, Difference => D, Underflow => A_lt_B);
100
101 -- B' := min(A, B)
102 FZ_Mux(X => B, Y => A, Result => B, Sel => A_lt_B);
103
104 -- A' := |A - B|
105 A := D;
106
107 end loop;
108
109 -- Normally, B will contain the GCD, but in the (N,0) N > 0 case -- A.
110 -- The other variable will always equal 0. Hence, take Bitwise-OR(A,B):
111 FZ_Or(X => A, Y => B, Result => A);
112
113 -- Reintroduce the common power-of-2 factor stored in 'Twos'
114 FZ_Quiet_ShiftLeft(N => A, ShiftedN => A, Count => Indices(Twos));
115
116 -- Output final result
117 -- Output final result -- the GCD.
118 Result := A;
119
120 end FZ_Greatest_Common_Divisor;