6502.org Forum  Projects  Code  Documents  Tools  Forum
It is currently Fri Nov 01, 2024 8:26 am

All times are UTC




Post new topic Reply to topic  [ 321 posts ]  Go to page Previous  1 ... 7, 8, 9, 10, 11, 12, 13 ... 22  Next
Author Message
PostPosted: Wed Apr 19, 2017 3:55 am 
Offline

Joined: Sat Mar 11, 2017 1:56 am
Posts: 276
Location: Lynden, WA
Hey guys! Been a bit since I've been able to work on things. Wife and kids all got colds, and I had to tend to my domestic duties :) .

I am working on the command parser for my monitor. A few here have suggested single letter commands, which would definitely be much easier, but I'd rather have the learning experience of using actual words.

Ok, the way I'm leaning is to have all the commands stored in ROM, all NULL terminated. I will have the user type in a command (let's ignore the possibility of command arguments for now), and the program will compare each command to the typed command until there is a match. I thought about having it be smart enough to use alphabetical order in order to not compare more commands then necessary, instead of brute force, but I don't think I'll have enough commands to make that kinda thing needed. Maybe later just for the exercise of it.

I want to have an array of addresses that I can index through, that contains the address of each of the commands. That is how I figure I can navigate a list of strings of varying length.

There lies my question. I can put such a list in ROM, but my understanding is there is no way to use indirection if the pointers are anywhere other than 0 page. Does this suggest that part of my reset routine should be to load an array in 0 page from ROM? It seems inefficient to have the same data in two places at once (the original in ROM, and the copy in 0 page), but I can't see another way.

Is this the way?


Top
 Profile  
Reply with quote  
PostPosted: Wed Apr 19, 2017 4:52 am 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1948
Location: Sacramento, CA, USA
I wouldn't recommend moving large tables of pointers from ROM to zero-page unless the situation really required it. What I might do is keep a list of "counted strings" in ROM, and just traverse it using absolute,X or absolute,Y. The strings are stored one after the other, with the first byte of each string being its length. You know the length of the word you're trying to match, so that could be the first thing you check. If the lengths don't match, then you use the counted string length to advance your index register to the next candidate. If the lengths do match, then you can start a character-by-character comparison to find the perfect match. If you fail to get the perfect match, you can use the length of the failed candidate to advance to the next potential candidate, until you run out of possibilities (for example, with a trailing string of length zero) and respond with an error. You really shouldn't need any zero page pointers at all for this particular task, unless your string list is larger than 256 bytes. You would probably need a few bytes of zero page to keep track of some temporary values, like the current string length and the saved index before starting a detailed comparison of a string candidate.

This "counted string" method I'm suggesting may not be the most efficient, but it could be a good learning exercise for you, if you don't wish to try the methods used by Woz or Gates (or Wilson) in their 65xx BASIC parsers.

Mike B.


Top
 Profile  
Reply with quote  
PostPosted: Wed Apr 19, 2017 4:58 am 
Offline
User avatar

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8534
Location: Southern California
Dan Moos wrote:
I want to have an array of addresses that I can index through, that contains the address of each of the commands. That is how I figure I can navigate a list of strings of varying length.

There lies my question. I can put such a list in ROM, but my understanding is there is no way to use indirection if the pointers are anywhere other than 0 page. Does this suggest that part of my reset routine should be to load an array in 0 page from ROM? It seems inefficient to have the same data in two places at once (the original in ROM, and the copy in 0 page), but I can't see another way.

Is this the way?

If I'm understanding correctly what you want to do, JMP (<addr>,X) will do the job (where <addr> is the 16-bit absolute address of the beginning of the table). It's op code 7C. If for some reason you did need ZP, you can just put the one address there in a two-byte variable, rather than put the whole table there.

_________________
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: Wed Apr 19, 2017 5:19 am 
Offline
User avatar

Joined: Thu May 28, 2009 9:46 pm
Posts: 8468
Location: Midwestern USA
Dan Moos wrote:
Ok, the way I'm leaning is to have all the commands stored in ROM, all NULL terminated...It seems inefficient to have the same data in two places at once (the original in ROM, and the copy in 0 page), but I can't see another way.

