src/util/libc.c

/* ----------------------------------------------------------------------------
Copyright (c) 2018-2026, Microsoft Research, Daan Leijen
This is free software; you can redistribute it and/or modify it under the
terms of the MIT license. A copy of the license can be found in the file
"LICENSE" at the root of this distribution.
-----------------------------------------------------------------------------*/

// --------------------------------------------------------
// This module defines various standard libc functions to reduce
// the dependency on libc, and also prevent errors caused
// by some libc implementations when called before `main`
// executes (due to malloc redirection)
// --------------------------------------------------------

#include "mimalloc.h"
#include "mimalloc/prim.h"             // mi_prim_getenv
#include "mimalloc/prim/prim-tls.h"
#include "mimalloc/util/options.h"
#include "mimalloc/util/libc.h"
#include <limits.h>                   // LONG_MIN, LONG_MAX

#if MI_DEBUG && NDEBUG
#if defined(_MSC_VER)
#pragma message("mimalloc assertions enabled in a release build")
#else
#warning "mimalloc assertions enabled in a release build"
#endif
#endif

char _mi_toupper(char c) {
  if (c >= 'a' && c <= 'z') return (c - 'a' + 'A');
                       else return c;
}

int _mi_strnicmp(const char* s, const char* t, size_t n) {
  mi_assert_internal(s!=NULL && t!=NULL);
  if (n == 0) return 0;
  for (; *s != 0 && *t != 0 && n > 0; s++, t++, n--) {
    if (_mi_toupper(*s) != _mi_toupper(*t)) break;
  }
  return (n == 0 ? 0 : *s - *t);
}

bool _mi_streq(const char* s, const char* t) {
  if (s==NULL && t==NULL) return true;
  if (s==NULL || t==NULL) return false;
  for (; *s != 0 && *t != 0; s++, t++) {
    if (*s != *t) break;
  }
  return (*s == *t);
}

bool _mi_strlcpy(char* dest, const char* src, size_t dest_size) {
  if (dest==NULL || src==NULL || dest_size == 0) return (src==NULL || *src==0);
  // copy until end of src, or when dest is (almost) full
  while (*src != 0 && dest_size > 1) {
    *dest++ = *src++;
    dest_size--;
  }
  // always zero terminate
  *dest = 0;
  return (*src == 0);
}

bool _mi_strlcat(char* dest, const char* src, size_t dest_size) {
  if (dest==NULL || src==NULL || dest_size == 0) return (src==NULL || *src==0);
  // find end of string in the dest buffer
  while (*dest != 0 && dest_size > 1) {
    dest++;
    dest_size--;
  }
  // and catenate
  return _mi_strlcpy(dest, src, dest_size);
}

size_t _mi_strnlen(const char* s, size_t max_len) {
  if (s==NULL) return 0;
  size_t len = 0;
  while(len < max_len && s[len] != 0) { len++; }
  return len;
}

size_t _mi_strlen(const char* s) {
  return _mi_strnlen(s,PTRDIFF_MAX);
}

char* _mi_strnstr(char* s, size_t max_len, const char* pat) {
  if (s==NULL) return NULL;
  if (pat==NULL) return s;
  const size_t m = _mi_strnlen(s, max_len);
  const size_t n = _mi_strlen(pat);
  for (size_t start = 0; start + n <= m; start++) {
    size_t i = 0;
    while (i<n && pat[i]==s[start+i]) {
      i++;
    }
    if (i==n) return &s[start];
  }
  return NULL;
}

const char* _mi_strchr(const char* s, char c) {
  if (s==NULL) return NULL;
  for (; *s != 0; s++) {
    if (*s == c) return s;
  }
  return (c == 0 ? s : NULL);
}

// backward search: like `strrchr`, returns the last occurrence of `c` in `s`, or NULL if not found.
const char* _mi_strrchr(const char* s, char c) {
  if (s==NULL) return NULL;
  const char* last = (c == 0 ? s + _mi_strlen(s) : NULL);
  for (; *s != 0; s++) {
    if (*s == c) last = s;
  }
  return last;
}


