Queue using Linked List

 Write a program to implement a queue using a linked list.

#include<stdio.h>

struct node{

    int data;

    struct node *next;

};

struct node *front=NULL,*rear=NULL,*newnode,*ptr;

int value;

void insert(){

    newnode = (struct node*)malloc(sizeof(struct node));

    if(newnode==NULL){

        printf("Queue Overflow.");

        return;

    }

    printf("Enter a Value:");

    scanf("%d",&value);

    newnode->data = value;

    newnode->next = NULL;

    if(front==NULL)

        front=rear=newnode;

    else{

        rear->next = newnode;

        rear=newnode;

    }

}

void del(){

    if(front==NULL)

        printf("Queue underflow.");

    else{

        ptr=front;

        printf("%d is deleted.",ptr->data);

        if(front==rear)

            front=rear=NULL;

        else

            front=front->next;

        free(ptr);

    }

}

void display(){

    if(front==NULL){

        printf("Queue is Empty.");

        return;

    }

    printf("\nQueue is: ");

    for(ptr=front;ptr!=NULL;ptr=ptr->next)

        printf("%d ",ptr->data);

}

void main(){

    int ch;

    while(1){

        printf("\nQueue using Linked List");

        printf("\n1. Insert\n2. Delete\n3. Display\n4. Exit");

        printf("\nEnter your choice:");

        scanf("%d",&ch);

        switch(ch){

            case 1: insert();   break;

            case 2: del();  break;

            case 3: display();  break;

            case 4: exit(0);

            default: printf("Invalid Choice..");

        }

    }

}

Binary Search Tree

Write a program to implement a binary search tree where the user can perform:

(a) Insert a value in an existing tree.

(b) Delete a value from the tree

(c) Traverse a Tree: Pre-Order, In-Order, Post-Order.

#include<stdio.h>

#include<stdlib.h>

struct BST

{

    struct BST *lchild;

    int data;

    struct BST *rchild;

};

typedef struct BST node;

node *root=NULL, *temp;

void inorder(node *tree){

    if(tree!=NULL){

        inorder(tree->lchild);

        printf(" %d ",tree->data);

        inorder(tree->rchild);

    }

}

void preorder(node *tree){

    if(tree!=NULL){

        printf(" %d ",tree->data);

        preorder(tree->lchild);

        preorder(tree->rchild);

    }

}

void postorder(node *tree){

    if(tree!=NULL){

        postorder(tree->lchild);

        postorder(tree->rchild);

        printf(" %d ",tree->data);

    }

}

void insert(node *root, node *new_node)

{

    if(new_node->data < root->data)

    {

        if (root->lchild == NULL)

            root->lchild = new_node;

        else

            insert(root->lchild, new_node);

    }

    else if (new_node->data >= root->data)

    {

        if (root->rchild == NULL)

                root->rchild = new_node;

        else

                insert(root->rchild, new_node);

    }

}

void search(int val)

{

    node *temp=root;

    while (temp != NULL)

    {

        if (temp->data == val)

            break;

        if (temp->data > val)

            temp = temp->lchild;

        else

            temp = temp->rchild;

    }

    if(temp!=NULL)

            printf("Element %d is found\n",temp->data);

    else

            printf("\nElement %d is not found\n",val);

}

struct BST* deleteNode(struct BST* root, int val)

{

  if (root == NULL)

    return root;

  if (val < root->data)

    {

      root->lchild = deleteNode (root->lchild, val);

    }

  else if (val > root->data)

    {

      root->rchild = deleteNode (root->rchild, val);

    }

  else

    {

      if (root->lchild == NULL)

        {

            struct BST *temp = root->rchild;

            free (root);

            return temp;

        }

      else if (root->rchild == NULL)

        {

            struct BST *temp = root->lchild;

            free (root);

            return temp;

        }

      struct BST *temp = root->rchild;

      while (temp->lchild != NULL)

        {

            temp = temp->lchild;

        }

        root->data = temp->data;

        root->rchild = deleteNode (root->rchild, temp->data);

    }

  return root;

}

int main()

