/src/quickjs/cutils.c

Source
/*
 * 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);
}

/* Try to allocate 'len' more bytes. return < 0 if error */
int dbuf_claim(DynBuf *s, size_t len)
{
    size_t new_size, size;
    uint8_t *new_buf;
    new_size = s->size + len;
    if (new_size < len)
        return -1; /* overflow case */
    if (new_size > s->allocated_size) {
        if (s->error)
            return -1;
        size = s->allocated_size + (s->allocated_size / 2);
        if (size < s->allocated_size)
            return -1; /* overflow case */
        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_put(DynBuf *s, const uint8_t *data, size_t len)
{
    if (unlikely((s->allocated_size - s->size) < len)) {
        if (dbuf_claim(s, 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->allocated_size - s->size) < len)) {
        if (dbuf_claim(s, 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_put_u16(DynBuf *s, uint16_t val)
{
    return dbuf_put(s, (uint8_t *)&val, 2);
}

int __dbuf_put_u32(DynBuf *s, uint32_t val)
{
    return dbuf_put(s, (uint8_t *)&val, 4);
}

int __dbuf_put_u64(DynBuf *s, uint64_t val)
{
    return dbuf_put(s, (uint8_t *)&val, 8);
}

int dbuf_putstr(DynBuf *s, const char *str)
{
    return dbuf_put(s, (const uint8_t *)str, strlen(str));
}

int __attribute__((format(printf, 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 < 0)
        return -1;
    if (len < sizeof(buf)) {
        /* fast case */
        return dbuf_put(s, (uint8_t *)buf, len);
    } else {
        if (dbuf_claim(s, 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

Coverage Report

Created: 2025-11-09 06:54

Line	Count	Source
1		/*
2		* C utilities
3		*
4		* Copyright (c) 2017 Fabrice Bellard
5		* Copyright (c) 2018 Charlie Gordon
6		*
7		* Permission is hereby granted, free of charge, to any person obtaining a copy
8		* of this software and associated documentation files (the "Software"), to deal
9		* in the Software without restriction, including without limitation the rights
10		* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11		* copies of the Software, and to permit persons to whom the Software is
12		* furnished to do so, subject to the following conditions:
13		*
14		* The above copyright notice and this permission notice shall be included in
15		* all copies or substantial portions of the Software.
16		*
17		* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18		* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19		* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
20		* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21		* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22		* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23		* THE SOFTWARE.
24		*/
25		#include <stdlib.h>
26		#include <stdio.h>
27		#include <stdarg.h>
28		#include <string.h>
29
30		#include "cutils.h"
31
32		void pstrcpy(char buf, int buf_size, const char str)
33	4.11k	{
34	4.11k	int c;
35	4.11k	char *q = buf;
36
37	4.11k	if (buf_size <= 0)
38	0	return;
39
40	68.7k	for(;;) {
41	68.7k	c = *str++;
42	68.7k	if (c == 0 \|\| q >= buf + buf_size - 1)
43	4.11k	break;
44	64.6k	*q++ = c;
45	64.6k	}
46	4.11k	*q = '\0';
47	4.11k	}
48
49		/* strcat and truncate. */
50		char pstrcat(char buf, int buf_size, const char *s)
51	435	{
52	435	int len;
53	435	len = strlen(buf);
54	435	if (len < buf_size)
55	435	pstrcpy(buf + len, buf_size - len, s);
56	435	return buf;
57	435	}
58
59		int strstart(const char str, const char val, const char **ptr)
60	2.68M	{
61	2.68M	const char p, q;
62	2.68M	p = str;
63	2.68M	q = val;
64	2.68M	while (*q != '\0') {
65	2.68M	if (p != q)
66	2.68M	return 0;
67	0	p++;
68	0	q++;
69	0	}
70	0	if (ptr)
71	0	*ptr = p;
72	0	return 1;
73	2.68M	}
74
75		int has_suffix(const char str, const char suffix)
76	2.29M	{
77	2.29M	size_t len = strlen(str);
78	2.29M	size_t slen = strlen(suffix);
79	2.29M	return (len >= slen && !memcmp(str + len - slen, suffix, slen));
80	2.29M	}
81
82		/* Dynamic buffer package */
83
84		static void dbuf_default_realloc(void opaque, void *ptr, size_t size)
85	0	{
86	0	return realloc(ptr, size);
87	0	}
88
89		void dbuf_init2(DynBuf s, void opaque, DynBufReallocFunc *realloc_func)
90	8.87M	{
91	8.87M	memset(s, 0, sizeof(*s));
92	8.87M	if (!realloc_func)
93	0	realloc_func = dbuf_default_realloc;
94	8.87M	s->opaque = opaque;
95	8.87M	s->realloc_func = realloc_func;
96	8.87M	}
97
98		void dbuf_init(DynBuf *s)
99	0	{
100	0	dbuf_init2(s, NULL, NULL);
101	0	}
102
103		/* Try to allocate 'len' more bytes. return < 0 if error */
104		int dbuf_claim(DynBuf *s, size_t len)
105	25.6M	{
106	25.6M	size_t new_size, size;
107	25.6M	uint8_t *new_buf;
108	25.6M	new_size = s->size + len;
109	25.6M	if (new_size < len)
110	0	return -1; /* overflow case */
111	25.6M	if (new_size > s->allocated_size) {
112	24.5M	if (s->error)
113	28.0k	return -1;
114	24.5M	size = s->allocated_size + (s->allocated_size / 2);
115	24.5M	if (size < s->allocated_size)
116	0	return -1; /* overflow case */
117	24.5M	if (size > new_size)
118	9.95M	new_size = size;
119	24.5M	new_buf = s->realloc_func(s->opaque, s->buf, new_size);
120	24.5M	if (!new_buf) {
121	156	s->error = TRUE;
122	156	return -1;
123	156	}
124	24.5M	s->buf = new_buf;
125	24.5M	s->allocated_size = new_size;
126	24.5M	}
127	25.5M	return 0;
128	25.6M	}
129
130		int dbuf_put(DynBuf s, const uint8_t data, size_t len)
131	47.5M	{
132	47.5M	if (unlikely((s->allocated_size - s->size) < len)) {
133	24.5M	if (dbuf_claim(s, len))
134	28.1k	return -1;
135	24.5M	}
136	47.5M	memcpy_no_ub(s->buf + s->size, data, len);
137	47.5M	s->size += len;
138	47.5M	return 0;
139	47.5M	}
140
141		int dbuf_put_self(DynBuf *s, size_t offset, size_t len)
142	18.8k	{
143	18.8k	if (unlikely((s->allocated_size - s->size) < len)) {
144	13.4k	if (dbuf_claim(s, len))
145	34	return -1;
146	13.4k	}
147	18.7k	memcpy(s->buf + s->size, s->buf + offset, len);
148	18.7k	s->size += len;
149	18.7k	return 0;
150	18.8k	}
151
152		int __dbuf_putc(DynBuf *s, uint8_t c)
153	7.90M	{
154	7.90M	return dbuf_put(s, &c, 1);
155	7.90M	}
156
157		int __dbuf_put_u16(DynBuf *s, uint16_t val)
158	2.52M	{
159	2.52M	return dbuf_put(s, (uint8_t *)&val, 2);
160	2.52M	}
161
162		int __dbuf_put_u32(DynBuf *s, uint32_t val)
163	1.21M	{
164	1.21M	return dbuf_put(s, (uint8_t *)&val, 4);
165	1.21M	}
166
167		int __dbuf_put_u64(DynBuf *s, uint64_t val)
168	0	{
169	0	return dbuf_put(s, (uint8_t *)&val, 8);
170	0	}
171
172		int dbuf_putstr(DynBuf s, const char str)
173	0	{
174	0	return dbuf_put(s, (const uint8_t *)str, strlen(str));
175	0	}
176
177		int __attribute__((format(printf, 2, 3))) dbuf_printf(DynBuf *s,
178		const char *fmt, ...)
179	10.0M	{
180	10.0M	va_list ap;
181	10.0M	char buf[128];
182	10.0M	int len;
183
184	10.0M	va_start(ap, fmt);
185	10.0M	len = vsnprintf(buf, sizeof(buf), fmt, ap);
186	10.0M	va_end(ap);
187	10.0M	if (len < 0)
188	0	return -1;
189	10.0M	if (len < sizeof(buf)) {
190		/* fast case */
191	10.0M	return dbuf_put(s, (uint8_t *)buf, len);
192	10.0M	} else {
193	0	if (dbuf_claim(s, len + 1))
194	0	return -1;
195	0	va_start(ap, fmt);
196	0	vsnprintf((char *)(s->buf + s->size), s->allocated_size - s->size,
197	0	fmt, ap);
198	0	va_end(ap);
199	0	s->size += len;
200	0	}
201	0	return 0;
202	10.0M	}
203
204		void dbuf_free(DynBuf *s)
205	6.71M	{
206		/* we test s->buf as a fail safe to avoid crashing if dbuf_free()
207		is called twice */
208	6.71M	if (s->buf) {
209	6.60M	s->realloc_func(s->opaque, s->buf, 0);
210	6.60M	}
211	6.71M	memset(s, 0, sizeof(*s));
212	6.71M	}
213
214		/* Note: at most 31 bits are encoded. At most UTF8_CHAR_LEN_MAX bytes
215		are output. */
216		int unicode_to_utf8(uint8_t *buf, unsigned int c)
217	22.7M	{
218	22.7M	uint8_t *q = buf;
219
220	22.7M	if (c < 0x80) {
221	0	*q++ = c;
222	22.7M	} else {
223	22.7M	if (c < 0x800) {
224	704k	*q++ = (c >> 6) \| 0xc0;
225	22.0M	} else {
226	22.0M	if (c < 0x10000) {
227	21.3M	*q++ = (c >> 12) \| 0xe0;
228	21.3M	} else {
229	685k	if (c < 0x00200000) {
230	685k	*q++ = (c >> 18) \| 0xf0;
231	685k	} else {
232	0	if (c < 0x04000000) {
233	0	*q++ = (c >> 24) \| 0xf8;
234	0	} else if (c < 0x80000000) {
235	0	*q++ = (c >> 30) \| 0xfc;
236	0	*q++ = ((c >> 24) & 0x3f) \| 0x80;
237	0	} else {
238	0	return 0;
239	0	}
240	0	*q++ = ((c >> 18) & 0x3f) \| 0x80;
241	0	}
242	685k	*q++ = ((c >> 12) & 0x3f) \| 0x80;
243	685k	}
244	22.0M	*q++ = ((c >> 6) & 0x3f) \| 0x80;
245	22.0M	}
246	22.7M	*q++ = (c & 0x3f) \| 0x80;
247	22.7M	}
248	22.7M	return q - buf;
249	22.7M	}
250
251		static const unsigned int utf8_min_code[5] = {
252		0x80, 0x800, 0x10000, 0x00200000, 0x04000000,
253		};
254
255		static const unsigned char utf8_first_code_mask[5] = {
256		0x1f, 0xf, 0x7, 0x3, 0x1,
257		};
258
259		/* return -1 if error. *pp is not updated in this case. max_len must
260		be >= 1. The maximum length for a UTF8 byte sequence is 6 bytes. */
261		int unicode_from_utf8(const uint8_t p, int max_len, const uint8_t *pp)
262	30.6M	{
263	30.6M	int l, c, b, i;
264
265	30.6M	c = *p++;
266	30.6M	if (c < 0x80) {
267	1.13M	*pp = p;
268	1.13M	return c;
269	1.13M	}
270	29.5M	switch(c) {
271	184k	case 0xc0: case 0xc1: case 0xc2: case 0xc3:
272	902k	case 0xc4: case 0xc5: case 0xc6: case 0xc7:
273	1.39M	case 0xc8: case 0xc9: case 0xca: case 0xcb:
274	1.50M	case 0xcc: case 0xcd: case 0xce: case 0xcf:
275	1.88M	case 0xd0: case 0xd1: case 0xd2: case 0xd3:
276	2.03M	case 0xd4: case 0xd5: case 0xd6: case 0xd7:
277	3.28M	case 0xd8: case 0xd9: case 0xda: case 0xdb:
278	17.5M	case 0xdc: case 0xdd: case 0xde: case 0xdf:
279	17.5M	l = 1;
280	17.5M	break;
281	279k	case 0xe0: case 0xe1: case 0xe2: case 0xe3:
282	324k	case 0xe4: case 0xe5: case 0xe6: case 0xe7:
283	543k	case 0xe8: case 0xe9: case 0xea: case 0xeb:
284	997k	case 0xec: case 0xed: case 0xee: case 0xef:
285	997k	l = 2;
286	997k	break;
287	169k	case 0xf0: case 0xf1: case 0xf2: case 0xf3:
288	233k	case 0xf4: case 0xf5: case 0xf6: case 0xf7:
289	233k	l = 3;
290	233k	break;
291	1.41M	case 0xf8: case 0xf9: case 0xfa: case 0xfb:
292	1.41M	l = 4;
293	1.41M	break;
294	4.80M	case 0xfc: case 0xfd:
295	4.80M	l = 5;
296	4.80M	break;
297	4.58M	default:
298	4.58M	return -1;
299	29.5M	}
300		/* check that we have enough characters */
301	24.9M	if (l > (max_len - 1))
302	0	return -1;
303	24.9M	c &= utf8_first_code_mask[l - 1];
304	26.5M	for(i = 0; i < l; i++) {
305	25.6M	b = *p++;
306	25.6M	if (b < 0x80 \|\| b >= 0xc0)
307	24.0M	return -1;
308	1.59M	c = (c << 6) \| (b & 0x3f);
309	1.59M	}
310	858k	if (c < utf8_min_code[l - 1])
311	1.06k	return -1;
312	857k	*pp = p;
313	857k	return c;
314	858k	}
315
316		#if 0
317
318		#if defined(EMSCRIPTEN) \|\| defined(__ANDROID__)
319
320		static void *rqsort_arg;
321		static int (rqsort_cmp)(const void , const void , void );
322
323		static int rqsort_cmp2(const void p1, const void p2)
324		{
325		return rqsort_cmp(p1, p2, rqsort_arg);
326		}
327
328		/* not reentrant, but not needed with emscripten */
329		void rqsort(void *base, size_t nmemb, size_t size,
330		int (cmp)(const void , const void , void ),
331		void *arg)
332		{
333		rqsort_arg = arg;
334		rqsort_cmp = cmp;
335		qsort(base, nmemb, size, rqsort_cmp2);
336		}
337
338		#endif
339
340		#else
341
342		typedef void (exchange_f)(void a, void *b, size_t size);
343		typedef int (cmp_f)(const void , const void , void opaque);
344
345	0	static void exchange_bytes(void a, void b, size_t size) {
346	0	uint8_t ap = (uint8_t )a;
347	0	uint8_t bp = (uint8_t )b;
348
349	0	while (size-- != 0) {
350	0	uint8_t t = *ap;
351	0	ap++ = bp;
352	0	*bp++ = t;
353	0	}
354	0	}
355
356	0	static void exchange_one_byte(void a, void b, size_t size) {
357	0	uint8_t ap = (uint8_t )a;
358	0	uint8_t bp = (uint8_t )b;
359	0	uint8_t t = *ap;
360	0	ap = bp;
361	0	*bp = t;
362	0	}
363
364	0	static void exchange_int16s(void a, void b, size_t size) {
365	0	uint16_t ap = (uint16_t )a;
366	0	uint16_t bp = (uint16_t )b;
367
368	0	for (size /= sizeof(uint16_t); size-- != 0;) {
369	0	uint16_t t = *ap;
370	0	ap++ = bp;
371	0	*bp++ = t;
372	0	}
373	0	}
374
375	0	static void exchange_one_int16(void a, void b, size_t size) {
376	0	uint16_t ap = (uint16_t )a;
377	0	uint16_t bp = (uint16_t )b;
378	0	uint16_t t = *ap;
379	0	ap = bp;
380	0	*bp = t;
381	0	}
382
383	0	static void exchange_int32s(void a, void b, size_t size) {
384	0	uint32_t ap = (uint32_t )a;
385	0	uint32_t bp = (uint32_t )b;
386
387	0	for (size /= sizeof(uint32_t); size-- != 0;) {
388	0	uint32_t t = *ap;
389	0	ap++ = bp;
390	0	*bp++ = t;
391	0	}
392	0	}
393
394	0	static void exchange_one_int32(void a, void b, size_t size) {
395	0	uint32_t ap = (uint32_t )a;
396	0	uint32_t bp = (uint32_t )b;
397	0	uint32_t t = *ap;
398	0	ap = bp;
399	0	*bp = t;
400	0	}
401
402	394k	static void exchange_int64s(void a, void b, size_t size) {
403	394k	uint64_t ap = (uint64_t )a;
404	394k	uint64_t bp = (uint64_t )b;
405
406	597k	for (size /= sizeof(uint64_t); size-- != 0;) {
407	203k	uint64_t t = *ap;
408	203k	ap++ = bp;
409	203k	*bp++ = t;
410	203k	}
411	394k	}
412
413	1.70M	static void exchange_one_int64(void a, void b, size_t size) {
414	1.70M	uint64_t ap = (uint64_t )a;
415	1.70M	uint64_t bp = (uint64_t )b;
416	1.70M	uint64_t t = *ap;
417	1.70M	ap = bp;
418	1.70M	*bp = t;
419	1.70M	}
420
421	20.7k	static void exchange_int128s(void a, void b, size_t size) {
422	20.7k	uint64_t ap = (uint64_t )a;
423	20.7k	uint64_t bp = (uint64_t )b;
424
425	31.1k	for (size /= sizeof(uint64_t) * 2; size-- != 0; ap += 2, bp += 2) {
426	10.3k	uint64_t t = ap[0];
427	10.3k	uint64_t u = ap[1];
428	10.3k	ap[0] = bp[0];
429	10.3k	ap[1] = bp[1];
430	10.3k	bp[0] = t;
431	10.3k	bp[1] = u;
432	10.3k	}
433	20.7k	}
434
435	83.5k	static void exchange_one_int128(void a, void b, size_t size) {
436	83.5k	uint64_t ap = (uint64_t )a;
437	83.5k	uint64_t bp = (uint64_t )b;
438	83.5k	uint64_t t = ap[0];
439	83.5k	uint64_t u = ap[1];
440	83.5k	ap[0] = bp[0];
441	83.5k	ap[1] = bp[1];
442	83.5k	bp[0] = t;
443	83.5k	bp[1] = u;
444	83.5k	}
445
446	25.7k	static inline exchange_f exchange_func(const void *base, size_t size) {
447	25.7k	switch (((uintptr_t)base \| (uintptr_t)size) & 15) {
448	2.30k	case 0:
449	2.30k	if (size == sizeof(uint64_t) * 2)
450	1.15k	return exchange_one_int128;
451	1.15k	else
452	1.15k	return exchange_int128s;
453	23.4k	case 8:
454	23.4k	if (size == sizeof(uint64_t))
455	11.7k	return exchange_one_int64;
456	11.7k	else
457	11.7k	return exchange_int64s;
458	0	case 4:
459	0	case 12:
460	0	if (size == sizeof(uint32_t))
461	0	return exchange_one_int32;
462	0	else
463	0	return exchange_int32s;
464	0	case 2:
465	0	case 6:
466	0	case 10:
467	0	case 14:
468	0	if (size == sizeof(uint16_t))
469	0	return exchange_one_int16;
470	0	else
471	0	return exchange_int16s;
472	0	default:
473	0	if (size == 1)
474	0	return exchange_one_byte;
475	0	else
476	0	return exchange_bytes;
477	25.7k	}
478	25.7k	}
479
480		static void heapsortx(void base, size_t nmemb, size_t size, cmp_f cmp, void opaque)
481	0	{
482	0	uint8_t basep = (uint8_t )base;
483	0	size_t i, n, c, r;
484	0	exchange_f swap = exchange_func(base, size);
485
486	0	if (nmemb > 1) {
487	0	i = (nmemb / 2) * size;
488	0	n = nmemb * size;
489
490	0	while (i > 0) {
491	0	i -= size;
492	0	for (r = i; (c = r * 2 + size) < n; r = c) {
493	0	if (c < n - size && cmp(basep + c, basep + c + size, opaque) <= 0)
494	0	c += size;
495	0	if (cmp(basep + r, basep + c, opaque) > 0)
496	0	break;
497	0	swap(basep + r, basep + c, size);
498	0	}
499	0	}
500	0	for (i = n - size; i > 0; i -= size) {
501	0	swap(basep, basep + i, size);
502
503	0	for (r = 0; (c = r * 2 + size) < i; r = c) {
504	0	if (c < i - size && cmp(basep + c, basep + c + size, opaque) <= 0)
505	0	c += size;
506	0	if (cmp(basep + r, basep + c, opaque) > 0)
507	0	break;
508	0	swap(basep + r, basep + c, size);
509	0	}
510	0	}
511	0	}
512	0	}
513
514		static inline void med3(void a, void b, void c, cmp_f cmp, void *opaque)
515	207k	{
516	207k	return cmp(a, b, opaque) < 0 ?
517	111k	(cmp(b, c, opaque) < 0 ? b : (cmp(a, c, opaque) < 0 ? c : a )) :
518	207k	(cmp(b, c, opaque) > 0 ? b : (cmp(a, c, opaque) < 0 ? a : c ));
519	207k	}
520
521		/* pointer based version with local stack and insertion sort threshhold */
522		void rqsort(void base, size_t nmemb, size_t size, cmp_f cmp, void opaque)
523	12.8k	{
524	12.8k	struct { uint8_t base; size_t count; int depth; } stack[50], sp = stack;
525	12.8k	uint8_t ptr, pi, pj, plt, pgt, top, *m;
526	12.8k	size_t m4, i, lt, gt, span, span2;
527	12.8k	int c, depth;
528	12.8k	exchange_f swap = exchange_func(base, size);
529	12.8k	exchange_f swap_block = exchange_func(base, size \| 128);
530
531	12.8k	if (nmemb < 2 \|\| size <= 0)
532	9.18k	return;
533
534	3.71k	sp->base = (uint8_t *)base;
535	3.71k	sp->count = nmemb;
536	3.71k	sp->depth = 0;
537	3.71k	sp++;
538
539	215k	while (sp > stack) {
540	211k	sp--;
541	211k	ptr = sp->base;
542	211k	nmemb = sp->count;
543	211k	depth = sp->depth;
544
545	418k	while (nmemb > 6) {
546	207k	if (++depth > 50) {
547		/* depth check to ensure worst case logarithmic time */
548	0	heapsortx(ptr, nmemb, size, cmp, opaque);
549	0	nmemb = 0;
550	0	break;
551	0	}
552		/* select median of 3 from 1/4, 1/2, 3/4 positions */
553		/* should use median of 5 or 9? */
554	207k	m4 = (nmemb >> 2) * size;
555	207k	m = med3(ptr + m4, ptr + 2 * m4, ptr + 3 * m4, cmp, opaque);
556	207k	swap(ptr, m, size); /* move the pivot to the start or the array */
557	207k	i = lt = 1;
558	207k	pi = plt = ptr + size;
559	207k	gt = nmemb;
560	207k	pj = pgt = top = ptr + nmemb * size;
561	1.22M	for (;;) {
562	3.48M	while (pi < pj && (c = cmp(ptr, pi, opaque)) >= 0) {
563	2.25M	if (c == 0) {
564	2.96k	swap(plt, pi, size);
565	2.96k	lt++;
566	2.96k	plt += size;
567	2.96k	}
568	2.25M	i++;
569	2.25M	pi += size;
570	2.25M	}
571	3.73M	while (pi < (pj -= size) && (c = cmp(ptr, pj, opaque)) <= 0) {
572	2.50M	if (c == 0) {
573	3.40k	gt--;
574	3.40k	pgt -= size;
575	3.40k	swap(pgt, pj, size);
576	3.40k	}
577	2.50M	}
578	1.22M	if (pi >= pj)
579	207k	break;
580	1.01M	swap(pi, pj, size);
581	1.01M	i++;
582	1.01M	pi += size;
583	1.01M	}
584		/* array has 4 parts:
585		* from 0 to lt excluded: elements identical to pivot
586		* from lt to pi excluded: elements smaller than pivot
587		* from pi to gt excluded: elements greater than pivot
588		* from gt to n excluded: elements identical to pivot
589		*/
590		/* move elements identical to pivot in the middle of the array: */
591		/* swap values in ranges [0..lt[ and [i-lt..i[
592		swapping the smallest span between lt and i-lt is sufficient
593		*/
594	207k	span = plt - ptr;
595	207k	span2 = pi - plt;
596	207k	lt = i - lt;
597	207k	if (span > span2)
598	286	span = span2;
599	207k	swap_block(ptr, pi - span, span);
600		/* swap values in ranges [gt..top[ and [i..top-(top-gt)[
601		swapping the smallest span between top-gt and gt-i is sufficient
602		*/
603	207k	span = top - pgt;
604	207k	span2 = pgt - pi;
605	207k	pgt = top - span2;
606	207k	gt = nmemb - (gt - i);
607	207k	if (span > span2)
608	0	span = span2;
609	207k	swap_block(pi, top - span, span);
610
611		/* now array has 3 parts:
612		* from 0 to lt excluded: elements smaller than pivot
613		* from lt to gt excluded: elements identical to pivot
614		* from gt to n excluded: elements greater than pivot
615		*/
616		/* stack the larger segment and keep processing the smaller one
617		to minimize stack use for pathological distributions */
618	207k	if (lt > nmemb - gt) {
619	84.4k	sp->base = ptr;
620	84.4k	sp->count = lt;
621	84.4k	sp->depth = depth;
622	84.4k	sp++;
623	84.4k	ptr = pgt;
624	84.4k	nmemb -= gt;
625	123k	} else {
626	123k	sp->base = pgt;
627	123k	sp->count = nmemb - gt;
628	123k	sp->depth = depth;
629	123k	sp++;
630	123k	nmemb = lt;
631	123k	}
632	207k	}
633		/* Use insertion sort for small fragments */
634	827k	for (pi = ptr + size, top = ptr + nmemb * size; pi < top; pi += size) {
635	1.17M	for (pj = pi; pj > ptr && cmp(pj - size, pj, opaque) > 0; pj -= size)
636	555k	swap(pj, pj - size, size);
637	616k	}
638	211k	}
639	3.71k	}
640
641		#endif