void trans(int M, int N, int A[N][M], int B[M][N]) {
    int i, j, tmp;

    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            tmp = A[i][j];
            B[j][i] = tmp;
        }
    }

}

for (a = 0 ; a < N ; a += 8) {
    for (b = 0 ; b < M ; b += 8) {
        for (c = b ; c < b + 8 ; ++c) {
            for (d = a + c - b ; d >= a ; --d) {
                B[c][d] = A[d][c];
            }
            for (d = a + c - b + 1 ; d < a + 8 ; ++d) {
                B[c][d] = A[d][c];
            }
        }
    }
}

for (a = 0 ; a < M ; a += 8) {
    for (b = 0 ; b < N ; b += 8) {
        for (c = a ; c < a + 4 ; ++c) {
            for (d = b + c - a ; d >= b ; -- d) {
                B[c][d] = A[d][c];
            }
            for (d = b + c - a + 1; d < b + 4 ; ++d) {
                B[c][d] = A[d][c];
            }
        }

        tmp0 = A[b][a + 4];
        tmp1 = A[b][a + 5];
        tmp2 = A[b][a + 6];
        tmp3 = A[b][a + 7];
        tmp4 = A[b + 1][a + 4];
        tmp5 = A[b + 1][a + 5];
        tmp6 = A[b + 1][a + 6];
        tmp7 = A[b + 1][a + 7];
        B[a + 4][b] = tmp0;
        B[a + 4][b + 1] = tmp4;
        B[a + 5][b] = tmp1;
        B[a + 5][b + 1] = tmp5;
        tmp0 = A[b + 2][a + 4];
        tmp4 = A[b + 2][a + 5];
        tmp1 = A[b + 3][a + 4];
        tmp5 = A[b + 3][a + 5];
        B[a + 4][b + 2] = tmp0;
        B[a + 4][b + 3] = tmp1;
        B[a + 5][b + 2] = tmp4;
        B[a + 5][b + 3] = tmp5;
        tmp0 = A[b + 2][a + 6];
        tmp4 = A[b + 2][a + 7];
        tmp1 = A[b + 3][a + 6];
        tmp5 = A[b + 3][a + 7];
        B[a + 6][b] = tmp2;
        B[a + 6][b + 1] = tmp6;
        B[a + 6][b + 2] = tmp0;
        B[a + 6][b + 3] = tmp1;
        B[a + 7][b] = tmp3;
        B[a + 7][b + 1] = tmp7;
        B[a + 7][b + 2] = tmp4;
        B[a + 7][b + 3] = tmp5;

        for (c = a + 4; c < a + 8 ; ++c) {
            for (d = b + c - a ; d >= b + 4 ; --d) {
                B[c][d] = A[d][c];
            }
            for (d = b + c - a + 1 ; d < b + 8 ; ++d) {
                B[c][d] = A[d][c];
            }
        }

        tmp0 = A[b + 6][a];
        tmp1 = A[b + 6][a + 1];
        tmp2 = A[b + 6][a + 2];
        tmp3 = A[b + 6][a + 3];
        tmp4 = A[b + 7][a];
        tmp5 = A[b + 7][a + 1];
        tmp6 = A[b + 7][a + 2];
        tmp7 = A[b + 7][a + 3];
        B[a + 2][b + 6] = tmp2;
        B[a + 2][b + 7] = tmp6;
        B[a + 3][b + 6] = tmp3;
        B[a + 3][b + 7] = tmp7;
        tmp2 = A[b + 4][a + 2];
        tmp3 = A[b + 4][a + 3];
        tmp6 = A[b + 5][a + 2];
        tmp7 = A[b + 5][a + 3];
        B[a + 2][b + 4] = tmp2;
        B[a + 2][b + 5] = tmp6;
        B[a + 3][b + 4] = tmp3;
        B[a + 3][b + 5] = tmp7;
        tmp2 = A[b + 4][a];
        tmp3 = A[b + 4][a + 1];
        tmp6 = A[b + 5][a];
        tmp7 = A[b + 5][a + 1];
        B[a][b + 4] = tmp2;
        B[a][b + 5] = tmp6;
        B[a][b + 6] = tmp0;qizhongqizhong
        B[a][b + 7] = tmp4;
        B[a + 1][b + 4] = tmp3;
        B[a + 1][b + 5] = tmp7;
        B[a + 1][b + 6] = tmp1;
        B[a + 1][b + 7] = tmp5;
    }
}

