gcc/sreal.c

   1 /* Simple data type for real numbers for the GNU compiler.
   2    Copyright (C) 2002-2016 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 = m_sig < 0 ? -1 : 1;
 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 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 = (m_sig << SREAL_PART_BITS) / other.m_sig;
 233   r.m_exp = m_exp - other.m_exp - SREAL_PART_BITS;
 234   r.normalize ();
 235   return r;
 236 }
 237
 238 #if CHECKING_P
 239
 240 namespace selftest {
 241
 242 /* Selftests for sreals.  */
 243
 244 /* Verify basic sreal operations.  */
 245
 246 static void
 247 sreal_verify_basics (void)
 248 {
 249   sreal minimum = INT_MIN;
 250   sreal maximum = INT_MAX;
 251
 252   sreal seven = 7;
 253   sreal minus_two = -2;
 254   sreal minus_nine = -9;
 255
 256   ASSERT_EQ (INT_MIN, minimum.to_int ());
 257   ASSERT_EQ (INT_MAX, maximum.to_int ());
 258
 259   ASSERT_FALSE (minus_two < minus_two);
 260   ASSERT_FALSE (seven < seven);
 261   ASSERT_TRUE (seven > minus_two);
 262   ASSERT_TRUE (minus_two < seven);
 263   ASSERT_TRUE (minus_two != seven);
 264   ASSERT_EQ (minus_two, -2);
 265   ASSERT_EQ (seven, 7);
 266   ASSERT_EQ ((seven << 10) >> 10, 7);
 267   ASSERT_EQ (seven + minus_nine, -2);
 268 }
 269
 270 /* Helper function that performs basic arithmetics and comparison
 271    of given arguments A and B.  */
 272
 273 static void
 274 verify_aritmetics (int64_t a, int64_t b)
 275 {
 276   ASSERT_EQ (a, -(-(sreal (a))).to_int ());
 277   ASSERT_EQ (a < b, sreal (a) < sreal (b));
 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)).to_int ());
 284   ASSERT_EQ (a - b, (sreal (a) - sreal (b)).to_int ());
 285   ASSERT_EQ (b + a, (sreal (b) + sreal (a)).to_int ());
 286   ASSERT_EQ (b - a, (sreal (b) - sreal (a)).to_int ());
 287 }
 288
 289 /* Verify arithmetics for interesting numbers.  */
 290
 291 static void
 292 sreal_verify_arithmetics (void)
 293 {
 294   int values[] = {-14123413, -7777, -17, -10, -2, 0, 17, 139, 1234123};
 295   unsigned c = sizeof (values) / sizeof (int);
 296
 297   for (unsigned i = 0; i < c; i++)
 298     for (unsigned j = 0; j < c; j++)
 299       {
 300         int a = values[i];
 301         int b = values[j];
 302
 303         verify_aritmetics (a, b);
 304       }
 305 }
 306
 307 /* Helper function that performs various shifting test of a given
 308    argument A.  */
 309
 310 static void
 311 verify_shifting (int64_t a)
 312 {
 313   sreal v = a;
 314
 315   for (unsigned i = 0; i < 16; i++)
 316     ASSERT_EQ (a << i, (v << i).to_int());
 317
 318   a = a << 16;
 319   v = v << 16;
 320
 321   for (unsigned i = 0; i < 16; i++)
 322     ASSERT_EQ (a >> i, (v >> i).to_int());
 323 }
 324
 325 /* Verify shifting for interesting numbers.  */
 326
 327 static void
 328 sreal_verify_shifting (void)
 329 {
 330   int values[] = {0, 17, 32, 139, 1024, 55555, 1234123};
 331   unsigned c = sizeof (values) / sizeof (int);
 332
 333   for (unsigned i = 0; i < c; i++)
 334     verify_shifting (values[i]);
 335 }
 336
 337 /* Run all of the selftests within this file.  */
 338
 339 void sreal_c_tests ()
 340 {
 341   sreal_verify_basics ();
 342   sreal_verify_arithmetics ();
 343   sreal_verify_shifting ();
 344 }
 345
 346 } // namespace selftest
 347 #endif /* CHECKING_P */