Juanito Perez Juanito Perez - 1 month ago 13
C Question

Higher part of multiply and division in C or C++?

When I multiply a pair of 4 bytes integers in assembly, the lower part of the result is in EAX and the higher part in EDX. If I am in C or C++ and I want to get the higher part, is it possible whithout use of inline assembly?

Is in the same way possible to get the integer division result from EAX and the modulus result from EDX without repeating the division in C or C++? I actually only know to do first

a/b
and then
a%b
, while in assembler both results are given in the same operation.

Answer

You can do it easily in C this way:

#include <stdint.h>

uint32_t a, b;  // input
uint64_t val = (uint64_t)a * b;
uint32_t high = val >> 32, low = val;

Leave it to the compiler to produce the best possible code. Modern optimizers are really good at it. Hand coded assembly often looks better but performs worse.

As commented by Pete Becker, the above relies on availability of the types uint32_t and uint64_t. If you insist on die hard portability (say you are programming on a DS9K), you may instead use the types uint_least32_t and uint_least64_t or uint_fast32_t and uint_fast64_t that are always available under C99, but you need an extra mask, that will be optimized out if not required:

#include <stdint.h>

uint_fast32_t a, b;  // input
uint_fast64_t val = (uint_fast64_t)a * b;
uint_fast32_t high = (val >> 32) & 0xFFFFFFFF, low = val & 0xFFFFFFFF;

Regarding division, you can use the C99 library functions div, ldiv or lldiv to perform a signed division and remainder operations in one call. The division will be implemented in one operation if possible on the target architecture for the specific operand types.

It may be more efficient to write both expressions and rely on the compiler to detect the pattern and produce code that uses a single IDIV opcode:

struct divmod_t { int quo, rem; };
struct divmod_t divmod(int num, int denom) {
    struct divmod_t r = { num / denom, num % denom };
    return r;
}

Testing on Matt Godbolt's compiler explorer shows no current compiler able to do this.

Yet you can turn one of these divisions into a multiplication for faster operation:

struct divmod_t { int quo, rem; };
struct divmod_t divmod2(int num, int denom) {
    struct divmod_t r;
    r.quo = num / denom;
    r.rem = num - r.quo * denom;
    return r;
}

Note that the above functions do not check for potential overflow, which results in undefined behavior. Overflow occurs if denom = 0 and if num = INT_MIN and denom = -1.

Comments