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