MattyIce
Bugfix/bitwise ops sometimes return negatives
This pull-request corrects some issues introduced during commit "calculation using weights and approx_sqrt" (sha: 9077ef6aef39359dc02b2166adf7a4663ddb42ed).
Original work from @joticajulian aimed on close(r) reproduction of inexact sqrt algorithm used in steem blockchain. To be honest, I didn't check, but it looks like translating C/C++ code into JS, and some subtle bugs creeped in: the 'integer' type and bitwise ops in JS work a little bit different than in C/C++, namely:
- all bitwise ops (except for >>>) return signed values (hence wrong results were produced during
+when hi/lo were merged back into one), - there is no true integer, it's all 64bit floats (so there's no sense in hi/lo'ing during shiftleft/right - just multiply or divide via Math.pow in one go)
This pull-request also contains some 'unit tests' (at the end of the code). Run them against unmodified and/or/shift to see what's wrong.
All of these tests pass just fine on patched code, but the tests are not exhaustive. I aimed to fix the negative results, which greatly damaged the overall result. Other subtle issues still occur after patching, because the attempt to mimic 64-bit integer and/or/shift is leaky: in JS the numeric type is 64bit float, not integer, so while numerical range is covered, the bitwise range is not covered. See for example:
(Math.pow(2,64)-0).toString(2)
"10000000000000000000000000000000000000000000000000000000000000000"
(Math.pow(2,64)-1023).toString(2)
"10000000000000000000000000000000000000000000000000000000000000000"
(Math.pow(2,64)-1024).toString(2)
"10000000000000000000000000000000000000000000000000000000000000000"
(Math.pow(2,64)-1025).toString(2)
"1111111111111111111111111111111111111111111111111111100000000000"
(Math.pow(2,64)-1026) === (Math.pow(2,64)-1025)
true
In short, this means, that by using standard JS 64bit floating point numeric type, any value which is sufficiently high in abs terms will have its last bits truncated, and resulting 64-bit-wise operations will have inexact results.
To correct that we'd need to move away from using native numerical type, and do even more things manually (or find a bigint/bitwise lib for JS), and that is outside of the scope of this patch.
Below: dump of my unredacted study of this issue, not really important, I'm pasting it here in case I have to review that again
curation estimator bug
on Google Chrome 69.0.3497.100, Windows 10 x64
in curation_calculator.html
in function calculate()
in approx_sqrt()
approx_sqrt() can go wild for valid input data
- this skews total-vote-weight estimations
- this cases such vote to be treated as downvote and is ignored in final calculation
probable cause:
- bitwise semantic mistake when translating C/C++ code into JS
example01:
post '@offgridtinyhouse/exploring-the-ruins-of-an-abandoned-town'
voter 'nfc'
line: var max_weight = approx_sqrt(data.rshares_total + rshares) - approx_sqrt(data.rshares_total);
expected: max_weight = 79219
actual: max_weight = -10737470093
fault: approx_sqrt(data.rshares_total + rshares)
== approx_sqrt(790934409 + 10254681182)
== approx_sqrt(11045615591)
=> -10737441641
cmp with Math.sqrt = 105098.12363215625
cmp with reimpl approx_sqrt in ruby = 107671
example02:
post '@offgridtinyhouse/exploring-the-ruins-of-an-abandoned-town'
voter 'luxbet'
line: var max_weight = approx_sqrt(data.rshares_total + rshares) - approx_sqrt(data.rshares_total);
expected: max_weight = 24086
actual: max_weight = 10737573398
fault: approx_sqrt(data.rshares_total)
== approx_sqrt(12694588943)
=> -10737435350
cmp with Math.sqrt = 112670.26645481939
cmp with reimpl approx_sqrt in ruby = 113962
analysis
approx_sqrt(x=20506658865) (same post, vote of 'isitfunny')
find_msb(x) -> 34 OK
msb_z -> 17 OK
shiftleft64(1,msb_x) -> 17179869184 OK
shiftleft64(1,msb_z) -> 131072 OK
mantissa_mask -> 17179869183 OK
and64(x,mantissa_mask) -> -968177615 WRONG, should be: 3326789681 (applying value correction for rest of function)
and64(msb_x,1) -> 0 OK
shiftright64(mantissa_x, msb_x-msb_z) -> 25381 OK
or64(mantissa_z_hi, mantissa_z_lo) -> 25381 OK
shiftright64(or64(mantissa_z_hi..., 1) -> 12690 OK
or64(msb_z_bit, mantissa_z) -> 143762 OK
final max_weight = 5714 OK (after 1 runtime value correction)
and64(x=20506658865,y=17179869183)
hi_lo(x) -> {hi: 4, lo: 3326789681} OK
hi_lo(y) -> {hi: 3, lo: 4294967295} OK
x.hi & y.hi -> 0 OK
x.lo & y.lo -> -968177615 WRONG, integer overflows to negatives
*exploratory*
y.lo -> 4294967295 OK
y.lo + 1 -> 4294967296 OK
y.lo - 1 -> 4294967294 OK
y.lo | 1 -> -1 seems bitwise ops return SIGNED!
patch for and64:
hi = x.hi & y.hi;
lo = x.lo & y.lo;
if(hi<0) hi = hi >>> 0
if(lo<0) lo = lo >>> 0
Hi there! I don't see any activity in this project anymore, is it finished/unmantained/etc? Or maybe it's just real-life things and you've got not time? Do you need some help with that? I suppose making an organisation and assigning a team of project mantainers would do the trick :)