aatch / ramp Goto Github PK

View Code? Open in Web Editor NEW

262.0 262.0 38.0 4.54 MB

RAMP - Rust Arithmetic in Multiple Precision

License: Apache License 2.0

Rust 98.51% Assembly 1.49%

bignum

ramp's People

Contributors

Stargazers

Watchers

ramp's Issues

ll::test::test_divrem fails sporadically

On my machine (x86_64, Arch Linux, grsecurity kernel version 4.0.4), ll::test::test_divrem fails sporadically with things like

thread 'll::test::test_divrem' panicked at 'assertion failed: `(left == right)` (left: `[13182838137603728971, 5708230739161860554, 3, 1]`, right: `[1, 3, 4, 1]`)', src/ll/mod.rs:497

Running the test binary through valgrind, I see lots of

==20599== Conditional jump or move depends on uninitialised value(s)
==20599==    at 0x11D32A: ll::addsub::sub_n::hffdbcc24b72e3a8dLda (addsub.rs:71)
==20599==    by 0x12354F: ll::div::sb_div::h35b128adc06803d5nRa (div.rs:239)
==20599==    by 0x1223BE: ll::div::divrem::h0b3da023be4cb42d7La (div.rs:192)
==20599==    by 0x138E53: ll::test::test_divrem::heb2cd3321ec3b338OZd (mod.rs:494)
==20599==    by 0x16BADB: boxed::F.FnBox$LT$A$GT$::call_box::h10806636898263112044 (in /home/jonathan/coding/general/ramp/target/debug/ramp-5a611b79a68508d5)
==20599==    by 0x16EBD7: boxed::F.FnBox$LT$A$GT$::call_box::h7348684160606361188 (in /home/jonathan/coding/general/ramp/target/debug/ramp-5a611b79a68508d5)
==20599==    by 0x16C2C9: rt::unwind::try::try_fn::h13513740954489387225 (in /home/jonathan/coding/general/ramp/target/debug/ramp-5a611b79a68508d5)
==20599==    by 0x1A16C8: rust_try_inner (in /home/jonathan/coding/general/ramp/target/debug/ramp-5a611b79a68508d5)
==20599==    by 0x1A16B5: rust_try (in /home/jonathan/coding/general/ramp/target/debug/ramp-5a611b79a68508d5)
==20599==    by 0x196F07: rt::unwind::try::inner_try::hb6f04bd1baacc20eKnw (in /home/jonathan/coding/general/ramp/target/debug/ramp-5a611b79a68508d5)
==20599==    by 0x16C4FA: boxed::F.FnBox$LT$A$GT$::call_box::h6754105881859822973 (in /home/jonathan/coding/general/ramp/target/debug/ramp-5a611b79a68508d5)
==20599==    by 0x19B391: sys::thread::Thread::new::thread_start::h285dd80d49b81cf50xv (in /home/jonathan/coding/general/ramp/target/debug/ramp-5a611b79a68508d5)

which might be the cause. It's possible that this isn't ramp's fault , however, as I also see a Conditional jump or move depends on uninitialised value(s) in fs::Path.PathExt::exists before anything else.

Some Questions

Hey

I looked a little bit around at the source code and thought about all that unsafe pointer usage.

Why is that and why not using slices that also carry pointer and length information? Is this a port of some C library? Performance reasons?

Secondly, I tried to understand how divmod works, but no chance by just looking at it. Can you give me a hint how the algorithm is called or where to search for more information?

I'm more a of rust beginner, but I maybe could contribute some things. I thought of three things:

Converting the /* */ comments into proper /// comments, so that they get compiled to the docs and the gh-pages.
#6 From byte conversion
#22 (and using usize for all sizes)

@Aatch Do you approve? Do you have time to review PRs?

ll::div::divrem_1 has possibly extraneous pointer bounds checks

#48 introduces several guards like if qp > qp_lo { qp = qp.offset(-1) } to divrem_1. A refactoring of that function could make them unnecessary.

Allow more aggressive reusing of existing allocations

Currently there's several methods that do from-scratch internal allocations, such as divmod, pow and square. It would be nice if there was a way to use this functionality in a way that can reuse temporaries, e.g.

/// computes `a/b` setting `self` to the quotient and `rem` to the remainder
fn divmod_from(&mut self, rem: &mut Int, a: &Int, b: &Int);

/// sets `self` to `a**pow`
fn pow_from(&mut self, a: &Int, pow: u32)

etc.

