1

I have written a little c++ function on godbolt.org and I am curious about a certain line inside the assembly. Here is the function:

unsigned long long foo(uint64_t a, uint8_t b){
    // unsigned long long fifteen = 15 * b;
    // unsigned long long result  = a + fifteen;
    // unsigned long long resultfinal = result / 2;
    // return resultfinal;

    return (a+(15*b)) / 2;
}

The generated assembly:

rsb     r2, r2, r2, lsl #4
adds    r0, r2, r0
adc     r1, r1, #0
lsrs    r1, r1, #1
rrx     r0, r0

Now I dont understand why the line with the ADC instruction happens. It adds 0 to the high of the 64 bit number. Why does it do that?

Here is the link if you want to play yourself: Link to assembly

artless noise
  • 21,212
  • 6
  • 68
  • 105
Florent
  • 111
  • 10
  • 6
    Adding carry from previous op – stark Feb 23 '22 at 21:56
  • When you zero-extend `15*uint8_t` to 64-bit, the high half is a constant zero. – Peter Cordes Feb 23 '22 at 23:39
  • b is 8bit wide, and 15*b is 12bit wide at max. in other words, the maxmum value to add to the higher 32bit is 1 at max. If I wrote this in assembly, I'd use `addcs r1, r1, #1` instead of the `adc`, but the compiler follows the standard protocol which is `adc`. - nothing bad in that at all. except for the confusion it caused to you – Jake 'Alquimista' LEE Feb 24 '22 at 09:10
  • 1
    [gcc is generating](https://godbolt.org/z/vYxzGqYsY) really horrible code here. gcc seems paranoid about `15*b` overflowing and requires intermediate registers to try and deal with it. – artless noise Mar 02 '22 at 15:03

1 Answers1

1

The arm32 is only 32 bits. The value 'a' is 64bits. The instructions that you are seeing are to allow computations of sizes larger than 32bits.

rsb     r2, r2, r2, lsl #4   # 15*b -> b*16-b
adds    r0, r2, r0           # a+(15*b) !LOW 32 bits! could carry.
adc     r1, r1, #0           # add a carry bit to the high portion
lsrs    r1, r1, #1           # divide high part by 2; (a+(15*b))/2
rrx     r0, r0               # The opposite of add with carry flowing down.

Note: if you are confused by the adc instruction, then the rrx will also be confusing? It is a 'dual' of the addition/multiplication. For division you need to take care of underflow in the higher part and put it in the next lower value.

I think the important point is that you can 'carry' this logic to arbitrarily large values. It has applications in cryptography, large value finance and other high accuracy science and engineering applications.

See: Gnu Multi-precision library, libtommath, etc.

artless noise
  • 21,212
  • 6
  • 68
  • 105
  • 2
    Subtraction propagates borrow purely from low to high. High bits do not affect the result in the low N bits, unlike division or right shift. That's why subtraction can be implemented in a binary adder-subtractor by inverting one input and feeding in a carry-in to the low bit, like add-with-carry. https://en.wikipedia.org/wiki/Adder%E2%80%93subtractor / [Which 2's complement integer operations can be used without zeroing high bits in the inputs, if only the low part of the result is wanted?](https://stackoverflow.com/q/34377711) – Peter Cordes Mar 02 '22 at 14:56
  • Thanks @PeterCordes; that is a good technical point. Also the multiple by larger values will cause more than a carry. You need almost double the storage unless you have range analysis. I was just trying to get across the thought that `Z mod 2^n` groups do not map to the full integer group and you need to support it with different types of overflow/underflow handling. So the `adc` is the tip of the iceberg and hopefully the OP can learn a lot from this question. – artless noise Mar 06 '22 at 14:32