Overflow Flag and Bit Shifting

[Nik469]

Hey all,
first of all I want to say that this is a great book. It might even be the best I've ever read about that topic. I'm neither an I T Specialist nor any other "real" technician, I'm just some lay person very interested in this topic (chip design) and am also using other resources to try to design a chip with my own twist (just for fun obv not going for much efficiency here).
I really like the ALU Design here but have two questions. Please bear in mind that as an interested lay without any practical experience in programming I am not really into that bit of the book (yet) but more diving deep into the basic design of the alu and machine coding. From other designs I know the Shift Bit function and - more important for me - the Overflow/Carry Out Flag. This is important for me as I want my ALU to be able to compute greater numbers than the actual width of my ALU would allow (I build an 8 Bit ALU bit also want to compute 16 bits for exp.). Usually I would solve this problem by splitting 16 bits into two 8 bits words and then compute the first 8 bit and carry the overflow into the next 8 bits. Or simply storing a new word when the overflow just activates (in an 8 bit scenario when adding 11111111+11111111 for example so it would store 11111110 and automatically 00000001 as a second word. Also when ADD is activated it would loop with the next register's word if Carry Out = 1 (overflow). So the size of calculated numbers would only be dependant on the RAM size and some programming.

Now that rises the following question:

Did you just ignore/not handle the overflow for simplicity's sake and the alu would just calculate "wrong" if the numbers were too big ?
Or am I missing out and this is handled by the software used in HACK, which is the part I was not diving into, please feel free to just hint me the chapter then in which this is handled,
Because for me, this overflow flag would be quite crucial, at least handling with it software wise.

Cheers everybody, have a nice day!

[WBahn]

Welcome aboard!

You ask a good question. The Hack hardware was definitely designed with simplicity in mind and therefore it has some pretty severe shortcoming compared to anything you might find in production (but probably not as severe as you might think).

As you noted, it lacks any kind of a status register that a program can query. Furthermore, the ALU lacks not only a carry-out, but also a carry-in bit for the adder. It also lacks both a shift and a rotate function. These are all operations that nearly all production chips support in hardware.

But as to whether these are "crucial" depends on the criteria used to decide what is crucial.

You probably noticed that the hardware doesn't have a multiply or divide function, either. Yet you will see when you get to the high-level Jack programming language, it supports both. These two operations are emulated in software by the operating system libraries. Quite a few of the low-end chips do not do multiplication or division in hardware, so the notion of emulating pretty basic capabilities in software is far from unheard of.

The same could be done for multi-word arithmetic on the Hack and could be implemented either at the VM level or compiler level via OS libraries. You just need to be able to be able to detect that an overflow has occurred and adjust accordingly.

It would actually be a great exercise for you to write an assembly language subroutine that adds two 32-bit values (each stored in two consecutive RAM locations) and produces a 32-bit result, again stored in two consecutive RAM locations, perhaps with a borrow/carry indicated in a third RAM location.

Think of all the possibilities, namely that either input number might be positive or negative and the result might be either positive or negative.

[Nik469]

Hi,

thanks for the quick response!
Ah thats interesting, I did not know that you would also build alu functions to mult/div, always thought these are always programmed. But now thinking about it, this would mean that in the hack example where an Integer is displayed
0vvv vvvv vvvv vvvv I could use the second most significant bit as an overflow (O) indicator right? So
0Ovv vvvv vvvv vvvv.
Another strategy that comes to mind would be to output the carry out and build a simple flag register which is called up by the code in some kind of loop (like if O=1 keep calculating the next word) would that be a better idea? Just for me to know, a flag register only stores the most recent flag, for the exact next operation to be computed, the flag is not saved into the RAM right? So I would only need to build (For HACK ALU with zr flag, ng flag and now my of flag) a 3 bit register next to the ALU which can be written, read and erased? The reading would the be done by the Program Counter to decide what to do next as far as I understand. There arises one problem though. How do I know how many words in RAM are actually one connected value? One Value could be two word another value five words and the next just one? But how does the RAM remember this? I guess I would have to handle that with some serious machine coding wouldn't I?

The other thing is how would I implement bit shifting into my ALU (you dont need to give me a fully explanation, I just dont know how to google an actual shift/rotate architecture, maybe you could tell me some Keyword(s) which could come in handy when searching.

And (sorry I seem to get annoying asking so much but its so interesting.....😵‍💫) what other ALU Functions and other ALU Flags would you use in a more complicated chip? Are there any standardised lists?

Ok, now, thats it!

Thanks again, huge help!

[WBahn]

You've got a number of questions and topics intermixed, so I don't know how much justice I will do to each of them.

Your CPU architecture can be as simple or as complex as you want -- this is at the heart of the CISC vs. RISC debate, with most real-world processors falling somewhere on the line but not really right at the end, making them a compromise of the two.

Decades ago, some microprocessors supported multiplication and division (the 8088 did) while others didn't (6502 didn't). Some microcontrollers did (the 68HC11 did) while most did not (the 8-bit PICs, for instance). For a long time, microprocessors could only do integer multiply/divide operations and floating point operations had to be done in software OR done on a separate chip known as a floating-point math coprocessor (such as the 8087).

Today, virtually all microprocessors natively support floating point math operations and can usually perform multiple such operations in parallel in one clock cycle.

So the capabilities of the hardware vary all over the place.

For shifting/rotating, they may use a barrel shifter to perform shifts/rotates in either direction by an arbitrary amount in a single instruction cycle.

On the HACK, if you need to do these (which are useful for multiply/divide routines), you can leverage the fact that multiplying the value in a register by two has the same effect as left shifting it one bit, and that adding a value to itself is they same as multiplying it by two. Right shifting is a lot more involved on the Hack.

While you could have a separate register for your status flags, the question then becomes how does your program access them. For instance, your programs on the Hack can't access the ng or zr flags that the CPU already has. The easiest way to remedy this is to place them into a register at a specific RAM location. You can make some (or all) of the bits read-only if you wanted to.

As for knowing how many words make up a value, that is defined by the protocol you come up with. You basically spell out how this is done. The simplest way is to define new data types, such as long int, to be specific widths, such as 32 bits. You also have to define the endianness of them.

[Nik469]

Thank you so much for the insight!

Especially the multiplication part - I knew this but always thought it the other way around so you just gave me an "aha!"!

I really start to dig more into that (chipdesign/logic design and assembly) topic, are there other beginner friendly books you could suggest that focus on ALU/CPU and Memory designs?

Cheers!