int hits = 0;
int misses = 0;
int evictions = 0;

/**
 * @brief This is a cache line, which line has a valid bit, tags and blocks.
 */
struct cacheRow {
    int valid;  /** valid bit */
    int tag;    /** tags */
};

/**
 * @brief The cache.
 */
struct cacheRow* cache = NULL;

/**
 * @brief A node for constructing a deque.
 */
typedef struct node{
    int offset;
    struct node* prev;
    struct node* next;
}node;

/**
 * @brief A deque, consist of a dummy head and a dummy tail.
 */
typedef struct deque{
    int size;
    int capacity;
    struct node* head;
    struct node* tail;
}deque;

/**
 * @brief For each SET, we have a deque (2^s deques)
 */
deque* deques;

/**
 * @brief Add the node to head of a deque.
 *
 * @param[in] dq deque
 * @param[in] node node
 */
void addToHead(deque* dq, node* node) {
    struct node* head = dq -> head;
    node -> prev = head;
    node -> next = head -> next;
    head -> next -> prev = node;
    head -> next = node;
}

/**
 * @brief Remove a node from its deque.
 *
 * @param[in] node node
 */
void removeNode(node* node) {
    node -> prev -> next = node -> next;
    node -> next -> prev = node -> prev;
}

/**
 * @brief Move a node to its deque's head.
 *
 * @param[in] dq deque
 * @param[in] node node
 */
void moveToHead(deque* dq, node* node) {
    removeNode(node);
    addToHead(dq, node);
}

/**
 * @brief Remove a tail from a deque.
 *
 * @param[in] dq deque
 *
 * @return the tail node
 */
node* removeTail(deque* dq) {
    node* res = dq -> tail -> prev;
    removeNode(res);
    return res;
}

/**
 * @brief Initialize cache
 *
 * @param[in] s set bits
 * @param[in] E lines per line
 */
void initCache(int s, int E) {
    int sets = 1 << s;

    struct cacheRow* cacheLines = (struct cacheRow*)malloc(sizeof(struct cacheRow) * sets * E); // 2^s * E lines of cache

    cache = cacheLines;

    deques = (deque*)malloc(sizeof(deque) * sets);

    for (int i = 0; i < sets; i++) {
        node* dummyHead = (struct node*)malloc(sizeof(node));
        node* dummyTail = (struct node*)malloc(sizeof(node));
        dummyHead -> offset = -1;
        dummyTail -> offset = -1;

        dummyHead->next = dummyTail;
        dummyTail->prev = dummyHead;

        deques[i].head = dummyHead;
        deques[i].tail = dummyTail;
        deques[i].size = 0;
        deques[i].capacity = E;
    }
}

/**
 * @brief The vital info about trace: operation and address.
 */
struct traceLine {
    char op;
    int address;
    // int block;
};

/**
 * @brief Parse the trace line to get op and address.
 *
 * @param[in] line a line of trace info
 *
 * @return operation and address
 */
struct traceLine* parseTraces(char* line) {
    if (line[0] != ' ')return NULL;
    char op = line[1]; // 'L' for load, 'M' for modify, 'S' for store
    int address = 0;

    char hexAddr[17];  // 存储十六进制地址，假设地址最多16位
    int i = 3, j = 0;

    // 提取逗号之前的十六进制字符串
    while (line[i] != ',' && line[i] != '\0') {
        hexAddr[j++] = line[i++];
    }
    hexAddr[j] = '\0'; // 确保字符串以 '\0' 结尾

    // 使用 strtol 将十六进制字符串转换为整数
    char* endptr;
    address = (int)strtol(hexAddr, &endptr, 16);

    struct traceLine* res = (struct traceLine*)malloc(sizeof(struct traceLine));
    res -> op = op;
    res -> address = address;
    return res;
}

/**
 * @brief Simulate cache
 *
 * @param[in] line trace info
 * @param[in] s set bits
 * @param[in] E lines per set
 * @param[in] b block bits
 * @param[in] verbose verbose option
 */
