raw
ffa_ch5_egypt.kv        1 ------------------------------------------------------------------------------
ffa_ch5_egypt.kv        2 ------------------------------------------------------------------------------
ffa_ch5_egypt.kv        3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
ffa_ch5_egypt.kv        4 --                                                                          --
ffa_ch5_egypt.kv        5 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org )                      --
ffa_ch5_egypt.kv        6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html     --
ffa_ch5_egypt.kv        7 --                                                                          --
ffa_ch5_egypt.kv        8 -- You do not have, nor can you ever acquire the right to use, copy or      --
ffa_ch5_egypt.kv        9 -- distribute this software ; Should you use this software for any purpose, --
ffa_ch5_egypt.kv       10 -- or copy and distribute it to anyone or in any manner, you are breaking   --
ffa_ch5_egypt.kv       11 -- the laws of whatever soi-disant jurisdiction, and you promise to         --
ffa_ch5_egypt.kv       12 -- continue doing so for the indefinite future. In any case, please         --
ffa_ch5_egypt.kv       13 -- always : read and understand any software ; verify any PGP signatures    --
ffa_ch5_egypt.kv       14 -- that you use - for any purpose.                                          --
ffa_ch5_egypt.kv       15 --                                                                          --
ffa_ch5_egypt.kv       16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     --
ffa_ch5_egypt.kv       17 ------------------------------------------------------------------------------
ffa_ch5_egypt.kv       18 ------------------------------------------------------------------------------
ffa_ch5_egypt.kv       19 
ffa_ch5_egypt.kv       20 with Words;    use Words;
ffa_ch9_exodus.kv      21 with Word_Ops; use Word_Ops;
ffa_ch9_exodus.kv      22 with W_Mul;    use W_Mul;
ffa_ch5_egypt.kv       23 
ffa_ch5_egypt.kv       24 
ffa_ch5_egypt.kv       25 package body FZ_Mul is
ffa_ch5_egypt.kv       26    
ffa_ch9_exodus.kv      27    -- Comba's multiplier.
ffa_ch9_exodus.kv      28    procedure FZ_Mul_Comba(X     : in  FZ;
ffa_ch9_exodus.kv      29                           Y     : in  FZ;
ffa_ch9_exodus.kv      30                           XY_Lo : out FZ;
ffa_ch9_exodus.kv      31                           XY_Hi : out FZ) is
ch9_asm_comba          32 
ch9_asm_comba          33       -- Words in each multiplicand
ch9_asm_comba          34       L : constant Word_Index := X'Length;
ch9_asm_comba          35 
ch9_asm_comba          36       -- Length of Product, i.e. double the length of either multiplicand
ch9_asm_comba          37       LP : constant Word_Index := 2 * L;
ch9_asm_comba          38 
ch9_asm_comba          39       -- Register holding Product; indexed from zero
ch9_asm_comba          40       XY : FZ(0 .. LP - 1);
ch9_asm_comba          41 
ch9_asm_comba          42       procedure Asm_Comba(X      : in  FZ;
ch9_asm_comba          43                           Y      : in  FZ;
ch9_asm_comba          44                           XY     : out FZ;
ch9_asm_comba          45                           X_Size : in  Word_Count);
ch9_asm_comba          46       pragma Import (C, Asm_Comba, "x86_64_comba");
ch9_asm_comba          47    begin
ch9_asm_comba          48       Asm_Comba(X, Y, XY, L);
ch9_asm_comba          49       XY_Lo := XY(0 .. L - 1);
ch9_asm_comba          50       XY_Hi := XY(L .. XY'Last);
ch9_asm_comba          51    end FZ_Mul_Comba;
ch9_asm_comba          52 
ch9_asm_comba          53    -- Comba's multiplier.
ch9_asm_comba          54    procedure FZ_Mul_Comba_C(X     : in  FZ;
ch9_asm_comba          55                             Y     : in  FZ;
ch9_asm_comba          56                             XY_Lo : out FZ;
ch9_asm_comba          57                             XY_Hi : out FZ) is
ffa_ch5_egypt.kv       58       
ffa_ch9_exodus.kv      59       -- Words in each multiplicand
ffa_ch9_exodus.kv      60       L : constant Word_Index := X'Length;
ffa_ch7_turbo_egy...   61       
ffa_ch9_exodus.kv      62       -- Length of Product, i.e. double the length of either multiplicand
ffa_ch9_exodus.kv      63       LP : constant Word_Index := 2 * L;
ffa_ch5_egypt.kv       64       
ffa_ch9_exodus.kv      65       -- 3-word Accumulator
ffa_ch9_exodus.kv      66       A2, A1, A0 : Word := 0;
ffa_ch9_exodus.kv      67       
ffa_ch9_exodus.kv      68       -- Register holding Product; indexed from zero
ffa_ch9_exodus.kv      69       XY : FZ(0 .. LP - 1);
ffa_ch9_exodus.kv      70       
ffa_ch9_exodus.kv      71       -- Type for referring to a column of XY
ffa_ch9_exodus.kv      72       subtype ColXY is Word_Index range XY'Range;
ffa_ch9_exodus.kv      73       
ffa_ch9_exodus.kv      74       -- Compute the Nth (indexed from zero) column of the Product
ffa_ch9_exodus.kv      75       procedure Col(N : in ColXY; U : in ColXY; V : in ColXY) is
ffa_ch9_exodus.kv      76          
ffa_ch9_exodus.kv      77          -- The outputs of a Word multiplication
ffa_ch9_exodus.kv      78          Lo, Hi : Word;
ffa_ch9_exodus.kv      79          
ffa_ch9_exodus.kv      80          -- Carry for the Accumulator addition
ffa_ch9_exodus.kv      81          C      : WBool;
ffa_ch9_exodus.kv      82          
ffa_ch9_exodus.kv      83          -- Sum for Accumulator addition
ffa_ch9_exodus.kv      84          Sum    : Word;
ffa_ch9_exodus.kv      85          
ffa_ch9_exodus.kv      86       begin
ffa_ch9_exodus.kv      87          
ffa_ch9_exodus.kv      88          -- For lower half of XY, will go from 0 to N
ffa_ch9_exodus.kv      89          -- For upper half of XY, will go from N - L + 1 to L - 1
ffa_ch9_exodus.kv      90          for j in U .. V loop
ffa_ch9_exodus.kv      91             
ffa_ch9_exodus.kv      92             -- Hi:Lo := j-th Word of X  *  (N - j)-th Word of Y
ffa_ch9_exodus.kv      93             Mul_Word(X(X'First + j),
ffa_ch9_exodus.kv      94                      Y(Y'First - j + N),
ffa_ch9_exodus.kv      95                      Lo, Hi);
ffa_ch9_exodus.kv      96             
ffa_ch9_exodus.kv      97             -- Now add Hi:Lo into the Accumulator:
ffa_ch9_exodus.kv      98             
ffa_ch9_exodus.kv      99             -- A0 += Lo; C := Carry
ffa_ch9_exodus.kv     100             Sum := A0 + Lo;
ffa_ch9_exodus.kv     101             C   := W_Carry(A0, Lo, Sum);
ffa_ch9_exodus.kv     102             A0  := Sum;
ffa_ch9_exodus.kv     103             
ffa_ch9_exodus.kv     104             -- A1 += Hi + C; C := Carry
ffa_ch9_exodus.kv     105             Sum := A1 + Hi + C;
ffa_ch9_exodus.kv     106             C   := W_Carry(A1, Hi, Sum);
ffa_ch9_exodus.kv     107             A1  := Sum;
ffa_ch9_exodus.kv     108             
ffa_ch9_exodus.kv     109             -- A2 += A2 + C
ffa_ch9_exodus.kv     110             A2  := A2 + C;
ffa_ch9_exodus.kv     111             
ffa_ch9_exodus.kv     112          end loop;
ffa_ch9_exodus.kv     113          
ffa_ch9_exodus.kv     114          -- We now have the Nth (indexed from zero) word of XY
ffa_ch9_exodus.kv     115          XY(N) := A0;
ffa_ch9_exodus.kv     116          
ffa_ch9_exodus.kv     117          -- Right-Shift the Accumulator by one Word width:
ffa_ch9_exodus.kv     118          A0 := A1;
ffa_ch9_exodus.kv     119          A1 := A2;
ffa_ch9_exodus.kv     120          A2 := 0;
ffa_ch9_exodus.kv     121          
ffa_ch9_exodus.kv     122       end Col;
ffa_ch9_exodus.kv     123       pragma Inline_Always(Col);
ffa_ch5_egypt.kv      124       
ffa_ch5_egypt.kv      125    begin
ffa_ch5_egypt.kv      126       
ffa_ch9_exodus.kv     127       -- Compute the lower half of the Product:
ffa_ch9_exodus.kv     128       for i in 0 .. L - 1 loop
ffa_ch9_exodus.kv     129          
ffa_ch9_exodus.kv     130          Col(i, 0, i);
ffa_ch9_exodus.kv     131          
ffa_ch9_exodus.kv     132       end loop;
ffa_ch9_exodus.kv     133       
ffa_ch9_exodus.kv     134       -- Compute the upper half (sans last Word) of the Product:
ffa_ch9_exodus.kv     135       for i in L .. LP - 2 loop
ffa_ch9_exodus.kv     136          
ffa_ch9_exodus.kv     137          Col(i, i - L + 1, L - 1);
ffa_ch5_egypt.kv      138          
ffa_ch5_egypt.kv      139       end loop;
ffa_ch5_egypt.kv      140       
ffa_ch9_exodus.kv     141       -- The very last Word of the Product:
ffa_ch9_exodus.kv     142       XY(XY'Last) := A0;
ffa_ch5_egypt.kv      143       
ffa_ch9_exodus.kv     144       -- Output the Product's lower and upper FZs:
ffa_ch9_exodus.kv     145       XY_Lo := XY(0 .. L - 1);
ffa_ch9_exodus.kv     146       XY_Hi := XY(L .. XY'Last);
ffa_ch9_exodus.kv     147       
ch9_asm_comba         148    end FZ_Mul_Comba_C;
ffa_ch9_exodus.kv     149    pragma Inline_Always(FZ_Mul_Comba);
ffa_ch9_exodus.kv     150    
ffa_ch5_egypt.kv      151 end FZ_Mul;