H O M E - APOLLO181 INTRODUCTION First Program Example Binary Clock Algorithm Shift-and-Add Multiplication Prime Numbers Benchmark PWM LED Dimmer Step Motor Controller Sound Generator: Part 1 Sound Generator: Part 2 Random Number Generator EPROM Data Storage My Previous Z80 Project

Bitwise and Bit Shift Operations implemented with a single 74181

 APOLLO181 Side View

In low level programming the ability to manipulate or move bits by executing logic instructions is extremely useful or even necessary.

Bitwise operators are used to change individual bits in an operand, while bit shift operators are used to move all the bits of the operand. Here below are described situations where bitwise and bit shift operators can be helpful.

The NOT instruction is used to flip every bit (each 0 becomes 1, 1 becomes 0) and performs the one's complement operation on the destination.

A = 0101

Example: NOT A = 1010

The AND instruction can be used to clear specific destination bits while leaving the other bits unchanged or mask out unwanted bits or to check if the value of certain bits are "0".

A = 0101

A AND 1110 = 0100 (clear the least significant bit (LSB))

A AND 0011 = 0001 (ignore or "mask" the two most significant bits (MSB))

A AND 1000 = 0000 (check if the MSB is "0")

In the 74181 chip, the carry output Cn+4 (pin 16) is set when any arithmetic function containing a subtraction requires a borrow into the the most significant bit (i.e. the result is less than zero, treating the operands as unsigned), otherwise it is cleared. In APOLLO181 we can check if the value of certain bits are "0" simply by testing the Carry flag soon after having executed the “A AND B minus 1” instruction.  To perform “A AND B minus 1” in the 74181, initial Carry must be set to “No Carry”. Only if all the tested bits are zero, the result of the logic AND is 0000, the “A AND B minus 1” instruction generates a “borrow” and the Cn+4 output goes high (i.e. “No Carry” status in APOLLO181 if the tested bits are "0").

The OR instruction can be used to set specific destination bits while preserving the other bits or can be used to check if the value of certain bits are "1".

A = 0101

A OR 1000 = 1101 (set the MSB)

A OR 1110 = 1111 (check if the LSB is "1")

Method One. In the 74181 chip, the carry output Cn+4 (pin 16) is cleared when any arithmetic function containing an addition generates a carry out of the most significant bit (i.e. the sum does not fit in the 4-bit output, treating the operands as unsigned), otherwise it is set. In APOLLO181 we can check if the value of certain bits are "1" simply by testing the Carry flag soon after having executed the “A OR B plus 1” instruction.  To perform “A OR B plus 1” in the 74181, initial Carry must be set to “With Carry”. Only if all the tested bits are one, the result of the logic OR is 1111, the “A OR B plus 1” instruction generates a carry and the Cn+4 output goes low (i.e. “With Carry” status in APOLLO181  if the tested bits are "1").

Method Two (working with the 74181 but not implemented in APOLLO181 since flags are not latched after logical operations). In the 74181 chip, the A=B output (pin 14) is set when the result of any arithmetic or logic function is "all-ones" (i.e all the bits of the 4-bit output are "1"), otherwise it is cleared. In the 74181 we can check if the value of certain bits are "1" simply by testing the Zero flag soon after having executed the OR instruction. Only if all the tested bits are one, the result of the OR operation gives "1111" and the A=B output goes high.

The XOR instruction can be used to complement specific destination bits (for example to change the sign) or to clear a word or for encryption/decryption purpose or to exchange the contents of two locations A and B.

A = 0101

A XOR 1000 = 1101 (change the MSB)

A XOR A = 0000 (clear itself)

A XOR B XOR B = A = 0101 (encryption/decryption)

A XOR B XOR A = B (exchange A with B)

Shift and Rotate instructions shift the bits in the destination operand by one or more positions either to the left or right. The difference between Rotate and Shift is that Rotate cycles the bits around, moving the bits it shifts out at one end, back in at the other end, while Shift loses the bits that are moved out and fills the empty bits with zeros. Shifting and rotation instructions are anyway one of the most useful set in any processor's instruction set.

The SHIFT LEFT instruction can be used to multiply an unsigned operand by powers of 2 or to move a low nibble into a high nibble of a large 8 bit register.

A = 0000 0101 = 5d

SHL A = 0000 1010 = 5d * 2 = 10d (multiply by 2)

SHL A SHL A SHL A SHL A= 0101 0000 (move a low nibble into a high nibble )

The SHIFT RIGHT instruction can be used to divide an unsigned operand by powers of 2. The remainder will be found in the carry flag after a shift-right operation. It can be also used to move a high nibble into a low nibble of a large 8 bit register.

A = 0101

SHR A = 0010 = 5d / 2 = 2d

Using shift instructions it is possible to perform fast binary multiplication in an efficient way by implementing the following simple algorithm:

1) Shift the multiplier to the right

2) If Carry = 1 add the multiplicand to the result

3) Shift the multiplicand to the left

4) Repeat the algorithm

The ROTATE instructions are useful to test a value bit-by-bit in a way that is non-destructive. Rotate can be used in hashing and cryptography, graphics, image processing and communications.

Ex: ROT A ROT A ROT A ROT A = A (encryption/decryption)

The 74181 ALU  device is capable of adding, subtracting, left shifting, comparing and performing all logic operations but it cannot shift right and there is no direct rotate support. Thus, I have identified simple algorithms to perform the missing operations: I have optimized them to reduce the required number of clock cycles, but there might be more efficient algorithms.

In APOLLO181 Left Shifting (SHL) is performed by adding operand to itself (A+A), soon after having cleared the Carry flag: the bits are shifted to the left, zero is filled in on the LSB (bit 0).

The Rotate Through Carry Left (RCL) is easily performed by adding operand to itself with Carry (A+A+Carry), which is a standard function of the 74181 ALU chip: the carry flag will be copied into the LSB (bit 0) then the MSB (bit 4) will be copied into the carry flag.

The Rotate Left (ROL) is done performing first a Left Shifting (SHL) as described, and then adding the Carry to the result (A+Carry), which is a standard function of the 74181 ALU chip: after Left Shifting, the MSB (bit 4) will be copied into the carry flag and the LSB (bit 0), which is zero, will be filled by the Carry soon after having performed the function A+Carry.

In APOLLO181 Right Shifting (SHR) is performed by repeating four times a Rotate Through Carry Left, soon after having cleared the Carry flag: the bits are shifted to the left, zero is filled in on the LSB (bit 0) and a circular shift including the carry is done four times.

The Rotate Through Carry Right (RCR) is performed by repeating four times a Rotate Through Carry Left: the bits are shifted to the left, the carry is filled in on the LSB (bit 0) and a circular shift including the carry is done four times.

To perform the Rotate Right (ROR) in APOLLO181, before we need to fill the Carry flag with the LSB. First we test if the LSB is "1" with a "A OR 1110 plus 1" arithmetic operation. To perform it in the 74181, initial Carry must be set to “With Carry”. Only if the tested bit is one, the result of the logic OR is 1111, the “A OR B plus 1” instruction generates a carry and the Cn+4 output goes low (i.e. “With Carry” status in APOLLO181). Then we reload again the 4-bit word which needs to be rotated, because it was destroyed by the previous operation: this instruction doesn't affect the Carry flag that was set before to the LSB value. Now we can perform the Rotate Right using the Rotate Through Carry Right algorithm: the bits are shifted to the left, the carry is filled in on the LSB (bit 0) and a circular shift including the carry is done four times.

Now in APOLLO181 performing a 16-bit Shift Right with a unique 74181 chip is as simple as performing four times a 4-bit Rotate Through Carry Right on the four nibbles which compose the 16-bit initial word that needs to be shifted. This simple algorithm is extremely important since it is intensively used in the fast 16-bit multiplication algorithm to shift right the multiplier and test the Carry. You may notice that it uses always the same function of the ALU 74181.

Fast 12-bit Multiplication using 74181 shifting capability

Now we are ready to implement the fast multiplication algorithm of two positive binary numbers, that is essentially an adding and shifting operation using the basic binary multiplication rules ( 1 X 1 = 1; 1 X 0 = 0; 0 X 1 = 0; 0 X 0 = 0).

1010  X    10d    (Multiplicand)

101  =    5d     (Multiplier)

______

1010       Partial product

0000        Partial product: shift multiplicand one bit to left

1010         Partial product: shift multiplicand one bit to left

______

110010       50d    (Product or Result)

According to the formal paper-and-pencil procedure (see the above example), we can perform in APOLLO181 the “sum of partial-products” algorithm on  two 12-bit factors, resulting in a 24-bit long product, by executing the following steps:

1) Store the 12-bit Multiplicand in six 4-bit registers

2) Store the 12-bit Multiplier in three 4-bit registers

3) Clear intermediate result (six 4-bit registers, i.e. 24-bit long)

4) Do steps from 5) to 7) twelve times, using a 4-bit register counter, then goto step 8)

5) Shift one bit right the Multiplier to fill in the Carry the LSB

6) If Carry  = 1 add the Multiplicand to the intermediate result

7) Shift one bit left the Multiplicand

8) Display the 24-bit result.

In total we have used all the sixteen 4-bit registers of APOLLO181: 6 registers for the shifting Multiplicand (Reg5, Reg4, Reg3, Reg2, Reg1, Reg0 = LSB), 3 registers for the Multiplier (Reg8, Reg7, Reg6 = LSB), 6 registers for the results (RegE, RegD, RegC, RegB, RegA, Reg9 = LSB), and 1 register as a counter of cycles (RegF).

The core of the multiplication algorithm is 74 Byte long, from P84 to P157, that is a cycle of seventy-four APOLLO181 instructions, and each cycle is repeated twelve times. In total the 12-bit fast multiplication requires 74*12 = 888 instructions.

We said that APOLLO181 running at 3 MHz, is able to perform 750000 complete instructions per second or one instruction every 1,33 microseconds.

Thus APOLLO181 will perform the 12-bit calculation in ( 74 * 12 *1,33 us ) = 1,184 ms.

So, the most complex calculation that can be performed by APOLLO181, that is 2^12-1 * 2^12-1 = 4095*4095 = 16.769.025 (or “1111 1111 1110 0000 0000 0001” in binary), takes less than one point two millisecond.

We cannot implement a 16-bit multiplication in APOLLO181 without doing hardware modifications because we don't have enough registers to store temporary results. We could use the sixteen latches of the output ports to perform it, connecting bit-to-bit the nibble output of one port number to the nibble input of the same port number and writing and reading any port as if it were a 4-bit register: that is an easy way to expand the number of internal 4-bit registers to 32.

Herebelow the working 12-bit multiplication algorithm.

Clear registers:

P1   00   10   ACC = 0#

P2   01   F7   OUT PORT [7] = ACC

P3   02   F8   OUT PORT [8] = ACC

P4   03   F9   OUT PORT [9] = ACC

P5   04   FA   OUT PORT [A] = ACC

P6   05   29   REG [9] = ACC

P7   06   2A   REG [A] = ACC

P8   07   2B   REG [B] = ACC

P9   08   2C   REG [C] = ACC

P10  09   2D   REG [D] = ACC

P11  0A   2E   REG [E] = ACC

P12  0B   2F   REG [F] = ACC

P13  0C   23   REG [3] = ACC

P14  0D   24   REG [4] = ACC

P15  0E   25   REG [5] = ACC

Input factors:

P16  0F   E7   ACC = IN PORT [7]

P17  10   20   REG [0] = ACC

P18  11   F7   OUT PORT [7] = ACC

P19  12   E8   ACC = IN PORT [8]

P20  13   21   REG [1] = ACC

P21  14   F8   OUT PORT [8] = ACC

P22  15   E9   ACC = IN PORT [9]

P23  16   AE   Compare ACC with E#

P24  17   1B   ACC = B#

P25  18   C1   IF ZERO GOTO 1B#

P26  19   1F   ACC = F#

P27  1A   00   GOTO 0F#

P28  1B   E9   ACC = IN PORT [9]

P29  1C   A7   Compare ACC with 7#

P30  1D   11   ACC = 1#

P31  1E   C2   IF ZERO GOTO 21#

P32  1F   1B   ACC = B#

P33  20   01   GOTO 1B#

P34  21   E7   ACC = IN PORT [7]

P35  22   22   REG [2] = ACC

P36  23   F9   OUT PORT [9] = ACC

P37  24   E9   ACC = IN PORT [9]

P38  25   AD   Compare ACC with D#

