1 /********************************************************************/
2 /* */
3 /* int_rtl.c Primitive actions for the integer type. */
4 /* Copyright (C) 1989 - 2019, 2021 Thomas Mertes */
5 /* */
6 /* This file is part of the Seed7 Runtime Library. */
7 /* */
8 /* The Seed7 Runtime Library is free software; you can */
9 /* redistribute it and/or modify it under the terms of the GNU */
10 /* Lesser General Public License as published by the Free Software */
11 /* Foundation; either version 2.1 of the License, or (at your */
12 /* option) any later version. */
13 /* */
14 /* The Seed7 Runtime Library is distributed in the hope that it */
15 /* will be useful, but WITHOUT ANY WARRANTY; without even the */
16 /* implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR */
17 /* PURPOSE. See the GNU Lesser General Public License for more */
18 /* details. */
19 /* */
20 /* You should have received a copy of the GNU Lesser General */
21 /* Public License along with this program; if not, write to the */
22 /* Free Software Foundation, Inc., 51 Franklin Street, */
23 /* Fifth Floor, Boston, MA 02110-1301, USA. */
24 /* */
25 /* Module: Seed7 Runtime Library */
26 /* File: seed7/src/int_rtl.c */
27 /* Changes: 1992 - 1994, 2000, 2005, 2009 - 2019 Thomas Mertes */
28 /* 2021 Thomas Mertes */
29 /* Content: Primitive actions for the integer type. */
30 /* */
31 /********************************************************************/
32
33 #define LOG_FUNCTIONS 0
34 #define VERBOSE_EXCEPTIONS 0
35
36 #include "version.h"
37
38 #include "stdlib.h"
39 #include "stdio.h"
40 #include "string.h"
41 #include "time.h"
42 #include "limits.h"
43
44 #include "common.h"
45 #include "data_rtl.h"
46 #include "heaputl.h"
47 #include "striutl.h"
48 #include "tim_drv.h"
49 #include "rtl_err.h"
50
51 #undef EXTERN
52 #define EXTERN
53 #include "int_rtl.h"
54
55
56 #define UINT_BITS(A) ((A) & UINTTYPE_MAX)
57 #define UINT_BITS_WITHOUT_HIGHEST_BIT(A) ((A) & (UINTTYPE_MAX >> 1))
58 #define UINT_HIGHEST_BIT(A) ((A) >> (INTTYPE_SIZE - 1))
59 #define UINT_LOWER_HALF_BITS_SET (UINTTYPE_MAX >> (INTTYPE_SIZE >> 1))
60 #define LOWER_HALF_OF_UINT(A) ((A) & UINT_LOWER_HALF_BITS_SET)
61 #define UPPER_HALF_OF_UINT(A) ((A) >> (INTTYPE_SIZE >> 1))
62
63 /**
64 * Number of characters needed if the most negative
65 * integer is written with radix 2. One character is
66 * needed for the sign. Assume that integers are just
67 * signed bytes. In this case the most negative number
68 * would be -128. -128 radix 2 returns "-10000000"
69 * The result needs 9 digits although -128 fits into a
70 * signed byte with 8 bits.
71 */
72 #define RADIX_BUFFER_SIZE (CHAR_BIT * sizeof(intType) + 1)
73
74 #define BYTE_BUFFER_SIZE sizeof(intType)
75
76 #if INTTYPE_SIZE == 32
77 #define DECIMAL_DIGITS(num) \
78 (num < UINT_SUFFIX(100000000) ? \
79 (num < UINT_SUFFIX(10000) ? \
80 (num < UINT_SUFFIX(100) ? \
81 (num < UINT_SUFFIX(10) ? 1 : 2) \
82 : \
83 (num < UINT_SUFFIX(1000) ? 3 : 4) \
84 ) \
85 : \
86 (num < UINT_SUFFIX(1000000) ? \
87 (num < UINT_SUFFIX(100000) ? 5 : 6) \
88 : \
89 (num < UINT_SUFFIX(10000000) ? 7 : 8) \
90 ) \
91 ) \
92 : \
93 (num < UINT_SUFFIX(1000000000) ? 9 : 10) \
94 )
95 #elif INTTYPE_SIZE == 64
96 #define DECIMAL_DIGITS(num) \
97 (num < UINT_SUFFIX(10000000000000000) ? \
98 (num < UINT_SUFFIX(100000000) ? \
99 (num < UINT_SUFFIX(10000) ? \
100 (num < UINT_SUFFIX(100) ? \
101 (num < UINT_SUFFIX(10) ? 1 : 2) \
102 : \
103 (num < UINT_SUFFIX(1000) ? 3 : 4) \
104 ) \
105 : \
106 (num < UINT_SUFFIX(1000000) ? \
107 (num < UINT_SUFFIX(100000) ? 5 : 6) \
108 : \
109 (num < UINT_SUFFIX(10000000) ? 7 : 8) \
110 ) \
111 ) \
112 : \
113 (num < UINT_SUFFIX(1000000000000) ? \
114 (num < UINT_SUFFIX(10000000000) ? \
115 (num < UINT_SUFFIX(1000000000) ? 9 : 10) \
116 : \
117 (num < UINT_SUFFIX(100000000000) ? 11 : 12) \
118 ) \
119 : \
120 (num < UINT_SUFFIX(100000000000000) ? \
121 (num < UINT_SUFFIX(10000000000000) ? 13 : 14) \
122 : \
123 (num < UINT_SUFFIX(1000000000000000) ? 15 : 16) \
124 ) \
125 ) \
126 ) \
127 : \
128 (num < UINT_SUFFIX(1000000000000000000) ? \
129 (num < UINT_SUFFIX(100000000000000000) ? 17 : 18) \
130 : \
131 (num < UINT_SUFFIX(10000000000000000000) ? 19 : 20) \
132 ) \
133 )
134 #endif
135
136
137 static const int most_significant[] = {
138 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
139 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
140 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
141 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
142 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
143 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
144 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
145 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
146 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
147 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
148 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
149 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
150 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
151 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
152 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
153 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
154 };
155
156 static const int least_significant[] = {
157 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
158 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
159 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
160 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
161 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
162 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
163 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
164 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
165 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
166 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
167 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
168 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
169 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
170 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
171 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
172 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
173 };
174
175 /**
176 * Table to support the overflow checking of intPowOvfChk().
177 * For a base between -8 and 8 use maxExponentOfBase[base + 8]
178 * to determine the maximum exponent. If the exponent is
179 * between 0 and maxExponentOfBase[base + 8] the expression
180 * base ** exponent can be computed without overflow.
181 */
182 static const intType maxExponentOfBase[] = {
183 21, 22, 24, 27, 31, 39, 63,
184 INTTYPE_MAX, INTTYPE_MAX, INTTYPE_MAX,
185 62, 39, 31, 27, 24, 22, 20
186 };
187
188 /**
189 * Table to support the overflow checking of intPowOvfChk().
190 * For an exponent between 0 and 22 minBaseOfExponent[exponent]
191 * is used to determine the minimum base. If a base is between
192 * minBaseOfExponent[exponent] and maxBaseOfExponent[exponent] the
193 * expression base ** exponent can be computed without overflow.
194 */
195 static const intType minBaseOfExponent[] = {
196 INTTYPE_MIN, INTTYPE_MIN,
197 -INT_SUFFIX(3037000499), -2097152, -55108, -6208, -1448, -512, -234,
198 -128, -78, -52, -38, -28, -22, -18, -15, -13, -11, -9, -8, -8, -7
199 };
200
201 /**
202 * Table to support the overflow checking of intPowOvfChk().
203 * For an exponent between 0 and 22 maxBaseOfExponent[exponent]
204 * is used to determine the maximum base. If a base is between
205 * minBaseOfExponent[exponent] and maxBaseOfExponent[exponent] the
206 * expression base ** exponent can be computed without overflow.
207 */
208 static const intType maxBaseOfExponent[] = {
209 INTTYPE_MAX, INTTYPE_MAX,
210 INT_SUFFIX(3037000499), 2097151, 55108, 6208, 1448, 511, 234,
211 127, 78, 52, 38, 28, 22, 18, 15, 13, 11, 9, 8, 7, 7
212 };
213
214 const const_ustriType digitTable[] = {
215 (const_ustriType) "0123456789abcdefghijklmnopqrstuvwxyz",
216 (const_ustriType) "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
217 };
218
219 #ifdef HAS_DOUBLE_INTTYPE
220 doubleUintType seed;
221 #else
222 static uintType low_seed;
223 static uintType high_seed;
224 #endif
225
226
227
228 /**
229 * Initialize the seed of the random number generator.
230 * Data from the current time and from the clock() function is used
231 * to set up the random number generator. This function is called
232 * once from the interpreter or from the main function of a compiled
233 * program.
234 */
setupRand(void)235 void setupRand (void)
236
237 {
238 uintType micro_sec;
239 #ifdef HAS_DOUBLE_INTTYPE
240 uintType low_seed;
241 uintType high_seed;
242 #endif
243
244 /* setupRand */
245 logFunction(printf("setupRand()\n"););
246 micro_sec = (uintType) timMicroSec();
247 high_seed = (uintType) time(NULL);
248 high_seed = high_seed ^ (high_seed << 16);
249 low_seed = (uintType) clock();
250 low_seed = (low_seed ^ (low_seed << 16)) ^ high_seed;
251 /* printf("%10lo %010lo seed\n", (long unsigned) high_seed, (long unsigned) low_seed); */
252 high_seed ^= micro_sec ^ micro_sec << 8 ^ micro_sec << 16 ^ micro_sec << 24;
253 #if INTTYPE_SIZE >= 64
254 high_seed ^= micro_sec << 32 ^ micro_sec << 40 ^ micro_sec << 48 ^ micro_sec << 56;
255 #endif
256 low_seed ^= micro_sec ^ micro_sec << 8 ^ micro_sec << 16 ^ micro_sec << 24;
257 #if INTTYPE_SIZE >= 64
258 low_seed ^= micro_sec << 32 ^ micro_sec << 40 ^ micro_sec << 48 ^ micro_sec << 56;
259 #endif
260 /* printf("%10lo %010lo seed\n", (long unsigned) high_seed, (long unsigned) low_seed); */
261 #ifdef HAS_DOUBLE_INTTYPE
262 seed = (doubleUintType) high_seed << INTTYPE_SIZE | (doubleUintType) low_seed;
263 #endif
264 } /* setupRand */
265
266
267
268 /**
269 * Multiply two uintType factors to a double uintType product.
270 * The whole product fits into the double uintType number.
271 * The product is returned in product_high and product_low.
272 * A double uintType number consists of a low and a high uintType
273 * number. A double uintType number can also be split into
274 * four halve uintType parts. The bits of a double uintType have
275 * the following memory layout:
276 * +---------------------------------------+
277 * | double uintType |
278 * +-------------------+-------------------+
279 * | high uintType | low uintType |
280 * +---------+---------+---------+---------+
281 * | part[3] | part[2] | part[1] | part[0] |
282 * +---------+---------+---------+---------+
283 * ^ highest bit ^ lowest bit
284 * @param product_high The address to return the high product.
285 * @return the low product
286 */
uintMult(uintType factor1,uintType factor2,uintType * product_high)287 uintType uintMult (uintType factor1, uintType factor2, uintType *product_high)
288
289 {
290 uintType factor1_part[2]; /* parts 2 and 3 are not used */
291 uintType factor2_part[2]; /* parts 2 and 3 are not used */
292 uintType c1; /* memory layout: | part[1] | part[0] | */
293 uintType c2; /* memory layout: | part[2] | part[1] | */
294 uintType c3; /* memory layout: | part[2] | part[1] | */
295 uintType c4; /* memory layout: | part[2] | part[1] | */
296 uintType c5; /* memory layout: | part[3] | part[2] | */
297 uintType product_low;
298
299 /* uintMult */
300 logFunction(printf("uintMult(" F_X(016) ", " F_X(016) ")\n",
301 factor1, factor2););
302 factor1_part[0] = LOWER_HALF_OF_UINT(factor1);
303 factor1_part[1] = UPPER_HALF_OF_UINT(factor1);
304 factor2_part[0] = LOWER_HALF_OF_UINT(factor2);
305 factor2_part[1] = UPPER_HALF_OF_UINT(factor2);
306 c1 = factor1_part[0] * factor2_part[0];
307 c2 = factor1_part[0] * factor2_part[1];
308 c3 = factor1_part[1] * factor2_part[0];
309 c4 = UPPER_HALF_OF_UINT(c1) + LOWER_HALF_OF_UINT(c2) + LOWER_HALF_OF_UINT(c3);
310 c5 = UPPER_HALF_OF_UINT(c2) + UPPER_HALF_OF_UINT(c3) + UPPER_HALF_OF_UINT(c4) +
311 factor1_part[1] * factor2_part[1];
312 /* c5 contains the high uintType of factor1 * factor2 */
313 product_low = UINT_BITS(factor1 * factor2);
314 *product_high = UINT_BITS(c5);
315 logFunction(printf("uintMult --> " F_X(016) F_X(016) "\n",
316 *product_high, product_low););
317 return product_low;
318 } /* uintMult */
319
320
321
322 #ifdef HAS_DOUBLE_INTTYPE
323 /**
324 * Compute a random unsigned number in the range 0 .. UINTTYPE_MAX.
325 * The linear congruential method is used to generate the random
326 * sequence of uintType numbers. The generator uses double uintType
327 * numbers for the seed. Only the high bits of the seed (high_seed)
328 * are used as random number. This avoids that the lower-order bits
329 * of the generated sequence have a short period.
330 * @return the random number.
331 */
uintRand(void)332 uintType uintRand (void)
333
334 { /* uintRand */
335 logFunction(printf("uintRand\n"););
336 seed = seed * RAND_MULTIPLIER + RAND_INCREMENT;
337 logFunction(printf("uintRand --> " F_X(016) "\n",
338 (uintType) (seed >> INTTYPE_SIZE)););
339 return (uintType) (seed >> INTTYPE_SIZE);
340 } /* uintRand */
341
342
343
uintRandMantissa(void)344 uintType uintRandMantissa (void)
345
346 { /* uintRandMantissa */
347 logFunction(printf("uintRandMantissa\n"););
348 seed = seed * RAND_MULTIPLIER + RAND_INCREMENT;
349 logFunction(printf("uintRandMantissa --> " F_X(016) "\n",
350 (uintType) (seed >> (INTTYPE_SIZE + FLOATTYPE_EXPONENT_AND_SIGN_BITS))););
351 return (uintType) (seed >> (INTTYPE_SIZE + FLOATTYPE_EXPONENT_AND_SIGN_BITS));
352 } /* uintRandMantissa */
353
354 #else
355
356
357
358 /**
359 * Multiply two double uintType factors to a double uintType product.
360 * The low bits of the product are returned as double uintType
361 * number (in product_high and product_low). The higher bits of
362 * the product (the bits higher than product_high) are discarded.
363 * A double uintType number consists of a low and a high uintType
364 * number. A double uintType number can also be split into
365 * four halve uintType parts. The bits of a double uintType have
366 * the following memory layout:
367 * +---------------------------------------+
368 * | double uintType |
369 * +-------------------+-------------------+
370 * | high uintType | low uintType |
371 * +---------+---------+---------+---------+
372 * | part[3] | part[2] | part[1] | part[0] |
373 * +---------+---------+---------+---------+
374 * ^ highest bit ^ lowest bit
375 * @param product_high The address to return the high product.
376 * @return the low product
377 */
uint2Mult(uintType factor1_high,uintType factor1_low,uintType factor2_high,uintType factor2_low,uintType * product_high)378 static inline uintType uint2Mult (uintType factor1_high, uintType factor1_low,
379 uintType factor2_high, uintType factor2_low, uintType *product_high)
380
381 {
382 uintType factor1_part[2]; /* parts 2 and 3 are not used */
383 uintType factor2_part[2]; /* parts 2 and 3 are not used */
384 uintType c1; /* memory layout: | part[1] | part[0] | */
385 uintType c2; /* memory layout: | part[2] | part[1] | */
386 uintType c3; /* memory layout: | part[2] | part[1] | */
387 uintType c4; /* memory layout: | part[2] | part[1] | */
388 uintType c5; /* memory layout: | part[3] | part[2] | */
389 uintType product_low;
390
391 /* uint2Mult */
392 logFunction(printf("uint2Mult(" F_X(016) F_X(016) ", " F_X(016) F_X(016) ")\n",
393 factor1_high, factor1_low, factor2_high, factor2_low););
394 factor1_part[0] = LOWER_HALF_OF_UINT(factor1_low);
395 factor1_part[1] = UPPER_HALF_OF_UINT(factor1_low);
396 factor2_part[0] = LOWER_HALF_OF_UINT(factor2_low);
397 factor2_part[1] = UPPER_HALF_OF_UINT(factor2_low);
398 c1 = factor1_part[0] * factor2_part[0];
399 c2 = factor1_part[0] * factor2_part[1];
400 c3 = factor1_part[1] * factor2_part[0];
401 c4 = UPPER_HALF_OF_UINT(c1) + LOWER_HALF_OF_UINT(c2) + LOWER_HALF_OF_UINT(c3);
402 c5 = UPPER_HALF_OF_UINT(c2) + UPPER_HALF_OF_UINT(c3) + UPPER_HALF_OF_UINT(c4) +
403 factor1_part[1] * factor2_part[1];
404 /* c5 contains the high uintType of factor1_low * factor2_low */
405 product_low = UINT_BITS(factor1_low * factor2_low);
406 *product_high = UINT_BITS(factor1_low * factor2_high + factor1_high * factor2_low + c5);
407 /* factor1_high * factor2_high is not computed. All bits of it */
408 /* would be discarded, since they are higher than product_high. */
409 logFunction(printf("uint2Mult --> " F_X(016) F_X(016) "\n",
410 *product_high, product_low););
411 return product_low;
412 } /* uint2Mult */
413
414
415
416 /**
417 * Add two double uintType summands to a double uintType sum.
418 * A possible excess bit, that does not fit into the sum
419 * (the excess bit is higher than sum_high), is discarded.
420 * A double uintType number consists of a low and a high uintType
421 * number. The bits of a double uintType have the following
422 * memory layout:
423 * +---------------------------------------+
424 * | double uintType |
425 * +-------------------+-------------------+
426 * | high uintType | low uintType |
427 * +-------------------+-------------------+
428 * ^ highest bit ^ lowest bit
429 * @param sum_high The address to return the high sum.
430 * @return the low sum
431 */
uint2Add(uintType summand1_high,uintType summand1_low,uintType summand2_high,uintType summand2_low,uintType * sum_high)432 static inline uintType uint2Add (uintType summand1_high, uintType summand1_low,
433 uintType summand2_high, uintType summand2_low, uintType *sum_high)
434
435 {
436 uintType sum_low;
437
438 /* uint2Add */
439 logFunction(printf("uint2Add(" F_X(016) F_X(016) ", " F_X(016) F_X(016) ")\n",
440 summand1_high, summand1_low, summand2_high, summand2_low););
441 sum_low = UINT_BITS(summand1_low + summand2_low);
442 if (UINT_HIGHEST_BIT(summand1_low) + UINT_HIGHEST_BIT(summand2_low) +
443 UINT_HIGHEST_BIT(UINT_BITS_WITHOUT_HIGHEST_BIT(summand1_low) +
444 UINT_BITS_WITHOUT_HIGHEST_BIT(summand2_low)) >= 2) {
445 *sum_high = UINT_BITS(summand1_high + summand2_high + 1);
446 } else {
447 *sum_high = UINT_BITS(summand1_high + summand2_high);
448 } /* if */
449 logFunction(printf("uint2Add --> " F_X(016) F_X(016) "\n",
450 *sum_high, sum_low););
451 return sum_low;
452 } /* uint2Add */
453
454
455
456 /**
457 * Compute a random unsigned number in the range 0 .. UINTTYPE_MAX.
458 * The linear congruential method is used to generate the random
459 * sequence of uintType numbers. The generator uses double uintType
460 * numbers for the seed. Only the high bits of the seed (high_seed)
461 * are used as random number. This avoids that the lower-order bits
462 * of the generated sequence have a short period.
463 * @return the random number.
464 */
uintRand(void)465 uintType uintRand (void)
466
467 { /* uintRand */
468 logFunction(printf("uintRand\n"););
469 /* SEED = SEED * RAND_MULTIPLIER + RAND_INCREMENT */
470 low_seed = uint2Mult(high_seed, low_seed, (uintType) INT_SUFFIX(0),
471 (uintType) INT_SUFFIX(RAND_MULTIPLIER), &high_seed);
472 low_seed = uint2Add(high_seed, low_seed, (uintType) INT_SUFFIX(0),
473 (uintType) INT_SUFFIX(RAND_INCREMENT), &high_seed);
474 logFunction(printf("uintRand --> " F_X(016) "\n", high_seed););
475 return high_seed;
476 } /* uintRand */
477
478
479
uintRandMantissa(void)480 uintType uintRandMantissa (void)
481
482 { /* uintRandMantissa */
483 logFunction(printf("uintRandMantissa\n"););
484 /* SEED = SEED * RAND_MULTIPLIER + RAND_INCREMENT */
485 low_seed = uint2Mult(high_seed, low_seed, (uintType) INT_SUFFIX(0),
486 (uintType) INT_SUFFIX(RAND_MULTIPLIER), &high_seed);
487 low_seed = uint2Add(high_seed, low_seed, (uintType) INT_SUFFIX(0),
488 (uintType) INT_SUFFIX(RAND_INCREMENT), &high_seed);
489 logFunction(printf("uintRandMantissa --> " F_X(016) "\n",
490 high_seed >> DOUBLE_EXPONENT_AND_SIGN_BITS););
491 return high_seed >> DOUBLE_EXPONENT_AND_SIGN_BITS;
492 } /* uintRandMantissa */
493 #endif
494
495
496
497 /**
498 * Compute a pseudo-random number in the range 0 .. rand_max.
499 * The random values are uniform distributed.
500 * This function is used by the compiler, if lower and upper bound
501 * of a random number are known at compile time.
502 * @param rand_max Maximum random number. Rand_max should be near to
503 * UINTTYPE_MAX to avoid that the loop is traversed to often.
504 * @return a random number such that 0 <= uintRandLimited(rand_max) and
505 * uintRandLimited(rand_max) <= rand_max holds.
506 */
uintRandLimited(uintType rand_max)507 uintType uintRandLimited (uintType rand_max)
508
509 {
510 uintType rand_val;
511
512 /* uintRandLimited */
513 logFunction(printf("uintRandLimited(" FMT_U ")\n", rand_max););
514 do {
515 rand_val = uintRand();
516 } while (rand_val > rand_max);
517 logFunction(printf("uintRandLimited --> " FMT_U "\n", rand_val););
518 return rand_val;
519 } /* uintRandLimited */
520
521
522
523 /**
524 * Compute the greatest common divisor (gcd) of two unsigned integers.
525 * @return the greatest common divisor.
526 */
uintGcd(uintType number1,uintType number2)527 static uintType uintGcd (uintType number1, uintType number2)
528
529 {
530 uintType temp;
531
532 /* uintGcd */
533 logFunction(printf("uintGcd(" FMT_D ", " FMT_D ")\n",
534 number1, number2););
535 if (number2 < number1) {
536 temp = number1;
537 number1 = number2;
538 number2 = temp;
539 } /* if */
540 while (number2 > 0) {
541 temp = number2;
542 number2 = number1 % number2;
543 number1 = temp;
544 } /* while */
545 logFunction(printf("uintGcd --> " FMT_D "\n", number1););
546 return number1;
547 } /* uintGcd */
548
549
550
uint8MostSignificantBit(uint8Type number)551 int uint8MostSignificantBit (uint8Type number)
552
553 {
554 int result;
555
556 /* uint8MostSignificantBit */
557 result = most_significant[number];
558 return result;
559 } /* uint8MostSignificantBit */
560
561
562
uint16MostSignificantBit(uint16Type number)563 int uint16MostSignificantBit (uint16Type number)
564
565 {
566 int result;
567
568 /* uint16MostSignificantBit */
569 if (number > 0xff) {
570 result = 8 + most_significant[number >> 8];
571 } else {
572 result = most_significant[number];
573 } /* if */
574 return result;
575 } /* uint16MostSignificantBit */
576
577
578
uint32MostSignificantBit(uint32Type number)579 int uint32MostSignificantBit (uint32Type number)
580
581 {
582 int result = 0;
583
584 /* uint32MostSignificantBit */
585 if (number > 0xffff) {
586 number >>= 16;
587 result = 16;
588 } /* if */
589 if (number & 0xff00) {
590 number >>= 8;
591 result += 8;
592 } /* if */
593 result += most_significant[number];
594 return result;
595 } /* uint32MostSignificantBit */
596
597
598
599 #ifdef INT64TYPE
uint64MostSignificantBit(uint64Type number)600 int uint64MostSignificantBit (uint64Type number)
601
602 {
603 int result = 0;
604
605 /* uint64MostSignificantBit */
606 if (number > 0xffffffff) {
607 number >>= 32;
608 result = 32;
609 } /* if */
610 if (number & 0xffff0000) {
611 number >>= 16;
612 result += 16;
613 } /* if */
614 if (number & 0xff00) {
615 number >>= 8;
616 result += 8;
617 } /* if */
618 result += most_significant[number];
619 return result;
620 } /* uint64MostSignificantBit */
621 #endif
622
623
624
uint8LeastSignificantBit(uint8Type number)625 int uint8LeastSignificantBit (uint8Type number)
626
627 {
628 int result;
629
630 /* uint8LeastSignificantBit */
631 result = least_significant[number & 0xff];
632 return result;
633 } /* uint8LeastSignificantBit */
634
635
636
uint16LeastSignificantBit(uint16Type number)637 int uint16LeastSignificantBit (uint16Type number)
638
639 {
640 int result;
641
642 /* uint16LeastSignificantBit */
643 if ((number & 0xff) == 0) {
644 result = 8 + least_significant[(number >> 8) & 0xff];
645 } else {
646 result = least_significant[number & 0xff];
647 } /* if */
648 return result;
649 } /* uint16LeastSignificantBit */
650
651
652
uint32LeastSignificantBit(uint32Type number)653 int uint32LeastSignificantBit (uint32Type number)
654
655 {
656 static const int MULTIPLY_DE_BRUIJN_BIT_POSITION[32] = {
657 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
658 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
659
660 /* uint32LeastSignificantBit */
661 return MULTIPLY_DE_BRUIJN_BIT_POSITION[
662 (uint32Type) ((number & -number) * UINT32_SUFFIX(0x077cb531)) >> 27];
663 } /* uint32LeastSignificantBit */
664
665
666
667 #ifdef INT64TYPE
uint64LeastSignificantBit(uint64Type number)668 int uint64LeastSignificantBit (uint64Type number)
669
670 {
671 static const int MULTIPLY_DE_BRUIJN_BIT_POSITION[64] = {
672 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
673 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
674 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
675 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12};
676
677 /* uint64LeastSignificantBit */
678 return MULTIPLY_DE_BRUIJN_BIT_POSITION[
679 (uint64Type) ((number & -number) * UINT64_SUFFIX(0x022fdd63cc95386d)) >> 58];
680 } /* uint64LeastSignificantBit */
681 #endif
682
683
684
685 /**
686 * Determine the number of one bits in an unsigned number.
687 * The function uses a combination of sideways additions and
688 * a multiplication to count the bits set in a number element.
689 * @return the number of one bits.
690 */
uintCard(uintType number)691 intType uintCard (uintType number)
692
693 { /* uintCard */
694 #if INTTYPE_SIZE == 32
695 number -= (number >> 1) & UINT32_SUFFIX(0x55555555);
696 number = (number & UINT32_SUFFIX(0x33333333)) +
697 ((number >> 2) & UINT32_SUFFIX(0x33333333));
698 number = (number + (number >> 4)) & UINT32_SUFFIX(0x0f0f0f0f);
699 return (intType) ((number * UINT32_SUFFIX(0x01010101)) >> 24);
700 #elif INTTYPE_SIZE == 64
701 number -= (number >> 1) & UINT64_SUFFIX(0x5555555555555555);
702 number = (number & UINT64_SUFFIX(0x3333333333333333)) +
703 ((number >> 2) & UINT64_SUFFIX(0x3333333333333333));
704 number = (number + (number >> 4)) & UINT64_SUFFIX(0x0f0f0f0f0f0f0f0f);
705 return (intType) ((number * UINT64_SUFFIX(0x0101010101010101)) >> 56);
706 #endif
707 } /* uintCard */
708
709
710
711 /**
712 * Compare two unsigned integer numbers.
713 * @return -1, 0 or 1 if the first argument is considered to be
714 * respectively less than, equal to, or greater than the
715 * second.
716 */
uintCmp(uintType number1,uintType number2)717 intType uintCmp (uintType number1, uintType number2)
718
719 {
720 intType signumValue;
721
722 /* uintCmp */
723 if (number1 < number2) {
724 signumValue = -1;
725 } else {
726 signumValue = number1 > number2;
727 } /* if */
728 return signumValue;
729 } /* uintCmp */
730
731
732
733 /**
734 * Reinterpret the generic parameters as uintType and call uintCmp.
735 * Function pointers in C programs generated by the Seed7 compiler
736 * may point to this function. This assures correct behaviour even
737 * if sizeof(genericType) != sizeof(intType).
738 * @return -1, 0 or 1 if the first argument is considered to be
739 * respectively less than, equal to, or greater than the
740 * second.
741 */
uintCmpGeneric(const genericType value1,const genericType value2)742 intType uintCmpGeneric (const genericType value1, const genericType value2)
743
744 { /* uintCmpGeneric */
745 return intCmp(((const_rtlObjectType *) &value1)->value.intValue,
746 ((const_rtlObjectType *) &value2)->value.intValue);
747 } /* uintCmpGeneric */
748
749
750
751 /**
752 * Convert an unsigned integer into a big-endian encoded string of bytes.
753 * The result uses binary representation with a base of 256.
754 * The result contains chars (bytes) with an ordinal <= 255.
755 * @param number Unsigned integer number to be converted.
756 * @param length Determines the length of the result string.
757 * @return a string of 'length' bytes with the unsigned binary
758 * representation of 'number'.
759 * @exception RANGE_ERROR If 'length' is negative or zero, or
760 * if the result would not fit in 'length' bytes.
761 * @exception MEMORY_ERROR Not enough memory to represent the result.
762 */
uintNBytesBe(uintType number,intType length)763 striType uintNBytesBe (uintType number, intType length)
764
765 {
766 strElemType *buffer;
767 memSizeType dataStart;
768 memSizeType pos = 0;
769 striType result;
770
771 /* uintNBytesBe */
772 logFunction(printf("uintNBytesBe(" FMT_U ", " FMT_D ")\n",
773 number, length););
774 if (unlikely(length <= 0)) {
775 logError(printf("uintNBytesBe(" FMT_U ", " FMT_D "): "
776 "Negative length.\n", number, length););
777 raise_error(RANGE_ERROR);
778 result = NULL;
779 } else if (unlikely((uintType) length > MAX_STRI_LEN ||
780 !ALLOC_STRI_SIZE_OK(result, (memSizeType) length))) {
781 raise_error(MEMORY_ERROR);
782 result = NULL;
783 } else {
784 result->size = (memSizeType) length;
785 if ((memSizeType) length > BYTE_BUFFER_SIZE) {
786 dataStart = (memSizeType) length - BYTE_BUFFER_SIZE;
787 } else {
788 dataStart = 0;
789 } /* if */
790 buffer = result->mem;
791 pos = (memSizeType) length;
792 do {
793 pos--;
794 buffer[pos] = (strElemType) (number & 0xff);
795 number >>= CHAR_BIT;
796 } while (pos > dataStart);
797 if (pos > 0) {
798 memset(buffer, 0, pos * sizeof(strElemType));
799 } else if (unlikely(number != 0)) {
800 logError(printf("uintNBytesBe: "
801 "Number does not fit into " FMT_D " bytes.\n", length););
802 FREE_STRI(result, (memSizeType) length);
803 raise_error(RANGE_ERROR);
804 result = NULL;
805 } /* if */
806 } /* if */
807 logFunction(printf("uintNBytesBe --> \"%s\"\n",
808 striAsUnquotedCStri(result)););
809 return result;
810 } /* uintNBytesBe */
811
812
813
814 /**
815 * Convert an unsigned integer into a little-endian encoded string of bytes.
816 * The result uses binary representation with a base of 256.
817 * The result contains chars (bytes) with an ordinal <= 255.
818 * @param number Unsigned integer number to be converted.
819 * @param length Determines the length of the result string.
820 * @return a string of 'length' bytes with the unsigned binary
821 * representation of 'number'.
822 * @exception RANGE_ERROR If 'length' is negative or zero, or
823 * if the result would not fit in 'length' bytes.
824 * @exception MEMORY_ERROR Not enough memory to represent the result.
825 */
uintNBytesLe(uintType number,intType length)826 striType uintNBytesLe (uintType number, intType length)
827
828 {
829 strElemType *buffer;
830 memSizeType dataLength;
831 memSizeType pos = 0;
832 striType result;
833
834 /* uintNBytesLe */
835 logFunction(printf("uintNBytesLe(" FMT_U ", " FMT_D ")\n",
836 number, length););
837 if (unlikely(length <= 0)) {
838 logError(printf("uintNBytesLe(" FMT_U ", " FMT_D "): "
839 "Negative length.\n", number, length););
840 raise_error(RANGE_ERROR);
841 result = NULL;
842 } else if (unlikely((uintType) length > MAX_STRI_LEN ||
843 !ALLOC_STRI_SIZE_OK(result, (memSizeType) length))) {
844 raise_error(MEMORY_ERROR);
845 result = NULL;
846 } else {
847 result->size = (memSizeType) length;
848 if ((memSizeType) length > BYTE_BUFFER_SIZE) {
849 dataLength = BYTE_BUFFER_SIZE;
850 } else {
851 dataLength = (memSizeType) length;
852 } /* if */
853 buffer = result->mem;
854 for (pos = 0; pos < dataLength; pos++) {
855 buffer[pos] = (strElemType) (number & 0xff);
856 number >>= CHAR_BIT;
857 } /* for */
858 if ((memSizeType) length > dataLength) {
859 memset(&buffer[pos], 0, ((memSizeType) length - dataLength) * sizeof(strElemType));
860 } else if (unlikely(number != 0)) {
861 logError(printf("uintNBytesLe: "
862 "Number does not fit into " FMT_D " bytes.\n", length););
863 FREE_STRI(result, (memSizeType) length);
864 raise_error(RANGE_ERROR);
865 result = NULL;
866 } /* if */
867 } /* if */
868 logFunction(printf("uintNBytesLe --> \"%s\"\n",
869 striAsUnquotedCStri(result)););
870 return result;
871 } /* uintNBytesLe */
872
873
874
875 /**
876 * Convert an unsigned number to a string using a radix.
877 * The conversion uses the numeral system with the given base.
878 * Digit values from 10 upward are encoded with letters.
879 * @param upperCase Decides about the letter case.
880 * @return the string result of the conversion.
881 * @exception RANGE_ERROR If base < 2 or base > 36 holds.
882 * @exception MEMORY_ERROR Not enough memory to represent the result.
883 */
uintRadix(uintType number,intType base,boolType upperCase)884 striType uintRadix (uintType number, intType base, boolType upperCase)
885
886 {
887 const_ustriType digits;
888 strElemType buffer_1[RADIX_BUFFER_SIZE];
889 strElemType *buffer;
890 memSizeType length;
891 striType result;
892
893 /* uintRadix */
894 logFunction(printf("uintRadix(" FMT_U ", " FMT_D ", %d)\n",
895 number, base, upperCase););
896 if (unlikely(base < 2 || base > 36)) {
897 logError(printf("uintRadix(" FMT_U ", " FMT_D ", %d): "
898 "base < 2 or base > 36.\n",
899 number, base, upperCase););
900 raise_error(RANGE_ERROR);
901 result = NULL;
902 } else {
903 digits = digitTable[upperCase];
904 buffer = &buffer_1[RADIX_BUFFER_SIZE];
905 do {
906 *(--buffer) = (strElemType) (digits[number % (uintType) base]);
907 } while ((number /= (uintType) base) != 0);
908 length = (memSizeType) (&buffer_1[RADIX_BUFFER_SIZE] - buffer);
909 if (unlikely(!ALLOC_STRI_SIZE_OK(result, length))) {
910 raise_error(MEMORY_ERROR);
911 } else {
912 result->size = length;
913 memcpy(result->mem, buffer, (size_t) (length * sizeof(strElemType)));
914 } /* if */
915 } /* if */
916 logFunction(printf("uintRadix --> \"%s\"\n", striAsUnquotedCStri(result)););
917 return result;
918 } /* uintRadix */
919
920
921
922 /**
923 * Convert an integer number to a string using a radix.
924 * The conversion uses the numeral system with the specified base.
925 * The base is a power of two and it is specified indirectly with
926 * shift and mask. Digit values from 10 upward are encoded with
927 * letters.
928 * @param shift Logarithm (log2) of the base (=number of bits in mask).
929 * @param mask Mask to get the bits of a digit (equivalent to base-1).
930 * @param upperCase Decides about the letter case.
931 * @return the string result of the conversion.
932 * @exception MEMORY_ERROR Not enough memory to represent the result.
933 */
uintRadixPow2(uintType number,int shift,int mask,boolType upperCase)934 striType uintRadixPow2 (uintType number, int shift, int mask, boolType upperCase)
935
936 {
937 const_ustriType digits;
938 strElemType buffer_1[RADIX_BUFFER_SIZE];
939 strElemType *buffer;
940 memSizeType length;
941 striType result;
942
943 /* uintRadixPow2 */
944 logFunction(printf("uintRadixPow2(" FMT_U ", %d, %x, %d)\n",
945 number, shift, mask, upperCase););
946 digits = digitTable[upperCase];
947 buffer = &buffer_1[RADIX_BUFFER_SIZE];
948 do {
949 *(--buffer) = (strElemType) (digits[number & (uintType) mask]);
950 } while ((number >>= shift) != 0);
951 length = (memSizeType) (&buffer_1[RADIX_BUFFER_SIZE] - buffer);
952 if (unlikely(!ALLOC_STRI_SIZE_OK(result, length))) {
953 raise_error(MEMORY_ERROR);
954 } else {
955 result->size = length;
956 memcpy(result->mem, buffer, (size_t) (length * sizeof(strElemType)));
957 } /* if */
958 logFunction(printf("uintRadixPow2 --> \"%s\"\n",
959 striAsUnquotedCStri(result)););
960 return result;
961 } /* uintRadixPow2 */
962
963
964
965 /**
966 * Convert an unsigned integer number to a string.
967 * The number is converted to a string with decimal representation.
968 * @return the string result of the conversion.
969 * @exception MEMORY_ERROR Not enough memory to represent the result.
970 */
uintStr(uintType number)971 striType uintStr (uintType number)
972
973 {
974 strElemType *buffer;
975 memSizeType length;
976 striType result;
977
978 /* uintStr */
979 logFunction(printf("uintStr(" FMT_U ")\n", number););
980 length = DECIMAL_DIGITS(number);
981 if (unlikely(!ALLOC_STRI_SIZE_OK(result, length))) {
982 raise_error(MEMORY_ERROR);
983 } else {
984 result->size = length;
985 buffer = &result->mem[length];
986 do {
987 *(--buffer) = (strElemType) (number % 10 + '0');
988 } while ((number /= 10) != 0);
989 } /* if */
990 logFunction(printf("uintStr --> \"%s\"\n",
991 striAsUnquotedCStri(result)););
992 return result;
993 } /* uintStr */
994
995
996
997 /**
998 * Compare two generic values.
999 * @return -1, 0 or 1 if the first argument is considered to be
1000 * respectively less than, equal to, or greater than the
1001 * second.
1002 */
genericCmp(const genericType value1,const genericType value2)1003 intType genericCmp (const genericType value1, const genericType value2)
1004
1005 {
1006 intType signumValue;
1007
1008 /* genericCmp */
1009 if (value1 < value2) {
1010 signumValue = -1;
1011 } else {
1012 signumValue = value1 > value2;
1013 } /* if */
1014 return signumValue;
1015 } /* genericCmp */
1016
1017
1018
1019 /**
1020 * Generic Copy function to be used via function pointers.
1021 * This functions is used to copy values for all types
1022 * where a binary copy without special functionality can be used:
1023 * E.g.: intType, floatType, charType, boolType.
1024 * Function pointers in C programs generated by the Seed7 compiler
1025 * may point to this function. The function genericCpy is
1026 * used from hashtables where the keys and the data is stored in
1027 * genericType data elements. This assures correct behaviour
1028 * even if sizeof(genericType) != sizeof(intType).
1029 */
genericCpy(genericType * const dest,const genericType source)1030 void genericCpy (genericType *const dest, const genericType source)
1031
1032 { /* genericCpy */
1033 *dest = source;
1034 } /* genericCpy */
1035
1036
1037
1038 /**
1039 * Generic Create function to be used via function pointers.
1040 * This functions is used to create new values for all types
1041 * where a binary copy without special functionality can be used:
1042 * E.g.: intType, floatType, charType, boolType.
1043 * Function pointers in C programs generated by the Seed7 compiler
1044 * may point to this function. The function genericCreate is
1045 * used from hashtables where the keys and the data is stored in
1046 * genericType data elements. This assures correct behaviour
1047 * even if sizeof(genericType) != sizeof(intType). Even for
1048 * sizeof(genericType) == sizeof(intType) some things must
1049 * be considered: On some architectures (linux with gcc)
1050 * functions with float results seem to be returned in a
1051 * different way (may be another register). Therefore
1052 * genericCreate (with genericType) must be used even
1053 * if sizeof(genericType) == sizeof(floatType).
1054 */
genericCreate(genericType source)1055 genericType genericCreate (genericType source)
1056
1057 { /* genericCreate */
1058 return source;
1059 } /* genericCreate */
1060
1061
1062
1063 /**
1064 * Generic Destr function to be used via function pointers.
1065 * This functions is used to destroy old values for all types
1066 * where a noop without special functionality can be used:
1067 * E.g.: intType, floatType, charType, boolType.
1068 * In contrast to prcNoop the number of parameters (1) of
1069 * genericDestr is correct. This is important since some
1070 * C compilers generate wrong code if prcNoop is used.
1071 */
genericDestr(genericType old_value)1072 void genericDestr (genericType old_value)
1073
1074 { /* genericDestr */
1075 } /* genericDestr */
1076
1077
1078
1079 /**
1080 * Compare two pointers.
1081 * @return -1, 0 or 1 if the first argument is considered to be
1082 * respectively less than, equal to, or greater than the
1083 * second.
1084 */
ptrCmp(const void * const value1,const void * const value2)1085 intType ptrCmp (const void *const value1, const void *const value2)
1086
1087 {
1088 intType signumValue;
1089
1090 /* ptrCmp */
1091 if ((memSizeType) value1 < (memSizeType) value2) {
1092 signumValue = -1;
1093 } else {
1094 signumValue = (memSizeType) value1 > (memSizeType) value2;
1095 } /* if */
1096 return signumValue;
1097 } /* ptrCmp */
1098
1099
1100
1101 /**
1102 * Reinterpret the generic parameters as rtlPtrType and call ptrCmp.
1103 * Function pointers in C programs generated by the Seed7 compiler
1104 * may point to this function. This assures correct behaviour even
1105 * if sizeof(genericType) != sizeof(rtlPtrType).
1106 * @return -1, 0 or 1 if the first argument is considered to be
1107 * respectively less than, equal to, or greater than the
1108 * second.
1109 */
ptrCmpGeneric(const genericType value1,const genericType value2)1110 intType ptrCmpGeneric (const genericType value1, const genericType value2)
1111
1112 { /* ptrCmpGeneric */
1113 return ptrCmp(((const_rtlObjectType *) &value1)->value.ptrValue,
1114 ((const_rtlObjectType *) &value2)->value.ptrValue);
1115 } /* ptrCmpGeneric */
1116
1117
1118
1119 /**
1120 * Reinterpret the generic parameters as rtlPtrType and assign source to dest.
1121 * Function pointers in C programs generated by the Seed7 compiler
1122 * may point to this function. This assures correct behaviour even
1123 * if sizeof(genericType) != sizeof(rtlPtrType).
1124 */
ptrCpyGeneric(genericType * const dest,const genericType source)1125 void ptrCpyGeneric (genericType *const dest, const genericType source)
1126
1127 { /* ptrCpyGeneric */
1128 ((rtlObjectType *) dest)->value.ptrValue =
1129 ((const_rtlObjectType *) &source)->value.ptrValue;
1130 } /* ptrCpyGeneric */
1131
1132
1133
1134 /**
1135 * Generic Create function to be used via function pointers.
1136 * Function pointers in C programs generated by the Seed7 compiler
1137 * may point to this function. This assures correct behaviour even
1138 * if sizeof(genericType) != sizeof(rtlPtrType).
1139 */
ptrCreateGeneric(const genericType from_value)1140 genericType ptrCreateGeneric (const genericType from_value)
1141
1142 {
1143 rtlObjectType result;
1144
1145 /* ptrCreateGeneric */
1146 INIT_GENERIC_PTR(result.value.genericValue);
1147 result.value.ptrValue =
1148 ((const_rtlObjectType *) &from_value)->value.ptrValue;
1149 return result.value.genericValue;
1150 } /* ptrCreateGeneric */
1151
1152
1153
1154 /**
1155 * Binomial coefficient
1156 * This is equivalent to n! / k! / (n - k)!
1157 * This function checks for overflow, otherwise it could not
1158 * provide the correct result in all situations. This keeps
1159 * a design principle of Seed7 intact: All overflow situations,
1160 * where OVERFLOW_ERROR is raised correspond to C situations,
1161 * which have undefined behaviour (wrong results). In other
1162 * words: Wrong results without overflow checking are only
1163 * acceptable if overflow checking would raise OVERFLOW_ERROR.
1164 * @return the binomial coefficient n over k
1165 * @exception OVERFLOW_ERROR If the result would be less than
1166 * integer.first or greater than integer.last.
1167 */
intBinom(intType n_number,intType k_number)1168 intType intBinom (intType n_number, intType k_number)
1169
1170 {
1171 uintType numerator;
1172 uintType denominator;
1173 boolType negative;
1174 uintType unsignedBinomialCoefficient;
1175 uintType gcd;
1176 uintType reducedNumerator;
1177 uintType reducedDenominator;
1178 intType binomialCoefficient;
1179
1180 /* intBinom */
1181 logFunction(printf("intBinom(" FMT_D ", " FMT_D ")\n",
1182 n_number, k_number););
1183 if (n_number >= 0 && k_number > (intType) ((uintType) n_number >> 1)) {
1184 k_number = n_number - k_number;
1185 } /* if */
1186 if (unlikely(k_number <= 1)) {
1187 if (k_number < 0) {
1188 binomialCoefficient = 0;
1189 } else if (k_number == 0) {
1190 binomialCoefficient = 1;
1191 } else {
1192 binomialCoefficient = n_number;
1193 } /* if */
1194 } else if (unlikely(n_number == -1)) {
1195 if (k_number & 1) {
1196 binomialCoefficient = -1;
1197 } else {
1198 binomialCoefficient = 1;
1199 } /* if */
1200 } else {
1201 if (n_number < 0) {
1202 negative = (boolType) (k_number & 1);
1203 numerator = -(uintType) n_number + (uintType) k_number - 1;
1204 if ((uintType) k_number > numerator >> 1) {
1205 k_number = (intType) (numerator - (uintType) k_number);
1206 } /* if */
1207 } else {
1208 negative = FALSE;
1209 numerator = (uintType) n_number;
1210 } /* if */
1211 unsignedBinomialCoefficient = numerator;
1212 numerator--;
1213 #if INTTYPE_SIZE == 32
1214 if (numerator <= 29) {
1215 #elif INTTYPE_SIZE == 64
1216 if (numerator <= 61) {
1217 #endif
1218 for (denominator = 2; denominator <= (uintType) k_number; denominator++, numerator--) {
1219 unsignedBinomialCoefficient *= numerator;
1220 unsignedBinomialCoefficient /= denominator;
1221 } /* for */
1222 } else {
1223 for (denominator = 2; denominator <= (uintType) k_number; denominator++, numerator--) {
1224 if (unsignedBinomialCoefficient > UINTTYPE_MAX / numerator) {
1225 /* Possible overflow */
1226 gcd = uintGcd(numerator, denominator);
1227 reducedNumerator = numerator / gcd;
1228 reducedDenominator = denominator / gcd;
1229 gcd = uintGcd(unsignedBinomialCoefficient, reducedDenominator);
1230 unsignedBinomialCoefficient = unsignedBinomialCoefficient / gcd;
1231 reducedDenominator = reducedDenominator / gcd;
1232 if (unlikely(unsignedBinomialCoefficient > UINTTYPE_MAX / reducedNumerator)) {
1233 /* Unavoidable overflow */
1234 logError(printf("intBinom(" FMT_D ", " FMT_D "): "
1235 "Unavoidable overflow.\n", n_number, k_number););
1236 raise_error(OVERFLOW_ERROR);
1237 return 0;
1238 } else {
1239 unsignedBinomialCoefficient *= reducedNumerator;
1240 unsignedBinomialCoefficient /= reducedDenominator;
1241 } /* if */
1242 } else {
1243 unsignedBinomialCoefficient *= numerator;
1244 unsignedBinomialCoefficient /= denominator;
1245 } /* if */
1246 } /* for */
1247 } /* if */
1248 if (negative) {
1249 /* The value INTTYPE_MIN below is casted, to avoid a signed */
1250 /* integer overflow, if it is negated. A negated unsigned */
1251 /* value should still be unsigned. But lcc-win32 thinks, that */
1252 /* negating an unsigned value results in a signed value. */
1253 /* Therefore an explicit cast of the negated value is done. */
1254 if (unlikely(unsignedBinomialCoefficient > (uintType) -(uintType) INTTYPE_MIN)) {
1255 logError(printf("intBinom(" FMT_D ", " FMT_D "): "
1256 "Negative binomial coefficient (-" FMT_U ") too small.\n",
1257 n_number, k_number, unsignedBinomialCoefficient););
1258 raise_error(OVERFLOW_ERROR);
1259 binomialCoefficient = 0;
1260 } else {
1261 binomialCoefficient = (intType) -unsignedBinomialCoefficient;
1262 } /* if */
1263 } else {
1264 /* The cast below silences possible signed-unsigned comparison */
1265 /* warnings and prevents that lcc-win32 does a signed comparison. */
1266 if (unlikely(unsignedBinomialCoefficient > (uintType) INTTYPE_MAX)) {
1267 logError(printf("intBinom(" FMT_D ", " FMT_D "): "
1268 "Positive binomial coefficient (" FMT_U ") too big.\n",
1269 n_number, k_number, unsignedBinomialCoefficient););
1270 raise_error(OVERFLOW_ERROR);
1271 binomialCoefficient = 0;
1272 } else {
1273 binomialCoefficient = (intType) unsignedBinomialCoefficient;
1274 } /* if */
1275 } /* if */
1276 } /* if */
1277 logFunction(printf("intBinom --> " FMT_D "\n", binomialCoefficient););
1278 return binomialCoefficient;
1279 } /* intBinom */
1280
1281
1282
1283 /**
1284 * Binomial coefficient
1285 * This is equivalent to n! / k! / (n - k)!
1286 * This is a special case function that provides the correct
1287 * result if n_number is less than a limit.
1288 * For 32-bit integers the limit is 30 (n_number <= 30 must hold).
1289 * For 64-bit integers the limit is 62 (n_number <= 62 must hold).
1290 * @return the binomial coefficient n over k
1291 */
1292 uintType uintBinomNoChk (uintType n_number, intType k_number)
1293
1294 {
1295 uintType denominator;
1296 uintType binomialCoefficient;
1297
1298 /* uintBinomNoChk */
1299 logFunction(printf("uintBinomNoChk(" FMT_D ", " FMT_U ")\n",
1300 n_number, k_number););
1301 if (k_number > (intType) (n_number >> 1)) {
1302 k_number = (intType) n_number - k_number;
1303 } /* if */
1304 if (unlikely(k_number <= 1)) {
1305 if (k_number < 0) {
1306 binomialCoefficient = 0;
1307 } else if (k_number == 0) {
1308 binomialCoefficient = 1;
1309 } else {
1310 binomialCoefficient = n_number;
1311 } /* if */
1312 } else {
1313 binomialCoefficient = n_number;
1314 n_number--;
1315 for (denominator = 2; denominator <= (uintType) k_number; denominator++, n_number--) {
1316 binomialCoefficient *= n_number;
1317 binomialCoefficient /= denominator;
1318 } /* for */
1319 } /* if */
1320 logFunction(printf("uintBinomNoChk --> " FMT_U "\n", binomialCoefficient););
1321 return binomialCoefficient;
1322 } /* uintBinomNoChk */
1323
1324
1325
1326 /**
1327 * Number of bits in the minimal two's-complement representation.
1328 * The high bits equivalent to the sign bit are not part of the
1329 * minimal two's-complement representation.
1330 * @return the number of bits.
1331 */
1332 intType intBitLength (intType number)
1333
1334 {
1335 intType bitLength;
1336
1337 /* intBitLength */
1338 if (number < 0) {
1339 number = ~number;
1340 } /* if */
1341 bitLength = uintMostSignificantBit((uintType) number) + 1;
1342 return bitLength;
1343 } /* intBitLength */
1344
1345
1346
1347 /**
1348 * Convert an integer into a big-endian encoded string of bytes.
1349 * The result uses binary representation with a base of 256.
1350 * The result contains chars (bytes) with an ordinal <= 255.
1351 * @param number Integer number to be converted.
1352 * @param isSigned Determines the signedness of the result.
1353 * If 'isSigned' is TRUE the result is encoded with the
1354 * twos-complement representation. In this case a negative
1355 * 'number' is converted to a result where the most significant
1356 * byte has an ordinal > BYTE_MAX (=127).
1357 * @return a string with the shortest binary representation of 'number'.
1358 * @exception RANGE_ERROR If 'number' is negative and 'isSigned' is FALSE.
1359 * @exception MEMORY_ERROR Not enough memory to represent the result.
1360 */
1361 striType intBytesBe (intType number, boolType isSigned)
1362
1363 {
1364 strElemType buffer[BYTE_BUFFER_SIZE];
1365 unsigned int pos = BYTE_BUFFER_SIZE;
1366 striType result;
1367
1368 /* intBytesBe */
1369 logFunction(printf("intBytesBe(" FMT_D ", %d)\n", number, isSigned););
1370 if (number >= 0) {
1371 do {
1372 pos--;
1373 buffer[pos] = (strElemType) (number & 0xff);
1374 number >>= CHAR_BIT;
1375 } while (number != 0);
1376 if (isSigned && buffer[pos] > BYTE_MAX) {
1377 pos--;
1378 buffer[pos] = 0;
1379 } /* if */
1380 } else if (likely(isSigned)) {
1381 do {
1382 pos--;
1383 buffer[pos] = (strElemType) (number & 0xff);
1384 #if RSHIFT_DOES_SIGN_EXTEND
1385 number >>= CHAR_BIT;
1386 #else
1387 number = ~(~number >> CHAR_BIT);
1388 #endif
1389 } while (number != -1);
1390 if (buffer[pos] <= BYTE_MAX) {
1391 pos--;
1392 buffer[pos] = UBYTE_MAX;
1393 } /* if */
1394 } else {
1395 logError(printf("intBytesBe(" FMT_D ", %d): "
1396 "Negative number and isSigned is FALSE.\n",
1397 number, isSigned););
1398 raise_error(RANGE_ERROR);
1399 return NULL;
1400 } /* if */
1401 if (unlikely(!ALLOC_STRI_SIZE_OK(result, (memSizeType) (BYTE_BUFFER_SIZE - pos)))) {
1402 raise_error(MEMORY_ERROR);
1403 } else {
1404 result->size = (memSizeType) (BYTE_BUFFER_SIZE - pos);
1405 memcpy(result->mem, &buffer[pos],
1406 (memSizeType) (BYTE_BUFFER_SIZE - pos) * sizeof(strElemType));
1407 } /* if */
1408 logFunction(printf("intBytesBe --> \"%s\"\n", striAsUnquotedCStri(result)););
1409 return result;
1410 } /* intBytesBe */
1411
1412
1413
1414 /**
1415 * Convert a string of bytes (interpreted as big-endian) to an integer.
1416 * @param byteStri String of bytes to be converted. The bytes are
1417 * interpreted as binary big-endian representation with a
1418 * base of 256. Negative values use the twos-complement
1419 * representation.
1420 * @return an integer created from 'byteStri'. The result is negative
1421 * if the most significant byte (the first byte) of 'byteStri'
1422 * has an ordinal > BYTE_MAX (=127).
1423 * @exception RANGE_ERROR If characters beyond '\255;' are present or
1424 * if the result value cannot be represented with an integer.
1425 */
1426 intType intBytesBe2Int (const const_striType byteStri)
1427
1428 {
1429 memSizeType pos = 0;
1430 intType result;
1431
1432 /* intBytesBe2Int */
1433 logFunction(printf("intBytesBe2Int(\"%s\")\n",
1434 striAsUnquotedCStri(byteStri)););
1435 if (byteStri->size == 0 || byteStri->mem[0] <= BYTE_MAX) {
1436 if (byteStri->size >= sizeof(intType)) {
1437 while (pos < byteStri->size && byteStri->mem[pos] == 0) {
1438 pos++;
1439 } /* if */
1440 if (unlikely(byteStri->size - pos > sizeof(intType) ||
1441 (byteStri->size - pos == sizeof(intType) &&
1442 byteStri->mem[pos] > BYTE_MAX))) {
1443 logError(printf("intBytesBe2Int(\"%s\"): "
1444 "Number too big.\n",
1445 striAsUnquotedCStri(byteStri)););
1446 raise_error(RANGE_ERROR);
1447 return 0;
1448 } /* if */
1449 } /* if */
1450 result = 0;
1451 } else { /* byteStri->size != 0 && byteStri->mem[0] > BYTE_MAX */
1452 if (byteStri->size >= sizeof(intType)) {
1453 while (pos < byteStri->size && byteStri->mem[pos] == UBYTE_MAX) {
1454 pos++;
1455 } /* if */
1456 if (unlikely(byteStri->size - pos > sizeof(intType) ||
1457 (byteStri->size - pos == sizeof(intType) &&
1458 byteStri->mem[pos] <= BYTE_MAX))) {
1459 logError(printf("intBytesBe2Int(\"%s\"): "
1460 "Number too small.\n",
1461 striAsUnquotedCStri(byteStri)););
1462 raise_error(RANGE_ERROR);
1463 return 0;
1464 } /* if */
1465 } /* if */
1466 result = -1;
1467 } /* if */
1468 for (; pos < byteStri->size; pos++) {
1469 if (unlikely(byteStri->mem[pos] > UBYTE_MAX)) {
1470 logError(printf("intBytesBe2Int(\"%s\"): "
1471 "Character '\\%d;' is beyond '\\255;'.\n",
1472 striAsUnquotedCStri(byteStri),
1473 byteStri->mem[pos]););
1474 raise_error(RANGE_ERROR);
1475 return 0;
1476 } /* if */
1477 result <<= CHAR_BIT;
1478 result += byteStri->mem[pos];
1479 } /* for */
1480 logFunction(printf("intBytesBe2Int --> " FMT_D "\n", result););
1481 return result;
1482 } /* intBytesBe2Int */
1483
1484
1485
1486 /**
1487 * Convert a string of bytes (interpreted as big-endian) to an integer.
1488 * @param byteStri String of bytes to be converted. The bytes are
1489 * interpreted as binary big-endian representation with a
1490 * base of 256.
1491 * @return an integer created from 'byteStri'. The result is always
1492 * positive.
1493 * @exception RANGE_ERROR If characters beyond '\255;' are present or
1494 * if the result value cannot be represented with an integer.
1495 */
1496 intType intBytesBe2UInt (const const_striType byteStri)
1497
1498 {
1499 memSizeType pos = 0;
1500 intType result = 0;
1501
1502 /* intBytesBe2UInt */
1503 logFunction(printf("intBytesBe2UInt(\"%s\")\n",
1504 striAsUnquotedCStri(byteStri)););
1505 if (byteStri->size >= sizeof(intType)) {
1506 while (pos < byteStri->size && byteStri->mem[pos] == 0) {
1507 pos++;
1508 } /* if */
1509 if (unlikely(byteStri->size - pos > sizeof(intType) ||
1510 (byteStri->size - pos == sizeof(intType) &&
1511 byteStri->mem[pos] > BYTE_MAX))) {
1512 logError(printf("intBytesBe2UInt(\"%s\"): "
1513 "Number too big.\n",
1514 striAsUnquotedCStri(byteStri)););
1515 raise_error(RANGE_ERROR);
1516 return 0;
1517 } /* if */
1518 } /* if */
1519 for (; pos < byteStri->size; pos++) {
1520 if (unlikely(byteStri->mem[pos] > UBYTE_MAX)) {
1521 logError(printf("intBytesBe2UInt(\"%s\"): "
1522 "Character '\\%d;' is beyond '\\255;'.\n",
1523 striAsUnquotedCStri(byteStri),
1524 byteStri->mem[pos]););
1525 raise_error(RANGE_ERROR);
1526 return 0;
1527 } /* if */
1528 result <<= CHAR_BIT;
1529 result += byteStri->mem[pos];
1530 } /* for */
1531 logFunction(printf("intBytesBe2UInt --> " FMT_D "\n", result););
1532 return result;
1533 } /* intBytesBe2UInt */
1534
1535
1536
1537 /**
1538 * Convert an integer into a little-endian encoded string of bytes.
1539 * The result uses binary representation with a base of 256.
1540 * The result contains chars (bytes) with an ordinal <= 255.
1541 * @param number Integer number to be converted.
1542 * @param isSigned Determines the signedness of the result.
1543 * If 'isSigned' is TRUE the result is encoded with the
1544 * twos-complement representation. In this case a negative
1545 * 'number' is converted to a result where the most significant
1546 * byte has an ordinal > BYTE_MAX (=127).
1547 * @return a string with the shortest binary representation of 'number'.
1548 * @exception RANGE_ERROR If 'number' is negative and 'isSigned' is FALSE.
1549 * @exception MEMORY_ERROR Not enough memory to represent the result.
1550 */
1551 striType intBytesLe (intType number, boolType isSigned)
1552
1553 {
1554 strElemType buffer[BYTE_BUFFER_SIZE];
1555 unsigned int pos = 0;
1556 striType result;
1557
1558 /* intBytesLe */
1559 logFunction(printf("intBytesLe(" FMT_D ", %d)\n", number, isSigned););
1560 if (number >= 0) {
1561 do {
1562 buffer[pos] = (strElemType) (number & 0xff);
1563 number >>= CHAR_BIT;
1564 pos++;
1565 } while (number != 0);
1566 if (isSigned && buffer[pos - 1] > BYTE_MAX) {
1567 buffer[pos] = 0;
1568 pos++;
1569 } /* if */
1570 } else if (likely(isSigned)) {
1571 do {
1572 buffer[pos] = (strElemType) (number & 0xff);
1573 #if RSHIFT_DOES_SIGN_EXTEND
1574 number >>= CHAR_BIT;
1575 #else
1576 number = ~(~number >> CHAR_BIT);
1577 #endif
1578 pos++;
1579 } while (number != -1);
1580 if (buffer[pos - 1] <= BYTE_MAX) {
1581 buffer[pos] = UBYTE_MAX;
1582 pos++;
1583 } /* if */
1584 } else {
1585 logError(printf("intBytesLe(" FMT_D ", %d): "
1586 "Negative number and isSigned is FALSE.\n",
1587 number, isSigned););
1588 raise_error(RANGE_ERROR);
1589 return NULL;
1590 } /* if */
1591 if (unlikely(!ALLOC_STRI_SIZE_OK(result, (memSizeType) (pos)))) {
1592 raise_error(MEMORY_ERROR);
1593 } else {
1594 result->size = (memSizeType) (pos);
1595 memcpy(result->mem, &buffer[0],
1596 (memSizeType) pos * sizeof(strElemType));
1597 } /* if */
1598 logFunction(printf("intBytesLe --> \"%s\"\n",
1599 striAsUnquotedCStri(result)););
1600 return result;
1601 } /* intBytesLe */
1602
1603
1604
1605 /**
1606 * Convert a string of bytes (interpreted as little-endian) to an integer.
1607 * @param byteStri String of bytes to be converted. The bytes are
1608 * interpreted as binary little-endian representation with a
1609 * base of 256. Negative values use the twos-complement
1610 * representation.
1611 * @return an integer created from 'byteStri'. The result is negative
1612 * if the most significant byte (the last byte) of 'byteStri'
1613 * has an ordinal > BYTE_MAX (=127).
1614 * @exception RANGE_ERROR If characters beyond '\255;' are present or
1615 * if the result value cannot be represented with an integer.
1616 */
1617 intType intBytesLe2Int (const const_striType byteStri)
1618
1619 {
1620 memSizeType pos;
1621 intType result;
1622
1623 /* intBytesLe2Int */
1624 logFunction(printf("intBytesLe2Int(\"%s\")\n",
1625 striAsUnquotedCStri(byteStri)););
1626 pos = byteStri->size;
1627 if (byteStri->size == 0 || byteStri->mem[pos - 1] <= BYTE_MAX) {
1628 if (unlikely(byteStri->size >= sizeof(intType))) {
1629 while (pos > 0 && byteStri->mem[pos - 1] == 0) {
1630 pos--;
1631 } /* if */
1632 if (unlikely(pos > sizeof(intType) ||
1633 (pos == sizeof(intType) &&
1634 byteStri->mem[pos - 1] > BYTE_MAX))) {
1635 logError(printf("intBytesLe2Int(\"%s\"): "
1636 "Number too big.\n",
1637 striAsUnquotedCStri(byteStri)););
1638 raise_error(RANGE_ERROR);
1639 return 0;
1640 } /* if */
1641 } /* if */
1642 result = 0;
1643 } else { /* byteStri->size != 0 && byteStri->mem[pos - 1] > BYTE_MAX */
1644 if (unlikely(byteStri->size >= sizeof(intType))) {
1645 while (pos > 0 && byteStri->mem[pos - 1] == UBYTE_MAX) {
1646 pos--;
1647 } /* if */
1648 if (unlikely(pos > sizeof(intType) ||
1649 (pos == sizeof(intType) &&
1650 byteStri->mem[pos - 1] <= BYTE_MAX))) {
1651 logError(printf("intBytesLe2Int(\"%s\"): "
1652 "Number too small.\n",
1653 striAsUnquotedCStri(byteStri)););
1654 raise_error(RANGE_ERROR);
1655 return 0;
1656 } /* if */
1657 } /* if */
1658 result = -1;
1659 } /* if */
1660 for (; pos > 0; pos--) {
1661 if (unlikely(byteStri->mem[pos - 1] > UBYTE_MAX)) {
1662 logError(printf("intBytesLe2Int(\"%s\"): "
1663 "Character '\\%d;' is beyond '\\255;'.\n",
1664 striAsUnquotedCStri(byteStri),
1665 byteStri->mem[pos - 1]););
1666 raise_error(RANGE_ERROR);
1667 return 0;
1668 } /* if */
1669 result <<= CHAR_BIT;
1670 result += byteStri->mem[pos - 1];
1671 } /* for */
1672 logFunction(printf("intBytesLe2Int --> " FMT_D "\n", result););
1673 return result;
1674 } /* intBytesLe2Int */
1675
1676
1677
1678 /**
1679 * Convert a string of bytes (interpreted as little-endian) to an integer.
1680 * @param byteStri String of bytes to be converted. The bytes are
1681 * interpreted as binary little-endian representation with a
1682 * base of 256.
1683 * @return an integer created from 'byteStri'. The result is always
1684 * positive.
1685 * @exception RANGE_ERROR If characters beyond '\255;' are present or
1686 * if the result value cannot be represented with an integer.
1687 */
1688 intType intBytesLe2UInt (const const_striType byteStri)
1689
1690 {
1691 memSizeType pos;
1692 intType result = 0;
1693
1694 /* intBytesLe2UInt */
1695 logFunction(printf("intBytesLe2UInt(\"%s\")\n",
1696 striAsUnquotedCStri(byteStri)););
1697 pos = byteStri->size;
1698 if (unlikely(byteStri->size >= sizeof(intType))) {
1699 while (pos > 0 && byteStri->mem[pos - 1] == 0) {
1700 pos--;
1701 } /* if */
1702 if (unlikely(pos > sizeof(intType) ||
1703 (pos == sizeof(intType) &&
1704 byteStri->mem[pos - 1] > BYTE_MAX))) {
1705 logError(printf("intBytesLe2UInt(\"%s\"): "
1706 "Number too big.\n",
1707 striAsUnquotedCStri(byteStri)););
1708 raise_error(RANGE_ERROR);
1709 return 0;
1710 } /* if */
1711 } /* if */
1712 for (; pos > 0; pos--) {
1713 if (unlikely(byteStri->mem[pos - 1] > UBYTE_MAX)) {
1714 logError(printf("intBytesLe2UInt(\"%s\"): "
1715 "Character '\\%d;' is beyond '\\255;'.\n",
1716 striAsUnquotedCStri(byteStri),
1717 byteStri->mem[pos - 1]););
1718 raise_error(RANGE_ERROR);
1719 return 0;
1720 } /* if */
1721 result <<= CHAR_BIT;
1722 result += byteStri->mem[pos - 1];
1723 } /* for */
1724 logFunction(printf("intBytesLe2UInt --> " FMT_D "\n", result););
1725 return result;
1726 } /* intBytesLe2UInt */
1727
1728
1729
1730 /**
1731 * Compare two integer numbers.
1732 * @return -1, 0 or 1 if the first argument is considered to be
1733 * respectively less than, equal to, or greater than the
1734 * second.
1735 */
1736 intType intCmp (intType number1, intType number2)
1737
1738 {
1739 intType signumValue;
1740
1741 /* intCmp */
1742 if (number1 < number2) {
1743 signumValue = -1;
1744 } else {
1745 signumValue = number1 > number2;
1746 } /* if */
1747 return signumValue;
1748 } /* intCmp */
1749
1750
1751
1752 /**
1753 * Reinterpret the generic parameters as intType and call intCmp.
1754 * Function pointers in C programs generated by the Seed7 compiler
1755 * may point to this function. This assures correct behaviour even
1756 * if sizeof(genericType) != sizeof(intType).
1757 * @return -1, 0 or 1 if the first argument is considered to be
1758 * respectively less than, equal to, or greater than the
1759 * second.
1760 */
1761 intType intCmpGeneric (const genericType value1, const genericType value2)
1762
1763 { /* intCmpGeneric */
1764 return intCmp(((const_rtlObjectType *) &value1)->value.intValue,
1765 ((const_rtlObjectType *) &value2)->value.intValue);
1766 } /* intCmpGeneric */
1767
1768
1769
1770 /**
1771 * Compute the truncated base 10 logarithm of an integer number.
1772 * The definition of intLog10 is extended by defining intLog10(0) = -1.
1773 * @return the truncated base 10 logarithm.
1774 * @exception NUMERIC_ERROR The number is negative.
1775 */
1776 intType intLog10 (intType number)
1777
1778 {
1779 int logarithm;
1780
1781 /* intLog10 */
1782 logFunction(printf("intLog10(" FMT_D ")\n", number););
1783 if (unlikely(number < 0)) {
1784 logError(printf("intLog10(" FMT_D "): Number is negative.\n",
1785 number););
1786 raise_error(NUMERIC_ERROR);
1787 logarithm = 0;
1788 } else if (number == 0) {
1789 logarithm = -1;
1790 } else {
1791 logarithm = DECIMAL_DIGITS((uintType) number) - 1;
1792 } /* if */
1793 logFunction(printf("intLog10 --> %d\n", logarithm););
1794 return (intType) logarithm;
1795 } /* intLog10 */
1796
1797
1798
1799 /**
1800 * Compute the truncated base 2 logarithm of an integer number.
1801 * The definition of intLog2 is extended by defining intLog2(0) = -1.
1802 * @return the truncated base 2 logarithm.
1803 * @exception NUMERIC_ERROR The number is negative.
1804 */
1805 intType intLog2 (intType number)
1806
1807 {
1808 int logarithm;
1809
1810 /* intLog2 */
1811 logFunction(printf("intLog2(" FMT_D ")\n", number););
1812 if (unlikely(number < 0)) {
1813 logError(printf("intLog2(" FMT_D "): Number is negative.\n",
1814 number););
1815 raise_error(NUMERIC_ERROR);
1816 logarithm = 0;
1817 } else {
1818 logarithm = uintMostSignificantBit((uintType) number);
1819 } /* if */
1820 logFunction(printf("intLog2 --> %d\n", logarithm););
1821 return (intType) logarithm;
1822 } /* intLog2 */
1823
1824
1825
1826 /**
1827 * Index of the lowest-order one bit.
1828 * For A <> 0 this is equal to the number of lowest-order zero bits.
1829 * @return the number of lowest-order zero bits or -1 for lowestSetBit(0).
1830 */
1831 intType intLowestSetBit (intType number)
1832
1833 {
1834 intType result;
1835
1836 /* intLowestSetBit */
1837 if (number == 0) {
1838 result = -1;
1839 } else {
1840 result = uintLeastSignificantBit((uintType) number);
1841 } /* if */
1842 return result;
1843 } /* intLowestSetBit */
1844
1845
1846
1847 /**
1848 * Convert integer to string and pad it with zeros at the left side.
1849 * The number is converted to a string with decimal representation.
1850 * For negative numbers a minus sign is prepended.
1851 * @param number Number to be converted to a string.
1852 * @param length Minimum length of the result.
1853 * @return number as decimal string left padded with zeroes.
1854 * @exception MEMORY_ERROR Not enough memory to represent the result.
1855 */
1856 striType intLpad0 (intType number, const intType padSize)
1857
1858 {
1859 uintType unsigned_number;
1860 boolType negative;
1861 strElemType *buffer;
1862 memSizeType length;
1863 memSizeType result_size;
1864 striType result;
1865
1866 /* intLpad0 */
1867 logFunction(printf("intLpad0(" FMT_D ", " FMT_D ")\n",
1868 number, padSize););
1869 negative = (number < 0);
1870 if (negative) {
1871 /* The unsigned value is negated to avoid a signed integer */
1872 /* overflow if the smallest signed integer is negated. */
1873 unsigned_number = -(uintType) number;
1874 } else {
1875 unsigned_number = (uintType) number;
1876 } /* if */
1877 length = DECIMAL_DIGITS(unsigned_number);
1878 if (negative) {
1879 length++;
1880 } /* if */
1881 if (padSize > (intType) length) {
1882 if (unlikely((uintType) padSize > MAX_STRI_LEN)) {
1883 raise_error(MEMORY_ERROR);
1884 return NULL;
1885 } else {
1886 result_size = (memSizeType) padSize;
1887 } /* if */
1888 } else {
1889 result_size = length;
1890 } /* if */
1891 if (unlikely(!ALLOC_STRI_SIZE_OK(result, result_size))) {
1892 raise_error(MEMORY_ERROR);
1893 } else {
1894 result->size = result_size;
1895 buffer = &result->mem[result_size];
1896 do {
1897 *(--buffer) = (strElemType) (unsigned_number % 10 + '0');
1898 } while ((unsigned_number /= 10) != 0);
1899 if (buffer != result->mem) {
1900 while (buffer != &result->mem[1]) {
1901 *(--buffer) = (strElemType) '0';
1902 } /* while */
1903 if (negative) {
1904 result->mem[0] = (strElemType) '-';
1905 } else {
1906 result->mem[0] = (strElemType) '0';
1907 } /* if */
1908 } /* if */
1909 } /* if */
1910 logFunction(printf("intLpad0 --> \"%s\"\n",
1911 striAsUnquotedCStri(result)););
1912 return result;
1913 } /* intLpad0 */
1914
1915
1916
1917 /**
1918 * Multiply two integer numbers.
1919 * @return the product of the two numbers.
1920 * @exception OVERFLOW_ERROR If an integer overflow occurs.
1921 */
1922 intType intMultOvfChk (intType factor1, intType factor2)
1923
1924 {
1925 intType product;
1926
1927 /* intMultOvfChk */
1928 logFunction(printf("intMultOvfChk(" FMT_D ", " FMT_D ")\n",
1929 factor1, factor2););
1930 if (factor1 < 0) {
1931 if (factor2 < 0) {
1932 if (unlikely(factor1 < INTTYPE_MAX / factor2)) {
1933 logError(printf("intMultOvfChk(" FMT_D ", " FMT_D "): "
1934 "factor1 < " FMT_D "\n",
1935 factor1, factor2, INTTYPE_MAX / factor2););
1936 raise_error(OVERFLOW_ERROR);
1937 return 0;
1938 } /* if */
1939 } else if (factor2 != 0) {
1940 if (unlikely(factor1 < INTTYPE_MIN / factor2)) {
1941 logError(printf("intMultOvfChk(" FMT_D ", " FMT_D "): "
1942 "factor1 < " FMT_D "\n",
1943 factor1, factor2, INTTYPE_MIN / factor2););
1944 raise_error(OVERFLOW_ERROR);
1945 return 0;
1946 } /* if */
1947 } /* if */
1948 } else if (factor1 != 0) {
1949 if (factor2 < 0) {
1950 if (unlikely(factor2 < INTTYPE_MIN / factor1)) {
1951 logError(printf("intMultOvfChk(" FMT_D ", " FMT_D "): "
1952 "factor2 < " FMT_D "\n",
1953 factor1, factor2, INTTYPE_MIN / factor1););
1954 raise_error(OVERFLOW_ERROR);
1955 return 0;
1956 } /* if */
1957 } else if (factor2 != 0) {
1958 if (unlikely(factor2 > INTTYPE_MAX / factor1)) {
1959 logError(printf("intMultOvfChk(" FMT_D ", " FMT_D "): "
1960 "factor2 > " FMT_D "\n",
1961 factor1, factor2, INTTYPE_MAX / factor1););
1962 raise_error(OVERFLOW_ERROR);
1963 return 0;
1964 } /* if */
1965 } /* if */
1966 } /* if */
1967 product = factor1 * factor2;
1968 logFunction(printf("intMultOvfChk --> " FMT_D "\n", product););
1969 return product;
1970 } /* intMultOvfChk */
1971
1972
1973
1974 #ifdef INT_MULT64_COMPILE_ERROR
1975 /**
1976 * Multiply two signed 64-bit int values and check for overflow.
1977 * Under Windows clang uses __mulodi4 if the option -ftrapv is used.
1978 * Unfortunately __mulodi4 is not part of the runtime library.
1979 * This rewrite of the original __mulodi4 needs only 56% of the runtime.
1980 */
1981 int64Type __mulodi4 (int64Type factor1, int64Type factor2, int *overflow)
1982
1983 {
1984 int64Type product;
1985
1986 /* __mulodi4 */
1987 logFunction(printf("__mulodi4(" FMT_D64 ", " FMT_D64 ", *)\n",
1988 factor1, factor2););
1989 product = (int64Type) ((uint64Type) factor1 * (uint64Type) factor2);
1990 if (factor1 < 0) {
1991 if (factor2 < 0) {
1992 if (unlikely(factor1 < INT64TYPE_MAX / factor2)) {
1993 *overflow = 1;
1994 logFunction(printf("__mulodi4(overflow=%d) --> " FMT_D64 "\n",
1995 *overflow, product););
1996 return product;
1997 } /* if */
1998 } else if (factor2 != 0) {
1999 if (unlikely(factor1 < INT64TYPE_MIN / factor2)) {
2000 *overflow = 1;
2001 logFunction(printf("__mulodi4(overflow=%d) --> " FMT_D64 "\n",
2002 *overflow, product););
2003 return product;
2004 } /* if */
2005 } /* if */
2006 } else if (factor1 != 0) {
2007 if (factor2 < 0) {
2008 if (unlikely(factor2 < INT64TYPE_MIN / factor1)) {
2009 *overflow = 1;
2010 logFunction(printf("__mulodi4(overflow=%d) --> " FMT_D64 "\n",
2011 *overflow, product););
2012 return product;
2013 } /* if */
2014 } else if (factor2 != 0) {
2015 if (unlikely(factor2 > INT64TYPE_MAX / factor1)) {
2016 *overflow = 1;
2017 logFunction(printf("__mulodi4(overflow=%d) --> " FMT_D64 "\n",
2018 *overflow, product););
2019 return product;
2020 } /* if */
2021 } /* if */
2022 } /* if */
2023 *overflow = 0;
2024 logFunction(printf("__mulodi4(overflow=%d) --> " FMT_D64 "\n",
2025 *overflow, product););
2026 return product;
2027 } /* __mulodi4 */
2028 #endif
2029
2030
2031
2032 /**
2033 * Convert an integer into a big-endian encoded string of bytes.
2034 * Negative numbers use a twos-complement representation.
2035 * The result uses a signed binary representation with a base of 256.
2036 * The result contains chars (bytes) with an ordinal <= 255.
2037 * @param number Integer number to be converted.
2038 * @param length Determines the length of the result string.
2039 * @return a string of 'length' bytes with the signed binary
2040 * representation of 'number'.
2041 * @exception RANGE_ERROR If 'length' is negative or zero, or
2042 * if the result would not fit in 'length' bytes.
2043 * @exception MEMORY_ERROR Not enough memory to represent the result.
2044 */
2045 striType intNBytesBeSigned (intType number, intType length)
2046
2047 {
2048 strElemType *buffer;
2049 memSizeType dataStart;
2050 memSizeType pos = 0;
2051 striType result;
2052
2053 /* intNBytesBeSigned */
2054 logFunction(printf("intNBytesBeSigned(" FMT_D ", " FMT_D ")\n", number, length););
2055 if (unlikely(length <= 0)) {
2056 logError(printf("intNBytesBeSigned(" FMT_D ", " FMT_D "): "
2057 "Negative length.\n", number, length););
2058 raise_error(RANGE_ERROR);
2059 result = NULL;
2060 } else if (unlikely((uintType) length > MAX_STRI_LEN ||
2061 !ALLOC_STRI_SIZE_OK(result, (memSizeType) length))) {
2062 raise_error(MEMORY_ERROR);
2063 result = NULL;
2064 } else {
2065 result->size = (memSizeType) length;
2066 if ((memSizeType) length > BYTE_BUFFER_SIZE) {
2067 dataStart = (memSizeType) length - BYTE_BUFFER_SIZE;
2068 } else {
2069 dataStart = 0;
2070 } /* if */
2071 buffer = result->mem;
2072 pos = (memSizeType) length;
2073 if (number >= 0) {
2074 do {
2075 pos--;
2076 buffer[pos] = (strElemType) (number & 0xff);
2077 number >>= CHAR_BIT;
2078 } while (pos > dataStart);
2079 if (pos > 0) {
2080 memset(buffer, 0, pos * sizeof(strElemType));
2081 } else if (unlikely(number != 0 || buffer[pos] > BYTE_MAX)) {
2082 logError(printf("intNBytesBeSigned: "
2083 "Number does not fit into " FMT_D " bytes.\n", length););
2084 FREE_STRI(result, (memSizeType) length);
2085 raise_error(RANGE_ERROR);
2086 result = NULL;
2087 } /* if */
2088 } else {
2089 do {
2090 pos--;
2091 buffer[pos] = (strElemType) (number & 0xff);
2092 #if RSHIFT_DOES_SIGN_EXTEND
2093 number >>= CHAR_BIT;
2094 #else
2095 number = ~(~number >> CHAR_BIT);
2096 #endif
2097 } while (pos > dataStart);
2098 if (pos > 0) {
2099 do {
2100 pos--;
2101 buffer[pos] = (strElemType) 0xff;
2102 } while (pos > dataStart);
2103 } else if (unlikely(number != -1 || buffer[pos] <= BYTE_MAX)) {
2104 logError(printf("intNBytesBeSigned: "
2105 "Number does not fit into " FMT_D " bytes.\n", length););
2106 FREE_STRI(result, (memSizeType) length);
2107 raise_error(RANGE_ERROR);
2108 result = NULL;
2109 } /* if */
2110 } /* if */
2111 } /* if */
2112 logFunction(printf("intNBytesBeSigned --> \"%s\"\n",
2113 striAsUnquotedCStri(result)););
2114 return result;
2115 } /* intNBytesBeSigned */
2116
2117
2118
2119 /**
2120 * Convert a positive integer into a big-endian encoded string of bytes.
2121 * The result uses an unsigned binary representation with a base of 256.
2122 * The result contains chars (bytes) with an ordinal <= 255.
2123 * @param number Integer number to be converted.
2124 * @param length Determines the length of the result string.
2125 * @return a string of 'length' bytes with the unsigned binary
2126 * representation of 'number'.
2127 * @exception RANGE_ERROR If 'length' is negative or zero, or
2128 * if 'number' is negative, or
2129 * if the result would not fit in 'length'' bytes.
2130 * @exception MEMORY_ERROR Not enough memory to represent the result.
2131 */
2132 striType intNBytesBeUnsigned (intType number, intType length)
2133
2134 {
2135 strElemType *buffer;
2136 memSizeType dataStart;
2137 memSizeType pos = 0;
2138 striType result;
2139
2140 /* intNBytesBeUnsigned */
2141 logFunction(printf("intNBytesBeUnsigned(" FMT_D ", " FMT_D ")\n",
2142 number, length););
2143 if (unlikely(length <= 0)) {
2144 logError(printf("intNBytesBeUnsigned(" FMT_D ", " FMT_D "): "
2145 "Negative length.\n", number, length););
2146 raise_error(RANGE_ERROR);
2147 result = NULL;
2148 } else if (unlikely(number < 0)) {
2149 logError(printf("intNBytesBeUnsigned(" FMT_D ", " FMT_D "): "
2150 "Negative number.\n",
2151 number, length););
2152 raise_error(RANGE_ERROR);
2153 return NULL;
2154 } else if (unlikely((uintType) length > MAX_STRI_LEN ||
2155 !ALLOC_STRI_SIZE_OK(result, (memSizeType) length))) {
2156 raise_error(MEMORY_ERROR);
2157 result = NULL;
2158 } else {
2159 result->size = (memSizeType) length;
2160 if ((memSizeType) length > BYTE_BUFFER_SIZE) {
2161 dataStart = (memSizeType) length - BYTE_BUFFER_SIZE;
2162 } else {
2163 dataStart = 0;
2164 } /* if */
2165 buffer = result->mem;
2166 pos = (memSizeType) length;
2167 do {
2168 pos--;
2169 buffer[pos] = (strElemType) (number & 0xff);
2170 number >>= CHAR_BIT;
2171 } while (pos > dataStart);
2172 if (pos > 0) {
2173 memset(buffer, 0, pos * sizeof(strElemType));
2174 } else if (unlikely(number != 0)) {
2175 logError(printf("intNBytesBeUnsigned: "
2176 "Number does not fit into " FMT_D " bytes.\n", length););
2177 FREE_STRI(result, (memSizeType) length);
2178 raise_error(RANGE_ERROR);
2179 result = NULL;
2180 } /* if */
2181 } /* if */
2182 logFunction(printf("intNBytesBeUnsigned --> \"%s\"\n",
2183 striAsUnquotedCStri(result)););
2184 return result;
2185 } /* intNBytesBeUnsigned */
2186
2187
2188
2189 /**
2190 * Convert an integer into a little-endian encoded string of bytes.
2191 * Negative numbers use a twos-complement representation.
2192 * The result uses a signed binary representation with a base of 256.
2193 * The result contains chars (bytes) with an ordinal <= 255.
2194 * @param number Integer number to be converted.
2195 * @param length Determines the length of the result string.
2196 * @return a string of 'length' bytes with the signed binary
2197 * representation of 'number'.
2198 * @exception RANGE_ERROR If 'length' is negative or zero, or
2199 * if the result would not fit in 'length' bytes.
2200 * @exception MEMORY_ERROR Not enough memory to represent the result.
2201 */
2202 striType intNBytesLeSigned (intType number, intType length)
2203
2204 {
2205 strElemType *buffer;
2206 memSizeType dataLength;
2207 memSizeType pos = 0;
2208 striType result;
2209
2210 /* intNBytesLeSigned */
2211 logFunction(printf("intNBytesLeSigned(" FMT_D ", " FMT_D ")\n", number, length););
2212 if (unlikely(length <= 0)) {
2213 logError(printf("intNBytesLeSigned(" FMT_D ", " FMT_D "): "
2214 "Negative length.\n", number, length););
2215 raise_error(RANGE_ERROR);
2216 result = NULL;
2217 } else if (unlikely((uintType) length > MAX_STRI_LEN ||
2218 !ALLOC_STRI_SIZE_OK(result, (memSizeType) length))) {
2219 raise_error(MEMORY_ERROR);
2220 result = NULL;
2221 } else {
2222 result->size = (memSizeType) length;
2223 if ((memSizeType) length > BYTE_BUFFER_SIZE) {
2224 dataLength = BYTE_BUFFER_SIZE;
2225 } else {
2226 dataLength = (memSizeType) length;
2227 } /* if */
2228 buffer = result->mem;
2229 if (number >= 0) {
2230 for (pos = 0; pos < dataLength; pos++) {
2231 buffer[pos] = (strElemType) (number & 0xff);
2232 number >>= CHAR_BIT;
2233 } /* for */
2234 if ((memSizeType) length > dataLength) {
2235 memset(&buffer[pos], 0, ((memSizeType) length - dataLength) * sizeof(strElemType));
2236 } else if (unlikely(number != 0 || buffer[pos - 1] > BYTE_MAX)) {
2237 logError(printf("intNBytesLeSigned: "
2238 "Number does not fit into " FMT_D " bytes.\n", length););
2239 FREE_STRI(result, (memSizeType) length);
2240 raise_error(RANGE_ERROR);
2241 result = NULL;
2242 } /* if */
2243 } else {
2244 for (pos = 0; pos < dataLength; pos++) {
2245 buffer[pos] = (strElemType) (number & 0xff);
2246 #if RSHIFT_DOES_SIGN_EXTEND
2247 number >>= CHAR_BIT;
2248 #else
2249 number = ~(~number >> CHAR_BIT);
2250 #endif
2251 } /* for */
2252 if ((memSizeType) length > dataLength) {
2253 for (; pos < (memSizeType) length; pos++) {
2254 buffer[pos] = (strElemType) 0xff;
2255 } /* for */
2256 } else if (unlikely(number != -1 || buffer[pos - 1] <= BYTE_MAX)) {
2257 logError(printf("intNBytesLeSigned: "
2258 "Number does not fit into " FMT_D " bytes.\n", length););
2259 FREE_STRI(result, (memSizeType) length);
2260 raise_error(RANGE_ERROR);
2261 result = NULL;
2262 } /* if */
2263 } /* if */
2264 } /* if */
2265 logFunction(printf("intNBytesLeSigned --> \"%s\"\n",
2266 striAsUnquotedCStri(result)););
2267 return result;
2268 } /* intNBytesLeSigned */
2269
2270
2271
2272 /**
2273 * Convert a positive integer into a little-endian encoded string of bytes.
2274 * The result uses an unsigned binary representation with a base of 256.
2275 * The result contains chars (bytes) with an ordinal <= 255.
2276 * @param number Integer number to be converted.
2277 * @param length Determines the length of the result string.
2278 * @return a string of 'length' bytes with the unsigned binary
2279 * representation of 'number'.
2280 * @exception RANGE_ERROR If 'length' is negative or zero, or
2281 * if 'number' is negative, or
2282 * if the result would not fit in 'length'' bytes.
2283 * @exception MEMORY_ERROR Not enough memory to represent the result.
2284 */
2285 striType intNBytesLeUnsigned (intType number, intType length)
2286
2287 {
2288 strElemType *buffer;
2289 memSizeType dataLength;
2290 memSizeType pos = 0;
2291 striType result;
2292
2293 /* intNBytesLeUnsigned */
2294 logFunction(printf("intNBytesLeUnsigned(" FMT_D ", " FMT_D ")\n",
2295 number, length););
2296 if (unlikely(length <= 0)) {
2297 logError(printf("intNBytesLeUnsigned(" FMT_D ", " FMT_D "): "
2298 "Negative length.\n", number, length););
2299 raise_error(RANGE_ERROR);
2300 result = NULL;
2301 } else if (unlikely(number < 0)) {
2302 logError(printf("intNBytesLeUnsigned(" FMT_D ", " FMT_D "): "
2303 "Negative number.\n",
2304 number, length););
2305 raise_error(RANGE_ERROR);
2306 return NULL;
2307 } else if (unlikely((uintType) length > MAX_STRI_LEN ||
2308 !ALLOC_STRI_SIZE_OK(result, (memSizeType) length))) {
2309 raise_error(MEMORY_ERROR);
2310 result = NULL;
2311 } else {
2312 result->size = (memSizeType) length;
2313 if ((memSizeType) length > BYTE_BUFFER_SIZE) {
2314 dataLength = BYTE_BUFFER_SIZE;
2315 } else {
2316 dataLength = (memSizeType) length;
2317 } /* if */
2318 buffer = result->mem;
2319 for (pos = 0; pos < dataLength; pos++) {
2320 buffer[pos] = (strElemType) (number & 0xff);
2321 number >>= CHAR_BIT;
2322 } /* for */
2323 if ((memSizeType) length > dataLength) {
2324 memset(&buffer[pos], 0, ((memSizeType) length - dataLength) * sizeof(strElemType));
2325 } else if (unlikely(number != 0)) {
2326 logError(printf("intNBytesLeUnsigned: "
2327 "Number does not fit into " FMT_D " bytes.\n", length););
2328 FREE_STRI(result, (memSizeType) length);
2329 raise_error(RANGE_ERROR);
2330 result = NULL;
2331 } /* if */
2332 } /* if */
2333 logFunction(printf("intNBytesLeUnsigned --> \"%s\"\n",
2334 striAsUnquotedCStri(result)););
2335 return result;
2336 } /* intNBytesLeUnsigned */
2337
2338
2339
2340 /**
2341 * Convert a string to an integer number.
2342 * The string must contain an integer literal consisting of an
2343 * optional + or - sign, followed by a sequence of digits. Other
2344 * characters as well as leading or trailing whitespace characters
2345 * are not allowed. The sequence of digits is taken to be decimal.
2346 * @return the integer result of the conversion.
2347 * @exception RANGE_ERROR If the string is empty or it does not contain
2348 * an integer literal or if the integer literal is too big
2349 * or too small to be represented as integer value.
2350 */
2351 intType intParse (const const_striType stri)
2352
2353 {
2354 boolType okay;
2355 boolType negative;
2356 memSizeType position = 0;
2357 uintType digitval;
2358 uintType uintValue;
2359 intType intResult;
2360
2361 /* intParse */
2362 logFunction(printf("intParse(\"%s\")\n", striAsUnquotedCStri(stri)););
2363 if (likely(stri->size != 0)) {
2364 if (stri->mem[0] == ((strElemType) '-')) {
2365 negative = TRUE;
2366 position++;
2367 } else {
2368 if (stri->mem[0] == ((strElemType) '+')) {
2369 position++;
2370 } /* if */
2371 negative = FALSE;
2372 } /* if */
2373 } /* if */
2374 if (unlikely(position >= stri->size)) {
2375 logError(printf("intParse(\"%s\"): "
2376 "Digit missing.\n",
2377 striAsUnquotedCStri(stri)););
2378 raise_error(RANGE_ERROR);
2379 intResult = 0;
2380 } else {
2381 uintValue = 0;
2382 okay = TRUE;
2383 #if TWOS_COMPLEMENT_INTTYPE
2384 while (position < stri->size &&
2385 (digitval = ((uintType) stri->mem[position]) - ((uintType) '0')) <= 9) {
2386 #else
2387 while (position < stri->size &&
2388 stri->mem[position] >= ((strElemType) '0') &&
2389 stri->mem[position] <= ((strElemType) '9')) {
2390 digitval = ((uintType) stri->mem[position]) - ((uintType) '0');
2391 #endif
2392 if (unlikely(uintValue > MAX_DIV_10)) {
2393 okay = FALSE;
2394 } else {
2395 uintValue = ((uintType) 10) * uintValue + digitval;
2396 } /* if */
2397 position++;
2398 } /* while */
2399 if (unlikely(position < stri->size)) {
2400 logError(printf("intParse(\"%s\"): "
2401 "Illegal digit.\n",
2402 striAsUnquotedCStri(stri)););
2403 raise_error(RANGE_ERROR);
2404 intResult = 0;
2405 } else if (unlikely(!okay)) {
2406 logError(printf("intParse(\"%s\"): "
2407 "Absolute value of literal is too big.\n",
2408 striAsUnquotedCStri(stri)););
2409 raise_error(RANGE_ERROR);
2410 intResult = 0;
2411 } else {
2412 if (negative) {
2413 #if TWOS_COMPLEMENT_INTTYPE
2414 if (uintValue > (uintType) INTTYPE_MAX + 1) {
2415 logError(printf("intParse(\"%s\"): Literal too small.\n",
2416 striAsUnquotedCStri(stri)););
2417 raise_error(RANGE_ERROR);
2418 intResult = 0;
2419 } else {
2420 /* The unsigned value is negated to avoid an overflow */
2421 /* if the most negative intType value is negated. */
2422 intResult = (intType) -uintValue;
2423 } /* if */
2424 #else
2425 intResult = (intType) -uintValue;
2426 #endif
2427 } else if (uintValue > (uintType) INTTYPE_MAX) {
2428 logError(printf("intParse(\"%s\"): Literal too big.\n",
2429 striAsUnquotedCStri(stri)););
2430 raise_error(RANGE_ERROR);
2431 intResult = 0;
2432 } else {
2433 intResult = (intType) uintValue;
2434 } /* if */
2435 } /* if */
2436 } /* if */
2437 logFunction(printf("intParse --> " FMT_D "\n", intResult););
2438 return intResult;
2439 } /* intParse */
2440
2441
2442
2443 /**
2444 * Compute the exponentiation of a integer base with an integer exponent.
2445 * @return the result of the exponentiation.
2446 * @exception NUMERIC_ERROR If the exponent is negative.
2447 */
2448 intType intPow (intType base, intType exponent)
2449
2450 {
2451 intType power;
2452
2453 /* intPow */
2454 logFunction(printf("intPow(" FMT_D ", " FMT_D ")\n", base, exponent););
2455 if (unlikely(exponent < 0)) {
2456 logError(printf("intPow(" FMT_D ", " FMT_D "): "
2457 "Exponent is negative.\n",
2458 base, exponent););
2459 raise_error(NUMERIC_ERROR);
2460 power = 0;
2461 } else {
2462 if (exponent & 1) {
2463 power = base;
2464 } else {
2465 power = 1;
2466 } /* if */
2467 exponent >>= 1;
2468 while (exponent != 0) {
2469 base *= base;
2470 if (exponent & 1) {
2471 power *= base;
2472 } /* if */
2473 exponent >>= 1;
2474 } /* while */
2475 } /* if */
2476 logFunction(printf("intPow --> " FMT_D "\n", power););
2477 return power;
2478 } /* intPow */
2479
2480
2481
2482 /**
2483 * Compute the exponentiation of a integer base with an integer exponent.
2484 * @return the result of the exponentiation.
2485 * @exception NUMERIC_ERROR If the exponent is negative.
2486 * @exception OVERFLOW_ERROR If an integer overflow occurs.
2487 */
2488 intType intPowOvfChk (intType base, intType exponent)
2489
2490 {
2491 intType power;
2492
2493 /* intPowOvfChk */
2494 logFunction(printf("intPowOvfChk(" FMT_D ", " FMT_D ")\n",
2495 base, exponent););
2496 if (unlikely(exponent < 0)) {
2497 logError(printf("intPowOvfChk(" FMT_D ", " FMT_D "): "
2498 "Exponent is negative.\n",
2499 base, exponent););
2500 raise_error(NUMERIC_ERROR);
2501 power = 0;
2502 } else {
2503 if ((uintType) exponent < sizeof(minBaseOfExponent) / sizeof(intType)) {
2504 if (unlikely(base < minBaseOfExponent[exponent] ||
2505 base > maxBaseOfExponent[exponent])) {
2506 logError(printf("intPowOvfChk(" FMT_D ", " FMT_D "): "
2507 "Base wrong: ",
2508 base, exponent);
2509 if (base < minBaseOfExponent[exponent]) {
2510 printf(FMT_D " < " FMT_D "\n",
2511 base, minBaseOfExponent[exponent]);
2512 } else {
2513 printf(FMT_D " > " FMT_D "\n",
2514 base, maxBaseOfExponent[exponent]);
2515 });
2516 raise_error(OVERFLOW_ERROR);
2517 return 0;
2518 } /* if */
2519 } else if (unlikely(base < -8 || base > 8 ||
2520 exponent > maxExponentOfBase[base + 8])) {
2521 logError(printf("intPowOvfChk(" FMT_D ", " FMT_D "): ",
2522 base, exponent);
2523 if (base < -8) {
2524 printf("Base wrong: " FMT_D " < -8\n", base);
2525 } else if (base > 8) {
2526 printf("Base wrong: " FMT_D " > 8\n", base);
2527 } else {
2528 printf("Exponent wrong: " FMT_D " > " FMT_D "\n",
2529 exponent, maxExponentOfBase[base + 8]);
2530 });
2531 raise_error(OVERFLOW_ERROR);
2532 return 0;
2533 } /* if */
2534 if (exponent & 1) {
2535 power = base;
2536 } else {
2537 power = 1;
2538 } /* if */
2539 exponent >>= 1;
2540 while (exponent != 0) {
2541 base *= base;
2542 if (exponent & 1) {
2543 power *= base;
2544 } /* if */
2545 exponent >>= 1;
2546 } /* while */
2547 } /* if */
2548 logFunction(printf("intPowOvfChk --> " FMT_D "\n", power););
2549 return power;
2550 } /* intPowOvfChk */
2551
2552
2553
2554 /**
2555 * Convert an integer number to a string using a radix.
2556 * The conversion uses the numeral system with the given base.
2557 * Digit values from 10 upward are encoded with letters.
2558 * E.g.: 10 is encoded with A or a, 11 with B or b, etc.
2559 * For negative numbers a minus sign is prepended.
2560 * @param number Number to be converted to a string.
2561 * @param base Base of the numeral system used for the conversion.
2562 * @param upperCase Decides about the letter case.
2563 * @return the string result of the conversion.
2564 * @exception RANGE_ERROR If base < 2 or base > 36 holds.
2565 * @exception MEMORY_ERROR Not enough memory to represent the result.
2566 */
2567 striType intRadix (intType number, intType base, boolType upperCase)
2568
2569 {
2570 uintType unsigned_number;
2571 boolType negative;
2572 const_ustriType digits;
2573 strElemType buffer_1[RADIX_BUFFER_SIZE];
2574 strElemType *buffer;
2575 memSizeType length;
2576 striType result;
2577
2578 /* intRadix */
2579 logFunction(printf("intRadix(" FMT_D ", " FMT_D ", %d)\n",
2580 number, base, upperCase););
2581 if (unlikely(base < 2 || base > 36)) {
2582 logError(printf("intRadix(" FMT_D ", " FMT_D ", %d): "
2583 "base < 2 or base > 36.\n",
2584 number, base, upperCase););
2585 raise_error(RANGE_ERROR);
2586 result = NULL;
2587 } else {
2588 negative = (number < 0);
2589 if (negative) {
2590 /* The unsigned value is negated to avoid a signed integer */
2591 /* overflow if the smallest signed integer is negated. */
2592 unsigned_number = -(uintType) number;
2593 } else {
2594 unsigned_number = (uintType) number;
2595 } /* if */
2596 digits = digitTable[upperCase];
2597 buffer = &buffer_1[RADIX_BUFFER_SIZE];
2598 do {
2599 *(--buffer) = (strElemType) (digits[unsigned_number % (uintType) base]);
2600 } while ((unsigned_number /= (uintType) base) != 0);
2601 if (negative) {
2602 *(--buffer) = (strElemType) '-';
2603 } /* if */
2604 length = (memSizeType) (&buffer_1[RADIX_BUFFER_SIZE] - buffer);
2605 if (unlikely(!ALLOC_STRI_SIZE_OK(result, length))) {
2606 raise_error(MEMORY_ERROR);
2607 } else {
2608 result->size = length;
2609 memcpy(result->mem, buffer, (size_t) (length * sizeof(strElemType)));
2610 } /* if */
2611 } /* if */
2612 logFunction(printf("intRadix --> \"%s\"\n", striAsUnquotedCStri(result)););
2613 return result;
2614 } /* intRadix */
2615
2616
2617
2618 /**
2619 * Convert an integer number to a string using a radix.
2620 * The conversion uses the numeral system with the specified base.
2621 * The base is a power of two and it is specified indirectly with
2622 * shift and mask. Digit values from 10 upward are encoded with
2623 * letters.
2624 * @param number Number to be converted to a string.
2625 * @param shift Logarithm (log2) of the base (=number of bits in mask).
2626 * @param mask Mask to get the bits of a digit (equivalent to base-1).
2627 * @param upperCase Decides about the letter case.
2628 * @return the string result of the conversion.
2629 * @exception MEMORY_ERROR Not enough memory to represent the result.
2630 */
2631 striType intRadixPow2 (intType number, int shift, int mask, boolType upperCase)
2632
2633 {
2634 uintType unsigned_number;
2635 boolType negative;
2636 const_ustriType digits;
2637 strElemType buffer_1[RADIX_BUFFER_SIZE];
2638 strElemType *buffer;
2639 memSizeType length;
2640 striType result;
2641
2642 /* intRadixPow2 */
2643 logFunction(printf("intRadixPow2(" FMT_D ", %d, %x, %d)\n",
2644 number, shift, mask, upperCase););
2645 negative = (number < 0);
2646 if (negative) {
2647 /* The unsigned value is negated to avoid a signed integer */
2648 /* overflow if the smallest signed integer is negated. */
2649 unsigned_number = -(uintType) number;
2650 } else {
2651 unsigned_number = (uintType) number;
2652 } /* if */
2653 digits = digitTable[upperCase];
2654 buffer = &buffer_1[RADIX_BUFFER_SIZE];
2655 do {
2656 *(--buffer) = (strElemType) (digits[unsigned_number & (uintType) mask]);
2657 } while ((unsigned_number >>= shift) != 0);
2658 if (negative) {
2659 *(--buffer) = (strElemType) '-';
2660 } /* if */
2661 length = (memSizeType) (&buffer_1[RADIX_BUFFER_SIZE] - buffer);
2662 if (unlikely(!ALLOC_STRI_SIZE_OK(result, length))) {
2663 raise_error(MEMORY_ERROR);
2664 } else {
2665 result->size = length;
2666 memcpy(result->mem, buffer, (size_t) (length * sizeof(strElemType)));
2667 } /* if */
2668 logFunction(printf("intRadixPow2 --> \"%s\"\n",
2669 striAsUnquotedCStri(result)););
2670 return result;
2671 } /* intRadixPow2 */
2672
2673
2674
2675 /**
2676 * Compute pseudo-random number in the range [low, high].
2677 * The random values are uniform distributed.
2678 * @return a random number such that low <= rand(low, high) and
2679 * rand(low, high) <= high holds.
2680 * @exception RANGE_ERROR The range is empty (low > high holds).
2681 */
2682 intType intRand (intType low, intType high)
2683
2684 {
2685 uintType scale_limit;
2686 uintType rand_max;
2687 uintType rand_val;
2688 intType randomNumber;
2689
2690 /* intRand */
2691 logFunction(printf("intRand(" FMT_D ", " FMT_D ")\n", low, high););
2692 if (unlikely(low >= high)) {
2693 if (low == high) {
2694 randomNumber = low;
2695 } else {
2696 logError(printf("intRand(" FMT_D ", " FMT_D "): "
2697 "The range is empty (low > high holds).\n",
2698 low, high););
2699 raise_error(RANGE_ERROR);
2700 randomNumber = 0;
2701 } /* if */
2702 } else {
2703 scale_limit = (uintType) high - (uintType) low;
2704 if (unlikely(scale_limit == UINTTYPE_MAX)) {
2705 /* low must be INTTYPE_MIN and high must be INTTYPE_MAX. */
2706 randomNumber = (intType) uintRand();
2707 } else {
2708 scale_limit++;
2709 /* Here 2 <= scale_limit <= UINTTYPE_MAX holds. */
2710 /* Set rand_max to be one less than a multiple of scale_limit. */
2711 /* Furthermore rand_max is set to a value that is as big as */
2712 /* possible but less than or equal to UINTTYPE_MAX. */
2713 rand_max = UINTTYPE_MAX - (UINTTYPE_MAX - scale_limit + 1) % scale_limit;
2714 do {
2715 rand_val = uintRand();
2716 } while (rand_val > rand_max);
2717 randomNumber = (intType) ((uintType) low + rand_val % scale_limit);
2718 } /* if */
2719 } /* if */
2720 logFunction(printf("intRand --> " FMT_D "\n", randomNumber););
2721 return randomNumber;
2722 } /* intRand */
2723
2724
2725
2726 /**
2727 * Compute the integer square root of an integer radicand.
2728 * @return the integer square root.
2729 * @exception NUMERIC_ERROR If the radicand is negative.
2730 */
2731 intType intSqrt (intType radicand)
2732
2733 {
2734 register uintType root;
2735 register uintType root2;
2736
2737 /* intSqrt */
2738 logFunction(printf("intSqrt(" FMT_D ")\n", radicand););
2739 if (unlikely(radicand < 0)) {
2740 logError(printf("intSqrt(" FMT_D "): Radicand is negative.\n",
2741 radicand););
2742 raise_error(NUMERIC_ERROR);
2743 root = 0;
2744 } else if (radicand == 0) {
2745 root = 0;
2746 } else {
2747 root2 = (uintType) radicand;
2748 do {
2749 root = root2;
2750 root2 = (root + (uintType) radicand / root) >> 1;
2751 } while (root > root2);
2752 } /* if */
2753 logFunction(printf("intSqrt --> " FMT_U "\n", root););
2754 return (intType) root;
2755 } /* intSqrt */
2756
2757
2758
2759 /**
2760 * Convert an integer number to a string.
2761 * The number is converted to a string with decimal representation.
2762 * For negative numbers a minus sign is prepended.
2763 * @return the string result of the conversion.
2764 * @exception MEMORY_ERROR Not enough memory to represent the result.
2765 */
2766 striType intStr (intType number)
2767
2768 {
2769 register uintType unsigned_number;
2770 boolType negative;
2771 strElemType *buffer;
2772 memSizeType length;
2773 striType result;
2774
2775 /* intStr */
2776 logFunction(printf("intStr(" FMT_D ")\n", number););
2777 negative = (number < 0);
2778 if (negative) {
2779 /* The unsigned value is negated to avoid a signed integer */
2780 /* overflow if the smallest signed integer is negated. */
2781 unsigned_number = -(uintType) number;
2782 } else {
2783 unsigned_number = (uintType) number;
2784 } /* if */
2785 length = DECIMAL_DIGITS(unsigned_number);
2786 if (negative) {
2787 length++;
2788 } /* if */
2789 if (unlikely(!ALLOC_STRI_SIZE_OK(result, length))) {
2790 raise_error(MEMORY_ERROR);
2791 } else {
2792 result->size = length;
2793 buffer = &result->mem[length];
2794 do {
2795 *(--buffer) = (strElemType) (unsigned_number % 10 + '0');
2796 } while ((unsigned_number /= 10) != 0);
2797 if (negative) {
2798 result->mem[0] = (strElemType) '-';
2799 } /* if */
2800 } /* if */
2801 logFunction(printf("intStr --> \"%s\"\n",
2802 striAsUnquotedCStri(result)););
2803 return result;
2804 } /* intStr */
2805
2806
2807
2808 #if ALLOW_STRITYPE_SLICES
2809 /**
2810 * Convert an integer number to a string in a buffer.
2811 * The number is converted to a string with decimal representation.
2812 * For negative numbers a minus sign is prepended.
2813 * @return the buffer with the string result of the conversion.
2814 */
2815 striType intStrToBuffer (intType number, striType buffer)
2816
2817 {
2818 register uintType unsigned_number;
2819 boolType negative;
2820 strElemType *bufferPtr;
2821
2822 /* intStrToBuffer */
2823 logFunction(printf("intStrToBuffer(" FMT_D ")\n", number););
2824 negative = (number < 0);
2825 if (negative) {
2826 /* The unsigned value is negated to avoid a signed integer */
2827 /* overflow if the smallest signed integer is negated. */
2828 unsigned_number = -(uintType) number;
2829 } else {
2830 unsigned_number = (uintType) number;
2831 } /* if */
2832 bufferPtr = &buffer->mem1[INTTYPE_DECIMAL_SIZE];
2833 do {
2834 *(--bufferPtr) = (strElemType) (unsigned_number % 10 + '0');
2835 } while ((unsigned_number /= 10) != 0);
2836 if (negative) {
2837 *(--bufferPtr) = (strElemType) '-';
2838 } /* if */
2839 buffer->mem = bufferPtr;
2840 buffer->size = (memSizeType) (&buffer->mem1[INTTYPE_DECIMAL_SIZE] - bufferPtr);
2841 logFunction(printf("intStrToBuffer --> \"%s\"\n",
2842 striAsUnquotedCStri(buffer)););
2843 return buffer;
2844 } /* intStrToBuffer */
2845 #endif
2846