/* Ajith - Syntax Higlighter - End ----------------------------------------------- */
Showing posts with label C. Show all posts
Showing posts with label C. Show all posts

3.14.2013

Divide a number by 3 without using any arithmetic operators

How to divide a number by 3 without using operators + - / * %

NOTE: I am just trying to collect various answers down in this post available across multiple sites in internet as mentioned in references.

Solution 01:
#include <stdio.h>
#include <stdlib.h>

int main()
{
    FILE *fp=fopen("temp.dat","w+b");
    int number=12346;
    int divisor=3;
    char *buf = calloc(number,1);
    fwrite(buf,number,1,fp);
    rewind(fp);
    int result=fread(buf,divisor,number,fp);
    printf("%d / %d = %d", number, divisor, result);
    free(buf);
    fclose(fp);
    return 0;
}

9.22.2012

Detecting a Loop in Singly Linked List - Tortoise & Hare

This article is part of article series - "Datastructures"

Previous Article: Reversing a Singly Linked List.
Next Article: Finding first node in a Loop in Singly Linked List.

Eventhough there are multiple algorithms available we start with

Floyd's Cycle-Finding Algorithm
In simple terms it is also known as "Tortoise and Hare Algorithm" or "Floyd's Cycle Detection Algorithm" named after its inventor Robert Floyd. It is one of the simple cycle detection algorithm. It's a simple pointers based approach.

Robert Floyd

8.23.2012

Write a C Program without main function

In a C program main function is the entry point so it is mandatory to have a main function.

But let us see how can we write a program without main (Kind of hiding main in some obfuscated code). This post is purely out of interest to know that we can do something weird like this, just for learning.


8.09.2012

Implementing ls command in C

We know that ls command in unix displays the list of files in a directory. It has various options to display the data in various styles and formats.

By default its implementation is part of Coreutils package, which is default package in all Linux flavours.

I want to see how we can implement its basic functionality with a simple C program.

3.04.2012

Memory Layout of a C program - Part 2

Continuation of PART-1

As we have seen so much theory in the PART-1 now let us see a real-time example to understand about these segments. we will use size(1) command to list various section sizes in a C code.

A simple C program is given below
#include <stdio.h>

int main()
{
    return 0;
}

$ gcc test.c 
$ size a.out 
   text    data     bss     dec     hex filename
    836     260       8    1104     450 a.out
Now add a global variable as shown below
#include <stdio.h>

int global; /* Uninitialized variable stored in bss*/

int main()
{
    return 0;
}

$ gcc test.c 
$ size a.out 
   text    data     bss     dec     hex filename
    836     260      12    1108     454 a.out
As you can see BSS is incremented by 4 bytes.

Memory Layout of a C program - Part 1

A running program is called a process.

When we run a program, its executable image is loaded into memory area that normally called a process address space in an organized manner. It is organized into following areas of memory, called segments:
  • text segment 
  • data segment 
  • stack segment 
  • heap segment 
Memory layout of a C program
Figure 1: Memory layout

text segment

It is also called the code segment.

This is the area where the compiled code of the program itself resides. This is the machine language representation of the program steps to be carried out, including all functions making up the program, both user defined and system.

For example, Linux/Unix arranges things so that multiple running instances of the same program share their code if possible. Only one copy of the instructions for the same program resides in memory at any time and also it is often read-only, to prevent a program from accidentally modifying its instructions.

The portion of the executable file containing the text segment is the text section.

3.01.2012

Deletion of a Node from Doubly Linked List

This article is part of article series - "Datastructures".

Previous Article: Inserting a Node in Doubly Linked List.

Deletion of a Node 
Let us say our current Doubly Linked List is as shown in Figure-1.
Figure 1: Current Doubly Linked List

  • Deleting First Node of the List
  • Now we have to delete First Node from the List shown in Figure-1. Because of this operation HEAD and Node-2 are affected.
    In HEAD - FIRST variable should now point to NODE-2 (i.e HEAD->FIRST = HEAD->FIRST->NEXT). If you see HEAD->FIRST->NEXT actually HEAD->FIRST currently points to NODE-1 so HEAD->FIRST->NEXT is equivalent to NODE-1->NEXT which is NODE-2.
    In NODE-2 - NEXT variable remains unchanged and PREV variable should now point to NULL since it is the first Node in the List.
    Decrement LENGTH variable in HEAD so that it maintains proper count of Nodes in the List.
    Pseudocode:
    HEAD->FIRST = HEAD->FIRST->NEXT
    
    NODE-2->PREV = NULL
    
    decrement(HEAD->LENGTH)
    Output:
Figure 2: After deleting the First Node in the List.

2.27.2012

Inserting a Node in Doubly Linked List

This article is part of article series - "Datastructures"

Previous Article: Doubly Linked List                                           Next Article: Deletion of a Node from Doubly Linked List.

Insertion of a Node
Before we discuss about how to insert a NODE let us discuss few rules to follow at the time of insertion.

  • Check the location into which the user want to insert a new NODE. The possible locations where an user can insert a new node is in the range of 1 <= loc <= (length of list)+1. Let us say the length of the list is 10 & the user want to insert at location 12 (sounds stupid).

  • As we know we can traverse Bi-Directional in case of Doubly Linked Lists so we have to take care of PREV and NEXT variables in the NODE structure. We should also update the neighboring Nodes which are affected by this operation. If not we might break up the List somewhere or the other by creating a BROKEN LIST.

We have following scenarios in the case of insertion of a NODE.
  • Adding a Node at the start of the Empty List
  • Figure 1: Empty List and the newNode we want to add
    As shown in Figure-1 we have a Empty List with LENGTH set to 0 and FIRST pointing to NULL. Let us add newNode at Location 1. 
    In HEAD - FIRST variable points to newNode (head->FIRST = newNode).
    In newNode - NEXT and  PREV points to NULL as we don't have any other Nodes in the List.
    Increment the LENGTH variable in HEAD once insertion is successful to maintain the count of number of Nodes in the List.
    Pseudocode:
    HEAD->FIRST = newNode
    
    newNode->PREV = NULL
    
    newNode->NEXT = NULL
    
    increment(HEAD->LENGTH)
    Output:
Figure 2: After adding newNode in Empty List. (Changes in BLUE)

2.25.2012

Implementation of Doubly Linked List in C

In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called Nodes. Each Node contains two fields, called Links, that are references to the Previous and to the Next Node in the sequence of Nodes as well as field named Data.
For every Linked List we have something called Head which marks the starting of a list. So we have two main structures namely
  • Node
  • Head

Why we need a new structure for HEAD variable ? 
Just for convenience I decided to have HEAD its own structure. You can even use the Node structure.

Node
Every Node in a Doubly Linked List has three main members namely
  • PREV
  • DATA
  • NEXT
As their names say
  • PREV - holds the memory location of the Previous Node in the List. If there are none we point towards NULL. For the First Node in the List PREV points to NULL.
  • NEXT - holds the memory location of the Next Node in the List. If there are none we point towards NULL. For the Last Node in the List NEXT points to NULL.
  • DATA - In simple words it holds Data. In our case it holds the memory location to the actual data to be held by the Node.
typedef struct node
{
    struct node *prev;
    void        *data;
    struct node *next;
}NODE;

Head
Head acts as the  "head" of the List. Head structure has two members namely
  • LENGTH - holds the count of number of Nodes in the List.
  • FIRST - hold the memory location of the first Node in the List. If the List is EMPTY it points to NULL.
typedef struct head 
{
    unsigned int length;
    struct node  *first;
}HEAD;

NOTE: Our Head structure doesn't contain any pointer to the Tail of the List. Eventhough its a best way to include a pointer to Tail Node we decided to cover that implementation in Circular Doubly Linked List.

8.07.2010

Printing logs based on log levels in C

LOG LEVELS ??
As per my definition LOG LEVEL means a way to differentiate the importance of logs in our application. We can divide the logs into categories based on their importance and effect for e.g. ERROR logs are more important than DEBUG logs.


Why do we need to print logs based on LOG LEVEL ??
It is really helpful in projects with millions of lines of source code where the user can't use #defines or #ifdef's in order to maintain DEBUG prints. It is really tiresome to maintain #defines and #ifdef atleast for printing logs.

printk which is a part of LINUX KERNEL supports printing logs based on LOG LEVEL and it is really helpful in debugging kernel.

printf or any of its brothers & sisters don't support the option to print logs depending upon the log levels.

7.07.2010

Implementation of Stack using Singly Linked Lists

Stacks are linear data structures which means the data is stored in what looks like a line (although vertically). In simple words we can say
A stack is a last in, first out (LIFO) abstract data type and data structure.
Basic usage of stack at the Architecture level is as a means of allocating and accessing memory.


We can only perform two fundamental operations on a stack: push and pop.

The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the list, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty list.

A stack is a restricted data structure, because only a small number of operations are performed on it.

6.30.2010

Static Functions in C

By default all functions are implicitly declared as extern, which means they're visible across translation units. But when we use static it restricts visibility of the function to the translation unit in which it's defined. So we can say
Functions that are visible only to other functions in the same file are known as static functions.

Let use try out some code about static functions.
main.c
#include "header.h"

int main()
{
hello();
return 0;
}
func.c
#include "header.h"

void hello()
{
printf("HELLO WORLD\n");
}
header.h
#include <stdio.h>

static void hello();
If we compile above code it fails as shown below
$gcc main.c func.c
header.h:4: warning: "hello" used but never defined
/tmp/ccaHx5Ic.o: In function `main':
main.c:(.text+0x12): undefined reference to `hello'
collect2: ld returned 1 exit status
It fails in Linking since function hello() is declared as static and its definition is accessible only within func.c file but not for main.c file. All the functions within func.c can access hello() function but not by functions outside func.c file.

Using this concept we can restrict others from accessing the internal functions which we want to hide from outside world. Now we don't need to create private header files for internal functions.

Note:
For some reason, static has different meanings in in different contexts.

1. When specified on a function declaration, it makes the function local to the file.
2. When specified with a variable inside a function, it allows the variable to retain its value between calls to the function. See static variables.

It seems a little strange that the same keyword has such different meanings...

4.25.2010

Singly Linked List in C

Check Implementation of Singly Linked List for theoretical explanation regarding implementation of singly linked lists.

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

//Structure containing a Data part & a
//Link part to the next node in the List

struct Node
{
 int Data;
 struct Node *Next;
}*Head;

// Counting number of elements in the List

int length()
{
  struct Node *cur_ptr;
  int count=0;

  cur_ptr=Head;

  while(cur_ptr != NULL)
  {
     cur_ptr=cur_ptr->Next;
     count++;
  }
  return(count);
}

// Deleting a node from List depending upon the data in the node.

int delNodeData(int num)
{
  struct Node *prev_ptr, *cur_ptr;

  cur_ptr=Head;

  while(cur_ptr != NULL)
  {
     if(cur_ptr->Data == num)
     {
        if(cur_ptr==Head)
        {
           Head=cur_ptr->Next;
           free(cur_ptr);
           return 0;
        }
        else
        {
           prev_ptr->Next=cur_ptr->Next;
           free(cur_ptr);
           return 0;
        }
     }
     else
     {
        prev_ptr=cur_ptr;
        cur_ptr=cur_ptr->Next;
     }
  }

  printf("\nElement %d is not found in the List", num);
  return 1;
}

// Deleting a node from List depending upon the location in the list.

int delNodeLoc(int loc)
{
  struct Node *prev_ptr, *cur_ptr;
  int i;

  cur_ptr=Head;

  if(loc > (length()) || loc <= 0)
  {
      printf("\nDeletion of Node at given location is not possible\n ");
  }
  else
  {
      // If the location is starting of the list
      if (loc == 1)
      {
          Head=cur_ptr->Next;
          free(cur_ptr);
          return 0;
      }
      else
      {
          for(i=1;i<loc;i++)
          {
              prev_ptr=cur_ptr;
              cur_ptr=cur_ptr->Next;
          }

          prev_ptr->Next=cur_ptr->Next;
          free(cur_ptr);
      }
  }
  return 1;
}

//Adding a Node at the end of the list

void addEnd(int num)
{
  struct Node *temp1, *temp2;

  temp1=(struct Node *)malloc(sizeof(struct Node));
  temp1->Data=num;

  // Copying the Head location into another node.
  temp2=Head;

  if(Head == NULL)
  {
     // If List is empty we create First Node.
     Head=temp1;
     Head->Next=NULL;
  }
  else
  {
     // Traverse down to end of the list.
     while(temp2->Next != NULL)
     temp2=temp2->Next;

     // Append at the end of the list.
     temp1->Next=NULL;
     temp2->Next=temp1;
  }
}

// Adding a Node at the Beginning of the List

void addBeg(int num)
{
  struct Node *temp;

  temp=(struct Node *)malloc(sizeof(struct Node));
  temp->Data = num;

  if (Head == NULL)
  {
     //List is Empty
     Head=temp;
     Head->Next=NULL;
  }
  else
  {
     temp->Next=Head;
     Head=temp;
  }
}

// Adding a new Node at specified position

void addAt(int num, int loc)
{
  int i;
  struct Node *temp, *prev_ptr, *cur_ptr;

  cur_ptr=Head;

  if(loc > (length()+1) || loc <= 0)
  {
     printf("\nInsertion at given location is not possible\n ");
  }
  else
  {
      // If the location is starting of the list
      if (loc == 1)
      {
          addBeg(num);
      }
      else
      {
          for(i=1;i<loc;i++)
          {
              prev_ptr=cur_ptr;
              cur_ptr=cur_ptr->Next;
          }

          temp=(struct Node *)malloc(sizeof(struct Node));
          temp->Data=num;

          prev_ptr->Next=temp;
          temp->Next=cur_ptr;
      }
  }
}

// Displaying list contents

void display()
{
  struct Node *cur_ptr;

  cur_ptr=Head;

  if(cur_ptr==NULL)
  {
     printf("\nList is Empty");
  }
  else
  {
      printf("\nElements in the List: ");
      //traverse the entire linked list
      while(cur_ptr!=NULL)
      {
          printf(" -> %d ",cur_ptr->Data);
          cur_ptr=cur_ptr->Next;
      }
      printf("\n");
  }
}

//Reversesing a Linked List

void reverse()
{
  struct Node *prev_ptr, *cur_ptr, *temp;

  cur_ptr=Head;
  prev_ptr=NULL;

  while(cur_ptr != NULL)
  {
     temp=prev_ptr;
     prev_ptr=cur_ptr;

     cur_ptr=cur_ptr->Next;
     prev_ptr->Next=temp;
  }

  Head=prev_ptr;
}


int main(int argc, char *argv[])
{
 int i=0;

 //Set HEAD as NULL
 Head=NULL;

 while(1)
 {
    printf("\n####################################################\n");
    printf("MAIN MENU\n");
    printf("####################################################\n");
    printf(" \nInsert a number \n1. At the Beginning");
    printf(" \n2. At the End");
    printf(" \n3. At a Particular Location in the List");
    printf(" \n\n4. Print the Elements in the List");
    printf(" \n5. Print number of elements in the List");
    printf(" \n6. Reverse the linked List");
    printf(" \n\nDelete a Node in the List");
    printf(" \n7. Delete a node based on Value");
    printf(" \n8. Delete a node based on Location\n");
    printf(" \n\n9. Exit\n");
    printf(" \nChoose Option: ");
    scanf("%d",&i);

    switch(i)
    {
      case 1:
      {
          int num;
          printf(" \nEnter a Number to insert in the List: ");
          scanf("%d",&num);
          addBeg(num);
          display();
          break;
      }

      case 2:
      {
          int num;
          printf(" \nEnter the Number to insert: ");
          scanf("%d",&num);
          addEnd(num);
          display();
          break;
      }

      case 3:
      {
          int num, loc;
          printf("\nEnter the Number to insert: ");
          scanf("%d",&num);
          printf("\nEnter the location Number in List at which \
          the Number is inserted: ");
          scanf("%d",&loc);
          addAt(num,loc);
          display();
          break;
      }

      case 4:
      {
          display();
          break;
      }

      case 5:
      {
          display();
          printf(" \nTotal number of nodes in the List: %d",length());
          break;
      }

      case 6:
      {
          reverse();
          display();
          break;
      }

      case 7:
      {
          int num;
          printf(" \nEnter the number to be deleted from List: ");
          scanf("%d",&num);
          delNodeData(num);
          display();
          break;
      }

      case 8:
      {
          int num;
          printf(" \nEnter the location of the node to \
          be deleted from List: ");
          scanf("%d",&num);
          delNodeLoc(num);
          display();
          break;
      }

      case 9:
      {
          struct Node *temp;

          while(Head!=NULL)
          {
              temp = Head->Next;
              free(Head);
              Head=temp;
          }
          exit(0);
      }

      default:
      {
          printf("\nWrong Option choosen");
      }
    }/* end if switch */
 }/* end of while */
}/* end of main */

12.17.2009

ctags - vim with steroids

Basically C/C++ projects have thousands of lines of code divided into hundreds in some cases thousands of files. Inorder to access various function definitions within the sourcecode repository effectively using a VIM editor there is a great need for using addons like ctags which provides easy code go through.

Eventhough there are many effective GUI based code editors like eclipse e.t.c I prefer to use VIM editor as my primary code editor. I am not much into GUI funda so still prefer basic editor like VIM.

1. Installing ctags package
Almost all the linux flavours with 2.6.X kernel might have ctags installed by default. If not download the appropriate .deb or rpm file. Sorry I am not dealing with installing of ctags as I havent came across this stage as I am using FEDORA 9.

2. Generating ctags on your source code.
We have to generate a file named 'tags' for all the source code files, use the following command:
ctags *.c *.h
When we have many files in many directories then we have to create a tags file in each of the directories. But VIM will only be able to jump to tags within the same directory. To find more tags files, we have to set the 'tags' option in VIM to include all the relevant tags files. Just set the following command in ~/.vimrc file.
:set tags=./tags,./../tags,./*/tags
This finds a tags file in the same directory as the current file, one directory level higher and in all subdirectories.

But VIM searching many places for tags files is not really robust enough as it may get a bit slow. It's better to generate one big tags file offcourse it takes more time to create a single tags files for whole project. Just give the following command to recursively add all files in your project.
$ cd /proj 
$ ctags -R *
-R is to recursively go across all the directories, and a ‘tags’ file will be created including all the files in the sub-directories also.

Now we can simply include this single tags files as shown below
:set tags=~/proj/tags
3. Start using ctags with VIM editor
We have 3 different ways to use ctags in VIM editor.

From Shell:
We can invoke directly the file or the files containing the definition for a particular function from shell.
vi -t function_name
This will find the correct file or list of files having function_name definition.

OR

VIM command line:
We can invoke from VIM commandline (in command mode) the definition of a function.
:tag function_name
or
:ta function_name
This will jump automatically from the current file to the file containing the function_name definition.

OR

By cursor position:
This option is more user-friendly as we use a key combination instead of giving commands.
ctrl + ]
Place the cursor on the first character of the function name and press ctrl-]. This will jump to the file containing the definition of function_name.
ctrl + t
This command will jump back to previous location.
ctrl + i
To travel forward through the tag history.
ctrl + o
To travel backward through the tag history.

History
To display the list of tags that we have traversed in past give the following command.
:tags
Shows tag stack (history).

Divide and Conquer
As we saw already 'ctrl + ]' replaces the file in the current window with the one containing the new function. But suppose if we want to see not only the old function but also the new one?

We can split the window using the ":split" command followed by the ":tag" command.
:stag function_name
Cursor command for above feature is
ctrl + w + ]
Auto Complete
VIM supports tag name completion. Start typing the tag name (i.e. function name) and then hit TAB key and name completion will be done automatically if there is a tag name.
:tag start-of-tag-name_TAB
Jump to a tag name found by a search.
:tag /search-string
When multiple entries exist in the tags file, such as a function declaration in a header file and a function definition (the function itself), the operator can choose by issuing this command. The user will be presented with all the references to the function and the user will be prompted to enter the number associated with the appropriate one.
:tselect function-name
Jumps to next matching tag.
:tnext
or
:tn
Jump to previous matching tag.
:tprevious
or
:tp
Jump to first matching tag.
:tfirst
or
:tf
or
:trewindor:tr
Jump to last matching tag.
:tlast
or
:tl
Finding global identifiers
You are editing a C program and wonder if a variable is declared as "int" or "unsigned". A quick way to find this is with the "[I" command. Suppose the cursor is on the word "column" then type
[ + shiftkey + i
Vim will list the matching lines it can find. Not only in the current file,
but also in all included files (and files included in them, etc.). The result
looks like this:

structs.h
1: 29 unsigned column; /* column number */
The advantage over using tags or the preview window is that included files are
searched. In most cases this results in the right declaration to be found.
Also when the tags file is out of date. Also when you don't have tags for the
included files.

However, a few things must be right for "[I" to do its work. First of all,
the 'include' option must specify how a file is included. The default value
works for C and C++. For other languages you will have to change it.

Reference:
ctags documentation

9.08.2009

Reading a string of length 'n' from Standard Input [STDIN]

We know how to read a string from STDIN in C by using library functions like scanf, fgets and so on. By using these functions there is a chance for memory corruption and strange behaviour. For example while using scanf if we try to save a string of length more than the variable size there is a chance of memory corruption.

So here in this post I am just trying to implement a function capable to read a string of length 'n' from STDIN without memory corruption and other bugs.

Do help me by checking the code if there is a chance for further improvements.

#include <stdio.h>
#include <string.h>

#define BUF_SIZE 6
#define STRING_SIZE 4

/*
* void getStringStdin(char *, int , int );
*
* 1: BUF :Pointer to the array of characters where input string
is to be stored.
* 2: BUF_LEN :Is the length of the array of characters where the
string is stored.buffer where we save the string.
* 3: STRING_LEN :Is the length of the string.
*
* NOTE: STRING_LEN < BUF_LEN
*
*/

getStringStdin(char *buf, int buf_len, int str_len)
{
int ch, len;
char *s;

if(str_len>=buf_len)
len=buf_len-1;
else
len=str_len;

printf ("\nEnter string of length %d(Remaining is ignored): ",len);

if( (fgets(buf, len+1, stdin)) != NULL )
{
s=my_strchr(buf,'\n');

if(s!=NULL)
{
*s='\0';
}
else
{
while ((ch = getchar()) != '\n' && ch != EOF);
}
}
}

int main(void)
{
int i=0;
char buf[BUF_SIZE];

do
{
getString(buf, BUF_SIZE, STRING_SIZE);
printf ("\nString : %s\n", buf);
i++;
}while(i<2);

return 0;
}

8.26.2009

Implementation of Singly Linked List

This article is part of article series - "Datastructures"

Generally a Linked List means "Singly Linked List". It is a chain of records known as Nodes. Each node has at least two members, one of which points to the next Node in the list and the other holds the data.

Figure 1: Singly Linked List
Basically Single Linked Lists are uni-directional as they can only point to the next Node in the list but not to the previous. We use below structure for a Node in our example.
 struct Node
 {
   int Data;
   struct Node *Next;
 }; 
Variable Data holds the data in the Node (It can be a pointer variable pointing to the dynamically allocated memory) while Next holds the address to the next Node in the list.

Figure 2: Node in a Singly Linked List
Head is a pointer variable of type struct Node which acts as the Head to the list. Initially we set 'Head' as NULL which means list is empty.

7.30.2009

Mysterious C program

Never thought in my life that one can write such a mysterious 'C' program which compiles without any errors and provides a strange output.

#include <stdio.h>

main(t,_,a)
char *a;
{return!0<t?t<3?main(-79,-13,a+main(-87,1-_,
main(-86, 0, a+1 )+a)):1,t<_?main(t+1, _, a ):3,main ( -94, -27+t, a
)&&t == 2 ?_<13 ?main ( 2, _+1, "%s %d %d\n" ):9:16:t<0?t<-72?main(_,
t,"@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+\
,/+#n+,/#;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/\
+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# ){n\
l]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#\
n'wk nw' iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \
;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;\
#'rdq#w! nr'/ ') }+}{rl#'{n' ')# }'+}##(!!/")
:t<-50?_==*a ?putchar(a[31]):main(-65,_,a+1):main((*a == '/')+t,_,a\
+1 ):0<t?main ( 2, 2 , "%s"):*a=='/'||main(0,main(-61,*a, "!ek;dc \
i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"),a+1);}
Any Clue of the output ???

Output for the above code is

On the first day of Christmas my true love gave to me
a partridge in a pear tree.

On the second day of Christmas my true love gave to me
two turtle doves
and a partridge in a pear tree.

On the third day of Christmas my true love gave to me
three french hens, two turtle doves
and a partridge in a pear tree.

On the fourth day of Christmas my true love gave to me
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the fifth day of Christmas my true love gave to me
five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the sixth day of Christmas my true love gave to me
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the seventh day of Christmas my true love gave to me
seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the eighth day of Christmas my true love gave to me
eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the ninth day of Christmas my true love gave to me
nine ladies dancing, eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the tenth day of Christmas my true love gave to me
ten lords a-leaping,
nine ladies dancing, eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the eleventh day of Christmas my true love gave to me
eleven pipers piping, ten lords a-leaping,
nine ladies dancing, eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.

On the twelfth day of Christmas my true love gave to me
twelve drummers drumming, eleven pipers piping, ten lords a-leaping,
nine ladies dancing, eight maids a-milking, seven swans a-swimming,
six geese a-laying, five gold rings;
four calling birds, three french hens, two turtle doves
and a partridge in a pear tree.
Can anyone explain me step by step way the process to get above output ....

2.17.2009

Gcov - analyzing code produced with GCC

How can a programmer exactly know which part of his code is frequently executed and which part of code is never traversed ? That's where CODE COVERAGE comes for rescue ...

Code Coverage is a measure used in software testing to describe the degree to which the source code of a program has been tested. It is a form of testing that inspects the code directly and checks the active and non-active parts of the source-code.

Basically there are number of code coverage criteria, the main ones being:
  • Function coverage
  • Has each function in the program been executed?

  • Statement coverage
  • Has each line of the source code been executed?

  • Decision coverage (also known as Branch coverage)
  • Has each control structure (such as an if statement) evaluated both to true
    and false?

  • Condition coverage
  • Has each boolean sub-expression evaluated both to true and false (this does
    not necessarily imply decision coverage)?

  • Modified Condition/Decision Coverage (MC/DC)
  • Has every condition in a decision taken on all possible outcomes at least
    once? Has each condition been shown to affect that decision outcome
    independently?

  • Path coverage
  • Has every possible route through a given part of the code been executed?

  • Entry/exit coverage
  • Has every possible call and return of the function been executed?

9.16.2008

Client Server example with PIPES

This example shows a combined use of unnamed and named pipes to produce a client–server relationship. Let us discuss first about the PROBLEM we are going to try.

There is a single Server process which runs continuously in background eventhough if there is no client to interact with it. Client processes runs in foreground and interacts with the server process. Both the client and server processes will run on the same machine (So server process will run background forever until it is manually killed).

The Client process accepts a command (probably a shell command) from the user and send's it to the Server via a FIFO which is a public channel between Client and Server for processing. Let us name this FIFO as PUBLIC fifo since its existence is known to all clients and the server. Once the command is received, the Server executes it using the popen–pclose sequence (which generates an unnamed pipe in the Server process). After execution Server process should return the output of the command executed to the client over a FIFO which is a private channel between the client and server. Let us name this FIFO as PRIVATE fifo. The Client, upon receipt, displays the output on the screen.

NOTE: Each and every Client process should have its own unique PRIVATE fifo to receive information from Server.

Check out the diagrammatic representation of the PROBLEM.


To ensure that both Server and Client processes use the same PUBLIC fifo name and have the same message format for the data sent through the FIFO, a local header file named local.h is created.
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <linux/limits.h>
#include <string.h>
#include <stdio.h>

#define B_SIZE (PIPE_BUF/2)

const char *PUBLIC = "/tmp/PUBLIC";

struct message {
char fifo_name[B_SIZE];
char cmd_line[B_SIZE];
};

The format of the message sent over the PUBLIC fifo is declared within the struct statement. The message structure consists of two character array's namely fifo_name, stores the name of the PRIVATE fifo of the Client process and cmd_line, stores the command to be executed by the Server.

Let us checkout the functionality steps of a newly created Client process.
  [1].  Create a unique name for the PRIVATE fifo and invoke it.
  [2].  Open the PUBLIC fifo in write mode.
  [3].  Prompt for command from user.
  [4].  Write command to PUBLIC fifo for Server to process.
  [5].  Open PRIVATE fifo in read mode to read the contents from Server..
#include "local.h"
int main()
{
int publicfifo, privatefifo, n;
static char buffer[PIPE_BUF];
struct message msg;

/*Using sprintf to create a unique fifo name
and save into message structure*/
sprintf(msg.fifo_name, "/tmp/fifo%d", getpid());

/*Creating the PRIVATE fifo*/
if(mknod(msg.fifo_name, S_IFIFO | 0666, 0) < 0) {
  perror(msg.fifo_name);
  exit(1);
}

/*Opening PUBLIC fifo in WRITE ONLY mode*/
if((publicfifo = open(PUBLIC,O_WRONLY)) < 0) {
  unlink(msg.fifo_name);
  perror(PUBLIC);
exit(1);
}

while(1) {

  write(fileno(stdout), "\n cmd>", 6);
  memset(msg.cmd_line, 0x0, B_SIZE);
  n = read(fileno(stdin), msg.cmd_line, B_SIZE);

if(strncmp("quit", msg.cmd_line, n-1) == 0) {
  break;
}

write(publicfifo, &msg, sizeof(msg));

if((privatefifo = open(msg.fifo_name, O_RDONLY)) < 0) {
  printf("1\n");
  perror(msg.fifo_name);
  goto CLEANUP;
}

while((n = read(privatefifo, buffer, PIPE_BUF)) > 0) {
  write(fileno(stderr), buffer, n);
}

close(privatefifo);
}

CLEANUP:
close(publicfifo);
unlink(msg.fifo_name);

return 0;
}

Now we will check the Server process.
  [1].  Generate a PUBLIC fifo and open it in both read and write mode. Wait for the message from a Client process.
  [2].  Read the message from PUBLIC fifo.
  [3].  Open the Client's PRIVATE fifo in write mode.
  [4].  Execute the command from Client process using popen.
  [5].  Write the output into Client's PRIVATE fifo.
#include "local.h"

int main() {

int privatefifo, dummyfifo, publicfifo, n, done;
struct message msg;
FILE *fin;
static char buffer[PIPE_BUF];

/*creating the PUBLIC fifo*/
mknod(PUBLIC, S_IFIFO | 0666, 0);

/*
Server process opens the PUBLIC fifo in write mode to make sure that
the PUBLIC fifo is associated with atleast one WRITER process. As a
result it never receives EOF on the PUBLIC fifo. The server process
will block any empty PUBLIC fifo waiting for additional messages to
be written. This technique saves us from having to close and reopen
the public FIFO every time a client process finishes its activities.
*/

if( (publicfifo = open(PUBLIC, O_RDONLY)) < 0 ||
(dummyfifo = open(PUBLIC, O_WRONLY | O_NDELAY)) < 0) {
   perror(PUBLIC);
   exit(1);
}

/*Read the message from PUBLIC fifo*/
while(read(publicfifo, &msg, sizeof(msg)) > 0) {

n=0;
done=0;

do {
  if((privatefifo = open(msg.fifo_name, O_WRONLY|O_NDELAY)) == -1) {
    sleep(5);
  }
  else {
    fin = popen(msg.cmd_line, "r");
    write(privatefifo,"\n",1);

    while((n= read(fileno(fin), buffer, PIPE_BUF)) > 0) {
      write(privatefifo, buffer, n);
      memset(buffer, 0x0, PIPE_BUF);
    }

    pclose(fin);
    close(privatefifo);
    done = 1;
  }
}while(n++ < 5 && !done);

if(!done) {
  perror("Not accessed the private fifo\n");
  exit(1);
}

}
return 0;
}

Compile server.c and client.c and generate server, client executable's. A sample execution of the client-server programs is shown below

[bash]$./server &                                  
[1] 27107

[bash]$./client
cmd>ps
PID TTY TIME CMD
14736 pts/3 00:00:00 csh
27107 pts/3 00:00:00 server
27108 pts/3 00:00:00 client
27109 pts/3 00:00:00 6
cmd>who
gray pts/3 Feb 27 11:28
cmd>quit

$./kill -9 27107
[1] Killed server
$

6.16.2008

Calculate Time in Linux

Calculating time in LINUX in milliseconds and Seconds. We should include sys/time.h header file and the remaining sample code is

struct timeval start;

we wil be using gettimeofday system call whose syntax is
int gettimeofday(struct timeval *tv, struct timezone *tz); where

struct timeval
{
time_t tv_sec;···············/* seconds */
suseconds_t tv_usec;······/* microseconds */
};


/* To calculate time in seconds*/

gettimeofday(&start, NULL);
starttime = start.tv_sec + start.tv_usec/1000000;


/* To calculate time in milliseconds*/

gettimeofday(&start, NULL);
starttime = start.tv_sec*1000 + start.tv_usec/1000;