SHARE
TWEET

Game Boy `malloc` & `free`

ISSOtm Nov 13th, 2018 (edited) 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ; Untested, but I think it should work.
  2. ; FIXED: Free didn't check for ends of heap
  3.  
  4.  
  5.  
  6. INCLUDE "stdlib/hardware.inc"
  7.  
  8. HEAP_SIZE = 2048
  9.  
  10.  
  11. SECTION "Heap", WRAMX, BANK[1]
  12.  
  13. ; Block header format:
  14. ;  2 bytes BE - Size; bit 15 is set whenever the block is used
  15. ;  2 bytes LE - Pointer to next
  16. ;  2 bytes LE - Pointer to prev
  17.  
  18.  
  19. Heap:
  20.     ds HEAP_SIZE
  21. .end
  22.  
  23.  
  24. SECTION "Heap management functions", ROM0
  25.  
  26. ; Inits the heap.
  27. ; @return a  0
  28. ; @destroy hl
  29. InitHeap::
  30.     ld hl, Heap
  31.     IF HEAP_SIZE & $8000
  32.         FAIL "Heap size ({HEAP_SIZE}) must not be over $8000. How did you do that anyways?!?"
  33.     ENDC
  34.     ; Size
  35.     ld a, HIGH(HEAP_SIZE - 6) ; Bit 7 is reset
  36.     ld [hli], a
  37.     ld a, LOW(HEAP_SIZE - 6)
  38.     ld [hli], a
  39.     xor a
  40.     ; Next ptr
  41.     ld [hli], a
  42.     ld [hli], a
  43.     ; Prev ptr
  44.     ld [hli], a
  45.     ld [hli], a
  46.     ret
  47.  
  48. ; Allocates a block in memory
  49. ; @param bc Requested size
  50. ; @return Z Reset if a block is found
  51. ; @return hl Pointer to allocated memory
  52. ; @destroy a de
  53. Malloc:
  54.     xor a
  55.     ld de, 0 ; Set "found" ptr to NULL
  56.     ld hl, Heap
  57.  
  58. .searchHeap
  59.     ; Check sign of difference between block size and requested size
  60.     ld a, [hli]
  61.     bit 7, a
  62.     ; hl must point to second byte of designated block on exit
  63.     jr nz, .notThisBlock
  64.     cp b
  65.     jr c, .notThisBlock
  66.     jr nz, .largeEnough
  67.     ; High bytes are equal, check low bytes
  68.     ld a, [hl]
  69.     cp c
  70.     jr c, .notThisBlock
  71.     jr nz, .largeEnough
  72.  
  73.     ; Block is *exactly* the right size, use it immediately
  74.     dec hl
  75.     set 7, [hl]
  76.     ld de, 6
  77.     add hl, de
  78.     ret
  79.  
  80. .largeEnough
  81.     ; Check if block is larger than current block (so we avoid splitting in small fragments)
  82.     ld a, d
  83.     or e
  84.     jr z, .useThisBlock ; If no block selected yet, use this one
  85.     dec de
  86.     ld a, [de]
  87.     inc de
  88.     cpl
  89.     inc a
  90.     dec hl
  91.     add a, [hl] ; a = [hl] - [de]
  92.     inc hl
  93.     jr c, .notThisBlock
  94.     ld a, [de]
  95.     cp [hl]
  96.     jr nc, .notThisBlock ; If blocks are of same size, don't pick them
  97. .useThisBlock
  98.     ld e, l
  99.     ld d, h
  100. .notThisBlock
  101.     inc hl
  102.     ld a, [hli]
  103.     ld h, [hl]
  104.     ld l, a
  105.     or h
  106.     jr nz, .searchHeap ; Keep searching if we didn't reach the end of the heap
  107.  
  108.     ld a, d
  109.     or e
  110.     ret z ; Return if no block has been found
  111.  
  112.     ; Modify the target block (split, change size & pointers...)
  113.     ; Don't split the target block if the resulting block would be too small
  114.     ld h, d
  115.     ld l, e
  116.     ld a, [hld] ; Read low
  117.     sub 6 + 1 ; Subtract header size (+ 1)
  118.     sub c
  119.     jr nc, .sizeOK
  120.     ld a, [hli]
  121.     sbc b
  122.     jr c, .dontSplit ; Note: Z is reset
  123.     ; Tbh I doubt 1-byte blocks are any use, but I'm not sure of any better solution
  124.     ; I know that *-fit mallocs are bad, but I'm not sure we can afford a more complex one...
  125.     ; Now, modify the current block's header, and create a new block
  126.  
  127.     ; Add header size to requested size, simplifies later calculations
  128.     ld a, c
  129.     add a, 6
  130.     ld c, a
  131.     adc a, b
  132.     sub c
  133.     ld b, a
  134.     ; Go to high (2nd) byte of new block's prev ptr (hl points to 2nd byte of size)
  135.     ld a, c
  136.     add a, 2
  137.     add a, l
  138.     ld l, a
  139.     ld a, b
  140.     add a, h
  141.     ld h, a
  142.     ; Write prev ptr
  143.     dec de ; de points to first byte of block
  144.     ld a, d
  145.     ld [hld], a
  146.     ld a, e
  147.     ld [hld], a
  148.     ; Copy next ptr
  149.     inc de
  150.     inc de ; de points to "next" ptr
  151.     inc de
  152.     ld a, [de]
  153.     ld [hld], a
  154.     dec de
  155.     ld a, [de]
  156.     ld [hld], a
  157.     ; Write new size
  158.     dec de
  159.     ld a, c
  160.     ld a, [de]
  161.     sub c
  162.     ld [hld], a
  163.     dec de
  164.     ld a, [de]
  165.     sbc b
  166.     ld [hli], a
  167.     ; Subtract header size to get real size
  168.     ld a, c
  169.     sub 6
  170.     ld c, a
  171.     adc a, b
  172.     sub c
  173.     ; Write new size
  174.     or $80 ; Mark block as used
  175.     ld [de], a
  176.     inc de
  177.     ld a, c
  178.     ld [de], a
  179.     ; Z reset from `or $80`
  180. .dontSplit
  181.     ld de, 6 - 1
  182.     add hl, de ; Preserves Z
  183.     ret
  184.  
  185. ; Frees the given block
  186. ; @param hl Pointer to the block to be freed
  187. ; @destroy a bc de hl
  188. Free::
  189.     ld de, -6
  190.     add hl, de
  191.     bit 7, [hl]
  192.     ret nz ; Prevent double frees
  193.     ; Get ptr to next ptr in `de`
  194.     ld a, l
  195.     add a, 2
  196.     ld e, a
  197.     adc a, h
  198.     sub e
  199.     ld d, a
  200.     ; Get ptr to next block
  201.     ld a, [de]
  202.     ld l, a
  203.     inc de
  204.     ld a, [de]
  205.     ld h, a
  206.     or l
  207.     jr z, .dontMergeWithNext
  208.     ld a, [hli]
  209.     bit 7, a ; 1 cycle slower than `bit 7, [hl]`, but saves one `inc hl`
  210.     jr nz, .dontMergeWithNext
  211.     ; Next block is free, need to merge with them
  212.     and $7F
  213.     ld b, a ; Save size for later
  214.     ld a, [hli]
  215.     add a, 6 ; Add header size while we have this in `a`
  216.     ld c, a
  217.     adc a, b
  218.     sub c
  219.     ld b, a
  220.     ; Copy next ptr
  221.     inc hl
  222.     ld a, [hld]
  223.     ld [de], a
  224.     dec de
  225.     ld a, [hl]
  226.     ld [de], a
  227.     dec de
  228.     ; Add sizes
  229.     ld a, [de]
  230.     add a, c
  231.     ld [de], a
  232.     dec de
  233.     ld a, [de]
  234.     adc a, b
  235.     ld [de], a
  236.     ; Make `de` point to next ptr's 2nd byte
  237.     inc de
  238.     inc de
  239.     inc de
  240. .dontMergeWithNext
  241.     inc de
  242.     ; Get prev ptr
  243.     ld a, [de]
  244.     inc de
  245.     ld l, a
  246.     ld a, [de]
  247.     ld h, a
  248.     or l
  249.     ret z
  250.     ld a, [hli]
  251.     bit 7, a
  252.     ret nz ; End here if we aren't gonna merge
  253.     and $7F
  254.     ld b, a ; Save size for later
  255.     ld a, [hli]
  256.     add a, 6 ; Add header size
  257.     ld c, a
  258.     adc a, b
  259.     sub c
  260.     ld b, a
  261.     ; Copy `next` ptr
  262.     dec de
  263.     dec de
  264.     inc hl
  265.     ld a, [de]
  266.     dec de
  267.     ld [hld], a
  268.     ld a, [de]
  269.     dec de
  270.     ld [hld], a
  271.     ld a, [de]
  272.     dec de
  273.     add a, c
  274.     ld [hld], a
  275.     ld a, [de]
  276.     adc a, b
  277.     ld [hl], a
  278.     ret
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top