Fighting spam with GMail

This won't be a post related to programming. However I find this useful to fight spam with GMail.

I usually get a lot of spam in my gmail account, probably because my name and surname are quite common (?) or who knows why. GMail filters spam quite good and once they're detected they're are sent to the Spam tab/mailbox. Since no system is perfect there are some non-spam emails that are treated as spam by gmail so I spend/waste some minutes every day to see if I can rescue a misreported spam email.
I know most of the spam contain some specific words so I tried using google's search engine inside GMail to simplify this horrible task. Here is what I copy-paste to the GMail search bar:

in:spam pharmacy | cialis | viagra | replica | rep1ica | buy | cird | bedroom | watches | pills

The OR operator works great and then I can delete the messages that meet that criteria without worrying (well, I do worry a little but less than deleting them without any filter at all).

I can say that 60% to 80% of spam I get contain one of those words.

_

openAHRS: Extended vs Unscented Kalman Filter

I've been thinking on openAHRS lately. Some days ago I found Sean D'Epagnier in FreeNode's #avr channel (IRC) and we started talking about his project and openAHRS, regarding sensor calibration and how things could evolve from now on.

Sean mentioned about the Sigma Point Kalman Filter (SPKF) and that it might improve performance for non-linear systems. I started searching for

papers on the Unscented Kalman Filter (UKF) and other information related to it.

After some tests I decided to compare the UKF with the EKF (Extended Kalman Filter) to see how good improvements are, and here are the results.

All input data was measured from the AVR32 openAHRS port. There are no precise calibrations, only some minor magnetometer ones and nothing else. The data was exported and UKF and EKF were implemented in Matlab.

The filters were tested under three different cases by exciting each rotation angle independently (or at least as far as independent as my hand could do it). There are peaks in the raw angles which are measured from accelerometer data, since a big deacceleration happened when I hit the table (on purpose) when I was getting close to 0 degrees.

I forgot to add the axis labels, but angles are shown in radians on the y-axis and time (in samples at 50Hz) is on the x-axis.

Results of exciting the Roll axis

Both filters did well: EKF / UKF. UKF did converge faster to a true value than EKF. I have to mention that the noise covariance matrices were the same for both filters.

Results of exciting the Pitch axis

Something similar to the case above happens. Here is the EKF one and there the UKF. It seems that I've disturbed the other axis I shouldn't have modified.

Results of exciting the Yaw (heading) axis

The yaw angle input is not affected from acceleration, at least not if the predicted pitch and roll are precise enough. This happens because yaw is calculated by using magnetic field sensing, so it will be quite accurate compared to the accelerometer readings. Here are the EKF results and here the UKF ones.

The EKF is a mess and the UKF doesn't do so well either. This has a simple explanation: lack of magnetometer calibration. I'll be adding some suggested code by Sean to see if it improves.

EKF and instability

The serious problem with EKF is instability. When playing around with the noise variance matrices (both measurement and process noise) there are certain points where the filter loses stability.

It's very important to let the states and noise matrices adapt to the system and noises before perceptible movements are applied to the sensors. A way to avoid this is to save the state covariance matrix P so that the kalman filter only needs a small time to adapt once powered up.

All these concepts apply to UKF except that it is much more stable. I was able to 'play' with the noise matrices in a free way. It's important to notice that UKF converges much faster than EKF at startup, probably because of the second and third order predictions EKF is not able to compute.

Kalman Tuning

The filter won't work without a minimal knowledge of how and what it is doing. It's important to understand what each coefficient in the noise matrices mean. For example, the filter needs to know that it should believe in the gyro bias estimates much more than in the accelerometers so that gyro data becomes credible in short-term measurements so tilt information does the same for long-terms. This also means that the gyro bias estimates will remain practically constant, changing their value slowly and thus adapting to temperature and time drifts.

To do

There is a large ToDo list:

• Test if the EKF can be improved, specially the heading axis.
• Implement SQ-UKF (Square Root KF) and/or UD-UKF since the classic UKF is really slow because of the matrix square root calculation.
• Implement a robust calibration routine for all the sensors. Sean told me some nice ideas that could greatly improve precision.

