gcc/hwint.c

   1 /* Operations on HOST_WIDE_INT.
   2    Copyright (C) 1987-2013 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 #include "config.h"
  21 #include "system.h"
  22 #include "diagnostic-core.h"
  23
  24 #if GCC_VERSION < 3004
  25
  26 /* The functions clz_hwi, ctz_hwi, ffs_hwi, floor_log2, ceil_log2,
  27    and exact_log2 are defined as inline functions in hwint.h
  28    if GCC_VERSION >= 3004.
  29    The definitions here are used for older versions of GCC and
  30    non-GCC bootstrap compilers.  */
  31
  32 /* Given X, an unsigned number, return the largest int Y such that 2**Y <= X.
  33    If X is 0, return -1.  */
  34
  35 int
  36 floor_log2 (unsigned HOST_WIDE_INT x)
  37 {
  38   int t = 0;
  39
  40   if (x == 0)
  41     return -1;
  42
  43   if (HOST_BITS_PER_WIDE_INT > 64)
  44     if (x >= (unsigned HOST_WIDE_INT) 1 << (t + 64))
  45       t += 64;
  46   if (HOST_BITS_PER_WIDE_INT > 32)
  47     if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 32))
  48       t += 32;
  49   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 16))
  50     t += 16;
  51   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 8))
  52     t += 8;
  53   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 4))
  54     t += 4;
  55   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 2))
  56     t += 2;
  57   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 1))
  58     t += 1;
  59
  60   return t;
  61 }
  62
  63 /* Given X, an unsigned number, return the largest Y such that 2**Y >= X.  */
  64
  65 int
  66 ceil_log2 (unsigned HOST_WIDE_INT x)
  67 {
  68   return floor_log2 (x - 1) + 1;
  69 }
  70
  71 /* Return the logarithm of X, base 2, considering X unsigned,
  72    if X is a power of 2.  Otherwise, returns -1.  */
  73
  74 int
  75 exact_log2 (unsigned HOST_WIDE_INT x)
  76 {
  77   if (x != (x & -x))
  78     return -1;
  79   return floor_log2 (x);
  80 }
  81
  82 /* Given X, an unsigned number, return the number of least significant bits
  83    that are zero.  When X == 0, the result is the word size.  */
  84
  85 int
  86 ctz_hwi (unsigned HOST_WIDE_INT x)
  87 {
  88   return x ? floor_log2 (x & -x) : HOST_BITS_PER_WIDE_INT;
  89 }
  90
  91 /* Similarly for most significant bits.  */
  92
  93 int
  94 clz_hwi (unsigned HOST_WIDE_INT x)
  95 {
  96   return HOST_BITS_PER_WIDE_INT - 1 - floor_log2(x);
  97 }
  98
  99 /* Similar to ctz_hwi, except that the least significant bit is numbered
 100    starting from 1, and X == 0 yields 0.  */
 101
 102 int
 103 ffs_hwi (unsigned HOST_WIDE_INT x)
 104 {
 105   return 1 + floor_log2 (x & -x);
 106 }
 107
 108 /* Return the number of set bits in X.  */
 109
 110 int
 111 popcount_hwi (unsigned HOST_WIDE_INT x)
 112 {
 113   int i, ret = 0;
 114   size_t bits = sizeof (x) * CHAR_BIT;
 115
 116   for (i = 0; i < bits; i += 1)
 117     {
 118       ret += x & 1;
 119       x >>= 1;
 120     }
 121
 122   return ret;
 123 }
 124
 125 #endif /* GCC_VERSION < 3004 */
 126
 127 /* Compute the absolute value of X.  */
 128
 129 HOST_WIDE_INT
 130 abs_hwi (HOST_WIDE_INT x)
 131 {
 132   gcc_checking_assert (x != HOST_WIDE_INT_MIN);
 133   return x >= 0 ? x : -x;
 134 }
 135
 136 /* Compute the absolute value of X as an unsigned type.  */
 137
 138 unsigned HOST_WIDE_INT
 139 absu_hwi (HOST_WIDE_INT x)
 140 {
 141   return x >= 0 ? (unsigned HOST_WIDE_INT)x : -(unsigned HOST_WIDE_INT)x;
 142 }
 143
 144 /* Compute the greatest common divisor of two numbers A and B using
 145    Euclid's algorithm.  */
 146
 147 HOST_WIDE_INT
 148 gcd (HOST_WIDE_INT a, HOST_WIDE_INT b)
 149 {
 150   HOST_WIDE_INT x, y, z;
 151
 152   x = abs_hwi (a);
 153   y = abs_hwi (b);
 154
 155   while (x > 0)
 156     {
 157       z = y % x;
 158       y = x;
 159       x = z;
 160     }
 161
 162   return y;
 163 }
 164
 165 /* For X and Y positive integers, return X multiplied by Y and check
 166    that the result does not overflow.  */
 167
 168 HOST_WIDE_INT
 169 pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
 170 {
 171   if (x != 0)
 172     gcc_checking_assert ((HOST_WIDE_INT_MAX) / x >= y);
 173
 174   return x * y;
 175 }
 176
 177 /* Return X multiplied by Y and check that the result does not
 178    overflow.  */
 179
 180 HOST_WIDE_INT
 181 mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
 182 {
 183   gcc_checking_assert (x != HOST_WIDE_INT_MIN
 184                        && y != HOST_WIDE_INT_MIN);
 185
 186   if (x >= 0)
 187     {
 188       if (y >= 0)
 189         return pos_mul_hwi (x, y);
 190
 191       return -pos_mul_hwi (x, -y);
 192     }
 193
 194   if (y >= 0)
 195     return -pos_mul_hwi (-x, y);
 196
 197   return pos_mul_hwi (-x, -y);
 198 }
 199
 200 /* Compute the least common multiple of two numbers A and B .  */
 201
 202 HOST_WIDE_INT
 203 least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b)
 204 {
 205   return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b));
 206 }