The Hardware Software Interface Lab 1

课程主页：https://courses.cs.washington.edu/courses/cse351/16sp/

课程资料：

实验部分：https://github.com/vuquangtrong/HW-SW_Interface_Course

实验说明：https://courses.cs.washington.edu/courses/cse351/13sp/lab-0.html

课件：http://academictorrents.com/details/b63a566df824b39740eb9754e4fe4c0140306f4b

课程视频：https://www.bilibili.com/video/BV1Zt411s7Gg?from=search&seid=8781593976070799647

这次完成Lab1，主要是进行比特操作。

bits.c

编译以及测试结果

make
./btest
Score	Rating	Errors	Function
 1	1	0	bitAnd
 1	1	0	bitXor
 1	1	0	thirdBits
 2	2	0	fitsBits
 2	2	0	sign
 2	2	0	getByte
 3	3	0	logicalShift
 3	3	0	addOK
 4	4	0	bang
 3	3	0	conditional
 4	4	0	isPower2
Total points: 26/26

./dlc -e bits.c
dlc:bits.c:126:bitAnd: 4 operators
dlc:bits.c:138:bitXor: 8 operators
dlc:bits.c:160:thirdBits: 6 operators
dlc:bits.c:181:fitsBits: 7 operators
dlc:bits.c:209:sign: 9 operators
dlc:bits.c:227:getByte: 3 operators
dlc:bits.c:272:logicalShift: 20 operators
dlc:bits.c:296:addOK: 16 operators
dlc:bits.c:319:bang: 9 operators
dlc:bits.c:342:conditional: 12 operators
dlc:bits.c:370:isPower2: 11 operators

bitAnd

利用如下恒等式即可

$x \land y = \overline{(\overline x\lor \overline y)}$

代码如下

int bitAnd(int x, int y) {
  int z;
  z = ~((~x) | (~y));
  return z;
}

bitXor

异或的运算规则如下：

$x$	$y$	$x\text{^}y$
1	1	0
1	0	1
0	1	1
0	0	0

不难看出

$x\text{^}y = (\bar x \land y)\lor (x \land \bar y) =\overline{\overline {(\bar x \land y)} \land \overline {(\bar y \land x)} }$

代码如下

int bitXor(int x, int y) {
  return ~((~((~x) & y)) & (~((~y) & x)));
}

thirdBits

题目意思是从最低位开始，第一位为$1$，然后每隔$3$位为$1$，所以结果为

0x49249249

代码如下

int thirdBits(void) {
  int x, y, z;
  //0x49
  x = 73;
  //0x2
  y = 2;
  //0x492
  z = (x << 4) | y;
  //0x492492
  z = (z << 12) | z;
  //0x49249249
  z = (z << 8) | x;

  return z;
}

fitsBits

思路是利用扩展的规则，假设输入为$x$，首先左移$32-n$位，然后右移$32-n$位得到$y$，最后判断两者是否相同即可。

首先回顾拓展以及求反的方法：

拓展

有符号拓展的方式：

任务：
- 给定$w$比特位的有符号整型$x$
- 将其转换为$w+k$比特位有符号整型，并且值相同
规则：
- 将符号位复制$k$份
- $X^{\prime}=X_{w-1}, \dots, X_{w-1}, X_{w-1}, X_{w-2}, \dots, X_{0}$

求反

假设输入为$x$，我们希望得到$-x$
方式为对比特向量取反然后加$1$

证明如下：

$B 2 T_w(X)=-x_{w-1} \cdot 2^{w-1}+\sum_{i=0}^{w-2} x_{i} \cdot 2^{i}$

取反

$\begin{aligned} -(1-x_{w-1}) \cdot 2^{w-1}+\sum_{i=0}^{w-2} (1-x_{i}) \cdot 2^{i} &= -2^{w-1} + \sum_{i=0}^{w-2} 2^{i} +x_{w-1} \cdot 2^{w-1}-\sum_{i=0}^{w-2} x_{i} \cdot 2^{i}\\ &=-1+x_{w-1} \cdot 2^{w-1}-\sum_{i=0}^{w-2} x_{i} \cdot 2^{i} \end{aligned}$

加$1$得到

$x_{w-1} \cdot 2^{w-1}-\sum_{i=0}^{w-2} x_{i} \cdot 2^{i} =-B2T_w(X)$

现在的过程相当于上述过程的逆过程，只要判断$x$是否为如下形式即可

$\underbrace{a_0\ldots a_0}_{32-n个a_0} a_0a_1\ldots a_{n-1}$

所以可以通过先左移$32-n$位，再右移$32-n$位的方法完成判断，代码如下

