Calc65: a BCD floating point package

[whartung]

GARTHWILSON wrote:

I've even changed an ISR between interrupts that were coming at over 40,000 per second on my 6502 workbench computer, not pausing the interrupts. (To do that you get the new ISR ready and then change the vector to point to the new one.) Even a fast PC can't do that.

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).

[rwiker]

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

[BigDumbDinosaur]

whartung wrote:

ElEctric_EyE wrote:

Yes, thanks BigEd and Charles R. Bond..
Excellent write-up by Charles on his CBA65. Hashing mnemonics is the most interesting chapter in the .pdf. I'll read this .pdf many times as I would like to eventually tackle an assembler/disassembler for the 65Org16.b. There are many clues here.

I read it, it's a novel idea.

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):

Code: Select all

10222    ;	encoded W65C816S instruction mnemonics MSB...
10223    ;
10224    mnetabhb .byte >mne_brk        ; $00  BRK
10225             .byte >mne_ora        ; $01  ORA (dp,X)
10226             .byte >mne_cop        ; $02  COP
10227             .byte >mne_ora        ; $03  ORA dp,S
10228             .byte >mne_tsb        ; $04  TSB dp
10229             .byte >mne_ora        ; $05  ORA dp
10230             .byte >mne_asl        ; $06  ASL dp
10231             .byte >mne_ora        ; $07  ORA [dp]
...
10497    ;	encoded W65C816S instruction mnemonics LSB...
10498    ;
10499    mnetablb .byte <mne_brk        ; $00  BRK
10500             .byte <mne_ora        ; $01  ORA (dp,X)
10501             .byte <mne_cop        ; $02  COP
10502             .byte <mne_ora        ; $03  ORA dp,S
10503             .byte <mne_tsb        ; $04  TSB dp
10504             .byte <mne_ora        ; $05  ORA dp
10505             .byte <mne_asl        ; $06  ASL dp
10506             .byte <mne_ora        ; $07  ORA [dp]
...

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

Code: Select all

1040      6D04             mne_asl  =$6d04                ;ASL
1049      64C6             mne_brk  =$64c6                ;BRK
1058      8C08             mne_cop  =$8c08                ;COP
1079      14E0             mne_ora  =$14e0                ;ORA
1118      1D2A             mne_tsb  =$1d2a                ;TSB

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):

Code: Select all

5929    EA2F  64 53                 stz mnepck            ;clear encoded...
5930    EA31  64 54                 stz mnepck+s_byte     ;mnemonic workspace (s_byte = 1)
5931    ;
5932    ;
5933    ;	encode mnemonic...
5934    ;
5935    EA33  A0 03                 ldy #s_mnemon         ;chars needed for mnemonic
5936    ;
5937    EA35  20 ED F2     .0000040 jsr getcharw          ;get a char from buffer, strip whitespace
5938    EA38  D0 0A                 bne .0000060          ;gotten
5939    ;
5940    EA3A  C0 03                 cpy #s_mnemon         ;any input at all? (s_mnemon = mnemonic size)
5941    EA3C  90 03                 bcc .0000050          ;yes
5942    ;
5943    EA3E  4C 55 E9              jmp monce             ;no, abort assembly
5944    ;
5945    EA41  4C C1 EB     .0000050 jmp monasc10          ;incomplete mnemonic — error
5946    ;
5947    EA44  38           .0000060 sec
5948    EA45  E9 3F                 sbc #a_mnecvt         ;ASCII to binary factor (a question mark)
5949    EA47  A2 05                 ldx #n_shfenc         ;shifts required to encode (5 bits to a char)
5950    ;
5951    EA49  4A           .0000070 lsr a                 ;shift out a bit...
5952    EA4A  66 54                 ror mnepck+s_byte     ;into...
5953    EA4C  66 53                 ror mnepck            ;encoded mnemonic
5954    EA4E  CA                    dex
5955    EA4F  D0 F8                 bne .0000070          ;next bit
5956    ;
5957    EA51  88                    dey
5958    EA52  D0 E1                 bne .0000040          ;get next char

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:

Code: Select all

