# Bitstuff

For people interested in how computers work bottom-up.

## Friday, February 09, 2007

### Subtract and Branch if Negative

I got pretty bored over winter break, and decided I needed a project to keep me busy until class started. Well, there was one thing that I've been wanting to do for a long time. I have wanted to build a simple computer out of 7400 series logic chips. I only had about a week for the whole project, so the design had to be pretty spartan. I also wanted to use chips that I had on hand, though that didn't last for too long.

After thinking up a few different ideas, I finally remembered another project that I've been wanting to do: build a Subtract and Branch if Negative computer. That is, a computer whose only instruction is to subtract two numbers, store the result, and branch to an alternative memory location if the result is negative. This is very much like SBN on wikipedia.

If you don't care to look at the Wikipedia page, the subtract and branch if negative instruction turns out to be the only instruction you need to build a turing-complete computer. That is, this one instruction, given enough time and memory, can compute anything that a regular computer can. Of course, it's slow, inefficient, and a pain to program.

So I went about designing a simple microcomputer based on this instruction. First step, I needed to decide on some basic specifications for the processor:

Data Width: 8-Bits
Instruction Set: Subtract and Branch if Negative

After that, I could rough out a block diagram of the dataflow. Using the dataflow as a guide, I figured out what chips I could use in what blocks, how many I would need and how they connect to each other.

The dataflow was the easy part. More difficult is designing the control logic, which was going to be especially complicated because of the 8 and 16 bit busses. This is because it now requires two cycles to read in the address of an operand, and another cycle to read in the value of the operand. This needs to be done once for both operands, and then again when we need to load the new PC value if the instruction takes the branch.

The control sequence for the processor goes something like this:
7. Store ALU Result; PC++
9. If (ALU Result is negative) {Load PC}
A pretty reasonable way to encode the control logic would be to program the control signals into an EEPROM. This is very simple and is easier to change if there is a bug. However, I had never used EEPROMs before, so I decided to build a state machine out of 7400 series logic. It's a bit of a mess, and there were a few bugs to squash, but it works.

So we have the control and the dataflow...what else? Input and output. There needs to be a way to load programs onto the device, and then a method of interacting with the running program.

I had initially thought about using a series of switches for loading programs into RAM. That was going to be incredibly tedious and time consuming, so I scratched that. Instead, I did some research on the Parallel port, and found it to be the perfect solution. It's easy to interface, easy to program and completely automated. This only required a few extra chips to interface the parallel port to the system bus on the microcomputer. Basically, it needs to be able to take control of the bus when it needs to program, and relinquish control when it's done.

Last bit of hardware, the human machine interface. I have to admit, it's pretty craptacular on this microcomputer. An 8-bit dipswitch and an 8-LED bargraph are all the I/O you get. However, this fits in with the overall strategy of making somewhat rediculous design decisions. There is however, at least one neat trick that can be done to expand the output capabilities.

The fabrication of this computer is another story. I had hoped I would be able to build it on a printed circuit board, that would have been wonderful. However, I had too many chips for the free version of Eagle CAD I had. Simply would not fit on the board. So I decided to use a pre-drilled perferated board with solder pads. Good enough, but wiring ended up taking most of the week. Luckily for you, you don't have to wait to see the finished product. The final stage of the microcomputer has two boards. The bottom board has the processor, memory, power supply and clock generator. The top board holds the batteries, has some blinky lights, dip switch and some simple address decode logic for memory-mapped IO.

To wire up all the parts, I used a lot of wire-wrap wire, solder and a wire-wrap tool. The leads on the parts were very short, so wire-wrapping was a real pain, but it seemed to be the best way to get the leads into place for soldering. It was slow going and took about four very full days to finish. On top of that, I had to test and debug different parts as I finished them. It can make you pretty nervous when you have to desolder several connections on one IC to make a fix.

If I do another 7400 series-based microcomputer, I will get a proper wire-wrap board.

Now that the darn thing is built, what to do? The work's not done yet. After building and debugging it, I still needed to be able to write, assemble and load programs. I needed to write an assembler and program loader.

The program loader actually turned out to be the easiest part of the whole project. Programming the parallel port on Linux was much easier than I expected. In fact, the loader program only had one bug in it the first time I tried it. Made the fix, tried it again, worked!

Now that I could load any data I wanted into the microcomputer's memory, I needed an easier way to program it. This meant developing a simple two-pass assembler. On top of that, I wanted it to have some built-in pseudo operations, so I could program and still keep my sanity. Programming this device with only using the low-level subtract and branch if negative instruction is not my cup of tea.

