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