diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/build.c | 117 | ||||
| -rw-r--r-- | src/free.c | 40 | ||||
| -rw-r--r-- | src/main.c | 100 | ||||
| -rw-r--r-- | src/parse.c | 161 | ||||
| -rw-r--r-- | src/print.c | 54 | ||||
| -rw-r--r-- | src/term.c | 19 |
6 files changed, 491 insertions, 0 deletions
diff --git a/src/build.c b/src/build.c new file mode 100644 index 0000000..510afe0 --- /dev/null +++ b/src/build.c @@ -0,0 +1,117 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#include <stdlib.h> +#include <string.h> +#include <stdio.h> + +#include <build.h> +#include <free.h> +#include <parse.h> + +static void write_bit(char val, FILE *file, char *byte, int *bit) +{ + if (*bit > 7) { // flush byte + fwrite(byte, 1, 1, file); + *byte = 0; + *bit = 0; + } + + if (val) + *byte |= 1UL << (7 - *bit); + (*bit)++; +} + +static void rec_write_bblc(struct term *term, FILE *file, char *byte, int *bit) +{ + switch (term->type) { + case ABS: + write_bit(0, file, byte, bit); + write_bit(0, file, byte, bit); + rec_write_bblc(term->u.abs.term, file, byte, bit); + break; + case APP: + write_bit(0, file, byte, bit); + write_bit(1, file, byte, bit); + rec_write_bblc(term->u.app.lhs, file, byte, bit); + rec_write_bblc(term->u.app.rhs, file, byte, bit); + break; + case VAR: + for (int i = 0; i <= term->u.var.index; i++) + write_bit(1, file, byte, bit); + write_bit(0, file, byte, bit); + break; + default: + fprintf(stderr, "Invalid type %d\n", term->type); + } +} + +// writes bit-encoded blc into file +static void write_bblc(struct term *term, FILE *file) +{ + char byte = 0; + int bit = 0; + rec_write_bblc(term, file, &byte, &bit); + + if (bit) // flush final + fwrite(&byte, 1, 1, file); +} + +void write_bloc(struct term *term, const char *path) +{ + (void)term; // TODO + + // example data + short length = 2; + struct term *M = parse_blc("0000000001100111100111100111100111011110"); + struct term *N = parse_blc("00000000011001111001111001100111011110"); + + FILE *file = fopen(path, "wb"); + fwrite(BLOC_IDENTIFIER, BLOC_IDENTIFIER_LENGTH, 1, file); + fwrite(&length, 2, 1, file); + + write_bblc(M, file); + write_bblc(N, file); + + // TODO + short table_index = 0; + char byte = 0; + int bit = 0; + write_bit(0, file, &byte, &bit); + write_bit(0, file, &byte, &bit); + write_bit(0, file, &byte, &bit); + write_bit(1, file, &byte, &bit); + write_bit(0, file, &byte, &bit); + write_bit(1, file, &byte, &bit); + write_bit(0, file, &byte, &bit); + write_bit(1, file, &byte, &bit); + write_bit(1, file, &byte, &bit); + + for (int i = 0; i < 16; i++) + write_bit(0, file, &byte, &bit); + + write_bit(0, file, &byte, &bit); + write_bit(0, file, &byte, &bit); + write_bit(1, file, &byte, &bit); + + for (int i = 0; i < 16; i++) + write_bit(0, file, &byte, &bit); + + write_bit(1, file, &byte, &bit); + + for (int i = 0; i < 16; i++) + write_bit(0, file, &byte, &bit); + + write_bit(1, file, &byte, &bit); + + for (int i = 0; i < 16; i++) + write_bit(0, file, &byte, &bit); + + if (bit) // flush final + fwrite(&byte, 1, 1, file); + + fclose(file); + + free_term(M); + free_term(N); +} diff --git a/src/free.c b/src/free.c new file mode 100644 index 0000000..b22089e --- /dev/null +++ b/src/free.c @@ -0,0 +1,40 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#include <stdio.h> +#include <stdlib.h> + +#include <free.h> + +void free_term(struct term *term) +{ + switch (term->type) { + case ABS: + free_term(term->u.abs.term); + free(term); + break; + case APP: + free_term(term->u.app.lhs); + free_term(term->u.app.rhs); + free(term); + break; + case VAR: + free(term); + break; + case REF: + free(term); + break; + default: + fprintf(stderr, "Invalid type %d\n", term->type); + } +} + +void free_bloc(struct bloc_parsed *bloc) +{ + for (size_t i = 0; i < bloc->length; i++) { + free_term(bloc->entries[i]); + } + + free(bloc->entries); + free(bloc); +} diff --git a/src/main.c b/src/main.c new file mode 100644 index 0000000..454c9d9 --- /dev/null +++ b/src/main.c @@ -0,0 +1,100 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#include <stdio.h> +#include <errno.h> +#include <string.h> +#include <stdlib.h> + +#include <term.h> +#include <print.h> +#include <parse.h> +#include <build.h> +#include <free.h> + +#define BUF_SIZE 1024 +static char *read_stdin(void) +{ + char buffer[BUF_SIZE]; + size_t size = 1; + char *string = malloc(sizeof(char) * BUF_SIZE); + if (!string) + return 0; + string[0] = '\0'; + while (fgets(buffer, BUF_SIZE, stdin)) { + char *old = string; + size += strlen(buffer); + string = realloc(string, size); + if (!string) { + free(old); + return 0; + } + strcat(string, buffer); + } + + if (ferror(stdin)) { + free(string); + fprintf(stderr, "Couldn't read from stdin\n"); + return 0; + } + return string; +} + +static char *read_file(const char *path) +{ + FILE *f = fopen(path, "rb"); + if (!f) { + fprintf(stderr, "Can't open file %s: %s\n", path, + strerror(errno)); + return 0; + } + + fseek(f, 0, SEEK_END); + long fsize = ftell(f); + fseek(f, 0, SEEK_SET); + + char *string = malloc(fsize + 1); + int ret = fread(string, fsize, 1, f); + fclose(f); + + if (ret != 1) { + fprintf(stderr, "Can't read file %s: %s\n", path, + strerror(errno)); + return 0; + } + + string[fsize] = 0; + return string; +} + +int main(int argc, char **argv) +{ + /* if (argc < 2) { */ + /* fprintf(stderr, "Invalid arguments\n"); */ + /* return 1; */ + /* } */ + + /* char *input; */ + /* if (argv[1][0] == '-') { */ + /* input = read_stdin(); */ + /* } else { */ + /* input = read_file(argv[1]); */ + /* } */ + + /* if (!input) */ + /* return 1; */ + + /* struct term *parsed = parse_blc(input); */ + /* print_bruijn(parsed); */ + + write_bloc(0, "test.bloc"); + + const char *input = read_file("test.bloc"); + struct bloc_parsed *bloc = parse_bloc(input); + struct term *term = from_bloc(bloc); + print_blc(term); + + /* free_term(term); // TODO: Fix sharing user-after-free */ + + return 0; +} diff --git a/src/parse.c b/src/parse.c new file mode 100644 index 0000000..8c69056 --- /dev/null +++ b/src/parse.c @@ -0,0 +1,161 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include <term.h> +#include <spec.h> +#include <parse.h> + +static struct term *rec_blc(const char **term) +{ + struct term *res = 0; + if (!**term) { + fprintf(stderr, "invalid parsing state!\n"); + } else if (**term == '0' && *(*term + 1) == '0') { + (*term) += 2; + res = new_term(ABS); + res->u.abs.term = rec_blc(term); + } else if (**term == '0' && *(*term + 1) == '1') { + (*term) += 2; + res = new_term(APP); + res->u.app.lhs = rec_blc(term); + res->u.app.rhs = rec_blc(term); + } else if (**term == '1') { + const char *cur = *term; + while (**term == '1') + (*term)++; + res = new_term(VAR); + res->u.var.index = *term - cur - 1; + (*term)++; + } else { + (*term)++; + res = rec_blc(term); + } + return res; +} + +struct term *parse_blc(const char *term) +{ + return rec_blc(&term); +} + +#define BIT_AT(i) (term[(i) / 8] & (1 << (7 - ((i) % 8)))) + +// parses normal bit-encoded blc +static struct term *parse_bblc(const char *term, size_t *bit) +{ + struct term *res = 0; + if (!BIT_AT(*bit) && !BIT_AT(*bit + 1)) { + (*bit) += 2; + res = new_term(ABS); + res->u.abs.term = parse_bblc(term, bit); + } else if (!BIT_AT(*bit) && BIT_AT(*bit + 1)) { + (*bit) += 2; + res = new_term(APP); + res->u.app.lhs = parse_bblc(term, bit); + res->u.app.rhs = parse_bblc(term, bit); + } else if (BIT_AT(*bit)) { + const size_t cur = *bit; + while (BIT_AT(*bit)) + (*bit)++; + res = new_term(VAR); + res->u.var.index = *bit - cur - 1; + (*bit)++; + } else { + (*bit)++; + res = parse_bblc(term, bit); + } + return res; +} + +// parses bloc's bit-encoded blc (1I => 2B index) +static struct term *parse_bloc_bblc(const char *term, size_t *bit) +{ + struct term *res = 0; + if (!BIT_AT(*bit) && !BIT_AT(*bit + 1)) { + (*bit) += 2; + res = new_term(ABS); + res->u.abs.term = parse_bloc_bblc(term, bit); + } else if (!BIT_AT(*bit) && BIT_AT(*bit + 1)) { + (*bit) += 2; + res = new_term(APP); + res->u.app.lhs = parse_bloc_bblc(term, bit); + res->u.app.rhs = parse_bloc_bblc(term, bit); + } else if (BIT_AT(*bit)) { + (*bit) += 1; + res = new_term(REF); + short index = 0; + for (int i = 0; i < 16; i++) + index |= (BIT_AT(*bit) >> (7 - (*bit % 8))) << i; + res->u.ref.index = index; + (*bit) += 16; + } else { + (*bit)++; + res = parse_bloc_bblc(term, bit); + } + return res; +} + +struct bloc_parsed *parse_bloc(const void *bloc) +{ + const struct bloc_header *header = bloc; + if (memcmp(header->identifier, BLOC_IDENTIFIER, + (size_t)BLOC_IDENTIFIER_LENGTH)) { + fprintf(stderr, "invalid BLoC identifier!\n"); + return 0; + } + + struct bloc_parsed *parsed = malloc(sizeof(*parsed)); + parsed->length = header->length; + parsed->entries = malloc(header->length * sizeof(struct term *)); + + const struct bloc_entry *current = (const void *)&header->data; + for (size_t i = 0; i < parsed->length; i++) { + size_t len = 0; + parsed->entries[i] = parse_bblc((const char *)current, &len); + current = + (const struct bloc_entry *)(((const char *)current) + + (len / 8) + (len % 8 != 0)); + } + + size_t len = 0; + const char *term = (const char *)current; + parsed->term = parse_bloc_bblc(term, &len); + + return parsed; +} + +static struct term *rec_bloc(struct term *term, struct bloc_parsed *bloc) +{ + switch (term->type) { + case ABS: + rec_bloc(term->u.abs.term, bloc); + break; + case APP: + rec_bloc(term->u.app.lhs, bloc); + rec_bloc(term->u.app.rhs, bloc); + break; + case VAR: + fprintf(stderr, "bloc can't have vars\n"); + return 0; + case REF: + if (term->u.ref.index >= bloc->length) { + fprintf(stderr, "invalid entry reference\n"); + return 0; + } + memcpy(term, bloc->entries[term->u.ref.index], sizeof(*term)); + break; + default: + fprintf(stderr, "invalid type %d\n", term->type); + return 0; + } + return term; +} + +struct term *from_bloc(struct bloc_parsed *bloc) +{ + return rec_bloc(bloc->term, bloc); +} diff --git a/src/print.c b/src/print.c new file mode 100644 index 0000000..425aedb --- /dev/null +++ b/src/print.c @@ -0,0 +1,54 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#include <stdio.h> + +#include <print.h> + +void print_bruijn(struct term *term) +{ + switch (term->type) { + case ABS: + printf("["); + print_bruijn(term->u.abs.term); + printf("]"); + break; + case APP: + printf("("); + print_bruijn(term->u.app.lhs); + printf(" "); + print_bruijn(term->u.app.rhs); + printf(")"); + break; + case VAR: + printf("%d", term->u.var.index); + break; + case REF: + printf("<%ld>", term->u.ref.index); + break; + default: + fprintf(stderr, "Invalid type %d\n", term->type); + } +} + +void print_blc(struct term *term) +{ + switch (term->type) { + case ABS: + printf("00"); + print_blc(term->u.abs.term); + break; + case APP: + printf("01"); + print_blc(term->u.app.lhs); + print_blc(term->u.app.rhs); + break; + case VAR: + for (int i = 0; i <= term->u.var.index; i++) + printf("1"); + printf("0"); + break; + default: + fprintf(stderr, "Invalid type %d\n", term->type); + } +} diff --git a/src/term.c b/src/term.c new file mode 100644 index 0000000..7ab1a79 --- /dev/null +++ b/src/term.c @@ -0,0 +1,19 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include <term.h> + +struct term *new_term(term_type type) +{ + struct term *term = malloc(sizeof(*term)); + if (!term) { + fprintf(stderr, "Out of memory!\n"); + abort(); + } + term->type = type; + return term; +} |