#include "common.h"

// 饱和计数器：加1
static inline UINT32 SatIncrement(UINT32 x, UINT32 max)
{
	if (x<max) return x + 1;
	return x;
}

// 饱和计数器：减1
static inline UINT32 SatDecrement(UINT32 x)
{
	if (x>0) return x - 1;
	return x;
}

#define BITS_OF_PC 13	// 选择13位的PC作为索引

#define STATE_MAX  3
#define STATE_INIT 2

UINT32 *State;			// 状态数组，用于保存分支指令的状态机，实际只使用最低2位
UINT64 StateArraySize;

void PREDICTOR_init(void)
{
	StateArraySize = (1 << BITS_OF_PC);    // 状态数组项数

	State = (UINT32 *)malloc(StateArraySize * sizeof(UINT32));

	// *********** 你需要在下面书写代码 ***********
    // 将状态数组，全部初始化为STATE_INIT
    for(UINT32 i = 0; i < StateArraySize; i++)
    {
        State[i] = 2;
    }
	// *********** 你需要在上面书写代码 ***********
}

// 2位状态的分支预测器（预测部分）
char GetPrediction(UINT64 PC)
{
	// *********** 你需要在下面书写代码 ***********
	// 将PC的低13位，去索引状态数组State，得到对应的饱和状态
	// 如果该状态的值超过一半，则预测跳转
	// 如果该状态的值低于一半，则预测不跳转
    UINT32 index = PC>>2 & 0x1fff;
    if(State[index] == 0 || State[index] == 1) return NOT_TAKEN;
    return TAKEN;
	//return TAKEN;
	//return NOT_TAKEN;
	// *********** 你需要在上面书写代码 ***********
}

// 2位状态的分支预测器（更新部分）
void  UpdatePredictor(UINT64 PC, OpType opType, char resolveDir, char predDir, UINT64 branchTarget)
{

	// *********** 你需要在下面书写代码 ***********
	// 根据分支指令实际执行结果，来更新对应的饱和计数器
	// 如果结果为跳转，则对应的饱和计数器+1
	// 如果结果为不跳转，则对应的饱和计数器-1
    UINT32 index = PC>>2 & 0x1fff;
    if(resolveDir == 'T')
    {
        State[index] = SatIncrement(State[index], 3);
    }
    else
    {
        State[index] = SatDecrement(State[index]);
    }

	// *********** 你需要在上面书写代码 ***********
}

void PREDICTOR_free(void)
{
	free(State);
}


#include "common.h"

// 饱和计数器：加1
static inline UINT32 SatIncrement(UINT32 x, UINT32 max)
{
	if (x<max) return x + 1;
	return x;
}

// 饱和计数器：减1
static inline UINT32 SatDecrement(UINT32 x)
{
	if (x>0) return x - 1;
	return x;
}

#define BITS_OF_PC 13	// 选择13位的PC作为索引

#define STATE_MAX  7
#define STATE_INIT 3

UINT32 *State;			// 状态数组，用于保存分支指令的状态机，实际只使用最低3位
UINT64 StateArraySize;

void PREDICTOR_init(void)
{
	StateArraySize = (1 << BITS_OF_PC);    // 状态数组项数

	State = (UINT32 *)malloc(StateArraySize * sizeof(UINT32));

	// *********** 你需要在下面书写代码 ***********
    // 将状态数组，全部初始化为STATE_INIT
    for(UINT64 i = 0; i <= StateArraySize; i++)
    {
        State[i] = STATE_INIT;
    }
	// *********** 你需要在上面书写代码 ***********
}

// 2位状态的分支预测器（预测部分）
char GetPrediction(UINT64 PC)
{
	// *********** 你需要在下面书写代码 ***********
	// 将PC的低13位，去索引状态数组State，得到对应的饱和状态
	// 如果该状态的值超过一半，则预测跳转
	// 如果该状态的值低于一半，则预测不跳转
    UINT64 index = (PC>>2) & 0x1fff;
    if(State[index] == 0 || State[index] == 1 || State[index] == 2 || State[index] == 3) return NOT_TAKEN;
    return TAKEN;
	//return TAKEN;
	//return NOT_TAKEN;
	// *********** 你需要在上面书写代码 ***********
}

