Original image by Riedsa, cropped.

Today’s puzzle is about stacks. The text of the puzzle is about a giant cargo crane moving crates around, but the implementation is going to focus on stack behaviours.

        JP      DAY05

The Z80 has a stack built right in to the processor’s instruction set. There’s a special stack pointer register and specific instructions to move values to and from the stack. But it’s always “the” stack, never “a” stack: if you want multiple stacks the CPU no longer has anything special to help you out.

The challenge posed on day 5 is to execute a series of movements from one stack to another. Each movement specifies the source, the destination, and a count. Star 1 moves one item at a time, while star 2 moves crates as a set - star 1 will reverse the order of a pile of crates moved in one step while star 2 will not.

The general problem will be to have a set of stacks of varying lengths, and to move bytes between them. A simple approach is to simply align each stack to some boundary, accepting a rather high overhead per stack. For my own input it’s more than enough to reserve 64 bytes for each stack and use up to 16 stacks, for 1KiB total space. To reduce overhead it would become necessary to move stacks around in memory, and it’s very likely the code required to do that would creep up to the same overhead as the stacks themselves.

        .align  64
STACKS: defs    16*64, " "
PTRS:   dw      STACKS+(64*0)
        dw      STACKS+(64*1)
        dw      STACKS+(64*2)
        dw      STACKS+(64*3)
        dw      STACKS+(64*4)
        dw      STACKS+(64*5)
        dw      STACKS+(64*6)
        dw      STACKS+(64*7)
        dw      STACKS+(64*8)
        dw      STACKS+(64*9)
        dw      STACKS+(64*10)
        dw      STACKS+(64*11)
        dw      STACKS+(64*12)
        dw      STACKS+(64*13)
        dw      STACKS+(64*14)
        dw      STACKS+(64*15)

As usual, I will be glib about error handling. My stacks must never overflow or underflow, else the program will simply go wrong. With that in mind, implementations to push and pop bytes are straightforward - so simple, in fact, that I will write macros for them rather than subroutines.

Note that my stacks will grow upwards, not downwards, with the stack pointer pointing to the next free byte and not the last written byte.

; IN:   HL      The stack pointer
;       A       The value to push
; OUT:  HL      The new stack pointer, incremented by one
.macro  spush
        ld      (hl), a
        inc     hl
.endm

; IN:   HL      the stack pointer
; OUT:  A       the popped value
;       HL      the new stack pointer, decremented by one
.macro  spop
        dec     hl
        ld      a, (hl)
.endm

The puzzle input consists of the initial configuration of stacked crates and the program to execute. As with most days I am not particularly interested in parsing the input, so instead I’ll store the initial configuration in a compact representation and the program slightly modified to be interpreted using macros.

;     [D]
; [N] [C]
; [Z] [M] [P]
; 1   2   3

.macro  move    count, from, to
        db      count
        dw      PTRS + (from-1)*2, PTRS + (to-1)*2
.endm

SAMPLE:
        db      "ZN", 0
        db      "MCD", 0
        db      "P", 0
        db      0

        move    1, 2, 1
        move    3, 1, 3
        move    2, 2, 1
        move    1, 1, 2
        db      0

The stacks will need to be initialised based on the input, which is a simple pair of nested loops. The working stacks grow downwards

        .block
; IN:   HL      the input
; OUT:  HL      the start of the movement program
;       stacks  initialised
@INIT:  push    af
        push    bc
        push    de

        ld      ix, PTRS
        ld      bc, 2

OUTER:  ld      e, (ix+0)
        ld      d, (ix+1)
        ld      a, (hl)
        inc     hl
        or      a
        jr      z, DONE
INNER:  ex      de, hl
        ld      (hl), a
        inc     hl
        ex      de, hl
        ld      a, (hl)
        inc     hl
        or      a
        jr      nz, INNER
        ld      (ix+0), e
        ld      (ix+1), d
        add     ix, bc
        jr      OUTER

DONE:   pop     de
        pop     bc
        pop     af
        ret
        .endblock

Let’s see what the first three stacks look like after executing this:

        ld      sp, $8000
        ld      hl, SAMPLE
        call    INIT
        halt

For star 1, executing a move means doing a set of pushes and pops. It turns out here that my macros aren’t as useful as I would have liked: I want to move data between (hl) and (de), not between (hl) and (hl).

        .block
; IN:   HL      source stack
;       DE      destination stack
;       B       movement size
; OUT:  HL      updated stack pointer
;       DE      updated stack pointer
;       crates moved from source to destination
@MOVE1: push    af
        push    bc

LOOP:   dec     hl
        ld      a, (hl)
        ld      (de), a
        inc     de
        djnz    LOOP

        pop     bc
        pop     af
        ret
        .endblock

For star 2 it’s a bulk copy:

        .block
; IN:   HL      source stack
;       DE      destination stack
;       B       movement size
; OUT:  HL      updated stack pointer
;       DE      updated stack pointer
;       crates moved from source to destination
@MOVE2: push    af
        push    bc

        ld      c, b
        ld      b, 0
        or      a       ; clear carry
        sbc     hl, bc
        push    hl
        ldir
        pop     hl

        pop     bc
        pop     af
        ret
        .endblock

