From 599d233f0a7283f0b73f9a9d6c422efea418a59e Mon Sep 17 00:00:00 2001 From: Jo-Philipp Wich Date: Mon, 13 Dec 2021 00:00:44 +0100 Subject: vallist: store double values in a platform neutral manner Import the binary64 double packing routines from the struct module and use them to store numeric double values in a platform agnostic big endian format. Signed-off-by: Jo-Philipp Wich --- include/ucode/vallist.h | 3 + vallist.c | 180 ++++++++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 178 insertions(+), 5 deletions(-) diff --git a/include/ucode/vallist.h b/include/ucode/vallist.h index 47ddc7d..a1b33a5 100644 --- a/include/ucode/vallist.h +++ b/include/ucode/vallist.h @@ -43,6 +43,9 @@ typedef enum { uc_value_t *uc_number_parse(const char *buf, char **end); +bool uc_double_pack(double d, char *buf, bool little_endian); +double uc_double_unpack(const char *buf, bool little_endian); + void uc_vallist_init(uc_value_list_t *list); void uc_vallist_free(uc_value_list_t *list); diff --git a/vallist.c b/vallist.c index d6a8169..d46bf23 100644 --- a/vallist.c +++ b/vallist.c @@ -18,6 +18,7 @@ #include /* htobe64(), be64toh() */ #include /* isnan(), INFINITY */ #include /* isspace(), isdigit(), isxdigit() */ +#include #include #include @@ -93,6 +94,171 @@ uc_number_parse(const char *buf, char **end) return ucv_uint64_new(u); } +bool +uc_double_pack(double d, char *buf, bool little_endian) +{ + int8_t step = little_endian ? -1 : 1; + uint32_t hibits = 0, lobits = 0; + int32_t exponent = 0; + bool sign = false; + double fraction; + uint8_t *p; + + if (d == 0.0) { + sign = (copysign(1.0, d) == -1.0); + } + else if (isnan(d)) { + sign = (copysign(1.0, d) == -1.0); + exponent = 0x7ff; + lobits = 0x1000000; + hibits = 0xfffffff; + } + else if (!isfinite(d)) { + sign = (d < 0.0); + exponent = 0x7ff; + } + else { + if (d < 0.0) { + sign = true; + d = -d; + } + + fraction = frexp(d, &exponent); + + if (fraction == 0.0) { + exponent = 0; + } + else { + assert(fraction >= 0.5 && fraction < 1.0); + + fraction *= 2.0; + exponent--; + } + + if (exponent >= 1024) { + errno = ERANGE; + + return false; + } + else if (exponent < -1022) { + fraction = ldexp(fraction, 1022 + exponent); + exponent = 0; + } + else if (exponent != 0 || fraction != 0.0) { + fraction -= 1.0; + exponent += 1023; + } + + fraction *= 268435456.0; + hibits = (uint32_t)fraction; + assert(hibits <= 0xfffffff); + + fraction -= (double)hibits; + fraction *= 16777216.0; + lobits = (uint32_t)(fraction + 0.5); + assert(lobits <= 0x1000000); + + if (lobits >> 24) { + lobits = 0; + + if (++hibits >> 28) { + hibits = 0; + + if (++exponent >= 2047) { + errno = ERANGE; + + return false; + } + } + } + } + + p = (uint8_t *)buf + (little_endian ? 7 : 0); + *p = (sign << 7) | (exponent >> 4); + + p += step; + *p = ((exponent & 0xf) << 4) | (hibits >> 24); + + p += step; + *p = (hibits >> 16) & 0xff; + + p += step; + *p = (hibits >> 8) & 0xff; + + p += step; + *p = hibits & 0xff; + + p += step; + *p = (lobits >> 16) & 0xff; + + p += step; + *p = (lobits >> 8) & 0xff; + + p += step; + *p = lobits & 0xff; + + return true; +} + +double +uc_double_unpack(const char *buf, bool little_endian) +{ + int8_t step = little_endian ? -1 : 1; + uint32_t lofrac, hifrac; + int32_t exponent; + uint8_t *p; + bool sign; + double d; + + p = (uint8_t *)buf + (little_endian ? 7 : 0); + sign = (*p >> 7) & 1; + exponent = (*p & 0x7f) << 4; + + p += step; + exponent |= (*p >> 4) & 0xf; + hifrac = (*p & 0xf) << 24; + + p += step; + hifrac |= *p << 16; + + p += step; + hifrac |= *p << 8; + + p += step; + hifrac |= *p; + + p += step; + lofrac = *p << 16; + + p += step; + lofrac |= *p << 8; + + p += step; + lofrac |= *p; + + if (exponent == 0x7ff) { + if (lofrac == 0 && hifrac == 0) + return sign ? -INFINITY : INFINITY; + else + return sign ? -NAN : NAN; + } + + d = (double)hifrac + (double)lofrac / 16777216.0; + d /= 268435456.0; + + if (exponent == 0) { + exponent = -1022; + } + else { + exponent -= 1023; + d += 1.0; + } + + d = ldexp(d, exponent); + + return sign ? -d : d; +} + void uc_vallist_init(uc_value_list_t *list) { @@ -180,7 +346,7 @@ find_num(uc_value_list_t *list, uint64_t n) static void add_dbl(uc_value_list_t *list, double d) { - size_t sz = TAG_ALIGN(sizeof(d)); + size_t sz = TAG_ALIGN(sizeof(uint64_t)); if ((TAG_TYPE)list->dsize + sz > TAG_MASK) { fprintf(stderr, "Constant data too large\n"); @@ -190,7 +356,11 @@ add_dbl(uc_value_list_t *list, double d) list->data = xrealloc(list->data, list->dsize + sz); memset(list->data + list->dsize, 0, sz); - memcpy(list->data + list->dsize, &d, sizeof(d)); + + if (!uc_double_pack(d, list->data + list->dsize, false)) { + fprintf(stderr, "Double value not representable\n"); + abort(); + } list->index[list->isize++] = (uint64_t)(TAG_DBL | (list->dsize << TAG_BITS)); list->dsize += sz; @@ -205,10 +375,10 @@ find_dbl(uc_value_list_t *list, double d) if (TAG_GET_TYPE(list->index[i]) != TAG_DBL) continue; - if (TAG_GET_OFFSET(list->index[i]) + sizeof(double) > list->dsize) + if (TAG_GET_OFFSET(list->index[i]) + sizeof(uint64_t) > list->dsize) continue; - if (*(double *)(list->data + TAG_GET_OFFSET(list->index[i])) != d) + if (uc_double_unpack(list->data + TAG_GET_OFFSET(list->index[i]), false) != d) continue; return i; @@ -414,7 +584,7 @@ uc_vallist_get(uc_value_list_t *list, size_t idx) if (TAG_GET_OFFSET(list->index[idx]) + sizeof(double) > list->dsize) return NULL; - return ucv_double_new(*(double *)(list->data + TAG_GET_OFFSET(list->index[idx]))); + return ucv_double_new(uc_double_unpack(list->data + TAG_GET_OFFSET(list->index[idx]), false)); case TAG_STR: len = TAG_GET_STR_L(list->index[idx]); -- cgit v1.2.3 From 5bb9ab77945ec429a4bdf9b5d317237d7619f8cc Mon Sep 17 00:00:00 2001 From: Jo-Philipp Wich Date: Mon, 13 Dec 2021 00:04:26 +0100 Subject: struct: reuse double packing routines from core Use uc_pack_double() and uc_unpack_double() from core to avoid unnecessary code duplication. Signed-off-by: Jo-Philipp Wich --- lib/struct.c | 167 ++--------------------------------------------------------- 1 file changed, 3 insertions(+), 164 deletions(-) diff --git a/lib/struct.c b/lib/struct.c index 32edb1b..dad73a6 100644 --- a/lib/struct.c +++ b/lib/struct.c @@ -69,6 +69,7 @@ #include #include "ucode/module.h" +#include "ucode/vallist.h" static uc_resource_type_t *struct_type; @@ -758,111 +759,7 @@ double_pack32(double d, char *buf, bool little_endian) return true; } -static bool -double_pack64(double d, char *buf, bool little_endian) -{ - int8_t step = little_endian ? -1 : 1; - uint32_t hibits = 0, lobits = 0; - int32_t exponent = 0; - bool sign = false; - double fraction; - uint8_t *p; - - if (d == 0.0) { - sign = (copysign(1.0, d) == -1.0); - } - else if (isnan(d)) { - sign = (copysign(1.0, d) == -1.0); - exponent = 0x7ff; - lobits = 0x1000000; - hibits = 0xfffffff; - } - else if (!isfinite(d)) { - sign = (d < 0.0); - exponent = 0x7ff; - } - else { - if (d < 0.0) { - sign = true; - d = -d; - } - - fraction = frexp(d, &exponent); - - if (fraction == 0.0) { - exponent = 0; - } - else { - assert(fraction >= 0.5 && fraction < 1.0); - - fraction *= 2.0; - exponent--; - } - - if (exponent >= 1024) { - errno = ERANGE; - - return false; - } - else if (exponent < -1022) { - fraction = ldexp(fraction, 1022 + exponent); - exponent = 0; - } - else if (exponent != 0 || fraction != 0.0) { - fraction -= 1.0; - exponent += 1023; - } - - fraction *= 268435456.0; - hibits = (uint32_t)fraction; - assert(hibits <= 0xfffffff); - - fraction -= (double)hibits; - fraction *= 16777216.0; - lobits = (uint32_t)(fraction + 0.5); - assert(lobits <= 0x1000000); - - if (lobits >> 24) { - lobits = 0; - - if (++hibits >> 28) { - hibits = 0; - - if (++exponent >= 2047) { - errno = ERANGE; - - return false; - } - } - } - } - - p = (uint8_t *)buf + (little_endian ? 7 : 0); - *p = (sign << 7) | (exponent >> 4); - - p += step; - *p = ((exponent & 0xf) << 4) | (hibits >> 24); - - p += step; - *p = (hibits >> 16) & 0xff; - - p += step; - *p = (hibits >> 8) & 0xff; - - p += step; - *p = hibits & 0xff; - - p += step; - *p = (lobits >> 16) & 0xff; - - p += step; - *p = (lobits >> 8) & 0xff; - - p += step; - *p = lobits & 0xff; - - return true; -} +#define double_pack64 uc_double_pack static double double_unpack16(const char *buf, bool little_endian) @@ -949,65 +846,7 @@ double_unpack32(const char *buf, bool little_endian) return sign ? -d : d; } - -static double -double_unpack64(const char *buf, bool little_endian) -{ - int8_t step = little_endian ? -1 : 1; - uint32_t lofrac, hifrac; - int32_t exponent; - uint8_t *p; - bool sign; - double d; - - p = (uint8_t *)buf + (little_endian ? 7 : 0); - sign = (*p >> 7) & 1; - exponent = (*p & 0x7f) << 4; - - p += step; - exponent |= (*p >> 4) & 0xf; - hifrac = (*p & 0xf) << 24; - - p += step; - hifrac |= *p << 16; - - p += step; - hifrac |= *p << 8; - - p += step; - hifrac |= *p; - - p += step; - lofrac = *p << 16; - - p += step; - lofrac |= *p << 8; - - p += step; - lofrac |= *p; - - if (exponent == 0x7ff) { - if (lofrac == 0 && hifrac == 0) - return sign ? -INFINITY : INFINITY; - else - return sign ? -NAN : NAN; - } - - d = (double)hifrac + (double)lofrac / 16777216.0; - d /= 268435456.0; - - if (exponent == 0) { - exponent = -1022; - } - else { - exponent -= 1023; - d += 1.0; - } - - d = ldexp(d, exponent); - - return sign ? -d : d; -} +#define double_unpack64 uc_double_unpack static bool range_exception(uc_vm_t *vm, const formatdef_t *f, bool is_unsigned) -- cgit v1.2.3 From 2fd7ab5f73048f3363c05a614dc3362a816af237 Mon Sep 17 00:00:00 2001 From: Jo-Philipp Wich Date: Mon, 3 Jan 2022 17:33:50 +0100 Subject: vm: optimize string concatenation When concatenating strings, avoid allocating three times the required memory in the worst case. Instead of first allocating the string representations of the operands followed by the memory for the final string, allocate a string buffer and print the operands into it. This will grow the target memory as needed and avoid redundant internal copies of the involved strings. Also handle the special where the final string fits into a tagged pointer and deal with it accordingly. Signed-off-by: Jo-Philipp Wich --- vm.c | 53 +++++++++++++++++++++++++++++++++-------------------- 1 file changed, 33 insertions(+), 20 deletions(-) diff --git a/vm.c b/vm.c index abdb9b9..e7757cd 100644 --- a/vm.c +++ b/vm.c @@ -1345,12 +1345,41 @@ uc_vm_value_bitop(uc_vm_t *vm, uc_vm_insn_t operation, uc_value_t *value, uc_val return rv; } +static uc_value_t * +uc_vm_string_concat(uc_vm_t *vm, uc_value_t *v1, uc_value_t *v2) +{ + char buf[sizeof(void *)], *s1, *s2; + uc_stringbuf_t *sbuf; + size_t l1, l2; + + /* optimize cases for string+string concat... */ + if (ucv_type(v1) == UC_STRING && ucv_type(v2) == UC_STRING) { + s1 = ucv_string_get(v1); + s2 = ucv_string_get(v2); + l1 = ucv_string_length(v1); + l2 = ucv_string_length(v2); + + /* ... result fits into a tagged pointer */ + if (l1 + l2 + 1 < sizeof(buf)) { + memcpy(&buf[0], s1, l1); + memcpy(&buf[l1], s2, l2); + + return ucv_string_new_length(buf, l1 + l2); + } + } + + sbuf = ucv_stringbuf_new(); + + ucv_to_stringbuf(vm, sbuf, v1, false); + ucv_to_stringbuf(vm, sbuf, v2, false); + + return ucv_stringbuf_finish(sbuf); +} + static uc_value_t * uc_vm_value_arith(uc_vm_t *vm, uc_vm_insn_t operation, uc_value_t *value, uc_value_t *operand) { uc_value_t *nv1, *nv2, *rv = NULL; - char *s, *s1, *s2; - size_t len1, len2; uint64_t u1, u2; int64_t n1, n2; double d1, d2; @@ -1359,24 +1388,8 @@ uc_vm_value_arith(uc_vm_t *vm, uc_vm_insn_t operation, uc_value_t *value, uc_val operation == I_BAND || operation == I_BXOR || operation == I_BOR) return uc_vm_value_bitop(vm, operation, value, operand); - if (operation == I_ADD && (ucv_type(value) == UC_STRING || ucv_type(operand) == UC_STRING)) { - s1 = (ucv_type(value) != UC_STRING) ? ucv_to_string(vm, value) : NULL; - s2 = (ucv_type(operand) != UC_STRING) ? ucv_to_string(vm, operand) : NULL; - len1 = s1 ? strlen(s1) : ucv_string_length(value); - len2 = s2 ? strlen(s2) : ucv_string_length(operand); - s = xalloc(len1 + len2 + 1); - - memcpy(s, s1 ? s1 : ucv_string_get(value), len1); - memcpy(s + len1, s2 ? s2 : ucv_string_get(operand), len2); - free(s1); - free(s2); - - rv = ucv_string_new_length(s, len1 + len2); - - free(s); - - return rv; - } + if (operation == I_ADD && (ucv_type(value) == UC_STRING || ucv_type(operand) == UC_STRING)) + return uc_vm_string_concat(vm, value, operand); nv1 = ucv_to_number(value); nv2 = ucv_to_number(operand); -- cgit v1.2.3