// 2位状态的分支预测器（更新部分）
void  UpdatePredictor(UINT64 PC, OpType opType, char resolveDir, char predDir, UINT64 branchTarget)
{

	// *********** 你需要在下面书写代码 ***********
	// 根据分支指令实际执行结果，来更新对应的饱和计数器
	// 如果结果为跳转，则对应的饱和计数器+1
	// 如果结果为不跳转，则对应的饱和计数器-1
    UINT64 index = (PC>>2) & 0x1fff;
    if(resolveDir == 'T')
    {
        State[index] = SatIncrement(State[index], 7);
    }
    else
    {
        State[index] = SatDecrement(State[index]);
    }

	// *********** 你需要在上面书写代码 ***********
}

void PREDICTOR_free(void)
{
	free(State);
}


#include "common.h"

// 饱和计数器：加1
static inline UINT32 SatIncrement(UINT32 x, UINT32 max)
{
	if (x < max) return x + 1;
	return x;
}

// 饱和计数器：减1
static inline UINT32 SatDecrement(UINT32 x)
{
	if (x > 0) return x - 1;
	return x;
}

#define BITS_OF_PC 10		// 选择10位的PC作为索引
#define LOCAL_HIST_LEN   3	// 局部历史长度，3位
#define LOCAL_HIST_MASK  ~(~0  << LOCAL_HIST_LEN)

#define STATE_MAX  3
#define STATE_INIT 2

UINT32* pht;            // pattern history table    模式历史表
UINT32 phtArraySize;	// pht数组项数
UINT32* State;			// 状态数组，用于保存分支指令的状态机，实际只使用最低2位
UINT64 StateArraySize;

void PREDICTOR_init(void)
{
	StateArraySize = (1 << (BITS_OF_PC + LOCAL_HIST_LEN));    // 状态数组项数

	State = (UINT32*)malloc(StateArraySize * sizeof(UINT32));

	phtArraySize = (1 << BITS_OF_PC);	// pht数组项数

	pht = (UINT32*)malloc(phtArraySize * sizeof(UINT32));

	// *********** 你需要在下面书写代码 ***********
	// 将状态数组，全部初始化为STATE_INIT
	// 将模式历史表（pht）全部初始化为0
    for(UINT64 i = 0; i < StateArraySize; i++)
    {
        State[i] = STATE_INIT;
    }
    for(UINT32 i = 0; i < phtArraySize; i++)
    {
        pht[i] = 0;
    }
	// *********** 你需要在上面书写代码 ***********
}

// 2位状态的分支预测器（预测部分）
char GetPrediction(UINT64 PC)
{
	// *********** 你需要在下面书写代码 ***********
	// 将PC的低10位，去索引模式历史表pht，得到对应的3位历史信息
    UINT32 index1 = (PC>>2) & 0x3ff;
	// 将PC的低10位，与3位历史信息进行拼接，形成一个13位的状态数组索引（拼接需要使用C语言的移位、与、或等运算）
    //UINT64 index2 = (index1<<3) | (pht[index1]);
    //UINT64 index2 = (index1) | (pht[index1]<<10);
    UINT64 index2 = (index1 & 0x3ff) | (pht[index1]<<10 & 0x1c00);
	// 用13位去索引状态数组，得到对应的饱和状态
    if(State[index2] == 0 || State[index2] == 1) return NOT_TAKEN;
    return TAKEN;
	// 如果该状态的值超过一半，则预测跳转
	// 如果该状态的值低于一半，则预测不跳转
	
	//return TAKEN;
	// return NOT_TAKEN;

	// *********** 你需要在上面书写代码 ***********

}

// 2位状态的分支预测器（更新部分）
void  UpdatePredictor(UINT64 PC, OpType opType, char resolveDir, char predDir, UINT64 branchTarget)
{

	// *********** 你需要在下面书写代码 ***********
	// 根据分支指令实际执行结果，来更新对应的饱和计数器
	// 如果结果为跳转，则对应的饱和计数器+1
	// 如果结果为不跳转，则对应的饱和计数器-1
    // 更新pht中的最近3次分支历史信息，使用移位寄存器来更新
	// 将其更新到pht中
    UINT32 index1 = (PC>>2) & 0x3ff;
    //UINT64 index2 = (index1<<3) | (pht[index1]);
    //UINT64 index2 = (index1) | (pht[index1]<<10);
    UINT64 index2 = (index1 & 0x3ff) | (pht[index1]<<10 & 0x1c00);
    if(resolveDir == 'T')
    {
        State[index2] = SatIncrement(State[index2], 3);
        pht[index1] = (pht[index1]<<1) | 0x1;
    }
    else
    {
        State[index2] = SatDecrement(State[index2]);
        pht[index1] = (pht[index1]<<1);
    }


	// *********** 你需要在上面书写代码 ***********
}