8722    F3EC  A6 55                 ldx opcode            ;instruction opcode is mnemonic table index
8723    ;
8724    ;
8725    ;	decode mnemonic & addressing info...
8726    ;
8727    F3EE  BD E1 F9              lda mnetablb,x        ;packed mnemonic LSB
8728    F3F1  85 53                 sta mnepck            ;working storage LSB
8729    F3F3  BD E1 F8              lda mnetabhb,x        ;packed mnemonic MSB
8730    F3F6  85 54                 sta mnepck+s_byte     ;working storage MSB
...

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

Code: Select all

8803    ;	display mnemonic...
8804    ;
8805    F457  A0 03                 ldy #s_mnemon         ;size of ASCII mnemonic
8806    ;
8807    F459  A9 00        .0000040 lda #0                ;initialize char
8808    F45B  A2 05                 ldx #n_shfenc         ;shifts to execute
8809    ;
8810    F45D  06 53        .0000050 asl mnepck            ;shift encoded mnemonic
8811    F45F  26 54                 rol mnepck+s_byte
8812    F461  2A                    rol a
8813    F462  CA                    dex
8814    F463  D0 F8                 bne .0000050
8815    ;
8816    F465  69 3F                 adc #a_mnecvt         ;convert to ASCII &...
8817    F467  48                    pha                   ;stash
8818    F468  88                    dey
8819    F469  D0 EE                 bne .0000040          ;continue with mnemonic
8820    ;
8821    F46B  A0 03                 ldy #s_mnemon
8822    ;
8823    F46D  68           .0000060 pla                   ;get mnenmonic byte
8824    F46E  20 9A E3              jsr bsouta            ;print it (BIOS console display sub)
8825    F471  88                    dey
8826    F472  D0 F9                 bne .0000060

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

Code: Select all

10772    ;	instruction addressing modes & sizes...
10773    ;
10774    ;	    xxxxxxxx
10775    ;	    ||||||||
10776    ;	    ||||++++———> addressing mode index...
10777    ;	    ||||
10778    ;	    ||||         Index   Mode
10779    ;	    ||||         ———————————————————————————————————
10780    ;	    ||||          0000   dp, abs, absl, implied or A
10781    ;	    ||||          0001   #
10782    ;	    ||||          0010   dp,X, abs,X or absl,X
10783    ;	    ||||          0011   dp,Y or abs,Y
10784    ;	    ||||          0100   (dp) or (abs)
10785    ;	    ||||          0101   [dp] or [abs]
10786    ;	    ||||          0110   [dp],Y
10787    ;	    ||||          0111   (dp,X) or (abs,X)
10788    ;	    ||||          1000   (dp),Y
10789    ;	    ||||          1001   dp,S
10790    ;	    ||||          1010   (dp,S),Y
10791    ;	    ||||          1111   sbnk,dbnk (block move)
10792    ;	    ||||          —-—-—-—-—-—-—-—-—-—-—-—-—-—-—-—-—-
10793    ;	    ||||           A    = accumulator
10794    ;	    ||||           abs  = absolute
10795    ;	    ||||           absl = absolute long
10796    ;	    ||||           dbnk = destination bank
10797    ;	    ||||           dp   = direct (zero) page
10798    ;	    ||||           S    = stack relative
10799    ;	    ||||           sbnk = source bank
10800    ;	    ||||         ———————————————————————————————————
10801    ;	    ||||
10802    ;	    ||++———————> binary-encoded operand size
10803    ;	    |+—————————> 1: relative branch instruction
10804    ;	    +——————————> 1: variable operand size...
10805    ;
10806    ;	    —————————————————————————————————————————————————————————————
10807    ;	    Variable operand size refers to an immediate mode instruction
10808    ;	    that can accept either an 8 or 16 bit operand.  During instr-
10809    ;	    uction assembly, an 8 bit operand can be forced to 16 bits by
10810    ;	    preceding the operand field with a pipe (|), e.g., LDA |#$01,
10811    ;	    which will assemble as $A9 $01 $00.  LDA #$0001 will assemble
10812    ;	    as $A9 $01, whereas LDA |#$0001 will assemble as $A9 $01 $00.
10813    ;	    —————————————————————————————————————————————————————————————
10814    ;
10815    mnetabam .byte ops0 | am_nam   ; $00  BRK
10816             .byte ops1 | am_indx  ; $01  ORA (dp,X)
10817             .byte ops1 | am_nam   ; $02  COP
10818             .byte ops1 | am_stk   ; $03  ORA dp,S
10819             .byte ops1 | am_nam   ; $04  TSB dp
10820             .byte ops1 | am_nam   ; $05  ORA dp
10821             .byte ops1 | am_nam   ; $06  ASL dp
10822             .byte ops1 | am_indl  ; $07  ORA [dp]

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):

