include qlib.inc
include errno.inc
include string.inc

; Fragmented Memory Manager

; All I do is keep simple 12 byte headers in front of each block of RAM.
; First 2 byte = 'PQ'.  Second = flags. (a junk byte here ). Then next dword
; is a pointer to the previous block header and the next dword is the size
; of this block.  Flags are used to tell if a block is free and/or last one.

; All alloc RAM will be dword aligned

.data
externdef _baseram:dword     ;... don't want user to touch cause malloc sceme may change
                             
;RAM header
heads struct  ;12bytes
  magic dw ? ; 'PQ' ;signature (it will be 'QP' thru out this file cause of intel byte swap)
  flag db ?  ;bit0=free(1)  bit1=last(2)   (1==true)
  _a1 db ?   ;junk byte for alignment (not used!)
  prev dd ?  ;ptr=>previous block
  siz dd ?   ;size of this block
heads ends

MB_FREE equ 1
MB_LAST equ 2

.code

malloc proc,sz:dword
  pushad
  cmp sz,0
  jnz @f
bad:
  popad
  mov errno,ENOMEM
  mov eax,NULL
  ret
@@:
  ;make sure alloc block is dword aligned
  add sz,3
  and sz,0ffffffffh-3
  ;search thru chain for best fit
  mov eax,_baseram  ;ram start
  .if !eax
    jmp bad
  .endif
  mov ebx,0     ;best fit location
  mov ecx,-1    ;best fit is ecx too much over sz
start:
  mov dl,[eax].heads.flag
  test dl,1  ;free?
  jnz ok3
next:
  mov dl,[eax].heads.flag
  test dl,2  ;last?
  jnz endsrc
  add eax,[eax].heads.siz
  add eax,sizeof heads
  jmp start
ok3:
  ;found one that's free
  mov edx,[eax].heads.siz
  sub edx,sz
  jb next ;too small
  ;found one big enough
  cmp edx,ecx
  jae next ;already got another that's better
  ;this one's better
  mov ecx,edx
  mov ebx,eax
  jmp next
endsrc:
  ;end of search
  cmp ebx,0
  jz bad
;split ebx into 2 blocks:1st = used 2nd = free
  mov eax,ebx
  xor [ebx].heads.flag,1  ;set as used!
  cmp ecx,256  ;don't make a really small block
  ja ok4
  add ecx,sz
  mov [ebx].heads.siz,ecx  ;set size (all of it)
  add eax,sizeof heads
  mov [esp+7*4],eax
  popad
  ret
ok4:
  mov edx,sz
  mov al,[ebx].heads.flag
  and al,2        ;mask last
  xor [ebx].heads.flag,al  ;remove last if it's there
  mov [ebx].heads.siz,edx ;set size
  add edx,ebx
  add edx,sizeof heads
  mov [edx].heads.magic,'QP'  ;free only
  mov [edx].heads.flag,1
  or [edx].heads.flag,al  ;set if last
  mov [edx].heads.prev,ebx  ;set prev
  sub ecx,sizeof heads
  mov [edx].heads.siz,ecx  ;set size
  mov eax,ebx
  add eax,sizeof heads
  mov [esp+7*4],eax
  popad
  ret
malloc endp

calloc proc,siz1:dword,siz2:dword   ;it's like size,n_size type thing
  ;this clears the alloc RAM to 0
  local siz:dword
  pushad
  mov eax,siz1
  mov ebx,siz2
  mul ebx
  mov siz,eax
  callp malloc,eax
  .if eax==NULL
    popad
    mov eax,NULL
    ret
  .endif
  mov [esp+7*4],eax  ;save for ret
  mov edi,eax
  mov eax,0
  mov ecx,siz
  mov ebx,ecx
  shr ecx,2
  rep stosd
  mov ecx,ebx
  and ecx,3
  .if !zero?
    rep stosb
  .endif
  popad
  ret
calloc endp

free proc,b:dword
  pushad
  mov eax,b
  cmp eax,0
  jnz ok6
bad:
  popad
  mov errno,ENOMEM   ;just ignore
  mov eax,ERROR
  ret
ok6:
  sub eax,sizeof heads
  cmp eax,_baseram
  jz ok7 ;no above!
  mov ebx,[eax].heads.prev
  test [ebx].heads.flag,1
  jz ok7
  ;above is free

  mov dl,[eax].heads.flag  ;must copy flags to above block
  mov ecx,[eax].heads.siz
  mov eax,ebx
  add ecx,sizeof heads
  add [eax].heads.siz,ecx
  mov [eax].heads.flag,dl
ok7: ;done joining with above block
  mov ebx,[eax].heads.siz
  add ebx,eax
  add ebx,sizeof heads
  test byte ptr[ebx].heads.flag,1
  jz ok8
  mov ecx,[ebx].heads.siz
  add ecx,sizeof heads
  add [eax].heads.siz,ecx
  mov dl,[ebx].heads.flag
  mov [eax].heads.flag,dl
ok8: ;done joining below
  or [eax].heads.flag,1  ;mark as free
  popad
  xor eax,eax
  ret