void PREDICTOR_free(void)
{
	free(State);
	free(pht);
}


#include "common.h"

// 饱和计数器：加1
static inline UINT32 SatIncrement(UINT32 x, UINT32 max)
{
	if (x < max) return x + 1;
	return x;
}

// 饱和计数器：减1
static inline UINT32 SatDecrement(UINT32 x)
{
	if (x > 0) return x - 1;
	return x;
}

#define BITS_OF_PC 9		// 选择9位的PC作为索引
#define LOCAL_HIST_LEN   4	// 局部历史长度，4位
#define LOCAL_HIST_MASK  ~(~0  << LOCAL_HIST_LEN)

#define STATE_MAX  3
#define STATE_INIT 2

UINT32* pht;            // pattern history table    模式历史表
UINT32 phtArraySize;	// pht数组项数
UINT32* State;			// 状态数组，用于保存分支指令的状态机，实际只使用最低2位
UINT64 StateArraySize;

void PREDICTOR_init(void)
{
	StateArraySize = (1 << (BITS_OF_PC + LOCAL_HIST_LEN));    // 状态数组项数

	State = (UINT32*)malloc(StateArraySize * sizeof(UINT32));

	phtArraySize = (1 << BITS_OF_PC);	// pht数组项数

	pht = (UINT32*)malloc(phtArraySize * sizeof(UINT32));

	// *********** 你需要在下面书写代码 ***********
	// 将状态数组，全部初始化为STATE_INIT
	// 将模式历史表（pht）全部初始化为0
    for(UINT64 i = 0; i < StateArraySize; i++)
    {
        State[i] = STATE_INIT;
    }
    for(UINT32 i = 0; i < phtArraySize; i++)
    {
        pht[i] = 0;
    }
	// *********** 你需要在上面书写代码 ***********
}

// 2位状态的分支预测器（预测部分）
char GetPrediction(UINT64 PC)
{
	// *********** 你需要在下面书写代码 ***********
	// 将PC的低10位，去索引模式历史表pht，得到对应的3位历史信息
	// 将PC的低10位，与3位历史信息进行拼接，形成一个13位的状态数组索引（拼接需要使用C语言的移位、与、或等运算）
	// 用13位去索引状态数组，得到对应的饱和状态
	// 如果该状态的值超过一半，则预测跳转
	// 如果该状态的值低于一半，则预测不跳转
    UINT32 index1 = (PC>>2) & 0x1ff;
    UINT64 index2 = (index1 & 0x1ff) | (pht[index1]<<9 & 0x1e00);
	if(State[index2] == 0 || State[index2] == 1) return NOT_TAKEN;
    return TAKEN;
	//return TAKEN;
	// return NOT_TAKEN;

	// *********** 你需要在上面书写代码 ***********

}

// 2位状态的分支预测器（更新部分）
void  UpdatePredictor(UINT64 PC, OpType opType, char resolveDir, char predDir, UINT64 branchTarget)
{

	// *********** 你需要在下面书写代码 ***********
	// 根据分支指令实际执行结果，来更新对应的饱和计数器
	// 如果结果为跳转，则对应的饱和计数器+1
	// 如果结果为不跳转，则对应的饱和计数器-1
	// 更新pht中的最近3次分支历史信息，使用移位寄存器来更新
	// 将其更新到pht中
    UINT32 index1 = (PC>>2) & 0x1ff;
    UINT64 index2 = (index1 & 0x1ff) | (pht[index1]<<9 & 0x1e00);
    if(resolveDir == 'T')
    {
        State[index2] = SatIncrement(State[index2], 3);
        pht[index1] = (pht[index1]<<1) | 0x1;
    }
    else
    {
        State[index2] = SatDecrement(State[index2]);
        pht[index1] = (pht[index1]<<1);
    }
	// *********** 你需要在上面书写代码 ***********
}

void PREDICTOR_free(void)
{
	free(State);
	free(pht);
}


#include "common.h"

// 饱和计数器：加1
static inline UINT32 SatIncrement(UINT32 x, UINT32 max)
{
	if (x < max) return x + 1;
	return x;
}

// 饱和计数器：减1
static inline UINT32 SatDecrement(UINT32 x)
{
	if (x > 0) return x - 1;
	return x;
}

