gcc/hwint.c

   1 /* Operations on HOST_WIDE_INT.
   2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "diagnostic-core.h"
  25
  26 #if GCC_VERSION < 3004
  27
  28 /* The functions clz_hwi, ctz_hwi, ffs_hwi, floor_log2, ceil_log2,
  29    and exact_log2 are defined as inline functions in hwint.h
  30    if GCC_VERSION >= 3004.
  31    The definitions here are used for older versions of GCC and
  32    non-GCC bootstrap compilers.  */
  33
  34 /* Given X, an unsigned number, return the largest int Y such that 2**Y <= X.
  35    If X is 0, return -1.  */
  36
  37 int
  38 floor_log2 (unsigned HOST_WIDE_INT x)
  39 {
  40   int t = 0;
  41
  42   if (x == 0)
  43     return -1;
  44
  45   if (HOST_BITS_PER_WIDE_INT > 64)
  46     if (x >= (unsigned HOST_WIDE_INT) 1 << (t + 64))
  47       t += 64;
  48   if (HOST_BITS_PER_WIDE_INT > 32)
  49     if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 32))
  50       t += 32;
  51   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 16))
  52     t += 16;
  53   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 8))
  54     t += 8;
  55   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 4))
  56     t += 4;
  57   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 2))
  58     t += 2;
  59   if (x >= ((unsigned HOST_WIDE_INT) 1) << (t + 1))
  60     t += 1;
  61
  62   return t;
  63 }
  64
  65 /* Given X, an unsigned number, return the largest Y such that 2**Y >= X.  */
  66
  67 int
  68 ceil_log2 (unsigned HOST_WIDE_INT x)
  69 {
  70   return floor_log2 (x - 1) + 1;
  71 }
  72
  73 /* Return the logarithm of X, base 2, considering X unsigned,
  74    if X is a power of 2.  Otherwise, returns -1.  */
  75
  76 int
  77 exact_log2 (unsigned HOST_WIDE_INT x)
  78 {
  79   if (x != (x & -x))
  80     return -1;
  81   return floor_log2 (x);
  82 }
  83
  84 /* Given X, an unsigned number, return the number of least significant bits
  85    that are zero.  When X == 0, the result is the word size.  */
  86
  87 int
  88 ctz_hwi (unsigned HOST_WIDE_INT x)
  89 {
  90   return x ? floor_log2 (x & -x) : HOST_BITS_PER_WIDE_INT;
  91 }
  92
  93 /* Similarly for most significant bits.  */
  94
  95 int
  96 clz_hwi (unsigned HOST_WIDE_INT x)
  97 {
  98   return HOST_BITS_PER_WIDE_INT - 1 - floor_log2(x);
  99 }
 100
 101 /* Similar to ctz_hwi, except that the least significant bit is numbered
 102    starting from 1, and X == 0 yields 0.  */
 103
 104 int
 105 ffs_hwi (unsigned HOST_WIDE_INT x)
 106 {
 107   return 1 + floor_log2 (x & -x);
 108 }
 109
 110 /* Return the number of set bits in X.  */
 111
 112 int
 113 popcount_hwi (unsigned HOST_WIDE_INT x)
 114 {
 115   int i, ret = 0;
 116   size_t bits = sizeof (x) * CHAR_BIT;
 117
 118   for (i = 0; i < bits; i += 1)
 119     {
 120       ret += x & 1;
 121       x >>= 1;
 122     }
 123
 124   return ret;
 125 }
 126
 127 #endif /* GCC_VERSION < 3004 */
 128
 129 /* Compute the absolute value of X.  */
 130
 131 HOST_WIDE_INT
 132 abs_hwi (HOST_WIDE_INT x)
 133 {
 134   gcc_checking_assert (x != HOST_WIDE_INT_MIN);
 135   return x >= 0 ? x : -x;
 136 }
 137
 138 /* Compute the absolute value of X as an unsigned type.  */
 139
 140 unsigned HOST_WIDE_INT
 141 absu_hwi (HOST_WIDE_INT x)
 142 {
 143   return x >= 0 ? (unsigned HOST_WIDE_INT)x : -(unsigned HOST_WIDE_INT)x;
 144 }
 145
 146 /* Compute the greatest common divisor of two numbers A and B using
 147    Euclid's algorithm.  */
 148
 149 HOST_WIDE_INT
 150 gcd (HOST_WIDE_INT a, HOST_WIDE_INT b)
 151 {
 152   HOST_WIDE_INT x, y, z;
 153
 154   x = abs_hwi (a);
 155   y = abs_hwi (b);
 156
 157   while (x > 0)
 158     {
 159       z = y % x;
 160       y = x;
 161       x = z;
 162     }
 163
 164   return y;
 165 }
 166
 167 /* For X and Y positive integers, return X multiplied by Y and check
 168    that the result does not overflow.  */
 169
 170 HOST_WIDE_INT
 171 pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
 172 {
 173   if (x != 0)
 174     gcc_checking_assert ((HOST_WIDE_INT_MAX) / x >= y);
 175
 176   return x * y;
 177 }
 178
 179 /* Return X multiplied by Y and check that the result does not
 180    overflow.  */
 181
 182 HOST_WIDE_INT
 183 mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
 184 {
 185   gcc_checking_assert (x != HOST_WIDE_INT_MIN
 186                        && y != HOST_WIDE_INT_MIN);
 187
 188   if (x >= 0)
 189     {
 190       if (y >= 0)
 191         return pos_mul_hwi (x, y);
 192
 193       return -pos_mul_hwi (x, -y);
 194     }
 195
 196   if (y >= 0)
 197     return -pos_mul_hwi (-x, y);
 198
 199   return pos_mul_hwi (-x, -y);
 200 }
 201
 202 /* Compute the least common multiple of two numbers A and B .  */
 203
 204 HOST_WIDE_INT
 205 least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b)
 206 {
 207   return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b));
 208 }