{

    int ch,val;

    node *new_node, *temp;

    printf("\nProgram For Binary Search Tree ");

    while(1)

    {

        printf("\n1.Insert an Element\n2.Search\n3.Recursive Traversals\n4.Delete a Node\n5. Exit");

        printf("\nEnter your Option : ");

        scanf("%d",&ch);

        switch(ch) {

            case 1: new_node = (node *)malloc(sizeof(node));

                    new_node->lchild=NULL;

                    new_node->rchild=NULL;

                    printf("\nEnter The Element : ");

                    scanf("%d", &new_node->data);

                    if(root == NULL)

                        root = new_node;

                    else

                        insert(root,new_node);

                    break;

            case 2: printf("\nEnter Element to be searched : ");

                    scanf("%d",&val);

                    search(val);

                    break;

            case 3: if(root == NULL)

                        printf("\nTree Is Not Created\n");

                    else{

                        printf("\nThe Inorder display : ");

                        inorder(root);

                        printf("\nThe Preorder display : ");

                        preorder(root);

                        printf("\nThe Postorder display : ");

                        postorder(root);

                    }

                    break;

            case 4: if(root==NULL)

                        printf("\nBST is EMPTY\n");

                    else{

                        printf("\nEnter the element to be deleted : ");

                        scanf("%d",&val);

                        root=deleteNode(root,val);

                    }

                    break;

            case 5: exit(0);

            default:

                    printf("\nINVALID CHOICE\n");

        }

    }

}

Stack using Linked List

Write a program to implement a stack using a linked list.

#include<stdio.h>

struct node{

    int data;

    struct node *next;

};

struct node *top=NULL,*ptr,*nn;

int value;

void push(){

    nn=(struct node*)malloc(sizeof(struct node));

    if(nn==NULL)

        printf("Stack Overflow.");

    else{

        printf("Enter a Value:");

        scanf("%d",&value);

        nn->data=value;

        nn->next = top;

        top=nn;

    }

}

void pop(){

    if(top==NULL)

        printf("Stack Underflow.");

    else{

        ptr=top;

        printf("%d is deleted.",top->data);

        top=top->next;

        free(ptr);

    }

}

void peep(){

    if(top==NULL)

        printf("Stack is Empty.");

    else

        printf("%d is Topmost Element.",top->data);

}

void display(){

    if(top==NULL)

        printf("Stack is Empty.");

    else{

        printf("Stack is: ");

        for(ptr=top;ptr!=NULL;ptr=ptr->next)

            printf("%d ",ptr->data);

    }

}

void main(){

    int choice;

    while(1){

            printf("\n\nStack using Linked List");

            printf("\n1. Push\n2. Pop\n3. Peep\n4. Display\n5. Exit");

            printf("\nEnter your choice:");

            scanf("%d",&choice);

            switch(choice){

                case 1: push();     

                               break;

                case 2: pop();      

                               break;

                case 3: peep();     

                               break;

                case 4: display();  

                               break;

                case 5: exit(0);

                default: printf("Invalid Choice..");

            }

    }

}

AES Implementation Code in C language | AES code in C | AES implmentation | AES Program

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

 

#define AES_RPOL      0x011b // reduction polynomial (x^8 + x^4 + x^3 + x + 1)

#define AES_GEN    0x03   // gf(2^8) generator  (x + 1)

#define AES_SBOX_CC   0x63   // S-Box C constant

 

#define KEY_128 (128/8)

#define KEY_192 (192/8)

#define KEY_256 (256/8)

 

#define aes_mul(a, b) ((a)&&(b)?g_aes_ilogt[(g_aes_logt[(a)]+g_aes_logt[(b)])%0xff]:0)

#define aes_inv(a)  ((a)?g_aes_ilogt[0xff-g_aes_logt[(a)]]:0)

 

unsigned char g_aes_logt[256], g_aes_ilogt[256];

unsigned char g_aes_sbox[256], g_aes_isbox[256];

 

typedef struct {

    unsigned char state[4][4];

    int kcol;

    size_t rounds;

    unsigned long keysched[0];

} aes_ctx_t;

 

