两条简单题+一条中等题
StringBuilder
StringBuilder是一个可变的字符序列,在机试中经常使用.
构造方法直接如下即可，对字符串长度不会有限制，他会自动扩容.
StringBuilder sb = new StringBuilder();
常用的有方法如下:
public StringBuilder append(Object obj){
//往末尾加字符 or 字符串
}
public StringBuilder insert(offset, Object obj){
//在offset位置插入obj
}
Transformer
int&&binary
public static String intToBinary(String numStr) {
StringBuilder binStr = new StringBuilder();
for (int i = 31; i >= 0; i--) binStr.append(Integer.parseInt(numStr) >>> i & 1); // 直接移位秒杀 >>>指代无符号右移
return binStr.toString();
}
public static String binaryToInt(String binStr) {
int num = 0;
for (int i = 31; i >= 0; i--) num += binStr.charAt(i) != binStr.charAt(0) ? 1 << 31 - i : 0;
return String.valueOf(binStr.charAt(0) == '0' ? num : - num - 1); // 判定符号位 取反加一
}
NBCD
NBCD:每一个十进制位用四个二进制位来表示，比如, 十进制数 9 在 NBCD 编码中为 1001（当然这里还没有加上符号位）。在 NBCD 编码的十进制数前面还要加上四位表示符号的位，通常正数用 1100，负数用 1101，也就是通常意义下的符号位 0/1 前面加上一个 110
public static String decimalToNBCD(String decimalStr) {
StringBuilder NBCDStr = new StringBuilder(decimalStr.charAt(0) == '-' ? "1101" : "1100"); // 符号位
if (decimalStr.charAt(0) == '-') decimalStr = decimalStr.substring(1); // 删除负号
for (int i = decimalStr.length() - 7; i < decimalStr.length(); i++) NBCDStr.append(intToBinary(i >= 0 ? String.valueOf(decimalStr.charAt(i)) : "0").substring(28)); // 循环 调函数 加上就完事了
return NBCDStr.toString();
}
public static String NBCDToDecimal(String NBCDStr) {
int decimal = 0;
for (int i = 1; i <= 7; i++) decimal += Integer.parseInt(binaryToInt("0000000000000000000000000000" + NBCDStr.substring(4 * i, 4 * i + 4))) * (int) Math.pow(10, 7 - i); // 循环 调函数 乘位数加上就完事了
return (NBCDStr.charAt(3) == '1' ? "-" : "") + decimal; // 判定符号位
}
Float
public static String floatToBinary(String floatStr) {
float flo = Float.parseFloat(floatStr);
if (String.valueOf(flo).endsWith("Infinity")) return (flo < 0 ? "-" : "+") + "Inf"; // 上溢
StringBuilder binStr = new StringBuilder(flo < 0 ? "1" : "0"); // 符号位
flo = flo < 0 ? - flo : flo;
double ints = Math.floor(flo); // 取整数部分
double decs = flo - ints; // 取小数部分
while(ints != 0){
binStr.insert(1, (ints % 2 == 1) ? "1" : "0");
ints -= Math.ceil(ints / 2);
}// 整数部分不为 0 的时候 正常十转二 然后直接 return
if (binStr.length() > 1) return binStr.charAt(0) + intToBinary(String.valueOf(binStr.length() + 125)).substring(24) + binStr.substring(2, Math.min(binStr.length(), 25)) + decsToBinary(decs, 24 - binStr.length());
int e = 0; // 整数部分为 0 时
for (; e < 127 && decs < 1; e++) decs *= 2; // 先去掉小数部分的前导 0 在规格化的情况下
if (e == 127) binStr.append(decsToBinary(decs, 0)); // 非规格化的情况
if (decs >= 1) decs--; // 把整数部分的 1 清理掉 然后直接 return
return binStr.charAt(0) + intToBinary(String.valueOf(127 - e)).substring(24) + binStr.append(decsToBinary(decs, 23)).substring(1, 24);
}
private static String decsToBinary(double decs, int length) {
StringBuilder binDecStr = new StringBuilder();
while(binDecStr.length() <= length){
if(length != 0){
binDecStr.append(((decs *= 2) >= 1) ? "1" : "0");
}
else{
binDecStr.append(decs >= 1 ? "1" : "0");
}
if(decs >= 1){
decs -= 1;
}
}
return binDecStr.toString();
}
public static String binaryToFloat(String binStr) {
if (binStr.endsWith("1111111100000000000000000000000")) return ((binStr.charAt(0) == '1') ? "-" : "+") + "Inf"; // 上溢
int e = Integer.parseInt(binaryToInt("000000000000000000000000" + binStr.substring(1, 9))); // 指数部分
float f = 0;
for (int i = 9; i < 32; i++) f += binStr.charAt(i) == '1' ? Math.pow(2, 8 - i) : 0; // 小数部分
return (binStr.charAt(0) == '1' ? "-" : "") + (float) Math.pow(2, e != 0 ? e - 127 : - 126) * (e != 0 ? 1 + f : f); // 判定规格化与否 直接 return
}
public static String floatToBinary(String floatStr) {
// TODO:
float ans = Float.parseFloat(floatStr);
if(ans == 0){
return "00000000000000000000000000000000";
}
if (ans > Float.MAX_VALUE && floatStr.charAt(0) != '-') {
return "+Inf";
} else if (ans < -Float.MAX_VALUE && floatStr.charAt(0) == '-') {
return "-Inf";
}
int index = 0;
if (ans < 0) {
ans = -ans;
index = 1;
}
int x = (int) ans;
float y = ans - x;
String str1 = intToBinary(Integer.toString(x));
String str2 = "";
while (y != 0) {
y = y * 2;
if (y >= 1) {
y -= 1;
str2 = str2.concat("1");
} else {
str2 = str2.concat("0");
}
}
if (str1.equals("00000000000000000000000000000000")) {
int firstone = str2.indexOf('1');
int head = 127 - firstone - 1;
if (index == 0) {
if(head <= 0){
String temp = "";
for(int i = 0; i < 23 - str2.length() + 126; i++){
temp = temp.concat("0");
}
if(str2.length() >= 23 + 126){
return "000000000" + str2.substring(126, 149);
}
else{
return "000000000" + str2.substring(126) + temp;
}
}
else{
if (str2.length() > firstone + 23) {
return "0" + intToBinary(Integer.toString(head)).substring(24, 32) + str2.substring(firstone + 1, firstone + 24);
}
else {
String temp = "";
for (int i = 0; i < firstone + 24 - str2.length(); i++) {
temp = temp.concat("0");
}
return "0"+ intToBinary(Integer.toString(head)).substring(24, 32) + str2.substring(firstone + 1) + temp;
}
}
}
else{
if (str2.length() > firstone + 23) {
return "1" + intToBinary(Integer.toString(head)).substring(24, 32) + str2.substring(firstone + 1, firstone + 24);
}
else {
String temp = "";
for (int i = 0; i < firstone + 24 - str2.length(); i++) {
temp = temp.concat("0");
}
return "1"+ intToBinary(Integer.toString(head)).substring(24, 32) + str2.substring(firstone +1) + temp;
}
}
}
else{
int numofstr1 = 31 - str1.indexOf('1');
if(index == 0){
if(str2.length() >= 23 - numofstr1){
return "0" + intToBinary(Integer.toString(numofstr1 + 127)).substring(24, 32) + str1.substring(str1.indexOf('1') + 1) + str2.substring(0, 24 - numofstr1);
}
else{
String num0 = "";
for(int i = 0; i < 23 - numofstr1 - str2.length(); i++){
num0 = num0.concat("0");
}
return "0" + intToBinary(Integer.toString(numofstr1 + 127)).substring(24, 32) + str1.substring(str1.indexOf('1') +1) + str2 + num0;
}
}
else {
if(str2.length() >= 23 - numofstr1){
return "1" + intToBinary(Integer.toString(numofstr1 + 127)).substring(24, 32) + str1.substring(str1.indexOf('1') + 1) + str2.substring(0, 24 - numofstr1);
}
else{
String num0 = "";
for(int i = 0; i < 23 - numofstr1 - str2.length(); i++){
num0 = num0.concat("0");
}
return "1" + intToBinary(Integer.toString(numofstr1 + 127)).substring(24, 32) + str1.substring(str1.indexOf('1') + 1) + str2 + num0;
}
}
}
}//AC
public static String binaryToFloat(String binStr) {
// TODO:
if(binStr.equals("01111111100000000000000000000000")){
return "+Inf";
}
else if(binStr.equals("11111111100000000000000000000000")){
return "-Inf";
}
else{
int x = Integer.parseInt(binaryToInt("000000000000000000000000" + binStr.substring(1,9)));
int y = Integer.parseInt(binaryToInt("000000000" + binStr.substring(9,32)));
if(x == 0){
if(binStr.charAt(0) == '0'){
return Float.toString((float) (y * Math.pow(2, -149)));
}
else{
return Float.toString((float) (-y * Math.pow(2, 149)));
}
}
else {
if(binStr.charAt(0) == '0'){
return Float.toString((float)(y * Math.pow(2, x - 150) + Math.pow(2, x - 127)));
}
return Float.toString((float) (-((y * Math.pow(2, x - 150) + Math.pow(2, x - 127)))));
}
}
}//AC
对于特殊情况的判断，以及Float.parseFloat()方法没想到
ALU
add
/**
* 返回两个二进制整数的和
* dest + src
*
* @param src 32-bits
* @param dest 32-bits
* @return 32-bits
*/
public DataType add(DataType src, DataType dest) {
StringBuilder ansStr = new StringBuilder();
int[] tmp = new int[33];
for (int i = 0; i < 32; i++) {
tmp[i] += dest.toString().charAt(31 - i) + src.toString().charAt(31 - i) - 2 * '0';
if (tmp[i] > 1) {
tmp[i + 1] += 1;
tmp[i] -= 2;
}
ansStr.insert(0, tmp[i]);
}
return new DataType(ansStr.toString());
}
sub
/**
* 返回两个二进制整数的差
* dest - src
*
* @param src 32-bits
* @param dest 32-bits
* @return 32-bits
*/
public DataType sub(DataType src, DataType dest) {
StringBuilder ansStr = new StringBuilder();
int[] tmp = new int[33];
for (int i = 0; i < 32; i++) {
tmp[i] += dest.toString().charAt(31 - i) - src.toString().charAt(31 - i);
if (tmp[i] < 0) {
tmp[i + 1] -= 1;
tmp[i] += 2;
}
ansStr.insert(0, tmp[i]);
}
return new DataType(ansStr.toString());
}
mul
乘积寄存器P
乘数寄存器Y
这里面的Y~i~指的是乘数寄存器,不难总结出规律
/**
* 返回两个二进制整数的乘积(结果低位截取后32位)
* dest * src
*
* @param src 32-bits
* @param dest 32-bits
* @return 32-bits
*/
public DataType mul(DataType src, DataType dest) {
int[] ansStr = new int[33];
int[] x = new int[33];
int[] y = new int[33];
for (int i = 0; i < 32; i++) {
x[31 - i] = src.toString().charAt(i) - '0';
y[31 - i] = dest.toString().charAt(i) - '0';
}
boolean neg = x[31] != y[31];//符号位 判断符号的
if (x[31] == 1) {
for (int i = 0; i < 32; i++) {
x[i] = x[i] ^ 1;
}
x[0]++;
for (int i = 0; i < 32; i++) {
if (x[i] > 1) {
x[i + 1] += 1;
x[i] -= 2;
}
}
}//取反+1
if (y[31] == 1) {
for (int i = 0; i < 32; i++) {
y[i] = y[i] ^ 1;
}
y[0]++;
for (int i = 0; i < 32; i++) {
if (y[i] > 1) {
y[i + 1] += 1;
y[i] -= 2;
}
}
}//取反+1
for (int i = 0; i < 32; i++) {
for (int j = 0; j <= i; j++)
ansStr[i] += x[j] * y[i - j];
if (ansStr[i] >= 2) {
ansStr[i + 1] += ansStr[i] / 2;
ansStr[i] %= 2;
}
}
if (neg) {
for (int i = 0; i < 32; i++) {
ansStr[i] = ansStr[i] ^ 1;
}
ansStr[0]++;
for (int i = 0; i < 32; i++) {
if (ansStr[i] > 1) {
ansStr[i + 1] += 1;
ansStr[i] -= 2;
}
}
}
StringBuilder repr = new StringBuilder();
for (int i = 0; i < 32; i++)
repr.append(ansStr[31 - i]);
return new DataType(repr.toString());
}
public DataType mul2(DataType src, DataType dest) {
StringBuilder ansStr = new StringBuilder();
int[] tmp = new int[33];
for (int i = 0; i < 32; i++) {
for (int j = 0; j <= i; j++)
tmp[i] += (dest.toString().charAt(31 - i + j) - '0') * (src.toString().charAt(31 - j) - '0');
if (tmp[i] >= 2) {
tmp[i + 1] += tmp[i] / 2;
tmp[i] %= 2;
}
ansStr.insert(0, tmp[i]);
}
return new DataType(ansStr.toString());
}
/**
* 返回两个二进制整数的乘积(结果低位截取后32位)
* dest * src
*
* @param src 32-bits
* @param dest 32-bits
* @return 32-bits
*/
public DataType mul(DataType src, DataType dest) {
// TODO
String srcStr = src.toString();
String srcStr1 = sub(src ,new DataType("00000000000000000000000000000000")).toString();//取反
String destStr = dest.toString();
char[] ans = new char[65];
for(int i = 0; i < 32; ++i){
ans[i] = '0';
}
for (int i = 32; i < 64; ++i){
ans[i] = destStr.charAt(i - 32);
}
ans[64] = '0';
//上面完成了初始化,把P设置好了
for(int i = 64; i >= 33; --i){
if(ans[64] - ans[63] > 0){//判断Y~i~ - Y~i+1~的符号 >0则+X <0则-X =0则什么都不干 最后右移
for(int j = 0; j < 32; ++j){
ans[j] += (char) (srcStr.charAt(j) - '0');
}
for(int j = 31; j > 0; --j){
if(ans[j] >= '2'){
ans[j] -= 2;
ans[j - 1] += 1;
}
}
if(ans[0] == '2'){
ans[0] = '0';
}
}
else if(ans[64] - ans[63] < 0){
for(int j = 0; j < 32; ++j){
ans[j] += (char) (srcStr1.charAt(j) - '0');
}
for(int j = 31; j > 0; --j){
if(ans[j] >= '2'){
ans[j] -= 2;
ans[j - 1] += 1;
}
}
if(ans[0] >= '2'){
ans[0] -= 2;
}
}
for(int j = 64; j >= 1; --j){
ans[j] = ans[j - 1];
}
ans[0] = ans[1];//算术右移
}
return new DataType(new String(ans).substring(32, 64));
}//布斯乘法版
eg.
div
DataType remainderReg;
/**
* 返回两个二进制整数的除法结果
* dest ÷ src
*
* @param src 32-bits
* @param dest 32-bits
* @return 32-bits
*/
public DataType div(DataType src, DataType dest) {
// TODO
String srcStr = src.toString();
String destStr = dest.toString();
if(srcStr.equals(Transformer.intToBinary("0"))){
throw new ArithmeticException("Division by zero");
}
if(destStr.equals(Transformer.intToBinary("0"))){
remainderReg = new DataType(Transformer.intToBinary("0"));
return new DataType(Transformer.intToBinary("0"));
}
//下面对余数寄存器进行初始化
char[] ans = new char[64];
for(int i = 32; i < 64; ++i){
ans[i] = destStr.charAt(i - 32);
}
for(int i = 0; i < 32; ++i){
ans[i] = ans[32];
}
for(int k = 0; k < 32; ++k){
for(int i = 0; i < 63; ++i){
ans[i] = ans[i + 1];
}//左移
ans[63] = '0';//用来放商的,暂时设置为0
//除数与余数符号相同 做减法
if(ans[0] == '1' && srcStr.charAt(0) == '1'){
String temp = sub(src, new DataType(new String(ans).substring(0, 32))).toString();
//判断是否够减(余数是否位全为0)
int iszero = 1;
for(int i = 0; i < 32; ++i){
if(temp.charAt(i) != '0'){
iszero = 0;
break;
}
}
for(int i = 32; i <= 63 - k; ++i){
if(ans[i] != '0'){
iszero = 0;
break;
}
}
if(temp.charAt(0) == '1' || iszero == 1){
for(int i = 0; i < 32 ; i++){
ans[i] = temp.charAt(i);
}
ans[63] = '1';//够减 上商为1
}
}
else if(ans[0] == '0' && srcStr.charAt(0) == '0'){
String temp = sub(src, new DataType(new String(ans).substring(0, 32))).toString();
int iszero = 1;
for(int i = 0; i < 32; ++i){
if(temp.charAt(i) != '0'){
iszero = 0;
break;
}
}
for(int i = 32; i <= 63 - k; ++i){
if(ans[i] != '0'){
iszero = 0;
break;
}
}
if(temp.charAt(0) == '0' || iszero == 1){
for(int i = 0; i < 32 ; i++){
ans[i] = temp.charAt(i);
}
ans[63] = '1';
}
}
//异号
else if(ans[0] == '1' && srcStr.charAt(0) == '0'){
String temp = add(new DataType(new String(ans).substring(0, 32)), src).toString();
int iszero = 1;
for(int i = 0; i < 32; ++i){
if(temp.charAt(i) != '0'){
iszero = 0;
break;
}
}
for(int i = 32; i <= 63 - k; ++i){
if(ans[i] != '0'){
iszero = 0;
break;
}
}
if(temp.charAt(0) == '1' || iszero == 1){
for(int i = 0; i < 32 ; i++){
ans[i] = temp.charAt(i);
}
ans[63] = '1';
}
}
else if(ans[0] == '0' && srcStr.charAt(0) == '1'){
String temp = add(new DataType(new String(ans).substring(0, 32)), src).toString();
int iszero = 1;
for(int i = 0; i < 32; ++i){
if(temp.charAt(i) != '0'){
iszero = 0;
break;
}
}
for(int i = 32; i <= 63 - k; ++i){
if(ans[i] != '0'){
iszero = 0;
break;
}
}
if(temp.charAt(0) == '0' || iszero == 1){
for(int i = 0; i < 32 ; i++){
ans[i] = temp.charAt(i);
}
ans[63] = '1';
}
}
}
if(srcStr.charAt(0) != destStr.charAt(0)){
String temp = sub(new DataType(new String(ans).substring(32, 64)), new DataType(Transformer.intToBinary("0"))).toString();
for(int i = 0; i < 32; ++i){
ans[i + 32] = temp.charAt(i);
}
}//除数与被除数异号,取反
remainderReg = new DataType(new String(ans).substring(0, 32));
return new DataType(new String(ans).substring(32, 64));
}
FPU
下面是提供的一些辅助方法
private final String[][] addCorner = new String[][]{
{IEEE754Float.P_ZERO, IEEE754Float.P_ZERO, IEEE754Float.P_ZERO},
{IEEE754Float.N_ZERO, IEEE754Float.P_ZERO, IEEE754Float.P_ZERO},
{IEEE754Float.P_ZERO, IEEE754Float.N_ZERO, IEEE754Float.P_ZERO},
{IEEE754Float.N_ZERO, IEEE754Float.N_ZERO, IEEE754Float.N_ZERO},
{IEEE754Float.P_INF, IEEE754Float.N_INF, IEEE754Float.NaN},
{IEEE754Float.N_INF, IEEE754Float.P_INF, IEEE754Float.NaN}
};
private final String[][] subCorner = new String[][]{
{IEEE754Float.P_ZERO, IEEE754Float.P_ZERO, IEEE754Float.P_ZERO},
{IEEE754Float.N_ZERO, IEEE754Float.P_ZERO, IEEE754Float.N_ZERO},
{IEEE754Float.P_ZERO, IEEE754Float.N_ZERO, IEEE754Float.P_ZERO},
{IEEE754Float.N_ZERO, IEEE754Float.N_ZERO, IEEE754Float.P_ZERO},
{IEEE754Float.P_INF, IEEE754Float.P_INF, IEEE754Float.NaN},
{IEEE754Float.N_INF, IEEE754Float.N_INF, IEEE754Float.NaN}
};
private final String[][] mulCorner = new String[][]{
{IEEE754Float.P_ZERO, IEEE754Float.N_ZERO, IEEE754Float.N_ZERO},
{IEEE754Float.N_ZERO, IEEE754Float.P_ZERO, IEEE754Float.N_ZERO},
{IEEE754Float.P_ZERO, IEEE754Float.P_ZERO, IEEE754Float.P_ZERO},
{IEEE754Float.N_ZERO, IEEE754Float.N_ZERO, IEEE754Float.P_ZERO},
{IEEE754Float.P_ZERO, IEEE754Float.P_INF, IEEE754Float.NaN},
{IEEE754Float.P_ZERO, IEEE754Float.N_INF, IEEE754Float.NaN},
{IEEE754Float.N_ZERO, IEEE754Float.P_INF, IEEE754Float.NaN},
{IEEE754Float.N_ZERO, IEEE754Float.N_INF, IEEE754Float.NaN},
{IEEE754Float.P_INF, IEEE754Float.P_ZERO, IEEE754Float.NaN},
{IEEE754Float.P_INF, IEEE754Float.N_ZERO, IEEE754Float.NaN},
{IEEE754Float.N_INF, IEEE754Float.P_ZERO, IEEE754Float.NaN},
{IEEE754Float.N_INF, IEEE754Float.N_ZERO, IEEE754Float.NaN}
};
private final String[][] divCorner = new String[][]{
{IEEE754Float.P_ZERO, IEEE754Float.P_ZERO, IEEE754Float.NaN},
{IEEE754Float.N_ZERO, IEEE754Float.N_ZERO, IEEE754Float.NaN},
{IEEE754Float.P_ZERO, IEEE754Float.N_ZERO, IEEE754Float.NaN},
{IEEE754Float.N_ZERO, IEEE754Float.P_ZERO, IEEE754Float.NaN},
{IEEE754Float.P_INF, IEEE754Float.P_INF, IEEE754Float.NaN},
{IEEE754Float.N_INF, IEEE754Float.N_INF, IEEE754Float.NaN},
{IEEE754Float.P_INF, IEEE754Float.N_INF, IEEE754Float.NaN},
{IEEE754Float.N_INF, IEEE754Float.P_INF, IEEE754Float.NaN},
};
/**
* check corner cases of mul and div
*
* @param cornerMatrix corner cases pre-stored
* @param oprA first operand (String)
* @param oprB second operand (String)
* @return the result of the corner case (String)
*/
private String cornerCheck(String[][] cornerMatrix, String oprA, String oprB) {
for (String[] matrix : cornerMatrix) {
if (oprA.equals(matrix[0]) && oprB.equals(matrix[1])) {
return matrix[2];
}
}
return null;
}
/**
* right shift a num without considering its sign using its string format
*
* @param operand to be moved
* @param n moving nums of bits
* @return after moving
*/
private String rightShift(String operand, int n) {
StringBuilder result = new StringBuilder(operand); //保证位数不变
boolean sticky = false;
for (int i = 0; i < n; i++) {
sticky = sticky || result.toString().endsWith("1");
result.insert(0, "0");
result.deleteCharAt(result.length() - 1);
}
if (sticky) {
result.replace(operand.length() - 1, operand.length(), "1");
}
return result.substring(0, operand.length());
}
/**
* 对GRS保护位进行舍入
*
* @param sign 符号位
* @param exp 阶码
* @param sig_grs 带隐藏位和保护位的尾数
* @return 舍入后的结果
*/
private String round(char sign, String exp, String sig_grs) {
int grs = Integer.parseInt(sig_grs.substring(24, 27), 2);
if ((sig_grs.substring(27).contains("1")) && (grs % 2 == 0)) {
grs++;
}
String sig = sig_grs.substring(0, 24); // 隐藏位+23位
if (grs > 4) {
sig = oneAdder(sig);
} else if (grs == 4 && sig.endsWith("1")) {
sig = oneAdder(sig);
}
if (Integer.parseInt(sig.substring(0, sig.length() - 23), 2) > 1) {
sig = rightShift(sig, 1);
exp = oneAdder(exp).substring(1);
}
if (exp.equals("11111111")) {
return sign == '0' ? IEEE754Float.P_INF : IEEE754Float.N_INF;
}
return sign + exp + sig.substring(sig.length() - 23);
}
/**
* add one to the operand
*
* @param operand the operand
* @return result after adding, the first position means overflow (not equal to the carry to the next)
* and the remains means the result
*/
private String oneAdder(String operand) {
int len = operand.length();
StringBuilder temp = new StringBuilder(operand);
temp.reverse();
int[] num = new int[len];
for (int i = 0; i < len; i++) num[i] = temp.charAt(i) - '0'; //先转化为反转后对应的int数组
int bit = 0x0;
int carry = 0x1;
char[] res = new char[len];
for (int i = 0; i < len; i++) {
bit = num[i] ^ carry;
carry = num[i] & carry;
res[i] = (char) ('0' + bit); //显示转化为char
}
String result = new StringBuffer(new String(res)).reverse().toString();
return "" + (result.charAt(0) == operand.charAt(0) ? '0' : '1') + result; //注意有进位不等于溢出，溢出要另外判断
}
add
对于浮点数加减运算的流程，课件与课本都有很详细的讲解，在此不再赘述。对于代码实现层面，大致可分为以下几步:
1. 处理边界情况(NaN, 0, INF)
2. 提取符号、阶码、尾数
3. 模拟运算得到中间结果
4. 规格化并舍入后返回
/**
* compute the float add of (dest + src)
*/
public DataType add(DataType src, DataType dest) {
//TODO
String srcStr = src.toString();
String destStr = dest.toString();
//判断所有特殊情况
if (srcStr.matches(IEEE754Float.NaN_Regular) || destStr.matches(IEEE754Float.NaN_Regular)) {
return new DataType(IEEE754Float.NaN);
}
String hr = cornerCheck(addCorner, srcStr, destStr);
if(hr != null){
return new DataType(hr);
}
if(srcStr.equals(IEEE754Float.P_INF) || destStr.equals(IEEE754Float.P_INF)){
return new DataType(IEEE754Float.P_INF);
}
if(srcStr.equals(IEEE754Float.N_INF) || destStr.equals(IEEE754Float.N_INF)){
return new DataType(IEEE754Float.N_INF);
}
char srcsign = srcStr.charAt(0);
char destsign = destStr.charAt(0);
int srcexpint = Integer.parseInt(Transformer.binaryToInt("000000000000000000000000" + srcStr.substring(1, 9)));
int destexpint = Integer.parseInt(Transformer.binaryToInt("000000000000000000000000" + destStr.substring(1, 9)));
char[] srcarr = new char[27]; //0位放1or0(小数点前的那个) 1~23位放尾数 24~26位放GRS保护位
char[] destarr = new char[27];
char[] ansarr = new char[27];
for(int i = 1; i < 24; i++){
srcarr[i] = srcStr.charAt(i + 8);
destarr[i] = destStr.charAt(i + 8);
}
for(int i = 24; i < 27; i++){
srcarr[i] = '0';
destarr[i] = '0';
}
for(int i = 0; i < 27; i++){
ansarr[i] = '0';
}
int index = 0;
if (srcexpint == 0) {
srcarr[0] = '0';
}
else{
srcarr[0] = '1';
}
if (destexpint == 0) {
destarr[0] = '0';
}
else{
destarr[0] = '1';
}
//底下这个+1就很灵性 是非规格化数的性质
if(srcexpint == 0){
srcexpint++;
}
if(destexpint == 0){
destexpint++;
}
//到这里初始化结束，开始对阶 对阶当然是小的往大的靠
if(srcexpint > destexpint){
int x = srcexpint - destexpint;
destarr = rightShift(new String(destarr), x).toCharArray();
destexpint = srcexpint;
}
else if(srcexpint < destexpint){
int x = destexpint - srcexpint;
srcarr = rightShift(new String(srcarr), x).toCharArray();
srcexpint = destexpint;
}//这同上
//对阶完,她直接是0了,那就直接返回
index = 0;
for(int i = 0; i < 27; ++i){
if(srcarr[i] == '1'){
index = 1;
break;
}
}
if(index == 0){
return dest;
}
index = 0;
for(int i = 0; i < 27; ++i){
if(destarr[i] == '1'){
index = 1;
break;
}
}
if(index == 0){
return src;
}
//到这里阶码对齐结束，开始对尾数进行处理
if(srcsign == destsign){
//非常淳朴的加法
for(int i = 0; i < 27; ++i){
ansarr[i] = (char) (srcarr[i] + destarr[i] - '0');
}
for(int i = 26; i > 0; --i){
if(ansarr[i] == '2'){
ansarr[i] = '0';
ansarr[i - 1] = (char) (ansarr[i - 1] + 1);
}
if(ansarr[i] == '3'){
ansarr[i] = '1';
ansarr[i - 1] = (char) (ansarr[i - 1] + 1);
}
}
//处理最高进位的情况
if(srcexpint == 0 && ansarr[0] == '1'){
srcexpint++;
}
if(ansarr[0] == '2'){
ansarr[0] = '0';
srcexpint++;
ansarr = rightShift(new String(ansarr), 1).toCharArray();
ansarr[0] = '1';
}
if(ansarr[0] == '3'){
ansarr[0] = '1';
srcexpint++;
ansarr = rightShift(new String(ansarr), 1).toCharArray();
ansarr[0] = '1';
}
//检查是否出现0了
int num = 0;
for(int i = 0; i < 27; ++i){
if(ansarr[i] == '0'){
num++;
}
else{
break;
}
}
if(num == 27){
if(srcsign == '0'){
return new DataType(IEEE754Float.P_ZERO);
}
else{
return new DataType(IEEE754Float.N_ZERO);
}
}
//规格化
if(srcexpint > num){
int x = num;
for(int i = 0; i < 27 - x; ++i){
ansarr[i] = ansarr[i + x];
}//相当于左移x位
for(int i = 27 - x; i < 27; ++i){
ansarr[i] = '0';
}//后面补0
srcexpint = srcexpint - num;//exponent减去移动的位数
}
else {
//说明是非规格化数
int x = srcexpint;
if(x != 0) {
for(int i = 0; i < 27 - x + 1; ++i){
ansarr[i] = ansarr[i + x - 1];
}//左移x - 1位
for(int i = 27 - x + 1; i < 27; ++i){
ansarr[i] = '0';
}
}
srcexpint = 0;
}
return new DataType(round(srcsign, Transformer.intToBinary(Integer.toString(srcexpint)).substring(24,32), new String(ansarr)));
}
else if(srcsign == '1' && destsign == '0'){
char anssign = '0';
//给src取反+1
for(int i = 0; i < 27; ++i){
srcarr[i] = srcarr[i] == '1' ? '0' : '1';
}
srcarr[26] = (char) (srcarr[26] + 1);
for(int i = 26; i > 0; --i){
if(srcarr[i] == '2'){
srcarr[i] = '0';
srcarr[i - 1] = (char) (srcarr[i - 1] + 1);
}
if(srcarr[i] == '3'){
srcarr[i] = '1';
srcarr[i - 1] = (char) (srcarr[i - 1] + 1);
}
}
if(srcexpint == 0 && ansarr[0] == '1'){
srcexpint++;
}
if(srcarr[0] == '2'){
srcarr[0] = '0';
}
else if(srcarr[0] == '3'){
srcarr[0] = '1';
}
for(int i = 0; i < 27; ++i){
ansarr[i] = (char) (srcarr[i] + destarr[i] - '0');
}
for(int i = 26; i > 0; --i){
if(ansarr[i] == '2'){
ansarr[i] = '0';
ansarr[i - 1] = (char) (ansarr[i - 1] + 1);
}
if(ansarr[i] == '3'){
ansarr[i] = '1';
ansarr[i - 1] = (char) (ansarr[i - 1] + 1);
}
}
int judge = 0;
if(ansarr[0] == '2'){
ansarr[0] = '0';
judge = 1;
}
if(ansarr[0] == '3'){
ansarr[0] = '1';
judge = 1;
}
if(judge == 0){
//说明
for(int i = 26; i >= 0; --i){
ansarr[i] = ansarr[i] == '1'? '0' : '1';
}
anssign = '1';
ansarr[26]++;
for(int i = 26; i > 0; --i){
if(ansarr[i] == '2'){
ansarr[i] = '0';
ansarr[i - 1] = (char) (ansarr[i - 1] + 1);
}
if(ansarr[i] == '3'){
ansarr[i] = '1';
ansarr[i - 1] = (char) (ansarr[i - 1] + 1);
}
}
if(ansarr[0] == '2'){
ansarr[0] = '0';
}
else if(ansarr[0] == '3'){
ansarr[0] = '1';
}
}
int num = 0;
for(int i = 0; i < 27; ++i){
if(ansarr[i] == '0'){
num++;
}
else{
break;
}
}
if(num == 27){
if(anssign == '0'){
return new DataType(IEEE754Float.P_ZERO);
}
else{
return new DataType(IEEE754Float.N_ZERO);
}
}
if(srcexpint > num){
int x = num;
for(int i = 0; i < 27 - x; ++i){
ansarr[i] = ansarr[i + x];
}
for(int i = 27 - x; i < 27; ++i){
ansarr[i] = '0';
}
srcexpint = srcexpint - num;
}
else {
int x = srcexpint;
if(x != 0) {
for(int i = 0; i < 27 - x + 1; ++i){
ansarr[i] = ansarr[i + x - 1];
}
for(int i = 27 - x + 1; i < 27; ++i){
ansarr[i] = '0';
}
}
srcexpint = 0;
}
return new DataType(round(anssign, Transformer.intToBinary(Integer.toString(srcexpint)).substring(24,32), new String(ansarr)));
}
else{
char anssign = '0';
for(int i = 0; i < 27; ++i){
destarr[i] = destarr[i] == '1' ? '0' : '1';
}
destarr[26] = (char) (destarr[26] + 1);
for(int i = 26; i > 0; --i){
if(destarr[i] == '2'){
destarr[i] = '0';
destarr[i - 1] = (char) (destarr[i - 1] + 1);
}
if(destarr[i] == '3'){
destarr[i] = '1';
destarr[i - 1] = (char) (destarr[i - 1] + 1);
}
}
if(srcexpint == 0 && ansarr[0] == '1'){
srcexpint++;
}
if(destarr[0] == '2'){
destarr[0] = '0';
}
else if(destarr[0] == '3'){
destarr[0] = '1';
}
for(int i = 0; i < 27; ++i){
ansarr[i] = (char) (srcarr[i] + destarr[i] - '0');
}
for(int i = 26; i > 0; --i){
if(ansarr[i] == '2'){
ansarr[i] = '0';
ansarr[i - 1] = (char) (ansarr[i - 1] + 1);
}
if(ansarr[i] == '3'){
ansarr[i] = '1';
ansarr[i - 1] = (char) (ansarr[i - 1] + 1);
}
}
int judge = 0;
if(ansarr[0] == '2'){
ansarr[0] = '0';
judge = 1;
}
if(ansarr[0] == '3'){
ansarr[0] = '1';
judge = 1;
}
if(judge == 0){
for(int i = 26; i >= 0; --i){
ansarr[i] = ansarr[i] == '1'? '0' : '1';
}
anssign = '1';
ansarr[26]++;
for(int i = 26; i > 0; --i){
if(ansarr[i] == '2'){
ansarr[i] = '0';
ansarr[i - 1] = (char) (ansarr[i - 1] + 1);
}
if(ansarr[i] == '3'){
ansarr[i] = '1';
ansarr[i - 1] = (char) (ansarr[i - 1] + 1);
}
}
if(ansarr[0] == '2'){
ansarr[0] = '0';
}
else if(ansarr[0] == '3'){
ansarr[0] = '1';
}
}
int num = 0;
for(int i = 0; i < 27; ++i){
if(ansarr[i] == '0'){
num++;
}
else{
break;
}
}
if(num == 27){
if(anssign == '0'){
return new DataType(IEEE754Float.P_ZERO);
}
else{
return new DataType(IEEE754Float.N_ZERO);
}
}
if(srcexpint > num){
int x = num;
for(int i = 0; i < 27 - x; ++i){
ansarr[i] = ansarr[i + x];
}
for(int i = 27 - x; i < 27; ++i){
ansarr[i] = '0';
}
srcexpint = srcexpint - num;
}
else {
int x = srcexpint;
if(x != 0) {
for(int i = 0; i < 27 - x + 1; ++i){
ansarr[i] = ansarr[i + x - 1];
}
for(int i = 27 - x + 1; i < 27; ++i){
ansarr[i] = '0';
}
}
srcexpint = 0;
}
return new DataType(round(anssign, Transformer.intToBinary(Integer.toString(srcexpint)).substring(24,32), new String(ansarr)));
}
}
sub
有了add sub不要太轻松
/**
* compute the float add of (dest - src)
*/
public DataType sub(DataType src, DataType dest) {
//TODO
String srcStr = src.toString();
String temp;
if(srcStr.charAt(0) == '1'){
temp = "0" + srcStr.substring(1);
}
else{
temp = "1" + srcStr.substring(1);
}
DataType tempData = new DataType(temp);
return add(tempData, dest);
}
mul
/**
* compute the float mul of (dest * src)
*/
public DataType mul(DataType src,DataType dest){
//TODO
String srcStr = src.toString();
String destStr = dest.toString();
//先判断特殊情况
if (srcStr.matches(IEEE754Float.NaN_Regular) || destStr.matches(IEEE754Float.NaN_Regular)) {
return new DataType(IEEE754Float.NaN);
}
String hr = cornerCheck(mulCorner, srcStr, destStr);
if(hr != null){
return new DataType(hr);
}
int[] srcarr = new int[27];
int[] destarr = new int[27];
int[] ansarr = new int[54];
for(int i = 0; i < 54; ++i){
ansarr[i] = 0;
}
for(int i = 1; i < 24; i++){
srcarr[i] = srcStr.charAt(i + 8) - '0';
destarr[i] = destStr.charAt(i + 8) - '0';
}
for(int i = 24; i < 27; i++){
srcarr[i] = 0;
destarr[i] = 0;
}
int srcexpint = Integer.parseInt(Transformer.binaryToInt("000000000000000000000000" + srcStr.substring(1, 9)));
int destexpint = Integer.parseInt(Transformer.binaryToInt("000000000000000000000000" + destStr.substring(1, 9)));
int srcsign = srcStr.charAt(0) - '0';
int destsign = destStr.charAt(0) - '0';
int anssign = srcsign ^ destsign;
if(srcexpint == 255){
if(anssign == 0){
return new DataType(IEEE754Float.P_INF);
}
else{
return new DataType(IEEE754Float.N_INF);
}
}
if(destexpint == 255){
if(anssign == 0){
return new DataType(IEEE754Float.P_INF);
}
else{
return new DataType(IEEE754Float.N_INF);
}
}
if(srcexpint == 0){
srcexpint++;
srcarr[0] = 0;
}
else{
srcarr[0] = 1;
}
if(destexpint == 0){
destexpint++;
destarr[0] = 0;
}
else{
destarr[0] = 1;
}
int exp = srcexpint + destexpint - 127;
//接下来开始原码乘法
for(int i = 27; i < 54; i++){
ansarr[i] = destarr[i - 27];
}
for(int i = 0; i < 27; i++){
if(ansarr[53] == 1){
for(int j = 0; j < 27; ++j){
ansarr[j] += srcarr[j];
}
}
for(int j = 53; j >= 1; j--){
ansarr[j] = ansarr[j - 1];
}//右移一位
ansarr[0] = 0;
for(int j = 53; j > 0; j--){
if(ansarr[j] == 2){
ansarr[j] = 0;
ansarr[j - 1]++;
}
else if(ansarr[j] == 3){
ansarr[j] = 1;
ansarr[j - 1]++;
}
}
}
exp++;//这一步是因为原码乘法的特性，最后的结果是右移了一位的
//规格化
while(ansarr[0] == 0 && exp > 0){
for(int i = 0; i < 53; ++i){
ansarr[i] = ansarr[i + 1];
}//左移
ansarr[53] = 0;
exp--;
}
int judge = 0;
for(int i = 0; i < 27; ++i){
if(ansarr[i] == 1){
judge = 1;
break;
}
}
//处理出现exp<0但是余数不为0的情况
while(judge == 1 && exp < 0){
char[] b = new char[54];
for(int i = 0; i < 54; ++i){
b[i] = (char) (ansarr[i] + '0');
}
b = rightShift(new String(b), 1).toCharArray();
for(int i = 0; i < 54; ++i){
ansarr[i] = b[i] - '0';
}
exp++;
judge = 0;
for(int i = 0; i < 27; ++i){
if(ansarr[i] == 1){
judge = 1;
break;
}
}
}
//溢出
if(exp >= 255){
if(anssign == 0){
return new DataType(IEEE754Float.P_INF);
}
else{
return new DataType(IEEE754Float.N_INF);
}
}
//像这种就是0
else if(exp < 0){
if(anssign == 0){
return new DataType(IEEE754Float.P_ZERO);
}
else{
return new DataType(IEEE754Float.N_ZERO);
}
}
//处理非规格化数
else if(exp == 0){
char[] b = new char[54];
for(int i = 0; i < 54; ++i){
b[i] = (char) (ansarr[i] + '0');
}
b = rightShift(new String(b), 1).toCharArray();
for(int i = 0; i < 54; ++i){
ansarr[i] = b[i] - '0';
}
}
char [] a = new char[54];
for(int i = 0; i < 54; ++i){
a[i] = (char) (ansarr[i] + '0');
}
return new DataType(round(anssign == 0 ? '0' : '1', Transformer.intToBinary(Integer.toString(exp)).substring(24, 32), new String(a)));
}
div
/**
* compute the float mul of (dest / src)
*/
public DataType div(DataType src,DataType dest){
//TODO
String srcStr = src.toString();
String destStr = dest.toString();
String hr = cornerCheck(divCorner, destStr, srcStr);
if(hr != null){
return new DataType(hr);
}
if (srcStr.matches(IEEE754Float.NaN_Regular) || destStr.matches(IEEE754Float.NaN_Regular)) {
return new DataType(IEEE754Float.NaN);
}
char[] srcarr = new char[27];
char[] destarr = new char[27];
char[] ansarr = new char[54];
for(int i = 0; i < 54; ++i){
ansarr[i] = '0';
}
for(int i = 1; i < 24; i++){
srcarr[i] = srcStr.charAt(i + 8);
destarr[i] = destStr.charAt(i + 8);
}
for(int i = 24; i < 27; i++){
srcarr[i] = '0';
destarr[i] = '0';
}
int srcexpint = Integer.parseInt(Transformer.binaryToInt("000000000000000000000000" + srcStr.substring(1, 9)));
int destexpint = Integer.parseInt(Transformer.binaryToInt("000000000000000000000000" + destStr.substring(1, 9)));
int srcsign = srcStr.charAt(0) - '0';
int destsign = destStr.charAt(0) - '0';
int anssign = srcsign ^ destsign;
if(srcexpint == 255){
if(anssign == 0){
return new DataType(IEEE754Float.P_ZERO);
}
else{
return new DataType(IEEE754Float.N_ZERO);
}
}
if(destexpint == 255){
if(anssign == 0){
return new DataType(IEEE754Float.P_INF);
}
else{
return new DataType(IEEE754Float.N_INF);
}
}
if(srcStr.equals(IEEE754Float.P_ZERO) || srcStr.equals(IEEE754Float.N_ZERO)){
throw new ArithmeticException();
}
if(srcexpint == 0){
srcexpint++;
srcarr[0] = '0';
}
else{
srcarr[0] = '1';
}
if(destexpint == 0){
destexpint++;
destarr[0] = '0';
}
else{
destarr[0] = '1';
}
int exp = destexpint - srcexpint + 127;//注意+127
//接下来原码除法
//填充余数寄存器
for(int i = 0; i < 27; i++){
ansarr[i] = destarr[i];
}
for(int i = 0; i < 27; i++){
int index = 0;
int k = 0;
while(k < 27 && ansarr[k] == srcarr[k]){
k++;
}
if(k == 27 || ansarr[k] >= srcarr[k]){
index = 0;//够减
}
else{
index = 1;//不够减
}
if(index == 1){
ansarr[1] = (char) (ansarr[1] + (2 * (ansarr[0] - '0')));
for(int j = 0; j < 53; ++j){
ansarr[j] = ansarr[j + 1];//左移
}
ansarr[53] = '0';
}
else{
for(int j = 0; j < 27; ++j){
ansarr[j] = (char) (ansarr[j] - srcarr[j] + '0');
}
for(int j = 26; j > 0; --j){
while(ansarr[j] < '0'){
ansarr[j] += 2;
ansarr[j - 1] = (char) (ansarr[j - 1] - 1);
}
}
ansarr[1] = (char) (ansarr[1] + (2 * (ansarr[0] - '0')));
for(int j = 0; j < 53; j++){
ansarr[j] = ansarr[j + 1];
}//左移
ansarr[53] = '1';
}
}
for(int i = 0; i < 27; ++i){
ansarr[i] = ansarr[i + 27];
}//把商放到前27位
while(ansarr[0] == '0' && exp > 0){
for(int i = 0; i < 26; ++i){
ansarr[i] = ansarr[i + 1];
}
ansarr[26] = '0';
exp--;
}
int judge = 0;
for(int i = 0; i < 27; ++i){
if(ansarr[i] == '1'){
judge = 1;
break;
}
}
while(judge == 1 && exp < 0){
char[] b = new char[27];
for(int i = 0; i < 27; ++i){
b[i] = ansarr[i];
}
b = rightShift(new String(b), 1).toCharArray();
for(int i = 0; i < 27; ++i){
ansarr[i] = b[i];
}
exp++;
judge = 0;
for(int i = 0; i < 27; ++i){
if(ansarr[i] == '1'){
judge = 1;
break;
}
}
}
if(exp >= 255){
if(anssign == 0){
return new DataType(IEEE754Float.P_INF);
}
else{
return new DataType(IEEE754Float.N_INF);
}
}
else if(exp < 0){
if(anssign == 0){
return new DataType(IEEE754Float.P_ZERO);
}
else{
return new DataType(IEEE754Float.N_ZERO);
}
}
else if(exp == 0){
char[] b = new char[27];
for(int i = 0; i < 27; ++i){
b[i] = ansarr[i];
}
b = rightShift(new String(b), 1).toCharArray();
for(int i = 0; i < 27; ++i){
ansarr[i] = b[i];
}
}
return new DataType(round(anssign == 0 ? '0' : '1', Transformer.intToBinary(Integer.toString(exp)).substring(24, 32), new String(ansarr).substring(0, 27)));
}
Cache
pAddr = tag + setNO + offset
blockNO = tag + setNO
- 基本工作机制：
- Check：当处理器试图从主存访问数据时，先检查该数据是否在Cache中
- 若命中，数据直接从Cache传输至CPU
- 若没有命中，CPU访问主存，将一块数据传输至Cache中，然后再从Cache传输到CPU。
- 如何判断命中：
- 冯诺依曼的设计：每个内存都可以被一个地址访问。
- Cache用标签(tags)去判断需要访问的数据在主存中的地址。
fetch
用getBlockNo方法将Paddr转换成块号(主存被分成一个一个块),然后用块号映射找到对应的cache的行号,接下来两种情况
(1)hit 那就说明这个数据就在cache里面,调用hit之后返回行号即可
(2)没有hit说明此刻cache里没有这个东西,我们需要根据不同的映射策略去将这个数据存储进cache
-
直接映射 Direct Mapping
- 每个块只有一个映射行。
- 设j为主存中的块数，C为Cache中的行数，则主存中每块对应在Cache中的行数
-
行数 i = j mod C（Cache中每行存一块）
- 优点：简单，匹配快，查找快
- 缺点：抖动
- 适用于大容量的Cache
-
关联映射 Associative Mapping
-
任何块可能被存在任何行。
-
优点：防止抖动。
-
缺点：复杂而且浪费资源。
-
适用于小容量的Cache
-
-
组关联映射 Set Associative Mapping
-
Cache被分为固定的组，每个块可以被存在指定的组里的任何一行。
-
组号s = j mod S
-
K路组：k=C/S,每组的行数
-
权衡任何容量的Cache
直接映射不需要替换策略
tag这个是17位 + 组号组成
// 标记，占位长度为26位，有效长度取决于映射策略： // 直接映射: 17 位 // 全关联映射: 26 位 // (2^n)-路组关联映射: 26-(9-n) 位 // 注意，tag在物理地址中用高位表示，如：直接映射(32位)=tag(17位)+行号(9位)+块内地址(6位)， // 那么对于值为0b1111的tag应该表示为00000000000000000000001111，其中低17位为有效长度 -
private int fetch(String pAddr) {
int blockNO = getBlockNO(pAddr);
int rowNO = map(blockNO);
if (rowNO == - 1) {
int setNO = blockNO % SETS;
char[] addrTag = calTag(blockNO);
if (SETS == CACHE_SIZE_B / LINE_SIZE_B) {
cacheInstance.update(setNO, addrTag, Memory.getMemory().read(Transformer.intToBinary(String.valueOf(LINE_SIZE_B * blockNO)), LINE_SIZE_B));
rowNO = setNO;
} else
rowNO = replacementStrategy.replace(setNO * setSize, (setNO + 1) * setSize, addrTag, Memory.getMemory().read(Transformer.intToBinary(String.valueOf(LINE_SIZE_B * blockNO)), LINE_SIZE_B));
}
return rowNO;
}
public char[] calTag(int blockNO) {
int tag = blockNO / SETS;//相当于右移了n位，那n位是因为组数多了，每组行数就多了，需要的位就少了
int offset = 0;
for (int i = 1; i < SETS; i *= 2)
offset++;
StringBuilder tmp = new StringBuilder(Transformer.intToBinary(String.valueOf(tag)).substring(6 + offset, 32));
for (int i = 0; i < offset; i++)
tmp.insert(0, "0");
return tmp.toString().toCharArray();
}
map
/**
* 根据目标数据内存地址前26位的int表示，进行映射
*
* @param blockNO 数据在内存中的块号
* @return 返回cache中所对应的行，-1表示未命中
*/
private int map(int blockNO) {
int setNO = blockNO % SETS;
char[] tag = calTag(blockNO);
for (int i = setNO * setSize; i < (setNO + 1) * setSize; i++) {
if (cache[i] != null && cache[i].validBit && Arrays.equals(tag, cache[i].getTag())) {
replacementStrategy.hit(i);
return i;
}
}
return - 1;
}
cacheReplacementStrategy
interface
package memory.cache.cacheReplacementStrategy;
public interface ReplacementStrategy {
/**
* 结合具体的替换策略，进行命中后进行相关操作
* @param rowNO 行号
*/
void hit(int rowNO);
/**
* 结合具体的映射策略，在给定范围内对cache中的数据进行替换
* @param start 起始行
* @param end 结束行 开区间
* @param addrTag tag
* @param input 数据
*/
int replace(int start, int end, char[] addrTag, byte[] input);
}
update
注意脏位和update无关,而是在write方法中
public void update(int rowNO, char[] tag, byte[] input) {
cache[rowNO].update(tag, input);
}//cache类
void update(char[] tag, byte[] data) {
validBit = true;
visited = 1;
timeStamp = System.currentTimeMillis();
this.tag = tag;
this.data = data;
}//cache的私有类cacheline类中
calPaddr
由行号转换到Paddr
32位物理地址(26位块号 + 6位块内地址)
rowNo / setSize = setNo
public String calPAddr(int rowNO) {
int offset = 0;
for (int i = 1; i < SETS; i *= 2) {
offset++;
}
String setNo = Transformer.intToBinary("" + rowNO / setSize).substring(32 - offset, 32);
char[] tag = cache[rowNO].tag;
return new String(tag).substring(offset, tag.length) + setNo + "000000";
}
FIFO
先进先出
package memory.cache.cacheReplacementStrategy;
import memory.Memory;
import memory.cache.Cache;
public class FIFOReplacement implements ReplacementStrategy {
@Override
public void hit(int rowNO) {
}
@Override
public int replace(int start, int end, char[] addrTag, byte[] input) {
long minTime = Long.MAX_VALUE;
int minIndex = - 1;
for (int i = start; i < end; i++) {
minIndex = Cache.getCache().getTimeStamp(i) < minTime ? i : minIndex;
minTime = Math.min(Cache.getCache().getTimeStamp(i), minTime);
}
if (Cache.isWriteBack && Cache.getCache().isDirty(minIndex) && Cache.getCache().isValid(minIndex)) {
Memory.getMemory().write(Cache.getCache().calPAddr(minIndex), Cache.LINE_SIZE_B, Cache.getCache().getData(minIndex));
}
Cache.getCache().update(minIndex, addrTag, input);
return minIndex;
}
}
public long getTimeStamp(int rowNO) {
CacheLine cacheLine = cache[rowNO];
if (cacheLine.validBit) {
return cacheLine.timeStamp;
}
return - 1;
}//Cache类里的
LFUR
最不经常使用
package memory.cache.cacheReplacementStrategy;
import memory.cache.Cache;
public class LFUReplacement implements ReplacementStrategy {
@Override
public void hit(int rowNO) {
Cache.getCache().addVisited(rowNO);
}
@Override
public int replace(int start, int end, char[] addrTag, byte[] input) {
int minVisited = Integer.MAX_VALUE;
int minIndex = - 1;
for (int i = start; i < end; i++) {
minIndex = Cache.getCache().getVisited(i) < minVisited ? i : minIndex;
minVisited = Math.min(Cache.getCache().getVisited(i), minVisited);
}
if (Cache.isWriteBack && Cache.getCache().isDirty(minIndex) && Cache.getCache().isValid(minIndex)) {
Memory.getMemory().write(Cache.getCache().calPAddr(minIndex), Cache.LINE_SIZE_B, Cache.getCache().getData(minIndex));
}
Cache.getCache().update(minIndex, addrTag, input);
return minIndex;
}
}
public int getVisited(int rowNO) {
CacheLine cacheLine = cache[rowNO];
if (cacheLine.validBit) {
return cacheLine.visited;
}
return - 1;
}//cache类
public void addVisited(int rowNO) {
CacheLine cacheLine = cache[rowNO];
cacheLine.visited = cacheLine.visited + 1;
}//cache类
LRUR
最近最少使用算法
package memory.cache.cacheReplacementStrategy;
import memory.cache.Cache;
public class LRUReplacement implements ReplacementStrategy {
@Override
public void hit(int rowNO) {
Cache.getCache().setTimeStamp(rowNO);
}
@Override
public int replace(int start, int end, char[] addrTag, byte[] input) {
long minTime = Long.MAX_VALUE;
int minIndex = - 1;
for (int i = start; i < end; i++) {
minIndex = Cache.getCache().getTimeStamp(i) < minTime ? i : minIndex;
minTime = Math.min(Cache.getCache().getTimeStamp(i), minTime);
}
if (Cache.isWriteBack && Cache.getCache().isDirty(minIndex) && Cache.getCache().isValid(minIndex)) {
Memory.getMemory().write(Cache.getCache().calPAddr(minIndex), Cache.LINE_SIZE_B, Cache.getCache().getData(minIndex));
}
Cache.getCache().update(minIndex, addrTag, input);
return minIndex;
}
}
MMU
添加Cache和TLB到MMU
/**
* 读取数据
*
* @param logicAddr 48-bits逻辑地址
* @param length 读取数据的长度
* @return 内存中的数据
*/
public byte[] read(String logicAddr, int length) {
String physicalAddr = addressTranslation(logicAddr, length);
// TODO: add cache here
if (Cache.isAvailable) {
return cache.read(physicalAddr, length);
}
return memory.read(physicalAddr, length);
}
/**
* 写数据
*
* @param logicAddr 48-bits逻辑地址
* @param length 读取数据的长度
*/
public void write(String logicAddr, int length, byte[] data) {
String physicalAddr = addressTranslation(logicAddr, length);
// TODO: add cache here
if (Cache.isAvailable) {
cache.write(physicalAddr, length, data);
}
else {
memory.write(physicalAddr, length, data);
}
}
/**
* 地址转换
*
* @param logicAddr 48-bits逻辑地址
* @param length 读取数据的长度
* @return 32-bits物理地址
*/
private String addressTranslation(String logicAddr, int length) {
String linearAddr; // 32位线性地址
String physicalAddr; // 32位物理地址
if (!Memory.SEGMENT) {
// 实模式：线性地址等于物理地址
linearAddr = toRealLinearAddr(logicAddr);
memory.real_load(linearAddr, length); // 从磁盘中加载到内存
physicalAddr = linearAddr;
} else {
// 分段模式
int segIndex = getSegIndex(logicAddr);
if (!memory.isValidSegDes(segIndex)) {
// 缺段中断，该段不在内存中，内存从磁盘加载该段索引的数据
memory.seg_load(segIndex);
}
linearAddr = toSegLinearAddr(logicAddr);
// 权限检查
int start = Integer.parseInt(Transformer.binaryToInt(linearAddr));
int base = chars2int(memory.getBaseOfSegDes(segIndex));
long limit = chars2int(memory.getLimitOfSegDes(segIndex));
if (memory.isGranularitySegDes(segIndex)) {
limit = (limit + 1) * Memory.PAGE_SIZE_B - 1;
}
if ((start < base) || (start + length > base + limit)) {
throw new SecurityException("Segmentation Fault");
}
if (!Memory.PAGE) {
// 分段模式：线性地址等于物理地址
physicalAddr = linearAddr;
} else {
// 段页式
int startvPageNo = Integer.parseInt(Transformer.binaryToInt(linearAddr.substring(0, 20))); // 高20位表示虚拟页号
int offset = Integer.parseInt(Transformer.binaryToInt(linearAddr.substring(20, 32))); // 低12位的页内偏移
int pages = (length - offset + Memory.PAGE_SIZE_B - 1) / Memory.PAGE_SIZE_B;
if (offset > 0) pages++;
int endvPageNo = startvPageNo + pages - 1;
for (int i = startvPageNo; i <= endvPageNo; i++) {
// TODO: add tlb here
if (TLB.isAvailable) {
if (!tlb.isValidPage(i)) {
if (!memory.isValidPage(i)) {
// 缺页中断，该页不在内存中，内存从磁盘加载该页的数据
memory.page_load(i);
}
tlb.write(i);
}
}
else {
if (!memory.isValidPage(i)) {
// 缺页中断，该页不在内存中，内存从磁盘加载该页的数据
memory.page_load(i);
}
}
}
physicalAddr = toPagePhysicalAddr(linearAddr);
}
}
return physicalAddr;
}
三个地址转换方法
/**
* 实模式下的逻辑地址转线性地址
*
* @param logicAddr 48位 = 16位段寄存器 + 32位offset，计算公式为：①(16-bits段寄存器左移4位 + offset的低16-bits) = 20-bits物理地址 ②高位补0到32-bits
* @return 32-bits实模式线性地址
*/
public String toRealLinearAddr(String logicAddr) {
// TODO
String segmentReg = logicAddr.substring(0, 16) + "0000";
int pysAddr = Integer.parseInt(Transformer.binaryToInt(segmentReg)) + Integer.parseInt(Transformer.binaryToInt(logicAddr.substring(32)));
return "000000000000" + Transformer.intToBinary(String.valueOf(pysAddr)).substring(12);
}
/**
* 分段模式下的逻辑地址转线性地址
*
* @param logicAddr 48位 = 16位段选择符(高13位index选择段表项) + 32位段内偏移
* @return 32-bits 线性地址
*/
public String toSegLinearAddr(String logicAddr) {
// TODO
int segIndex = getSegIndex(logicAddr);
String baseAddr = String.valueOf(Memory.getMemory().getBaseOfSegDes(segIndex));
int linearAddr = Integer.parseInt(Transformer.binaryToInt(baseAddr)) + Integer.parseInt(Transformer.binaryToInt(logicAddr.substring(16)));
return Transformer.intToBinary(String.valueOf(linearAddr));
}
/**
* 段页式下的线性地址转物理地址
*
* @param linearAddr 32位
* @return 32-bits 物理地址
*/
public String toPagePhysicalAddr(String linearAddr) {
// TODO
String vPageNo = linearAddr.substring(0, 20);
String offset = linearAddr.substring(20);
String phyPageNo;
// TODO: add tlb here
if (TLB.isAvailable) {
phyPageNo = String.valueOf(tlb.getFrameOfPage(Integer.parseInt(Transformer.binaryToInt(vPageNo))));
}
else {
phyPageNo = String.valueOf(memory.getFrameOfPage(Integer.parseInt(Transformer.binaryToInt(vPageNo))));
}
return phyPageNo + offset;
}
Write
分为write through 和 write back
public void write(String pAddr, int len, byte[] data) {
int addr = Integer.parseInt(Transformer.binaryToInt("0" + pAddr));
int upperBound = addr + len;
int index = 0;
while (addr < upperBound) {
int nextSegLen = LINE_SIZE_B - (addr % LINE_SIZE_B);
if (addr + nextSegLen >= upperBound) {
nextSegLen = upperBound - addr;
}
int rowNO = fetch(Transformer.intToBinary(String.valueOf(addr)));
byte[] cache_data = cache[rowNO].getData();
int i = 0;
while (i < nextSegLen) {
cache_data[addr % LINE_SIZE_B + i] = data[index];
index++;
i++;
}
if (isWriteBack)
cache[rowNO].dirty = true;
else {
Memory.getMemory().write(calPAddr(rowNO), LINE_SIZE_B, cache_data);
cache[rowNO].validBit = true;//Memory的write方法会让validBit = false
}
addr += nextSegLen;
}
}
Memory.disk
模拟磁盘
Disk
在Disk类中，实现磁头寻道相关的两个方法。
/**
* 磁头，记录了自己当前所在位置
*/
private static class DiskHead {
int track = 0; // 当前所在磁道号
int sector = 0; // 当前所在扇区号
int point = 0; // 当前所在扇区内部的字节号
/**
* 将磁头移动到目标位置
*
* @param start 数据起始点
*/
public void seek(int start) {
//TODO
track = start / BYTE_PER_SECTOR / SECTOR_PER_TRACK % TRACK_NUM;
sector = start / BYTE_PER_SECTOR % SECTOR_PER_TRACK;
point = start % BYTE_PER_SECTOR;
}
/**
* 磁头移动一个字节
*/
public void addPoint() {
//TODO
point++;
if (point == BYTE_PER_SECTOR) {
point = 0;
sector++;
}
if (sector == SECTOR_PER_TRACK) {
sector = 0;
track++;
}
if(track == TRACK_NUM) {
track = 0;
}//代表换了一个磁头
}
}//Disk的私有类
Scheduler
在Scheduler类中，实现六个磁盘调度算法：先来先服务算法、最短寻道时间优先算法、扫描算法、循环扫描算法、LOOK算法和C-LOOK算法，并计算平均寻道长度。
FCFS
First Come First Service
/**
* 先来先服务算法
*
* @param start 磁头初始位置
* @param request 请求访问的磁道号
* @return 平均寻道长度
*/
public double FCFS(int start, int[] request) {
//TODO
double ans = 0.0;
for(int i = 0;i < request.length;i++) {
ans += Math.abs(request[i] - start);
start = request[i];
}
return ans / request.length;
}
SSTF
/**
* 最短寻道时间优先算法
*
* @param start 磁头初始位置
* @param request 请求访问的磁道号
* @return 平均寻道长度
*/
public double SSTF(int start, int[] request) {
//TODO
boolean []visited = new boolean[request.length];
double ans = 0.0;
for(int i = 0; i < request.length; i++){
visited[i] = false;
}
for(int i = 0; i < request.length; i++){
int min = Integer.MAX_VALUE;
int index = -1;
for(int j = 0; j < request.length; j++){
if(!visited[j] && Math.abs(request[j] - start) < min){
min = Math.abs(request[j] - start);
index = j;
}
}
ans += min;
start = request[index];
visited[index] = true;
}
return ans / request.length;
}
Scan
/**
* 扫描算法
*
* @param start 磁头初始位置
* @param request 请求访问的磁道号
* @param direction 磁头初始移动方向，true表示磁道号增大的方向，false表示磁道号减小的方向
* @return 平均寻道长度
*/
public double SCAN(int start, int[] request, boolean direction) {
//TODO
Arrays.sort(request);
double ans = 0.0;
if (direction) {
if (start <= request[0]) {
ans = request[request.length - 1] - start;
}
else {
ans = 2 * Disk.TRACK_NUM - 2 - start - request[0];
}
}
else {
if (start >= request[request.length - 1]) {
ans = start - request[0];
}
else {
ans = start + request[request.length - 1];
}
}
return ans / request.length;
}
C-SCAN
/**
* C-SCAN算法：默认磁头向磁道号增大方向移动
*
* @param start 磁头初始位置
* @param request 请求访问的磁道号
* @return 平均寻道长度
*/
public double CSCAN(int start,int[] request){
//TODO
double ans = 0.0;
Arrays.sort(request);
int index = -1;
for(int i = 0; i < request.length; i++){
if(request[i] >= start){
index = i;
break;
}
}
if(index == 0){
ans = request[request.length - 1] - start;
}
else if(index == -1){
ans = 2 * Disk.TRACK_NUM - 2 - start + request[request.length - 1];
}
else{
ans = 2 * Disk.TRACK_NUM - 2 - start + request[index - 1];
}
return ans / request.length;
}
LOOK
/**
* LOOK算法
*
* @param start 磁头初始位置
* @param request 请求访问的磁道号
* @param direction 磁头初始移动方向，true表示磁道号增大的方向，false表示磁道号减小的方向
* @return 平均寻道长度
*/
public double LOOK(int start,int[] request,boolean direction){
//TODO
double ans = 0.0;
Arrays.sort(request);
if(direction){
if(start <= request[0]){
ans = request[request.length - 1] - start;
}
else if(start >= request[request.length - 1]){
ans = start - request[0];
}
else{
ans = request[request.length - 1] - start + request[request.length - 1] - request[0];
}
}
else{
if(start >= request[request.length - 1]){
ans = start - request[0];
}
else if(start <= request[0]){
ans = request[request.length - 1] - start;
}
else{
ans = start - request[0] + request[request.length - 1] - request[0];
}
}
return ans / request.length;
}
C-LOOK
/**
* C-LOOK算法：默认磁头向磁道号增大方向移动
*
* @param start 磁头初始位置
* @param request 请求访问的磁道号
* @return 平均寻道长度
*/
public double CLOOK(int start,int[] request){
//TODO
double ans = 0.0;
Arrays.sort(request);
int index = -1;
for(int i = 0; i < request.length; i++){
if(request[i] >= start){
index = i;
break;
}
}
if(index == 0){
ans = request[request.length - 1] - start;
}
else if(index == -1){
ans = 2 * Disk.TRACK_NUM - 2 - start + request[0];
}
else{
ans = request[request.length - 1] - start + request[request.length - 1] - request[0] + request[index - 1] - request[0];
}
return ans / request.length;
}
Memory MMU
分别实现实模式、分段式、段页式三种内存的地址转换与数据加载功能。
地址转换-MMU类
toRealLinearAddr
/**
* 实模式下的逻辑地址转线性地址
*
* @param logicAddr 48位 = 16位段寄存器 + 32位offset，计算公式为：①(16-bits段寄存器左移4位 + offset的低16-bits) = 20-bits物理地址 ②高位补0到32-bits
* @return 32-bits实模式线性地址
*/
private String toRealLinearAddr(String logicAddr) {
// TODO
String a = logicAddr.substring(0, 16) + "0000";
String b = logicAddr.substring(32, 48);
int paddr = Integer.parseInt(Transformer.binaryToInt(a)) + Integer.parseInt(Transformer.binaryToInt(b));
return "000000000000"+ Transformer.intToBinary(String.valueOf(paddr)).substring(12, 32);
}
toSegLinearAddr
/**
* 分段模式下的逻辑地址转线性地址
*
* @param logicAddr 48位 = 16位段选择符(高13位index选择段表项) + 32位段内偏移
* @return 32-bits 线性地址
*/
private String toSegLinearAddr(String logicAddr) {
// TODO
int index = getSegIndex(logicAddr);
String baseAddr = String.valueOf(Memory.getMemory().getBaseOfSegDes(index));
String offset = logicAddr.substring(16, 48);
int LinearAddr = Integer.parseInt(Transformer.binaryToInt(baseAddr)) + Integer.parseInt(Transformer.binaryToInt(offset));
return Transformer.intToBinary(String.valueOf(LinearAddr));
}
/**
* 根据逻辑地址找到对应的段索引
*
* @param logicAddr 逻辑地址
* @return 整数表示的段索引
*/
private int getSegIndex(String logicAddr) {
String indexStr = logicAddr.substring(0, 13);
return Integer.parseInt(Transformer.binaryToInt(indexStr)); // 段描述符索引
}
public char[] getBaseOfSegDes(int index) {
return getSegDescriptor(index).base;
}//memory类
toPagePhysicalAddr
IA-32采用段页式虚拟存储管理方式，通过分段方式完成逻辑地址到线性地址的转换后，再进一步通过分页方式将线性地址转换为物理地址.
/**
* 段页式下的线性地址转物理地址
*
* @param linearAddr 32位
* @return 32-bits 物理地址
*/
private String toPagePhysicalAddr(String linearAddr) {
// TODO
String vpNO = linearAddr.substring(0, 20);//20位虚拟页号 addresstranslation方法里有
String offset = linearAddr.substring(20, 32);//12位偏移量
String pvNO;
// TODO: add tlb here
if(TLB.isAvailable){
pvNO = String.valueOf(tlb.getFrameOfPage(Integer.parseInt(Transformer.binaryToInt(vpNO))));
}
else{
pvNO = String.valueOf(memory.getFrameOfPage(Integer.parseInt(Transformer.binaryToInt(vpNO))));
}
return pvNO + offset;
}
/**
* 根据虚页页号返回该页的物理页框号
* 注意，调用此方法前应该保证该虚页已经加载进入TLB
*
* @param vPageNo 虚拟页号
* @return 20-bits
*/
public char[] getFrameOfPage(int vPageNo) {
for (int i = 0; i < TLB_SIZE; i++) {
if (vPageNo == getTLBLine(i).vPageNo && getTLBLine(i).valid) {
return getTLBLine(i).pageFrame;
}
}
return null;
}//TLB类
/**
* 根据虚页页号返回该页的物理页框号
*
* @param vPageNo 虚拟页号
* @return 20-bits
*/
public char[] getFrameOfPage(int vPageNo) {
if (timer) {
try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
return getPageItem(vPageNo).pageFrame;
}//Memory类
数据加载(Memory类)
在Memory类中,实现三个数据加载方法.数据加载，就是从磁盘中加载相应的数据进入内存。
real-load
内存地址对应磁盘地址
/**
* 实模式下从磁盘中加载数据
*
* @param pAddr 实模式下，内存地址对应磁盘地址
* @param len 数据段长度
*/
public void real_load(String pAddr, int len) {
// TODO
byte[] data = new byte[len];
data = disk.read(pAddr, len);
write(pAddr, len, data);//Memory类的用于向内存写入数据的方法
}
seg_load
seg_load方法需要干两件事情：
- 从磁盘上加载该段的数据到内存。如何从磁盘上读取一整段呢？你应该使用段基址作为访问磁盘的地址，用段限长（即段大小）作为读取的长度。至于段基址和段限长是多少，参考我们3.2.3的规定。那么加载过来之后写到内存的哪里呢？由于分段式下每个段大小只有1MB，不会超出内存大小，所以我们默认把数据放在物理地址为 0 的地方。
- 除了加载数据，你还需要填好全局描述符表GDT，需要填入的内容还是按照3.2.3的规定进行填写。下面为该规定的原文。
我们规定，除了测试需要，每个由MMU装载进入GDT的段，其段基址均为全 0 ，其限长均为全 1 ，未开启分页时粒度为false，开启分页后粒度为true。
/**
* 段式存储模式下，从磁盘中加载数据.段页式存储中，不用从磁盘中加载数据
*
* @param segIndex 段索引
*/
public void seg_load(int segIndex) {
// TODO
Arrays.fill(getSegDescriptor(segIndex).base, '0');
Arrays.fill(getSegDescriptor(segIndex).limit, '1');
getSegDescriptor(segIndex).validBit = true;
getSegDescriptor(segIndex).granularity = PAGE;
if (!PAGE) {
int len = Integer.parseInt(Transformer.binaryToInt(String.valueOf(getLimitOfSegDes(segIndex))));
if (isGranularitySegDes(segIndex)) { // 粒度，为true表示段以页（4KB）为基本单位，为false表示段以字节为基本单位
len *= 4 * 1024;
}
byte[] data = disk.read("0", len);//说了数据存储在物理地址为0的地方
write("0", len, data);
}
//如果分页,则数据加载交给page_load方法,seg_load跳过这个
}
page_load
page_load方法也是需要干两件事情：
- 从磁盘上加载该页数据到内存。如何在磁盘上读取该页数据呢？你应该使用该虚页的起始地址作为作为访问磁盘的地址，用页大小作为读取的长度。至于该虚页的起始地址是多少，可以直接根据虚页号得到。那么加载过来之后写到内存的哪里呢？这就需要你找出一个空闲的物理页框然后放下去啦。
-
除了加载数据，你还需要填好页表，如果你使用有效位数组的话还需要填好有效位数组。
- 在段页式存储管理下，从磁盘加载数据应该是以页为单位的，不再是以段为单位。因为开启分页之后，一个段应该是4GB（怎么算出来？），加载这么多数据内存可吃不消。因此开启分页之后，seg_load应该跳过加载数据这一步，它的作用在开启分页之后仅仅是填写GDT，加载数据的任务应该交给page_load来完成
/**
* 段页式存储下，从磁盘中加载数据
* 不考虑16MB内存用满的情况
*
* @param vPageNo 虚拟页号
*/
public void page_load(int vPageNo) {
// TODO
String pAddr = Transformer.intToBinary(String.valueOf(vPageNo)).substring(12, 32) + "000000000000";
byte[] data = disk.read(pAddr, PAGE_SIZE_B);
int frameNO;
for(frameNO = 0; frameNO < pageValid.length; frameNO++){
if(!pageValid[frameNO]){
break;
}
}//这个frame指的内存中用于存放页的单元 这里是在找有没有空闲的frame
pageValid[frameNO] = true;//现在我拿来用了
getPageItem(vPageNo).pageFrame = Transformer.intToBinary(String.valueOf(frameNO)).substring(12, 32).toCharArray();//20位物理页框号
getPageItem(vPageNo).isInMem = true;//我已经装入了
String phyAddr = Transformer.intToBinary(String.valueOf(frameNO)).substring(12, 32) + "000000000000";//和上面那个对应
write(phyAddr, PAGE_SIZE_B, data);
}
融合Cache和TLB
将cache与TLB融合到MMU中.
/**
* 读取数据
*
* @param logicAddr 48-bits逻辑地址
* @param length 读取数据的长度
* @return 内存中的数据
*/
public byte[] read(String logicAddr, int length) {
String physicalAddr = addressTranslation(logicAddr, length);
// TODO: add cache here
if (Cache.isAvailable) {
return cache.read(physicalAddr, length);
}
return memory.read(physicalAddr, length);
}
/**
* 写数据
*
* @param logicAddr 48-bits逻辑地址
* @param length 读取数据的长度
*/
public void write(String logicAddr, int length, byte[] data) {
String physicalAddr = addressTranslation(logicAddr, length);
// TODO: add cache here
if (Cache.isAvailable) {
cache.write(physicalAddr, length, data);
}
memory.write(physicalAddr, length, data);
}
/**
* 地址转换
*
* @param logicAddr 48-bits逻辑地址
* @param length 读取数据的长度
* @return 32-bits物理地址
*/
private String addressTranslation(String logicAddr, int length) {
String linearAddr; // 32位线性地址
String physicalAddr; // 32位物理地址
if (!Memory.SEGMENT) {
// 实模式：线性地址等于物理地址
linearAddr = toRealLinearAddr(logicAddr);
memory.real_load(linearAddr, length); // 从磁盘中加载到内存
physicalAddr = linearAddr;
} else {
// 分段模式
int segIndex = getSegIndex(logicAddr);
if (!memory.isValidSegDes(segIndex)) {
// 缺段中断，该段不在内存中，内存从磁盘加载该段索引的数据
memory.seg_load(segIndex);
}
linearAddr = toSegLinearAddr(logicAddr);
// 权限检查
int start = Integer.parseInt(Transformer.binaryToInt(linearAddr));
int base = chars2int(memory.getBaseOfSegDes(segIndex));
long limit = chars2int(memory.getLimitOfSegDes(segIndex));
if (memory.isGranularitySegDes(segIndex)) {
limit = (limit + 1) * Memory.PAGE_SIZE_B - 1;
}
if ((start < base) || (start + length > base + limit)) {
throw new SecurityException("Segmentation Fault");
}
if (!Memory.PAGE) {
// 分段模式：线性地址等于物理地址
physicalAddr = linearAddr;
} else {
// 段页式
int startvPageNo = Integer.parseInt(Transformer.binaryToInt(linearAddr.substring(0, 20))); // 高20位表示虚拟页号
int offset = Integer.parseInt(Transformer.binaryToInt(linearAddr.substring(20, 32))); // 低12位的页内偏移
int pages = (length - offset + Memory.PAGE_SIZE_B - 1) / Memory.PAGE_SIZE_B;
if (offset > 0) pages++;
int endvPageNo = startvPageNo + pages - 1;
for (int i = startvPageNo; i <= endvPageNo; i++) {
// TODO: add tlb here
if (TLB.isAvailable) {
if (!tlb.isValidPage(i)) {
if (!memory.isValidPage(i)) {
memory.page_load(i);
}
tlb.write(i);
}
}
else {
if (!memory.isValidPage(i)) {
memory.page_load(i);
}
}
}
physicalAddr = toPagePhysicalAddr(linearAddr);
}
}
return physicalAddr;
}
Controller
本次实验我们要求完成cpu中的控制器部分，模拟每个时钟周期取指、间址、执行、中断四种操作。我们使用RISC-V指令来完成本次实验。 本次实验仅涉及到add,addi,lw,lui,jalr,ecall几种指令，在以下实验指导中均会给出具体格式。
kick
在每个时钟周期内根据ICC的状态进行对应操作
本次实验我们使用一个tick函数来模拟每个时钟周期。在每个时钟周期中，我们需要完成三件事：
- 判断ICC中内容，得到当前处于哪个时钟周期
- 执行对应周期的指令微操作序列
- 根据指令执行情况判断ICC的下一个状态
ICC是一个2位的寄存器，请参考课堂讲解内容完成对应状态的判断。
在判断ICC下一个状态时请注意，我们在框架代码中提供了一个中断控制器，其中包含了表示中断是否发生的标志，请参考代码中InterruptController部分。 是否进入间址周期的判断请阅读2.2.3节间址周期的实现。（你可以在完成间址周期的处理和中断的处理后再回到时钟周期的实现）
public void tick(){
// TODO
if(new String(ICC).equals("00")){
getInstruct();
if(new String(Arrays.copyOfRange(IR,0,7)).equals("1101110")){
ICC[0] = '0';
ICC[1] = '1';
}
else{
ICC[0] = '1';
ICC[1] = '0';
}
}
else if(new String(ICC).equals("01")){
findOperand();
ICC[0] = '1';
ICC[1] = '0';
}
else if(new String(ICC).equals("10")){
operate();
if(interruptController.signal){
ICC[0] = '1';
ICC[1] = '1';
}
else{
ICC[0] = '0';
ICC[1] = '0';
}
}
else if(new String(ICC).equals("11")){
interrupt();
ICC[0] = '0';
ICC[1] = '0';
}
}
取指
在取指过程中，我们要进行以下操作：
- 将PC中的内容加载到MAR（PC中的内容会被初始化为全0，即我们默认程序开始位置为主存开始位置，此处我们忽略了系统程序，请阅读测试用例对整个流程进行理解）
- 根据MAR中保存的地址，读取memory中对应内容到MBR（请注意memory中读出的数据是byte数组类型，而寄存器类型是char数组）
- 增加PC到下一条指令的位置（此时PC应该加上多少？为什么？考虑指令的长度）
- 将MBR中的内容装载到IR中
private void getInstruct(){
// TODO
MAR = Arrays.copyOf(PC,32);
MBR = getFromMemory(String.valueOf(MAR));
PC = alu.add(new DataType(String.valueOf(PC)), new DataType("00000000000000000000000000000100")).toString().toCharArray();//PC = PC + 4
IR = Arrays.copyOf(MBR,32);
}
public char[] getFromMemory(String pAddr){
byte[] tmp = Memory.getMemory().read(pAddr,4);
char[] data = new char[32];
for(int i = 0;i < tmp.length;i++){
for (int j = 0;j < 8;j++){
data[i*8+j] = (char)(((tmp[i] & (int)Math.pow(2,7-j)) > 0 ? 1:0)+'0');
}
}
return data;
}
间址
由于risc-v并不具备间址类型的指令，因此我们额外规定一种间址指令addc。我们规定addc指令格式和add相同，根据reference-card我们可以得到正常的R类型add指令opcode为1100110， 此处规定addc的opcode为1101110.只有寄存器rs2中保存的是操作数的地址。所以如何判断是否需要进入间址周期的方式就交给聪明的你了！
在间址过程中，我们规定了以下操作：
- 将rs2中的内容加载到MAR中
- 根据MAR中的地址读出内存中对应数据存回rs2中
在完成间址周期后，我们就可以和正常的add指令一样进入执行周期了.
/** 执行间址操作 */
private void findOperand(){
// TODO
//将rs2中的内容加载到MAR中
//根据MAR中的地址读出内存中对应数据存回rs2中
MAR = Arrays.copyOf(GPR[getRegister(new String(IR).substring(20, 25).toCharArray())],32);
MBR = getFromMemory(String.valueOf(MAR));
GPR[getRegister(new String(IR).substring(20, 25).toCharArray())] = Arrays.copyOf(MBR,32);
}
private int getRegister(char[] rs){
return Integer.valueOf(String.valueOf(rs),2);
}
执行
执行周期需要根据不同的opcode进行不同的操作。此处add指令可以调用ALU中已经实现好的加法进行。请将对应结果存到相应的位置中， 在测试中，我们将对寄存器和主存进行检查。本次实验我们不设置隐藏用例，请同学们认真阅读测试用例中的memory部分进行debug工作。
有两个指令在执行阶段需要我们特殊关注：
- jalr: 保存并跳转指令。在改变PC之前，我们要先将返回的位置保存到ra寄存器中，我们规定GPR的第1个寄存器是返回地址寄存器（第0个GPR寄存器保存0）
- ecall: 系统调用中断指令。同样要保存返回位置，同时要设置中断控制器。
请注意，寄存器和立即数的下标在指令中为了方便处理采用大端存储的方式，即从低到高直接截取转化为十进制即可。不明白的同学请参考测试用例.
他这个匹配的顺序就是按照card上面的index标号由大到小
/** 执行周期 */
private void operate(){
// TODO
char[] opcode = Arrays.copyOfRange(IR,0,7);
if(new String(opcode).equals("1100110")){
char[] funct3 = Arrays.copyOfRange(IR,12,15);
char[] funct7 = Arrays.copyOfRange(IR,25,32);
char[] rs1 = Arrays.copyOfRange(IR,15,20);
char[] rs2 = Arrays.copyOfRange(IR,20,25);
char[] rd = Arrays.copyOfRange(IR,7,12);
//add
GPR[getRegister(rd)] = alu.add(new DataType(String.valueOf(GPR[getRegister(rs1)])),new DataType(String.valueOf(GPR[getRegister(rs2)]))).toString().toCharArray();
}
else if(new String(opcode).equals("1100100")){
char[] imm = Arrays.copyOfRange(IR,20,32);
char[] rs1 = Arrays.copyOfRange(IR,15,20);
char[] rd = Arrays.copyOfRange(IR,7,12);
char[] funct3 = Arrays.copyOfRange(IR,12,15);
//addi
GPR[getRegister(rd)] = alu.add(new DataType(String.valueOf(GPR[getRegister(rs1)])),new DataType(Transformer.intToBinary(String.valueOf(imm)))).toString().toCharArray();
}
else if(new String(opcode).equals("1100000")){
char[] imm = Arrays.copyOfRange(IR,20,32);
char[] rs1 = Arrays.copyOfRange(IR,15,20);
char[] rd = Arrays.copyOfRange(IR,7,12);
char[] funct3 = Arrays.copyOfRange(IR,12,15);
//lw
GPR[getRegister(rd)] = Arrays.copyOf(getFromMemory(alu.add(new DataType(String.valueOf(GPR[getRegister(rs1)])),new DataType(Transformer.intToBinary(String.valueOf(imm)))).toString()), 32);
}
else if(new String(opcode).equals("1110110")){
char[] imm = Arrays.copyOfRange(IR,12,32);
char[] rd = Arrays.copyOfRange(IR,7,12);
//lui
GPR[getRegister(rd)] = Transformer.intToBinary(String.valueOf(Integer.parseInt(new String(imm),2) << 12)).toCharArray();
}
else if(new String(opcode).equals("1110011")){
char[] imm = Arrays.copyOfRange(IR,20,32);
char[] rs1 = Arrays.copyOfRange(IR,15,20);
char[] rd = Arrays.copyOfRange(IR,7,12);
char[] funct3 = Arrays.copyOfRange(IR,12,15);
//jalr
GPR[getRegister(rd)] = Arrays.copyOf(PC,32);
GPR[1] = Arrays.copyOf(PC,32);
PC = alu.add(new DataType(String.valueOf(GPR[getRegister(rs1)])),new DataType(Transformer.intToBinary(String.valueOf(imm)))).toString().toCharArray();
}
else if(new String(opcode).equals("1100111")){
char[] imm = Arrays.copyOfRange(IR,20,32);
char[] rs1 = Arrays.copyOfRange(IR,15,20);
char[] rd = Arrays.copyOfRange(IR,7,12);
char[] funct3 = Arrays.copyOfRange(IR,12,15);
//ecall
GPR[getRegister(rd)] = Arrays.copyOf(PC,32);
GPR[1] = Arrays.copyOf(PC,32);
interruptController.signal = true;
}
else if(new String(opcode).equals("1101110")){
char[] funct3 = Arrays.copyOfRange(IR,12,15);
char[] funct7 = Arrays.copyOfRange(IR,25,32);
char[] rs1 = Arrays.copyOfRange(IR,15,20);
char[] rs2 = Arrays.copyOfRange(IR,20,25);
char[] rd = Arrays.copyOfRange(IR,7,12);
//addc
GPR[getRegister(rd)] = alu.add(new DataType(String.valueOf(GPR[getRegister(rs1)])),new DataType(String.valueOf(GPR[getRegister(rs2)]))).toString().toCharArray();
}
}
中断
本次实验中，我们使用ecall指令来模拟中断操作。在中断发生时，系统要保存程序的返回位置（是多少？），以便完成中断处理程序后返回原有程序。
private void interrupt(){
// TODO
interruptController.handleInterrupt();
interruptController.signal = false;//中断结束
}
public class InterruptController{
// 中断信号：是否发生中断
public boolean signal;
public StringBuffer console = new StringBuffer();
/** 处理中断 */
public void handleInterrupt(){
console.append("ecall ");
}
public void reset(){
signal = false;
console = new StringBuffer();
}
}