diff options
Diffstat (limited to 'include')
| -rwxr-xr-x | include/ann.h | 582 | ||||
| -rwxr-xr-x | include/bin.h | 299 | ||||
| -rw-r--r-- | include/direct.h | 121 | ||||
| -rwxr-xr-x | include/escape.h | 121 | ||||
| -rwxr-xr-x | include/flat.h | 120 | ||||
| -rwxr-xr-x | include/genetic.h | 146 | ||||
| -rwxr-xr-x | include/interpolate.h | 31 | ||||
| -rwxr-xr-x | include/pool.h | 124 | ||||
| -rw-r--r-- | include/pushdown.h | 137 | ||||
| -rw-r--r-- | include/stack.h | 84 | ||||
| -rw-r--r-- | include/type.h | 23 | ||||
| -rwxr-xr-x | include/uri.h | 328 |
12 files changed, 2116 insertions, 0 deletions
diff --git a/include/ann.h b/include/ann.h new file mode 100755 index 0000000..087daa5 --- /dev/null +++ b/include/ann.h @@ -0,0 +1,582 @@ +// ann.h - Artificial Neural Nework Libray + +#ifndef ANN_H +#define ANN_H + +#include <stdint.h> +#include "./type.h" + +#ifdef __cplusplus +extern "C" { +#endif + +typedef enum { + IDENTITY, + BINARY, + SIGMOID, + RELU, + ELU, + LRELU, + TANH, +} ann_activation_t; + +typedef struct { + // The full size of the allocated structure + uint_t n; + + // The number of layers in the neural network + uint_t layer_n; + + // The neuron count ( hidden ) + uint_t neuron_n; + + // The total number of weights and biases + uint_t weight_n; + + // The number of neurons in each layer + uint_t *layer_neuron_n; + + // The pointer to the neurons + fp_t *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; + + // The delta between between the actual and the cost function + fp_t *delta; + + // The activation function used in the hidden layer neurons + fp_t (*activation_hidden)(fp_t); + + // The partial derivative of the activation function used in the hidden + // layer neurons + fp_t (*activation_hidden_partial)(fp_t); + + // The activation function used in the ouput neurons + fp_t (*activation_output)(fp_t); + + // The partial derivative of the activation function used in the output + // layer neurons + fp_t (*activation_output_partial)(fp_t); +} ann_t; + +ann_t *ann_init(uint_t, uint_t *); +ann_t *ann_copy(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); + +fp_t ann_error_total(fp_t const *, fp_t const *, uint_t); +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); + +#ifdef __cplusplus +} +#endif + +#endif // ANN_H + +//////////////////////////////////////////////////////////////////////////////// +// IMPELEMENTATION SECTION +//////////////////////////////////////////////////////////////////////////////// + +#ifdef ANN_IMPLEMENTATION + +#include <assert.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <tgmath.h> + +#define PRINT_PRECISION 10 + +#define SQUARE_ROOT_2 1.4142135623730950488016887242096 +#define PI 3.1415926535897932384626433832795 +#define SQUARE_ROOT_PI 1.7724538509055160272981674833411 +#define SQUARE_ROOT_2_OVER_PI 0.7978845608028653558798921198687 + +#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 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 fp_t (*ACTIVATION[][2])(fp_t) = { + {ann_activation_identity, ann_activation_identity_partial}, // IDENTITY + {ann_activation_binary, ann_activation_binary_partial}, // BINARY + {ann_activation_sigmoid, ann_activation_sigmoid_partial}, // SIGMOID + {ann_activation_relu, ann_activation_relu_partial}, // RELU + {ann_activation_elu, ann_activation_elu_partial}, // ELU + {ann_activation_lrelu, ann_activation_lrelu_partial}, // LRELU + {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); + + uint_t neuron_n = 0; + uint_t weight_n = 0; + + // Calculate the number of neurons and weights / biases + uint_t l = 1; + for (; l < layer_n - 1; l++) { + neuron_n += layer_neuron_n[l]; + weight_n += layer_neuron_n[l] * (layer_neuron_n[l - 1] + 1); + } + + weight_n += layer_neuron_n[l] * (layer_neuron_n[l - 1] + 1); + + 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[] + + // Allocate everything as one structure + ann_t *ann = (ann_t *)malloc(n); + + // 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->weight = ann->neuron + ann->neuron_n; + ann->delta = ann->weight + ann->weight_n; + + ann_set_activation(ann, SIGMOID, SIGMOID); + + return ann; +} + +// ann_free() +// +// Free the neural network's memory +// +// ann - The instance of ann_t to free + +void ann_free(ann_t *ann) { free(ann); } + +// 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 + +ann_t *ann_copy(ann_t const *ann) { + ann_t *copy = (ann_t *)malloc(ann->n); + memcpy(copy, ann, ann->n); + + return copy; +} + +// 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 + + uint_t 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])); + y[j] = 0; + for (uint_t i = 0; i < ann->layer_neuron_n[l - 1]; i++) { + y[j] += x[i] * *w_ij++; + } + + y[j] += *w_ij++; + y[j] = ann->activation_hidden(y[j]); + } + + x = y; + 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])); + output[j] = 0; + + for (uint_t i = 0; i < ann->layer_neuron_n[l - 1]; i++) { + output[j] += x[i] * *w_ij++; + } + + output[j] += *w_ij++; + output[j] = ann->activation_output(output[j]); + } +} + +// 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; + + // First output layer delta + fp_t *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]); + } + + // 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]; + + fp_t *o_j = ann->neuron + ann->neuron_n; + fp_t *d_q; + + 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 (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]); + } + + 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; + 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; + + // Hidden training + for (; l < (int_t)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 fp_t ann_activation_binary(fp_t x) { + return (x > 0.0) ? 1.0 : (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 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 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) { + 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) { + return (x > 0.0) ? x : ELU_ALPHA * (expm1(x)); +} +static fp_t ann_activation_elu_partial(fp_t 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) { + return (x > 0.0) ? x : LRELU_ALPHA * x; +} +static fp_t ann_activation_lrelu_partial(fp_t 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); } + +// 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 + +fp_t ann_error(fp_t output, fp_t target) { + fp_t error = output - target; + error = 0.5 * error * error; + + 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 + +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]); + } + + return error; +} + +// 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_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 + +void ann_random(ann_t *ann) { + uint_t l, j, i; + fp_t *wb = ann->weight; + for (l = 1; l < ann->layer_n; l++) { + 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); + } + + *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); +} + +// 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) { + fputs("-> ", stderr); + for (uint_t 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++) { + 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++) { + 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++) { + fprintf(stderr, " %+.*f", PRINT_PRECISION, + *(weight + j + k * (ann->layer_neuron_n[i - 1] + 1))); + } + + fputs("\n", stderr); + } + + weight += ann->layer_neuron_n[i - 1] * ann->layer_neuron_n[i] + + ann->layer_neuron_n[i]; + + fputs("\n", stderr); + } +} + +#endif // ANN_IMPLEMENTATION
\ No newline at end of file diff --git a/include/bin.h b/include/bin.h new file mode 100755 index 0000000..d764f09 --- /dev/null +++ b/include/bin.h @@ -0,0 +1,299 @@ +// bin.h - flat file, fixed block size, time series database + +#ifndef BIN_H +#define BIN_H + +#include <stddef.h> +#include <stdint.h> +#include <stdio.h> + +#include "type.h" + +typedef struct { + uint_t length; + uint_t block_size; +} bin_meta_t; + +FILE *bin_init(char const *, uint_t); +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); + +uint_t bin_length(FILE *); +uint_t bin_block_size(FILE *); + +int_t bin_search(FILE *, bin_key_t); +uint_t bin_fuzzy_index(int_t); + +#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); + +#define index_bytes(i, bs) ((i * bs) + sizeof(bin_meta_t)) + +#define member_sizeof(type, member) (sizeof(((type *)0)->member)) + +// bin_init() +// +// Creates the desired binary file +// +// path - The path and file name for the desired file +// +// return - The newly created file + +FILE *bin_init(char const *path, uint_t block_size) { + FILE *f = fopen(path, "wb+"); + + if (!f) + return NULL; + + setvbuf(f, NULL, _IONBF, 0); + + bin_write_length(f, 0); + bin_write_block_size(f, block_size); + + return f; +} + +// bin_open() +// +// Opens the desired binary file +// +// path - The path and file name for the desired file +// +// return - The newly opened file + +FILE *bin_open(char const *path) { + FILE *f = fopen(path, "rb+"); + + if (!f) + return NULL; + + setvbuf(f, NULL, _IONBF, 0); + + return f; +} + +// bin_close() +// +// Closes the desired binary file +// +// f - The file descriptor to be closed + +void bin_close(FILE *f) { fclose(f); } + +// bin_read() +// +// Read the desired data into the buffer +// +// f - The file pointer +// i - The initial index of the read +// 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); + + assert(0 <= i && (i + n) <= bin_length(f)); + + fseek(f, index_bytes(i, bs), SEEK_SET); + fread(data, bs, n, f); +} + +// bin_write() +// +// Write the buffer into the file +// +// f - The file pointer +// i - The initial index of the write +// 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); + + assert(0 <= i && i <= l); + + fseek(f, index_bytes(i, bs), SEEK_SET); + fwrite(data, bs, n, f); + + if ((i + n) >= l) { + l += (i + n - l); + } + + bin_write_length(f, l); +} + +// bin_append() +// +// Appends the given data to the end of the binary file +// +// f - The file to be appended to +// 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); + + fseek(f, index_bytes(l, bs), SEEK_SET); + fwrite(data, bs, n, f); + + bin_write_length(f, l + n); +} + +// bin_insert() +// +// Inserts the given data into the binary file +// +// f - The file to be inserted into +// i - The initial index of the insertion +// 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); + + assert(0 <= i && i <= l); + + uint_t tmp_n = (l - i) * bs; + + uint8_t tmp[tmp_n]; + + fseek(f, index_bytes(i, bs), SEEK_SET); + fread(tmp, bs, l - i, f); + + fseek(f, index_bytes(i, bs), SEEK_SET); + fwrite(data, bs, n, f); + fwrite(tmp, 1, tmp_n, f); + + bin_write_length(f, l + n); +} + +// bin_length() +// +// Reads the block count number from the given file +// +// f - The file to be read from +// +// return - The length / number of entries in the file + +uint_t bin_length(FILE *f) { + uint_t n = 0; + + fseek(f, offsetof(bin_meta_t, length), SEEK_SET); + fread(&n, member_sizeof(bin_meta_t, length), 1, f); + + return n; +} + +// bin_block_size() +// +// Reads the block size from the given file +// +// f - The file to be read from +// +// return - The block size for the entries in the file + +uint_t bin_block_size(FILE *f) { + uint_t n = 0; + + fseek(f, offsetof(bin_meta_t, block_size), SEEK_SET); + fread(&n, member_sizeof(bin_meta_t, block_size), 1, f); + + return n; +} + +// bin_search() +// +// Search for a given key in the file +// +// f - The file to be searched within +// k - The key to search for +// +// return - The block_t index of the key. In the case that the key is not found, +// 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); + + int_t l = 0; + int_t r = bin_length(f) - 1; + int_t m; + + uint_t bs = bin_block_size(f); + + bin_key_t key; + + while (l <= r) { + m = (l + r) / 2; + fseek(f, index_bytes(m, bs), SEEK_SET); + fread(&key, sizeof(k), 1, f); + + if (key < k) + l = m + 1; + + else if (key > k) + r = m - 1; + + else + break; + } + + fseek(f, origin, SEEK_SET); + + if (key != k) + return -(l + 1); + + return m; +} + +// bin_fuzzy_index() +// +// If one does a binary search on the file and is returned a negative error, +// it may be useful to retrueve the index which it would be at. +// +// i - The number to map to the correct index +// +// 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; } + +// bin_write_length() +// +// Writes a length to the given file +// +// 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) { + fseek(f, offsetof(bin_meta_t, length), SEEK_SET); + fwrite(&length, member_sizeof(bin_meta_t, length), 1, f); +} + +// bin_write_block_size() +// +// Writes a block size to the given file +// +// 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) { + fseek(f, offsetof(bin_meta_t, block_size), SEEK_SET); + fwrite(&block_size, member_sizeof(bin_meta_t, block_size), 1, f); +} + +#endif diff --git a/include/direct.h b/include/direct.h new file mode 100644 index 0000000..c26907e --- /dev/null +++ b/include/direct.h @@ -0,0 +1,121 @@ +#ifndef DT_H +#define DT_H + +#include <stdbool.h> +#include <stdlib.h> +#include <stdio.h> + +struct value_t; + +typedef struct edge { + struct edge *next; + struct node *node; +} edge_t; + +typedef struct node { + struct edge *edge; + value_t x; + bool flag; + value_t (*function)(struct node *node); +} node_t; + +void dt_connect(node_t *, node_t *); +void dt_disconnect(node_t *, node_t *); +void dt_update(node_t *); + +value_t dt_one(node_t *node); +value_t dt_add(node_t *node); +value_t dt_subtract(node_t *node); + +#endif + +#ifdef DT_IMPLEMENTATION + +void dt_connect(node_t *to, node_t *from) { + edge_t *edge = malloc(sizeof(edge_t)); + edge->node = from; + edge->next = to->edge; + to->edge = edge; +} + +void dt_disconnect(node_t *to, node_t *from) { + edge_t *edge = to->edge; + edge_t *last = NULL; + + while (edge) { + if (edge->node == from) { + edge_t *tmp = edge; + last->next = edge->next; + free(tmp); + } + + last = edge; + edge = edge->next; + } +} + +void dt_update(node_t *origin) { + // printf(">: %p - %lf\n", origin, origin->x); + + edge_t *edge = origin->edge; + origin->flag = !origin->flag; + + while (edge) { + if (origin->flag != edge->node->flag) { + dt_update(edge->node); + } + + edge = edge->next; + } + + origin->x = origin->function(origin); + // printf("<: %p - %lf\n", origin, origin->x); +} + +void dt_update_trace(node_t *origin) { + printf(">: %p - %lf\n", origin, origin->x); + + edge_t *edge = origin->edge; + origin->flag = !origin->flag; + + while (edge) { + if (origin->flag != edge->node->flag) { + dt_update_trace(edge->node); + } + + edge = edge->next; + } + + origin->x = origin->function(origin); + printf("<: %p - %lf\n", origin, origin->x); +} + +value_t dt_one(node_t *node) { + return 1; +} + +value_t dt_add(node_t *node) { + edge_t *edge = node->edge; + value_t x = node->x; + + while(edge) { + x += edge->node->x; + edge = edge->next; + } + + return x; +} + +value_t dt_subtract(node_t *node) { + edge_t *edge = node->edge; + value_t x = node->x; + + while(edge) { + x -= edge->node->x; + edge = edge->next; + } + + return x; +} + +#endif diff --git a/include/escape.h b/include/escape.h new file mode 100755 index 0000000..13bd996 --- /dev/null +++ b/include/escape.h @@ -0,0 +1,121 @@ +// escape.h - ESC escape code macros and functions + +#ifndef ESCAPE_H +#define ESCAPE_H + + +#include <stdint.h> + + +#ifdef __cplusplus +extern "C" { +#endif + + +#define CSI "\x1B[" + + +#define ESC_CURSOR_UP( n ) CSI #n "A" +void esc_cursor_up( uint32_t n ); + +#define ESC_CURSOR_DOWN( n ) CSI #n "B" +void esc_cursor_down( uint32_t n ); + +#define ESC_CURSOR_LEFT( n ) CSI #n "C" +void esc_cursor_left( uint32_t n ); + +#define ESC_CURSOR_RIGHT( n ) CSI #n "D" +void esc_cursor_right( uint32_t n ); + +#define ESC_CURSOR_LINE_NEXT( n ) CSI #n "E" +void esc_cursor_line_next( uint32_t n ); + +#define ESC_CURSOR_POSITION( x, y ) CSI #y ";" #x "H" +void esc_cursor_position( uint32_t x, uint32_t y ); + +#define ESC_CLEAR_SCREEN CSI "2J" +void esc_clear_screen( void ); + +#define ESC_CLEAR_SCREEN_START CSI "1J" +void esc_clear_screen_start( void ); + +#define ESC_CLEAR_SCREEN_END CSI "0J" +void esc_clear_screen_end( void ); + +#define ESC_CLEAR_LINE CSI "2K" +void esc_clear_line( void ); + +#define ESC_CLEAR_LINE_START CSI "1L" +void esc_clear_line_start( void ); + +#define ESC_CLEAR_LINE_END CSI "0L" +void esc_clear_line_end( void ); + +#define ESC_SCROLL_UP( n ) CSI #n "S" +void esc_scroll_up( uint32_t n ); + +#define ESC_SCROLL_DOWN( n ) CSI #n "T" +void esc_scroll_down( uint32_t n ); + +#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_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_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_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_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 + + +#ifdef __cplusplus +} +#endif + +#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_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 ); } + +#endif // ESCAPE_IMPLEMENTATION
\ No newline at end of file diff --git a/include/flat.h b/include/flat.h new file mode 100755 index 0000000..17a1cc4 --- /dev/null +++ b/include/flat.h @@ -0,0 +1,120 @@ +// flat.h - Directory traversal utility functions + +#ifndef FLAT_H + +#include <stdint.h> +#include <sys/stat.h> + +char *flat_path(int, ...); +int64_t flat_directory_entry_count(char const *); +char **flat_directory_entries(char const *); + +#define MKDIR(x) (mkdir(x, 0777)) + +#endif // FLAT_H + +#ifdef FLAT_IMPLEMENTATION + +#include <stdarg.h> +#include <stdlib.h> +#include <string.h> + +#include <dirent.h> + +char *flat_path(int s_n, ...) { + va_list list; + size_t c_n = 0; + + 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); + } + + va_end(list); + + // Allocate return buffer. + char *r = malloc(c_n + 1); + 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--; + } + + va_end(list); + return r; +} + +int64_t flat_directory_entry_count(char const *path) { + DIR *dir; + struct dirent *ent; + + if (!(dir = opendir(path))) { + return 0; + } + int64_t n = 0; + + while ((ent = readdir(dir))) { + if (!strcmp(ent->d_name, ".")) + continue; + + if (!strcmp(ent->d_name, "..")) + continue; + + n++; + } + + closedir(dir); + + return n; +} + +char **flat_directory_entries(char const *path) { + int64_t n = flat_directory_entry_count(path); + char **entries = calloc(n + 1, sizeof(char **)); + + DIR *dir; + struct dirent *ent; + + int64_t i = 0; + int64_t entry_n = 0; + + if (!(dir = opendir(path))) { + return NULL; + } + while (i < n) { + ent = readdir(dir); + + if (!strcmp(ent->d_name, ".")) + continue; + + if (!strcmp(ent->d_name, "..")) + continue; + + entry_n = strlen(ent->d_name); + entries[i] = malloc(entry_n + 1); + strcpy(entries[i], ent->d_name); + + i++; + } + + closedir(dir); + + return entries; +} + +#endif // FLAT_IMPELEMTATION diff --git a/include/genetic.h b/include/genetic.h new file mode 100755 index 0000000..eadcab5 --- /dev/null +++ b/include/genetic.h @@ -0,0 +1,146 @@ +// genetic.h - A simple genetic algorithm implementation + +#ifndef GENETIC_H +#define GENETIC_H + +#include <assert.h> +#include <stdint.h> + +struct ga_individual_t; + +// 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 + +typedef void (*ga_crossover_t)(ga_individual_t *, ga_individual_t, + ga_individual_t); + +// ga_mutation_t +// +// Type definition for a crossover function +// +// uintptr_t - The individual being mutated + +typedef void (*ga_mutation_t)(ga_individual_t); + +// ga_fitness_t() +// +// Type definition for a fitness function +// +// 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 *); + +double ga_generation(ga_individual_t *, uint32_t, double, double, ga_fitness_t, + void const *, ga_crossover_t, ga_mutation_t); + +#endif // ga_H + +#ifdef GENETIC_IMPLEMENTATION // IMPLEMENTATION + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <tgmath.h> + +// ga_finess_sort() +// +// Run the fitness function on +// +// population - An array of pointers to each individual +// population_n - The size of the population array +// fitness - The function used to evaluate the fitness of an individual +// fitness_data - Additional data required for the fitness function +// +// 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; + + // 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--) { + } + + // 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]; + } + + population[j] = individual; + fitness_buffer[j] = fitness_current; + } + + // for (i = 0; i < population_n; i++) { + // printf("%u - %lf\n", i, fitness_buffer[i]); + // } + + double error = fitness_buffer[0]; + free(fitness_buffer); + + return error; +} + +// ga_generation() +// +// Run a single generation of the genetic algorithm +// +// population - An array of pointers to each individual +// population_n - The size of the population array +// rate_selection - A number [0,1] denoting the percentage of the population +// which survives to the next generation +// rate_mutation - A number [0,1] denoting the percentage of new individuals +// which will recieve mutations +// fitness - The function used to evaluate the fitness of an individual +// fitness_data - Additional data required for the fitness function +// crossover - The function used to perform repopulation via the +// combination of two parents +// mutation - The function used to perform mutations on a given individual +// +// 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); + + uint32_t selection_n = rate_selection * population_n; + + // 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; + + // 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]); + } + + // Fitness + return ga_fitness_sort(population, population_n, fitness, fitness_data); +} + +#endif diff --git a/include/interpolate.h b/include/interpolate.h new file mode 100755 index 0000000..1f79405 --- /dev/null +++ b/include/interpolate.h @@ -0,0 +1,31 @@ +// Math for Game Programmers: Fast and Funky 1D Nonlinear Transformations +// https://www.youtube.com/watch?v=mr5xkf6zSzk + +#ifndef 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 ) + +#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 ) ) ) ) + +#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 ) + +#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 ) ) + +#define flip( x ) ( 1 - x ) + +#endif
\ No newline at end of file diff --git a/include/pool.h b/include/pool.h new file mode 100755 index 0000000..d418142 --- /dev/null +++ b/include/pool.h @@ -0,0 +1,124 @@ +// pool.h - Fixed block size, free list based, memory pool + +#ifndef POOL_H +#define POOL_H + +#include <complex.h> +#include <setjmp.h> +#include <stdint.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 +} pool_t; + +pool_t *pool_init(uint32_t, uint32_t); +void pool_fini(pool_t *); +void *pool_malloc(pool_t *); +void pool_free(pool_t *, void *); + +#endif // POOL_H + +#define POOL_IMPLEMENTATION +#ifdef POOL_IMPLEMENTATION // IMPLEMENTATION + +#define POOL_MULTIPLIER_RESIZE 2 +#define POOL_BLOCK_N 10 + +#include <stdio.h> +#include <stdlib.h> + +static void pool_print(pool_t *pool); +static void pool_free_list(uintptr_t *, uint32_t, uint32_t); + +// pool_init() +// +// Initializes a memory pool and returns a pointer to the memory pool +// +// 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 = (pool_t *)malloc(sizeof(pool_t)); + + // Set size and count + pool->block_n = block_n; + pool->block_s = block_s; + + pool->data = calloc(block_n, block_s); + pool->free = pool->data; + + pool_free_list((uintptr_t *)pool->data, block_n, block_s); + + return pool; +} + +// pool_malloc() +// +// Return a block of free memory +// +// pool - A pointer to the pool object + +void *pool_malloc(pool_t *pool) { + uintptr_t *free = (uintptr_t *)pool->free; + + if (free) { + pool->free = (uintptr_t *)*free; + pool->block_i++; + } + + return free; +} + +// pool_free() +// +// Free the memory at the pointer p +// +// pool - A pointer to the pool object + +void pool_free(pool_t *pool, void *p) { + // Convert the pointer into a usable type + uintptr_t *free = (uintptr_t *)p; + + // Set the value at the address to the current front of the free list + *free = (uintptr_t)pool->free; + + // Set the pool's free head to the newly freed pointer + pool->free = (void *)free; + + pool->block_i--; +} + +uint32_t pool_capacity(pool_t *pool) { + return pool->block_n; +} + +uint32_t pool_size(pool_t *pool) { + 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, uint32_t block_n, + uint32_t block_s) { + uint8_t *ptr = (uint8_t *)block; + for (int i = 0; i < block_n - 1; i++) { + uintptr_t *tmp = (uintptr_t *)ptr; + *tmp = (uintptr_t)ptr + block_s; + ptr = ptr + block_s; + } + + *(uintptr_t *)ptr = (uintptr_t)0; +} + +#endif // POOL_IMPLEMENTATION diff --git a/include/pushdown.h b/include/pushdown.h new file mode 100644 index 0000000..aa7c308 --- /dev/null +++ b/include/pushdown.h @@ -0,0 +1,137 @@ +#ifndef PUSHDOWN_H +#define PUSHDOWN_H + +typedef pushdown_value_t stack_value_t; +#include "./stack.h" + +typedef enum { + END, + PUSH, + POP, + SKIP, + COPY, + ADD, + SUB, + MUL, + DIV, + SIN, + COS, + TAN, + ASIN, + ACOS, + ATAN, + SINH, + COSH, + TANH, + ASINH, + ACOSH, + ATANH, + EXP, + LOG, + SQRT, + ABS +} pushdown_instruction_t; + +void pushdown_run(stack_t *, stack_t *, pushdown_instruction_t *); + +#endif + +#ifdef PUSHDOWN_IMPLEMENTATION + +#include <tgmath.h> + +void pushdown_run(stack_t *output, stack_t *input, + pushdown_instruction_t *instructions) { + pushdown_instruction_t *op = instructions; + + pushdown_value_t x, y; + + while (*op) { + 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; + } + + op++; + } +} + +#endif
\ No newline at end of file diff --git a/include/stack.h b/include/stack.h new file mode 100644 index 0000000..7e0f711 --- /dev/null +++ b/include/stack.h @@ -0,0 +1,84 @@ +#ifndef STACK_H +#define STACK_H + +#include "./type.h" +#include <assert.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +typedef struct stack { + stack_value_t *data; + stack_value_t *head; + uint_t size; + uint_t 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); +stack_value_t stack_pop(stack_t *); +stack_value_t stack_peek(stack_t *); + +#endif + +#ifdef STACK_IMPLEMENTATION + +const stack_value_t ZERO = 0; + +void stack_init(stack_t *stack) { + if (stack->capacity == 0) { + stack->capacity = 16; + } + + stack->size = 0; + stack->data = calloc(stack->capacity, sizeof(stack_value_t)); + stack->head = stack->data; +} + +stack_t *stack_from_array(stack_value_t *array, uint_t size) { + stack_t *stack = calloc(1, sizeof(stack_t)); + + stack->size = size; + stack->capacity = size; + stack->data = calloc(size, sizeof(stack_value_t)); + 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) { + if (stack->size == stack->capacity) { + stack->capacity *= 2; + stack->data = realloc(stack->data, sizeof(stack_value_t) * stack->capacity); + stack->head = &(stack->data[stack->size - 1]); + } + + *stack->head = x; + stack->head++; + stack->size++; +} + +stack_value_t stack_pop(stack_t *stack) { + if (stack->size == 0) { + return ZERO; + } + + stack_value_t x = stack->head[-1]; + stack->size--; + stack->head--; + + return x; +} + +stack_value_t stack_peek(stack_t *stack) { + if (stack->size == 0) { + return ZERO; + } + + return stack->head[-1]; +} + +#endif
\ No newline at end of file diff --git a/include/type.h b/include/type.h new file mode 100644 index 0000000..56819c8 --- /dev/null +++ b/include/type.h @@ -0,0 +1,23 @@ +#ifndef TYPE_H +#define TYPE_H + +#include <stdint.h> + +typedef double f64; +typedef float f32; + +typedef int8_t i8; +typedef int16_t i16; +typedef int32_t i32; +typedef int64_t i64; + +typedef uint8_t u8; +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 diff --git a/include/uri.h b/include/uri.h new file mode 100755 index 0000000..a00400d --- /dev/null +++ b/include/uri.h @@ -0,0 +1,328 @@ +// uri.h - Minimal URI (de)serializer + +// Ethan Werner +// +// URI Parser and Serializer +// +// The uri_t structure is intended to be used as a black box. The primary use +// of the header as a whole is to enable the efficient creation of +// related URIs. +// +// Usage Notes +// The internally held strings should remain opaque and only interacted with +// through the given functions +// +// 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. + + +#ifndef URI_H +#define URI_H + + +typedef enum +{ + BUILD, + SCHEME, + USERINFO, + HOST, + PORT, + PATH, + QUERY, + FRAGMENT, + URI_END +} uri_element_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 * ); + + +#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> + + +#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; \ + } \ +} + + +void uri_set( uri_t *u, uri_element_t e, char const *data ) +{ + char *c; + copy_string( c, data ); + + if( u->data[e] ) + free( u->data[e] ); + + u->data[e] = c; +} + + +char * uri_get( uri_t *u ) +{ + uri_build( u ); + char *c; + copy_string( c, u->data[BUILD] ); + + return c; +} + + +char * uri_remove( uri_t *u, uri_element_t e ) +{ + char *data = u->data[e]; + uri_set( u, e, NULL ); + + return data; +} + +// TODO: Account for / when path is missing in query and fragment +void uri_build( uri_t *u ) +{ + int n = 0; + + // TODO: Convert to a for loop + if( u->data[BUILD] ) + free( u->data[BUILD] ); + + // 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; // # + + char *build = ( char * ) malloc( n + 1 ); + build[n] = '\0'; + + // Copy strings to BUILD + strcpy( build, u->data[SCHEME] ); + strcat( build, ":" ); + + if( u->data[HOST] ) + { + strcat( build, "//" ); + + if( u->data[USERINFO] ) + { + strcat( build, u->data[USERINFO] ); + strcat( build, "@" ); + } + + strcat( build, u->data[HOST] ); + + if( u->data[PORT] ) + { + strcat( build, ":" ); + strcat( build, u->data[PORT] ); + } + } + if( u->data[PATH] ) + { + strcat( build, u->data[PATH] ); + } + if( u->data[QUERY] ) + { + strcat( build, "?" ); + strcat( build, u->data[QUERY] ); + } + if( u->data[FRAGMENT] ) + { + strcat( build, "#" ); + strcat( build, u->data[FRAGMENT] ); + } + + u->data[BUILD] = build; +} + + +char * copy_substring( char const *from, char const *to ) +{ + char *s = ( char * ) malloc( to - from + 1 ); + s[to - from] = 0; + strncpy( s, from, to - from ); + + return s; +} + + + +uri_t * uri_parse( char const * uri_s ) +{ + uri_t *uri = ( uri_t * ) calloc( 1, sizeof( uri_t ) ); + + char const *current = uri_s; + char const *working; + char *token; + + // SCHEME + working = strchr( current, ( int ) ':' ); + + if( !working ) + return NULL; + + token = copy_substring( current, working ); + uri_set( uri, SCHEME, token ); + current = ++working; + + // AUTHORITY + if( ( *( working ) == '/' ) && ( *( working + 1 ) == '/' ) ) + { + current = working += 2; + + while( *working && *working != '@' && *working != ':' &&*working != '/' ) + working++; + + // USERINFO + if( *working == '@' ) + { + token = copy_substring( current, working ); + uri_set( uri, USERINFO, token ); + + current = ++working; + + while( *working && *working != ':' && *working != '/' ) + working++; + } + + // HOST + token = copy_substring( current, working ); + uri_set( uri, HOST, token ); + + if( !( *working ) ) + return uri; + + // PORT + if( *working == ':' ) + { + current = ++working; + + while( *working && *working != '/' ) + working++; + + token = copy_substring( current, working ); + uri_set( uri, PORT, token ); + } + + + if( !( *working ) ) + return uri; + + current = working; + + while( *working && *working != '?' && *working != '#' ) + working++; + } + else + { + while( *working && *working != '/' ) + working++; + } + + // PATH + token = copy_substring( current, working ); + uri_set( uri, PATH, token ); + + if( !( *working ) ) + return uri; + + current = working; + + // QUERY + if( *working == '?' ) + { + while( *working && *working != '#' ) + working++; + + token = copy_substring( current, working ); + uri_set( uri, QUERY, token ); + + current = working; + } + + // FRAGMENT + if( *working == '#' ) + { + while( *working ) + working++; + + token = copy_substring( current, working ); + uri_set( uri, FRAGMENT, token ); + } + + uri_build( uri ); + + return uri; +} + + +void uri_print( uri_t const *u ) +{ + if( u->data[BUILD] ) + fputs( u->data[BUILD], stdout ); +} + + +void uri_print_elements( uri_t const *u ) +{ + for( int i = 0; i < URI_END; i++ ) + { + + printf( "%d", i ); + + if( u->data[i] ) + { + printf( " - %s", u->data[i] ); + } + + putchar('\n'); + + } +} + + +#endif // URI_IMPLEMENTATION |