1 /****************************************************************************
2 **
3 ** This file is part of GAP, a system for computational discrete algebra.
4 **
5 ** Copyright of GAP belongs to its developers, whose names are too numerous
6 ** to list here. Please refer to the COPYRIGHT file for details.
7 **
8 ** SPDX-License-Identifier: GPL-2.0-or-later
9 **
10 ** This file implements helper for dealing with GAP immediate integers.
11 **
12 ** Small integers are represented by an immediate integer handle, containing
13 ** the value instead of pointing to it, which has the following form:
14 **
15 ** +-------+-------+-------+-------+- - - -+-------+-------+-------+
16 ** | guard | sign | bit | bit | | bit | tag | tag |
17 ** | bit | bit | N-5 | N-6 | | 0 | = 0 | = 1 |
18 ** +-------+-------+-------+-------+- - - -+-------+-------+-------+
19 **
20 ** Immediate integers handles carry the tag 'T_INT', i.e. the last bit is 1.
21 ** This distinguishes immediate integers from other handles which point to
22 ** structures aligned on even boundaries and therefore have last bit zero.
23 ** (The second bit is reserved as tag to allow extensions of this scheme.)
24 ** Using immediates as pointers and dereferencing them gives address errors.
25 **
26 ** To aid overflow check the most significant two bits must always be equal,
27 ** that is to say that the sign bit of immediate integers has a guard bit.
28 **
29 ** The functions 'INTOBJ_INT' and 'INT_INTOBJ' should be used to convert
30 ** between a small integer value and its representation as immediate integer
31 ** handle.
32 */
33
34 #ifndef GAP_INTOBJ_H
35 #define GAP_INTOBJ_H
36
37 #include "system.h"
38
39 enum {
40 NR_SMALL_INT_BITS = sizeof(UInt) * 8 - 4,
41
42 // the minimal / maximal possible values of an immediate integer object:
43 INT_INTOBJ_MIN = -(1L << NR_SMALL_INT_BITS),
44 INT_INTOBJ_MAX = (1L << NR_SMALL_INT_BITS) - 1,
45 };
46
47 // the minimal / maximal possible immediate integer objects:
48 #define INTOBJ_MIN (Obj)(((UInt)INT_INTOBJ_MIN << 2) + 0x01)
49 #define INTOBJ_MAX (Obj)(((UInt)INT_INTOBJ_MAX << 2) + 0x01)
50
51
52 /****************************************************************************
53 **
54 *F IS_INTOBJ( <o> ) . . . . . . . . test if an object is an integer object
55 **
56 ** 'IS_INTOBJ' returns 1 if the object <o> is an (immediate) integer object,
57 ** and 0 otherwise.
58 */
IS_INTOBJ(Obj o)59 EXPORT_INLINE Int IS_INTOBJ(Obj o)
60 {
61 return (Int)o & 0x01;
62 }
63
64
65 /****************************************************************************
66 **
67 *F IS_POS_INTOBJ( <o> ) . . test if an object is a positive integer object
68 **
69 ** 'IS_POS_INTOBJ' returns 1 if the object <o> is an (immediate) integer
70 ** object encoding a positive integer, and 0 otherwise.
71 */
IS_POS_INTOBJ(Obj o)72 EXPORT_INLINE Int IS_POS_INTOBJ(Obj o)
73 {
74 return ((Int)o & 0x01) && ((Int)o > 0x01);
75 }
76
77 /****************************************************************************
78 **
79 *F IS_NONNEG_INTOBJ( <o> ) . . test if an object is a non-negative integer object
80 **
81 ** 'IS_NONNEG_INTOBJ' returns 1 if the object <o> is an (immediate) integer
82 ** object encoding a non-negative integer, and 0 otherwise.
83 */
IS_NONNEG_INTOBJ(Obj o)84 EXPORT_INLINE Int IS_NONNEG_INTOBJ(Obj o)
85 {
86 return ((Int)o & 0x01) && ((Int)o > 0);
87 }
88
89
90 /****************************************************************************
91 **
92 *F ARE_INTOBJS( <o1>, <o2> ) . . . . test if two objects are integer objects
93 **
94 ** 'ARE_INTOBJS' returns 1 if the objects <o1> and <o2> are both (immediate)
95 ** integer objects.
96 */
ARE_INTOBJS(Obj o1,Obj o2)97 EXPORT_INLINE Int ARE_INTOBJS(Obj o1, Obj o2)
98 {
99 return (Int)o1 & (Int)o2 & 0x01;
100 }
101
102
103 /****************************************************************************
104 **
105 *F INT_INTOBJ( <o> ) . . . . . . . convert an integer object to a C integer
106 **
107 ** 'INT_INTOBJ' converts the (immediate) integer object <o> to a C integer.
108 */
109 /* Note that the C standard does not define what >> does here if the
110 * value is negative. So we have to be careful if the C compiler
111 * chooses to do a logical right shift. */
112 GAP_STATIC_ASSERT((-1) >> 1 == -1, "right shifts are not arithmetic");
113 GAP_STATIC_ASSERT((-2) >> 1 == -1, "right shifts are not arithmetic");
114
INT_INTOBJ(Obj o)115 EXPORT_INLINE Int INT_INTOBJ(Obj o)
116 {
117 GAP_ASSERT(IS_INTOBJ(o));
118 return (Int)o >> 2;
119 }
120
121
122 /****************************************************************************
123 **
124 *F INTOBJ_INT( <i> ) . . . . . . . convert a C integer to an integer object
125 **
126 ** 'INTOBJ_INT' converts the C integer <i> to an (immediate) integer object.
127 */
INTOBJ_INT(Int i)128 EXPORT_INLINE Obj INTOBJ_INT(Int i)
129 {
130 Obj o;
131 GAP_ASSERT(INT_INTOBJ_MIN <= i && i <= INT_INTOBJ_MAX);
132 o = (Obj)(((UInt)i << 2) + 0x01);
133 GAP_ASSERT(INT_INTOBJ(o) == i);
134 return o;
135 }
136
137 /****************************************************************************
138 **
139 *F EQ_INTOBJS( <o>, <l>, <r> ) . . . . . . . . . compare two integer objects
140 **
141 ** 'EQ_INTOBJS' returns 'True' if the (immediate) integer object <l> is
142 ** equal to the (immediate) integer object <r> and 'False' otherwise. The
143 ** result is also stored in <o>.
144 */
145 #define EQ_INTOBJS(o, l, r) ((o) = (((Int)(l)) == ((Int)(r)) ? True : False))
146
147
148 /****************************************************************************
149 **
150 *F LT_INTOBJS( <o>, <l>, <r> ) . . . . . . . . . compare two integer objects
151 **
152 ** 'LT_INTOBJS' returns 'True' if the (immediate) integer object <l> is
153 ** less than the (immediate) integer object <r> and 'False' otherwise. The
154 ** result is also stored in <o>.
155 */
156 #define LT_INTOBJS(o, l, r) ((o) = (((Int)(l)) < ((Int)(r)) ? True : False))
157
158
159 //
160 // Check whether the sign and guard bit of the given word match.
161 //
DETECT_INTOBJ_OVERFLOW(UInt o)162 EXPORT_INLINE int DETECT_INTOBJ_OVERFLOW(UInt o)
163 {
164 const UInt BITS_IN_UINT = sizeof(UInt) * 8;
165 // extract sign bit + guard bit
166 const UInt top_bits = ((UInt)o) >> (BITS_IN_UINT - 2);
167 // the integer object is valid if the two top bits are equal, i.e. if
168 // top_bits is 0 or 3. If we subtract 1 from this, the valid values are 2
169 // and (UInt)-1, which both are larger than 1; the invalid values are 0
170 // and 1.
171 return (top_bits - 1) <= 1;
172 }
173
174
175 /****************************************************************************
176 **
177 *F SUM_INTOBJS( <o>, <l>, <r> ) . . . . . . . . sum of two integer objects
178 **
179 ** 'SUM_INTOBJS' returns 1 if the sum of the (imm.) integer objects
180 ** <l> and <r> can be stored as (immediate) integer object and 0 otherwise.
181 ** The sum itself is stored in <o>.
182 */
sum_intobjs(Obj * o,Obj l,Obj r)183 EXPORT_INLINE int sum_intobjs(Obj * o, Obj l, Obj r)
184 {
185 const Int tmp = (Int)l + (Int)r - 1;
186 if (DETECT_INTOBJ_OVERFLOW(tmp))
187 return 0;
188 *o = (Obj)tmp;
189 return 1;
190 }
191 #define SUM_INTOBJS(o, l, r) sum_intobjs(&(o), (l), (r))
192
193
194 /****************************************************************************
195 **
196 *F DIFF_INTOBJS( <o>, <l>, <r> ) . . . . . difference of two integer objects
197 **
198 ** 'DIFF_INTOBJS' returns 1 if the difference of the (imm.) integer objects
199 ** <l> and <r> can be stored as (immediate) integer object and 0 otherwise.
200 ** The difference itself is stored in <o>.
201 */
diff_intobjs(Obj * o,Obj l,Obj r)202 EXPORT_INLINE int diff_intobjs(Obj * o, Obj l, Obj r)
203 {
204 const Int tmp = (Int)l - (Int)r + 1;
205 if (DETECT_INTOBJ_OVERFLOW(tmp))
206 return 0;
207 *o = (Obj)tmp;
208 return 1;
209 }
210 #define DIFF_INTOBJS(o, l, r) diff_intobjs(&(o), (l), (r))
211
212
213 /****************************************************************************
214 **
215 *F PROD_INTOBJS( <o>, <l>, <r> ) . . . . . . product of two integer objects
216 **
217 ** 'PROD_INTOBJS' returns 1 if the product of the (imm.) integer objects
218 ** <l> and <r> can be stored as (immediate) integer object and 0 otherwise.
219 ** The product itself is stored in <o>.
220 */
221
222 // check for __builtin_mul_overflow support
223 #if defined(__has_builtin)
224 // clang >= 3.8 supports it, but better to check with __has_builtin
225 #if __has_builtin(__builtin_mul_overflow)
226 #define HAVE___BUILTIN_MUL_OVERFLOW 1
227 #endif
228 #elif defined(__INTEL_COMPILER)
229 // icc >= 19.0 supports it; but already version 18.0 claims to be GCC 5
230 // compatible, so we must perform this check before that for __GNUC__
231 #if __INTEL_COMPILER >= 1900
232 #define HAVE___BUILTIN_MUL_OVERFLOW 1
233 #endif
234 #elif defined(__GNUC__) && (__GNUC__ >= 5)
235 // GCC >= 5 supports it
236 #define HAVE___BUILTIN_MUL_OVERFLOW 1
237 #endif
238
239
240 #ifdef HAVE___BUILTIN_MUL_OVERFLOW
prod_intobjs(Int l,Int r)241 EXPORT_INLINE Obj prod_intobjs(Int l, Int r)
242 {
243 Int prod;
244 if (__builtin_mul_overflow(l >> 1, r ^ 1, &prod))
245 return (Obj)0;
246 return (Obj)((prod >> 1) ^ 1);
247 }
248 #else
249
250 #ifdef SYS_IS_64_BIT
251 typedef Int4 HalfInt;
252 #else
253 typedef Int2 HalfInt;
254 #endif
255
prod_intobjs(Int l,Int r)256 EXPORT_INLINE Obj prod_intobjs(Int l, Int r)
257 {
258 if (l == (Int)INTOBJ_INT(0) || r == (Int)INTOBJ_INT(0))
259 return INTOBJ_INT(0);
260 if (l == (Int)INTOBJ_INT(1))
261 return (Obj)r;
262 if (r == (Int)INTOBJ_INT(1))
263 return (Obj)l;
264
265 const Int prod = ((Int)((UInt)l >> 2) * ((UInt)r - 1) + 1);
266
267 if (DETECT_INTOBJ_OVERFLOW(prod))
268 return (Obj)0;
269
270 // if both factors fit into half a word, their product fits in a word
271 if ((HalfInt)l == (Int)l && (HalfInt)r == (Int)r)
272 return (Obj)prod;
273
274 // last resort: perform trial division using arithmetic right shift
275 if ((prod - 1) / (l >> 2) == r - 1)
276 return (Obj)prod;
277
278 return (Obj)0;
279 }
280 #endif
281
282 #define PROD_INTOBJS(o, l, r) ((o) = prod_intobjs((Int)(l), (Int)(r)))
283
284 #endif // GAP_INTOBJ_H
285