------------------------------------------------------------------------------
--                                                                          --
--                         GNAT RUN-TIME COMPONENTS                         --
--                                                                          --
--                   ADA.NUMERICS.BIG_NUMBERS.BIG_REALS                     --
--                                                                          --
--                                 B o d y                                  --
--                                                                          --
--             Copyright (C) 2019-2024, Free Software Foundation, Inc.      --
--                                                                          --
-- GNAT 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 3,  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.                                     --
--                                                                          --
-- As a special exception under Section 7 of GPL version 3, you are granted --
-- additional permissions described in the GCC Runtime Library Exception,   --
-- version 3.1, as published by the Free Software Foundation.               --
--                                                                          --
-- You should have received a copy of the GNU General Public License and    --
-- a copy of the GCC Runtime Library Exception along with this program;     --
-- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
-- <http://www.gnu.org/licenses/>.                                          --
--                                                                          --
-- GNAT was originally developed  by the GNAT team at  New York University. --
-- Extensive contributions were provided by Ada Core Technologies Inc.      --
--                                                                          --
------------------------------------------------------------------------------

with System.Unsigned_Types; use System.Unsigned_Types;

package body Ada.Numerics.Big_Numbers.Big_Reals is

   use Big_Integers;

   procedure Normalize (Arg : in out Big_Real);
   --  Normalize Arg by ensuring that Arg.Den is always positive and that
   --  Arg.Num and Arg.Den always have a GCD of 1.

   --------------
   -- Is_Valid --
   --------------

   function Is_Valid (Arg : Big_Real) return Boolean is
     (Is_Valid (Arg.Num) and Is_Valid (Arg.Den));

   ---------
   -- "/" --
   ---------

   function "/" (Num, Den : Valid_Big_Integer) return Valid_Big_Real is
      Result : Big_Real;
   begin
      if Den = To_Big_Integer (0) then
         raise Constraint_Error with "divide by zero";
      end if;

      Result.Num := Num;
      Result.Den := Den;
      Normalize (Result);
      return Result;
   end "/";

   ---------------
   -- Numerator --
   ---------------

   function Numerator (Arg : Valid_Big_Real) return Valid_Big_Integer is
     (Arg.Num);

   -----------------
   -- Denominator --
   -----------------

   function Denominator (Arg : Valid_Big_Real) return Big_Positive is
     (Arg.Den);

   ---------
   -- "=" --
   ---------

   function "=" (L, R : Valid_Big_Real) return Boolean is
     (L.Num = R.Num and then L.Den = R.Den);

   ---------
   -- "<" --
   ---------

   function "<" (L, R : Valid_Big_Real) return Boolean is
     (L.Num * R.Den < R.Num * L.Den);
   --  The denominator is guaranteed to be positive since Normalized is
   --  always called when constructing a Valid_Big_Real

   ----------
   -- "<=" --
   ----------

   function "<=" (L, R : Valid_Big_Real) return Boolean is (not (R < L));

   ---------
   -- ">" --
   ---------

   function ">" (L, R : Valid_Big_Real) return Boolean is (R < L);

   ----------
   -- ">=" --
   ----------

   function ">=" (L, R : Valid_Big_Real) return Boolean is (not (L < R));

   -----------------------
   -- Float_Conversions --
   -----------------------

   package body Float_Conversions is

      package Conv is new
        Big_Integers.Unsigned_Conversions (Long_Long_Unsigned);

      -----------------
      -- To_Big_Real --
      -----------------

      --  We get the fractional representation of the floating-point number by
      --  multiplying Num'Fraction by 2.0**M, with M the size of the mantissa,
      --  which gives zero or a number in the range [2.0**(M-1)..2.0**M), which
      --  means that it is an integer N of M bits. The floating-point number is
      --  thus equal to N / 2**(M-E) where E is its Num'Exponent.

      function To_Big_Real (Arg : Num) return Valid_Big_Real is

         A : constant Num'Base := abs (Arg);
         E : constant Integer  := Num'Exponent (A);
         F : constant Num'Base := Num'Fraction (A);
         M : constant Natural  := Num'Machine_Mantissa;

         N, D : Big_Integer;

      begin
         pragma Assert (Num'Machine_Radix = 2);
         --  This implementation does not handle radix 16

         pragma Assert (M <= 64);
         --  This implementation handles only 80-bit IEEE Extended or smaller

         N := Conv.To_Big_Integer (Long_Long_Unsigned (F * 2.0**M));

         --  If E is smaller than M, the denominator is 2**(M-E)

         if E < M then
            D := To_Big_Integer (2) ** (M - E);

         --  Or else, if E is larger than M, multiply the numerator by 2**(E-M)

         elsif E > M then
            N := N * To_Big_Integer (2) ** (E - M);
            D := To_Big_Integer (1);

         --  Otherwise E is equal to M and the result is just N

         else
            D := To_Big_Integer (1);
         end if;

         return (if Arg >= 0.0 then N / D else -N / D);
      end To_Big_Real;

      -------------------
      -- From_Big_Real --
      -------------------

      --  We get the (Frac, Exp) representation of the real number by finding
      --  the exponent E such that it lies in the range [2.0**(E-1)..2.0**E),
      --  multiplying the number by 2.0**(M-E) with M the size of the mantissa,
      --  and converting the result to integer N in the range [2**(M-1)..2**M)
      --  with rounding to nearest, ties to even, and finally call Num'Compose.
      --  This does not apply to the zero, for which we return 0.0 early.

      function From_Big_Real (Arg : Big_Real) return Num is

         M    : constant Natural     := Num'Machine_Mantissa;
         One  : constant Big_Real    := To_Real (1);
         Two  : constant Big_Real    := To_Real (2);
         Half : constant Big_Real    := One / Two;
         TwoI : constant Big_Integer := To_Big_Integer (2);

         function Log2_Estimate (V : Big_Real) return Natural;
         --  Return an integer not larger than Log2 (V) for V >= 1.0

         function Minus_Log2_Estimate (V : Big_Real) return Natural;
         --  Return an integer not larger than -Log2 (V) for V < 1.0

         -------------------
         -- Log2_Estimate --
         -------------------

         function Log2_Estimate (V : Big_Real) return Natural is
            Log : Natural  := 1;
            Pow : Big_Real := Two;

         begin
            while V >= Pow loop
               Pow := Pow * Pow;
               Log := Log + Log;
            end loop;

            return Log / 2;
         end Log2_Estimate;

         -------------------------
         -- Minus_Log2_Estimate --
         -------------------------

         function Minus_Log2_Estimate (V : Big_Real) return Natural is
            Log : Natural  := 1;
            Pow : Big_Real := Half;

         begin
            while V <= Pow loop
               Pow := Pow * Pow;
               Log := Log + Log;
            end loop;

            return Log / 2;
         end Minus_Log2_Estimate;

         --  Local variables

         V : Big_Real := abs (Arg);
         E : Integer  := 0;
         L : Integer;

         A, B, Q, X : Big_Integer;
         N          : Long_Long_Unsigned;
         R          : Num'Base;

      begin
         pragma Assert (Num'Machine_Radix = 2);
         --  This implementation does not handle radix 16

         pragma Assert (M <= 64);
         --  This implementation handles only 80-bit IEEE Extended or smaller

         --  Protect from degenerate case

         if Numerator (V) = To_Big_Integer (0) then
            return 0.0;
         end if;

         --  Use a binary search to compute exponent E

         while V < Half loop
            L := Minus_Log2_Estimate (V);
            V := V * (Two ** L);
            E := E - L;
         end loop;

         --  The dissymetry with above is expected since we go below 2

         while V >= One loop
            L := Log2_Estimate (V) + 1;
            V := V / (Two ** L);
            E := E + L;
         end loop;

         --  The multiplication by 2.0**(-E) has already been done in the loops

         V := V * To_Big_Real (TwoI ** M);

         --  Now go into the integer domain and divide

         A := Numerator (V);
         B := Denominator (V);

         Q := A / B;
         N := Conv.From_Big_Integer (Q);

         --  Round to nearest, ties to even, by comparing twice the remainder

         X := (A - Q * B) * TwoI;

         if X > B or else (X = B and then (N mod 2) = 1) then
            N := N + 1;

            --  If the adjusted quotient overflows the mantissa, scale up

            if N = 2**M then
               N := 1;
               E := E + 1;
            end if;
         end if;

         R := Num'Compose (Num'Base (N), E);

         return (if Numerator (Arg) >= To_Big_Integer (0) then R else -R);
      end From_Big_Real;

   end Float_Conversions;

   -----------------------
   -- Fixed_Conversions --
   -----------------------

   package body Fixed_Conversions is

      package Float_Aux is new Float_Conversions (Long_Float);

      subtype LLLI is Long_Long_Long_Integer;
      subtype LLLU is Long_Long_Long_Unsigned;

      Too_Large : constant Boolean :=
                    Num'Small_Numerator > LLLU'Last
                      or else Num'Small_Denominator > LLLU'Last;
      --  True if the Small is too large for Long_Long_Long_Unsigned, in which
      --  case we convert to/from Long_Float as an intermediate step.

      package Conv_I is new Big_Integers.Signed_Conversions (LLLI);
      package Conv_U is new Big_Integers.Unsigned_Conversions (LLLU);

      -----------------
      -- To_Big_Real --
      -----------------

      --  We just compute V * N / D where V is the mantissa value of the fixed
      --  point number, and N resp. D is the numerator resp. the denominator of
      --  the Small of the fixed-point type.

      function To_Big_Real (Arg : Num) return Valid_Big_Real is
         N, D, V : Big_Integer;

      begin
         if Too_Large then
            return Float_Aux.To_Big_Real (Long_Float (Arg));
         end if;

         N := Conv_U.To_Big_Integer (Num'Small_Numerator);
         D := Conv_U.To_Big_Integer (Num'Small_Denominator);
         V := Conv_I.To_Big_Integer (LLLI'Integer_Value (Arg));

         return V * N / D;
      end To_Big_Real;

      -------------------
      -- From_Big_Real --
      -------------------

      --  We first compute A / B = Arg * D / N where N resp. D is the numerator
      --  resp. the denominator of the Small of the fixed-point type. Then we
      --  divide A by B and convert the result to the mantissa value.

      function From_Big_Real (Arg : Big_Real) return Num is
         N, D, A, B, Q, X : Big_Integer;

      begin
         if Too_Large then
            return Num (Float_Aux.From_Big_Real (Arg));
         end if;

         N := Conv_U.To_Big_Integer (Num'Small_Numerator);
         D := Conv_U.To_Big_Integer (Num'Small_Denominator);
         A := Numerator (Arg) * D;
         B := Denominator (Arg) * N;

         Q := A / B;

         --  Round to nearest, ties to away, by comparing twice the remainder

         X := (A - Q * B) * To_Big_Integer (2);

         if X >= B then
            Q := Q + To_Big_Integer (1);

         elsif X <= -B then
            Q := Q - To_Big_Integer (1);
         end if;

         return Num'Fixed_Value (Conv_I.From_Big_Integer (Q));
      end From_Big_Real;

   end Fixed_Conversions;

   ---------------
   -- To_String --
   ---------------

   function To_String
     (Arg  : Valid_Big_Real;
      Fore : Field := 2;
      Aft  : Field := 3;
      Exp  : Field := 0) return String
   is
      Zero : constant Big_Integer := To_Big_Integer (0);
      Ten  : constant Big_Integer := To_Big_Integer (10);

      function Leading_Padding
        (Str        : String;
         Min_Length : Field;
         Char       : Character := ' ') return String;
      --  Return padding of Char concatenated with Str so that the resulting
      --  string is at least Min_Length long.

      function Trailing_Padding
        (Str    : String;
         Length : Field;
         Char   : Character := '0') return String;
      --  Return Str with trailing Char removed, and if needed either
      --  truncated or concatenated with padding of Char so that the resulting
      --  string is Length long.

      function Image (N : Natural) return String;
      --  Return image of N, with no leading space.

      function Numerator_Image
        (Num   : Big_Integer;
         After : Natural) return String;
      --  Return image of Num as a float value with After digits after the "."
      --  and taking Fore, Aft, Exp into account.

      -----------
      -- Image --
      -----------

      function Image (N : Natural) return String is
         S : constant String := Natural'Image (N);
      begin
         return S (2 .. S'Last);
      end Image;

      ---------------------
      -- Leading_Padding --
      ---------------------

      function Leading_Padding
        (Str        : String;
         Min_Length : Field;
         Char       : Character := ' ') return String is
      begin
         if Str = "" then
            return Leading_Padding ("0", Min_Length, Char);
         else
            return [1 .. Integer'Max (Integer (Min_Length) - Str'Length, 0)
                           => Char] & Str;
         end if;
      end Leading_Padding;

      ----------------------
      -- Trailing_Padding --
      ----------------------

      function Trailing_Padding
        (Str    : String;
         Length : Field;
         Char   : Character := '0') return String is
      begin
         if Str'Length > 0 and then Str (Str'Last) = Char then
            for J in reverse Str'Range loop
               if Str (J) /= '0' then
                  return Trailing_Padding
                    (Str (Str'First .. J), Length, Char);
               end if;
            end loop;
         end if;

         if Str'Length >= Length then
            return Str (Str'First .. Str'First + Length - 1);
         else
            return Str &
              [1 .. Integer'Max (Integer (Length) - Str'Length, 0)
                      => Char];
         end if;
      end Trailing_Padding;

      ---------------------
      -- Numerator_Image --
      ---------------------

      function Numerator_Image
        (Num   : Big_Integer;
         After : Natural) return String
      is
         Tmp   : constant String := To_String (Num);
         Str   : constant String (1 .. Tmp'Last - 1) := Tmp (2 .. Tmp'Last);
         Index : Integer;

      begin
         if After = 0 then
            return Leading_Padding (Str, Fore) & "."
                   & Trailing_Padding ("0", Aft);
         else
            Index := Str'Last - After;

            if Index < 0 then
               return Leading_Padding ("0", Fore)
                 & "."
                 & Trailing_Padding ([1 .. -Index => '0'] & Str, Aft)
                 & (if Exp = 0 then "" else "E+" & Image (Natural (Exp)));
            else
               return Leading_Padding (Str (Str'First .. Index), Fore)
                 & "."
                 & Trailing_Padding (Str (Index + 1 .. Str'Last), Aft)
                 & (if Exp = 0 then "" else "E+" & Image (Natural (Exp)));
            end if;
         end if;
      end Numerator_Image;

   begin
      if Arg.Num < Zero then
         declare
            Str : String := To_String (-Arg, Fore, Aft, Exp);
         begin
            if Str (1) = ' ' then
               for J in 1 .. Str'Last - 1 loop
                  if Str (J + 1) /= ' ' then
                     Str (J) := '-';
                     exit;
                  end if;
               end loop;

               return Str;
            else
               return '-' & Str;
            end if;
         end;
      else
         --  Compute Num * 10^Aft so that we get Aft significant digits
         --  in the integer part (rounded) to display.

         return Numerator_Image
           ((Arg.Num * Ten ** Aft) / Arg.Den, After => Exp + Aft);
      end if;
   end To_String;

   -----------------
   -- From_String --
   -----------------

   function From_String (Arg : String) return Valid_Big_Real is
      Ten   : constant Big_Integer := To_Big_Integer (10);
      Frac  : Big_Integer;
      Exp   : Integer := 0;
      Pow   : Natural := 0;
      Index : Natural := 0;
      Last  : Natural := Arg'Last;

   begin
      for J in reverse Arg'Range loop
         if Arg (J) in 'e' | 'E' then
            if Last /= Arg'Last then
               raise Constraint_Error with "multiple exponents specified";
            end if;

            Last := J - 1;
            Exp := Integer'Value (Arg (J + 1 .. Arg'Last));
            Pow := 0;

         elsif Arg (J) = '.' then
            Index := J - 1;
            exit;
         elsif Arg (J) /= '_' then
            Pow := Pow + 1;
         end if;
      end loop;

      if Index = 0 then
         raise Constraint_Error with "invalid real value";
      end if;

      declare
         Result : Big_Real;
      begin
         Result.Den := Ten ** Pow;
         Result.Num := From_String (Arg (Arg'First .. Index)) * Result.Den;
         Frac := From_String (Arg (Index + 2 .. Last));

         if Result.Num < To_Big_Integer (0) then
            Result.Num := Result.Num - Frac;
         else
            Result.Num := Result.Num + Frac;
         end if;

         if Exp > 0 then
            Result.Num := Result.Num * Ten ** Exp;
         elsif Exp < 0 then
            Result.Den := Result.Den * Ten ** (-Exp);
         end if;

         Normalize (Result);
         return Result;
      end;
   end From_String;

   --------------------------
   -- From_Quotient_String --
   --------------------------

   function From_Quotient_String (Arg : String) return Valid_Big_Real is
      Index : Natural := 0;
   begin
      for J in Arg'First + 1 .. Arg'Last - 1 loop
         if Arg (J) = '/' then
            Index := J;
            exit;
         end if;
      end loop;

      if Index = 0 then
         raise Constraint_Error with "no quotient found";
      end if;

      return Big_Integers.From_String (Arg (Arg'First .. Index - 1)) /
        Big_Integers.From_String (Arg (Index + 1 .. Arg'Last));
   end From_Quotient_String;

   ---------------
   -- Put_Image --
   ---------------

   procedure Put_Image (S : in out Root_Buffer_Type'Class; V : Big_Real) is
      --  This is implemented in terms of To_String. It might be more elegant
      --  and more efficient to do it the other way around, but this is the
      --  most expedient implementation for now.
   begin
      Strings.Text_Buffers.Put_UTF_8 (S, To_String (V));
   end Put_Image;

   ---------
   -- "+" --
   ---------

   function "+" (L : Valid_Big_Real) return Valid_Big_Real is
      Result : Big_Real;
   begin
      Result.Num := L.Num;
      Result.Den := L.Den;
      return Result;
   end "+";

   ---------
   -- "-" --
   ---------

   function "-" (L : Valid_Big_Real) return Valid_Big_Real is
     (Num => -L.Num, Den => L.Den);

   -----------
   -- "abs" --
   -----------

   function "abs" (L : Valid_Big_Real) return Valid_Big_Real is
     (Num => abs L.Num, Den => L.Den);

   ---------
   -- "+" --
   ---------

   function "+" (L, R : Valid_Big_Real) return Valid_Big_Real is
      Result : Big_Real;
   begin
      Result.Num := L.Num * R.Den + R.Num * L.Den;
      Result.Den := L.Den * R.Den;
      Normalize (Result);
      return Result;
   end "+";

   ---------
   -- "-" --
   ---------

   function "-" (L, R : Valid_Big_Real) return Valid_Big_Real is
      Result : Big_Real;
   begin
      Result.Num := L.Num * R.Den - R.Num * L.Den;
      Result.Den := L.Den * R.Den;
      Normalize (Result);
      return Result;
   end "-";

   ---------
   -- "*" --
   ---------

   function "*" (L, R : Valid_Big_Real) return Valid_Big_Real is
      Result : Big_Real;
   begin
      Result.Num := L.Num * R.Num;
      Result.Den := L.Den * R.Den;
      Normalize (Result);
      return Result;
   end "*";

   ---------
   -- "/" --
   ---------

   function "/" (L, R : Valid_Big_Real) return Valid_Big_Real is
      Result : Big_Real;
   begin
      Result.Num := L.Num * R.Den;
      Result.Den := L.Den * R.Num;
      Normalize (Result);
      return Result;
   end "/";

   ----------
   -- "**" --
   ----------

   function "**" (L : Valid_Big_Real; R : Integer) return Valid_Big_Real is
      Result : Big_Real;
   begin
      if R = 0 then
         Result.Num := To_Big_Integer (1);
         Result.Den := To_Big_Integer (1);
      else
         if R < 0 then
            Result.Num := L.Den ** (-R);
            Result.Den := L.Num ** (-R);
         else
            Result.Num := L.Num ** R;
            Result.Den := L.Den ** R;
         end if;

         Normalize (Result);
      end if;

      return Result;
   end "**";

   ---------
   -- Min --
   ---------

   function Min (L, R : Valid_Big_Real) return Valid_Big_Real is
     (if L < R then L else R);

   ---------
   -- Max --
   ---------

   function Max (L, R : Valid_Big_Real) return Valid_Big_Real is
     (if L > R then L else R);

   ---------------
   -- Normalize --
   ---------------

   procedure Normalize (Arg : in out Big_Real) is
      Zero : constant Big_Integer := To_Big_Integer (0);
   begin
      if Arg.Den < Zero then
         Arg.Num := -Arg.Num;
         Arg.Den := -Arg.Den;
      end if;

      if Arg.Num = Zero then
         Arg.Den := To_Big_Integer (1);
      else
         declare
            GCD : constant Big_Integer :=
              Greatest_Common_Divisor (Arg.Num, Arg.Den);
         begin
            Arg.Num := Arg.Num / GCD;
            Arg.Den := Arg.Den / GCD;
         end;
      end if;
   end Normalize;

end Ada.Numerics.Big_Numbers.Big_Reals;