Laptop charger disconnected alarm

Now that my laptop’s battery is not co-operating and giving me a battery backup of at max 10 minutes, I need to connect it to AC adapter all the time. Still sometimes when my adapter cord gets disconnected, my laptop shuts itself off without any warning 😦

I believe it’s the same problem with most of the people and how much it hurts when your unsaved data is lost 😛

Finally when my laptop died for 5th time today, I decided to make a small script to get rid if this problem.

#!/bin/bash

###########SETTINGS###################

SLEEP_INTERVAL=2
BEEP_HOW_MANY_TIMES=2

########DONOT TOUCH AFTER THIS########

while [ "" == "" ]; do
	STATE=`acpi -a | grep on-line`
	if [ "$STATE" == "" ]
	then
		for i in {1 .. $BEEP_HOW_MANY_TIMES}
		do
			echo -en "\007"
			sleep 0.25
		done
	fi
	sleep $SLEEP_INTERVAL
done

Once the script was running, I attached it with my startup script.

One of the easiest way is to press Alt + F2 and type gnome-session-properties. After that things are pretty much easy.
This way you can have your own AC Adapter monitoring service ready within 5 minutes.

Best thing is it doesn’t even require any Super User controls. 🙂

Enjoy friends 🙂

P.S. I am still looking for interrupt event when charger is disconnected to get rid of while loop. Please do tell me if it’s possible. 🙂

Median of two sorted arrays.

Problem statement: There are 2 sorted arrays A and B of size n each. What is the fastest way to find the median of the elements of both the array.

Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half.
The median of a finite list of numbers can be found by sprting and picking the middle one.

Median of N elements in an array of elements [0..N-1] is

Solution 1: O(n)
Simple and slow, Merge the array and apply above formula.

Solution 2: O(log (n))
By comparing the medians of 2 array.

#include<stdio.h>
#define MAX(a , b) (a>b)?a:b
#define MIN(a , b) (a<b)?a:b
int median(int [], int); /* to get median of a sorted array */
int get_median(int array_1[], int array_2[], int n)
{
	int m1; /* For median of array_1 */
	int m2; /* For median of array_2 */
	if (n <= 0)
	return -1;
	if (n == 1)
	return (array_1[0] + array_2[0])/2;
	if (n == 2)
	return (MAX(array_1[0], array_2[0]) + MIN(array_1[1], array_2[1])) / 2;
	m1 = median(array_1, n); /* get the median of the first array */
	m2 = median(array_2, n); /* get the median of the second array */
	/* If medians are equal then return either m1 or m2 */
	if (m1 == m2)
	return m1;
	/* if m1 < m2 then median must exist in array_1[m1....] and array_2[....m2] */
	if (m1 < m2)
	{
		if (n % 2 == 0)
			return get_median(array_1 + n/2 - 1, array_2, n - n/2 +1);
		else
			return get_median(array_1 + n/2, array_2, n - n/2);
	}
	/* if m1 > m2 then median must exist in array_1[....m1] and array_2[m2...] */
	else
	{
		if (n % 2 == 0)
			return get_median(array_2 + n/2 - 1, array_1, n - n/2 + 1);
		else
			return get_median(array_2 + n/2, array_1, n - n/2);
	}
}

int median(int arr[], int n)
{
	if (n%2 == 0)
		return (arr[n/2] + arr[n/2-1])/2;
	else
		return arr[n/2];
}

int main()
{
	int array_1[] = {1, 2, 3, 7, 8, 10, 12};
	int array_2[] = {4, 7, 8, 10, 15, 30, 32};
	int n1 = sizeof(array_1)/sizeof(array_1[0]);
	printf("Median is %d", get_median(array_1, array_2, n1));
	return 0;
}

P.S. You can also use binary search approach.
P.P.S. Your task becomes much much easier if all the elements of Array 1 is smaller than Array 2 😉

Please suggest more optimized approach if possible. 🙂

Immediate lower/higher number of same digits problem

As I was working on my research project, I came across an interesting problem which asks

Given a number xyz, find the immediate higher and lower number which has the exact same set of digits as the original numbers.

And I remember I’ve solved a similar question in Google Codejam practice sessions.

For example : N = 134578362714
Then the answer is 134578362741 (Higher) and 134578362471

Most of us will be trying for brute force or next permutation approach since the time wont be much but if I say 10^100 < number < 10^1000 😛

This is pretty simple as you have to just play with the digits and their positions. Take 3-4 examples and you will get the answer on your own.

Solution for immediate higher: (Number = 1345783627198642)

1. X = Starting from MSB move towards LSB and find the last digit whose next digit is greater than itself.
   Here it’s 1 :  1345783627“1″98642.
   Alternatively you can start with LSB and reverse the process.
2. Y = Find smallest digit greater than X by moving towards LSB.
   Here it’s 2 : 134578362719864“2”.
3. Move Y left to X.
   N = 1345783627219864.
   
4. Sort the numbers after Y.
   N = 1345783627214689.

And that’s your solution 🙂
Moving on immediate lower, just modify the above algorithm.

P.S. Link to the codejam problem : https://code.google.com/codejam/contest/dashboard?c=186264#s=p1&a=1

Fun with qsort() in C

Using qsort() during competitive programming is fun ( as well as time saving 😉 ). But when someone tells you to modify compare function of qsort in such a way that you are able to generate different (but meaningful) results from qsort(), what will you do?

Let the list be : [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]

Fun 1 : Convert list to [ 9 , 7 , 5 , 3 , 1 , 0 , 2 , 4 , 6 , 8  ]
Fun 2 : Convert list to [ 0 , 2 , 4 , 6 , 8 , 1 , 3 , 5 , 7 , 9  ]

#include <stdio.h>
#include <stdlib.h>

int comp ( const void *p, const void *q )
{
        //Insert code here
}
int main()
{
        int arr[] =  { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 };
        int i;
        int size = sizeof ( arr ) / sizeof ( arr[0] );
        qsort ( ( void* ) arr, size, sizeof ( arr[0] ), comp );

        printf ( "Output array is\n" );
        for ( i = 0 ; i < size ; i++ )
                printf ( "%d ", arr[i] );
        printf ( "\n" );
        return 0;
}

int comp(const void* p1, const void* p2);
Return value meaning
<0 The element pointed by p1 goes before the element pointed by p2
0 The element pointed by p1 is equivalent to the element pointed by p2
>0 The element pointed by p1 goes after the element pointed by p2

Fun 1 can be easily be solved by this code

int comp ( const void *p, const void *q )
{
        int l = * ( const int * ) p;
        int r = * ( const int * ) q;
        if ( ( l & 1 ) && ( r & 1 ) )
                return ( r - l );
        if ( ! ( l & 1 ) && ! ( r & 1 ) )
                return ( l - r );
        if ( ! ( l & 1 ) )
                return 1;
        return -1;
}

Explaination to Fun 1 :
1) If both (l and r) are odd, put the greater of two first.
2) If both (l and r) are even, put the smaller of two first.
3) If one of them is even and other is odd, put the odd number first.

Solution to Fun 2 : 

int comp ( const void *p, const void *q )
{
        int l = * ( const int * ) p;
        int r = * ( const int * ) q;
        if ( ( l & 1 ) && ( r & 1 ) )
                return ( l - r );
        if ( ! ( l & 1 ) && ! ( r & 1 ) )
                return ( l - r );
        if ( ! ( l & 1 ) )
                return -1;
        return 1;
}

Please come out with some more challenges and such ‘fun with callback functions’.
P.S. This question was asked to me by my Project Guide at IIIT Hyderabad while explaining uses of callback functions. 🙂

Connected Components problem

Connected components (Or sets) problem is a classic problem in graph theory also used in digital image processing which can be defined for a binary image as.

Given a 2–d matrix , which has only 1’s and 0’s in it. Find the total number of connected sets in that matrix.

Connected set can be defined as group of cell(s) which has 1 mentioned on it and has at least one other cell in that set with which they share the neighbor relationship. A cell with 1 in it and no surrounding neighbor having 1 in it can be considered as a set with one cell in it. Neighbors can be defined as all the cells adjacent to the given cell in 8 possible directions ( i.e N , W , E , S , NE , NW , SE , SW direction ). A cell is not a neighbor of itself.

Example

1 0 0 1 1
0 0 1 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0

Hence the number of connected sets are 3.

The most basic solution is DFS or BFS and it will give quick results for image size < 500 x 500 px. But these 2 algorithms will throw out of memory or stack overflow errors for large images ( say 2000 x 2000).

So basically there are 3 approaches in my mind.

Solution 1 : Detect edge and apply DFS / BFS.

You can simply detect the edges of BLOBs and apply DFS.
This solution can be very effective if the connected sets are less in number but greater in size. Don’t expect it to work with large number of sets.
Solution 2: 3 scan algorithm

Initialization step : make a boundary of 0s across the image like this.


0 0 0 0 0 0 0
0 1 0 0 1 1 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

Scan 1 :

MAX = 2;
for ( i in 1 .. n )
{
	for ( j in 1 .. n )
	{
		if ( image [i][j] == 1 )
		{
			if ( image [i][j-1] != 0 )
			{
				image [i][j] = image [i][j-1];
			}
			else if ( image [i-1][j] != 0 )
			{
				image [i][j] = image [i-1][j];
			}
			else if ( image [i-1][j-1] != 0 )
			{
				image [i][j] = image [i-1][j-1];
			}
			else
			{
				image [i][j] = MAX++;
			}
		}
	}
}

It will convert the above matrix to


0 0 0 0 0 0 0
0 1 0 0 2 2 0
0 0 0 3 0 0 0
0 0 0 0 0 0 0
0 4 4 4 4 4 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

Scan 2 :
Start from the bottom check if each neighbor has the same number as the left most neighbor as well as the same number as the neighbor in the row below it.

for ( i in n .. 1 )
{
	for ( j in 1 .. n )
	{
		if ( image [i][j] != 0 )
		{
			if ( image [i][j-1] != 0 && image [i][j-1] != image [i][j] )
			{
				image [i][j] = image [i][j-1];
			}
			else if ( image [i+1][j-1] != 0 && image [i+1][j-1] != image [i][j] )
			{
				image [i][j] = image [i+1][j-1];
			}
			else if ( image [i+1][j] != 0 && image [i+1][j] != image [i][j] )
			{
				image [i][j] = image [i+1][j];
			}
			else if ( image [i+1][j+1] != 0 && image [i+1][j+1] != image [i][j] )
			{
				image [i][j] = image [i+1][j+1];
			}
		}
	}
}

Outputs

0 0 0 0 0 0 0
0 1 0 0 3 3 0
0 0 0 3 0 0 0
0 0 0 0 0 0 0
0 4 4 4 4 4 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

Step 3 :

Just count the number of non 0 entries in the matrix.

Solution 3 : Apply minimizing image canvas or max flow thoerm.
Applying these algorithms will help in Digital Image Processing and quick results but they can miss many small points. This solution is used only when the area of connected set is huge.

P.S. This might not be the perfect solution to this problem but these are the best one I can think of. More solutions/optimizations are welcomed 🙂

Address of different segments of a process (The C Way)

After learning about basics of Micro Processors and x86 architecture, I started taking interest in the program segments (Data, code, stack etc.) and I was amazed to see, how assembly programming can be simplified by simply segmenting the program.

So I started experimenting with basic ASM programs on 8086 and Pentium series. But in new era I think C is the most widely used language for programming and definitely generates a code or binary file, which follows the same rule of segmenting.

AIM: Get the [Starting] address of various segments in C. We will be working on Code, Stack, BSS and Data segments.

Prerequisites :

• Code segment: Memory area containing the actual instructions to the micro processor – the actual executable program.
• Data Segment: A data segment is a portion of virtual address space of a program, which contains the global variables that are initialized by the programmer. The size of this segment is determined by the values placed there by the programmer before the program was compiled or assembled, and does not change at run-time.
• BSS: The BSS segment, also known as uninitialized data, starts at the end of the data segment and contains all global variables and static variables that are initialized to zero or do not have explicit initialization in source code.
• Stack Segment: The area contains the program stack, a LIFO structure, typically located in the higher parts of memory. A “stack pointer” register tracks the top of the stack.

More information : http://en.wikipedia.org/wiki/Data_segment

Approach: 

1. Code segment: let a function say hello() and an address pointer addr.
   and addr = &hello;
   Thus the address of hello() function will give us the idea of code segment. Keep the function on top of the code will give us the address of code segment as close to the starting address as possible. Please note: it is impossible to get the actual starting address of code segment without going into kernel or system calls.
2. Data segment: A fully initialized global variable will give us the address of data segment. lets recall our 1st assembly program and the pneumonic  “dw var_int 100h” , hence var_int will be saved in data segment.
3. Stack Segment: All the local variables are initialized in stack segment. Now if you have a question why is it so? The answer is simple, local variables are needed only for sometime, more precisely, they are used as temporary variables.
   Next question arrives, why cant we make use of a simple function call and grab the stack pointer?
   Ans: Well do you think it is simple enough to grab stack pointer? We are trying to get the addresses with minimal effort. Hence the address of 1st local variable will be our answer, closest to the base pointer.
4. BSS: Block started by Symbols or BSS is actually part of data segment itself but in new micro processors, Data segment is divided into further 3 segments (Data + BSS + heap) and as wiki said, “The BSS segment, also known as uninitialized data” we can have its address by a static uninitialized global variable.

Solution: 

#include

int temp_data = 100;
static int temp_bss;

void print_addr ( void )
{
        int local_var = 100;
        int *code_segment_address = ( int* ) &print_addr;
        int *data_segment_address = &temp_data;
        int *bss_address = &temp_bss;
        int *stack_segment_address = &local_var;

        printf ( "\nAddress of various segments:" );
        printf ( "\n\tCode Segment : %p" , code_segment_address );
        printf ( "\n\tData Segment : %p" , data_segment_address );
        printf ( "\n\tBSS : %p" , bss_address );
        printf ( "\n\tStack Segment : %p\n" , stack_segment_address );

}

int main ( )
{
        print_addr ();
        return 0;
}

Output: 
Address of various segments:
Code Segment : 0x4004f4
Data Segment : 0x601020
BSS : 0x601038
Stack Segment : 0x7fffd784debc

And hence is the final solution, but yeah, it is not the exact starting addresses since there are various other functions or variables which are initialized by libc before our main function.

How to run a process for specific time (PHP way proc_open)

Hey all,
Lets summarize, we are trying to run an application from PHP script with complete control over stdin , stdout and stderr buffers. At this moment of time, we need to need to make use of PHP’s built in function : proc_open()
P.S. For advanced user, please directly jump to the tutorial.

BACKGROUND

It is well known that no single language can perform all the tasks required by a developer. Same way if there are some positive points of a certain language, there also exists negative points too. And to overcome these drawbacks, we prefer to make use of multiple programming languages.

One such example is PHP (Widely used in web-development) PHP no doubt is very good in handling data from website but when it comes to processing or manipulation of HUGE amount of data, PHP literally sucks 1000 times.

Lets take a small experiment of Square Matrix Multiplication of dimension 1000 x 1000.
Hence our results were.

aman@CloudNIT:~/test/matrix$ time ./a.out < out.txt > res.txt

real 0m6.796s
user 0m6.400s
sys 0m0.076s
aman@CloudNIT:~/test/matrix$ time php pmul.php > res2.txt

real 5m7.462s
user 4m36.877s
sys 0m2.692s

Shocking isn’t it??
Now what if I start the CPP application from PHP using system ()?

It’s exactly what you think, I am simply distributing my processing load from PHP to CPP application.

Anyways we got deviated from our main aim. So system () is not the only option to deal with this situation. Some times you need to run a process and take care of all 3 standard stream (stdin , stdout and stderr).

TUTORIAL

Starting with very basic PHP script which will run an application with small input and output.

<?php $description = array ( 	0 =--> array("pipe", "r"),  // stdin
	1 => array("pipe", "w"),  // stdout
	2 => array("pipe", "w")   // stderr
);

/*
 * This a.out application accepts a number
 * and print's its square.
 */

$application = "./a.out";
$pipes = array();

$proc = proc_open ( $application , $description , $pipes );

if (is_resource ( $proc ))
{
	fwrite ( $pipes [0] , "20" ); //Writing 20 in stdin buffer
	fclose ( $pipes [0] ); //Closing stdout buffer
	echo "Stdout : " . stream_get_contents ( $pipes [1] ); //Reading stdout buffer
	fclose ( $pipes [1] ); //Closing stdout buffer
	fclose ( $pipes [2] ); //Closing stderr buffer

	$return_value = proc_close($proc);
	echo "\ncommand returned $return_value\n";
}
?>

Output of above program is

Stdout : 400
command returned 0

Coming back to our main Aim, “Run a process for specific time”. It is very simple to run a process for certain amount of time.

1. Start timer
2. Open Process
3. Read/Write I/O Handler (stdio , stdout etc).
4. Monitor the timer.
5. Come out of the loop once Time Limit Exceeded.

Summing up all the above points, here is a small PHP function which will perform my task.

function shell_exec_p($cmd , $tim)
{
	$end = time() + $tim;
	$description = array ( 	0 => array("pipe", "r"),  // stdin
		1 => array("pipe", "w"),  // stdout
		2 => array("pipe", "w")   // stderr
	);
	$pipes = array();

	$proc = proc_open ( $cmd , $description , $pipes );
	stream_set_blocking ($proc , 0);
	$output = "";
	while (!feof($pipes [1]) && (time() < $end)) {
		$output .= fread($pipes [1] , 2096);
	}
	return $output;
}

That was pretty simple 🙂

Experiment : Fast root square inverse

Root square inverse (x^−½) simply means x = 1/sqrt(x); Right???
If you think so then I’ll ask you to think once again can there be any another approach to find x^−½ of x (through programming).

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;              // evil floating point bit level hacking
        i  = 0x5f3759df - ( i >> 1 );      // what the fuck?
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}

Believe me or not but this function works with an accuracy of 99.825% (According to wiki). Which can be even further increased by uncommenting the “2nd iteration” line.

Motivation:

The inverse square root of a floating point number is used in calculating a normalized vector. Since a 3D graphics program uses these normalized vectors to determine lighting and reflection, millions of these calculations must be done per second. Before the creation of specialized hardware to handle transform and lighting, software computations could be slow. Specifically, when the code was developed in the early 1990s, most floating point processing power lagged behind the speed of integer processing.

The above code is used in many games to calculate reflection of lightening on surface quickly. Quake 3 uses the same code for accelerating the lightening and graphics quality (Use of Fast square root inverse in Quake 3)

Experiment:
To calculate root square inverse of 10⁸ random floating point numbers by :

1. x = 1/sqrt (x);
2. x = Q_rsqrt (x);

Results: 

1. When  I used trivial method ” x = 1/sqrt (x); ”
   Time taken by the function to calculate 10⁸ floating point numbers was:
2. After using the same dataset on Fast Root Inverse function, The time was reduced dramatically by means of 5 times.
   

Conclusion:
Fast root square inverse is used in lightening programming of games (1st used in quake 3 arena by ID software ).
For more details on Fast square root inverse and 0x5f3759df ( the magic number ) Please visit wiki page : http://en.wikipedia.org/wiki/Fast_inverse_square_root

Make bridge network on linux: Simplest and quickest

After doing hell lot of research on computer networks , especially on bridge networks I started looking at behavior of brctl command, I came to a conclusion, the quickest and easiest way to make a bridge network is to edit interfaces file.

Note of advice: I hope you know what you are doing, If you want to experiment bridging on your machine, please read the pros and cons of using or activating bridge in linux.

Lets start.
Open interfaces file.

sudo vim /etc/network/interfaces

Just add the following lines in your interface file

auto lo
iface lo inet loopback

auto eth0
iface eth0 inet manual

auto br0
iface br0 inet static
        address 192.168.0.10
        network 192.168.0.0
        netmask 255.255.255.0
        broadcast 192.168.0.255
        gateway 192.168.0.1
        bridge_ports eth0
        bridge_stp off
        bridge_fd 0
        bridge_maxwait 0

or to use DHCP

auto lo
iface lo inet loopback

auto eth0
iface eth0 inet manual

auto br0
iface br0 inet dhcp
        bridge_ports eth0
        bridge_stp off
        bridge_fd 0
        bridge_maxwait 0

Now last step, restart networking

sudo /etc/init.d/networking restart

You can now check br0 network from ip addr or ifconfig command.

Compiler Optimization: GCC and -Ox Flags (Experiment)

Introduction

The GNU Compiler Collection (GCC) is one of the most popular compilers available today. Over the last 15-20 years, GCC has evolved from a relatively modest C compiler to a sophisticated system that supports many languages (C, C++, Java, Objective C, Objective C++, Ada, Fortran 95) and about 30 different architectures.

When GCC optimizes your application, the original program goes through an assortment of optimizing transformations before generating the final binary. Since optimizations are usually expensive, the optimizer is organized in levels of aggressiveness. You can select between -O1for quick and light transformations to -O3 for heavy duty optimizations. In theory, the higher the optimization level, the faster your application will run. Unfortunately, things are not always so simple. Generating perfect target code is almost an impossibility for a multitude of factors: Compiler optimizations usually interfere with each other in almost infinite ways, heuristics and cost models may be wrong, the code may be obscure enough to confuse the optimizers, etc.

How does optimization flag works in GCC

gcc -O2 [other -f or -m flags] -o file file.c

For a complete listing of all the available options and their meaning, refer to the GCC documentation.

Optimization Levels and their Advantages

Flag	Description
-O0	Barely any transformations are done to the code, just code generation. At this level, the target code can be debugged with no loss of information.
-O1	Some transformations that preserve execution ordering. Debuggability of the generated code is hardly affected. User variables should not disappear and function inlining is not done.
-O2	More aggressive transformations that may affect execution ordering and usually provide faster code. Debuggability may be somewhat compromised by disappearing user variables and function bodies.
-O3	Very aggressive transformations that may or may not provide better code. Some semantics may be modified (particularly floating point). Order of execution completely distorted. Debuggability is seriously compromised.
-Os	Optimize for size. This option enables transformations that reduce the size of the generated code. Ironically, this may sometimes improve application performance because there simply is less code to execute. This may lead to reduced memory footprints which may produce fewer page faults.
-O4	There is no -O4. Anything above -O3 is treated as -O3.

Experiment

I wrote a C program to solve http://projecteuler.net/problem=67 and tested its binary with different Optimization levels (O0, Os and O3)

Results

PS ~DUMMY PATH~> Measure-Command { .\O3.exe }
Compilation time : 627 Micro Seconds
Ticks : 78280
TotalMilliseconds : 7.828

PS ~DUMMY PATH~> Measure-Command { .\Os.exe }
Compilation time : 597 Micro Seconds
Ticks : 76332
TotalMilliseconds : 7.6332

PS ~DUMMY PATH~> Measure-Command { .\O0.exe }
Compilation time : 260 Micro Seconds
Ticks : 173434
TotalMilliseconds : 17.3434

Conclusion

Compilation time in -O3 and -Os flag takes ~3 times more than  -O0 flag but there is no harm in adding any of the optimization flag as our main target is to make the code run faster. 🙂

[Source: http://www.redhat.com/magazine/011sep05/features/gcc/]