diff options
author | Mitya Selivanov <automainint@guattari.tech> | 2024-07-14 21:12:37 +0200 |
---|---|---|
committer | Mitya Selivanov <automainint@guattari.tech> | 2024-07-14 21:12:37 +0200 |
commit | 30740ca4131d1f574718262451b4410207dc8d4e (patch) | |
tree | fc88b16a216079397ad85b9c6b1a1c1c5712a814 /kit | |
parent | 5e3c99bb1cf1d03ea006300121265571f5008fd2 (diff) | |
download | saw-30740ca4131d1f574718262451b4410207dc8d4e.zip |
Reworking the build system
Diffstat (limited to 'kit')
54 files changed, 9339 insertions, 0 deletions
diff --git a/kit/_lib.c b/kit/_lib.c new file mode 100644 index 0000000..0f7cc19 --- /dev/null +++ b/kit/_lib.c @@ -0,0 +1,17 @@ +#include "allocator.c" +#include "array_ref.c" +#include "dynamic_array.c" +#include "file.c" +#include "input_buffer.c" +#include "input_stream.c" +#include "mersenne_twister_64.c" +#include "secure_random.c" +#include "sha256.c" +#include "atomic.win32.c" +#include "threads.posix.c" +#include "threads.win32.c" +#include "process.posix.c" +#include "process.win32.c" +#include "shared_memory.posix.c" +#include "shared_memory.win32.c" +#include "xml.c" diff --git a/kit/allocator.c b/kit/allocator.c new file mode 100644 index 0000000..9fd7bad --- /dev/null +++ b/kit/allocator.c @@ -0,0 +1,199 @@ +#include "allocator.h" + +#include <assert.h> +#include <string.h> + +#ifndef KIT_DISABLE_SYSTEM_MALLOC +# include <stdlib.h> +#endif + +static void *kit_allocate_default_(i32 request, i64 size, + i64 previous_size, void *pointer) { +#ifndef KIT_DISABLE_SYSTEM_MALLOC + switch (request) { + case KIT_ALLOCATE: + case KIT_ALLOCATE_ZERO: { + assert(size >= 0); + assert(previous_size == 0); + assert(pointer == NULL); + + if (size <= 0) + return NULL; + + void *p = malloc(size); + + if (p != NULL && request == KIT_ALLOCATE_ZERO) + memset(p, 0, size); + + return p; + } + + case KIT_REALLOCATE: + case KIT_REALLOCATE_ZERO: { + assert(size >= 0); + assert(previous_size != 0 || pointer == NULL); + assert(previous_size == 0 || pointer != NULL); + + if (previous_size == 0 && pointer != NULL) + return NULL; + if (previous_size != 0 && pointer == NULL) + return NULL; + if (size == previous_size) + return pointer; + + u8 *p = NULL; + + if (size > 0) { + p = (u8 *) malloc(size); + + if (p != NULL) { + if (size > 0 && previous_size > 0) + memcpy(p, pointer, + size < previous_size ? size : previous_size); + if (request == KIT_REALLOCATE_ZERO && size > previous_size) + memset(p + previous_size, 0, size - previous_size); + } + } + + free(pointer); + + return p; + } + + case KIT_DEALLOCATE: + assert(size == 0); + assert(pointer != NULL); + if (pointer != NULL) + free(pointer); + return NULL; + + case KIT_DEALLOCATE_ALL: + // Do nothing. + // + return NULL; + + default:; + } +#endif + + assert(0); + return NULL; +} + +static void *kit_allocate_from_buffer_(kit_allocator_t *alloc, + i32 request, i64 size, + i64 previous_size, + void *pointer) { + assert(alloc != NULL); + assert(pointer == NULL || pointer < alloc->data); + + if (alloc == NULL) + return NULL; + + switch (request) { + case KIT_ALLOCATE: + case KIT_ALLOCATE_ZERO: { + assert(size >= 0); + assert(previous_size == 0); + assert(pointer == NULL); + + if (size <= 0) + return NULL; + + if (alloc->size < size) + return NULL; + + void *p = alloc->data; + alloc->bytes += size; + alloc->size -= size; + + if (request == KIT_ALLOCATE_ZERO) + memset(p, 0, size); + + return p; + } + + case KIT_REALLOCATE: + case KIT_REALLOCATE_ZERO: { + assert(size >= 0); + assert(previous_size != 0 || pointer == NULL); + assert(previous_size == 0 || pointer != NULL); + + if (size <= 0) + return NULL; + if (size <= previous_size) + return pointer; + if (previous_size == 0 && pointer != NULL) + return NULL; + if (previous_size != 0 && pointer == NULL) + return NULL; + + if ((u8 *) pointer + previous_size == alloc->data) { + if (alloc->size < size - previous_size) + return NULL; + alloc->bytes += size - previous_size; + alloc->size -= size - previous_size; + return pointer; + } + + if (alloc->size < size) + return NULL; + + u8 *p = alloc->bytes; + alloc->bytes += size; + alloc->size -= size; + + if (previous_size > 0) + memcpy(p, pointer, previous_size); + if (request == KIT_REALLOCATE_ZERO) + memset(p + previous_size, 0, size - previous_size); + + return p; + } + + case KIT_DEALLOCATE: + case KIT_DEALLOCATE_ALL: return NULL; + + default:; + } + + assert(0); + return NULL; +} + +#ifndef KIT_ENABLE_CUSTOM_ALLOC_DISPATCH +void *kit_alloc_dispatch(kit_allocator_t *alloc, i32 request, + i64 size, i64 previous_size, void *pointer) { + if (alloc == NULL) + return kit_allocate_default_(request, size, previous_size, + pointer); + + switch (alloc->type) { + case KIT_ALLOC_TYPE_DEFAULT: + return kit_allocate_default_(request, size, previous_size, + pointer); + + case KIT_ALLOC_TYPE_BUFFER: + return kit_allocate_from_buffer_(alloc, request, + // alignment + ((size + 7) / 8) * 8, + previous_size, pointer); + + default:; + } + + return NULL; +} +#endif + +kit_allocator_t kit_alloc_default(void) { + return (kit_allocator_t) { .type = KIT_ALLOC_TYPE_DEFAULT, + .size = 0, + .data = NULL }; +} + +kit_allocator_t kit_alloc_buffer(i64 size, void *buffer) { + return (kit_allocator_t) { .type = KIT_ALLOC_TYPE_BUFFER, + .size = size, + .data = buffer }; +} diff --git a/kit/allocator.h b/kit/allocator.h new file mode 100644 index 0000000..97e453e --- /dev/null +++ b/kit/allocator.h @@ -0,0 +1,50 @@ +#ifndef KIT_ALLOCATOR_H +#define KIT_ALLOCATOR_H + +#include "types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +enum { + KIT_ALLOC_TYPE_NONE, + KIT_ALLOC_TYPE_DEFAULT, + KIT_ALLOC_TYPE_BUFFER, +}; + +enum { + KIT_ALLOCATE, + KIT_ALLOCATE_ZERO, + KIT_DEALLOCATE, + KIT_REALLOCATE, + KIT_REALLOCATE_ZERO, + KIT_DEALLOCATE_ALL, +}; + +typedef struct { + i32 type; + i64 size; + union { + u8 *bytes; + void *data; + }; +} kit_allocator_t; + +// Application should implement this function if custom allocator +// dispatch is enabled. +// +// See KIT_ENABLE_CUSTOM_ALLOC_DISPATCH macro. +// +void *kit_alloc_dispatch(kit_allocator_t *alloc, i32 request, + i64 size, i64 previous_size, void *pointer); + +kit_allocator_t kit_alloc_default(void); + +kit_allocator_t kit_alloc_buffer(i64 size, void *buffer); + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/kit/array_ref.c b/kit/array_ref.c new file mode 100644 index 0000000..a9df2c4 --- /dev/null +++ b/kit/array_ref.c @@ -0,0 +1,41 @@ +#include "array_ref.h" + +#include <string.h> + +i8 kit_ar_equal_bytes(i64 left_element_size, i64 left_size, + void *left_data, i64 right_element_size, + i64 right_size, void *right_data) { + i64 i; + if (left_element_size != right_element_size) + return 0; + if (left_size != right_size) + return 0; + for (i = 0; i < left_size; i++) + if (memcmp((u8 *) left_data + i * left_element_size, + (u8 *) right_data + i * left_element_size, + left_element_size) != 0) + return 0; + return 1; +} + +i8 kit_ar_compare(i64 left_element_size, i64 left_size, + void *left_data, i64 right_element_size, + i64 right_size, void *right_data, + kit_ar_compare_fn compare) { + i64 i; + if (left_element_size < right_element_size) + return -1; + if (left_element_size > right_element_size) + return 1; + for (i = 0; i < left_size && i < right_size; i++) { + i8 c = compare((u8 *) left_data + i * left_element_size, + (u8 *) right_data + i * left_element_size); + if (c != 0) + return c; + } + if (left_size < right_size) + return -1; + if (left_size > right_size) + return 1; + return 0; +} diff --git a/kit/array_ref.h b/kit/array_ref.h new file mode 100644 index 0000000..3a7244e --- /dev/null +++ b/kit/array_ref.h @@ -0,0 +1,57 @@ +#ifndef KIT_ARRAY_REF_H +#define KIT_ARRAY_REF_H + +#include "types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +typedef i8 (*kit_ar_compare_fn)(void *left, void *right); + +i8 kit_ar_equal_bytes(i64 left_element_size, i64 left_size, + void *left_data, i64 right_element_size, + i64 right_size, void *right_data); + +i8 kit_ar_compare(i64 left_element_size, i64 left_size, + void *left_data, i64 right_element_size, + i64 right_size, void *right_data, + kit_ar_compare_fn compare); + +#define KIT_AR(type_) \ + struct { \ + i64 size; \ + type_ *values; \ + } + +#define KIT_AR_WRAP(name_, element_type_, array_) \ + struct { \ + i64 size; \ + element_type_ *values; \ + } name_ = { .size = (sizeof(array_) / sizeof((array_)[0])), \ + .values = (array_) } + +#define KIT_AR_EQUAL(left_, right_) \ + kit_ar_equal_bytes(sizeof((left_).values[0]), (left_).size, \ + (left_).values, sizeof((right_).values[0]), \ + (right_).size, (right_).values) + +#define KIT_AR_COMPARE(left_, right_, compare_) \ + kit_ar_compare(sizeof((left_).values[0]), (left_).size, \ + (left_).values, sizeof((right_).values[0]), \ + (right_).size, (right_).values, \ + (kit_ar_compare_fn) (compare_)) + +#ifdef __cplusplus +} +#endif + +#define ar_compare_fn kit_ar_compare_fn +#define ar_equal_bytes kit_ar_equal_bytes +#define ar_compare kit_ar_compare +#define AR KIT_AR +#define AR_WRAP KIT_AR_WRAP +#define AR_EQUAL KIT_AR_EQUAL +#define AR_COMPARE KIT_AR_COMPARE + +#endif diff --git a/kit/astar.h b/kit/astar.h new file mode 100644 index 0000000..b76ef67 --- /dev/null +++ b/kit/astar.h @@ -0,0 +1,400 @@ +// ================================================================ +// +// A* graph search algorithm +// +// ================================================================ + +// TODO +// - Nearest: save the nearest node when the search is failed or not +// yet finished. +// - Sight: when two nodes are in direct sight of each other, skip +// nodes between them (Theta*). + +#ifndef KIT_ASTAR_H +#define KIT_ASTAR_H + +#include "types.h" +#include "status.h" + +#include <assert.h> +#include <stddef.h> +#include <string.h> + +enum { + ASTAR_PROGRESS = 0, + ASTAR_SUCCESS, + ASTAR_FAIL, + ASTAR_OUT_OF_MEMORY, + ASTAR_INVALID_ARGUMENT, +}; + +typedef struct { + b8 stop; + b8 skip; + i64 neighbor; + i64 distance; +} Astar_Link; + +typedef struct { + i64 id; + i64 previous; + i64 exact_distance; + i64 estimate; +} Astar_Node; + +typedef struct { + i64 capacity; + i64 size; + Astar_Node *values; +} Astar_Set; + +typedef struct { + Astar_Set open; + Astar_Set closed; + void * user_data; + i64 source; + i64 destination; +} Astar_State; + +#ifdef __GNUC__ +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-function" +# pragma GCC diagnostic ignored "-Wunknown-pragmas" +# pragma GCC push_options +# pragma GCC optimize("O3") +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +static s32 astar_init( + Astar_State *state, + Astar_Set open, + Astar_Set closed, + void * user_data, + i64 source, + i64 destination +) { + assert( + state != NULL && + open.capacity > 0 && + open.values != NULL && + closed.capacity > 0 && + closed.values != NULL + ); + + if (state == NULL) + return KIT_ERROR_INVALID_ARGUMENT; + + memset(state, 0, sizeof *state); + + state->source = source; + state->destination = destination; + state->open = open; + state->closed = closed; + state->user_data = user_data; + + if (state->open.capacity <= 0) + return KIT_ERROR_INVALID_ARGUMENT; + + state->open.values[0] = (Astar_Node) { + .id = source, + .previous = -1, + .exact_distance = 0, + .estimate = 0x7fffffffffffffffll, + }; + + state->open.size = 1; + state->closed.size = 0; + + return KIT_OK; +} + +static s32 astar_path(Astar_State *state, i64 *size, i64 *path) { + assert(state != NULL && size != NULL); + + if (state == NULL || size == NULL) + return KIT_ERROR_INVALID_ARGUMENT; + + i64 path_size = *size; + + *size = 1; + + i64 id = state->destination; + + while (id != state->source) { + if (*size > state->closed.size) + return KIT_ERROR_INTERNAL; + + i64 index = 0; + for (; index < state->closed.size; index++) + if (state->closed.values[index].id == id) + break; + if (index == state->closed.size) + return KIT_ERROR_INTERNAL; + + if (path != NULL && *size <= path_size) + path[*size - 1] = id; + + id = state->closed.values[index].previous; + ++*size; + } + + if (path != NULL && *size <= path_size) + path[*size - 1] = id; + + if (path != NULL) { + if (*size < path_size) + path_size = *size; + + for (i64 i = 0; i < path_size / 2; ++i) { + i64 z = path[i]; + path[i] = path[path_size - 1 - i]; + path[path_size - 1 - i] = z; + } + } + + return KIT_OK; +} + +#ifdef __cplusplus +} +#endif + +#ifdef __GNUC__ +# pragma GCC pop_options +# pragma GCC diagnostic pop +#endif + +#endif + +// ================================================================ +// +// Algorithm template +// +// ================================================================ + +#ifdef ASTAR_TEMPLATE + +#ifndef ASTAR_SUFFIX +# define ASTAR_SUFFIX +#endif + +#ifndef ASTAR_NEIGHBOR +# define ASTAR_NEIGHBOR(user_data_, node_, index_) \ + (Astar_Link) { \ + .stop = 1, \ + } +#endif + +#ifndef ASTAR_HEURISTIC +# define ASTAR_HEURISTIC(user_data_, node_0_, node_2_) \ + 0x7fffffffffffffffll +#endif + +#ifdef __GNUC__ +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-function" +# pragma GCC diagnostic ignored "-Wunknown-pragmas" +# pragma GCC push_options +# pragma GCC optimize("O3") +#endif + +#define CAT1_(x, y) x##y +#define CAT2_(x, y) CAT1_(x, y) +#define NAME_(x) CAT2_(x, ASTAR_SUFFIX) + +#ifdef __cplusplus +extern "C" { +#endif + +static s32 NAME_(astar_iteration)(Astar_State *state) { + assert(state != NULL); + + if (state == NULL) + return ASTAR_INVALID_ARGUMENT; + + if (state->open.size == 0) + return ASTAR_FAIL; + + if (state->open.values == NULL || state->closed.values == NULL) + return ASTAR_OUT_OF_MEMORY; + + // Find a node in the open set that is closest to the destination + // + Astar_Node nearest_node; + { + i64 index_in_open = 0; + for (i64 i = 1; i < state->open.size; i++) + if (state->open.values[i].estimate < state->open.values[index_in_open].estimate) + index_in_open = i; + nearest_node = state->open.values[index_in_open]; + if (index_in_open != state->open.size - 1) + state->open.values[index_in_open] = state->open.values[state->open.size - 1]; + --state->open.size; + } + + // Check if we reached the destination + // + if (nearest_node.id == state->destination) { + if (state->closed.size + 1 > state->closed.capacity) { + // Restore the state + state->open.values[state->open.size] = nearest_node; + ++state->open.size; + + return ASTAR_OUT_OF_MEMORY; + } + + // Add the nearest node to the closed set + // + state->closed.values[state->closed.size] = nearest_node; + ++state->closed.size; + + // Finish the search + return ASTAR_SUCCESS; + } + + // Enumerate all neighbors + // + for (i64 k = 0;; ++k) { + // Get a link to the next neighbor node + // + (void) state->user_data; + (void) k; + Astar_Link link = ASTAR_NEIGHBOR(state->user_data, nearest_node.id, k); + + // If there is no more neighbors, break the loop + if (link.stop) + break; + // If there is no link, proceed to the next link + if (link.skip) + continue; + + // Calculate distance estimations + // + (void) state->user_data; + (void) state->destination; + + Astar_Node neighbor_node = { + .id = link.neighbor, + .previous = nearest_node.id, + .exact_distance = nearest_node.exact_distance + link.distance, + .estimate = ASTAR_HEURISTIC(state->user_data, link.neighbor, state->destination), + }; + + // Check if we reached the destination + // + if (neighbor_node.id == state->destination) { + if (state->closed.size + 2 > state->closed.capacity) { + // Restore the state + state->open.values[state->open.size] = nearest_node; + ++state->open.size; + + return ASTAR_OUT_OF_MEMORY; + } + + // Add the nearest node to the closed set + // + state->closed.values[state->closed.size] = nearest_node; + ++state->closed.size; + + // Add the neighbor node to the closed set + // + state->closed.values[state->closed.size] = neighbor_node; + ++state->closed.size; + + // Finish the search + return ASTAR_SUCCESS; + } + + // Check if this node is already in the closed set + // + { + i64 index_in_closed = -1; + for (i64 i = 0; i < state->closed.size; ++i) + if (state->closed.values[i].id == neighbor_node.id) { + index_in_closed = i; + break; + } + if (index_in_closed != -1) { + // Check if this node has a better distance + // + if (neighbor_node.exact_distance < state->closed.values[index_in_closed].exact_distance) + // Replace the node + state->closed.values[index_in_closed] = neighbor_node; + + // Skip this node + continue; + } + } + + // Check if this node is already in the open set + // + { + i64 index_in_open = -1; + for (i64 i = 0; i < state->closed.size; ++i) + if (state->open.values[i].id == neighbor_node.id) { + index_in_open = i; + break; + } + if (index_in_open != -1) { + // Check if this node has a better distance + // + if (neighbor_node.exact_distance < state->open.values[index_in_open].exact_distance) + // Replace the node + state->open.values[index_in_open] = neighbor_node; + + // Skip this node + continue; + } + } + + if (state->open.size + 1 > state->open.capacity) { + // Restore the state + state->open.values[state->open.size] = nearest_node; + ++state->open.size; + + return ASTAR_OUT_OF_MEMORY; + } + + // Add this node to the open set + // + state->open.values[state->open.size] = neighbor_node; + ++state->open.size; + } + + // Check if we can add a node to the closed set + // + if (state->closed.size + 1 > state->closed.capacity) { + // Restore the state + state->open.values[state->open.size - 1] = nearest_node; + ++state->open.size; + + return ASTAR_OUT_OF_MEMORY; + } + + // Add the nearest node to the closed set + // + state->closed.values[state->closed.size] = nearest_node; + ++state->closed.size; + + // Continue the search + return ASTAR_PROGRESS; +} + +#ifdef __cplusplus +} +#endif + +#undef NAME_ +#undef CAT1_ +#undef CAT2_ + +#ifdef __GNUC__ +# pragma GCC pop_options +# pragma GCC diagnostic pop +#endif + +#undef ASTAR_TEMPLATE +#endif diff --git a/kit/async_function.h b/kit/async_function.h new file mode 100644 index 0000000..5460fd6 --- /dev/null +++ b/kit/async_function.h @@ -0,0 +1,241 @@ +#ifndef KIT_ASYNC_FUNCTION_H +#define KIT_ASYNC_FUNCTION_H + +#include "types.h" + +#include <string.h> + +#ifdef __GNUC__ +#define KIT_FALLTHROUGH __attribute__((fallthrough)); +#else +#define KIT_FALLTHROUGH +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct { + i32 _; +} kit_af_void; + +typedef void (*kit_af_state_machine)(void *self_void_); + +#define KIT_AF_STATE_DATA \ + struct { \ + i32 _index; \ + i32 _id; \ + kit_af_state_machine _state_machine; \ + } + +typedef struct { + KIT_AF_STATE_DATA; +} kit_af_type_void; + +#if defined(__GNUC__) || defined(__clang__) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-function" +# pragma GCC diagnostic ignored "-Wunknown-pragmas" +#endif + +#define KIT_AF_INTERNAL(coro_) (*((kit_af_type_void *) (coro_))) + +#ifdef KIT_ENABLE_CUSTOM_ASYNC_FUNCTION_DISPATCH +// Application should implement this function if custom async +// function dispatch is enabled. +// +// See KIT_ENABLE_CUSTOM_ASYNC_FUNCTION_DISPATCH macro. +// +void kit_async_function_dispatch(void *promise); +#else +static void kit_async_function_dispatch(void *promise) { + // Dynamic dispatch by default. + // + KIT_AF_INTERNAL(promise)._state_machine(promise); +} +#endif + +#if defined(__GNUC__) || defined(__clang__) +# pragma GCC diagnostic pop +#endif + +#define KIT_AF_STATE(ret_type_, name_, ...) \ + struct name_##_coro_state_ { \ + KIT_AF_STATE_DATA; \ + ret_type_ return_value; \ + __VA_ARGS__ \ + } + +#define KIT_AF_DECL(name_) void name_(void *self_void_) + +#define KIT_CORO_IMPL(name_) \ + KIT_AF_DECL(name_) { \ + struct name_##_coro_state_ *self = \ + (struct name_##_coro_state_ *) self_void_; \ + switch (self->_index) { \ + case 0:; + +#define KIT_AF_LINE_() __LINE__ + +#define KIT_CORO_END \ + } \ + self->_index = -1; \ + } + +#define KIT_CORO_DECL(ret_type_, name_, ...) \ + KIT_AF_STATE(ret_type_, name_, __VA_ARGS__); \ + KIT_AF_DECL(name_) + +#define KIT_CORO(ret_type_, name_, ...) \ + KIT_AF_STATE(ret_type_, name_, __VA_ARGS__); \ + KIT_CORO_IMPL(name_) + +#define KIT_CORO_DECL_VOID(name_, ...) \ + KIT_CORO_DECL(kit_af_void, name_, __VA_ARGS__) + +#define KIT_CORO_VOID(name_, ...) \ + KIT_CORO(kit_af_void, name_, __VA_ARGS__) + +#define KIT_STATIC_CORO(ret_type_, name_, ...) \ + KIT_AF_STATE(ret_type_, name_, __VA_ARGS__); \ + static KIT_CORO_IMPL(name_) + +#define KIT_STATIC_CORO_VOID(name_, ...) \ + KIT_STATIC_CORO(kit_af_void, name_, __VA_ARGS__) + +#define KIT_AF_EXECUTE(promise_) \ + kit_async_function_dispatch(&(promise_)) + +#define KIT_AF_NEXT(promise_) \ + (kit_async_function_dispatch(&(promise_)), (promise_).return_value) + +#define KIT_AF_YIELD(...) \ + do { \ + self->_index = KIT_AF_LINE_(); \ + self->return_value = __VA_ARGS__; \ + return; \ + case KIT_AF_LINE_():; \ + } while (0) + +#define KIT_AF_YIELD_VOID \ + do { \ + self->_index = KIT_AF_LINE_(); \ + return; \ + case KIT_AF_LINE_():; \ + } while (0) + +#define KIT_AF_RETURN(...) \ + do { \ + self->_index = -1; \ + self->return_value = __VA_ARGS__; \ + return; \ + } while (0) + +#define KIT_AF_RETURN_VOID \ + do { \ + self->_index = -1; \ + return; \ + } while (0) + +#define KIT_AF_AWAIT(promise_) \ + do { \ + KIT_FALLTHROUGH \ + case KIT_AF_LINE_(): \ + if ((promise_)._index != -1) { \ + self->_index = KIT_AF_LINE_(); \ + kit_async_function_dispatch(&(promise_)); \ + } \ + if ((promise_)._index != -1) \ + return; \ + } while (0) + +#define KIT_AF_YIELD_AWAIT(promise_) \ + do { \ + KIT_FALLTHROUGH \ + case KIT_AF_LINE_(): \ + if ((promise_)._index != -1) { \ + self->_index = KIT_AF_LINE_(); \ + kit_async_function_dispatch(&(promise_)); \ + self->return_value = (promise_).return_value; \ + return; \ + } \ + } while (0) + +#define KIT_AF_TYPE(coro_) struct coro_##_coro_state_ + +#define KIT_AF_INITIAL(id_, coro_) \ + ._index = 0, ._id = (id_), ._state_machine = (coro_) + +#define KIT_AF_CREATE(promise_, coro_, ...) \ + KIT_AF_TYPE(coro_) \ + promise_ = { KIT_AF_INITIAL(0, coro_), __VA_ARGS__ } + +#define KIT_AF_CREATE_ID(promise_, id_, ...) \ + KIT_AF_TYPE(coro_) \ + promise_ = { KIT_AF_INITIAL(id_, NULL), __VA_ARGS__ } + +#define KIT_AF_INIT(promise_, coro_, ...) \ + do { \ + KIT_AF_CREATE(kit_af_temp_, coro_, __VA_ARGS__); \ + memcpy(&(promise_), &kit_af_temp_, sizeof kit_af_temp_); \ + } while (0) + +#define KIT_AF_INIT_ID(promise_, id_, ...) \ + do { \ + KIT_AF_CREATE_ID(kit_af_temp_, id_, __VA_ARGS__); \ + memcpy(&(promise_), &kit_af_temp_, sizeof kit_af_temp_); \ + } while (0) + +#define KIT_AF_FINISHED(promise_) ((promise_)._index == -1) + +#define KIT_AF_FINISHED_N(return_, promises_, size_) \ + do { \ + i32 kit_af_index_; \ + (return_) = 1; \ + for (kit_af_index_ = 0; kit_af_index_ < (size_); \ + kit_af_index_++) \ + if (!KIT_AF_FINISHED((promises_)[kit_af_index_])) { \ + (return_) = 0; \ + break; \ + } \ + } while (0) + +#define KIT_AF_FINISHED_ALL(return_, promises_) \ + KIT_AF_FINISHED_N((return_), (promises_), \ + sizeof(promises_) / sizeof((promises_)[0])) + +#ifdef __cplusplus +} +#endif + +#define af_void kit_af_void +#define af_state_machine kit_af_state_machine +#define af_type_void kit_af_type_void +#define AF_STATE_DATA KIT_AF_STATE_DATA +#define AF_STATE KIT_AF_STATE +#define AF_DECL KIT_AF_DECL +#define CORO_IMPL KIT_CORO_IMPL +#define CORO_END KIT_CORO_END +#define CORO_DECL KIT_CORO_DECL +#define CORO KIT_CORO +#define CORO_DECL_VOID KIT_CORO_DECL_VOID +#define STATIC_CORO KIT_STATIC_CORO +#define STATIC_CORO_VOID KIT_STATIC_CORO_VOID +#define CORO_VOID KIT_CORO_VOID +#define AF_EXECUTE KIT_AF_EXECUTE +#define AF_NEXT KIT_AF_NEXT +#define AF_YIELD KIT_AF_YIELD +#define AF_YIELD_VOID KIT_AF_YIELD_VOID +#define AF_RETURN KIT_AF_RETURN +#define AF_RETURN_VOID KIT_AF_RETURN_VOID +#define AF_AWAIT KIT_AF_AWAIT +#define AF_YIELD_AWAIT KIT_AF_YIELD_AWAIT +#define AF_TYPE KIT_AF_TYPE +#define AF_INITIAL KIT_AF_INITIAL +#define AF_CREATE KIT_AF_CREATE +#define AF_INIT KIT_AF_INIT +#define AF_FINISHED KIT_AF_FINISHED +#define AF_FINISHED_N KIT_AF_FINISHED_N +#define AF_FINISHED_ALL KIT_AF_FINISHED_ALL + +#endif diff --git a/kit/atomic.h b/kit/atomic.h new file mode 100644 index 0000000..8ec7bad --- /dev/null +++ b/kit/atomic.h @@ -0,0 +1,219 @@ +#ifndef KIT_ATOMIC_H +#define KIT_ATOMIC_H + +#include "types.h" + +#ifndef _MSC_VER +# include <stdatomic.h> +#else +# include <assert.h> + +# ifdef __cplusplus +extern "C" { +# endif + +# define _Atomic volatile + +enum { + memory_order_relaxed, + memory_order_consume, + memory_order_acquire, + memory_order_release, + memory_order_acq_rel, + memory_order_seq_cst +}; + +void kit_atomic_store_explicit_8(u8 volatile *var, u8 value, + i32 memory_order); + +void kit_atomic_store_explicit_16(u16 volatile *var, u16 value, + i32 memory_order); + +void kit_atomic_store_explicit_32(u32 volatile *var, u32 value, + i32 memory_order); + +void kit_atomic_store_explicit_64(u64 volatile *var, u64 value, + i32 memory_order); + +u8 kit_atomic_load_explicit_8(u8 volatile *var, i32 memory_order); + +u16 kit_atomic_load_explicit_16(u16 volatile *var, i32 memory_order); + +u32 kit_atomic_load_explicit_32(u32 volatile *var, i32 memory_order); + +u64 kit_atomic_load_explicit_64(u64 volatile *var, i32 memory_order); + +u8 kit_atomic_exchange_explicit_8(u8 volatile *var, u8 value, + i32 memory_order); + +u16 kit_atomic_exchange_explicit_16(u16 volatile *var, u16 value, + i32 memory_order); + +u32 kit_atomic_exchange_explicit_32(u32 volatile *var, u32 value, + i32 memory_order); + +u64 kit_atomic_exchange_explicit_64(u64 volatile *var, u64 value, + i32 memory_order); + +i32 kit_atomic_compare_exchange_explicit_8(u8 volatile *var, + u8 *expected, u8 value, + i32 memory_order_succ_, + i32 memory_order_fail_); + +i32 kit_atomic_compare_exchange_explicit_16(u16 volatile *var, + u16 *expected, u16 value, + i32 memory_order_succ_, + i32 memory_order_fail_); + +i32 kit_atomic_compare_exchange_explicit_32(u32 volatile *var, + u32 *expected, u32 value, + i32 memory_order_succ_, + i32 memory_order_fail_); + +i32 kit_atomic_compare_exchange_explicit_64(u64 volatile *var, + u64 *expected, u64 value, + i32 memory_order_succ_, + i32 memory_order_fail_); + +u8 kit_atomic_fetch_add_explicit_8(u8 volatile *var, u8 value, + i32 memory_order); + +u16 kit_atomic_fetch_add_explicit_16(u16 volatile *var, u16 value, + i32 memory_order); + +u32 kit_atomic_fetch_add_explicit_32(u32 volatile *var, u32 value, + i32 memory_order); + +u64 kit_atomic_fetch_add_explicit_64(u64 volatile *var, u64 value, + i32 memory_order); + +# define atomic_store_explicit(var_, value_, memory_order_) \ + do { \ + assert(sizeof *(var_) == 1 || sizeof *(var_) == 2 || \ + sizeof *(var_) == 4 || sizeof *(var_) == 8); \ + if (sizeof *(var_) == 1) \ + kit_atomic_store_explicit_8((u8 volatile *) (var_), \ + (u8) (value_), (memory_order_)); \ + if (sizeof *(var_) == 2) \ + kit_atomic_store_explicit_16((u16 volatile *) (var_), \ + (u16) (value_), \ + (memory_order_)); \ + if (sizeof *(var_) == 4) \ + kit_atomic_store_explicit_32((u32 volatile *) (var_), \ + (u32) (value_), \ + (memory_order_)); \ + if (sizeof *(var_) == 8) \ + kit_atomic_store_explicit_64((u64 volatile *) (var_), \ + (u64) (value_), \ + (memory_order_)); \ + } while (0) + +# define atomic_load_explicit(var_, memory_order_) \ + (assert(sizeof *(var_) == 1 || sizeof *(var_) == 2 || \ + sizeof *(var_) == 4 || sizeof *(var_) == 8), \ + (sizeof *(var_) == 1 \ + ? kit_atomic_load_explicit_8((u8 volatile *) (var_), \ + (memory_order_)) \ + : sizeof *(var_) == 2 \ + ? kit_atomic_load_explicit_16((u16 volatile *) (var_), \ + (memory_order_)) \ + : sizeof *(var_) == 4 \ + ? kit_atomic_load_explicit_32((u32 volatile *) (var_), \ + (memory_order_)) \ + : kit_atomic_load_explicit_64((u64 volatile *) (var_), \ + (memory_order_)))) + +# define atomic_exchange_explicit(var_, value_, memory_order_) \ + (assert(sizeof *(var_) == 1 || sizeof *(var_) == 2 || \ + sizeof *(var_) == 4 || sizeof *(var_) == 8), \ + (sizeof *(var_) == 1 ? kit_atomic_exchange_explicit_8( \ + (u8 volatile *) (var_), \ + (u8) (value_), (memory_order_)) \ + : sizeof *(var_) == 2 ? kit_atomic_exchange_explicit_16( \ + (u16 volatile *) (var_), \ + (u16) (value_), (memory_order_)) \ + : sizeof *(var_) == 4 \ + ? kit_atomic_exchange_explicit_32((u32 volatile *) (var_), \ + (u32) (value_), \ + (memory_order_)) \ + : kit_atomic_exchange_explicit_64((u64 volatile *) (var_), \ + (u64) (value_), \ + (memory_order_)))) + +# define atomic_compare_exchange_strong_explicit( \ + var_, expected_, value_, memory_order_succ_, \ + memory_order_fail_) \ + (assert(sizeof *(var_) == 1 || sizeof *(var_) == 2 || \ + sizeof *(var_) == 4 || sizeof *(var_) == 8), \ + (sizeof *(var_) == 1 \ + ? kit_atomic_compare_exchange_explicit_8( \ + (u8 volatile *) (var_), (u8 *) (expected_), \ + (u8) (value_), (memory_order_succ_), \ + (memory_order_fail_)) \ + : sizeof *(var_) == 2 \ + ? kit_atomic_compare_exchange_explicit_16( \ + (u16 volatile *) (var_), (u16 *) (expected_), \ + (u16) (value_), (memory_order_succ_), \ + (memory_order_fail_)) \ + : sizeof *(var_) == 4 \ + ? kit_atomic_compare_exchange_explicit_32( \ + (u32 volatile *) (var_), (u32 *) (expected_), \ + (u32) (value_), (memory_order_succ_), \ + (memory_order_fail_)) \ + : kit_atomic_compare_exchange_explicit_64( \ + (u64 volatile *) (var_), (u64 *) (expected_), \ + (u64) (value_), (memory_order_succ_), \ + (memory_order_fail_)))) + +# define atomic_compare_exchange_weak_explicit( \ + var_, expected_, value_, memory_order_succ_, \ + memory_order_fail_) \ + atomic_compare_exchange_strong_explicit(var_, expected_, value_, \ + memory_order_succ_, \ + memory_order_fail_) + +# define atomic_fetch_add_explicit(var_, value_, memory_order_) \ + (assert(sizeof *(var_) == 1 || sizeof *(var_) == 2 || \ + sizeof *(var_) == 4 || sizeof *(var_) == 8), \ + (sizeof *(var_) == 1 ? kit_atomic_fetch_add_explicit_8( \ + (u8 volatile *) (var_), \ + (u8) (value_), (memory_order_)) \ + : sizeof *(var_) == 2 ? kit_atomic_fetch_add_explicit_16( \ + (u16 volatile *) (var_), \ + (u16) (value_), (memory_order_)) \ + : sizeof *(var_) == 4 ? kit_atomic_fetch_add_explicit_32( \ + (u32 volatile *) (var_), \ + (u32) (value_), (memory_order_)) \ + : kit_atomic_fetch_add_explicit_64( \ + (u64 volatile *) (var_), \ + (u64) (value_), (memory_order_)))) + +# define atomic_store(var_, value_) \ + atomic_store(var_, value_, memory_order_seq_cst) + +# define atomic_load(var_) atomic_load(var_, memory_order_seq_cst) + +# define atomic_exchange(var_, value_) \ + atomic_exchange(var_, value_, memory_order_seq_cst) + +# define atomic_compare_exchange_strong(var_, expected_, value_) \ + atomic_compare_exchange_strong_explicit(var_, expected_, value_, \ + memory_order_seq_cst, \ + memory_order_seq_cst) + +# define atomic_compare_exchange_weak(var_, expected_, value_) \ + atomic_compare_exchange_weak_explicit(var_, expected_, value_, \ + memory_order_seq_cst, \ + memory_order_seq_cst) + +# define atomic_fetch_add(var_, value_) \ + atomic_fetch_add(var_, value_, memory_order_seq_cst) + +# ifdef __cplusplus +} +# endif +#endif + +#define ATOMIC KIT_ATOMIC + +#endif diff --git a/kit/atomic.win32.c b/kit/atomic.win32.c new file mode 100644 index 0000000..791f8fe --- /dev/null +++ b/kit/atomic.win32.c @@ -0,0 +1,234 @@ +#include "atomic.h" + +#ifdef _MSC_VER +static_assert(sizeof(char) == 1, "Wrong char size"); +static_assert(sizeof(short) == 2, "Wrong short size"); +static_assert(sizeof(int) == 4, "Wrong int size"); + +# include <intrin.h> + +void kit_atomic_store_explicit_8(u8 volatile *var, u8 value, + i32 memory_order) { + char volatile *dst = (char volatile *) var; + char src = (char) value; + + switch (memory_order) { + case memory_order_relaxed: *dst = src; break; + default: _InterlockedExchange8(dst, src); + } +} + +void kit_atomic_store_explicit_16(u16 volatile *var, u16 value, + i32 memory_order) { + short volatile *dst = (short volatile *) var; + short src = (short) value; + + switch (memory_order) { + case memory_order_relaxed: *dst = src; break; + default: _InterlockedExchange16(dst, src); + } +} + +void kit_atomic_store_explicit_32(u32 volatile *var, u32 value, + i32 memory_order) { + int volatile *dst = (int volatile *) var; + int src = (int) value; + + switch (memory_order) { + case memory_order_relaxed: *dst = src; break; + default: _InterlockedExchange(dst, src); + } +} + +void kit_atomic_store_explicit_64(u64 volatile *var, u64 value, + i32 memory_order) { + __int64 volatile *dst = (__int64 volatile *) var; + __int64 src = (__int64) value; + + switch (memory_order) { + case memory_order_relaxed: *dst = src; break; + default: +# ifdef _WIN64 + _InterlockedExchange64(dst, src); +# else + assert(0); + _InterlockedExchange((int volatile *) dst, (int) src); +# endif + } +} + +u8 kit_atomic_load_explicit_8(volatile u8 *var, i32 memory_order) { + char volatile *dst = (char volatile *) var; + + if (memory_order == memory_order_relaxed) + return (u8) *dst; + + return (u8) _InterlockedOr8(dst, 0); +} + +u16 kit_atomic_load_explicit_16(u16 volatile *var, i32 memory_order) { + short volatile *dst = (short volatile *) var; + + if (memory_order == memory_order_relaxed) + return (u16) *dst; + + return (u16) _InterlockedOr16(dst, 0); +} + +u32 kit_atomic_load_explicit_32(u32 volatile *var, i32 memory_order) { + int volatile *dst = (int volatile *) var; + + if (memory_order == memory_order_relaxed) + return (u32) *dst; + + return (u32) _InterlockedOr(dst, 0); +} + +u64 kit_atomic_load_explicit_64(u64 volatile *var, i32 memory_order) { + __int64 volatile *dst = (__int64 volatile *) var; + + if (memory_order == memory_order_relaxed) + return (u64) *dst; + +# ifdef _WIN64 + return (u64) _InterlockedOr64(dst, 0); +# else + assert(0); + return (u64) _InterlockedOr((int volatile *) dst, 0); +# endif +} + +u8 kit_atomic_exchange_explicit_8(volatile u8 *var, u8 value, + i32 memory_order) { + char volatile *dst = (char volatile *) var; + char src = (char) value; + + return (u8) _InterlockedExchange8(dst, src); +} + +u16 kit_atomic_exchange_explicit_16(u16 volatile *var, u16 value, + i32 memory_order) { + short volatile *dst = (short volatile *) var; + short src = (short) value; + + return (u16) _InterlockedExchange16(dst, src); +} + +u32 kit_atomic_exchange_explicit_32(u32 volatile *var, u32 value, + i32 memory_order) { + int volatile *dst = (int volatile *) var; + int src = (int) value; + + return (u32) _InterlockedExchange(dst, src); +} + +u64 kit_atomic_exchange_explicit_64(u64 volatile *var, u64 value, + i32 memory_order) { + __int64 volatile *dst = (__int64 volatile *) var; + __int64 src = (__int64) value; + +# ifdef _WIN64 + return (u64) _InterlockedExchange64(dst, src); +# else + assert(0); + return (u64) _InterlockedExchange((int volatile *) dst, (int) src); +# endif +} + +int kit_atomic_compare_exchange_explicit_8(volatile u8 *var, + u8 *expected, u8 value, + i32 memory_order_succ_, + i32 memory_order_fail_) { + char volatile *dst = (char volatile *) var; + char src = (char) value; + char exp = (char) *expected; + + *expected = (u8) _InterlockedCompareExchange8(dst, src, exp); + + return exp == (char) *expected; +} + +int kit_atomic_compare_exchange_explicit_16(u16 volatile *var, + u16 *expected, u16 value, + i32 memory_order_succ_, + i32 memory_order_fail_) { + short volatile *dst = (short volatile *) var; + short src = (short) value; + short exp = (short) *expected; + + *expected = (u16) _InterlockedCompareExchange16(dst, src, exp); + + return exp == (short) *expected; +} + +int kit_atomic_compare_exchange_explicit_32(u32 volatile *var, + u32 *expected, u32 value, + i32 memory_order_succ_, + i32 memory_order_fail_) { + int volatile *dst = (int volatile *) var; + int src = (int) value; + int exp = (int) *expected; + + *expected = (u32) _InterlockedCompareExchange(dst, src, exp); + + return exp == (int) *expected; +} + +int kit_atomic_compare_exchange_explicit_64(u64 volatile *var, + u64 *expected, u64 value, + i32 memory_order_succ_, + i32 memory_order_fail_) { + __int64 volatile *dst = (__int64 volatile *) var; + __int64 src = (__int64) value; + __int64 exp = (__int64) *expected; + +# ifdef _WIN64 + *expected = (u64) _InterlockedCompareExchange64(dst, src, exp); +# else + assert(0); + *expected = (u64) _InterlockedCompareExchange((int volatile *) dst, + (int) src, (int) exp); +# endif + + return exp == (__int64) *expected; +} + +u8 kit_atomic_fetch_add_explicit_8(volatile u8 *var, u8 value, + i32 memory_order) { + char volatile *dst = (char volatile *) var; + char src = (char) value; + + return (u8) _InterlockedExchangeAdd8(dst, src); +} + +u16 kit_atomic_fetch_add_explicit_16(u16 volatile *var, u16 value, + i32 memory_order) { + short volatile *dst = (short volatile *) var; + short src = (short) value; + + return (u16) _InterlockedExchangeAdd16(dst, src); +} + +u32 kit_atomic_fetch_add_explicit_32(u32 volatile *var, u32 value, + i32 memory_order) { + int volatile *dst = (int volatile *) var; + int src = (int) value; + + return (u32) _InterlockedExchangeAdd(dst, src); +} + +u64 kit_atomic_fetch_add_explicit_64(u64 volatile *var, u64 value, + i32 memory_order) { + __int64 volatile *dst = (__int64 volatile *) var; + __int64 src = (__int64) value; + +# ifdef _WIN64 + return (u64) _InterlockedExchangeAdd64(dst, src); +# else + assert(0); + return (u64) _InterlockedExchangeAdd((int volatile *) dst, + (int) src); +# endif +} + +#endif diff --git a/kit/bigint.h b/kit/bigint.h new file mode 100644 index 0000000..89610f4 --- /dev/null +++ b/kit/bigint.h @@ -0,0 +1,597 @@ +#ifndef KIT_BIGINT_H +#define KIT_BIGINT_H + +#include "string_ref.h" + +#include <assert.h> +#include <string.h> + +#ifdef __cplusplus +extern "C" { +#endif + +#ifndef KIT_BIGINT_SIZE +# define KIT_BIGINT_SIZE 64 +#endif + +typedef struct { + u32 v[KIT_BIGINT_SIZE / 4]; +} kit_bigint_t; + +#if defined(__GNUC__) || defined(__clang__) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-function" +# pragma GCC diagnostic ignored "-Wunknown-pragmas" +# pragma GCC push_options +# pragma GCC optimize("O3") +#endif + +static kit_bigint_t kit_bi_u32(u32 x) { + kit_bigint_t z; + memset(&z, 0, sizeof z); + z.v[0] = x; + return z; +} + +static kit_bigint_t kit_bi_u64(u64 x) { + kit_bigint_t z; + memset(&z, 0, sizeof z); + z.v[0] = (u32) (x & 0xffffffff); + z.v[1] = (u32) (x >> 32); + return z; +} + +static kit_bigint_t kit_bi_i32(i32 x) { + kit_bigint_t z; + memset(&z, x < 0 ? -1 : 0, sizeof z); + z.v[0] = x; + return z; +} + +static kit_bigint_t kit_bi_i64(i64 x) { + kit_bigint_t z; + memset(&z, x < 0 ? -1 : 0, sizeof z); + z.v[0] = (u32) (((u64) x) & 0xffffffff); + z.v[1] = (u32) (((u64) x) >> 32); + return z; +} + +static int kit_bi_is_zero(kit_bigint_t x) { + i64 i; + for (i = 0; i < KIT_BIGINT_SIZE / 4; i++) + if (x.v[i] != 0) + return 0; + return 1; +} + +static int kit_bi_is_neg(kit_bigint_t x) { + return (x.v[KIT_BIGINT_SIZE / 4 - 1] & 0x80000000) != 0; +} + +static int kit_bi_equal(kit_bigint_t x, kit_bigint_t y) { + return kit_ar_equal_bytes(1, KIT_BIGINT_SIZE, x.v, 1, + KIT_BIGINT_SIZE, y.v); +} + +static int kit_bi_compare(kit_bigint_t x, kit_bigint_t y) { + i64 i; + for (i = KIT_BIGINT_SIZE / 4 - 1; i >= 0; i--) + if (x.v[i] < y.v[i]) + return -1; + else if (x.v[i] > y.v[i]) + return 1; + return 0; +} + +static i64 kit_bi_significant_bit_count(kit_bigint_t x) { + i64 n = KIT_BIGINT_SIZE / 4 - 1; + + while (n > 0 && x.v[n] == 0) n--; + + u32 val = x.v[n]; + + if (val == 0) + return 0; + + i64 bits = (val & 0x80000000u) != 0 ? 32 + : (val & 0x40000000u) != 0 ? 31 + : (val & 0x20000000u) != 0 ? 30 + : (val & 0x10000000u) != 0 ? 29 + : (val & 0x8000000u) != 0 ? 28 + : (val & 0x4000000u) != 0 ? 27 + : (val & 0x2000000u) != 0 ? 26 + : (val & 0x1000000u) != 0 ? 25 + : (val & 0x800000u) != 0 ? 24 + : (val & 0x400000u) != 0 ? 23 + : (val & 0x200000u) != 0 ? 22 + : (val & 0x100000u) != 0 ? 21 + : (val & 0x80000u) != 0 ? 20 + : (val & 0x40000u) != 0 ? 19 + : (val & 0x20000u) != 0 ? 18 + : (val & 0x10000u) != 0 ? 17 + : (val & 0x8000u) != 0 ? 16 + : (val & 0x4000u) != 0 ? 15 + : (val & 0x2000u) != 0 ? 14 + : (val & 0x1000u) != 0 ? 13 + : (val & 0x800u) != 0 ? 12 + : (val & 0x400u) != 0 ? 11 + : (val & 0x200u) != 0 ? 10 + : (val & 0x100u) != 0 ? 9 + : (val & 0x80u) != 0 ? 8 + : (val & 0x40u) != 0 ? 7 + : (val & 0x20u) != 0 ? 6 + : (val & 0x10u) != 0 ? 5 + : (val & 0x08u) != 0 ? 4 + : (val & 0x04u) != 0 ? 3 + : (val & 0x02u) != 0 ? 2 + : 1; + + return n * 32 + bits; +} + +static kit_bigint_t kit_bi_and(kit_bigint_t x, kit_bigint_t y) { + kit_bigint_t z; + i64 i; + + for (i = 0; i < KIT_BIGINT_SIZE / 4; i++) z.v[i] = x.v[i] & y.v[i]; + + return z; +} + +static kit_bigint_t kit_bi_or(kit_bigint_t x, kit_bigint_t y) { + kit_bigint_t z; + i64 i; + + for (i = 0; i < KIT_BIGINT_SIZE / 4; i++) z.v[i] = x.v[i] | y.v[i]; + + return z; +} + +static kit_bigint_t kit_bi_xor(kit_bigint_t x, kit_bigint_t y) { + kit_bigint_t z; + i64 i; + + for (i = 0; i < KIT_BIGINT_SIZE / 4; i++) z.v[i] = x.v[i] ^ y.v[i]; + + return z; +} + +static kit_bigint_t kit_bi_shl_uint(kit_bigint_t x, u32 y) { + kit_bigint_t z; + memset(&z, 0, sizeof z); + + i64 words = (i64) (y / 32); + i64 bits = (i64) (y % 32); + i64 i; + + for (i = words; i < KIT_BIGINT_SIZE / 4; i++) { + z.v[i] |= x.v[i - words] << bits; + if (bits != 0 && i + 1 < KIT_BIGINT_SIZE / 4) + z.v[i + 1] = x.v[i - words] >> (32 - bits); + } + + return z; +} + +static kit_bigint_t kit_bi_shr_uint(kit_bigint_t x, u32 y) { + kit_bigint_t z; + memset(&z, 0, sizeof z); + + i64 words = (i64) (y / 32); + i64 bits = (i64) (y % 32); + i64 i; + + for (i = KIT_BIGINT_SIZE / 4 - words - 1; i >= 0; i--) { + z.v[i] |= x.v[i + words] >> bits; + if (bits != 0 && i > 0) + z.v[i - 1] = x.v[i + words] << (32 - bits); + } + + return z; +} + +static i8 kit_bi_carry(u32 x, u32 y, u8 carry) { + assert(carry == 0 || carry == 1); + return 0xffffffffu - x < y || 0xffffffffu - x - y < carry ? 1 : 0; +} + +/* Increment. + */ +static kit_bigint_t kit_bi_inc(kit_bigint_t x) { + kit_bigint_t z; + u8 carry = 1; + i64 i; + + for (i = 0; i < KIT_BIGINT_SIZE / 4; i++) { + z.v[i] = x.v[i] + carry; + carry = kit_bi_carry(x.v[i], 0, carry); + } + + return z; +} + +/* Decrement + */ +static kit_bigint_t kit_bi_dec(kit_bigint_t x) { + kit_bigint_t z; + u8 carry = 0; + i64 i; + + for (i = 0; i < KIT_BIGINT_SIZE / 4; i++) { + z.v[i] = x.v[i] + 0xffffffff + carry; + carry = kit_bi_carry(x.v[i], 0xffffffff, carry); + } + + return z; +} + +/* Addition. + */ +static kit_bigint_t kit_bi_add(kit_bigint_t x, kit_bigint_t y) { + kit_bigint_t z; + u8 carry = 0; + i64 i; + + for (i = 0; i < KIT_BIGINT_SIZE / 4; i++) { + z.v[i] = x.v[i] + y.v[i] + carry; + carry = kit_bi_carry(x.v[i], y.v[i], carry); + } + + return z; +} + +/* Negation. + */ +static kit_bigint_t kit_bi_neg(kit_bigint_t x) { + kit_bigint_t y; + u8 carry = 1; + i64 i; + + for (i = 0; i < KIT_BIGINT_SIZE / 4; i++) { + y.v[i] = (x.v[i] ^ 0xffffffff) + carry; + carry = kit_bi_carry(x.v[i] ^ 0xffffffff, 0, carry); + } + + return y; +} + +/* Subtraction. + */ +static kit_bigint_t kit_bi_sub(kit_bigint_t x, kit_bigint_t y) { + kit_bigint_t z; + u8 carry = 1; + i64 i; + + for (i = 0; i < KIT_BIGINT_SIZE / 4; i++) { + z.v[i] = x.v[i] + (y.v[i] ^ 0xffffffff) + carry; + carry = kit_bi_carry(x.v[i], (y.v[i] ^ 0xffffffff), carry); + } + + return z; +} + +static kit_bigint_t kit_bi_mul_u32(kit_bigint_t x, u32 y) { + kit_bigint_t z; + i64 i, k; + + memset(&z, 0, sizeof z); + + if (y != 0) + for (i = 0; i < KIT_BIGINT_SIZE / 4; i++) { + if (x.v[i] == 0) + continue; + + u64 carry = ((u64) x.v[i]) * ((u64) y); + + for (k = i; k < KIT_BIGINT_SIZE / 4 && carry != 0; k++) { + u64 sum = ((u64) z.v[k]) + carry; + z.v[k] = ((u32) (sum & 0xffffffffull)); + carry = sum >> 32; + } + } + + return z; +} + +/* Multiplication. + */ +static kit_bigint_t kit_bi_mul(kit_bigint_t x, kit_bigint_t y) { + kit_bigint_t z; + i64 i, j, k; + + memset(&z, 0, sizeof z); + + for (i = 0; i < KIT_BIGINT_SIZE / 4; i++) { + if (x.v[i] == 0) + continue; + + for (j = 0; i + j < KIT_BIGINT_SIZE / 4; j++) { + if (y.v[j] == 0) + continue; + + u64 carry = ((u64) x.v[i]) * ((u64) y.v[j]); + + for (k = i + j; k < KIT_BIGINT_SIZE / 4 && carry != 0; k++) { + u64 sum = ((u64) z.v[k]) + carry; + z.v[k] = ((u32) (sum & 0xffffffffull)); + carry = sum >> 32; + } + } + } + + return z; +} + +typedef struct { + i8 undefined; + kit_bigint_t quotient; + kit_bigint_t remainder; +} kit_bi_division_t; + +/* Unsigned division. + */ +static kit_bi_division_t kit_bi_udiv(kit_bigint_t x, kit_bigint_t y) { + kit_bi_division_t z; + memset(&z, 0, sizeof z); + + i64 y_bits = kit_bi_significant_bit_count(y); + + if (y_bits == 0) { + z.undefined = 1; + return z; + } + + i64 x_bits = kit_bi_significant_bit_count(x); + i64 shift = x_bits - y_bits; + + z.remainder = x; + z.quotient = kit_bi_u32(0); + + y = kit_bi_shl_uint(y, (u32) shift); + + while (shift >= 0) { + if (kit_bi_compare(z.remainder, y) >= 0) { + z.remainder = kit_bi_sub(z.remainder, y); + z.quotient.v[shift / 32] |= (1u << (shift % 32)); + } + + y = kit_bi_shr_uint(y, 1); + shift--; + } + + return z; +} + +/* Signed division. + * + * Remainder is always a non-negative value less than absolute value + * of y. + */ +static kit_bi_division_t kit_bi_div(kit_bigint_t x, kit_bigint_t y) { + int x_neg = kit_bi_is_neg(x); + int y_neg = kit_bi_is_neg(y); + + kit_bigint_t x_abs = x_neg ? kit_bi_neg(x) : x; + kit_bigint_t y_abs = y_neg ? kit_bi_neg(y) : y; + + if (x_neg == y_neg) + return kit_bi_udiv(x_abs, y_abs); + + kit_bi_division_t z = kit_bi_udiv(x_abs, y_abs); + + if (!kit_bi_is_zero(z.remainder) && !y_neg) + z.quotient = kit_bi_dec(kit_bi_neg(z.quotient)); + else + z.quotient = kit_bi_neg(z.quotient); + + return z; +} + +static void kit_bi_serialize(kit_bigint_t in, u8 *out) { + i64 i; + + assert(out != NULL); + + for (i = 0; i < KIT_BIGINT_SIZE / 4; i++) { + out[i * 4] = (u8) (in.v[i] & 0xff); + out[i * 4 + 1] = (u8) ((in.v[i] >> 8) & 0xff); + out[i * 4 + 2] = (u8) ((in.v[i] >> 16) & 0xff); + out[i * 4 + 3] = (u8) ((in.v[i] >> 24) & 0xff); + } +} + +static kit_bigint_t kit_bi_deserialize(u8 *in) { + i64 i; + kit_bigint_t out; + + assert(in != NULL); + + memset(&out, 0, sizeof out); + + for (i = 0; i < KIT_BIGINT_SIZE; i++) + out.v[i / 4] |= ((u32) in[i]) << (8 * (i % 4)); + + return out; +} + +static u8 kit_bin_digit(c8 hex) { + assert(hex == '0' || hex == '1'); + return hex == '1' ? 1 : 0; +} + +static kit_bigint_t kit_bi_from_bin(kit_str_t bin) { + kit_bigint_t z; + i64 i; + + memset(&z, 0, sizeof z); + + for (i = 0; i < bin.size && i / 8 < KIT_BIGINT_SIZE; i++) { + u8 digit = kit_bin_digit(bin.values[bin.size - i - 1]); + z.v[i / 32] |= digit << (i % 32); + } + + return z; +} + +static u8 kit_dec_digit(c8 c) { + assert('c' >= '0' && c <= '9'); + return c >= '0' && c <= '9' ? (u8) (c - '0') : 0; +} + +static kit_bigint_t kit_bi_from_dec(kit_str_t dec) { + kit_bigint_t z = kit_bi_u32(0); + kit_bigint_t factor = kit_bi_u32(1); + i64 i; + + for (i = 0; i < dec.size; i++) { + u32 digit = kit_dec_digit(dec.values[dec.size - i - 1]); + z = kit_bi_add(z, kit_bi_mul_u32(factor, digit)); + factor = kit_bi_mul_u32(factor, 10); + } + + return z; +} + +static u8 kit_hex_digit(c8 hex) { + assert((hex >= '0' && hex <= '9') || (hex >= 'a' && hex <= 'f') || + (hex >= 'A' && hex <= 'F')); + + if (hex >= '0' && hex <= '9') + return hex - '0'; + if (hex >= 'a' && hex <= 'f') + return hex - 'a'; + if (hex >= 'A' && hex <= 'F') + return hex - 'A'; + + return 0; +} + +static kit_bigint_t kit_bi_from_hex(kit_str_t hex) { + kit_bigint_t z; + i64 i; + + memset(&z, 0, sizeof z); + + for (i = 0; i < hex.size && i / 2 < KIT_BIGINT_SIZE; i++) { + u8 digit = kit_hex_digit(hex.values[hex.size - i - 1]); + z.v[i / 8] |= digit << (4 * (i % 8)); + } + + return z; +} + +static u8 KIT_BASE32_DIGITS[256] = { + ['1'] = 0, ['2'] = 1, ['3'] = 2, ['4'] = 3, ['5'] = 4, + ['6'] = 5, ['7'] = 6, ['8'] = 7, ['9'] = 8, ['a'] = 9, + ['b'] = 10, ['c'] = 11, ['d'] = 12, ['e'] = 13, ['f'] = 14, + ['g'] = 15, ['h'] = 16, ['j'] = 17, ['k'] = 18, ['m'] = 19, + ['n'] = 20, ['p'] = 21, ['q'] = 22, ['r'] = 23, ['s'] = 24, + ['t'] = 25, ['u'] = 26, ['v'] = 27, ['w'] = 28, ['x'] = 29, + ['y'] = 30, ['z'] = 31 +}; + +static u8 kit_base32_digit(c8 c) { + assert(c == '1' || KIT_BASE32_DIGITS[(size_t) (u8) c] != 0); + + return KIT_BASE32_DIGITS[(size_t) (u8) c]; +} + +static kit_bigint_t kit_bi_from_base32(kit_str_t base32) { + kit_bigint_t z; + i64 i; + + memset(&z, 0, sizeof z); + + for (i = 0; i < base32.size; i++) { + z = kit_bi_shl_uint(z, 5 * i); + z.v[0] |= kit_base32_digit(base32.values[i]); + } + + return z; +} + +static u8 KIT_BASE58_DIGITS[256] = { + ['1'] = 0, ['2'] = 1, ['3'] = 2, ['4'] = 3, ['5'] = 4, + ['6'] = 5, ['7'] = 6, ['8'] = 7, ['9'] = 8, ['A'] = 9, + ['B'] = 10, ['C'] = 11, ['D'] = 12, ['E'] = 13, ['F'] = 14, + ['G'] = 15, ['H'] = 16, ['J'] = 17, ['K'] = 18, ['L'] = 19, + ['M'] = 20, ['N'] = 21, ['P'] = 22, ['Q'] = 23, ['R'] = 24, + ['S'] = 25, ['T'] = 26, ['U'] = 27, ['V'] = 28, ['W'] = 29, + ['X'] = 30, ['Y'] = 31, ['Z'] = 32, ['a'] = 33, ['b'] = 34, + ['c'] = 35, ['d'] = 36, ['e'] = 37, ['f'] = 38, ['g'] = 39, + ['h'] = 40, ['i'] = 41, ['j'] = 42, ['k'] = 43, ['m'] = 44, + ['n'] = 45, ['o'] = 46, ['p'] = 47, ['q'] = 48, ['r'] = 49, + ['s'] = 50, ['t'] = 51, ['u'] = 52, ['v'] = 53, ['w'] = 54, + ['x'] = 55, ['y'] = 56, ['z'] = 57 +}; + +static u8 kit_base58_digit(c8 c) { + assert(c == '1' || KIT_BASE58_DIGITS[(size_t) (u8) c] != 0); + + return KIT_BASE58_DIGITS[(size_t) (u8) c]; +} + +static kit_bigint_t kit_bi_from_base58(kit_str_t base58) { + kit_bigint_t z = kit_bi_u32(0); + kit_bigint_t factor = kit_bi_u32(1); + i64 i; + + for (i = 0; i < base58.size; i++) { + u32 digit = kit_base58_digit(base58.values[base58.size - i - 1]); + z = kit_bi_add(z, kit_bi_mul_u32(factor, digit)); + factor = kit_bi_mul_u32(factor, 58); + } + + return z; +} + +#if defined(__GNUC__) || defined(__clang__) +# pragma GCC pop_options +# pragma GCC diagnostic pop +#endif + +#define KIT_BIN(static_str_) \ + kit_bi_from_bin(kit_str(sizeof(static_str_) - 1, (static_str_))) + +#define KIT_DEC(static_str_) \ + kit_bi_from_dec(kit_str(sizeof(static_str_) - 1, (static_str_))) + +#define KIT_HEX(static_str_) \ + kit_bi_from_hex(kit_str(sizeof(static_str_) - 1, (static_str_))) + +#define KIT_BASE32(static_str_) \ + kit_bi_from_base32(kit_str(sizeof(static_str_) - 1, (static_str_))) + +#define KIT_BASE58(static_str_) \ + kit_bi_from_base58(kit_str(sizeof(static_str_) - 1, (static_str_))) + +#ifdef __cplusplus +} +#endif + +#define bigint_t kit_bigint_t +#define bi_u32 kit_bi_u32 +#define bi_u64 kit_bi_u64 +#define bi_i32 kit_bi_i32 +#define bi_i64 kit_bi_i64 +#define bi_is_zero kit_bi_is_zero +#define bi_is_neg kit_bi_is_neg +#define bi_equal kit_bi_equal +#define bi_compare kit_bi_compare +#define bi_carry kit_bi_carry +#define bi_inc kit_bi_inc +#define bi_dec kit_bi_dec +#define bi_add kit_bi_add +#define bi_neg kit_bi_neg +#define bi_sub kit_bi_sub +#define bi_mul kit_bi_mul +#define bi_div kit_bi_div +#define bi_serialize kit_bi_serialize +#define bi_deserialize kit_bi_deserialize +#define BIN KIT_BIN +#define DEC KIT_DEC +#define HEX KIT_HEX +#define BASE32 KIT_BASE32 +#define BASE58 KIT_BASE58 + +#endif diff --git a/kit/dynamic_array.c b/kit/dynamic_array.c new file mode 100644 index 0000000..ede817b --- /dev/null +++ b/kit/dynamic_array.c @@ -0,0 +1,81 @@ +#include "dynamic_array.h" + +#include <assert.h> + +void kit_da_init(kit_da_void_t *array, i64 element_size, i64 size, + kit_allocator_t *alloc) { + assert(array != NULL); + assert(element_size > 0); + assert(size >= 0); + + memset(array, 0, sizeof(kit_da_void_t)); + + if (size > 0) + array->values = kit_alloc_dispatch(alloc, KIT_ALLOCATE, + element_size * size, 0, NULL); + + if (array->values != NULL) { + array->capacity = size; + array->size = size; + } + + array->alloc = alloc; +} + +static i64 eval_capacity(i64 current_cap, i64 required_cap) { + if (current_cap == 0) + return required_cap; + i64 cap = current_cap; + while (cap < required_cap) cap *= 2; + return cap; +} + +void kit_da_resize(kit_da_void_t *array, i64 element_size, i64 size) { + assert(array != NULL); + assert(element_size > 0); + assert(size >= 0); + + if (size <= array->capacity) { + array->size = size; + } else { + i64 capacity = eval_capacity(array->capacity, size); + + void *bytes = kit_alloc_dispatch( + array->alloc, KIT_ALLOCATE, element_size * capacity, 0, NULL); + + if (bytes != NULL) { + if (array->size > 0) + memcpy(bytes, array->values, element_size * array->size); + if (array->values != NULL) + kit_alloc_dispatch(array->alloc, KIT_DEALLOCATE, 0, 0, + array->values); + array->capacity = capacity; + array->size = size; + array->values = bytes; + } + } +} + +void kit_da_resize_exact(kit_da_void_t *array, i64 element_size, + i64 capacity) { + assert(array != NULL); + assert(element_size > 0); + assert(capacity >= 0); + + void *bytes = capacity <= 0 + ? NULL + : kit_alloc_dispatch(array->alloc, KIT_ALLOCATE, + element_size * capacity, 0, + NULL); + + if (bytes != NULL || capacity == 0) { + if (array->size > 0 && capacity > 0) + memcpy(bytes, array->values, element_size * array->size); + if (array->values != NULL) + kit_alloc_dispatch(array->alloc, KIT_DEALLOCATE, 0, 0, + array->values); + array->capacity = capacity; + array->size = capacity; + array->values = bytes; + } +} diff --git a/kit/dynamic_array.h b/kit/dynamic_array.h new file mode 100644 index 0000000..571f344 --- /dev/null +++ b/kit/dynamic_array.h @@ -0,0 +1,126 @@ +#ifndef KIT_DYNAMIC_ARRAY_H +#define KIT_DYNAMIC_ARRAY_H + +#include "allocator.h" + +#include <string.h> + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct { + i64 capacity; + i64 size; + void *values; + kit_allocator_t *alloc; +} kit_da_void_t; + +void kit_da_init(kit_da_void_t *array, i64 element_size, i64 size, + kit_allocator_t *alloc); + +void kit_da_resize(kit_da_void_t *array, i64 element_size, i64 size); + +void kit_da_resize_exact(kit_da_void_t *array, i64 element_size, + i64 size); + +/* Dynamic array type definition. + */ +#define KIT_DA(element_type_) \ + struct { \ + i64 capacity; \ + i64 size; \ + element_type_ *values; \ + kit_allocator_t *alloc; \ + } + +/* Initialize dynamic array. + */ +#define KIT_DA_INIT(array_, size_, alloc_) \ + kit_da_init((kit_da_void_t *) &(array_), \ + sizeof((array_).values[0]), (size_), (alloc_)) + +/* Declare and initialize dynamic array. + */ +#define KIT_DA_CREATE(name_, element_type_, size_) \ + KIT_DA(element_type_) name_; \ + KIT_DA_INIT(name_, (size_), NULL) + +/* Destroy dynamic array. + */ +#define KIT_DA_DESTROY(array_) \ + do { \ + if ((array_).values != NULL) \ + kit_alloc_dispatch((array_).alloc, KIT_DEALLOCATE, 0, \ + (array_).capacity * \ + sizeof((array_).values[0]), \ + (array_).values); \ + memset(&(array_), 0, sizeof(array_)); \ + } while (0) + +/* Resize dynamic array. + */ +#define KIT_DA_RESIZE(array_, size_) \ + kit_da_resize((kit_da_void_t *) &(array_), \ + sizeof((array_).values[0]), size_) + +/* Resize dynamic array with exact capacity. + */ +#define KIT_DA_RESIZE_EXACT(array_, capacity_) \ + kit_da_resize_exact((kit_da_void_t *) &(array_), \ + sizeof((array_).values[0]), capacity_) + +/* Append a value to dynamic array. + */ +#define KIT_DA_APPEND(array_, value_) \ + do { \ + i64 kit_index_back_ = (array_).size; \ + KIT_DA_RESIZE((array_), kit_index_back_ + 1); \ + if (kit_index_back_ < (array_).size) \ + (array_).values[kit_index_back_] = (value_); \ + } while (0) + +/* Insert a value into dynamic array. + */ +#define KIT_DA_INSERT(array_, index_, value_) \ + do { \ + i64 kit_i_; \ + i64 kit_index_back_ = (array_).size; \ + i64 kit_indert_n_ = (index_); \ + KIT_DA_RESIZE((array_), kit_index_back_ + 1); \ + if (kit_index_back_ + 1 == (array_).size) { \ + for (kit_i_ = kit_index_back_; kit_i_ > kit_indert_n_; \ + kit_i_--) \ + (array_).values[kit_i_] = (array_).values[kit_i_ - 1]; \ + (array_).values[kit_indert_n_] = (value_); \ + } \ + } while (0) + +/* Erase a value from dynamic array. + */ +#define KIT_DA_ERASE(array_, index_) \ + do { \ + i64 i_; \ + for (i_ = (index_) + 1; i_ < (array_).size; i_++) \ + (array_).values[i_ - 1] = (array_).values[i_]; \ + KIT_DA_RESIZE((array_), (array_).size - 1); \ + } while (0) + +#ifdef __cplusplus +} +#endif + +#define da_void_t kit_da_void_t +#define da_init kit_da_init +#define da_resize kit_da_resize +#define DA KIT_DA +#define DA_INIT KIT_DA_INIT +#define DA_CREATE KIT_DA_CREATE +#define DA_DESTROY KIT_DA_DESTROY +#define DA_RESIZE KIT_DA_RESIZE +#define DA_RESIZE_EXACT KIT_DA_RESIZE_EXACT +#define DA_APPEND KIT_DA_APPEND +#define DA_INSERT KIT_DA_INSERT +#define DA_ERASE KIT_DA_ERASE + +#endif diff --git a/kit/file.c b/kit/file.c new file mode 100644 index 0000000..3eafc70 --- /dev/null +++ b/kit/file.c @@ -0,0 +1,691 @@ +#include "file.h" + +#include <assert.h> +#include <stdlib.h> +#include <string.h> + +enum { PATH_BUF_SIZE = 4096 }; + +#if defined(_WIN32) && !defined(__CYGWIN__) +# ifndef WIN32_LEAN_AND_MEAN +# define WIN32_LEAN_AND_MEAN +# endif +# ifndef NOMINMAX +# define NOMINMAX +# endif +# include <windows.h> +# include <shlwapi.h> +#else +# include <dirent.h> +# include <sys/mman.h> +# include <sys/stat.h> +# include <fcntl.h> +# include <unistd.h> +# include <limits.h> +#endif + +#ifdef __APPLE__ +# define st_mtim st_mtimespec +#endif + +#ifndef PATH_MAX +# define PATH_MAX MAX_PATH +#endif + +static i32 is_delim(char c) { + return c == '/' || c == '\\'; +} + +kit_str_builder_t kit_get_env(kit_str_t name, + kit_allocator_t *alloc) { + char *val = getenv(BS(name)); + i64 size = val != NULL ? (i64) strlen(val) : 0; + + str_builder_t result; + DA_INIT(result, size, alloc); + assert(result.size == size); + + if (result.size == size && size > 0) + memcpy(result.values, val, result.size); + else + DA_RESIZE(result, 0); + + return result; +} + +kit_str_builder_t kit_path_norm(kit_str_t path, + kit_allocator_t *alloc) { + str_t parent = SZ(".."); + i64 i, i1, j; + + str_builder_t norm; + DA_INIT(norm, path.size, alloc); + assert(norm.size == path.size); + + if (norm.size != path.size) + return norm; + + memcpy(norm.values, path.values, path.size); + + for (i1 = 0, i = 0; i < path.size; i++) { + if (!is_delim(path.values[i])) + continue; + + str_t s = { .size = i - i1 - 1, .values = path.values + i1 + 1 }; + if (AR_EQUAL(s, parent)) { + i32 have_parent = 0; + i64 i0 = 0; + + for (j = 0; j < i1; j++) { + if (norm.values[j] != '\0') + have_parent = 1; + if (is_delim(norm.values[j])) + i0 = j; + } + + if (have_parent) { + memset(norm.values + i0, '\0', i - i0); + + if (!is_delim(path.values[i0])) + norm.values[i] = '\0'; + } + } + + i1 = i; + } + + i64 size = 0; + + for (i = 0; i < norm.size; i++) { + if (norm.values[i] != '\0') { + if (is_delim(norm.values[i])) + norm.values[size] = KIT_PATH_DELIM_C; + else + norm.values[size] = norm.values[i]; + size++; + } + } + + norm.size = size; + return norm; +} + +kit_str_builder_t kit_path_join(kit_str_t left, kit_str_t right, + kit_allocator_t *alloc) { + i64 left_size = left.size; + i64 right_size = right.size; + char *right_values = right.values; + + if (left_size > 0 && is_delim(left.values[left_size - 1])) + left_size--; + if (right_size > 0 && is_delim(right.values[0])) { + right_size--; + right_values++; + } + + kit_str_builder_t joined; + DA_INIT(joined, left_size + right_size + 1, alloc); + assert(joined.size == left_size + right_size + 1); + + if (joined.size != left_size + right_size + 1) + return joined; + + memcpy(joined.values, left.values, left_size); + joined.values[left_size] = KIT_PATH_DELIM_C; + memcpy(joined.values + left_size + 1, right_values, right_size); + + return joined; +} + +kit_str_builder_t kit_path_user(kit_allocator_t *alloc) { + kit_str_builder_t user = kit_get_env(SZ(KIT_ENV_HOME), alloc); + if (user.size == 0) { + DA_RESIZE(user, 1); + if (user.size == 1) + user.values[0] = '.'; + } + return user; +} + +kit_str_builder_t kit_path_cache(kit_allocator_t *alloc) { + kit_str_builder_t cache, user; + + cache = kit_get_env(SZ("XDG_CACHE_HOME"), alloc); + if (cache.size != 0) + return cache; + DA_DESTROY(cache); + +#if defined(_WIN32) && !defined(__CYGWIN__) + cache = kit_get_env(SZ("TEMP"), alloc); + if (cache.size != 0) + return cache; + DA_DESTROY(cache); +#endif + + user = kit_path_user(alloc); + cache = +#ifdef __APPLE__ + kit_path_join(WRAP_STR(user), SZ("Library" PATH_DELIM "Caches"), + alloc); +#else + kit_path_join(WRAP_STR(user), SZ(".cache"), alloc); +#endif + DA_DESTROY(user); + + return cache; +} + +kit_str_builder_t kit_path_data(kit_allocator_t *alloc) { + kit_str_builder_t data, user; + + data = kit_get_env(SZ("XDG_DATA_HOME"), alloc); + if (data.size != 0) + return data; + DA_DESTROY(data); + +#if defined(_WIN32) && !defined(__CYGWIN__) + data = kit_get_env(SZ("LOCALAPPDATA"), alloc); + if (data.size != 0) + return data; + DA_DESTROY(data); +#endif + + user = kit_path_user(alloc); + data = +#ifdef __APPLE__ + kit_path_join(WRAP_STR(user), SZ("Library"), alloc); +#else + kit_path_join(WRAP_STR(user), SZ(".local" PATH_DELIM "share"), + alloc); +#endif + DA_DESTROY(user); + + return data; +} + +kit_str_t kit_path_index(kit_str_t path, i64 index) { + str_t s = { .size = 0, .values = NULL }; + + i64 i0 = 0; + i64 i = 0; + i64 n = 0; + + for (; i < path.size; i++) { + if (!is_delim(path.values[i])) + continue; + + if (i0 < i) { + if (n++ == index) { + s.values = path.values + i0; + s.size = i - i0; + return s; + } + } + + i0 = i + 1; + } + + if (n == index) { + s.values = path.values + i0; + s.size = i - i0; + } + + return s; +} + +kit_str_t kit_path_take(kit_str_t path, i64 count) { + str_t s = { .size = 0, .values = path.values }; + + i64 i0 = 0; + i64 i = 0; + i64 n = 0; + + for (; i < path.size; i++) { + if (!is_delim(path.values[i])) + continue; + + if (i0 < i) { + if (n++ == count) { + s.size = i; + return s; + } + } + + i0 = i + 1; + } + + if (n == count) + s.size = i; + + return s; +} + +// TODO +// Long path support for Windows +// +static void kit_prepare_path_(char *buf, kit_str_t path) { + assert(path.size == 0 || path.values != NULL); + assert(path.size + 1 < PATH_BUF_SIZE); + + memset(buf, 0, PATH_BUF_SIZE); + if (path.size > 0 && path.size + 1 < PATH_BUF_SIZE) + memcpy(buf, path.values, path.size); +} + +#define PREPARE_PATH_BUF_ \ + char buf[PATH_BUF_SIZE]; \ + kit_prepare_path_(buf, path) + +s32 kit_folder_create(kit_str_t path) { + PREPARE_PATH_BUF_; +#if defined(_WIN32) && !defined(__CYGWIN__) + return CreateDirectoryA(buf, NULL) ? KIT_OK + : KIT_ERROR_MKDIR_FAILED; +#else + return mkdir(buf, 0775) == 0 ? KIT_OK : KIT_ERROR_MKDIR_FAILED; +#endif +} + +s32 kit_folder_create_recursive(kit_str_t path) { + for (i32 i = 0;; i++) { + str_t part = kit_path_take(path, i); + i32 type = kit_path_type(part); + if (type == KIT_PATH_FILE) + return KIT_ERROR_FILE_ALREADY_EXISTS; + if (type == KIT_PATH_NONE) { + s32 s = kit_folder_create(part); + if (s != KIT_OK) + return s; + } + if (part.size == path.size) + break; + } + + return KIT_OK; +} + +s32 kit_file_remove(kit_str_t path) { + PREPARE_PATH_BUF_; +#if defined(_WIN32) && !defined(__CYGWIN__) + return DeleteFileA(buf) ? KIT_OK : KIT_ERROR_UNLINK_FAILED; +#else + return unlink(buf) == 0 ? KIT_OK : KIT_ERROR_UNLINK_FAILED; +#endif +} + +s32 kit_folder_remove(kit_str_t path) { + PREPARE_PATH_BUF_; +#if defined(_WIN32) && !defined(__CYGWIN__) + return RemoveDirectoryA(buf) ? KIT_OK : KIT_ERROR_RMDIR_FAILED; +#else + return rmdir(buf) == 0 ? KIT_OK : KIT_ERROR_RMDIR_FAILED; +#endif +} + +s32 kit_file_remove_recursive(kit_str_t path, + kit_allocator_t *alloc) { + i32 type = kit_path_type(path); + i64 i; + + switch (type) { + case KIT_PATH_FILE: { + s32 s = kit_file_remove(path); + assert(s == KIT_OK); + return s; + } + + case KIT_PATH_FOLDER: { + kit_path_list_t list = kit_folder_enum(path, alloc); + + assert(list.status == KIT_OK); + if (list.status != KIT_OK) { + kit_path_list_destroy(list); + return list.status; + } + + for (i = 0; i < list.files.size; i++) { + str_builder_t full_path = kit_path_join( + path, WRAP_STR(list.files.values[i]), alloc); + s32 s = kit_file_remove_recursive(WRAP_STR(full_path), alloc); + DA_DESTROY(full_path); + assert(s == KIT_OK); + } + + kit_path_list_destroy(list); + + s32 s = kit_folder_remove(path); + assert(s == KIT_OK); + return s; + } + + default:; + } + + return KIT_ERROR_FILE_DOES_NOT_EXIST; +} + +kit_path_type_t kit_path_type(kit_str_t path) { + PREPARE_PATH_BUF_; +#if defined(_WIN32) && !defined(__CYGWIN__) + if (PathFileExistsA(buf)) { + if ((GetFileAttributesA(buf) & FILE_ATTRIBUTE_DIRECTORY) != 0) + return KIT_PATH_FOLDER; + else + return KIT_PATH_FILE; + } +#else + struct stat info; + if (stat(buf, &info) == 0) { + if (S_ISREG(info.st_mode)) + return KIT_PATH_FILE; + if (S_ISDIR(info.st_mode)) + return KIT_PATH_FOLDER; + } +#endif + return KIT_PATH_NONE; +} + +kit_file_info_t kit_file_info(kit_str_t path) { + kit_file_info_t result; + memset(&result, 0, sizeof result); + + PREPARE_PATH_BUF_; + +#if defined(_WIN32) && !defined(__CYGWIN__) + HANDLE f = CreateFileA(buf, GENERIC_READ, FILE_SHARE_READ, NULL, + OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL); + if (f != INVALID_HANDLE_VALUE) { + FILETIME ft; + if (GetFileTime(f, NULL, NULL, &ft) != 0) { + i64 nsec100 = (((u64) ft.dwHighDateTime) << 32) | + (u64) ft.dwLowDateTime; + result.time_modified_sec = (i64) (nsec100 / 10000000); + result.time_modified_nsec = (i32) (100 * (nsec100 % 10000000)); + } else { + assert(0); + } + + DWORD high; + DWORD low = GetFileSize(f, &high); + + result.size = (i64) ((((u64) high) << 32) | (u64) low); + result.status = KIT_OK; + + CloseHandle(f); + return result; + } +#else + struct stat info; + if (stat(buf, &info) == 0 && S_ISREG(info.st_mode)) { + result.size = (i64) info.st_size; +# ifndef st_mtime + // No support for nanosecond timestamps. + // + result.time_modified_sec = (i64) info.st_mtime; +# else + result.time_modified_sec = (i64) info.st_mtim.tv_sec; + result.time_modified_nsec = (i32) info.st_mtim.tv_nsec; +# endif + result.status = KIT_OK; + return result; + } +#endif + + result.status = KIT_ERROR_FILE_DOES_NOT_EXIST; + return result; +} + +kit_path_list_t kit_folder_enum(kit_str_t path, + kit_allocator_t *alloc) { + PREPARE_PATH_BUF_; + + kit_path_list_t result = { .status = KIT_OK }; + DA_INIT(result.files, 0, alloc); + +#if defined(_WIN32) && !defined(__CYGWIN__) + if (path.size + 3 >= PATH_BUF_SIZE) { + result.status = KIT_ERROR_PATH_TOO_LONG; + return result; + } + + buf[path.size] = '\\'; + buf[path.size + 1] = '*'; + + WIN32_FIND_DATAA data; + HANDLE find = FindFirstFileA(buf, &data); + + if (find == INVALID_HANDLE_VALUE) + return result; + + do { + if (strcmp(data.cFileName, ".") == 0 || + strcmp(data.cFileName, "..") == 0) + continue; + + i64 n = result.files.size; + DA_RESIZE(result.files, n + 1); + if (result.files.size != n + 1) { + result.status = KIT_ERROR_OUT_OF_MEMORY; + break; + } + + i64 size = (i64) strlen(data.cFileName); + DA_INIT(result.files.values[n], size, alloc); + if (result.files.values[n].size != size) { + DA_RESIZE(result.files, n); + result.status = KIT_ERROR_OUT_OF_MEMORY; + break; + } + + memcpy(result.files.values[n].values, data.cFileName, size); + } while (FindNextFileA(find, &data) != 0); + + FindClose(find); +#else + DIR *directory = opendir(buf); + + if (directory == NULL) + return result; + + for (;;) { + struct dirent *entry = readdir(directory); + + if (entry == NULL) + break; + + if (entry->d_name[0] == '.') + continue; + + i64 n = result.files.size; + DA_RESIZE(result.files, n + 1); + if (result.files.size != n + 1) { + result.status = KIT_ERROR_OUT_OF_MEMORY; + break; + } + + i64 size = (i64) strlen(entry->d_name); + DA_INIT(result.files.values[n], size, alloc); + if (result.files.values[n].size != size) { + DA_RESIZE(result.files, n); + result.status = KIT_ERROR_OUT_OF_MEMORY; + break; + } + + if (size > 0) + memcpy(result.files.values[n].values, entry->d_name, size); + } + + closedir(directory); +#endif + + return result; +} + +void kit_path_list_destroy(kit_path_list_t list) { + i64 i; + for (i = 0; i < list.files.size; i++) + DA_DESTROY(list.files.values[i]); + DA_DESTROY(list.files); +} + +kit_mapped_file_t kit_file_map(kit_str_t path, i64 size, i32 mode) { + assert(size > 0); + assert(path.size > 0); + assert(path.size <= PATH_MAX); + assert(path.values != NULL); + + kit_mapped_file_t mf; + memset(&mf, 0, sizeof mf); + + if (size <= 0) { + mf.status = KIT_ERROR_INVALID_SIZE; + return mf; + } + + if (path.size <= 0) { + mf.status = KIT_ERROR_INVALID_ARGUMENT; + return mf; + } + + if (path.size > PATH_MAX) { + mf.status = KIT_ERROR_PATH_TOO_LONG; + return mf; + } + +#if defined(_WIN32) && !defined(__CYGWIN__) + char buf[MAX_PATH + 1]; + memcpy(buf, path.values, path.size); + buf[path.size] = '\0'; + + HANDLE file = CreateFileA( + buf, GENERIC_READ | GENERIC_WRITE, + mode == FILE_MAP_SHARED ? FILE_SHARE_READ | FILE_SHARE_WRITE + : 0, + NULL, OPEN_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL); + + if (file == INVALID_HANDLE_VALUE) { + mf.status = KIT_ERROR_OPEN_FAILED; + return mf; + } + + LONG high = (LONG) (size >> 32); + + if (SetFilePointer(file, (LONG) size, &high, FILE_BEGIN) == + INVALID_SET_FILE_POINTER) { + CloseHandle(file); + assert(0); + mf.status = KIT_ERROR_TRUNCATE_FAILED; + return mf; + } + + if (!SetEndOfFile(file)) { + CloseHandle(file); + assert(0); + mf.status = KIT_ERROR_TRUNCATE_FAILED; + return mf; + } + + HANDLE map = CreateFileMappingA(file, NULL, PAGE_READWRITE, + (DWORD) (size >> 32), (DWORD) size, + NULL); + + if (map == INVALID_HANDLE_VALUE) { + CloseHandle(file); + assert(0); + mf.status = KIT_ERROR_MAP_FAILED; + return mf; + } + + void *p = MapViewOfFile(map, FILE_MAP_ALL_ACCESS, 0, 0, + (SIZE_T) size); + + if (p == NULL) { + CloseHandle(map); + CloseHandle(file); + assert(0); + mf.status = KIT_ERROR_MAP_FAILED; + return mf; + } + + mf.status = KIT_OK; + mf.size = size; + mf.bytes = p; + mf._file = file; + mf._map = map; +#else + char buf[PATH_MAX + 1]; + memcpy(buf, path.values, path.size); + buf[path.size] = '\0'; + + i32 fd = open(buf, O_RDWR | O_CREAT, 0664); + + if (fd == -1) { + mf.status = KIT_ERROR_OPEN_FAILED; + return mf; + } + + if (ftruncate(fd, size) == -1) { + close(fd); + assert(0); + mf.status = KIT_ERROR_TRUNCATE_FAILED; + return mf; + } + + void *p = mmap( + NULL, size, PROT_READ | PROT_WRITE, + mode == KIT_FILE_MAP_SHARED ? MAP_SHARED : MAP_PRIVATE, fd, 0); + + if (p == MAP_FAILED) { + close(fd); + assert(0); + mf.status = KIT_ERROR_MAP_FAILED; + return mf; + } + + mf.status = KIT_OK; + mf.size = size; + mf.bytes = (u8 *) p; + mf._fd = fd; +#endif + + return mf; +} + +s32 kit_file_sync(kit_mapped_file_t *mf) { + assert(mf != NULL); + + if (mf == NULL) + return KIT_ERROR_INVALID_ARGUMENT; + + s32 status = KIT_OK; + +#if !defined(_WIN32) || defined(__CYGWIN__) + if (msync(mf->bytes, mf->size, MS_SYNC) != 0) + status |= KIT_ERROR_SYNC_FAILED; +#endif + + return status; +} + +s32 kit_file_unmap(kit_mapped_file_t *mf) { + assert(mf != NULL); + + if (mf == NULL) + return KIT_ERROR_INVALID_ARGUMENT; + + s32 status = KIT_OK; + +#if defined(_WIN32) && !defined(__CYGWIN__) + if (!UnmapViewOfFile(mf->bytes)) + status |= KIT_ERROR_UNMAP_FAILED; + if (!CloseHandle(mf->_map) || !CloseHandle(mf->_file)) + status |= KIT_ERROR_CLOSE_FAILED; +#else + if (munmap(mf->bytes, mf->size) != 0) + status |= KIT_ERROR_UNMAP_FAILED; + if (close(mf->_fd) != 0) + status |= KIT_ERROR_CLOSE_FAILED; +#endif + + return status; +} diff --git a/kit/file.h b/kit/file.h new file mode 100644 index 0000000..12f00a2 --- /dev/null +++ b/kit/file.h @@ -0,0 +1,134 @@ +#ifndef KIT_FILE_H +#define KIT_FILE_H + +#include "dynamic_array.h" +#include "string_builder.h" + +#include <stdio.h> + +#ifdef __cplusplus +extern "C" { +#endif + +#if defined(_WIN32) && !defined(__CYGWIN__) +# define KIT_PATH_DELIM_C '\\' +# define KIT_PATH_DELIM "\\" +# define KIT_ENV_HOME "USERPROFILE" +#else +# define KIT_PATH_DELIM_C '/' +# define KIT_PATH_DELIM "/" +# define KIT_ENV_HOME "HOME" +#endif + +typedef enum { + KIT_PATH_NONE, + KIT_PATH_FILE, + KIT_PATH_FOLDER +} kit_path_type_t; + +typedef struct { + s32 status; + + i64 time_modified_sec; + i32 time_modified_nsec; + i64 size; +} kit_file_info_t; + +typedef struct { + s32 status; + KIT_DA(kit_str_builder_t) files; +} kit_path_list_t; + +enum { KIT_FILE_MAP_PRIVATE, KIT_FILE_MAP_SHARED }; + +typedef struct { + s32 status; + i64 size; + u8 *bytes; +#if defined(_WIN32) && !defined(__CYGWIN__) + void *_file; + void *_map; +#else + int _fd; +#endif +} kit_mapped_file_t; + +kit_str_builder_t kit_get_env(kit_str_t name, kit_allocator_t *alloc); + +kit_str_builder_t kit_path_norm(kit_str_t path, + kit_allocator_t *alloc); + +kit_str_builder_t kit_path_join(kit_str_t left, kit_str_t right, + kit_allocator_t *alloc); + +kit_str_builder_t kit_path_user(kit_allocator_t *alloc); + +kit_str_builder_t kit_path_cache(kit_allocator_t *alloc); + +kit_str_builder_t kit_path_data(kit_allocator_t *alloc); + +kit_str_t kit_path_index(kit_str_t path, i64 index); + +kit_str_t kit_path_take(kit_str_t path, i64 count); + +s32 kit_folder_create(kit_str_t path); + +s32 kit_folder_create_recursive(kit_str_t path); + +s32 kit_file_remove(kit_str_t path); + +s32 kit_folder_remove(kit_str_t path); + +s32 kit_file_remove_recursive(kit_str_t path, kit_allocator_t *alloc); + +kit_path_type_t kit_path_type(kit_str_t path); + +kit_file_info_t kit_file_info(kit_str_t path); + +kit_path_list_t kit_folder_enum(kit_str_t path, + kit_allocator_t *alloc); + +void kit_path_list_destroy(kit_path_list_t list); + +kit_mapped_file_t kit_file_map(kit_str_t path, i64 size, i32 mode); +s32 kit_file_sync(kit_mapped_file_t *mf); +s32 kit_file_unmap(kit_mapped_file_t *mf); + +#ifdef __cplusplus +} +#endif + +#define path_type_t kit_path_type_t +#define file_info_t kit_file_info_t +#define path_list_t kit_path_list_t +#define mapped_file_t kit_mapped_file_t +#define get_env kit_get_env +#define path_norm kit_path_norm +#define path_join kit_path_join +#define path_user kit_path_user +#define path_cache kit_path_cache +#define path_data kit_path_data +#define path_index kit_path_index +#define path_take kit_path_take +#define folder_create kit_folder_create +#define folder_create_recursive kit_folder_create_recursive +#define file_remove kit_file_remove +#define folder_remove kit_folder_remove +#define file_remove_recursive kit_file_remove_recursive +#define path_type kit_path_type +#define file_info kit_file_info +#define folder_enum kit_folder_enum +#define path_list_destroy kit_path_list_destroy +#define file_map kit_file_map +#define file_sync kit_file_sync +#define file_unmap kit_file_unmap +#define FILE_MAP_PRIVATE KIT_FILE_MAP_PRIVATE +#define FILE_MAP_SHARED KIT_FILE_MAP_SHARED +#define PATH_DELIM_C KIT_PATH_DELIM_C +#define PATH_DELIM KIT_PATH_DELIM +#define ENV_HOME KIT_ENV_HOME +#define PATH_NONE KIT_PATH_NONE +#define PATH_FILE KIT_PATH_FILE +#define PATH_FOLDER KIT_PATH_FOLDER + +#endif diff --git a/kit/http1.h b/kit/http1.h new file mode 100644 index 0000000..0a58f96 --- /dev/null +++ b/kit/http1.h @@ -0,0 +1,511 @@ +// TODO +// - Error handling +// - HTTPS support + +#ifndef KIT_HTTP1_H +#define KIT_HTTP1_H + +#include "types.h" +#include "string_builder.h" +#include "sockets.h" + +#include <stdio.h> +#include <assert.h> + +#ifdef __cplusplus +extern "C" { +#endif + +#define KIT_HTTP1_NEWLINE "\r\n" +#define KIT_HTTP1_SPACE " " +#define KIT_HTTP1_HEADER_SEPARATOR ": " +#define KIT_HTTP1_BUFFER_SIZE 8192 + +enum { + KIT_HTTP1_OPTIONS, + KIT_HTTP1_GET, + KIT_HTTP1_HEAD, + KIT_HTTP1_POST, + KIT_HTTP1_PUT, + KIT_HTTP1_DELETE, + KIT_HTTP1_TRACE, + KIT_HTTP1_CONNECT, +}; + +typedef struct { + kit_str_t key; + kit_str_t value; +} kit_http1_str_pair_t; + +typedef KIT_DA(kit_http1_str_pair_t) kit_http1_str_map_t; + +typedef struct { + kit_str_t str; + i64 position; +} kit_http1_tok_t; + +typedef struct { + kit_str_t protocol; + kit_str_t host; + kit_str_t port; + kit_str_t address; + kit_str_t query_string; + kit_str_t hash; + kit_http1_str_map_t parameters; +} kit_http1_uri_t; + +typedef struct { + i8 success; + kit_str_builder_t protocol; + kit_str_builder_t response; + kit_str_builder_t response_str; + kit_http1_str_map_t header; + kit_str_builder_t header_str; + kit_str_builder_t body; +} kit_http1_response_t; + +#ifdef __GNUC__ +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-function" +# pragma GCC diagnostic ignored "-Wunknown-pragmas" +#endif + +static kit_str_t kit_http1_tok_tail(kit_http1_tok_t *tok) { + assert(tok != NULL); + + if (tok == NULL) + return (kit_str_t) { .size = 0, .values = NULL }; + + i64 previous_position = tok->position; + tok->position = tok->str.size; + + return (kit_str_t) { .size = tok->position - previous_position, + .values = tok->str.values + + previous_position }; +} + +static kit_str_t kit_http1_tok_next(kit_http1_tok_t *tok, + kit_str_t search, + i8 return_tail) { + assert(tok != NULL); + if (tok == NULL) + return (kit_str_t) { .size = 0, .values = NULL }; + + i64 hit = tok->position; + + while (hit + search.size <= tok->str.size) { + kit_str_t s = { .size = search.size, + .values = tok->str.values + hit }; + if (KIT_AR_EQUAL(s, search)) + break; + } + + if (hit + search.size > tok->str.size) { + if (return_tail) + return kit_http1_tok_tail(tok); + else + return (kit_str_t) { .size = 0, .values = NULL }; + } + + i64 previous_position = tok->position; + tok->position = hit + search.size; + + return (kit_str_t) { .size = hit - previous_position, + .values = tok->str.values + + previous_position }; +} + +// TODO +// - Return error status +static void kit_http1_uri_init(kit_http1_uri_t *uri, kit_str_t input, + kit_allocator_t *alloc) { + static const kit_str_t port_80 = { .size = 2, .values = "80" }; + + assert(uri != NULL); + if (uri == NULL) + return; + + memset(uri, 0, sizeof *uri); + + kit_http1_tok_t input_tok = { .str = input, .position = 0 }; + + uri->protocol = kit_http1_tok_next(&input_tok, SZ("://"), 0); + kit_str_t host_port_str = kit_http1_tok_next(&input_tok, SZ("/"), + 0); + + // FIXME + // Handle invalid host port error + assert(host_port_str.size > 0); + if (host_port_str.size == 0) + return; + + kit_http1_tok_t host_port_tok = { .str = host_port_str, + .position = 0 }; + + uri->host = kit_http1_tok_next( + &host_port_tok, + host_port_str.values[0] == '[' ? SZ("]:") : SZ(":"), 1); + + if (uri->host.values[0] == '[') + uri->host = (kit_str_t) { .size = uri->host.size - 1, + .values = uri->host.values + 1 }; + + // TODO + // - HTTPS default port 443 + uri->port = kit_http1_tok_tail(&host_port_tok); + if (uri->port.size == 0) + uri->port = port_80; + + uri->address = kit_http1_tok_next(&input_tok, SZ("?"), 1); + uri->query_string = kit_http1_tok_next(&input_tok, SZ("#"), 1); + + uri->hash = kit_http1_tok_tail(&input_tok); + + KIT_DA_INIT(uri->parameters, 0, alloc); + + kit_http1_tok_t query_tok = { + .str = { .size = uri->query_string.size, + .values = uri->query_string.values }, + .position = 0 + }; + + for (;;) { + kit_str_t key = kit_http1_tok_next(&query_tok, SZ("="), 0); + if (key.size == 0) + break; + kit_str_t value = kit_http1_tok_next(&query_tok, SZ("&"), 1); + + i64 index = uri->parameters.size; + + KIT_DA_RESIZE(uri->parameters, index + 1); + + assert(uri->parameters.size == index + 1); + if (uri->parameters.size != index + 1) + // FIXME + // Handle bad alloc error + break; + + uri->parameters.values[index] = (kit_http1_str_pair_t) { + .key = key, .value = value + }; + } +} + +static void kit_http1_uri_destroy(kit_http1_uri_t *uri) { + assert(uri != NULL); + if (uri == NULL) + return; + + KIT_DA_DESTROY(uri->parameters); + + memset(uri, 0, sizeof *uri); +} + +static kit_str_t kit_http1_method_to_str(i32 method) { + static kit_str_t methods[] = { { .size = 7, .values = "OPTIONS" }, + { .size = 3, .values = "GET" }, + { .size = 4, .values = "HEAD" }, + { .size = 4, .values = "POST" }, + { .size = 3, .values = "PUT" }, + { .size = 6, .values = "DELETE" }, + { .size = 5, .values = "TRACE" }, + { .size = 7, .values = "CONNECT" } }; + + assert(method >= 0 && method < (i32) (sizeof methods / sizeof *methods)); + if (method < 0 || method >= (i32) (sizeof methods / sizeof *methods)) + return (kit_str_t) { .size = 0, .values = NULL }; + + return methods[method]; +} + +// TODO +// - Return error status +static socket_t kit_http1_connect_to_uri(kit_http1_uri_t *uri) { + assert(uri != NULL); + if (uri == NULL) + return INVALID_SOCKET; + + struct addrinfo hints, *result, *rp; + + memset(&hints, 0, sizeof hints); + + hints.ai_family = AF_UNSPEC; + hints.ai_socktype = SOCK_STREAM; + + char host_str[128]; + char port_str[128]; + + assert(uri->host.size < (i64) sizeof host_str); + memcpy(host_str, uri->host.values, uri->host.size); + host_str[uri->host.size] = '\0'; + + assert(uri->port.size < (i64) sizeof port_str); + memcpy(port_str, uri->port.values, uri->port.size); + port_str[uri->port.size] = '\0'; + + i32 getaddrinfo_result = getaddrinfo(host_str, port_str, &hints, + &result); + + if (getaddrinfo_result != 0) + return INVALID_SOCKET; + + socket_t fd = INVALID_SOCKET; + + for (rp = result; rp != NULL; rp = rp->ai_next) { + fd = socket(rp->ai_family, rp->ai_socktype, rp->ai_protocol); + + if (fd == INVALID_SOCKET) + continue; + + i32 connect_result = connect(fd, rp->ai_addr, + (socklen_t) rp->ai_addrlen); + + if (connect_result == -1) { + closesocket(fd); + fd = INVALID_SOCKET; + continue; + } + + break; + } + + freeaddrinfo(result); + + return fd; +} + +// TODO +// - Return error status +static kit_str_builder_t kit_http1_buffered_read( + socket_t fd, kit_allocator_t *alloc) { + kit_str_builder_t buf; + KIT_DA_INIT(buf, KIT_HTTP1_BUFFER_SIZE, alloc); + + // FIXME + // Handle bad alloc error + assert(buf.size == KIT_HTTP1_BUFFER_SIZE); + if (buf.size != KIT_HTTP1_BUFFER_SIZE) + return buf; + + i64 offset = 0; + + for (;;) { + i64 chunk = buf.size - offset; + i64 n = recv(fd, buf.values + offset, (socklen_t) chunk, 0); + if (n < chunk) + break; + offset += n; + KIT_DA_RESIZE(buf, offset + KIT_HTTP1_BUFFER_SIZE); + + // FIXME + // Handle bad alloc error + assert(buf.size == offset + KIT_HTTP1_BUFFER_SIZE); + if (buf.size != offset + KIT_HTTP1_BUFFER_SIZE) + break; + } + + return buf; +} + +// TODO +// - Return error status +static kit_http1_response_t kit_http1_request( + i32 method, kit_http1_uri_t *uri, kit_str_t body, + kit_allocator_t *alloc) { + + socket_t fd = kit_http1_connect_to_uri(uri); + + assert(fd != INVALID_SOCKET); + if (fd == INVALID_SOCKET) { + kit_http1_response_t res; + memset(&res, 0, sizeof res); + res.success = 0; + return res; + } + + kit_str_builder_t req; + + // reserve + KIT_DA_INIT(req, 512, alloc); + + assert(req.size == 512); + if (req.size != 512) { + // bad alloc + // + + closesocket(fd); + + kit_http1_response_t res; + memset(&res, 0, sizeof res); + res.success = 0; + return res; + } + + req.size = 0; + + // FIXME + // Handle errors + // + + kit_str_append(&req, kit_http1_method_to_str(method)); + kit_str_append(&req, SZ(" /")); + kit_str_append(&req, uri->address); + kit_str_append(&req, + uri->query_string.size == 0 ? SZ("") : SZ("?")); + kit_str_append(&req, uri->query_string); + kit_str_append(&req, SZ(" HTTP/1.1")); + kit_str_append(&req, SZ(KIT_HTTP1_NEWLINE)); + + kit_str_append(&req, SZ("Host: ")); + kit_str_append(&req, uri->host); + kit_str_append(&req, SZ(":")); + kit_str_append(&req, uri->port); + kit_str_append(&req, SZ(KIT_HTTP1_NEWLINE)); + + kit_str_append(&req, SZ("Accept: */*")); + kit_str_append(&req, SZ(KIT_HTTP1_NEWLINE)); + + kit_str_append( + &req, + SZ("Content-Type: text/plain; version=0.0.4; charset=utf-8")); + kit_str_append(&req, SZ(KIT_HTTP1_NEWLINE)); + + // FIXME + // Use our own print instead + char content_length_str[11]; + sprintf(content_length_str, "%lld", body.size); + + kit_str_append(&req, SZ("Content-Length: ")); + kit_str_append(&req, + (kit_str_t) { .size = strlen(content_length_str), + .values = content_length_str }); + kit_str_append(&req, SZ(KIT_HTTP1_NEWLINE)); + + kit_str_append(&req, SZ(KIT_HTTP1_NEWLINE)); + kit_str_append(&req, body); + + // Append '\0' at the end + // + { + i64 n = req.size; + KIT_DA_RESIZE(req, n + 1); + + assert(req.size == n + 1); + if (req.size != n + 1) { + KIT_DA_DESTROY(req); + closesocket(fd); + + kit_http1_response_t res; + memset(&res, 0, sizeof res); + res.success = 0; + return res; + } + + req.size = n; + req.values[n] = '\0'; + } + + i64 req_size = req.size; + i64 n = send(fd, req.values, (socklen_t) req.size, 0); + + KIT_DA_DESTROY(req); + + if (n != req_size) { + // send failed + // + + closesocket(fd); + + kit_http1_response_t res; + memset(&res, 0, sizeof res); + res.success = 0; + return res; + } + + kit_str_builder_t buffer = kit_http1_buffered_read(fd, alloc); + + closesocket(fd); + + kit_http1_response_t res; + memset(&res, 0, sizeof res); + res.success = 1; + + kit_http1_tok_t buf_tok = { .str = { .size = buffer.size, + .values = buffer.values }, + .position = 0 }; + + res.protocol = kit_str_build( + kit_http1_tok_next(&buf_tok, SZ(KIT_HTTP1_SPACE), 0), alloc); + res.response = kit_str_build( + kit_http1_tok_next(&buf_tok, SZ(KIT_HTTP1_SPACE), 0), alloc); + res.response_str = kit_str_build( + kit_http1_tok_next(&buf_tok, SZ(KIT_HTTP1_NEWLINE), 0), alloc); + + res.header_str = kit_str_build( + kit_http1_tok_next(&buf_tok, + SZ(KIT_HTTP1_NEWLINE KIT_HTTP1_NEWLINE), 0), + alloc); + + res.body = kit_str_build(kit_http1_tok_tail(&buf_tok), alloc); + + kit_http1_tok_t header_tok = { + .str = (kit_str_t) { .size = res.header_str.size, + .values = res.header_str.values }, + .position = 0 + }; + + KIT_DA_INIT(res.header, 0, alloc); + + for (;;) { + kit_str_t key = kit_http1_tok_next( + &header_tok, SZ(KIT_HTTP1_HEADER_SEPARATOR), 0); + if (key.size == 0) + break; + kit_str_t value = kit_http1_tok_next(&header_tok, + SZ(KIT_HTTP1_NEWLINE), 1); + + i64 index = res.header.size; + + KIT_DA_RESIZE(res.header, index + 1); + + assert(res.header.size == index + 1); + if (res.header.size != index + 1) { + // FIXME + // Handle bad alloc error + res.success = 0; + break; + } + + res.header.values[index] = (kit_http1_str_pair_t) { + .key = key, .value = value + }; + } + + return res; +} + +static void kit_http1_response_destroy( + kit_http1_response_t *response) { + assert(response != NULL); + if (response == NULL) + return; + + KIT_DA_DESTROY(response->protocol); + KIT_DA_DESTROY(response->response); + KIT_DA_DESTROY(response->response_str); + KIT_DA_DESTROY(response->header); + KIT_DA_DESTROY(response->header_str); + KIT_DA_DESTROY(response->body); + + memset(response, 0, sizeof *response); +} + +#ifdef __GNUC__ +# pragma GCC diagnostic pop +#endif + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/kit/input_buffer.c b/kit/input_buffer.c new file mode 100644 index 0000000..1f3e274 --- /dev/null +++ b/kit/input_buffer.c @@ -0,0 +1,360 @@ +#include "input_buffer.h" + +#include <assert.h> +#include <string.h> + +enum { KIT_IB_CACHE_SIZE = 256 }; + +static s32 kit_buf_adjust_(kit_input_buffer_t *buf, i64 size) { + assert(buf != NULL); + assert(size >= 0); + + if (buf == NULL) + return KIT_ERROR_INTERNAL; + + i64 offset = buf->data.size; + + if (offset >= size) + return KIT_OK; + + DA_RESIZE(buf->data, size); + if (buf->data.size != size) + return KIT_ERROR_OUT_OF_MEMORY; + + str_t destination = { .size = size - offset, + .values = buf->data.values + offset }; + i64 n = IS_READ(buf->upstream, destination); + + DA_RESIZE(buf->data, offset + n); + if (buf->data.size != offset + n) + return KIT_ERROR_OUT_OF_MEMORY; + + return KIT_OK; +} + +kit_input_buffer_t kit_ib_init(is_handle_t upstream, + kit_allocator_t *alloc) { + kit_input_buffer_t buf; + memset(&buf, 0, sizeof buf); + + buf.upstream = upstream; + DA_INIT(buf.data, 0, alloc); + + return buf; +} + +void kit_ib_destroy(kit_input_buffer_t *buf) { + assert(buf != NULL); + if (buf == NULL) + return; + + DA_DESTROY(buf->data); + memset(buf, 0, sizeof *buf); +} + +kit_ib_token_t kit_ib_token(kit_input_buffer_t *buf) { + return (kit_ib_token_t) { + .status = KIT_OK, .offset = 0, .size = 0, .buffer = buf + }; +} + +kit_str_t kit_ib_str(kit_ib_token_t tok) { + assert(tok.buffer != NULL); + + if (tok.buffer == NULL || tok.buffer->data.values == NULL) + return (str_t) { .size = 0, .values = NULL }; + + return (str_t) { .size = tok.size, + .values = tok.buffer->data.values + tok.offset }; +} + +kit_ib_token_t kit_ib_read(kit_ib_token_t tok, i64 size) { + assert(tok.buffer != NULL); + + kit_ib_token_t next = tok; + + next.offset = tok.offset + tok.size; + next.size = 0; + + if (tok.status != KIT_OK) + return next; + + if (tok.buffer == NULL) { + next.status = KIT_ERROR_INVALID_ARGUMENT; + return next; + } + + s32 s = kit_buf_adjust_(tok.buffer, tok.offset + tok.size + size); + + if (s != KIT_OK) { + next.status = s; + return next; + } + + assert(tok.buffer->data.values != NULL); + + if (tok.buffer->data.values == NULL) { + next.status = KIT_ERROR_INTERNAL; + return next; + } + + next.size = size < tok.buffer->data.size - tok.offset - tok.size + ? size + : tok.buffer->data.size - tok.offset - tok.size; + + return next; +} + +#define IB_CACHE_INIT_(res_) \ + str_builder_t cache_dynamic; \ + memset(&cache_dynamic, 0, sizeof cache_dynamic); \ + char cache_static[KIT_IB_CACHE_SIZE]; \ + \ + do { \ + if (data.size > 0) { \ + if (data.size < KIT_IB_CACHE_SIZE) { \ + memcpy(cache_static, data.values, data.size); \ + data.values = cache_static; \ + } else { \ + DA_INIT(cache_dynamic, data.size, tok.buffer->data.alloc); \ + if (cache_dynamic.size != data.size) { \ + (res_).status |= KIT_ERROR_OUT_OF_MEMORY; \ + return (res_); \ + } \ + memcpy(cache_dynamic.values, data.values, data.size); \ + data.values = cache_dynamic.values; \ + } \ + } \ + } while (0) + +#define IB_CACHE_CLEANUP_() \ + do { \ + if (cache_dynamic.values != NULL) \ + DA_DESTROY(cache_dynamic); \ + } while (0) + +kit_ib_token_t kit_ib_any(kit_ib_token_t tok, str_t data) { + assert(tok.buffer != NULL); + + kit_ib_token_t next = tok; + + next.offset = tok.offset + tok.size; + next.size = 0; + + if (tok.status != KIT_OK) + return next; + + if (tok.buffer == NULL) { + next.status = KIT_ERROR_INVALID_ARGUMENT; + return next; + } + + IB_CACHE_INIT_(next); + + for (;; ++next.size) { + s32 s = kit_buf_adjust_(tok.buffer, + tok.offset + tok.size + next.size + 1); + + if (s != KIT_OK) { + next.status = s; + return next; + } + + assert(tok.buffer->data.values != NULL); + + if (tok.buffer->data.values == NULL) { + next.status = KIT_ERROR_INTERNAL; + return next; + } + + if (tok.offset + tok.size + next.size >= tok.buffer->data.size) + break; + + i8 found = 0; + + for (i64 i = 0; i < data.size; i++) + if (data.values[i] == + tok.buffer->data.values[next.offset + next.size]) { + found = 1; + break; + } + + if (!found) + break; + } + + IB_CACHE_CLEANUP_(); + + return next; +} + +kit_ib_token_t kit_ib_none(kit_ib_token_t tok, str_t data) { + assert(tok.buffer != NULL); + + kit_ib_token_t next = tok; + + next.offset = tok.offset + tok.size; + next.size = 0; + + if (tok.status != KIT_OK) + return next; + + if (tok.buffer == NULL) { + next.status = KIT_ERROR_INVALID_ARGUMENT; + return next; + } + + IB_CACHE_INIT_(next); + + for (;; ++next.size) { + s32 s = kit_buf_adjust_(tok.buffer, + tok.offset + tok.size + next.size + 1); + + if (s != KIT_OK) { + next.status = s; + return next; + } + + assert(tok.buffer->data.values != NULL); + + if (tok.buffer->data.values == NULL) { + next.status = KIT_ERROR_INTERNAL; + return next; + } + + if (tok.offset + tok.size + next.size >= tok.buffer->data.size) + break; + + i8 found = 0; + + for (i64 i = 0; i < data.size; i++) + if (data.values[i] == + tok.buffer->data.values[next.offset + next.size]) { + found = 1; + break; + } + + if (found) + break; + } + + IB_CACHE_CLEANUP_(); + + return next; +} + +kit_ib_token_t kit_ib_exact(kit_ib_token_t tok, str_t data) { + kit_ib_token_t res = tok; + + res.offset = tok.offset + tok.size; + res.size = 0; + + IB_CACHE_INIT_(res); + + res = kit_ib_read(tok, data.size); + if (!AR_EQUAL(kit_ib_str(res), data)) + res.status = KIT_PARSING_FAILED; + + IB_CACHE_CLEANUP_(); + + return res; +} + +kit_ib_token_t kit_ib_until(kit_ib_token_t tok, str_t data) { + assert(tok.buffer != NULL); + + kit_ib_token_t next = tok; + + next.offset = tok.offset + tok.size; + next.size = 0; + + if (tok.status != KIT_OK) + return next; + + if (tok.buffer == NULL) { + next.status = KIT_ERROR_INVALID_ARGUMENT; + return next; + } + + IB_CACHE_INIT_(next); + + for (;; ++next.size) { + s32 s = kit_buf_adjust_(tok.buffer, + tok.offset + tok.size + next.size + 1); + + if (s != KIT_OK) { + next.status = s; + return next; + } + + assert(tok.buffer->data.values != NULL); + + if (tok.buffer->data.values == NULL) { + next.status = KIT_ERROR_INTERNAL; + return next; + } + + if (tok.offset + tok.size + next.size >= tok.buffer->data.size) + break; + + if (next.size + 1 >= data.size && + AR_EQUAL(kit_str(data.size, tok.buffer->data.values + + (next.offset + next.size + 1 - + data.size)), + data)) { + next.size -= data.size - 1; + break; + } + } + + IB_CACHE_CLEANUP_(); + + return next; +} + +kit_ib_token_t kit_ib_while(kit_ib_token_t tok, + kit_ib_read_condition_fn condition, + void *context) { + assert(tok.buffer != NULL); + + kit_ib_token_t next = tok; + + next.offset = tok.offset + tok.size; + next.size = 0; + + if (tok.status != KIT_OK) + return next; + + if (tok.buffer == NULL) { + next.status = KIT_ERROR_INVALID_ARGUMENT; + return next; + } + + for (;; ++next.size) { + s32 s = kit_buf_adjust_(tok.buffer, + tok.offset + tok.size + next.size + 1); + + if (s != KIT_OK) { + next.status = s; + return next; + } + + assert(tok.buffer->data.values != NULL); + + if (tok.buffer->data.values == NULL) { + next.status = KIT_ERROR_INTERNAL; + return next; + } + + if (tok.offset + tok.size + next.size >= tok.buffer->data.size) + break; + + if (condition == NULL || + !condition(kit_str(next.size + 1, + tok.buffer->data.values + next.offset), + context)) + break; + } + + return next; +} diff --git a/kit/input_buffer.h b/kit/input_buffer.h new file mode 100644 index 0000000..2a490c0 --- /dev/null +++ b/kit/input_buffer.h @@ -0,0 +1,66 @@ +#ifndef KIT_INPUT_BUFFER_H +#define KIT_INPUT_BUFFER_H + +#include "string_builder.h" +#include "input_stream.h" + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct { + kit_is_handle_t upstream; + kit_str_builder_t data; +} kit_input_buffer_t; + +typedef struct { + s32 status; + i64 offset; + i64 size; + kit_input_buffer_t *buffer; +} kit_ib_token_t; + +typedef b8 (*kit_ib_read_condition_fn)(kit_str_t data, void *context); + +kit_input_buffer_t kit_ib_init(kit_is_handle_t upstream, + kit_allocator_t *alloc); + +void kit_ib_destroy(kit_input_buffer_t *buf); + +kit_ib_token_t kit_ib_token(kit_input_buffer_t *buf); + +kit_str_t kit_ib_str(kit_ib_token_t tok); + +kit_ib_token_t kit_ib_read(kit_ib_token_t tok, i64 size); + +kit_ib_token_t kit_ib_any(kit_ib_token_t tok, kit_str_t data); + +kit_ib_token_t kit_ib_none(kit_ib_token_t tok, kit_str_t data); + +kit_ib_token_t kit_ib_exact(kit_ib_token_t tok, kit_str_t data); + +kit_ib_token_t kit_ib_until(kit_ib_token_t tok, kit_str_t data); + +kit_ib_token_t kit_ib_while(kit_ib_token_t buf, + kit_ib_read_condition_fn condition, + void *context); + +#ifdef __cplusplus +} +#endif + +#define input_buffer_t kit_input_buffer_t +#define ib_token_t kit_ib_token_t +#define ib_read_condition_fn kit_ib_read_condition_fn +#define ib_init kit_ib_init +#define ib_destroy kit_ib_destroy +#define ib_token kit_ib_token +#define ib_str kit_ib_str +#define ib_read kit_ib_read +#define ib_any kit_ib_any +#define ib_none kit_ib_none +#define ib_exact kit_ib_exact +#define ib_until kit_ib_until +#define ib_while kit_ib_while + +#endif diff --git a/kit/input_stream.c b/kit/input_stream.c new file mode 100644 index 0000000..369cf64 --- /dev/null +++ b/kit/input_stream.c @@ -0,0 +1,103 @@ +#include "input_stream.h" + +#include <string.h> + +enum { KIT_INPUT_STREAM_STR, KIT_INPUT_STREAM_FILE }; + +typedef struct { + i64 type; + kit_allocator_t *alloc; +} kit_is_state_basic_t; + +typedef struct { + i64 type; + kit_allocator_t *alloc; + kit_str_t string; +} kit_is_state_str_t; + +typedef struct { + i64 type; + kit_allocator_t *alloc; + FILE *file; +} kit_is_state_file_t; + +static int kit_is_check_type_(void *state, i64 type) { + kit_is_state_basic_t *basic = (kit_is_state_basic_t *) state; + return basic != NULL && basic->type == type; +} + +static i64 kit_read_str_(void *state, kit_str_t destination) { + if (!kit_is_check_type_(state, KIT_INPUT_STREAM_STR)) + return 0; + + kit_is_state_str_t *str = (kit_is_state_str_t *) state; + i64 size = destination.size < str->string.size ? destination.size + : str->string.size; + memcpy(destination.values, str->string.values, size); + str->string.values += size; + str->string.size -= size; + return size; +} + +static i64 kit_read_file_(void *state, kit_str_t destination) { + if (!kit_is_check_type_(state, KIT_INPUT_STREAM_FILE)) + return 0; + + kit_is_state_file_t *f = (kit_is_state_file_t *) state; + + if (f->file == NULL || feof(f->file)) + return 0; + + i64 size = (i64) fread(destination.values, 1, destination.size, + f->file); + + if (size <= 0) + return 0; + + return size; +} + +kit_is_handle_t kit_is_wrap_string(kit_str_t string, + kit_allocator_t *alloc) { + kit_is_handle_t in; + memset(&in, 0, sizeof in); + + kit_is_state_str_t *state = (kit_is_state_str_t *) + kit_alloc_dispatch(alloc, KIT_ALLOCATE, + sizeof(kit_is_state_str_t), 0, NULL); + if (state != NULL) { + memset(state, 0, sizeof *state); + state->type = KIT_INPUT_STREAM_STR; + state->string = string; + state->alloc = alloc; + in.state = state; + in.read = kit_read_str_; + } + return in; +} + +kit_is_handle_t kit_is_wrap_file(FILE *f, kit_allocator_t *alloc) { + kit_is_handle_t in; + memset(&in, 0, sizeof in); + + kit_is_state_file_t *state = (kit_is_state_file_t *) + kit_alloc_dispatch(alloc, KIT_ALLOCATE, + sizeof(kit_is_state_file_t), 0, NULL); + + if (state != NULL) { + memset(state, 0, sizeof *state); + state->type = KIT_INPUT_STREAM_FILE; + state->file = f; + state->alloc = alloc; + in.state = state; + in.read = kit_read_file_; + } + + return in; +} + +void kit_is_destroy(kit_is_handle_t in) { + kit_is_state_basic_t *basic = (kit_is_state_basic_t *) in.state; + if (basic != NULL) + kit_alloc_dispatch(basic->alloc, KIT_DEALLOCATE, 0, 0, in.state); +} diff --git a/kit/input_stream.h b/kit/input_stream.h new file mode 100644 index 0000000..3442ee4 --- /dev/null +++ b/kit/input_stream.h @@ -0,0 +1,41 @@ +#ifndef KIT_INPUT_STREAM_H +#define KIT_INPUT_STREAM_H + +#include "allocator.h" +#include "string_ref.h" + +#include <stdio.h> + +#ifdef __cplusplus +extern "C" { +#endif + +typedef i64 (*kit_is_read_fn)(void *state, kit_str_t destination); + +typedef struct { + void *state; + kit_is_read_fn read; +} kit_is_handle_t; + +kit_is_handle_t kit_is_wrap_string(kit_str_t string, + kit_allocator_t *alloc); + +kit_is_handle_t kit_is_wrap_file(FILE *f, kit_allocator_t *alloc); + +void kit_is_destroy(kit_is_handle_t in); + +#define KIT_IS_READ(in, destination) \ + (in).read((in).state, (destination)) + +#ifdef __cplusplus +} +#endif + +#define is_read_fn kit_is_read_fn +#define is_handle_t kit_is_handle_t +#define is_wrap_string kit_is_wrap_string +#define is_wrap_file kit_is_wrap_file +#define is_destroy kit_is_destroy +#define IS_READ KIT_IS_READ + +#endif diff --git a/kit/lower_bound.h b/kit/lower_bound.h new file mode 100644 index 0000000..eb437ed --- /dev/null +++ b/kit/lower_bound.h @@ -0,0 +1,42 @@ +#ifndef KIT_LOWER_BOUND_H +#define KIT_LOWER_BOUND_H + +#include "types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +#define KIT_LOWER_BOUND_INL(return_val, size, ...) \ + do { \ + i64 position_ = 0; \ + i64 count_ = (size); \ + while (count_ > 0) { \ + i64 delta_ = count_ / 2; \ + i64 index_ = position_ + delta_; \ + if (__VA_ARGS__) { \ + position_ += delta_ + 1; \ + count_ -= delta_ + 1; \ + } else \ + count_ = delta_; \ + } \ + (return_val) = position_; \ + } while (0) + +#define KIT_LOWER_BOUND(return_val, array, value, op) \ + KIT_LOWER_BOUND_INL(return_val, (array).size, \ + (op) ((array).values[index_], (value))) + +#define KIT_LOWER_BOUND_REF(return_val, array, value, op) \ + KIT_LOWER_BOUND_INL(return_val, (array).size, \ + (op) ((array).values + index_, (value))) + +#ifdef __cplusplus +} +#endif + +#define LOWER_BOUND_INL KIT_LOWER_BOUND_INL +#define LOWER_BOUND KIT_LOWER_BOUND +#define LOWER_BOUND_REF KIT_LOWER_BOUND_REF + +#endif diff --git a/kit/math.h b/kit/math.h new file mode 100644 index 0000000..d7044f1 --- /dev/null +++ b/kit/math.h @@ -0,0 +1,780 @@ +#ifndef KIT_MATH_H +#define KIT_MATH_H + +#include "types.h" + +#ifndef _USE_MATH_DEFINES +# define _USE_MATH_DEFINES +#endif +#include <math.h> + +#include <assert.h> +#include <string.h> + +// TODO +// - Gamma correction. +// - Custom prefixes +// - Unnecesary XYZ scaling. + +#ifdef __cplusplus +extern "C" { +#endif + +#ifndef M_PI +# define M_PI 3.14159265358979323846 +#endif + +#ifndef M_E +# define M_E 2.71828182845904523536 +#endif + +#ifndef KIT_VEC_TYPE +# define KIT_VEC_TYPE f32 +#endif + +#define KIT_EPSILON .00001 + +#define KIT_COLOR_REF_X 95.047f +#define KIT_COLOR_REF_Y 100.0f +#define KIT_COLOR_REF_Z 108.883f + +typedef KIT_VEC_TYPE vec_t; + +typedef struct { + vec_t v[2]; +} vec2_t; + +typedef struct { + vec_t v[3]; +} vec3_t; + +typedef struct { + vec_t v[4]; +} vec4_t, quat_t; + +typedef struct { + vec_t v[9]; +} mat3_t; + +typedef struct { + vec_t v[16]; +} mat4_t; + +#ifdef __GNUC__ +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-function" +# pragma GCC diagnostic ignored "-Wunknown-pragmas" +# pragma GCC push_options +# pragma GCC optimize("O3") +#endif + +static vec2_t vec2(vec_t x, vec_t y) { + vec2_t v = { { x, y } }; + return v; +} + +static vec3_t vec3(vec_t x, vec_t y, vec_t z) { + vec3_t v = { { x, y, z } }; + return v; +} + +static vec4_t vec4(vec_t x, vec_t y, vec_t z, vec_t w) { + vec4_t v = { { x, y, z, w } }; + return v; +} + +static mat3_t mat3( // + vec_t _00, vec_t _01, vec_t _02, // + vec_t _10, vec_t _11, vec_t _12, // + vec_t _20, vec_t _21, vec_t _22) { + mat3_t m = { { + _00, _01, _02, // + _10, _11, _12, // + _20, _21, _22 // + } }; + return m; +} + +static mat4_t mat4(vec_t _00, vec_t _01, vec_t _02, vec_t _03, + vec_t _10, vec_t _11, vec_t _12, vec_t _13, + vec_t _20, vec_t _21, vec_t _22, vec_t _23, + vec_t _30, vec_t _31, vec_t _32, vec_t _33) { + mat4_t m = { { + _00, _01, _02, _03, // + _10, _11, _12, _13, // + _20, _21, _22, _23, // + _30, _31, _32, _33 // + } }; + return m; +} + +static mat3_t vec3_to_mat3(vec3_t a, vec3_t b, vec3_t c) { + return mat3(a.v[0], a.v[1], a.v[2], // + b.v[0], b.v[1], b.v[2], // + c.v[0], c.v[1], c.v[2]); +} + +static mat4_t vec4_to_mat4(vec4_t a, vec4_t b, vec4_t c, vec4_t d) { + return mat4(a.v[0], a.v[1], a.v[2], a.v[3], // + b.v[0], b.v[1], b.v[2], b.v[3], // + c.v[0], c.v[1], c.v[2], c.v[3], // + d.v[0], d.v[1], d.v[2], d.v[3]); +} + +static mat4_t mat3_to_mat4(mat3_t a) { + return mat4(a.v[0], a.v[1], a.v[2], 0.f, // + a.v[3], a.v[4], a.v[5], 0.f, // + a.v[6], a.v[7], a.v[8], 0.f, // + 0.f, 0.f, 0.f, 1.f); +} + +static mat3_t mat4_to_mat3(mat4_t a) { + return mat3(a.v[0], a.v[1], a.v[2], // + a.v[4], a.v[5], a.v[6], // + a.v[8], a.v[9], a.v[10]); +} + +static quat_t quat(vec_t x, vec_t y, vec_t z, vec_t w) { + return vec4(x, y, z, w); +} + +static quat_t vec3_to_quat(vec3_t v, vec_t w) { + return quat(v.v[0], v.v[1], v.v[2], w); +} + +static vec3_t vec4_to_vec3(vec4_t a) { + return vec3(a.v[0], a.v[1], a.v[2]); +} + +static vec3_t quat_to_vec3(quat_t a) { + return vec4_to_vec3(a); +} + +static vec_t vec_abs(vec_t x) { + return fabs(x); +} + +static vec_t vec_min(vec_t x, vec_t y) { + return fmin(x, y); +} + +static vec_t vec_max(vec_t x, vec_t y) { + return fmax(x, y); +} + +static vec_t vec_clamp(vec_t x, vec_t x0, vec_t x1) { + return fmax(x0, fmin(x, x1)); +} + +static vec3_t vec3_clamp(vec3_t x, vec3_t x0, vec3_t x1) { + return vec3(vec_clamp(x.v[0], x0.v[0], x1.v[0]), + vec_clamp(x.v[1], x0.v[1], x1.v[1]), + vec_clamp(x.v[2], x0.v[2], x1.v[2])); +} + +static vec_t vec_sqrt(vec_t x) { + return sqrtf(x); +} + +static vec_t vec_pow(vec_t x, vec_t y) { + return powf(x, y); +} + +static vec_t vec_sin(vec_t x) { + return sinf(x); +} + +static vec_t vec_cos(vec_t x) { + return cosf(x); +} + +static vec_t vec_asin(vec_t x) { + return asinf(x); +} + +static vec_t vec_acos(vec_t x) { + return acosf(x); +} + +static vec_t vec_atan(vec_t x) { + return atanf(x); +} + +static vec_t vec_atan2(vec_t y, vec_t x) { + return atan2f(y, x); +} + +static vec3_t vec3_neg(vec3_t a) { + return vec3(-a.v[0], -a.v[1], -a.v[2]); +} + +static vec3_t vec3_add(vec3_t a, vec3_t b) { + return vec3(a.v[0] + b.v[0], a.v[1] + b.v[1], a.v[2] + b.v[2]); +} + +static vec3_t vec3_add3(vec3_t a, vec3_t b, vec3_t c) { + return vec3(a.v[0] + b.v[0] + c.v[0], a.v[1] + b.v[1] + c.v[1], + a.v[2] + b.v[2] + c.v[2]); +} + +static vec3_t vec3_sub(vec3_t a, vec3_t b) { + return vec3(a.v[0] - b.v[0], a.v[1] - b.v[1], a.v[2] - b.v[2]); +} + +static vec3_t vec3_mul(vec3_t v, vec_t x) { + return vec3(v.v[0] * x, v.v[1] * x, v.v[2] * x); +} + +static vec_t vec3_dot(vec3_t a, vec3_t b) { + return a.v[0] * b.v[0] + a.v[1] * b.v[1] + a.v[2] * b.v[2]; +} + +static vec3_t vec3_cross(vec3_t a, vec3_t b) { + return vec3(a.v[1] * b.v[2] - a.v[2] * b.v[1], // + a.v[2] * b.v[0] - a.v[0] * b.v[2], // + a.v[0] * b.v[1] - a.v[1] * b.v[0]); +} + +static vec3_t vec3_normal(vec3_t v) { + vec_t x = v.v[0]; + vec_t y = v.v[1]; + vec_t z = v.v[2]; + + vec_t length_squared = x * x + y * y + z * z; + assert(length_squared >= KIT_EPSILON); + + if (length_squared < KIT_EPSILON) { + vec3_t n = { { 0.f, 0.f, 1.f } }; + return n; + } + + vec_t length = vec_sqrt(length_squared); + vec3_t n = { { x / length, y / length, z / length } }; + + return n; +} + +static vec4_t vec4_neg(vec4_t a) { + return vec4(-a.v[0], -a.v[1], -a.v[2], -a.v[3]); +} + +static vec4_t vec4_add(vec4_t a, vec4_t b) { + return vec4(a.v[0] + b.v[0], a.v[1] + b.v[1], a.v[2] + b.v[2], + a.v[3] + b.v[3]); +} + +static vec4_t vec4_mul(vec4_t v, vec_t x) { + return vec4(v.v[0] * x, v.v[1] * x, v.v[2] * x, v.v[3] * x); +} + +static vec4_t vec4_div(vec4_t v, vec_t x) { + assert(x < KIT_EPSILON); + assert(x > -KIT_EPSILON); + + if (x >= -KIT_EPSILON || x < KIT_EPSILON) + return vec4(0.f, 0.f, 0.f, 0.f); + + return vec4(v.v[0] / x, v.v[1] / x, v.v[2] / x, v.v[3] / x); +} + +static vec_t vec4_dot(vec4_t a, vec4_t b) { + return a.v[0] * b.v[0] + a.v[1] * b.v[1] + a.v[2] * b.v[2] + + a.v[3] * b.v[3]; +} + +static vec4_t vec4_normal(vec4_t v) { + vec_t x = v.v[0]; + vec_t y = v.v[1]; + vec_t z = v.v[2]; + vec_t w = v.v[3]; + + vec_t length_squared = x * x + y * y + z * z + w * w; + assert(length_squared >= KIT_EPSILON); + + if (length_squared < KIT_EPSILON) { + vec4_t n = { { 0.f, 0.f, 0.f, 1.f } }; + return n; + } + + vec_t length = vec_sqrt(length_squared); + vec4_t n = { { x / length, y / length, z / length, w / length } }; + + return n; +} + +static quat_t quat_conjugate(quat_t q) { + return quat(-q.v[0], -q.v[1], -q.v[2], q.v[3]); +} + +static quat_t quat_normal(quat_t q) { + return vec4_normal(q); +} + +static quat_t quat_mul(quat_t left, quat_t right) { + vec_t i0 = left.v[0]; + vec_t j0 = left.v[1]; + vec_t k0 = left.v[2]; + vec_t r0 = left.v[3]; + + vec_t i1 = right.v[0]; + vec_t j1 = right.v[1]; + vec_t k1 = right.v[2]; + vec_t r1 = right.v[3]; + + quat_t q = { { r0 * i1 + i0 * r1 + j0 * k1 - k0 * j1, // + r0 * j1 - i0 * k1 + j0 * r1 + k0 * i1, // + r0 * k1 + i0 * j1 - j0 * i1 + k0 * r1, // + r0 * r1 - i0 * i1 - j0 * j1 - k0 * k1 } }; + + return q; +} + +static quat_t quat_rotation(vec_t angle, vec3_t axis) { + vec_t s = vec_sin(angle / 2.f); + vec_t c = vec_cos(angle / 2.f); + + vec_t x = axis.v[0]; + vec_t y = axis.v[1]; + vec_t z = axis.v[2]; + + quat_t q = { { x * s, y * s, z * s, c } }; + + return q; +} + +static mat3_t mat3_transpose(mat3_t m) { + return mat3(m.v[0], m.v[3], m.v[6], // + m.v[1], m.v[4], m.v[7], // + m.v[2], m.v[5], m.v[8]); +} + +static mat4_t mat4_transpose(mat4_t m) { + return mat4(m.v[0], m.v[4], m.v[8], m.v[12], // + m.v[1], m.v[5], m.v[9], m.v[13], // + m.v[2], m.v[6], m.v[10], m.v[14], // + m.v[3], m.v[7], m.v[11], m.v[15]); +} + +static mat3_t mat3_look_at(vec3_t direction, vec3_t up) { + vec3_t f = vec3_normal(vec3_neg(direction)); + vec3_t s = vec3_normal(vec3_cross(f, up)); + vec3_t u = vec3_cross(s, f); + + return mat3(s.v[0], u.v[0], f.v[0], // + s.v[1], u.v[1], f.v[1], // + s.v[2], u.v[2], f.v[2]); +} + +static vec3_t vec3_rotate(vec3_t v, quat_t rotation) { + vec3_t u = vec3(rotation.v[0], rotation.v[1], rotation.v[2]); + vec_t s = rotation.v[3]; + + return vec3_add3(vec3_mul(u, 2.f * vec3_dot(u, v)), + vec3_mul(v, s * s - vec3_dot(u, u)), + vec3_mul(vec3_cross(u, v), 2.f * s)); +} + +static mat3_t quat_to_mat3(quat_t q) { + vec_t xx = q.v[0] * q.v[0]; + vec_t yy = q.v[1] * q.v[1]; + vec_t zz = q.v[2] * q.v[2]; + vec_t xz = q.v[0] * q.v[2]; + vec_t xy = q.v[0] * q.v[1]; + vec_t yz = q.v[1] * q.v[2]; + vec_t wx = q.v[3] * q.v[0]; + vec_t wy = q.v[3] * q.v[1]; + vec_t wz = q.v[3] * q.v[2]; + + return mat3(1.f - 2.f * (yy + zz), // + 2.f * (xy + wz), // + 2.f * (xz - wy), // + 2.f * (xy - wz), // + 1.f - 2.f * (xx + zz), // + 2.f * (yz + wx), // + 2.f * (xz + wy), // + 2.f * (yz - wx), // + 1.f - 2.f * (xx + yy)); +} + +static quat_t mat3_to_quat(mat3_t m) { + vec_t a = m.v[0] - m.v[4] - m.v[8]; + vec_t b = m.v[4] - m.v[0] - m.v[8]; + vec_t c = m.v[8] - m.v[0] - m.v[4]; + vec_t d = m.v[0] + m.v[4] + m.v[8]; + + int n = 0; + vec_t h = d; + if (a > h) { + h = a; + n = 1; + } + if (b > h) { + h = b; + n = 2; + } + if (c > h) { + h = c; + n = 3; + } + + vec_t s = vec_sqrt(h + 1.f) * .5f; + vec_t k = .25f / s; + + switch (n) { + case 0: + return quat((m.v[5] - m.v[7]) * k, // + (m.v[6] - m.v[2]) * k, // + (m.v[1] - m.v[3]) * k, // + s); + case 1: + return quat(s, // + (m.v[1] + m.v[3]) * k, // + (m.v[6] + m.v[2]) * k, // + (m.v[5] - m.v[7]) * k); + case 2: + return quat((m.v[1] + m.v[3]) * k, // + s, // + (m.v[5] + m.v[7]) * k, // + (m.v[6] - m.v[2]) * k); + case 3: + return quat((m.v[6] + m.v[2]) * k, // + (m.v[5] + m.v[7]) * k, // + s, // + (m.v[1] - m.v[3]) * k); + default:; + } + + assert(0); + return quat(0.f, 0.f, 0.f, 1.f); +} + +static quat_t quat_look_at(vec3_t direction, vec3_t up) { + vec3_t z = vec3_normal(vec3_neg(direction)); + vec3_t right = vec3_cross(up, z); + vec3_t x = vec3_mul( + right, + 1.f / vec_sqrt(vec_max(KIT_EPSILON, vec3_dot(right, right)))); + vec3_t y = vec3_cross(z, x); + + return mat3_to_quat(vec3_to_mat3(x, y, z)); +} + +static mat3_t mat3_mul(mat3_t left, mat3_t right) { + mat3_t m; + memset(&m, 0, sizeof m); + + for (int j = 0; j < 3; j++) + for (int i = 0; i < 3; i++) + for (int k = 0; k < 3; k++) + m.v[j * 3 + i] += left.v[k * 3 + i] * right.v[j * 3 + k]; + + return m; +} + +static mat4_t mat4_mul(mat4_t left, mat4_t right) { + mat4_t m; + memset(&m, 0, sizeof m); + + for (int j = 0; j < 4; j++) + for (int i = 0; i < 4; i++) + for (int k = 0; k < 4; k++) + m.v[j * 4 + i] += left.v[k * 4 + i] * right.v[j * 4 + k]; + + return m; +} + +static mat4_t mat4_move(vec3_t offset) { + vec_t x = offset.v[0]; + vec_t y = offset.v[1]; + vec_t z = offset.v[2]; + + return mat4(1.f, 0.f, 0.f, 0.f, // + 0.f, 1.f, 0.f, 0.f, // + 0.f, 0.f, 1.f, 0.f, // + x, y, z, 1.f); +} + +static mat4_t mat4_scale(vec3_t scale) { + vec_t x = scale.v[0]; + vec_t y = scale.v[1]; + vec_t z = scale.v[2]; + + return mat4(x, 0.f, 0.f, 0.f, // + 0.f, y, 0.f, 0.f, // + 0.f, 0.f, z, 0.f, // + 0.f, 0.f, 0.f, 1.f); +} + +static mat4_t mat4_frustum(vec_t left, vec_t right, vec_t bottom, + vec_t top, vec_t znear, vec_t zfar) { + vec_t t0 = 2.f * znear; + vec_t t1 = right - left; + vec_t t2 = top - bottom; + vec_t t3 = zfar - znear; + + return mat4(t0 / t1, // + 0.f, // + 0.f, // + 0.f, // + 0.f, // + t0 / t2, // + 0.f, // + 0.f, // + (right + left) / t1, // + (top + bottom) / t2, // + (-zfar - znear) / t3, // + -1.f, // + 0.f, // + 0.f, // + (-t0 * zfar) / t3, // + 0.f); +} + +static mat4_t mat4_perspective(vec_t fovy, vec_t aspect_ratio_, + vec_t znear, vec_t zfar) { + vec_t ymax = znear * tanf(fovy); + vec_t xmax = ymax * aspect_ratio_; + + return mat4_frustum(-xmax, xmax, -ymax, ymax, znear, zfar); +} + +static vec_t vec_lerp(vec_t x0, vec_t x1, vec_t t) { + assert(t >= 0.f); + assert(t <= 1.f); + + if (t <= 0.f) + return x0; + if (t >= 1.f) + return x1; + + return x0 + (x1 - x0) * t; +} + +static vec3_t vec3_lerp(vec3_t x0, vec3_t x1, vec_t t) { + return vec3(vec_lerp(x0.v[0], x1.v[0], t), + vec_lerp(x0.v[1], x1.v[1], t), + vec_lerp(x0.v[2], x1.v[2], t)); +} + +static vec4_t vec4_lerp(vec4_t x0, vec4_t x1, vec_t t) { + return vec4( + vec_lerp(x0.v[0], x1.v[0], t), vec_lerp(x0.v[1], x1.v[1], t), + vec_lerp(x0.v[2], x1.v[2], t), vec_lerp(x0.v[3], x1.v[3], t)); +} + +static quat_t quat_slerp(quat_t q0, quat_t q1, vec_t t) { + assert(t >= 0.f); + assert(t <= 1.f); + + if (t <= 0.f) + return q0; + if (t >= 1.f) + return q1; + + quat_t q = q1; + + vec_t cos_theta = vec4_dot(q0, q1); + + if (cos_theta < 0.f) { + q = vec4_neg(q1); + cos_theta = -cos_theta; + } + + if (cos_theta > 1.f - KIT_EPSILON) + return vec4_lerp(q0, q1, t); + + vec_t angle = vec_acos(cos_theta); + + return vec4_div(vec4_add(vec4_mul(q0, vec_sin((1.f - t) * angle)), + vec4_mul(q, vec_sin(t * angle))), + vec_sin(angle)); +} + +static vec3_t rgb_to_xyz(vec3_t rgb) { + // FIXME + // Remove unnecessary x100 scaling. + // + + vec_t red = rgb.v[0]; + vec_t green = rgb.v[1]; + vec_t blue = rgb.v[2]; + + // Gamma correction + // + /* + if (red > 0.04045f) + red = vec_pow(((red + 0.055f) / 1.055f), 2.4f); + else + red = red / 12.92f; + + if (green > 0.04045f) + green = vec_pow(((green + 0.055f) / 1.055f), 2.4f); + else + green = green / 12.92f; + + if (blue > 0.04045f) + blue = vec_pow(((blue + 0.055f) / 1.055f), 2.4f); + else + blue = blue / 12.92f; + */ + + red = red * 100.f; + green = green * 100.f; + blue = blue * 100.f; + + return vec3(red * 0.4124f + green * 0.3576f + blue * 0.1805f, + red * 0.2126f + green * 0.7152f + blue * 0.0722f, + red * 0.0193f + green * 0.1192f + blue * 0.9505f); +} + +static vec3_t xyz_to_rgb(vec3_t xyz) { + // FIXME + // Remove unnecessary x100 scaling. + // + + vec_t x = xyz.v[0] / 100.f; + vec_t y = xyz.v[1] / 100.f; + vec_t z = xyz.v[2] / 100.f; + + vec_t red = x * 3.2406f + (y * -1.5372f) + z * (-0.4986f); + vec_t green = x * (-0.9689f) + y * 1.8758f + z * 0.0415f; + vec_t blue = x * 0.0557f + y * (-0.2040f) + z * 1.0570f; + + // Gamma correction + // + /* + if (red > 0.0031308f) + red = 1.055f * vec_pow(red, (1.0f / 2.4)) - 0.055f; + else + red = 12.92f * red; + + if (green > 0.0031308f) + green = 1.055f * vec_pow(green, (1.0f / 2.4)) - 0.055f; + else + green = 12.92f * green; + + if (blue > 0.0031308f) + blue = 1.055f * vec_pow(blue, (1.0f / 2.4)) - 0.055f; + else + blue = 12.92f * blue; + */ + + return vec3_clamp(vec3(red, green, blue), vec3(0.f, 0.f, 0.f), + vec3(1.f, 1.f, 1.f)); +} + +static vec3_t lab_to_xyz(vec3_t lab) { + // FIXME + // Remove unnecessary x100 scaling. + // + + vec_t lightness = lab.v[0]; + vec_t a = lab.v[1]; + vec_t b = lab.v[2]; + + vec_t y = (lightness + 16.f) / 116.f; + vec_t x = (a / 500.f) + y; + vec_t z = y - (b / 200.f); + + if (vec_pow(y, 3.f) > 0.008856) + y = vec_pow(y, 3.f); + else + y = (y - (16.f / 116.f)) / 7.787f; + + if (vec_pow(x, 3.f) > 0.008856f) + x = vec_pow(x, 3.f); + else + x = (x - (16.f / 116.f)) / 7.787f; + + if (vec_pow(z, 3.f) > 0.008856f) + z = vec_pow(z, 3.f); + else + z = (z - (16.f / 116.f)) / 7.787f; + + return vec3(KIT_COLOR_REF_X * x, KIT_COLOR_REF_Y * y, + KIT_COLOR_REF_Z * z); +} + +static vec3_t xyz_to_lab(vec3_t xyz) { + // FIXME + // Remove unnecessary x100 scaling. + // + + vec_t x = (xyz.v[0] / KIT_COLOR_REF_X); + vec_t y = (xyz.v[1] / KIT_COLOR_REF_Y); + vec_t z = (xyz.v[2] / KIT_COLOR_REF_Z); + + if (x > 0.008856f) + x = vec_pow(x, (1.f / 3.f)); + else + x = (7.787f * x) + (16.f / 116.f); + + if (y > 0.008856f) + y = vec_pow(y, (1.f / 3.f)); + else + y = (7.787f * y) + (16.f / 116.f); + + if (z > 0.008856f) + z = vec_pow(z, (1.f / 3.f)); + else + z = (7.787f * z) + (16.f / 116.f); + + vec_t lightness = (116.f * y) - 16.f; + vec_t a = 500.f * (x - y); + vec_t b = 200.f * (y - z); + + return vec3(lightness, a, b); +} + +static vec3_t lab_to_lch(vec3_t lab) { + vec_t lightness = lab.v[0]; + vec_t a = lab.v[1]; + vec_t b = lab.v[2]; + + vec_t chroma = sqrtf(a * a + b * b); + vec_t hue = a == 0.f ? 0.f : vec_atan(b / a); + + return vec3(lightness, chroma, hue); +} + +static vec3_t lch_to_lab(vec3_t lch) { + vec_t lightness = lch.v[0]; + vec_t chroma = lch.v[1]; + vec_t hue = lch.v[2]; + + vec_t a = chroma * cos(hue); + vec_t b = chroma * sin(hue); + + return vec3(lightness, a, b); +} + +static vec3_t rgb_to_lch(vec3_t rgb) { + vec3_t xyz = rgb_to_xyz(rgb); + vec3_t lab = xyz_to_lab(xyz); + + return lab_to_lch(lab); +} + +static vec3_t lch_to_rgb(vec3_t lch) { + vec3_t lab = lch_to_lab(lch); + vec3_t xyz = lab_to_xyz(lab); + + return xyz_to_rgb(xyz); +} + +static vec4_t rgba_from_lcha(vec_t lightness, vec_t chroma, vec_t hue, + vec_t alpha) { + vec3_t rgb = lch_to_rgb(vec3(lightness, chroma, hue)); + return vec4(rgb.v[0], rgb.v[1], rgb.v[2], alpha); +} + +#ifdef __GNUC__ +# pragma GCC pop_options +# pragma GCC diagnostic pop +#endif + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/kit/mersenne_twister_64.c b/kit/mersenne_twister_64.c new file mode 100644 index 0000000..4032dc9 --- /dev/null +++ b/kit/mersenne_twister_64.c @@ -0,0 +1,66 @@ +#include "mersenne_twister_64.h" + +#define MM 156 +#define MATRIX_A 0xb5026f5aa96619e9ull +#define UM 0xffffffff80000000ull +#define LM 0x7fffffffull + +void kit_mt64_init_array(kit_mt64_state_t *state, i64 size, + u64 *seed) { + i64 i; + for (i = 0; i < size && i < KIT_MT64_N; i++) state->mt[i] = seed[i]; + for (state->index = size; state->index < KIT_MT64_N; state->index++) + state->mt[state->index] = (6364136223846793005ull * + (state->mt[state->index - 1] ^ + (state->mt[state->index - 1] >> + 62u)) + + state->index); +} + +void kit_mt64_init(kit_mt64_state_t *state, u64 seed) { + kit_mt64_init_array(state, 1, &seed); +} + +void kit_mt64_rotate(kit_mt64_state_t *state) { + static u64 mag01[2] = { 0ull, MATRIX_A }; + + u64 x; + i32 i; + + for (i = 0; i < KIT_MT64_N - MM; i++) { + x = (state->mt[i] & UM) | (state->mt[i + 1] & LM); + state->mt[i] = state->mt[i + MM] ^ (x >> 1u) ^ + mag01[(i32) (x & 1ull)]; + } + + for (; i < KIT_MT64_N - 1; i++) { + x = (state->mt[i] & UM) | (state->mt[i + 1] & LM); + state->mt[i] = state->mt[i + (MM - KIT_MT64_N)] ^ (x >> 1u) ^ + mag01[(i32) (x & 1ull)]; + } + + x = (state->mt[KIT_MT64_N - 1] & UM) | (state->mt[0] & LM); + state->mt[KIT_MT64_N - 1] = state->mt[MM - 1] ^ (x >> 1u) ^ + mag01[(i32) (x & 1ull)]; + + state->index = 0; +} + +u64 kit_mt64_generate(kit_mt64_state_t *state) { + if (state->index >= KIT_MT64_N) + kit_mt64_rotate(state); + + u64 x = state->mt[state->index++]; + + x ^= (x >> 29u) & 0x5555555555555555ull; + x ^= (x << 17u) & 0x71d67fffeda60000ull; + x ^= (x << 37u) & 0xfff7eee000000000ull; + x ^= (x >> 43u); + + return x; +} + +#undef MM +#undef MATRIX_A +#undef UM +#undef LM diff --git a/kit/mersenne_twister_64.h b/kit/mersenne_twister_64.h new file mode 100644 index 0000000..2709dd7 --- /dev/null +++ b/kit/mersenne_twister_64.h @@ -0,0 +1,35 @@ +#ifndef KIT_MERSENNE_TWISTER_64_H +#define KIT_MERSENNE_TWISTER_64_H + +#include "types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +enum { + KIT_MT64_N = 312, +}; + +typedef struct { + u64 mt[KIT_MT64_N]; + u64 index; +} kit_mt64_state_t; + +void kit_mt64_init_array(kit_mt64_state_t *state, i64 size, + u64 *seed); +void kit_mt64_init(kit_mt64_state_t *state, u64 seed); +void kit_mt64_rotate(kit_mt64_state_t *state); +u64 kit_mt64_generate(kit_mt64_state_t *state); + +#ifdef __cplusplus +} +#endif + +#define mt64_state_t kit_mt64_state_t +#define mt64_init_array kit_mt64_init_array +#define mt64_init kit_mt64_init +#define mt64_rotate kit_mt64_rotate +#define mt64_generate kit_mt64_generate + +#endif diff --git a/kit/move_back.h b/kit/move_back.h new file mode 100644 index 0000000..1885f5d --- /dev/null +++ b/kit/move_back.h @@ -0,0 +1,49 @@ +#ifndef KIT_MOVE_BACK_H +#define KIT_MOVE_BACK_H + +#include "types.h" + +#include <string.h> + +#ifdef __cplusplus +extern "C" { +#endif + +#define KIT_MOVE_BACK_INL(new_size, array, ...) \ + do { \ + i64 index_; \ + i64 end_ = (array).size; \ + u8 temp_[sizeof *(array).values]; \ + for (index_ = 0; index_ < end_;) { \ + if (__VA_ARGS__) { \ + end_--; \ + if (index_ != end_) { \ + memcpy(temp_, (array).values + end_, \ + sizeof *(array).values); \ + (array).values[end_] = (array).values[index_]; \ + memcpy((array).values + index_, temp_, \ + sizeof *(array).values); \ + } \ + } else \ + index_++; \ + } \ + (new_size) = end_; \ + } while (0) + +#define KIT_MOVE_BACK(new_size, array, value, cond) \ + KIT_MOVE_BACK_INL(new_size, array, \ + (cond) ((array).values[index_], (value))) + +#define KIT_MOVE_BACK_REF(new_size, array, value, cond) \ + KIT_MOVE_BACK_INL(new_size, array, \ + (cond) ((array).values + index_, (value))) + +#ifdef __cplusplus +} +#endif + +#define MOVE_BACK_INL KIT_MOVE_BACK_INL +#define MOVE_BACK KIT_MOVE_BACK +#define MOVE_BACK_REF KIT_MOVE_BACK_REF + +#endif diff --git a/kit/parse.c b/kit/parse.c new file mode 100644 index 0000000..042e2d0 --- /dev/null +++ b/kit/parse.c @@ -0,0 +1,2 @@ +#include "parse.h" + diff --git a/kit/parse.h b/kit/parse.h new file mode 100644 index 0000000..efb8156 --- /dev/null +++ b/kit/parse.h @@ -0,0 +1,14 @@ +#ifndef KIT_PARSE_H +#define KIT_PARSE_H + +#include "string_builder.h" + +#ifdef __cplusplus +extern "C" { +#endif + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/kit/print.c b/kit/print.c new file mode 100644 index 0000000..5c98910 --- /dev/null +++ b/kit/print.c @@ -0,0 +1,2 @@ +#include "print.h" + diff --git a/kit/print.h b/kit/print.h new file mode 100644 index 0000000..5a64a20 --- /dev/null +++ b/kit/print.h @@ -0,0 +1,47 @@ +#ifndef KIT_PRINT_H +#define KIT_PRINT_H + +#include "string_builder.h" + +#ifdef __cplusplus +extern "C" { +#endif + +enum { + KIT_PRINT_ALIGN_RIGHT = 1, + KIT_PRINT_UNSIGNED = (1 << 1), + KIT_PRINT_BIN = (1 << 2), + KIT_PRINT_OCT = (1 << 3), + KIT_PRINT_DEC = (1 << 4), + KIT_PRINT_HEX = (1 << 5), + KIT_PRINT_PRECISE = (1 << 6), + KIT_PRINT_UTF8 = (1 << 7), +}; + +s32 kit_print_int(kit_str_builder_t *s, i64 value, i64 width, c8 fill, + u32 flags); + +s32 kit_print_float(kit_str_builder_t *s, f64 value, i64 width, + c8 fill, u32 flags); + +s32 kit_print_esc(kit_str_builder_t *s, kit_str_t value, + c8 escape_char, kit_str_t special_symbols, + u32 flags); + +#ifdef __cplusplus +} +#endif + +#define PRINT_ALIGN_RIGHT KIT_PRINT_ALIGN_RIGHT +#define PRINT_UNSIGNED KIT_PRINT_UNSIGNED +#define PRINT_BIN KIT_PRINT_BIN +#define PRINT_OCT KIT_PRINT_OCT +#define PRINT_DEC KIT_PRINT_DEC +#define PRINT_HEX KIT_PRINT_HEX +#define PRINT_PRECISE KIT_PRINT_PRECISE +#define PRINT_UTF8 KIT_PRINT_UTF8 +#define print_int kit_print_int +#define print_float kit_print_float +#define print_esckit_print_esc + +#endif diff --git a/kit/process.h b/kit/process.h new file mode 100644 index 0000000..8031cc1 --- /dev/null +++ b/kit/process.h @@ -0,0 +1,71 @@ +// TODO +// + +#ifndef KIT_PROCESS_H +#define KIT_PROCESS_H + +#include "types.h" +#include "string_ref.h" + +#if !defined(_WIN32) || defined(__CYGWIN__) +# include <unistd.h> +#else +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +enum { + KIT_PROCESS_NO_ARGUMENTS = 1, + KIT_PROCESS_NO_ENVIRONMENT = (1 << 1), + KIT_PROCESS_NO_PIPES = (1 << 2), + KIT_PROCESS_FORK = (1 << 3), +}; + +typedef struct { + s32 status; + u8 exit_code; + b8 current_is_forked; +#if !defined(_WIN32) || defined(__CYGWIN__) + b8 _ready; + b8 _running; + pid_t _id; + i32 _stdin; + i32 _stdout; + i32 _stderr; +#else +#endif +} kit_process_t; + +typedef struct { + kit_str_t name; + kit_str_t value; +} kit_process_env_var_t; + +typedef KIT_AR(kit_str_t) kit_process_args_t; +typedef KIT_AR(kit_process_env_var_t) kit_process_env_t; + +typedef struct { + u32 flags; + kit_str_t file_name; + kit_process_args_t command_line; + kit_process_env_t environment; + kit_str_t working_directory; +} kit_process_info_t; + +s32 kit_process_init(kit_process_t *p, kit_process_info_t info); +void kit_process_cleanup(kit_process_t *p); + +i64 kit_process_write_stdin(kit_process_t *p, kit_str_t in_data); +i64 kit_process_read_stdout(kit_process_t *p, kit_str_t out_data); +i64 kit_process_read_stderr(kit_process_t *p, kit_str_t out_data); +s32 kit_process_terminate(kit_process_t *p); +b8 kit_process_alive(kit_process_t *p); +s32 kit_process_wait(kit_process_t *p); + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/kit/process.posix.c b/kit/process.posix.c new file mode 100644 index 0000000..d9bec1f --- /dev/null +++ b/kit/process.posix.c @@ -0,0 +1,323 @@ +#include "process.h" + +#if !defined(_WIN32) || defined(__CYGWIN__) +# include "status.h" + +# include <assert.h> +# include <fcntl.h> +# include <signal.h> +# include <sys/wait.h> + +static char *kit_process_argv_null_[] = { "", NULL }; +static char *kit_process_env_null_[] = { NULL }; + +static char *kit_process_str_(kit_str_t s) { + // FIXME + // + + return BS(s); +} + +static char **kit_init_argv_(kit_process_args_t args, u32 flags) { + // TODO + // + + if ((flags & KIT_PROCESS_NO_ARGUMENTS) != 0) + return kit_process_argv_null_; + + (void) args; + + return NULL; +} + +static char **kit_init_envp_(kit_process_env_t env, u32 flags) { + // TODO + // + + if ((flags & KIT_PROCESS_NO_ENVIRONMENT) != 0) + return kit_process_env_null_; + + (void) env; + + return NULL; +} + +s32 kit_process_init(kit_process_t *p, kit_process_info_t info) { + assert(p != NULL); + assert(info.working_directory.size == 0 || + info.working_directory.values != NULL); + + if (p == NULL || (info.working_directory.size != 0 && + info.working_directory.values == NULL)) + return KIT_ERROR_INVALID_ARGUMENT; + + memset(p, 0, sizeof *p); + + p->_stdin = -1; + p->_stdout = -1; + p->_stderr = -1; + + signal(SIGCHLD, SIG_IGN); + signal(SIGALRM, SIG_IGN); // pipes + + i32 pipe_in[2]; + i32 pipe_out[2]; + i32 pipe_err[2]; + + if ((info.flags & KIT_PROCESS_NO_PIPES) == 0) { + if (pipe(pipe_in) == -1) { + assert(0); + return KIT_ERROR_PIPE_FAILED; + } + + if (pipe(pipe_out) == -1) { + assert(0); + close(pipe_in[0]); + close(pipe_in[1]); + return KIT_ERROR_PIPE_FAILED; + } + + if (pipe(pipe_err) == -1) { + assert(0); + close(pipe_in[0]); + close(pipe_in[1]); + close(pipe_out[0]); + close(pipe_out[1]); + return KIT_ERROR_PIPE_FAILED; + } + + // non-blocking writing for stdout, stderr + if (fcntl(pipe_out[1], F_SETFL, O_NONBLOCK) == -1 || + fcntl(pipe_err[1], F_SETFL, O_NONBLOCK) == -1) { + assert(0); + close(pipe_in[0]); + close(pipe_in[1]); + close(pipe_out[0]); + close(pipe_out[1]); + close(pipe_err[0]); + close(pipe_err[1]); + return KIT_ERROR_PIPE_FAILED; + } + } + + pid_t id = fork(); + + switch (id) { + case -1: return KIT_ERROR_FORK_FAILED; + + case 0: + // Child process + // + + p->status = KIT_OK; + p->current_is_forked = 1; + + if ((info.flags & KIT_PROCESS_NO_PIPES) == 0) { + // Redirect IO + if (dup2(pipe_in[0], STDIN_FILENO) == -1 || + dup2(pipe_out[1], STDOUT_FILENO) == -1 || + dup2(pipe_err[1], STDERR_FILENO) == -1) { + assert(0); + close(pipe_in[0]); + close(pipe_in[1]); + close(pipe_out[0]); + close(pipe_out[1]); + close(pipe_err[0]); + close(pipe_err[1]); + return KIT_ERROR_DUP2_FAILED; + } + + // Close pipes + close(pipe_in[0]); + close(pipe_in[1]); + close(pipe_out[0]); + close(pipe_out[1]); + close(pipe_err[0]); + close(pipe_err[1]); + } + + // Change working directory + if (info.working_directory.size != 0 && + chdir(kit_process_str_(info.working_directory)) == -1) { + assert(0); + return KIT_ERROR_CHDIR_FAILED; + } + + if ((info.flags & KIT_PROCESS_FORK) == 0) { + execve(kit_process_str_(info.file_name), + kit_init_argv_(info.command_line, info.flags), + kit_init_envp_(info.environment, info.flags)); + // Doesn't return on success + + return KIT_ERROR_EXECVE_FAILED; + } + + return KIT_OK; + + default: + // Parent process + // + + p->status = KIT_OK; + p->current_is_forked = 0; + p->_ready = 1; + p->_running = 1; + p->_id = id; + + if ((info.flags & KIT_PROCESS_NO_PIPES) == 0) { + p->_stdin = pipe_in[1]; + p->_stdout = pipe_out[0]; + p->_stderr = pipe_err[0]; + + // Close unused pipes + close(pipe_in[0]); + close(pipe_out[1]); + close(pipe_err[1]); + } + } + + return KIT_OK; +} + +void kit_process_cleanup(kit_process_t *p) { + assert(p != NULL); + assert(p->_ready); + + if (p == NULL || !p->_ready) + return; + + if (p->_stdin != -1) + close(p->_stdin); + if (p->_stdout != -1) + close(p->_stdout); + if (p->_stderr != -1) + close(p->_stderr); + + memset(p, 0, sizeof *p); +} + +i64 kit_process_write_stdin(kit_process_t *p, kit_str_t in_data) { + assert(p != NULL && (in_data.size == 0 || in_data.values != NULL) && + p->_running); + + if (p == NULL || (in_data.size != 0 && in_data.values == NULL)) + return KIT_ERROR_INVALID_ARGUMENT; + if (in_data.size == 0 || !p->_running || p->_stdin == -1) + return 0; + + i64 n = write(p->_stdin, in_data.values, in_data.size); + + assert(n >= 0); + if (n < 0) + return 0; + + return n; +} + +i64 kit_process_read_stdout(kit_process_t *p, kit_str_t out_data) { + assert(p != NULL && + (out_data.size == 0 || out_data.values != NULL) && + p->_ready); + + if (p == NULL || (out_data.size != 0 && out_data.values == NULL)) + return KIT_ERROR_INVALID_ARGUMENT; + if (out_data.size == 0 || !p->_ready || p->_stdout == -1) + return 0; + + i64 n = read(p->_stdout, out_data.values, out_data.size); + + assert(n >= 0); + if (n < 0) + return 0; + + return n; +} + +i64 kit_process_read_stderr(kit_process_t *p, kit_str_t out_data) { + assert(p != NULL && + (out_data.size == 0 || out_data.values != NULL) && + p->_ready); + + if (p == NULL || (out_data.size != 0 && out_data.values == NULL)) + return KIT_ERROR_INVALID_ARGUMENT; + if (out_data.size == 0 || !p->_ready || p->_stderr == -1) + return 0; + + i64 n = read(p->_stderr, out_data.values, out_data.size); + + assert(n >= 0); + if (n < 0) + return 0; + + return n; +} + +s32 kit_process_terminate(kit_process_t *p) { + assert(p != NULL && p->_running); + if (p == NULL || !p->_running) + return KIT_ERROR_INVALID_ARGUMENT; + + if (kill(p->_id, SIGTERM) == -1) + return KIT_ERROR_KILL_FAILED; + + return KIT_OK; +} + +b8 kit_process_alive(kit_process_t *p) { + assert(p != NULL); + if (p == NULL || p->status != KIT_OK) + return 0; + + if (!p->_running) + return 0; + + int status; + + pid_t id = waitpid(p->_id, &status, WNOHANG); + + if (id == -1) { + p->status = KIT_ERROR_WAITPID_FAILED; + return 0; + } + + if (id == 0) + return 1; + + if (WIFEXITED(status)) { + p->exit_code = WEXITSTATUS(status); + p->_running = 0; + return 0; + } + + return 1; +} + +s32 kit_process_wait(kit_process_t *p) { + assert(p != NULL); + if (p == NULL) + return KIT_ERROR_INVALID_ARGUMENT; + + if (p->status != KIT_OK) + return p->status; + if (!p->_running) + return KIT_OK; + + for (;;) { + int status; + + pid_t id = waitpid(p->_id, &status, 0); + + if (id == -1) + return KIT_ERROR_WAITPID_FAILED; + + if (WIFEXITED(status)) { + p->exit_code = WEXITSTATUS(status); + p->_running = 0; + break; + } + } + + return KIT_OK; +} + +#endif diff --git a/kit/process.win32.c b/kit/process.win32.c new file mode 100644 index 0000000..ebff7b1 --- /dev/null +++ b/kit/process.win32.c @@ -0,0 +1,5 @@ +#include "process.h" + +#if defined(_WIN32) && !defined(__CYGWIN__) + +#endif diff --git a/kit/secure_random.c b/kit/secure_random.c new file mode 100644 index 0000000..2565f6f --- /dev/null +++ b/kit/secure_random.c @@ -0,0 +1,45 @@ +#include "secure_random.h" + +#include <assert.h> +#include <stdio.h> +#include <stdlib.h> + +#if defined(_WIN32) && !defined(__CYGWIN__) +# ifndef WIN32_LEAN_AND_MEAN +# define WIN32_LEAN_AND_MEAN 1 +# endif +# include <windows.h> +# include <wincrypt.h> +#else +# include <unistd.h> +#endif + +s32 kit_secure_random(i64 size, void *data) { + assert(size >= 0); + assert(data != NULL); + + if (size <= 0 || data == NULL) + return KIT_ERROR_INVALID_ARGUMENT; + +#if defined(_WIN32) && !defined(__CYGWIN__) + HCRYPTPROV prov = 0; + if (!CryptAcquireContextW(&prov, NULL, NULL, PROV_RSA_FULL, + CRYPT_VERIFYCONTEXT | CRYPT_SILENT) || + !CryptGenRandom(prov, (DWORD) size, (BYTE *) data) || + !CryptReleaseContext(prov, 0)) + return KIT_ERROR_RESOURCE_UNAVAILABLE; +#else + FILE *f = fopen("/dev/urandom", "rb"); + + if (f == NULL) + return KIT_ERROR_RESOURCE_UNAVAILABLE; + + i64 n = (i64) fread(data, 1, size, f); + fclose(f); + + if (n != size) + return KIT_ERROR_RESOURCE_UNAVAILABLE; +#endif + + return KIT_OK; +} diff --git a/kit/secure_random.h b/kit/secure_random.h new file mode 100644 index 0000000..435fe88 --- /dev/null +++ b/kit/secure_random.h @@ -0,0 +1,19 @@ +#ifndef KIT_SECURE_RANDOM_H +#define KIT_SECURE_RANDOM_H + +#include "types.h" +#include "status.h" + +#ifdef __cplusplus +extern "C" { +#endif + +s32 kit_secure_random(i64 size, void *data); + +#ifdef __cplusplus +} +#endif + +#define secure_random kit_secure_random + +#endif diff --git a/kit/sha256.c b/kit/sha256.c new file mode 100644 index 0000000..3abe972 --- /dev/null +++ b/kit/sha256.c @@ -0,0 +1,151 @@ +#include "sha256.h" + +#include <assert.h> +#include <string.h> + +#define ROTLEFT(a, b) (((a) << (b)) | ((a) >> (32 - (b)))) +#define ROTRIGHT(a, b) (((a) >> (b)) | ((a) << (32 - (b)))) + +#define CH(x, y, z) (((x) & (y)) ^ (~(x) & (z))) +#define MAJ(x, y, z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z))) +#define EP0(x) (ROTRIGHT(x, 2) ^ ROTRIGHT(x, 13) ^ ROTRIGHT(x, 22)) +#define EP1(x) (ROTRIGHT(x, 6) ^ ROTRIGHT(x, 11) ^ ROTRIGHT(x, 25)) +#define SIG0(x) (ROTRIGHT(x, 7) ^ ROTRIGHT(x, 18) ^ ((x) >> 3)) +#define SIG1(x) (ROTRIGHT(x, 17) ^ ROTRIGHT(x, 19) ^ ((x) >> 10)) + +static u32 kit_sha256_k[64] = { + 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, + 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, + 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, + 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, + 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, + 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, + 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, + 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, + 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, + 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08, + 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, + 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, + 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2 +}; + +static void kit_sha256_transform(u32 *state, u8 *data) { + assert(state != NULL); + assert(data != NULL); + + u32 a, b, c, d, e, f, g, h, i, j, t1, t2, m[64]; + + for (i = 0, j = 0; i < 16; ++i, j += 4) + m[i] = ((u32) data[j] << 24) | ((u32) data[j + 1] << 16) | + ((u32) data[j + 2] << 8) | ((u32) data[j + 3]); + for (; i < 64; ++i) + m[i] = SIG1(m[i - 2]) + m[i - 7] + SIG0(m[i - 15]) + m[i - 16]; + + a = state[0]; + b = state[1]; + c = state[2]; + d = state[3]; + e = state[4]; + f = state[5]; + g = state[6]; + h = state[7]; + + for (i = 0; i < 64; ++i) { + t1 = h + EP1(e) + CH(e, f, g) + kit_sha256_k[i] + m[i]; + t2 = EP0(a) + MAJ(a, b, c); + h = g; + g = f; + f = e; + e = d + t1; + d = c; + c = b; + b = a; + a = t1 + t2; + } + + state[0] += a; + state[1] += b; + state[2] += c; + state[3] += d; + state[4] += e; + state[5] += f; + state[6] += g; + state[7] += h; +} + +kit_sha256_hash_t kit_sha256(i64 in_size, u8 *in_data) { + assert(in_size >= 0); + assert(in_data != NULL); + + u32 state[8] = { 0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, + 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19 }; + + u8 data[64]; + + i64 i; + i64 datalen = 0; + u64 bitlen = 0; + + if (in_data != NULL) + for (i = 0; i < in_size; ++i) { + data[datalen] = in_data[i]; + datalen++; + + if (datalen != 64) + continue; + + kit_sha256_transform(state, data); + bitlen += 512; + datalen = 0; + } + + i = datalen; + + if (datalen < 56) { + data[i++] = 0x80; + while (i < 56) data[i++] = 0x00; + } else { + data[i++] = 0x80; + while (i < 64) data[i++] = 0x00; + + kit_sha256_transform(state, data); + memset(data, 0, 56); + } + + bitlen += datalen * 8; + data[63] = bitlen; + data[62] = bitlen >> 8; + data[61] = bitlen >> 16; + data[60] = bitlen >> 24; + data[59] = bitlen >> 32; + data[58] = bitlen >> 40; + data[57] = bitlen >> 48; + data[56] = bitlen >> 56; + + kit_sha256_transform(state, data); + + kit_sha256_hash_t hash; + memset(&hash, 0, sizeof hash); + + for (i = 0; i < 4; ++i) { + hash.v[i] = (state[0] >> (24 - i * 8)) & 0xff; + hash.v[i + 4] = (state[1] >> (24 - i * 8)) & 0xff; + hash.v[i + 8] = (state[2] >> (24 - i * 8)) & 0xff; + hash.v[i + 12] = (state[3] >> (24 - i * 8)) & 0xff; + hash.v[i + 16] = (state[4] >> (24 - i * 8)) & 0xff; + hash.v[i + 20] = (state[5] >> (24 - i * 8)) & 0xff; + hash.v[i + 24] = (state[6] >> (24 - i * 8)) & 0xff; + hash.v[i + 28] = (state[7] >> (24 - i * 8)) & 0xff; + } + + return hash; +} + +#undef ROTLEFT +#undef ROTRIGHT +#undef CH +#undef MAJ +#undef EP0 +#undef EP1 +#undef SIG0 +#undef SIG1 diff --git a/kit/sha256.h b/kit/sha256.h new file mode 100644 index 0000000..da05385 --- /dev/null +++ b/kit/sha256.h @@ -0,0 +1,26 @@ +#ifndef KIT_SHA256_H +#define KIT_SHA256_H + +#include "types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +enum { KIT_SHA256_BLOCK_SIZE = 32 }; + +typedef struct { + u8 v[KIT_SHA256_BLOCK_SIZE]; +} kit_sha256_hash_t; + +kit_sha256_hash_t kit_sha256(i64 size, u8 *data); + +#ifdef __cplusplus +} +#endif + +#define SHA256_BLOCK_SIZE KIT_SHA256_BLOCK_SIZE +#define sha256_hash_t kit_sha256_hash_t +#define sha256 kit_sha256 + +#endif diff --git a/kit/shared_memory.h b/kit/shared_memory.h new file mode 100644 index 0000000..a13ccee --- /dev/null +++ b/kit/shared_memory.h @@ -0,0 +1,48 @@ +#ifndef KIT_SHARED_MEMORY_H +#define KIT_SHARED_MEMORY_H + +#include "status.h" +#include "string_ref.h" + +#if !defined(_WIN32) || defined(__CYGWIN__) +# include <limits.h> +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct { + s32 status; + i64 size; + u8 *bytes; +#if defined(_WIN32) && !defined(__CYGWIN__) + void *_handle; +#else + i8 _owned; + char _name[NAME_MAX + 1]; +#endif +} kit_shared_memory_t; + +enum { + KIT_SHARED_MEMORY_OPEN, + KIT_SHARED_MEMORY_CREATE, +}; + +kit_shared_memory_t kit_shared_memory_open(kit_str_t name, i64 size, + i32 mode); +s32 kit_shared_memory_close(kit_shared_memory_t *mem); +s32 kit_shared_memory_clean(kit_str_t name); + +#ifdef __cplusplus +} +#endif + +#define shared_memory_t kit_shared_memory_t +#define shared_memory_clean kit_shared_memory_clean +#define shared_memory_open kit_shared_memory_open +#define shared_memory_close kit_shared_memory_close +#define SHARED_MEMORY_OPEN KIT_SHARED_MEMORY_OPEN +#define SHARED_MEMORY_CREATE KIT_SHARED_MEMORY_CREATE + +#endif diff --git a/kit/shared_memory.posix.c b/kit/shared_memory.posix.c new file mode 100644 index 0000000..fa0db98 --- /dev/null +++ b/kit/shared_memory.posix.c @@ -0,0 +1,124 @@ +#include "shared_memory.h" + +#if !defined(_WIN32) || defined(__CYGWIN__) +# include <stdio.h> +# include <string.h> +# include <sys/mman.h> +# include <sys/stat.h> +# include <fcntl.h> +# include <unistd.h> +# include <assert.h> + +kit_shared_memory_t kit_shared_memory_open(kit_str_t name, i64 size, + i32 mode) { + kit_shared_memory_t mem; + + memset(&mem, 0, sizeof mem); + + assert(size > 0); + assert(name.size > 0); + assert(name.size + 1 <= NAME_MAX); + assert(name.values != NULL); + + if (size <= 0) { + mem.status = KIT_ERROR_INVALID_SIZE; + return mem; + } + + if (name.size <= 0) { + mem.status = KIT_ERROR_INVALID_NAME; + return mem; + } + + if (name.size + 1 > NAME_MAX) { + mem.status = KIT_ERROR_NAME_TOO_LONG; + return mem; + } + + for (i64 i = 0; i < name.size; i++) + if (name.values[i] == '/' || name.values[i] == '\\') { + mem.status = KIT_ERROR_INVALID_NAME; + return mem; + } + + mem._name[0] = '/'; + memcpy(mem._name + 1, name.values, name.size); + mem._name[1 + name.size] = '\0'; + + i32 fd = shm_open(mem._name, + mode == KIT_SHARED_MEMORY_CREATE + ? O_RDWR | O_CREAT | O_EXCL + : O_RDWR, + mode == KIT_SHARED_MEMORY_CREATE ? 0660 : 0); + + if (fd == -1) { + mem.status = KIT_ERROR_OPEN_FAILED; + return mem; + } + + if (mode == KIT_SHARED_MEMORY_CREATE && ftruncate(fd, size) == -1) { + shm_unlink(mem._name); + assert(0); + mem.status = KIT_ERROR_TRUNCATE_FAILED; + return mem; + } + + void *p = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, + 0); + + close(fd); + + if (p == MAP_FAILED) { + shm_unlink(mem._name); + mem.status = KIT_ERROR_MAP_FAILED; + return mem; + } + + mem.status = KIT_OK; + mem.size = size; + mem.bytes = (u8 *) p; + mem._owned = (mode == KIT_SHARED_MEMORY_CREATE); + return mem; +} + +s32 kit_shared_memory_close(kit_shared_memory_t *mem) { + assert(mem != NULL); + + if (mem == NULL) + return KIT_ERROR_INVALID_ARGUMENT; + + s32 status = KIT_OK; + + if (munmap(mem->bytes, mem->size) != 0) + status |= KIT_ERROR_UNMAP_FAILED; + if (mem->_owned && shm_unlink(mem->_name) != 0) + status |= KIT_ERROR_UNLINK_FAILED; + + return status; +} + +s32 kit_shared_memory_clean(kit_str_t name) { + assert(name.size > 0); + assert(name.size + 1 <= NAME_MAX); + assert(name.values != NULL); + + if (name.size <= 0) + return KIT_ERROR_INVALID_NAME; + + if (name.size + 1 > NAME_MAX) + return KIT_ERROR_NAME_TOO_LONG; + + for (i64 i = 0; i < name.size; i++) + if (name.values[i] == '/' || name.values[i] == '\\') + return KIT_ERROR_INVALID_NAME; + + char buf[NAME_MAX + 1] = "/"; + memcpy(buf + 1, name.values, name.size); + buf[1 + name.size] = '\0'; + + if (shm_unlink(buf) != 0) + return KIT_ERROR_UNLINK_FAILED; + + return KIT_OK; +} +#endif diff --git a/kit/shared_memory.win32.c b/kit/shared_memory.win32.c new file mode 100644 index 0000000..f1d24d0 --- /dev/null +++ b/kit/shared_memory.win32.c @@ -0,0 +1,91 @@ +#include "shared_memory.h" + +#if defined(_WIN32) && !defined(__CYGWIN__) +# ifndef WIN32_LEAN_AND_MEAN +# define WIN32_LEAN_AND_MEAN +# endif +# ifndef NOMINMAX +# define NOMINMAX +# endif +# include <windows.h> + +kit_shared_memory_t kit_shared_memory_open(kit_str_t name, i64 size, + i32 mode) { + kit_shared_memory_t mem; + memset(&mem, 0, sizeof mem); + + char buf[264] = "Global\\"; + + assert(size > 0); + assert(name.size > 0); + assert(name.size + 8 < (i64) sizeof buf); + assert(name.values != NULL); + + if (name.size <= 0) { + mem.status = KIT_ERROR_INVALID_NAME; + return mem; + } + + if (name.size + 8 >= (i64) sizeof buf) { + mem.status = KIT_ERROR_NAME_TOO_LONG; + return mem; + } + + for (i64 i = 0; i < name.size; i++) + if (name.values[i] == '/' || name.values[i] == '\\') { + mem.status = KIT_ERROR_INVALID_NAME; + return mem; + } + + memcpy(buf + 7, name.values, name.size); + buf[7 + name.size] = '\0'; + + HANDLE h = mode == KIT_SHARED_MEMORY_CREATE + ? CreateFileMappingA( + INVALID_HANDLE_VALUE, NULL, PAGE_READWRITE, + (DWORD) (size >> 32), (DWORD) size, buf) + : OpenFileMappingA(FILE_MAP_ALL_ACCESS, 0, buf); + + if (h == INVALID_HANDLE_VALUE) { + mem.status = KIT_ERROR_OPEN_FAILED; + return mem; + } + + void *p = MapViewOfFile(h, FILE_MAP_ALL_ACCESS, 0, 0, + (SIZE_T) size); + + if (p == NULL) { + CloseHandle(h); + mem.status = KIT_ERROR_MAP_FAILED; + return mem; + } + + mem.status = KIT_OK; + mem.size = size; + mem.bytes = (u8 *) p; + mem._handle = h; + return mem; +} + +s32 kit_shared_memory_close(kit_shared_memory_t *mem) { + assert(mem != NULL); + + i32 status = KIT_OK; + + if (!UnmapViewOfFile(mem->bytes)) + status |= KIT_ERROR_UNMAP_FAILED; + if (!CloseHandle(mem->_handle)) + status |= KIT_ERROR_UNLINK_FAILED; + + return status; +} + +s32 kit_shared_memory_clean(kit_str_t name) { + // Do nothing. + // + + (void) name; + + return KIT_OK; +} +#endif diff --git a/kit/shared_mutex.h b/kit/shared_mutex.h new file mode 100644 index 0000000..ad83418 --- /dev/null +++ b/kit/shared_mutex.h @@ -0,0 +1,176 @@ +// Shared mutex can be used in shared memory for interprocess +// synchronization. +// + +#ifndef KIT_SHARED_MUTEX_H +#define KIT_SHARED_MUTEX_H + +#include "atomic.h" +#include "threads.h" + +#include <assert.h> +#include <string.h> + +#ifdef __cplusplus +extern "C" { +#endif + +#if defined(__GNUC__) || defined(__clang__) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-function" +# pragma GCC diagnostic ignored "-Wunknown-pragmas" +# pragma GCC push_options +# pragma GCC optimize("O3") +#endif + +enum { + KIT_SHARED_MUTEX_READY = 1, + KIT_SHARED_MUTEX_LOCKED, + KIT_SHARED_MUTEX_WRITER +}; + +typedef union { + struct { + i8 _Atomic state; + i32 readers; + }; + struct { + u8 _pad[16]; + }; +} kit_shared_mutex_t; + +static void kit_shared_mutex_init(kit_shared_mutex_t *m) { + assert(m != NULL); + memset(m, 0, sizeof *m); + + atomic_store_explicit(&m->state, KIT_SHARED_MUTEX_READY, + memory_order_relaxed); +} + +static b8 kit_shared_try_lock(kit_shared_mutex_t *m) { + assert(m != NULL); + + for (;;) { + i8 prev_state = KIT_SHARED_MUTEX_READY; + if (atomic_compare_exchange_strong_explicit( + &m->state, &prev_state, KIT_SHARED_MUTEX_LOCKED, + memory_order_seq_cst, memory_order_seq_cst)) + break; + if (prev_state == KIT_SHARED_MUTEX_WRITER) + return 0; + // FIXME + // Check performance + thrd_yield(); + } + + assert(m->readers >= 0); + ++m->readers; + + i8 prev_state = KIT_SHARED_MUTEX_LOCKED; + if (!atomic_compare_exchange_strong_explicit( + &m->state, &prev_state, KIT_SHARED_MUTEX_READY, + memory_order_seq_cst, memory_order_seq_cst)) + assert(0); + + return 1; +} + +static void kit_shared_lock(kit_shared_mutex_t *m) { + assert(m != NULL); + + while (!kit_shared_try_lock(m)) + // FIXME + // Check performance + thrd_yield(); +} + +static void kit_shared_unlock(kit_shared_mutex_t *m) { + assert(m != NULL); + + for (;;) { + i8 prev_state = KIT_SHARED_MUTEX_READY; + if (atomic_compare_exchange_strong_explicit( + &m->state, &prev_state, KIT_SHARED_MUTEX_LOCKED, + memory_order_seq_cst, memory_order_seq_cst)) + break; + // FIXME + // Check performance + thrd_yield(); + } + + assert(m->readers > 0); + m->readers--; + + i8 prev_state = KIT_SHARED_MUTEX_LOCKED; + if (!atomic_compare_exchange_strong_explicit( + &m->state, &prev_state, KIT_SHARED_MUTEX_READY, + memory_order_seq_cst, memory_order_seq_cst)) + assert(0); +} + +static b8 kit_unique_try_lock(kit_shared_mutex_t *m) { + assert(m != NULL); + + i8 prev_state = KIT_SHARED_MUTEX_READY; + if (!atomic_compare_exchange_strong_explicit( + &m->state, &prev_state, KIT_SHARED_MUTEX_WRITER, + memory_order_seq_cst, memory_order_seq_cst)) + return 0; + + i8 is_locked = (m->readers == 0); + + prev_state = KIT_SHARED_MUTEX_WRITER; + if (!is_locked && + !atomic_compare_exchange_strong_explicit( + &m->state, &prev_state, KIT_SHARED_MUTEX_READY, + memory_order_seq_cst, memory_order_seq_cst)) + assert(0); + + return is_locked; +} + +static void kit_unique_lock(kit_shared_mutex_t *m) { + assert(m != NULL); + + while (!kit_unique_try_lock(m)) + // FIXME + // Check performance + thrd_yield(); +} + +static void kit_unique_unlock(kit_shared_mutex_t *m) { + assert(m != NULL); + + i8 prev_state = KIT_SHARED_MUTEX_WRITER; + if (!atomic_compare_exchange_strong_explicit( + &m->state, &prev_state, KIT_SHARED_MUTEX_READY, + memory_order_seq_cst, memory_order_seq_cst)) + assert(0); +} + +#if defined(__GNUC__) || defined(__clang__) +# pragma GCC pop_options +# pragma GCC diagnostic pop +#endif + +#ifdef __cplusplus +} +#endif + +#define shared_mutex_t kit_shared_mutex_t +#define shared_mutex_init kit_shared_mutex_init +#define shared_try_lock kit_shared_try_lock +#define shared_lock kit_shared_lock +#define shared_unlock kit_shared_unlock +#define unique_try_lock kit_unique_try_lock +#define unique_lock kit_unique_lock +#define unique_unlock kit_unique_unlock +#define shared_mutex_init kit_shared_mutex_init +#define shared_try_lock kit_shared_try_lock +#define shared_lock kit_shared_lock +#define shared_unlock kit_shared_unlock +#define unique_try_lock kit_unique_try_lock +#define unique_lock kit_unique_lock +#define unique_unlock kit_unique_unlock + +#endif diff --git a/kit/sockets.h b/kit/sockets.h new file mode 100644 index 0000000..276ecc5 --- /dev/null +++ b/kit/sockets.h @@ -0,0 +1,107 @@ +#ifndef KIT_SOCKETS_H +#define KIT_SOCKETS_H + +#include "types.h" +#include "status.h" + +#ifndef KIT_DISABLE_SYSTEM_SOCKETS +# ifdef __GNUC__ +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-function" +# pragma GCC diagnostic ignored "-Wunknown-pragmas" +# endif + +# ifdef __cplusplus +extern "C" { +# endif + +# if defined(_WIN32) && !defined(__CYGWIN__) + +# define WIN32_LEAN_AND_MEAN +# include <winsock2.h> +# include <ws2tcpip.h> + +# define socket_t SOCKET +# define socklen_t i32 + +static s32 kit_sockets_init(void) { + WSADATA data; + memset(&data, 0, sizeof data); + WORD version = MAKEWORD(2, 2); + return WSAStartup(version, &data) == ERROR_SUCCESS + ? KIT_OK + : KIT_ERROR_SOCKETS_STARTUP_FAILED; +} + +static s32 kit_sockets_cleanup(void) { + WSACleanup(); + return KIT_OK; +} + +static i32 kit_socket_set_blocking(socket_t s) { + u_long flag = 0; + return ioctlsocket(s, FIONBIO, &flag) == 0 + ? KIT_OK + : KIT_ERROR_SOCKET_CONTROL_FAILED; +} + +static i32 kit_socket_set_nonblocking(socket_t s) { + u_long flag = 1; + return ioctlsocket(s, FIONBIO, &flag) == 0 + ? KIT_OK + : KIT_ERROR_SOCKET_CONTROL_FAILED; +} + +# else + +# include <arpa/inet.h> +# include <errno.h> +# include <fcntl.h> +# include <netinet/in.h> +# include <signal.h> +# include <sys/ioctl.h> +# include <sys/select.h> +# include <sys/socket.h> +# include <sys/types.h> +# include <unistd.h> +# include <netdb.h> + +# define socket_t i32 +# define closesocket close +# define INVALID_SOCKET -1 + +static s32 kit_sockets_init(void) { + signal(SIGPIPE, SIG_IGN); + return KIT_OK; +} + +static s32 kit_sockets_cleanup(void) { + return KIT_OK; +} + +static i32 kit_socket_set_blocking(socket_t s) { + i32 flags = fcntl(s, F_GETFL, 0); + return fcntl(s, F_SETFL, flags & ~O_NONBLOCK) == 0 + ? KIT_OK + : KIT_ERROR_SOCKET_CONTROL_FAILED; +} + +static i32 kit_socket_set_nonblocking(socket_t s) { + i32 flags = fcntl(s, F_GETFL, 0); + return fcntl(s, F_SETFL, flags | O_NONBLOCK) == 0 + ? KIT_OK + : KIT_ERROR_SOCKET_CONTROL_FAILED; +} + +# endif + +# ifdef __cplusplus +} +# endif + +# ifdef __GNUC__ +# pragma GCC diagnostic pop +# endif +#endif + +#endif diff --git a/kit/status.h b/kit/status.h new file mode 100644 index 0000000..88eb5e0 --- /dev/null +++ b/kit/status.h @@ -0,0 +1,43 @@ +#ifndef KIT_STATUS_H +#define KIT_STATUS_H + +#ifndef _GNU_SOURCE +# define _GNU_SOURCE +#endif + +enum { + KIT_OK = 0, + KIT_PARSING_FAILED = 1, + KIT_ERROR_OUT_OF_MEMORY = (1 << 1), + KIT_ERROR_INVALID_ARGUMENT = (1 << 2), + KIT_ERROR_MKDIR_FAILED = (1 << 3), + KIT_ERROR_RMDIR_FAILED = (1 << 4), + KIT_ERROR_UNLINK_FAILED = (1 << 5), + KIT_ERROR_FILE_ALREADY_EXISTS = (1 << 6), + KIT_ERROR_FILE_DOES_NOT_EXIST = (1 << 7), + KIT_ERROR_PATH_TOO_LONG = (1 << 8), + KIT_ERROR_SOCKETS_STARTUP_FAILED = (1 << 9), + KIT_ERROR_SOCKET_CONTROL_FAILED = (1 << 10), + KIT_ERROR_NAME_TOO_LONG = (1 << 11), + KIT_ERROR_INVALID_SIZE = (1 << 12), + KIT_ERROR_INVALID_NAME = (1 << 13), + KIT_ERROR_INVALID_PATH = (1 << 14), + KIT_ERROR_OPEN_FAILED = (1 << 15), + KIT_ERROR_TRUNCATE_FAILED = (1 << 16), + KIT_ERROR_MAP_FAILED = (1 << 17), + KIT_ERROR_UNMAP_FAILED = (1 << 18), + KIT_ERROR_SYNC_FAILED = (1 << 19), + KIT_ERROR_CLOSE_FAILED = (1 << 20), + KIT_ERROR_RESOURCE_UNAVAILABLE = (1 << 21), + KIT_ERROR_FORK_FAILED = (1 << 22), + KIT_ERROR_EXECVE_FAILED = (1 << 23), + KIT_ERROR_WAITPID_FAILED = (1 << 24), + KIT_ERROR_PIPE_FAILED = (1 << 25), + KIT_ERROR_DUP2_FAILED = (1 << 26), + KIT_ERROR_CHDIR_FAILED = (1 << 27), + KIT_ERROR_KILL_FAILED = (1 << 28), + KIT_ERROR_INTERNAL = (1 << 30), + KIT_ERROR_NOT_IMPLEMENTED = -1, +}; + +#endif diff --git a/kit/string_builder.h b/kit/string_builder.h new file mode 100644 index 0000000..23eda65 --- /dev/null +++ b/kit/string_builder.h @@ -0,0 +1,112 @@ +#ifndef KIT_STRING_BUILDER_H +#define KIT_STRING_BUILDER_H + +#include "status.h" +#include "string_ref.h" +#include "dynamic_array.h" + +#include <assert.h> + +#ifdef __cplusplus +extern "C" { +#endif + +typedef KIT_DA(char) kit_str_builder_t; + +#ifdef __GNUC__ +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-function" +# pragma GCC diagnostic ignored "-Wunknown-pragmas" +# pragma GCC push_options +# pragma GCC optimize("O3") +#endif + +static kit_str_builder_t kit_str_build(kit_str_t s, + kit_allocator_t *alloc) { + assert(s.size >= 0 && (s.size == 0 || s.values != NULL)); + kit_str_builder_t builder; + memset(&builder, 0, sizeof builder); + if (s.size < 0 || (s.size != 0 && s.values == NULL)) + return builder; + KIT_DA_INIT(builder, s.size, alloc); + assert(builder.size == s.size); + if (builder.size == s.size) + memcpy(builder.values, s.values, s.size); + return builder; +} + +static kit_str_builder_t kit_substr_build(kit_str_t s, i64 index, + i64 size, + kit_allocator_t *alloc) { + assert(index + size <= s.size); + if (index + size > s.size) { + kit_str_builder_t builder; + memset(&builder, 0, sizeof builder); + return builder; + } + return kit_str_build(kit_str(size, s.values + index), alloc); +} + +static s32 kit_str_append(kit_str_builder_t *a, kit_str_t b) { + assert(a != NULL); + if (a == NULL) + return KIT_ERROR_INVALID_ARGUMENT; + if (b.size <= 0) + return KIT_OK; + i64 n = a->size; + KIT_DA_RESIZE(*a, n + b.size); + if (a->size != n + b.size) + return KIT_ERROR_OUT_OF_MEMORY; + memcpy(a->values + n, b.values, b.size); + return KIT_OK; +} + +static s32 kit_str_insert(kit_str_builder_t *a, i64 index, + kit_str_t b) { + assert(a != NULL && index >= 0 && index <= a->size); + if (a == NULL || index < 0 || index > a->size) + return KIT_ERROR_INVALID_ARGUMENT; + if (b.size <= 0) + return KIT_OK; + i64 n = a->size; + KIT_DA_RESIZE(*a, n + b.size); + if (a->size != n + b.size) + return KIT_ERROR_OUT_OF_MEMORY; + if (index < n) + memmove(a->values + (index + b.size), a->values + index, + n - index); + memcpy(a->values + index, b.values, b.size); + return KIT_OK; +} + +static s32 kit_str_erase(kit_str_builder_t *a, i64 index, i64 size) { + assert(a != NULL && index >= 0 && size >= 0 && + index + size <= a->size); + if (a == NULL || index < 0 || size < 0 || index + size > a->size) + return KIT_ERROR_INVALID_ARGUMENT; + if (size <= 0) + return KIT_OK; + if (index + size < a->size) + memmove(a->values + index, a->values + (index + size), + a->size - index - size); + KIT_DA_RESIZE(*a, a->size - size); + return KIT_OK; +} + +#ifdef __GNUC__ +# pragma GCC pop_options +# pragma GCC diagnostic pop +#endif + +#ifdef __cplusplus +} +#endif + +#define str_builder_t kit_str_builder_t +#define str_build kit_str_build +#define substr_build kit_substr_build +#define str_append kit_str_append +#define str_insert kit_str_insert +#define str_erase kit_str_erase + +#endif diff --git a/kit/string_ref.h b/kit/string_ref.h new file mode 100644 index 0000000..e7ea809 --- /dev/null +++ b/kit/string_ref.h @@ -0,0 +1,137 @@ +#ifndef KIT_STRING_REF_H +#define KIT_STRING_REF_H + +#include "array_ref.h" + +#include <assert.h> +#include <string.h> + +#ifdef __cplusplus +extern "C" { +#endif + +typedef KIT_AR(char) kit_str_t; + +#if defined(__GNUC__) || defined(__clang__) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-function" +# pragma GCC diagnostic ignored "-Wunknown-pragmas" +# pragma GCC push_options +# pragma GCC optimize("O3") +#endif + +static kit_str_t kit_str(i64 size, char const *static_string) { + kit_str_t s = { .size = size, .values = (char *) static_string }; + return s; +} + +enum { + KIT_STR_NOT_FOUND = -1, +}; + +static i64 kit_str_find(kit_str_t a, kit_str_t b) { + assert(a.size >= 0 && (a.size == 0 || a.values != NULL) && + b.size >= 0 && (b.size == 0 || b.values != NULL)); + if (a.size < 0 || (a.size != 0 && a.values == NULL) || b.size < 0 || + (b.size != 0 && b.values == NULL)) + return -1; + for (i64 index = 0; index + b.size <= a.size; index++) + if (KIT_AR_EQUAL(kit_str(b.size, a.values + index), b)) + return index; + return -1; +} + +static i64 kit_str_find_back(kit_str_t a, kit_str_t b) { + assert(a.size >= 0 && (a.size == 0 || a.values != NULL) && + b.size >= 0 && (b.size == 0 || b.values != NULL)); + if (a.size < 0 || (a.size != 0 && a.values == NULL) || b.size < 0 || + (b.size != 0 && b.values == NULL)) + return -1; + for (i64 index = a.size - b.size; index >= 0; index--) + if (KIT_AR_EQUAL(kit_str(b.size, a.values + index), b)) + return index; + return -1; +} + +static i64 kit_str_find_n(kit_str_t a, kit_str_t b, i64 n) { + assert(a.size >= 0 && (a.size == 0 || a.values != NULL) && + b.size >= 0 && (b.size == 0 || b.values != NULL)); + if (a.size < 0 || (a.size != 0 && a.values == NULL) || b.size < 0 || + (b.size != 0 && b.values == NULL)) + return -1; + i64 count = 0; + for (i64 index = 0; index + b.size <= a.size; index++) + if (KIT_AR_EQUAL(kit_str(b.size, a.values + index), b)) { + if (count == n) + return index; + else + count++; + } + return -1; +} + +static i64 kit_str_find_back_n(kit_str_t a, kit_str_t b, i64 n) { + assert(a.size >= 0 && (a.size == 0 || a.values != NULL) && + b.size >= 0 && (b.size == 0 || b.values != NULL)); + if (a.size < 0 || (a.size != 0 && a.values == NULL) || b.size < 0 || + (b.size != 0 && b.values == NULL)) + return -1; + i64 count = 0; + for (i64 index = a.size - b.size; index >= 0; index--) + if (KIT_AR_EQUAL(kit_str(b.size, a.values + index), b)) { + if (count == n) + return index; + else + count++; + } + return -1; +} + +// Make a barbarian string for C standard library functions. +// Not thread safe. +// Use with caution. +// +static char *kit_make_bs(kit_str_t s) { + static char buf[8][4096]; + static i32 index = 0; + i64 n = s.size; + if (n > 4095) + n = 4095; + if (n > 0) + memcpy(buf[index], s.values, n); + buf[index][n] = '\0'; + char *result = buf[index]; + index = (index + 1) % 8; + return result; +} + +#if defined(__GNUC__) || defined(__clang__) +# pragma GCC pop_options +# pragma GCC diagnostic pop +#endif + +#define KIT_SZ(static_str_) \ + kit_str(sizeof(static_str_) - 1, (static_str_)) + +#define KIT_WRAP_BS(string_) kit_str(strlen(string_), (string_)) + +#define KIT_WRAP_STR(...) \ + kit_str((__VA_ARGS__).size, (__VA_ARGS__).values) + +#ifdef __cplusplus +} +#endif + +#define BS(...) kit_make_bs(KIT_WRAP_STR(__VA_ARGS__)) +#define str_t kit_str_t +#define str kit_str +#define str_find kit_str_find +#define str_find_back kit_str_find_back +#define str_find_n kit_str_find_n +#define str_find_back_n kit_str_find_back_n +#define STR_NOT_FOUND KIT_STR_NOT_FOUND +#define SZ KIT_SZ +#define WRAP_BS KIT_WRAP_BS +#define WRAP_STR KIT_WRAP_STR + +#endif diff --git a/kit/test.h b/kit/test.h new file mode 100644 index 0000000..243111e --- /dev/null +++ b/kit/test.h @@ -0,0 +1,1096 @@ +// ================================================================ +// +// test.h +// https://guattari.tech/git/kit +// +// Header-only unit-testing and microbenchmarks library for C. +// +// +// - Define a unique KIT_TEST_FILE for each file to avoid name +// collisions. +// +// - Define KIT_TEST_IMPLEMENTATION to include the implementation. +// +// +// Optional settings +// +// - KIT_TESTS_SIZE_LIMIT +// - KIT_TEST_ASSERTIONS_LIMIT +// - KIT_BENCHS_SIZE_LIMIT +// - KIT_BENCH_MAX_REPEATS +// - KIT_BENCH_MAX_CYCLES +// - KIT_BENCH_REPEATS_DEFAULT_1 +// - KIT_BENCH_REPEATS_DEFAULT_2 +// +// +// Usage example +// +// // foo.test.c +// #define KIT_TEST_FILE foo // This is required if you want to +// // use multiple test files. +// #include "test.h" +// TEST("foo") { +// REQUIRE(1); +// REQUIRE_EQ(2 + 2, 4); +// } +// +// // main.c +// #define KIT_TEST_IMPLEMENTATION +// #include "test.h" +// int main(int argc, char **argv) { +// return run_tests(argc, argv); +// } +// +// ================================================================ + +#ifndef KIT_TEST_H +#define KIT_TEST_H + +#ifdef __GNUC__ +# pragma GCC diagnostic ignored "-Wunused-value" +# pragma GCC diagnostic ignored "-Wunused-parameter" +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +#ifndef _GNU_SOURCE +# define _GNU_SOURCE +#endif + +#include <stddef.h> +#include <stdint.h> + +#ifndef KIT_TEST_FILE +# define KIT_TEST_FILE kit_test +#endif + +#ifndef KIT_TESTS_SIZE_LIMIT +# define KIT_TESTS_SIZE_LIMIT 0x1000 +#endif + +#ifndef KIT_TEST_ASSERTIONS_LIMIT +# define KIT_TEST_ASSERTIONS_LIMIT 0x50 +#endif + +#ifndef KIT_BENCHS_SIZE_LIMIT +# define KIT_BENCHS_SIZE_LIMIT 200 +#endif + +#ifndef KIT_BENCH_MAX_REPEATS +# define KIT_BENCH_MAX_REPEATS 4000 +#endif + +#ifndef KIT_BENCH_MAX_CYCLES +# define KIT_BENCH_MAX_CYCLES 40 +#endif + +#ifndef KIT_BENCH_REPEATS_DEFAULT_1 +# define KIT_BENCH_REPEATS_DEFAULT_1 40 +#endif + +#ifndef KIT_BENCH_REPEATS_DEFAULT_2 +# define KIT_BENCH_REPEATS_DEFAULT_2 400 +#endif + +typedef void (*kit_test_report_fn)(int test_index, int line, + int64_t value, int64_t expected); +typedef void (*kit_test_run_fn)( + int kit_test_index_, kit_test_report_fn kit_test_report_fn_); + +typedef struct { + char const *test_name; + char const *test_file; + kit_test_run_fn test_fn; + int assertions; + int line[KIT_TEST_ASSERTIONS_LIMIT]; + int status[KIT_TEST_ASSERTIONS_LIMIT]; + int64_t value[KIT_TEST_ASSERTIONS_LIMIT]; + int64_t expected[KIT_TEST_ASSERTIONS_LIMIT]; + int signal; +} kit_test_case_t; + +typedef struct { + int size; + kit_test_case_t v[KIT_TESTS_SIZE_LIMIT]; +} kit_tests_list_t; + +extern kit_tests_list_t kit_tests_list; + +#define KIT_TEST_CONCAT4_(a, b, c, d) a##b##c##d +#define KIT_TEST_CONCAT3_(a, b, c) KIT_TEST_CONCAT4_(a, b, _, c) + +#ifdef __cplusplus +# define KIT_TEST_ON_START_(f) \ + static void f(void); \ + static int KIT_TEST_CONCAT3_(_kit_test_init_, __LINE__, \ + f) = (f(), 0); \ + static void f(void) +#else +# ifdef _MSC_VER +# pragma section(".CRT$XCU", read) +# define KIT_TEST_ON_START_2_(f, p) \ + static void f(void); \ + __declspec(allocate(".CRT$XCU")) void (*f##_)(void) = f; \ + __pragma(comment(linker, "/include:" p #f "_")) static void f( \ + void) +# ifdef _WIN64 +# define KIT_TEST_ON_START_(f) KIT_TEST_ON_START_2_(f, "") +# else +# define KIT_TEST_ON_START_(f) KIT_TEST_ON_START_2_(f, "_") +# endif +# else +# define KIT_TEST_ON_START_(f) \ + static void f(void) __attribute__((constructor)); \ + static void f(void) +# endif +#endif + +void kit_test_register(char const *name, char const *file, + kit_test_run_fn fn); + +#define KIT_TEST(name) \ + static void KIT_TEST_CONCAT3_(kit_test_run_, __LINE__, \ + KIT_TEST_FILE)(int, \ + kit_test_report_fn); \ + KIT_TEST_ON_START_( \ + KIT_TEST_CONCAT3_(kit_test_case_, __LINE__, KIT_TEST_FILE)) { \ + kit_test_register( \ + name, __FILE__, \ + KIT_TEST_CONCAT3_(kit_test_run_, __LINE__, KIT_TEST_FILE)); \ + } \ + static void KIT_TEST_CONCAT3_(kit_test_run_, __LINE__, \ + KIT_TEST_FILE)( \ + int kit_test_index_, kit_test_report_fn kit_test_report_fn_) + +#define KIT_REQUIRE(...) \ + kit_test_report_fn_(kit_test_index_, __LINE__, (__VA_ARGS__), 1) + +#define KIT_REQUIRE_EQ(...) \ + kit_test_report_fn_(kit_test_index_, __LINE__, __VA_ARGS__) + +int kit_run_tests(int argc, char **argv); + +typedef void (*kit_bench_set_repeats_limit_fn)(int bench_index, + int repeats_limit); +typedef int (*kit_bench_loop_fn)(int bench_index); +typedef void (*kit_bench_begin_fn)(int bench_index); +typedef void (*kit_bench_end_fn)(int bench_index); + +typedef void (*kit_bench_run_fn)( + int kit_bench_index_, + kit_bench_set_repeats_limit_fn kit_bench_set_repeats_limit_, + kit_bench_loop_fn kit_bench_loop_, + kit_bench_begin_fn kit_bench_begin_, + kit_bench_end_fn kit_bench_end_); + +typedef struct { + char const *bench_name; + char const *bench_file; + kit_bench_run_fn bench_fn; + int64_t sec[KIT_BENCH_MAX_REPEATS]; + int32_t nsec[KIT_BENCH_MAX_REPEATS]; + int64_t duration_nsec[KIT_BENCH_MAX_REPEATS]; + int64_t duration_sorted_nsec[KIT_BENCH_MAX_REPEATS]; + int repeats; + int cycles_size; + int cycles[KIT_BENCH_MAX_CYCLES]; + int cycle; + int signal; + int ready; +} kit_benchmark_t; + +typedef struct { + int size; + kit_benchmark_t v[KIT_BENCHS_SIZE_LIMIT]; +} kit_benchs_list_t; + +extern kit_benchs_list_t kit_benchs_list; + +void kit_bench_register(char const *name, char const *file, + kit_bench_run_fn fn); + +#define KIT_BENCHMARK(name) \ + static void KIT_TEST_CONCAT3_(kit_bench_run_, __LINE__, \ + KIT_TEST_FILE)( \ + int, kit_bench_set_repeats_limit_fn, kit_bench_loop_fn, \ + kit_bench_begin_fn, kit_bench_end_fn); \ + KIT_TEST_ON_START_( \ + KIT_TEST_CONCAT3_(kit_benchmark_, __LINE__, KIT_TEST_FILE)) { \ + kit_bench_register( \ + name, __FILE__, \ + KIT_TEST_CONCAT3_(kit_bench_run_, __LINE__, KIT_TEST_FILE)); \ + } \ + static void KIT_TEST_CONCAT3_(kit_bench_run_, __LINE__, \ + KIT_TEST_FILE)( \ + int kit_bench_index_, \ + kit_bench_set_repeats_limit_fn kit_bench_set_repeats_limit_, \ + kit_bench_loop_fn kit_bench_loop_, \ + kit_bench_begin_fn kit_bench_begin_, \ + kit_bench_end_fn kit_bench_end_) + +#define KIT_BENCHMARK_REPEAT(repeats_limit_) \ + kit_bench_set_repeats_limit_(kit_bench_index_, repeats_limit_) + +#define KIT_BENCHMARK_BEGIN \ + while (kit_bench_loop_(kit_bench_index_)) { \ + kit_bench_begin_(kit_bench_index_); \ + { + +#define KIT_BENCHMARK_END \ + } \ + kit_bench_end_(kit_bench_index_); \ + } + +// FIXME +// +#define KIT_DO_NOT_OPTIMIZE(x) \ + do { \ + volatile void *bench_ptr_ = &(x); \ + (void) bench_ptr_; \ + } while (0) + +int kit_run_benchmarks(int argc, char **argv); + +#define TEST KIT_TEST +#define REQUIRE KIT_REQUIRE +#define REQUIRE_EQ KIT_REQUIRE_EQ +#define BENCHMARK KIT_BENCHMARK +#define BENCHMARK_REPEAT KIT_BENCHMARK_REPEAT +#define BENCHMARK_BEGIN KIT_BENCHMARK_BEGIN +#define BENCHMARK_END KIT_BENCHMARK_END +#define DO_NOT_OPTIMIZE KIT_DO_NOT_OPTIMIZE +#define test_register kit_test_register +#define run_tests kit_run_tests +#define bench_register kit_bench_register +#define run_benchmarks kit_run_benchmarks + +#ifdef __cplusplus +} +#endif + +#endif + +// ================================================================ +// +// Implementation +// +// ================================================================ + +#if defined(KIT_TEST_IMPLEMENTATION) && !defined(KIT_TEST_H_IMPL) +#define KIT_TEST_H_IMPL + +#ifdef __cplusplus +extern "C" { +#endif + +#ifndef KIT_TIME_H +# define KIT_TIME_H + +# include <time.h> + +# ifndef TIME_UTC +# define TIME_UTC 1 +# endif + +# ifdef KIT_REQUIRE_TIMESPEC_GET +# ifndef WIN32_LEAN_AND_MEAN +# define WIN32_LEAN_AND_MEAN 1 +# endif +# include <windows.h> + +# define KIT_TIMESPEC_IMPL_UNIX_EPOCH_IN_TICKS \ + 116444736000000000ull +# define KIT_TIMESPEC_IMPL_TICKS_PER_SECONDS 10000000ull + +static int timespec_get(struct timespec *ts, int base) { + if (ts == NULL || base != TIME_UTC) + return 0; + + FILETIME ft; + ULARGE_INTEGER date; + LONGLONG ticks; + + GetSystemTimeAsFileTime(&ft); + date.HighPart = ft.dwHighDateTime; + date.LowPart = ft.dwLowDateTime; + ticks = (LONGLONG) (date.QuadPart - + KIT_TIMESPEC_IMPL_UNIX_EPOCH_IN_TICKS); + ts->tv_sec = ticks / KIT_TIMESPEC_IMPL_TICKS_PER_SECONDS; + ts->tv_nsec = (ticks % KIT_TIMESPEC_IMPL_TICKS_PER_SECONDS) * 100; + + return base; +} +# endif + +#endif + +#include <setjmp.h> +#include <signal.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +enum { + kit_white_, + kit_blue_, + kit_light_, + kit_yellow_, + kit_red_, + kit_green_ +}; + +static char const *kit_color_codes_[] = { "\x1b[38m", "\x1b[34m", + "\x1b[37m", "\x1b[33m", + "\x1b[31m", "\x1b[32m" }; + +static int kit_print_color_(int c) { + return printf("%s", kit_color_codes_[c]); +} + +static int kit_signums_[] = { SIGINT, SIGILL, SIGABRT, + SIGFPE, SIGSEGV, SIGTERM }; + +static char const *kit_signames_[64]; + +static void kit_signames_init_(void) { + memset(kit_signames_, 0, sizeof kit_signames_); + kit_signames_[SIGINT] = "Interactive attention signal"; + kit_signames_[SIGILL] = "Illegal instruction"; + kit_signames_[SIGABRT] = "Abnormal termination"; + kit_signames_[SIGFPE] = "Erroneous arithmetic operation"; + kit_signames_[SIGSEGV] = "Invalid access to storage"; + kit_signames_[SIGTERM] = "Termination request"; +} + +kit_tests_list_t kit_tests_list = { 0 }; + +static void kit_report_(int i, int line, int64_t value, + int64_t expected) { + int n = kit_tests_list.v[i].assertions++; + + if (n >= KIT_TEST_ASSERTIONS_LIMIT) + return; + + kit_tests_list.v[i].line[n] = line; + kit_tests_list.v[i].status[n] = value == expected; + kit_tests_list.v[i].value[n] = value; + kit_tests_list.v[i].expected[n] = expected; +} + +static int64_t ns_to_ms(int64_t ns) { + return (ns + 500000) / 1000000; +} + +static int64_t sec_to_ms(int64_t sec) { + return 1000 * sec; +} + +void kit_test_register(char const *name, char const *file, + kit_test_run_fn fn) { + int n = kit_tests_list.size++; + if (n < KIT_TESTS_SIZE_LIMIT) { + kit_tests_list.v[n].test_fn = fn; + kit_tests_list.v[n].test_name = name; + kit_tests_list.v[n].test_file = file; + kit_tests_list.v[n].assertions = 0; + } +} + +static jmp_buf kit_test_restore_execution; + +static void kit_test_handle_signal(int signum) { + longjmp(kit_test_restore_execution, signum); +} + +static void kit_test_setup_signals() { + for (unsigned i = 0; i < sizeof kit_signums_ / sizeof *kit_signums_; i++) + signal(kit_signums_[i], kit_test_handle_signal); +} + +static int kit_run_test_(volatile int i) { + int signum = setjmp(kit_test_restore_execution); + + if (signum != 0) { + kit_tests_list.v[i].signal = signum; + return 0; + } + + kit_tests_list.v[i].test_fn(i, kit_report_); + return 1; +} + +int kit_run_tests(int argc, char **argv) { + kit_signames_init_(); + + int success_count = 0; + int fail_assertion_count = 0; + int total_assertion_count = 0; + int status = 0; + int quiet = 0; + int no_color = 0; + int line_width = 20; + int carriage_return = 1; + + int i, j; + + char const *specific_test = NULL; + + kit_test_setup_signals(); + + for (i = 0; i < argc; i++) + if (strcmp("--no-term-color", argv[i]) == 0) + no_color = 1; + else if (strcmp("--no-carriage-return", argv[i]) == 0) + carriage_return = 0; + else if (strcmp("--quiet", argv[i]) == 0) + quiet = 1; + else if (strcmp("--match", argv[i]) == 0) + specific_test = argv[++i]; + + quiet && (no_color = 1); + + if (specific_test != NULL) { + no_color || kit_print_color_(kit_light_); + quiet || printf("Run tests matching "); + no_color || kit_print_color_(kit_white_); + quiet || printf("*%s*", specific_test); + no_color || kit_print_color_(kit_light_); + quiet || printf("\n\n"); + } + + char const *file = NULL; + ptrdiff_t file_root = -1; + int tests_total = 0; + + for (i = 0; i < kit_tests_list.size && i < KIT_TESTS_SIZE_LIMIT; + i++) { + if (specific_test != NULL && + strstr(kit_tests_list.v[i].test_name, specific_test) == NULL) + continue; + tests_total++; + int l = 2 + (int) strlen(kit_tests_list.v[i].test_name); + if (line_width < l) + line_width = l; + } + + if (tests_total > 0) { + char const *s = kit_tests_list.v[0].test_file; + + for (j = 1; j < kit_tests_list.size && j < KIT_TESTS_SIZE_LIMIT; + j++) { + if (specific_test != NULL && + strstr(kit_tests_list.v[j].test_name, specific_test) == + NULL) + continue; + if (strcmp(s, kit_tests_list.v[j].test_file) == 0) + continue; + int k = 0; + for (; + s[k] != '\0' && kit_tests_list.v[j].test_file[k] != '\0' && + s[k] == kit_tests_list.v[j].test_file[k]; + k++) { } + if (file_root == -1 || file_root > k) + file_root = k; + } + + if (file_root == -1) { + for (i = 0; s[i] != '\0'; i++) + if (s[i] == '/' || s[i] == '\\') + file_root = i + 1; + } + } + + for (i = 0; i < kit_tests_list.size && i < KIT_TESTS_SIZE_LIMIT; + i++) { + if (specific_test != NULL && + strstr(kit_tests_list.v[i].test_name, specific_test) == NULL) + continue; + if (file == NULL || + strcmp(file, kit_tests_list.v[i].test_file) != 0) { + if (file != NULL) + quiet || printf("\n"); + file = kit_tests_list.v[i].test_file; + no_color || kit_print_color_(kit_blue_); + quiet || printf("* "); + no_color || kit_print_color_(kit_white_); + quiet || printf("%s\n", file + file_root); + } + + !carriage_return || no_color || kit_print_color_(kit_yellow_); + carriage_return || no_color || kit_print_color_(kit_light_); + quiet || printf("` %s ", kit_tests_list.v[i].test_name); + !carriage_return || quiet || printf("\r"); + quiet || fflush(stdout); + + struct timespec begin, end; + timespec_get(&begin, TIME_UTC); + + int test_status = kit_run_test_(i); + + timespec_get(&end, TIME_UTC); + int duration = (int) (ns_to_ms(end.tv_nsec - begin.tv_nsec) + + sec_to_ms(end.tv_sec - begin.tv_sec)); + + for (j = 0; j < kit_tests_list.v[i].assertions && + j < KIT_TEST_ASSERTIONS_LIMIT; + j++) + if (kit_tests_list.v[i].status[j] == 0) { + fail_assertion_count++; + test_status = 0; + } + + if (kit_tests_list.v[i].assertions > KIT_TEST_ASSERTIONS_LIMIT) + test_status = 0; + + total_assertion_count += kit_tests_list.v[i].assertions; + + !carriage_return || no_color || kit_print_color_(kit_light_); + !carriage_return || quiet || + printf("` %s ", kit_tests_list.v[i].test_name); + + int l = (int) strlen(kit_tests_list.v[i].test_name); + quiet || printf("%*c", line_width - l, ' '); + + if (test_status == 0) { + no_color || kit_print_color_(kit_red_); + quiet || printf("FAIL"); + no_color || kit_print_color_(kit_light_); + duration == 0 || quiet || printf(" %d ms", duration); + quiet || printf("\n"); + status = 1; + } else { + no_color || kit_print_color_(kit_green_); + quiet || printf("OK"); + no_color || kit_print_color_(kit_light_); + duration == 0 || quiet || printf(" %d ms", duration); + quiet || printf("\n"); + success_count++; + } + + quiet || fflush(stdout); + } + + no_color || kit_print_color_(kit_white_); + quiet || printf("\n%d of %d tests passed.\n", success_count, + tests_total); + quiet || printf("%d of %d assertions passed.\n\n", + total_assertion_count - fail_assertion_count, + total_assertion_count); + + no_color || kit_print_color_(kit_light_); + + if (!quiet && status != 0) { + int have_kit_report_s = 0; + + for (i = 0; i < kit_tests_list.size && i < KIT_TESTS_SIZE_LIMIT; + i++) { + if (specific_test != NULL && + strstr(kit_tests_list.v[i].test_name, specific_test) == + NULL) + continue; + if (kit_tests_list.v[i].signal != 0) { + int signum = kit_tests_list.v[i].signal; + if (signum >= 0 && + signum < (int) (sizeof kit_signames_ / sizeof *kit_signames_) && + kit_signames_[signum] != NULL) { + no_color || kit_print_color_(kit_light_); + printf("Signal \"%s\" (%d) for \"", kit_signames_[signum], + signum); + no_color || kit_print_color_(kit_white_); + printf("%s", kit_tests_list.v[i].test_name); + no_color || kit_print_color_(kit_light_); + printf("\" in \""); + no_color || kit_print_color_(kit_white_); + + printf("%s", kit_tests_list.v[i].test_file + file_root); + no_color || kit_print_color_(kit_light_); + printf("\"!\n"); + } else { + no_color || kit_print_color_(kit_light_); + printf("Unknown signal (%d) for \"", signum); + no_color || kit_print_color_(kit_white_); + printf("%s", kit_tests_list.v[i].test_name); + no_color || kit_print_color_(kit_light_); + printf("\" in \""); + no_color || kit_print_color_(kit_white_); + + printf("%s", kit_tests_list.v[i].test_file + file_root); + no_color || kit_print_color_(kit_light_); + printf("\"!\n"); + } + have_kit_report_s = 1; + } + if (kit_tests_list.v[i].assertions > + KIT_TEST_ASSERTIONS_LIMIT) { + no_color || kit_print_color_(kit_light_); + printf("Too many assertions for \""); + no_color || kit_print_color_(kit_white_); + printf("%s", kit_tests_list.v[i].test_name); + no_color || kit_print_color_(kit_light_); + printf("\" in \""); + no_color || kit_print_color_(kit_white_); + + printf("%s", kit_tests_list.v[i].test_file + file_root); + no_color || kit_print_color_(kit_light_); + printf("\"!\n"); + have_kit_report_s = 1; + } + } + + have_kit_report_s &&printf("\n"); + } + + if (!quiet && status != 0) { + for (i = 0; i < kit_tests_list.size && i < KIT_TESTS_SIZE_LIMIT; + i++) { + if (specific_test != NULL && + strstr(kit_tests_list.v[i].test_name, specific_test) == + NULL) + continue; + + if (kit_tests_list.v[i].assertions <= KIT_TEST_ASSERTIONS_LIMIT) + for (j = 0; j < kit_tests_list.v[i].assertions; j++) + if (!kit_tests_list.v[i].status[j]) { + no_color || kit_print_color_(kit_light_); + printf("Assertion on line "); + no_color || kit_print_color_(kit_white_); + printf("%d", kit_tests_list.v[i].line[j]); + no_color || kit_print_color_(kit_light_); + printf(" in \""); + no_color || kit_print_color_(kit_white_); + printf("%s", kit_tests_list.v[i].test_file + file_root); + no_color || kit_print_color_(kit_light_); + printf("\" failed.\n"); + no_color || kit_print_color_(kit_red_); + printf(" -> "); + no_color || kit_print_color_(kit_light_); + printf("Got wrong value "); + no_color || kit_print_color_(kit_white_); + printf("%10lld", + (long long) kit_tests_list.v[i].value[j]); + no_color || kit_print_color_(kit_light_); + printf(" ("); + no_color || kit_print_color_(kit_white_); + printf("0x%08llx", + (unsigned long long) kit_tests_list.v[i].value[j]); + no_color || kit_print_color_(kit_light_); + printf(")\n"); + no_color || kit_print_color_(kit_green_); + printf(" -> "); + no_color || kit_print_color_(kit_light_); + printf("Expected value "); + no_color || kit_print_color_(kit_white_); + printf("%10lld", + (long long) kit_tests_list.v[i].expected[j]); + no_color || kit_print_color_(kit_light_); + printf(" ("); + no_color || kit_print_color_(kit_white_); + printf( + "0x%08llx", + (unsigned long long) kit_tests_list.v[i].expected[j]); + no_color || kit_print_color_(kit_light_); + printf(")\n\n"); + } + } + } + + if (kit_tests_list.size > KIT_TESTS_SIZE_LIMIT) { + no_color || kit_print_color_(kit_light_); + quiet || printf("Too many tests!\n\n"); + status = 1; + } + + if (status == 0) { + no_color || kit_print_color_(kit_green_); + quiet || printf("OK\n"); + } else { + no_color || kit_print_color_(kit_red_); + quiet || printf("FAILED\n"); + } + + no_color || kit_print_color_(kit_light_); + quiet || printf("\n"); + return status; +} + +kit_benchs_list_t kit_benchs_list = { 0 }; + +static void bench_set_repeats_limit(int i, int repeats_limit) { + if (kit_benchs_list.v[i].ready) + return; + if (kit_benchs_list.v[i].cycles_size >= KIT_BENCH_MAX_CYCLES) + return; + kit_benchs_list.v[i].cycles[kit_benchs_list.v[i].cycles_size] = + repeats_limit; + kit_benchs_list.v[i].cycles_size++; +} + +static int bench_loop(int i) { + if (!kit_benchs_list.v[i].ready) + return 0; + return kit_benchs_list.v[i].repeats < + kit_benchs_list.v[i].cycles[kit_benchs_list.v[i].cycle]; +} + +static void bench_begin(int i) { + int n = kit_benchs_list.v[i].repeats++; + + if (n >= KIT_BENCH_MAX_REPEATS) + return; + + struct timespec tv; + timespec_get(&tv, TIME_UTC); + + kit_benchs_list.v[i].sec[n] = (int64_t) tv.tv_sec; + kit_benchs_list.v[i].nsec[n] = (int64_t) tv.tv_nsec; +} + +static void bench_end(int i) { + int n = kit_benchs_list.v[i].repeats - 1; + + if (n < 0 || n >= KIT_BENCH_MAX_REPEATS) + return; + + struct timespec tv; + timespec_get(&tv, TIME_UTC); + + int64_t sec = ((int64_t) tv.tv_sec) - kit_benchs_list.v[i].sec[n]; + int64_t nsec = ((int64_t) tv.tv_nsec) - + kit_benchs_list.v[i].nsec[n]; + + kit_benchs_list.v[i].duration_nsec[n] = sec * 1000000000 + nsec; +} + +void kit_bench_register(char const *name, char const *file, + kit_bench_run_fn fn) { + int n = kit_benchs_list.size++; + if (n < KIT_BENCHS_SIZE_LIMIT) { + kit_benchmark_t *bench = kit_benchs_list.v + n; + + bench->bench_fn = fn; + bench->bench_name = name; + bench->bench_file = file; + bench->cycles_size = 0; + bench->ready = 0; + } +} + +static void kit_bench_setup_signals() { + for (unsigned i = 0; i < sizeof kit_signums_ / sizeof *kit_signums_; i++) + signal(kit_signums_[i], kit_test_handle_signal); +} + +static int kit_run_bench_(volatile int i) { + int signum = setjmp(kit_test_restore_execution); + + if (signum != 0) { + kit_benchs_list.v[i].signal = signum; + return 0; + } + + kit_benchs_list.v[i].bench_fn(i, bench_set_repeats_limit, + bench_loop, bench_begin, bench_end); + return 1; +} + +static int kit_compare_64_(void const *x_, void const *y_) { + int64_t const *x = (int64_t const *) x_; + int64_t const *y = (int64_t const *) y_; + return *x - *y; +} + +static int kit_compare_32_(void const *x_, void const *y_) { + int const *x = (int const *) x_; + int const *y = (int const *) y_; + return *x - *y; +} + +int kit_run_benchmarks(int argc, char **argv) { + int success_count = 0; + int status = 0; + int no_color = 0; + int line_width = 20; + int carriage_return = 1; + + char const *specific_bench = NULL; + + kit_bench_setup_signals(); + + for (int i = 0; i < argc; i++) + if (strcmp("--no-term-color", argv[i]) == 0) + no_color = 1; + else if (strcmp("--no-carriage-return", argv[i]) == 0) + carriage_return = 0; + else if (strcmp("--match", argv[i]) == 0) + specific_bench = argv[++i]; + + if (specific_bench != NULL) { + no_color || kit_print_color_(kit_light_); + printf("Run benchmarks matching "); + no_color || kit_print_color_(kit_white_); + printf("*%s*", specific_bench); + no_color || kit_print_color_(kit_light_); + printf("\n\n"); + } + + char const *file = NULL; + ptrdiff_t file_root = -1; + int benchs_total = 0; + + for (int i = 0; + i < kit_benchs_list.size && i < KIT_BENCHS_SIZE_LIMIT; i++) { + if (specific_bench != NULL && + strstr(kit_benchs_list.v[i].bench_name, specific_bench) == + NULL) + continue; + benchs_total++; + int l = 2 + (int) strlen(kit_benchs_list.v[i].bench_name); + if (line_width < l) + line_width = l; + } + + if (benchs_total > 0) { + char const *s = kit_benchs_list.v[0].bench_file; + + for (int j = 1; + j < kit_benchs_list.size && j < KIT_BENCHS_SIZE_LIMIT; j++) { + kit_benchmark_t *bench = kit_benchs_list.v + j; + + if (specific_bench != NULL && + strstr(bench->bench_name, specific_bench) == NULL) + continue; + if (strcmp(s, bench->bench_file) == 0) + continue; + int k = 0; + for (; s[k] != '\0' && bench->bench_file[k] != '\0' && + s[k] == bench->bench_file[k]; + k++) { } + if (file_root == -1 || file_root > k) + file_root = k; + } + + if (file_root == -1) { + for (int i = 0; s[i] != '\0'; i++) + if (s[i] == '/' || s[i] == '\\') + file_root = i + 1; + } + } + + no_color || kit_print_color_(kit_blue_); + printf("# "); + no_color || kit_print_color_(kit_light_); + printf("BENCHMARK"); + printf("%*c", line_width - 9, ' '); + no_color || kit_print_color_(kit_green_); + printf(" LOW "); + no_color || kit_print_color_(kit_light_); + printf("|"); + no_color || kit_print_color_(kit_blue_); + printf(" MEDIAN "); + no_color || kit_print_color_(kit_light_); + printf("|"); + no_color || kit_print_color_(kit_yellow_); + printf(" HIGH\n"); + no_color || kit_print_color_(kit_light_); + printf(" (in microseconds)\n\n"); + + /* Prepare cycles. + */ + + for (int i = 0; + i < kit_benchs_list.size && i < KIT_BENCHS_SIZE_LIMIT; i++) { + kit_benchmark_t *bench = kit_benchs_list.v + i; + + if (specific_bench != NULL && + strstr(bench->bench_name, specific_bench) == NULL) + continue; + + kit_run_bench_(i); + + if (bench->cycles_size == 0) { + bench->cycles_size = 2; + bench->cycles[0] = KIT_BENCH_REPEATS_DEFAULT_1; + bench->cycles[1] = KIT_BENCH_REPEATS_DEFAULT_2; + } + + qsort(bench->cycles, bench->cycles_size, sizeof *bench->cycles, + kit_compare_32_); + + kit_benchs_list.v[i].ready = 1; + } + + /* Run cycles. + */ + + for (int cycle = 0; cycle < KIT_BENCH_MAX_CYCLES; cycle++) { + /* Prepare cycle. + */ + + int cycles_done = 1; + + for (int i = 0; + i < kit_benchs_list.size && i < KIT_BENCHS_SIZE_LIMIT; i++) { + kit_benchmark_t *bench = kit_benchs_list.v + i; + + if (specific_bench != NULL && + strstr(bench->bench_name, specific_bench) == NULL) + continue; + if (cycle >= bench->cycles_size) + continue; + + bench->repeats = 0; + bench->cycle = cycle; + cycles_done = 0; + } + + if (cycles_done) + break; + + /* Run benchmarks. + */ + + for (int i = 0; + i < kit_benchs_list.size && i < KIT_BENCHS_SIZE_LIMIT; i++) { + kit_benchmark_t *bench = kit_benchs_list.v + i; + + if (specific_bench != NULL && + strstr(bench->bench_name, specific_bench) == NULL) + continue; + if (cycle >= bench->cycles_size) + continue; + + if (file == NULL || strcmp(file, bench->bench_file) != 0) { + if (file != NULL) + printf("\n"); + file = bench->bench_file; + no_color || kit_print_color_(kit_blue_); + printf("* "); + no_color || kit_print_color_(kit_white_); + printf("%s\n", file + file_root); + } + + !carriage_return || no_color || kit_print_color_(kit_yellow_); + carriage_return || no_color || kit_print_color_(kit_light_); + printf("` %s ", bench->bench_name); + !carriage_return || printf("\r"); + fflush(stdout); + + int bench_status = kit_run_bench_(i); + + if (bench->repeats > KIT_BENCH_MAX_REPEATS) + bench_status = 0; + + !carriage_return || no_color || kit_print_color_(kit_light_); + !carriage_return || printf("` %s ", bench->bench_name); + + int l = (int) strlen(bench->bench_name); + printf("%*c", line_width - l, ' '); + + if (bench->repeats <= 0) { + no_color || kit_print_color_(kit_yellow_); + printf(" 0 runs\n"); + success_count++; + } else if (bench_status == 0) { + no_color || kit_print_color_(kit_red_); + printf(" FAIL\n"); + status = 1; + } else { + int repeats = bench->repeats; + + memcpy(bench->duration_sorted_nsec, bench->duration_nsec, + repeats * sizeof *bench->duration_sorted_nsec); + qsort(bench->duration_sorted_nsec, repeats, + sizeof *bench->duration_sorted_nsec, kit_compare_64_); + + int64_t average = bench->duration_sorted_nsec[repeats / 2]; + int64_t floor = bench->duration_sorted_nsec[repeats / 20]; + int64_t roof = + bench->duration_sorted_nsec[repeats - repeats / 20 - 1]; + + no_color || kit_print_color_(kit_white_); + printf("%-9g", (double) floor * 0.001); + no_color || kit_print_color_(kit_light_); + printf("| "); + no_color || kit_print_color_(kit_white_); + printf("%-9g", (double) average * 0.001); + no_color || kit_print_color_(kit_light_); + printf("| "); + no_color || kit_print_color_(kit_white_); + printf("%-9g", (double) roof * 0.001); + no_color || kit_print_color_(kit_light_); + printf(" %d runs\n", repeats); + success_count++; + } + } + } + + printf("\n"); + + if (status != 0) { + for (int i = 0; + i < kit_benchs_list.size && i < KIT_BENCHS_SIZE_LIMIT; i++) { + kit_benchmark_t *bench = kit_benchs_list.v + i; + + if (specific_bench != NULL && + strstr(bench->bench_name, specific_bench) == NULL) + continue; + if (bench->signal != 0) { + int signum = bench->signal; + if (signum >= 0 && + signum < (int) (sizeof kit_signames_ / sizeof *kit_signames_) && + kit_signames_[signum] != NULL) { + no_color || kit_print_color_(kit_light_); + printf("Signal \"%s\" (%d) for \"", kit_signames_[signum], + signum); + no_color || kit_print_color_(kit_white_); + printf("%s", bench->bench_name); + no_color || kit_print_color_(kit_light_); + printf("\" in \""); + no_color || kit_print_color_(kit_white_); + printf("%s", bench->bench_file + file_root); + no_color || kit_print_color_(kit_light_); + printf("\"!.\n"); + } else { + no_color || kit_print_color_(kit_light_); + printf("Unknown signal (%d) for \"", signum); + no_color || kit_print_color_(kit_white_); + printf("%s", bench->bench_name); + no_color || kit_print_color_(kit_light_); + printf("\" in \""); + no_color || kit_print_color_(kit_white_); + printf("%s", bench->bench_file + file_root); + no_color || kit_print_color_(kit_light_); + printf("\"!.\n"); + } + } + } + + printf("\n"); + } + + if (kit_benchs_list.size > KIT_BENCHS_SIZE_LIMIT) { + no_color || kit_print_color_(kit_light_); + printf("Too many benchmarks!\n\n"); + status = 1; + } + + if (status == 0) { + no_color || kit_print_color_(kit_green_); + printf("DONE\n"); + } else { + no_color || kit_print_color_(kit_red_); + printf("DONE WITH ERRORS\n"); + } + + no_color || kit_print_color_(kit_light_); + printf("\n"); + return status; +} + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/kit/threads.h b/kit/threads.h new file mode 100644 index 0000000..a636e99 --- /dev/null +++ b/kit/threads.h @@ -0,0 +1,129 @@ +#ifndef KIT_THREADS_H +#define KIT_THREADS_H +#ifndef KIT_DISABLE_SYSTEM_THREADS + +# include "time.h" + +# include <stddef.h> +# include <stdint.h> + +# if !defined(_WIN32) || defined(__CYGWIN__) +# include <pthread.h> +# endif + +# if defined(__cplusplus) +# define _Noreturn [[noreturn]] +# elif defined(_MSC_VER) +# define _Noreturn __declspec(noreturn) +# endif + +# ifndef _Thread_local +# if defined(__cplusplus) +// C++11 doesn't need `_Thread_local` keyword or macro +# elif !defined(__STDC_NO_THREADS__) +// threads are optional in C11, _Thread_local present in this +// condition +# elif defined(_MSC_VER) +# define _Thread_local __declspec(thread) +# elif defined(__GNUC__) +# define _Thread_local __thread +# else +// Leave _Thread_local undefined so that use of _Thread_local would +// not promote to a non-thread-local global variable +# endif +# endif + +# if !defined(__cplusplus) +// C11 thread_local() macro C++11 and above already have thread_local +// keyword +# ifndef thread_local +# if _MSC_VER +# define thread_local __declspec(thread) +# else +# define thread_local _Thread_local +# endif +# endif +# endif + +# ifdef __cplusplus +extern "C" { +# endif + +enum { + mtx_plain, + mtx_recursive, + mtx_timed, +}; + +enum { + thrd_success, + thrd_timedout, + thrd_error, + thrd_busy, + thrd_nomem, + thrd_wrong_stack_size +}; + +# if defined(_WIN32) && !defined(__CYGWIN__) +typedef struct { + void *DebugInfo; + long LockCount; + long RecursionCount; + void *OwningThread; + void *LockSemaphore; + uintptr_t SpinCount; +} mtx_t; + +typedef struct { + void *Ptr; +} cnd_t; + +typedef struct { + volatile uintptr_t status; +} once_flag; + +typedef struct { + void *handle; +} thrd_t; + +# else +typedef pthread_mutex_t mtx_t; +typedef pthread_cond_t cnd_t; +typedef pthread_once_t once_flag; +typedef pthread_t thrd_t; +# endif + +typedef int (*thrd_start_t)(void *); + +void mtx_destroy(mtx_t *mtx_); +int mtx_init(mtx_t *mtx_, int); +int mtx_lock(mtx_t *mtx_); +int mtx_timedlock(mtx_t *__restrict mtx_, + struct timespec const *__restrict); +int mtx_trylock(mtx_t *mtx_); +int mtx_unlock(mtx_t *mtx_); +void call_once(once_flag *, void (*)(void)); +int cnd_broadcast(cnd_t *); +void cnd_destroy(cnd_t *); +int cnd_init(cnd_t *); +int cnd_signal(cnd_t *); +int cnd_timedwait(cnd_t *__restrict, mtx_t *__restrict mtx_, + struct timespec const *__restrict); +int cnd_wait(cnd_t *, mtx_t *mtx_); +int thrd_create(thrd_t *, thrd_start_t, void *); +int thrd_create_with_stack(thrd_t *, thrd_start_t, void *, + ptrdiff_t stack_size); +thrd_t thrd_current(void); +int thrd_detach(thrd_t); +int thrd_equal(thrd_t, thrd_t); +_Noreturn void thrd_exit(int); +int thrd_join(thrd_t, int *); +int thrd_sleep(struct timespec const *, struct timespec *); +void thrd_yield(void); + +# ifdef __cplusplus +} +# endif + +#endif +#endif diff --git a/kit/threads.posix.c b/kit/threads.posix.c new file mode 100644 index 0000000..44465a3 --- /dev/null +++ b/kit/threads.posix.c @@ -0,0 +1,271 @@ +#include "threads.h" + +#ifndef KIT_DISABLE_SYSTEM_THREADS +# include "allocator.h" + +# if !defined(_WIN32) || defined(__CYGWIN__) +# include <assert.h> +# include <errno.h> +# include <limits.h> +# include <sched.h> +# include <stdlib.h> +# include <unistd.h> + +# ifndef PTHREAD_STACK_MIN +# define PTHREAD_STACK_MIN 16384 +# endif + +/* +Configuration macro: + + EMULATED_THREADS_USE_NATIVE_TIMEDLOCK + Use pthread_mutex_timedlock() for `mtx_timedlock()' + Otherwise use mtx_trylock() + *busy loop* emulation. +*/ +# if !defined(__CYGWIN__) && !defined(__APPLE__) && \ + !defined(__NetBSD__) +# define EMULATED_THREADS_USE_NATIVE_TIMEDLOCK +# endif + +/* +Implementation limits: + - Conditionally emulation for "mutex with timeout" + (see EMULATED_THREADS_USE_NATIVE_TIMEDLOCK macro) +*/ +typedef struct { + thrd_start_t func; + void *arg; +} impl_thrd_param_t; + +static void *impl_thrd_routine(void *p) { + impl_thrd_param_t pack = *((impl_thrd_param_t *) p); + kit_alloc_dispatch(NULL, KIT_DEALLOCATE, 0, 0, p); + return (void *) (intptr_t) pack.func(pack.arg); +} + +void call_once(once_flag *flag, void (*func)(void)) { + pthread_once(flag, func); +} + +int cnd_broadcast(cnd_t *cond) { + assert(cond != NULL); + return (pthread_cond_broadcast(cond) == 0) ? thrd_success + : thrd_error; +} + +void cnd_destroy(cnd_t *cond) { + assert(cond); + pthread_cond_destroy(cond); +} + +int cnd_init(cnd_t *cond) { + assert(cond != NULL); + return (pthread_cond_init(cond, NULL) == 0) ? thrd_success + : thrd_error; +} + +int cnd_signal(cnd_t *cond) { + assert(cond != NULL); + return (pthread_cond_signal(cond) == 0) ? thrd_success : thrd_error; +} + +int cnd_timedwait(cnd_t *cond, mtx_t *mtx, + struct timespec const *abs_time) { + int rt; + + assert(mtx != NULL); + assert(cond != NULL); + assert(abs_time != NULL); + + rt = pthread_cond_timedwait(cond, mtx, abs_time); + if (rt == ETIMEDOUT) + return thrd_timedout; + return (rt == 0) ? thrd_success : thrd_error; +} + +int cnd_wait(cnd_t *cond, mtx_t *mtx) { + assert(mtx != NULL); + assert(cond != NULL); + return (pthread_cond_wait(cond, mtx) == 0) ? thrd_success + : thrd_error; +} + +void mtx_destroy(mtx_t *mtx) { + assert(mtx != NULL); + pthread_mutex_destroy(mtx); +} + +/* + * XXX: Workaround when building with -O0 and without pthreads link. + * + * In such cases constant folding and dead code elimination won't be + * available, thus the compiler will always add the pthread_mutexattr* + * functions into the binary. As we try to link, we'll fail as the + * symbols are unresolved. + * + * Ideally we'll enable the optimisations locally, yet that does not + * seem to work. + * + * So the alternative workaround is to annotate the symbols as weak. + * Thus the linker will be happy and things don't clash when building + * with -O1 or greater. + */ +# if defined(KIT_HAVE_FUNC_ATTRIBUTE_WEAK) && !defined(__CYGWIN__) +__attribute__((weak)) int pthread_mutexattr_init( + pthread_mutexattr_t *attr); + +__attribute__((weak)) int pthread_mutexattr_settype( + pthread_mutexattr_t *attr, int type); + +__attribute__((weak)) int pthread_mutexattr_destroy( + pthread_mutexattr_t *attr); +# endif + +int mtx_init(mtx_t *mtx, int type) { +# ifdef KIT_HAVE_PTHREAD_MUTEXATTR_SETTYPE + pthread_mutexattr_t attr; +# endif + assert(mtx != NULL); + if (type != mtx_plain && type != mtx_timed && + type != (mtx_plain | mtx_recursive) && + type != (mtx_timed | mtx_recursive)) + return thrd_error; + + if ((type & mtx_recursive) == 0) { + pthread_mutex_init(mtx, NULL); + return thrd_success; + } + +# ifdef KIT_HAVE_PTHREAD_MUTEXATTR_SETTYPE + pthread_mutexattr_init(&attr); + pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE); + pthread_mutex_init(mtx, &attr); + pthread_mutexattr_destroy(&attr); + return thrd_success; +# else + return thrd_error; +# endif +} + +int mtx_lock(mtx_t *mtx) { + assert(mtx != NULL); + return (pthread_mutex_lock(mtx) == 0) ? thrd_success : thrd_error; +} + +int mtx_timedlock(mtx_t *mtx, const struct timespec *ts) { + assert(mtx != NULL); + assert(ts != NULL); + + { +# ifdef EMULATED_THREADS_USE_NATIVE_TIMEDLOCK + int rt; + rt = pthread_mutex_timedlock(mtx, ts); + if (rt == 0) + return thrd_success; + return (rt == ETIMEDOUT) ? thrd_timedout : thrd_error; +# else + time_t expire = time(NULL); + expire += ts->tv_sec; + while (mtx_trylock(mtx) != thrd_success) { + time_t now = time(NULL); + if (expire < now) + return thrd_timedout; + // busy loop! + thrd_yield(); + } + return thrd_success; +# endif + } +} + +int mtx_trylock(mtx_t *mtx) { + assert(mtx != NULL); + return (pthread_mutex_trylock(mtx) == 0) ? thrd_success : thrd_busy; +} + +int mtx_unlock(mtx_t *mtx) { + assert(mtx != NULL); + return (pthread_mutex_unlock(mtx) == 0) ? thrd_success : thrd_error; +} + +int thrd_create_with_stack(thrd_t *thr, thrd_start_t func, void *arg, + ptrdiff_t const require_stack_size) { + impl_thrd_param_t *pack; + assert(thr != NULL); + assert(require_stack_size == 0 || + require_stack_size >= PTHREAD_STACK_MIN); + pthread_attr_t attr; + pthread_attr_t *attr_p = NULL; + if (require_stack_size > 0) { + ptrdiff_t const page_size = (ptrdiff_t) sysconf(_SC_PAGESIZE); + ptrdiff_t const delta = require_stack_size % page_size; + ptrdiff_t const stack_size = delta == 0 ? require_stack_size + : require_stack_size + + page_size - delta; + if (pthread_attr_init(&attr) != 0) + return thrd_nomem; + if (pthread_attr_setstacksize(&attr, (size_t) stack_size) != 0) + return thrd_wrong_stack_size; + attr_p = &attr; + } + + pack = (impl_thrd_param_t *) kit_alloc_dispatch( + NULL, KIT_ALLOCATE, sizeof(impl_thrd_param_t), 0, NULL); + if (!pack) { + if (attr_p) + pthread_attr_destroy(attr_p); + return thrd_nomem; + } + pack->func = func; + pack->arg = arg; + if (pthread_create(thr, attr_p, impl_thrd_routine, pack) != 0) { + kit_alloc_dispatch(NULL, KIT_DEALLOCATE, 0, 0, pack); + if (attr_p) + pthread_attr_destroy(attr_p); + return thrd_error; + } + if (attr_p) + pthread_attr_destroy(attr_p); + return thrd_success; +} + +int thrd_create(thrd_t *thr, thrd_start_t func, void *arg) { + return thrd_create_with_stack(thr, func, arg, 0); +} +thrd_t thrd_current(void) { + return pthread_self(); +} + +int thrd_detach(thrd_t thr) { + return (pthread_detach(thr) == 0) ? thrd_success : thrd_error; +} + +int thrd_equal(thrd_t thr0, thrd_t thr1) { + return pthread_equal(thr0, thr1); +} + +_Noreturn void thrd_exit(int res) { + pthread_exit((void *) (intptr_t) res); +} + +int thrd_join(thrd_t thr, int *res) { + void *code; + if (pthread_join(thr, &code) != 0) + return thrd_error; + if (res) + *res = (int) (intptr_t) code; + return thrd_success; +} + +int thrd_sleep(const struct timespec *time_point, + struct timespec *remaining) { + assert(time_point != NULL); + return nanosleep(time_point, remaining); +} + +void thrd_yield(void) { + sched_yield(); +} + +# endif +#endif diff --git a/kit/threads.win32.c b/kit/threads.win32.c new file mode 100644 index 0000000..ac185f7 --- /dev/null +++ b/kit/threads.win32.c @@ -0,0 +1,342 @@ +#include "threads.h" + +#ifndef KIT_DISABLE_SYSTEM_THREADS +# include "allocator.h" + +# if defined(_WIN32) && !defined(__CYGWIN__) +# include <assert.h> +# include <errno.h> +# include <limits.h> +# include <process.h> +# include <stdlib.h> + +# ifndef WIN32_LEAN_AND_MEAN +# define WIN32_LEAN_AND_MEAN 1 +# endif +# ifndef NOMINMAX +# define NOMINMAX +# endif +# include <windows.h> + +/* +Configuration macro: + + EMULATED_THREADS_USE_NATIVE_CALL_ONCE + Use native WindowsAPI one-time initialization function. + (requires WinVista or later) + Otherwise emulate by mtx_trylock() + *busy loop* for WinXP. +*/ + +# if _WIN32_WINNT >= 0x0600 +/* Prefer native WindowsAPI on newer environment. */ +# if !defined(__MINGW32__) +# define EMULATED_THREADS_USE_NATIVE_CALL_ONCE +# endif +# endif + +/* check configuration */ +# if defined(EMULATED_THREADS_USE_NATIVE_CALL_ONCE) && \ + (_WIN32_WINNT < 0x0600) +# error EMULATED_THREADS_USE_NATIVE_CALL_ONCE requires _WIN32_WINNT>=0x0600 +# endif + +static_assert(sizeof(cnd_t) == sizeof(CONDITION_VARIABLE), + "The size of cnd_t must equal to CONDITION_VARIABLE"); +static_assert(sizeof(thrd_t) == sizeof(HANDLE), + "The size of thrd_t must equal to HANDLE"); +static_assert(sizeof(mtx_t) == sizeof(CRITICAL_SECTION), + "The size of mtx_t must equal to CRITICAL_SECTION"); +static_assert(sizeof(once_flag) == sizeof(INIT_ONCE), + "The size of once_flag must equal to INIT_ONCE"); + +/* +Implementation limits: + - Conditionally emulation for "Initialization functions" + (see EMULATED_THREADS_USE_NATIVE_CALL_ONCE macro) + - Emulated `mtx_timelock()' with mtx_trylock() + *busy loop* +*/ + +typedef struct { + thrd_start_t func; + void *arg; + thrd_t thrd; +} impl_thrd_param_t; + +struct thrd_state { + thrd_t thrd; + int handle_need_close; +}; + +static thread_local struct thrd_state impl_current_thread = { 0 }; + +static unsigned __stdcall impl_thrd_routine(void *p) { + impl_thrd_param_t *pack_p = (impl_thrd_param_t *) p; + impl_thrd_param_t pack; + int code; + impl_current_thread.thrd = pack_p->thrd; + impl_current_thread.handle_need_close = 0; + memcpy(&pack, pack_p, sizeof(impl_thrd_param_t)); + kit_alloc_dispatch(NULL, KIT_DEALLOCATE, 0, 0, p); + code = pack.func(pack.arg); + return (unsigned) code; +} + +static time_t impl_timespec2msec(const struct timespec *ts) { + return (ts->tv_sec * 1000U) + (ts->tv_nsec / 1000000L); +} + +static DWORD impl_abs2relmsec(const struct timespec *abs_time) { + const time_t abs_ms = impl_timespec2msec(abs_time); + struct timespec now; + timespec_get(&now, TIME_UTC); + const time_t now_ms = impl_timespec2msec(&now); + const DWORD rel_ms = (abs_ms > now_ms) ? (DWORD) (abs_ms - now_ms) + : 0; + return rel_ms; +} + +# ifdef EMULATED_THREADS_USE_NATIVE_CALL_ONCE +struct impl_call_once_param { + void (*func)(void); +}; + +static BOOL CALLBACK impl_call_once_callback(PINIT_ONCE InitOnce, + PVOID Parameter, + PVOID *Context) { + struct impl_call_once_param *param = (struct impl_call_once_param *) + Parameter; + (param->func)(); + ((void) InitOnce); + ((void) Context); /* suppress warning */ + return TRUE; +} +# endif /* ifdef EMULATED_THREADS_USE_NATIVE_CALL_ONCE */ + +void call_once(once_flag *flag, void (*func)(void)) { + assert(flag && func); +# ifdef EMULATED_THREADS_USE_NATIVE_CALL_ONCE + { + struct impl_call_once_param param; + param.func = func; + InitOnceExecuteOnce((PINIT_ONCE) flag, impl_call_once_callback, + (PVOID) ¶m, NULL); + } +# else + if (InterlockedCompareExchangePointer( + (PVOID volatile *) &flag->status, (PVOID) 1, (PVOID) 0) == + 0) { + (func)(); + InterlockedExchangePointer((PVOID volatile *) &flag->status, + (PVOID) 2); + } else { + while (flag->status == 1) { + // busy loop! + thrd_yield(); + } + } +# endif +} + +int cnd_broadcast(cnd_t *cond) { + assert(cond != NULL); + WakeAllConditionVariable((PCONDITION_VARIABLE) cond); + return thrd_success; +} + +void cnd_destroy(cnd_t *cond) { + assert(cond != NULL); + /* do nothing */ + (void) cond; +} + +int cnd_init(cnd_t *cond) { + assert(cond != NULL); + InitializeConditionVariable((PCONDITION_VARIABLE) cond); + return thrd_success; +} + +int cnd_signal(cnd_t *cond) { + assert(cond != NULL); + WakeConditionVariable((PCONDITION_VARIABLE) cond); + return thrd_success; +} + +int cnd_timedwait(cnd_t *cond, mtx_t *mtx, + const struct timespec *abs_time) { + assert(cond != NULL); + assert(mtx != NULL); + assert(abs_time != NULL); + const DWORD timeout = impl_abs2relmsec(abs_time); + if (SleepConditionVariableCS((PCONDITION_VARIABLE) cond, + (PCRITICAL_SECTION) mtx, timeout)) + return thrd_success; + return (GetLastError() == ERROR_TIMEOUT) ? thrd_timedout + : thrd_error; +} + +int cnd_wait(cnd_t *cond, mtx_t *mtx) { + assert(cond != NULL); + assert(mtx != NULL); + SleepConditionVariableCS((PCONDITION_VARIABLE) cond, + (PCRITICAL_SECTION) mtx, INFINITE); + return thrd_success; +} + +void mtx_destroy(mtx_t *mtx) { + assert(mtx); + DeleteCriticalSection((PCRITICAL_SECTION) mtx); +} + +int mtx_init(mtx_t *mtx, int type) { + assert(mtx != NULL); + if (type != mtx_plain && type != mtx_timed && + type != (mtx_plain | mtx_recursive) && + type != (mtx_timed | mtx_recursive)) + return thrd_error; + InitializeCriticalSection((PCRITICAL_SECTION) mtx); + return thrd_success; +} + +int mtx_lock(mtx_t *mtx) { + assert(mtx != NULL); + EnterCriticalSection((PCRITICAL_SECTION) mtx); + return thrd_success; +} + +int mtx_timedlock(mtx_t *mtx, const struct timespec *ts) { + assert(mtx != NULL); + assert(ts != NULL); + while (mtx_trylock(mtx) != thrd_success) { + if (impl_abs2relmsec(ts) == 0) + return thrd_timedout; + /* busy loop! */ + thrd_yield(); + } + return thrd_success; +} + +int mtx_trylock(mtx_t *mtx) { + assert(mtx != NULL); + return TryEnterCriticalSection((PCRITICAL_SECTION) mtx) + ? thrd_success + : thrd_busy; +} + +int mtx_unlock(mtx_t *mtx) { + assert(mtx != NULL); + LeaveCriticalSection((PCRITICAL_SECTION) mtx); + return thrd_success; +} + +int thrd_create_with_stack(thrd_t *thr, thrd_start_t func, void *arg, + ptrdiff_t const stack_size) { + impl_thrd_param_t *pack; + uintptr_t handle; + assert(thr != NULL); + assert(stack_size >= 0 && stack_size < 0x100000000); + + pack = (impl_thrd_param_t *) kit_alloc_dispatch( + NULL, KIT_ALLOCATE, (sizeof(impl_thrd_param_t)), 0, NULL); + if (!pack) + return thrd_nomem; + pack->func = func; + pack->arg = arg; + handle = _beginthreadex(NULL, (unsigned) stack_size, + impl_thrd_routine, pack, CREATE_SUSPENDED, + NULL); + if (handle == 0) { + kit_alloc_dispatch(NULL, KIT_DEALLOCATE, 0, 0, pack); + if (errno == EAGAIN || errno == EACCES) + return thrd_nomem; + return thrd_error; + } + thr->handle = (void *) handle; + pack->thrd = *thr; + ResumeThread((HANDLE) handle); + return thrd_success; +} + +int thrd_create(thrd_t *thr, thrd_start_t func, void *arg) { + return thrd_create_with_stack(thr, func, arg, 0); +} + +thrd_t thrd_current(void) { + /* GetCurrentThread() returns a pseudo-handle, which we need + * to pass to DuplicateHandle(). Only the resulting handle can be + * used from other threads. + * + * Note that neither handle can be compared to the one by + * thread_create. Only the thread IDs - as returned by GetThreadId() + * and GetCurrentThreadId() can be compared directly. + * + * Other potential solutions would be: + * - define thrd_t as a thread Ids, but this would mean we'd need to + * OpenThread for many operations + * - use malloc'ed memory for thrd_t. This would imply using TLS for + * current thread. + * + * Neither is particularly nice. + * + * Life would be much easier if C11 threads had different + * abstractions for threads and thread IDs, just like C++11 threads + * does... + */ + struct thrd_state *state = &impl_current_thread; + if (state->thrd.handle == NULL) { + if (!DuplicateHandle(GetCurrentProcess(), GetCurrentThread(), + GetCurrentProcess(), &(state->thrd.handle), + 0, FALSE, DUPLICATE_SAME_ACCESS)) { + abort(); + } + state->handle_need_close = 1; + } + return state->thrd; +} + +int thrd_detach(thrd_t thr) { + CloseHandle(thr.handle); + return thrd_success; +} + +int thrd_equal(thrd_t thr0, thrd_t thr1) { + return GetThreadId(thr0.handle) == GetThreadId(thr1.handle); +} + +_Noreturn void thrd_exit(int res) { + _endthreadex((unsigned) res); +} + +int thrd_join(thrd_t thr, int *res) { + DWORD w, code; + if (thr.handle == NULL) { + return thrd_error; + } + w = WaitForSingleObject(thr.handle, INFINITE); + if (w != WAIT_OBJECT_0) + return thrd_error; + if (res) { + if (!GetExitCodeThread(thr.handle, &code)) { + CloseHandle(thr.handle); + return thrd_error; + } + *res = (int) code; + } + CloseHandle(thr.handle); + return thrd_success; +} + +int thrd_sleep(const struct timespec *time_point, + struct timespec *remaining) { + (void) remaining; + assert(time_point); + assert(!remaining); /* not implemented */ + Sleep((DWORD) impl_timespec2msec(time_point)); + return 0; +} + +void thrd_yield(void) { + SwitchToThread(); +} + +# endif +#endif diff --git a/kit/time.h b/kit/time.h new file mode 100644 index 0000000..c14f8ff --- /dev/null +++ b/kit/time.h @@ -0,0 +1,54 @@ +#ifndef KIT_TIME_H +#define KIT_TIME_H + +#ifndef _GNU_SOURCE +# define _GNU_SOURCE +#endif + +#include <time.h> + +#ifdef __cplusplus +extern "C" { +#endif + +#ifndef TIME_UTC +# define TIME_UTC 1 +#endif + +#ifdef KIT_REQUIRE_TIMESPEC_GET +# ifndef WIN32_LEAN_AND_MEAN +# define WIN32_LEAN_AND_MEAN 1 +# endif +# ifndef NOMINMAX +# define NOMINMAX 1 +# endif +# include <windows.h> + +# define KIT_TIMESPEC_IMPL_UNIX_EPOCH_IN_TICKS 116444736000000000ull +# define KIT_TIMESPEC_IMPL_TICKS_PER_SECONDS 10000000ull + +static int timespec_get(struct timespec *ts, int base) { + if (ts == NULL || base != TIME_UTC) + return 0; + + FILETIME ft; + ULARGE_INTEGER date; + LONGLONG ticks; + + GetSystemTimeAsFileTime(&ft); + date.HighPart = ft.dwHighDateTime; + date.LowPart = ft.dwLowDateTime; + ticks = (LONGLONG) (date.QuadPart - + KIT_TIMESPEC_IMPL_UNIX_EPOCH_IN_TICKS); + ts->tv_sec = ticks / KIT_TIMESPEC_IMPL_TICKS_PER_SECONDS; + ts->tv_nsec = (ticks % KIT_TIMESPEC_IMPL_TICKS_PER_SECONDS) * 100; + + return base; +} +#endif + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/kit/types.h b/kit/types.h new file mode 100644 index 0000000..bbe8717 --- /dev/null +++ b/kit/types.h @@ -0,0 +1,36 @@ +#ifndef KIT_TYPES_H +#define KIT_TYPES_H + +#ifndef _GNU_SOURCE +# define _GNU_SOURCE +#endif + +// signed integers +// +typedef signed char i8; +typedef signed short i16; +typedef signed int i32; +typedef signed long long i64; + +// unsigned integers +// +typedef unsigned char u8; +typedef unsigned short u16; +typedef unsigned int u32; +typedef unsigned long long u64; + +// floats +// +typedef float f32; +typedef double f64; + +// chars +// +typedef char c8; +typedef int c32; + +typedef signed char b8; // 8-bit boolean +typedef signed int b32; // 32-bit boolean +typedef signed int s32; // 32-bit status + +#endif diff --git a/kit/unival.c b/kit/unival.c new file mode 100644 index 0000000..4fed179 --- /dev/null +++ b/kit/unival.c @@ -0,0 +1,51 @@ +#include "unival.h" + +kit_uv_decode_result_t kit_uv_decode(kit_is_handle_t is, + kit_allocator_t *alloc) { + kit_uv_decode_result_t result; + memset(&result, 0, sizeof result); + + result.status = KIT_ERROR_NOT_IMPLEMENTED; + return result; +} + +kit_uv_encode_result_t kit_uv_encode(kit_unival_t *value, + kit_allocator_t *alloc, + i32 flags) { + kit_uv_encode_result_t result; + memset(&result, 0, sizeof result); + + result.status = KIT_ERROR_NOT_IMPLEMENTED; + return result; +} + +kit_uv_decode_result_t kit_uv_parse(kit_is_handle_t is, + kit_allocator_t *alloc) { + kit_uv_decode_result_t result; + memset(&result, 0, sizeof result); + + result.status = KIT_ERROR_NOT_IMPLEMENTED; + return result; +} + +kit_uv_decode_result_t kit_uv_parse_json(kit_is_handle_t is, + kit_allocator_t *alloc) { + kit_uv_decode_result_t result; + memset(&result, 0, sizeof result); + + result.status = KIT_ERROR_NOT_IMPLEMENTED; + return result; +} + +kit_uv_print_result_t kit_uv_print(kit_unival_t *value, + kit_allocator_t *alloc, + i32 flags) { + kit_uv_print_result_t result; + memset(&result, 0, sizeof result); + + result.status = KIT_ERROR_NOT_IMPLEMENTED; + return result; +} + +void kit_uv_destroy(kit_unival_t *value) { } + diff --git a/kit/unival.h b/kit/unival.h new file mode 100644 index 0000000..e0362b1 --- /dev/null +++ b/kit/unival.h @@ -0,0 +1,86 @@ +#ifndef KIT_UNIVAL_H +#define KIT_UNIVAL_H + +#include "string_builder.h" +#include "input_stream.h" + +#ifdef __cplusplus +extern "C" { +#endif + +enum { + KIT_UV_NONE, + KIT_UV_BOOLEAN, + KIT_UV_INTEGER, + KIT_UV_FLOAT, + KIT_UV_STRING, + KIT_UV_BYTES, + KIT_UV_ARRAY, + KIT_UV_COMPOSITE, +}; + +enum { + KIT_UV_ENCODE_BZIP = 1, + KIT_UV_PRINT_PRETTY = 1, + KIT_UV_PRINT_JSON = 2, +}; + +typedef struct kit_unival_ kit_unival_t; + +typedef KIT_DA(kit_unival_t) kit_da_unival_t; +typedef KIT_DA(u8) kit_uv_bytes_t; + +struct kit_unival_ { + i8 type; + union { + i8 boolean; + i64 integer; + f64 float_; + kit_str_builder_t string; + kit_uv_bytes_t bytes; + kit_da_unival_t array; + struct { + kit_da_unival_t keys; + kit_da_unival_t values; + } composite; + }; +}; + +typedef struct { + s32 status; + kit_unival_t *value; +} kit_uv_decode_result_t; + +kit_uv_decode_result_t kit_uv_decode(kit_is_handle_t is, + kit_allocator_t *alloc); + +typedef struct { + s32 status; + kit_uv_bytes_t value; +} kit_uv_encode_result_t; + +kit_uv_encode_result_t kit_uv_encode(kit_unival_t *value, + kit_allocator_t *alloc, + i32 flags); + +kit_uv_decode_result_t kit_uv_parse(kit_is_handle_t is, + kit_allocator_t *alloc); + +kit_uv_decode_result_t kit_uv_parse_json(kit_is_handle_t is, + kit_allocator_t *alloc); + +typedef struct { + s32 status; + kit_str_builder_t value; +} kit_uv_print_result_t; + +kit_uv_print_result_t kit_uv_print(kit_unival_t *value, + kit_allocator_t *alloc, i32 flags); + +void kit_uv_destroy(kit_unival_t *value); + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/kit/utf8.h b/kit/utf8.h new file mode 100644 index 0000000..3dc6822 --- /dev/null +++ b/kit/utf8.h @@ -0,0 +1,44 @@ +#ifndef KIT_UTF8_H +#define KIT_UTF8_H + +#include "string_builder.h" + +#ifdef __cplusplus +extern "C" { +#endif + +#if defined(__GNUC__) || defined(__clang__) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wunused-function" +# pragma GCC diagnostic ignored "-Wunknown-pragmas" +# pragma GCC push_options +# pragma GCC optimize("O3") +#endif + +static s32 kit_utf8_count(kit_str_t s, i64 *count) { + return KIT_ERROR_NOT_IMPLEMENTED; +} + +static s32 kit_utf8_offset(kit_str_t s, i64 count, i64 *offset) { + return KIT_ERROR_NOT_IMPLEMENTED; +} + +static s32 kit_utf8_decode(kit_str_t s, i64 offset, i64 *size, + c32 *value) { + return KIT_ERROR_NOT_IMPLEMENTED; +} + +static s32 kit_utf8_encode(kit_str_builder_t *s, c32 value) { + return KIT_ERROR_NOT_IMPLEMENTED; +} + +#if defined(__GNUC__) || defined(__clang__) +# pragma GCC pop_options +# pragma GCC diagnostic pop +#endif + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/kit/xml.c b/kit/xml.c new file mode 100644 index 0000000..f61bfc1 --- /dev/null +++ b/kit/xml.c @@ -0,0 +1,483 @@ +#include "xml.h" + +#include "input_buffer.h" +#include <assert.h> + +typedef struct { + ib_token_t last; + str_builder_t text; + kit_da_xml_t tags; +} kit_xml_intermediate_t; + +static s32 kit_xml_alloc_and_unescape_(str_builder_t *dst, str_t str, + kit_allocator_t *alloc) { + assert(dst != NULL); + assert(str.size == 0 || str.values != NULL); + + if (dst == NULL) + return KIT_ERROR_INTERNAL; + if (str.size != 0 && str.values == NULL) + return KIT_ERROR_INTERNAL; + + DA_INIT(*dst, str.size, alloc); + + if (dst->size != str.size) + return KIT_ERROR_OUT_OF_MEMORY; + + dst->size = 0; + + for (i64 i = 0; i < str.size; i++) + if (str.values[i] != '&') + dst->values[dst->size++] = str.values[i]; + else { + i64 n = 1; + while (i + n < str.size && str.values[i + n] != ';') + n++; + if (i + n >= str.size) { + DA_DESTROY(*dst); + return KIT_PARSING_FAILED; + } + if (n == 3 && memcmp(str.values + i, "<", 4) == 0) + dst->values[dst->size++] = '<'; + else if (n == 3 && memcmp(str.values + i, ">", 4) == 0) + dst->values[dst->size++] = '>'; + else if (n == 4 && memcmp(str.values + i, "&", 5) == 0) + dst->values[dst->size++] = '&'; + else if (n == 5 && memcmp(str.values + i, """, 6) == 0) + dst->values[dst->size++] = '"'; + else if (n == 5 && memcmp(str.values + i, "'", 6) == 0) + dst->values[dst->size++] = '\''; + else if (n - 2 <= 8 && str.values[i + 1] == '#' && + str.values[i + 2] == 'x') { + // hex encoding + // + + c8 buf[8]; + u64 x = 0; + + memcpy(buf, str.values + (i + 3), n - 2); + + for (i64 k = 0; k < n - 2; k++) { + c8 c = str.values[i + 3 + k]; + x <<= 8; + if (c >= '0' && c <= '9') + x |= (c - '0'); + else if (c >= 'a' && c <= 'f') + x |= 10 + (c - 'a'); + else if (c >= 'A' && c <= 'F') + x |= 10 + (c - 'A'); + else { + x = 0; + break; + } + } + + if (x == 0 || x > 255u) { + // TODO + // UTF-8 encoding + + DA_DESTROY(*dst); + return KIT_PARSING_FAILED; + } + + dst->values[dst->size++] = (c8) x; + } else if (n - 1 <= 20 && str.values[i + 1] == '#') { + // dec encoding + // + + c8 buf[20]; + u64 x = 0; + + memcpy(buf, str.values + (i + 2), n - 2); + + for (i64 k = 0; k < n - 1; k++) { + c8 c = str.values[i + 2 + k]; + x *= 10; + if (c >= '0' && c <= '9') + x += (c - '0'); + else { + x = 0; + break; + } + } + + if (x == 0 || x > 255u) { + // TODO + // UTF-8 encoding + + DA_DESTROY(*dst); + return KIT_PARSING_FAILED; + } + + dst->values[dst->size++] = (c8) x; + } else { + DA_DESTROY(*dst); + return KIT_PARSING_FAILED; + } + i += n; + } + + return KIT_OK; +} + +static ib_token_t kit_xml_parse_text_(ib_token_t begin, + str_builder_t *dst) { + ib_token_t last = ib_until(begin, SZ("<")); + + DA_RESIZE(*dst, last.size); + + assert(dst->size == last.size); + if (dst->size != last.size) + last.status |= KIT_ERROR_OUT_OF_MEMORY; + else if (last.size > 0) + memcpy(dst->values, ib_str(last).values, last.size); + + for (;;) { + ib_token_t comment_open = ib_exact(last, SZ("<!--")); + + if (comment_open.status != KIT_OK) + break; + + ib_token_t comment_text = ib_until(comment_open, SZ("-->")); + ib_token_t comment_close = ib_exact(comment_text, SZ("-->")); + ib_token_t next_text = ib_until(comment_close, SZ("<")); + + if (next_text.status == KIT_OK && next_text.size > 0) { + i64 n = dst->size; + DA_RESIZE(*dst, n + next_text.size); + + assert(dst->size == n + next_text.size); + if (dst->size != n + next_text.size) + next_text.status |= KIT_ERROR_OUT_OF_MEMORY; + else + memcpy(dst->values + n, ib_str(next_text).values, + ib_str(next_text).size); + } + + last = next_text; + } + + return last; +} + +static ib_token_t kit_xml_parse_string_(ib_token_t begin, + ib_token_t *value) { + assert(value != NULL); + if (value == NULL) { + begin.status |= KIT_ERROR_INTERNAL; + return begin; + } + + ib_token_t quotes_open = ib_exact(begin, SZ("\"")); + ib_token_t apostr_open = ib_exact(begin, SZ("'")); + + ib_token_t open = quotes_open.status == KIT_OK ? quotes_open + : apostr_open; + + *value = ib_until(open, ib_str(open)); + ib_token_t close = ib_exact(*value, ib_str(open)); + + return close; +} + +static kit_xml_intermediate_t kit_xml_parse_buf_( + ib_token_t begin, kit_allocator_t *alloc) { + kit_xml_intermediate_t res; + memset(&res, 0, sizeof res); + + ib_token_t last, spaces; + memset(&last, 0, sizeof last); + memset(&spaces, 0, sizeof spaces); + + str_builder_t tag_text_string; + str_builder_t tag_tail_string; + DA_INIT(tag_text_string, 0, alloc); + DA_INIT(tag_tail_string, 0, alloc); + + ib_token_t tag_text = kit_xml_parse_text_(begin, &tag_text_string); + last = tag_text; + + DA_INIT(res.tags, 0, alloc); + + for (;;) { + ib_token_t tagend_open = ib_exact(last, SZ("</")); + if (tagend_open.status == KIT_OK) + break; + + ib_token_t tag_open = ib_exact(last, SZ("<")); + + if (tag_open.status != KIT_OK) + break; + + xml_t tag; + memset(&tag, 0, sizeof tag); + + ib_token_t decl_open = ib_exact(tag_open, SZ("?")); + + if (decl_open.status == KIT_OK) { + tag.is_declaration = 1; + last = decl_open; + } else + last = tag_open; + + spaces = ib_any(last, SZ(" \t\r\n")); + ib_token_t tag_name = ib_none(spaces, SZ(" \t\r\n/>")); + + DA_INIT(tag.properties, 0, alloc); + + last = tag_name; + + for (;;) { + spaces = ib_any(last, SZ(" \t\r\n")); + ib_token_t property = ib_none(spaces, SZ(" \t\r\n=?/>")); + + if (property.status != KIT_OK || property.size == 0) + break; + + spaces = ib_any(property, SZ(" \t\r\n")); + ib_token_t equals = ib_exact(spaces, SZ("=")); + spaces = ib_any(equals, SZ(" \t\r\n")); + + ib_token_t value; + last = kit_xml_parse_string_(spaces, &value); + + if (last.status == KIT_OK) { + i64 n = tag.properties.size; + DA_RESIZE(tag.properties, n + 1); + + assert(tag.properties.size == n + 1); + if (tag.properties.size != n + 1) { + last.status |= KIT_ERROR_OUT_OF_MEMORY; + DA_DESTROY(tag.properties); + } else { + last.status |= kit_xml_alloc_and_unescape_( + &tag.properties.values[n].name, ib_str(property), + alloc); + last.status |= kit_xml_alloc_and_unescape_( + &tag.properties.values[n].value, ib_str(value), alloc); + } + } + } + + if (tag.is_declaration) { + ib_token_t tag_decl_close = ib_exact(spaces, SZ("?>")); + + last = tag_decl_close; + + DA_INIT(tag.text, 0, alloc); + DA_INIT(tag.children, 0, alloc); + } else { + ib_token_t tag_close = ib_exact(spaces, SZ(">")); + ib_token_t tag_close_empty = ib_exact(spaces, SZ("/>")); + + if (tag_close.status == KIT_OK) { + kit_xml_intermediate_t im = kit_xml_parse_buf_(tag_close, + alloc); + + tag.text = im.text; + tag.children = im.tags; + + tagend_open = ib_exact(im.last, SZ("</")); + spaces = ib_any(tagend_open, SZ(" \t\r\n")); + ib_token_t tagend_name = ib_exact(spaces, ib_str(tag_name)); + spaces = ib_any(tagend_name, SZ(" \t\r\n")); + ib_token_t tagend_close = ib_exact(spaces, SZ(">")); + + last = tagend_close; + + } else if (tag_close_empty.status == KIT_OK) { + last = tag_close_empty; + + DA_INIT(tag.text, 0, alloc); + DA_INIT(tag.children, 0, alloc); + } else + last.status |= KIT_PARSING_FAILED; + } + + ib_token_t tag_tail = kit_xml_parse_text_(last, &tag_tail_string); + + last = tag_tail; + + if (last.status == KIT_OK) { + i64 n = res.tags.size; + DA_RESIZE(res.tags, n + 1); + + assert(res.tags.size == n + 1); + if (res.tags.size != n + 1) { + last.status |= KIT_ERROR_OUT_OF_MEMORY; + xml_destroy(&tag); + } else { + last.status |= kit_xml_alloc_and_unescape_( + &tag.tag, ib_str(tag_name), alloc); + last.status |= kit_xml_alloc_and_unescape_( + &tag.tail, WRAP_STR(tag_tail_string), alloc); + + res.tags.values[n] = tag; + } + } else + xml_destroy(&tag); + } + + if (last.status != KIT_OK) { + for (i64 i = 0; i < res.tags.size; i++) + xml_destroy(res.tags.values + i); + DA_DESTROY(res.text); + DA_DESTROY(res.tags); + } else + last.status |= kit_xml_alloc_and_unescape_( + &res.text, WRAP_STR(tag_text_string), alloc); + + DA_DESTROY(tag_text_string); + DA_DESTROY(tag_tail_string); + + res.last = last; + return res; +} + +kit_xml_parse_result_t kit_xml_parse(is_handle_t is, + kit_allocator_t *alloc) { + input_buffer_t ib = ib_init(is, alloc); + kit_xml_intermediate_t im = kit_xml_parse_buf_(ib_token(&ib), + alloc); + + kit_xml_parse_result_t res; + memset(&res, 0, sizeof res); + + res.status = im.last.status; + + if (res.status != KIT_OK) { + ib_destroy(&ib); + return res; + } + + if (im.text.size == 0 && im.tags.size == 1) { + res.xml = im.tags.values[0]; + DA_DESTROY(im.text); + DA_DESTROY(im.tags); + ib_destroy(&ib); + return res; + } + + DA_INIT(res.xml.tag, 0, alloc); + DA_INIT(res.xml.tail, 0, alloc); + DA_INIT(res.xml.properties, 0, alloc); + + res.xml.text = im.text; + res.xml.children = im.tags; + + ib_destroy(&ib); + return res; +} + +kit_xml_text_t kit_xml_print(kit_xml_t *xml, kit_allocator_t *alloc) { + // TODO + // + + assert(xml != NULL); + + xml_text_t result; + memset(&result, 0, sizeof result); + + (void) alloc; + + result.status = KIT_ERROR_NOT_IMPLEMENTED; + return result; +} + +static s32 kit_xml_append_text_(str_builder_t *buf, xml_t *xml) { + assert(buf != NULL); + assert(xml != NULL); + + i64 n = buf->size; + DA_RESIZE(*buf, n + xml->text.size); + + assert(buf->size == n + xml->text.size); + if (buf->size != n + xml->text.size) + return KIT_ERROR_OUT_OF_MEMORY; + + if (xml->text.size > 0) + memcpy(buf->values + n, xml->text.values, xml->text.size); + + for (i64 i = 0; i < xml->children.size; i++) { + s32 s = kit_xml_append_text_(buf, xml->children.values + i); + if (s != KIT_OK) + return s; + + str_t tail = WRAP_STR(xml->children.values[i].tail); + + if (tail.size <= 0) + continue; + + n = buf->size; + DA_RESIZE(*buf, n + tail.size); + + assert(buf->size == n + tail.size); + if (buf->size != n + tail.size) + return KIT_ERROR_OUT_OF_MEMORY; + + if (tail.size > 0) + memcpy(buf->values + n, tail.values, tail.size); + } + + return KIT_OK; +} + +kit_xml_text_t kit_xml_full_text(kit_xml_t *xml, + kit_allocator_t *alloc) { + kit_xml_text_t res; + res.status = KIT_OK; + DA_INIT(res.text, 0, alloc); + + if (xml != NULL) + res.status = kit_xml_append_text_(&res.text, xml); + else + res.status = KIT_ERROR_INVALID_ARGUMENT; + + return res; +} + +b8 kit_xml_has_property(kit_xml_t *xml, kit_str_t name) { + assert(xml != NULL); + if (xml == NULL) + return 0; + + for (i64 i = 0; i < xml->properties.size; i++) + if (AR_EQUAL(xml->properties.values[i].name, name)) + return 1; + + return 0; +} + +str_t kit_xml_property(kit_xml_t *xml, str_t name) { + assert(xml != NULL); + if (xml == NULL) + return str(0, NULL); + + for (i64 i = 0; i < xml->properties.size; i++) + if (AR_EQUAL(xml->properties.values[i].name, name)) + return WRAP_STR(xml->properties.values[i].value); + + assert(0); + return str(0, NULL); +} + +void kit_xml_destroy(kit_xml_t *xml) { + assert(xml != NULL); + if (xml == NULL) + return; + + for (i64 i = 0; i < xml->properties.size; i++) { + DA_DESTROY(xml->properties.values[i].name); + DA_DESTROY(xml->properties.values[i].value); + } + + for (i64 i = 0; i < xml->children.size; i++) + kit_xml_destroy(xml->children.values + i); + + DA_DESTROY(xml->tag); + DA_DESTROY(xml->text); + DA_DESTROY(xml->tail); + + DA_DESTROY(xml->properties); + DA_DESTROY(xml->children); +} diff --git a/kit/xml.h b/kit/xml.h new file mode 100644 index 0000000..a4dd3d1 --- /dev/null +++ b/kit/xml.h @@ -0,0 +1,64 @@ +#ifndef KIT_XML_H +#define KIT_XML_H + +#include "string_builder.h" +#include "input_stream.h" + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct kit_xml_ kit_xml_t; + +typedef struct { + kit_str_builder_t name; + kit_str_builder_t value; +} kit_xml_property_t; + +typedef KIT_DA(kit_xml_property_t) kit_da_xml_property_t; +typedef KIT_DA(kit_xml_t) kit_da_xml_t; + +struct kit_xml_ { + i8 is_declaration; + kit_str_builder_t tag; + kit_str_builder_t text; + kit_str_builder_t tail; + kit_da_xml_property_t properties; + kit_da_xml_t children; +}; + +typedef struct { + s32 status; + kit_xml_t xml; +} kit_xml_parse_result_t; + +typedef struct { + s32 status; + kit_str_builder_t text; +} kit_xml_text_t; + +kit_xml_parse_result_t kit_xml_parse(kit_is_handle_t is, + kit_allocator_t *alloc); +kit_xml_text_t kit_xml_print(kit_xml_t *xml, kit_allocator_t *alloc); +kit_xml_text_t kit_xml_full_text(kit_xml_t *xml, + kit_allocator_t *alloc); +b8 kit_xml_has_property(kit_xml_t *xml, kit_str_t name); +kit_str_t kit_xml_property(kit_xml_t *xml, kit_str_t name); +void kit_xml_destroy(kit_xml_t *xml); + +#ifdef __cplusplus +} +#endif + +#define xml_t kit_xml_t +#define xml_property_t kit_xml_property_t +#define xml_parse_result_t kit_xml_parse_result_t +#define xml_text_t kit_xml_text_t +#define xml_parse kit_xml_parse +#define xml_print kit_xml_print +#define xml_full_text kit_xml_full_text +#define xml_has_property kit_xml_has_property +#define xml_property kit_xml_property +#define xml_destroy kit_xml_destroy + +#endif |