free endp

qfree proc ;query free ram  ;out:eax=largest
  pushad
  mov ecx,_baseram
  .if !ecx
    popad
    xor eax,eax
    ret
  .endif
  xor eax,eax  ;largest
  xor edx,edx  ;size of last block
  sub ecx,sizeof heads
start:
  add ecx,sizeof heads
  add ecx,edx
  mov edx,[ecx].heads.siz
  test [ecx].heads.flag,1
  jz nope       ;FIX : v2.03 Beta #4 : this was jumping no where before?
  cmp edx,eax
  jb nope       ;FIX : v2.03 Beta #4 : this was jbe ?
  mov eax,edx
nope:
  test [ecx].heads.flag,2
  jz start
  mov [esp+7*4],eax
  popad
  ret
qfree endp

coreleft proc ;query free ram  ;out:eax=total
  pushad
  mov ecx,_baseram
  .if !ecx
    popad
    xor eax,eax
    ret
  .endif
  xor ebx,ebx  ;total
  xor edx,edx  ;size of last block
  sub ecx,sizeof heads
start:
  add ecx,sizeof heads
  add ecx,edx
  mov edx,[ecx].heads.siz
  test [ecx].heads.flag,1
  jz @f
  add ebx,edx
@@:
  test [ecx].heads.flag,2
  jz start
  mov [esp+7*4],ebx
  popad
  ret
coreleft endp

;reallocs a block of RAM
;this may return a new block addr and it will copy the old block to the new one
realloc proc,p:dword,siz:dword
  ;1st: attempts to see if next block is free and the simple enlarges
  ;     the block as needed
  ;ELSE alloc a new block and copies to it and then releases old block

  ;1st part not implemented yet (other more important stuff to do)

  local tmp:dword
  .if p==NULL
    callp malloc,siz
    ret
  .endif
  mov eax,p
  sub eax,sizeof heads     ;FIX : v2.00 Beta #4 : this was after .if
  .if wptr[eax].heads.magic!='QP'
    mov eax,NULL  ;ERROR!!
    ret
  .endif
  pushad
  mov ebx,[eax].heads.siz
  .if ebx==siz  ;requested same size
    popad
    mov eax,p   ;nothing to do
    ret
  .endif
  .if ebx<siz
    ;make smaller
    mov ecx,ebx
    sub ecx,siz
    .if ecx<256
      ;don't make the new block too small
      popad
      mov eax,p
      ret
    .endif
    ;split p into 2 blocks!
    mov ebx,siz
    mov edx,[eax].heads.siz
    mov [eax].heads.siz,ebx
    mov cl,[eax].heads.flag
    mov ebx,eax
    add ebx,siz
    add ebx,sizeof heads
    mov [ebx].heads.magic,'QP'
    mov [ebx].heads.flag,cl
    or [ebx].heads.flag,1   ;set as free
    sub edx,siz
    mov [ebx].heads.prev,eax
    sub edx,sizeof heads
    mov [ebx].heads.siz,edx
    popad
    mov eax,p
    ret
  .else
    ;make bigger (if possible)
    ; finished here v2.00 Beta #4
    .if [eax].heads.flag & MB_LAST
      jmp _else ;this is the last one
    .endif
    mov ecx,eax
    add ecx,ebx
    add ecx,sizeof heads  ;FIX : v2.03 Beta #4 : this was missing
    .if ! ([ecx].heads.flag & MB_FREE)
      jmp _else  ;it's not free
    .endif
    mov edx,[ecx].heads.siz
    add edx,sizeof heads
    ;if edx+ebx >= siz then we can do it!
    add edx,ebx
    .if (siz > edx)
      jmp _else
    .endif
    mov ebx,edx
    sub ebx,siz
    .if ebx<256  ;don't make too small
      mov [eax].heads.siz,edx
      mov bl,[ecx].heads.flag
      and bl,MB_LAST
      or [eax].heads.flag,bl  ;set last if it was last
    .else
      ;make another block
      mov cl,[ecx].heads.flag
      and cl,MB_LAST
      mov ebx,siz
      mov [eax].heads.siz,ebx
      mov [eax].heads.flag,0
      add eax,ebx
      mov [eax].heads.magic,'QP'
      mov [eax].heads.flag,MB_FREE
      or [eax].heads.flag,cl  ;set last if needed
      sub edx,siz
      sub edx,sizeof heads
      mov [eax].heads.siz,edx
      mov ebx,p
      mov [eax].heads.prev,ebx
    .endif
    popad
    mov eax,p
    ret
  .endif
_else:    ;alloc a new block and copy to it
  callp malloc,siz
  .if eax==NULL
    popad
    ret
  .endif
  mov tmp,eax
  mov eax,p
  sub eax,sizeof heads
  mov eax,[eax].heads.siz      ;only copy block size
  .if eax>siz
    mov eax,siz                ;unless requested size is smaller
  .endif
  callp memcpy,tmp,p,eax
  callp free,p
  popad 
  mov eax,tmp
  ret
realloc endp

end