Nix

For the last few months my team (OpenBossa) at INDT (Instituto Nokia de Tecnologia) have been working on WebKitNix (Nix for short). WebKitNix is a new WebKit2 port, fully based on POSIX and OpenGL. We also use CMake build system (like GTK and Efl), GLib, libsoup (networking) and Cairo (2D graphics) as dependencies. It also uses Coordinated Graphics and Tiled Backing Store from WebKit2. Many of its building blocks are shared with others ports already on trunk.

The Nix port offers a C API for rendering a WebView within a OpenGL context, based on WebKit2 API. You can use Nix to create applications such as a web browser or a web runtime. WebKit2 run the context for each web page in a different process. This process isolation keeps the UI responsive, with smooth animations and scrolling, because it does not get blocked by Javascript execution.

We want to ease the work of Consumer Electronics developers who wants to have a web runtime in their platform, without the need to create another WebKit port. That is why Nix has less dependencies than Efl, GTK or Qt, which should also be ported to the target platform.

Nix API also enables the application to interact with the Javascript context. So it is possible to add new APIs, to handle application specific features.

How did it started?

The OpenBossa team used to maintain the Qt WebKit port for years, helping Nokia/Trolltech. But then, in the last years, from the experience gathered with the Snowshoe browser, handling with dependencies (such as QtNetwork) that were much bigger than we really needed. We tried to replace some dependencies of QtWebKit and later Efl to see how minimal WebKit could be. So we took some steps:

1. Initial idea: platform/posix or platform/glib (share code)
2. Ivolved problem: we wanted to have different behaviors for QQuickWebView -> Qt Raw WebView
3. Network: QtWebKit + Soup experiment
4. Efl Raw WebView experiment
5. Efl Without Efl :-)
6. Nix

How to use it?

When you compile Nix source code you can run the MiniBrowser to test it:

$ $WEBKITOUTPUTDIR/Release/bin/MiniBrowser http://maps.nokia.com

MiniBrowser code

The Nix-Demos repository offers some example code, including a Glut based browser and minimal Python bindings for Nix: https://github.com/WebKitNix/nix-demos.

On Nix-Demos we also have a Nix view, using only a DispmanX and OpenGL ES 2 working on the Raspberry Pi. To compile this demo, you will need our RaspberryPi SDK .

There is even a browser with its UI written in HTML: Drowser

Feel free to contact us on #webkitnix at freenode.

Roadmap

Our plan is to upstream Nix in WebKit trunk by June/2013. Then, keep the maintainence and focus on the web platform, including some new HTML5 features, such as WebRTC.

Why is Python slow? Python Nordeste 2013

Why is Python slow? Python Nordeste 2013 from Daker Fernandes

It was a great event! Thanks to everyone who made it happen.

OpenGL Lesson 02 - Drawing with OpenGL

OpenGL is a primarily an C API, for drawing graphics. Implementations and bindings exists for several languages such as Java, Python, Ruby and Objective C. OpenGL became the standard drawing API supported by most modern device with graphics, independent from vendor, operational system, or if it is desktop or embedded. Of course the platform matters, but we can split the platform dependent code from pure OpenGL.

OpenGL became a standard mainly due to its rendering pipeline, which is trivially parallelized. This allowed the creation of specialized hardware, the well known graphics cards. These cards became very small and started to be practical shipping embedded devices with them. Now high performance graphics in these devices are a reality.

On traditional desktop platforms, the usual layout of graphics card stand as pictured below. In this scenario, moving data to and from the card can mean a huge cost. On others platforms, such as the mobile, its common that GPUs uses the same memory as the CPU. However, the programmer still needs to handle this memory efficiently.

For this new range of devices, the Khronos (group responsible for standardizing OpenGL API) released an OpengGL specification focused on embedded systems, the OpenGL ES.

In this post I would like to explain some key concepts about the OpenGL API:

• What are the best practices for it.
• Differences between the "Desktop" version versus the ES version.

I want not to go deep in the API or its functionalities. You have other sources that covers them better. I recommend the ones used as reference for this post:

• GL Programming
• Song Ho Ahn's Tutorials and Notes
• OpenGL Programming Guide, 7th edition. (a.k.a. The Red Book) or a newer edition

Hello Triangle!

Enough talking, show me the code! I wrote the following code using GLUT and OpenGL 1. GLUT is a simple toolkit to create simple OpenGL applications. It basically opens an window with a GL context, and handles primitive mouse and keyboard events.

#include <GL/gl.h>
#include <GL/glut.h>

void display()
{
    glClear(GL_COLOR_BUFFER_BIT); // Clean up the canvas

    glBegin(GL_TRIANGLES);
    glVertex2f(-1.0f, -1.0f);
    glVertex2f( 0.0f,  1.0f);
    glVertex2f( 1.0f, -1.0f);
    glEnd();

    glFlush(); // Forces previous GL commands to be send to the GPU
}

int main(int argc, char **argv)
{
    glutInit(&argc, argv);
    glutInitWindowSize(480, 480);
    glutCreateWindow("Hello World");

    glutDisplayFunc(display);

    glutMainLoop();

    return 0;
}

Drawing the triagle

In OpenGL 1 and 2, the easiest way for you to draw a triangle, is using some form of glVertex*. These call must be enclosed between glBegin and glEnd.

OpengGL uses a coordinate system where the origin is the center of the viewport, the X axis has left to right orientation and Y axis is bottom to top, as pictured below. By default everything between (-1, -1) and (1, 1) is what youll be shown in the viewport. Check this tutorial for understanding OpengGL coordinate system and camera deeper.

You also need to assert what kind of primitive you are passing to OpenGL. It accepts the primitives illustrated below with their correspondent constants. OpenGL ES does not support polygon or quads, you will need to assemble them yourself.

Interleaved with the vertex position, you can add other information such as colors, texture coordinates, normal direction. You can define other vertex attributes for richer shaders. Shader is a piece of code that defines how your primitives will be rendered. With them is possible to make a lot of effects such as normal mapping, adding shadows, particles and many more. When we choose a shading model we are using OpengGL default shaders. Standard OpengGL defines a large set of inputs and outputs a shader must have. OpenGL ES 2 and above does not defines what you must enter as input for the shaders. Is up to the programmer what will be the inputs vertex shader will have. The contract assumes that the vertex shader will return at least a position (search for gl_Position) and the fragment shader a color (gl_FragColor). Do not worry. This will be further detailed in a following post.

Vertex Arrays

Drawing with glVertex* was deprecated from OpenGL 3 and beyond. In OpenGL ES we do not have them either. This drawing method overheads of one function call for each information entered in the pipeline. The OpengGL comittee also wanted to disencourage the usage of this kind of input mode. The interfere of this overhead is small for small objects, but is not true for large ones. Another reason, for removing them (specially on ES version), was the make OpenGL implementation lighter, by reducing the number of internal states.

