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
ffa_ch5_egypt.kv       32       
ffa_ch9_exodus.kv      33       -- Words in each multiplicand
ffa_ch9_exodus.kv      34       L : constant Word_Index := X'Length;
ffa_ch7_turbo_egy...   35       
ffa_ch9_exodus.kv      36       -- Length of Product, i.e. double the length of either multiplicand
ffa_ch9_exodus.kv      37       LP : constant Word_Index := 2 * L;
ffa_ch5_egypt.kv       38       
ffa_ch9_exodus.kv      39       -- 3-word Accumulator
ffa_ch9_exodus.kv      40       A2, A1, A0 : Word := 0;
ffa_ch9_exodus.kv      41       
ffa_ch9_exodus.kv      42       -- Register holding Product; indexed from zero
ffa_ch9_exodus.kv      43       XY : FZ(0 .. LP - 1);
ffa_ch9_exodus.kv      44       
ffa_ch9_exodus.kv      45       -- Type for referring to a column of XY
ffa_ch9_exodus.kv      46       subtype ColXY is Word_Index range XY'Range;
ffa_ch9_exodus.kv      47       
ffa_ch9_exodus.kv      48       -- Compute the Nth (indexed from zero) column of the Product
ffa_ch9_exodus.kv      49       procedure Col(N : in ColXY; U : in ColXY; V : in ColXY) is
ffa_ch9_exodus.kv      50          
ffa_ch9_exodus.kv      51          -- The outputs of a Word multiplication
ffa_ch9_exodus.kv      52          Lo, Hi : Word;
ffa_ch9_exodus.kv      53          
ffa_ch9_exodus.kv      54          -- Carry for the Accumulator addition
ffa_ch9_exodus.kv      55          C      : WBool;
ffa_ch9_exodus.kv      56          
ffa_ch9_exodus.kv      57          -- Sum for Accumulator addition
ffa_ch9_exodus.kv      58          Sum    : Word;
ffa_ch9_exodus.kv      59          
ffa_ch9_exodus.kv      60       begin
ffa_ch9_exodus.kv      61          
ffa_ch9_exodus.kv      62          -- For lower half of XY, will go from 0 to N
ffa_ch9_exodus.kv      63          -- For upper half of XY, will go from N - L + 1 to L - 1
ffa_ch9_exodus.kv      64          for j in U .. V loop
ffa_ch9_exodus.kv      65             
ffa_ch9_exodus.kv      66             -- Hi:Lo := j-th Word of X  *  (N - j)-th Word of Y
ffa_ch9_exodus.kv      67             Mul_Word(X(X'First + j),
ffa_ch9_exodus.kv      68                      Y(Y'First - j + N),
ffa_ch9_exodus.kv      69                      Lo, Hi);
ffa_ch9_exodus.kv      70             
ffa_ch9_exodus.kv      71             -- Now add Hi:Lo into the Accumulator:
ffa_ch9_exodus.kv      72             
ffa_ch9_exodus.kv      73             -- A0 += Lo; C := Carry
ffa_ch9_exodus.kv      74             Sum := A0 + Lo;
ffa_ch9_exodus.kv      75             C   := W_Carry(A0, Lo, Sum);
ffa_ch9_exodus.kv      76             A0  := Sum;
ffa_ch9_exodus.kv      77             
ffa_ch9_exodus.kv      78             -- A1 += Hi + C; C := Carry
ffa_ch9_exodus.kv      79             Sum := A1 + Hi + C;
ffa_ch9_exodus.kv      80             C   := W_Carry(A1, Hi, Sum);
ffa_ch9_exodus.kv      81             A1  := Sum;
ffa_ch9_exodus.kv      82             
ffa_ch9_exodus.kv      83             -- A2 += A2 + C
ffa_ch9_exodus.kv      84             A2  := A2 + C;
ffa_ch9_exodus.kv      85             
ffa_ch9_exodus.kv      86          end loop;
ffa_ch9_exodus.kv      87          
ffa_ch9_exodus.kv      88          -- We now have the Nth (indexed from zero) word of XY
ffa_ch9_exodus.kv      89          XY(N) := A0;
ffa_ch9_exodus.kv      90          
ffa_ch9_exodus.kv      91          -- Right-Shift the Accumulator by one Word width:
ffa_ch9_exodus.kv      92          A0 := A1;
ffa_ch9_exodus.kv      93          A1 := A2;
ffa_ch9_exodus.kv      94          A2 := 0;
ffa_ch9_exodus.kv      95          
ffa_ch9_exodus.kv      96       end Col;
ffa_ch9_exodus.kv      97       pragma Inline_Always(Col);
ffa_ch5_egypt.kv       98       
ffa_ch5_egypt.kv       99    begin
ffa_ch5_egypt.kv      100       
ffa_ch9_exodus.kv     101       -- Compute the lower half of the Product:
ffa_ch9_exodus.kv     102       for i in 0 .. L - 1 loop
ffa_ch9_exodus.kv     103          
ffa_ch9_exodus.kv     104          Col(i, 0, i);
ffa_ch9_exodus.kv     105          
ffa_ch9_exodus.kv     106       end loop;
ffa_ch9_exodus.kv     107       
ffa_ch9_exodus.kv     108       -- Compute the upper half (sans last Word) of the Product:
ffa_ch9_exodus.kv     109       for i in L .. LP - 2 loop
ffa_ch9_exodus.kv     110          
ffa_ch9_exodus.kv     111          Col(i, i - L + 1, L - 1);
ffa_ch5_egypt.kv      112          
ffa_ch5_egypt.kv      113       end loop;
ffa_ch5_egypt.kv      114       
ffa_ch9_exodus.kv     115       -- The very last Word of the Product:
ffa_ch9_exodus.kv     116       XY(XY'Last) := A0;
ffa_ch5_egypt.kv      117       
ffa_ch9_exodus.kv     118       -- Output the Product's lower and upper FZs:
ffa_ch9_exodus.kv     119       XY_Lo := XY(0 .. L - 1);
ffa_ch9_exodus.kv     120       XY_Hi := XY(L .. XY'Last);
ffa_ch9_exodus.kv     121       
ffa_ch9_exodus.kv     122    end FZ_Mul_Comba;
ffa_ch9_exodus.kv     123    pragma Inline_Always(FZ_Mul_Comba);
ffa_ch9_exodus.kv     124    
ffa_ch5_egypt.kv      125 end FZ_Mul;