static bool mi_isspace(char c) {
  return (c == ' ' || (c >= '\t' && c <= '\r'));
}

static int mi_digit_value(char c, int base) {
  if (c >= '0' && c <= '9') return (c - '0');
  if (base == 16) {
    if (c >= 'a' && c <= 'f') return (c - 'a' + 10);
    if (c >= 'A' && c <= 'F') return (c - 'A' + 10);
  }
  return -1;
}

// Parse up to max_len bytes without errno or requiring a terminator; skip at most 128 whitespace characters.
// Allow at most 64 digits; leading zeros are allowed only in hexadecimal.
// On failure, result is zero (clamped on overflow); end is s if no digits, otherwise the stopping point.
bool _mi_strntol(const char* s, size_t max_len, const char** end, long* result) {
  if (end != NULL) { *end = s; }
  if (result != NULL) { *result = 0; }
  if (s == NULL) return false;
  size_t i = 0;
  while (i < max_len && i < 128 && mi_isspace(s[i])) { i++; }
  if (i == max_len) return false;
  const bool neg = (s[i] == '-');
  if (neg || s[i] == '+') { i++; }
  if (i == max_len) return false;
  int base = 10;
  if (i + 1 < max_len && s[i] == '0' && (s[i+1] == 'x' || s[i+1] == 'X')) {
    base = 16;
    i += 2;
  }
  if (base == 10 && i + 1 < max_len && s[i] == '0' && mi_digit_value(s[i+1], base) >= 0) return false;
  const size_t start = i;
  // Accumulate negatively so LONG_MIN is representable without unsigned arithmetic.
  const long limit = (neg ? LONG_MIN : -LONG_MAX);
  const long cutoff = limit / base;
  const long cutlim = -(limit % base);
  long acc = 0;
  while (i < max_len && i - start < 64) {
    const int digit = mi_digit_value(s[i], base);
    if (digit < 0) break;
    if (acc < cutoff || (acc == cutoff && digit > cutlim)) {
      if (end != NULL) { *end = s + i; }
      if (result != NULL) { *result = (neg ? LONG_MIN : LONG_MAX); }
      return false;
    }
    acc = acc*base - digit;
    i++;
  }
  if (i == start) return false;
  if (end != NULL) { *end = s + i; }
  if (i < max_len && i - start == 64 && mi_digit_value(s[i], base) >= 0) return false;
  if (result != NULL) { *result = (neg ? acc : -acc); }
  return true;
}

#ifdef MI_NO_GETENV
int _mi_getenv(const char* name, char* result, size_t result_size) {
  MI_UNUSED(name);
  MI_UNUSED(result);
  MI_UNUSED(result_size);
  return ENOENT;
}
#else
int _mi_getenv(const char* name, char* result, size_t result_size) {
  if (name==NULL || result == NULL || result_size < 64) return ENOENT;
  // change the result of _mi_prim_getenv to an errno result
  const int res = _mi_prim_getenv(name,result,result_size);
  return (res > 0 ? 0 : (res == 0 ? ENOENT : EAGAIN));
}
#endif


// --------------------------------------------------------
// Define our own primitives for doing an action once
// --------------------------------------------------------

// Returns `true` only on the first invocation, signifying we can execute an action once.
// If it returns `true`, the caller should call `_mi_atomic_once_release` after performing the action.
// Other threads (than the initial thread that entered) will block until `_mi_atomic_once_release` has been called.
bool _mi_atomic_once_enter(mi_atomic_once_t* once) {
  const size_t once_tid = mi_atomic_load_acquire(&once->tid);
  if mi_likely(once_tid == 1) {
    return false; // already executed
  }
  const mi_thread_id_t current_tid = _mi_thread_id();
  if (once_tid == current_tid) {
    return false; // recursive invocation; don't block on ourselves
  }

  mi_lock_acquire(&once->lock);
  size_t expected = 0;
  if (mi_atomic_cas_strong_acq_rel(&once->tid, &expected, current_tid)) {  // could use atomic_load/store as well
    return true;  // should execute and release
  }
  else {
    mi_lock_release(&once->lock);
    return false; // already another thread entered and released
  }
}

