diff options
Diffstat (limited to 'src/crypto-types-big_numbers-utils.adb')
| -rw-r--r-- | src/crypto-types-big_numbers-utils.adb | 704 |
1 files changed, 704 insertions, 0 deletions
diff --git a/src/crypto-types-big_numbers-utils.adb b/src/crypto-types-big_numbers-utils.adb new file mode 100644 index 0000000..313ce9b --- /dev/null +++ b/src/crypto-types-big_numbers-utils.adb @@ -0,0 +1,704 @@ +-- This program is free software; you can redistribute it and/or +-- modify it under the terms of the GNU General Public License as +-- published by the Free Software Foundation; either version 2 of the +-- License, or (at your option) any later version. + +-- This program is distributed in the hope that it will be useful, +-- but WITHOUT ANY WARRANTY; without even the implied warranty of +-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +-- General Public License for more details. + +-- You should have received a copy of the GNU General Public License +-- along with this program; if not, write to the Free Software +-- Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA +-- 02111-1307, USA. + +-- As a special exception, if other files instantiate generics from +-- this unit, or you link this unit with other files to produce an +-- executable, this unit does not by itself cause the resulting +-- executable to be covered by the GNU General Public License. This +-- exception does not however invalidate any other reasons why the +-- executable file might be covered by the GNU Public License. + +--with Ada.Integer_Text_IO; +--with Ada.Strings.Unbounded.Text_IO; +with Crypto.Types.Random; + +SEPARATE(Crypto.Types.Big_Numbers) + +package body Utils is + + pragma Optimize (Time); + + --------------------------------------------------------------------------- + + procedure Swap(X, Y : in out Big_Unsigned) is + Temp : constant Big_Unsigned := X; + begin + X := Y; + Y := Temp; + end Swap; pragma Inline (Swap); + + --------------------------------------------------------------------------- + + procedure Set_Least_Significant_Bit(X : in out Big_Unsigned) is + begin + X.Number(0) := X.Number(0) or 1; + end Set_Least_Significant_Bit; pragma Inline(Set_Least_Significant_Bit); + + --------------------------------------------------------------------------- + + function Is_Odd(X : Big_Unsigned) return Boolean is + begin + if (X.Number(0) and 1) = 1 then return True; + else return False; + end if; + end Is_Odd; pragma Inline(Is_Odd); + + --------------------------------------------------------------------------- + + function Is_Even(X : Big_Unsigned) return Boolean is + begin + if (X.Number(0) and 1) = 0 then return True; + else return False; + end if; + end Is_Even; pragma Inline(Is_Even); + + --------------------------------------------------------------------------- + + procedure Set_Most_Significant_Bit(X : in out Big_Unsigned) is + begin + X.Last_Index := Max_Length; + X.Number(Max_Length) := X.Number(Max_Length) or + Shift_Left(Word(1), Word'Size-1); + end Set_Most_Significant_Bit; pragma Inline(Set_Most_Significant_Bit); + + + --------------------------------------------------------------------------- + + function Bit_Length(X : Big_Unsigned) return Natural is + begin + if X = Big_Unsigned_Zero then + return 0; + end if; + + for I in reverse 0..Word'Size-1 loop + if Shift_Left(1,I) <= X.Number(X.Last_Index) then + return Word'Size * X.Last_Index + I + 1 ; + end if; + end loop; + return X.Last_Index * Word'Size; + end Bit_Length; pragma Inline(Bit_Length); + + --------------------------------------------------------------------------- + + function Lowest_Set_Bit(X : Big_Unsigned) return Natural is + begin + if X = Big_Unsigned_Zero then + raise Is_Zero_Error; + end if; + + for I in 0..X.Last_Index loop + if X.Number(I) /= 0 then + for J in 0..Word'Size-1 loop + if (Shift_Right(X.Number(I),J) and 1) = 1 then + return I*Word'Size+J+1; + end if; + end loop; + end if; + end loop; + return Size+1; --X = Big_unsgned_Zero = 2**(Size+1) + end Lowest_Set_Bit; pragma Inline (Lowest_Set_Bit); + + + --------------------------------------------------------------------------- + + + procedure Inc(X : in out Big_Unsigned) is + begin + if X = Big_Unsigned_Last then + X := Big_Unsigned_Zero; + else + X.Number(0) := X.Number(0) + 1; + for I in 0..X.Last_Index loop + if X.Number(I) /= 0 then + exit; + else X.Number(I+1) := X. Number(I+1) + 1; + end if; + end loop; + + -- if an mod_type overflow occure then we have some extra work do + if X.Number(X.Last_Index) = 0 then + X.Last_Index := X.Last_Index + 1; + end if; + end if; + end Inc; pragma Inline(Inc); + + --------------------------------------------------------------------------- + + procedure Dec(X : in out Big_Unsigned) is + begin + if X = Big_Unsigned_Zero then + X := Big_Unsigned_Last; + else + X.Number(0) := X.Number(0) - 1; + for I in 0..X.Last_Index loop + if X.Number(I) /= Word'Last then + exit; + else X.Number(I+1) := X.Number(I+1) - 1; + end if; + end loop; + + + -- check if we must dec the Last_index too + if X.Number(X.Last_Index) = 0 and X.Last_Index /= 0 then + X.Last_Index := X.Last_Index - 1; + end if; + end if; + end Dec; pragma Inline(Dec); + + --------------------------------------------------------------------------- + + function Shift_Left(Value : Big_Unsigned; Amount : Natural) + return Big_Unsigned is + begin + if Amount >= (Max_Length+1)*Word'Size or Value = Big_Unsigned_Zero + then return Big_Unsigned_Zero; + elsif Amount = 0 then return Value; + end if; + + declare + Result : Big_Unsigned; + Temp : Limbs:=(others => 0); + L : constant Natural := Amount mod Word'Size; + R : constant Natural := Word'Size-L; + M : constant Natural := Amount/Word'Size; + begin + Temp(0) := Shift_Left(Value.Number(0), L); + +-- for I in 1..Value.Last_Index loop +-- Temp(I) := Shift_Right(Value.Number(I-1), R) + +-- Shift_Left(Value.Number(I), L); +-- end loop; + for I in 1..Value.Last_Index loop + Temp(I) := Shift_Right(Value.Number(I-1), R) xor + Shift_Left(Value.Number(I), L); + end loop; + + if Value.Last_Index /= Max_Length then + Temp(Value.Last_Index+1):= + Shift_Right(Value.Number(Value.Last_Index), R); + end if; + + for I in Temp'Range loop + if (I+M) > Max_Length then + exit; + end if; + Result.Number(I+M):= Temp(I); + end loop; + for I in reverse 0..Max_Length loop + if Result.Number(I) /=0 then + Result.Last_Index:=I; + exit; + end if; + end loop; + return Result; + end; + end Shift_Left; -- pragma Inline (Shift_Left); + + --------------------------------------------------------------------------- + + function Shift_Right(Value : Big_Unsigned; Amount : Natural) + return Big_Unsigned is + begin + if Amount >= (Max_Length+1)*Word'Size or Value = Big_Unsigned_Zero + then return Big_Unsigned_Zero; + elsif Amount = 0 then return Value; + end if; + + declare + Result : Big_Unsigned:=Big_Unsigned_Zero; + Temp : Limbs :=(others => 0); + R : constant Natural := Amount mod Word'Size; + L : constant Natural := Word'Size-R; + M : constant Natural := Amount/Word'Size; + begin + Temp(Value.Last_Index) := + Shift_Right(Value.Number(Value.Last_Index), R); + +-- for I in reverse 0..Value.Last_Index-1 loop +-- Temp(I) := Shift_Left(Value.Number(I+1), L) + +-- Shift_Right(Value.Number(I), R); +-- end loop; + for I in reverse 0..Value.Last_Index-1 loop + Temp(I) := Shift_Left(Value.Number(I+1), L) xor + Shift_Right(Value.Number(I), R); + end loop; + + for I in reverse Temp'Range loop + if (I-M) < 0 then + exit; + end if; + Result.Number(I-M):= Temp(I); + end loop; + + for I in reverse 0..Value.Last_Index loop + if Result.Number(I) /= 0 or I = 0 then + Result.Last_Index := I; + exit; + end if; + end loop; + return Result; + end; + end Shift_Right; --pragma Inline (Shift_Right); + + + --------------------------------------------------------------------------- + + function Rotate_Left(Value : Big_Unsigned; Amount : Natural) + return Big_Unsigned is + L : constant Natural := Amount mod Size; + begin + if Value = Big_Unsigned_Last then + return Big_Unsigned_Last; + end if; + return Shift_Left(Value,L) xor Shift_Right(Value, Size-L); + end Rotate_Left; pragma Inline (Rotate_Left); + + --------------------------------------------------------------------------- + + function Rotate_Right(Value : Big_Unsigned; Amount : Natural) + return Big_Unsigned is + R : constant Natural := Amount mod Size; + begin + if Value = Big_Unsigned_Last then + return Big_Unsigned_Last; + end if; + return Shift_Right(Value,R) xor Shift_Left(Value, Size-R); + end Rotate_Right; pragma Inline (Rotate_Right); + + --------------------------------------------------------------------------- + + function Gcd(Left, Right : Big_Unsigned) return Big_Unsigned is + A : Big_Unsigned := Max(Left,Right); + B : Big_Unsigned := Min(Left,Right); + R : Big_Unsigned; + begin + while B /= Big_Unsigned_Zero loop + R := A mod B; + A := B; + B := R; + end loop; + return A; + end Gcd; pragma Inline (Gcd); + + --------------------------------------------------------------------------- + + function Get_Random return Big_Unsigned is + Result : Big_Unsigned; + begin + Random.Read(Result.Number); + return Result; + end Get_Random; pragma Inline (Get_Random); + + --------------------------------------------------------------------------- + + function Length_In_Bytes(X : Big_Unsigned) return Natural is + Len : constant Natural := Bit_Length(X); + begin + if Len mod Byte'Size = 0 then return (Len / Byte'Size); + else return (Len / Byte'Size) + 1; + end if; + end Length_In_Bytes; pragma Inline (Length_In_Bytes); + + --------------------------------------------------------------------------- + + function To_Big_Unsigned(X : Word) return Big_Unsigned is + Result : constant Big_Unsigned := + (Last_Index => 0, Number => (0 => X, OTHERS => 0)); + begin + return Result; + end To_Big_Unsigned; pragma Inline (To_Big_Unsigned); + + + function To_Words(X : Big_Unsigned) return Words is + begin + return X.Number(0..X.Last_Index); + end To_Words; pragma Inline (To_Words); + + + --------------------------------------------------------------------------- + + function Max(Left, Right : Integer) return Integer is + begin + if Left < Right then + return Right; + else + return Left; + end if; + end Max; + + + --------------------------------------------------------------------------- + + function To_Bytes(X : Big_Unsigned) return Bytes is + L : constant Natural := Max(Length_In_Bytes(X)-1,0); + M : constant Natural := 3; --(Word'Size / Byte'Size) - 1; + E : constant Integer := ((L+1) mod 4) - 1; + B : Bytes(0..L); + begin + for I in 0..X.Last_Index-1 loop + for J in 0..M loop + B(L-I*(M+1)-J) := Byte(Shift_Right(X.Number(I), J*Byte'Size) and + Word(Byte'Last)); + end loop; + end loop; + + if E >= 0 then + for I in 0..E loop + B(I) := Byte(Shift_Right(X.Number(X.Last_Index), (E-I)*Byte'Size) + and Word(Byte'Last)); + end loop; + else + for J in 0..M loop + B(M-J) := Byte(Shift_Right(X.Number(X.Last_Index), J*Byte'Size) + and Word(Byte'Last)); + end loop; + end if; + + return B; + end To_Bytes; + + --------------------------------------------------------------------------- + + function To_Big_Unsigned(X : Words) return Big_Unsigned is + Result : Big_Unsigned; + begin + if X'Length > Max_Length then + raise Constraint_Error; + else + Result.Number(0..X'Last-X'First) := X; + end if; + + for I in reverse 0..Max_Length loop + if Result.Number(I) /= 0 then + Result.Last_Index := I; + exit; + end if; + end loop; + + return Result; + end To_Big_Unsigned; + + --------------------------------------------------------------------------- + + function To_Big_Unsigned(X : Bytes) return Big_Unsigned is + Result : Big_Unsigned; + M : constant Natural := Word'Size / Byte'Size; -- Bytes per Word + Shift_Amount, counter : Natural:=0; + begin + if X'Length*Byte'Size > Size then + raise Constraint_Error; + end if; + + for I in reverse X'Range loop + Result.Number(Counter/M) := Result.Number(Counter/M) or + Shift_Left(Word(X(I)), Shift_Amount*Byte'Size); + Shift_Amount := (Shift_Amount + 1) mod M; + Counter:=Counter+1; + end loop; + + for I in reverse 0..Max_Length loop + if Result.Number(I) /= 0 then + Result.Last_Index := I; + exit; + end if; + end loop; + + return Result; + + end To_Big_Unsigned; + + --------------------------------------------------------------------------- + + procedure Big_Div(Dividend, Divisor : in Big_Unsigned; + Quotient, Remainder : out Big_Unsigned) is + Last_Divisor : constant Natural := Divisor.Last_Index; + begin + if (Last_Divisor = 0) then + case Divisor.Number(0) is + when 0 => raise Division_By_Zero; + when 1 => Quotient := Dividend; + Remainder := Big_Unsigned_Zero; + return; + when others => declare + Temp_Remainder : Word; + Temp_Divisor : constant Word := Divisor.Number(0); + begin + -- We use the function Short_Div, which is faster. + -- See below for the implementation of Short_Div. + Short_Div(Dividend, Temp_Divisor, Quotient, Temp_Remainder); + Remainder := (Last_Index => 0, + Number => (Temp_Remainder, others => 0)); + return; + end; + end case; + + elsif (Dividend < Divisor) then + Quotient := Big_Unsigned_Zero; + Remainder := Dividend; + return; + + elsif Dividend = Big_Unsigned_Zero then + Quotient := Big_Unsigned_Zero; + Remainder := Big_Unsigned_Zero; + return; + + elsif (Bit_Length(Dividend) = Bit_Length(Divisor)) then + -- Dividend > Divisor and Divisor /= 0 and + -- |Dividend|=|Divisor| => Dividend/Divisor=1 + Quotient:=Big_Unsigned_One; + Remainder:=Dividend-Divisor; + return; + end if; + + -- Now, there is only the case where (Dividend > Divisor), (Divisor /= 0) + -- and |Dividend|>|Divisor|. + + declare + Temp_Divisor: Big_Unsigned :=Divisor; + Diff: Natural; + begin + Remainder:= Dividend; + Quotient:=Big_Unsigned_Zero; + + while(Remainder >= Divisor) loop + Diff := Bit_Length(Remainder) - Bit_Length(Divisor); + if Diff = 0 then + Quotient:=Quotient+1; + Remainder:=Remainder-Divisor; + return; + else Diff:=Diff-1; + end if; + Temp_Divisor := Shift_Left(Divisor, Diff); + Remainder := Remainder-Temp_Divisor; + Quotient := Quotient + Shift_Left(Big_Unsigned_One, Diff); + end loop; + end; + end Big_Div; + + + --------------------------------------------------------------------------- + --------------------------------------------------------------------------- + + procedure Short_Div(Dividend : in Big_Unsigned; + Divisor : in Word; + Quotient : out Big_Unsigned; + Remainder : out Word) is + begin + + -- simple cases + if (Dividend < Divisor) then + Remainder := Dividend.Number(0); + Quotient := Big_Unsigned_Zero; + return; + elsif (Divisor = 0) then + raise Division_By_Zero; + elsif (Divisor = 1) then + Quotient := Dividend; + Remainder := 0; + return; + elsif (Dividend = Divisor) then + Quotient := Big_Unsigned_One; + Remainder := 0; + return; + end if; + + declare + Last_Dividend : constant Natural := Dividend.Last_Index; + Temp_Quotient : Big_Unsigned; + Carry : Largest_Unsigned := 0; + Temp : Largest_Unsigned; + Temp_Divisor : constant Largest_Unsigned := + Largest_Unsigned(Divisor); + + begin + for I in reverse 0..Last_Dividend loop + Temp := Largest_Unsigned(Dividend.Number(I)) + + Shift_Left(Carry, Word'Size); + Temp_Quotient.Number(I) := Word(Temp / Temp_Divisor); + Carry := Temp mod Temp_Divisor; + end loop; + + if (Last_Dividend > 0) and then + (Temp_Quotient.Number(Last_Dividend) = 0) then + Temp_Quotient.Last_Index := Last_Dividend - 1; + else + Temp_Quotient.Last_Index := Last_Dividend; + end if; + Quotient := Temp_Quotient; + Remainder := Word(Carry); + end; + end Short_Div; + + + --------------------------------------------------------------------------- + --------------------------------------------------------------------------- + +-- package IIO renames Ada.Integer_Text_IO; +-- package UIO renames Ada.Strings.Unbounded.Text_IO; + + --------------------------------------------------------------------------- + + function To_String(Item : Big_Unsigned; + Base : Number_Base := 10) return String is + S : Unbounded_String := Null_Unbounded_String; + Remainder : Word:=0; + Temp_Item : Big_Unsigned := Item; + Trans : constant array(Word range 0..15) of Character := + ('0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'); + Base_Img : constant String := Base'Img; + begin + if Item = Big_Unsigned_Zero then + if Base = 10 then return "0"; + else + S := "#0#" & S; + S := Base_Img & S; + return Slice(S,2,Length(S)); + end if; + else + if Base /= 10 then + S := "#" & S; + end if; + while (Temp_Item /= Big_Unsigned_Zero) loop + Short_Div(Temp_Item, Word(Base), Temp_Item, Remainder); + S := Trans(Remainder) & S; + end loop; + if Base /= 10 then + S := "#" & S; + S := Base_Img & S; + return Slice(S,2,Length(S)); + end if; + end if; + return To_String(S); + end To_String; + + --------------------------------------------------------------------------- + + procedure Put(Item : in Big_Unsigned; Base : in Number_Base := 10) is + begin + Put(To_String(Item, Base)); + end Put; --pragma Inline(Put); + + --------------------------------------------------------------------------- + + procedure Put_Line(Item : in Big_Unsigned; Base : in Number_Base := 10) is + begin + Put(To_String(Item, Base)); New_Line; + end Put_Line; --pragma Inline(Put_Line); + + --------------------------------------------------------------------------- + + function Get_Digit(C : Character) return Word is + begin + case C is + when '0'..'9' => return Character'Pos(C) - Character'Pos('0'); + when 'A'..'F' => return Character'Pos(C) - Character'Pos('A') + 10; + when others => raise Conversion_Error; + end case; + end Get_Digit; pragma Inline(Get_Digit); + + --------------------------------------------------------------------------- + + function To_Big_Unsigned(S : String) return Big_Unsigned is + Fence_Count: Natural := 0; + Temp : Unbounded_String := Null_Unbounded_String; + M_B : Natural:=0; + begin + if S'Length = 0 then + raise Conversion_Error; + else + for I in reverse S'Range loop + case S(I) is + when '0' => Temp:= S(I) & Temp; M_B:=Natural'Max(M_B,0); + when '1' => Temp:= S(I) & Temp; M_B:=Natural'Max(M_B,1); + when '2' => Temp:= S(I) & Temp; M_B:=Natural'Max(M_B,2); + when '3' => Temp:= S(I) & Temp; M_B:=Natural'Max(M_B,3); + when '4' => Temp:= S(I) & Temp; M_B:=Natural'Max(M_B,4); + when '5' => Temp:= S(I) & Temp; M_B:=Natural'Max(M_B,5); + when '6' => Temp:= S(I) & Temp; M_B:=Natural'Max(M_B,6); + when '7' => Temp:= S(I) & Temp; M_B:=Natural'Max(M_B,7); + when '8' => Temp:= S(I) & Temp; M_B:=Natural'Max(M_B,8); + when '9' => Temp:= S(I) & Temp; M_B:=Natural'Max(M_B,9); + when 'a' | 'A' => Temp:= 'A' & Temp; M_B:=Natural'Max(M_B,11); + when 'b' | 'B' => Temp:= 'B' & Temp; M_B:=Natural'Max(M_B,12); + when 'c' | 'C' => Temp:= 'C' & Temp; M_B:=Natural'Max(M_B,13); + when 'd' | 'D' => Temp:= 'D' & Temp; M_B:=Natural'Max(M_B,14); + when 'e' | 'E' => Temp:= 'E' & Temp; M_B:=Natural'Max(M_B,15); + when 'f' | 'F' => Temp:= 'F' & Temp; M_B:=Natural'Max(M_B,16); + when '_' | ' ' => null; + when '#' => Fence_Count := Fence_Count+1; Temp:= S(I) & Temp; + when others => raise Conversion_Error; + end case; + end loop; + end if; + + declare + Result : Big_Unsigned; + S2 : constant String := To_String(Temp); + begin + + -- Base = 10 + if Fence_Count = 0 then + if M_B > 10 then + raise Conversion_Error; + end if; + for I in S2'Range loop + Result := Result * 10 + Get_Digit(S2(I)); + end loop; + return Result; + + -- Base /= 10 + -- check fences and size (Min_Size=|2#0#|=4) + elsif Fence_Count /= 2 or S2(S2'Last) /= '#' or S2(S2'First) = '#' + or S2'Length < 4 then + raise Conversion_Error; + end if; + + declare + Base : Number_Base; + begin + --Compute and check Base + if S2(S2'First+1) /= '#' then + if S2(S2'First+2) /= '#' then + raise Conversion_Error; + end if; + Base := Number_Base(Get_Digit(S2(S2'First)) * 10 + + Get_Digit(S2(S2'First+1))); + else Base := Number_Base(Get_Digit(S2(S2'First))); + end if; + + -- Check if all Characters are valid to the base + if M_B > Base then + raise Conversion_Error; + end if; + + --Time to compute the Big_Unsigned + if Base > 10 then + for I in S2'First+3..S2'Last-1 loop + Result := Result * Word(Base) + Get_Digit(S2(I)); + end loop; + else + for I in S2'First+2..S2'Last-1 loop + Result := Result * Word(Base) + Get_Digit(S2(I)); + end loop; + end if; + return Result; + end; + end; + end To_Big_Unsigned; + + --------------------------------------------------------------------------- + + end Utils; + |