Safe u64 modular multiplication

1

I am trying to perform "(a * b) % m" on u64 avoiding the multiplication overflow. I think this operation is still missing from the Rust std lib.

Online I've found this C++ code that on a 64 bit system seems to work correctly (compiled with a recent GCC):

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {
    uint64_t q;
    uint64_t r;
    asm("mulq %3;"
        "divq %4;"
        : "=a"(q), "=d"(r)
        : "a"(a), "rm"(b), "rm"(m));
    return r;
}

I have tried to convert it in Rust, but it gives me a "error: malformed inline assembly":

#![feature(asm)]

#[cfg(any(target_arch = "x86_64"))]
fn mul_mod(a: u64, b: u64, m: u64) -> u64 {
    let mut q: u64;
    let mut r: u64;
    unsafe {
        asm!("mulq $3"
             "divq $4"
             : "=a"(q), "=d"(r)
             : "a"(a), "rm"(b), "rm"(m)
             );
    }
    r
}

fn main() {}

Do you know how to fix it?

2

The semicolons are missing and Rust doesn't have string literal concatenation. This works, but only in release mode (optimizations on).

3

Oh, thank you. Why is it working only in release mode?

I am compiling this code (on Windows 64 bit, rustc 1.12.0-nightly (54c0dcfd6 2016-07-28)):

#![feature(asm)]

#[allow(unused_variables, unused_mut, unused_assignments)]
#[cfg(any(target_arch = "x86_64"))]
// Performs  (a * b) % m  in 128 bits.
fn mul_mod(a: u64, b: u64, m: u64) -> u64 {
    let mut q: u64;
    let mut r: u64; // r = a b mod m

    unsafe {
        asm!("mulq $3; divq $4;"
             : "=a"(q), "=d"(r)
             : "a"(a), "rm"(b), "rm"(m)
             );
    }

    r
}

fn main() {
    println!("{}", mul_mod(10, 300, 3));
}

If I compile without optimizations:

rustc test.rc

The code compiles and it seems to work...

But if I compile with optimizations, the Rustc seems to crash:

...>rustc -O test.rs
Assertion failed!

Program: ...\rustc.exe
File: .../bot/slave/nightly-dist-rustc-win-gnu-64/build/src/llvm/lib/CodeGen/LiveVariables.cpp, Line 133

Expression: MRI->getVRegDef(reg) && "Register use before def!"
4 
        asm!("mulq $3; divq $4;"
             : "=&{ax}"(q), "=&{dx}"(r)
             : "{ax}"(a), "r"(b), "r"(m)
             );

Seems to work with both release and debug builds. (I think LLVM is supposed to support the "a" register class in theory, but clang never uses it, so it might just be broken.)

Note that the divq will trap if the result doesn't fit into a 64-bit integer, so use carefully. (I think it's sufficient to check a < m && b < m.)

1 Like
5

Clang supports the "a" register class but LLVM doesn't. Clang will transform the constraint into "{ax}" before passing it on to LLVM. Rust on the other hand does not perform any pre-processing and passes the constraints to LLVM directly.

6

Thank you.

Right, I've seen that. So to have a "safe" mul_mod (that works with all u64 inputs) I have to add more asm instructions.