void _mi_atomic_once_release(mi_atomic_once_t* once) {
  if (mi_atomic_load_acquire(&once->tid)>1) {  // paranoia
    mi_atomic_store_release(&once->tid,1);     // done executing
    mi_lock_release(&once->lock);
  }
}

#if MI_USE_PTHREADS
mi_decl_noinline bool _mi_pthread_key_create(pthread_key_t* pkey, void (*destruct)(void*), void* init) {
  int err = pthread_key_create(pkey,destruct);
  if mi_unlikely(err!=0) {
    *pkey = MI_PTHREAD_KEY_INVALID;
    _mi_error_message(ENOMEM,"unable to allocate a thread local variable (error %d)\n", err);
    return false;
  }
  mi_assert_internal(*pkey != MI_PTHREAD_KEY_INVALID);
  if (init!=NULL) {
    pthread_setspecific(*pkey,init);
  };
  mi_assert_internal(pthread_getspecific(*pkey)==init);
  return true;
}
#endif

// --------------------------------------------------------
// Detect CPU features
// --------------------------------------------------------
mi_decl_cache_align bool   _mi_cpu_has_popcnt = false;

#if (MI_ARCH_X64 || MI_ARCH_X86)
#if defined(__GNUC__)
// #include <cpuid.h>
static bool mi_cpuid(uint32_t* regs4, uint32_t level, uint32_t sublevel) {
  // note: use explicit assembly instead of __get_cpuid as we need the sublevel (in ecx)
  // (on Ubuntu 22 with WSL the __get_cpuid does not clear ecx for level 7 which is incorrect).
  uint32_t eax, ebx, ecx, edx;
  __asm __volatile("cpuid" : "=a"(eax), "=b"(ebx), "=c"(ecx), "=d"(edx) : "a"(level), "c"(sublevel) : );
  regs4[0] = eax;
  regs4[1] = ebx;
  regs4[2] = ecx;
  regs4[3] = edx;
  return true;
}

#elif defined(_MSC_VER)
static bool mi_cpuid(uint32_t* regs4, uint32_t level, uint32_t sublevel) {
  __cpuidex((int32_t*)regs4, (int32_t)level, (int32_t)sublevel);
  return true;
}
#else
static bool mi_cpuid(uint32_t* regs4, uint32_t level, uint32_t sublevel) {
  MI_UNUSED(regs4); MI_UNUSED(level); MI_UNUSED(sublevel);
  return false;
}
#endif

void _mi_detect_cpu_features(void) {
  uint32_t cpu_info[4];
  if (mi_cpuid(cpu_info, 1, 0)) {
    _mi_cpu_has_popcnt = ((cpu_info[2] & (1 << 23)) != 0); // bit 23 of ECX : see <https://en.wikipedia.org/wiki/CPUID#EAX=1:_Processor_Info_and_Feature_Bits>
  }
}

#else
void _mi_detect_cpu_features(void) {
  #if MI_ARCH_ARM64 || defined(__riscv_zbb) || defined(__riscv_b)
  _mi_cpu_has_popcnt = true;
  #endif
}
#endif


// --------------------------------------------------------
// Define our own limited `_mi_vsnprintf` and `_mi_snprintf`
// This is mostly to avoid calling these when libc is not yet
// initialized (and to reduce dependencies)
//
// format:      d i, p x u, s
// prec:        z l ll L l8 l4   // l8=64-bit, l4=32-bit
// width:       10
// align-left:  -
// fill:        0
// plus:        +
// --------------------------------------------------------

static void mi_outc(char c, char** out, char* end) {
  char* p = *out;
  if (p >= end) return;
  *p = c;
  *out = p + 1;
}

