Mercurial > hg > CbC > CbC_gcc

annotate gcc/hwint.c @ 145:1830386684a0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-9.2.0
author anatofuz
date Thu, 13 Feb 2020 11:34:05 +0900
parents 84e7813d76e9
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 /* Operations on HOST_WIDE_INT.
145
1830386684a0 gcc-9.2.0
anatofuz
parents: 131
diff changeset
2 Copyright (C) 1987-2020 Free Software Foundation, Inc.
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 This file is part of GCC.
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 GCC is free software; you can redistribute it and/or modify it under
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 the terms of the GNU General Public License as published by the Free
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 Software Foundation; either version 3, or (at your option) any later
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 version.
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 for more details.
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 You should have received a copy of the GNU General Public License
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 along with GCC; see the file COPYING3. If not see
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 <http://www.gnu.org/licenses/>. */
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 #include "config.h"
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 #include "system.h"
111
kono
parents: 68
diff changeset
22 #include "coretypes.h"
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 #if GCC_VERSION < 3004
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25
111
kono
parents: 68
diff changeset
26 /* The functions clz_hwi, ctz_hwi, ffs_hwi, floor_log2, ceil_log2,
kono
parents: 68
diff changeset
27 and exact_log2 are defined as inline functions in hwint.h
kono
parents: 68
diff changeset
28 if GCC_VERSION >= 3004.
kono
parents: 68
diff changeset
29 The definitions here are used for older versions of GCC and
kono
parents: 68
diff changeset
30 non-GCC bootstrap compilers. */
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 /* Given X, an unsigned number, return the largest int Y such that 2**Y <= X.
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 If X is 0, return -1. */
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
34
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 int
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 floor_log2 (unsigned HOST_WIDE_INT x)
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 {
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 int t = 0;
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 if (x == 0)
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 return -1;
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
42
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 if (HOST_BITS_PER_WIDE_INT > 64)
111
kono
parents: 68
diff changeset
44 if (x >= HOST_WIDE_INT_1U << (t + 64))
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 t += 64;
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 if (HOST_BITS_PER_WIDE_INT > 32)
111
kono
parents: 68
diff changeset
47 if (x >= HOST_WIDE_INT_1U << (t + 32))
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 t += 32;
111
kono
parents: 68
diff changeset
49 if (x >= HOST_WIDE_INT_1U << (t + 16))
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 t += 16;
111
kono
parents: 68
diff changeset
51 if (x >= HOST_WIDE_INT_1U << (t + 8))
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 t += 8;
111
kono
parents: 68
diff changeset
53 if (x >= HOST_WIDE_INT_1U << (t + 4))
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 t += 4;
111
kono
parents: 68
diff changeset
55 if (x >= HOST_WIDE_INT_1U << (t + 2))
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 t += 2;
111
kono
parents: 68
diff changeset
57 if (x >= HOST_WIDE_INT_1U << (t + 1))
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 t += 1;
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 return t;
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 }
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
62
131
84e7813d76e9 gcc-8.2
mir3636
parents: 111
diff changeset
63 /* Given X, an unsigned number, return the least Y such that 2**Y >= X. */
111
kono
parents: 68
diff changeset
64
kono
parents: 68
diff changeset
65 int
kono
parents: 68
diff changeset
66 ceil_log2 (unsigned HOST_WIDE_INT x)
kono
parents: 68
diff changeset
67 {
131
84e7813d76e9 gcc-8.2
mir3636
parents: 111
diff changeset
68 return x == 0 ? 0 : floor_log2 (x - 1) + 1;
111
kono
parents: 68
diff changeset
69 }
kono
parents: 68
diff changeset
70
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 /* Return the logarithm of X, base 2, considering X unsigned,
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 if X is a power of 2. Otherwise, returns -1. */
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
73
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 int
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 exact_log2 (unsigned HOST_WIDE_INT x)
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 {
111
kono
parents: 68
diff changeset
77 if (!pow2p_hwi (x))
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 return -1;
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 return floor_log2 (x);
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 }
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
81
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
82 /* Given X, an unsigned number, return the number of least significant bits
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 that are zero. When X == 0, the result is the word size. */
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
84
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 int
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 ctz_hwi (unsigned HOST_WIDE_INT x)
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 {
111
kono
parents: 68
diff changeset
88 return x ? floor_log2 (least_bit_hwi (x)) : HOST_BITS_PER_WIDE_INT;
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 }
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
90
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 /* Similarly for most significant bits. */
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
92
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 int
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 clz_hwi (unsigned HOST_WIDE_INT x)
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 {
111
kono
parents: 68
diff changeset
96 return HOST_BITS_PER_WIDE_INT - 1 - floor_log2 (x);
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 }
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
98
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 /* Similar to ctz_hwi, except that the least significant bit is numbered
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 starting from 1, and X == 0 yields 0. */
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
101
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 int
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
103 ffs_hwi (unsigned HOST_WIDE_INT x)
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 {
111
kono
parents: 68
diff changeset
105 return 1 + floor_log2 (least_bit_hwi (x));
kono
parents: 68
diff changeset
106 }
kono
parents: 68
diff changeset
107
kono
parents: 68
diff changeset
108 /* Return the number of set bits in X. */
kono
parents: 68
diff changeset
109
kono
parents: 68
diff changeset
110 int
kono
parents: 68
diff changeset
111 popcount_hwi (unsigned HOST_WIDE_INT x)
kono
parents: 68
diff changeset
112 {
kono
parents: 68
diff changeset
113 int i, ret = 0;
kono
parents: 68
diff changeset
114 size_t bits = sizeof (x) * CHAR_BIT;
kono
parents: 68
diff changeset
115
kono
parents: 68
diff changeset
116 for (i = 0; i < bits; i += 1)
kono
parents: 68
diff changeset
117 {
kono
parents: 68
diff changeset
118 ret += x & 1;
kono
parents: 68
diff changeset
119 x >>= 1;
kono
parents: 68
diff changeset
120 }
kono
parents: 68
diff changeset
121
kono
parents: 68
diff changeset
122 return ret;
68
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
123 }
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
124
561a7518be6b update gcc-4.6
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
125 #endif /* GCC_VERSION < 3004 */
111
kono
parents: 68
diff changeset
126
kono
parents: 68
diff changeset
127
kono
parents: 68
diff changeset
128 /* Compute the greatest common divisor of two numbers A and B using
kono
parents: 68
diff changeset
129 Euclid's algorithm. */
kono
parents: 68
diff changeset
130
kono
parents: 68
diff changeset
131 HOST_WIDE_INT
kono
parents: 68
diff changeset
132 gcd (HOST_WIDE_INT a, HOST_WIDE_INT b)
kono
parents: 68
diff changeset
133 {
kono
parents: 68
diff changeset
134 HOST_WIDE_INT x, y, z;
kono
parents: 68
diff changeset
135
kono
parents: 68
diff changeset
136 x = abs_hwi (a);
kono
parents: 68
diff changeset
137 y = abs_hwi (b);
kono
parents: 68
diff changeset
138
kono
parents: 68
diff changeset
139 while (x > 0)
kono
parents: 68
diff changeset
140 {
kono
parents: 68
diff changeset
141 z = y % x;
kono
parents: 68
diff changeset
142 y = x;
kono
parents: 68
diff changeset
143 x = z;
kono
parents: 68
diff changeset
144 }
kono
parents: 68
diff changeset
145
kono
parents: 68
diff changeset
146 return y;
kono
parents: 68
diff changeset
147 }
kono
parents: 68
diff changeset
148
kono
parents: 68
diff changeset
149 /* For X and Y positive integers, return X multiplied by Y and check
kono
parents: 68
diff changeset
150 that the result does not overflow. */
kono
parents: 68
diff changeset
151
kono
parents: 68
diff changeset
152 HOST_WIDE_INT
kono
parents: 68
diff changeset
153 pos_mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
kono
parents: 68
diff changeset
154 {
kono
parents: 68
diff changeset
155 if (x != 0)
kono
parents: 68
diff changeset
156 gcc_checking_assert ((HOST_WIDE_INT_MAX) / x >= y);
kono
parents: 68
diff changeset
157
kono
parents: 68
diff changeset
158 return x * y;
kono
parents: 68
diff changeset
159 }
kono
parents: 68
diff changeset
160
kono
parents: 68
diff changeset
161 /* Return X multiplied by Y and check that the result does not
kono
parents: 68
diff changeset
162 overflow. */
kono
parents: 68
diff changeset
163
kono
parents: 68
diff changeset
164 HOST_WIDE_INT
kono
parents: 68
diff changeset
165 mul_hwi (HOST_WIDE_INT x, HOST_WIDE_INT y)
kono
parents: 68
diff changeset
166 {
kono
parents: 68
diff changeset
167 gcc_checking_assert (x != HOST_WIDE_INT_MIN
kono
parents: 68
diff changeset
168 && y != HOST_WIDE_INT_MIN);
kono
parents: 68
diff changeset
169
kono
parents: 68
diff changeset
170 if (x >= 0)
kono
parents: 68
diff changeset
171 {
kono
parents: 68
diff changeset
172 if (y >= 0)
kono
parents: 68
diff changeset
173 return pos_mul_hwi (x, y);
kono
parents: 68
diff changeset
174
kono
parents: 68
diff changeset
175 return -pos_mul_hwi (x, -y);
kono
parents: 68
diff changeset
176 }
kono
parents: 68
diff changeset
177
kono
parents: 68
diff changeset
178 if (y >= 0)
kono
parents: 68
diff changeset
179 return -pos_mul_hwi (-x, y);
kono
parents: 68
diff changeset
180
kono
parents: 68
diff changeset
181 return pos_mul_hwi (-x, -y);
kono
parents: 68
diff changeset
182 }
kono
parents: 68
diff changeset
183
kono
parents: 68
diff changeset
184 /* Compute the least common multiple of two numbers A and B . */
kono
parents: 68
diff changeset
185
kono
parents: 68
diff changeset
186 HOST_WIDE_INT
kono
parents: 68
diff changeset
187 least_common_multiple (HOST_WIDE_INT a, HOST_WIDE_INT b)
kono
parents: 68
diff changeset
188 {
kono
parents: 68
diff changeset
189 return mul_hwi (abs_hwi (a) / gcd (a, b), abs_hwi (b));
kono
parents: 68
diff changeset
190 }