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