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

This page was automatically generated by LXR 0.3.1.  •  OpenWrt