Some thoughts for you...I'm not going to design the code for you but give you enough wheat so you can mill your flour and bake some bread.

  • Methods. If a word list is in ASCII order, which is alphabetic if only the A-Z and a-z characters are used, you can examine the list for a match using a binary search. However, a binary search is inefficient with small lists. Your alternative is a linear search. At machine language speeds the user is not going to notice the difference, even with a list of 50-or-so words. So I would use a linear search.

  • List structure. You have the choice of null-terminating each word or preceding each word with a byte that is the length of the word. In either case, word comparisons are byte-by-byte, with the comparison failing as soon as the bytes being compared differ. Preceding a word with its length has a slight advantage in performance in that a search can first compare word lengths and only if the lengths are equal would a byte-by-byte comparison be done.

  • Search and compare. As your command words will be of varying lengths a pointer table must be used to pick a word for comparison to user input. Pointers are 16 bits, therefore you would step through the pointer table two bytes at a time. You start at one end of the table, using a zero-based index. A copy of the index is doubled and used as an offset into your word pointer table. The pointer to which the offset is pointing is copied to zero page so indirection can be used to perform the actual comparison. If the comparison fails you increment the index and repeat the process until the entire list has been examined.

  • Function execution. If the comparison succeeds you use the same offset that was used on the word pointer table to select a function address from a table of such addresses. The JMP (<addr>,X) instruction may be used to run the function. Alternatively, you can push the function address minus one to the stack and then execute RTS to run the function. I use the latter method in Supermon 816.

Indirection is the key, as it usually is in much 6502 software. However, there is no reason to keep a static table in zero page. The pointers can be copied on the fly.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!


Top
 Profile  
Reply with quote  
PostPosted: Wed Apr 19, 2017 5:37 am 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
I trick I've seen used in the Acorn Atom ROM OS, is to have the ASCII text of the keywords terminated by the subroutine address. Because the addresses are all in ROM ($F000 and higher), and they were stored MSB first, the BPL/BMI instruction can be used to find the end of the words.

The biggest advantage of this method is that everything is contained in the same table, so you can make a general purpose routine for comparing a word, and jumping to the right place. This could be useful for parsing extra arguments, e.g. you first jump on the command word, and then for certain command words, you can jump again based on the argument.


Top
 Profile  
Reply with quote  
PostPosted: Wed Apr 19, 2017 6:10 am 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
A more difficult, but really fast way to lookup a constant set of words is by using a perfect hash.

The idea is that you go through the letters of the word, and you perform a (simple) mathematical function, to combine all letters into a single number, that you then use as index in a lookup table. The function should be chosen so that each word maps to a unique number, and that the numbers are small enough to be used as indexes. The lookup table can then contain the original word, so you can make sure it was entered correctly, plus the address of the routine.


Top
 Profile  
Reply with quote  
PostPosted: Fri Apr 21, 2017 3:53 am 
Offline

Joined: Sat Mar 11, 2017 1:56 am
Posts: 276
Location: Lynden, WA
Ok, BDD kinda described what I want to do, and I think he answered my question.

Basically, I have my list of pointers to the command strings in ROM, I index through them like I planned, and just copy the current pointer into 0 page, rather than having the whole thing there to begin with.

Actually, a pretty obvious plan now that I think of it.

