!pr2
!lm12
!rm75
Search and Perform Subroutine..............Bob Sander-Cederlof

When writing an editor or other single-keystroke command system, a very common need is a subroutine which branches according to the value of a character.  In Pascal and some other languages there is even a special statement for this programming need:  CASE.  You might do it like this in Applesoft:

!lm+5
1000 GET A$
1010 IF A$ = "A" THEN 2000
1020 IF A$ = "C" THEN 3000
1030 et cetera
!lm-5

You will often find the equivalent code in assembly language programs:

!lm+5
1000        LDA CHARACTER
1010        CMP #'A
1020        BEQ CHAR.WAS.A
1030        CMP #'C
1040        BEQ CHAR.WAS.C
1050   et cetera
!lm-5

Of course, it frequently happens that the number of different values is small, and the code sequence above with several CMP-BEQ pairs is the most efficient.  It loses a little of its appeal, though, when you have to do it for more than about ten different values.  And what if the branch points are too far away for BEQ relative branches?  Then you have to write:

!lm+5
1000        LDA CHARACTER
1010        CMP #'A
1020        BNE .1
1030        JMP CHAR.WAS.A
1040 .1     CMP #'C
1050        BNE .2
1060        JMP CHAR.WAS.C
1070 .2   et cetera
!lm-5

That takes seven bytes of program for each value of the character.

Personally, I like to put the possible values and the corresponding branch addresses in a table, and search that table whenever necessary.  Each table entry takes only three bytes.  If the subroutine is used with several tables, and if there are a lot of possible values, then the tabular method saves a lot of memory.

I used the tabular method in my still-in-development word-processor.  To speed and simplify the coding of the table entries, I wrote a macro definition JTBL as follows:

!lm+5
1020        .MA JTBL
1030        .DA #$]1,]2-1
1040        .EM
!lm-5
!np
This defines a macro JTBL with two parameters.  The first one will be the hexadecimal value to compare the test-character with, and the second one will be the branch address for that value.  For example, if I write the macro call:

!lm+5
1400        >JTBL 86,FLIP.CHARS
!lm-5

the S-C Macro Assembler will generate:

!lm+5
            .DA #$86,FLIP.CHARS-1
!lm-5

The "-1" is appended to each branch address in the table, because I use the PHA-PHA-RTS method to perform the branch.  Before I go any farther, here is the search and branch subroutine:

!lm+5
1220 SEARCH.AND.PERFORM.NEXT
1230        INY                POINT TO NEXT ENTRY
1240        INY
1250        INY
1260 SEARCH.AND.PERFORM
1270        LDA T.BASE,Y       GET VALUE FROM TABLE
1280        BEQ .1             NOT IN THE TABLE
1290        CMP CURRENT.CHAR
1300        BNE SEARCH.AND.PERFORM.NEXT
1310 .1     LDA T.BASE+2,Y     LOW-BYTE OF BRANCH
1320        PHA
1330        LDA T.BASE+1,Y     HIGH-BYTE OF BRANCH
1340        PHA
1350        LDY #0     (SINCE MOST BRANCHES WANT Y=0)
1360        RTS                DO THE BRANCH!
!lm-5

There are so far four different value-branch tables in my word processor.  Here is an abbreviated listing:

!lm+5
1380 T.BASE
1390 T.ESC0 >JTBL 81,AUXILIARY.MENU
1400        >JTBL 82,SCAN.BEGIN
1410        >JTBL 83,TOGGLE.CASE.LOCK
 . . . . . .
1540        >JTBL 9B,ESC0.ESC
1550        >JTBL 00,SC.BELL
1560 *--------------------------------
1570 T.ESC2 >JTBL 81,AUXILIARY.MENU
 . . . . . .
1690        >JTBL EB,SCAN.RIGHT
1700        >JTBL ED,SCAN.DOWN
1710        >JTBL 00,ESC2.END
1720 *--------------------------------
1730 T.MAIN >JTBL C4,MAIN.DOS
1740        >JTBL C5,MAIN.EDIT
 . . . . . .
1800        >JTBL D3,MAIN.SAVE
1810        >JTBL 00,MON.BELL
1820 *--------------------------------
1830 T.AUX  >JTBL C3,COPY.BLOCK
1840        >JTBL C4,DELETE.BLOCK
 . . . . . .
1890        >JTBL D3,SAVE.SEGMENT
1900        >JTBL 00,SC.BELL
!lm-5

Notice that each of the four tables ends with a 00 value.  The branch address after the 00 value tells where to branch if the current character does not match any values in the table.

When I want to compare the current character with entries in the T.MAIN table, here is how I do it:

!lm+5
2000        LDY #T.MAIN-T.BASE
2010        JSR SEARCH.AND.PERFORM
!lm-5

The LDY instruction sets Y to the offset of the table from T.BASE, and the search subroutine references the table relative to T.BASE.  I use JSR to call the search subroutine. The search subroutine uses PHA-PHA-RTS to effectively JMP to the chosen branch address.  And then the value processor ends with RTS to return to the next line after the JSR SEARCH.AND.PERFORM.

Counting all four tables, I have 45 branches, occupying 3*45 = 135 bytes.  If I had used the CMP-BEQ method, which occupy four bytes per value, it would have taken 4*45 = 180 bytes.  The subroutine is only 23 bytes long, so I saved 22 bytes.  But if I needed the longer CMP-BNE-JMP sequences throughout, I would have had 7*45 = 315 bytes!  Wow!  Long live tables!

Tables have even more advantages.  For one, they are a lot easier to modify when you want to add or delete a value.  For another, the program is easier to read when there is no rat's nest of branches to try to unravel.  For me, it almost makes the assembly listing as easy to read as the reference manual!

Notice that it would be possible to overlap tables using my subroutine.  I might need at some times to search for 13 different values, and at others to search for only 7 of those same values, with the same branches.  If so, the seven entries in common would be grouped at the end of the 13-entry table.  The table has two labels, like this:

!lm+5
3000 T.13   >JTBL C1,DO.A
3010        >JTBL C4,DO.D
 . . . . .
3050        >JTBL CF,DO.O
3060 T.7    >JTBL C2,DO.B
3070        >JTBL C5,DO.E
 . . . . .
3120        >JTBL D7,DO.W
3130        >JTBL 00,DO.NOTHING
!lm-5

What about speed?  Well, it is pretty fast too.  The CMP-BNE-JMP takes five cycles for each value that does not compare equal, and finally seven cycles for the one which compares equal.  If the tenth comparison bingos, that is 9*5+7 = 52 cycles.  The subroutine takes 171 cycles for the same search.  Over three times longer, but still less that 120 microseconds longer.  You would have to perform the search over 8000 times in one day to add a whole second of computer time!
