As a reminder, the Bentium Pro has four flags:
- Carry. This can contain the carry/borrow from the adder and also the bit moved ‘out’ by a shift/rotate operation. It will be cleared by a logic AND, OR, or XOR operation and can also be explicitly set, cleared or inverted.
- Overflow. The overflow operation indicates that the result of a two’s complement arithmetic operation was too large a positive number or too large a negative number to be represented in a single byte.
- Not-zero. Whether the result was zero or not. This takes input from the bus so can be used for anything output by the ALU as well as anything placed on the bus from elsewhere in the computer (e.g. an I/O operation).
- Negative (sign). This is set if the result of a two’s complement operation was negative.
The Register Itself
Data is latched into the register by the /flags_latch control signal. Note that all four flags will always be stored but a /flags_latch signal. If an operation doesn’t generate a meaningful value for one or more flags then those flags will not contain valid information.
The Negative Flag
This is a quick an easy one. The negative flag indicates if the result of the last addition (or subtraction) was negative. It only contains a meaningful value if the operation was a two’s complement operation and only the programmer knows if her operation involved two’s complement numbers.
A two’s complement number is negative if the most significant bit (bit 7) is set, so this flag simply takes bit 7 as output by the adder.
For operations other than addition/subtraction this value will be meaningless.
The Not-Zero Flag
I actually intended to have a zero flag rather than a not-zero flag but the value output from the basic circuitry is not-zero and I didn’t have any board space left to invert it. Since this is purely a semantic issue which can easily be compensated for by the assembly language code I’ve decided to leave it this way.
Not-Zero is evaluated simply by testing whether all eight output bits are zero and all we have to do to evaluate that is OR all eight bits together. The only part available for this would be a 74LS version of the 74HC4078 8-input OR/NOR gate but even the 74HC version is listed as obsolete. We could use seven two input OR gates but this would require two 74LS32 ICs, as shown below.
I didn’t want to have to use that much board space so decided to use diode logic instead. If you’ve never encountered diode logic before I would strongly recommend reading my article about it.
The diagram above shows my actual circuit. This uses a 74LS245 bus transceiver to act as a buffer between the main bus and the diodes. I use this to ensure that the diodes are getting good, solid input signals and also to isolate the diodes from the bus so they don’t cause any unwanted side-effects. This may well be unnecessary but I didn’t want to have to deal with debugging obscure problems later. The ‘245 is permanently enabled.
The diode OR gate works such that, if all the outputs from the ‘245 are low then the resistor pulls the not_zero_flag_out signal low. If one or more of outputs from the ‘245 are high then the not_zero_flag_out signal will become high.
The resistor value is, admittedly, the result of trial and error. I initially used a 10k resistor but the output was unreliable. Moving down to 3.3k has given a faultless output, so far.
The Overflow Flag
As you may remember from Ben Eater’s video on negative numbers in binary than a single byte in two’s complement format can hold a number between -128 and 127. An overflow happens when the result is a number which is too large a positive number or too small a negative number to fit into the output (in our case an 8-bit byte).
This happens when we add two numbers and the total is more than 127 or when we subtract two number and the result is less than -128. (The latter properly termed an underflow).
Testing For Overflow
Lets look at all the possible operations and the largest result we could get from each and see which could cause an overflow or underflow.
- positive + positive: 127 + 127 = 254 Overflow
- positive + negative: 0 + -128 = -128
- negative + positive: -1 + 127 = 126
- negative + negative: -128 + -128 = -256 Underflow
- positive – positive: 0 – 127 = 0 + -127 = -127
- positive – negative: 127 – -128 = 127 + 128 = 255 Overflow
- negative – positive: -128 – 127 = -128 + -127 = -255 Underflow
- negative – negative: -128 – -128 = -128 + 128 = 0
In the above list I have also rewritten the subtractions as additions which shows there is only one operation which could cause an overflow: adding a positive number to a positive number; and only one condition which could cause an underflow, subtracting a negative number from a negative number.
In two’s complement a positive number will always have a 0 if the most significant bit (MSB) (values 0 .. 127). An overflow happens when the result causes a carry into the most significant bit (values 128..255). I.e. when both inputs are positive but the result is negative. When the MSB of both inputs is zero and the MSB of the result is 1.
Negative numbers always have a 1 as the MSB. An underflow happens when there is a carry into the MSB. Since the MSB of both inputs is 1 this results in a carry out of the MSB and the MSB of the result is 0. For example:
-128 + -1 = -129 10000000 + 11111111 = 1.01111111 -128 + -128 = -256 10000000 + 10000000 = 1.00000000
(I recommend having a play with a two’s complement decimal to binary converter to help visualise this).
Thus we get an underflow when both inputs are negative but the result is positive. When the MSB of both inputs is 1 and the MSB of the output is 0.
Building An Overflow Tester Circuit
If we name the MSB of input W as w7 and the same for input Z as z7 and for the result as r7 then we get an overflow when (w7 == z7) AND (w7 != r7).
How do we test a boolean for equality (or inequality)? Look at the truth table for an exclusive OR:
a b q 0 0 0 0 1 1 1 0 1 1 1 0
and you can see that if both inputs are the same we get a zero out, if both inputs are different we get a one. We can rewrite our overflow formula above as NOT (w7 XOR z7) AND (w7 XOR r7) giving the following circuit:
On the Bentium Pro I had no space for an inverter but I did have a spare XOR gate so I used that to do the inversion by XORing against a fixed high input. I also had no spare space for an AND gate so I used a diode logic AND gate giving the final circuit below:
In practice the ALU is already calculating W XOR Z as part of the logic circuitry so I can use bit 7 of the output from this as the w7 XOR z7 value and save a XOR gate (which I don’t have room for anyway!). I’ve termed this xor_bit_7. My final circuit diagram for the flags module is:
The Carry Flag
The final flag is the carry flag. As mentioned above this can take a value from one of four different sources depending on the operation:
- Carry out from the adder.
- Left shift/rotate.
- Right shift/rotate.
- An explicit value for logic operations, set carry, clear carry and complement carry.
Before I get to the circuitry for selecting a source for the carry flag I want to talk about where the flag values come from.
Carry Out From The Adder
This is, fairly obviously, the carry out from the 74LS161 calculating the most significant nybble of the sum. However when I initially wired this up I found that, for a subtraction, the value was the inverse of what I was expecting.
Googling for the reason why gave me two possible explanations:
- The carry is actually a borrow for a subtraction so needs to be inverted.
- I’m inverting the Z register and the carry flag on input to the adders and therefore need to invert the carry flag again on the way out.
(These explanations are not necessarily exclusive: they may both be correct). I’m ashamed to say that I can’t give a proper reason why, but the end result of this is that I need to invert the carry out if I’m doing a subtraction and this can be done, as it is for the carry in by XORing the carry out with the subtract control signal.
Carry From Shift/Rotate
These two options are simple to explain. When the value is shifted/rotated right the value in the old least significant bit is the carry out. When the value is shifted/rotated left the old most significant bit is the carry out.
The shift/rotate circuit only works on the W register and the potential carry out bits aren’t actually modified in any way by the shift/rotate circuit so, to keep the wiring shorter, values are fed directly from the W register. If you look at the register circuit board you can see the two brown wires leading up from bits 7 and 0 to the carry out selector.
Explicit Carry Out Value
The final option for the carry output is an explicit on/off/inverted value. If you’ve read my article about Adding ADC, SBC, INC & DEC Operations To Ben Eater’s ALU you’ll know that this circuit has the ability to feed an explicit zero (for DEC and ADD), one (for INC) and inverted carry flag (for SBC).
So all I need to do is feed this output back as a potential input to the carry flag.
Selecting a Carry Out Value
The only thing left to do is to select a suitable source for the carry flag.
The ALU as a whole evaluates every possible output and has a 74LS245 bus transceiver for each possible output. The control logic sends an enable signal for the appropriate value to be output to the bus. I.e. for an addition or subtraction the ‘245 for the adder will be enabled. For an AND the ‘245 for the AND will be enabled, and so on for OR, XOR, left shift/rotate and right shift/rotate.
We can reuse those signals to select our carry out source. In programming terms we need a case statement:
on adder_read: use adder_carry_out on left_read: use left_carry out on right_read: use right_carry_out etc...
We might think of the using something like the 74LS153 Data selector/multiplexer which selects one of four possible inputs as the output (as used in the shift/rotate circuit) but this chip uses a two bit binary input to select a source and we have four separate selection signals.
Selecting With AND Gates
How about using AND gates? Have a look at the truth table for an AND gate with the inputs renamed:
Select Signal Output 0 0 0 0 1 0 1 0 0 1 1 1
If select is 0 the output will always be 0. If select is 1 the output is the same as the signal input.
Extending this to multiple sources with a separate AND gate for each source then, as long as we’re only sending one select signal at a time, every AND gate will be outputting a 0 except the selected gate which will only be outputting a 1 if it’s signal input is one:
OutputA OutputB OutputC OutputD Output 0 0 0 0 0 (Nothing select or selected signal is 0). 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1
It should be easy to see that our final output is the result of ORing the outputs of the four AND gates.
And Now With Inverted Logic
But the ‘245 uses an inverted enable signal so these signals are also inverted. Thus we need to select a value based on whichever signal is low. This is just as easy to do but harder to understand. In inverted logic an AND gate becomes and OR gate, and an OR gate becomes an AND gate.
We need to OR each signal with each potential value. The OR gate outputs will normally be high (because the select/enables, when off are high). When a select/enable becomes low the OR gate outputs the signal (the potential carry value).
So the final output will be high unless the selected signal is low: an AND gate.
So the circuit needs four OR gates, one for each signal, plus an AND gate to combine the four outputs. But given my lack of space and thrill of playing with diode logic I’ve used a diode AND gate to do this, and here’s the circuit:
The Other Carry Selector Signal
In the passages above I glossed over the selector for the fourth carry output value. Remember this is the explicit on/off/invert value.
I also want my AND/OR/XOR operations to clear the carry flag. They’re already affecting the not-zero flag and, because the flags register writes all four flags at the same time then <i>something</i> will be going into the carry flag and we may as well make this something which could be useful to the programmer.
I chose to select by fourth carry value when any of the AND, OR or XOR ‘245 bus transceivers is enabled and added a little hack to use one of those signals for the explicit carry on/off/invert operations. This means that when to do a carry on/off/invert one of the logic outputs will also be writing to the bus but we just need to make sure that nothing else is using the bus at the same time.
Again those enable signals are inverted. To get an inverted select signal when any of them is active needs and AND gate. Again I didn’t have any board space for an AND gate and used one built with diodes.
On the physical boards you can see these diodes next to each of the ‘245s in the logic section on the left hand side of the bottom three boards.
And that epic post wraps up the flags section of the ALU. Next time I’ll move back to the beginning to describe the ALU registers, adder and logic circuits, all of which are either almost identical to Ben Eater’s originals or refreshingly simple to explain.