P39  26   1A   ACC = A#

P40  27   C2   IF ZERO GOTO 2A#

P41  28   11   ACC = 1#

P42  29   02   GOTO 21#

P43  2A   E9   ACC = IN PORT [9]

P44  2B   A7   Compare ACC with 7#

P45  2C   10   ACC = 0#

P46  2D   C3   IF ZERO GOTO 30#

P47  2E   1A   ACC = A#

P48  2F   02   GOTO 2A#

P49  30   E7   ACC = IN PORT [7]

P50  31   26   REG [6] = ACC

P51  32   F7   OUT PORT [7] = ACC

P52  33   E8   ACC = IN PORT [8]

P53  34   27   REG [7] = ACC

P54  35   F8   OUT PORT [8] = ACC

P55  36   10   ACC = 0#

P56  37   F9   OUT PORT [9] = ACC

P57  38   E9   ACC = IN PORT [9]

P58  39   AE   Compare ACC with E#

P59  3A   1E   ACC = E#

P60  3B   C3   IF ZERO GOTO 3E#

P61  3C   10   ACC = 0#

P62  3D   03   GOTO 30#

P63  3E   E9   ACC = IN PORT [9]

P64  3F   A7   Compare ACC with 7#

P65  40   14   ACC = 4#

P66  41   C4   IF ZERO GOTO 44#

P67  42   1E   ACC = E#

P68  43   03   GOTO 3E#

P69  44   E7   ACC = IN PORT [7]

P70  45   28   REG [8] = ACC

P71  46   F9   OUT PORT [9] = ACC

P72  47   E9   ACC = IN PORT [9]

P73  48   AD   Compare ACC with D#

P74  49   1D   ACC = D#

P75  4A   C4   IF ZERO GOTO 4D#

P76  4B   14   ACC = 4#

P77  4C   04   GOTO 44#

P78  4D   E9   ACC = IN PORT [9]

P79  4E   A7   Compare ACC with 7#

P80  4F   13   ACC = 3#

P81  50   C5   IF ZERO GOTO 53#

P82  51   1D   ACC = D#

P83  52   04   GOTO 4D#

Increment the counter:

P84  53   9F   SET WITH CARRY

P85  54   49   SET ALU to 9#

P86  55   10   ACC = 0#

P87  56   6F   ACC = Arithm f (ACC, REGF, CARRY)

P88  57   2F   REG [F] = ACC

Test the counter:

P89  58   AD   Compare ACC with D#

P90  59   1D   ACC = D#

P91  5A   C9   IF ZERO GOTO 9D#

Shift Rigth the Multiplier:

P92  5B   90   SET NO CARRY

P93  5C   4C   SET ALU to C#

P94  5D   38   ACC = REG [8]

