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