1 /* Operations on HOST_WIDE_INT. 2 Copyright (C) 1987-2018 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 "coretypes.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 >= HOST_WIDE_INT_1U << (t + 64)) 45 t += 64; 46 if (HOST_BITS_PER_WIDE_INT > 32) 47 if (x >= HOST_WIDE_INT_1U << (t + 32)) 48 t += 32; 49 if (x >= HOST_WIDE_INT_1U << (t + 16)) 50 t += 16; 51 if (x >= HOST_WIDE_INT_1U << (t + 8)) 52 t += 8; 53 if (x >= HOST_WIDE_INT_1U << (t + 4)) 54 t += 4; 55 if (x >= HOST_WIDE_INT_1U << (t + 2)) 56 t += 2; 57 if (x >= HOST_WIDE_INT_1U << (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 (!pow2p_hwi (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 (least_bit_hwi (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 (least_bit_hwi (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 128 /* Compute the greatest common divisor of two numbers A and B using 129 Euclid's algorithm. */ 130 131 HOST_WIDE_INT 132 gcd (HOST_WIDE_INT a, HOST_WIDE_INT b) 133 { 134 HOST_WIDE_INT x, y, z; 135 136 x = abs_hwi (a); 137 y = abs_hwi (b); 138 139 while (x > 0) 140 { 141 z = y % x; 142 y = x; 143 x = z; 144 } 145 146 return y; 147 } 148 149 /* For X and Y positive integers, return X multiplied by Y and check 150 that the result does not overflow. */ 151 152 HOST_WIDE_INT 153 pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y) 154 { 155 if (x != 0) 156 gcc_checking_assert ((HOST_WIDE_INT_MAX) / x >= y); 157 158 return x * y; 159 } 160 161 /* Return X multiplied by Y and check that the result does not 162 overflow. */ 163 164 HOST_WIDE_INT 165 mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y) 166 { 167 gcc_checking_assert (x != HOST_WIDE_INT_MIN 168 && y != HOST_WIDE_INT_MIN); 169 170 if (x >= 0) 171 { 172 if (y >= 0) 173 return pos_mul_hwi (x, y); 174 175 return -pos_mul_hwi (x, -y); 176 } 177 178 if (y >= 0) 179 return -pos_mul_hwi (-x, y); 180 181 return pos_mul_hwi (-x, -y); 182 } 183 184 /* Compute the least common multiple of two numbers A and B . */ 185 186 HOST_WIDE_INT 187 least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b) 188 { 189 return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b)); 190 } 191