gcc/sreal.c

   1 /* Simple data type for real numbers for the GNU compiler.
   2    Copyright (C) 2002-2017 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 /* This library supports real numbers;
  21    inf and nan are NOT supported.
  22    It is written to be simple and fast.
  23
  24    Value of sreal is
  25         x = sig * 2 ^ exp
  26    where
  27         sig = significant
  28           (for < 64-bit machines sig = sig_lo + sig_hi * 2 ^ SREAL_PART_BITS)
  29         exp = exponent
  30
  31    One uint64_t is used for the significant.
  32    Only a half of significant bits is used (in normalized sreals) so that we do
  33    not have problems with overflow, for example when c->sig = a->sig * b->sig.
  34    So the precision is 32-bit.
  35
  36    Invariant: The numbers are normalized before and after each call of sreal_*.
  37
  38    Normalized sreals:
  39    All numbers (except zero) meet following conditions:
  40          SREAL_MIN_SIG <= sig && sig <= SREAL_MAX_SIG
  41         -SREAL_MAX_EXP <= exp && exp <= SREAL_MAX_EXP
  42
  43    If the number would be too large, it is set to upper bounds of these
  44    conditions.
  45
  46    If the number is zero or would be too small it meets following conditions:
  47         sig == 0 && exp == -SREAL_MAX_EXP
  48 */
  49
  50 #include "config.h"
  51 #include "system.h"
  52 #include <math.h>
  53 #include "coretypes.h"
  54 #include "sreal.h"
  55 #include "selftest.h"
  56
  57 /* Print the content of struct sreal.  */
  58
  59 void
  60 sreal::dump (FILE *file) const
  61 {
  62   fprintf (file, "(%" PRIi64 " * 2^%d)", m_sig, m_exp);
  63 }
  64
  65 DEBUG_FUNCTION void
  66 debug (const sreal &ref)
  67 {
  68   ref.dump (stderr);
  69 }
  70
  71 DEBUG_FUNCTION void
  72 debug (const sreal *ptr)
  73 {
  74   if (ptr)
  75     debug (*ptr);
  76   else
  77     fprintf (stderr, "<nil>\n");
  78 }
  79
  80 /* Shift this right by S bits.  Needed: 0 < S <= SREAL_BITS.
  81    When the most significant bit shifted out is 1, add 1 to this (rounding).
  82    */
  83
  84 void
  85 sreal::shift_right (int s)
  86 {
  87   gcc_checking_assert (s > 0);
  88   gcc_checking_assert (s <= SREAL_BITS);
  89   /* Exponent should never be so large because shift_right is used only by
  90      sreal_add and sreal_sub ant thus the number cannot be shifted out from
  91      exponent range.  */
  92   gcc_checking_assert (m_exp + s <= SREAL_MAX_EXP);
  93
  94   m_exp += s;
  95
  96   m_sig += (int64_t) 1 << (s - 1);
  97   m_sig >>= s;
  98 }
  99
 100 /* Return integer value of *this.  */
 101
 102 int64_t
 103 sreal::to_int () const
 104 {
 105   int64_t sign = SREAL_SIGN (m_sig);
 106
 107   if (m_exp <= -SREAL_BITS)
 108     return 0;
 109   if (m_exp >= SREAL_PART_BITS)
 110     return sign * INTTYPE_MAXIMUM (int64_t);
 111   if (m_exp > 0)
 112     return sign * (SREAL_ABS (m_sig) << m_exp);
 113   if (m_exp < 0)
 114     return m_sig >> -m_exp;
 115   return m_sig;
 116 }
 117
 118 /* Return value of *this as double.
 119    This should be used for debug output only.  */
 120
 121 double
 122 sreal::to_double () const
 123 {
 124   double val = m_sig;
 125   if (m_exp)
 126     val = ldexp (val, m_exp);
 127   return val;
 128 }
 129
 130 /* Return *this + other.  */
 131
 132 sreal
 133 sreal::operator+ (const sreal &other) const
 134 {
 135   int dexp;
 136   sreal tmp, r;
 137
 138   const sreal *a_p = this, *b_p = &other, *bb;
 139
 140   if (a_p->m_exp < b_p->m_exp)
 141     std::swap (a_p, b_p);
 142
 143   dexp = a_p->m_exp - b_p->m_exp;
 144   r.m_exp = a_p->m_exp;
 145   if (dexp > SREAL_BITS)
 146     {
 147       r.m_sig = a_p->m_sig;
 148       return r;
 149     }
 150
 151   if (dexp == 0)
 152     bb = b_p;
 153   else
 154     {
 155       tmp = *b_p;
 156       tmp.shift_right (dexp);
 157       bb = &tmp;
 158     }
 159
 160   r.m_sig = a_p->m_sig + bb->m_sig;
 161   r.normalize ();
 162   return r;
 163 }
 164
 165
 166 /* Return *this - other.  */
 167
 168 sreal
 169 sreal::operator- (const sreal &other) const
 170 {
 171   int dexp;
 172   sreal tmp, r;
 173   const sreal *bb;
 174   const sreal *a_p = this, *b_p = &other;
 175
 176   int64_t sign = 1;
 177   if (a_p->m_exp < b_p->m_exp)
 178     {
 179       sign = -1;
 180       std::swap (a_p, b_p);
 181     }
 182
 183   dexp = a_p->m_exp - b_p->m_exp;
 184   r.m_exp = a_p->m_exp;
 185   if (dexp > SREAL_BITS)
 186     {
 187       r.m_sig = sign * a_p->m_sig;
 188       return r;
 189     }
 190   if (dexp == 0)
 191     bb = b_p;
 192   else
 193     {
 194       tmp = *b_p;
 195       tmp.shift_right (dexp);
 196       bb = &tmp;
 197     }
 198
 199   r.m_sig = sign * (a_p->m_sig - bb->m_sig);
 200   r.normalize ();
 201   return r;
 202 }
 203
 204 /* Return *this * other.  */
 205
 206 sreal
 207 sreal::operator* (const sreal &other) const
 208 {
 209   sreal r;
 210   if (absu_hwi (m_sig) < SREAL_MIN_SIG || absu_hwi (other.m_sig) < SREAL_MIN_SIG)
 211     {
 212       r.m_sig = 0;
 213       r.m_exp = -SREAL_MAX_EXP;
 214     }
 215   else
 216     {
 217       r.m_sig = m_sig * other.m_sig;
 218       r.m_exp = m_exp + other.m_exp;
 219       r.normalize ();
 220     }
 221
 222   return r;
 223 }
 224
 225 /* Return *this / other.  */
 226
 227 sreal
 228 sreal::operator/ (const sreal &other) const
 229 {
 230   gcc_checking_assert (other.m_sig != 0);
 231   sreal r;
 232   r.m_sig
 233     = SREAL_SIGN (m_sig) * (SREAL_ABS (m_sig) << SREAL_PART_BITS) / other.m_sig;
 234   r.m_exp = m_exp - other.m_exp - SREAL_PART_BITS;
 235   r.normalize ();
 236   return r;
 237 }
 238
 239 #if CHECKING_P
 240
 241 namespace selftest {
 242
 243 /* Selftests for sreals.  */
 244
 245 /* Verify basic sreal operations.  */
 246
 247 static void
 248 sreal_verify_basics (void)
 249 {
 250   sreal minimum = INT_MIN;
 251   sreal maximum = INT_MAX;
 252
 253   sreal seven = 7;
 254   sreal minus_two = -2;
 255   sreal minus_nine = -9;
 256
 257   ASSERT_EQ (INT_MIN, minimum.to_int ());
 258   ASSERT_EQ (INT_MAX, maximum.to_int ());
 259
 260   ASSERT_FALSE (minus_two < minus_two);
 261   ASSERT_FALSE (seven < seven);
 262   ASSERT_TRUE (seven > minus_two);
 263   ASSERT_TRUE (minus_two < seven);
 264   ASSERT_TRUE (minus_two != seven);
 265   ASSERT_EQ (minus_two, -2);
 266   ASSERT_EQ (seven, 7);
 267   ASSERT_EQ ((seven << 10) >> 10, 7);
 268   ASSERT_EQ (seven + minus_nine, -2);
 269 }
 270
 271 /* Helper function that performs basic arithmetics and comparison
 272    of given arguments A and B.  */
 273
 274 static void
 275 verify_aritmetics (int64_t a, int64_t b)
 276 {
 277   ASSERT_EQ (a, -(-(sreal (a))).to_int ());
 278   ASSERT_EQ (a < b, sreal (a) < sreal (b));
 279   ASSERT_EQ (a <= b, sreal (a) <= sreal (b));
 280   ASSERT_EQ (a == b, sreal (a) == sreal (b));
 281   ASSERT_EQ (a != b, sreal (a) != sreal (b));
 282   ASSERT_EQ (a > b, sreal (a) > sreal (b));
 283   ASSERT_EQ (a >= b, sreal (a) >= sreal (b));
 284   ASSERT_EQ (a + b, (sreal (a) + sreal (b)).to_int ());
 285   ASSERT_EQ (a - b, (sreal (a) - sreal (b)).to_int ());
 286   ASSERT_EQ (b + a, (sreal (b) + sreal (a)).to_int ());
 287   ASSERT_EQ (b - a, (sreal (b) - sreal (a)).to_int ());
 288 }
 289
 290 /* Verify arithmetics for interesting numbers.  */
 291
 292 static void
 293 sreal_verify_arithmetics (void)
 294 {
 295   int values[] = {-14123413, -7777, -17, -10, -2, 0, 17, 139, 1234123};
 296   unsigned c = sizeof (values) / sizeof (int);
 297
 298   for (unsigned i = 0; i < c; i++)
 299     for (unsigned j = 0; j < c; j++)
 300       {
 301         int a = values[i];
 302         int b = values[j];
 303
 304         verify_aritmetics (a, b);
 305       }
 306 }
 307
 308 /* Helper function that performs various shifting test of a given
 309    argument A.  */
 310
 311 static void
 312 verify_shifting (int64_t a)
 313 {
 314   sreal v = a;
 315
 316   for (unsigned i = 0; i < 16; i++)
 317     ASSERT_EQ (a << i, (v << i).to_int());
 318
 319   a = a << 16;
 320   v = v << 16;
 321
 322   for (unsigned i = 0; i < 16; i++)
 323     ASSERT_EQ (a >> i, (v >> i).to_int());
 324 }
 325
 326 /* Verify shifting for interesting numbers.  */
 327
 328 static void
 329 sreal_verify_shifting (void)
 330 {
 331   int values[] = {0, 17, 32, 139, 1024, 55555, 1234123};
 332   unsigned c = sizeof (values) / sizeof (int);
 333
 334   for (unsigned i = 0; i < c; i++)
 335     verify_shifting (values[i]);
 336 }
 337
 338 /* Verify division by (of) a negative value.  */
 339
 340 static void
 341 sreal_verify_negative_division (void)
 342 {
 343   ASSERT_EQ (sreal (1) / sreal (1), sreal (1));
 344   ASSERT_EQ (sreal (-1) / sreal (-1), sreal (1));
 345   ASSERT_EQ (sreal (-1234567) / sreal (-1234567), sreal (1));
 346   ASSERT_EQ (sreal (-1234567) / sreal (1234567), sreal (-1));
 347   ASSERT_EQ (sreal (1234567) / sreal (-1234567), sreal (-1));
 348 }
 349
 350 /* Run all of the selftests within this file.  */
 351
 352 void sreal_c_tests ()
 353 {
 354   sreal_verify_basics ();
 355   sreal_verify_arithmetics ();
 356   sreal_verify_shifting ();
 357   sreal_verify_negative_division ();
 358 }
 359
 360 } // namespace selftest
 361 #endif /* CHECKING_P */