Random number generator based on normal distribution with Boost

Yesterday I was looking for some random number generator, based on gaussian distribution. As I don’t like to reinvent the wheel, I started to look for some already existing solutions. I found out that Boost library provided a very powerful engine for generating random numbers using various algorithms. The whole description of Boost Random Number library is available here.

For those who are looking for already existing solutions I attach a small snippet, which generates random numbers basing on the normal distribution. As typical for gaussian distribution, the algorithm takes two parameters: mean value and sigma(variance).

#include  
....

double 
GetRandomDoubleUsingNormalDistribution(double mean,
                    double sigma)
{
 typedef boost::normal_distribution NormalDistribution;
 typedef boost::mt19937 RandomGenerator;
 typedef boost::variate_generator GaussianGenerator;

  /** Initiate Random Number generator with current time */
  static RandomGenerator rng(static_cast (time(0)));

  /* Choose Normal Distribution */
  NormalDistribution gaussian_dist(mean, sigma);
 
  /* Create a Gaussian Random Number generator
   *  by binding with previously defined
   *  normal distribution object
   */
  GaussianGenerator generator(rng, gaussian_dist);
 
  // sample from the distribution
  return generator();
}

Fuzzy Logic Controller

This project is an exemplary application of fuzzy logic for controlling different types of processes. I wrote it for an Artificial Intelligence course in Windesheim University of Applied Sciences. The assignment is composed of four components:

  • Knowledge base
  • Knowledge base parser
  • Fuzzy Logic Controler
  • Controlled process

Read More

Distributed Game of Life with OpenMPI

Game of Life is a simple simulation developed by John Conway. It uses a 2 dimensional array of cells, in each every cell can be either “alive” or “dead”. At each iteration of the process the application logic decides what will be the next status of the cell. This is done basing on the number of adjacent alive cells (including diagonals), and a set of following rules:

  • If a cell has three neighbors that are alive, the cell will be alive. If it was already alive it
    will remain so, and if it was dead it will become alive.
  • If a cell has two neighbors that are alive, there is no change in the state of the cell
  • In all other cases the cell will be dead

Read More

GObject and protected fields – simple hack

Not so long ago I wondered how to add some protected fields into one of my GObject. Those of you who have more experience with Glib and GObject should know a very popular construct allowing to define and then add a private structure to a GObject class definition (with g_type_class_add_private).
As opposed to that, there is no such an easy mechanism which simplifies adding protected fields. Unfortunately when we use inheritance and virtual methods sometimes this can lead to some inconvenience and a lot of boilerplate code (which btw. in case of GObject library can reach a significant number of lines)

I tried to search over the net, but I couldn’t find any solution to this problem. Having no better solution I invented a simple “hack” that mixes the behavior of both private and public fields. Together with some naming conventions it allows to simulate some kind of protected mechanism. Of course the word protected has more intuitive meaning because it violates a lot of constraints that must be satisfied in a real OOP language.
The main problem in implementing protected mechanism in a GObject is the scope and visibility of the protected fields. It is impossible to define them in the source file, because then the implementation will be hidden in all the derived GObjects. That’s why I decided to move it into a header file and wrap all the fields into a struct similar to the one used to define private fields.

/** Struct representing protected fields of a class */
typedef struct
{
    /* Some protected fields */
    guchar *_raw_header;
    guint     _raw_header_size;
    ....
} MicGenericObjectProtected;

Moreover the header file should contain the macro definition allowing to access protected fields from other derived objects. This can be done with the following line:

/** Getter for protected data of an object **/
#define MIC_GENERIC_OBJECT_GET_PROTECTED(o) \
  (G_TYPE_INSTANCE_GET_PRIVATE ((o), \
  MIC_GENERIC_OBJECT_TYPE, MicGenericObjectProtected))

Now it’s time to move into source code of GObject class.
In the class_init function we add the protected structure into class definition with previously mentioned g_type_class_add_private function.


The code can be similar to the one below:

static void
mic_generic_object_class_init (MicGenericObjectClass *klass)
{
 GObjectClass *object_class = G_OBJECT_CLASS (klass);

 /** Add private structure to the class **/
g_type_class_add_private (klass,                             \
                          sizeof (MicGenericObjectProtected));

object_class->dispose = mic_generic_object_dispose;
object_class->finalize  = mic_generic_object_finalize;

/** Virtual public methods with their implementations **/
....
/** Abstract Method */
....
}

That’s everything. This hack is not perfect because it doesn’t allow to easily add both private and protected fields in a single GObject. Remember that g_type_class_add_private can be called only once! The other problem is that protected fields are public to all other code and in fact they can be used from arbitrary object or function. That’s why I decided to implement some kind of naming convention (“protected” suffix) which highlights that a given collection of fields can be used only by derived objects. Of course it is not a protection, it’s more like an information to the programmer. It’s his decision whether he takes it into consideration or not.

Ubuntu 8.10 Fixed problem with sound

In my previous post I wrote about a strange bahavior of my freshly installed Ubuntu. One of the problems was related to sound. I managed to get it working. It came out that something had muted the PCM channel of my sound card. ( while updating from Ubuntu 8.04)

You can fix it by right clicking on the “Sound” icon next to menu bar, choosing “Open Volume Control” and moving up the slider next to PCM label.

I read on some boads that it’s quite a common issue on Ubuntu 8.10, and quite a lot of people had problems with that. I hopy that this “silly” solution might help someone.

Ubuntu 8.10 first (bad)impression

Yesterday I found out that a new version of Ubuntu was released. Unfortunatelly I’m always excited in all the latest products and want to test them as fast as possible. That’s why I started to google for the safest and quickest possible way to upgrade.
My previous version of Ubuntu was 8.04 TLS, so I had to change some option in Software Sources dialog in order to make visible the latest version of Ubuntu.
I don’t know if you knew that but by default in Ubuntu only upgrades to “Long term” releases are performed. If you want to upgrade from 8.04 TLS into 8.10 you have to switch to “Normal releases” in Software Sources dialog.

If you need more details about this topic you can find it on the following web page: http://www.ubuntu.com/getubuntu/upgrading

Ok, but what I’ve written so far is not related to my impressions, so here I start:

Installation

My Update Manager had to work really hard and upgrade more then 1300 packages. All in all it took me about 1:20 h for downloading all of the files (on 2Mb/s connection) and then additional 30-40 minutes for unpackaging and setting them up. Unfortunately I started very late in the evening because I didn’t expect that it would take such a long time. Finally I ended up at 2:30 A.M.

First reboot

Although the installation took me some time, I didn’t have much problems with that. But when I restarted the computer the series of strange things started to happen.

Long startup
First of all the system initialized for more than 5 minutes. In the beginning I thought that it just hanged. But then it came out that the problem was related to ALSA demon which did not respond for the certain amount of time. After a given timeout it was killed by the system. That caused another problem which resulted in no support for sound.

No Sound – problematic ALSA
I managed to solve the startup problem temporarily by blocking ALSA daemon. But what’s obvious it didn’t help with the sound:( I guess that the new kernel that was installed in the system might cause some conflict with the sound card or sth.

NVIdia and Compuz Fusion
Another problem, that I faced, was related to Compuz Fusion and NVidia drivers. Fortunately all these eye-catching effects work, but sometimes I observe a strange behavior of my window title which blinks and disappear without any reason. This can be seen on pictures below (look at the right top of windows):

 

I can easily reproduce that strange behavior when the window is deactivated (should be transparent) and then activated by moving mouse cursor over the maximize button.

Firefox

Another problem was related to Firefox. My Adobe Flash plugin stopped working. Firefox claimed that it was not installed, but when I wanted to do that it complained that it’s already installed:) Strange. I had to fix it by removing the plugin manually using apt-get and then reinstalling it back using Firefox.

Summary