#define GLOBAL_HIST_LEN   13	// 全局历史长度，13位
#define GLOBAL_HIST_MASK  ~(~0  << GLOBAL_HIST_LEN)

#define STATE_MAX  3
#define STATE_INIT 2

UINT32 GHR;				// Global History Register，全局历史寄存器
UINT32* State;			// 状态数组，用于保存分支指令的状态机，实际只使用最低2位
UINT64 StateArraySize;

void PREDICTOR_init(void)
{
	StateArraySize = (1 << GLOBAL_HIST_LEN);    // 状态数组项数

	State = (UINT32*)malloc(StateArraySize * sizeof(UINT32));

	// *********** 你需要在下面书写代码 ***********
	// 将状态数组，全部初始化为STATE_INIT
	// 将全局历史寄存器（GHR）初始化为0
    for(UINT64 i = 0; i < StateArraySize; i++)
    {
        State[i] = STATE_INIT;
    }
    GHR = 0;
	// *********** 你需要在上面书写代码 ***********
}

// Gshare分支预测器（预测部分）
char GetPrediction(UINT64 PC)
{
	// *********** 你需要在下面书写代码 ***********
	// 用13位的GHR去索引状态数组，得到对应的饱和状态
	// 如果该状态的值超过一半，则预测跳转
	// 如果该状态的值低于一半，则预测不跳转
    UINT64 index = GHR & 0x1fff;
    if(State[index] == 0 || State[index] == 1) return NOT_TAKEN;
    return TAKEN;
	// return TAKEN;
	// return NOT_TAKEN;

	// *********** 你需要在上面书写代码 ***********

}

// Gshare分支预测器（更新部分）
void  UpdatePredictor(UINT64 PC, OpType opType, char resolveDir, char predDir, UINT64 branchTarget)
{

	// *********** 你需要在下面书写代码 ***********
	// 根据分支指令实际执行结果，来更新对应的饱和计数器
	// 如果结果为跳转，则对应的饱和计数器+1
	// 如果结果为不跳转，则对应的饱和计数器-1
	// 更新GHR中的最近1次分支历史信息，使用移位寄存器来更新
    UINT64 index = GHR & 0x1fff;
    if(resolveDir == 'T')
    {
        State[index] = SatIncrement(State[index], 3);
        GHR = GHR << 1 | 0x1;
    }
    else
    {
        State[index] = SatDecrement(State[index]);
        GHR = GHR << 1;
    }
    
	// *********** 你需要在上面书写代码 ***********
}

void PREDICTOR_free(void)
{
	free(State);
}



#include "common.h"

// 饱和计数器：加1
static inline UINT32 SatIncrement(UINT32 x, UINT32 max)
{
	if (x < max) return x + 1;
	return x;
}

// 饱和计数器：减1
static inline UINT32 SatDecrement(UINT32 x)
{
	if (x > 0) return x - 1;
	return x;
}

#define BITS_OF_PC 3		// 选择3位的PC作为索引
#define GLOBAL_HIST_LEN   10	// 全局历史长度，10位
#define STATE_INDEX_MASK  ~(~0  << (BITS_OF_PC + GLOBAL_HIST_LEN))

#define STATE_MAX  3
#define STATE_INIT 2

UINT32 GHR;				// Global History Register，全局历史寄存器
UINT32* State;			// 状态数组，用于保存分支指令的状态机，实际只使用最低2位
UINT64 StateArraySize;

void PREDICTOR_init(void)
{
	StateArraySize = (1 << (BITS_OF_PC +GLOBAL_HIST_LEN));    // 状态数组项数

	State = (UINT32*)malloc(StateArraySize * sizeof(UINT32));

	// *********** 你需要在下面书写代码 ***********
	// 将状态数组，全部初始化为STATE_INIT
	// 将全局历史寄存器（GHR）初始化为0
    for(UINT64 i = 0; i < StateArraySize; i++)
    {
        State[i] = STATE_INIT;
    }
    GHR = 0;
	// *********** 你需要在上面书写代码 ***********
}

// Gshare分支预测器（预测部分）
char GetPrediction(UINT64 PC)
{
	// *********** 你需要在下面书写代码 ***********
	// 将PC的低3位，与10位GHR进行拼接，形成一个13位的状态数组索引
	// 用13位去索引状态数组，得到对应的饱和状态
	// 如果该状态的值超过一半，则预测跳转
	// 如果该状态的值低于一半，则预测不跳转
	UINT64 index = (((PC>>2 & 0x7) << 10) & 0x1c00) | (GHR & 0x3ff);
    if(State[index] == 0 || State[index] == 1) return NOT_TAKEN;
    return TAKEN;
	// return TAKEN;
	// return NOT_TAKEN;

	// *********** 你需要在上面书写代码 ***********

}

