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