Friday, June 13, 2014

StrNCpy and StrNCmp

Copying strings is pretty much just your regular memory copy operation with a couple of twists. First, we have no idea how many bytes need to be copied. Second, we need to make sure to write a zero at the end of the string so that the copied string will always be a valid string.

This function requires two pointers be set up. The SOURCE_PTR points to string to be copied while the DEST_PTR pointer where string is copied to. We also use the X Register to hold the maximum length of the string (including null terminator) to be copied, with a length of 0 being an entire page.

First we set the character to copy to zero. We then use zero page indirect addressing to load a character from the source string. If this character is a zero then the copying is done. Because our last action is always to write an ending zero, we can branch right to our ending code. If not a zero then we write the character to the destination location.

StrNCpy:
        LDY #0
StrNCpy_loop:
        LDA [SOURCE_PTR],Y
        BEQ StrNCpy_done
        STA [DEST_PTR],Y

The X Register is deducted to make sure the maximum copy length had not been reached. If it has been then we force an overwrite of the last character with a zero.

        DEX
        BEQ StrNCpy_lengthReached
        INY
        JMP StrNCpy_loop
StrNCpy_lengthReached:
        LDA #0  ; Make sure last character a zero
StrNCpy_done:
        STA [DEST_PTR],Y
        RTS

String comparison is fairly similar which makes it a fairly costly operation. The longer the strings being compared the longer the operation will take. This is why it irks me when I see programmers use strings when integer constants could be used. This is thankfully not as bad a situation as it could be. Many string class libraries use hash values when comparing strings. This technique has the cost of computing a hash value, but if strings are immutable as they are in many modern languages then the hash value will only be computed once. While hash values result in a simple and fast integer comparison for non-matching strings, hashes are not  unique so if a match is found then you still need to check each character to make sure the strings match.

We are not computing or checking hash values, but are checking if the source and destination pointers are the same. This takes a few cycles but can save a lot of work. This also lets us cheat by using string pointers as our integer constants for prompts and other text-based menus.

StrNCmp:
        LDY #0
        LDA SOURCE_PTR
        CMP DEST_PTR
        BNE StrNCmp_compareLoop
        LDA SOURCE_PTR+1
        CMP DEST_PTR+1
        BNE StrNCmp_compareLoop
        ; If we reach here, same pointer so must match
        LDA #0
        RTS

The second phase is a byte by byte comparison of the strings. The logic here is pretty similar to the string copy except we are comparing instead of copying.

StrNCmp_compareLoop:
        LDA [SOURCE_PTR],Y
        BEQ StrNCmp_done
        CMP [DEST_PTR],Y
        BNE StrNCmp_done
        DEX             ; Make sure not comparing beyond limit
        BEQ StrNCmp_done
        INY             ; Now set next byte and continue
        JMP StrNCmp_compareLoop

Finally we determine the comparison result. We do this the same way the CMP instruction does by simply subtracting the compared byte from the source byte.

StrNCmp_done:
        SEC
        SBC [DEST_PTR],Y
        RTS

That covers the most important parts of our string library but there are still a few functions that I want to write which will be covered next.

No comments: