------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. -- -- -- -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) -- -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html -- -- -- -- You do not have, nor can you ever acquire the right to use, copy or -- -- distribute this software ; Should you use this software for any purpose, -- -- or copy and distribute it to anyone or in any manner, you are breaking -- -- the laws of whatever soi-disant jurisdiction, and you promise to -- -- continue doing so for the indefinite future. In any case, please -- -- always : read and understand any software ; verify any PGP signatures -- -- that you use - for any purpose. -- -- -- -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . -- ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ with Iron; use Iron; with Word_Ops; use Word_Ops; with W_Pred; use W_Pred; with W_Shifts; use W_Shifts; with FZ_Basic; use FZ_Basic; with FZ_Shift; use FZ_Shift; package body FZ_QShft is -- Constant-time subword shift, for where there is no barrel shifter procedure FZ_Quiet_ShiftRight_SubW_Soft(N : in FZ; ShiftedN : in out FZ; Count : in WBit_Index) is Nw : constant Word := Word(Count); nC : constant WBool := W_ZeroP(Nw); -- 'no carry' for Count == 0 case Ni : Word := 0; -- Current word C : Word := 0; -- Current carry S : Positive; -- Current shiftness level B : Word; -- Quantity of shift (bitwalked over) CB : Word; -- Quantity of carry counter-shift (bitwalked over) St : Word; -- Temporary word shift candidate Ct : Word; -- Temporary carry counter-shift candidate begin for i in reverse N'Range loop Ni := N(i); ShiftedN(i) := C; C := W_Mux(Ni, 0, nC); S := 1; B := Nw; CB := Word(Bitness) - B; -- For each shift level (of the subword shiftvalue width) : for j in 1 .. BitnessLog2 loop -- Shift and mux the current word St := Shift_Right(Ni, S); Ni := W_Mux(Ni, St, B and 1); -- Shift and mux the current carry Ct := Shift_Left(C, S); C := W_Mux(C, Ct, CB and 1); -- Go to the next shiftness level S := S * 2; B := Shift_Right(B, 1); CB := Shift_Right(CB, 1); end loop; -- Slide in the carry from the previous shift ShiftedN(i) := ShiftedN(i) or Ni; end loop; end FZ_Quiet_ShiftRight_SubW_Soft; -- Constant-time subword shift, for where there is no barrel shifter procedure FZ_Quiet_ShiftLeft_SubW_Soft(N : in FZ; ShiftedN : in out FZ; Count : in WBit_Index) is Nw : constant Word := Word(Count); nC : constant WBool := W_ZeroP(Nw); -- 'no carry' for Count == 0 case Ni : Word := 0; -- Current word C : Word := 0; -- Current carry S : Positive; -- Current shiftness level B : Word; -- Quantity of shift (bitwalked over) CB : Word; -- Quantity of carry counter-shift (bitwalked over) St : Word; -- Temporary word shift candidate Ct : Word; -- Temporary carry counter-shift candidate begin for i in N'Range loop Ni := N(i); ShiftedN(i) := C; C := W_Mux(Ni, 0, nC); S := 1; B := Nw; CB := Word(Bitness) - B; -- For each shift level (of the subword shiftvalue width) : for j in 1 .. BitnessLog2 loop -- Shift and mux the current word St := Shift_Left(Ni, S); Ni := W_Mux(Ni, St, B and 1); -- Shift and mux the current carry Ct := Shift_Right(C, S); C := W_Mux(C, Ct, CB and 1); -- Go to the next shiftness level S := S * 2; B := Shift_Right(B, 1); CB := Shift_Right(CB, 1); end loop; -- Slide in the carry from the previous shift ShiftedN(i) := ShiftedN(i) or Ni; end loop; end FZ_Quiet_ShiftLeft_SubW_Soft; -- Constant-time arbitrary Right-Shift. procedure FZ_Quiet_ShiftRight(N : in FZ; ShiftedN : in out FZ; Count : in FZBit_Index) is -- Total number of bit positions to shift by C : constant Word := Word(Count); -- Number of sub-Word bit positions to shift by Bits : constant Natural := Natural(C and (2**BitnessLog2 - 1)); -- The Bitness of N's Length Wb : constant Positive := FZ_Bitness_Log2(N); -- Number of whole-Word bitnesses to shift by Words : Word := Shift_Right(C, BitnessLog2); -- Current 'shiftness level' S : Indices := 1; begin -- Subword shift first: if HaveBarrelShifter then -- If permitted, use iron shifter: FZ_ShiftRight(N, ShiftedN, Bits); else -- Otherwise, use the soft subword shifter: FZ_Quiet_ShiftRight_SubW_Soft(N, ShiftedN, Bits); end if; -- Then whole-Word shift: for i in 1 .. Wb loop declare -- Current bit of Words WordsBit : constant WBool := Words and 1; begin -- Shift at the current shiftness for i in ShiftedN'First .. ShiftedN'Last - S loop ShiftedN(i) := W_Mux(ShiftedN(i), ShiftedN(i + S), WordsBit); end loop; -- Fill the emptiness for i in ShiftedN'Last - S + 1 .. ShiftedN'Last loop ShiftedN(i) := W_Mux(ShiftedN(i), 0, WordsBit); end loop; -- Go to the next shiftness level S := S * 2; Words := Shift_Right(Words, 1); end; end loop; end FZ_Quiet_ShiftRight; -- Constant-time arbitrary Left-Shift. procedure FZ_Quiet_ShiftLeft(N : in FZ; ShiftedN : in out FZ; Count : in FZBit_Index) is -- Total number of bit positions to shift by C : constant Word := Word(Count); -- Number of sub-Word bit positions to shift by Bits : constant Natural := Natural(C and (2**BitnessLog2 - 1)); -- The Bitness of N's Length Wb : constant Positive := FZ_Bitness_Log2(N); -- Number of whole-Word bitnesses to shift by Words : Word := Shift_Right(C, BitnessLog2); -- Current 'shiftness level' S : Indices := 1; begin -- Subword shift first: if HaveBarrelShifter then -- If permitted, use iron shifter: FZ_ShiftLeft(N, ShiftedN, Bits); else -- Otherwise, use the soft subword shifter: FZ_Quiet_ShiftLeft_SubW_Soft(N, ShiftedN, Bits); end if; -- Then whole-Word shift: for i in 1 .. Wb loop declare -- Current bit of Words WordsBit : constant WBool := Words and 1; begin -- Shift at the current shiftness for i in reverse ShiftedN'First + S .. ShiftedN'Last loop ShiftedN(i) := W_Mux(ShiftedN(i), ShiftedN(i - S), WordsBit); end loop; -- Fill the emptiness for i in ShiftedN'First .. ShiftedN'First + S - 1 loop ShiftedN(i) := W_Mux(ShiftedN(i), 0, WordsBit); end loop; -- Go to the next shiftness level S := S * 2; Words := Shift_Right(Words, 1); end; end loop; end FZ_Quiet_ShiftLeft; end FZ_QShft;