int fitsBits(int x, int n) {
  int y, m, res;
  //m=32-n
  m = 32 + (~n) + 1;
  //带符号扩展
  y = (x << m) >> m;
  //判断是否相同
  res = !(x ^ y);

  return res;
}

备注：本题原来的测试程序个人感觉有点问题，原始的测试程序如下

int test_fitsBits(int x, int n)
{
  int TMin_n = -(1 << (n-1));
  int TMax_n = (1 << (n-1)) - 1;
  return x >= TMin_n && x <= TMax_n;
}

但是$n=32$时$\text{TMin_n}$的计算是有问题的，正确的代码如下

int test_fitsBits(int x, int n)
{
  int TMin_n, TMax_n;
  if (n < 32){
    TMin_n = -(1 << (n-1));
    TMax_n = (1 << (n-1)) - 1;
  }else{
    TMin_n = (1 << (n-1));
    TMax_n = ~(1 << (n-1));
  }
  return x >= TMin_n && x <= TMax_n;
}

sign

注释中写的比较清楚，代码如下：

int sign(int x) {
  int mask1, mask2, r1, r2, res;
  //将x转换为0或1，x为0的时候转换为1，其余情形为0
  mask1 = (!x);
  //取反转换为1110,1111，x为0的时候转换为1110，其余情形为1111
  mask1 = ~mask1;
  //加1转换为1111,0000，x为0的时候转换为1111，其余情形为0000
  mask1 = mask1 + 1;
  //x为0的时候转换为0000，其余情形为1111
  mask1 = ~mask1;
  //x>0转换为0000，x<0转换为1111
  mask2 = (x >> 31);
  //x>0的情形
  r1 = (~mask2) & 1;
  //x<0的情形
  r2 = mask2;
  res = mask1 & (r1 | r2);

  return res;
}

getByte

这个比较简单，只要进行移位以及使用mask即可：

int getByte(int x, int n) {
  int mask, d, res;
  mask = 0xFF;
  //d = n * 8
  d = n << 3;
  res = x >> d;
  res = res & mask;

  return res;
}

logicalShift

注意此题需要考虑$n=0$的特殊情形，否则会报错，方法依然是生成多个mask，具体内容在代码中

int logicalShift(int x, int n) {
  int r1, r2, r3, res, mask1, mask2, mask3;
  //n != 0
  //x >= 0时为全0，x < 0时为全1
  mask1 = x >> 31;

  //将n转换为0或1，n为0的时候转换为1，其余情形为0
  mask2 = (!n);
  //取反转换为1110,1111，n为0的时候转换为1110，其余情形为1111
  mask2 = ~mask2;
  //加1转换为1111,0000，n为0的时候转换为1111，其余情形为0000
  mask2 = mask2 + 1;

  //前n个为1，其余的为0
  //(~n) + 1 = -n
  mask3 = (~0) << (32 + (~n) + 1);
  //前n位为0，其余的为1
  mask3 = ~mask3;

  //x >= 0
  r1 = x >> n;

  //x < 0的结果
  //将前n位变为0
  r2 = r1 & mask3;
  //生成中间结果
  res = ((r1 & (~mask1)) | (r2 & mask1));
  res = res & (~mask2);

  //n = 0特殊处理
  r3 = x & mask2;
  //生成结果
  res = res | r3;

  return res;
}

addOK

溢出只会发生在两个正数相加为负或者两个负数相加为正的情形，据此判断即可：

int addOK(int x, int y) {
  int f1, f2, f3, f4, f5, z, res;
  z = x + y;
  //正负号，如果小于0则为0，否则为1
  f1 = !(x >> 31);
  f2 = !(y >> 31);
  f3 = !(z >> 31);
  //错误1，两个负数相加为正，出现此情形则为1
  f4 = ((~f1) & (~f2) & f3);
  //错误2，两个正数相加为负，出现此情形则为1
  f5 = (f1 & f2 & (~f3));
  //生成结果
  res = !(f4 | f5);

  return res;
}

bang

具体方法是将正数转换成负数，然后对负数和零进行处理：

int bang(int x) {
  int mask, r1, r2, res;
  //x >= 0时为全0，否则为全1
  mask = x >> 31;
  //-x
  r1 = (~x) + 1;
  //将x >= 0的情形变成x <= 0
  r2 = (x & mask) | (r1 & (~mask));
  //r2 = 0时为全0，否则为全1
  res = r2 >> 31;
  //x = 0时为1，否则为0
  res = res + 1;

  return res;
}

conditional

和上题类似，将正数转换成负数，然后生成mask：