Let’s try moving some stacks around:

        ld      sp, $8000
        ld      hl, SAMPLE
        call    INIT

        ; move ZN on top of P one by one, to get PNZ
        ld      hl, (PTRS+0)
        ld      de, (PTRS+4)
        ld      b, 2
        call    MOVE1
        ld      (PTRS+0), hl
        ld      (PTRS+4), de

        ; and move CD to stack one
        ld      hl, (PTRS+2)
        ld      de, (PTRS+0)
        ld      b, 2
        call    MOVE2
        ld      (PTRS+2), hl
        ld      (PTRS+0), de

        halt

It’s worth pointing out that moving data around on the stacks doesn’t clear popped data - instead, the tail pointer of the stack merely points at the next write address. The middle stack contains just M, which can be verified through the dumped stack pointer values, or by looking at HL.

Executing the program is just calling the appropriate movement routine depending on the star being executed. To get anywhere useful the program will also need to print the top crate label on each stack:

        .block
; IN:   stacks initialised
; OUT:  stack heads printed, empty stacks skipped
@HEADS: push    af
        push    bc
        push    de
        push    hl

        ld      hl, PTRS
        ld      bc, $103f       ; b=16,c=63
LOOP:   ld      a, (hl)
        ld      e, a
        inc     hl
        and     a, c            ; if ptr & 63 == 0
        jr      z, EMPTY        ; the stack is empty
        ld      d, (hl)
        dec     de
        ld      a, (de)
        out     (1), a
EMPTY:  inc     hl
        djnz    LOOP

        ld      a, '\n'
        out     (1), a

        pop     hl
        pop     de
        pop     bc
        pop     af
        ret
        .endblock

Let’s see this in action, repeating the same movements above printing out the stack heads each time:


        ld      sp, $8000
        ld      hl, SAMPLE
        call    INIT
        call    HEADS

        ; move ZN on top of P one by one, to get PNZ
        ld      hl, (PTRS+0)
        ld      de, (PTRS+4)
        ld      b, 2
        call    MOVE1
        ld      (PTRS+0), hl
        ld      (PTRS+4), de
        call    HEADS

        ; and move CD to stack one
        ld      hl, (PTRS+2)
        ld      de, (PTRS+0)
        ld      b, 2
        call    MOVE2
        ld      (PTRS+2), hl
        ld      (PTRS+0), de
        call    HEADS

        halt

It’s finally time to execute the program step by step.

        .block
; IN:   HL      the program to execute
;       IX      the movement routine
; OUT:  HL      end of the program
;       stacks modified
@RUN:   push    af
        push    bc
        push    de
        push    iy

LOOP:   ld      a, (hl) ; count
        or      a
        jr      z, DONE
        inc     hl

        ; load the FROM stack pointer address
        ld      c, (hl)
        inc     hl
        ld      b, (hl)
        inc     hl

        ; load the TO stack pointer address
        ld      e, (hl)
        inc     hl
        ld      d, (hl)
        inc     hl

        ; save the program pointer and stack pointers
        push    hl
        push    bc
        push    de

        ; load the TO stack pointer
        ex      de, hl
        ld      e, (hl)
        inc     hl
        ld      d, (hl)

        ; load the FROM stack pointer
        ld      h, b
        ld      l, c
        ld      b, (hl)
        inc     hl
        ld      h, (hl)
        ld      l, b

        ; transfer the count
        ld      b, a

        ; do the move
        call    BOUNCE

        ; store the updated TO pointer
        pop     iy
        ld      (iy+0), e
        ld      (iy+1), d

        ; store the updated FROM pointer
        pop     iy
        ld      (iy+0), l
        ld      (iy+1), h

        ; restore the program pointer
        pop     hl

        jr      LOOP

DONE:   call    HEADS

        pop     iy
        pop     de
        pop     bc
        pop     af
        ret

; indirection to (ix)
BOUNCE: jp      (ix)
        .endblock

There’s some pointer register trickery in the middle, but otherwise this is a straightforward bit of code.

        ld      sp, $8000
        ld      hl, SAMPLE
        call    INIT
        ld      ix, MOVE1
        call    RUN
        ld      hl, SAMPLE
        call    INIT
        ld      ix, MOVE2
        call    RUN
        halt

All looks good for the sample input. It’s time to load up my own input and give it a shot.

DAY05:  ld      sp, $8000
        ld      hl, INPUT
        call    INIT
        ld      ix, MOVE1
        call    RUN
        ld      hl, INPUT
        call    INIT
        ld      ix, MOVE2
        call    RUN
        halt
INPUT:
.include        "day05-input.z80"

Hooray!

The series

Day 1 | Day 2 | Day 3 | Day 4 | Day 5 | Day 6 | Day 7 | Day 8 | Day 9 | Day 10 | Day 11 | Day 12 | Day 13 | Day 14 | Day 15 | Day 16 | Day 17 | Day 18 | Day 19 | Day 20 | Day 21 | Day 22 | Day 23 | Day 24 | Day 25 |