static void mi_outs(const char* s, char** out, char* end) {
  if (s == NULL) return;
  char* p = *out;
  while (*s != 0 && p < end) {
    *p++ = *s++;
  }
  *out = p;
}

static void mi_out_fill(char fill, size_t len, char** out, char* end) {
  char* p = *out;
  for (size_t i = 0; i < len && p < end; i++) {
    *p++ = fill;
  }
  *out = p;
}

static void mi_out_alignright(char fill, char* start, size_t len, size_t extra, char* end) {
  if (len == 0 || extra == 0) return;
  if (start + len + extra >= end) return;
  // move `len` characters to the right (in reverse since it can overlap)
  for (size_t i = 1; i <= len; i++) {
    start[len + extra - i] = start[len - i];
  }
  // and fill the start
  for (size_t i = 0; i < extra; i++) {
    start[i] = fill;
  }
}


static void mi_out_num(uintmax_t x, size_t base, char prefix, char** out, char* end)
{
  if (x == 0 || base == 0 || base > 16) {
    if (prefix != 0) { mi_outc(prefix, out, end); }
    mi_outc('0',out,end);
  }
  else {
    #define MI_MAX_OUT_DIGITS (160)     /* a 512 bit number has 155 digits */
    char num[MI_MAX_OUT_DIGITS];
    int dcount = 0;
    while(x>0 && dcount < MI_MAX_OUT_DIGITS) {
      char digit = (char)(x % base);
      num[dcount++] = (digit <= 9 ? '0' + digit : 'A' + digit - 10);
      x = x / base;
    }
    if (dcount>=MI_MAX_OUT_DIGITS) return;  // don't output anything?
    if (prefix != 0) {
      mi_outc(prefix, out, end);
    }
    while(dcount-- > 0) {
      mi_outc(num[dcount], out, end);
    }
  }
}


#define MI_NEXTC()  c = *in; if (c==0) break; in++;

