codingfreak

Displaying MATH formulas in blogger

noreply@blogger.com (Unknown) — Mon, 02 Dec 2013 11:38:00 +0000

Introducing math formulas in blogger was a daunting task in olden days. Now using Mathjax we can include them without any issue. Let us see steps to add support for Mathjax to blogger template.

1. In your blog default home page under "template" section select "Edit HTML" option. Add following line after <head> tag

<script type="text/javascript"
   src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

2. Now we can include math formulas as simple ASCII Math notation.

NOTE: We should use ∖( ...∖) for inline math and ∖[ ... ∖] for displayed math.

For inline math

To display $\left(x-1\right)\left(x+3\right) \sqrt{a^2+b^2}$ as inline formula

Similarly for displayed math

\[\sqrt{a^2+b^2}x = a_0 + \frac{1}x = a_0 + \frac{1}{\displaystyle a_1 + \frac{1}{\displaystyle a_2 + \frac{1}{\displaystyle a_3 + a_4}}}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + a_4}}}\]
References:

1. Mathjax
2. Online Latex Editor

Bubble Sorting

noreply@blogger.com (Unknown) — Mon, 04 Nov 2013 10:32:00 +0000

Bubble sort is one of the simple sorting algorithms and also popularly known as a Brute Force Approach. The logic of the algorithm is very simple as it works by repeatedly iterating through a list of elements, comparing two elements at a time and swapping them if necessary until all the elements are swapped to an order.

For e.g. if we have a list of 10 elements, bubble sort starts by comparing the first two elements in the list. If the second element is smaller than the first element then it exchanges them. Then it compares the current second element with the third element in the list. This continues until the second last and the last element is compared which completes one iteration through the list. By the time it completes the first iteration the largest element in the list comes to the rightmost position.

Image courtesy from Annieink.com

The algorithm gets its name as we start from lowest point and “bubble up” the higher elements to the highest point in the list. We can also follow other approach where we start from highest point and “bubble down” lowest elements in the list. Since it only uses comparisons to operate on elements, it is a comparison sort.

Graphical Example

As we can see in above example the list sorted by third iteration and it is useless to go for 4th and 5th iterations. So we use a flag which determines whether a swap operation is done in last iteration or not. If a swap operation is not done in last iteration we will stop remaining iterations since the list is already in sorted order. For the above example we will stop iterating once third iteration is done as the whole list is sorted by then.

Pseudo-code

procedure bubbleSort( A : list of sortable items )
   repeat     
     swapped = false
     for i = 0 to length(A) - 1 
       if A[i] > A[i+1] then
         swap( A[i], A[i+1] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

Code Snippet

void bubbleSort(int arr[], int numberOfElements) 
{
  char swapped = 1;
  int tmp, i;

  while (swapped) 
    {
      swapped = 0;

      for (i = 0; i < (numberOfElements - 1); i++) 
        {
          if (arr[i] > arr[i + 1]) 
            {
              tmp = arr[i];
              arr[i] = arr[i + 1];
              arr[i + 1] = tmp;
              swapped = 1;
            }
        }
    }
}

As we know, every iteration bubbles up the highest element to the end of the list. So there is no need to compare the same in next iteration. Above logic can be further enhanced by ignoring last n-1 elements when running for the nth iteration.

void bubbleSort(int arr[], int numberOfElements) 
{
  char swapped = 1;
  int numberOfElementsToSwap = numberOfElements;
  int tmp, i;

  while (swapped) 
    {
      swapped = 0;
      numberOfElementsToSwap = numberOfElementsToSwap - 1;

      for (i = 0; i < numberOfElementsToSwap; i++) 
        {
          if (arr[i] > arr[i + 1]) 
            {
              tmp = arr[i];
              arr[i] = arr[i + 1];
              arr[i + 1] = tmp;
              swapped = 1;
            }
        }
    }
}

Complexity Analysis

Worst case performance - $O(n^2)$
Best case performance - O(n)
Average case performance - $O(n^2)$
Worst case space complexity - O(1) auxiliary

Although bubble sort is one of the simplest sorting algorithms to understand and implement, its $O(n^2)$ complexity means that its efficiency decreases dramatically on lists of more than a small number of elements. Even among simple $O(n^2)$ sorting algorithms, algorithms like insertion sort are usually considerably more efficient.

Rabbits and turtles

The positions of the elements in bubble sort plays a large part in determining its performance. Large elements (Rabbits) at the beginning of the list do not pose a problem, as they are quickly swapped. But small elements (Turtle) towards the end, however, move to the beginning extremely slowly. This has led to these types of elements being named rabbits and turtles, respectively.

For e.g. In case of {2, 3, 4, 5, 1} list it takes a complexity of $O(n^2)$ to sort the list as smallest element (Turtle) 1 is at the end of the list while {6, 2, 3, 4, 5} list takes a complexity of $O(n)$ to sort the list.

Various efforts have been made to eliminate turtles to improve upon the speed of bubble sort. Cocktail sort achieves this goal fairly well, but it retains $O(n^2)$ worst-case complexity.

Reality of a Software Project

noreply@blogger.com (Unknown) — Wed, 14 Aug 2013 02:16:00 +0000

That's the reality I faced in real world crappy planning of Software Project. As a Developer we never have "FREE TIME" ..

Reality of a Software Project

How to narrate a story to computer scientist

noreply@blogger.com (Unknown) — Tue, 11 Jun 2013 02:10:00 +0000

If it brings back old memories or a smile then I hope you understood the characters in STORY.

Death of Google Reader - Journey towards alternatives

noreply@blogger.com (Unknown) — Sat, 16 Mar 2013 06:14:00 +0000

Flashback

Long Long ago when INTERNET is booming up with so many websites its really hard to follow the interesting one. Its quite clumsy to go around miliions of sites to check for new posts.

Am I Doomed ?

No, you are not. RSS feed mechanism is the answer.

Just follow the RSS feed of your favourite site and the RSS reader will maintain the unread articles, favourite articles and so on. Voilla simple and effective solution to follow various sites.

Which RSS reader to use ?

I started my journey with Google Reader just because

Service from GOOGLE (Truly .. those were the days everyone crazy to use Google Services. Even having a GMAIL account is symbol of techy saviness.)
Simplicity
Cleaner interface
Meets all my basic needs like tagging, starring, sharing
No extra signup trash (Just use your google account)

I am already using it for last 6 years and I simply love it. I have around 1000+ subscriptions on various topics in it.

Present

As part of cleanup process which GOOGLE follows for its services they decided to ditch Google reader with only reason saying - it doesnt meets their expectation. Being a Loyal user of Google from last 6 years I have really lost my trust on them when they scrapped Google Reader. I really need to think alternatives for their services.

Uproar started every where as users backlashed at google's decision in various popular social networking sites. Even I am one among them. Nothing can be done but looking for alternatives.

Future

Before I really jump into alternatives for Google reader I decided to sort down my requirements.

Web based RSS reader like Google Reader not a application only one. Its main advantage is I can read from anywhere from browser.
Simple, Cleaner Interface.
Support 1000+ subscriptions.
Tagging of Feeds.
Support for various views like List view, Expanded view, Full view so on.
Automatic marking of items as read as they are scrolled past. This option really helps in marking posts as read the moment we scroll past them.
Sharing options with various social networking sites (Not so mandatory).
Free Service.
Extra goodies

Alternatives I am gonna try

1. Feedly

Quite popular among the alternatives I decided to start with Feedly. Feedly already started to face huge traffic from users migrating from Google Reader as they promise to provide seamless migration for Google Reader users. Just signup with your google account and all your feeds are imported automatically.

Important Tips for users migrating from Google Reader to Feedly is shared in their Blog Link. These tips are really helpful.Even though initial look is clumsy we can customize it in preferences tab making it look simple and cleaner as shown below.

Pros:

Simple, Cleaner Interface
Transition from Google Reader is very simple.
Meets all my requirements mentioned above.
Web Based RSS reader and even supports apps for various platforms.
Support cleaner background themes option.
Save option is really helpful to check the old and interesting articles later.

Cons:

None currently.

I would highly recommend this service for google readers as you gonna feel back home.I would call Feedly as Google Reader on steroids.

Eventhough I am very happy with Feedly I decided to try other popular services available.

2. Bloglovin

A simple signup procedure which accepts your Facebook account or Email sign-up. Once sign-up is done it asks for importing feeds from Google reader making transition from Google Reader very simple.

Pros:

Simple, Cleaner interface.
Transition from Google Reader is very simple.
Creates personal profile.

Cons:

Only supports magazine view.
No support for automatic marking of items as read as they are scrolled past.
No Tagging option.
Very basic sorting option.

3. Netvibes

Netvibes is a personalized dashboard publishing platform like iGoogle. It provides simple signup procedure which accepts your Facebook account or Email sign-up. Once signed-in initial feel is just like iGoogle service with its widgets look of various sites.

Steps for importing feeds from Google Reader to netvibes is shared in their blog link.

Pros:

Simple, Cleaner Interface.
Support various options like iGoogle service.

Cons:

Its a dashboard publishing service. I just need a RSS reader.
Free edition doesn't support automatic marking of items as read as they are scrolled past.
Premium Services at whopping 499$/month. Are you kidding me lol.

4. Feedspot

After simple signup procedure users are provided with a link to transition feeds from Google Reader.

Pros:

Simple, Cleaner interface.
Easy transition of feeds from Google Reader.

Cons:

Doesn't support automatic marking of items as read as they are scrolled past.

Divide a number by 3 without using any arithmetic operators

noreply@blogger.com (Unknown) — Thu, 14 Mar 2013 04:35:00 +0000

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;
}

Above solution is a bit tricky so let us simplify it

Open a temporary file i.e. temp.dat in write mode.
Allocate a temporary "buf" of size "number".
Now fwrite writes "number" of bytes from "buf" into FILE STREAM "fp". (In the above code since the value of "number" variable is 12346, we write 12346 bytes from "buf" into "temp.dat" file).
rewind will reset the file pointer "fp" to the start of the file.
fread reads "number" of elements of data, each "divisor" bytes long, from FILE STREAM "fp" and writes into "buf". Hence the return value of fread is 4115 in the above example. If you write 30 bytes and read back from the file in units of 3 then fread returns 10 which equivalent to 30 / 3.

Solution 02:

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

int main(int argc, char *argv[])
{
    int num = 1234567;
    int den = 3;
    div_t r = div(num,den); // div() is a standard C function.
    printf("%dn", r.quot);

    return 0;
}

Solution 03:

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

int add(int x, int y) {
  int a, b;
  do {
    a = x & y;
    b = x ^ y;
    x = a << 1;
    y = b;
  } while (a);
  return b;
}

int divideby3 (int num) {
  int sum = 0;
  while (num > 3) {
    sum = add(num >> 2, sum);
    num = add(num >> 2, num & 3);
  }
  if (num == 3)
    sum = add(sum, 1);
  return sum;   
}

int main()
{
  int number=30;

  printf("%d n", divideby3(number));
  return 0;
}

References:

Stackoverflow.

Checking Balance of Symbols in a expression

noreply@blogger.com (Unknown) — Wed, 13 Mar 2013 16:49:00 +0000

This article is part of article series - "Datastructures"

A balanced expression contains right number of closing and open braces.

For example:

