I have integrated the LRDE (EPITA Research & Development Lab) few months ago as a student and this is my first research presentation.

Climb - A Generic and Dynamic Approach to Image Processing

Abstract: "Climb is a generic image processing library. A case study of the erosion algorithm from mathematical morphology highlights the issues of a non-generic implementation. Structures such as Image, Site Set and Accumulator are defined to solve them. Genericity is even increased by the concept of Morphers: a way to alter the communication between an object and the outside world. All these additions are done using the dynamic aspect of Lisp that allows for rapid prototyping."


The oral presentation is in French. The slides (Download) are not readable in the video due to the poor recording quality, please scroll the slideshare at the same time you are viewing the video.

Technical Report

Along with the presentation, I have written a 20-pages technical report (Download).

The Bistromathique is an Arbitrary Precision Calculator EPITA project where the main focus is optimization. The input can be in any base (up to 250) and the following operations have to be performed: Addition, Subtraction, Multiplication, Division, Modulo.

Base Representation

Going back and forth a textual representation to a computable representation is the first part of the project and several optimizations are possible at this step.

Binary Representation

Encoding the numbers as binary allows you to make the best use of the processor calculation unit. There is no space lost and the number being represented as an uninterrupted series of 0 and 1 can be added and subtracted directly with the hardware.

However, in order to convert the number for a base B representation to a base 2 requires roughly n divisions by B. And to reconvert it back requires another n multiplications. This can be affordable for applications that uses the same numbers again and again but in our case, this cost is prohibitive.

The other major drawback is that you are required to have the multiplications and divisions (and therefore addition and subtraction) in order to have the numbers in the right form to start working on the operations ... In summary, you have to code all these operations before being able to test them!

char Representation

The binary representation not being possible, the solution that comes in mind is to put each digit into a char (8 bits). Since we are limited up to a base of 250, any base will fit. This comes at a price, there is a lot of space wasted, and it increases as the base size decreases.

We are in a 1 to 1 relation between the input and the represented number, this way we can store the represented number inside the input. This prevents from allocating memory at this step. The conversion can be efficiently done, each character goes through vector of 256 slots storing its representation and a magic value used as a non valid input. One final trick is to add a non number at the end of the input to remove a end of input check in the loop.

Filling more

A char can store values up to 256. If we are working on base 16 we could store two digits into 1 char and thus divide by 2 the number of digits. Additions are therefore 2 times faster and even more for n log n operations such as multiplication.

Calculating the number of digits to fill into a char is quite straightforward however some caution has to be taken during the transition. We have to know in advance the length of the input to decide how to start filling the digits. If you can fit 2 digits per char, if the number is even then it goes as expected, but if the number is odd you have to place 0 at the beginning to fill the gap.

Even: [1] [2] [3] [4] -> [12] [34]
Odd (Naive): [2] [3] [4] -> [23] [4?]
Odd (Smart): [2] [3] [4] -> [02] [34]

This method works well but requires 2 passes for each number and a special case at the beginning of each number. Not enough to stop us from using it.

Using a larger representation

Now that we filled the char at its maximum, why stick with it? This should ring a bell since you know that common architecture is 32-bit, and from now we are talking about a 8-bit representation. We would be tempted to change the char to an int (32-bit) or even a long (64-bit) that could benefit from register optimizations.

Moving away from a char, we lose the assumption that the output being smaller (or equal) than the input. Without it, this is no longer possible to work in place. We now have to compare the cost of a reduction in the number of operations and the cost of the memory allocation.

The overhead happens for values that are represented in less than 4 characters for an int representation. This is a maximum 3-characters overhead possible for each number, which is negligible. We could eat the operation character but we are left with 2 characters. I haven't found a solution to stay in place yet and this minor problem prevents from accessing a great speed up.

To be continued ...

It has been one month that the third year (called Ing1) of EPITA started and this is a recap of the interesting projects that I developed.

malloc (1 week)
The goal of this mini-project is to improve our knowledge of memory management by implementing the C standard library memory allocator (malloc, free, realloc). Implementation using the Binary Buddy technique:

  • List of free blocks of size 2^k.
  • Split and Merge using adjacent block of the same size called buddy.
  • Insertion and Deletion in O(log n).
  • 32 & 64 bit ready.

find (1 week)
find is a very well known UNIX command used to satisfy research upon files and directories.

  • File listing and options parsing with error handling.
  • -name: Filtering using globbing.
  • -newer, -atime, -size, -inum, -type, -links: Filtering off information sources. Handles -/+ for "less/more than".
  • -perm: Filtering based on permission expressed in octal (0777) or symbolic (u+rwx,go=r) notation.

fnmatch (10 hours)
fnmatch is a function that implements globbing. It returns whether the string matches the pattern. This is mainly used to filter out files (eg: *.txt) or text search in databases (eg: LIKE '%Text%').

  • *: any character 0 or more times.
  • ?: any character 1 time.
  • [abcA-Z]: any character from the class.
  • \*: escaping.

Libstream (10 hours)
I/O functions are slow hence they should be called few time as possible. This is why they are typically buffered. The project is to recode all the I/O buffered functions of the C standard library as they are defined by the Single UNIX Specifications V3.

  • fopen, fclose, fgetc, fputc, fflush: Core functions to handle buffered I/O at a character level.
  • fseek, ftell, frewind: File positioning functions.
  • fread, fwrite, fgets, fputs, fgetdelim: Helper functions to use buffered I/O at a string level.
  • tinyPrintf: Basic string formatting (%d, %u, %s, %c, %o, %x without modifiers).