| /* |
| * 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; |
| } |
| |
| // FIXME: It would be preferable to instead apply fixes to the source of |
| // whatever passes a null pointer or zero length, but there are many |
| // instances this function and used and different call paths can lead to |
| // this. |
| if (!data || !len) |
| return 0; |
| |
| memcpy(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 __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 < 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 |
