Random Numer Geneator in C

Most of us will have an intuitive feeling of randomness. When a sequence of occurring something has no recognizable patterns or regularities.

But why should we at all bother about randomness? Because it is  core component of simulation of any algorithm. If the random number generator component of the simulation is biased the analysis of the simulation will be incorrect. Or if the generator always generate same sequence its practically unreliable because simulations need to be run many time on different set for the purpose of analysis.

It can be used to select a random sample from a set of large data 
 
Lets look an example of tossing a coin.

Sequence 1st seems to be less random than 2nd but actually both have same probability of occurence of 1/2^20

Which gives the birth to the next question how are we going to measure randomness. Yes you read correct measure randomness .

Some of the naive technique can be

frequency test in this test we check the frequency of each element in the sequence and make sure that each element roughly occur equal number of time
BUT if we pass a random generator on this test are not we loosing the test case where one element is excessive are not occuring { 1,1,2,1,1} a good random sequence of set {1,2}.
 Also frequency test makes no difference between generator generating these two sequence frequently {1,1,1,2,2,2} {1,2,1,2,1,2} basically when element occur in the sequence is not the concern for the frequency test.

 So looking for a better statical analysis of the random number is a good option (that will be whole new blog).

Generating Random Number

Option 1:

This is ok but has some major flaw because the way rand work its real randomness lies in upper bit and not the lower bits. MOD operation takes the lower bit into consideration and discards the higher order bits hence this generator will not satisfy our need.

Option 2:
   
This takes the upper bit into consideration but this too has flaw each time you run these two random number generator the output is same
Because on every run it is  initialized with default seed. So we need a unique seed every time we need to generate random number

TIME can be that seed

Option 3:


Now you have a generator in C which generate a random sequence uniquely every time it is run.

Rectangle circumscribing group of smaller rectangles

Today, i am going to discuss how to find a rectangle in a plane which circumscribe the group of the rectangle in the same plane.

Eg:
       

Red Rectangle circumscribing the group of smaller rectangles 

Input will be a link list of rectangle. Each node in the link list  containing {x,y,h,w} of separate rectangle from the group of rectangles.

Output should be the {x,y,h,w} of the rectangle which tightly circumscribe the rectangles of the group.

Lets solve this step by step:

Initial 

Input to the algo

{0,0} in the plane in top left corner.

We will start with assuming the Circumscribing rectangle[ Tightly bound ] (CR) as {0,0,0,0}.

In first iteration we will make CR equal to the first rectangle that is {5,5,5,10}.

In second iteration.

1. Find x for right most edge in new Circumscribing rectangle.
   
   Firstly
   #define RightEdge(RECTANGLE)  RECTANGLE ->X +RECTANGLE -> WIDTH;
   
   Secondly
   rightmost edge will be T= MAX( RightEdge(circumscribing Rectangle  ), RightEdge(New Rectangle)),
   
2. New x coordinate of CR will be MIN of its current x and x coordinate of New Rectangle.
3. New Width for CR will be T(from step 1) - new X coordinate of CR (calculated in step 2)
4. Similarly y and height can also be calculated.
   
   
   

Code:

void RectUnion(RectT *CR, RectT *NEXTRECTANGLE)
{
int t1, t2;
// the new recatngle in the group is of negligible size
if (!NEXTRECTANGLE->w && !NEXTRECTANGLE->h)
return;

// first rectangle from the group
if (!CR->w && !CR->h) {
*CR = *NEXTRECTANGLE;
return;
}

//finding rightmost x 
t1 = CR->x + CR->w;
t2 = NEXTRECTANGLE->x + NEXTRECTANGLE->w;
if (t1 < t2)
t1 = t2;
// finding new x
if (CR->x > NEXTRECTANGLE->x)
CR->x = NEXTRECTANGLE->x;

//new width 
CR->w = t1 - CR->x;

t1 = CR->y + CR->h;
t2 = NEXTRECTANGLE->y + NEXTRECTANGLE->h;
if (t1 < t2)
t1 = t2;
if (CR->y > NEXTRECTANGLE->y)
CR->y = NEXTRECTANGLE->y;
CR->h = t1 - CR->y;
}

PS: comment if you have any confusion. For exercise you can write a program which takes input as both set of rectangle and CR and verifies the solution. 

Returning memory from Stack or accessing memory out of scope

A sample program trying to access stack memory after the function it belongs to has returned.

#include<stdio.h>
int* testing()
{
      int i=5;
      int *ptr=&i;
      return ptr;
}

int main()
{
             printf("%d\n",*(testing()));
             return 0;
}

There won't be any compilation error but the output of the program will be unpredictable.

Now lets do

#include<stdio.h>
void printMem(int *ptr)
{
printf("%d\n",*ptr);
}
void testing()
{
  int i=5;
  int *ptr=&i;
   printMem(ptr);
 }
int main()
{
   testing();
   return 0;
}

ya you judged it right, its ok. It will print 5 every time, because the address of i is still in the scope of the process. While in case of first program it was not.

Lets look at this program


Here the output will be correct and that is 5. Why?, because test function is returning the address of the static variable.
Static variable lies in the data segment of the process. Once a static variable is created it remains in the process memory throughout its life span.
lets look in another program

#include<stdio.h>
int main()
{
  int *ptr;
  {
     int i=5;
    ptr=&i;
}
 printf("%d\n",*ptr);
return 0;
}

This will also result in unpredictable result WHY??????? this is for you :)

BoundChecker

There are many static code analysis tools, to analyse memory issues in you code for example 

1. PC-Lint (http://www.gimpel.com/html/pcl.htm)
2. PVS-studio (http://www.viva64.com/en/pvs-studio/)
3. Coverity: (http://www.coverity.com/products/coverity-save.html)
4. Purify (http://www-142.ibm.com/software/products/us/en/ratpurwin)

Some Open Source Project

1.  CPPCheck: (http://cppcheck.sourceforge.net/  http://sourceforge.net/apps/mediawiki/cppcheck/index.php?title=Main_Page)
2. Veera++  ( https://bitbucket.org/ThArGos/vera)
3. Splint ( http://lclint.cs.virginia.edu/)

But in this post i will be talking about BoundsChecker

 BoundsChecker is the classical program to detect memory leak or memory corruption in the program. If your application is too large and you need an automation tool to detect memory corruption BoundsCheker is for you.

Some of the defects detected by boundsChecker is as follows

1. Memory leak
2. memory corruption
3. out of bound memory access
4. buffer overflow 
5. Deadlock 
6. Race condition

You can download BounsChecker from http://www.microfocus.com/store/devpartner/boundschecker.aspx

after installation you can find "micro focus" folder in your program files folder.

If you are using Visual Studio you are done. You will find a task bar dedicated to BoundsChecker, A simple UI to access all the feature, but if you are using command prompt to build the project, there is still lot to be done.

Add  "C:\Program Files (x86)\Micro Focus\DevPartner Studio\BoundsChecker"  make necessary changes to  fit your system path, this to PATH environment variable of the system

Now replace your compiler with nmcl and linker with nmlink , these are just the raper to your cl and link.You can build the project now. In the same path you can find BC.exe run the same. Open your project executable from BC.exe to collect the log of all the defects in your program. this process is actually a incremental build where BC plug in some of its code into you intermediate code to analyse defect properly.

You can also run your executable created without incremental build from Boundschecker but it not so effective as the first process.  

Free/ double free in a process // Use of BoundsChecker and Coverity

If you have never given importance to free chances are you never worked in real life project. If i try to define free in one line, its the way to transfer ownership of "memory allocated" back to the heap manager.

Free should only be used with something you malloced or NULL.

int x=20;
int ptr= &x;
free(ptr); 
this will result in an error, as memory pointed by ptr is in  stack part of the process.

Wondered why NULL?

For NULL free only checks the value of ptr and does not release any block, process is not harmed at all. This can be used as boon if used properly. Will explain you how at correct time.

When we allocated memory by malloc or calloc, it is supplied by heap manager from the heap of the process which i limited. Once the maximum heap memory allocated is exhausted the process dies  crying for more space.

example:-

int main()
{
            int *ptr;
            while(1)
            {
                   ptr=malloc(10);
            }

}
this process dies/(phat jaiyega, mar jayega - :) ) because of lack of heap memory.

For a large application like in a small software if there is a memory leak, lets say small as 2 or 3 bytes in a piece of code, but if the application runs for 2 to 3 days (for those who don't  shut down there system - i am one of them though) chances are this piece of code  gets executed many times resulting in large memory leak.


Let me list few of the leaks/errors due to not using  free properly;

1>

char* Copy(int *str)
{
     char* sptr= malloc(30);
     memset(sptr,'\0',30);
     strcpy(sptr,str);
}

A programmer after some times write  a function PlayBasketBall(int number,char* player1,char* player2)

and call it as PlayBasketBall(1,Copy(user1),Copy(online_user)). The programmer missed that function call to Copy allocates memory which need to be freed , hence every time PlayBasketBall is called it leaks memory. Believe me its very common, i have found such errors in very reputed application. The thumb rule is, the function allocating memory should take the responsibility to free it.

2> Deallocating a memory area with free does not make the contents of the pointer NULL.

After free the pointer remains pointing to the memory, its just that its made available to heap manager, hence can,t be access during execution.

What will happen if you double free the pointer.

case 1:

int *ptr= malloc(20);
if(xyz>20)
{
    PlayWithPtr(ptr);
    free(ptr);
}
..........
.........\
if(abc<10)
{
    free(ptr);
}

case 2:

typedef struct link
{
  int val;
   struct link *common;
   struct link * next;
}LL;

void delete(LL* list)
{
    if(list==NULL)
         return;
    delete(list->next);
    delete(list->common);
    free(list);
     
}
int main()
{
  LL list1,list2;
  list1.val=2;
  list1.next=NULL;
  list1.commom= malloc(sizeof(LL));
  list1.common->next=NULL;
  list1.common->common->next=NULL;
  
  list2.val=3;
  list2.next=NULL;
  list2.common=list1.common;

  /*...... manipulate list1 and list 2 ............... */

delete(&list1);
delete(&list2);
}


if both the condition if true ptr is freed twice.?? you are trying to return double the memory what you borrowed :) you are making heap manager rich. 

in case 2: the common area is deleted twice while deleting link list1 and list2. this will result in memory corruption.


It will result in unpredictable behavior and most probably a crash.
Its best to set the pointer to NULL after free to be on safer side. Now i think you got the boon of free(NULL); 

3> Memory used after free.

int *ptr= malloc(20)
if(i am happy)
{
    free(ptr);
}
............
..................
.........

if(my dad increased my pocket money this month)
{
     ptr[7]=ptr[6]+amount increased;
}

now think what will happen if the guy is happy because his dad increased his pocket money. this might lead to unpredictable behavior and you might be roaming in GBs of code to find the reason of the bug. but if the code would have been


int *ptr= malloc(20)
if(i am happy)
{
    free(ptr);
    ptr=NULL;
}
............
..................
.........

if(my dad increased my pocket money this month)
{
     ptr[7]=ptr[6]+amount increased;
}



Program will crash at the exact point where there is issue and its easy to fix.

From second and third reason its clear free(ptr) should also be accompanied by ptr=NULL;