This applies to functions like add too, since something like t = &a + &b has to allocate, but could be written as t.add_from(&a, &b), and multiplication is even worse: t = a * b is likely to allocate, but the temporary t may be large enough (e.g. if its a temporary being used for multiple multiplications in a loop), so t.mul_from(&a, &b) would be better. (Notably, one can avoid the allocations by doing something like t.clone_from(&a); t *= &b, but this pays the O(n) cost of a memcpy and so isn't so great.)

(The _from naming scheme is purely hypothetical, and just so I can write some examples here.)

Improve GCD performance

Rationals rely pretty heavily on the GCD for either calculating the LCM or reducing the rational. Initial benchmarks show that the GCD is a large proportion of the time for addition and subtraction of rationals.

According perf, GCD is ~90% of the time for the rationals benchmarks.

usage of `usize`

It seems that ramp abuses usize as a default unsigned integer in a few places. For example, in examples/factorial.rs it makes more sense to use a fixed-size integer (u32 or u64). Also, the operators are usually overloaded for usize instead of u32 or u64.

Use qemu to test on more architectures

E.g. libc tests on a wide variety on travis, via qemu.

cc #55.

Subtraction is backward on non-Ints

A test added to int.rs:

    #[test]
    fn int_sub() {
        let l : Int = "100".parse().unwrap();
        let a : Int = "99".parse().unwrap();
        assert_mp_eq!(&l - 1, a);
    }

Fails:

---- int::test::int_sub stdout ----
    assertion failed: &l - 1 == a
thread 'int::test::int_sub' panicked at '101 != 99', src/int.rs:2972

Float Support

I would like to know the status of float support, I have found a project called float, but is has not been updated since 2015, against ramp .2: float

Currently, I am using Bignumber.js, and an eval.js to use an eval, basically I just pass it an expression. My numbers are very large, and Floating point is not accurate enough. My App is going to be a WebAssembly app, and I would like to do it all in rust, currently I am using Qt.

I need to be able to fix the decimal places in a float, and not the precision, I am looking for a way to do this in rust, is this possible now?

`let x = mem::replace(self, Int::zero()); *self = ...` pattern seems to result in very poor code-gen

For instance, this is the contents of shl_assign:

impl ShlAssign<usize> for Int {
    #[inline]
    fn shl_assign(&mut self, other: usize) {
        let this = std::mem::replace(self, Int::zero());
        *self = this << other;
    }
}

And this is its assembly:

_ZN3int13_$LT$impl$GT$10shl_assign20h9a00eefbb5e99e3aTafE:
    pushq   %rbx
    subq    $48, %rsp
    movq    %rsi, %rax
    movq    %rdi, %rbx
    movq    (%rbx), %rcx
    movq    8(%rbx), %rdx
    movq    %rcx, (%rsp)
    movl    %edx, 8(%rsp)
    shrq    $32, %rdx
    movb    16(%rbx), %cl
    movq    $1, (%rbx)
    movl    $0, 8(%rbx)
    movl    $0, 12(%rbx)
    movb    $-44, 16(%rbx)
    movl    %edx, 12(%rsp)
    movb    %cl, 16(%rsp)
    movb    23(%rbx), %cl
    movb    %cl, 23(%rsp)
    movw    21(%rbx), %cx
    movw    %cx, 21(%rsp)
    movl    17(%rbx), %ecx
    movl    %ecx, 17(%rsp)
    leaq    24(%rsp), %rdi
    leaq    (%rsp), %rsi
    movq    %rax, %rdx
    callq   _ZN3int13_$LT$impl$GT$3shl20hc829f8e5c8476956r6eE@PLT
    movq    40(%rsp), %rax
    movq    %rax, 16(%rbx)
    movups  24(%rsp), %xmm0
    movups  %xmm0, (%rbx)
    addq    $48, %rsp
    popq    %rbx
    retq

(Why are there _movb_s in there?)

The other way to share code is to write the non-Assign versions in terms of the Assign versions, which seems to generate better code and so hence it may be better to try to use this pattern where possible, e.g.

impl<'a> BitAnd<Limb> for Int {
    type Output = Int;

    fn bitand(mut self, other: Limb) -> Int {
        self &= other;
        self
    }
}

_ZN3int13_$LT$impl$GT$6bitand20hb4c960ade11a09ccRsfE:
    pushq   %r15
    pushq   %r14
    pushq   %rbx
    movq    %rdx, %rax
    movq    %rsi, %r15
    movq    %rdi, %rbx
    xorl    %edx, %edx
    xorl    %ecx, %ecx
    movq    %r15, %rdi
    movq    %rax, %rsi
    callq   _ZN3int10bitop_limb20h0a6a37ca86ca46f2AofE@PLT
    movq    16(%r15), %rax
    movq    %rax, 16(%rbx)
    movups  (%r15), %xmm0
    movups  %xmm0, (%rbx)
    movq    %rbx, %rax
    popq    %rbx
    popq    %r14
    popq    %r15
    retq

Illformed giraffe

Cargo.toml:

...

[dependencies]
ramp = "0.3.12"

Code:

extern crate ramp;

use ramp::Int;

static GIRAFFE: &str = 
"
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000001000000000000000000000000000000000000000000
0000000000000000000011000000000000000000000000000000000000000000
0000000000000000000111000000000000000000000000000000000000000000
0000000000000000001111100000000000000000000000000000000000000000
0000000000000000011111100000000000000000000000000000000000000000
0000000000000000011111110000000000000000000000000000000000000000
0000000000000000111111110000000000000000000000000000000000000000
0000000000000000100001111000000000000000000000000000000000000000
0000000000000000000000111000000000000000000000000000000000000000
0000000000000000000000111100000000000000000000000000000000000000
0000000000000000000000011110000000000000000000000000000000000000
0000000000000000000000011110000000000000000000000000000000000000
0000000000000000000000001111000000000000000000000000000000000000
0000000000000000000000001111100000000000000000000000000000000000
0000000000000000000000000111110000000000000000000000000000000000
0000000000000000000000000111111000000000000000000000000000000000
0000000000000000000000000011111110000000000000000000000000000000
0000000000000000000000000011111111100000000000000000000000000000
0000000000000000000000000001111111111000000000000000000000000000
0000000000000000000000000001111111111100000000000000000000000000
0000000000000000000000000000111111111111000000000000000000000000
0000000000000000000000000000011111111111111000000000000000000000
0000000000000000000000000000011111111111111110000000000000000000
0000000000000000000000000000011111111111111111000000000000000000
0000000000000000000000000000011111111111111111100000000000000000
0000000000000000000000000000011111111111111111100000000000000000
0000000000000000000000000000011111111111111111110000000000000000
0000000000000000000000000000011111111111111111110000000000000000
0000000000000000000000000000001111111111111111110000000000000000
0000000000000000000000000000001111111111111111110000000000000000
0000000000000000000000000000001111000011111111100000000000000000
0000000000000000000000000000001111000001111111100000000000000000
0000000000000000000000000000001111000000111111100000000000000000
0000000000000000000000000000011111000000111111100000000000000000
0000000000000000000000000000011011000000011011100000000000000000
0000000000000000000000000000011011000000011101110000000000000000
0000000000000000000000000000110011000000011101110000000000000000
0000000000000000000000000000110011000000011100111000000000000000
0000000000000000000000000000110011000000011100110000000000000000
0000000000000000000000000000110011000000011000110000000000000000
0000000000000000000000000000011001000000010000110000000000000000
0000000000000000000000000000001001000000110000110000000000000000
0000000000000000000000000000000111000000100000110000000000000000
0000000000000000000000000000000111000001100000110000000000000000
0000000000000000000000000000000011000011000000110000000000000000
0000000000000000000000000000000011000011000000110000000000000000
0000000000000000000000000000000011100110000000110000000000000000
0000000000000000000000000000000011100110000000110000000000000000
0000000000000000000000000000000010100110000000100000000000000000
0000000000000000000000000000000110000000000001100000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
";

