From 8db1fa3aa00cdaf8935dbff6c9cb3b2dc9406732 Mon Sep 17 00:00:00 2001 From: cuz Date: Fri, 21 Jul 2000 21:36:06 +0000 Subject: [PATCH] Rewrite _hadd in assembler (a huge speedup!) and integrate it with free for even faster code. The old _hadd function is now also written in assembler but does only setup variables and calls the internal function that is part of free. git-svn-id: svn://svn.cc65.org/cc65/trunk@182 b7a2c559-68d2-44c3-8de9-860c34a00d81 --- libsrc/common/.cvsignore | 1 - libsrc/common/Makefile | 5 +- libsrc/common/_hadd.c | 107 ---------- libsrc/common/_hadd.s | 59 ++++++ libsrc/common/free.s | 442 ++++++++++++++++++++++++++++++++++----- 5 files changed, 453 insertions(+), 161 deletions(-) delete mode 100644 libsrc/common/_hadd.c create mode 100644 libsrc/common/_hadd.s diff --git a/libsrc/common/.cvsignore b/libsrc/common/.cvsignore index 7f2a43786..fabf0b023 100644 --- a/libsrc/common/.cvsignore +++ b/libsrc/common/.cvsignore @@ -25,7 +25,6 @@ vsprintf.s sprintf.s abort.s errormsg.s -_hadd.s cprintf.s vcprintf.s freopen.s diff --git a/libsrc/common/Makefile b/libsrc/common/Makefile index 2521e28a2..98ca45efd 100644 --- a/libsrc/common/Makefile +++ b/libsrc/common/Makefile @@ -10,7 +10,7 @@ @$(AS) -g -o $@ $(AFLAGS) $(*).s %.o: %.s - @echo $< + @echo $< @$(AS) -g -o $@ $(AFLAGS) $< C_OBJS = fclose.o fgets.o fprintf.o strdup.o calloc.o _fopen.o\ @@ -18,10 +18,11 @@ C_OBJS = fclose.o fgets.o fprintf.o strdup.o calloc.o _fopen.o\ printf.o _hextab.o vfprintf.o fdopen.o strtok.o\ _afailed.o fopen.o fgetc.o fputc.o puts.o gets.o perror.o getchar.o\ _printf.o vprintf.o vsprintf.o sprintf.o abort.o qsort.o putchar.o\ - errormsg.o _hadd.o cprintf.o vcprintf.o freopen.o locale.o + errormsg.o cprintf.o vcprintf.o freopen.o locale.o S_OBJS = _fdesc.o \ _file.o \ + _hadd.o \ _heap.o \ _oserror.o \ _stksize.o \ diff --git a/libsrc/common/_hadd.c b/libsrc/common/_hadd.c deleted file mode 100644 index c257ffcdf..000000000 --- a/libsrc/common/_hadd.c +++ /dev/null @@ -1,107 +0,0 @@ -/* - * _hadd.c - * - * Ullrich von Bassewitz, 19.06.1998 - */ - - - -#include -#include "_heap.h" - - - -void _hadd (void* mem, size_t size) -/* Add an arbitrary memory block to the heap. This function is used by - * free(), but it does also allow usage of otherwise unused memory - * blocks as heap space. The given block is entered in the free list - * without any checks, so beware! - */ -{ - struct freeblock* f; - struct freeblock* left; - struct freeblock* right; - - if (size >= sizeof (struct freeblock)) { - - /* Set the admin data */ - f = (struct freeblock*) mem; - f->size = size; - - /* Check if the freelist is empty */ - if (_hfirst == 0) { - - /* The freelist is empty until now, insert the block */ - f->prev = 0; - f->next = 0; - _hfirst = f; - _hlast = f; - - } else { - - /* We have to search the free list. As we are doing so, we check - * if it is possible to combine this block with another already - * existing block. Beware: The block may be the "missing link" - * between *two* other blocks. - */ - left = 0; - right = _hfirst; - while (right && f > right) { - left = right; - right = right->next; - } - - - /* Ok, the current block must be inserted between left and right (but - * beware: one of the two may be zero!). Also check for the condition - * that we have to merge two or three blocks. - */ - if (right) { - /* Check if we must merge the block with the right one */ - if (((unsigned) f) + size == (unsigned) right) { - /* Merge with the right block */ - f->size += right->size; - if (f->next = right->next) { - f->next->prev = f; - } else { - /* This is now the last block */ - _hlast = f; - } - } else { - /* No merge, just set the link */ - f->next = right; - right->prev = f; - } - } else { - f->next = 0; - /* Special case: This is the new freelist end */ - _hlast = f; - } - if (left) { - /* Check if we must merge the block with the left one */ - if ((unsigned) f == ((unsigned) left) + left->size) { - /* Merge with the left block */ - left->size += f->size; - if (left->next = f->next) { - left->next->prev = left; - } else { - /* This is now the last block */ - _hlast = left; - } - } else { - /* No merge, just set the link */ - left->next = f; - f->prev = left; - } - } else { - f->prev = 0; - /* Special case: This is the new freelist start */ - _hfirst = f; - } - } - } -} - - - - diff --git a/libsrc/common/_hadd.s b/libsrc/common/_hadd.s new file mode 100644 index 000000000..7032c6502 --- /dev/null +++ b/libsrc/common/_hadd.s @@ -0,0 +1,59 @@ +; +; Ullrich von Bassewitz, 21.7.2000 +; +; Add a block to the heap free list +; +; void __fastcall__ _hadd (void* mem, size_t size); +; +; + + .importzp ptr1, ptr2 + .import popax + .import hadd + .export _hadd + + .macpack generic + +; Offsets into struct freeblock and other constant stuff + +size = 0 +next = 2 +prev = 4 +admin_space = 2 +min_size = 6 + + +; Code + +_hadd: sta ptr1 ; Store size in ptr1 + stx ptr1+1 + jsr popax ; Get the block pointer + sta ptr2 + stx ptr2+1 ; Store block pointer in ptr2 + +; Check if size is greater or equal than min_size. Otherwise we don't care +; about the block (this may only happen for user supplied blocks, blocks +; from the heap are always large enough to hold a freeblock structure). + + lda ptr1 ; Load low byte + ldx ptr1+1 ; Load/check high byte + bne @L1 + cmp #min_size + bcs @L1 + + rts ; Block not large enough + +; The block is large enough. Set the size field in the block. + +@L1: ldy #size + sta (ptr2),y + iny + txa + sta (ptr2),y + +; Call the internal function since variables are now setup correctly + + jmp hadd + + + diff --git a/libsrc/common/free.s b/libsrc/common/free.s index 8caf04d4b..06ccd135b 100644 --- a/libsrc/common/free.s +++ b/libsrc/common/free.s @@ -59,10 +59,9 @@ ; } ; - .importzp ptr1, ptr2 - .import __hptr, __hfirst, __hlast - .import pushax, __hadd - .export _free + .importzp ptr1, ptr2, ptr3, ptr4 + .import __hptr, __hfirst, __hlast, __hend + .export _free, hadd .macpack generic @@ -77,66 +76,66 @@ min_size = 6 ; Code -_free: sta ptr1 - stx ptr1+1 ; Save block +_free: sta ptr2 + stx ptr2+1 ; Save block ; Is the argument NULL? - ora ptr1+1 ; Is the argument NULL? + ora ptr2+1 ; Is the argument NULL? beq @L9 ; Jump if yes ; Decrement the given pointer by the admin space amount, so it points to the ; real block allocated. The size of the block is stored in the admin space. -; Remember the block size in ptr2. +; Remember the block size in ptr1. - lda ptr1 + lda ptr2 sub #admin_space - sta ptr1 + sta ptr2 bcs @L1 - dec ptr1+1 + dec ptr2+1 @L1: ldy #size+1 - lda (ptr1),y ; High byte of size - sta ptr2+1 ; Save it + lda (ptr2),y ; High byte of size + sta ptr1+1 ; Save it dey - lda (ptr1),y - sta ptr2 + lda (ptr2),y + sta ptr1 ; Check if the block is on top of the heap - add ptr1 + add ptr2 tay - lda ptr1+1 - adc ptr2+1 + lda ptr2+1 + adc ptr1+1 cpy __hptr - bne @AddToFreeList + bne hadd ; Add to free list cmp __hptr+1 - bne @AddToFreeList + bne hadd ; The pointer is located at the heap top. Lower the heap top pointer to ; release the block. -@L3: lda ptr1 +@L3: lda ptr2 sta __hptr - lda ptr1+1 + lda ptr2+1 sta __hptr+1 ; Check if the last block in the freelist is now at heap top. If so, remove ; this block from the freelist. lda __hlast - sta ptr2 + sta ptr1 ora __hlast+1 beq @L9 ; Jump if free list empty lda __hlast+1 - sta ptr2+1 ; Pointer to last block now in ptr2 + sta ptr1+1 ; Pointer to last block now in ptr1 ldy #size - lda (ptr2),y ; Low byte of block size - add ptr2 + lda (ptr1),y ; Low byte of block size + add ptr1 tax - iny ; High byte of block size - lda (ptr2),y - adc ptr2+1 + iny ; High byte of block size + lda (ptr1),y + adc ptr1+1 cmp __hptr+1 bne @L9 ; Jump if last block not on top of heap @@ -145,20 +144,20 @@ _free: sta ptr1 ; Remove the last block - lda ptr2 + lda ptr1 sta __hptr - lda ptr2+1 + lda ptr1+1 sta __hptr+1 ; Correct the next pointer of the now last block ldy #prev+1 ; Offset of ->prev field - lda (ptr2),y - sta ptr1+1 ; Remember f->prev in ptr1 + lda (ptr1),y + sta ptr2+1 ; Remember f->prev in ptr2 sta __hlast+1 dey - lda (ptr2),y - sta ptr1 ; Remember f->prev in ptr1 + lda (ptr1),y + sta ptr2 ; Remember f->prev in ptr2 sta __hlast ora __hlast+1 ; -> prev == 0? bne @L8 ; Jump if free list not empty @@ -172,26 +171,367 @@ _free: sta ptr1 @L9: rts -; Block before is now last block. ptr1 points to f->prev. +; Block before is now last block. ptr2 points to f->prev. @L8: lda #$00 - dey ; Points to high byte of ->next - sta (ptr1),y - dey ; Low byte of f->prev->next - sta (ptr1),y - rts ; Done + dey ; Points to high byte of ->next + sta (ptr2),y + dey ; Low byte of f->prev->next + sta (ptr2),y + rts ; Done + +; The block is not on top of the heap. Add it to the free list. This was +; formerly a separate function called __hadd that was implemented in C as +; shown here: +; +; void _hadd (void* mem, size_t size) +; /* Add an arbitrary memory block to the heap. This function is used by +; * free(), but it does also allow usage of otherwise unused memory +; * blocks as heap space. The given block is entered in the free list +; * without any checks, so beware! +; */ +; { +; struct freeblock* f; +; struct freeblock* left; +; struct freeblock* right; +; +; if (size >= sizeof (struct freeblock)) { +; +; /* Set the admin data */ +; f = (struct freeblock*) mem; +; f->size = size; +; +; /* Check if the freelist is empty */ +; if (_hfirst == 0) { +; +; /* The freelist is empty until now, insert the block */ +; f->prev = 0; +; f->next = 0; +; _hfirst = f; +; _hlast = f; +; +; } else { +; +; /* We have to search the free list. As we are doing so, we check +; * if it is possible to combine this block with another already +; * existing block. Beware: The block may be the "missing link" +; * between *two* other blocks. +; */ +; left = 0; +; right = _hfirst; +; while (right && f > right) { +; left = right; +; right = right->next; +; } +; +; +; /* Ok, the current block must be inserted between left and right (but +; * beware: one of the two may be zero!). Also check for the condition +; * that we have to merge two or three blocks. +; */ +; if (right) { +; /* Check if we must merge the block with the right one */ +; if (((unsigned) f) + size == (unsigned) right) { +; /* Merge with the right block */ +; f->size += right->size; +; if (f->next = right->next) { +; f->next->prev = f; +; } else { +; /* This is now the last block */ +; _hlast = f; +; } +; } else { +; /* No merge, just set the link */ +; f->next = right; +; right->prev = f; +; } +; } else { +; f->next = 0; +; /* Special case: This is the new freelist end */ +; _hlast = f; +; } +; if (left) { +; /* Check if we must merge the block with the left one */ +; if ((unsigned) f == ((unsigned) left) + left->size) { +; /* Merge with the left block */ +; left->size += f->size; +; if (left->next = f->next) { +; left->next->prev = left; +; } else { +; /* This is now the last block */ +; _hlast = left; +; } +; } else { +; /* No merge, just set the link */ +; left->next = f; +; f->prev = left; +; } +; } else { +; f->prev = 0; +; /* Special case: This is the new freelist start */ +; _hfirst = f; +; } +; } +; } +; } +; + +; Check if the free list is empty, storing _hfirst into ptr3 for later + +hadd: lda __hfirst + sta ptr3 + lda __hfirst+1 + sta ptr3+1 + ora ptr3 + bne SearchFreeList + +; The free list is empty, so this is the first and only block. A contains +; zero if we come here. + + ldy #next-1 +@L2: iny ; f->next = f->prev = 0; + sta (ptr2),y + cpy #prev+1 ; Done? + bne @L2 + + lda ptr2 + ldx ptr2+1 + sta __hfirst + stx __hfirst+1 ; _hfirst = f; + sta __hlast + stx __hlast+1 ; _hlast = f; + + rts ; Done + +; We have to search the free list. As we are doing so, check if it is possible +; to combine this block with another, already existing block. Beware: The +; block may be the "missing link" between two blocks. +; ptr3 contains _hfirst (the start value of the search) when execution reaches +; this point, Y contains size+1. We do also know that _hfirst (and therefore +; ptr3) is not zero on entry. + +SearchFreeList: + lda #0 + sta ptr4 + sta ptr4+1 ; left = 0; + ldy #next+1 + ldx ptr3 + +@Loop: lda ptr3+1 ; High byte of right + cmp ptr2+1 + bne @L1 + cpx ptr2 + beq @L2 +@L1: bcs CheckRightMerge + +@L2: stx ptr4 ; left = right; + sta ptr4+1 + + dey ; Points to next + lda (ptr3),y ; right = right->next; + tax + iny ; Points to next+1 + lda (ptr3),y + stx ptr3 + sta ptr3+1 + ora ptr3 + bne @Loop + +; If we come here, the right pointer is zero, so we don't need to check for +; a merge. The new block is the new freelist end. +; A is zero when we come here, Y points to next+1 + + sta (ptr2),y ; Clear high byte of f->next + dey + sta (ptr2),y ; Clear low byte of f->next + + lda ptr2 ; _hlast = f; + sta __hlast + lda ptr2+1 + sta __hlast+1 + +; Since we have checked the case that the freelist is empty before, if the +; right pointer is NULL, the left *cannot* be NULL here. So skip the +; pointer check and jump right to the left block merge + + jmp CheckLeftMerge2 + +; The given block must be inserted between left and right, and right is not +; zero. + +CheckRightMerge: + lda ptr2 + add ptr1 ; f + size + tax + lda ptr2+1 + adc ptr1+1 + + cpx ptr3 + bne NoRightMerge + cmp ptr3+1 + bne NoRightMerge + +; Merge with the right block. Do f->size += right->size; + + ldy #size + lda ptr1 + add (ptr3),y + sta (ptr2),y + iny ; Points to size+1 + lda ptr1+1 + adc (ptr3),y + sta (ptr2),y + +; Set f->next = right->next and remember f->next in ptr1 (we don't need the +; size stored there any longer) + + iny ; Points to next + lda (ptr3),y ; Low byte of right->next + sta (ptr2),y ; Store to low byte of f->next + sta ptr1 + iny ; Points to next+1 + lda (ptr3),y ; High byte of right->next + sta (ptr2),y ; Store to high byte of f->next + sta ptr1+1 + ora ptr1 + beq @L1 ; Jump if f->next zero + +; f->next->prev = f; + + iny ; Points to prev + lda ptr2 ; Low byte of f + sta (ptr1),y ; Low byte of f->next->prev + iny ; Points to prev+1 + lda ptr2+1 ; High byte of f + sta (ptr1),y ; High byte of f->next->prev + jmp CheckLeftMerge ; Done + +; f->next is zero, this is now the last block + +@L1: lda ptr2 ; _hlast = f; + sta __hlast + lda ptr2+1 + sta __hlast+1 + jmp CheckLeftMerge + +; No right merge, just set the link. + +NoRightMerge: + ldy #next ; f->next = right; + lda ptr3 + sta (ptr2),y + iny ; Points to next+1 + lda ptr3+1 + sta (ptr2),y + + iny ; Points to prev + lda ptr2 ; right->prev = f; + sta (ptr3),y + iny ; Points to prev+1 + lda ptr2+1 + sta (ptr3),y + +; Check if the left pointer is zero + +CheckLeftMerge: + lda ptr4 ; left == NULL? + ora ptr4+1 + bne CheckLeftMerge2 ; Jump if there is a left block + +; We don't have a left block, so f is actually the new freelist start + + ldy #prev + sta (ptr2),y ; f->prev = 0; + iny + sta (ptr2),y + + lda ptr2 ; _hfirst = f; + sta __hfirst + lda ptr2+1 + sta __hfirst+1 + + rts ; Done + +; Check if the left block is adjacent to the following one + +CheckLeftMerge2: + ldy #size ; Calculate left + left->size + lda (ptr4),y ; Low byte of left->size + add ptr4 + tax + iny ; Points to size+1 + lda (ptr4),y ; High byte of left->size + adc ptr4+1 + + cpx ptr2 + bne NoLeftMerge + cmp ptr2+1 + bne NoLeftMerge ; Jump if blocks not adjacent + +; Merge with the left block. Do left->size += f->size; + + dey ; Points to size + lda (ptr4),y + add (ptr2),y + sta (ptr4),y + iny ; Points to size+1 + lda (ptr4),y + adc (ptr2),y + sta (ptr4),y + +; Set left->next = f->next and remember left->next in ptr1. + + iny ; Points to next + lda (ptr2),y ; Low byte of f->next + sta (ptr4),y + sta ptr1 + iny ; Points to next+1 + lda (ptr2),y ; High byte of f->next + sta (ptr4),y + sta ptr1+1 + ora ptr1 ; left->next == NULL? + beq @L1 + +; Do left->next->prev = left + + iny ; Points to prev + lda ptr4 ; Low byte of left + sta (ptr1),y + iny + lda ptr4+1 ; High byte of left + sta (ptr1),y + rts ; Done + +; This is now the last block, do _hlast = left + +@L1: lda ptr4 + sta __hlast + lda ptr4+1 + sta __hlast+1 + rts ; Done + +; No merge of the left block, just set the link. Y points to size+1 if +; we come here. Do left->next = f. + +NoLeftMerge: + iny ; Points to next + lda ptr2 ; Low byte of left + sta (ptr4),y + iny + lda ptr2+1 ; High byte of left + sta (ptr4),y + +; Do f->prev = left + + iny ; Points to prev + lda ptr4 + sta (ptr2),y + iny + lda ptr4+1 + sta (ptr2),y + rts ; Done -; The block is not on top of the heap. Add it to the free list. -@AddToFreeList: - lda ptr1 - ldx ptr1+1 - jsr pushax ; Push b - lda ptr2 - ldx ptr2+1 - jsr pushax ; Push size - jmp __hadd ; Add to free list and return - -- 2.39.5