Compiler Explorer

Source code

// 右タブ: Intel x86_64, ARM aarch64 環境向けの最適化コンパイル結果

pub fn udiv3(x: u64) -> u64 {
    x / 3
}
pub fn udiv3_shim(x: u64) -> u64 {
    ((x as u128) * (((1u128 << 65) - 1) / 3 + 1) >> 65) as u64
}

pub fn udiv1e8(x: u64) -> u64 {
    x / 100000000
}
pub fn udiv1e8_shim(x: u64) -> u64 {
    ((x as u128) * (((1u128 << 90) - 1) / 100000000 + 1) >> 90) as u64
}

pub fn udiv7(x: u64) -> u64 {
    x / 7
}
pub fn udiv7_shim(x: u64) -> u64 {
    let t = ((x as u128) * (((1u128 << 67) - 1) / 7 + 1 - (1u128 << 64)) >> 64) as u64;
    (((x - t) >> 1) + t) >> 2
}

// 2^128 未満の整数 x の入力に対して floor(x / 10^32), (x mod 10^32) を計算
pub fn udivrem_1e32(x: u128) -> (u64, u128) {
    // (z0, z1) = (floor(x / 10^32), x mod 10^32)
    // floor((2^128)/(10^32)) = 3402823
    let mut z0 = ((((x >> 64) as u64 as u128) * 3402823) >> 64) as u64;
    let mut z1 = (x - (z0 as u128) * 100000000000000000000000000000000);
    if let Some(zt) = z1.checked_sub(100000000000000000000000000000000) {
        z1 = zt;
        z0 += 1;
    }
    (z0, z1)
}

// 10^32 未満の整数 x の入力に対して floor(x / 10^16), (x mod 10^16) を計算
pub fn udivrem_1e16_less1e32(x: u128) -> (u64, u64) {
    // must be x < 10^32
    debug_assert!(x < 100000000000000000000000000000000);
    // (z0, z1) = (floor(x / 10^16), x mod 10^16)
    // floor((2^107)/(10^16)) = 16225927682921336
    let mut z0 = ((((x >> 43) as u64 as u128) * 16225927682921336) >> 64) as u64;
    let mut z1 = (x - (z0 as u128) * 10000000000000000) as u64;
    if let Some(zt) = z1.checked_sub(10000000000000000) {
        z1 = zt;
        z0 += 1;
    }
    (z0, z1)
}

// 10^24 未満の整数 x の入力に対して floor(x / 10^16), (x mod 10^16) を計算
pub fn udivrem1e16_less1e24(x: u128) -> (u64, u64) {
    // must be x < 10^24
    debug_assert!(x < 1000000000000000000000000);
    // (z0, z1) = (floor(x / 10^16), x mod 10^16)
    // ceil(2^115 / 10^16) = ceil(2^99 / 5^16) = 4153837486827862103
    let z0 = (((x >> 16) as u64 as u128) * 4153837486827862103 >> 99) as u64;
    let z1 = (x - (z0 as u128) * 10000000000000000) as u64;
    (z0, z1)
}