GSoC 2017 progress so far

Hi,

This post serves as my first main post relating to the GSoC project I’ve been working on. Earlier I discussed how to set up the development environment.

Introduction

Recently I got accepted as a student for Google Summer of Code 2017 to work on Mesa to add a new OpenMax IL state tracker that uses tizonia instead of bellagio that the current state tracker uses.

Project link: https://summerofcode.withgoogle.com/projects/#4737166321123328

Project proposal: https://docs.google.com/document/d/1BM1LdSPVAQRsle1O_jj9Ssq52Z0HHlY8XwYY5y9j6Lk/edit?usp=sharing

Progress so far

Most of the effort till now has been to make tizonia compatible with gst-omx so that we can test out the new component.

Changes in gst-omx

The commits are are on my github fork https://github.com/gpalsingh/gst-omx/commits/tizonia

The first thing needed to use gst-omx to test for OMX IL 1.2 was to add tizonia as a target. https://github.com/gpalsingh/gst-omx/commit/0aff53c9f01f04a09b41b01a313afa7255ad20a1 is the last of the three commits to do the same. They simply involve adding tizonia target in addition to bellagio, generic and rpi. Right now it needs external IL headers unlike other targets that can fall back to internal headers in case no external IL headers are available.

Next we worked on making it work with the mp3 decoder component that comes with tizonia. Luckily that needed only small change to ignore an error https://github.com/gpalsingh/gst-omx/commit/2f8be06754077847c3f0a0862e6336fe37907e5e

Right now work on getting the tizonia vp8 decoder to work with gst-omx is in progress. It is possible to play the video but there are still some improvements to be made.

Changes to tizonia

Since tizonia is more aligned to audio cases it is was still missing and AVC port. As Juan suggested in our discussion here https://github.com/tizonia/tizonia-openmax-il/issues/319#issuecomment-304410741, I added the new AVC port to tizonia which was merged after Julien fixed some minor errors in it https://github.com/tizonia/tizonia-openmax-il/commit/9c9e6d0f74b6c80984b48d71c46ae52d46d83b7d.

This mostly involved changing the existing code from the VP8 port according to the AVC port as given in the OMX IL specifications. It would need still more work later on for initialising the structures that depend on different profile levels which is currently marked as TODO.

New component

This work is the main project work involving adding the new component to mesa/gallium.

Main branch

On this branch I keep the final work that is (almost) ready to be commited. It is located at https://github.com/gpalsingh/mesa/tree/gsoc

Currently it is complete up to adding an empty component to the omx-tiz state tracker, the openmax state tracker that uses tizonia. It can be used by passing the –use-omx-tiz argument to autogen.sh script.

Dev branch

This is the branch that I do all the experimental work on. It is located at https://github.com/gpalsingh/mesa/tree/gsoc-dev

To avoid confusion this branch uses omx_tizonia instead of omx_tiz in all places.

I’ve added an H.264 decoder which works with tizonia. It uses most of the code from the existing bellagio H.264 state tracker. Bellagio uses a private class (priv) to hold the decoder data while tizonia uses a processor (p_prc) for similar purpose. So it just needed to replace priv with p_prc.

Currently I’m working on improving the decode_stream function that decodes the input stream and shows the ouput https://github.com/gpalsingh/mesa/blob/gsoc-dev/src/gallium/state_trackers/omx_tizonia/h264dprc.c#L1242

In bellagio the decoding and buffer management take place in two different functions (vid_dec_DecodeBuffer and vid_dec_FrameDecoded) whereas in tizonia only one function does the work of both (*_buffers_ready).

I’ve used h264d_frame_decoded as replacement for bellagio’s base_port_SendBufferFunction since while checking with gdb I noticed it invokes vid_dec_FrameDecoded which performs the output and is the buffer management function for bellagio. https://github.com/gpalsingh/mesa/blob/gsoc-dev/src/gallium/state_trackers/omx_tizonia/h264dprc.c#L1296

