Dedicated to Carina Beeson

. 1 1 Ill MW i'HWlim IIIHtiHlilllWIWi'tf f iflpM

Published in Great Britain by:

INTERFACE, 9-1 1 Kensington High Street, London W8 5NP. ISBN 0 907563 33 3

Copyright (C) Jeremy Ruston, 1983.

First printing December 1983.

Any enquiries regarding the contents of this book should be directed by mail to the above address.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical or photo¬ copying, recording or otherwise, except for the sole use of the purchaser of this book, without the prior written permission of the copyright owner. No warranty in respect of the contents of this book, and their suitability for any purpose, is expressed or implied.

Cover photograph by MRT Studios, London W8.

Typeset and Printed by Commercial Colour Press, London E7.

4

Contents

Introduction

1 Assembly language programming (Diversion: Drawing a mexican hat) (Diversion: Three-dimensional sine curves)	V 27 29
2 Computer arithmetic (Diversion: Drawing a milk splash)	32 41
3 Boolean arithmetic	43
(Diversion: Faster cursor keys)	49
4 Floating point arithmetic	52
(Diversion: Bresenham meets Moire)	66
(Diversion: Blowing up the screen)	68
5 Evaluating expressions	70
(Diversion: Drawing on the tube)	81
(Diversion: Doubling the vertical screen resolution)	83
6 The FROTH threaded language	88
(Diversion: Screen oddity)	114
7 The SLU G structured language	116
(Diversion: Studying DNA)	158
(Diversion: More on Moire)	159
8 Introduction to the BASIC ROM	161
9 The BASIC ROM listing	194

5

Introduction

BBC Micrc>S 3 C°UrSe *n a<^vance<^ programming techniques and algorithms for the

The first chapter teaches assembly language programming. As well as being useful in its own right, a knowledge of assembly language is vital to understanding the BASIC ROM. The next chapter describes integer arithmetic, which is vital for many assembly language programs. Chapter 3 describes Boolean arithmetic. This is vital in many areas of graphics. Chapter 4 details several algorithms for floating point arithmetic. Using this chapter, the reader has enough material to write a floating point package in assembly language.

Chapter 5 covers expression evaluation. As well as giving a good introduction to the ROM disassembly and SLUG, this section shows some of the practical advantages of recursion. Chapter 6 applies the knowledge of Reverse Polish Notation gained in chapter 5 to write a FORTH like language called FROTH. Unlike a true FORTH, which produces threaded interpreted code, FROTH produces machine code, making it considerably faster than FORTH. Chapter 7 presents a complete compiler for another new language, SLUG. SLUG is an elegant language with some of the features of BCPL, Pascal and Algol. Both SLUG and FROTH are considerably faster than BASIC (from 5 to 100 times faster, depending very much upon the ‘benchmark’ used). The final two chapters describe and list the BASIC ROM at the heart of the BBC Micro. This serves two purposes. The advanced reader can use it to improve his programming in BASIC, whilst the beginner will find it a useful guide to advanced programming techniques in assembly language.

Thus, the reader of this book will be equipped with the best possible understanding of BBC BASIC and assembly language.

Because of the complex nature of much of the material in this book, I have attempted to lessen the intellectual burden of the reader (and the writer) by providing a number of ‘diversions’ as interludes between the chapters. A couple of the diversions are trivial, some involve some very complex and attractive graphics, one is a useful utility and one doubles the vertical screen resolution to 512 pixels.

This book was written on a BBC Micro running the Wordwise wordprocessor from Computer Concepts. I am grateful to Kathy Goudge, who typed the original draft, and to John Coll, Chaz Moir, Rob Pickering, Jeremy San, Richard Gollner and Tim Hart-

7

nell who all provided helpful advice. The proof reading work of Penelope O’Rorke was invaluable. Finally, I must thank David Johnson-Davies, of Acornsoft, who first aroused my interest in languages.

A Note About Basics and Operating Systems

At the time this book was written, there were two versions of BASIC and two versions of the operating system in use on the BBC Micro. This book was written under OS 1 .2; however all the programs should work on OS 1 .0 and upwards. Users of OSO. 10 should note that some small modifications might be necessary to use some of the programs. However, SLUG and FROTH, the most important programs in the book, will work with any operating system.

I used BASIC II to write the book. BASIC I is very similar, but it has a number of obscure bugs. Naturally, the BASIC II ROM disassembly does not directly apply to BASIC I, but, as I argue in chapter 8, this is not of any importance.

8

Assembly Language Programming

Many programmers of the BBC micro will restrict themselves to programming in BBC BASIC. This is not a bad idea, since BASIC carries many advantages - program¬ ming can generally be done quickly, easily and with less chance of things not working when you try to run the program. Just as importantly, BASIC is an easy language to debug.

Once programmers begin to realise the disadvantages of BASIC - slow speed and long length, they often start using a compiler in order to gain extra speed. Indeed, this book devotes a sizable section to writing compilers. However, the time often comes when you will wish to learn assembly language. This is usually because code generated by a compiler is never as efficient as ‘real’ assembly language - especially if you choose to compile programs written in BASIC, which is not really a suitable language for compi¬ lation. This section is intended to be a complete tutorial course on assembly language. The ROM disassembly and, to a lesser extent, the sections on compilers will improve your programming in a practical way, since they contain assembly language.

A computer is based around a particular microprocessor. In the case of the BBC Micro it is a 6502, but many computers are based on other (usually more exotic) processors, such as the 8088, 8086 or the Z80.

Each of these microprocesors responds to its own particular set of machine level instructions which make it carry out certain very basic operations.

These machine level operations are usually of the order of complexity of “fetch a number from a particular memory location”, “add these two numbers together” or “store a number in this memory location”.

All these operations are identified by a special number - the operation code, or op-code - which depends on the microprocessor in use. To program a computer in these numbers, one simply fills up memory with the relevant numbers and sets the computer up to execute these numbers.

This is a very tedious way of programming because the numbers themselves bear no relation to the operation being performed. This makes them rather difficult to remem¬ ber, especially in the case of a machine like the 8086, where there are thousands of different numbers.

Rather than expect programmers to remember these sequences of numbers, manufac¬ turers have developed various mnemonics to represent these numbers.

9

THE BBC MICRO COMPENDIUM

For example, a common operation in assembly language programming is to load a given number into a variable. (In assembly language there are only three variables available). In machine code, this is represented as &A9 &XX, where &XX is the number to be loaded. On the other hand, the same instruction in 6502 assembly lan¬ guage is LDA ft XX.

The 6502 Registers

Internally, the 6502 consists of several registers. These registers are similar to the variables that are used in BASIC except that they are more limited in range. Most 6502 registers are 8 bits wide, which means that they can only hold a number between 0 and 255.

The registers provided are the accumulator, which is often referred to as the A register, the two index registers which are usually referred to as X and Y, the program counter register which is called PC, the stack pointer and the status register.

The accumulator is the most important register of the system. It is used for all arithme¬ tic and logical operations. It is 8 bits wide.

The index registers are normally used to access memory but they are often used for passing parameters to subroutines. The index registers cannot be used for arithmetic or logical instructions. Both index registers are 8 bits wide.

The program counter is 16 bits wide, but it cannot be accessed directly by the program¬ mer. It is used to keep track of which instruction is being executed. It could be looked upon as a book marker.

The strange thing about the stack pointer is that it is only eight bits wide. Because it is used to access memory, we might expect it to be a full 16 bits wide. In fact, it is always assumed to be between addresses &100 and &1FF, so the top eight bits are not stored.

The status register contains 7 bits which reflect various things about the current state of the microprocessor. For example, one of the bits is always a 1 (or ‘set’) if the last instruction dealt with a number that was zero and is only unset if the number was not zero. These flags are often used for operations like discovering which of two numbers is the larger.

Because the 6502 only has 3 general purpose registers, it is also possible to treat all the memory locations in page zero (the bottom 256 bytes of memory) as 256 extra registers. They aren’t quite as good as real registers, since they are slower to access. In addition, m the case of BBC Micro, many of these registers in page zero are used by BASIC and the operating system. In fact, the only locations in page zero that are free for use are &70 to &8F. In practice, neither BASIC I nor BASIC II use memory locations &50 to

10

ASSEMBLY LANGUAGE PROGRAMMING

Addressing Modes

Most of the instructions the 6509 *

get the data needed for the instruction ThV 3CCeSS “ S°me W*y in °rder t0

according to what the instruction d^s ‘ ^ Y “ WhlCh ^ aCCeSS mem°ry V3rieS

JneTn detail. addressing modes (or ways to access memory). We will look at each

an instruction fnlln ressmg mode is immediate addressing. In this mode the data for words this mr»H WS imm^diately t^e op-code identifying the instruction. In other number Tr & •?leans dlat tEe accumulator should be loaded with a particular Xss nl 'L ar t0 thu BASIC Statement LET A=23* To indicate that this g e is in use, the number is preceded with a ft sign (pronounced ‘hash’).

For example, LDA ft 8 would place the number eight in the accumulator.

On the other hand, if you miss out the hash sign, direct memory addressing is used. 1 his means load the accumulator with the contents of the given memory location’. Using the above example, LDA 8 would mean ‘load the accumulator with the contents ot location 8’. In BASIC, a similar statement would be ‘LET A=?8\ This mode is slower than immediate addressing, since two memory accesses have to be made (one to get the address of the data and one to retrieve the data). Immediate addressing only needs one memory access.

Direct addressing comes in two forms:

8 bit addressing and 16 bit addressing. The idea is that you can access any location using the 16 bit addressing mode (for example, LDA &3200). If you wish to access a page zero register, you can omit the top eight bits of the address. This makes the page zero instructions faster than the others. The BBC Micro assembler automatically decides which of the two kinds of direct addressing should be used. Thus, you rarely have to think about the two kinds of instructions. However, they dictate that it is sensible to ensure that any data that you may wish to access frequently during a pro¬ gram should be placed in page zero.

The next addressing mode is sometimes call ‘implied’ or ‘inherent’. In this mode no data is required by the instruction. This means that the instruction is written without any memory address. It doesn’t need any data because all the instructions that use this mode imply their own data. Examples of this mode are CLC, which clears the carry flag, TAX, which transfers the contents of register A to register X, and the similar TAY.

Accumulator addressing is similar to implied addressing, except that the data is always assumed to be the accumulator. The trouble is that these instructions can often use other addressing modes, so it becomes necessary to include an indication of the addressing mode required. The normal way of doing this is to include the letter ‘A’

11

THE BBC MICRO COMPENDIUM

after the mnemonic. For example, the instruction ASL &3200 means ‘multiply the contents of location &3200 by two’, whilst ASL A means ‘multiply the contents of the accumulator by two’.

From now on, the addressing modes become more complex.

The first of these more complex modes is pre-indexed indirect addressing. In all prob¬ ability, you will never remember the name of this mode, but you will remember how it works.

The format of this mode (using LDA as an example) is LDA (&20,X). In this case, the computer first adds together &20 and the contents of the X register. If the answer to this sum is over 256, the computer subtracts 256. It treats this number as an address in page zero. From this address, it retrieves two numbers - one from the address indicated, and one from the next address after the one indicated. The second of these numbers is multiplied by 256 before being added to the first. This new number is treated as the address from where the data for the instruction will be extracted. Quite often, the X register will be zero when this mode is used, whereupon, it becomes a simple means for getting the byte pointed to by an address in page zero.

Post-indexed indirect addressing is similar to pre-indexed indirect addressing. In this mode the format is LDA (&20),Y. You cannot use this addressing mode with the X index register.

Using this mode, a 16 bit number is retrieved from the indicated memory location and the one following it. (In this case, the bottom 8 bits come from the contents of location &20, and the top 8 bits come from location &21). The contents of the Y register is then added to this 16 bit number to gain a new 16 bit number. The data for the instruction is then obtained from the location indicated by this number. This mode is useful in a number of different applications. For example, the indicated memory locations could contain the start of a table. Then it would be easy to access the Yth element of the table - assuming the elements of the table were 8 bits wide. Even if they weren’t this would still be a trivial program.

Indexed addressing is rather simpler than post-indexed indirect addressing, but the two modes share some common characteristics. Indexed addressing is written as LDA &20,X. In this mode, the address of the data for the instruction is &20+X - in other words, the BASIC equivalent of the above would be LET A=X?&20. This mode can be used to access tables when you know the address of the table at the time the program is written.

The indirect addressing mode, which can only be used with the JMP instruction, is similar to post-indexed indirect addressing. Using this mode, the 16 bit address that the JMP instruction must jump to is not given literally, rather an address is given where the actual jump address can be found. For example, the instruction JMP (&200)

12

ASSEMBLY LANGUAGE PROGRAMMING

would pass control to the routine whose address was stored as a 16 bit number in locations &200 and &20 1 . All the operating system routines are accessed using indirect addressing.

Relative addressing is only used with certain types of jump instruction. Using this mode, a constant is added to the program counter, allowing a jump to be made relative to the program counter by a few bytes. The range of relative addressing is limited to about 125 bytes in each direction

The Status Register

The flags in the status register are each 1 bit long. If the bit corresponding to a flag is a T’, that flag is said to be set - otherwise it is unset or reset. Each of these flags reflect various internal states the processor can be in.

The bits in the status register have the following meanings:

Bit 0 - Carry flag

Bit 1 - Zero flag

Bit 2 - Interrupt disable status

Bit 3 - Decimal mode

Bit 4 - Break status

Bit 5 - Not used

Bit 6 - Overflow flag

Bit 7 - Sign flag

To examine them in detail:

The carry flag usually consists of the 9th bit of an arithmetic instruction. For example, if 200 and 100 are added together, the result is a number outside the normal range of the accumulator, ie. 300. To get around this problem, the most significant bit of this answer is stored in the carry flag and the rest is stored in the accumulator.

The zero status simply remembers whether the last number dealt with by the processor was zero or not.

The interrupt status flag allows interrupts to be enabled or disabled. If this bit is set, it means that interrupts are disabled and if it is unset it means that interrupts are not disabled - they are enabled. We shall be talking further about interrupts later on, when we look at the instructions which affect this flag.

The decimal mode status is set if decimal mode is in effect and unset otherwise. In decimal mode all arithmetic operations are carried out using decimal arithmetic rather than binary arithmetic. Again, we shall see the significance of this flag when we look at the instructions which affect it and are affected by it.

The break status is not normally used in user programs, since it is only affected by

13

THE BBC MICRO COMPENDIUM

interrupts, which are handled in the operating system. In brief, the 6502 jumps to the same address when it finds either a break instruction or receives an interrupt. This flag allows the computer to see which of the two caused it to stop what it was doing.

The overflow status reflects the status of bit 6 of the last byte that we have used, while the sign status reflects the value of bit 7. If bit 7 is a 0, the number which is being tested is positive. If it is set, it means the number is negative.

The rest of this section explores the instructions that may be used with the above addressing modes.

The ADC Instruction

This instruction mnemonic means ‘add with carry’. The action of the instruction is to add two numbers together, taking into account the current setting of the carry bit. It works in 8 addressing modes:

Immediate

Absolute (to a 16 bit address)

Zero Page (to address in zero page)

Pre-Indexed with Index Register X Post-Indexed with Index Register Y Zero Page Indexed with Index Register X Absolute Indexed with Index Register X Absolute Indexed with Index Register Y

The ADC instruction retrieves the data from the address indicated, adds it to the accumulator and then finally adds in the contents of the carry flag. As we noted earlier, it copies the state of the imaginary 9th bit of the accumulator to the carry flag.

The important point is that because the carry flag is involved in both ends of the addition, we can add numbers that are larger than the actual size of the accumulator.

But what if we simply want to do a simple addition like 2 + 2 ? To demonstrate this, we’ll have to introduce an instruction out of the proper order, the LDA instruction. It simply loads a number into the accumulator. So, code to add two and two might be:

LDA ft 2 ADC ft 2

All this code does is to load the accumulator with 2, then add 2 to the 2 already in the accumulator. No it doesn’t. It doesn’t because the carry flag is also taken into account. The only way to ensure the carry flag doesn’t muck up the sum is to take steps to ensure it is unset before the sum is carried out. This calls for another new instruction, CLC, which clears the carry flag. So all we need to do is add a CLC instruction to the start of the above code.

If you want to add larger numbers, you can do something like this:

14

ASSEMBLY LANGUAGE PROGRAMMING

1 . Clear the carry flag

j together the least significant bytes of the two numbers

3. Add the next bytes in ascending order

4. Repeat step 3 until all the bytes have been added

Using this technique, the carry flag will automatically take care of itself. The net effect is similar to the way some people add multi-digit decimal numbers, writing the carry digit as a small superscript to the original number.

The AND Instruction

This instruction logically ANDs the contents of a memory location with the contents of the accumulator. The AND operation is identical to the AND operation carried out by the BASIC keyword AND. However, the assembly language version of AND only acts on eight bits at a time.

It can easily be extended to act upon data of arbitrary length, in the same sort of way as we extended the ADC instruction, by using more than one AND instruction, each acting upon a different pair of bytes.

The addressing modes allowed with the AND instruction are the same as those used with the ADC instruction.

The AND instruction sets the flags as follows:

Zero flag - set if the result of the calculation was zero.

Sign flag - set if the result was negative (it reflects the status of bit 7 of the result)

The ASL Instruction

The ASL instruction works with rather fewer addressing modes than the ADC and AND instructions.

The addressng modes allowed are:

Accumulator, eq. ASL A Zero page direct, eg. ASL &20 Absolute direct, eg. ASL &3000 Zero paged indexed with X, eg. ASL &20,X Absolute indexed with X, eg. ASL &3000,X

You’ll notice that besides the accumulator mode, these modes can be reduced to two distinct modes - indexed with X and absolute, since the assembler automatically works out whether zero page should be used or not.

The ASL instruction mnemonic stands for ‘arithmetic shift left’. This means that the instruction moves all the bits in the number one position to the left. In other words, the

15

THE BBC MICRO COMPENDIUM

instruction moves the contents of bit 0 to bit 1, bit 1 to 2 and so on. There are some slight problems. Bit zero is going to be undefined and bit 7 has nowhere to go, because bit 8 doesn’t exist. In fact, bit zero is always left unset, and the contents of bit 7 are copied into the carry flag, in the same way as the carry flag acts as bit 8 in the ADC instruction.

The other status bits affected are:

Zero flag - set if the result was zero

Sign flag - set if the sign of the result was negative

The BCC Instruction

The BCC instruction is called a conditional jump instruction - or sometimes, a condi¬ tional branch instruction. It acts somewhat like the ‘IF < condition> THEN GOTO < line — number> ’ statement of BASIC. The BCC instruction will only carry out the GOTO to a new address if the carry flag is clear.

Rather than loading the program counter with a new value to carry out the branch, it adds a displacement to the present value of the program counter. There are two prob¬ lems with this approach. The program counter is set to the address after the BCC instruction before the displacement is added to it, and the displacement can only be an eight bit number. This means that the range of the branch is only within +/- 125 bytes of the BCC instruction. Luckily, you don’t have to explicitly work out whether a branch instruction will reach a specific address, since the assembler will not assemble an instruction which attempts to branch out of range.

When you are programming normally, all you have to be aware of is the limited range, since the other factors are dealt with automatically.

To use the BCC instruction in your programs, you must follow it with a label. This sample program explains what a label does:

.START LDA &80 CMP &81 BCC START RTS

This program doesn’t do anything useful.

A label is like a place marker in the program. It is created by writing the name of the label preceded by a full stop. (A label can be followed by other instructions without using a colon to start a new statement). When a label is processed by the assembler, it assigns the address of the instruction that follows the label to the variable name given as the label. Thus, labels must adhere to the normal BBC BASIC rules for naming varia¬ bles. In this way, the label becomes a mnemonic for the address at which it is placed.

16

ASSEMBLY LANGUAGE PROGRAMMING

When a branch or jump instruction is written, the label following the instruction is taken as the destination for the jump.

It may not seem very useful to be able to execute a jump if the carry flag is set, but it allows us to do several vital things, like see which of two numbers is the larger.

The BCS and BEQ Instructions

The BCS instruction and the BEQ instruction do more or less the same thing as the BCC instruction, except that different conditions spark off the jump. The BCS instruction will only branch if the carry flag is set, whilst the BEQ instruction will only jump if the zero flag is set - in other words, if the last result was zero.

The BIT Instruction

The BIT instruction logically ANDs the contents of the accumulator with the contents of a selected memory location and then sets the condition flags accordingly. Stangely, it doesn’t alter the contents of the accumulator or the contents of the memory byte. Thus, the only effect this instruction has is on the condition flags.

The only addressing modes allowed are:

Absolute, eg. BIT &1234 Zero page, eg. BIT &23

In other words, you can only carry out the BIT instruction on the contents of a memory location the address of which is known at the time you write the program.

The point of this instruction is to allow you to see if a certain bit (or bits) of a memory location are set (or unset) without upsetting the contents of the location, and ignoring any untested bits. This is a useful operation since it allows you to set up, in effect, your own flag register in memory which can be used to reflect the status of various things inside your own program.

The way to use it is to select the bits you wish to test of the location. For example, if you wished to see how bit 4 of location &234 was set, the bit in question would be bit 4. Then, turn the ‘value’ of the bit into a number. The value of bit 4 is 2~4 or 16. You can then write instructions to load this number into the accumulator, then do a BIT instruction with reference to location &234. If the selected bit was zero, the zero flag will be set, otherwise it will be unset. The code needed in this example would be:

LDA ft 16 BIT &234

The other use of this instruction is to inspect the contents of bits 6 and 7 of a memory location without disturbing the accumulator. For example, after the above instruction, the sign and overflow flags are set to the state of bits 7 and 6 respectively of location &234. Once these bits have been moved into the flags, you can use them in calculations.

17

THE BBC MICRO COMPENDIUM

The other result of the action of these two flags is that they allow you to use the top two bits of any location as flags, and then test them without having the do anything to the accumulator - without even having to load a ‘mask’, as we did above.

To sum up the action of the flags:

Zero flag - set if the result of the AND operation was zero Sign flag - set to the status of bit 7 of the memory byte selected Overflow flag - set to the status of bit 6 of the memory byte selected

The BMI, BPL and BNE Instructions

These three branch instructions all act like the BCC instruction, except they branch under different conditions.

The BMI instruction (Branch if Minus) will only branch if the sign bit is set, the BPL instruction (Branch if PLus) will only branch if the sign bit is unset, and the BNE instruction will only branch if the zero flag is not set.

The BRK Instruction

The BRK instruction is desribed in the User Guide in its capacity for trapping errors in programs, such as the ‘No such line’ message in BASIC.

The internal action of the BRK instruction is to set the break flag, push the program counter and status register onto the stack and finally to jump to the routine whose address is contained in locations &FFFE (lsb) and &FFFF (msb). It is worth pointing out that interrupts also jump to the same address. The only way the operating system can see which type of interrupt (BRK or external) caused the jump to the routine is to look at the contents of the flag register. Finally, the action of executing a BRK instruc¬ tion or responding to an interrupt automatically disables further interrupts.

The BVC and BVS Instructions

The BVC and BVS instructions operate in the same way as the BCC instruction. The BVC instruction, which means Branch if oVerflow Clear, will only carry out a branch instruction if the overflow flag is unset. The BVS instruction means Branch if over¬ flow Set and will only carry out a branch instruction if the overflow flag is set.

The CLC Instruction

The CLC instruction simply clears the carry flag and, as we discussed, is often used just before an ADC instruction if the carry flag is not being used in the calculation.

The CLD Instruction

The CLD instruction clears the decimal flag. Under normal conditions, the decimal flag is unset - which implies that binary arithmetic will be carried out.

The CLI Instruction

The CLI instruction clears the interrupt enable flag, in other words enabling inter¬ rupts. Under normal circumstances, interrupts are enabled, so this instruction need not be used.

18

ASSEMBLY LANGUAGE PROGRAMMING

The CLV Instruction

The CLV instruction clears the overflow flag.

The CMP Instruction

The CMP instruction subtracts the contents of a selected memory location from the accumu ator an sets the condition flags accordingly, but does not alter the contents of e accumu ator or the memory byte. It offers the same memory addressing options as the ADC instruction.

The flags set by the CMP instruction after a sequence of instructions like:

LDA < number _ 1>

CMP < number _ 2>

are as follows:

< number _ 1>	=	< number _ 2>	Z=1
< number _ 1>	<>	< number _ 2>	Z=0
< number _ 1>	> =	< number _ 2>	C= 1
< number _ 1>	<	< number _ 2>	c=o

This table assumes unsigned arithmetic is being used.

Using the above table, you can test numbers to see which is larger, and then use a branch instruction to alter the course of the program depending on some relation.

The difference between signed and unsigned arithmetic is covered in the section on two’s complement arithmetic.

The CPX Instruction

The CPX instruction stands for ComPare X register. It is identical in intent to the CMP instruction, with the exception that the X register is used in preference to the accumulator. The addressing modes you can use with this instruction are much more limited:

Immediate, eg. CPX ft 23 Zero page, eg. CPX &23 Absolute, eg. CPX &2000

This means that you can only compare the contents of the X register to a constant, or to the contents of a memory location whose address is known at the time the program is written/assembled.

The CPY Instruction

The CPY instruction is exactly equivalent register is used rather than the X register.

to the CPX instruction except that the Y

The same three addressing modes are used.

19

THE BBC MICRO COMPENDIUM

The DEC Instruction

The DEC instruction stands for DECrement. It decrements the contents of a location (by 1) and sets various flags accordingly. The addressing modes allowed are:

Zero page direct, eg. DEC &45 Absolute direct, eg. DEC &7C00 Zero page indexed with X, eg. DEC &20,X Absolute indexed with X, eg. DEC &7C00,X

The flags affected are the sign and zero flags.

The DEX Instruction

The DEX instruction decrements the X register and sets the sign and zero flags accord¬ ing to the result.

The DEY Instruction

The DEY instruction decrements the Y index register and sets the sign and zero flags according to the result.

The EOR Instruction

The EOR instruction Exclusive ORs the contents of the accumulator with the con¬ tents of a selected memory location.

It offers the same addressing options as the ADC instruction. The condition flags affected are the sign flag and the zero flag.

The INC Instruction

The^.instraction incremen« a memory location by 1, but otherwise behaves like the DEC instruction.

The INX and INY Instructions

The INX instruction increments the X register and sets the sign and the zero flags according to the new value in the X register. The INY instruction does the same for the Y register.

The JMP Instruction

THE JMP instruction passes program control to j the program counter. It is used with labels in the we looked at earlier.

a new address by altering the value in same way as the branch instructions

Two addressing modes are allowed:

Absolute direct, eg. JMP &FFEE Indirect, eg. JMP (&208)

With indirect jumps, the program counter is loaded with the at the locations indicated (lsb followed by msb).

1 6 bit number to be found

20

ASSEMBLY LANGUAGE PROGRAMMING

The JSR Instruction

The JSR instruction is the assembly language equivalent to the BASIC word GOSUB, in that it is used to call subroutines. Similarly, the RTS instruction is the equivalent of RETURN. So, a subroutine in assembly language looks like this:

< main program>

JSR < label>

< rest of program>

.< label>

< subroutine code>

RTS

The internal action of JSR is quite complex, and need not be understood for normal programming activities. It first pushes the address of the instruction following the JSR instruction onto the stack. This address will be the current contents of the program counter, because the 6502 doesn’t process an instruction until the entire instruction has been ‘read in’. Finally, it carries out a normal JMP to the address of the subroutine indicated. The RTS instruction simply retrieves the address from the stack, and jumps to it. The idea of using the stack is that it allows you to ‘nest’ subroutines - have one subroutine being called from inside another. Irritatingly, indirect subroutine calls are not allowed - eg. JSR (&200).

The LDA Instruction

The LDA instruction loads the accumulator from a memory location. The addressing modes allowed are the same as for the ADC instruction. After the accumulator has been loaded, the sign and zero flags are adjusted to reflect the new value in the accumulator.

The LDX Instruction

The LDX instruction loads the index register X from a memory location. The follow¬ ing addressing modes can be used:

Immediate, eg. LDX #&20

Zero page, eg. LDX &20

Absolute, eg. LDX &2000

Zero page indexed with Y, eg. LDX &20,Y

Absolute indexed with Y, eg. LDX &2000,Y

The sign and zero flags reflect the value loaded into the X register.

The LDY Instruction

The LDY instruction loads the Y register with the contents of a memory location. Again it affects the sign and zero flags. The addressing modes allowed are:

Immediate, eg. LDY #&45

Zero page, eg. LDY &45

Absolute, eg. LDY &4500

Zero page indexed with X, eg. LDY &45,X

Absolute indexed with X, eg. LDY &4500,X

21

THE BBC MICRO COMPENDIUM

The LSR Instruction

This instruction moves all the bits in the selected byte one position to the right. It is thus the opposite of ASL. Like the ASL instruction, the previous contents of bit 0 are copied into the carry flag, and zero is copied into bit 7. The sign flag is always unset (think about it), whilst the zero flag is set if the result was zero.

The addressing modes allowed are:

Accumulator, eg. LSR A

Zero page, eg. LSR &56

Absolute, eg. LSR &5678

Zero page indexed with X, eg. LSR &56,X

Absolute indexed with X, eg. LSR &5678,X

The NOP Instruction

The NOP instruction has no effect - which is why it is called ‘No Operation’. It is rarely used in assembly programming, but is often useful in machine code programming.

Its only effect is to use up memory, so it can be substituted for instructions you wish to omit from a program in RAM.

The ORA Instruction

The ORA instruction logically ORs the contents of a selected memory location with the accumulator. The addressing modes allowed are the same as for the ADC instruc¬ tion. Additionally, the condition flags affected are the sign and zero flags.

The PHA Instruction

The PHA instruction, which means PusH Accumulator (onto the stack), does just that. It is often used for restoring return addresses and passing parameters on the stack. No condition flags are affected. Saving the accumulator on the stack is a good way of maintaining its value through a subroutine call. For example, the operating system routines usually retain the value of the accumulator when they pass control back to their calling program. They do this by pushing the accumulator on entry, and pulling it back as soon as they leave.

The PHP Instruction

The PHP instruction pushes the status register on to the stack. Apart from pushing it, this instruction does not affect the status register. It is often used in the same way as the PHA instruction above.

The PLA Instruction

The PLA instruction pulls the accumulator off the stack. Thus, it complements the PHA instruction. It also provides the only means for transferring the contents of the status register to the accumulator - eg.

PHP:

PLA.

22

ASSEMBLY LANGUAGE PROGRAMMING

The PLP Instruction

The PLP instruction pulls a byte from the stack, then moves it into the status register. The flags are inherently affected.

This instruction is usually paired with a PHP instruction to conserve the status regis¬ ter whilst a subroutine is executing.

The ROL Instruction

This instruction is similar to the ASL instruction. The difference is that when the byte is shifted left, bit zero is not set to zero - rather, it is set to the previous value ofthe carry flag. The instruction thus rotates the byte, and assumes that the carry flag is the 9th bit of the byte.

The addressing modes allowed are:

Accumulator, eg. ROL A

Zero page, eg. ROL &83

Absolute, eg. ROL &8300

Zero page indexed with X, eg. ROL &83,X

Absolute indexed with X, eg. ROL &8300,X

The idea of this instruction, in part, is to allow the shifting of numbers that are more than eight bits long. For example, if a 32 bit number is stored in &80-&83, the follow¬ ing sequence of instructions will shift the whole lot one position to the left.

ASL &80 ROL &81 ROL &82 ROL &83

In addition to the action of the carry flag mentioned earlier, the sign and zero flags are affected in the normal way.

The ROR Instruction

This instruction is similar to the ROL instruction, except that the rotation is carried out to the right.

Exactly the same addressing options can be used.

The RTI Intstruction

The RTI instruction is like the BASIC keyword RETURN, except that it is not used to return from a normal subroutine. Rather, it is used to exit from a subroutine designed to deal with interrupts. Thus, you’ll almost certainly never have to use this instruction.

Internally, it pulls the status register off the stack, then pulls the new program counter contents off the stack. Thus, it pulls off the stack exactly what the BRK instruction put there.

23

THE BBC MICRO COMPENDIUM

You could use the RTI instruction to effect return from a normal subroutine as follows:

< main _ program>

JSR < label>

< rest of program>

.< label>

PHP

< subroutine code>

RTI

In this case, you are substituting RTI for the code PLP, RTS.

The RTS Instruction

This instruction is used like the RETURN keyword of BASIC. It pulls the program counter off the stack, where it was placed by the JSR instruction.

Subroutines are described under the description of the JSR instruction.

The SBC Instruction

This instruction subtracts the contents of the indicated memory location from the accumulator. However, like the ADC instruction, it also takes the contents of the carry flag into account. If the carry flag is set, it is ignored, otherwise, 1 is subtracted from the final answer.

Thus, the SBC instruction is often preceded by an SEC instruction (SEt Carry flag), to ensure that the carry flag does not disturb the result. Like the ADC instruction, bit 8 of the accumulator is assumed to be the carry flag, so if a borrow is necessary (as in 3-5) the carry flag is set.

In keeping with the way the carry flag is treated at the start of the instruction, it is inverted after the instruction. This means that the carry flag will be unset if a borrow was required, and set if it was not.

The SBC instruction can use the same addressing modes as the ADC instruction. Multiple SBC instructions can be concatenated in the same way as multiple ADC instructions.

Besides the carry flag, the sign and zero flags are affected in the normal way by this instruction.

The SEC Instruction

The only effect of this instruction is to set the carry flag.

The SED Instruction

The SED instruction sets the decimal mode flag. This makes the computer carry out decimal arithmetic until the next CLD instruction.

24

ASSEMBLY LANGUAGE PROGRAMMING

The SEI Instruction

The SEI instruction sets the interrupt disable flag, so disabling interrupts. You can use this instruction in particularly crucial bits of code to ensure that the processor is not interrupted. If you do, you should push the old status value beforehand, and retrieve it afterwards. This ensures that interrupts are treated the same before and after the routine executes.

The ST A Instruction

This instruction stores that value of the accumulator to the indicated location. It can use all the ADC addressing modes, except the immediate addressing mode - which wouldn’t make any sense in this instruction anyway.

Thus, STA &2000 stores the value in the accumulator to location &2000.

The STX Instruction

This instruction does the same thing as the STA instruction, except it stores the value in the X register. The addressing modes allowed are:

Zero page, eg. STX &80

Absolute, eg. STX &7C00

Zero page indexed with Y, eg. STX &80,Y

Naturally, no flags are affected by this instruction.

The STY Instruction

This instruction stores the value of the Y register to a specified memory location. The addressing modes allowed are:

Zero page, eg. STY & 75

Absolute, eg. STY &7500

Zero page indexed with X, eg. STY &75,X

The TAX Instruction

This instruction transfers the value in the accumulator the X register. In the process, the sign and zero flags are affected in the normal way.

The TAY Instruction

This instruction transfers the value in the accumulator the Y register. In the process, the sign and zero flags are affected in the normal way.

The TSX Instruction

This instruction transfers the current value of the stack pointer to the X register. It is the only way to examine the contents of the stack pointer.

This instruction is used by the operating system to access information passed on the stack, but normal programming rarely uses it.

The sign and zero flags are affected in the normal way.

25

THE BBC MICRO COMPENDIUM

The TXA Instruction

the siln*!11?011 trans^ers contents of the X register to the accumulator, affecting me sign and zero flags as it does so.

The TXS Instruction

C0P^es X register to the stack pointer, without affecting any flags, rarel & n®rma way t0 set the stack pointer when the computer is reset. Otherwise, it is

The TYA Instruction

This instruction copies the value held in the Y register to the accumulator, affecting e sign and zero flags in the normal way as it does so.

The general form of an assembly language program is:

1. DIM STORE 3000

2. FOR PASS = 0 TO 2 STEP 2

3. P% = STORE

