as-bignum
as-bignum copied to clipboard
MaxGraey
u256.shr implementation is broken.
The bit shifting doesn’t work for shift values >= 64.
Here’s testing data comparing u256.shr vs. fixed impl vs. JS bigint.shr. Copy out to code editor for better viewing.
Testing 0 >> 1. fixed: 0, original: 0, js: 0
Testing 0 >> 64. fixed: 0, original: 0, js: 0
Testing 1 >> 1. fixed: 0, original: 0, js: 0
Testing 1 >> 64. fixed: 0, original: 1, js: 0
Testing 10 >> 1. fixed: 5, original: 5, js: 5
Testing 10 >> 64. fixed: 0, original: 10, js: 0
Testing 100 >> 1. fixed: 50, original: 50, js: 50
Testing 100 >> 64. fixed: 0, original: 100, js: 0
Testing 1000 >> 1. fixed: 500, original: 500, js: 500
Testing 1000 >> 64. fixed: 0, original: 1000, js: 0
Testing 1234567890 >> 1. fixed: 617283945, original: 617283945, js: 617283945
Testing 1234567890 >> 64. fixed: 0, original: 1234567890, js: 0
Testing 4294967296 >> 1. fixed: 2147483648, original: 2147483648, js: 2147483648
Testing 4294967296 >> 64. fixed: 0, original: 4294967296, js: 0
Testing 9223372036854775808 >> 1. fixed: 4611686018427387904, original: 4611686018427387904, js: 4611686018427387904
Testing 9223372036854775808 >> 64. fixed: 0, original: 9223372036854775808, js: 0
Testing 18446744073709551616 >> 1. fixed: 9223372036854775808, original: 9223372036854775808, js: 9223372036854775808
Testing 18446744073709551616 >> 64. fixed: 1, original: 18446744073709551617, js: 1
Testing 18446744073709551616 >> 1. fixed: 9223372036854775808, original: 9223372036854775808, js: 9223372036854775808
Testing 18446744073709551616 >> 64. fixed: 1, original: 18446744073709551617, js: 1
Testing 36893488147419103232 >> 1. fixed: 18446744073709551616, original: 18446744073709551616, js: 18446744073709551616
Testing 36893488147419103232 >> 64. fixed: 2, original: 36893488147419103234, js: 2
Testing 73786976294838206464 >> 1. fixed: 36893488147419103232, original: 36893488147419103232, js: 36893488147419103232
Testing 73786976294838206464 >> 64. fixed: 4, original: 73786976294838206468, js: 4
Testing 1180591620717411303424 >> 1. fixed: 590295810358705651712, original: 590295810358705651712, js: 590295810358705651712
Testing 1180591620717411303424 >> 64. fixed: 64, original: 1180591620717411303488, js: 64
Testing 1208925819614629174706176 >> 1. fixed: 604462909807314587353088, original: 604462909807314587353088, js: 604462909807314587353088
Testing 1208925819614629174706176 >> 64. fixed: 65536, original: 1208925819614629174771712, js: 65536
Testing 1267650600228229401496703205376 >> 1. fixed: 633825300114114700748351602688, original: 633825300114114700748351602688, js: 633825300114114700748351602688
Testing 1267650600228229401496703205376 >> 64. fixed: 68719476736, original: 1267650600228229401565422682112, js: 68719476736
Here is a functional implementation:
public static shr(a: u256, shift: i32): u256 {
shift &= 255;
if (shift == 0) return a;
const w = shift >>> 6; // how many full 64-bit words to drop
const b = shift & 63; // how many bits to shift within a word
// Extract the words
let lo1 = a.lo1;
let lo2 = a.lo2;
let hi1 = a.hi1;
let hi2 = a.hi2;
// Shift words down by w words
// For w = 1, move lo2->lo1, hi1->lo2, hi2->hi1, and hi2 = 0
// For w = 2, move hi1->lo1, hi2->lo2, and zeros in hi1, hi2
// For w = 3, move hi2->lo1 and zeros in others
// For w >= 4, everything is zero.
if (w >= 4) {
// Shifting by >= 256 bits zeros out everything
return u256.Zero;
} else if (w == 3) {
lo1 = hi2;
lo2 = 0;
hi1 = 0;
hi2 = 0;
} else if (w == 2) {
lo1 = hi1;
lo2 = hi2;
hi1 = 0;
hi2 = 0;
} else if (w == 1) {
lo1 = lo2;
lo2 = hi1;
hi1 = hi2;
hi2 = 0;
}
// Now apply the bit shift b
if (b > 0) {
// Bring down bits from the higher word
const carryLo2 = hi1 << (64 - b);
const carryLo1 = lo2 << (64 - b);
const carryHi1 = hi2 << (64 - b);
lo1 = (lo1 >>> b) | carryLo1;
lo2 = (lo2 >>> b) | carryLo2;
hi1 = (hi1 >>> b) | carryHi1;
hi2 = hi2 >>> b;
}
return new u256(lo1, lo2, hi1, hi2);
}
If you have the opportunity to do PR I will be very happy, because at the moment I have suspended the active maintenance of all my open source projects