For replacing port->ReturnBufferFunction (https://cgit.freedesktop.org/mesa/mesa/tree/src/gallium/state_trackers/omx/vid_dec.c#n519) I’m trying out h264d_release_input_buffer.

Trying with that gst-omx compiled for tizonia shows a blank window and the execution stops after that (without any error thrown). My focus will be on fixing this in the upcoming week and hopefully have a working decoder soon.

Advertisements

Setting up development environment for Gallium state tracker development

In this post we will be looking at the process to set up the development environment that I used for working with state trackers in Mesa/Gallium. We will be using gst-uninstalled as the uninstalled environment.

Get the main packages

These are the packages we’ll be testing. We’ll be using Mesa and libva. Mesa has the state trackers and libva because Mesa uses it. We won’t be installing them now as the testing environment still needs to be set up.

First make a folder where all the stuff goes.

$ mkdir ~/tutorial
$ cd ~/tutorial

Then clone mesa into it.

$ git clone git://anongit.freedesktop.org/git/mesa/mesa

Next is libva.

$ git clone https://anongit.freedesktop.org/git/vaapi/libva.git

Install bellagio

$ sudo apt install libomxil-bellagio*

Install tizonia (originally from https://github.com/tizonia/tizonia-openmax-il#installation)

$ curl -kL https://github.com/tizonia/tizonia-openmax-il/raw/master/tools/install.sh | bash
# Or its shortened version:
$ curl -kL https://goo.gl/Vu8qGR | bash
$ sudo apt-get update && sudo apt-get upgrade

Setting up testing environment

Get Gstreamer

(From the official homepage) GStreamer is a library for constructing graphs of media-handling components. Applications can take advantage of advances in codec and filter technology transparently. Developers can add new codecs and filters by writing a simple plugin with a clean, generic interface. Here we will be using the gst-omx and some other plugins for testing.

First build the dependencies for Gstreamer.

$ sudo apt-get build-dep gstreamer1.0-plugins-{base,good,bad,ugly}

Get the installer script

$ curl -O https://cgit.freedesktop.org/gstreamer/gstreamer/plain/scripts/create-uninstalled-setup.sh

Edit the script and add gst-omx and gstreamer-vaapi to “MODULES”

MODULES=”gstreamer gst-plugins-base gst-plugins-good gst-plugins-ugly gst-plugins-bad gst-libav gstreamer-vaapi gst-omx”

or you can clone them later manually. Other options like BRANCH and UNINSTALLED_ROOT can also be changed to your liking.

Run the script and wait for it to finish.

$ sh create-uninstalled-setup.sh

This will install the plugins in ~/gst directory.

Using the environment

The script will give you additional information before exiting which you should take note of. The instructions here are general.

Enter the environment with

$ ~/gst/gst-master.

This will take you a to ~/gst/gst-master in the uninstalled environement (a bit similar to python’s venv).

Use

$ exit

to exit out of the uninstalled environment anytime.

To make it easier to use you can link it to bin in your home.

$ mkdir ~/bin; ln -s ~/gst/gst-master ~/bin/gst-master

And then add this line in your bashrc / bash_profile

export PATH=$PATH:~/bin

Load the changes

$ source ~/.bashrc

Now you can simply use it like a command

$ gst-master

More details could be found here: https://arunraghavan.net/2014/07/quick-start-guide-to-gst-uninstalled-1-x/

Firmware installation (Optional)

You need to do this only if you are using NVIDIA graphics card like I did.

Use the following commands to install the firmware for your NVIDIA graphics card:

$ mkdir /tmp/nouveau
$ cd /tmp/nouveau
$ wget https://raw.github.com/imirkin/re-vp2/master/extract_firmware.py
$ wget http://us.download.nvidia.com/XFree86/Linux-x86/325.15/NVIDIA-Linux-x86-325.15.run
$ sh NVIDIA-Linux-x86-325.15.run --extract-only
$ python2 extract_firmware.py  # this script is for python 2 only
# mkdir /lib/firmware/nouveau
# cp -d nv* vuc-* /lib/firmware/nouveau/

More details could be found on the official page: https://nouveau.freedesktop.org/wiki/VideoAcceleration/

Installing modules

Now that we have the base set up, we can proceed to installing the packages to finish the setup process. Note: You should be uninstalled environment before proceeding.

Install Mesa

First move to the mesa directory

$ cd ~/tutorial/mesa

Then use the autogen.sh script to configure everything

./autogen.sh \
 --enable-texture-float \
 --enable-gles1 \
 --enable-gles2 \
 --enable-glx \
 --enable-egl \
 --enable-gallium-llvm \
 --enable-shared-glapi \
 --enable-gbm \
 --enable-glx-tls \
 --enable-dri \
 --enable-osmesa \
 --with-egl-platforms=x11,drm \
 --with-gallium-drivers=nouveau,swrast \
 --with-dri-drivers=nouveau,swrast \
 --enable-vdpau \
 --enable-omx \
 --enable-va \
 --prefix=/home/gurkirpal/gst/master/prefix/

Note the the prefix is ~/gst/master/prefix. It is necessary to use it otherwise mesa will be installed in default location. In case you used a different UNINSTALLED_ROOT and/or BRANCH you should change it accordingly. Also nouveau is in case for NVIDIA graphics card which is the driver.

Finally make and make install.

$ make -j8
$ make install

This will install mesa in ~/gst/master/prefix and could be used in the environment. This means even if you break something during testing your system wide installation will be unharmed.

Install libva

Similar to Mesa, we just need to give the prefix before configuring

$ cd ~/tutorial/mesa
$ ./autogen.sh --prefix=/home/gurkirpal/gst/master/prefix/
$ make -j8
$ make install

Instal Gstreamer and modules

The modules downloaded by the gst-uninstalled script still need to be installed before using them.

Just need to move to the ~/gst/master directory and use the automated script in ~/gst/master/gstreamer/scripts/git-update.sh which will do all the work for you.

You will have to edit the script to add extra modules like gstreamer-vaapi (only those which don’t need extra arguments)

EXTRA_MODULES="\
 gstreamer-vaapi \
 gst-editing-services \
 gst-rtsp-server \
 gst-python"

or you can choose to do it manually, starting with gstreamer then gst-plugins-base then any others in any order

$ ./autogen.sh
$ make -j8

We still need to install gst-omx manually because we will be using different omx targets

$ cd gst-omx
$ ./autogen.sh --with-omx-target=bellagio
$ make -j8

Note that we need to use “make install” with the gstreamer modules.

Checking the environment

Here are some tips to check if you have set up the environment correctly.

Checking mesa install

Running

$ glxinfo

should give different info from when invoked outside the environment.

For example, Outside the env

$ glxinfo | fgrep "OpenGL core profile version string"
OpenGL core profile version string: 4.3 (Core Profile) Mesa 17.2.0-devel - padoka PPA

In the uninstalled env

$ glxinfo | fgrep "OpenGL core profile version string"
OpenGL core profile version string: 4.3 (Core Profile) Mesa 17.2.0-devel (git-5ff4858)

Checking firmware install

In case you installed the NVIDIA firmware, after installing the firmware you should have lots of files in /lib/firmware/nouveau/. For brevity I’m only showing the number of files that I have.

$ ls -l /lib/firmware/nouveau/ | wc -l
221

The number of files you have should need not be exactly same.

Checking Gstreamer install

Just check if you are using the uninstalled version of gst-*

$ which gst-inspect-1.0
 /home/gurkirpal/gst/master/gstreamer/tools/gst-inspect-1.0
$ which gst-launch-1.0
 /home/gurkirpal/gst/master/gstreamer/tools/gst-launch-1.0

Checking gst-omx install

$ gst-inspect-1.0 omxh264dec

should show information about the omxh264dec plugin. Otherwise you’ll get an error message like this

$ gst-inspect-1.0 omxh264dec
No such element or plugin 'omxh264dec'

Checking VA-API installation

Running vainfo should give output similar to as shown below

$ LIBVA_DRIVER_NAME=nouveau vainfo
libva info: VA-API version 0.40.0
libva info: va_getDriverName() returns 0
libva info: User requested driver 'nouveau'
libva info: Trying to open /home/gpalsingh/gst/master/prefix/lib/dri/nouveau_drv_video.so
libva info: Found init function __vaDriverInit_0_40
libva info: va_openDriver() returns 0
vainfo: VA-API version: 0.40 (libva 1.8.0.pre1)
vainfo: Driver version: mesa gallium vaapi
vainfo: Supported profile and entrypoints
      VAProfileMPEG2Simple            :    VAEntrypointVLD
      VAProfileMPEG2Main              :    VAEntrypointVLD
      VAProfileVC1Simple              :    VAEntrypointVLD
      VAProfileVC1Main                :    VAEntrypointVLD
      VAProfileVC1Advanced            :    VAEntrypointVLD
      VAProfileH264ConstrainedBaseline:    VAEntrypointVLD
      VAProfileH264Main               :    VAEntrypointVLD
      VAProfileH264High               :    VAEntrypointVLD
      VAProfileNone                   :    VAEntrypointVideoProc

You can use the following pipeline to test if gstreamer-vaapi is working fine:

$ gst-launch-1.0 filesrc location=any_video.mp4 ! qtdemux ! h264parse ! vaapidecodebin ! videoconvert ! ximagesink

This should bring up a video window without any audio.

To quit switch to terminal and press Ctrl + C.

You can find clips for testing at http://www.h264info.com/clips.html

Quick Vim tutorial

What is Vim?

Vim is basically a text editor for editing files in linux systems which is also available for windows. Vim stands for “Vi IMproved” because it is an open source clone of the original “vi” editor for unix.

I started using vim a few months back and liked it so much that I now use it all the time.  Although there are plenty of tutorials and books from which you can learn from, it is still difficult to get started with Vim. This because normally they give you much more information than you need as a beginner. It took me a few weeks to properly learn even the basic editing commands because I had to constantly search for them in long command tables. And it took a few months of practice, searching and reading to get my speed high enough in vim. Because of that I decided to share some of the most useful features of Vim at a single place so that you could save your time.

Should you learn Vim?

But before we begin we need to make sure that you actually need to learn vim or not and if you should be reading this. Answer all the following as yes or no:

  • You know touch typing.
  • You know a programming language.
  • You program almost every other day.
  • You don’t use any advanced editing tool already or don’t like it.
  • You get frustrated while moving to line 625 just to fix a typo.
  • You are new to vim.
  • You want to get productive fast.

If you answered all of them as yes then you can skip the next section and carry on. Otherwise read the following section according to your response.

  • You don’t know touch typing – Then do it. It would mostly take a week or so.
  • You cannot program – The point of this post is to learn Vim to program faster. Besides it will be very bad idea to learn Vim and programming together.
  • You don’t program very often – Better use an IDE.
  • You already use IDE or advanced editor – Never switch editors just because the other one sounds cooler. Just stick with it.
  • You are OK with slow editing (really?) – You will benefit from Vim but it is your choice.
  • You already know some Vim – In case you are a beginner just have a quick look. Maybe you will find something new. Otherwise the stuff is really basic and without much depth.
  • You have lot of time for learning everything in detail- Pick up a good book.

Getting started

Before we start you need to remember these thing throughout the tutorial:

  • Even if a some commands sound stupid and/or unnecessarily complex than normal editors they will you will eventually realize that it is the best way to do things and actually make things faster. Just take my word for now and see for yourself.
  • Vim is case sensitive. Don’t forget to turn your caps lock off.

Installing

Vim is most probably already installed on your system if you are using linux. To install vim or to upgrade it use

$ sudo apt install vim --upgrade

if you use ubuntu. The command for other systems is similar.

There are also a windows, unix and mac versions available. There is even an android version available if you are curious.

Starting

Vim runs in terminal. In your system terminal type

$ vim

This would bring up a screen like this.

vimstart

Vim modes

Vim basically has three main modes insert, command and ex. The command mode is normally called “normal” mode but it is not actually normal for most beginners so we will call it command mode. The following diagram shows which keys to press to move between them.

vimmodes

Vim starts in command mode. In insert mode vim mostly behaves like notepad. In ex mode your cursor moves to bottom of the line. You don’t need to understand them right now. Just make sure that you know how to move between them.

Each vim command needs a specific mode to work. Although I could have just listed commands according to type, I have instead listed them in the order that I would have prefered while I learned them. To avoid confusion have specified the mode with each command where applicable. Following are the abbreviations I use below.

  • [IM] – Insert Mode.
  • [CM] – Command Mode.
  • [EM] – Ex Mode.
  • [SH] – Shell command. Although it is not a mode but it makes things clearer.

TIP: If you have a problem with any command below press Escape key a few times and then try again.

Quiting [EM]

You wouldn’t believe me but this is the most difficult part. Most people give up here and end up as Vim haters. Although there are various ways to quit vim, you should move to ex mode and use “:q!” for now.
This will work in almost all the cases, no matter what. “q” Stands for quit. “!” means forced quit. This would discard all the unsaved changes to file and quit. This is analogous to quit without save.

Inserting [IM]

Unlike normal text editors you can’t just enter text into vim right away. You need to be insert mode. You should read “– INSERT –” in the bottom line of the editor if you are in this mode. You can now freely enter any other text editor.

Saving [EM]

To save the file you first need to go back to command mode. Just press “Esc” key. The “– INSERT –” in the bottom line should disappear. We are now in the command mode. When the cursor moves to end of screen enter “w <file_name>” where file_name is name of file to save to without spaces. For eg: “:w tutorial.txt”

Opening / Creating a file [SH]

Now exit vim. To open an existing file just use “vim <file_name>”. For example:

$ vim tutorial.txt

If file didn’t exist then vim will create it. When opening file in such manner you no longer need to tell the file name and can use just “:w” to save the file as vim already knows the file name.

Moving the cursor [CM]

Vim does not use arrow keys by default to move the cursor. Instead it uses the keyboard keys h, j, k and l for left, down, up and right respectively. At first they might sound stupid as a, s, w and d make more sense but if you know touch typing then it makes sense as they are faster to reach.

640px-qwerty-home-keys-position-svg

Start position with fingers on the home row. (source: Wikipedia)

 

But still getting used to it is difficult if you try to do it by practice only. I found a little hack to learn it more easily. You just need to play any racing game with keyboard keys. Yes that’s true! Just play it differently. Place your index finger on the down arrow key, middle one on the up arrow key, next one on the right arrow key and the last one is free. Use the index finger to use both down and left arrow keys but always keep it on down key. Now play some car racing game with this hand position. It will feel quite uncomfortable but it works. Next time you use vim moving the cursor will feel much easier.

Delete character [CM]

One way to delete character is to go in insert mode and use “backspace” key. But you can delete characters  in command mode too. Just place the cursor on any character and press “x” key to delete it.

Delete a line [CM]

Move the cursor to the line you want to delete and press “dd”.

Undo [CM]

To undo any previous edit press “u”. Keep undoing by pressing “u” again.

Redo [CM]

No it’s not “r” but “<Ctrl> + r” because “r” is already used for replacement. Remember this.

Inserting in already present text [CM]

Insert to the left of the character under the cursor – “i”.

Insert to the right of the character under the cursor – “a”.

“i” is for insert. “a” for append.

Adding new line [CM]

You can add new line by moving to end of the line, pressing “a” and then pressing enter. Pressing “o” would do the same thing in just one key stroke!

Save and quit [EM]

You can save with “:w” and then quit with “:q” or you can combine both commands as “:wq”. Even shorter is “:x” if you prefer it, which does the same work.

Numbered commands [CM]

Let’s face it. Moving the cursor by repeatedly pressing l, h etc. is too slow. When you already know you want to move 3 lines down press “3j”. To move eight characters to the right is “8l”. To delete four characters to the right press “4x”. Basically, pressing a number before any command mode command will repeat it that many times. General yntax is number following by any CM command.

An example: You can use it while inserting text too! Just press “200i” and write anything. Move back to command mode and that text will be repeated 200 times.

Copy [CM]

To copy the line on which the cursor is, just press “yy”.

Paste [CM]

To paste the copied text press “p”. The text will be pasted in the line below.

Cut [CM]

You can cut a line with “dd”. Wait, didn’t I say that it is for deleting? Well, it actually is neither but it works like that. Also the “x” command too works like cut command. You can paste the deleted character(s) by pressing “p” anytime.
Example: Suppose you missplled “Dennis” as “Dennsi”. First place the cursor on “s” in CM and press “xp”. This will fix it .Try it.

Repeat [CM]

Let’s suppose you are deleting lines that are far apart. You first move to first line using “dd”. Next you move to another line and instead of using “dd” again you can just press “.”. It will delete this line. Pressing the “.” key repeats the last command mode command.

Indenting code [CM]

Let’s say you want to add a tab in the beginning of the current line. You can press “I” and then “” key or use “>>”. Pressing “>>” in command mode moves the line to the right by one indent. The opposite command is “<<“. “3>>”will not increase indent by three tabs but increase indent of next three lines by one tab.

Moving the cursor in long lines [CM]

If you want to edit long lines then simply moving with numbered command like “5l” is not fast and accurate enough. If you want to start editing after ‘)’ character in current line, use “f)” this will move the cursor to the first “)” character to the right. To move to next occurrence press “;” and to move to previous use “,”. You can say “ft” is like saying “find letter t in current line and move cursor to it”.

