4

I'm learning about assembly code in "Computer Systems- A Programmer's Perspective", and I encountered the following example:

In the following C function, we have left the definition of operation OP incomplete:

#define OP

/* Unknown operator */
short arith(short x) {
    return x OP 16;
}

When compiled, gcc generates the following assembly code:

arith:
  leaq    15(%rdi), %rax
  testq   %rdi, %rdi
  cmovns  %rdi, %rax
  sarq    $4, %rax
  ret

What operation is OP?

Later, the book gives the following answer:

The operator is ‘/’. We see this is an example of dividing by a power of 4 by right shifting (see Section 2.3.7). Before shifting by k = 4, we must add a bias of (2^k) − 1 = 15 when the dividend is negative.

I get that the compiler is using an optimization here, creating a temporary variable equal to x + 15, and conditionally re-setting that variable back to x if x is less than zero. What I'm wondering is why it's necessary to use a bias in the first place. What would happen if the code left out the first 3 assembly steps, like so?

  sarq    $4, %rax
  ret

I think the answer is that we need to get rid of the twos-complement sign bits from a negative number in order to arrive at the correct answer of zero. For example, if x = -12 (i.e. 11110100), and we wanted to divide by 4, then shifting right by 4 bits without adding the bias first would equal 11111111 (or -1 in decimal form), which is not the expected answer of 0 that I'd expect from dividing -12 by 16. Instead, we add 15 to -12 to get 3 (aka 00000011), which we can then shift right by 4 bits to get 00000000, aka the correct answer of 0 in decimal form.

Is the above explanation correct? Or am I missing the mark when it comes to how and why a bias is used?

UPDATE- apparently the example assembly code in the book I'm using isn't correct. Here's the correct assembly:

    arith:
        testw   %di, %di
        leal    15(%rdi), %eax
        cmovns  %edi, %eax
        sarw    $4, %ax
        ret

My larger question about why the bias is needed still stands. Is it because shifting a negative number without first adding the bias produces the incorrect result that I mentioned?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Richie Thomas
  • 3,073
  • 4
  • 32
  • 55
  • 2
    That example is broken, the return-value register is RAX not RBX. It's also definitely not going to use 64-bit operand-size for `short`. https://godbolt.org/z/fq6Mf6 shows the actual asm output. Was this from the global edition of CS:APP? It's known to have some broken practice problems, modified by people who aren't the authors. See [CS:APP example uses idivq with two operands?](https://stackoverflow.com/q/57998998) for details of how this happened. – Peter Cordes Dec 02 '20 at 21:16
  • Makes sense, I was a bit confused by the use of `%rbx` as well. I'll fix the example in the question so that it's more clear. – Richie Thomas Dec 02 '20 at 21:18
  • 1
    See my edit to my previous comment, that wasn't the only problem. Probably best to leave the CS:APP code untouched, or remove it entirely and use actual GCC output. Except the book has a half-assed description of the asm. Your question is still answerable, the correct implementation still involves +=15 to round up (towards zero) instead of towards -inf, to implement signed division semantics. – Peter Cordes Dec 02 '20 at 21:21
  • It's only correct if you define it to be correct :) It's just a difference between how C does division and how the shift does it. If you expect the remainder to be always non-negative then the shift is correct. – Jester Dec 02 '20 at 21:22
  • @PeterCordes yes it's from the 3rd Global Edition of CS:APP. Thanks for the heads' up. RE: "It's also definitely not going to use 64-bit operand-size for short"- do you mean the instruction suffixes in the example should be "w" instead of "q"? – Richie Thomas Dec 02 '20 at 21:26
  • The very next thing in that comment was a link to actual GCC output. Go see for yourself how it uses 16 and 32-bit operand sizes for efficiency and correctness. – Peter Cordes Dec 02 '20 at 21:30
  • @PeterCordes yes I saw that link, I see what the Godbolt code does, and I see the difference in suffixes between the example I gave and the Godbolt code. I'm wondering if this difference is what you were referring to in your 2nd point. I take it from your response that this is indeed what you meant. – Richie Thomas Dec 02 '20 at 21:31
  • Oh, yes, `q` is 64-bit (quad-word) operand-size, and it's not using it because `short` isn't that size. To get the low 16 bits correct, the arithmetic right shift *must* have its operand-size match the C type, because it treats the sign bit specially. Different operand-sizes would of course take a different bit as the sign bit. The actual `w` suffix on the instructions is redundant, though; the 16-bit register name is the important part (and will imply the operand-size if you omit a suffix). – Peter Cordes Dec 02 '20 at 21:38

2 Answers2

2

Right arithmetic shifting negative values represented using two's complement performs integer division by a power of 2 with rounding toward negative infinity. This is not the semantics of the integer division in C where rounding must be performed toward 0.

In order to implement signed division by 16, your compiler biasses the numerator by 15 if it is negative and performs an arithmetic right shift by 4:

arith:
    testw   %di, %di           // testing numerator
    leal    15(%rdi), %eax     // computing numerator+15 into %eax, flags unchanged
    cmovns  %edi, %eax         // conditional move depending if numerator was negative
    sarw    $4, %ax            // arithmetic right shift by 4 positions
    ret

The code is equivalent to this:

short div16(short num) {
    return (num < 0 ? num + 15 : num) >> 4;
}
chqrlie
  • 131,814
  • 10
  • 121
  • 189
2

As mentioned earlier in rounding section of book default behavior of shifting is rounding down but in C dividing the number result in rounding towards zero. This amounts to rounding up in case of negative numbers. Thus, bias is needed to be added beforehand for negative number to result in consist behavior with C. Having 2^k - 1 (k ones) as bias value leaves no effect if number has k zeros on right but will round the number up if there is one at any place in k digits.

Ravi Bhat
  • 19
  • 3