Implementation issue for unsigned/triple-shift >>> operator

[floitschG]

This is the implementation issue for the triple-shift >>> operator (unsigned shift), see language feature #120

The operator has the same precedence as >>.
The expression e1 >>> e2 is a compile-time constant expression if both e1 and e2 are compile-time constant expressions evaluating to integers (and int will implement the operator).
The symbol #>>> is valid (along with const Symbol(">>>")), as is x >>>= e as an expression.

Adding the new operator is non-breaking.

• specification
• Frontend Handle the unsigned shift operator in the frontend sdk#30888
• Analyzer Handle the unsigned shift, triple-shift, >>> operator in analyzer sdk#44908
• dart2js Handle the unsigned shift operator in dart2js sdk#30890
• DDC Handle the unsigned shift operator in DDC sdk#30891
• VM Implement the triple shift operator sdk#30892

[rashedmyt]

waiting for this operator to be in release

[kevmoo]

@lrhn what's the story with this?

@aadilmaan @mit-mit – are we tracking this somewhere?

Related: https://stackoverflow.com/questions/57190508/does-dart-have-operator/57210971

[mit-mit]

This is now tracked in #120. Closing the present historical issue.

[mit-mit]

Transferring and re-purposing to be the implementation issue for this feature. Please note that this isn't currently being implemented, it's just ready for implementation.

[AKushWarrior]

Is there a status on this? It would be massively helpful for cryptography.

[AKushWarrior]

I don't think this would be too difficult. I haven't tried forking dart's internals, but I'm using a utility extension function. Converted to an operator, it would look like. (EDIT: JS is hard)

int operator >>> (int n) {
    return ((this >= 0) ? this >> (n) : ~(~this >> (n)));
}

[AKushWarrior]

The code snippet I posted was wrong. I fixed it.

It's tested and works on the VM, but does not work when trans-piled to JS.

[AKushWarrior]

New code snippet, which works both on the VM and when trans-piled to JS. (EDIT: it doesn't; it's broken for JS for negative numbers; see below)

  int operator >>> (int count) {
    if (!isJS) {
      return (this >= 0) ? this >> count : ~(~this >> count);
    } else {
      count &= 0x1f;
      if (this >= 0) {
        return (this >> count + 1);
      } else {
        var mask = 1 << (31 - count);
        return (~this >> count) | mask;
      }
    }
  }

  bool get isJS {
    // Some definition here...
  }

I dunno about performance, but I use only bitwise operators, so it should be decent. It's tested on the VM and DartPad. All cases (negative, zero, positive) check out for both.

If someone could guide me through the process, I'd be happy to try and implement the >>> operator as a language feature.

[mpfaff]

@AKushWarrior what is x supposed to be in your code example?

[AKushWarrior]

@AKushWarrior what is x supposed to be in your code example?

Nothing. It was a remnant from me testing the function in a different setup than the extension method presented here. It should be fixed now.

[mpfaff]

Neither quite works for me.

This is the code I'm testing:

(3185753779 * 3185753779).tripleShift(32)

On DartPad, I get 1208817664, which is half of 2417635328 which I get from a pure JavaScript >>>. On the Dart VM, I get -1931962775.

[AKushWarrior]

@mpfaff I'll review at some point. I'm kinda swamped and I didn't really test it super extensively, just with 10 or so test cases.

[AKushWarrior]

@mpfaff new DartPad code is below and seems to work fine on DartPad. If you could try to break it with more cases, that would be great. All test cases have been generated using TypeScript.

void main() {
  //positive
  print((3185753779 * 3185753779).tripleShift(32) == 2417635328);
  print(25.tripleShift(25) == 0);
  print(13123423.tripleShift(5) == 410106);
  
  //zero
  print(0.tripleShift(23) == 0);
  
  //negative
  print((-12245234).tripleShift(11) == 2091172);
  print((-2938648).tripleShift(4) == 268251790);
}

extension tripShift on int {
  int tripleShift (int count) {
    if (false) {
      return (this >= 0) ? this >> count : ~(~this >> count);
    } else {
      // assumes this > -4294967295, or -(2^32 -1)
      count &= 0x1f;
      if (this >= 0) {
        return (this >> count);
      } else {
        return (this >> count) ^ ((0xFFFFFFFF) ^ ((1 << (32-count)) - 1));
      }
    }
  }
}

[AKushWarrior]