for (a = 0 ; a < N ; a += 8) {
    for (b = 0 ; b < M ; b += 8) {
        for (c = b ; c < b + 4 ; ++c) {
            tmp0 = A[c][a];
            tmp1 = A[c][a + 1];
            tmp2 = A[c][a + 2];
            tmp3 = A[c][a + 3];
            tmp4 = A[c][a + 4];
            tmp5 = A[c][a + 5];
            tmp6 = A[c][a + 6];
            tmp7 = A[c][a + 7];
            B[a][c] = tmp0;
            B[a + 1][c] = tmp1;
            B[a + 2][c] = tmp2;
            B[a + 3][c] = tmp3;
            B[a][c + 4] = tmp4;
            B[a + 1][c + 4] = tmp5;
            B[a + 2][c + 4] = tmp6;
            B[a + 3][c + 4] = tmp7;
        }
        for (c = a + 4 ; c < a + 8 ; ++c) {
            tmp0 = B[c - 4][b + 4];
            tmp1 = B[c - 4][b + 5];
            tmp2 = B[c - 4][b + 6];
            tmp3 = B[c - 4][b + 7];

            B[c - 4][b + 4] = A[b + 4][c - 4];
            B[c - 4][b + 5] = A[b + 5][c - 4];
            B[c - 4][b + 6] = A[b + 6][c - 4];
            B[c - 4][b + 7] = A[b + 7][c - 4];

            B[c][b] = tmp0;
            B[c][b + 1] = tmp1;
            B[c][b + 2] = tmp2;
            B[c][b + 3] = tmp3;

            B[c][b + 4] = A[b + 4][c];
            B[c][b + 5] = A[b + 5][c];
            B[c][b + 6] = A[b + 6][c];
            B[c][b + 7] = A[b + 7][c];
        }
    }
}

for (a = 0 ; a < N ; a += 16) {
    for (b = 0 ; b < M ; b += 16) {
        for (c = b ; (c < b + 16) && (c < M) ; ++c) {
            for (d = a ; (d < a + 16) && (d < N) ; ++d) {
                    B[c][d] = A[d][c];
            }
        }
    }
}

struct job_t {              //任务
    pid_t pid;              //任务的PID
    int jid;                //任务JID [1, 2, ...]
    int state;              //状态 - 包括UNDEF, BG, FG, ST
    char cmdline[MAXLINE];  //对应的命令行输入
};

void eval(char *cmdline)
{
    char * argv[MAXARGS];
    char buf[MAXLINE];
    int bg; /* if run in background */
    pid_t pid;

    sigset_t mask_all, mask_chld, prev_chld;

    /*initialize signal sets*/
    Sigfillset(&mask_all);
    Sigemptyset(&mask_chld);
    Sigaddset(&mask_chld, SIGCHLD);

    strcpy(buf, cmdline);
    bg = parseline(buf, argv); /* parse the command line */
    if (argv[0] == NULL) {
        return;
    } /* handles if there is empty input */

    if (!builtin_cmd(argv)) { /* if the command line is builtin command */
        Sigprocmask(SIG_BLOCK, &mask_chld, &prev_chld); /* block SIGCHLD to avoid potential race between addjob and deletejob */
        if ((pid = Fork()) == 0) {
            Setpgid(0, 0); /* give the child process a new group id to handle SIGINT correctly */
            Sigprocmask(SIG_SETMASK, &prev_chld, NULL); /* unblock SIGCHLD */
            Execve(argv[0], argv, environ);
        }
        Sigprocmask(SIG_BLOCK, &mask_all, NULL); /* mask all signals to avoid potential races */
        addjob(jobs, pid, bg + 1, cmdline); /* add job to joblist */
        Sigprocmask(SIG_SETMASK, &prev_chld, NULL);
        if (!bg) { /* if the process should be exeuted in foreground */
            waitfg(pid); /* fg wait explictly */
        } else {
            printf("[%d] (%d) %s", pid2jid(pid), pid, cmdline); /* bg print message*/
        }
    }

    return;
}

int builtin_cmd(char **argv)
{
    /* handles the builtin command in current context */
    if (!strcmp(argv[0], "quit")) {
        exit(0); /* quit: exit directly*/
    }
    if (!strcmp(argv[0], "jobs")) {
        listjobs(jobs); /* jobs: print the current job list */
        return 1;
    }
    if (!strcmp(argv[0], "bg") || !strcmp(argv[0], "fg")) {
        do_bgfg(argv); /* bg|fg: handles in function do_bgfg */
        return 1;
    }
    if (!strcmp(argv[0], "&")) {
        return 1; /* returns 1 for empty & */
    }
    return 0;     /* not a builtin command */
}

