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
;; => queenEach 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.
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"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 trapThe 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 retWe 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 retWe 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.
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.