diff options
Diffstat (limited to 'include')
| -rwxr-xr-x | include/ann.h | 604 | ||||
| -rwxr-xr-x | include/bin.h | 315 | ||||
| -rw-r--r-- | include/buffer.h | 232 | ||||
| -rw-r--r-- | include/direct.h | 313 | ||||
| -rwxr-xr-x | include/escape.h | 209 | ||||
| -rwxr-xr-x | include/flat.h | 293 | ||||
| -rwxr-xr-x | include/genetic.h | 148 | ||||
| -rwxr-xr-x | include/interpolate.h | 205 | ||||
| -rwxr-xr-x | include/pool.h | 123 | ||||
| -rw-r--r-- | include/pushdown.h | 915 | ||||
| -rw-r--r-- | include/stack.h | 211 | ||||
| -rw-r--r-- | include/test.h | 57 | ||||
| -rw-r--r-- | include/type.h | 11 | ||||
| -rwxr-xr-x | include/ufo.h | 730 | ||||
| -rw-r--r--[-rwxr-xr-x] | include/uri.h | 499 |
15 files changed, 3886 insertions, 979 deletions
diff --git a/include/ann.h b/include/ann.h index 087daa5..e34176a 100755 --- a/include/ann.h +++ b/include/ann.h @@ -1,10 +1,14 @@ -// ann.h - Artificial Neural Nework Libray +// ann.h - Artificial Neural Network Library +// +// Thread safety: Not thread-safe. External synchronization required. +// Memory: Single-allocation design — all neurons, weights, and deltas +// stored in one contiguous buffer for easy persistence and cloning. +// Use ann_copy for deep clone; ann_free to release. #ifndef ANN_H #define ANN_H -#include <stdint.h> -#include "./type.h" +#include "type.h" #ifdef __cplusplus extern "C" { @@ -21,64 +25,66 @@ typedef enum { } ann_activation_t; typedef struct { + void *buffer; + // The full size of the allocated structure - uint_t n; + u64 n; // The number of layers in the neural network - uint_t layer_n; + u64 layer_n; // The neuron count ( hidden ) - uint_t neuron_n; + u64 neuron_n; // The total number of weights and biases - uint_t weight_n; + u64 weight_n; // The number of neurons in each layer - uint_t *layer_neuron_n; + u64 *layer_neuron_n; // The pointer to the neurons - fp_t *neuron; + f64 *neuron; // The weights and biases for each neuron // - w_lji denotes the connection between the jth neuron in layer l, and // the ith neuron in the previous layer // - b_lj denotes the bias for the jth neuron in layer l // { w_000, w_001, w_002, .... , b_00, ...., w_ijk, b_ij }` - fp_t *weight; + f64 *weight; // The delta between between the actual and the cost function - fp_t *delta; + f64 *delta; // The activation function used in the hidden layer neurons - fp_t (*activation_hidden)(fp_t); + f64 (*activation_hidden)(f64); // The partial derivative of the activation function used in the hidden // layer neurons - fp_t (*activation_hidden_partial)(fp_t); + f64 (*activation_hidden_partial)(f64); // The activation function used in the ouput neurons - fp_t (*activation_output)(fp_t); + f64 (*activation_output)(f64); // The partial derivative of the activation function used in the output // layer neurons - fp_t (*activation_output_partial)(fp_t); + f64 (*activation_output_partial)(f64); } ann_t; -ann_t *ann_init(uint_t, uint_t *); -ann_t *ann_copy(ann_t const *); +int ann_init(ann_t *, u64, u64 *); +void ann_copy(ann_t *, ann_t const *); void ann_free(ann_t *); void ann_random(ann_t *); -void ann_propagation_forward(ann_t *, fp_t const *const, fp_t *); -void ann_propagation_backward(ann_t *, fp_t const *, fp_t *, fp_t const *, - fp_t); -void ann_train_numeric(ann_t *, fp_t const *, fp_t const *, fp_t); +void ann_propagation_forward(ann_t *, f64 const *const, f64 *); +void ann_propagation_backward(ann_t *, f64 const *, f64 *, f64 const *, + f64); +void ann_train_numeric(ann_t *, f64 const *, f64 const *, u64, f64); -fp_t ann_error_total(fp_t const *, fp_t const *, uint_t); +f64 ann_error_total(f64 const *, f64 const *, u64); void ann_set_activation(ann_t *, ann_activation_t, ann_activation_t); void ann_print_weight(ann_t *); -void ann_print_neuron(ann_t *, fp_t const *const, fp_t const *const); +void ann_print_neuron(ann_t *, f64 const *const, f64 const *const); #ifdef __cplusplus } @@ -87,7 +93,7 @@ void ann_print_neuron(ann_t *, fp_t const *const, fp_t const *const); #endif // ANN_H //////////////////////////////////////////////////////////////////////////////// -// IMPELEMENTATION SECTION +// IMPLEMENTATION SECTION //////////////////////////////////////////////////////////////////////////////// #ifdef ANN_IMPLEMENTATION @@ -108,27 +114,27 @@ void ann_print_neuron(ann_t *, fp_t const *const, fp_t const *const); #define ELU_ALPHA 0.2 #define LRELU_ALPHA 0.2 -static fp_t ann_random_range(fp_t, fp_t); - -static fp_t ann_error(fp_t, fp_t); -static fp_t ann_error_partial(fp_t, fp_t); +static void ann_zero_weights(ann_t *); +static f64 ann_random_range(f64, f64); +static f64 ann_error(f64, f64); +static f64 ann_error_partial(f64, f64); -static fp_t ann_activation_identity(fp_t); -static fp_t ann_activation_identity_partial(fp_t); -static fp_t ann_activation_binary(fp_t); -static fp_t ann_activation_binary_partial(fp_t); -static fp_t ann_activation_sigmoid(fp_t); -static fp_t ann_activation_sigmoid_partial(fp_t); -static fp_t ann_activation_relu(fp_t); -static fp_t ann_activation_relu_partial(fp_t); -static fp_t ann_activation_elu(fp_t); -static fp_t ann_activation_elu_partial(fp_t); -static fp_t ann_activation_lrelu(fp_t); -static fp_t ann_activation_lrelu_partial(fp_t); -static fp_t ann_activation_tanh(fp_t); -static fp_t ann_activation_tanh_partial(fp_t); +static f64 ann_activation_identity(f64); +static f64 ann_activation_identity_partial(f64); +static f64 ann_activation_binary(f64); +static f64 ann_activation_binary_partial(f64); +static f64 ann_activation_sigmoid(f64); +static f64 ann_activation_sigmoid_partial(f64); +static f64 ann_activation_relu(f64); +static f64 ann_activation_relu_partial(f64); +static f64 ann_activation_elu(f64); +static f64 ann_activation_elu_partial(f64); +static f64 ann_activation_lrelu(f64); +static f64 ann_activation_lrelu_partial(f64); +static f64 ann_activation_tanh(f64); +static f64 ann_activation_tanh_partial(f64); -static fp_t (*ACTIVATION[][2])(fp_t) = { +static f64 (*ACTIVATION[][2])(f64) = { {ann_activation_identity, ann_activation_identity_partial}, // IDENTITY {ann_activation_binary, ann_activation_binary_partial}, // BINARY {ann_activation_sigmoid, ann_activation_sigmoid_partial}, // SIGMOID @@ -138,103 +144,135 @@ static fp_t (*ACTIVATION[][2])(fp_t) = { {ann_activation_tanh, ann_activation_tanh_partial}, // TANH }; -// ann_init() -// -// Initialize the neural network -// -// layer_n - The layer count for the layer count -// layer_neuron_n - An array of neuron counts for each layer -// -// return - The created ann_t instance - -ann_t *ann_init(uint_t layer_n, uint_t *layer_neuron_n) { - assert(layer_n >= 2); +int ann_init(ann_t *ann, u64 layer_n, u64 *layer_neuron_n) { + if (!ann || !layer_neuron_n || layer_n < 2) + return 0; - uint_t neuron_n = 0; - uint_t weight_n = 0; + u64 neuron_n = 0; + u64 weight_n = 0; - // Calculate the number of neurons and weights / biases - uint_t l = 1; + u64 l = 1; for (; l < layer_n - 1; l++) { + if (neuron_n > UINT64_MAX - layer_neuron_n[l]) + return 0; neuron_n += layer_neuron_n[l]; - weight_n += layer_neuron_n[l] * (layer_neuron_n[l - 1] + 1); + if (layer_neuron_n[l - 1] == UINT64_MAX) + return 0; + { + u64 rhs = layer_neuron_n[l - 1] + 1; + if (layer_neuron_n[l] > UINT64_MAX / rhs) + return 0; + u64 prod = layer_neuron_n[l] * rhs; + if (weight_n > UINT64_MAX - prod) + return 0; + weight_n += prod; + } + } + + if (layer_neuron_n[l - 1] == UINT64_MAX) + return 0; + { + u64 rhs = layer_neuron_n[l - 1] + 1; + if (layer_neuron_n[l] > UINT64_MAX / rhs) + return 0; + u64 prod = layer_neuron_n[l] * rhs; + if (weight_n > UINT64_MAX - prod) + return 0; + weight_n += prod; } - weight_n += layer_neuron_n[l] * (layer_neuron_n[l - 1] + 1); + if (layer_n > SIZE_MAX / sizeof(u64)) + return 0; + size_t layer_neuron_sz = sizeof(u64) * layer_n; + size_t padding = (sizeof(f64) - (layer_neuron_sz % sizeof(f64))) % sizeof(f64); - uint_t n = - sizeof(ann_t) + // ANN - (sizeof(uint_t) * layer_n) + // layer_neuron_n[] - (sizeof(fp_t) * (neuron_n + // neuron[] - weight_n + // weight[] - neuron_n + layer_neuron_n[layer_n - 1])); // delta[] + u64 total_fp = neuron_n + weight_n; + if (total_fp < neuron_n || total_fp < weight_n) + return 0; + if (total_fp > UINT64_MAX - neuron_n) + return 0; + total_fp += neuron_n; + if (total_fp > UINT64_MAX - layer_neuron_n[layer_n - 1]) + return 0; + total_fp += layer_neuron_n[layer_n - 1]; + if (total_fp > SIZE_MAX / sizeof(f64)) + return 0; + u64 n = (u64)(layer_neuron_sz + padding + sizeof(f64) * total_fp); - // Allocate everything as one structure - ann_t *ann = (ann_t *)malloc(n); + ann->buffer = malloc(n); + if (!ann->buffer) + return 0; - // ann_t | layer_neuron_n[] | neuron[] | weight[] | delta[] ann->n = n; ann->layer_n = layer_n; ann->weight_n = weight_n; ann->neuron_n = neuron_n; - ann->layer_neuron_n = (uint_t *)((uint8_t *)ann + sizeof(ann_t)); - memcpy(ann->layer_neuron_n, layer_neuron_n, sizeof(uint_t) * layer_n); - ann->neuron = (fp_t *)(ann->layer_neuron_n + ann->layer_n); + ann->layer_neuron_n = (u64 *)ann->buffer; + memcpy(ann->layer_neuron_n, layer_neuron_n, sizeof(u64) * layer_n); + ann->neuron = (f64 *)((char *)ann->buffer + layer_neuron_sz + padding); ann->weight = ann->neuron + ann->neuron_n; ann->delta = ann->weight + ann->weight_n; ann_set_activation(ann, SIGMOID, SIGMOID); + ann_zero_weights(ann); + return 1; +} - return ann; +void ann_free(ann_t *ann) { + if (ann) { + free(ann->buffer); + ann->buffer = NULL; + ann->layer_neuron_n = NULL; + ann->neuron = NULL; + ann->weight = NULL; + ann->delta = NULL; + } } -// ann_free() -// -// Free the neural network's memory -// -// ann - The instance of ann_t to free +void ann_copy(ann_t *dest, ann_t const *source) { + if (!dest || !source || !source->buffer) + return; + void *new_buffer = malloc(source->n); + if (!new_buffer) + return; -void ann_free(ann_t *ann) { free(ann); } + memcpy(new_buffer, source->buffer, source->n); -// ann_copy() -// -// Make a copy of the given ann_t instance -// -// ann - The instance of ann_t to copy -// -// return - The copied ann_t instance + if (dest->buffer) + free(dest->buffer); -ann_t *ann_copy(ann_t const *ann) { - ann_t *copy = (ann_t *)malloc(ann->n); - memcpy(copy, ann, ann->n); + size_t layer_neuron_sz = sizeof(u64) * source->layer_n; + size_t padding = (sizeof(f64) - (layer_neuron_sz % sizeof(f64))) % sizeof(f64); - return copy; + dest->buffer = new_buffer; + dest->n = source->n; + dest->layer_n = source->layer_n; + dest->weight_n = source->weight_n; + dest->neuron_n = source->neuron_n; + dest->layer_neuron_n = (u64 *)dest->buffer; + dest->neuron = (f64 *)((char *)dest->buffer + layer_neuron_sz + padding); + dest->weight = dest->neuron + source->neuron_n; + dest->delta = dest->weight + source->weight_n; + dest->activation_hidden = source->activation_hidden; + dest->activation_hidden_partial = source->activation_hidden_partial; + dest->activation_output = source->activation_output; + dest->activation_output_partial = source->activation_output_partial; } -// ann_propagation_forward() -// -// Perform forward propagation on the ann_t instance -// -// ann - The ann_t instance to perform the propagation on -// input - An array containing the input vector -// output - The destination array for the output vector - -void ann_propagation_forward(ann_t *ann, fp_t const *const input, - fp_t *output) { - // printf("ann:\t\t%p\n", ann); - // printf("output:\t\t%p\n", output); - fp_t *w_ij = ann->weight; - // printf("ann->weight:\t%p\n", w_ij); - fp_t const *x = input; // Input neuron into y - fp_t *y = ann->neuron; // The current neuron being calculated +void ann_propagation_forward(ann_t *ann, f64 const *const input, + f64 *output) { + if (!ann || !input || !output) + return; + f64 *w_ij = ann->weight; + f64 const *x = input; + f64 *y = ann->neuron; - uint_t l = 1; + u64 l = 1; for (; l < ann->layer_n - 1; l++) { - for (uint_t j = 0; j < ann->layer_neuron_n[l]; j++) { - // printf("neuron[%u]:\t%p\n", j, &(y[j])); + for (u64 j = 0; j < ann->layer_neuron_n[l]; j++) { y[j] = 0; - for (uint_t i = 0; i < ann->layer_neuron_n[l - 1]; i++) { + for (u64 i = 0; i < ann->layer_neuron_n[l - 1]; i++) { y[j] += x[i] * *w_ij++; } @@ -246,12 +284,10 @@ void ann_propagation_forward(ann_t *ann, fp_t const *const input, y += ann->layer_neuron_n[l]; } - // Last layer - for (uint_t j = 0; j < ann->layer_neuron_n[l]; j++) { - // printf("output[%u]:\t%p\n", j, &(output[j])); + for (u64 j = 0; j < ann->layer_neuron_n[l]; j++) { output[j] = 0; - for (uint_t i = 0; i < ann->layer_neuron_n[l - 1]; i++) { + for (u64 i = 0; i < ann->layer_neuron_n[l - 1]; i++) { output[j] += x[i] * *w_ij++; } @@ -260,321 +296,253 @@ void ann_propagation_forward(ann_t *ann, fp_t const *const input, } } -// ann_propagation_backward() -// -// Perform backpropagation on the ann_t instance -// -// ann - The ann_t instance to perform backpropagation upon -// input - Input vector array -// output - Output vector array -// target - Target output vector array -// rate - Learning rate - -void ann_propagation_backward(ann_t *ann, fp_t const *input, fp_t *output, - fp_t const *target, fp_t rate) { - int_t l = ann->layer_n - 1; - uint_t i, j, q; +void ann_propagation_backward(ann_t *ann, f64 const *input, f64 *output, + f64 const *target, f64 rate) { + if (!ann || !input || !output || !target) + return; + i64 l = (i64)ann->layer_n - 1; + u64 i = 0, j = 0, q = 0; - // First output layer delta - fp_t *d_j = ann->delta + ann->neuron_n; + f64 *d_j = ann->delta + ann->neuron_n; - // Output Deltas for (j = 0; j < ann->layer_neuron_n[l]; j++) { - d_j[j] = ann->activation_output_partial(output[j]) * - ann_error_partial(output[j], target[j]); + d_j[j] = ann_error_partial(output[j], target[j]) * ann->activation_output_partial(output[j]); } - // First weight in the set between the last layer and the current - fp_t *w_jq = ann->weight + ann->weight_n - - ann->layer_neuron_n[l] * ann->layer_neuron_n[l - 1] - - ann->layer_neuron_n[l]; + { + u64 last_layer_n = ann->layer_neuron_n[l]; + u64 prev_layer_plus_bias = ann->layer_neuron_n[l - 1] + 1; + if (last_layer_n > UINT64_MAX / prev_layer_plus_bias) + return; + f64 *w_jq = ann->weight + ann->weight_n - last_layer_n * prev_layer_plus_bias; - fp_t *o_j = ann->neuron + ann->neuron_n; - fp_t *d_q; + f64 *o_j = ann->neuron + ann->neuron_n; + f64 *d_q; - l--; + l--; - // Hidden Deltas - for (; l > 0; --l) { - d_q = d_j; - d_j -= ann->layer_neuron_n[l]; - o_j -= ann->layer_neuron_n[l]; + for (; l > 0; --l) { + d_q = d_j; + d_j -= ann->layer_neuron_n[l]; + o_j -= ann->layer_neuron_n[l]; - for (j = 0; j < ann->layer_neuron_n[l]; j++) { - d_j[j] = 0; - - for (q = 0; q < ann->layer_neuron_n[l + 1]; q++) { - d_j[j] += w_jq[q * (ann->layer_neuron_n[l] + 1) + j] * d_q[q]; + for (j = 0; j < ann->layer_neuron_n[l]; j++) { + d_j[j] = 0; + for (q = 0; q < ann->layer_neuron_n[l + 1]; q++) { + d_j[j] += w_jq[q * (ann->layer_neuron_n[l] + 1) + j] * d_q[q]; + } + d_j[j] *= ann->activation_hidden_partial(o_j[j]); } - d_j[j] *= ann->activation_hidden_partial(o_j[j]); + if (l > 1) { + u64 shift = ann->layer_neuron_n[l]; + u64 prev_plus_bias = ann->layer_neuron_n[l - 1] + 1; + if (shift <= UINT64_MAX / prev_plus_bias) { + w_jq -= shift * prev_plus_bias; + } else { + return; + } + } } - - w_jq -= (ann->layer_neuron_n[l - 1] * ann->layer_neuron_n[l] + - ann->layer_neuron_n[l - 1]); } - fp_t *w_ij = ann->weight; + f64 *w_ij = ann->weight; d_j = ann->delta; l = 1; - // Input training for (j = 0; j < ann->layer_neuron_n[l]; j++) { for (i = 0; i < ann->layer_neuron_n[l - 1]; i++) { *w_ij -= rate * input[i] * d_j[j]; w_ij++; } - *w_ij -= rate * d_j[j]; w_ij++; } l++; - fp_t *i_i = ann->neuron; + f64 *i_i = ann->neuron; - // Hidden training - for (; l < (int_t)ann->layer_n; l++) { + for (; l < (i64)ann->layer_n; l++) { d_j += ann->layer_neuron_n[l - 1]; - for (j = 0; j < ann->layer_neuron_n[l]; j++) { for (i = 0; i < ann->layer_neuron_n[l - 1]; i++) { *w_ij -= rate * i_i[i] * d_j[j]; w_ij++; } - *w_ij -= rate * d_j[j]; w_ij++; } - i_i += ann->layer_neuron_n[l - 1]; } } -// ann_activation_identity() -// -// y = x -// dy/dx = 1 - -static fp_t ann_activation_identity(fp_t x) { return x; } -static fp_t ann_activation_identity_partial(fp_t x) { return 1; } - -// ann_activation_binary() -// -// y = { x < 0 -> 0, x > 0 -> 1 } -// dy/dx = 0 +static f64 ann_activation_identity(f64 x) { return x; } +static f64 ann_activation_identity_partial(f64 x) { (void)x; return 1.0; } -static fp_t ann_activation_binary(fp_t x) { - return (x > 0.0) ? 1.0 : (x < 0.0) ? -1.0 : 0.0; +static f64 ann_activation_binary(f64 x) { + return (x >= 0.0) ? 1.0 : 0.0; } -static fp_t ann_activation_binary_partial(fp_t x) { return 0.0; } - -// ann_activation_sign() -// -// y = { x < 0 -> -1, x = 0 -> 0, x > 0 -> 1 } -// dy/dx = 0 - -static fp_t ann_activation_sign(fp_t x) { return (x > 0.0) ? 1.0 : 0.0; } -static fp_t ann_activation_sign_partial(fp_t x) { return 0.0; } - -// ann_activation_sigmoid() -// -// y = 1.0 / ( 1.0 + e^-x ) -// dy/dx = f(x) * ( 1.0 - f(x) ) +static f64 ann_activation_binary_partial(f64 x) { (void)x; return 0.0; } -static fp_t ann_activation_sigmoid(fp_t x) { return 1.0 / (1.0 + exp(-x)); } -static fp_t ann_activation_sigmoid_partial(fp_t x) { return x * (1.0 - x); } - -// ann_activation_relu() -// -// y = { x < 0 -> 0, x >= 0 -> x } -// dy/dx = { x < 0 -> 0, x >= 0 -> 1 } +static f64 ann_activation_sigmoid(f64 x) { + return (x >= 0) ? (1.0 / (1.0 + exp(-x))) : (exp(x) / (1.0 + exp(x))); +} +static f64 ann_activation_sigmoid_partial(f64 x) { + // x is the already-activated sigmoid output σ(z), so σ'(z) = σ(z)(1-σ(z)) = x(1-x) + return x * (1.0 - x); +} -static fp_t ann_activation_relu(fp_t x) { return (x > 0.0) ? x : 0.0; } -static fp_t ann_activation_relu_partial(fp_t x) { +static f64 ann_activation_relu(f64 x) { return (x > 0.0) ? x : 0.0; } +static f64 ann_activation_relu_partial(f64 x) { return (x > 0.0) ? 1.0 : 0.0; } -// ann_activation_elu() -// -// y = { x < 0 -> a * ( e^x - 1 ), x >= 0 -> x } -// dy/dx = { x < 0 -> x + a, x >= 0 -> 1 } - -static fp_t ann_activation_elu(fp_t x) { +static f64 ann_activation_elu(f64 x) { return (x > 0.0) ? x : ELU_ALPHA * (expm1(x)); } -static fp_t ann_activation_elu_partial(fp_t x) { +static f64 ann_activation_elu_partial(f64 x) { return (x > 0.0) ? 1.0 : x + ELU_ALPHA; } -// ann_activation_lelu() -// -// y = { x < 0 -> a * x, x >= 0 -> x } -// dy/dx = { x < 0 -> a, x >= 0 -> 1 } - -static fp_t ann_activation_lrelu(fp_t x) { +static f64 ann_activation_lrelu(f64 x) { return (x > 0.0) ? x : LRELU_ALPHA * x; } -static fp_t ann_activation_lrelu_partial(fp_t x) { +static f64 ann_activation_lrelu_partial(f64 x) { return (x > 0.0) ? 1.0 : LRELU_ALPHA; } -// ann_activation_tanh() -// -// y = sinh( x ) / cosh( x ) = ( e^2x - 1 ) / ( e^2x + 1 ) -// dy/dx = 1.0 - f(x)^2 - -static fp_t ann_activation_tanh(fp_t x) { return tanh(x); } -static fp_t ann_activation_tanh_partial(fp_t x) { return 1.0 - (x * x); } +static f64 ann_activation_tanh(f64 x) { return tanh(x); } +static f64 ann_activation_tanh_partial(f64 x) { return 1.0 - (x * x); } -// ann_error() -// -// Implementation of mean squared error for calculating the difference between -// the current and target outputs for the ann_t instance -// -// output - The current ann_t output -// target - The target ann_t output +static f64 ann_error(f64 output, f64 target) { + f64 error = output - target; + return 0.5 * error * error; +} -fp_t ann_error(fp_t output, fp_t target) { - fp_t error = output - target; - error = 0.5 * error * error; +static f64 ann_error_partial(f64 output, f64 target) { return (output - target); } +f64 ann_error_total(f64 const *output, f64 const *target, u64 n) { + if (!output || !target) + return 0; + f64 error = 0; + for (u64 i = 0; i < n; i++) { + error += ann_error(output[i], target[i]); + } return error; } -// ann_error_partial() -// -// The partial derivative of mean squared error where n = 2 -// -// output - The current ann_t output -// target - The target ann_t output - -fp_t ann_error_partial(fp_t output, fp_t target) { return (output - target); } - -// ann_error_total() -// -// -// -// output - The array of current outputs -// target - The array of target outputs -// n - The size of the output and target arrays +void ann_train_numeric(ann_t *ann, f64 const *input, f64 const *target, + u64 n, f64 rate) { + if (!ann || !input || !target || rate == 0) + return; + if (n > SIZE_MAX / sizeof(f64)) + return; + f64 *output = malloc(n * sizeof(f64)); + if (!output) + return; -fp_t ann_error_total(fp_t const *output, fp_t const *target, uint_t n) { - fp_t error = 0; - for (uint_t i = 0; i < n; i++) { - error += ann_error(output[i], target[i]); + for (u64 w = 0; w < ann->weight_n; w++) { + f64 original = ann->weight[w]; + ann->weight[w] = original + rate; + ann_propagation_forward(ann, input, output); + f64 error_p = ann_error_total(output, target, n); + ann->weight[w] = original - rate; + ann_propagation_forward(ann, input, output); + f64 error_m = ann_error_total(output, target, n); + f64 gradient = (error_p - error_m) / (2.0 * rate); + ann->weight[w] = original - rate * gradient; } - return error; + free(output); } -// ann_set_activation() -// -// Set the activation functions for the hidden and output layers -// -// ann - The current ann_t instance -// activation_hidden - The hidden layer activation function -// activation_output - The output layer activation function - void ann_set_activation(ann_t *ann, ann_activation_t activation_hidden, - ann_activation_t activation_output) { + ann_activation_t activation_output) { + if (!ann) + return; + if ((int)activation_hidden < 0 || (int)activation_output < 0) + return; + if (activation_hidden > TANH || activation_output > TANH) + return; ann->activation_hidden = ACTIVATION[activation_hidden][0]; ann->activation_hidden_partial = ACTIVATION[activation_hidden][1]; ann->activation_output = ACTIVATION[activation_output][0]; ann->activation_output_partial = ACTIVATION[activation_output][1]; } -// ann_random() -// -// Set the weights of the ann_t instance to random numbers in the [-1, 1] range -// -// ann - The current ann_t instance +static void ann_zero_weights(ann_t *ann) { + if (!ann) + return; + memset(ann->weight, 0, ann->weight_n * sizeof(f64)); +} void ann_random(ann_t *ann) { - uint_t l, j, i; - fp_t *wb = ann->weight; + if (!ann) + return; + u64 l, j, i; + f64 *wb = ann->weight; for (l = 1; l < ann->layer_n; l++) { + if (ann->layer_neuron_n[l - 1] == 0) + continue; + if (ann->layer_neuron_n[l] == 0) + continue; + f64 fan_in = (f64)ann->layer_neuron_n[l - 1]; + f64 fan_out = (f64)ann->layer_neuron_n[l]; + f64 range = sqrt(6.0 / (fan_in + fan_out)); for (j = 0; j < ann->layer_neuron_n[l]; j++) { - i = 0; - for (; i < ann->layer_neuron_n[l - 1]; i++) { - *wb++ = ann_random_range(-1.0, 1.0); + for (i = 0; i < ann->layer_neuron_n[l - 1]; i++) { + *wb++ = ann_random_range(-range, range); } - *wb++ = 0; } } } -// ann_random_range() -// -// Remap a random value to a given range -// -// low - The lower bounds of the range -// high - The upper bounds of the range - -static fp_t ann_random_range(fp_t low, fp_t high) { - return (low + ((fp_t)rand()) * (high - low) / RAND_MAX); +static f64 ann_random_range(f64 low, f64 high) { + return (low + ((f64)rand()) * (high - low) / (f64)RAND_MAX); } -// ann_print_neuron() -// -// Print a text representation of the neurons in a given ann_t instance -// -// ann - The current ann_t instance -// input - The input used for the ann_t propagation being printed -// output - The output used for the ann_t propagation being printed - -void ann_print_neuron(ann_t *ann, fp_t const *const input, - fp_t const *const output) { +void ann_print_neuron(ann_t *ann, f64 const *const input, + f64 const *const output) { + if (!ann || !input || !output) + return; fputs("-> ", stderr); - for (uint_t i = 0; i < ann->layer_neuron_n[0]; i++) { + for (u64 i = 0; i < ann->layer_neuron_n[0]; i++) { fprintf(stderr, " %+.*f", PRINT_PRECISION, input[i]); } - fputs("\n", stderr); - fp_t *n = ann->neuron; - - for (uint_t l = 1; l < ann->layer_n - 1; l++) { - fprintf(stderr, " ", l); - for (uint_t i = 0; i < ann->layer_neuron_n[l]; i++) { + f64 *n = ann->neuron; + for (u64 l = 1; l < ann->layer_n - 1; l++) { + fprintf(stderr, " "); + for (u64 i = 0; i < ann->layer_neuron_n[l]; i++) { fprintf(stderr, " %+.*f", PRINT_PRECISION, *n); n++; } - fputs("\n", stderr); } fputs("= ", stderr); - for (uint_t i = 0; i < ann->layer_neuron_n[ann->layer_n - 1]; i++) { + for (u64 i = 0; i < ann->layer_neuron_n[ann->layer_n - 1]; i++) { fprintf(stderr, " %+.*f", PRINT_PRECISION, output[i]); } - fputs("\n\n", stderr); } -// ann_print_weight() -// -// Print a text representation of weights in the given ann_t instance -// -// ann - The current ann_t instance - void ann_print_weight(ann_t *ann) { - fp_t *weight = ann->weight; - - for (uint_t i = 1; i < ann->layer_n; i++) { - for (uint_t j = 0; j < ann->layer_neuron_n[i - 1] + 1; j++) { - for (uint_t k = 0; k < ann->layer_neuron_n[i]; k++) { + if (!ann) + return; + f64 *weight = ann->weight; + for (u64 i = 1; i < ann->layer_n; i++) { + for (u64 j = 0; j < ann->layer_neuron_n[i - 1] + 1; j++) { + for (u64 k = 0; k < ann->layer_neuron_n[i]; k++) { fprintf(stderr, " %+.*f", PRINT_PRECISION, - *(weight + j + k * (ann->layer_neuron_n[i - 1] + 1))); + *(weight + k * (ann->layer_neuron_n[i - 1] + 1) + j)); } - fputs("\n", stderr); } - - weight += ann->layer_neuron_n[i - 1] * ann->layer_neuron_n[i] + - ann->layer_neuron_n[i]; - + weight += ann->layer_neuron_n[i] * (ann->layer_neuron_n[i - 1] + 1); fputs("\n", stderr); } } diff --git a/include/bin.h b/include/bin.h index d764f09..d06b074 100755 --- a/include/bin.h +++ b/include/bin.h @@ -1,47 +1,77 @@ // bin.h - flat file, fixed block size, time series database +// +// Thread safety: Not thread-safe. External synchronization required. +// Behavior: No input validation — out-of-order data persists as-is. +// Unbuffered I/O by default (use _buffered variants for performance). +// _ok variants return 1 on success, 0 on any error (invalid args, I/O fail, +// overflow). Non-_ok variants remain for backward compatibility. #ifndef BIN_H #define BIN_H +/* USER-DEFINED (define before including): + * typedef <numerical_type> bin_key_t; + */ + #include <stddef.h> #include <stdint.h> #include <stdio.h> +#include <string.h> #include "type.h" typedef struct { - uint_t length; - uint_t block_size; + u64 length; + u64 block_size; } bin_meta_t; -FILE *bin_init(char const *, uint_t); +FILE *bin_init(char const *, u64); +FILE *bin_init_buffered(char const *, u64); FILE *bin_open(char const *path); -void bin_close(FILE *); -void bin_read(FILE *, int_t, void *, uint_t); -void bin_write(FILE *, int_t, void *, uint_t); -void bin_insert(FILE *, int_t, void *, uint_t); -void bin_append(FILE *, void *, uint_t); +FILE *bin_open_buffered(char const *path); +int bin_read(FILE *, i64, void *, u64); +void bin_write(FILE *, i64, void *, u64); +int bin_write_ok(FILE *, i64, void *, u64); +void bin_insert(FILE *, i64, void *, u64); +int bin_insert_ok(FILE *, i64, void *, u64); +void bin_append(FILE *, void *, u64); +int bin_append_ok(FILE *, void *, u64); +int bin_close(FILE *); -uint_t bin_length(FILE *); -uint_t bin_block_size(FILE *); +u64 bin_length(FILE *); +u64 bin_block_size(FILE *); -int_t bin_search(FILE *, bin_key_t); -uint_t bin_fuzzy_index(int_t); +i64 bin_search(FILE *, bin_key_t); +u64 bin_fuzzy_index(i64); #endif // BIN_H #ifdef BIN_IMPLEMENTATION // IMPLEMENTATION -#include <assert.h> #include <stdlib.h> -static void bin_write_length(FILE *, uint_t); -static void bin_write_block_size(FILE *, uint_t); +static void bin_write_length(FILE *, u64); +static void bin_write_block_size(FILE *, u64); -#define index_bytes(i, bs) ((i * bs) + sizeof(bin_meta_t)) +static inline i64 index_bytes_safe(i64 i, u64 bs, u64 *out) { + if (bs == 0 || i < 0 || (u64)i > (UINT64_MAX - sizeof(bin_meta_t)) / bs) + return -1; + *out = (u64)i * bs + sizeof(bin_meta_t); + return 0; +} #define member_sizeof(type, member) (sizeof(((type *)0)->member)) +static inline int fseek_safe(FILE *f, u64 offset) { +#ifdef _WIN32 + return _fseeki64(f, (long long)offset, SEEK_SET); +#else + if ((u64)(long)offset != offset) + return -1; + return fseek(f, (long)offset, SEEK_SET); +#endif +} + // bin_init() // // Creates the desired binary file @@ -50,7 +80,9 @@ static void bin_write_block_size(FILE *, uint_t); // // return - The newly created file -FILE *bin_init(char const *path, uint_t block_size) { +FILE *bin_init(char const *path, u64 block_size) { + if (!path) + return NULL; FILE *f = fopen(path, "wb+"); if (!f) @@ -64,6 +96,20 @@ FILE *bin_init(char const *path, uint_t block_size) { return f; } +FILE *bin_init_buffered(char const *path, u64 block_size) { + if (!path) + return NULL; + FILE *f = fopen(path, "wb+"); + + if (!f) + return NULL; + + bin_write_length(f, 0); + bin_write_block_size(f, block_size); + + return f; +} + // bin_open() // // Opens the desired binary file @@ -73,6 +119,8 @@ FILE *bin_init(char const *path, uint_t block_size) { // return - The newly opened file FILE *bin_open(char const *path) { + if (!path) + return NULL; FILE *f = fopen(path, "rb+"); if (!f) @@ -83,13 +131,23 @@ FILE *bin_open(char const *path) { return f; } +FILE *bin_open_buffered(char const *path) { + if (!path) + return NULL; + return fopen(path, "rb+"); +} + // bin_close() // // Closes the desired binary file // // f - The file descriptor to be closed -void bin_close(FILE *f) { fclose(f); } +int bin_close(FILE *f) { + if (!f) return 0; + int r = fclose(f); + return r == 0; +} // bin_read() // @@ -100,13 +158,33 @@ void bin_close(FILE *f) { fclose(f); } // data - The block_t buffer to be read into // n - The number of elements to read into the buffer -void bin_read(FILE *f, int_t i, void *data, uint_t n) { - uint_t bs = bin_block_size(f); +int bin_read(FILE *f, i64 i, void *data, u64 n) { + if (!f || !data || n == 0) + return 0; + u64 bs = bin_block_size(f); + if (bs == 0) + return 0; - assert(0 <= i && (i + n) <= bin_length(f)); + if (i < 0) + return 0; + u64 len = bin_length(f); + if ((u64)i + n > len) + return 0; - fseek(f, index_bytes(i, bs), SEEK_SET); - fread(data, bs, n, f); + u64 offset = 0; + if (index_bytes_safe(i, bs, &offset) != 0) + return 0; + if (bs > SIZE_MAX / n) + return 0; + fseek_safe(f, offset); + size_t read_n = fread(data, (size_t)bs, (size_t)n, f); + if (read_n != n) { + if ((n - read_n) > SIZE_MAX / bs) + return (int)read_n; + memset((char *)data + read_n * bs, 0, (n - read_n) * bs); + return (int)read_n; + } + return (int)n; } // bin_write() @@ -118,20 +196,30 @@ void bin_read(FILE *f, int_t i, void *data, uint_t n) { // data - The block_t buffer to write from // n - The number of elements to write from the buffer -void bin_write(FILE *f, int_t i, void *data, uint_t n) { - uint_t l = bin_length(f); - uint_t bs = bin_block_size(f); +void bin_write(FILE *f, i64 i, void *data, u64 n) { + (void)bin_write_ok(f, i, data, n); +} - assert(0 <= i && i <= l); +int bin_write_ok(FILE *f, i64 i, void *data, u64 n) { + if (!f || !data || n == 0) + return 0; + u64 l = bin_length(f); + u64 bs = bin_block_size(f); + if (bs == 0) + return 0; - fseek(f, index_bytes(i, bs), SEEK_SET); - fwrite(data, bs, n, f); + if (i < 0) + return 0; + if ((u64)i + n > l) + return 0; - if ((i + n) >= l) { - l += (i + n - l); - } - - bin_write_length(f, l); + u64 offset = 0; + if (index_bytes_safe(i, bs, &offset) != 0) + return 0; + if (fseek_safe(f, offset) != 0) + return 0; + size_t written = fwrite(data, bs, n, f); + return written == (size_t)n; } // bin_append() @@ -142,14 +230,31 @@ void bin_write(FILE *f, int_t i, void *data, uint_t n) { // data - The blocks to append to the file // n - The number of block to be appended -void bin_append(FILE *f, void *data, uint_t n) { - uint_t l = bin_length(f); - uint_t bs = bin_block_size(f); +void bin_append(FILE *f, void *data, u64 n) { + (void)bin_append_ok(f, data, n); +} - fseek(f, index_bytes(l, bs), SEEK_SET); - fwrite(data, bs, n, f); +int bin_append_ok(FILE *f, void *data, u64 n) { + if (!f || !data || n == 0) + return 0; + u64 l = bin_length(f); + u64 bs = bin_block_size(f); + if (bs == 0) + return 0; + if (l > UINT64_MAX - n) + return 0; + + u64 offset = 0; + if (index_bytes_safe((i64)l, bs, &offset) != 0) + return 0; + if (fseek_safe(f, offset) != 0) + return 0; + size_t written = fwrite(data, bs, n, f); + if (written != (size_t)n) + return 0; bin_write_length(f, l + n); + return 1; } // bin_insert() @@ -161,24 +266,59 @@ void bin_append(FILE *f, void *data, uint_t n) { // data - The blocks to insert into the file // n - The number of blocks to be inserted -void bin_insert(FILE *f, int_t i, void *data, uint_t n) { - uint_t l = bin_length(f); - uint_t bs = bin_block_size(f); +void bin_insert(FILE *f, i64 i, void *data, u64 n) { + (void)bin_insert_ok(f, i, data, n); +} + +int bin_insert_ok(FILE *f, i64 i, void *data, u64 n) { + if (!f || !data || n == 0) + return 0; + u64 l = bin_length(f); + u64 bs = bin_block_size(f); + if (bs == 0) + return 0; - assert(0 <= i && i <= l); + if (i < 0 || (u64)i > l) + return 0; - uint_t tmp_n = (l - i) * bs; + u64 blocks_to_move = l - (u64)i; + if (blocks_to_move > UINT64_MAX / bs) + return 0; - uint8_t tmp[tmp_n]; + if (l > UINT64_MAX - n) + return 0; - fseek(f, index_bytes(i, bs), SEEK_SET); - fread(tmp, bs, l - i, f); + u64 offset = 0; + if (index_bytes_safe(i, bs, &offset) != 0) + return 0; + if (fseek_safe(f, offset) != 0) + return 0; - fseek(f, index_bytes(i, bs), SEEK_SET); - fwrite(data, bs, n, f); - fwrite(tmp, 1, tmp_n, f); + if (blocks_to_move > 0) { + u64 tmp_n = blocks_to_move * bs; + if (tmp_n > SIZE_MAX) + return 0; + u8 *tmp = malloc((size_t)tmp_n); + if (tmp == NULL) + return 0; + size_t rn = fread(tmp, (size_t)bs, (size_t)blocks_to_move, f); + if (rn != (size_t)blocks_to_move) { + memset((char *)tmp + rn * (size_t)bs, 0, ((size_t)blocks_to_move - rn) * (size_t)bs); + } + + if (fseek_safe(f, offset) != 0) { free(tmp); return 0; } + size_t written = fwrite(data, bs, n, f); + if (written != (size_t)n) { free(tmp); return 0; } + fwrite(tmp, 1, (size_t)tmp_n, f); + free(tmp); + } else { + size_t written = fwrite(data, bs, n, f); + if (written != (size_t)n) + return 0; + } bin_write_length(f, l + n); + return 1; } // bin_length() @@ -189,11 +329,13 @@ void bin_insert(FILE *f, int_t i, void *data, uint_t n) { // // return - The length / number of entries in the file -uint_t bin_length(FILE *f) { - uint_t n = 0; +u64 bin_length(FILE *f) { + if (!f) return 0; + u64 n = 0; fseek(f, offsetof(bin_meta_t, length), SEEK_SET); - fread(&n, member_sizeof(bin_meta_t, length), 1, f); + size_t rn = fread(&n, member_sizeof(bin_meta_t, length), 1, f); + if (rn != 1) return 0; return n; } @@ -206,11 +348,13 @@ uint_t bin_length(FILE *f) { // // return - The block size for the entries in the file -uint_t bin_block_size(FILE *f) { - uint_t n = 0; +u64 bin_block_size(FILE *f) { + if (!f) return 0; + u64 n = 0; fseek(f, offsetof(bin_meta_t, block_size), SEEK_SET); - fread(&n, member_sizeof(bin_meta_t, block_size), 1, f); + size_t rn = fread(&n, member_sizeof(bin_meta_t, block_size), 1, f); + if (rn != 1) return 0; return n; } @@ -226,21 +370,38 @@ uint_t bin_block_size(FILE *f) { // The returned value is -( index + 1 ) where index is that of the // first element greater than k or bin_length(). -int_t bin_search(FILE *f, bin_key_t k) { - uint_t origin = ftell(f); +i64 bin_search(FILE *f, bin_key_t k) { + if (!f) return -1; + fpos_t origin; + fgetpos(f, &origin); - int_t l = 0; - int_t r = bin_length(f) - 1; - int_t m; + u64 len = bin_length(f); + if (len == 0) { + fsetpos(f, &origin); + return -1; + } + + i64 l = 0; + i64 r = (i64)len - 1; + i64 m; - uint_t bs = bin_block_size(f); + u64 bs = bin_block_size(f); - bin_key_t key; + bin_key_t key = 0; + int found = 0; while (l <= r) { - m = (l + r) / 2; - fseek(f, index_bytes(m, bs), SEEK_SET); - fread(&key, sizeof(k), 1, f); + m = l + (r - l) / 2; + u64 offset = 0; + if (index_bytes_safe(m, bs, &offset) != 0) { + fsetpos(f, &origin); + return -(l + 1); + } + fseek_safe(f, offset); + if (fread(&key, sizeof(k), 1, f) != 1) { + fsetpos(f, &origin); + return -(l + 1); + } if (key < k) l = m + 1; @@ -248,13 +409,15 @@ int_t bin_search(FILE *f, bin_key_t k) { else if (key > k) r = m - 1; - else + else { + found = 1; break; + } } - fseek(f, origin, SEEK_SET); + fsetpos(f, &origin); - if (key != k) + if (!found) return -(l + 1); return m; @@ -270,7 +433,11 @@ int_t bin_search(FILE *f, bin_key_t k) { // return - The index remapped the binary file. If the index is already // positive, then no operation occurrs. -uint_t bin_fuzzy_index(int_t i) { return (i < 0) ? -(i + 1) : i; } +u64 bin_fuzzy_index(i64 i) { + if (i < 0) + return (u64)(-(i + 1)); + return (u64)i; +} // bin_write_length() // @@ -279,9 +446,11 @@ uint_t bin_fuzzy_index(int_t i) { return (i < 0) ? -(i + 1) : i; } // f - The file to be written to // count - The length to be written to the file -static void bin_write_length(FILE *f, uint_t length) { +static void bin_write_length(FILE *f, u64 length) { fseek(f, offsetof(bin_meta_t, length), SEEK_SET); - fwrite(&length, member_sizeof(bin_meta_t, length), 1, f); + if (fwrite(&length, member_sizeof(bin_meta_t, length), 1, f) != 1) { + clearerr(f); + } } // bin_write_block_size() @@ -291,7 +460,7 @@ static void bin_write_length(FILE *f, uint_t length) { // f - The file to be written to // count - The block size to be written to the file -static void bin_write_block_size(FILE *f, uint_t block_size) { +static void bin_write_block_size(FILE *f, u64 block_size) { fseek(f, offsetof(bin_meta_t, block_size), SEEK_SET); fwrite(&block_size, member_sizeof(bin_meta_t, block_size), 1, f); } diff --git a/include/buffer.h b/include/buffer.h new file mode 100644 index 0000000..2365173 --- /dev/null +++ b/include/buffer.h @@ -0,0 +1,232 @@ +// buffer.h - Dynamic buffer with metadata +// +// Thread safety: Not thread-safe. External synchronization required. +// Memory safety: NULL-safe on all operations. buffer_resize returns +// original pointer on failure; use buffer_resize_ok for NULL on failure. +// Resize policy: doubles when usage > 80%, halves when < 20% (min 32). + +#ifndef BUFFER_H +#define BUFFER_H + +#include "type.h" + +typedef struct { + u64 n; // Array capacity + u64 i; // Element count + u64 s; // Element size +} buffer_meta_t; + +#define _buffer_from_meta(x) ((void *)((u8 *)(x) + sizeof(buffer_meta_t))) +#define _buffer_to_meta(x) ((void *)((u8 *)(x) - sizeof(buffer_meta_t))) + +void *buffer_malloc(u64 num, u64 size); +void buffer_free(void *); +void *buffer_resize(void *); +void *buffer_resize_ok(void *); +u64 buffer_count(const void *); +u64 buffer_byte_count(const void *); +u64 buffer_capacity(const void *); +u64 buffer_element_size(const void *); + +#endif // BUFFER_H + +#ifdef BUFFER_IMPLEMENTATION +#ifndef BUFFER_IMPLEMENTED +#define BUFFER_IMPLEMENTED + +#include <stdint.h> +#include <stdlib.h> + +// buffer_malloc() +// +// Allocate a dynamic buffer with embedded metadata +// +// n - Initial element capacity +// s - Element size in bytes +// +// return - Pointer to data region, or NULL on failure + +void *buffer_malloc(u64 n, u64 s) { + if (n == 0 || s == 0) + return NULL; + if (n > (SIZE_MAX - sizeof(buffer_meta_t)) / s) + return NULL; + + void *x = malloc((n * s) + sizeof(buffer_meta_t)); + if (!x) + return NULL; + + buffer_meta_t *meta = (buffer_meta_t *)x; + meta->i = 0; + meta->n = n; + meta->s = s; + + return _buffer_from_meta(x); +} + +// buffer_free() +// +// Release a dynamic buffer and its metadata +// +// buffer - Pointer returned by buffer_malloc + +void buffer_free(void *buffer) { + if (buffer == NULL) + return; + buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer); + meta->n = 0; + meta->i = 0; + meta->s = 0; + free(_buffer_to_meta(buffer)); +} + +// buffer_count() +// +// Return the number of elements currently in use +// +// buffer - Pointer to buffer data region +// +// return - Element count, or 0 if buffer is NULL + +u64 buffer_count(const void *buffer) { + if (!buffer) + return 0; + buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer); + return meta->i; +} + +// buffer_byte_count() +// +// Return the number of bytes currently in use +// +// buffer - Pointer to buffer data region +// +// return - Byte count (count * element size), or 0 if buffer is NULL + +u64 buffer_byte_count(const void *buffer) { + if (!buffer) + return 0; + buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer); + if (meta->s == 0 || meta->i > UINT64_MAX / meta->s) + return 0; + return meta->i * meta->s; +} + +// buffer_element_size() +// +// Return the size of each element in bytes +// +// buffer - Pointer to buffer data region +// +// return - Element size, or 0 if buffer is NULL + +u64 buffer_element_size(const void *buffer) { + if (!buffer) + return 0; + buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer); + return meta->s; +} + +// buffer_capacity() +// +// Return the total element capacity +// +// buffer - Pointer to buffer data region +// +// return - Capacity, or 0 if buffer is NULL + +u64 buffer_capacity(const void *buffer) { + if (!buffer) + return 0; + buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer); + return meta->n; +} + +// buffer_resize() +// +// Automatically resize buffer based on usage ratio. Doubles capacity when +// usage > 80%, halves when < 20% (min 32). Returns original pointer on +// realloc failure — use buffer_resize_ok for NULL on failure. +// +// buffer - Pointer to buffer data region +// +// return - New data pointer (may differ from input), or original on failure + +void *buffer_resize(void *buffer) { + if (!buffer) + return NULL; + buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer); + u64 new_n = meta->n; + if (meta->n == 0) + return buffer; + f64 ratio = (f64)meta->i / (f64)meta->n; + + if (ratio > 0.8) { + if (new_n > UINT64_MAX / 2) + return buffer; + new_n *= 2; + } else if (ratio < 0.2 && new_n > 32) { + new_n /= 2; + } + + if (new_n == meta->n) + return buffer; + + if (meta->s == 0 || new_n > (SIZE_MAX - sizeof(buffer_meta_t)) / meta->s) + return buffer; + + void *new_meta = realloc(meta, sizeof(buffer_meta_t) + new_n * meta->s); + if (!new_meta) + return buffer; + + meta = (buffer_meta_t *)new_meta; + meta->n = new_n; + + return _buffer_from_meta(new_meta); +} + +// buffer_resize_ok() +// +// Same as buffer_resize, but returns NULL on realloc failure instead of +// the original pointer. Caller must check return value. +// +// buffer - Pointer to buffer data region +// +// return - New data pointer, original if no resize needed, or NULL on failure + +void *buffer_resize_ok(void *buffer) { + if (!buffer) + return NULL; + buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer); + u64 old_n = meta->n; + u64 new_n = meta->n; + if (meta->n == 0) + return buffer; + f64 ratio = (f64)meta->i / (f64)meta->n; + + if (ratio > 0.8) { + if (new_n > UINT64_MAX / 2) + return buffer; + new_n *= 2; + } else if (ratio < 0.2 && new_n > 32) { + new_n /= 2; + } + + if (new_n == old_n) + return buffer; + + if (meta->s == 0 || new_n > (SIZE_MAX - sizeof(buffer_meta_t)) / meta->s) + return buffer; + + void *new_meta = realloc(meta, sizeof(buffer_meta_t) + new_n * meta->s); + if (!new_meta) + return NULL; + + meta = (buffer_meta_t *)new_meta; + meta->n = new_n; + + return _buffer_from_meta(meta); +} + +#endif /* BUFFER_IMPLEMENTED */ +#endif // BUFFER_IMPLEMENTATION diff --git a/include/direct.h b/include/direct.h index c26907e..4302db0 100644 --- a/include/direct.h +++ b/include/direct.h @@ -1,11 +1,21 @@ -#ifndef DT_H -#define DT_H +// direct.h — Computation graph with topological update +// +// Thread safety: Not thread-safe. External synchronization required. +// Behavior: dt_update does DFS from origin, evaluates nodes in reverse +// order (topological). Uses a global generation counter to avoid +// re-visiting nodes. The counter is u64 and overflows after ~1.8e19 +// calls, at which point reachable node generations are reset. +// Memory: Edges are heap-allocated per dt_connect. Use dt_clear_edges to +// free all edges for a node. -#include <stdbool.h> -#include <stdlib.h> -#include <stdio.h> +#ifndef DIRECT_H +#define DIRECT_H -struct value_t; +/* USER-DEFINED (define before including): + * typedef <type> direct_value_t; + */ + +#include "type.h" typedef struct edge { struct edge *next; @@ -14,108 +24,303 @@ typedef struct edge { typedef struct node { struct edge *edge; - value_t x; - bool flag; - value_t (*function)(struct node *node); + direct_value_t x; + u64 visited_generation; + direct_value_t (*function)(struct node *node); } node_t; -void dt_connect(node_t *, node_t *); +int dt_connect(node_t *, node_t *); +int dt_connect_ok(node_t *, node_t *); void dt_disconnect(node_t *, node_t *); void dt_update(node_t *); +void dt_update_trace(node_t *); +void dt_clear_edges(node_t *); -value_t dt_one(node_t *node); -value_t dt_add(node_t *node); -value_t dt_subtract(node_t *node); +direct_value_t dt_one(node_t *node); +direct_value_t dt_add(node_t *node); +direct_value_t dt_subtract(node_t *node); #endif #ifdef DT_IMPLEMENTATION +#ifndef DT_IMPLEMENTED +#define DT_IMPLEMENTED + +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> + +// dt_connect() / dt_connect_ok() +// +// Add an edge from 'to' to 'from'. When dt_update is called on a node, +// it will recursively evaluate its connected dependents. +// +// to - Destination node (depends on 'from') +// from - Source node +// +// return - 1 on success, 0 on failure + +int dt_connect(node_t *to, node_t *from) { + return dt_connect_ok(to, from); +} + +int dt_connect_ok(node_t *to, node_t *from) { + if (!to || !from) + return 0; -void dt_connect(node_t *to, node_t *from) { edge_t *edge = malloc(sizeof(edge_t)); + if (!edge) + return 0; edge->node = from; edge->next = to->edge; to->edge = edge; + return 1; } +// dt_disconnect() +// +// Remove the edge from 'to' to 'from' + void dt_disconnect(node_t *to, node_t *from) { + if (!to || !from) + return; + edge_t *edge = to->edge; - edge_t *last = NULL; + edge_t *prev = NULL; while (edge) { if (edge->node == from) { - edge_t *tmp = edge; - last->next = edge->next; - free(tmp); + if (prev) { + prev->next = edge->next; + } else { + to->edge = edge->next; + } + free(edge); + break; } - - last = edge; + prev = edge; edge = edge->next; } } -void dt_update(node_t *origin) { - // printf(">: %p - %lf\n", origin, origin->x); +static u64 _dt_generation = 1; - edge_t *edge = origin->edge; - origin->flag = !origin->flag; +static int dt_grow(node_t ***s, node_t ***e, u32 *cap) { + if (*cap > UINT32_MAX / 2) return 0; + u32 nc = (*cap) * 2; + size_t grow_sz = (size_t)nc * sizeof(node_t *); + if (nc > 0 && grow_sz / nc != sizeof(node_t *)) return 0; + node_t **ns = realloc(*s, grow_sz); + if (!ns) return 0; + node_t **ne = realloc(*e, grow_sz); + if (!ne) { + node_t **shrunk = realloc(*s, (size_t)(*cap) * sizeof(node_t *)); + if (!shrunk) + shrunk = ns; + else + free(ns); + *s = shrunk; + return 0; + } + *s = ns; + *e = ne; + *cap = nc; + return 1; +} - while (edge) { - if (origin->flag != edge->node->flag) { - dt_update(edge->node); +static void dt_update_impl(node_t *origin) { + if (!origin || !origin->function) + return; + u32 cap = 64; + node_t **dfs = malloc(cap * sizeof(node_t *)); + if (!dfs) return; + node_t **eval = malloc(cap * sizeof(node_t *)); + if (!eval) { free(dfs); return; } + u32 sp = 0, ep = 0; + dfs[sp++] = origin; + while (sp > 0) { + node_t *c = dfs[--sp]; + if (!c || !c->function) continue; + if (c->visited_generation == _dt_generation) continue; + c->visited_generation = _dt_generation; + if (!dt_grow(&dfs, &eval, &cap)) { free(dfs); free(eval); return; } + eval[ep++] = c; + edge_t *e = c->edge; + while (e) { + if (e->node && e->node->function && e->node->visited_generation != _dt_generation) { + if (!dt_grow(&dfs, &eval, &cap)) { free(dfs); free(eval); return; } + dfs[sp++] = e->node; + } + e = e->next; } - - edge = edge->next; } - - origin->x = origin->function(origin); - // printf("<: %p - %lf\n", origin, origin->x); + for (u32 i = ep; i > 0; i--) + eval[i - 1]->x = eval[i - 1]->function(eval[i - 1]); + free(dfs); + free(eval); } -void dt_update_trace(node_t *origin) { - printf(">: %p - %lf\n", origin, origin->x); +static void dt_reset_generations(node_t *origin, node_t **dfs, u32 *dfs_sp, + u32 cap, u32 *stack_cap) { + (void)cap; + if (*stack_cap == 0) return; + node_t *c = origin; + if (!c || !c->function) return; + dfs[(*dfs_sp)++] = c; + c->visited_generation = 0; + while (*dfs_sp > 0) { + node_t *n = dfs[--(*dfs_sp)]; + edge_t *e = n->edge; + while (e) { + if (e->node && e->node->function && e->node->visited_generation != 0) { + if (*dfs_sp >= *stack_cap) { + u32 nc = (*stack_cap) * 2; + node_t **nd = realloc(dfs, (size_t)nc * sizeof(node_t *)); + if (nd) { dfs = nd; *stack_cap = nc; } + else return; + } + dfs[(*dfs_sp)++] = e->node; + e->node->visited_generation = 0; + } + e = e->next; + } + } +} - edge_t *edge = origin->edge; - origin->flag = !origin->flag; +// dt_update() +// +// Evaluate the computation graph starting from origin. Performs DFS to +// collect all reachable nodes, then evaluates them in reverse (topological) +// order. Uses generation counters to skip already-evaluated nodes. - while (edge) { - if (origin->flag != edge->node->flag) { - dt_update_trace(edge->node); +void dt_update(node_t *origin) { + if (!origin || !origin->function) + return; + if (_dt_generation >= UINT64_MAX) { + _dt_generation = 1; + u32 cap = 64; + u32 sp = 0; + node_t **dfs = malloc(cap * sizeof(node_t *)); + if (dfs) { + dt_reset_generations(origin, dfs, &sp, cap, &cap); + free(dfs); } - - edge = edge->next; + } else { + _dt_generation++; } + dt_update_impl(origin); +} - origin->x = origin->function(origin); - printf("<: %p - %lf\n", origin, origin->x); +static void dt_update_trace_impl(node_t *origin) { + if (!origin || !origin->function) + return; + u32 cap = 64; + node_t **dfs = malloc(cap * sizeof(node_t *)); + if (!dfs) return; + node_t **eval = malloc(cap * sizeof(node_t *)); + if (!eval) { free(dfs); return; } + u32 sp = 0, ep = 0; + dfs[sp++] = origin; + while (sp > 0) { + node_t *c = dfs[--sp]; + if (!c || !c->function) continue; + if (c->visited_generation == _dt_generation) continue; + c->visited_generation = _dt_generation; + if (!dt_grow(&dfs, &eval, &cap)) { free(dfs); free(eval); return; } + eval[ep++] = c; + fprintf(stderr, ">: %p\n", (void *)c); + edge_t *e = c->edge; + while (e) { + if (e->node && e->node->function && e->node->visited_generation != _dt_generation) { + if (!dt_grow(&dfs, &eval, &cap)) { free(dfs); free(eval); return; } + dfs[sp++] = e->node; + } + e = e->next; + } + } + for (u32 i = ep; i > 0; i--) { + node_t *n = eval[i - 1]; + n->x = n->function(n); + fprintf(stderr, "<: %p\n", (void *)n); + } + free(dfs); + free(eval); } -value_t dt_one(node_t *node) { - return 1; +// dt_update_trace() +// +// Same as dt_update, but prints each node's address to stderr as it is +// visited (">:") and evaluated ("<:") for debugging purposes. + +void dt_update_trace(node_t *origin) { + if (!origin || !origin->function) + return; + if (_dt_generation >= UINT64_MAX) { + _dt_generation = 1; + u32 cap = 64; + u32 sp = 0; + node_t **dfs = malloc(cap * sizeof(node_t *)); + if (dfs) { + dt_reset_generations(origin, dfs, &sp, cap, &cap); + free(dfs); + } + } else { + _dt_generation++; + } + dt_update_trace_impl(origin); } -value_t dt_add(node_t *node) { +// dt_one() - Constant node that always returns 1 +direct_value_t dt_one(node_t *node) { (void)node; return 1; } + +// dt_add() - Sums the values of all connected input nodes plus the node's own value +direct_value_t dt_add(node_t *node) { + if (!node) + return 0; edge_t *edge = node->edge; - value_t x = node->x; + direct_value_t x = node->x; - while(edge) { - x += edge->node->x; + while (edge) { + if (edge->node) + x += edge->node->x; edge = edge->next; } return x; } -value_t dt_subtract(node_t *node) { +// dt_subtract() - Subtracts all connected input node values from the node's own value +direct_value_t dt_subtract(node_t *node) { + if (!node) + return 0; edge_t *edge = node->edge; - value_t x = node->x; + direct_value_t x = node->x; - while(edge) { - x -= edge->node->x; + while (edge) { + if (edge->node) + x -= edge->node->x; edge = edge->next; } return x; } -#endif +// dt_clear_edges() +// +// Free all edges connected to a node + +void dt_clear_edges(node_t *node) { + if (!node) + return; + edge_t *edge = node->edge; + node->edge = NULL; + + while (edge) { + edge_t *next = edge->next; + free(edge); + edge = next; + } +} + +#endif /* DT_IMPLEMENTED */ +#endif /* DT_IMPLEMENTATION */ diff --git a/include/escape.h b/include/escape.h index 13bd996..db46694 100755 --- a/include/escape.h +++ b/include/escape.h @@ -1,91 +1,110 @@ // escape.h - ESC escape code macros and functions +// +// Thread safety: Safe for concurrent use (no shared state). The macros +// produce string literals; the functions write to the provided FILE*. +// Portability: ANSI escape codes are not supported on Windows Console API +// (use Windows 10+ VT mode or a translation layer). #ifndef ESCAPE_H #define ESCAPE_H - -#include <stdint.h> - +#include "type.h" +#include <stdio.h> #ifdef __cplusplus extern "C" { #endif +#define CSI "\x1B[" -#define CSI "\x1B[" - - -#define ESC_CURSOR_UP( n ) CSI #n "A" -void esc_cursor_up( uint32_t n ); +#define ESC_CURSOR_UP(n) CSI #n "A" +void esc_cursor_up(u32 n); +void esc_fcursor_up(FILE *, u32 n); -#define ESC_CURSOR_DOWN( n ) CSI #n "B" -void esc_cursor_down( uint32_t n ); +#define ESC_CURSOR_DOWN(n) CSI #n "B" +void esc_cursor_down(u32 n); +void esc_fcursor_down(FILE *, u32 n); -#define ESC_CURSOR_LEFT( n ) CSI #n "C" -void esc_cursor_left( uint32_t n ); +#define ESC_CURSOR_LEFT(n) CSI #n "D" +void esc_cursor_left(u32 n); +void esc_fcursor_left(FILE *, u32 n); -#define ESC_CURSOR_RIGHT( n ) CSI #n "D" -void esc_cursor_right( uint32_t n ); +#define ESC_CURSOR_RIGHT(n) CSI #n "C" +void esc_cursor_right(u32 n); +void esc_fcursor_right(FILE *, u32 n); -#define ESC_CURSOR_LINE_NEXT( n ) CSI #n "E" -void esc_cursor_line_next( uint32_t n ); +#define ESC_CURSOR_LINE_NEXT(n) CSI #n "E" +void esc_cursor_line_next(u32 n); +void esc_fcursor_line_next(FILE *, u32 n); -#define ESC_CURSOR_POSITION( x, y ) CSI #y ";" #x "H" -void esc_cursor_position( uint32_t x, uint32_t y ); +#define ESC_CURSOR_POSITION(col, row) CSI #row ";" #col "H" +void esc_cursor_position(u32 col, u32 row); +void esc_fcursor_position(FILE *, u32 col, u32 row); -#define ESC_CLEAR_SCREEN CSI "2J" -void esc_clear_screen( void ); +#define ESC_CLEAR_SCREEN CSI "2J" +void esc_clear_screen(void); +void esc_fclear_screen(FILE *); #define ESC_CLEAR_SCREEN_START CSI "1J" -void esc_clear_screen_start( void ); +void esc_clear_screen_start(void); +void esc_fclear_screen_start(FILE *); #define ESC_CLEAR_SCREEN_END CSI "0J" -void esc_clear_screen_end( void ); +void esc_clear_screen_end(void); +void esc_fclear_screen_end(FILE *); #define ESC_CLEAR_LINE CSI "2K" -void esc_clear_line( void ); +void esc_clear_line(void); +void esc_fclear_line(FILE *); -#define ESC_CLEAR_LINE_START CSI "1L" -void esc_clear_line_start( void ); +#define ESC_CLEAR_LINE_START CSI "1K" +void esc_clear_line_start(void); +void esc_fclear_line_start(FILE *); -#define ESC_CLEAR_LINE_END CSI "0L" -void esc_clear_line_end( void ); +#define ESC_CLEAR_LINE_END CSI "0K" +void esc_clear_line_end(void); +void esc_fclear_line_end(FILE *); -#define ESC_SCROLL_UP( n ) CSI #n "S" -void esc_scroll_up( uint32_t n ); +#define ESC_SCROLL_UP(n) CSI #n "S" +void esc_scroll_up(u32 n); +void esc_fscroll_up(FILE *, u32 n); -#define ESC_SCROLL_DOWN( n ) CSI #n "T" -void esc_scroll_down( uint32_t n ); +#define ESC_SCROLL_DOWN(n) CSI #n "T" +void esc_scroll_down(u32 n); +void esc_fscroll_down(FILE *, u32 n); -#define ESC_SGR "m" +#define ESC_SGR "m" -#define ESC_RESET CSI "0" ESC_SGR -#define ESC_BOLD CSI "1" ESC_SGR -#define ESC_UNDERLINE CSI "4" ESC_SGR -#define ESC_BLINK CSI "5" ESC_SGR -#define ESC_REVERSE CSI "7" ESC_SGR -#define ESC_CONCEAL CSI "8" ESC_SGR -#define ESC_REVEAL CSI "28" ESC_SGR -#define ESC_STRIKETHROUGH CSI "9" ESC_SGR -#define ESC_OVERLINE CSI "53" ESC_SGR +#define ESC_RESET CSI "0" ESC_SGR +#define ESC_BOLD CSI "1" ESC_SGR +#define ESC_UNDERLINE CSI "4" ESC_SGR +#define ESC_BLINK CSI "5" ESC_SGR +#define ESC_REVERSE CSI "7" ESC_SGR +#define ESC_CONCEAL CSI "8" ESC_SGR +#define ESC_REVEAL CSI "28" ESC_SGR +#define ESC_STRIKETHROUGH CSI "9" ESC_SGR +#define ESC_OVERLINE CSI "53" ESC_SGR -#define ESC_COLOR_FG_RGB( r, g, b ) CSI "38;2;" #r ";" #g ";" #b ESC_SGR -void esc_color_fg_rgb( uint32_t r, uint32_t g, uint32_t b ); +#define ESC_COLOR_FG_RGB(r, g, b) CSI "38;2;" #r ";" #g ";" #b ESC_SGR +void esc_color_fg_rgb(u32 r, u32 g, u32 b); +void esc_fcolor_fg_rgb(FILE *, u32 r, u32 g, u32 b); -#define ESC_COLOR_BG_RGB( r, g, b ) CSI "48;2;" #r ";" #g ";" #b ESC_SGR -void esc_color_bg_rgb( uint32_t r, uint32_t g, uint32_t b ); +#define ESC_COLOR_BG_RGB(r, g, b) CSI "48;2;" #r ";" #g ";" #b ESC_SGR +void esc_color_bg_rgb(u32 r, u32 g, u32 b); +void esc_fcolor_bg_rgb(FILE *, u32 r, u32 g, u32 b); -#define ESC_COLOR_FG_256( n ) CSI "38;5;" #n ESC_SGR -void esc_color_fg_256( uint32_t r, uint32_t g, uint32_t b ); +#define ESC_COLOR_FG_256(n) CSI "38;5;" #n ESC_SGR +void esc_color_fg_256(u32 n); +void esc_fcolor_fg_256(FILE *, u32 n); -#define ESC_COLOR_BG_256( n ) CSI "48;5;" #n ESC_SGR -void esc_color_bg_256( uint32_t r, uint32_t g, uint32_t b ); - -#define ESC_COLOR_FG( n ) CSI "3" #n ESC_SGR -#define ESC_COLOR_BG( n ) CSI "4" #n ESC_SGR -#define ESC_COLOR_FG_BRIGHT( n ) CSI "9" #n ESC_SGR -#define ESC_COLOR_BG_BRIGHT( n ) CSI "10" #n ESC_SGR +#define ESC_COLOR_BG_256(n) CSI "48;5;" #n ESC_SGR +void esc_color_bg_256(u32 n); +void esc_fcolor_bg_256(FILE *, u32 n); +#define ESC_COLOR_FG(n) CSI "3" #n ESC_SGR +#define ESC_COLOR_BG(n) CSI "4" #n ESC_SGR +#define ESC_COLOR_FG_BRIGHT(n) CSI "9" #n ESC_SGR +#define ESC_COLOR_BG_BRIGHT(n) CSI "10" #n ESC_SGR #ifdef __cplusplus } @@ -93,29 +112,73 @@ void esc_color_bg_256( uint32_t r, uint32_t g, uint32_t b ); #endif // ESCAPE_H - #ifdef ESCAPE_IMPLEMENTATION #include <stdio.h> -void esc_cursor_up( uint32_t n ) { fprintf( stdout, CSI "%dA", n ); } -void esc_cursor_down( uint32_t n ) { fprintf( stdout, CSI "%dB", n ); } -void esc_cursor_left( uint32_t n ) { fprintf( stdout, CSI "%dC", n ); } -void esc_cursor_right( uint32_t n ) { fprintf( stdout, CSI "%dD", n ); } -void esc_cursor_line_next( uint32_t n ) { fprintf( stdout, CSI "%dE", n ); } -void esc_cursor_position( uint32_t x, uint32_t y ) { fprintf( stdout, CSI "%d;%dH", y, x ); } -void esc_clear_screen( void ) { fputs( CSI "2J", stdout ); } -void esc_clear_screen_start( void ) { fputs( CSI "1J", stdout ); } -void esc_clear_screen_end( void ) { fputs( CSI "0J", stdout ); } -void esc_clear_line( void ) { fputs( CSI "2L", stdout ); } -void esc_clear_line_start( void ) { fputs( CSI "1L", stdout ); } -void esc_clear_line_end( void ) { fputs( CSI "0L", stdout ); } -void esc_scroll_up( uint32_t n ) { fprintf( stdout, "%dS", n ); } -void esc_scroll_down( uint32_t n ) { fprintf( stdout, "%dT", n ); } +void esc_fcursor_up(FILE *f, u32 n) { if (!f) return; fprintf(f, CSI "%uA", (unsigned)n); } +void esc_fcursor_down(FILE *f, u32 n) { if (!f) return; fprintf(f, CSI "%uB", (unsigned)n); } +void esc_fcursor_left(FILE *f, u32 n) { if (!f) return; fprintf(f, CSI "%uD", (unsigned)n); } +void esc_fcursor_right(FILE *f, u32 n) { if (!f) return; fprintf(f, CSI "%uC", (unsigned)n); } +void esc_fcursor_line_next(FILE *f, u32 n) { if (!f) return; fprintf(f, CSI "%uE", (unsigned)n); } +void esc_fcursor_position(FILE *f, u32 col, u32 row) { + if (!f) return; + fprintf(f, CSI "%u;%uH", (unsigned)row, (unsigned)col); +} +void esc_fclear_screen(FILE *f) { if (!f) return; fputs(CSI "2J", f); } +void esc_fclear_screen_start(FILE *f) { if (!f) return; fputs(CSI "1J", f); } +void esc_fclear_screen_end(FILE *f) { if (!f) return; fputs(CSI "0J", f); } +void esc_fclear_line(FILE *f) { if (!f) return; fputs(CSI "2K", f); } +void esc_fclear_line_start(FILE *f) { if (!f) return; fputs(CSI "1K", f); } +void esc_fclear_line_end(FILE *f) { if (!f) return; fputs(CSI "0K", f); } +void esc_fscroll_up(FILE *f, u32 n) { if (!f) return; fprintf(f, CSI "%uS", (unsigned)n); } +void esc_fscroll_down(FILE *f, u32 n) { if (!f) return; fprintf(f, CSI "%uT", (unsigned)n); } -void esc_color_fg_rgb( uint32_t r, uint32_t g, uint32_t b ) { fprintf( stdout, CSI "38;2;%d;%d;%d" ESC_SGR, r, g, b ); } -void esc_color_bg_rgb( uint32_t r, uint32_t g, uint32_t b ) { fprintf( stdout, CSI "48;2;%d;%d;%d" ESC_SGR, r, g, b ); } -void esc_color_fg_256( uint32_t r, uint32_t g, uint32_t b ) { fprintf( stdout, CSI "38;5;%d;%d;%d" ESC_SGR, r, g, b ); } -void esc_color_bg_256( uint32_t r, uint32_t g, uint32_t b ) { fprintf( stdout, CSI "48;5;%d;%d;%d" ESC_SGR, r, g, b ); } +void esc_fcolor_fg_rgb(FILE *f, u32 r, u32 g, u32 b) { + if (!f) return; + fprintf(f, CSI "38;2;%u;%u;%u" ESC_SGR, (unsigned)r, (unsigned)g, (unsigned)b); +} +void esc_fcolor_bg_rgb(FILE *f, u32 r, u32 g, u32 b) { + if (!f) return; + fprintf(f, CSI "48;2;%u;%u;%u" ESC_SGR, (unsigned)r, (unsigned)g, (unsigned)b); +} +void esc_fcolor_fg_256(FILE *f, u32 n) { + if (!f) return; + fprintf(f, CSI "38;5;%u" ESC_SGR, (unsigned)n); +} +void esc_fcolor_bg_256(FILE *f, u32 n) { + if (!f) return; + fprintf(f, CSI "48;5;%u" ESC_SGR, (unsigned)n); +} + +void esc_cursor_up(u32 n) { esc_fcursor_up(stdout, n); } +void esc_cursor_down(u32 n) { esc_fcursor_down(stdout, n); } +void esc_cursor_left(u32 n) { esc_fcursor_left(stdout, n); } +void esc_cursor_right(u32 n) { esc_fcursor_right(stdout, n); } +void esc_cursor_line_next(u32 n) { esc_fcursor_line_next(stdout, n); } +void esc_cursor_position(u32 col, u32 row) { + esc_fcursor_position(stdout, col, row); +} +void esc_clear_screen(void) { esc_fclear_screen(stdout); } +void esc_clear_screen_start(void) { esc_fclear_screen_start(stdout); } +void esc_clear_screen_end(void) { esc_fclear_screen_end(stdout); } +void esc_clear_line(void) { esc_fclear_line(stdout); } +void esc_clear_line_start(void) { esc_fclear_line_start(stdout); } +void esc_clear_line_end(void) { esc_fclear_line_end(stdout); } +void esc_scroll_up(u32 n) { esc_fscroll_up(stdout, n); } +void esc_scroll_down(u32 n) { esc_fscroll_down(stdout, n); } + +void esc_color_fg_rgb(u32 r, u32 g, u32 b) { + esc_fcolor_fg_rgb(stdout, r, g, b); +} +void esc_color_bg_rgb(u32 r, u32 g, u32 b) { + esc_fcolor_bg_rgb(stdout, r, g, b); +} +void esc_color_fg_256(u32 n) { + esc_fcolor_fg_256(stdout, n); +} +void esc_color_bg_256(u32 n) { + esc_fcolor_bg_256(stdout, n); +} #endif // ESCAPE_IMPLEMENTATION
\ No newline at end of file diff --git a/include/flat.h b/include/flat.h index 17a1cc4..9bbde7a 100755 --- a/include/flat.h +++ b/include/flat.h @@ -1,16 +1,30 @@ // flat.h - Directory traversal utility functions +// +// Thread safety: Not thread-safe. External synchronization required. +// Memory: flat_directory_entries returns a NULL-terminated array of +// heap-allocated strings. Use flat_free_entries to release both. +// Portability: Provides POSIX (dirent.h) and Windows (FindFirstFileA) impls. #ifndef FLAT_H +#define FLAT_H -#include <stdint.h> +#include "type.h" #include <sys/stat.h> +#ifdef _WIN32 +#include <direct.h> +#include <windows.h> +#define MKDIR(x) (mkdir(x)) +#else +#include <dirent.h> +#define MKDIR(x) (mkdir(x, 0755)) +#endif + char *flat_path(int, ...); -int64_t flat_directory_entry_count(char const *); +void flat_free_entries(char **); +i64 flat_directory_entry_count(char const *); char **flat_directory_entries(char const *); -#define MKDIR(x) (mkdir(x, 0777)) - #endif // FLAT_H #ifdef FLAT_IMPLEMENTATION @@ -19,7 +33,16 @@ char **flat_directory_entries(char const *); #include <stdlib.h> #include <string.h> -#include <dirent.h> +#ifndef _WIN32 + +// flat_path() +// +// Join path components into a single allocated string. Uses '/' separator +// on POSIX, '\\' on Windows. Caller must free the result. +// +// s_n - Number of string components +// +// return - Allocated path string, or NULL on failure char *flat_path(int s_n, ...) { va_list list; @@ -28,45 +51,55 @@ char *flat_path(int s_n, ...) { if (s_n < 1) return NULL; - // First, measure the total length required. va_start(list, s_n); for (int i = 0; i < s_n; i++) { const char *s = va_arg(list, char *); - c_n += strlen(s); + if (s) + c_n += strlen(s); } va_end(list); - // Allocate return buffer. - char *r = malloc(c_n + 1); + size_t separators = (s_n > 1 ? (size_t)(s_n - 1) : 0); + if (c_n > SIZE_MAX - separators - 1) + return NULL; + size_t total = c_n + separators + 1; + char *r = malloc(total); if (r == NULL) return NULL; - // Concatenate all the strings into the return buffer. char *d = r; va_start(list, s_n); for (int i = 0; i < s_n; i++) { const char *s = va_arg(list, char *); - // This loop is a strcpy. - while ((*d++ = *s++)) - ; - d--; + // Add separator between components (not before the first). + if (i > 0) + *d++ = '/'; + + if (s) { + while ((*d++ = *s++)) + ; + d--; // Step back over the null terminator. + } } va_end(list); + *d = '\0'; return r; } -int64_t flat_directory_entry_count(char const *path) { +i64 flat_directory_entry_count(char const *path) { DIR *dir; struct dirent *ent; + if (path == NULL) + return 0; if (!(dir = opendir(path))) { return 0; } - int64_t n = 0; + i64 n = 0; while ((ent = readdir(dir))) { if (!strcmp(ent->d_name, ".")) @@ -83,38 +116,234 @@ int64_t flat_directory_entry_count(char const *path) { return n; } -char **flat_directory_entries(char const *path) { - int64_t n = flat_directory_entry_count(path); - char **entries = calloc(n + 1, sizeof(char **)); +static int flat_skip_entry(struct dirent *ent) { + if (!ent) return 1; + if (!strcmp(ent->d_name, ".")) return 1; + if (!strcmp(ent->d_name, "..")) return 1; + return 0; +} +char **flat_directory_entries(char const *path) { DIR *dir; struct dirent *ent; - int64_t i = 0; - int64_t entry_n = 0; - + if (path == NULL) + return NULL; if (!(dir = opendir(path))) { return NULL; } - while (i < n) { - ent = readdir(dir); - if (!strcmp(ent->d_name, ".")) - continue; + i64 capacity = 16; + char **entries = calloc((size_t)capacity, sizeof(char *)); + if (!entries) { + closedir(dir); + return NULL; + } - if (!strcmp(ent->d_name, "..")) + i64 count = 0; + while ((ent = readdir(dir))) { + if (flat_skip_entry(ent)) continue; - entry_n = strlen(ent->d_name); - entries[i] = malloc(entry_n + 1); - strcpy(entries[i], ent->d_name); + if (count >= capacity - 1) { + if (capacity > INT64_MAX / 2) { + flat_free_entries(entries); + closedir(dir); + return NULL; + } + i64 new_capacity = capacity * 2; + if ((size_t)new_capacity > SIZE_MAX / sizeof(char *)) { + flat_free_entries(entries); + closedir(dir); + return NULL; + } + char **new_entries = realloc(entries, (size_t)new_capacity * sizeof(char *)); + if (!new_entries) { + flat_free_entries(entries); + closedir(dir); + return NULL; + } + entries = new_entries; + capacity = new_capacity; + } - i++; + size_t entry_n = strlen(ent->d_name); + entries[count] = malloc(entry_n + 1); + if (!entries[count]) { + flat_free_entries(entries); + closedir(dir); + return NULL; + } + strcpy(entries[count], ent->d_name); + count++; } + entries[count] = NULL; + closedir(dir); return entries; } -#endif // FLAT_IMPELEMTATION +void flat_free_entries(char **entries) { + if (!entries) + return; + i64 i = 0; + while (entries[i]) { + free(entries[i]); + i++; + } + free(entries); +} + +#else /* _WIN32 */ + +#include <errno.h> +#include <windows.h> + +static int flat_skip_entry_win(char const *name) { + if (!name) return 1; + if (name[0] == '.' && (name[1] == '\0' || (name[1] == '.' && name[2] == '\0'))) + return 1; + return 0; +} + +char *flat_path(int s_n, ...) { + va_list list; + size_t c_n = 0; + + if (s_n < 1) + return NULL; + + va_start(list, s_n); + for (int i = 0; i < s_n; i++) { + const char *s = va_arg(list, char *); + if (s) + c_n += strlen(s); + } + va_end(list); + + size_t separators = (s_n > 1 ? (size_t)(s_n - 1) : 0); + if (c_n > SIZE_MAX - separators - 1) + return NULL; + size_t total = c_n + separators + 1; + char *r = malloc(total); + if (r == NULL) + return NULL; + + char *d = r; + va_start(list, s_n); + for (int i = 0; i < s_n; i++) { + const char *s = va_arg(list, char *); + if (i > 0) + *d++ = '\\'; + if (s) { + while ((*d++ = *s++)) + ; + d--; + } + } + va_end(list); + *d = '\0'; + return r; +} + +i64 flat_directory_entry_count(char const *path) { + if (path == NULL) + return 0; + char pattern[4096]; + if (strlen(path) > sizeof(pattern) - 3) + return 0; + sprintf(pattern, "%s\\*", path); + + WIN32_FIND_DATAA fd; + HANDLE h = FindFirstFileA(pattern, &fd); + if (h == INVALID_HANDLE_VALUE) + return 0; + + i64 n = 0; + do { + if (!flat_skip_entry_win(fd.cFileName)) + n++; + } while (FindNextFileA(h, &fd)); + + FindClose(h); + return n; +} + +char **flat_directory_entries(char const *path) { + if (path == NULL) + return NULL; + char pattern[4096]; + if (strlen(path) > sizeof(pattern) - 3) + return NULL; + sprintf(pattern, "%s\\*", path); + + WIN32_FIND_DATAA fd; + HANDLE h = FindFirstFileA(pattern, &fd); + if (h == INVALID_HANDLE_VALUE) + return NULL; + + i64 capacity = 16; + char **entries = calloc((size_t)capacity, sizeof(char *)); + if (!entries) { + FindClose(h); + return NULL; + } + + i64 count = 0; + do { + if (flat_skip_entry_win(fd.cFileName)) + continue; + + if (count >= capacity - 1) { + if (capacity > INT64_MAX / 2) { + flat_free_entries(entries); + FindClose(h); + return NULL; + } + i64 new_capacity = capacity * 2; + if ((size_t)new_capacity > SIZE_MAX / sizeof(char *)) { + flat_free_entries(entries); + FindClose(h); + return NULL; + } + char **new_entries = realloc(entries, (size_t)new_capacity * sizeof(char *)); + if (!new_entries) { + flat_free_entries(entries); + FindClose(h); + return NULL; + } + entries = new_entries; + capacity = new_capacity; + } + + size_t entry_n = strlen(fd.cFileName); + entries[count] = malloc(entry_n + 1); + if (!entries[count]) { + flat_free_entries(entries); + FindClose(h); + return NULL; + } + strcpy(entries[count], fd.cFileName); + count++; + } while (FindNextFileA(h, &fd)); + + entries[count] = NULL; + FindClose(h); + return entries; +} + +void flat_free_entries(char **entries) { + if (!entries) + return; + i64 i = 0; + while (entries[i]) { + free(entries[i]); + i++; + } + free(entries); +} + +#endif /* _WIN32 */ +#endif // FLAT_IMPLEMENTATION diff --git a/include/genetic.h b/include/genetic.h index eadcab5..2ebf985 100755 --- a/include/genetic.h +++ b/include/genetic.h @@ -1,31 +1,35 @@ // genetic.h - A simple genetic algorithm implementation +// +// Thread safety: Not thread-safe. External synchronization required. +// Behavior: rate_selection must be in (0, 1). A value of 1.0 is rejected +// because it results in no evolution (all individuals survive). +// rate_mutation must be >= 0. Returns -1.0 on any parameter error. #ifndef GENETIC_H #define GENETIC_H -#include <assert.h> -#include <stdint.h> +#include "type.h" -struct ga_individual_t; +// ga_individual_t must be typedef'd by the user before including this header. // ga_crossover_t // // Type definition for a crossover function // -// uintptr_t * - The address for the child pointer -// uintptr_t - Parent pointer -// uintptr_t - Parent pointer +// ga_individual_t * - The address for the child individual +// ga_individual_t - Parent individual 0 +// ga_individual_t - Parent individual 1 typedef void (*ga_crossover_t)(ga_individual_t *, ga_individual_t, - ga_individual_t); + ga_individual_t); // ga_mutation_t // -// Type definition for a crossover function +// Type definition for a mutation function // -// uintptr_t - The individual being mutated +// ga_individual_t * - The individual being mutated -typedef void (*ga_mutation_t)(ga_individual_t); +typedef void (*ga_mutation_t)(ga_individual_t *); // ga_fitness_t() // @@ -34,12 +38,12 @@ typedef void (*ga_mutation_t)(ga_individual_t); // uintptr_t - The individual on which to run the fitness function // void const * - The user defined data pointer -typedef double (*ga_fitness_t)(ga_individual_t, void const *); +typedef f64 (*ga_fitness_t)(ga_individual_t, void const *); -double ga_generation(ga_individual_t *, uint32_t, double, double, ga_fitness_t, - void const *, ga_crossover_t, ga_mutation_t); +f64 ga_generation(ga_individual_t *, u32, f64, f64, ga_fitness_t, + void const *, ga_crossover_t, ga_mutation_t); -#endif // ga_H +#endif #ifdef GENETIC_IMPLEMENTATION // IMPLEMENTATION @@ -48,7 +52,7 @@ double ga_generation(ga_individual_t *, uint32_t, double, double, ga_fitness_t, #include <string.h> #include <tgmath.h> -// ga_finess_sort() +// ga_fitness_sort() // // Run the fitness function on // @@ -59,38 +63,61 @@ double ga_generation(ga_individual_t *, uint32_t, double, double, ga_fitness_t, // // return - The error for the best performing individual -static double ga_fitness_sort(ga_individual_t *population, - uint32_t population_n, ga_fitness_t fitness, - void const *fitness_data) { - double *fitness_buffer = calloc(population_n, sizeof(double)); - double fitness_current = 0; - ga_individual_t individual; +static f64 ga_fitness_sort(ga_individual_t *population, + u32 population_n, ga_fitness_t fitness, + void const *fitness_data) { + if (!population || !fitness || population_n == 0) + return -1; - // Insertion sort - uint32_t i, j, k; - for (i = 0; i < population_n; i++) { - fitness_current = fabs(fitness(population[i], fitness_data)); - individual = population[i]; - // for (j = i; j > 0 && fitness_current > fitness_buffer[j - 1]; j--) { - for (j = i; j > 0 && fitness_current < fitness_buffer[j - 1]; j--) { - } + f64 *fitness_buffer = calloc((size_t)population_n, sizeof(f64)); + if (!fitness_buffer) + return -1; - // Shift array back by one for sorting - for (k = i; k > j; k--) { - population[k] = population[k - 1]; - fitness_buffer[k] = fitness_buffer[k - 1]; - } + for (u32 i = 0; i < population_n; i++) { + fitness_buffer[i] = fabs(fitness(population[i], fitness_data)); + } - population[j] = individual; - fitness_buffer[j] = fitness_current; + // Index array for indirect sort + u32 *indices = malloc((size_t)population_n * sizeof(u32)); + if (!indices) { + free(fitness_buffer); + return -1; } + for (u32 i = 0; i < population_n; i++) + indices[i] = i; - // for (i = 0; i < population_n; i++) { - // printf("%u - %lf\n", i, fitness_buffer[i]); - // } + // Shell sort on indices by fitness value (indirect sort, only rearrange indices) + { + u32 gap = population_n / 2; + while (gap > 0) { + for (u32 i = gap; i < population_n; i++) { + u32 temp = indices[i]; + f64 temp_f = fitness_buffer[temp]; + u32 j; + for (j = i; j >= gap && fitness_buffer[indices[j - gap]] > temp_f; j -= gap) { + indices[j] = indices[j - gap]; + } + indices[j] = temp; + } + gap /= 2; + } + } + + // Copy sorted individuals back + ga_individual_t *sorted = calloc((size_t)population_n, sizeof(ga_individual_t)); + if (!sorted) { + free(fitness_buffer); + free(indices); + return -1; + } + for (u32 i = 0; i < population_n; i++) + sorted[i] = population[indices[i]]; + memcpy(population, sorted, (size_t)population_n * sizeof(ga_individual_t)); - double error = fitness_buffer[0]; + f64 error = fitness_buffer[indices[0]]; + free(sorted); free(fitness_buffer); + free(indices); return error; } @@ -113,30 +140,37 @@ static double ga_fitness_sort(ga_individual_t *population, // // return - The error of the best performing individual -double ga_generation(ga_individual_t *population, uint32_t population_n, - double rate_selection, double rate_mutation, - ga_fitness_t fitness, void const *fitness_data, - ga_crossover_t crossover, ga_mutation_t mutation) { - // assert(0 < rate_selection && rate_selection <= 1.0); - // assert(0 < rate_mutation && rate_mutation <= 1.0); - assert(2 < population_n); +f64 ga_generation(ga_individual_t *population, u32 population_n, + f64 rate_selection, f64 rate_mutation, + ga_fitness_t fitness, void const *fitness_data, + ga_crossover_t crossover, ga_mutation_t mutation) { + if (!population || !fitness || !crossover || !mutation) + return -1; + if (rate_selection <= 0 || rate_selection >= 1.0) + return -1; + if (rate_mutation < 0) + return -1; + if (population_n < 3) + return -1; - uint32_t selection_n = rate_selection * population_n; + u32 selection_n = (u32)(rate_selection * (f64)population_n); + if (selection_n >= population_n) + return -1; // Crossover - for (uint32_t i = selection_n; i < population_n; i++) { - uint32_t parent_i = rand() % selection_n; - uint32_t parent_j = rand() % selection_n; + for (u32 i = selection_n; i < population_n; i++) { + u32 parent_i = (u32)((u64)rand() * (u64)selection_n / ((u64)RAND_MAX + 1)); + u32 parent_j = (u32)((u64)rand() * (u64)selection_n / ((u64)RAND_MAX + 1)); - // printf("%p - %p\n", &population[i], population[i]); crossover(&population[i], population[parent_i], population[parent_j]); } - // Mutation - uint32_t mutation_n = rate_mutation * (population_n - selection_n); - for (uint32_t i = 0; i < mutation_n; i++) { - uint32_t mutation_i = rand() % (population_n - selection_n) + selection_n; - mutation(population[mutation_i]); + // Mutation count + u32 mutation_n = (u32)(rate_mutation * (f64)(population_n - selection_n)); + for (u32 i = 0; i < mutation_n; i++) { + u32 range = population_n - selection_n; + u32 mutation_i = selection_n + (u32)((u64)rand() * (u64)range / ((u64)RAND_MAX + 1)); + mutation(&population[mutation_i]); } // Fitness diff --git a/include/interpolate.h b/include/interpolate.h index 1f79405..da23315 100755 --- a/include/interpolate.h +++ b/include/interpolate.h @@ -1,31 +1,194 @@ // Math for Game Programmers: Fast and Funky 1D Nonlinear Transformations // https://www.youtube.com/watch?v=mr5xkf6zSzk +// +// Thread safety: Safe for concurrent use (no shared state, pure functions). +// Macros: Namespaced INTERP_* variants are collision-safe. Legacy un-prefixed +// names are provided via #ifndef guard — if your code already defines e.g. +// "mix", the library will not override it. #ifndef INTERPOLATE_H -#define INTERPOLATE_H +#define INTERPOLATE_H -#define smooth_start_2( t ) ( t * t ) -#define smooth_start_3( t ) ( smooth_start_2( t ) * t ) -#define smooth_start_4( t ) ( smooth_start_3( t ) * t ) -#define smooth_start_5( t ) ( smooth_start_4( t ) * t ) -#define smooth_start_6( t ) ( smooth_start_5( t ) * t ) +// Namespaced macros (safe from collisions). Use these in new code. +#ifndef INTERP_FLIP +#define INTERP_FLIP(x) (1.0 - (double)(x)) +#endif +#ifndef INTERP_SCALE +#define INTERP_SCALE(a, t) ((double)(t) * (double)(a)) +#endif +#ifndef INTERP_REVERSE_SCALE +#define INTERP_REVERSE_SCALE(a, t) ((1.0 - (double)(t)) * (double)(a)) +#endif +#ifndef INTERP_MIX +#define INTERP_MIX(a, b, b_weight) ((double)(a) + (double)(b_weight) * ((double)(b) - (double)(a))) +#endif +#ifndef INTERP_CROSSFADE +#define INTERP_CROSSFADE(a, b, t) ((double)(a) + (double)(t) * ((double)(b) - (double)(a))) +#endif -#define smooth_stop_2( t ) ( flip( smooth_start_2( flip( t ) ) ) ) -#define smooth_stop_3( t ) ( flip( smooth_start_3( flip( t ) ) ) ) -#define smooth_stop_4( t ) ( flip( smooth_start_4( flip( t ) ) ) ) -#define smooth_stop_5( t ) ( flip( smooth_start_5( flip( t ) ) ) ) -#define smooth_stop_6( t ) ( flip( smooth_start_6( flip( t ) ) ) ) +#ifndef INTERP_SMOOTH_START_2 +#define INTERP_SMOOTH_START_2(t) ((double)(t) * (double)(t)) +#endif +#ifndef INTERP_SMOOTH_START_3 +#define INTERP_SMOOTH_START_3(t) (INTERP_SMOOTH_START_2(t) * (double)(t)) +#endif +#ifndef INTERP_SMOOTH_START_4 +#define INTERP_SMOOTH_START_4(t) (INTERP_SMOOTH_START_3(t) * (double)(t)) +#endif +#ifndef INTERP_SMOOTH_START_5 +#define INTERP_SMOOTH_START_5(t) (INTERP_SMOOTH_START_4(t) * (double)(t)) +#endif +#ifndef INTERP_SMOOTH_START_6 +#define INTERP_SMOOTH_START_6(t) (INTERP_SMOOTH_START_5(t) * (double)(t)) +#endif -#define smooth_step_3( t ) ( crossfade( smooth_start_2( t ), smooth_stop_2( t ), t ) ) -#define mix( a, b, b_weight ) ( a + b_weight * ( b - a ) ) -#define crossfade( a, b, t ) ( a + t * ( b - a ) ) -#define scale( a, t ) ( t * a ) -#define reverse_scale( a, t ) ( ( 1 - t ) * a ) +#ifndef INTERP_SMOOTH_STOP_2 +#define INTERP_SMOOTH_STOP_2(t) (INTERP_FLIP(INTERP_SMOOTH_START_2(INTERP_FLIP(t)))) +#endif +#ifndef INTERP_SMOOTH_STOP_3 +#define INTERP_SMOOTH_STOP_3(t) (INTERP_FLIP(INTERP_SMOOTH_START_3(INTERP_FLIP(t)))) +#endif +#ifndef INTERP_SMOOTH_STOP_4 +#define INTERP_SMOOTH_STOP_4(t) (INTERP_FLIP(INTERP_SMOOTH_START_4(INTERP_FLIP(t)))) +#endif +#ifndef INTERP_SMOOTH_STOP_5 +#define INTERP_SMOOTH_STOP_5(t) (INTERP_FLIP(INTERP_SMOOTH_START_5(INTERP_FLIP(t)))) +#endif +#ifndef INTERP_SMOOTH_STOP_6 +#define INTERP_SMOOTH_STOP_6(t) (INTERP_FLIP(INTERP_SMOOTH_START_6(INTERP_FLIP(t)))) +#endif -#define arch_2( t ) ( scale( flip( t ), t ) ) -#define smooth_start_arch_3( t ) ( scale( arch_2( t ), t ) ) -#define smooth_stop_arch_3( t ) ( reverse_scale( arch_2( t ), t ) ) +#ifndef INTERP_SMOOTH_STEP_3 +#define INTERP_SMOOTH_STEP_3(t) (INTERP_CROSSFADE(INTERP_SMOOTH_START_2(t), INTERP_SMOOTH_STOP_2(t), (double)(t))) +#endif -#define flip( x ) ( 1 - x ) +#ifndef INTERP_ARCH_2 +#define INTERP_ARCH_2(t) (INTERP_SCALE(INTERP_FLIP(t), (double)(t))) +#endif +#ifndef INTERP_SMOOTH_START_ARCH_3 +#define INTERP_SMOOTH_START_ARCH_3(t) (INTERP_SCALE(INTERP_ARCH_2(t), (double)(t))) +#endif +#ifndef INTERP_SMOOTH_STOP_ARCH_3 +#define INTERP_SMOOTH_STOP_ARCH_3(t) (INTERP_REVERSE_SCALE(INTERP_ARCH_2(t), (double)(t))) +#endif -#endif
\ No newline at end of file +// Legacy macro names — alias to namespaced variants when not already defined by user. +#ifndef flip +#define flip(x) INTERP_FLIP(x) +#endif +#ifndef scale +#define scale(a, t) INTERP_SCALE(a, t) +#endif +#ifndef reverse_scale +#define reverse_scale(a, t) INTERP_REVERSE_SCALE(a, t) +#endif +#ifndef mix +#define mix(a, b, b_weight) INTERP_MIX(a, b, b_weight) +#endif +#ifndef crossfade +#define crossfade(a, b, t) INTERP_CROSSFADE(a, b, t) +#endif + +#ifndef smooth_start_2 +#define smooth_start_2(t) INTERP_SMOOTH_START_2(t) +#endif +#ifndef smooth_start_3 +#define smooth_start_3(t) INTERP_SMOOTH_START_3(t) +#endif +#ifndef smooth_start_4 +#define smooth_start_4(t) INTERP_SMOOTH_START_4(t) +#endif +#ifndef smooth_start_5 +#define smooth_start_5(t) INTERP_SMOOTH_START_5(t) +#endif +#ifndef smooth_start_6 +#define smooth_start_6(t) INTERP_SMOOTH_START_6(t) +#endif + +#ifndef smooth_stop_2 +#define smooth_stop_2(t) INTERP_SMOOTH_STOP_2(t) +#endif +#ifndef smooth_stop_3 +#define smooth_stop_3(t) INTERP_SMOOTH_STOP_3(t) +#endif +#ifndef smooth_stop_4 +#define smooth_stop_4(t) INTERP_SMOOTH_STOP_4(t) +#endif +#ifndef smooth_stop_5 +#define smooth_stop_5(t) INTERP_SMOOTH_STOP_5(t) +#endif +#ifndef smooth_stop_6 +#define smooth_stop_6(t) INTERP_SMOOTH_STOP_6(t) +#endif + +#ifndef smooth_step_3 +#define smooth_step_3(t) INTERP_SMOOTH_STEP_3(t) +#endif + +#ifndef arch_2 +#define arch_2(t) INTERP_ARCH_2(t) +#endif +#ifndef smooth_start_arch_3 +#define smooth_start_arch_3(t) INTERP_SMOOTH_START_ARCH_3(t) +#endif +#ifndef smooth_stop_arch_3 +#define smooth_stop_arch_3(t) INTERP_SMOOTH_STOP_ARCH_3(t) +#endif + +/* Function wrappers for debuggability (use these instead of macros when debugging) */ +#ifdef __cplusplus +extern "C" { +#endif + +double interpolate_flip(double t); +double interpolate_scale(double a, double t); +double interpolate_reverse_scale(double a, double t); +double interpolate_mix(double a, double b, double b_weight); +double interpolate_crossfade(double a, double b, double t); +double interpolate_smooth_start_2(double t); +double interpolate_smooth_start_3(double t); +double interpolate_smooth_start_4(double t); +double interpolate_smooth_start_5(double t); +double interpolate_smooth_start_6(double t); +double interpolate_smooth_stop_2(double t); +double interpolate_smooth_stop_3(double t); +double interpolate_smooth_stop_4(double t); +double interpolate_smooth_stop_5(double t); +double interpolate_smooth_stop_6(double t); +double interpolate_smooth_step_3(double t); +double interpolate_arch_2(double t); +double interpolate_smooth_start_arch_3(double t); +double interpolate_smooth_stop_arch_3(double t); + +#ifdef __cplusplus +} +#endif + +#endif + +#ifdef INTERPOLATE_IMPLEMENTATION +#ifndef INTERPOLATE_IMPLEMENTED +#define INTERPOLATE_IMPLEMENTED + +double interpolate_flip(double t) { return flip(t); } +double interpolate_scale(double a, double t) { return scale(a, t); } +double interpolate_reverse_scale(double a, double t) { return reverse_scale(a, t); } +double interpolate_mix(double a, double b, double b_weight) { return mix(a, b, b_weight); } +double interpolate_crossfade(double a, double b, double t) { return crossfade(a, b, t); } +double interpolate_smooth_start_2(double t) { return smooth_start_2(t); } +double interpolate_smooth_start_3(double t) { return smooth_start_3(t); } +double interpolate_smooth_start_4(double t) { return smooth_start_4(t); } +double interpolate_smooth_start_5(double t) { return smooth_start_5(t); } +double interpolate_smooth_start_6(double t) { return smooth_start_6(t); } +double interpolate_smooth_stop_2(double t) { return smooth_stop_2(t); } +double interpolate_smooth_stop_3(double t) { return smooth_stop_3(t); } +double interpolate_smooth_stop_4(double t) { return smooth_stop_4(t); } +double interpolate_smooth_stop_5(double t) { return smooth_stop_5(t); } +double interpolate_smooth_stop_6(double t) { return smooth_stop_6(t); } +double interpolate_smooth_step_3(double t) { return smooth_step_3(t); } +double interpolate_arch_2(double t) { return arch_2(t); } +double interpolate_smooth_start_arch_3(double t) { return smooth_start_arch_3(t); } +double interpolate_smooth_stop_arch_3(double t) { return smooth_stop_arch_3(t); } + +#endif /* INTERPOLATE_IMPLEMENTED */ +#endif // INTERPOLATE_IMPLEMENTATION
\ No newline at end of file diff --git a/include/pool.h b/include/pool.h index d418142..7121f18 100755 --- a/include/pool.h +++ b/include/pool.h @@ -1,38 +1,43 @@ // pool.h - Fixed block size, free list based, memory pool +// +// Note: block_s must be >= sizeof(void*) and aligned to maintain proper +// pointer alignment for returned blocks. +// +// Thread safety: Not thread-safe. External synchronization required. +// Memory safety: pool_free validates pointer range, alignment, and detects +// double-free via free-list walk (O(n) in number of free blocks). +// Invalid frees are silently ignored. #ifndef POOL_H #define POOL_H -#include <complex.h> -#include <setjmp.h> -#include <stdint.h> +#include "type.h" typedef struct pool_t { - uint32_t block_n; // Block capacity - uint32_t block_i; // Block count - uint32_t block_s; // Block size in bytes - void *data; // Blocks - void *free; // Free chunk + u32 block_n; // Block capacity + u32 block_i; // Block count + u32 block_s; // Block size in bytes + void *data; // Blocks + void *free; // Free chunk } pool_t; -pool_t *pool_init(uint32_t, uint32_t); -void pool_fini(pool_t *); +pool_t *pool_init(u32, u32); +void pool_fini(pool_t **); void *pool_malloc(pool_t *); void pool_free(pool_t *, void *); +u32 pool_capacity(const pool_t *); +u32 pool_size(const pool_t *); + #endif // POOL_H -#define POOL_IMPLEMENTATION #ifdef POOL_IMPLEMENTATION // IMPLEMENTATION -#define POOL_MULTIPLIER_RESIZE 2 -#define POOL_BLOCK_N 10 - -#include <stdio.h> +#include <stddef.h> +#include <assert.h> #include <stdlib.h> -static void pool_print(pool_t *pool); -static void pool_free_list(uintptr_t *, uint32_t, uint32_t); +static void pool_free_list(uintptr_t *, u32, u32); // pool_init() // @@ -41,16 +46,32 @@ static void pool_free_list(uintptr_t *, uint32_t, uint32_t); // block_s - The size of a block in bytes // block_n - The number of initial blocks -pool_t *pool_init( uint32_t block_s, uint32_t block_n) { +pool_t *pool_init(u32 block_s, u32 block_n) { + if (block_n == 0) + return NULL; + if (block_s < sizeof(void *) || block_s % sizeof(void *) != 0) + return NULL; + pool_t *pool = (pool_t *)malloc(sizeof(pool_t)); + if (!pool) + return NULL; // Set size and count pool->block_n = block_n; pool->block_s = block_s; + pool->block_i = 0; + if (block_n != 0 && block_s > SIZE_MAX / (size_t)block_n) { + free(pool); + return NULL; + } pool->data = calloc(block_n, block_s); - pool->free = pool->data; + if (!pool->data) { + free(pool); + return NULL; + } + pool->free = pool->data; pool_free_list((uintptr_t *)pool->data, block_n, block_s); return pool; @@ -63,6 +84,8 @@ pool_t *pool_init( uint32_t block_s, uint32_t block_n) { // pool - A pointer to the pool object void *pool_malloc(pool_t *pool) { + if (!pool) + return NULL; uintptr_t *free = (uintptr_t *)pool->free; if (free) { @@ -80,6 +103,31 @@ void *pool_malloc(pool_t *pool) { // pool - A pointer to the pool object void pool_free(pool_t *pool, void *p) { + if (!pool || !p || !pool->data) + return; + // Validate pointer is within pool range + u8 *base = (u8 *)pool->data; + u8 *ptr = (u8 *)p; + if ((u64)pool->block_n > UINT64_MAX / (u64)pool->block_s) + return; + u64 total = (u64)pool->block_n * pool->block_s; + if (total > SIZE_MAX) + return; + u8 *end = base + (size_t)total; + if (ptr < base || ptr >= end) + return; + // Validate pointer is aligned to block size + if ((ptr - base) % pool->block_s != 0) + return; + // Check for double-free: walk free list to detect already-freed block + { + uintptr_t *cur = (uintptr_t *)pool->free; + while (cur) { + if ((uintptr_t)cur == (uintptr_t)p) + return; + cur = (uintptr_t *)*cur; + } + } // Convert the pointer into a usable type uintptr_t *free = (uintptr_t *)p; @@ -89,30 +137,21 @@ void pool_free(pool_t *pool, void *p) { // Set the pool's free head to the newly freed pointer pool->free = (void *)free; - pool->block_i--; + if (pool->block_i > 0) + pool->block_i--; } -uint32_t pool_capacity(pool_t *pool) { - return pool->block_n; -} +u32 pool_capacity(const pool_t *pool) { if (!pool) return 0; return pool->block_n; } -uint32_t pool_size(pool_t *pool) { - return pool->block_i; -} +u32 pool_size(const pool_t *pool) { if (!pool) return 0; return pool->block_i; } -static void pool_print(pool_t *pool) { - uintptr_t *ptr = (uintptr_t *)pool->free; - while (((uintptr_t)ptr - (uintptr_t)pool->data) < - pool->block_n * pool->block_s) { - printf("%p %lx\n", ptr, *ptr); - ptr = (uintptr_t *)(((uint8_t *)ptr) + pool->block_s); - } -} +static void pool_free_list(uintptr_t *block, u32 block_n, + u32 block_s) { + if (block_n == 0) + return; -static void pool_free_list(uintptr_t *block, uint32_t block_n, - uint32_t block_s) { - uint8_t *ptr = (uint8_t *)block; - for (int i = 0; i < block_n - 1; i++) { + u8 *ptr = (u8 *)block; + for (u32 i = 0; i < block_n - 1; i++) { uintptr_t *tmp = (uintptr_t *)ptr; *tmp = (uintptr_t)ptr + block_s; ptr = ptr + block_s; @@ -121,4 +160,12 @@ static void pool_free_list(uintptr_t *block, uint32_t block_n, *(uintptr_t *)ptr = (uintptr_t)0; } +void pool_fini(pool_t **pool) { + if (pool && *pool) { + free((*pool)->data); + free(*pool); + *pool = NULL; + } +} + #endif // POOL_IMPLEMENTATION diff --git a/include/pushdown.h b/include/pushdown.h index aa7c308..5369cfc 100644 --- a/include/pushdown.h +++ b/include/pushdown.h @@ -1,11 +1,23 @@ +// pushdown.h — Stack-based pushdown automata with 65+ math/stack operations +// +// Thread safety: Not thread-safe. External synchronization required. +// Behavior: Instructions execute sequentially until END. Invalid instruction +// values cause immediate termination (pushdown_run) or validation failure +// (pushdown_validate). Arithmetic on invalid input (div/0, sqrt negative, +// log <= 0, etc.) returns 0 rather than signaling error. + #ifndef PUSHDOWN_H #define PUSHDOWN_H -typedef pushdown_value_t stack_value_t; -#include "./stack.h" +/* USER-DEFINED (define before including pushdown.h): + * typedef <type> stack_value_t; (required by stack.h) + * typedef <type> pushdown_value_t; (required by pushdown.h) + */ + +#include "stack.h" typedef enum { - END, + NOOP, PUSH, POP, SKIP, @@ -14,12 +26,18 @@ typedef enum { SUB, MUL, DIV, + RECIP, + INC, + DEC, + SIGN, + NEG, SIN, COS, TAN, ASIN, ACOS, ATAN, + ATAN2, SINH, COSH, TANH, @@ -27,111 +45,830 @@ typedef enum { ACOSH, ATANH, EXP, + POW, LOG, SQRT, - ABS + ABS, + CEIL, + FLOOR, + ERF, + GAMMA, + MIN, + MAX, + CLAMP, + ROUNDD, + FRACT, + MOD, + LOG10, + LOG2, + SIGNUM, + SWAP, + ROT3, + DEPTH, + OVER, + PICK, + DROP2, + NIP, + TUCK, + EQUAL, + LESS, + GREATER, + COMPARE, + PI_CONST, + E_CONST, + RAND, + SQUARE, + CUBE, + RSQRT, + SORT2, + SORT3, + MINMAX, + END } pushdown_instruction_t; void pushdown_run(stack_t *, stack_t *, pushdown_instruction_t *); +u32 pushdown_instruction_count(pushdown_instruction_t *); +int pushdown_validate(pushdown_instruction_t *); +void pushdown_print(pushdown_instruction_t *); #endif #ifdef PUSHDOWN_IMPLEMENTATION +#ifndef PUSHDOWN_IMPLEMENTED +#define PUSHDOWN_IMPLEMENTED #include <tgmath.h> +static void _noop(stack_t *output, stack_t *input) { (void)output; (void)input; } + +static void _push(stack_t *output, stack_t *input) { + if (input->size < 1) + return; + pushdown_value_t x = stack_peek(input); + if (!stack_push(output, x)) + return; + stack_pop(input); +} + +static void _pop(stack_t *output, stack_t *input) { (void)input; stack_pop(output); } + +static void _skip(stack_t *output, stack_t *input) { (void)output; stack_pop(input); } + +static void _copy(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_peek(output); + if (!stack_push(output, x)) + return; +} + +static void _add(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = x + y; +} + +static void _sub(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = x - y; +} + +static void _mul(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = x * y; +} + +static void _div(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = (y == 0) ? 0 : x / y; +} + +static void _recip(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = (x == 0) ? 0 : 1.0 / x; +} + +static void _inc(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = x + 1; +} + +static void _dec(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = x - 1; +} + +static void _sign(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = (x > 0) ? 1 : ((x < 0) ? -1 : 0); +} + +static void _neg(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = -x; +} + +static void _sin(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = sin(x); +} + +static void _cos(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = cos(x); +} + +static void _tan(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = tan(x); +} + +static void _asin(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = (x < -1 || x > 1) ? 0 : asin(x); +} + +static void _acos(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = (x < -1 || x > 1) ? 0 : acos(x); +} + +static void _atan(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = atan(x); +} + +static void _sinh(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = sinh(x); +} + +static void _cosh(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = cosh(x); +} + +static void _tanh(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = tanh(x); +} + +static void _asinh(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = asinh(x); +} + +static void _acosh(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = (x < 1) ? 0 : acosh(x); +} + +static void _atanh(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = (x <= -1 || x >= 1) ? 0 : atanh(x); +} + +static void _atan2(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = atan2(x, y); +} + +static void _exp(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = exp(x); +} + +static void _pow(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = (x < 0 && fmod(y, 1.0) != 0.0) ? 0 : pow(x, y); +} + +static void _log(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = (x <= 0) ? 0 : log(x); +} + +static void _sqrt(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = (x < 0) ? 0 : sqrt(x); +} + +static void _abs(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = fabs(x); +} + +static void _ceil(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = ceil(x); +} + +static void _floor(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = floor(x); +} + +static void _erf(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = erf(x); +} + +static void _min(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = (x < y) ? x : y; +} + +static void _max(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = (x > y) ? x : y; +} + +static void _clamp(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 3) + return; + pushdown_value_t hi = stack_pop(output); + pushdown_value_t lo = stack_pop(output); + pushdown_value_t v = stack_pop(output); + output->data[output->size++] = (v < lo) ? lo : ((v > hi) ? hi : v); +} + +static void _roundd(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = round(x); +} + +static void _fract(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = x - floor(x); +} + +static void _mod(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = (y == 0) ? 0 : fmod(x, y); +} + +static void _log10_fn(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = (x <= 0) ? 0 : log10(x); +} + +static void _log2_fn(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = (x <= 0) ? 0 : log2(x); +} + +static void _signum(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = (x > 0) ? 1 : ((x < 0) ? -1 : 0); +} + +static void _swap(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = x; + output->data[output->size++] = y; +} + +static void _rot3(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 3) + return; + pushdown_value_t t1 = stack_pop(output); + pushdown_value_t t2 = stack_pop(output); + pushdown_value_t t3 = stack_pop(output); + output->data[output->size++] = t2; + output->data[output->size++] = t3; + output->data[output->size++] = t1; +} + +static void _depth(stack_t *output, stack_t *input) { + (void)input; + pushdown_value_t d = (pushdown_value_t)output->size; + output->data[output->size++] = d; +} + +static void _over(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = output->data[output->size - 2]; + if (!stack_push(output, x)) + return; +} + +static void _pick(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t n = stack_pop(output); + u32 idx = (u32)n; + if (idx >= output->size) { + output->data[output->size++] = n; + return; + } + pushdown_value_t x = output->data[output->size - 1 - idx]; + if (!stack_push(output, x)) + return; +} + +static void _drop2(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + output->size -= 2; +} + +static void _nip(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t top = stack_pop(output); + stack_pop(output); + output->data[output->size++] = top; +} + +static void _tuck(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t top = stack_pop(output); + pushdown_value_t second = output->data[output->size - 1]; + if (!stack_push(output, top)) + return; + output->data[output->size++] = second; + output->data[output->size++] = top; +} + +static void _equal(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = (x == y) ? 1 : 0; +} + +static void _less(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = (y < x) ? 1 : 0; +} + +static void _greater(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = (y > x) ? 1 : 0; +} + +static void _compare(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = (y > x) ? -1 : ((y < x) ? 1 : 0); +} + +static void _pi_const(stack_t *output, stack_t *input) { + (void)input; + if (!stack_push(output, 3.14159265358979323846)) + return; +} + +static void _e_const(stack_t *output, stack_t *input) { + (void)input; + if (!stack_push(output, 2.71828182845904523536)) + return; +} + +static void _rand(stack_t *output, stack_t *input) { + (void)input; + if (!stack_push(output, (pushdown_value_t)((f64)rand() / RAND_MAX))) + return; +} + +static void _square(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = x * x; +} + +static void _cube(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = x * x * x; +} + +static void _rsqrt(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = (x == 0) ? 0 : 1.0 / sqrt(x < 0 ? -x : x); +} + +static void _sort2(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + if (x < y) { + output->data[output->size++] = x; + output->data[output->size++] = y; + } else { + output->data[output->size++] = y; + output->data[output->size++] = x; + } +} + +static void _sort3(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 3) + return; + pushdown_value_t a = stack_pop(output); + pushdown_value_t b = stack_pop(output); + pushdown_value_t c = stack_pop(output); + pushdown_value_t s[3] = {a, b, c}; + for (u32 i = 0; i < 3; i++) + for (u32 j = i + 1; j < 3; j++) + if (s[j] < s[i]) { + pushdown_value_t tmp = s[i]; + s[i] = s[j]; + s[j] = tmp; + } + output->data[output->size++] = s[0]; + output->data[output->size++] = s[1]; + output->data[output->size++] = s[2]; +} + +static void _minmax(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 2) + return; + pushdown_value_t x = stack_pop(output); + pushdown_value_t y = stack_pop(output); + output->data[output->size++] = (x < y) ? x : y; + output->data[output->size++] = (x > y) ? x : y; +} + +static void _gamma(stack_t *output, stack_t *input) { + (void)input; + if (output->size < 1) + return; + pushdown_value_t x = stack_pop(output); + output->data[output->size++] = tgamma(x); +} + +static void (*OPERATIONS[])(stack_t *output, stack_t *input) = { + [NOOP] = _noop, + [PUSH] = _push, + [POP] = _pop, + [SKIP] = _skip, + [COPY] = _copy, + [ADD] = _add, + [SUB] = _sub, + [MUL] = _mul, + [DIV] = _div, + [RECIP] = _recip, + [INC] = _inc, + [DEC] = _dec, + [SIGN] = _sign, + [NEG] = _neg, + [SIN] = _sin, + [COS] = _cos, + [TAN] = _tan, + [ASIN] = _asin, + [ACOS] = _acos, + [ATAN] = _atan, + [ATAN2] = _atan2, + [SINH] = _sinh, + [COSH] = _cosh, + [TANH] = _tanh, + [ASINH] = _asinh, + [ACOSH] = _acosh, + [ATANH] = _atanh, + [EXP] = _exp, + [POW] = _pow, + [LOG] = _log, + [SQRT] = _sqrt, + [ABS] = _abs, + [CEIL] = _ceil, + [FLOOR] = _floor, + [ERF] = _erf, + [GAMMA] = _gamma, + [MIN] = _min, + [MAX] = _max, + [CLAMP] = _clamp, + [ROUNDD] = _roundd, + [FRACT] = _fract, + [MOD] = _mod, + [LOG10] = _log10_fn, + [LOG2] = _log2_fn, + [SIGNUM] = _signum, + [SWAP] = _swap, + [ROT3] = _rot3, + [DEPTH] = _depth, + [OVER] = _over, + [PICK] = _pick, + [DROP2] = _drop2, + [NIP] = _nip, + [TUCK] = _tuck, + [EQUAL] = _equal, + [LESS] = _less, + [GREATER] = _greater, + [COMPARE] = _compare, + [PI_CONST] = _pi_const, + [E_CONST] = _e_const, + [RAND] = _rand, + [SQUARE] = _square, + [CUBE] = _cube, + [RSQRT] = _rsqrt, + [SORT2] = _sort2, + [SORT3] = _sort3, + [MINMAX] = _minmax, +}; + +// pushdown_run() +// +// Execute a sequence of instructions until END. Instructions operate on +// the output stack, pulling values from the input stack via PUSH. + void pushdown_run(stack_t *output, stack_t *input, - pushdown_instruction_t *instructions) { + pushdown_instruction_t *instructions) { + if (!output || !input || !instructions) + return; + pushdown_instruction_t *op = instructions; + + while (*op != END) { + if (*op > MINMAX || *op < NOOP) + break; + OPERATIONS[*op](output, input); + op++; + } +} + +// pushdown_instruction_count() +// +// Count the number of instructions before END marker. +// +// return - Instruction count, or 0 if NULL or invalid + +u32 pushdown_instruction_count(pushdown_instruction_t *instructions) { + if (!instructions) + return 0; + u32 count = 0; + pushdown_instruction_t *op = instructions; + while (*op != END) { + if (*op > MINMAX || *op < NOOP) + return count; + count++; + op++; + } + return count; +} + +// pushdown_validate() +// +// Check that all instruction values in the sequence are valid enum members. +// +// return - 1 if valid, 0 if invalid + +int pushdown_validate(pushdown_instruction_t *instructions) { + if (!instructions) + return 0; pushdown_instruction_t *op = instructions; + while (*op != END) { + if (*op < NOOP || *op > MINMAX) + return 0; + op++; + } + return 1; +} - pushdown_value_t x, y; +// pushdown_print() +// +// Print the instruction sequence to stdout in readable format - while (*op) { +void pushdown_print(pushdown_instruction_t *instructions) { + if (!instructions) + return; + pushdown_instruction_t *op = instructions; + printf("["); + int first = 1; + while (*op != END) { + if (!first) printf(", "); switch (*op) { - case PUSH: - stack_push(output, stack_pop(input)); - break; - case POP: - stack_pop(output); - break; - case SKIP: - stack_pop(input); - break; - case COPY: - stack_push(output, stack_peek(output)); - break; - case ADD: - x = stack_pop(output); - y = stack_pop(output); - stack_push(output, x + y); - break; - case SUB: - x = stack_pop(output); - y = stack_pop(output); - stack_push(output, x - y); - break; - case MUL: - x = stack_pop(output); - y = stack_pop(output); - stack_push(output, x * y); - break; - case DIV: - x = stack_pop(output); - y = stack_pop(output); - stack_push(output, x / y); - break; - case SIN: - stack_push(output, sin(stack_pop(output))); - break; - case COS: - stack_push(output, cos(stack_pop(output))); - break; - case TAN: - stack_push(output, tan(stack_pop(output))); - break; - case ASIN: - stack_push(output, asin(stack_pop(output))); - break; - case ACOS: - stack_push(output, acos(stack_pop(output))); - break; - case ATAN: - stack_push(output, atan(stack_pop(output))); - break; - case SINH: - stack_push(output, sinh(stack_pop(output))); - break; - case COSH: - stack_push(output, cosh(stack_pop(output))); - break; - case TANH: - stack_push(output, tanh(stack_pop(output))); - break; - case ASINH: - stack_push(output, asinh(stack_pop(output))); - break; - case ACOSH: - stack_push(output, acosh(stack_pop(output))); - break; - case ATANH: - stack_push(output, atanh(stack_pop(output))); - break; - case EXP: - stack_push(output, exp(stack_pop(output))); - break; - case LOG: - stack_push(output, log(stack_pop(output))); - break; - case SQRT: - stack_push(output, sqrt(stack_pop(output))); - break; - case ABS: - stack_push(output, fabs(stack_pop(output))); - break; + case NOOP: printf("NOOP"); break; + case PUSH: printf("PUSH"); break; + case POP: printf("POP"); break; + case SKIP: printf("SKIP"); break; + case COPY: printf("COPY"); break; + case ADD: printf("ADD"); break; + case SUB: printf("SUB"); break; + case MUL: printf("MUL"); break; + case DIV: printf("DIV"); break; + case RECIP: printf("RECIP"); break; + case INC: printf("INC"); break; + case DEC: printf("DEC"); break; + case SIGN: printf("SIGN"); break; + case NEG: printf("NEG"); break; + case SIN: printf("SIN"); break; + case COS: printf("COS"); break; + case TAN: printf("TAN"); break; + case ASIN: printf("ASIN"); break; + case ACOS: printf("ACOS"); break; + case ATAN: printf("ATAN"); break; + case ATAN2: printf("ATAN2"); break; + case SINH: printf("SINH"); break; + case COSH: printf("COSH"); break; + case TANH: printf("TANH"); break; + case ASINH: printf("ASINH"); break; + case ACOSH: printf("ACOSH"); break; + case ATANH: printf("ATANH"); break; + case EXP: printf("EXP"); break; + case POW: printf("POW"); break; + case LOG: printf("LOG"); break; + case SQRT: printf("SQRT"); break; + case ABS: printf("ABS"); break; + case CEIL: printf("CEIL"); break; + case FLOOR: printf("FLOOR"); break; + case ERF: printf("ERF"); break; + case GAMMA: printf("GAMMA"); break; + case MIN: printf("MIN"); break; + case MAX: printf("MAX"); break; + case CLAMP: printf("CLAMP"); break; + case ROUNDD: printf("ROUNDD"); break; + case FRACT: printf("FRACT"); break; + case MOD: printf("MOD"); break; + case LOG10: printf("LOG10"); break; + case LOG2: printf("LOG2"); break; + case SIGNUM: printf("SIGNUM"); break; + case SWAP: printf("SWAP"); break; + case ROT3: printf("ROT3"); break; + case DEPTH: printf("DEPTH"); break; + case OVER: printf("OVER"); break; + case PICK: printf("PICK"); break; + case DROP2: printf("DROP2"); break; + case NIP: printf("NIP"); break; + case TUCK: printf("TUCK"); break; + case EQUAL: printf("EQUAL"); break; + case LESS: printf("LESS"); break; + case GREATER: printf("GREATER"); break; + case COMPARE: printf("COMPARE"); break; + case PI_CONST: printf("PI"); break; + case E_CONST: printf("E"); break; + case RAND: printf("RAND"); break; + case SQUARE: printf("SQUARE"); break; + case CUBE: printf("CUBE"); break; + case RSQRT: printf("RSQRT"); break; + case SORT2: printf("SORT2"); break; + case SORT3: printf("SORT3"); break; + case MINMAX: printf("MINMAX"); break; + default: printf("?"); break; } - + first = 0; op++; } + printf(", END]\n"); } -#endif
\ No newline at end of file +#endif /* PUSHDOWN_IMPLEMENTED */ +#endif /* PUSHDOWN_IMPLEMENTATION */
\ No newline at end of file diff --git a/include/stack.h b/include/stack.h index 7e0f711..659b013 100644 --- a/include/stack.h +++ b/include/stack.h @@ -1,84 +1,229 @@ +// stack.h — Generic dynamic stack +// +// Thread safety: Not thread-safe. External synchronization required. +// Memory safety: Double-free and use-after-free protected via NULL reset. +// Empty stack: pop/peek on empty stack returns zero-initialized value. +// Use stack_pop_ok / stack_peek_ok for error detection. + #ifndef STACK_H #define STACK_H -#include "./type.h" -#include <assert.h> -#include <stdint.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> +/* USER-DEFINED (define before including): + * typedef <type> stack_value_t; + */ + +#include "type.h" typedef struct stack { stack_value_t *data; - stack_value_t *head; - uint_t size; - uint_t capacity; + u64 size; + u64 capacity; } stack_t; void stack_init(stack_t *); -stack_t *stack_from_array(stack_value_t *, uint_t); -void stack_push(stack_t *, stack_value_t); +void stack_free(stack_t *); +void stack_from_array(stack_t *, stack_value_t *, u64); +int stack_push(stack_t *, stack_value_t); stack_value_t stack_pop(stack_t *); -stack_value_t stack_peek(stack_t *); +int stack_pop_ok(stack_t *, stack_value_t *); +stack_value_t stack_peek(const stack_t *); +int stack_peek_ok(const stack_t *, stack_value_t *); +int stack_empty(const stack_t *); +void stack_clear(stack_t *); #endif #ifdef STACK_IMPLEMENTATION +#ifndef STACK_IMPLEMENTED +#define STACK_IMPLEMENTED -const stack_value_t ZERO = 0; +#include <assert.h> +#include <stdlib.h> +#include <string.h> + +static stack_value_t const ZERO = {0}; /* Requires stack_value_t to be an aggregate type. For scalar types (double, int, pointer), {0} zero-initializes the entire value. For struct types, C99 guarantees remaining members are zero-initialized. */ + +// stack_init() +// +// Initialize or reset a stack. If stack->capacity is 0, defaults to 16. +// Frees any existing data buffer before allocating new one. void stack_init(stack_t *stack) { + if (!stack) + return; + if (stack->data != NULL) { + free(stack->data); + stack->data = NULL; + } if (stack->capacity == 0) { stack->capacity = 16; } - + if (stack->capacity > SIZE_MAX / sizeof(stack_value_t)) { + stack->capacity = 0; + stack->size = 0; + stack->data = NULL; + return; + } stack->size = 0; stack->data = calloc(stack->capacity, sizeof(stack_value_t)); - stack->head = stack->data; + if (!stack->data) + stack->capacity = 0; } -stack_t *stack_from_array(stack_value_t *array, uint_t size) { - stack_t *stack = calloc(1, sizeof(stack_t)); +// stack_from_array() +// +// Initialize a stack from an existing array. Allocates exact capacity. +void stack_from_array(stack_t *stack, stack_value_t *array, u64 size) { + if (!stack || !array || size == 0) + return; + if (size > SIZE_MAX / sizeof(stack_value_t)) + return; + if (stack->data) + free(stack->data); stack->size = size; stack->capacity = size; - stack->data = calloc(size, sizeof(stack_value_t)); + stack->data = calloc((size_t)size, sizeof(stack_value_t)); + if (!stack->data) { + stack->size = 0; + stack->capacity = 0; + stack->data = NULL; + return; + } memcpy(stack->data, array, sizeof(stack_value_t) * size); - stack->head = stack->data; - - return stack; } -void stack_push(stack_t *stack, stack_value_t x) { +// stack_push() +// +// Push a value onto the stack. Automatically doubles capacity if full. +// +// return - 1 on success, 0 on failure + +int stack_push(stack_t *stack, stack_value_t x) { + if (!stack || !stack->data) + return 0; if (stack->size == stack->capacity) { + if (stack->capacity > UINT64_MAX / 2) + return 0; stack->capacity *= 2; - stack->data = realloc(stack->data, sizeof(stack_value_t) * stack->capacity); - stack->head = &(stack->data[stack->size - 1]); + if (stack->capacity > SIZE_MAX / sizeof(stack_value_t)) { + stack->capacity /= 2; + return 0; + } + void *tmp = realloc(stack->data, sizeof(stack_value_t) * stack->capacity); + if (!tmp) { + stack->capacity /= 2; + return 0; + } + stack->data = tmp; } - *stack->head = x; - stack->head++; + stack->data[stack->size] = x; stack->size++; + return 1; } +// stack_pop() +// +// Remove and return the top element. Returns zero-initialized value on +// empty stack — use stack_pop_ok for error detection. + stack_value_t stack_pop(stack_t *stack) { - if (stack->size == 0) { + if (!stack || !stack->data || stack->size == 0) { return ZERO; } - stack_value_t x = stack->head[-1]; stack->size--; - stack->head--; + stack_value_t x = stack->data[stack->size]; + stack->data[stack->size] = ZERO; return x; } -stack_value_t stack_peek(stack_t *stack) { - if (stack->size == 0) { +// stack_pop_ok() +// +// Same as stack_pop, but writes result to *out and returns status code. +// +// return - 1 on success, 0 on empty stack or invalid args + +int stack_pop_ok(stack_t *stack, stack_value_t *out) { + if (!stack || !stack->data || !out || stack->size == 0) { + return 0; + } + + stack->size--; + *out = stack->data[stack->size]; + stack->data[stack->size] = ZERO; + + return 1; +} + +// stack_peek() +// +// Return the top element without removing it. Returns zero on empty stack +// — use stack_peek_ok for error detection. + +stack_value_t stack_peek(const stack_t *stack) { + if (!stack || !stack->data || stack->size == 0) { return ZERO; } - return stack->head[-1]; + return stack->data[stack->size - 1]; +} + +// stack_peek_ok() +// +// Same as stack_peek, but writes result to *out and returns status code. +// +// return - 1 on success, 0 on empty stack or invalid args + +int stack_peek_ok(const stack_t *stack, stack_value_t *out) { + if (!stack || !stack->data || !out || stack->size == 0) { + return 0; + } + + *out = stack->data[stack->size - 1]; + return 1; +} + +// stack_empty() +// +// Check if the stack is empty. +// +// return - 1 if empty, 0 otherwise + +int stack_empty(const stack_t *stack) { + if (!stack) + return 1; + return stack->size == 0; +} + +// stack_clear() +// +// Reset the stack to empty, zeroing all allocated slots + +void stack_clear(stack_t *stack) { + if (!stack || !stack->data) + return; + if (stack->capacity > SIZE_MAX / sizeof(stack_value_t)) + return; + for (u64 i = 0; i < stack->capacity; i++) + stack->data[i] = ZERO; + stack->size = 0; +} + +// stack_free() +// +// Release the stack's data buffer and reset all fields + +void stack_free(stack_t *stack) { + if (stack) { + free(stack->data); + stack->data = NULL; + stack->size = 0; + stack->capacity = 0; + } } -#endif
\ No newline at end of file +#endif /* STACK_IMPLEMENTED */ +#endif /* STACK_IMPLEMENTATION */
\ No newline at end of file diff --git a/include/test.h b/include/test.h new file mode 100644 index 0000000..9f40fd6 --- /dev/null +++ b/include/test.h @@ -0,0 +1,57 @@ +// test.h - Minimal test assertion macros +// +// Not a library for distribution. Intended for the test suite only. +// Provides ASSERT, ASSERT_FLOAT_EQ, and ASSERT_STR_EQ macros with +// failure tracking via a global test_failures counter. + +#ifndef TEST_H +#define TEST_H + +#include <stdio.h> +#include <string.h> +#include <math.h> + +#include "type.h" + +#ifndef TEST_EPS +#define TEST_EPS 1e-9 +#endif + +#ifndef TEST_FAILURES_VAR +#define TEST_FAILURES_VAR int test_failures = 0 +#endif + +#define ASSERT(cond, msg) \ + do { \ + if (!(cond)) { \ + fprintf(stderr, "FAIL: %s (%s:%d)\n", msg, __FILE__, __LINE__); \ + test_failures++; \ + } \ + } while (0) + +#define ASSERT_FLOAT_EQ(a, b, msg) \ + do { \ + f64 _a = (a); \ + f64 _b = (b); \ + if (fabs(_a - _b) > TEST_EPS) { \ + fprintf(stderr, "FAIL: %s (got %f, expected %f) (%s:%d)\n", \ + msg, (double)_a, (double)_b, __FILE__, __LINE__); \ + test_failures++; \ + } \ + } while (0) + +#define ASSERT_STR_EQ(a, b, msg) \ + do { \ + char const *_a = (a); \ + char const *_b = (b); \ + if (_a == NULL || _b == NULL || strcmp(_a, _b) != 0) { \ + fprintf(stderr, "FAIL: %s (got '%s', expected '%s') (%s:%d)\n", \ + msg, _a ? _a : "NULL", _b ? _b : "NULL", __FILE__, __LINE__); \ + test_failures++; \ + } \ + } while (0) + +#define TEST_PRINT_RESULTS(name) \ + printf("%s: %d failures\n", name, test_failures) + +#endif /* TEST_H */ diff --git a/include/type.h b/include/type.h index 56819c8..1106832 100644 --- a/include/type.h +++ b/include/type.h @@ -1,3 +1,8 @@ +// type.h - Common type aliases +// +// Used across header libraries to provide consistent, concise type names +// for fixed-width integers and floating point types. + #ifndef TYPE_H #define TYPE_H @@ -16,8 +21,4 @@ typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; -typedef uint64_t uint_t; -typedef int64_t int_t; -typedef double fp_t; - -#endif
\ No newline at end of file +#endif diff --git a/include/ufo.h b/include/ufo.h new file mode 100755 index 0000000..a92cff1 --- /dev/null +++ b/include/ufo.h @@ -0,0 +1,730 @@ +// https://www.sciencedirect.com/science/article/abs/pii/S1568494620303574 + +// ufo.h - Universal Function Originator +// +// Thread safety: Not thread-safe. External synchronization required. +// Memory: Single-allocation design — struct and all arrays stored in one +// contiguous buffer for easy persistence. Use ufo_copy for deep clone; +// ufo_free to release. Serialization via ufo_serialize / ufo_deserialize. + +// f_j(X) = f_j(a_0j (⊙_1j) a_1j*x_1^b_1j (⊙_2j) a_2j*x_2^b_2j (⊙_3j) ... (⊙_nj) +// a_nj*x_2^b_nj) g_j(X) = w_j * [f_j(X)]^(c_j) y = w_0 + g_1(X) ⊚_1 g_1(X) ⊚_2 +// ... ⊚_v g_v(X) + +#ifndef UFO_H +#define UFO_H + +#include "type.h" + +struct ufo_t; + +typedef struct ufo_t { + // Input count + u32 n; + // The number of internal blocks + u32 v; + // Internal weights [v][n+1] + f64 *a; + // Internal exponents [v][n] + f64 *b; + // External weights [v+1] + f64 *w; + // External exponents [v] + f64 *c; + // Unary functions [v] + f64 (**f)(f64); + // External binary functions [v] + f64 (**fe)(f64, f64); + // Internal binary functions [v][n] + f64 (**fi)(f64, f64); +} ufo_t; + +#define ufo_ajk(ufo, j, k) (*(ufo->a + (j) * (ufo->n + 1) + (k))) +#define ufo_bjk(ufo, j, k) (*(ufo->b + (j) * (ufo->n) + (k))) +#define ufo_fijk(ufo, j, k) (*(ufo->fi + (j) * (ufo->n) + (k))) + +ufo_t *ufo_init(u32 n, u32 v); +void ufo_free(ufo_t *ufo); +f64 ufo_evaluate(ufo_t *ufo, f64 *x); +void ufo_print(ufo_t *ufo); +ufo_t *ufo_copy(const ufo_t *src); +void ufo_randomize(ufo_t *ufo, f64 min_w, f64 max_w); +void ufo_mutate(ufo_t *ufo, f64 rate, f64 min_w, f64 max_w); +void ufo_crossover(ufo_t *parent1, ufo_t *parent2, u32 split); +u32 ufo_complexity(const ufo_t *ufo); +void ufo_set_unary(ufo_t *ufo, u32 j, f64 (*fn)(f64)); +void ufo_set_external_binary(ufo_t *ufo, u32 j, f64 (*fn)(f64, f64)); +void ufo_set_internal_binary(ufo_t *ufo, u32 j, u32 k, f64 (*fn)(f64, f64)); +void ufo_evaluate_jacobian(ufo_t *ufo, f64 *x, f64 *jacobian); +void ufo_evaluate_batch(ufo_t *ufo, f64 *x, u32 count, f64 *out); +void ufo_reset(ufo_t *ufo); +void ufo_simplify(ufo_t *ufo); +f64 ufo_similar(const ufo_t *a, const ufo_t *b); +void ufo_serialize(const ufo_t *ufo, u8 *buffer, u64 *size); +int ufo_deserialize(ufo_t **out, const u8 *buffer, u64 size); +u32 ufo_serialize_size(u32 n, u32 v); +void ufo_gradient_weights(ufo_t *ufo, f64 *x, f64 *weights_grad); +void ufo_to_formula_string(const ufo_t *ufo, char *buf, u32 buf_size); + +#endif // UFO_H + +#ifdef UFO_IMPLEMENTATION + +#include <assert.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <tgmath.h> + +static f64 ufo_identity(f64); +static f64 ufo_increment(f64); +static f64 ufo_decrement(f64); +static f64 ufo_reciprocal(f64); +static f64 ufo_root(f64); +static f64 ufo_absolute_value(f64); +static f64 ufo_floor(f64); +static f64 ufo_ceiling(f64); +static f64 ufo_round(f64); +static f64 ufo_exponent(f64); +static f64 ufo_log_natural(f64); +static f64 ufo_log_decimal(f64); +static f64 ufo_log_binary(f64); +static f64 ufo_sine(f64); +static f64 ufo_cosine(f64); +static f64 ufo_tangent(f64); + +static f64 ufo_addition(f64, f64); +static f64 ufo_subtraction(f64, f64); +static f64 ufo_division(f64, f64); +static f64 ufo_multiplication(f64, f64); +static f64 ufo_power(f64, f64); + +ufo_t *ufo_init(u32 n, u32 v) { + if (n == 0 || v == 0) + return NULL; + if (n > UINT32_MAX / 5) + return NULL; + { + u32 factor_a = 3 * n + 5; + if (factor_a < 3 * n) + return NULL; + if (v > UINT32_MAX / factor_a) + return NULL; + } + u32 N = 3 * v * n + 5 * v; + { + u32 factor_d = 2 * n + 3; + if (factor_d < 2 * n) + return NULL; + if (v > UINT32_MAX / factor_d) + return NULL; + } + u32 D = 2 * v * n + 3 * v; + + size_t bytes_a = sizeof(f64) * (size_t)N; + size_t bytes_d = sizeof(f64 (*)(f64)) * (size_t)D; + if (N > 0 && bytes_a / N != sizeof(f64)) + return NULL; + if (D > 0 && bytes_d / D != sizeof(f64 (*)(f64))) + return NULL; + if (bytes_a > SIZE_MAX - bytes_d) + return NULL; + size_t bytes = bytes_a + bytes_d; + + void *buffer = malloc(bytes); + if (!buffer) + return NULL; + + ufo_t *ufo = (ufo_t *)buffer; + ufo->n = n; + ufo->v = v; + + // Assign everything + ufo->a = (f64 *)(ufo + 1); + ufo->b = ufo->a + v * (n + 1); + ufo->w = ufo->b + v * n; + ufo->c = ufo->w + v + 1; + ufo->f = (f64(**)(f64))(ufo->c + v); + ufo->fe = (f64(**)(f64, f64))(ufo->f + v); + ufo->fi = (f64(**)(f64, f64))(ufo->fe + v * n); + + // Initialize all weights to one + f64 *tmp_fp = ufo->a; + while ((void *)tmp_fp != (void *)ufo->f) + *tmp_fp++ = 1.0; + + // Initialize all unary functions to identity + f64 (**tmp_unary)(f64) = ufo->f; + while ((void *)tmp_unary < (void *)ufo->fe) + *tmp_unary++ = ufo_identity; + + // Initialize all binary functions to addition + f64 (**tmp_binary)(f64, f64) = ufo->fe; + while ((u8 *)tmp_binary != (u8 *)buffer + bytes) + *tmp_binary++ = ufo_addition; + + // Set bias to zero + ufo->w[v] = 0; + + for (u32 j = 0; j < v; j++) + ufo_ajk(ufo, j, n) = 0; + + return ufo; +} + +void ufo_free(ufo_t *ufo) { + free(ufo); +} + +static f64 ufo_ujk(ufo_t *ufo, f64 *x, u32 j, u32 k) { + (void)k; + if (!ufo || !x) + return 0; + f64 acc = ufo_ajk(ufo, j, ufo->n); + for (u32 i = ufo->n; i > 0; i--) + acc = ufo_fijk(ufo, j, i - 1)(acc, x[i - 1]); + return acc; +} + +static f64 ufo_gj(ufo_t *ufo, f64 *x, u32 j) { + if (!ufo || !x) + return 0; + f64 base = ufo->f[j](ufo_ujk(ufo, x, j, 0)); + if (base < 0 && fmod(ufo->c[j], 1.0) != 0.0) + return 0; + if (base == 0.0 && ufo->c[j] <= 0.0) + return 0.0; + return ufo->w[j] * pow(base, ufo->c[j]); +} + +f64 ufo_evaluate(ufo_t *ufo, f64 *x) { + if (!ufo || !x) + return 0; + f64 y = 0; + + // Calculate g_j(X) for every j (excluding constant term) + u32 j; + for (j = 0; j < ufo->v; j++) + y = ufo->fe[j](y, ufo_gj(ufo, x, j)); + + // Constant term + y = ufo->fe[0](y, ufo->w[ufo->v]); + + return y; +} + +void ufo_print(ufo_t *ufo) { + if (!ufo) + return; + printf("UFO: %p\n" + "\n" + "N: %u\n" + "V: %u\n" + "A: %p\n" + "B: %p\n" + "W: %p\n" + "C: %p\n" + "F: %p\n" + "FE: %p\n" + "FI: %p\n", + (void *)ufo, (unsigned)ufo->n, (unsigned)ufo->v, + (void *)ufo->a, (void *)ufo->b, (void *)ufo->w, (void *)ufo->c, + (void *)ufo->f, (void *)ufo->fe, (void *)ufo->fi); +} + +static f64 ufo_identity(f64 x) { return x; } +static f64 ufo_increment(f64 x) { return x + 1; } +static f64 ufo_decrement(f64 x) { return x - 1; } +static f64 ufo_reciprocal(f64 x) { return (x == 0) ? 0 : 1 / x; } +static f64 ufo_root(f64 x) { return (x < 0) ? 0 : sqrt(x); } +static f64 ufo_absolute_value(f64 x) { return fabs(x); } +static f64 ufo_floor(f64 x) { return floor(x); } +static f64 ufo_ceiling(f64 x) { return ceil(x); } +static f64 ufo_round(f64 x) { return round(x); } +static f64 ufo_exponent(f64 x) { return exp(x); } +static f64 ufo_log_natural(f64 x) { return (x <= 0) ? 0 : log(x); } +static f64 ufo_log_decimal(f64 x) { return (x <= 0) ? 0 : log10(x); } +static f64 ufo_log_binary(f64 x) { return (x <= 0) ? 0 : log2(x); } +static f64 ufo_sine(f64 x) { return sin(x); } +static f64 ufo_cosine(f64 x) { return cos(x); } +static f64 ufo_tangent(f64 x) { return tan(x); } + +__attribute__((unused)) static f64 (*UNARY[])(f64) = { + ufo_identity, ufo_increment, ufo_decrement, ufo_reciprocal, + ufo_root, ufo_absolute_value, ufo_floor, ufo_ceiling, + ufo_round, ufo_exponent, ufo_log_natural, ufo_log_decimal, + ufo_log_binary, ufo_sine, ufo_cosine, + ufo_tangent +}; + +f64 ufo_addition(f64 x0, f64 x1) { return (x0 + x1); } +f64 ufo_subtraction(f64 x0, f64 x1) { return (x0 - x1); } +f64 ufo_division(f64 x0, f64 x1) { return (x1 == 0) ? 0 : (x0 / x1); } +f64 ufo_multiplication(f64 x0, f64 x1) { return (x0 * x1); } +f64 ufo_power(f64 x0, f64 x1) { return (x0 >= 0 || fmod(x1, 1.0) == 0.0) ? pow(x0, x1) : 0; } + +__attribute__((unused)) static f64 (*BINARY[])(f64, f64) = {ufo_addition, ufo_subtraction, ufo_division, + ufo_multiplication, ufo_power}; + +ufo_t *ufo_copy(const ufo_t *src) { + if (!src) + return NULL; + ufo_t *dst = ufo_init(src->n, src->v); + if (!dst) + return NULL; + memcpy(dst->a, src->a, sizeof(f64) * (src->v * (src->n + 1))); + memcpy(dst->b, src->b, sizeof(f64) * (src->v * src->n)); + memcpy(dst->w, src->w, sizeof(f64) * (src->v + 1)); + memcpy(dst->c, src->c, sizeof(f64) * src->v); + memcpy(dst->f, src->f, sizeof(f64 (*)(f64)) * src->v); + memcpy(dst->fe, src->fe, sizeof(f64 (*)(f64, f64)) * (src->v + src->v * src->n)); + return dst; +} + +void ufo_randomize(ufo_t *ufo, f64 min_w, f64 max_w) { + if (!ufo) + return; + f64 range = max_w - min_w; + for (u32 j = 0; j < ufo->v; j++) { + for (u32 k = 0; k < ufo->n + 1; k++) + ufo_ajk(ufo, j, k) = min_w + (f64)rand() / RAND_MAX * range; + for (u32 k = 0; k < ufo->n; k++) + ufo_bjk(ufo, j, k) = min_w + (f64)rand() / RAND_MAX * range; + ufo->w[j] = min_w + (f64)rand() / RAND_MAX * range; + ufo->c[j] = min_w + (f64)rand() / RAND_MAX * range; + ufo->f[j] = UNARY[(rand() % 16)]; + u32 bi_idx = (rand() % 5); + ufo->fe[j] = BINARY[bi_idx]; + for (u32 k = 0; k < ufo->n; k++) + ufo_fijk(ufo, j, k) = BINARY[(rand() % 5)]; + } + ufo->w[ufo->v] = min_w + (f64)rand() / RAND_MAX * range; +} + +void ufo_mutate(ufo_t *ufo, f64 rate, f64 min_w, f64 max_w) { + if (!ufo || rate <= 0.0) + return; + f64 range = max_w - min_w; + for (u32 j = 0; j < ufo->v; j++) { + for (u32 k = 0; k < ufo->n + 1; k++) + if ((f64)rand() / RAND_MAX < rate) + ufo_ajk(ufo, j, k) = min_w + (f64)rand() / RAND_MAX * range; + for (u32 k = 0; k < ufo->n; k++) + if ((f64)rand() / RAND_MAX < rate) + ufo_bjk(ufo, j, k) = min_w + (f64)rand() / RAND_MAX * range; + if ((f64)rand() / RAND_MAX < rate) + ufo->w[j] = min_w + (f64)rand() / RAND_MAX * range; + if ((f64)rand() / RAND_MAX < rate) + ufo->c[j] = min_w + (f64)rand() / RAND_MAX * range; + if ((f64)rand() / RAND_MAX < rate) + ufo->f[j] = UNARY[(rand() % 16)]; + if ((f64)rand() / RAND_MAX < rate) + ufo->fe[j] = BINARY[(rand() % 5)]; + for (u32 k = 0; k < ufo->n; k++) + if ((f64)rand() / RAND_MAX < rate) + ufo_fijk(ufo, j, k) = BINARY[(rand() % 5)]; + } + if ((f64)rand() / RAND_MAX < rate) + ufo->w[ufo->v] = min_w + (f64)rand() / RAND_MAX * range; +} + +void ufo_crossover(ufo_t *parent1, ufo_t *parent2, u32 split) { + if (!parent1 || !parent2 || parent1->n != parent2->n || parent1->v != parent2->v) + return; + if (split > 0 && split < parent1->v) { + u32 n = parent1->n; + for (u32 j = split; j < parent1->v; j++) { + u32 offset = j * (n + 1); + f64 tmp_a; + for (u32 k = 0; k < n + 1; k++) { + tmp_a = parent1->a[offset + k]; + parent1->a[offset + k] = parent2->a[offset + k]; + parent2->a[offset + k] = tmp_a; + } + { + u32 bob = j * n; + f64 tmp_b; + for (u32 k = 0; k < n; k++) { + tmp_b = parent1->b[bob + k]; + parent1->b[bob + k] = parent2->b[bob + k]; + parent2->b[bob + k] = tmp_b; + } + } + { + f64 tmp = parent1->w[j]; + parent1->w[j] = parent2->w[j]; + parent2->w[j] = tmp; + tmp = parent1->c[j]; + parent1->c[j] = parent2->c[j]; + parent2->c[j] = tmp; + f64 (*tmp_fn)(f64) = parent1->f[j]; + parent1->f[j] = parent2->f[j]; + parent2->f[j] = tmp_fn; + f64 (*tmp_fn2)(f64, f64) = parent1->fe[j]; + parent1->fe[j] = parent2->fe[j]; + parent2->fe[j] = tmp_fn2; + for (u32 k = 0; k < n; k++) { + u32 fi_off = j * n + k; + f64 (*tmp_fi)(f64, f64) = parent1->fi[fi_off]; + parent1->fi[fi_off] = parent2->fi[fi_off]; + parent2->fi[fi_off] = tmp_fi; + } + } + } + } +} + +u32 ufo_complexity(const ufo_t *ufo) { + if (!ufo) + return 0; + u32 score = 0; + for (u32 j = 0; j < ufo->v; j++) { + score++; + f64 c_val = ufo->c[j]; + if (c_val != 1.0 && c_val != 0.0) + score++; + f64 test = ufo->f[j](2.0); + if (test != 2.0) + score++; + for (u32 k = 0; k < ufo->n; k++) { + f64 b_val = ufo_bjk(ufo, j, k); + if (b_val != 1.0 && b_val != 0.0) + score++; + } + } + return score; +} + +void ufo_set_unary(ufo_t *ufo, u32 j, f64 (*fn)(f64)) { + if (!ufo || j >= ufo->v) + return; + ufo->f[j] = fn; +} + +void ufo_set_external_binary(ufo_t *ufo, u32 j, f64 (*fn)(f64, f64)) { + if (!ufo || j >= ufo->v) + return; + ufo->fe[j] = fn; +} + +void ufo_set_internal_binary(ufo_t *ufo, u32 j, u32 k, f64 (*fn)(f64, f64)) { + if (!ufo || j >= ufo->v || k >= ufo->n) + return; + ufo_fijk(ufo, j, k) = fn; +} + +void ufo_evaluate_jacobian(ufo_t *ufo, f64 *x, f64 *jacobian) { + if (!ufo || !x || !jacobian) + return; + f64 y0 = ufo_evaluate(ufo, x); + for (u32 i = 0; i < ufo->n; i++) + jacobian[i] = 0; + f64 eps = 1e-6; + f64 *xp = malloc(sizeof(f64) * ufo->n); + if (!xp) + return; + for (u32 i = 0; i < ufo->n; i++) { + memcpy(xp, x, sizeof(f64) * ufo->n); + xp[i] += eps; + f64 yp = ufo_evaluate(ufo, xp); + jacobian[i] = (yp - y0) / eps; + } + free(xp); +} + +void ufo_evaluate_batch(ufo_t *ufo, f64 *x, u32 count, f64 *out) { + if (!ufo || !x || !out || count == 0) + return; + for (u32 i = 0; i < count; i++) + out[i] = ufo_evaluate(ufo, x + (i64)i * (i64)ufo->n); +} + +void ufo_reset(ufo_t *ufo) { + if (!ufo) + return; + f64 *tmp_fp = ufo->a; + while ((void *)tmp_fp != (void *)ufo->f) + *tmp_fp++ = 1.0; + f64 (**tmp_unary)(f64) = ufo->f; + while ((void *)tmp_unary < (void *)ufo->fe) + *tmp_unary++ = ufo_identity; + f64 (**tmp_binary)(f64, f64) = ufo->fe; + u32 total_bin = ufo->v + ufo->v * ufo->n; + for (u32 i = 0; i < total_bin; i++) + *tmp_binary++ = ufo_addition; + ufo->w[ufo->v] = 0; + for (u32 j = 0; j < ufo->v; j++) + ufo_ajk(ufo, j, ufo->n) = 0; +} + +static int ufo_fn_index_unary(f64 (*fn)(f64)) { + for (int i = 0; i < 16; i++) + if (UNARY[i] == fn) + return i; + return -1; +} + +static int ufo_fn_index_binary(f64 (*fn)(f64, f64)) { + for (int i = 0; i < 5; i++) + if (BINARY[i] == fn) + return i; + return -1; +} + +void ufo_simplify(ufo_t *ufo) { + if (!ufo || ufo->v < 2) + return; + u32 write = 0; + for (u32 read = 0; read < ufo->v; read++) { + if (ufo->w[read] == 0.0 && ufo->c[read] == 0.0) + continue; + if (read != write) { + u32 n = ufo->n; + memcpy(ufo->a + write * (n + 1), ufo->a + read * (n + 1), sizeof(f64) * (n + 1)); + memcpy(ufo->b + write * n, ufo->b + read * n, sizeof(f64) * n); + ufo->w[write] = ufo->w[read]; + ufo->c[write] = ufo->c[read]; + ufo->f[write] = ufo->f[read]; + ufo->fe[write] = ufo->fe[read]; + { + size_t sz = sizeof(void *) * (size_t)n; + memcpy((void *)(ufo->fi + write * n), (void *)(ufo->fi + read * n), sz); + } + } + write++; + } + for (u32 j = write; j < ufo->v; j++) { + ufo->w[j] = 0; + ufo->c[j] = 0; + ufo->f[j] = ufo_identity; + ufo->fe[j] = ufo_addition; + for (u32 k = 0; k < ufo->n + 1; k++) + ufo_ajk(ufo, j, k) = 0; + for (u32 k = 0; k < ufo->n; k++) { + ufo_bjk(ufo, j, k) = 0; + ufo_fijk(ufo, j, k) = ufo_addition; + } + } +} + +f64 ufo_similar(const ufo_t *a, const ufo_t *b) { + if (!a || !b || a->n != b->n || a->v != b->v) + return 0; + u32 n = a->n; + u32 v = a->v; + f64 total = 0; + u32 count = 0; + for (u32 j = 0; j < v; j++) { + for (u32 k = 0; k < n + 1; k++) { + total += (a->a[j * (n + 1) + k] == b->a[j * (n + 1) + k]) ? 1 : 0; + count++; + } + for (u32 k = 0; k < n; k++) { + total += (a->b[j * n + k] == b->b[j * n + k]) ? 1 : 0; + count++; + } + total += (a->w[j] == b->w[j]) ? 1 : 0; + count++; + total += (a->c[j] == b->c[j]) ? 1 : 0; + count++; + total += (a->f[j] == b->f[j]) ? 1 : 0; + count++; + total += (a->fe[j] == b->fe[j]) ? 1 : 0; + count++; + for (u32 k = 0; k < n; k++) { + total += (a->fi[j * n + k] == b->fi[j * n + k]) ? 1 : 0; + count++; + } + } + total += (a->w[v] == b->w[v]) ? 1 : 0; + count++; + return count ? total / count : 1; +} + +u32 ufo_serialize_size(u32 n, u32 v) { + return sizeof(u32) * 2 + + sizeof(f64) * v * (n + 1) + + sizeof(f64) * v * n + + sizeof(f64) * (v + 1) + + sizeof(f64) * v + + sizeof(u8) * v + + sizeof(u8) * v + + sizeof(u8) * v * n; +} + +void ufo_serialize(const ufo_t *ufo, u8 *buffer, u64 *size) { + if (!ufo || !buffer || !size) + return; + u32 n = ufo->n; + u32 v = ufo->v; + *size = ufo_serialize_size(n, v); + u8 *p = buffer; + memcpy(p, &n, sizeof(u32)); + p += sizeof(u32); + memcpy(p, &v, sizeof(u32)); + p += sizeof(u32); + memcpy(p, ufo->a, sizeof(f64) * v * (n + 1)); + p += sizeof(f64) * v * (n + 1); + memcpy(p, ufo->b, sizeof(f64) * v * n); + p += sizeof(f64) * v * n; + memcpy(p, ufo->w, sizeof(f64) * (v + 1)); + p += sizeof(f64) * (v + 1); + memcpy(p, ufo->c, sizeof(f64) * v); + p += sizeof(f64) * v; + for (u32 j = 0; j < v; j++) { + p[0] = (u8)ufo_fn_index_unary(ufo->f[j]); + p++; + } + for (u32 j = 0; j < v; j++) { + p[0] = (u8)ufo_fn_index_binary(ufo->fe[j]); + p++; + } + for (u32 j = 0; j < v; j++) + for (u32 k = 0; k < n; k++) { + p[0] = (u8)ufo_fn_index_binary(ufo_fijk(ufo, j, k)); + p++; + } +} + +int ufo_deserialize(ufo_t **out, const u8 *buffer, u64 size) { + if (!out || !buffer) + return 0; + u64 min = sizeof(u32) * 2 + 1; + if (size < min) + return 0; + u32 n, v; + memcpy(&n, buffer, sizeof(u32)); + memcpy(&v, buffer + sizeof(u32), sizeof(u32)); + u64 needed = ufo_serialize_size(n, v); + if (size < needed) + return 0; + ufo_t *ufo = ufo_init(n, v); + if (!ufo) + return 0; + *out = ufo; + const u8 *p = buffer + sizeof(u32) * 2; + memcpy(ufo->a, p, sizeof(f64) * v * (n + 1)); + p += sizeof(f64) * v * (n + 1); + memcpy(ufo->b, p, sizeof(f64) * v * n); + p += sizeof(f64) * v * n; + memcpy(ufo->w, p, sizeof(f64) * (v + 1)); + p += sizeof(f64) * (v + 1); + memcpy(ufo->c, p, sizeof(f64) * v); + p += sizeof(f64) * v; + for (u32 j = 0; j < v; j++) { + int idx = (int)p[0]; + p++; + ufo->f[j] = (idx >= 0 && idx < 16) ? UNARY[(size_t)idx] : ufo_identity; + } + for (u32 j = 0; j < v; j++) { + int idx = (int)p[0]; + p++; + ufo->fe[j] = (idx >= 0 && idx < 5) ? BINARY[(size_t)idx] : ufo_addition; + } + for (u32 j = 0; j < v; j++) + for (u32 k = 0; k < n; k++) { + int idx = (int)p[0]; + p++; + ufo_fijk(ufo, j, k) = (idx >= 0 && idx < 5) ? BINARY[(size_t)idx] : ufo_addition; + } + return 1; +} + +void ufo_gradient_weights(ufo_t *ufo, f64 *x, f64 *weights_grad) { + if (!ufo || !x || !weights_grad) + return; + f64 y0 = ufo_evaluate(ufo, x); + f64 eps = 1e-6; + u32 n = ufo->n; + u32 v = ufo->v; + for (u32 j = 0; j < v; j++) + for (u32 k = 0; k < n + 1; k++) { + f64 orig = ufo_ajk(ufo, j, k); + ufo_ajk(ufo, j, k) = orig + eps; + weights_grad[j * (n + 1) + k] = (ufo_evaluate(ufo, x) - y0) / eps; + ufo_ajk(ufo, j, k) = orig; + } + for (u32 j = 0; j < v; j++) { + f64 orig = ufo->w[j]; + ufo->w[j] = orig + eps; + weights_grad[v * (n + 1) + j] = (ufo_evaluate(ufo, x) - y0) / eps; + ufo->w[j] = orig; + } + { + u32 off = v * (n + 1) + v; + f64 orig = ufo->w[v]; + ufo->w[v] = orig + eps; + weights_grad[off] = (ufo_evaluate(ufo, x) - y0) / eps; + ufo->w[v] = orig; + } + for (u32 j = 0; j < v; j++) { + u32 off = v * (n + 1) + v + 1 + j; + f64 orig = ufo->c[j]; + ufo->c[j] = orig + eps; + weights_grad[off] = (ufo_evaluate(ufo, x) - y0) / eps; + ufo->c[j] = orig; + } +} + +static void ufo_unary_name(char *buf, u32 sz, f64 (*fn)(f64)) { + int idx = ufo_fn_index_unary(fn); + if (idx < 0) { + snprintf(buf, sz, "<unknown>"); + return; + } + static const char *names[] = {"id", "inc", "dec", "recip", "root", "abs", + "floor", "ceil", "round", "exp", "log", "log10", + "log2", "sin", "cos", "tan"}; + snprintf(buf, sz, "%s", names[idx]); +} + +static void ufo_binary_name(char *buf, u32 sz, f64 (*fn)(f64, f64)) { + int idx = ufo_fn_index_binary(fn); + if (idx < 0) { + snprintf(buf, sz, "?"); + return; + } + static const char *names[] = {"+", "-", "/", "*", "^"}; + snprintf(buf, sz, "%s", names[idx]); +} + +void ufo_to_formula_string(const ufo_t *ufo, char *buf, u32 buf_size) { + if (!ufo || !buf || buf_size < 2) { + if (buf && buf_size >= 1) buf[0] = '\0'; + return; + } + u32 n = ufo->n; + u32 v = ufo->v; + u32 pos = 0; + buf[pos++] = '('; + for (u32 j = 0; j < v; j++) { + if (j > 0) { + char bn[8]; + ufo_binary_name(bn, sizeof(bn), ufo->fe[j]); + pos += (u32)snprintf(buf + pos, buf_size - pos, " %s ", bn); + if (pos >= buf_size - 1) break; + } + char un[16]; + ufo_unary_name(un, sizeof(un), ufo->f[j]); + pos += (u32)snprintf(buf + pos, buf_size - pos, "%s(", un); + if (pos >= buf_size - 1) break; + pos += (u32)snprintf(buf + pos, buf_size - pos, "%g", ufo_ajk(ufo, j, n)); + if (pos >= buf_size - 1) break; + for (u32 k = 0; k < n; k++) { + char bn[8]; + ufo_binary_name(bn, sizeof(bn), ufo_fijk(ufo, j, k)); + pos += (u32)snprintf(buf + pos, buf_size - pos, " %s ", bn); + if (pos >= buf_size - 1) break; + pos += (u32)snprintf(buf + pos, buf_size - pos, "(%g*x_%u)^%g", + ufo_ajk(ufo, j, k), (unsigned)k, ufo_bjk(ufo, j, k)); + if (pos >= buf_size - 1) break; + } + pos += (u32)snprintf(buf + pos, buf_size - pos, "))^%g", ufo->c[j]); + if (pos >= buf_size - 1) break; + } + if (pos < buf_size - 1) + pos += (u32)snprintf(buf + pos, buf_size - pos, ") + %g", ufo->w[v]); + buf[pos < buf_size ? pos : buf_size - 1] = '\0'; +} + +#endif // UFO_IMPLEMENTATION diff --git a/include/uri.h b/include/uri.h index a00400d..80df641 100755..100644 --- a/include/uri.h +++ b/include/uri.h @@ -14,12 +14,15 @@ // // Any string interacting with a uri_t is copied upon both entry and // exit, thus, all strings except those must be (de)allocated by the user. +// +// Thread safety: Not thread-safe. External synchronization required. +// Limitations: uri_parse only accepts absolute URIs with a scheme. Relative +// URIs (e.g., "/path/to/resource") will cause uri_parse to return NULL. #ifndef URI_H #define URI_H - typedef enum { BUILD, @@ -33,296 +36,420 @@ typedef enum URI_END } uri_element_t; +typedef struct uri_t +{ + char *data[URI_END]; +} uri_t; - -uri_t uri_init( void ); -void uri_set( uri_t *, uri_element_t, char const * ); -char * uri_get( uri_t * ); -uri_t * uri_parse( char const * ); -void uri_print( uri_t const * ); -void uri_build( uri_t * ); - +uri_t *uri_init(void); +void uri_free(uri_t *); +void uri_set(uri_t *, uri_element_t, char const *); +char *uri_get(uri_t *); +uri_t *uri_parse(char const *); +char *uri_remove(uri_t *, uri_element_t); +void uri_print(uri_t const *); +void uri_print_elements(uri_t const *); +void uri_build(uri_t *); #endif // URI_H #ifdef URI_IMPLEMENTATION - -typedef struct uri_t -{ - char *data[URI_END]; -} uri_t; - - #include <stdlib.h> #include <string.h> #include <stdio.h> +#include <stdint.h> +static void uri_copy_string(char **ptr, char const *source); -#define copy_string( ptr, source ) { \ - if( source ) \ - { \ - size_t n = strlen( source ); \ - ptr = malloc( n + 1 ); \ - ptr[n] = '\0'; \ - strcpy( ptr, source ); \ - } \ - else \ - { \ - ptr = NULL; \ - } \ +uri_t *uri_init(void) +{ + uri_t *u = calloc(1, sizeof(uri_t)); + if (!u) + return NULL; + return u; } - -void uri_set( uri_t *u, uri_element_t e, char const *data ) +void uri_free(uri_t *u) { - char *c; - copy_string( c, data ); - - if( u->data[e] ) - free( u->data[e] ); - - u->data[e] = c; + if (u == NULL) + return; + for(int i = 0; i < URI_END; i++) + { + if(u->data[i]) + free(u->data[i]); + } + free(u); } +static void uri_copy_string(char **ptr, char const *source) +{ + if (!ptr) + return; + if (*ptr) + free(*ptr); + if(source) { + size_t n = strlen(source); + if (n == SIZE_MAX) + return; + *ptr = malloc(n + 1); + if (!*ptr) + return; + memcpy(*ptr, source, n); + (*ptr)[n] = '\0'; + } + else { + *ptr = NULL; + } +} -char * uri_get( uri_t *u ) +void uri_set(uri_t *u, uri_element_t e, char const *data) { - uri_build( u ); - char *c; - copy_string( c, u->data[BUILD] ); + if (u == NULL) + return; + if ((int)e < 0 || (int)e >= URI_END) + return; + uri_copy_string(&u->data[e], data); +} +char *uri_get(uri_t *u) +{ + if (u == NULL) + return NULL; + uri_build(u); + char *c = NULL; + uri_copy_string(&c, u->data[BUILD]); return c; } - -char * uri_remove( uri_t *u, uri_element_t e ) +char *uri_remove(uri_t *u, uri_element_t e) { + if (u == NULL) + return NULL; + if ((int)e < 0 || (int)e >= URI_END) + return NULL; char *data = u->data[e]; - uri_set( u, e, NULL ); - + u->data[e] = NULL; return data; } -// TODO: Account for / when path is missing in query and fragment -void uri_build( uri_t *u ) +void uri_build(uri_t *u) { - int n = 0; + if (u == NULL) + return; + size_t n = 0; - // TODO: Convert to a for loop - if( u->data[BUILD] ) - free( u->data[BUILD] ); + if(u->data[BUILD]) + free(u->data[BUILD]); + u->data[BUILD] = NULL; // Length of built string - if( u->data[SCHEME] ) - n += strlen( u->data[SCHEME] ) + 1; // ":" - - if( u->data[USERINFO] ) - n += strlen( u->data[USERINFO] ) + 1; // "@" - - if( u->data[HOST] ) - n += strlen( u->data[HOST] ) + 2; // "//" - - if( u->data[PORT] ) - n += strlen( u->data[PORT] ) + 1; // ":" - - if( u->data[PATH] ) - n += strlen( u->data[PATH] ); - - if( u->data[QUERY] ) - n += strlen( u->data[QUERY] ) + 1; // ? - - if( u->data[FRAGMENT] ) - n += strlen( u->data[FRAGMENT] ) + 1; // # + { + size_t s; + if(u->data[SCHEME]) + { + s = strlen(u->data[SCHEME]) + 1; + if (n > SIZE_MAX - s) { u->data[BUILD] = NULL; return; } + n += s; + } + if(u->data[USERINFO]) + { + s = strlen(u->data[USERINFO]) + 1; + if (n > SIZE_MAX - s) { u->data[BUILD] = NULL; return; } + n += s; + } + if(u->data[HOST]) + { + s = strlen(u->data[HOST]) + 2; + if (n > SIZE_MAX - s) { u->data[BUILD] = NULL; return; } + n += s; + } + if(u->data[PORT]) + { + s = strlen(u->data[PORT]) + 1; + if (n > SIZE_MAX - s) { u->data[BUILD] = NULL; return; } + n += s; + } + if(u->data[PATH]) + { + s = strlen(u->data[PATH]); + if (n > SIZE_MAX - s) { u->data[BUILD] = NULL; return; } + n += s; + } + if(u->data[QUERY]) + { + s = strlen(u->data[QUERY]) + 1; + if (n > SIZE_MAX - s) { u->data[BUILD] = NULL; return; } + n += s; + } + if(u->data[FRAGMENT]) + { + s = strlen(u->data[FRAGMENT]) + 1; + if (n > SIZE_MAX - s) { u->data[BUILD] = NULL; return; } + n += s; + } + } - char *build = ( char * ) malloc( n + 1 ); - build[n] = '\0'; + if (n == SIZE_MAX) + return; + char *build = malloc(n + 1); + if (!build) + return; + build[0] = '\0'; + size_t pos = 0; // Copy strings to BUILD - strcpy( build, u->data[SCHEME] ); - strcat( build, ":" ); + if(u->data[SCHEME]) + { + size_t len = strlen(u->data[SCHEME]); + memcpy(build + pos, u->data[SCHEME], len); + pos += len; + build[pos++] = ':'; + } - if( u->data[HOST] ) + if(u->data[HOST]) { - strcat( build, "//" ); + memcpy(build + pos, "//", 2); + pos += 2; - if( u->data[USERINFO] ) + if(u->data[USERINFO]) { - strcat( build, u->data[USERINFO] ); - strcat( build, "@" ); + size_t len = strlen(u->data[USERINFO]); + memcpy(build + pos, u->data[USERINFO], len); + pos += len; + build[pos++] = '@'; } - strcat( build, u->data[HOST] ); + size_t len = strlen(u->data[HOST]); + memcpy(build + pos, u->data[HOST], len); + pos += len; - if( u->data[PORT] ) + if(u->data[PORT]) { - strcat( build, ":" ); - strcat( build, u->data[PORT] ); + build[pos++] = ':'; + len = strlen(u->data[PORT]); + memcpy(build + pos, u->data[PORT], len); + pos += len; } } - if( u->data[PATH] ) + if(u->data[PATH]) { - strcat( build, u->data[PATH] ); + size_t len = strlen(u->data[PATH]); + memcpy(build + pos, u->data[PATH], len); + pos += len; } - if( u->data[QUERY] ) + if(u->data[QUERY]) { - strcat( build, "?" ); - strcat( build, u->data[QUERY] ); + build[pos++] = '?'; + size_t len = strlen(u->data[QUERY]); + memcpy(build + pos, u->data[QUERY], len); + pos += len; } - if( u->data[FRAGMENT] ) + if(u->data[FRAGMENT]) { - strcat( build, "#" ); - strcat( build, u->data[FRAGMENT] ); + build[pos++] = '#'; + size_t len = strlen(u->data[FRAGMENT]); + memcpy(build + pos, u->data[FRAGMENT], len); + pos += len; } + build[pos] = '\0'; u->data[BUILD] = build; } - -char * copy_substring( char const *from, char const *to ) +static int uri_set_range(uri_t *u, uri_element_t e, char const *from, char const *to) { - char *s = ( char * ) malloc( to - from + 1 ); - s[to - from] = 0; - strncpy( s, from, to - from ); - - return s; -} + if (u == NULL || from == NULL || to == NULL) + return 0; + if ((int)e < 0 || (int)e >= URI_END) + return 0; + if (to <= from) + return 0; + size_t len = (size_t)(to - from); + if (len == SIZE_MAX) + return 0; + char *s = malloc(len + 1); + if (!s) + return 0; + s[len] = 0; + memcpy(s, from, len); + if(u->data[e]) + free(u->data[e]); + u->data[e] = s; + return 1; +} -uri_t * uri_parse( char const * uri_s ) +uri_t *uri_parse(char const *uri_s) { - uri_t *uri = ( uri_t * ) calloc( 1, sizeof( uri_t ) ); + if (uri_s == NULL) + return NULL; + uri_t *uri = calloc(1, sizeof(uri_t)); + if (!uri) + return NULL; char const *current = uri_s; char const *working; - char *token; // SCHEME - working = strchr( current, ( int ) ':' ); + working = strchr(current, ':'); - if( !working ) + if(!working) + { + uri_free(uri); return NULL; + } - token = copy_substring( current, working ); - uri_set( uri, SCHEME, token ); - current = ++working; + if (!uri_set_range(uri, SCHEME, current, working)) { + uri_free(uri); + return NULL; + } + current = ++working; - // AUTHORITY - if( ( *( working ) == '/' ) && ( *( working + 1 ) == '/' ) ) - { - current = working += 2; + // AUTHORITY + if(working[0] == '/' && working[1] == '/') + { + current = working += 2; - while( *working && *working != '@' && *working != ':' &&*working != '/' ) - working++; + char const *at = strchr(working, '@'); + if (at) { + if (!uri_set_range(uri, USERINFO, current, at)) { + uri_free(uri); + return NULL; + } + current = at + 1; - // USERINFO - if( *working == '@' ) - { - token = copy_substring( current, working ); - uri_set( uri, USERINFO, token ); + char const *host_end = strpbrk(current, ":/"); + if (!host_end) + host_end = current + strlen(current); - current = ++working; + if (!uri_set_range(uri, HOST, current, host_end)) { + uri_free(uri); + return NULL; + } + working = host_end; + } else { + while(*working && *working != ':' && *working != '/') + working++; - while( *working && *working != ':' && *working != '/' ) - working++; - } + if (!uri_set_range(uri, HOST, current, working)) { + uri_free(uri); + return NULL; + } + } - // HOST - token = copy_substring( current, working ); - uri_set( uri, HOST, token ); + if(!*working) + { + uri_build(uri); + return uri; + } - if( !( *working ) ) - return uri; + // PORT + if(*working == ':') + { + current = ++working; - // PORT - if( *working == ':' ) - { - current = ++working; + while(*working && *working != '/') + working++; - while( *working && *working != '/' ) - working++; + if (!uri_set_range(uri, PORT, current, working)) { + uri_free(uri); + return NULL; + } + } - token = copy_substring( current, working ); - uri_set( uri, PORT, token ); - } + if(!*working) + { + uri_build(uri); + return uri; + } + current = working; - if( !( *working ) ) - return uri; + while(*working && *working != '?' && *working != '#') + working++; + } + else + { + // No authority section - scan for query/fragment delimiters + while(*working && *working != '?' && *working != '#') + working++; + } - current = working; + // PATH + if (!uri_set_range(uri, PATH, current, working)) { + uri_free(uri); + return NULL; + } - while( *working && *working != '?' && *working != '#' ) - working++; - } - else - { - while( *working && *working != '/' ) - working++; - } + if(!*working) + { + uri_build(uri); + return uri; + } - // PATH - token = copy_substring( current, working ); - uri_set( uri, PATH, token ); + current = working; - if( !( *working ) ) - return uri; + // QUERY + if(*working == '?') + { + char const *query_start = ++working; - current = working; + while(*working && *working != '#') + working++; - // QUERY - if( *working == '?' ) - { - while( *working && *working != '#' ) - working++; + if (!uri_set_range(uri, QUERY, query_start, working)) { + uri_free(uri); + return NULL; + } - token = copy_substring( current, working ); - uri_set( uri, QUERY, token ); + current = working; + } - current = working; - } + // FRAGMENT + if(*working == '#') + { + char const *frag_start = ++working; - // FRAGMENT - if( *working == '#' ) - { - while( *working ) - working++; + while(*working) + working++; - token = copy_substring( current, working ); - uri_set( uri, FRAGMENT, token ); - } + if (!uri_set_range(uri, FRAGMENT, frag_start, working)) { + uri_free(uri); + return NULL; + } + } - uri_build( uri ); + uri_build(uri); - return uri; + return uri; } - -void uri_print( uri_t const *u ) +void uri_print(uri_t const *u) { - if( u->data[BUILD] ) - fputs( u->data[BUILD], stdout ); + if (u == NULL) + return; + if(u->data[BUILD]) + fputs(u->data[BUILD], stdout); } - -void uri_print_elements( uri_t const *u ) +void uri_print_elements(uri_t const *u) { - for( int i = 0; i < URI_END; i++ ) + if (u == NULL) + return; + for(int i = 0; i < URI_END; i++) { + printf("%d", i); - printf( "%d", i ); - - if( u->data[i] ) + if(u->data[i]) { - printf( " - %s", u->data[i] ); + printf(" - %s", u->data[i]); } putchar('\n'); - } } - #endif // URI_IMPLEMENTATION |