Archive for category C

Recursion

Every passionate programmer through one stage of his career must have tried this out and surely must have loved it. .These are not the best methods to solve problems, yet many complex problems have their natural solution as recursive ones. We have a lots of recursive patterns in nature to be observed. One of the most common is  a tree of which each branch is a tree in itself (though smaller  in size).

  

Even some geometric shapes (fractals) can also be observed to have recursive patterns. You can observe the repeating pattern which is being created recursively.

       

My python function for Koch-Snow flake (fractal) .

def flake(self,length):
if length < 10:
self.move_forward(l)
self.c.update()
return
else:
self.flake(length/3)
self.rotate_left(60)
self.flake(length/3)
self.rotate_right(120)
self.flake(length/3)
self.rotate_left(60)
self.flake(length/3)

My code for the above is available here

Ackermann function

One of the most interesting recursive problems I’ve encountered.

def A(m,n):
if m == 0:
return n + 1
elif n == 0:
return A ( m - 1 , 1 )
else:
return A ( m - 1,  A ( m, n - 1 ) )

It will be observed the behaviour of the function can not be predicted unless the values of the parameters ‘m’ and ‘n’ are known.

This kind of programming might be simple enough but it has its own drawbacks too. These kind of programs might not be supported at production level as they might eat up the system stack and affect the performance drastically.

The size of process stack(8MB) on a standard linux machine can be easily be manipulated with ‘ulimit’ utility.

ulimit  -a

A simple C code to observe how a recursive program eats up the process stack.


void foo( int i ) {
char temp[ 1024 * 1024 ]; //1Mb of memory will be allocated from the stack-frame
printf (" %d \n", i );
foo ( i + 1 );

}

int main() {
foo( 1 );
}

Each time the ‘foo’ is invoked a new stack frame is created and a character array of 1 MB size is allocated from it  .So after a definite number of recursive calls when their is no more memory left it results in ‘‘segmentation-fault” when the program tries to allocate memory in the new frame( outside of process’s address-space).

Changing the size of the array ‘temp’ and size of stack using

‘ulimit    -s    <value>’

will give interesting results.

Tail-Recursion

Here the recursive procedure call is kept at the bottom of the procedure. This is of significant importance because an optimization technique can be used where no new stack frame is allocated for a recursive procedure call, instead the new frame can be used to replace the current frame.  This kind of optimization is called tail-call-optimization . Many functional Programming languages like to cope with this situation has implemented

I tried out some of both basic & classical recursive problems during my graduation years. Anyone who is interested with recursive patterns I suggest you to try out the below problems.

Eight Queens Problem  ,  Towers of Hanoi.  , Min-Max Algorithm   ,Creating  Fractal shapes SICP Chapter-1 (a lot of mind-bending problems are in there)

Advertisements

Leave a comment

Memory inspection using ‘Valgrind’



            Valgrind is a a programming tool suite used for debugging, profiling and detection of memory leaks which are quiet common in C,C++ programs. Detecting memory leaks is done by ‘memcheck’ tool  ,which by other means is a very difficult task to do .

To detect a memory leak using ‘Valgrind’ ,let us take an example code which does memory leak .For Example

                                           
Here in the example
   1)  in function ‘f‘  a char * variable ‘k’ is declared and  memory block of 100 bytes are allocated  to it from the heap. That means , the variable ‘k’  resides  on stack and it contains the  address of a memory block which is there in heap .
   2) the function ‘f’ tries to write in a memory block which has not been allocated to it .That is 
when we write
                                                 k[105] = 10 ;
 we are trying to access the memory byte which lies at an offset of 105 from the ‘k‘ . This memory byte was not allocated to ‘k‘ , hence can lead to serious untrackable bug and mysterious behaviour of the program . When the code is compiled using ‘gcc’ not even a single warning is given , forcing the programmer to believe that the function behaves normally.
                         Apart from this the when the function ‘f’ returns  to the ‘main’ function , the stack frame where the local variables of function ‘f’   (for example ‘k’) gets deallocated, so in this case the value in ‘k‘  ( the address of the 100 byte block) gets lost and thus memory leak occur. For this again, compiler can’t generate error or warning messages.

     So for coping with these kind of problems ,valgrind can be used.  

Using Valgrind  for detecting memory  leaks

    For using Valgrind the program has to be compiled with  ‘-g’  option  

as shown

                    gcc  – g   ‘program_name’.c

then the ‘Valgrind’ program can be used to  generate usefull information 


                    valgrind   –leak-check=yes   ./a.out

For example for the above piece of code it will generate meassages as

Here  in above messages,

   1)  In   ==5124==  , 5124 is the process id .  It is not that important
   2)  Display a stack trace showing where the problem occured. It can be usefull in large complex code.
   3)  Error messages show memory addresses involved as the second component.


Memory leaks  can be analysed by analysing the error messages



Conclusion

            This Dynamic analysis tool is usefull in detecting memory bugs and memory leakage.

Leave a comment

Programming a "PARALLEL PORT" in C using "inb " and "outb()"

   
                           For programming a parallel port in C,the user program is supposed to get the permission for accesing  the I/O port using the call

iopl(permission value)

which changes the previlege of the calling process.
By default the user program has a permission value of 0.So for accessing the parallel port,the user program  is supposed to have a permission value of 3

iopl(3);

  • outb()

For porting a value onto the parallel – port,the function outb() is used .

outb(value,0x378); 


parallel port the out pins are from 2 to 9 pin.


outb(value,portaddr);

will port a byte to the portaddr address.
the port address is to be selected as follows 

for 
/dev/lp0     ——    0x378 
/dev/lp1     ——–   0x3bc

 
a simple program in C to port a value to the parallel port


inb(portaddr)

parallel port register set


there are three main registers for a parallel port

  • status register
  • controll register
  • status  register

so these registers are used to read  the values of specific pins

the address of the status register
/dev/lp0 — >  0x378
/dev/lp1 — >  0x

4 Comments

Creating commands in linux by a simple C program

Below i’ll try to  give an idea about how bash commands are implemented in linux by illustrating a small example.

        Simple way to create a command( in C ) ‘hello’ which prints hello world.

  • Step1 :  Create a cprogram “test.c” to print the string “hello world” by          first opening the file “test.c” using the text editor “vim”

                    

                                 vim test.c  
                           
                         and then writing into it

                                #include
                                main(){
                                           printf(“hello world\n”); 

                                 }

  • Step 2  : now compile the program by using the compiler gcc

                                gcc test.c

                       to produce an executable file” a.out”.Now this file is the object file which prints the string “hello world” to the monitor.for executing the file we use as

                               ./a.out

  • Step 3 :  Actually, a command like “cp” has it’s executable file in the directory /bin ,so by copying our executable file to that folder we can use it as a command .

                              sudo cp a.out /bin/hello

         which prompts for the root password

             Now we can use the command “hello” in the bash prompt to print “hello world” on the screen.

Leave a comment