Yesterday we were leaving Lucky (a supermarket) in downtown Hayward. Ahead in the parking lot, right next to our car, a delivery truck began backing out while a group of teenagers was walking behind it. They started waving their hands, slamming on the sides of the truck to get the driver to stop but he kept backing out. The running board hit one of the boys in the shin and he fell over. The driver continued backing up as the fallen boy scrambled away, and the others ran around to the front of the the truck trying to get him to stop.
The driver finally stopped, sticking partway out into the lot and blocking our car in. At least four other people watched it happen, and they just went to their cars or into the stores and didn't want to get involved. We stood by to make sure the boys had support from witnesses.
At first the scene was just commotion; the boys understandably were riled up, yelling threats of lawsuits and arrest, filming with their cell phones, taking the license plate number etc.
Then the driver started to back out again!
This guy hit a minor pedestrian with a commercial truck and was going to leave the scene before any officials arrived. He backed all the way out to the point where he could start driving forward. I stepped in front of the truck and put my body against it as he inched forward. He stopped when I looked in his eyes and pulled out my phone to call 911. The boys started swarming the truck, some joining me in front or going to the back to block his exit, some climbing on the cab roof, etc.
I told the dispatcher that I was witnessing a hit-and-run in progress, and that we were preventing him from leaving. I gave her my details, the location, etc. and said she was sending some officers.
The driver sat there with the engine running, blocking the main lane of traffic in the lot. A woman leaving the store complained about her car being blocked in. By this time some of the angst had died down, and my wife suggested we get him to pull back into his original spot.
We all started to gesture as such, asking him to park again, backing off the front of the truck to give him some room. My wife went up to the driver's window and asked him directly a few times. Eventually we saw him put the truck into gear and he parked, though he left the engine running. The boys sat down on the back of the truck, and a minute or two later the Lucky manager came out.
He started asking us the usual from those of us at the back of the truck: contact info, what happened, whether we had already called the police. While we were talking with the manager, the driver finally turned off the engine and stepped out.
When the manager talked to the driver, things turned towards the surreal. We overheard the driver saying something like "they got hit on purpose to get money," blaming them even though he tried to flee the scene. The manager came back and started asking once more about whether we had called the police, and said that he had as well, but that since it was private property they might not come. He asked if the boys were injured, and said that it would be really bad for the driver if the police came.
In near unison, the teenagers, my wife, and I screamed "WHAAT?!!" followed by individual variations of "Are you fucking kidding me? It's going to be bad for HIM? What about the fact that he just hit a pedestrian and tried to leave the scene? He should be arrested!"
By this point it had been about 10 minutes since I called 911, and with the manager seeming to advocate for the driver, I called the non-emergency police number to check on the status of our call. She asked "aren't they on scene already?" I said no, but started looking around and saw a police car at the corner waiting to turn right.
Two cars showed up at first. The officers took down my info and account, then one talked to the boys and the other went around to talk to the driver. As another police car arrived, I overheard the officer say to the driver something like "this wouldn't be so bad for you if you had a license."
In the hopes of planting as few assumptions as possible, I have intentionally omitted any mention of race. But at this point, I can't just say "Everything calmed down for no apparent reason when the third officer arrived." The manager was latino, as was the driver of the truck. The first two officers were white, as were we. The third officer was black, as were the kids.
Most of the people on the scene noticeably relaxed when he arrived, and various mental circuits that had been shut down in preparation for fight/flight started to fire back up again.
With our accounts provided to the police and no longer feeling like we were the only ones around who could offer these boys any hope, I realized we were all standing outside in the acrid smoke funneling down from the fires up north. My wife and I had just bought some breathing masks from the hardware store nearby, and figuring that the police would be taking statements for a bit, I went back to buy a few packs for everyone. As I was leaving the store, the boys were walking away from the scene, so I handed them the masks and wished them a good one.
When I got back to the car, my wife was there holding our dog as the police dispersed and the driver started to leave. Since there were no serious injuries, the police made him report the incident to his company and let him leave without arrest. At one point while I was gone, my wife said one of the white officers asked something like "Well who do you think will win you or the truck?" mirroring the victim blaming of the manager. This just added further insult to injury.
We sat there for a while reflecting on what happened. There is a lot to feel ambivalent over. When the incident first occurred, the truck was moving slowly enough that the kids might have been able to avoid being hit, but that's a matter for the police/insurance to sort out. When the driver tried to flee there was no doubt that we needed to stay to support the kids.
When I left to buy the masks, my wife felt helpless in the face of the victim blaming attitude of the cops, but I could see the boys appreciated the gesture. In addition to the victim blaming, the police also treated her with less credibility than me or than when I was around.
Earlier we were gung ho! "He should be arrested for hit and run." But at the end of the day, I'm glad he wasn't. When I looked into his eyes I saw no malice, only fear.
Rants and Ravings from Cogwheel’s Workshop
Thursday, October 12, 2017
Thursday, June 22, 2017
TTL Brainfuck Computer Part 8 - Clocking Progress
Part 1 (first) - Part 7 (prev) - Part 9 (next)
Note: there are plenty of pretty pictures below the fold
My pie-in-the-sky goal for the clock speed of this computer was originally 10 MHz. The LS series chips should be capable of 16 MHz, but that's not accounting for the poorly engineered environment of a hobbyist's breadboard computer. I figured 10 MHz would offer enough head room for the chips to cope.
As it turns out, the limiting factor is the EEPROM, which takes 150ns for the data to be valid after changing the address. If I set the address on the rising edge of the clock and read the data on the falling edge, that would be a period of 300ns or a frequency of 3⅓ MHz. While that's only one third of my original goal, it's well within the range of early personal computers (not that the performance will be remotely comparable).
So now I actually have a realistic target frequency, which likely can be pushed a dozen or two percentage points beyond spec (hello, overclocking!). Unfortunately the trusty 555 just isn't up to the task.
First of all, most sources I've read say it's only good up to about 1 MHz. But as an easily adjustable variable frequency (i.e. a single dial), the range and resolution are extremely limited.
I'm using a 1 M potentiometer right now. In order to have a usable range between, say, 0.5 Hz and 32 KHz, I have to manually switch from a 10 μF capacitor to a 10 nF. I'd need to go down another two orders of magnitude on the capacitor or up two on the resistor to reach 3⅓ MHz, and as I mentioned earlier, that would push the 555 well beyond its limits.
The adjustment resolution is similarly frustrating. Even though the potentiometer changes resistance linearly, the effect on clock rate highly non-linear. At the low speed end of the dial, a tiny movement makes a large difference in the clock speed. At the high speed end, the duty cycle changes more than the frequency.
Note: there are plenty of pretty pictures below the fold
My pie-in-the-sky goal for the clock speed of this computer was originally 10 MHz. The LS series chips should be capable of 16 MHz, but that's not accounting for the poorly engineered environment of a hobbyist's breadboard computer. I figured 10 MHz would offer enough head room for the chips to cope.
As it turns out, the limiting factor is the EEPROM, which takes 150ns for the data to be valid after changing the address. If I set the address on the rising edge of the clock and read the data on the falling edge, that would be a period of 300ns or a frequency of 3⅓ MHz. While that's only one third of my original goal, it's well within the range of early personal computers (not that the performance will be remotely comparable).
So now I actually have a realistic target frequency, which likely can be pushed a dozen or two percentage points beyond spec (hello, overclocking!). Unfortunately the trusty 555 just isn't up to the task.
First of all, most sources I've read say it's only good up to about 1 MHz. But as an easily adjustable variable frequency (i.e. a single dial), the range and resolution are extremely limited.
I'm using a 1 M potentiometer right now. In order to have a usable range between, say, 0.5 Hz and 32 KHz, I have to manually switch from a 10 μF capacitor to a 10 nF. I'd need to go down another two orders of magnitude on the capacitor or up two on the resistor to reach 3⅓ MHz, and as I mentioned earlier, that would push the 555 well beyond its limits.
The adjustment resolution is similarly frustrating. Even though the potentiometer changes resistance linearly, the effect on clock rate highly non-linear. At the low speed end of the dial, a tiny movement makes a large difference in the clock speed. At the high speed end, the duty cycle changes more than the frequency.
Duty Dilligence
Speaking of the duty cycle, in order to keep the time spent on as close as possible to the time spent off, the capacitors and resistors need to be in particular ratios. To get a variable 555 timer with an even duty cycle, you would need both a potentiometer and a variable capacitor, each with an abnormally wide range.
As I mentioned in a previous post, the uneven duty cycle means the chips had to respond as if the clock was around 600-700 KHz even though the clock period was only 32 KHz. If I had a 3⅓ MHz clock with an 88% duty cycle, the chips would be seeing a pulse 18ns wide, which is equivalent to ~28 MHz with a 50% duty cycle.
As a quick fix for the duty cycle issue, I switched the inverter on the clock for a 74LS73, using one of the J/K flip-flops in toggle mode as a single-bit counter. Since it changes with each pulse rather than at each clock edge, its output will have a duty cycle as even as the 555's period. However, the period of the flip-flop's output will be half that of the 555, so I replaced the 10 nF capacitor with a 4.7 nF to maintain the frequency range I was used to.
The blue line on the oscilloscope is the output of the 555 timer. You can see how it spends significantly more time on (up) than off (down). The yellow line is the output of the flip-flop. You can see how it rises or falls every time the clock signal falls. Since I'm using a "raw" flip-flop instead of a counter chip, I have access to both the Q and Q' outputs to use as clock and inverted clock. The white and yellow LEDs are connected to them, respectively.
The Crystal Method
One of my first toy projects when I got back into electronics was a slowly shifting RGB mood light on Arduino. The LED itself is on a tiny breadboard and attached to the arduino with 3 signals and ground. I wanted to put the code on an ATTiny on the same board as the LED for a truly minimalist design. The ATTiny requires an external crystal to run at full speed, so I got a crystal assortment from 4 MHz to 25 MHz. I haven't made much progress on that project, but I do have everything I need for a stable, high frequency clock for the BFCPU.
The metal can on the left is an 8.000 MHz crystal. When it's resonating, it generates a near sine wave at that frequency, but it doesn't provide much current. The nearest chip is a 74HC04 hex inverter. As a CMOS chip, its inputs respond to voltage rather than current, but its outputs can provide a wide range of current. This allows it to act as a gateway between the crystal and the TTL chips. Since the output of the first inverter is part of the crystal feedback circuit, it runs through another inverter to actually provide the 8 MHz clock signal for the rest of the system.
The other chips on the board are all 74LS93s, the ripple-carry cousins of the '193 counters that make up most of the computer so far. These act as frequency dividers, giving me a selectable clock speed for any power of ½ of 8.000 MHz (4 MHz, 2 MHz, 1 MHz, 500 KHz, etc.), down to 0.4768 Hz, or about one cycle every two seconds. I'm only interested in a single "bit" at a time, so the ripple carry isn't going to be an issue.
The two 22 pF capacitors on the left corner of the board are part of the crystal resonator. The bypass capacitors straddling the high frequency chips from near to far are 1 nF, 4.7 nF, 10 nF, and 47nF, chosen experimentally to minimize noise on the outputs. There are also a couple of 100 nF capacitors across the power rails closer to the low frequency chips for the same purpose.
With nothing attached to the clock I was getting some pretty significant ringing in the outputs, sometimes as much as +6 V to -1.5 V peak-to-peak. It turned out to mostly be inductance from the oscilloscope probes, and pretty much disappeared when the clock was attached to other parts of the circuit.
In this shot, the long yellow lead on the left is connected to the 8 MHz output of the CMOS chip, and into the count enable circuitry of the Data Pointer and Data Register. The blue lead/oscilloscope probe is connected to the same signal.
The Data Pointer is set to count down, as you can see by the red lead going to Vcc just to the left of the blue LEDs. The yellow oscilloscope probe at the top is connected to the low order bit of the Data Pointer, which should be changing at half the period of the clock. Here's the result:
The scope is triggering on the clock signal, and you can see the measurement of 8.00029 MHz in the lower right. As expected, the first counter stage is flipping with every pulse. The edges don't quite line up because of the propagation delay in the counters and the NAND gates combining the clock with the control lines. If I had measured the clock at the counter input, the edges would be much closer. I left this running for an hour or so with "infinite persistence" and there wasn't a single glitch. So far so good for pushing the limits of my components!
One interesting thing to note is that TTL considers anything above 2 V to be a high signal. You can see here that the counter's output reaches just above 3 V, with a slight peak before switching. At lower frequencies, the voltage has some time to build further due to capacitive effects, and generally tops out around 4-4.5 V. You can see the effect of this in the previous image, where the 3 left-most LEDs are noticeably dimmer than the rest. The second bit from the left is the one switching the fastest, and is also the dimmest. You can see the same effect when I enable counting on the data register:
This isn't just an artifact of the camera or variability in LED quality or resistor value (which is also noticeable). If the switching speed were instantaneous, the LED would be spending just as much time on as it is off, so the only reason the brightness would be different is if the amount of current flowing is different. Since the resistance of the LED (plus resistor) is essentially fixed, the only way the current can be different is if the voltage is different.
Switching speed is not instantaneous, and doesn't change very much with clock speed. At high frequencies, instead of 50% on 50% off, it's more like 40% on, 40% off, 20% somewhere in the middle. This amplifies the effect of the already lower voltage.
The Data Pointer's up/down signals are now connected to the clock and control lines via NAND gates, just like the Data Register. The only buttons left are Clear signals. The Data Pointer doesn't ever load data, the load lines are all tied high.
In a couple of the pictures above you can see the beginnings of the program side. From top to bottom is the Stack Pointer, Stack RAM, Program Pointer, and Program ROM. I'm in the process of wiring up the Program Pointer to the Program ROM.
The milestone I'm shooting for next is to have a program in ROM control the Data Pointer and Data Register counters. But first I need to work the new clock design into the computer.
Part 1 (first) - Part 7 (prev) - Part 9 (next)
The other chips on the board are all 74LS93s, the ripple-carry cousins of the '193 counters that make up most of the computer so far. These act as frequency dividers, giving me a selectable clock speed for any power of ½ of 8.000 MHz (4 MHz, 2 MHz, 1 MHz, 500 KHz, etc.), down to 0.4768 Hz, or about one cycle every two seconds. I'm only interested in a single "bit" at a time, so the ripple carry isn't going to be an issue.
The two 22 pF capacitors on the left corner of the board are part of the crystal resonator. The bypass capacitors straddling the high frequency chips from near to far are 1 nF, 4.7 nF, 10 nF, and 47nF, chosen experimentally to minimize noise on the outputs. There are also a couple of 100 nF capacitors across the power rails closer to the low frequency chips for the same purpose.
With nothing attached to the clock I was getting some pretty significant ringing in the outputs, sometimes as much as +6 V to -1.5 V peak-to-peak. It turned out to mostly be inductance from the oscilloscope probes, and pretty much disappeared when the clock was attached to other parts of the circuit.
 |
| Poor 555 clock, blinking away in solitude back there |
In this shot, the long yellow lead on the left is connected to the 8 MHz output of the CMOS chip, and into the count enable circuitry of the Data Pointer and Data Register. The blue lead/oscilloscope probe is connected to the same signal.
The Data Pointer is set to count down, as you can see by the red lead going to Vcc just to the left of the blue LEDs. The yellow oscilloscope probe at the top is connected to the low order bit of the Data Pointer, which should be changing at half the period of the clock. Here's the result:
The scope is triggering on the clock signal, and you can see the measurement of 8.00029 MHz in the lower right. As expected, the first counter stage is flipping with every pulse. The edges don't quite line up because of the propagation delay in the counters and the NAND gates combining the clock with the control lines. If I had measured the clock at the counter input, the edges would be much closer. I left this running for an hour or so with "infinite persistence" and there wasn't a single glitch. So far so good for pushing the limits of my components!
One interesting thing to note is that TTL considers anything above 2 V to be a high signal. You can see here that the counter's output reaches just above 3 V, with a slight peak before switching. At lower frequencies, the voltage has some time to build further due to capacitive effects, and generally tops out around 4-4.5 V. You can see the effect of this in the previous image, where the 3 left-most LEDs are noticeably dimmer than the rest. The second bit from the left is the one switching the fastest, and is also the dimmest. You can see the same effect when I enable counting on the data register:
Switching speed is not instantaneous, and doesn't change very much with clock speed. At high frequencies, instead of 50% on 50% off, it's more like 40% on, 40% off, 20% somewhere in the middle. This amplifies the effect of the already lower voltage.
Other Updates and Plans
The Data Pointer's up/down signals are now connected to the clock and control lines via NAND gates, just like the Data Register. The only buttons left are Clear signals. The Data Pointer doesn't ever load data, the load lines are all tied high.
In a couple of the pictures above you can see the beginnings of the program side. From top to bottom is the Stack Pointer, Stack RAM, Program Pointer, and Program ROM. I'm in the process of wiring up the Program Pointer to the Program ROM.
The milestone I'm shooting for next is to have a program in ROM control the Data Pointer and Data Register counters. But first I need to work the new clock design into the computer.
Part 1 (first) - Part 7 (prev) - Part 9 (next)
Wednesday, June 21, 2017
Complaint Breadboard
As much as I have ranted over the first breadboards I used for my Brainfuck computer, the company behind them has tried to help. After I left a one-star review on Amazon, they admitted that their manufacturing quality varied and sent me new ones. They were indeed a bit better than the first ones in a few specific ways, so I bumped my review up to three stars.
Over time, the experience was more unpleasant than first impressions suggested. They couldn't compete with a few other cheap breadboards I've acquired over the years. I won't list my grievances again here, but I decided to go back to a one-star review.
Earlier this month they sent me an e-mail saying:
The cynic in me thinks they mean "we found another supplier" when they say "we have developed", but I can't complain about the effort they're putting into making me a satisfied customer. I'm also a sucker for friendly emoji. :)
After bouncing back and forth between USPS facilities in San Francisco and Oakland for a week, they arrived a couple days ago. Whether the cynic in me turns out to be right or not, these new ones are vastly improved over the originals.
Two things are obvious at first glance: the plastic is much higher quality, both in look and feel, and the silk-screening is clearer. On closer inspection, there seems to be much more consistency in the way the contacts line up with the holes.
Here is a close up of the old board. You can see several areas where the contacts are directly under the holes. This would block entry of pins unless you put them in at an angle, which might go off to the side of the clip rather than into the center.
And here is one of the new ones for comparison:
One thing you might notice is that the contacts are much more visible in the new board when looking at an angle. You can see the bright spots on the left side of the holes on the left part of the board but on the right side of the holes on the right side of the board. This shows both that the contacts are more centered with respect to the holes and that they are closer to the surface of the breadboard.
Combined, these two fixes should alleviate most of the problems I had with the old ones. Insertion of components with multiple pins is much less frustrating, and retention of components is much better. In particular, these new boards seem to hold onto my DIP and tactile switches just as well as the Jameco boards.
The new boards also lay much flatter. The old ones had a noticeable curve out of the box, so they would tend to stretch and strain when assembled into a large panel. Here's a video demonstrating the improvements in curvature. Note: I'm using the one old Elegoo board that remained completely intact (I didn't cut the power strip off) to give it the best chances.
To be fair, there are still some problems with consistency. One of the three boards I received has a power rail where one contact in each block of 5 holes is misaligned:
I have not yet done any serious testing of their electrical characteristics since I'm not planning to assemble these into another computer. The contacts don't feel quite as eager to grip as the Jameco ones, so your mileage may vary.
All in all, I'm actually quite glad to have these three new boards. I had been using some of the old ones for a couple side projects, and am eager to transfer them over.
All in all I'm happy with their performance. While the power connections feel a bit looser than the Jameco boards, the electrical contact seems pretty stable. The board has no problem handling an 8 MHz crystal clock with a 24 stage (6x4 bit counter) TTL frequency divider. There is virtually no noticeable effect on the clock outputs when I jiggle the power leads coming into or jumping across the board. I'm not sure how they'd behave in the bus strip/massive board configuration I'm using for the computer, but so far they look promising.
Over time, the experience was more unpleasant than first impressions suggested. They couldn't compete with a few other cheap breadboards I've acquired over the years. I won't list my grievances again here, but I decided to go back to a one-star review.
 |
| Pile of |
Sorry to disturb you again.
I read from your review that you were dissatisfied with our breadboard. We sincerely apologize for that and we took your comment very seriously. After strict tests, we have developed a new breadboard which is of better quality. We have sent out 3 new breadboards to your address via China Post which will take about 15-20 days to deliver . The tracking number is [REDACTED] and you can track it here: https://www.17track.net/en ^.^
We care very much about how you feel and your review means everything to us. So we’d really appreciate it if you could give us an update review based on the new breadboard and our service. ^.^
Once again I apologize for all the inconvenience caused in this case and I look forward to your reply. Thank you very much!!
The cynic in me thinks they mean "we found another supplier" when they say "we have developed", but I can't complain about the effort they're putting into making me a satisfied customer. I'm also a sucker for friendly emoji. :)
After bouncing back and forth between USPS facilities in San Francisco and Oakland for a week, they arrived a couple days ago. Whether the cynic in me turns out to be right or not, these new ones are vastly improved over the originals.
 |
| Bottom: old Elegoo board. Middle: new Elegoo board. Top: corner of my Brainfuck Computer built with Jameco boards |
Here is a close up of the old board. You can see several areas where the contacts are directly under the holes. This would block entry of pins unless you put them in at an angle, which might go off to the side of the clip rather than into the center.
And here is one of the new ones for comparison:
One thing you might notice is that the contacts are much more visible in the new board when looking at an angle. You can see the bright spots on the left side of the holes on the left part of the board but on the right side of the holes on the right side of the board. This shows both that the contacts are more centered with respect to the holes and that they are closer to the surface of the breadboard.
Combined, these two fixes should alleviate most of the problems I had with the old ones. Insertion of components with multiple pins is much less frustrating, and retention of components is much better. In particular, these new boards seem to hold onto my DIP and tactile switches just as well as the Jameco boards.
The new boards also lay much flatter. The old ones had a noticeable curve out of the box, so they would tend to stretch and strain when assembled into a large panel. Here's a video demonstrating the improvements in curvature. Note: I'm using the one old Elegoo board that remained completely intact (I didn't cut the power strip off) to give it the best chances.
To be fair, there are still some problems with consistency. One of the three boards I received has a power rail where one contact in each block of 5 holes is misaligned:
I have not yet done any serious testing of their electrical characteristics since I'm not planning to assemble these into another computer. The contacts don't feel quite as eager to grip as the Jameco ones, so your mileage may vary.
All in all, I'm actually quite glad to have these three new boards. I had been using some of the old ones for a couple side projects, and am eager to transfer them over.
Update 2017-06-22:
All in all I'm happy with their performance. While the power connections feel a bit looser than the Jameco boards, the electrical contact seems pretty stable. The board has no problem handling an 8 MHz crystal clock with a 24 stage (6x4 bit counter) TTL frequency divider. There is virtually no noticeable effect on the clock outputs when I jiggle the power leads coming into or jumping across the board. I'm not sure how they'd behave in the bus strip/massive board configuration I'm using for the computer, but so far they look promising.
Wednesday, June 14, 2017
TTL Brainfuck Computer Part 7 - EEPROM woes
 |
| Arduino Mega2560 connected to EEPROM |
Alas, I still was unable to get any successful data writes onto the chip. I decided to try moving it over to a breadboard with some dip switches for addressing. The address pins are pulled down through 100K resistors, and the other side of the switch is pulled up through 10K resistors. These values should work fine since this is a CMOS chip and I'm not after super fast speeds. They just need to act as a voltage divider not a current source/sink, and I have verified that the voltages are around 4.5 for the high level and 0.3 for the low level.
The I/O pins are connected to one of my LED modules to show the output of the ROM, and to an 8-bit dip switch for entering data. The output enable and chip enable pins are the blue & yellow jumper wires, respectively, which I manually connect to ground or Vdd.
The load signal is connected to the common pole of a DPST switch (tucked above the LEDs next to the ROM), with the normally closed position connected to Vdd and normally open connected to ground.
 |
| Manual EEPROM reader/writer after some fixes |
The pinout for the EEPROM identical to the RAM chips I'm using (the difference in address line numbers should be immaterial). According to the data sheet, doing a single byte write should have the same steps, as well: Disable output (set OE high), enable the chip (set CE low), and pulse the the Load input low. When the load input goes low, the address is latched; when the load input goes high again, the data is latched.
The main difference with the RAM chip is the timings. When you issue a write, you have to wait ~5ms for the operation to complete before the data will be readable (and before doing another single-byte write). That's definitely not an issue here since I'm doing this all by hand. Unlike the EEPROM in Ben Eater's computer, this one does not specify a maximum pulse width for the write cycle, so I just have a small RC filter to compensate for switch bounce.
Enabling output shows the expected 1s everywhere in the factory-fresh ROM. Before I had the data dip switch, to do a write I would:
- Disable the ROM output
- Move the I/O lines from the LED array to ground
- Press and release the LOAD button
- Move the I/O lines back to the LED array
- Enable ROM output
This always resulted in a full bank of lit LEDs, suggesting the write failed. There were no signs of floating inputs to suggest it was rapidly changing addresses. To rule out connection issues, I swapped out the EEPROM for one of the RAM chips. Everything worked as expected.
By this point I was at a complete loss. I'd gone over the data sheet another few times. I added some bypass capacitors across the power strips near where the ROM connects to power & ground, I made sure the voltages make sense on the address pins and control signals. I used the dip switches to control the output enable pin to verify that the ROM senses the dip switch signals correctly.
The fact that 2 different software/microcontroller attempts failed, as well as the manual attempts described above, and with the successful test with a RAM chip, it became hard to stand by the "poor craftsman blames his tools" principle... Maybe the data sheet incorrectly omitted a maximum time for the write pulse? Maybe I got a bad batch? Maybe I zapped all four of them them with static? (not likely; I have a grounding strap I touch every time I sit down and have never even noticed a tickle).
Nearly ready to give up rolling my own, I started googling around for existing Arduino X28C256 EEPROM programming code. I came across a forum thread where someone said the chips come software write-protected from the supplier, despite the data sheet saying "The X28C256 is shipped from Xicor with the software data protection NOT ENABLED" (emphasis in original).
The next day it hit me... While the order of the address and data lines is immaterial for normal usage, it is absolutely critical for sending the magic values to do the software unlock. I rearranged the address lines so that they match the pinout (the data already did) and re-ran the unlock. It still failed!
I need to clarify what I mean by "failing" here: The code that writes some test data reads it back and validates it against the test data. It turns on the Arduino built-in LED if it finds a mismatch. That light came on. I assumed this meant the write failed. Thinking that was a dead end, I put the ROM chip into my manual programmer to do some more investigation.
Lo and behold, when I enabled the chip, some of the bits were off! Not only that, but they seem to be the correct bits for the capital T in my test data: "This is ...". The next 3 addresses had the telltale "lower case" bit set, and the 5th address in the ROM had only the 32 bit set, which is a space. Apparently my write succeeded but my verification failed.
After one more pass over my code I finally realized what happened: the test data string in the original version called itself 64 bytes, but it was actually only 60 bytes. Apparently the 3 bytes beyond the end of the string are used for global variables. The writer would write whatever happened to be in those cells to the ROM, then failed verification when it read that value back but the Arduino's memory had changed. Here is the current code for the EEPROM programmer after fixing that issue.
I can now reliably unlock and write data to the EEPROM, and the unlocked chip works as expected in the manual programmer. Some further improvements I want to make are to use buttons to control the writing/unlocking and add a lock feature. This way it won't clobber the ROM every time it turns on, and I'll be able to use it to easily lock the chips once I have them programmed to avoid any unintended writes.
Until then, I've used my manual programmer to write the first program that will run on this computer:
+-><Or in the CPU's encoding:
0123
Part 1 (first) - Part 6 (prev) - Part 8 (next)
Friday, June 2, 2017
TTL Brainfuck Computer Part 6 - Breadboards and Puzzles, Old and New
Part 1 (first) - Part 5 (prev) - Part 7 (next)
The new breadboards arrived! At more than three times the price of the old ones and with a one year warranty, I wasn't sure exactly what to expect, but damn. Literally everything about them is an order of magnitude better, right down the quality of the packaging.
So I got everything hooked up, and after fixing the address lines to RAM, I was still getting some weird issues. I could use the buttons to move up and down in RAM, but at some point the output would stop changing when going down. At first I thought this was just a coincidence; that a bunch of the high memory addresses, by quirk of die process, started out filled with ones on power-up.
Then I hooked up my 16-bit LED counter and the strangeness intensified. With the counters all starting at zero, count up seems to work as expected. If I hit the LOAD button to fill the counter with 1s (due to floating TTL inputs pulling high), counting up once sets it to zero, and it continues counting from there. However, counting down from zero leaves it at zero. If I count up past zero, it will count down to zero and stop. If I load all ones, it seemed to count down from there.
Until I realized that it was the most significant bits that were changing each count not the least significant. O.o When those most significant bits counted down below zero, suddenly all the least significant bits lit up, then the count-down would happen in the least-significant counter, until it reached zero. Then the most significant counter would start changing.
I double checked that borrow/carry-out connected to count down/up of the next chip.
I checked the continuity of connections between the chip pin entering the breadboard and the signal line entering the breadboard and found nothing wrong.
I checked the voltage levels of the borrow lines with a multimeter, and they all went low-then-high as expected when I pressed the down button while the data was all zeroes.
I triple-checked the borrow/carry-to-down/up connections by removing and re-inserting them. Same behavior.
I verified that the underflow works with the data register (2 chips) by having it count down. All of my assumptions checked out.
I replaced all the counter chips with brand new ones that came earlier this week and they behaved exactly the same. This also had the effect of quadruple-checking all of the clear, load, borrow, carry, up, & down connections.
Since a lot of the issues seemed to come from the most significant bit, I swapped out the capacitor on my clock to get a range of ~ 1 to 10KHz and watched "count up" work perfectly over all 16 bits. As soon as i switched to count down, it would quickly hit zero and stop.
I removed the LED bank and measured the output voltages directly, in case the LED board was causing issues. The outputs all stayed low when I tried counting down.
I added a 100uF capacitor across the power rail on the board with the counters in case it was a switching issue. Same behavior.
I rearranged all of the clear/load wires, both to reduce overlap and to double-check their placement, even though they both worked as expected.
Nothing even hinted at a cause until I removed the borrow/down connection between the 2nd and 3rd counter. Once I did that, the low order byte started working perfectly (basically a copy of the data register). After another pass with the multimeter, I still could not see anything wrong.
I started googling for issues with cascading counters, and everything I read says what I'm doing should work as expected.
Knowing how much I don't know about electronics yet, I figured there was some minutiae of electrical engineering I missed. Maybe I'm getting voltage spikes? Maybe the signals are ringing in the breadboard? It's time for the oscilloscope...
Since the clock signal is driven by a schmitt triggered inverter, the rising and falling edges are extremely clean. There is a tiny bit of ringing at the detection limit of my oscilloscope (70MHz), but at +/- 600mV, it should be well below the threshold for a false-1.
Triggering on the clock and watching the various inputs & outputs didn't produce anything unexpected until I probed the borrow output of the third chip. Suddenly the high order bits started flashing rapidly as if the probe of my oscilloscope was dropping it to ground and triggering the count. I don't see how that would be possible unless this was a CMOS chip; my probes are set to 10x attenuation and should not draw enough current to register as a 0. Maybe I'm wrong about that?
It seems consistent though. If I touch the probe to the clear line on the 3rd chip, the first two chips start behaving correctly. Wait what?
I started rearranging some of the connections again while the clock was running and the LED module was plugged in. When I removed the clear line between the 3rd and 4th chip, the first 3 counters started working perfectly.
Ok... Now I'm getting somewhere. I had noticed that the voltage on the Clear line was in the 0.6V range earlier. It seemed a little high, but it did make sense since you have to sink some current from TTL inputs to register a zero, and that is going through a 1K pull-down resister.
I replaced the 1K resister with a 470R and everything is peachy in counter-land.
I don't quite have a clear grasp on what's going on, but the gist of it seems that when underflowing, the fourth chip in the chain gets into a state where it drives the clear line so high the other chips register it as a signal.
I'm sure there's something in the 74LS193's data sheet that would've alerted me to this problem. I had problems before with pull-down resistors. My first electronics kits had CMOS chips (one had CD4000 series, the other had both that and 74HC) so I generally went with 10K. I switched to 1K when I was having some not-similar-enough-to-ring-a-bell issues with the Data Register.
Anyway, here's the thing hooked up to life support, running properly at 32 KHz. The fact that the clock is operating at 88% duty cycle means the actual swiching is happening in the hundreds of KHZ (around 700 if I mathed it right in my head). The pie in the sky goal I have in the back of my mind is 10 MHz for the final build, so this is pretty encouraging.
Once I get Now that I have this counter issue sorted out, all of the major pieces of the Data Side are in place for the +, -, <, and > operations (half of the language), so I plan to move onto the Program Side.
Breadboards
Here's a non-exhaustive list of the major differences:
I spent Thursday evening moving/copying the existing circuitry to the new breadboards. From the experience with the first iteration, I decided to make several changes. Here's the current state:
I realized I had been orienting the breadboards the wrong way around. All of the power & ground connections had to jump across the ground & power rails. This doesn't have any material effect on the functionality, but it did mean some modules would have to cross wires with another to reach power (aesthetically unpleasant), and all the power jumpers are 1/10" longer than they would otherwise need to be (marginally less cost-effective).
Because of this change, I had to move the power adapter to the other side of the assembly, which is actually more convenient for the way my desk is set up. I went ahead and brought the clock with it, and I added a couple switches to the clock for manual mode (not connected yet). I also added an inverting buffer to provide both inverted (yellow) & non-inverted (white) clock signals for when that becomes a thing.
Now all of the components I had working are on the left side of the board, which I'm calling the Data Side. The empty boards on the left will likely end up being the I/O areas. The right side of the board will be the Program Side, and house the program ROM, controller logic, etc.
I also made an effort to do much flatter, cleaner-looking routes. The thick bundles of wire in the previous version made it difficult to use the LED modules I made to monitor the counters, and it was much harder to follow individual wires between components.
Speaking of LED modules, I finished cutting the 16-bit one down to size. One of the LEDs has a janky connection. It would be pretty tedious to remove and I'd worry about damaging the ones nearby in the process, so I'm not going to bother for now.
Since minimal power consumption has never been one of my goals (I'd be using CMOS if it were), and since these breadboards are so much more reliable, I decided to remove one of the tri-state buffer chips (74LS244) from the Data Register and leave the counter inputs always connected to the bus.
I also modified the color scheme. I was originally planning to use rainbow colors to represent the bit positions of data lines (you can see that in the jumpers connecting the top & bottom bus sections on the old version), but that would get confusing with the colors being used for more general "kinds" of signals. I didn't end up using that, even in the previous build, but when I went to connect the new bus sections, it was a good time to solidify my plans.
In the previous build, I thought it was pretty clever how the RAM chip had its bi-directional bus interface in green, and the data register had "from bus" as blue and "to bus" as yellow. However, I was disappointed by the lack of orange overall, which you may notice is "my" color (along with blue). So I decided that all connections directly to/from the data bus would be in orange. I was already using orange for the LOAD signal on the counters, so the "load data from the bus" control lines will be the same color as the connections to the bus, which is neat.
I preserved the meaning of blue and yellow by using yellow to connect the outputs of the counters to the inputs of the tri-state buffers, and blue to "copy" bus signals from the buffer outputs (bus connections) to the counter inputs.
The borrow/carry signals for both the data register and pointer now use the same colors: green for up, brown for down (rhymes!). I also reversed the order of the counters, such that the most significant counter is on the right. This fits a bit more logically with how the count signal flows from the buttons and avoids a two long run of wires across all the chips.
This is actually why the RAM address lines look a bit in disarray; there are only 15 address lines and I had the most significant bit of the 16-bit counter connected to the address lines and I DIDN'T have the second-most significant one connected, so the memory would see 2 addresses repeated twice before moving on to the next. The look of the wires is a result of shifting them all over by one.
- The plastic looks and feels like ABS (think Legos) rather than HDPE (think plastic milk jugs)
- The silk screening is much clearer and perfectly aligned with the holes
- The boards lay flat by default, even when connected together
- There are more plastic connection tabs along the long edge for better stability
- There are connection tabs along the short edge so they can connect end-to-end, one in the center, and one on each power rail. This made the bus section of my megaboard much more stable
- On visual inspection, none of the holes look like they're obstructed by the clips inside
- They include a metal plate to stick on the back, I'm assuming for both shielding and structural support
- The warm yellowish color is easier on my eyes under fluorescent/LED lighting. It also makes white wires easier to spot
- Even though it's not white, it is completely opaque, so it ends up looking brighter than the white ones.
- The double-sided tape is trimmed so it doesn't get in the way of the connection tabs
- Pushing leads into the board doesn't push the contacts out through the other side
- Actually, the contacts themselves deserve an entire section
3-2-1 Contact!
Imagine you grew up eating nothing but USDA choice sirloin. Now imagine going to Morton's or Gallagher's and having, for the first time, 21+ day dry-aged prime ribeye (or filet, if you prefer). This is what it was like the first time I pushed a lead into these breadboards.
At first it takes a little more force than the cheap ones to open the contact. This is a teeny bit annoying for components with long leads, but I found shortening the leads makes the entire breadboard experience better (much less stuff sticking up to accidentally knock over with fat fingers, easier to add more components nearby, etc.).
As long as the lead is going into the plastic hole, it will be captured by the contacts if you apply enough pressure, unlike the old ones. Those would often bend leads even if you push them in straight down & center.
The power rails hold on even more tightly, which again can be somewhat annoying the first time you insert a lead, but the benefits are well worth it. None of the connections show any signs of loosening after working on other pieces of the board. The bus was physically connected to the left half by only 4 wires (2 ground and 2 power) and never showed any signs of shifting.
The corner-to-corner resistance with the minimum number of connections was about 1.5 Ω compared to the 10-20 Ω of the others (I say 10-20, because any slight movement of the old ones would screw up most of the connections).
So yeah. Don't skimp on your breadboards unless you're a masochist.
Copy Pasta
I spent Thursday evening moving/copying the existing circuitry to the new breadboards. From the experience with the first iteration, I decided to make several changes. Here's the current state:
I realized I had been orienting the breadboards the wrong way around. All of the power & ground connections had to jump across the ground & power rails. This doesn't have any material effect on the functionality, but it did mean some modules would have to cross wires with another to reach power (aesthetically unpleasant), and all the power jumpers are 1/10" longer than they would otherwise need to be (marginally less cost-effective).
Because of this change, I had to move the power adapter to the other side of the assembly, which is actually more convenient for the way my desk is set up. I went ahead and brought the clock with it, and I added a couple switches to the clock for manual mode (not connected yet). I also added an inverting buffer to provide both inverted (yellow) & non-inverted (white) clock signals for when that becomes a thing.
Now all of the components I had working are on the left side of the board, which I'm calling the Data Side. The empty boards on the left will likely end up being the I/O areas. The right side of the board will be the Program Side, and house the program ROM, controller logic, etc.
I also made an effort to do much flatter, cleaner-looking routes. The thick bundles of wire in the previous version made it difficult to use the LED modules I made to monitor the counters, and it was much harder to follow individual wires between components.
Speaking of LED modules, I finished cutting the 16-bit one down to size. One of the LEDs has a janky connection. It would be pretty tedious to remove and I'd worry about damaging the ones nearby in the process, so I'm not going to bother for now.
Since minimal power consumption has never been one of my goals (I'd be using CMOS if it were), and since these breadboards are so much more reliable, I decided to remove one of the tri-state buffer chips (74LS244) from the Data Register and leave the counter inputs always connected to the bus.
I also modified the color scheme. I was originally planning to use rainbow colors to represent the bit positions of data lines (you can see that in the jumpers connecting the top & bottom bus sections on the old version), but that would get confusing with the colors being used for more general "kinds" of signals. I didn't end up using that, even in the previous build, but when I went to connect the new bus sections, it was a good time to solidify my plans.
In the previous build, I thought it was pretty clever how the RAM chip had its bi-directional bus interface in green, and the data register had "from bus" as blue and "to bus" as yellow. However, I was disappointed by the lack of orange overall, which you may notice is "my" color (along with blue). So I decided that all connections directly to/from the data bus would be in orange. I was already using orange for the LOAD signal on the counters, so the "load data from the bus" control lines will be the same color as the connections to the bus, which is neat.
I preserved the meaning of blue and yellow by using yellow to connect the outputs of the counters to the inputs of the tri-state buffers, and blue to "copy" bus signals from the buffer outputs (bus connections) to the counter inputs.
The borrow/carry signals for both the data register and pointer now use the same colors: green for up, brown for down (rhymes!). I also reversed the order of the counters, such that the most significant counter is on the right. This fits a bit more logically with how the count signal flows from the buttons and avoids a two long run of wires across all the chips.
This is actually why the RAM address lines look a bit in disarray; there are only 15 address lines and I had the most significant bit of the 16-bit counter connected to the address lines and I DIDN'T have the second-most significant one connected, so the memory would see 2 addresses repeated twice before moving on to the next. The look of the wires is a result of shifting them all over by one.
Old Puzzles
Swinging back around to the loop optimizations from last time, I had a couple fruitful discussions on Reddit and Hacker News.
The reason I hadn't settled on one way or another is that pre-processing allows me to achieve my performance goals during execution, but it makes the machine into a sort of combined compiler+CPU, rather than "just" a CPU. I feel strongly about both goals and have been struggling with a good way to word this newly discovered principle. The best I have so far is:
- Purity - This is a CPU that runs Brainfuck; strong justification is required to do anything a "normal" CPU or Brainfuck wouldn't do
I really don't want to sacrifice purity for performance, but I also don't want to sacrifice performance for purity. Luckily there is a very precise modification I can make to the principles that can give me (nearly) the best of both worlds:
Constant time execution of each instruction - It should never take more than 3 cycles to execute any instruction- Amortized constant time execution of each instruction - Let i be some instruction at a particular location in a program. Let n be the number of times that instruction has been executed since the program started. Let En(i) be the average number of cycles required to execute i n times. The limit of En(i) as n approaches infinity must be 3 or less.
The "minimal number of execution steps" principle could also be defined in terms of En(i), but I think it's clear enough as-is.
I'm now planning to use a hybrid of the approaches from the previous post. The first time through a loop, if the loop condition is 0, it will skip over the instructions in the loop one at a time. In the process, it will index the start & end locations of the loop and any loops nested inside it. The next time the loop is entered, the indexed location will be used to jump to the end if the loop condition is 0.
Another advantage of this approach is that it provides an incremental pathway of increasing complexity for implementing the looping logic. I can start with the "pretend NOP" approach for linear time on both [ & ], add the stack-based approach for constant time ], then use the stack RAM as a bi-directional index for amortizing [.
In a similar vein, I'm also planning to use a data zeroing counter instead of erase-on-reset. The first time a memory location is moved to, it will synthesize a 0 (probably by clearing the data register and scheduling a write to RAM). Unless a program passes over memory locations without ever reading/writing them (a rather silly pessimization in the Brainfuck code), I believe this should match the performance characteristics of pre-zeroed RAM.
Another advantage of this approach is that it provides an incremental pathway of increasing complexity for implementing the looping logic. I can start with the "pretend NOP" approach for linear time on both [ & ], add the stack-based approach for constant time ], then use the stack RAM as a bi-directional index for amortizing [.
In a similar vein, I'm also planning to use a data zeroing counter instead of erase-on-reset. The first time a memory location is moved to, it will synthesize a 0 (probably by clearing the data register and scheduling a write to RAM). Unless a program passes over memory locations without ever reading/writing them (a rather silly pessimization in the Brainfuck code), I believe this should match the performance characteristics of pre-zeroed RAM.
New Puzzles
So I got everything hooked up, and after fixing the address lines to RAM, I was still getting some weird issues. I could use the buttons to move up and down in RAM, but at some point the output would stop changing when going down. At first I thought this was just a coincidence; that a bunch of the high memory addresses, by quirk of die process, started out filled with ones on power-up.
Then I hooked up my 16-bit LED counter and the strangeness intensified. With the counters all starting at zero, count up seems to work as expected. If I hit the LOAD button to fill the counter with 1s (due to floating TTL inputs pulling high), counting up once sets it to zero, and it continues counting from there. However, counting down from zero leaves it at zero. If I count up past zero, it will count down to zero and stop. If I load all ones, it seemed to count down from there.
Until I realized that it was the most significant bits that were changing each count not the least significant. O.o When those most significant bits counted down below zero, suddenly all the least significant bits lit up, then the count-down would happen in the least-significant counter, until it reached zero. Then the most significant counter would start changing.
I double checked that borrow/carry-out connected to count down/up of the next chip.
I checked the continuity of connections between the chip pin entering the breadboard and the signal line entering the breadboard and found nothing wrong.
I checked the voltage levels of the borrow lines with a multimeter, and they all went low-then-high as expected when I pressed the down button while the data was all zeroes.
I triple-checked the borrow/carry-to-down/up connections by removing and re-inserting them. Same behavior.
I verified that the underflow works with the data register (2 chips) by having it count down. All of my assumptions checked out.
I replaced all the counter chips with brand new ones that came earlier this week and they behaved exactly the same. This also had the effect of quadruple-checking all of the clear, load, borrow, carry, up, & down connections.
Since a lot of the issues seemed to come from the most significant bit, I swapped out the capacitor on my clock to get a range of ~ 1 to 10KHz and watched "count up" work perfectly over all 16 bits. As soon as i switched to count down, it would quickly hit zero and stop.
I removed the LED bank and measured the output voltages directly, in case the LED board was causing issues. The outputs all stayed low when I tried counting down.
I added a 100uF capacitor across the power rail on the board with the counters in case it was a switching issue. Same behavior.
I rearranged all of the clear/load wires, both to reduce overlap and to double-check their placement, even though they both worked as expected.
Nothing even hinted at a cause until I removed the borrow/down connection between the 2nd and 3rd counter. Once I did that, the low order byte started working perfectly (basically a copy of the data register). After another pass with the multimeter, I still could not see anything wrong.
I started googling for issues with cascading counters, and everything I read says what I'm doing should work as expected.
Knowing how much I don't know about electronics yet, I figured there was some minutiae of electrical engineering I missed. Maybe I'm getting voltage spikes? Maybe the signals are ringing in the breadboard? It's time for the oscilloscope...
Since the clock signal is driven by a schmitt triggered inverter, the rising and falling edges are extremely clean. There is a tiny bit of ringing at the detection limit of my oscilloscope (70MHz), but at +/- 600mV, it should be well below the threshold for a false-1.
Triggering on the clock and watching the various inputs & outputs didn't produce anything unexpected until I probed the borrow output of the third chip. Suddenly the high order bits started flashing rapidly as if the probe of my oscilloscope was dropping it to ground and triggering the count. I don't see how that would be possible unless this was a CMOS chip; my probes are set to 10x attenuation and should not draw enough current to register as a 0. Maybe I'm wrong about that?
It seems consistent though. If I touch the probe to the clear line on the 3rd chip, the first two chips start behaving correctly. Wait what?
I started rearranging some of the connections again while the clock was running and the LED module was plugged in. When I removed the clear line between the 3rd and 4th chip, the first 3 counters started working perfectly.
Ok... Now I'm getting somewhere. I had noticed that the voltage on the Clear line was in the 0.6V range earlier. It seemed a little high, but it did make sense since you have to sink some current from TTL inputs to register a zero, and that is going through a 1K pull-down resister.
I replaced the 1K resister with a 470R and everything is peachy in counter-land.
I don't quite have a clear grasp on what's going on, but the gist of it seems that when underflowing, the fourth chip in the chain gets into a state where it drives the clear line so high the other chips register it as a signal.
I'm sure there's something in the 74LS193's data sheet that would've alerted me to this problem. I had problems before with pull-down resistors. My first electronics kits had CMOS chips (one had CD4000 series, the other had both that and 74HC) so I generally went with 10K. I switched to 1K when I was having some not-similar-enough-to-ring-a-bell issues with the Data Register.
Anyway, here's the thing hooked up to life support, running properly at 32 KHz. The fact that the clock is operating at 88% duty cycle means the actual swiching is happening in the hundreds of KHZ (around 700 if I mathed it right in my head). The pie in the sky goal I have in the back of my mind is 10 MHz for the final build, so this is pretty encouraging.
Next Steps
Last week I made a half-hearted attempt to program an EEPROM with my Arduino but didn't get very far. The code was quick & dirty so I'm sure it wasn't doing the right thing somewhere. Hopefully my next post will involve a look through program memory.
Wednesday, May 31, 2017
TTL Brainfuck Computer Part 5 - Complexities and Missteps
Part 1 (first) - Part 4 (prev) - Part 6 (next)
My guiding principles, both separately and in conjunction, present some interesting challenges. Here are the optimization puzzles I'm currently working on.
Modifying a value in RAM involves moving the data from RAM to the Data Register, in/decrementing the Data Register, and moving the data from the Data Register back to RAM. Since Brainfuck programs usually have several +/- in a row, the data only needs to be transferred at the beginning and end of a run.
To state more clearly, you only need to write to RAM when the Data Register has been incremented/decremented and the memory location is about to change. Similarly, you only need to read from RAM if the memory location has changed since the previous read. The story gets a bit more complicated with the I/O instructions, but that's for another day.
As an alternative to the conditional read/write, I've been toying with the idea of putting the read/writes and inc/decs out of phase. So the RAM would be read/written on rising clock, and inc/dec would happen on falling clock. Coincidentally (or more likely by foresight of the 7400 series designers), the control signals to the RAM and counters already follow this logic. I haven't followed this line of thinking very far though so I'm not sure where it will lead.
When a Brainfuck program begins, all memory locations have to start at 0. One option would be to keep a "Clear Pointer" of the highest accessed address. Whenever the Data Pointer goes up, if it is higher than the Clear Pointer, write a 0 to that location. With some clever micro-instruction logic, this would only take 2 extra cycles the first time you access a RAM location.
A simpler (and somewhat less fun) option would be to have the reset circuitry walk through RAM with a fast clock and set it all to 0 before running the program. I feel like this better fits the "Minimal number of execution steps per instruction" principle, and more directly reflects the execution of an interpreted/complied Brainfuck program on a regular computer.
If you've been paying really close attention so far and, and if you have an intimate working knowledge of Brainfuck, you may have noticed some hand waiving in my early posts about constant time looping. My logisim implementation had a 'uge mistake in its implementation of the Brainfuck language, and I didn't notice until long after I'd started on the breadboard project.
The loop construct, [ ... ], is represented in C as while (*data_pointer) { ... }. This means that as the loop is entered, the current RAM value is read. If it's 0, the contents of the loop are skipped. Otherwise, the contents of the loop run. At the end of the loop, if the contents of RAM at the current location is NOT zero, then it jumps back to the beginning of the loop.
Unfortunately, the way I built it in logisim would be represented by do { ... } while (*data_pointer);. This means the contents of the loop always run at least once. An open question is whether this change breaks the language's Turing Completeness. Another open question is what do we call this new language? But those questions are for another time.
Does this problem mean I have to sacrifice [ to the O(n) gods? Not necessarily... If I'm planning to do the "zero RAM on reset" strategy, I could throw in a parallel "index all the loop locations". I would have a bit of circuitry walk through program memory looking for all the [ and ]. In another RAM, at each address where there is a [ in the program, write the address of the corresponding ]. This reset circuitry could use the existing Stack RAM to balance the brackets.
So that's where I am as of this moment. The replacement breadboards should be here today. Yay!
On second thought, the index could be used for both [ and ], and the stack would only be necessary during analysis. That would make the control circuitry more consistent.
Part 1 (first) - Part 4 (prev) - Part 6 (next)
My guiding principles, both separately and in conjunction, present some interesting challenges. Here are the optimization puzzles I'm currently working on.
Minimizing Clock Per Instruction
Modifying a value in RAM involves moving the data from RAM to the Data Register, in/decrementing the Data Register, and moving the data from the Data Register back to RAM. Since Brainfuck programs usually have several +/- in a row, the data only needs to be transferred at the beginning and end of a run.
To state more clearly, you only need to write to RAM when the Data Register has been incremented/decremented and the memory location is about to change. Similarly, you only need to read from RAM if the memory location has changed since the previous read. The story gets a bit more complicated with the I/O instructions, but that's for another day.
As an alternative to the conditional read/write, I've been toying with the idea of putting the read/writes and inc/decs out of phase. So the RAM would be read/written on rising clock, and inc/dec would happen on falling clock. Coincidentally (or more likely by foresight of the 7400 series designers), the control signals to the RAM and counters already follow this logic. I haven't followed this line of thinking very far though so I'm not sure where it will lead.
Zeroing RAM
When a Brainfuck program begins, all memory locations have to start at 0. One option would be to keep a "Clear Pointer" of the highest accessed address. Whenever the Data Pointer goes up, if it is higher than the Clear Pointer, write a 0 to that location. With some clever micro-instruction logic, this would only take 2 extra cycles the first time you access a RAM location.
A simpler (and somewhat less fun) option would be to have the reset circuitry walk through RAM with a fast clock and set it all to 0 before running the program. I feel like this better fits the "Minimal number of execution steps per instruction" principle, and more directly reflects the execution of an interpreted/complied Brainfuck program on a regular computer.
Fixing a Major Brainfuck
If you've been paying really close attention so far and, and if you have an intimate working knowledge of Brainfuck, you may have noticed some hand waiving in my early posts about constant time looping. My logisim implementation had a 'uge mistake in its implementation of the Brainfuck language, and I didn't notice until long after I'd started on the breadboard project.
The loop construct, [ ... ], is represented in C as while (*data_pointer) { ... }. This means that as the loop is entered, the current RAM value is read. If it's 0, the contents of the loop are skipped. Otherwise, the contents of the loop run. At the end of the loop, if the contents of RAM at the current location is NOT zero, then it jumps back to the beginning of the loop.
Unfortunately, the way I built it in logisim would be represented by do { ... } while (*data_pointer);. This means the contents of the loop always run at least once. An open question is whether this change breaks the language's Turing Completeness. Another open question is what do we call this new language? But those questions are for another time.
Does this problem mean I have to sacrifice [ to the O(n) gods? Not necessarily... If I'm planning to do the "zero RAM on reset" strategy, I could throw in a parallel "index all the loop locations". I would have a bit of circuitry walk through program memory looking for all the [ and ]. In another RAM, at each address where there is a [ in the program, write the address of the corresponding ]. This reset circuitry could use the existing Stack RAM to balance the brackets.
So that's where I am as of this moment. The replacement breadboards should be here today. Yay!
Edit
On second thought, the index could be used for both [ and ], and the stack would only be necessary during analysis. That would make the control circuitry more consistent.
Part 1 (first) - Part 4 (prev) - Part 6 (next)
Tuesday, May 30, 2017
TTL Brainfuck Computer Part 4 - Animate Objects
Part 1 (first) - Part 3 (prev) - Part 5 (next)
To breathe life into my CPU, it needs a heartbeat. I put together a simple 555 astable circuit with a 10k potentiometer to adjust the clock speed. I'm still waiting on some switches to put in a manual clock mode.
To breathe life into my CPU, it needs a heartbeat. I put together a simple 555 astable circuit with a 10k potentiometer to adjust the clock speed. I'm still waiting on some switches to put in a manual clock mode.
Since the counter control signals need to be synchronized with the clock, I added a 74LS00 (quad 2-input NAND) to combine the signals. This provides the high signal by default to disable count/load, and only activates (goes low) when both the clock and control signals go high. This "uninverts" the logic of the control signals and confuses me a couple times in the following video:
You'll notice a couple extra jumpers connecting the ground lines on the data register. I'm starting to have some really frustrating issues with these crappy breadboards. Replacements should be here tomorrow.
The LED boards are made from some breadboard-style PCB that came with one of the Elegoo kits. I trimmed the plastic lip with wire nippers so they'd fit snugly. I alternated their orientations so cathode is next to cathode, anode next to anode. Then I put resistors on the underside of the board between the cathodes and the power rail of the PCB. I chopped off the cathode leads, and added a ground connection to the new common cathode. Having 2 anodes side by side with 2 blank spaces between fits perfectly in the outputs of the 193s, and only needs a small bit of bending to fit into the data bus.
TTL Brainfuck Computer Part 3 - First Connections
Part 1 (first) - Part 2 (prev) - Part 4 (next)
After making a pile of insulation confetti, here's a thing that actually does some stuff:
I went ahead and grabbed one of the other 193s to finish up the Data Pointer at the top-left. The output of the counters are connected in purple to the address lines of the Data RAM.
The buttons on the left are connected to Load (orange), Clear (white), Down (red/blue) and Up (green/yellow). This allows me to easily cycle through memory addresses. Load, Down, & Up are active low, so they've got pull-up resistors to +5V. Clear is pulled low.
The I/O pins of the RAM are connected to the data bus. The three jumper wires coming out of the ram are Load (orange), Output Enable (blue), and Chip Enable (yellow). These are all active low, so currently it's sending whatever value is being pointed to in RAM onto the bus. The LEDs show this as 11001000 (0xC8).
The Data Register has grown quite a bit more complicated. The chips with wires going to the bus are 74LS244 octal tri-state buffers. These separately connect/disconnect the inputs (blue) and outputs (yellow) of the counters to/from the data bus. If I were using CMOS chips, I would leave the inputs connected and only switch the outputs. But with TTL, inputs draw non-trivial current and I don't want to load the bus any more than necessary; breadboards already have a hard enough time delivering power.
The 193s have the same jumper wire colors for clear, load, down, and up as the data pointer but are connected directly to the power rails rather than through buttons. At this point I'm more concerned with moving data between RAM and the register. I can do that in this shot by moving the blue jumper to ground on the data register (input from bus), then momentarily bringing the orange jumper to ground (load).
Once the value is loaded into the register it can be modified with the up/down jumpers (albeit with tons of bounce). Then I can load it back into RAM by turning off the output from RAM (set its blue jumper high), enabling output from the data register (set its yellow pin low), and momentarily set the RAM's load pin low.
Next post will demonstrate some of this in action.
Part 1 (first) - Part 2 (prev) - Part 4 (next)
After making a pile of insulation confetti, here's a thing that actually does some stuff:
I went ahead and grabbed one of the other 193s to finish up the Data Pointer at the top-left. The output of the counters are connected in purple to the address lines of the Data RAM.
The buttons on the left are connected to Load (orange), Clear (white), Down (red/blue) and Up (green/yellow). This allows me to easily cycle through memory addresses. Load, Down, & Up are active low, so they've got pull-up resistors to +5V. Clear is pulled low.
The I/O pins of the RAM are connected to the data bus. The three jumper wires coming out of the ram are Load (orange), Output Enable (blue), and Chip Enable (yellow). These are all active low, so currently it's sending whatever value is being pointed to in RAM onto the bus. The LEDs show this as 11001000 (0xC8).
The Data Register has grown quite a bit more complicated. The chips with wires going to the bus are 74LS244 octal tri-state buffers. These separately connect/disconnect the inputs (blue) and outputs (yellow) of the counters to/from the data bus. If I were using CMOS chips, I would leave the inputs connected and only switch the outputs. But with TTL, inputs draw non-trivial current and I don't want to load the bus any more than necessary; breadboards already have a hard enough time delivering power.
The 193s have the same jumper wire colors for clear, load, down, and up as the data pointer but are connected directly to the power rails rather than through buttons. At this point I'm more concerned with moving data between RAM and the register. I can do that in this shot by moving the blue jumper to ground on the data register (input from bus), then momentarily bringing the orange jumper to ground (load).
Once the value is loaded into the register it can be modified with the up/down jumpers (albeit with tons of bounce). Then I can load it back into RAM by turning off the output from RAM (set its blue jumper high), enabling output from the data register (set its yellow pin low), and momentarily set the RAM's load pin low.
Next post will demonstrate some of this in action.
Part 1 (first) - Part 2 (prev) - Part 4 (next)
TTL Brainfuck Computer Part 2 - First steps
Part 1 (prev) - Part 3 (next)
The most basic piece of a breadboard computer is, of course, the breadboards. I found some Elegoo brand 3-packs on Amazon with primarily positive reviews for less than $10 and snagged a couple, along with some other Elegoo kits which each came with one breadboard.
I was not impressed at all with their quality. The clips were misaligned so that inserting leads was tedious-to-impossible. Their own brand power modules, which have a DC jack and plug into the power rails on a breadboard, would not fit without some extreme jiggling & pin bending.
I left a one-star review and they sent me replacements hoping I'd reconsider. At first they seemed much better than the original set. But while they didn't have the same frequency of issues, they still had problems. For one thing, the DIP switches I got will not stay in the holes at all. Tactile switches are similarly hard to keep in. By comparison, a breadboard that came with an electronics kit years ago holds onto these with enough force that they were more difficult to remove than insert.
I ordered some better ones which should be here this week, but these ones work just well enough that I couldn't resist starting. Here is an initial layout:
All but two of the breadboards had their "top" power rail sliced off (the slicing is just through the double-sided tape; they're otherwise joined by plastic tabs). The boards and power rails were joined together in two chunks each. I cut some pieces of hookup wire to connect the power & data buses together.
The clock is a 555 timer. The second 555 is for de-bouncing the manual clock button. I'm planning to use a different design that only needs a single 555, but I need a SPDT switch, not just an OFF-(ON).
Data Pointer and Data Register/ALU are made of Binary up/down counters (74LS193). This naturally represents the fundamental Brainfuck operations of +, -, >, and <. The Data Pointer pictured here has only 3 of the 4 chips needed to address 32 K of RAM. A handful more of these chips should be arriving this week.
A + instruction will cause the Data Register to increment. A - will cause it to decrement. A > will cause the Data Pointer to increment. A < will cause it to decrement. Values will be transferred to/from RAM whenever necessary.
Stack Pointer is also made of 193s to handle Brainfuck's [ and ] instructions. The location to jump to will be stored when entering the loop. An alternative design would be to keep a depth counter and decrement PC until depth goes down, but looping should be constant time for remotely reasonable performance.
The Program Pointer also uses 193s; It never needs to count down, but the other binary counters in the kit are ripple carry and can't be loaded directly with data. It needs to be able to load a program counter location from the Stack Pointer.
Data and Stack RAM are made of 32 KB ram chips (CY7C199-35PC). Stack needs 2 of them to handle the address width of the Data RAM. The two chips will have address lines in common, so it acts as a single 32 K x 16-bit memory.
The microcode stepper is a J/K flip flop to toggle between micro-instruction steps.
The Program & Microcode ROMs are 32 KB EEPROMs (X28C256P-15). This is massive overkill for the Microcode. I shouldn't need more than 8 bits per instruction and Brainfuck only has 8 instructions. I may end up doing the microcode with discrete logic gates just for the challenge.
The most basic piece of a breadboard computer is, of course, the breadboards. I found some Elegoo brand 3-packs on Amazon with primarily positive reviews for less than $10 and snagged a couple, along with some other Elegoo kits which each came with one breadboard.
I was not impressed at all with their quality. The clips were misaligned so that inserting leads was tedious-to-impossible. Their own brand power modules, which have a DC jack and plug into the power rails on a breadboard, would not fit without some extreme jiggling & pin bending.
I left a one-star review and they sent me replacements hoping I'd reconsider. At first they seemed much better than the original set. But while they didn't have the same frequency of issues, they still had problems. For one thing, the DIP switches I got will not stay in the holes at all. Tactile switches are similarly hard to keep in. By comparison, a breadboard that came with an electronics kit years ago holds onto these with enough force that they were more difficult to remove than insert.
I ordered some better ones which should be here this week, but these ones work just well enough that I couldn't resist starting. Here is an initial layout:
All but two of the breadboards had their "top" power rail sliced off (the slicing is just through the double-sided tape; they're otherwise joined by plastic tabs). The boards and power rails were joined together in two chunks each. I cut some pieces of hookup wire to connect the power & data buses together.
The clock is a 555 timer. The second 555 is for de-bouncing the manual clock button. I'm planning to use a different design that only needs a single 555, but I need a SPDT switch, not just an OFF-(ON).
Data Pointer and Data Register/ALU are made of Binary up/down counters (74LS193). This naturally represents the fundamental Brainfuck operations of +, -, >, and <. The Data Pointer pictured here has only 3 of the 4 chips needed to address 32 K of RAM. A handful more of these chips should be arriving this week.
A + instruction will cause the Data Register to increment. A - will cause it to decrement. A > will cause the Data Pointer to increment. A < will cause it to decrement. Values will be transferred to/from RAM whenever necessary.
Stack Pointer is also made of 193s to handle Brainfuck's [ and ] instructions. The location to jump to will be stored when entering the loop. An alternative design would be to keep a depth counter and decrement PC until depth goes down, but looping should be constant time for remotely reasonable performance.
The Program Pointer also uses 193s; It never needs to count down, but the other binary counters in the kit are ripple carry and can't be loaded directly with data. It needs to be able to load a program counter location from the Stack Pointer.
Data and Stack RAM are made of 32 KB ram chips (CY7C199-35PC). Stack needs 2 of them to handle the address width of the Data RAM. The two chips will have address lines in common, so it acts as a single 32 K x 16-bit memory.
The microcode stepper is a J/K flip flop to toggle between micro-instruction steps.
The Program & Microcode ROMs are 32 KB EEPROMs (X28C256P-15). This is massive overkill for the Microcode. I shouldn't need more than 8 bits per instruction and Brainfuck only has 8 instructions. I may end up doing the microcode with discrete logic gates just for the challenge.
TTL Brainfuck Computer Part 1 - Intro
Part 2
A couple months ago I stumbled across Ben Eater's series building a breadboard computer out of TTL chips. I've had the idea in the back of my mind to do something like this for a while now, but Ben's series has kicked a lot of people over the edge and it's turning into a bit of a trend.
I've always had a soft spot for Brainfuck (and more generally, esolangs and obfuscated code). Way back in ought 6, I wrote an obfuscated Brainfuck interpreter to use as my e-mail signature (the yin-yang light bulb was my personal logo before Gnomes took over my identity):
#include <iostream> // // _ | |
#include <fstream> //| //| // \\ \ __ /
#include <cstring> //||//|| // // __ /o)\ __
#define S 32768 // |// || \\_//RLANDO \(o/
#define b ;break; // |/ ||ATTHEW 2006 ZZ
#define c(x,y) case x:y //==================================
char a[2*S],*m=a,*p=a+S,*r=p,o; void i(int n=0){char*l=p;while
(p<r){switch(*p++){c(43,++*m)b c(45, --*m)b c(62,++m)b c(60,--
m)b c(46,std::cout.put(*m))b c(44, *m=std::cin.get(o)?o:*m)b c
(91,if(*m)i(n+1);else for(o= 1;o&&p<r;++p){o+=*p==91;o-=*p==93
;})b c(93,if(*m)p=l; else return;)}}}int main(int _, char**f){
memset(a,0,2*S);std::ifstream z(f[1]); while(z.get(*r++));i();
return 0;} //BF interpreter. No err chk. 32k mem, 32k program.
Someone who knows me well enough probably could've predicted my urge to make a hardware Brainfuck computer after seeing Ben's series.
From the beginning, I had some guiding principles for the design:
Brainfuck programs are extremely inefficient in code size, and fairly inefficient in memory usage. Only the most trivial programs would fit in 16 bytes (nothing close to printing the Fibonacci sequence). Since I'm targeting minimal clock cycles, a Harvard architecture makes more sense, where data and instructions are transferred on separate buses. Since Brainfuck programs are so inefficient in code size, it would be extremely tedious to have to enter the program every time the system powers on. I decided to use EEPROMs for the program memory.
I spent some time playing with logisim-evolution, a digital circuit designer/simulator to get a rough idea of the implementation. By using RAM with asynchronous outputs (output changes immediately when the address changes) and separate inputs, I was able to make a design that executed one instruction per cycle.
Then I started looking at hardware. Jameco sells a kit with 10 or 20 each of 35 different 74LS chips, which I believe is the same kit Ben used. Except for the RAM and ROM, this kit has pretty much everything I needed. The most important parts are the binary up/down counters (74LS193) since half of all Brainfuck operations involve either incrementing or decrementing a number (either the location in memory or the data in memory). They also had a suitable EEPROM. So that side of things is fine, but I still needed RAM.
Even if I used every flip flop & latch in the kit, I would still only have probably a hundred or so bytes of RAM, so I went looking for SRAM chips with 15+ address lines. Unfortunately, the only asynchronous SRAM chips available with separate input & output lines are fully dual port, meaning both sets of I/O lines can act as input or output. This makes them much more complicated in design and the cost for a 32KB chip is north of $40. On top of the cost, they're all surface mount devices (BGA, QFP, etc), so I'd have to solder them onto a break-out board. I've never done surface mount soldering, and there's no way I'm going to practice on a $40 chip.
So I decided to scale back my ambitions and go for a 2-cycle design using single port RAM. I was able to get ten of CY7C199-35PC for half the price of a single dual-port.
In the next post, I'll show the initial breadboard layout and give an overview of the design of the computer.
Part 2
A couple months ago I stumbled across Ben Eater's series building a breadboard computer out of TTL chips. I've had the idea in the back of my mind to do something like this for a while now, but Ben's series has kicked a lot of people over the edge and it's turning into a bit of a trend.
I've always had a soft spot for Brainfuck (and more generally, esolangs and obfuscated code). Way back in ought 6, I wrote an obfuscated Brainfuck interpreter to use as my e-mail signature (the yin-yang light bulb was my personal logo before Gnomes took over my identity):
#include <iostream> // // _ | |
#include <fstream> //| //| // \\ \ __ /
#include <cstring> //||//|| // // __ /o)\ __
#define S 32768 // |// || \\_//RLANDO \(o/
#define b ;break; // |/ ||ATTHEW 2006 ZZ
#define c(x,y) case x:y //==================================
char a[2*S],*m=a,*p=a+S,*r=p,o; void i(int n=0){char*l=p;while
(p<r){switch(*p++){c(43,++*m)b c(45, --*m)b c(62,++m)b c(60,--
m)b c(46,std::cout.put(*m))b c(44, *m=std::cin.get(o)?o:*m)b c
(91,if(*m)i(n+1);else for(o= 1;o&&p<r;++p){o+=*p==91;o-=*p==93
;})b c(93,if(*m)p=l; else return;)}}}int main(int _, char**f){
memset(a,0,2*S);std::ifstream z(f[1]); while(z.get(*r++));i();
return 0;} //BF interpreter. No err chk. 32k mem, 32k program.
From the beginning, I had some guiding principles for the design:
- Provide enough storage for non-trivial programs - Minimum specs matching my Brainfuck signature: 32 K instructions, 32 K data.
- One-to-one correspondence between Brainfuck commands and CPU instructions - There is merely an encoding difference
- Constant time execution of each instruction - It should never take more than 3 cycles to execute any instruction
- Minimal number of execution steps - If an instruction can be executed in one cycle, it should be
Brainfuck programs are extremely inefficient in code size, and fairly inefficient in memory usage. Only the most trivial programs would fit in 16 bytes (nothing close to printing the Fibonacci sequence). Since I'm targeting minimal clock cycles, a Harvard architecture makes more sense, where data and instructions are transferred on separate buses. Since Brainfuck programs are so inefficient in code size, it would be extremely tedious to have to enter the program every time the system powers on. I decided to use EEPROMs for the program memory.
I spent some time playing with logisim-evolution, a digital circuit designer/simulator to get a rough idea of the implementation. By using RAM with asynchronous outputs (output changes immediately when the address changes) and separate inputs, I was able to make a design that executed one instruction per cycle.
Then I started looking at hardware. Jameco sells a kit with 10 or 20 each of 35 different 74LS chips, which I believe is the same kit Ben used. Except for the RAM and ROM, this kit has pretty much everything I needed. The most important parts are the binary up/down counters (74LS193) since half of all Brainfuck operations involve either incrementing or decrementing a number (either the location in memory or the data in memory). They also had a suitable EEPROM. So that side of things is fine, but I still needed RAM.
Even if I used every flip flop & latch in the kit, I would still only have probably a hundred or so bytes of RAM, so I went looking for SRAM chips with 15+ address lines. Unfortunately, the only asynchronous SRAM chips available with separate input & output lines are fully dual port, meaning both sets of I/O lines can act as input or output. This makes them much more complicated in design and the cost for a 32KB chip is north of $40. On top of the cost, they're all surface mount devices (BGA, QFP, etc), so I'd have to solder them onto a break-out board. I've never done surface mount soldering, and there's no way I'm going to practice on a $40 chip.
So I decided to scale back my ambitions and go for a 2-cycle design using single port RAM. I was able to get ten of CY7C199-35PC for half the price of a single dual-port.
In the next post, I'll show the initial breadboard layout and give an overview of the design of the computer.
Part 2
Subscribe to:
Posts (Atom)