Using Lookup Tables To Make The Impossible Possible

Embarrassing confession time: I never learned my multiplication tables in grade school. Sure, I had the easy tables like the twos and the fives down, but if asked what 4 x 7 or 8 x 6 was, I’d draw a blank. As you can imagine, that made me a less than stellar math student, and I was especially handicapped on time-limited tests with lots of long multiplication problems. The standard algorithm is much faster when you’ve committed those tables to memory, as I discovered to my great woe.

I was reminded of this painful memory as I watched Charles Lohr’s 2019 Supercon talk on the usefulness and flexibility of lookup tables, or LUTs, and their ability to ease or even completely avoid computationally intensive operations. Of course most LUT implementations address problems somewhat more complex than multiplication tables, but they don’t have to. As Charles points out, even the tables of sines and logarithms that used to populate page after page in reference books have been ported to silicon, where looking up the correct answer based on user input is far easier than deriving the answer computationally.

Yes, this is a Minecraft server all thanks to LUTs.

One of the most interesting examples of how LUTs can achieve the seemingly impossible lies in an old project where Charles attempted to build a Minecraft server on an ATMega168. Sending chunks (the data representations of a portion of the game world) to clients is the essential job of a Minecraft server, and on normal machines that involves using data compression. Rather than trying to implement zlib on an 8-bit microcontroller, he turned to a LUT that just feeds the raw bytes to the client, without the server having the slightest idea what any of it means. A similar technique is used by some power inverters, which synthesize sine wave output by feeding one full cycle of values to a DAC from a byte array. It’s brute force, but it works.

Another fascinating and unexpected realization is that LUTs don’t necessarily have to be software. Some can be implemented in completely mechanical systems. Charles used the example of cams on a shaft; in a car’s engine, these represent the code needed to open and close valves at the right time for each cylinder. More complicated examples are the cams and gears once found in fire control computers for naval guns, or the programming cards used for Jacquard looms. He even tips his hat to the Wintergatan marble machine, with its large programming drum and pegs acting as a hardware LUT.

I found Charles’ talk wide-ranging and fascinating. Originally I thought it would be an FPGA-heavy talk, but he didn’t actually get to the FPGA-specific stuff until the very end. That worked out fine, though — just hearing about all the cool problems a LUT can solve was worth the price of admission.

And for the curious, yes, I did eventually end up memorizing the multiplication tables. Oddly, it only clicked for me after I started playing with numbers and seeing their relationships using my first calculator, which ironically enough probably used LUTs to calculate results.

Continue reading “Using Lookup Tables To Make The Impossible Possible”

This Week In Security: Camera Feeds, Python 2, FPGAs

Networked cameras keep making the news, and not in the best of ways. First it was compromised Ring accounts used for creepy pranks, and now it’s Xiaomi’s stale cache sending camera images to strangers! It’s not hard to imagine how such a flaw could happen: Xiaomi does some video feed transcoding in order to integrate with Google’s Hub service. When a transcoding slot is re-purposed from one camera to another, the old data stays in the buffer until it is replaced by the new camera’s feed. The root cause is probably the same as the random images shown when starting some 3D games.

Python is Dead, Long Live Python

Python 2 has finally reached End of Life. While there are many repercussions to this change, the security considerations are important too. The Python 2 environment will no longer receive updates, even if a severe security vulnerability is found. How often is a security vulnerability found in a language? Perhaps not very often, but the impact can be far-reaching. Let’s take, for instance, this 2016 bug in zipimport. It failed to sanitize the header of a ZIP file being processed, causing all the problems one would expect.

It is quite possible that because of the continued popularity and usage of Python2, a third party will step in and take over maintenance of the language, essentially forking Python. Unless such an event happens, it’s definitely time to migrate away from Python2.
Continue reading “This Week In Security: Camera Feeds, Python 2, FPGAs”

36C3: Open Source Is Insufficient To Solve Trust Problems In Hardware

With open source software, we’ve grown accustomed to a certain level of trust that whatever we are running on our computers is what we expect it to actually be. Thanks to hashing and public key signatures in various parts in the development and deployment cycle, it’s hard for a third party to modify source code or executables without us being easily able to spot it, even if it travels through untrustworthy channels.

