1 ------------------------------------------------------------------------------ 2 ------------------------------------------------------------------------------ 3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. -- 4 -- -- 5 -- (C) 2019 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 73 -- Exactly same thing as IDiv, but keep only the Quotient 74 procedure FZ_Div(Dividend : in FZ; 75 Divisor : in FZ; 76 Quotient : out FZ) is 77 Remainder : FZ(Divisor'Range); 78 pragma Unreferenced(Remainder); 79 begin 80 FZ_IDiv(Dividend, Divisor, Quotient, Remainder); 81 end FZ_Div; 82 83 84 -- Modulus. Permits the asymmetric Dividend and Divisor in FZ_Mod_Exp. 85 procedure FZ_Mod(Dividend : in FZ; 86 Divisor : in FZ; 87 Remainder : out FZ) is 88 89 -- Length of Divisor and Remainder; <= Dividend'Length 90 L : constant Indices := Divisor'Length; 91 92 -- Remainder register, starts as zero 93 R : FZ(1 .. L) := (others => 0); 94 95 -- Indices into the words of Dividend 96 subtype Dividend_Index is Word_Index range Dividend'Range; 97 98 -- Permissible 'cuts' for the Slice operation 99 subtype Divisor_Cuts is Word_Index range 2 .. Divisor'Length; 100 101 -- Performs Restoring Division on a given segment of Dividend:Divisor 102 procedure Slice(Index : Dividend_Index; 103 Cut : Divisor_Cuts) is 104 105 -- Borrow, from comparator 106 C : WBool; 107 108 -- Left-Shift Overflow 109 LsO : WBool; 110 111 -- Current cut of Remainder register 112 Rs : FZ renames R(1 .. Cut); 113 114 -- Current cut of Divisor 115 Ds : FZ renames Divisor(1 .. Cut); 116 117 -- Current word of Dividend, starting from the highest 118 W : Word := Dividend(Dividend'Last + 1 - Index); 119 120 begin 121 122 -- For each bit in the current Dividend word: 123 for b in 1 .. Bitness loop 124 125 -- Send top bit of current Dividend word to the bottom of W 126 W := Rotate_Left(W, 1); 127 128 -- Advance Rs, shifting in the current Dividend bit 129 FZ_ShiftLeft_O_I(N => Rs, ShiftedN => Rs, Count => 1, 130 OF_In => W and 1, 131 Overflow => LsO); 132 133 -- Subtract Divisor-Cut from R-Cut; Underflow goes into C 134 FZ_Sub(X => Rs, Y => Ds, Difference => Rs, Underflow => C); 135 136 -- If C=1, subtraction underflowed, and we must undo it: 137 FZ_Add_Gated(X => Rs, Y => Ds, Sum => Rs, 138 Gate => C and W_Not(LsO)); 139 140 end loop; 141 142 end Slice; 143 144 begin 145 146 -- Process bottom half of dividend: 147 for i in 1 .. L - 1 loop 148 149 Slice(i, i + 1); -- stay ahead by a word to handle carry 150 151 end loop; 152 153 -- Process top half of dividend 154 for i in L .. Dividend'Length loop 155 156 Slice(i, L); 157 158 end loop; 159 160 -- Output the Remainder. 161 Remainder := R; 162 163 end FZ_Mod; 164 165 end FZ_Divis;