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
floor_log2(unsigned HOST_WIDE_INT x)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
ceil_log2(unsigned HOST_WIDE_INT x)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
exact_log2(unsigned HOST_WIDE_INT x)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
ctz_hwi(unsigned HOST_WIDE_INT x)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
clz_hwi(unsigned HOST_WIDE_INT x)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
ffs_hwi(unsigned HOST_WIDE_INT x)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
popcount_hwi(unsigned HOST_WIDE_INT x)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
gcd(HOST_WIDE_INT a,HOST_WIDE_INT b)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
pos_mul_hwi(HOST_WIDE_INT x,HOST_WIDE_INT y)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
mul_hwi(HOST_WIDE_INT x,HOST_WIDE_INT y)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
least_common_multiple(HOST_WIDE_INT a,HOST_WIDE_INT b)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