Unfortunately, when it comes to open source hardware, the number of steps and parties involved that are out of our control until we have a final product — production, logistics, distribution, even the customer — makes it substantially more difficult to achieve the same peace of mind. To make things worse, to actually validate the hardware on chip level, you’d ultimately have to destroy it.

On his talk this year at the 36C3, [bunnie] showed a detailed insight of several attack vectors we could face during manufacturing. Skipping the obvious ones like adding or substituting components, he’s focusing on highly ambitious and hard to detect modifications inside an IC’s package with wirebonded or through-silicon via (TSV) implants, down to modifying the netlist or mask of the integrated circuit itself. And these aren’t any theoretical or “what if” scenarios, but actual possible options — of course, some of them come with a certain price tag, but in the end, with the right motivation, money is only a detail.

Continue reading “36C3: Open Source Is Insufficient To Solve Trust Problems In Hardware”

FPGA 6800 Uses Python Toolbox

Usually, when you think of designing — or recreating — a CPU on an FPGA, you assume you’ll have to use Verilog or VHDL. There are other options, as well, but those are the biggest two players in FPGA configuration. [Robert Baruch] has a multipart series where he uses nMigen — a Python toolbox — to recreate a 6800 CPU like the one used in many vintage video games and pinball machines.

Unlike some tools that try to convert software written in some language to an FPGA configuration, nMigen uses Python as a scripting language to create code in FHDL. This is similar in concept to VHDL or Verilog, but gives up the event-driven paradigm, opting instead to allow designers to explicitly call out synchronous and combinatorial logic.

Continue reading “FPGA 6800 Uses Python Toolbox”

2019: As The Hardware World Turns

Well, this is it. The end of the decade. In a few days the 2010s will be behind us, and a lot of very smug people will start making jokes on social media about how we’re back in the “Roaring 20s” again. Only this time around there’s a lot more plastic, and drastically less bathtub gin. It’s still unclear as to how much jazz will be involved.

Around this time we always say the same thing, but once again it bears repeating: it’s been a fantastic year for Hackaday. Of course, we had our usual honor of featuring literally thousands of incredible creations from the hacking and making community. But beyond that, we also bore witness to some fascinating tech trends, moments that could legitimately be called historic, and a fair number of blunders which won’t soon be forgotten. In fact, this year we’ve covered a wider breadth of topics than ever before, and judging by the record setting numbers we’ve seen in response, it seems you’ve been just as excited to read it as we were to write it.

To close out the year, let’s take a look at a few of the most popular and interesting stories of 2019. It’s been a wild ride, and we can’t wait to do it all over again in 2020.

Continue reading “2019: As The Hardware World Turns”

.NET To FPGA With Hastlayer

There are lots of ways to use FPGAs. One way is to convert compute-bound software into hardware. This can increase speed and — in some cases — reduce power consumption. Typically, you’ll do this by writing in a subset of C, but Hastlayer can convert .NET assemblies into FPGA configurations with some limitations.

The Hungarian company behind Hastlayer claims they’ll eventually have to charge money for something but for now, the tool is free and they are promising to always have some free option. The interesting thing is that the .NET assemblies are essentially object code so you aren’t compiling source but rather an intermediate language that you can generate with many different language tools.

Continue reading “.NET To FPGA With Hastlayer”

Yosys Fronts For Xilinx ISE

We always marvel at how open-source tools can often outstrip their commercial counterparts. Yosys, the open-source tool for Verilog synthesis, is a good example. Although the Xilinx ISE design suite is something close to abandonware, a lot of people still use it because it supports older FPGAs the newer tools don’t. Its Verilog parser is somewhat slow to catch up to new standards, and according to a recent GitHub update, Yosys can now provide files for ISE that target Spartan 6, Virtex 7, and Series 7 FPGAs. In addition, there is some support for Spartan 3, Virtex 2, 4, and 5, although those are not ready yet.

According to the post, you’ll want to use the synth_xilinx command along with the -ise option and a -family option that matches your target (that is, xc6s for Spartan 6).  On the output side, you’ll write an EDIF file using the write_edif command.

Continue reading “Yosys Fronts For Xilinx ISE”