Page 1 of 1
Efficient memmove()
Posted: Wed Oct 16, 2024 6:44 pm
by barnacle
I haven't started coding 6502 for my tiny basic, but one thing it's going to need is a memmove() that is capable of operating in both directions so it can move to an area its already occupying (i.e. C memmove() rather than memcpy()). It'll need to be able to move at least 32k...
It shouldn't be too complex to implement, but I'm feeling lazy and wondered if anyone had such a thing in their toolkit?
My API is expected to call with parameter 1 (destination) in Y:A, with parameters 2 and 3 (source and length) pushed on the stack before calling - parameter 3 first. A single return value would be in Y:A; the calling routine is responsible for tidying the stack up.
There is at the moment shedloads of page zero memory hanging around doing nothing.
Neil
Re: Efficient memmove()
Posted: Wed Oct 16, 2024 10:33 pm
by Yuri
Re: Efficient memmove()
Posted: Thu Oct 17, 2024 5:58 pm
by teamtempest
Dunno how you've arranged things, but I chose the easiest possible mechanism when I implemented such a thing a few years ago in a Tiny BASIC. As I recall, one of the longest routines I needed to write:
Code: Select all
; ISRT opcode - insert BASIC text line (aka INSRT)
opcode ISRT
; txtPtr points into input buffer
jsr chrGot
sty data1 ; offset of first non-space after line#
beq + ; b: first non-space is end of line
jsr skipTxtEnd ; skip to end of line
+ tya
sbc data1 ; (carry is set)
sta data1+1 ; # text bytes to insert
; look for an existing BASIC line with same line#
; - after this txtPtr points into BASIC program text
; at the point any insertion/deletion should happen
jsr findLine
bcs isrt1 ; b: not found
; delete BASIC line
; - the easy way, just by copying each following line down
ldx #addr1 ; ... is also destination start address
jsr moveTxtPtr
jsr skipTxtEnd ; find start of next line
jsr setTxtNext
ldx #addr0 ; ...which is also source start address
jsr moveTxtPtr
lda addr1 ; put this back for possible insertion later
ldx addr1+1
sta txtPtr
stx txtPtr+1
; check if we've reached end of BASIC text
; - which we have right away if we're deleting last line
]loop ldy #0 ; copy line#
lda (addr0),y
sta (addr1),y
iny
lda (addr0),y
sta (addr1),y
ldx #0
ora (addr1,x)
beq del1 ; b: end of deletion
- iny
lda (addr0),y
sta (addr1),y
cmp #CH_CR ; copied line ?
bne - ; b: no
tya ; point source to start of next line
adc addr0
sta addr0
bcc +
inc addr0+1
+ sec ; update destination by the same amount
tya
adc addr1
sta addr1
bcc ]loop
inc addr1+1
bcs ]loop
del1 lda addr1
ldx addr1+1
jsr setTxtEnd ; update end of text pointer
; make room for any new BASIC line
isrt1 lda data1+1 ; how much space do we need ?
beq isrt2 ; none, so done
; make space for new BASIC line
clc
lda txtEnd
sta addr0 ; set source end address lo
adc #2+1 ; account for line# plus end of line bytes
adc data1+1 ; (must be < 254)
ldx txtEnd+1
stx addr0+1 ; source end address hi
bcc +
inx ; BASIC lines always < 256 chars
+ cpx memTop+1
bcc + ; b: < memTop
cmp memTop
bcc + ; b: < memTop
jmp errMem ; >= memTop
+ sta txtEnd ; new end of BASIC
stx txtEnd+1
sta addr1 ; ..also destination end address hi
stx addr1+1
sec ; how many bytes to move ?
lda addr0
sbc txtPtr
tay ; partial page count
lda addr0+1
sbc txtPtr+1
tax ; whole page count
inx ; ...plus one
tya
beq mksp2 ; b: no partial page to move
sta data2
sec
lda addr0 ; adjust source end
sbc data2
sta addr0
bcs +
dec addr0+1
sec
+ lda addr1 ; adjust destination end
sbc data2
sta addr1
bcs mksp1
dec addr1+1
bcc mksp1 ; b: forced
]loop lda (addr0),y ; copy up to 255 bytes
sta (addr1),y
mksp1 dey
bne ]loop
lda (addr0),y ; copy last byte
sta (addr1),y
mksp2 dec addr0+1
dec addr1+1
dex
bne mksp1
; insert new BASIC line
ldy #0
lda linNum
sta (txtPtr),y ; (points at insertion address)
iny
lda linNum+1
sta (txtPtr),y
ldx data1 ; offset into input buffer of start of BASIC text
]loop lda inpBuf,x
iny
sta (txtPtr),y
inx
cmp #CH_CR
bne ]loop
isrt2 rts
Re: Efficient memmove()
Posted: Thu Oct 17, 2024 7:11 pm
by barnacle
Thanks guys; I need to study those in some detail.
At the moment, the C version makes use (obviously) of memmove:
- First, squishbuffer() moves things around in the input text buffer to replace the line number with a 16 bit integer, converts all the tokens to single bytes, gets rid of leading space, and sticks a length byte in as the third byte in the string.
- findline() searches the whole of the memory space to find a line either matching or above the requested line, or a zero if it gets past the last line; it returns the line number and also sets a global pointer to the memory (naughty naughty).
- storeline() matches the line number in the buffer with the program store (findline()) and then either adds the line to the end of the store, deletes the line (if the buffer is just a number), makes a space for a new line in the store, or shuffles the store to allow a new line to replace an existing one.
It all seems to work. But I'll have to see how it looks as 65c02 code.
Neil
p.s. the code which handles print and let works identically with either the input buffer or a pointer to a specified line in memory.