1 //------------------------------------------------------------------------------
2 // GB_bitwise.h: definitions for bitwise operators
3 //------------------------------------------------------------------------------
4
5 // SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
6 // SPDX-License-Identifier: Apache-2.0
7
8 //------------------------------------------------------------------------------
9
10 #ifndef GB_BITWISE_H
11 #define GB_BITWISE_H
12
13 //------------------------------------------------------------------------------
14 // bitget, bitset, bitclr
15 //------------------------------------------------------------------------------
16
17 // bitget (x,k) returns a single bit from x, as 0 or 1, whose position is given
18 // by k. k = 1 is the least significant bit, and k = bits (64 for uint64)
19 // is the most significant bit. If k is outside this range, the result is zero.
20
21 #define GB_BITGET(x,k,type,bits) \
22 ( \
23 (k >= 1 && k <= bits) ? \
24 ( \
25 /* get the kth bit */ \
26 ((x & (((type) 1) << (k-1))) ? 1 : 0) \
27 ) \
28 : \
29 ( \
30 0 \
31 ) \
32 )
33
34 // bitset (x,k) returns x modified by setting a bit from x to 1, whose position
35 // is given by k. If k is in the range 1 to bits, then k gives the position
36 // of the bit to set. If k is outside the range 1 to bits, then z = x is
37 // returned, unmodified.
38
39 #define GB_BITSET(x,k,type,bits) \
40 ( \
41 (k >= 1 && k <= bits) ? \
42 ( \
43 /* set the kth bit to 1 */ \
44 (x | (((type) 1) << (k-1))) \
45 ) \
46 : \
47 ( \
48 x \
49 ) \
50 )
51
52 // bitclr (x,k) returns x modified by setting a bit from x to 0, whose position
53 // is given by k. If k is in the range 1 to bits, then k gives the position of
54 // the bit to clear. If k is outside the range 1 to GB_BITS, then z = x is
55 // returned, unmodified.
56
57 #define GB_BITCLR(x,k,type,bits) \
58 ( \
59 (k >= 1 && k <= bits) ? \
60 ( \
61 /* set the kth bit to 0 */ \
62 (x & ~(((type) 1) << (k-1))) \
63 ) \
64 : \
65 ( \
66 x \
67 ) \
68 )
69
70 //------------------------------------------------------------------------------
71 // z = bitshift (x,y) when x and z are unsigned
72 //------------------------------------------------------------------------------
73
GB_bitshift_uint8(uint8_t x,int8_t k)74 inline uint8_t GB_bitshift_uint8 (uint8_t x, int8_t k)
75 {
76 if (k == 0)
77 {
78 // no shift to do at all
79 return (x) ;
80 }
81 else if (k >= 8 || k <= -8)
82 {
83 // ANSI C11 states that the result of x << k is undefined if k is
84 // negative or if k is greater than the # of bits in x. Here, the
85 // result is defined to be zero (the same as if shifting left
86 // or right by 8).
87 return (0) ;
88 }
89 else if (k > 0)
90 {
91 // left shift x by k bits. z is defined by ANSI C11 as
92 // (x * (2^k)) mod (uintmax + 1).
93 return (x << k) ;
94 }
95 else
96 {
97 k = -k ;
98 // right shift x by k bits. z is defined by ANSI C11 as the
99 // integral part of the quotient of x / (2^k).
100 return (x >> k) ;
101 }
102 }
103
GB_bitshift_uint16(uint16_t x,int8_t k)104 inline uint16_t GB_bitshift_uint16 (uint16_t x, int8_t k)
105 {
106 if (k == 0)
107 {
108 // no shift
109 return (x) ;
110 }
111 else if (k >= 16 || k <= -16)
112 {
113 return (0) ;
114 }
115 else if (k > 0)
116 {
117 // left shift
118 return (x << k) ;
119 }
120 else
121 {
122 // right shift
123 return (x >> (-k)) ;
124 }
125 }
126
GB_bitshift_uint32(uint32_t x,int8_t k)127 inline uint32_t GB_bitshift_uint32 (uint32_t x, int8_t k)
128 {
129 if (k == 0)
130 {
131 // no shift
132 return (x) ;
133 }
134 else if (k >= 32 || k <= -32)
135 {
136 return (0) ;
137 }
138 else if (k > 0)
139 {
140 // left shift
141 return (x << k) ;
142 }
143 else
144 {
145 // right shift
146 return (x >> (-k)) ;
147 }
148 }
149
GB_bitshift_uint64(uint64_t x,int8_t k)150 inline uint64_t GB_bitshift_uint64 (uint64_t x, int8_t k)
151 {
152 if (k == 0)
153 {
154 // no shift
155 return (x) ;
156 }
157 else if (k >= 64 || k <= -64)
158 {
159 return (0) ;
160 }
161 else if (k > 0)
162 {
163 // left shift
164 return (x << k) ;
165 }
166 else
167 {
168 // right shift
169 return (x >> (-k)) ;
170 }
171 }
172
173 //------------------------------------------------------------------------------
174 // z = bitshift (x,y) when x and z are signed
175 //------------------------------------------------------------------------------
176
GB_bitshift_int8(int8_t x,int8_t k)177 inline int8_t GB_bitshift_int8 (int8_t x, int8_t k)
178 {
179 if (k == 0)
180 {
181 // no shift to do at all
182 return (x) ;
183 }
184 else if (k >= 8)
185 {
186 // ANSI C11 states that z = x << k is undefined if k is greater
187 // than the # of bits in x. Here, the result is defined to be zero.
188 return (0) ;
189 }
190 else if (k <= -8)
191 {
192 // ANSI C11 states that z = x >> (-k) is undefined if (-k) is
193 // greater than the # of bits in x. Here, the result is defined to
194 // be the sign of x (z = 0 if x >= 0 and z = -1 if x is negative).
195 return ((x >= 0) ? 0 : -1) ;
196 }
197 else if (k > 0)
198 {
199 // left shift x by k bits (where k is in range 1 to #bits - 1).
200 // ANSI C11 states that z is defined only if x is non-negative and
201 // x * (2^k) is representable. This computation assumes x and z
202 // are represented in 2's complement. The result depends on the
203 // underlying machine architecture and the compiler.
204 return (x << k) ;
205 }
206 else
207 {
208 k = -k ;
209 // right shift x by k bits (where k is in range 1 to 8)
210 if (x >= 0)
211 {
212 // ANSI C11 defines z as the integral part of the quotient
213 // of x / (2^k).
214 return (x >> k) ;
215 }
216 else
217 {
218 // ANSI C11 states that the result is implementation-defined if
219 // x is negative. This computation assumes x and z are in 2's
220 // complement, so 1-bits are shifted in on the left, and thus
221 // the sign bit is always preserved. The result depends on the
222 // underlying machine architecture and the compiler.
223 return ((x >> k) | (~(UINT8_MAX >> k))) ;
224 }
225 }
226 }
227
GB_bitshift_int16(int16_t x,int8_t k)228 inline int16_t GB_bitshift_int16 (int16_t x, int8_t k)
229 {
230 if (k == 0)
231 {
232 // no shift
233 return (x) ;
234 }
235 else if (k >= 16)
236 {
237 return (0) ;
238 }
239 else if (k <= -16)
240 {
241 return ((x >= 0) ? 0 : -1) ;
242 }
243 else if (k > 0)
244 {
245 // left shift
246 return (x << k) ;
247 }
248 else
249 {
250 // right shift
251 k = -k ;
252 if (x >= 0)
253 {
254 return (x >> k) ;
255 }
256 else
257 {
258 return ((x >> k) | (~(UINT16_MAX >> k))) ;
259 }
260 }
261 }
262
GB_bitshift_int32(int32_t x,int8_t k)263 inline int32_t GB_bitshift_int32 (int32_t x, int8_t k)
264 {
265 if (k == 0)
266 {
267 // no shift
268 return (x) ;
269 }
270 else if (k >= 32)
271 {
272 return (0) ;
273 }
274 else if (k <= -32)
275 {
276 return ((x >= 0) ? 0 : -1) ;
277 }
278 else if (k > 0)
279 {
280 // left shift
281 return (x << k) ;
282 }
283 else
284 {
285 // right shift
286 k = -k ;
287 if (x >= 0)
288 {
289 return (x >> k) ;
290 }
291 else
292 {
293 return ((x >> k) | (~(UINT32_MAX >> k))) ;
294 }
295 }
296 }
297
GB_bitshift_int64(int64_t x,int8_t k)298 inline int64_t GB_bitshift_int64 (int64_t x, int8_t k)
299 {
300 if (k == 0)
301 {
302 // no shift
303 return (x) ;
304 }
305 else if (k >= 64)
306 {
307 return (0) ;
308 }
309 else if (k <= -64)
310 {
311 return ((x >= 0) ? 0 : -1) ;
312 }
313 else if (k > 0)
314 {
315 // left shift
316 return (x << k) ;
317 }
318 else
319 {
320 // right shift
321 k = -k ;
322 if (x >= 0)
323 {
324 return (x >> k) ;
325 }
326 else
327 {
328 return ((x >> k) | (~(UINT64_MAX >> k))) ;
329 }
330 }
331 }
332
333 #endif
334
335