- 46157DCF363B52695F6EC10671307155E62702A1EA79861A067F56716B03ACB8573988BED3E2350401AD8222F7351F96D22383F2B7B5FC8EBC1D9901E24B6F63+ 4CCCFEFD78EA3AF2EBFC0482E530B2C554721504BB4BB7227ED15E72DCE1D29B95F4711A446E46D2025AF228D14C46B93F76159BBB836A2CBABAA15A3DCAFA41ffa/libffa/fz_gcd.adb(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;