diff options
| -rw-r--r-- | .gitignore | 5 | ||||
| -rw-r--r-- | inc/build.h | 12 | ||||
| -rw-r--r-- | inc/free.h | 13 | ||||
| -rw-r--r-- | inc/parse.h | 22 | ||||
| -rw-r--r-- | inc/print.h | 12 | ||||
| -rw-r--r-- | inc/spec.h | 24 | ||||
| -rw-r--r-- | inc/term.h | 32 | ||||
| -rw-r--r-- | license | 21 | ||||
| -rw-r--r-- | makefile | 48 | ||||
| -rw-r--r-- | readme.md | 4 | ||||
| -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 |
16 files changed, 682 insertions, 2 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..c50f973 --- /dev/null +++ b/.gitignore @@ -0,0 +1,5 @@ +.cache/ +build/ + +compile_commands.json +tags diff --git a/inc/build.h b/inc/build.h new file mode 100644 index 0000000..fe41e11 --- /dev/null +++ b/inc/build.h @@ -0,0 +1,12 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#ifndef BLOC_BUILD_H +#define BLOC_BUILD_H + +#include <spec.h> +#include <term.h> + +void write_bloc(struct term *term, const char *path); + +#endif diff --git a/inc/free.h b/inc/free.h new file mode 100644 index 0000000..34c82c7 --- /dev/null +++ b/inc/free.h @@ -0,0 +1,13 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#ifndef BLOC_FREE_H +#define BLOC_FREE_H + +#include <parse.h> +#include <term.h> + +void free_term(struct term *term); +void free_bloc(struct bloc_parsed *bloc); + +#endif diff --git a/inc/parse.h b/inc/parse.h new file mode 100644 index 0000000..c8cafed --- /dev/null +++ b/inc/parse.h @@ -0,0 +1,22 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#ifndef BLOC_PARSE_H +#define BLOC_PARSE_H + +#include <stddef.h> + +#include <term.h> +#include <spec.h> + +struct bloc_parsed { + size_t length; + struct term **entries; + struct term *term; +}; + +struct term *parse_blc(const char *term); +struct bloc_parsed *parse_bloc(const void *bloc); +struct term *from_bloc(struct bloc_parsed *bloc); + +#endif diff --git a/inc/print.h b/inc/print.h new file mode 100644 index 0000000..9885f57 --- /dev/null +++ b/inc/print.h @@ -0,0 +1,12 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#ifndef BLOC_PRINT_H +#define BLOC_PRINT_H + +#include <term.h> + +void print_bruijn(struct term *term); +void print_blc(struct term *term); + +#endif diff --git a/inc/spec.h b/inc/spec.h new file mode 100644 index 0000000..8bd8ace --- /dev/null +++ b/inc/spec.h @@ -0,0 +1,24 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#ifndef BLOC_SPEC_H +#define BLOC_SPEC_H + +#define BLOC_IDENTIFIER "BLoC" +#define BLOC_IDENTIFIER_LENGTH 4 + +struct bloc_header { + char identifier[BLOC_IDENTIFIER_LENGTH]; + short length; + void *data; +} __attribute__((packed)); + +struct bloc_entry { + void *expression; +} __attribute__((packed)); + +struct bloc_structure { + void *expression; +} __attribute__((packed)); + +#endif diff --git a/inc/term.h b/inc/term.h new file mode 100644 index 0000000..a90bdd3 --- /dev/null +++ b/inc/term.h @@ -0,0 +1,32 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#ifndef BLOC_TERM_H +#define BLOC_TERM_H + +#include <stddef.h> + +typedef enum { INV, ABS, APP, VAR, REF } term_type; + +struct term { + term_type type; + union { + struct { + struct term *term; + } abs; + struct { + struct term *lhs; + struct term *rhs; + } app; + struct { + int index; + } var; + struct { + size_t index; + } ref; + } u; +}; + +struct term *new_term(term_type type); + +#endif @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2023 Marvin Borner + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/makefile b/makefile new file mode 100644 index 0000000..bb6530d --- /dev/null +++ b/makefile @@ -0,0 +1,48 @@ +# Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +# SPDX-License-Identifier: MIT + +CC = gcc +TG = ctags + +BUILD = ${CURDIR}/build +SRC = ${CURDIR}/src +INC = ${CURDIR}/inc +SRCS = $(wildcard $(SRC)/*.c) +OBJS = $(patsubst $(SRC)/%.c, $(BUILD)/%.o, $(SRCS)) + +CFLAGS_DEBUG = -Wno-error -g -O0 -Wno-unused -fsanitize=address,undefined,leak +CFLAGS_WARNINGS = -Wall -Wextra -Wshadow -Wpointer-arith -Wwrite-strings -Wredundant-decls -Wnested-externs -Wmissing-declarations -Wstrict-prototypes -Wmissing-prototypes -Wcast-qual -Wswitch-default -Wswitch-enum -Wunreachable-code -Wundef -Wold-style-definition -pedantic -Wno-switch-enum +CFLAGS = $(CFLAGS_WARNINGS) -std=c99 -Ofast -I$(INC) + +ifdef DEBUG # TODO: Somehow clean automagically +CFLAGS += $(CFLAGS_DEBUG) +endif + +ifeq ($(PREFIX),) + PREFIX := /usr/local +endif + +all: compile sync + +compile: $(BUILD) $(OBJS) $(BUILD)/bloc + +clean: + @rm -rf $(BUILD)/* + +install: + @install -m 755 $(BUILD)/bloc $(DESTDIR)$(PREFIX)/bin/ + +sync: # Ugly hack + @$(MAKE) $(BUILD)/bloc --always-make --dry-run | grep -wE 'gcc|g\+\+' | grep -w '\-c' | jq -nR '[inputs|{directory:".", command:., file: match(" [^ ]+$$").string[1:]}]' >compile_commands.json + @$(TG) -R --exclude=.git --exclude=build . + +$(BUILD)/%.o: $(SRC)/%.c + @$(CC) -c -o $@ $(CFLAGS) $< + +$(BUILD)/bloc: $(OBJS) + @$(CC) -o $@ $(CFLAGS) $^ + +.PHONY: all compile clean sync + +$(BUILD): + @mkdir -p $@ @@ -56,5 +56,5 @@ A possible encoding in BLoC: | 0x16 | 0x26 | `N` in BLC | | 0x26 | 0x32 | `000101011<M>001<N>1<M>1<N>`, where `<M>=0` and `<N>=1` are 2 byte indices | -Even using this small example BLoC uses less space than BLC (0x32 vs. -0x42 bytes). +Even in this small example BLoC uses less space than BLC (0x32 vs. 0x42 +bytes). 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; +} |