The Linear Search

Do you want to store and retrieve information with your computer? This program uses a machine language search routine that is so fast you can blitz through a full 13000 bytes of files to find the one you want in less than a second! The program uses Basic to create files and PRINT found ones. It is only the search which runs in assembly language. So even if you find Z80 source code a complete mystery, you can program “around” the machine language search to create your own data management program with super fast access to any file stored in memory.

The Concept

Linear data storage is a simple and straightforward method of holding information in your computer. Simply stated, a large block of memory is set aside for files. Data that you want to input is placed in that memory block one character at a time, one after another. When you need access to a particular file, you input a search word which can be found in the file you want. Then you scan the block of files until you find a match to the word you input. When a match is found, you PRINT the file.

The program creates a very large REM line for the data storage block; 13000 spaces to be exact. Data held in REM has the advantage of being saveable on your tape recorder. It is unaffected by CLEAR or RUN, and its position in memory is fixed. The block of data always begins at the same memory address. This makes programming a bit easier than when data is held in a string. Information to be stored in the Data REM Line is POKEd into it just like a machine code routine gets POKEd into REM.

When you want to access a file, you input a search command. This command can be any word, symbol, or phrase. Just as with the data files, the search command is POKEd into its own special REM line. The search routine then compares the characters of the search REM with the characters of the data REM until a match is found.

Entering the Program

Entering the program is a three step process.

Step 1

First, the large data REM is built. The program used to create this REM line was adapted from “Space in REM” by Frank O’Hara which appeared in the August issue of SYNTAX. After you enter and RUN the REM Builder listed in Figure 1, line 1 1 turns into a REM state ment containing 13000 blank spaces. Imagine putting this line in manually!

The program takes about 7 minutes to run. When it finally does stop with a report 0/11, delete lines 1 through 10 by typing in the line number and ENTER. This will leave you with a single REM line — line 11 — which consists of 13000 blank spaces.

Step 2

The second part of the program involves entering the search command REM, the search routine REM, and the loader program which lets you POKE in the machine code search routine. Add to line 1 1 the listing shown in Figure 2.

This program steps through each address of memory between 16507 and 17000. First the address is PRINTed, then the value stored in that byte. Finally the character the value represents is displayed. After display of each byte, the program gives you these options:

1) Hit ENTER if you want to continue to the next address.

2) Press “S” to STOP.

3) Press “P” to POKE this address.

4) Press “B” to BACK UP one address

5) Press “G” to GOTO a different starting address.

Use the program to input the machine code search routine and to inspect important addresses to make sure everything is added properly. The Linear Search routine uses several system variables the same way that the Sinclair Basic uses them. Figure 3 lists the addresses of these important bytes and describes their functions. Also listed are key addresses of the search routine.

Before you enter the MC SEARCH routine you should use the loader program (Figure 2) to make sure you entered the REM lines correctly. Check the program against these values. At each of the following addresses you should find the PEEK value of 118; 16546; The last byte of 1 REM 16617; The last byte of 5 REM 16652; The last byte of 6 REM When you are sure everything is right, begin entering the MC SEARCH. Since the routine begins at 16552, type “G” and input this address when prompted. Begin POKEing the code from the table in Figure 4. Remember to push “P* 1 for every byte you wish to POKE.

POKEing in the code from Figure 4 fills the 65 space REM line (line 5) with the MC SEARCH instructions.

Step 3

When you are done, you are ready to enter the third and final phase of the program: Typing in the Basic. This part executes file inputs to the Data REM and displays found files.

There is no need to delete the loader program. When you are experimenting with the search routine, you can use the loader to PEEK into the various pointers as well as observe the search command and data REMs.

Figure 5 lists the Basic routines. Simply insert the lines into what you already have typed into your computer.

How The Program Works

When you RUN the program, the first line to be executed is

12 LET P=0

This variable represents the number of data characters used in the data REM line. Since you have not added any files yet, P is initialized with the value of zero.

Line 15 prints the search command menu. From here you can either input a command word or let the computer know that you want to ADD a new file. If you type “A”, line 30 sends you off to the ADD/FILE routine beginning at line 500.

ADD/FILE uses a FOR-NEXT loop to let you input four lines of data. For each value of the loop, you input a line of information at line 530.

This program “marks” each line you input with two very important symbols. These file markers are used by both the machine code search and the Basic display routines. Every file begins with a “” and each new line of data begins with a quote image. Lines 535 and 540 insert these symbols into the string of data you input. For each iteration of the loop, these lines put the text you input into one long string (A$). If you are inputting the first line, A$ becomes “” + X$ (the line you input). If you are adding lines 2 through 4, line 540 adds a quote image, then the line of text.

