代码之家 › 专栏 › 技术社区 › user8510613

模拟JG指令(DataLab的更大)

eflags instructions assembly c

5

user8510613 · 技术社区 · 6 年前

我在做csapp的数据实验室,这个功能更强大。
这是描述

isGreater - if x > y  then return 1, else return 0
   Example: isGreater(4,5) = 0, isGreater(5,4) = 1
   Legal ops: ! ~ & ^ | + << >>
   Max ops: 24
   Rating: 3

x和y都是int类型。
所以我考虑模拟jg指令来实现它。

int isGreater(int x, int y)
{
    int yComplement = ~y + 1;
    int minusResult = x + yComplement;  // 0xffffffff
    int SF = (minusResult >> 31) & 0x1; // 1
    int ZF = !minusResult; // 0
    int xSign = (x >> 31) & 0x1; // 0 
    int ySign = (yComplement >> 31) & 0x1; // 1
    int OF = !(xSign ^ ySign) & (xSign ^ SF); // 0
    return !(OF ^ SF) & !ZF;
}

JG指令需要sf==of和zf==0。
但它不能传递特殊情况,即x=0x7fffffff(int_max),y=0x8000000(int_min)。
我这样推断:
X+Ycomplement=0xffffffff,所以sf=1,zf=0,因为xsign!=ysign,of设置为0。
那么,我的代码有什么问题,我的设置操作有问题吗?

2 回复 | 直到 6 年前

1

4

Peter Cordes 6 年前

你发现加法中有溢出 x + yComplement ,而不是在整体减法中

-INT_MIN 自身在2的补码中溢出; INT_MIN == -INT_MIN 是的。这是 the 2's complement anomaly ^1个是的。

对于任何负数(除了 INT_MIN )减 内景 是的。由此产生的加法将有符号溢出。例如 -10 + INT_MIN 溢出。

http://teaching.idallen.com/dat2343/10f/notes/040_overflow.txt 有一个用于加减运算的输入/输出符号表。溢出的情况是,输入符号相反,但结果符号匹配 y 是的。

      SUBTRACTION SIGN BITS  (for num1 - num2 = sum)
    num1sign num2sign sumsign
   ---------------------------
        0 0 0
        0 0 1
        0 1 0
 *OVER* 0 1 1 (subtracting a negative is the same as adding a positive)
 *OVER* 1 0 0 (subtracting a positive is the same as adding a negative)
        1 0 1
        1 1 0
        1 1 1

你可以直接用这个 x 和 是的 ,且仅使用 yComplement 作为获得 minusResult 是的。调整你的逻辑以匹配这个真值表。

或者你可以用 int ySign = (~y) >> 31; 剩下的代码保持不变 是的。(使用tmp保持 ~y 所以你只做一次手术 Y组件 )补语逆( ~ )不受2补体异常的影响。

脚注1 :符号/大小和一的补码有两种冗余方式来表示0,而不是一个没有反比的值。

有趣的事实:如果你做一个整数绝对值函数,你应该考虑结果 unsigned 为了避免这个问题。 int 无法表示的绝对值 内景 是的。

提高效率:

如果你使用 unsigned int ,你不需要 & 1 在一个移位之后,因为逻辑移位没有符号扩展。(另外,它还可以避免在 + 以下内容: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html )中。

然后(如果你用 uint32_t ,或 sizeof(unsigned) * CHAR_BIT 你将得到一个安全的、可移植的2的补码比较实现。(负数的有符号移位语义是在c中定义的实现)我认为您将c用作位操作的一种伪代码,并且对实际编写可移植的实现不感兴趣,这很好。您的工作方式将在普通CPU上的普通编译器上运行。

或者你可以用 & 0x80000000 把高位保持在适当的位置(但是你必须把你的 ! 结果)。

这只是实验室的限制,不能使用无符号或任何大于0xFF(255)的常量

好吧,所以你没有逻辑右移的权限。不过,你最多需要一个 &1 是的。在你只关心低位的情况下使用数字是可以的,但是在其他的情况下使用的是垃圾。

你最终会的 & !ZF ,或者 &0 或&1 . Thus, any high garbage in 的被抹去了。

你也可以推迟 >> 31 直到把两个数字串在一起。

这是一个有趣的问题,我想优化自己:

// untested, 13 operations
int isGreater_optimized(int x, int y)
{
    int not_y = ~y;

    int minus_y = not_y + 1;
    int sum = x + minus_y;

    int x_vs_y = x ^ y;       // high bit = 1 if they were opposite signs: OF is possible
    int x_vs_sum = x ^ sum;   // high bit = 1 if they were opposite signs: OF is possible

    int OF = (x_vs_y & x_vs_sum) >> 31;   // high bits hold garbage
    int SF = sum >> 31;

    int non_zero = !!sum;              // 0 or 1
    return (~(OF ^ SF)) & non_zero;      // high garbage is nuked by `& 1`
}

注意使用 ~ 而不是 ! 反转具有高垃圾的值。

与sf分离的计算看起来还是有一定的冗余,但实际上两次和的异或并没有消除。 x ^ sum 是的输入 & ,然后我们用sum异或运算。

不过,我们可以推迟转换,我通过避免额外的反转找到了一些更优化的方法。 这是11次行动

// replace 31 with  sizeof(int) * CHAR_BIT  if you want.  #include <limit.h>
// or use int32_t

int isGreater_optimized2(int x, int y)
{
    int not_y = ~y;

    int minus_y = not_y + 1;
    int sum = x + minus_y;
    int SF = sum;             // value in the high bit, rest are garbage

    int x_vs_y = x ^ y;       // high bit = 1 if they were opposite signs: OF is possible
    int x_vs_sum = x ^ sum;   // high bit = 1 if they were opposite signs: OF is possible
    int OF = x_vs_y & x_vs_sum;   // low bits hold garbage

    int less = (OF ^ SF);
    int ZF   = !sum;               // 0 or 1
    int le   = (less >> 31) & ZF;  // clears high garbage
    return  !le;                   // jg == jnle
}

我想知道是否有编译器能看穿这本手册,并将其优化为 cmp edi, esi / setg al ,但是没有这样的运气:/我想这不是他们所寻找的模式,因为代码可以被编写为 x > y 倾向于是这样写的:p

但不管怎样,这里 the x86 asm output from gcc and clang on the Godbolt compiler explorer.

2

3

Sander De Dycker 6 年前

假设二者是互补的, INT_MIN 的绝对值不能表示为 int 是的。所以, yComplement == y (即仍然是否定的),以及 ySign 是 1 而不是想要的 0 是的。

你可以计算出 y 像这样(在代码中尽可能少地更改):

int ySign = !((y >> 31) & 0x1);

要获得更详细的分析和更优化的选择,请检查 Peter Cordes' answer 是的。