• source navigation  • diff markup  • identifier search  • freetext search  • 

Sources/ucode/vallist.c

  1 /*
  2  * Copyright (C) 2020-2021 Jo-Philipp Wich <jo@mein.io>
  3  *
  4  * Permission to use, copy, modify, and/or distribute this software for any
  5  * purpose with or without fee is hereby granted, provided that the above
  6  * copyright notice and this permission notice appear in all copies.
  7  *
  8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 15  */
 16 
 17 #include <string.h> /* memcpy(), memset() */
 18 #include <math.h> /* isnan(), INFINITY */
 19 #include <ctype.h> /* isspace(), isdigit(), isxdigit() */
 20 #include <assert.h>
 21 #include <errno.h>
 22 #include <assert.h>
 23 
 24 #include "ucode/util.h"
 25 #include "ucode/chunk.h"
 26 #include "ucode/program.h"
 27 #include "ucode/vallist.h"
 28 #include "ucode/vm.h"
 29 #include "ucode/platform.h"
 30 
 31 #define TAG_TYPE                        uint64_t
 32 #define TAG_BITS                        3
 33 #define TAG_MASK                        ((1LL << ((sizeof(TAG_TYPE) << 3) - TAG_BITS)) - 1)
 34 #define TAG_ALIGN(s)            (((s) + (1 << TAG_BITS) - 1) & -(1 << TAG_BITS))
 35 #define TAG_GET_TYPE(n)         (int)((TAG_TYPE)n & ((1 << TAG_BITS) - 1))
 36 #define TAG_FIT_NV(n)           ((uint64_t)n <= TAG_MASK)
 37 #define TAG_SET_NV(n)           ((TAG_TYPE)(uint64_t)n << TAG_BITS)
 38 #define TAG_GET_NV(n)           (uint64_t)((uint64_t)((TAG_TYPE)n >> TAG_BITS) & TAG_MASK)
 39 #define TAG_FIT_STR(l)          ((l - 1) < (((sizeof(TAG_TYPE) << 3) - TAG_BITS) >> 3))
 40 #define TAG_SET_STR_L(l)        (TAG_TYPE)((l & ((1 << (8 - TAG_BITS)) - 1)) << TAG_BITS)
 41 #define TAG_GET_STR_L(n)        (size_t)(((TAG_TYPE)n >> TAG_BITS) & ((1 << (8 - TAG_BITS)) - 1))
 42 #define TAG_GET_BOOL(n)         (bool)(((TAG_TYPE)n >> TAG_BITS) & 1)
 43 #define TAG_GET_OFFSET(n)       (size_t)(((TAG_TYPE)n >> TAG_BITS) & TAG_MASK)
 44 
 45 #define UC_VALLIST_CHUNK_SIZE   8
 46 
 47 
 48 static uc_value_t *
 49 uc_number_parse_common(const char *buf, bool octal, char **end)
 50 {
 51         unsigned long long u;
 52         const char *p = buf;
 53         bool neg = false;
 54         int base = 10;
 55         double d;
 56         char *e;
 57 
 58         while (isspace(*p))
 59                 p++;
 60 
 61         if (*p == '-') {
 62                 neg = true;
 63                 p++;
 64         }
 65         else if (*p == '+') {
 66                 p++;
 67         }
 68 
 69         if (*p != 0 && !isxdigit(*p))
 70                 return NULL;
 71 
 72         if (!end)
 73                 end = &e;
 74 
 75         if (p[0] == '') {
 76                 switch (p[1]|32) {
 77                 case '':
 78                 case '1':
 79                 case '2':
 80                 case '3':
 81                 case '4':
 82                 case '5':
 83                 case '6':
 84                 case '7':
 85                         base = octal ? 8 : 10;
 86                         break;
 87 
 88                 case 'x':
 89                         base = 16;
 90                         break;
 91 
 92                 case 'b':
 93                         base = 2;
 94                         p += 2;
 95                         break;
 96 
 97                 case 'o':
 98                         base = 8;
 99                         p += 2;
100                         break;
101                 }
102         }
103 
104         u = strtoull(p, end, base);
105 
106         if (base >= 10 && (**end == '.' || (**end|32) == 'e')) {
107                 d = strtod(p, end);
108 
109                 while (isspace(**end))
110                         (*end)++;
111 
112                 if (**end != 0)
113                         return NULL;
114 
115                 if (neg)
116                         d = -d;
117 
118                 return ucv_double_new(d);
119         }
120 
121         while (isspace(**end))
122                 (*end)++;
123 
124         if (**end != 0)
125                 return NULL;
126 
127         if (neg) {
128                 if (u > INT64_MAX)
129                         return ucv_int64_new(INT64_MIN);
130 
131                 return ucv_int64_new(-(int64_t)u);
132         }
133 
134         return ucv_uint64_new(u);
135 }
136 
137 uc_value_t *
138 uc_number_parse(const char *buf, char **end)
139 {
140         return uc_number_parse_common(buf, false, end);
141 }
142 
143 uc_value_t *
144 uc_number_parse_octal(const char *buf, char **end)
145 {
146         return uc_number_parse_common(buf, true, end);
147 }
148 
149 bool
150 uc_double_pack(double d, char *buf, bool little_endian)
151 {
152         int8_t step = little_endian ? -1 : 1;
153         uint32_t hibits = 0, lobits = 0;
154         int32_t exponent = 0;
155         bool sign = false;
156         double fraction;
157         uint8_t *p;
158 
159         if (d == 0.0) {
160                 sign = (copysign(1.0, d) == -1.0);
161         }
162         else if (isnan(d)) {
163                 sign = (copysign(1.0, d) == -1.0);
164                 exponent = 0x7ff;
165                 lobits = 0x1000000;
166                 hibits = 0xfffffff;
167         }
168         else if (!isfinite(d)) {
169                 sign = (d < 0.0);
170                 exponent = 0x7ff;
171         }
172         else {
173                 if (d < 0.0) {
174                         sign = true;
175                         d = -d;
176                 }
177 
178                 fraction = frexp(d, &exponent);
179 
180                 if (fraction == 0.0) {
181                         exponent = 0;
182                 }
183                 else {
184                         assert(fraction >= 0.5 && fraction < 1.0);
185 
186                         fraction *= 2.0;
187                         exponent--;
188                 }
189 
190                 if (exponent >= 1024) {
191                         errno = ERANGE;
192 
193                         return false;
194                 }
195                 else if (exponent < -1022) {
196                         fraction = ldexp(fraction, 1022 + exponent);
197                         exponent = 0;
198                 }
199                 else if (exponent != 0 || fraction != 0.0) {
200                         fraction -= 1.0;
201                         exponent += 1023;
202                 }
203 
204                 fraction *= 268435456.0;
205                 hibits = (uint32_t)fraction;
206                 assert(hibits <= 0xfffffff);
207 
208                 fraction -= (double)hibits;
209                 fraction *= 16777216.0;
210                 lobits = (uint32_t)(fraction + 0.5);
211                 assert(lobits <= 0x1000000);
212 
213                 if (lobits >> 24) {
214                         lobits = 0;
215 
216                         if (++hibits >> 28) {
217                                 hibits = 0;
218 
219                                 if (++exponent >= 2047) {
220                                         errno = ERANGE;
221 
222                                         return false;
223                                 }
224                         }
225                 }
226         }
227 
228         p = (uint8_t *)buf + (little_endian ? 7 : 0);
229         *p = (sign << 7) | (exponent >> 4);
230 
231         p += step;
232         *p = ((exponent & 0xf) << 4) | (hibits >> 24);
233 
234         p += step;
235         *p = (hibits >> 16) & 0xff;
236 
237         p += step;
238         *p = (hibits >> 8) & 0xff;
239 
240         p += step;
241         *p = hibits & 0xff;
242 
243         p += step;
244         *p = (lobits >> 16) & 0xff;
245 
246         p += step;
247         *p = (lobits >> 8) & 0xff;
248 
249         p += step;
250         *p = lobits & 0xff;
251 
252         return true;
253 }
254 
255 double
256 uc_double_unpack(const char *buf, bool little_endian)
257 {
258         int8_t step = little_endian ? -1 : 1;
259         uint32_t lofrac, hifrac;
260         int32_t exponent;
261         uint8_t *p;
262         bool sign;
263         double d;
264 
265         p = (uint8_t *)buf + (little_endian ? 7 : 0);
266         sign = (*p >> 7) & 1;
267         exponent = (*p & 0x7f) << 4;
268 
269         p += step;
270         exponent |= (*p >> 4) & 0xf;
271         hifrac = (*p & 0xf) << 24;
272 
273         p += step;
274         hifrac |= *p << 16;
275 
276         p += step;
277         hifrac |= *p << 8;
278 
279         p += step;
280         hifrac |= *p;
281 
282         p += step;
283         lofrac = *p << 16;
284 
285         p += step;
286         lofrac |= *p << 8;
287 
288         p += step;
289         lofrac |= *p;
290 
291         if (exponent == 0x7ff) {
292                 if (lofrac == 0 && hifrac == 0)
293                         return sign ? -INFINITY : INFINITY;
294                 else
295                         return sign ? -NAN : NAN;
296         }
297 
298         d = (double)hifrac + (double)lofrac / 16777216.0;
299         d /= 268435456.0;
300 
301         if (exponent == 0) {
302                 exponent = -1022;
303         }
304         else {
305                 exponent -= 1023;
306                 d += 1.0;
307         }
308 
309         d = ldexp(d, exponent);
310 
311         return sign ? -d : d;
312 }
313 
314 void
315 uc_vallist_init(uc_value_list_t *list)
316 {
317         list->isize = 0;
318         list->dsize = 0;
319         list->index = NULL;
320         list->data = NULL;
321 }
322 
323 void
324 uc_vallist_free(uc_value_list_t *list)
325 {
326         free(list->index);
327         free(list->data);
328         uc_vallist_init(list);
329 }
330 
331 static void
332 add_num(uc_value_list_t *list, uint64_t n)
333 {
334         size_t sz = TAG_ALIGN(sizeof(n));
335 
336         if (TAG_FIT_NV(n)) {
337                 list->index[list->isize++] = (TAG_TYPE)(TAG_NUM | TAG_SET_NV(n));
338         }
339         else {
340                 if ((TAG_TYPE)list->dsize + sz > TAG_MASK) {
341                         fprintf(stderr, "Constant data too large\n");
342                         abort();
343                 }
344 
345                 list->data = xrealloc(list->data, list->dsize + sz);
346 
347                 n = htobe64(n);
348                 memset(list->data + list->dsize, 0, sz);
349                 memcpy(list->data + list->dsize, &n, sizeof(n));
350 
351                 list->index[list->isize++] = (TAG_TYPE)(TAG_LNUM | (list->dsize << TAG_BITS));
352                 list->dsize += sz;
353         }
354 }
355 
356 static ssize_t
357 find_num(uc_value_list_t *list, uint64_t n)
358 {
359         TAG_TYPE search;
360         size_t i;
361 
362         if (TAG_FIT_NV(n)) {
363                 search = (TAG_TYPE)(TAG_NUM | TAG_SET_NV(n));
364 
365                 for (i = 0; i < list->isize; i++)
366                         if (list->index[i] == search)
367                                 return i;
368         }
369         else {
370                 for (i = 0; i < list->isize; i++) {
371                         if (TAG_GET_TYPE(list->index[i]) != TAG_LNUM)
372                                 continue;
373 
374                         if (TAG_GET_OFFSET(list->index[i]) + sizeof(uint64_t) > list->dsize)
375                                 continue;
376 
377                         if ((uint64_t)be64toh(*(uint64_t *)(list->data + TAG_GET_OFFSET(list->index[i]))) != n)
378                                 continue;
379 
380                         return i;
381                 }
382         }
383 
384         return -1;
385 }
386 
387 static void
388 add_dbl(uc_value_list_t *list, double d)
389 {
390         size_t sz = TAG_ALIGN(sizeof(uint64_t));
391 
392         if ((TAG_TYPE)list->dsize + sz > TAG_MASK) {
393                 fprintf(stderr, "Constant data too large\n");
394                 abort();
395         }
396 
397         list->data = xrealloc(list->data, list->dsize + sz);
398 
399         memset(list->data + list->dsize, 0, sz);
400 
401         if (!uc_double_pack(d, list->data + list->dsize, false)) {
402                 fprintf(stderr, "Double value not representable\n");
403                 abort();
404         }
405 
406         list->index[list->isize++] = (uint64_t)(TAG_DBL | (list->dsize << TAG_BITS));
407         list->dsize += sz;
408 }
409 
410 static ssize_t
411 find_dbl(uc_value_list_t *list, double d)
412 {
413         size_t i;
414 
415         for (i = 0; i < list->isize; i++) {
416                 if (TAG_GET_TYPE(list->index[i]) != TAG_DBL)
417                         continue;
418 
419                 if (TAG_GET_OFFSET(list->index[i]) + sizeof(uint64_t) > list->dsize)
420                         continue;
421 
422                 if (uc_double_unpack(list->data + TAG_GET_OFFSET(list->index[i]), false) != d)
423                         continue;
424 
425                 return i;
426         }
427 
428         return -1;
429 }
430 
431 static void
432 add_str(uc_value_list_t *list, const char *s, size_t slen)
433 {
434         const uint8_t *u8 = (const uint8_t *)s;
435         uint32_t sl;
436         size_t sz;
437         char *dst;
438         size_t i;
439 
440         if (slen > UINT32_MAX) {
441                 fprintf(stderr, "String constant too long\n");
442                 abort();
443         }
444 
445         sz = TAG_ALIGN(sizeof(uint32_t) + slen);
446 
447         if ((TAG_TYPE)list->dsize + sz > TAG_MASK) {
448                 fprintf(stderr, "Constant data too large\n");
449                 abort();
450         }
451 
452         if (TAG_FIT_STR(slen)) {
453                 list->index[list->isize] = (uint64_t)(TAG_STR | TAG_SET_STR_L(slen));
454 
455                 for (i = 0; i < slen; i++)
456                         list->index[list->isize] |= (((TAG_TYPE)u8[i] << ((i + 1) << 3)));
457 
458                 list->isize++;
459         }
460         else {
461                 list->data = xrealloc(list->data, list->dsize + sz);
462 
463                 sl = htobe32(slen);
464                 dst = list->data + list->dsize;
465                 memcpy(dst, &sl, sizeof(sl));
466 
467                 dst += sizeof(sl);
468                 memcpy(dst, s, slen);
469 
470                 dst += slen;
471                 memset(dst, 0, TAG_ALIGN(sizeof(uint32_t) + slen) - (sizeof(uint32_t) + slen));
472 
473                 list->index[list->isize++] = (uint64_t)(TAG_LSTR | (list->dsize << TAG_BITS));
474                 list->dsize += sz;
475         }
476 }
477 
478 static ssize_t
479 find_str(uc_value_list_t *list, const char *s, size_t slen)
480 {
481         const uint8_t *u8 = (const uint8_t *)s;
482         TAG_TYPE search;
483         size_t i, len;
484 
485         if (TAG_FIT_STR(slen)) {
486                 search = (TAG_TYPE)(TAG_STR | TAG_SET_STR_L(slen));
487 
488                 for (i = 0; i < slen; i++)
489                         search |= (((TAG_TYPE)u8[i] << ((i + 1) << 3)));
490 
491                 for (i = 0; i < list->isize; i++)
492                         if (list->index[i] == search)
493                                 return i;
494         }
495         else {
496                 for (i = 0; i < list->isize; i++) {
497                         if (TAG_GET_TYPE(list->index[i]) != TAG_LSTR)
498                                 continue;
499 
500                         if (TAG_GET_OFFSET(list->index[i]) + sizeof(uint32_t) > list->dsize)
501                                 continue;
502 
503                         len = (size_t)be32toh(*(uint32_t *)(list->data + TAG_GET_OFFSET(list->index[i])));
504 
505                         if (len != slen)
506                                 continue;
507 
508                         if (TAG_GET_OFFSET(list->index[i]) + sizeof(uint32_t) + len > list->dsize)
509                                 continue;
510 
511                         if (memcmp(list->data + TAG_GET_OFFSET(list->index[i]) + sizeof(uint32_t), s, slen))
512                                 continue;
513 
514                         return i;
515                 }
516         }
517 
518         return -1;
519 }
520 
521 ssize_t
522 uc_vallist_add(uc_value_list_t *list, uc_value_t *value)
523 {
524         ssize_t existing;
525         uint64_t u64;
526 
527         if ((list->isize % UC_VALLIST_CHUNK_SIZE) == 0) {
528                 list->index = xrealloc(list->index, sizeof(list->index[0]) * (list->isize + UC_VALLIST_CHUNK_SIZE));
529                 memset(&list->index[list->isize], 0, UC_VALLIST_CHUNK_SIZE);
530         }
531 
532         switch (ucv_type(value)) {
533         case UC_INTEGER:
534                 u64 = ucv_uint64_get(value);
535 
536                 assert(errno == 0);
537 
538                 existing = find_num(list, u64);
539 
540                 if (existing > -1)
541                         return existing;
542 
543                 add_num(list, u64);
544 
545                 break;
546 
547         case UC_DOUBLE:
548                 existing = find_dbl(list, ucv_double_get(value));
549 
550                 if (existing > -1)
551                         return existing;
552 
553                 add_dbl(list, ucv_double_get(value));
554 
555                 break;
556 
557         case UC_STRING:
558                 existing = find_str(list,
559                         ucv_string_get(value),
560                         ucv_string_length(value));
561 
562                 if (existing > -1)
563                         return existing;
564 
565                 add_str(list,
566                         ucv_string_get(value),
567                         ucv_string_length(value));
568 
569                 break;
570 
571         default:
572                 return -1;
573         }
574 
575         return (ssize_t)list->isize - 1;
576 }
577 
578 uc_value_type_t
579 uc_vallist_type(uc_value_list_t *list, size_t idx)
580 {
581         if (idx >= list->isize)
582                 return TAG_INVAL;
583 
584         return TAG_GET_TYPE(list->index[idx]);
585 }
586 
587 uc_value_t *
588 uc_vallist_get(uc_value_list_t *list, size_t idx)
589 {
590         uint8_t str[sizeof(TAG_TYPE)];
591         size_t n, len;
592 
593         switch (uc_vallist_type(list, idx)) {
594         case TAG_NUM:
595                 return ucv_uint64_new(TAG_GET_NV(list->index[idx]));
596 
597         case TAG_LNUM:
598                 if (TAG_GET_OFFSET(list->index[idx]) + sizeof(uint64_t) > list->dsize)
599                         return NULL;
600 
601                 return ucv_uint64_new(be64toh(*(uint64_t *)(list->data + TAG_GET_OFFSET(list->index[idx]))));
602 
603         case TAG_DBL:
604                 if (TAG_GET_OFFSET(list->index[idx]) + sizeof(double) > list->dsize)
605                         return NULL;
606 
607                 return ucv_double_new(uc_double_unpack(list->data + TAG_GET_OFFSET(list->index[idx]), false));
608 
609         case TAG_STR:
610                 len = TAG_GET_STR_L(list->index[idx]);
611 
612                 for (n = 0; n < len; n++)
613                         str[n] = (list->index[idx] >> ((n + 1) << 3));
614 
615                 return ucv_string_new_length((char *)str, len);
616 
617         case TAG_LSTR:
618                 if (TAG_GET_OFFSET(list->index[idx]) + sizeof(uint32_t) > list->dsize)
619                         return NULL;
620 
621                 len = (size_t)be32toh(*(uint32_t *)(list->data + TAG_GET_OFFSET(list->index[idx])));
622 
623                 if (TAG_GET_OFFSET(list->index[idx]) + sizeof(uint32_t) + len > list->dsize)
624                         return NULL;
625 
626                 return ucv_string_new_length(list->data + TAG_GET_OFFSET(list->index[idx]) + sizeof(uint32_t), len);
627 
628         default:
629                 return NULL;
630         }
631 }
632 

This page was automatically generated by LXR 0.3.1.  •  OpenWrt