CPU multi-byte mathematical operations

In order to be more than a toy the 8 bit Juno CPU needs to be capable of performing multi-byte mathematical operations. 

It is capable of adding, subtracting and shifting of multi-byte numbers as described below. The  shifting operations are used to support multiplication and division. 

In order to make the examples below simpler and shorter 4 bit numbers are used but the Juno CPU is 8 bit.

Multi-byte addition

In order to add two multi-byte numbers the bytes are added starting with the least significant bytes first. Adding the least significant bytes calculates the least significant byte of the result and the carry. The next two bytes are then added plus the carry and so on.

Example

28 + 28 = 56

In binary this is

0001 1100 + 0001 1100

= 0011 1000

This is calculated 4 bits at a time as follows

Set carry = 0

1100 + 1100 + carry = 1000 (carry =1)

0001 + 0001 + carry = 11 (carry = 0)

= 0011 1000

Two CPU instructions are required to perform the above calculation in assembler code. The first instruction is to clear the carry flag e.g. CLC. The second instruction is to add two number with carry e.g. ADC.

The inclusion of a third instruction to the Instruction set add without carry, ADD, which over-rides the carry flag with 0 allows the addition to be implemented more optimally in fewer lines of code as it removes the need to explicitly clear the carry flag first.

Multi-byte subtraction

In order to subtract two multi-byte numbers the fact that mathematically a- b is the same as a + (-b) is exploited as it is easy to calculate -b and doing so allows the logic of the adder to be reused rather than building an entirely seperate piece of logic dedicated to subtraction.

-b is calculated by inverting b and adding 1 to produce the two's complement representation of -b. The invertion can be achieved through the application of not logic and the adding of 1 can be done by forcing the carry to 1 for the addition of the first two bytes. The addition of subsequent bytes adds the resultant carry of the previous calculation.

Example

28 - 27 = 1

In binary this is

0001 1100 - 0001 1011 

= 0000 0001

This is calculated 4 bits at a time as follows

