Dynamic Mutable Bit Slices

Designing a brand new CPU is not only about opcodes, it is also about its internal workings. One such internal thing is how certain multi-bit values can be split into different single and multi-bit slices.

To simplify the main task, we will assume we have two helper procedures at our disposal: bits-split and bits-join. The former gets a single multi-bit value and arbitrary number of bit-lengths and returns the value split into individual slices of given lengths:

(bits-split #x123 8 4)
#x12
#x3

The order of bit-lenghts is big-endian to follow the human-readable notation of the value in the first argument. The latter procedure takes a list of two-element lists representing values and their bit-widths and it joins it using the same order into single wider value:

(bits-join '(#x12 8) '(#x3 4))
#x123

These procedures are easy to implement and therefore we leave the this exercise to the reader. Let's have a look at the more interesting part of this task. What if we wanted to take bit slices from arbitrary number of source values? Something akin to the following:

(define-bits (msb 1) (middle -6) (lsb 1) #:from (high-nibble 4) (low-nibble 4))

Arbitrary number of new bindings on the left-hand side and arbitrary number of values on the right-hand side seem like a good design choice. Also using negative bit lengths to specify sign extension for possibly negative integers feels very natural.

The goal is to make the left-hand side bindings dynamic. Any change to the bindings used as right-hand side values should be immediately visible in the newly created bindings.

We start with a syntax class for the bit slices definitions. It is always an identifier and an integer as a single S-expression.

(begin-for-syntax
  (define-syntax-class bitdef
    #:attributes (id bitlen sbitlen)
    (pattern (id:id bitlendef:integer)
             #:do ((define bitlenum (syntax->datum #'bitlendef))
                   (define bitlen (abs bitlenum)))
             #:fail-when (zero? bitlenum) "cannot have zero bitlen"
             #:attr bitlen (datum->syntax #'id bitlen)
             #:attr sbitlen #'bitlendef)))

This syntax class provides the following attributes id as the identifier, bitlen as the absolute value of given bit-length and sbitlen containing the bit-length value as-is. This allows for defining a relatively simple implementation of aforementioned specification:

(define-syntax (define-bits stx)
  (syntax-parse stx
    ((_ lb:bitdef ... #:from rb:bitdef ...)
     #'(begin
         (define-syntax (lb.id sty)
           (syntax-parse sty
             (_
              #'(let-values (((lb.id ...)
                              (bits-split
                               (bits-join (list rb.id rb.bitlen) ...)
                               lb.sbitlen ...)))
                  lb.id)))) ...))))

This syntax creates identifier transformers for all left-hand side identifiers which dynamically resolve to composed bits-join/bits-split evaluation.

The usage is pretty straightforward:

> (define high-nibble 15)
> (define low-nibble 0)
> (define-bits (msb 1) (middle -6) (lsb 1) #:from (high-nibble 4) (low-nibble 4))
> msb
1
> middle
-8
> low-nibble
0

This was rather easy, but what if we would like to support mutations of left-hand side bindings that would be immediately visible in the values of the right-hand side bindings? Identifier transformers are not powerful enough for this task. For this, we need set! transformers which are capable of both redirecting set! usage and lone identifier usage. It makes the syntax a bit more complex, however way more powerful:

(define-syntax (define-bits stx)
  (syntax-parse stx
    ((_ lb:bitdef ... #:from rb:bitdef ...)
     #:with (rbid ...) (generate-temporaries #'(rb.id ...))
     #'(begin
         (define-syntax lb.id
           (make-set!-transformer
            (lambda (sty)
              (syntax-parse sty
                ((set! _ v)
                 #'(let ((lb.id lb.id) ...)
                     (set! lb.id v)
                     (let-values (((rbid ...)
                                   (bits-split
                                    (bits-join (list lb.id lb.bitlen) ...)
                                    rb.sbitlen ...)))
                       (set! rb.id rbid) ...)))
                (_
                 #'(let-values (((lb.id ...)
                                 (bits-split
                                  (bits-join (list rb.id rb.bitlen) ...)
                                  lb.sbitlen ...)))
                     lb.id)))))) ...))))

Although it is a bit tougher than the read-only version, however it works as we can see:

> (define high-nibble 15)
> (define low-nibble 0)
> (define-bits (msb 1) (middle -6) (lsb 1) #:from (high-nibble 4) (low-nibble 4))
> (set! lsb 1)
> low-nibble
1
> (set! msb 0)
> high-nibble
7
> middle
24

This was quite a blast, wasn't it? This approach simplifies many tasks in CPU emulation and the programmer can focus on important features and not repretitive tasks like bit extractions and adjoining.

Hope you like this deeper dive into CPU design-related tasks and see ya next time for more!