6502.org Forum  Projects  Code  Documents  Tools  Forum
It is currently Thu Apr 18, 2024 10:01 pm

All times are UTC




Post new topic Reply to topic  [ 8 posts ] 
Author Message
PostPosted: Thu Apr 17, 2014 6:59 am 
Offline

Joined: Mon Apr 16, 2007 6:04 am
Posts: 155
Location: Auckland, New Zealand
Been doing more on my Orwell machine. After getting Grant's 80 col graphics processor working I have been adding some graphics functions into my version of MSBasic. Draw pixel, draw line (err, thanks again Grant - I am using your algorithm!), draw rect, etc.

Only I hit a point where adding in new commands stopped working. The machine would startup then lock up after entering the first command.

I worked out finally that the issue is I have overflowed the TOKEN_NAME_TABLE it uses to look up commands. The code used absolute indexed addressing to access the table.

Code:
L248C:
        sty     STRNG2             ; Save index into output line.
        ldy     #$00
        sty     EOLPNTR
        dey
        stx     TXTPTR             ; Save position in input line.
        dex
L2496:
        iny                        ; Y is the index into the token table.
L2497:
        inx                        ; X is the index into the line.
L2498:
        lda     INPUTBUFFERX,x      ; Get next character.
        cmp     #$20                ; Ignore spaces.
        beq     L2497

        SEC
        sbc     TOKEN_NAME_TABLE,y
        beq     L2496
        cmp     #$80
        bne     L24D7
        ora     EOLPNTR            ; Token matched.


But with the table bigger than 256 bytes it is broken. What is the most standard/easiest way to make this work with a larger table? Must be a common problem?

Store the table address as two separate bytes then loop and once Y overflows increment the high byte to access the second half of the table?

I have a feeling zero page addressing is involved somehow?

Simon

_________________
My 6502 related blog: http://www.asciimation.co.nz/bb/category/6502-computer


Top
 Profile  
Reply with quote  
PostPosted: Thu Apr 17, 2014 7:34 am 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1922
Location: Sacramento, CA, USA
Yeah, Simon, it's a common problem on any cpu with 8-bit index registers. The only two solutions that jump to mind are to compress the table or resort to (zp),y table accesses, with MSB increment whenever y tries to wrap.
On further thought, other possibilities could be to come up with a hashing function, or just splitting the table into two or more smaller tables based on the value of the first character in the search string, but those would add a layer of complexity that you might not find appealing. It sounds to me like you are easily capable of trying the (zp),y route.

Mike


Top
 Profile  
