Define and search a critbit tree

critbit.c

#include "critbit.h"
const node nodes[] = {

// read indices inside out
// for example, L(R(L(L(ROOT)))) is the root's left child's left child's
// right child's left child.
    [               ROOT        ] = {  6, 0 },
    [             R(ROOT)       ] = { 64, 1 },
    [             L(ROOT)       ] = {  5, 0 },
    [           R(L(ROOT))      ] = { 32, 1 },
    [           L(L(ROOT))      ] = {  4, 0 },
    [         R(L(L(ROOT)))     ] = { 16, 1 },
    [         L(L(L(ROOT)))     ] = {  3, 0 },
    [       R(L(L(L(ROOT))))    ] = {  8, 1 },
    [       L(L(L(L(ROOT))))    ] = {  2, 0 },
    [     L(L(L(L(L(ROOT)))))   ] = {  0, 0 },
    [   L(L(L(L(L(L(ROOT))))))  ] = {  2, 1 },
    [   R(L(L(L(L(L(ROOT))))))  ] = {  3, 1 },

    [     R(L(L(L(L(ROOT)))))   ] = {  1, 0 },
    [   R(R(L(L(L(L(ROOT))))))  ] = {  6, 1 },
    [   L(R(L(L(L(L(ROOT))))))  ] = {  0, 0 },
    [ L(L(R(L(L(L(L(ROOT))))))) ] = {  4, 1 },
    [ R(L(R(L(L(L(L(ROOT))))))) ] = {  5, 1 },
};

critbit.h

struct cbnode {
    unsigned char len:7; ///< also value
    unsigned char external:1;
};

#define ROOT 0
#define L(Node) (2 * (Node) + 1)
#define R(Node) (2 * (Node) + 2)

typedef struct cbnode node;

critbit_asm.S

#if __amd64__
#define NODES   %rdi    // argument 1, tree packed into array
#define I       %rcx    // index into nodes array
#define SEARCH  %esi    // argument 2, value to find in tree
#elif __i386__
#define NODES   %edx    // argument 1, tree packed into array
#define I       %ecx    // index into nodes array
#define STACK   %esp    // just to keep the names as macros
#define SEARCH  %ebp    // argument 2, value to find in tree
#endif

#define RESULT  %eax    // temp / return register

    .globl find_asm_in
    .balign 16                  // align function entry
find_asm_in:
#if __i386__
    mov     4(STACK), NODES
    mov     8(STACK), SEARCH
#endif
    xor     I, I
    movzb   (NODES), RESULT     // load first node
    btr     $7, RESULT          // check external bit and clear

    .balign 16                  // align loop entry
10: bt      RESULT, SEARCH      // test for match on this node
    lea     1(I,I,1), I         // if !match, next node is 2n + 1
    adc     $0, I               // if  match, next node is 2n + 2
    movzb   (NODES,I,1), RESULT // load next node
    btr     $7, RESULT          // check external bit and clear
    jnc     10b                 // loop again if internal node

    ret

critbit_c.c

#include "critbit.h"
int find_c_in(const node *nodes, int search)
{
    const node *n = nodes;

    while (!n->external) {
        if ((1ULL << n->len) & search)
            n = &nodes[R(n - nodes)];
        else
            n = &nodes[L(n - nodes)];
    }

    return n->len;
}