raw
ffa_ch13_measure_...    1 ------------------------------------------------------------------------------
ffa_ch13_measure_...    2 ------------------------------------------------------------------------------
ffa_ch13_measure_...    3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
ffa_ch13_measure_...    4 --                                                                          --
ffa_ch13_measure_...    5 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org )                      --
ffa_ch13_measure_...    6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html     --
ffa_ch13_measure_...    7 --                                                                          --
ffa_ch13_measure_...    8 -- You do not have, nor can you ever acquire the right to use, copy or      --
ffa_ch13_measure_...    9 -- distribute this software ; Should you use this software for any purpose, --
ffa_ch13_measure_...   10 -- or copy and distribute it to anyone or in any manner, you are breaking   --
ffa_ch13_measure_...   11 -- the laws of whatever soi-disant jurisdiction, and you promise to         --
ffa_ch13_measure_...   12 -- continue doing so for the indefinite future. In any case, please         --
ffa_ch13_measure_...   13 -- always : read and understand any software ; verify any PGP signatures    --
ffa_ch13_measure_...   14 -- that you use - for any purpose.                                          --
ffa_ch13_measure_...   15 --                                                                          --
ffa_ch13_measure_...   16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     --
ffa_ch13_measure_...   17 ------------------------------------------------------------------------------
ffa_ch13_measure_...   18 ------------------------------------------------------------------------------
ffa_ch13_measure_...   19 
ffa_ch13_measure_...   20 with Iron;     use Iron;
ffa_ch13_measure_...   21 with Word_Ops; use Word_Ops;
ffa_ch13_measure_...   22 with W_Pred;   use W_Pred;
ffa_ch13_measure_...   23 with W_Shifts; use W_Shifts;
ffa_ch13_measure_...   24 with FZ_Basic; use FZ_Basic;
ffa_ch13_measure_...   25 with FZ_Shift; use FZ_Shift;
ffa_ch13_measure_...   26 
ffa_ch13_measure_...   27 
ffa_ch13_measure_...   28 package body FZ_QShft is
ffa_ch13_measure_...   29    
ffa_ch13_measure_...   30    -- Constant-time subword shift, for where there is no barrel shifter
ffa_ch13_measure_...   31    procedure FZ_Quiet_ShiftRight_SubW_Soft(N        : in FZ;
ffa_ch13_measure_...   32                                            ShiftedN : in out FZ;
ffa_ch13_measure_...   33                                            Count    : in WBit_Index) is
ffa_ch13_measure_...   34       Nw  : constant Word  := Word(Count);
ffa_ch13_measure_...   35       nC  : constant WBool := W_ZeroP(Nw); -- 'no carry' for Count == 0 case
ffa_ch13_measure_...   36       Ni  : Word := 0; -- Current word
ffa_ch13_measure_...   37       C   : Word := 0; -- Current carry
ffa_ch13_measure_...   38       S   : Positive;  -- Current shiftness level
ffa_ch13_measure_...   39       B   : Word;      -- Quantity of shift (bitwalked over)
ffa_ch13_measure_...   40       CB  : Word;      -- Quantity of carry counter-shift (bitwalked over)
ffa_ch13_measure_...   41       St  : Word;      -- Temporary word shift candidate
ffa_ch13_measure_...   42       Ct  : Word;      -- Temporary carry counter-shift candidate
ffa_ch13_measure_...   43    begin
ffa_ch13_measure_...   44       for i in reverse N'Range loop
ffa_ch13_measure_...   45          Ni          := N(i);
ffa_ch13_measure_...   46          ShiftedN(i) := C;
ffa_ch13_measure_...   47          C           := W_Mux(Ni, 0, nC);
ffa_ch13_measure_...   48          S           := 1;
ffa_ch13_measure_...   49          B           := Nw;
ffa_ch13_measure_...   50          CB          := Word(Bitness) - B;
ffa_ch13_measure_...   51          -- For each shift level (of the subword shiftvalue width) :
ffa_ch13_measure_...   52          for j in 1 .. BitnessLog2 loop
ffa_ch13_measure_...   53             -- Shift and mux the current word
ffa_ch13_measure_...   54             St := Shift_Right(Ni, S);
ffa_ch13_measure_...   55             Ni := W_Mux(Ni, St, B and 1);
ffa_ch13_measure_...   56             -- Shift and mux the current carry
ffa_ch13_measure_...   57             Ct := Shift_Left(C, S);
ffa_ch13_measure_...   58             C  := W_Mux(C,  Ct, CB and 1);
ffa_ch13_measure_...   59             -- Go to the next shiftness level
ffa_ch13_measure_...   60             S  := S * 2;
ffa_ch13_measure_...   61             B  := Shift_Right(B,  1);
ffa_ch13_measure_...   62             CB := Shift_Right(CB, 1);
ffa_ch13_measure_...   63          end loop;
ffa_ch13_measure_...   64          -- Slide in the carry from the previous shift
ffa_ch13_measure_...   65          ShiftedN(i) := ShiftedN(i) or Ni;
ffa_ch13_measure_...   66       end loop;
ffa_ch13_measure_...   67    end FZ_Quiet_ShiftRight_SubW_Soft;
ffa_ch13_measure_...   68    
ffa_ch13_measure_...   69    
ffa_ch13_measure_...   70    -- Constant-time subword shift, for where there is no barrel shifter
ffa_ch13_measure_...   71    procedure FZ_Quiet_ShiftLeft_SubW_Soft(N        : in FZ;
ffa_ch13_measure_...   72                                           ShiftedN : in out FZ;
ffa_ch13_measure_...   73                                           Count    : in WBit_Index) is
ffa_ch13_measure_...   74       Nw  : constant Word  := Word(Count);
ffa_ch13_measure_...   75       nC  : constant WBool := W_ZeroP(Nw); -- 'no carry' for Count == 0 case
ffa_ch13_measure_...   76       Ni  : Word := 0; -- Current word
ffa_ch13_measure_...   77       C   : Word := 0; -- Current carry
ffa_ch13_measure_...   78       S   : Positive;  -- Current shiftness level
ffa_ch13_measure_...   79       B   : Word;      -- Quantity of shift (bitwalked over)
ffa_ch13_measure_...   80       CB  : Word;      -- Quantity of carry counter-shift (bitwalked over)
ffa_ch13_measure_...   81       St  : Word;      -- Temporary word shift candidate
ffa_ch13_measure_...   82       Ct  : Word;      -- Temporary carry counter-shift candidate
ffa_ch13_measure_...   83    begin
ffa_ch13_measure_...   84       for i in N'Range loop
ffa_ch13_measure_...   85          Ni          := N(i);
ffa_ch13_measure_...   86          ShiftedN(i) := C;
ffa_ch13_measure_...   87          C           := W_Mux(Ni, 0, nC);
ffa_ch13_measure_...   88          S           := 1;
ffa_ch13_measure_...   89          B           := Nw;
ffa_ch13_measure_...   90          CB          := Word(Bitness) - B;
ffa_ch13_measure_...   91          -- For each shift level (of the subword shiftvalue width) :
ffa_ch13_measure_...   92          for j in 1 .. BitnessLog2 loop
ffa_ch13_measure_...   93             -- Shift and mux the current word
ffa_ch13_measure_...   94             St := Shift_Left(Ni, S);
ffa_ch13_measure_...   95             Ni := W_Mux(Ni, St, B and 1);
ffa_ch13_measure_...   96             -- Shift and mux the current carry
ffa_ch13_measure_...   97             Ct := Shift_Right(C, S);
ffa_ch13_measure_...   98             C  := W_Mux(C,  Ct, CB and 1);
ffa_ch13_measure_...   99             -- Go to the next shiftness level
ffa_ch13_measure_...  100             S  := S * 2;
ffa_ch13_measure_...  101             B  := Shift_Right(B,  1);
ffa_ch13_measure_...  102             CB := Shift_Right(CB, 1);
ffa_ch13_measure_...  103          end loop;
ffa_ch13_measure_...  104          -- Slide in the carry from the previous shift
ffa_ch13_measure_...  105          ShiftedN(i) := ShiftedN(i) or Ni;
ffa_ch13_measure_...  106       end loop;
ffa_ch13_measure_...  107    end FZ_Quiet_ShiftLeft_SubW_Soft;
ffa_ch13_measure_...  108    
ffa_ch13_measure_...  109    
ffa_ch13_measure_...  110    -- Constant-time arbitrary Right-Shift.
ffa_ch13_measure_...  111    procedure FZ_Quiet_ShiftRight(N        : in     FZ;
ffa_ch13_measure_...  112                                  ShiftedN : in out FZ;
ffa_ch13_measure_...  113                                  Count    : in     FZBit_Index) is
ffa_ch13_measure_...  114       
ffa_ch13_measure_...  115       -- Total number of bit positions to shift by
ffa_ch13_measure_...  116       C     : constant Word     := Word(Count);
ffa_ch13_measure_...  117       
ffa_ch13_measure_...  118       -- Number of sub-Word bit positions to shift by
ffa_ch13_measure_...  119       Bits  : constant Natural  := Natural(C and (2**BitnessLog2 - 1));
ffa_ch13_measure_...  120       
ffa_ch13_measure_...  121       -- The Bitness of N's Length
ffa_ch13_measure_...  122       Wb    : constant Positive := FZ_Bitness_Log2(N);
ffa_ch13_measure_...  123       
ffa_ch13_measure_...  124       -- Number of whole-Word bitnesses to shift by
ffa_ch13_measure_...  125       Words : Word              := Shift_Right(C, BitnessLog2);
ffa_ch13_measure_...  126       
ffa_ch13_measure_...  127       -- Current 'shiftness level'
ffa_ch13_measure_...  128       S     : Indices           := 1;
ffa_ch13_measure_...  129       
ffa_ch13_measure_...  130    begin
ffa_ch13_measure_...  131       
ffa_ch13_measure_...  132       -- Subword shift first:
ffa_ch13_measure_...  133       if HaveBarrelShifter then
ffa_ch13_measure_...  134          -- If permitted, use iron shifter:
ffa_ch13_measure_...  135          FZ_ShiftRight(N, ShiftedN, Bits);
ffa_ch13_measure_...  136       else
ffa_ch13_measure_...  137          -- Otherwise, use the soft subword shifter:
ffa_ch13_measure_...  138          FZ_Quiet_ShiftRight_SubW_Soft(N, ShiftedN, Bits);
ffa_ch13_measure_...  139       end if;
ffa_ch13_measure_...  140       
ffa_ch13_measure_...  141       -- Then whole-Word shift:
ffa_ch13_measure_...  142       for i in 1 .. Wb loop
ffa_ch13_measure_...  143          
ffa_ch13_measure_...  144          declare
ffa_ch13_measure_...  145             
ffa_ch13_measure_...  146             -- Current bit of Words
ffa_ch13_measure_...  147             WordsBit : constant WBool := Words and 1;
ffa_ch13_measure_...  148             
ffa_ch13_measure_...  149          begin
ffa_ch13_measure_...  150             
ffa_ch13_measure_...  151             -- Shift at the current shiftness
ffa_ch13_measure_...  152             for i in ShiftedN'First        .. ShiftedN'Last - S loop
ffa_ch13_measure_...  153                ShiftedN(i) := W_Mux(ShiftedN(i), ShiftedN(i + S), WordsBit);
ffa_ch13_measure_...  154             end loop;
ffa_ch13_measure_...  155             
ffa_ch13_measure_...  156             -- Fill the emptiness
ffa_ch13_measure_...  157             for i in ShiftedN'Last - S + 1 .. ShiftedN'Last loop
ffa_ch13_measure_...  158                ShiftedN(i) := W_Mux(ShiftedN(i), 0,               WordsBit);
ffa_ch13_measure_...  159             end loop;
ffa_ch13_measure_...  160             
ffa_ch13_measure_...  161             -- Go to the next shiftness level
ffa_ch13_measure_...  162             S     := S * 2;
ffa_ch13_measure_...  163             Words := Shift_Right(Words, 1);
ffa_ch13_measure_...  164             
ffa_ch13_measure_...  165          end;
ffa_ch13_measure_...  166          
ffa_ch13_measure_...  167       end loop;
ffa_ch13_measure_...  168       
ffa_ch13_measure_...  169    end FZ_Quiet_ShiftRight;
ffa_ch13_measure_...  170    
ffa_ch13_measure_...  171    
ffa_ch13_measure_...  172    -- Constant-time arbitrary Left-Shift.
ffa_ch13_measure_...  173    procedure FZ_Quiet_ShiftLeft(N        : in     FZ;
ffa_ch13_measure_...  174                                 ShiftedN : in out FZ;
ffa_ch13_measure_...  175                                 Count    : in     FZBit_Index) is
ffa_ch13_measure_...  176       
ffa_ch13_measure_...  177       -- Total number of bit positions to shift by
ffa_ch13_measure_...  178       C     : constant Word     := Word(Count);
ffa_ch13_measure_...  179       
ffa_ch13_measure_...  180       -- Number of sub-Word bit positions to shift by
ffa_ch13_measure_...  181       Bits  : constant Natural  := Natural(C and (2**BitnessLog2 - 1));
ffa_ch13_measure_...  182       
ffa_ch13_measure_...  183       -- The Bitness of N's Length
ffa_ch13_measure_...  184       Wb    : constant Positive := FZ_Bitness_Log2(N);
ffa_ch13_measure_...  185       
ffa_ch13_measure_...  186       -- Number of whole-Word bitnesses to shift by
ffa_ch13_measure_...  187       Words : Word              := Shift_Right(C, BitnessLog2);
ffa_ch13_measure_...  188       
ffa_ch13_measure_...  189       -- Current 'shiftness level'
ffa_ch13_measure_...  190       S     : Indices           := 1;
ffa_ch13_measure_...  191       
ffa_ch13_measure_...  192    begin
ffa_ch13_measure_...  193       
ffa_ch13_measure_...  194       -- Subword shift first:
ffa_ch13_measure_...  195       if HaveBarrelShifter then
ffa_ch13_measure_...  196          -- If permitted, use iron shifter:
ffa_ch13_measure_...  197          FZ_ShiftLeft(N, ShiftedN, Bits);
ffa_ch13_measure_...  198       else
ffa_ch13_measure_...  199          -- Otherwise, use the soft subword shifter:
ffa_ch13_measure_...  200          FZ_Quiet_ShiftLeft_SubW_Soft(N, ShiftedN, Bits);
ffa_ch13_measure_...  201       end if;
ffa_ch13_measure_...  202       
ffa_ch13_measure_...  203       -- Then whole-Word shift:
ffa_ch13_measure_...  204       for i in 1 .. Wb loop
ffa_ch13_measure_...  205          
ffa_ch13_measure_...  206          declare
ffa_ch13_measure_...  207             
ffa_ch13_measure_...  208             -- Current bit of Words
ffa_ch13_measure_...  209             WordsBit : constant WBool := Words and 1;
ffa_ch13_measure_...  210             
ffa_ch13_measure_...  211          begin
ffa_ch13_measure_...  212             
ffa_ch13_measure_...  213             -- Shift at the current shiftness
ffa_ch13_measure_...  214             for i in reverse ShiftedN'First + S .. ShiftedN'Last loop
ffa_ch13_measure_...  215                ShiftedN(i) := W_Mux(ShiftedN(i), ShiftedN(i - S), WordsBit);
ffa_ch13_measure_...  216             end loop;
ffa_ch13_measure_...  217             
ffa_ch13_measure_...  218             -- Fill the emptiness
ffa_ch13_measure_...  219             for i in ShiftedN'First             .. ShiftedN'First + S - 1 loop
ffa_ch13_measure_...  220                ShiftedN(i) := W_Mux(ShiftedN(i), 0,               WordsBit);
ffa_ch13_measure_...  221             end loop;
ffa_ch13_measure_...  222             
ffa_ch13_measure_...  223             -- Go to the next shiftness level
ffa_ch13_measure_...  224             S     := S * 2;
ffa_ch13_measure_...  225             Words := Shift_Right(Words, 1);
ffa_ch13_measure_...  226             
ffa_ch13_measure_...  227          end;
ffa_ch13_measure_...  228          
ffa_ch13_measure_...  229       end loop;
ffa_ch13_measure_...  230       
ffa_ch13_measure_...  231    end FZ_Quiet_ShiftLeft;
ffa_ch13_measure_...  232    
ffa_ch13_measure_...  233 end FZ_QShft;