Reply with quote  
PostPosted: Thu Apr 17, 2014 7:52 am 
Online
User avatar

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8422
Location: Southern California
Yep, short of using the 65816 which allows 16-bit registers, it looks like the (ind),Y will be most efficient, something like the following. (I put the structure macro calls in it so I could better see what it's doing.)
Code:
L248C:  STY   STRNG2                  ; Save index into output line.
        STZ   EOLPNTR
        LDY   #$FF
        STX   TXTPTR                  ; Save position in input line.
        DEX

        LDA   #<TOKEN_NAME_TABLE      ; Get ADL of table
        STA   TBL_PTR                 ; and put it in low  byte of pointer in ZP.
        LDA   #{>TOKEN_NAME_TABLE}-1  ; Get ADH of table, minus 1,
        STA   TBL_PTR+1               ; and put it in high byte of pointer in ZP.

        BEGIN
            INY                       ; Y is the index into the token table.
            IF_ZERO                   ; (Just assembles a BNE around the INC.)
               INC   TBL_PTR+1        ; Increment the high byte of the ZP pointer to the table
            END_IF                    ; Table ADH gets incremented the first time, to the
                                      ; correct value, per Mike's post below.
            BEGIN
               INX                    ; X is the index into the line.
               LDA   INPUTBUFFERX,X   ; Get next character.  (L2498 was on this line, if you still need it.)
               CMP   #$20             ; Ignore spaces.
            UNTIL_NEQ                 ; (Just assembles a BEQ up to the last BEGIN.)

            SEC
            SBC   (TBL_PTR),Y         ; Now it becomes indirect indexed.
        UNTIL_NOT_ZERO                ; (Just assembles a BEQ up to the first BEGIN.)

        CMP   #$80
        IF_EQ                         ; (Just assembles a BNE to the END_IF below.)
            ORA   EOLPNTR             ; Token matched.
            ...
            ...
            ...
        END_IF                        ; (at L24D7)

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?


Last edited by GARTHWILSON on Thu Apr 17, 2014 9:28 am, edited 1 time in total.
Y starting out at FF rather than 0


Top
 Profile  
Reply with quote  
PostPosted: Thu Apr 17, 2014 8:04 am 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1922
Location: Sacramento, CA, USA
It's right before my bed-time Garth, but I think that you're going to have to start your table pointer 256 bytes lower with the LDY #$FF version or one byte lower with the LDY #0 version, because the very first INY is going to trigger an INC TBL_PTR+1 in the first case. Please correct me if I'm wrong ... I'm a bit bleary-eyed.

Mike


Top
 Profile  
Reply with quote  
PostPosted: Thu Apr 17, 2014 8:27 am 
Offline

Joined: Mon Apr 16, 2007 6:04 am
Posts: 155
Location: Auckland, New Zealand
Ah, thanks for the ideas. I had a thought and checked how it's done in the Applesoft BASIC which is also based on MSBasic but I knew Applesoft support a lot more commands so has a bigger token table. They do it using the FAC variable which already exists in the code. I think this is basically what Garth is saying and their pre DEX/DEY is what Mike is talking about?

Disassembly is from here of course: http://www.txbobsc.com/scsc/scdocumentor/D52C.html

Code:
STY STRNG2   SAVE INDEX TO OUTPUT LINE
D592- A9 D0    1650        LDA #TOKEN.NAME.TABLE-$100
D594- 85 9D    1660        STA FAC      MAKE PNTR FOR SEARCH
D596- A9 CF    1670        LDA /TOKEN.NAME.TABLE-$100
D598- 85 9E    1680        STA FAC+1
D59A- A0 00    1690        LDY #0       USE Y-REG WITH (FAC) TO ADDRESS TABLE
D59C- 84 0F    1700        STY TKN.CNTR     HOLDS CURRENT TOKEN-$80
D59E- 88       1710        DEY          PREPARE FOR "INY" A FEW LINES DOWN
D59F- 86 B8    1720        STX TXTPTR   SAVE POSITION IN INPUT LINE
D5A1- CA       1730        DEX          PREPARE FOR "INX" A FEW LINES DOWN
D5A2- C8       1740 .5     INY          ADVANCE POINTER TO TOKEN TABLE
D5A3- D0 02    1750        BNE .6       Y=Y+1 IS ENOUGH
D5A5- E6 9E    1760        INC FAC+1    ALSO NEED TO BUMP THE PAGE
D5A7- E8       1770 .6     INX          ADVANCE POINTER TO INPUT LINE
D5A8- BD 00 02 1780 .7     LDA INPUT.BUFFER,X   NEXT CHAR FROM INPUT LINE
D5AB- C9 20    1790        CMP #' '     THIS CHAR A BLANK?
D5AD- F0 F8    1800        BEQ .6       YES, IGNORE ALL BLANKS
D5AF- 38       1810        SEC          NO, COMPARE TO CHAR IN TABLE
D5B0- F1 9D    1820        SBC (FAC),Y  SAME AS NEXT CHAR OF TOKEN NAME?
D5B2- F0 EE    1830        BEQ .5       YES, CONTINUE MATCHING
D5B4- C9 80    1840        CMP #$80     MAYBE; WAS IT SAME EXCEPT FOR BIT 7?
D5B6- D0 41    1850        BNE .14      NO, SKIP TO NEXT TOKEN
D5B8- 05 0F    1860        ORA TKN.CNTR     YES, END OF TOKEN; GET TOKEN #
D5BA- C9 C5    1870        CMP #TOKEN.AT  DID WE MATCH "AT"?
D5BC- D0 0D    1880        BNE .8       NO, SO NO AMBIGUITY
D5BE- BD 01 02 1890        LDA INPUT.BUFFER+1,X  "AT" COULD BE "ATN" OR "A TO"
D5C1- C9 4E    1900        CMP #'N      "ATN" HAS PRECEDENCE OVER "AT"
D5C3- F0 34    1910        BEQ .14      IT IS "ATN", FIND IT THE HARD WAY
D5C5- C9 4F    1920        CMP #'O      "TO" HAS PRECEDENCE OVER "AT"
D5C7- F0 30    1930        BEQ .14      IT IS "A TO", FIN IT THE HARD WAY
D5C9- A9 C5    1940        LDA #TOKEN.AT     NOT "ATN" OR "A TO", SO USE "AT"


I need to go through it closely. Still a newbie, takes me a while :)

Simon

_________________
My 6502 related blog: http://www.asciimation.co.nz/bb/category/6502-computer


Top
 Profile  
Reply with quote  
PostPosted: Thu Apr 17, 2014 9:12 am 
Online
User avatar

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8422
Location: Southern California
barrym95838 wrote:
It's right before my bed-time Garth, but I think that you're going to have to start your table pointer 256 bytes lower with the LDY #$FF version or one byte lower with the LDY #0 version, because the very first INY is going to trigger an INC TBL_PTR+1 in the first case. Please correct me if I'm wrong ... I'm a bit bleary-eyed.

