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