Tuesday, April 24, 2012

Implementing car and cdr in Scheme


;;;;#########Implimenting Set-car and set cdr######;;;;;
(define (cons! x y)
 (define (set-x! v) (set! x v))
 (define (set-y! v) (set! y v))
 (define (dispatch m)
  (cond   ((eq? m 'car) x)
   ((eq? m 'cdr) y)
   ((eq? m 'set-car) set-x!)
   ((eq? m 'set-cdr) set-y!)
   (else 'error)
  )

 )
 dispatch
)

(define (car! z)
 (z 'car)
)

(define (cdr! z)
 (z 'cdr)
)

(define (set-car z v)
 ((z 'set-car) v)
)


(define (set-cdr z v)
 ((z 'set-cdr) v)
)

Summation and Integration functions in Scheme(Higher Order Procedures)


;;######################----------------------##################33

;Higher order Procedures....
;Function for summation
(define (sigma fn a b)
  (if (> a b)
 0
 (+  (fn a)
  (sigma (+ a 1) b)
 )
  )

)

;Function for integration
(define (integral2 fn a b dx)
    (if (> a b)
 0
 (+   (fn (+ a (/ dx 2)))
      (integral fn (+ a dx) b dx)

 )
    )
)

(define (integral fn a b)
    (integral2 fn a b 0.001)
)

Checking Prime Numbers in Scheme


;Function to check whether a given number is prime

(define (prime? n)
    (test-prime n 2)
)

(define (factor a b)
  (= (modulo a b) 0)
)

(define (test-prime n test-no)
  (if (> test-no (/ n 2))
      #t
      (if (factor n test-no)
   #f
   (test-prime n (+ test-no 1))
      )
  )
)

Sum of first n natural numbers NASM (Assembly)


section .data
  message: db "Enter a two digit number : "
  message_length: equ $-message


section .bss
  digit1: resb  1
  digit2: resb  1
  digit3: resb  1
  digit4: resb  1
  num:    resb 1
  num1:   resb 1
  num2:   resb 1
  sum:   resw 1

section .text
  global _start

_start:

  mov eax, 4
  mov ebx, 1
  mov ecx, message
  mov edx, message_length
  int 80h
  
  ;Reding first digit
  mov eax, 3
  mov ebx, 0
  mov ecx, digit1
  mov edx, 1
  int 80h

  ;Reading second digit
  mov eax, 3
  mov ebx, 0
  mov ecx, digit2
  mov edx, 2
  int 80h

  sub byte[digit1], 30h
  sub byte[digit2], 30h

  movzx ax, byte[digit1]
  mov bl, 10
  mul bl
  movzx bx, byte[digit2]
  add ax, bx
  mov byte[num], al ;We are sure that no less than 256...
  
  mov word[sum], 0
  movzx ecx, byte[num]

;Loop for adding ecx to num
adding:
  add word[sum], cx ; Assuming maxium vale in ecx will use only 16 bits
Loop adding

  mov ax, word[sum]
  mov bl, 100
  div bl
  mov byte[num1], al
  mov byte[num2], ah


  movzx ax, byte[num1]
  mov bl, 10
  div bl
  mov byte[digit4], al
  mov byte[digit3], ah

  movzx ax, byte[num2]
  mov bl, 10
  div bl
  mov byte[digit2], al
  mov byte[digit1], ah


  add byte[digit1], 30h
  add byte[digit2], 30h
  add byte[digit3], 30h
  add byte[digit4], 30h


  mov eax, 4
  mov ebx, 1
  mov ecx, digit4
  mov edx, 1
  int 80h

  mov eax, 4
  mov ebx, 1
  mov ecx, digit3
  mov edx, 1
  int 80h

  mov eax, 4
  mov ebx, 1
  mov ecx, digit2
  mov edx, 1
  int 80h

  mov eax, 4
  mov ebx, 1
  mov ecx, digit1
  mov edx, 1
  int 80h  
  

  ;Exit code
  mov eax, 1
  mov ebx, 0
  int 80h 


Searching an array for an element in NASM (Assembly)


section .bss
  digit0: resb 1
  digit1: resb 1
  array:  resb 50
  element: resb 1
  num: resb 1
  pos: resb 1
  temp: resb 1
  ele: resb 1



section .data

msg1: db "Enter the number of numbers : "
size1: equ $-msg1
msg2: db "Enter a number:"
size2: equ $-msg2
msg3: db "Enter the number to be searched : "
size3: equ $-msg3
msg_found: db "Element found at position : "
size_found: equ $-msg_found
msg_not: db "Element not found"
size_not: equ $-msg_not

section .text
  global _start

_start:
  

;Printing the message to enter the number
  mov eax, 4
  mov ebx, 1
  mov ecx, msg1
  mov edx, size1
  int 80h
  
  ;Reading the number
  mov eax, 3
  mov ebx, 0
  mov ecx, digit1
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, digit0
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, temp
  mov edx, 1
  int 80h

  sub byte[digit1], 30h
  sub byte[digit0], 30h  

  mov al, byte[digit1]
  mov dl, 10
  mul dl
  mov byte[num], al
  mov al, byte[digit0]
  add byte[num], al
  mov al, byte[num]

  mov byte[temp], al

  mov ebx, array
  

reading:
  
  push ebx

  ;Printing the message to enter the numbers
  mov eax, 4
  mov ebx, 1
  mov ecx, msg2
  mov edx, size2
  int 80h
  
  ;Reading the number
  mov eax, 3
  mov ebx, 0
  mov ecx, digit1
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, digit0
  mov edx, 2
  int 80h

  sub byte[digit1], 30h
  sub byte[digit0], 30h  
  mov al, byte[digit1]
  mov dl, 10
  mul dl
  add al, byte[digit0]

  ;al now contains the number
  pop ebx

  mov byte[ebx], al

  add ebx, 1

  dec byte[temp]
  cmp byte[temp], 0

jg reading

  ;Reading the number to be searched :.....

  mov eax, 4
  mov ebx, 1
  mov ecx, msg3
  mov edx, size3
  int 80h
  
  ;Reading the number
  mov eax, 3
  mov ebx, 0
  mov ecx, digit1
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, digit0
  mov edx, 2
  int 80h

  sub byte[digit1], 30h
  sub byte[digit0], 30h  
  mov al, byte[digit1]
  mov dl, 10
  mul dl
  add al, byte[digit0]

  mov byte[ele], al

  
  movzx ecx, byte[num]

  mov ebx, array
  mov byte[pos], 1

searching:

  
  push ecx
 
  mov al , byte[ebx]

  cmp al, byte[ele]
  je found

  add ebx, 1

  pop ecx
  add byte[pos], 1

loop searching
  
  
  mov eax, 4
  mov ebx, 1
  mov ecx, msg_not
  mov edx, size_not
  int 80h

exit:
  mov eax, 1
  mov ebx, 0
  int 80h


found:
  mov eax, 4
  mov ebx, 1
  mov ecx, msg_found
  mov edx, size_found
  int 80h
  
  movzx ax, byte[pos]
  mov bl, 10
  div bl
  mov byte[digit1], al
  mov byte[digit0], ah

  add byte[digit0], 30h
  add byte[digit1], 30h

  mov eax, 4
  mov ebx, 1
  mov ecx, digit1
  mov edx, 1
  int 80h

  mov eax, 4
  mov ebx, 1
  mov ecx, digit0
  mov edx, 1
  int 80h
  jmp exit
  
  
  
  
  
  
  
  
  
  
  
  section .bss
  digit0: resb 1
  digit1: resb 1
  array:  resb 50
  element: resb 1
  num: resb 1
  pos: resb 1
  temp: resb 1
  ele: resb 1



section .data

msg1: db "Enter the number of numbers : "
size1: equ $-msg1
msg2: db "Enter a number:"
size2: equ $-msg2
msg3: db "Enter the number to be searched : "
size3: equ $-msg3
msg_found: db "Element found at position : "
size_found: equ $-msg_found
msg_not: db "Element not found"
size_not: equ $-msg_not

section .text
  global _start

_start:
  

;Printing the message to enter the number
  mov eax, 4
  mov ebx, 1
  mov ecx, msg1
  mov edx, size1
  int 80h
  
  ;Reading the number
  mov eax, 3
  mov ebx, 0
  mov ecx, digit1
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, digit0
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, temp
  mov edx, 1
  int 80h

  sub byte[digit1], 30h
  sub byte[digit0], 30h  

  mov al, byte[digit1]
  mov dl, 10
  mul dl
  mov byte[num], al
  mov al, byte[digit0]
  add byte[num], al
  mov al, byte[num]

  mov byte[temp], al

  mov ebx, array
  

reading:
  
  push ebx

  ;Printing the message to enter the numbers
  mov eax, 4
  mov ebx, 1
  mov ecx, msg2
  mov edx, size2
  int 80h
  
  ;Reading the number
  mov eax, 3
  mov ebx, 0
  mov ecx, digit1
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, digit0
  mov edx, 2
  int 80h

  sub byte[digit1], 30h
  sub byte[digit0], 30h  
  mov al, byte[digit1]
  mov dl, 10
  mul dl
  add al, byte[digit0]

  ;al now contains the number
  pop ebx

  mov byte[ebx], al

  add ebx, 1

  dec byte[temp]
  cmp byte[temp], 0

jg reading

  ;Reading the number to be searched :.....

  mov eax, 4
  mov ebx, 1
  mov ecx, msg3
  mov edx, size3
  int 80h
  
  ;Reading the number
  mov eax, 3
  mov ebx, 0
  mov ecx, digit1
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, digit0
  mov edx, 2
  int 80h

  sub byte[digit1], 30h
  sub byte[digit0], 30h  
  mov al, byte[digit1]
  mov dl, 10
  mul dl
  add al, byte[digit0]

  mov byte[ele], al

  
  movzx ecx, byte[num]

  mov ebx, array
  mov byte[pos], 1

searching:

  
  push ecx
 
  mov al , byte[ebx]

  cmp al, byte[ele]
  je found

  add ebx, 1

  pop ecx
  add byte[pos], 1

loop searching
  
  
  mov eax, 4
  mov ebx, 1
  mov ecx, msg_not
  mov edx, size_not
  int 80h

exit:
  mov eax, 1
  mov ebx, 0
  int 80h


found:
  mov eax, 4
  mov ebx, 1
  mov ecx, msg_found
  mov edx, size_found
  int 80h
  
  movzx ax, byte[pos]
  mov bl, 10
  div bl
  mov byte[digit1], al
  mov byte[digit0], ah

  add byte[digit0], 30h
  add byte[digit1], 30h

  mov eax, 4
  mov ebx, 1
  mov ecx, digit1
  mov edx, 1
  int 80h

  mov eax, 4
  mov ebx, 1
  mov ecx, digit0
  mov edx, 1
  int 80h
  jmp exit

Checking whether a given string is palindrome in NASM (Assembly)


section .data
  msg1: db "Enter the string : "
  size1: equ $-msg1
  msg2: db " is pallindrome "
  size2: equ $-msg2
  msg3: db " is not pallindrome "
  size3: equ $-msg3


section .bss
  string: resb 50
  temp: resb 1
  len:  resb 1
  j: resb 1
  i: resb 1


section .text
  global _start

_start:
  
  mov eax, 4
  mov ebx, 1
  mov ecx, msg1
  mov edx, size1
  int 80h

  mov ebx, string
  mov byte[len], 0

reading:
  push ebx

  mov eax, 3
  mov ebx, 0
  mov ecx, temp
  mov edx, 1
  int 80h
  
  pop ebx
  mov al, byte[temp]
  mov byte[ebx], al
  
  inc byte[len]
  inc ebx

  ;NASM change the ascii code of enter 13 to 10
  cmp byte[temp], 10
  jne reading


endreading:
  dec ebx
  mov byte[ebx],0
  dec byte[len]




;Printing the string....
  mov eax, 4
  mov ebx, 1
  mov ecx, string
  movzx edx, byte[len]
  int 80h

  mov byte[i], 0
  mov al, byte[len]
  mov byte[j], al
  sub byte[j], 1

pal_check:
  mov eax, string
  mov ebx, string
  movzx ecx, byte[i]
  add eax, ecx
  movzx ecx, byte[j]
  add ebx, ecx
  mov cl, byte[eax]
  mov ch, byte[ebx]
  cmp cl, ch
  jne not_pal

  inc byte[i]
  dec byte[j]
  mov al, byte[i]
  mov ah, byte[j]
  cmp al,ah
  jl pal_check


  mov eax, 4
  mov ebx, 1
  mov ecx, msg2
  mov edx, size2
  int 80h
  jmp exit

not_pal:
  mov eax, 4
  mov ebx, 1
  mov ecx, msg3
  mov edx, size3
  int 80h


exit:
  mov eax, 1
  mov ebx, 0
  int 80h

Factorial Function in NASM (Recursive Algorithm)


section .bss

  digit0: resb 1
  digit1: resb 1
  digit2: resb 1
  digit3: resb 1
  digit4: resb 1
  temp: resb 1
  num: resb 1
  n: resw 1
  nod: resb 1
  num1: resb 1
  num2: resb 1
  factorial: resw 1


section .data

msg1: db "Enter the number : "
size1: equ $-msg1
msg2: db "Enter a number:"
size2: equ $-msg2
msg3: db "Sorted Array : "
size3: equ $-msg3


section .text
  global _start

_start:
  


;Printing the message to enter the number
  mov eax, 4
  mov ebx, 1
  mov ecx, msg1
  mov edx, size1
  int 80h
  
  ;Reading the number
  mov eax, 3
  mov ebx, 0
  mov ecx, digit1
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, digit0
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, temp
  mov edx, 1
  int 80h

  sub byte[digit1], 30h
  sub byte[digit0], 30h  

  mov al, byte[digit1]
  mov dl, 10
  mul dl
  mov byte[num], al
  mov al, byte[digit0]
  add byte[num], al
  mov al, byte[num]
  mov ah,0
  mov word[n], ax
  ;num contains the numbers


call fact

mov word[factorial], cx


  
mov ax, word[factorial]

  mov word[num], ax
  mov byte[nod], 0 ;No of digits...
 

extract_no:

  cmp word[num], 0
  je print_no
  inc byte[nod]
  mov dx, 0
  mov ax, word[num]
  mov bx, 10
  div bx
  push dx
  mov word[num], ax
  jmp extract_no

print_no:
  cmp byte[nod], 0
  je end_print
  dec byte[nod]
  pop dx
  mov byte[temp], dl
  add byte[temp], 30h


  mov eax, 4
  mov ebx, 1
  mov ecx, temp
  mov edx, 1
  int 80h

  jmp print_no
end_print:  


mov eax, 1
mov ebx, 0
int 80h



fact:
  
  mov ax, word[n]
  cmp ax, 1
  je terminate
  push word[n]

  dec word[n]
  call fact

  pop word[n]
  mov dx, word[n]

  mov ax, cx
  mul dx
  mov cx, ax
  jmp exit
  
terminate:
  mov cx, 1

exit:
  ret


Bubble Sorting in NASM (Assembly Code)


section .bss
  digit0: resb 1
  digit1: resb 1
  array:  resb 50
  element: resb 1
  num: resb 1
  pos: resb 1
  temp: resb 1
  temp2: resb 1
  temp3: resb 1
  i: resb 1
  j: resb 1


section .data

msg1: db "Enter the number of numbers : "
size1: equ $-msg1
msg2: db "Enter a number:"
size2: equ $-msg2
msg3: db "Sorted Array : "
size3: equ $-msg3
msg_found: db "Element found at position : "
size_found: equ $-msg_found
msg_not: db "Element not found"
size_not: equ $-msg_not
comma: db ","

section .text
  global _start

_start:
  


;Printing the message to enter the number
  mov eax, 4
  mov ebx, 1
  mov ecx, msg1
  mov edx, size1
  int 80h
  
  ;Reading the number
  mov eax, 3
  mov ebx, 0
  mov ecx, digit1
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, digit0
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, temp
  mov edx, 1
  int 80h

  sub byte[digit1], 30h
  sub byte[digit0], 30h  

  mov al, byte[digit1]
  mov dl, 10
  mul dl
  mov byte[num], al
  mov al, byte[digit0]
  add byte[num], al
  mov al, byte[num]

  mov byte[temp], al
  mov byte[temp2], al
  mov ebx, array
  

reading:
  
  push ebx

  ;Printing the message to enter the numbers
  mov eax, 4
  mov ebx, 1
  mov ecx, msg2
  mov edx, size2
  int 80h
  
  ;Reading the number
  mov eax, 3
  mov ebx, 0
  mov ecx, digit1
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, digit0
  mov edx, 1
  int 80h

  mov eax, 3
  mov ebx, 0
  mov ecx, temp3
  mov edx, 1
  int 80h


  sub byte[digit1], 30h
  sub byte[digit0], 30h  
  mov al, byte[digit1]
  mov dl, 10
  mul dl
  add al, byte[digit0]

  ;al now contains the number
  pop ebx

  mov byte[ebx], al

  add ebx, 1

  dec byte[temp]
  cmp byte[temp], 0

jg reading

  
  
  movzx ecx, byte[num]

  mov ebx, array

  mov byte[i], 0

i_loop:
  mov byte[j], 0
  j_loop:
    mov ebx, array
    movzx eax, byte[j]
    add ebx, eax
    mov eax, ebx
    add eax, 1
    mov dl, byte[ebx]
    mov dh, byte[eax]
    cmp dh, dl
    jl swap
    jmp no_swap
  
    swap:
      mov byte[ebx], dh
      mov byte[eax], dl

no_swap:
    inc byte[j]
    mov al, byte[num]
    sub al, byte[i]
    sub al, 1
    cmp byte[j], al
    jl j_loop

  inc byte[i]
  mov al, byte[num]
  cmp byte[i], al
jl i_loop


;Printing the sorted array....
;To beedited

  mov eax, 4
  mov ebx, 1
  mov ecx, msg3
  mov edx, size3
  int 80h


  mov ebx, array

printing:
  
  push ebx
  mov al, byte[ebx]
  mov byte[pos], al

  movzx ax, byte[pos]
  mov bl, 10
  div bl
  mov byte[digit1], al
  mov byte[digit0], ah

  add byte[digit0], 30h
  add byte[digit1], 30h

  mov eax, 4
  mov ebx, 1
  mov ecx, digit1
  mov edx, 1
  int 80h

  mov eax, 4
  mov ebx, 1
  mov ecx, digit0
  mov edx, 1
  int 80h

  mov eax, 4
  mov ebx, 1
  mov ecx, comma
  mov edx, 1
  int 80h




  ;al now contains the number
  pop ebx

  add ebx, 1

  dec byte[temp2]
  cmp byte[temp2], 0

jg printing




  
exit:
  mov eax, 1
  mov ebx, 0
  int 80h



  
  
  

Checking whether a system is Little Endian or Big Endian in NASM


;Program to check whether the given architecture is little endian 
;Or Big Endian

section .data
  msg1: db "Architechture is Little Endian"
  size1: equ $-msg1
  msg2: db "Architechture is Big Endian"
  size2: equ $-msg2

section .bss
  temp: resb 1


section .text
  global _start

_start:

  mov eax, 0xffff0000
  push eax
  pop ax
  pop bx

  cmp bx, 0xffff
  je  LittleEndian
  
BigEndian:
  mov eax, 4
  mov ebx, 1
  mov ecx, msg2
  mov edx, size2
  int 80h
  jmp End


LittleEndian:
  mov eax, 4
  mov ebx, 1
  mov ecx, msg1
  mov edx, size1
  int 80h


End:
  mov eax, 1
  mov ebx, 0
  int 80h




Thursday, April 19, 2012

Breadth First Search(BFS) in C++


#include<iostream>

using namespace std;

int n;


struct vertex
{
    int index;
    int no_edges;
    int adj[20];
    int predecessor;
    int d;
    char color;

}v[20];

struct queue{

    int data;
    queue * link;

}*front, *rear;



void enqueue(int e)
{
    queue * ptr;
    ptr = new queue;
    (*ptr).link = NULL;
    (*ptr).data = e;
    if(rear == NULL)
    {

        front = rear = ptr;
    }
    else
    {
        (*rear).link = ptr;
        rear = ptr;
    }
}



int dequeue()
{
    queue * temp;
    int e;
    if(front == NULL)
        return 0;
    else if((*front).link == NULL)
    {
        e = (*front).data;
        temp = front;
        front  = rear = NULL;
        delete temp;

    }
    else{
        e = (*front).data;
        temp = front;
        front = (*front).link;
        delete temp;
    }
    return e;

}

void BFS(vertex s);



int main()
{
    front = NULL;
    rear = NULL;
    int i,j, noe,u, u2;



    cout<<"Enter the number of edges :";
    cin>>n;

    cout<<"Let the vertices be : ";
    for(i = 1;i<=n;i++)
        cout<<i<<" ";
    cout<<"\n";

    for(i = 1;i<=n;i++)
    {
        v[i].index = i;
        cout<<"Enter the number of adjacent vertices for vertex no : "<<i<<" : ";
        cin>>v[i].no_edges;
        if(v[i].no_edges != 0)
            cout<<"Enter the adjacent vertices : ";
        for(j = 1;j<=v[i].no_edges;j++)
            cin>>v[i].adj[j];
    }

    cout<<"Enter a vertex no : ";
    cin>>u;
    BFS(v[u]);

    cout<<"Enter another vertex no :";
    cin>>u2;

    cout<<"\nDistance : "<< v[u2].d;


    if(  v[u2].d > 50   )
        cout<<"Points ureachable...";
    else
    {
        cout<<"Path : "<<u2;
        i = v[u2].predecessor;
        while(i != 0)
        {
                cout<<" -> "<<i;
                i = v[i].predecessor;
        }
    }


    return 0;
}


void BFS(vertex s)
{
    int u,i,j,noe,k;
    for(i = 1; i<=n ;i++)
    {

        v[i].color = 'w';
        v[i].predecessor = 0;
        v[i].d = 100;

    }
        v[s.index].color = 'g';
        v[s.index].predecessor = 0;
        v[s.index].d = 0;

    enqueue(s.index);
    while(front)
    {
        u = dequeue();
        noe = v[u].no_edges;
        for(j = 1;j<=noe;j++)
        {
            k = v[u].adj[j];
            if (v[k].color == 'w')
            {
                v[k].color = 'g';
                v[k].d = v[u].d + 1;
                v[k].predecessor = u;
                enqueue(k);
            }
            v[u].color = 'b';

        }



    }


}





Cache Simulator in C++


#include<iostream>
#include<fstream>
#include<cstdlib>


using namespace std;

int lru[500][20];

//Function to change the tag order in the lru algo
int bringtotop(int set, int assoc, int x)
{
    int i,pos;
    for(i=0;i<assoc;i++)
        if(lru[set][i] == x)
            pos = i;
    for(i=pos;i<assoc-1;i++)
        lru[set][i] = lru[set][i+1];
    lru[set][assoc-1] = x;


}

void plot(int total, int hit, int miss);

long int changebase(char hex[], int base);


int convert(char);

int main()
{
 int cache_size, asso, block_size,i,j, no_blocks, base,r,alg, x,pos;
 long int address;
 float hitrate;
 char hex[20], filename[20];
 int no_set;
 int check=0, hit=0, miss=0;



 cout<<"Enter the cache_size : ";
 cin>>cache_size;
 cout<<"Enter the associativity : ";
 cin>>asso;
 cout<<"Enter the block size : ";
 cin>>block_size;
 cout<<"Enter trace filename : ";
 cin>>filename;
 cout<<"Enter the base of number in trace file : ";
 cin>>base;
 cout<<"1. FIFO  2.LRU  3. Random...Enter Your Choice : ";
 cin>>alg;

 no_blocks = cache_size / block_size;
 no_set = cache_size / (asso * block_size);

 int cache[no_set][asso];

 for(i=0;i<no_set;i++)
  for(j=0;j<asso;j++)
   cache[i][j] = -10; // Eliminating all garbage values in in the cache...


 int fifo[no_set];
 for(i=0;i<no_set;i++)
  fifo[i] = 0;

    for(i=0;i<no_set;i++)
        for(j=0;j<asso;j++)
            lru[i][j] = j;

 ifstream infile;
 infile.open(filename,ios::in);
 if(!infile)
 {
     cout<<"Error! File not found...";
     exit(0);

 }
 int set, tag, found;
 while(!infile.eof()) //Reading each address from trace file
 {

        if(base!=10)
        {
            infile>>hex;
            address = changebase(hex, base);
        }
        else
            infile>>address;

  set = (address / block_size) % no_set;
  tag = address / (block_size * no_set);


  check++;
  found = 0;
  for(i=0;i<asso;i++)
   if(cache[set][i] == tag)
    {
        found = 1;
        pos = i;
    }


  if(found)
  {
      hit++;
      if(alg == 2)
      {
                bringtotop(set,asso,pos);
      }
  }

  else
  {
            if(alg==1)
            {
             i = fifo[set];

   cache[set][i] = tag;
   fifo[set]++;

   if(fifo[set] == asso)
    fifo[set] = 0;

            }
            else if(alg==2)
            {
                i = lru[set][0];
                cache[set][i] = tag;
                bringtotop(set,asso,i);

            }
            else
            {
                r = rand() % asso;
                cache[set][r] = tag;

            }

  }



 }
 infile.close();
 system("clear");
 cout<<"No: of checks : "<<check;
 cout<<" No: of hits : "<<hit;
 cout<<" No of misses : "<<check-hit;
 hitrate = float(hit)/float(check);
 cout<<" Hit Rate : "<<hitrate;
    plot(check,hit, check-hit);
 return 0;

}







int convert(char c)
{
    if(c == '1')
        return 1;

    else if(c == '2')
        return 2;

    else if(c == '3')
        return 3;

    else if(c == '4')
        return 4;

    else if(c =='5')
        return 5;

    else if(c == '6')
        return 6;

    else if(c == '7')
        return 7;

    else if(c == '8')
        return 8;

    else if(c == '9')
        return 9;

    else if(c == '0')
        return 0;

    else if( (c == 'a') || (c == 'A') )
        return 10;

    else if( (c == 'b') || (c == 'B') )
        return 11;

    else if( (c == 'c') || (c == 'C') )
        return 12;

    else if( (c == 'd') || (c == 'D') )
        return 13;

    else if( (c == 'e') || (c == 'E') )
        return 14;

    else if( (c == 'f') || (c == 'F') )
        return 15;

    else
        return 0;

}

//Function to change the base of a number system to decimal
long int changebase(char hex[], int base)
{
    int pow = 1,len,i,j;
    char temp;
    long int dec;

    for(len=0;hex[len]!='\0';len++);

    for(i=0,j=(len-1);i<j;i++,j--)
    {
        temp = hex[i];
        hex[i]=hex[j];
        hex[j]=temp;
    }


    pow = 1;
    dec = 0;
    for(i=0;i<len;i++)
    {
        if(convert(hex[i]== -1))
        {
            dec =0;
            break;
        }
        dec = dec + (pow * convert(hex[i]));
        pow*=base;

    }
    return dec;

}


//Function to plot a graph...
void plot(int total, int hit, int miss)
{

    cout<<"\n\n     ************Graph**********\n\n";

    int hit_limit,miss_limit, i;
    hit_limit = (float (hit)/total)*30;
    miss_limit = (float(miss)/total)*30;



    cout<<"\n\t^";
    cout<<"\n\t|\n";
    for(i=30;i>=0;i--)
    {
        cout<<"\t";
        cout<<"|";
        cout<<"\t\t";

        //Total hit bar
        cout<<"|";
        if(i==30)
            cout<<"----";
        else
            cout<<"    ";
        cout<<"|";

        cout<<"\t\t";
        //Hit Bar...
        if(i<=hit_limit)
            cout<<"|";
        else
            cout<<" ";

        if(i==hit_limit)
            cout<<"----";
        else
            cout<<"    ";

        if(i<=hit_limit)
            cout<<"|";
        else
            cout<<" ";



         cout<<"\t\t";
        //Miss Bar...
        if(i<=miss_limit)
            cout<<"|";
        else
            cout<<" ";

        if(i==miss_limit)
            cout<<"----";
        else
            cout<<"    ";

        if(i<=miss_limit)
            cout<<"|";
        else
            cout<<" ";

        cout<<"\n";

    }
    cout<<"\t------------------------------------------------------------------------------>";
    cout<<"\n\t\t\tTotal\t\t Hits\t\tMiss\n";



}