void do_bgfg(char **argv)
{
    int number = 0; /* used to store the converted number */
    char * ptr = argv[1]; /* get the pointer to argument 1 */
    char * endptr = NULL; /* used for error handling */
    struct job_t * job = NULL; /* used to store job pointer */
    if (!argv[1]) { /* returns if missing argument */
        printf("%s command requires PID or %%jobid argument\n", argv[0]);
        return;
    }
    if (*ptr == '%') { /* if argument 1 is job ID */
        ptr++; /* adjust pointer */
        number = strtol(ptr, &endptr, 10);
        if (ptr == endptr) { /* handles convert error */
            printf("%s: argument must be a PID or %%jobid\n", argv[0]);
            return;
        }
        job = getjobjid(jobs, number); /* get the job */
        if (!job) {/* handles if there is no such job */
            printf("%%%d: No such job\n", number);
            return;
        }
    } else {/* if argument 1 is pid */
        number = strtol(ptr, &endptr, 10);
        if (ptr == endptr) { /* handles convert error */
            printf("%s: argument must be a PID or %%jobid\n", argv[0]);
            return;
        }
        job = getjobpid(jobs, (pid_t)number); /* get the job */
        if (!job) {/* handles if there is no such job */
            printf("(%d): No such process\n", number);
            return;
        }
    }
    /* change process state and update the job list*/
    if (!strcmp(argv[0], "bg")) { /*bg: turns ST to BG, send SIGCONT */
        if(job->state == ST) {
            Kill(-(job->pid), SIGCONT);
            printf("[%d] (%d) %s", job->jid, job->pid, job->cmdline);
            job->state = BG;
        }
    } else if (!strcmp(argv[0], "fg")) {/* fg: turns ST/BG to FG, sent SIGCONT */
        if(job->state == ST) {
            Kill(-(job->pid), SIGCONT);
            job->state = BG;
        }
        if(job->state == BG) {
            job->state = FG;
            waitfg(job->pid);
        }
    }
    return;
}

void waitfg(pid_t pid)
{
    while(fgpid(jobs)) { /* handles all zombie processes in signal handler */
        sleep(0.01); /* busy loop only */
    }
    return;
}

void sigchld_handler(int sig)
{
    int olderrno = errno; /* store old errno */
    int status; /* used to trace pid's status */
    sigset_t mask_all, prev_all;
    pid_t pid;

    Sigfillset(&mask_all);

    while((pid = Waitpid(-1, &status, WUNTRACED | WNOHANG)) > 0) { /* waitpid without waiting(WNOHANG) */
        if (WIFSTOPPED(status) && (WSTOPSIG(status) == SIGTSTP || WSTOPSIG(status) == SIGSTOP)) { /* if the process is stopped */
            struct job_t * job = getjobpid(jobs, pid);
            if (job && job->state != ST) { /* if the stop signal hasn't been catched */
                printf("Job [%d] (%d) stopped by signal %d\n", pid2jid(pid), pid, WSTOPSIG(status));
                struct job_t * stpjob = getjobpid(jobs, pid);
                stpjob->state = ST;/* handles here */
            }
        }
        if (WIFSIGNALED(status) && WTERMSIG(status) == SIGINT) { /* it the terminate signal hasn't been catched */
            struct job_t * job = getjobpid(jobs, pid);
            if (job) {
                printf("Job [%d] (%d) terminated by signal %d\n", pid2jid(pid), pid, WTERMSIG(status));
                /* handles here */
            }
        }
        if (WIFEXITED(status) || WIFSIGNALED(status)) {
            Sigprocmask(SIG_BLOCK, &mask_all, &prev_all);
            deletejob(jobs, pid);
            Sigprocmask(SIG_SETMASK, &prev_all, NULL);
        }/* remove the job in job list accordingly */
    }
    errno = olderrno;
    return;
}

