Wednesday, December 19, 2012

Weird reversal of Stack.

A very commonly asked question during interviews is to write a recursive solution to reverse a stack. A lot of discussion is out there with different kind of implementation varying from O(n*n) to O(n).My interest in this question is due to something else.
While I was getting ready for office my room-mate was having a telephonic interview with one of the IT companies in Bangalore. He was asked this question (Which is very straight forward if no constraints are given),  with a constraint that he is supposed to use recursion and he is allowed to use only constant memory in each recursion. Well , when I saw this question I was pretty convinced that it can be done in O(n) given I use few bytes in each recursion and I decided to hack in my beloved "C++" to help me through it.
The approach that is explained here is a little non-trivial but not too difficult to understand. Now try this code :-

void reverse(stack<int> &s,int *prevdata=0) {
     int data,*t;
     if(s.empty())
          return;
     data=s.top();
     s.pop();
     size++;
     reverse(s,&data);
    if(s.size() <= (size-1)/2) {
          t=(int*((char*)(&data)-((((char*)&data)-((char*)prevdata))*((size-1)-s.size()*2)));
          s.push(*t);
          *t=data;
    } else {
         s.push(data);
    }
}

To understand "why this code is working" you will need to know how bits synchronously dance around your computer's hardware to make your code run.In case you don't get it read this blog entry.
Now,  if you can manage to see the stack and how local variables are placed in there you should be able to observe that the way it is placed each time variable data is getting the same relative location in its own function's memory space. Given the same function is being called and size of memory assigned to it is same each time, it is possible to know where all variables are placed.
From above observation it can be concluded that distance between a variable of function with itself in next recursive call remains the same throughout.
If memory can be visualized as horizontal straight line as follows :-

_| _ _ X _ _ _| _ _ X _ _ _| _ _ X _ _ _| _ _ X _ _ _| _ _ X _ _ _| 

Where, X is the variable (data) and function (reverse) get the memory between ' | '.Distance between two X's is same throughout.
Now when this information is available, distance between variable in each recursion can be calculated if the address of variable in previous recursion (prevdata) is available. As size of stack is known we know that (n-1)th element of stack should be replaced with 0th element, (n-2)th element with 1st element and so on. Upto half size of stack we can just take the data which is at the same distance from middle element and place it on the stack and replace the content at other point with current element of the stack. When recursion goes below half, it will have information available in variable data in reverse order, which we just need to place on the stack.

Hope you like this blog entry.Views and modifications are welcome.

Sunday, August 19, 2012

Scope of variables in C. An illusion ?


The following article is an experiment with C and some of the concepts of COR (computer organization).Well, not everything that is taught, comes out to be exactly same in implementation.
Following experiment is done on

OS Fedora x86_64
Processor Intel(R) Core(TM)i5-2540M CPU
System type 64 bit
gcc 4.7.0

Try the following code  [ 1 ]

struct Coord {
                        long x,y;
};
void canItModify(){
                        long *x;
                        x=(long*)((char*)&x+40);
                        (*x)=0;
                        x++;
                        (*x)=0;
}
int main(int argc,char *argv[]) {
                        struct Coord pt;
                        scanf("%d%d",&pt.x,&pt.y);
                        canItModify();
                        printf("%d %d\n",pt.x,pt.y);
                        return 0;
}

Compile and run it.
Well, you will be surprised by the fact that no matter whatever you give as an input printf will always print 0 0.

Now try this  [ 2 ]

struct Coord {
                        long x,y;
};
void canItModify(){
                        long *x;
                        x=(long*)((char*)&x+72);
                        (*x)=0;
                        x++;
                        (*x)=0;
}
void womanIntheMiddle() {
                        int ar[3];
                        scanf("%d%d%d",ar,ar+1,ar+2);
                        canItModify();
}
int main(int argc,char *argv[]) {
                        struct Coord pt;
                        scanf("%d%d",&pt.x,&pt.y);
                        womanIntheMiddle()
                        printf("%d %d\n",pt.x,pt.y);
                        return 0;
}

compile and run.
Now again you will see the same result. Even a "womanIntheMiddle" can't stop "canItModify" to meet variable pt in main.

Now it is obvious that core of the above two program is "canItModify()".And it is instructions in this function that is altering the pt variable of the main function.Well if a variable, locally scoped to some function, can be modified by other function anywhere in the code that doesn't have direct access to that variable then what about the scope of the variable.In words of Dennis M. Ritchie, "If a variable is locally scoped to a function, no other function can have direct access to it".It is worth noticing that it is said that the function can’t have direct access to a variable locally scoped to another function i.e; a function might have an indirect access to local variable of another function.Further in this article I am going to explain how an external function can access variables of other functions without taking them as parameter.

Understanding of C and pointer arithmetic is a must for further reading. If you are weak in any one of these first read those.


WARNING :- Method explained in this article is not a standard programming practice so do not get into habit of using it. This is just for fun and understanding.

Lets Swim through the architecture and investigate.

How Local variables are allocated space ?

There are 4 memory sections for a program when loaded in memory to execute.
  1. Code Segment    :- Non-modifiable section that contains code.
  2. Data Segment     :- Contains global and static variable
  3. Heap                  :- Dynamic memory is allocated from here.
  4. Stack                 :- function call and spaces for local variable.
We won’t be discussing CS, DS and heap but stack memory. Local variables of all functions are there on the stack and each of them use variable locally scoped to those functions.So how can a function be tricked to make it think that it's variable is in another function and access it? Answer to this question is that a function can't be tricked to do this, as relative addresses to local variables are hard-coded in the machine instruction after compilation, which is in the code segment. But there is a way-out.
Here is what happen when a function call is made (Numb3rs are corresponding to 64 bit machine, It will vary for 32 bit and so on)
  1. Return address of Next instruction is pushed onto the stack (8 byte)
  2. stack pointer decremented (8 byte).
  3. Base pointer of previous function is pushed on the stack (8 byte).
  4. Memory for local variable is allocated (16*n , n is a +ve integer, it depends on compiler implementation, as per above specification it is 16*n).
  5. stack pointer is decremented (16*n).
Now the question is,"How much exact memory is allocated and where all variables reside?".
Answer to this question is that memory sufficient enough for all the local variables such that memory look-up is efficient. These variables reside in the memory space, allocating spaces for the variable declared first i.e; if an int is declared first, it will be given space first then other variables, in the order of their declaration from the bottom of actual space allocated for local variable, of the current function.

Note :- If a function is taking some arguments, first 6 arguments are assigned to registers rdi,rsi,rdx,rcx,r8,r9 respectively, all other arguments are stored in stack after all local variables are assigned their space on local stack space. Read from here.

Here is stack memory structure of 2nd example as given above (Each row  in Stack segment is 8 byte long and ___ is blank space, sfp (8 byte)=> base pointer of previous function, ret(8 byte) => return address)

fig :- stack growing from higher to lower and heap from lower to higher

How variables are placed in local frame ?
A 64 bit machine can read 8 byte in one memory cycle and this is from a location that is multiple of 8. Compiler tries to place the variables in such a way so that it takes minimum memory cycle to read those variables from memory.

eg :- for a function "dummyfunction",
void dummyfunction() {
                int i;     //int takes 4 byte
                long j;    //long takes 8 byte
                int k;     //int takes 4 byte
                .....
                .....
}
Ideally it should take 16B and it is also multiple of 16 but it will take 32B.

Explanation

Suppose base address from where variables are placed is 0.
  1. First space for an int will be allocated.As int takes 4 byte it will be from 4 to 0.
  2. Now space for j (long) will be allocated.As it takes 8 byte, it can be assigned space from 12 to 4 but this assignment has a problem that it will take 2 memory cycle to read one long variable (16-8 and 8-0) as memory read is not from in between. If it is assigned space from 16-8, it will take just one memory cycle to read this variable. Therefore j is assigned space from 16-8.
  3. Next variable k can be assigned @ 8-4 but compiler is not that intelligent for making such arrangement you will have to arrange the variable in order. Compiler will place k from 20-16.
As requirement is 20 it will assign 32 byte space for local variable of given function.

Note :- Space allocated for local variable of each function has a gap of 16 byte (sizeof(ret)+sizeof(sfp)) from the local variable space of previous function.

Calculation for example 1 :
  • main will need 32 byte for local variables in stack. 16 byte for variable pt (2 long = 8*2 = 16) after that 4 byte for int (argc) and 8 byte for pointer (argv = address takes 8 byte in 64bit machine).
  • When "canItmodify" function will be called there will be a 8 byte return address and a 8 byte stack frame pointer on stack.
  • "canItModify" will allocate 16 byte for local variable and x will require 8 byte (pointer need 8 byte).
  • Bottom 8 byte will be assigned to x.
Therefore the distance of &x (In "canInModify") from pt (In "main") will be 
8 (size of x)+16 (sizeof(ret)+sizeof(sfp)+16 (space for argv+space for argc)=40.

Calculation for example 2 :
  • main will need 32 byte for local variables in stack. 16 byte for variable pt (2 long = 8*2 = 16) after that 4 byte for int (argc) and 8 byte for pointer (argv = address takes 8 byte in 64bit machine).
  • When "womanInthMiddle" will be called there will be a 8 byte return address and a 8 byte stack frame pointer.
  • local variable in "womanIntheMiddle" will need 12 byte (3*sizeof(int)=3*4=12 byte), therefore 16 byte will be allocated for local variable in it.
  • When "canItModify" will be called  there will be a 8 byte return address and a 8 byte stack frame pointer.
  • "canItModify" will allocate 16 byte for local variable and x will require 8 byte (pointer need 8 byte).
  • Bottom 8 byte will be assigned to x.
Therefore the distance of &x (in "canItModify") from pt (In "main") will be
8 (size of x)+16 (sizeof(ret)+sizeof(sfp) between "canItModify" and "womanIntheMiddle")+16 (local variable in "womanIntheMiddle")+16 (sizeof(ret)+sizeof(sfp) between "womanIntheMiddle" and "main")+16 (space for argv+space for argc)=72 

The conclusion
Now as we have seen how space for local variables are allocated and spaces between function calls, it is easy to calculate the exact distance between any two variables in a function call sequence. As all these variables are in a linear address space and function scope is just an illusion, it is possible to access any variable anywhere in any function.
The above article has been constructed by my own experiment with “C” and reading various article and books through internet. Any suggestion and idea is always welcome. Wish you good luck with this new toy.

Thursday, January 26, 2012

Make your life easier, social coding @github.com

When was the last time when you has written a code that has given you more than grades and points? What do you do after you are done with that code? Do you see the potential of that code? I was unable to answer these question till I decided to put all of my codes even the simpler one that has made my life easier at a social coding site github.
Morning 10:15 AM , I received a call for my interview with Raghuveer. It started with my intro and then went on to my liking and my life at college.
Raghu : Hi
me : Hi , sir.
Raghu : How are u ?
me : I am fine sir.
Raghu : Hey !! you can call me just Raghu.
me : Okay !! Raghu.
Raghu : I was looking at your code. You have written it very cleanly.It is easy to understand and well written. But you forgot to optimize it.
"He was talking about a code for web crawler that I was asked to write and I didn't check if there is a link to a page in some other page that I have already visited.What to do in that case"
me : I was told to submit it in 4 hour and I was not asked to make any optimization ,therefore I preferred to avoid it and my main focus was to complete the crawler and I didn't try to optimize it at that point of time. However I could have used set to manage links , so that I don't visit a link again.
Raghu : Well , what do you do in your spare time.
me : I try to implement ideas that I have in my mind with the knowledge that I have.
Raghu : Can you give me an example ? <--He gave one of his own example.-->
<-- I gave examples of fixing an srt file by writing a C code and few of my projects such as LDM. -->
Raghu : Whenever you write some code that has made your life easier and you think that other can also be benefited by it, you should try to share. It gets easy for interviewer to see your work if u had shared it with all.
<-- After that we had a small discussion about my project on hand gesture recognition and we were done in next 20-30 minutes -->
On the same day, I searched my laptop to collect small projects and codes that I have done either out of my interest or to make my life easier and pushed them all on my github profile.
Some of them are :-
Coding is always fun ,make your life easier by coding for yourself and social coding @github.com.

Sunday, April 17, 2011

Modification in the Application code :- Python Byte-Code(.pyc)

Not amused but its a weird experience that the python byte-code(.pyc) which I generated on my system refused to work properly on other systems.Their is nothing wrong in it . When a python compiler generates the byte-code it optimizes the source-code suitable for further execution.However it is easy to take the byte-code in any platform and it'll work well.A Java programmer will think that once I've created the byte-code I can move the code anywhere and in any system and it'll work but this is not true with python byte-code(.pyc). (.pyc) is very different from (.class).Python byte-code is not compatible between python releases(eg:- Python2.x is not compatible with any of python-3.x release).Also, some of the modules like multiprocessing are not well supported in windows operating system , therefore a code or byte-code using these module will not work properly on windows operating system. This is one of the reason that it will also create problems while porting to other platforms.
However as some of the bugs are reported here is a quick solution to those.
  • Bug 1. IOError: [Errno 2] No such file or directory: '/home/sachin/LDM/a9c97fa678f4a067bccf15a8befb27358d72de8b7b202693ed1d174c/Uinfo' .Submitted by Arihant (Sachin).
  • Bug 2. ZeroDivisionError: integer division or modulo by zero .Submitted by blunderboy & pankajbankanitjsr.

Now the solution.
  • As per the Bug 1 is concerned.I didn't really get it. This part of code is working well. This code has been checked on Fedora , Ubuntu & Mandriva.It is working very well.However if you still having problem create "a9c97fa678f4a067bccf15a8befb27358d72de8b7b202693ed1d174c" folder at the installation directory inside LDM folder.Also create a Uinfo file in this newly created folder.

  • Now on the report of Bug 2 problem was traced back to TabWidget.py.Download TabWidget.py from here.In this file go to line number 148 and replace self.setCellWidget(row,2,self.getLabel(str((100*dL)/int(obj.length))+'%',str(100*dL/int(obj.length)))) line with

    if int(obj.length) == 0 :
      self.setCellWidget(row,2,self.getLabel(str(0)+'%',str(0)))
    else :
     self.setCellWidget(row,2,self.getLabel(str((100*dL)/int(obj.length))+'%',str(100*dL/int(obj.length))))


    Remember Indentation matters in python.So , do proper indentation while updation.Now after you have updated the code , replace the TabWidget.pyc in your LDM installation with TabWidget.py.
    Note :- If you get the updated code at line-148 of TabWidget.py that means it has already been updated.So , put it in place of TabWidget.pyc and it'll work.
One important thing is that many people keep on asking the installation procedure for LDM.To them

READ INSTRUCTIONS IN INSTALL.TXT & README OF DOWNLOAD

Thank you all for posting bugs.Keep posting bugs as soon as you get it.

Wednesday, March 30, 2011

Release of Prototype-I

It has been quite a long time till I've visited my blog. It seems like documenting took more time that building code. But this is not true in this case. Finally the day has come when the concept below &LDM is floating free in the e-space. Anyone from anywhere can download & enjoy the strength of it. Although it is not complete yet powerful enough to blow your mind. Their are Lot of think to do , a lot of work & in this small life one can't get all of the knowledge around him. Thank god I realized it on time. I started documentation work 2 days ago & it took almost 3 hrs of daily to complete the entire documentation. Now the good news is that I'm done with a very bad documentation of the code but still basic functionality will be quite clear to understand.Now you can get source code of it from here and if you are only interested in using this application you can get it from here . All the necessary information is available with the package.
With this post I'ld like to point out some of the things that are not yet implemented and future modification will have those features :-
  • Site grabber
  • FTP & RTMP support
  • A browser plugin for LDM
  • Reconfiguration of dLoadInformation module(Process XML file for download information)
  • Queuing & time scheduling of downloads
  • A robust download routine 
I had tried very well to clarify the installation process through README.txt & INSTALL.txt available through install package. Still , I'm in doubt that someone can get confused. Visit this link in case anyone get stuck to the installation :-
Installation Instruction
This is 1.0 release of &LDM with all it's good features.With upgrades in future it'll be a fully functional application for your linux desktop.As code is freely available to everyone this gives everyone the equal opportunity to try their hand on it.Everyone can contribute & make it a full-fledge app.Now you can start using &LDM & in case of any query either you can directly mail to me or ask me through this blog. I hope to get all the genuine questions & I'll try my best to solve them.

Wednesday, February 16, 2011

Completion of Prototype-1 of '&LDM'

It was quite a busy time in last 7 days.Each time I made an update in the code , I have seen a new problem.This made me feel that even if each individual module is working flawlessly , it is not necessary that when integrated they will work flawlessly.Apart from this one major problem that couldn't let the code complete was the portion of code that runs individual downloads and their communication , even if I make them communicate through IPC or shared variables and locks etc their was still a time lag in communication that has created multiple critical regions in the programme. 
Their is nothing like pre-build weapon in any programming language that can save you from getting your hand dirty while working with parallel processes.Their is very famous quote "A distributed process is one in which the failure of a computer you didn't even know existed can render your own computer unusable."-lamport,leslie and when you love something you try your best to make it flawless.I tried the same.Till date prototype-1 is complete ( You can see the demo at ) and major part of work is still ahead.This prototype is just a feel of '&LDM' but had solved a major problem of work.Hope everyone will like it.It is just impossible to understand and modify the source code of '&LDM' without proper documentation , which is being done right now.As soon as documentation complete I'll share it through my blog.You can either subscribe to this blog or '&LDM' mailing list to be up-to-date to the development and get all the latest version of '&LDM'.

Love Freedom Love OpenSource

Thursday, February 3, 2011

My View of OpenSource and LDM

I had somewhat good day on 3rd of feb.Yesterday I had a very nice talk with robinanil.Knowing that he works in a money making organisation , I asked him about the importance of OpenSource for his company and he replied like I had just asked some stupid question to him.He said "what OpenSource means for our organisation !!! " and for a moment he was silent.Then suddenly he said OpenSource means a lot to our organization.Although it's not a part of our regular job but I , my friend and  almost  each of us is working in some OpenSource project.It was nice to know that even if those people have a very nice job in a billion dollar organization they are working for OpenSource.
OpenSource is not just learning , trying new idea.It's about human knowledge that belongs to the world.Working in OpenSource doesn't only mean that one should work in some bigger OpenSource project .Whatever knowledge you have that you think may be beneficial to the world, share it to the world.Let the world know , how you've done it.Let other people add their idea in it ,re-share it and enjoy the freedom.
Now is the time to talk something about LDM.Although , I'm not sure but I'm very optimistic this time that I'll be able to out with it's first small working module by 14th feb.Last night when I modified it's older implementation with a new method , I received an extraordinary response.After replacing the entire threads with individual processes , it grew exponentially in speed.Just at 4 partition of download , speed exponentially increased to 500KBPS. I'm trying to increase the number of partitioned downloads and some works in GUI field is still left.14th feb release might not be a complete working LDM but yeah it'll be a small working module and if everything goes all right soon , we all will be enjoying a fully functional LDM in Linux.We have just moved out LDM code group from google codegroup to facebook group and registered our project repository to github from where you all can have the code and enjoy the freedom.Wish everyone will enjoy it.Soon , I'll let you know more about it and I'll also forward the important links through my blog.Have a nice day.