Robbepop / apint

Arbitrary precision integers library.
Other
26 stars 4 forks source link

Fix critical bug in multiplication of large odd-width instances #35

Closed AaronKutch closed 5 years ago

AaronKutch commented 5 years ago

I was working on making a better fuzz tester when I discovered a flaw that the old 0.2.0 tester missed. Overflowing multiplication using ApInts with a bit width that is not a multiple of Digits could sometimes not erase the excess bits in the last Digit, violating an invariant. It is unlikely that someone is using multiplication, wierd width ApInts, and overflowing the multiplication at the same, but this should still be merged as soon as possible, given a commit to update the changelog and bump version to 0.2.1, and released.

AaronKutch commented 5 years ago

Also, I need a more brief terminology when referring to ApInts with a bitwidth that is not a multiple of Digits, because I am going to end up using that a lot. "weird width ApInts" doesn't sound right to me, and "unusual width" is inprecise.

coveralls commented 5 years ago

Coverage Status

Coverage increased (+0.02%) to 75.069% when pulling a00b29f3ed81d30ad9aecbe467bed84ec0003a4b on AaronKutch:hotfix into 418d8bfda90c019ca2bffc93ebc52718b5cc6068 on Robbepop:master.

coveralls commented 5 years ago

Coverage Status

Coverage increased (+0.8%) to 75.877% when pulling 3c3189895ad13888d07f9f5fdd72d043bab7b7c5 on AaronKutch:hotfix into 418d8bfda90c019ca2bffc93ebc52718b5cc6068 on Robbepop:master.

codecov-io commented 5 years ago

Codecov Report

Merging #35 into master will increase coverage by 0.83%. The diff coverage is 97.56%.

Impacted file tree graph

@@            Coverage Diff            @@
##           master     #35      +/-   ##
=========================================
+ Coverage   74.97%   75.8%   +0.83%     
=========================================
  Files          22      22              
  Lines        5062    5117      +55     
=========================================
+ Hits         3795    3879      +84     
+ Misses       1267    1238      -29
Impacted Files Coverage Δ
src/apint/shift.rs 100% <100%> (ø) :arrow_up:
src/apint/arithmetic.rs 92.83% <96.49%> (+2.14%) :arrow_up:
src/apint/to_primitive.rs 97.89% <0%> (-0.01%) :arrow_down:
src/digit.rs 93.65% <0%> (+0.73%) :arrow_up:
src/apint/casting.rs 69.87% <0%> (+2.4%) :arrow_up:

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 418d8bf...3c31898. Read the comment docs.

Robbepop commented 5 years ago

Good catch! We should really write some contribution guidelines so that new code is always tested for all relevant scenarios and special cases and widths. E.g. bit widths of 1, 2, 8, 16, 32, 64, 128, 256, 512, 1024, 50, 100, 1000, etc. That's at least what I always targeted to do whenever I was testing new code. This, however, is really cumbersome and you can imagine ...

Could you maybe also add a regression test for the fixed bug?

Also, I need a more brief terminology when referring to ApInts with a bitwidth that is not a multiple of Digits, because I am going to end up using that a lot. "weird width ApInts" doesn't sound right to me, and "unusual width" is inprecise.

Yeah true ... I also haven't come up with a name but also I am against naming all the things. If we think about it in a different way what should be so special about those widths? Their only property is that they do not align with a multiple of a digit width.

AaronKutch commented 5 years ago

I have a regression test and a greatly improved fuzz tester (it tests a great variety of widths and has a proper overflowing multiplication test, and I have added more shifting and division tests) in my reorganization branch. I am confident now that all the arithmetic ops are working in both my branch (edit: my local branch, I need to do some more things before I push it to the PR) and in the current master.

Robbepop commented 5 years ago

I have a regression test and a greatly improved fuzz tester (it tests a great variety of widths and has a proper overflowing multiplication test, and I have added more shifting and division tests) in my reorganization branch. I am confident now that all the arithmetic ops are working in both my branch (edit: my local branch, I need to do some more things before I push it to the PR) and in the current master.

Ah very nice! So could you move the regression test for this bug over to this PR so it is self contained? (CI etc.) I would merge it as soon as CI passes it.

AaronKutch commented 5 years ago

I backported some chunks of code from the newer fuzz tester and found an arithmetic shift right bug in your old code, again regarding odd-width instances. In my local branch I rewrote the shifting functions before I made the newer fuzz tester so I didn't catch this. I have also backported the new arithmetic shifting function to fix this.

Robbepop commented 5 years ago

Okay so I think this is ready for merge.

Robbepop commented 5 years ago

Thanks a lot for fixing this!