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, 0 insertions, 704 deletions
diff --git a/src/crypto-types-big_numbers-utils.adb b/src/crypto-types-big_numbers-utils.adb deleted file mode 100644 index 313ce9b..0000000 --- a/src/crypto-types-big_numbers-utils.adb +++ /dev/null @@ -1,704 +0,0 @@ --- 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; - |