1/* Operations on HOST_WIDE_INT. 2 Copyright (C) 1987-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along 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 35int 36floor_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 65int 66ceil_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 74int 75exact_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 85int 86ctz_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 93int 94clz_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 102int 103ffs_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 110int 111popcount_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 131HOST_WIDE_INT 132gcd (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 152HOST_WIDE_INT 153pos_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 164HOST_WIDE_INT 165mul_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 186HOST_WIDE_INT 187least_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