Find text in file [EM]

I use this a lot. This is the “<Ctrl> + f” of Vim. To search a (sub)string press “:/”. This will move the cursor to the bottom. Enter the search string and press enter.
To find the next occurrence press “n” and “N” for previous one.
One thing to note is that search is case sensitive. To make it case insensitive enter “\c” before pressing enter.
For example, “:/Blah” is case sensitive and “:/Blah\c” is case insensitive.
You could actually skip the “:” and just use “/Blah”.

Find and replace [EM]

The command is “:s” followed by “/search” followed by “/replacement”. The full command is “:s/search/replacement”. This works only for current line. To replace everything in whole file use “:%s/search/replacement/g”.

Open file at line number [SH]

You can open a file at a specific line buy usin the “+” argument

$ vim +80 file.c

Will open file.c at line 80.

Example: Most programming languages provide a stack trace informing the cause of error. The trace usually includes line number. You can use this argument to quickly move to that line while opening the file.

Switching to shell [EM]

You can start a shell from vim by using “:sh”. To quit it just press “<Ctrl> + d” and you will return to vim. If you want to save your work before opening shell use “:wa|sh” instead (“| is pipe symbol”).

Example usage: While testing the program you have to constantly open vim, edit, close, test cycle or use two terminal sessions. This command removes the need for both.

