Tuesday, January 27, 2009

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.

Friday, January 16, 2009

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.

Sunday, January 4, 2009

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.

Friday, December 26, 2008

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).

Wednesday, December 17, 2008

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.

Thursday, December 4, 2008

Embedded C++ constructs - Part 2

As mentioned in part 1, I'll now get into an UART example, providing the basic functionality through a class. This example works with the LPC ARM7 family from NXP Semiconductors (Philips).

Register abstraction

First here is how I abstract a hardware register. It's nothing special but a simple template class:



namespace HW
{
/**
* Individual HW register
*/
template < unsigned long int BASE, unsigned long int OFF >
class Reg
{
public:
void operator = (const unsigned long int & val) {
*((volatile unsigned long int *)(BASE + 4*OFF)) = val;
}

unsigned long int & operator = ( const Reg & reg ) {
return *((volatile unsigned long int *)(BASE + 4*OFF));
}

operator unsigned long int () {
return *((volatile unsigned long int *)(BASE + 4*OFF));
}
};

};

(I used C-like casts here but it would be better to use reinterpret_cast<> instead)


Three operators are implemented. It's essential to be able to cast the class to an unsigned int so we can use it transparently.

The template parameters let us provide a base and offset address which will be useful when a peripheral is abstracted through a template class.

UART peripheral abstraction

The UART peripheral in the LPC2xxx family consists of a collection of registers, starting from a base address. There are some interesting bits lying around on the microcontroller too that control peripheral power, the peripheral's clock and associated interrupts. Here all of them are encapsulated in a single class, except for the interrupts (to do).



namespace HW
{
/**
* UART Module Abstraction
*/
template<unsigned int BASE, unsigned int PCON_BIT, unsigned int PCLK_SEL>
class RegUART
{
public:
void powerOn() {
PCONP |= (1<<PCON_BIT);
}

void setClkDiv( unsigned int divv ) {
PCLOCK_SELECT( PCLK_SEL, divv );
}

HW::Reg<BASE, 0> RBR;
HW::Reg<BASE, 0> THR;
HW::Reg<BASE, 0> DLL;
HW::Reg<BASE, 1> DLM;
HW::Reg<BASE, 1> IER;
HW::Reg<BASE, 2> IIR;
HW::Reg<BASE, 2> FCR;
HW::Reg<BASE, 3> LCR;
HW::Reg<BASE, 5> LSR;
HW::Reg<BASE, 7> SCR;
HW::Reg<BASE, 8> ACR;
HW::Reg<BASE, 9> ICR;
HW::Reg<BASE, 10> FDR;
HW::Reg<BASE, 12> TER;
};
};

#define HWUART0 HW::RegUART< UART0_BASE_ADDR, PCLK_UART0, PCLK_UART0 >
#define HWUART1 HW::RegUART< UART1_BASE_ADDR, PCLK_UART1, PCLK_UART1 >
#define HWUART2 HW::RegUART< UART2_BASE_ADDR, PCLK_UART2, PCLK_UART2 >
#define HWUART3 HW::RegUART< UART3_BASE_ADDR, PCLK_UART3, PCLK_UART3 >

PCONP and PCLOCK_SELECT() are macros defined in another file, nothing special.

HWUARTx are macros that help when specifying certain port. It will be used in the next piece of code.



#include <string.h>

namespace Drivers
{
/**
* LPC2xxx UART Peripheral
* Polled.
*
* @param T Hw::RegUART
* Use HWUART0, HWUART1...
*/
template< class T >
class PolledUart
{
private:
T UART;

public:

/**
* Init UART
*
* @param brate desired baudrate
*/
void init(unsigned int brate) {

UART.setClkDiv( PCLK_DIV_1 );
UART.powerOn();

UART.LCR = 0x80; //DLAB = 1

UART.DLL = (Fpclk/16)/brate & 0xFF;
UART.DLM = (((Fpclk/16)/brate) >> 8) & 0xFF;

UART.LCR = 3 | //8 bit char length
(0<<2) | // 1 stop bit
(0<<3) | //no parity
(0<<4) | //partity type
(0<<6) | //disable break transmission
(0<<0) ; //enable access to divisor latches

UART.FCR = (0x07); //FIFO ENABLE, Rx & Tx
}

/**
* Transmit a single byte
*
* @param c
*/
void tx( unsigned char c ) {
while ( !( UART.LSR & (1<<5) ) )
;
UART.THR = c;
}

/**
* Transmit several bytes
*
* @param data data to transmit
* @param length length of 'data'
*/
void tx( const unsigned char *data, unsigned int length ) {
while( length-- > 0 )
tx( *(data++) );
}

/**
* Transmit a C string
*
* @param str
*/
void tx( const char *str ) {
tx( (const unsigned char *) str, strlen(str) );
}

/**
* Byte receive
* BLOCKING
*
* @return unsigned char received char
*/
unsigned char rx(void)
{
while ( !( UART.LSR & (1<<0) ) )
;

return UART.RBR;
}

/**
* Returns if there is data to be read in the FIFO
*
* @return bool true if there is data available
*/
bool isDataAvailable(void)
{
if ( UART.LSR & (1<<0) )
return true;
else
return false;
}
};
};

