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;