4. [OPT PASS

5. < ASSEMBLY LANGUAGE STATEMENTS>

6. 1NEXT

(The numbers above are not intended to be line numbers).

We will look at the lines above one by one:

1. This line reserves 3001 bytes of free space. The variable SPACE contains the address of the first byte. The space is used to hold the machine code. 3000 bytes is an arbitrary figure, and could be reduced if the rest of the program gets too big. However, it is your responsibility to ensure that the machine code does not overrun the space allocated to it.

2. This line loops through two values for the OPT statement.

3. The lefthand square bracket is used to enter the assembler. The OPT statement is called a pseudo-operation, since it is a ‘fake’ assembly language operation. It is described in the User Guide, but the above shows a typical example of its use. On the first pass through the assembly language statements no listing is issued, and errors are suppressed. On the second, errors are not suppressed.

5. This line represents the assembly language statements of the program.

26

ASSEMBLY LANGUAGE PROGRAMMING

p". qq^|S linV“teS t^le Pro§ram by leaving the assembler and terminating the oop. is ensures that the assembly language is assembled twice.

Some practical examples of assembly language programming are to be found elsewhere in the book, notably in the ROM disassembly

Diversion”, “Drawing a mexican hat”

This simple program draws a three dimensional view of a function. The accompanying screen dumps show the output of the program.

^ ™st comPlex Part of the algorithm is the procedure PROCP(K%,X%,Y%, Z/o). I his acts in the same way as PLOT K%,X%,Y%, except it plots in three intensions. The routine rotates the point in the horizontal plane before it is plotted. 1 his is achieved using:

X = X*COS(angle) + Y*SIN(angle)

Y = -X*SIN(angle) + Y*COS(angle)

SIN(angle) and COS(angle) are computed in advance, since the angle of rotation is constant. To plot the rotated point, the Y coordinate is scaled down and summed with the Z coordinate. This makes the plot slightly angled away from the viewer, rising above the horizon the farther away it gets. The rotation factor generally enhances the effect. It shold be noticed that this is not a truly general purpose plotting routine, since the squares nearest the viewer appear the same size as those farther away. We shall examine a routine later that passes this criterion.

You may like to alter the function that is plotted. This can be done by altering line 410. This line must yield a result between about -500 and 500 as D% goes from 0 to about 700.

> LIST

10 REM FilenamerHAT 20

30 REM Mexican hat drawing program 40

70 MODE 0

80 VDU 23,224,&AA,&55,&AA,&55,&AA,&55,&AA,&55 90 FOR Y% = 0 TO 31 100 FOR X% = 0 TO 79

HO IF (X% AND 8)< > (Y%_ AND 4)*2 THEN VDU 31,X%,Y% 224 120 NEXT ,

27

THE BBC MICRO COMPENDIUM

28

ASSEMBLY LANGUAGE PROGRAMMING

130 VDU 30 140 ANGLE% = 40 150 S% = 20

160 C = COS(RAD(ANGLE%))

170 S = SIN(RAD(ANGLE%))

180 VDU 29,640;512;

190 FOR X% = -500 TO 500 STEP S%

200 FOR Y% = 500 TO -500 STEP -S%

210 PROCP(4,X%,Y%,FNA(X%,Y%))

220 PROCP(4,X%,Y% + S%,FNA(X%,Y% + S%))

230 PROCP(87,X% + S%,Y%,FNA(X% + S%,Y%))

PPOCP(87>x% + S%,Y% + S%,FNA(X% + S%,Y% + S%)) 250 PROCP(4,X% , Y% ,FN A(X% , Y%))

260 PROCP(5,X% + S%,Y%,FNA(X% + S%,Y%))

270 PROCP(5,X% + S%,Y% + S%,FNA(X% + S%,Y% + S%)) 280 PROCP(5,X%,Y% + S%,FNA(X%,Y% + S%))

290 PROCP(5,X%,Y%,FNA(X%,Y%»

300 NEXT Y%

310 NEXT X%

320 *SAVE P.HAT 3000 8000

330 END

340

350 DEF PROCP(K%,X%,Y%,Z%)

360 PLOT K%,X%*C + Y%*S,(-X%*S + Y%*C) DIV 3 + Z%

370 ENDPROC

380

390 DEF FNA(X%,Y%)

400 D% = SQR(X%*X% + Y%*Y%)

410 = SIN(RAD(D%))*200

“Diversion59, “Three dimensional sine curves55.

This program draws a simple pattern comprised of a family of overlapping sine curves The screen dump shows the output from it.

The program is valuable since it shows how a three dimensional effect can be built by overwriting parts of the pattern with new lines. 11 up

By changing the equation in line 1 10 to something more complex this nrna™™ „ generate quite intricate patterns. The only disadvantage is that it is mther sT0^

> LIST

10 REM FilenamerSINE 20

29

THE BBC MICRO COMPENDIUM

ASSEMBLY LANGUAGE PROGRAMMING

30 REM Overlayed sine waves 40

70 MODE 0

80 FOR Y% = 400 TO 0 STEP -8 90 GCOL 0,(Y% DIV 8) MOD 2 100 FOR X% = 0 TO 1279 STEP 2 110 MOVE X%,SIN(RAD(Y% + X%))*Y% + Y%*2 120 PLOT 1,0,-100 130 NEXT ,

31

Computer Arithmetic

stntp« nkn°W’ kecaus^ a byte contains 8 bits it can only represent one of 256 possible states or, more normally, a number between 0 and 255 inclusive.

Similarly, if we combine 2 bytes to form a 16 bit number we can only represent um ers between 0 and 65535 inclusive. This range is very restrictive because it does not allow for negative numbers.

A scheme has been developed to allow the representation of negative numbers using the binary system. The way in which it works is to set aside the most significant bit of the number to indicate whether the number is positive or negative. The normal con¬ vention is to assume that if the most significant bit is 0, then the number is positive. If it is 1 then it is negative.

As well as setting the most significant bit to be 1, one other change has to be made to a negative number. All the bits of the number have to be inverted and then 1 has to be added to the number.

For example, assume we wish to encode the number -10 into a single byte using this method. First we encode 10 into a binary number, getting 00001010. To convert it from being a positive number to negative, we have to invert it. This gives us 1 1 1 10101. We must then add 1 to it, whereupon we get 1 1 1 10110.

Notice that we don’t have to make sure that the top bit is set to one explicitly, since the inversion operation takes care of this automatically.

This system for representing numbers is called the 2’s complement system. It is worth bearing in mind that the range of numbers you can represent using 2’s complement numbers in a byte is different from the normal range of 0 to 255. The largest number is obviously 01111111(1 27 in decimal), since this is the largest number without the top bit set. The smallest number we can represent is 10000000 since this is the smallest number with the top bit set. As an exercise, this is how to convert it to a normal decimal number. First, we invert it, getting 01111111. Then one is added to it, getting 10000000 again. Thus, this number corresponds to -128.

The reason why this system is so powerful is that it allows us to add and subtract numbers regardless of the sign. This can be verified by examining the sample sum shown below:

Add -3 and 23:

32

COMPUTER ARITHMETIC

Convert -3 to binary:

3 = 0000 0011 NOT 3 = 1111 1100 -3 = 1111 1101

Convert 23 to binary: 23 = 0001 0111

Add:

1111 1101 + 0001 0111

0001 0100 (20 in decimal)

1 1111 111 (this row shows the carries)

So, the answer comes out as 20, which is correct.

The 2’s complement system cannot directly cope with multiplication or division. If you wish to multiply two 2’s complement numbers together you must first work out the signs of the two numbers that you are multiplying and then take the absolute values of both numbers. If both of the signs are the same, the answer will be positive. If they are different, the answer will be negative. A similar rule holds for division. If the answer to a multiplication or division is found to be negative, then you must negate the answer either by inverting it and adding 1 to it, or by subracting it from 0.

Most of the 2’s complement arithmetic contained in this book is transparent to the reader but there are some sections such as those in compiler for the FROTH language towards the end of the book which assume a certain amount of knowledge of 2’s com¬ plement numbers.

One stumbling block in learning assembly language is the absence of some of the features that one takes for granted in BASIC. These include instructions for such simple operations as multiplication and division and program control statements such as FOR - NEXT and REPEAT - UNTIL loops. This section goes some of the way to removing the problem by discussing how to multiply in assembly language.

There are four 6502 instructions which shift bytes left or right:

ASL shifts the contents of a memory location or the accumulator one bit to the left. The least significant bit assumes a value of zero. For example, the binary number 0 1 1 0 1 0 1 1 (6B hex, 1 07 decimal) would turn into 1 1 0 1 0 1 1 0 (D6 hex, 2 1 4 decimal) after an ASL instruction had been performed on it. The most significant bit (the first digit written down) of the original number is copied into the carry flag. The clever thing about the ASL instruction is that the process of shifting a number left is exactly the same multiplying the number by two. So the ASL instruction is the seminal multiplic¬ ation instruction.

33

THE BBC MICRO COMPENDIUM

LSR is the opposite of the ASL instruction, in that it shifts a byte one position to the right. The most significant bit becomes zero and the least significant bit is copied into the carry flag. In consequence of this, it divides a byte by two, leaving the remainder in the carry flag.

ROL is identical to ASL, except that the least significant bit is not automatically set to zero, but instead the current status of the carry flag is used.

ROR is identical to LSR, except that the most significant bit is set to the carry flag.

The useful property of these last two instructions is that they allow you to shift numbers which are bigger than a single byte wide. For example, to shift left the four bytes starting at address &80, you could use:

ASL &80 ROL &81 ROL &82 ROL &83

The ASL instruction as it stands can be used to multiply by 2, 4, 8, 16 and so on. This can be done because if you follow one ASL instruction by another, the effect of each is compounded. For example, three ASLs will multiply by 2 three times, giving 2*2*2. This is a total multiplication factor of eight. If you continued along these lines you would get factors of 16 and 32, and so on. This is great, but many times you may wish to multiply by a number other than 2, 4, 8, 16 and 32 etc. This is relatively easy to do. Let us assume we wish the computer to work out 5*X. You might be able to see that this sum can also be written as 4*X+X. This may not look like much of a simplifi¬ cation, but it is, because in this new form the only multiplication we need to carry out is X*4, which we know how to do. Therefore to multiply a number by 5, one need only multiply by 4 using the arithmetic shift left instruction twice and then add on to that the original number.

This technique can be extended to apply to other multiplication factors. For example, we can represent a multiplication by 7 as 4*X + 2*X + X. Again, this sum can quite easily be coded in assembly language.

We may not appear to be any closer to a fully general multiply routine which will multiply any two numbers together but we have come somewhere nearer that point.

Part of the solution is to examine how we broke down a complicated multiplication, which we couldn’t do, into a simpler calculation that we can do.

We started off with the sum 5*X. Notice two things: five in binary is 0101; and the weightings assigned to each binary digit position start at 1 and ascend through 2, 4, 8 etc, multiplying by two each time we move one position to the left.

The interesting thing to note is that when we were doing multiplication in terms of

34

COMPUTER ARITHMETIC

shifts and additions, we multpliplied by 4 and then by 1 for a multiplication by five. There is a connection between what you must multiply X by and the binary represen¬ tation of the number that is being multiplied. We can now say that to multiply any two arbitrarily long binary numbers we must scan one of the numbers and for every posi¬ tion in which there is a 1 in the number (a bit is set),we must multiply the other number in the calculation by the weighting assigned to the original bit position. We must then add together the results of these calculations. In other words, if the detected bit has a ‘value’ of 16, you must multiply the other number by 16 and add this result to the grand total.

You can build a perfectly reasonable multiplication routine by using this technique. However, it is usually easier to use the fact that a given multiplication will also do an arithmetic shift left in the process of doing multiplication, which is a complicated way of explaining that if you have two eight bit numbers X and Y the multiplication process should go something like this:

1 . The result will be stored in location Z.

2. Do an arithmetic shift left (use the ASL instruction, combined with ROL instruc¬ tions if the numbers are more than a byte long) of the number X. If the bit that falls off the end of X, in other words the bit that ends up in the carry, is set then set Z to Z + Y.

3. Shift left Z.

4. Repeat the process until X becomes zero.

The program on the next page shows how to do this in assembly language. It will multiply two eight bit numbers together. (Unsigned arithmetic is used, but that’s another story).

The program as presented here will not detect overflow (as in 200*200), but this is relatively easy to add. All you need to do to add overflow detection is check to see if Z+Y is more than 255 - this can be checked by examining the carry bit after the addition. It is interesting to note that if you do decide to detect overflow, you can assume that one of the two numbers will be less than 16, since if they were both 16 or greater, overflow would be bound to result. Thus, it would be possible to alter the range of the loop in the program to 4, but you would have to swap around the numbers N1 and N2, according to which had the top four bits set to zero, and take appropriate action if neither did.

Anentirdy different W3y ofillustrating the Process of binary multiplication goes like Call your two numbers X and Y, and assume the answer will appear in a number called

First write X in binary, omitting any leading zeros. (In other words, write 101101

35

THE BBC MICRO COMPENDIUM

[a“a“ 00101101). Then replace each ‘ 1 ’ with the letters MA and each ‘0’ with the

“ilfySfs^g: d ^ Wi" then * “ F°r eXampk’ 'he biMry

MAAMAMAAMA

(Any budding blues singers, start singing).

Then set N to zero and scan the string from left to right. For each letter M encountered, multply N by two. For each letter A, add Y to N, storing the result in N.

When no more letters are left, the number N is the answer. (The same method can be altered to show the raising to a power process in binary. This is described in a subse¬ quent section).

Some analysis will show that this is exactly the same method as the one described earlier.

A decimal form of this method was used by some early civilisations as an easy way to multiply, in preference to long multiplication.

(The brackets in line 180 are necessary to prevent an obscure bug/feature in BBC BASIC where if you carry out ASL (or ROL, ROR etc) on a label starting with ‘A’, the system interprets you to be using accumulator addressing. This means that ‘ASL ANS’ would be treated as ‘ASL A/NS-’ !! You can see how this occurs in the ROM listing)

> LIST

10 REM Filename:8MULT 20

30 REM 8 bit binary multiplication 40

70 DIM SPACE 100

80 N1 = &80:REM Storage for first number 90 N2 = &81:REM Storage for second number 100 ANS = &82:REM Storage for answer 110 FOR LOOP = 0 TO 2 STEP 2 120 P% = SPACE 130 [OPT LOOP 140

150.MULTIPLY

160 LDA #0 / Zero answer

170 STA ANS

180 LDX ^ 8 / Set up loop

190. ST ART

36

COMPUTER ARITHMETIC

200 ASL (ANS)

210 ASL N1

220 BCC NO _ ADD

230 LDA N2 240 CLC 250 ADC ANS 260 STA ANS

270.NO _ ADD

280 DEX

290 BNE START

300 RTS

310 ] NEXT LOOP 320

330 REPEAT

/Multiply answer

/Copy bit 7 to carry

/If the bit was zero, skip addition

/ Get addition factor

/ Clear carry for addition

/ Add into answer

/Store back to answer

/Check for end of loop

340 INPUT "Enter two numbers: "?N1,?N2 350 CALL MULTIPLY 360 PRINT "Answer is ";?ANS 370 UNTIL FALSE

>

The program starts by reserving space for the assembly language at the label SPACE.

Lines 80 to 100 simply assign labels to the zero page locations used by the program.

Lines 1 10 to 130 are the mechanism for making two passes over the assembly language.

The program starts at the label MULTIPLY. First, it sets the answer location to zero. This has to be done because the answer is accumulative - that is, it is arrived at through a sequence of additions to the answer location. Next the X register is initialised to 8. This is because we shall be making 8 iterations of the main loop, to allow for eight bits in the two original numbers.

The first ‘active’ piece of code occurs at line 200, where the answer is multiplied by two.

Next, bit seven of one of the two original numbers is copied into the carry flag. This is done by means of an ASL instruction. A cause of confusion is that this ASL instruction is not being used as a device to multiply by two with.

Next, if no carry was generated, the code for adding the other number and the answer are skipped.

Finally, the loop is terminated in the normal way.

As a matter of interest, here is a version of the above program written using all the improvements I could think of. It should help to demonstrate tactics you can use in cleaning up your own programs.

37

BBC MICRO COMPENDIUM

THE

> LIST

10 REM Filename :8MULT2

% ^ &**0:REM Storage for first number

inn .XTI^1:REM Storage for second number iin = Storage for answer

110 FOR LOOP = 0 TO 2 STEP 2 120 P% = SPACE 130 [ OPT LOOP 140

150. MULTIPLY

160 LDX ft 8 /Set up loop 170 LDA fto / Zero answer

180. ST ART

190 ASL A /Multiply answer

200 ASL N1 / Copy bit 7 to carry

210 BCC NO — ADD /If the bit was zero, skip addition

220 CLC /Clear carry for addition

230 ADC N2 /Add into answer

240.NO _ ADD

250 DEX /Check for end of loop

260 BNE START

270 ST A ANS / Store answer

280 RTS

290 ] NEXT LOOP 300

310 REPEAT

320 INPUT "Enter two numbers: "?N1,?N2 330 CALL MULTIPLY 340 PRINT "Answer is ";?ANS 350 UNTIL FALSE

As you can see, the main speed improvement has come from replacing some memory accesses by register accesses.

It is also fairly easy to take the powers of numbers in assembly language. (For example, 2 ‘to the power of 3 is two multiplied by itself three times which comes to eight. In BASIC, this is ‘PRINT 2‘3’).

38

COMPUTER ARITHMETIC

There are several reasons why we should wish to be able to compute powers of numbers. A simple compiler or interpreter that only supports integer arithmetic can use this method to implement powers, without needing floating point arithmetic. I find the most common use of the power operator is to help in extracting bits from a byte. In addition, many arithmetic and numerical analysis techniques require power calculations. These techniques can be speeded considerably by using a fast algorithm such as this.

For example, we shall examine how to compute X to the power of N, given X and N, and assuming N is a positive integer.

Let us assume that N is 16. We could start with X and multiply it by itself 15 times. This is the obvious way to do it, but it is needlessly complex and slow. It is possible to obtain the same answer with only 4 multiplications, as opposed to fifteen. The method is to repeatedly take the square of each partial result. This will yield the partial answers X~2, X~4, X~8 and XT 6. This result is extracted from one of the basic laws of indices, which state that (X~N)~M is the same as X~(N*M).

The same idea can be applied to any value of N in the following way:

1 . Write the number N down in binary, but omit any zeros on the left, ie. the first digit must be a 1 .

2. Replace each 1 in the number by the pair of letters SX and replace each zero by the letter S.

3. Cross off any SX pairs that appear on the left.

4. The result is a sequence of the letters S and X. Oddly enough, this result can be used for computing X to the power of N.

5. S is interpreted as the operation of squaring and X is interpreted as the operation of multiplying by X.

As an example, I shall work through the above method if N is equal to 23.

The binary representation of 23 is 10 1 1 1 . This gives a letter sequence of SX S SX SX SX. We can remove the leading SX to gain the answer S SX SX SX.

This rule states that we should square the number twice, then multiply by X, square it again, multiply by X, square it and then multiply by X.

We would be successively computing X~2, X*4, X~5, XT0,XT1, X~22 and X~23. This binary method is pretty easy to translate into assembly language as long as you have a suitable multiplication routine, like those we have discussed previously.

39

THE BBC MICRO COMPENDIUM

A computer program to do all this often bears algorithm. The method used is as follows:

very little resemblance to the above

To find X~N:

1. Set Y to 1 and Z to X.

2. Shift N right. If the bit that fell off was zero, go on to step 5.

3. Set Y = Z* Y.

4. If N 0, the program has finished; the answer is Y.

5. Set Z = Z*Z.

6. Go back to step 2.

This can be encoded in the following simple BASIC program:

10 REM POWER 20

30 REM Binary method for exponentiation 40

70 INPUT "What do you want to the power of what:"Z,N 80

90 REM Step 1:

100 Y = 1 110

120 REM Step 2:

130 N = N/2

140 IF N = INT(N) THEN GOTO 230 150 N = INT(N)

160

170 REM Step 3:

180 Y = Z*Y 190

200 REM Step 4:

210 IF N = 0 THEN PRINT "Answer: "Y:END 220

230 REM Step 5:

240 Z = Z*Z 250

260 REM Step 6:

270 GOTO 120

COMPUTER ARITHMETIC

You can trace through this program by hand to see exactly how the algorithm works. You may a so ike to encode the program into assembly language. If you decide to do so, I would recomend you stick a limit of one byte on the lengths of all the variables used.

“Diversion”, “Drawing a milk splash”

This program draws a pattern on the screen resembling a milk drop splashing into a cup. The screen dump shows the effect.

The program is extremely slow to run, so it makes sense to *SAVE the result as the last line of the program, so that it can be reproduced quicker in future.

Like the Mexican hat’ program, the function drawn can easily be altered, in this case by changing line 200.

>LIST

10 REM Filename:SPLASH 20

30 REM Milk splash 40

70 MODE 0 80 VDU 29,640;512;

90 FOR X% = -640 TO 0 STEP 2 100 M% = -512

110 FOR Y% = -1212 TO 912 STEP 16 120 V% = (Y% + FNA(X%,Y%))/2

130 IF M%< V% THEN M%=V%:PLOT 69,X%,V%:PLOT 69,-X%,V%

140 NEXT Y%

150 NEXT X%

160 END

170 DEF FNA(X%,Y%)

180 LOCAL A%

190 A% = SQR(X%*X% + Y%*Y%)

200 = SIN(RAD(A%)*2)*200-A% DIV 5

41

THE BBC MICRO COMPENDIUM

42

Boolean Arithmetic

An understanding of Boolean algebra is useful for advanced programming techniques in BASIC and assembly language. While leafing through the BBC Micro User Guide you may have seen mention of the AND, OR and NOT operators and so may be aware of what the Boolean operators do.

f501pl 10sll20people only use Boolean operators in IF statements, in the form of IF A = B

AND B< 13 THEN < do something> . This is only one of the many uses of the Boolean operators.

Boolean algebra consists of four basic operations. Three of these take two binary digits and arrive at a third as the answer and the fourth takes a single binary digit and arrives at another binary digit as the answer. Because binary digits can only be 0 or 1, an operator which takes two binary digits as its arguments can only have four possible different inputs. This is because the arguments can only be 0 and 0, 0 and 1, 1 and 0 or 1 and 1.

It is possible to show how each of these operations behave for each possible argument of the operation. The four operations are OR, AND, EOR and NOT. Briefly, the action of each of these operators is as follows. The AND operator takes the two binary digits and if both of them are set to 1, then it returns an answer of 1, otherwise it returns an answer of 0. This is shown in the table below:

INPUT OUTPUT

00 0

01 0

10 0

11

The OR operation returns a value of 1 if either or both of the binary digits are set. Another way of putting it is that it will return 1 unless both the binary digits are zero This can be shown as follows:

INPUT

OUTPUT

0

1

00

01

10

11

1

43

THE BBC MICRO COMPENDIUM

S:st: rn 1 if the two binary digi,s are difFerem and *» «■>*

INPUT OUTPUT

00 o

01 i

10 l

11 0

The EOR operation means ‘exclusive OR’, because it is an OR operation that excludes tne case when both arguments are 1.

The NOT operation simply inverts on single bit or binary digit. NOT 1 is 0 and NOT 0 is 1 . The truth table for NOT is as follows:

INPUT OUTPUT

0 1

1 0

Before we examine any other uses of these Boolean operators, it is a good idea to see how they can behave as they do when used in IF statements.

The crucial thing is that when the BBC Micro evaluates an IF statement, it is looking for a numeric expression between the word IF and THEN. If this expression evaluates to zero then the expression is said to be FALSE but if it evaulates to a non-zero number, then the expression is said to be TRUE.

Similarly, when you use the comparison operators such as = and > , if the thing they are testing for is TRUE they give a value of a -1 and if the thing they are testing for is FALSE, they return zero. You might expect the value 1 to be used to represent TRUE, but this is not so. The reason -1 is used is because when the BBC Micro does a Boolean calculation, it carries out the operation on each bit of a 32 bit binary number in turn. Thus, 101 AND 110 is 100. TRUE occurs when all the available bits are set to 1 - otherwise NOT TRUE wouldn’t be FALSE. When the computer comes to print this string of ones as a decimal number, it first looks at the top bit of the number. This is 1, which indicates (due to the use of 2’s complement arithmetic) that the number is negative. As the number is negative, the computer inverts all the bits (getting a string of zeros), then adds one to this answer, getting the answer 1 . This is combined with the minus sign to give -1. Simple.

Going back to the original explanation, when you combine two of the comparison operators such as = or > , each gives either TRUE or FALSE. The TRUE and FALSE values are then dealt with quite happily by the AND operator, to give a new value. This new value is the one with which the IF statement deals.

We can also use these operations in other circumstances. The AND operation is

44

BOOLEAN ARITHMETIC

k >p<viaUy useful because it allows us to mask out some of the bits of a number. If you u c . o to PRINT < a number> AND 7, the computer will first take the number and then AND it with the binary number 7. The binary number 7 is 1 1 1, thus, all the bits of the -.umber will be knocked out except for the bottom 3, since these are the ones ‘pro- uvted' by the number 7. This can be very useful because the only alternative is to use ; o MOD operator, as in PRINT < a number> MOD 8, which is somewhat inelegant ind takes up more time.

you extract a byte from a graphics screen and EOR it with -1, you will have inverted ill the bits in the byte. When the byte is replaced in memory, that area of the screen will Nr inverted. For example, try running this in MODE 4:

FOR T% = &5800 TO &7FFF:?T% = ?T% EOR 255:NEXT T%

Hus leads on to another very valuable use of the Boolean operators which has already been thought of by the designers of the BBC Micro.

This is to use the AND, OR, NOT and EOR operators in graphics work to make objects move in front of and behind other objects on the screen, without disturbing anything else on the screen.

Usually the first argument of the GCOL statement is zero, which means that the ; rciputer will plot in the colour specified by the next number. Many users of the BBC Micro will ignore what happens when a number other than 0 is used, but the other cumbers have quite powerful effects.

To be specific, the options available to the GCOL statement are as follows:

GCOL 0,< colour> makes the computer plot in the colour specified.

GCOL 1,< colour> makes the computer do a Boolean OR operation between the .clour specified and the colour present at any point it is required to plot. Thus,

GCOL 1,4 PLOT 69,500,500

» equivalent to

rfCOL 0,4 OR POINT(500,500)

PITXT 69,500,500

' ‘ reason the second method is not used in preference to the first is that the first ' Mv>d can cope with carrying out these operations throughout a line or a triangle, ‘ bile th^second can only conveniently cope with points.

' r >L 2,< colour> is the same, except that the AND operation is used.

1 T 3,< colour> is the same again, except EOR is used.

45

THE BBC MICRO COMPENDIUM

GCOL 4,< colour> uses the NOT operation, by inverting the colour of every point it as to p ot. As NOT only takes a single argument, the value of < colour> is not used in tins case.

Those GCOL modifiers allow programs like this to be run:

> LIST

10 REM F ilename : PRIORY 20

30 REM Graphic priority demo 40

70 ON ERROR GOTO 420 80 *FX 11,1 90 *FX 12,1 100 MODE 2 110 FOR X% = 0 TO 39 120 GCOL 0,(X% MOD 5) + 1 130 MOVE X%*32,0 140 DRAW X%*32,1023 150 MOVE X%*32 + 8,0 160 DRAW X%*32 + 8,1023 170 NEXT X%

180 FOR T % = 8 TO 15 190 VDU 19,T%,7;0;

200 NEXT T%

210 VDU 23,224,&3C,&7E,&DB,&DB,&FF,&24,&42,&81

220 X% = 500:Y% = 500

230 VDU 5

240 GCOL 3,8

250 P% = 5

260 L% = 0

270 REPEAT

280 MOVE X%,Y%

290 VDU 224

300 A% = INKEY(10)

310 *FX 15 320 VDU 8,224

330 IF A% = 90 THEN X% = X%-8 340 IF A% = 88 THEN X% = X% + 8 350 IF A% = 47 THEN Y% = Y%-8 360 IF A% = 58 THEN Y% = Y% + 8

46

BOOLEAN ARITHMETIC

370 IF A% = 44 AND P%> 0 AND U 19, P% + 9,P% + 1;0;

380 IF A% = 46 AND P%< 5 AND DU 19, P% + 8,7;0;

390 L% = A%

400 UNTIL FALSE 410

420 REPORT

430 PRINT " at line ";ERL 440 *FX 12 450 *FX 12,3 460 END

L%< > 44 THEN P% L%< > 46 THEN P%

>

P%-1:VD P% + lsV

When you run this program, a MODE 2 screen will fill up with lots of vertical lines in various colours. Near the middle of the screen will be a little ‘space invader’ type character. You can use the ‘ZyX’,7’ and keys to move the character left, right, down and up over the screen. No checks are made for the little man exceeding the limits of the screen, so you’ll have to be mature while you control it.

You’ll notice that the little man moves around the screen OVER the lines, and when he has passed over a particular line, that line is not erased. This in itself is useful, but we can achieve even more interesting effects.

Press the comma key once. From now on, the little man will pass over all the lines - except the purple ones, which he will pass behind. If you press the comma again, he will pass behind the blue lines, and so on until he passes behind all the lines. Once you have reached this point, the comma key stops doing anything. If you press the full stop key, the man starts to pass in front of the red line, and succeeding presses of the full stop key will make him pass in front of progressively more lines, until he passes over them all, as when the program started.

Many commercial games for the BBC Micro use this technique. For example, the ‘Monsters’ game from Acornsoft uses this technique to ensure that the little men in the game do not erase the various ladders littered around the screen.

This technique is also dependent on the ability to change the logical to physical colour pairings using VDU 19.

To describe the program line by line:

Line 70 sets up an error trap. This is because the program alters the repeat rate and delay of the keyboard, and it is irritating to break out of a program, using Escape, to find that the keyboard is malfunctioning. Thus, the error trap prints the error message, and restores the computer to normal operation.

Lines 80 and 90 set the keyboard ta repeat very fast, without a delay before repeating. This is to allow smooth keyboard control.

47

Line 100 goes into MODE 2. We shall see that although the program only appears to use 6 colours, it in fact uses 13, so MODE 2 is essential. The large number of colours used up is the only disadvantage of this method.

Line 110 sets up a loop to draw the lines.

Line 120 chooses a colour for the line.

Lines 130 to 160 draw two vertical lines next door to each other.

Line 170 terminates the loop.

Lines 180 to 200 sets the colours of logical colours 8 to 15 to be white.

Line 210 defines the little man.

Line 220 sets the starting coordinates of the little man.

Line 230 joins the text and graphics cursors. This is to enable the little man to be drawn anywhere on the screen.

Line 240 sets the plotting action to be ‘exclusive OR whatever is on the screen with 8’. This means that each time a point is plotted, the top bit will be toggled. With the colours set up as they are, this ensures that any plotting operation will plot in white.

Line 250 sets the current priority of the little man to be 5. This means he will appear in front of those lines that are colour 5, and all those that precede colour 5 in numerical order.

Line 260 sets the variable that holds the last key pressed to be zero. This is because we have to allow the movement keys to repeat, but not the priority change keys.

Line 270 starts a loop through the main program.

Lines 280 and 290 print the little man at his current position.

Line 300 gets a keypress from the user.

L'ne 310 clears the keyboard buffer, to ensure that the keyboard does not store exra characters, which could lead to a time lag between what is typed in and what you see on

the screen.

I ine 320 moves the cursor back a character position, and reprints the little man The fi st Eme Z man was printed, whatever was underneath him would have had the t P bit set, moving it from a colour in the range 0 to 7 to a colour in the range 8 to 1 5. When

48

DUVJL.^

it is removed in line 320, the opposite happens, so. it moves back to be a colour in the range 0 to 7. The crucial point is that all the colours in the range 8 to 15 are white, which makes the whole figure white.

Lines 330 to 360 move the object around by checking for the movement keys.

Line 370 deals with decreasing the priority of the little man. It will only do this if the relevant key is pressed and the priority is greater than zero (a priority of T would otherwise result, which would be meaningless). In addition, it makes sure that the last key pressed was not a comma. This makes the priority keys unrepeatable. Once all these conditions are met, the computer decrements the priority. Then it sets the colour of anything of the logical colour corresponding to the original priority be the same as the corresponding colour without the top bit set. This sounds complex, but it effectively means that instead of colour 8 + 5 (which is the colour generated when the little man is over a purple line) being white, it is purple, giving the illusion that the man is behind the line.

Line 380 reverses this effect to increase the man’s priority.

Line 390 sets the last key pressed to be the current key.

To sum the technique up in more general terms:

1. Draw the background / foreground in whatever colours you like, using colours 0 to 7.

2. Set the plotting colour to be GCOL 3,8.

3. If the moving object is to pass in front of a piece of the background / foreground of colour X, then set colour X + 8 to be the colour of the object, else set it be the colour of the foreground / background.

Once you have mastered this method, you will see how it can be simplified or otherwise altered to suit your needs.

You might like to write a program like the one in this chapter, except allowing two objects with different priorities to be manipulated.

“Diversion”, “Faster cursor keys”

This practical routine speeds up the action of the cursor and copy keys when they are used in conjunction with the shift key. Without the shift key, they act normally. This makes it easier to alter just a small part of a long line.

The program operates using the ‘key pressed’ event. Whenever a key is pressed, the computer can be instructed to jump to a user written machine code routine. The

49

THE BBC MICRO COMPENDIUM

routine is also example.

used to ‘trap’ certain other events, but this facility is not used in this

Notice that the machine code of this routine is stored from &A00 onwards. This is not perfect, since it overwrites the cassette/RS423 buffer, but it does prevent the routine Jrwf overwritten if a new program is loaded. The routine could easily be placed at &C00 if user defined characters are not being used.

e program saves the registers as soon as it is entered at line 120. The accumulator contains the number of the event, which is not tested in this example. Line 130 causes the routine to exit if the ASCII code of the key pressed was less than &9B. Line 140 exits if the key number is greater than &9F. This indicates that the key is one of the cursor keys, or the copy key, combined with the shift key.

The key code (without shift) is then inserted into the keyboard buffer using *FX 138. The routine then exits.

The action of the routine ensures that the cursor and copy keys are entered into the buffer twice, once using *FX 138 and once as soon as the routine exits.

Line 220 turns the routine on. You can turn it off using *FX 13,2.

> LIST

10 REM Filename:FAST 20

30 REM Speedy edit keys 40

70 R% = &A00

80 FOR T% = 0 TO 2 STEP 2 90 P% = R%

1001OPT T%

110. key

120 sta &80:stx &81:sty &82

130 tyarcmp #&9B:bcc exit

140 cmp ft&AOrbcs exit

150 secrsbc #&10:tay

160 Ida #138:ldx #0:jsr &FFF4

170. exit

180 Ida &80:ldx &81:ldy &82:rts 1901NEXT

50

BOOLEAN ARITHMETIC

200 ?&220 = key

210 ?&221 = key DIV 256

220 *FX 14,2

51

Floating Point Arithmetic

Whilst programming in BASIC, you will have met two different types of number: integers and floating point numbers (or reals). Although integers are a subset of reals’ me computer has to deal with these two types of numbers in fundamentally different ways. Integers are quite easy to deal with in assembly language. This is because most processors include instructions for the very basic two’s complement arithmetic functions.

Real numbers, on the other hand, are much more difficult. One problem is that it is impossible to represent some numbers accurately, as we shall discuss later. So, computers cannot properly be said to carry out real arithmetic - instead they use floating point arithmetic, which is a convenient way to approximate real numbers.

The floating point system is really a variation of the scientific notation used by calcula¬ tors. The BBC Micro also uses scientific notation for very small and very large numbers. With this system, three pieces of information are required to represent a particular number - as opposed to the two bits required for integers (the sign and the magnitude). The three pieces of information are called the sign, the exponent -and the fractional part. We’ll first discuss why we need these three parts, then look at how the BBC Micro represents them.

Consider the number:

-5.346E2

In this example, the sign is negative (a missing sign would indicate a positive number), the mantissa is 5.346 and the exponent is 2. The number actually being represented by these pieces of information is obtained by the following expression:

-5.346*10*2 = -534.6

The number of digits assigned to the mantissa dictates the accuracy with which numbers can be represented, while the number allocated to the exponent dictates how large a range can be covered by a number. For example, if the number of digits allo¬ cated to the mantissa is 5, PI would be represented as 3.1416, but with 20 it will be represented as 3.1415926535897932385, which is a much more accurate represen¬ tation. Similarly, if the number of digits allocated to the exponent is 3, numbers as small as IE-999 and as large as 1E999 can be represented.

52

FLOATING POINT ARITHMETIC

In decimal scientific notation, the number 348.26 would be normally represented as: 3.4826E2

and the number 0.000825 would be normally written as:

8.25E-4

The normal position for the decimal point is to the right of the most significant digit. When it is in that position, the number is said to be in normalised form.

Sometimes, when you do a calculation involving floating point numbers, the answer is unnormalised:

(4. 1468E2)*(-3.45E-3) = 14.30646E-1

The answer can be normalised by shifting the decimal point left or right and adjusting the exponent as we do so. Therefore the above can be normalised by a single shift to the left, yielding:

1.430646E0

Zero is rather special, since there is no way we can normalise it - there is no most significant digit. It can be represented by a mantissa of zero. The exponent is of course arbitrary (in theory). For example, both these numbers are zero:

0.0E345

0.0E-23

The computer does not use scientific notation to base 10, instead it uses binary.

This brings us to a small problem - how can numbers less than one be represented in binary? It turns out that we can extend the binary ‘number bar’ to the right of the decimal point (called a bicimal point when you use binary arithmetic):

16 8 4 2 1 . 1/2 1/4 1/8 1/16

Thus, the decimal number 5.75 could be represented as the binary number:

101.11

In normalised binary scientific notation, this is:

1.0111E2

In this case, the exponent indicates the power of two by which it must be multiplied. Strictly speaking, the exponent should have been shown as a binary number, too. When a binary floating point number is stored in the BBC Micro, one bit is used for the

53

THE BBC MICRO COMPENDIUM

sign, eight for the exponent and 32 for the mantissa. Since the exponent can be either positive or negative, you might expect it to be stored in 2’s complement form. This, however, is not the case. A special constant, called a bias, is added to the 2’s comple¬ ment form. In the case of the BBC Micro, this bias is &80. Thus, an exponent of zero is stored as &80, not &00. In addition, an exponent of zero is used as a special case, for representing the number zero. This is mainly to speed up detection of underflow.

Floating point numbers are always normalised in the BBC Micro. This means that a mantissa of:

00111011

is actually stored as:

111011

The exponent is suitably adjusted. As the number always starts with a binary 1, we don’t need to actually store the bit. Instead, it is replaced by the sign bit. Thus, the apparently impossible feat of storing 4 1 bits of information in 40 bits of storage is acheived.

A floating point number is stored in memory as follows: XX + 0:Exponent

XX + 1:MSB of mantissa, with sign bit replacing bit 7 XX + 2:Mantissa XX + 3:Mantissa XX + 4:LSB of mantissa

Thus five bytes are required for each number.

We shall now look at the classical methods of doing the four arithmetic operations on floating point numbers. The BBC Micro uses highly optimised forms of these algo¬ rithms, which are very difficult to follow unless you know the standard way of doing things.

The first algorithm we shall examine is that for floating point addition. The algorithm forms U + V into the floating point variable W :

1 Seoarate the exponent and fractional parts of the representations of U and V This includes moving the sign bit out of the mantissa to where we can get at it and replacing it by a true numeric bit for both numbers.

2. If the exponent of U is cases it is more efficient to other steps.

less than the exponent of V, swap around U and V. In many combine this step either with the first step or with one of the

3. Set the exponent of W to be the exponent of U.

54

FLOATING POINT ARITHMETIC

4. If the exponent of U minus the exponent of V is greater than or equal to the number of bits in the mantissa^ then set the fractional part of W to be the fractional part of U and go on to step 7. This effectively means that if the two numbers are of different orders of magnitude adding the smaller one to the larger one will not make any differ¬ ence to it, so we can ignore the addition altogether.

6' ,?5tthe ^r?Ctj°na* part t0 be the fractional part of U plus the fractional part of V. This can be done using a simple integer addition algorithm.

7. Normalise the answer in W . The method of normalising a number is given below.

More informally, the numbers are manipulated until they both have the same exponent (by shifting one mantissa and adjusting one exponent) and then the addition can be carried out fairly normally.

The normalisation algorithm proceeds as follows:

1 . Is the most significant bit of the fractional part set? If so, exit, else go on to step 2

2. Shift the fractional part one position to the left

3. Decrement the exponent

4. Go back to step 1

This algorithm will patently not work if you try to normalise zero. The solution? Don’t normalise zero - test for it in advance.

Diagramatically, this makes the floating point number look like this:

xxxxxxxx

exponent

1 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

mantissa

X indicates a bit which could be set or unset, but it doesn’t matter which.

The normalisation process often includes the packing process, whereby the most signi¬ ficant bit is replaced by the sign bit.

To subtract floating point numbers you must negate one of the numbers before using the addition algorithm. This negation can be achieved by simply inverting the status of the sign bit before entering the routine.

Floating point multiplication and division proceed in a very similar manner to each other. Given floating point numbers U and V, they will be multiplied together or U

55

THE BBC MICRO COMPENDIUM

will be divided by V to gain either the quotient W or the product W. We will first examine the stages for multiplication. (The following descriptions use the notation FW to indicate the fractional part of W, EU for the exponent of U and so on).

The algorithm for multiplication is:

1 . Separate the exponent and fraction parts of U and V.

2. Set EW equal to EU + UV-&7F and set FW equal to FU*FV.

3. Normalise the floating point number W and pack the result, by replacing the most significant bit of FW with the sign bit.

The algorithm for division is as follows:

1. Separate the exponent and fraction parts of the representation of U and V.

2. Set EW equal to EU-EV + &81, while FW is set to FU/FV.

3. Normalise the floating point number W.

These descriptions are based on the routines found in the BASIC II ROM. The routines in BASIC I are almost exactly the same, but they are at different places.

If you don’t know which version of BASIC your machine has, there is an easy way to find out. Press the ‘break’ key, and type REPORT. BASIC II will respond with:

BASIC I gives the copyright date as 1981.

BASIC has to deal with floating point numbers from a number of sources. To speed things up, all numbers are moved into two sets of page zero locations called the ‘floating point accumulators’ - 1 shall abbreviate them to FAC ft 1 and FAC ft 2. They are mapped as follows:

SIGN

OVER/UNDERFLOW EXPONENT MANTISSA 1 MANTISSA 2 MANTISSA 3 MANTISSA 4 MANTISSA 5

-&2E (FAC ft 1) -&2F (FAC ft 1) -&30 (FAC ft 1) -&31 (FAC ft 1)

- &32 (FAC ft 1)

- &33 (FAC ft 1)

- &34 (FAC ft 1)

- &35 (FAC ft 1)

and &3B (FAC ft 2)

and &3C (FAC ft 2)

and &3D (FAC ft 2)

and &3E (FAC ft 2)

and &3F (FAC ft 2)

and &40 (FAC ft 2)

and &41 (FAC ft 2)

and &42 (FAC ft 2)

(The accumulators are at the same addresses for both versions of BASIC.) To take each element of the accumulators individually:

56

i

FLOATING POINT ARITHMETIC

The sign byte is used to hold the sign after it has been moved out of the mantissa. Although a full byte is used, only bit 7 is significant. As normal, if bit 7 is set, the number is negative, else it is deemed to be positive.

The over/underflow byte is used to check when accuracy has been lost during a calcu¬ lation. At the start of a calculation, zero is stored there. Then, every time underflow is detected, it is decremented, and whenever overflow is detected, it is incremented. If> at the end of the calculation, this location still contains zero, no action is taken. If a negative number is found, zero is returned. This ensures that the computer won’t do something silly like print 0.000000001 when it means zero, which other BASIC inter¬ preters are prone to do. If the number is found to be positive, the error message ‘Too big’ is given, and the routine terminates. This scheme allows one underflow to cancel out one overflow and vice versa.

The exponent is entirely standard.

The mantissa is odd, because it has five bytes allocated to it, rather than the four bytes you might expect. The least significant byte (MANTISSA 5) is called the ‘rounding byte’ in some quarters, and that is exactly the purpose it serves. It helps remove the danger of the situation where a number is shifted to the right and then to the left successively. If the extra byte were not supplied, we would lose a bit for every shift. As a side effect of this, the rounding byte also allows the computer to carry out quite accurate internal calculations - to about 12 significant figures - and then round this figure to the normal precision. Generally, when we speak of the mantissa, we include the rounding byte in the expression.

The mantissa has always had the sign bit in the mantissa replaced by a true numeric bit before it reaches the computer.

We will start by looking at the normalisation algorithm used by BBC BASIC. This description is only in terms of the algorithm used. (For the precise details of how it is implemented, see the ROM listing.)

I will present the algorithms in a sort of bastardised BBC BASIC. They cannot be typed directly into the computer because they use several mythical features, but they should be easy to understand. Particularly esoteric features include the functions B0, B 1, B2 etc, which extract the indicated bit from a variable. Notice that some of the time the mantissa is treated as one variable, at others it is an array of the bytes making it up (with the index starting at 1, not zero).

10 REM BBC BASIC Normalisation algorithm 20 IF B7(M ANTISS A( 1 )) THEN ENDPROC 30 IF MANTISSA = 0 THEN. ENDPROC 40 IF B7(MANTISSA(1)) THEN ENDPROC 50 IF M ANTISS A(l)< > 0 THEN GOTO 160

57

THE BBC MICRO COMPENDIUM

60 MANTISSA(l) = MANTISSA(2)

70 MANTISSA(2) = MANTISSA(3)

80 MANTISSA(3) = MANTISSA(4)

90 MANTISSA(4) = MANTISSA(5)

100 MANTISSA(5) = 0

110 EXPONENT = EXPONENT-8

120 IF EXPONENT didn’t dip below zero THEN GOTO 40 130 UNDERFLOW = UNDERFLOW-1 140 GOTO 40

150 IF B7(MANTISSA(1)) THEN ENDPROC 160 Shift whole lot left one position 170 EXPONENT = EXPONENT-1

180 IF EXPONENT didn’t dip below zero THEN GOTO 150 190 UNDERFLOW = UNDERFLOW- 1 200 GOTO 150

Even that may require some comments:

Line 20 leaves the routine if it has been entered with the number already normalised. Line 30 leaves the routine if the number was zero.

Line 40 again tests to see if the number is normalised. This is the start of a loop, so we have to have another test.

Line 50 decides whether the shift required should be in terms of bits or bytes. If the whole first byte of the mantissa is zero, there will have to be at least one byte shift before we stand a chance of meeting a set bit.

Line 60 starts a byte shift of all the bytes in the mantissa. It acts rather like a chain of firepersons passing buckets. Or, it could be described as being like a row of sports cars edging towards a zebra crossing.

Line 110: we’ve just done a shift of eight bits, so we need to inform the exponent of this fact. This is done by subtracting eight from it.

Line 120 tests to see if underflow occured. In the ROM this is done by examining the carry flag, but there is no easy way of showing this in BASIC.

Line 130 adjusts the underflow counter.

Line 140 returns control to the start of the loop. Once there, a further check will be made to see if another byte shift needs to be made. If there isn’t, line 50 will pass control to the code to carry out bit shifts.

Line 150 checks to see if the number has yet been normalised.

58

FLOATING POINT ARITHMETIC

Line 160 shifts the entire mantissa one position to the left. Again, it was difficult to encode this in BASIC. 5

Line 170 decrements the exponent to reflect the shift just carried out.

Lines 180 to 200 again check for underflow before passing control back to the start of the loop to check whether the number has been normalised, and whether a new bit shift is needed.

So, it can be seen that the clever thing about the routine is that it doesn’t blindly shift the mantissa left - it rather intelligently does the bare minimum number of shifts required. This is because eight shifts next door to each other correspond to a block move

Most of the other routines bear very little resemblence to our original algorithms.

For example, here is the algorithm used for floating point addition. It adds FAC# 1 to FAC #2, leaving the answer in FAC#1. Obviously, the same routine is used for subtraction:

(EXP# 1 means the exponent of FAC# 1, MAN #2 means the mantissa of FAC #2, etc.)

10 REM BBC BASIC addition algorithm 20 IF MAN #2 = 0 THEN ENDPROC 30 IF MAN #1 = 0 THEN MAN # 1 = MAN # 2:ENDPROC 40 IF EXP # 1 = EXP #2 THEN GOTO 410 50 IF EXP # 1< EXP # 2 THEN GOTO 240 60 DIFF = EXP#1-EXP#2 70 IF DIFF>&25 THEN ENDPROC 80 NUM = DIFF AND &38 90 IF NUM = 0 THEN GOTO 180 100 NUM = NUM DIV 8 110 FOR TEMP = 1 TO NUM 120 MAN #2(5) = MAN #2(4)

130 MAN #2(4) = MAN #2(3)

140 MAN # 2(3) = MAN # 2(2)

150 MAN # 2(2) = MAN #2(1)

160 MAN #2(1) = 0

170 NEXT TEMP

180 NUM = DIFF AND 7

190 IF NUM = 0 THEN GOTO 410

200 FOR TEMP = 1 TO NUM

210 Shift MAN #2 right one bit

220 NEXT TEMP

230 GOTO 410

59

THE BBC MICRO COMPENDIUM

240 DIFF = EXP# 2-EXP ft 1

250 IF DIFF>&25 THEN ENDPROC

260 NUM = DIFF AND &38

270 IF NUM = 0 THEN GOTO 360

280 NUM = NUM DIV 8

290 FOR TEMP = 1 TO NUM

300 MAN #1(5) = MAN #1(4)

310 MAN #1(4) = MAN #1(3)

320 MAN #1(3) = MAN #1(2)

330 MAN #1(2) = MAN #1(1)

340 MAN# 1(1) = 0

350 NEXT TEMP

360 NUM = DIFF AND 7

370 IF NUM = 0 THEN GOTO 410

380 FOR TEMP = 1 TO NUM 390 Shift MAN#1 right one bit 400 NEXT TEMP

410 IF SIGN # 1 = SIGN # 2 THEN GOTO 510

420 IF MAN # 1 = MAN#2 THEN MAN # 1 = 0:ENDPROC

430 IF MAN # 1> MAN # 2 THEN GOTO 480

440 MAN # 1 = MAN # 2-MAN # 1

450 SIGN # 1 = SIGN # 2

460 Normalise

470 ENDPROC

480 MAN # 1 = MAN # 1-MAN # 2 490 Normalise

500 ENDPROC

510 MAN # 1 = MAN # 1 + MAN#2 520 Normalise 530 ENDPROC

(You may have noticed the deliberate error near line 510. In all probability, MAN# 1 + MAN #2 will overflow to the left. In the ROM whenever this happens the exponent is decremented and the mantissa is shifted one position to the left.)

Line by line notes:

Line 20 checks to see if the second of the two numbers is zero. If it is, the routine simply exits, since the other number is going to be the answer.

Line 30 checks to see if the other number is zero. If it is, it has to copy the second number into the answer accumulator.

Line 40 checks to see if the exponents of the two numbers are already equal. You will

60

FLOATING POINT ARITHMETIC

recall that the main purpose of the preamble of the addition routine is to match up the exponents, so if they are matched on entry, the computer takes advantage and skips to the later code.

Line 50 works out which exponent is the smaller. If EXP ft 1 is the smaller, then it goes off to perform shifts upon MAN ft 1, otherwise it continues and shifts MAN ft 2.

Line 60 works out how different the exponents are. This informs us how many shifts are going to be required to do the matching.

Line 70 ignores the addition if the difference is too huge. This is because adding a very small number (like 1) to a very large number (like 34.45E32) will not make a noticeable impression on the larger number.

Line 80 works out how many bytes need to be shifted. If DIFF contains the number of bits, then DIFF DIV 8 is going to contain the number of bytes. This division is not done straight away, since it keeps things nice and fast. Thus, the computer masks all the bits out of the difference, except those that determine the number of bytes to move. The section on Boolean arithmetic should make this use of the AND operation clear.

Line 90 checks to see if there are no bytes to move. If there aren’t any, then it skips off to look at how many bits need to be moved.

Line 100 divides the number of bits to move by 8, so that it can be used as a loop index. Line 110 starts a loop of the number of bytes that need shifting.

Lines 120 to 160 carry out a byte shift to the left (away from the bicimal point).

Line 170 terminates the loop.

Line 180 uses the AND operation again, this time to work out how many bits should be moved.

Line 190 ensures that we don’t try to do zero shifts, by skipping the shifting code if it is not needed. The place it skips off to is where the actual addition is done.

Line 200 starts a loop through the number of shifts required.

Line 210 performs the shift itself.

Line 220 terminates the loop.

Line 230 jumps off to the code for doing the actual addition

Lines 240 to 400 are similar to lines 60 to 220, except that they shift MAN ft 1.

61

THE BBC MICRO COMPENDIUM

Line 410 is the start of the code that does the addition itself. First, it checks to see if the two numbers have the same sign. If they have, it goes offto line 510. The point is that if they have the same sign, a normal addition is required, but if they have different signs it is quicker to assume that they are both positive, but subtract one from t’other. *

Line 420 checks to see if the mantissas are the same. If they are, the answer will be zero, since the signs are different, and adding X and -X will always yield zero.

Line 430 works out which of the mantissas is the larger. If MAN ft 1 is larger, then MAN ft 1 -MAN ^ 2 must be computed, otherwise MAN ft 2-MAN ft 1 is computed.

Line 440 does the said subtraction.

Line 450 sets the sign of the answer be the sign of mantissa number two.

Line 460 normalises the answer, using the normalisation routine we looked at earlier. Line 470 exits the routine.

Line 480 subtracts the other way, since MAN ft 1 is the larger.

Line 490 normalises the answer.

Line 500 exits the routine.

Line 5 10 is used when the numbers have the same sign. It adds the two numbers, using normal integer arithmetic.

Line 520 normalises this answer.

Line 530 exits the routine.

In assembly language, all this is amazingly short.

The routine is faster than the traditional one because it adopts a useful programming principle, the gist of which is ‘Never write a single, complex, routine where several simpler ones would do’.

For example, the routine would have been shorter if, instead of having separate code for situations when either exponent is the smaller, simply doing a swap if one exponent is larger. But it would also be slower.

In addition, all the shifting operations use the by now familiar approach of sussing out the number of bytes to shift before thinking about the number of bits.

62

FLOATING POINT ARITHMETIC

Another way of looking at it is that most of the instructions in the routine actually do something useful, rather than simply decode material, or move things to the right locations.

Now, for a change, we’ll try something difficult. Here is the multiplication algorithm:

(This routine needs to use a third mantissa, called MAN $3. This is located at &42 onwards.)

10 REM BBC BASIC Multiplication 20 IF MAN #1 = 0 THEN ENDPROC 30 IF MAN #2 = 0 THEN FAC £1 = 0:ENDPROC 40 TOT = EXP #1 + EXP £2

50 IF TOT didn’t go above 255 THEN GOTO 70 60 OVERFLOW = OVERFLOW + 1 70 TOT = TOT-&80 80 EXP# 1 = TOT

90 IF TOT didn’t dip below zero THEN GOTO 110 100 UNDERFLOW = UNDERFLOW-1 110 MAN#3 = MAN # 1 120 MAN #1 = 0

130 SIGN # 1 = SIGN # 1 EOR SIGN#2 140 FOR TEMP = 1 TO 32 150 shift FAC #2 right 160 shift FAC #3 left

170 IF a bit fell off the end THEN MAN # 1 = MAN # 1 + MAN#2 180 NEXT TEMP 190 Normalise 200 ENDPROC

Again, this routine fudges the issue of overflow when adding - see line 170. You should also note than UNDERFLOW and OVERFLOW both refer to the same location - they are refered to differently to make the algorithm easier to follow.

Line by line notes:

Line 20 ignores the multiplication request if FAC# 1 = 0, since this would obviously give an answer of zero.

Line 30 does the same for FAC #2. Of course, zero has to be copied into the answer accumulator before the routine can be left.

Line 40 adds the two exponents together. Lines 50 and 60 take care of any overflow that may have occured as a result of the addition.

63

THE BBC MICRO COMPENDIUM

Line 70 subtracts &80 from the total of the two exponents. This is the bias used by the BBC Micro.

Line 80 uses this answer as the final exponent.

Lines 90 and 100 deal with any underflow generated by this subtraction. This code is a good example of the need for the over/underflow byte. If we simply gave an error message every time the addition at line 40 overflowed, we would be ignoring the fact that the answer might well be reduced to the correct range by subtracting &80 from it.

Line 110 copies MAN ft 1 to MAN ft 3. This is because the answer will be built up in MAN ft 1, but we still need to access the contents of it.

Line 120 places zero in MAN ft 1. This simply initialises the answer.

Line 130 uses the exclusive OR of the two signs as the sign of the answer. This is because multiplying two numbers of different signs yields a negative answer, while the same signs leads to a positive answer. If you draw a truth table up of these facts, you will see that the EOR instruction takes care of all the considerations.

Line 140 starts up a loop through all 32 bits of MAN ft 1 . This loop is really a normal multiplication routine. So, the whole routine is only a few bits and pieces concerned with getting the sign and exponent right, followed by a nice simple multiplication routine.

Line 150 shifts the multiplicand right. This divides it by two.

Line 1 60 shifts FAC ft 3 left. This is simply so we can inspect the least significant bit of it.

Line 170 adds the multiplicand and multiplicator if a bit did indeed fall off the end. Line 180 terminates the loop.

Unfortunately, the method the BBC Micro uses for floating point division is not suitable for conversion into the BASIC-like programs we have previously looked at. Instead, you can look at the precise details in the ROM listing. It turns out that the division algorithm is the one most similar to the classical algorithm.

It is worth looking at some of the algorithms used by BBC BASIC to compute func¬ tions and other operators. For example SQR is computed from this algorithm:

(Notice that this algorithm uses extra accumulators. These are indicated as FAC ft (X), where X is the address of the fake accumulator).

64

FLOATING POINT ARITHMETIC

10 REM BBC BASIC square root 20 IF FAC ft 1 = 0 THEN ENDPROC

30 IF SGN(FAC$ 1)=-1 THEN PRINT "Negative root":END

40 FAC#(&46C)=FAC#1

50 EXP ft 1 = (EXP ft 1 DIV 2)+&40 60 FOR TEMP = 1 TO 5 70 FACft(&471) = FACftl 80 FAC ft 1 = FAC ft (&46C)/FAC ft 1 90 FACftl=FACftl+FACft(&471)

100 EXPftl=EXPftl-l 110 NEXT TEMP 120 ENDPROC

This is a disguised copy of the classical square root algorithm. Rather than try to explain it directly, here is a BASIC version that you can actually RUN normally:

> LIST

10 REM FilenametSQRT 20

30 REM SQR demonstration 40

70 INPUT "Number:" A

80 PRINT "The machine says:"SQR(A)

90 IF A = 0 THEN PRINT "Ruston says:"0:END 100 IF SGN(A) = -1 THEN PRINT "-ve root":END 110 A46C = A 120 EX = TOP + 3 130 ?EX = (?EX DIV 2) + &40 140 FOR TEMP = 1 TO 5 150 PRINT A 160 A471 = A 170 A = A46C/A 180 A = A + A471 190 ?EX = ?EX-1 200 NEXT TEMP 210 PRINT "Ruston says: "A

>

Running this program will verify that the algorithm works.

Notice that the exponent of FAC ft 1 (which is stored in the variable A) is accessed by directly messing around in the computers memory. This will only work if A is the first variable to be defined in the program.

65

THE BBC MICRO COMPENDIUM

“Diversion”, “Bresenham meets Moire”

This program uses a very fast algorithm for drawing circles (Bresenham’s algorithm) to draw an intricate display composed of Moire patterns.

The main circle procedure, PROCcircle, only generates the points on the circumfer¬ ence of one 45 degree quadrant of the circle, while PROCcirc _ points repeats each

point around the circumference of the circle.

In this example, points are not drawn on the edge; lines are inverted from the centre of the screen, through the point in question and off the edge of the screen.

> LIST

10 REM Filename:Moire 20

30 REM Moire patterns using Bresenham’s circle algorithm 40

70 MODE 0 80 XF% = 4: YF% = 4 90 GCOL 4,0

100 PROCcircle(640,5 12,850)

110 END 120

130 DEF PROCcirc _ points(X% , Y % ,L% ,M%)

140 LOCAL K%

150 K% = 5

160 L% = L%*XF%:X% = X%*XF%

170 M% = M%*YF%:Y% = Y%*YF%

180 MOVE L%,M%:PLOT K%,L% + X%,M% + Y%

190 MOVE L% ,M% :PLOT K%,L% + Y%,M% + X%

200 MOVE L% ,M% :PLOT K%,L% + Y%,M%-X%

210 MOVE L%,M%:PLOT K%,L% + X%,M%-Y%

220 MOVE L% ,M% :PLOT K%,L%-X%,M%-Y%

230 MOVE L% ,M% :PLOT K%,L%-Y%,M%-X%

240 MOVE L% ,M% :PLOT K%,L%-Y%,M% + X%

250 MOVE L% ,M% :PLOT K%,L%-X%,M% + Y%

260 ENDPROC 270

280 DEF PROCcircle(L% ,M% ,R%)

290 L% = L% DIV XF%

300 M% = M% DIV YF%

310 R% = R% DIV XF%

320 LOCAL X%,Y%,D%

66

FLOATING POINT ARITHMETIC

67

THE BBC MICRO COMPENDIUM

330 X% = 0 340 Y% = R%

350 D% = 3-2*R%

360 IF X%> Y% THEN GOTO 410 370 PROCcirc _ points(X%,Y%,L%,M%)

380 IF D%< 0 THEN D% = D% + 4*X% + 6 ELSE D% = D% + 4*(X% -Y%) + 10:Y% = Y%-1 V

390 X% = X% + 1 400 GOTO 360

410 IF X% = Y% THEN PROCcirc_points(X%,Y%,L%,M%)

420 ENDPROC

>

“Diversion”, “Blowing up the screen”

This simple program is a good exercise in programming graphics displays in assembly language. It enlarges the top half of the screen so that it fills the entire screen. It only directly works in 20K MODES (0, 1 and 2), but it can easily be adapted for all MODEs except MODE 7.

The program in its present form requires you to select a suitable MODE and fill the top of the screen with the required text before you type ‘RUN’.

The first part of the program, from line 120 to 190, builds a table of the start addresses of each horizontal line of pixels. This is done by setting a 16 bit variable to the start address of the screen, &3000, and the Y register to the current row number (counting from the top). The program then loops through all the rows, placing the current address in the table. The address is then incremented. If the current row number is the last in a group of eight, a further constant is added to allow for the organisation of memory. I have coded the problem in a slightly more obscure, but probably faster, way. Executing the immediate mode command ‘MODE 0:FOR T% = &3000 TO &7FFF STEP 4:!T% = -1:NEXT’ will make the memory organization clearer.

The next section, from line 200 to line 230 computes a similar table for the X coordi¬ nates. The X coordinates only stretch from 0 to 79 since we are dealing in bytes, not pixels.

Lines 260 to 290 make up the address subroutine. This returns the address of the byte with coordinates X, Y.

Lines 310 to 380 enlarge the screen by taking a pixel from X,Y and replacing it at X,Y*2 and X,Y*2 + 1.

> LIST

10 REM FilenamerENLRGE

68

FLOATING POINT ARITHMETIC

20

30 REM Blowing up the screen 40

70 DIM R% 2000

80 DIM lsb 256, msb 256, lab 80,mab 80 90 FOR T% = 0 TO 2 STEP 2 100 P% = R%

110[OPT T%

120. construct

130 ldy ft 0:sty&8 1 :lda ft &30:sta&80

140. coni lda&80:sta msb,Y

150 lda&81:sta lsb,Y

160 inc &81:lda ft8:bit &81

170 beq con2:lda &81:eor ft 128 + 8:sta&81

180 inc &80:inc &80:ldaftl28:bit&81:bnecon2:inc &80

190.con2 iny:bne coni

200 ldy ft 0:sty&80:sty&8 1

210.con3 lda&80:sta lab,Y:lda&81:sta mab,Y

220 Ida ft 8 : clc : adc&80 : sta&80 : Ida ft 0 : adc&8 1 : sta&8 1

230 iny:cpyft80:bnecon3

240 rts

250

260.address

270 Ida lsb,Y:clc:adc lab,X:sta &80 280 Ida msb,Y:adc mab,X:sta &81 290 rts 300

310. demo

320 ldaft 127:sta&82 330.deml ldaft79:sta&83

340.dem2 ldx&83:ldy&82:jsr address:ldyftU:lda (&80),Y:sta&84

350 ldx&83:lda&82:aslA:tay:jsr address:ldyft0:lda &84:sta (&80),Y

360 ldx&83 : lda&82 : aslA : tay : iny : jsr address:ldyft0:lda &84:sta (&80),Y

370 dec&83:bpl dem2

380 dec&82:bpl deml

390 rts

4001NEXT

410 CALL construct 420 REPEAT 430 CALL demo 440 UNTIL GET = 13

69

Evaluating Expressions

Most programming languages permit you to write expressions in normal algebraic form, rather than some crazy internal form. For example, you can happily write ‘2 + 2’ in BBC BaSIC, and the computer will automatically convert it to its own form.

However, when we start to write our own languages, we have to learn how to do this conversion ourselves.

Most computers convert expressions to reverse Polish notation as their internal form.

There are some other pieces of notation you should be familiar with: an operand is a passive part of an expression, such as a number or a variable.

an operator is an active part of an expression, such as the symbols *, - ,+ and /. Operators come in two varieties - binary and unary. Binary operators require two operands to arrive at an answer, while unary operators only require a single operand. Thus, * is a binary operator, whilst the ? in ‘?a%’ is a unary operator.

In reverse Polish notation, all operators are written after their operands. So we have to write 2 2 + rather than 2 + 2. This doesn’t seem particularly helpful, but we shall see later that computers can evaluate reverse Polish expressions rather efficiently and easily.

We can thus reduce our task to that of discovering how to convert expressions to reverse Polish notation.

In fact, BBC BaSIC converts expressions to reverse Polish notation so subtly that it is almosnransparent. We still need to look at some classical algorithms for converting to reverse Polish notation, since these form the basis of the BBC BaSIC method. The compilers we will look at in this book use a fairly classical approach to the conversion.

The exoressions we will initially convert will not contain brackets and will only involve the operations +, * and /. Operands will be restricted to variables named

with a single letter or numbers.

Most of us would give the answer 14 to the sum 2 + 3*4, even be interpreted as (2 + 3)*4, which is 20. The reason we arrive

though the answer could at the first answer is that

70

EVALUATING EXPRESSIONS

Zw1^atl°’j1 ^ intyitiveJy calculated before addition. Multiplication is said to have a g p ece ence than addition or subtraction. The order of precedence of the other operators is usually as follows:

*,/

+,-

Thus, ‘2 + 3*4’ is ‘2 3 4 * +’ in reverse Polish notation, but ‘(2 + 3)*4’ is ‘2 3 + 4 *’.

mcuia5> although we take the precedence of operators into account without too much thought, a computer must be explicitly taught about precedence.

The above example of reverse Polish notation, ‘2 3 4*+’, may also cause some prob¬ lems. It could be computed in the following steps:

234* +

2 12 +

14

Thus, although the figure 2 appears before the other numbers, it is actually used last.

The way a computer computes reverse Polish notation is rather different. Taking the same example, a computer would scan the expression from left to right.

When it comes across a number (or a variable) it pushes that number onto the stack. If it comes across an operator, it executes that operator using as data the top two numbers on the stack leaving the result on the stack.

At the end of the expression, the answer will be the number on the stack. If more than one number was left on the stack, there were not enough operators in the expression, as in the incomplete expression ‘2*’.

Unary operators are computed from the single number at the top of the stack.

This BASIC program shows a simple algebraic to RPN routine:

> LIST

10 REM Filename: EXP 1 20

30 REM RPN converter 40

70 INPUT "Enter expression:" EX$ 80 STACKS = ""

90

71

THE BBC MICRO COMPENDIUM

100 PROCexp 110 PRINT

120 IF EX$< > "" THEN PRINT "Badly formed expression"

loO END

140

150 DEF PROCpush(A$)

160 STACKS = STACKS + A$

170 ENDPROC 180

190 DEF FNpull 200 LOCAL G$

210 G$ = RIGHT$(STACK$,1)

220 STACKS = LEFT$(STACK$,LEN(STACK$)-1)

230 = G$

240

250 DEF FNprec(AS) = INSTR(" + -*/", AS)

260

270 DEF PROCexp 280 LOCAL TEMPS 290 PROCoperand 300 TEMPS = EX$

310 PROCoperator

320 IF EX$<> TEMPS THEN GOTO 290 330 REPEAT

340 IF STACKSO"" THEN PRINT FNpull;" ";

350 UNTIL STACKS = ""

360 ENDPROC 370

380 DEF PROCoperand 390 LOCAL L$

400 L$ = LEFT$(EX$,1)

410 EXS = MID$(EX$,2)

420 IF L$> = "A" AND L$< = "Z" THEN PRINT L$;" ";:ENDPROC 430 IF LS< "0" OR L$> "9" THEN PRINT "Bad operand":END 440 PRINT L$;

450 L$ = LEFT$(EX$,1)

460 IF L$< "0" OR L$> "9" THEN PRINT " ";:ENDPROC 470 EXS = MID$(EX$,2)

480 PRINT L$;

490 GOTO 450 500

510 DEF PROCoperator 520 LOCAL L$

530 LS = LEFT$(EX$,1)

540 IF FNprec(L$)< 1 OR L$ = "" THEN ENDPROC

72

EVALUATING EXPRESSIONS

550 EX$ = MID$(EX$,2)

560 IF FNprec(L$)< = FNprec(RIGHT$(STACK$,l)) AND STACK$<

> "" THEN PRINT FNpull;" ";:GOTO 560 570 PROCpush(L$)

580 ENDPROC

> RUN

Enter expression: 12 + 32 12 32 +

> RUN

Enter expression: 12 + 34*45/3 12 34 45 3 / * +

> RUN

Enter expression: 1 + 2 + 3 + 4 + 5*6 12 + 3 + 4 + 56* +

> RUN

Enter expression:23*23 + 45*45 23 23 * 45 45 * +

>

The expression evaluation routine starts ofFby scanning for an operand. If it can’t find one, it gives an error message. Otherwise, the operand is printed out.

Then it checks to see if the next thing in sequence is an operator. If it is not it goes off and unstacks all the operators that are on the stack before exitting.

If it is an operator, it examines the operator to see whether the precedence of the operator on top of the stack is greater than or equal to the precedence of the operator in question. If it is, it unstacks the top operator and goes back to ask itself the question again. If, however, the precedence of the top operator is less than the precedence of the operator in question, it stacks the operator in question and goes back to get another operand.

Unfortunately, the vagaries of BASIC have prevented a readable program being writ¬ ten; particularly irritating in this case is the absence of the WHILE program control statement. It would be a good exercise to try and work out where the WHILE construc¬ tion could have been used, had it been available.

It is still worth giving line by line notes:

Line 70 gets the expression string from the user. As the expression is scanned, char¬ acters are knocked off the left hand side, which removes the need to maintain a separate pointer to the current character in the expression.

Line 80 initialises the thing we’ll use as the stack. We can use a single string by simply adding and knocking characters off the right hand end. Luckily, everything we may want to put on the stack is only going to be a single character long, so we won’t have too much extraneous code.

73

THE BBC MICRO COMPENDIUM

Line 100 calls the expression evaluator procedure. The procedure will knock off all the characters it could cope with, leaving the unconverted residue in EX$.

Line 110 moves the cursor to a new line.

Line 120 checks to see if the entire expression was converted. If it wasn’t, it assumes there was an error, and issues the appropriate message.

Line 130 terminates the program.

Lines 150 to 170 comprise PROCpush. They simply add the single character string indicated on to the end of the stack string.

Lines 190 to 230 comprise FNpull. In this case, a character is pulled off the end of the string. Notice the use of a temporary variable.

Line 250 computes the precedence of a given operator, using the INSTR function. Line 270 starts PROCexp

Line 290 goes to get an operand. PROCoperand will give an error message if it couldn’t find one.

Line 300 stores the current state of EX$ in TEMP$. This is done so that we can tell if PROCoperator managed to find an operator or not.

Line 310 calls PROCoperator to look for one.

Line 320 checks to see if EX$ has been changed by PROCoperator. If it has, control is passed back to look for another operand.

Lines 330 to 350 empty the stack, printing everything out as they do so.

Line 380 starts the definition of PROCoperand.

Line 400 extracts the leftmost character.

Line 410 knocks this character off EX$.

Line 420 checks to see if the character we pulled off was a variable name. If it was, the name is printed, and the routine ends.

Line 430 checks for a digit. If one is not found, an error message is given.

Line 440 prints this first digit.

74

EVALUATING EXPRESSIONS

Lines 450 to 490 repeatedly check for more digits, printing them as they go along. Lines 510 to 580 comprise PROCoperator.

Line 530 gets the left most character.

Line 540 checks to see if it is a valid operator. If it is not, the routine is exitted.

Line 550 extracts this operator from the expression string.

Line 560 checks to see if the precedence of the new operator is less than or equal to that of the one at the top of the stack. If it is, the top operator is pulled and printed.

Line 570 pushes the new operator onto the stack.

Line 580 exits PROCoperator.

There is one problem with this kind of expression evaluator. A simple expression like "2 + 2" will get converted to the RPN form "2 2 + ". This will be computed using the following steps:

1 . Load 2 into a register

2. Push the register onto the stack

3. Load 2 into a register

4. Push the register onto the stack

5. Pull the top of the stack to a register

6. Pull the next number to a different register

7. Add the registers

8. Push the result

On the other hand, the only instructions actually needed are:

LDA #2 CLC ADC #2

Thus, this method is rather verbose.

We shall now look at an expanded version of the program, which allows such things as brackets and unary operators.

Here is an improved version of the RPN converter program. This time, we can cope with functions (each of which takes a single argument) which are named ‘a’ to ‘z’, and the unary plus and minus signs. In addition, exponentiation has been added. Brackets are now legal too.

The sample runs after the listing will give you an idea of how it works.

75

THE BBC MICRO COMPENDIUM

> LIST

10 REM Filename :EXP2 20

30 REM Second RPN converter 40

70 REM Variables = A-Z 80 REM Functions = a-z 90 REM Operators = +

100

110 STACKS = ""

120 INPUT "Enter expression:" EX$

130 PROCexp

140 IF EX$< > "" THEN PRINT "Bad operator" 150 IF POS< > 0 THEN PRINT 160 END 170

180 DEF FNprec(A$) = INSTR(":- + /*'‘~\",A$)

190

200 DEF FNtop = LEFT$(STACK$,1)

210

220 DEF FNpull 230 LOCAL V$

240 V$ = FNtop

250 STACKS = MID$(STACK$,2)

260 = VS 270

280 DEF PROCpush(AS)

290 STACKS = AS + STACKS

300 ENDPROC

310

320 DEF FNcur = LEFT$(EX$,1)

330

340 DEF FNnext

350 LOCAL VS

360 VS = LEFT$(EX$,1)

370 EX$ = MID$(EX$,2)

380 = VS 390

400 DEF PROCexp 410 LOCAL OPS 420 PROCpush(": ")

430 REM Main loop 440 PROCoperand

76

EVALUATING EXPRESSIONS

450 OPS = FNoperator

460 IF OP$ = "" THEN GOTO 510

470 IF FNprec(FNtop)> =FNprec(OP$) THEN PRINT FNpull;" GOTO 470 480 PROCpush(OP$)

490 GOTO 430 500

510 OP$ = FNpull

520 IF OP$< > ":" THEN PRINT OP$;" ";:GOTO 510

530 ENDPROC

540

550 DEF FNoperator 560 LOCAL OPS 570 OP$ = FNcur

580 IF INSTR(" + *-r~",OP$) THEN = FNnext 590 = ""

600

610 DEF PROCoperand 620 LOCAL N$,FU$

630 N$ = FNnumber

640 IF N$< > "" THEN PRINT NS;" ";:ENDPROC 650 N$ = FNvariable

660 IF N$< > "" THEN PRINT N$;" ";:ENDPROC 670 IF FNcur THEN PROCpush("~"):N$ = FNnextrGOTO 630 680 IF FNcur = " + " THEN PROCpush("\"):N$ = FNnextrGOTO 630 690 IF FNcur = "(" THEN GOTO 730

700 IF FNcur> = "a" AND FNcur< = "z" THEN GOTO 740 710 PRINT "Bad operand"

720 END

730 NS = FNnext:PROCexp:IF FNnext = ")" THEN END PROC ELSE PRINT "Missing right bracket":END 740 FU$ = FNnext:N$ = FNnext:PROCexp:IF FN next = ")" THEN PRINT FU$;" ";:ENDPROC ELSE PRINT "Miss ing right bracket to function": END

DEF FNnumber LOCAL SA$,SG$

SA$ = EX$

IF FNcur = " + " OR FNcur ="-" THEN SG$ = FNnext ELSE SG

IF FNcur< "0" OR FNcur> "9" THEN GOTO 830 SGS = SGS + FNnext GOTO 800

IF STRS(VAL(SG$)) = SG$ THEN = SG$ ELSE EX$ = SA$: = ""

750

760

770

780

790

$=""

800

810

820

830

840

77

THE BBC MICRO COMPENDIUM

850 DEF FNvariable

860 IF FNcur> = "A" AND FNcur< = "Z" THEN = FNnext ELSEr ""

> RUN

Enter expression^ + 2 2 2 +

> RUN

Enter expression: 23 + (23 + 23*23)

23 23 23 23 * + +

>RUN

Enter expression^ + c(2 + (3-c(4A(3 + -3))))

12343 -3 + A c - + c*

>

When the computer has to work out a function, it simply pulls the value off the top of the stack, uses it in the function and places the answer on the stack.

Line by line notes:

Line 1 10 sets the string variable STACK$ to the null string. STACKS will hold the operator stack.

Line 120 accepts the expression for conversion from the user of the program.

Line 130 calls PROXexp, which will decode as much of EX$ as it can. When it comes to something it cannot decode, (it could be a comma at the end of a expression - as in the PRINT statement) it will return and EX$ will contain the portion of the expression it failed to translate. The same idea was used in the previous converter.

Line 140 checks to see if EX$ is equal to the null string. If it is not, it then prints the message " Bad operator" . If EX$ is completely empty, the entire expression was successfully converted, so no message is given.

Line 1 50 checks to see if the cursor is positioned at the left edge of the screen, and if it is not, it prints a newline character to move to a new screen line.

Line 180 defines a function which returns the precedence of a given operator. It does this by finding the position of that operator in a master string of operators, which are arranged according to precedence, using the INSTR function. As you can see, the colon is an imaginary operator that I have introduced. It is put onto the stack at each call to PROCexp. It has the lowest precedence of all, which means that it is not pulled off the stack in normal circumstances. When PROCexp has finished, it simply empties the stack until it finds this colon. This allows the procedure to be recursive, as we shall see when we examine how I have implemented brackets. There are two other unusual operators in the list: \ is used to denote a unary plus, whilst ~ is used to denote unary minus.

Line 200 defines FNtop, which returns the operator at the top of the stack without

78

EVALUATING EXPRESSIONS

actually pulling it from the stack. Notice that, for maximum confusion, the stack grows from right to left in this converter, while it worked the other way around in the pre¬ vious program.

Line 220 starts the definition of FNpull, which pulls and returns the top operator from the stack.

Line 230 declares a local variable that we’ll need.

Line 240 extracts the top operator and places it in V$.

Line 250 shortens the stack string by knocking off the operator we have just placed in

Line 260 exits the function with the value v$.

Lines 280 to 300 define PROCpush, which pushes the operator A$ on to the stack. It does this in line 290 with the string concatenation.

Line 320 defines FNcur which returns the current character of EX$. This is done by the LEFTS function.

Line 340 starts the definition of FNnext. This function returns the next character from EX$, like FNcur, but it also knocks off the character.

Lines 350 to 380 are similar to FNpull, except they extract the character from EX$.

Line 400 starts the definition of PROCexp which is the main element of the program.

The first step, at line 410, is to declare OP$ to be a local variable. OP$ will be held to use the operator under consideration. This is one of the rare occassions where using a local variable is not only pretty, it’s necessary. The necessity springs from the recursive nature of the routine.

Line 420 pushes a colon onto the stack. This is the dummy operator used to sense the bottom of the stack.

Line 430 simply marks the start of the program’s main loop.

Line 440 calls PROCoperand which checks for and prints out the operand at the start of the expression string.

Line 450 sets OP$ to be the next operator encountered.

Line 460 checks to see if an operator was found. If it wasn’t, control is passed on to line 510 which will empty the stack.

79

THE BBC MICRO COMPENDIUM

Line 470 checks to see if the precedence of the operator on the top of the stack is greater than or equal to the precedence of the operator just found. If so, the top operator is printed and pulled from the stack, and control is passed back to the beginning of the line to try again.

Line 480 pushes the new operator onto the stack.

Line 490 goes back to find the operand that follows the operator.

Lines 510 to 530 pull another operator off the stack, checking if it is the dummy colon. If it was a colon, the procedure is exitted, otherwise the operator is printed and return is passed back to line 510 to try again.

Line 550 starts the definition of FNoperator which returns the next operator in the expression string.

Line 570 gets the current character.

Line 580 checks to see if it is a legal operator, using the INSTR operation as before.

Line 590 returns the null string if it was not a valid operator.

Line 610 starts the definition of PROCoperand. This is where it starts to get a bit complicated.

Line 630 gets a number from the left hand side of the expression string.

Line 640 checks to see if a number was found. If it wasn’t, N$ will be null. If the number was found, it is printed out, and the procedure is exitted.

Lines 650 and 660 do the same thing for a variable.

Line 670 checks for the presence of a unary minus sign. If one is present, the character is pushed onto the stack to represent the minus sign. Then the minus sign is stripped off with a dummy call to FNnext, after which control is returned to the start of PROCoperand. This is because unary operators are always followed by another operand.

Line 680 does the same for a leading plus sign.

Line 690 checks for left hand bracket, and if one is found, goes off to line 730 to deal with it.

Line 700 checks for a function call, passing control to line 740 if one is found.

Line 710 assumes that a bad operand has been found, and issues the appropriate message.

80

EVALUATING EXPRESSIONS

Line 730 is the section of code dealing with a left hand bracket. First, it pulls the bracket off the expression string, using a dummy call to FNnext. Then it calls PRO- Cexp to evaluate the expression left in EX$. PROCexp should then return when it comes to the closing bracket. This is checked for, and an error message is issued if it is absent.

Line 740 does the same sort of thing for the brackets in function calls, except that it prints the function name after the function argument has been evaluated.

Lines 760 to 860 are not worth commenting.

We shall be examining the BBC BASIC method when we look at the disassembly and when the SLUG compiler is discussed.

“Diversion”, “Drawing on the tube”

This program draws a complex pattern of a tube with writing on it. The clever point is the way that the writing wraps around the tube. The screen dump shows the output of the program.

The program takes a long time to run, and spends a considerable time building up a SIN and COS table, and a table of the dot patterns of the characters on the tube, so do not be alarmed if the program appears to be malfunctioning.

> LIST

10 REM FilenamerTUBE 20

30 REM Tubular writing 40

70 INPUT "Enter phrase:" A$

80 IF LEN(A$)> 8 THEN A$ = LEFT$(A$,8)

90 IF LEN(A$)< 8 THEN A$ = A$ + " "-.GOTO 90 100 LE% = LEN(A$)

110 DIM PO%(LE%,7),X% 100,SI%(35),CO%(35)

120 FOR T% = 0 TO 35

130 SI%(T%) = SIN(RAD(T%*5-45))*250

140 CO%(T%) = COS(RAD(T%*5-45))*250

150 NEXT T%

160 Y% = X% DIV 256 170 FOR T% = 1 TO LE%

180 ?X% = ASC(MID$(A$,T%,1))

190 A% = 10

81

THE BBC MICRO COMPENDIUM

82

EVALUATING EXPRESSIONS

200 CALL &FFF1

210 FOR P% = 0 TO 7

220 PO%(T%,P%) = ?(X% + 1 + P%)

230 NEXT P%,T%

240

250 MODE 0 260 VDU 29,640;0;

270 FOR T% = -640 TO 640 STEP 50

280 MOVE T%,1023

290 MOVE T% + 25,1023

300 PLOT 85,T%*6,0

310 PLOT 85, (T% + 25)*6,0

320 NEXT T%

330 VDU 26

340 FOR C% = -400 TO 1100

350 VDU29,C%-(C% MOD 2);C% + (C% MOD 2);

360 PROCsemi(C% + 400)

370 NEXT C%

380*SAVE P.TUBE 3000 8000

390 END

400

410

420 DEF PROCsemi(C % )

430 LOCAL B%,K%,A%,H%

440 B% = 2“(7-(C% DIV 4) MOD 8)

450 K% = 4

460 FOR T% = 0 TO 35

470 H% = (C%DIV32 + T%DIV8) MOD LE%

480 IF (PO%(H% + l,T%MOD8) AND B%) = 0 THEN GCOL 0,0 ELSE GCOL 0,1

490 PLOT K% ,SI% (T % ) ,CO%(T % )

500 K% = 5 510 NEXT T%

520 ENDPROC

>

“Diversion”, “Doubling the vertical screen resolution”

This program cannot be guarenteed to work correctly with all monitors - it works with about 50% of those I tried. Colour monitors and televisions work best.

Unless specifically told to do otherwise, the BBC Micro always generates an interlaced picture. Effectively, an interlaced picture means that every scan line is sent to the screen twice very close together, which stops the small black horizontal bars appearing, that sometimes marr the appearance of other computers’ output. It should be added that these are pretty unoticeable, unless you are close to the screen.

83

THE BBC MICRO COMPENDIUM

This means that in say, MODE 4, the computer is acutally sending 512 lines of information, not the 256 you might expect. However, it is possible to gain individual control over these bars which then allows us to have a vertical graphics resolution of 512, rather than the normal value of 256. This would give a resolution of 5 1 2 by 320 in MODE 4.

To explain more precisely, every time a vertical sync pulse, which happens every 50th of a second, is sent to the television, the screen will display first odd and then even scan lines. Normally, these two frames are identical, which is exactly what interlace is. On some micros the second set of scan lines is just sent as a black picture. If we can somehow send a different video image at each time when these vertical sync pulses reach it, we should be able to synthesize this extra large vertical resolution which is exactly what this program does. To allow us to control the image sent at each vertical sync pulse, I have decided to use two pages with MODE 4, which means that the screen uses a total of 20K of video RAM.

By switching between these two frames at every vertical sync pulse, it becomes pos¬ sible to display a different page on the odd and even sync pulses. For this to make sense, one has to place reasonable information in both video frames. This is done by printing some random characters on the MODE 4 screen. Then the odd scan lines are moved to the lower page, and the normal MODE 4 screen has the gaps removed.

> LIST

10 REM Filename:DOUBLE 20

30 REM 512 by 320 resolution for MODE 4 40

70 MODE 0 80 HIMEM = 12288 90 VDU 22,4

100 PROCassemble

110 PRINT "This is the BBC Micro Compendium.

I would like to thank a number of people who either made this boo- k possible, or made it a great deal easier: John Coll; Kathy Goudge- , who typed the original";

120 PRINT " manuscript; Benedicte de Germay; Chaz Moir and Rob Pickering from Computer Concepts; Carina Beeson, the ex¬ model; The people who make";

130 PRINT " Southern Comfort; The people who make ginger ale; Ten Years After; Led Zeppelin; Steppenwolf; Neil Young; Crosby, Sti¬ lls and Nash; Joni Mitchell; Jimi Hendrix; Buffalo Springfield; The- people behind Ribena; Donald Knuth; Dill Tudor";

84

EVALUATING EXPRESSIONS

140 PRINT "and all the other people too numerous to mention." 150 PROCmove 160

170 REPEAT 180 CALL bot 190 CALL top 200 UNTIL FALSE 210

220 DEF PROCassemble 230 DIM R% 200 240 FOR T% = 0 TO 2 STEP 2 250 P% = R%

260[OPT T%

270. top

280 lda#19:jsr &FFF4 290 lda#12:sta &FE00 300 lda#6:sta &FE01 310 rts

320

330.bot

340 lda#19:jsr &FFF4 350 lda#12:sta &FE00 360 ldaftllrsta &FE01 370 rts

380

390]NEXT

400 ENDPROC

410

420 DEF FNhad(X%,Y%) = &5800 + (X%*8) + (Y%MOD8) + (Y%DIV 8)*320 430

440 DEF FNlad(X%,Y%) = &3000 + (X%*8) + (Y%MOD8) + (Y%DIV 8)*320 450

460 DEF PROCmove 470 CALL top

480 FOR Y% = 0 TO 255 STEP 2 490 FOR X% = 0 TO 39 500 A% = ?FNhad(X%,Y%)

510 ?FNlad(X% , Y % DIV 2) = A%

520 NEXT X%,Y%

530 CALL bot

540 FOR Y% = 1 TO 255 STEP 2 550 FOR X% = 0 TO 39 560 A% = ?FNhad(X%,Y%)

85

THE BBC MICRO COMPENDIUM

570 ?FNhad(X%,Y% DIV 2) = A% 580 NEXT X%,Y%

590 ENDPROC

To cover the program line by line:

urconvPeUnt,tme,COmPUter “ M°DE °' AlthouSh the P~g*n doesn’t use MODE 0, it is convenient to use it to clear the top 20K of memory.

rtL“op°of Memory8 'ha' M°DE ° P"tS HIMEM at 12288 ‘ having sPa“ for 20K at

VDU drived dhectly ^ °E ^ W“h°Ut altering HIMEM- !t does this by accessing the

Line 100 calls the procedure which assembles the machine code used in the program. Lines 1 10 to 140 print some random characters on the screen.

Line 1 50 calls PROCmove, which moves the contents of the MODE 4 screen into the correct format for the new display.

Line 170 starts off the major REPEAT loop of the program.

Line 180 calls the routine BOT, which waits for a vertical sync pulse and then displays the bottom of the two display pages.

Line 190 does the same for the top page.

Line 200 terminates the loop.

Line 220 starts to define PROCassemble.

Line 230 defines some space for the machine code used by the program.

Line 270 starts the assembly ocode for the routine TOP.

Line 280 effects *FX 19.

Line 290 selects the 6845 register 12.

Line 300 places 6 into the register. This makes the address of the screen be 6*256*8, which is 12288. This corresponds tot he lower of the two screens.

Lines 340 to 360 are the same, except that they select the other page.

86

EVALUATING EXPRESSIONS

Line 420 defines the function HAD. This means ‘High Address’. It returns the address of a byte with coordinates X,Y on the higher screen.

Line 440 is the same except that it gives the address on the lower screen. It could have been defined as FNhad(X%,Y%)-&2800.

Line 460 starts the definition of PROCmove.

Line 470 calls the TOP routine to ensure that the lower of the two screens is displayed.

Line 480 loops through the spectrum of Y coordinates in steps of two. This makes it step through all the even Y coordinates.

Line 490 steps along the 40 bytes in each line.

Line 500 gets the byte stored at the coordinates in the upper screen.

Line 510 then deposits this byte in the lower screen. Notice that the Y coordinate is divided by two.

Line 520 terminates both loops.

Lines 530 to 580 act in the same way except that they move the odd coordinate bytes up the upper screen.

I should add that the program takes some time to run and once all the characters have been built up, two things can happen. The first is that you can get faced with a rather nasty flickering screen. If this happens you have to press ‘escape’ to get out of the program and type ‘REP. CALL bot:CALL top:U.FA.’. You may have to type this a few times before it works. It makes sense to program this sequence into a function key before you run the program, as this makes it easier to do the typing when the display is switched to the lower screen.

Alternatively, you could have a nice 512 vertical resolution screen with a slightly inordinate amount of flicker. The reason it doesn’t always work is that occasionally it tries to display the scan lines in the wrong positions. Thus, although this program is interesting for experimentation, it is not practical due to its inherent unpredictability.

87

The FROTH threaded language

The language I have chosen to compile in this section is a little like FORTH. FORTH is not quite as useful for general programming as BBC BASIC, but it is extraordinarily easy to compile. The version here is not quite similar enough to FORTH to be called FORTH, so I’ve taken the liberty of calling it FROTH.

The first thing to bear in mind about any language is that it is based upon a number of standard routines for carrying out tasks such as addition, multiplication, subtraction, division and so on. Before you write a language, it is a good idea to have decided upon the arithmetic routines you are going to use and to have coded these routines. Doing this helps to separate the tasks of writing the compiler, and allows you to spend time ensuring that the routines are as fast as possible.

The routines I would recommend are addition, subtraction, multiplication, division, the modulus operation, the indirection operators, greater than, less than, equal to, not equal to, greater than or equal to, less than or equal to and possibly the Boolean operators AND, OR, NOT and EOR.

Any serious language should have variables that are at least 16 bits wide, which allows it to have a numeric range of either 0 to 65535, or -32768 to 32767 (if two’s complement notation is used) which is sometimes more useful for general programming.

Once all the routines have been written, you can start work on the language.

FROTH is based around a stack of 16 bit numbers, like most FORTH implemen tations. You interact with FROTH by typing one or more words on the keyboard, terminated by pressing carriage return, and separated by spaces. A word can then be made up of any characters except spaces and carriage returns. For convenience, control characters cannot be used either.

The words you type in fall into two categories. If a word is made up of just digits (including a leading plus or minus sign), then the word is converted to a binary number and pushed onto the stack. If it is not a number, the computer searches through a list of known words, and executes any word which matches that typed in. If no match is found, the computer reports an error.

Some examples of these words are ’ + and ’PRINT’. ’ + ’ pulls two numbers off

the stack, adds them together and pushes the answer on the stack, ’*’ does the same for multiplication and ’PRINT’ simply pulls and prints the number on top of the stack.

88

THE FROTH THREADED LANGUAGE

This simple language description allows the creation of RPN expressions using the other arithmetic words, combined with other words which allow you to define more words, carry out loops and so on.

Here is the listing of FROTH. There are some examples of it in operation following the listing, which will give an idea of how the language works:

> LIST

10 REM FilenamerFROTH 20

30 REM Hybrid FORTH 40

70 MAXCO% = 3000:REM Code size 80 MAXST% = 50*2:REM Stack size 90 MAXDC% = 1000:REM Dictionary size 100

110 PROCinit

120 ON ERROR REPORT :PRINT " at line ";ERL:BUF$ = "":IF E RR = 17 THEN END ELSE GOTO 140 130 PROClibrary 140 REPEAT 150 PROCprocess 160 UNTIL FALSE 170

180 DEF PROCinit 190 LOCAL A%,B%,C%

200 DIM A% MAXCO%,B% MAXST%,C% MAXDC%

210 AC1% = &50:REM Accumulator 220 AC2% = &52:REM Accumulator 230 AC3% = &54:REM Accumulator 240 STS% = &56:REM Stack start 250 STE% = &58:REM Stack end 260 STP% = &5A:REM Stack pointer 270 !STS% = B%

280 !STE% = B% + MAXST%-1 290 !STP% = B%

300 CDS% = A%:REM Code start

310 CDE% = A% + MAXCO%-l:REM Code end

320 CDP% = A%:REM Code pointer

330 DCS% = C%:REM Dictionary start

340 DCE% = C% + MAXDC%-1:REM Dictionary end

350 DCP% = C%:REM Dictionary pointer

89

THE BBC MICRO COMPENDIUM

360 BUF$ = STRING$(255 "*")

370 ENDPROC 380

390 DEF PROCerror(A$)

400 $P% = CHR$(0) + CHR$(100) + A$ + CHR$(0)

410 P% = P% + LEN(A$) + 3

420 ENDPROC

430

440 DEF PROClibrary 450 LOCAL 0%,P%,A$,A%

460 FOR O% = 0 TO 2 STEP 2 470 P% = CDP%

480[OPT 0%

490

500.PUSH1%

510 LDA AC1%:LDY ^0:STA (STP%),Y:INY:LDA AC1% + 1:STA ( STP%),Y

520. aa LDA STP%:CLC:ADC #2:STA STP%:LDA STP% + 1:ADC $0:STA STP% + 1

530 CMP STE% + 1:BNE bb:LDA STP%:CMP STE%:BNE bb 540]:PROCerror("Stack overflow"):[OPT 0%

550.bb RTS 560

570.PUSH2%

580 LDA AC2%:LDY #0:STA (STP%),Y:INY:LDA AC2% + 1:STA (STP%),Y 590 JMP aa 600

610.PULL1%

620 LDA STP%:CMP STS%:BNE cc:LDA STP% + 1:CMP STS%

+ 1:BNE cc

630] :PROCerror( "Stack underflow"): [OPT 0%

640.cc LDA STP%:SEC:SBC #2:STA STP%:LDA STP% + 1:SBC #0:STA STP% + 1

650 LDY#0:LDA (STP%),Y:STA AC1%:INY:LDA (STP%),Y:STA AC1% + 1:RTS

660

670.PULL2%

680 LDA STP%:CMP STS%:BNE dd:LDA STP% + 1:CMP STS%

+ 1:BNE dd

690 ] * PROCerror( "Stack underflow"): [OPT 0%

700. dd LDA STP%:SEC:SBC #2:STA STP%:LDA STP% + 1:SBC ItO'STA STP% + 1

710 LDY#0:LDA <STP%),Y:STA AC2%:INY:LDA (STP%),Y:STA AC2% + 1:RTS

90

THE FROTH THREADED LANGUAGE

720

730.NTRUE%

740 LDA #&FF:STA AC1%:STA AC1% + 1:JMP PUSH1%

750

760.NFALSE%

770 LDA #0:STA AC1%:STA AC1% + 1:JMP PUSH1%

780

790.EQUAL%

800 JSR PULL1%:JSR PULL2%:LDA AC1%:CMP AC2%:BNE NFA LSE%:LDA AC1% + 1:CMP AC2% + 1:BNE NFALSE%:JMP NTRUE% 810

820.NEQUAL%

830 JSR PULL1%:JSR PULL2%:LDA AC1%:CMP AC2%:BNE NTR UE%:LDA AC1% + 1:CMP AC2% + 1:BNE NTRUE%:JMP NFALSE% 840

850.GREATER%

860 JSR COMP ARE% :BMI NTRUE%:JMP NFALSE%

870

880.LESS%

890 JSR COMPARE% :BMI NF ALSE% :BEQ NF ALSE% :JMP NTR UE%

900

910.LE _ EQ%

920 JSR COMP ARE% :BPL NF ALSE% :JMP NTRUE%

930

950 JSR COMP ARE% :BEQ NTRUE% :BMI NTRUE%:JMP NFALS E%

960

970. COMP ARE%

980 JSR PULL1%:JSR PULL2%

qqn r DA AC1%:CMP AC2%:BEQ DEQUAL%

1000 LDA AC1% + 1:SBC AC2% + l:ORA ftlOVS DOVFLOW%:RTS 1o!o.DEQUAL% LDA AC1% + 1:SBC AC2% + 1.BVS DOV

'l OMJK) VFLOVV0/.) EOR ft&80:ORA |fl:RTS 1030

!m0 JSDRDPULL1%:JSR PULL2%:LDA AC1%:CLC:ADC AC2%:STA lOOO^LDA AC1% + 1:ADC AC2% + 1=STA AC1% + 1:JMP PUSH1%

1070

1080.SUBTRACT% „ttttoo7 TnA

1090 JSR PULL1%:JSR PULL2%.LDA AC1%

AC2%:SEC:SBC AC1%:STA

91

THE BBC MICRO COMPENDIUM

1110 LDA AC2% + 1:SBC AC1% + 1:STA AC1% + 1:JMP PUSH1% 1120.OUT%

1130 JSR PULL1%:LDA AC1% + 1:BPL ee 1140 LDA ftASC"-":JSR &FFEE:LDA ^0:SEC:SBC AC1%:STA AC1%:LDA #0:SBC AC1% + 1:STA AC1% + 1 1150.ee LDY $0:.ff LDX $16:LDA #0:.gg ASL (ACl%):ROL (AC1% + l):ROL A:CMP #10:BCC hh:SBC #10:INC ACl%:.hh DEX 1160 BNE gg:PHA:INY:LD A AC1% + l:ORA AC1%:BNE PLA :CLC:ADC #&30:JSR &FFEE:DEY:BNE ii:RTS 1170

1180.MULT%

1190 JSR PULL1%:JSR PULL2%:LDA #0:STA AC3%:STA AC3% + 1 1200 LDX #16:.)) ASL (AC3%):ROL (AC3% + 1):ASL (AC2%):ROL (AC2% + 1):BCC kk:LDA AC1%:CLC:ADC AC3%:STA AC3%

1210 LDA AC1% + 1:ADC AC3% + 1:STA AC3% + l:.kk DEX:BNE jj:LDA AC3%:STA AC1%:LDA AC3% + 1:STA AC1% + 1:JMP PUSH 1%

1220

1230.NABS%

1240 JSR PULL1%:LDA AC1% + 1:BPL U:LDA^0:SEC:SBC AC1%:S TA AC1%:LDA #0:SBC AC1% + 1:STA AC1% + Is. 11 JMP PUSH1% 1250

1260.SDIVMD%

1270 JSR PULL1%:JSR PULL2%:LDA AC2%:STA AC3%:LDA AC2% + 1:STA AC3% + 1

1280 LDA AC3% + l:EOR AC1% + 1:STA &90:LDA AC3% + 1:STA &91

1290 LDA AC1% + 1:BPL CHKDE:LDA #0:SEC:SBC AC1%:STA AC1%:LDA #0:SBC AC1% + 1:STA AC1% + 1 1300.CHKDE LDA AC3% + 1:BPL DODIV:LDA ^0:SEC:SBC AC3%:STA AC3%:LDA #0:SBC AC3% + 1:STA AC3% + 1 1310.DODIV JSR UDIVrBCS EREXITrLDA &90:BPL DOREMiLDA #0:SEC:SBC AC3%:STA AC3%:LDA #0:SBC AC3% + 1:STA AC3% + 1

1320.DOREM LDA &91:BPL OKEXIT:LDA #0:SEC:SBC AC3% + 2:STA AC3% + 2:LDA #0:SBC AC3% + 3:STA AC3% + 3:JM P OKEXIT

1 330. EREXIT:]:PROCerror( "Division by zero"):[OPT 0%

1340. OKEXIT LDA AC3%:STA AC2%:LDA AC3% + 1:STA AC2% + 1:LDA AC3% + 2:STA AC1%:LDA AC3% + 3:STA AC1% + 1:RTS 1350

1360.UDIV LDA #0:STA AC3% + 2:STA AC3% + 3 1370 LDA ACl%:ORA AC1% + 1:BNE OKUDIV:SEC:RTS

92

THE FROTH THREADED LANGUAGE

1380.OKUDIV LDX #16:.DAVLP ROL (AC3%):ROL (AC3% + l):RO L (AC3% + 2):ROL (AC3% + 3)

1390.CHKLT SEC:LDA AC3% + 2:SBC AC1%:TAY:LDA AC3% + 3:S BC AC1 % + 1:BCC DECCNT :ST Y AC3% + 2:STA AC3% + 3 1400.DECCNT DEXrBNE DAVLPtROL (AC3%):ROL (AC3% + 1):CL C:RTS 1410

1420.NDIV%

1430 JSR SDIVMD%:JMP PUSH2%

1440

1450.NMOD%

1460 JSR SDIVMD%:JMP PUSH1%

1470

1480.DUP%

1490 JSR PULL1%:JSR PUSH1%:JMP PUSH1%

1500

1510.SWAP%

1520 JSR PULL1%:JSR PULL2%:JSR PUSH1%:JMP PUSH2%

1530

1540.NDIVMOD%

1550 JSR SDIVMD%:JSR PUSH1%:JMP PUSH2%

1560

1570.NMODDIV%

1580 JSR SDIVMD%:JSR PUSH2%:JMP PUSH1%

1590

1600.DISCARD%

1610 JMP PULL1%

1620

1630.NVDU%

1640 JSR PULL1 % :LD A AC1%:JMP &FFEE 1650

1660.NGET%

1670 JSR &FFE0:STA AC1%:LDA #0:STA AC1% + 1:JMP PUSH1% 1680

1690.NAND%

1700 JSR PULL1%:JSR PULL2%:LDA AC1%:AND AC2%:STA AC1%:LDA AC1% + 1:AND AC2% + 1:STA AC1% + 1:JMP PUSH1% 1710

1720.NOR%

1730 JSR PULL1%:JSR PULL2%:LDA ACl%:ORA AC2%:STA AC1%:LDA AC1% + l:ORA AC2% + 1:STA AC1% + 1:JMP PUSH1% 1740

1750.NEOR%

1760 JSR PULL1%:JSR PULL2%:LDA ACl%:EOR AC2%:STA AC1%:LDA AC1% + l:EOR AC2% + 1:STA AC1% + 1:JMP PUSH1%

93

THE BBC MICRO COMPENDIUM

1770

1780.NNOT%

1790 JSR PULL1%:LDA ACl%:EOR #255:STA AC1%:LDA AC1%

+ l:EOR #255:STA AC1% + 1:JMP PUSH1%

1800

1810 ACE%

1820 LDA ^32:JMP &FFEE

1830

1840

1850 LDA #32:JMP &FFEE 1860

1870. CR%

1880 JMP &FFE7 1890

1900 ACES%

1910 JSR PULL1%:.AA LDA ACl%:ORA AC1% + 1:BEQ BB:LDA jj= 32: JSR &F FEErLDA AC1%:SEC:SBC #1:STA AC1%:LDA AC1% + 1: SBC#0:STA AC1% + 1:JMP AA:.BB RTS 1920

1930.CHARS%

1940 JSR PULL1%:JSR PULL2%:.CC LDA ACl%:ORA AC1% + 1:B EO DD:LDA AC2%:JSR &FFEE:LDA AC1%:SEC:SBC #1:STA AC1%:LDA AC1% + 1:SBC^=0:STA AC1% + 1:JMP CC:.DD RTS

1950

1960.NPRINTON%

1970 LDA #2:JMP &FFEE 1980

1990.NPRINTOFF%

2000 LDA $3:JMP &FFEE

2010

2030 JSF^ PULL1%:LDA #128:LDX AC1%:LDY AC1% + 1:JSR &FFF 4:STY AC1% + 1:STX AC1%:JMP PUSH1%

2040

mo'S^LU^otLDA #129:LDX AC1%:LDY AC1% + 1:JSR &FFF 4flSTY AClVo + 1:STX AC1%:JMP PUSH1%

2070

2100

2120 JSR^PULL1%:FDA *138:LDX P=LDY AC1%:JMP &FFF4

94

THE FROTH THREADED LANGUAGE

2130

2140.TV%

2150 JSR PULL1%:JSR PULL2%:LDA #144:LDX AC2%:LDY

AC1%:JMP &FFF4

2160

2170.NTIME%

2180 LDA $1:LDX ^&50:LDY #0:JSR &FFF1 2190 JMP PUSH1%

2200

2210.SET _ TIME%

2220 JSR PULL1%

2230 LDA $2:LDX #&50:LDY #0:JMP &FFF1 2240

2250]NEXT 2260 CDP% = P%

2270 DATA + ,ADD%

2280 DATA -,SUBTRACT%

2290 DATA PRINT, OUT%

2300 DATA *,MULT%

2310 DATA ABS,NABS%

2320 DATA DIV,NDrV%

2330 DATA MOD,NMOD%

2340 DATA DUP,DUP%

2350 DATA SWAP,SWAP%

2360 DATA DIVMOD,NDIVMOD%

2370 DATA MODDIV,NMODDIV%

2380 DATA DISCARD, DISC ARD%

2390 DATA VDU,NVDU%

2400 DATA GET,NGET%

2410 DATA AND,NAND%

2420 DATA OR,NOR%

2430 DATA EOR,NEOR%

2440 DATA NOT,NNOT%

2450 DATA SPACE,SPACE%

2460 DATA SP,SP%

2470 DATA CR,CR%

2480 DATA SPACES,SPACES%

2490 DATA CHARS, CHARS%

2500 DATA PRINT_ON,NPRINTON%

2510 DATA PRINT _ OFF ,NPRINT OFF%

2520 DATA ADVAL,NADVAL%

2530 DATA INKEY,NINKEY%

2540 DATA READCH,NREADCH%

2550 DATA INSERT, INSERT%

2560 DATA TV,TV%

95

THE BBC MICRO COMPENDIUM

2570 DATA TRUE,NTRUE%

2580 DATA FALSE, NFALSE%

2590 DATA = ,EQUAL%

2600 DATA < > ,NEQUAL%

2610 DATA > , GREATER %

2620 DATA < ,LESS%

2630 DATA < = ,LE _ EQ%

2640 DATA > = ,GR _ EQ%

2650 DATA TIME,NTIME%

2660 DATA SET _ TIME, SET _ TIME%

2670 DATA *,0 2680 BUF$ = ""

2690 RESTORE 2270 2700 READ A$,A%

2710 IF A% = 0 THEN GOTO 2790 2720 $DCP% = A$

2730 DCP% = DCP% + LEN($DCP%) + 1 2740 ?DCP% = LEN(A$)

2750 DCP%!1 = A%

2760 DCP% = DCP% + 4 2770 GOTO 2700 2780

2790 TRE% = DCP%

2800 ENDPROC

2810

2820

2830

2840 DEF FNword 2850 LOCAL A$,A%

2860 IF LEN(BUF$) = 0 THEN INPUT LINE "]"BUF$:GOTO 2860 2870 IF LEFT$(BUF$,1) = " " THEN BUF$ = MID$(BUF$,2):GOTO 2860

2880 A$ = BUF$

2890 A% = INSTR(A$," ")

2900 IF A% = 0 THEN BUF$ = "": = A$

2910 BUF$ = MID$(BUF$,A% + 1)

2920 = LEFT$(A$,A%-1)

2930

2940

2950

2960 DEF PROCprocess 2970 LOCAL P%

2980 A$ = FNword:IF LEN(A$) = 0 THEN GOTO 2980 2990 IF FNnum(A$) THEN PROCpush(VAL(A$)):GOTO 2980 3000 P% = FNdick(A$)

96

THE FROTH THREADED LANGUAGE

3010 IF P% = 0 THEN PROCcommand(A$):ENDPROC 3020 CALL !(P% + LEN($P%) + 2)

3030 ENDPROC 3040

3050 DEF FNdick(A$)

3060 LOCAL P%

3070 P% = DCS%

3080 IF $P% = A$ THEN = P%

3090 P% = P% + LEN($P%) + 5 3100 IF P%> = DCP% THEN = 0 3110 GOTO 3080 3120

3130 DEF FNnum(A$)

3140 = STR$(VAL(A$)) = A$

3150

3160 DEF PROCpush(A%)

3170 IF SGN(A%) = -1 THEN A% = 65536 + A%

3180 !AC1% = A%:CALL PUSH1%

3190 ENDPROC 3200

3210 DEF PROCcommand(A$)

3220 IF A$ = "VOCAB" THEN PROCVOCAB:ENDPROC 3230 IF A$ = "BASIC" THEN CLEAR:END 3240 IF A$ = ":" THEN PROCcompile:ENDPROC 3250 PRINT "No such word as ";A$

3260 BUF$ = ""

3270 ENDPROC 3280

3290 DEF PROCVOCAB 3300 LOCAL T%

3310 PRINT "Resident words:"

3320 T% = DCS%

3330 PRINT $T%;"

3340 T% = T% + LEN($T%) + 5

3350 IF T% = TRE% THEN PRINT ’"User defined words:" 3360 IF T%> =DCP% THEN PRINT : ENDPROC 3370 GOTO 3330 3380

3390 DEF PROCcompile 3400 LOCAL A$,P%,A$,T%

3410 IF DCP%> =DCE% THEN PRINT ’"No dictionary space":BUF$ = "":ENDPROC 3420 A$ = FNword

3430 IF FNdick(A$)> 0 THEN PRINT ’"Word already exists":BUF$ = "":ENDPROC

97

THE BBC MICRO COMPENDIUM

3440 $DCP% = A$

3450 DCP% = DCP% + LEN(A$) + 1 3460 ?DCP% = LEN(A$)

3470 DCP%!1 = CDP%

3480 DCP% = DCP% + 4 3490 P% = CDP%

3500 A$ = FNword

3510 IF FNnum(A$) THEN PROCnumber(VAL(A$)):GOTO 3500 3520 IF A$ = ";" THEN [OPT 2:RTS:]:CDP% = P%:ENDPROC 3530 T% = FNdick(A$)

3540 IF T% = 0 THEN PROCimmed(A$):GOTO 3500 3550[OPT 2:JSR !(T% + LEN($T%) + 2):]

3560 IF P%> CDE% THEN PRINT ’"Code too long":BUF$="":ENDPROC 3570 GOTO 3500 3580

3590 DEF PROCnumber(A%)

3600 IF SGN(A%) = -1 THEN A% = A% + 65536

3610[OPT 2:LDA #(A% MOD 256):STA AC1%:LDA #(A% DIV 256): STA AC1% + 1:JSR PUSH1%:]

3620 ENDPROC 3630

3640 DEF PROCimmed(A$)

3650 IF A$ = "BEGIN" THEN PROCbegimENDPROC 3660 IF A$ = "END" THEN PROCend: ENDPROC 3670 PRINT ’"No such word as ";A$:BUF$ = "":ENDPROC 3680

3690 DEF PROCbegin 3700 !AC1% = P%

3710 CALL PUSH1%

3720 ENDPROC 3730

3740 DEF PROCend 3750 CALL PULL1%

3770lJSPR PULL1%:LDA ACl%:ORA AC1% + 1:BNE P% + 5 3780 JMP !AC1%

37901ENDPROC

> RUN

jVOCAB Resident words:

_ t./MA TAT m cw&p niVMOD MODDIV DIS

+ - PRINT * ABS ' ’CARD VDU GET

ARS PRINT _ ON

TV TRUE FALSE

98

THE FROTH THREADED LANGUAGE

User defined words:

]2 2 + PRINT CR 4

]2 2 * PRINT CR 4

]5 4 + 4 * PRINT CR 36

3100 32 DIV PRINT CR 3

]42 43 44 45 46 47 48 49 VDU VDU VDU VDU VDU VDU VDU VDU

10/.-, + *]

]GET VDU GET VDU GET VDU GET VDU CR

JR.

3GET GET GET GET VDU VDU VDU VDU CR

R.J

]45 SPACES 42 VDU CR

★

342 43 CHARS

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★•A:*********]

]42 INSERT 2 2 3*

3 PRINT CR

4

3

Escape at line 2860

>

Before looking at the listing, it makes sense to examine the sample run following the listing.

On typing RUN, FROTH takes a few seconds to initialise, before presenting you with its prompt. In MODE 7 this appears as an arrow. You will not normally have space to run FROTH in other MODEs - it has no graphics statements anyway, so there probably wouldn’t be very much point.

The first word I typed was VOCAB. This is like the FORTH word VLIST - it gives a list of all the words that FROTH responds to. There are some exceptions. VOCAB, BEGIN and END are dealt with in an odd way, so they do not appear in the list.

Unlike FORTH the oldest words appear first. The words are broken into two types - those provided as standard by the system and those added by the user. At start up there are no user defined words, so this section is empty.

99

THE BBC MICRO COMPENDIUM

The next entry, ‘2 2 + PRINT CR’, is a simple example of FROTH’s amazing mathematical capability, showing that FROTH works in RPN. The word PRINT simply pops and prints the top stack item, whilst CR moves the cursor to a new line, since PRINT does not automatically do this at the end of its run. Thus, the above FROTH entry is similar to the BASIC statement:

PRINT 2 + 2

The next entry is again similar, except it shows multiplication.

The next entry shows some rather more complex RPN arithmetic - can you work out the algebraic expression that corresponds to the RPN expression featured ?

After a quick division demonstration, the next line shows how the VDU word works. It pops the top item from the stack and sends it direct to the VDU driver.

The point to bear in mind is that this line is equivalent to:

VDU 49,48,47,46,45,44,43,42

and NOT to:

VDU 42,43,44,45,46,47,48,49

This is due to FROTH’s use of the stack. The next two lines show the same effect. In each case, I typed the letters ‘J.R.’ after pressing RETURN. In the second example, the letters were transposed due to the action of the stack.

The next two lines show the SPACES and CHARS words. The SPACES word pops a number off the stack, and prints that number of spaces.

CHARS prints X copies of character Y, where X is on top of the stack and Y is under X on the stack.

The final example shows the use of the word INSERT to insert characters into the keyboard buffer.

Notice that the words provided in FROTH are an odd mix. I tried to include one word illustrating each of a number of possible word sources - thus there are the TIME and

SET _ TIME words to show how OS WORD can be called from FROTH, and the

INSERT word to show how OSBYTE can be called.

If the words supplied are unsuitable, the following description will enable you to define your own, more suitable, ones.

Line 70 defines the maximum size of the code area. The code area is used to store the machine code that comprises each word. 3000 is probably a little too generous for mos applications.

100

THE FROTH THREADED LANGUAGE

Line 80 defines the maximum number of entries for the stack. Because the stack is used to store two byte quantities, a stack size of 100 bytes will only allow 50 numbers to be stacked.

Line 90 defines the size of the dictionary. The dictionary is used to store the names and addresses of all the words in the systems. 1000 will allow space for about 100 words.

Line 1 10 calls PROCinit which simply defines some of the locations used by FROTH.

Line 120 defines the error handling routine. The routine gives the required error message, but only leaves the system if the error was generated by pressing ‘escape . This means that some of the new error messages generated by FROTH (such as ‘Stack overflow’) will not cause a return to BASIC - which would lose all the user defined words.

Line 130 calls PROClibrary which installs the built in FROTH words.

Line 140 starts the main REPEAT loop of the program.

Line 150 calls PROCprocess, which simply acts upon a single word.

Line 160 terminates this loop by allowing it to continue ad infinitum.

Line 180 starts the definition of PROCinit.

Line 200 reserves space for the code area, the stack and the dictionary.

Line 210 defines the location of the FROTH primary accumulator. These two loca tions are used for storing numbers during calculations.

Lines 220 and 230 define the secondary and tertiary accumulators.

Line 240 defines the location where the start of the stack is stored. This has to be stored in a page zero location so that the machine code parts of FROTH can detect stack underflow - an attempt to pull a number off an empty stack.

Lines 250 and 260 define the locations for the stack end address and the stack pointer in a similar way to the stack start address.

Lines 270 to 290 set these locations to their default values. Notice that the stack used in FROTH grows upwards - hence the stack pointer is initialised to the start address of the stack Normal FORTH systems have stacks that grow downwards.

101

THE BBC MICRO COMPENDIUM

Line 300 sets the default value for CDS% which contains the start of the code area.

Line 310 sets CDE%, which contains the final location of the code area.

Line 320 defines CDP%, which contains the lowest unused location in the code area.

Lines 330 to 350 behave in a similar manner, except that they define the extent of the dictionary area.

Line 360 assigns a whole lot of asterisks to BUF$. BUF$ is used to hold the words typed in by the user. It is filled up with asterisks to counteract the odd way in which BBC BASIC assigns string space. Finally, the string is returned to zero length.

Line 370 terminates PROCinit.

Lines 390 to 420 define PROCerror. This procedure is used to insert error messages into assembled code.

Line 440 starts the definition of PROClibrary.

Line 500 starts the code for the push operation. The value held in the primary accumu lator is pushed onto the stack.

Line 510 first loads the 6502’s accumulator with the low order byte of the number to be pushed, then uses indirect addressing to place this in the stack area. The index register is then incremented before the upper byte is stored.

Line 520 adds two to the current stack pointer value.

Line 530 checks to see if the stack has overflowed over the top of the stack. F.or this code to operate correctly, the stack must be an even number of bytes long.

Line 540 gives an error if overflow did occur.

Line 550 returns control to the calling routine.

Line 570 starts the definition of the other push routine - this one pushes the contents of the secondary accumulator.

Line 580 stores the accumulator on the stack.

Line 590 passes control back to the other push routine to increment the stack pointer and check for overflow.

Line 610 defines the first pull routine. It pulls the word at the top of the stack to the primary accumulator.

102

THE FROTH THREADED LANGUAGE

Line 620 checks to see if the stack pointer points to the bottom of the stack. If it does, there is no number on the stack to be pulled.

Line 630 gives an error message if underflow does occur.

Line 640 then decrements the stack pointer by two.

Line 650 gets the top value from the stack, placing it in the primary accumulator.

Lines 670 to 7 10 are identical to lines 6 10 to 650, except that they pull the value to the secondary accumulator.

Lines 730 and 740 define the word ‘TRUE’. Notice that the label used is prefixed with an ‘N’ to prevent BASIC tokenising the label. The word TRUE simply places the Boolean value TRUE (or &FFFF) onto the stack. This is achieved by loading the primary accumulator with &FFFF, then pushing it to the stack.

Lines 760 and 770 are similar except that they define the word FALSE, which places the number zero onto the stack.

Lines 790 and 800 define the word EQUAL or ‘ = ’, which pulls two numbers off the stack, checking whether they are equal. If they are, TRUE is placed on the stack, otherwise FALSE is pushed. This is achieved by pulling the top two values to the primary and secondary accumulators, then comparing the two accumulators byte by byte.

Lines 820 and 830 do the same except that they define the word NEQUAL or £< > ’, which checks to see if the top two values on the stack are not equal, pushing TRUE if they differ and FALSE if they do not.

Lines 850 and 860 define the word GREATER or > They do this by calling the COMPARE subroutine, which will pull the top two values and bring CMP to bear on them. Depending on the state of the flags when control returns from COMPARE, this routine either branches to NTRUE or NFALSE.

Lines 880 to 890 do the same for LESS or

Lines 910 and 920 do the same for LE — EQ (less than or equal to), which appears in the vocabulary as ‘< = ’•

Lines 940 and 950 do the same for greater then or equal to or

Lines 970 to 1020 comprise the subroutine COMPARE. This subroutine pulls the top two subroutine values and compares them.

103

THE BBC MICRO COMPENDIUM

Line 1040 starts to define the word ADD, which appears in the vocabulary as ‘ + ’.

Line 1050 pulls the top two values off the stack, then adds their least significant bytes in the normal way. J

Line 1060 adds the more significant bytes of the accumulators. Finally, the answer is pushed onto the stack.

Line 1080 starts the definition of the word SUBTRACT or

Line 1090 pulls the to two values from the stack, and then subtracts the less significant bytes of the accumulators.

Line 1100 subtracts the more significant bytes before pushing the answer onto the stack.

Notice that neither the addition nor the subtraction routine bother to check for over flow or underflow of the answer.

Line 1120 starts the definition of the word ‘PRINT’. It is labelled OUT to prevent a conflict with the BASIC tokenisation process.

Line 1130 first pulls the value to be printed from the stack into the primary accumula tor. It then checks to see if the most significant byte has its top bit set - i.e. whether the number is negative. If it is not, control is passed to the label ee.

Line 1140 first prints the leading minus sign needed for negative values. The value is then negated to make it positive.

Line 1 1 50 starts with the label ‘ee’, which is where the code for a positive number rejoins that for negative numbers. The rest of the code divides the number and prints it in the normal way.

Lines 1 180 to 1 2 1 0 carries out the multiplication word - again, using the standard shift and add algorithm.

104

THE FROTH THREADED LANGUAGE

Lines 1230 to 1240 take the absolute value of the number at the top of the stack.

Cai>r^ °Ut ^v^i°n using the standard shift and trial subtraction method. The division algorithm can be expressed as follows:

1 . Check for division by zero

2. Zero accumulator

3. Adjust signs

4. For loop= 16 to 1

5. Shift dividend left into accumulator

6. Subtract divisor from accumulator

7. Increment dividend

8. Goto step 1 1 if the subtraction didn’t generate a carry (in 6502 terms this is a BCS instruction)

9. Add divisor to accumulator

10. Decrement dividend

1 1 . Next loop

12. Remainder is in accumulator

13. Quotient is in dividend

Lines 1420 and 1430 call the division routine to make the word DIV.

Lines 1450 and 1460 call the same routine to make the word MOD.

Lines 1480 and 1490 comprise the word DUP which makes an additional copy of the number on top of the stack.

Lines 1510 and 1 520 comprise the word SWAP, which swaps the top two items on the stack.

Lines 1 540 and 1550 comprise the word DIVMOD, which carries out a division in the normal way, then places the quotient followed by the remainder on the stack. This is useful if you wish to access both but don’t want to call the routine twice for reasons of speed.

Lines 1570 and 1580 are the same, except the remainder is placed on the stack before the quotient.

Lines 1600 and 1610 comprise the word DISCARD which throws away the number on the top of the stack.

Lines 1630 and 1640 comprise the word VDU which passes the byte at the top of the stack to the VDU driver.

Lines 1660 and 1670 comprise the word GET, which places the ASCII value of a keypress on the stack.

Lines 1690 and 1700 comprise the word AND which pulls the top two items off the stack, ANDs them, and then pushes the answer on the stack.

105

THE BBC MICRO COMPENDIUM

Lines 1720 and 1730 carry out the same processes for the word OR.

Lines 1750 and 1760 carry out the word EOR.

Lines 1780 and 1790 carry out the word NOT, which logically inverts the value at the top of the stack.

Lines 1810 and 1820 comprise the word SPACE, which prints a space on the screen.

Lines 1870 and 1880 comprise the word CR which simply moves the cursor to a new line.

Lines 1900 and 1910 comprise the word SPACES, not to be confused with SPACE, which pulls a number off the top of the stack and prints that number of spaces.

Lines 1930 and 1940 are development of SPACES, called CHARS, which print out multiple repetitions of any character.

Lines 1960 and 1970 comprise PRINT _ ON, which turns the printer on using VDU

2.

Lines 1990 and 2000 comprise PRINT _ OFF, which turn it off again.

Lines 2020 and 2030 make up the word ADVAL. They pull the channel to be investi¬ gated from the stack, leaving the value found on the stack.

Lines 2050 and 2060 make up the word INKEY in an almost identical manner.

Lines 2080 to 2090 make up the word READCH which pulls a pair of coordinates off the stack, and return the character found at their position.

Lines 21 10 to 2120 comprise the word INSERT. This word takes the top value off the stack and inserts it into the keyboard buffer, using *FX 138.

Lines 2140 and 2 1 50 make up the word TV which acts exactly like a reversed version of *TV. The only difference is that both parameters must be supplied.

Lines 2170 to 2190 use an OSWORD call to read the current time, and then push this value onto the stack, making up the word TIME.

Lines 2 1 10 to 2230 comprise the word SET _ TIME, which sets the clock to the value

from the top of the stack.

Line 2260 updates the code pointer by setting it to the address reached so far.

Lines 2270 to 2660 are made up of all the names of the built in words followed by the labels used as aliases. This information is used to build up the dictionary.

106

THE FROTH THREADED LANGUAGE

Line 2670 marks the end of the data.

Line 2690 restores the data pointer to the start of this table.

Line 2700 reads the first data pair, which is made up of the label followed by its address.

Line 2710 jumps out of this section if the end of the data is encountered.

Line 2720 places the name of the routine in the current dictionary location.

Line 2730 increments the dictionary pointer past the name of the word. Notice that one is added to it to allow for the carriage return following each word.

Line 2740 inserts the length of the word’s name at the next dictionary location.

Line 2750 inserts the address of the word at the next two free addresses.

Line 2760 increments the dictionary pointer past the new data.

Line 2770 returns to get a new word.

Line 2790 is where the routine passes control to when it reaches the end of the data list of words. The current dictionary address is used to set the last address used for resident words into the variable ‘TRE%’.

Line 2800 exits the routine.

Line 2840 starts the definition of FNword. This function returns a word from the user. It will return the left most word from BUF$, but if BUF$ is empty, it will invite the user to enter more words (into BUF$) before trying again.

Line 2860 checks to see if BUF$ is empty, and if it is, gets another line of input from the user. Notice the use of INPUT LINE to allow the typing of commas.

Line 2870 strips off any spaces from the left of BUF$. It checks at this point for BUF$ being made up of just spaces.

Line 2880 copies BUF$ into A$ to prevent a conflict between the value returned and that retained in BUF$.

Line 2890 looks for the first space in A$. The letters between the start of A$ and this space will comprise the first word from A$.

Line 2900 checks too see if no space was present. If none was, BUF$ is set to the null string to ensure that an input will be requested next time around, but the routine returns with an unmodified copy of A$, since this will be the word in question.

107

THE BBC MICRO COMPENDIUM

Line 2910 removes the first word from BUF$.

Line 2920 exits the routine with the first word from A$.

Line 2960 Starts PROCprocess which is the main procedure of FROTH.

Line 2980 gets a word from the user.

Line 2990 checks to see if the word is a number. If it is, the number is pushed onto the stack and a new word is accepted.

Line 3000 uses FNdick to get the address in the dictionary of the word typed.

Line 3010 checks to see if the word appeared in the dictionary. If it did not, FROTH goes off to try and interpret it as an immediate command, like VOCAB.

Line 3020 calls the routine if it was found. It does this by finding the start address of the word from the dictionary and then using the CALL command to execute it.

Line 3030 exits the routine.

Line 3050 starts the definition of FNdick - which returns the dictionary address of a given word.

Line 3070 copies the start address of the dictionary to the pointer used in the search.

Line 3080 checks to see if the word defined at the current pointer address is the word being searched for, and if it is, returns with the address pointed to.

Line 3090 increments the pointer onto the next word in the dictionary.

Line 3100 checks to see if the end of the dictionary has been reached - if it has, zero is returned.

Line 3110 then goes back to look again for the word at the new dictionary location.

Line 3130 starts the define FNnum which checks whether its argument is a valid number.

Line 3140 carries out the check by seeing if the string representation of the number represented as a number is the same as the first string representing the number.

Line 3160 starts to define PROCpush which pushes the value of its argument onto the stack.

Line 3 1 70 checks to see if the number is negative - if it is, 65536 is added to it, to bring it into two’s complement noation.

108

THE FROTH THREADED LANGUAGE

Line 3180 inserts the number into the primary accumulator before calling the PUSH routine to place it onto the stack.

Line 3190 exits the routine.

Line 3210 starts to define PROCcommand, which checks to see if the word typed in was a direct command.

Line 3220 compares the word with VOCAB. If there is a match, PROCvocab is called and the routine exits.

Line 3230 checks for BASIC, which simply clears all variables and passes control to BASIC.

Line 3240 calls PROCcompile if the word was a colon. The colon is used to define your own words.

Line 3250 gives an error message if no match was found.

Line 3260 clears the buffer, so that the system stops after finding the error.

Line 3270 exits the routine.

Line 3290 starts to define PROCvocab, which simply prints out the names of all the words in the system.

Line 3310 prints the heading for the first part of the vocabulary.

Line 3320 sets a pointer to the start of the dictionary.

Line 3330 prints the word pointed to, followed by a space.

Line 3340 then increments the pointer onto the next word.

Line 3350 checks to see if the end of the system words has been reached. If it has, the system prints another message.

Line 3360 terminates the routine if the end of the vocabulary has been reached.

Line 3370 goes back to search again.

t- a n^prcorcomDile, which allows you to define your own words.

Line 3410 ensures that the dictionary is not full. This step is not strictly needed, but it does help to give instant feedback.

109

THE BBC MICRO COMPENDIUM

Line 3420 gets the next word (following the colon). This word will be the name of the word under definition.

Line 3430 looks for the word in the dictionary. If it exists already, the user is informed, and the attempt to redefine the word is halted.

Line 3440 inserts the name of the word in the dictionary.

Line 3450 increments the dictionary pointer past the name of the word.

Line 3460 places the length of the word into the dictionary space. This information is added to allow backwards searches thorough the dictionary (not presently imple¬ mented), which would allow you to redefine words.

Line 3470 inserts the address of the routine into the dictionary space. The address will obviously be the current location in the code area.

Line 3480 increments the dictionary pointer past this new information.

Line 3490 copies the current code location into the pointer P%.

Line 3500 gets the next word. This word will be the first one to actually feature in the definition of the word currently being defined.

Line 3510 checks to see if the word is a number. If it is, PROCnumber is called to assemble the relevant code, and control is passed back to get a new word.

Line 3520 checks to see if a semicolon was entered. If it was, the compilation is ended, so a return is added to the code area. Finally, the code pointer is updated and the routine exits.

Line 3530 searches for the word in the dictionary.

Line 3540 calls PROCimmed to compile so-called immediate key words if the word typed did not appear in the dictionary.

110

i

THE FROTH THREADED LANGUAGE

Line 3550 assembles code to execute the word.

Line 3560 checks to see if too much code has been defined.

Line 3570 passes control back to the main routine.

Line 3590 assembles code for a number appearing in a word being compiled.

Line 3600 turns the number into proper two’s complement if it is negative.

Line 3610 assembles the relevant code.

Line 3620 exits the routine.

Line 3640 checks for an immediate keyword. This is similar to the piece of code that checked for BASIC and VOCAB in interpretive mode.

Line 3650 checks for the word BEGIN.

Line 3660 checks for the word END.

Line 3670 gives an error message if the word is still unaccounted for.

Line 3690 starts the code to deal with the word BEGIN appearing in the word defi¬ nition in progress.

Line 3700 loads the primary accumulator with the current address in the code area. Line 3710 pushes this value onto the stack.

Line 3720 exits the routine.

Line 3740 defines the code for the word END.

Line 3750 pulls the address that BEGIN pushed.

Line 3770 assembles code to pull the value off the top of the stack, and if it is zero, jump back to the address where BEGIN occured.

Line 3790 exits the routine.

Here are some examples of defining your own words:

> RUN ] VOCAB Resident words:

111

THE BBC MICRO COMPENDIUM

+ - PRINT * ABS DIV MOD DUP SWAP DIVMOD MODDTV m«r ARD VDU GET AND OR EOR NOT SPACE SPCR SPACES S

TRUEpkfsF PR'NT^°FF ADVAL 'NKEY READCH INSERT Tv”

TRUE FALSE <