Missed function Check

[Jeana]

Something that has been bothering me is the lack of verification of 2s Complement math.

One line that would help check for this in the test and compare would be:
| 0000000000000010 | 0000000000000010 | 0 | 1 | 0 | 1 | 1 | 0 | 1111111111111100 | 1 | 0 |

This is x=2, y=2, nx, ny, and f are set to 1, output is -4.  None of the other tests check for this.

Most versions of the ALU that I have found will fail this check, because few actually account for correctly implementing the math.

Under the current test, all the checks can be made without every once using a increment, however if you add 2 negative numbers, the result with most implementations shows a failure.

Am I missing something here?

[WBahn]

Jeana wrote

Something that has been bothering me is the lack of verification of 2s Complement math.

One line that would help check for this in the test and compare would be:
| 0000000000000010 | 0000000000000010 | 0 | 1 | 0 | 1 | 1 | 0 | 1111111111111100 | 1 | 0 |

This is x=2, y=2, nx, ny, and f are set to 1, output is -4.  None of the other tests check for this.

Most versions of the ALU that I have found will fail this check, because few actually account for correctly implementing the math.

Under the current test, all the checks can be made without every once using a increment, however if you add 2 negative numbers, the result with most implementations shows a failure.

Am I missing something here?

I'm having a hard time trying to figure out what your point is -- you seem to be mixing up all kinds of different things with little rhyme or reason. For instance, you say that all the checks can be made without using an increment. Okay, let's say that's true. What does that have to do with adding 2 negative numbers? And what does that then have to do with the test you propose?

If you set nx, ny, and f to 1 (and presumably all the others to 0), then you get a function that is not one of the eighteen defined functions. Why should the test file be testing an instruction that is not in the instruction set?

If you work through the logic implied by the control signals, then you would get that the output for that instruction would be

out = -(x+y+2)

which with x=y=2 would be -6, or 1111111111111010

Let's walk it through.

x = 2 = 0000 0000 0000 0010
y = 2 = 0000 0000 0000 0010
!x = 1111 1111 1111 1101
!y = 1111 1111 1111 1101
(!x) + (!y) = 1111 1111 1111 1010 = -6

If you want to test whether or not the ALU adds two negative numbers together correctly, then why not use a test that sets x and y both to negative numbers and then sets the control signals so that the function x+y is executed (namely f=1 and all other signals are 0)?

[WBahn]

Jeana wrote

Something that has been bothering me is the lack of verification of 2s Complement math.

I just looked at the test file and it does do some verification of 2'c complement math.

There is a test of y-x with y = 3 and x = 17, with the result being -14.

Then all of the math functions are tested with x = 0 and y = -1.

Certainly the tests can be made far more extensive, but they also need to run in a reasonable time, particularly when a grader is running the submissions of dozens of people.

The claim is not that it is impossible that a flawed implementation could coincidentally pass the 36 tests in this file, merely that it is pretty unlikely that this would happen. Given the very simple implementation of the ALU, this is almost certainly a valid position.

It would be interesting to see a nontrivial implementation that passes all of these tests but that fails work properly for all input. I say nontrivial because it would be trivial to mix the input data with the control signals to accomplish this feat. For instance, since x[10] is zero in all of the test cases, this could be OR'ed with one or more of the control signals and it would have no impact on these particular tests. But as soon as you have a value for which x[10] is a 1, then some of the instructions would be corrupted.

[Jeana]

So, my assumption is that negative numbers cannot be passed directly into the ALU.  Or at least the practice for the hardware drivers is to specify negative numbers using the flags, not direct entry.

Second, -2 + -2 is -4.  Completing a bitwise-not on a number is not the name as getting its inverse value.  For example -2 under 2s complement would be 111..1110 not 111..11101 (as would be the case when simply doing a bitwise-not of a binary 2).  Of course getting the bitwise-not is the first step in getting the 2s complement, next would be incrementing the number by 1 (before doing further arithmetic functions not after).

In order to properly complete an arithmetic addition between 2 numbers, they would need to be in 2s complement.  There are a few ways to implement 2s complement.  However due to the tests performed, the issue is not brought to light if these steps were skipped.  With only 1 negative number, there is a sort of built in work wound when using a full adder, however this breaks down when using 2 negative numbers (made negative by flags).
I expanded beyond the original tests specifically because I was experimenting with trying to minimize the number of complex gates used, and since certain responses were not what I expected, I dug deeper which initiated the expanded test criteria and exposed this interesting quirk.
A further test I did try was to increment a number after, as you have with the x+y+2, and as you said it gets -6, however to only user the bitwise function to add you get -2 (111..1110) which is not the correct answer either.  Only by adding the 2s complements for -2 can you get -4 (mathematically correct).

[WBahn]

Jeana wrote

So, my assumption is that negative numbers cannot be passed directly into the ALU.  

Sure they can. There are no restrictions on what the x and y inputs can be. The beauty of two's complement is that the adder neither knows nor cares whether the input value is unsigned or two's comp.

I think you are basing your assumption on the fact that you can't load a negative number directly into the A register via an A-type instruction. This has nothing to do with the ALU. For instance, consider the following:

@1234
D = -A
@5678
A = -A
D = A - D

When we execute the final instruction we are taking the difference of two negative numbers that were passed into the ALU.

Or at least the practice for the hardware drivers is to specify negative numbers using the flags, not direct entry.

What hardware drivers? What flags? The Hack only has two flags, the ng and zr flags that out outputs from the CPU.

Second, -2 + -2 is -4.  Completing a bitwise-not on a number is not the name as getting its inverse value.  For example -2 under 2s complement would be 111..1110 not 111..11101 (as would be the case when simply doing a bitwise-not of a binary 2).  Of course getting the bitwise-not is the first step in getting the 2s complement, next would be incrementing the number by 1 (before doing further arithmetic functions not after).

That is ONE way to take the two's complement additive inverse of a number. It is not the only way.

Notice that this involves two operations. A more traditional ALU implementation would use XOR gates to perform the bitwise complement on the input value and then use the carry-in bit to perform the increment. But the Hack ALU doesn't have a carry-in bit. Yet it is still able to perform -x (the two's complement additive inverse) in a single instruction. You might examine how it manages to do this.

In order to properly complete an arithmetic addition between 2 numbers, they would need to be in 2s complement.  There are a few ways to implement 2s complement.  However due to the tests performed, the issue is not brought to light if these steps were skipped.  With only 1 negative number, there is a sort of built in work wound when using a full adder, however this breaks down when using 2 negative numbers (made negative by flags).

What workaround?

Again, what flags?

What breaks down? If you set both x and y to be negative numbers, then all of the operations perform exactly as they are supposed to. Try it! Set x to -1234, y to -5678 and run the tests. Which result is incorrect?

I expanded beyond the original tests specifically because I was experimenting with trying to minimize the number of complex gates used, and since certain responses were not what I expected, I dug deeper which initiated the expanded test criteria and exposed this interesting quirk.

What quirk?

You tested the instruction out = -(x+y+2) and it behaved as it should when you set both x and y to 2. No quirk.

A further test I did try was to increment a number after, as you have with the x+y+2, and as you said it gets -6, however to only user the bitwise function to add you get -2 (111..1110) which is not the correct answer either.  Only by adding the 2s complements for -2 can you get -4 (mathematically correct).

Where did I increment a number after?

I don't know what you mean by "to only user the bitwise function to add".

[Jeana]

Ok, when I was saying flags I meant the instruction pins.  My background includes a lot of shell coding, flags are used for instruction modifiers, so I used the term in the wrong context on accident.  I  apologize for the confusion.

I know that the numbers can be processed as input if they were already in 2s complement (specifically useful if further computations would be completed on that variable).  However from the external data entry point of view, a user would (presumably) send a positive numbers with the negate (flags) instructions to produce a product of 2 negative numbers.  Maybe this kind of math would require further processing outside the ALU?

I am aware of using an Xor combined with a half-adder for 2s complement, building a sub-chip for this concept is part of what set off this entire investigation for me.  The use of the full adder was the workaround (vice creating a 2s complement chip separate or other integrated methods) I was talking about.  Maybe it could be called more of a shortcut then a workaround?

Since carry operations are part of an adder, this can (and does) work under most conditions.  I would assume that under extreme high and low numbers this may fail, but haven't tested this.

That method does seems breaks down when both nx, ny instructions are set, at least with the testing I have done so far.  Assuming the goal is specifically arithmetic.

I really do not understand how nx,ny,f=1 (rest=0) are meant to translates to -(x+y+2) aka -x-y-2.  
I understand that this is the result, but it wasn't my intended operation?  

I understand how this condition is created (between the bitwise not and the adder), but the why when using addition this should occur is kind of the issue to me.  Shouldn't the ALU account for the difference between bitwise instructions and math operations?

I would have thought that those instructions should produce = -x + (-y) = -x-y.  Is this were I am misunderstanding the operations?

I will have to try the x to -1234, y to -5678 test later.  I assume you mean using positive x and y, then using the nx and ny instructions?

[WBahn]

I think I'm getting a much better feeling for where you are going astray.

Jeana wrote

Ok, when I was saying flags I meant the instruction pins.  My background includes a lot of shell coding, flags are used for instruction modifiers, so I used the term in the wrong context on accident.  I  apologize for the confusion.

Each control signal tells the ALU to do a very specific thing -- nx, for instance, tells the ALU to take the bitwise complement of the x input (after first being operated on by the zx signal).

The collection of the six input signals results in an overall relationship between the output and the inputs that defines an instruction. The relationship realized by each instruction can be expressed as an arithmetic relationship between x and y and, in some cases, as a bitwise logical relationship. In all of the arithmetic relationships, the inputs are generally interpreted as two's complement values.

There are therefore 64 instructions, although not all of them are unique. The authors chose 18 of them as the Instruction Set for the Hack.

Let's consider the instruction where zx=nx=zy=0 and ny=f=no=1 and see what the relationship is.