void aes_init();

aes_ctx_t *aes_alloc_ctx(unsigned char *key, size_t keyLen);

inline unsigned long aes_subword(unsigned long w);

inline unsigned long aes_rotword(unsigned long w);

void aes_keyexpansion(aes_ctx_t *ctx);

 

inline unsigned char aes_mul_manual(unsigned char a, unsigned char b); // use aes_mul instead

 

void aes_subbytes(aes_ctx_t *ctx);

void aes_shiftrows(aes_ctx_t *ctx);

void aes_mixcolumns(aes_ctx_t *ctx);

void aes_addroundkey(aes_ctx_t *ctx, int round);

void aes_encrypt(aes_ctx_t *ctx, unsigned char input[16], unsigned char output[16]);

 

void aes_invsubbytes(aes_ctx_t *ctx);

void aes_invshiftrows(aes_ctx_t *ctx);

void aes_invmixcolumns(aes_ctx_t *ctx);

void aes_decrypt(aes_ctx_t *ctx, unsigned char input[16], unsigned char output[16]);

 

void aes_free_ctx(aes_ctx_t *ctx);

 

void init_aes()

{

    int i;

    unsigned char gen;

 

    // build logarithm table and it's inverse

    gen = 1;

    for(i = 0; i < 0xff; i++) {

        g_aes_logt[gen]  = i;

        g_aes_ilogt[i]   = gen;

        gen = aes_mul_manual(gen, AES_GEN);

    }

 

    // build S-Box and it's inverse

    for(i = 0; i <= 0xff; i++) {

        char bi;

        unsigned char inv = aes_inv(i);

 

        g_aes_sbox[i] = 0;

        for(bi = 0; bi < 8; bi++) {

            // based on transformation 5.1

            // could also be done with a loop based on the matrix

            g_aes_sbox[i] |= ((inv & (1<<bi)?1:0)

                        ^ (inv & (1 << ((bi+4) & 7))?1:0)

                        ^ (inv & (1 << ((bi+5) & 7))?1:0)

                        ^ (inv & (1 << ((bi+6) & 7))?1:0)

                        ^ (inv & (1 << ((bi+7) & 7))?1:0)

                        ^ (AES_SBOX_CC & (1 << bi)?1:0)

            ) << bi;

        }

        g_aes_isbox[g_aes_sbox[i]] = i;

    }

    // warning: quickhack

    g_aes_sbox[1] = 0x7c;

    g_aes_isbox[0x7c] = 1;

    g_aes_isbox[0x63] = 0;

}

 

aes_ctx_t *aes_alloc_ctx(unsigned char *key, size_t keyLen)

{

    aes_ctx_t *ctx;

    size_t rounds;

    size_t ks_size;

 

    switch(keyLen) {

        case 16: // 128-bit key

            rounds = 10;

            break;

 

        case 24: // 192-bit key

            rounds = 12;

            break;

 

        case 32: // 256-bit key

            rounds = 14;

            break;

 

        defaut:

            return NULL;

    }

 

    ks_size = 4*(rounds+1)*sizeof(unsigned long);

    ctx = malloc(sizeof(aes_ctx_t)+ks_size);

    if(ctx) {

        ctx->rounds = rounds;

        ctx->kcol = keyLen/4;

        memcpy(ctx->keysched, key, keyLen);

        ctx->keysched[43] = 0;

        aes_keyexpansion(ctx);

    }

 

    return ctx;

}

 

inline unsigned long aes_subword(unsigned long w)

{

    return g_aes_sbox[w & 0x000000ff] |

        (g_aes_sbox[(w & 0x0000ff00) >> 8] << 8) |

        (g_aes_sbox[(w & 0x00ff0000) >> 16] << 16) |

        (g_aes_sbox[(w & 0xff000000) >> 24] << 24);

}

 

inline unsigned long aes_rotword(unsigned long w)