void sigint_handler(int sig)
{
    int olderrno = errno; /* store old errno */
    sigset_t mask_all, prev_all;
    Sigfillset(&mask_all);
    Sigprocmask(SIG_BLOCK, &mask_all, &prev_all); /* block all signal in case the race between SIGINT and SIGCHLD */

    pid_t pid;
    pid = fgpid(jobs);
    Kill(-pid, SIGINT); /* kill processes in fg job's process group */

    printf("Job [%d] (%d) terminated by signal %d\n", pid2jid(pid), pid, sig); /* print the message */

    deletejob(jobs, pid); /* delete job in joblist */

    Sigprocmask(SIG_SETMASK, &prev_all, NULL);

    errno = olderrno;
    return;
}

void sigtstp_handler(int sig)
{
    int olderrno = errno; /* store old errno */
    sigset_t mask_all, prev_all;
    Sigfillset(&mask_all);
    Sigprocmask(SIG_BLOCK, &mask_all, &prev_all); /* block all signal in case the race between SIGTSTP and SIGCHLD */

    pid_t pid;
    pid = fgpid(jobs);
    Kill(-pid, SIGTSTP); /* send SIGTSTP to fg job's process group */

    printf("Job [%d] (%d) stopped by signal %d\n", pid2jid(pid), pid, sig); /* print the message */

    struct job_t * stpjob = getjobpid(jobs, pid);
    stpjob->state = ST; /* modify the job list */

    Sigprocmask(SIG_SETMASK, &prev_all, NULL);

    errno = olderrno;
    return;
}

The core data structure deals with image representation. A pixel is a struct as shown below:
typedef struct {
    unsigned short red;    /* R value */
    unsigned short green;  /* G value */
    unsigned short blue;   /* B value */
} pixel;

#define RIDX(i,j,n) ((i)*(n)+(j))

void naive_rotate(int dim, pixel *src, pixel *dst) {
    int i, j;
    for(i=0; i < dim; i++)
        for(j=0; j < dim; j++)
            dst[RIDX(dim-1-j,i,dim)] = src[RIDX(i,j,dim)];
    return;
}

void naive_smooth(int dim, pixel *src, pixel *dst) {
    int i, j;
    for(i=0; i < dim; i++)
        for(j=0; j < dim; j++)
            dst[RIDX(i,j,dim)] = avg(dim, i, j, src); /* Smooth the (i,j)th pixel */
    return;
}

void block_rotate(int dim, pixel * src, pixel * dst) {
    int i, j, k, l;
    int cst0 = dim - 1;
    for (i = 0 ; i < dim ; i += 8) {
        for (j = 0 ; j < dim ; j += 8) {
            for (k = i ; k < i + 8 ; k++) {
                for (l = j ; l < j + 8 ; l++) {
                    dst[RIDX(cst0 - l, k, dim)] = src[RIDX(k, l, dim)];
                }
            }
        }
    }
}

