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