header image
The OFF button
September 26th, 2011 under Fun, rengolin, Stories. [ Comments: none ]

Geeks like to hack stuff, especially if they’re not meant to be hacked. But hacking computers or mobile phones is piece of cake, so some, more adventurous geeks hack cars. The Toyota Prius is a particularly interesting car to hack, since a lot of its functionality is based on control systems and they have interface ports that you can plug in debug systems and change (or add) behaviour to your car.

For instance, you can enable the SatNav screen to play video CDs or MP3s, since the system supports it, but there aren’t enough buttons on the panel and, well, you shouldn’t be watching videos while you drive, anyway.

Another less common hack, but doable is to change the voice commands. They’re normally hard-coded to respond when you press a button on the steering wheel and say something. For instance, on my Prius, if you say “fire photon torpedoes” it puts the air condition temperature down a bit. If you say “Khaaaaaaaan!” it turns off the radio, and so on.

Some controls are a bit less harmless, like activating the breaks or turning off the car, but normally you can’t access them from the control panel, anyway. That is, unless you by-pass the CAN network and connect the central control with the control panel.

Legend tells that a geek bypassed the system and, just for fun, added a voice command to turn off the car when he’d say “off“. That was his pride and joy, and (geek) friends would go jealous of his control over his car. Until the day the car was too old and he decided to buy a new one, with even more technology. Only he forgot to disable the “off” button.

A few months later, they say, the new owner was having a fight with his girlfriend on M11 at full speed and, well, as many would do in those circumstances, he was swearing a lot. Loudly. His unfortunate last minute of life began when he accidentally pressed the “talk” button and said something along the lines of “f*** off …”.

The car dutifully acknowledged the command and, since the previous owner forgot to add any security checks, turned itself off at once. Havoc and carnage followed, but that’s another story.

Now you know why Toyota voids your warranty when you open the panel…


FreeCell puzzles solver API
September 25th, 2011 under Algorithms, Devel, Fun, Games, rengolin. [ Comments: 2 ]

This is a little pet project I did a while ago. It’s a FreeCell puzzle‘s solver API.

The idea is to provide a basic validation engine and board management (pretty much like my old chess validation), so people can write FreeCell solvers on top of it. It has basic board setup (of multiple sizes), movement legalisation, and a basic Solver class, which you must derive to create your own solvers.

There’s even a BruteFroceSolver that can solve a few small boards, and that gives you an idea on how to create your own solvers. However, the API is not clear enough yet that children could start playing with it, and that’s the real goal of this project: to get kids interested in solving complex optimisation problems in an easy way.

Freecell is a perfect game for it. Most boards can be solved (only a handful of them were proven – by exhaustion – not solvable), some movements can be rolled back and you can freely re-use cards that have already been placed into the foundations (their final destination) back in the game again.

It’s out of the scope of this project to produce a full-featured graphic interface for kids, but making the API easy enough so they understand the concepts without dragging themselves into idiosyncrasies of C++ is important.

Compiler optimisations

The reason why I did this was to make some of the optimisations compiler engineers have to do more appealing to non-compiler engineers or children with a taste for complex problems. But what does this have to do with compilers? The analogy is a bit far-fetching and somewhat reverse, but it’s interesting nevertheless and it was worth the shot.

Programming languages are transformed into graphs inside the compiler, which should represent the intentions of the original programmer. This graphs are often optimised multiple times until you end up with a stream of instructions representing the source code in the machine language.

Ignore for now the optimisations on those graphs, and focus on the final part: selecting machine instructions that can represent that final graph in the machine language (assembly). This selection can pick any assembly instruction at will, but it has to put them into a very specific order to represent the same semantics (not just syntactic) of the original program. Since many instructions have side effects, pipeline interactions, special flags set or cleaned up, it’s not trivial to produce correct code if you don’t check and re-check all conditions every time. This is a known complex optimisation problem and can be responsible for changes in speed or code size in orders of magnitude.

What does it have to do with the Freecell puzzle? Well, in Freecell, you have a number of cards and you have to put them in a specific order, just like assembly instructions. But in this case, the analogy is reverse: the “sequence” is trivial, but the “instructions” are hard to get.

There are other similarities. For example, you have four free cells, and they can only hold one value at a time. They are similar to registers, and manipulating them, gives you a good taste of how hard it is to do register scheduling when building the assembly result. But in this case, it’s much harder to spill (move the data back to memory, or in this case, card back to cascades), since there are strict rules on how to move cards around.

Reusing cards from the foundations is similar to expanding single instructions into a sequence of them in order to circumvent pipeline stalls. In real compilers you could expand a multiply+add (very useful for digital signal processing) into two instructions: multiply and add, if that gives you some advantage on special cases on special chips. In Freecell, you can use a 9 on top of a 10, to move an 8 from another cascade and free up a card that you need to clean up your freecells (registers).

I’m sure you can find many more similarities, even if you have to skew the rules a bit (or completely reverse them), but that’s not the point. The point is to interest people into complex optimisation techniques without the hassle of learning a whole new section of computer science, especially if that section puts fear in most people in the first place.


 


License
Creative Commons License
We Support

WWF

EFF

National Autistic Society

Royal Society for the Prevention of Cruelty to Animals

DefectiveByDesign.org

End Software Patents

See Also
Disclaimer

The information in this weblog is provided “AS IS” with no warranties, and confers no rights.

This weblog does not represent the thoughts, intentions, plans or strategies of our employers. It is solely our opinion.

Feel free to challenge and disagree, and do not take any of it personally. It is not intended to harm or offend.

We will easily back down on our strong opinions by presentation of facts and proofs, not beliefs or myths. Be sensible.

Recent Posts