int conditional(int x, int y, int z) {
  int mask, mask1, r1, r2, res;
  //x >= 0时为全0，否则为全1
  mask = x >> 31;
  //-x
  r1 = (~x) + 1;
  //将x >= 0的情形变成x <= 0
  r2 = (x & mask) | (r1 & (~mask));
  //r2 = 0时为全0，否则为全1
  mask1 = r2 >> 31;

  res = ((mask1 & y) | ((~mask1) & z));
  
  return res;
}

isPower2

此题比较难，参考了如下资料：

http://read.pudn.com/downloads136/sourcecode/book/580317/Lab1/bits.c__.htm

首先对于满足条件的数，形式必然如下

$a=\underbrace{0\ldots0}_{n个0}1 \underbrace{0\ldots0}_{m个0}$

所以

$-a=\underbrace{1\ldots1}_{n个0}1 \underbrace{0\ldots0}_{m个0}$

因此

$(-a)\text{^}a=a$

容易验证，对于不满足条件的数，上述等式必然不成立，我们称上述性质为性质a。

所以对于满足条件的数，必然有如下性质：

非负
大于0
满足性质a

因此得到如下代码

int isPower2(int x) {
  int minus_x;
  int f1, f2, f3, res;
  //判断正负， x < 0时为全1，否则为全0
  f1 = x >> 31;

  //判断是否为0
  f2 = (!x);

  //从形式上判断
  minus_x = (~x) + 1;
  //x = 2 ^ k时f2为1，否则为0
  f3 = !((minus_x & x) ^ x);

  //生成结果
  res = (~f1) & (~f2) & f3;

  return res;
}

pointer.c

编译以及测试结果

make
./ptest
intSize() = 4	[ OK ]
doubleSize() = 8	[ OK ]
pointerSize() = 8	[ OK ]
changeValue() = 351	[ OK ]
withinSameBlock(0x1, 0x48) = 0	[ OK ]
withinSameBlock(0x1, 0x4) = 1	[ OK ]
withinSameBlock(0x12345678, 0x1) = 0	[ OK ]
withinSameBlock(0x12345678, 0x12345658) = 1	[ OK ]
withinSameBlock(0x12345678, 0x12345686) = 0	[ OK ]
withinArray(0x1, 4, 0xd) = 1	[ OK ]
withinArray(0x1, 4, 0x11) = 0	[ OK ]
withinArray(0x14, 4, 0xd) = 0	[ OK ]
invert(142, 3, 3) = 182	[ OK ]
invert(1645, 2, 4) = 1617	[ OK ]
invert(123456, 12, 1) = 127552	[ OK ]

intSize

int intSize() {
  int intArray[10];
  int * intPtr1;
  int * intPtr2;
  // TODO: Write code to compute size of an integer.
  int size;
  void * p1 = (void *)intArray;
  void * p2 = (void *)(intArray + 1);
  size = p2 - p1;
    
  return size;
}

doubleSize

int doubleSize() {
  double doubArray[10];
  double * doubPtr1;
  double * doubPtr2;
  // TODO: Write code to compute size of a double.
  int size;
  void * p1 = (void *)doubArray;
  void * p2 = (void *)(doubArray + 1);
  size = p2 - p1;

  return size;
}

pointerSize

int pointerSize() {
  double * ptrArray[10];
  double ** ptrPtr1;
  double ** ptrPtr2;
  // TODO: Write code to compute size of a pointer.
  int size;
  void * p1 = (void *)ptrArray;
  void * p2 = (void *)(ptrArray + 1);
  size = p2 - p1;

  return size;
}

changeValue

int changeValue() {
  int intArray[10];
  int * intPtr1 = intArray;
  int * intPtr2;
  // TODO: Write code to change value of intArray[5] to 351 using only
  //       intPtr1 and the + operator.
  *(intPtr1 + 5) = 351;

  return intArray[5];
}

withinSameBlock

只有地址除以64的结果是否相同即可：

int withinSameBlock(int * ptr1, int * ptr2) {
  // TODO
  int d, res, g1, g2;
  int d1, d2;
  //判断是否在同一组
  g1 = ((unsigned)ptr2) >> 6;
  g2 = ((unsigned)ptr1) >> 6;
  res = (g1 == g2);

  return res;
}

int withinArray(int * intArray, int size, int * ptr) {
  // TODO
  int res;
  res = (ptr >= intArray) && (ptr < (intArray + size));

  return res;
}

invert

编码规则

$a_{n-1}a_{n-2}\ldots a_1 a_0$

所以代码如下

int invert(int x, int p, int n) {
  // TODO
  unsigned mask;
  int res;
  mask = (~0);
  mask = mask >> (32 - n);
  mask = mask << p;
  res = (x ^ mask);

  return res;
}