{

    // May seem a bit different from the spec

    // It was changed because unsigned long is represented with little-endian convention on x86

    // Should not depend on architecture, but this is only a POC

    return ((w & 0x000000ff) << 24) |

        ((w & 0x0000ff00) >> 8) |

        ((w & 0x00ff0000) >> 8) |

        ((w & 0xff000000) >> 8);

}

 

void aes_keyexpansion(aes_ctx_t *ctx)

{

    unsigned long temp;

    unsigned long rcon;

    register int i;

 

    rcon = 0x00000001;

    for(i = ctx->kcol; i < (4*(ctx->rounds+1)); i++) {

        temp = ctx->keysched[i-1];

        if(!(i%ctx->kcol)) {

            temp = aes_subword(aes_rotword(temp)) ^ rcon;

            rcon = aes_mul(rcon, 2);

        } else if(ctx->kcol > 6 && i%ctx->kcol == 4)

            temp = aes_subword(temp);

        ctx->keysched[i] = ctx->keysched[i-ctx->kcol] ^ temp;

    }

}

 

inline unsigned char aes_mul_manual(unsigned char a, unsigned char b)

{

    register unsigned short ac;

    register unsigned char ret;

 

    ac = a;

    ret = 0;

    while(b) {

        if(b & 0x01)

            ret ^= ac;

        ac <<= 1;

        b >>= 1;

        if(ac & 0x0100)

            ac ^= AES_RPOL;

    }

 

    return ret;

}

 

void aes_subbytes(aes_ctx_t *ctx)

{

    int i;

 

    for(i = 0; i < 16; i++) {

        int x, y;

 

        x = i & 0x03;

        y = i >> 2;

        ctx->state[x][y] = g_aes_sbox[ctx->state[x][y]];

    }

}

 

void aes_shiftrows(aes_ctx_t *ctx)

{

    unsigned char nstate[4][4];

    int i;

 

    for(i = 0; i < 16; i++) {

        int x, y;

 

        x = i & 0x03;

        y = i >> 2;

        nstate[x][y] = ctx->state[x][(y+x) & 0x03];

    }

 

    memcpy(ctx->state, nstate, sizeof(ctx->state));

}

 

void aes_mixcolumns(aes_ctx_t *ctx)

{

    unsigned char nstate[4][4];

    int i;

     

    for(i = 0; i < 4; i++) {

        nstate[0][i] = aes_mul(0x02, ctx->state[0][i]) ^

                aes_mul(0x03, ctx->state[1][i]) ^

                ctx->state[2][i] ^

                ctx->state[3][i];

        nstate[1][i] = ctx->state[0][i] ^

                aes_mul(0x02, ctx->state[1][i]) ^

                aes_mul(0x03, ctx->state[2][i]) ^

                ctx->state[3][i];

        nstate[2][i] = ctx->state[0][i] ^

                ctx->state[1][i] ^

                aes_mul(0x02, ctx->state[2][i]) ^

                aes_mul(0x03, ctx->state[3][i]);

        nstate[3][i] = aes_mul(0x03, ctx->state[0][i]) ^

                ctx->state[1][i] ^

                ctx->state[2][i] ^

                aes_mul(0x02, ctx->state[3][i]);

    }

 

    memcpy(ctx->state, nstate, sizeof(ctx->state));

}

 

void aes_addroundkey(aes_ctx_t *ctx, int round)

{

    int i;

 

    for(i = 0; i < 16; i++) {

        int x, y;

 

        x = i & 0x03;

        y = i >> 2;

        ctx->state[x][y] = ctx->state[x][y] ^

            ((ctx->keysched[round*4+y] & (0xff << (x*8))) >> (x*8));

    }

}

 

void aes_encrypt(aes_ctx_t *ctx, unsigned char input[16], unsigned char output[16])

{

    int i;

 

    // copy input to state

    for(i = 0; i < 16; i++)

        ctx->state[i & 0x03][i >> 2] = input[i];

 

    aes_addroundkey(ctx, 0);

 

    for(i = 1; i < ctx->rounds; i++) {

        aes_subbytes(ctx);

        aes_shiftrows(ctx);

        aes_mixcolumns(ctx);

        aes_addroundkey(ctx, i);

    }

 

    aes_subbytes(ctx);

    aes_shiftrows(ctx);

    aes_addroundkey(ctx, ctx->rounds);

 

    // copy state to output

    for(i = 0; i < 16; i++)

        output[i] = ctx->state[i & 0x03][i >> 2];

}

 

