util.c (27424B)
1 /* See LICENSE for license details. */ 2 #if COMPILER_CLANG 3 #pragma GCC diagnostic ignored "-Winitializer-overrides" 4 #elif COMPILER_GCC 5 #pragma GCC diagnostic ignored "-Woverride-init" 6 #endif 7 8 #define zero_struct(s) memory_clear((s), 0, sizeof(*(s))) 9 function void * 10 memory_clear(void *restrict p_, u8 c, u64 size) 11 { 12 u8 *p = p_; 13 while (size > 0) p[--size] = c; 14 return p; 15 } 16 17 function b32 18 memory_equal(void *restrict left, void *restrict right, u64 n) 19 { 20 u8 *a = left, *b = right; 21 b32 result = 1; 22 for (; result && n; n--) 23 result &= *a++ == *b++; 24 return result; 25 } 26 27 function void 28 memory_copy(void *restrict dest, void *restrict src, u64 n) 29 { 30 u8 *s = src, *d = dest; 31 #ifdef __AVX512BW__ 32 { 33 for (; n >= 64; n -= 64, s += 64, d += 64) 34 _mm512_storeu_epi8(d, _mm512_loadu_epi8(s)); 35 __mmask64 k = _cvtu64_mask64(_bzhi_u64(-1ULL, n)); 36 _mm512_mask_storeu_epi8(d, k, _mm512_maskz_loadu_epi8(k, s)); 37 } 38 #else 39 for (; n; n--) *d++ = *s++; 40 #endif 41 } 42 43 /* IMPORTANT: this function may fault if dest, src, and n are not multiples of 64 */ 44 function void 45 memory_copy_non_temporal(void *restrict dest, void *restrict src, u64 n) 46 { 47 assume(((u64)dest & 63) == 0); 48 assume(((u64)src & 63) == 0); 49 assume(((u64)n & 63) == 0); 50 u8 *s = src, *d = dest; 51 52 #if defined(__AVX512BW__) 53 { 54 for (; n >= 64; n -= 64, s += 64, d += 64) 55 _mm512_stream_si512((__m512i *)d, _mm512_stream_load_si512((__m512i *)s)); 56 } 57 #elif defined(__AVX2__) 58 { 59 for (; n >= 32; n -= 32, s += 32, d += 32) 60 _mm256_stream_si256((__m256i *)d, _mm256_stream_load_si256((__m256i *)s)); 61 } 62 #elif ARCH_ARM64 && !COMPILER_MSVC 63 { 64 asm volatile ( 65 "cbz %2, 2f\n" 66 "1: ldnp q0, q1, [%1]\n" 67 "subs %2, %2, #32\n" 68 "add %1, %1, #32\n" 69 "stnp q0, q1, [%0]\n" 70 "add %0, %0, #32\n" 71 "b.ne 1b\n" 72 "2:" 73 : "+r"(d), "+r"(s), "+r"(n) 74 :: "memory", "v0", "v1" 75 ); 76 } 77 #else 78 memory_copy(d, s, n); 79 #endif 80 } 81 82 function void 83 memory_move(void *dest, void *src, u64 n) 84 { 85 u8 *d = dest, *s = src; 86 if (d < s) memory_copy(d, s, n); 87 else while (n) { n--; d[n] = s[n]; } 88 } 89 90 function void * 91 memory_scan_backwards(void *memory, u8 byte, i64 n) 92 { 93 void *result = 0; 94 u8 *s = memory; 95 while (n > 0) if (s[--n] == byte) { result = s + n; break; } 96 return result; 97 } 98 99 /* NOTE(rnp): from Hacker's Delight */ 100 function force_inline u64 101 round_down_power_of_two(u64 a) 102 { 103 u64 result = 0x8000000000000000ULL >> clz_u64(a); 104 return result; 105 } 106 107 function force_inline u64 108 round_up_power_of_two(u64 a) 109 { 110 u64 result = 0x8000000000000000ULL >> (clz_u64(a - 1) - 1); 111 return result; 112 } 113 114 function force_inline i64 115 round_up_to(i64 value, i64 multiple) 116 { 117 i64 result = value; 118 if (value % multiple != 0) 119 result += multiple - value % multiple; 120 return result; 121 } 122 123 typedef enum { 124 ArenaAllocateFlags_NoZero = 1 << 0, 125 } ArenaAllocateFlags; 126 127 typedef struct { 128 i64 size; 129 u64 align; 130 i64 count; 131 ArenaAllocateFlags flags; 132 } ArenaAllocateInfo; 133 134 function u8 * 135 arena_commit(Arena *a, i64 size) 136 { 137 Arena *current = a->current; 138 assert(current->committed - current->position >= (u64)size); 139 u8 *result = (u8 *)current + current->position; 140 current->position += size; 141 return result; 142 } 143 144 #define arena_create(...) arena_create_((ArenaParameters){\ 145 .reserve_size = MB(64),\ 146 .commit_size = KB(64),\ 147 .flags = 0,\ 148 .allocation_site_file = __FILE__,\ 149 .allocation_site_line = __LINE__,\ 150 __VA_ARGS__}) 151 152 function Arena * 153 arena_create_(ArenaParameters ap) 154 { 155 void *base = ap.optional_backing_store; 156 if (base == 0) { 157 ap.commit_size = round_up_to(ap.commit_size, os_system_info()->page_size); 158 ap.reserve_size = round_up_to(ap.reserve_size, os_system_info()->page_size); 159 160 base = os_memory_reserve(ap.reserve_size); 161 os_memory_commit(base, ap.commit_size); 162 } 163 164 Arena *result = base; 165 result->current = result; 166 result->position = sizeof(*result); 167 result->reserved = ap.reserve_size; 168 result->committed = ap.commit_size; 169 result->flags = ap.flags; 170 171 result->reserve_size = ap.reserve_size; 172 result->commit_size = ap.commit_size; 173 174 result->name = ap.name; 175 result->allocation_site_file = ap.allocation_site_file; 176 result->allocation_site_line = ap.allocation_site_line; 177 178 return result; 179 } 180 181 function void 182 arena_destroy(Arena *arena) 183 { 184 for (Arena *a = arena->current, *prev = 0; a; a = prev) { 185 prev = a->prev; 186 os_memory_release(a, a->reserved); 187 } 188 } 189 190 function void 191 arena_seal(Arena *arena) 192 { 193 assert(arena == arena->current); 194 u64 position = round_up_to(arena->position, os_system_info()->page_size); 195 if (arena->committed > position) { 196 os_memory_uncommit((u8 *)arena + position, arena->committed - position); 197 arena->committed = position; 198 } 199 if (arena->reserved > arena->committed) { 200 os_memory_release((u8 *)arena + arena->committed, arena->reserved - arena->committed); 201 arena->reserved = arena->committed; 202 } 203 os_memory_seal(arena, arena->reserved); 204 } 205 206 #define arena_alloc(a, ...) arena_alloc_(a, (ArenaAllocateInfo){.align = 8, .count = 1, __VA_ARGS__}) 207 #define push_array(a, t, n, ...) (t *)arena_alloc(a, .size = sizeof(t), .align = alignof(t), .count = n, __VA_ARGS__) 208 #define push_array_no_zero(a, t, n, ...) (t *)arena_alloc(a, .size = sizeof(t), .align = alignof(t), .count = n, .flags = ArenaAllocateFlags_NoZero, __VA_ARGS__) 209 #define push_struct(a, t, ...) push_array(a, t, 1, __VA_ARGS__) 210 #define push_struct_no_zero(a, t, ...) push_array_no_zero(a, t, 1, __VA_ARGS__) 211 212 function void * 213 arena_alloc_(Arena *arena, ArenaAllocateInfo info) 214 { 215 Arena *current = arena->current; 216 u64 size = info.count * info.size; 217 u64 pre_position = AlignUpPowerOfTwo(current->position, info.align); 218 u64 post_position = pre_position + size; 219 u64 zero_size = Min(current->committed, post_position) - pre_position; 220 221 if (current->reserved < post_position && (current->flags & ArenaFlag_NoChain) == 0) { 222 u64 reserve_size = current->reserve_size; 223 u64 commit_size = current->commit_size; 224 if (size + AlignUpPowerOfTwo(sizeof(*arena), info.align) > reserve_size) { 225 reserve_size = size + AlignUpPowerOfTwo(sizeof(*arena), info.align); 226 commit_size = size + AlignUpPowerOfTwo(sizeof(*arena), info.align); 227 } 228 Arena *new_arena = arena_create(.reserve_size = reserve_size, 229 .commit_size = commit_size, 230 .flags = current->flags, 231 .allocation_site_file = current->allocation_site_file, 232 .allocation_site_line = current->allocation_site_line, 233 .name = current->name); 234 zero_size = 0; 235 236 new_arena->base_position = current->base_position + current->reserved; 237 SLLStackPush(arena->current, new_arena, prev); 238 current = new_arena; 239 pre_position = AlignUpPowerOfTwo(current->position, info.align); 240 post_position = pre_position + size; 241 } 242 243 if (current->committed < post_position) { 244 u64 commit_post = post_position + current->commit_size - 1; 245 commit_post -= commit_post % current->commit_size; 246 commit_post = Min(commit_post, current->reserved); 247 os_memory_commit((u8 *)current + current->committed, commit_post - current->committed); 248 current->committed = commit_post; 249 } 250 251 void *result = 0; 252 if (current->committed >= post_position) { 253 result = (u8 *)current + pre_position; 254 current->position = post_position; 255 if ((info.flags & ArenaAllocateFlags_NoZero) == 0) 256 result = memory_clear(result, 0, zero_size); 257 } 258 259 assert(result); 260 261 return result; 262 } 263 264 function u64 265 arena_position(Arena *arena) 266 { 267 Arena *current = arena->current; 268 u64 result = current->base_position + current->position; 269 return result; 270 } 271 272 function void 273 arena_pop_to(Arena *arena, u64 position) 274 { 275 position = Max(position, sizeof(*arena)); 276 Arena *current = arena->current; 277 for (Arena *prev = 0; current->base_position >= position; current = prev) { 278 prev = current->prev; 279 os_memory_release(current, current->reserved); 280 } 281 arena->current = current; 282 u64 new_position = position - current->base_position; 283 assert(new_position <= current->position); 284 current->position = new_position; 285 } 286 287 function void 288 arena_pop(Arena *arena, u64 size) 289 { 290 u64 old_position = arena_position(arena); 291 u64 new_position = old_position; 292 if (size < old_position) 293 new_position = old_position - size; 294 arena_pop_to(arena, new_position); 295 } 296 297 function void 298 arena_clear(Arena *arena) 299 { 300 arena_pop_to(arena, 0); 301 } 302 303 function void 304 arena_pre_align(Arena *arena, u64 align) 305 { 306 assert(IsPowerOfTwo(align)); 307 Arena *current = arena->current; 308 u8 *start = (u8 *)current + current->position; 309 u8 *desired_start = (u8 *)AlignUpPowerOfTwo((u64)start, align); 310 current->position += (u64)(desired_start - start); 311 } 312 313 function Temp 314 temp_begin(Arena *arena) 315 { 316 Temp result = {.arena = arena, .position = arena_position(arena)}; 317 return result; 318 } 319 320 function void 321 temp_end(Temp t) 322 { 323 arena_pop_to(t.arena, t.position); 324 } 325 326 enum { DA_INITIAL_CAP = 16 }; 327 328 #define da_index(it, s) ((it) - (s)->data) 329 #define da_reserve(a, s, n) \ 330 (s)->data = da_reserve_((a), (s)->data, &(s)->capacity, (s)->count + n, \ 331 _Alignof(typeof(*(s)->data)), sizeof(*(s)->data)) 332 333 #define da_append_count(a, s, items, item_count) do { \ 334 da_reserve((a), (s), (item_count)); \ 335 memory_copy((s)->data + (s)->count, (items), sizeof(*(items)) * (u64)(item_count)); \ 336 (s)->count += (item_count); \ 337 } while (0) 338 339 #define da_push(a, s) \ 340 ((typeof((s)->data))memory_clear((s)->count == (s)->capacity \ 341 ? da_reserve(a, s, 1), \ 342 (s)->data + (s)->count++ \ 343 : (s)->data + (s)->count++, 0, sizeof(*(s)->data))) 344 345 346 /* NOTE(rnp): handles both 0 initialized DAs and DAs that need to be moved (they started 347 * on the stack or someone allocated something in the middle of the arena during usage) */ 348 function void * 349 da_reserve_(Arena *a, void *data, da_count *capacity, da_count needed, u64 align, i64 size) 350 { 351 da_count cap = *capacity; 352 if (!cap) cap = DA_INITIAL_CAP; 353 while (cap < needed) cap *= 2; 354 355 Arena *current = a->current; 356 u64 needed_size = cap * size; 357 u64 old_size = *capacity * size; 358 b32 can_extend = data && (u8 *)current + current->position == (u8 *)data + old_size && 359 (current->reserved - current->position) >= (needed_size - old_size); 360 b32 needs_copy = data && !can_extend; 361 362 u64 alloc_cap = cap; 363 if (can_extend) alloc_cap -= *capacity; 364 365 void *new = arena_alloc(a, .size = size, .align = align, .count = alloc_cap); 366 367 if (needs_copy) 368 memory_copy(new, data, (u64)(*capacity * size)); 369 370 if (!can_extend) 371 data = new; 372 373 *capacity = cap; 374 375 return data; 376 } 377 378 function u32 379 utf8_encode(u8 *out, u32 cp) 380 { 381 u32 result = 1; 382 if (cp <= 0x7F) { 383 out[0] = cp & 0x7F; 384 } else if (cp <= 0x7FF) { 385 result = 2; 386 out[0] = ((cp >> 6) & 0x1F) | 0xC0; 387 out[1] = ((cp >> 0) & 0x3F) | 0x80; 388 } else if (cp <= 0xFFFF) { 389 result = 3; 390 out[0] = ((cp >> 12) & 0x0F) | 0xE0; 391 out[1] = ((cp >> 6) & 0x3F) | 0x80; 392 out[2] = ((cp >> 0) & 0x3F) | 0x80; 393 } else if (cp <= 0x10FFFF) { 394 result = 4; 395 out[0] = ((cp >> 18) & 0x07) | 0xF0; 396 out[1] = ((cp >> 12) & 0x3F) | 0x80; 397 out[2] = ((cp >> 6) & 0x3F) | 0x80; 398 out[3] = ((cp >> 0) & 0x3F) | 0x80; 399 } else { 400 out[0] = '?'; 401 } 402 return result; 403 } 404 405 function UnicodeDecode 406 utf16_decode(u16 *data, i64 length) 407 { 408 UnicodeDecode result = {.cp = U32_MAX}; 409 if (length) { 410 result.consumed = 1; 411 result.cp = data[0]; 412 if (length > 1 && Between(data[0], 0xD800u, 0xDBFFu) 413 && Between(data[1], 0xDC00u, 0xDFFFu)) 414 { 415 result.consumed = 2; 416 result.cp = ((data[0] - 0xD800u) << 10u) | ((data[1] - 0xDC00u) + 0x10000u); 417 } 418 } 419 return result; 420 } 421 422 function u32 423 utf16_encode(u16 *out, u32 cp) 424 { 425 u32 result = 1; 426 if (cp == U32_MAX) { 427 out[0] = '?'; 428 } else if (cp < 0x10000u) { 429 out[0] = (u16)cp; 430 } else { 431 u32 value = cp - 0x10000u; 432 out[0] = (u16)(0xD800u + (value >> 10u)); 433 out[1] = (u16)(0xDC00u + (value & 0x3FFu)); 434 result = 2; 435 } 436 return result; 437 } 438 439 function Stream 440 stream_from_buffer(u8 *buffer, u32 capacity) 441 { 442 Stream result = {.data = buffer, .cap = (i32)capacity}; 443 return result; 444 } 445 446 function Stream 447 stream_alloc(Arena *a, i32 cap) 448 { 449 Stream result = stream_from_buffer(push_array_no_zero(a, u8, cap), (u32)cap); 450 return result; 451 } 452 453 function str8 454 stream_to_str8(Stream *s) 455 { 456 str8 result = str8(""); 457 if (!s->errors) result = (str8){.length = s->widx, .data = s->data}; 458 return result; 459 } 460 461 function void 462 stream_reset(Stream *s, i32 index) 463 { 464 s->errors = s->cap <= index; 465 if (!s->errors) 466 s->widx = index; 467 } 468 469 function void 470 stream_append(Stream *s, void *data, i64 count) 471 { 472 s->errors |= (s->cap - s->widx) < count; 473 if (!s->errors) { 474 memory_copy(s->data + s->widx, data, (u64)count); 475 s->widx += (i32)count; 476 } 477 } 478 479 function void 480 stream_append_codepoint(Stream *s, u32 codepoint) 481 { 482 u8 buffer[4]; 483 stream_append(s, buffer, utf8_encode(buffer, codepoint)); 484 } 485 486 // TODO(rnp): replace with handwritten version 487 #include <stdarg.h> 488 #include <stdio.h> 489 function void 490 stream_appendfv(Stream *s, const char *format, va_list args) 491 { 492 i32 written = vsnprintf((char *)s->data + s->widx, s->cap - s->widx, format, args); 493 s->errors |= written > (s->cap - s->widx); 494 if (!s->errors) s->widx += written; 495 } 496 497 function print_format(2, 3) void 498 stream_appendf(Stream *s, const char *format, ...) 499 { 500 va_list args; 501 va_start(args, format); 502 stream_appendfv(s, format, args); 503 va_end(args); 504 } 505 506 function void 507 stream_append_byte(Stream *s, u8 b) 508 { 509 stream_append(s, &b, 1); 510 } 511 512 function void 513 stream_pad(Stream *s, u8 b, i32 n) 514 { 515 while (n > 0) stream_append_byte(s, b), n--; 516 } 517 518 function void 519 stream_append_str8(Stream *s, str8 str) 520 { 521 stream_append(s, str.data, str.length); 522 } 523 524 #define stream_append_str8s(s, ...) stream_append_str8s_(s, arg_list(str8, ##__VA_ARGS__)) 525 function void 526 stream_append_str8s_(Stream *s, str8 *strs, i64 count) 527 { 528 for (i64 i = 0; i < count; i++) 529 stream_append(s, strs[i].data, strs[i].length); 530 } 531 532 function void 533 stream_append_u64_width(Stream *s, u64 n, u64 min_width) 534 { 535 u8 tmp[64]; 536 u8 *end = tmp + sizeof(tmp); 537 u8 *beg = end; 538 min_width = Min(sizeof(tmp), min_width); 539 540 do { *--beg = (u8)('0' + (n % 10)); } while (n /= 10); 541 while (end - beg > 0 && (u64)(end - beg) < min_width) 542 *--beg = '0'; 543 544 stream_append(s, beg, end - beg); 545 } 546 547 function void 548 stream_append_u64(Stream *s, u64 n) 549 { 550 stream_append_u64_width(s, n, 0); 551 } 552 553 function void 554 stream_append_hex_u64_width(Stream *s, u64 n, i64 width) 555 { 556 assert(width <= 16); 557 if (!s->errors) { 558 u8 buf[16]; 559 u8 *end = buf + sizeof(buf); 560 u8 *beg = end; 561 while (n) { 562 *--beg = (u8)"0123456789abcdef"[n & 0x0F]; 563 n >>= 4; 564 } 565 while (end - beg < width) 566 *--beg = '0'; 567 stream_append(s, beg, end - beg); 568 } 569 } 570 571 function void 572 stream_append_hex_u64(Stream *s, u64 n) 573 { 574 stream_append_hex_u64_width(s, n, 2); 575 } 576 577 function void 578 stream_append_i64(Stream *s, i64 n) 579 { 580 if (n < 0) { 581 stream_append_byte(s, '-'); 582 n *= -1; 583 } 584 stream_append_u64(s, (u64)n); 585 } 586 587 function void 588 stream_append_f64(Stream *s, f64 f, u64 prec) 589 { 590 if (f < 0) { 591 stream_append_byte(s, '-'); 592 f *= -1; 593 } 594 595 /* NOTE: round last digit */ 596 f += 0.5f / (f64)prec; 597 598 if (f >= (f64)(-1UL >> 1)) { 599 stream_append_str8(s, str8("inf")); 600 } else { 601 u64 integral = (u64)f; 602 u64 fraction = (u64)((f - (f64)integral) * (f64)prec); 603 stream_append_u64(s, integral); 604 stream_append_byte(s, '.'); 605 for (u64 i = prec / 10; i > 1; i /= 10) { 606 if (i > fraction) 607 stream_append_byte(s, '0'); 608 } 609 stream_append_u64(s, fraction); 610 } 611 } 612 613 function void 614 stream_append_f64_e(Stream *s, f64 f) 615 { 616 /* TODO: there should be a better way of doing this */ 617 #if 0 618 /* NOTE: we ignore subnormal numbers for now */ 619 union { f64 f; u64 u; } u = {.f = f}; 620 i32 exponent = ((u.u >> 52) & 0x7ff) - 1023; 621 f32 log_10_of_2 = 0.301f; 622 i32 scale = (exponent * log_10_of_2); 623 /* NOTE: normalize f */ 624 for (i32 i = ABS(scale); i > 0; i--) 625 f *= (scale > 0)? 0.1f : 10.0f; 626 #else 627 f32 sign = Sign(f); 628 f *= sign; 629 i32 scale = 0; 630 if (f != 0) { 631 while (f > 1) { 632 f *= 0.1f; 633 scale++; 634 } 635 while (f < 1) { 636 f *= 10.0f; 637 scale--; 638 } 639 } 640 #endif 641 642 u32 prec = 100; 643 stream_append_f64(s, sign * f, prec); 644 stream_append_byte(s, 'e'); 645 stream_append_byte(s, scale >= 0? '+' : '-'); 646 for (u32 i = prec / 10; i > 1; i /= 10) 647 stream_append_byte(s, '0'); 648 stream_append_u64(s, (u64)Abs(scale)); 649 } 650 651 function void 652 stream_append_struct_member(Stream *s, MetaStructMember *m, void *struct_base) 653 { 654 switch (m->type_id) { 655 InvalidDefaultCase; 656 case MetaKind_F32:{ 657 f32 value; 658 memory_copy(&value, ((u8 *)struct_base + m->offset), sizeof(value)); 659 stream_append_f64_e(s, value); 660 }break; 661 case MetaKind_B32:{ 662 b32 value; 663 memory_copy(&value, ((u8 *)struct_base + m->offset), sizeof(value)); 664 stream_append_str8(s, value ? str8("True") : str8("False")); 665 }break; 666 case MetaKind_U32:{ 667 u32 value; 668 memory_copy(&value, ((u8 *)struct_base + m->offset), sizeof(value)); 669 stream_append_u64(s, value); 670 }break; 671 case MetaKind_U64:{ 672 u64 value; 673 memory_copy(&value, ((u8 *)struct_base + m->offset), sizeof(value)); 674 stream_append_str8(s, str8("0x")); 675 stream_append_hex_u64(s, value); 676 }break; 677 case MetaKind_S32:{ 678 i32 value; 679 memory_copy(&value, ((u8 *)struct_base + m->offset), sizeof(value)); 680 stream_append_i64(s, value); 681 }break; 682 } 683 } 684 685 function Stream 686 arena_stream(Arena *a) 687 { 688 Arena *current = a->current; 689 Stream result = {0}; 690 result.data = (u8 *)current + current->position; 691 result.cap = (i32)(current->committed - current->position); 692 693 /* TODO(rnp): no idea what to do here if we want to maintain the ergonomics */ 694 asan_unpoison_region(result.data, result.cap); 695 696 return result; 697 } 698 699 function str8 700 arena_stream_commit(Arena *a, Stream *s) 701 { 702 Arena *current = a->current; 703 assert(s->data == (u8 *)current + current->position); 704 str8 result = stream_to_str8(s); 705 arena_commit(a, result.length); 706 return result; 707 } 708 709 function str8 710 arena_stream_commit_zero(Arena *a, Stream *s) 711 { 712 b32 error = s->errors || s->widx == s->cap; 713 if (!error) 714 s->data[s->widx] = 0; 715 str8 result = stream_to_str8(s); 716 arena_commit(a, result.length + 1); 717 return result; 718 } 719 720 function str8 721 arena_stream_commit_and_reset(Arena *arena, Stream *s) 722 { 723 str8 result = arena_stream_commit_zero(arena, s); 724 *s = arena_stream(arena); 725 return result; 726 } 727 728 #if !defined(XXH_IMPLEMENTATION) 729 # define XXH_INLINE_ALL 730 # define XXH_IMPLEMENTATION 731 # define XXH_STATIC_LINKING_ONLY 732 # include "external/xxhash.h" 733 #endif 734 735 function u128 736 u128_hash_from_data(void *data, u64 size) 737 { 738 u128 result = {0}; 739 XXH128_hash_t hash = XXH3_128bits_withSeed(data, size, 4969); 740 memory_copy(&result, &hash, sizeof(result)); 741 return result; 742 } 743 744 function u64 745 u64_hash_from_str8_seed(str8 string, u64 seed) 746 { 747 u64 result = XXH3_64bits_withSeed(string.data, (u64)string.length, seed); 748 return result; 749 } 750 751 function u64 752 u64_hash_from_str8(str8 v) 753 { 754 u64 result = u64_hash_from_str8_seed(v, 4969); 755 return result; 756 } 757 758 function str8 759 str8_from_c_str(char *cstr) 760 { 761 str8 result = {.data = (u8 *)cstr}; 762 if (cstr) while (*cstr) cstr++; 763 result.length = (u8 *)cstr - result.data; 764 return result; 765 } 766 767 function str8 768 str8_range(u8 *start, u8 *one_past_last) 769 { 770 str8 result; 771 result.data = start; 772 result.length = one_past_last - start; 773 return result; 774 } 775 776 function str8 777 str8_skip(str8 s, i64 count) 778 { 779 str8 result = s; 780 if (count > 0) { 781 result.data += count; 782 result.length -= count; 783 } 784 return result; 785 } 786 787 function b32 788 str8_equal(str8 a, str8 b) 789 { 790 b32 result = a.length == b.length; 791 for (i64 i = 0; result && i < a.length; i++) 792 result = a.data[i] == b.data[i]; 793 return result; 794 } 795 796 /* NOTE(rnp): returns < 0 if byte is not found */ 797 function i64 798 str8_scan_backwards(str8 s, u8 byte) 799 { 800 i64 result = (u8 *)memory_scan_backwards(s.data, byte, s.length) - s.data; 801 return result; 802 } 803 804 function str8 805 str8_cut_head(str8 s, i64 cut) 806 { 807 str8 result = s; 808 if (cut > 0) { 809 result.data += cut; 810 result.length -= cut; 811 } 812 result.length = Max(0, result.length); 813 return result; 814 } 815 816 function i64 817 str8_word_boundary_before(str8 s, i64 p) 818 { 819 p = Max(p - 1, 0); 820 b32 negate = IsWordBoundary(s.data[p]); 821 while (p >= 0 && (negate ^ !IsWordBoundary(s.data[p]))) 822 p -= 1; 823 p++; 824 return p; 825 } 826 827 function i64 828 str8_word_boundary_after(str8 s, i64 p) 829 { 830 b32 negate = IsWordBoundary(s.data[p]); 831 while (p != s.length && (negate ^ !IsWordBoundary(s.data[p]))) 832 p += 1; 833 return p; 834 } 835 836 function i64 837 str8_word_boundary(str8 s, i64 p, i64 count) 838 { 839 i64 sign = Sign(count); 840 i64 end_p = sign > 0 ? s.length : 0; 841 count = Abs(count); 842 p = Clamp(p, 0, s.length); 843 844 for (i64 word_count = 0; word_count < count && p != end_p; word_count++) 845 p = sign > 0 ? str8_word_boundary_after(s, p) : str8_word_boundary_before(s, p); 846 847 return p; 848 } 849 850 function b32 851 str8_match(str8 a, str8 b, StringMatchFlags flags) 852 { 853 b32 result = 0; 854 if (flags == 0) { 855 result = str8_equal(a, b); 856 } else if (a.length == b.length || (flags & StringMatchFlag_SloppySize)) { 857 result = 1; 858 i64 length = Min(a.length, b.length); 859 for (i64 it = 0; it < length && result; it++) { 860 u8 ab = a.data[it], bb = b.data[it]; 861 if (flags & StringMatchFlag_CaseInsensitive) { 862 ab |= 0x20; 863 bb |= 0x20; 864 } 865 result &= ab == bb; 866 } 867 } 868 return result; 869 } 870 871 function i64 872 str8_find_needle(str8 string, str8 needle, StringMatchFlags flags) 873 { 874 u8 *s = string.data; 875 u8 *se = string.data + Max(string.length + 1, needle.length) - needle.length; 876 if (needle.length > 0) { 877 flags |= StringMatchFlag_SloppySize; 878 879 u8 nb = needle.data[0]; 880 if (flags & StringMatchFlag_CaseInsensitive) 881 nb |= 0x20; 882 883 str8 needle_tail = str8_skip(needle, 1); 884 u8 *s_opl = string.data + string.length; 885 for (; s < se; s++) { 886 u8 sb = *s; 887 if (flags & StringMatchFlag_CaseInsensitive) 888 sb |= 0x20; 889 890 if (sb == nb && str8_match(str8_range(s + 1, s_opl), needle_tail, flags)) 891 break; 892 } 893 } 894 895 i64 result = string.length; 896 if (s < se) 897 result = s - string.data; 898 return result; 899 } 900 901 902 function str8 903 str8_alloc(Arena *a, i64 length) 904 { 905 str8 result = {.data = push_array(a, u8, length), .length = length}; 906 return result; 907 } 908 909 function str8 910 str8_from_str16(Arena *a, str16 in) 911 { 912 str8 result = str8(""); 913 if (in.length) { 914 i64 commit = in.length * 4; 915 i64 length = 0; 916 u8 *data = push_array_no_zero(a, u8, commit + 1); 917 u16 *beg = in.data; 918 u16 *end = in.data + in.length; 919 while (beg < end) { 920 UnicodeDecode decode = utf16_decode(beg, end - beg); 921 length += utf8_encode(data + length, decode.cp); 922 beg += decode.consumed; 923 } 924 data[length] = 0; 925 result = (str8){.length = length, .data = data}; 926 arena_pop(a, commit - length); 927 } 928 return result; 929 } 930 931 function str16 932 str16_from_str8(Arena *a, str8 in) 933 { 934 str16 result = {0}; 935 if (in.length) { 936 i64 length = 0; 937 i64 required = 2 * in.length + 1; 938 u16 *data = push_array(a, u16, required); 939 /* TODO(rnp): utf8_decode */ 940 for (i64 i = 0; i < in.length; i++) { 941 u32 cp = in.data[i]; 942 length += utf16_encode(data + length, cp); 943 } 944 result = (str16){.length = length, .data = data}; 945 arena_pop(a, required - length); 946 } 947 return result; 948 } 949 950 #define push_str8_from_parts(a, j, ...) push_str8_from_parts_((a), (j), arg_list(str8, __VA_ARGS__)) 951 function str8 952 push_str8_from_parts_(Arena *arena, str8 joiner, str8 *parts, i64 count) 953 { 954 i64 length = joiner.length * (count - 1); 955 for (i64 i = 0; i < count; i++) 956 length += parts[i].length; 957 958 str8 result = {.length = length, .data = push_array_no_zero(arena, u8, length + 1)}; 959 960 i64 offset = 0; 961 for (i64 i = 0; i < count; i++) { 962 if (i != 0) { 963 memory_copy(result.data + offset, joiner.data, (u64)joiner.length); 964 offset += joiner.length; 965 } 966 memory_copy(result.data + offset, parts[i].data, (u64)parts[i].length); 967 offset += parts[i].length; 968 } 969 result.data[result.length] = 0; 970 971 return result; 972 } 973 974 function str8 975 push_str8(Arena *a, str8 str) 976 { 977 str8 result = str8_alloc(a, str.length + 1); 978 result.length -= 1; 979 memory_copy(result.data, str.data, (u64)result.length); 980 return result; 981 } 982 983 // TODO(rnp): replace with handwritten version 984 function str8 985 push_str8_fv(Arena *arena, const char *format, va_list args) 986 { 987 va_list args2; 988 va_copy(args2, args); 989 i64 size = vsnprintf(0, 0, format, args2); 990 va_end(args2); 991 str8 result = str8_alloc(arena, size + 1); 992 i64 written = vsnprintf((char *)result.data, result.length, format, args); 993 assert(written == size); 994 result.length -= 1; 995 return result; 996 } 997 998 function print_format(2, 3) str8 999 push_str8_f(Arena *arena, const char *format, ...) 1000 { 1001 va_list args; 1002 va_start(args, format); 1003 str8 result = push_str8_fv(arena, format, args); 1004 va_end(args); 1005 return result; 1006 } 1007 1008 function NumberConversion 1009 integer_from_str8(str8 raw) 1010 { 1011 read_only local_persist alignas(64) i8 lut[64] = { 1012 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, 1013 -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1014 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1015 -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1016 }; 1017 1018 NumberConversion result = {.unparsed = raw}; 1019 1020 i64 i = 0; 1021 i64 scale = 1; 1022 if (raw.length > 0 && raw.data[0] == '-') { 1023 scale = -1; 1024 i = 1; 1025 } 1026 1027 b32 hex = 0; 1028 if (raw.length - i > 2 && raw.data[i] == '0' && (raw.data[1] == 'x' || raw.data[1] == 'X')) { 1029 hex = 1; 1030 i += 2; 1031 } 1032 1033 #define integer_conversion_body(radix, clamp) do {\ 1034 for (; i < raw.length; i++) {\ 1035 i64 value = lut[Min((u8)(raw.data[i] - (u8)'0'), clamp)];\ 1036 if (value >= 0) {\ 1037 if (result.U64 > (U64_MAX - (u64)value) / radix) {\ 1038 result.result = NumberConversionResult_OutOfRange;\ 1039 result.U64 = U64_MAX;\ 1040 return result;\ 1041 } else {\ 1042 result.U64 = radix * result.U64 + (u64)value;\ 1043 }\ 1044 } else {\ 1045 break;\ 1046 }\ 1047 }\ 1048 } while (0) 1049 1050 if (hex) integer_conversion_body(16u, 63u); 1051 else integer_conversion_body(10u, 15u); 1052 1053 #undef integer_conversion_body 1054 1055 result.unparsed = (str8){.length = raw.length - i, .data = raw.data + i}; 1056 result.result = i > 0 ? NumberConversionResult_Success : NumberConversionResult_Invalid; 1057 result.kind = NumberConversionKind_Integer; 1058 if (scale < 0) result.U64 = 0 - result.U64; 1059 1060 return result; 1061 } 1062 1063 function NumberConversion 1064 number_from_str8(str8 s) 1065 { 1066 NumberConversion result = {.unparsed = s}; 1067 NumberConversion integer = integer_from_str8(s); 1068 if (integer.result == NumberConversionResult_Success) { 1069 if (integer.unparsed.length != 0 && integer.unparsed.data[0] == '.') { 1070 s = integer.unparsed; 1071 s.data++; 1072 s.length--; 1073 1074 while (s.length > 0 && s.data[s.length - 1] == '0') s.length--; 1075 1076 NumberConversion fractional = integer_from_str8(s); 1077 if (fractional.result == NumberConversionResult_Success || s.length == 0) { 1078 result.F64 = (f64)fractional.U64; 1079 1080 u64 divisor = (u64)(fractional.unparsed.data - s.data); 1081 while (divisor > 0) { result.F64 /= 10.0; divisor--; } 1082 1083 result.F64 += (f64)integer.S64; 1084 1085 result.result = NumberConversionResult_Success; 1086 result.kind = NumberConversionKind_Float; 1087 result.unparsed = fractional.unparsed; 1088 } 1089 } else { 1090 result = integer; 1091 } 1092 } 1093 return result; 1094 } 1095 1096 function b32 1097 take_lock(i32 *lock, i32 timeout_ms) 1098 { 1099 b32 result = 0; 1100 for (;;) { 1101 i32 current = 0; 1102 if (atomic_cas_u32(lock, ¤t, 1)) 1103 result = 1; 1104 if (result || !timeout_ms || (!os_wait_on_address(lock, current, (u32)timeout_ms) && timeout_ms != -1)) 1105 break; 1106 } 1107 return result; 1108 } 1109 1110 function void 1111 release_lock(i32 *lock) 1112 { 1113 assert(atomic_load_u32(lock)); 1114 atomic_store_u32(lock, 0); 1115 os_wake_all_waiters(lock); 1116 }