; Exercise the "malloc" and "free" subroutines. This involves using
; an array of 16 entries. The program repeatedly selects a random
; entry. If the entry is zero, the program calls "malloc" with a random
; parameter between 1 and 32 and places the returned address into the
; array. And if it is nonzero, it passes the value found into "free"
; and clears the array entry to zero.

        MOV SP, #0x1000          ; set stack pointer to 0x10000
        BL ttyStart              ; initialize terminal
        BL initHeap              ; initialize heap
        
        SUB SP, SP, #64          ; allocate array of entries
doTest  BL rand                  ; select random index and see what
        AND R4, R0, #0xF         ; block is allocated for that index
        LDR R6, [SP, R4, LSL #2]
        MOV R0, R4
        BL printHex
        TST R6, R6
        BNE doFree  ; go to freeing if index has block allocated
                    ; otherwise go to allocating a block for the index
        
doAlloc MOV R0, #'+'             ; if no block allocated, allocate block
        BL printChar             ; using malloc of random size (1-32)
        BL rand
        AND R0, R0, #0x1F
        ADD R0, R0, #1
        MOV R6, R0
        BL malloc
        STRB R4, [R0]
        STR R0, [SP, R4, LSL #2]
        BL printHex
        MOV R0, #'/'
        BL printChar
        MOV R0, R6
        BL printHex
        MOV R0, #'\n'
        BL printChar
        B doTest
        
doFree  MOV R0, #'-'             ; if block allocated, deallocate
        BL printChar             ; using free and mark index as 0
        MOV R0, R6
        BL free
        MOV R0, #0
        STRB R0, [R6]
        STR R0, [SP, R4, LSL #2]
        MOV R0, R6
        BL printHex
        MOV R0, #'\n'
        BL printChar
        B doTest
        
; Places into R0 a pseudorandom number between 0 and 255.
rand    LDR R0, [PC, #rseed]   ; compute random number according to
        ADD R0, R0, R0, LSL #8 ; sequence s[n] = 257 * s[n-1] + 97
        ADD R0, R0, #97
        STR R0, [PC, #rseed]
        EOR R0, R0, R0, LSR #8 ; and return (s[n] ^ (s[n] >>> 8)) & 0x7F
        AND R0, R0, #0xFF
        MOV PC, LR
        
rseed   DCD 87         ; current random number in sequence

        INCLUDE "io-sub.s"
        INCLUDE "heap.s"