void optimized_smooth(int dim, pixel * src, pixel * dst) {
    int i, j;
    int tmp;

    dst[0].red = (src[0].red + src[1].red + src[dim].red + src[dim + 1].red) >> 2;
    dst[0].green = (src[0].green + src[1].green + src[dim].green + src[dim + 1].green) >> 2;
    dst[0].blue = (src[0].blue + src[1].blue + src[dim].blue + src[dim + 1].blue) >> 2;
    i = dim - 1;
    dst[i].red = (src[i].red + src[i - 1].red + src[i + dim].red + src[i + dim -1].red) >> 2;
    dst[i].green = (src[i].green + src[i - 1].green + src[i + dim].green + src[i + dim -1].green) >> 2;
    dst[i].blue = (src[i].blue + src[i - 1].blue + src[i + dim].blue + src[i + dim -1].blue) >> 2;
    i = i * dim;
    dst[i].red = (src[i].red + src[i + 1].red + src[i - dim].red + src[i - dim + 1].red) >> 2;
    dst[i].green = (src[i].green + src[i + 1].green + src[i - dim].green + src[i - dim + 1].green) >> 2;
    dst[i].blue = (src[i].blue + src[i + 1].blue + src[i - dim].blue + src[i - dim + 1].blue) >> 2;
    i = i + dim - 1;
    dst[i].red = (src[i].red + src[i - 1].red + src[i - dim].red + src[i - dim - 1].red) >> 2;
    dst[i].green = (src[i].green + src[i - 1].green + src[i - dim].green + src[i - dim - 1].green) >> 2;
    dst[i].blue = (src[i].blue + src[i - 1].blue + src[i - dim].blue + src[i - dim - 1].blue) >> 2;

    for (i = 1 ; i < dim - 1 ; i++) {
        dst[i].red = (src[i].red + src[i - 1].red + src[i + 1].red + src[i + dim].red + src[i + dim - 1].red + src[i + dim + 1].red) / 6;
        dst[i].green = (src[i].green + src[i - 1].green + src[i + 1].green + src[i + dim].green + src[i + dim - 1].green + src[i + dim + 1].green) / 6;
        dst[i].blue = (src[i].blue + src[i - 1].blue + src[i + 1].blue + src[i + dim].blue + src[i + dim - 1].blue + src[i + dim + 1].blue) / 6;
    }
    for (i = dim * (dim - 1) + 1 ; i < dim * dim - 1 ; i++) {
        dst[i].red = (src[i].red + src[i - 1].red + src[i + 1].red + src[i - dim].red + src[i - dim - 1].red + src[i - dim + 1].red) / 6;
        dst[i].green = (src[i].green + src[i - 1].green + src[i + 1].green + src[i - dim].green + src[i - dim - 1].green + src[i - dim + 1].green) / 6;
        dst[i].blue = (src[i].blue + src[i - 1].blue + src[i + 1].blue+ src[i - dim].blue + src[i - dim - 1].blue+ src[i - dim + 1].blue) / 6;
    }
    for (j = dim ; j < dim * (dim - 1) ; j+= dim) {
        dst[j].red = (src[j].red + src[j + 1].red + src[j - dim].red + src[j - dim + 1].red + src[j + dim].red + src[j + dim + 1].red) / 6;
        dst[j].green = (src[j].green + src[j + 1].green + src[j - dim].green+ src[j - dim + 1].green + src[j + dim].green + src[j + dim + 1].green) / 6;
        dst[j].blue = (src[j].blue + src[j + 1].blue + src[j - dim].blue + src[j - dim + 1].blue + src[j + dim].blue + src[j + dim + 1].blue) / 6;
    }
    for (j = 2 * dim - 1 ; j < dim * dim - 1 ; j += dim) {
        dst[j].red = (src[j].red + src[j - 1].red + src[j - dim].red + src[j - dim - 1].red + src[j + dim].red + src[j + dim - 1].red) / 6;
        dst[j].green = (src[j].green + src[j - 1].green + src[j - dim].green + src[j - dim - 1].green + src[j + dim].green + src[j + dim - 1].green) / 6;
        dst[j].blue = (src[j].blue + src[j - 1].blue + src[j - dim].blue + src[j - dim - 1].blue + src[j + dim].blue + src[j + dim - 1].blue) / 6;
    }

    for (i = 1 ; i < dim - 1 ; i++) {
        for (j = 1 ; j < dim - 1 ; j++) {
            tmp = i * dim + j;
            dst[tmp].red = (src[tmp].red + src[tmp - 1].red + src[tmp + 1].red + src[tmp - dim].red + src[tmp - dim - 1].red + src[tmp - dim + 1].red + src[tmp + dim].red + src[tmp + dim - 1].red + src[tmp + dim + 1].red) / 9;
            dst[tmp].green = (src[tmp].green + src[tmp - 1].green + src[tmp + 1].green + src[tmp - dim].green + src[tmp - dim - 1].green + src[tmp - dim + 1].green + src[tmp + dim].green + src[tmp + dim - 1].green + src[tmp + dim + 1].green) / 9;
            dst[tmp].blue = (src[tmp].blue + src[tmp - 1].blue + src[tmp + 1].blue + src[tmp - dim].blue + src[tmp - dim - 1].blue + src[tmp - dim + 1].blue + src[tmp + dim].blue + src[tmp + dim - 1].blue + src[tmp + dim + 1].blue) / 9;
        }
    }
}

/* include necessary headers */
#include "cachelab.h"

#include "getopt.h"
#include "stdlib.h"
#include "unistd.h"

#include "string.h"

#include "stdio.h"

#include "stdint.h"

/* cache struct definition */
typedef struct CSim_Cache_Entry {
    char valid_bit;
    uint64_t tag_bit;
}CSim_Cache_Entry;

typedef struct CSim_Cache_Set{
    CSim_Cache_Entry * entries;
}CSim_Cache_Set;

typedef struct CSim_Cache {
    /* basic arguments */
    int block_offset;
    int set_number;
    int line_number;
    /* masks and offsets */
    int tag_offset;
    int set_offset;
    uint64_t tag_mask;
    uint64_t set_mask;
    /* cache */
    CSim_Cache_Set * sets;
}CSim_Cache;

