From 81115aa82625f2b7e773b29844a3a7af589cdb95 Mon Sep 17 00:00:00 2001 From: IrgendwerA8 Date: Sun, 5 Mar 2017 02:09:12 +0100 Subject: [PATCH] Added further optimizations and unit tests. --- libsrc/common/memmove.s | 11 +-- libsrc/common/strcat.s | 6 +- libsrc/common/strchr.s | 6 +- libsrc/common/strcspn.s | 80 ++++++++-------- libsrc/common/strlen.s | 5 +- libsrc/common/strncat.s | 96 ++++++++++--------- libsrc/common/strspn.s | 82 ++++++++-------- libsrc/runtime/axlong.s | 16 ++-- test/val/{atoi-test.c => lib_common_atoi.c} | 0 test/val/lib_common_memmove.c | 61 ++++++++++++ .../val/lib_common_strcat.c | 2 - .../val/lib_common_strchr.c | 39 +++----- test/val/lib_common_strcspn.c | 26 +++++ test/val/lib_common_strncat.c | 54 +++++++++++ .../val/{strtol-test.c => lib_common_strol.c} | 0 .../val/lib_common_strrchr.c | 0 test/val/lib_common_strspn.c | 24 +++++ .../{strtoul-test.c => lib_common_strtoul.c} | 0 {testcode/lib => test/val}/unittest.h | 0 19 files changed, 329 insertions(+), 179 deletions(-) rename test/val/{atoi-test.c => lib_common_atoi.c} (100%) create mode 100644 test/val/lib_common_memmove.c rename testcode/lib/strcat-test.c => test/val/lib_common_strcat.c (99%) rename testcode/lib/strchr-test.c => test/val/lib_common_strchr.c (50%) create mode 100644 test/val/lib_common_strcspn.c create mode 100644 test/val/lib_common_strncat.c rename test/val/{strtol-test.c => lib_common_strol.c} (100%) rename testcode/lib/strrchr-test.c => test/val/lib_common_strrchr.c (100%) create mode 100644 test/val/lib_common_strspn.c rename test/val/{strtoul-test.c => lib_common_strtoul.c} (100%) rename {testcode/lib => test/val}/unittest.h (100%) diff --git a/libsrc/common/memmove.s b/libsrc/common/memmove.s index 9c33124f1..666447cd8 100644 --- a/libsrc/common/memmove.s +++ b/libsrc/common/memmove.s @@ -1,6 +1,6 @@ ; ; 2003-08-20, Ullrich von Bassewitz -; 2009-09-13, Christian Krueger -- performance increase (about 20%) +; 2009-09-13, Christian Krueger -- performance increase (about 20%), 2013-07-25 improved unrolling ; 2015-10-23, Greg King ; ; void* __fastcall__ memmove (void* dest, const void* src, size_t size); @@ -61,13 +61,10 @@ PageSizeCopy: ; assert Y = 0 dec ptr1+1 ; adjust base... dec ptr2+1 dey ; in entry case: 0 -> FF - lda (ptr1),y ; need to copy this 'intro byte' - sta (ptr2),y ; to 'land' later on Y=0! (as a result of the '.repeat'-block!) - dey ; FF ->FE @copyBytes: - .repeat 2 ; Unroll this a bit to make it faster... - lda (ptr1),y - sta (ptr2),y + .repeat 3 ; unroll this a bit to make it faster... + lda (ptr1),y ; important: unrolling three times gives a nice + sta (ptr2),y ; 255/3 = 85 loop which ends at 0 dey .endrepeat @copyEntry: ; in entry case: 0 -> FF diff --git a/libsrc/common/strcat.s b/libsrc/common/strcat.s index 9be65386f..74fef0759 100644 --- a/libsrc/common/strcat.s +++ b/libsrc/common/strcat.s @@ -1,6 +1,6 @@ ; ; Ullrich von Bassewitz, 31.05.1998 -; Christian Krueger: 2013-Jul-24, minor optimization +; Christian Krueger: 2013-Jul-24, minor optimizations ; ; char* strcat (char* dest, const char* src); ; @@ -15,8 +15,12 @@ _strcat: jsr popax ; Get dest sta tmp3 ; Remember for function return tay +.if (.cpu .bitand ::CPU_ISET_65SC02) + stz ptr2 +.else lda #0 sta ptr2 ; access from page start, y contains low byte +.endif stx ptr2+1 findEndOfDest: diff --git a/libsrc/common/strchr.s b/libsrc/common/strchr.s index 0bd55d0e1..48bb8822b 100644 --- a/libsrc/common/strchr.s +++ b/libsrc/common/strchr.s @@ -14,8 +14,12 @@ _strchr: jsr popax ; get s tay ; low byte of pointer to y stx ptr1+1 +.if (.cpu .bitand ::CPU_ISET_65SC02) + stz ptr1 +.else lda #0 - sta ptr1 ; ptr access page wise + sta ptr1 ; access from page start, y contains low byte +.endif Loop: lda (ptr1),y ; Get next char beq EOS ; Jump on end of string diff --git a/libsrc/common/strcspn.s b/libsrc/common/strcspn.s index 8fd567ae4..3f7b42ed1 100644 --- a/libsrc/common/strcspn.s +++ b/libsrc/common/strcspn.s @@ -1,54 +1,54 @@ ; ; Ullrich von Bassewitz, 11.06.1998 +; Christian Krueger: 05-Aug-2013, optimization ; ; size_t strcspn (const char* s1, const char* s2); ; .export _strcspn - .import popax - .importzp ptr1, ptr2, tmp1, tmp2, tmp3 + .import popax, _strlen + .importzp ptr1, ptr2, tmp1, tmp2 _strcspn: - sta ptr2 ; Save s2 - stx ptr2+1 - jsr popax ; Get s1 - sta ptr1 - stx ptr1+1 - ldx #0 ; low counter byte - stx tmp1 ; high counter byte - ldy #$00 - -L1: lda (ptr1),y ; get next char from s1 - beq L6 ; jump if done - sta tmp2 ; save char + jsr _strlen ; get length in a/x and transfer s2 to ptr1 + ; Note: It does not make sense to + ; have more than 255 test chars, so + ; we don't support a high byte here! (ptr1+1 is + ; also unchanged in strlen then (important!)) + ; -> the original implementation also + ; ignored this case + + sta tmp1 ; tmp1 = strlen of test chars + jsr popax ; get and save s1 + sta ptr2 ; to ptr2 + stx ptr2+1 + ldx #0 ; low counter byte + stx tmp2 ; high counter byte + +loadChar: + ldy #0 + lda (ptr2),y ; get next char from s1 + beq leave ; handly byte of s1 +advance: + inc ptr2 ; advance string position to test + bne check + inc ptr2+1 + dey ; correct next iny (faster/shorter than bne...) + +checkNext: iny - bne L2 - inc ptr1+1 -L2: sty tmp3 ; save index into s1 - - ldy #0 ; get index into s2 -L3: lda (ptr2),y ; - beq L4 ; jump if done - cmp tmp2 - beq L6 - iny - bne L3 - -; The character was not found in s2. Increment the counter and start over - -L4: ldy tmp3 ; reload index - inx - bne L1 - inc tmp1 - bne L1 +check: cpy tmp1 ; compare with length of test character string + beq endOfTestChars + cmp (ptr1),y ; found matching char? + bne checkNext -; The character was found, or we reached the end of s1. Return count of -; characters - -L6: txa ; get low counter byte - ldx tmp1 ; get high counter byte +leave: txa ; restore position of finding + ldx tmp2 ; and return rts - - +endOfTestChars: + inx + bne loadChar + inc tmp2 + bne loadChar ; like bra... diff --git a/libsrc/common/strlen.s b/libsrc/common/strlen.s index b583eea50..1a51edb11 100644 --- a/libsrc/common/strlen.s +++ b/libsrc/common/strlen.s @@ -1,6 +1,10 @@ ; ; Ullrich von Bassewitz, 31.05.1998 ; +; Note: strspn & strcspn call internally this function and rely on +; the usage of only ptr1 here! Keep in mind when appling changes +; and check the other implementations too! +; ; int strlen (const char* s); ; @@ -23,4 +27,3 @@ L1: lda (ptr1),y L9: tya ; get low byte of counter, hi's all set rts - diff --git a/libsrc/common/strncat.s b/libsrc/common/strncat.s index b7bb04b2a..42717853f 100644 --- a/libsrc/common/strncat.s +++ b/libsrc/common/strncat.s @@ -1,5 +1,6 @@ ; ; Ullrich von Bassewitz, 31.05.1998 +; Christian Krueger: 12-Aug-2013, minor optimizations ; ; char* strncat (char* dest, const char* src, size_t n); ; @@ -9,64 +10,65 @@ .importzp ptr1, ptr2, ptr3, tmp1, tmp2 _strncat: - eor #$FF ; one's complement to count upwards - sta tmp1 - txa - eor #$FF - sta tmp2 - jsr popax ; get src - sta ptr1 - stx ptr1+1 - jsr popax ; get dest - sta ptr2 - stx ptr2+1 - sta ptr3 ; remember for function return - stx ptr3+1 - ldy #0 + eor #$FF ; one's complement to count upwards + sta tmp1 + txa + eor #$FF + sta tmp2 + + jsr popax ; get src + sta ptr1 + stx ptr1+1 -; find end of dest + jsr popax ; get dest + sta ptr3 ; remember for function return + stx ptr3+1 + stx ptr2+1 + tay ; low byte as offset in Y +.if (.cpu .bitand ::CPU_ISET_65SC02) + stz ptr2 +.else + ldx #0 + stx ptr2 ; destination on page boundary +.endif -L1: lda (ptr2),y - beq L2 - iny - bne L1 - inc ptr2+1 - bne L1 +; find end of dest -; end found, get offset in y into pointer +L1: lda (ptr2),y + beq L2 + iny + bne L1 + inc ptr2+1 + bne L1 -L2: tya - clc - adc ptr2 - sta ptr2 - bcc L3 - inc ptr2+1 +; end found, apply offset to dest ptr and reset y +L2: sty ptr2 ; copy src. We've put the ones complement of the count into the counter, so ; we'll increment the counter on top of the loop -L3: ldy #0 - ldx tmp1 ; low counter byte +L3: ldy #0 + ldx tmp1 ; low counter byte -L4: inx - bne L5 - inc tmp2 - beq L6 ; jump if done -L5: lda (ptr1),y - sta (ptr2),y - beq L7 - iny - bne L4 - inc ptr1+1 - inc ptr2+1 - bne L4 +L4: inx + bne L5 + inc tmp2 + beq L6 ; jump if done +L5: lda (ptr1),y + sta (ptr2),y + beq L7 + iny + bne L4 + inc ptr1+1 + inc ptr2+1 + bne L4 ; done, set the trailing zero and return pointer to dest -L6: lda #0 - sta (ptr2),y -L7: lda ptr3 - ldx ptr3+1 - rts +L6: lda #0 + sta (ptr2),y +L7: lda ptr3 + ldx ptr3+1 + rts diff --git a/libsrc/common/strspn.s b/libsrc/common/strspn.s index f8b8fff2a..3316f0dab 100644 --- a/libsrc/common/strspn.s +++ b/libsrc/common/strspn.s @@ -1,56 +1,54 @@ ; ; Ullrich von Bassewitz, 11.06.1998 +; Christian Krueger: 08-Aug-2013, optimization ; ; size_t strspn (const char* s1, const char* s2); ; .export _strspn - .import popax - .importzp ptr1, ptr2, tmp1, tmp2, tmp3 + .import popax, _strlen + .importzp ptr1, ptr2, tmp1, tmp2 _strspn: - sta ptr2 ; Save s2 - stx ptr2+1 - jsr popax ; get s1 - sta ptr1 - stx ptr1+1 - ldx #0 ; low counter byte - stx tmp1 ; high counter byte - ldy #$00 - -L1: lda (ptr1),y ; get next char from s1 - beq L6 ; jump if done - sta tmp2 ; save char - iny - bne L2 - inc ptr1+1 -L2: sty tmp3 ; save index into s1 - - ldy #0 ; get index into s2 -L3: lda (ptr2),y ; - beq L6 ; jump if done - cmp tmp2 - beq L4 + jsr _strlen ; get length in a/x and transfer s2 to ptr1 + ; Note: It does not make sense to + ; have more than 255 test chars, so + ; we don't support a high byte here! (ptr1+1 is + ; also unchanged in strlen then (important!)) + ; -> the original implementation also + ; ignored this case + + sta tmp1 ; tmp1 = strlen of test chars + jsr popax ; get and save s1 + sta ptr2 ; to ptr2 + stx ptr2+1 + ldx #0 ; low counter byte + stx tmp2 ; high counter byte + +loadChar: + ldy #0 + lda (ptr2),y ; get next char from s1 + beq leave ; handly byte of s1 +advance: + inc ptr2 ; advance string position to test + bne check + inc ptr2+1 + dey ; correct next iny (faster/shorter than bne...) + +checkNext: iny - bne L3 +check: cpy tmp1 ; compare with length of test character string + beq leave + cmp (ptr1),y ; found matching char? + bne checkNext -; The character was found in s2. Increment the counter and start over - -L4: ldy tmp3 ; reload index +foundTestChar: inx - bne L1 - inc tmp1 - bne L1 - -; The character was not found, or we reached the end of s1. Return count of -; characters + bne loadChar + inc tmp2 + bne loadChar ; like bra... -L6: txa ; get low counter byte - ldx tmp1 ; get high counter byte +leave: txa ; restore position of finding + ldx tmp2 ; and return rts - - - - - - + \ No newline at end of file diff --git a/libsrc/runtime/axlong.s b/libsrc/runtime/axlong.s index 6d97b5025..02d0a825c 100644 --- a/libsrc/runtime/axlong.s +++ b/libsrc/runtime/axlong.s @@ -1,5 +1,6 @@ ; ; Ullrich von Bassewitz, 25.10.2000 +; Christian Krueger, 02-Mar-2017, some bytes saved ; ; CC65 runtime: Convert int in ax into a long ; @@ -9,18 +10,13 @@ ; Convert AX from int to long in EAX +axlong: ldy #$ff + cpx #$80 ; Positive? + bcs store ; No, apply $FF + axulong: ldy #0 - sty sreg - sty sreg+1 - rts - -axlong: cpx #$80 ; Positive? - bcc axulong ; Yes, handle like unsigned type - ldy #$ff - sty sreg +store: sty sreg sty sreg+1 rts - - diff --git a/test/val/atoi-test.c b/test/val/lib_common_atoi.c similarity index 100% rename from test/val/atoi-test.c rename to test/val/lib_common_atoi.c diff --git a/test/val/lib_common_memmove.c b/test/val/lib_common_memmove.c new file mode 100644 index 000000000..dd5801569 --- /dev/null +++ b/test/val/lib_common_memmove.c @@ -0,0 +1,61 @@ +#include +#include "unittest.h" + +#define BufferSize 384 // test correct page passing (>256, multiple of 128 here) + +static char Buffer[BufferSize+3]; // +1 to move up (and down) + + + +TEST +{ + unsigned i, v; + char* p; + + for (i=0; i < BufferSize; ++i) + Buffer[i+1] = (i%128); + + Buffer[0] = 255; // to check if start position is untouched + Buffer[BufferSize+2] = 255; // to check if end position is untouched + + // copy upwards + p = memmove(Buffer+2, Buffer+1, BufferSize); + + // check buffer consistency before target + ASSERT_AreEqual(255, (unsigned)Buffer[0], "%u", "Unexpected value before range!"); + + // check buffer consistency at starting point + ASSERT_AreEqual(0, (unsigned)Buffer[1], "%u", "Unexpected value at range start!"); + + // check buffer consistency after range + ASSERT_AreEqual(255, (unsigned)Buffer[BufferSize+2], "%u", "Unexpected value after range!"); + + // check buffer values + for (i=0; i < BufferSize; ++i) + { + ASSERT_AreEqual(i%128, (unsigned)Buffer[i+2], "%u", "Unexpected value in buffer at position %u!" COMMA i+2); + } + + v = Buffer[BufferSize+1]; // rember value of first untouched end-byte + + // copy downwards + p = memmove(Buffer+1, Buffer+2, BufferSize); + + // check buffer consistency before target + ASSERT_AreEqual(255, (unsigned)Buffer[0], "%u", "Unexpected value before range!"); + + // check buffer consistency at end point + ASSERT_AreEqual(v, (unsigned)Buffer[BufferSize+1], "%u", "Unexpected value at range end!"); + + // check buffer consistency after range + ASSERT_AreEqual(255, (unsigned)Buffer[BufferSize+2], "%u", "Unexpected value after range!"); + + // check buffer values + for (i=0; i < BufferSize; ++i) + { + ASSERT_AreEqual(i%128, (unsigned)Buffer[i+1], "%u", "Unexpected value in buffer at position %u!" COMMA i+1); + } +} +ENDTEST + + diff --git a/testcode/lib/strcat-test.c b/test/val/lib_common_strcat.c similarity index 99% rename from testcode/lib/strcat-test.c rename to test/val/lib_common_strcat.c index 58119e27a..1872053a4 100644 --- a/testcode/lib/strcat-test.c +++ b/test/val/lib_common_strcat.c @@ -52,5 +52,3 @@ TEST } } ENDTEST - - diff --git a/testcode/lib/strchr-test.c b/test/val/lib_common_strchr.c similarity index 50% rename from testcode/lib/strchr-test.c rename to test/val/lib_common_strchr.c index 7aba1de1e..a48d287e5 100644 --- a/testcode/lib/strchr-test.c +++ b/test/val/lib_common_strchr.c @@ -1,7 +1,5 @@ -#include -#include #include - +#include "unittest.h" /* Test string. Must NOT have duplicate characters! */ @@ -11,49 +9,34 @@ static char Found[256]; -int main (void) +TEST { unsigned Len; unsigned I; char* P; - /* Print a header */ - printf ("strchr(): "); - /* Get the length of the string */ Len = strlen (S); /* Search for all characters in the string, including the terminator */ - for (I = 0; I < Len+1; ++I) { - + for (I = 0; I < Len+1; ++I) + { /* Search for this char */ P = strchr (S, S[I]); /* Check if we found it */ - if (P == 0 || (P - S) != I) { - printf ("Failed for code 0x%02X, offset %u!\n", S[I], I); - printf ("P = %04X offset = %04X\n", P, P-S); - exit (EXIT_FAILURE); - } - + ASSERT_IsFalse(P == 0 || (P - S) != I, "For code 0x%02X, offset %u!\nP = %04X offset = %04X\n" COMMA S[I] COMMA I COMMA P COMMA P-S); /* Mark the char as checked */ Found[S[I]] = 1; } /* Search for all other characters and make sure they aren't found */ - for (I = 0; I < 256; ++I) { - if (Found[I] == 0) { - if (strchr (S, (char)I) != 0) { - printf ("Failed for code 0x%02X\n", I); - exit (EXIT_FAILURE); - } + for (I = 0; I < 256; ++I) + { + if (Found[I] == 0) + { + ASSERT_IsFalse(strchr (S, (char)I), "Failed for code 0x%02X\n" COMMA I); } } - - /* Test passed */ - printf ("Passed\n"); - return EXIT_SUCCESS; } - - - +ENDTEST diff --git a/test/val/lib_common_strcspn.c b/test/val/lib_common_strcspn.c new file mode 100644 index 000000000..10935a78e --- /dev/null +++ b/test/val/lib_common_strcspn.c @@ -0,0 +1,26 @@ +#include +#include "unittest.h" + +#define EstimatedStringSize 384 // test correct page passing (>256) + +static char EstimatedString[EstimatedStringSize+1]; // +1 room for terminating null +static char* EmptyTestChars=""; // strlen equivalent... +static char* TestChars="1234567890"; // we like to find numbers + +TEST +{ + unsigned i; + + for (i=0; i < EstimatedStringSize; ++i) + EstimatedString[i] = (i%26)+'A'; // put ABCD... into the string to be estimated + + ASSERT_AreEqual(strlen(EstimatedString), strcspn(EstimatedString, TestChars), "%u", "Unxpected position returned for non-participant case!"); + + EstimatedString[EstimatedStringSize/2] = TestChars[strlen(TestChars-1)]; + ASSERT_AreEqual(EstimatedStringSize/2, strcspn(EstimatedString, TestChars), "%u", "Unxpected position returned for participant case!"); + + ASSERT_AreEqual(strlen(EstimatedString), strcspn(EstimatedString, EmptyTestChars), "%u", "Unxpected position returned for empty test case!"); +} +ENDTEST + + diff --git a/test/val/lib_common_strncat.c b/test/val/lib_common_strncat.c new file mode 100644 index 000000000..dd6df9147 --- /dev/null +++ b/test/val/lib_common_strncat.c @@ -0,0 +1,54 @@ +#include +#include "unittest.h" + +#define SourceStringSize 384 // test correct page passing (>256, multiple of 128 here) + +static char SourceString[SourceStringSize+1]; // +1 room for terminating null +static char DestinationString[2*SourceStringSize+1]; // will contain two times the source buffer + + +TEST +{ + unsigned i; + char* p; + + for (i=0; i < SourceStringSize; ++i) + SourceString[i] = (i%128)+1; + + SourceString[i] = 0; + + ASSERT_AreEqual(SourceStringSize, strlen(SourceString), "%u", "Source string initialization or 'strlen()' problem!"); + + /* Ensure empty destination string */ + DestinationString[0] = 0; + + ASSERT_AreEqual(0, strlen(DestinationString), "%u", "Destination string initialization or 'strlen()' problem!"); + + /* Test "unlimted" concatenation to empty buffer */ + + strncat(DestinationString, SourceString, 1024); + + ASSERT_AreEqual(SourceStringSize, strlen(DestinationString), "%u", "Unexpected string length while string concatenation to empty buffer!"); + + /* Test limited concatenation to non empty buffer */ + + p = strncat(DestinationString, SourceString, 128); + + ASSERT_AreEqual(SourceStringSize+128, strlen(DestinationString), "%u", "Unexpected string length while string concatenation to non-empty buffer!"); + + /* Test return value */ + + ASSERT_IsTrue(p == DestinationString, "Invalid return value!"); + + /* Test contents */ + + for(i=0; i < strlen(DestinationString); ++i) + { + unsigned current = DestinationString[i]; + unsigned expected = (i%128)+1; + ASSERT_AreEqual(expected, current, "%u", "Unexpected destination buffer contents at position %u!\n" COMMA i); + } +} +ENDTEST + + diff --git a/test/val/strtol-test.c b/test/val/lib_common_strol.c similarity index 100% rename from test/val/strtol-test.c rename to test/val/lib_common_strol.c diff --git a/testcode/lib/strrchr-test.c b/test/val/lib_common_strrchr.c similarity index 100% rename from testcode/lib/strrchr-test.c rename to test/val/lib_common_strrchr.c diff --git a/test/val/lib_common_strspn.c b/test/val/lib_common_strspn.c new file mode 100644 index 000000000..96a006469 --- /dev/null +++ b/test/val/lib_common_strspn.c @@ -0,0 +1,24 @@ +#include +#include "unittest.h" + +#define EstimatedStringSize 384 // test correct page passing (>256) + +static char EstimatedString[EstimatedStringSize+1]; // +1 room for terminating null +static char* EmptyTestChars=""; // empty test case... +static char* TestChars="1234567890"; // we like to find numbers + +TEST +{ + unsigned i; + + for (i=0; i < EstimatedStringSize; ++i) + EstimatedString[i] = (i%10)+'0'; // put 0123... into the string to be estimated + + ASSERT_AreEqual(strlen(EstimatedString), strspn(EstimatedString, TestChars), "%u", "Unxpected position returned for all participant case!"); + + EstimatedString[EstimatedStringSize/2] = 'X'; + ASSERT_AreEqual(EstimatedStringSize/2, strspn(EstimatedString, TestChars), "%u", "Unxpected position returned for breaking case!"); + + ASSERT_AreEqual(0, strspn(EstimatedString, EmptyTestChars), "%u", "Unxpected position returned for empty test case!"); +} +ENDTEST diff --git a/test/val/strtoul-test.c b/test/val/lib_common_strtoul.c similarity index 100% rename from test/val/strtoul-test.c rename to test/val/lib_common_strtoul.c diff --git a/testcode/lib/unittest.h b/test/val/unittest.h similarity index 100% rename from testcode/lib/unittest.h rename to test/val/unittest.h -- 2.39.5