### Simple example hash table in 20 lines of assembly and 14 instructions.

### See intcount.c for the antecedent, and intcountst.c for the
### harness.  This code just maintains parallel arrays of (32-bit
### integer) keys and values; invoking `inc` inserts its argument into
### the hash table as a key, if necessary, and increments its value.
### Later you can loop over the table.  The hash function here is just
### the low bits of the key.

### It isn’t PIE-compatible, I guess because this directly indexes
### static arrays in assembly instructions (rather than using
### RIP-relative addresses?).

        .globl inc, kj, vj
        .set nb, 1024           # Number of buckets (power of 2).

        .bss
kj:     .fill nb * 4            # Keys k0, k1, ... k_{nb-1}.
vj:     .fill nb * 4            # Values (counts).

        .text
inc:    xor %eax, %eax          # Initialize loop counter to 0.
    1:  lea (%rdi, %rax), %ecx  # Add counter to key to upsert.
	and $(nb-1), %ecx       # Restrict to valid bucket indices.
        cmp %edi, kj(,%rcx,4)   # Is the key already there?
        je 2f                   # If so, just increment.
        cmp $0, kj(,%rcx,4)     # If not, is the slot empty?
        je 3f                   # If empty, insert.
        inc %eax                # Otherwise, increment loop counter.
        cmp $nb, %eax           # Tried all buckets?
        jne 1b                  # Restart loop if not.
        call abort              # Table is full, can’t insert, die.

    3:  mov %edi, kj(,%rcx,4)   # put key in empty slot
    2:  incw vj(,%rcx,4)        # increment occurrence count
	ret                     # done!