Finite Field Arithmetic

fz_qshft.adb


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