/* simulation result definition */
typedef struct CSim_Cache_Result {
    int hit;
    int miss;
    int evict;
}CSim_Cache_Result;

/* operation type definition */
typedef enum CSIM_OPERATION_TYPE {
    CSIM_OPERATION_TYPE_NONE,
    CSIM_OPERATION_TYPE_MODIFY,
    CSIM_OPERATION_TYPE_LOAD,
    CSIM_OPERATION_TYPE_STORE,
}CSIM_OPERATION_TYPE;

/* operation result definition */
typedef enum CSIM_OPERATION_RESULT {
    CSIM_OPERATION_RESULT_MISS,
    CSIM_OPERATION_RESULT_HIT,
    CSIM_OPERATION_RESULT_MISS_EVICTION,
}CSIM_OPERATION_RESULT;

/* error definition */
typedef enum CSIM_ERROR {
    CSIM_OK = 0,
    CSIM_ERROR_INVALID_OPTION,
    CSIM_ERROR_MISSING_ARGUMENT,
    CSIM_ERROR_FILE_CANNOT_OPEN,
    CSIM_ERROR_OUT_OF_MEMORY,
}CSIM_ERROR;

/* macro definition for get a value given mask and offset */
#define csim_get_value(number, mask, offset) (((number) & (mask)) >> (offset))

/* function list */
/* message print functions */
void csim_print_help_info();
void csim_error_missing_argument();
void csim_error_file_cannot_open();
void csim_error_out_of_memory();
/* cache structure related functions */
CSim_Cache * csim_construct_cache(int set_number, int line_number, int block_offset);
void csim_deconstruct_cache(CSim_Cache ** pcache);
/* cache simulation function */
CSim_Cache_Result csim_parse_trace_file(CSim_Cache * cache, FILE * file_pointer, char verbose_flag);

/* global variable */
char * program_name = NULL;

void csim_print_help_info() {
    printf("Usage: ./csim [-hv] -s <num> -E <num> -b <num> -t <file>\n");
    printf("Options:\n");
    printf("  -h         Print this help message.\n");
    printf("  -v         Optional verbose flag.\n");
    printf("  -s <num>   Number of set index bits.\n");
    printf("  -E <num>   Number of lines per set.\n");
    printf("  -b <num>   Number of block offset bits.\n");
    printf("  -t <file>  Trace file.\n\n");
    printf("Examples:\n");
    printf("  linux>  ./csim -s 4 -E 1 -b 4 -t traces/yi.trace\n");
    printf("  linux>  ./csim -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");
}

void csim_error_missing_argument() {
    printf("%s: Missing required command line argument\n", program_name);
    csim_print_help_info();
}

void csim_error_file_cannot_open() {
    printf("%s: No such file or directory\n", program_name);
}

void csim_error_out_of_memory() {
    printf("%s: Out of memory\n", program_name);
}

CSim_Cache * csim_construct_cache(int set_number, int line_number, int block_offset) {
    /* memory allocation */
    CSim_Cache * cache = malloc(sizeof(CSim_Cache));
    if (cache == NULL) {
        csim_error_out_of_memory();
        exit(CSIM_ERROR_OUT_OF_MEMORY);
    }
    /* configure basic arguments */
    cache->set_number = set_number;
    cache->line_number = line_number;
    cache->block_offset = block_offset;
    /* caculate masks and offsets */
    cache->tag_mask = ((uint64_t)0xFFFFFFFFFFFFFFFF) << (block_offset + set_number);
    cache->tag_offset = block_offset + set_number;
    cache->set_mask = ((((((uint64_t)0xFFFFFFFFFFFFFFFF) << (64 - cache->tag_offset)) >> (64 - cache->tag_offset)) >> block_offset) << block_offset);
    cache->set_offset = block_offset;
    /* memory allocation for cache */
    cache->sets = calloc((1 << set_number), sizeof(CSim_Cache_Set));
    if (cache->sets == NULL) {
        csim_error_out_of_memory();
        exit(CSIM_ERROR_OUT_OF_MEMORY);
    }
    for (int index = 0 ; index < (1 << set_number) ; ++index) {
        (cache->sets)[index].entries = calloc(line_number, sizeof(CSim_Cache_Entry));
        if ((cache->sets)[index].entries == NULL) {
            csim_error_out_of_memory();
            exit(CSIM_ERROR_OUT_OF_MEMORY);
        }
    }
    return cache;
}