Prefere to draw using vertex arrays. Vertex arrays are arrays that each element contains all the vertex information. The command to draw them is glDrawArrays . Indexes can be specified to reuse the vertex definition by using glDrawElements. A good reference for this subject is this one . As this is the standard way when using OpenGL ES 2, I will give an example.

Example of Vertex Arrays

To draw a square you must first define the schema of each vertex. Here, each vertex has a position (3 floats) and a color (3 floats for R, G and B color channels). In C I like to define a struct to improve readability:

struct vertex_t {
    GLfloat position[3];
    GLfloat color[3];
};

void display()
{
    struct vertex_t vertex_data[] = {
         {{-1.0f, -1.0f, 0.0f}, {1.0f, 0.0f, 0.0f}}, // red bottom left
         {{-1.0f,  1.0f, 0.0f}, {0.0f, 1.0f, 0.0f}}, // green top left 
         {{ 1.0f, -1.0f, 0.0f}, {0.0f, 0.0f, 1.0f}}, // blue bottom right
         {{ 1.0f,  1.0f, 0.0f}, {1.0f, 1.0f, 1.0f}}, // white top right
    };
    
    // ...
}

It is possible to have different arrays for color and position, but for speeding up the shader execution is recommended to keep information about the same vertex contiguous to use memory locality.

glVertexAttribPointer(
    position_attribute_location, // attribute description (depends on the shader)
    3, // size of the information (3 coordinates in this case)
    GL_FLOAT, // type of the information
    GL_FALSE, // if the value will be normalized (for vectors)
    sizeof(struct vertex_t), // stride of the memory vector
    &vertex_data[0].position // initial address
);
// asserting that position will be used by the shader
glEnableVertexAttribArray(position_attribute_location); 

glVertexAttribPointer(
    color_attribute_location,
    3,
    GL_FLOAT,
    GL_FALSE,
    sizeof(struct vertex_t),
    &vertex_data[0].color
);
// asserting that color will be used by the shader
glEnableVertexAttribArray(color_attribute_location);

// Draw a triangle strip vertex from the current attribute pointers
// starting on index 0 and using 4 elements
glDrawArrays(GL_TRIANGLE_STRIP, 0, 4);

This gives us the following result:

Notice that the colors for each vertex stands as the ones we gave, but all the region in between has the color calculated as the interpolation of the vertex colors. The rasterizer is the responsible for doing this.

You could also use indexes to access the vertex. For bigger elements it may be a better solution, specially for 3D objects, because you can share vertex that appears in multiple polygons of an object. Using index would speed up the memory transfer and usage for these objects.

GLubyte indices[] = {
    0, 1, 2, // first triangle
    1, 2, 3  // second triangle
};

glDrawElements(
    GL_TRIANGLES, // not a strip in this case
    6, // number of indexes
    GL_UNSIGNED_BYTE, // type of the indexes
    indices // a pointer to indexes themselves
);

The previous code does it for a trivial shader set (called a program). I will not explain how to use it here because is out of the scope for this lesson. On regular OpenGL versions you could use glVertexPointer and glColorPointer. I will left it as an exercise for you.

Vertex Buffer Objects

Buffers are objects that stores vertex information in GPU memory. It is a must for improving the performance when drawing large objects. In heavy application such as games or CADs, is good to remove the overhead of from sending vertex data from regular memory to graphics card memory by pre loading the vertex data in a buffer. The code below show how can you upload the vertex data to a buffer.

GLuint bufferId;

// here you get handlers for GPU buffers, in this case, only one
glGenBuffers(1, &bufferId);

// asserts that you are using the buffer represented by bufferId
// as the current ARRAY_BUFFER
glBindBuffer(GL_ARRAY_BUFFER, bufferId);

glBufferData(
    GL_ARRAY_BUFFER, // the data is uploaded to current array buffer
    sizeof(vertex_data), // number of bytes of the total array
    vertex_data, // the pointer to the data
    GL_STATIC_DRAW, // hint of how the buffer will be used, in this case, data will not change
)

To draw the buffer content, you must use glVertexAttribPointer passing the buffer offset instead of the vertex_data address. OpenGL will notice that a buffer is bound and will use it.

glBindBuffer(GL_ARRAY_BUFFER, bufferId); // Bind whenever you will use it

glVertexAttribPointer(
    position_attribute_location, // attribute description (depends on the shader)
    3, // size of the information (3 coordinates in this case)
    GL_FLOAT, // type of the information
    GL_FALSE, // if the value will be normalized (for vectors)
    sizeof(struct vertex_t), // stride of the vertex buffer data
    0 // offset at buffer
);
// asserting that position will be used by the shader
glEnableVertexAttribArray(position_attribute_location); 

glVertexAttribPointer(
    color_attribute_location,
    3,
    GL_FLOAT,
    GL_FALSE,
    sizeof(struct vertex_t),
    3 // offset at buffer
);
// asserting that color will be used by the shader
glEnableVertexAttribArray(color_attribute_location);

// Draw a triangle strip vertex from the current attribute pointers
// starting on index 0 and using 4 elements
glDrawArrays(GL_TRIANGLE_STRIP, 0, 4);

// Unbinds the buffer
glBindBuffer(GL_ARRAY_BUFFER, 0);

Remarks about OpengGL ES 2

OpenGL ES 2 does not have the model-view matrix, responsible for setting the camera view, nor the matrix stack. All you have is the X axis [-1.0, -1.0] to Y axis [1.0, 1.0] region which will be mapped to the viewport. If you need those features (you will for most 3d applications) you will have to handle them inside your application code. You will have to do it yourself by exporting a model-view in the vertex shader as an uniform variable. For a theorical background on it, check my previous lesson . A great tutorial on how to play with the camera, transformations and model coordinates is this . It explains a bit how it works under the hood for regular OpenGL. Its worthy to take a look.

While hacking some examples I have come to some weird behaviour in OpenGL ES 2.0 for the Raspberry Pi. It might be bugs or mine misinterpretation.

• glUniformMatrix4fv translate parameter must be false. It simply does not work otherwise.
• glDrawElements did not worked with unsigned int.

Raspberry + Python at Python Brasil [8]

This is the presentation given at Python Brasil [8], in Rio de Janeiro. I hope you like it. :-)

OpenGL Lesson 01 - Pre OpenGL

This slides are from a lecture about OpenGL I'm giving at INDT. The first lesson was to refresh some important math concepts that will be important to understand how OpenGL works under the hood.

The slides are simply pictures of the board. Yes, they are in portuguese.

Feel free to make a question in the comments.

Qt & KDE in FISL 13

