计组机试盘点
Contents
programming07
实验要求是分别实现实模式、分段式、段页式三种内存的地址转换与数据加载功能
资料核心点：
实模式和保护模式都是CPU的工作模式的一种。
实模式出现于早期8088CPU时期。当时由于CPU的性能有限，一共只有 20 位地址线（所以地址空间只有1MB），以及一些 16 位的寄存器。为了能够通过这些 16 位的寄存器去构成 20 位的主存地址，通常需要用两个寄存器，第一个寄存器表示基址，第二个寄存器表示偏移量。那么两个 16 位的值如何组合成一个 20位的地址呢？实模式采用的方式是把基址先向左移 4 位，然后再与偏移量相加。即：
物理地址 = 基址 << 4 + 偏移量
而在本实验中，
logicAddr 48位 = 16位段寄存器 + 32位offset，计算公式为：①(16-bits段寄存器左移4位 + offset的低16-bits) = 20-bits物理地址 ②高位补0到32-bits
@return 32-bits实模式线性地址
因为物理地址只有20位，所以只要偏移量有效的低20位即可，为了最后是32位注意使用inttobinary转换可以自动补齐至32位
分段过程实现将逻辑地址转换为线性地址，分页过程再实现将线性地址转换为物理地址。
段选择符和段寄存器
段选择符格式如下图所示，其中TI和RPL字段我们暂时不用关心。高 13 位的索引值用来确定当前使用的段描述符在描述符表中的位置，表示是其中的第几个段表项。
段选择符存放在段寄存器中，共有 6 个段寄存器: CS、SS、DS、ES、FS和GS。其中，CS是代码段寄存器，指向程序代码所在的段。SS是栈段寄存器，指向栈区所在的段。DS是数据段寄存器，指向程序的全局静态数据区所在的段。其他 3 个段寄存器可以指向任意的数据段。
段描述符
段描述符是一种数据结构，实际上就是分段方式下的段表项。一个段描述符占用 8 个字节，其一般格式如下图所示，包括 32 位的基地址（Base）、 20 位的限界（SegLimit）和一些属性位。属性位比较多，我们只介绍属性位G。
属性位G表示粒度大小。G=1说明段以页（4KB）为基本单位，G=0则段以字节为基本单位。由于界限为20 位，所以当G=0时，最大的段为1B * 2^20 = 1MB。当G=1时，最大的段为4KB * 2^20 = 4GB。
Programming 05 cache
package memory.cache;
import memory.Memory;
import memory.cache.cacheReplacementStrategy.ReplacementStrategy;
import util.Transformer;
import java.util.Arrays;
/**
* 高速缓存抽象类
*/
public class Cache {
public static final boolean isAvailable = true; // 默认启用Cache
public static final int CACHE_SIZE_B = 32 * 1024; // 32 KB 总大小
public static final int LINE_SIZE_B = 64; // 64 B 行大小
private final CacheLine[] cache = new CacheLine[CACHE_SIZE_B / LINE_SIZE_B];
private int SETS; // 组数
private int setSize; // 每组行数
// 单例模式
private static final Cache cacheInstance = new Cache();
private Cache() {
for (int i = 0; i < cache.length; i++) {
cache[i] = new CacheLine();
}
}
public static Cache getCache() {
return cacheInstance;
}
private ReplacementStrategy replacementStrategy; // 替换策略
public static boolean isWriteBack; // 写策略
/**
* 读取[pAddr, pAddr + len)范围内的连续数据，可能包含多个数据块的内容
*
* @param pAddr 数据起始点(32位物理地址 = 26位块号 + 6位块内地址)
* @param len 待读数据的字节数
* @return 读取出的数据，以char数组的形式返回
*/
public byte[] read(String pAddr, int len) {
byte[] data = new byte[len];
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;
}//get the length of the next segment
//if exceed the upper bound, then set the length to the rest of the data
int rowNO = fetch(Transformer.intToBinary(String.valueOf(addr)));
byte[] cache_data = cache[rowNO].getData();
int i = 0;
while (i < nextSegLen) {
data[index] = cache_data[addr % LINE_SIZE_B + i];
index++;
i++;
}
addr += nextSegLen;
}
return data;
}
/**
* 向cache中写入[pAddr, pAddr + len)范围内的连续数据，可能包含多个数据块的内容
*
* @param pAddr 数据起始点(32位物理地址 = 26位块号 + 6位块内地址)
* @param len 待写数据的字节数
* @param data 待写数据
*/
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++;
}
//TODO but done
//write the data according to the write strategy
//1. write through
if(!isWriteBack){
//dirty bit is always 0
//write the data to memory
Memory.getMemory().write(pAddr, len, data);
//update the cache and using strategy
addTimeStamp();
update(rowNO, getTag(pAddr), cache_data);
setTimeStamp(rowNO);
}
else{
//get the dirty bit
cache[rowNO].dirty = true;
//update the cache and using strategy
addTimeStamp();
update(rowNO, getTag(pAddr), cache_data);
setTimeStamp(rowNO);
}
addr += nextSegLen;
}
}
/**
* 从32位物理地址(26位块号 + 6位块内地址)获取目标数据的tag
* 首先将32位物理地址转换为26位，然后将其前面补0至32位
* @param pAddr 32位物理地址
* @return 数据的tag
*
*/
public char[] getTag(String pAddr) {
int tagSize = 26 - (int) (Math.log(SETS) / Math.log(2));
StringBuilder builder = new StringBuilder();
for (int i = 0; i < 26 - tagSize; i++) {
builder.append("0");
}
builder.append(pAddr.substring(0, tagSize));
return builder.toString().toCharArray();
}
/**
* 查询{@link Cache#cache}表以确认包含pAddr的数据块是否在cache内
* 如果目标数据块不在Cache内，则将其从内存加载到Cache
*
* @param pAddr 数据起始点(32位物理地址 = 26位块号 + 6位块内地址)
* @return 数据块在Cache中的对应行号
*/
private int fetch(String pAddr) {
//TODO but done
int blockNO = getBlockNO(pAddr);
int rowNO = map(blockNO);
int start = (blockNO%SETS)*setSize;
int last = start + setSize;
//get the tag
char[] tag = getTag(pAddr);
//if didn't hit
if(rowNO == -1){
//get the data from memory(pAddr is 26 bits but the address in memory is 32 bits)
byte[] data = Memory.getMemory().read(pAddr.substring(0,26)+"000000", LINE_SIZE_B);
int availableRow = -1;
//find an available row
for(int i = start; i < last; i++){
if(!cache[i].validBit){
availableRow = i;
break;
}
}
//if there is an available row
if(availableRow != -1){
//update the cache
addTimeStamp();
update(availableRow, tag, data);
//update the strategy
setTimeStamp(availableRow);
rowNO = availableRow;
}
else{
//if there is no available row
//replace the row
int replace = replacementStrategy.replace(start, last, tag, data);
if(cache[replace].dirty){
//if the dirty bit is 1
//write the data to memory
Memory.getMemory().write(pAddr.substring(0,26)+"000000", LINE_SIZE_B, cache[replace].getData());
cache[replace].dirty = false;
}
//update the cache
addTimeStamp();
update(replace, tag, data);
setTimeStamp(replace);
return replace;
}
}
else {
//if hit
//update the strategy
replacementStrategy.hit(rowNO);
return rowNO;
}
return rowNO;
}
public String getpAddr(int rowNO) {
// System.out.println(getBlockNO("00000000000000000000000001000000"));
// rowNO = setSize * blocknum + blockAddr
int n = 0;
while (Math.pow(2, n) != SETS) {
n += 1;
}
String tag = String.valueOf(this.cache[rowNO].tag).substring(n, 26);
int blocknum = rowNO / setSize;
String block = Transformer.intToBinary("0" + blocknum).substring(32 - n, 32);
String blockAddr = Transformer.intToBinary("0" + (rowNO - setSize * blocknum)).substring(26, 32);
return tag + block + blockAddr;
}
/**
* 根据目标数据内存地址前26位的int表示，进行映射
*
* @param blockNO 数据在内存中的块号
* @return 返回cache中所对应的行，-1表示未命中
*/
private int map(int blockNO) {
//TODO but done
//search for the rowNO
int start = (blockNO%SETS)*setSize;
int last = start + setSize;
for(int i = start; i < last; i++){
if(cache[i].validBit){
if(Integer.parseInt(Transformer.binaryToInt(String.valueOf(cache[i].getTag()))) == blockNO/SETS){
return i;
}
}
}
return -1;
}
/**
* 更新cache
*
* @param rowNO 需要更新的cache行号
* @param tag 待更新数据的Tag
* @param input 待更新的数据
*/
public void update(int rowNO, char[] tag, byte[] input) {
//TODO but done
//update the cache
cache[rowNO].tag = tag;
cache[rowNO].data = input;
cache[rowNO].validBit = true;
//cache[rowNO].dirty = true;
//replacementStrategy.hit(rowNO);
}
/**
* 从32位物理地址(26位块号 + 6位块内地址)获取目标数据在内存中对应的块号
*
* @param pAddr 32位物理地址
* @return 数据在内存中的块号
*/
private int getBlockNO(String pAddr) {
return Integer.parseInt(Transformer.binaryToInt("0" + pAddr.substring(0, 26)));
}
public void setDirty(int rowNO){
cache[rowNO].dirty = false;
}
/**
* 该方法会被用于测试，请勿修改
* 使用策略模式，设置cache的替换策略
*
* @param replacementStrategy 替换策略
*/
public void setReplacementStrategy(ReplacementStrategy replacementStrategy) {
this.replacementStrategy = replacementStrategy;
}
/**
* 该方法会被用于测试，请勿修改
*
* @param SETS 组数
*/
public void setSETS(int SETS) {
this.SETS = SETS;
}
/**
* 该方法会被用于测试，请勿修改
*
* @param setSize 每组行数
*/
public void setSetSize(int setSize) {
this.setSize = setSize;
}
/**
* 告知Cache某个连续地址范围内的数据发生了修改，缓存失效
* 该方法仅在memory类中使用，请勿修改
*
* @param pAddr 发生变化的数据段的起始地址
* @param len 数据段长度
*/
public void invalid(String pAddr, int len) {
int from = getBlockNO(pAddr);
int to = getBlockNO(Transformer.intToBinary(String.valueOf(Integer.parseInt(Transformer.binaryToInt("0" + pAddr)) + len - 1)));
for (int blockNO = from; blockNO <= to; blockNO++) {
int rowNO = map(blockNO);
if (rowNO != -1) {
cache[rowNO].validBit = false;
}
}
}
/**
* 清除Cache全部缓存
* 该方法会被用于测试，请勿修改
*/
public void clear() {
for (CacheLine line : cache) {
if (line != null) {
line.validBit = false;
line.dirty = false;
line.timeStamp = 0L;
line.visited = 0;
}
}
}
/**
* 输入行号和对应的预期值，判断Cache当前状态是否符合预期
* 这个方法仅用于测试，请勿修改
*
* @param lineNOs 行号
* @param validations 有效值
* @param tags tag
* @return 判断结果
*/
public boolean checkStatus(int[] lineNOs, boolean[] validations, char[][] tags) {
if (lineNOs.length != validations.length || validations.length != tags.length) {
return false;
}
for (int i = 0; i < lineNOs.length; i++) {
CacheLine line = cache[lineNOs[i]];
if (line.validBit != validations[i]) {
return false;
}
if (!Arrays.equals(line.getTag(), tags[i])) {
System.out.println(Arrays.toString(line.getTag()));
System.out.println(Arrays.toString(tags[i]));
return false;
}
}
return true;
}
// 获取有效位
public boolean isValid(int rowNO){
return cache[rowNO].validBit;
}
// 获取脏位
public boolean isDirty(int rowNO){
return cache[rowNO].dirty;
}
// LFU算法增加访问次数
public void addVisited(int rowNO){
cache[rowNO].visited++;
}
// 获取访问次数
public int getVisited(int rowNO){
return cache[rowNO].visited;
}
// 用于LRU算法，重置时间戳
public void setTimeStamp(int rowNO){
cache[rowNO].timeStamp = 0L;
}
//增加时间戳
public void addTimeStamp(){
for(int i = 0; i < cache.length; i++){
if(cache[i].validBit)
{
cache[i].timeStamp++;
}
}
}
//用于FIFO算法，重置时间戳
public void setTimeStampFIFO(int rowNo){
cache[rowNo].timeStamp = 1L;
if((rowNo+1)%setSize == 0){
cache[rowNo+1-setSize].timeStamp = 0L;
}else{
cache[rowNo+1].timeStamp = 0L;
}
}
// 获取时间戳
public long getTimeStamp(int rowNO){
return cache[rowNO].timeStamp;
}
// 获取该行数据
public byte[] getData(int rowNO){
return cache[rowNO].data;
}
/**
* Cache行，每行长度为(1+22+{@link Cache#LINE_SIZE_B})
*/
private static class CacheLine {
// 有效位，标记该条数据是否有效
boolean validBit = false;
// 脏位，标记该条数据是否被修改
boolean dirty = false;
// 用于LFU算法，记录该条cache使用次数
int visited = 0;
// 用于LRU和FIFO算法，记录该条数据时间戳
Long timeStamp = 0L;
// 标记，占位长度为26位，有效长度取决于映射策略：
// 直接映射: 17 位
// 全关联映射: 26 位
// (2^n)-路组关联映射: 26-(9-n) 位
// 注意，tag在物理地址中用高位表示，如：直接映射(32位)=tag(17位)+行号(9位)+块内地址(6位)，
// 那么对于值为0b1111的tag应该表示为00000000000000000000001111，其中低12位为有效长度
char[] tag = new char[26];
// 数据
byte[] data = new byte[LINE_SIZE_B];
byte[] getData() {
return this.data;
}
char[] getTag() {
return this.tag;
}
}
}
package cpu.mmu;
import memory.Memory;
import memory.cache.Cache;
import memory.tlb.TLB;
import util.Transformer;
/**
* MMU内存管理单元抽象类
* 接收一个48-bits的逻辑地址，并最终将其转换成32-bits的物理地址
* Memory.SEGMENT和Memory.PAGE标志用于表示是否开启分段和分页。
* 实际上在机器里从实模式进入保护模式后分段一定会保持开启(即使实模式也会使用段寄存器)，因此一共只要实现三种模式的内存管理即可：实模式、只有分段、段页式
* 所有模式的物理地址都采用32-bits，实模式的物理地址高位补0
*/
public class MMU {
private static final MMU mmuInstance = new MMU();
private MMU() {
}
public static MMU getMMU() {
return mmuInstance;
}
private final Memory memory = Memory.getMemory();
private final Cache cache = Cache.getCache();
private final TLB tlb = TLB.getTLB();
/**
* 读取数据
*
* @param logicAddr 48-bits逻辑地址
* @param length 读取数据的长度
* @return 内存中的数据
*/
public byte[] read(String logicAddr, int length) {
String physicalAddr = addressTranslation(logicAddr, length);
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);
if(Cache.isAvailable){
cache.write(physicalAddr, length, data);
return;
}
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++) {
if(TLB.isAvailable){
if(!tlb.isValidPage(i)){
// 缺页中断，该页不在内存中，内存从磁盘加载该页的数据
memory.page_load(i);
tlb.write(i);
}
}
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实模式线性地址
*/
private String toRealLinearAddr(String logicAddr) {
return Transformer.intToBinary(""+(Integer.valueOf(logicAddr.substring(0, 16)+"0000",2)+Integer.valueOf("0000"+logicAddr.substring(48-16),2)));
}
private String add(char[] base, String offsetStr) {
char[] offset = offsetStr.toCharArray();
StringBuilder res = new StringBuilder();
char carry = '0';
for (int i = base.length - 1; i >= 0; i--) {
res.append((carry - '0') ^ (base[i] - '0') ^ (offset[i] - '0'));
carry = (char) (((carry - '0') & (base[i] - '0')) | ((carry - '0') & (offset[i] - '0')) | ((base[i] - '0') & (offset[i] - '0')) + '0');
}
int t = res.length();
for (int i = 0; i < 32 - t; i++) {
res.append("0");
}
return res.reverse().toString();
}
/**
* 分段模式下的逻辑地址转线性地址
*
* @param logicAddr 48位 = 16位段选择符(高13位index选择段表项) + 32位段内偏移
* @return 32-bits 线性地址
*/
private String toSegLinearAddr(String logicAddr) {
String offset = logicAddr.substring(16, 48);
int segIndex = Integer.parseInt(Transformer.binaryToInt(logicAddr.substring(0, 13))); // 段描述符索引
char[] segBase = memory.getBaseOfSegDes(segIndex); // 内存基址base 32位
return add(segBase, offset);
}
/**
* 段页式下的线性地址转物理地址
*
* @param linearAddr 32位
* @return 32-bits 物理地址
*/
private String toPagePhysicalAddr(String linearAddr) {
String offset = linearAddr.substring(20);
int vPageNo = Integer.parseInt(Transformer.binaryToInt("000000000000"+linearAddr.substring(0,20)));
return TLB.isAvailable ? (new String(tlb.getFrameOfPage(vPageNo)) + offset) : (String.valueOf(memory.getFrameOfPage(vPageNo)) + offset);
}
/**
* 根据逻辑地址找到对应的段索引
*
* @param logicAddr 逻辑地址
* @return 整数表示的段索引
*/
private int getSegIndex(String logicAddr) {
String indexStr = logicAddr.substring(0, 13);
return Integer.parseInt(Transformer.binaryToInt(indexStr)); // 段描述符索引
}
private int chars2int(char[] chars) {
return Integer.parseInt(Transformer.binaryToInt(String.valueOf(chars)));
}
public void clear() {
memory.clear();
if (Cache.isAvailable) {
cache.clear();
}
if (TLB.isAvailable) {
tlb.clear();
}
}
}
Programming 03 Integer Add & Sub
package cpu.alu;
import util.DataType;
import util.Transformer;
/**
* Arithmetic Logic Unit
* ALU封装类
*/
public class ALU {
/**
* 返回两个二进制整数的乘积(结果低位截取后32位)
* dest * src
*Put multiplicand in BR and multiplier in QR
* and then the algorithm works as per the following conditions :
* 1. If Qn and Qn+1 are same i.e. 00 or 11 perform arithmetic shift by 1 bit.
* 2. If Qn Qn+1 = 01 do A= A + BR and perform arithmetic shift by 1 bit.
* 3. If Qn Qn+1 = 10 do A= A – BR and perform arithmetic shift by 1 bit.
* @param src 32-bits
* @param dest 32-bits
* @return 32-bits
*/
public DataType mul(DataType src, DataType dest) {
//Booth Algorithm
String srcStr = src.toString();
String desStr = dest.toString();
StringBuilder srcStrBuilder = new StringBuilder("00000000000000000000000000000000");
srcStrBuilder.append(srcStr);
srcStrBuilder.append("0");//to fill the first
int len=srcStrBuilder.length();//should be 65
for(int i=0;i<32;i++){
if(srcStrBuilder.charAt(len-1)=='0'&&srcStrBuilder.charAt(len-2)=='1'){
srcStrBuilder.replace(0,32,sub(desStr,srcStrBuilder.substring(0,32)));
}
else if(srcStrBuilder.charAt(len-1)=='1'&&srcStrBuilder.charAt(len-2)=='0'){
srcStrBuilder.replace(0,32,add(srcStrBuilder.substring(0,32),desStr));
}
srcStrBuilder.insert(0,srcStrBuilder.charAt(0));
srcStrBuilder.deleteCharAt(len);
}
return new DataType(srcStrBuilder.substring(32,64));
}
static DataType remainderReg = new DataType("00000000000000000000000000000000");
/**
* 返回两个二进制整数的除法结果
* dest ÷ src
*
* @param src 32-bits
* @param dest 32-bits
* @return 32-bits
*/
public DataType div(DataType src, DataType dest) {
String srcStr = src.toString();
String desStr = dest.toString();
String retu="";
StringBuilder ans=new StringBuilder("00000000000000000000000000000000");
if(srcStr.equals(ans.toString())){
throw new ArithmeticException("Divisor cannot be 0");
}
if(desStr.equals(ans.toString())){
return dest;
}
int flag=0;
if(srcStr.charAt(0)==desStr.charAt(0)){
flag=0;
if(srcStr.charAt(0)=='1'){
srcStr=not(srcStr);
desStr=not(desStr);
}
}
else{
flag=1;
if(srcStr.charAt(0)=='1'){
srcStr=not(srcStr);
}
else {
desStr=not(desStr);
}
}
ans.append(desStr);
int len=ans.length();
String temp="";
for(int i=1;i<=32;i++){
temp=sub(srcStr,ans.substring(i,i+32));
if(temp.charAt(0)=='0'){
ans.replace(i,i+32,temp);
retu+="1";
}
else{
retu+="0";
}
}
if(flag==1){
retu=not(retu);
}
remainderReg=new DataType(ans.substring(32,64));
if(dest.toString().charAt(0)=='1')
remainderReg=new DataType(not(ans.substring(32,64)));
return new DataType(retu);
}
public static void main(String[] args){
ALU alu=new ALU();
DataType src = new DataType(intToBinary("10"));
DataType dest = new DataType(intToBinary("-25"));
String ans=alu.div(src,dest).toString();
System.out.println(binaryToInt(remainderReg.toString()));
System.out.println(binaryToInt(ans));
}
public String add(String src, String dest) {
int c=0;
int s1,d1;
String s = src.toString();
String d = dest.toString();
StringBuilder ans = new StringBuilder();
for(int i=s.length()-1;i>=0;i--){
s1 = s.charAt(i) - '0';
d1 = d.charAt(i) - '0';
ans.append(c ^ s1 ^ d1);
c = (s1 & d1) | (c & d1) | (s1 & c);
}
return ans.reverse().toString();
}
/*
sub: dest - src
*/
public String sub(String srcStr, String destStr) {
return add(destStr, not(srcStr));
}
public String not(String srcStr){
String ans = "";
for(int i = 0;i < 32;i++){
if(srcStr.charAt(i) == '0'){
ans = ans + '1';
}
else{
ans = ans + '0';
}
}
return add(ans,"00000000000000000000000000000001");
}
public static String intToBinary(String numStr) {
return BinarytoComplement(DecimaltoBinary(numStr,true));
}
public static String binaryToInt(String binStr) {
int num=0;
int len=binStr.length(),result =0;
for(int i=1;i<=len-1;i++)
{
num=binStr.charAt(i)-'0';
result+=num*Math.pow(2,len-1-i);
}
if(binStr.charAt(0)=='1')
result-=Math.pow(2,len-1);
return String.valueOf(result);
}
public static String BinarytoComplement(String binStr){
int len=binStr.length();
StringBuilder result=new StringBuilder();
if(binStr.charAt(0)=='1'){
result.append("1");
for(int i=1;i<len;i++) {
if (binStr.charAt(i) == '0')
result.append("1");
else
result.append("0");
}
//System.out.println(result.toString());
StringBuilder temp=new StringBuilder();
int i=result.length()-1;
while(result.charAt(i)=='1'&&i>0){
temp.append("0");
i--;
}
if(i>0)
temp.append("1");
i--;
for(;i>0;i--){
temp.append(result.charAt(i));
}
temp.append("1");
return temp.reverse().toString();
}
else {
return binStr;
}
}
public static String DecimaltoBinary(String decimalStr,boolean f){
StringBuilder result=new StringBuilder();
int num=Integer.parseInt(decimalStr);
int flag=0;
if(num<0){
num=-num;
flag=1;
}
int len=0;
while(num>0){
result.append(num%2);
num/=2;
len++;
}
while(len<31&&f)
{
result.append("0");
len++;
}
if (f)
{
if (flag == 1) {
result.append("1");
} else
result.append("0");
}
return result.reverse().toString();
}
}
Programmming 05 cache
package memory.cache;
import memory.Memory;
import memory.cache.cacheReplacementStrategy.ReplacementStrategy;
import util.Transformer;
import java.util.Arrays;
/**
* 高速缓存抽象类
*/
public class Cache {
public static final boolean isAvailable = true; // 默认启用Cache
public static final int CACHE_SIZE_B = 32 * 1024; // 32 KB 总大小
public static final int LINE_SIZE_B = 64; // 64 B 行大小
private final CacheLine[] cache = new CacheLine[CACHE_SIZE_B / LINE_SIZE_B];
private int SETS; // 组数
private int setSize; // 每组行数
// 单例模式
private static final Cache cacheInstance = new Cache();
private Cache() {
for (int i = 0; i < cache.length; i++) {
cache[i] = new CacheLine();
}
}
public static Cache getCache() {
return cacheInstance;
}
private ReplacementStrategy replacementStrategy; // 替换策略
public static boolean isWriteBack; // 写策略
/**
* 读取[pAddr, pAddr + len)范围内的连续数据，可能包含多个数据块的内容
*
* @param pAddr 数据起始点(32位物理地址 = 26位块号 + 6位块内地址)
* @param len 待读数据的字节数
* @return 读取出的数据，以char数组的形式返回
*/
public byte[] read(String pAddr, int len) {
byte[] data = new byte[len];
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;
}//get the length of the next segment
//if exceed the upper bound, then set the length to the rest of the data
int rowNO = fetch(Transformer.intToBinary(String.valueOf(addr)));
byte[] cache_data = cache[rowNO].getData();
int i = 0;
while (i < nextSegLen) {
data[index] = cache_data[addr % LINE_SIZE_B + i];
index++;
i++;
}
addr += nextSegLen;
}
return data;
}
/**
* 向cache中写入[pAddr, pAddr + len)范围内的连续数据，可能包含多个数据块的内容
*
* @param pAddr 数据起始点(32位物理地址 = 26位块号 + 6位块内地址)
* @param len 待写数据的字节数
* @param data 待写数据
*/
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++;
}
//TODO but done
//write the data according to the write strategy
//1. write through
if(!isWriteBack){
//dirty bit is always 0
//write the data to memory
Memory.getMemory().write(pAddr, len, data);
//update the cache and using strategy
addTimeStamp();
update(rowNO, getTag(pAddr), cache_data);
setTimeStamp(rowNO);
}
else{
//get the dirty bit
cache[rowNO].dirty = true;
//update the cache and using strategy
addTimeStamp();
update(rowNO, getTag(pAddr), cache_data);
setTimeStamp(rowNO);
}
addr += nextSegLen;
}
}
/**
* 从32位物理地址(26位块号 + 6位块内地址)获取目标数据的tag
* 首先将32位物理地址转换为26位，然后将其前面补0至32位
* @param pAddr 32位物理地址
* @return 数据的tag
*
*/
public char[] getTag(String pAddr) {
int tagSize = 26 - (int) (Math.log(SETS) / Math.log(2));
StringBuilder builder = new StringBuilder();
for (int i = 0; i < 26 - tagSize; i++) {
builder.append("0");
}
builder.append(pAddr.substring(0, tagSize));
return builder.toString().toCharArray();
}
/**
* 查询{@link Cache#cache}表以确认包含pAddr的数据块是否在cache内
* 如果目标数据块不在Cache内，则将其从内存加载到Cache
*
* @param pAddr 数据起始点(32位物理地址 = 26位块号 + 6位块内地址)
* @return 数据块在Cache中的对应行号
*/
private int fetch(String pAddr) {
//TODO but done
int blockNO = getBlockNO(pAddr);
int rowNO = map(blockNO);
int start = (blockNO%SETS)*setSize;
int last = start + setSize;
//get the tag
char[] tag = getTag(pAddr);
//if didn't hit
if(rowNO == -1){
//get the data from memory(pAddr is 26 bits but the address in memory is 32 bits)
byte[] data = Memory.getMemory().read(pAddr.substring(0,26)+"000000", LINE_SIZE_B);
int availableRow = -1;
//find an available row
for(int i = start; i < last; i++){
if(!cache[i].validBit){
availableRow = i;
break;
}
}
//if there is an available row
if(availableRow != -1){
//update the cache
addTimeStamp();
update(availableRow, tag, data);
//update the strategy
setTimeStamp(availableRow);
rowNO = availableRow;
}
else{
//if there is no available row
//replace the row
int replace = replacementStrategy.replace(start, last, tag, data);
if(cache[replace].dirty){
//if the dirty bit is 1
//write the data to memory
Memory.getMemory().write(pAddr.substring(0,26)+"000000", LINE_SIZE_B, cache[replace].getData());
cache[replace].dirty = false;
}
//update the cache
addTimeStamp();
update(replace, tag, data);
setTimeStamp(replace);
return replace;
}
}
else {
//if hit
//update the strategy
replacementStrategy.hit(rowNO);
return rowNO;
}
return rowNO;
}
public String getpAddr(int rowNO) {
// System.out.println(getBlockNO("00000000000000000000000001000000"));
// rowNO = setSize * blocknum + blockAddr
int n = 0;
while (Math.pow(2, n) != SETS) {
n += 1;
}
String tag = String.valueOf(this.cache[rowNO].tag).substring(n, 26);
int blocknum = rowNO / setSize;
String block = Transformer.intToBinary("0" + blocknum).substring(32 - n, 32);
String blockAddr = Transformer.intToBinary("0" + (rowNO - setSize * blocknum)).substring(26, 32);
return tag + block + blockAddr;
}
/**
* 根据目标数据内存地址前26位的int表示，进行映射
*
* @param blockNO 数据在内存中的块号
* @return 返回cache中所对应的行，-1表示未命中
*/
private int map(int blockNO) {
//TODO but done
//search for the rowNO
int start = (blockNO%SETS)*setSize;
int last = start + setSize;
for(int i = start; i < last; i++){
if(cache[i].validBit){
if(Integer.parseInt(Transformer.binaryToInt(String.valueOf(cache[i].getTag()))) == blockNO/SETS){
return i;
}
}
}
return -1;
}
/**
* 更新cache
*
* @param rowNO 需要更新的cache行号
* @param tag 待更新数据的Tag
* @param input 待更新的数据
*/
public void update(int rowNO, char[] tag, byte[] input) {
//TODO but done
//update the cache
cache[rowNO].tag = tag;
cache[rowNO].data = input;
cache[rowNO].validBit = true;
//cache[rowNO].dirty = true;
//replacementStrategy.hit(rowNO);
}
/**
* 从32位物理地址(26位块号 + 6位块内地址)获取目标数据在内存中对应的块号
*
* @param pAddr 32位物理地址
* @return 数据在内存中的块号
*/
private int getBlockNO(String pAddr) {
return Integer.parseInt(Transformer.binaryToInt("0" + pAddr.substring(0, 26)));
}
public void setDirty(int rowNO){
cache[rowNO].dirty = false;
}
/**
* 该方法会被用于测试，请勿修改
* 使用策略模式，设置cache的替换策略
*
* @param replacementStrategy 替换策略
*/
public void setReplacementStrategy(ReplacementStrategy replacementStrategy) {
this.replacementStrategy = replacementStrategy;
}
/**
* 该方法会被用于测试，请勿修改
*
* @param SETS 组数
*/
public void setSETS(int SETS) {
this.SETS = SETS;
}
/**
* 该方法会被用于测试，请勿修改
*
* @param setSize 每组行数
*/
public void setSetSize(int setSize) {
this.setSize = setSize;
}
/**
* 告知Cache某个连续地址范围内的数据发生了修改，缓存失效
* 该方法仅在memory类中使用，请勿修改
*
* @param pAddr 发生变化的数据段的起始地址
* @param len 数据段长度
*/
public void invalid(String pAddr, int len) {
int from = getBlockNO(pAddr);
int to = getBlockNO(Transformer.intToBinary(String.valueOf(Integer.parseInt(Transformer.binaryToInt("0" + pAddr)) + len - 1)));
for (int blockNO = from; blockNO <= to; blockNO++) {
int rowNO = map(blockNO);
if (rowNO != -1) {
cache[rowNO].validBit = false;
}
}
}
/**
* 清除Cache全部缓存
* 该方法会被用于测试，请勿修改
*/
public void clear() {
for (CacheLine line : cache) {
if (line != null) {
line.validBit = false;
line.dirty = false;
line.timeStamp = 0L;
line.visited = 0;
}
}
}
/**
* 输入行号和对应的预期值，判断Cache当前状态是否符合预期
* 这个方法仅用于测试，请勿修改
*
* @param lineNOs 行号
* @param validations 有效值
* @param tags tag
* @return 判断结果
*/
public boolean checkStatus(int[] lineNOs, boolean[] validations, char[][] tags) {
if (lineNOs.length != validations.length || validations.length != tags.length) {
return false;
}
for (int i = 0; i < lineNOs.length; i++) {
CacheLine line = cache[lineNOs[i]];
if (line.validBit != validations[i]) {
return false;
}
if (!Arrays.equals(line.getTag(), tags[i])) {
System.out.println(Arrays.toString(line.getTag()));
System.out.println(Arrays.toString(tags[i]));
return false;
}
}
return true;
}
// 获取有效位
public boolean isValid(int rowNO){
return cache[rowNO].validBit;
}
// 获取脏位
public boolean isDirty(int rowNO){
return cache[rowNO].dirty;
}
// LFU算法增加访问次数
public void addVisited(int rowNO){
cache[rowNO].visited++;
}
// 获取访问次数
public int getVisited(int rowNO){
return cache[rowNO].visited;
}
// 用于LRU算法，重置时间戳
public void setTimeStamp(int rowNO){
cache[rowNO].timeStamp = 0L;
}
//增加时间戳
public void addTimeStamp(){
for(int i = 0; i < cache.length; i++){
if(cache[i].validBit)
{
cache[i].timeStamp++;
}
}
}
//用于FIFO算法，重置时间戳
public void setTimeStampFIFO(int rowNo){
cache[rowNo].timeStamp = 1L;
if((rowNo+1)%setSize == 0){
cache[rowNo+1-setSize].timeStamp = 0L;
}else{
cache[rowNo+1].timeStamp = 0L;
}
}
// 获取时间戳
public long getTimeStamp(int rowNO){
return cache[rowNO].timeStamp;
}
// 获取该行数据
public byte[] getData(int rowNO){
return cache[rowNO].data;
}
/**
* Cache行，每行长度为(1+22+{@link Cache#LINE_SIZE_B})
*/
private static class CacheLine {
// 有效位，标记该条数据是否有效
boolean validBit = false;
// 脏位，标记该条数据是否被修改
boolean dirty = false;
// 用于LFU算法，记录该条cache使用次数
int visited = 0;
// 用于LRU和FIFO算法，记录该条数据时间戳
Long timeStamp = 0L;
// 标记，占位长度为26位，有效长度取决于映射策略：
// 直接映射: 17 位
// 全关联映射: 26 位
// (2^n)-路组关联映射: 26-(9-n) 位
// 注意，tag在物理地址中用高位表示，如：直接映射(32位)=tag(17位)+行号(9位)+块内地址(6位)，
// 那么对于值为0b1111的tag应该表示为00000000000000000000001111，其中低12位为有效长度
char[] tag = new char[26];
// 数据
byte[] data = new byte[LINE_SIZE_B];
byte[] getData() {
return this.data;
}
char[] getTag() {
return this.tag;
}
}
}
Programming 04 Float add and mul and div
public String floatAddition(String operand1, String operand2, int eLength, int sLength, int gLength) {
//floatAddition加法的特殊情况，如果有0，答案就是另一个，如果有一个是+Inf结果就是Inf
if (allZero(operand1.substring(1))) {
return "0" + operand2;
}
if (allZero(operand2.substring(1))) {
return "0" + operand1;
}
//处理阶码，考虑阶码的2种特殊的情况，全0和全1.全0就+1，全1的话，返回本身
int Xexponent = Integer.valueOf(operand1.substring(1, 1 + eLength), 2); //注意这里要加上第二个参数2，不然默认十进制转化
int Yexponent = Integer.valueOf(operand2.substring(1, 1 + eLength), 2);
if (Xexponent == 0) Xexponent++; //如果指数是全0，那么指数的真实值为1，因为阶码已经考虑了隐藏位
if (Yexponent == 0) Yexponent++;
if (Xexponent == 255) {
return "0" + operand1;
}
if (Yexponent == 255) {
return "0" + operand2;
}
//处理尾数：前面加了1位是规格化的
StringBuilder Xsig = new StringBuilder(getSignificand(operand1, eLength, sLength)); //get the two significands including the implicit bit
StringBuilder Ysig = new StringBuilder(getSignificand(operand2, eLength, sLength));
//加上保护胃，1+23+3=27
for (int i = 0; i < gLength; i++) { //add the guard bits
Xsig.append("0");
Ysig.append("0");
}
//现在Xsig组成为 隐藏位+sLength+保护位
int exponent = Math.max(Xexponent, Yexponent); //choose the bigger exponent and right shift the smaller one
//提取大的然后右移动
if (Xexponent != Yexponent) {
if (Xexponent > Yexponent) {
Ysig = new StringBuilder(rightShift(Ysig.toString(), Xexponent - Yexponent));
} else {
Xsig = new StringBuilder(rightShift(Xsig.toString(), Yexponent - Xexponent));
}
}
//尾码全部0就可以直接输出了
if (allZero(Xsig.toString())) {
return "0" + operand2;
}
if (allZero(Ysig.toString())) {
return "0" + operand1;
}
String temp = signedAddition(operand1.charAt(0) + Xsig.toString(), operand2.charAt(0) + Ysig.toString(), Xsig.length()); //需要传入符号。这里直接设置寄存器长度为 Xsig.length() 就可以检测是否溢出，传入参数结构为 符号位+隐藏位+sLength+保护位
//temp结构为 溢出位+符号位+隐藏位+sLength+保护位
boolean overflow = temp.charAt(0) != '0';
char sign = temp.charAt(1);
String sig = temp.substring(2); //sig结构为 隐藏位+sLength+保护位
StringBuilder answer = new StringBuilder();
//溢出情况
if (overflow) {
sig = "1" + sig.substring(0, sig.length() - 1); //右移一位（不可能要移动两次）
exponent++;
if (exponent == maxValue(eLength)) { //指数上溢
answer.append("1").append(sign);
answer.append(Integer.toBinaryString(exponent));
for (int i = 0; i < sLength; i++) answer.append("0"); //无穷要求阶码全为0
return answer.toString();
}
}
if (allZero(sig)) {
for (int i = 0; i < eLength + sLength + 2; i++) answer.append("0");
return answer.toString();
}
while (sig.charAt(0) != '1' && exponent > 0) { //规格化
sig = leftShift(sig, "1");
exponent--;
}
if (exponent == 0) { //非规格化数
sig = rightShift(sig, 1);
}
StringBuilder ans_exponent = new StringBuilder(Integer.toBinaryString(exponent));
int len = ans_exponent.length(); //注意要先把长度单独写出来，不能写在循环里面
for (int i = 0; i < eLength - len; i++) ans_exponent.insert(0, "0"); //补齐到eLength长度
return "0" + round(sign, ans_exponent.toString(), sig);
}Another Version
public DataType add(DataType src, DataType dest) {
String destStr = dest.toString();
String srcStr = src.toString();
if (destStr.matches(IEEE754Float.NaN_Regular) || srcStr.matches(IEEE754Float.NaN_Regular)) {
return new DataType(IEEE754Float.NaN);
}
String cornerCondition = cornerCheck(addCorner, destStr, srcStr);
if (null != cornerCondition)
return new DataType(cornerCondition);
//corner cases
String exp1 = destStr.substring(1, 9);
String exp2 = srcStr.substring(1, 9);
//get the exp value
int expVal_1 = Integer.valueOf(exp1, 2);
int expVal_2 = Integer.valueOf(exp2, 2);
if (expVal_1 == 255)
return dest;
if (expVal_2 == 255)
return src;
if (destStr.substring(1).equals(IEEE754Float.P_ZERO.substring(1)))
return src;
if (srcStr.substring(1).equals(IEEE754Float.P_ZERO.substring(1)))
return dest;
//some other corner cases
String sig1 = "";
String sig2 = "";
if (expVal_1 == 0) {
expVal_1++;
sig1 += "0";
} else sig1 += "1";
if (expVal_2 == 0) {
expVal_2++;
sig2 += "0";
} else sig2 += "1";
sig1 = sig1 + destStr.substring(9) + "000";
sig2 = sig2 + srcStr.substring(9) + "000";
int expVal = Math.max(expVal_1, expVal_2);
if (expVal_1 > expVal_2) {
sig2 = rightShift(sig2, expVal - expVal_2);
} else {
sig1 = rightShift(sig1, expVal - expVal_1);
}
String temp = signedADD(sig1, sig2, destStr.charAt(0), srcStr.charAt(0));
String sig = temp.substring(1);
String sign = temp.substring(0, 1);
expVal++;//因为转换成规格化之后位数+1但实际大小没变动
while (sig.charAt(0) == '0' && expVal > 0) {
expVal--;
sig = sig.substring(1) + '0';
}
while (!sig.startsWith("00000000000000000000000000") && expVal < 0) {
expVal++;
sig = rightShift(sig, 1);
}
if (expVal >= 255)
return new DataType(sign + "1111111100000000000000000000000");
if (expVal == 0)
sig = rightShift(sig, 1);
String exp = Transformer.intToBinary(String.valueOf(expVal)).substring(32 - 8);
String round = round(sign.charAt(0), exp, sig);
return new DataType(round);
}
private String signedADD(String sig1, String sig2, char sign1, char sign2) {
boolean sameSign = sign1 == sign2;
if (sig1.equals("000000000000000000000000000"))
return sign2 + sig2;
if (sig2.equals("000000000000000000000000000"))
return sign1 + sig1;
if (sameSign) {
int intSig1 = Integer.valueOf(sig1, 2);
int intSig2 = Integer.valueOf(sig2, 2);
String intToBinary = Transformer.intToBinary(String.valueOf(intSig1 + intSig2));
String ansSig = intToBinary.substring(32 - 28);
return sign1 + ansSig;
} else {
int intSig1 = Integer.valueOf(sig1, 2);
int intSig2 = Integer.valueOf(sig2, 2);
if (sig1.equals(sig2))
return "00000000000000000000000000000";
String intToBinary = Transformer.intToBinary(String.valueOf(Math.abs(intSig1 - intSig2)));
String ansSig = intToBinary.substring(32 - 28);
return intSig1 > intSig2 ? (sign1 + ansSig) : (sign2 + ansSig);
}
}Another version of div
package cpu.fpu;
import util.DataType;
import util.IEEE754Float;
import java.util.Collections;
import static util.Transformer.oneAdder;
import static util.Transformer.negation;
public class FPU {
final int eLength = 8;
final int sLength = 23;
final int gLength = 3;
class FLOAT {
char sign;
int exp;
String sig;
FLOAT(String v) {
sign = v.charAt(0);
exp = Integer.parseInt(v.substring(1, 9), 2);
sig = exp == 0 ? "0" : "1";
if (exp == 0)
exp++;
sig += v.substring(9) + "000";
}
}
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},
};
//dest + src
public DataType add(DataType src, DataType dest) {
String a = src.toString();
String b = dest.toString();
if (Corner(a, b, addCorner) != null) {
return Corner(a, b, addCorner);
}
return new DataType(floatAddition(new FLOAT(a), new FLOAT(b)));
}
//dest - src
public DataType sub(DataType src, DataType dest) {
String a = src.toString();
String b = dest.toString();
if (Corner(a, b, subCorner) != null) {
return Corner(a, b, subCorner);
}
a = negation("" + a.charAt(0)) + a.substring(1);
return new DataType(floatAddition(new FLOAT(a), new FLOAT(b)));
}
//dest * src
public DataType mul(DataType src, DataType dest) {
String a = src.toString();
String b = dest.toString();
if (Corner(a, b, mulCorner) != null) {
return Corner(a, b, mulCorner);
}
return new DataType(floatMul(new FLOAT(a), new FLOAT(b)));
}
//dest / src
public DataType div(DataType src, DataType dest) {
String a = src.toString();
String b = dest.toString();
if (Corner(a, b, divCorner) != null) {
return Corner(a, b, divCorner);
}
boolean sameSign = a.charAt(0) == b.charAt(0);
if (isZero(b.substring(1))) {
return sameSign ? new DataType(IEEE754Float.P_ZERO) : new DataType(IEEE754Float.N_ZERO);
}
if (isZero(a.substring(1))) throw new ArithmeticException();
return new DataType(floatDiv(new FLOAT(b), new FLOAT(a)));
}
public String floatAddition(FLOAT a, FLOAT b) {
int exp = Math.max(a.exp, b.exp);
b.sig = rightShift(b.sig, exp - b.exp);
a.sig = rightShift(a.sig, exp - a.exp);
String temp = signedAdder(a.sign + a.sig, b.sign + b.sig);
boolean overFlow = temp.charAt(0) == '1';
char sign = temp.charAt(1);
String sig = temp.substring(2);
if (overFlow) {
exp++;
sig = "1" + sig.substring(0, sig.length() - 1);
}
if (exp >= 255) {
return "" + sign + "11111111" + String.join("", Collections.nCopies(sLength, "0"));
}
return NormalTreatment1(sig, exp, sign, sig.length());
}
public String floatMul(FLOAT a, FLOAT b) {
int exp = a.exp + b.exp - 127;
char sign = (char) ((a.sign - '0') ^ (b.sign - '0') + '0');
if (a.exp == 255 || b.exp == 255) {
return "" + sign + "11111111" + String.join("", Collections.nCopies(sLength, "0"));
}
String sig = unsignedMul(a.sig, b.sig, a.sig.length());
//乘积的隐藏位是2位
exp++;
return NormalTreatment2(sig, exp, sign, a.sig.length());
}
// a / b
public String floatDiv(FLOAT a, FLOAT b) {
char sign = (char) ((a.sign - '0') ^ (b.sign - '0') + '0');
int exp = a.exp - b.exp + 127;
if (a.exp == 255) {
return "" + sign + "11111111" + String.join("", Collections.nCopies(sLength, "0"));
}
if (b.exp == 255) {
return "" + sign + "00000000" + String.join("", Collections.nCopies(sLength, "0"));
}
String temp = unsignedDiv(a.sig, b.sig, a.sig.length());
return NormalTreatment2(temp, exp, sign, a.sig.length());
}
public String NormalTreatment1(String sig, int exp, char sign, int length) {
while (sig.charAt(0) != '1' && exp > 0) { //加减乘除均需要
sig = leftShift(sig, 1);
exp--;
}
if (exp == 0) {
sig = rightShift(sig, 1);
}
if (isZero(sig)) { //仅在加减中需要注意符号位设为0
return "" + String.join("", Collections.nCopies(eLength + sLength + 1, "0"));
}
String expStr = String.format("%8s", Integer.toBinaryString(exp)).replaceAll(" ", "0");
return round(sign, expStr, sig);
}
public String NormalTreatment2(String sig, int exp, char sign, int length) {
while (sig.charAt(0) != '1' && exp > 0) { //加减乘除均需要
sig = leftShift(sig, 1);
exp--;
}
while (!isZero(sig.substring(0, length)) && exp < 0) { //仅在乘除中需要
sig = rightShift(sig, 1);
exp++;
}
if (exp >= 255) { //乘除中需要
return "" + sign + "11111111" + String.join("", Collections.nCopies(sLength, "0"));
}
if (exp == 0) {
sig = rightShift(sig, 1);
}
if (exp < 0) { //仅在乘除中需要，注意符号位设为sign
return "" + sign + String.join("", Collections.nCopies(eLength + sLength, "0"));
}
String expStr = String.format("%8s", Integer.toBinaryString(exp)).replaceAll(" ", "0");
return round(sign, expStr, sig);
}
//第一位是符号位的加法
public String signedAdder(String a, String b) {
char signA = a.charAt(0);
char signB = b.charAt(0);
//对于零情况的特殊判断
if (isZero(a.substring(1))) return "0" + b;
if (isZero(b.substring(1))) return "0" + a;
a = a.substring(1);
b = b.substring(1);
if (signA == signB) { //用 temp.charAt(0) 判断是否溢出
String temp = carry_adder(a, b, 0, a.length());
return "" + temp.charAt(0) + signA + temp.substring(1);
} else {
b = oneAdder(negation(b)).substring(1);
String temp = carry_adder(a, b, 0, a.length());
if (temp.charAt(0) == '1') return "0" + signA + temp.substring(1);
return "0" + negation("" + signA) + oneAdder(negation(temp.substring(1))).substring(1);
}
}
String unsignedMul(String x, String y, int length) {
String ans = String.join("", Collections.nCopies(length, "0")) + y;
for (int i = 0; i < length; i++) {
char carry = '0';
if (ans.charAt(2 * length - 1) == '1') {
String temp = carry_adder(x, ans.substring(0, length), 0, length);
carry = temp.charAt(0);
ans = temp.substring(1) + ans.substring(length);
}
ans = carry + ans.substring(0, 2 * length - 1);
}
return ans;
}
// x / y
String unsignedDiv(String x, String y, int length) {
String Qstr = "";
x += String.join("", Collections.nCopies(length, "0"));
String negy = oneAdder(negation(y)).substring(1);
for (int i = 0; i < length; i++) {
String temp = carry_adder(x.substring(0, length), negy, 0, length).substring(1);
if (temp.charAt(0) == '0') {
x = temp.substring(1) + x.substring(length) + "1";
} else {
x = leftShift(x, 1);
}
}
Qstr = x.substring(length);
return Qstr;
}
public String carry_adder(String add1, String add2, int carry, int length) {
StringBuilder ans = new StringBuilder();
int x, y;
for (int i = length - 1; i >= 0; i--) {//顺序是从低位到高位
x = add1.charAt(i) - '0';
y = add2.charAt(i) - '0';
ans.insert(0, x ^ y ^ carry);
carry = x & carry | y & carry | x & y;
}
return "" + carry + ans;
}
public boolean isZero(String s) {
for (char c : s.toCharArray()) {
if (c != '0') return false;
}
return true;
}
public String leftShift(String s, int n) {
StringBuilder res = new StringBuilder(s.substring(n));
for (int i = 0; i < n; i++) {
res.append(0);
}
return res.toString();
}
public DataType Corner(String a, String b, String[][] corner) {
String check = cornerCheck(corner, a, b);
if (check != null) return new DataType(check);
if (a.matches(IEEE754Float.NaN_Regular) || b.matches(IEEE754Float.NaN_Regular)) {
return new DataType(IEEE754Float.NaN);
}
return null;
}
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;
}
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 || (grs == 4 && sig.endsWith("1"))) {
sig = oneAdder(sig);
if (sig.charAt(0) == '1') {
exp = oneAdder(exp).substring(1);
sig = sig.substring(1);
}
}
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);
}
}