aboutsummaryrefslogtreecommitdiffstats
path: root/src/shared/quickjs/cutils.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/shared/quickjs/cutils.c')
-rw-r--r--src/shared/quickjs/cutils.c630
1 files changed, 630 insertions, 0 deletions
diff --git a/src/shared/quickjs/cutils.c b/src/shared/quickjs/cutils.c
new file mode 100644
index 000000000..95ae5688d
--- /dev/null
+++ b/src/shared/quickjs/cutils.c
@@ -0,0 +1,630 @@
+/*
+ * C utilities
+ *
+ * Copyright (c) 2017 Fabrice Bellard
+ * Copyright (c) 2018 Charlie Gordon
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdarg.h>
+#include <string.h>
+
+#include "cutils.h"
+
+void pstrcpy(char *buf, int buf_size, const char *str)
+{
+ int c;
+ char *q = buf;
+
+ if (buf_size <= 0)
+ return;
+
+ for(;;) {
+ c = *str++;
+ if (c == 0 || q >= buf + buf_size - 1)
+ break;
+ *q++ = c;
+ }
+ *q = '\0';
+}
+
+/* strcat and truncate. */
+char *pstrcat(char *buf, int buf_size, const char *s)
+{
+ int len;
+ len = strlen(buf);
+ if (len < buf_size)
+ pstrcpy(buf + len, buf_size - len, s);
+ return buf;
+}
+
+int strstart(const char *str, const char *val, const char **ptr)
+{
+ const char *p, *q;
+ p = str;
+ q = val;
+ while (*q != '\0') {
+ if (*p != *q)
+ return 0;
+ p++;
+ q++;
+ }
+ if (ptr)
+ *ptr = p;
+ return 1;
+}
+
+int has_suffix(const char *str, const char *suffix)
+{
+ size_t len = strlen(str);
+ size_t slen = strlen(suffix);
+ return (len >= slen && !memcmp(str + len - slen, suffix, slen));
+}
+
+/* Dynamic buffer package */
+
+static void *dbuf_default_realloc(void *opaque, void *ptr, size_t size)
+{
+ return realloc(ptr, size);
+}
+
+void dbuf_init2(DynBuf *s, void *opaque, DynBufReallocFunc *realloc_func)
+{
+ memset(s, 0, sizeof(*s));
+ if (!realloc_func)
+ realloc_func = dbuf_default_realloc;
+ s->opaque = opaque;
+ s->realloc_func = realloc_func;
+}
+
+void dbuf_init(DynBuf *s)
+{
+ dbuf_init2(s, NULL, NULL);
+}
+
+/* return < 0 if error */
+int dbuf_realloc(DynBuf *s, size_t new_size)
+{
+ size_t size;
+ uint8_t *new_buf;
+ if (new_size > s->allocated_size) {
+ if (s->error)
+ return -1;
+ size = s->allocated_size * 3 / 2;
+ if (size > new_size)
+ new_size = size;
+ new_buf = s->realloc_func(s->opaque, s->buf, new_size);
+ if (!new_buf) {
+ s->error = TRUE;
+ return -1;
+ }
+ s->buf = new_buf;
+ s->allocated_size = new_size;
+ }
+ return 0;
+}
+
+int dbuf_write(DynBuf *s, size_t offset, const uint8_t *data, size_t len)
+{
+ size_t end;
+ end = offset + len;
+ if (dbuf_realloc(s, end))
+ return -1;
+ memcpy(s->buf + offset, data, len);
+ if (end > s->size)
+ s->size = end;
+ return 0;
+}
+
+int dbuf_put(DynBuf *s, const uint8_t *data, size_t len)
+{
+ if (unlikely((s->size + len) > s->allocated_size)) {
+ if (dbuf_realloc(s, s->size + len))
+ return -1;
+ }
+ memcpy_no_ub(s->buf + s->size, data, len);
+ s->size += len;
+ return 0;
+}
+
+int dbuf_put_self(DynBuf *s, size_t offset, size_t len)
+{
+ if (unlikely((s->size + len) > s->allocated_size)) {
+ if (dbuf_realloc(s, s->size + len))
+ return -1;
+ }
+ memcpy(s->buf + s->size, s->buf + offset, len);
+ s->size += len;
+ return 0;
+}
+
+int dbuf_putc(DynBuf *s, uint8_t c)
+{
+ return dbuf_put(s, &c, 1);
+}
+
+int dbuf_putstr(DynBuf *s, const char *str)
+{
+ return dbuf_put(s, (const uint8_t *)str, strlen(str));
+}
+
+int FORMAT_ATTR(2, 3) dbuf_printf(DynBuf *s, const char *fmt, ...)
+{
+ va_list ap;
+ char buf[128];
+ int len;
+
+ va_start(ap, fmt);
+ len = vsnprintf(buf, sizeof(buf), fmt, ap);
+ va_end(ap);
+ if (len < sizeof(buf)) {
+ /* fast case */
+ return dbuf_put(s, (uint8_t *)buf, len);
+ } else {
+ if (dbuf_realloc(s, s->size + len + 1))
+ return -1;
+ va_start(ap, fmt);
+ vsnprintf((char *)(s->buf + s->size), s->allocated_size - s->size,
+ fmt, ap);
+ va_end(ap);
+ s->size += len;
+ }
+ return 0;
+}
+
+void dbuf_free(DynBuf *s)
+{
+ /* we test s->buf as a fail safe to avoid crashing if dbuf_free()
+ is called twice */
+ if (s->buf) {
+ s->realloc_func(s->opaque, s->buf, 0);
+ }
+ memset(s, 0, sizeof(*s));
+}
+
+/* Note: at most 31 bits are encoded. At most UTF8_CHAR_LEN_MAX bytes
+ are output. */
+int unicode_to_utf8(uint8_t *buf, unsigned int c)
+{
+ uint8_t *q = buf;
+
+ if (c < 0x80) {
+ *q++ = c;
+ } else {
+ if (c < 0x800) {
+ *q++ = (c >> 6) | 0xc0;
+ } else {
+ if (c < 0x10000) {
+ *q++ = (c >> 12) | 0xe0;
+ } else {
+ if (c < 0x00200000) {
+ *q++ = (c >> 18) | 0xf0;
+ } else {
+ if (c < 0x04000000) {
+ *q++ = (c >> 24) | 0xf8;
+ } else if (c < 0x80000000) {
+ *q++ = (c >> 30) | 0xfc;
+ *q++ = ((c >> 24) & 0x3f) | 0x80;
+ } else {
+ return 0;
+ }
+ *q++ = ((c >> 18) & 0x3f) | 0x80;
+ }
+ *q++ = ((c >> 12) & 0x3f) | 0x80;
+ }
+ *q++ = ((c >> 6) & 0x3f) | 0x80;
+ }
+ *q++ = (c & 0x3f) | 0x80;
+ }
+ return q - buf;
+}
+
+static const unsigned int utf8_min_code[5] = {
+ 0x80, 0x800, 0x10000, 0x00200000, 0x04000000,
+};
+
+static const unsigned char utf8_first_code_mask[5] = {
+ 0x1f, 0xf, 0x7, 0x3, 0x1,
+};
+
+/* return -1 if error. *pp is not updated in this case. max_len must
+ be >= 1. The maximum length for a UTF8 byte sequence is 6 bytes. */
+int unicode_from_utf8(const uint8_t *p, int max_len, const uint8_t **pp)
+{
+ int l, c, b, i;
+
+ c = *p++;
+ if (c < 0x80) {
+ *pp = p;
+ return c;
+ }
+ switch(c) {
+ case 0xc0: case 0xc1: case 0xc2: case 0xc3:
+ case 0xc4: case 0xc5: case 0xc6: case 0xc7:
+ case 0xc8: case 0xc9: case 0xca: case 0xcb:
+ case 0xcc: case 0xcd: case 0xce: case 0xcf:
+ case 0xd0: case 0xd1: case 0xd2: case 0xd3:
+ case 0xd4: case 0xd5: case 0xd6: case 0xd7:
+ case 0xd8: case 0xd9: case 0xda: case 0xdb:
+ case 0xdc: case 0xdd: case 0xde: case 0xdf:
+ l = 1;
+ break;
+ case 0xe0: case 0xe1: case 0xe2: case 0xe3:
+ case 0xe4: case 0xe5: case 0xe6: case 0xe7:
+ case 0xe8: case 0xe9: case 0xea: case 0xeb:
+ case 0xec: case 0xed: case 0xee: case 0xef:
+ l = 2;
+ break;
+ case 0xf0: case 0xf1: case 0xf2: case 0xf3:
+ case 0xf4: case 0xf5: case 0xf6: case 0xf7:
+ l = 3;
+ break;
+ case 0xf8: case 0xf9: case 0xfa: case 0xfb:
+ l = 4;
+ break;
+ case 0xfc: case 0xfd:
+ l = 5;
+ break;
+ default:
+ return -1;
+ }
+ /* check that we have enough characters */
+ if (l > (max_len - 1))
+ return -1;
+ c &= utf8_first_code_mask[l - 1];
+ for(i = 0; i < l; i++) {
+ b = *p++;
+ if (b < 0x80 || b >= 0xc0)
+ return -1;
+ c = (c << 6) | (b & 0x3f);
+ }
+ if (c < utf8_min_code[l - 1])
+ return -1;
+ *pp = p;
+ return c;
+}
+
+#if 0
+
+#if defined(EMSCRIPTEN) || defined(__ANDROID__)
+
+static void *rqsort_arg;
+static int (*rqsort_cmp)(const void *, const void *, void *);
+
+static int rqsort_cmp2(const void *p1, const void *p2)
+{
+ return rqsort_cmp(p1, p2, rqsort_arg);
+}
+
+/* not reentrant, but not needed with emscripten */
+void rqsort(void *base, size_t nmemb, size_t size,
+ int (*cmp)(const void *, const void *, void *),
+ void *arg)
+{
+ rqsort_arg = arg;
+ rqsort_cmp = cmp;
+ qsort(base, nmemb, size, rqsort_cmp2);
+}
+
+#endif
+
+#else
+
+typedef void (*exchange_f)(void *a, void *b, size_t size);
+typedef int (*cmp_f)(const void *, const void *, void *opaque);
+
+static void exchange_bytes(void *a, void *b, size_t size) {
+ uint8_t *ap = (uint8_t *)a;
+ uint8_t *bp = (uint8_t *)b;
+
+ while (size-- != 0) {
+ uint8_t t = *ap;
+ *ap++ = *bp;
+ *bp++ = t;
+ }
+}
+
+static void exchange_one_byte(void *a, void *b, size_t size) {
+ uint8_t *ap = (uint8_t *)a;
+ uint8_t *bp = (uint8_t *)b;
+ uint8_t t = *ap;
+ *ap = *bp;
+ *bp = t;
+}
+
+static void exchange_int16s(void *a, void *b, size_t size) {
+ uint16_t *ap = (uint16_t *)a;
+ uint16_t *bp = (uint16_t *)b;
+
+ for (size /= sizeof(uint16_t); size-- != 0;) {
+ uint16_t t = *ap;
+ *ap++ = *bp;
+ *bp++ = t;
+ }
+}
+
+static void exchange_one_int16(void *a, void *b, size_t size) {
+ uint16_t *ap = (uint16_t *)a;
+ uint16_t *bp = (uint16_t *)b;
+ uint16_t t = *ap;
+ *ap = *bp;
+ *bp = t;
+}
+
+static void exchange_int32s(void *a, void *b, size_t size) {
+ uint32_t *ap = (uint32_t *)a;
+ uint32_t *bp = (uint32_t *)b;
+
+ for (size /= sizeof(uint32_t); size-- != 0;) {
+ uint32_t t = *ap;
+ *ap++ = *bp;
+ *bp++ = t;
+ }
+}
+
+static void exchange_one_int32(void *a, void *b, size_t size) {
+ uint32_t *ap = (uint32_t *)a;
+ uint32_t *bp = (uint32_t *)b;
+ uint32_t t = *ap;
+ *ap = *bp;
+ *bp = t;
+}
+
+static void exchange_int64s(void *a, void *b, size_t size) {
+ uint64_t *ap = (uint64_t *)a;
+ uint64_t *bp = (uint64_t *)b;
+
+ for (size /= sizeof(uint64_t); size-- != 0;) {
+ uint64_t t = *ap;
+ *ap++ = *bp;
+ *bp++ = t;
+ }
+}
+
+static void exchange_one_int64(void *a, void *b, size_t size) {
+ uint64_t *ap = (uint64_t *)a;
+ uint64_t *bp = (uint64_t *)b;
+ uint64_t t = *ap;
+ *ap = *bp;
+ *bp = t;
+}
+
+static void exchange_int128s(void *a, void *b, size_t size) {
+ uint64_t *ap = (uint64_t *)a;
+ uint64_t *bp = (uint64_t *)b;
+
+ for (size /= sizeof(uint64_t) * 2; size-- != 0; ap += 2, bp += 2) {
+ uint64_t t = ap[0];
+ uint64_t u = ap[1];
+ ap[0] = bp[0];
+ ap[1] = bp[1];
+ bp[0] = t;
+ bp[1] = u;
+ }
+}
+
+static void exchange_one_int128(void *a, void *b, size_t size) {
+ uint64_t *ap = (uint64_t *)a;
+ uint64_t *bp = (uint64_t *)b;
+ uint64_t t = ap[0];
+ uint64_t u = ap[1];
+ ap[0] = bp[0];
+ ap[1] = bp[1];
+ bp[0] = t;
+ bp[1] = u;
+}
+
+static inline exchange_f exchange_func(const void *base, size_t size) {
+ switch (((uintptr_t)base | (uintptr_t)size) & 15) {
+ case 0:
+ if (size == sizeof(uint64_t) * 2)
+ return exchange_one_int128;
+ else
+ return exchange_int128s;
+ case 8:
+ if (size == sizeof(uint64_t))
+ return exchange_one_int64;
+ else
+ return exchange_int64s;
+ case 4:
+ case 12:
+ if (size == sizeof(uint32_t))
+ return exchange_one_int32;
+ else
+ return exchange_int32s;
+ case 2:
+ case 6:
+ case 10:
+ case 14:
+ if (size == sizeof(uint16_t))
+ return exchange_one_int16;
+ else
+ return exchange_int16s;
+ default:
+ if (size == 1)
+ return exchange_one_byte;
+ else
+ return exchange_bytes;
+ }
+}
+
+static void heapsortx(void *base, size_t nmemb, size_t size, cmp_f cmp, void *opaque)
+{
+ uint8_t *basep = (uint8_t *)base;
+ size_t i, n, c, r;
+ exchange_f swap = exchange_func(base, size);
+
+ if (nmemb > 1) {
+ i = (nmemb / 2) * size;
+ n = nmemb * size;
+
+ while (i > 0) {
+ i -= size;
+ for (r = i; (c = r * 2 + size) < n; r = c) {
+ if (c < n - size && cmp(basep + c, basep + c + size, opaque) <= 0)
+ c += size;
+ if (cmp(basep + r, basep + c, opaque) > 0)
+ break;
+ swap(basep + r, basep + c, size);
+ }
+ }
+ for (i = n - size; i > 0; i -= size) {
+ swap(basep, basep + i, size);
+
+ for (r = 0; (c = r * 2 + size) < i; r = c) {
+ if (c < i - size && cmp(basep + c, basep + c + size, opaque) <= 0)
+ c += size;
+ if (cmp(basep + r, basep + c, opaque) > 0)
+ break;
+ swap(basep + r, basep + c, size);
+ }
+ }
+ }
+}
+
+static inline void *med3(void *a, void *b, void *c, cmp_f cmp, void *opaque)
+{
+ return cmp(a, b, opaque) < 0 ?
+ (cmp(b, c, opaque) < 0 ? b : (cmp(a, c, opaque) < 0 ? c : a )) :
+ (cmp(b, c, opaque) > 0 ? b : (cmp(a, c, opaque) < 0 ? a : c ));
+}
+
+/* pointer based version with local stack and insertion sort threshhold */
+void rqsort(void *base, size_t nmemb, size_t size, cmp_f cmp, void *opaque)
+{
+ struct { uint8_t *base; size_t count; int depth; } stack[50], *sp = stack;
+ uint8_t *ptr, *pi, *pj, *plt, *pgt, *top, *m;
+ size_t m4, i, lt, gt, span, span2;
+ int c, depth;
+ exchange_f swap = exchange_func(base, size);
+ exchange_f swap_block = exchange_func(base, size | 128);
+
+ if (nmemb < 2 || size <= 0)
+ return;
+
+ sp->base = (uint8_t *)base;
+ sp->count = nmemb;
+ sp->depth = 0;
+ sp++;
+
+ while (sp > stack) {
+ sp--;
+ ptr = sp->base;
+ nmemb = sp->count;
+ depth = sp->depth;
+
+ while (nmemb > 6) {
+ if (++depth > 50) {
+ /* depth check to ensure worst case logarithmic time */
+ heapsortx(ptr, nmemb, size, cmp, opaque);
+ nmemb = 0;
+ break;
+ }
+ /* select median of 3 from 1/4, 1/2, 3/4 positions */
+ /* should use median of 5 or 9? */
+ m4 = (nmemb >> 2) * size;
+ m = med3(ptr + m4, ptr + 2 * m4, ptr + 3 * m4, cmp, opaque);
+ swap(ptr, m, size); /* move the pivot to the start or the array */
+ i = lt = 1;
+ pi = plt = ptr + size;
+ gt = nmemb;
+ pj = pgt = top = ptr + nmemb * size;
+ for (;;) {
+ while (pi < pj && (c = cmp(ptr, pi, opaque)) >= 0) {
+ if (c == 0) {
+ swap(plt, pi, size);
+ lt++;
+ plt += size;
+ }
+ i++;
+ pi += size;
+ }
+ while (pi < (pj -= size) && (c = cmp(ptr, pj, opaque)) <= 0) {
+ if (c == 0) {
+ gt--;
+ pgt -= size;
+ swap(pgt, pj, size);
+ }
+ }
+ if (pi >= pj)
+ break;
+ swap(pi, pj, size);
+ i++;
+ pi += size;
+ }
+ /* array has 4 parts:
+ * from 0 to lt excluded: elements identical to pivot
+ * from lt to pi excluded: elements smaller than pivot
+ * from pi to gt excluded: elements greater than pivot
+ * from gt to n excluded: elements identical to pivot
+ */
+ /* move elements identical to pivot in the middle of the array: */
+ /* swap values in ranges [0..lt[ and [i-lt..i[
+ swapping the smallest span between lt and i-lt is sufficient
+ */
+ span = plt - ptr;
+ span2 = pi - plt;
+ lt = i - lt;
+ if (span > span2)
+ span = span2;
+ swap_block(ptr, pi - span, span);
+ /* swap values in ranges [gt..top[ and [i..top-(top-gt)[
+ swapping the smallest span between top-gt and gt-i is sufficient
+ */
+ span = top - pgt;
+ span2 = pgt - pi;
+ pgt = top - span2;
+ gt = nmemb - (gt - i);
+ if (span > span2)
+ span = span2;
+ swap_block(pi, top - span, span);
+
+ /* now array has 3 parts:
+ * from 0 to lt excluded: elements smaller than pivot
+ * from lt to gt excluded: elements identical to pivot
+ * from gt to n excluded: elements greater than pivot
+ */
+ /* stack the larger segment and keep processing the smaller one
+ to minimize stack use for pathological distributions */
+ if (lt > nmemb - gt) {
+ sp->base = ptr;
+ sp->count = lt;
+ sp->depth = depth;
+ sp++;
+ ptr = pgt;
+ nmemb -= gt;
+ } else {
+ sp->base = pgt;
+ sp->count = nmemb - gt;
+ sp->depth = depth;
+ sp++;
+ nmemb = lt;
+ }
+ }
+ /* Use insertion sort for small fragments */
+ for (pi = ptr + size, top = ptr + nmemb * size; pi < top; pi += size) {
+ for (pj = pi; pj > ptr && cmp(pj - size, pj, opaque) > 0; pj -= size)
+ swap(pj, pj - size, size);
+ }
+ }
+}
+
+#endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-28 20:04:12 +0000