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