gcc/ada/uintp.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT COMPILER COMPONENTS                         --
   4 --                                                                          --
   5 --                                U I N T P                                 --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --          Copyright (C) 1992-2019, Free Software Foundation, Inc.         --
  10 --                                                                          --
  11 -- GNAT is free software;  you can  redistribute it  and/or modify it under --
  12 -- terms of the  GNU General Public License as published  by the Free Soft- --
  13 -- ware  Foundation;  either version 3,  or (at your option) any later ver- --
  14 -- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
  15 -- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
  16 -- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
  17 --                                                                          --
  18 -- As a special exception under Section 7 of GPL version 3, you are granted --
  19 -- additional permissions described in the GCC Runtime Library Exception,   --
  20 -- version 3.1, as published by the Free Software Foundation.               --
  21 --                                                                          --
  22 -- You should have received a copy of the GNU General Public License and    --
  23 -- a copy of the GCC Runtime Library Exception along with this program;     --
  24 -- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
  25 -- <http://www.gnu.org/licenses/>.                                          --
  26 --                                                                          --
  27 -- GNAT was originally developed  by the GNAT team at  New York University. --
  28 -- Extensive contributions were provided by Ada Core Technologies Inc.      --
  29 --                                                                          --
  30 ------------------------------------------------------------------------------
  31
  32 --  Support for universal integer arithmetic
  33
  34 --  WARNING: There is a C version of this package. Any changes to this
  35 --  source file must be properly reflected in the C header file uintp.h
  36
  37 with Alloc;
  38 with Table;
  39 pragma Elaborate_All (Table);
  40 with Types; use Types;
  41
  42 package Uintp is
  43
  44    -------------------------------------------------
  45    -- Basic Types and Constants for Uintp Package --
  46    -------------------------------------------------
  47
  48    type Uint is private;
  49    --  The basic universal integer type
  50
  51    No_Uint : constant Uint;
  52    --  A constant value indicating a missing or unset Uint value
  53
  54    Uint_0   : constant Uint;
  55    Uint_1   : constant Uint;
  56    Uint_2   : constant Uint;
  57    Uint_3   : constant Uint;
  58    Uint_4   : constant Uint;
  59    Uint_5   : constant Uint;
  60    Uint_6   : constant Uint;
  61    Uint_7   : constant Uint;
  62    Uint_8   : constant Uint;
  63    Uint_9   : constant Uint;
  64    Uint_10  : constant Uint;
  65    Uint_11  : constant Uint;
  66    Uint_12  : constant Uint;
  67    Uint_13  : constant Uint;
  68    Uint_14  : constant Uint;
  69    Uint_15  : constant Uint;
  70    Uint_16  : constant Uint;
  71    Uint_24  : constant Uint;
  72    Uint_32  : constant Uint;
  73    Uint_63  : constant Uint;
  74    Uint_64  : constant Uint;
  75    Uint_80  : constant Uint;
  76    Uint_128 : constant Uint;
  77
  78    Uint_Minus_1   : constant Uint;
  79    Uint_Minus_2   : constant Uint;
  80    Uint_Minus_3   : constant Uint;
  81    Uint_Minus_4   : constant Uint;
  82    Uint_Minus_5   : constant Uint;
  83    Uint_Minus_6   : constant Uint;
  84    Uint_Minus_7   : constant Uint;
  85    Uint_Minus_8   : constant Uint;
  86    Uint_Minus_9   : constant Uint;
  87    Uint_Minus_12  : constant Uint;
  88    Uint_Minus_36  : constant Uint;
  89    Uint_Minus_63  : constant Uint;
  90    Uint_Minus_80  : constant Uint;
  91    Uint_Minus_128 : constant Uint;
  92
  93    type UI_Vector is array (Pos range <>) of Int;
  94    --  Vector containing the integer values of a Uint value
  95
  96    --  Note: An earlier version of this package used pointers of arrays of Ints
  97    --  (dynamically allocated) for the Uint type. The change leads to a few
  98    --  less natural idioms used throughout this code, but eliminates all uses
  99    --  of the heap except for the table package itself. For example, Uint
 100    --  parameters are often converted to UI_Vectors for internal manipulation.
 101    --  This is done by creating the local UI_Vector using the function N_Digits
 102    --  on the Uint to find the size needed for the vector, and then calling
 103    --  Init_Operand to copy the values out of the table into the vector.
 104
 105    -----------------
 106    -- Subprograms --
 107    -----------------
 108
 109    procedure Initialize;
 110    --  Initialize Uint tables. Note that Initialize must not be called if
 111    --  Tree_Read is used. Note also that there is no lock routine in this
 112    --  unit, these are among the few tables that can be expanded during
 113    --  gigi processing.
 114
 115    procedure Tree_Read;
 116    --  Initializes internal tables from current tree file using the relevant
 117    --  Table.Tree_Read routines. Note that Initialize should not be called if
 118    --  Tree_Read is used. Tree_Read includes all necessary initialization.
 119
 120    procedure Tree_Write;
 121    --  Writes out internal tables to current tree file using the relevant
 122    --  Table.Tree_Write routines.
 123
 124    function UI_Abs (Right : Uint) return Uint;
 125    pragma Inline (UI_Abs);
 126    --  Returns abs function of universal integer
 127
 128    function UI_Add (Left : Uint; Right : Uint) return Uint;
 129    function UI_Add (Left : Int;  Right : Uint) return Uint;
 130    function UI_Add (Left : Uint; Right : Int)  return Uint;
 131    --  Returns sum of two integer values
 132
 133    function UI_Decimal_Digits_Hi (U : Uint) return Nat;
 134    --  Returns an estimate of the number of decimal digits required to
 135    --  represent the absolute value of U. This estimate is correct or high,
 136    --  i.e. it never returns a value that is too low. The accuracy of the
 137    --  estimate affects only the effectiveness of comparison optimizations
 138    --  in Urealp.
 139
 140    function UI_Decimal_Digits_Lo (U : Uint) return Nat;
 141    --  Returns an estimate of the number of decimal digits required to
 142    --  represent the absolute value of U. This estimate is correct or low,
 143    --  i.e. it never returns a value that is too high. The accuracy of the
 144    --  estimate affects only the effectiveness of comparison optimizations
 145    --  in Urealp.
 146
 147    function UI_Div (Left : Uint; Right : Uint) return Uint;
 148    function UI_Div (Left : Int;  Right : Uint) return Uint;
 149    function UI_Div (Left : Uint; Right : Int)  return Uint;
 150    --  Returns quotient of two integer values. Fatal error if Right = 0
 151
 152    function UI_Eq (Left : Uint; Right : Uint) return Boolean;
 153    function UI_Eq (Left : Int;  Right : Uint) return Boolean;
 154    function UI_Eq (Left : Uint; Right : Int)  return Boolean;
 155    pragma Inline (UI_Eq);
 156    --  Compares integer values for equality
 157
 158    function UI_Expon (Left : Uint; Right : Uint) return Uint;
 159    function UI_Expon (Left : Int;  Right : Uint) return Uint;
 160    function UI_Expon (Left : Uint; Right : Int)  return Uint;
 161    function UI_Expon (Left : Int;  Right : Int)  return Uint;
 162    --  Returns result of exponentiating two integer values.
 163    --  Fatal error if Right is negative.
 164
 165    function UI_GCD (Uin, Vin : Uint) return Uint;
 166    --  Computes GCD of input values. Assumes Uin >= Vin >= 0
 167
 168    function UI_Ge (Left : Uint; Right : Uint) return Boolean;
 169    function UI_Ge (Left : Int;  Right : Uint) return Boolean;
 170    function UI_Ge (Left : Uint; Right : Int)  return Boolean;
 171    pragma Inline (UI_Ge);
 172    --  Compares integer values for greater than or equal
 173
 174    function UI_Gt (Left : Uint; Right : Uint) return Boolean;
 175    function UI_Gt (Left : Int;  Right : Uint) return Boolean;
 176    function UI_Gt (Left : Uint; Right : Int)  return Boolean;
 177    pragma Inline (UI_Gt);
 178    --  Compares integer values for greater than
 179
 180    function UI_Is_In_Int_Range (Input : Uint) return Boolean;
 181    pragma Inline (UI_Is_In_Int_Range);
 182    --  Determines if universal integer is in Int range
 183
 184    function UI_Le (Left : Uint; Right : Uint) return Boolean;
 185    function UI_Le (Left : Int;  Right : Uint) return Boolean;
 186    function UI_Le (Left : Uint; Right : Int)  return Boolean;
 187    pragma Inline (UI_Le);
 188    --  Compares integer values for less than or equal
 189
 190    function UI_Lt (Left : Uint; Right : Uint) return Boolean;
 191    function UI_Lt (Left : Int;  Right : Uint) return Boolean;
 192    function UI_Lt (Left : Uint; Right : Int)  return Boolean;
 193    --  Compares integer values for less than
 194
 195    function UI_Max (Left : Uint; Right : Uint) return Uint;
 196    function UI_Max (Left : Int;  Right : Uint) return Uint;
 197    function UI_Max (Left : Uint; Right : Int)  return Uint;
 198    --  Returns maximum of two integer values
 199
 200    function UI_Min (Left : Uint; Right : Uint) return Uint;
 201    function UI_Min (Left : Int;  Right : Uint) return Uint;
 202    function UI_Min (Left : Uint; Right : Int)  return Uint;
 203    --  Returns minimum of two integer values
 204
 205    function UI_Mod (Left : Uint; Right : Uint) return Uint;
 206    function UI_Mod (Left : Int;  Right : Uint) return Uint;
 207    function UI_Mod (Left : Uint; Right : Int)  return Uint;
 208    pragma Inline (UI_Mod);
 209    --  Returns mod function of two integer values
 210
 211    function UI_Mul (Left : Uint; Right : Uint) return Uint;
 212    function UI_Mul (Left : Int;  Right : Uint) return Uint;
 213    function UI_Mul (Left : Uint; Right : Int)  return Uint;
 214    --  Returns product of two integer values
 215
 216    function UI_Ne (Left : Uint; Right : Uint) return Boolean;
 217    function UI_Ne (Left : Int;  Right : Uint) return Boolean;
 218    function UI_Ne (Left : Uint; Right : Int)  return Boolean;
 219    pragma Inline (UI_Ne);
 220    --  Compares integer values for inequality
 221
 222    function UI_Negate (Right : Uint) return Uint;
 223    pragma Inline (UI_Negate);
 224    --  Returns negative of universal integer
 225
 226    function UI_Rem (Left : Uint; Right : Uint) return Uint;
 227    function UI_Rem (Left : Int;  Right : Uint) return Uint;
 228    function UI_Rem (Left : Uint; Right : Int)  return Uint;
 229    --  Returns rem of two integer values
 230
 231    function UI_Sub (Left : Uint; Right : Uint) return Uint;
 232    function UI_Sub (Left : Int;  Right : Uint) return Uint;
 233    function UI_Sub (Left : Uint; Right : Int)  return Uint;
 234    pragma Inline (UI_Sub);
 235    --  Returns difference of two integer values
 236
 237    function UI_Modular_Exponentiation
 238      (B      : Uint;
 239       E      : Uint;
 240       Modulo : Uint) return Uint;
 241    --  Efficiently compute (B**E) rem Modulo
 242
 243    function UI_Modular_Inverse (N : Uint; Modulo : Uint) return Uint;
 244    --  Compute the multiplicative inverse of N in modular arithmetics with the
 245    --  given Modulo (uses Euclid's algorithm). Note: the call is considered
 246    --  to be erroneous (and the behavior is undefined) if n is not invertible.
 247
 248    function UI_From_Int (Input : Int) return Uint;
 249    --  Converts Int value to universal integer form
 250
 251    generic
 252       type In_T is range <>;
 253    function UI_From_Integral (Input : In_T) return Uint;
 254    --  Likewise, but converts from any integer type. Must not be applied to
 255    --  biased types (instantiation will provide a warning if actual is a biased
 256    --  type).
 257
 258    function UI_From_CC (Input : Char_Code) return Uint;
 259    --  Converts Char_Code value to universal integer form
 260
 261    function UI_To_Int (Input : Uint) return Int;
 262    --  Converts universal integer value to Int. Constraint_Error if value is
 263    --  not in appropriate range.
 264
 265    function UI_To_CC (Input : Uint) return Char_Code;
 266    --  Converts universal integer value to Char_Code. Constraint_Error if value
 267    --  is not in Char_Code range.
 268
 269    function Num_Bits (Input : Uint) return Nat;
 270    --  Approximate number of binary bits in given universal integer. This
 271    --  function is used for capacity checks, and it can be one bit off
 272    --  without affecting its usage.
 273
 274    function Vector_To_Uint
 275      (In_Vec   : UI_Vector;
 276       Negative : Boolean) return Uint;
 277    --  Functions that calculate values in UI_Vectors, call this function to
 278    --  create and return the Uint value. In_Vec contains the multiple precision
 279    --  (Base) representation of a non-negative value. Leading zeroes are
 280    --  permitted. Negative is set if the desired result is the negative of the
 281    --  given value. The result will be either the appropriate directly
 282    --  represented value, or a table entry in the proper canonical format is
 283    --  created and returned.
 284    --
 285    --  Note that Init_Operand puts a signed value in the result vector, but
 286    --  Vector_To_Uint is always presented with a non-negative value. The
 287    --  processing of signs is something that is done by the caller before
 288    --  calling Vector_To_Uint.
 289
 290    ---------------------
 291    -- Output Routines --
 292    ---------------------
 293
 294    type UI_Format is (Hex, Decimal, Auto);
 295    --  Used to determine whether UI_Image/UI_Write output is in hexadecimal
 296    --  or decimal format. Auto, the default setting, lets the routine make a
 297    --  decision based on the value.
 298
 299    UI_Image_Max    : constant := 48; -- Enough for a 128-bit number
 300    UI_Image_Buffer : String (1 .. UI_Image_Max);
 301    UI_Image_Length : Natural;
 302    --  Buffer used for UI_Image as described below
 303
 304    procedure UI_Image (Input : Uint; Format : UI_Format := Auto);
 305    --  Places a representation of Uint, consisting of a possible minus sign,
 306    --  followed by the value in UI_Image_Buffer. The form of the value is an
 307    --  integer literal in either decimal (no base) or hexadecimal (base 16)
 308    --  format. If Hex is True on entry, then hex mode is forced, otherwise
 309    --  UI_Image makes a guess at which output format is more convenient. The
 310    --  value must fit in UI_Image_Buffer. The actual length of the result is
 311    --  returned in UI_Image_Length. If necessary to meet this requirement, the
 312    --  result is an approximation of the proper value, using an exponential
 313    --  format. The image of No_Uint is output as a single question mark.
 314
 315    function UI_Image (Input : Uint; Format : UI_Format := Auto) return String;
 316    --  Functional form, in which the result is returned as a string. This call
 317    --  also leaves the result in UI_Image_Buffer/Length as described above.
 318
 319    procedure UI_Write (Input : Uint; Format : UI_Format := Auto);
 320    --  Writes a representation of Uint, consisting of a possible minus sign,
 321    --  followed by the value to the output file. The form of the value is an
 322    --  integer literal in either decimal (no base) or hexadecimal (base 16)
 323    --  format as appropriate. UI_Format shows which format to use. Auto, the
 324    --  default, asks UI_Write to make a guess at which output format will be
 325    --  more convenient to read.
 326
 327    procedure pid (Input : Uint);
 328    pragma Export (Ada, pid);
 329    --  Writes representation of Uint in decimal with a terminating line
 330    --  return. This is intended for use from the debugger.
 331
 332    procedure pih (Input : Uint);
 333    pragma Export (Ada, pih);
 334    --  Writes representation of Uint in hex with a terminating line return.
 335    --  This is intended for use from the debugger.
 336
 337    ------------------------
 338    -- Operator Renamings --
 339    ------------------------
 340
 341    function "+" (Left : Uint; Right : Uint) return Uint renames UI_Add;
 342    function "+" (Left : Int;  Right : Uint) return Uint renames UI_Add;
 343    function "+" (Left : Uint; Right : Int)  return Uint renames UI_Add;
 344
 345    function "/" (Left : Uint; Right : Uint) return Uint renames UI_Div;
 346    function "/" (Left : Int;  Right : Uint) return Uint renames UI_Div;
 347    function "/" (Left : Uint; Right : Int)  return Uint renames UI_Div;
 348
 349    function "*" (Left : Uint; Right : Uint) return Uint renames UI_Mul;
 350    function "*" (Left : Int;  Right : Uint) return Uint renames UI_Mul;
 351    function "*" (Left : Uint; Right : Int)  return Uint renames UI_Mul;
 352
 353    function "-" (Left : Uint; Right : Uint) return Uint renames UI_Sub;
 354    function "-" (Left : Int;  Right : Uint) return Uint renames UI_Sub;
 355    function "-" (Left : Uint; Right : Int)  return Uint renames UI_Sub;
 356
 357    function "**"  (Left : Uint; Right : Uint) return Uint renames UI_Expon;
 358    function "**"  (Left : Uint; Right : Int)  return Uint renames UI_Expon;
 359    function "**"  (Left : Int;  Right : Uint) return Uint renames UI_Expon;
 360    function "**"  (Left : Int;  Right : Int)  return Uint renames UI_Expon;
 361
 362    function "abs" (Real : Uint) return Uint renames UI_Abs;
 363
 364    function "mod" (Left : Uint; Right : Uint) return Uint renames UI_Mod;
 365    function "mod" (Left : Int;  Right : Uint) return Uint renames UI_Mod;
 366    function "mod" (Left : Uint; Right : Int)  return Uint renames UI_Mod;
 367
 368    function "rem" (Left : Uint; Right : Uint) return Uint renames UI_Rem;
 369    function "rem" (Left : Int;  Right : Uint) return Uint renames UI_Rem;
 370    function "rem" (Left : Uint; Right : Int)  return Uint renames UI_Rem;
 371
 372    function "-"   (Real : Uint) return Uint renames UI_Negate;
 373
 374    function "="   (Left : Uint; Right : Uint) return Boolean renames UI_Eq;
 375    function "="   (Left : Int;  Right : Uint) return Boolean renames UI_Eq;
 376    function "="   (Left : Uint; Right : Int)  return Boolean renames UI_Eq;
 377
 378    function ">="  (Left : Uint; Right : Uint) return Boolean renames UI_Ge;
 379    function ">="  (Left : Int;  Right : Uint) return Boolean renames UI_Ge;
 380    function ">="  (Left : Uint; Right : Int)  return Boolean renames UI_Ge;
 381
 382    function ">"   (Left : Uint; Right : Uint) return Boolean renames UI_Gt;
 383    function ">"   (Left : Int;  Right : Uint) return Boolean renames UI_Gt;
 384    function ">"   (Left : Uint; Right : Int)  return Boolean renames UI_Gt;
 385
 386    function "<="  (Left : Uint; Right : Uint) return Boolean renames UI_Le;
 387    function "<="  (Left : Int;  Right : Uint) return Boolean renames UI_Le;
 388    function "<="  (Left : Uint; Right : Int)  return Boolean renames UI_Le;
 389
 390    function "<"   (Left : Uint; Right : Uint) return Boolean renames UI_Lt;
 391    function "<"   (Left : Int;  Right : Uint) return Boolean renames UI_Lt;
 392    function "<"   (Left : Uint; Right : Int)  return Boolean renames UI_Lt;
 393
 394    -----------------------------
 395    -- Mark/Release Processing --
 396    -----------------------------
 397
 398    --  The space used by Uint data is not automatically reclaimed. However, a
 399    --  mark-release regime is implemented which allows storage to be released
 400    --  back to a previously noted mark. This is used for example when doing
 401    --  comparisons, where only intermediate results get stored that do not
 402    --  need to be saved for future use.
 403
 404    type Save_Mark is private;
 405
 406    function Mark return Save_Mark;
 407    --  Note mark point for future release
 408
 409    procedure Release (M : Save_Mark);
 410    --  Release storage allocated since mark was noted
 411
 412    procedure Release_And_Save (M : Save_Mark; UI : in out Uint);
 413    --  Like Release, except that the given Uint value (which is typically among
 414    --  the data being released) is recopied after the release, so that it is
 415    --  the most recent item, and UI is updated to point to its copied location.
 416
 417    procedure Release_And_Save (M : Save_Mark; UI1, UI2 : in out Uint);
 418    --  Like Release, except that the given Uint values (which are typically
 419    --  among the data being released) are recopied after the release, so that
 420    --  they are the most recent items, and UI1 and UI2 are updated if necessary
 421    --  to point to the copied locations. This routine is careful to do things
 422    --  in the right order, so that the values do not clobber one another.
 423
 424    -----------------------------------
 425    -- Representation of Uint Values --
 426    -----------------------------------
 427
 428 private
 429
 430    type Uint is new Int range Uint_Low_Bound .. Uint_High_Bound;
 431    for Uint'Size use 32;
 432
 433    No_Uint : constant Uint := Uint (Uint_Low_Bound);
 434
 435    --  Uint values are represented as multiple precision integers stored in
 436    --  a multi-digit format using Base as the base. This value is chosen so
 437    --  that the product Base*Base is within the range of allowed Int values.
 438
 439    --  Base is defined to allow efficient execution of the primitive operations
 440    --  (a0, b0, c0) defined in the section "The Classical Algorithms"
 441    --  (sec. 4.3.1) of Donald Knuth's "The Art of Computer Programming",
 442    --  Vol. 2. These algorithms are used in this package. In particular,
 443    --  the product of two single digits in this base fits in a 32-bit integer.
 444
 445    Base_Bits : constant := 15;
 446    --  Number of bits in base value
 447
 448    Base : constant Int := 2**Base_Bits;
 449
 450    --  Values in the range -(Base-1) .. Max_Direct are encoded directly as
 451    --  Uint values by adding a bias value. The value of Max_Direct is chosen
 452    --  so that a directly represented number always fits in two digits when
 453    --  represented in base format.
 454
 455    Min_Direct : constant Int := -(Base - 1);
 456    Max_Direct : constant Int := (Base - 1) * (Base - 1);
 457
 458    --  The following values define the bias used to store Uint values which
 459    --  are in this range, as well as the biased values for the first and last
 460    --  values in this range. We use a new derived type for these constants to
 461    --  avoid accidental use of Uint arithmetic on these values, which is never
 462    --  correct.
 463
 464    type Ctrl is new Int;
 465
 466    Uint_Direct_Bias  : constant Ctrl := Ctrl (Uint_Low_Bound) + Ctrl (Base);
 467    Uint_Direct_First : constant Ctrl := Uint_Direct_Bias + Ctrl (Min_Direct);
 468    Uint_Direct_Last  : constant Ctrl := Uint_Direct_Bias + Ctrl (Max_Direct);
 469
 470    Uint_0   : constant Uint := Uint (Uint_Direct_Bias + 0);
 471    Uint_1   : constant Uint := Uint (Uint_Direct_Bias + 1);
 472    Uint_2   : constant Uint := Uint (Uint_Direct_Bias + 2);
 473    Uint_3   : constant Uint := Uint (Uint_Direct_Bias + 3);
 474    Uint_4   : constant Uint := Uint (Uint_Direct_Bias + 4);
 475    Uint_5   : constant Uint := Uint (Uint_Direct_Bias + 5);
 476    Uint_6   : constant Uint := Uint (Uint_Direct_Bias + 6);
 477    Uint_7   : constant Uint := Uint (Uint_Direct_Bias + 7);
 478    Uint_8   : constant Uint := Uint (Uint_Direct_Bias + 8);
 479    Uint_9   : constant Uint := Uint (Uint_Direct_Bias + 9);
 480    Uint_10  : constant Uint := Uint (Uint_Direct_Bias + 10);
 481    Uint_11  : constant Uint := Uint (Uint_Direct_Bias + 11);
 482    Uint_12  : constant Uint := Uint (Uint_Direct_Bias + 12);
 483    Uint_13  : constant Uint := Uint (Uint_Direct_Bias + 13);
 484    Uint_14  : constant Uint := Uint (Uint_Direct_Bias + 14);
 485    Uint_15  : constant Uint := Uint (Uint_Direct_Bias + 15);
 486    Uint_16  : constant Uint := Uint (Uint_Direct_Bias + 16);
 487    Uint_24  : constant Uint := Uint (Uint_Direct_Bias + 24);
 488    Uint_32  : constant Uint := Uint (Uint_Direct_Bias + 32);
 489    Uint_63  : constant Uint := Uint (Uint_Direct_Bias + 63);
 490    Uint_64  : constant Uint := Uint (Uint_Direct_Bias + 64);
 491    Uint_80  : constant Uint := Uint (Uint_Direct_Bias + 80);
 492    Uint_128 : constant Uint := Uint (Uint_Direct_Bias + 128);
 493
 494    Uint_Minus_1   : constant Uint := Uint (Uint_Direct_Bias - 1);
 495    Uint_Minus_2   : constant Uint := Uint (Uint_Direct_Bias - 2);
 496    Uint_Minus_3   : constant Uint := Uint (Uint_Direct_Bias - 3);
 497    Uint_Minus_4   : constant Uint := Uint (Uint_Direct_Bias - 4);
 498    Uint_Minus_5   : constant Uint := Uint (Uint_Direct_Bias - 5);
 499    Uint_Minus_6   : constant Uint := Uint (Uint_Direct_Bias - 6);
 500    Uint_Minus_7   : constant Uint := Uint (Uint_Direct_Bias - 7);
 501    Uint_Minus_8   : constant Uint := Uint (Uint_Direct_Bias - 8);
 502    Uint_Minus_9   : constant Uint := Uint (Uint_Direct_Bias - 9);
 503    Uint_Minus_12  : constant Uint := Uint (Uint_Direct_Bias - 12);
 504    Uint_Minus_36  : constant Uint := Uint (Uint_Direct_Bias - 36);
 505    Uint_Minus_63  : constant Uint := Uint (Uint_Direct_Bias - 63);
 506    Uint_Minus_80  : constant Uint := Uint (Uint_Direct_Bias - 80);
 507    Uint_Minus_128 : constant Uint := Uint (Uint_Direct_Bias - 128);
 508
 509    Uint_Max_Simple_Mul : constant := Uint_Direct_Bias + 2**15;
 510    --  If two values are directly represented and less than or equal to this
 511    --  value, then we know the product fits in a 32-bit integer. This allows
 512    --  UI_Mul to efficiently compute the product in this case.
 513
 514    type Save_Mark is record
 515       Save_Uint   : Uint;
 516       Save_Udigit : Int;
 517    end record;
 518
 519    --  Values outside the range that is represented directly are stored using
 520    --  two tables. The secondary table Udigits contains sequences of Int values
 521    --  consisting of the digits of the number in a radix Base system. The
 522    --  digits are stored from most significant to least significant with the
 523    --  first digit only carrying the sign.
 524
 525    --  There is one entry in the primary Uints table for each distinct Uint
 526    --  value. This table entry contains the length (number of digits) and
 527    --  a starting offset of the value in the Udigits table.
 528
 529    Uint_First_Entry : constant Uint := Uint (Uint_Table_Start);
 530
 531    --  Some subprograms defined in this package manipulate the Udigits table
 532    --  directly, while for others it is more convenient to work with locally
 533    --  defined arrays of the digits of the Universal Integers. The type
 534    --  UI_Vector is defined for this purpose and some internal subprograms
 535    --  used for converting from one to the other are defined.
 536
 537    type Uint_Entry is record
 538       Length : Pos;
 539       --  Length of entry in Udigits table in digits (i.e. in words)
 540
 541       Loc : Int;
 542       --  Starting location in Udigits table of this Uint value
 543    end record;
 544
 545    package Uints is new Table.Table (
 546      Table_Component_Type => Uint_Entry,
 547      Table_Index_Type     => Uint'Base,
 548      Table_Low_Bound      => Uint_First_Entry,
 549      Table_Initial        => Alloc.Uints_Initial,
 550      Table_Increment      => Alloc.Uints_Increment,
 551      Table_Name           => "Uints");
 552
 553    package Udigits is new Table.Table (
 554      Table_Component_Type => Int,
 555      Table_Index_Type     => Int,
 556      Table_Low_Bound      => 0,
 557      Table_Initial        => Alloc.Udigits_Initial,
 558      Table_Increment      => Alloc.Udigits_Increment,
 559      Table_Name           => "Udigits");
 560
 561    --  Note: the reason these tables are defined here in the private part of
 562    --  the spec, rather than in the body, is that they are referenced directly
 563    --  by gigi.
 564
 565 end Uintp;