int _mi_vsnprintf(char* buf, size_t bufsize, const char* fmt, va_list args) {
  if (buf == NULL || bufsize == 0 || fmt == NULL) return 0;
  buf[bufsize - 1] = 0;
  char* const end = buf + (bufsize - 1);
  const char* in = fmt;
  char* out = buf;
  while (true) {
    if (out >= end) break;
    char c;
    MI_NEXTC();
    if (c != '%') {
      if (c == '\\') {
        MI_NEXTC();
        switch (c) {
        case 'e': mi_outc('\x1B', &out, end); break;
        case 't': mi_outc('\t', &out, end); break;
        case 'n': mi_outc('\n', &out, end); break;
        case 'r': mi_outc('\r', &out, end); break;
        case '\\': mi_outc('\\', &out, end); break;
        default: /* ignore */ break;
        }
      }
      else if ((c >= ' ' && c <= '~') || c=='\n' || c=='\r' || c=='\t' || c=='\x1b') { // output visible ascii or standard control only
        mi_outc(c, &out, end);
      }
    }
    else {
      MI_NEXTC();
      char   fill = ' ';
      size_t width = 0;
      char   numtype = 'd';
      char   numplus = 0;
      bool   alignright = true;
      if (c == '+' || c == ' ') { numplus = c; MI_NEXTC(); }
      if (c == '-') { alignright = false; MI_NEXTC(); }
      if (c == '0') { fill = '0'; MI_NEXTC(); }
      if (c >= '1' && c <= '9') {
        width = (c - '0'); MI_NEXTC();
        while (c >= '0' && c <= '9') {
          if (width < SIZE_MAX/1024) {  // no overflow
            width = (10 * width) + (c - '0');
          }
          MI_NEXTC();
        }
        if (c == 0) break;  // extra check due to while
      }
      if (c == 'z' || c == 't' || c == 'L') {
        numtype = c; MI_NEXTC();
      }
      else if (c == 'l') {
        numtype = c; MI_NEXTC();
        if (c == 'l') { numtype = 'L'; MI_NEXTC(); }
        else if (c == '8') { numtype = '8'; MI_NEXTC(); } // 64-bit
        else if (c == '4') { numtype = '4'; MI_NEXTC(); } // 32-bit
      }


      char* start = out;
      if (c == '%') {
        mi_outc('%', &out, end);
      }
      else if (c == 's') {
        // string
        const char* s = va_arg(args, const char*);
        mi_outs(s, &out, end);
      }
      else if (c == 'p' || c == 'x' || c == 'u') {
        // unsigned
        uintmax_t x = 0;
        if (c == 'x' || c == 'u') {
          if (numtype == 'z')       x = va_arg(args, size_t);
          else if (numtype == 't')  x = va_arg(args, size_t);   // unsigned ptrdiff_t
          else if (numtype == 'L')  x = va_arg(args, unsigned long long);
          else if (numtype == 'l')  x = va_arg(args, unsigned long);
          else if (numtype == '8')  x = va_arg(args, uint64_t);
          else if (numtype == '4')  x = va_arg(args, uint32_t);
                               else x = va_arg(args, unsigned int);
        }
        else if (c == 'p') {
          void* const p = va_arg(args, void*);
          x = mi_addr(p);
          mi_outs("0x", &out, end);
          start = out;
          width = (width >= 2 ? width - 2 : 0);
        }
        if (width == 0 && (c == 'x' || c == 'p')) {
          if (c == 'p')   { width = 2 * (x <= UINT32_MAX ? 4 : ((x >> 16) <= UINT32_MAX ? 6 : sizeof(size_t))); }
          if (width == 0) { width = 2; }
          if (alignright) { fill = '0'; }
        }
        mi_out_num(x, (c == 'x' || c == 'p' ? 16 : 10), numplus, &out, end);
      }
      else if (c == 'i' || c == 'd') {
        // signed
        intmax_t x = 0;
        if (numtype == 'z')       x = va_arg(args, ptrdiff_t);  // signed size_t
        else if (numtype == 't')  x = va_arg(args, ptrdiff_t);
        else if (numtype == 'L')  x = va_arg(args, long long);
        else if (numtype == 'l')  x = va_arg(args, long);
        else if (numtype == '8')  x = va_arg(args, int64_t);
        else if (numtype == '4')  x = va_arg(args, int32_t);
                             else x = va_arg(args, int);
        char pre = 0;
        if (x < 0) {
          pre = '-';
          if (x > INTMAX_MIN) { x = -x; }
        }
        else if (numplus != 0) {
          pre = numplus;
        }
        mi_out_num((uintmax_t)x, 10, pre, &out, end);
      }
      else if (c >= ' ' && c <= '~') {
        // unknown format
        mi_outc('%', &out, end);
        mi_outc(c, &out, end);
      }

      // fill & align
      mi_assert_internal(out <= end);
      mi_assert_internal(out >= start);
      const size_t len = out - start;
      if (len < width) {
        mi_out_fill(fill, width - len, &out, end);
        if (alignright && out <= end) {
          mi_out_alignright(fill, start, len, width - len, end);
        }
      }
    }
  }
  mi_assert_internal(out <= end);
  *out = 0;
  return (int)(out - buf);
}

int _mi_snprintf(char* buf, size_t buflen, const char* fmt, ...) {
  va_list args;
  va_start(args, fmt);
  const int written = _mi_vsnprintf(buf, buflen, fmt, args);
  va_end(args);
  return written;
}

#undef MI_NEXTC


// --------------------------------------------------------
// generic trailing and leading zero count, and popcount
// --------------------------------------------------------

#if !MI_HAS_FAST_BITSCAN

static size_t mi_ctz_generic32(uint32_t x) {
  // de Bruijn multiplication, see <http://keithandkatie.com/keith/papers/debruijn.html>
  static const uint8_t debruijn[32] = {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };
  if (x==0) return 32;
  return debruijn[(uint32_t)((x & (~x + 1U)) * (uint32_t)(0x077CB531U)) >> 27];
}

