; s.Cache

                GET             hdr.Common
                GET             hdr.Hardware

                AREA            |$Cache|, PIC, CODE

CacheRef        STRUC
Offset          INT
Length          INT
Address         INT                             ; Device << 28 | LBA
Used            INT                             ; Monotonic time
                STREND

Cache           STRUC
IndexSize       INT                             ; Maximum number of index entries
IndexUsed       INT                             ; Current used size
Index           INT                             ; Pointer to a CacheRef
BufferSize      INT                             ; Buffer size
Buffer          INT                             ; Pointer to buffer
                STREND

; The cache allocation strategy is like this
;
; Scan the cache for a gap which is large enough to accomodate the block which
; we're trying to read. While doing this record the total amount of space which
; is available in the cache.
;
; If the total amount of space would allow the block to be inserted but it is too
; fragmented then garbage collect it and add the block at the end.
;
; If there is not enough room then discard blocks at random until there is enough
; room, and repeat the whole process.
;
; R4  ==> Size of required block (typically 2048 or so)
;
; On exit
;
; C   ==> 0 if space available, else 1
; R3  ==> Address of block, if C = 0


CacheAlloc      SAVE            "r0-r2, r4-r8"

; If the block is too large for the cache then there's no hope

                LDR             r0, Cache + Cache_BufferSize
                CMP             r4, r0
                RESTORE         CS
                MOVCS           pc, lr             ;exit with C set

; Comes back here after making some space in the cache

CacheAlloc1     ADR             r8, Cache

                ASSERT          :INDEX: Cache_IndexSize = 0
                ASSERT          :INDEX: Cache_IndexUsed = 4
                ASSERT          :INDEX: Cache_Index = 8

                LDMIA           r8, {r0, r1, r2}

                CMP             r1, r0
                BLGE            CacheLRUDelete
                BGE             CacheAlloc1

; Some space in the index, so look down it for a large enough block

                MOV             r3, #0          ; End of previous block
                MOV             r5, #0          ; Total space

                CMP             r1, #0
                BLE             CacheAlloc3

                ASSERT          :INDEX: CacheRef_Offset = 0
                ASSERT          :INDEX: CacheRef_Length = 4

CacheAlloc2     LDMIA           r2, {r6, r7}
                SUB             lr, r6, r3      ; Size of gap
                ADD             r5, r5, lr      ; add to total

; Is the gap big enough?

                CMP             lr, r4
                BGE             CacheAlloc4

                ADD             r3, r6, r7      ; End of block

                ADD             r2, r2, #CacheRef_Size
                SUBS            r1, r1, #0
                BGT             CacheAlloc2

; Count the gap at the end

CacheAlloc3     LDR             lr, [r8, #Cache_BufferSize]
                SUB             lr, lr, r3
                ADD             r5, r5, lr
                CMP             lr, r4
                BGE             CacheAlloc4

; No gap was big enough; what about the total free space?

                CMP             r5, r4
                BLGE            CacheGarbage
                BGE             CacheAlloc1

                BL              CacheLRUDelete
                B               CacheAlloc1

; Got a slot
;
; R1  ==> Number of index items to move up (may be 0)
; R2  ==> Pointer to portion of index to move
; R3  ==> Offset of slot

CacheAlloc4

                RESTORE
                CMP             r0, r0              ;clear C
                MOV             pc, lr

; Remove the least recently used block from the cache

CacheLRUDelete  SAVE            "r0-r8"

                ADR             r8, Cache

                ASSERT          :INDEX: Cache_IndexUsed = 4
                ASSERT          :INDEX: Cache_Index = 8

                LDMIB           r8, {r1, r2}
                MOV             r3, #&7FFFFFFF  ; LRU
                MOV             r4, #-1
                MOV             r5, #-1

                CMP             r1, #0
                BLE             CacheLRUDelete4

CacheLRUDelete1 LDR             r0, [r2, #CacheRef_Used]
                CMP             r0, r3
                MOVLT           r3, r0          ; Used
                MOVLT           r4, r1          ; Number left to do
                MOVLT           r5, r2          ; Address of this item
                ADD             r2, r2, #CacheRef_Size
                SUBS            r1, r1, #1
                BNE             CacheLRUDelete1

CacheLRUDelete2 CMP             r4, #-1
                BEQ             CacheLRUDelete4

                ADD             r0, r5, #CacheRef_Size

                ASSERT          CacheRef_Size = 16

CacheLRUDelete3 SUBS            r4, r4, #1
                LDMGTIA         r0!, {r1, r2, r3, r6}
                STMGTIA         r5!, {r1, r2, r3, r6}
                BGT             CacheLRUDelete3

                LDR             r0, Cache + Cache_IndexUsed
                SUB             r0, r0, #1
                STR             r0, Cache + Cache_IndexUsed

CacheLRUDelete4 RETURN

                END