Eventually I hacked out a simple assembler that fit the bill. The assembly code looks like this:

sub i, imm(-10)
loop:
dec i
bltz i, loop

This little snippet is a simple loop. It subtracts -10 from i (which it assumes to be 0), setting up the number of iterations. Each iteration it decrements the loop index, and continues to loop as long as "i" is greater than or equal to zero.

Each instruction in that snippet is a pseudo-operation that is converted into SBN instructions by the assembler. Furthermore, each of those pseudo-ops can be converted into exactly one SBN instruction.

The "imm(-10)" bit of code allows me to operate with immediate values in my code. All it does is return the address of the value"-10" on the constant table. These keeps me from having to allocate a memory location for each constant I use in my code.

I now have everything I need to write a demo program. I wanted the microcomputer to do something unexpected. Something you wouldn't think it would be able to do. I think the most limiting part of it is it's input and output. I decided the demo would be an output-only program. This leaves me with eight blinky lights to do something cool with.

So, the most unexpected thing to do, would be to project an image with those eight lights. That's my thought anyways. I was set on displaying a smiley face using just those lights. How, you might ask, can that be done? Using persistance of vision.

If you've ever looked at a flashlight in the dark, you've probably noticed that it seems to leave a trail when you look at it. If you spin it in a circle fast enough, you might see a circle of light, neato. The idea behind displaying a smiley face on the eight lights is the same. If I move the lights, or use a mirror to move them, your eyes will see a trail marking where that light has been in your field of vision. If we setup a regular motion of a mirror, and display one line of the image at a time, we can display an entire 2D image using one line of eight lights.

So that's what I did. The program outputs one line of the desired image, blanks the lights for a split second, the next line is lit up, and so on. I took a picture of the effect with my camera. I don't have any mirrors yet, so I just panned the camera across the lights in the dark, it worked out really well. To show other people, I can just shake the lights up and down. Eventually, I would like to get a small mirror, motor and switch for synchronization. That seems a bit safer than shaking the fragile computer.

In the end what I got is an 8-Bit computer with one instruction, 32 KB of RAM and a clock speed of 250KHz. Though it takes nine cycles to execute one instruction, so in reality, it's executing about 28,000 instructions per second.

Unknown said...

This comment has been removed by the author.

12:22 AM
Unknown said...

I simply don't know what to say.... besides.... most impressive

12:24 AM
ozamosi said...

*drewl* I want one!

One question: is there any way to get the schematics and/or the software (assembler and parallell port communication software)?

5:54 AM
Luke Valenty said...

The schematics are written in colored pencil on several sheets of paper. So it may take a bit of work to get those into order.

The source code is easier, and I'll find a way to post it.

6:01 PM
XANi said...

Very impressive :D
Build 32 version and run linux on it ;]

10:47 AM
John Metcalf said...

This looks like a fantastic project, I'd be interested in seeing the schematics.

I'd love to try something similar which can communicate back to the PC over the parallel port.

6:18 AM
NPolynomial said...

Very cool! I once built a brainfuck processor using TTL chips.

I'm looking forward to building new architectures someday and have been considering the OISC for a while now...

http://novaconceptions.blogspot.com

2:31 PM
NPolynomial said...

Well, I don't know how to follow your blog, would you be interested in a link swap with me? We seem to write about similar subjects and we have the same layout background.

Take care,

Jesse

2:34 PM
Anonymous said...

8:09 PM
走吧 said...

6:35 AM
Anonymous said...

nice job! waiting for your new artical. ........................................

1:38 AM
Anonymous said...

4:14 AM
Anonymous said...
4:29 PM
Anonymous said...

9:35 PM
Anonymous said...
11:04 AM
Anonymous said...
11:04 AM
Anonymous said...

1:26 AM
Anonymous said...

2:40 AM
Anonymous said...

6:30 PM
Anonymous said...
1:02 PM
昭彥 said...
1:40 AM
Anonymous said...
9:38 AM
建銘建銘 said...

10:13 PM
Dorath政儒yN_ said...

A liar is not believed when he speaks the truth...................................................

5:09 AM
saa said...
9:46 PM
Anonymous said...

4:35 PM
林奕廷 said...

5:29 PM
Anonymous said...

Pen and ink is wits plough. .................................................................

7:26 AM
Anonymous said...

7:26 AM
Anonymous said...
8:16 PM
Anonymous said...

6:27 AM
Anonymous said...
2:20 AM
Anonymous said...
8:51 AM
Anonymous said...