Last month, the 13rd FISL (Free Software International Forum) happened in Porto Alegre , in the very south of Brazil. It was a great opportunity to see what's going on in the free software community besides Qt and KDE in Brazil.

It was a great to see again some friends from KDE Brazil and met some new ones. The Konqui

I also gave some talks and workshop about Qt, KDE and game development.

Workshop: Developing applications for multiple devices using Plasma technologies

This workshop was idealized and given by Sebas , and I was there for helping him, specially with the language barrier. In the workshop, QML was introduced together with KDE libs and what they can add to the applications.

Was good to show the current state of the Plasmate and how easily is creating and deploying a new Plasmoid. It was interesting to see how people were amazed about how easy is to start hacking and deploying a project.

This is the slide we used during the workshop:

Talk: Games with Qt

In this talk I gave an overview about what Qt is and which tool are available for creating games with it.

Jogos em Qt from Daker Fernandes

Workshop: Games with Qt

On the third day I gave a 3 hours hands-on workshop about game development using only QtQuick. During the workshop, I've presented basic QtQuick and some basic game concepts such as the game loop, collisions and physics. I also tried to apply to explain how these concepts match with the QML development.

I created a simple click game Monera as an example to the attendees. The code was written step by step and used itself as example and introduction to QtQuick. It was possible for everyone to write the code on their own computers and test.

In the end also gave them a overview about how to install the QML-Box2D and how to use it's API.

The code used as case is available on GitHub: https://github.com/dakerfp/Monera-Game

Unfortunately I didn't used git to keep the history of steps, modularization and refactoring I did during the workshop. I think that would be a plus to understand the code and how we came to it.

This was my first time on FISL and it was great! And I expect that won't be my last.

Akademy 2012

Hey folks, I'm going to Akademy!

Me and Thiago are going to present about Qt Components & Qt Styles in Qt5.
I hope to see you in Tallinn!

QML Theming/Styling (Update)

This post is an update about the research project from my team, described a few weeks ago.

From the time we published the last post about QML Styling until now we have worked on this set of issues/features:

• Get feedback about research project
• Combo Box Component
• Combo Box Customizable Style
• Combo Box Plastique Style
• SubControl Styling
• Understand SceneGraph internals
• Understand other native platform internals

I will detail what was possible to make for each of these topics in sessions below.

What is our vision now?

Last week, we have read a few blog posts, and talked with a few Qt & KDE application developers about what should be the priorities for creating desktop and mobile applications. I have presented our proposed solution for using native look and feel for QML widgets, how to create custom styles from scratch, using the CustomStyles helper, and how to apply them with the ApplicationStyle API.

Based on the feedback and the blog posts, my team sat down and came with the following set of statements which summarize our vision for what sould be our focus of our current research:

1. Usable QML components with native styles working ASAP
Developers want to code entire application UI with QML having native look and feel.
2. Easy customization
It's all about making easier to create components with different look only by filling in some templates to avoid code repetition for standard. These custom styles are targeted to be like a short cut, obviously for more complex behaviour, you will need to create your own style.
3. Powerful customization
Enabling to use QtQuick components as the style can make widgets look fluid. It's desirable that the new styling mechanism is at least as powerful as QStyle is today. As a first shot we want to enable styling do at least what QtWidgets style does. The main point here is to maximize the results and minimize ramblings about what is style or not.
4. Styling modularization
By spliting the old style scheme in a set of widget style, enables us to create the style for each component/platform independently instead of the monolithic QStyle. Now it's easier to mix styles and change them on demand more easily.
5. Disruption with QtWidgets
We wish to make this component set free from QtWidgets modules. One of the reasons is because now it is considered done and it's desirable for the new components set that it can be expanded. We also don't want to link with QtWidgets module, because the real dependency should be the QStyle only. The current ApplicationStyle approach, shows us that the styles depends only on QtQuick. One of the possible paths to achive this is:
1. Move QStyles out of QtWidgets with a few adaptions on it.
2. Create a SceneGraph based native styles when possible

Combo Box