void processCache(struct traceLine* line, int s, int E, int b, int verbose) {
    int address = line->address;
    char op = line->op;
    int index = whichSet(address, s, b);
    int tag = address >> (s + b);
    deque* dq = &deques[index];

    struct cacheRow* setStart = cache + index * E;
    struct cacheRow* victimLine = NULL;
    node* victimNode = NULL;

    // Traverse the deque to find if cache hits
    for (node* n = dq->head->next; n != dq->tail; n = n->next) {
        struct cacheRow* cacheLine = setStart + n->offset;
        if (cacheLine->valid && cacheLine->tag == tag) {
            // Cache hit
            if (op == 'L' || op == 'S') {
                hits++;
                if (verbose) printf("hit\n");
            } else if (op == 'M') {
                hits += 2;
                if (verbose) printf("hit hit\n");
            }
            moveToHead(dq, n);
            return;
        }
    }

    // Cache miss: all the nodes in deque miss
    misses++;
    if (verbose && (op == 'L' || op == 'S')) printf("miss ");
    if (verbose && op == 'M') printf("miss hit");

    // Find an empty line or prepare for eviction
    for (int i = 0; i < E; i++) {
        struct cacheRow* cacheLine = setStart + i;
        if (!cacheLine->valid) {
            victimLine = cacheLine;
            victimNode = NULL;
            break;
        }
    }

    // All lines are valid, so evict the LRU line
    if (!victimLine) {
        evictions++;
        if (verbose) printf("eviction");
        victimNode = removeTail(dq);
        victimLine = setStart + victimNode->offset;
        free(victimNode);
    }

    // Update the victim line with new data
    victimLine->valid = 1;
    victimLine->tag = tag;

    // Add new node to head of deque
    node* newNode = (node*)malloc(sizeof(node));
    newNode->offset = victimLine - setStart;
    addToHead(dq, newNode);

    if (dq->size > dq->capacity) {
        removeTail(dq);
        --dq->size;
    }

    // If operation is 'M', the second store operation is a hit
    if (op == 'M') {
        hits++;
    }
    printf("\n");
}

void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    for (int i = 0; i < N; i += 8) {
        for (int j = 0; j < M; j += 8) {
            for (int k = i; k < i + 8; k++) {
                for (int s = j; s < j + 8; s++) {
                    B[s][k] = A[k][s];
                }
            }
        }
    }
}

void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    int a0, a1, a2, a3, a4, a5, a6, a7;
    for (int i = 0; i < N; i += 8) {
        for (int j = 0; j < M; j += 8) {
            for (int k = i; k < i + 8; k++) {
                a0 = A[k][j];
                a1 = A[k][j + 1];
                a2 = A[k][j + 2];
                a3 = A[k][j + 3];
                a4 = A[k][j + 4];
                a5 = A[k][j + 5];
                a6 = A[k][j + 6];
                a7 = A[k][j + 7];

                B[j][k] = a0;
                B[j + 1][k] = a1;
                B[j + 2][k] = a2;
                B[j + 3][k] = a3;
                B[j + 4][k] = a4;
                B[j + 5][k] = a5;
                B[j + 6][k] = a6;
                B[j + 7][k] = a7;
            }
        }
    }
}

void transpose_64x64(int M, int N, int A[N][M], int B[M][N])
{
    int a0, a1, a2, a3, a4, a5, a6, a7;
    for (int i = 0; i < N; i += 8) {
        for (int j = 0; j < M; j += 8) {
            // 外两层循环遍历每个8 * 8块

            // step0: 对于每个8*8块，因为4行占满cache，每次读4行
            // step1: 对于小小块，取出0和1块赋值给B
            for (int k = i; k < i + 4; k++) {
                // 取 A 的0和1两块
                a0 = A[k][j + 0];
                a1 = A[k][j + 1];
                a2 = A[k][j + 2];
                a3 = A[k][j + 3];
                a4 = A[k][j + 4];
                a5 = A[k][j + 5];
                a6 = A[k][j + 6];
                a7 = A[k][j + 7];
                // 存到 B 的块0
                B[j + 0][k] = a0;
                B[j + 1][k] = a1;
                B[j + 2][k] = a2;
                B[j + 3][k] = a3;

                // 存到 B 的块1
                B[j + 0][k + 4] = a4;
                B[j + 1][k + 4] = a5;
                B[j + 2][k + 4] = a6;
                B[j + 3][k + 4] = a7;
            }

            // step2: 临时变量存储B的块1 同时A的块3转置到B的块1
            for (int k = j; k < j + 4; k++) {
                // 存下每块 B 中块1，作为本地 buffer
                a0 = B[k][i + 4];
                a1 = B[k][i + 5];
                a2 = B[k][i + 6];
                a3 = B[k][i + 7];
                // A 的块3
                a4 = A[i + 4][k];
                a5 = A[i + 5][k];
                a6 = A[i + 6][k];
                a7 = A[i + 7][k];
                // 正常转置
                B[k][i + 4] = a4;
                B[k][i + 5] = a5;
                B[k][i + 6] = a6;
                B[k][i + 7] = a7;
                // 临时变量转置到B的块2
                B[k + 4][i + 0] = a0;
                B[k + 4][i + 1] = a1;
                B[k + 4][i + 2] = a2;
                B[k + 4][i + 3] = a3;
            }

            // step3: 正常转置最后一个
            for (int k = i + 4; k < i + 8; k++) {
                a4 = A[k][j + 4];
                a5 = A[k][j + 5];
                a6 = A[k][j + 6];
                a7 = A[k][j + 7];
                B[j + 4][k] = a4;
                B[j + 5][k] = a5;
                B[j + 6][k] = a6;
                B[j + 7][k] = a7;
            }
        }
    }
}