2023-12-07

计组机试盘点

2023-12-07 Windows相关

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.
- 1. If Qn Qn+1 = 01 do A= A + BR and perform arithmetic shift by 1 bit.
- 1. 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"));

/**
 * 根据目标数据内存地址前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);
}

}

返回文章中心询问 Blog Bot