[[ - unbalanced expression
[]{}() - balanced expression
[(*)] - balanced expression

Let us see how to find if an expression is balanced or not by checking for following operators [ ] { } and ( ) in the given expression.

Using Stacks

Pseudocode:

We divide [ , ] , { , } , ( , ) operators into LEFT and RIGHT sets where LEFT set contains ( , { , [ operators while RIGHT set contains ) , } , ] operators. So we have a one to one mapping between RIGHT and LEFT set operators i,e

{ --- }
[ ---]
( --- )

NOTE: Stack related operations like create stack, delete stack, push into stack and pop from stack are considered generic and we are not including its logic in below pseudocode.

********************************************************
 Function  : isExprBalanced 

 Calls     : popFromStack 

 Called by : main

 Input 
 Parameters: stack, var
  
 Returns   : balanced : TRUE 
             unbalanced: FALSE
********************************************************

CASE var

  ')' : IF stackTop equals '(' THEN
          CALL popFromStack (stack)
          RETURN TRUE
        ENDIF

  '}' : IF stackTop equals '{' THEN
          CALL popFromStack (stack)
          RETURN TRUE
        ENDIF

  ']' : IF stackTop equals '[' THEN
          CALL popFromStack (stack)
          RETURN TRUE
        ENDIF
  
ENDCASE

RETURN FALSE

********************************************************
 Function  : main

 Calls     : createStack
             isExprBalanced              
             pushIntoStack 
             popFromStack 

 Called by : NONE 

 Input 
 Parameters: Accepts input expression for processing
  
 Returns   : If input expression is balanced or not.
********************************************************

SET i to 0
GET input expression from user into input[20]
SET var with input[i]

CALL createStack

WHILE var != end of string

  IF var belongs to (RIGHT set) THEN

    CALL isExprBalanced (stack,var)

    IF not balanced THEN
      PRINT expression is not balanced
      RETURN
    ENDIF 

  ELSE IF var belongs to (LEFT set) THEN

    CALL pushIntoStack (stack,var)

  ENDIF

  SET var with input[INCREMENT i]

ENDWHILE

IF stack is empty THEN
  PRINT expression is balanced
ELSE
  PRINT expression is un-balanced
ENDIF

CALL freeStack (stack)

Complexity:

TIme Complexity: O(n)
Space Complexity: O(n)

Sample Code:

stackSLL.h

#define MAX_STACK_SIZE 10
#define RESULT_ERROR -1
#define RESULT_OK     0

struct sllNode
{
  struct sllNode *next;
  int data;
};

struct sllHead
{
  struct sllNode *next;
  u_int32_t count;
  u_int32_t maxStackSize;
};

#define IS_RIGHT(_i)  ((_i == ')') || (_i == '}') || (_i == ']'))

#define IS_LEFT(_i)  ((_i == '(') || (_i == '{') || (_i == '['))

stackSLL.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stackSLL.h"

/*Poping from a Stack*/
int
popFromStack(struct sllHead *head)
{
  struct sllNode *tmpNode_ptr = NULL;

  if (!head)
  {
    return RESULT_ERROR;
  }

  if (head->next)
  {
    tmpNode_ptr = head->next;
    head->next = head->next->next;
    free(tmpNode_ptr);
    head->count--;
  }    
  else  
    printf("Stack is Empty\n");

  return RESULT_OK;
} 

/*Pushing into Stack*/
int
pushIntoStack(struct sllHead *head, int data)
{
  struct sllNode *tmpNode_ptr = NULL;

  if (!head)
  {
    return RESULT_ERROR;
  }

  if (head->count == head->maxStackSize)
  {
    printf ("Stack is FILLED to MAX level\n");
    return RESULT_ERROR;
  }

  tmpNode_ptr = (struct sllNode *)calloc(1, sizeof(struct sllNode));

  if (tmpNode_ptr)
    tmpNode_ptr->data = data;
  else
  {
    printf("Memory Allocation Failedn");
    return RESULT_ERROR;
  }

  tmpNode_ptr->next = head->next;
  head->next = tmpNode_ptr;
  head->count++;

  return RESULT_OK;
}

struct sllHead *
createStack()
{
  struct sllHead *head = struct sllHead *)calloc(1, sizeof(struct sllHead));

  if (head)
    head->maxStackSize = MAX_STACK_SIZE;

  return head;
}

void
freeStack(struct sllHead **head)
{
  if (*head)
  {
    while((*head)->count)
      popFromStack(*head);

    free(*head);
    *head = NULL;
  }
}

int
isExprBalanced (struct sllHead *head, char val)
{
  if (head == NULL || head->next == NULL)
    return RESULT_ERROR;

  if (!IS_RIGHT(val))
    return RESULT_ERROR;

  switch(val)
  {
    case ')':
      if (head->next->data == '(')
      {
        popFromStack(head);
        return RESULT_OK;
      }
    break;

    case '}':
      if (head->next->data == '{')
      {
        popFromStack(head);
        return RESULT_OK;
      }
    break;

    case ']':
      if (head->next->data == '[')
      {
        popFromStack(head);
        return RESULT_OK;
      }
    break;
  }

  return RESULT_ERROR;
}

int
main(int argc, char *argv[])
{
  char in[20];
  short i = 0;
  struct sllHead *stack = NULL;

  memset(in, 0, 20);

  printf("Enter expression containing ( { [ ) { ]: ");
  scanf("%s", in);

  stack = createStack();

  while(i < 20 && in[i] != '\0')
  {
    if (IS_RIGHT(in[i]))
    {
      if (isExprBalanced(stack, in[i]) != RESULT_OK)
      {
        printf("Expression is not balanced\n");
        goto EXIT;
      }
    }
    else if (IS_LEFT(in[i]))
    {
      if (pushIntoStack(stack, in[i]) == RESULT_ERROR)
        goto EXIT;
    }

  if (stack->count)
    printf ("Expression is not balanced\n");
  else
    printf ("Expression is balanced\n");

EXIT:

  freeStack (&stack);

  return RESULT_OK;
}

Conversion from Infix to Postfix

noreply@blogger.com (Unknown) — Tue, 05 Feb 2013 10:42:00 +0000

This article is part of article series - "Datastructures"

Converting a Fully Parenthesized Infix expression into Postfix expression

Analysis:

Five types of input characters

Opening parentheses
Operands
Operators
Closing parentheses
New line character (\n)

Pseudocode:

********************************************************  
 Function  : main  
  
 Calls     : createStack  
             freeStack                
             pushIntoStack   
             popFromStack   
  
 Called by : NONE   
  
 Input   
 Parameters: Accepts input expression for processing  
    
 Returns   : Converts Fully paranthesized INFIX 
             expression into POSTFIX expression
******************************************************** 

SET i to 0
GET infix expression from user into input_array
SET var with input_array[i]

CALL createStack

WHILE var != end of string

  IF var equals to '(' THEN
  
    CALL pushIntoStack (stack, var)  

  ELSE IF var is a number THEN        
  
    PRINT var  

  ELSE IF var is an arithmetic operator THEN
  
    CALL pushIntoStack (stack, var) 
    
  ELSE IF var equals to ')' THEN

    WHILE stackTop != '('

      IF stackTop is an arithmetic operator THEN

        PRINT stackTop
        popFromStack (stack)

      ENDIF
    
    ENDWHILE

    popFromStack (stack)

  ENDIF

  SET var with input_expression[INCREMENT i]

ENDWHILE

CALL freeStack (stack)

Complexity:

Time Complexity: O(n)
Space Complexity: O(n)

Explanation:

We will try out above pseudocode with input expression - (((8+1)-(7-4))/(11-9))

Input	Operation	Stack (after op)	Output on monitor
(	Push operand into stack	(
(	Push operand into stack	( (
(	Push operand into stack	( ( (
8	Print it		8
+	Push operator into stack	( ( ( +	8
1	Print it		8 1
)	Pop from the stack: Since popped element is '+' print it	( ( (	8 1 +
	Pop from the stack: Since popped element is '(' we ignore it and read next character	( (	8 1 +
-	Push operator into stack	( ( -
(	Push operand into stack	( ( - (
7	Print it		8 1 + 7
-	Push the operator in the stack	( ( - ( -
4	Print it		8 1 + 7 4
)	Pop from the stack: Since popped element is '-' print it	( ( - (	8 1 + 7 4 -
	Pop from the stack: Since popped element is '(' we ignore it and read next character	( ( -
)	Pop from the stack: Since popped element is '-' print it	( (	8 1 + 7 4 - -
	Pop from the stack: Since popped element is '(' we ignore it and read next character	(
/	Push the operand into the stack	( /
(	Push into the stack	( / (
11	Print it		8 1 + 7 4 - - 11
-	Push the operand into the stack	( / ( -
9	Print it		8 1 + 7 4 - - 11 9
)	Pop from the stack: Since popped element is '-' print it	( / (	8 1 + 7 4 - - 11 9 -
	Pop from the stack: Since popped element is '(' we ignore it and read next character	( /
)	Pop from the stack: Since popped element is '/' print it	(	8 1 + 7 4 - - 11 9 - /
	Pop from the stack: Since popped element is '(' we ignore it and read next character	Stack is empty
New line character	STOP

Sample Code:

stack01.h

#define MAX_ARRAY_SIZE 50
#define MAX_STACK_SIZE 10
#define RESULT_ERROR -1
#define RESULT_OK     0

struct sllNode
{
  struct sllNode *next;
  char data;
};


struct sllHead
{
  struct sllNode *next;
  u_int32_t count;
  u_int32_t maxStackSize;
};

#define IS_ARITHMETIC_OPERATOR(_i)                                          
   ((_i == '*') || (_i == '+') || (_i == '-') || (_i == '/') || (_i == '%'))

#define IS_OPERAND(_i)                                                      
   ( (_i >= '0' && _i <= '9') ||                                            
     (_i >= 'a' && _i <= 'z') ||                                            
     (_i >= 'A' && _i <= 'Z'))

#define IS_STACK_EMPTY(_stack)  ((_stack) ? _stack->count : 0)    

#define STACK_TOP(_stack) ((_stack) ?                                       
                           ((_stack->next) ?                                
                            (_stack->next->data) : 0) : 0)

stack01.c

/*FULLY PARANTHESIZED INFIX to POSTFIX*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack01.h"

/*Poping from a Stack*/
int popFromStack(struct sllHead *head)
{
  struct sllNode *tmpNode_ptr = NULL;

  if (!head)
  {
    return RESULT_ERROR;
  }

  if (head->next)
  {
    tmpNode_ptr = head->next;
    head->next = head->next->next;
    free(tmpNode_ptr);
    head->count--;
  }    
  else  
   printf("Stack is Emptyn");

  return RESULT_OK;
}   

/*Pushing into Stack*/
int pushIntoStack(struct sllHead *head, char data)
{
  struct sllNode *tmpNode_ptr = NULL;

  if (!head)
  {
    return RESULT_ERROR;
  }

  if (head->count == head->maxStackSize)
  {
    printf ("Stack is FILLED to MAX leveln");
    return RESULT_ERROR;
  }

  tmpNode_ptr = (struct sllNode *)calloc(1, sizeof(struct sllNode));

  if (tmpNode_ptr)
    tmpNode_ptr->data = data;
  else
  {
    printf("Memory Allocation Failedn");
    return RESULT_ERROR;
  }

  tmpNode_ptr->next = head->next;
  head->next = tmpNode_ptr;
  head->count++;

  return RESULT_OK;
}

struct sllHead * createStack()
{
  struct sllHead *head = NULL;
  head = (struct sllHead *)calloc(1, sizeof(struct sllHead));
  if (head)
    head->maxStackSize = MAX_STACK_SIZE;

  return head;
}

void freeStack(struct sllHead **head)
{
  if (*head)
  {
    while((*head)->count)
      popFromStack(*head);

    free(*head);
    *head = NULL;
  }
}

int main(int argc, char *argv[])
{
  char in[MAX_ARRAY_SIZE];
  short i = 0;
  struct sllHead *stack;
  u_char operand_before = 0;

  memset(in, 0, MAX_ARRAY_SIZE);

  printf("Enter INFIX expression : ");
  scanf("%s", in);

  stack = createStack();

  while(i < MAX_ARRAY_SIZE && in[i] != '\0')
  {
    if (in[i] == '(' ||
        IS_ARITHMETIC_OPERATOR(in[i]))
    {
      pushIntoStack (stack,in[i]);
      operand_before = 0;
    }
    else if (IS_OPERAND(in[i]))
    {
      if (operand_before)
      printf ("%c", in[i]);
      else
      printf (" %c", in[i]);

      operand_before = 1;
    }
    else if (in[i] == ')')
    {
      operand_before = 0;
      while (IS_STACK_EMPTY(stack) &&
             STACK_TOP(stack) != '(')
      {
        if (IS_ARITHMETIC_OPERATOR(STACK_TOP(stack)))
        {
          printf(" %c", STACK_TOP(stack));
          popFromStack(stack);
        }
      }

      if (STACK_TOP(stack) == '(')
        popFromStack(stack);
    }

    i++;
  }

  printf ("\n");

EXIT:

  freeStack (&stack);

  return RESULT_OK;
}

References:

wikipedia

Deleting a Node from a Singly Linked List

noreply@blogger.com (Unknown) — Tue, 25 Dec 2012 12:55:00 +0000

This article is part of article series - "Datastructures"

Previous Article: Implementation of Singly Linked List.
Next Article: Reversing a Singly Linked List

Deletion of a Node from a Singly Linked List
Similar to insertion we have three cases for deleting a Node from a Singly Linked List.

Deleting First Node in Singly Linked List

To complete deletion of firstNode in the list we have to change Head pointing to Next of firstNode.

Pseudocode:

firstNode = Head

Head = firstNode->Next

free firstNode

Complexity:
Time Complexity: O(1)
Space Complexity: O(1)

Sourcecode:

 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 Last Node in the Singly Linked List

Traverse to Last Node in the List using two pointers namely prevNode and curNode. Once curNode reaches the last Node in the list point Next in prevNode to NULL and free the curNode.

Pseudocode:
```
curNode = head

forever:

 if curNode->Next == NULL
 break

 prevNode = curNode
 curNode = curNode->Next

prevNode->Next = NULL

free curNode
```
Complexity:
Time Complexity: O(n)
Space Complexity: O(1)

Deleting Node from position 'p' in the List

To delete a Node at the position 'p' we have to first traverse the list until we reach the position 'p'. For this case have to maintain two pointers namely prevNode and curNode. Since Singly Linked Lists are uni-directional we have to maintain the information about previous Node in prevNode. Once we reach the position 'p' we have to modify prevNode Next pointing to curNode Next and free curNode.

Pseudocode:

curNode = head
curPos = 1

forever:

 if curPos == P || curNode == NULL
 break

 prevNode = curNode
 curNode = curNode->Next
 curPos++

if curNode != NULL:
 
 prevNode->Next = curNode->Next
 free curNode

Complexity:
Time Complexity: O(n) worst case
Space Complexity: O(3)

Sourcecode:

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;
 }

Previous Article: Implementation of Singly Linked List.
Next Article: Reversing a Singly Linked List

Detecting First Node in a Loop in the List

noreply@blogger.com (Unknown) — Tue, 25 Dec 2012 09:06:00 +0000

This article is part of article series - "Datastructures"

Previous Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.
Next Article: Finding Nth node from end of a Singly Linked List.

Once we confirm that there is a Loop in a Singly Linked List we will see how to determine first node of the loop.

Figure-1: Singly Linked list with a loop which we have detected using Floyd's Cycle Detection Algorithm

NOTE: Example in Figure-1 is the output of Floyd's Cycle detection Algorithm which we have seen in Floyd's Cycle Detection Algorithm. We are not randomly choosing Hare and Tortoise at Node-6.

Solution 01: Brute-force Approach

Start at the Head of the Singly Linked List (i.e. curNode).

If Tortoise and Hare are at the same Node move the curNode forward by one position.

If Tortoise and curNode are at the same Node return, we have found first Node in the loop.

Move Tortoise forward by one position and start with STEP-2.

Pseudocode:

curNode = head

forever:

  if tortoise == hare
    tortoise = tortoise.next
    curNode = curNode.next

  if tortoise == curNode
    return curNode

  tortoise = tortoise.next

Complexity:

Time Complexity: O(n*p) - where 'p' is the length of the loop and 'n' is the length of the List.
Space Complexity: O(1)

Example:

Let us try above algorithm on example in Figure-1.The pattern for Hare, Tortoise and Culprit is given below

Hare Tortoise Culprit
7        7            HEAD
7          8            1
7          3            1
7          4            1
7          5            1
7          6            1
7          7            1
7          8            2
7          3            2
7          4            2
7          5            2
7          6            2
7          7            2
7          8            3
7          3            3

Solution 02:

Let use see how to improve the Time Complexity of the solution 01.

But before we go into the solution I would like to mention that the below solution can be used only after detecting a loop in the singly linked list. As mentioned Figure-1 is the output of Floyd's cycle detection algorithm and we havent randomly choosen Node-7. As pointed out many users if we start from Node-6 we might end up in loop.

Start Tortoise at first node.

Move Hare and Tortoise by one position.

If Hare and Tortoise points to same node then return (its the first Node in the loop)

Start again from STEP-2

Pseudocode:

tortoise := firstNode

forever:

  if tortoise == hare
    return tortoise

  tortoise := tortoise.next
  hare := hare.next

Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

Example:

Let us try above algorithm on same example in Figure-1. Now let us start the Tortoise from the first node in the list.

The pattern for Hare and Tortoise is given below

Hare Tortoise
7        1
8          2
3          3

Previous Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.
Next Article: Finding Nth node from end of a Singly Linked List.

Finding Nth node from end of a Singly Linked List

noreply@blogger.com (Unknown) — Wed, 14 Nov 2012 04:17:00 +0000

This article is part of article series - "Datastructures"

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

Figure 1: Singly Linked List

Solution 01 - Brute Force Approach:

Start at First Node of the List (call it curNodePtr).
Assign curNodePtr to tmpPtr and count number of nodes after the curNodePtr.
If number of nodes after curNodePtr are equal to N nodes or tmpPtr reaches END then break. If tmPtr reaches END but count not equal to N then return since we can't find the Nth node from the end of the Singly Linked List.
Move the curNodePtr one step forward in the Linked List i.e curNodePtr now points to its next node in the list and start again from STEP-2.

Pseudocode:

curNodePtr := FirstNode

if curNodePtr == NULL
  return 'Less Nodes in the List'

forever:

  tmpPtr := curNodePtr
  count := 0

  forever:

    if tmpPtr == NULL || count == N
      break

    tmpPtr := tmpPtr.NEXT
    count++

  if tmpPtr == NULL
    if count == n
      return curNodePtr
    else
      return 'Less Nodes in the List'

  curNodePtr := curNodePtr.NEXT

Complexity:

Time Complexity: O(n^2) - For traversing each node after curNode.
Space Complexity: O(1)

Example:

Let us try above brute-force approach on example in Figure-1

Find 2nd Node: It returns Node 4.

curNode tmpNode Count
01    01    0
01    02    1
01                    03            2
02    02    0
02    03    1
02    04    2
03    03    0
03    04    1
03    05    2
04                    04            0
04                    05            1
04    NULL     2

Find 6th Node: It returns 'Less Nodes in the List'

curNode tmpNode Count
01    01    0
01    02    1
01    03    2
01    04    3
01    05    4
01    NULL     5

Solution 02:

Let us improve the time complexity when compared to Solution-01.

Find the length of the Singly Linked List (Let us say P).
If Length of the Singly linked List (P) is lesser than N return, since we can't find the Nth node from the end of the Singly Linked List.
If Length of the Singly Linked List (P) greater than N then compute (P-N+1) value, which points to Nth node from the end of Singly Linked List.
Traverse to (P-N+1)th Node in the Singly Linked List.

Pseudocode:

curNodePtr := FirstNode
P = 0

forever:

  if curNodePtr == NULL
    break

  P++
  curNodePtr := curNodePtr.NEXT

if P < N
  return 'Less Nodes in the List'

curNodePtr := FirstNode
count = 1

forever:

  if count == (P-N+1)
    return curNodePtr

  count++
  curNodePtr = curNodePtr.NEXT

Complexity:

Time Complexity: O(n) - Time for finding the length of a Singly Linked List O(n) + Time for finding (P-N+1) node in the List O(n) = O(n)
Space Complexity: O(1)

Solution 03:

Let us see one more simple and cleaner approach when compared to Solution 02 which doesn't need to traverse all nodes in the list twice to find the Nth node from the end of a Singly Linked List.

Let us take two pointers tmpPtr and nthNodePtr starting at the First Node of the Singly Linked List.
tmpPtr will start first by traversing N positions in the list. If it doesn't reach N positions from start of the singly linked list it means list is small. Return as we can't find the Nth node from the end of the list.
Once tmpPtr traverses N positions successfully nthNodePtr starts traversing along with tmpPtr one position forward until tmpPtr reaches the end of the List.
Once tmpPtr reaches end of the Singly Linked List nthNodePtr will be pointing to Nth node from the end of the Singly Linked List

Pseudocode:

tmpPtr := FirstNode
nthNodePtr := FirstNode
count := 1

forever:
  
  if count == N || tmpPtr == NULL
    break

  tmpPtr := tmpPtr.NEXT
  count++

if tmpPtr == NULL && count < N
  return 'Cannot find Nth element in the list'

tmpPtr := tmpPtr.NEXT

forever:

  if tmpPtr == NULL
    return nthNodePtr

  tmpPtr := tmpPtr.NEXT
  nthNodePtr := nthNodePtr.NEXT

Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

Example:

Let us try the above solution on example in Figure-1

Find 2nd Node from end of the List

tmpPtr nthNodePtr count
    1     1 1
    2     1 2
    3     1 -
    4     2 -
    5     3 -
    NULL    4 -

Reversing a Singly Linked List

noreply@blogger.com (Unknown) — Wed, 07 Nov 2012 04:24:00 +0000

This article is part of article series - "Datastructures"

Previous Article: Deleting a Node from a Singly Linked List.
Next Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.

Let us see how to reverse a Singly Linked List.

Figure-1: Singly Linked List

Pseudocode:

cur_ptr = HEAD->NEXT
prev_ptr = NULL

forever:

   if cur_ptr == NULL
   break

   tmp_ptr  = prev_ptr
   prev_ptr = cur_ptr
   cur_ptr  = cur_ptr->NEXT
   
   prev_ptr->NEXT = tmp_ptr

HEAD->NEXT = prev_ptr

Complexity:
Time Complexity: O(n)
Space Complexity: O(3)

If we try on the example in Figure-1 we get the output as shown below

Figure-2: After reversing the Singly Linked List

Previous Article: Deleting a Node from a Singly Linked List.
Next Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.

Detecting a Loop in Singly Linked List - Tortoise & Hare

noreply@blogger.com (Unknown) — Sat, 22 Sep 2012 06:07:00 +0000

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

Let us take 2 pointers namely slow Pointer and fast Pointer to traverse a Singly Linked List at different speeds. A slow Pointer (Also called Tortoise) moves one step forward while fast Pointer (Also called Hare) moves 2 steps forward

Start Tortoise and Hare at the first node of the List.
If Hare reaches end of the List, return as there is no loop in the list.
Else move Hare one step forward.
If Hare reaches end of the List, return as there is no loop in the list.
Else move Hare and Tortoise one step forward.
If Hare and Tortoise pointing to same Node return, we found loop in the List.
Else start with STEP-2.

Pseudocode:

tortoise := firstNode
hare := firstNode

forever:

  if hare == end 
    return 'No Loop Found'

  hare := hare.next

  if hare == end
    return 'No Loop Found'

  hare = hare.next
  tortoise = tortoise.next

  if hare == tortoise
    return 'Loop Found'

Why can't we let the Hare go by itself like Tortoise ?
If there is a loop, Hare would just go forever. Tortoise ensures that you will only take 'n' steps atmost.

How to find the length of the Loop ?
Once Hare and Tortoise finds the loop in a Singly linked List move Tortoise one step forward everytime maintaining the count of the nodes until it reaches the Hare again.

Example:

Singly Linked List with a Loop

Both Tortoise and Hare starts at First node of the list and Tortoise moves 1 step forward while Hare moves 2 steps forward.

Hare and Tortoise starts at First Node of the List

The pattern of Hare and Tortoise movements are shown below.

Hare   Tortoise
1          1
3          2
5          3
7          4
3          5
5          6
7          7

Both Hare and Tortoise meet up at Node 7. That proves there is a loop in the list

Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

To calculate the Time Complexity the shape of the cycle doesn't matter. It can have a long tail, and a loop towards the end or just a loop from the beginning to the end without a tail. Irrespective of the shape of the cycle, one thing is clear - that the Tortoise can never catch up with the Hare. If the two has to meet, the Hare has to catch up with the Tortoise from behind.

With that established, consider the two possibilities

Hare is one step behind Tortoise
Hare is two step behind Tortoise

All greater distances will reduce to One or Two. Let us assume always Tortoise moves first (it could be even other way).

In the first case were the distance between Hare and Tortoise is one step. Tortoise moves one step forward and the distance between Hare and Tortoise becomes 2. Now Hare moves 2 steps forward meeting up with Tortoise.

In the second case were the distance between Hare and Tortoise is two steps. Tortoise moves one step forward and the distance between Hare and Tortoise becomes 3. Now Hare moved 2 steps forward which makes the distance between Hare and Tortoise as 1. It is similar to first case which we already proved that both Hare and Tortoise will meet up in next step.

Let the length of the loop be 'n' and there are 'p' variables before the loop. Hare traverses the loop twice in 'n' moves, they are guaranteed to meet in O(n).

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

Write a C Program without main function

noreply@blogger.com (Unknown) — Thu, 23 Aug 2012 15:19:00 +0000

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.

Solution 01: Using simple macro substitution

#include <stdio.h>

#define START main

int START()
{
   printf("HELLO WORLD");
}

During the preprocessing stage of compilation of above code, HELLO is replaced with main.

Solution 02: Using Token Merging Operator

## is a Token merging operator. It can merge two or more characters.

#include <stdio.h>

#define START m##a##i##n

int START()
{
   printf("HELLO WORLD");
}

Solution 03: Using Argumented Macro

#include <stdio.h>

#define decode(l,i,g,h,t) h##l##g##i
#define START decode(a,n,i,m,e)

int START()
{
   printf("HELLO WORLD");
}

During the preprocessing stage START is replaced with decode which takes 5 arguments namely a n i m e and then decode is replaced h##l##g##i which means main.

Implementing ls command in C

noreply@blogger.com (Unknown) — Thu, 09 Aug 2012 15:14:00 +0000

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.

/*Listing the Files in a directory */

#include <sys/types.h>
#include <sys/dir.h>
#include <sys/param.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <dirent.h>
#include <pwd.h>
#include <grp.h>
#include <time.h>
#include <locale.h>
#include <langinfo.h>
#include <stdint.h>
#include <fcntl.h>

static char perms_buff[30];

const char *get_perms(mode_t mode)
{
  char ftype = '?';

  if (S_ISREG(mode)) ftype = '-';
  if (S_ISLNK(mode)) ftype = 'l';
  if (S_ISDIR(mode)) ftype = 'd';
  if (S_ISBLK(mode)) ftype = 'b';
  if (S_ISCHR(mode)) ftype = 'c';
  if (S_ISFIFO(mode)) ftype = '|';

  sprintf(perms_buff, "%c%c%c%c%c%c%c%c%c%c %c%c%c", ftype,
  mode & S_IRUSR ? 'r' : '-',
  mode & S_IWUSR ? 'w' : '-',
  mode & S_IXUSR ? 'x' : '-',
  mode & S_IRGRP ? 'r' : '-',
  mode & S_IWGRP ? 'w' : '-',
  mode & S_IXGRP ? 'x' : '-',
  mode & S_IROTH ? 'r' : '-',
  mode & S_IWOTH ? 'w' : '-',
  mode & S_IXOTH ? 'x' : '-',
  mode & S_ISUID ? 'U' : '-',
  mode & S_ISGID ? 'G' : '-',
  mode & S_ISVTX ? 'S' : '-');

  return (const char *)perms_buff;
}

char pathname[MAXPATHLEN];

void die(char *msg)
{
  perror(msg);
  exit(0);
}

static int
one (const struct dirent *unused)
{
  return 1;
}

int main()
{
  int count,i;
  struct direct **files;
  struct stat statbuf;
  char datestring[256];
  struct passwd pwent;
  struct passwd *pwentp;
  struct group grp;
  struct group *grpt;
  struct tm time;
  char buf[1024];

  if(!getcwd(pathname, sizeof(pathname)))
    die("Error getting pathnamen");

  count = scandir(pathname, &files, one, alphasort);

  if(count > 0)
  {
    printf("total %d\n",count);

    for (i=0; i<count; ++i)
    {
      if (stat(files[i]->d_name, &statbuf) == 0)
      {
        /* Print out type, permissions, and number of links. */
        printf("%10.10s", get_perms(statbuf.st_mode));
        printf(" %d", statbuf.st_nlink);

        if (!getpwuid_r(statbuf.st_uid, &pwent, buf, sizeof(buf), &pwentp))
          printf(" %s", pwent.pw_name);
        else
          printf(" %d", statbuf.st_uid);

        if (!getgrgid_r (statbuf.st_gid, &grp, buf, sizeof(buf), &grpt))
          printf(" %s", grp.gr_name);
        else
          printf(" %d", statbuf.st_gid);

        /* Print size of file. */
        printf(" %5d", (int)statbuf.st_size);

        localtime_r(&statbuf.st_mtime, &time);
        /* Get localized date string. */
        strftime(datestring, sizeof(datestring), "%F %T", &time);

        printf(" %s %s\n", datestring, files[i]->d_name);
      }

      free (files[i]);
    }

    free(files);
  }
}

GIT - Adding diffmerge as visual merge in git

noreply@blogger.com (Unknown) — Thu, 12 Jul 2012 06:45:00 +0000

GIT is one of the popular distributed code repositories in opensource community, especially with developers working on opensource projects like linux kernel and others.

Operations like Merge and Diff are the most irritating & tricky tasks via command line when working on large code changes. So let us see how can we add some graphical stuff for these operations when using on GIT so that we can do merging and other options very easily.

By following below steps you can install and configure diffmerge tool for git.

Based on the operating system you are using download respective diffmerge tool.

Now go to the source code directory which have been cloned from a git repository. Add the following commands to make git support diffmerge in diff and merge operations.

git config --global diff.tool diffmerge
git config --global difftool.diffmerge.cmd 'diffmerge "$LOCAL" "$REMOTE"'
git config --global merge.tool diffmerge
git config --global mergetool.diffmerge.cmd 'diffmerge --merge --result="$MERGED" "$LOCAL" "$(if test -f "$BASE"; then echo "$BASE"; else echo "$LOCAL"; fi)" "$REMOTE"'
git config --global mergetool.diffmerge.trustExitCode true

Configuration is done.

Now let us see how can we use the diffmerge tool.

Whenever you want to launch diff use difftool and similarly mergetool to launch merge as shown below.

# To diff a local file against the checked-in version
git difftool file

# to diff the local file against the version in some-feature-branch
git difftool some-feature-branch file

# to diff the file under the Build-54 tag to the Build-55 tag
git difftool Build-54..Build-55 file

# to do merge operations and resolve conflicts via diffmerge tool use below command.
git mergetool

Start using it now.

References

1. Twobit Labs

TCPDUMP cheat sheet

noreply@blogger.com (Unknown) — Thu, 14 Jun 2012 09:29:00 +0000

Listing possible network interfaces on the system

tcpdump -D

E.g.
$ tcpdump -D
1.eth0
2.eth1
3.usbmon1 (USB bus number 1)
4.eth2
Capture packets from a particular interface

tcpdump -i interface-name

E.g. To capture packets from interface eth1 - tcpdump -i eth1
Capture only N number of packets

tcpdump -c N

E.g. To capture 10 packets from interface eth1 - tcpdump -i eth1 -c 10
Capture the packets and write into a file

tcpdump -w file.pcap

E.g. tcpdump -i eth1 -w tmp.pcap
To capture and store network frames full-length

tcpdump -s 0

E.g. tcpdump -i eth1 -w tmp.pcap -s 0
Reading the packets from a saved file

tcpdump -r file.pcap

E.g.tcpdump -tttt -r tmp.pcap
Capture packets with proper readable timestamp

tcpdump -tttt

E.g. tcpdump -i eth1 -tttt

Filter Options

type

dir

proto

Read packets longer than N bytes

tcpdump greater N

E.g. tcpdump -i eth1 -w tmp.pcap greater 1024
Receive only the packets of a specific protocol type - fddi, tr, wlan, ip, ip6, arp, rarp, decnet, tcp and udp

E.g tcpdump -i eth1 arp
Receive packets flows on a particular port

tcpdump port PORT_NO

E.g. tcpdump -i eth1 port 22
Capture packets for particular destination IP and Port

tcpdump dst IPADDRESS and port PORT-NO

E.g. tcpdump -i eth1 dst 10.181.140.216 and port 22

Display options

Display more packet information

tcpdump -vvv

E.g. tcpdump -i eth1 -vvv
Display link level header of every packet: -e

tcpdump -e

E.g.

tcpdump -i eth1 -e -t
listening on eth2, link-type EN10MB (Ethernet), capture size 65535 bytes
52:54:00:e1:1c:10 (oui Unknown) > 01:80:c2:00:00:00 (oui Unknown), 802.3, length 60: LLC, dsap STP (0x42) Individual, ssap STP (0x42) Command, ctrl 0x03: STP 802.1d, Config, Flags [none], bridge-id 8000.52:54:00:e1:1c:10.8003, length 43
52:54:00:e1:1c:10 (oui Unknown) > 01:80:c2:00:00:00 (oui Unknown), 802.3, length 60: LLC, dsap STP (0x42) Individual, ssap STP (0x42) Command, ctrl 0x03: STP 802.1d, Config, Flags [none], bridge-id 8000.52:54:00:e1:1c:10.8003, length 43
Don’t print a timestamp on each dump line: -t

tcpdump -t

E.g.

Without using -t option we can see the below output timestamp is dumped (In bold letters).

tcpdump -i eth2

listening on eth2, link-type EN10MB (Ethernet), capture size 65535 bytes
08:44:51.295229 STP 802.1d, Config, Flags [none], bridge-id 8000.52:54:00:e1:1c:10.8003, length 43
08:44:53.296795 STP 802.1d, Config, Flags [none], bridge-id 8000.52:54:00:e1:1c:10.8003, length 43

tcpdump -i eth2 -t

listening on eth2, link-type EN10MB (Ethernet), capture size 65535 bytes
STP 802.1d, Config, Flags [none], bridge-id 8000.52:54:00:e1:1c:10.8003, length 43
STP 802.1d, Config, Flags [none], bridge-id 8000.52:54:00:e1:1c:10.8003, length 43
Display packets with IP address instead of DNS names: -n

Basically tcpdump converts the plain address to DNS names. Using n option we can make tcpdump to display ip address.

tcpdump -n

E.g. tcpdump -i eth1 -n
Display Captured Packets in ASCII

tcpdump -A

E.g. tcpdump -i eth1 -A
Display Captured Packets in HEX and ASCII

tcpdump -XX

Decoding hardware information of a PC

noreply@blogger.com (Unknown) — Wed, 02 May 2012 09:47:00 +0000

Checking out machine hardware information is no more a geeky thing of olden days where you need to go through the hardware specification documents or to open up a physical machine to find out the hardware details if the specification documents are missing. Now we have some really cool handy software tools to help us out.

I thought to make a page with some important tools which help us in decoding the hardware related information on a Linux Box. Feel free to drop a comment with the tool names I missed out in this post.

NOTE: All of them are ordered in alphabetical order and I am trying these tools on a Ubuntu machine running in virtual box. So some of the tool outputs might be displaying names likes VirtualBox and Oracle Corporation.

biosdecode
Also known as BIOS Information Decoder is one of the best tools to check the BIOS information. It parses the BIOS memory and displays the info about your system BIOS. For more detailed info checkout man-page.

ACPI 2.0 present.
 OEM Identifier: VBOX  
 RSD Table 32-bit Address: 0x33FF0000
 XSD Table 64-bit Address: 0x0000000033FF0030
BIOS32 Service Directory present.
 Revision: 0
 Calling Interface Address: 0x000FDA00
PCI Interrupt Routing 1.0 present.
 Router ID: 00:01.0
 Exclusive IRQs: None
 Compatible Router: 8086:7000
.
.
SMBIOS 2.5 present.
 Structure Table Length: 352 bytes
 Structure Table Address: 0x000E1000
 Number Of Structures: 5
 Maximum Structure Size: 255 bytes

dmidecode
Also known as DMI Table Decoder. It just dumps the DMI or SMBIOS information, to screen, in a human-readable format. Quite verbose with the information it provides but this tool seems to be unreliable as per its users in some case. For more detailed info checkout man-page.

# dmidecode
# dmidecode 2.9
SMBIOS 2.5 present.
5 structures occupying 352 bytes.
Table at 0x000E1000.

Handle 0x0000, DMI type 0, 20 bytes
BIOS Information
 Vendor: innotek GmbH
 Version: VirtualBox
 Release Date: 12/01/2006
.
Handle 0x0001, DMI type 1, 27 bytes
System Information
 Manufacturer: innotek GmbH
 Product Name: VirtualBox
 Version: 1.2
 Serial Number: 0
 UUID: B220160E-6104-4C00-B1B4-D00F6384DD24

lspci
It displays complete information about all the PCI buses in the system and the devices connected to them. As you can see in below output we can see about type of ethernet nic cards being used and other stuff. For more detailed info checkout man-page.

# lspci
00:00.0 Host bridge: Intel Corporation 440FX - 82441FX PMC [Natoma] (rev 02)
00:01.0 ISA bridge: Intel Corporation 82371SB PIIX3 ISA [Natoma/Triton II]
00:01.1 IDE interface: Intel Corporation 82371AB/EB/MB PIIX4 IDE (rev 01)
00:02.0 VGA compatible controller: InnoTek Systemberatung GmbH VirtualBox Graphics Adapter
00:03.0 Ethernet controller: Intel Corporation 82540EM Gigabit Ethernet Controller (rev 02)
00:04.0 System peripheral: InnoTek Systemberatung GmbH VirtualBox Guest Service
00:06.0 USB Controller: Apple Computer Inc. KeyLargo/Intrepid USB
00:07.0 Bridge: Intel Corporation 82371AB/EB/MB PIIX4 ACPI (rev 08)
00:08.0 Ethernet controller: Intel Corporation 82540EM Gigabit Ethernet Controller (rev 02)
00:0d.0 SATA controller: Intel Corporation 82801HBM/HEM (ICH8M/ICH8M-E) SATA AHCI Controller (rev 02)

Uli Drepper - Basics you should know about buffer overflow

noreply@blogger.com (Unknown) — Thu, 19 Apr 2012 12:18:00 +0000

Part 1: Buffer Overflows

Part 2: Buffer overflow and libc attacks

Part 3: Memory allocation errors

Part 4: SELinux

Part 5: Preventing exploits

For direct REDHAT videos checkout this link.

Connecting via SSH without password prompt

noreply@blogger.com (Unknown) — Fri, 06 Apr 2012 05:49:00 +0000

SSH is the common way to connect remote machines these days. Almost all kinds of applications use SSH in background for communicating with end machines.

But sometimes typing password repeatedly for establishing a SSH connection with the trusted end machine is quite daunting task.

Let us see how to automate the things in 3 simple steps where we can ssh to "user@host" without asking a password every time. Replace user with the username and host with the remote machine ip-address or hostname. For E.g. john@192.168.245.129

NOTE: Only do this with trusted machines.

cd ~/.ssh

Check if you have a 'id_rsa.pub' (or 'id_dsa.pub') file in .ssh folder. If not, try below command:

ssh-keygen -t rsa

Run ssh-copy-id

ssh-copy-id -i id_rsa.pub user@host

Its done .. Now you can ssh to user@host without being prompted for password.

Daemon-izing a Process in Linux

noreply@blogger.com (Unknown) — Tue, 13 Mar 2012 13:44:00 +0000

A Linux process works either in foreground or background.

A process running in foreground can interact with the user in front of the terminal. To run a.out in foreground we execute as shown below.

./a.out

When a process runs as background process then it runs by itself without any user interaction. The user can check its status but he doesn't (need to) know what it is doing. To run a.out in background we execute as shown below.

$ ./a.out &
[1] 3665

As shown above when we run a process with & at the end then the process runs in background and returns the process id (3665 in above example).

what is a DAEMON Process?
A 'daemon' process is a process that runs in background, begins execution at startup
(not neccessarily), runs forever, usually do not die or get restarted, waits for requests to arrive and respond to them and frequently spawn other processes to handle these requests.

So running a process in BACKGROUND with a while loop logic in code to loop forever makes a Daemon ? Yes and also No. But there are certain things to be considered when we create a daemon process. We follow a step-by-step procedure as shown below to create a daemon process.

1. Create a separate child process - fork() it.
Using fork() system call create a copy of our process(child), then let the parent process exit. Once the parent process exits the Orphaned child process will become the child of init process (this is the initial system process, in other words the parent of all processes). As a result our process will be completely detached from its parent and start operating in background.

pid=fork();

if (pid<0) exit(1); /* fork error */

if (pid>0) exit(0); /* parent exits */

/* child (daemon) continues */

2. Make child process In-dependent - setsid()

Before we see how we gonna make a child process independent let us talk Process group and Session ID.

A process group denotes a collection of one or more processes. Process groups are used to control the distribution of signals. A signal directed to a process group is delivered individually to all of the processes that are members of the group.

Process groups are themselves grouped into sessions. Process groups are not permitted to migrate from one session to another, and a process may only create new process groups belonging to the same session as it itself belongs to. Processes are not permitted to join process groups that are not in the same session as they themselves are.

New process images created by a call to a function of the exec family and fork() inherit the process group membership and the session membership of the parent process image.

A process receives signals from the terminal that it is connected to, and each process inherits its parent's controlling tty. A daemon process should not receive signals from the process that started it, so it must detach itself from its controlling tty.

In Unix systems, processes operates within a process group, so that all processes within a group is treated as a single entity. Process group or session is also inherited. A daemon process should operate independently from other processes.

setsid();

setsid() system call is used to create a new session containing a single (new) process group, with the current process as both the session leader and the process group leader of that single process group. (setpgrp() is an alternative for this).

NOTE: We have to create a child process and use setsid() to make it independent. Trying on a parent process returns error saying EPERM.

3. Change current Running Directory - chdir()

A daemon process should run in a known directory. There are many advantages, in fact the opposite has many disadvantages: suppose that our daemon process is started in a user's home directory, it will not be able to find some input and output files. If the home directory is a mounted filesystem then it will even create many issues if the filesystem is accidentally un-mounted.

chdir("/server/");

The root "/" directory may not be appropriate for every server, it should be chosen carefully depending on the type of the server.

4. Close Inherited Descriptors and Standard I/O Descriptors
A child process inherits default standard I/O descriptors and opened file descriptors from a parent process, this may cause the use of resources un-neccessarily. Unnecessary file descriptors should be closed before fork() system call (so that they are not inherited) or close all open descriptors as soon as the child process starts running as shown below.

for ( i=getdtablesize(); i>=0; --i) 
close(i); /* close all descriptors */

There are three standard I/O descriptors:

standard input 'stdin' (0),
standard output 'stdout' (1),
standard error 'stderr' (2).

For safety, these descriptors should be opened and connected to a harmless I/O device (such as /dev/null).

int fd;

fd = open("/dev/null",O_RDWR, 0);

if (fd != -1) 
{   
  dup2 (fd, STDIN_FILENO);
  dup2 (fd, STDOUT_FILENO);
  dup2 (fd, STDERR_FILENO);
  
  if (fd > 2)
  close (fd);
}

5. Reset File Creation Mask - umask()
Most Daemon processes runs as super-user, for security reasons they should protect files that they create. Setting user mask will prevent unsecure file priviliges that may occur on file creation.

umask(027);

This will restrict file creation mode to 750 (complement of 027).

Let us see a sample 'C' code which creates a daemon.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

#define EXIT_SUCCESS 0
#define EXIT_FAILURE 1

static void daemonize(void)
{
    pid_t pid, sid;
    int fd; 

    /* already a daemon */
    if ( getppid() == 1 ) return;

    /* Fork off the parent process */
    pid = fork();
    if (pid < 0)  
    {   
        exit(EXIT_FAILURE);
    }   

    if (pid > 0)  
    {   
        exit(EXIT_SUCCESS); /*Killing the Parent Process*/
    }   

    /* At this point we are executing as the child process */

    /* Create a new SID for the child process */
    sid = setsid();
    if (sid < 0)  
    {
        exit(EXIT_FAILURE);
    }

    /* Change the current working directory. */
    if ((chdir("/")) < 0)
    {
        exit(EXIT_FAILURE);
    }


    fd = open("/dev/null",O_RDWR, 0);

    if (fd != -1)
    {
        dup2 (fd, STDIN_FILENO);
        dup2 (fd, STDOUT_FILENO);
        dup2 (fd, STDERR_FILENO);

        if (fd > 2)
        {
            close (fd);
        }
    }

    /*resettign File Creation Mask */
    umask(027);
}

int main( int argc, char *argv[] )
{
    daemonize();

    while(1)
    {
      /* Now we are a daemon -- do the work for which we were paid */

      sleep(10);
    }

    return 0;
}

References

Memory Layout of a C program - Part 2

noreply@blogger.com (Unknown) — Sun, 04 Mar 2012 11:59:00 +0000

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.

Let us include a static variable as shown below.

#include <stdio.h>

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

int main()
{
    static int i; /* Uninitialized static variable stored in bss */
    return 0;
}

$ gcc test.c 
$ size a.out 
   text    data     bss     dec     hex filename
    836     260      16    1112     458 a.out

As you can see BSS is incremented by 4 bytes.

Now let us initialize the static variable so that it is saved in the initialized data segment.

#include <stdio.h>

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

int main()
{
    static int i=10; /* Initialized static variable stored in DS*/
    return 0;
}

$ gcc test.c 
$ size a.out 
   text    data     bss     dec     hex filename
    836     264      12    1112     458 a.out

Now you can see that data section is incremented by 4 bytes and BSS is decremented by 4 bytes.

Let us even initialize the Global variable which makes it part of Data Segment.

#include <stdio.h>

int global=10; /* Initialized variable stored in DS*/

int main()
{
    static int i=10; /* Initialized static variable stored in DS*/
    return 0;
}

$ gcc test.c 
$ size a.out 
   text    data     bss     dec     hex filename
    836     268      8    1112     458 a.out

We can see that data section is incremented by 4 bytes and BSS is decremented by 4 bytes.

Let us see what happens when we add a const variable.

#include <stdio.h>

const int i = 1;

int global=10;

int main()
{
    static int i=10;
    return 0;
}

$ gcc test.c 
$ size a.out 
   text    data     bss     dec     hex filename
    840     268       8    1116     45c a.out

Now we can see that TEXT segment is incremented by 4 bytes.

References:
1. Narendra Kangralkar

Memory Layout of a C program - Part 1

noreply@blogger.com (Unknown) — Sun, 04 Mar 2012 11:10:00 +0000

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

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.

data segment

initialized data
It contains both static and global data that are initialized with non-zero values. Each process running the same program has its own data segment.This segment can be further classified into initialized read-only area and initialized read-write area.

For Eg: The global string defined by char s[] = “hello world” in C and a C statement like int debug=1 outside the main (i.e. global) would be stored in initialized read-write area. And a global C statement like const char* string = “hello world” makes the string literal “hello world” to be stored in initialized read-only area and the character pointer variable string in initialized read-write area.

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

Uninitialized data - bss segment
BSS stands for ‘Block Started by Symbol’ named after an ancient assembler operator that stood for “block started by symbol".uninitialized data starts at the end of the data segment and contains all global variables and static variables that are initialized to zero or do not have explicit initialization in source code.

For Eg: A variable declared static int i and a global variable declared int j would be contained in the BSS segment.

Each process running the same program has its own BSS area. When running, the BSS data are placed in the data segment.

For Linux/Unix the format of an executable, only variables that are initialized to a nonzero value occupy space in the executable’s disk file. In the executable file, they are stored in the BSS section.

The remaining two areas of system memory are where storage may be allocated by the compiler for data storage.

heap segment

The heap is where dynamically allocated memory (obtained by malloc(), calloc(), realloc() and new for C++) comes from. As memory is allocated on the heap, the process’s address space grows. Although it is possible to give memory back to the system and shrink a process’s address space, this is almost never done because it will be allocated to other process again.

Freed memory (free() and delete) goes back to the heap. Heap memory does not have to be returned in the same order in which it was acquired (it doesn't have to be returned at all), so unordered malloc/free's eventually cause heap fragmentation. The heap must keep track of different regions, and whether they are in use or available to malloc. One scheme is to have a linked list of available blocks (the "free store"), and each block handed to malloc is preceded by a size count that goes with it. Some people use the term arena to describe the set of blocks managed by a memory allocator (in SunOS, the area between the end of the data segment and the current position of the break).

It is typical for the heap to grow upward. This means that successive items that are added to the heap are added at addresses that are numerically greater than previous items. It is also typical for the heap to start immediately after the BSS area of the data segment. The end of the heap is marked by a pointer known as the "break" (Your programs will "break" if they reference past the break).

When the heap manager needs more memory, it can push the break further away using the system calls brk and sbrk. We don't call brk yourself explicitly, but if we malloc enough memory, brk will eventually be called.

stack segment

The stack segment is where local (automatic) variables are allocated. In C program, local variables are all variables declared inside the opening left curly brace of a function body including the main() or other left curly brace that aren’t defined as static. The data is popped up or pushed into the stack following the Last in First out (LIFO) rule.

On the standard PC x86 computer architecture it grows toward address zero; on some other architectures it grows the opposite direction.

A “stack pointer” register tracks the top of the stack; it is adjusted each time a value is “pushed” onto the stack.When a function is called, a stack frame (or a procedure activation record) is created and PUSHed onto the top of the stack. This stack frame contains information such as the address from which the function was called and where to jump back to when the function is finished (return address), parameters, local variables, and any other information needed by the invoked function. The order of the information may vary by system and compiler.

When a function returns, the stack frame is POPped from the stack. Typically the stack grows downward, meaning that items deeper in the call chain are at numerically lower addresses and toward the heap.

Figure 2: Stack layout

When a program begins executing in the function main(), space is allocated on the stack for all variables declared within main(), as seen in Figure (a). If main() calls a function, func1(), additional storage is allocated for the variables in func1() at the top of the stack as shown in Figure (b). Notice that the parameters passed by main() to func1() are also stored on the stack.

If func1() were to call any additional functions, storage would be allocated at the new Top of stack as seen in the figure. When func1() returns, storage for its local variables is deallocated, and the Top of the stack returns to position shown in Figure (c). If main() were to call another function, storage would be allocated for that function at the Top shown in the figure. As can be seen, the memory allocated in the stack area is used and reused during program execution. It should be clear that memory allocated in this area will contain garbage values left over from previous usage.

Although it is theoretically possible for the stack and heap to grow into each other, the operating system prevents that event.

Check the PART-2 for detailed understanding of these sections with examples.

The relationship among the different sections/segments is summarized below.

Figure 3: Relationship between Sections and Segments

Deletion of a Node from Doubly Linked List

noreply@blogger.com (Unknown) — Thu, 01 Mar 2012 14:49:00 +0000

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

In HEAD

In NODE-2

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.

Deleting Middle Node from the List

Using a temporary Node pointer curPtr we have to traverse until NODE-2.

In NODE-1

In NODE-3

Decrement LENGTH variable in HEAD so that it maintains the proper count of Nodes in the List.

Pseudocode:

curPtr->PREV->NEXT = curPtr->NEXT

curPtr->NEXT->PREV = curPtr->PREV

decrement(HEAD->LENGTH)

Output:

Figure 3: After Deleting NODE-2 in the List.

Deleting Last Node in the List

Using a temporary Node pointer curPtr we have to traverse until the end Node of the List. So curPtr is now pointing to NODE-3.

In NODE-2

Decrement the LENGTH variable in HEAD so that it maintains the proper count of Nodes in the List.

Pseudocode:

curPtr->PREV->NEXT = NULL

decrement(HEAD->LENGTH)

Output:

Figure 4: After Deleting Last Node from the List.

Let us see sample 'C' code to the deletion of a Node operation

retVal
delNodeAtLoc(listHead *head, UINT32 loc)
{
    retVal ret = SUCCESS;
    UINT32 i;

    listNode *curPtr;

    if(head && head->first && loc && loc <= (head->length)) 
    {   
        curPtr = head->first;

        if (loc == 1)
        {   
            head->first = curPtr->next;

            if(head->first)
                head->first->prev = NULL;
        }   
        else 
        {   
            for(i=1; i<loc; i++) 
                curPtr = curPtr->next;

            curPtr->prev->next = curPtr->next;

            if(curPtr->next)
                curPtr->next->prev = curPtr->prev;
        }    

        dlist_freeNode(curPtr);
        head->length--;
    }
    else
        ret = FAILURE;

    return ret;
}

Inserting a Node in Doubly Linked List

noreply@blogger.com (Unknown) — Mon, 27 Feb 2012 12:30:00 +0000

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

NULL

In HEAD

In newNode

NULL

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)

Adding a Node at the start of the Non-Empty List

Figure 3: A Doubly Linked List of Length 3.

In newNode

In curFirstNode

In HEAD

Increment the LENGTH variable in HEAD to maintain the count of number of Nodes in the List.

Pseudocode:

newNode->NEXT = HEAD->FIRST

HEAD->FIRST->PREV = newNode

HEAD->FIRST = newNode

newNode->PREV = NULL

increment(HEAD->LENGTH)

Output:

Figure 4: After adding newNode at location 1. (Changes in BLUE)

Adding a Node at the middle of the list.

Figure 5: Current Preview of the Doubly Linked List.

Traverse the Doubly Linked List until the Location 2. So our curPtr is pointing to Node 2.

In newNode

In NODE3

In NODE2

Increment the LENGTH variable in HEAD to maintain the count of number of Nodes in the List.

Pseudocode:

newNode->PREV = curPtr

newNode->NEXT = curPtr->NEXT

newNode->NEXT->PREV = newNode

curPtr->NEXT = newNode

increment(HEAD->LENGTH)

Output:

Figure 6: After adding newNode at Location 3 (Changes in BLUE)

Adding a Node at the End of the List

In Last Node

In newNode

Increment the LENGTH variable in HEAD to maintain the count of number of Nodes in the List.

Pseudocode:

curPtr->NEXT = newNode

newNode->PREV = curPtr

increment(HEAD->LENGTH)

Let us see the preview of the C code which does the insertion of a Node at a particular location.

This code is generic for all the possible scenarios explained above.

addNodeAtLoc(listHead *head, listNode *newNode, UINT32 loc)
{
    UINT32 i;
    retVal ret = SUCCESS;

    listNode *curPtr;

    if(head && newNode && loc && (loc <= (head->length)+1))
    {   
        if(loc == 1)
        {   
            newNode->prev = NULL;
            newNode->next = head->first;
    
            if(head->first)
                head->first->prev = newNode;

            head->first = newNode;
        }   
        else
        {   
            curPtr = head->first;

            for(i=1; i<(loc-1); i++)
                curPtr = curPtr->next;

            newNode->prev = curPtr;
            newNode->next = curPtr->next;

            if(curPtr->next)
                curPtr->next->prev = newNode;

            curPtr->next = newNode;
        } 

        head->length++;
    }
    else
        ret = FAILURE;

    return ret;
}

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