File : fz_divis.adb
1 ------------------------------------------------------------------------------
2 ------------------------------------------------------------------------------
3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
4 -- --
5 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
7 -- --
8 -- You do not have, nor can you ever acquire the right to use, copy or --
9 -- distribute this software ; Should you use this software for any purpose, --
10 -- or copy and distribute it to anyone or in any manner, you are breaking --
11 -- the laws of whatever soi-disant jurisdiction, and you promise to --
12 -- continue doing so for the indefinite future. In any case, please --
13 -- always : read and understand any software ; verify any PGP signatures --
14 -- that you use - for any purpose. --
15 -- --
16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
17 ------------------------------------------------------------------------------
18 ------------------------------------------------------------------------------
19
20 with Words; use Words;
21 with W_Pred; use W_Pred;
22 with W_Shifts; use W_Shifts;
23 with FZ_Basic; use FZ_Basic;
24 with FZ_Arith; use FZ_Arith;
25 with FZ_BitOp; use FZ_BitOp;
26 with FZ_Shift; use FZ_Shift;
27
28
29 package body FZ_Divis is
30
31 -- Dividend is divided by Divisor, producing Quotient and Remainder.
32 -- WARNING: NO div0 test here! Caller must test.
33 procedure FZ_IDiv(Dividend : in FZ;
34 Divisor : in FZ;
35 Quotient : out FZ;
36 Remainder : out FZ) is
37
38 -- The working register
39 QR : FZ(1 .. Dividend'Length + Divisor'Length);
40
41 -- Bottom seg of Z will end up containing the Quotient; top - remainder
42 Q : FZ renames QR(1 .. Dividend'Length); -- Quotient
43 R : FZ renames QR(Dividend'Length + 1 .. QR'Last); -- Remainder
44
45 C : WBool := 0; -- Borrow, from comparator
46 begin
47 Q := Dividend; -- Q begins with the Dividend
48 FZ_Clear(R); -- R begins empty
49
50 -- For each bit of Dividend:
51 for i in 1 .. FZ_Bitness(Dividend) loop
52
53 -- Advance QR by 1 bit:
54 FZ_ShiftLeft(QR, QR, 1);
55
56 -- Subtract Divisor from R; Underflow goes into C
57 FZ_Sub(X => R, Y => Divisor, Difference => R, Underflow => C);
58
59 -- If C=1, subtraction underflowed, and then Divisor gets added back:
60 FZ_Add_Gated(X => R, Y => Divisor, Gate => C, Sum => R);
61
62 -- Current result-bit is equal to Not-C, i.e. 1 if Divisor 'went in'
63 FZ_Or_W(Q, W_Not(C));
64
65 end loop;
66
67 Quotient := Q; -- Output the Quotient.
68 Remainder := R; -- Output the Remainder.
69
70 end FZ_IDiv;
71
72 -- Exactly same thing as IDiv, but keep only the Quotient
73 procedure FZ_Div(Dividend : in FZ;
74 Divisor : in FZ;
75 Quotient : out FZ) is
76 Remainder : FZ(Divisor'Range);
77 pragma Unreferenced(Remainder);
78 begin
79 FZ_IDiv(Dividend, Divisor, Quotient, Remainder);
80 end FZ_Div;
81
82 -- Modulus. Permits the asymmetric Dividend and Divisor in FZ_Mod_Exp.
83 procedure FZ_Mod(Dividend : in FZ;
84 Divisor : in FZ;
85 Remainder : out FZ) is
86
87 -- Length of Divisor and Remainder; <= Dividend'Length
88 L : constant Indices := Divisor'Length;
89
90 -- Remainder register, starts as zero
91 R : FZ(1 .. L) := (others => 0);
92
93 -- Indices into the words of Dividend
94 subtype Dividend_Index is Word_Index range Dividend'Range;
95
96 -- Permissible 'cuts' for the Slice operation
97 subtype Divisor_Cuts is Word_Index range 2 .. Divisor'Length;
98
99 -- Performs Restoring Division on a given segment of Dividend:Divisor
100 procedure Slice(Index : Dividend_Index;
101 Cut : Divisor_Cuts) is
102 begin
103
104 declare
105
106 -- Borrow, from comparator
107 C : WBool;
108
109 -- Left-Shift Overflow
110 LsO : WBool;
111
112 -- Current cut of Remainder register
113 Rs : FZ renames R(1 .. Cut);
114
115 -- Current cut of Divisor
116 Ds : FZ renames Divisor(1 .. Cut);
117
118 -- Current word of Dividend, starting from the highest
119 W : Word := Dividend(Dividend'Last + 1 - Index);
120
121 begin
122
123 -- For each bit in the current Dividend word:
124 for b in 1 .. Bitness loop
125
126 -- Send top bit of current Dividend word to the bottom of W
127 W := Rotate_Left(W, 1);
128
129 -- Advance Rs, shifting in the current Dividend bit
130 FZ_ShiftLeft_O_I(N => Rs, ShiftedN => Rs, Count => 1,
131 OF_In => W and 1,
132 Overflow => LsO);
133
134 -- Subtract Divisor-Cut from R-Cut; Underflow goes into C
135 FZ_Sub(X => Rs, Y => Ds, Difference => Rs, Underflow => C);
136
137 -- If C=1, subtraction underflowed, and we must undo it:
138 FZ_Add_Gated(X => Rs, Y => Ds, Sum => Rs,
139 Gate => C and W_Not(LsO));
140
141 end loop;
142
143 end;
144
145 end Slice;
146
147 begin
148
149 -- Process bottom half of dividend:
150 for i in 1 .. L - 1 loop
151
152 Slice(i, i + 1); -- stay ahead by a word to handle carry
153
154 end loop;
155
156 -- Process top half of dividend
157 for i in L .. Dividend'Length loop
158
159 Slice(i, L);
160
161 end loop;
162
163 -- Output the Remainder.
164 Remainder := R;
165
166 end FZ_Mod;
167
168 end FZ_Divis;