Sunday, 26 June 2011

JPEG Compression Algorithm

Who knew, that the file format we daily use to store our images, is not just a file format, but also a state-of-the-art compression technique. It has been a common day-to-day experience for every multimedia enthusiast, that the same png image when saved in the jpeg format, results in smaller size, i.e. the image gets compressed. The degree of compression is adjusted, allowing a selectable trade-off between storage size and image quality. JPEG typically achieves 10:1 compression with little perceptible loss in image quality. The term "JPEG" is an acronym for the Joint Photographic Experts Group which created the standard, it is the most common format for storing and transmitting photographic images on the World Wide Web.

The image compression techniques is of 2 types :-
(1). Lossy
(2). Loss-less.

It is the Lossy technique that is more preferred, as it gives better compression ratios, for very little loss in clarity.
The compression is often achieved by leaving out non-important data parameters, and focussing only on important parameters, like :-

(1). color-space transformation matrix :-
The image is converted into a RBG colored matrix and also a gamma channel determing the brightness of the respective color. This kind of a color space conversion creates greater compression, without any perceptual change in image quality.The compression is more efficient because the brightness information, which is more important to the eventual perceptual quality of the image, is confined to a single channel. This more closely corresponds to the perception of color in the human visual system. The color transformation also improves compression by statistical de-correlation.

The various steps involved in the conversion of an image into jpeg format, is :-

(2). Down-sampling
(3). Block-Splitting
After Sub-sampling each block is split into 8*8 blocks.
(4). Discrete cosine transform
Next, each 8×8 block of each component (Y, Cb, Cr) is converted to a frequency-domain representation, using a normalised, two-dimensional type-II discrete cosine transform (DCT). Before computing the DCT of the 8×8 block, its values are shifted from a positive range to one centred around zero. For an 8-bit image, each entry in the original block falls in the range [0,255]. The mid-point of the range (in this case, the value 128) is subtracted from each entry to produce a data range that is centred around zero, so that the modified range is [ − 128,127]. This step reduces the dynamic range requirements in the DCT processing stage that follows. (Aside from the difference in dynamic range within the DCT stage, this step is mathematically equivalent to subtracting 1024 from the DC coefficient after performing the transform – which may be a better way to perform the operation on some architectures since it involves performing only one subtraction rather than 64 of them.)

(5). Quantisation
The human eye is good at seeing small differences in brightness over a relatively large area, but not so good at distinguishing the exact strength of a high frequency brightness variation. This allows one to greatly reduce the amount of information in the high frequency components. This is done by simply dividing each component in the frequency domain by a constant for that component, and then rounding to the nearest integer. This rounding operation is the only lossy operation in the whole process if the DCT computation is performed with sufficiently high precision. As a result of this, it is typically the case that many of the higher frequency components are rounded to zero, and many of the rest become small positive or negative numbers, which take many fewer bits to represent.

(6). Entropy encoding :-
It is basically a step where we apply Huffman coding/algorithm on the redundant information bit.

sighhhh.......... you would have never thought that these many steps take place, just while saving the image.

To reconstruct the image from these mathematical Data, an entirely opposite data transformation takes place, i.e. the encoded Data passes through the decoder, the inverse discrete fourier transform takes place, and so on and so-forth.

Technorati Tags: , ,

Thursday, 23 June 2011

Decoding GSOC

I applied for a position in this year's Google Summer of Code. Though frankly, prior to this year's GSOC, I had very little experience of Open source Software development, still I thought may be I should give it a shot. GSOC is a annual event that takes place from April to August, in which students code for various Open Source Organisations and Google pays them for it. If you complete your project, you get $5000, certificate and Google Goodies. The Theme says, flip bits not burgers. The whole event is based on getting more students familiar with Open Source.

I applied for Abiword this year, the very first organisation that appears in the list of participating organisations. AbiWord is a free word processing program similar to Microsoft® Word. It is suitable for a wide variety of word processing tasks. What makes Abiword special is its cross-platform characteristics. It runs on Windows, Linux and OSX too. Sadly I didn't get selected, but a Chinese friend of mine, 26 year old Phd student from Chinese Academy of Sciences, ChenXiajian got selected, who will complete the project, I applied for, Hyphenation Support in Abiword. Meanwhile, I made a lot of good friends in the Abiword Community. Even though I didn't get selected, but my friend Divyanshu Bandil, did get selected, in Ascend, where he will make a parser and compiler for ascend in python, due to its BSD licensing freedom. I also requested him to share his valuable experience, on how to get selected in GSOC. And even though he is very busy, trying to meet Deadlines, but he did spare some time, and shares his account.

By Divyanshu Bandil

After getting my proposal selected for GSoC 2011, my friend asked me to share the experience on his blog. So here are some tips for future aspirants.

1. Ignore the hoopla - The first impression you get about the program is that you have to be too skilful and a 'supercoder' for getting selected. You tend to think that the other guy who got selected is a magician in coding and carries all the algos at the tips of his hand. Though it is necessary to have some amount of experience in programming (hey! you already have that or why else would you be applying then?) and it helps if you have knowledge of basic data structures and some algorithms. But the fact is GSoC is more of doing a project and learning on the way. So believe me if you have the will to learn and work hard than nothing can stop you from getting selected.

2. Get your act together - I hope I have got you motivated enough to work forward. First of all ask some basic questions from yourself. What type of organisation/software you would like to work for? Which programming language you are comfortable to work with? Which is the the platform you would to interested to develop for?etc. You need not be too decisive but its good to have a general idea about the nature of the project you would be interested to work on.

3. Bond with the org - Based on the above answers choose two or maximum three organisations you would be interested to work for. Join their mailing lists and IRC. Chat with the members of the community. Discuss about the project idea you would like to work on. Try to contribute to the code by solving a bug or maybe adding a small feature. This improves your chances of getting selected by helping you to showcase your capability. The idea is to know the community and show that you will be able to work for them.

4. Writing the proposal - Once you have discussed about the project and are confident enough in its implemention, next step is to write your proposal. Most organisations provide a template for writing a proposal. However there are some things you should always mention in your proposal. First of all write a small abstract of the project. Provide some implementation details of the idea. Also provide a tentative schedule you will follow. Add some bits about your prior experience in programming. Its good to provide links to any project you have worked previously. Also submit your proposal early which leaves time enough to get it reviewed. Subsequently, you will be able to remove any loopholes in your implementation and make your proposal better.

After submitting your final proposal, just keep your fingers crossed!

Thanks a ton Divyanshu, for sharing your experience, with others. I hope it would be very useful to the future aspirants, in-case you have a question just fire away.

Technorati Tags: , , , , , ,

Wednesday, 22 June 2011

UnderStanding Systemd Part -II

This Post is from my understanding of the original post by leannart poettering on systemd :- 

At this point may be we should look back and analyse how the init scripts work, and have worked over the past so many generations, and may be draw a parallel with kde's style of booting up.
SystemV init ----> Upstart ----> Systemd

SystemV's Approach :-

Finding the dependencies between services and starting them according to a topological sort is inherently serial. You could start daemons that don’t depend on one another at the same time, but if two daemons both depend on dbus, dbus must start first. This creates inevitable bottlenecks which slow down the boot up.

Upstart's Approach :-

“All jobs waiting on a particular event are normally started at the same time when that event occurs”. This means that all services that depend on dbus are started immediately after dbus has finished starting. Although this certainly improves boot times by a fair margin (Ubuntu boots very quickly nowadays), the bottleneck is still there.

Systemd/launchd's Approach :-

What Happens is that for every daemon the resources gets allocated right at the start,(resources here implies, the sockets and the ports), while keeping the mapping from resources to the daemons, it is pretended that everything has been started, while loading all the daemons simultaneously. If a daemon requires a socket that belongs to a daemon that has not finished starting yet, the requests are buffered and ordered by the kernel and the requesting daemon blocks, waiting for an answer. Finally, when a daemon finishes starting up, it gets all the requests buffered by the kernel without any fuss, as if it had just received them.

I am not too sure, but from the look of things, it seems that kde's model of start-up is pretty much similar to either Upstart's or SystemV's approach, starting one process after another serially. Analysing my system boot charts, it looks more close to Upstart's approach. Here the order of execution is :-

KDE Display Manager ----> startkde script ----> (1). kdeinit (starts various services)  ---->  klauncher + kded + kcminit
                                                                              (2). ksmserver

Image Showing System Processes of my system with init script being high-lighted .
To achieve something close to systemd's model, the focus area should be the tie-up between kdeinit script and its subsequent sub-processes, and how we can parallise the process calls instead of the current serial inter-connections, between the processes. Apparently this approach should be highly feasible for an enviro like kde/gnome. But editing and implementing all these scripts is still going to be a Herculean task.

Friday, 17 June 2011

Understanding systemd part-I

This Post is from my understanding of the original post by leannart poettering on systemd :- 

From the look of things systemd just looks like a fancy init system.

May be at this point, I must get more familiar with init system, to understand more about systemd. init has PID 1, and so obviously it gets started first by the kernel, before all other processes. It is the parent process to all other child processes. Apart from this very important function, init script performs the central task of bringing up and maintaining user-space during boot. init script is much faster than its venerable predecessor sysvinit. For a faster system, 2 main things are required.
(1). Start less ---> Starting less means starting fewer services or deferring the starting of services until they are actually needed. For example a printing service may not be required immediately after having system on, whereas, there are some services where we know that they will be required sooner or later (syslog, D-Bus system bus, etc.). There would be no need to start many services, until directly called by the user, or its API is required by some-other service.
(2). Start More in parallel ---> Starting more in parallel means that if we have to run something, we should not serialise its start-up (as sysvinit does), but run it all at the same time, so that the available CPU and disk IO bandwidth is maxed out, and hence the overall start-up time minimised.

Lets see how programs start, with an example :-

--------------X--------------------------------------------------------- DBus service
---------------|------------------------------------------------- --X--- HAL service
--------------X---------------------------------------------------X---  syslog
               |                                                    |
               |                                                    |
Avahi(dependent on dbus and syslog)---------->livirtd (dependent on HAL and syslog) & also on Avahi

So for livirtd to start, it would have to wait for HAL and syslog to start, and additionally wait for Avahi to start too, hence livirtd can't start until all these services have started, and hence the incumbent delay.

Parallelizing Socket Services :-
In-order to get rid of these synchronising and paralleling delays, we have to understand what is required by one process from another. Usually that is an AF_UNIX socket in the file-system, but it could be AF_INET[6], too. For example, clients of D-Bus wait that /var/run/dbus/system_bus_socket can be connected to, clients of syslog wait for /dev/log, clients of CUPS wait for /var/run/cups/cups.sock and NFS mounts wait for /var/run/rpcbind.sock and the portmapper IP port, and so on. Now if we can make this socket appear before the entire daemon gets executed, and link it with the service, we can significantly reduce boot time and start more processes in parallel. We can create the listening sockets before we actually start the daemon, and then just pass the socket during exec() to it. That way, we can create all sockets for all daemons in one step in the init system, and then in a second step run all daemons at once. If a service needs another, and it is not fully started up, that's completely OK: what will happen is that the connection is queued in the providing service and the client will potentially block on that single request. But only that one client will block and only on that one request. Also, dependencies between services will no longer necessarily have to be configured to allow proper parallelized start-up: if we start all sockets at once and a service needs another it can be sure that it can connect to its socket.

## not clearly understood this part ##

Basically, the kernel socket buffers help us to maximise parallelization, and the ordering and synchronisation is done by the kernel, without any further management from userspace! And if all the sockets are available before the daemons actually start-up, dependency management also becomes redundant (or at least secondary): if a daemon needs another daemon, it will just connect to it. If the other daemon is already started, this will immediately succeed. If it isn't started but in the process of being started, the first daemon will not even have to wait for it, unless it issues a synchronous request. And even if the other daemon is not running at all, it can be auto-spawned. From the first daemon's perspective there is no difference, hence dependency management becomes mostly unnecessary or at least secondary, and all of this in optimal parallelization and optionally with on-demand loading. On top of this, this is also more robust, because the sockets stay available regardless whether the actual daemons might temporarily become unavailable (maybe due to crashing). In fact, you can easily write a daemon with this that can run, and exit (or crash), and run again and exit again (and so on), and all of that without the clients noticing or loosing any request.

Parallelizing Bus Services
Modern daemons on Linux tend to provide services via D-Bus instead of plain AF_UNIX sockets. Now, the question is, for those services, can we apply the same parallelizing boot logic as for traditional socket services? Yes, we can, D-Bus already has all the right hooks for it: using bus activation a service can be started the first time it is accessed. Bus activation also gives us the minimal per-request synchronisation we need for starting up the providers and the consumers of D-Bus services at the same time: if we want to start Avahi at the same time as CUPS (side note: CUPS uses Avahi to browse for mDNS/DNS-SD printers), then we can simply run them at the same time, and if CUPS is quicker than Avahi via the bus activation logic we can get D-Bus to queue the request until Avahi manages to establish its service name.

Apart from these services, filesystem jobs also have to be parallised, but I am not going to read much into it, as the main focus of my project, should lie in maintaining Bus and Socket services.
Technorati Tags: , , , ,

Thursday, 16 June 2011

UnderStanding KDE Launch Sequence

Its time to begin some serious work, I am already behind schedule, I will have to choose an area to work-on and then move-on to doing some instrumentation/benchmarking to see where the most time is spent, and where the efforts have to be focussed. I have decide to take a look at complete launch sequence right from KDM to the Plasma Shell, with Akonadi Application. My modest assumption, at this stage is that the bulk of the time for all the applications is spent on the transfer from one process to another, from startkde/kdeinit/kded etc. and their tie-up together, maybe we could unify this a bit more. Maybe also add some timing instrumentation/debug output, to see where time is spent.

Having a more detailed look on the entire start-up sequence :-

KDE Display Manager 
   startkde script (executes 2 main functions) ----> 
(1). kdeinit (starts various services)
   dcopserver + klauncher + kded + kcminit
(2). ksmserver

Process 1:-
The user gets authenticated at start-up by entering the user-name and password at KDE Display Manager (KDM). KDM then executes startkde script, this scripts performs two vital functions, and calls the following scripts :-

LD_BIND_NOW=true kdeinit +kcminit +knotify
Starts the kdeinit master process, which in-turn starts all other KDE processes. The arguments behind kdeinit are the names of additional services to be started. The + indicates that kdeinit needs to wait till the service has finished.
                ## Haven't clearly understood the script ##

kwrapper ksmserver $KDEWM 

Starts the kde's session manager. On startup the session manager starts auto-start applications and it restores applications from the previous session. The session manager determines the lifetime of the session. When this process exits, the user is logged out.

Process 2:-
kdeinit master process begins after the startkde script gets executed. kdeinit can start normal binary program files as well as kdeinit loadable modules (KLMs). KLMs work just like binary program files but can be started more efficiently.

for example :-
> ps aux
waba     23184  0.2  2.1 23428 11124 ?       S    21:41   0:00 kdeinit: Running...
waba     23187  0.1  2.1 23200 11124 ?       S    21:41   0:00 kdeinit: dcopserver --nosid
waba     23189  0.2  2.4 25136 12496 ?       S    21:41   0:00 kdeinit: klauncher
waba     23192  0.7  2.8 25596 14772 ?       S    21:41   0:00 kdeinit: kded
waba     23203  0.8  3.4 31516 17892 ?       S    21:41   0:00 kdeinit: knotify

kdeinit in the first line: Running... indicates the master kdeinit process. The other processes listed are programs started as KLMs.

Process 3:-
BackGround/Subprocesses :-

1. dcopserver 
# confusion? - is it any different from the dbus daemon that starts on system booting ??? #
 The doci says "dcopserver is a deamon which provides inter-process communication (DCOP) facilities to all KDE applications." Which is pretty similar to dbus-daemon, which provides inter-process communication (IPC) facilities to all KDE applications as well as several other system components, such as HAL, network manager, power manager and various non-KDE desktop applications.

2. klauncher
klauncher is a deamon which is responsible for service activation within KDE. It operates in close connection with the kdeinit master process to start new processes. KDE applications communicate with klauncher over dcop in order to start new applications or services.

3. kded
kded is a generic KDE daemon. It has the ability to load various service modules and run these in the background. The Service Manager in the Control Center can be used to monitor the status of the service modules and to disable certain services.

4. kcminit
kcminit executes initialisation services during startup. Initialisation services are specified in the .desktop files of applications or services via the X-KDE-Init line. Initialisation services are typically used for initialisating hardware based on user specified settings. kcminit --list can be used to show all initialisation services and kcminit can be used to execute a single service explicity. This can be useful when investigating start-up problems.
## More Understanding required ##

Process 4:-
ksmserver is KDE's session manager. On startup the session manager starts auto-start applications and it restores applications from the previous session.

Whether to auto-start an application can be conditional upon some configuration entry determined by the X-KDE-autostart-condition entry in the .desktop file. The KDE session manager also restores one of the previous sessions. A session contains of a collection of applications as well as application-specific information that reflects the state of the applications at the time the session was saved. Sessions are stored in the ksmserverrc configuration file and contains references to application-specific state information. The application specific state infomation is saved in $KDEHOME/share/config/session.

For example, if ksmserverrc contains:


Then the application specific state information for kwin and konsole can be found in





The state information of kwin contains the location of the application windows of all the other applications in the session.

At this point the order of execution with respect to ksmserver is not very well understood by me, like what happens immediately after the startkde script, if the ksmserver script gets executed alongside, kdeinit, then the values returned by ksmserver would have to communicate in some-way with the klauncher and kded.
Technorati Tags: , , , ,