std.math.big.int sqrt panic

[guidovranken]

Zig Version

zig-linux-x86_64-0.12.0-dev.1396+f6de3ec96

Steps to Reproduce and Observed Behavior

sqrt added by @mizuochik in 4422af8

Sqrt of 0

const std = @import("std");

pub fn main() !void {
    const allocator = std.heap.page_allocator;

    var a = std.math.big.int.Managed.initSet(allocator, @as(usize, 1)) catch unreachable;
    defer a.deinit();

    var res = std.math.big.int.Managed.initSet(allocator, @as(usize, 1)) catch unreachable;
    defer res.deinit();

    a.setString(10, "0") catch unreachable;

    res.sqrt(&a) catch unreachable;
}

Output:

thread 1853221 panic: integer overflow
/home/jhg/cf-zig-sqrt/zig-linux-x86_64-0.12.0-dev.1396+f6de3ec96/lib/std/math/big/int.zig:70:39: 0x21fb00 in calcSqrtLimbsBufferLen (p)
    const a_limb_count = (a_bit_count - 1) / limb_bits + 1;
                                      ^
/home/jhg/cf-zig-sqrt/zig-linux-x86_64-0.12.0-dev.1396+f6de3ec96/lib/std/math/big/int.zig:3231:52: 0x21f818 in sqrt (p)
        const needed_limbs = calcSqrtLimbsBufferLen(a.bitCountAbs());
                                                   ^
/home/jhg/cf-zig-sqrt/p/p.zig:14:13: 0x220b78 in main (p)
    res.sqrt(&a) catch unreachable;
            ^
/home/jhg/cf-zig-sqrt/zig-linux-x86_64-0.12.0-dev.1396+f6de3ec96/lib/std/start.zig:581:37: 0x21e237 in posixCallMainAndExit (p)
            const result = root.main() catch |err| {
                                    ^
/home/jhg/cf-zig-sqrt/zig-linux-x86_64-0.12.0-dev.1396+f6de3ec96/lib/std/start.zig:249:5: 0x21dd61 in _start (p)
    asm volatile (switch (native_arch) {
    ^
???:?:?: 0x0 in ??? (???)
Aborted (core dumped)

Sqrt of large value

const std = @import("std");

pub fn main() !void {
    const allocator = std.heap.page_allocator;

    var a = std.math.big.int.Managed.initSet(allocator, @as(usize, 1)) catch unreachable;
    defer a.deinit();

    var res = std.math.big.int.Managed.initSet(allocator, @as(usize, 1)) catch unreachable;
    defer res.deinit();

    a.setString(10, "136036462105870278006290938611834481486") catch unreachable;

    res.sqrt(&a) catch unreachable;
}

Output:

thread 1853271 panic: index out of bounds: index 3, len 2
/home/jhg/cf-zig-sqrt/zig-linux-x86_64-0.12.0-dev.1396+f6de3ec96/lib/std/math/big/int.zig:1975:36: 0x22927d in normalize (p)
        r.len = llnormalize(r.limbs[0..length]);
                                   ^
/home/jhg/cf-zig-sqrt/zig-linux-x86_64-0.12.0-dev.1396+f6de3ec96/lib/std/math/big/int.zig:1100:20: 0x225702 in shiftLeft (p)
        r.normalize(a.limbs.len + (shift / limb_bits) + 1);
                   ^
/home/jhg/cf-zig-sqrt/zig-linux-x86_64-0.12.0-dev.1396+f6de3ec96/lib/std/math/big/int.zig:1385:24: 0x22039b in sqrt (p)
            m.shiftLeft(m.toConst(), shift); // u must be >= ⌊√a⌋, and should be as small as possible for efficiency
                       ^
/home/jhg/cf-zig-sqrt/zig-linux-x86_64-0.12.0-dev.1396+f6de3ec96/lib/std/math/big/int.zig:3238:15: 0x21fa20 in sqrt (p)
        m.sqrt(a.toConst(), limbs_buffer);
              ^
/home/jhg/cf-zig-sqrt/p/p.zig:14:13: 0x220b78 in main (p)
    res.sqrt(&a) catch unreachable;
            ^
/home/jhg/cf-zig-sqrt/zig-linux-x86_64-0.12.0-dev.1396+f6de3ec96/lib/std/start.zig:581:37: 0x21e237 in posixCallMainAndExit (p)
            const result = root.main() catch |err| {
                                    ^
/home/jhg/cf-zig-sqrt/zig-linux-x86_64-0.12.0-dev.1396+f6de3ec96/lib/std/start.zig:249:5: 0x21dd61 in _start (p)
    asm volatile (switch (native_arch) {
    ^
???:?:?: 0x0 in ??? (???)
Aborted (core dumped)

Expected Behavior

No panics

[mizuochik]

@guidovranken Thanks for reporting. I'll fix it.

[guidovranken]

This only fixes sqrt(0), not sqrt with larger values. Please read my bug report again. There are reproducers for these two distinct issues.

[tisonkun]

@guidovranken @Vexu it's about an offset by one issue for the result take more than usize bits. I propose a fix at #17919.

[guidovranken]

Confirmed that #17919 fully resolves the issues with sqrt