ref: af68820de45fb5675495e70c38d2688138701936
parent: 0ddd26de786eb67b38bc7a6fa371e7d3a87725db
author: Sigrid Solveig Haflínudóttir <sigrid@ftrv.se>
date: Tue Dec 24 22:12:41 EST 2024
symtab: use QP tries instead (can help with completion later too)
--- /dev/null
+++ b/3rd/fn.c
@@ -1,0 +1,209 @@
+// fn.c: quintet bit popcount patricia tries, new version
+//
+// Written by Tony Finch <dot@dotat.at>
+// You may do anything with this. It has no warranty.
+// <http://creativecommons.org/publicdomain/zero/1.0/>
+
+#include "platform.h"
+#include "tbl.h"
+#include "fn.h"
+
+bool
+Tgetkv(Tbl *t, const char *key, size_t len, const char **pkey, void **pval)
+{+ if(t == nil)
+ return false;
+ while(isbranch(t)){+ __builtin_prefetch(t->ptr);
+ Tindex i = t->index;
+ Tbitmap b = twigbit(i, key, len);
+ if(!hastwig(i, b))
+ return false;
+ t = Tbranch_twigs(t) + twigoff(i, b);
+ }
+ if(strcmp(key, Tleaf_key(t)) != 0)
+ return false;
+ *pkey = Tleaf_key(t);
+ *pval = Tleaf_val(t);
+ return true;
+}
+
+static bool
+next_rec(Trie *t, const char **pkey, size_t *plen, void **pval)
+{+ Tindex i = t->index;
+ if(Tindex_branch(i)){+ // Recurse to find either this leaf (*pkey != nil)
+ // or the next one (*pkey == nil).
+ Tbitmap b = twigbit(i, *pkey, *plen);
+ uint s, m; TWIGOFFMAX(s, m, i, b);
+ for(; s < m; s++){+ if(next_rec(Tbranch_twigs(t)+s, pkey, plen, pval))
+ return true;
+ }
+ return false;
+ }
+ // We have found the next leaf.
+ if(*pkey == nil){+ *pkey = Tleaf_key(t);
+ *plen = strlen(*pkey);
+ *pval = Tleaf_val(t);
+ return true;
+ }
+ // We have found this leaf, so start looking for the next one.
+ if(strcmp(*pkey, Tleaf_key(t)) == 0){+ *pkey = nil;
+ *plen = 0;
+ return false;
+ }
+ // No match.
+ return false;
+}
+
+bool
+Tnextl(Tbl *tbl, const char **pkey, size_t *plen, void **pval)
+{+ if(tbl == nil){+ *pkey = nil;
+ *plen = 0;
+ return false;
+ }
+ return next_rec(tbl, pkey, plen, pval);
+}
+
+Tbl *
+Tdelkv(Tbl *tbl, const char *key, size_t len, const char **pkey, void **pval)
+{+ if(tbl == nil)
+ return nil;
+ Trie *t = tbl, *p = nil;
+ Tindex i = 0;
+ Tbitmap b = 0;
+ while(isbranch(t)){+ __builtin_prefetch(t->ptr);
+ i = t->index;
+ b = twigbit(i, key, len);
+ if(!hastwig(i, b))
+ return tbl;
+ p = t; t = Tbranch_twigs(t) + twigoff(i, b);
+ }
+ if(strcmp(key, Tleaf_key(t)) != 0)
+ return tbl;
+ *pkey = Tleaf_key(t);
+ *pval = Tleaf_val(t);
+ if(p == nil){+ MEM_FREE(tbl);
+ return nil;
+ }
+ Trie *twigs = Tbranch_twigs(p);
+ uint m = popcount(Tindex_bitmap(i));
+ assert(twigs <= t && t < twigs+m);
+ if(m == 2){+ // Move the other twig to the parent branch.
+ *p = twigs[twigs == t];
+ MEM_FREE(twigs);
+ return tbl;
+ }
+ memmove(t, t+1, ((twigs + m) - (t + 1)) * sizeof(Trie));
+ p->index = Tbitmap_del(i, b);
+ // We have now correctly removed the twig from the trie, so if
+ // MEM_REALLOC() fails we can ignore it and continue to use the
+ // slightly oversized twig array.
+ twigs = MEM_REALLOC(twigs, sizeof(Trie) * (m - 1));
+ if(twigs != nil)
+ Tset_twigs(p, twigs);
+ return tbl;
+}
+
+Tbl *
+Tsetl(Tbl *tbl, const char *key, size_t len, void *val)
+{+ assert(!Tindex_branch((Tindex)val) && len <= Tmaxlen);
+ if(val == nil)
+ return Tdell(tbl, key, len);
+ // First leaf in an empty tbl?
+ if(tbl == nil){+ tbl = MEM_ALLOC(sizeof(*tbl));
+ if(tbl == nil)
+ return nil;
+ Tset_key(tbl, key);
+ Tset_val(tbl, val);
+ return tbl;
+ }
+ Trie *t = tbl;
+ // Find the most similar leaf node in the trie. We will compare
+ // its key with our new key to find the first differing nibble,
+ // which can be at a lower index than the point at which we
+ // detect a difference.
+ while(isbranch(t)){+ __builtin_prefetch(t->ptr);
+ Tindex i = t->index;
+ Tbitmap b = twigbit(i, key, len);
+ // Even if our key is missing from this branch we need to
+ // keep iterating down to a leaf. It doesn't matter which
+ // twig we choose since the keys are all the same up to this
+ // index. Note that blindly using twigoff(t, b) can cause
+ // an out-of-bounds index if it equals twigmax(t).
+ uint s = hastwig(i, b) ? twigoff(i, b) : 0;
+ t = Tbranch_twigs(t) + s;
+ }
+ // Do the keys differ, and if so, where?
+ uint off, xor, shf;
+ const char *tkey = Tleaf_key(t);
+ for(off = 0; off <= len; off++){+ xor = (byte)key[off] ^ (byte)tkey[off];
+ if(xor != 0)
+ goto newkey;
+ }
+ Tset_val(t, val);
+ return tbl;
+newkey:; // We have the branch's byte index; what is its chunk index?
+ uint bit = off * 8 + __builtin_clz(xor) + 8 - sizeof(uint) * 8;
+ uint qo = bit / 5;
+ off = qo * 5 / 8;
+ shf = qo * 5 % 8;
+ // re-index keys with adjusted offset
+ Tbitmap nb = 1U << knybble(key,off,shf);
+ Tbitmap tb = 1U << knybble(tkey,off,shf);
+ // Prepare the new leaf.
+ Trie nt;
+ Tset_key(&nt, key);
+ Tset_val(&nt, val);
+ // Find where to insert a branch or grow an existing branch.
+ t = tbl;
+ Tindex i;
+ while(isbranch(t)){+ __builtin_prefetch(t->ptr);
+ i = t->index;
+ if(off == Tindex_offset(i) && shf == Tindex_shift(i))
+ goto growbranch;
+ if(off == Tindex_offset(i) && shf < Tindex_shift(i))
+ goto newbranch;
+ if(off < Tindex_offset(i))
+ goto newbranch;
+ Tbitmap b = twigbit(i, key, len);
+ assert(hastwig(i, b));
+ t = Tbranch_twigs(t) + twigoff(i, b);
+ }
+newbranch:;
+ Trie *twigs = MEM_ALLOC(sizeof(Trie) * 2);
+ if(twigs == nil)
+ return nil;
+ i = Tindex_new(shf, off, nb | tb);
+ twigs[twigoff(i, nb)] = nt;
+ twigs[twigoff(i, tb)] = *t;
+ Tset_twigs(t, twigs);
+ Tset_index(t, i);
+ return tbl;
+growbranch:
+ assert(!hastwig(i, nb));
+ uint s, m; TWIGOFFMAX(s, m, i, nb);
+ twigs = MEM_REALLOC(Tbranch_twigs(t), sizeof(Trie) * (m + 1));
+ if(twigs == nil)
+ return nil;
+ memmove(twigs+s+1, twigs+s, sizeof(Trie) * (m - s));
+ memmove(twigs+s, &nt, sizeof(Trie));
+ Tset_twigs(t, twigs);
+ Tset_index(t, Tbitmap_add(i, nb));
+ return tbl;
+}
--- /dev/null
+++ b/3rd/fn.h
@@ -1,0 +1,220 @@
+// fn.h: quintet bit popcount patricia tries, new version
+//
+// This version uses somewhat different terminology than older
+// variants. The location of a quintet in the key is now called its
+// "offset", and the whole word containing the offset, bitmap, and tag
+// bit is called the "index word" (by analogy with a database index).
+// The precise quintet location is represented as a byte offset and a
+// shift. Previously a flags field contained the isbranch tag and shift,
+// but these are now separate.
+//
+// Instead of trying to use bit fields, this code uses accessor
+// functions to split up a pair of words into their constituent parts.
+// This should improve portability to machines with varying endianness
+// and/or word size.
+//
+// Written by Tony Finch <dot@dotat.at>
+// You may do anything with this. It has no warranty.
+// <http://creativecommons.org/publicdomain/zero/1.0/>
+
+typedef unsigned char byte;
+typedef unsigned int uint;
+
+typedef uint32_t Tbitmap;
+typedef uint64_t Tindex;
+
+const char *dump_bitmap(Tbitmap w);
+
+#if defined(__plan9__)
+static inline uint
+popcount(Tbitmap w)
+{+ w -= (w >> 1) & 0x55555555;
+ w = (w & 0x33333333) + ((w >> 2) & 0x33333333);
+ w = (w + (w >> 4)) & 0x0F0F0F0F;
+ w = (w * 0x01010101) >> 24;
+ return(w);
+}
+#else
+#define popcount(w) __builtin_popcount(w)
+#endif
+
+typedef struct Tbl {+ Tindex index;
+ void *ptr;
+}Trie;
+
+// accessor functions, except for the index word
+
+#define Tset_field(cast, elem, type, field) \
+ static inline void \
+ Tset_##field(Trie *t, type field) \
+ { \+ t->elem = cast field; \
+ } \
+ struct dummy
+
+Tset_field((void *), ptr, Trie *, twigs);
+Tset_field((Tindex), index, Tindex, index);
+Tset_field((void *)(uint64_t), ptr, const char *, key);
+Tset_field((Tindex), index, void *, val);
+
+static inline bool Tindex_branch(Tindex i);
+
+static inline bool isbranch(Trie *t)
+{+ return(Tindex_branch(t->index));
+}
+
+#ifdef WITH_EXTRA_CHECKS
+#define Tbranch(t) assert(isbranch(t))
+#define Tleaf(t) assert(!isbranch(t))
+#else
+#define Tbranch(t)
+#define Tleaf(t)
+#endif
+
+#define Tcheck_get(type, tag, field, expr) \
+ static inline type \
+ tag##_##field(Trie *t) \
+ { \+ tag(t); \
+ return expr; \
+ } \
+ struct dummy
+
+Tcheck_get(Trie *, Tbranch, twigs, t->ptr);
+Tcheck_get(const char *, Tleaf, key, t->ptr);
+Tcheck_get(void *, Tleaf, val, (void*)t->index);
+
+// index word layout
+
+#define Tix_width_branch 1
+#define Tix_width_shift 3
+#define Tix_width_offset 28
+#define Tix_width_bitmap 32
+
+#define Tix_base_branch 0
+#define Tix_base_shift (Tix_base_branch + Tix_width_branch)
+#define Tix_base_offset (Tix_base_shift + Tix_width_shift)
+#define Tix_base_bitmap (Tix_base_offset + Tix_width_offset)
+
+#define Tix_place(field) ((Tindex)(field) << Tix_base_##field)
+
+#define Tix_mask(field) ((1ULL << Tix_width_##field) - 1ULL)
+
+#define Tunmask(field,index) ((uint)(((index) >> Tix_base_##field) \
+ & Tix_mask(field)))
+
+#define Tmaxlen Tix_mask(offset)
+
+// index word accessor functions
+
+#define Tindex_get(type, field) \
+ static inline type \
+ Tindex_##field(Tindex i) \
+ { \+ return(Tunmask(field, i)); \
+ } \
+ struct dummy
+
+Tindex_get(bool, branch);
+Tindex_get(uint, shift);
+Tindex_get(uint, offset);
+Tindex_get(Tbitmap, bitmap);
+
+static inline Tindex
+Tindex_new(uint shift, uint offset, Tbitmap bitmap)
+{+ uint branch = 1;
+ return( Tix_place(branch) |
+ Tix_place(shift) |
+ Tix_place(offset) |
+ Tix_place(bitmap) );
+}
+
+static inline Tindex
+Tbitmap_add(Tindex i, Tbitmap bitmap)
+{+ return(i | Tix_place(bitmap));
+}
+
+static inline Tindex
+Tbitmap_del(Tindex i, Tbitmap bitmap)
+{+ return(i & ~Tix_place(bitmap));
+}
+
+// sanity checks!
+
+#if !defined(__plan9__)
+#if !defined(static_assert)
+#define static_assert_cat(a,b) a##b
+#define static_assert_name(line) static_assert_cat(static_assert_,line)
+#define static_assert(must_be_true,message) \
+ static const void *static_assert_name(__LINE__) \
+ [must_be_true ? 2 : -1] = { \+ message, \
+ &static_assert_name(__LINE__) }
+#endif
+
+static_assert(Tix_base_bitmap + Tix_width_bitmap == 64,
+ "index fields must fill a 64 bit word");
+
+static_assert(Tunmask(bitmap,0x1234567800000000ULL) == 0x12345678,
+ "extracting the bitmap works");
+
+static_assert(Tunmask(offset,0x0420ULL) == 0x42,
+ "extracting the offset works");
+
+static_assert(Tunmask(shift,0xFEDCBAULL) == 5,
+ "extracting the shift works");
+
+// ..key[o%5==0].. ..key[o%5==1].. ..key[o%5==2].. ..key[o%5==3].. ..key[o%5==4]..
+// | | | | | |
+// 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+// | | | | | | | | |
+// shift=0 shift=5 shift=2 shift=7 shift=4 shift=1 shift=6 shift=3
+#endif
+
+static inline byte
+knybble(const char *key, uint off, uint shift)
+{+ uint word = key[off]<<8;
+ if(word)
+ word |= key[off+1];
+ uint right = 16 - 5 - shift;
+ return (word >> right) & 0x1FU;
+}
+
+static inline byte
+nibble(Tindex i, const char *key, size_t len)
+{+ uint off = Tindex_offset(i);
+ if(off >= len)
+ return(0);
+ else return knybble(key, off, Tindex_shift(i));
+}
+
+static inline Tbitmap
+twigbit(Tindex i, const char *key, size_t len)
+{+ return(1U << nibble(i, key, len));
+}
+
+static inline bool
+hastwig(Tindex i, Tbitmap bit)
+{+ return Tindex_bitmap(i) & bit;
+}
+
+static inline uint
+twigoff(Tindex i, Tbitmap bit)
+{+ return popcount(Tindex_bitmap(i) & (bit-1));
+}
+
+#define TWIGOFFMAX(off, max, i, b) do{ \+ off = twigoff(i, b); \
+ max = popcount(Tindex_bitmap(i)); \
+ }while(0)
--- /dev/null
+++ b/3rd/tbl.c
@@ -1,0 +1,57 @@
+// Tbl.c: simpler wrappers for core table functions
+//
+// Written by Tony Finch <dot@dotat.at>
+// You may do anything with this. It has no warranty.
+// <http://creativecommons.org/publicdomain/zero/1.0/>
+
+#include "platform.h"
+#include "tbl.h"
+
+void *
+Tgetl(Tbl *tbl, const char *key, size_t len)
+{+ const char *rkey = nil;
+ void *rval = nil;
+ return Tgetkv(tbl, key, len, &rkey, &rval) ? rval : nil;
+}
+
+void *
+Tget(Tbl *tbl, const char *key)
+{+ return Tgetl(tbl, key, strlen(key));
+}
+
+Tbl *
+Tset(Tbl *tbl, const char *key, void *value)
+{+ return Tsetl(tbl, key, strlen(key), value);
+}
+
+Tbl *
+Tdell(Tbl *tbl, const char *key, size_t len)
+{+ const char *rkey = nil;
+ void *rval = nil;
+ return Tdelkv(tbl, key, len, &rkey, &rval);
+}
+
+Tbl *
+Tdel(Tbl *tbl, const char *key)
+{+ return Tdell(tbl, key, strlen(key));
+}
+
+bool
+Tnext(Tbl *tbl, const char **pkey, void **pvalue)
+{+ size_t len = *pkey == nil ? 0 : strlen(*pkey);
+ return Tnextl(tbl, pkey, &len, pvalue);
+}
+
+const char *
+Tnxt(Tbl *tbl, const char *key)
+{+ void *value = nil;
+ Tnext(tbl, &key, &value);
+ return key;
+}
--- /dev/null
+++ b/3rd/tbl.h
@@ -1,0 +1,56 @@
+// Tbl.h: an abstract API for tables with string keys.
+//
+// Written by Tony Finch <dot@dotat.at>
+// You may do anything with this. It has no warranty.
+// <http://creativecommons.org/publicdomain/zero/1.0/>
+
+#pragma once
+
+// A table is represented by a pointer to this incomplete struct type.
+// You initialize an empty table by setting the pointer to NULL.
+//
+typedef struct Tbl Tbl;
+#if defined(__plan9__)
+#pragma incomplete Tbl
+#endif
+
+// Get the value associated with a key.
+// Returns NULL if the key is not in the Table.
+//
+void *Tgetl(Tbl *tbl, const char *key, size_t klen);
+void *Tget(Tbl *tbl, const char *key);
+
+// Returns false if the key is not found, otherwise returns true and
+// sets *rkey and *rval to the table's key and value pointers.
+//
+bool Tgetkv(Tbl *tbl, const char *key, size_t klen, const char **rkey, void **rval);
+
+// Associate a key with a value in a table. Returns a new pointer to
+// the modified table. If there is an error it sets errno and returns
+// NULL. To delete a key, set its value to NULL. When the last key is
+// deleted, Tset() returns NULL without setting errno. The key and
+// value are borrowed not copied.
+//
+// Errors:
+// EINVAL - value pointer is not word-aligned
+// ENOMEM - allocation failed
+//
+Tbl *Tsetl(Tbl *tbl, const char *key, size_t klen, void *value);
+Tbl *Tset(Tbl *tbl, const char *key, void *value);
+Tbl *Tdell(Tbl *tbl, const char *key, size_t klen);
+Tbl *Tdel(Tbl *tbl, const char *key);
+
+// Deletes an entry from the table as above, and sets *rkey and *rval
+// to the removed key and value pointers.
+//
+Tbl *Tdelkv(Tbl *tbl, const char *key, size_t klen, const char **rkey, void **rval);
+
+// Find the next item in the table. The p... arguments are in/out
+// parameters. To find the first key, pass *pkey=NULL and *pklen=0.
+// For subsequent keys, *pkey must be present in the table and is
+// updated to the lexicographically following key. Returns false or
+// NULL when there are no more keys.
+//
+bool Tnextl(Tbl *tbl, const char **pkey, size_t *pklen, void **pvalue);
+bool Tnext(Tbl *tbl, const char **pkey, void **pvalue);
+const char *Tnxt(Tbl *tbl, const char *key);
--- a/LICENSE
+++ b/LICENSE
@@ -2,6 +2,8 @@
SpookyHash implementation is under CC0 license.
+QP tries (3rd/fn.[ch] 3rd/tbl.[ch]) is under CC0 license.
+
Copyright (c) 2008 Jeff Bezanson
All rights reserved.
--- a/builtins.c
+++ b/builtins.c
@@ -184,17 +184,6 @@
return FL_void;
}
-static void
-global_env_list(symbol_t *root, value_t *pv)
-{- while(root != nil){- if(root->name[0] != ':' && (root->binding != UNBOUND))
- *pv = fl_cons(tagptr(root, TAG_SYM), *pv);
- global_env_list(root->left, pv);
- root = root->right;
- }
-}
-
BUILTIN("environment", environment) {USED(args);
@@ -201,7 +190,12 @@
argcount(nargs, 0);
value_t lst = FL_nil;
fl_gc_handle(&lst);
- global_env_list(FL(symtab), &lst);
+ const char *k = nil;
+ symbol_t *v;
+ while(Tnext(FL(symtab), &k, (void**)&v)){+ if(v->binding != UNBOUND)
+ lst = fl_cons(tagptr(v, TAG_SYM), lst);
+ }
fl_free_gc_handles(1);
return lst;
}
--- a/flisp.c
+++ b/flisp.c
@@ -197,24 +197,17 @@
return sym;
}
-static symbol_t **
-symtab_lookup(symbol_t **ptree, const char *str)
-{- int x;
- while(*ptree != nil && (x = strcmp(str, (*ptree)->name)) != 0)
- ptree = x < 0 ? &(*ptree)->left : &(*ptree)->right;
- return ptree;
-}
-
value_t
symbol(const char *str, bool copy)
{- symbol_t **pnode;
-
- pnode = symtab_lookup(&FL(symtab), str);
- if(*pnode == nil)
- *pnode = mk_symbol(str, copy);
- return tagptr(*pnode, TAG_SYM);
+ int len = strlen(str);
+ symbol_t *v;
+ const char *k;
+ if(!Tgetkv(FL(symtab), str, len, &k, (void**)&v)){+ v = mk_symbol(str, copy);
+ FL(symtab) = Tsetl(FL(symtab), v->name, len, v);
+ }
+ return tagptr(v, TAG_SYM);
}
BUILTIN("gensym", gensym)@@ -434,13 +427,13 @@
}
static void
-trace_globals(symbol_t *root)
+trace_globals(void)
{- while(root != nil){- if(root->binding != UNBOUND)
- root->binding = relocate(root->binding);
- trace_globals(root->left);
- root = root->right;
+ const char *k = nil;
+ symbol_t *v;
+ while(Tnext(FL(symtab), &k, (void**)&v)){+ if(v->binding != UNBOUND)
+ v->binding = relocate(v->binding);
}
}
@@ -475,7 +468,7 @@
}
for(i = 0; i < FL(ngchandles); i++)
*FL(gchandles)[i] = relocate(*FL(gchandles)[i]);
- trace_globals(FL(symtab));
+ trace_globals();
relocate_typetable();
rs = FL(readstate);
while(rs){--- a/flisp.h
+++ b/flisp.h
@@ -3,6 +3,7 @@
#include "platform.h"
#include "utf8.h"
#include "ios.h"
+#include "tbl.h"
#include "bitvector.h"
#include "htableh.inc"
HTPROT(ptrhash)
@@ -57,11 +58,9 @@
}cons_t;
typedef struct _symbol_t {- fltype_t *type;
const char *name;
- struct _symbol_t *left;
- struct _symbol_t *right;
value_t binding; // global value binding
+ fltype_t *type;
uint32_t hash;
uint8_t numtype;
uint8_t size;
@@ -365,7 +364,7 @@
uint32_t ngchandles;
fl_readstate_t *readstate;
- symbol_t *symtab;
+ Tbl *symtab;
// saved execution state for an unwind target
fl_exception_context_t *exctx;
--- a/meson.build
+++ b/meson.build
@@ -33,8 +33,10 @@
]
src = [
+ '3rd/fn.c',
'3rd/mt19937-64.c',
'3rd/spooky.c',
+ '3rd/tbl.c',
'bitvector.c',
'builtins.c',
'cvalues.c',
--- a/mkfile
+++ b/mkfile
@@ -12,9 +12,11 @@
plan9/platform.h\
OFILES=\
+ 3rd/fn.$O\
3rd/mt19937-64.$O\
- 3rd/wcwidth.$O\
3rd/spooky.$O\
+ 3rd/tbl.$O\
+ 3rd/wcwidth.$O\
bitvector.$O\
builtins.$O\
cvalues.$O\
@@ -30,6 +32,7 @@
main_plan9.$O\
opcodes.$O\
operators.$O\
+ plan9_builtins`{test -f plan9_builtins_$objtype.s && echo -n _$objtype}.$O\print.$O\
ptrhash.$O\
random.$O\
--- a/plan9/platform.h
+++ b/plan9/platform.h
@@ -9,8 +9,10 @@
#endif
#define __os_name__ "plan9"
-
#define __thread
+
+#define __builtin_prefetch(x)
+int __builtin_clz(unsigned int x);
#define MEM_ALLOC(n) malloc(n)
#define MEM_REALLOC(p, n) realloc((p), (n))
--- /dev/null
+++ b/plan9_builtins.c
@@ -1,0 +1,11 @@
+#include "platform.h"
+
+int
+__builtin_clz(unsigned int x)
+{+ unsigned int r;
+ if(x == 0)
+ return 32;
+ for(r = 0; (x & (1UL<<31)) == 0; x <<= 1, r++);
+ return r;
+}
--- /dev/null
+++ b/plan9_builtins_amd64.s
@@ -1,0 +1,4 @@
+TEXT __builtin_clz(SB),1,$0
+ BYTE $0x0F; BYTE $0xBD; BYTE $0xC5 /* BSRL RARG, AX */
+ XORL $31, AX
+ RET
--- /dev/null
+++ b/plan9_builtins_arm64.s
@@ -1,0 +1,3 @@
+TEXT __builtin_clz(SB),1,$0
+ CLZW R0, R0
+ RETURN