Bubble sort

This example demonstrates a simple bubble sort algorithm implemented in assembly language for the Tiny8 CPU. The program first fills a section of RAM with pseudo-random bytes, then sorts those bytes using the bubble sort algorithm. Finally, a Python script runs the assembly program and visualizes the sorting process.

bubblesort.asm

; Bubble sort using RAM (addresses 100..131) - 32 elements
; Purpose: fill RAM[100..131] with pseudo-random bytes and sort them
; Registers (use R16..R31 for LDI immediates):
;   R16 - base address (start = 100)
;   R17 - index / loop counter for initialization
;   R18 - PRNG state (seed)
;   R19..R24 - temporary registers used in loops and swaps
;   R25 - PRNG multiplier (kept aside to avoid clobber in MUL)
;
; The code below is split into two phases:
; 1) init_loop: generate and store 32 pseudo-random bytes at RAM[100..131]
; 2) outer/inner loops: perform a simple bubble sort over those 32 bytes

    ; initialize pointers and PRNG
    ldi r16, 100    ; base address
    ldi r17, 0      ; index = 0
    ldi r18, 123    ; PRNG seed
    ldi r25, 75     ; PRNG multiplier (kept in r25 so mul doesn't clobber it)

init_loop:
    ; PRNG step: r2 := lowbyte(r2 * 75), then tweak
    mul r18, r25     ; r18 = low byte of (r18 * 75)
    inc r18           ; small increment to avoid repeating patterns
    ; store generated byte into memory at base + index
    st r16, r18       ; RAM[base] = r18
    inc r16           ; advance base pointer
    inc r17           ; increment index
    ldi r23, 32
    cp r17, r23
    brne init_loop

; Bubble sort for 32 elements (perform passes until i == 31)
    ldi r18, 0      ; i = 0 (outer loop counter)
outer_loop:
    ldi r19, 0      ; j = 0 (inner loop counter)
inner_loop:
    ; compute address of element A = base + j
    ldi r20, 100
    add r20, r19
    ld r21, r20      ; r21 = A
    ; compute address of element B = base + j + 1
    ldi r22, 100
    add r22, r19
    ldi r23, 1
    add r22, r23
    ld r24, r22      ; r24 = B
    ; compare A and B (we'll swap if A < B)
    cp r21, r24      ; sets carry if r21 < r24
    brcc no_swap
    ; swap A and B: store B into A's address, A into B's address
    st r20, r24
    st r22, r21
no_swap:
    inc r19
    ldi r23, 31
    cp r19, r23
    breq end_inner
    jmp inner_loop
end_inner:
    inc r18
    ldi r23, 31
    cp r18, r23
    breq done
    jmp outer_loop

done:
    jmp done

bubblesort.py

from tiny8 import CPU, Visualizer, assemble_file

prog, labels = assemble_file("examples/bubblesort.asm")
cpu = CPU()
cpu.load_program(prog, labels)
cpu.run(max_cycles=15000)

print([cpu.read_ram(i) for i in range(100, 132)])

viz = Visualizer(cpu)
base = 100
viz.animate_combined(
    interval=1,
    mem_addr_start=base,
    mem_addr_end=base + 31,
    plot_every=100,
    # filename="bubblesort.gif",
    # fps=60,
)

Example Output

[247, 243, 239, 238, 227, 211, 210, 195, 190, 187, 186, 171, 167, 159, 155, 150, 142, 139, 135, 130, 127, 106, 102, 94, 54, 50, 34, 26, 23, 15, 10, 6]