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 } 207