1 /*
2     $Id: bitsobj.c 2604 2021-04-25 10:47:25Z 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 along
15     with this program; if not, write to the Free Software Foundation, Inc.,
16     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
17 
18 */
19 #include "bitsobj.h"
20 #include <string.h>
21 #include "math.h"
22 #include "eval.h"
23 #include "variables.h"
24 #include "unicode.h"
25 #include "encoding.h"
26 #include "error.h"
27 #include "arguments.h"
28 
29 #include "codeobj.h"
30 #include "boolobj.h"
31 #include "floatobj.h"
32 #include "strobj.h"
33 #include "bytesobj.h"
34 #include "intobj.h"
35 #include "listobj.h"
36 #include "typeobj.h"
37 #include "noneobj.h"
38 #include "errorobj.h"
39 #include "addressobj.h"
40 
41 #define SHIFT (8 * (unsigned int)sizeof(bdigit_t))
42 
43 static Type obj;
44 
45 Type *const BITS_OBJ = &obj;
46 
47 static Bits null_bitsval = { { &obj, 1 }, 0, 0, null_bitsval.u.val, { {0, 0} } };
48 static Bits inv_bitsval = { { &obj, 1 }, ~0, 0, inv_bitsval.u.val, { {0, 0} } };
49 static Bits zero_bitsval = { { &obj, 1 }, 0, 1, zero_bitsval.u.val, { {0, 0} } };
50 static Bits one_bitsval = { { &obj, 1 }, 1, 1, one_bitsval.u.val, { {1, 0} } };
51 static Bits zero_ibitsval = { { &obj, 1 }, ~0, 1, zero_ibitsval.u.val, { {0, 0} } };
52 static Bits one_ibitsval = { { &obj, 1 }, ~1, 1, one_ibitsval.u.val, { {1, 0} } };
53 
54 Obj *const null_bits = &null_bitsval.v;
55 Obj *const inv_bits = &inv_bitsval.v;
56 Obj *const bits_value[2] = { &zero_bitsval.v, &one_bitsval.v };
57 Obj *const ibits_value[2] = { &zero_ibitsval.v, &one_ibitsval.v };
58 
ref_bits(Bits * v1)59 static inline Bits *ref_bits(Bits *v1) {
60     v1->v.refcount++; return v1;
61 }
62 
63 static MUST_CHECK Obj *bits_from_int(const Int *, linepos_t);
64 
bits_from_obj(Obj * v1,linepos_t epoint)65 MUST_CHECK Obj *bits_from_obj(Obj *v1, linepos_t epoint) {
66     Obj *err, *ret;
67     switch (v1->obj->type) {
68     case T_NONE:
69     case T_ERROR:
70     case T_BITS: return val_reference(v1);
71     case T_BOOL: return val_reference(bits_value[v1 == true_value ? 1 : 0]);
72     case T_STR: return bits_from_str(Str(v1), epoint);
73     case T_BYTES: return bits_from_bytes(Bytes(v1), epoint);
74     case T_INT: return bits_from_int(Int(v1), epoint);
75     case T_CODE: return bits_from_code(Code(v1), epoint);
76     case T_ADDRESS: return bits_from_address(Address(v1), epoint);
77     case T_FLOAT:
78          err = int_from_float(Float(v1), epoint);
79          if (err->obj != INT_OBJ) return err;
80          ret = bits_from_int(Int(err), epoint);
81          val_destroy(err);
82          return ret;
83     default: break;
84     }
85     return new_error_conv(v1, BITS_OBJ, epoint);
86 }
87 
convert(oper_t op)88 static MUST_CHECK Obj *convert(oper_t op) {
89     return bits_from_obj(op->v2, op->epoint2);
90 }
91 
bitslen(const Bits * v1)92 static inline size_t bitslen(const Bits *v1) {
93     ssize_t len = v1->len;
94     return (size_t)(len < 0 ? ~len : len);
95 }
96 
bits_destroy(Bits * v1)97 static FAST_CALL NO_INLINE void bits_destroy(Bits *v1) {
98     free(v1->data);
99 }
100 
destroy(Obj * o1)101 static FAST_CALL void destroy(Obj *o1) {
102     Bits *v1 = Bits(o1);
103     if (v1->u.val != v1->data) bits_destroy(v1);
104 }
105 
new_bits2(size_t len)106 static MALLOC Bits *new_bits2(size_t len) {
107     Bits *v = Bits(val_alloc(BITS_OBJ));
108     if (len > lenof(v->u.val)) {
109         v->u.hash = -1;
110         v->data = (len <= SIZE_MAX / sizeof *v->data) ? (bdigit_t *)malloc(len * sizeof *v->data) : NULL;
111         if (v->data == NULL) {
112             val_destroy(Obj(v));
113             v = NULL;
114         }
115     } else {
116         v->data = v->u.val;
117     }
118     return v;
119 }
120 
convert2(oper_t op)121 static MUST_CHECK Obj *convert2(oper_t op) {
122     Funcargs *v2 = Funcargs(op->v2);
123     argcount_t args = v2->len;
124     Error *err;
125     ival_t ival;
126     uval_t len2, blen2;
127     size_t blen;
128     Obj *v;
129     Bits *bits, *bits2;
130     unsigned int m;
131     bool inplace, bytes;
132     if (args != 2) {
133         return new_error_argnum(args, 1, 2, op->epoint2);
134     }
135     v = v2->val[1].val;
136     err = v->obj->ival(v, &ival, 8 * sizeof ival, &v2->val[1].epoint);
137     if (err != 0) return Obj(err);
138     v = v2->val[0].val;
139     inplace = (v->obj == BITS_OBJ);
140     bytes = (v->obj == BYTES_OBJ || v->obj == STR_OBJ);
141     if (!inplace) {
142         v = bits_from_obj(v, op->epoint2);
143         if (v->obj != BITS_OBJ) return v;
144     }
145     bits = Bits(v);
146     if (ival >= 0) {
147         len2 = (uval_t)ival;
148         if (!inplace && !bytes && bits->len < 0) {
149             val_destroy(Obj(bits));
150             err = new_error(ERROR______NOT_UVAL, &v2->val[0].epoint);
151             err->u.intconv.val = val_reference(v2->val[0].val);
152             return Obj(err);
153         }
154     } else {
155         len2 = (uval_t)-(1 + ival);
156     }
157     blen2 = len2 / SHIFT + 1;
158     m = len2 % SHIFT;
159     if (ival < 0) len2++;
160     blen = bitslen(bits);
161     if (((inplace || bytes) && bits->bits > len2) || blen > blen2 || (blen == blen2 && (bits->data[blen2 - 1] >> m) != 0)) {
162         if (!inplace) val_destroy(Obj(bits));
163         err = new_error(ival < 0 ? ERROR_____CANT_IVAL : ERROR_____CANT_UVAL, &v2->val[0].epoint);
164         err->u.intconv.bits = len2;
165         err->u.intconv.val = val_reference(v2->val[0].val);
166         return Obj(err);
167     }
168     if (bits->v.refcount == 1) {
169         bits->bits = len2;
170     }
171     if (bits->bits == len2) {
172         return inplace ? val_reference(Obj(bits)) : Obj(bits);
173     }
174     bits2 = new_bits2(blen);
175     bits2->len = bits->len;
176     bits2->bits = len2;
177     if (blen != 0) memcpy(bits2->data, bits->data, blen * sizeof *bits2->data); else bits2->u.val[0] = 0;
178     if (!inplace) val_destroy(Obj(bits));
179     return Obj(bits2);
180 }
181 
invert(const Bits * v1,linepos_t epoint)182 static MUST_CHECK Obj *invert(const Bits *v1, linepos_t epoint) {
183     size_t sz = bitslen(v1);
184     Bits *v = new_bits2(sz);
185     if (v == NULL) return new_error_mem(epoint);
186     v->bits = v1->bits;
187     v->len = ~v1->len;
188     if (sz != 0) {
189         memcpy(v->data, v1->data, sz * sizeof *v->data);
190     } else {
191         v->data[0] = 0;
192     }
193     return Obj(v);
194 }
195 
normalize2(Bits * v,size_t sz)196 static FAST_CALL NO_INLINE Obj *normalize2(Bits *v, size_t sz) {
197     if (sz != 0) {
198         do {
199             sz--;
200             v->u.val[sz] = v->data[sz];
201         } while (sz != 0);
202     } else {
203         v->u.val[0] = 0;
204     }
205     free(v->data);
206     v->data = v->u.val;
207     return Obj(v);
208 }
209 
normalize(Bits * v,size_t sz,bool neg)210 static FAST_CALL MUST_CHECK Obj *normalize(Bits *v, size_t sz, bool neg) {
211     bdigit_t *d = v->data;
212     while (sz != 0 && d[sz - 1] == 0) sz--;
213     /*if (sz >= SSIZE_MAX) err_msg_out_of_memory();*/ /* overflow */
214     v->len = (ssize_t)(neg ? ~sz : sz);
215     if (v->u.val != d && sz <= lenof(v->u.val)) {
216         return normalize2(v, sz);
217     }
218     return Obj(v);
219 }
220 
negate(Bits * v1,linepos_t epoint)221 static MUST_CHECK Obj *negate(Bits *v1, linepos_t epoint) {
222     size_t i, sz = bitslen(v1);
223     Bits *v;
224     bool ext = false;
225     if (v1->len == 0) return val_reference(Obj(v1));
226     if (v1->len < 0) {
227         size_t bs = (v1->bits % SHIFT);
228         ext = true;
229         for (i = 0; i < sz; i++) {
230             if (v1->data[i] != (bdigit_t)~0) {
231                 ext = false;
232                 break;
233             }
234         }
235         if (i == v1->bits / SHIFT) {
236             if (bs == 0) return NULL;
237             if (v1->data[i] == ~((~(v1->data[i] >> bs)) << bs)) return NULL;
238         }
239         v = new_bits2(ext ? sz + 1 : sz);
240         if (v == NULL) goto failed;
241         if (ext) {
242             for (i = 0; i < sz; i++) v->data[i] = 0;
243             v->data[i] = 1;
244         } else {
245             for (i = 0; i < sz; i++) {
246                 if (v1->data[i] != (bdigit_t)~0) {
247                     v->data[i] = v1->data[i] + 1;
248                     i++;
249                     break;
250                 }
251                 v->data[i] = 0;
252             }
253         }
254     } else {
255         v = new_bits2(sz);
256         if (v == NULL) goto failed;
257         for (i = 0; i < sz; i++) {
258             if (v1->data[i] != 0) {
259                 v->data[i] = v1->data[i] - 1;
260                 i++;
261                 break;
262             }
263             v->data[i] = ~(bdigit_t)0;
264         }
265     }
266     for (; i < sz; i++) v->data[i] = v1->data[i];
267     v->bits = v1->bits;
268     return normalize(v, ext ? sz + 1 : sz, v1->len > 0);
269 failed:
270     return new_error_mem(epoint);
271 }
272 
return_bits(bdigit_t c,unsigned int blen)273 static MALLOC Obj *return_bits(bdigit_t c, unsigned int blen) {
274     Bits *vv = Bits(val_alloc(BITS_OBJ));
275     vv->data = vv->u.val;
276     vv->u.val[0] = c;
277     vv->len = (c != 0) ? 1 : 0;
278     vv->bits = blen;
279     return Obj(vv);
280 }
281 
bits_same(const Bits * v1,const Bits * v2)282 static FAST_CALL NO_INLINE bool bits_same(const Bits *v1, const Bits *v2) {
283     return memcmp(v1->data, v2->data, bitslen(v1) * sizeof *v1->data) == 0;
284 }
285 
same(const Obj * o1,const Obj * o2)286 static FAST_CALL bool same(const Obj *o1, const Obj *o2) {
287     const Bits *v1 = Bits(o1), *v2 = Bits(o2);
288     if (o1->obj != o2->obj || v1->len != v2->len || v1->bits != v2->bits) return false;
289     switch (v1->len) {
290     case 0: return true;
291     case -1:
292     case 1: return v1->data[0] == v2->data[0];
293     default: return bits_same(v1, v2);
294     }
295 }
296 
truth(Obj * o1,Truth_types type,linepos_t epoint)297 static MUST_CHECK Obj *truth(Obj *o1, Truth_types type, linepos_t epoint) {
298     const Bits *v1 = Bits(o1);
299     size_t i, sz, sz2;
300     bdigit_t b, inv;
301     switch (type) {
302     case TRUTH_ALL:
303         if (v1->bits == 0) return ref_true();
304         sz = bitslen(v1);
305         sz2 = v1->bits / SHIFT;
306         if (sz2 > sz) sz2 = sz;
307         inv = (v1->len >= 0) ? ~(bdigit_t)0 : 0;
308         for (i = 0; i < sz2; i++) {
309             if (v1->data[i] != inv) return ref_false();
310         }
311         b = (i >= sz) ? 0 : v1->data[i];
312         b ^= inv;
313         b <<= SHIFT - v1->bits % SHIFT;
314         return truth_reference(b == 0);
315     case TRUTH_ANY:
316         if (v1->bits == 0) return ref_false();
317         /* fall through */
318     default:
319         return truth_reference(v1->len != 0);
320     }
321     return DEFAULT_OBJ->truth(o1, type, epoint);
322 }
323 
repr(Obj * o1,linepos_t UNUSED (epoint),size_t maxsize)324 static MUST_CHECK Obj *repr(Obj *o1, linepos_t UNUSED(epoint), size_t maxsize) {
325     const Bits *v1 = Bits(o1);
326     size_t len, i, len2, sz;
327     uint8_t *s;
328     bool inv;
329     Str *v;
330 
331     len2 = v1->bits;
332     sz = bitslen(v1);
333     inv = (v1->len < 0);
334     len = inv ? 2 : 1;
335     if ((len2 & 3) != 0) {
336         len += len2;
337         if (len < len2) return NULL; /* overflow */
338         if (len > maxsize) return NULL;
339         v = new_str2(len);
340         if (v == NULL) return NULL;
341         v->chars = len;
342         s = v->data;
343 
344         if (inv) *s++ = '~';
345         *s++ = '%';
346         for (i = len2; (i--) != 0;) {
347             size_t j = i / SHIFT;
348             *s++ = (j < sz && (v1->data[j] & (1U << (i % SHIFT))) != 0) ? '1' : '0';
349         }
350         return Obj(v);
351     }
352     len2 /= 4;
353     len += len2;
354     if (len < len2) return NULL; /* overflow */
355     if (len > maxsize) return NULL;
356     v = new_str2(len);
357     if (v == NULL) return NULL;
358     v->chars = len;
359     s = v->data;
360 
361     if (inv) *s++ = '~';
362     *s++ = '$';
363     for (i = len2; (i--) != 0;) {
364         size_t j = i / (2 * sizeof *v1->data);
365         *s++ = (j >= sz) ? 0x30 : (uint8_t)"0123456789abcdef"[(v1->data[j] >> ((i & (2 * (sizeof *v1->data) - 1)) * 4)) & 15];
366     }
367     return Obj(v);
368 }
369 
hash(Obj * o1,int * hs,linepos_t UNUSED (epoint))370 static MUST_CHECK Obj *hash(Obj *o1, int *hs, linepos_t UNUSED(epoint)) {
371     Bits *v1 = Bits(o1);
372     size_t l;
373     unsigned int h;
374 
375     switch (v1->len) {
376     case ~1: *hs = (v1->bits ^ ~v1->data[0]) & ((~0U) >> 1); return NULL;
377     case ~0: *hs = (v1->bits ^ ~0U) & ((~0U) >> 1); return NULL;
378     case 0: *hs = v1->bits & ((~0U) >> 1); return NULL;
379     case 1: *hs = (v1->bits ^ v1->data[0]) & ((~0U) >> 1); return NULL;
380     default: break;
381     }
382     if (v1->data != v1->u.val && v1->u.hash >= 0) {
383         *hs = v1->u.hash;
384         return NULL;
385     }
386     if (v1->len < 0) {
387         l = (size_t)~v1->len;
388         h = ~0U;
389         while ((l--) != 0) {
390             h -= v1->data[l];
391         }
392     } else {
393         l = (size_t)v1->len;
394         h = 0;
395         while ((l--) != 0) {
396             h += v1->data[l];
397         }
398     }
399     h ^= (unsigned int)v1->bits;
400     h &= ((~0U) >> 1);
401     if (v1->data != v1->u.val) v1->u.hash = (int)h;
402     *hs = (int)h;
403     return NULL;
404 }
405 
uvalx(Obj * o1,uval_t * uv,unsigned int bits)406 static bool uvalx(Obj *o1, uval_t *uv, unsigned int bits) {
407     Bits *v1 = Bits(o1);
408     switch (v1->len) {
409     case ~1:
410         *uv = ~v1->data[0];
411         if (v1->bits > bits) break;
412         return true;
413     case ~0:
414         *uv = ~(uval_t)0;
415         if (v1->bits > bits) break;
416         return true;
417     case 0:
418         *uv = 0;
419         return true;
420     case 1:
421         *uv = v1->data[0];
422         if (bits < SHIFT && (*uv >> bits) != 0) break;
423         return true;
424     default:
425         break;
426     }
427     return false;
428 }
429 
ival(Obj * o1,ival_t * iv,unsigned int bits,linepos_t epoint)430 static MUST_CHECK Error *ival(Obj *o1, ival_t *iv, unsigned int bits, linepos_t epoint) {
431     Error *v;
432     if (uvalx(o1, (uval_t *)iv, bits)) return NULL;
433     v = new_error(ERROR_____CANT_IVAL, epoint);
434     v->u.intconv.bits = bits;
435     v->u.intconv.val = val_reference(o1);
436     return v;
437 }
438 
uval(Obj * o1,uval_t * uv,unsigned int bits,linepos_t epoint)439 static MUST_CHECK Error *uval(Obj *o1, uval_t *uv, unsigned int bits, linepos_t epoint) {
440     Error *v;
441     if (uvalx(o1, uv, bits)) return NULL;
442     v = new_error(ERROR_____CANT_UVAL, epoint);
443     v->u.intconv.bits = bits;
444     v->u.intconv.val = val_reference(o1);
445     return v;
446 }
447 
uval2(Obj * o1,uval_t * uv,unsigned int bits,linepos_t epoint)448 static MUST_CHECK Error *uval2(Obj *o1, uval_t *uv, unsigned int bits, linepos_t epoint) {
449     if (Bits(o1)->len < 0) {
450         Error *v = new_error(ERROR______NOT_UVAL, epoint);
451         v->u.intconv.val = val_reference(o1);
452         return v;
453     }
454     return uval(o1, uv, bits, epoint);
455 }
456 
float_from_bits(const Bits * v1,linepos_t epoint)457 MUST_CHECK Obj *float_from_bits(const Bits *v1, linepos_t epoint) {
458     double d;
459     size_t i, len1;
460     switch (v1->len) {
461     case ~1: d = -1.0 - v1->data[0]; break;
462     case ~0: d = -1.0; break;
463     case 0: d = 0.0; break;
464     case 1: d = v1->data[0]; break;
465     default:
466         d = ((v1->len < 0) ? 1.0 : 0.0) + v1->data[0];
467         len1 = bitslen(v1);
468         for (i = 1; i < len1; i++) {
469             d += ldexp(v1->data[i], (int)(i * SHIFT));
470         }
471         if (v1->len < 0) d = -d;
472         return float_from_double(d, epoint);
473     }
474     return new_float(d);
475 }
476 
sign(Obj * o1,linepos_t UNUSED (epoint))477 static MUST_CHECK Obj *sign(Obj *o1, linepos_t UNUSED(epoint)) {
478     Bits *v1 = Bits(o1);
479     ssize_t len = v1->len;
480     return val_reference(len < 0 ? minus1_value : int_value[(len > 0) ? 1 : 0]);
481 }
482 
function(oper_t op)483 static MUST_CHECK Obj *function(oper_t op) {
484     Bits *v1 = Bits(op->v2);
485     Obj *tmp, *ret;
486     op->v2 = tmp = int_from_bits(v1, op->epoint2);
487     op->inplace = tmp->refcount == 1 ? tmp : NULL;
488     ret = tmp->obj->function(op);
489     val_destroy(tmp);
490     return ret;
491 }
492 
len(oper_t op)493 static MUST_CHECK Obj *len(oper_t op) {
494     Bits *v1 = Bits(op->v2);
495     return int_from_size(v1->bits);
496 }
497 
bits_from_uval(uval_t i,unsigned int bits)498 MUST_CHECK Obj *bits_from_uval(uval_t i, unsigned int bits) {
499     return return_bits(i, bits);
500 }
501 
bits_from_hexstr(const uint8_t * s,linecpos_t * ln)502 MUST_CHECK Obj *bits_from_hexstr(const uint8_t *s, linecpos_t *ln) {
503     linecpos_t i, j, k;
504     int bits;
505     bdigit_t *d, uv;
506     Bits *v;
507 
508     i = k = 0; uv = 0;
509     if (s[0] != '_') {
510         for (;;k++) {
511             uint8_t c2, c = s[k] ^ 0x30;
512             if (c < 10) {
513                 uv = (uv << 4) + c;
514                 continue;
515             }
516             c2 = (uint8_t)((c | 0x20) - 0x71);
517             if (c2 < 6) {
518                 uv = (uv << 4) + c2 + 10;
519                 continue;
520             }
521             if (c != ('_' ^ 0x30)) break;
522             i++;
523         }
524         while (k != 0 && s[k - 1] == '_') {
525             k--;
526             i--;
527         }
528     }
529     *ln = k;
530     i = k - i;
531 
532     if (i <= 2 * sizeof *d) {
533         return (i == 0) ? val_reference(null_bits) : return_bits(uv, (unsigned int)i * 4);
534     }
535 
536     if ((size_t)i + 0 > SIZE_MAX / 4) return NULL; /* overflow */
537 
538     v = new_bits2(i / (2 * sizeof *d) + ((i % (2 * sizeof *d)) != 0 ? 1 :0));
539     if (v == NULL) return NULL;
540     v->bits = i * 4;
541     d = v->data;
542 
543     uv = 0; j = 0; bits = 0;
544     while ((k--) != 0) {
545         bdigit_t c = s[k] ^ 0x30;
546         if (c < 10) uv += c << bits;
547         else if (c == ('_' ^ 0x30)) continue;
548         else uv += ((c & 7) + 9) << bits;
549         if (bits == SHIFT - 4) {
550             d[j++] = uv;
551             bits = 0; uv = 0;
552         } else bits += 4;
553     }
554     if (uv != 0) d[j++] = uv;
555 
556     return normalize(v, j, false);
557 }
558 
bits_from_binstr(const uint8_t * s,linecpos_t * ln)559 MUST_CHECK Obj *bits_from_binstr(const uint8_t *s, linecpos_t *ln) {
560     linecpos_t i, j, k;
561     bdigit_t bits;
562     bdigit_t *d, uv;
563     Bits *v;
564 
565     i = k = 0; uv = 0;
566     if (s[0] != '_') {
567         for (;;k++) {
568             uint8_t c = s[k] ^ 0x30;
569             if (c < 2) {
570                 uv = (uv << 1) + c;
571                 continue;
572             }
573             if (c != ('_' ^ 0x30)) break;
574             i++;
575         }
576         while (k != 0 && s[k - 1] == '_') {
577             k--;
578             i--;
579         }
580     }
581     *ln = k;
582     i = k - i;
583 
584     if (i <= 8 * sizeof *d) {
585         return (i == 0) ? val_reference(null_bits) : return_bits(uv, (unsigned int)i);
586     }
587 
588     v = new_bits2(i / SHIFT + ((i % SHIFT) != 0 ? 1 : 0));
589     if (v == NULL) return NULL;
590     v->bits = i;
591     d = v->data;
592 
593     uv = 0; j = 0; bits = 1;
594     while ((k--) != 0) {
595         if (s[k] == 0x31) uv += bits;
596         else if (s[k] == '_') continue;
597         bits <<= 1;
598         if (bits == 0) {
599             d[j++] = uv;
600             uv = 0;
601             bits = 1;
602         }
603     }
604     if (uv != 0) d[j++] = uv;
605 
606     return normalize(v, j, false);
607 }
608 
bits_from_str(const Str * v1,linepos_t epoint)609 MUST_CHECK Obj *bits_from_str(const Str *v1, linepos_t epoint) {
610     struct encoder_s *encoder;
611     int ch;
612     Bits *v;
613     unsigned int bits;
614     size_t j, sz, osz;
615     bdigit_t *d, uv;
616 
617     if (actual_encoding == NULL) {
618         if (v1->chars == 1) {
619             uchar_t ch2 = v1->data[0];
620             if ((ch2 & 0x80) != 0) utf8in(v1->data, &ch2);
621             return return_bits(ch2 & 0xffffff, 24);
622         }
623         return Obj(new_error((v1->chars == 0) ? ERROR__EMPTY_STRING : ERROR__NOT_ONE_CHAR, epoint));
624     }
625 
626     if (v1->len == 0) {
627         return val_reference(null_bits);
628     }
629 
630     if (v1->len <= sizeof v->u.val) sz = lenof(v->u.val);
631     else {
632         sz = v1->len / sizeof *d;
633         if ((v1->len % sizeof *d) != 0) sz++;
634     }
635     v = new_bits2(sz);
636     if (v == NULL) goto failed;
637     d = v->data;
638 
639     uv = 0; bits = 0; j = 0;
640     encoder = encode_string_init(v1, epoint);
641     while ((ch = encode_string(encoder)) != EOF) {
642         uv |= (bdigit_t)(ch & 0xff) << bits;
643         if (bits == SHIFT - 8) {
644             if (j >= sz) {
645                 if (v->u.val == d) {
646                     sz = 16 / sizeof *d;
647                     d = (bdigit_t *)malloc(sz * sizeof *d);
648                     if (d == NULL) goto failed2;
649                     v->data = d;
650                     memcpy(d, v->u.val, j * sizeof *d);
651                     v->u.hash = -1;
652                 } else {
653                     sz += 1024 / sizeof *d;
654                     if (/*sz < 1024 / sizeof *d ||*/ sz > SIZE_MAX / sizeof *d) goto failed2; /* overflow */
655                     d = (bdigit_t *)realloc(d, sz * sizeof *d);
656                     if (d == NULL) goto failed2;
657                     v->data = d;
658                 }
659             }
660             d[j++] = uv;
661             bits = uv = 0;
662         } else bits += 8;
663     }
664     if (bits != 0) {
665         if (j >= sz) {
666             sz++;
667             if (v->u.val == d) {
668                 d = (bdigit_t *)malloc(sz * sizeof *d);
669                 if (d == NULL) goto failed2;
670                 v->data = d;
671                 memcpy(d, v->u.val, j * sizeof *d);
672                 v->u.hash = -1;
673             } else {
674                 if (/*sz < 1 ||*/ sz > SIZE_MAX / sizeof *d) goto failed2; /* overflow */
675                 d = (bdigit_t *)realloc(d, sz * sizeof *d);
676                 if (d == NULL) goto failed2;
677                 v->data = d;
678             }
679         }
680         d[j] = uv;
681         osz = j + 1;
682     } else osz = j;
683 
684     while (osz != 0 && d[osz - 1] == 0) osz--;
685     if (v->u.val != d) {
686         if (osz <= lenof(v->u.val)) {
687             if (osz != 0) {
688                 memcpy(v->u.val, d, osz * sizeof *d);
689             } else {
690                 v->u.val[0] = 0;
691             }
692             free(d);
693             v->data = v->u.val;
694         } else if (osz < sz) {
695             bdigit_t *d2 = (bdigit_t *)realloc(d, osz * sizeof *d);
696             v->data = (d2 != NULL) ? d2 : d;
697         }
698     }
699     v->len = (ssize_t)osz;
700     v->bits = j * SHIFT + bits;
701     if (/*v->bits < bits ||*/ j > SIZE_MAX / SHIFT /*|| osz > SSIZE_MAX*/) goto failed2; /* overflow */
702     return Obj(v);
703 failed2:
704     val_destroy(Obj(v));
705 failed:
706     return new_error_mem(epoint);
707 }
708 
bits_from_bytes(const Bytes * v1,linepos_t epoint)709 MUST_CHECK Obj *bits_from_bytes(const Bytes *v1, linepos_t epoint) {
710     int bits;
711     size_t i, j, sz, len1;
712     bdigit_t *d, uv;
713     Bits *v;
714     bool inv = (v1->len < 0);
715 
716     len1 = (size_t)(inv ? ~v1->len : v1->len);
717     if (len1 == 0) {
718         return val_reference(inv ? inv_bits : null_bits);
719     }
720 
721     if (len1 > SIZE_MAX / 8) goto failed; /* overflow */
722 
723     sz = len1 / sizeof *d;
724     if ((len1 % sizeof *d) != 0) sz++;
725     v = new_bits2(sz);
726     if (v == NULL) goto failed;
727     v->bits = len1 * 8;
728     d = v->data;
729 
730     uv = 0; j = 0; i = 0; bits = 0;
731     while (len1 > i) {
732         uv |= (bdigit_t)v1->data[i++] << bits;
733         if (bits == SHIFT - 8) {
734             d[j++] = uv;
735             bits = 0; uv = 0;
736         } else bits += 8;
737     }
738     if (bits != 0) d[j] = uv;
739 
740     return normalize(v, sz, inv);
741 failed:
742     return new_error_mem(epoint);
743 }
744 
bits_from_int(const Int * v1,linepos_t epoint)745 static MUST_CHECK Obj *bits_from_int(const Int *v1, linepos_t epoint) {
746     bool inv;
747     size_t i, sz, bits;
748     bdigit_t *d, d2;
749     const digit_t *b;
750     Bits *v;
751 
752     if (v1->len == 0) return val_reference(null_bits);
753     if (v1->len == -1 && v1->data[0] == 1) return val_reference(inv_bits);
754 
755     inv = (v1->len < 0);
756     sz = (size_t)(inv ? -v1->len : v1->len);
757     v = new_bits2(sz);
758     if (v == NULL) return new_error_mem(epoint);
759     d = v->data;
760 
761     b = v1->data;
762     if (inv) {
763         digit_t c = 0;
764         for (i = 0; c == 0 && i < sz; i++) {
765             d[i] = (c = b[i]) - 1;
766         }
767         for (; i < sz; i++) {
768             d[i] = b[i];
769         }
770     } else memcpy(d, b, sz * sizeof *d);
771 
772     d2 = d[sz - 1];
773     for (bits = 0; d2 != 0; bits++) d2 >>= 1;
774 
775     v->bits = (sz - 1) * SHIFT + bits;
776 
777     return normalize(v, sz, inv);
778 }
779 
bits_calc1(Oper_types op,unsigned int val)780 MUST_CHECK Obj *bits_calc1(Oper_types op, unsigned int val) {
781     switch (op) {
782     case O_BANK: val >>= 8; /* fall through */
783     case O_HIGHER: val >>= 8; /* fall through */
784     case O_LOWER:
785     default: return return_bits((uint8_t)val, 8);
786     case O_BSWORD: val = (uint16_t)val | (val << 16); /* fall through */
787     case O_HWORD: val >>= 8; /* fall through */
788     case O_WORD: return return_bits((uint16_t)val, 16);
789     }
790 }
791 
icmp(oper_t op)792 static ssize_t icmp(oper_t op) {
793     const Bits *vv1 = Bits(op->v1), *vv2 = Bits(op->v2);
794     ssize_t i;
795     size_t j;
796     bdigit_t a, b;
797     i = vv1->len - vv2->len;
798     if (i != 0) return i;
799     j = bitslen(vv1);
800     while (j != 0) {
801         j--;
802         a = vv1->data[j]; b = vv2->data[j];
803         if (a != b) return (a > b) ? vv1->len : -vv1->len;
804     }
805     return 0;
806 }
807 
ldigit(const Bits * v1)808 static inline unsigned int ldigit(const Bits *v1) {
809     ssize_t ln = v1->len;
810     if (ln > 0) return v1->data[0];
811     if (ln == 0) return 0;
812     ln = ~ln;
813     if (ln == 0) return ~(bdigit_t)0;
814     return ~v1->data[0];
815 }
816 
calc1(oper_t op)817 static MUST_CHECK Obj *calc1(oper_t op) {
818     Bits *v1 = Bits(op->v1);
819     Obj *tmp, *v;
820     switch (op->op) {
821     case O_BANK:
822     case O_HIGHER:
823     case O_LOWER:
824     case O_HWORD:
825     case O_WORD:
826     case O_BSWORD:
827         return bits_calc1(op->op, ldigit(v1));
828     case O_INV:
829         if (op->inplace != Obj(v1)) return invert(v1, op->epoint3);
830         v1->len = ~v1->len;
831         if (v1->data != v1->u.val) v1->u.hash = -1;
832         return val_reference(Obj(v1));
833     case O_POS: return val_reference(Obj(v1));
834     case O_NEG:
835         v = negate(v1, op->epoint3);
836         if (v != NULL) return v;
837         /* fall through */
838     case O_STRING:
839         tmp = int_from_bits(v1, op->epoint);
840         op->v1 = tmp;
841         op->inplace = (tmp->refcount == 1) ? tmp : NULL;
842         v = tmp->obj->calc1(op);
843         val_destroy(tmp);
844         return v;
845     case O_LNOT:
846         if (diagnostics.strict_bool) err_msg_bool_oper(op);
847         return truth_reference(v1->len == 0);
848     default:
849         break;
850     }
851     return obj_oper_error(op);
852 }
853 
binary(oper_t op)854 static inline MUST_CHECK Obj *binary(oper_t op) {
855     Bits *vv1 = Bits(op->v1), *vv2 = Bits(op->v2);
856     size_t i, len1, len2, sz;
857     bool neg;
858     const bdigit_t *v1, *v2;
859     bdigit_t *v;
860     Bits *vv;
861     len1 = bitslen(vv1);
862     len2 = bitslen(vv2);
863 
864     if (len1 < len2) {
865         Bits *tmp = vv1; vv1 = vv2; vv2 = tmp;
866         sz = len1; len1 = len2; len2 = sz;
867     }
868 
869     switch (op->op) {
870     case O_AND:
871         sz = vv2->len < 0 ? len1 : len2;
872         break;
873     case O_OR:
874         sz = vv2->len < 0 ? len2 : len1;
875         break;
876     default:
877         sz = len1;
878         break;
879     }
880     if (op->inplace == Obj(vv1)) {
881         vv = ref_bits(vv1);
882         if (vv->data != vv->u.val) vv->u.hash = -1;
883     } else if (op->inplace == Obj(vv2) && sz <= len2) {
884         vv = ref_bits(vv2);
885         if (vv->data != vv->u.val) vv->u.hash = -1;
886     } else {
887         vv = new_bits2(sz);
888         if (vv == NULL) return new_error_mem(op->epoint3);
889         if (sz == 0) vv->data[0] = 0;
890     }
891     v = vv->data;
892     v1 = vv1->data; v2 = vv2->data;
893 
894     i = 0;
895     switch (op->op) {
896     case O_AND:
897         if (vv1->bits < vv2->bits) {
898             vv->bits = (vv1->len < 0) ? vv2->bits : vv1->bits;
899         } else {
900             vv->bits = (vv2->len < 0) ? vv1->bits : vv2->bits;
901         }
902         if (vv1->len < 0) {
903             if (vv2->len < 0) {
904                 neg = true;
905                 for (; i < len2; i++) v[i] = v1[i] | v2[i];
906             } else {
907                 neg = false;
908                 for (; i < len2; i++) v[i] = ~v1[i] & v2[i];
909             }
910         } else {
911             neg = false;
912             if (vv2->len < 0) {
913                 for (; i < len2; i++) v[i] = v1[i] & ~v2[i];
914             } else {
915                 for (; i < len2; i++) v[i] = v1[i] & v2[i];
916             }
917         }
918         break;
919     case O_OR:
920         if (vv1->bits < vv2->bits) {
921             vv->bits = (vv1->len < 0) ? vv1->bits : vv2->bits;
922         } else {
923             vv->bits = (vv2->len < 0) ? vv2->bits : vv1->bits;
924         }
925         if (vv1->len < 0) {
926             neg = true;
927             if (vv2->len < 0) {
928                 for (; i < len2; i++) v[i] = v1[i] & v2[i];
929             } else {
930                 for (; i < len2; i++) v[i] = v1[i] & ~v2[i];
931             }
932         } else {
933             if (vv2->len < 0) {
934                 neg = true;
935                 for (; i < len2; i++) v[i] = ~v1[i] & v2[i];
936             } else {
937                 neg = false;
938                 for (; i < len2; i++) v[i] = v1[i] | v2[i];
939             }
940         }
941         break;
942     default:
943         vv->bits = vv2->bits > vv1->bits ? vv2->bits : vv1->bits;
944         neg = (vv1->len < 0) != (vv2->len < 0);
945         for (; i < len2; i++) v[i] = v1[i] ^ v2[i];
946         break;
947     }
948     for (; i < sz; i++) v[i] = v1[i];
949     return normalize(vv, i, neg);
950 }
951 
concat(oper_t op)952 static inline MUST_CHECK Obj *concat(oper_t op) {
953     Bits *vv1 = Bits(op->v1), *vv2 = Bits(op->v2);
954     size_t blen;
955     size_t sz, bits, i, j, rbits, l;
956     bdigit_t *v1, *v, uv;
957     bdigit_t inv;
958     Bits *vv;
959 
960     if (vv1->bits == 0) {
961         return Obj(ref_bits(vv2));
962     }
963     if (vv2->bits == 0) {
964         return Obj(ref_bits(vv1));
965     }
966     blen = vv1->bits + vv2->bits;
967     if (blen < vv2->bits) goto failed; /* overflow */
968     sz = blen / SHIFT;
969     if ((blen % SHIFT) != 0) sz++;
970     i = vv2->bits / SHIFT + bitslen(vv1);
971     if ((vv2->bits % SHIFT) != 0) i++;
972     if (i < sz) sz = i;
973     vv = new_bits2(sz);
974     if (vv == NULL) goto failed;
975     v = vv->data;
976     inv = ((vv2->len ^ vv1->len) < 0) ? ~(bdigit_t)0 : 0;
977 
978     v1 = vv2->data;
979     rbits = vv2->bits / SHIFT;
980     bits = vv2->bits & (SHIFT - 1);
981     l = bitslen(vv2);
982     for (i = 0; i < rbits && i < l; i++) v[i] = v1[i] ^ inv;
983     for (; i < rbits; i++) v[i] = inv;
984     if (i < l) uv = v1[i] ^ inv; else uv = inv;
985     if (inv != 0) uv &= (1U << bits) - 1;
986 
987     v1 = vv1->data;
988 
989     l = bitslen(vv1);
990     if (bits != 0) {
991         for (j = 0; j < l; j++) {
992             v[i++] = uv | (v1[j] << bits);
993             uv = v1[j] >> (SHIFT - bits);
994         }
995         if (i < sz) v[i++] = uv;
996     } else {
997         for (j = 0; j < l; j++) v[i++] = v1[j];
998     }
999 
1000     vv->bits = blen;
1001     return normalize(vv, i, (vv1->len < 0));
1002 failed:
1003     return new_error_mem(op->epoint3);
1004 }
1005 
lshift(oper_t op,uval_t s)1006 static MUST_CHECK Obj *lshift(oper_t op, uval_t s) {
1007     Bits *vv1 = Bits(op->v1);
1008     size_t i, sz, bits, len1;
1009     unsigned int bit, word;
1010     bdigit_t *v1, *v, *v2;
1011     Bits *vv;
1012 
1013     sz = word = s / SHIFT;
1014     bit = s % SHIFT;
1015     if (bit != 0) sz++;
1016     bits = vv1->bits + s;
1017     if (bits < s) goto failed; /* overflow */
1018     len1 = bitslen(vv1);
1019     sz += len1;
1020     if (sz < len1) goto failed; /* overflow */
1021     if (op->inplace == Obj(vv1) && sz <= lenof(vv->u.val)) {
1022         vv = ref_bits(vv1);
1023     } else {
1024         vv = new_bits2(sz);
1025         if (vv == NULL) goto failed;
1026     }
1027     vv->bits = bits;
1028     v = vv->data;
1029     v1 = vv1->data;
1030     v2 = v + word;
1031     if (bit != 0) {
1032         bdigit_t d = 0;
1033         for (i = len1; i != 0;) {
1034             bdigit_t d2 = v1[--i];
1035             v2[i + 1] = d | (d2 >> (SHIFT - bit));
1036             d = d2 << bit;
1037         }
1038         if (vv1->len < 0) d |= ((bdigit_t)1 << bit) - 1;
1039         v2[0] = d;
1040     } else if (len1 != 0) memmove(v2, v1, len1 * sizeof *v2);
1041     if (word != 0) memset(v, (vv1->len < 0) ? ~0 : 0, word * sizeof *v);
1042 
1043     return normalize(vv, sz, (vv1->len < 0));
1044 failed:
1045     return new_error_mem(op->epoint3);
1046 }
1047 
rshift(oper_t op,uval_t s)1048 static MUST_CHECK Obj *rshift(oper_t op, uval_t s) {
1049     Bits *vv1 = Bits(op->v1);
1050     size_t i, sz, bits, len1;
1051     unsigned int bit, word;
1052     Bits *vv;
1053 
1054     word = s / SHIFT;
1055     bit = s % SHIFT;
1056     bits = vv1->bits;
1057     if (bits <= s) {
1058         return val_reference((vv1->len < 0) ? inv_bits : null_bits);
1059     }
1060     bits -= s;
1061     len1 = bitslen(vv1);
1062     sz = (len1 > word) ? (len1 - word) : 0;
1063     if (op->inplace == Obj(vv1)) {
1064         vv = ref_bits(vv1);
1065         if (vv->data != vv->u.val) vv->u.hash = -1;
1066     } else {
1067         vv = new_bits2(sz);
1068         if (vv == NULL) return new_error_mem(op->epoint3);
1069     }
1070     vv->bits = bits;
1071     if (sz == 0) {
1072         vv->data[0] = 0;
1073     } else {
1074         bdigit_t *v = vv->data;
1075         bdigit_t *v1 = vv1->data + word;
1076         if (bit != 0) {
1077             bdigit_t d = v1[0] >> bit;
1078             for (i = 0; i < sz - 1; i++) {
1079                 bdigit_t d2 = v1[i + 1];
1080                 v[i] = d | (d2 << (SHIFT - bit));
1081                 d = d2 >> bit;
1082             }
1083             v[i] = d;
1084         } else memmove(v, v1, sz * sizeof *v);
1085     }
1086     return normalize(vv, sz, (vv1->len < 0));
1087 }
1088 
calc2_bits(oper_t op)1089 static MUST_CHECK Obj *calc2_bits(oper_t op) {
1090     ssize_t val;
1091     switch (op->op) {
1092     case O_CMP:
1093         val = icmp(op);
1094         return val_reference(val < 0 ? minus1_value : int_value[(val > 0) ? 1 : 0]);
1095     case O_EQ: return truth_reference(icmp(op) == 0);
1096     case O_NE: return truth_reference(icmp(op) != 0);
1097     case O_MIN:
1098     case O_LT: return truth_reference(icmp(op) < 0);
1099     case O_LE: return truth_reference(icmp(op) <= 0);
1100     case O_MAX:
1101     case O_GT: return truth_reference(icmp(op) > 0);
1102     case O_GE: return truth_reference(icmp(op) >= 0);
1103     case O_AND:
1104     case O_OR:
1105     case O_XOR: return binary(op);
1106     case O_CONCAT: return concat(op);
1107     case O_IN: return obj_oper_error(op); /* TODO */
1108     default: return NULL;
1109     }
1110 }
1111 
repeat(oper_t op)1112 static inline MUST_CHECK Obj *repeat(oper_t op) {
1113     Bits *vv1 = Bits(op->v1), *vv;
1114     bdigit_t *v, *v1;
1115     bdigit_t uv;
1116     size_t sz, i, j, rbits, abits, bits, l;
1117     size_t blen = vv1->bits;
1118     uval_t rep;
1119     Error *err;
1120 
1121     err = op->v2->obj->uval(op->v2, &rep, 8 * sizeof rep, op->epoint2);
1122     if (err != NULL) return Obj(err);
1123 
1124     if (rep == 0 || blen == 0) {
1125         return val_reference((vv1->len < 0) ? inv_bits : null_bits);
1126     }
1127     if (rep == 1) {
1128         return Obj(ref_bits(vv1));
1129     }
1130 
1131     if (blen > SIZE_MAX / rep) goto failed; /* overflow */
1132     blen *= rep;
1133     sz = blen / SHIFT;
1134     if ((blen % SHIFT) != 0) sz++;
1135 
1136     vv = new_bits2(sz);
1137     if (vv == NULL) goto failed;
1138     v = vv->data;
1139     v1 = vv1->data;
1140 
1141     i = 0;
1142     bits = 0;
1143     uv = 0;
1144     rbits = vv1->bits / SHIFT;
1145     abits = vv1->bits % SHIFT;
1146     l = bitslen(vv1);
1147     for (; rep != 0; rep--) {
1148         if (bits != 0) {
1149             for (j = 0; j < rbits && j < l; j++) {
1150                 v[i++] = uv | (v1[j] << bits);
1151                 uv = (v1[j] >> (SHIFT - bits));
1152             }
1153             if (j < l) uv |= v1[j] << bits;
1154             if (j < rbits) {
1155                 v[i++] = uv; uv = 0; j++;
1156                 for (; j < rbits; j++) v[i++] = 0;
1157             }
1158             bits += abits;
1159             if (bits >= SHIFT) {
1160                 bits -= SHIFT;
1161                 v[i++] = uv;
1162                 if (bits != 0 && j < l) uv = v1[j] >> (abits - bits);
1163                 else uv = 0;
1164             }
1165         } else {
1166             for (j = 0; j < rbits && j < l; j++) v[i++] = v1[j];
1167             for (; j < rbits; j++) v[i++] = 0;
1168             uv = (j < l) ? v1[j] : 0;
1169             bits = abits;
1170         }
1171     }
1172     if (i < sz) v[i] = uv;
1173 
1174     vv->bits = blen;
1175     return normalize(vv, sz, (vv1->len < 0));
1176 failed:
1177     return new_error_mem(op->epoint3);
1178 }
1179 
slice(oper_t op,argcount_t indx)1180 static MUST_CHECK Obj *slice(oper_t op, argcount_t indx) {
1181     size_t sz;
1182     size_t i, o;
1183     Bits *vv, *vv1 = Bits(op->v1);
1184     bdigit_t *v;
1185     bdigit_t uv;
1186     bdigit_t inv = (vv1->len < 0) ? ~(bdigit_t)0 : 0;
1187     int bits;
1188     Obj *err;
1189     Funcargs *args = Funcargs(op->v2);
1190     struct indexoffs_s io;
1191 
1192     if (args->len < 1 || args->len - 1 > indx) {
1193         return new_error_argnum(args->len, 1, indx + 1, op->epoint2);
1194     }
1195     io.len = vv1->bits;
1196     io.epoint = &args->val[indx].epoint;
1197     io.val = args->val[indx].val;
1198 
1199     if (io.val->obj->iterable) {
1200         struct iter_s iter;
1201         iter.data = io.val; io.val->obj->getiter(&iter);
1202 
1203         if (iter.len == 0) {
1204             iter_destroy(&iter);
1205             return val_reference(null_bits);
1206         }
1207         sz = (iter.len + SHIFT - 1) / SHIFT;
1208 
1209         vv = new_bits2(sz);
1210         if (vv == NULL) {
1211             iter_destroy(&iter);
1212             goto failed;
1213         }
1214         v = vv->data;
1215 
1216         uv = inv;
1217         bits = 0; sz = 0;
1218         for (i = 0; i < iter.len && (io.val = iter.next(&iter)) != NULL; i++) {
1219             err = indexoffs(&io);
1220             if (err != NULL) {
1221                 val_destroy(Obj(vv));
1222                 iter_destroy(&iter);
1223                 return err;
1224             }
1225             o = io.offs / SHIFT;
1226             if (o < bitslen(vv1) && ((vv1->data[o] >> (io.offs % SHIFT)) & 1) != 0) {
1227                 uv ^= 1U << bits;
1228             }
1229             bits++;
1230             if (bits == SHIFT) {
1231                 v[sz++] = uv;
1232                 uv = inv;
1233                 bits = 0;
1234             }
1235         }
1236         iter_destroy(&iter);
1237         if (bits != 0) v[sz++] = uv & ((1U << bits) - 1);
1238 
1239         vv->bits = i;
1240         return normalize(vv, sz, false);
1241     }
1242     if (io.val->obj == COLONLIST_OBJ) {
1243         struct sliceparam_s s;
1244         size_t bo, wo, bl, wl, wl2, l;
1245         bdigit_t *v1;
1246 
1247         err = sliceparams(&s, &io);
1248         if (err != NULL) return err;
1249 
1250         if (s.length == 0) {
1251             return val_reference(null_bits);
1252         }
1253         if (s.step == 1) {
1254             if (s.length == vv1->bits && inv == 0) {
1255                 return Obj(ref_bits(vv1)); /* original bits */
1256             }
1257 
1258             bo = (uval_t)s.offset % SHIFT;
1259             wo = (uval_t)s.offset / SHIFT;
1260             bl = s.length % SHIFT;
1261             wl = s.length / SHIFT;
1262 
1263             sz = (bl > 0) ? (wl + 1) : wl;
1264             vv = new_bits2(sz);
1265             if (vv == NULL) goto failed;
1266             v = vv->data;
1267 
1268             l = bitslen(vv1);
1269             v1 = vv1->data + wo;
1270             wl2 = (wo > l) ? 0 : (l - wo);
1271             if (bo != 0) {
1272                 for (sz = 0; sz < wl; sz++) {
1273                     v[sz] = inv ^ (sz < wl2 ? (v1[sz] >> bo) : 0) ^ ((sz + 1 < wl2) ? (v1[sz + 1] << (SHIFT - bo)) : 0);
1274                 }
1275                 if (bl != 0) {
1276                     v[sz] = sz < wl2 ? (v1[sz] >> bo) : 0;
1277                     if (bl > (SHIFT - bo) && (sz + 1 < wl2)) v[sz] |= v1[sz + 1] << (SHIFT - bo);
1278                     v[sz] ^= inv;
1279                 }
1280             } else {
1281                 for (sz = 0; sz < wl2 && sz < wl; sz++) v[sz] = v1[sz] ^ inv;
1282                 for (; sz < wl; sz++) v[sz] = inv;
1283                 if (bl != 0) v[sz] = inv ^ ((sz < wl2) ? v1[sz] : 0);
1284             }
1285             if (bl != 0) v[sz++] &= ((1U << bl) - 1);
1286         } else {
1287             sz = s.length / SHIFT;
1288             if ((s.length % SHIFT) != 0) sz++;
1289             vv = new_bits2(sz);
1290             if (vv == NULL) goto failed;
1291             v = vv->data;
1292 
1293             uv = inv;
1294             sz = 0; bits = 0;
1295             l = bitslen(vv1);
1296             for (i = 0; i < s.length; i++) {
1297                 wo = (uval_t)s.offset / SHIFT;
1298                 if (wo < l && ((vv1->data[wo] >> ((uval_t)s.offset % SHIFT)) & 1) != 0) {
1299                     uv ^= 1U << bits;
1300                 }
1301                 bits++;
1302                 if (bits == SHIFT) {
1303                     v[sz++] = uv;
1304                     uv = inv;
1305                     bits = 0;
1306                 }
1307                 s.offset += s.step;
1308             }
1309             if (bits != 0) v[sz++] = uv & ((1U << bits) - 1);
1310         }
1311 
1312         vv->bits = s.length;
1313         return normalize(vv, sz, false);
1314     }
1315     err = indexoffs(&io);
1316     if (err != NULL) return err;
1317 
1318     uv = inv;
1319     o = io.offs / SHIFT;
1320     if (o < bitslen(vv1) && ((vv1->data[o] >> (io.offs % SHIFT)) & 1) != 0) {
1321         uv ^= 1;
1322     }
1323     return val_reference(bits_value[uv & 1]);
1324 failed:
1325     return new_error_mem(op->epoint3);
1326 }
1327 
calc2(oper_t op)1328 static MUST_CHECK Obj *calc2(oper_t op) {
1329     Bits *v1 = Bits(op->v1);
1330     Obj *o2 = op->v2;
1331     Obj *tmp, *result;
1332     Error *err;
1333     ival_t shift;
1334 
1335     if (op->op == O_X) {
1336         if (o2 == none_value || o2->obj == ERROR_OBJ) return val_reference(o2);
1337         return repeat(op);
1338     }
1339     if (op->op == O_LAND) {
1340         if (diagnostics.strict_bool) err_msg_bool_oper(op);
1341         return val_reference((v1->len != 0) ? o2 : Obj(v1));
1342     }
1343     if (op->op == O_LOR) {
1344         if (diagnostics.strict_bool) err_msg_bool_oper(op);
1345         return val_reference((v1->len != 0) ? Obj(v1) : o2);
1346     }
1347     switch (o2->obj->type) {
1348     case T_BOOL:
1349         if (diagnostics.strict_bool) err_msg_bool_oper(op);
1350         op->v2 = tmp = val_reference(bits_value[o2 == true_value ? 1 : 0]);
1351         if (op->inplace != NULL && op->inplace->refcount != 1) op->inplace = NULL;
1352         result = calc2(op);
1353         val_destroy(tmp);
1354         return result;
1355     case T_BITS:
1356         result = calc2_bits(op);
1357         if (result != NULL) return result;
1358         /* fall through */
1359     case T_INT:
1360         switch (op->op) {
1361         case O_LSHIFT:
1362             err = o2->obj->ival(o2, &shift, 8 * sizeof shift, op->epoint2);
1363             if (err != NULL) return Obj(err);
1364             if (shift == 0) return val_reference(Obj(v1));
1365             return (shift < 0) ? rshift(op, (uval_t)-shift) : lshift(op, (uval_t)shift);
1366         case O_RSHIFT:
1367             err = o2->obj->ival(o2, &shift, 8 * sizeof shift, op->epoint2);
1368             if (err != NULL) return Obj(err);
1369             if (shift == 0) return val_reference(Obj(v1));
1370             return (shift < 0) ? lshift(op, (uval_t)-shift) : rshift(op, (uval_t)shift);
1371         default: break;
1372         }
1373         tmp = int_from_bits(v1, op->epoint);
1374         op->v1 = tmp;
1375         op->inplace = (tmp->refcount == 1) ? tmp : NULL;
1376         result = tmp->obj->calc2(op);
1377         if (result->obj == ERROR_OBJ) error_obj_update(Error(result), tmp, Obj(v1));
1378         val_destroy(tmp);
1379         return result;
1380     default:
1381         if (op->op != O_MEMBER) {
1382             return o2->obj->rcalc2(op);
1383         }
1384         if (o2 == none_value || o2->obj == ERROR_OBJ) return val_reference(o2);
1385     }
1386     return obj_oper_error(op);
1387 }
1388 
rcalc2(oper_t op)1389 static MUST_CHECK Obj *rcalc2(oper_t op) {
1390     Bits *v2 = Bits(op->v2);
1391     Obj *o1 = op->v1;
1392     Obj *tmp, *result;
1393 
1394     switch (o1->obj->type) {
1395     case T_BOOL:
1396         if (diagnostics.strict_bool) err_msg_bool_oper(op);
1397         op->v1 = tmp = val_reference(bits_value[o1 == true_value ? 1 : 0]);
1398         op->inplace = NULL;
1399         result = calc2(op);
1400         val_destroy(tmp);
1401         return result;
1402     case T_BITS:
1403         result = calc2_bits(op);
1404         if (result != NULL) return result;
1405         /* fall through */
1406     case T_INT:
1407         tmp = int_from_bits(v2, op->epoint2);
1408         op->v2 = tmp;
1409         op->inplace = NULL;
1410         result = o1->obj->calc2(op);
1411         if (result->obj == ERROR_OBJ) error_obj_update(Error(result), tmp, Obj(v2));
1412         val_destroy(tmp);
1413         return result;
1414     default: break;
1415     }
1416     return obj_oper_error(op);
1417 }
1418 
bitsobj_init(void)1419 void bitsobj_init(void) {
1420     new_type(&obj, T_BITS, "bits", sizeof(Bits));
1421     obj.convert = convert;
1422     obj.convert2 = convert2;
1423     obj.destroy = destroy;
1424     obj.same = same;
1425     obj.truth = truth;
1426     obj.hash = hash;
1427     obj.repr = repr;
1428     obj.ival = ival;
1429     obj.uval = uval;
1430     obj.uval2 = uval2;
1431     obj.iaddress = ival;
1432     obj.uaddress = uval;
1433     obj.sign = sign;
1434     obj.function = function;
1435     obj.len = len;
1436     obj.calc1 = calc1;
1437     obj.calc2 = calc2;
1438     obj.rcalc2 = rcalc2;
1439     obj.slice = slice;
1440 }
1441 
bitsobj_names(void)1442 void bitsobj_names(void) {
1443     new_builtin("bits", val_reference(Obj(BITS_OBJ)));
1444 }
1445 
bitsobj_destroy(void)1446 void bitsobj_destroy(void) {
1447 #ifdef DEBUG
1448     if (null_bits->refcount != 1) fprintf(stderr, "bits %" PRIuSIZE "\n", null_bits->refcount - 1);
1449     if (inv_bits->refcount != 1) fprintf(stderr, "invbits %" PRIuSIZE "\n", inv_bits->refcount - 1);
1450     if (bits_value[0]->refcount != 1) fprintf(stderr, "bit0 %" PRIuSIZE "\n", bits_value[0]->refcount - 1);
1451     if (bits_value[1]->refcount != 1) fprintf(stderr, "bit1 %" PRIuSIZE "\n", bits_value[1]->refcount - 1);
1452     if (ibits_value[0]->refcount != 1) fprintf(stderr, "bit0 %" PRIuSIZE "\n", ibits_value[0]->refcount - 1);
1453     if (ibits_value[1]->refcount != 1) fprintf(stderr, "bit1 %" PRIuSIZE "\n", ibits_value[1]->refcount - 1);
1454 #endif
1455 }
1456