Some Interesting lInux commands Usage

Write a linux command that prints the list of all the unique include files in all the c++ files in a given area : 

Answer :

         find . -name "*.cxx" | xargs grep "#include" | awk '{print $2}' | sort -u

Defining a clock signal in VHDL

Defining a clock signal in VHDL

Clock is the backbone of any synchronous design. For test-benches, a clock is the most desired signal as almost every design requires a clock. Going a bit deeper, a clock signal is a binary signal that changes state every few time units. So, defining a clock in VHDL is pretty simple, as shown below in the following code:

                signal my_clock : std_logic;

                process               

                                my_clock <= ‘0’;

                                wait for 5 ns;

                                my_clock = ‘1’;

                                wait for 5 ns;

                end process;

The above code defines a clock of  period 10 ns with 5 ns high time and 5 ns low time, hence, 50% duty cycle. Since, we are assigning a value to my_clock in the code, it can wither be defines as a signal or an output. Most probably, clocks are defined in test-benches, hence, are internal signals. High time and low time don’t always need to be same. You can always define a clock that has different high and low times as shown below:

signal my_clock : std_logic;

                process

                                my_clock <= ‘0’;

                                wait for 8 ns;

                                my_clock = ‘1’;

                                wait for 2 ns;

                end process;

As we can see, now, my_clock has a duty cycle of 80%; i.e. a high time of 80% and a low time of 20%.

Defining a clock in this way, obviously, is not synthesizable as we are using delays in code, and delays cannot be synthesized. Hence, this way of defining a clock can only be used in a test-bench to test a piece of code. If you need to write a synthesizable clock, then you have to use structural coding. The simplest of clock generation circuits is a ring counter (a chain of inverters connected back-to-back), but it will have a variable frequency clock because delay of inverters changes on change in operating conditions.

some good reads about process

Today I was supposed to write a function that finds user name or user Id who is running the application. I was looking for C++ APIs that can bring this information for me. I found two API's getuid and geteuid. I could not understand the difference between these two So I did some research around it and  found one interesting paper and a nice example. unfortunately I could not read it the whole paper but it looks cool stuff so I thought of sharing it with you. You can check links in References at the end of post:

Some facts about process :  Each process has a set of user Ids and group Ids that determines which system resources like network ports and files a process can access. Certain privileged User Id or group Ids allow a process to access restricted  system resources. E.g. 0 id is preserved for superuser root and allows a process to access all resources.

Each process has three Ids :

Real User ID(ruid) : It identifies owner of process.
Effective user ID(euid) : It is used in most access control decisions.
Saved ID (suid): It stores previous User ID so that it can be used later.

Similarly a process has three group Ids :Real group ID, Effective Group ID,Saved Group ID that has the same meaning as corresponding user ID.

In linux, a process has fsuid and fsgid as well for access control to filesystem. fsuid usually follows the value in euid unless it is not set by setfsuid and similarly fsgid follows the same value in effective group ID unless explicitly set by setfsgid.

 Since access control is based on effective user-id, A process gains privilege by assigning a privileged user ID to its effective ID and drops privilege by removing privilege user ID from effective user ID. Privilege can be removed temporary or permanently.

Gaining or removing privilege temporary : Process assigns the privileged user ID to process's effective user-ID and move original effective ID saved ID so that later privilege can be removed.

Gaining or removing privilege permanently :  Process assigns or remove the privileged ID from all three User-IDs. As there is no way left to retrieve the previous id privilege is gained or removed permanently respectively. 

References :
http://www.cs.berkeley.edu/~daw/papers/setuid-usenix02.pdf
http://www.gnu.org/software/libc/manual/html_node/Setuid-Program-Example.html

Can pure virtual functions be defined as well?

A class that contains pure virtual functions is called abstract or interface class and concrete class derived from abstract class is called implementation class. Since abstract class just defines the interface i.e. what data a class contain and what operations can be performed on it. Virtual functions in abstract class are usually declared but not defined. It is the responsibility of derived class to define it.

Declaration of pure virtual function in C++:

virtual <return type> <user defined function name>(<arguments>) = 0; 
e.g.
virtual void Speak(int a) =  0;

But compiler does not complain even if you give the definition of pure virtual function and in some cases it is useful. Let us try to understand where it can be helpful and when that function get called as there can not be object of abstract class.

Let us say we have base class Aeroplane and AeroplaneA and AeroplaneB are derived from it. class Aeroplane has a method called fly() that defines general way of flying. Let us say AeroplaneA and AeroplaneB  have their own way of flying because they are special sort of planes (Jet or something :P). How can we design it in C++?

First approach:   Make function fly() pure virtual and define the fly() function in every class which is an intuitive solution.

  But let us say for another 3 Aeroplanes C, D and E have same general of flying(They are not special kind of planes). In that case you will have to copy the code of fly() function of Aeroplane class to the fly() function of class AeroplaneC, AeroplaneD and AeroplaneE that is duplicate code and moreover let us say there is some bug in flying functionality you will have to change 3 functions and you may forget to modify one or two of them. Hence It is really difficult to maintain.

class Aeroplane {
// constructor,destrcutor etc
public :
   virtual void fly() = 0;
} ;
class AeroplaneA : public Aeroplane{
// constructor,destrcutor etc
public :
   virtual void fly() {
     //own functionality
  }
} ;
class AeroplaneB : public Aeroplane{
// constructor,destrcutor etc
public :
   virtual void fly() {
       //own functionality
   }
} ;
class AeroplaneC : public Aeroplane{
// constructor,destrcutor etc
public :
   virtual void fly() {
     // general fly functionality Duplicate code
   }
} ;
class AeroplaneD : public Aeroplane{
// constructor,destrcutor etc
public :
   virtual void fly() {
     // general fly functioanlity.. Duplicate code
   }
} ;
//similarly for AeroplaneE

Second Approach :  Make function fly() virtual instead of pure virtual. Put the general flying functionality in fly() function of Aeroplane class and whichever class wants to override this functionality it can do. 

    Now we don't need to declare fly() function in AeroplaneC,AeroplaneD and AeroplaneE. Hence for objects of type AeroplaneA or AeroplaneB their own version of fly() will be called. and for rest of the Aeroplanes general fly() function in Aeroplane class will be called. 

class Aeroplane {
// constructor,destrcutor etc
public :
   virtual void fly() {
      // general fly functionality
   }
} ;
class AeroplaneA : public Aeroplane{
// constructor,destrcutor etc
public :
   virtual void fly() {
     //own functionality
  }
} ;
class AeroplaneB : public Aeroplane{
// constructor,destrcutor etc
public :
   virtual void fly() {
       //own functionality
   }
} ;
class AeroplaneC : public Aeroplane{
// constructor,destrcutor etc
// don't need to define fly function here

} ;
class AeroplaneD : public Aeroplane{
// constructor,destrcutor etc
// don't need to define fly function here
} ;

It looks perfect. Isn't it?

But unfortunately answer is No.  It can also cause some problems. e.g.

 Let us say another AeroplaneF(special plane) which has its own way of flying is introduced and designer forget to over ride the fly() function, compiler will not complain, your code will just start working without even a warning. It will be caught as part of bug etc. But what if it is not even caught in testing? For crucial and such critical design you can not take risk or you should not do such mistakes. During the actual run, your Aeroplane may just crash. :(

So what do we do? Neither solution looks like a good solution. Both are bug prone. 

Don't worry we will not let your plane crash.. :) C++ compiler gives you a very nice solution for such problems. 

Solution : Define pure virtual function.  By defining pure virtual function, we can put general fly() functionality in fly() function of Aeroplane and since fly() function is pure virtual all concrete class needs to redefine it and there we can simply call fly() function of class Aeroplane. Hence we have taken care of both problems.  Now there is no duplicate code and compiler enforces you to define virtual function in each concrete class.

class Aeroplane {
// constructor,destrcutor etc
public :
   virtual void fly() = 0 {
      // general fly functionality
   }
} ;
class AeroplaneA : public Aeroplane{
// constructor,destrcutor etc
public :
   virtual void fly() {
     //own functionality
  }
} ;
class AeroplaneB : public Aeroplane{
// constructor,destrcutor etc
public :
   virtual void fly() {
       //own functionality
   }
} ;
class AeroplaneC : public Aeroplane{
// constructor,destrcutor etc
  virtual void fly() {
       Aeroplane::fly();
  }

} ;
class AeroplaneD : public Aeroplane{
// constructor,destrcutor etc
virtual void fly() {
       Aeroplane::fly();
  }


 
} ;

Reference : One of the Item from 50 specific ways to improve your C++ skills by Scott Meyer.

Dead reference Problem and its detection

In Meyer's singleton pattern, we saw how we can use meyer's implementation approach of singleton design pattern to destroy the singleton object efficiently. It seems perfect at the first glance. However, it has certain problem called Dead reference problem. Let us try to understand it with the help of an example :

Let us say there are two static objects of class A and B and we have a singleton design pattern class called log that errors out if there is some error in creation or deletion of A or B. As we had studied in the last post that singleton object is created in Instance() function when it is called first time. A and B calls Instance() function of log while initialization and destruction if there occurs some error. Let us say object of A got created successfully  but while constructing object of B there comes some error and it calls Instance() function of log Hence singleton object got created and possibly whole application exits out after this. Since compiler destroys local static object in the reverse order of their creation Hence log will be destroyed before object of A and let us say there occurs some error in destruction of A Instance() function return an Invalid object and program can behave unexpected. This is called dead reference problem.

Before thinking its solution we should understand what the real problem is. Problem is that we do not know the order of creation of object of A,B and log. A and B should follow the C++ rule(last object created first) but log should be exempted from this rule. log should destroyed after destruction of A and B so that it can catch all errors thrown by creation or destroy of A and B.

We have no way yet to control lifetime of objects (at least not in this post) but we can atleast detect dead reference problem that can be done by keeping a static bool variable called deleted_ inside singleton class which is initialized to false  and set to true in its destructor.


class Singelton {
   static bool deleted_;
public :
  Singleton& Instance() {
    if( !deleted ) {
          static singleton obj;
         return obj;
    } else {
        throw std::runtime_error("dead reference detected") ;
    }
 }

 ~Singeton() {
     inst_ = 0;
    deleted_ = true;
  }
};

bool Singleton::deleted_ = false;

If some object tries to access singleton after its destruction, It will throw an error.

C function that converts hexadecimal value to decimal value.

Hexadecimal to decimal conversion is something that is often needed in hardware. Below functions can be used for hexadecimal to decimal conversion in C:

#include<stdio.h>#include<conio.h>#include<string.h>
int get_value(char a)  { if(a>='0'&& a<='9' ) { return (a- '0'); } else if(a>='A' && a<='F') return ((a-'0')-7); } else if(a>='a' && a<='f') return ((a-'0')-39); else return -1;
}

int htoi(char a[]){ int len=strlen(a); int temp=0; for(int i=0;i<len;i++) { int digit=get_value(a[i]); if(digit == -1){ return -1; } temp=temp*16+digit; } return temp;}
int main(){ char a[]="f0"; clrscr(); int b=htoi(a); if(b == -1) printf("invalid input"); else printf("decimal value is %d",b); getch();        return 0;}

Interesting programming quiz : Array Bound Read Error

Problem: Can you figure out what is wrong with following piece of code?

#include <iostream>int main() {     int a[5] = {1,2,3,4,5};     for (int i = 4; a[i] >= 0 && i >=0 ; i--) {          std::cout<< "ith element of array is "<<a[i]<<std::endl;     }}

I would suggest you to  try it yourself before scrolling down to see the answer. Its quite interesting,

......

......

......

......

......

......

......

......

......

......

......

......

......

......

......

......

......

......

Answer : Here, as one can figure out, the intention is to print array elements from end till we don't hit any negative number. In the first look it may seem fine but unfortunately it will end up in ABR (Array Bound Read).

Explanation : After the completion of 5th iteration; i.e. when i = 0, compiler will decrement i;  i.e., i will become "-1". It will, then, try to check the condition, which will result in reading a[-1]. Since, array can have indexes only greater than or equal to 0, it will result in an error. Trying to read array elements out of the allowed indexes is termed as Array Bound Read Error. Hence, one should avoid such conditions because it can result into random result. The program can crash anytime. If you are lucky, it may run successfully also. Its all up to your luck.  Instead, it should be

for (int i = 5; i>=0 && a[i]  >= 0 ; i--) {

i.e. first check index value and then do the array access operation.

Here, with the above solution, one more interesting thing comes up to understand. In AND (&&) operation compiler first evaluates  condition1; if it is true, then goes to evaluate condition2; otherwise return false from there only.

For example,

#include <iostream>
int main() {int i = 0;int j= 1;if(  ( i == 1) && (++j ==3)  ) {      std::cout<<"inside if"<<std::endl;}std::cout<<"i is "<<i<<" and j is "<<j<<std::endl;}

Output :

i is 0 and j is 1

Here, as you can see code control will not go into if branch as none of condition is true. since condition1 i==1 is false, compiler will not even check condition2 i.e. value of j will not be incremented.

Internally,  compiler might be doing some following kind of transformation to evaluate && operation

  bool cond = (i==1);  if( cond ) {      cond = (++j != 0) ;  }if(cond){      std::cout<<"inside if"<<std::endl;}

Also read:

• Automatic include of header dependencies in makefile
• Library
• C++ trivia
• Some good reads about process
• String class vs dynamically allocated array

Function Overloading

Function overloading is a feature inherent in many programming languages including c++. It allows a user to write multiple functions with same name but with different signatures. On calling the function, the version of the function corresponding to the signature will be referred to. Function signature includes function parameters/arguments, but it does not include return type. Function signature may differ in terms of number of parameters or type of parameters. Let us illustrate with the help of a few examples:

Example 1: The two functions below are overloaded, since the return type of arguments differ:

int func(int a,int b);double func(double a,double b);

Example 2: The two functions below are overloaded because they differ in the number of arguments:

int func(int a,int b);int func(int a,int b,int c);

Example 3: The two functions below are not overloaded because they differ only in terms of their return type; the number and type of all the arguments is same.

void func(int a,int b,int c);int func(int a,int b,int c);

Please note that C does not support function overloading because there is no concept of name mangling in C. On the other hand, C++ does support function overloading as name mangling is supported in C++. Name mangling is mangled name of function name and its signature which is used by C++ compiler internally to refer to functions. For instance, in above example 1, mangled name of functions will look something like shown below:

func__int_intfunc__double_double

This way C++ compiler can handle function overloading. 

Note : above are not the actual mangled names. Compiler can make some more complicated names. this is just for understanding. 

Also read:

• Meyer's singleton pattern
• Function overloading
• Comparison between array, linked list and vector
• C function for hexadecimal to decimal conversion
• Problem - can you figure out is there something wrong with this code

Setup checks and hold checks for flop-to-flop paths

In the post (Setup time and hold time – static timing analysis), we introduced setup and hold timing requirements and also discussed why these requirements exist. In this post, we will be discussing how these checks are applied for different cases for paths starting from and ending at flip-flops.

In present day designs, most of the paths (more than 95%) start from and end at flip-flops (exceptions are there like paths starting from and/or ending at latches). There can be flops which are positive edge triggered or negative edge triggered. Thus, depending upon the type of launching flip-flop and capturing flip-flop, there can be 4 cases as discussed below:

1)      Setup and hold checks for paths launching from positive edge-triggered flip-flop and being captured at positive edge-triggered flip-flop (rise-to-rise checks): Figure 1 shows a path being launched from a positive edge-triggered flop and being captured on a positive edge-triggered flop. In this case, setup check is on the next rising edge and hold check is on the same edge corresponding to the clock edge on which launching flop is launching the data.

Figure 1 : Timing path from positive edge flop to positive edge flop (rise to rise path)

Figure 2 below shows the setup and hold checks for positive edge-triggered register to positive edge-triggered register in the form of waveform. As is shown, setup check occurs at the next rising edge and hold check occurs at the same edge corresponding to the launch clock edge. For this case setup timing equation cab be given as:

            T_ck->q + T_prop + T_setup < T_period + T_{skew               (for setup check)}
And the equation for hold timing can be given as:

            T_ck->q + T_prop > T_hold + T_{skew                                  (for hold check)}

Where

        T_ck->q  : Clock-to-output delay of launch register

        T_prop : Maximum delay of the combinational path between launch and capture register

       T_hold : Hold time requirement of capturing register

       T_skew : skew between the two registers (Clock arrival at capture register - Clock arrival at launch register)

 

Also, we show below the data valid and invalid windows. From this figure,

                Data valid window = Clock period – Setup window – Hold window
                Start of data valid window = T_launch + T_hold
                End of data valid window = T_launch + T_period – T_setup

In other words, data at the input of capture register can toggle any time between (T_launch + T_hold) and (T_launch + T_period – T_setup).

Figure 3: Figure showing data valid window for rise-to-rise path

2)        Setup and hold checks for paths launching from positive edge-triggered flip-flop and being captured at negative edge-triggered flip-flop: In this case, both setup and hold check are half cycle checks; setup being checked on the next falling edge at the capture flop and hold on the previous falling edge of clock at the capture flop (data is launched at rising edge). Thus, with respect to (case 1) above, setup check has become tight and hold check has relaxed.

Figure 4: Timing path from positive edge flop to negative edge flop (Rise-to-fall path)

Figure 5 below shows the setup and hold checks in the form of waveforms. As is shown, setup check occurs at the next falling edge and hold check occurs at the previous falling edge corresponding to the launch clock edge. The equation for setup check can be written, in this case, as:

            T_ck->q + T_prop + T_setup  < (T_period/2) + T_{skew                       (for setup check)}

And the equation for hold check can be written as:
            T_ck->q + T_prop + (T_period/2) > T_hold + T_{skew                         (for hold check)}

 

Figure 5: Setup and hold checks for rise-to-fall paths

Also, we show below the data valid and invalid windows. From this figure, 

                Data valid window = Clock period – Setup window – Hold window

                Start of data valid window = T_launch – (T_period/2)+ T_hold

                End of data valid window = T_launch + (T_period/2) – T_setup

As we can see, the data valid window is spread evenly on both sides of launch clock edge.

 

Figure 6: Figure showing data valid window for rise-to-fall path

3)           Setup and hold checks for paths launching from negative edge-triggered flip-flop and being captured at positive edge-triggered flip-flop (rise-to-fall paths): This case is similar to case 2; i.e. both setup and hold checks are half cycle checks. Data is launched on negative edge of the clock, setup is checked on the next rising edge and hold on previous rising edge of the clock.

Figure 7: Timing path from negative edge flop to positive edge flop (fall-to-rise path)

Figure 8 below shows the setup and hold checks in the form of waveforms. As is shown, setup check occurs at the next rising edge and hold check occurs at the previous rising edge corresponding to the launch clock edge.  The equation for setup check can be written, in this case, as:

            T_ck->q + T_prop + T_setup  < (T_period/2) + T_{skew                       (for setup check)}

And the equation for hold check can be written as:
            T_ck->q + T_prop + (T_period/2) > T_hold + T_{skew                         (for hold check)}

Figure 8: Setup and hold checks for fall to rise paths

Also, we show below the data valid and invalid windows. From this figure,

                Data valid window = Clock period – Setup window – Hold window

                Start of data valid window = T_launch – (T_period/2)+ T_hold

                End of data valid window = T_launch + (T_period/2) – T_setup

In this case too, data valid window spreads evenly on both the sides of launch clock edge.

 

Figure 9: Figure showing data valid window for fall-to-rise path

4)             Setup and hold checks for paths launching from negative edge-triggered flip-flop and being captured at negative edge-triggered flip-flop (fall-to-fall paths): The interpretation of this case is similar to case 1. Both launch and capture of data happen at negative edge of the clock. Figure 10 shows a path being launched from a negative edge-triggered flop and being captured on a negative edge-triggered flop. In this case, setup check is on the next falling edge and hold check is on the same edge corresponding to the clock edge on which launching flop is launching the data.

Figure 10: Path from negative edge flop to negative edge flop (fall to fall path)

Figure below shows the setup and hold checks in the form of waveforms. As is shown, setup check occurs at the next falling edge and hold check occurs at the same edge corresponding to the launch clock edge. 
The equation for setup check can be given as:

                T_ck->q + T_prop + T_setup < T_period + T_{skew                (for setup check)
And the equation for hold check can be given as:}

               T_ck->q + T_prop > T_hold + T_{skew                                                    (for hold check)} 

Figure 11: Setup and hold check for fall-to-fall path

Also, we show below the data valid and invalid windows. From this figure,

                Data valid window = Clock period – Setup window – Hold window

                Start of data valid window = T_launch + T_hold

                End of data valid window = T_launch + T_period – T_setup

 

Figure 12: Figure showing data valid window for fall-to-fall path

Related posts:

• Setup time and hold time : static timing analysis
• Setup and hold checks for latch-to-reg and reg-to-latch paths
• Data checks: data setup and data hold checks
• On-chip variations
• Race conditions