------------------------------------------------------------------------------ -- -- -- G N U _ M U L T I P L E _ P R E C I S I O N . Z -- -- -- -- S p e c -- -- -- -- $Revision: 1.2 $ -- -- -- -- Copyright (C) 1999 Michael Roe -- -- -- -- This is free software; you can redistribute it and/or modify it under -- -- terms of the GNU General Public License as published by the Free Soft- -- -- ware Foundation; either version 2, or (at your option) any later ver- -- -- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- -- OUT 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 distributed with GNAT; see file COPYING. If not, write -- -- to the Free Software Foundation, 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. -- -- -- ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ -- Ada language binding to the GNU Multiple Precision library (GMP) -- -- -- -- This package provides facilities for doing arithmetic on integers which -- -- are too large to fit into any if the language-defined integer types. -- -- -- -- A multiple precision integer is represented by the type Big_Integer. -- -- A variable of this type must be explicitly initialised by calling Init -- -- before is can be used, and it must be explicitly freed by calling Clear -- -- when it is no longer needed. -- -- -- -- GNU_Multiple_Precision.Controlled_Z is an alternative to this package -- -- which uses finalization to automatically call Init and Clear. -- -- -- ------------------------------------------------------------------------------ with Ada.Streams; with System; with Interfaces.C; package GNU_Multiple_Precision.Z is pragma Remote_Types (GNU_Multiple_Precision.Z); -- We want to be able to pass a Big_Integer between a client and a server, -- so this package is declared Remote_Types. As Big_Integer is a limited -- private type, user defined Read and Write attibutes are defined for it -- in the private part of this package. pragma Linker_Options ("-lgmp"); -- Most of these functions are implemented in C or assembler, and they -- are found in the library libgmp.a type Big_Integer is limited private; -- Big_Integer represents an integer of unlimited size. -- Its internal representation contains C-language pointers to buffers -- which have been allocated on the heap, so it is not safe to copy one -- by assignment: hence it is declared as a limited type ------------------------------------------------------------------------------ -- Initialization and assignment -- ------------------------------------------------------------------------------ ---------- -- Init -- ---------- procedure Init (X : out Big_Integer); pragma Import (C, Init, "mpz_init"); -- Initializes the fields within a Big_Integer. Big_Integers must be -- be initialized before they are used. -- mpz_array_init is not included in this binding, because it's a -- horrible hack, and you can't free the memory it allocates ----------- -- Clear -- ----------- procedure Clear (X : in out Big_Integer); pragma Import (C, Clear, "mpz_clear"); -- A Big_Integer contains a C-language pointer to a buffer which has -- been allocated on the heap. This function deallocates the buffer. -- Call this procedure to free up memory when the Big_Integer is no -- longer needed. --------- -- Set -- --------- procedure Set (Rop : in out Big_Integer; Op : in Big_Integer); pragma Import (C, Set, "mpz_set"); -- Assign the value of Op to Rop procedure Set_Integer (Rop : in out Big_Integer; Op : in Interfaces.C.int); pragma Import (C, Set_Integer, "mpz_set_si"); procedure Set_Unsigned (Rop : in out Big_Integer; Op : in Interfaces.C.unsigned); pragma Import (C, Set_Unsigned, "mpz_set_ui"); procedure Set_Double (Rop : in out Big_Integer; Op : in Interfaces.C.double); pragma Import (C, Set_Double, "mpz_set_d"); procedure Set_C_String (Rop : in out Big_Integer; Str : in Interfaces.C.char_array; Base : in Interfaces.C.int); pragma Import (C, Set_C_String, "mpz_set_str"); ------------------------------------------------------------------------------ -- Type Conversion -- ------------------------------------------------------------------------------ --------- -- Get -- --------- function Get_Unsigned (Op : Big_Integer) return Interfaces.C.unsigned; pragma Import (C, Get_Unsigned, "mpz_get_ui"); function Get_Integer (Op : Big_Integer) return Interfaces.C.int; pragma Import (C, Get_Integer, "mpz_get_si"); function Get_String (Buffer : System.Address; Base : Integer; Op : Big_Integer) return System.Address; pragma Import (C, Get_String, "mpz_get_str"); ------------------------------------------------------------------------------ -- Arithmetic -- ------------------------------------------------------------------------------ -------------- -- Absolute -- -------------- -- NB: Abs is a reserved word in Ada, so cannot be a procedure name procedure Absolute (Rop : in out Big_Integer; Op : in Big_Integer); pragma Import (C, Absolute, "mpz_abs"); --------- -- Add -- --------- procedure Add (Rop : in out Big_Integer; Op1, Op2 : in Big_Integer); pragma Import (C, Add, "mpz_add"); procedure Add_Unsigned (Rop : in out Big_Integer; Op1 : in Big_Integer; Op2 : in Interfaces.C.unsigned_long); pragma Import (C, Add_Unsigned, "mpz_add_ui"); procedure Add (Rop : in out Big_Integer; Op1 : in Big_Integer; Op2 : in Interfaces.C.unsigned_long) renames Add_Unsigned; --------- -- Div -- --------- procedure Cdiv_Q (Rop : in out Big_Integer; Op1, Op2 : in Big_Integer); pragma Import (C, Cdiv_Q, "mpz_cdiv_q"); procedure Cdiv_Q_Unsigned (Rop : in out Big_Integer; Op1 : in Big_Integer; Op2 : in Interfaces.C.unsigned); pragma Import (C, Cdiv_Q_Unsigned, "mpz_cdiv_q_ui"); procedure Cdiv_QR (Quotient, Remainder : out Big_Integer; Op1, Op2 : in Big_Integer); pragma Import (C, Cdiv_QR, "mpz_cdiv_qr"); procedure Cdiv_QR_Unsigned (Quotient, Remainder : out Big_Integer; Op1 : in Big_Integer; Op2 : in Interfaces.C.unsigned); pragma Import (C, Cdiv_QR_Unsigned, "mpz_cdiv_qr_ui"); procedure Cdiv_R (Rop : in out Big_Integer; Op1, Op2 : in Big_Integer); pragma Import (C, Cdiv_R, "mpz_cdiv_r"); procedure Cdiv_R_Unsigned (Remainder : out Interfaces.C.unsigned; Quotient : out Big_Integer; Op1 : in Big_Integer; Op2 : in Interfaces.C.unsigned); pragma Import (C, Cdiv_R_Unsigned, "mpz_cdiv_r_ui"); -- Ada functions cannot have out parameters, which is a problem for cdiv_r_ui pragma Import_Valued_Procedure (Cdiv_R_Unsigned); function Cdiv_Unsigned (Op1 : in Big_Integer; Op2 : in Interfaces.C.unsigned) return Interfaces.C.unsigned; pragma Import (C, Cdiv_Unsigned, "mpz_cdiv_ui"); --------------- -- Div_Exact -- --------------- procedure Div_Exact (Rop : in out Big_Integer; Op1, Op2 : in Big_Integer); pragma Import (C, Div_Exact, "mpz_divexact"); --------------- -- Factorial -- --------------- procedure Factorial (Rop : in out Big_Integer; Op : Interfaces.C.unsigned); pragma Import (C, Factorial, "mpz_fac_ui"); --------- -- GCD -- --------- procedure GCD (Rop : in out Big_Integer; Op1, Op2 : in Big_Integer); pragma Import (C, GCD, "mpz_gcd"); procedure GCD_Unsigned (Rop : in out Big_Integer; Op1 : in Big_Integer; Op2 : in Interfaces.C.unsigned); pragma Import (C, GCD_Unsigned, "mpz_gcd_ui"); procedure GCD_Extended (G, S, T : in out Big_Integer; A, B : in Big_Integer); pragma Import (C, GCD_Extended, "mpz_gcdext"); -- In Ada, we can't pass a NULL pointer so have to resort to this trick: procedure GCD_Extended_No_T (G, S : in out Big_Integer; Dummy : System.Address; A, B : in Big_Integer); pragma Import (C, GCD_Extended_No_T, "mpz_gcdext"); ------------ -- Invert -- ------------ procedure Invert (Return_Code : out Interfaces.C.int; Rop : in out Big_Integer; Op1, Op2 : in Big_Integer); pragma Import (C, Invert, "mpz_invert"); pragma Import_Valued_Procedure (Invert); --------- -- Neg -- --------- procedure Negate (Rop : in out Big_Integer; Op : in Big_Integer); pragma Import (C, Negate, "mpz_neg"); --------- -- Mod -- --------- -- Mod is a reserved word in Ada procedure Remainder (Rop : in out Big_Integer; Op1, Op2 : in Big_Integer); pragma Import (C, Remainder, "mpz_mod"); -- function Mod_Unsigned (Rop : in out Big_Integer; -- Op1, Op2 : in Big_Integer) -- return Interfaces.C.unsigned; -- pragma Import (C, Mod_Unsigned, "mpz_mod_ui"); -------------- -- Multiply -- -------------- procedure Multiply (Rop : in out Big_Integer; Op1, Op2 : in Big_Integer); pragma Import (C, Multiply, "mpz_mul"); procedure Multiply_2_Exponent (Rop : in out Big_Integer; X : in Big_Integer; Exponent : in Interfaces.C.unsigned); pragma Import (C, Multiply_2_Exponent, "mpz_mul_2exp"); procedure Multiply_Unsigned (Rop : in out Big_Integer; Op1 : in Big_Integer; Op2 : in Interfaces.C.unsigned); pragma Import (C, Multiply_Unsigned, "mpz_mul_ui"); ---------------------- -- Perfect_Square_P -- ---------------------- function Perfect_Square_P (Op : Big_Integer) return Interfaces.C.int; pragma Import (C, Perfect_Square_P, "mpz_perfect_square_p"); ----------- -- Power -- ----------- procedure Power (Rop : in out Big_Integer; Base : in Big_Integer; Exponent : in Interfaces.C.unsigned); pragma Import (C, Power, "mpz_pow_ui"); procedure Power_Unsigned (Rop : in out Big_Integer; Base, Exponent : Interfaces.C.unsigned); pragma Import (C, Power_Unsigned, "mpz_ui_pow_ui"); procedure Power_Modulus (Rop : in out Big_Integer; Base, Exponent, Modulus : in Big_Integer); pragma Import (C, Power_Modulus, "mpz_powm"); procedure Power_Modulus_Unsigned (Rop : in out Big_Integer; Base : in Big_Integer; Exponent : in Interfaces.C.unsigned; Modulus : in Big_Integer); pragma Import (C, Power_Modulus_Unsigned, "mpz_powm_ui"); ---------------------- -- Probable_Prime_P -- ---------------------- function Probable_Prime_P (Op : Big_Integer; Reps : Interfaces.C.int) return Interfaces.C.int; pragma Import (C, Probable_Prime_P, "mpz_probab_prime_p"); ---------- -- Sqrt -- ---------- procedure Sqrt (Rop : in out Big_Integer; Op : in Big_Integer); pragma Import (C, Sqrt, "mpz_sqrt"); procedure Sqrt_Remainder (Rop1, Rop2 : in out Big_Integer; Op : in Big_Integer); pragma Import (C, Sqrt_Remainder, "mpz_sqrtrem"); --------- -- Sub -- --------- procedure Sub (Rop : in out Big_Integer; Op1, Op2 : in Big_Integer); pragma Import (C, Sub, "mpz_sub"); procedure Sub_Unsigned (Rop : in out Big_Integer; Op1 : in Big_Integer; Op2 : in Interfaces.C.unsigned); pragma Import (C, Sub_Unsigned, "mpz_sub_ui"); ------------------------------------------------------------------------------ -- Comparison -- ------------------------------------------------------------------------------ ------------- -- Compare -- ------------- function Compare (Op1, Op2 : Big_Integer) return Integer; pragma Import (C, Compare, "mpz_cmp"); -- Returns a positive value if Op1 > Op2, zero if Op1 = Op2, -- and a negative value if Op1 < Op2. function Compare_Integer (X : Big_Integer; Y : Integer) return Integer; pragma Import (C, Compare_Integer, "mpz_cmp_si"); function Compare (X : Big_Integer; Y : Integer) return Integer renames Compare_Integer; function Compare_Unsigned (X : Big_Integer; Y : Interfaces.C.unsigned) return Integer; pragma Import (C, Compare_Unsigned, "mpz_cmp_ui"); -- Don't overload both the signed and unsigned versions as 'compare', -- as this will lead to ambiguity in resolving the name ------------------------------------------------------------------------------ -- Bit Manipulation -- ------------------------------------------------------------------------------ ----------------- -- Bitwise_And -- ----------------- -- and is a reserved word in Ada, so cannot be a procedure name procedure Bitwise_And (Rop : in out Big_Integer; X, Y : in Big_Integer); pragma Import (C, Bitwise_And, "mpz_and"); ---------------- -- Bitwise_Or -- ---------------- -- or is a reserved word in Ada, so cannot be a procedure name procedure Bitwise_Or (Rop : in out Big_Integer; Op1, Op2 : in Big_Integer); pragma Import (C, Bitwise_Or, "mpz_ior"); ---------------- -- Complement -- ---------------- procedure Complement (Rop : in out Big_Integer; Op : in Big_Integer); pragma Import (C, Complement, "mpz_com"); -- Set Rop to the one's complement of Op ---------------------- -- Population_Count -- ---------------------- function Population_Count (Op : Big_Integer) return Interfaces.C.unsigned; pragma Import (C, Population_Count, "mpz_popcount"); -- For non-negative numbers, return the numbers of 1's bits in the twos -- complement representation of Op. For negative numbers, return MAX_ULONG ---------------------- -- Hamming_Distance -- ---------------------- function Hamming_Distance (Op1, Op2 : Big_Integer) return Interfaces.C.unsigned; pragma Import (C, Hamming_Distance, "mpz_hamdist"); -- If Op1 and Op2 are both non-negative, return the hamming distance -- between them. The behaviour in other cases depends on the version of -- the GMP library; MAX_ULONG may be returned. ----------- -- Scan0 -- ----------- function Scan0 (Op1 : Big_Integer; Starting_Bit : Interfaces.C.unsigned) return Interfaces.C.unsigned; pragma Import (C, Scan0, "mpz_scan0"); -- Starting with Starting_Bit, search towards more significant bits -- until a zero bit is found. Return the index of the found bit. ----------- -- Scan1 -- ----------- function Scan1 (Op1 : Big_Integer; Starting_Bit : Interfaces.C.unsigned) return Interfaces.C.unsigned; pragma Import (C, Scan1, "mpz_scan1"); -- Starting with Starting_Bit, search towards more significant bits -- until a ones bit is found. Return the index of the found bit. ------------- -- Set_Bit -- ------------- procedure Set_Bit (Rop : in out Big_Integer; Bit_Index : in Interfaces.C.unsigned); pragma Import (C, Set_Bit, "mpz_setbit"); -- Set bit number Bit_Index in Rop --------------- -- Clear_Bit -- --------------- procedure Clear_Bit (Rop : in out Big_Integer; Bit : Interfaces.C.unsigned); pragma Import (C, Clear_Bit, "mpz_clrbit"); ------------------------------------------------------------------------------ -- Miscellaneous -- ------------------------------------------------------------------------------ ------------------ -- Size_In_Base -- ------------------- function Size_In_Base (Op : Big_Integer; Base : Interfaces.C.int) return Interfaces.C.size_t; pragma Import (C, Size_In_Base, "mpz_sizeinbase"); ------------ -- Random -- ------------ procedure Random (Rop : Big_Integer; Max_Size : Interfaces.C.size_t); pragma Import (C, Random, "mpz_random"); -- Generate a random integer of size at most Max_Size. The size is -- specified in 'limbs', ie. machine words in the internal representation -- No guarantees are made about the quality of the random-number generator -- Random numbers are generated when Max_Size is negative procedure Random2 (Rop : Big_Integer; Max_Size : Interfaces.C.size_t); pragma Import (C, Random2, "mpz_random2"); private type Big_Integer is record Alloc : Interfaces.C.int; Size : Interfaces.C.int; Limbs : System.Address; end record; procedure Read (Stream : access Ada.Streams.Root_Stream_Type'Class; Item : out Big_Integer); for Big_Integer'Read use Read; procedure Write (Stream : access Ada.Streams.Root_Stream_Type'Class; Item : in Big_Integer); for Big_Integer'Write use Write; end GNU_Multiple_Precision.Z;