fn main() {
    let input: String = GIRAFFE.chars()
        .filter(|c| !c.is_whitespace())
        .collect();

    let x = Int::from_str_radix(&input, 2).unwrap();
    println!("{}", x);
}

Output:

$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.0 secs
     Running `target/debug/illformed-giraffe`
thread 'main' panicked at 'assertion failed: self.well_formed()', /home/d34d10cc/.cargo/registry/src/github.com-1ecc6299db9ec823/ramp-0.3.12/src/int.rs:314:9
note: Run with `RUST_BACKTRACE=1` for a backtrace.

Expected output:

342581792649127676198127791406119644054852809184750511204770992210601825938383173228625368612512343524580568135765381129832784929140287102447656231670490278371618738040053550924844754083137995849927287014555199009052294292243605111352278964229602623894816760629354416193979550552423279842373621548435137856781153105076831681645952473068169294190544029391463758663828828100567003458546392021905815042131115480711892076216081858013250696070743624005842779807059777397154653840706692288630135185563366228931093496037459868457738024280865863648682544327375771172685872176976999577303715645442779935499071380556380855234358517399907184246818275843840363379983214925406281243183361618849192180391506653641933784053451121171160334712857092937535606122822893204604775038632348974223351004456787673186165100098223897371450275291114458983950607846718107603195397991880820766444935587675531082421404505700110617860358142315360174185418283092141238404865012380329781867103175076882601367389664213176688432343205501275425887396821357210158983064167712232404771958406106398750988506833703615072967113834496

Add lcm and gcd functions

[Feature Request] Implement From trait for i128 and u128

Just for completeness sake 😄

Would it be as simple as putting i128 in the impl_from_prim!(signed i8, i16, i32, i64, isize); and u128 in the impl_from_prim!(unsigned u8, u16, u32, u64, usize);?

No longer compiles

Maintenance on open source stuff is tough, so while I open this issue I also understand that it might not be possible to solve these problems right away and I'm happy to help with a PR if someone can point me in the right direction.

It seems that this library relies on traits in the std and heap libraries that have since been made unstable or deprecated, and as a result it doesn't compile

Size calculation in pub fn to_str_radix

Here, num_base_digits is called with size()-1:

https://github.com/Aatch/ramp/blob/master/src/int.rs#L275

So if the Int has one limb, num_base_digits is called with n=0, that will cause return 1 independent of base.

https://github.com/Aatch/ramp/blob/master/src/ll/base.rs#L48

I just found another related problem, but that would better be part of another issue.

Infinite loop on ARM

Trying to run the multiply example from zcdziura/pumpkin on ARM Linux, never fnishes, not even getting to the first println. (the example takes just 12s on x86)

Letting it run for a while produces the following profile:

--------------------------------------------------------------------------------
           Ir 
--------------------------------------------------------------------------------
5,158,779,308  PROGRAM TOTALS

--------------------------------------------------------------------------------
           Ir  file:function