To sum up my first impressions with new Ubuntu 8.10.
I must admit that at a first glance it’s hard to see any outstanding and innovative modifications in GUI. In my opinion that should at least influence system stability and reliability. Unfortunately even in this matter I’m not fully satisfied. Maybe my requirements are too high?? Thanks to previous releases of Ubuntu I got used to Linux which works perfectly just out of the box. For me in 8.10 this most crucial rule was violated:(((

AutoTools, tar and paths longer than 99 characters

I tried to build a Debian package for the project I am currently working on. Unfortunately all the paths I used in the structure of my application were very long. While executing make dist command I got lots of errors similar to the one below:

wzt-poc2/media-server/src/[....]wzt-children-manager/tests/: file name is too long (max > 99); not dumped

I found out that the error is due to the tar archiver. It does not support file names (in fact “paths”) longer than 99 characters. This problem can be easily solved by forcing AutoTools to use POSIX version of tar which does not have this limitation.

It is enough to modify a configure.ac file in the following way:

AC_INIT([your-application-name], [0.1.0])
....
AM_INIT_AUTOMAKE([1.9 tar-ustar])

The crucial part is inside the AM_INIT_AUTOMAKE declaration which changes the default tar archiver.

Making Debian library package with dh_make

This post is a short introduction to building *.deb packages using dh_make & dpkg_buildpackage tools.

Let us assume that we want to make a Debian package for a simple library. We are going to create two *.deb files, due to the fact that in Debian-based operating systems, libraries are usually distributed in one of the two forms:

  • dev package – containing both library binaries and header files for programmers. Used mainly by the developers.
  • standard package – storing only the library binaries

Having that in mind, we should start our work from downloading necessary utilities:

apt-get install dpkg-dev dh-make debhelper devscripts pbuilder fakeroot

Next step is to set a proper name for the directory containing the source code of the library.
It should have the following pattern: <package>-<version> ( ex. mylib-0.1.0 )
Inside that directory we execute a command generating files describing the content of the package:


dh_make -l

where “l” stands for library

We can notice that a new directory “debian” was created. It contains several files, the most important are described below:

  • changelog – Changelog for the package from which a number of the latest version is taken
  • control – File containing package description and its dependencies
  • rules – Script responsible for generating package (similar to make)
  • mylib1.install – List of directories containing files which should be copied to the package (normal package)
  • mylib-dev.install – Similar as mylib1.install but related to development package

Just to make it look better, let’s rename all “mylib1*” files into “mylib*” and then delete unnecessary *.EX and *.ex files. (these files are used in more complex packages, for example involving rc.init script modifications)

Exemplary content of the mentioned files is presented below:

debian/changelog

mylib (0.1.0-1) unstable; urgency=low

* Initial release

-- TG <myemail@x.com>  Fri, 05 Sep 2008 17:40:45

debian/control

Source: mylib
Priority: extra
Maintainer: TG <myemail@x.com>
Build-Depends: debhelper (>= 5)
Standards-Version: 3.7.2
Section: libs

Package: mylib-dev
Section: libdevel
Architecture: any
Depends: mylib (= ${Source-Version})
Description:  myITcorner.com Sample Library  (dev)
Development files.

Package: mylib
Section: libs
Architecture: any
Depends: libglib2.0-0 (>= 2.6), openssl (>= 0.9)
Description:  myITcorner.com Sample Library.
Binary package

mylib.install
Copy all the libraries from usr/local/lib

usr/local/lib/lib*.so.*

mylib.install
Copy all the libraries (also dev files) and C headers

usr/local/include/*
usr/local/lib/lib*.a
usr/local/lib/lib*.so
usr/local/lib/pkgconfig/*
usr/local/lib/*.la
usr/local/lib/pkgconfig/*

debian/rules
Content of debian/rules script is more complex and in most of the situations we can base our package on the file generated by dh_make utility. However, some minor modifications presented below should be introduced:

...
#Configure and compile library from the
#source code and install it into temporary location
install: build
	dh_testdir
	dh_testroot
	dh_clean -k 
	dh_installdirs

	# Add here commands to install
        # the package into debian/tmp
	$(MAKE) DESTDIR=$(CURDIR)/debian/tmp install

# Build architecture-dependent files here.
binary-arch: build install
	dh_testdir
	dh_testroot
	dh_installchangelogs ChangeLog
	dh_installdocs
	dh_installexamples
	dh_install --sourcedir debian/tmp

It’s worth mentioning that a structure of the above file is similar to Makefile script. There are some tasks and their dependencies. For example in install task a library is compiled and then installed into debian/tmp directory. Later in binary-arch, a Debian package is generated from the compiled data taken from debian/tmp directory.

Building the package

Package description and configuration files are ready. So how to make a *.deb files? For that purpose we can use the following command:

dpkg-buildpackage -us -uc -rfakeroot

But let’s make it simpler. Why not to add an entry in a Makefile, just to have everything in one place?
Assuming that we are using Autotools, here is the most interesting part of Makefile.am.

Makefile.am

pkg-deb: dist
	- rm -rf  $(TMP_DIR)
	mkdir -p $(TMP_DIR)
	mv $(PACKAGE)-$(VERSION).tar.gz $(TMP_DIR)/

	tar --directory $(TMP_DIR)/ \
         -xf $(TMP_DIR)/$(PACKAGE)-$(VERSION).tar.gz

	cd $(TMP_DIR)/$(PACKAGE)-$(VERSION)/; \
                ./configure; \
                dpkg-buildpackage -us -uc -rfakeroot; \
                mv ../*.deb $(PWD)/pkg/

	rm -rf $(TMP_DIR);

In such a way a new task pkg-deb was defined. It executes another task called dist, which makes a tarball of the library source code. Later dpkg-buildpackage is called and just to clean everything up, some files are either removed or renamed.

It is important not to forget about including debian directory in the tarball generated with dist task. It can be done by adding the following line somewhere at the top of the Makefile.am:

EXTRA_DIST = debian

By the way TMP_DIR stores a location of the directory for the library installation files. In my case I assumed that

TMP_DIR = tmp

Now it’s enough to invoke:


make pkg-deb

Debian packages should be created inside pkg directory.

References:
Debian New Maintainers’ Guide
Andy Balaam’s Blog

Problem with PKG_CHECK_MODULES under Mac OS X

Yesterday I had some problem with compiling my Glib application under Mac OS X. I knew that everything worked before on Debian and the problem had to be one of this darwin-specific.
Just to make myself clear. Here is the error I got after executing: ./configure

checking for pkg-config... pkg-config
./configure: line 3489: syntax error near unexpected token `GLIB,'
./configure: line 3489: `PKG_CHECK_MODULES(GLIB, glib-2.0)'

It seemed that there was some problem with PKG_CHECK_MODULES – autoconf’s macro responsible for detecting if a given library or module was installed in the system (basing on pkg-config).
In fact it came out that the macro was not defined at all. Normally after running aclocal command it should be generated in the file aclocal.m4. But in my situation there was no such entry.

Why did that occur? At that time I could not answer that question but at least I had some starting point.
You may probably know that aclocal is one of the tools of Autotools package. It creates a file named aclocal.m4 which includes a number of Autoconf macros that can be used later by configure. (one of these macros is of course PKG_CHECK_MODULES)
After reading the aclocal info page I found out that the aclocal.m4 file content was based on some external .m4 files and my configure.ac. I read that the PKG_CHECK_MODULES macro should be defined inside pkg.m4 file, and I really could find it there in my directory /opt/local/share/aclocal .

And here the answer came. I installed pkg-config and Glib using darwin ports, where the default prefix for packages was /opt/local. But on the other hand all the Autotools programs were located in /usr/bin. It was obvious that the prefix was different, so that aclocal could not detect pkg.m4 file and define PKG_CHECK_MODULES macro.

The only missing thing was to inform aclocal about the path of pkg.m4 and all other external .m4 files.
It was simple and could be done by adding extra parameter -I:

aclocal -I /opt/local/share/aclocal

Now after running my autogen.sh file which more or less looked liked that:

aclocal -I /opt/local/share/aclocal
autoheader
automake
autoconf

and later

./configure
make

my application was compiled.
Of course this can be also achieved in many different ways. To find more solutions I recommend studying aclocalinfo page (especially secion Macro Search Path)

Glib, GObject and memory leaks

I’m working currently on a server application which uses Glib and GObject system. I wanted to test it with valgrind against memory leaks, but the results had really scared me. I got tens of memory alignment errors and hundreds of bytes that leaked somewhere. After investigating the problem I found possible reasons and a solution.
The main problem is related to Glib and the way it allocates memory. It doesn’t use a pure C-like way which is based only on malloc & free. It rather uses something called “slice allocator”.
If you don’t know what the “slice allocator” is, I will quote some useful information from the Gnome Reference Manual.

Memory slices provide a space-efficient and multi-processing scalable way to allocate equal-sized pieces of memory, just like the original GMemChunks (from GLib <= 2.8), while avoiding their excessive memory-waste, scalability and performance problems. To achieve these goals, the slice allocator uses a sophisticated, layered design that has been inspired by Bonwick's slab allocator. It uses posix_memalign() to optimize allocations of many equally-sized chunks, and has per-thread free lists (the so-called magazine layer) to quickly satisfy allocation requests of already known structure sizes. This is accompanied by extra caching logic to keep freed memory around for some time before returning it to the system. Memory that is unused due to alignment constraints is used for cache colorization (random distribution of chunk addresses) to improve CPU cache utilization. The caching layer of the slice allocator adapts itself to high lock contention to improve scalability.

If you are interested more information about “slice allocator” can be found here.

Unfortunately valgrind has some problems with the above concept and cannot detect if given blocks of memory were actually freed or not. When I tested a simple Glib application using g_slice_alloc with valgrind I got tens of memory alignment errors.
You can imagine how hard it can be to find some other errors/leaks which are not related to “slice alloc”, but are rather the fault of the programmer.
Having tens or hundreds of messages printed by valgrind can be quite misleading and in fact can hide some real problems. So how to avoid that? The simplest solution is always the best. Why can’t we disable “slice allocator”? Of course only for testing, later on when we are sure that there are no memory leaks in our application we can turn it on again.

In order to do this we have to set an environmental variable which disables the “slice allocator” and forces Glib to use normal mallocs.

G_SLICE=always-malloc

There is no need to change anything in a source code, even the program doesn’t have to be recompiled.

Unfortunately “slice allocator” is not the only problem, the other one lies on the GObject side.
I don’t know why, but somebody invented a really “nice” function called g_type_init, which is responsible for initializing GObject type system. Ok, its great but why there is no g_type_deinit? Does anyone know where the whole memory that was previously initialized is freed? Valgrind doesn’t know that and again it complaints…
I managed to get rid of some of this errors by creating suppression files that are forcing valgrind to omit some of the most common errors. Of course it is not the best solution, but at least it can help to reduce the number of errors that are not the result of our fault.

The suppression file can be found below:
glibsupp.txt

One thing is certain. The list of suppression will be expanding. The more I work with Glib the more suppressions I have to add. The current version of this file includes suppressions mainly from GHashTable, g_thread_init and g_type_init. If I find more possible leaks I will update this file.

Now it’s time to start valgrind with the whole configuration which allows to get rid of this Glib and GObject errors, the command is as follows:

G_SLICE=always-malloc valgrind --suppressions=build-aux/glib.supp --leak-check=full --show-reachable=yes ./our_program

Logic gates with Neural Networks

Simple Java Swing application written to present learning abilities of Neural Networks. Program uses a back propagation algorithm and provides a set of adjustable logic gates which can be used for the testing purposes.

Read More

Pacman3D

Pacman3D is a clone of a well known computer game moved into 3D world. It was created for a Computer Graphics course during my studies at Windesheim University of Applied Sciences, Holland. The project was realized in a group of five people. My main responsibilities were connected to 3D scene coding, sound effects, game AI and basic 2D graphics (like menu, game panel and console).

Some of the game elements are based on Quake graphics (menu, console etc.). However the core of the Pacman is based on the original game rules.

Read More

Image Processing Tools

Useful collection of Image Processing and manipulation algorithms embedded in a GUI application enabling quick previewing and comparison. Application written in Java, using Swing and JUnit tests.

Read More

aMazeProject

aMazeProject is a simple maze generator and solver. Application is written in Java and was created using NetBeans 6.0 IDE. The code is commented so that it should be self explanatory.

Read More