static size_t mi_clz_generic32(uint32_t x) {
  // de Bruijn multiplication, see <http://keithandkatie.com/keith/papers/debruijn.html>
  static const uint8_t debruijn[32] = {
    31, 22, 30, 21, 18, 10, 29, 2, 20, 17, 15, 13, 9, 6, 28, 1,
    23, 19, 11, 3, 16, 14, 7, 24, 12, 4, 8, 25, 5, 26, 27, 0
  };
  if (x==0) return 32;
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  return debruijn[(uint32_t)(x * (uint32_t)(0x07C4ACDDU)) >> 27];
}

size_t _mi_ctz_generic(size_t x) {
  if (x==0) return MI_SIZE_BITS;
  #if (MI_SIZE_BITS <= 32)
    return mi_ctz_generic32((uint32_t)x);
  #else
    const uint32_t lo = (uint32_t)x;
    if (lo != 0) {
      return mi_ctz_generic32(lo);
    }
    else {
      return (32 + mi_ctz_generic32((uint32_t)(x>>32)));
    }
  #endif
}

size_t _mi_clz_generic(size_t x) {
  if (x==0) return MI_SIZE_BITS;
  #if (MI_SIZE_BITS <= 32)
    return mi_clz_generic32((uint32_t)x);
  #else
    const uint32_t hi = (uint32_t)(x>>32);
    if (hi != 0) {
      return mi_clz_generic32(hi);
    }
    else {
      return 32 + mi_clz_generic32((uint32_t)x);
    }
  #endif
}

#endif // bit scan


#if MI_SIZE_SIZE == 4
#define mi_mask_even_bits32      (0x55555555)
#define mi_mask_even_pairs32     (0x33333333)
#define mi_mask_even_nibbles32   (0x0F0F0F0F)

// sum of all the bytes in `x` if it is guaranteed that the sum < 256!
static size_t mi_byte_sum32(uint32_t x) {
  // perform `x * 0x01010101`: the highest byte contains the sum of all bytes.
  x += (x << 8);
  x += (x << 16);
  return (size_t)(x >> 24);
}

static size_t mi_popcount_generic32(uint32_t x) {
  // first count each 2-bit group `a`, where: a==0b00 -> 00, a==0b01 -> 01, a==0b10 -> 01, a==0b11 -> 10
  // in other words, `a - (a>>1)`; to do this in parallel, we need to mask to prevent spilling a bit pair
  // into the lower bit-pair:
  x = x - ((x >> 1) & mi_mask_even_bits32);
  // add the 2-bit pair results
  x = (x & mi_mask_even_pairs32) + ((x >> 2) & mi_mask_even_pairs32);
  // add the 4-bit nibble results
  x = (x + (x >> 4)) & mi_mask_even_nibbles32;
  // each byte now has a count of its bits, we can sum them now:
  return mi_byte_sum32(x);
}

mi_decl_noinline size_t _mi_popcount_generic(size_t x) {
  if (x<=1) return x;
  if (~x==0) return MI_SIZE_BITS;
  return mi_popcount_generic32(x);
}

#else
#define mi_mask_even_bits64      (0x5555555555555555)
#define mi_mask_even_pairs64     (0x3333333333333333)
#define mi_mask_even_nibbles64   (0x0F0F0F0F0F0F0F0F)

// sum of all the bytes in `x` if it is guaranteed that the sum < 256!
static size_t mi_byte_sum64(uint64_t x) {
  x += (x << 8);
  x += (x << 16);
  x += (x << 32);
  return (size_t)(x >> 56);
}

static size_t mi_popcount_generic64(uint64_t x) {
  x = x - ((x >> 1) & mi_mask_even_bits64);
  x = (x & mi_mask_even_pairs64) + ((x >> 2) & mi_mask_even_pairs64);
  x = (x + (x >> 4)) & mi_mask_even_nibbles64;
  return mi_byte_sum64(x);
}

mi_decl_noinline size_t _mi_popcount_generic(size_t x) {
  if (x<=1) return x;
  if (~x==0) return MI_SIZE_BITS;
  return mi_popcount_generic64(x);
}
#endif