--------------------------------------------------------------------------------
1,097,181,200  /ramp-0.2.4/src/ll/limb.rs:ramp::ll::limb::mul::h42f9717ba7a0c591 [/pumpkin/target/release/examples/multiply]
  822,885,900  /src/libcore/num/mod.rs:ramp::ll::limb::mul::h42f9717ba7a0c591
  680,088,987  /ramp-0.2.4/src/ll/limb.rs:ramp::ll::mul::submul_1_generic::hbeb09a870749cc21
  440,138,242  /ramp-0.2.4/src/ll/mul.rs:ramp::ll::mul::submul_1_generic::hbeb09a870749cc21 [/pumpkin/target/release/examples/multiply]
  370,224,000  /ramp-0.2.4/src/ll/limb.rs:ramp::ll::mul::addmul_1_generic::hfa83cc681e5292db
  274,295,300  /src/libcore/ops.rs:ramp::ll::limb::mul::h42f9717ba7a0c591
  263,206,125  /ramp-0.2.4/src/ll/mul.rs:ramp::ll::mul::addmul_1_generic::hfa83cc681e5292db [/pumpkin/target/release/examples/multiply]
  250,919,928  /src/libcore/ptr.rs:ramp::ll::mul::submul_1_generic::hbeb09a870749cc21
  170,022,246  /src/libcore/num/mod.rs:ramp::ll::mul::submul_1_generic::hbeb09a870749cc21
  130,156,875  /src/libcore/ptr.rs:ramp::ll::mul::addmul_1_generic::hfa83cc681e5292db
   92,556,000  /src/libcore/num/mod.rs:ramp::ll::mul::addmul_1_generic::hfa83cc681e5292db
   61,571,727  /ramp-0.2.4/src/ll/limb.rs:ramp::ll::addsub::add_n_generic::h8017fb3f696c3827
   49,425,624  /ramp-0.2.4/src/ll/div.rs:ramp::ll::div::invert_pi::h37e4002131b72562 [/pumpkin/target/release/examples/multiply]
   35,384,665  /ramp-0.2.4/src/ll/addsub.rs:ramp::ll::addsub::add_n_generic::h8017fb3f696c3827 [/pumpkin/target/release/examples/multiply]
   32,008,950  /ramp-0.2.4/src/ll/mul.rs:ramp::ll::mul::mul_basecase::h24ea3d00965ade9a [/pumpkin/target/release/examples/multiply]
   30,008,121  /build/eglibc-euxZvP/eglibc-2.19/malloc/malloc.c:_int_malloc [/lib/arm-linux-gnueabihf/libc-2.19.so]
   24,692,260  /ramp-0.2.4/src/ll/limb.rs:ramp::ll::div::divrem_3by2::h3ad1011bead13922
   23,355,848  /src/libcore/num/mod.rs:ramp::ll::div::divrem_3by2::h3ad1011bead13922
   19,817,019  /src/libcore/ptr.rs:ramp::ll::addsub::add_n_generic::h8017fb3f696c3827
   19,476,292  /build/eglibc-euxZvP/eglibc-2.19/malloc/malloc.c:_int_free [/lib/arm-linux-gnueabihf/libc-2.19.so]
   19,211,688  /build/eglibc-euxZvP/eglibc-2.19/string/../ports/sysdeps/arm/memset.S:memset [/lib/arm-linux-gnueabihf/libc-2.19.so]
   18,511,200  /ramp-0.2.4/src/ll/limb.rs:ramp::ll::mul::mul_1_generic::hb74fcfb822b9692a
   17,819,126  /ramp-0.2.4/src/ll/div.rs:ramp::ll::div::divrem_3by2::h3ad1011bead13922 [/pumpkin/target/release/examples/multiply]
   17,020,241  /ramp-0.2.4/src/ll/limb.rs:ramp::ll::addsub::sub_n_generic::h8a9a928dc6dc2db7
   15,130,058  /ramp-0.2.4/src/ll/addsub.rs:ramp::ll::addsub::sub_n_generic::h8a9a928dc6dc2db7 [/pumpkin/target/release/examples/multiply]
   14,461,875  /ramp-0.2.4/src/ll/mul.rs:ramp::ll::mul::mul_1_generic::hb74fcfb822b9692a [/pumpkin/target/release/examples/multiply]
   13,819,125  /ramp-0.2.4/src/ll/mod.rs:ramp::mem::TmpAllocator::allocate::h6d2af0ca83521b26
   10,969,176  /src/libcore/num/mod.rs:ramp::ll::div::invert_pi::h37e4002131b72562
    9,068,068  /ramp-0.2.4/src/ll/limb.rs:ramp::ll::div::divrem_1::h00ea568e6ff59101
    9,042,938  /build/eglibc-euxZvP/eglibc-2.19/malloc/malloc.c:malloc'2 [/lib/arm-linux-gnueabihf/libc-2.19.so]
    8,677,125  /src/libcore/ptr.rs:ramp::ll::mul::mul_1_generic::hb74fcfb822b9692a
    6,969,621  /src/libcore/ptr.rs:ramp::ll::addsub::sub_n_generic::h8a9a928dc6dc2db7
    6,919,952  /ramp-0.2.4/src/ll/mod.rs:ramp::ll::div::invert_pi::h37e4002131b72562
    6,916,488  /ramp-0.2.4/src/int.rs:ramp::int::Int::with_capacity::hbad52ef439589d1c'2 [/pumpkin/target/release/examples/multiply]
    6,855,740  /ramp-0.2.4/src/ll/mul.rs:ramp::ll::div::invert_pi::h37e4002131b72562
    5,944,943  ???:__udivsi3 [/lib/arm-linux-gnueabihf/libgcc_s.so.1]
    5,811,630  /ramp-0.2.4/src/ll/div.rs:ramp::ll::div::divrem_1::h00ea568e6ff59101 [/pumpkin/target/release/examples/multiply]
    4,841,424  /ramp-0.2.4/src/ll/limb.rs:ramp::ll::limb::mul::h42f9717ba7a0c591'2 [/pumpkin/target/release/examples/multiply]
    4,723,641  /ramp-0.2.4/src/ll/mod.rs:ramp::int::Int::with_capacity::hbad52ef439589d1c'2
    3,631,068  /src/libcore/num/mod.rs:ramp::ll::limb::mul::h42f9717ba7a0c591'2
    3,123,600  /build/eglibc-euxZvP/eglibc-2.19/malloc/malloc.c:free [/lib/arm-linux-gnueabihf/libc-2.19.so]
    3,085,200  /src/libcore/num/mod.rs:ramp::ll::mul::mul_1_generic::hb74fcfb822b9692a
    2,742,296  /ramp-0.2.4/src/ll/limb_ptr.rs:ramp::ll::div::invert_pi::h37e4002131b72562
    2,552,655  /src/libcore/num/mod.rs:_$LT$alloc..raw_vec..RawVec$LT$T$GT$$GT$::reserve_exact::hb7fda2cd8a63e7ac
    2,487,954  /src/libcore/num/mod.rs:ramp::ll::div::divrem_1::h00ea568e6ff59101

Probably a rustc bug, both 1.9 and 1.10 produce broken code. Any suggestions?

Problem building ramp on armv7

Trying to build ramp (through pumpkin) on a 32-bit arm platform ends in this:

Compiling ramp v0.1.9
     Running `rustc /home/odroid/.cargo/registry/src/github.com-121aea75f9ef2ce2/ramp-0.1.9/src/lib.rs --crate-name ramp --crate-type lib -C opt-level=3 -C metadata=014f6b64cb3efd27 -C extra-filename=-014f6b64cb3efd27 --out-dir /tmp/pumpkin-master/target/release/deps --emit=dep-info,link -L dependency=/tmp/pumpkin-master/target/release/deps -L dependency=/tmp/pumpkin-master/target/release/deps --extern rand=/tmp/pumpkin-master/target/release/deps/librand-a5a71c849766362c.rlib --cap-lints allow`
/home/odroid/.cargo/registry/src/github.com-121aea75f9ef2ce2/ramp-0.1.9/src/ll/limb.rs:590:24: 590:39 error: the trait `core::ops::Sub<bool>` is not implemented for the type `ll::limb::Limb` [E0277]
/home/odroid/.cargo/registry/src/github.com-121aea75f9ef2ce2/ramp-0.1.9/src/ll/limb.rs:590             let high = ah - bh - carry;
                                                                                                                  ^~~~~~~~~~~~~~~
/home/odroid/.cargo/registry/src/github.com-121aea75f9ef2ce2/ramp-0.1.9/src/ll/limb.rs:555:5: 594:6 note: in this expansion of if_cfg! (defined in /home/odroid/.cargo/registry/src/github.com-121aea75f9ef2ce2/ramp-0.1.9/src/ll/limb.rs)
/home/odroid/.cargo/registry/src/github.com-121aea75f9ef2ce2/ramp-0.1.9/src/ll/limb.rs:590:24: 590:39 help: run `rustc --explain E0277` to see a detailed explanation
error: aborting due to previous error
Could not compile `ramp`.

Caused by:
  Process didn't exit successfully: `rustc /home/odroid/.cargo/registry/src/github.com-121aea75f9ef2ce2/ramp-0.1.9/src/lib.rs --crate-name ramp --crate-type lib -C opt-level=3 -C metadata=014f6b64cb3efd27 -C extra-filename=-014f6b64cb3efd27 --out-dir /tmp/pumpkin-master/target/release/deps --emit=dep-info,link -L dependency=/tmp/pumpkin-master/target/release/deps -L dependency=/tmp/pumpkin-master/target/release/deps --extern rand=/tmp/pumpkin-master/target/release/deps/librand-a5a71c849766362c.rlib --cap-lints allow` (exit code: 101)

The problem is non-existent on 32-bit x86.

Shr mismatches primitives integers for negative values

>>'ing a primitive integer (or a GMP Mpz) will round to negative infinity, while ramp currently rounds to zero (same as division). Maybe this should be changed?

extern crate ramp;
extern crate gmp;
use ramp::Int;

fn main() {
    let x = -1;
    let shift = 1;

    let r = Int::from(x);
    let g = gmp::mpz::Mpz::from(x);
    let div = 1i32 << shift;
    println!("ramp {} {}\ngmp  {} {}\ni32  {} {}",
             &r >> shift,
             r / div,
             &g >> shift,
             g / div as u64,
             x >> shift,
             x / div);
}

ramp 0 0
gmp  -1 0
i32  -1 0

(2**64 - 1) * 264 + 264 == 1

This test fails:

#[test]
fn foo() {
    let mut ar = ((Int::from(1) << 64) - 1) << 64_usize;
    let br = Int::from(1) << 64;
    assert_eq!(ar + br, Int::from(1) << 128);
}

(I'm debugging it now.)

Possible latent memory corruption?

https://travis-ci.org/Aatch/ramp/jobs/90644821 failed in the cargo test --release section:

---- sub::usize_int stdout ----

    thread 'sub::usize_int' panicked at '[quickcheck] TEST FAILED. Arguments: (3, BigIntStr("2"))', /home/travis/.cargo/registry/src/github.com-0a35038f75765ae4/quickcheck-0.2.24/src/tester.rs:113

failures:

    sub::usize_int

But this isn't reliable (other test runs passed) and running 3 - Int::from(2) in a test by itself works fine, suggesting memory corruption, in something (probably not sub).

Junk in the cargo package source

Ramp 0.1.6 has megabytes of junk files in the source directory. (perf.data and .ll files)

This is a reminder that cargo includes all non-ignored files in your working directory when you publish — look at git status before you publish.

(I downloaded all crates.io crates and I started to grep for junk)

Int::from panics for i64::MIN

The following simple test case panics. It doesn't seem like the expected behaviour for me.

    #[test]
    fn test_i64_MIN_panick() {
        Int::from(i64::MIN);
    }

Possible memory corruption in pow(?)

Quickcheck runs will very occasionally fail with an error like

thread 'safe' panicked at 'called `Result::unwrap()` on an `Err` value: ParseIntError { kind: InvalidDigit }', ../src/libcore/result.rs:736

which appears to be caused by the &str being parsed having been corrupted (there's no way the generator will generate an incorrect digit). I managed to catch this with rr with an opt+debuginfo build, which seems to point the finger at

ramp/src/ll/mul.rs

Lines 420 to 422 in 8c66762

    
           ll::copy_incr(w_tmp.offset(ys as isize), 
        
                         wp.offset(ys as isize), 
        
                         ys);

but the optimisations mean a lot of stuff is optimised out.

The following is the exact pow call in the trace I've found. The corruption appears to occur when exp is 1 in

ramp/src/ll/pow.rs

Lines 70 to 94 in 8c66762

    
           loop { 
        
               if (exp & 1) == 1 { 
        
                   if wn > bn { 
        
                       ll::mul(scratch, wp, wn, bp, bn); 
        
                   } else { 
        
                       ll::mul(scratch, bp, bn, wp, wn); 
        
                   } 
        
                   wn = ll::normalize(scratch, wn + bn); 
        
                   ll::copy_incr(scratch, wp, wn); 
        
               } 
        
               exp >>= 1; 
        
               // Do this check before the base multiplication so we don't 
        
               // end up needing more space than necessary 
        
               if exp == 0 { 
        
                   break; 
        
               } 
        
               ll::sqr(scratch, bp, bn); 
        
               bn = ll::normalize(scratch, bn + bn); 
        
               ll::copy_incr(scratch, bp, bn); 
        
           }

extern crate ramp;
use ramp::Int;

fn parse(s: &str) -> Int {
    Int::from_str_radix(s, 16).unwrap()
}
fn main() {
    let ar = parse("3283bc9fffffb00000000000000000000000000000000005fffffffffffffffffffffffffffffffffffffffffffe700000000000000000000000000000000000000000000000000714fffff930000000000000000000000000000000000000000000000000000000000000000000005a000000000000000000000000000f93bad4358ffffffff3fff350a940000000000000102fffffffffffffffffffffffffffffffffffffffffffffffffffffffffff");
    ar.pow(5);
}

However, this doesn't seem reproduce any corruption by itself.

Backtrace:

#0  0x0000556993f51bac in ramp::ll::mul::mul_unbalanced (wp=<optimised out>, xp=<optimised out>, 
    xs=<optimised out>, yp=0x7f277684c880, ys=<optimised out>, scratch=0x7f27768b5610)
    at src/ll/mul.rs:435
#1  0x0000556993f5124d in ramp::ll::mul::mul (wp=0x7f2776844b88, xp=0x7f2776844810, xs=89, yp=0x0, ys=23)
    at src/ll/mul.rs:203
#2  0x0000556993f545a2 in ramp::ll::pow::pow (wp=<optimised out>, ap=<optimised out>, an=<optimised out>, 
    exp=1) at src/ll/pow.rs:75