// Gshare分支预测器（更新部分）
void  UpdatePredictor(UINT64 PC, OpType opType, char resolveDir, char predDir, UINT64 branchTarget)
{

	// *********** 你需要在下面书写代码 ***********
	// 根据分支指令实际执行结果，来更新对应的饱和计数器
	// 如果结果为跳转，则对应的饱和计数器+1
	// 如果结果为不跳转，则对应的饱和计数器-1
	// 更新GHR中的最近1次分支历史信息，使用移位寄存器来更新
    UINT64 index = (((PC>>2 & 0x7) << 10) & 0x1c00) | (GHR & 0x3ff);
    if(resolveDir == 'T')
    {
        State[index] = SatIncrement(State[index], 3);
        GHR = GHR << 1 | 0x1;
    }
    else
    {
        State[index] = SatDecrement(State[index]);
        GHR = GHR << 1;
    }
	// *********** 你需要在上面书写代码 ***********
}

void PREDICTOR_free(void)
{
	free(State);
}



#include "common.h"

// 饱和计数器：加1
static inline UINT32 SatIncrement(UINT32 x, UINT32 max)
{
	if (x < max) return x + 1;
	return x;
}

// 饱和计数器：减1
static inline UINT32 SatDecrement(UINT32 x)
{
	if (x > 0) return x - 1;
	return x;
}

#define GLOBAL_HIST_LEN   13	// 全局历史长度，13位
#define GLOBAL_HIST_MASK  ~(~0  << GLOBAL_HIST_LEN)

#define STATE_MAX  3
#define STATE_INIT 2

UINT32 GHR;				// Global History Register，全局历史寄存器
UINT32* State;			// 状态数组，用于保存分支指令的状态机，实际只使用最低2位
UINT64 StateArraySize;

void PREDICTOR_init(void)
{
	StateArraySize = (1 << GLOBAL_HIST_LEN);    // 状态数组项数

	State = (UINT32*)malloc(StateArraySize * sizeof(UINT32));

	// *********** 你需要在下面书写代码 ***********
	// 将状态数组，全部初始化为STATE_INIT
	// 将全局历史寄存器（GHR）初始化为0
    for(UINT64 i = 0; i < StateArraySize; i++)
    {
        State[i] = STATE_INIT;
    }
    GHR = 0;
	// *********** 你需要在上面书写代码 ***********
}

// Gshare分支预测器（预测部分）
char GetPrediction(UINT64 PC)
{
	// *********** 你需要在下面书写代码 ***********
	// 将PC的低13位，与13位GHR进行异或，形成一个13位的状态数组索引
	// 用13位去索引状态数组，得到对应的饱和状态
	// 如果该状态的值超过一半，则预测跳转
	// 如果该状态的值低于一半，则预测不跳转7]
    UINT64 nPC = (PC) & 0x1fff;
    UINT64 index = nPC ^ (GHR & 0x1fff);
    if(State[index] == 0 || State[index] == 1) return NOT_TAKEN;
    return TAKEN;
	// return TAKEN;
	// return NOT_TAKEN;

	// *********** 你需要在上面书写代码 ***********

}

// Gshare分支预测器（更新部分）
void  UpdatePredictor(UINT64 PC, OpType opType, char resolveDir, char predDir, UINT64 branchTarget)
{

	// *********** 你需要在下面书写代码 ***********
	// 根据分支指令实际执行结果，来更新对应的饱和计数器
	// 如果结果为跳转，则对应的饱和计数器+1
	// 如果结果为不跳转，则对应的饱和计数器-1
	// 更新GHR中的最近1次分支历史信息，使用移位寄存器来更新
    UINT64 nPC = (PC) & 0x1fff;
    UINT64 index = nPC ^ (GHR & 0x1fff);
    if(resolveDir == 'T')
    {
        State[index] = SatIncrement(State[index], 3);
        GHR = GHR << 1 | 0x1;
    }
    else
    {
        State[index] = SatDecrement(State[index]);
        GHR = GHR << 1;
    }

	// *********** 你需要在上面书写代码 ***********
}

void PREDICTOR_free(void)
{
	free(State);
}