Code: Select all

0992    ;	addressing mode translation...
0993    ;
0994      0000             am_nam   =%0000                ;(0)  no symbol
0995      0001             am_imm   =%0001                ;(1)  #
0996      0002             am_adrx  =%0010                ;(2)  dp,X or addr,X
0997      0003             am_adry  =%0011                ;(3)  dp,Y or addr,Y
0998      0004             am_ind   =%0100                ;(4)  (dp) or (addr)
0999      0005             am_indl  =%0101                ;(5)  [dp] or [addr]
1000      0006             am_indly =%0110                ;(6)  [dp],Y
1001      0007             am_indx  =%0111                ;(7)  (dp,X) or (addr,X)
1002      0008             am_indy  =%1000                ;(8)  (dp),Y
1003      0009             am_stk   =%1001                ;(9)  dp,S
1004      000A             am_stky  =%1010                ;(10) (dp,S),Y
1005      000B             am_rsrva =%1011                ;(11) reserved
1006      000C             am_rsrvb =%1100                ;(12) reserved
1007      000D             am_rsrvc =%1101                ;(13) reserved
1008      000E             am_rsrvd =%1110                ;(14) reserved
1009      000F             am_move  =%1111                ;(15) MVN/MVP sbnk,dbnk

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.

[BigDumbDinosaur]

BigEd wrote:

BigDumbDinosaur wrote:

BigEd wrote:

C R Bond's calc65 floating point arithmetic and transcendental function package:
http://www.crbond.com/calc65.htm
Uses 8 bytes and BCD to give 12 decimal digits and 3 exponent digits.

Have you tried that link? All I get is a screen full of gibberish when I attempt to access the source code.

Yes, it's assembly source. Try saving to disk and viewing as a text file (when viewed in-browser the line-ends are not rendered):

Code: Select all

        .print stats,xref,clip=76,csort=c,cycles
        .files h6x
;   fltpt7.cba -- floating point routines for 650X
;
;   (C) 1999 - 2008, C. Bond. All rights reserved.
;
;   v.1
;   This version includes add, subtract, multiply, divide, square
;   root, tangent and arctangent. The tangent and arctangent are
;   implemented as efficient BCD CORDIC algorithms. Sine, cosine
;   arcsine and arccosine are also provided.

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

[BigDumbDinosaur]

whartung wrote:

GARTHWILSON wrote:

I've even changed an ISR between interrupts that were coming at over 40,000 per second on my 6502 workbench computer, not pausing the interrupts. (To do that you get the new ISR ready and then change the vector to point to the new one.) Even a fast PC can't do that.

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).

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.

[Arlet]

BigDumbDinosaur wrote:

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.

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.

[GARTHWILSON]

Quote:

Quote:

Quote:

I've even changed an ISR between interrupts that were coming at over 40,000 per second on my 6502 workbench computer, not pausing the interrupts. (To do that you get the new ISR ready and then change the vector to point to the new one.) Even a fast PC can't do that.

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).

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.

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.

[BigEd]

BigDumbDinosaur wrote:

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

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

Code: Select all

  $ file fltpt65.cba 
  fltpt65.cba: ISO-8859 English text, with CRLF line terminators

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

[Arlet]

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:

Code: Select all

A       2
B       4
C       1
D       2
E       11
F       2
G       82
H       82
I       19
J       32
K       46
L       5
M       31
N       43
O       15
P       3
Q       39
R       18
S       0
T       5
U       25
V       10
W       48
X       6
Y       4
Z       16

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:

Code: Select all

SBC -> SCC -> 0 + 1 + 1 = 2
SEC -> SFC -> 0 + 2 + 1 = 3
SED -> SFD -> 0 + 2 + 2 = 4
DEC -> DFC -> 2 + 2 + 1 = 5
BCS -> BDS -> 4 + 2 + 0 = 6
BCC -> BDC -> 4 + 2 + 1 = 7
DEY -> DFY -> 2 + 2 + 4 = 8
TXS -> TYS -> 5 + 4 + 0 = 9
DEX -> DFX -> 2 + 2 + 6 = 10
TXA -> TYA -> 5 + 4 + 2 = 11
...all  codes between 11 and 53 ...
BVC -> BWC -> 4 + 48 + 1 = 53 
JSR -> JTR -> 32 + 5 + 18 = 55
RTI -> RUI -> 18 + 25 + 19 = 62
BMI -> BNI -> 4 + 43 + 19 = 66
JMP -> JNP -> 32 + 43 + 3 = 78

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.

