Tuesday 31 May 2016

C code to Encrypt & Decrypt Message using Transposition Cipher



C-code-to-encrypt-and-decrypt-a-message-using-Transposition-cipher
C-code-to-encrypt-and-decrypt-a-message-using-Transposition-cipher-2

C Program

  1. #include<stdio.h>
  2. #include<string.h>
  3. void cipher(int i,int c);
  4. int findMin();
  5. void makeArray(int,int);
  6. char arr[22][22],darr[22][22],emessage[111],retmessage[111],key[55];
  7. char temp[55],temp2[55];
  8. int k=0;
  9. int main() {
  10. char *message,*dmessage;
  11. int i,j,klen,emlen,flag=0;
  12. int r,c,index,min,rows;
  13. clrscr();
  14. printf("Enetr the key\n");
  15. fflush(stdin);
  16. gets(key);
  17. printf("\nEnter message to be ciphered\n");
  18. fflush(stdin);
  19. gets(message);
  20. strcpy(temp,key);
  21. klen=strlen(key);
  22. k=0;
  23. for (i=0; ;i++) {
  24. if(flag==1)
  25. break;
  26. for (j=0;key[j]!=NULL;j++) {
  27. if(message[k]==NULL) {
  28. flag=1;
  29. arr[i][j]='-';
  30. } else {
  31. arr[i][j]=message[k++];
  32. }
  33. }
  34. }
  35. r=i;
  36. c=j;
  37. for (i=0;i<r;i++) {
  38. for (j=0;j<c;j++) {
  39. printf("%c ",arr[i][j]);
  40. }
  41. printf("\n");
  42. }
  43. k=0;
  44. for (i=0;i<klen;i++) {
  45. index=findMin();
  46. cipher(index,r);
  47. }
  48. emessage[k]='\0';
  49. printf("\nEncrypted message is\n");
  50. for (i=0;emessage[i]!=NULL;i++)
  51. printf("%c",emessage[i]);
  52. printf("\n\n");
  53. //deciphering
  54. emlen=strlen(emessage);
  55. //emlen is length of encrypted message
  56. strcpy(temp,key);
  57. rows=emlen/klen;
  58. //rows is no of row of the array to made from ciphered message
  59. rows;
  60. j=0;
  61. for (i=0,k=1;emessage[i]!=NULL;i++,k++) {
  62. //printf("\nEmlen=%d",emlen);
  63. temp2[j++]=emessage[i];
  64. if((k%rows)==0) {
  65. temp2[j]='\0';
  66. index=findMin();
  67. makeArray(index,rows);
  68. j=0;
  69. }
  70. }
  71. printf("\nArray Retrieved is\n");
  72. k=0;
  73. for (i=0;i<r;i++) {
  74. for (j=0;j<c;j++) {
  75. printf("%c ",darr[i][j]);
  76. //retrieving message
  77. retmessage[k++]=darr[i][j];
  78. }
  79. printf("\n");
  80. }
  81. retmessage[k]='\0';
  82. printf("\nMessage retrieved is\n");
  83. for (i=0;retmessage[i]!=NULL;i++)
  84. printf("%c",retmessage[i]);
  85. getch();
  86. return(0);
  87. }
  88. void cipher(int i,int r) {
  89. int j;
  90. for (j=0;j<r;j++) { {
  91. emessage[k++]=arr[j][i];
  92. }
  93. }
  94. // emessage[k]='\0';
  95. }
  96. void makeArray(int col,int row) {
  97. int i,j;
  98. for (i=0;i<row;i++) {
  99. darr[i][col]=temp2[i];
  100. }
  101. }
  102. int findMin() {
  103. int i,j,min,index;
  104. min=temp[0];
  105. index=0;
  106. for (j=0;temp[j]!=NULL;j++) {
  107. if(temp[j]<min) {
  108. min=temp[j];
  109. index=j;
  110. }
  111. }
  112. temp[index]=123;
  113. return(index);
  114. }

Monday 30 May 2016

Memory Layout of C Programs


A typical memory representation of C program consists of following sections.
1. Text segment
2. Initialized data segment
3. Uninitialized data segment
4. Stack
5. Heap