Quick text compression

Recently I faced a problem related to short text compression. The idea was to reduce the space needed to save SMS messages. Since each SMS contains up to 160 characters the classic LZW or Huffman methods won't work out-of-the-box, mostly because of the size of the resulting dictionary. It is even worse if we consider that most messages are less than 80 characters long.

Finally I decided to use a fixed dictionary and a sort of hybrid Huffman code compression (which isn't Huffman at all, but it retains some similarity -somehow). Then I started looking for letter, digraph and trigraph probability in words and texts. There are many resources on the net like this and this one where symbol probability is listed for different languages, including Spanish which was the one I used.

The compression algorithm tries to use the minimum number of bits to encode frequent letters/digraphs/trigraphs. It is not optimal since the dictionary is fixed but it does a good job, reducing message size to 60-70% on most cases. If the right text is picked then it can be reduced to 30% but that is cheating, of course! The space character is one of the most used ones along with the 'e' letter (Spanish at least). Trigraphs and digraphs also play an important role in compression.

Lower/uppercase letters is another issue, but since SMS messages are mostly written in lowercase or uppercase that is not a problem. A trick is to invert the whole text to see which text gets the best compression ratio. This is quite fast since the algorithm is simple and the strings are short. Another trick would be to provide more than one dictionary (maybe three or four) and see which one does better with the desired message. The resulting space overhead is about two or three bits which should be acceptable for long messages.

Another possibility is to compress many messages together with Huffman or any other compression method. The drawback is that the message won't be a unit itself and then message management becomes messy.

Dirty little bugs - a pin/macro approach

Program testing can be used to show the presence of bugs, but never to show their absence!

Edsger W. Dijkstra

/-

Measuring and observing usually (if not always) change what one is measuring. I've never seen Schrödinger's cat, at least not when leading with embedded systems nor in my garden, but the former implication causes many problems when trying to debug time-critical functions/operations in embedded software and hardware.

Usually a printf-like UART output works but that would slow down or even hang code which can't wait for the UART to stream its data out. Even though with a substantial buffer it will come a time where it will get stuck.

There is a nice, well known techinque, that uses output pins to reflect some state, such as which function or interrupt handler the microcontroller is doing at the time. Since setting the output value requires only a few instructions, this approach suits better the time-critical scenarios. This technique is helpful in many ways: one may measure from interrupt latency and cpu usage to interrupt or thread deadlock.

That's how the following code came up to mind, here is a simple header file which is based on the macros I posted some time ago here.

#ifndef _dbgpin_h_
#define _dbgpin_h_

#include "portutil.h"

/* Enables or disables debugging */
#if    DBGPIN_ENABLED 1

/* Debug pins */
#define DBGPIN_01    0,2
#define DBGPIN_02    0,3
//---- etc

/* Initialization */
#define DBGPIN_INIT( pin )    do { FPIN_AS_OUTPUT(pin); FPIN_CLR(pin);  } while(0);

/**
* Beware of returns, exclude them!
*/
#if    DBGPIN_ENABLED
#define DBGPIN_BLOCK( pin, block ) \
           FPIN_SET_( pin ); \
           do { \
               block \
           } while(0); \
           FPIN_CLR_( pin );
#else
#define    DBGPIN_BLOCK( pin, block ) block
#endif

#endif /* _dbgpin_h_ */

Here is an example:

DBGPIN_BLOCK( DBGPIN_01,
a = b;
callSomething();
);

There is a small drawback: the do-while structure won't let any variable declared inside 'block' to be visible outside. That can be solved by removing the do-while, if you need it that way just go ahead and delete those two lines.

Also notice that a return in 'block' won't allow the macro to clear the corresponding pin, so applying the macro to a function with many return points is messy. The alternative is to change the original function's name and call it through a sort of wrapper which does it inside a DBGPIN_BLOCK macro. It's not pure beauty but it works nice, and once you've done the debugging it can be disabled by changing DBGPIN_ENABLED to 0.

Qt-Embedded and busy-waiting

Qt-embedded is astonishing. I'm currently developing a product which uses embedded linux, color 800x480 LCD and touchscreen. Qt-embedded does really nice, faster than gtk on DirectFB and much better-looking.

However, qt won't show any notification to the user when it is busy, be it refreshing an window, loading a frame, etc. This behaviour is somewhat expected, but on a product I'm developing the user needs to be notified (somehow) that the application is doing alright but is busy, so the [in]famous sand clock jumps in.

Since it's a touchscreen device the mouse cursor was disabled when compiling Qt, and in the end it was better since it looks like only B/W cursors are supported on embedded linux (or at least in this platform?).

I thought of a trick by using QTimer, and later I found out some posts when googling. Here is what I finally did:

#ifndef _busy_notify_h_
#define _busy_notify_h_

#include <QTimer>
#include <QApplication>

/**
* Class to show a bitmap inside a widget when
* the event loop is busy.
*/


class BusyNotify : QObject
{
  Q_OBJECT

public:
  // Call to initialise an instance
  static void init();

  BusyNotify();
  /**
  * Show the busy cursor,
  * it will disappear once the event loop is
  * done and the timer times out */
  void showBusyCursor();

private:
  bool waiting;
  int screenWidth, screenHeight; //cached

public slots:
  void TimerTimeout();
};

// This should be the one used
extern BusyNotify *BusyNotifier;

#endif

#include "BusyNotify.h"

#include <QPixmap>
#include <QPainter>
#include <QDesktopWidget>
#include <QLabel>

BusyNotify *BusyNotifier;

static QPixmap *waitPixmap;
static QTimer *timer;
static QWidget *widget;

void BusyNotify::init()
{
  BusyNotifier  = new BusyNotify();

  //load sand clock image
  waitPixmap  = new QPixmap( "icons/png/sand_clock.png" );

  timer = new QTimer();
  timer->setInterval( 100 ); //this could be less..
  timer->setSingleShot(false);

  Qt::WindowFlags flags = Qt::Dialog;
  //flags |= Qt::FramelessWindowHint;
  flags |= Qt::CustomizeWindowHint | Qt::WindowTitleHint;
  flags |= Qt::WindowStaysOnTopHint;

  widget = new QWidget( NULL, flags );
  widget->setWindowTitle("Wait...");

  QLabel *lbl = new QLabel( widget );
  lbl->setText("");
  lbl->setPixmap( *waitPixmap );
  lbl->setAlignment( Qt::AlignCenter );

  widget->resize( waitPixmap->width() + 2, waitPixmap->height() + 2 );
  widget->move( screenWidth/2 - widget->width()/2, screenHeight/2 - widget->height()/2 );

  connect( timer, SIGNAL(timeout()), BusyNotifier, SLOT(TimerTimeout()) );
}

BusyNotify::BusyNotify() : QObject()
{
  waiting = false;
  screenWidth = QApplication::desktop()->screenGeometry(0).width();
  screenHeight = QApplication::desktop()->screenGeometry(0).height();
}

void BusyNotify::showBusyCursor()
{
  if ( !waiting )
  {
      widget->setVisible(true);

      // this will force the widget to show up
      // as fast as possible
      QApplication::processEvents();

      waiting = true;
      timer->start();
  }
}

void BusyNotify::TimerTimeout()
{
  widget->setVisible(false);
  timer->stop();
  waiting = false;
}

After defining the source and header files above one just needs to call BusyNotify::init() once, at program startup, and then BusyNotifier->showBusyCursor() any time the sand clock is needed. 'showBusyCursor()' comes from an old version based on the mouse busy cursor.

How it works

This class works fine when processing or loading (widgets, etc.) is done in the main loop which is also Qt's event processor. When calling showBusyCursor() Qt will be forced to show the sand clock. Then processing can be done and the QTimer will timeout whenever Qt is able to process events once again (since the 100mseg delay is small enough), so the sand clock will remain on the screen as long as needed. Of course, if processing is done in another thread this won't work, but that's not what it is intended for.

GIT and CR/LF-ing

I recently started using git and it's amazing. Since I do many of my work in Windows I use msysgit which does a nice job. 

However, there are some issues regarding the famous <CR><LF> line endings: git will try to convert single <LF>'s to <CR><LF>'s by defaut. Recalling the previous post about automatic build number generation, git will warn about single <LF> termination on some files, specially the ones generated by sh under Windows.

Fortunately, the git docs discuss every detail about customization and git itself. To force git to leave the files as is and forget about line terminations the file .git/info/attributes should be modified by adding something like this (and created if it doesn't exist yet):

file_to_ignore -crlf
another_file_to_ignore -crlf

That way git will just ignore the single-LF ending inside the specified files. Wildcards are also possible.

Another nice trick that has nothing to do with line termination is the file .git/info/exclude which tells git to exclude certain files from the repository (wildcards allowed too).

Automatic build number generation

Version tracking is essential for several reasons. Without a proper versioning system it's difficult to know if this or that firmware contains certain update or feature, specially if one forgets to increment the version number.

That's where the build number appears, assigning a unique number per build (or 'make' in this special case). That way it can't go wrong. Version number is still there but there is also a build number, uniquely defining the release.

I usually never reset the build number, so even if the version number jumps (modified manually) the build number will always increment. It's not mandatory, it depends on how you feel about it.

Implementation

Here is an automatic build number generator. It's a shell script based on sh. I used it with Windows without any problems as long as sh and friends are available on the system path.

#!sh
# FILE: make_buildnum.sh
version="`sed  's/^ *//' major_version`"
old="`sed  's/^ *//' build.number` +1"
echo $old | bc > build.number.temp
mv build.number.temp build.number
#versión..
echo "$version`sed  's/^ *//' build.number` - `date`" > version.number
#header
echo "#ifndef BUILD_NUMBER_STR" > build_number.h
echo "#define BUILD_NUMBER_STR \"`sed  's/^ *//' build.number`\"" >> build_number.h
echo "#endif" >> build_number.h

echo "#ifndef VERSION_STR" >> build_number.h
echo "#define VERSION_STR \"$version`sed  's/^ *//' build.number` - `date`\"" >> build_number.h
echo "#endif" >> build_number.h

echo "#ifndef VERSION_STR_SHORT" >> build_number.h
echo "#define VERSION_STR_SHORT \"$version`sed  's/^ *//' build.number`\"" >> build_number.h
echo "#endif" >> build_number.h

In order to make it work a file named major_version has to be created. It should contain something like "1.02." (no double commas). A file called build.number is also needed. It will be the starting build number like "1". Version number won't be modified but build number will be incremented each time make_buildnum.sh is executed. In order to be useful for C programming the header file build_number.h is updated to reflect both build.number and major_version.

I usually create a makefile dependency to perform automatic build number generation by adding something like this to the Makefile:

# main rule
all: build_number.h $(TARGET).whatever $(TARGET).other
   @whatever rules

# rule for build number generation
build_number.h: $(SOURCES)
   @echo
   @echo Generating build number..
   sh make_buildnum.sh

A new build number is assigned every time a source file is modified. There can be other approachs too like generating a new build number even if no files were modified.

IMPORTANT: Under Windows care must be taken with CR and CRLF line endings. The files build.number and major_version have to be terminated with CRLF, otherwise sed and the other linux/unix utils won't be able to parse them.

Finally here is an example of what build_number.h looks like:

#ifndef BUILD_NUMBER_STR
#define BUILD_NUMBER_STR "1234"
#endif
#ifndef VERSION_STR
#define VERSION_STR "1.0.1234 - Fri Dec 19 11:00:23 HSE 2008"
#endif
#ifndef VERSION_STR_SHORT
#define VERSION_STR_SHORT "1.0.1234"
#endif

The bash script is easy to modify if any other information is needed, such as build number as a proper integer if some preprocessing is needed.