Permalink
Switch branches/tags
Nothing to show
Find file Copy path
14406 lines (12648 sloc) 452 KB
/* stb.h - v2.31 - Sean's Tool Box -- public domain -- http://nothings.org/stb.h
no warranty is offered or implied; use this code at your own risk
This is a single header file with a bunch of useful utilities
for getting stuff done in C/C++.
Documentation: http://nothings.org/stb/stb_h.html
Unit tests: http://nothings.org/stb/stb.c
============================================================================
You MUST
#define STB_DEFINE
in EXACTLY _one_ C or C++ file that includes this header, BEFORE the
include, like this:
#define STB_DEFINE
#include "stb.h"
All other files should just #include "stb.h" without the #define.
============================================================================
Version History
2.31 stb_ucharcmp
2.30 MinGW fix
2.29 attempt to fix use of swprintf()
2.28 various new functionality
2.27 test _WIN32 not WIN32 in STB_THREADS
2.26 various warning & bugfixes
2.25 various warning & bugfixes
2.24 various warning & bugfixes
2.23 fix 2.22
2.22 64-bit fixes from '!='; fix stb_sdict_copy() to have preferred name
2.21 utf-8 decoder rejects "overlong" encodings; attempted 64-bit improvements
2.20 fix to hash "copy" function--reported by someone with handle "!="
2.19 ???
2.18 stb_readdir_subdirs_mask
2.17 stb_cfg_dir
2.16 fix stb_bgio_, add stb_bgio_stat(); begin a streaming wrapper
2.15 upgraded hash table template to allow:
- aggregate keys (explicit comparison func for EMPTY and DEL keys)
- "static" implementations (so they can be culled if unused)
2.14 stb_mprintf
2.13 reduce identifiable strings in STB_NO_STB_STRINGS
2.12 fix STB_ONLY -- lots of uint32s, TRUE/FALSE things had crept in
2.11 fix bug in stb_dirtree_get() which caused "c://path" sorts of stuff
2.10 STB_F(), STB_I() inline constants (also KI,KU,KF,KD)
2.09 stb_box_face_vertex_axis_side
2.08 bugfix stb_trimwhite()
2.07 colored printing in windows (why are we in 1985?)
2.06 comparison functions are now functions-that-return-functions and
accept a struct-offset as a parameter (not thread-safe)
2.05 compile and pass tests under Linux (but no threads); thread cleanup
2.04 stb_cubic_bezier_1d, smoothstep, avoid dependency on registry
2.03 ?
2.02 remove integrated documentation
2.01 integrate various fixes; stb_force_uniprocessor
2.00 revised stb_dupe to use multiple hashes
1.99 stb_charcmp
1.98 stb_arr_deleten, stb_arr_insertn
1.97 fix stb_newell_normal()
1.96 stb_hash_number()
1.95 hack stb__rec_max; clean up recursion code to use new functions
1.94 stb_dirtree; rename stb_extra to stb_ptrmap
1.93 stb_sem_new() API cleanup (no blockflag-starts blocked; use 'extra')
1.92 stb_threadqueue--multi reader/writer queue, fixed size or resizeable
1.91 stb_bgio_* for reading disk asynchronously
1.90 stb_mutex uses CRITICAL_REGION; new stb_sync primitive for thread
joining; workqueue supports stb_sync instead of stb_semaphore
1.89 support ';' in constant-string wildcards; stb_mutex wrapper (can
implement with EnterCriticalRegion eventually)
1.88 portable threading API (only for win32 so far); worker thread queue
1.87 fix wildcard handling in stb_readdir_recursive
1.86 support ';' in wildcards
1.85 make stb_regex work with non-constant strings;
beginnings of stb_introspect()
1.84 (forgot to make notes)
1.83 whoops, stb_keep_if_different wasn't deleting the temp file
1.82 bring back stb_compress from stb_file.h for cmirror
1.81 various bugfixes, STB_FASTMALLOC_INIT inits FASTMALLOC in release
1.80 stb_readdir returns utf8; write own utf8-utf16 because lib was wrong
1.79 stb_write
1.78 calloc() support for malloc wrapper, STB_FASTMALLOC
1.77 STB_FASTMALLOC
1.76 STB_STUA - Lua-like language; (stb_image, stb_csample, stb_bilinear)
1.75 alloc/free array of blocks; stb_hheap bug; a few stb_ps_ funcs;
hash*getkey, hash*copy; stb_bitset; stb_strnicmp; bugfix stb_bst
1.74 stb_replaceinplace; use stdlib C function to convert utf8 to UTF-16
1.73 fix performance bug & leak in stb_ischar (C++ port lost a 'static')
1.72 remove stb_block, stb_block_manager, stb_decompress (to stb_file.h)
1.71 stb_trimwhite, stb_tokens_nested, etc.
1.70 back out 1.69 because it might problemize mixed builds; stb_filec()
1.69 (stb_file returns 'char *' in C++)
1.68 add a special 'tree root' data type for stb_bst; stb_arr_end
1.67 full C++ port. (stb_block_manager)
1.66 stb_newell_normal
1.65 stb_lex_item_wild -- allow wildcard items which MUST match entirely
1.64 stb_data
1.63 stb_log_name
1.62 stb_define_sort; C++ cleanup
1.61 stb_hash_fast -- Paul Hsieh's hash function (beats Bob Jenkins'?)
1.60 stb_delete_directory_recursive
1.59 stb_readdir_recursive
1.58 stb_bst variant with parent pointer for O(1) iteration, not O(log N)
1.57 replace LCG random with Mersenne Twister (found a public domain one)
1.56 stb_perfect_hash, stb_ischar, stb_regex
1.55 new stb_bst API allows multiple BSTs per node (e.g. secondary keys)
1.54 bugfix: stb_define_hash, stb_wildmatch, regexp
1.53 stb_define_hash; recoded stb_extra, stb_sdict use it
1.52 stb_rand_define, stb_bst, stb_reverse
1.51 fix 'stb_arr_setlen(NULL, 0)'
1.50 stb_wordwrap
1.49 minor improvements to enable the scripting language
1.48 better approach for stb_arr using stb_malloc; more invasive, clearer
1.47 stb_lex (lexes stb.h at 1.5ML/s on 3Ghz P4; 60/70% of optimal/flex)
1.46 stb_wrapper_*, STB_MALLOC_WRAPPER
1.45 lightly tested DFA acceleration of regexp searching
1.44 wildcard matching & searching; regexp matching & searching
1.43 stb_temp
1.42 allow stb_arr to use stb_malloc/realloc; note this is global
1.41 make it compile in C++; (disable stb_arr in C++)
1.40 stb_dupe tweak; stb_swap; stb_substr
1.39 stb_dupe; improve stb_file_max to be less stupid
1.38 stb_sha1_file: generate sha1 for file, even > 4GB
1.37 stb_file_max; partial support for utf8 filenames in Windows
1.36 remove STB__NO_PREFIX - poor interaction with IDE, not worth it
streamline stb_arr to make it separately publishable
1.35 bugfixes for stb_sdict, stb_malloc(0), stristr
1.34 (streaming interfaces for stb_compress)
1.33 stb_alloc; bug in stb_getopt; remove stb_overflow
1.32 (stb_compress returns, smaller&faster; encode window & 64-bit len)
1.31 stb_prefix_count
1.30 (STB__NO_PREFIX - remove stb_ prefixes for personal projects)
1.29 stb_fput_varlen64, etc.
1.28 stb_sha1
1.27 ?
1.26 stb_extra
1.25 ?
1.24 stb_copyfile
1.23 stb_readdir
1.22 ?
1.21 ?
1.20 ?
1.19 ?
1.18 ?
1.17 ?
1.16 ?
1.15 stb_fixpath, stb_splitpath, stb_strchr2
1.14 stb_arr
1.13 ?stb, stb_log, stb_fatal
1.12 ?stb_hash2
1.11 miniML
1.10 stb_crc32, stb_adler32
1.09 stb_sdict
1.08 stb_bitreverse, stb_ispow2, stb_big32
stb_fopen, stb_fput_varlen, stb_fput_ranged
stb_fcmp, stb_feq
1.07 (stb_encompress)
1.06 stb_compress
1.05 stb_tokens, (stb_hheap)
1.04 stb_rand
1.03 ?(s-strings)
1.02 ?stb_filelen, stb_tokens
1.01 stb_tolower
1.00 stb_hash, stb_intcmp
stb_file, stb_stringfile, stb_fgets
stb_prefix, stb_strlower, stb_strtok
stb_image
(stb_array), (stb_arena)
Parenthesized items have since been removed.
LICENSE
See end of file for license information.
CREDITS
Written by Sean Barrett.
Fixes:
Philipp Wiesemann
Robert Nix
r-lyeh
blackpawn
github:Mojofreem
Ryan Whitworth
Vincent Isambart
Mike Sartain
Eugene Opalev
Tim Sjostrand
github:infatum
Dave Butler (Croepha)
*/
#include <stdarg.h>
#ifndef STB__INCLUDE_STB_H
#define STB__INCLUDE_STB_H
#define STB_VERSION 1
#ifdef STB_INTROSPECT
#define STB_DEFINE
#endif
#ifdef STB_DEFINE_THREADS
#ifndef STB_DEFINE
#define STB_DEFINE
#endif
#ifndef STB_THREADS
#define STB_THREADS
#endif
#endif
#if defined(_WIN32) && !defined(__MINGW32__)
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#ifndef _CRT_NONSTDC_NO_DEPRECATE
#define _CRT_NONSTDC_NO_DEPRECATE
#endif
#ifndef _CRT_NON_CONFORMING_SWPRINTFS
#define _CRT_NON_CONFORMING_SWPRINTFS
#endif
#if !defined(_MSC_VER) || _MSC_VER > 1700
#include <intrin.h> // _BitScanReverse
#endif
#endif
#include <stdlib.h> // stdlib could have min/max
#include <stdio.h> // need FILE
#include <string.h> // stb_define_hash needs memcpy/memset
#include <time.h> // stb_dirtree
#ifdef __MINGW32__
#include <fcntl.h> // O_RDWR
#endif
#ifdef STB_PERSONAL
typedef int Bool;
#define False 0
#define True 1
#endif
#ifdef STB_MALLOC_WRAPPER_PAGED
#define STB_MALLOC_WRAPPER_DEBUG
#endif
#ifdef STB_MALLOC_WRAPPER_DEBUG
#define STB_MALLOC_WRAPPER
#endif
#ifdef STB_MALLOC_WRAPPER_FASTMALLOC
#define STB_FASTMALLOC
#define STB_MALLOC_WRAPPER
#endif
#ifdef STB_FASTMALLOC
#ifndef _WIN32
#undef STB_FASTMALLOC
#endif
#endif
#ifdef STB_DEFINE
#include <assert.h>
#include <stdarg.h>
#include <stddef.h>
#include <ctype.h>
#include <math.h>
#ifndef _WIN32
#include <unistd.h>
#else
#include <io.h> // _mktemp
#include <direct.h> // _rmdir
#endif
#include <sys/types.h> // stat()/_stat()
#include <sys/stat.h> // stat()/_stat()
#endif
#define stb_min(a,b) ((a) < (b) ? (a) : (b))
#define stb_max(a,b) ((a) > (b) ? (a) : (b))
#ifndef STB_ONLY
#if !defined(__cplusplus) && !defined(min) && !defined(max)
#define min(x,y) stb_min(x,y)
#define max(x,y) stb_max(x,y)
#endif
#ifndef M_PI
#define M_PI 3.14159265358979323846f
#endif
#ifndef TRUE
#define TRUE 1
#define FALSE 0
#endif
#ifndef deg2rad
#define deg2rad(a) ((a)*(M_PI/180))
#endif
#ifndef rad2deg
#define rad2deg(a) ((a)*(180/M_PI))
#endif
#ifndef swap
#ifndef __cplusplus
#define swap(TYPE,a,b) \
do { TYPE stb__t; stb__t = (a); (a) = (b); (b) = stb__t; } while (0)
#endif
#endif
typedef unsigned char uint8 ;
typedef signed char int8 ;
typedef unsigned short uint16;
typedef signed short int16;
#if defined(STB_USE_LONG_FOR_32_BIT_INT) || defined(STB_LONG32)
typedef unsigned long uint32;
typedef signed long int32;
#else
typedef unsigned int uint32;
typedef signed int int32;
#endif
typedef unsigned char uchar ;
typedef unsigned short ushort;
typedef unsigned int uint ;
typedef unsigned long ulong ;
// produce compile errors if the sizes aren't right
typedef char stb__testsize16[sizeof(int16)==2];
typedef char stb__testsize32[sizeof(int32)==4];
#endif
#ifndef STB_TRUE
#define STB_TRUE 1
#define STB_FALSE 0
#endif
// if we're STB_ONLY, can't rely on uint32 or even uint, so all the
// variables we'll use herein need typenames prefixed with 'stb':
typedef unsigned char stb_uchar;
typedef unsigned char stb_uint8;
typedef unsigned int stb_uint;
typedef unsigned short stb_uint16;
typedef short stb_int16;
typedef signed char stb_int8;
#if defined(STB_USE_LONG_FOR_32_BIT_INT) || defined(STB_LONG32)
typedef unsigned long stb_uint32;
typedef long stb_int32;
#else
typedef unsigned int stb_uint32;
typedef int stb_int32;
#endif
typedef char stb__testsize2_16[sizeof(stb_uint16)==2 ? 1 : -1];
typedef char stb__testsize2_32[sizeof(stb_uint32)==4 ? 1 : -1];
#ifdef _MSC_VER
typedef unsigned __int64 stb_uint64;
typedef __int64 stb_int64;
#define STB_IMM_UINT64(literalui64) (literalui64##ui64)
#define STB_IMM_INT64(literali64) (literali64##i64)
#else
// ??
typedef unsigned long long stb_uint64;
typedef long long stb_int64;
#define STB_IMM_UINT64(literalui64) (literalui64##ULL)
#define STB_IMM_INT64(literali64) (literali64##LL)
#endif
typedef char stb__testsize2_64[sizeof(stb_uint64)==8 ? 1 : -1];
// add platform-specific ways of checking for sizeof(char*) == 8,
// and make those define STB_PTR64
#if defined(_WIN64) || defined(__x86_64__) || defined(__ia64__) || defined(__LP64__)
#define STB_PTR64
#endif
#ifdef STB_PTR64
typedef char stb__testsize2_ptr[sizeof(char *) == 8];
typedef stb_uint64 stb_uinta;
typedef stb_int64 stb_inta;
#else
typedef char stb__testsize2_ptr[sizeof(char *) == 4];
typedef stb_uint32 stb_uinta;
typedef stb_int32 stb_inta;
#endif
typedef char stb__testsize2_uinta[sizeof(stb_uinta)==sizeof(char*) ? 1 : -1];
// if so, we should define an int type that is the pointer size. until then,
// we'll have to make do with this (which is not the same at all!)
typedef union
{
unsigned int i;
void * p;
} stb_uintptr;
#ifdef __cplusplus
#define STB_EXTERN extern "C"
#else
#define STB_EXTERN extern
#endif
// check for well-known debug defines
#if defined(DEBUG) || defined(_DEBUG) || defined(DBG)
#ifndef NDEBUG
#define STB_DEBUG
#endif
#endif
#ifdef STB_DEBUG
#include <assert.h>
#endif
STB_EXTERN void stb_wrapper_malloc(void *newp, int sz, char *file, int line);
STB_EXTERN void stb_wrapper_free(void *oldp, char *file, int line);
STB_EXTERN void stb_wrapper_realloc(void *oldp, void *newp, int sz, char *file, int line);
STB_EXTERN void stb_wrapper_calloc(size_t num, size_t sz, char *file, int line);
STB_EXTERN void stb_wrapper_listall(void (*func)(void *ptr, int sz, char *file, int line));
STB_EXTERN void stb_wrapper_dump(char *filename);
STB_EXTERN int stb_wrapper_allocsize(void *oldp);
STB_EXTERN void stb_wrapper_check(void *oldp);
#ifdef STB_DEFINE
// this is a special function used inside malloc wrapper
// to do allocations that aren't tracked (to avoid
// reentrancy). Of course if someone _else_ wraps realloc,
// this breaks, but if they're doing that AND the malloc
// wrapper they need to explicitly check for reentrancy.
//
// only define realloc_raw() and we do realloc(NULL,sz)
// for malloc() and realloc(p,0) for free().
static void * stb__realloc_raw(void *p, int sz)
{
if (p == NULL) return malloc(sz);
if (sz == 0) { free(p); return NULL; }
return realloc(p,sz);
}
#endif
#ifdef _WIN32
STB_EXTERN void * stb_smalloc(size_t sz);
STB_EXTERN void stb_sfree(void *p);
STB_EXTERN void * stb_srealloc(void *p, size_t sz);
STB_EXTERN void * stb_scalloc(size_t n, size_t sz);
STB_EXTERN char * stb_sstrdup(char *s);
#endif
#ifdef STB_FASTMALLOC
#define malloc stb_smalloc
#define free stb_sfree
#define realloc stb_srealloc
#define strdup stb_sstrdup
#define calloc stb_scalloc
#endif
#ifndef STB_MALLOC_ALLCHECK
#define stb__check(p) 1
#else
#ifndef STB_MALLOC_WRAPPER
#error STB_MALLOC_ALLCHECK requires STB_MALLOC_WRAPPER
#else
#define stb__check(p) stb_mcheck(p)
#endif
#endif
#ifdef STB_MALLOC_WRAPPER
STB_EXTERN void * stb__malloc(int, char *, int);
STB_EXTERN void * stb__realloc(void *, int, char *, int);
STB_EXTERN void * stb__calloc(size_t n, size_t s, char *, int);
STB_EXTERN void stb__free(void *, char *file, int);
STB_EXTERN char * stb__strdup(char *s, char *file, int);
STB_EXTERN void stb_malloc_checkall(void);
STB_EXTERN void stb_malloc_check_counter(int init_delay, int rep_delay);
#ifndef STB_MALLOC_WRAPPER_DEBUG
#define stb_mcheck(p) 1
#else
STB_EXTERN int stb_mcheck(void *);
#endif
#ifdef STB_DEFINE
#ifdef STB_MALLOC_WRAPPER_DEBUG
#define STB__PAD 32
#define STB__BIAS 16
#define STB__SIG 0x51b01234
#define STB__FIXSIZE(sz) (((sz+3) & ~3) + STB__PAD)
#define STB__ptr(x,y) ((char *) (x) + (y))
#else
#define STB__ptr(x,y) (x)
#define STB__FIXSIZE(sz) (sz)
#endif
#ifdef STB_MALLOC_WRAPPER_DEBUG
int stb_mcheck(void *p)
{
unsigned int sz;
if (p == NULL) return 1;
p = ((char *) p) - STB__BIAS;
sz = * (unsigned int *) p;
assert(* (unsigned int *) STB__ptr(p,4) == STB__SIG);
assert(* (unsigned int *) STB__ptr(p,8) == STB__SIG);
assert(* (unsigned int *) STB__ptr(p,12) == STB__SIG);
assert(* (unsigned int *) STB__ptr(p,sz-4) == STB__SIG+1);
assert(* (unsigned int *) STB__ptr(p,sz-8) == STB__SIG+1);
assert(* (unsigned int *) STB__ptr(p,sz-12) == STB__SIG+1);
assert(* (unsigned int *) STB__ptr(p,sz-16) == STB__SIG+1);
stb_wrapper_check(STB__ptr(p, STB__BIAS));
return 1;
}
static void stb__check2(void *p, int sz, char *file, int line)
{
stb_mcheck(p);
}
void stb_malloc_checkall(void)
{
stb_wrapper_listall(stb__check2);
}
#else
void stb_malloc_checkall(void) { }
#endif
static int stb__malloc_wait=(1 << 30), stb__malloc_next_wait = (1 << 30), stb__malloc_iter;
void stb_malloc_check_counter(int init_delay, int rep_delay)
{
stb__malloc_wait = init_delay;
stb__malloc_next_wait = rep_delay;
}
void stb_mcheck_all(void)
{
#ifdef STB_MALLOC_WRAPPER_DEBUG
++stb__malloc_iter;
if (--stb__malloc_wait <= 0) {
stb_malloc_checkall();
stb__malloc_wait = stb__malloc_next_wait;
}
#endif
}
#ifdef STB_MALLOC_WRAPPER_PAGED
#define STB__WINDOWS_PAGE (1 << 12)
#ifndef _WINDOWS_
STB_EXTERN __declspec(dllimport) void * __stdcall VirtualAlloc(void *p, unsigned long size, unsigned long type, unsigned long protect);
STB_EXTERN __declspec(dllimport) int __stdcall VirtualFree(void *p, unsigned long size, unsigned long freetype);
#endif
#endif
static void *stb__malloc_final(int sz)
{
#ifdef STB_MALLOC_WRAPPER_PAGED
int aligned = (sz + STB__WINDOWS_PAGE - 1) & ~(STB__WINDOWS_PAGE-1);
char *p = VirtualAlloc(NULL, aligned + STB__WINDOWS_PAGE, 0x2000, 0x04); // RESERVE, READWRITE
if (p == NULL) return p;
VirtualAlloc(p, aligned, 0x1000, 0x04); // COMMIT, READWRITE
return p;
#else
return malloc(sz);
#endif
}
static void stb__free_final(void *p)
{
#ifdef STB_MALLOC_WRAPPER_PAGED
VirtualFree(p, 0, 0x8000); // RELEASE
#else
free(p);
#endif
}
int stb__malloc_failure;
static void *stb__realloc_final(void *p, int sz, int old_sz)
{
#ifdef STB_MALLOC_WRAPPER_PAGED
void *q = stb__malloc_final(sz);
if (q == NULL)
return ++stb__malloc_failure, q;
// @TODO: deal with p being smaller!
memcpy(q, p, sz < old_sz ? sz : old_sz);
stb__free_final(p);
return q;
#else
return realloc(p,sz);
#endif
}
void stb__free(void *p, char *file, int line)
{
stb_mcheck_all();
if (!p) return;
#ifdef STB_MALLOC_WRAPPER_DEBUG
stb_mcheck(p);
#endif
stb_wrapper_free(p,file,line);
#ifdef STB_MALLOC_WRAPPER_DEBUG
p = STB__ptr(p,-STB__BIAS);
* (unsigned int *) STB__ptr(p,0) = 0xdeadbeef;
* (unsigned int *) STB__ptr(p,4) = 0xdeadbeef;
* (unsigned int *) STB__ptr(p,8) = 0xdeadbeef;
* (unsigned int *) STB__ptr(p,12) = 0xdeadbeef;
#endif
stb__free_final(p);
}
void * stb__malloc(int sz, char *file, int line)
{
void *p;
stb_mcheck_all();
if (sz == 0) return NULL;
p = stb__malloc_final(STB__FIXSIZE(sz));
if (p == NULL) p = stb__malloc_final(STB__FIXSIZE(sz));
if (p == NULL) p = stb__malloc_final(STB__FIXSIZE(sz));
if (p == NULL) {
++stb__malloc_failure;
#ifdef STB_MALLOC_WRAPPER_DEBUG
stb_malloc_checkall();
#endif
return p;
}
#ifdef STB_MALLOC_WRAPPER_DEBUG
* (int *) STB__ptr(p,0) = STB__FIXSIZE(sz);
* (unsigned int *) STB__ptr(p,4) = STB__SIG;
* (unsigned int *) STB__ptr(p,8) = STB__SIG;
* (unsigned int *) STB__ptr(p,12) = STB__SIG;
* (unsigned int *) STB__ptr(p,STB__FIXSIZE(sz)-4) = STB__SIG+1;
* (unsigned int *) STB__ptr(p,STB__FIXSIZE(sz)-8) = STB__SIG+1;
* (unsigned int *) STB__ptr(p,STB__FIXSIZE(sz)-12) = STB__SIG+1;
* (unsigned int *) STB__ptr(p,STB__FIXSIZE(sz)-16) = STB__SIG+1;
p = STB__ptr(p, STB__BIAS);
#endif
stb_wrapper_malloc(p,sz,file,line);
return p;
}
void * stb__realloc(void *p, int sz, char *file, int line)
{
void *q;
stb_mcheck_all();
if (p == NULL) return stb__malloc(sz,file,line);
if (sz == 0 ) { stb__free(p,file,line); return NULL; }
#ifdef STB_MALLOC_WRAPPER_DEBUG
stb_mcheck(p);
p = STB__ptr(p,-STB__BIAS);
#endif
#ifdef STB_MALLOC_WRAPPER_PAGED
{
int n = stb_wrapper_allocsize(STB__ptr(p,STB__BIAS));
if (!n)
stb_wrapper_check(STB__ptr(p,STB__BIAS));
q = stb__realloc_final(p, STB__FIXSIZE(sz), STB__FIXSIZE(n));
}
#else
q = realloc(p, STB__FIXSIZE(sz));
#endif
if (q == NULL)
return ++stb__malloc_failure, q;
#ifdef STB_MALLOC_WRAPPER_DEBUG
* (int *) STB__ptr(q,0) = STB__FIXSIZE(sz);
* (unsigned int *) STB__ptr(q,4) = STB__SIG;
* (unsigned int *) STB__ptr(q,8) = STB__SIG;
* (unsigned int *) STB__ptr(q,12) = STB__SIG;
* (unsigned int *) STB__ptr(q,STB__FIXSIZE(sz)-4) = STB__SIG+1;
* (unsigned int *) STB__ptr(q,STB__FIXSIZE(sz)-8) = STB__SIG+1;
* (unsigned int *) STB__ptr(q,STB__FIXSIZE(sz)-12) = STB__SIG+1;
* (unsigned int *) STB__ptr(q,STB__FIXSIZE(sz)-16) = STB__SIG+1;
q = STB__ptr(q, STB__BIAS);
p = STB__ptr(p, STB__BIAS);
#endif
stb_wrapper_realloc(p,q,sz,file,line);
return q;
}
STB_EXTERN int stb_log2_ceil(unsigned int);
static void *stb__calloc(size_t n, size_t sz, char *file, int line)
{
void *q;
stb_mcheck_all();
if (n == 0 || sz == 0) return NULL;
if (stb_log2_ceil(n) + stb_log2_ceil(sz) >= 32) return NULL;
q = stb__malloc(n*sz, file, line);
if (q) memset(q, 0, n*sz);
return q;
}
char * stb__strdup(char *s, char *file, int line)
{
char *p;
stb_mcheck_all();
p = stb__malloc(strlen(s)+1, file, line);
if (!p) return p;
strcpy(p, s);
return p;
}
#endif // STB_DEFINE
#ifdef STB_FASTMALLOC
#undef malloc
#undef realloc
#undef free
#undef strdup
#undef calloc
#endif
// include everything that might define these, BEFORE making macros
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#define malloc(s) stb__malloc ( s, __FILE__, __LINE__)
#define realloc(p,s) stb__realloc(p,s, __FILE__, __LINE__)
#define calloc(n,s) stb__calloc (n,s, __FILE__, __LINE__)
#define free(p) stb__free (p, __FILE__, __LINE__)
#define strdup(p) stb__strdup (p, __FILE__, __LINE__)
#endif
//////////////////////////////////////////////////////////////////////////////
//
// Windows pretty display
//
STB_EXTERN void stbprint(const char *fmt, ...);
STB_EXTERN char *stb_sprintf(const char *fmt, ...);
STB_EXTERN char *stb_mprintf(const char *fmt, ...);
STB_EXTERN int stb_snprintf(char *s, size_t n, const char *fmt, ...);
STB_EXTERN int stb_vsnprintf(char *s, size_t n, const char *fmt, va_list v);
#ifdef STB_DEFINE
int stb_vsnprintf(char *s, size_t n, const char *fmt, va_list v)
{
int res;
#ifdef _WIN32
// Could use "_vsnprintf_s(s, n, _TRUNCATE, fmt, v)" ?
res = _vsnprintf(s,n,fmt,v);
#else
res = vsnprintf(s,n,fmt,v);
#endif
if (n) s[n-1] = 0;
// Unix returns length output would require, Windows returns negative when truncated.
return (res >= (int) n || res < 0) ? -1 : res;
}
int stb_snprintf(char *s, size_t n, const char *fmt, ...)
{
int res;
va_list v;
va_start(v,fmt);
res = stb_vsnprintf(s, n, fmt, v);
va_end(v);
return res;
}
char *stb_sprintf(const char *fmt, ...)
{
static char buffer[1024];
va_list v;
va_start(v,fmt);
stb_vsnprintf(buffer,1024,fmt,v);
va_end(v);
return buffer;
}
char *stb_mprintf(const char *fmt, ...)
{
static char buffer[1024];
va_list v;
va_start(v,fmt);
stb_vsnprintf(buffer,1024,fmt,v);
va_end(v);
return strdup(buffer);
}
#ifdef _WIN32
#ifndef _WINDOWS_
STB_EXTERN __declspec(dllimport) int __stdcall WriteConsoleA(void *, const void *, unsigned int, unsigned int *, void *);
STB_EXTERN __declspec(dllimport) void * __stdcall GetStdHandle(unsigned int);
STB_EXTERN __declspec(dllimport) int __stdcall SetConsoleTextAttribute(void *, unsigned short);
#endif
static void stb__print_one(void *handle, char *s, int len)
{
if (len)
if (WriteConsoleA(handle, s, len, NULL,NULL))
fwrite(s, 1, len, stdout); // if it fails, maybe redirected, so do normal
}
static void stb__print(char *s)
{
void *handle = GetStdHandle((unsigned int) -11); // STD_OUTPUT_HANDLE
int pad=0; // number of padding characters to add
char *t = s;
while (*s) {
int lpad;
while (*s && *s != '{') {
if (pad) {
if (*s == '\r' || *s == '\n')
pad = 0;
else if (s[0] == ' ' && s[1] == ' ') {
stb__print_one(handle, t, s-t);
t = s;
while (pad) {
stb__print_one(handle, t, 1);
--pad;
}
}
}
++s;
}
if (!*s) break;
stb__print_one(handle, t, s-t);
if (s[1] == '{') {
++s;
continue;
}
if (s[1] == '#') {
t = s+3;
if (isxdigit(s[2]))
if (isdigit(s[2]))
SetConsoleTextAttribute(handle, s[2] - '0');
else
SetConsoleTextAttribute(handle, tolower(s[2]) - 'a' + 10);
else {
SetConsoleTextAttribute(handle, 0x0f);
t=s+2;
}
} else if (s[1] == '!') {
SetConsoleTextAttribute(handle, 0x0c);
t = s+2;
} else if (s[1] == '@') {
SetConsoleTextAttribute(handle, 0x09);
t = s+2;
} else if (s[1] == '$') {
SetConsoleTextAttribute(handle, 0x0a);
t = s+2;
} else {
SetConsoleTextAttribute(handle, 0x08); // 0,7,8,15 => shades of grey
t = s+1;
}
lpad = (t-s);
s = t;
while (*s && *s != '}') ++s;
if (!*s) break;
stb__print_one(handle, t, s-t);
if (s[1] == '}') {
t = s+2;
} else {
pad += 1+lpad;
t = s+1;
}
s=t;
SetConsoleTextAttribute(handle, 0x07);
}
stb__print_one(handle, t, s-t);
SetConsoleTextAttribute(handle, 0x07);
}
void stbprint(const char *fmt, ...)
{
int res;
char buffer[1024];
char *tbuf = buffer;
va_list v;
va_start(v,fmt);
res = stb_vsnprintf(buffer, sizeof(buffer), fmt, v);
va_end(v);
if (res < 0) {
tbuf = (char *) malloc(16384);
va_start(v,fmt);
res = _vsnprintf(tbuf,16384, fmt, v);
va_end(v);
tbuf[16383] = 0;
}
stb__print(tbuf);
if (tbuf != buffer)
free(tbuf);
}
#else // _WIN32
void stbprint(const char *fmt, ...)
{
va_list v;
va_start(v,fmt);
vprintf(fmt,v);
va_end(v);
}
#endif // _WIN32
#endif // STB_DEFINE
//////////////////////////////////////////////////////////////////////////////
//
// Windows UTF8 filename handling
//
// Windows stupidly treats 8-bit filenames as some dopey code page,
// rather than utf-8. If we want to use utf8 filenames, we have to
// convert them to WCHAR explicitly and call WCHAR versions of the
// file functions. So, ok, we do.
#ifdef _WIN32
#define stb__fopen(x,y) _wfopen((const wchar_t *)stb__from_utf8(x), (const wchar_t *)stb__from_utf8_alt(y))
#define stb__windows(x,y) x
#else
#define stb__fopen(x,y) fopen(x,y)
#define stb__windows(x,y) y
#endif
typedef unsigned short stb__wchar;
STB_EXTERN stb__wchar * stb_from_utf8(stb__wchar *buffer, char *str, int n);
STB_EXTERN char * stb_to_utf8 (char *buffer, stb__wchar *str, int n);
STB_EXTERN stb__wchar *stb__from_utf8(char *str);
STB_EXTERN stb__wchar *stb__from_utf8_alt(char *str);
STB_EXTERN char *stb__to_utf8(stb__wchar *str);
#ifdef STB_DEFINE
stb__wchar * stb_from_utf8(stb__wchar *buffer, char *ostr, int n)
{
unsigned char *str = (unsigned char *) ostr;
stb_uint32 c;
int i=0;
--n;
while (*str) {
if (i >= n)
return NULL;
if (!(*str & 0x80))
buffer[i++] = *str++;
else if ((*str & 0xe0) == 0xc0) {
if (*str < 0xc2) return NULL;
c = (*str++ & 0x1f) << 6;
if ((*str & 0xc0) != 0x80) return NULL;
buffer[i++] = c + (*str++ & 0x3f);
} else if ((*str & 0xf0) == 0xe0) {
if (*str == 0xe0 && (str[1] < 0xa0 || str[1] > 0xbf)) return NULL;
if (*str == 0xed && str[1] > 0x9f) return NULL; // str[1] < 0x80 is checked below
c = (*str++ & 0x0f) << 12;
if ((*str & 0xc0) != 0x80) return NULL;
c += (*str++ & 0x3f) << 6;
if ((*str & 0xc0) != 0x80) return NULL;
buffer[i++] = c + (*str++ & 0x3f);
} else if ((*str & 0xf8) == 0xf0) {
if (*str > 0xf4) return NULL;
if (*str == 0xf0 && (str[1] < 0x90 || str[1] > 0xbf)) return NULL;
if (*str == 0xf4 && str[1] > 0x8f) return NULL; // str[1] < 0x80 is checked below
c = (*str++ & 0x07) << 18;
if ((*str & 0xc0) != 0x80) return NULL;
c += (*str++ & 0x3f) << 12;
if ((*str & 0xc0) != 0x80) return NULL;
c += (*str++ & 0x3f) << 6;
if ((*str & 0xc0) != 0x80) return NULL;
c += (*str++ & 0x3f);
// utf-8 encodings of values used in surrogate pairs are invalid
if ((c & 0xFFFFF800) == 0xD800) return NULL;
if (c >= 0x10000) {
c -= 0x10000;
if (i + 2 > n) return NULL;
buffer[i++] = 0xD800 | (0x3ff & (c >> 10));
buffer[i++] = 0xDC00 | (0x3ff & (c ));
}
} else
return NULL;
}
buffer[i] = 0;
return buffer;
}
char * stb_to_utf8(char *buffer, stb__wchar *str, int n)
{
int i=0;
--n;
while (*str) {
if (*str < 0x80) {
if (i+1 > n) return NULL;
buffer[i++] = (char) *str++;
} else if (*str < 0x800) {
if (i+2 > n) return NULL;
buffer[i++] = 0xc0 + (*str >> 6);
buffer[i++] = 0x80 + (*str & 0x3f);
str += 1;
} else if (*str >= 0xd800 && *str < 0xdc00) {
stb_uint32 c;
if (i+4 > n) return NULL;
c = ((str[0] - 0xd800) << 10) + ((str[1]) - 0xdc00) + 0x10000;
buffer[i++] = 0xf0 + (c >> 18);
buffer[i++] = 0x80 + ((c >> 12) & 0x3f);
buffer[i++] = 0x80 + ((c >> 6) & 0x3f);
buffer[i++] = 0x80 + ((c ) & 0x3f);
str += 2;
} else if (*str >= 0xdc00 && *str < 0xe000) {
return NULL;
} else {
if (i+3 > n) return NULL;
buffer[i++] = 0xe0 + (*str >> 12);
buffer[i++] = 0x80 + ((*str >> 6) & 0x3f);
buffer[i++] = 0x80 + ((*str ) & 0x3f);
str += 1;
}
}
buffer[i] = 0;
return buffer;
}
stb__wchar *stb__from_utf8(char *str)
{
static stb__wchar buffer[4096];
return stb_from_utf8(buffer, str, 4096);
}
stb__wchar *stb__from_utf8_alt(char *str)
{
static stb__wchar buffer[4096];
return stb_from_utf8(buffer, str, 4096);
}
char *stb__to_utf8(stb__wchar *str)
{
static char buffer[4096];
return stb_to_utf8(buffer, str, 4096);
}
#endif
//////////////////////////////////////////////////////////////////////////////
//
// Miscellany
//
STB_EXTERN void stb_fatal(char *fmt, ...);
STB_EXTERN void stb_(char *fmt, ...);
STB_EXTERN void stb_append_to_file(char *file, char *fmt, ...);
STB_EXTERN void stb_log(int active);
STB_EXTERN void stb_log_fileline(int active);
STB_EXTERN void stb_log_name(char *filename);
STB_EXTERN void stb_swap(void *p, void *q, size_t sz);
STB_EXTERN void *stb_copy(void *p, size_t sz);
STB_EXTERN void stb_pointer_array_free(void *p, int len);
STB_EXTERN void **stb_array_block_alloc(int count, int blocksize);
#define stb_arrcount(x) (sizeof(x)/sizeof((x)[0]))
STB_EXTERN int stb__record_fileline(char *f, int n);
#ifdef STB_DEFINE
static char *stb__file;
static int stb__line;
int stb__record_fileline(char *f, int n)
{
stb__file = f;
stb__line = n;
return 0;
}
void stb_fatal(char *s, ...)
{
va_list a;
if (stb__file)
fprintf(stderr, "[%s:%d] ", stb__file, stb__line);
va_start(a,s);
fputs("Fatal error: ", stderr);
vfprintf(stderr, s, a);
va_end(a);
fputs("\n", stderr);
#ifdef STB_DEBUG
#ifdef _MSC_VER
#ifndef STB_PTR64
__asm int 3; // trap to debugger!
#else
__debugbreak();
#endif
#else
__builtin_trap();
#endif
#endif
exit(1);
}
static int stb__log_active=1, stb__log_fileline=1;
void stb_log(int active)
{
stb__log_active = active;
}
void stb_log_fileline(int active)
{
stb__log_fileline = active;
}
#ifdef STB_NO_STB_STRINGS
char *stb__log_filename = "temp.log";
#else
char *stb__log_filename = "stb.log";
#endif
void stb_log_name(char *s)
{
stb__log_filename = s;
}
void stb_(char *s, ...)
{
if (stb__log_active) {
FILE *f = fopen(stb__log_filename, "a");
if (f) {
va_list a;
if (stb__log_fileline && stb__file)
fprintf(f, "[%s:%4d] ", stb__file, stb__line);
va_start(a,s);
vfprintf(f, s, a);
va_end(a);
fputs("\n", f);
fclose(f);
}
}
}
void stb_append_to_file(char *filename, char *s, ...)
{
FILE *f = fopen(filename, "a");
if (f) {
va_list a;
va_start(a,s);
vfprintf(f, s, a);
va_end(a);
fputs("\n", f);
fclose(f);
}
}
typedef struct { char d[4]; } stb__4;
typedef struct { char d[8]; } stb__8;
// optimize the small cases, though you shouldn't be calling this for those!
void stb_swap(void *p, void *q, size_t sz)
{
char buffer[256];
if (p == q) return;
if (sz == 4) {
stb__4 temp = * ( stb__4 *) p;
* (stb__4 *) p = * ( stb__4 *) q;
* (stb__4 *) q = temp;
return;
} else if (sz == 8) {
stb__8 temp = * ( stb__8 *) p;
* (stb__8 *) p = * ( stb__8 *) q;
* (stb__8 *) q = temp;
return;
}
while (sz > sizeof(buffer)) {
stb_swap(p, q, sizeof(buffer));
p = (char *) p + sizeof(buffer);
q = (char *) q + sizeof(buffer);
sz -= sizeof(buffer);
}
memcpy(buffer, p , sz);
memcpy(p , q , sz);
memcpy(q , buffer, sz);
}
void *stb_copy(void *p, size_t sz)
{
void *q = malloc(sz);
memcpy(q, p, sz);
return q;
}
void stb_pointer_array_free(void *q, int len)
{
void **p = (void **) q;
int i;
for (i=0; i < len; ++i)
free(p[i]);
}
void **stb_array_block_alloc(int count, int blocksize)
{
int i;
char *p = (char *) malloc(sizeof(void *) * count + count * blocksize);
void **q;
if (p == NULL) return NULL;
q = (void **) p;
p += sizeof(void *) * count;
for (i=0; i < count; ++i)
q[i] = p + i * blocksize;
return q;
}
#endif
#ifdef STB_DEBUG
// tricky hack to allow recording FILE,LINE even in varargs functions
#define STB__RECORD_FILE(x) (stb__record_fileline(__FILE__, __LINE__),(x))
#define stb_log STB__RECORD_FILE(stb_log)
#define stb_ STB__RECORD_FILE(stb_)
#ifndef STB_FATAL_CLEAN
#define stb_fatal STB__RECORD_FILE(stb_fatal)
#endif
#define STB__DEBUG(x) x
#else
#define STB__DEBUG(x)
#endif
//////////////////////////////////////////////////////////////////////////////
//
// stb_temp
//
#define stb_temp(block, sz) stb__temp(block, sizeof(block), (sz))
STB_EXTERN void * stb__temp(void *b, int b_sz, int want_sz);
STB_EXTERN void stb_tempfree(void *block, void *ptr);
#ifdef STB_DEFINE
void * stb__temp(void *b, int b_sz, int want_sz)
{
if (b_sz >= want_sz)
return b;
else
return malloc(want_sz);
}
void stb_tempfree(void *b, void *p)
{
if (p != b)
free(p);
}
#endif
//////////////////////////////////////////////////////////////////////////////
//
// math/sampling operations
//
#define stb_lerp(t,a,b) ( (a) + (t) * (float) ((b)-(a)) )
#define stb_unlerp(t,a,b) ( ((t) - (a)) / (float) ((b) - (a)) )
#define stb_clamp(x,xmin,xmax) ((x) < (xmin) ? (xmin) : (x) > (xmax) ? (xmax) : (x))
STB_EXTERN void stb_newell_normal(float *normal, int num_vert, float **vert, int normalize);
STB_EXTERN int stb_box_face_vertex_axis_side(int face_number, int vertex_number, int axis);
STB_EXTERN void stb_linear_controller(float *curpos, float target_pos, float acc, float deacc, float dt);
STB_EXTERN int stb_float_eq(float x, float y, float delta, int max_ulps);
STB_EXTERN int stb_is_prime(unsigned int m);
STB_EXTERN unsigned int stb_power_of_two_nearest_prime(int n);
STB_EXTERN float stb_smoothstep(float t);
STB_EXTERN float stb_cubic_bezier_1d(float t, float p0, float p1, float p2, float p3);
STB_EXTERN double stb_linear_remap(double x, double a, double b,
double c, double d);
#ifdef STB_DEFINE
float stb_smoothstep(float t)
{
return (3 - 2*t)*(t*t);
}
float stb_cubic_bezier_1d(float t, float p0, float p1, float p2, float p3)
{
float it = 1-t;
return it*it*it*p0 + 3*it*it*t*p1 + 3*it*t*t*p2 + t*t*t*p3;
}
void stb_newell_normal(float *normal, int num_vert, float **vert, int normalize)
{
int i,j;
float p;
normal[0] = normal[1] = normal[2] = 0;
for (i=num_vert-1,j=0; j < num_vert; i=j++) {
float *u = vert[i];
float *v = vert[j];
normal[0] += (u[1] - v[1]) * (u[2] + v[2]);
normal[1] += (u[2] - v[2]) * (u[0] + v[0]);
normal[2] += (u[0] - v[0]) * (u[1] + v[1]);
}
if (normalize) {
p = normal[0]*normal[0] + normal[1]*normal[1] + normal[2]*normal[2];
p = (float) (1.0 / sqrt(p));
normal[0] *= p;
normal[1] *= p;
normal[2] *= p;
}
}
int stb_box_face_vertex_axis_side(int face_number, int vertex_number, int axis)
{
static int box_vertices[6][4][3] =
{
{ { 1,1,1 }, { 1,0,1 }, { 1,0,0 }, { 1,1,0 } },
{ { 0,0,0 }, { 0,0,1 }, { 0,1,1 }, { 0,1,0 } },
{ { 0,0,0 }, { 0,1,0 }, { 1,1,0 }, { 1,0,0 } },
{ { 0,0,0 }, { 1,0,0 }, { 1,0,1 }, { 0,0,1 } },
{ { 1,1,1 }, { 0,1,1 }, { 0,0,1 }, { 1,0,1 } },
{ { 1,1,1 }, { 1,1,0 }, { 0,1,0 }, { 0,1,1 } },
};
assert(face_number >= 0 && face_number < 6);
assert(vertex_number >= 0 && vertex_number < 4);
assert(axis >= 0 && axis < 3);
return box_vertices[face_number][vertex_number][axis];
}
void stb_linear_controller(float *curpos, float target_pos, float acc, float deacc, float dt)
{
float sign = 1, p, cp = *curpos;
if (cp == target_pos) return;
if (target_pos < cp) {
target_pos = -target_pos;
cp = -cp;
sign = -1;
}
// first decelerate
if (cp < 0) {
p = cp + deacc * dt;
if (p > 0) {
p = 0;
dt = dt - cp / deacc;
if (dt < 0) dt = 0;
} else {
dt = 0;
}
cp = p;
}
// now accelerate
p = cp + acc*dt;
if (p > target_pos) p = target_pos;
*curpos = p * sign;
// @TODO: testing
}
float stb_quadratic_controller(float target_pos, float curpos, float maxvel, float maxacc, float dt, float *curvel)
{
return 0; // @TODO
}
int stb_float_eq(float x, float y, float delta, int max_ulps)
{
if (fabs(x-y) <= delta) return 1;
if (abs(*(int *)&x - *(int *)&y) <= max_ulps) return 1;
return 0;
}
int stb_is_prime(unsigned int m)
{
unsigned int i,j;
if (m < 2) return 0;
if (m == 2) return 1;
if (!(m & 1)) return 0;
if (m % 3 == 0) return (m == 3);
for (i=5; (j=i*i), j <= m && j > i; i += 6) {
if (m % i == 0) return 0;
if (m % (i+2) == 0) return 0;
}
return 1;
}
unsigned int stb_power_of_two_nearest_prime(int n)
{
static signed char tab[32] = { 0,0,0,0,1,0,-1,0,1,-1,-1,3,-1,0,-1,2,1,
0,2,0,-1,-4,-1,5,-1,18,-2,15,2,-1,2,0 };
if (!tab[0]) {
int i;
for (i=0; i < 32; ++i)
tab[i] = (1 << i) + 2*tab[i] - 1;
tab[1] = 2;
tab[0] = 1;
}
if (n >= 32) return 0xfffffffb;
return tab[n];
}
double stb_linear_remap(double x, double x_min, double x_max,
double out_min, double out_max)
{
return stb_lerp(stb_unlerp(x,x_min,x_max),out_min,out_max);
}
#endif
// create a macro so it's faster, but you can get at the function pointer
#define stb_linear_remap(t,a,b,c,d) stb_lerp(stb_unlerp(t,a,b),c,d)
//////////////////////////////////////////////////////////////////////////////
//
// bit operations
//
#define stb_big32(c) (((c)[0]<<24) + (c)[1]*65536 + (c)[2]*256 + (c)[3])
#define stb_little32(c) (((c)[3]<<24) + (c)[2]*65536 + (c)[1]*256 + (c)[0])
#define stb_big16(c) ((c)[0]*256 + (c)[1])
#define stb_little16(c) ((c)[1]*256 + (c)[0])
STB_EXTERN int stb_bitcount(unsigned int a);
STB_EXTERN unsigned int stb_bitreverse8(unsigned char n);
STB_EXTERN unsigned int stb_bitreverse(unsigned int n);
STB_EXTERN int stb_is_pow2(unsigned int n);
STB_EXTERN int stb_log2_ceil(unsigned int n);
STB_EXTERN int stb_log2_floor(unsigned int n);
STB_EXTERN int stb_lowbit8(unsigned int n);
STB_EXTERN int stb_highbit8(unsigned int n);
#ifdef STB_DEFINE
int stb_bitcount(unsigned int a)
{
a = (a & 0x55555555) + ((a >> 1) & 0x55555555); // max 2
a = (a & 0x33333333) + ((a >> 2) & 0x33333333); // max 4
a = (a + (a >> 4)) & 0x0f0f0f0f; // max 8 per 4, now 8 bits
a = (a + (a >> 8)); // max 16 per 8 bits
a = (a + (a >> 16)); // max 32 per 8 bits
return a & 0xff;
}
unsigned int stb_bitreverse8(unsigned char n)
{
n = ((n & 0xAA) >> 1) + ((n & 0x55) << 1);
n = ((n & 0xCC) >> 2) + ((n & 0x33) << 2);
return (unsigned char) ((n >> 4) + (n << 4));
}
unsigned int stb_bitreverse(unsigned int n)
{
n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
return (n >> 16) | (n << 16);
}
int stb_is_pow2(unsigned int n)
{
return (n & (n-1)) == 0;
}
// tricky use of 4-bit table to identify 5 bit positions (note the '-1')
// 3-bit table would require another tree level; 5-bit table wouldn't save one
#if defined(_WIN32) && !defined(__MINGW32__)
#pragma warning(push)
#pragma warning(disable: 4035) // disable warning about no return value
int stb_log2_floor(unsigned int n)
{
#if _MSC_VER > 1700
unsigned long i;
_BitScanReverse(&i, n);
return i != 0 ? i : -1;
#else
__asm {
bsr eax,n
jnz done
mov eax,-1
}
done:;
#endif
}
#pragma warning(pop)
#else
int stb_log2_floor(unsigned int n)
{
static signed char log2_4[16] = { -1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3 };
// 2 compares if n < 16, 3 compares otherwise
if (n < (1U << 14))
if (n < (1U << 4)) return 0 + log2_4[n ];
else if (n < (1U << 9)) return 5 + log2_4[n >> 5];
else return 10 + log2_4[n >> 10];
else if (n < (1U << 24))
if (n < (1U << 19)) return 15 + log2_4[n >> 15];
else return 20 + log2_4[n >> 20];
else if (n < (1U << 29)) return 25 + log2_4[n >> 25];
else return 30 + log2_4[n >> 30];
}
#endif
// define ceil from floor
int stb_log2_ceil(unsigned int n)
{
if (stb_is_pow2(n)) return stb_log2_floor(n);
else return 1 + stb_log2_floor(n);
}
int stb_highbit8(unsigned int n)
{
return stb_log2_ceil(n&255);
}
int stb_lowbit8(unsigned int n)
{
static signed char lowbit4[16] = { -1,0,1,0, 2,0,1,0, 3,0,1,0, 2,0,1,0 };
int k = lowbit4[n & 15];
if (k >= 0) return k;
k = lowbit4[(n >> 4) & 15];
if (k >= 0) return k+4;
return k;
}
#endif
//////////////////////////////////////////////////////////////////////////////
//
// qsort Compare Routines
//
#ifdef _WIN32
#define stb_stricmp(a,b) stricmp(a,b)
#define stb_strnicmp(a,b,n) strnicmp(a,b,n)
#else
#define stb_stricmp(a,b) strcasecmp(a,b)
#define stb_strnicmp(a,b,n) strncasecmp(a,b,n)
#endif
STB_EXTERN int (*stb_intcmp(int offset))(const void *a, const void *b);
STB_EXTERN int (*stb_qsort_strcmp(int offset))(const void *a, const void *b);
STB_EXTERN int (*stb_qsort_stricmp(int offset))(const void *a, const void *b);
STB_EXTERN int (*stb_floatcmp(int offset))(const void *a, const void *b);
STB_EXTERN int (*stb_doublecmp(int offset))(const void *a, const void *b);
STB_EXTERN int (*stb_charcmp(int offset))(const void *a, const void *b);
#ifdef STB_DEFINE
static int stb__intcmpoffset, stb__ucharcmpoffset, stb__strcmpoffset;
static int stb__floatcmpoffset, stb__doublecmpoffset;
int stb__intcmp(const void *a, const void *b)
{
const int p = *(const int *) ((const char *) a + stb__intcmpoffset);
const int q = *(const int *) ((const char *) b + stb__intcmpoffset);
return p < q ? -1 : p > q;
}
int stb__ucharcmp(const void *a, const void *b)
{
const int p = *(const unsigned char *) ((const char *) a + stb__ucharcmpoffset);
const int q = *(const unsigned char *) ((const char *) b + stb__ucharcmpoffset);
return p < q ? -1 : p > q;
}
int stb__floatcmp(const void *a, const void *b)
{
const float p = *(const float *) ((const char *) a + stb__floatcmpoffset);
const float q = *(const float *) ((const char *) b + stb__floatcmpoffset);
return p < q ? -1 : p > q;
}
int stb__doublecmp(const void *a, const void *b)
{
const double p = *(const double *) ((const char *) a + stb__doublecmpoffset);
const double q = *(const double *) ((const char *) b + stb__doublecmpoffset);
return p < q ? -1 : p > q;
}
int stb__qsort_strcmp(const void *a, const void *b)
{
const char *p = *(const char **) ((const char *) a + stb__strcmpoffset);
const char *q = *(const char **) ((const char *) b + stb__strcmpoffset);
return strcmp(p,q);
}
int stb__qsort_stricmp(const void *a, const void *b)
{
const char *p = *(const char **) ((const char *) a + stb__strcmpoffset);
const char *q = *(const char **) ((const char *) b + stb__strcmpoffset);
return stb_stricmp(p,q);
}
int (*stb_intcmp(int offset))(const void *, const void *)
{
stb__intcmpoffset = offset;
return &stb__intcmp;
}
int (*stb_ucharcmp(int offset))(const void *, const void *)
{
stb__ucharcmpoffset = offset;
return &stb__ucharcmp;
}
int (*stb_qsort_strcmp(int offset))(const void *, const void *)
{
stb__strcmpoffset = offset;
return &stb__qsort_strcmp;
}
int (*stb_qsort_stricmp(int offset))(const void *, const void *)
{
stb__strcmpoffset = offset;
return &stb__qsort_stricmp;
}
int (*stb_floatcmp(int offset))(const void *, const void *)
{
stb__floatcmpoffset = offset;
return &stb__floatcmp;
}
int (*stb_doublecmp(int offset))(const void *, const void *)
{
stb__doublecmpoffset = offset;
return &stb__doublecmp;
}
#endif
//////////////////////////////////////////////////////////////////////////////
//
// Binary Search Toolkit
//
typedef struct
{
int minval, maxval, guess;
int mode, step;
} stb_search;
STB_EXTERN int stb_search_binary(stb_search *s, int minv, int maxv, int find_smallest);
STB_EXTERN int stb_search_open(stb_search *s, int minv, int find_smallest);
STB_EXTERN int stb_probe(stb_search *s, int compare, int *result); // return 0 when done
#ifdef STB_DEFINE
enum
{
STB_probe_binary_smallest,
STB_probe_binary_largest,
STB_probe_open_smallest,
STB_probe_open_largest,
};
static int stb_probe_guess(stb_search *s, int *result)
{
switch(s->mode) {
case STB_probe_binary_largest:
if (s->minval == s->maxval) {
*result = s->minval;
return 0;
}
assert(s->minval < s->maxval);
// if a < b, then a < p <= b
s->guess = s->minval + (((unsigned) s->maxval - s->minval + 1) >> 1);
break;
case STB_probe_binary_smallest:
if (s->minval == s->maxval) {
*result = s->minval;
return 0;
}
assert(s->minval < s->maxval);
// if a < b, then a <= p < b
s->guess = s->minval + (((unsigned) s->maxval - s->minval) >> 1);
break;
case STB_probe_open_smallest:
case STB_probe_open_largest:
s->guess = s->maxval; // guess the current maxval
break;
}
*result = s->guess;
return 1;
}
int stb_probe(stb_search *s, int compare, int *result)
{
switch(s->mode) {
case STB_probe_open_smallest:
case STB_probe_open_largest: {
if (compare <= 0) {
// then it lies within minval & maxval
if (s->mode == STB_probe_open_smallest)
s->mode = STB_probe_binary_smallest;
else
s->mode = STB_probe_binary_largest;
} else {
// otherwise, we need to probe larger
s->minval = s->maxval + 1;
s->maxval = s->minval + s->step;
s->step += s->step;
}
break;
}
case STB_probe_binary_smallest: {
// if compare < 0, then s->minval <= a < p
// if compare = 0, then s->minval <= a <= p
// if compare > 0, then p < a <= s->maxval
if (compare <= 0)
s->maxval = s->guess;
else
s->minval = s->guess+1;
break;
}
case STB_probe_binary_largest: {
// if compare < 0, then s->minval <= a < p
// if compare = 0, then p <= a <= s->maxval
// if compare > 0, then p < a <= s->maxval
if (compare < 0)
s->maxval = s->guess-1;
else
s->minval = s->guess;
break;
}
}
return stb_probe_guess(s, result);
}
int stb_search_binary(stb_search *s, int minv, int maxv, int find_smallest)
{
int r;
if (maxv < minv) return minv-1;
s->minval = minv;
s->maxval = maxv;
s->mode = find_smallest ? STB_probe_binary_smallest : STB_probe_binary_largest;
stb_probe_guess(s, &r);
return r;
}
int stb_search_open(stb_search *s, int minv, int find_smallest)
{
int r;
s->step = 4;
s->minval = minv;
s->maxval = minv+s->step;
s->mode = find_smallest ? STB_probe_open_smallest : STB_probe_open_largest;
stb_probe_guess(s, &r);
return r;
}
#endif
//////////////////////////////////////////////////////////////////////////////
//
// String Processing
//
#define stb_prefixi(s,t) (0==stb_strnicmp((s),(t),strlen(t)))
enum stb_splitpath_flag
{
STB_PATH = 1,
STB_FILE = 2,
STB_EXT = 4,
STB_PATH_FILE = STB_PATH + STB_FILE,
STB_FILE_EXT = STB_FILE + STB_EXT,
STB_EXT_NO_PERIOD = 8,
};
STB_EXTERN char * stb_skipwhite(char *s);
STB_EXTERN char * stb_trimwhite(char *s);
STB_EXTERN char * stb_skipnewline(char *s);
STB_EXTERN char * stb_strncpy(char *s, char *t, int n);
STB_EXTERN char * stb_substr(char *t, int n);
STB_EXTERN char * stb_duplower(char *s);
STB_EXTERN void stb_tolower (char *s);
STB_EXTERN char * stb_strchr2 (char *s, char p1, char p2);
STB_EXTERN char * stb_strrchr2(char *s, char p1, char p2);
STB_EXTERN char * stb_strtok(char *output, char *src, char *delimit);
STB_EXTERN char * stb_strtok_keep(char *output, char *src, char *delimit);
STB_EXTERN char * stb_strtok_invert(char *output, char *src, char *allowed);
STB_EXTERN char * stb_dupreplace(char *s, char *find, char *replace);
STB_EXTERN void stb_replaceinplace(char *s, char *find, char *replace);
STB_EXTERN char * stb_splitpath(char *output, char *src, int flag);
STB_EXTERN char * stb_splitpathdup(char *src, int flag);
STB_EXTERN char * stb_replacedir(char *output, char *src, char *dir);
STB_EXTERN char * stb_replaceext(char *output, char *src, char *ext);
STB_EXTERN void stb_fixpath(char *path);
STB_EXTERN char * stb_shorten_path_readable(char *path, int max_len);
STB_EXTERN int stb_suffix (char *s, char *t);
STB_EXTERN int stb_suffixi(char *s, char *t);
STB_EXTERN int stb_prefix (char *s, char *t);
STB_EXTERN char * stb_strichr(char *s, char t);
STB_EXTERN char * stb_stristr(char *s, char *t);
STB_EXTERN int stb_prefix_count(char *s, char *t);
STB_EXTERN const char * stb_plural(int n); // "s" or ""
STB_EXTERN size_t stb_strscpy(char *d, const char *s, size_t n);
STB_EXTERN char **stb_tokens(char *src, char *delimit, int *count);
STB_EXTERN char **stb_tokens_nested(char *src, char *delimit, int *count, char *nest_in, char *nest_out);
STB_EXTERN char **stb_tokens_nested_empty(char *src, char *delimit, int *count, char *nest_in, char *nest_out);
STB_EXTERN char **stb_tokens_allowempty(char *src, char *delimit, int *count);
STB_EXTERN char **stb_tokens_stripwhite(char *src, char *delimit, int *count);
STB_EXTERN char **stb_tokens_withdelim(char *src, char *delimit, int *count);
STB_EXTERN char **stb_tokens_quoted(char *src, char *delimit, int *count);
// with 'quoted', allow delimiters to appear inside quotation marks, and don't
// strip whitespace inside them (and we delete the quotation marks unless they
// appear back to back, in which case they're considered escaped)
#ifdef STB_DEFINE
size_t stb_strscpy(char *d, const char *s, size_t n)
{
size_t len = strlen(s);
if (len >= n) {
if (n) d[0] = 0;
return 0;
}
strcpy(d,s);
return len + 1;
}
const char *stb_plural(int n)
{
return n == 1 ? "" : "s";
}
int stb_prefix(char *s, char *t)
{
while (*t)
if (*s++ != *t++)
return STB_FALSE;
return STB_TRUE;
}
int stb_prefix_count(char *s, char *t)
{
int c=0;
while (*t) {
if (*s++ != *t++)
break;
++c;
}
return c;
}
int stb_suffix(char *s, char *t)
{
size_t n = strlen(s);
size_t m = strlen(t);
if (m <= n)
return 0 == strcmp(s+n-m, t);
else
return 0;
}
int stb_suffixi(char *s, char *t)
{
size_t n = strlen(s);
size_t m = strlen(t);
if (m <= n)
return 0 == stb_stricmp(s+n-m, t);
else
return 0;
}
// originally I was using this table so that I could create known sentinel
// values--e.g. change whitetable[0] to be true if I was scanning for whitespace,
// and false if I was scanning for nonwhite. I don't appear to be using that
// functionality anymore (I do for tokentable, though), so just replace it
// with isspace()
char *stb_skipwhite(char *s)
{
while (isspace((unsigned char) *s)) ++s;
return s;
}
char *stb_skipnewline(char *s)
{
if (s[0] == '\r' || s[0] == '\n') {
if (s[0]+s[1] == '\r' + '\n') ++s;
++s;
}
return s;
}
char *stb_trimwhite(char *s)
{
int i,n;
s = stb_skipwhite(s);
n = (int) strlen(s);
for (i=n-1; i >= 0; --i)
if (!isspace(s[i]))
break;
s[i+1] = 0;
return s;
}
char *stb_strncpy(char *s, char *t, int n)
{
strncpy(s,t,n);
s[n-1] = 0;
return s;
}
char *stb_substr(char *t, int n)
{
char *a;
int z = (int) strlen(t);
if (z < n) n = z;
a = (char *) malloc(n+1);
strncpy(a,t,n);
a[n] = 0;
return a;
}
char *stb_duplower(char *s)
{
char *p = strdup(s), *q = p;
while (*q) {
*q = tolower(*q);
++q;
}
return p;
}
void stb_tolower(char *s)
{
while (*s) {
*s = tolower(*s);
++s;
}
}
char *stb_strchr2(char *s, char x, char y)
{
for(; *s; ++s)
if (*s == x || *s == y)
return s;
return NULL;
}
char *stb_strrchr2(char *s, char x, char y)
{
char *r = NULL;
for(; *s; ++s)
if (*s == x || *s == y)
r = s;
return r;
}
char *stb_strichr(char *s, char t)
{
if (tolower(t) == toupper(t))
return strchr(s,t);
return stb_strchr2(s, (char) tolower(t), (char) toupper(t));
}
char *stb_stristr(char *s, char *t)
{
size_t n = strlen(t);
char *z;
if (n==0) return s;
while ((z = stb_strichr(s, *t)) != NULL) {
if (0==stb_strnicmp(z, t, n))
return z;
s = z+1;
}
return NULL;
}
static char *stb_strtok_raw(char *output, char *src, char *delimit, int keep, int invert)
{
if (invert) {
while (*src && strchr(delimit, *src) != NULL) {
*output++ = *src++;
}
} else {
while (*src && strchr(delimit, *src) == NULL) {
*output++ = *src++;
}
}
*output = 0;
if (keep)
return src;
else
return *src ? src+1 : src;
}
char *stb_strtok(char *output, char *src, char *delimit)
{
return stb_strtok_raw(output, src, delimit, 0, 0);
}
char *stb_strtok_keep(char *output, char *src, char *delimit)
{
return stb_strtok_raw(output, src, delimit, 1, 0);
}
char *stb_strtok_invert(char *output, char *src, char *delimit)
{
return stb_strtok_raw(output, src, delimit, 1,1);
}
static char **stb_tokens_raw(char *src_, char *delimit, int *count,
int stripwhite, int allow_empty, char *start, char *end)
{
int nested = 0;
unsigned char *src = (unsigned char *) src_;
static char stb_tokentable[256]; // rely on static initializion to 0
static char stable[256],etable[256];
char *out;
char **result;
int num=0;
unsigned char *s;
s = (unsigned char *) delimit; while (*s) stb_tokentable[*s++] = 1;
if (start) {
s = (unsigned char *) start; while (*s) stable[*s++] = 1;
s = (unsigned char *) end; if (s) while (*s) stable[*s++] = 1;
s = (unsigned char *) end; if (s) while (*s) etable[*s++] = 1;
}
stable[0] = 1;
// two passes through: the first time, counting how many
s = (unsigned char *) src;
while (*s) {
// state: just found delimiter
// skip further delimiters
if (!allow_empty) {
stb_tokentable[0] = 0;
while (stb_tokentable[*s])
++s;
if (!*s) break;
}
++num;
// skip further non-delimiters
stb_tokentable[0] = 1;
if (stripwhite == 2) { // quoted strings
while (!stb_tokentable[*s]) {
if (*s != '"')
++s;
else {
++s;
if (*s == '"')
++s; // "" -> ", not start a string
else {
// begin a string
while (*s) {
if (s[0] == '"') {
if (s[1] == '"') s += 2; // "" -> "
else { ++s; break; } // terminating "
} else
++s;
}
}
}
}
} else
while (nested || !stb_tokentable[*s]) {
if (stable[*s]) {
if (!*s) break;
if (end ? etable[*s] : nested)
--nested;
else
++nested;
}
++s;
}
if (allow_empty) {
if (*s) ++s;
}
}
// now num has the actual count... malloc our output structure
// need space for all the strings: strings won't be any longer than
// original input, since for every '\0' there's at least one delimiter
result = (char **) malloc(sizeof(*result) * (num+1) + (s-src+1));
if (result == NULL) return result;
out = (char *) (result + (num+1));
// second pass: copy out the data
s = (unsigned char *) src;
num = 0;
nested = 0;
while (*s) {
char *last_nonwhite;
// state: just found delimiter
// skip further delimiters
if (!allow_empty) {
stb_tokentable[0] = 0;
if (stripwhite)
while (stb_tokentable[*s] || isspace(*s))
++s;
else
while (stb_tokentable[*s])
++s;
} else if (stripwhite) {
while (isspace(*s)) ++s;
}
if (!*s) break;
// we're past any leading delimiters and whitespace
result[num] = out;
++num;
// copy non-delimiters
stb_tokentable[0] = 1;
last_nonwhite = out-1;
if (stripwhite == 2) {
while (!stb_tokentable[*s]) {
if (*s != '"') {
if (!isspace(*s)) last_nonwhite = out;
*out++ = *s++;
} else {
++s;
if (*s == '"') {
if (!isspace(*s)) last_nonwhite = out;
*out++ = *s++; // "" -> ", not start string
} else {
// begin a quoted string
while (*s) {
if (s[0] == '"') {
if (s[1] == '"') { *out++ = *s; s += 2; }
else { ++s; break; } // terminating "
} else
*out++ = *s++;
}
last_nonwhite = out-1; // all in quotes counts as non-white
}
}
}
} else {
while (nested || !stb_tokentable[*s]) {
if (!isspace(*s)) last_nonwhite = out;
if (stable[*s]) {
if (!*s) break;
if (end ? etable[*s] : nested)
--nested;
else
++nested;
}
*out++ = *s++;
}
}
if (stripwhite) // rewind to last non-whitespace char
out = last_nonwhite+1;
*out++ = '\0';
if (*s) ++s; // skip delimiter
}
s = (unsigned char *) delimit; while (*s) stb_tokentable[*s++] = 0;
if (start) {
s = (unsigned char *) start; while (*s) stable[*s++] = 1;
s = (unsigned char *) end; if (s) while (*s) stable[*s++] = 1;
s = (unsigned char *) end; if (s) while (*s) etable[*s++] = 1;
}
if (count != NULL) *count = num;
result[num] = 0;
return result;
}
char **stb_tokens(char *src, char *delimit, int *count)
{
return stb_tokens_raw(src,delimit,count,0,0,0,0);
}
char **stb_tokens_nested(char *src, char *delimit, int *count, char *nest_in, char *nest_out)
{
return stb_tokens_raw(src,delimit,count,0,0,nest_in,nest_out);
}
char **stb_tokens_nested_empty(char *src, char *delimit, int *count, char *nest_in, char *nest_out)
{
return stb_tokens_raw(src,delimit,count,0,1,nest_in,nest_out);
}
char **stb_tokens_allowempty(char *src, char *delimit, int *count)
{
return stb_tokens_raw(src,delimit,count,0,1,0,0);
}
char **stb_tokens_stripwhite(char *src, char *delimit, int *count)
{
return stb_tokens_raw(src,delimit,count,1,1,0,0);
}
char **stb_tokens_quoted(char *src, char *delimit, int *count)
{
return stb_tokens_raw(src,delimit,count,2,1,0,0);
}
char *stb_dupreplace(char *src, char *find, char *replace)
{
size_t len_find = strlen(find);
size_t len_replace = strlen(replace);
int count = 0;
char *s,*p,*q;
s = strstr(src, find);
if (s == NULL) return strdup(src);
do {
++count;
s = strstr(s + len_find, find);
} while (s != NULL);
p = (char *) malloc(strlen(src) + count * (len_replace - len_find) + 1);
if (p == NULL) return p;
q = p;
s = src;
for (;;) {
char *t = strstr(s, find);
if (t == NULL) {
strcpy(q,s);
assert(strlen(p) == strlen(src) + count*(len_replace-len_find));
return p;
}
memcpy(q, s, t-s);
q += t-s;
memcpy(q, replace, len_replace);
q += len_replace;
s = t + len_find;
}
}
void stb_replaceinplace(char *src, char *find, char *replace)
{
size_t len_find = strlen(find);
size_t len_replace = strlen(replace);
int delta;
char *s,*p,*q;
delta = len_replace - len_find;
assert(delta <= 0);
if (delta > 0) return;
p = strstr(src, find);
if (p == NULL) return;
s = q = p;
while (*s) {
memcpy(q, replace, len_replace);
p += len_find;
q += len_replace;
s = strstr(p, find);
if (s == NULL) s = p + strlen(p);
memmove(q, p, s-p);
q += s-p;
p = s;
}
*q = 0;
}
void stb_fixpath(char *path)
{
for(; *path; ++path)
if (*path == '\\')
*path = '/';
}
void stb__add_section(char *buffer, char *data, int curlen, int newlen)
{
if (newlen < curlen) {
int z1 = newlen >> 1, z2 = newlen-z1;
memcpy(buffer, data, z1-1);
buffer[z1-1] = '.';
buffer[z1-0] = '.';
memcpy(buffer+z1+1, data+curlen-z2+1, z2-1);
} else
memcpy(buffer, data, curlen);
}
char * stb_shorten_path_readable(char *path, int len)
{
static char buffer[1024];
int n = strlen(path),n1,n2,r1,r2;
char *s;
if (n <= len) return path;
if (len > 1024) return path;
s = stb_strrchr2(path, '/', '\\');
if (s) {
n1 = s - path + 1;
n2 = n - n1;
++s;
} else {
n1 = 0;
n2 = n;
s = path;
}
// now we need to reduce r1 and r2 so that they fit in len
if (n1 < len>>1) {
r1 = n1;
r2 = len - r1;
} else if (n2 < len >> 1) {
r2 = n2;
r1 = len - r2;
} else {
r1 = n1 * len / n;
r2 = n2 * len / n;
if (r1 < len>>2) r1 = len>>2, r2 = len-r1;
if (r2 < len>>2) r2 = len>>2, r1 = len-r2;
}
assert(r1 <= n1 && r2 <= n2);
if (n1)
stb__add_section(buffer, path, n1, r1);
stb__add_section(buffer+r1, s, n2, r2);
buffer[len] = 0;
return buffer;
}
static char *stb__splitpath_raw(char *buffer, char *path, int flag)
{
int len=0,x,y, n = (int) strlen(path), f1,f2;
char *s = stb_strrchr2(path, '/', '\\');
char *t = strrchr(path, '.');
if (s && t && t < s) t = NULL;
if (s) ++s;
if (flag == STB_EXT_NO_PERIOD)
flag |= STB_EXT;
if (!(flag & (STB_PATH | STB_FILE | STB_EXT))) return NULL;
f1 = s == NULL ? 0 : s-path; // start of filename
f2 = t == NULL ? n : t-path; // just past end of filename
if (flag & STB_PATH) {
x = 0; if (f1 == 0 && flag == STB_PATH) len=2;
} else if (flag & STB_FILE) {
x = f1;
} else {
x = f2;
if (flag & STB_EXT_NO_PERIOD)
if (buffer[x] == '.')
++x;
}
if (flag & STB_EXT)
y = n;
else if (flag & STB_FILE)
y = f2;
else
y = f1;
if (buffer == NULL) {
buffer = (char *) malloc(y-x + len + 1);
if (!buffer) return NULL;
}
if (len) { strcpy(buffer, "./"); return buffer; }
strncpy(buffer, path+x, y-x);
buffer[y-x] = 0;
return buffer;
}
char *stb_splitpath(char *output, char *src, int flag)
{
return stb__splitpath_raw(output, src, flag);
}
char *stb_splitpathdup(char *src, int flag)
{
return stb__splitpath_raw(NULL, src, flag);
}
char *stb_replacedir(char *output, char *src, char *dir)
{
char buffer[4096];
stb_splitpath(buffer, src, STB_FILE | STB_EXT);
if (dir)
sprintf(output, "%s/%s", dir, buffer);
else
strcpy(output, buffer);
return output;
}
char *stb_replaceext(char *output, char *src, char *ext)
{
char buffer[4096];
stb_splitpath(buffer, src, STB_PATH | STB_FILE);
if (ext)
sprintf(output, "%s.%s", buffer, ext[0] == '.' ? ext+1 : ext);
else
strcpy(output, buffer);
return output;
}
#endif
//////////////////////////////////////////////////////////////////////////////
//
// stb_alloc - hierarchical allocator
//
// inspired by http://swapped.cc/halloc
//
//
// When you alloc a given block through stb_alloc, you have these choices:
//
// 1. does it have a parent?
// 2. can it have children?
// 3. can it be freed directly?
// 4. is it transferrable?
// 5. what is its alignment?
//
// Here are interesting combinations of those:
//
// children free transfer alignment
// arena Y Y N n/a
// no-overhead, chunked N N N normal
// string pool alloc N N N 1
// parent-ptr, chunked Y N N normal
// low-overhead, unchunked N Y Y normal
// general purpose alloc Y Y Y normal
//
// Unchunked allocations will probably return 16-aligned pointers. If
// we 16-align the results, we have room for 4 pointers. For smaller
// allocations that allow finer alignment, we can reduce the pointers.
//
// The strategy is that given a pointer, assuming it has a header (only
// the no-overhead allocations have no header), we can determine the
// type of the header fields, and the number of them, by stepping backwards
// through memory and looking at the tags in the bottom bits.
//
// Implementation strategy:
// chunked allocations come from the middle of chunks, and can't
// be freed. thefore they do not need to be on a sibling chain.
// they may need child pointers if they have children.
//
// chunked, with-children
// void *parent;
//
// unchunked, no-children -- reduced storage
// void *next_sibling;
// void *prev_sibling_nextp;
//
// unchunked, general
// void *first_child;
// void *next_sibling;
// void *prev_sibling_nextp;
// void *chunks;
//
// so, if we code each of these fields with different bit patterns
// (actually same one for next/prev/child), then we can identify which
// each one is from the last field.
STB_EXTERN void stb_free(void *p);
STB_EXTERN void *stb_malloc_global(size_t size);
STB_EXTERN void *stb_malloc(void *context, size_t size);
STB_EXTERN void *stb_malloc_nofree(void *context, size_t size);
STB_EXTERN void *stb_malloc_leaf(void *context, size_t size);
STB_EXTERN void *stb_malloc_raw(void *context, size_t size);
STB_EXTERN void *stb_realloc(void *ptr, size_t newsize);
STB_EXTERN void stb_reassign(void *new_context, void *ptr);
STB_EXTERN void stb_malloc_validate(void *p, void *parent);
extern int stb_alloc_chunk_size ;
extern int stb_alloc_count_free ;
extern int stb_alloc_count_alloc;
extern int stb_alloc_alignment ;
#ifdef STB_DEFINE
int stb_alloc_chunk_size = 65536;
int stb_alloc_count_free = 0;
int stb_alloc_count_alloc = 0;
int stb_alloc_alignment = -16;
typedef struct stb__chunk
{
struct stb__chunk *next;
int data_left;
int alloc;
} stb__chunk;
typedef struct
{
void * next;
void ** prevn;
} stb__nochildren;
typedef struct
{
void ** prevn;
void * child;
void * next;
stb__chunk *chunks;
} stb__alloc;
typedef struct
{
stb__alloc *parent;
} stb__chunked;
#define STB__PARENT 1
#define STB__CHUNKS 2
typedef enum
{
STB__nochildren = 0,
STB__chunked = STB__PARENT,
STB__alloc = STB__CHUNKS,
STB__chunk_raw = 4,
} stb__alloc_type;
// these functions set the bottom bits of a pointer efficiently
#define STB__DECODE(x,v) ((void *) ((char *) (x) - (v)))
#define STB__ENCODE(x,v) ((void *) ((char *) (x) + (v)))
#define stb__parent(z) (stb__alloc *) STB__DECODE((z)->parent, STB__PARENT)
#define stb__chunks(z) (stb__chunk *) STB__DECODE((z)->chunks, STB__CHUNKS)
#define stb__setparent(z,p) (z)->parent = (stb__alloc *) STB__ENCODE((p), STB__PARENT)
#define stb__setchunks(z,c) (z)->chunks = (stb__chunk *) STB__ENCODE((c), STB__CHUNKS)
static stb__alloc stb__alloc_global =
{
NULL,
NULL,
NULL,
(stb__chunk *) STB__ENCODE(NULL, STB__CHUNKS)
};
static stb__alloc_type stb__identify(void *p)
{
void **q = (void **) p;
return (stb__alloc_type) ((stb_uinta) q[-1] & 3);
}
static void *** stb__prevn(void *p)
{
if (stb__identify(p) == STB__alloc) {
stb__alloc *s = (stb__alloc *) p - 1;
return &s->prevn;
} else {
stb__nochildren *s = (stb__nochildren *) p - 1;
return &s->prevn;
}
}
void stb_free(void *p)
{
if (p == NULL) return;
// count frees so that unit tests can see what's happening
++stb_alloc_count_free;
switch(stb__identify(p)) {
case STB__chunked:
// freeing a chunked-block with children does nothing;
// they only get freed when the parent does
// surely this is wrong, and it should free them immediately?
// otherwise how are they getting put on the right chain?
return;
case STB__nochildren: {
stb__nochildren *s = (stb__nochildren *) p - 1;
// unlink from sibling chain
*(s->prevn) = s->next;
if (s->next)
*stb__prevn(s->next) = s->prevn;
free(s);
return;
}
case STB__alloc: {
stb__alloc *s = (stb__alloc *) p - 1;
stb__chunk *c, *n;
void *q;
// unlink from sibling chain, if any
*(s->prevn) = s->next;
if (s->next)
*stb__prevn(s->next) = s->prevn;
// first free chunks
c = (stb__chunk *) stb__chunks(s);
while (c != NULL) {
n = c->next;
stb_alloc_count_free += c->alloc;
free(c);
c = n;
}
// validating
stb__setchunks(s,NULL);
s->prevn = NULL;
s->next = NULL;
// now free children
while ((q = s->child) != NULL) {
stb_free(q);
}
// now free self
free(s);
return;
}
default:
assert(0); /* NOTREACHED */
}
}
void stb_malloc_validate(void *p, void *parent)
{
if (p == NULL) return;
switch(stb__identify(p)) {
case STB__chunked:
return;
case STB__nochildren: {
stb__nochildren *n = (stb__nochildren *) p - 1;
if (n->prevn)
assert(*n->prevn == p);
if (n->next) {
assert(*stb__prevn(n->next) == &n->next);
stb_malloc_validate(n, parent);
}
return;
}
case STB__alloc: {
stb__alloc *s = (stb__alloc *) p - 1;
if (s->prevn)
assert(*s->prevn == p);
if (s->child) {
assert(*stb__prevn(s->child) == &s->child);
stb_malloc_validate(s->child, p);
}
if (s->next) {
assert(*stb__prevn(s->next) == &s->next);
stb_malloc_validate(s->next, parent);
}
return;
}
default:
assert(0); /* NOTREACHED */
}
}
static void * stb__try_chunk(stb__chunk *c, int size, int align, int pre_align)
{
char *memblock = (char *) (c+1), *q;
stb_inta iq;
int start_offset;
// we going to allocate at the end of the chunk, not the start. confusing,
// but it means we don't need both a 'limit' and a 'cur', just a 'cur'.
// the block ends at: p + c->data_left
// then we move back by size
start_offset = c->data_left - size;
// now we need to check the alignment of that
q = memblock + start_offset;
iq = (stb_inta) q;
assert(sizeof(q) == sizeof(iq));
// suppose align = 2
// then we need to retreat iq far enough that (iq & (2-1)) == 0
// to get (iq & (align-1)) = 0 requires subtracting (iq & (align-1))
start_offset -= iq & (align-1);
assert(((stb_uinta) (memblock+start_offset) & (align-1)) == 0);
// now, if that + pre_align works, go for it!
start_offset -= pre_align;
if (start_offset >= 0) {
c->data_left = start_offset;
return memblock + start_offset;
}
return NULL;
}
static void stb__sort_chunks(stb__alloc *src)
{
// of the first two chunks, put the chunk with more data left in it first
stb__chunk *c = stb__chunks(src), *d;
if (c == NULL) return;
d = c->next;
if (d == NULL) return;
if (c->data_left > d->data_left) return;
c->next = d->next;
d->next = c;
stb__setchunks(src, d);
}
static void * stb__alloc_chunk(stb__alloc *src, int size, int align, int pre_align)
{
void *p;
stb__chunk *c = stb__chunks(src);
if (c && size <= stb_alloc_chunk_size) {
p = stb__try_chunk(c, size, align, pre_align);
if (p) { ++c->alloc; return p; }
// try a second chunk to reduce wastage
if (c->next) {
p = stb__try_chunk(c->next, size, align, pre_align);
if (p) { ++c->alloc; return p; }
// put the bigger chunk first, since the second will get buried
// the upshot of this is that, until it gets allocated from, chunk #2
// is always the largest remaining chunk. (could formalize
// this with a heap!)
stb__sort_chunks(src);
c = stb__chunks(src);
}
}
// allocate a new chunk
{
stb__chunk *n;
int chunk_size = stb_alloc_chunk_size;
// we're going to allocate a new chunk to put this in
if (size > chunk_size)
chunk_size = size;
assert(sizeof(*n) + pre_align <= 16);
// loop trying to allocate a large enough chunk
// the loop is because the alignment may cause problems if it's big...
// and we don't know what our chunk alignment is going to be
while (1) {
n = (stb__chunk *) malloc(16 + chunk_size);
if (n == NULL) return NULL;
n->data_left = chunk_size - sizeof(*n);
p = stb__try_chunk(n, size, align, pre_align);
if (p != NULL) {
n->next = c;
stb__setchunks(src, n);
// if we just used up the whole block immediately,
// move the following chunk up
n->alloc = 1;
if (size == chunk_size)
stb__sort_chunks(src);
return p;
}
free(n);
chunk_size += 16+align;
}
}
}
static stb__alloc * stb__get_context(void *context)
{
if (context == NULL) {
return &stb__alloc_global;
} else {
int u = stb__identify(context);
// if context is chunked, grab parent
if (u == STB__chunked) {
stb__chunked *s = (stb__chunked *) context - 1;
return stb__parent(s);
} else {
return (stb__alloc *) context - 1;
}
}
}
static void stb__insert_alloc(stb__alloc *src, stb__alloc *s)
{
s->prevn = &src->child;
s->next = src->child;
src->child = s+1;
if (s->next)
*stb__prevn(s->next) = &s->next;
}
static void stb__insert_nochild(stb__alloc *src, stb__nochildren *s)
{
s->prevn = &src->child;
s->next = src->child;
src->child = s+1;
if (s->next)
*stb__prevn(s->next) = &s->next;
}
static void * malloc_base(void *context, size_t size, stb__alloc_type t, int align)
{
void *p;
stb__alloc *src = stb__get_context(context);
if (align <= 0) {
// compute worst-case C packed alignment
// e.g. a 24-byte struct is 8-aligned
int align_proposed = 1 << stb_lowbit8(size);
if (align_proposed < 0)
align_proposed = 4;
if (align_proposed == 0) {
if (size == 0)
align_proposed = 1;
else
align_proposed = 256;
}
// a negative alignment means 'don't align any larger
// than this'; so -16 means we align 1,2,4,8, or 16
if (align < 0) {
if (align_proposed > -align)
align_proposed = -align;
}
align = align_proposed;
}
assert(stb_is_pow2(align));
// don't cause misalignment when allocating nochildren
if (t == STB__nochildren && align > 8)
t = STB__alloc;
switch (t) {
case STB__alloc: {
stb__alloc *s = (stb__alloc *) malloc(size + sizeof(*s));
if (s == NULL) return NULL;
p = s+1;
s->child = NULL;
stb__insert_alloc(src, s);
stb__setchunks(s,NULL);
break;
}
case STB__nochildren: {
stb__nochildren *s = (stb__nochildren *) malloc(size + sizeof(*s));
if (s == NULL) return NULL;
p = s+1;
stb__insert_nochild(src, s);
break;
}
case STB__chunk_raw: {
p = stb__alloc_chunk(src, size, align, 0);
if (p == NULL) return NULL;
break;
}
case STB__chunked: {
stb__chunked *s;
if (align < sizeof(stb_uintptr)) align = sizeof(stb_uintptr);
s = (stb__chunked *) stb__alloc_chunk(src, size, align, sizeof(*s));
if (s == NULL) return NULL;
stb__setparent(s, src);
p = s+1;
break;
}
default: p = NULL; assert(0); /* NOTREACHED */
}
++stb_alloc_count_alloc;
return p;
}
void *stb_malloc_global(size_t size)
{
return malloc_base(NULL, size, STB__alloc, stb_alloc_alignment);
}
void *stb_malloc(void *context, size_t size)
{
return malloc_base(context, size, STB__alloc, stb_alloc_alignment);
}
void *stb_malloc_nofree(void *context, size_t size)
{
return malloc_base(context, size, STB__chunked, stb_alloc_alignment);
}
void *stb_malloc_leaf(void *context, size_t size)
{
return malloc_base(context, size, STB__nochildren, stb_alloc_alignment);
}
void *stb_malloc_raw(void *context, size_t size)
{
return malloc_base(context, size, STB__chunk_raw, stb_alloc_alignment);
}
char *stb_malloc_string(void *context, size_t size)
{
return (char *) malloc_base(context, size, STB__chunk_raw, 1);
}
void *stb_realloc(void *ptr, size_t newsize)
{
stb__alloc_type t;
if (ptr == NULL) return stb_malloc(NULL, newsize);
if (newsize == 0) { stb_free(ptr); return NULL; }
t = stb__identify(ptr);
assert(t == STB__alloc || t == STB__nochildren);
if (t == STB__alloc) {
stb__alloc *s = (stb__alloc *) ptr - 1;
s = (stb__alloc *) realloc(s, newsize + sizeof(*s));
if (s == NULL) return NULL;
ptr = s+1;
// update pointers
(*s->prevn) = ptr;
if (s->next)
*stb__prevn(s->next) = &s->next;
if (s->child)
*stb__prevn(s->child) = &s->child;
return ptr;
} else {
stb__nochildren *s = (stb__nochildren *) ptr - 1;
s = (stb__nochildren *) realloc(ptr, newsize + sizeof(s));
if (s == NULL) return NULL;
// update pointers
(*s->prevn) = s+1;
if (s->next)
*stb__prevn(s->next) = &s->next;
return s+1;
}
}
void *stb_realloc_c(void *context, void *ptr, size_t newsize)
{
if (ptr == NULL) return stb_malloc(context, newsize);
if (newsize == 0) { stb_free(ptr); return NULL; }
// @TODO: verify you haven't changed contexts
return stb_realloc(ptr, newsize);
}
void stb_reassign(void *new_context, void *ptr)
{
stb__alloc *src = stb__get_context(new_context);
stb__alloc_type t = stb__identify(ptr);
assert(t == STB__alloc || t == STB__nochildren);
if (t == STB__alloc) {
stb__alloc *s = (stb__alloc *) ptr - 1;
// unlink from old
*(s->prevn) = s->next;
if (s->next)
*stb__prevn(s->next) = s->prevn;
stb__insert_alloc(src, s);
} else {
stb__nochildren *s = (stb__nochildren *) ptr - 1;
// unlink from old
*(s->prevn) = s->next;
if (s->next)
*stb__prevn(s->next) = s->prevn;
stb__insert_nochild(src, s);
}
}
#endif
//////////////////////////////////////////////////////////////////////////////
//
// stb_arr
//
// An stb_arr is directly useable as a pointer (use the actual type in your
// definition), but when it resizes, it returns a new pointer and you can't
// use the old one, so you have to be careful to copy-in-out as necessary.
//
// Use a NULL pointer as a 0-length array.
//
// float *my_array = NULL, *temp;
//
// // add elements on the end one at a time
// stb_arr_push(my_array, 0.0f);
// stb_arr_push(my_array, 1.0f);
// stb_arr_push(my_array, 2.0f);
//
// assert(my_array[1] == 2.0f);
//
// // add an uninitialized element at the end, then assign it
// *stb_arr_add(my_array) = 3.0f;
//
// // add three uninitialized elements at the end
// temp = stb_arr_addn(my_array,3);
// temp[0] = 4.0f;
// temp[1] = 5.0f;
// temp[2] = 6.0f;
//
// assert(my_array[5] == 5.0f);
//
// // remove the last one
// stb_arr_pop(my_array);
//
// assert(stb_arr_len(my_array) == 6);
#ifdef STB_MALLOC_WRAPPER
#define STB__PARAMS , char *file, int line
#define STB__ARGS , file, line
#else
#define STB__PARAMS
#define STB__ARGS
#endif
// calling this function allocates an empty stb_arr attached to p
// (whereas NULL isn't attached to anything)
STB_EXTERN void stb_arr_malloc(void **target, void *context);
// call this function with a non-NULL value to have all successive
// stbs that are created be attached to the associated parent. Note
// that once a given stb_arr is non-empty, it stays attached to its
// current parent, even if you call this function again.
// it turns the previous value, so you can restore it
STB_EXTERN void* stb_arr_malloc_parent(void *p);
// simple functions written on top of other functions
#define stb_arr_empty(a) ( stb_arr_len(a) == 0 )
#define stb_arr_add(a) ( stb_arr_addn((a),1) )
#define stb_arr_push(a,v) ( *stb_arr_add(a)=(v) )
typedef struct
{
int len, limit;
int stb_malloc;
unsigned int signature;
} stb__arr;
#define stb_arr_signature 0x51bada7b // ends with 0123 in decimal
// access the header block stored before the data
#define stb_arrhead(a) /*lint --e(826)*/ (((stb__arr *) (a)) - 1)
#define stb_arrhead2(a) /*lint --e(826)*/ (((stb__arr *) (a)) - 1)
#ifdef STB_DEBUG
#define stb_arr_check(a) assert(!a || stb_arrhead(a)->signature == stb_arr_signature)
#define stb_arr_check2(a) assert(!a || stb_arrhead2(a)->signature == stb_arr_signature)
#else
#define stb_arr_check(a) ((void) 0)
#define stb_arr_check2(a) ((void) 0)
#endif
// ARRAY LENGTH
// get the array length; special case if pointer is NULL
#define stb_arr_len(a) (a ? stb_arrhead(a)->len : 0)
#define stb_arr_len2(a) ((stb__arr *) (a) ? stb_arrhead2(a)->len : 0)
#define stb_arr_lastn(a) (stb_arr_len(a)-1)
// check whether a given index is valid -- tests 0 <= i < stb_arr_len(a)
#define stb_arr_valid(a,i) (a ? (int) (i) < stb_arrhead(a)->len : 0)
// change the array length so is is exactly N entries long, creating
// uninitialized entries as needed
#define stb_arr_setlen(a,n) \
(stb__arr_setlen((void **) &(a), sizeof(a[0]), (n)))
// change the array length so that N is a valid index (that is, so
// it is at least N entries long), creating uninitialized entries as needed
#define stb_arr_makevalid(a,n) \
(stb_arr_len(a) < (n)+1 ? stb_arr_setlen(a,(n)+1),(a) : (a))
// remove the last element of the array, returning it
#define stb_arr_pop(a) ((stb_arr_check(a), (a))[--stb_arrhead(a)->len])
// access the last element in the array
#define stb_arr_last(a) ((stb_arr_check(a), (a))[stb_arr_len(a)-1])
// is iterator at end of list?
#define stb_arr_end(a,i) ((i) >= &(a)[stb_arr_len(a)])
// (internal) change the allocated length of the array
#define stb_arr__grow(a,n) (stb_arr_check(a), stb_arrhead(a)->len += (n))
// add N new unitialized elements to the end of the array
#define stb_arr__addn(a,n) /*lint --e(826)*/ \
((stb_arr_len(a)+(n) > stb_arrcurmax(a)) \
? (stb__arr_addlen((void **) &(a),sizeof(*a),(n)),0) \
: ((stb_arr__grow(a,n), 0)))
// add N new unitialized elements to the end of the array, and return
// a pointer to the first new one
#define stb_arr_addn(a,n) (stb_arr__addn((a),n),(a)+stb_arr_len(a)-(n))
// add N new uninitialized elements starting at index 'i'
#define stb_arr_insertn(a,i,n) (stb__arr_insertn((void **) &(a), sizeof(*a), i, n))
// insert an element at i
#define stb_arr_insert(a,i,v) (stb__arr_insertn((void **) &(a), sizeof(*a), i, 1), ((a)[i] = v))
// delete N elements from the middle starting at index 'i'
#define stb_arr_deleten(a,i,n) (stb__arr_deleten((void **) &(a), sizeof(*a), i, n))
// delete the i'th element
#define stb_arr_delete(a,i) stb_arr_deleten(a,i,1)
// delete the i'th element, swapping down from the end
#define stb_arr_fastdelete(a,i) \
(stb_swap(&a[i], &a[stb_arrhead(a)->len-1], sizeof(*a)), stb_arr_pop(a))
// ARRAY STORAGE
// get the array maximum storage; special case if NULL
#define stb_arrcurmax(a) (a ? stb_arrhead(a)->limit : 0)
#define stb_arrcurmax2(a) (a ? stb_arrhead2(a)->limit : 0)
// set the maxlength of the array to n in anticipation of further growth
#define stb_arr_setsize(a,n) (stb_arr_check(a), stb__arr_setsize((void **) &(a),sizeof((a)[0]),n))
// make sure maxlength is large enough for at least N new allocations
#define stb_arr_atleast(a,n) (stb_arr_len(a)+(n) > stb_arrcurmax(a) \
? stb_arr_setsize((a), (n)) : 0)
// make a copy of a given array (copies contents via 'memcpy'!)
#define stb_arr_copy(a) stb__arr_copy(a, sizeof((a)[0]))
// compute the storage needed to store all the elements of the array
#define stb_arr_storage(a) (stb_arr_len(a) * sizeof((a)[0]))
#define stb_arr_for(v,arr) for((v)=(arr); (v) < (arr)+stb_arr_len(arr); ++(v))
// IMPLEMENTATION
STB_EXTERN void stb_arr_free_(void **p);
STB_EXTERN void *stb__arr_copy_(void *p, int elem_size);
STB_EXTERN void stb__arr_setsize_(void **p, int size, int limit STB__PARAMS);
STB_EXTERN void stb__arr_setlen_(void **p, int size, int newlen STB__PARAMS);
STB_EXTERN void stb__arr_addlen_(void **p, int size, int addlen STB__PARAMS);
STB_EXTERN void stb__arr_deleten_(void **p, int size, int loc, int n STB__PARAMS);
STB_EXTERN void stb__arr_insertn_(void **p, int size, int loc, int n STB__PARAMS);
#define stb_arr_free(p) stb_arr_free_((void **) &(p))
#define stb__arr_copy stb__arr_copy_
#ifndef STB_MALLOC_WRAPPER
#define stb__arr_setsize stb__arr_setsize_
#define stb__arr_setlen stb__arr_setlen_
#define stb__arr_addlen stb__arr_addlen_
#define stb__arr_deleten stb__arr_deleten_
#define stb__arr_insertn stb__arr_insertn_
#else
#define stb__arr_addlen(p,s,n) stb__arr_addlen_(p,s,n,__FILE__,__LINE__)
#define stb__arr_setlen(p,s,n) stb__arr_setlen_(p,s,n,__FILE__,__LINE__)
#define stb__arr_setsize(p,s,n) stb__arr_setsize_(p,s,n,__FILE__,__LINE__)
#define stb__arr_deleten(p,s,i,n) stb__arr_deleten_(p,s,i,n,__FILE__,__LINE__)
#define stb__arr_insertn(p,s,i,n) stb__arr_insertn_(p,s,i,n,__FILE__,__LINE__)
#endif
#ifdef STB_DEFINE
static void *stb__arr_context;
void *stb_arr_malloc_parent(void *p)
{
void *q = stb__arr_context;
stb__arr_context = p;
return q;
}
void stb_arr_malloc(void **target, void *context)
{
stb__arr *q = (stb__arr *) stb_malloc(context, sizeof(*q));
q->len = q->limit = 0;
q->stb_malloc = 1;
q->signature = stb_arr_signature;
*target = (void *) (q+1);
}
static void * stb__arr_malloc(int size)
{
if (stb__arr_context)
return stb_malloc(stb__arr_context, size);
return malloc(size);
}
void * stb__arr_copy_(void *p, int elem_size)
{
stb__arr *q;
if (p == NULL) return p;
q = (stb__arr *) stb__arr_malloc(sizeof(*q) + elem_size * stb_arrhead2(p)->limit);
stb_arr_check2(p);
memcpy(q, stb_arrhead2(p), sizeof(*q) + elem_size * stb_arrhead2(p)->len);
q->stb_malloc = !!stb__arr_context;
return q+1;
}
void stb_arr_free_(void **pp)
{
void *p = *pp;
stb_arr_check2(p);
if (p) {
stb__arr *q = stb_arrhead2(p);
if (q->stb_malloc)
stb_free(q);
else
free(q);
}
*pp = NULL;
}
static void stb__arrsize_(void **pp, int size, int limit, int len STB__PARAMS)
{
void *p = *pp;
stb__arr *a;
stb_arr_check2(p);
if (p == NULL) {
if (len == 0 && size == 0) return;
a = (stb__arr *) stb__arr_malloc(sizeof(*a) + size*limit);
a->limit = limit;
a->len = len;
a->stb_malloc = !!stb__arr_context;
a->signature = stb_arr_signature;
} else {
a = stb_arrhead2(p);
a->len = len;
if (a->limit < limit) {
void *p;
if (a->limit >= 4 && limit < a->limit * 2)
limit = a->limit * 2;
if (a->stb_malloc)
p = stb_realloc(a, sizeof(*a) + limit*size);
else
#ifdef STB_MALLOC_WRAPPER
p = stb__realloc(a, sizeof(*a) + limit*size, file, line);
#else
p = realloc(a, sizeof(*a) + limit*size);
#endif
if (p) {
a = (stb__arr *) p;
a->limit = limit;
} else {
// throw an error!
}
}
}
a->len = stb_min(a->len, a->limit);
*pp = a+1;
}
void stb__arr_setsize_(void **pp, int size, int limit STB__PARAMS)
{
void *p = *pp;
stb_arr_check2(p);
stb__arrsize_(pp, size, limit, stb_arr_len2(p) STB__ARGS);
}
void stb__arr_setlen_(void **pp, int size, int newlen STB__PARAMS)
{
void *p = *pp;
stb_arr_check2(p);
if (stb_arrcurmax2(p) < newlen || p == NULL) {
stb__arrsize_(pp, size, newlen, newlen STB__ARGS);
} else {
stb_arrhead2(p)->len = newlen;
}
}
void stb__arr_addlen_(void **p, int size, int addlen STB__PARAMS)
{
stb__arr_setlen_(p, size, stb_arr_len2(*p) + addlen STB__ARGS);
}
void stb__arr_insertn_(void **pp, int size, int i, int n STB__PARAMS)
{
void *p = *pp;
if (n) {
int z;
if (p == NULL) {
stb__arr_addlen_(pp, size, n STB__ARGS);
return;
}
z = stb_arr_len2(p);
stb__arr_addlen_(&p, size, n STB__ARGS);
memmove((char *) p + (i+n)*size, (char *) p + i*size, size * (z-i));
}
*pp = p;
}
void stb__arr_deleten_(void **pp, int size, int i, int n STB__PARAMS)
{
void *p = *pp;
if (n) {
memmove((char *) p + i*size, (char *) p + (i+n)*size, size * (stb_arr_len2(p)-(i+n)));
stb_arrhead2(p)->len -= n;
}
*pp = p;
}
#endif
//////////////////////////////////////////////////////////////////////////////
//
// Hashing
//
// typical use for this is to make a power-of-two hash table.
//
// let N = size of table (2^n)
// let H = stb_hash(str)
// let S = stb_rehash(H) | 1
//
// then hash probe sequence P(i) for i=0..N-1
// P(i) = (H + S*i) & (N-1)
//
// the idea is that H has 32 bits of hash information, but the
// table has only, say, 2^20 entries so only uses 20 of the bits.
// then by rehashing the original H we get 2^12 different probe
// sequences for a given initial probe location. (So it's optimal
// for 64K tables and its optimality decreases past that.)
//
// ok, so I've added something that generates _two separate_
// 32-bit hashes simultaneously which should scale better to
// very large tables.
STB_EXTERN unsigned int stb_hash(char *str);
STB_EXTERN unsigned int stb_hashptr(void *p);
STB_EXTERN unsigned int stb_hashlen(char *str, int len);
STB_EXTERN unsigned int stb_rehash_improved(unsigned int v);
STB_EXTERN unsigned int stb_hash_fast(void *p, int len);
STB_EXTERN unsigned int stb_hash2(char *str, unsigned int *hash2_ptr);
STB_EXTERN unsigned int stb_hash_number(unsigned int hash);
#define stb_rehash(x) ((x) + ((x) >> 6) + ((x) >> 19))
#ifdef STB_DEFINE
unsigned int stb_hash(char *str)
{
unsigned int hash = 0;
while (*str)
hash = (hash << 7) + (hash >> 25) + *str++;
return hash + (hash >> 16);
}
unsigned int stb_hashlen(char *str, int len)
{
unsigned int hash = 0;
while (len-- > 0 && *str)
hash = (hash << 7) + (hash >> 25) + *str++;
return hash + (hash >> 16);
}
unsigned int stb_hashptr(void *p)
{
unsigned int x = (unsigned int)(size_t) p;
// typically lacking in low bits and high bits
x = stb_rehash(x);
x += x << 16;
// pearson's shuffle
x ^= x << 3;
x += x >> 5;
x ^= x << 2;
x += x >> 15;
x ^= x << 10;
return stb_rehash(x);
}
unsigned int stb_rehash_improved(unsigned int v)
{
return stb_hashptr((void *)(size_t) v);
}
unsigned int stb_hash2(char *str, unsigned int *hash2_ptr)
{
unsigned int hash1 = 0x3141592c;
unsigned int hash2 = 0x77f044ed;
while (*str) {
hash1 = (hash1 << 7) + (hash1 >> 25) + *str;
hash2 = (hash2 << 11) + (hash2 >> 21) + *str;
++str;
}
*hash2_ptr = hash2 + (hash1 >> 16);
return hash1 + (hash2 >> 16);
}
// Paul Hsieh hash
#define stb__get16_slow(p) ((p)[0] + ((p)[1] << 8))
#if defined(_MSC_VER)
#define stb__get16(p) (*((unsigned short *) (p)))
#else
#define stb__get16(p) stb__get16_slow(p)
#endif
unsigned int stb_hash_fast(void *p, int len)
{
unsigned char *q = (unsigned char *) p;
unsigned int hash = len;
if (len <= 0 || q == NULL) return 0;
/* Main loop */
if (((int)(size_t) q & 1) == 0) {
for (;len > 3; len -= 4) {
unsigned int val;
hash += stb__get16(q);
val = (stb__get16(q+2) << 11);
hash = (hash << 16) ^ hash ^ val;
q += 4;
hash += hash >> 11;
}
} else {
for (;len > 3; len -= 4) {
unsigned int val;
hash += stb__get16_slow(q);
val = (stb__get16_slow(q+2) << 11);
hash = (hash << 16) ^ hash ^ val;
q += 4;
hash += hash >> 11;
}
}
/* Handle end cases */
switch (len) {
case 3: hash += stb__get16_slow(q);
hash ^= hash << 16;
hash ^= q[2] << 18;
hash += hash >> 11;
break;
case 2: hash += stb__get16_slow(q);
hash ^= hash << 11;
hash += hash >> 17;
break;
case 1: hash += q[0];
hash ^= hash << 10;
hash += hash >> 1;
break;
case 0: break;
}
/* Force "avalanching" of final 127 bits */
hash ^= hash << 3;
hash += hash >> 5;
hash ^= hash << 4;
hash += hash >> 17;
hash ^= hash << 25;
hash += hash >> 6;
return hash;
}
unsigned int stb_hash_number(unsigned int hash)
{
hash ^= hash << 3;
hash += hash >> 5;
hash ^= hash << 4;
hash += hash >> 17;
hash ^= hash << 25;
hash += hash >> 6;
return hash;
}
#endif
//////////////////////////////////////////////////////////////////////////////
//
// Perfect hashing for ints/pointers
//
// This is mainly useful for making faster pointer-indexed tables
// that don't change frequently. E.g. for stb_ischar().
//
typedef struct
{
stb_uint32 addend;
stb_uint multiplicand;
stb_uint b_mask;
stb_uint8 small_bmap[16];
stb_uint16 *large_bmap;
stb_uint table_mask;
stb_uint32 *table;
} stb_perfect;
STB_EXTERN int stb_perfect_create(stb_perfect *,unsigned int*,int n);
STB_EXTERN void stb_perfect_destroy(stb_perfect *);
STB_EXTERN int stb_perfect_hash(stb_perfect *, unsigned int x);
extern int stb_perfect_hash_max_failures;
#ifdef STB_DEFINE
int stb_perfect_hash_max_failures;
int stb_perfect_hash(stb_perfect *p, unsigned int x)
{
stb_uint m = x * p->multiplicand;
stb_uint y = x >> 16;
stb_uint bv = (m >> 24) + y;
stb_uint av = (m + y) >> 12;
if (p->table == NULL) return -1; // uninitialized table fails
bv &= p->b_mask;
av &= p->table_mask;
if (p->large_bmap)
av ^= p->large_bmap[bv];
else
av ^= p->small_bmap[bv];
return p->table[av] == x ? av : -1;
}
static void stb__perfect_prehash(stb_perfect *p, stb_uint x, stb_uint16 *a, stb_uint16 *b)
{
stb_uint m = x * p->multiplicand;
stb_uint y = x >> 16;
stb_uint bv = (m >> 24) + y;
stb_uint av = (m + y) >> 12;
bv &= p->b_mask;
av &= p->table_mask;
*b = bv;
*a = av;
}
static unsigned long stb__perfect_rand(void)
{
static unsigned long stb__rand;
stb__rand = stb__rand * 2147001325 + 715136305;
return 0x31415926 ^ ((stb__rand >> 16) + (stb__rand << 16));
}
typedef struct {
unsigned short count;
unsigned short b;
unsigned short map;
unsigned short *entries;
} stb__slot;
static int stb__slot_compare(const void *p, const void *q)
{
stb__slot *a = (stb__slot *) p;
stb__slot *b = (stb__slot *) q;
return a->count > b->count ? -1 : a->count < b->count; // sort large to small
}
int stb_perfect_create(stb_perfect *p, unsigned int *v, int n)
{
unsigned int buffer1[64], buffer2[64], buffer3[64], buffer4[64], buffer5[32];
unsigned short *as = (unsigned short *) stb_temp(buffer1, sizeof(*v)*n);
unsigned short *bs = (unsigned short *) stb_temp(buffer2, sizeof(*v)*n);
unsigned short *entries = (unsigned short *) stb_temp(buffer4, sizeof(*entries) * n);
int size = 1 << stb_log2_ceil(n), bsize=8;
int failure = 0,i,j,k;
assert(n <= 32768);
p->large_bmap = NULL;
for(;;) {
stb__slot *bcount = (stb__slot *) stb_temp(buffer3, sizeof(*bcount) * bsize);
unsigned short *bloc = (unsigned short *) stb_temp(buffer5, sizeof(*bloc) * bsize);
unsigned short *e;
int bad=0;
p->addend = stb__perfect_rand();
p->multiplicand = stb__perfect_rand() | 1;
p->table_mask = size-1;
p->b_mask = bsize-1;
p->table = (stb_uint32 *) malloc(size * sizeof(*p->table));
for (i=0; i < bsize; ++i) {
bcount[i].b = i;
bcount[i].count = 0;
bcount[i].map = 0;
}
for (i=0; i < n; ++i) {
stb__perfect_prehash(p, v[i], as+i, bs+i);
++bcount[bs[i]].count;
}
qsort(bcount, bsize, sizeof(*bcount), stb__slot_compare);
e = entries; // now setup up their entries index
for (i=0; i < bsize; ++i) {
bcount[i].entries = e;
e += bcount[i].count;
bcount[i].count = 0;
bloc[bcount[i].b] = i;
}
// now fill them out
for (i=0; i < n; ++i) {
int b = bs[i];
int w = bloc[b];
bcount[w].entries[bcount[w].count++] = i;
}
stb_tempfree(buffer5,bloc);
// verify
for (i=0; i < bsize; ++i)
for (j=0; j < bcount[i].count; ++j)
assert(bs[bcount[i].entries[j]] == bcount[i].b);
memset(p->table, 0, size*sizeof(*p->table));
// check if any b has duplicate a
for (i=0; i < bsize; ++i) {
if (bcount[i].count > 1) {
for (j=0; j < bcount[i].count; ++j) {
if (p->table[as[bcount[i].entries[j]]])
bad = 1;
p->table[as[bcount[i].entries[j]]] = 1;
}
for (j=0; j < bcount[i].count; ++j) {
p->table[as[bcount[i].entries[j]]] = 0;
}
if (bad) break;
}
}
if (!bad) {
// go through the bs and populate the table, first fit
for (i=0; i < bsize; ++i) {
if (bcount[i].count) {
// go through the candidate table[b] values
for (j=0; j < size; ++j) {
// go through the a values and see if they fit
for (k=0; k < bcount[i].count; ++k) {
int a = as[bcount[i].entries[k]];
if (p->table[(a^j)&p->table_mask]) {
break; // fails
}
}
// if succeeded, accept
if (k == bcount[i].count) {
bcount[i].map = j;
for (k=0; k < bcount[i].count; ++k) {
int a = as[bcount[i].entries[k]];
p->table[(a^j)&p->table_mask] = 1;
}
break;
}
}
if (j == size)
break; // no match for i'th entry, so break out in failure
}
}
if (i == bsize) {
// success... fill out map
if (bsize <= 16 && size <= 256) {
p->large_bmap = NULL;
for (i=0; i < bsize; ++i)
p->small_bmap[bcount[i].b] = (stb_uint8) bcount[i].map;
} else {
p->large_bmap = (unsigned short *) malloc(sizeof(*p->large_bmap) * bsize);
for (i=0; i < bsize; ++i)
p->large_bmap[bcount[i].b] = bcount[i].map;
}
// initialize table to v[0], so empty slots will fail
for (i=0; i < size; ++i)
p->table[i] = v[0];
for (i=0; i < n; ++i)
if (p->large_bmap)
p->table[as[i] ^ p->large_bmap[bs[i]]] = v[i];
else
p->table[as[i] ^ p->small_bmap[bs[i]]] = v[i];
// and now validate that none of them collided
for (i=0; i < n; ++i)
assert(stb_perfect_hash(p, v[i]) >= 0);
stb_tempfree(buffer3, bcount);
break;
}
}
free(p->table);
p->table = NULL;
stb_tempfree(buffer3, bcount);
++failure;
if (failure >= 4 && bsize < size) bsize *= 2;
if (failure >= 8 && (failure & 3) == 0 && size < 4*n) {
size *= 2;
bsize *= 2;
}
if (failure == 6) {
// make sure the input data is unique, so we don't infinite loop
unsigned int *data = (unsigned int *) stb_temp(buffer3, n * sizeof(*data));
memcpy(data, v, sizeof(*data) * n);
qsort(data, n, sizeof(*data), stb_intcmp(0));
for (i=1; i < n; ++i) {
if (data[i] == data[i-1])
size = 0; // size is return value, so 0 it
}
stb_tempfree(buffer3, data);
if (!size) break;
}
}
if (failure > stb_perfect_hash_max_failures)
stb_perfect_hash_max_failures = failure;
stb_tempfree(buffer1, as);
stb_tempfree(buffer2, bs);
stb_tempfree(buffer4, entries);
return size;
}
void stb_perfect_destroy(stb_perfect *p)
{
if (p->large_bmap) free(p->large_bmap);
if (p->table ) free(p->table);
p->large_bmap = NULL;
p->table = NULL;
p->b_mask = 0;
p->table_mask = 0;
}
#endif
//////////////////////////////////////////////////////////////////////////////
//
// Perfect hash clients
STB_EXTERN int stb_ischar(char s, char *set);
#ifdef STB_DEFINE
int stb_ischar(char c, char *set)
{
static unsigned char bit[8] = { 1,2,4,8,16,32,64,128 };
static stb_perfect p;
static unsigned char (*tables)[256];
static char ** sets = NULL;
int z = stb_perfect_hash(&p, (int)(size_t) set);
if (z < 0) {
int i,k,n,j,f;
// special code that means free all existing data
if (set == NULL) {
stb_arr_free(sets);
free(tables);
tables = NULL;
stb_perfect_destroy(&p);
return 0;
}
stb_arr_push(sets, set);
stb_perfect_destroy(&p);
n = stb_perfect_create(&p, (unsigned int *) (char **) sets, stb_arr_len(sets));
assert(n != 0);
k = (n+7) >> 3;
tables = (unsigned char (*)[256]) realloc(tables, sizeof(*tables) * k);
memset(tables, 0, sizeof(*tables) * k);
for (i=0; i < stb_arr_len(sets); ++i) {
k = stb_perfect_hash(&p, (int)(size_t) sets[i]);
assert(k >= 0);
n = k >> 3;
f = bit[k&7];
for (j=0; !j || sets[i][j]; ++j) {
tables[n][(unsigned char) sets[i][j]] |= f;
}
}
z = stb_perfect_hash(&p, (int)(size_t) set);
}
return tables[z >> 3][(unsigned char) c] & bit[z & 7];
}
#endif
//////////////////////////////////////////////////////////////////////////////
//
// Instantiated data structures
//
// This is an attempt to implement a templated data structure.
//
// Hash table: call stb_define_hash(TYPE,N,KEY,K1,K2,HASH,VALUE)
// TYPE -- will define a structure type containing the hash table
// N -- the name, will prefix functions named:
// N create
// N destroy
// N get
// N set, N add, N update,
// N remove
// KEY -- the type of the key. 'x == y' must be valid
// K1,K2 -- keys never used by the app, used as flags in the hashtable
// HASH -- a piece of code ending with 'return' that hashes key 'k'
// VALUE -- the type of the value. 'x = y' must be valid
//
// Note that stb_define_hash_base can be used to define more sophisticated
// hash tables, e.g. those that make copies of the key or use special
// comparisons (e.g. strcmp).
#define STB_(prefix,name) stb__##prefix##name
#define STB__(prefix,name) prefix##name
#define STB__use(x) x
#define STB__skip(x)
#define stb_declare_hash(PREFIX,TYPE,N,KEY,VALUE) \