Solutions and hints (Digital Systems)

Lab one

The tasks in this lab are to try various small pieces of assembly code, starting with individual instructions, and building up to bigger subroutines containing loops. The suggestions are to implement a faster version of integer multiplication (pretending the chip has no multiply instruction), or to implement a simple or a fast integer division routine.

For the simplest example, just take the supplied file add.s and substitute for the instruction

adds r0, r0, r1

the alternative instruction

subs r0, r0, r1

Then use make subs.hex to build, and copy the resulting file subs.hex to the micro:bit.

A simple multiplication routine is included with the lab materials as mul1.s, but a better one (my file mul2.s) is as follows.

@ Multiplication by halving
@ Variables x = r0, y = r1, z = r2
@ Invariant a * b = x * y + z

    movs r2, #0
    b test
again:
    lsrs r0, r0, #1
    bcc even
    adds r2, r2, r1
even:
    lsls r1, r1, #1
test:
    cmp r0, #0
    bne again
    movs r0, r2             @ return z;

Here's a simple implementation of unsigned integer division (div1.s).

@ Division by repeated subtraction

    movs r2, #0             @ q = 0;
loop:
    cmp r0, r1              @ while (r >= b)
    blo done                @ Note unsigned comparison
    adds r2, r2, #1         @   q = q+1;
    subs r0, r0, r1         @   r = r-b;
    b loop
done:
    movs r0, r2

A better implementation uses binary long division (div2.s).

@ Long division

    push {r4, lr}
    movs r4, #0             @ j = 0;
    movs r2, r1

double:                     @ while ((b << j) < 2^32) j++;
    adds r4, r4, #1
    lsls r2, r2, #1
    bcc double

    movs r3, #0             @ q = 0;
loop:                       @ do {
    subs r4, r4, #1         @   j--;
    lsls r3, r3, #1         @   q <<= 1;
    movs r2, r1
    lsls r2, r4             @   b << j in r2
    cmp r0, r2              @   if (r >= (b << j)) {
    blo skip
    adds r3, r3, #1         @     q++;
    subs r0, r0, r2         @     r -= (b << j);
skip:                       @   }
    cmp r4, #0              @ } while (j != 0)
    bne loop

    movs r0, r3
    pop {r4, pc}

Note that signed integer multiplication and division are boring: the best method is to make some or all of the arguments positive, use unsigned multiplication or division, then fix up the sign of the result.

Lab two

The main point here is to have some fun [messing about] with the LED matrix. It's worth actually doing the exercise of increasing the delay to see at what point the flickering becomes noticeable.

The hollow heart pattern is defined by these constants:

static const unsigned empty[] = {
    0x3af0, 0x5e40, 0x9560
};

Experts on C will want to automate the process of deriving the hex constants. Here's an appropriate definition of the macro PIC and a clearer definition of the bitmap.

#define ROW(r, c1, c2, c3, c4, c5, c6, c7, c8, c9) \
    (r | !c1 * BIT(4) | !c2 * BIT(5) | !c3 * BIT(6) | !c4 * BIT(7) 
     | !c5 * BIT(8) | !c6 * BIT(9) | !c7 * BIT(10) | !c8 * BIT(11) \
     | !c9 * BIT(12))

#define PIC(x11, x24, x12, x25, x13, \
            x34, x35, x36, x37, x38, \
            x22, x19, x23, x39, x21, \
            x18, x17, x16, x15, x14, \
            x33, x27, x31, x26, x32) \
    ROW(0x2000, x11, x12, x13, x14, x15, x16, x17, x18, x19),   \
    ROW(0x4000, x21, x22, x23, x24, x25, x26, x27, 0, 0),    \
    ROW(0x8000, x31, x32, x33, x34, x35, x36, x37, x38, x39)

static const unsigned empty[] = {
    PIC(0,1,0,1,0,
        1,0,1,0,1,
        1,0,0,0,1,
        0,1,0,1,0,
        0,0,1,0,0)
};

To make the display respond to the buttons, we need to look at appropriate bits read from GPIO_IN in the main loop.

void init(void) {
    unsigned const *pic1, *pic2;

    GPIO_DIR = 0xfff0;
    GPIO_PINCNF[BUTTON_A] = 0;
    GPIO_PINCNF[BUTTON_B] = 0;

    while (1) {
        unsigned x = GPIO_IN;
        if ((x & BIT(BUTTON_A)) == 0 || (x & BIT(BUTTON_B)) == 0) {
            pic1 = empty; pic2 = heart;
        } else {
            pic1 = heart; pic2 = small;
        }

        frame(pic1, 70);
        frame(pic2, 10);
        frame(pic1, 10);
        frame(pic2, 10);
    }
}

Many alternatives are possible, and exploration is encouraged.

Lab three

Random number generator

Here's code to drive the random number generator.

#define NRAND 64

/* A stack (!) of waiting random bytes */
static volatile unsigned char randoms[NRAND];
static volatile unsigned nrand = 0;

void rng_init(void) {
    SET_BIT(RNG_CONFIG, RNG_DERCEN); // Correct for bias
    RNG_VALRDY = 0;
    RNG_START = 1;

    RNG_INTENSET = BIT(RNG_INT_VALRDY);
    set_priority(RNG_IRQ, 3);
    enable_irq(RNG_IRQ);
}

void rng_handler(void) {
    unsigned char val;

    if (RNG_VALRDY) {
        val = RNG_VALUE;
        RNG_VALRDY = 0;
        if (nrand < NRAND)
            randoms[nrand++] = val;
    }
}

unsigned char random_byte(void) {
    unsigned char val;

    while (nrand == 0) pause();

    intr_disable();
    val = randoms[--nrand];
    intr_enable();

    return val;
}

Lab four

Randomising race

The race example is unpredictable a priori, but because the UART clock is derived from the same source as the processor clock, there is no timing jitter and the program produces the same values each time. We can introduce a random element by including a driver for the hardware random number generator. At least if we put it in 'bias correction' mode, the time to produce a random byte is itself random, so interrupts arrive at random times. We don't even have to fetch the random values! Here's a suitable driver, depending on an up-to-date copy of hardware.h.

void rng_task(int n) {
    message m;

    SET_BIT(RNG_CONFIG, RNG_DERCEN); // Correct for bias
    RNG_VALRDY = 0;
    RNG_START = 1;

    RNG_INTENSET = BIT(RNG_INT_VALRDY);
    set_priority(RNG_IRQ, 3);
    enable_irq(RNG_IRQ);
    connect(RNG_IRQ);

    while (1) {
        receive(ANY, &m);

        switch (m.m_type) {
        case INTERRUPT:
            RNG_VALRDY = 0;
            clear_pending(RNG_IRQ);
            enable_irq(RNG_IRQ);
            break;

        default:
            panic("You're kidding me");
        }
    }
}

Insert this line in the main program to start the process, and watch the results in multiple runs.

start(USER+2, "Random", rng_task, 0, STACK);

(Note added later: if we disable bias-correction mode, there is still some randomness of timing, but the interrupt rate from the RNG is now high enough that the program does not get so far in counting before all ten values are printed.)