Isn't that unsafe? Updating the vector is not atomic on the 6502 (can't speak to the 65816). If you get half the vector updated and then the IRQ fires, you're in a potentially undefined space. Normal interrupts can be disabled long enough to set the vector, but, in theory, there is no safe way to update an NMI vector (beyond shutting down the source of the interrupt).

I guess you can do that safely, if only one half of the vector needs to be changed...

I also read up on it and concluded it's mostly wasted effort. He (C.R. Bond) has to maintain an ASCII list of the mnemonics in a table, as well as the hash table, plus the hash code itself. After having generated the hash from the presumed mnemonic, he still has to cross-compare it with the ASCII list—albeit a single comparison, since it is conceivable a seemingly-valid hash could be produced from an invalid mnemonic.

When all is said and done, all that has been accomplished is determining whether a mnemonic in the source code is a valid one. His technique doesn't address (!) the requirement of associating that mnemonic with a valid addressing mode and the number of bytes that must be present in the operand, if an operand is required. As many mnemonics can be used with multiple addressing modes, further resolution is required at assembly time to determine if the entered instruction can, in fact, be assembled as written.

Furthermore, while his "perfect" hashing does work for the NMOS 6502 it doesn't directly apply to the CMOS derivatives, which map some previously invalid opcodes onto new instructions or onto existing instructions with new addressing modes. The result is that there isn't a consistent pattern to the relationships between mnemonics and the corresponding opcodes like there was in the NMOS 6502 parts. This is especially the case with the 65C816, which unlike its 8 bit cousins, has no invalid opcodes, has instructions stashed in "odd places," and therefore requires a different method of resolving mnemonics and corresponding addressing modes and operands.

As I earlier said, I used tables (totaling 850 bytes) in my POC's M/L monitor to assemble and disassemble machine instructions, as I was not able to develop any hashing method for the '816 that would work with consistency. Three of the tables are 256 bytes each, corresponding to the 256 possible opcodes of the '816 (i.e., the first entry in each table corresponds to the BRK instruction and the last entry corresponds to an SBC $BBHHLL instruction, where BBHHLL is a 24 bit address), two containing the actual mnemonics in a binary format that produces a unique 16 bit encoding for each mnemonic. I separated the LSBs (least significant byte) and MSBs (most significant byte) into two tables so a simple technique can be used to search for a mnemonic. A short excerpt of the two mnemonic tables follows (taken directly from the POC's BIOS ROM assembly listing):


The bytes corresponding to the symbolic names (e.g., MNE_ASL) shown above are as follows:


The encoding method takes advantage of the fact that all 65xx mnemonics are comprised of three alpha characters and that, disregarding case, any character in the Roman alphabet can be encoded in only 5 bits. Hence it is possible to represent each mnemonic with a unique 15 bit value, which can be generated with the following code (again, taken directly from the assembly listing for the POC's ROM):


The result, which is left in the location MNEPCK, is a 16 bit value. The conversion is not case-sensitive, of course. A simple loop and compare function can then be used to see if the encoded mnemonic is in the tables.

It is possible, using the same tables, to diassemble an instruction into the corresponding ASCII mnemonic. The first code fragment uses the opcode to get the encoded form of the mnemonic:


With the encoded mnemonic stored at MNEPCK, simple code converts it back to ASCII and displays it:


The third 256 byte table contains flags that identify the addressing mode that corresponds to each opcode. Again, a short excerpt follows:


In the above table, OPS0, OPS1, etc., are the operand size in bytes (OPS0 means no operand, OPS1 is a one byte operand, etc.) and the UNIX pipe symbol is the assembler's logical OR operator. The AM_... symbols are the addressing mode indices, which are defined as follows (another excerpt):


Other tables are used to translate between the symbolic form of an operand, e.g., the ($01,S),Y part of an LDA ($01,S),Y instruction, and the opcode that corresponds to that particular addressing mode, $B3 in this case (the resulting machine code would be $B3 $01). In the case of the '816, such translation is somewhat complicated by the irregular syntax of some instructions, such as MVN SBNK,DBNK, where DBNK is actually the second byte in the three byte assembled instruction—the assembled code has SBNK and DBNK reversed in memory. The stack relative instructions are another such case, due to the presence of the ,S in the operand syntax. To resolve all syntax matters, I use one table that contains the ASCII form of each possible operand syntax and a corresponding look-up table to relate the syntactical form to the addressing mode index bits. The tables are bidirectional, so they can be used to disassemble instructions as well.

As the '816 can use 24 bit operands with many instructions (e.g., LDA $123456), some code shenanigans were required to deal such situations. In general, the rule is "least fit," meaning use the machine opcode to which the smallest form of the operand will fit. For example, if I code JMP $000012, the assembler will assemble the instruction as $4C $12 $00 (JMP $0012), since JMP can accept either a two or three byte address and the entered address, $12, can be minimally resolved to two bytes. Coding JMP $012345 will result in $5c $54 $32 $01 (JMP $012345)—note the $5C opcode, which is a jump to another bank instruction.

Immediate mode instructions that can accept either 8 or 16 bit operands are also subjected to the "least fit" rule, so coding LDA #$0012 assembles to $A9 $12, even though the apparent intention is to assemble the instruction with a 16 bit operand. As "least fit" in this case can alter the program in an undesirable way, I devised a syntactical method to force the assembler to assemble a 16 bit operand, even though the MSB is zero. If the programmer precedes the operand with a | (UNIX pipe) the operand will be assembled as 16 bits. Hence LDA |#$12 will result in $A9 $12 $00 (LDA #$0012). This sort of chicanery is necessary because, unlike the above JMP examples, as well as other instructions that can use 24 bit addresses as operands, there is no opcode difference when assembling 8 bit immediate operands vs. 16 bits—the resolution comes from how the M and X bits in the status register are conditioned at run time.

Anyhow, this ran on a bit longer than originally intended and wasn't meant to be a diatribe on assembler algorithms. My point was that C.R. Bond's assembler is simplistic in the sense that going outside of the realm of the NMOS 6502 will produces complications that his code would not readily handle. This statement, however, is not meant to denigrate his work in any way.

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

I did and it didn't—it's still run-on lines.

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

You could get away with altering the vector while IRQs are enabled as long as only half of the vector has to be changed (e.g., the MSB, which would put the new ISR in a different page). The full vector can be atomically changed with the '816 by using a 16 bit store operation.

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

The perfect hashing method works fine with other 6502 derivatives, as long as the list of mnemonics is fixed. The idea is that you take a random 3 character string, and turn it into a 8 bit number with a small amount of arithmetic operations. With a perfect hash, each of the valid mnemonics would generate a distinct number. After verifying the 3 character string, the next step is to look up the 8 bit number in a table, and produce the mnemonic index in the range 0..N-1, where N is the number of mnemonics. The rest of the processing is the same as if you'd looked up the mnemonic in a table of strings to produce this index.

You can go into a loop that watches for evidence of the interrupt just having been serviced, and when you see that one has been, immediately jump in and change both bytes of the vector, while you know you have enough time before the next interrupt. The interrupts were on evenly spaced intervals from a timer.

_________________
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?

Works for me, whether saved or fetched with w g e t, on linux or os x:


Edit: spaced out w g e t to avoid the 403

Here's an example of a perfect hash I tried with the GNU 'gperf' program, and the NMOS 6502 mnemonics. First, it defines a table of letter values:

Now, if you have a 3 letter mnemonic, you can turn that into a number. The first step is to change the middle letter, so it's one more. For example, "SBC" becomes "SCC", and "TXA" becomes "TYA". The next step is to look up the resulting letters in the table, and add up the 3 numbers. So for instance, "SBC" becomes "SCC", and S=0, and C=1, S+C+C = 0+1+1 = 2.

Here are the results:


All codes from 2 to 53 are used exactly once. Between the last couple of codes, there are some holes. These could be patched by a few lines of code that map 62->54, 66->56, and 78->57. Or, if you have enough memory, you can fill the holes with some value that indicates the mnemonic isn't valid.

I converted the fltpt65.cba file with dos2unix, then assembled it with C R Bond's cba65 assembler (using WINE on linux) and have bundled the results up in a zip file attached to the head post. One would either study this package or port it to another assembler syntax, I suspect. I may remove the archive as technically it's a copyright problem - so if you want it, grab it while you can.

The log file from the assembler is quite interesting: it includes a count of the opcodes used, sorted in order:


Also, the assembly listing includes cycle count information.

Cheers
Ed

I know how hashes work.

The hashing process, in my not-uneducated opinion, is a colossal waste of time for this application. Hashing would make sense when the array is large, elements in the list are of varying sizes, and/or not in ascending or descending lexical order. In such cases, the overhead of hashing the search key and checking for collisions would pay off. However, the NMOS 6502 only has 56 unique mnemonics and the worst case, the 65C816, has only 92. There's just not all that much data to search. Hence the hashing search algorithm itself would contribute to much of the wall clock time required to look up a mnemonic. In all likelihood, a binary search on a sorted array of mnemonics (or a 16 bit representation of them) would be on average just as fast and would not require hash collision checks. In an assembler, far more time will be consumed in evaluating and error checking of each line of code than in looking up a mnemonic in a sorted array. In fact, I daresay I/O performance will be the true bottleneck, not compute-bound operations.

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

What about transpositions, such as CBS when the programmer meant SBC?

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

Explaining them is fine for other readers though. My own understanding of hashes, splay trees, AVL trees, etc. is awfully foggy.

_________________
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?

That makes it very predictable. Another way to jump in at the right time would be to watch the timer by comparing its present value to the previous one. If the present value is higher, the timer has reloaded following an underflow and therefore the IRQ was generated and serviced. It would be more difficult if the IRQs were random in nature, e.g., from serial I/O.

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

True, and I wasn't remonstrating about that. I was trying to make the point that sometimes advocacy for a particular coding method ends up closing ones eyes to other potentially more efficient methods. I've been guilty of that more than once, and have castigated myself upon realizing it.


Mine isn't foggy—yet—but is fading into the mists of time, along with a lot of other stuff I don't use any more. Sometimes the basics get lost in the complexity of what we do. While I have been blessed with excellent long-term memory, much of it is the kind that is stored on tape reels stashed away in a vault, not on a local hard disk. Therefore It takes me time to "find the reel," so to speak, and access the information. My long-time friend Bernie, himself no slouch in the recollection department, refers to me as a "treasure trove of tedious minutia" due to my ability to recall arcane information from long ago. I retort by saying that all that "tedious minutia" must have been useful at one time, otherwise why would I know it.

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