DATE.......: 2000-07-17
LESSON.....: 001
TITLE......: efficient multiplication in assembler
AUTHOR.....: Stephan Schmidt / Matthias L. Jugel (vmu@mud.de)

= COMMENTS =============================================================

	I did not start with the explanation of the skeletion or how
	to set up a development environment because there are others who
	have a lot more experience than I do. I would like to encourage
	you to write lessons about those topics and I will be happy to
	collect all these lessons and put them together on our web page
	for later readers.

	Davis Glaude very made a list of interesting open topics I would
	like to repeat here. These are open topics:

	1) The Skeleton
	2) Writing to the LCD
	3) About font and text
	4) Playing with the keyboard
	5) Using the timer
	6) Making sound
	7) Accessing the flash
	8) Communicating

	and I would like to add simple assembler skills to this list. 
	Please add if you feel there is something we should write about
	and I will put it on the list of open topics.

= SCOPE ================================================================

	This lesson will give you a short overview on how to make time
	consuming multiplications more efficient. It explains how powers
	of two are used for multiplication and the impact on cpu cycles.

========================================================================

When programming a small scale cpu like the one found in Visual Memory
Units your are forced to write small efficient programs. In contrast to
large processors common in todays personal computers you have limited
speed and memory at your disposal. For those who have programmed in
assembler before it is not new that some operations (like multiplication)
need more cpu-cylces than other "simple" operations (like addition). Due
to that fact you will find strange looking code in most of the programs.

Let's begin with a look at some of the operations found in the cpu of the
VMU (which is a customized Sanyo microcontroller of the LC86000 family):

	Operation | CPU cycles | Comments
	================================================================ 
	ADD       |    1       | add operand to the ACC register
	SUB       |    1       | subtract operand from the ACC register
	MUL       |    7       | perform multiplication (ACC..C * B)
	DIV       |    7       | perform division (ACC..C / B)

As you can see there is quite a difference in the amount of time needed to
execute an addition or perform a multiplication. It should let you think
about performing simple multiplications by 2 or other small numbers. It
would be much more efficient to perform these operations using just ADD
operations.

We will assume the simple example that the contents of the ACC register 
needs to be multiplied by eight. In a first attempt, using normal day-to
day logic we would write code like this:

	MOV #8,B	; move an eight into the register B
	MUL		; multiply the ACC with the contents of register B
	LD B		; load the result (8 bit) into ACC (it may be C?)

The MOV and LD operation takes one cycle each and the MUL operation takes 
seven. That sums up to nine cou cycles which is a long time compared to the
next bit of code below, that does the same:

	ADD ACC		; add ACC to ACC	=> original ACC * 2
	ADD ACC		; same again 		=> original ACC * 4
	ADD ACC		: and again		=> original ACC * 8

So we have multiplied ACC with eight and it sums up to 3 cpu cycles. That
was quick! But there is another benefit: we even saved two registers (B, C)
that were used by the MUL operation in out previous example.

Now you are a smart person and you comment: we can now multiply easily by
2, 4, 8, 16, 32 ... (powers of 2) but what about those multipliers inbetween?
That can be done easily. It will use up one of our precious registers:

Let's multiply first by five  and then by seven:

	ST B		; save ACC contents in register B
	ADD ACC		; multiply by two
	ADD ACC		; make it four
	ADD B		; add register B to make it 5

Summing up: four cpu cycles used

	ST B		; save ACC contents in register B
	ADD ACC		; multiply by 8 as explained above
	ADD ACC
	ADD ACC
	SUB B		; now subtract once and we have multiplied by 7

Of course another register may be used instead of B but always remember
that the ACC register is special and most algebraic operations are 
performed on the ACC register.

There are other ways to optimize calculations but this will be part of
anothe lesson.

= HOME WORK ============================================================

This is more an overview lesson and this there is nothing much you can
do except try to understand what has been explained and try it yourself.

Write down multiplications for other multipliers and compare them to
the "logical" implementation. Find the multiplier that makes no 
difference whether you use the ADD ACC or MUL operation.

Learn about the ROLC and RORC operations and their uses for
multiplication (hint rotating one bit left multiplies by 2).

========================================================================

Please send corrections or errors to the author mentioned in the header
of this lesson so that the lesson can be corrected in the archive.