While we are on the subject of this kinda thing, it got me thinking about memory management in general. Lets say I have my monitor running, and lets say it has the capability to load and execute a program in RAM. (maybe it's more of a OS at that point. The definitions here seem blurry to me.). Ok, is it standard for the monitor to be completely ended, and every memory resource to be released (abandoned is probably a better word)? That seems unlikely, since then you couldn't re-start the monitor with out a hardware reset.

How is this usually done? I know I could use interrupts to get back into the monitor, but if the running application has control of the keyboard, how would you do that?

For instance, lets say my interrupt vectors in ROM just eventually get you to some ISR's in RAM that the loaded app supplies, (or the monitor when its running). I could have some key sequence trigger a software interrupt, but the loaded app would have still have to know how to get the monitor going again.

Or am I making this too complicated? Could I just ensure that any program I run from RAM knows to exit by restarting the monitor (OS)? I realize that you could just press the reset button, but that seems primitive. Of course this is a fairly primitive computer with limited resources, so...


Top
 Profile  
Reply with quote  
PostPosted: Fri Apr 21, 2017 10:03 am 
Offline
User avatar

Joined: Wed Mar 01, 2017 8:54 pm
Posts: 660
Location: North-Germany
The monitor I grew up with has a dedicated memory region (that could be write protected) where a few bytes were reserved for "registers" (a copy of A,X,Y,F,S,PC). When I started a self written program at $0200 I typed "G 0200". Then these "registers" were loaded into the 6502, the stack was reset to $01FF and a JSR to my program was executed.
In that way my programs could return to monitor simply by using a RTS. The monitor then saves A,X,Y,F into these "registers" memory, and then enters the main waiting for command loop. There I could inspect these "registers" if I wish, using the proper command.
As long as my SW didn't ruin other settings (like baudrate, I/O vectors, etc.) everything was fine.

addit:
The monitor itself was very well designed. A pretty short "mainloop" (check for an entry - process the entry - loop) and tons of subroutines. With proper setup of A,X,Y and perhaps RAM I could use many of these routines out of my software, like looking for any key is pressed, scan keyboard, outchar, outhex, out2hex (= print an address) and lots more. Even interrupt processing with monitor assistance was possible. The monitor setup 3 JMPs in RAM (so I could change the destination) for NMI-, IRQ-, and BRK-processing. So I could selectively alter one of these JMPs to go to a program I provided. Leaving these JMPs untouched simply calls monitor routines that printed a message like "IRQ at $1A2B" and then a list of the registers. Then the monitor waits what to do. I could use "G" without an adress to continue IIRC.

So if you design your monitor in a similar fashion, most of it could be used by your applications. And if your application need to change too much, so the monitor wouldn't work anymore, don't use RTS but do a JMP (ResetVector) to get back to the monitor. This should reorganize everything.


Top
 Profile  
Reply with quote  
PostPosted: Sat Apr 22, 2017 4:02 am 
Offline

Joined: Sat Dec 13, 2003 3:37 pm
Posts: 1004
On simple systems, the monitor stays in memory (ROM typically). As was mentioned, your program was typically JSRd to, and a simple RTS would return to the monitor. Typically BRK faulted to the monitor as well, ideally taking care to be able to resume the program.

Interrupts are typically handled by the monitor also, as the monitor provides the nascent I/O routines that programs tend to use.

Naturally, a program is free to disregard all of this: clear off the stack, reset the BRK or other interrupt vectors, overwrite known monitor memory locations.

As you move up to disk based systems, then there's usually no monitor at all, rather a loader. It loads from the disk using some well know booting process. The basic system with a command processor will leave the basic BIOS in place, but lose the command shell, and have it reloaded and reinitialized when the program gracefully returns, in order to free up resources.

A counter example of this is the old school "TSRs" or MS-DOS, or "Terminate and Stay Resident", software that once loaded actually remained in memory rather than having it released automatically by the system.


Top
 Profile  
Reply with quote  
PostPosted: Sat Apr 22, 2017 4:09 am 
Offline

Joined: Sat Mar 11, 2017 1:56 am
Posts: 276
Location: Lynden, WA
Funny you should mention TSRs. I was wracking my brain trying to remember that term, so I could ask if that was a valid method in a such a simple computer. I totally remember using TSRs on DOS machines.


Top
 Profile  
Reply with quote  
PostPosted: Mon Apr 24, 2017 1:33 am 
Offline

Joined: Sat Mar 11, 2017 1:56 am
Posts: 276
Location: Lynden, WA
Ok, here's a question.

I am coding my command parser, and it's just about done. But I've hit a snag.

I didn't realize that JSR only supports absolute addressing.

I have a list of pointers to the various routines entered commands will trigger (they just write a screen message for now)

My plan was that once the proper command was identified, its pointer would be placed in a slot in 0 page called SELECTED_CMD, and then I'd just:

JSR (SELECTED_CMD)

Except I now know you can't do that. I imagine I could JMP (SELECTED_CMD), and have each routine JMP back, but that sure seems messy and inelegant.

Is that what you have to do?


Top
 Profile  
Reply with quote  
PostPosted: Mon Apr 24, 2017 1:56 am 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
JSR exec
JMP next
exec: JMP (SELECTED_CMD)


Top
 Profile  
Reply with quote  
PostPosted: Mon Apr 24, 2017 1:59 am 
Offline
User avatar

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8534
Location: Southern California
65c02 also has JMP (abs,X). "Abs" there can be the absolute (ie, not necessarily ZP) beginning address of your jump table. Its op code is $7C.

The '816 adds a JSR (abs,X), op code $FC.

_________________
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: Mon Apr 24, 2017 3:02 am 
Offline

Joined: Sat Mar 11, 2017 1:56 am
Posts: 276
Location: Lynden, WA
Correct me if I'm wrong, but if I use the mentioned method of JSRing to a subroutine that has an indirect JMP in it, I can RTS just as if I'd never had to use the extra JMP, correct? My understanding of how those commands work (stack and all) says yes, but just checking.

BTW, I did get it working by using JMP, instead of JSR, and just having each routine know its way home with an absolute JMP. But Arlet's way seems much cleaner for sure.

My code for entering, interpreting, and acting on commands worked on the first try! Couldn't believe it, considering all the things that had to go right. Right now, it interprets known commands by going routine that just displays, say "writing", if you typed "write, and so forth. It also displays an "Unknown Command" message if there isn't a match. In all my years in the electronics hobby, I've never had something with so many steps work on the first try like that. I must be getting somewhere!

Well, there is one issue. I'm getting intermittent lockups and garbage on the screen with no rhyme or reason to when it happens. I suspect my breadboard build might finally be biting me, although I suppose some inattentive RAM use could be the culprit too.

I'm doing zero handshaking with my serial connection. Could it be that? I do check that the Tx buffer is empty before a send, but that's it (It's the Rockwell part, not the buggy WDC). I'm gonna slow down the baud rate (I'm at 9,600, which seemed conservative to me), and see if it matters. Funny though. Only just now have problems. My guess is still a dodgy connection on the breadboard. I always get a clean reset, with a properly displayed prompt though, which to me tests things as much as anything else. Hate intermittent problems...


Top
 Profile  
Reply with quote  
PostPosted: Mon Apr 24, 2017 3:28 am 
Offline
User avatar

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8534
Location: Southern California
Dan Moos wrote:
Correct me if I'm wrong, but if I use the mentioned method of JSRing to a subroutine that has an indirect JMP in it, I can RTS just as if I'd never had to use the extra JMP, correct? My understanding of how those commands work (stack and all) says yes, but just checking.

Yes, because the JMP does not disturb the return address on the stack, or its position relative to the stack pointer. Are you using self-modifying code in the subroutine with the indirect JMP? Another way would be something like
Code:
        LDA  #>(ReturnAddr-1)   ; (High byte, but remember that the
        PHA                     ; RTS increments it; hence the "-1".)
        LDA  #<(ReturnAddr-1)   ; (Low byte.)
        PHA
        JMP  (TableAddr,X)
ReturnAddr:

Which you'll probably want to put in a macro. If you don't want the return address label, you could replace the LDA#'s with $+8 and $+5 (or modify the numbers per what your assembler returns for the $ (or *), whether it's the address of the first byte of the instruction or that of the operand.

I added a little more to my post above. I'll add even more now. Yes, the '816 adds the JSR (abs,X) capability; but even if it didn't and you wanted to do the LDA#, PHA, LDA#, PHA above, the '816 can do those four lines in a single 3-byte, 6-clock instruction PER "Push Effective Relative address" which is always 16-bit regardless of the size you have the accumulator and index registers set to, and it does not affect the processor registers (except the stack pointer of course). It is useful in writing self-relocatable (address-agnostic) code.

Congratulations on getting a big routine working on first try! It's always a relief, isn't it? Exciting too.

_________________
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  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 321 posts ]  Go to page Previous  1 ... 7, 8, 9, 10, 11, 12, 13 ... 22  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 8 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: