Wednesday, December 19, 2012

Fresh & Easy receipt printer test

Look what I found hanging out of the receipt printer at the self-service checkout at Fresh & Easy (grocery store) the other day:

Some of the screwiness of this image is due to my handheld scanner. The actual receipt was not printed crookedly.

Here's a transcript so people can find this by searching on Google:

--------------------------------------------
   NCR 734x-F307 Printer: Thermal Receipt   
  NCR 71xx Printer/MICR/CD/ChkScan Service
                   Object
   OPOS Spec Compliancy Version: 1.7.000
--------------------------------------------
 OPOS POSPrinter Control 1.10.001 [Public,
             by CRM/RCS-Dayton]
   OPOS Spec Compliancy Version: 1.10.001
--------------------------------------------
         NCR Printer Service Object
     NCR Release File Version: 2.5.1.50
--------------------------------------------
SH/SW: 0123456789:;<=>?@ABCDEFGHIJKLMNOPQRST
DH/SW: 0123456789:;<=>?@ABCDEFGHIJKLMNOPQRST
SH/DW: 0123456789:;<=>
DH/DW: 0123456789:;<=>
--------------------------------------------
              CharacterSet-437
(List-437,737,850,852,858,860,862,863,864,86
   5,866,874,932,1252,101); LineChars-44
                (List-44,56)
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJK
LMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvw
xyz{|}~

Monday, December 3, 2012

Getting git 1.8.0 to work with PuTTY/plink/pageant 0.62

I am successfully running the following things together:

  • Windows 8
  • Git-1.8.0-preview20121022.exe from here
  • PuTTY, plink, and pageant, all version 0.62, from here

I'm not sure if the Startup menu exists any more in Windows 8. To make pageant.exe run at startup and load my key, I used regedit to add a registry value under HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Run. The value is a String, the name can be whatever, and the value should be something like:

"C:\Program Files (x86)\PuTTY\pageant.exe" "C:\your\private\key.ppk"

By default, the version of SSH that ships with msysgit does not try to access pageant. You have to configure git to use plink.exe instead. Lots of people on the internet will tell you that you must set the GIT_SSH environment variable to be the full path to plink.exe, but for some reason that wasn't working for me this time. I'm sure this is not optimal, but my solution was to move plink.exe to "C:\Program Files (x86)\Git\bin\ssh.exe", overwriting the original ssh.exe. (I saved a copy of the of the original ssh.exe just in case I need it later.)

Anyway, it works now so I can continue working on all of my favorite coding projects.

UPDATE: See my new and improved article entitled Git and PuTTY in Windows.

Monday, November 26, 2012

Orientation sensing with the Raspberry Pi and MinIMU-9 v2

The Raspberry Pi is an ideal platform for experimenting with inertial measurement units (IMUs). These IMUs are usually I²C devices, so it is straightforward to access them using the Raspberry Pi's I²C bus. The integrated 3D graphics on the Raspberry Pi are useful for visualizing the results.

I have made some software that allows you to connect the MinIMU-9 v2 from Pololu Robotics & Electronics to your Raspberry Pi and calculate the orientation of the IMU. I also wrote a visualization program that shows the results in 3D. Check out the demo in this video:

The software is open source and I have written a tutorial for it. The only items needed besides your Raspberry Pi setup are:

Soldering is required: the male header pins that come with the MinIMU-9 v2 need to be soldered in.

The MinIMU-9 v2 can be conveniently powered from the Raspberry Pi's 3V3 power line. The photos below show how to connect a MinIMU-9 v2 to a Raspberry Pi:

Wiring

The software consists mainly of two programs, both written in C++. The minimu9-ahrs program reads data from the MinIMU-9's sensors via I²C, calculates the orientation of the IMU, and outputs data to the standard output. Internally, it represents the orientation with a quaternion, but several different output options are available: direction cosine matrix, quaternion, euler angles, and raw sensor data. The ahrs-visualizer program reads direction cosine matrix data from its standard input and displays a 3D representation of the MinIMU-9 v2 using OpenGL. I also used libi2c, libpng, the Boost program_options library, and Eigen. There is a Python script that helps calibrate the magnetometer. For easy installation of the software, I have created Debian packages.