P95  5E   50   ACC = Arithm f (ACC, 0#, CARRY)

P96  5F   50   ACC = Arithm f (ACC, 0#, CARRY)

P97  60   50   ACC = Arithm f (ACC, 0#, CARRY)

P98  61   50   ACC = Arithm f (ACC, 0#, CARRY)

P99  62   28   REG [8] = ACC

P100 63   37   ACC = REG [7]

P101 64   50   ACC = Arithm f (ACC, 0#, CARRY)

P102 65   50   ACC = Arithm f (ACC, 0#, CARRY)

P103 66   50   ACC = Arithm f (ACC, 0#, CARRY)

P104 67   50   ACC = Arithm f (ACC, 0#, CARRY)

P105 68   27   REG [7] = ACC

P106 69   36   ACC = REG [6]

P107 6A   50   ACC = Arithm f (ACC, 0#, CARRY)

P108 6B   50   ACC = Arithm f (ACC, 0#, CARRY)

P109 6C   50   ACC = Arithm f (ACC, 0#, CARRY)

P110 6D   50   ACC = Arithm f (ACC, 0#, CARRY)

P111 6E   26   REG [6] = ACC

Test if  Carry = 1:

P112 6F   13   ACC = 3#

P113 70   D7   IF CARRY GOTO 73#

P114 71   17   ACC = 7#

P115 72   08   GOTO 87#

Shift Left the Multiplicand:

P116 73   90   SET NO CARRY

P117 74   49   SET ALU to 9#

P118 75   30   ACC = REG [0]

P119 76   69   ACC = Arithm f (ACC, REG9, CARRY)

P120 77   29   REG [9] = ACC

P121 78   31   ACC = REG [1]

P122 79   6A   ACC = Arithm f (ACC, REGA, CARRY)

P123 7A   2A   REG [A] = ACC

P124 7B   32   ACC = REG [2]

P125 7C   6B   ACC = Arithm f (ACC, REGB, CARRY)

P126 7D   2B   REG [B] = ACC

P127 7E   33   ACC = REG [3]

P128 7F   6C   ACC = Arithm f (ACC, REGC, CARRY)

P129 80   2C   REG [C] = ACC

P130 81   34   ACC = REG [4]

P131 82   6D   ACC = Arithm f (ACC, REGD, CARRY)

P132 83   2D   REG [D] = ACC

P133 84   35   ACC = REG [5]

P134 85   6E   ACC = Arithm f (ACC, REGE, CARRY)

P135 86   2E   REG [E] = ACC

Add the Multiplicand to the intermediate result:

P136 87   90   SET NO CARRY

P137 88   4C   SET ALU to C#

P138 89   30   ACC = REG [0]

P139 8A   50   ACC = Arithm f (ACC, 0#, CARRY)

P140 8B   20   REG [0] = ACC

P141 8C   31   ACC = REG [1]

P142 8D   50   ACC = Arithm f (ACC, 0#, CARRY)

P143 8E   21   REG [1] = ACC

P144 8F   32   ACC = REG [2]

P145 90   50   ACC = Arithm f (ACC, 0#, CARRY)

P146 91   22   REG [2] = ACC

P147 92   33   ACC = REG [3]

P148 93   50   ACC = Arithm f (ACC, 0#, CARRY)

P149 94   23   REG [3] = ACC

P150 95   34   ACC = REG [4]

P151 96   50   ACC = Arithm f (ACC, 0#, CARRY)

P152 97   24   REG [4] = ACC

P153 98   35   ACC = REG [5]

P154 99   50   ACC = Arithm f (ACC, 0#, CARRY)

P155 9A   25   REG [5] = ACC

Repeat the cycle:

P156 9B   13   ACC = 3#

P157 9C   05   GOTO 53#

Display the result:

P158 9D   39   ACC = REG [9]

P159 9E   F7   OUT PORT [7] = ACC

P160 9F   3A   ACC = REG [A]

P161 A0   F8   OUT PORT [8] = ACC

P162 A1   3B   ACC = REG [B]

P163 A2   F9   OUT PORT [9] = ACC

P164 A3   3C   ACC = REG [C]

P165 A4   FA   OUT PORT [A] = ACC

P166 A5   E9   ACC = IN PORT [9]

P167 A6   AD   Compare ACC with D#

P168 A7   1B   ACC = B#

P169 A8   CA   IF ZERO GOTO AB#

P170 A9   1D   ACC = D#

P171 AA   09   GOTO 9D#

P172 AB   E9   ACC = IN PORT [9]

P173 AC   A7   Compare ACC with 7#

P174 AD   11   ACC = 1#

P175 AE   CB   IF ZERO GOTO B1#

P176 AF   1B   ACC = B#

P177 B0   0A   GOTO AB#

P178 B1   3D   ACC = REG [D]

P179 B2   F7   OUT PORT [7] = ACC

P180 B3   3E   ACC = REG [E]

P181 B4   F8   OUT PORT [8] = ACC

P182 B5   10   ACC = 0#

P183 B6   F9   OUT PORT [9] = ACC

P184 B7   FA   OUT PORT [A] = ACC

P185 B8   E9   ACC = IN PORT [9]

P186 B9   AE   Compare ACC with E#

P187 BA   1E   ACC = E#

P188 BB   CB   IF ZERO GOTO BE#

P189 BC   11   ACC = 1#

P190 BD   0B   GOTO B1#

P191 BE   E9   ACC = IN PORT [9]

P192 BF   A7   Compare ACC with 7#

P193 C0   14   ACC = 4#

P194 C1   CC   IF ZERO GOTO C4#

P195 C2   1E   ACC = E#

P196 C3   0B   GOTO BE#

P197 C4   1D   ACC = D#

P198 C5   09   GOTO 9D#