void csim_deconstruct_cache(CSim_Cache ** pcache) {
    /* release cache according to construct function */
    CSim_Cache * temp = *pcache;
    int set_number = temp->set_number;
    for (int index = 0 ; index < set_number ; ++index) {
        free((temp->sets)[index].entries);
    }
    free(temp->sets);
    free(temp);
    *pcache = NULL;
}

CSim_Cache_Result csim_parse_trace_file(CSim_Cache * cache, FILE * file_pointer, char verbose_flag) {
    /* file I/O related */
    char line[80];
    char * line_pointer = NULL;
    /* cache type and cache result */
    CSIM_OPERATION_TYPE type;
    CSIM_OPERATION_RESULT result;
    /* address and set index & tag bis from it */
    int address = 0;
    int set = 0, tag = 0;
    /* line number */
    int line_number = cache->line_number;
    /* simulation result */
    CSim_Cache_Result summary = {0, 0, 0};
    /* parsing process */
    while (fgets(line, 80, file_pointer), feof(file_pointer) == 0) {
        line_pointer = line;
        type = CSIM_OPERATION_TYPE_NONE;
        /* exclude instrction load */
        if (*line_pointer++ == ' ') {
            switch(*line_pointer++) {
                case 'L':
                    type = CSIM_OPERATION_TYPE_LOAD;
                    if (verbose_flag) {
                        putchar('L');
                    }
                    break;
                case 'S':
                    type = CSIM_OPERATION_TYPE_STORE;
                    if (verbose_flag) {
                        putchar('S');
                    }
                    break;
                case 'M':
                    type = CSIM_OPERATION_TYPE_MODIFY;
                    if (verbose_flag) {
                        putchar('M');
                    }
                    break;
                default:
                    type = CSIM_OPERATION_TYPE_NONE;
                    break;
            }
            result = CSIM_OPERATION_RESULT_MISS_EVICTION;
            sscanf(line_pointer, "%x", &address);
            if (verbose_flag) {
                while ((*line_pointer) != '\n') {
                    putchar(*line_pointer++);
                }
            }
            /* separate set and tag according to mask and offset */
            set = csim_get_value(address, cache->set_mask, cache->set_offset);
            tag = csim_get_value(address, cache->tag_mask, cache->tag_offset);
            /* determine the cache result */
            CSim_Cache_Entry * pentry = (cache->sets)[set].entries;
            int index;
            CSim_Cache_Entry temp;
            for (index = 0; index < line_number ; ++index) {
                if (!pentry[index].valid_bit) {
                    result = CSIM_OPERATION_RESULT_MISS;
                    break;
                }
                if (pentry[index].tag_bit == tag) {
                    result = CSIM_OPERATION_RESULT_HIT;
                    break;
                }
            }
            /* simulate according to the result of cache behavior */
            switch(result) {
                case CSIM_OPERATION_RESULT_MISS:
                    if (verbose_flag) {
                        printf(" miss");
                    }
                    pentry[index].valid_bit = 1;
                    pentry[index].tag_bit = tag;
                    summary.miss++;
                    break;
                case CSIM_OPERATION_RESULT_MISS_EVICTION:
                    if (verbose_flag) {
                        printf(" miss eviction");
                    }
                    pentry[0].tag_bit = tag;
                    temp = pentry[0];
                    for (index = 0 ; index < line_number - 1 ; ++index) {
                        pentry[index] = pentry[index + 1];
                    }
                    pentry[index] = temp;
                    summary.miss++;
                    summary.evict++;
                    break;
                case CSIM_OPERATION_RESULT_HIT:
                    if (verbose_flag) {
                        printf(" hit");
                    }
                    temp = pentry[index];
                    for ( ; (index < line_number - 1) && (pentry[index + 1].valid_bit) ; ++index) {
                        pentry[index] = pentry[index + 1];
                    }
                    pentry[index] = temp;
                    summary.hit++;
                    break;
            }
            if (type == CSIM_OPERATION_TYPE_MODIFY) {
                if (verbose_flag) {
                    printf(" hit");
                }
                summary.hit++;
            }
            if (verbose_flag) {
                putchar('\n');
            }
        }
    }
    return summary;
}