Set carry = 1 (force carry to 1 to calculate the two's complement)

1100 + (invert 1011) + carry =

1100 + 0100 + carry =

 0001 (carry = 1)

0001 + (invert 0001) + carry =

0001 + 1110 + carry = 

0000 (carry = 1)

The final carry of 1 is ignored.

Two CPU instructions are required to perform the above calculation in assembler code. The first instruction is to set the carry flag e.g. SEC. The second instruction is to subtract two numbers with carry e.g. SBC.

The addition of a third instruction to subtract without carry, SUB, which over-rides the carry flag with 1 allows the subtraction to be implemented more optimally in fewer lines of code as it removes the need to explicitly set the carry flag first.

Shifting multi-byte numbers left and right

The ability to shift numbers is key to implementing multiplication and division efficiently in assembler as the Juno CPU does not have dedicated multiplication and division instructions.

Mathematically shifting a number 1 place to the left is the equivalent of multiplying by 2. Likewise, mathematically shifting a number 1 place to the right is the equivalent of dividing by 2.

In order to shift multi-byte numbers two types of shift operation are required, mathematical shift and rotation.

Mathematical shift fills the gap created by the shift with a zero and moves the bit that drops off into the carry flag.

Examples

1101 mathematically shifted to the left becomes 1010 (carry = 1)

0101 mathematically shifted to the left becomes 1010 (carry = 0)

1101 mathematically shifted to the right becomes 0110 (carry = 1)

The value of carry before the shift is irrelevant.

Rotational shift is similar to mathematical shift but fills the gap with the input value of carry. Like mathematical shift the output value of the carry flag is set to the bit that drops off.

Example

carry = 1

1101 rotated to the left becomes 1011 (carry = 1)

In order to multiply a multi-byte number by two the least significant byte is first mathematically shifted to the left by one place. The subsequent bytes are then rotated to the left by one place starting with the second least significant byte. This approach preserves the bit that 'drops off' and moves it into the next byte.

In order to divide a multi-byte number by two a similar approach is taken but starting with mathematically shifting the most significant byte to the right by 1 place. Subsequent bytes are then rotated to the right by one place starting with the second most significant byte.

The rotate and shift operations can be implemented by two CPU instructions.

ROR - ROtate Right through carry. Fill with carry.

ROL  - ROtate Left through carry. Fill with carry.

In order to optimise assemble code additional instructions could be provided that over-ride the value of carry removing the need to clear, or set, carry before performing a Mathematical Shift instruction.

SL0 - Shift Left filling with 0

SL1 - Shift Left filling with 1

SR0 - Shift Right filling with 0

SR1 - Shift Left filling with 1

Overflow flag implemented using an 8:1 multiplexer

The overflow flag is used to indicate an error condition when adding, or subtracting, two's complement numbers. The error indicates that the result does not fit within the number of ALU bits and is therefore incorrect.
The overflow flag is different to the carry flag which indicates that a mathematical carry or borrow has been generated out of the most significant bit.

In a two's complement number the most significant bit indicates whether the number is negative or positive. Zero indicates positive and one indicates negative. When adding two's complement positive numbers (msb is 0) the result should be positive (msb 0) likewise when adding two negative numbers (msb is 1) the result should be negative (msb 1).

In an 8 bit ALU adding 127 and 127 gives 254 which in binary is 1111 1110. But if two's complement notation is being used then the output is not interpreted as 254 but -2.This error occures because the result is two large to fit within 8 bits and has overflowed.

It is important to understand that the overflow flag is set for every addition but it only makes sense when two's complement notation is being used. If two's complement representation is not being used it should be ignored.

The calculation of the overflow flag for addition is given below. Within Juno subtraction is performed using addition therefore we only need to calculate overflow for addition.

Inputs  Outputs
A B Z   Overflow Flag
0 0 0   0
0 0 1   1 (adding two positives should be positive)
0 1 0   0
0 1 1   0
1 0 0   0
1 0 1   0
1 1 0   1 (adding two negatives should be negative)
1 1 1   0


The calculation of the overflow flag can be done in logic as shown below






But this would require a number of logic chips of different types. An alternative approach is to implement the logic using a single 8:1 multiplexer such as the 74HC251.The 8:1 multiplexer has three select inputs(S0,S1,S2) which correspond to A, B and Z above and are used to select one of the eight inputs to be the output. By appropriately hard wiring the eight inputs high or low it is possible to create the logic table above and implement the overflow logic using a single IC.

The table below shows how the input values need to be set. 

A  B  Z   
S2 S1 S0  input  value
0  0  0   I0     0
0  0  1   I1     1
0  1  0   I2     0
0  1  1   I3     0
0  0  0   I4     0
1  0  0   I5     0
1  0  1   I6     0
1  1  0   I7     1
1  1  1   I8     0  

ALU Design v0.1

The ALU Design v0.1 is a slight variation on the previous ALU (bits 0..3) design which means the same board design can be used for both the ALU bits 0..3 and the ALU bits 4..7 boards.

The modification adds the A3 and B3 from the ALU board's input buses to the board's output bus so that these input values form part of the input into the shifter and flags board.

Bits 7 of the A and B inputs into the ALU are required by the shifter and flags board to calculate the overflow flag. The design means both bits 3 and 7 of the ALU input will go the the shifter and flags board but the board design will simply ignore the bits from the ALU bits 0..3 board.

The Eagle CAD schematic for ALU Design v0.1 can be downloaded here.

The Eagle CAD board for ALU Design v0.1 can be downloaded here.

The bill of materials
Part     Value          Package      Library  Position (inch)       Orientation

C1       0.1uF          C050-030X075 rcl      (0.55 0.6)            R0
C2       0.1uF          C050-030X075 rcl      (0.95 0.6)            R180
C4       0.1uF          C050-030X075 rcl      (2.35 0.6)            R0
C5       0.1uF          C050-030X075 rcl      (0.9 2.95)            R90
C6       0.1uF          C050-030X075 rcl      (1.5 2.95)            R90
C7       0.1uF          C050-030X075 rcl      (2.1 2.95)            R90
C8       0.1uF          C050-030X075 rcl      (3.55 1)              R270
C9       0.1uF          C050-030X075 rcl      (3.55 2.15)           R270
C10      10uF           E5-5         rcl      (0.9 0.3)             R90
C11      0.1uF          C050-030X075 rcl      (2.7 2.9)             R90
C12      10uF           E5-5         rcl      (3.2 2.7)             R270
CONTROL                 1X08         pinhead  (1.85 0.3)            R180
IC1      74HC08N        DIL14        74xx-eu  (1.2 2.5)             R270
IC2      74HC32N        DIL14        74xx-eu  (1.8 2.5)             R270
IC3      74HC86N        DIL14        74xx-eu  (2.4 2.5)             R270
IC4      74HC157N       DIL16        74xx-eu  (1.2 1.15)            R90
IC5      74HC153N       DIL16        74xx-eu  (3.2 1.9)             R270
IC6      74HC153N       DIL16        74xx-eu  (3.2 0.75)            R270
IC7      7483N          DIL16        74xx-eu  (1.8 1.15)            R90
IC8      74HC157N       DIL16        74xx-eu  (0.55 2.5)            R270
IC9      74HC153N       DIL16        74xx-eu  (2.4 1.15)            R90
IC10     74HC86N        DIL14        74xx-eu  (0.6 1.2)             R90
INPUT                   1X08         pinhead  (0.2 1.4)             R90
JP4                     1X02         pinhead  (0.6 0.2)             R180
JP5                     1X02         pinhead  (3.45 2.8)            R0
OUTPUT                  1X08         pinhead  (3.75 1.45)           R270

 

ALU Sketch #2 - PCB board layout

Having experimented laying out the PCB for the ALU sketch #2 design it is clear it will not fit on a single board within the EagleCAD size constraints therefore I have split it into 3 PCBs as follows

• Board 1 is the 4 bit ALU for bits 0 to 3
• Board 2 is the 4 bit ALU for bits 4 to 7
• Board 3 contains the shifter and flag logic

For details of the ALU design see ALU Sketch #2

Little Endian vs Big Endian

Little Endian and Big Endian refers to the order in which multi-byte numbers are stored in memory. The  Juno CPU is Little Endian like Intel chips used in PCs and the 6502.

What is Endianess? 

It is easier to demonstrate Endianess using hexadecimal numbers, which is one of the reasons why system programmers like using hexadecimal so much as it makes things much simpler.

Take the two byte hexadecimal value 0xFF08 (65288 in decimal) in Big Endian notation the 2 byte value 0xFF08 is stored in memory most significant byte first as follows

Address 100 = FF

Address 101 = 08

In Little Endian notion the same two byte value is stored in memory least significant byte first

Address 100 = 08

Address 101 = FF

If you read the contents of memory as part of a memory dump then Big Endian notation would be written left to right as FF08 whereas Little Endian notation would be written 08FF. 

Note that byte order Endianess does not apply to the order in which the individual bits within a byte are stored only the bytes themselves.

So why would anybody want to use Little Endian notation as it appears backwards and awkward to read? 

There are many articles on the web discussing the advantages and disadvantages of Little vs big Endian and even many articles arguing there are no real advantages or disadvantages to either.

For the Juno PC there is one clear advantage of using Little Endian which is why I have chosen to use it. Little Endian makes some multi-byte operations easier to implement in micro-code because the program counter will be pointing to the least significant byte following the fetch of the instruction and the least significant bytes need to be added first in order to calculate the carry in multi-byte operations

For example, consider an instruction to jump relative by a two byte offset e.g. JMR #1000. In micro-code this instruction is implemented by adding the 2 byte value to the program counter in an intermediate register such as MAR and loading PC with the result. After fetching the JMR instruction the PC will point to the least significant byte of the offset. This can be fetched and added to MAR and the carry will be calculated ready for the addition of the second byte to MAR. If the value was stored in Big Endian order then the PC would need to be incremented to point to the LSB and then decremented to point to the MSB which would require more micro-code steps and hence clock cycles.

ALU Design (bits 0 - 3) #1 PCB

The ALU (bits 0..3) board lay out in EagleCAD. The EagleCAD board file can be downloaded here and the schematic here.

The following settings were used whilst laying out the board everything else was left as default

• DRC set to Eurocircuits-EAGLE design rules setup for 2-layer PatternClass6 BaseCopper018 eCDefault. The DRC rules can be downloaded from Eurocircuits website. 
• The version text used size = 0.05, ratio 8 %, line distance 50%, and font set to vector
• The labelling of the input & outputs header pins used text  size = 0.04, ratio 8%, line distance 50%, and font set to vector
• Silkscreen text placed on layer 21 tPlace.
• DRC clearance changed to 0.2mm (8mil) for wire: wire, pad and via
• DRC minimum width changed to 0.25mm (10mil) for signal and 0.30 (12mil) for power
• Restring changed to 0.25mm (10mil) for pads: top and bottom. 
• Restring changed to 0.25mm (10mil) for vias outer

 A net class was defined for power with a width of 0.3mm, drill 0mil and clearance 0.mm. The default net class was set to 0.25mm width, 0mil drill and 0.22mm clearance.

Partlist

The parts list exported from EagleCAD. 

Part     Value          Package      Library  Position (inch)       Orientation

C1       0.1uF          C050-030X075 rcl      (0.55 0.6)            R0
C2       0.1uF          C050-030X075 rcl      (0.95 0.6)            R180
C4       0.1uF          C050-030X075 rcl      (2.15 0.6)            R180
C5       0.1uF          C050-030X075 rcl      (0.9 2.95)            R90
C6       0.1uF          C050-030X075 rcl      (1.5 2.95)            R90
C7       0.1uF          C050-030X075 rcl      (2.1 2.95)            R90
C8       0.1uF          C050-030X075 rcl      (3.55 1)              R270
C9       0.1uF          C050-030X075 rcl      (3.55 2.15)           R270
C10      10uF           E5-5         rcl      (0.9 0.3)             R90
C11      0.1uF          C050-030X075 rcl      (2.7 2.9)             R90
C12      10uF           E5-5         rcl      (3.2 2.7)             R270
CONTROL                 1X08         pinhead  (1.85 0.3)            R180
IC1      74HC08N        DIL14        74xx-eu  (1.2 2.5)             R270
IC2      74HC32N        DIL14        74xx-eu  (1.8 2.5)             R270
IC3      74HC86N        DIL14        74xx-eu  (2.4 2.5)             R270
IC4      74HC157N       DIL16        74xx-eu  (1.2 1.15)            R90
IC5      74HC153N       DIL16        74xx-eu  (3.2 1.9)             R270
IC6      74HC153N       DIL16        74xx-eu  (3.2 0.75)            R270
IC7      7483N          DIL16        74xx-eu  (1.8 1.15)            R90
IC8      74HC157N       DIL16        74xx-eu  (0.55 2.5)            R270
IC9      74HC153N       DIL16        74xx-eu  (2.4 1.15)            R90
IC10     74HC86N        DIL14        74xx-eu  (0.6 1.2)             R90
INPUT                   1X08         pinhead  (0.2 1.4)             R90
JP4                     1X02         pinhead  (0.6 0.2)             R180
JP5                     1X02         pinhead  (3.45 2.8)            R0
OUTPUT                  1X08         pinhead  (3.75 1.45)           R270

The mount holes used library component: MOUNT-HOLE3.0 (MOUNT-HOLE).

Shift Register IO Test Board PCB

The IO test board PCB has arrived from Eurocircuits. In fact they have sent two even though I only ordered one. Thanks!

 

and with parts soldered in place.




Running a demo test program which cycles through the values 0 to 255 on the first 75HC595 which in turn is connected to LEDs. Being the first PCB I have ever designed I am pleased with how it has turned out.




 

The demo source code can be found here.