[BigEd]

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:

Code: Select all

NUMBER OF SOURCE LINES: 4135
NUMBER OF LISTING LINES: 4413
NUMBER OF SYMBOLS: 345
NUMBER OF UNREFERENCED LABELS: 35
NUMBER OF REFERENCES: 1975
NUMBER OF ANONYMOUS LABELS: 153
NUMBER OF ASSEMBLER WARNINGS: 0
MAX. INCLUDE FILE NESTING LEVEL: 0
NUMBER OF CPU INSTRUCTIONS: 2965

OPCODE USAGE SUMMARY (SORTED BY OPCODE COUNT):

MNEMONIC OPCODE COUNT      MNEMONIC OPCODE COUNT      MNEMONIC OPCODE COUNT
---------------------      ---------------------      ---------------------
JSR nn     20    0332      LDA #n     A9    0306      LDX #n     A2    0247      
LDY #n     A0    0175      BPL n      10    0153      STA n      85    0119      
STA nn,X   9D    0114      DEX        CA    0110      LDA nn     AD    0106      
RTS        60    0092      STA nn     8D    0084      LDA nn,X   BD    0071      
BNE n      D0    0067      JMP nn     4C    0061      AND #n     29    0055      
LDA n      A5    0051      LDA nn,Y   B9    0046      CLC        18    0042      
DEY        88    0040      BRK        00    0040      BEQ n      F0    0039      
BCC n      90    0037      STA nn,Y   99    0033      BCS n      B0    0032      
DEC n      C6    0029      LDA (n),Y  B1    0028      ASL        0A    0026      
SED        F8    0025      ADC #n     69    0024      ORA nn,Y   19    0022      
LDY nn,X   BC    0022      CMP #n     C9    0020      INC n      E6    0019      
SEC        38    0018      CLD        D8    0017      BIT nn     2C    0015      
ORA nn     0D    0014      TAX        AA    0014      LSR        4A    0014      
LDX n      A6    0014      ADC nn,X   7D    0011      BMI n      30    0010      
CPX nn     EC    0009      CMP nn     CD    0009      BVS n      70    0009      

Also, the assembly listing includes cycle count information.

Cheers
Ed

[BigDumbDinosaur]

Arlet wrote:

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.

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.

[BigDumbDinosaur]

Arlet wrote:

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:

Code: Select all

A       2
B       4
C       1
D       2
E       11
F       2
G       82
H       82
I       19
J       32
K       46
L       5
M       31
N       43
O       15
P       3
Q       39
R       18
S       0
T       5
U       25
V       10
W       48
X       6
Y       4
Z       16

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:

Code: Select all

SBC -> SCC -> 0 + 1 + 1 = 2
SEC -> SFC -> 0 + 2 + 1 = 3
SED -> SFD -> 0 + 2 + 2 = 4
DEC -> DFC -> 2 + 2 + 1 = 5
BCS -> BDS -> 4 + 2 + 0 = 6
BCC -> BDC -> 4 + 2 + 1 = 7
DEY -> DFY -> 2 + 2 + 4 = 8
TXS -> TYS -> 5 + 4 + 0 = 9
DEX -> DFX -> 2 + 2 + 6 = 10
TXA -> TYA -> 5 + 4 + 2 = 11
...all  codes between 11 and 53 ...
BVC -> BWC -> 4 + 48 + 1 = 53 
JSR -> JTR -> 32 + 5 + 18 = 55
RTI -> RUI -> 18 + 25 + 19 = 62
BMI -> BNI -> 4 + 43 + 19 = 66
JMP -> JNP -> 32 + 43 + 3 = 78

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.

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

[GARTHWILSON]

Quote:

I know how hashes work.

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

[BigDumbDinosaur]

GARTHWILSON wrote:

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.

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.

[BigDumbDinosaur]

GARTHWILSON wrote:

Quote:

I know how hashes work.

Explaining them is fine for other readers though.

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.

Quote:

My own understanding of hashes, splay trees, AVL trees, etc. is awfully foggy.

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.