diff options
| -rwxr-xr-x | README.md | 86 | ||||
| -rwxr-xr-x | example/ann_xor.c | 48 | ||||
| -rwxr-xr-x | example/bin.c | 47 | ||||
| -rwxr-xr-x | example/build | 6 | ||||
| -rw-r--r-- | example/direct.c | 33 | ||||
| -rwxr-xr-x | example/escape.c | 62 | ||||
| -rwxr-xr-x | example/genetic_ann.c | 91 | ||||
| -rwxr-xr-x | example/genetic_char.c | 113 | ||||
| -rwxr-xr-x | example/pool.c | 7 | ||||
| -rw-r--r-- | example/pushdown.c | 22 | ||||
| -rw-r--r-- | example/stack.c | 20 | ||||
| -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 | ||||
| -rw-r--r-- | working/buffer.h | 67 | ||||
| -rwxr-xr-x | working/ufo.c | 15 | ||||
| -rwxr-xr-x | working/ufo.h | 217 |
26 files changed, 2950 insertions, 0 deletions
diff --git a/README.md b/README.md new file mode 100755 index 0000000..a3f2732 --- /dev/null +++ b/README.md @@ -0,0 +1,86 @@ +# C Header Libraries + +The following libraries are *highly* experimental and should be treated as such. The intent of this repository is archival in nature. While I do use many of the following libraries in my projects, they are not production ready. + +Please feel free to create issues, and pull requests are always welcome. + +## ann.h - Artifical Neural Network + +This library provides an implementation of a fully connected, artifical neural network with backpropagation. The entirety of the ANN is stored in a single memory allocation, allowing for ease in persisting models and training via external methods. + +### Activation Functions + +The activation function for hidden layers can be chosen independently from that used for the output layer. + +- Identity +- Binary +- Sigmoid +- RELU +- ELU +- LRELU +- Tanh + +## bin.h - Flat File Block Storage + +This library is an experiment in storing ordered numerical data as binary "flat files". The contained data must be of a fixed block size. The primary goal of the library is to provide a simple method of persisting and caching data that is time-series in nature. The resulting files should be short lived. + +### Format + +The file header contains two 64 bit unsigned integers, block count and block size. The rest of the file contains the block data. + +Each block must possess a numerical key/index as the first element. Prior to using the library, a ```typedef [numerical_type] bin_key_t``` must be declared in the implementation file. + +**Operations:** read, write, insert, append, search, and fuzzy search + +This is a naive library, and as such, does not provide input validation. If data is placed out of order, *there it will remain.* + +## escape.h - ANSI Escape Codes + +This library provides utility functions/macros for an assortment of ANSI escape codes. + +## flat.h - Directory Traversal + +This library provides a simple wrapper for traversing POSIX file systems. The intention for this library is to be used alongside bin.h, for the purpose of traversing hierarchial directory structures. + +## genetic.h - Genetic Algorithm + +An implementation of a genetic algorithm. The library exposes a single function for creating a new generation of individuals. The function is "generic", meaning that the respective operations for crossover, mutation, and fitness are passed as as function pointers. + +### Algorithm Overview + +**1. Crossover** + +- Determine the selection cutoff for the population. +- Replace all unfit individuals by preforming a crossover operation with two randomly selected fit indivuals. + +**2. Mutation** + +- Determine the number of mutation operations, and perform those on a randomly selected individual. + +**3. Fitness** + +- Sort the population by descending fitness, in preparation for the next generation. + +## pool.h - Memory Pool + +A free-list based memory pool. The pool has a fixed size after allocation. + +**Note:** The size of a block must be greater than or equal to ```sizeof(void *)``` + +## stack.h - Stack Implementation + +A stack implementation to be used with pushdown.h + +**Note:** A pop operation on an empty stack will return 0/NULL. + +## pushdown.h - A Pushdown/Stack Automata + +This file provides an implementation of a pushdown/stack automata. + +## ufo.h - Universal Functions Originator + + An implementation of the symbolic regression technique known as a Universal Functions Originator. The originating paper can be found [here](https://doi.org/10.1016/j.asoc.2020.106417). + +## uri.h - URI Builder + +A simple, and likely incomplete, implementation of a "builder" pattern to generate URIs as defined by [RFC 3986](https://datatracker.ietf.org/doc/html/rfc3986). The URIs are stored interally as separate blocks, enabling sequential URIs to be generated with ease. diff --git a/example/ann_xor.c b/example/ann_xor.c new file mode 100755 index 0000000..a39264c --- /dev/null +++ b/example/ann_xor.c @@ -0,0 +1,48 @@ +// example_xor.c - Example XOR training + +#define ANN_IMPLEMENTATION +#include "../include/ann.h" + +#include <stdio.h> +#include <stdlib.h> +#include <time.h> + +int main(void) { + srand(time(0)); + + ann_t *ann = ann_init(3, (uint_t[]){2, 2, 1}); + ann_set_activation(ann, SIGMOID, SIGMOID); + ann_random(ann); + + fp_t input[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}}; + fp_t output[4] = {0, 0, 0, 0}; + fp_t expected[4] = {0, 1, 1, 0}; + fp_t error = 0; + + for (int_t iteration = 0; iteration < 100000; iteration++) { + for (int_t training = 0; training < 4; training++) { + ann_propagation_forward(ann, (fp_t const *const)&input[training], + &output[training]); + + error += ann_error_total(&output[training], &expected[training], + ann->layer_neuron_n[ann->layer_n - 1]); + + // Train using backpropagation + ann_propagation_backward(ann, (fp_t const *const)&input[training], + &output[training], &expected[training], 0.4); + + // Train using numeric integration + // ann_train_numeric( ann, ( fp_t const * const ) &i[b], &t[b], 0.03 ); + } + } + + ann_print_weight(ann); + + fputs("------------------------------------------------------------\n\n", + stderr); + + for (int i = 0; i < 4; i++) { + ann_propagation_forward(ann, (fp_t const *const)&input[i], &output[i]); + ann_print_neuron(ann, (fp_t const *const)&input[i], &output[i]); + } +} diff --git a/example/bin.c b/example/bin.c new file mode 100755 index 0000000..40a7f77 --- /dev/null +++ b/example/bin.c @@ -0,0 +1,47 @@ +#include <stdint.h> +#include <stdio.h> + +typedef int32_t bin_key_t; + +#define TEST_LENGTH 10 +#define TEST_START -2 +#define TEST_STEP 0.5; + +struct sample_t { + bin_key_t time; + double data; +}; + +#define BIN_IMPLEMENTATION +#include "../include/bin.h" + +int main() { + char const *path = "./test.bin"; + FILE *bin = bin_init(path, sizeof(struct sample_t)); + + bin_key_t half = (bin_key_t)((TEST_START + TEST_LENGTH) / 2.0); + + // Insert half of the values using bin_insert() + for (bin_key_t i = half - 1; i >= TEST_START; i--) { + bin_insert(bin, 0, &(struct sample_t){.time = i, .data = 2.0 * i}, 1); + } + + // Append half of the values to the end + for (bin_key_t i = half; i < TEST_START + TEST_LENGTH; i++) { + bin_append(bin, &(struct sample_t){.time = i, .data = 2.0 * i}, 1); + } + + uint64_t l = bin_length(bin); + uint64_t bs = bin_block_size(bin); + + struct sample_t x[l]; + bin_read(bin, 0, x, l); + + // Test that all values are correct + for (int32_t i = 0; i < TEST_LENGTH; i++) { + bin_key_t key = TEST_START + i; + assert(x[i].time == key && x[i].data == 2.0 * key); + } + + bin_close(bin); +}
\ No newline at end of file diff --git a/example/build b/example/build new file mode 100755 index 0000000..b6c600f --- /dev/null +++ b/example/build @@ -0,0 +1,6 @@ +EXAMPLES=$(ls -1 --color=never *.c | sed 's/\.c//') + +for EXAMPLE in $EXAMPLES +do + gcc -g -fno-fast-math -O0 -o $EXAMPLE $EXAMPLE.c -lm +done diff --git a/example/direct.c b/example/direct.c new file mode 100644 index 0000000..102c0c3 --- /dev/null +++ b/example/direct.c @@ -0,0 +1,33 @@ +typedef double value_t; +#define DT_IMPLEMENTATION +#include "../include/direct.h" +#include <stdio.h> + +int main() { + node_t x0 = {.x = 0.0, .function = dt_add}; + node_t x1 = {.x = 0.0, .function = dt_one}; + node_t x2 = {.x = 0.0, .function = dt_add}; + node_t x3 = {.x = 0.0, .function = dt_add}; + node_t x4 = {.x = 0.0, .function = dt_add}; + node_t x5 = {.x = 0.0, .function = dt_add}; + node_t x6 = {.x = 0.0, .function = dt_one}; + + dt_connect(&x0, &x2); + dt_connect(&x0, &x1); + dt_connect(&x0, &x3); + dt_connect(&x2, &x1); + dt_connect(&x2, &x4); + dt_connect(&x3, &x4); + dt_connect(&x4, &x5); + dt_connect(&x4, &x6); + dt_connect(&x5, &x2); + + dt_update_trace(&x0); + printf("data: %lf\n", x0.x); + dt_update_trace(&x0); + printf("data: %lf\n", x0.x); + dt_update_trace(&x0); + printf("data: %lf\n", x0.x); + + return 0; +}
\ No newline at end of file diff --git a/example/escape.c b/example/escape.c new file mode 100755 index 0000000..c5e71ac --- /dev/null +++ b/example/escape.c @@ -0,0 +1,62 @@ +// escape.c - Simple test print code + + +#include <stdint.h> +#include <tgmath.h> + +#define ESCAPE_IMPLEMENTATION +#include "../include/escape.h" + +#define TEST_STRING "HELLO" + +void hsv_rgb( float h, float s, float v, uint8_t *r, uint8_t *g, uint8_t *b ) +{ + float h0 = h * 6.0; + + float k = fmod( 5.0 + h0, 6.0 ); + *r = 255 * ( v - v * s * fmax( 0.0, fmin( k, fmin( 4.0 - k, 1.0 ) ) ) ); + + k = fmod( 3.0 + h0, 6.0 ); + *g = 255 * ( v - v * s * fmax( 0.0, fmin( k, fmin( 4.0 - k, 1.0 ) ) ) ); + + k = fmod( 1.0 + h0, 6.0 ); + *b = 255 * ( v - v * s * fmax( 0.0, fmin( k, fmin( 4.0 - k, 1.0 ) ) ) ); +} + + +int main( void ) +{ + // Clear screen + fputs( ESC_CLEAR_SCREEN, stdout ); + + // Print a rectangle of Xs with positional coordinates + fputs( ESC_CURSOR_POSITION( 1, 1 ), stdout ); fflush( stdout ); + fputs( ESC_CURSOR_POSITION( 3, 2 ) "X", stdout ); fflush( stdout ); + fputs( ESC_CURSOR_POSITION( 10, 2 ) "X", stdout ); fflush( stdout ); + fputs( ESC_CURSOR_POSITION( 10, 4 ) "X", stdout ); fflush( stdout ); + fputs( ESC_CURSOR_POSITION( 3, 4 ) "X", stdout ); fflush( stdout ); + fputs( "\n", stdout ); + + fputs( "\n" ESC_RESET TEST_STRING "\n\n", stdout ); + fputs( ESC_BOLD TEST_STRING ESC_RESET "\n\n", stdout ); + fputs( ESC_OVERLINE TEST_STRING ESC_RESET "\n\n", stdout ); + fputs( ESC_UNDERLINE TEST_STRING ESC_RESET "\n\n", stdout ); + fputs( ESC_STRIKETHROUGH TEST_STRING ESC_RESET "\n\n", stdout ); + fputs( ESC_COLOR_FG_RGB( 0, 128, 128 ) TEST_STRING ESC_RESET "\n\n", stdout ); + fputs( ESC_COLOR_BG_RGB( 128, 0, 128 ) TEST_STRING ESC_RESET "\n\n", stdout ); + fputs( ESC_BLINK TEST_STRING ESC_RESET "\n\n", stdout ); + fputs( ESC_REVERSE TEST_STRING ESC_RESET "\n\n", stdout ); + fputs( ESC_CONCEAL TEST_STRING ESC_REVEAL TEST_STRING ESC_RESET "\n\n", stdout ); + + uint8_t r,g,b; + + for( float i = 0; i < 1; i += 0.01 ) + { + hsv_rgb( i, 1.0, 1.0, &r, &g, &b ); + + esc_color_fg_rgb( r, g, b ); + fputs( "█", stdout ); + } + + fputs( "\n", stdout ); +} diff --git a/example/genetic_ann.c b/example/genetic_ann.c new file mode 100755 index 0000000..071ccf5 --- /dev/null +++ b/example/genetic_ann.c @@ -0,0 +1,91 @@ +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <time.h> + +#define ANN_IMPLEMENTATION +#include "../include/ann.h" + +#define POPULATION_N 100 +#define RATE_SELECTION 0.2 +#define RATE_MUTATON 10 +#define MAGNITUDE_MUTATION 0.01 +#define ERROR 0.00001 + +typedef ann_t *ga_individual_t; + +#define GENETIC_IMPLEMENTATION +#include "../include/genetic.h" + +double fitness(ann_t *const x, void const *c) { + fp_t *i = *((fp_t **)c); + fp_t *t = *((fp_t **)c + 1); + fp_t o[4]; + + fp_t e = 0, sum = 0; + for (uint_t b = 0; b < 4; b++) { + ann_propagation_forward(x, &i[2 * b], &o[b]); + e = ann_error_total(&o[b], &t[b], x->layer_neuron_n[x->layer_n - 1]); + sum += e; + } + + return sum; +} + +void crossover(ann_t **y, ann_t *x0, ann_t *x1) { + uint32_t i_crossover = rand() % x0->weight_n; + memcpy((*y)->weight, x0->weight, i_crossover * sizeof(fp_t)); + memcpy((*y)->weight + i_crossover, x1->weight + i_crossover, + (x0->weight_n - i_crossover) * sizeof(fp_t)); +} + +void mutate(ann_t *x) { + uint32_t i_mutation = rand() % x->weight_n; + fp_t r = + (2 * (MAGNITUDE_MUTATION * (fp_t)rand() / RAND_MAX)) - MAGNITUDE_MUTATION; + x->weight[i_mutation] += r; +} + +int main(void) { + srand(time(0)); + + fp_t input[12] = {0, 0, 0, 1, 1, 0, 1, 1}; + fp_t output; + fp_t target[4] = {0, 1, 1, 0}; + + ann_t **networks = malloc(sizeof(ann_t *) * POPULATION_N); + + for (uint_t i = 0; i < POPULATION_N; i++) { + networks[i] = ann_init(3, (uint_t[]){2, 2, 1}); + ann_set_activation(networks[i], SIGMOID, IDENTITY); + ann_random(networks[i]); + } + + fp_t e = ERROR + 1; + uint32_t n = 0, i = 0; + while (e > ERROR) { + e = ga_generation(networks, POPULATION_N, RATE_SELECTION, RATE_MUTATON, + fitness, (fp_t *[2]){input, target}, crossover, mutate); + + n++; + i++; + + if (i > 1000) { + printf("\rERROR: %10.5lf", e); + i = 0; + } + } + + printf("\33[2K\r"); + printf("ERROR: %lf", e); + + for (int i = 0; i < 1; i++) { + for (int j = 0; j < 4; j++) { + ann_propagation_forward(networks[i], (fp_t const *const)&input[2 * j], + &output); + ann_print_neuron(networks[i], &input[2 * j], &output); + } + } + + printf("\nITERATIONS: %u\n", n); +} diff --git a/example/genetic_char.c b/example/genetic_char.c new file mode 100755 index 0000000..7dc24d4 --- /dev/null +++ b/example/genetic_char.c @@ -0,0 +1,113 @@ +// example_string.c - Example training of ann.h ANN, with genetic algorithm + +#include <stdint.h> +#include <stdio.h> +#include <string.h> +#include <time.h> + +typedef char *ga_individual_t; + +#define GENETIC_IMPLEMENTATION +#include "../include/genetic.h" + +#define POPULATION_N 100 +#define RATE_SELECTION 0.5 +#define RATE_MUTATON 2.0 +#define ERROR 0 + +#define TARGET_STRING \ + " !\"#$%&'()*+,-./" \ + "0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`" \ + "abcdefghijklmnopqrstuvwxyz{|}~" + +#define generate() ((char)(rand() % (127 - 32) + 32)) + +void crossover(char **y, char *x0, char *x1) { + uint32_t lx0 = strlen(x0); + uint32_t lx1 = strlen(x1); + + uint32_t ix0 = rand() % lx0; + uint32_t ix1 = rand() % lx1; + + uint32_t ly = ix0 + (lx1 - ix1); + + char *sy = malloc(ly + 1); + strncpy(sy, x0, ix0); + strncpy(sy + ix0, x1 + ix1, lx1 - ix1); + sy[ly] = 0; + + free(*y); + *y = sy; +} + +void mutation(char *x) { + uint32_t l = strlen(x); + uint32_t i = rand() % l; + + x[i] = generate(); +} + +double fitness(char *individual, void const *data) { + double error = 0; + + char const *target = (char const *)data; + + while (*individual && *target) { + error += abs(*target++ - *individual++); + } + while (*individual) { + error += *individual++; + } + while (*target) { + error += *target++; + } + + return error; +} + +int main(void) { + char const *target = TARGET_STRING; + char *population[POPULATION_N]; + + srand(time(0)); + + // Initialize poplation + for (uint64_t i = 0; i < POPULATION_N; i++) { + uint64_t n = rand() % 5 + 20; + char *str = malloc(n + 1); + str[n] = (uint8_t)0; + + for (uint64_t j = 0; j < n; j++) { + str[j] = generate(); + } + + population[i] = str; + } + + printf("TARGET: %s\n", TARGET_STRING); + fflush(stdout); + + time_t t0 = clock(); + + uint32_t n = 0; + + // Conduct opitmization + double error = 1; + while (error > ERROR) { + error = + ga_generation(population, POPULATION_N, RATE_SELECTION, RATE_MUTATON, + fitness, (void const *)target, crossover, mutation); + + n++; + } + + time_t t1 = clock(); + + printf("\nSOLUTION: %s", population[0]); + printf("\nITERATIONS: %d\nTIME: %f ms\n", n, + 1000.0 * (t1 - t0) / CLOCKS_PER_SEC); + + for (int i = 0; i < POPULATION_N; i++) { + free(population[i]); + } +} diff --git a/example/pool.c b/example/pool.c new file mode 100755 index 0000000..8b1fafd --- /dev/null +++ b/example/pool.c @@ -0,0 +1,7 @@ +#define POOL_IMPLEMENTATION +#include "../include/pool.h" + +int main() { + pool_t*p = pool_init(10, 100); + pool_print(p); +}
\ No newline at end of file diff --git a/example/pushdown.c b/example/pushdown.c new file mode 100644 index 0000000..ada8d73 --- /dev/null +++ b/example/pushdown.c @@ -0,0 +1,22 @@ +typedef double pushdown_value_t; +#define STACK_IMPLEMENTATION +#define PUSHDOWN_IMPLEMENTATION +#include "../include/pushdown.h" + +int main() { + pushdown_instruction_t instructions[] = {PUSH, COPY, MUL, END}; + + stack_t input = {}; + stack_t output = {}; + + stack_init(&input); + stack_init(&output); + + stack_push(&input, 4.0); + + pushdown_run(&output, &input, instructions); + + while (output.size) { + printf("%lf\n", stack_pop(&output)); + } +}
\ No newline at end of file diff --git a/example/stack.c b/example/stack.c new file mode 100644 index 0000000..93128f4 --- /dev/null +++ b/example/stack.c @@ -0,0 +1,20 @@ +typedef double stack_value_t; + +#define STACK_IMPLEMENTATION +#include "../include/stack.h" + +void main() { + stack_t stack = { .capacity = 10 }; + stack_init(&stack); + + for(int i = 0; i < 15; i++) { + stack_push(&stack, (stack_value_t) i); + } + + printf("%lf\n", stack_peek(&stack)); + printf("%lf\n", stack_pop(&stack)); + + for(int i = 0; i < 15; i++) { + printf("%lf\n", stack_pop(&stack)); + } +}
\ No newline at end of file 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 diff --git a/working/buffer.h b/working/buffer.h new file mode 100644 index 0000000..629821f --- /dev/null +++ b/working/buffer.h @@ -0,0 +1,67 @@ +#ifndef BUFFER_H +#define BUFFER_H + +#include "./type.h" + +void *buffer_malloc(uint_t num, uint_t size); +void buffer_free(void *); +void buffer_insert(void *); +void buffer_remove(void *); + +#endif + +#ifdef BUFFER_IMPLEMENTATION + +#define _buffer_from_meta(x) ((void *)((u8 *)x) + sizeof(buffer_meta_t)) +#define _buffer_to_meta(x) ((void *)((u8 *)x) + sizeof(buffer_meta_t)) + +struct { + uint_t i; // Array size + uint_t n; // Array capacity + uint_t s; // Element size +} buffer_meta_t; + +void *buffer_malloc(uint_t n, uint_t s) { + void *x = malloc((n * s) + sizeof(uint_t) * 3); + buffer_meta_t *meta = (buffer_meta_t *)x; + + meta->i = 0; + meta->n = n; + meta->s = s; + + void *buffer = _buffer_from_meta(x); + + return buffer; +} + +void buffer_free(void *buffer) { free(_buffer_to_meta(buffer)); } + +uint_t buffer_size(void *buffer) { + buffer_meta_t *meta = _buffer_to_meta(buffer); + return meta->i; +} + +uint_t buffer_capacity(void *buffer) { + buffer_meta_t *meta = _buffer_to_meta(buffer); + return meta->n; +} + +void *buffer_resize(void *buffer) { + buffer_meta_t *meta = _buffer_to_meta(buffer); + + if (meta->n > 32) { + fp_t ratio = (fp_t)meta->i / (fp_t)meta->n; + + if (ratio > 0.8) { + meta->n *= 2; + meta = realloc(meta, sizeof(buffer_meta_t) + meta->n * meta->s) + } else if (ratio < 0.2) { + meta->n /= 2; + meta = realloc(meta, sizeof(buffer_meta_t) + meta->n * meta->s) + } + } + + return meta; +} + +#endif
\ No newline at end of file diff --git a/working/ufo.c b/working/ufo.c new file mode 100755 index 0000000..b404f80 --- /dev/null +++ b/working/ufo.c @@ -0,0 +1,15 @@ +#define UFO_IMPLEMENTATION +#include "ufo.h" + + +#include <stdio.h> + + +int main() { + ufo_t *ufo = ufo_init( 1, 100 ); + printf( "%f\n", ufo_evaluate( ufo, (fp_t[]){ 1.0 } ) ); + free( ufo ); + + return 0; +} + diff --git a/working/ufo.h b/working/ufo.h new file mode 100755 index 0000000..2ae33ae --- /dev/null +++ b/working/ufo.h @@ -0,0 +1,217 @@ +// https://www.sciencedirect.com/science/article/abs/pii/S1568494620303574 + +// ufo.h - Universal Function Originator + +// 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 + +#include <stdint.h> +#include <stdlib.h> + +typedef double fp_t; + +struct ufo_t; + +#endif // UFO_H + +#ifdef UFO_IMPLEMENTATION + +#include <assert.h> +#include <stdio.h> +#include <tgmath.h> + +typedef struct ufo_t { + // Input count + uint32_t n; + // The number of internal blocks + uint32_t v; + // Internal weights [v][n+1] + fp_t *a; + // Internal exponents [v][n] + fp_t *b; + // External weights [v+1] + fp_t *w; + // External exponents [v] + fp_t *c; + // Unary functions [v] + fp_t (**f)(fp_t); + // External binary functions [v] + fp_t (**fe)(fp_t, fp_t); + // Internal binary functions [v][n] + fp_t (**fi)(fp_t, fp_t); +} 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(uint32_t n, uint32_t v) { + assert(n > 0); + assert(v > 0); + + fp_t N = 3 * v * n + 5 * v; + fp_t D = 2 * v * n + 3 * v; + uint32_t bytes = + sizeof(ufo_t) + sizeof(fp_t) * N + sizeof(void (*)(void)) * D; + + ufo_t *ufo = malloc(bytes); + ufo->n = n; + ufo->v = v; + + ufo->a = (void *)((uint8_t *)ufo + sizeof(ufo_t)); + ufo->b = ufo->a + v * (n + 1); + ufo->w = ufo->b + v * n; + ufo->c = ufo->w + v + 1; + ufo->f = (fp_t(**)(fp_t))(ufo->c + v); + ufo->fe = (fp_t(**)(fp_t, fp_t))(ufo->f + v); + ufo->fi = (fp_t(**)(fp_t, fp_t))(ufo->fe + v * n); + + // Initialize all weights to one + fp_t *tmp_fp = ufo->a; + while ((void *)tmp_fp != (void *)ufo->f) + *tmp_fp++ = 1.0; + + // Initialize all unary functions to identity + fp_t (**tmp_unary)(fp_t) = ufo->f; + while ((void *)tmp_unary < (void *)ufo->fe) + *tmp_unary++ = ufo_identity; + + // Initialize all binary functions to addition + fp_t (**tmp_binary)(fp_t, fp_t) = ufo->fe; + while ((void *)tmp_binary != (void *)ufo + bytes) + *tmp_binary++ = ufo_addition; + + // Set bias to zero + ufo->w[v] = 0; + + for (uint32_t j = 0; j < v; j++) + ufo_ajk(ufo, j, ufo->n) = 0; + + return ufo; +} + +fp_t ufo_ujk(ufo_t *ufo, fp_t *x, uint32_t j, uint32_t k) { + if (k >= ufo->n) + return ufo_ajk(ufo, j, k); + + return ufo_fijk(ufo, j, k)(ufo_ujk(ufo, x, j, k + 1), x[k]); +} + +fp_t ufo_gj(ufo_t *ufo, fp_t *x, uint32_t j) { + return ufo->w[j] * pow(ufo->f[j](ufo_ujk(ufo, x, j, 0)), ufo->c[j]); +} + +fp_t ufo_evaluate(ufo_t *ufo, fp_t *x) { + fp_t y = 0; + + // Calculate g_j(X) for every j (excluding constant term) + uint32_t j; + for (j = 0; j < ufo->v; j++) + y = ufo->fe[j](y, ufo_gj(ufo, x, j)); + + // Constant term + y = ufo->fe[j](y, ufo->w[j]); + + return y; +} + +void ufo_print(ufo_t *ufo) { + 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, ufo->n, ufo->v, ufo->a, ufo->b, ufo->w, ufo->c, + (void *)ufo->f, (void *)ufo->fe, (void *)ufo->fi); +} + +fp_t ufo_identity(fp_t x) { return x; } +fp_t ufo_increment(fp_t x) { return x + 1; } +fp_t ufo_increment(fp_t x) { return x - 1; } +fp_t ufo_reciporical(fp_t x) { return 1 / x; } +fp_t ufo_root(fp_t x) { return sqrt(x); } +fp_t ufo_absolute_value(fp_t x) { return fabs(x); } +fp_t ufo_floor(fp_t x) { return floor(x); } +fp_t ufo_ceiling(fp_t x) { return ceiling(x); } +fp_t ufo_round(fp_t x) { return round(x); } +fp_t ufo_exponent(fp_t x) { return exp(x); } +fp_t ufo_log_natural(fp_t x) { return log(x); } +fp_t ufo_log_decimal(fp_t x) { return log10(x); } +fp_t ufo_log_binary(fp_t x) { return log2(x); } +fp_t ufo_sine(fp_t x) { return sin(x); } +fp_t ufo_cosine(fp_t x) { return cos(x); } +fp_t ufo_tangent(fp_t x) { return tan(x); } + +fp_t (*UNARY[])(fp_t) = { + ufo_identity, ufo_increment, ufo_decrement, ufo_reciporical, + 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, + // ufo_cosecant, + // ufo_secant, + // ufo_cotangent, + // ufo_sine_hyperbolic, + // ufo_cosine_hyperbolic, + // ufo_tangent_hyperbolic, + // ufo_cosecant_hyperbolic, + // ufo_secant_hyperbolic, + // ufo_cotangent_hyperbolic, + // ufo_sine_inverse, + // ufo_cosine_inverse, + // ufo_tangent_inverse, + // ufo_cosecant_inverse, + // ufo_sectant_inverse, + // ufo_cotangent_inverse, + // ufo_sine_hyperbolic_inverse, + // ufo_cosine_hyperbolic_inverse, + // ufo_tangent_hyperbolic_inverse, + // ufo_cosecant_hyperbolic_inverse, + // ufo_secant_hyperbolic_inverse, + // ufo_cotangent_hyperbolic_inverse, + // ufo_sinc, + // ufo_versine, + // ufo_vercosine, + // ufo_coversine, + // ufo_covercosine, + // ufo_haversine, + // ufo_havercosine, + // ufo_hacoversine, + // ufo_hacovercosine, + // ufo_versine_inverse, + // ufo_vercosine_inverse, + // ufo_coversine_inverse, + // ufo_covercosine_inverse, + // ufo_haversine_inverse, + // ufo_havercosine_inverse, + // ufo_hacoversine_inverse, + // ufo_hacovercosine_inverse, + // ufo_exsecant, + // ufo_excosecant, + // ufo_negation, + // ufo_heaviside, + // ufo_logistic, + // ufo_saw, + // ufo_square, + // ufo_triangle +}; + +fp_t ufo_addition(fp_t x0, fp_t x1) { return (x0 + x1); } +fp_t ufo_subtraction(fp_t x0, fp_t x1) { return (x0 + x1); } +fp_t ufo_division(fp_t x0, fp_t x1) { return (x0 / x1); } +fp_t ufo_multiplication(fp_t x0, fp_t x1) { return (x0 * x1); } +fp_t ufo_power(fp_t x0, fp_t x1) { return pow(x0, x1); } + +fp_t (*BINARY[])(fp_t, fp_t) = {ufo_addition, ufo_subtraction, ufo_division, + ufo_multiplication ufo_power}; + +#endif // UFO_IMPLEMENTATION
\ No newline at end of file |