cutils.c (17798B)
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 { 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. */ 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 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 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 84 static void *dbuf_default_realloc(void *opaque, void *ptr, size_t size) 85 { 86 return realloc(ptr, size); 87 } 88 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 98 void dbuf_init(DynBuf *s) 99 { 100 dbuf_init2(s, NULL, NULL); 101 } 102 103 /* Try to allocate 'len' more bytes. return < 0 if error */ 104 int dbuf_claim(DynBuf *s, size_t len) 105 { 106 size_t new_size, size; 107 uint8_t *new_buf; 108 new_size = s->size + len; 109 if (new_size < len) 110 return -1; /* overflow case */ 111 if (new_size > s->allocated_size) { 112 if (s->error) 113 return -1; 114 size = s->allocated_size + (s->allocated_size / 2); 115 if (size < s->allocated_size) 116 return -1; /* overflow case */ 117 if (size > new_size) 118 new_size = size; 119 new_buf = s->realloc_func(s->opaque, s->buf, new_size); 120 if (!new_buf) { 121 s->error = TRUE; 122 return -1; 123 } 124 s->buf = new_buf; 125 s->allocated_size = new_size; 126 } 127 return 0; 128 } 129 130 int dbuf_put(DynBuf *s, const uint8_t *data, size_t len) 131 { 132 if (unlikely((s->allocated_size - s->size) < len)) { 133 if (dbuf_claim(s, len)) 134 return -1; 135 } 136 memcpy_no_ub(s->buf + s->size, data, len); 137 s->size += len; 138 return 0; 139 } 140 141 int dbuf_put_self(DynBuf *s, size_t offset, size_t len) 142 { 143 if (unlikely((s->allocated_size - s->size) < len)) { 144 if (dbuf_claim(s, len)) 145 return -1; 146 } 147 memcpy(s->buf + s->size, s->buf + offset, len); 148 s->size += len; 149 return 0; 150 } 151 152 int __dbuf_putc(DynBuf *s, uint8_t c) 153 { 154 return dbuf_put(s, &c, 1); 155 } 156 157 int __dbuf_put_u16(DynBuf *s, uint16_t val) 158 { 159 return dbuf_put(s, (uint8_t *)&val, 2); 160 } 161 162 int __dbuf_put_u32(DynBuf *s, uint32_t val) 163 { 164 return dbuf_put(s, (uint8_t *)&val, 4); 165 } 166 167 int __dbuf_put_u64(DynBuf *s, uint64_t val) 168 { 169 return dbuf_put(s, (uint8_t *)&val, 8); 170 } 171 172 int dbuf_putstr(DynBuf *s, const char *str) 173 { 174 return dbuf_put(s, (const uint8_t *)str, strlen(str)); 175 } 176 177 int __attribute__((format(printf, 2, 3))) dbuf_printf(DynBuf *s, 178 const char *fmt, ...) 179 { 180 va_list ap; 181 char buf[128]; 182 int len; 183 184 va_start(ap, fmt); 185 len = vsnprintf(buf, sizeof(buf), fmt, ap); 186 va_end(ap); 187 if (len < 0) 188 return -1; 189 if (len < sizeof(buf)) { 190 /* fast case */ 191 return dbuf_put(s, (uint8_t *)buf, len); 192 } else { 193 if (dbuf_claim(s, len + 1)) 194 return -1; 195 va_start(ap, fmt); 196 vsnprintf((char *)(s->buf + s->size), s->allocated_size - s->size, 197 fmt, ap); 198 va_end(ap); 199 s->size += len; 200 } 201 return 0; 202 } 203 204 void dbuf_free(DynBuf *s) 205 { 206 /* we test s->buf as a fail safe to avoid crashing if dbuf_free() 207 is called twice */ 208 if (s->buf) { 209 s->realloc_func(s->opaque, s->buf, 0); 210 } 211 memset(s, 0, sizeof(*s)); 212 } 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 { 218 uint8_t *q = buf; 219 220 if (c < 0x80) { 221 *q++ = c; 222 } else { 223 if (c < 0x800) { 224 *q++ = (c >> 6) | 0xc0; 225 } else { 226 if (c < 0x10000) { 227 *q++ = (c >> 12) | 0xe0; 228 } else { 229 if (c < 0x00200000) { 230 *q++ = (c >> 18) | 0xf0; 231 } else { 232 if (c < 0x04000000) { 233 *q++ = (c >> 24) | 0xf8; 234 } else if (c < 0x80000000) { 235 *q++ = (c >> 30) | 0xfc; 236 *q++ = ((c >> 24) & 0x3f) | 0x80; 237 } else { 238 return 0; 239 } 240 *q++ = ((c >> 18) & 0x3f) | 0x80; 241 } 242 *q++ = ((c >> 12) & 0x3f) | 0x80; 243 } 244 *q++ = ((c >> 6) & 0x3f) | 0x80; 245 } 246 *q++ = (c & 0x3f) | 0x80; 247 } 248 return q - buf; 249 } 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 { 263 int l, c, b, i; 264 265 c = *p++; 266 if (c < 0x80) { 267 *pp = p; 268 return c; 269 } 270 switch(c) { 271 case 0xc0: case 0xc1: case 0xc2: case 0xc3: 272 case 0xc4: case 0xc5: case 0xc6: case 0xc7: 273 case 0xc8: case 0xc9: case 0xca: case 0xcb: 274 case 0xcc: case 0xcd: case 0xce: case 0xcf: 275 case 0xd0: case 0xd1: case 0xd2: case 0xd3: 276 case 0xd4: case 0xd5: case 0xd6: case 0xd7: 277 case 0xd8: case 0xd9: case 0xda: case 0xdb: 278 case 0xdc: case 0xdd: case 0xde: case 0xdf: 279 l = 1; 280 break; 281 case 0xe0: case 0xe1: case 0xe2: case 0xe3: 282 case 0xe4: case 0xe5: case 0xe6: case 0xe7: 283 case 0xe8: case 0xe9: case 0xea: case 0xeb: 284 case 0xec: case 0xed: case 0xee: case 0xef: 285 l = 2; 286 break; 287 case 0xf0: case 0xf1: case 0xf2: case 0xf3: 288 case 0xf4: case 0xf5: case 0xf6: case 0xf7: 289 l = 3; 290 break; 291 case 0xf8: case 0xf9: case 0xfa: case 0xfb: 292 l = 4; 293 break; 294 case 0xfc: case 0xfd: 295 l = 5; 296 break; 297 default: 298 return -1; 299 } 300 /* check that we have enough characters */ 301 if (l > (max_len - 1)) 302 return -1; 303 c &= utf8_first_code_mask[l - 1]; 304 for(i = 0; i < l; i++) { 305 b = *p++; 306 if (b < 0x80 || b >= 0xc0) 307 return -1; 308 c = (c << 6) | (b & 0x3f); 309 } 310 if (c < utf8_min_code[l - 1]) 311 return -1; 312 *pp = p; 313 return c; 314 } 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 static void exchange_bytes(void *a, void *b, size_t size) { 346 uint8_t *ap = (uint8_t *)a; 347 uint8_t *bp = (uint8_t *)b; 348 349 while (size-- != 0) { 350 uint8_t t = *ap; 351 *ap++ = *bp; 352 *bp++ = t; 353 } 354 } 355 356 static void exchange_one_byte(void *a, void *b, size_t size) { 357 uint8_t *ap = (uint8_t *)a; 358 uint8_t *bp = (uint8_t *)b; 359 uint8_t t = *ap; 360 *ap = *bp; 361 *bp = t; 362 } 363 364 static void exchange_int16s(void *a, void *b, size_t size) { 365 uint16_t *ap = (uint16_t *)a; 366 uint16_t *bp = (uint16_t *)b; 367 368 for (size /= sizeof(uint16_t); size-- != 0;) { 369 uint16_t t = *ap; 370 *ap++ = *bp; 371 *bp++ = t; 372 } 373 } 374 375 static void exchange_one_int16(void *a, void *b, size_t size) { 376 uint16_t *ap = (uint16_t *)a; 377 uint16_t *bp = (uint16_t *)b; 378 uint16_t t = *ap; 379 *ap = *bp; 380 *bp = t; 381 } 382 383 static void exchange_int32s(void *a, void *b, size_t size) { 384 uint32_t *ap = (uint32_t *)a; 385 uint32_t *bp = (uint32_t *)b; 386 387 for (size /= sizeof(uint32_t); size-- != 0;) { 388 uint32_t t = *ap; 389 *ap++ = *bp; 390 *bp++ = t; 391 } 392 } 393 394 static void exchange_one_int32(void *a, void *b, size_t size) { 395 uint32_t *ap = (uint32_t *)a; 396 uint32_t *bp = (uint32_t *)b; 397 uint32_t t = *ap; 398 *ap = *bp; 399 *bp = t; 400 } 401 402 static void exchange_int64s(void *a, void *b, size_t size) { 403 uint64_t *ap = (uint64_t *)a; 404 uint64_t *bp = (uint64_t *)b; 405 406 for (size /= sizeof(uint64_t); size-- != 0;) { 407 uint64_t t = *ap; 408 *ap++ = *bp; 409 *bp++ = t; 410 } 411 } 412 413 static void exchange_one_int64(void *a, void *b, size_t size) { 414 uint64_t *ap = (uint64_t *)a; 415 uint64_t *bp = (uint64_t *)b; 416 uint64_t t = *ap; 417 *ap = *bp; 418 *bp = t; 419 } 420 421 static void exchange_int128s(void *a, void *b, size_t size) { 422 uint64_t *ap = (uint64_t *)a; 423 uint64_t *bp = (uint64_t *)b; 424 425 for (size /= sizeof(uint64_t) * 2; size-- != 0; ap += 2, bp += 2) { 426 uint64_t t = ap[0]; 427 uint64_t u = ap[1]; 428 ap[0] = bp[0]; 429 ap[1] = bp[1]; 430 bp[0] = t; 431 bp[1] = u; 432 } 433 } 434 435 static void exchange_one_int128(void *a, void *b, size_t size) { 436 uint64_t *ap = (uint64_t *)a; 437 uint64_t *bp = (uint64_t *)b; 438 uint64_t t = ap[0]; 439 uint64_t u = ap[1]; 440 ap[0] = bp[0]; 441 ap[1] = bp[1]; 442 bp[0] = t; 443 bp[1] = u; 444 } 445 446 static inline exchange_f exchange_func(const void *base, size_t size) { 447 switch (((uintptr_t)base | (uintptr_t)size) & 15) { 448 case 0: 449 if (size == sizeof(uint64_t) * 2) 450 return exchange_one_int128; 451 else 452 return exchange_int128s; 453 case 8: 454 if (size == sizeof(uint64_t)) 455 return exchange_one_int64; 456 else 457 return exchange_int64s; 458 case 4: 459 case 12: 460 if (size == sizeof(uint32_t)) 461 return exchange_one_int32; 462 else 463 return exchange_int32s; 464 case 2: 465 case 6: 466 case 10: 467 case 14: 468 if (size == sizeof(uint16_t)) 469 return exchange_one_int16; 470 else 471 return exchange_int16s; 472 default: 473 if (size == 1) 474 return exchange_one_byte; 475 else 476 return exchange_bytes; 477 } 478 } 479 480 static void heapsortx(void *base, size_t nmemb, size_t size, cmp_f cmp, void *opaque) 481 { 482 uint8_t *basep = (uint8_t *)base; 483 size_t i, n, c, r; 484 exchange_f swap = exchange_func(base, size); 485 486 if (nmemb > 1) { 487 i = (nmemb / 2) * size; 488 n = nmemb * size; 489 490 while (i > 0) { 491 i -= size; 492 for (r = i; (c = r * 2 + size) < n; r = c) { 493 if (c < n - size && cmp(basep + c, basep + c + size, opaque) <= 0) 494 c += size; 495 if (cmp(basep + r, basep + c, opaque) > 0) 496 break; 497 swap(basep + r, basep + c, size); 498 } 499 } 500 for (i = n - size; i > 0; i -= size) { 501 swap(basep, basep + i, size); 502 503 for (r = 0; (c = r * 2 + size) < i; r = c) { 504 if (c < i - size && cmp(basep + c, basep + c + size, opaque) <= 0) 505 c += size; 506 if (cmp(basep + r, basep + c, opaque) > 0) 507 break; 508 swap(basep + r, basep + c, size); 509 } 510 } 511 } 512 } 513 514 static inline void *med3(void *a, void *b, void *c, cmp_f cmp, void *opaque) 515 { 516 return cmp(a, b, opaque) < 0 ? 517 (cmp(b, c, opaque) < 0 ? b : (cmp(a, c, opaque) < 0 ? c : a )) : 518 (cmp(b, c, opaque) > 0 ? b : (cmp(a, c, opaque) < 0 ? a : c )); 519 } 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 { 524 struct { uint8_t *base; size_t count; int depth; } stack[50], *sp = stack; 525 uint8_t *ptr, *pi, *pj, *plt, *pgt, *top, *m; 526 size_t m4, i, lt, gt, span, span2; 527 int c, depth; 528 exchange_f swap = exchange_func(base, size); 529 exchange_f swap_block = exchange_func(base, size | 128); 530 531 if (nmemb < 2 || size <= 0) 532 return; 533 534 sp->base = (uint8_t *)base; 535 sp->count = nmemb; 536 sp->depth = 0; 537 sp++; 538 539 while (sp > stack) { 540 sp--; 541 ptr = sp->base; 542 nmemb = sp->count; 543 depth = sp->depth; 544 545 while (nmemb > 6) { 546 if (++depth > 50) { 547 /* depth check to ensure worst case logarithmic time */ 548 heapsortx(ptr, nmemb, size, cmp, opaque); 549 nmemb = 0; 550 break; 551 } 552 /* select median of 3 from 1/4, 1/2, 3/4 positions */ 553 /* should use median of 5 or 9? */ 554 m4 = (nmemb >> 2) * size; 555 m = med3(ptr + m4, ptr + 2 * m4, ptr + 3 * m4, cmp, opaque); 556 swap(ptr, m, size); /* move the pivot to the start or the array */ 557 i = lt = 1; 558 pi = plt = ptr + size; 559 gt = nmemb; 560 pj = pgt = top = ptr + nmemb * size; 561 for (;;) { 562 while (pi < pj && (c = cmp(ptr, pi, opaque)) >= 0) { 563 if (c == 0) { 564 swap(plt, pi, size); 565 lt++; 566 plt += size; 567 } 568 i++; 569 pi += size; 570 } 571 while (pi < (pj -= size) && (c = cmp(ptr, pj, opaque)) <= 0) { 572 if (c == 0) { 573 gt--; 574 pgt -= size; 575 swap(pgt, pj, size); 576 } 577 } 578 if (pi >= pj) 579 break; 580 swap(pi, pj, size); 581 i++; 582 pi += size; 583 } 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 span = plt - ptr; 595 span2 = pi - plt; 596 lt = i - lt; 597 if (span > span2) 598 span = span2; 599 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 span = top - pgt; 604 span2 = pgt - pi; 605 pgt = top - span2; 606 gt = nmemb - (gt - i); 607 if (span > span2) 608 span = span2; 609 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 if (lt > nmemb - gt) { 619 sp->base = ptr; 620 sp->count = lt; 621 sp->depth = depth; 622 sp++; 623 ptr = pgt; 624 nmemb -= gt; 625 } else { 626 sp->base = pgt; 627 sp->count = nmemb - gt; 628 sp->depth = depth; 629 sp++; 630 nmemb = lt; 631 } 632 } 633 /* Use insertion sort for small fragments */ 634 for (pi = ptr + size, top = ptr + nmemb * size; pi < top; pi += size) { 635 for (pj = pi; pj > ptr && cmp(pj - size, pj, opaque) > 0; pj -= size) 636 swap(pj, pj - size, size); 637 } 638 } 639 } 640 641 #endif