The things to remember:

  • This shell is new one. You’ll need to reactivate virtualenv.
  • This shell is temporary.
  • This shell does not have same history as the shell in which vim is running.

You can always check that you are inside a sub shell by using “ps” and seeing if vim is in the list.

Move to line number [CM]

To move to line 237 use “237G”

Moving gg and G [CM]

Move to top of line – “gg”
Move to end of file – “G”

Jumping back [CM]

Suppose you are editing a C file. You use “gg” and add an import statement. Now you want to to move back to where you came from. Use ” ” ” that is, press ‘ (single quote) two times.

Marks [CM]

Marks are similar to jumping to different places in a file. Move to any part of file and press “mm” or “m”. You have made a kind of bookmark there. To move there from any other place use ‘m or ”.
You can make any number of marks in a file. They will be deleted after exiting file. List all current marks with “:marks”.

Folds [CM]

Foldings allow you to fold parts of file to provide better readability. To make a fold first

  1. Press “v”
  2. Select the text
  3. Press “zf”

To open a fold use “zo” and “zc” for closing.

This is extremely useful while reading large code files.

Splits [EM]

To start a split use “:vsplit”. Now you can edit two files on one split screen. Move to left split with “<Ctrl> + w + h” or right split with “<Ctrl> + w + l”. Just like normal cursor commands, prefixed with “<Ctrl> + w”.

