Bitfield

1How It Works

The bitfield library provides a simple, efficient mechanism for storing multiple discrete states into a single non-negative integer. Its main API is the macro define-bitfield that defines a certain kind of bitfield consisting of a constructor, a function for creating modified clones, and one reader function for each slot.

The following example illustrates these features for the case of defining cards from a standard 52 card deck:

(define-bitfield card
  (suit (member clubs diamonds hearts spades))
  (rank (member ace 2 3 4 5 6 7 8 9 10 jack queen king)))

(defparameter *card* (make-card :rank 'ace :suit 'spades))

(values
 ,*card*
 (card-suit *card*)
 (card-rank *card*))
;; => 3
;; => spades
;; => ace

(defparameter *card* (clone-card *card* :rank 'queen))

(values
 ,*card*
 (card-suit *card*)
 (card-rank *card*))
;; => 91
;; => spades
;; => queen

2Kinds of Bitfield Slots

Each bitfield slot is described by a list whose first element is the slot name and whose second element is a slot specifier. The remaining entries form a plist that may supply additional keyword arguments. The bitfield slot specifier is then parsed using an extensible protocol to obtain a bitfield slot class, the number of distinct states of that slot, and a (possibly empty) plist of additional keyword arguments. These properties are then used to create a bitfield slot instance. In the end, the properties of the bitfield slot instances of all slots constitute the behavior of the resulting bitfield.

The different kinds of bitfield slots are illustrated in this second example:

(define-bitfield examplebits
  (a boolean)
  (b (signed-byte 2))
  (c (unsigned-byte 3) :initform 1)
  (d (integer -100 100))
  (e (member foo bar baz)))

(defun examplebits-values (examplebits)
  (list
   (examplebits-a examplebits)
   (examplebits-b examplebits)
   (examplebits-c examplebits)
   (examplebits-d examplebits)
   (examplebits-e examplebits)))

(defparameter *default* (make-examplebits))

(examplebits-values *default*)
;; => (nil 0 1 -100 foo)

(defparameter *explicit* (make-examplebits :a t :b -1 :c 7 :d 42 :e 'baz))

(examplebits-values *explicit*)
;; => (t -1 7 42 baz)

(defparameter *clone* (clone-examplebits *explicit* :a nil :b -1 :c 2 :d -12 :e 'bar))

(examplebits-values *clone*)
;; => (nil -1 2 -12 bar)

This library comes equipped with parsers for boolean, bit, (unsigned-byte N), (signed-byte N), (integer A B), and (member OBJ1 ... OBJN) slot specifiers. New kinds of slots and slot specifiers can be defined by extending the existing protocol functions, as shown in the next section.

3Custom Bitfield Slots

In the next example, we show how the protocol can be augmented by introducing both a bitfield slot class and the corresponding atomic bitfield slot specifier parser for an ascii slot.

(defclass bitfield-ascii-slot (bitfield-slot)
  ())

(defmethod bitfield-slot-pack ((slot bitfield-ascii-slot) value-form)
  `(char-code ,value-form))

(defmethod bitfield-slot-unpack ((slot bitfield-ascii-slot) value-form)
  `(code-char ,value-form))

(defmethod parse-atomic-bitfield-slot-specifier
    ((specifier (eql 'ascii)) &key (initform #\?))
  (values 'bitfield-ascii-slot
          128
          `(:initform ,initform)))

(define-bitfield four-letter-word
  (first-letter ascii)
  (second-letter ascii)
  (third-letter ascii)
  (fourth-letter ascii))

(defun four-letter-word-string (four-letter-word)
  (format nil "~C~C~C~C"
          (four-letter-word-first-letter four-letter-word)
          (four-letter-word-second-letter four-letter-word)
          (four-letter-word-third-letter four-letter-word)
          (four-letter-word-fourth-letter four-letter-word)))

(four-letter-word-string
 (make-four-letter-word))
;; => "????"

(four-letter-word-string
 (make-four-letter-word
  :fourth-letter #\n
  :second-letter #\v
  :first-letter #\o
  :third-letter #\e))
;; => "oven"

4Performance

Bitfields are defined or redefined exclusively via keyword arguments. Thanks to inlining, this doesn't affect performance at all. In this example, we inspect the assembler code that is generated for manipulations of a particular bitfield. The examples are shown for SBCL.

(define-bitfield hero
  (dex (integer 1 24))
  (str (integer 1 24))
  (int (integer 1 24)))

Firstly, we look at the code that is generated for a bitfield whose arguments are constant:

(defun make-archmage ()
  (make-hero :dex 10 :str 8 :int 24))

(disassemble #'make-archmage)
; disassembly for make-archmage
; Size: 21 bytes. Origin: #x52E2147C                          ; make-archmage
; 7C:       498B4510         mov RAX, [R13+16]                ; thread.binding-stack-pointer
; 80:       488945F8         mov [RBP-8], RAX
; 84:       BAD2B90000       mov EDX, 47570
; 89:       488BE5           mov RSP, RBP
; 8C:       F8               clc
; 8D:       5D               pop RBP
; 8E:       C3               ret
; 8F:       CC10             int3 16                          ; Invalid argument count trap

We see that the entire constructor has been folded into a single constant, 47570, which is the value of an Archmage shifted left by one bit. The shift is due to SBCL's internal representation of fixnums.

A more interesting example is when we consider constructors where not all arguments are constant. Here, we define a constructor for a wizard where we supply the int attribute as an argument:

(defun make-wizard (int)
  (make-hero :dex 10 :str 8 :int int))

(disassemble #'make-wizard)
; disassembly for make-wizard
; Size: 53 bytes. Origin: #x52E21510                          ; make-wizard
; 10:       498B5D10         mov RBX, [R13+16]                ; thread.binding-stack-pointer
; 14:       48895DF8         mov [RBP-8], RBX
; 18:       4885C0           test RAX, RAX
; 1B:       7422             jeq L0
; 1D:       A801             test AL, 1
; 1F:       751E             jne L0
; 21:       4883F830         cmp RAX, 48
; 25:       7718             jnbe L0
; 27:       488BD0           mov RDX, RAX
; 2A:       4883C2FE         add RDX, -2
; 2E:       48C1E20A         shl RDX, 10
; 32:       4881CAD2010000   or RDX, 466
; 39:       488BE5           mov RSP, RBP
; 3C:       F8               clc
; 3D:       5D               pop RBP
; 3E:       C3               ret
; 3F: L0:   CC1E             int3 30                          ; OBJECT-NOT-TYPE-ERROR
; 41:       00               byte #X00                        ; RAX
; 42:       23               byte #X23                        ; '(integer 1 24)
; 43:       CC10             int3 16                          ; Invalid argument count trap

The generated assembler code is slightly more complicated, but most of this is about checking that the int argument is actually a positive integer that is at most 24. If we strip the argument checking code, we end up with

; 27:       488BD0           mov RDX, RAX
; 2A:       4883C2FE         add RDX, -2
; 2E:       48C1E20A         shl RDX, 10
; 32:       4881CAD2010000   or RDX, 466
; 39:       488BE5           mov RSP, RBP
; 3C:       F8               clc
; 3D:       5D               pop RBP
; 3E:       C3               ret

We see that adding one variable argument to a bitfield constructor only costs one add instruction and one shl (left-shift) instruction.

The next example is about cloning bitfields. The next function takes a hero and returns a copy of that hero but with a slightly higher str attribute.

(defun go-to-gym (hero)
  (clone-hero hero :str (1+ (hero-str hero))))

If we disable argument checking (e.g., by declaring (safety 0)) we end up with the following sequence of instructions for our go-to-gym function:

; 12:       8BD8             mov EBX, EAX
; 14:       C1EB05           shr EBX, 5
; 17:       83E33E           and EBX, 62
; 1A:       4883C302         add RBX, 2
; 1E:       4883C302         add RBX, 2
; 22:       488BD0           mov RDX, RAX
; 25:       8BF2             mov ESI, EDX
; 27:       83E63E           and ESI, 62
; 2A:       4883C602         add RSI, 2
; 2E:       488BCA           mov RCX, RDX
; 31:       48C1F90A         sar RCX, 10
; 35:       4883E1FE         and RCX, -2
; 39:       4883C102         add RCX, 2
; 3D:       488D56FE         lea RDX, [RSI-2]
; 41:       4883C3FE         add RBX, -2
; 45:       48C1E305         shl RBX, 5
; 49:       4809DA           or RDX, RBX
; 4C:       4883C1FE         add RCX, -2
; 50:       48C1E10A         shl RCX, 10
; 54:       4809CA           or RDX, RCX
; 57:       488BE5           mov RSP, RBP
; 5A:       F8               clc
; 5B:       5D               pop RBP
; 5C:       C3               ret

We count one shr instruction, two shl instructions, six add instructions and two or instructions. Not bad for parsing three keyword arguments with complicated values. With argument checking, the code grows further by two conditional branches per argument. But with the branch prediction of a modern CPU, those branches will be almost for free.

5Conclusion

I wrote this library because I am tired of manually fiddling with bits just to save memory. Now I can finally pack plenty of information into a single machine word without worrying about correctness. I hope you find this useful, too.