Line 545 displays your new file. After all four lines are put into A$, lines 580 to 595 are executed. The prompt tells you that if you see a mistake in the new file, you can correct it by pressing the letter

Press any other key and the file gets added to the data REM line. This is done in lines 600 to 635. The FORNEXT loop takes each character of A$ and POKEs it into the next unused byte of the data REM. After each POKE, the variable P is incremented by line 620.

Before ADD/FILE is complete, line 635 POKEs a file marker (*) into the space immediately following the last character of the newly added file. This marker tells the computer to stop PRINTing when it is displaying files.

The line says: POKE 16658 + P,23.

23 is the code number for an asterisk. See the ZX8 1 owners manual for a complete list of all characters and their codes. The file is added. We now jump back to line 14; the search command menu.

Before you actually add your first file, you should note how the machine code search works. If the search routine cannot find a file which contains the search word you input, the computer PRINTs the first file of the data REM line. Therefore, your first file should be an informative statement like “SEARCH IS COMPLETE”. Even though the program asks for four lines of data per file, it is perfectly legal to input a one liner. To add empty line, just hit ENTER when lines 520 and 530 ask you to INPUT a line of text.

Finding and PRINTing Files

The linear search hunts for any word, symbol, or phrase you want. Every file which contains the words or characters in question get PRINTed. This “seek and print” routine begins at line 15, the search command menu. This is where we ADDed new files by typing “A”. If you do not type “A”, the computer tacks an inverse period onto the end of the word you INPUT when line 35 is executed. This symbol indicates to the computer that it is the last character of the search command word.

Next, lines 50 to 70 POKE the search command into the first REM line of the program.

Before the MC SEARCH is called, lines 80 to 110 initialize both BC Ctr and D Ptr to their proper values. At the beginning of every search, BC Ctr takes the value of P. D Ptr receives the address of DATA BYTE, the first character of the data REM line (address 16658). When BC Ctr and D Ptr have these values, the MC SEARCH knows it must begin searching at the beginning of the data REM line and continue searching until it has gone through every used byte of stored data.

The hunt for the first file which contains the search command word is ready to commence. Line

122LETB-USR 16552 breaks the computer from Basic and executes the assembly language instructions beginning at address 16552. This line does more that just jump to the USR code. It also sets up the variable B. The value that B assumes is the number which is held in the BC register pair on return to Basic . In the assembly language routine, the BC pair acts as a counter of each byte of data searched. BC starts off equal as a counter of each byte of data searched. BC starts off equal to P and decrements with each byte until it reaches zero. The variable B, then, does the same thing. When B — 0, the computer knows that the search is complete.

Figure 6 shows exactly what the MC SEARCH does.

Essentially, the Machine Code Search takes the first character of the search command word and checks it against every character held in the data storage REM. When it finds a match, the routine compares the next character of the search word with the next character of the data REM. With every match the operation repeats until the computer reaches the last character of the search word (an inverse period) or until it finds 2 non-matching characters. If the last character of the search word is encountered, the computer steps back through the REM until it finds a file marker (*). This indicates the beginning of a found file. The variable FILEPEEK is loaded with the address the marker is occupying, D Ptr marks the spot where the file was found, and BC Ctr is loaded with the number of data bytes still unchecked. Completing this, the computer returns to Basic.

If the search resulted in a non-match, the computer simply resumes searching for a match of the first character of the search word until the entire block of occupied loads FILEPEEK with the address of the first file in the data REM. Then it returns to Basic.

File Display

With FILEPEEK loaded and the computer back in Basic, line 130 takes FILEPEEK’s address and assigns it to the variable X. Then lines 135 to 210 display the file. At 135, a “Y” loop is initialized. Its first value is X or the address held in FILEPEEK. The next line checks each byte of data held in address Y to see if it is a quote image (CHR$ 192). If it is not, the character held in that address gets PRINTed.

Line 150 checks the next byte for a quote image or an asterisk. If the computer finds one of these file markers, the command:

GOTO 200 + (20*(PEEK (Y+l)=23)) is executed. The expression