We decided to choose the ComboBox component to work on because it is one of the most complex (if it isn't the most). Because of the complexity, we hoped that during its development we could be enlightened of knowing if we are in a correct path, what still misses, and what should be the next steps.

As we did in the Slider approach, which was divided in 3 different subcomponents:

• Handle
• Groove
• Tickmarks

While creating the ComboBox, we decided to divide it in 4 other subcomponents:

• ArrowStyle
• BackgroundStyle
• TextEditStyle
• DropListStyle

We basically mimicked how QStyle splits the QComboBox painting into subcontrols. The drop list was also delegated a sub style as QComboBox does with it's internal QListView. We haven't worked on the drop list style since it would require a native style such as Plasma's ListItemView, which also would rely on a ScrollBar.

Creating the combo box component showed us that positioning and size hints can be more tricky than it looks like.

The ComboBox got stuck in a few parts and unfortunately it's not complete right now. However we took the questions and answers from its development. :-/

Positioning and Size Hints

This topic of discussion came out when we were thinking about a theoretical style in which the ComboBox would be in the left. One of the issues we had in mind while developing the editable ComboBox was how to set a MouseArea that can know when set the focus to the text edit or to open the drop list. This would be possible to be done with current QStyle, since on it's approach the QWidget reads the subcomponent's size hints by the subControlRect method from QStyle.

We would like to have this positioning information on the style as well. The approach can be similar to what happens with the size, which you can read it from the widget reference.

The following piece of code is a simple example of how size hints can be taken:

// ComboBox.qml
Item {
    property alias arrowStyle: arrowControl.sourceComponent

    Loader {
        id: arrowControl
        width: arrowControl.implicitWidth
        height: arrowControl.implicitHeight
    }

    MouseArea {
        anchors.fill: arrowControl
        onClicked: {
            // do some action
            // ...
        }
    }
}

ArrowStyle defines the implicit size, which works as a size hint, and the position where they are. These properties together can work analogue to subControlRect, as they hold the same info. The component may ignore such hints and override the properties values, such as Slider's Handle style position.

// MyComboBoxArrowStyle.qml
Image {
    implicitWidth: 50
    implicitHeight: comboBox.height
    x: comboBox.width - width // Arrow could also appear on the left by setting x = 0
    source: "arrow.png"
}

One may ask "Can't I have a round button with a circular hit area?" That's more complex than just setting hints for the geometry of sub control styles. As we defined in our view we're trying to be at least as powerful as QStyle. We consider that, by now, we should be strict at least about the interaction styling of the components themselves. From my point behaviour difference should be defined as the component API.

Sub StyleComponents Sets

Another discussed topic was about the fragmentation of the style property of the components. For instance, take the following Slider style code:

// Slider style now
Slider {
    grooveStyle: CustomGrooveStyle { ... }
    handleStyle: CustomHandleStyle { ... }
}

The Slider style property is fragmented as more than one property. We thought that these properties could be centralized with a SliderStyle as an aggregator object. This helps API clarity for style manipulation since we can play with a single object reference that represents the component style, enabling to handle it atomically.

// Proposed Slider style usage
Slider {
    sliderStyle: CustomSliderStyle { ... }
}

with CustomSliderStyle as:

// Proposed Slider style creation
// CustomSliderStyle.qml

// Aggregated style object
SliderStyle {
    grooveStyle: CustomGrooveStyle { ... }
    handleStyle: CustomHandleStyle { ... }
    tickmarksStyle: CustomTickmarksStyle { ... }
}

or more compactly:

Slider {
    sliderStyle: SliderStyle {
        grooveStyle: NativeGrooveStyle { ... }
        handleStyle: CustomHandleStyle { ... }
    }
}

or even:

Slider {
    sliderStyle {
        grooveStyle: NativeGrooveStyle { ... }
        handleStyle: CustomHandleStyle { ... }
    }
}

This issue is only an idea only discussed between ourselves. It would be nice to have feedback about these API.

Insights from SceneGraph & QStyle study

The isolated study of the scene graph internals (getting rid of QQuickPaintedItem), and how it could be used to create the new styles directly on it, didn't told us much in fact. Only that is better we keep doing these styles in QML and using Scene Graph itself to create sub elements that needs a more refined handling.

On the other hand, the Windows and Mac styles investigation was very important to decide our next steps. It showed us that these styles uses platform native APIs to draw the native widgets on each platform on pixmaps. So we would have to deeply study these API to create our own implementation of native styles using the scene graph. For these reasons isn't too simple to give up from QQuickPaintedItem some time to going deep on them right now since our time and head count is limited.

Two steps forward, one step back

After the feedback from other developers, one of the main thing people want more is to have a widget set working with the native look and feel as soon as possible. Keeping this as our primary focus, we will left the restriction of depending on QtWidgets for now. So we will focus on having a working solution that can be easily replaced after. Fortunately, our proposed modular solution for styling fills that requisite.

QML Theming/Styling

Intro

As I mentioned in my last post, I and my team in INdT are researching on how to improve the Styling  new way of creating styled QML widgets components (Button, Sliders, ComboBox, etc.). We've been involved for such a long time in the development of Qt Components for the Harmattan, and me personally worked on the Plasma Components widget set.

We also did a some big desktop and mobile applications (such as Snowshoe and PagSeguro NFC Payment) which required us to create lots of custom widgets. Obviously there's a lot of redundant code between the applications that could belong to a common code base.

Besides the existence of the Qt Components, the styling of widgets is an issue it doesn't solves as well. Nowadays if you want a new style, you'll have to create a set of QML components from scratch or to base on an existing widget set, which would increase the development and code fragmentation. One way to style your widgets is to rely on the old and confusing QStyle classes, and there is no easy way to it purely in QML.

ps: This post was written by me and Thiago Lacerda.

Issues and Requirements

Recently, lots of discussions about a new styles API happened on the Qt development mailing list. Some of the issues as we considered were summarized by Alan Alpert in a thread on Qt Project's forum. Here are some of the points he collected from the discussion in the mailing list:

• One source, multiple target platforms
• Change the appearance of standard controls in my application
• Style QWidget and QQuickItem UIs with the same code
• Inside QML items, draw native controls without using QML

In addition to those concerns, based on our experience on desktop and mobile applications we have a few other important issues to guide us:

• Configure current theme/style from the QML
• Use QML for configure new Styles for widgets
• Minimize code size for application developers
• Wisely use SceneGraph to improve performance
• Don't need to link with the old QtWidgets module

The current implementation of the custom components in the Desktop Components solves a few of these problems. However one of the biggest problem is depending on QtWidgets, not having an easy style change support and not properly using the SceneGraph for painting the widgets.

QtQuickStyles

To research how to solve these issues we've decided to create the QtQuickStyles module. The general idea for this module is to provide a simple way of styling QML widgets (think of Qt Components). The current research is about creating an API to allow proper platform look and feel integration without depending on QtWidgets, and easily theme your whole application with your custom style, if you want another theme besides the underneath platform look and feel. We want that the developers be able to do it all purely in QML. All the collected issues are being considered for the API.

The current work is available here:

git clone git://code.openbossa.org/projects/qtquickstyles.git

Now, our focus is to adapt the existing code base, from QStyle, for painting elements in QML as a short term target so we can have working code faster, and supporting all the same platforms and styles that QtWidgets does.

QStyle

Today, on Qt code, each style knows how to paint all the control elements, and they all follow an interface (defined by QStyle class). If you want a new style you will have to implement a new QStyle subclass. The following scheme may clear up your mind:

Current QStyle architecture

Additionally, if you take a look at the QStyle code, you can see a bunch of mixed code, taking care of drawing all type of widgets. Almost all the methods have a huge switch case, each taking care of an specific action of an specific widget. When someone put the eyes on it for the first time, thinks it is too complicated to understand and very messy (and indeed it is). Additionally, a code like this leads to a huge complexity to maintain and understand it.

So, why can’t each widget take care of its own features and painting? Why we could not have an interface that would define how a button is painted, for instance? Doing it this way, if we have some work to be done on the button (again the button example), it would only be done on this button class. Furthermore, if we have modifications on how the button with the plastique style, for instance, is painted, we have only to do it on the plastique button class. This approach leads to more understanding on the overall code and also makes it easy to maintain, isolating the problems that can appear, to the widget itself.

To do this, a component must be a control or composed of sub controls (such as the Slider's groove, handle and tickmarks) and for each control it'll use a QQuickItem that reads the widget's state and "paints" itself with as it is the style.

QtQuickStyles in use

We've done a few brainstorm for defining the current API to use the style in the components.
The following code is the example of how our API was thought to be used:


// Regular Button having the underneath platform look and feel
import QtQuick 2.0
import QtUiComponents 1.0

Button {
    width: 140
    height: 40
    text: "Native Button"
}


We are going to explain later how the style resolves the current platform being used.

Override platforms style:


// Regular Button having the plastique look and feel
import QtQuick 2.0
import QtUiComponents 1.0
import QtUiStyles 1.0

Button {
    width: 140
    height: 40
    text: "Plastique Button"

    // This use case is not implemented exported yet, but it will be
    style: PlastiqueButtonStyle { }
}


Using a user defined style:


// Regular Button
import QtQuick 2.0
import QtUiComponents 1.0

Button {
    width: 140
    height: 40
    text: "User-defined Button"
    // Accepts a QML Component
    style: Rectangle {
        color: "gray"
        Text {
            anchors.centerIn: parent
            text: button.text // button reference is injected when the internal Loader loads it
        }
    }
}


We can see, by the examples above that we can easily uses a Button component and gives it the look and feel that we want, by only playing around with the style property. In order to follow a well discussed and already implemented Component's API, we're using the Qt Components Common API specification for creating the components in the repository.

Custom Styles

To solve the issue of being easy to create a new style, we are also adding component helpers that exports properties that commonly changes from one application to another. These configurable properties were selected based on our experience of creating QML components.
The custom style API defined for the Button and Style can be found here.


// Regular Button
import QtQuick 2.0
import QtUiComponents 1.0

import QtUiStyles 1.0

Button {
    width: 140
    height: 40
    text: "Custom Style Button"
    style: CustomButtonStyle {
        background: "myButton.png"
        pressedBackground: "myPressedButton.png"
    }
}


ApplicationStyle API

As listed in the issues list, it's interesting that we had an easy way of setting the application theme/style in QML. We came to an API that let the developer change the style of all the components in the application that uses the default style. The example below shows how to play around with the application theme/style:


import QtQuick 2.0
import QtUiStyles 1.0

Item {
    ApplicationStyle {
        id: appStyle
        buttonStyle: CustomButtonStyle {
            background: "myButton.png"
            pressedBackground: "myPressedButton.png"
        }
    }

    Button {
        text: "Button with custom Style"
    }

    Button {
        text: "Button with plastique Style"
        style: PlastiqueButtonStyle { } // Theme changes doesn't affect when style property is set
    }

    Button {
        text: "Button with appStyle"
        style: appStyle.buttonStyle // Explicitly binds button style with a style
    }
}


Implementation Details

We have a global class, called QUiStyle, which (practically) has getters for each widget style who defines how it is painted. So, we would have some methods like: buttonStyle(), checkBoxStyle(), radioButtonStyle() and so on. Each specific style, e.g. Plastique, Cleanlooks, Widows, etc, will inherits from this base class and set the members that will be returned by the getters, to its specific widget style class, for instance, on the QUiPlastiqueStyle class, we will set buttonStyle member to an instance of QUiPlastiqueButton. So, it is easy for a developer to add its own Style (if he desires to make it on C++), he only has to define his new style class, inheriting from QUiStyle, and set the style widget members of QUiStyle to its own style widgets.

The following diagram can ease your understanding of the current code structure:

Proposal for a new QStyle modular architecture

For each type of widget we will have a class that calls the correct style class to paint it. For example, for the button, we have a class called QUiButtonStyle, which will ask for the QUiStyle a reference for the platform button style (calling the buttonStyle() method). Then, it will be drawn with the current platform look and feel. All the other widgets follows the same workflow.

Current implementation for the style components

In order to theme your application, we have a global object called appStyle and a QML component, called ApplicationStyle (presented in the QML example above). The ApplicationStyle component as a style property for each type of widget, e.g. buttonStyle, checkBoxStyle, radioButtonStyle, etc. These properties binds to the appStyle object analogue properties. So, if you want all your buttons of your application to have a CustomButtonStyle, you can simply do it as the example.

Development Status

Currently, we are focusing on creating a good set of working widgets for the Plastique style, but we are planning to implement another style parallelly, the CleanLooks is the favourite candidate.
Now, if you take a look at our repository, you will find the following widgets:

• Button
• CheckBox
• RadioButton
• Slider

Besides this, we have a CustomStyle for each one, e.g. CustomButtonStyle, CustomCheckBoxStyle, etc. If a user does not want to use the platform look and feel or create a style from scratch, he can use this Custom API to easily create his own styles.
The next widget that is planned to be developed is the ComboBox, also with his Custom Style.

Remarks

This first release was done using the QPainter to paint the widgets, instead of using the new SceneGraph. This was done in order to speed up our development and have a nice set of widgets working as fast as possible. In the future (close future) we will get rid of all QPainter based classes and replace them to use SceneGraph. The current custom styles already does that, but we would like to have them working for the platform styles as well, and we are already researching it.

The code in repository is mess because we are still doing a lot of changes, but we need to make it make it more stable and follow the Qt addons repository architecture until the end of the month. If you have any opinion, doubt or suggestion, please let us know.

Qt, KDE & Akademy 2012 Event Guide Application

I've been away from KDE activities from a time, because I was organizing a lot of stuff in my life. Happily I've finally arranged some time to hack more on the weekends. I'll try to keep up the work with the Plasma Components documentation, because I think it can be improved a lot. I will also try to come up with a few examples inside the documentation, to make easier for plasmoid developers.

Another long term goal for this year, which I already started to investigate, is how to optimize  Qt Components for more about the Qt QML Components, beyond Plasma, and I'm already investigating how can we do proper styling for Qt5.

In another thread, I'm also having a great experience by working with Nuno in an application for the Akademy 2012, at Tallinn, Estonia. The application it's basically a guide for the event, with essential information about it. It will also include a programme which will alert you about the presentations you want to attend to. And it's being such a great experience to share ideas with him!

Here are some snapshots of the app:

If you want to check it yourself, just clone the git repository for the app: git@git.kde.org:scratch/pinheiro/akademy2012

Cropping mp3 files with FFmpeg

Today, I was trying to find a free app for cropping a mp3 sound file. And I found a simple one with CLI. The FFmpeg is a multimedia files handler and it is pretty complex. But to do this task we will use the following parameters:

• -t chop after specified number of seconds
• -ss chop until specified number of seconds
• -acodec copy to maintain encoding and sampling rate
• -i use file as input file

And the final command was something like this:

ffmpeg -acodec copy -y -t $start_at -ss $ends-at -i $inputfile.mp3 $outputfile.mp3


Manifesto CodeCereal

Venho recebendo diversas críticas, de várias pessoas, que deixam de ler meus posts porquê são em inglês, além de tratar de "assuntos complicados". O fato é que eu estou deixando de divulgar muita coisa que faço e está em português e não tenho tempo para fazer a tradução de tudo, devido meu recurso finito de tempo. Também gosto de escrever em inglês como forma de exercício, além de dar uma maior dispersão dos posts. Portanto decidí tomara a decisão de tornar este blog híbrido onde quando possível farei posts em inglês, mas aproveitarei o meu material escrito em português, que caso contrário ficaria arquivado. Também continuarei a compartilhar o que for relativo a inteligência artificial no AIMotion e começarei a divulgar os posts relativos ao Qt aqui e no Qt Labs Brasil.

Espero que dê certo.

Back to Plasma Components

This last month I've been working slowly on my GSoC project due to the university activities (due to Brazilian academic calendar). And my thesis, which I shall talk in other post. But at least now I'm undergraduated!

As I explained in my last post about Plasma Components, my GSoC project. I'm building graphics components for developers to build plasmoids in QML using non trivial common components such as Sliders, ScrollBars and RadioButtons. After the break I've done these components following the Qt Components common API:

• Switch
• ButtonRow
• ButtonColumn
• ScrollBar
• ScrollDecorator

Keyboard event handling and focus policy for the new and old components were added in this sprint. I also spent a lot of time refactoring some components. I think their code is much better now.

I'm also adding more complex use cases at the components gallery (at kde-runtime/plasma/declarativeimports/test/gallery). By the way, this is screenshot of the new gallery:

Plasma Components Gallery

 

Part of the work was just straightforward, but there are some doubts I would like to ask which you think is the best, because some of the components behaviour are not defined.

1. Should ScrollDecorator appear only when it's flickableItem is flicked, like in the mobile use case?
2. ScrollDecorator must should look like ScrollBar or have it's own appearence?
3. There are no SVG graphics for CheckBox, RadioButton and Switch. Currently there are placeholders. What can I do?
4. Currently, when you click a component, it gains the focus. This logic must be in the components as it is? Or should left it external to the button.
5. The Qt Components doesn't define any enabled property, for any components. I think it's important to have such a property in all interactive components. What do you think about it?

Any other tip/suggestion is highly appreciated.

I expect to give other update as soon as I have something more to report.

PySide on CITi

Here is the PySide slides from the python course in CITi. Have fun!

CITi - PySide

View more presentations from Daker Fernandes.

Protein Profile with HMM

Profiling is the action of summarizing a set of data in a smaller mathematical model. One of the practical usages of profiling techniques is the classification of sequences. With a data set profile, you may calculate the distance of an instance to the model, and classify the instance trough this value.

Profiling proteins is a more specific case of profiling sequences. As we know from the previous ṕost about Hidden Markov Models (HMMs) is a very robust mathematical model to represent probabilistically sequences. This post will detail how to profile sets of proteins with a HMM model.

The HMM model for this problem must be a HMM which when we calculate a probability of generation of a protein by the model, must give higher probabilities for proteins similar for the ones used to create the profile against the others.

To build the model, I've started with a multiple sequence alignment to see how is the structure of the sequences. That means that our HMM will be a probabilistic representation of a multiple alignment. With the alignment we see that some columns are complete and some are almost, and the others have few data. These most common matches can be used as a common matches for our model and the deletions and insertions can be modelled as other states. Here is an example of a few sequences aligned and the core columns of the alignment (marked with an *):

A C - - - - A T G
T C A A C T A T C
A C A C - - A G C
A G A - - - A T C
A C C G - - A T C
* * *       * * *


With this sample of alignment we have examples of insertions and deletions between the core alignments, which may have a state on the HMM to represent them. Note that insertions may occur on arbitrary times between the matching states. And the deletion states always replaces some matching. One possible HMM template for building the model is presented in the following picture:

HMM protein profile model

Each matching state (M_j) is related to the matching on the j^th core alignment. The same applies for deletion state (D_j). The insertion is slightly different, because it represents the insertions between the core alignments, that's why it has one extra state, and this enable to represent states before the first and after the last alignment.

Our model will be like the one in the picture with the same length as the core alignments of a multiple alignment for a given set of sequences. However we should use maximum likelihood to estimate the transitions and emission for each state. The easiest way to count the total emissions/transitions, is to thread each sequence to be profiled in the model. For each symbol in the aligned sequence you must check if the symbol is in the core alignment. If it is, then increment the count of that state to the next match state, otherwise, you go to the insertion state. If it is a deletion, go to the deletion state and increment the transition. Finally, to calculate the probability for the transitions, just divide the count of each transition and divide it by all the states leaving the same state. It's important to notice that we have a stopping state, and this is a special state that has no transitions.

Note that is important to initialize the model with pseudo counts at each possible transitions. Adding this pseudo count, we let our model less rigid and avoid overfitting to the train set. Otherwise we could have some zero probabilities for some sequences.

To create the emissions probabilities, at each match state, you also have to count which symbol was emitted and then increment them. To calculate the probability, just divide it by the total symbols matched in the threading process. 

The similar process could be done with the insertion. However, the insertion states are characterized by having a low occurrence rate and this may lead us directly to a overfitting problem because the number of emissions must be too small. To avoid this we should use the background distribution as the emissions probabilities of each insertion state. The background distribution is the probability of the occurrence of a given amino acid in the entire protein set. To calculate this, count each amino acid type for all the train set sequence and then divided by the total count.

For the deletion states, it's important to notice that it is a silent state. It doesn't emit any symbol at all. To signalize it in ghmm, just let all the emissions probabilities with 0. Note that the end state is also a silent state once we have no emission associated to it.

ALERT: the loglikelihood is the only function in the ghmm library which handles silent states correctly.

At this point, the model is ready for use. However we have a problem of how to classify a new protein sequence. A threshold could be used to divide the two classes. However, the most common alternative is to use a null model to compare with it. The null model is a model which aims represents any protein with similar probability as any other. With this two models we could take a sequence and compare if it is more similar to a general definition of a protein or to a specific family. This model should model a sequence with average size equal to the aligned sequences being handled, and should emit any kind of symbol at each position. A common alternative for creating the null model, is using a single insertion state, which goes to a stopping state with probability of 1 divided by the average length of  sequences in the train set. For the emissions probability, we should use the background distribution, because this is related to the general amino acid distribution. At the end, the model should be like this:

Null Model

For testing the proposed model, I used a set of 100 globin proteins from the NCBI protein repository as a train set to build a profile model, and used ghmm to build and test the model.

To test if our model corresponds to our expectations, 100 globins different from the ones in the trains set were used with 1800 other random proteins with similar length. The loglikelihood function from the ghmm library to calculate the similarity index. The classification of the globins versus non globins, was a comparison between the likelihood of the protein with the globins profile hmm, and the null model. This test gave us 100% of accuracy! To display this result graph, each sequence was pointed out in a graph where the horizontal axis displays the length of the sequence and the vertical the log of globins / null models likelihood (or globins - null model loglikelihood). The globins are plotted in red an the others in blue. Proteins over the zero line are classified as globins, and below means they aren't globins. The graphs show us a clear distinction between the classes, and that our model is very precise for this problem.

Length x log(Globin's Profile Model Likelihood/Null Model Likelihood)

Encrypted Tweets

As a cryptography course project, me and @laisandrade developed a twitter extension which allows us to tweet in a way that only a group of followers can decrypt and understand my tweet. The goal is to secure broadcasting tweets to a group of followers and avoid anyone else to understand it's content. This definition of security is safe against a eavesdropping attack, which is considered secure enough for the common sense for cryptography, what is not true. Another concerns emerges when we consider other attacks or ways of extracting informations from the cyphertext, as an example the Known-Plaintext Attack.

Configuration of the Encrypted Tweets problem - Alice securely broadcasting messages to a specific group

In this project we should also consider other security issues such as forgery attacks and secure information storage. The only real world problem outside the project's scope was the private key distribution. We assume that the user who wants to share it's keys to his followers could use other mechanisms such as a Diffie-Hellman key exchange or using a trusted key broker. The full project's specification can be found here.

For doing the task we used the Grease Monkey Firefox's plugin. This plugin allow us to run custom javascript scripts in specifics web pages, so we can add functionalities to known web pages. In fact, we used a script stub for doing it. This script adds a encrypt tweet functionality as well as a key manager at password settings page. It also gives a function to store (unsafely) the user information. Was also our job to make it secure. We assumed that the script couldn't be cracked, the focus where we were concerned was about the information safety outside the script execution memory.

Encrypt button and Group selection close to Tweet button


============================== Encryption Specification ==============================

Encripted Message:
+--------+-----+--------------------------------------+
| "aes:" | Ctr | Extended-AES(Content, Ctr, GroupKey) |
+--------+-----+--------------------------------------+
* The Ctr is the base counter for the CTR block chaining cypher. Every message picks a random Ctr.
* The group key is the key to the group whom members are the only who should understand the message.
* The Extended-AES function will be detailed after.
* the "aes:" indicator is not a security threat due to Kerckhoffs's Principle.

Content:
+---------------+---------+
| sha1(Message) | Message |
+---------------+---------+
* The sha1 cryptographic hash is used to check the integrity of the stored keys and avoid modifications on the massage bypass as a real message.
* The sha1 produces a 160 bits length message, which is convertes into a base64 string to send it over twitter.
* This Message Authentication Code (MAC) is necessary for Chosen Ciphertext Security (CCA Security).

Message: the original message
======================================================================================


For our Extended-AES implementation, we used a Cypher Block Chaining to extend the AES block cypher, that we use as a block cypher. To do this we used a Counter (CTR) chaining to extend the cypher. Note that the CTR mode uses a base counter (Ctr) as an Initialization Vector (IV) which also must be transmitted to enable to be decrypted. This IV is chosen at random by our pseudorandom generator. If the IV is not truly random, an attacker may predict the IV sequence and get more information from the message. A real problem faced by pseudorandom generators are when the seed selection are not truly random. To handle this, the script stub creates a seed using the mouse positions at the first seconds of running (an entropy test is also used to check the randomness of the seed).

When someone receives a "aes:" tagged message, the script checks the author of the message and get the key provided by him. To decrypt, we also use the Extended-AES since it is symmetric (due to XOR reversibility property). At last the SHA-1 hash is confronted with the message to check if the key is correct or the message suffered a forgery attempt.

To store the groups keys we used the grease monkey's key value storage (GM_setValue and GM_getValue functions). We store and recover the values from the key "twit-key-" + login, which is stored as plaintext in the hard drive. To avoid the stealth of this information from other users, virus or worm we added an encryption layer over it. The stored data representation developed was this one:

Keys management screen


==============================   Safe Storaging Specification   ==============================

Stored Data:
AES(Data, MasterKey)

MasterKey:
User secret key to access all the other keys. This key requires user input every time it logs in.

Data:
+---------------------+-----------------+
|   sha1(GroupKeys)   |   Groups Keys   |
+---------------------+-----------------+
* This cryptographic hash is used to check the integrity of the stored keys.
* A malicious agent may override the values on the keys and may set the keys he can decrypt.

Groups Keys:
+----------+----------+----------+----------+---------+----------+----------+
|   Item   |   "$$"   |   Item   |   "$$"   |   ...   |   "$$"   |   Item   |
+----------+----------+----------+----------+---------+----------+----------+

Item:
+----------+---------+-----------+---------+---------+
|   User   |   "$"   |   Group   |   "$"   |   Key   |
+----------+---------+-----------+---------+---------+

User: base64 string
Group: base64 string
Key: base64 string

==============================================================================================


It's important to notice that we implemented the SHA-1 hashing algorithm to ensure the data wasn't modified while stored or transmitted. We trust it wasn't modified due to the difficulty to crack the AES cypher to forge a new MAC. And if the attacker try to change bits from the stored data, we trust that SHA-1 hash collision difficulty will be enough to ensure us that someone will be able to produce valid message, hash pairs without looking at the plaintext. If the pair is corrupted, then the user is alerted that someone modified his keys. By doing this, we may disable an attacker to modify bits from our keys and have better chances to crack the scheme. The SHA-1 also has some theoretical weakness, however, in practice it still is a very strong cryptographic hash function.

The ePassport Standard and it's Cryptographic Scheme

ePassport is the name given for the new passport specification standardized by the International Civil Aviation Organization (ICAO). It was created to speed up and standardize the immigration procedures. This standard specifies RFID as the communication channel between the passport and the reader. The main feature present on it is the insertion of biometric data into the passport for biometric checks, including facial recognition, fingerprint and iris information. To keep this important data protected, an interesting cryptographic layer was added in addition to the usual document falsification mechanisms such as watermarks.

Brazilian ePassport. One of few which has full compatibility with the ICAO specification.

The name, nationality, birth date and other personal information as well as the biometric informations are held on a contactless chip inside the passport. This set of information are securely handled and is called the Machine Readable Zone (MRZ) and the chip asserts their security. These informations are transmitted to a ePassport reader at immigration process. As the embedded chip has low processing power, the biometric data is transmitted to a reader so it can be checked against the porter of the passport.

Anatomy of an ePassport

As the physical communication layer of the ePassport broadcasts the messages, even with the low range (less than a meter) RFID communication. But as we know an eavesdropper can be very determined to listen the communication ;-). I also has an electromagnetic shield on the passport cover, however it doesn't assure to block the communication between the chip and the outside world when it's closed, however it's an extra obstacle. Another issue to prevent is the passport and digital data forgery. Otherwise a falsary could get someone else passport and insert it's biometrics information and easily bypass the immigration. As we may see, the ePassport is a complete meal for cryptography specialists.

Starring at this cryptographic layer we have: 

A unique id used as a private key. This key is hardcoded in the chip manufacturing process and it's non traceable. Doing reverse engineering on this kind of chip it's really difficult because the equipment to do it is extremely expensive and hard to obtain, it is only available to large chip manufacturers.

An access control to prevent an attacker to force the ePassport to send information in the MRZ to readers unless the passport owner authorizes it. Otherwise an attacker could use a reader and simply request the biometric information to the passport. It uses a protocol called Basic Access Control (BAC) to give access for the reader. It consists on a OCR readable code inside the passport. With this code, the reader can say to the passport it is an authorized reader, and then transmit data to it. The BAC code is also used as key for the encrypted transmission of the data, making an eavesdropping attack more difficult. It's important to note that the BAC security entirely relies on the physical access to the passport. The BAC is inside the ICAO standard but doesn't obligates it's support.

BAC happy path's sequence diagram

The ICAO also standardizes a authentication for readers called Extended Access Control (EAC). It consists of sets of signatures of terminals stored in the passport's chip. These signatures are changed periodically by the countries (which signs them) on the terminals to avoid keys stolen from equipments being used for much time. Some MRZ sensitive data, such as iris and fingerprint, are just transmitted to readers if it is EAC authenticated. Other informations are optional.

EAC happy path's sequence diagram

The Passive Authentication (PA) is a cryptographic mechanism  to ensure the data in the passport is valid by the authority emitting the passports. The PA is a kind of digital signature where the country who emits passports ensures the veracity of the data with a asymmetric Country Verification Certificate Authority (CVCA), a kind of message authentication code (MAC). This process is known as asymmetric cryptographic hashing or digital signing. The PA MAC is created by the country when emits a passport, which must keep a signing key safe, which is used to create the MAC code. Then it publish the public key (all readers must know the countries public keys) which can be used to check if the MAC is valid and it was really generated by the organization which possess the signing key. The PA scheme relies on mathematical functions which are easy to encrypt a MAC with the private key, but computationally hard without them. The public key can easily check if the MAC was generated by the ones who posses the private key, and detect forged data. This process makes the forgery of digital data a really hard computational problem, and ensures with negligible chance of failure that the data is valid. All the MRZ data is signed using such process. Using PA is mandatory by ICAO standards.

PA happy path's sequence diagram

The Active Authentication (AA) is a kind of challenge response authentication mechanism to prevent the cloning of passports. It relies on the untraceable chip key. Cloning the MRZ data is a simple task to be done, however you can't get a passport private key due to the difficulty of doing reverse engineering to obtain it. The AA works as a challenge to the passport, so you can verify if it really is. The reader encrypts a random message that only him knows it's content with the passport's public key. The message is then sent to the passport and it must decrypt and response to the reader what was the original message. This process works because of the duality principle of asymmetric cryptography. This concept of challenge is the same concept behind CAPTCHAs and the Turing Test.

AA hapy path's sequence diagram

Optimizing Functions with Python Caching Decorators

On these last months I've been solving some problems (such as some HMMs algorithms) which the best solutions involves some kind of dynamic programming. Some of them are quite simple to implement, but their recursive formulation are far more intuitive. The problem is that even in functional languages, the recursive functions aren't well handled unless you some mechanism like tail call, which aren't intuitive as we would like to. The simplest example that comes in my mind is the fibonacci function which is usually defined as:


fib(0) = 1
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)



As we know, almost all the languages compilers and interpreters use the call stack to call the recursives cases on functions being executed. We can analyze the following C fibonacci version:

int fib(n)
{
    if (n == 0 || n == 1)
        return 1;
    else
        return fib(n-1) + fib(n-2);
}



It is really simple to understand when contrasted with the definition. But, if we make a trace of the the program (even with a small input value) we'll have something like the following evaluation order:

fib(6) = fib(5) + fib(4)
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)