There should be a difference between how zero-fill right shift works on the web and on the VM: 64-bit numbers which have been zero-fill right shifted are very different from 32-bit numbers which have been zero-fill right shifted.

[AKushWarrior]

@mit-mit @lrhn is this on the roadmap for post-NNBD improvements?

[eernstg]

It is on a shortlist of small, useful features: #1077.

[Comevius]

@AKushWarrior

Neither of your implementations work properly. Many of your tests also expects the wrong result:

(3185753779 * 3185753779) == -8297716933296770775;
// 1000110011011000100101100110100110010000000110100011000100101001
(3185753779 * 3185753779) >>> 32 == 2363004521;
// 10001100110110001001011001101001
(3185753779 * 3185753779) >>> 32 != 2417635328;
// 10010000000110100011000000000000

This is the correct implementation for Dart Native:

extension TripleShift on int {
  int tripleShift(int count) { 
    return (this >> count) & ~(-1 << (64 - count));
  }
}

[AKushWarrior]

@AKushWarrior

Neither of your implementations work properly. Many of your tests also expects the wrong result:

(3185753779 * 3185753779) == -8297716933296770775;
// 1000110011011000100101100110100110010000000110100011000100101001
(3185753779 * 3185753779) >>> 32 == 2363004521;
// 10001100110110001001011001101001
(3185753779 * 3185753779) >>> 32 != 2417635328;
// 10010000000110100011000000000000

This is the correct implementation for Dart Native:

extension TripleShift on int {
  int tripleShift(int count) { 
    return (this >> count) & ~(-1 << (64 - count));
  }
}

I'm matching the JS version. While you are mathematically right, a programmer is likely to be confused that using >>> in dart2js results in a different value than pure js.

[Comevius]

@AKushWarrior

JavaScript only defines bitwise operations on 32-bit unsigned integers, so even when you do >>>0 it lowers the precision of your already lowered precision 53-bit int to the 0 to 0xffffffff range.

You would need something like Int64 to emulate 64-bit values and operations:
https://pub.dev/documentation/fixnum/latest/fixnum/Int64/shiftRightUnsigned.html

BigInt would be another solution, but Dart is yet to support it.

[AKushWarrior]

@Comevius

Dart integers, when translated to JS, are 32 bit, not 53 bit. While I agree that we should have clearer types (or just standardize the fixnum types), that would break all existing code.

When using Dart for JS, you have to assume that all your integers are 32 bit, or just use https://pub.dev/packages/fixnum. Dart integers, to the best of my knowledge, are not meant to emulate 64 bit integers when transpiled to JS.

Instead of trying to create a solution that produces the same results on both Native and JS, which doesn't make sense given the nature of both platforms, I created a separate version which matches the ES6 results for >>>. All those test cases were designed to be run on DartPad, which transpiles code to JS before running it.

EDIT: In fact, your native code is not platform agnostic either. If you evaluate that code after transpilation to JS, it will result in incorrect shifts (due to 32 bit truncation).

[eernstg]

Dart integers, when translated to JS, are 32 bit, not 53 bit.

Not quite: Dart numbers are represented as JavaScript numbers when compiled to JavaScript. A number is int if it has no fractional part, and it always is double. So that yields 53 bits of information for an int, but includes larger numbers where the "missing" low bits are treated as zeros (so 18014398509481982 is int).

However, bitwise operations work on 32 bits and treat them as an unsigned number (cf. this comment). So >>> should work accordingly when compiled to JS, and in particular there will be differences between the results when the target language is native vs. when it is JS.

[AKushWarrior]

Dart integers, when translated to JS, are 32 bit, not 53 bit.

Not quite: Dart numbers are represented as JavaScript numbers when compiled to JavaScript. A number is int if it has no fractional part, and it always is double. So that yields 53 bits of information for an int, but includes larger numbers where the "missing" low bits are treated as zeros (so 18014398509481982 is int).

Interesting. The only time I considered the bit length of integers was when doing bitwise ops, so I guess it never occurred to me.

However, bitwise operations work on 32 bits and treat them as an unsigned number (cf. this comment). So >>> should work accordingly when compiled to JS, and in particular there will be differences between the results when the target language is native vs. when it is JS.

This is in line with my example. My newest DartPad example works with expected results from the target language (JS).

[srawlins]

Note: added analyzer subtask above dart-lang/sdk#44908

[eernstg]

Closing: This feature was enabled by default in 2.14.