Since zx and nx are both unasserted, the ALU gets the x input directly.
Since zy is unasserted but ny is asserted, the ALU gets !y.
Since f is asserted we add x and !y
Since no is asserted we take the bitwise inverse of the adder's output.

The net result is that we have

!(x + !y)

Now, we know that with 2's complement we have the following relation between the additive inverse of a number and the bitwise complement

-n = !n + 1

That means that

!n = -n-1 = -(n+1)

So leveraging that knowledge, we can write our ALU output for this instruction as

!(x + !y) = !(x + -(y+1)) = !(x - y -1) = -(x - y - 1 + 1) = -(x - y) = y - x

So if we want to compute y-x, we can do so by setting the ALU control signals to these values.

I know that the numbers can be processed as input if they were already in 2s complement (specifically useful if further computations would be completed on that variable).  However from the external data entry point of view, a user would (presumably) send a positive numbers with the negate (flags) instructions to produce a product of 2 negative numbers.  Maybe this kind of math would require further processing outside the ALU?

Remember that we are talking about assembly language programs at this level. If we want to load -42 into the D register, we do that with a sequence of two instructions.

@42
D = -A

The -A instruction will set zx=nx=f=no=1 and zy=ny=0. It will also set a bit that will route the contents of the A register to the y input of the ALU (as opposed to the value stored in RAM at the address stored in the A register).

The relationship for this set of control signals is therefore

!(!0 + y) = !(!0 + A) = !(-(0+1) + A) = !(A-1) = -(A-1 + 1) = -A

I am aware of using an Xor combined with a half-adder for 2s complement, building a sub-chip for this concept is part of what set off this entire investigation for me.  The use of the full adder was the workaround (vice creating a 2s complement chip separate or other integrated methods) I was talking about.  Maybe it could be called more of a shortcut then a workaround?

Since carry operations are part of an adder, this can (and does) work under most conditions.  I would assume that under extreme high and low numbers this may fail, but haven't tested this.

That method does seems breaks down when both nx, ny instructions are set, at least with the testing I have done so far.  Assuming the goal is specifically arithmetic.

It's important to keep in mind that nx and ny are NOT flags or instructions. They are control signals that perform a very simple, specific task. If nx is 1 then the x input to the ALU is bitwise negated otherwise it is passed through unmodified. That's what it does and that is all that it does.

I really do not understand how nx,ny,f=1 (rest=0) are meant to translates to -(x+y+2) aka -x-y-2.  
I understand that this is the result, but it wasn't my intended operation?  

It's unclear to me what about this you do and what you do not understand. When you configure the control signals that way, you get the following:

!x + !y

To convert this to 2's complement arithmetic terms we have

!x + !y = -(x+1) + -(y+1) = -(x+y+2)

I understand how this condition is created (between the bitwise not and the adder), but the why when using addition this should occur is kind of the issue to me.  Shouldn't the ALU account for the difference between bitwise instructions and math operations?

The ALU can't read our minds. It takes two patterns of input bits and produces an output bit pattern according to the effects that its six control signals perform. That's all it does. WE assign meaning to the relationships between those patterns.

I would have thought that those instructions should produce = -x + (-y) = -x-y.  Is this were I am misunderstanding the operations?

Why? You are still trying to think of nx as being a flag telling the ALU that it should treat the input at its x input as the additive inverse of that value. That's NOT what nx does; ALL it does is make the ALU do a bitwise negation of the value on the x data path before sending it to both the 16-bit adder and the 16-bit AND gate.

I will have to try the x to -1234, y to -5678 test later.  I assume you mean using positive x and y, then using the nx and ny instructions?

In your test file (or in the ALU emulator running in interactive mode) you can force the x and y inputs to be whatever bit pattern you want (the same way that the test file sets one of them to -1 for some of the tests).

-1234 = b1111 1011 0010 1110
-5678 = b1110 1001 1101 0010

[Jeana]

So essentially, my mistake was thinking that the ALU was designed to be capable of adding 2 negative numbers (assuming positive initial input) in one ALU cycle.  Instead to accomplish this, auxiliary components would be needed an combination with a control unit/program.

the sequence needed would be something generally like...
operation set 1: convert first number (!A+1) to 2s complement = -A.
operation set 2: convert second number (!B+1) to 2s complement = -B.
operation set 3: then add -A and -B.

I think I have it now.  Thanks!

[WBahn]

The ALU very much IS designed to be capable of adding 2 negative numbers. Keep in mind, the ALU is a combinatorial logic circuit -- it has no clock and thus no concept of a cycle of any kind. If you apply two negative values at it's input and configure the control signals so that it performs addition, then the output will be the sum of those two negative numbers.

How you get a negative value to the ALU is a higher level task. The design of this particular CPU means that you can't embed immediate values within a C-type instruction (other than +1 and -1) and also means that you can only load 15-bit unsigned immediate values into the A register using the A-type instruction. Neither of those constraints has anything to do with the ALU.

If you look at many language specifications, including C, you will find that this is not that uncommon. All literal numeric values in a C program are positive. This is to make it easier to parse the expressions. So if you have

x = -42;

then this is a unary negation operator acting on the constant 42 with the result being stored in x.