Pointer tagging!

Copied from oats, just the basics required for tagging integers or
symbols.

3 files changed, 83 insertions, 4 deletions

diff --git a/base.h b/base.h
index 034bef2..ae62268 100644
--- a/base.h
+++ b/base.h
@@ -18,9 +18,10 @@
 #include <stdint.h>
 
 /// The bare fucking minimum
-#define MAX(A, B)  ((A) > (B) ? (A) : (B))
-#define MIN(A, B)  ((A) < (B) ? (A) : (B))
-#define ARRSIZE(A) (sizeof(A) / sizeof((A)[0]))
+#define MAX(A, B)      ((A) > (B) ? (A) : (B))
+#define MIN(A, B)      ((A) < (B) ? (A) : (B))
+#define ARRSIZE(A)     (sizeof(A) / sizeof((A)[0]))
+#define NTH_BYTE(X, N) (((X) >> (8 * N)) & ((1 << 8) - 1))
 
 typedef uint8_t u8;
 typedef uint16_t u16;
@@ -80,4 +81,40 @@ void sym_table_init(sym_table_t *table);
 char *sym_table_find(sym_table_t *table, sv_t sv);
 void sym_table_cleanup(sym_table_t *table);
 
+/// Pointer tagging scheme for lisps
+#define NIL 0
+typedef struct Obj lisp_t;
+
+typedef enum Tag
+{
+  TAG_NIL  = 0b00000000,
+  TAG_INT  = 0b00000001, // special so we can encode 63 bit integers
+  TAG_SYM  = 0b00000100,
+  NUM_TAGS = 3,
+} tag_t;
+
+enum Shift
+{
+  SHIFT_INT = 1,
+  SHIFT_SYM = 8,
+};
+
+enum Mask
+{
+  MASK_INT = 0b00000001,
+  MASK_SYM = 0b11111111,
+};
+
+#define TAG(PTR, TYPE)    ((lisp_t *)(((PTR) << SHIFT_##TYPE) | TAG_##TYPE))
+#define IS_TAG(PTR, TYPE) (((u64)(PTR) & MASK_##TYPE) == TAG_##TYPE)
+#define UNTAG(PTR, TYPE)  (((u64)PTR) >> SHIFT_##TYPE)
+
+#define INT_MAX ((1L << 62) - 1)
+#define INT_MIN (-(1L << 62))
+
+lisp_t *tag_int(i64 i);
+lisp_t *tag_sym(char *str);
+i64 as_int(lisp_t *);
+char *as_sym(lisp_t *);
+
 #endif
diff --git a/build.sh b/build.sh
index 6b06888..9f749ed 100644
--- a/build.sh
+++ b/build.sh
@@ -1,7 +1,7 @@
 #!/usr/bin/env sh
 
 CFLAGS="-Wall -Wextra -std=c11 -ggdb -fsanitize=address -fsanitize=undefined"
-SRC="vec.c symtable.c main.c"
+SRC="vec.c tag.c symtable.c main.c"
 OUT="alisp.out"
 
 set -xe
diff --git a/tag.c b/tag.c
new file mode 100644
index 0000000..7688d63
--- /dev/null
+++ b/tag.c
@@ -0,0 +1,42 @@
+/* Copyright (C) 2025 Aryadev Chavali
+
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE.  See the Unlicense for details.
+
+ * You may distribute and modify this code under the terms of the Unlicense,
+ * which you should have received a copy of along with this program.  If not,
+ * please go to <https://unlicense.org/>.
+
+ * Created: 2025-08-19
+ * Description: Pointer tagging
+ */
+
+#include <assert.h>
+
+#include "./base.h"
+
+lisp_t *tag_int(i64 i)
+{
+  return TAG((u64)i, INT);
+}
+
+lisp_t *tag_sym(char *str)
+{
+  return TAG((u64)str, SYM);
+}
+
+i64 as_int(lisp_t *obj)
+{
+  assert(IS_TAG(obj, INT));
+  u64 p_obj = (u64)obj;
+  return UNTAG(p_obj, INT) |               // Delete the tag
+         (NTH_BYTE(p_obj, 7) & 0x80) << 56 // duplicate the MSB (preserve sign)
+      ;
+}
+
+char *as_sym(lisp_t *obj)
+{
+  assert(IS_TAG(obj, SYM));
+  return (char *)UNTAG(obj, SYM);
+}