From 2b8b55de4a18757e8d6769e458c84f7c1df1e261 Mon Sep 17 00:00:00 2001 From: Jed Barber Date: Mon, 13 Feb 2017 18:27:13 +1100 Subject: Swapped out crypto package for something smaller, revised other code and readme/notes slightly --- src/crypto-types-big_numbers.adb | 921 --------------------------------------- 1 file changed, 921 deletions(-) delete mode 100644 src/crypto-types-big_numbers.adb (limited to 'src/crypto-types-big_numbers.adb') diff --git a/src/crypto-types-big_numbers.adb b/src/crypto-types-big_numbers.adb deleted file mode 100644 index b69e55b..0000000 --- a/src/crypto-types-big_numbers.adb +++ /dev/null @@ -1,921 +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.Text_IO; use Ada.Text_IO; -with Ada.Strings.Unbounded; use Ada.Strings.Unbounded; - -package body Crypto.Types.Big_Numbers is - - -- package MIO is new Ada.Text_Io.Modular_IO (Word); - - --------------------------------------------------------------------------- - -----------------------SEPARATED_BODYS------------------------------------- - --------------------------------------------------------------------------- - - package body Utils is separate; - use Utils; - - package body Mod_Utils is separate; - use Mod_Utils; - - package body Binfield_Utils is separate; - use Binfield_Utils; - - --------------------------------------------------------------------------- - ---------------------------COMPARE_FUNCTIONS-------------------------------- - --------------------------------------------------------------------------- - - - --------------------------------------------------------------------------- - -- compare: Big_Unsigned with Big_Unsigned -- - --------------------------------------------------------------------------- - - - function "="(Left, Right : Big_Unsigned) return Boolean is - begin - if Left.Last_Index = Right.Last_Index then - for I in 0..Left.Last_Index loop - if Left.Number(I) /= Right.Number(I) then return False; - end if; - end loop; - else return False; - end if; - return True; - end "="; - - --------------------------------------------------------------------------- - - function "<"(Left, Right : Big_Unsigned) return Boolean is - begin - if Left.Last_Index < Right.Last_Index then return True; - elsif Left.Last_Index > Right.Last_Index then return False; - else - for I in reverse 0..Left.Last_Index loop - if Left.Number(I) < Right.Number(I) then return True; - elsif Left.Number(I) > Right.Number(I) then return False; - end if; - end loop; - end if; - return False; - end "<"; - - --------------------------------------------------------------------------- - - function ">"(Left, Right : Big_Unsigned) return Boolean is - begin - return Right < Left; - end ">"; - - --------------------------------------------------------------------------- - - function "<="(Left, Right : Big_Unsigned) return Boolean is - begin - return not (Right < Left); - end "<="; - - - --------------------------------------------------------------------------- - - - function ">="(Left, Right : Big_Unsigned) return Boolean is - begin - return not (Left < Right); - end ">="; - - --------------------------------------------------------------------------- - - function Min(X, Y : in Big_Unsigned) return Big_Unsigned is - begin - if (X < Y) then return X; - else return Y; - end if; - end Min; - - --------------------------------------------------------------------------- - - function Max(X, Y : in Big_Unsigned) return Big_Unsigned is - begin - if (X < Y) then return Y; - else return X; - end if; - end Max; - - - --------------------------------------------------------------------------- - -- compare: Big_Unsigned with Word -- - --------------------------------------------------------------------------- - - - function "="(Left : Big_Unsigned; Right : Word) return Boolean is - begin - if Left.Last_Index=0 and Left.Number(0) = Right then return True; - else return False; - end if; - end "="; - - --------------------------------------------------------------------------- - - function "="(Left : Word; Right : Big_Unsigned) return Boolean is - begin - return Right = Left; - end "="; - - --------------------------------------------------------------------------- - - function "<"(Left : Big_Unsigned; Right : Word) return Boolean is - begin - if Left.Last_Index > 0 then return False; - else return Left.Number(Left.Last_Index) < Right; - end if; - end "<"; - - --------------------------------------------------------------------------- - - function "<"(Left : Word; Right : Big_Unsigned) return Boolean is - begin - if Right.Last_Index > 0 then return True; - else return Left < Right.Number(Right.Last_Index); - end if; - end "<"; - - --------------------------------------------------------------------------- - - function ">"(Left : Big_Unsigned; Right : Word) return Boolean is - begin - return Right < Left; - end ">"; - - --------------------------------------------------------------------------- - - function ">"(Left : Word; Right : Big_Unsigned) return Boolean is - begin - return Right < Left; - end ">"; - - --------------------------------------------------------------------------- - - function "<="(Left : Big_Unsigned; Right : Word) return Boolean is - begin - return not (Right < Left); - end "<="; - - --------------------------------------------------------------------------- - - function "<="(Left : Word; Right : Big_Unsigned) return Boolean is - begin - return not (Right < Left); - end "<="; - - --------------------------------------------------------------------------- - - function ">="(Left : Big_Unsigned; Right : Word) return Boolean is - begin - return not (Left < Right); - end ">="; - - --------------------------------------------------------------------------- - - function ">="(Left : Word; Right : Big_Unsigned) return Boolean is - begin - return not (Left < Right); - end ">="; - - - --------------------------------------------------------------------------- - ----------------------------BASE_FUNCTIONS--------------------------------- - --------------------------------------------------------------------------- ---============================================================================-- - - function "+"(Left, Right : Big_Unsigned) return Big_Unsigned is - Result : Big_Unsigned; - L : constant Natural := Natural'Max( Bit_Length(Left), Bit_Length(Right)); - begin - if L + 1 <= Word'Size then - Result.Number(0) := Left.Number(0) + Right.Number(0); - else - - declare - Carry : Big_Unsigned; - Temp : Big_Unsigned; - begin - Carry := Left and Right; - Result := Left xor Right; - Carry := Shift_Left(Carry,1); - loop - Temp := Result and Carry; - Result := Result xor Carry; - Carry := Temp; - Carry := Shift_Left(Carry,1); - exit when Carry = Big_Unsigned_Zero; - end loop; - end; - end if; - - return Result; - end "+"; - --- function "+"(Left, Right : Big_Unsigned) return Big_Unsigned is --- Result: Big_Unsigned; --- Carry : Big_Unsigned; --- Temp : Big_Unsigned; --- begin --- Carry := Left and Right; --- Result := Left xor Right; --- Carry := Shift_Left(Carry,1); --- --ADA Do_While --- loop --- Temp := Result and Carry; --- Result := Result xor Carry; --- Carry := Temp; --- Carry := Shift_Left(Carry,1); --- exit when Carry = Big_Unsigned_Zero; --- end loop; --- return Result; --- end "+"; --------------------------------------------------------------------------------- --- function "+"(Left, Right : Big_Unsigned) return Big_Unsigned is --- Result : Big_Unsigned; --- M : constant Natural := Natural'Max(Left.Last_Index, Right.Last_Index); --- Temp : Word; --- Carry : Word :=0; --- begin --- for I in 0..M loop --- Temp :=Carry; --- Result.Number(I) := Left.Number(I) + Right.Number(I) +Temp; --- if Result.Number(I) < Word'Max(Left.Number(I), Right.Number(I)) --- then Carry := 1; --- else Carry := 0; --- end if; --- end loop; - --- if Carry =1 and M < Max_Length then --- Result.Number(M+1) := 1; --- Result.Last_Index := M+1; --- else --- -- Set Result.Last_Index --- for I in reverse 0..M loop --- if Result.Number(I) /= 0 then --- Result.Last_Index := I; --- return Result; --- end if; --- end loop; --- end if; --- return Result; --- end "+"; ---============================================================================-- - --------------------------------------------------------------------------- - - function "+"(Left : Big_Unsigned; Right : Word) return Big_Unsigned is - Big_Right : Constant Big_Unsigned := - (Last_Index => 0, Number => (0 => Right, OTHERS => 0)); - begin - return Left + Big_Right; - end "+"; - - --------------------------------------------------------------------------- - - function "+"(Left : Word; Right : Big_Unsigned) return Big_Unsigned is - Big_Left : constant Big_Unsigned := (Last_Index => 0, Number => (0 => Left, OTHERS => 0)); - begin - return Big_Left + Right; - end "+"; - - --------------------------------------------------------------------------- - - function "-"(Left, Right : Big_Unsigned) return Big_Unsigned is - begin - -- Add the modulus if Right > Left - if Right > Left then - return Big_Unsigned_Last - Right + Left + 1; --- raise Big_Unsigned_Negative; -- RSA does not run - else - declare - Result : Big_Unsigned; - Carry : Word:=0; - begin - -- Remember: Left => Right - for I in 0..Left.Last_Index loop - Result.Number(I) := Left.Number(I) - Right.Number(I) - Carry; - if (Right.Number(I) > Left.Number(I)) or - (Carry= 1 and Right.Number(I) = Left.Number(I)) - then Carry :=1; - else Carry :=0; - end if; - if Result.Number(I) /= 0 then - Result.Last_Index := I; - end if; - end loop; - return Result; - end; - end if; - end "-"; - - --------------------------------------------------------------------------- - - function "-"(Left : Big_Unsigned; Right : Word) return Big_Unsigned is - Big_Right : constant Big_Unsigned := (Last_Index => 0, Number => (0 => Right, OTHERS => 0)); - begin - return Left - Big_Right; - end "-"; - - --------------------------------------------------------------------------- - - function "-"(Left : Word; Right : Big_Unsigned) return Big_Unsigned is - Big_Left : constant Big_Unsigned := (Last_Index => 0, Number => (0 => Left, OTHERS => 0)); - begin - return Big_Left - Right; - end "-"; - - --------------------------------------------------------------------------- - - function "-"(X : Big_Unsigned) return Big_Unsigned is - begin - if X /= Big_Unsigned_Zero then - return Big_Unsigned_Last-X-1; - else - return X; - end if; - end "-"; - - --------------------------------------------------------------------------- ---============================================================================-- - - function "*"(Left, Right : Big_Unsigned) return Big_Unsigned is - Result : Big_Unsigned ; - L : constant Natural := Bit_Length(Left)+Bit_Length(Right); - begin - if L <= Word'Size then - Result.Number(0) := Left.Number(0) * Right.Number(0); - elsif L > 2800 and L <= 3600 then - Result := Karatsuba_P(Left, Right); - elsif L > 3600 then - Result := Toom_Cook_P(Left, Right); - else - declare - Temp : Big_Unsigned; - begin - for I in reverse 0..Left.Last_Index loop - Temp := Left.Number(I) * Right; - Temp := Shift_Left(Temp, (I*Word'Size)); - Result := Result + Temp; - end loop; - end; - end if; - return Result; - end "*"; --------------------------------------------------------------------------------- - - function Russ (Left,Right : Big_Unsigned)return Big_Unsigned is - Result : Big_Unsigned ; - begin - if Bit_Length(Left)+Bit_Length(Right) <= Word'Size then - Result.Number(0) := Left.Number(0) * Right.Number(0); - else - declare - AA : Big_Unsigned := Left; - BB : Big_Unsigned := Right; - begin - while AA > Big_Unsigned_Zero loop - if (AA and Big_Unsigned_One) = 1 then - Result := Result + BB; - AA := AA - 1; - end if; - AA := Shift_Right(AA, 1); - BB := Shift_Left(BB, 1); - end loop; - end; - end if; - return Result; - end Russ; - --------------------------------------------------------------------------------- - - function Karatsuba (Left, Right : Big_Unsigned) return Big_Unsigned is - Result : Big_Unsigned; - begin - if Bit_Length(Left)+Bit_Length(Right) < Word'Size then - Result.Number(0) := Left.Number(0) * Right.Number(0); - else - declare - Left_1, Left_2 : Big_Unsigned; - Right_1, Right_2 : Big_Unsigned; - P_1, P_2 : Big_Unsigned; - N : constant Natural := Natural'Max( Bit_Length(Left) - , Bit_Length(Right))/2; - begin - Left_1 := Shift_Right(Left, N); - Left_2 := Left - Shift_Left( Left_1, N ); - Right_1 := Shift_Right(Right, N); - Right_2 := Right - Shift_Left( Right_1, N ); - - P_1 := Left_1 * Right_1; - P_2 := Left_2 * Right_2; - Result := Shift_Left(P_1, 2*N) - + Shift_Left(((Left_1 + Left_2)*(Right_1 + Right_2)) - P_1 - P_2, N) - + P_2; - end; - end if; - return Result; - end Karatsuba; - - --------------------------------------------------------------------------------- - - function Karatsuba_P (Left, Right : Big_Unsigned) return Big_Unsigned is - Result : Big_Unsigned; - begin - if Bit_Length(Left)+Bit_Length(Right) < Word'Size then - Result.Number(0) := Left.Number(0) * Right.Number(0); - else - declare - Left_1, Left_2 : Big_Unsigned:= Big_Unsigned_Zero; - Right_1, Right_2 : Big_Unsigned:= Big_Unsigned_Zero; - P_1, P_2, P_3 : Big_Unsigned:= Big_Unsigned_Zero; - N : constant Natural := Natural'Max( Bit_Length(Left), - Bit_Length(Right))/2; - ----------------------------------------------------------------------- - task type Karatsuba_Task_Type is - entry Input (Left, Right : in Big_Unsigned); - entry Output(Result : out Big_Unsigned); - end Karatsuba_Task_Type; - task body Karatsuba_Task_Type is - X : Big_Unsigned; - Left_Local : Big_Unsigned; - Right_Local : Big_Unsigned; - begin - accept Input (Left, Right : Big_Unsigned) do - Left_Local := Left; - Right_Local := Right; - end Input; - --- X := Karatsuba(Left_Local, Right_Local); - X := Left_Local * Right_Local; - - accept Output(Result : out Big_Unsigned) do - Result := X; - end Output; - end Karatsuba_Task_Type; - Task_1 : Karatsuba_Task_Type; - Task_2 : Karatsuba_Task_Type; - Task_3 : Karatsuba_Task_Type; - ----------------------------------------------------------------------- - begin - Left_1 := Shift_Right(Left, N); - Left_2 := Left - Shift_Left( Left_1, N ); - Right_1 := Shift_Right(Right, N); - Right_2 := Right - Shift_Left( Right_1, N ); - - Task_1.Input(Left_1, Right_1); - Task_2.Input(Left_2, Right_2); - Task_3.Input((Left_1 + Left_2), (Right_1 + Right_2)); - - Task_1.Output(Result => P_1); - Task_2.Output(Result => P_2); - Task_3.Output(Result => P_3); - - Result := Shift_Left(P_1, 2*N) - + Shift_Left((P_3 - P_1 - P_2), N) - + P_2; - end; - end if; - return Result; - end Karatsuba_P; - - ----------------------------------------------------------------------- - - function Toom_Cook(Left, Right : Big_Unsigned) return Big_Unsigned is - Result : Big_Unsigned; - begin - if Bit_Length(Left)+Bit_Length(Right) < Word'Size then - Result.Number(0) := Left.Number(0) * Right.Number(0); - else - - declare - knuth_1 : Array (1..5) of Big_Unsigned; - knuth_2 : Array (1..4) of Big_Unsigned; - knuth_3 : Array (1..3) of Big_Unsigned; - knuth_4 : Array (1..2) of Big_Unsigned; - knuth_5_1 : Big_Unsigned; - L, R : Array (0..3) of Big_Unsigned; - F_Left, F_Right : Array (2..4) of Big_Unsigned; - Z : Array (0..4) of Big_Unsigned; - Length : constant Natural := Natural'Max( Bit_Length(Left) , - Bit_Length(Right) ); - N : constant Natural := Length / 3; - DN : constant Natural := 2 * N; - - begin - - -- SPLITTING ............................................................. - - L(0) := Shift_Right( Left, DN); - L(1) := Shift_Right( Left, N ) - Shift_Left( L(0), N ); - L(2) := Left - Shift_Left( L(0), DN ) - Shift_Left( L(1), N ); - R(0) := Shift_Right( Right, DN); - R(1) := Shift_Right( Right, N ) - Shift_Left( R(0), N ); - R(2) := Right - Shift_Left( R(0), DN ) - Shift_Left( R(1), N ); - - F_Left(2) := Shift_Left(L(0),2) + Shift_Left(L(1),1) + L(2); - F_Right(2) := Shift_Left(R(0),2) + Shift_Left(R(1),1) + R(2); - F_Left(3) := (Shift_Left(L(0),3) + L(0)) + (Shift_Left(L(1),1)+L(1)) + L(2); - F_Right(3) := (Shift_Left(R(0),3) + R(0)) + (Shift_Left(R(1),1)+R(1)) + R(2); - F_Left(4) := Shift_Left(L(0),4) + Shift_Left(L(1),2) + L(2); - F_Right(4) := Shift_Left(R(0),4) + Shift_Left(R(1),2) + R(2); - - -- INTERPOLATION with POINTWISE MULT ..................................... - - knuth_1(1) := L(2)* R(2); - knuth_1(2) := (L(0) + L(1) + L(2)) * (R(0) + R(1) + R(2)); - knuth_1(3) := F_Left(2) * F_Right(2); - knuth_1(4) := F_Left(3) * F_Right(3); - knuth_1(5) := F_Left(4) * F_Right(4); - - knuth_2(1) := knuth_1(2) - knuth_1(1); - knuth_2(2) := knuth_1(3) - knuth_1(2); - knuth_2(3) := knuth_1(4) - knuth_1(3); - knuth_2(4) := knuth_1(5) - knuth_1(4); - knuth_3(1) := Shift_Right((knuth_2(2) - knuth_2(1)),1); - knuth_3(2) := Shift_Right((knuth_2(3) - knuth_2(2)),1); - knuth_3(3) := Shift_Right((knuth_2(4) - knuth_2(3)),1); - knuth_4(1) := (knuth_3(2) - knuth_3(1)) / 3; - knuth_4(2) := (knuth_3(3) - knuth_3(2)) / 3; - knuth_5_1 := Shift_Right(knuth_4(2) - knuth_4(1),2); - - Z(0) := knuth_5_1; - Z(1) := knuth_4(1); - Z(2) := knuth_3(1); - Z(3) := knuth_2(1); - Z(4) := knuth_1(1); - - -- RECOMPOSITION ............................................................ - - knuth_1(1) := Z(1) - (Z(0) + Shift_Left(Z(0),1)); - knuth_1(2) := knuth_1(1) - (Shift_Left(Z(0),1)); - knuth_1(3) := knuth_1(2) - Z(0); - knuth_2(1) := Z(2) - (Shift_Left(knuth_1(1),1)); - knuth_2(2) := knuth_2(1) - knuth_1(2); - knuth_3(1) := Z(3) - knuth_2(1); - - Result := Shift_Left( Z(0), DN*2) - + Shift_Left(knuth_1(3), DN+N) - + Shift_Left(knuth_2(2), DN) - + Shift_Left(knuth_3(1), N) - + Z(4); - end; - end if; - return Result; - end Toom_Cook; - --------------------------------------------------------------------------------- - - function Toom_Cook_P(Left, Right : Big_Unsigned) return Big_Unsigned is - Result : Big_Unsigned; - begin - if Bit_Length(Left)+Bit_Length(Right) < Word'Size then - Result.Number(0) := Left.Number(0) * Right.Number(0); - else - declare - knuth_1 : Array (1..5) of Big_Unsigned; - knuth_2 : Array (1..4) of Big_Unsigned; - knuth_3 : Array (1..3) of Big_Unsigned; - knuth_4 : Array (1..2) of Big_Unsigned; - knuth_5_1 : Big_Unsigned; - L, R : Array (0..3) of Big_Unsigned; - F_Left, F_Right : Array (2..4) of Big_Unsigned; - Z : Array (0..4) of Big_Unsigned; - - Length : constant Natural := Natural'Max(Bit_Length(Left) , - Bit_Length(Right) ); - N : constant Natural := Length / 3; - DN : constant Natural := 2 * N; - - task type Toom_Cook_Task_Type is - entry Input (Left, Right : in Big_Unsigned); - entry Output(Result : out Big_Unsigned); - end Toom_Cook_Task_Type; - task body Toom_Cook_Task_Type is - X : Big_Unsigned; - Left_Local : Big_Unsigned; - Right_Local : Big_Unsigned; - begin - accept Input (Left, Right : Big_Unsigned) do - Left_Local := Left; - Right_Local := Right; - end Input; - - X := Left_Local * Right_Local; - - accept Output(Result : out Big_Unsigned) do - Result := X; - end Output; - end Toom_Cook_Task_Type; - - Task_1 : Toom_Cook_Task_Type; - Task_2 : Toom_Cook_Task_Type; - Task_3 : Toom_Cook_Task_Type; - Task_4 : Toom_Cook_Task_Type; - Task_5 : Toom_Cook_Task_Type; - - begin - -- SPLITTING ............................................................. - L(0) := Shift_Right( Left, DN); - L(1) := Shift_Right( Left, N ) - Shift_Left( L(0), N ); - L(2) := Left - Shift_Left( L(0), DN ) - Shift_Left( L(1), N ); - R(0) := Shift_Right( Right, DN); - R(1) := Shift_Right( Right, N ) - Shift_Left( R(0), N ); - R(2) := Right - Shift_Left( R(0), DN ) - Shift_Left( R(1), N ); - -- EVALUATION ............................................................ - F_Left(2) := Shift_Left(L(0),2) + Shift_Left(L(1),1) + L(2); - F_Right(2) := Shift_Left(R(0),2) + Shift_Left(R(1),1) + R(2); - F_Left(3) := (Shift_Left(L(0),3) + L(0)) - + (Shift_Left(L(1),1)+L(1)) + L(2); - F_Right(3) := (Shift_Left(R(0),3) + R(0)) - + (Shift_Left(R(1),1)+R(1)) + R(2); - F_Left(4) := Shift_Left(L(0),4) + Shift_Left(L(1),2) + L(2); - F_Right(4) := Shift_Left(R(0),4) + Shift_Left(R(1),2) + R(2); - -- INTERPOLATION with POINTWISE MULT ..................................... - Task_1.Input( L(2), R(2) ); - Task_2.Input(L(0) + L(1) + L(2), R(0) + R(1) + R(2)); - Task_3.Input(F_Left(2), F_Right(2)); - Task_4.Input(F_Left(3), F_Right(3)); - Task_5.Input(F_Left(4), F_Right(4)); - Task_1.Output(Result => knuth_1(1)); - Task_2.Output(Result => knuth_1(2)); - Task_3.Output(Result => knuth_1(3)); - Task_4.Output(Result => knuth_1(4)); - Task_5.Output(Result => knuth_1(5)); - - knuth_2(1) := knuth_1(2) - knuth_1(1); - knuth_2(2) := knuth_1(3) - knuth_1(2); - knuth_2(3) := knuth_1(4) - knuth_1(3); - knuth_2(4) := knuth_1(5) - knuth_1(4); - knuth_3(1) := Shift_Right((knuth_2(2) - knuth_2(1)),1); - knuth_3(2) := Shift_Right((knuth_2(3) - knuth_2(2)),1); - knuth_3(3) := Shift_Right((knuth_2(4) - knuth_2(3)),1); - knuth_4(1) := (knuth_3(2) - knuth_3(1)) / 3; - knuth_4(2) := (knuth_3(3) - knuth_3(2)) / 3; - knuth_5_1 := Shift_Right(knuth_4(2) - knuth_4(1),2); - - Z(0) := knuth_5_1; - Z(1) := knuth_4(1); - Z(2) := knuth_3(1); - Z(3) := knuth_2(1); - Z(4) := knuth_1(1); - -- RECOMPOSITION ......................................................... - knuth_1(1) := Z(1) - (Z(0) + Shift_Left(Z(0),1)); - knuth_1(2) := knuth_1(1) - (Shift_Left(Z(0),1)); - knuth_1(3) := knuth_1(2) - Z(0); - knuth_2(1) := Z(2) - (Shift_Left(knuth_1(1),1)); - knuth_2(2) := knuth_2(1) - knuth_1(2); - knuth_3(1) := Z(3) - knuth_2(1); - - Result := Shift_Left( Z(0), DN*2) - + Shift_Left(knuth_1(3), DN+N) - + Shift_Left(knuth_2(2), DN) - + Shift_Left(knuth_3(1), N) - + Z(4); - end; - end if; - return Result; - end Toom_Cook_P; - ---============================================================================-- - --------------------------------------------------------------------------- - - function "*"(Left : Big_Unsigned; Right : Word) return Big_Unsigned is - begin - if Right = 0 or Left = Big_Unsigned_Zero then return Big_Unsigned_Zero; - elsif Right = 1 then return Left; - end if; - - declare - Result : Big_Unsigned; - begin - for I in 0..Word'Size loop - if (Shift_Right(Right,I) mod 2) = 1 then - Result:= Result + Shift_Left(Left,I); - end if; - end loop; - return Result; - end; - end "*"; - - --------------------------------------------------------------------------- - - function "*"(Left : Word; Right : Big_Unsigned) return Big_Unsigned is - begin - return Right * Left; - end "*"; - - --------------------------------------------------------------------------- - - function "**"(Left, Right : Big_Unsigned) return Big_Unsigned is - begin - if Left = Big_Unsigned_Zero or Left = Big_Unsigned_One then - return Left; - end if; - - -- Square_And_Multiply - declare - Result : Big_Unsigned := Big_Unsigned_One; - begin - for I in reverse 0..Bit_Length(Right)-1 loop - Result := Result * Result; - if (Shift_Right(Right, I) mod 2) = Big_Unsigned_One then - Result := Result * Left; - end if; - end loop; - return Result; - end; - end "**"; - - --------------------------------------------------------------------------- - - - function "/"(Left, Right : Big_Unsigned) return Big_Unsigned is - Q : Big_Unsigned; - R : Big_Unsigned; - begin - Big_Div(Left,Right,Q,R); - return Q; - end "/"; - - --------------------------------------------------------------------------- - - function "/"(Left : Word; Right : Big_Unsigned) return Big_Unsigned is - Big_Left: constant Big_Unsigned := - (Last_Index => 0, Number => (0=> Left, others => 0)); - Q : Big_Unsigned; - R : Big_Unsigned; - begin - Big_Div(Big_Left,Right,Q,R); - return Q; - end "/"; - - --------------------------------------------------------------------------- - - function "/"(Left : Big_Unsigned; Right : Word) return Big_Unsigned is - Q : Big_Unsigned; - R : Word; - begin - Short_Div(Left,Right,Q,R); - return Q; - end "/"; - - - --------------------------------------------------------------------------- - - function "mod"(Left, Right : Big_Unsigned) return Big_Unsigned is - Q : Big_Unsigned; - R : Big_Unsigned; - begin - Big_Div(Left,Right,Q,R); - return R; - end "mod"; - - - - --------------------------------------------------------------------------- - - function "mod"(Left : Big_Unsigned; Right : Word) return Big_Unsigned is - Q : Big_Unsigned; - R : Word; - begin - Short_Div(Left,Right,Q,R); - declare - Result: constant Big_Unsigned := - (Last_Index => 0, Number => (0 => R, others => 0)); - begin - return Result; - end; - end "mod"; - - --------------------------------------------------------------------------- - - -- This is a helper function - -- This procedure computes/adjust the Last_Index of B - procedure Last_Index(B : in out Big_Unsigned; M : in M_Len:=Max_Length) is - begin - for I in reverse 0..M loop - if B.Number(I) /= 0 then - B.Last_Index := I; - exit; - end if; - end loop; - end Last_Index; pragma Inline (Last_Index); - - --------------------------------------------------------------------------- - - - function "xor"(Left, Right : Big_Unsigned) return Big_Unsigned is - Result : Big_Unsigned; - M : constant Natural:= Natural'Max(Left.Last_Index, Right.Last_Index); - begin - -- xor - for I in 0..M loop - Result.Number(I) := Left.Number(I) xor Right.Number(I); - end loop; - - -- compute the Last_Index - Last_Index(Result,M); - - return Result; - - end "xor"; - - --------------------------------------------------------------------------- - - function "and"(Left, Right : Big_Unsigned) return Big_Unsigned is - Result : Big_Unsigned; - M : constant Natural:= Natural'Min(Left.Last_Index, Right.Last_Index); - begin - - --and - for I in 0..M loop - Result.Number(I) := Left.Number(I) and Right.Number(I); - end loop; - - -- compute last index - Last_Index(Result, M); - - return Result; - end "and"; - - --------------------------------------------------------------------------- - - - function "and"(Left : Big_Unsigned; Right : Word) return Big_Unsigned - is - Result : Big_Unsigned; - begin - - Result.Number(0) := Left.Number(0) and Right; - - -- compute last index - Last_Index(Result, 0); - - return Result; - end "and"; - - --------------------------------------------------------------------------- - - function "and"(Left : Word; Right : Big_Unsigned) return Big_Unsigned - is - Result : Big_Unsigned; - begin - - Result.Number(0) := Left and Right.Number(0); - - -- compute last index - Last_Index(Result, 0); - - return Result; - end "and"; - - --------------------------------------------------------------------------- - - - function "or"(Left, Right : Big_Unsigned) return Big_Unsigned is - Result : Big_Unsigned; - M : constant Natural:= Natural'Max(Left.Last_Index, Right.Last_Index); - begin - -- or - for I in 0..M loop - Result.Number(I) := Left.Number(I) or Right.Number(I); - end loop; - - -- compute last index - Last_Index(Result, M); - - return Result; - end "or"; - - --------------------------------------------------------------------------- - --------------------------------------------------------------------------- - --------------------------------------------------------------------------- - -begin - if Size mod Word'Size /= 0 then - Put("Size must be a multiple of " & Word'Image(Word'Size)); - raise Constraint_Size_Error; - end if; -end Crypto.Types.Big_Numbers; -- cgit