void aes_invshiftrows(aes_ctx_t *ctx)

{

    unsigned char nstate[4][4];

    int i;

 

    for(i = 0; i < 16; i++) {

        int x, y;

 

        x = i & 0x03;

        y = i >> 2;

        nstate[x][(y+x) & 0x03] = ctx->state[x][y];

    }

 

    memcpy(ctx->state, nstate, sizeof(ctx->state));

}

 

void aes_invsubbytes(aes_ctx_t *ctx)

{

    int i;

 

    for(i = 0; i < 16; i++) {

        int x, y;

 

        x = i & 0x03;

        y = i >> 2;

        ctx->state[x][y] = g_aes_isbox[ctx->state[x][y]];

    }

}

 

void aes_invmixcolumns(aes_ctx_t *ctx)

{

    unsigned char nstate[4][4];

    int i;

     

    for(i = 0; i < 4; i++) {

        nstate[0][i] = aes_mul(0x0e, ctx->state[0][i]) ^

                aes_mul(0x0b, ctx->state[1][i]) ^

                aes_mul(0x0d, ctx->state[2][i]) ^

                aes_mul(0x09, ctx->state[3][i]);

        nstate[1][i] = aes_mul(0x09, ctx->state[0][i]) ^

                aes_mul(0x0e, ctx->state[1][i]) ^

                aes_mul(0x0b, ctx->state[2][i]) ^

                aes_mul(0x0d, ctx->state[3][i]);

        nstate[2][i] = aes_mul(0x0d, ctx->state[0][i]) ^

                aes_mul(0x09, ctx->state[1][i]) ^

                aes_mul(0x0e, ctx->state[2][i]) ^

                aes_mul(0x0b, ctx->state[3][i]);

        nstate[3][i] = aes_mul(0x0b, ctx->state[0][i]) ^

                aes_mul(0x0d, ctx->state[1][i]) ^

                aes_mul(0x09, ctx->state[2][i]) ^

                aes_mul(0x0e, ctx->state[3][i]);

    }

 

    memcpy(ctx->state, nstate, sizeof(ctx->state));

}

 

void aes_decrypt(aes_ctx_t *ctx, unsigned char input[16], unsigned char output[16])

{

    int i, j;

 

    // copy input to state

    for(i = 0; i < 16; i++)

        ctx->state[i & 0x03][i >> 2] = input[i];

 

    aes_addroundkey(ctx, ctx->rounds);

    for(i = ctx->rounds-1; i >= 1; i--) {

        aes_invshiftrows(ctx);

        aes_invsubbytes(ctx);

        aes_addroundkey(ctx, i);

        aes_invmixcolumns(ctx);

    }

 

    aes_invshiftrows(ctx);

    aes_invsubbytes(ctx);

    aes_addroundkey(ctx, 0);

 

    // copy state to output

    for(i = 0; i < 16; i++)

        output[i] = ctx->state[i & 0x03][i >> 2];

}

 

void aes_free_ctx(aes_ctx_t *ctx)

{

    free(ctx);

}

 

int main(int argc, char *argv[])

{

    unsigned char key[KEY_128] = "uber strong key!";

    unsigned char ptext[16] = "Attack at dawn!";

    unsigned char ctext[16];

    unsigned char decptext[16];

    aes_ctx_t *ctx;

 

    init_aes();

    ctx = aes_alloc_ctx(key, sizeof(key));

    if(!ctx) {

        perror("aes_alloc_ctx");

        return EXIT_FAILURE;

    }

    aes_encrypt(ctx, ptext, ctext);

    aes_decrypt(ctx, ctext, decptext);

    puts(decptext);

 

    aes_free_ctx(ctx);

    return EXIT_SUCCESS;

}




In the attached zip you will also find the compiled ELF binary. - Click here