int main(int argc, char *argv[]) {
    /* variables for argument parsing */
    char h = 0, v = 0, s = 0, E = 0, b = 0, t = 0;
    int opt;
    /* cache arguments */
    int set_number = 0, line_number = 0, block_offset = 0;
    /* cache */
    CSim_Cache * cache = NULL;
    /* file path */
    char file_path[80];
    /* verbose flag */
    char verbose_flag = 0;
    /* summary */
    CSim_Cache_Result summary = {0, 0, 0};
    /* pre-operation */
    program_name = argv[0];
    /* argument parsing */
    while ((opt = getopt(argc, argv, "hvs:E:b:t:")) != -1) {
        switch(opt) {
            case 'h':
                h = 1;
                break;
            case 'v':
                v = 1;
                verbose_flag = 1;
                break;
            case 's':
                set_number = atoi(optarg);
                if (set_number == 0) {
                    csim_error_missing_argument();
                    return CSIM_ERROR_MISSING_ARGUMENT;
                }
                s = 1;
                break;
            case 'E':
                line_number = atoi(optarg);
                if (line_number == 0) {
                    csim_error_missing_argument();
                    return CSIM_ERROR_MISSING_ARGUMENT;
                }
                E = 1;
                break;
            case 'b':
                block_offset = atoi(optarg);
                if (block_offset == 0) {
                    csim_error_missing_argument();
                    return CSIM_ERROR_MISSING_ARGUMENT;
                }
                b = 1;
                break;
            case 't':
                t = 1;
                strcpy(file_path, optarg);
                break;
            default:
                csim_print_help_info();
                return CSIM_ERROR_INVALID_OPTION;
                break;
        }
    }
    if (h == 1) {
        csim_print_help_info();
        return CSIM_OK;
    }
    if (v == 1) {
        verbose_flag = 1;
    }
    if (!(s == 1 && E == 1 && b == 1 && t == 1)) {
        csim_error_missing_argument();
        return CSIM_ERROR_MISSING_ARGUMENT;
    }
    /* file processing */
    FILE * file_pointer = fopen(file_path, "r");
    if (file_pointer == NULL) {
        csim_error_file_cannot_open(file_path);
        return CSIM_ERROR_FILE_CANNOT_OPEN;
    }
    /* cache construction */
    cache = csim_construct_cache(set_number, line_number, block_offset);
    /* trace file parsing */
    summary = csim_parse_trace_file(cache, file_pointer, verbose_flag);
    /* summary */
    printSummary(summary.hit, summary.miss, summary.evict);
    /* post operations */
    csim_deconstruct_cache(&cache);
    fclose(file_pointer);
    return CSIM_OK;
}

/* getbuf */
#define NORMAL_BUFFER_SIZE ??
int getbuf()
{
char buf[NORMAL_BUFFER_SIZE];
Gets(buf);
return 1;
}

/* test */
void test()
{
int val;
/* Put canary on stack to detect possible corruption */
volatile int local = uniqueval();

val = getbuf();

/* Check for corrupted stack */
if (local != uniqueval()) {
printf("Sabotaged!: the stack has been corrupted\n");
}
else if (val == cookie) {
printf("Boom!: getbuf returned 0x%x\n", val);
validate(3);
} else {
printf("Dud: getbuf returned 0x%x\n", val);
}
}

void smoke()
{
printf("Smoke!: You called smoke()\n");
validate(0);
exit(0);
}

void fizz(int val)
{
if (val == cookie) {
printf("Fizz!: You called fizz(0x%x)\n", val);
validate(1);
} else
printf("Misfire: You called fizz(0x%x)\n", val);
exit(0);
}

int global_value = 0;
void bang(int val)
{
if (global_value == cookie) {
printf("Bang!: You set global_value to 0x%x\n", global_value);
validate(2);
} else
printf("Misfire: global_value = 0x%x\n", global_value);
exit(0);
}

unsigned getbuf()
{
	char buf[BUFFER_SIZE];
	Gets(buf);
	return 1;
}

void test()
{
	int val;
	val = getbuf();
	printf("No exploit. Getbuf returned 0x%x\n", val);
}

void touch1()
{
	vlevel = 1;
	printf("Touch1!: You called touch1()\n");
	validate(1);
	exit(0);
}

void touch2(unsigned val)
{
	vlevel = 2;
	if (val == cookie) {
		printf("Touch2!: You called touch2(0x%.8x)\n", val);
		validate(2);
	} else {
		printf("Misfire: you called touch2(0x%.8x)\n", val);
		fail(2);
	}
	exit(0);
}