raw
ffa_ch14_barrett.kv     1 ------------------------------------------------------------------------------
ffa_ch14_barrett.kv     2 ------------------------------------------------------------------------------
ffa_ch14_barrett.kv     3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
ffa_ch14_barrett.kv     4 --                                                                          --
ffa_ch15_gcd.kv         5 -- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org )                      --
ffa_ch14_barrett.kv     6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html     --
ffa_ch14_barrett.kv     7 --                                                                          --
ffa_ch14_barrett.kv     8 -- You do not have, nor can you ever acquire the right to use, copy or      --
ffa_ch14_barrett.kv     9 -- distribute this software ; Should you use this software for any purpose, --
ffa_ch14_barrett.kv    10 -- or copy and distribute it to anyone or in any manner, you are breaking   --
ffa_ch14_barrett.kv    11 -- the laws of whatever soi-disant jurisdiction, and you promise to         --
ffa_ch14_barrett.kv    12 -- continue doing so for the indefinite future. In any case, please         --
ffa_ch14_barrett.kv    13 -- always : read and understand any software ; verify any PGP signatures    --
ffa_ch14_barrett.kv    14 -- that you use - for any purpose.                                          --
ffa_ch14_barrett.kv    15 --                                                                          --
ffa_ch14_barrett.kv    16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     --
ffa_ch14_barrett.kv    17 ------------------------------------------------------------------------------
ffa_ch14_barrett.kv    18 ------------------------------------------------------------------------------
ffa_ch14_barrett.kv    19 
ffa_ch14_barrett.kv    20 with Words;    use Words;
ffa_ch14_barrett.kv    21 with Word_Ops; use Word_Ops;
ffa_ch14_barrett.kv    22 with W_Mul;    use W_Mul;
ffa_ch14_barrett.kv    23 with FZ_Arith; use FZ_Arith;
ffa_ch14_barrett.kv    24 with FZ_Mul;   use FZ_Mul;
ffa_ch14_barrett.kv    25 
ffa_ch14_barrett.kv    26 
ffa_ch14_barrett.kv    27 -- "Low Multiplication" computes only the bottom half of the product XY.
ffa_ch14_barrett.kv    28 -- Presently, it is used solely in Barrett's Modular Reduction.
ffa_ch14_barrett.kv    29 
ffa_ch14_barrett.kv    30 package body FZ_LoMul is
ffa_ch14_barrett.kv    31       
ffa_ch14_barrett.kv    32    -- Low-Only Comba's multiplier. (CAUTION: UNBUFFERED)
ffa_ch14_barrett.kv    33    procedure FZ_Low_Mul_Comba(X     : in  FZ;
ffa_ch14_barrett.kv    34                               Y     : in  FZ;
ffa_ch14_barrett.kv    35                               XY    : out FZ) is
ffa_ch14_barrett.kv    36       
ffa_ch14_barrett.kv    37       -- Words in each multiplicand (and also in the half-product)
ffa_ch14_barrett.kv    38       L : constant Word_Index := X'Length;
ffa_ch14_barrett.kv    39       
ffa_ch14_barrett.kv    40       -- 3-word Accumulator
ffa_ch14_barrett.kv    41       A2, A1, A0 : Word := 0;
ffa_ch14_barrett.kv    42       
ffa_ch14_barrett.kv    43    begin
ffa_ch14_barrett.kv    44       
ffa_ch14_barrett.kv    45       -- Compute the lower half of the Product, which is all we want:
ffa_ch14_barrett.kv    46       for N in 0 .. L - 1 loop
ffa_ch14_barrett.kv    47          
ffa_ch14_barrett.kv    48          -- Compute the Nth (indexed from zero) column of the Half-Product
ffa_ch14_barrett.kv    49          declare
ffa_ch14_barrett.kv    50             
ffa_ch14_barrett.kv    51             -- The outputs of a Word multiplication
ffa_ch14_barrett.kv    52             Lo, Hi : Word;
ffa_ch14_barrett.kv    53             
ffa_ch14_barrett.kv    54             -- Carry for the Accumulator addition
ffa_ch14_barrett.kv    55             C      : WBool;
ffa_ch14_barrett.kv    56             
ffa_ch14_barrett.kv    57             -- Sum for Accumulator addition
ffa_ch14_barrett.kv    58             Sum    : Word;
ffa_ch14_barrett.kv    59             
ffa_ch14_barrett.kv    60          begin
ffa_ch14_barrett.kv    61             
ffa_ch14_barrett.kv    62             -- For lower half of XY, will go from 0 to N
ffa_ch14_barrett.kv    63             -- For upper half of XY, will go from N - L + 1 to L - 1
ffa_ch14_barrett.kv    64             for j in 0 .. N loop
ffa_ch14_barrett.kv    65                
ffa_ch14_barrett.kv    66                -- Hi:Lo := j-th Word of X  *  (N - j)-th Word of Y
ffa_ch14_barrett.kv    67                Mul_Word(X(X'First + j),
ffa_ch14_barrett.kv    68                         Y(Y'First - j + N),
ffa_ch14_barrett.kv    69                         Lo, Hi);
ffa_ch14_barrett.kv    70                
ffa_ch14_barrett.kv    71                -- Now add Hi:Lo into the Accumulator:
ffa_ch14_barrett.kv    72                
ffa_ch14_barrett.kv    73                -- A0 += Lo; C := Carry
ffa_ch14_barrett.kv    74                Sum := A0 + Lo;
ffa_ch14_barrett.kv    75                C   := W_Carry(A0, Lo, Sum);
ffa_ch14_barrett.kv    76                A0  := Sum;
ffa_ch14_barrett.kv    77                
ffa_ch14_barrett.kv    78                -- A1 += Hi + C; C := Carry
ffa_ch14_barrett.kv    79                Sum := A1 + Hi + C;
ffa_ch14_barrett.kv    80                C   := W_Carry(A1, Hi, Sum);
ffa_ch14_barrett.kv    81                A1  := Sum;
ffa_ch14_barrett.kv    82                
ffa_ch14_barrett.kv    83                -- A2 += A2 + C
ffa_ch14_barrett.kv    84                A2  := A2 + C;
ffa_ch14_barrett.kv    85                
ffa_ch14_barrett.kv    86             end loop;
ffa_ch14_barrett.kv    87             
ffa_ch14_barrett.kv    88             -- We now have the Nth (indexed from zero) word of XY
ffa_ch14_barrett.kv    89             XY(XY'First + N) := A0;
ffa_ch14_barrett.kv    90             
ffa_ch14_barrett.kv    91             -- Right-Shift the Accumulator by one Word width:
ffa_ch14_barrett.kv    92             A0 := A1;
ffa_ch14_barrett.kv    93             A1 := A2;
ffa_ch14_barrett.kv    94             A2 := 0;
ffa_ch14_barrett.kv    95          end;
ffa_ch14_barrett.kv    96          
ffa_ch14_barrett.kv    97       end loop;
ffa_ch14_barrett.kv    98       
ffa_ch14_barrett.kv    99    end FZ_Low_Mul_Comba;
ffa_ch14_barrett.kv   100    
ffa_ch14_barrett.kv   101    
ffa_ch14_barrett.kv   102    -- Low-Only Multiplier. (CAUTION: UNBUFFERED)
ffa_ch14_barrett.kv   103    procedure Low_Mul(X  : in  FZ;
ffa_ch14_barrett.kv   104                      Y  : in  FZ;
ffa_ch14_barrett.kv   105                      XY : out FZ) is
ffa_ch14_barrett.kv   106       
ffa_ch14_barrett.kv   107       -- L is the wordness of a multiplicand. Guaranteed to be a power of two.
ffa_ch14_barrett.kv   108       L : constant Word_Count := X'Length;
ffa_ch14_barrett.kv   109       
ffa_ch14_barrett.kv   110       -- K is HALF of the length of a multiplicand.
ffa_ch14_barrett.kv   111       K : constant Word_Index := L / 2;
ffa_ch14_barrett.kv   112       
ffa_ch14_barrett.kv   113       -- A 'KSeg' is the same length as HALF of a multiplicand.
ffa_ch14_barrett.kv   114       subtype KSeg is FZ(1 .. K);
ffa_ch14_barrett.kv   115       
ffa_ch14_barrett.kv   116       -- The two K-sized variables of the half-product equation:
ffa_ch14_barrett.kv   117       LH, HL : KSeg;
ffa_ch14_barrett.kv   118       
ffa_ch14_barrett.kv   119       -- Bottom and Top K-sized halves of the multiplicand X.
ffa_ch14_barrett.kv   120       XLo        : KSeg  renames    X(  X'First       ..   X'Last - K );
ffa_ch14_barrett.kv   121       XHi        : KSeg  renames    X(  X'First + K   ..   X'Last     );
ffa_ch14_barrett.kv   122       
ffa_ch14_barrett.kv   123       -- Bottom and Top K-sized halves of the multiplicand Y.
ffa_ch14_barrett.kv   124       YLo        : KSeg  renames    Y(  Y'First       ..   Y'Last - K );
ffa_ch14_barrett.kv   125       YHi        : KSeg  renames    Y(  Y'First + K   ..   Y'Last     );
ffa_ch14_barrett.kv   126       
ffa_ch14_barrett.kv   127       -- Top K-sized half of the half-product XY.
ffa_ch14_barrett.kv   128       XYHi       : KSeg  renames   XY( XY'First + K   ..  XY'Last     );
ffa_ch14_barrett.kv   129       
ffa_ch14_barrett.kv   130       -- Carry from individual term additions.
ffa_ch14_barrett.kv   131       C          : WBool;
ffa_ch14_barrett.kv   132       pragma Unreferenced(C);
ffa_ch14_barrett.kv   133       
ffa_ch14_barrett.kv   134    begin
ffa_ch14_barrett.kv   135       
ffa_ch14_barrett.kv   136       -- Recurse to FULL-width multiplication: XY := XLo * YLo
ffa_ch14_barrett.kv   137       FZ_Multiply_Unbuffered(XLo, YLo, XY);
ffa_ch14_barrett.kv   138       
ffa_ch14_barrett.kv   139       -- Recurse to HALF-width multiplication: LH := XLo * YHi
ffa_ch14_barrett.kv   140       FZ_Low_Multiply_Unbuffered(XLo, YHi, LH);
ffa_ch14_barrett.kv   141       
ffa_ch14_barrett.kv   142       -- Recurse to HALF-width multiplication: HL := XHi * YLo
ffa_ch14_barrett.kv   143       FZ_Low_Multiply_Unbuffered(XHi, YLo, HL);
ffa_ch14_barrett.kv   144       
ffa_ch14_barrett.kv   145       -- XY += 2^(K * Bitness) * LH
ffa_ch14_barrett.kv   146       FZ_Add_D(X => XYHi, Y => LH, Overflow => C);
ffa_ch14_barrett.kv   147       
ffa_ch14_barrett.kv   148       -- XY += 2^(K * Bitness) * HL
ffa_ch14_barrett.kv   149       FZ_Add_D(X => XYHi, Y => HL, Overflow => C);
ffa_ch14_barrett.kv   150       
ffa_ch14_barrett.kv   151    end Low_Mul;
ffa_ch14_barrett.kv   152    -- CAUTION: Inlining prohibited for Low_Mul !
ffa_ch14_barrett.kv   153    
ffa_ch14_barrett.kv   154    
ffa_ch14_barrett.kv   155    -- Low-Only Multiplier. (CAUTION: UNBUFFERED)
ffa_ch14_barrett.kv   156    procedure FZ_Low_Multiply_Unbuffered(X     : in  FZ;
ffa_ch14_barrett.kv   157                                         Y     : in  FZ;
ffa_ch14_barrett.kv   158                                         XY    : out FZ) is
ffa_ch14_barrett.kv   159       
ffa_ch14_barrett.kv   160       -- The length of either multiplicand
ffa_ch14_barrett.kv   161       L : constant Word_Count := X'Length;
ffa_ch14_barrett.kv   162       
ffa_ch14_barrett.kv   163    begin
ffa_ch14_barrett.kv   164       
ffa_ch14_barrett.kv   165       if L <= Low_Mul_Thresh then
ffa_ch14_barrett.kv   166          
ffa_ch14_barrett.kv   167          -- Base case:
ffa_ch14_barrett.kv   168          FZ_Low_Mul_Comba(X, Y, XY);
ffa_ch14_barrett.kv   169          
ffa_ch14_barrett.kv   170       else
ffa_ch14_barrett.kv   171          
ffa_ch14_barrett.kv   172          -- Recursive case:
ffa_ch14_barrett.kv   173          Low_Mul(X, Y, XY);
ffa_ch14_barrett.kv   174          
ffa_ch14_barrett.kv   175       end if;
ffa_ch14_barrett.kv   176       
ffa_ch14_barrett.kv   177    end FZ_Low_Multiply_Unbuffered;
ffa_ch14_barrett.kv   178    
ffa_ch15_gcd.kv       179    
ffa_ch15_gcd.kv       180    -- Low-Only Multiplier. Preserves the inputs.
ffa_ch15_gcd.kv       181    procedure FZ_Low_Multiply_Buffered(X     : in  FZ;
ffa_ch15_gcd.kv       182                                       Y     : in  FZ;
ffa_ch15_gcd.kv       183                                       XY    : out FZ) is
ffa_ch15_gcd.kv       184       
ffa_ch15_gcd.kv       185       -- Product buffer.
ffa_ch15_gcd.kv       186       P : FZ(1 .. X'Length);
ffa_ch15_gcd.kv       187       
ffa_ch15_gcd.kv       188    begin
ffa_ch15_gcd.kv       189       
ffa_ch15_gcd.kv       190       FZ_Low_Multiply_Unbuffered(X, Y, P);
ffa_ch15_gcd.kv       191       
ffa_ch15_gcd.kv       192       XY := P;
ffa_ch15_gcd.kv       193       
ffa_ch15_gcd.kv       194    end FZ_Low_Multiply_Buffered;
ffa_ch15_gcd.kv       195    
ffa_ch14_barrett.kv   196 end FZ_LoMul;