Tabs [EM]

For now you can assume that a tab in vim is just like in a browser or in an editor like sublime text.
To make a new tab use “:tabe”. You can move to next tab with “gt”.

File Explorer [EM]

Explorer can be used in vim to open files interactively. Use “:Explore” to open it.
This can be useful while opening a new blank tab.
To open a file press enter on it or “t” to open it in a new tab.
The explorer supports searching with “/” just like in a normal file.

Save sessions [EM]

Vim will not save any folds, tabs or marks by default. To store a session use “:mk “. This will make a new file “session_name” in the directory where vim started. Next time you want to continue use “:source path/to/session_name”. This will load all the marks, tabs, folds etc. just as you left them.

That’s it

If you know all the above then you have become a fairly ok beginner. You should have no problem expanding your knowledge further. This was just the tip of the tip of the iceberg (yes, 2x). I deliberately left a lot of information to make it concise. You still got a long way to go.

What’s next?

Now you can easily learn vim without having much problem. Here are some suggestions on what to do next:

  • Vimtutor – It is just a basic tutorial program installed with vim. It will give you detailed knowledge of the basic commands.
  • Customization – The later sections of vimtutor teach you about “~/.vimrc”. Learn how to use it and customize vim according to your needs.
  • Plugins – Vim has a lot of community plugins which add features like text completion, highlighting, and much more.
  • Vimscript – This is basically just an advanced version of customising using “.vimrc”. With this you can write your own plugins. A great resource if Learn Vimscript the Hard Way.