PolledUart implements UART basic functionality. No constructor is used to avoid undesired code creation, so init() must be called before using any other function.

Even though this class contains a RegUART class as a private member it won't take any extra memory since the compiler (at least gcc-elf-arm here) will optimize the template. I did some tests and there is no difference in code size with a simple C function doing the same statements directly.

Finally, to see how it works, if we wanted to use UART0 through this class we could instantiate it like this:



Drivers::PolledUart< HWUART0 > Uart0;

void testUart0()
{
Uart0.init(115200); //init @ 115200 bps

Uart0.tx("Hello there!\n");
}

If the class is to be used by many C++ files one should consider declaring it extern inside a header file and implementing it in a single cpp one. That would save code by avoiding function inlining each time it's used.

Improvements

This is just a basic version to demonstrate how easy and clean code can get. Here are some modifications that will make the class more useful:

  • If there is an RTOS it would be useful to protect this class from concurrent access by using semaphores. It's not a difficult task, a mutex should be declared and initialized (maybe inside a constructor).
  • An interrupt-based uart is nice too, even better if RTOS' messages queues are used. This shouldn't be a problem either.

Tuesday, December 2, 2008

Embedded C++ constructs - Part 1

There has been a big explosion about using C++ within embedded systems. Recently David sent me some interesting papers and info about Embedded C++ so here I present what I've been doing so far (or at least a small portion of it).

Templates

First I have to say that templates are not a code bloat if they're managed with care. In fact the C++ compiler is supposed to optimize them at compile time.

Here are some base templates I've coded to ease pin mapping on the LPC23xx ARM family.



#include "lpc24xx.h" /* LPC23/24xx register definitions */
#include "static_assert.h" /* static assert for non-C++0x compilers */

namespace HW
{
/**
* Output Pin Abstraction
*/
template<unsigned int port, unsigned int pin>
class OutPin
{
STATIC_ASSERT(pin <= 31, PinMustBeLessThan32);

public:
OutPin() {
*(&FIO0DIR + 8*port) |= (1<<pin); //configure pin as output
}
void Set(void) { *(&FIO0SET + 8*port) = (1<<pin);}
void Clr(void) { *(&FIO0CLR + 8*port) = (1<<pin);}
};

/**
* Input Pin Abstraction
*/
template<unsigned int port, unsigned int pin>
class InPin
{
STATIC_ASSERT(pin <= 31, PinMustBeLessThan32);

public:
InPin() {
*(&FIO0DIR + 8*port) &= ~(1<<pin); //configure pin as input
}

operator bool () {
if ( (*(&FIO0PIN + 8*port)) & (1<<pin) )
return true;
else
return false;
}
};
};

This may look a like waste of code at first glance. However these classes avoid many mistakes and provide a hardware independent interface to pin outputs and inputs, it's just a question of redefining this templates to fit the platform.

Also note that the compiler will throw an error if pin's value is not within the allowed range. This is also a protection and won't waste any processor instructions or any other memory. It would be useful to limit the port range too. The above templates use the static assert method described earlier in this post.

The constructors will manage to configure the port pin as output or input. If the pin is defined globally then the constructor will be called before entering the main function, configuring the pin as it should. If it is defined inside a function or by using the new operator (which I would try to avoid)  then the constructor will be called when it is instantiated.

Here is an example:



// Pin 0.25
HW::OutPin< 0,25 > myLed;
// Pin 1.20
HW::InPin< 1,20 > mySwitch;

void invert(void)
{
if ( mySwitch )
myLed.Clr();
else
myLed.Set();
}

Beautiful, isn't it? The generated code (arm-elf-gcc 4.2.x) is exactly the same as if it is done manually by writing/reading the corresponding registers. There is no loss in performance compared to the equivalent C code.

In the next post I will discuss a UART implementation by using similar code constructions.

What I do not like about C++

C++ lacks many useful C99 characteristics and g++ doesn't implement them either. I could live without most of them but what really hurts me is to avoid using Designated Initializers, specially on structs. It won't be a big problem if struct's data is on RAM but it's disappointing when structs are on ROM (const).

If we want a struct to be in ROM while using C++ it has to be declared const, but in addition constructors can't be used or the const-declared struct will be placed in RAM (cRazY). It is an understandable limitation but that means that the only way to initialize a struct is by passing each element one by one and in the exact order as they're defined in the struct. That is error prone, particularly when a new element is added in the middle of the struct. So when we try to switch to C++ to avoid errors we become prone to issues that were solved with C99.

So, that's the only thing I don't like about C++, the solution? Use C for cont struct initializers and C++ for the rest? Don't know.