Darn-- You're right. He started Y at 0, stored it, then decremented it, then by the time I got down further I was thinking Y was still at 0. I'll fix it-- after I decide which way is best.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?


Top
 Profile  
Reply with quote  
PostPosted: Thu Apr 17, 2014 9:24 am 
Offline

Joined: Sat Jul 28, 2012 11:41 am
Posts: 442
Location: Wiesbaden, Germany
Another option is self modifying code. It is faster because indirect ops eat more cycles. This would require the code to be in RAM, or if you are running from ROM to have a segment of the code to be moved to RAM. EHbasic does that as part of its get current/next byte routine.
Code:
; page 0 initialisation table from $BC
; increment and scan memory

LAB_2CEE
   INC   Bpntrl      ; increment BASIC execute pointer low byte
   BNE   LAB_2CF4      ; branch if no carry
               ; else
   INC   Bpntrh      ; increment BASIC execute pointer high byte

; page 0 initialisation table from $C2
; scan memory

LAB_2CF4
   LDA   $FFFF         ; get byte to scan (addr set by call routine)
   CMP   #TK_ELSE      ; compare with the token for ELSE
   BEQ   LAB_2D05      ; exit if ELSE, not numeric, carry set

   CMP   #':'         ; compare with ":"
   BCS   LAB_2D05      ; exit if >= ":", not numeric, carry set

   CMP   #' '         ; compare with " "
   BEQ   LAB_2CEE      ; if " " go do next

   SEC            ; set carry for SBC
   SBC   #'0'         ; subtract "0"
   SEC            ; set carry for SBC
   SBC   #$D0         ; subtract -"0"
               ; clear carry if byte = "0"-"9"
LAB_2D05
   RTS
Above code is moved here during init:
Code:
LAB_IGBY      = $BC      ; get next BASIC byte subroutine

LAB_GBYT      = $C2      ; get current BASIC byte subroutine
Bpntrl      = $C3      ; BASIC execute (get byte) pointer low byte
Bpntrh      = Bpntrl+1   ; BASIC execute (get byte) pointer high byte

;         = $D7      ; end of get BASIC char subroutine
In this case the location pointed to by Bpntrl/h can be accessed as LDA (Bpntrl),Y or by calling LAB_GBYT. Calling LAB_IGBY will increment Bpntr before accessing it.

Another example in non ZP RAM from my SPI/I2C speed tests:
Code:
        ldy #hi(buf1)   ;reset self modified address
        sty rd_pio1_hi
        ldx #lo(buf1)   ;0 in this case
rd_pio1
        lda spi_165
rd_pio1_hi = *+2
        sta $1000,x     ;self modified address
        inx
        bne rd_pio1
        iny
        sty rd_pio1_hi
        cpy #(buf1>>8)+$10 ;16 pages - 4k
        bne rd_pio1
;.....
        ldy #hi(buf1)   ;reset self modified address
        sty wt_pio1_hi
        ldx #lo(buf1)   ;0 in this case
wt_pio1
wt_pio1_hi = *+2
        lda $1000,x     ;self modified address
        sta spi_595
        inx
        bne wt_pio1
        iny
        sty wt_pio1_hi
        cpy #(buf1>>8)+$10 ;16 pages - 4k
        bne wt_pio1

_________________
6502 sources on GitHub: https://github.com/Klaus2m5


Top
 Profile  
Reply with quote  
PostPosted: Thu Apr 17, 2014 8:13 pm 
Offline

Joined: Mon Apr 16, 2007 6:04 am
Posts: 155
Location: Auckland, New Zealand
I think MS Basic also does tricks with copying code into RAM from ROM. I'm having enough issues with code that doesn't change itself! But I got things working by taking the Applesoft code and using that on my machine. There are a couple of tricks though. On the Apple the input buffer isn't in ZP so there are some extra things happening there. And there is something I missed to start with when they store the two bytes of the address.

Code:
D590- 84 AD    1640 .4     STY STRNG2   SAVE INDEX TO OUTPUT LINE
D592- A9 D0    1650        LDA #TOKEN.NAME.TABLE-$100
D594- 85 9D    1660        STA FAC      MAKE PNTR FOR SEARCH
D596- A9 CF    1670        LDA /TOKEN.NAME.TABLE-$100


They have that -$100 there which is going back to what Mike was saying about the first iteration triggering the FAC+1 roll over. I got an out of range error trying to do that as they do above using CC65 so instead, after getting the high byte, I subtract 1 from it which I think does the same thing?

The code works now but needs more testing (as always).

Simon

_________________
My 6502 related blog: http://www.asciimation.co.nz/bb/category/6502-computer


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to: