Peasant's Multiplication Algorithm

Peasant's Multiplication Algorithm

Exploit the binary representation of the number. eg:
98 * 19
Take one of the two number and represent it in binary. Now, what happens
= 98 * (1 0 0 1 1)
= 98 * (16 + 2 + 1)
= 98 * 16 + 98 * 2 + 98 * 1
= 1568 + 196 + 98
= 1862

Calculate by hand or calculator
= 98 * 19
= 1862

What is the usefulness ?
Computation of multiplication is not as easy as addition, subtraction, shift operations or logical operations. Many primitive microprocessor and micro-controller doesn't
even support it directly. So, one way of doing it is by adding a term to itself for the number of second term. eg if x*y then if we add x to itself y times then we get x*y,
However, the computation has to be done y times. But same thing can be achieved by using this algorithm but still we are doing three multiplications in above example instead of
one. But the trick is all the multiplication above is multiplication by the power of 2 and which is very cheap to compute which can be achieved easily by shifting the bits.

C Code:
 #include<stdio.h>
int mult(int a,int b)
{
int count = 0,sum=0;
while(b != 0)
{
if((b & 1)!= 0)
sum += a << count;
b = b >> 1;
count++;
}
return sum;
}
int main()
{
int num1,num2;
scanf("%d%d",&num1,&num2);
printf("%d x %d = %d\n",num1,num2,mult(num1,num2));

return 0;
}

Doubly Linked List using Single Pointer

Doubly Linked List needs two pointers to maintain the previous and next pointer value so that we can traverse in both forward and reverse direction. However, maintaining two pointers may be costly for the system with low memory. For such circumstances we have an option to create a double linked list with a single pointer. This is attainable by the use of XOR.

Steps to create DLL:

1. For, after creating the first node, make its pointer point to NULL.
2. Now, create a next node and then make it point to the predecessor node.
3. The pointer of the predecessor node is XOR with the current node. i.e. pred->pointer= pred->pointer ^ current_node
4. Jump to Step 2 to add more elements

Displaying the DLL

1. Check the list to be displayed is empty. If so, return.
2. Use two additional pointers prev and temp. Initialize prev to NULL.
3. Now, save list to temp variable.
4. Find new value of list by: list=list->ptr ^ prev.
5. Set prev=temp.
6. Jump to Step 3 until list become NULL

Displaying in Reverse direction

It can be done in the same way as Displaying element but here you need to be in the last element and then you can traverse forward.

Code:

#include
#include
struct node;
typedef struct node NODE;
struct node
{
       int info;
       struct node *ptr;
};
void create_list(int a[],NODE **list,int size)
{
     NODE *temp,*new_node;
     temp=*list;
     int i;
     for(i=0;iptr=NULL;
                              temp->info=a[0];
                              *list=temp;
                }
                else 
                {
                     new_node=(NODE*)malloc(sizeof(struct node));
                     new_node->info=a[i];
                     new_node->ptr=temp;
                     temp->ptr=(NODE*)((long)temp->ptr ^ (long)new_node);
                     temp=new_node;
                 }
     }
}
void display_normal(NODE *list)
{
     NODE *temp,*prev;
     prev=NULL;
     if(list==NULL)
                   return;
     printf("\n\n\n");                   
     do
     {
          printf("  %d  ",list->info);
          temp=list;
          list=(NODE*)((long)list->ptr ^ (long)prev);
          prev=temp;
     }while(list!=NULL);     
     
}
void display_rev(NODE *list)
{
     NODE *temp,*prev;
     prev=NULL;
     if(list==NULL)
                   return;
     do
     {
                   temp=list;
                   list=(NODE*)((long)list->ptr ^ (long)prev);
                   prev=temp;
     }while(list!=NULL);
     
     printf("\n\n\n");
     list=prev;
     prev=NULL;
     do
     {
               printf("  %d ",list->info);
               temp=list;
               list=(NODE*)((long)list->ptr ^ (long)prev);
               prev=temp;
     }while(list!=NULL);
}
int main()
{
    int a[]={23,45,78,90,12,10};
    NODE *list;
    list=NULL;
    create_list(a,&list,sizeof(a)/sizeof(a[0]));
    display_normal(list);
    display_rev(list);
    getchar();
    return 0;
}

A Fast Majority Vote Algorithm (Moore's Majority Algorithm)

Algorithm:
Suppose, we have several candidates participating in voting. Now, if the number of candidate is static then it can be done easily in O(n) time complexity with an additional storage for the number of candidates participating in the voting. However, the time required can increased tremendously if
i. The number of voters are not static. In that case, for each vote we have to scan for the candidate and update the count which may cause as worse as O(n*n) time complexity.
ii. We don't have additional space to store the vote. We are allowed to only use O(1) space.

The problem can be solved using Majority Vote Algorithm.
Here, we use two variable to find out the majority. The total comparisons required for this algorithm is 2*n.
There are two variables count and c.
count= total number of vote for the candidate
c= particular candidate
Now, go through the votes one by one in the following fashion
Step 0: Initialize count to be zero
Step 1: Go through the vote
           i. Check if the count is zero
                    if so then assign the c to this vote's candidate and then set count=1
                    if not then check if this vote's candidate is equal to c
                                  if yes then set count+=1
                                  if no then set count-=1
Step 2: Continue until the end
Step 3: Now, return c
Step 4: Check once again by going through the votes if it is really the majority.
Code:
/*I have used the static number of candidate by defining the array however it works equally fine for dynamic candidate number too. */
#include<stdio.h>
int count_vote(int a[],int size)
{
    int count=0,c,i;
    for(i=0;i<size;i++)
    {
        if(count==0)
        {
            c=a[i];
            count=1;
        }
        else
        {
            if(c==a[i])
                count++;
            else
                count--;
        }
    }
    return c;
}
int main()
{
    int a[]={2,3,2,4,5,2,4,3,2,2,2,8,9,2,7,6,1,2,2,2,4,2,5,6,7,2,1,2,2,2,2};
    int size=sizeof(a)/sizeof(a[0]);
    int majority,count=0,i;
    majority=count_vote(a,size);
    for(i=0;i<size;i++)
        if(a[i]==majority)
            count++;
    if(count>size/2)
        printf("\nThe %d is a majority with %d vote where total vote is %d .\n",majority,count,size);
    else
        printf("\nThe %d is not a majority vote but has %d vote in total vote of %d.\n",majority,count,size);
    return 0;
}

Writing character device driver

#include<linux/init.h>
#include<linux/device.h>
#include<linux/module.h>
#include<linux/fs.h>
#include<asm/uaccess.h>
#include<linux/string.h>
#include<linux/cdev.h>
MODULE_LICENSE("GPL");
#define DEVICE_NAME "mychardev"
struct cdev *mydevice;
struct class *myclass;
static char Buffer[256];
static ssize_t device_read(struct file *file,char *buffer,size_t length,loff_t *offset);
static ssize_t device_write(struct file *file,const char *buffer,size_t length,loff_t *offset);
static int device_open(struct inode *inode,struct file *file);
static int device_release(struct inode *inode,struct file *file);
static struct file_operations fops=
{
    .read=device_read,
    .write=device_write,
    .open=device_open,
    .release=device_release,
};
static int hello_init(void)
{
    int error;
    mydevice=cdev_alloc();
    if((error=alloc_chrdev_region(&mydevice->dev,0,1,DEVICE_NAME)))
    {
        printk(KERN_ALERT "\nThere is problem in allocating the chrdev region.");
        return error;
    }
    mydevice->ops=&fops;
    mydevice->owner=THIS_MODULE;
    if((error=cdev_add(mydevice,mydevice->dev,1))<0)   
    {
        printk(KERN_ALERT "\nThere is a problem in adding cdev.");
        return error;
    }
    if((myclass=class_create(THIS_MODULE,DEVICE_NAME))==NULL)
    {
        printk(KERN_ALERT "\nThe class creation failed.");
        return -15;
    }
    device_create(myclass,NULL,mydevice->dev,NULL,DEVICE_NAME);
    printk(KERN_ALERT "\nThe device created successfully");
    return 0;
}
static int hello_exit(void)
{
    printk(KERN_ALERT"\nTrying to exit.");
    device_destroy(myclass,mydevice->dev);
    class_destroy(myclass);
    unregister_chrdev_region(mydevice->dev,1);
    cdev_del(mydevice);
    printk(KERN_ALERT "\nExiting the device successfully.");
    return 0;
}
static int device_open(struct inode *inode,struct file *filep)
{
    printk(KERN_ALERT "\nThe device has been opened successfully.");
    return 0;
}
static int device_release(struct inode *inode,struct file *filep)
{
    printk(KERN_ALERT "\nThe device has been closed successfully.");
    return 0;
}
static ssize_t device_read(struct file *file,char *buffer,size_t length,loff_t *offset)
{
    size_t totalbytes;
    long bytesnotcopied;
    totalbytes=strlen(Buffer);
    bytesnotcopied=copy_to_user(buffer,Buffer,totalbytes);
    return totalbytes-bytesnotcopied;
}
static ssize_t device_write(struct file *file,const char *buffer,size_t length,loff_t *offset)
{
    size_t bytesnotcopied;
    bytesnotcopied=copy_from_user(Buffer,buffer,length);
    printk(KERN_ALERT "%s ",Buffer);
    return (length-bytesnotcopied);
}
module_init(hello_init);
module_exit(hello_exit);


-------------------------------------------------------------------------------------------------------------------------------------

What are all the headers for ??

i. linux/init
       It is used for module_init() and module_exit(). Actually, these are macros and it tells the compiler that module_init() is used by the driver when it is loaded. It can be later on deleted as it will be having no other functions besides at start up. The module_exit() is used to deallocate the resources which we allocated when loading the driver through init functions.
ii.linux/device
      This header is used as the struct class and struct device are described here. These are actually needed to create a node in the filesystem like /sys. The struct class create a class entry in the class directory in the /sys with the name specified with DEVICE_NAME (in the above example). Similarly, the device is used to create a actual device node. The class is generally the accumulation of different devices.
iii.linux/module
     This header is needed as it is in this header that MODULE_LICENSE(), MODULE_AUTHOR(),etc are all described.
iv.linux/fs
     The file related operations and the struct file_operations is described in here.
v.asm/uaccess
     The inline duo functions copy_from_user and copy_to_user are described here. These two are used to take care of virtual memory as the address we are referring to might not be actually present but rather be need to swept out from the disk. Furthermore, it checks the validity of the pointer that is provided form the user space. First it checks it the read/write permission is there and it also checks if the pointer lies in the address space of the process. And it is architecture dependent thus will be present inside arch/(any architecture)/asm/uaccess.h
vi. linux/cdev
     The structure cdev is defined here.
----------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------
alloc_chrdev_region() : This function is used to dynamically allocate the device number for the device( i.e. Major and Minor). The best thing about it is that it is safer to user as there is no chance of contradicting the Major number with the existing one. There is another variation to this
register_chrdev_reigion() : If we are sure that we are not violating the Major number that is not using the same as other drivers then we can statically allocate the device using register_chrdev_region().
cdev_alloc() : It is used to allocate the memory for the struct cdev structure.
cdev_add():  It adds the struct cdev passed and makes it lives immediately.
class_create(): It is used to create an entry in the class directory in /sys.
device_create(): It is used to create a device entry.
copy_from_user():
copy_to_user(): described above
Similarly, all the other functions are used in the exit module to release the resources allocated in the init module.
---------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------

The mistakes I made 

i. Always include MODULE_LICENSE(" ") either "GPL" or "Dual BSD/GPL" .This is because the kernel and all the proprietary codes are released under "GPL" license so if you are using it or modifying or doing anything with it. The code must be in compliance with "GPL" license so we declared. If we forget to give MODULE_LICENSE(), we will get several errors.
ii. Run the user level program as root user or as the user who inserted the modules.
---------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------

Inserting into the kernel

i. Building as a module

Write a make file in any directory,
obj-m := chardevices.o
all:
    make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules
clean:
    make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean
Then run $make in the terminal.
Once it is built then use
$sudo insmod ./chardevices.ko
The sudo here is mandatory without which we cannot insert it.
Similarly, *.ko should be used not *.o.

ii.Building as a part of the kernel

i. Go to the linux/device/char/chardevices (this is our directory)
Create a directory and copy a code in this directory.
Write a Makefile here,
obj-$(CONFIG_MY_CHAR)    := chardevices.o

ii. In the Makefile of linux/device/char add the following line 

obj-$(CONFIG_MY_CHAR) += chardevices/ (this is usually to specify the directory)

iii. Now, go ahead in linux/device/char and modify the Kconfig to add our configuration ie MY_CHAR

config MY_CHAR
    tristate "This is my character device"
    default y
    help

(give anything)

Since we are using tristate, there can be three state viz:

i. m which means to build the driver as module and will not be the part of the kernel

ii. y which means to build the driver as a part of the kernel

ii. n

Linux System Call for Arm Architecture

Implementation of System Calls for Arm Architecture

 I have used Linux 3.2 version for this as I was testing my system call in Mobile phone so this system call procedure may not work for the newer release of kernel.
Step 1:
Add a system call number
path : /arch/arm/include/asm/unistd.h
e.g. :
#define __NR_my_add     (__NR_SYSCALL_BASE +377 )

Step 2: 
Make an entry to calls.S with path given below
path: /arch/arm/kernel/calls.S
e.g. :
CALL(sys_my_add); (the position has to be same as the system call number ie 377)
 This file will be automatically added to entry-common.S as the file entry-common.S include it as follows.
      .table
#include "calls.S"

(Alternatively)
We can define a wrapper function in entry-common.S and then register this wrapper function in calls.S. In the entry-common.S then finally we can jump to our system call routine.
path: /arch/arm/kernel/entry-common.S
e.g. :
In calls.S
CALL(sys_my_add_wrapper);  (the position has to be same as the system call number ie 377)
In entry-common.S,
Add the following code
START(sys_my_add_wrapper)
     b      sys_my_add
ENDPROC(sys_my_add_wrapper)

Step 3:
Writing the routine for system call. Again it can be done in two ways:
i. Directly it can be included in the existing files( so that it doesn't require us to modify the Makefile)
ii. Make a separate file and change the Make file to make sure it compiles.
eg:
asmlinkage long sys_my_add(int a,int b)
{
        printk(KERN_ALERT "The addition is %d ",a+b);
        return a+b;
}
If separate file (say my_add.c) is maintained we have to add the following line in the Makefile.
e.g.:
obj-y :=my_add.o

Step 4: 
Register the function with the prototype.
path: /include/linux/syscall.h
Add the following line:
asmlinkage long sys_my_add(int,int);

Implementation in User Space 

I have written a code in Assembly to call the function.
e.g.:
mov  r7,#377
mov  r0,#25
mov r1,#35
SWI 0
mov r7,#1
SWI  0

we can also replace the last three lines of code by using SWI 377 instead.

System Calls Implementaion in Linux (for both older and newer version) in x86

Implementation of System Call in Older Linux Version

Step 1:
Reserve a system call number
path: (inside linux source tree) /arch/x86/include/asm/unistd_32.h
Go to the end and add the system call number and also modify NR_syscalls by adding 1.
e.g. : #define __NR_my_add     350
Step 2:
Declare system call prototype
path: /arch/x86/include/asm/syscalls.h
go to : #ifdef CONFIG_x86_32 (for 32 bit) or common (for both 32 or 64 or ..._64
asmlinkage long sys_my_add(int,int);
Step 3:
Append system call address to sys_call_table
path: /arch/x86/kernel/syscall_table_32.S
Go to the last position, here I'm going to the 350th position (same position as call number) and write
.long sys_my_add
Step 4:
Implement syscall Routine
It can be done in one of the two ways:
i. Add the function to the existing source file ( you don't have to change the source file)
ii. Adding a source file ( however, modify the Makefile to compile this file too)
e.g.:
asmlinkage long sys_my_add(int a,int b)
{
        printk(KERN_ALERT "The sum is %d ",a+b);
        return a+b;
}
Now, This function can be added to any existing file. If so we are done but if we have created a file say my_add.c then don't forget to add following line in a Makefile where this code exist.
obj-y := my_add.o

Implementation of System Call in Newer Linux Version

Step 1:
Now, if you would follow the previous method you would be surprise to find that
/arch/x86/include/asm/unistd_32.h file doesn't exist. It does however exist but has been removed from there and is saved in generated directory which gets generated automatically. Rather now we have to follow to the following path to modify the system call table.
path: /arch/x86/sycalls/sycall_32.tbl
Now, the table is of the form as below:
<number> <api> <name> <entry point><compat entry point>
number: specify the system call number ie increase the count of the last system call by 1
api : in the case of x86 it is by default i386
name: name of the system call
entry point: it is the entry point for our system call
compat entry point: if our call has a compat entry point
eg:
350   i386   my_add    sys_my_add
After doing this automatically the system call number gets appended in unistd_32.h and we don't have to do anything.

Step 2:
Follow the step 2 of older version.

Step 3:
Follow the step 4 of older version.

Calling the system call from user space after building the kernel

#include<stdio.h>
#include<unistd.h>
int main()
{
        int a,b,c;
        a=35;
        b=45;
        c=sycall(350,a,b);
        printf("\nThe value of the sum is %d \n",c);
        return 0;
}

Part II: Threaded Binary Search Tree Traversal

Inorder

Algorithm:
Follow the tree towards the left, print the smallest value and then move on to print the next smallest value so that finally we will be printing all the value in the ascending order. This one can be achieved simply by using recursive algorithm as follows:
For the general binary search tree,
void inorder(struct node *tree)
{
    if(tree==NULL)
        return;
    inorder(tree->left);
    printf(" %d ",tree->info);
    inorder(tree->right);
}

However, the inorder code for Threaded binary search tree isnot as simple, the code is given below

struct node *inorder_successor(struct node *tree)
{
    struct node *temp;
    temp=tree->right;
    if(tree->isright==0) //here we are checking if the tree is a leaf ( not the temp)
        return temp;
    while(temp->isleft==1)
        temp=temp->left;
    return temp;
}
/*Thus, what we are doing in the above steps are first checking if the tree is a leaf. If so we are returning temp (which is right of the tree), otherwise we are going to find the inorder successor of that tree. */
void inorder(struct node *head_tree)
{
    struct node *tree;
    printf("\n\n");
    tree=head_tree->left;
    if(tree==NULL)
    {
        printf("\nNo element in the tree.");
        return;
    }
    while(tree->left!=head_tree)
        tree=tree->left;
    do
    {
        printf(" %d ",tree->info);
        tree=inorder_successor(tree);
        if(tree==head_tree)
            break;
    }while(1);
    printf("\n\n");
}

We are using two functions here, one for the traversal and one to find the inorder succesor after traversing any node. By the way, the traversal has started from the first inorder element. (not the root of the tree)

Preorder

In preorder, for any node we first print the value of the node and then follow its left and after printing all its left value we follow the right and print all the value.
For general binary search tree, the recursive algorithm is as follows:
void preorder(struct node *tree)
{
    if(tree==NULL)
          return;
    printf(" %d ",tree->info);
    preorder(tree->left);
    preorder(tree->right);
}
However, we do it in the similar fashion as inorder for the threaded binary trees by using two functions respectively to traverse and find the preorder successor. The code for the preorder traversal is given below:

struct node *preorder_successor(struct node *tree,struct node *head_tree)
{
    struct node *temp;
    if(tree->isleft==1)
        return tree->left;
    if(tree->isright==1)
        return tree=tree->right;
    while(tree->isright==0)
    {
        tree=tree->right;
        if(tree==head_tree)
            return head_tree;
    }
    return tree->right;
}
void preorder(struct node *head_tree)
{
    struct node *tree;
    tree=head_tree->left;
    printf("\n\n");
    if(tree==NULL)
    {
        printf("\nNo element in the tree.\n");
        return;
    }
    do
    {
        printf("  %d  ",tree->info);
        tree=preorder_successor(tree,head_tree);
        if(tree==head_tree)
            return;
    }while(1);
    printf("\n\n");
}

Postorder 

In the postorder successor, for any node we follow the left link and print all the values and then follow the right one and print all the values and finally print the value of that node.
For the general binary search tree, the postorder code is below
void postorder(struct node *tree)
{
    if(tree==NULL)
          return;
    postorder(tree->left);
    postorder(tree->right);
    printf(" %d ",tree->info);
}
However, for the threaded binary search tree, it is the trickiest. Following algorithm I used to write a code from the following address http://stackoverflow.com/questions/10694037/postorder-traversal-of-tree-without-using-recursion-or-stack

The algorithm goes as follows 

• A variable can be used to check type of current action.
• If action is left traversal and current node has a left descendant, then descendant is traversed. Otherwise action changed to right traversal.
• If action is right traversal and current node has a left descendant, action changed to left traversal. Otherwise action changed to visiting a node.
• If action is visiting node: current node is visited, afterwards its postorder successor has to be found.
• If current node’s parent accessible through a thread (i.e. current node is parent’s left child) then traversal is set to continue with the right descendant of parent.
• If current node has no right descendant, this is the end of the right-extended chain of nodes.
• First: the beginning of the chain is reached through the thread of the current node.
• Second: right references of nodes in the chain is reversed.
• Finally: chain is scanned backward, each node is visited, then right references are restored to previous settings.

 The code goes as follow
enum my_enum {LEFT_TRAVERSAL=0,RIGHT_TRAVERSAL,CURRENT_VISITING};
void chain_formation(struct node *tree)
{
    struct node *start_chain,*parent,*temp;
    parent=tree;
    start_chain=tree->left;
    if(start_chain->right==tree)
        printf("  %d  ",start_chain->info);
    while(start_chain->right!=tree)
    {
        temp=start_chain->right;
        start_chain->right=parent;
        parent=start_chain;
        start_chain=temp;
    }
    while(start_chain!=tree)
    {
        printf(" %d ",start_chain->info);
        temp=parent->right;
        start_chain=parent;
        parent=temp;
    }
      
}
void postorder(struct node *head_tree)
{
    enum my_enum traversal;
    struct node *tree,*parent;  
    tree=head_tree->left;
    printf("\n\n");
    traversal=LEFT_TRAVERSAL;
    int i=20;
    do
    {
        switch(traversal)
        {
            case LEFT_TRAVERSAL:
                        parent=tree;
                        while(tree->isleft!=0)
                        {
                            parent=tree;
                            tree=tree->left;
                        }
                        traversal=RIGHT_TRAVERSAL;
                        break;
            case RIGHT_TRAVERSAL:
                        if(tree->isright==0)
                        {
                            traversal=CURRENT_VISITING;
                            break;
                        }
                        parent=tree;
                        tree=tree->right;
                        if(tree->isleft==1)
                            traversal=LEFT_TRAVERSAL;
                        else if(tree->isright==1)
                            traversal=RIGHT_TRAVERSAL;
                        else
                            traversal=CURRENT_VISITING;
                        break;
            case CURRENT_VISITING:                  
                        if(parent->info>tree->info)
                        {
                            printf("  %d  ",tree->info);
                            tree=tree->right;
                            if(parent->isright==0)
                            {
                                parent=parent->right;
                                traversal=CURRENT_VISITING;
                            }
                            else
                                traversal=RIGHT_TRAVERSAL;
                        }
                        else
                        {
                            chain_formation(tree->right);
                            tree=tree->right;
                            if(tree->isright==0)
                                parent=tree->right;
                            traversal=RIGHT_TRAVERSAL;
                        }
                        break;
            default:
                        printf("\nWrong Input\n");
                        break;
      
        }
    }while(tree!=head_tree);
    printf("\n\n");
}