#3  0x0000556993f576a5 in ramp::int::Int::pow (self=<optimised out>, exp=5) at src/int.rs:422
#4  0x0000556993e4af85 in quickcheck::pow::pow (a=BigIntStr = {...}, b=5) at tests/quickcheck.rs:180
#5  0x0000556993e449a5 in fnfn ()
    at /home/huon/.multirust/toolchains/nightly/cargo/registry/src/github.com-0a35038f75765ae4/quickcheck-0.2.24/src/tester.rs:310
#6  0x0000556993e44528 in fnfn () at ../src/libstd/thread/mod.rs:271
#7  0x0000556993e444ca in quickcheck::sys_common::unwind::try::try_fn<closure> (
    opt_closure=0x7f27ba2fbb10 "") at ../src/libstd/sys/common/unwind/mod.rs:156
#8  0x0000556993fb7869 in __rust_try ()
#9  0x0000556993fb4a1c in sys_common::unwind::try::inner_try::he2b5e2c66f0c0baaMbs ()
#10 0x0000556993e44438 in quickcheck::sys_common::unwind::try<closure> (f=closure = {...})
    at ../src/libstd/sys/common/unwind/mod.rs:126
#11 0x0000556993e44217 in fnfn () at ../src/libstd/thread/mod.rs:271
#12 0x0000556993e44d09 in quickcheck::boxed::F.FnBox<A>::call_box (self=0x7f28010ed430, args=0)
    at ../src/liballoc/boxed.rs:521
#13 0x0000556993fb9424 in sys::thread::_$LT$impl$GT$::new::thread_start::h73f43dc58e7e67e9wEw ()
#14 0x00007f28029489b4 in ?? () from /usr/bin/../lib/librrpreload.so
#15 0x00007f2801bda6aa in start_thread (arg=0x7f27ba2fc700) at pthread_create.c:333
#16 0x00007f2802403eed in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:109

I'm working on this, including trying to get a better capture, via:

while nice rr target/debug/quickcheck-d576313f0448fe02; do :; done

`Rem` is incorrect

extern crate ramp;
use ramp::Int;

fn main() {
    assert_eq!(Int::from(1) % Int::from(2),
               Int::from(1));
}

thread '<main>' panicked at 'assertion failed: `(left == right)` (left: `0`, right: `1`)', examples/rem.rs:5

(It also fails with % 2_i32, % 2_usize and % 2_u64.)

ramp-0.2.2/src/ll/limb.rs:89:28: 89:66 error: unresolved name `std::intrinsics::u64_add_with_overflow` [E0425]

rustc 1.6.0-nightly (5b4986fa5 2015-11-08)

[BUG] `&a - b` is reordered to `b - &a`

This fails (&1 - 0 == -1):

    assert_eq!(&Int::one() - Int::zero(), 1);

AVX2

YMP claims an impressive 2-3x speedup over GMP by using AVX2. Any opinions on: If what YMP does is sensible. What AVX2 support might look like? What internal algorithms it'd improve? How much work it requires?

divmod should possibly be "divrem"

The divmod function computes the remainder, not the modulus.

[feature request] Convert from/to bytes

It would be really nice if there were a way to convert Ints from/to byte slices (i.e. MSB/LSB encoded integers). Currently, I'm just doing a bunch of shifts and adds but this is definitely not the best way to do this.

BitXor is missing

[feature request] Functions for generating random Ints

It would be nice to have some functions for generating random Ints.
I would suggest functions for generating numbers:

with a given bit-length
out of a given range.

I am interested in implementing this feature. After some research I also have an idea how it should work, but I need some hint where it should go? I think a separate trait like in num::bigint would be better than directly including it in the Int trait.

Copy trait not implemented on Int struct

Is there any reason for this ?
It force to clone() everytime you need a for loop on range of Int, for example.

modular arithmetic

I'm working on a Rust implementation of Paillier cryptosystem (https://github.com/kunerd/rpaillier). After I started I realised a lag of fundamental big number arithmetic functions like mod_pow and mod_inverse. At the moment there is also no way to generate probably primes. So I started to implement them by myself.