Call stack for fib(6)

As we can see, there is a repetition of the calculation of fib 4 to 1, many times and is something we can avoid. In fact, the complexity of this solution has a exponencial computational complexity because for each n from input we branch it in 2 until it reachs 0 or 1 approximately n times, leading us into a O(2ⁿ) complexity. A simple way to avoid it, is converting into a interactive form:

int fib(int n)
{
    int current = 1;
    int previous = 1;
    int i;
    for (i = 1; i < n; i++) {

        int temp = current; // XXX: nasty
        current += previous;
        previous = temp;
    }

    return current;
}


The same result is achieved by using tail call for functional languages.

As you can see, it obfuscates the intuitive definition given in as the recursive formulation. But we still have a problem whenever we calculate fib(n), we have to recalculate it's previous results even if they was previously calculated. If this function is used many times in our program it will take a lot of processing re-computing many of the values. We can avoid this by using the dynamic programming, which keeps the record of previously calculated results. The drawback of this technique is the memory usage, which for large entries can become a bottleneck. However, processing usually is a more rare computer resource. A C implementation (not the most elegant) for it is:


// XXX: kids, don't do this at home
int fib_results[10000];
int last_fib;

int fib(int n)
{
    if (n <= last_fib
        return fib_results[n];

    int current = fib_results[last_fib-1];
    int previous = fib_results[last_fib-2];
    for (; last_fib < n; last_fib++) {
        int temp = current;
        current += previous;
        fib_results[last_fib] = current;
        previous = temp;
    }

    return current;
}

int main()
{
    fib_results[0] = 1;
    fib_results[1] = 1;
    last_fib = 1;

    // ... other stuff ...

    return 0;
} 



As we can see, dynamic programming isn't too hard to implement. On the other hand, reading a code it's a though task to do unless you are already familiar with the algorithm.

If we extract what is dynamic programming fundamental concept, which is "store pre-computed results", we find a regularity in every recursive function which we can be transformed into a dynamic programming one. One of the reasons I love python because it's easy to use meta-programming concepts, and that's what I will use to transform recursive functions into it's dynamic form in a ridiculous easy way using function decorators.

Function decorators (or annotations in Java) are a form of meta-programming for functions. It extends functions with some functionalities, such as debugging, tracing, adding meta-data to the function, synchronization or memoization (not memorization) of values, which is a great way of optimizing recursive functions by caching their results (if you have enough memory available). One possible implementation of memoitized decorator in python is the following:


def cached(function):
    cache = {}
    def wrapper(*args):
        if args in cache:
            return cache[args]
        else:
            result = function(*args)
            cache[args] = result 
            return result

    return wrapper

Note that I'm not using kwargs because they're not hashable, such as the tuple args, and will add a few complexity in the example. See also that we a have a function that returns another function, which uses a given one to calculate results and store them in a cache. To cache our fib function we may use the following code:

@cached
def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

# or in a not so clean version:
def normal_fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

fib = cached(normal_fib)



This technique is really useful to improve your code performance in a really easy. On the other hand, it isn't the best solution for almost all the cases. Many times code a dynamic programming method (if performance is crucial) will be necessary. Is also important to notice that I didn't used any cache memory management policy, which is important to economize memory. Most appropriate cache data structures (such as numpy arrays for integer arguments) also are welcome. The python 3.2 version added the lru_cache decorator into the functools module to make this cache mechanism. If you are already using this version, it's smarter to use it instead of implementing your one. Here is how it must be used:

# Python > 3.2
import functools
@functools.lru_cached(max_size=500) # uses a fixed size cache to avoid memory usage explosion
def fib(n)
    ...



This technique is very useful not only for economize the CPU resources but also network (such as caching SQL query results), other IO operations (such as disk reading) and even user interaction input in a straightforward way.