diff options
Diffstat (limited to 'libs/raylib/src')
| -rw-r--r-- | libs/raylib/src/external/msf_gif.h | 608 | ||||
| -rw-r--r-- | libs/raylib/src/external/sdefl.h | 697 | ||||
| -rw-r--r-- | libs/raylib/src/external/sinfl.h | 464 | ||||
| -rw-r--r-- | libs/raylib/src/uwp_events.h | 119 |
4 files changed, 1888 insertions, 0 deletions
diff --git a/libs/raylib/src/external/msf_gif.h b/libs/raylib/src/external/msf_gif.h new file mode 100644 index 0000000..348b1b1 --- /dev/null +++ b/libs/raylib/src/external/msf_gif.h @@ -0,0 +1,608 @@ +/* +HOW TO USE: + + In exactly one translation unit (.c or .cpp file), #define MSF_GIF_IMPL before including the header, like so: + + #define MSF_GIF_IMPL + #include "msf_gif.h" + + Everywhere else, just include the header like normal. + + +USAGE EXAMPLE: + + int width = 480, height = 320, centisecondsPerFrame = 5, bitDepth = 16; + MsfGifState gifState = {}; + msf_gif_begin(&gifState, width, height); + msf_gif_frame(&gifState, ..., centisecondsPerFrame, bitDepth, width * 4); //frame 1 + msf_gif_frame(&gifState, ..., centisecondsPerFrame, bitDepth, width * 4); //frame 2 + msf_gif_frame(&gifState, ..., centisecondsPerFrame, bitDepth, width * 4); //frame 3, etc... + MsfGifResult result = msf_gif_end(&gifState); + FILE * fp = fopen("MyGif.gif", "wb"); + fwrite(result.data, result.dataSize, 1, fp); + fclose(fp); + msf_gif_free(result); + +Detailed function documentation can be found in the header section below. + + +REPLACING MALLOC: + + This library uses malloc+realloc+free internally for memory allocation. + To facilitate integration with custom memory allocators, these calls go through macros, which can be redefined. + The expected function signature equivalents of the macros are as follows: + + void * MSF_GIF_MALLOC(void * context, size_t newSize) + void * MSF_GIF_REALLOC(void * context, void * oldMemory, size_t oldSize, size_t newSize) + void MSF_GIF_FREE(void * context, void * oldMemory, size_t oldSize) + + If your allocator needs a context pointer, you can set the `customAllocatorContext` field of the MsfGifState struct + before calling msf_gif_begin(), and it will be passed to all subsequent allocator macro calls. + +See end of file for license information. +*/ + +//version 2.1 + +#ifndef MSF_GIF_H +#define MSF_GIF_H + +#include <stdint.h> +#include <stddef.h> + +typedef struct { + void * data; + size_t dataSize; + + size_t allocSize; //internal use + void * contextPointer; //internal use +} MsfGifResult; + +typedef struct { //internal use + uint32_t * pixels; + int depth, count, rbits, gbits, bbits; +} MsfCookedFrame; + +typedef struct { + MsfCookedFrame previousFrame; + uint8_t * listHead; + uint8_t * listTail; + int width, height; + void * customAllocatorContext; +} MsfGifState; + +#ifdef __cplusplus +extern "C" { +#endif //__cplusplus + +/** + * @param width Image width in pixels. + * @param height Image height in pixels. + * @return Non-zero on success, 0 on error. + */ +int msf_gif_begin(MsfGifState * handle, int width, int height); + +/** + * @param pixelData Pointer to raw framebuffer data. Rows must be contiguous in memory, in RGBA8 format. + * Note: This function does NOT free `pixelData`. You must free it yourself afterwards. + * @param centiSecondsPerFrame How many hundredths of a second this frame should be displayed for. + * Note: This being specified in centiseconds is a limitation of the GIF format. + * @param maxBitDepth Limits how many bits per pixel can be used when quantizing the gif. + * The actual bit depth chosen for a given frame will be less than or equal to + * the supplied maximum, depending on the variety of colors used in the frame. + * `maxBitDepth` will be clamped between 1 and 16. The recommended default is 16. + * Lowering this value can result in faster exports and smaller gifs, + * but the quality may suffer. + * Please experiment with this value to find what works best for your application. + * @param pitchInBytes The number of bytes from the beginning of one row of pixels to the beginning of the next. + * If you want to flip the image, just pass in a negative pitch. + * @return Non-zero on success, 0 on error. + */ +int msf_gif_frame(MsfGifState * handle, uint8_t * pixelData, int centiSecondsPerFame, int maxBitDepth, int pitchInBytes); + +/** + * @return A block of memory containing the gif file data, or NULL on error. + * You are responsible for freeing this via `msf_gif_free()`. + */ +MsfGifResult msf_gif_end(MsfGifState * handle); + +/** + * @param result The MsfGifResult struct, verbatim as it was returned from `msf_gif_end()`. + */ +void msf_gif_free(MsfGifResult result); + +#ifdef __cplusplus +} +#endif //__cplusplus + +#endif //MSF_GIF_H + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/// IMPLEMENTATION /// +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +#ifdef MSF_GIF_IMPL +#ifndef MSF_GIF_ALREADY_IMPLEMENTED_IN_THIS_TRANSLATION_UNIT +#define MSF_GIF_ALREADY_IMPLEMENTED_IN_THIS_TRANSLATION_UNIT + +#ifndef MSF_GIF_BUFFER_INIT_SIZE +#define MSF_GIF_BUFFER_INIT_SIZE 1024 * 1024 * 4 //4MB by default, you can increase this if you want to realloc less +#endif + +//ensure the library user has either defined all of malloc/realloc/free, or none +#if defined(MSF_GIF_MALLOC) && defined(MSF_GIF_REALLOC) && defined(MSF_GIF_FREE) //ok +#elif !defined(MSF_GIF_MALLOC) && !defined(MSF_GIF_REALLOC) && !defined(MSF_GIF_FREE) //ok +#else +#error "You must either define all of MSF_GIF_MALLOC, MSF_GIF_REALLOC, and MSF_GIF_FREE, or define none of them" +#endif + +//provide default allocator definitions that redirect to the standard global allocator +#if !defined(MSF_GIF_MALLOC) +#include <stdlib.h> //malloc, etc. +#define MSF_GIF_MALLOC(contextPointer, newSize) malloc(newSize) +#define MSF_GIF_REALLOC(contextPointer, oldMemory, oldSize, newSize) realloc(oldMemory, newSize) +#define MSF_GIF_FREE(contextPointer, oldMemory, oldSize) free(oldMemory) +#endif + +//instrumentation for capturing profiling traces (useless for the library user, but useful for the library author) +#ifdef MSF_GIF_ENABLE_TRACING +#define MsfTimeFunc TimeFunc +#define MsfTimeLoop TimeLoop +#define msf_init_profiling_thread init_profiling_thread +#else +#define MsfTimeFunc +#define MsfTimeLoop(name) +#define msf_init_profiling_thread() +#endif //MSF_GIF_ENABLE_TRACING + +#include <string.h> //memcpy + +//TODO: use compiler-specific notation to force-inline functions currently marked inline +#if defined(__GNUC__) //gcc, clang +static inline int msf_bit_log(int i) { return 32 - __builtin_clz(i); } +#elif defined(_MSC_VER) //msvc +#include <intrin.h> +static inline int msf_bit_log(int i) { unsigned long idx; _BitScanReverse(&idx, i); return idx + 1; } +#else //fallback implementation for other compilers +//from https://stackoverflow.com/a/31718095/3064745 - thanks! +static inline int msf_bit_log(int i) { + static const int MultiplyDeBruijnBitPosition[32] = { + 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, + 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31, + }; + i |= i >> 1; + i |= i >> 2; + i |= i >> 4; + i |= i >> 8; + i |= i >> 16; + return MultiplyDeBruijnBitPosition[(uint32_t)(i * 0x07C4ACDDU) >> 27] + 1; +} +#endif +static inline int msf_imin(int a, int b) { return a < b? a : b; } +static inline int msf_imax(int a, int b) { return b < a? a : b; } + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/// Frame Cooking /// +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +#if (defined (__SSE2__) || defined (_M_X64) || _M_IX86_FP == 2) && !defined(MSF_GIF_NO_SSE2) +#include <emmintrin.h> +#endif + +static MsfCookedFrame msf_cook_frame(void * allocContext, uint8_t * raw, uint8_t * used, + int width, int height, int pitch, int depth) +{ MsfTimeFunc + //bit depth for each channel + const static int rdepths[17] = { 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5 }; + const static int gdepths[17] = { 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6 }; + const static int bdepths[17] = { 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5 }; + + const static int ditherKernel[16] = { + 0 << 12, 8 << 12, 2 << 12, 10 << 12, + 12 << 12, 4 << 12, 14 << 12, 6 << 12, + 3 << 12, 11 << 12, 1 << 12, 9 << 12, + 15 << 12, 7 << 12, 13 << 12, 5 << 12, + }; + + uint32_t * cooked = (uint32_t *) MSF_GIF_MALLOC(allocContext, width * height * sizeof(uint32_t)); + if (!cooked) { MsfCookedFrame blank = {0}; return blank; } + + int count = 0; + MsfTimeLoop("do") do { + int rbits = rdepths[depth], gbits = gdepths[depth], bbits = bdepths[depth]; + int paletteSize = 1 << (rbits + gbits + bbits); + memset(used, 0, paletteSize * sizeof(uint8_t)); + + //TODO: document what this math does and why it's correct + int rdiff = (1 << (8 - rbits)) - 1; + int gdiff = (1 << (8 - gbits)) - 1; + int bdiff = (1 << (8 - bbits)) - 1; + short rmul = (short) ((255.0f - rdiff) / 255.0f * 257); + short gmul = (short) ((255.0f - gdiff) / 255.0f * 257); + short bmul = (short) ((255.0f - bdiff) / 255.0f * 257); + + int gmask = ((1 << gbits) - 1) << rbits; + int bmask = ((1 << bbits) - 1) << rbits << gbits; + + MsfTimeLoop("cook") for (int y = 0; y < height; ++y) { + int x = 0; + + #if (defined (__SSE2__) || defined (_M_X64) || _M_IX86_FP == 2) && !defined(MSF_GIF_NO_SSE2) + __m128i k = _mm_loadu_si128((__m128i *) &ditherKernel[(y & 3) * 4]); + __m128i k2 = _mm_or_si128(_mm_srli_epi32(k, rbits), _mm_slli_epi32(_mm_srli_epi32(k, bbits), 16)); + // MsfTimeLoop("SIMD") + for (; x < width - 3; x += 4) { + uint8_t * pixels = &raw[y * pitch + x * 4]; + __m128i p = _mm_loadu_si128((__m128i *) pixels); + + __m128i rb = _mm_and_si128(p, _mm_set1_epi32(0x00FF00FF)); + __m128i rb1 = _mm_mullo_epi16(rb, _mm_set_epi16(bmul, rmul, bmul, rmul, bmul, rmul, bmul, rmul)); + __m128i rb2 = _mm_adds_epu16(rb1, k2); + __m128i r3 = _mm_srli_epi32(_mm_and_si128(rb2, _mm_set1_epi32(0x0000FFFF)), 16 - rbits); + __m128i b3 = _mm_and_si128(_mm_srli_epi32(rb2, 32 - rbits - gbits - bbits), _mm_set1_epi32(bmask)); + + __m128i g = _mm_and_si128(_mm_srli_epi32(p, 8), _mm_set1_epi32(0x000000FF)); + __m128i g1 = _mm_mullo_epi16(g, _mm_set1_epi32(gmul)); + __m128i g2 = _mm_adds_epu16(g1, _mm_srli_epi32(k, gbits)); + __m128i g3 = _mm_and_si128(_mm_srli_epi32(g2, 16 - rbits - gbits), _mm_set1_epi32(gmask)); + + //TODO: does storing this as a __m128i then reading it back as a uint32_t violate strict aliasing? + uint32_t * c = &cooked[y * width + x]; + __m128i out = _mm_or_si128(_mm_or_si128(r3, g3), b3); + _mm_storeu_si128((__m128i *) c, out); + } + #endif + + //scalar cleanup loop + // MsfTimeLoop("scalar") + for (; x < width; ++x) { + uint8_t * p = &raw[y * pitch + x * 4]; + int dx = x & 3, dy = y & 3; + int k = ditherKernel[dy * 4 + dx]; + cooked[y * width + x] = + (msf_imin(65535, p[2] * bmul + (k >> bbits)) >> (16 - rbits - gbits - bbits) & bmask) | + (msf_imin(65535, p[1] * gmul + (k >> gbits)) >> (16 - rbits - gbits ) & gmask) | + msf_imin(65535, p[0] * rmul + (k >> rbits)) >> (16 - rbits ); + } + } + + count = 0; + MsfTimeLoop("mark and count") for (int i = 0; i < width * height; ++i) { + used[cooked[i]] = 1; + } + + //count used colors + MsfTimeLoop("count") for (int j = 0; j < paletteSize; ++j) { + count += used[j]; + } + } while (count >= 256 && --depth); + + MsfCookedFrame ret = { cooked, depth, count, rdepths[depth], gdepths[depth], bdepths[depth] }; + return ret; +} + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/// Frame Compression /// +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +typedef struct { + uint8_t * next; + size_t size; +} MsfBufferHeader; + +static inline int msf_put_code(uint8_t * * writeHead, uint32_t * blockBits, int len, uint32_t code) { + //insert new code into block buffer + int idx = *blockBits / 8; + int bit = *blockBits % 8; + (*writeHead)[idx + 0] |= code << bit ; + (*writeHead)[idx + 1] |= code >> ( 8 - bit); + (*writeHead)[idx + 2] |= code >> (16 - bit); + *blockBits += len; + + //prep the next block buffer if the current one is full + if (*blockBits >= 256 * 8) { + *blockBits -= 255 * 8; + (*writeHead) += 256; + (*writeHead)[2] = (*writeHead)[1]; + (*writeHead)[1] = (*writeHead)[0]; + (*writeHead)[0] = 255; + memset((*writeHead) + 4, 0, 256); + } + + return 1; +} + +typedef struct { + int16_t * data; + int len; + int stride; +} MsfStridedList; + +static inline void msf_lzw_reset(MsfStridedList * lzw, int tableSize, int stride) { MsfTimeFunc + memset(lzw->data, 0xFF, 4096 * stride * sizeof(int16_t)); + lzw->len = tableSize + 2; + lzw->stride = stride; +} + +static uint8_t * msf_compress_frame(void * allocContext, int width, int height, int centiSeconds, + MsfCookedFrame frame, MsfCookedFrame previous, uint8_t * used) +{ MsfTimeFunc + //NOTE: we reserve enough memory for theoretical the worst case upfront because it's a reasonable amount, + // and prevents us from ever having to check size or realloc during compression + int maxBufSize = sizeof(MsfBufferHeader) + 32 + 256 * 3 + width * height * 3 / 2; //headers + color table + data + uint8_t * allocation = (uint8_t *) MSF_GIF_MALLOC(allocContext, maxBufSize); + if (!allocation) { return NULL; } + uint8_t * writeBase = allocation + sizeof(MsfBufferHeader); + uint8_t * writeHead = writeBase; + int lzwAllocSize = 4096 * (frame.count + 1) * sizeof(int16_t); + MsfStridedList lzw = { (int16_t *) MSF_GIF_MALLOC(allocContext, lzwAllocSize) }; + if (!lzw.data) { MSF_GIF_FREE(allocContext, allocation, maxBufSize); return NULL; } + + //allocate tlb + int totalBits = frame.rbits + frame.gbits + frame.bbits; + int tlbSize = 1 << totalBits; + uint8_t tlb[1 << 16]; //only 64k, so stack allocating is fine + + //generate palette + typedef struct { uint8_t r, g, b; } Color3; + Color3 table[256] = { {0} }; + int tableIdx = 1; //we start counting at 1 because 0 is the transparent color + MsfTimeLoop("table") for (int i = 0; i < tlbSize; ++i) { + if (used[i]) { + tlb[i] = tableIdx; + int rmask = (1 << frame.rbits) - 1; + int gmask = (1 << frame.gbits) - 1; + //isolate components + int r = i & rmask; + int g = i >> frame.rbits & gmask; + int b = i >> (frame.rbits + frame.gbits); + //shift into highest bits + r <<= 8 - frame.rbits; + g <<= 8 - frame.gbits; + b <<= 8 - frame.bbits; + table[tableIdx].r = r | r >> frame.rbits | r >> (frame.rbits * 2) | r >> (frame.rbits * 3); + table[tableIdx].g = g | g >> frame.gbits | g >> (frame.gbits * 2) | g >> (frame.gbits * 3); + table[tableIdx].b = b | b >> frame.bbits | b >> (frame.bbits * 2) | b >> (frame.bbits * 3); + ++tableIdx; + } + } + + //SPEC: "Because of some algorithmic constraints however, black & white images which have one color bit + // must be indicated as having a code size of 2." + int tableBits = msf_imax(2, msf_bit_log(tableIdx - 1)); + int tableSize = 1 << tableBits; + //NOTE: we don't just compare `depth` field here because it will be wrong for the first frame and we will segfault + int hasSamePal = frame.rbits == previous.rbits && frame.gbits == previous.gbits && frame.bbits == previous.bbits; + + //NOTE: because __attribute__((__packed__)) is annoyingly compiler-specific, we do this unreadable weirdness + char headerBytes[19] = "\x21\xF9\x04\x05\0\0\0\0" "\x2C\0\0\0\0\0\0\0\0\x80"; + memcpy(&headerBytes[4], ¢iSeconds, 2); + memcpy(&headerBytes[13], &width, 2); + memcpy(&headerBytes[15], &height, 2); + headerBytes[17] |= tableBits - 1; + memcpy(writeHead, headerBytes, 18); + writeHead += 18; + + //local color table + memcpy(writeHead, table, tableSize * sizeof(Color3)); + writeHead += tableSize * sizeof(Color3); + *writeHead++ = tableBits; + + //prep block + memset(writeHead, 0, 260); + writeHead[0] = 255; + uint32_t blockBits = 8; //relative to block.head + + //SPEC: "Encoders should output a Clear code as the first code of each image data stream." + msf_lzw_reset(&lzw, tableSize, tableIdx); + msf_put_code(&writeHead, &blockBits, msf_bit_log(lzw.len - 1), tableSize); + + int lastCode = hasSamePal && frame.pixels[0] == previous.pixels[0]? 0 : tlb[frame.pixels[0]]; + MsfTimeLoop("compress") for (int i = 1; i < width * height; ++i) { + //PERF: branching vs. branchless version of this line is observed to have no discernable impact on speed + int color = hasSamePal && frame.pixels[i] == previous.pixels[i]? 0 : tlb[frame.pixels[i]]; + //PERF: branchless version must use && otherwise it will segfault on frame 1, but it's well-predicted so OK + // int color = (!(hasSamePal && frame.pixels[i] == previous.pixels[i])) * tlb[frame.pixels[i]]; + int code = (&lzw.data[lastCode * lzw.stride])[color]; + if (code < 0) { + //write to code stream + int codeBits = msf_bit_log(lzw.len - 1); + msf_put_code(&writeHead, &blockBits, codeBits, lastCode); + + if (lzw.len > 4095) { + //reset buffer code table + msf_put_code(&writeHead, &blockBits, codeBits, tableSize); + msf_lzw_reset(&lzw, tableSize, tableIdx); + } else { + (&lzw.data[lastCode * lzw.stride])[color] = lzw.len; + ++lzw.len; + } + + lastCode = color; + } else { + lastCode = code; + } + } + + MSF_GIF_FREE(allocContext, lzw.data, lzwAllocSize); + MSF_GIF_FREE(allocContext, previous.pixels, width * height * sizeof(uint32_t)); + + //write code for leftover index buffer contents, then the end code + msf_put_code(&writeHead, &blockBits, msf_imin(12, msf_bit_log(lzw.len - 1)), lastCode); + msf_put_code(&writeHead, &blockBits, msf_imin(12, msf_bit_log(lzw.len)), tableSize + 1); + + //flush remaining data + if (blockBits > 8) { + int bytes = (blockBits + 7) / 8; //round up + writeHead[0] = bytes - 1; + writeHead += bytes; + } + *writeHead++ = 0; //terminating block + + //filling in buffer header and shrink buffer to fit data + MsfBufferHeader * header = (MsfBufferHeader *) allocation; + header->next = NULL; + header->size = writeHead - writeBase; + uint8_t * moved = (uint8_t *) MSF_GIF_REALLOC(allocContext, allocation, maxBufSize, writeHead - allocation); + if (!moved) { MSF_GIF_FREE(allocContext, allocation, maxBufSize); return NULL; } + return moved; +} + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/// Incremental API /// +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +int msf_gif_begin(MsfGifState * handle, int width, int height) { MsfTimeFunc + MsfCookedFrame empty = {0}; //god I hate MSVC... + handle->previousFrame = empty; + handle->width = width; + handle->height = height; + + //setup header buffer header (lol) + handle->listHead = (uint8_t *) MSF_GIF_MALLOC(handle->customAllocatorContext, sizeof(MsfBufferHeader) + 32); + if (!handle->listHead) { return 0; } + handle->listTail = handle->listHead; + MsfBufferHeader * header = (MsfBufferHeader *) handle->listHead; + header->next = NULL; + header->size = 32; + + //NOTE: because __attribute__((__packed__)) is annoyingly compiler-specific, we do this unreadable weirdness + char headerBytes[33] = "GIF89a\0\0\0\0\x10\0\0" "\x21\xFF\x0BNETSCAPE2.0\x03\x01\0\0\0"; + memcpy(&headerBytes[6], &width, 2); + memcpy(&headerBytes[8], &height, 2); + memcpy(handle->listHead + sizeof(MsfBufferHeader), headerBytes, 32); + return 1; +} + +int msf_gif_frame(MsfGifState * handle, uint8_t * pixelData, int centiSecondsPerFame, int maxBitDepth, int pitchInBytes) +{ MsfTimeFunc + if (!handle->listHead) { return 0; } + + maxBitDepth = msf_imax(1, msf_imin(16, maxBitDepth)); + if (pitchInBytes == 0) pitchInBytes = handle->width * 4; + if (pitchInBytes < 0) pixelData -= pitchInBytes * (handle->height - 1); + + uint8_t used[1 << 16]; //only 64k, so stack allocating is fine + MsfCookedFrame frame = + msf_cook_frame(handle->customAllocatorContext, pixelData, used, handle->width, handle->height, pitchInBytes, + msf_imin(maxBitDepth, handle->previousFrame.depth + 160 / msf_imax(1, handle->previousFrame.count))); + //TODO: de-duplicate cleanup code + if (!frame.pixels) { + MSF_GIF_FREE(handle->customAllocatorContext, + handle->previousFrame.pixels, handle->width * handle->height * sizeof(uint32_t)); + for (uint8_t * node = handle->listHead; node;) { + MsfBufferHeader * header = (MsfBufferHeader *) node; + node = header->next; + MSF_GIF_FREE(handle->customAllocatorContext, header, sizeof(MsfBufferHeader) + header->size); + } + handle->listHead = handle->listTail = NULL; + return 0; + } + + uint8_t * buffer = msf_compress_frame(handle->customAllocatorContext, + handle->width, handle->height, centiSecondsPerFame, frame, handle->previousFrame, used); + ((MsfBufferHeader *) handle->listTail)->next = buffer; + handle->listTail = buffer; + if (!buffer) { + MSF_GIF_FREE(handle->customAllocatorContext, frame.pixels, handle->width * handle->height * sizeof(uint32_t)); + MSF_GIF_FREE(handle->customAllocatorContext, + handle->previousFrame.pixels, handle->width * handle->height * sizeof(uint32_t)); + for (uint8_t * node = handle->listHead; node;) { + MsfBufferHeader * header = (MsfBufferHeader *) node; + node = header->next; + MSF_GIF_FREE(handle->customAllocatorContext, header, sizeof(MsfBufferHeader) + header->size); + } + handle->listHead = handle->listTail = NULL; + return 0; + } + + handle->previousFrame = frame; + return 1; +} + +MsfGifResult msf_gif_end(MsfGifState * handle) { MsfTimeFunc + if (!handle->listHead) { MsfGifResult empty = {0}; return empty; } + + MSF_GIF_FREE(handle->customAllocatorContext, + handle->previousFrame.pixels, handle->width * handle->height * sizeof(uint32_t)); + + //first pass: determine total size + size_t total = 1; //1 byte for trailing marker + for (uint8_t * node = handle->listHead; node;) { + MsfBufferHeader * header = (MsfBufferHeader *) node; + node = header->next; + total += header->size; + } + + //second pass: write data + uint8_t * buffer = (uint8_t *) MSF_GIF_MALLOC(handle->customAllocatorContext, total); + if (buffer) { + uint8_t * writeHead = buffer; + for (uint8_t * node = handle->listHead; node;) { + MsfBufferHeader * header = (MsfBufferHeader *) node; + memcpy(writeHead, node + sizeof(MsfBufferHeader), header->size); + writeHead += header->size; + node = header->next; + } + *writeHead++ = 0x3B; + } + + //third pass: free buffers + for (uint8_t * node = handle->listHead; node;) { + MsfBufferHeader * header = (MsfBufferHeader *) node; + node = header->next; + MSF_GIF_FREE(handle->customAllocatorContext, header, sizeof(MsfBufferHeader) + header->size); + } + + MsfGifResult ret = { buffer, total, total, handle->customAllocatorContext }; + return ret; +} + +void msf_gif_free(MsfGifResult result) { + if (result.data) { MSF_GIF_FREE(result.contextPointer, result.data, result.allocSize); } +} + +#endif //MSF_GIF_ALREADY_IMPLEMENTED_IN_THIS_TRANSLATION_UNIT +#endif //MSF_GIF_IMPL + +/* +------------------------------------------------------------------------------ +This software is available under 2 licenses -- choose whichever you prefer. +------------------------------------------------------------------------------ +ALTERNATIVE A - MIT License +Copyright (c) 2020 Miles Fogle +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions: +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. +------------------------------------------------------------------------------ +ALTERNATIVE B - Public Domain (www.unlicense.org) +This is free and unencumbered software released into the public domain. +Anyone is free to copy, modify, publish, use, compile, sell, or distribute this +software, either in source code form or as a compiled binary, for any purpose, +commercial or non-commercial, and by any means. +In jurisdictions that recognize copyright laws, the author or authors of this +software dedicate any and all copyright interest in the software to the public +domain. We make this dedication for the benefit of the public at large and to +the detriment of our heirs and successors. We intend this dedication to be an +overt act of relinquishment in perpetuity of all present and future rights to +this software under copyright law. +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN +ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION +WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +------------------------------------------------------------------------------ +*/ diff --git a/libs/raylib/src/external/sdefl.h b/libs/raylib/src/external/sdefl.h new file mode 100644 index 0000000..218e754 --- /dev/null +++ b/libs/raylib/src/external/sdefl.h @@ -0,0 +1,697 @@ +/* +# Small Deflate +`sdefl` is a small bare bone lossless compression library in ANSI C (ISO C90) +which implements the Deflate (RFC 1951) compressed data format specification standard. +It is mainly tuned to get as much speed and compression ratio from as little code +as needed to keep the implementation as concise as possible. + +## Features +- Portable single header and source file duo written in ANSI C (ISO C90) +- Dual license with either MIT or public domain +- Small implementation + - Deflate: 525 LoC + - Inflate: 320 LoC +- Webassembly: + - Deflate ~3.7 KB (~2.2KB compressed) + - Inflate ~3.6 KB (~2.2KB compressed) + +## Usage: +This file behaves differently depending on what symbols you define +before including it. + +Header-File mode: +If you do not define `SDEFL_IMPLEMENTATION` before including this file, it +will operate in header only mode. In this mode it declares all used structs +and the API of the library without including the implementation of the library. + +Implementation mode: +If you define `SDEFL_IMPLEMENTATION` before including this file, it will +compile the implementation . Make sure that you only include +this file implementation in *one* C or C++ file to prevent collisions. + +### Benchmark + +| Compressor name | Compression| Decompress.| Compr. size | Ratio | +| ------------------------| -----------| -----------| ----------- | ----- | +| sdefl 1.0 -0 | 127 MB/s | 233 MB/s | 40004116 | 39.88 | +| sdefl 1.0 -1 | 111 MB/s | 259 MB/s | 38940674 | 38.82 | +| sdefl 1.0 -5 | 45 MB/s | 275 MB/s | 36577183 | 36.46 | +| sdefl 1.0 -7 | 38 MB/s | 276 MB/s | 36523781 | 36.41 | +| zlib 1.2.11 -1 | 72 MB/s | 307 MB/s | 42298774 | 42.30 | +| zlib 1.2.11 -6 | 24 MB/s | 313 MB/s | 36548921 | 36.55 | +| zlib 1.2.11 -9 | 20 MB/s | 314 MB/s | 36475792 | 36.48 | +| miniz 1.0 -1 | 122 MB/s | 208 MB/s | 48510028 | 48.51 | +| miniz 1.0 -6 | 27 MB/s | 260 MB/s | 36513697 | 36.51 | +| miniz 1.0 -9 | 23 MB/s | 261 MB/s | 36460101 | 36.46 | +| libdeflate 1.3 -1 | 147 MB/s | 667 MB/s | 39597378 | 39.60 | +| libdeflate 1.3 -6 | 69 MB/s | 689 MB/s | 36648318 | 36.65 | +| libdeflate 1.3 -9 | 13 MB/s | 672 MB/s | 35197141 | 35.20 | +| libdeflate 1.3 -12 | 8.13 MB/s | 670 MB/s | 35100568 | 35.10 | + +### Compression +Results on the [Silesia compression corpus](http://sun.aei.polsl.pl/~sdeor/index.php?page=silesia): + +| File | Original | `sdefl 0` | `sdefl 5` | `sdefl 7` | +| :------ | ---------: | -----------------: | ---------: | ----------: | +| dickens | 10.192.446 | 4,260,187| 3,845,261| 3,833,657 | +| mozilla | 51.220.480 | 20,774,706 | 19,607,009 | 19,565,867 | +| mr | 9.970.564 | 3,860,531 | 3,673,460 | 3,665,627 | +| nci | 33.553.445 | 4,030,283 | 3,094,526 | 3,006,075 | +| ooffice | 6.152.192 | 3,320,063 | 3,186,373 | 3,183,815 | +| osdb | 10.085.684 | 3,919,646 | 3,649,510 | 3,649,477 | +| reymont | 6.627.202 | 2,263,378 | 1,857,588 | 1,827,237 | +| samba | 21.606.400 | 6,121,797 | 5,462,670 | 5,450,762 | +| sao | 7.251.944 | 5,612,421 | 5,485,380 | 5,481,765 | +| webster | 41.458.703 | 13,972,648 | 12,059,432 | 11,991,421 | +| xml | 5.345.280 | 886,620| 674,009 | 662,141 | +| x-ray | 8.474.240 | 6,304,655 | 6,244,779 | 6,244,779 | + +## License +``` +------------------------------------------------------------------------------ +This software is available under 2 licenses -- choose whichever you prefer. +------------------------------------------------------------------------------ +ALTERNATIVE A - MIT License +Copyright (c) 2020 Micha Mettke +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions: +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. +------------------------------------------------------------------------------ +ALTERNATIVE B - Public Domain (www.unlicense.org) +This is free and unencumbered software released into the public domain. +Anyone is free to copy, modify, publish, use, compile, sell, or distribute this +software, either in source code form or as a compiled binary, for any purpose, +commercial or non-commercial, and by any means. +In jurisdictions that recognize copyright laws, the author or authors of this +software dedicate any and all copyright interest in the software to the public +domain. We make this dedication for the benefit of the public at large and to +the detriment of our heirs and successors. We intend this dedication to be an +overt act of relinquishment in perpetuity of all present and future rights to +this software under copyright law. +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN +ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION +WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +------------------------------------------------------------------------------ +``` +*/ +#ifndef SDEFL_H_INCLUDED +#define SDEFL_H_INCLUDED + +#ifdef __cplusplus +extern "C" { +#endif + +#define SDEFL_MAX_OFF (1 << 15) +#define SDEFL_WIN_SIZ SDEFL_MAX_OFF +#define SDEFL_WIN_MSK (SDEFL_WIN_SIZ-1) + +#define SDEFL_HASH_BITS 15 +#define SDEFL_HASH_SIZ (1 << SDEFL_HASH_BITS) +#define SDEFL_HASH_MSK (SDEFL_HASH_SIZ-1) + +#define SDEFL_MIN_MATCH 4 +#define SDEFL_BLK_MAX (256*1024) +#define SDEFL_SEQ_SIZ ((SDEFL_BLK_MAX + SDEFL_MIN_MATCH)/SDEFL_MIN_MATCH) + +#define SDEFL_SYM_MAX (288) +#define SDEFL_OFF_MAX (32) +#define SDEFL_PRE_MAX (19) + +#define SDEFL_LVL_MIN 0 +#define SDEFL_LVL_DEF 5 +#define SDEFL_LVL_MAX 8 + +struct sdefl_freq { + unsigned lit[SDEFL_SYM_MAX]; + unsigned off[SDEFL_OFF_MAX]; +}; +struct sdefl_code_words { + unsigned lit[SDEFL_SYM_MAX]; + unsigned off[SDEFL_OFF_MAX]; +}; +struct sdefl_lens { + unsigned char lit[SDEFL_SYM_MAX]; + unsigned char off[SDEFL_OFF_MAX]; +}; +struct sdefl_codes { + struct sdefl_code_words word; + struct sdefl_lens len; +}; +struct sdefl_seqt { + int off, len; +}; +struct sdefl { + int bits, bitcnt; + int tbl[SDEFL_HASH_SIZ]; + int prv[SDEFL_WIN_SIZ]; + + int seq_cnt; + struct sdefl_seqt seq[SDEFL_SEQ_SIZ]; + struct sdefl_freq freq; + struct sdefl_codes cod; +}; +extern int sdefl_bound(int in_len); +extern int sdeflate(struct sdefl *s, void *o, const void *i, int n, int lvl); +extern int zsdeflate(struct sdefl *s, void *o, const void *i, int n, int lvl); + +#ifdef __cplusplus +} +#endif + +#endif /* SDEFL_H_INCLUDED */ + +#ifdef SDEFL_IMPLEMENTATION + +#include <assert.h> /* assert */ +#include <string.h> /* memcpy */ +#include <limits.h> /* CHAR_BIT */ + +#define SDEFL_NIL (-1) +#define SDEFL_MAX_MATCH 258 +#define SDEFL_MAX_CODE_LEN (15) +#define SDEFL_SYM_BITS (10u) +#define SDEFL_SYM_MSK ((1u << SDEFL_SYM_BITS)-1u) +#define SDEFL_LIT_LEN_CODES (14) +#define SDEFL_OFF_CODES (15) +#define SDEFL_PRE_CODES (7) +#define SDEFL_CNT_NUM(n) ((((n)+3u/4u)+3u)&~3u) +#define SDEFL_EOB (256) + +#define sdefl_npow2(n) (1 << (sdefl_ilog2((n)-1) + 1)) + +static int +sdefl_ilog2(int n) { + if (!n) return 0; +#ifdef _MSC_VER + unsigned long msbp = 0; + _BitScanReverse(&msbp, (unsigned long)n); + return (int)msbp; +#elif defined(__GNUC__) || defined(__clang__) + return (int)sizeof(unsigned long) * CHAR_BIT - 1 - __builtin_clzl((unsigned long)n); +#else + #define lt(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n + static const char tbl[256] = { + 0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,lt(4), lt(5), lt(5), lt(6), lt(6), lt(6), lt(6), + lt(7), lt(7), lt(7), lt(7), lt(7), lt(7), lt(7), lt(7)}; + int tt, t; + if ((tt = (n >> 16))) { + return (t = (tt >> 8)) ? 24 + tbl[t] : 16 + tbl[tt]; + } else { + return (t = (n >> 8)) ? 8 + tbl[t] : tbl[n]; + } + #undef lt +#endif +} +static unsigned +sdefl_uload32(const void *p) { + /* hopefully will be optimized to an unaligned read */ + unsigned n = 0; + memcpy(&n, p, sizeof(n)); + return n; +} +static unsigned +sdefl_hash32(const void *p) { + unsigned n = sdefl_uload32(p); + return (n * 0x9E377989) >> (32 - SDEFL_HASH_BITS); +} +static void +sdefl_put(unsigned char **dst, struct sdefl *s, int code, int bitcnt) { + s->bits |= (code << s->bitcnt); + s->bitcnt += bitcnt; + while (s->bitcnt >= 8) { + unsigned char *tar = *dst; + *tar = (unsigned char)(s->bits & 0xFF); + s->bits >>= 8; + s->bitcnt -= 8; + *dst = *dst + 1; + } +} +static void +sdefl_heap_sub(unsigned A[], unsigned len, unsigned sub) { + unsigned c, p = sub; + unsigned v = A[sub]; + while ((c = p << 1) <= len) { + if (c < len && A[c + 1] > A[c]) c++; + if (v >= A[c]) break; + A[p] = A[c], p = c; + } + A[p] = v; +} +static void +sdefl_heap_array(unsigned *A, unsigned len) { + unsigned sub; + for (sub = len >> 1; sub >= 1; sub--) + sdefl_heap_sub(A, len, sub); +} +static void +sdefl_heap_sort(unsigned *A, unsigned n) { + A--; + sdefl_heap_array(A, n); + while (n >= 2) { + unsigned tmp = A[n]; + A[n--] = A[1]; + A[1] = tmp; + sdefl_heap_sub(A, n, 1); + } +} +static unsigned +sdefl_sort_sym(unsigned sym_cnt, unsigned *freqs, + unsigned char *lens, unsigned *sym_out) { + unsigned cnts[SDEFL_CNT_NUM(SDEFL_SYM_MAX)] = {0}; + unsigned cnt_num = SDEFL_CNT_NUM(sym_cnt); + unsigned used_sym = 0; + unsigned sym, i; + for (sym = 0; sym < sym_cnt; sym++) + cnts[freqs[sym] < cnt_num-1 ? freqs[sym]: cnt_num-1]++; + for (i = 1; i < cnt_num; i++) { + unsigned cnt = cnts[i]; + cnts[i] = used_sym; + used_sym += cnt; + } + for (sym = 0; sym < sym_cnt; sym++) { + unsigned freq = freqs[sym]; + if (freq) { + unsigned idx = freq < cnt_num-1 ? freq : cnt_num-1; + sym_out[cnts[idx]++] = sym | (freq << SDEFL_SYM_BITS); + } else lens[sym] = 0; + } + sdefl_heap_sort(sym_out + cnts[cnt_num-2], cnts[cnt_num-1] - cnts[cnt_num-2]); + return used_sym; +} +static void +sdefl_build_tree(unsigned *A, unsigned sym_cnt) { + unsigned i = 0, b = 0, e = 0; + do { + unsigned m, n, freq_shift; + if (i != sym_cnt && (b == e || (A[i] >> SDEFL_SYM_BITS) <= (A[b] >> SDEFL_SYM_BITS))) + m = i++; + else m = b++; + if (i != sym_cnt && (b == e || (A[i] >> SDEFL_SYM_BITS) <= (A[b] >> SDEFL_SYM_BITS))) + n = i++; + else n = b++; + + freq_shift = (A[m] & ~SDEFL_SYM_MSK) + (A[n] & ~SDEFL_SYM_MSK); + A[m] = (A[m] & SDEFL_SYM_MSK) | (e << SDEFL_SYM_BITS); + A[n] = (A[n] & SDEFL_SYM_MSK) | (e << SDEFL_SYM_BITS); + A[e] = (A[e] & SDEFL_SYM_MSK) | freq_shift; + } while (sym_cnt - ++e > 1); +} +static void +sdefl_gen_len_cnt(unsigned *A, unsigned root, unsigned *len_cnt, + unsigned max_code_len) { + int n; + unsigned i; + for (i = 0; i <= max_code_len; i++) + len_cnt[i] = 0; + len_cnt[1] = 2; + + A[root] &= SDEFL_SYM_MSK; + for (n = (int)root - 1; n >= 0; n--) { + unsigned p = A[n] >> SDEFL_SYM_BITS; + unsigned pdepth = A[p] >> SDEFL_SYM_BITS; + unsigned depth = pdepth + 1; + unsigned len = depth; + + A[n] = (A[n] & SDEFL_SYM_MSK) | (depth << SDEFL_SYM_BITS); + if (len >= max_code_len) { + len = max_code_len; + do len--; while (!len_cnt[len]); + } + len_cnt[len]--; + len_cnt[len+1] += 2; + } +} +static void +sdefl_gen_codes(unsigned *A, unsigned char *lens, const unsigned *len_cnt, + unsigned max_code_word_len, unsigned sym_cnt) { + unsigned i, sym, len, nxt[SDEFL_MAX_CODE_LEN + 1]; + for (i = 0, len = max_code_word_len; len >= 1; len--) { + unsigned cnt = len_cnt[len]; + while (cnt--) lens[A[i++] & SDEFL_SYM_MSK] = (unsigned char)len; + } + nxt[0] = nxt[1] = 0; + for (len = 2; len <= max_code_word_len; len++) + nxt[len] = (nxt[len-1] + len_cnt[len-1]) << 1; + for (sym = 0; sym < sym_cnt; sym++) + A[sym] = nxt[lens[sym]]++; +} +static unsigned +sdefl_rev(unsigned c, unsigned char n) { + c = ((c & 0x5555) << 1) | ((c & 0xAAAA) >> 1); + c = ((c & 0x3333) << 2) | ((c & 0xCCCC) >> 2); + c = ((c & 0x0F0F) << 4) | ((c & 0xF0F0) >> 4); + c = ((c & 0x00FF) << 8) | ((c & 0xFF00) >> 8); + return c >> (16-n); +} +static void +sdefl_huff(unsigned char *lens, unsigned *codes, unsigned *freqs, + unsigned num_syms, unsigned max_code_len) { + unsigned c, *A = codes; + unsigned len_cnt[SDEFL_MAX_CODE_LEN + 1]; + unsigned used_syms = sdefl_sort_sym(num_syms, freqs, lens, A); + if (!used_syms) return; + if (used_syms == 1) { + unsigned s = A[0] & SDEFL_SYM_MSK; + unsigned i = s ? s : 1; + codes[0] = 0, lens[0] = 1; + codes[i] = 1, lens[i] = 1; + return; + } + sdefl_build_tree(A, used_syms); + sdefl_gen_len_cnt(A, used_syms-2, len_cnt, max_code_len); + sdefl_gen_codes(A, lens, len_cnt, max_code_len, num_syms); + for (c = 0; c < num_syms; c++) { + codes[c] = sdefl_rev(codes[c], lens[c]); + } +} +struct sdefl_symcnt { + int items; + int lit; + int off; +}; +static void +sdefl_precode(struct sdefl_symcnt *cnt, unsigned *freqs, unsigned *items, + const unsigned char *litlen, const unsigned char *offlen) { + unsigned *at = items; + unsigned run_start = 0; + + unsigned total = 0; + unsigned char lens[SDEFL_SYM_MAX + SDEFL_OFF_MAX]; + for (cnt->lit = SDEFL_SYM_MAX; cnt->lit > 257; cnt->lit--) + if (litlen[cnt->lit - 1]) break; + for (cnt->off = SDEFL_OFF_MAX; cnt->off > 1; cnt->off--) + if (offlen[cnt->off - 1]) break; + + total = (unsigned)(cnt->lit + cnt->off); + memcpy(lens, litlen, sizeof(unsigned char) * cnt->lit); + memcpy(lens + cnt->lit, offlen, sizeof(unsigned char) * cnt->off); + do { + unsigned len = lens[run_start]; + unsigned run_end = run_start; + do run_end++; while (run_end != total && len == lens[run_end]); + if (!len) { + while ((run_end - run_start) >= 11) { + unsigned n = (run_end - run_start) - 11; + unsigned xbits = n < 0x7f ? n : 0x7f; + freqs[18]++; + *at++ = 18u | (xbits << 5u); + run_start += 11 + xbits; + } + if ((run_end - run_start) >= 3) { + unsigned n = (run_end - run_start) - 3; + unsigned xbits = n < 0x7 ? n : 0x7; + freqs[17]++; + *at++ = 17u | (xbits << 5u); + run_start += 3 + xbits; + } + } else if ((run_end - run_start) >= 4) { + freqs[len]++; + *at++ = len; + run_start++; + do { + unsigned xbits = (run_end - run_start) - 3; + xbits = xbits < 0x03 ? xbits : 0x03; + *at++ = 16 | (xbits << 5); + run_start += 3 + xbits; + freqs[16]++; + } while ((run_end - run_start) >= 3); + } + while (run_start != run_end) { + freqs[len]++; + *at++ = len; + run_start++; + } + } while (run_start != total); + cnt->items = (int)(at - items); +} +struct sdefl_match_codes { + int ls, lc; + int dc, dx; +}; +static void +sdefl_match_codes(struct sdefl_match_codes *cod, int dist, int len) { + static const short dxmax[] = {0,6,12,24,48,96,192,384,768,1536,3072,6144,12288,24576}; + static const unsigned char lslot[258+1] = { + 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, + 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, + 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, + 18, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, + 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, + 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, + 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, + 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, + 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, + 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, + 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, + 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, + 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, + 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, + 27, 27, 28 + }; + cod->ls = lslot[len]; + cod->lc = 257 + cod->ls; + cod->dx = sdefl_ilog2(sdefl_npow2(dist) >> 2); + cod->dc = cod->dx ? ((cod->dx + 1) << 1) + (dist > dxmax[cod->dx]) : dist-1; +} +static void +sdefl_match(unsigned char **dst, struct sdefl *s, int dist, int len) { + static const char lxn[] = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0}; + static const short lmin[] = {3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43, + 51,59,67,83,99,115,131,163,195,227,258}; + static const short dmin[] = {1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257, + 385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577}; + + struct sdefl_match_codes cod; + sdefl_match_codes(&cod, dist, len); + sdefl_put(dst, s, (int)s->cod.word.lit[cod.lc], s->cod.len.lit[cod.lc]); + sdefl_put(dst, s, len - lmin[cod.ls], lxn[cod.ls]); + sdefl_put(dst, s, (int)s->cod.word.off[cod.dc], s->cod.len.off[cod.dc]); + sdefl_put(dst, s, dist - dmin[cod.dc], cod.dx); +} +static void +sdefl_flush(unsigned char **dst, struct sdefl *s, int is_last, + const unsigned char *in) { + int j, i = 0, item_cnt = 0; + struct sdefl_symcnt symcnt = {0}; + unsigned codes[SDEFL_PRE_MAX]; + unsigned char lens[SDEFL_PRE_MAX]; + unsigned freqs[SDEFL_PRE_MAX] = {0}; + unsigned items[SDEFL_SYM_MAX + SDEFL_OFF_MAX]; + static const unsigned char perm[SDEFL_PRE_MAX] = {16,17,18,0,8,7,9,6,10,5,11, + 4,12,3,13,2,14,1,15}; + + /* huffman codes */ + s->freq.lit[SDEFL_EOB]++; + sdefl_huff(s->cod.len.lit, s->cod.word.lit, s->freq.lit, SDEFL_SYM_MAX, SDEFL_LIT_LEN_CODES); + sdefl_huff(s->cod.len.off, s->cod.word.off, s->freq.off, SDEFL_OFF_MAX, SDEFL_OFF_CODES); + sdefl_precode(&symcnt, freqs, items, s->cod.len.lit, s->cod.len.off); + sdefl_huff(lens, codes, freqs, SDEFL_PRE_MAX, SDEFL_PRE_CODES); + for (item_cnt = SDEFL_PRE_MAX; item_cnt > 4; item_cnt--) { + if (lens[perm[item_cnt - 1]]) break; + } + /* block header */ + sdefl_put(dst, s, is_last ? 0x01 : 0x00, 1); /* block */ + sdefl_put(dst, s, 0x02, 2); /* dynamic huffman */ + sdefl_put(dst, s, symcnt.lit - 257, 5); + sdefl_put(dst, s, symcnt.off - 1, 5); + sdefl_put(dst, s, item_cnt - 4, 4); + for (i = 0; i < item_cnt; ++i) + sdefl_put(dst, s, lens[perm[i]], 3); + for (i = 0; i < symcnt.items; ++i) { + unsigned sym = items[i] & 0x1F; + sdefl_put(dst, s, (int)codes[sym], lens[sym]); + if (sym < 16) continue; + if (sym == 16) sdefl_put(dst, s, items[i] >> 5, 2); + else if(sym == 17) sdefl_put(dst, s, items[i] >> 5, 3); + else sdefl_put(dst, s, items[i] >> 5, 7); + } + /* block sequences */ + for (i = 0; i < s->seq_cnt; ++i) { + if (s->seq[i].off >= 0) + for (j = 0; j < s->seq[i].len; ++j) { + int c = in[s->seq[i].off + j]; + sdefl_put(dst, s, (int)s->cod.word.lit[c], s->cod.len.lit[c]); + } + else sdefl_match(dst, s, -s->seq[i].off, s->seq[i].len); + } + sdefl_put(dst, s, (int)(s)->cod.word.lit[SDEFL_EOB], (s)->cod.len.lit[SDEFL_EOB]); + memset(&s->freq, 0, sizeof(s->freq)); + s->seq_cnt = 0; +} +static void +sdefl_seq(struct sdefl *s, int off, int len) { + assert(s->seq_cnt + 2 < SDEFL_SEQ_SIZ); + s->seq[s->seq_cnt].off = off; + s->seq[s->seq_cnt].len = len; + s->seq_cnt++; +} +static void +sdefl_reg_match(struct sdefl *s, int off, int len) { + struct sdefl_match_codes cod; + sdefl_match_codes(&cod, off, len); + s->freq.lit[cod.lc]++; + s->freq.off[cod.dc]++; +} +struct sdefl_match { + int off; + int len; +}; +static void +sdefl_fnd(struct sdefl_match *m, const struct sdefl *s, + int chain_len, int max_match, const unsigned char *in, int p) { + int i = s->tbl[sdefl_hash32(&in[p])]; + int limit = ((p-SDEFL_WIN_SIZ)<SDEFL_NIL)?SDEFL_NIL:(p-SDEFL_WIN_SIZ); + while (i > limit) { + if (in[i+m->len] == in[p+m->len] && + (sdefl_uload32(&in[i]) == sdefl_uload32(&in[p]))){ + int n = SDEFL_MIN_MATCH; + while (n < max_match && in[i+n] == in[p+n]) n++; + if (n > m->len) { + m->len = n, m->off = p - i; + if (n == max_match) break; + } + } + if (!(--chain_len)) break; + i = s->prv[i&SDEFL_WIN_MSK]; + } +} +static int +sdefl_compr(struct sdefl *s, unsigned char *out, const unsigned char *in, + int in_len, int lvl) { + unsigned char *q = out; + static const unsigned char pref[] = {8,10,14,24,30,48,65,96,130}; + int max_chain = (lvl < 8) ? (1 << (lvl + 1)): (1 << 13); + int n, i = 0, litlen = 0; + for (n = 0; n < SDEFL_HASH_SIZ; ++n) { + s->tbl[n] = SDEFL_NIL; + } + do {int blk_end = i + SDEFL_BLK_MAX < in_len ? i + SDEFL_BLK_MAX : in_len; + while (i < blk_end) { + struct sdefl_match m = {0}; + int max_match = ((in_len-i)>SDEFL_MAX_MATCH) ? SDEFL_MAX_MATCH:(in_len-i); + int nice_match = pref[lvl] < max_match ? pref[lvl] : max_match; + int run = 1, inc = 1, run_inc; + if (max_match > SDEFL_MIN_MATCH) { + sdefl_fnd(&m, s, max_chain, max_match, in, i); + } + if (lvl >= 5 && m.len >= SDEFL_MIN_MATCH && m.len < nice_match){ + struct sdefl_match m2 = {0}; + sdefl_fnd(&m2, s, max_chain, m.len+1, in, i+1); + m.len = (m2.len > m.len) ? 0 : m.len; + } + if (m.len >= SDEFL_MIN_MATCH) { + if (litlen) { + sdefl_seq(s, i - litlen, litlen); + litlen = 0; + } + sdefl_seq(s, -m.off, m.len); + sdefl_reg_match(s, m.off, m.len); + if (lvl < 2 && m.len >= nice_match) { + inc = m.len; + } else { + run = m.len; + } + } else { + s->freq.lit[in[i]]++; + litlen++; + } + run_inc = run * inc; + if (in_len - (i + run_inc) > SDEFL_MIN_MATCH) { + while (run-- > 0) { + unsigned h = sdefl_hash32(&in[i]); + s->prv[i&SDEFL_WIN_MSK] = s->tbl[h]; + s->tbl[h] = i, i += inc; + } + } else { + i += run_inc; + } + } + if (litlen) { + sdefl_seq(s, i - litlen, litlen); + litlen = 0; + } + sdefl_flush(&q, s, blk_end == in_len, in); + } while (i < in_len); + + if (s->bitcnt) + sdefl_put(&q, s, 0x00, 8 - s->bitcnt); + return (int)(q - out); +} +extern int +sdeflate(struct sdefl *s, void *out, const void *in, int n, int lvl) { + s->bits = s->bitcnt = 0; + return sdefl_compr(s, (unsigned char*)out, (const unsigned char*)in, n, lvl); +} +static unsigned +sdefl_adler32(unsigned adler32, const unsigned char *in, int in_len) { + #define SDEFL_ADLER_INIT (1) + const unsigned ADLER_MOD = 65521; + unsigned s1 = adler32 & 0xffff; + unsigned s2 = adler32 >> 16; + unsigned blk_len, i; + + blk_len = in_len % 5552; + while (in_len) { + for (i = 0; i + 7 < blk_len; i += 8) { + s1 += in[0]; s2 += s1; + s1 += in[1]; s2 += s1; + s1 += in[2]; s2 += s1; + s1 += in[3]; s2 += s1; + s1 += in[4]; s2 += s1; + s1 += in[5]; s2 += s1; + s1 += in[6]; s2 += s1; + s1 += in[7]; s2 += s1; + in += 8; + } + for (; i < blk_len; ++i) { + s1 += *in++, s2 += s1; + } + s1 %= ADLER_MOD; + s2 %= ADLER_MOD; + in_len -= blk_len; + blk_len = 5552; + } + return (unsigned)(s2 << 16) + (unsigned)s1; +} +extern int +zsdeflate(struct sdefl *s, void *out, const void *in, int n, int lvl) { + int p = 0; + unsigned a = 0; + unsigned char *q = (unsigned char*)out; + + s->bits = s->bitcnt = 0; + sdefl_put(&q, s, 0x78, 8); /* deflate, 32k window */ + sdefl_put(&q, s, 0x01, 8); /* fast compression */ + q += sdefl_compr(s, q, (const unsigned char*)in, n, lvl); + + /* append adler checksum */ + a = sdefl_adler32(SDEFL_ADLER_INIT, (const unsigned char*)in, n); + for (p = 0; p < 4; ++p) { + sdefl_put(&q, s, (a >> 24) & 0xFF, 8); + a <<= 8; + } + return (int)(q - (unsigned char*)out); +} +extern int +sdefl_bound(int len) { + int a = 128 + (len * 110) / 100; + int b = 128 + len + ((len / (31 * 1024)) + 1) * 5; + return (a > b) ? a : b; +} +#endif /* SDEFL_IMPLEMENTATION */ + diff --git a/libs/raylib/src/external/sinfl.h b/libs/raylib/src/external/sinfl.h new file mode 100644 index 0000000..37c1aae --- /dev/null +++ b/libs/raylib/src/external/sinfl.h @@ -0,0 +1,464 @@ +/* +# Small Deflate +`sdefl` is a small bare bone lossless compression library in ANSI C (ISO C90) +which implements the Deflate (RFC 1951) compressed data format specification standard. +It is mainly tuned to get as much speed and compression ratio from as little code +as needed to keep the implementation as concise as possible. + +## Features +- Portable single header and source file duo written in ANSI C (ISO C90) +- Dual license with either MIT or public domain +- Small implementation + - Deflate: 525 LoC + - Inflate: 320 LoC +- Webassembly: + - Deflate ~3.7 KB (~2.2KB compressed) + - Inflate ~3.6 KB (~2.2KB compressed) + +## Usage: +This file behaves differently depending on what symbols you define +before including it. + +Header-File mode: +If you do not define `SINFL_IMPLEMENTATION` before including this file, it +will operate in header only mode. In this mode it declares all used structs +and the API of the library without including the implementation of the library. + +Implementation mode: +If you define `SINFL_IMPLEMENTATION` before including this file, it will +compile the implementation. Make sure that you only include +this file implementation in *one* C or C++ file to prevent collisions. + +### Benchmark + +| Compressor name | Compression| Decompress.| Compr. size | Ratio | +| ------------------------| -----------| -----------| ----------- | ----- | +| sdefl 1.0 -0 | 127 MB/s | 233 MB/s | 40004116 | 39.88 | +| sdefl 1.0 -1 | 111 MB/s | 259 MB/s | 38940674 | 38.82 | +| sdefl 1.0 -5 | 45 MB/s | 275 MB/s | 36577183 | 36.46 | +| sdefl 1.0 -7 | 38 MB/s | 276 MB/s | 36523781 | 36.41 | +| zlib 1.2.11 -1 | 72 MB/s | 307 MB/s | 42298774 | 42.30 | +| zlib 1.2.11 -6 | 24 MB/s | 313 MB/s | 36548921 | 36.55 | +| zlib 1.2.11 -9 | 20 MB/s | 314 MB/s | 36475792 | 36.48 | +| miniz 1.0 -1 | 122 MB/s | 208 MB/s | 48510028 | 48.51 | +| miniz 1.0 -6 | 27 MB/s | 260 MB/s | 36513697 | 36.51 | +| miniz 1.0 -9 | 23 MB/s | 261 MB/s | 36460101 | 36.46 | +| libdeflate 1.3 -1 | 147 MB/s | 667 MB/s | 39597378 | 39.60 | +| libdeflate 1.3 -6 | 69 MB/s | 689 MB/s | 36648318 | 36.65 | +| libdeflate 1.3 -9 | 13 MB/s | 672 MB/s | 35197141 | 35.20 | +| libdeflate 1.3 -12 | 8.13 MB/s | 670 MB/s | 35100568 | 35.10 | + +### Compression +Results on the [Silesia compression corpus](http://sun.aei.polsl.pl/~sdeor/index.php?page=silesia): + +| File | Original | `sdefl 0` | `sdefl 5` | `sdefl 7` | +| :------ | ---------: | -----------------: | ---------: | ----------: | +| dickens | 10.192.446 | 4,260,187| 3,845,261| 3,833,657 | +| mozilla | 51.220.480 | 20,774,706 | 19,607,009 | 19,565,867 | +| mr | 9.970.564 | 3,860,531 | 3,673,460 | 3,665,627 | +| nci | 33.553.445 | 4,030,283 | 3,094,526 | 3,006,075 | +| ooffice | 6.152.192 | 3,320,063 | 3,186,373 | 3,183,815 | +| osdb | 10.085.684 | 3,919,646 | 3,649,510 | 3,649,477 | +| reymont | 6.627.202 | 2,263,378 | 1,857,588 | 1,827,237 | +| samba | 21.606.400 | 6,121,797 | 5,462,670 | 5,450,762 | +| sao | 7.251.944 | 5,612,421 | 5,485,380 | 5,481,765 | +| webster | 41.458.703 | 13,972,648 | 12,059,432 | 11,991,421 | +| xml | 5.345.280 | 886,620| 674,009 | 662,141 | +| x-ray | 8.474.240 | 6,304,655 | 6,244,779 | 6,244,779 | + +## License +``` +------------------------------------------------------------------------------ +This software is available under 2 licenses -- choose whichever you prefer. +------------------------------------------------------------------------------ +ALTERNATIVE A - MIT License +Copyright (c) 2020 Micha Mettke +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions: +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. +------------------------------------------------------------------------------ +ALTERNATIVE B - Public Domain (www.unlicense.org) +This is free and unencumbered software released into the public domain. +Anyone is free to copy, modify, publish, use, compile, sell, or distribute this +software, either in source code form or as a compiled binary, for any purpose, +commercial or non-commercial, and by any means. +In jurisdictions that recognize copyright laws, the author or authors of this +software dedicate any and all copyright interest in the software to the public +domain. We make this dedication for the benefit of the public at large and to +the detriment of our heirs and successors. We intend this dedication to be an +overt act of relinquishment in perpetuity of all present and future rights to +this software under copyright law. +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN +ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION +WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +------------------------------------------------------------------------------ +``` +*/ +#ifndef SINFL_H_INCLUDED +#define SINFL_H_INCLUDED + +#ifdef __cplusplus +extern "C" { +#endif + +#define SINFL_PRE_TBL_SIZE 128 +#define SINFL_LIT_TBL_SIZE 1334 +#define SINFL_OFF_TBL_SIZE 402 + +struct sinfl { + int bits, bitcnt; + unsigned lits[SINFL_LIT_TBL_SIZE]; + unsigned dsts[SINFL_OFF_TBL_SIZE]; +}; +extern int sinflate(void *out, const void *in, int size); +extern int zsinflate(void *out, const void *in, int size); + +#ifdef __cplusplus +} +#endif + +#endif /* SINFL_H_INCLUDED */ + +#ifdef SINFL_IMPLEMENTATION + +#include <string.h> /* memcpy, memset */ + +static int +sinfl_bsr(unsigned n) { +#ifdef _MSC_VER + _BitScanReverse(&n, n); + return n; +#elif defined(__GNUC__) || defined(__clang__) + return 31 - __builtin_clz(n); +#endif +} +static int +sinfl_get(const unsigned char **src, const unsigned char *end, struct sinfl *s, + int n) { + const unsigned char *in = *src; + int v = s->bits & ((1 << n)-1); + s->bits >>= n; + s->bitcnt = s->bitcnt - n; + s->bitcnt = s->bitcnt < 0 ? 0 : s->bitcnt; + while (s->bitcnt < 16 && in < end) { + s->bits |= (*in++) << s->bitcnt; + s->bitcnt += 8; + } + *src = in; + return v; +} +struct sinfl_gen { + int len; + int cnt; + int word; + short* sorted; +}; +static int +sinfl_build_tbl(struct sinfl_gen *gen, unsigned *tbl, int tbl_bits, + const int *cnt) { + int tbl_end = 0; + while (!(gen->cnt = cnt[gen->len])) { + ++gen->len; + } + tbl_end = 1 << gen->len; + while (gen->len <= tbl_bits) { + do {unsigned bit = 0; + tbl[gen->word] = (*gen->sorted++ << 16) | gen->len; + if (gen->word == tbl_end - 1) { + for (; gen->len < tbl_bits; gen->len++) { + memcpy(&tbl[tbl_end], tbl, (size_t)tbl_end * sizeof(tbl[0])); + tbl_end <<= 1; + } + return 1; + } + bit = 1 << sinfl_bsr((unsigned)(gen->word ^ (tbl_end - 1))); + gen->word &= bit - 1; + gen->word |= bit; + } while (--gen->cnt); + do { + if (++gen->len <= tbl_bits) { + memcpy(&tbl[tbl_end], tbl, (size_t)tbl_end * sizeof(tbl[0])); + tbl_end <<= 1; + } + } while (!(gen->cnt = cnt[gen->len])); + } + return 0; +} +static void +sinfl_build_subtbl(struct sinfl_gen *gen, unsigned *tbl, int tbl_bits, + const int *cnt) { + int sub_bits = 0; + int sub_start = 0; + int sub_prefix = -1; + int tbl_end = 1 << tbl_bits; + while (1) { + unsigned entry; + int bit, stride, i; + /* start new subtable */ + if ((gen->word & ((1 << tbl_bits)-1)) != sub_prefix) { + int used = 0; + sub_prefix = gen->word & ((1 << tbl_bits)-1); + sub_start = tbl_end; + sub_bits = gen->len - tbl_bits; + used = gen->cnt; + while (used < (1 << sub_bits)) { + sub_bits++; + used = (used << 1) + cnt[tbl_bits + sub_bits]; + } + tbl_end = sub_start + (1 << sub_bits); + tbl[sub_prefix] = (sub_start << 16) | 0x10 | (sub_bits & 0xf); + } + /* fill subtable */ + entry = (*gen->sorted << 16) | ((gen->len - tbl_bits) & 0xf); + gen->sorted++; + i = sub_start + (gen->word >> tbl_bits); + stride = 1 << (gen->len - tbl_bits); + do { + tbl[i] = entry; + i += stride; + } while (i < tbl_end); + if (gen->word == (1 << gen->len)-1) { + return; + } + bit = 1 << sinfl_bsr(gen->word ^ ((1 << gen->len) - 1)); + gen->word &= bit - 1; + gen->word |= bit; + gen->cnt--; + while (!gen->cnt) { + gen->cnt = cnt[++gen->len]; + } + } +} +static void +sinfl_build(unsigned *tbl, unsigned char *lens, int tbl_bits, int maxlen, + int symcnt) { + int i, used = 0; + short sort[288]; + int cnt[16] = {0}, off[16]= {0}; + struct sinfl_gen gen = {0}; + gen.sorted = sort; + gen.len = 1; + + for (i = 0; i < symcnt; ++i) + cnt[lens[i]]++; + off[1] = cnt[0]; + for (i = 1; i < maxlen; ++i) { + off[i + 1] = off[i] + cnt[i]; + used = (used << 1) + cnt[i]; + } + used = (used << 1) + cnt[i]; + for (i = 0; i < symcnt; ++i) + gen.sorted[off[lens[i]]++] = (short)i; + gen.sorted += off[0]; + + if (used < (1 << maxlen)){ + for (i = 0; i < 1 << tbl_bits; ++i) + tbl[i] = (0 << 16u) | 1; + return; + } + if (!sinfl_build_tbl(&gen, tbl, tbl_bits, cnt)){ + sinfl_build_subtbl(&gen, tbl, tbl_bits, cnt); + } +} +static int +sinfl_decode(const unsigned char **in, const unsigned char *end, + struct sinfl *s, const unsigned *tbl, int bit_len) { + int idx = s->bits & ((1 << bit_len) - 1); + unsigned key = tbl[idx]; + if (key & 0x10) { + /* sub-table lookup */ + int len = key & 0x0f; + sinfl_get(in, end, s, bit_len); + idx = s->bits & ((1 << len)-1); + key = tbl[((key >> 16) & 0xffff) + (unsigned)idx]; + } + sinfl_get(in, end, s, key & 0x0f); + return (key >> 16) & 0x0fff; +} +static int +sinfl_decompress(unsigned char *out, const unsigned char *in, int size) { + static const unsigned char order[] = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; + static const short dbase[30+2] = {1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193, + 257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577}; + static const unsigned char dbits[30+2] = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9, + 10,10,11,11,12,12,13,13,0,0}; + static const short lbase[29+2] = {3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35, + 43,51,59,67,83,99,115,131,163,195,227,258,0,0}; + static const unsigned char lbits[29+2] = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4, + 4,4,4,5,5,5,5,0,0,0}; + + const unsigned char *e = in + size, *o = out; + enum sinfl_states {hdr,stored,fixed,dyn,blk}; + enum sinfl_states state = hdr; + struct sinfl s = {0}; + int last = 0; + + sinfl_get(&in,e,&s,0); /* buffer input */ + while (in < e || s.bitcnt) { + switch (state) { + case hdr: { + int type = 0; /* block header */ + last = sinfl_get(&in,e,&s,1); + type = sinfl_get(&in,e,&s,2); + + switch (type) {default: return (int)(out-o); + case 0x00: state = stored; break; + case 0x01: state = fixed; break; + case 0x02: state = dyn; break;} + } break; + case stored: { + int len; /* uncompressed block */ + sinfl_get(&in,e,&s,s.bitcnt & 7); + len = sinfl_get(&in,e,&s,16); + //int nlen = sinfl_get(&in,e,&s,16); + in -= 2; s.bitcnt = 0; + + if (len > (e-in) || !len) + return (int)(out-o); + memcpy(out, in, (size_t)len); + in += len, out += len; + state = hdr; + } break; + case fixed: { + /* fixed huffman codes */ + int n; unsigned char lens[288+32]; + for (n = 0; n <= 143; n++) lens[n] = 8; + for (n = 144; n <= 255; n++) lens[n] = 9; + for (n = 256; n <= 279; n++) lens[n] = 7; + for (n = 280; n <= 287; n++) lens[n] = 8; + for (n = 0; n < 32; n++) lens[288+n] = 5; + + /* build lit/dist tables */ + sinfl_build(s.lits, lens, 10, 15, 288); + sinfl_build(s.dsts, lens + 288, 8, 15, 32); + state = blk; + } break; + case dyn: { + /* dynamic huffman codes */ + int n, i; + unsigned hlens[SINFL_PRE_TBL_SIZE]; + unsigned char nlens[19] = {0}, lens[288+32]; + int nlit = 257 + sinfl_get(&in,e,&s,5); + int ndist = 1 + sinfl_get(&in,e,&s,5); + int nlen = 4 + sinfl_get(&in,e,&s,4); + for (n = 0; n < nlen; n++) + nlens[order[n]] = (unsigned char)sinfl_get(&in,e,&s,3); + sinfl_build(hlens, nlens, 7, 7, 19); + + /* decode code lengths */ + for (n = 0; n < nlit + ndist;) { + int sym = sinfl_decode(&in, e, &s, hlens, 7); + switch (sym) {default: lens[n++] = (unsigned char)sym; break; + case 16: for (i=3+sinfl_get(&in,e,&s,2);i;i--,n++) lens[n]=lens[n-1]; break; + case 17: for (i=3+sinfl_get(&in,e,&s,3);i;i--,n++) lens[n]=0; break; + case 18: for (i=11+sinfl_get(&in,e,&s,7);i;i--,n++) lens[n]=0; break;} + } + /* build lit/dist tables */ + sinfl_build(s.lits, lens, 10, 15, nlit); + sinfl_build(s.dsts, lens + nlit, 8, 15, ndist); + state = blk; + } break; + case blk: { + /* decompress block */ + int i, sym = sinfl_decode(&in, e, &s, s.lits, 10); + if (sym > 256) {sym -= 257; /* match symbol */ + {int len = sinfl_get(&in, e, &s, lbits[sym]) + lbase[sym]; + int dsym = sinfl_decode(&in, e, &s, s.dsts, 8); + int offs = sinfl_get(&in, e, &s, dbits[dsym]) + dbase[dsym]; + if (offs > (int)(out-o)) { + return (int)(out-o); + } else if (offs == 1) { + /* rle match copying */ + unsigned char c = *(out - offs); + unsigned long w = (c << 24) | (c << 16) | (c << 8) | c; + for (i = 0; i < len >> 2; ++i) { + memcpy(out, &w, 4); + out += 4; + } + len = len & 3; + } else if (offs >= 4) { + /* copy match */ + int wcnt = len >> 2; + for (i = 0; i < wcnt; ++i) { + unsigned long w = 0; + memcpy(&w, out - offs, 4); + memcpy(out, &w, 4); + out += 4; + } + len = len & 3; + } + for (i = 0; i < len; ++i) + {*out = *(out-offs), out++;} + } + } else if (sym == 256) { + /* end of block */ + if (last) return (int)(out-o); + state = hdr; + break; + /* literal */ + } else *out++ = (unsigned char)sym; + } break;} + } + return (int)(out-o); +} +extern int +sinflate(void *out, const void *in, int size) { + return sinfl_decompress((unsigned char*)out, (const unsigned char*)in, size); +} +static unsigned +sinfl_adler32(unsigned adler32, const unsigned char *in, int in_len) { + const unsigned ADLER_MOD = 65521; + unsigned s1 = adler32 & 0xffff; + unsigned s2 = adler32 >> 16; + unsigned blk_len, i; + + blk_len = in_len % 5552; + while (in_len) { + for (i=0; i + 7 < blk_len; i += 8) { + s1 += in[0]; s2 += s1; + s1 += in[1]; s2 += s1; + s1 += in[2]; s2 += s1; + s1 += in[3]; s2 += s1; + s1 += in[4]; s2 += s1; + s1 += in[5]; s2 += s1; + s1 += in[6]; s2 += s1; + s1 += in[7]; s2 += s1; + in += 8; + } + for (; i < blk_len; ++i) + s1 += *in++, s2 += s1; + s1 %= ADLER_MOD; s2 %= ADLER_MOD; + in_len -= blk_len; + blk_len = 5552; + } return (unsigned)(s2 << 16) + (unsigned)s1; +} +extern int +zsinflate(void *out, const void *mem, int size) { + const unsigned char *in = (const unsigned char*)mem; + if (size >= 6) { + const unsigned char *eob = in + size - 4; + int n = sinfl_decompress((unsigned char*)out, in + 2u, size); + unsigned a = sinfl_adler32(1u, (unsigned char*)out, n); + unsigned h = eob[0] << 24 | eob[1] << 16 | eob[2] << 8 | eob[3] << 0; + return a == h ? n : -1; + } else { + return -1; + } +} +#endif + diff --git a/libs/raylib/src/uwp_events.h b/libs/raylib/src/uwp_events.h new file mode 100644 index 0000000..2c403fd --- /dev/null +++ b/libs/raylib/src/uwp_events.h @@ -0,0 +1,119 @@ +/********************************************************************************************** +* +* raylib.uwp_events - Functions for bootstrapping UWP functionality within raylib's core. +* +* +* LICENSE: zlib/libpng +* +* Copyright (c) 2020-2020 Reece Mackie (@Rover656) +* +* This software is provided "as-is", without any express or implied warranty. In no event +* will the authors be held liable for any damages arising from the use of this software. +* +* Permission is granted to anyone to use this software for any purpose, including commercial +* applications, and to alter it and redistribute it freely, subject to the following restrictions: +* +* 1. The origin of this software must not be misrepresented; you must not claim that you +* wrote the original software. If you use this software in a product, an acknowledgment +* in the product documentation would be appreciated but is not required. +* +* 2. Altered source versions must be plainly marked as such, and must not be misrepresented +* as being the original software. +* +* 3. This notice may not be removed or altered from any source distribution. +* +**********************************************************************************************/ + +#ifndef UWP_EVENTS_H +#define UWP_EVENTS_H + +#if defined(__cplusplus) +extern "C" { +#endif + +#if defined(PLATFORM_UWP) + +// Determine if UWP functions are set and ready for raylib's use. +bool UWPIsConfigured(); + +// Call this to set the UWP data path you wish for saving and loading. +void UWPSetDataPath(const char* path); + +// Function for getting program time. +typedef double(*UWPQueryTimeFunc)(); +UWPQueryTimeFunc UWPGetQueryTimeFunc(void); +void UWPSetQueryTimeFunc(UWPQueryTimeFunc func); + +// Function for sleeping the current thread +typedef void (*UWPSleepFunc)(double sleepUntil); +UWPSleepFunc UWPGetSleepFunc(void); +void UWPSetSleepFunc(UWPSleepFunc func); + +// Function for querying the display size +typedef void(*UWPDisplaySizeFunc)(int* width, int* height); +UWPDisplaySizeFunc UWPGetDisplaySizeFunc(void); +void UWPSetDisplaySizeFunc(UWPDisplaySizeFunc func); + +// Functions for mouse cursor control +typedef void(*UWPMouseFunc)(void); +UWPMouseFunc UWPGetMouseLockFunc(); +void UWPSetMouseLockFunc(UWPMouseFunc func); +UWPMouseFunc UWPGetMouseUnlockFunc(); +void UWPSetMouseUnlockFunc(UWPMouseFunc func); +UWPMouseFunc UWPGetMouseShowFunc(); +void UWPSetMouseShowFunc(UWPMouseFunc func); +UWPMouseFunc UWPGetMouseHideFunc(); +void UWPSetMouseHideFunc(UWPMouseFunc func); + +// Function for setting mouse cursor position. +typedef void (*UWPMouseSetPosFunc)(int x, int y); +UWPMouseSetPosFunc UWPGetMouseSetPosFunc(); +void UWPSetMouseSetPosFunc(UWPMouseSetPosFunc func); + +// The below functions are implemented in core.c but are placed here so they can be called by user code. +// This choice is made as platform-specific code is preferred to be kept away from raylib.h + +// Call this when a Key is pressed or released. +void UWPKeyDownEvent(int key, bool down, bool controlKey); + +// Call this on the CoreWindow::CharacterRecieved event +void UWPKeyCharEvent(int key); + +// Call when a mouse button state changes +void UWPMouseButtonEvent(int button, bool down); + +// Call when the mouse cursor moves +void UWPMousePosEvent(double x, double y); + +// Call when the mouse wheel moves +void UWPMouseWheelEvent(int deltaY); + +// Call when the window resizes +void UWPResizeEvent(int width, int height); + +// Call when a gamepad is made active +void UWPActivateGamepadEvent(int gamepad, bool active); + +// Call when a gamepad button state changes +void UWPRegisterGamepadButton(int gamepad, int button, bool down); + +// Call when a gamepad axis state changes +void UWPRegisterGamepadAxis(int gamepad, int axis, float value); + +// Call when the touch point moves +void UWPGestureMove(int pointer, float x, float y); + +// Call when there is a touch down or up +void UWPGestureTouch(int pointer, float x, float y, bool touch); + +// Set the core window pointer so that we can pass it to EGL. +void* UWPGetCoreWindowPtr(); +void UWPSetCoreWindowPtr(void* ptr); + +#if defined(__cplusplus) +} +#endif + +#endif // PLATFORM_UWP + +#endif // UWP_EVENTS_H |