For more information, see the tutorial! I would love to see what people build with this, so please post comments below!

PIC18F14K50 errata: I was right all along

In March 2009 (3.5 years ago), I reported a problem with the PIC18F14K50 on the Microchip forum. This month, they finally added it to the errata list. This should somehow give me more credibility the next time I report a bug to a silicon manufacturer!

Tuesday, July 10, 2012

Atmel Studio bug caused by --Wl,--gc-sections

I have found a bug in Atmel Studio 6.0.1843 (with AVR Toolchain 8 Bit 3.4.663 - GCC 4.6.2) that results in RAM variables being placed starting at address 0x60 instead of 0x100 if the --Wl,--gc-sections flag is enabled and the .data section is empty. This makes the RAM variables overlap with memory-mapped SFRs, so they do not function properly.

You can follow these steps to reproduce the bug:
  1. Make a new project with the GCC C Executable Project template and select the ATmega328P. (I believe this bug affects other parts too.)
  2. In the project properties, check the "Garbage collect unused sections (-Wl,--gc-sections)" checkbox.
  3. Write the following in main.c:
    
    #include <avr/io.h>
    unsigned char foo = 0;
    int main(void)
    {
        while(1){ PORTC = foo++; }
    }
    
  4. Build the project.
Now look at the .map output file. You will see the following line, which indicates that foo is at address 0x60.
                0x00800060                foo
Unfortunately, address 0x60 is the location of WDTCSR, so putting a variable there does not work well.

The problem goes away if you ensure that the .data section is non-empty by making a static variable that is initialized to a non-zero value:
static void __attribute__((used)) workaround(void)
{
    static volatile unsigned char w = 1;
    w++;
}
I believe that Atmel Studio is affected by bug #13697 from GNU binutils.

I hope that the next version of Atmel Studio comes with a patched or updated binutils that does not suffer from this problem. I have reported the bug to Atmel.

Update 2012-07-18: A member of the Atmel AVR Toolchain Team has responded to my bug report. He said: "Thanks. We will have this fix available with our next release."

Wednesday, June 20, 2012

Using I²C on the Raspberry Pi

Last night I succeeded in getting my Raspberry Pi to do some basic I²C (also known as I2C, TWI, or SMBus) communication. I had to look around in a couple different places on the web to figure out how to do it, so I thought I would make this blog post to consolidate the knowledge.

The first step, of course, is to set up an SD card suitable for the Raspberry Pi. I used the official Debian image from the Raspberry Pi Foundation.

Unfortunately, this official image has no support for I²C! You need to enter Chris's Digital Realm for that. Follow the instructions on Chris Boot's site to upgrade your Raspberry Pi firmware and install his Raspberry Pi kernel, which has drivers for I²C. Now if you run lsmod you should see a lot of good stuff, such as the i2c_bcm2708 module.

Once you are running the new kernel, you will need to run sudo modprobe i2c_dev. You should also add i2c_dev to the /etc/modules.conf file so that it loads automatically the next time you boot up the Raspberry Pi. Now you should see two I2C devices:
pi@raspberrypi:~/$ ls -l /dev/i2c*
crw------- 1 root root 89, 0 Dec 31  1969 /dev/i2c-0
crw------- 1 root root 89, 1 Dec 31  1969 /dev/i2c-1

You will need to connect your device to the Raspberry Pi. I used Pololu Female-Female Premium Jumper Wires to make the following connections between the Raspberry Pi's GPIO header and my device:
  • Raspberry Pi GND to device GND
  • Raspberry Pi SCL to device SCL
  • Raspberry Pi SDA to device SDA
  • Raspberry Pi 3V3 Power to device's power input. This line can only provide a few tens of milliamps so you should look up how much current your device draws and make sure you can power it at 3.3 V. The Raspberry Pi's 5V power line is also available.
At this point, you can use simple C system calls to communicate with I2C devices. Here is some code I wrote to read the "Who Am I" register from the LSM303DLM on a Pololu MinIMU-9 Gyro, Accelerometer, and Compass (L3G4200D and LSM303DLM Carrier):
#include <unistd.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <linux/i2c-dev.h>
#include <sys/ioctl.h>
#include <fcntl.h>

#define MAG_ADDRESS        (0x3C >> 1)
#define LSM303_WHO_AM_I_M  (0x0F)

int main()
{
    char buf[10];
    const char * devName = "/dev/i2c-0";

    // Open up the I2C bus
    int file = open(devName, O_RDWR);
    if (file == -1)
    {
        perror(devName);
        exit(1);
    }

    // Specify the address of the slave device.
    if (ioctl(file, I2C_SLAVE, MAG_ADDRESS) < 0)
    {
        perror("Failed to acquire bus access and/or talk to slave");
        exit(1);
    }

    // Write a byte to the slave.
    buf[0] = LSM303_WHO_AM_I_M;
    if (write(file, buf, 1) != 1)
    {
        perror("Failed to write to the i2c bus");
        exit(1);
    }

    // Read a byte from the slave.
    if (read(file,buf,1) != 1)
    {
        perror("Failed to read from the i2c bus");
        exit(1);
    }

    printf("result: 0x%02X\n", buf[0]);

    return 0;
}
When I ran this code, it printed 0x3C which means that it successfully talked to the device! There might be a simpler way to read the register; see the Linux Kernel I2C Documentation.

In conclusion, it was not too hard to get I²C working on the Raspberry Pi. The biggest hurdle is that the official Debian image/kernel has no support for it. This is kind of surprising because the Raspberry Pi team purposefully brought the I²C lines out to their GPIO header and the product has been selling for several months now.

Wednesday, March 21, 2012

The Ruby Enumerable module

When programming in the Ruby language, it is essential to know about the Enumerable module. The more Enumerable methods you know, the more concise and elegant your code will be. The Enumerable module is mixed into many common classes such as Array, Hash, and Range. It is also mixed into some not-so-common classes such as Set, Struct, and Enumerator.

The official documentation of Ruby 1.9.3's Enumerable module is good, but I don't like the alphabetical organization. I think you can understand what's going on better if you group the methods into similar categories. To that end, I have created a Ruby 1.9.3 Enumerable module quick reference. It's a one-page sheet that briefly documents ALL of enumerable's methods. Check it out!

Download links:

Ruby 1.9.3 Enumerable module quick reference (PDF)

Ruby 1.9.3 Enumerable module quick reference (ODS)

Let me know if there are any errors or you think it could be better in some way!

Thursday, March 1, 2012

Doku: solve Sudoku-like puzzles with Ruby!

This week I published my first Ruby gem! It's called Doku and it can solve Sudoku-like puzzles quickly using the Dancing Links algorithm by Donald Knuth. Currently it can solve these types of puzzles:


It takes less than a second to solve Sudoku and Hexadoku puzzles.

Here is some example code:
require 'rubygems'
require 'doku'

puzzle = Doku::Sudoku.new <<END
...|..8|...
..7|.35|..9
5..|4.6|8..
---+---+---
...|..4|2..
4..|...|.37
8..|...|5..
---+---+---
.9.|.67|...
..3|...|1.5
...|...|..3
END

solution = puzzle.solve

puts solution.get(7,8)   # => 9
puts solution            # prints the solution in same format as above

Motivation

Back in July 2011, I saw this puzzle in Elektor magazine:



(That's an SVG image, so you can see it larger!)

This beast is called Hexamurai. It has 768 squares, which is 9.5 times larger than Sudoku. It is made by superimposing 5 Hexadoku (16×16 Sudoku) puzzles on top of eachother. One of the Hexadokus is in the center, and each of the other four is offset by 8 in some direction from the central puzzle.

When I looked at this puzzle I knew two things:
  1. Solving this puzzle is an awesome challenge.
  2. Solving this puzzle by hand is not fun and a waste of my time.

A simple, naive algorithm is not good enough to solve Hexamurai. I learned this the hard way; after my first algorithm languished for hours with no progress I had to abandon it.

It turns out that people have been solving Sudoku-like puzzles efficiently by reducing them to exact cover problems and then using the Dancing Links algorithm. If you're interested, I definitely recommend reading the PDF version of Knuth's paper. It's only 26 pages.

The exact cover problem for that particular Hexamurai consists of 3433 sets that contain 2872 different elements. With Doku, I was able to solve it in about 90 minutes!

That was back in August 2011. Since then, I have spent a lot of time refactoring, polishing, and adding useful features to every part of the gem.

Doku is general

Doku is designed to solve Sudoku-like puzzles. More precisely, it can solve any puzzle consisting of a set of glyphs (i.e. symbols), a set of squares, and a set of groups of squares. Additionally, the number of squares in each group must be equal to the number of glyphs. Given a partial assignment of glyphs to squares, Doku can figure out how to assign a glyph to every square such that no two squares in the same group are assigned the same glyph.

You can define your own puzzle class where the squares and glyphs are any type of Ruby object you want except nil. You are not forced to arrange your squares on a 2D grid: they can have any structure you want.

If you know of any interesting Sudoku-like puzzles that are not already supported by Doku, let me know in the comments and I'll probably implement a class for them!

Doku classes include batteries

Every puzzle class, including Sudoku, Hexadoku, and Hexamurai are well thought out and designed to be generally useful. Each of these classes inherits from a base class (Puzzle) which provides equality comparison, solution checking, and proper behavior for dup and clone. Each class includes a module (PuzzleOnGrid) that provides convenient methods for converting instances to strings and strings to instances (see the example code above).

Doku is elegant

Doku is meant to showcase beautiful Ruby code. Test-driven development was used at all times during the development of this gem. I have spent many hours reviewing the code, looking for ways to make it simpler, and refactoring it. Every class and public method is documented. Every method is short. There are no ugly hacks. All method names were chosen carefully. At every level, the power of the Ruby language is exploited to its fullest potential.

Learn more!


P.S. Here's the solution to that monstrous puzzle:

Sunday, January 22, 2012

Make 3.82 can't handle parentheses in prerequisites

GNU Make 3.82, which is the latest official release of GNU Make, behaves unpredictably when you try to run it with the following Makefile:
a : libawesome.a(x.o y.o)
The above Makefile is a perfectly valid Makefile that uses archive member targets. When you run Make with this Makefile, the expected output is:
make: *** No rule to make target `libawesome.a(x.o)', needed by `a'.  Stop.

But when I ran Make 3.82 (compiled from source) under Ubuntu 10.04 it printed:
make: *** No rule to make target `libawesome.a(x.o', needed by `a'.  Stop.

Note the missing right parenthesis in the target name.

The reason for this incorrect behavior is that there is a serious bug in the source code of Make 3.82 in read.c on line 3031 that causes it to read past the end of a string, which means it is probably reading into unallocated memory, which can cause undefined behavior. If you have the ability to compile Make from source, you can prove this by downloading the Make 3.82 source and adding a two-line if statement to read.c above line 3031:

if (! (flags & PARSEFS_NOAR)
          && tp == tmpbuf && tp[0] != '(' && tp[nlen-1] != ')')
        {
          char *n = strchr (tp, '(');
          if (n)
            {
              /* This looks like the first element in an open archive group.
                 A valid group MUST have ')' as the last character.  */
              if (nlen > strlen(p) + 1)
                printf("About to read past end of string!  p = %s, nlen = %d\n", p, nlen);
              const char *e = p + nlen;
              do
                {
                  e = next_token (e);
When you compile and run this modified version of Make with the Makefile above, it should print something like:
About to read past end of string!  p =  y.o), nlen = 16
make: *** No rule to make target `libawesome.a(x.o', needed by `a'.  Stop.
Here's the problem: the pointer p is already pointing to the end of the current token, so adding nlen (the length of the current token) makes no sense and can cause Make to read past the end of the string. The memory after the end of the string is probably unallocated memory, so when the program tries to read from it this is undefined behavior: anything can happen!

The solution to this bug is to remove the "+ nlen". This solution appears to prevent Make from crashing, but it looks like there are still more bugs with archive target groups that are not fixed by this simple change.

The bug was actually fixed a long time ago


This bug was reported by Peter Breitenlohner on July 31st, 2010 as Savannah bug #30612 and fixed by Paul Smith, a maintainer of GNU Make. Unfortunately, there hasn't been a new release of GNU Make since then. Until there is a new release of GNU Make, people can keep using GNU Make 3.81 or they can use the version 3.82-pololu2 which I just released the other day. It contains the fix discussed above and another fix that affects Windows users who have a parenthesis in the path to their shell.

Based on the timestamps at ftp://ftp.gnu.org/gnu/make/ it looks like new release of Make only happen about every 4 years, so it would be a while before we have a new release.


How I found the bug


This was a tricky bug to find. If you're interested in debugging open source C programs you might want to know how I did it.

A while ago, some users of the Wixel SDK were erratically getting a non-sensical error from GNU Make in Windows which was preventing them from building their Wixel apps.

Initially, tracking the bug down was frustrating. I eventually managed to reproduce the bug on my computer, but it was very slippery: sometimes Make would run fine, sometimes it would display the non-sensical error, and sometimes it would just crash with an Access Violation error when trying to read from an invalid address. Almost any perturbation to the environment would cause it to switch randomly between these three behaviors. Deleting an empty folder sitting in the current directory, switching to a different Command Prompt, or piping the output of Make to a file: any of these changes would change the result of running Make, sometimes permanently.

But the most frustrating thing was that Make would never crash when it was running in gdb. I was compiling Make with MinGW with debug options enabled and attempting to debug it with gdb, but it would never crash in gdb so I could not get a stack trace.

Whenever Make did crash, its exception handler would print the address of the code where it crashed and I could use gdb to convert that address to a file name and line number. That turned out to be a dead end because it was crashing in a very simple function that was called from many places (next_token).

I knew there must be a way to get a stack trace in situations like this, so I searched around and found DrMingw by José Fonseca. It was easy to install and use. After downloading it, I extracted it to a folder in "Program Files (x86)", put it on my PATH, ran Command Prompt as Administrator, and ran "drmingw -i" to install it as the Just-In-Time Debugger on my system. I commented out the call to SetUnhandledExceptionFilter in main.c so that the exception would be handled by Windows instead of by Make's own exception handler. I got Make to crash again. When the standard Windows crash dialog came up, I clicked "Debug" to launch DrMingw and it opened a window with a full stack trace with file names and line numbers. Here is an excerpt:
Call stack:
0041A930  gnumake.exe:0041A930  next_token  misc.c:511

 ...
 next_token (const char *s)
 {
>   while (isblank ((unsigned char)*s))
     ++s;
   return (char *)s;
 ...

00415AA8  gnumake.exe:00415AA8  parse_file_seq  read.c:3038

 ...
               do
                 {
>                   e = next_token (e);
                   /* Find the end of this word.  We don't want to unquote and
                      we don't care about quoting since we're looking for the
 ...
I looked in read.c around line 3038 and found that it was a block of code that had to do with parsing archive member targets in make. From there is was pretty easy to find the bug.