A typical memory layout of a running process
1. Text Segment:
A text segment , also known as a code segment or simply as text, is one of the sections of a program in an object file or in memory, which contains executable instructions.
As a memory region, a text segment may be placed below the heap or stack in order to prevent heaps and stack overflows from overwriting it.
Usually, the text segment is sharable so that only a single copy needs to be in memory for frequently executed programs, such as text editors, the C compiler, the shells, and so on. Also, the text segment is often read-only, to prevent a program from accidentally modifying its instructions.
2. Initialized Data Segment:
Initialized data segment, usually called simply the Data Segment. A data segment is a portion of virtual address space of a program, which contains the global variables and static variables that are initialized by the programmer.
Note that, data segment is not read-only, since the values of the variables can be altered at run time.
This segment can be further classified into initialized read-only area and initialized read-write area.
For instance 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.
Ex: static int i = 10 will be stored in data segment and global int i = 10 will also be stored in data segment
3. Uninitialized Data Segment:
Uninitialized data segment, often called the “bss” segment, named after an ancient assembler operator that stood for “block started by symbol.” Data in this segment is initialized by the kernel to arithmetic 0 before the program starts executing
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 instance a variable declared static int i; would be contained in the BSS segment.
For instance a global variable declared int j; would be contained in the BSS segment.
4. Stack:
The stack area traditionally adjoined the heap area and grew the opposite direction; when the stack pointer met the heap pointer, free memory was exhausted. (With modern large address spaces and virtual memory techniques they may be placed almost anywhere, but they still typically grow opposite directions.)
The stack area contains the program stack, a LIFO structure, typically located in the higher parts of memory. 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. The set of values pushed for one function call is termed a “stack frame”; A stack frame consists at minimum of a return address.
Stack, where automatic variables are stored, along with information that is saved each time a function is called. Each time a function is called, the address of where to return to and certain information about the caller’s environment, such as some of the machine registers, are saved on the stack. The newly called function then allocates room on the stack for its automatic and temporary variables. This is how recursive functions in C can work. Each time a recursive function calls itself, a new stack frame is used, so one set of variables doesn’t interfere with the variables from another instance of the function.
5. Heap:
Heap is the segment where dynamic memory allocation usually takes place.
The heap area begins at the end of the BSS segment and grows to larger addresses from there.The Heap area is managed by malloc, realloc, and free, which may use the brk and sbrk system calls to adjust its size (note that the use of brk/sbrk and a single “heap area” is not required to fulfill the contract of malloc/realloc/free; they may also be implemented using mmap to reserve potentially non-contiguous regions of virtual memory into the process’ virtual address space). The Heap area is shared by all shared libraries and dynamically loaded modules in a process.
Examples.
The size(1) command reports the sizes (in bytes) of the text, data, and bss segments. ( for more details please refer man page of size(1) )
1. Check the following simple C program
#include <stdio.h>

int main(void)
{
    return 0;
}
[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
960        248          8       1216        4c0    memory-layout
2. Let us add one global variable in program, now check the size of bss (highlighted in red color).
#include <stdio.h>

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

int main(void)
{
    return 0;
}
[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
 960        248         12       1220        4c4    memory-layout
3. Let us add one static variable which is also stored in bss.
#include <stdio.h>

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

int main(void)
{
    static int i; /* Uninitialized static variable stored in bss */
    return 0;
}
[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
 960        248         16       1224        4c8    memory-layout
4. Let us initialize the static variable which will then be stored in Data Segment (DS)
#include <stdio.h>

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

int main(void)
{
    static int i = 100; /* Initialized static variable stored in DS*/
    return 0;
}
[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
960         252         12       1224        4c8    memory-layout
5. Let us initialize the global variable which will then be stored in Data Segment (DS)
#include <stdio.h>

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

int main(void)
{
    static int i = 100; /* Initialized static variable stored in DS*/
    return 0;
}
[narendra@CentOS]$ gcc memory-layout.c -o memory-layout
[narendra@CentOS]$ size memory-layout
text       data        bss        dec        hex    filename
960         256          8       1224        4c8    memory-layout
This article is compiled by Narendra Kangralkar. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Write an Efficient C Program to Reverse Bits of a Number

Method1 – Simple
Loop through all the bits of an integer. If a bit at ith position is set in the i/p no. then set the bit at (NO_OF_BITS – 1) – i in o/p. Where NO_OF_BITS is number of bits present in the given number.
/* Function to reverse bits of num */
unsigned int reverseBits(unsigned int num)
{
    unsigned int  NO_OF_BITS = sizeof(num) * 8;
    unsigned int reverse_num = 0, i, temp;
 
    for (i = 0; i < NO_OF_BITS; i++)
    {
        temp = (num & (1 << i));
        if(temp)
            reverse_num |= (1 << ((NO_OF_BITS - 1) - i));
    }
  
    return reverse_num;
}
 
/* Driver function to test above function */
int main()
{
    unsigned int x = 2;
    printf("%u", reverseBits(x));
    getchar();
}
Above program can be optimized by removing the use of variable temp. See below the modified code.
unsigned int reverseBits(unsigned int num)
{
    unsigned int  NO_OF_BITS = sizeof(num) * 8;
    unsigned int reverse_num = 0;
    int i;
    for (i = 0; i < NO_OF_BITS; i++)
    {
        if((num & (1 << i)))
           reverse_num |= 1 << ((NO_OF_BITS - 1) - i); 
   }
    return reverse_num;
}
Time Complexity: O(log n)
Space Complexity: O(1)
Method 2 – Standard
The idea is to keep putting set bits of the num in reverse_num until num becomes zero. After num becomes zero, shift the remaining bits of reverse_num.
Let num is stored using 8 bits and num be 00000110. After the loop you will get reverse_num as 00000011. Now you need to left shift reverse_num 5 more times and you get the exact reverse 01100000.
unsigned int reverseBits(unsigned int num)
{
    unsigned int count = sizeof(num) * 8 - 1;
    unsigned int reverse_num = num;
     
    num >>= 1;
    while(num)
    {
       reverse_num <<= 1;      
       reverse_num |= num & 1;
       num >>= 1;
       count--;
    }
    reverse_num <<= count;
    return reverse_num;
}
 
int main()
{
    unsigned int x = 1;
    printf("%u", reverseBits(x));
    getchar();
}
Time Complexity: O(log n)
Space Complexity: O(1)