Now I want to ask, if there is an interest to add these algorithms to this project?

current state of my implementation:

mod_pow: Implementation of LR-k-ary algorithm as described in the "Handbook of Applied Cryptography, 14.82".
mod_inverse: Implementation of "Extended Euclidean Algorithm" as described by Knuth

BitAnd and BitOr have memory corruption

Unfortunately, I can't reproduce this, except in a quickcheck run.

Broken build?

I think 0.3.6 is busted:

/home/alfie/.cargo/registry/src/github.com-XYZ/ramp-0.3.6/src/int.rs:160:24

self.ptr = Unique::new(vec.ptr());
^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::ptr::Unique`, found enum `std::option::Option`

And here's the minimal code to trigger it:

extern crate ramp;
fn main() {}

[feature request] Checked primitive type conversion

Add checked conversion for Int to primitive types (u8, u16, u32, ...), similar as in num::bigint trait.

fn to_i64(&self) -> Option<i64> { ... }

ARM?

Theres no easy way I presume, that I could get ramp to
work on an ARM processor I assume, due to the inline ASM?

cheers

Chris

Consider tuning the #[inline] declarations

Most of the operations on big-integers probably don't benefit much from inlining across crates (the time to run vastly outweights the call itself), so it might be nice to reduce how much is pushed across crates.

This should improving compile times of things that use ramp (such as the quickcheck test runner), and avoiding difficulties where not everything is inlined, e.g. currently bit_length() is inlined into other crates and ends up doing a division because some of the constants it needs are not inlined. (cc #53)

There's some probable exceptions to a no-#[inline] rule:

things that operate on a bigint and a primitive, such as x == 0
simple constructors like Int::zero
very fast/O(1) operations (like bit_length)
possibly, an outer layer of fast-paths for things like addition (e.g. for Int + Int detect if one arg is zero, or a single-limb), since the compiler may be able to deduce this earlier/statically when things are inlined. However, I expect this is mostly in the noise.

It might be nice if there was a way to request inlining at specific call sites, where calls to things in ll are particularly sensitive in ramp itself, so that not everything has to be explicitly marked #[inline] (e.g. inlining num_base_digits into bit_length is helpful, because it allows constant propagation to simplify things a lot). I guess this can be simulated with something like:

pub fn foo(...) {
    foo_inline(...)
}

#[inline]
pub fn foo_inline(...) {
     // implementation here
}

One defaults to calling foo directly, but sensitive call sites can call foo_inline if they really need to.

Documentation Broken

https://docs.rs/ramp/ is broken even for old versions.

num_base_digits special case pow2

    #[test]
    fn num_base_digits_pow2() {
        use ::ll::base::num_base_digits;
        let cases = [
            ("10", 2, 4), // 0b 1010
            ("15", 2, 4), // 0b 1111
            ("16", 2, 5), // 0b10000
            ("1023", 2, 10), // 0b 1111111111
            ("1024", 2, 11), // 0b10000000000
            ("341", 4, 5), // 4»11111
            ("5461", 4, 7), // 4»1111111
            ("16383", 4, 7), // 4» 3333333
            ("16384", 4, 8), // 4»10000000
            ("65535", 4, 8), // 4»33333333
            ("299593", 8, 7), // 8»1111111 // 8**0 + 8**1 + 8**2 + 8**3 + 8**4 + 8**5 + 8**6
            ("299594", 8, 7), // 8»1111112
            ("2097151", 8, 7), // 8» 7777777
            ("2097152", 8, 8), // 8»10000000
            ("268435455", 16, 7), // 0x fffffff
            ("268435456", 16, 8), // 0x10000000
            ("13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084095", 2, 512), // 512 bits with value 1 -> 1 Limb
            ("13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096", 2, 513), // 513 bits -> 2 Limbs
        ];
        for &(s, base, digits) in cases.iter() {
            let i : Int = s.parse().unwrap();
            unsafe {
                println!("{:?} in base {} should need {} digits", s, base, digits);
                assert_eq!(digits,
                           num_base_digits(i.limbs(), i.abs_size(), base));
            }
        }
    }

fails with

"15" in base 2 should need 4 digits
"16" in base 2 should need 5 digits
"1023" in base 2 should need 10 digits
"1024" in base 2 should need 11 digits
"341" in base 4 should need 5 digits
"5461" in base 4 should need 7 digits
"16383" in base 4 should need 7 digits
"16384" in base 4 should need 8 digits
"65535" in base 4 should need 8 digits
"299593" in base 8 should need 7 digits
thread 'int::test::num_base_digits_pow2' panicked at 'assertion failed: `(left == right)` (left: `7`, right: `21`)', src/int.rs:3680

Expose numerator/denominator of Rational

Is it possible to get a fractional form from Rational?
for example

let (numerator, denominator) = rational.fraction()

Relicense under dual MIT/Apache-2.0

Why?

The MIT license requires reproducing countless copies of the same copyright
header with different names in the copyright field, for every MIT library in
use. The Apache license does not have this drawback, and has protections from
patent trolls and an explicit contribution licensing clause. However, the
Apache license is incompatible with GPLv2. This is why Rust is dual-licensed as
MIT/Apache (the "primary" license being Apache, MIT only for GPLv2 compat), and
doing so would be wise for this project. This also makes this crate suitable
for inclusion in the Rust standard distribution and other project using dual
MIT/Apache.

How?

To do this, get explicit approval from each contributor of copyrightable work
(as not all contributions qualify for copyright) and then add the following to
your README:

## License

Licensed under either of
 * Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
 * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)
at your option.

### Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted
for inclusion in the work by you shall be dual licensed as above, without any
additional terms or conditions.

and in your license headers, use the following boilerplate (based on that used in Rust):

// Copyright (c) 2015 t developers
// Licensed under the Apache License, Version 2.0
// <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT
// license <LICENSE-MIT or http://opensource.org/licenses/MIT>,
// at your option. All files in the project carrying such
// notice may not be copied, modified, or distributed except
// according to those terms.

And don't forget to update the license metadata in your Cargo.toml!

Contributor checkoff

0x10000000000000000.pow(3) is computed incorrectly

extern crate ramp;
extern crate gmp;
use ramp::Int;
use gmp::mpz::Mpz;

macro_rules! eq {
    ($r: expr, $g: expr) => {
        assert_eq!($r.to_str_radix(16, false), $g.to_str_radix(16))
    }
}

fn parse(s: &str) -> (Int, Mpz) {
    (Int::from_str_radix(s, 16).unwrap(),
     Mpz::from_str_radix(s, 16).unwrap())
}
fn main() {
    let (ar, ag) = parse("10000000000000000");

    eq!(ar.pow(3),
        ag.pow(3));
}

thread '<main>' panicked at 'assertion failed: `(left == right)` (left: `"10000000000000000"`, right: `"1000000000000000000000000000000000000000000000000"`)', examples/isolated.rs:19

There has to be at least that many trailing zeros, presumably so that the lowest word is empty. And .pow(2) is computed correctly.

div_1000 & pow_10 slow on default 32-bit Rust

Compiled with default codegen (pentium4) settings:

test int::test::bench_div_1000_1000 ... bench: 7,178 ns/iter (+/- 9,400)
test int::test::bench_pow_10_10 ... bench: 2,717 ns/iter (+/- 9,571)

whereas with pentium2:

test int::test::bench_div_1000_1000 ... bench: 1,431 ns/iter (+/- 9,266)
test int::test::bench_pow_10_10 ... bench: 1,576 ns/iter (+/- 9,464)

Used rustc 1.8 (0d1cd9b) after llvm rebase. The rest of the benchmarks didn't exhibit any anomalous results.

Use of pow with Int exp

Is it possible to add a version of Int::pow that accepts another Int as the exponent?

let n = Int::from(53174392371729765229371175317439237172976522937117);
let new_n = 8 * Int::from(2).pow(n - 1) + 5;
// instead of
let new_n = 8 * (Int::zero()..n).fold(Int::from(2), |acc, _| acc * 2) + 5;

Thanks!

Change use of i32 to u32 where appropriate

Most of the function in the ll module take a size as an i32 type. I'm not entirely sure why I did that, as a u32 type makes more sense most of the time.

This should be a fairly simple task, just change the signatures so the size arguments are u32 instead of i32, most of them start with a debug_assert! for the size being greater than 0 anyway.

Implement divide-and-conquer algorithm in ll/base.rs

On line 306. there is a todo stating to use a divide and conquer algorithm for large inputs.

In my use case of the library, over 60% of instructions executed according to cargo-profiler belong to the functions from_base and from_base_small. Is there any possibility of this algorithm being implemented in the future, or should I look into using other libraries?

Error compiling ramp 0.1.2

Hi there,
Compiling ramp gives:

Updating registry https://github.com/rust-lang/crates.io-index
Compiling ramp v0.1.2
/home/manfred/.cargo/registry/src/github.com-1ecc6299db9ec823/ramp-0.1.2/src/ll/limb.rs:52:9: 52:14 error: expected one of extern, fn, type, or unsafe, found const
/home/manfred/.cargo/registry/src/github.com-1ecc6299db9ec823/ramp-0.1.2/src/ll/limb.rs:52 pub const BITS : usize = 32;
^~~~~
Could not compile ramp.

To learn more, run the command again with --verbose.

Documentation bug

the Int::is_even() method's documentation states Returns 0 if self == 0 which isn't correct since the method returns a bool

[BUG] `ThreadRng::gen_uint_below()` hangs for large numbers

Whenever I try to generate a number less than a certain large prime, the program seems to get caught in a loop. It takes up a bunch of CPU time and I've never waited long enough to see it (possibly) return a value. Here's a small program that will hang:

extern crate ramp;
extern crate rand;

use rand::Rng;
use ramp::int::{Int, RandomInt};

static P_521: &'static str = "\
    000001ffffffffffffffffffffffffffffffffffffffffff\
    ffffffffffffffffffffffffffffffffffffffffffffffff\
    ffffffffffffffffffffffffffffffffffffffff";

fn main() {
    let big = Int::from_str_radix(P_521, 16).unwrap();
    let small = Int::from(957);

    let mut rng = rand::thread_rng();

    let small_rand = rng.gen_uint_below(&small);
    println!("Small random {}", &small_rand);

    let big_rand = rng.gen_uint_below(&big); // Hangs here
    println!("Big random {}", &big_rand);
}

	ll::copy_incr(w_tmp.offset(ys as isize),
	wp.offset(ys as isize),
	ys);

	loop {
	if (exp & 1) == 1 {
	if wn > bn {
	ll::mul(scratch, wp, wn, bp, bn);
	} else {
	ll::mul(scratch, bp, bn, wp, wn);
	}
	wn = ll::normalize(scratch, wn + bn);
	ll::copy_incr(scratch, wp, wn);
	}

	exp >>= 1;

	// Do this check before the base multiplication so we don't
	// end up needing more space than necessary
	if exp == 0 {
	break;
	}

	ll::sqr(scratch, bp, bn);
	bn = ll::normalize(scratch, bn + bn);

	ll::copy_incr(scratch, bp, bn);

	}

aatch / ramp Goto Github PK

ramp's People

Contributors

Stargazers

Watchers

Forkers

ramp's Issues

Why?

How?

Contributor checkoff

Recommend Projects

Recommend Topics

Recommend Org