Have some tips or suggestions? Share them in the comments below!

Best Sites for Programming Practice

Learning to code is one thing but getting better at it is another. Here are some great resources to hone your skills.
(more…)

Understanding recursion visually with fractals

Recursion is one of the more difficult type of concept that begginer computer programmers have to face. Simply making a fibonacci sequence doesn’t really guarantee complete understanding. Usually one has to get some experience before getting a good feel of the concept. But there’s an easier way. If you could see what happens under the hood you could get a better understanding more quickly. I found that fractals are perfect for this purpose beside being beautiful to look at.
Fractal is basically a reccuring pattern. If you zoom into an ideal fractal, you couldn’t tell how much we have zoomed in. One famous example of fractals, the mendelbrot set, is shown below.

Photo by Wolfgangbeyer

Setting up

Fractals can be drawn with ease if we have some turtle like object to draw objects. I chose to do it in C to make it a little challenging but you could use any other language you like. If you don’t understand or like the code just don’t bother and stick to the bigger details only. I used a very simple turtle structure with configurable angle and side variables. I also made some accompanying functions to serve as an abstraction layer to control turtle movement. All the code used in this post is available here in my github repo.

Our first fractal

Armed with the basic knowledge, we are ready to draw our first fractal, the Koch snowflake. It basically involves dividing a line into three( equal ) parts and then converting the middle one into a baseless triangle, repeat over and over again. In steps:

  1. Split the line into three parts.
  2. Convert middle part into an equilateral triangle without the base.
  3. Repeat the same procedure for all the new individual lines.

You don’t really need to do the procedure infinite times. We usually stop after doing it for a finite number of times. These number of times is called iterations. Here is the result of increasing number of iterations.

  1. One iteration only

koch1

At this time if you don’t get how this happened I suggest you reread the previous paragraph

2. Two iterations

This is where the fun starts. Now in the one iteration, we stop after making a single triangle but in this case we would further divide each of the four lines:

koch2But where does the base line go? If you are having this question then you must see some before I explain it

3. Three iterations

koch3

4. Four iterations

koch4

Now we can see the pattern. Instead of drawing the line first and then splitting it, the program first splits down the work down until it reaches the base case. Then it starts doing the work for all the smaller parts one by one. So the above design would be drawn from the left to the right as is without erasing any line, as we like to think about it. I know it still isn’t very obvious if you are new. One thing that could be done is to run the code in a debugger to actually see how the control flow works.

But this isn’t the Koch snowflake I was talking about. It is just a part of it. The snowflake is formed by first making an equilateral triangle and then applying the algorithm to each of it’s sides. The result is this:

kochcurve

In different colors:

kochcurve2

The Sierpinski Arrowhead

OK, that was great for our first fractal, but that’s not the only thing we could do! Another kind of fractal that we could make is the Sierpinski arrowhead. This one adds a little extra detail to the algorithm but the main idea is same as before. In steps:

  1. Draw a line( not really in case of program ). Think of the line as the base of an equilateral triangle.
  2. Move up the left side of the triangle upto it’s middle.
  3. Move parallel to the base until we meet the next side.
  4. Move down the side until we touch the base again.

Now lets get to drawing:

  1. One iteration

sier1Again read the above paragraph if you don’t really get it. Good. Now let’s move on further .

2. Two iterations

sier23. Three iterations

sier3fourth, fifth, …

6. Sixth iteration

sier6Wow! did you see that coming? We started with a simple rule and got an unexpected result. But if you look closely, You will see that all the smaller parts of the curve are the same as in iterations 2.

In different colors:

siercolor

This is the power of recursion. The basic idea is that you can apply the same algorithm to the larger thing and it’s individual parts with ease. Recursion is used frequently in computer like quick-sort, merge-sort, graph searching, towers of Hanoi… and making beautiful fractals. This is just the tip of the iceberg. You can find fractals everywhere in nature. Even in your body!( the blood vessels ). You can find more about them on the Internet if you like( there are also tutorials teaching how to make the Mandelbrot set mentioned in the start ).

Credits

I got the idea for this post from an exercise of the book Think Python. I picked the name “pica” for the turtle from the book Squeak: Learn Programming with Robots

Programming is Fun!

During my learning i have come up with some fun ideas and projects which helped in my learning. But most of them were left lying there in my old folders or lost . Then i saw people doing similar things but in a different way – they did it online . People just put up their work for everyone to see, learn and improve. This introduced me to The Learning Pyramid.

The Learning Pyramid The Learing Pyramid

All this partially motivated to make this move. So i plan to use this blog for  :

(more…)