11:23 AM
Anonymous said...
9:08 PM
Anonymous said...

3:40 AM
Anonymous said...

Poverty tries friends.............................................................

7:12 PM
Anonymous said...

Share and share alike.............................................................

8:54 AM
Anonymous said...

i consder your artical is so nice!............................................................

2:47 AM
Anonymous said...

11:23 PM
淑李娟 said...

2:00 AM
Anonymous said...

2:00 AM
黃怡張華樺張華樺妹 said...

More haste, less speed..................................................................

4:50 AM
Anonymous said...
12:21 AM
Anonymous said...

Poverty tries friends...................................................................

8:01 PM
Anonymous said...

3:33 AM
Anonymous said...

4:36 PM
Anonymous said...

4:36 PM
Anonymous said...

6:47 PM
江仁趙雲虹昆 said...

10:19 PM
建枫 said...

4:27 AM
Anonymous said...

It is no use crying over spilt milk.......................................................................

7:34 PM
Unknown said...

Aw man, I wanted to build something like this for a while... This is amazing :-°. I will definitely give it a go as soon as I am settled.

Cheers

2:52 AM
alkopop79 said...

Amazing job!

6:05 PM
Will Gilreath said...

Hello Luke, (sorry for length...couldn't find e-mail address for you...)

I was searching the web for material relating to the search keywords of “one instruction computer” or “single instruction computer” (ultimate RISC, minimal instruction set) and found your website with a one-instruction computer that you had developed and explored--very interesting and impressive.

I’m curious about what caught your interest in the concept of a one-instruction computer? And, if you have done further work on the project/concept?

My message/questions are of mutual interest in the notion of one-instruction computers. I am William Gilreath, the lead author of a computer architecture book that explored much of the history, background, and concepts of one-instruction computers. The book is “Computer Architecture: A Minimalist Perspective” published in 2003, and there is a website about the book at http://www.caamp.info.

One possibility I am considering is a webpage on the CAAMP website with third-party implementations and projects. If you have no objection, I’d like to link to your project webpage. If you do not want that, all is well (or more simply, “that’s cool, no harm, no foul”, but if you do, that’d be great.

Thanks, my best, and keep up the good work on your webpage about OISC.

William Gilreath
http://www.williamgilreath.com

9:47 PM
ペンギン said...

*通販しますご注文を期待しています
*全物品運賃無料(日本全国)
http://www.txewatch777.com/ ブランドコピー
http://www.txewatch777.com/Tree-c632.html ルイヴィトンスーパーコピー
http://www.txewatch777.com/Tree-c644.html エルメス スーパーコピー
http://www.txewatch777.com/Tree-c662.html スーパーコピーシャネル
http://www.txewatch777.com/Tree-c748.html ヴィトン 財布 コピー
http://www.txewatch777.com/Tree-c753.html グッチ 財布 コピー
http://www.txewatch777.com/Tree-c688.html ウブロ スーパーコピー
http://www.txewatch777.com/Tree-c835.html パテックフィリップスーパーコピー
http://www.txewatch777.com/Tree-c691.html ブライトリングコピー

3:25 AM
Unknown said...

スーパーコピー 代引きN品をご 購入の方は、こちらへ
.弊社は正規品と同等品質のコピー品を低価で お客様に提供します!
すべての商品は品質2年無料保証です。100%実物写真ですし、品質が完璧です!"
ブランド財布偽物財布コピー ルイヴィトン財布偽物

スーパーコピー腕時計は他社のものより品質がよくて、価格も安いです
http://www.niewatch777.net/category-51-b0.html ウブロスーパーコピー
http://www.niewatch777.net/category-10-b0.html パネライスーパーコピー
http://www.niewatch777.net/category-84-b0.html カルティエスーパーコピー
http://www.niewatch777.net/ スーパーコピー時計

11:34 PM
Niketan jha said...

Awesome project brother :)

8:29 AM
Targeted Web Traffic said...

State targeted USA website traffic is a powerful element to any business development strategic plan. Whether it’s state or country-specific traffic you are looking for, we can help! If you’ve never tried Targeted Web Traffic to help you achieve business results, what are you waiting for? Ask us today how buying targeted US.

11:29 AM
Rina Stewart said...

I wanted to build something like this for a while... This is amazing!
The Online

8:47 PM
Top New BIZ Idea said...

https://www.targetedwebtraffic.com - Don't let your business be judged based on a poor Alexa ranking. Even if you are starting from zero, Targeted Web Traffic can help you quickly and safely increase your score! ,