How do I get a positive modulo on a negative dividend

Question

I am trying to get a modulo-n (0 < n) in the range [0 ... n-1].

The instruction idiv n divides EDX:EAX (64 bits) by n, and leaves
EAX=quotient, EDX=remainder. (n is a register in my code)

My problem is that when the content of EDX:EAX is negative, I get a negative result in EDX.

The simplest solution I found was:

cdq            ; extend EAX sign bit to EDX
idiv n         ; edx = (possibly neg.) remainder
add edx, n
mov eax, edx   ; eax = remainder + n
cdq
idiv n         ; edx = positive remainder

Is there a cleaner/easier/quicker way to get the positive remainder?

Answer 1

-5 mod 3 = -2 (remainder, -1 quotient)

patched remainder: -2 + 3 = +1, that's what you want, right?

Quotient is then -1 - 1 = -2.

Verification: -2 * 3 + +1 = -5

cdq            ; extend EAX sign bit to EDX
idiv n         ; edx = (possibly neg.) remainder
mov eax, edx   ; eax = copy of remainder
add edx, n     ; negative remainder modified to positive one (for --quotient)
               ; when going from negative to positive, CF will be set (unsigned overflow)
cmovc eax,edx  ; when CF, load eax with modified remainder
; eax = to-be-positive-adjusted remainder

I didn't verify it in debugger, and I merely woke up, so test it first.

Answer 2

The kind of division that produces a non-negative modulo is called Euclidean division.

For C implementations and more background, see Division and Modulus for Computer Scientists. (also related: What's the difference between “mod” and “remainder”?).

This is a special case, where we know the divisor is positive, which allows the faster implementation suggested by Ped7g. It's probably optimal or at least close to it.

Interestingly, we can write it in C in a way that compiles to the same asm as Ped7g's hand-written version (or close to it, depending on gcc vs. clang). See it on the Godbolt compiler explorer.

// https://stackguides.com/questions/40861023/how-do-i-get-a-positive-modulo-on-a-negative-dividend
// uses unsigned carry to detect when a negative 2's complement integer wrapped to non-negative
long modE_positive_divisor_2s_complement( long D, long d )
{
  long r = D%d;

  unsigned long tmp = (unsigned long)r + (unsigned long)d;
  // detect carry by looking for unsigned wraparound:
  // that means remainder was negative (not zero), so adding the (non-negative) divisor is what we need
  r = (tmp < (unsigned long)r) ? (long)tmp : r;

  return r;
}

With clang3.9 -O3, we get:

    mov     rax, rdi
    cqo
    idiv    rsi
    add     rsi, rdx
    cmovae  rsi, rdx
    mov     rax, rsi
    ret

gcc6.2 uses an extra CMP before the CMOV :(

On Godbolt, I included the original general-case C function and a version that tells the compiler to assume positive d (using __builtin_unreachable()). For the latter, gcc does about as well as with this, using a test rdx,rdx / cmovs to do the conditional add.

It works identically for 32-bit vs. 64-bit long (with EAX instead of RAX, etc.), so use int32_t if you care about performance and don't need 64-bit integers. (idiv r64 is much slower than idiv r32).