1 | /* Operations on HOST_WIDE_INT. |
---|---|

2 | Copyright (C) 1987-2017 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 |