(PEEK (Y+l) = 23 is actually a number.

If PEEK (Y + l) really does equal 23, the number is 1 .

If PEEK (Y+l) does not equal 23, the number is 0.

So depending on the PEEK value of address (Y+l), the computer will GOTO 200 + (20*1) or 220 if it finds an asterisk (PEEK Y + 1 = 23), or

GOTO 200 +(20*0) or 200 if it finds a quote image.

If the quote image is encountered, lines 200 to 210 simply move the PRINTing down one line. Then the computer jumps right back into the loop to PRINT more characters.

But, if the asterisk is found, we have come to the end of the file, or more precisely, the beginning of the next file: GOTO 220.

Here, we find a list of display options. After the text of the menu is PRINTed, line 230 lets you make your selection.

If you type “R” meaning RETURN to previous file displays, line 235 sends you back to line 80. This has the effect of making the same search over again. This is useful when you have several files that contain the same search word. If, after printing the third or fourth file, you want to go back to look at the first one, type “R” to RETURN.

Line 240 says that, if B is not equal to zero (the search has not yet progressed through all occupied bytes of the data REM) and you press just ENTER, then GOTO 120. This jumps you back into the MC SEARCH. D Ptr and BC Ctr remember where the computer stopped before it printed the last file, and searching resumes from that point. Hitting ENTER, therefore, lets you continue the search through the remainder of the Data REM.

Finally, if you type “NT, line 245 sends you back to line 14. This breaks the search entirely and you can INPUT a new search command word.

Conclusion

This program showed you one way to store information, find it with lightning speed, and display that information once it is found. A good data base must also take into consideration many other design parameters, How do you edit existing files? How do you delete those that are out of date? What other display options need to be included? What about SAVEing the program on tape? How can files longer than four lines be stored?

Every new capability added to a program uses valuable memory space which could otherwise be used for data storage. Finding ways to combine the most function with the most data capacity is perhaps the greatest challenge of all.

Figure 1. Data REM builder.

1 REM 12EfcRNDLN QmTAN
2 LET D=PEEK 16396+256*PEEK 16397-2
3 FOR I=1 TO 13000
4 POKE 16515, INT ((D+I)/256)
5 POKE l6514,D+I-256*PEEK 16515
6 RAND USR 16516
7 POKE D+I,0
8 NEXT I
9 POKE D-l,INT ((13000+2)/256)
10 POKE D-2,13000+2-256*PEEK (D-l)
11 REM

Figure 2. Machine Code loader

1 REM (32 spaces)
5 REM (65 spaces)
6 REM (29 spaces)
1000 FOR X=16507 TO 17000
1005 PRINT AT 0,0;"HIT ENTER TO GOTO NEXT ADDRESS ""P"" TO POKE THIS ADDRESS";TAB 0;"""S"" TO STOP",,"""G"" TO GOTO A NEW ADDRESS";TAB 0;"""B"" TO BACK UP"
1010 PRINT AT 7,0;"ADDR  PEEK CHR$ "
1015 PRINT AT 8,0;X;" ";PEEK X;" ";TAB 12;CHR$ PEEK X;"     "
1020 INPUT X$
1025 IF X$="S" THEN STOP
1030 IF X$="P" THEN GOTO 2000
1035 IF X$="B" THEN LET X=X-2
1040 IF X$="G" THEN GOTO 1500
1050 NEXT X
1060 STOP
1500 PRINT AT 10,0;"INPUT STARTING ADDRESS"
1510 INPUT X
1520 PRINT AT 10,0;"                                "
1530 GOTO 1010
2000 PRINT AT 10,0;"INPUT A DECIMAL VALUE"
2010 INPUT Y
2020 POKE X,Y
2030 GOTO 1520

Figure 3. System variables and key MC addresses

Decimal	Hex	Name	Function
16507	407B	FILE PEEK (2 bytes)	The last two bytes of the Sinclair system variables area of memory, these bytes are not used by the BASIC so you can use them for whatever you want. FILE PEEK points to the starting address of found files for display.
16514	4082	SEARCH COMMAND WORD (32 bytes)	The first byte after 1 REM. This is where you store the search command word.
16552	40A8	MC SEARCH (65 bytes)	The first byte after 5 REM. This is the start of the assembly routine that does the byte blitzing.
16583	40C7	LASTCHR	Starting address of MC SEARCH which handles found files.
16604	40DC	D Ptr (2 bytes)	This address resides in 5 REM. A 2 byte pointer which shows MC SEARCH where to begin looking.
16606	40DE	BC Ptr (2 bytes)	Also located in 5 REM. Counts how many bytes have been searched.
16608	40E0	NOGOT	Starting address of MC SEARCH which handles unlisted search commands.
16623	40F0	not used	The first byte after 6 REM. These 29 bytes are not used by the program but you must not leave them out. They might someday be useful for another assembly language routine.
16658	4112	DATA BYTE	First byte of Data Storage REM (line 11)