cutils.c (17552B)
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 /* return < 0 if error */ 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 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 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_no_ub(s->buf + s->size, data, len); 144 s->size += len; 145 return 0; 146 } 147 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 159 int dbuf_putc(DynBuf *s, uint8_t c) 160 { 161 return dbuf_put(s, &c, 1); 162 } 163 164 int dbuf_putstr(DynBuf *s, const char *str) 165 { 166 return dbuf_put(s, (const uint8_t *)str, strlen(str)); 167 } 168 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 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. */ 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. */ 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 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 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 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 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 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 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 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 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 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 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 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 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 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 */ 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