1 /*
2 $Id: intobj.c 2609 2021-04-25 10:52:48Z soci $
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
18 */
19 #include "intobj.h"
20 #include <string.h>
21 #include "math.h"
22 #include "unicode.h"
23 #include "encoding.h"
24 #include "error.h"
25 #include "eval.h"
26 #include "variables.h"
27 #include "arguments.h"
28
29 #include "boolobj.h"
30 #include "floatobj.h"
31 #include "codeobj.h"
32 #include "strobj.h"
33 #include "bytesobj.h"
34 #include "bitsobj.h"
35 #include "typeobj.h"
36 #include "noneobj.h"
37 #include "errorobj.h"
38 #include "addressobj.h"
39 #include "functionobj.h"
40
41 #define SHIFT (8 * (unsigned int)sizeof(digit_t))
42 #define MASK (~(digit_t)0)
43 #define DSHIFT 9
44 #define DMUL ((digit_t)1000000000)
45
46 static Type obj;
47
48 static Int minus1_val = { { &obj, 1 }, -1, {1, 0}, minus1_val.val };
49 static Int zero_val = { { &obj, 1 }, 0, {0, 0}, zero_val.val };
50 static Int one_val = { { &obj, 1 }, 1, {1, 0}, one_val.val };
51
52 Type *const INT_OBJ = &obj;
53 Obj *const int_value[2] = { &zero_val.v, &one_val.v };
54 Obj *const minus1_value = &minus1_val.v;
55
ref_int(Int * v1)56 static inline Int *ref_int(Int *v1) {
57 v1->v.refcount++; return v1;
58 }
59
intlen(const Int * v1)60 static inline size_t intlen(const Int *v1) {
61 ssize_t len = v1->len;
62 return (size_t)(len < 0 ? -len : len);
63 }
64
int_from_obj(Obj * v1,linepos_t epoint)65 MUST_CHECK Obj *int_from_obj(Obj *v1, linepos_t epoint) {
66 switch (v1->obj->type) {
67 case T_NONE:
68 case T_ERROR:
69 case T_INT: return val_reference(v1);
70 case T_FLOAT: return int_from_float(Float(v1), epoint);
71 case T_CODE: return int_from_code(Code(v1), epoint);
72 case T_STR: return int_from_str(Str(v1), epoint);
73 case T_BOOL: return int_from_bool(Bool(v1));
74 case T_BYTES: return int_from_bytes(Bytes(v1), epoint);
75 case T_BITS: return int_from_bits(Bits(v1), epoint);
76 case T_ADDRESS: return int_from_address(Address(v1), epoint);
77 default: break;
78 }
79 return new_error_conv(v1, INT_OBJ, epoint);
80 }
81
convert(oper_t op)82 static MUST_CHECK Obj *convert(oper_t op) {
83 return int_from_obj(op->v2, op->epoint2);
84 }
85
int_destroy(Int * v1)86 static FAST_CALL NO_INLINE void int_destroy(Int *v1) {
87 free(v1->data);
88 }
89
destroy(Obj * o1)90 static FAST_CALL void destroy(Obj *o1) {
91 Int *v1 = Int(o1);
92 if (v1->val != v1->data) int_destroy(v1);
93 }
94
new_int(void)95 static inline MALLOC Int *new_int(void) {
96 return Int(val_alloc(INT_OBJ));
97 }
98
inew(Int * v,size_t len)99 static digit_t *inew(Int *v, size_t len) {
100 if (len <= lenof(v->val)) return v->val;
101 if (len > SIZE_MAX / sizeof *v->data) err_msg_out_of_memory(); /* overflow */
102 return (digit_t *)mallocx(len * sizeof *v->data);
103 }
104
inew2(Int * v,size_t len)105 static digit_t *inew2(Int *v, size_t len) {
106 if (len <= lenof(v->val)) return v->val;
107 if (len > SIZE_MAX / sizeof *v->data) return NULL; /* overflow */
108 return (digit_t *)malloc(len * sizeof *v->data);
109 }
110
negate(Int * v1,linepos_t epoint)111 static MUST_CHECK Obj *negate(Int *v1, linepos_t epoint) {
112 Int *v;
113 size_t ln;
114 if (v1->len == 0) return val_reference(int_value[0]);
115 v = new_int();
116 ln = intlen(v1);
117 v->data = inew2(v, ln);
118 if (v->data == NULL) goto failed2;
119 v->len = -v1->len;
120 memcpy(v->data, v1->data, ln * sizeof *v->data);
121 return Obj(v);
122 failed2:
123 val_destroy(Obj(v));
124 return new_error_mem(epoint);
125 }
126
zeroint(Int * v)127 static FAST_CALL NO_INLINE Obj *zeroint(Int *v) {
128 val_destroy(Obj(v));
129 return val_reference(int_value[0]);
130 }
131
normalize2(Int * v,size_t sz)132 static FAST_CALL NO_INLINE Obj *normalize2(Int *v, size_t sz) {
133 do {
134 sz--;
135 v->val[sz] = v->data[sz];
136 } while (sz != 0);
137 free(v->data);
138 v->data = v->val;
139 return Obj(v);
140 }
141
normalize(Int * v,size_t sz,bool neg)142 static FAST_CALL MUST_CHECK Obj *normalize(Int *v, size_t sz, bool neg) {
143 digit_t *d = v->data;
144 while (sz != 0 && d[sz - 1] == 0) sz--;
145 if (sz == 0) return zeroint(v);
146 /*if (sz > SSIZE_MAX) err_msg_out_of_memory();*/ /* overflow */
147 v->len = (ssize_t)(neg ? -sz : sz);
148 if (v->val != d && sz <= lenof(v->val)) {
149 return normalize2(v, sz);
150 }
151 return Obj(v);
152 }
153
return_int(digit_t c,bool neg)154 static MUST_CHECK Obj *return_int(digit_t c, bool neg) {
155 Int *vv;
156 if (c < lenof(int_value) && (!neg || c == 0)) return val_reference(int_value[c]);
157 vv = new_int();
158 vv->data = vv->val;
159 vv->val[0] = c;
160 vv->len = neg ? -1 : 1;
161 return Obj(vv);
162 }
163
return_int_inplace(Int * vv,digit_t c,bool neg)164 static MUST_CHECK Obj *return_int_inplace(Int *vv, digit_t c, bool neg) {
165 if (vv->data != vv->val) {
166 int_destroy(vv);
167 vv->data = vv->val;
168 }
169 vv->val[0] = c;
170 vv->len = c == 0 ? 0 : neg ? -1 : 1;
171 return val_reference(Obj(vv));
172 }
173
int_same(const Int * v1,const Int * v2)174 static FAST_CALL NO_INLINE bool int_same(const Int *v1, const Int *v2) {
175 return memcmp(v1->data, v2->data, intlen(v1) * sizeof *v1->data) == 0;
176 }
177
same(const Obj * o1,const Obj * o2)178 static FAST_CALL bool same(const Obj *o1, const Obj *o2) {
179 const Int *v1 = Int(o1), *v2 = Int(o2);
180 if (o1->obj != o2->obj || v1->len != v2->len) return false;
181 switch (v1->len) {
182 case 0: return true;
183 case -1:
184 case 1: return v1->data[0] == v2->data[0];
185 default: return int_same(v1, v2);
186 }
187 }
188
truth(Obj * o1,Truth_types UNUSED (type),linepos_t UNUSED (epoint))189 static MUST_CHECK Obj *truth(Obj *o1, Truth_types UNUSED(type), linepos_t UNUSED(epoint)) {
190 return truth_reference(Int(o1)->len != 0);
191 }
192
hash(Obj * o1,int * hs,linepos_t UNUSED (epoint))193 static MUST_CHECK Obj *hash(Obj *o1, int *hs, linepos_t UNUSED(epoint)) {
194 Int *v1 = Int(o1);
195 ssize_t l = v1->len;
196 unsigned int h;
197
198 switch (l) {
199 case -1: *hs = (-v1->val[0]) & ((~0U) >> 1); return NULL;
200 case 0: *hs = 0; return NULL;
201 case 1: *hs = v1->val[0] & ((~0U) >> 1); return NULL;
202 }
203 h = 0;
204 if (l > 0) {
205 while ((l--) != 0) {
206 h += v1->data[l];
207 }
208 } else {
209 while ((l++) != 0) {
210 h -= v1->data[-l];
211 }
212 }
213 *hs = h & ((~0U) >> 1);
214 return NULL;
215 }
216
repr(Obj * o1,linepos_t UNUSED (epoint),size_t maxsize)217 static MUST_CHECK Obj *repr(Obj *o1, linepos_t UNUSED(epoint), size_t maxsize) {
218 Int *v1 = Int(o1);
219 size_t len = intlen(v1);
220 bool neg = v1->len < 0;
221 uint8_t *s;
222 digit_t ten, r, *out;
223 size_t slen, i, j, sz, len2;
224 Int tmp;
225 Str *v;
226
227 if (len <= 1) {
228 static const digit_t d[9] = {1000000000, 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10};
229 digit_t dec;
230 i = 9;
231 if (len != 0) {
232 len = (v1->len < 0) ? 1U : 0U;
233 dec = v1->val[0];
234 for (; i > 0; i--) {
235 if (dec < d[i - 1]) break;
236 }
237 } else dec = 0;
238 len += 10 - i;
239 if (len > maxsize) return NULL;
240 v = new_str2(len);
241 if (v == NULL) return NULL;
242 v->chars = len;
243 s = v->data;
244 if (v1->len < 0) *s++ = '-';
245 for (; i < 9; i++) {
246 digit_t a = dec / d[i];
247 dec = dec % d[i];
248 *s++ = (uint8_t)('0' + a);
249 }
250 *s = (uint8_t)('0' + dec);
251 return Obj(v);
252 }
253
254 sz = len * SHIFT / (3 * DSHIFT);
255 if (len > SSIZE_MAX / SHIFT) return NULL; /* overflow */
256 if (sz * DSHIFT > maxsize) return NULL;
257 sz++;
258 out = inew2(&tmp, sz);
259 if (out == NULL) return NULL;
260
261 for (sz = 0, i = len; (i--) != 0;) {
262 digit_t h = v1->data[i];
263 for (j = 0; j < sz; j++) {
264 twodigits_t tm = ((twodigits_t)out[j] << SHIFT) | h;
265 h = (digit_t)(tm / DMUL);
266 out[j] = (digit_t)(tm - (twodigits_t)h * DMUL);
267 }
268 while (h != 0) {
269 out[sz++] = h % DMUL;
270 h /= DMUL;
271 }
272 }
273 if (sz == 0) out[sz] = 0;
274 else sz--;
275 slen = neg ? 2 : 1;
276 ten = 10;
277 r = out[sz];
278 while (r >= ten) {
279 ten *= 10;
280 slen++;
281 }
282 len2 = sz * DSHIFT;
283 slen += len2;
284 if (slen < len2 || sz > SIZE_MAX / DSHIFT) goto error; /* overflow */
285 if (slen > maxsize) {
286 error:
287 if (tmp.val != out) free(out);
288 return NULL;
289 }
290 v = new_str2(slen);
291 if (v == NULL) goto error;
292 v->chars = slen;
293 s = v->data + slen;
294 for (i = 0; i < sz; i++) {
295 r = out[i];
296 for (j = 0; j < DSHIFT; j++) {
297 *--s = (uint8_t)('0' + (r % 10));
298 r /= 10;
299 }
300 }
301 r = out[i];
302 do {
303 *--s = (uint8_t)('0' + (r % 10));
304 r /= 10;
305 } while (r != 0);
306 if (neg) *--s = '-';
307
308 if (tmp.val != out) free(out);
309 return Obj(v);
310 }
311
ival(Obj * o1,ival_t * iv,unsigned int bits,linepos_t epoint)312 static MUST_CHECK Error *ival(Obj *o1, ival_t *iv, unsigned int bits, linepos_t epoint) {
313 Int *v1 = Int(o1);
314 Error *v;
315 digit_t d;
316 switch (v1->len) {
317 case 1: d = v1->data[0];
318 *iv = (ival_t)d;
319 if (bits <= SHIFT && (d >> (bits - 1)) != 0) break;
320 return NULL;
321 case 0: *iv = 0; return NULL;
322 case -1: d = v1->data[0];
323 *iv = -(ival_t)d;
324 if (bits <= SHIFT && ((d - 1) >> (bits - 1)) != 0) break;
325 return NULL;
326 default: break;
327 }
328 v = new_error(ERROR_____CANT_IVAL, epoint);
329 v->u.intconv.bits = bits;
330 v->u.intconv.val = val_reference(o1);
331 return v;
332 }
333
uval(Obj * o1,uval_t * uv,unsigned int bits,linepos_t epoint)334 static MUST_CHECK Error *uval(Obj *o1, uval_t *uv, unsigned int bits, linepos_t epoint) {
335 Int *v1 = Int(o1);
336 Error *v;
337 switch (v1->len) {
338 case 1: *uv = v1->data[0];
339 if (bits < SHIFT && (*uv >> bits) != 0) break;
340 return NULL;
341 case 0: *uv = 0; return NULL;
342 default: break;
343 }
344 v = new_error(v1->len < 0 ? ERROR______NOT_UVAL : ERROR_____CANT_UVAL, epoint);
345 v->u.intconv.bits = bits;
346 v->u.intconv.val = val_reference(o1);
347 return v;
348 }
349
float_from_int(const Int * v1,linepos_t epoint)350 MUST_CHECK Obj *float_from_int(const Int *v1, linepos_t epoint) {
351 size_t i, len1;
352 double d;
353 switch (v1->len) {
354 case -1: d = -(double)v1->data[0]; break;
355 case 0: d = 0.0; break;
356 case 1: d = v1->data[0]; break;
357 default:
358 len1 = intlen(v1); d = v1->data[0];
359 for (i = 1; i < len1; i++) {
360 d += ldexp(v1->data[i], (int)(i * SHIFT));
361 }
362 if (v1->len < 0) d = -d;
363 return float_from_double(d, epoint);
364 }
365 return new_float(d);
366 }
367
sign(Obj * o1,linepos_t UNUSED (epoint))368 static MUST_CHECK Obj *sign(Obj *o1, linepos_t UNUSED(epoint)) {
369 Int *v1 = Int(o1);
370 return val_reference(v1->len < 0 ? minus1_value : int_value[(v1->len > 0) ? 1 : 0]);
371 }
372
function(oper_t op)373 static MUST_CHECK Obj *function(oper_t op) {
374 Int *v1 = Int(op->v2);
375 if (v1->len >= 0 || Function(op->v1)->func != F_ABS) return Obj(ref_int(v1));
376 if (op->inplace == Obj(v1)) {
377 v1->len = -v1->len;
378 return val_reference(Obj(v1));
379 }
380 return negate(v1, op->epoint2);
381 }
382
383 static void iadd(const Int *, const Int *, Int *);
384 static void isub(const Int *, const Int *, Int *);
385
ldigit(const Int * v1)386 static inline unsigned int ldigit(const Int *v1) {
387 ssize_t len = v1->len;
388 if (len < 0) return ~v1->data[0] + 1U;
389 return (len != 0) ? v1->data[0] : 0;
390 }
391
calc1(oper_t op)392 static MUST_CHECK Obj *calc1(oper_t op) {
393 Int *v1 = Int(op->v1), *v;
394 switch (op->op) {
395 case O_BANK:
396 case O_HIGHER:
397 case O_LOWER:
398 case O_HWORD:
399 case O_WORD:
400 case O_BSWORD:
401 return bits_calc1(op->op, ldigit(v1));
402 case O_INV:
403 v = new_int();
404 if (v1->len < 0) isub(v1, Int(int_value[1]), v);
405 else {
406 iadd(v1, Int(int_value[1]), v);
407 v->len = -v->len;
408 }
409 return Obj(v);
410 case O_NEG:
411 if (op->inplace != Obj(v1)) return negate(v1, op->epoint3);
412 v1->len = -v1->len;
413 return val_reference(Obj(v1));
414 case O_POS: return Obj(ref_int(v1));
415 case O_STRING:
416 {
417 Obj *o = repr(Obj(v1), op->epoint, SIZE_MAX);
418 return (o != NULL) ? o : new_error_mem(op->epoint3);
419 }
420 case O_LNOT:
421 if (diagnostics.strict_bool) err_msg_bool_oper(op);
422 return truth_reference(v1->len == 0);
423 default: break;
424 }
425 return obj_oper_error(op);
426 }
427
iadd(const Int * vv1,const Int * vv2,Int * vv)428 static void iadd(const Int *vv1, const Int *vv2, Int *vv) {
429 size_t i, len1, len2;
430 digit_t *v1, *v2, *v;
431 digit_t d;
432 digit_t c;
433 len1 = intlen(vv1);
434 len2 = intlen(vv2);
435 if (len1 <= 1 && len2 <= 1) {
436 v = vv->data = vv->val;
437 d = vv1->val[0];
438 v[0] = d + vv2->val[0];
439 if (v[0] < d) {
440 v[1] = 1;
441 vv->len = 2;
442 return;
443 }
444 vv->len = (v[0] != 0) ? 1 : 0;
445 return;
446 }
447 if (len1 < len2) {
448 const Int *tmp = vv1; vv1 = vv2; vv2 = tmp;
449 i = len1; len1 = len2; len2 = i;
450 }
451 if (len1 + 1 < 1) err_msg_out_of_memory(); /* overflow */
452 v = inew(vv, len1 + 1);
453 v1 = vv1->data; v2 = vv2->data;
454 for (c = 0, i = 0; i < len2; i++) {
455 d = v1[i];
456 v[i] = d + v2[i] + c;
457 c = ((c != 0) ? (v[i] <= d) : (v[i] < d)) ? 1 : 0;
458 }
459 for (;i < len1; i++) {
460 v[i] = v1[i] + c;
461 c = (v[i] < c) ? 1 : 0;
462 }
463 if (c != 0) v[i++] = 1;
464 while (i != 0 && v[i - 1] == 0) i--;
465 if (v != vv->val && i <= lenof(vv->val)) {
466 memcpy(vv->val, v, i * sizeof *v);
467 free(v);
468 v = vv->val;
469 }
470 if (vv == vv1 || vv == vv2) destroy(Obj(vv));
471 vv->data = v;
472 vv->len = (ssize_t)i;
473 }
474
isub(const Int * vv1,const Int * vv2,Int * vv)475 static void isub(const Int *vv1, const Int *vv2, Int *vv) {
476 size_t i, len1, len2;
477 digit_t *v1, *v2, *v;
478 bool c;
479 bool neg;
480 len1 = intlen(vv1);
481 len2 = intlen(vv2);
482 if (len1 <= 1 && len2 <= 1) {
483 digit_t d1 = vv1->val[0], d2 = vv2->val[0];
484 v = vv->val;
485 vv->data = v;
486 if (d1 < d2) {
487 v[0] = d2 - d1;
488 vv->len = -1;
489 return;
490 }
491 v[0] = d1 - d2;
492 vv->len = (v[0] != 0) ? 1 : 0;
493 return;
494 }
495 if (len1 < len2) {
496 const Int *tmp = vv1; vv1 = vv2; vv2 = tmp;
497 neg = true;
498 i = len1; len1 = len2; len2 = i;
499 } else {
500 neg = false;
501 if (len1 == len2) {
502 i = len1;
503 v1 = vv1->data; v2 = vv2->data;
504 while (i != 0 && v1[i - 1] == v2[i - 1]) i--;
505 if (i == 0) {
506 if (vv == vv1 || vv == vv2) destroy(Obj(vv));
507 vv->len = 0;
508 vv->val[0] = 0;
509 vv->data = vv->val;
510 return;
511 }
512 if (v1[i - 1] < v2[i - 1]) {
513 const Int *tmp = vv1; vv1 = vv2; vv2 = tmp;
514 neg = true;
515 }
516 len1 = len2 = i;
517 }
518 }
519 v = inew(vv, len1);
520 v1 = vv1->data; v2 = vv2->data;
521 for (c = false, i = 0; i < len2; i++) {
522 if (c) {
523 c = (v1[i] <= v2[i]);
524 v[i] = v1[i] - v2[i] - 1;
525 continue;
526 }
527 c = (v1[i] < v2[i]);
528 v[i] = v1[i] - v2[i];
529 }
530 for (;c && i < len1; i++) {
531 c = (v1[i] == 0);
532 v[i] = v1[i] - 1;
533 }
534 for (;i < len1; i++) v[i] = v1[i];
535 while (i != 0 && v[i - 1] == 0) i--;
536 if (v != vv->val && i <= lenof(vv->val)) {
537 memcpy(vv->val, v, i * sizeof *v);
538 free(v);
539 v = vv->val;
540 }
541 if (vv == vv1 || vv == vv2) destroy(Obj(vv));
542 vv->data = v;
543 vv->len = (ssize_t)(neg ? -i : i);
544 }
545
imul(const Int * vv1,const Int * vv2,Int * vv)546 static void imul(const Int *vv1, const Int *vv2, Int *vv) {
547 size_t i, j, len1, len2, sz;
548 digit_t *v1, *v2, *v;
549 Int tmp;
550 len1 = intlen(vv1);
551 len2 = intlen(vv2);
552 sz = len1 + len2;
553 if (sz < len2) err_msg_out_of_memory(); /* overflow */
554 if (sz <= 2) {
555 twodigits_t c = (twodigits_t)vv1->val[0] * vv2->val[0];
556 v = vv->val;
557 vv->data = v;
558 if (c > (twodigits_t)MASK) {
559 v[0] = (digit_t)c;
560 v[1] = (digit_t)(c >> SHIFT);
561 vv->len = 2;
562 return;
563 }
564 v[0] = (digit_t)c;
565 vv->len = (v[0] != 0) ? 1 : 0;
566 return;
567 }
568 v = inew(&tmp, sz);
569 memset(v, 0, sz * sizeof *v);
570 v1 = vv1->data; v2 = vv2->data;
571 for (i = 0; i < len1; i++) {
572 twodigits_t c = 0, t = v1[i];
573 digit_t *o = v + i;
574 for (j = 0; j < len2; j++) {
575 c += o[j] + v2[j] * t;
576 o[j] = (digit_t)c;
577 c >>= SHIFT;
578 }
579 if (c != 0) o[j] += (digit_t)c;
580 }
581 i = sz;
582 while (i != 0 && v[i - 1] == 0) i--;
583 if (vv == vv1 || vv == vv2) destroy(Obj(vv));
584 if (i <= lenof(vv->val)) {
585 if (i != 0) memcpy(vv->val, v, i * sizeof *v); else vv->val[0] = 0;
586 if (tmp.val != v) free(v);
587 v = vv->val;
588 }
589 vv->data = v;
590 vv->len = (ssize_t)i;
591 }
592
idivrem(oper_t op,bool divrem)593 static MUST_CHECK Obj *idivrem(oper_t op, bool divrem) {
594 Int *vv1 = Int(op->v1), *vv2 = Int(op->v2);
595 size_t len1, len2;
596 bool neg, negr;
597 digit_t *v1, *v2, *v;
598 Int *vv;
599
600 len2 = intlen(vv2);
601 if (len2 == 0) {
602 return new_error_obj(ERROR_DIVISION_BY_Z, op->v2, op->epoint3);
603 }
604 len1 = intlen(vv1);
605 v1 = vv1->data;
606 v2 = vv2->data;
607 negr = (vv1->len < 0);
608 neg = (negr != (vv2->len < 0));
609 if (len1 < len2 || (len1 == len2 && v1[len1 - 1] < v2[len2 - 1])) {
610 return val_reference(divrem ? ((neg && len1 != 0) ? minus1_value : int_value[0]) : Obj(vv1));
611 }
612 if (len2 == 1) {
613 size_t i;
614 twodigits_t r;
615 digit_t n = v2[0];
616 if (len1 == 1) {
617 if (divrem) {
618 digit_t t = v1[0] / n;
619 if (neg && v1[0] != t * n) t++;
620 return op->inplace == Obj(vv1) ? return_int_inplace(vv1, t, neg) : return_int(t, neg);
621 }
622 n = v1[0] % n;
623 return op->inplace == Obj(vv1) ? return_int_inplace(vv1, n, negr) : return_int(n, negr);
624 }
625 r = 0;
626 if (divrem) {
627 vv = new_int();
628 vv->data = v = inew(vv, len1);
629 for (i = len1; (i--) != 0;) {
630 digit_t h;
631 r = (r << SHIFT) | v1[i];
632 h = (digit_t)(r / n);
633 v[i] = h;
634 r -= (twodigits_t)h * n;
635 }
636 if (neg && r != 0) {
637 for (i = 0; i < len1; i++) {
638 if ((v[i] = v[i] + 1) >= 1) break;
639 }
640 }
641 return normalize(vv, len1, neg);
642 }
643 for (i = len1; (i--) != 0;) {
644 digit_t h;
645 r = (r << SHIFT) | v1[i];
646 h = (digit_t)(r / n);
647 r -= (twodigits_t)h * n;
648 }
649 return op->inplace == Obj(vv1) ? return_int_inplace(vv1, (digit_t)r, negr) : return_int((digit_t)r, negr);
650 } else {
651 size_t i, k;
652 unsigned int d;
653 digit_t wm1, wm2, *v0, *vk, *w0, *ak, *a;
654 Int tmp1, tmp2, tmp3;
655
656 if (len1 + 1 < 1) err_msg_out_of_memory(); /* overflow */
657 v0 = inew(&tmp1, len1 + 1);
658 w0 = inew(&tmp2, len2);
659
660 d = 0;
661 while ((v2[len2 - 1] << d) <= MASK / 2) d++;
662
663 if (d != 0) {
664 w0[0] = v2[0] << d;
665 for (i = 1; i < len2; i++) w0[i] = (v2[i] << d) | (v2[i - 1] >> (SHIFT - d));
666 v0[0] = v1[0] << d;
667 for (i = 1; i < len1; i++) v0[i] = (v1[i] << d) | (v1[i - 1] >> (SHIFT - d));
668 v0[i] = v1[i - 1] >> (SHIFT - d);
669 } else {
670 memcpy(w0, v2, len2 * sizeof *w0);
671 v0[len1] = 0;
672 memcpy(v0, v1, len1 * sizeof *v0);
673 }
674 if (v0[len1] != 0 || v0[len1 - 1] >= w0[len2 - 1]) len1++;
675
676 k = len1 - len2;
677 a = inew(&tmp3, k);
678
679 wm1 = w0[len2 - 1]; wm2 = w0[len2 - 2];
680 for (vk = v0 + k, ak = a + k; vk-- > v0;) {
681 bool c = false;
682 digit_t vtop = vk[len2];
683 twodigits_t vvv = ((twodigits_t)vtop << SHIFT) | vk[len2 - 1];
684 digit_t q = (digit_t)(vvv / wm1);
685 digit_t r = (digit_t)(vvv - (twodigits_t)q * wm1);
686 twodigits_t e;
687 while ((twodigits_t)q * wm2 > (((twodigits_t)r << SHIFT) | vk[len2 - 2])) {
688 --q;
689 r += wm1;
690 if (r < wm1) break;
691 }
692 for (e = i = 0; i < len2; i++) {
693 digit_t t;
694 e += (twodigits_t)q * w0[i];
695 t = (digit_t)e; e >>= SHIFT;
696 if (c) {
697 c = (vk[i] <= t);
698 vk[i] = vk[i] - t - 1;
699 continue;
700 }
701 c = vk[i] < t;
702 vk[i] -= t;
703 }
704 if (c ? (vtop <= e) : (vtop < e)) {
705 c = false;
706 for (i = 0; i < len2; i++) {
707 digit_t t = vk[i];
708 if (c) {
709 c = ((vk[i] = t + w0[i] + 1) <= t);
710 continue;
711 }
712 c = ((vk[i] = t + w0[i]) < t);
713 }
714 --q;
715 }
716 *--ak = q;
717 }
718 if (w0 != tmp2.val) free(w0);
719
720 vv = new_int();
721 if (divrem) {
722 if (neg) {
723 while (len2 != 0 && v0[len2 - 1] == 0) len2--;
724 if (len2 != 0) {
725 for (i = 0; i < k; i++) {
726 if ((a[i] = a[i] + 1) >= 1) break;
727 }
728 }
729 }
730 if (v0 != tmp1.val) free(v0);
731 if (a == tmp3.val) {
732 memcpy(&vv->val, a, k * sizeof *a);
733 a = vv->val;
734 }
735 vv->data = a;
736 return normalize(vv, k, neg);
737 }
738
739 if (d != 0) {
740 for (i = 0; i < len2 - 1; i++) v0[i] = (v0[i] >> d) | (v0[i + 1] << (SHIFT - d));
741 v0[i] >>= d;
742 }
743
744 if (a != tmp3.val) free(a);
745 if (v0 == tmp1.val) {
746 memcpy(&vv->val, v0, len2 * sizeof *v0);
747 v0 = vv->val;
748 }
749 vv->data = v0;
750 return normalize(vv, len2, negr);
751 }
752 }
753
power(oper_t op)754 static inline MUST_CHECK Obj *power(oper_t op) {
755 const Int *vv1 = Int(op->v1), *vv2 = Int(op->v2);
756 int j;
757 bool neg = false;
758 size_t i;
759 Int *v = new_int();
760 v->data = v->val;
761 v->val[0] = 1;
762 v->len = 1;
763
764 for (i = (size_t)vv2->len; (i--) != 0;) {
765 digit_t d = vv2->data[i];
766 for (j = SHIFT - 1; j >= 0; j--) {
767 imul(v, v, v);
768 if ((d & (1U << j)) != 0) {
769 imul(v, vv1, v);
770 neg = true;
771 } else neg = false;
772 }
773 }
774 if (neg && vv1->len < 0) v->len = -v->len;
775 return Obj(v);
776 }
777
lshift(oper_t op,uval_t s)778 static MUST_CHECK Obj *lshift(oper_t op, uval_t s) {
779 Int *vv1 = Int(op->v1);
780 size_t i, len1, sz;
781 unsigned int word, bit;
782 digit_t *v1, *v, *v2;
783 Int *vv;
784
785 if (vv1->len == 0) return val_reference(int_value[0]);
786 sz = word = s / SHIFT;
787 bit = s % SHIFT;
788 if (bit != 0) sz++;
789 len1 = intlen(vv1);
790 sz += len1;
791 if (sz < len1) goto failed; /* overflow */
792 if (op->inplace == Obj(vv1) && sz <= lenof(vv->val)) {
793 vv = ref_int(vv1);
794 v = vv->data;
795 } else {
796 vv = new_int();
797 vv->data = v = inew2(vv, sz);
798 if (v == NULL) goto failed2;
799 }
800 v1 = vv1->data;
801 v2 = v + word;
802 if (bit != 0) {
803 digit_t d = 0;
804 for (i = len1; i != 0;) {
805 digit_t d2 = v1[--i];
806 v2[i + 1] = d | (d2 >> (SHIFT - bit));
807 d = d2 << bit;
808 }
809 v2[0] = d;
810 } else if (len1 != 0) memmove(v2, v1, len1 * sizeof *v2);
811 if (word != 0) memset(v, 0, word * sizeof *v);
812
813 return normalize(vv, sz, vv1->len < 0);
814 failed2:
815 val_destroy(Obj(vv));
816 failed:
817 return new_error_mem(op->epoint3);
818 }
819
rshift(oper_t op,uval_t s)820 static MUST_CHECK Obj *rshift(oper_t op, uval_t s) {
821 Int *vv1 = Int(op->v1);
822 size_t i, sz;
823 unsigned int word, bit;
824 bool neg;
825 digit_t *v1, *v;
826 Int *vv;
827
828 switch (vv1->len) {
829 case 1:
830 if (s < SHIFT) {
831 digit_t d = vv1->val[0] >> s;
832 return op->inplace == Obj(vv1) ? return_int_inplace(vv1, d, false) : return_int(d, false);
833 }
834 /* fall through */
835 case 0:
836 return val_reference(int_value[0]);
837 default: break;
838 }
839
840 word = s / SHIFT;
841 bit = s % SHIFT;
842 neg = (vv1->len < 0);
843 if (neg) {
844 vv = new_int();
845 isub(vv1, Int(int_value[1]), vv);
846 vv1 = vv;
847 if ((size_t)vv->len <= word) {
848 val_destroy(Obj(vv));
849 return val_reference(minus1_value);
850 }
851 sz = (size_t)vv->len - word;
852 v = vv->data;
853 } else {
854 if ((size_t)vv1->len <= word) return val_reference(int_value[0]);
855 sz = (size_t)vv1->len - word;
856 if (op->inplace == Obj(vv1)) {
857 vv = ref_int(vv1);
858 v = vv->data;
859 }
860 else {
861 vv = new_int();
862 vv->data = v = inew2(vv, sz);
863 if (v == NULL) goto failed2;
864 }
865 }
866 v1 = vv1->data + word;
867 if (bit != 0) {
868 for (i = 0; i < sz - 1; i++) {
869 v[i] = v1[i] >> bit;
870 v[i] |= v1[i + 1] << (SHIFT - bit);
871 }
872 v[i] = v1[i] >> bit;
873 } else if (sz != 0) memmove(v, v1, sz * sizeof *v);
874
875 if (neg) {
876 vv->len = (ssize_t)sz;
877 iadd(Int(int_value[1]), vv, vv);
878 vv->len = -vv->len;
879 return Obj(vv);
880 }
881 return normalize(vv, sz, false);
882 failed2:
883 val_destroy(Obj(vv));
884 return new_error_mem(op->epoint3);
885 }
886
and_(oper_t op)887 static inline MUST_CHECK Obj *and_(oper_t op) {
888 Int *vv1 = Int(op->v1), *vv2 = Int(op->v2);
889 size_t i, len1, len2, sz;
890 bool neg1, neg2;
891 digit_t *v1, *v2, *v;
892 Int *vv;
893 len1 = intlen(vv1);
894 len2 = intlen(vv2);
895
896 if (len1 <= 1 && len2 <= 1) {
897 digit_t c;
898 neg1 = (vv1->len < 0); neg2 = (vv2->len < 0);
899 c = neg1 ? -vv1->val[0] : vv1->val[0];
900 c &= neg2 ? -vv2->val[0] : vv2->val[0];
901 if (!neg2) neg1 = false;
902 if (neg1) c = -c;
903 return op->inplace == Obj(vv1) ? return_int_inplace(vv1, c, neg1) : return_int(c, neg1);
904 }
905 if (len1 < len2) {
906 Int *tmp = vv1; vv1 = vv2; vv2 = tmp;
907 i = len1; len1 = len2; len2 = i;
908 }
909 v1 = vv1->data; v2 = vv2->data;
910 neg1 = (vv1->len < 0); neg2 = (vv2->len < 0);
911
912 sz = neg2 ? len1 : len2;
913 if (neg1 && neg2) sz++;
914 if (sz == 0) return val_reference(int_value[0]);
915 vv = new_int();
916 vv->data = v = inew2(vv, sz);
917 if (v == NULL) goto failed2;
918
919 if (neg1) {
920 if (neg2) {
921 bool c1 = true, c2 = true, c = true;
922 for (i = 0; i < len2; i++) {
923 digit_t e = v1[i], f = v2[i], g;
924 if (c1) {
925 c1 = (e == 0);
926 if (c2) {
927 c2 = (f == 0);
928 g = (~e + 1) & (~f + 1);
929 } else g = (~e + 1) & ~f;
930 } else {
931 if (c2) {
932 c2 = (f == 0);
933 g = ~e & (~f + 1);
934 } else g = ~e & ~f;
935 }
936 if (c) {
937 c = (g == 0);
938 v[i] = ~g + 1;
939 continue;
940 }
941 v[i] = ~g;
942 }
943 if (c2) {
944 if (c) for (; i < len1; i++) v[i] = 0;
945 else for (; i < len1; i++) v[i] = ~(digit_t)0;
946 } else {
947 for (; i < len1; i++) {
948 digit_t e = v1[i], g;
949 if (c1) {
950 c1 = (e == 0);
951 g = ~e + 1;
952 } else g = ~e;
953 if (c) {
954 c = (g == 0);
955 v[i] = ~g + 1;
956 continue;
957 }
958 v[i] = ~g;
959 }
960 }
961 v[i] = c ? 1 : 0;
962 } else {
963 bool c1 = true;
964 for (i = 0; i < len2; i++) {
965 digit_t e = v1[i], f = v2[i];
966 if (c1) {
967 c1 = (e == 0);
968 v[i] = (~e + 1) & f;
969 continue;
970 }
971 v[i] = ~e & f;
972 }
973 }
974 } else {
975 if (neg2) {
976 bool c2 = true;
977 for (i = 0; i < len2; i++) {
978 digit_t e = v1[i], f = v2[i];
979 if (c2) {
980 c2 = f == 0;
981 v[i] = e & (~f + 1);
982 continue;
983 }
984 v[i] = e & ~f;
985 }
986 if (c2) for (; i < len1; i++) v[i] = 0;
987 else for (; i < len1; i++) v[i] = v1[i];
988 } else {
989 for (i = 0; i < len2; i++) v[i] = v1[i] & v2[i];
990 }
991 }
992 return normalize(vv, sz, neg1 && neg2);
993 failed2:
994 val_destroy(Obj(vv));
995 return new_error_mem(op->epoint3);
996 }
997
or_(oper_t op)998 static inline MUST_CHECK Obj *or_(oper_t op) {
999 Int *vv1 = Int(op->v1), *vv2 = Int(op->v2);
1000 size_t i, len1, len2, sz;
1001 bool neg1, neg2;
1002 digit_t *v1, *v2, *v;
1003 Int *vv;
1004 len1 = intlen(vv1);
1005 len2 = intlen(vv2);
1006
1007 if (len1 <= 1 && len2 <= 1) {
1008 digit_t c;
1009 neg1 = (vv1->len < 0); neg2 = (vv2->len < 0);
1010 c = neg1 ? -vv1->val[0] : vv1->val[0];
1011 c |= neg2 ? -vv2->val[0] : vv2->val[0];
1012 if (neg2) neg1 = true;
1013 if (neg1) c = -c;
1014 return op->inplace == Obj(vv1) ? return_int_inplace(vv1, c, neg1) : return_int(c, neg1);
1015 }
1016 if (len1 < len2) {
1017 Int *tmp = vv1; vv1 = vv2; vv2 = tmp;
1018 i = len1; len1 = len2; len2 = i;
1019 }
1020 v1 = vv1->data; v2 = vv2->data;
1021 neg1 = (vv1->len < 0); neg2 = (vv2->len < 0);
1022
1023 sz = neg2 ? len2 : len1;
1024 if (neg1 || neg2) sz++;
1025 vv = new_int();
1026 vv->data = v = inew2(vv, sz);
1027 if (v == NULL) goto failed2;
1028
1029 if (neg1) {
1030 bool c = true;
1031 if (neg2) {
1032 bool c1 = true, c2 = true;
1033 for (i = 0; i < len2; i++) {
1034 digit_t e = v1[i], f = v2[i], g;
1035 if (c1) {
1036 c1 = e == 0;
1037 if (c2) {
1038 c2 = f == 0;
1039 g = (~e + 1) | (~f + 1);
1040 } else g = (~e + 1) | ~f;
1041 } else {
1042 if (c2) {
1043 c2 = f == 0;
1044 g = ~e | (~f + 1);
1045 } else g = ~e | ~f;
1046 }
1047 if (c) {
1048 c = g == 0;
1049 v[i] = ~g + 1;
1050 continue;
1051 }
1052 v[i] = ~g;
1053 }
1054 } else {
1055 bool c1 = true;
1056 for (i = 0; i < len2; i++) {
1057 digit_t e = v1[i], f = v2[i], g;
1058 if (c1) {
1059 c1 = e == 0;
1060 g = (~e + 1) | f;
1061 } else g = ~e | f;
1062 if (c) {
1063 c = g == 0;
1064 v[i] = ~g + 1;
1065 continue;
1066 }
1067 v[i] = ~g;
1068 }
1069 for (; i < len1; i++) {
1070 digit_t e = v1[i], g;
1071 if (c1) {
1072 c1 = e == 0;
1073 g = ~e + 1;
1074 } else g = ~e;
1075 if (c) {
1076 c = g == 0;
1077 v[i] = ~g + 1;
1078 continue;
1079 }
1080 v[i] = ~g;
1081 }
1082 }
1083 v[i] = c ? 1 : 0;
1084 } else {
1085 if (neg2) {
1086 bool c2 = true, c = true;
1087 for (i = 0; i < len2; i++) {
1088 digit_t e = v1[i], f = v2[i], g;
1089 if (c2) {
1090 c2 = (f == 0);
1091 g = e | (~f + 1);
1092 } else g = e | ~f;
1093 if (c) {
1094 c = (g == 0);
1095 v[i] = ~g + 1;
1096 continue;
1097 }
1098 v[i] = ~g;
1099 }
1100 v[i] = c ? 1 : 0;
1101 } else {
1102 for (i = 0; i < len2; i++) v[i] = v1[i] | v2[i];
1103 for (; i < len1; i++) v[i] = v1[i];
1104 }
1105 }
1106 return normalize(vv, sz, neg1 || neg2);
1107 failed2:
1108 val_destroy(Obj(vv));
1109 return new_error_mem(op->epoint3);
1110 }
1111
xor_(oper_t op)1112 static inline MUST_CHECK Obj *xor_(oper_t op) {
1113 Int *vv1 = Int(op->v1), *vv2 = Int(op->v2);
1114 size_t i, len1, len2, sz;
1115 bool neg1, neg2;
1116 digit_t *v1, *v2, *v;
1117 Int *vv;
1118 len1 = intlen(vv1);
1119 len2 = intlen(vv2);
1120
1121 if (len1 <= 1 && len2 <= 1) {
1122 digit_t c;
1123 neg1 = (vv1->len < 0); neg2 = (vv2->len < 0);
1124 c = neg1 ? -vv1->val[0] : vv1->val[0];
1125 c ^= neg2 ? -vv2->val[0] : vv2->val[0];
1126 if (neg2) neg1 = !neg1;
1127 if (neg1) c = -c;
1128 return op->inplace == Obj(vv1) ? return_int_inplace(vv1, c, neg1) : return_int(c, neg1);
1129 }
1130 if (len1 < len2) {
1131 Int *tmp = vv1; vv1 = vv2; vv2 = tmp;
1132 i = len1; len1 = len2; len2 = i;
1133 }
1134 v1 = vv1->data; v2 = vv2->data;
1135 neg1 = (vv1->len < 0); neg2 = (vv2->len < 0);
1136
1137 sz = (neg1 != neg2) ? (len1 + 1) : len1;
1138 vv = new_int();
1139 vv->data = v = inew2(vv, sz);
1140 if (v == NULL) goto failed2;
1141
1142 if (neg1) {
1143 if (neg2) {
1144 bool c1 = true, c2 = true;
1145 for (i = 0; i < len2; i++) {
1146 digit_t e = v1[i], f = v2[i], g;
1147 if (c1) {
1148 c1 = e == 0;
1149 if (c2) {
1150 c2 = f == 0;
1151 g = (~e + 1) ^ (~f + 1);
1152 } else g = (~e + 1) ^ ~f;
1153 } else {
1154 if (c2) {
1155 c2 = f == 0;
1156 g = ~e ^ (~f + 1);
1157 } else g = e ^ f;
1158 }
1159 v[i] = g;
1160 }
1161 for (; i < len1; i++) {
1162 digit_t e = v1[i], g;
1163 if (c1) {
1164 c1 = e == 0;
1165 g = ~e + 1;
1166 } else g = ~e;
1167 v[i] = c2 ? g : ~g;
1168 }
1169 } else {
1170 bool c1 = true, c = true;
1171 for (i = 0; i < len2; i++) {
1172 digit_t e = v1[i], f = v2[i], g;
1173 if (c1) {
1174 c1 = (e == 0);
1175 g = (~e + 1) ^ f;
1176 } else g = ~e ^ f;
1177 if (c) {
1178 c = (g == 0);
1179 v[i] = ~g + 1;
1180 continue;
1181 }
1182 v[i] = ~g;
1183 }
1184 for (; i < len1; i++) {
1185 digit_t e = v1[i], g;
1186 if (c1) {
1187 c1 = (e == 0);
1188 g = ~e + 1;
1189 } else g = ~e;
1190 if (c) {
1191 c = (g == 0);
1192 v[i] = ~g + 1;
1193 continue;
1194 }
1195 v[i] = ~g;
1196 }
1197 v[i] = c ? 1 : 0;
1198 }
1199 } else {
1200 if (neg2) {
1201 bool c2 = true, c = true;
1202 for (i = 0; i < len2; i++) {
1203 digit_t e = v1[i], f = v2[i], g;
1204 if (c2) {
1205 c2 = (f == 0);
1206 g = e ^ (~f + 1);
1207 } else g = e ^ ~f;
1208 if (c) {
1209 c = (g == 0);
1210 v[i] = ~g + 1;
1211 continue;
1212 }
1213 v[i] = ~g;
1214 }
1215 for (; i < len1; i++) {
1216 digit_t e = v1[i], g;
1217 g = c2 ? e : ~e;
1218 if (c) {
1219 c = (g == 0);
1220 v[i] = ~g + 1;
1221 continue;
1222 }
1223 v[i] = ~g;
1224 }
1225 v[i] = c ? 1 : 0;
1226 } else {
1227 for (i = 0; i < len2; i++) v[i] = v1[i] ^ v2[i];
1228 for (; i < len1; i++) v[i] = v1[i];
1229 }
1230 }
1231 return normalize(vv, sz, neg1 != neg2);
1232 failed2:
1233 val_destroy(Obj(vv));
1234 return new_error_mem(op->epoint3);
1235 }
1236
icmp(oper_t op)1237 static ssize_t icmp(oper_t op) {
1238 const Int *vv1 = Int(op->v1), *vv2 = Int(op->v2);
1239 ssize_t i;
1240 size_t j;
1241 digit_t a, b;
1242 i = vv1->len - vv2->len;
1243 if (i != 0) return i;
1244 j = intlen(vv1);
1245 while (j != 0) {
1246 j--;
1247 a = vv1->data[j]; b = vv2->data[j];
1248 if (a != b) return (a > b) ? vv1->len : -vv1->len;
1249 }
1250 return 0;
1251 }
1252
int_from_size(size_t i)1253 MUST_CHECK Obj *int_from_size(size_t i) {
1254 unsigned int j;
1255 Int *v;
1256 if (i < lenof(int_value)) return val_reference(int_value[i]);
1257 v = new_int();
1258 v->data = v->val;
1259 v->val[0] = (digit_t)i;
1260 for (j = 1; j < sizeof i / sizeof *v->data; j++) {
1261 i >>= 4 * sizeof *v->data;
1262 i >>= 4 * sizeof *v->data;
1263 if (i == 0) break;
1264 v->val[j] = (digit_t)i;
1265 }
1266 v->len = (ssize_t)j;
1267 return Obj(v);
1268 }
1269
int_from_uval(uval_t i)1270 MUST_CHECK Obj *int_from_uval(uval_t i) {
1271 return return_int(i, false);
1272 }
1273
int_from_ival(ival_t i)1274 MUST_CHECK Obj *int_from_ival(ival_t i) {
1275 Int *v;
1276 if (i == 0) return val_reference(int_value[0]);
1277 v = new_int();
1278 v->data = v->val;
1279 if (i > 0) {
1280 v->val[0] = (uval_t)i;
1281 v->len = 1;
1282 } else {
1283 v->val[0] = (uval_t)-i;
1284 v->len = -1;
1285 }
1286 return Obj(v);
1287 }
1288
int_from_float(const Float * v1,linepos_t epoint)1289 MUST_CHECK Obj *int_from_float(const Float *v1, linepos_t epoint) {
1290 bool neg;
1291 unsigned int expo;
1292 double frac, f = v1->real;
1293 size_t sz;
1294 digit_t *d;
1295 Int *v;
1296
1297 neg = (f < 0.0);
1298 if (neg) f = -f;
1299
1300 if (f < (double)(~(digit_t)0) + 1.0) return return_int((digit_t)f, neg);
1301
1302 frac = frexp(f, (int *)&expo);
1303 sz = (expo - 1) / SHIFT + 1;
1304
1305 v = new_int();
1306 v->data = d = inew2(v, sz);
1307 if (d == NULL) goto failed2;
1308 v->len = (ssize_t)(neg ? -sz : sz);
1309
1310 frac = ldexp(frac, (int)((expo - 1) % SHIFT + 1));
1311
1312 while ((sz--) != 0) {
1313 digit_t dg = (digit_t)frac;
1314 d[sz] = dg;
1315 frac = ldexp(frac - (double)dg, SHIFT);
1316 }
1317 return Obj(v);
1318 failed2:
1319 val_destroy(Obj(v));
1320 return new_error_mem(epoint);
1321 }
1322
int_from_bytes(const Bytes * v1,linepos_t epoint)1323 MUST_CHECK Obj *int_from_bytes(const Bytes *v1, linepos_t epoint) {
1324 unsigned int bits;
1325 size_t i, j, sz, len1;
1326 digit_t *d, uv;
1327 Int *v;
1328 bool inv;
1329
1330 switch (v1->len) {
1331 case 1: return return_int(v1->data[0], false);
1332 case 0: return val_reference(int_value[0]);
1333 case ~0: return val_reference(minus1_value);
1334 case ~1: return return_int(v1->data[0] + 1U, true);
1335 }
1336
1337 inv = v1->len < 0;
1338 len1 = (size_t)(inv ? -v1->len : v1->len); /* it's - for the additional length */
1339 sz = len1 / sizeof *d;
1340 if ((len1 % sizeof *d) != 0) sz++;
1341
1342 v = new_int();
1343 v->data = d = inew2(v, sz);
1344 if (d == NULL) goto failed2;
1345
1346 uv = 0; bits = 0; j = 0; i = 0;
1347 if (inv) {
1348 uint8_t c = 0xff;
1349 for (;c == 0xff && i < len1 - 1; i++) {
1350 c = v1->data[i];
1351 uv |= (digit_t)((uint8_t)(c + 1)) << bits;
1352 if (bits == SHIFT - 8) {
1353 d[j++] = uv;
1354 bits = uv = 0;
1355 } else bits += 8;
1356 }
1357 for (; i < len1 - 1; i++) {
1358 uv |= (digit_t)v1->data[i] << bits;
1359 if (bits == SHIFT - 8) {
1360 d[j++] = uv;
1361 bits = uv = 0;
1362 } else bits += 8;
1363 }
1364 if (c == 0xff) uv |= 1U << bits;
1365 d[j] = uv;
1366 } else {
1367 for (;i < len1; i++) {
1368 uv |= (digit_t)v1->data[i] << bits;
1369 if (bits == SHIFT - 8) {
1370 d[j++] = uv;
1371 bits = uv = 0;
1372 } else bits += 8;
1373 }
1374 if (bits != 0) d[j] = uv;
1375 }
1376
1377 return normalize(v, sz, inv);
1378 failed2:
1379 val_destroy(Obj(v));
1380 return new_error_mem(epoint);
1381 }
1382
int_from_bits(const Bits * v1,linepos_t epoint)1383 MUST_CHECK Obj *int_from_bits(const Bits *v1, linepos_t epoint) {
1384 bool inv;
1385 size_t i, sz;
1386 digit_t *d;
1387 const bdigit_t *b;
1388 Int *v;
1389
1390 switch (v1->len) {
1391 case 1: return return_int(v1->data[0], false);
1392 case 0: return val_reference(int_value[0]);
1393 case ~0: return val_reference(minus1_value);
1394 }
1395
1396 inv = v1->len < 0;
1397 sz = (size_t)(inv ? -v1->len : v1->len); /* it's - for the additional length */
1398 if (sz == 0 && inv) goto failed; /* overflow */
1399 v = new_int();
1400 v->data = d = inew2(v, sz);
1401 if (d == NULL) goto failed2;
1402
1403 b = v1->data;
1404 if (inv) {
1405 bool c = true;
1406 for (i = 0; c && i < sz - 1; i++) {
1407 c = (d[i] = b[i] + 1) < 1;
1408 }
1409 for (; i < sz - 1; i++) {
1410 d[i] = b[i];
1411 }
1412 d[i] = c ? 1 : 0;
1413 } else memcpy(d, b, sz * sizeof *d);
1414
1415 return normalize(v, sz, inv);
1416 failed2:
1417 val_destroy(Obj(v));
1418 failed:
1419 return new_error_mem(epoint);
1420 }
1421
int_from_str(const Str * v1,linepos_t epoint)1422 MUST_CHECK Obj *int_from_str(const Str *v1, linepos_t epoint) {
1423 struct encoder_s *encoder;
1424 int ch;
1425 Int *v;
1426 digit_t uv;
1427 unsigned int bits;
1428 size_t i, j, sz, osz;
1429 digit_t *d;
1430
1431 if (actual_encoding == NULL) {
1432 if (v1->chars == 1) {
1433 uchar_t ch2 = v1->data[0];
1434 if ((ch2 & 0x80) != 0) utf8in(v1->data, &ch2);
1435 return int_from_uval(ch2);
1436 }
1437 return Obj(new_error((v1->chars == 0) ? ERROR__EMPTY_STRING : ERROR__NOT_ONE_CHAR, epoint));
1438 }
1439
1440 i = v1->len;
1441 if (i == 0) {
1442 return val_reference(int_value[0]);
1443 }
1444
1445 sz = i / sizeof *d;
1446 if ((i % sizeof *d) != 0) sz++;
1447 v = new_int();
1448 v->data = d = inew2(v, sz);
1449 if (d == NULL) goto failed2;
1450
1451 uv = 0; bits = 0; j = 0;
1452 encoder = encode_string_init(v1, epoint);
1453 while ((ch = encode_string(encoder)) != EOF) {
1454 uv |= (digit_t)(ch & 0xff) << bits;
1455 if (bits == SHIFT - 8) {
1456 if (j >= sz) {
1457 if (v->val == d) {
1458 sz = 16 / sizeof *d;
1459 d = (digit_t *)malloc(sz * sizeof *d);
1460 if (d == NULL) goto failed2;
1461 v->data = d;
1462 memcpy(d, v->val, j * sizeof *d);
1463 } else {
1464 sz += 1024 / sizeof *d;
1465 if (/*sz < 1024 / sizeof *d ||*/ sz > SIZE_MAX / sizeof *d) goto failed2; /* overflow */
1466 d = (digit_t *)realloc(d, sz * sizeof *d);
1467 if (d == NULL) goto failed2;
1468 v->data = d;
1469 }
1470 }
1471 d[j++] = uv;
1472 bits = uv = 0;
1473 } else bits += 8;
1474 }
1475 if (bits != 0) {
1476 if (j >= sz) {
1477 sz++;
1478 if (v->val == d) {
1479 d = (digit_t *)malloc(sz * sizeof *d);
1480 if (d == NULL) goto failed2;
1481 v->data = d;
1482 memcpy(d, v->val, j * sizeof *d);
1483 } else {
1484 if (/*sz < 1 ||*/ sz > SIZE_MAX / sizeof *d) goto failed2; /* overflow */
1485 d = (digit_t *)realloc(d, sz * sizeof *d);
1486 if (d == NULL) goto failed2;
1487 v->data = d;
1488 }
1489 }
1490 d[j] = uv;
1491 osz = j + 1;
1492 } else osz = j;
1493
1494 while (osz != 0 && d[osz - 1] == 0) osz--;
1495 if (osz == 0) return zeroint(v);
1496 v->len = (ssize_t)osz;
1497 if (v->val != d) {
1498 if (osz <= lenof(v->val)) return normalize2(v, osz);
1499 if (osz < sz) {
1500 digit_t *d2 = (digit_t *)realloc(d, osz * sizeof *d);
1501 v->data = (d2 != NULL) ? d2 : d;
1502 }
1503 }
1504 return Obj(v);
1505 failed2:
1506 val_destroy(Obj(v));
1507 return new_error_mem(epoint);
1508 }
1509
int_from_decstr(const uint8_t * s,linecpos_t * ln,linecpos_t * ln2)1510 MUST_CHECK Obj *int_from_decstr(const uint8_t *s, linecpos_t *ln, linecpos_t *ln2) {
1511 const uint8_t *end;
1512 linecpos_t i, k;
1513 size_t sz;
1514 digit_t *d, *end2, val;
1515 Int *v;
1516
1517 i = k = val = 0;
1518 if (s[0] != '_') {
1519 for (;;k++) {
1520 uint8_t c = s[k] ^ 0x30;
1521 if (c < 10) {
1522 if (val <= ((~(digit_t)0)-9)/10) val = val * 10 + c;
1523 continue;
1524 }
1525 if (c != ('_' ^ 0x30)) break;
1526 i++;
1527 }
1528 while (k != 0 && s[k - 1] == '_') {
1529 k--;
1530 i--;
1531 }
1532 }
1533 *ln = k;
1534 i = k - i;
1535 *ln2 = i;
1536 if (val <= ((~(digit_t)0)-9)/10) {
1537 if (val >= lenof(int_value)) {
1538 v = new_int();
1539 v->data = v->val;
1540 v->val[0] = val;
1541 v->len = 1;
1542 return Obj(v);
1543 }
1544 return val_reference(int_value[val]);
1545 }
1546 sz = (size_t)((double)i * 0.11073093649624542178511177326072356663644313812255859375) + 1;
1547
1548 v = new_int();
1549 v->data = d = inew2(v, sz);
1550 if (d == NULL) goto failed2;
1551
1552 end = s + k;
1553 end2 = d;
1554 while (s < end) {
1555 digit_t *d2, mul;
1556 int j;
1557 val = 0;
1558 for (j = 0; j < 9 && s < end; s++) {
1559 uint8_t c = *s ^ 0x30;
1560 if (c < 10) {
1561 val = val * 10 + c;
1562 j++;
1563 continue;
1564 }
1565 }
1566 if (j == 9) mul = 1000000000;
1567 else {
1568 mul = 10;
1569 while ((--j) != 0) mul *= 10;
1570 }
1571 d2 = d;
1572 while (d2 < end2) {
1573 twodigits_t a = (twodigits_t)*d2 * mul + val;
1574 *d2++ = (digit_t)a;
1575 val = (digit_t)(a >> SHIFT);
1576 }
1577 if (val != 0) {
1578 if (end2 >= &d[sz]) {
1579 sz++;
1580 if (sz > lenof(v->val)) {
1581 if (d == v->val) {
1582 d = (digit_t *)malloc(sz * sizeof *d);
1583 if (d == NULL) goto failed2;
1584 v->data = d;
1585 memcpy(d, v->val, sizeof v->val);
1586 } else {
1587 if (/*sz < 1 ||*/ sz > SIZE_MAX / sizeof *d) goto failed2; /* overflow */
1588 d = (digit_t *)realloc(d, sz * sizeof *d);
1589 if (d == NULL) goto failed2;
1590 v->data = d;
1591 }
1592 }
1593 end2 = d + sz - 1;
1594 }
1595 *end2++ = val;
1596 }
1597 }
1598
1599 sz = (size_t)(end2 - d);
1600 return normalize(v, sz, false);
1601 failed2:
1602 val_destroy(Obj(v));
1603 return NULL;
1604 }
1605
calc2_int(oper_t op)1606 static MUST_CHECK Obj *calc2_int(oper_t op) {
1607 Int *v1 = Int(op->v1), *v2 = Int(op->v2), *v;
1608 Error *err;
1609 Obj *val;
1610 ival_t shift;
1611 ssize_t cmp;
1612 switch (op->op) {
1613 case O_CMP:
1614 cmp = icmp(op);
1615 return val_reference(cmp < 0 ? minus1_value : int_value[(cmp > 0) ? 1 : 0]);
1616 case O_EQ: return truth_reference(icmp(op) == 0);
1617 case O_NE: return truth_reference(icmp(op) != 0);
1618 case O_MIN:
1619 case O_LT: return truth_reference(icmp(op) < 0);
1620 case O_LE: return truth_reference(icmp(op) <= 0);
1621 case O_MAX:
1622 case O_GT: return truth_reference(icmp(op) > 0);
1623 case O_GE: return truth_reference(icmp(op) >= 0);
1624 case O_ADD:
1625 v = (op->inplace == Obj(v1)) ? ref_int(v1) : new_int();
1626 if (v1->len < 0) {
1627 if (v2->len < 0) {
1628 iadd(v1, v2, v);
1629 v->len = -v->len;
1630 } else isub(v2, v1, v);
1631 } else {
1632 if (v2->len < 0) isub(v1, v2, v);
1633 else iadd(v1, v2, v);
1634 }
1635 return Obj(v);
1636 case O_SUB:
1637 v = (op->inplace == Obj(v1)) ? ref_int(v1) : new_int();
1638 if (v1->len < 0) {
1639 if (v2->len < 0) isub(v1, v2, v);
1640 else iadd(v1, v2, v);
1641 v->len = -v->len;
1642 } else {
1643 if (v2->len < 0) iadd(v1, v2, v);
1644 else isub(v1, v2, v);
1645 }
1646 return Obj(v);
1647 case O_MUL:
1648 v = (op->inplace == Obj(v1)) ? ref_int(v1) : new_int();
1649 if ((v1->len ^ v2->len) < 0) {
1650 imul(v1, v2, v);
1651 v->len = -v->len;
1652 } else imul(v1, v2, v);
1653 return Obj(v);
1654 case O_DIV:
1655 return idivrem(op, true);
1656 case O_MOD:
1657 val = idivrem(op, false);
1658 if (val->obj != INT_OBJ) return val;
1659 v = Int(val);
1660 if (v->len !=0 && (v->len ^ v2->len) < 0) {
1661 Int *vv = new_int();
1662 if (v->len < 0) isub(v2, v, vv);
1663 else isub(v, v2, vv);
1664 val_destroy(Obj(v));
1665 return Obj(vv);
1666 }
1667 return Obj(v);
1668 case O_EXP:
1669 if (v2->len == 1) {
1670 if (v2->data[0] == 2) {
1671 v = (op->inplace == Obj(v1)) ? ref_int(v1) : new_int();
1672 imul(v1, v1, v);
1673 return Obj(v);
1674 }
1675 if (v2->data[0] == 1) {
1676 return val_reference(Obj(v1));
1677 }
1678 } else if (v2->len == 0) {
1679 return val_reference(int_value[1]);
1680 } else if (v2->len < 0) {
1681 Obj *vv1 = float_from_int(v1, op->epoint);
1682 Obj *vv2 = float_from_int(v2, op->epoint2);
1683 op->v1 = vv1;
1684 op->v2 = vv2;
1685 op->inplace = (vv1->refcount == 1) ? vv1 : NULL;
1686 val = vv1->obj->calc2(op);
1687 if (val->obj == ERROR_OBJ) {
1688 error_obj_update(Error(val), vv1, Obj(v1));
1689 error_obj_update(Error(val), vv2, Obj(v2));
1690 }
1691 val_destroy(vv1);
1692 val_destroy(vv2);
1693 return val;
1694 }
1695 return power(op);
1696 case O_LSHIFT:
1697 err = ival(Obj(v2), &shift, 8 * sizeof shift, op->epoint2);
1698 if (err != NULL) return Obj(err);
1699 if (shift == 0) return val_reference(Obj(v1));
1700 return (shift < 0) ? rshift(op, (uval_t)-shift) : lshift(op, (uval_t)shift);
1701 case O_RSHIFT:
1702 err = ival(Obj(v2), &shift, 8 * sizeof shift, op->epoint2);
1703 if (err != NULL) return Obj(err);
1704 if (shift == 0) return val_reference(Obj(v1));
1705 return (shift < 0) ? lshift(op, (uval_t)-shift) : rshift(op, (uval_t)shift);
1706 case O_AND: return and_(op);
1707 case O_OR: return or_(op);
1708 case O_XOR: return xor_(op);
1709 default: break;
1710 }
1711 return obj_oper_error(op);
1712 }
1713
calc2(oper_t op)1714 static MUST_CHECK Obj *calc2(oper_t op) {
1715 Obj *tmp, *ret, *v2 = op->v2;
1716
1717 if (op->op == O_LAND) {
1718 if (diagnostics.strict_bool) err_msg_bool_oper(op);
1719 return val_reference((Int(op->v1)->len != 0) ? v2 : op->v1);
1720 }
1721 if (op->op == O_LOR) {
1722 if (diagnostics.strict_bool) err_msg_bool_oper(op);
1723 return val_reference((Int(op->v1)->len != 0) ? op->v1 : v2);
1724 }
1725 switch (v2->obj->type) {
1726 case T_INT: return calc2_int(op);
1727 case T_BOOL:
1728 if (diagnostics.strict_bool) err_msg_bool_oper(op);
1729 tmp = int_value[v2 == true_value ? 1 : 0];
1730 op->v2 = tmp;
1731 ret = calc2_int(op);
1732 if (ret->obj == ERROR_OBJ) error_obj_update(Error(ret), tmp, v2);
1733 return ret;
1734 case T_BYTES:
1735 tmp = int_from_bytes(Bytes(v2), op->epoint2);
1736 goto conv;
1737 case T_BITS:
1738 tmp = int_from_bits(Bits(v2), op->epoint2);
1739 goto conv;
1740 case T_STR:
1741 tmp = int_from_str(Str(v2), op->epoint2);
1742 conv:
1743 op->v2 = tmp;
1744 if (op->inplace != NULL && op->inplace->refcount != 1) op->inplace = NULL;
1745 ret = calc2(op);
1746 if (ret->obj == ERROR_OBJ) error_obj_update(Error(ret), tmp, v2);
1747 val_destroy(tmp);
1748 return ret;
1749 default:
1750 if (op->op != O_MEMBER && op->op != O_X) {
1751 return v2->obj->rcalc2(op);
1752 }
1753 if (v2 == none_value || v2->obj == ERROR_OBJ) return val_reference(v2);
1754 }
1755 return obj_oper_error(op);
1756 }
1757
rcalc2(oper_t op)1758 static MUST_CHECK Obj *rcalc2(oper_t op) {
1759 Obj *tmp, *v1 = op->v1;
1760 if (v1->obj == BOOL_OBJ) {
1761 if (diagnostics.strict_bool) err_msg_bool_oper(op);
1762 switch (op->op) {
1763 case O_LSHIFT:
1764 case O_RSHIFT: tmp = bits_value[v1 == true_value ? 1 : 0]; break;
1765 default: tmp = int_value[v1 == true_value ? 1 : 0]; break;
1766 }
1767 op->v1 = tmp;
1768 op->inplace = NULL;
1769 return tmp->obj->calc2(op);
1770 }
1771 return obj_oper_error(op);
1772 }
1773
intobj_init(void)1774 void intobj_init(void) {
1775 new_type(&obj, T_INT, "int", sizeof(Int));
1776 obj.convert = convert;
1777 obj.destroy = destroy;
1778 obj.same = same;
1779 obj.truth = truth;
1780 obj.hash = hash;
1781 obj.repr = repr;
1782 obj.ival = ival;
1783 obj.uval = uval;
1784 obj.uval2 = uval;
1785 obj.iaddress = ival;
1786 obj.uaddress = uval;
1787 obj.sign = sign;
1788 obj.function = function;
1789 obj.calc1 = calc1;
1790 obj.calc2 = calc2;
1791 obj.rcalc2 = rcalc2;
1792 }
1793
intobj_names(void)1794 void intobj_names(void) {
1795 new_builtin("int", val_reference(Obj(INT_OBJ)));
1796 }
1797
intobj_destroy(void)1798 void intobj_destroy(void) {
1799 #ifdef DEBUG
1800 if (int_value[0]->refcount != 1) fprintf(stderr, "int[0] %" PRIuSIZE "\n", int_value[0]->refcount - 1);
1801 if (int_value[1]->refcount != 1) fprintf(stderr, "int[1] %" PRIuSIZE "\n", int_value[1]->refcount - 1);
1802 if (minus1_value->refcount != 1) fprintf(stderr, "int[-1] %" PRIuSIZE "\n", minus1_value->refcount - 1);
1803 #endif
1804 }
1805