initHEADmaster

12 files changed, 693 insertions, 0 deletions

diff --git a/.clang-format b/.clang-format
new file mode 100644
index 0000000..6422547
--- /dev/null
+++ b/.clang-format
@@ -0,0 +1,6 @@
+BasedOnStyle: LLVM
+IndentWidth: 4
+UseTab: Never
+BreakBeforeBraces: Linux
+AllowShortIfStatementsOnASingleLine: false
+IndentCaseLabels: false
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..29f57a2
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+brainfuck
+bflisp.bf
+
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..08b9123
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,207 @@
+Non-Profit Open Software License (“Non-Profit OSL”) 3.0
+
+This Non-Profit Open Software License (“Non-Profit OSL”) version 3.0
+(the“License”) applies to any original work of authorship (the
+“Original Work”) whose owner (the “Licensor”) has placed the following
+licensing notice adjacent to the copyright notice for the Original
+Work:
+
+Licensed under the Non-Profit Open Software License version 3.0
+
+1. Grant of Copyright License. Licensor grants You a worldwide,
+royalty-free, non-exclusive, sublicensable license, for the duration
+of the copyright, to do the following:
+
+  a. to reproduce the Original Work in copies, either alone or as part
+  of a collective work;
+  b. to translate, adapt, alter, transform, modify, or arrange the
+  Original Work, thereby creating derivative works (“Derivative Works”)
+  based upon the Original Work;
+  c. to distribute or communicate copies of the Original Work and
+  Derivative Works to the public, with the proviso that copies of
+  Original Work or Derivative Works that You distribute or communicate
+  shall be licensed under this Non-Profit Open Software License or as
+  provided in section 17(d);
+  d. to perform the Original Work publicly; and
+  e. to display the Original Work publicly.
+
+2. Grant of Patent License. Licensor grants You a worldwide,
+royalty-free, non-exclusive, sublicensable license, under patent
+claims owned or controlled by the Licensor that are embodied in the
+Original Work as furnished by the Licensor, for the duration of the
+patents, to make, use, sell, offer for sale, have made, and import the
+Original Work and Derivative Works.
+
+3. Grant of Source Code License. The term “Source Code” means the
+preferred form of the Original Work for making modifications to it and
+all available documentation describing how to modify the Original
+Work. Licensor agrees to provide a machine-readable copy of the Source
+Code of the Original Work along with each copy of the Original Work
+that Licensor distributes. Licensor reserves the right to satisfy this
+obligation by placing a machine-readable copy of the Source Code in an
+information repository reasonably calculated to permit inexpensive and
+convenient access by You for as long as Licensor continues to
+distribute the Original Work.
+
+4. Exclusions From License Grant. Neither the names of Licensor, nor
+the names of any contributors to the Original Work, nor any of their
+trademarks or service marks, may be used to endorse or promote
+products derived from this Original Work without express prior
+permission of the Licensor. Except as expressly stated herein, nothing
+in this License grants any license to Licensor’s trademarks,
+copyrights, patents, trade secrets or any other intellectual property.
+No patent license is granted to make, use, sell, offer for sale, have
+made, or import embodiments of any patent claims other than the
+licensed claims defined in Section 2. No license is granted to the
+trademarks of Licensor even if such marks are included in the Original
+Work. Nothing in this License shall be interpreted to prohibit
+Licensor from licensing under terms different from this License any
+Original Work that Licensor otherwise would have a right to license.
+
+5. External Deployment. The term “External Deployment” means the use,
+distribution, or communication of the Original Work or Derivative
+Works in any way such that the Original Work or Derivative Works may
+be used by anyone other than You, whether those works are distributed
+or communicated to those persons or made available as an application
+intended for use over a network.  As an express condition for the
+grants of license hereunder, You must treat any External Deployment by
+You of the Original Work or a Derivative Work as a distribution under
+section 1(c).
+
+6. Attribution Rights. You must retain, in the Source Code of any
+Derivative Works that You create, all copyright, patent, or trademark
+notices from the Source Code of the Original Work, as well as any
+notices of licensing and any descriptive text identified therein as an
+“Attribution Notice.” You must cause the Source Code for any
+Derivative Works that You create to carry a prominent Attribution
+Notice reasonably calculated to inform recipients that You have
+modified the Original Work.
+
+7. Warranty of Provenance and Disclaimer of Warranty. The Original
+Work is provided under this License on an “AS IS” BASIS and WITHOUT
+WARRANTY, either express or implied, including, without limitation,
+the warranties of non-infringement, merchantability or fitness for a
+particular purpose. THE ENTIRE RISK AS TO THE QUALITY OF THE ORIGINAL
+WORK IS WITH YOU. This DISCLAIMER OF WARRANTY constitutes an essential
+part of this License. No license to the Original Work is granted by
+this License except under this disclaimer.
+
+8. Limitation of Liability. Under no circumstances and under no legal
+theory, whether in tort (including negligence), contract, or otherwise,
+shall the Licensor be liable to anyone for any direct, indirect,
+special, incidental, or consequential damages of any character arising
+as a result of this License or the use of the Original Work including,
+without limitation, damages for loss of goodwill, work stoppage,
+computer failure or malfunction, or any and all other commercial
+damages or losses. This limitation of liability shall not apply to the
+extent applicable law prohibits such limitation.
+
+9. Acceptance and Termination. If, at any time, You expressly assented
+to this License, that assent indicates your clear and irrevocable
+acceptance of this License and all of its terms and conditions. If You
+distribute or communicate copies of the Original Work or a Derivative
+Work, You must make a reasonable effort under the circumstances to
+obtain the express assent of recipients to the terms of this License.
+This License conditions your rights to undertake the activities listed
+in Section 1, including your right to create Derivative Works based
+upon the Original Work, and doing so without honoring these terms and
+conditions is prohibited by copyright law and international treaty.
+Nothing in this License is intended to affect copyright exceptions and
+limitations (including “fair use” or “fair dealing”). This License
+shall terminate immediately and You may no longer exercise any of the
+rights granted to You by this License upon your failure to honor the
+conditions in Section 1(c).
+
+10. Termination for Patent Action. This License shall terminate
+automatically and You may no longer exercise any of the rights granted
+to You by this License as of the date You commence an action,
+including a cross-claim or counterclaim, against Licensor or any
+licensee alleging that the Original Work infringes a patent. This
+termination provision shall not apply for an action alleging patent
+infringement by combinations of the Original Work with other software
+or hardware.
+
+11. Jurisdiction, Venue and Governing Law. Any action or suit relating
+to this License may be brought only in the courts of a jurisdiction
+wherein the Licensor resides or in which Licensor conducts its primary
+business, and under the laws of that jurisdiction excluding its
+conflict-of-law provisions. The application of the United Nations
+Convention on Contracts for the International Sale of Goods is
+expressly excluded. Any use of the Original Work outside the scope of
+this License or after its termination shall be subject to the
+requirements and penalties of copyright or patent law in the
+appropriate jurisdiction. This section shall survive the termination
+of this License.
+
+12. Attorneys’ Fees. In any action to enforce the terms of this
+License or seeking damages relating thereto, the prevailing party
+shall be entitled to recover its costs and expenses, including,
+without limitation, reasonable attorneys’ fees and costs incurred in
+connection with such action, including any appeal of such action. This
+section shall survive the termination of this License.
+
+13. Miscellaneous. If any provision of this License is held to be
+unenforceable, such provision shall be reformed only to the extent
+necessary to make it enforceable.
+
+14. Definition of “You” in This License. “You” throughout this License,
+whether in upper or lower case, means an individual or a legal entity
+exercising rights under, and complying with all of the terms of, this
+License.  For legal entities, “You” includes any entity that controls,
+is controlled by, or is under common control with you. For purposes of
+this definition, “control”means (i) the power, direct or indirect, to
+cause the direction or management of such entity, whether by contract
+or otherwise, or (ii) ownership of fifty percent (50%) or more of the
+outstanding shares, or (iii) beneficial ownership of such entity.
+
+15. Right to Use. You may use the Original Work in all ways not
+otherwise restricted or conditioned by this License or by law, and
+Licensor promises not to interfere with or be responsible for such
+uses by You.
+
+16. Modification of This License. This License is Copyright © 2005
+Lawrence Rosen. Permission is granted to copy, distribute, or
+communicate this License without modification. Nothing in this License
+permits You to modify this License as applied to the Original Work or
+to Derivative Works. However, You may modify the text of this License
+and copy, distribute or communicate your modified version (the
+“Modified License”) and apply it to other original works of authorship
+subject to the following conditions: (i) You may not indicate in any
+way that your Modified License is the “Open Software License” or “OSL”
+and you may not use those names in the name of your Modified License;
+(ii) You must replace the notice specified in the first paragraph
+above with the notice“Licensed under ” or with a notice of your own
+that is not confusingly similar to the notice in this License; and
+(iii) You may not claim that your original works are open source
+software unless your Modified License has been approved by Open Source
+Initiative (OSI) and You comply with its license review and
+certification process.
+
+17. Non-Profit Amendment. The name of this amended version of the Open
+Software License (“OSL 3.0”) is “Non-Profit Open Software License 3.0”
+. The original OSL 3.0 license has been amended as follows:
+
+  a. Licensor represents and declares that it is a not-for-profit
+  organization that derives no revenue whatsoever from the distribution
+  of the Original Work or Derivative Works thereof, or from support or
+  services relating thereto.
+  b. The first sentence of Section 7 [“Warranty of Provenance”] of OSL
+  3.0 has been stricken. For Original Works licensed under this
+  Non-Profit OSL 3.0, LICENSOR OFFERS NO WARRANTIES WHATSOEVER.
+  c. In the first sentence of Section 8 [“Limitation of Liability”] of
+  this Non-Profit OSL 3.0, the list of damages for which LIABILITY IS
+  LIMITED now includes “direct” damages.
+  d. The proviso in Section 1(c) of this License now refers to this
+  “Non-Profit Open Software License” rather than the “Open Software
+  License”. You may distribute or communicate the Original Work or
+  Derivative Works thereof under this Non-Profit OSL 3.0 license only if
+  You make the representation and declaration in paragraph (a) of this
+  Section 17. Otherwise, You shall distribute or communicate the
+  Original Work or Derivative Works thereof only under the OSL 3.0
+  license and You shall publish clear licensing notices so stating. Also
+  by way of clarification, this License does not authorize You to
+  distribute or communicate works under this Non-Profit OSL 3.0 if You
+  received them under the original OSL 3.0 license.
+  e. Original Works licensed under this license shall reference
+  “Non-Profit OSL 3.0” in licensing notices to distinguish them from
+  works licensed under the original OSL 3.0 license.
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..4605125
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,8 @@
+brainfuck: brainfuck.c htable.c crc32.c
+	gcc -O3 $^ -o $@
+
+run: brainfuck
+	./brainfuck helloworld.bf
+
+clean:
+	-rm brainfuck
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..6c125e4
--- /dev/null
+++ b/README.md
@@ -0,0 +1,30 @@
+#  brainfuck
+
+A brainfuck interpreter
+
+## Build
+
+```
+make
+```
+
+## Hello World
+
+```
+./brainfuck ./helloworld.bf
+```
+
+## Lisp!
+
+```
+wget https://raw.githubusercontent.com/shinh/bflisp/master/bflisp.bf
+echo "(car (quote (a b c)))" | ./brainfuck bflisp.bf
+```
+
+WARNING: It's very slow, may takes ~10 minutes to run a `(car (quote (a b c)))`.
+
+## License
+
+You are free to copy, distribute and transmit this software for non-profit purposes under Non-Profit Open Software License 3.0.
+
+See LICENSE for details.
\ No newline at end of file
diff --git a/brainfuck.c b/brainfuck.c
new file mode 100644
index 0000000..1579231
--- /dev/null
+++ b/brainfuck.c
@@ -0,0 +1,212 @@
+// Copyright (C) 2023 Dzshy <dzshy@outlook.com>. All Rights Reserved.
+// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0.
+
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <fcntl.h>
+#include <sys/mman.h>
+#include <sys/stat.h>
+
+#include "crc32.h"
+#include "htable.h"
+
+#define LOGGER(s, ...)                                                         \
+    do {                                                                       \
+        fprintf(stderr, s "\n", ##__VA_ARGS__);                                \
+    } while (0)
+
+uint8_t *pbuf;
+uint8_t *nbuf;
+long nsz, psz;
+static const int INIT_SZ = 128;
+
+typedef struct {
+    long key;
+    long val;
+} JmpTblEntry;
+
+static bool jmptbl_eq(void *x, void *y)
+{
+    long *a = x, *b = y;
+    return *a == *b;
+}
+
+static uint32_t jmptbl_hash(void *k) { return crc32(0, k, sizeof(long)); }
+
+HTable jmptbl;
+
+struct listnode {
+    struct listnode *next;
+    long val;
+};
+typedef struct {
+    struct listnode *head;
+} Stack;
+
+void stack_push(Stack *s, long val)
+{
+    struct listnode *n = malloc(sizeof(struct listnode));
+    n->next = s->head;
+    n->val = val;
+    s->head = n;
+}
+
+long *stack_top(Stack *s)
+{
+    if (s->head == NULL)
+        return NULL;
+    return &(s->head->val);
+}
+
+void stack_pop(Stack *s)
+{
+    if (s->head == NULL)
+        return;
+    struct listnode *next = s->head->next;
+    free(s->head);
+    s->head = next;
+}
+
+void buildjmptable(char *buf, long len)
+{
+    Stack s = {0};
+    htable_init(&jmptbl, sizeof(JmpTblEntry), -1, jmptbl_hash, jmptbl_eq);
+    for (long i = 0; i < len; i++) {
+        if (buf[i] == '[') {
+            stack_push(&s, i);
+        } else if (buf[i] == ']') {
+            long j = *stack_top(&s);
+            stack_pop(&s);
+            JmpTblEntry e1 = {i, j};
+            JmpTblEntry e2 = {j, i};
+            htable_insert(&jmptbl, &e1);
+            htable_insert(&jmptbl, &e2);
+        }
+    }
+}
+
+static long tbllookup(long pos)
+{
+    JmpTblEntry *iter = htable_find(&jmptbl, &pos);
+    return iter->val;
+}
+
+void ensurespc_impl(uint8_t **buf, long *cursz, long ptr)
+{
+    if (ptr > *cursz) {
+        *buf = realloc(*buf, ptr * 2);
+        memset((*buf) + (*cursz), 0, 2 * ptr - (*cursz));
+        *cursz = ptr * 2;
+    }
+}
+
+void ensurespc(long ptr)
+{
+    if (ptr >= 0) {
+        ensurespc_impl(&pbuf, &psz, ptr);
+    } else {
+        ensurespc_impl(&nbuf, &nsz, -ptr);
+    }
+}
+
+uint8_t getdata(long ptr)
+{
+    ensurespc(ptr);
+    if (ptr >= 0)
+        return pbuf[ptr];
+    else
+        return nbuf[-ptr];
+}
+
+void setdata(long ptr, uint8_t val)
+{
+    ensurespc(ptr);
+    if (ptr >= 0)
+        pbuf[ptr] = val;
+    else
+        nbuf[-ptr] = val;
+}
+
+void interp(char *prog, long prog_sz)
+{
+    long prog_p = 0;
+    long data_p = 0;
+    nbuf = malloc(INIT_SZ);
+    pbuf = malloc(INIT_SZ);
+    nsz = INIT_SZ;
+    psz = INIT_SZ;
+    memset(nbuf, 0, INIT_SZ);
+    memset(pbuf, 0, INIT_SZ);
+
+    while (prog_p < prog_sz) {
+        switch (prog[prog_p]) {
+        case '>':
+            data_p++;
+            break;
+        case '<':
+            data_p--;
+            break;
+        case '+':
+            setdata(data_p, getdata(data_p) + 1);
+            break;
+        case '-':
+            setdata(data_p, getdata(data_p) - 1);
+            break;
+        case '.':
+            putchar(getdata(data_p));
+            break;
+        case ',':
+            setdata(data_p, getchar());
+            break;
+        case '[':
+            if (getdata(data_p) == 0) {
+                prog_p = tbllookup(prog_p);
+            }
+            break;
+        case ']':
+            if (getdata(data_p) != 0) {
+                prog_p = tbllookup(prog_p);
+            }
+            break;
+        default:
+            break;
+        }
+        prog_p++;
+    }
+}
+
+int main(int argc, char **argv)
+{
+    if (argc < 2) {
+        LOGGER("invalid args");
+        return EXIT_FAILURE;
+    }
+    int fd = open(argv[1], O_RDONLY);
+    if (fd < 0) {
+        return EXIT_FAILURE;
+    }
+    struct stat fst;
+    int ret = fstat(fd, &fst);
+    if (ret != 0) {
+        LOGGER("error: failed to get file stat");
+        return EXIT_FAILURE;
+    }
+    long filesz = fst.st_size;
+    char *prog = malloc(filesz);
+    FILE *fp = fdopen(fd, "r");
+    if (fp == NULL) {
+        LOGGER("error opening file");
+        exit(-1);
+    }
+    size_t read = fread(prog, 1, filesz, fp);
+    if (read < filesz) {
+        LOGGER("erro reading");
+        exit(-1);
+    }
+    buildjmptable(prog, filesz);
+    interp(prog, filesz);
+    return EXIT_SUCCESS;
+}
diff --git a/crc32.c b/crc32.c
new file mode 100644
index 0000000..23436dc
--- /dev/null
+++ b/crc32.c
@@ -0,0 +1,58 @@
+// Copyright (C) 2023 Dzshy <dzshy@outlook.com>. All Rights Reserved.
+// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0.
+
+#include "crc32.h"
+
+const uint32_t crc32_tab[] = {
+    0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
+    0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
+    0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
+    0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
+    0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
+    0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
+    0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
+    0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
+    0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
+    0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
+    0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
+    0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
+    0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
+    0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
+    0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
+    0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
+    0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
+    0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
+    0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
+    0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
+    0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
+    0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
+    0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
+    0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
+    0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
+    0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
+    0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
+    0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
+    0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
+    0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
+    0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
+    0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
+    0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
+    0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
+    0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
+    0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
+    0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
+    0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
+    0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
+    0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
+    0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
+    0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
+    0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d};
+
+uint32_t crc32(uint32_t crc, void *buf, int size)
+{
+    uint8_t *p = buf;
+    crc = ~crc;
+    while (size--)
+        crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
+    return ~crc;
+}
diff --git a/crc32.h b/crc32.h
new file mode 100644
index 0000000..7055a1c
--- /dev/null
+++ b/crc32.h
@@ -0,0 +1,11 @@
+// Copyright (C) 2023 Dzshy <dzshy@outlook.com>. All Rights Reserved.
+// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0.
+
+#ifndef CRC32_H_
+#define CRC32_H_
+
+#include <stdint.h>
+
+uint32_t crc32(uint32_t r, void *buf, int size);
+
+#endif
diff --git a/helloworld.bf b/helloworld.bf
new file mode 100644
index 0000000..4e1d726
--- /dev/null
+++ b/helloworld.bf
@@ -0,0 +1,12 @@
+>++++++++[<+++++++++>-]<.
+>++++[<+++++++>-]<+.
++++++++..
++++.
+>>++++++[<+++++++>-]<++.
+------------.
+>++++++[<+++++++++>-]<+.
+<.
++++.
+------.
+--------.
+>>>++++[<++++++++>-]<+.
diff --git a/htable.c b/htable.c
new file mode 100644
index 0000000..66ae607
--- /dev/null
+++ b/htable.c
@@ -0,0 +1,112 @@
+// Copyright (C) 2023 Dzshy <dzshy@outlook.com>. All Rights Reserved.
+// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0.
+
+#include "htable.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#define HTFL_NUL 0
+#define HTFL_VAL 1
+#define HTFL_DEL 2
+
+static void *htable_end(HTable *ht)
+{
+    return ht->buf + ht->cap * (ht->elemsz + 1);
+}
+
+static void rebuild(HTable *ht)
+{
+    HTable newht;
+    htable_init(&newht, ht->elemsz, ht->size * 8, ht->hash, ht->eq);
+    void *iter = htable_begin(ht);
+    while (iter != NULL) {
+        htable_insert(&newht, iter);
+        iter = htable_next(ht, iter);
+    }
+    free(ht->buf);
+    *ht = newht;
+}
+
+static uint8_t getflag(void *iter) { return *(uint8_t *)(iter - 1); }
+
+static void setflag(void *iter, uint8_t flag) { *(uint8_t *)(iter - 1) = flag; }
+
+void htable_init(HTable *ht, int elemsz, int cap, uint32_t (*hash)(void *),
+                 bool (*eq)(void *, void *))
+{
+    if (cap < 16)
+        cap = 16;
+    ht->buf = malloc(cap * (elemsz + 1));
+    memset(ht->buf, 0, cap * (elemsz + 1));
+    ht->size = 0;
+    ht->cap = cap;
+    ht->taken = 0;
+    ht->begin = NULL;
+    ht->elemsz = elemsz;
+    ht->hash = hash;
+    ht->eq = eq;
+}
+
+bool htable_insert(HTable *ht, void *elem)
+{
+    if (ht->taken + 1 > ht->cap / 4) {
+        rebuild(ht);
+    }
+    ht->taken++;
+    ht->size++;
+    int hashcode = ht->hash(elem) % ht->cap;
+    void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1;
+    while (getflag(pos) != HTFL_NUL) {
+        if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem))
+            return false;
+        pos += ht->elemsz + 1;
+        if (pos >= htable_end(ht)) { // arrived end, restart from beginning
+            pos = ht->buf + 1;
+        }
+    }
+    memcpy(pos, elem, ht->elemsz);
+    setflag(pos, HTFL_VAL);
+    if (pos < ht->begin || ht->begin == NULL) {
+        ht->begin = pos;
+    }
+}
+
+void htable_del(HTable *ht, void *iter)
+{
+    ht->size--;
+    setflag(iter, HTFL_DEL);
+    if (iter == ht->begin) {
+        ht->begin = htable_next(ht, iter);
+    }
+}
+
+void *htable_find(HTable *ht, void *elem)
+{
+    int hashcode = ht->hash(elem) % ht->cap;
+    void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1;
+    while (getflag(pos) != HTFL_NUL) {
+        if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem))
+            return pos;
+        pos += ht->elemsz + 1;
+        if (pos >= htable_end(ht)) { // arrived end, restart from beginning
+            pos = ht->buf + 1;
+        }
+    }
+    return NULL;
+}
+
+void *htable_begin(HTable *ht) { return ht->begin; }
+
+void *htable_next(HTable *ht, void *iter)
+{
+    void *pos = iter;
+    pos += ht->elemsz + 1;
+    while (getflag(pos) != HTFL_VAL) {
+        pos += ht->elemsz + 1;
+        if (pos >= htable_end(ht)) { // arrived end, restart from beginning
+            return NULL;
+        }
+    }
+    return pos;
+}
diff --git a/htable.h b/htable.h
new file mode 100644
index 0000000..c373baa
--- /dev/null
+++ b/htable.h
@@ -0,0 +1,31 @@
+// Copyright (C) 2023 Dzshy <dzshy@outlook.com>. All Rights Reserved.
+// Licensed under Non-Profit Open Software License ("Non-Profit OSL") 3.0.
+
+#ifndef HTABLE_H_
+#define HTABLE_H_
+
+#include <stdbool.h>
+#include <stdint.h>
+
+typedef struct {
+    void *buf;
+    int size;
+    int cap;
+    int taken;
+    void *begin;
+    int elemsz;
+    uint32_t (*hash)(void *);
+    bool (*eq)(void *, void *);
+} HTable;
+
+void htable_init(HTable *ht, int elemsz, int cap, uint32_t (*hash)(void *),
+                 bool (*eq)(void *, void *));
+bool htable_insert(HTable *ht, void *elem);
+void htable_del(HTable *ht, void *iter);
+
+// return a iterator
+void *htable_find(HTable *ht, void *elem);
+void *htable_begin(HTable *ht);
+void *htable_next(HTable *ht, void *iter);
+
+#endif
diff --git a/scripts/format.sh b/scripts/format.sh
new file mode 100755
index 0000000..6dade1b
--- /dev/null
+++ b/scripts/format.sh
@@ -0,0 +1,3 @@
+#!/bin/bash
+
+clang-format -i $(find . -name '*.c' -or -name '*.h')