raw
ffa_ch9_exodus.kv       1 ------------------------------------------------------------------------------
ffa_ch9_exodus.kv       2 ------------------------------------------------------------------------------
ffa_ch9_exodus.kv       3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
ffa_ch9_exodus.kv       4 --                                                                          --
ffa_ch15_gcd.kv         5 -- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org )                      --
ffa_ch9_exodus.kv       6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html     --
ffa_ch9_exodus.kv       7 --                                                                          --
ffa_ch9_exodus.kv       8 -- You do not have, nor can you ever acquire the right to use, copy or      --
ffa_ch9_exodus.kv       9 -- distribute this software ; Should you use this software for any purpose, --
ffa_ch9_exodus.kv      10 -- or copy and distribute it to anyone or in any manner, you are breaking   --
ffa_ch9_exodus.kv      11 -- the laws of whatever soi-disant jurisdiction, and you promise to         --
ffa_ch9_exodus.kv      12 -- continue doing so for the indefinite future. In any case, please         --
ffa_ch9_exodus.kv      13 -- always : read and understand any software ; verify any PGP signatures    --
ffa_ch9_exodus.kv      14 -- that you use - for any purpose.                                          --
ffa_ch9_exodus.kv      15 --                                                                          --
ffa_ch9_exodus.kv      16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     --
ffa_ch9_exodus.kv      17 ------------------------------------------------------------------------------
ffa_ch9_exodus.kv      18 ------------------------------------------------------------------------------
ffa_ch9_exodus.kv      19 
ffa_ch9_exodus.kv      20 with W_Shifts; use W_Shifts;
ffa_ch9_exodus.kv      21 
ffa_ch9_exodus.kv      22 
ffa_ch9_exodus.kv      23 package body W_Mul is
ffa_ch9_exodus.kv      24    
ffa_ch10_karatsub...   25    function Mul_HalfWord_Iron(X : in HalfWord;
ffa_ch10_karatsub...   26                               Y : in HalfWord) return Word is
ffa_ch10_karatsub...   27    begin
ffa_ch10_karatsub...   28       return X * Y;
ffa_ch10_karatsub...   29    end Mul_HalfWord_Iron;
ffa_ch10_karatsub...   30    
ffa_ch10_karatsub...   31    
ffa_ch9_exodus.kv      32    -- Multiply half-words X and Y, producing a Word-sized product
ffa_ch10_karatsub...   33    function Mul_HalfWord_Soft(X : in HalfWord; Y : in HalfWord) return Word is
ffa_ch9_exodus.kv      34       
ffa_ch9_exodus.kv      35       -- X-Slide
ffa_ch9_exodus.kv      36       XS : Word := X;
ffa_ch9_exodus.kv      37       
ffa_ch9_exodus.kv      38       -- Y-Slide
ffa_ch9_exodus.kv      39       YS : Word := Y;
ffa_ch9_exodus.kv      40       
ffa_ch9_exodus.kv      41       -- Gate Mask
ffa_ch9_exodus.kv      42       GM : Word;
ffa_ch9_exodus.kv      43       
ffa_ch9_exodus.kv      44       -- The Product
ffa_ch9_exodus.kv      45       XY : Word := 0;
ffa_ch9_exodus.kv      46       
ffa_ch9_exodus.kv      47       -- Performed for each bit of HalfWord's bitness:
ffa_ch9_exodus.kv      48       procedure Bit is
ffa_ch9_exodus.kv      49       begin
ffa_ch9_exodus.kv      50          
ffa_ch9_exodus.kv      51          -- Compute the gate mask
ffa_ch9_exodus.kv      52          GM := 0 - (YS and 1);
ffa_ch9_exodus.kv      53          
ffa_ch9_exodus.kv      54          -- Perform the gated addition
ffa_ch9_exodus.kv      55          XY := XY + (XS and GM);
ffa_ch9_exodus.kv      56          
ffa_ch9_exodus.kv      57          -- Crank the next Y-slide bit into position
ffa_ch9_exodus.kv      58          YS := Shift_Right(YS, 1);
ffa_ch9_exodus.kv      59          
ffa_ch9_exodus.kv      60          -- Advance the X-slide by 1 bit
ffa_ch9_exodus.kv      61          XS := Shift_Left(XS, 1);
ffa_ch9_exodus.kv      62          
ffa_ch9_exodus.kv      63       end Bit;
ffa_ch9_exodus.kv      64       
ffa_ch9_exodus.kv      65    begin
ffa_ch9_exodus.kv      66       
ffa_ch9_exodus.kv      67       -- For each bit of the Y-Slide (unrolled) :
ffa_ch9_exodus.kv      68       for b in 1 .. HalfByteness loop
ffa_ch9_exodus.kv      69          
ffa_ch9_exodus.kv      70          Bit; Bit; Bit; Bit; Bit; Bit; Bit; Bit;
ffa_ch9_exodus.kv      71          
ffa_ch9_exodus.kv      72       end loop;
ffa_ch9_exodus.kv      73       
ffa_ch9_exodus.kv      74       -- Return the Product
ffa_ch9_exodus.kv      75       return XY;
ffa_ch9_exodus.kv      76       
ffa_ch10_karatsub...   77    end Mul_HalfWord_Soft;
ffa_ch9_exodus.kv      78    
ffa_ch9_exodus.kv      79    
ffa_ch9_exodus.kv      80    -- Get the bottom half of a Word
ffa_ch9_exodus.kv      81    function BottomHW(W : in Word) return HalfWord is
ffa_ch9_exodus.kv      82    begin
ffa_ch9_exodus.kv      83       return W and (2**HalfBitness - 1);
ffa_ch9_exodus.kv      84    end BottomHW;
ffa_ch9_exodus.kv      85    
ffa_ch9_exodus.kv      86    
ffa_ch9_exodus.kv      87    -- Get the top half of a Word
ffa_ch9_exodus.kv      88    function TopHW(W : in Word) return HalfWord is
ffa_ch9_exodus.kv      89    begin
ffa_ch9_exodus.kv      90       return Shift_Right(W, HalfBitness);
ffa_ch9_exodus.kv      91    end TopHW;
ffa_ch9_exodus.kv      92    
ffa_ch9_exodus.kv      93    
ffa_ch9_exodus.kv      94    -- Carry out X*Y mult, return lower word XY_LW and upper word XY_HW.
ffa_ch9_exodus.kv      95    procedure Mul_Word(X       : in  Word;
ffa_ch9_exodus.kv      96                       Y       : in  Word;
ffa_ch9_exodus.kv      97                       XY_LW   : out Word;
ffa_ch9_exodus.kv      98                       XY_HW   : out Word) is
ffa_ch9_exodus.kv      99       
ffa_ch9_exodus.kv     100       -- Bottom half of multiplicand X
ffa_ch9_exodus.kv     101       XL : constant HalfWord := BottomHW(X);
ffa_ch9_exodus.kv     102       
ffa_ch9_exodus.kv     103       -- Top half of multiplicand X
ffa_ch9_exodus.kv     104       XH : constant HalfWord := TopHW(X);
ffa_ch9_exodus.kv     105       
ffa_ch9_exodus.kv     106       -- Bottom half of multiplicand Y
ffa_ch9_exodus.kv     107       YL : constant HalfWord := BottomHW(Y);
ffa_ch9_exodus.kv     108       
ffa_ch9_exodus.kv     109       -- Top half of multiplicand Y
ffa_ch9_exodus.kv     110       YH : constant HalfWord := TopHW(Y);
ffa_ch9_exodus.kv     111       
ffa_ch9_exodus.kv     112       -- XL * YL
ffa_ch10_karatsub...  113       LL : constant Word := Mul_HalfWord_Iron(XL, YL);
ffa_ch9_exodus.kv     114       
ffa_ch9_exodus.kv     115       -- XL * YH
ffa_ch10_karatsub...  116       LH : constant Word := Mul_HalfWord_Iron(XL, YH);
ffa_ch9_exodus.kv     117       
ffa_ch9_exodus.kv     118       -- XH * YL
ffa_ch10_karatsub...  119       HL : constant Word := Mul_HalfWord_Iron(XH, YL);
ffa_ch9_exodus.kv     120       
ffa_ch9_exodus.kv     121       -- XH * YH
ffa_ch10_karatsub...  122       HH : constant Word := Mul_HalfWord_Iron(XH, YH);
ffa_ch9_exodus.kv     123       
ffa_ch9_exodus.kv     124       -- Carry
ffa_ch9_exodus.kv     125       CL : constant Word := TopHW(TopHW(LL) + BottomHW(LH) + BottomHW(HL));
ffa_ch9_exodus.kv     126       
ffa_ch9_exodus.kv     127    begin
ffa_ch9_exodus.kv     128       
ffa_ch9_exodus.kv     129       -- Get the bottom half of the Product:
ffa_ch9_exodus.kv     130       XY_LW := LL + Shift_Left(LH + HL, HalfBitness);
ffa_ch9_exodus.kv     131       
ffa_ch9_exodus.kv     132       -- Get the top half of the Product:
ffa_ch9_exodus.kv     133       XY_HW := HH + TopHW(HL) + TopHW(LH) + CL;
ffa_ch9_exodus.kv     134       
ffa_ch9_exodus.kv     135    end Mul_Word;
ffa_ch9_exodus.kv     136    
ffa_ch12_karatsub...  137    ---------------------------------------------------------------------------
ffa_ch12_karatsub...  138    -- LET A CURSE FALL FOREVER on the authors of GCC, and on the Ada committee,
ffa_ch12_karatsub...  139    -- neither of whom saw it fit to decree a primitive which returns both
ffa_ch12_karatsub...  140    -- upper and lower halves of an iron MUL instruction's result. Consequently,
ffa_ch12_karatsub...  141    -- portable Mul_Word demands ~four~ MULs (and several additions and shifts);
ffa_ch12_karatsub...  142    -- while portable Sqr_Word demands ~three~ MULs (and likewise adds/shifts.)
ffa_ch12_karatsub...  143    -- If it were not for their idiocy, BOTH routines would weigh 1 CPU instr.!
ffa_ch12_karatsub...  144    ---------------------------------------------------------------------------
ffa_ch12_karatsub...  145    
ffa_ch12_karatsub...  146    -- Carry out X*X squaring, return lower word XX_LW and upper word XX_HW.
ffa_ch12_karatsub...  147    procedure Sqr_Word(X       : in  Word;
ffa_ch12_karatsub...  148                       XX_LW   : out Word;
ffa_ch12_karatsub...  149                       XX_HW   : out Word) is
ffa_ch12_karatsub...  150       
ffa_ch12_karatsub...  151       -- Bottom half of multiplicand X
ffa_ch12_karatsub...  152       XL : constant HalfWord := BottomHW(X);
ffa_ch12_karatsub...  153       
ffa_ch12_karatsub...  154       -- Top half of multiplicand X
ffa_ch12_karatsub...  155       XH : constant HalfWord := TopHW(X);
ffa_ch12_karatsub...  156       
ffa_ch12_karatsub...  157       -- XL^2
ffa_ch12_karatsub...  158       LL : constant Word := Mul_HalfWord_Iron(XL, XL);
ffa_ch12_karatsub...  159       
ffa_ch12_karatsub...  160       -- XL * XH
ffa_ch12_karatsub...  161       LH : constant Word := Mul_HalfWord_Iron(XL, XH);
ffa_ch12_karatsub...  162       
ffa_ch12_karatsub...  163       -- XH^2
ffa_ch12_karatsub...  164       HH : constant Word := Mul_HalfWord_Iron(XH, XH);
ffa_ch12_karatsub...  165       
ffa_ch12_karatsub...  166       -- Carry
ffa_ch12_karatsub...  167       CL : constant Word := TopHW(TopHW(LL) + Shift_Left(BottomHW(LH), 1));
ffa_ch12_karatsub...  168       
ffa_ch12_karatsub...  169    begin
ffa_ch12_karatsub...  170       
ffa_ch12_karatsub...  171       -- Get the bottom half of the Product:
ffa_ch12_karatsub...  172       XX_LW := LL + Shift_Left(LH, HalfBitness + 1);
ffa_ch12_karatsub...  173       
ffa_ch12_karatsub...  174       -- Get the top half of the Product:
ffa_ch12_karatsub...  175       XX_HW := HH + Shift_Left(TopHW(LH), 1) + CL;
ffa_ch12_karatsub...  176       
ffa_ch12_karatsub...  177    end Sqr_Word;
ffa_ch12_karatsub...  178    
ffa_ch9_exodus.kv     179 end W_Mul;