ByteData.getUint64() can't able to generate integers greater than (2^63)-1

[rashedmyt]

I am writing code which takes bytes from a buffer and convert them to Uint64... but to my surprise I found out that the method isn't working as expected..

Here is a sample code to reproduce the error..

Code

import 'dart:typed_data';

void main() {
  print(ByteData.view(Uint8List.fromList([0,0,0,0,0,0,0,128]).buffer).getUint64(0, Endian.host));
}

Output

$ dart main.dart
-9223372036854775808

Expected Output:

$ dart main.dart
9223372036854775808

Dart Version: Dart VM version: 2.1.0-dev.9.3.flutter-9c07fb64c4
OS: Windows 10 1803 Build 17134.407

[lrhn]

Dart 2 integers are 64-bit signed values (in the VM, they are doubles as ususal in the browser).

So, when you read a Uint64List element, you do get the correct bits, but the value as an int is interpreted as signed.

To represent a positive number larger than 2^63-1, you need to use a BigInt.
You can try something like:

  var uint64Mask = ((BigInt.one << 64) - BigInt.one);
  var big = BigInt.from(uint64List[index]) & uint64Mask;

[rakudrama]

@lrhn Or

BigInt.from(uint64List[index]).toUnsigned(64);

[rashedmyt]

If that's the case then what about the misleading information present in the API documentation https://api.dartlang.org/stable/2.1.0/dart-typed_data/ByteData/getUint64.html

[lrhn]

The misleading information should be fixed. The returned value is the listed value converted to int.

Web compiled programs can't even use Uint64List at all, so we don't have to account for int actually being double on those platforms.

[rashedmyt]

I am writing a flutter application which internally calculates the uint64 value from bytes as given in my first comment.. If the code couldn't generate the correct value then my entire application will be of no use because it entirely depends on the correct parsing of those bytes.. there should be some kind of workaround or a way native to dart should be available since most of other languages I've worked with has that support..

[rashedmyt]

Even BigInt isn't able to generate uint64 numbers IIRC..

[lrhn]

BigInt can represent unsigned numbers of any size.
As @rakudrama pointed out, BigInt.from(int64Value).toUnsigned(64) will get you the unsigned value corresponding to the 64 bits of an integer.

The Dart integer type (on the VM) can only represent signed 64-bit numbers, and Dart only has the one integer type, so you need to use BigInt for any integer which isn't a signed 64-bit.

[rashedmyt]

Apologies for the remark on BigInt.. I have tested the example @rakudrama gave and it indeed worked.. But my main question is still - shouldn't the getUint64() method on a ByteData return a uint64 value? Instead of changing the documentation you guys can change its implementation to either return a num or BigInt object. If this change is done then Uint64List also needs to be updated as it should be able to store the generated uint64 numbers

[mraleph]

@rashedmyt int is considerably more efficient than BigInt so we certainly don't want to return BigInt from getUint64.

What kind of math are you doing with the uint64 that you are getting out of the array?

[rashedmyt]

I am implementing keccak crypto in which from a given array of bytes a uint64 number is generated which is xor'ed with the state of hash.. you can see its implementation here which I am trying to port to dart https://github.com/turtlecoin/cs-turtlecoin/blob/master/CantiLib/Blockchain/Crypto/Keccak/Keccak.cs

the exact line I'm concerned with is this https://github.com/turtlecoin/cs-turtlecoin/blob/master/CantiLib/Blockchain/Crypto/Keccak/Keccak.cs#L132

[mraleph]

From a brief look I suspect that you don't actually need uint64 for this crypto algorithm.

If you are only doing +, -, <<, * 8 then int would bitwise behave exactly the same as uint.

The only thing you need to be careful about is shift to the right >>, which behaves differently.

But you can easily work-around those differences by masking upper bits away (or by using >>> which was supposed to be part of Dart 2 - but got by accident omitted and is going to be added in Dart 2.2)

[rashedmyt]

This is the input to my library var res = Keccak.hash(Uint8List.fromList("".codeUnits));

I put a print before the loop to see the temp list

[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128, 1, 0, 0, 0, 0, 0, 0, 0]

which is exactly the same as produced in any other language.. inside the loop it computes uint64 value from 8 bytes starting from i*8 position in the byte array..

The code in my first comment is failing to generate the required uint64 value.. it should generate 2^63 value but it is generating -(2^63) probably due to out of bounds and wrapping

[mraleph]

@rashedmyt yes, the code in your first comment does not print 2^63. However 2^63 and -(2^63) is exactly the same value if you look at it bitwise, which is what most hashing algorithms care about - they look at bits rather the integer value that those bits represent.

Imagine you take uint64 value 2^63 and int64 value -(2^63). Bitwise both of these values are the same thing - 0x8000000000000000. So if your algorithm works with bits there is no difference to it. You just need to be careful about the right shift - all other operations would work the same way. For the right shift you need to do something like this

int logicalShiftRight(int val, int n) => (val >> n) & ~(-1 << (64 - n))

If you post the whole Dart source you have I can take a look and tell you why you are not getting the result you want.

(From what I see in the C# source there is only a single shift to the right in rotation helper - you need to write it using logicalShiftRight instead of >> and things should work).

[rashedmyt]

import 'dart:typed_data';
import 'constants.dart';
import 'dart:math';

class Keccak {
  static Uint8List hash(Uint8List input) {
    return keccak(input);
  }

  static void keccakf(Uint64List state, [int rounds = keccakRounds]) {
    int t;

    Uint64List bc = Uint64List(5);

    for (int round = 0; round < rounds; round++) {
      /* Theta */
      for (int i = 0; i < 5; i++) {
        bc[i] = state[i] ^
            state[i + 5] ^
            state[i + 10] ^
            state[i + 15] ^
            state[i + 20];
      }

      for (int i = 0; i < 5; i++) {
        t = bc[(i + 4) % 5] ^ rotl64(bc[(i + 1) % 5], 1);

        for (int j = 0; j < 25; j += 5) {
          state[i + j] ^= t;
        }
      }

      /* Rho Pi */
      t = state[1];

      for (int i = 0; i < 24; i++) {
        int j = keccakfPiln[i];
        bc[0] = state[j];
        state[j] = rotl64(t, (keccakfRotc[i]).toUnsigned(64));
        t = bc[0];
      }

      /* Chi */
      for (int j = 0; j < 25; j += 5) {
        for (int i = 0; i < 5; i++) {
          bc[i] = state[i + j];
        }

        for (int i = 0; i < 5; i++) {
          state[i + j] ^= (~bc[(i + 1) % 5]) & bc[(i + 2) % 5];
        }
      }

      /* Iota */
      state[0] ^= keccakfRndc[round];
    }
  }

  /* Compute a hash of length outputSize from input */
  static Uint8List _keccak(Uint8List input, int outputSize) {
    Uint64List state = Uint64List(25);

    int rsiz = hashDataArea;

    if (outputSize != 200) {
      rsiz = 200 - 2 * outputSize;
    }

    int rsizw = (rsiz ~/ 8).toInt().toSigned(32);
    
    int inputLength = input.length;

    /* Offset of input array */
    int offset = 0;

    for (; inputLength >= rsiz; inputLength -= rsiz, offset += rsiz) {
      for (int i = 0; i < rsizw; i++) {
        /* Read 8 bytes as a ulong, need to multiply i by 8
                       because we're reading chunks of 8 at once */
        state[i] ^= ByteData.view(input.buffer)
            .getUint64(offset + (i * 8), Endian.little);
        
      }

      keccakf(state);
    }

    Uint8List tmp = Uint8List(144);

    /* Copy inputLength bytes from input to tmp at an offset of
               offset from input */
    for (int i = 0; i < inputLength; i++) {
      tmp[i] = input[i];
    }

    tmp[inputLength] = 1;
    inputLength++;

    /* Zero (rsiz - inputLength) bytes in tmp, at an offset of
               inputLength */
    for (int i = inputLength; i < rsiz; i++) {
      tmp[i] = 0;
    }

    tmp[rsiz - 1] |= 0x80;
    tmp[rsiz] = 1;

    for (int i = 0; i < rsizw; i++) {
      /* Read 8 bytes as a ulong - need to read at (i * 8) because
                   we're reading chunks of 8 at once, rather than overlapping
                   chunks of 8 */
      state[i] ^= ByteData.view(tmp.buffer,i*8, 8).getUint64(0, Endian.host);
    }

    keccakf(state, keccakRounds);

    Uint8List output = state.buffer.asUint8List(0, outputSize);

    return output;
  }

  static int rotl64(int x, int y) {
    x = x.toUnsigned(64);
    y = y.toUnsigned(64);
    return (x << y | x >> ((64 - y))).toUnsigned(64);
  }

  /* Hashes the given input with keccak, into an output hash of 200
           bytes. */
  static Uint8List keccak1600(Uint8List input) {
    return _keccak(input, 200);
  }

  /* Hashes the given input with keccak, into an output hash of 32 bytes.
           Copies outputLength bytes of the output and returns it. Output
           length cannot be larger than 32. */
  static Uint8List keccak(Uint8List input, [int outputLength = 32]) {
    if (outputLength > 32) {
      throw ArgumentError("Output length must be 32 bytes or less!");
    }

    Uint8List result = _keccak(input, 32);

    Uint8List output = Uint8List(outputLength);

    /* Don't overflow input array */
    for (int i = 0; i < min(outputLength, 32); i++) {
      output[i] = result[i];
    }

    return output;
  }
}

[rashedmyt]

you are right.. the logicalShiftRight worked.. but looks like my implementation has gone somewhere wrong.. for 1 out of 4 inputs I tried its giving different results

[rashedmyt]

so at the end.. its just documentation misleading then..

[rashedmyt]

@mraleph any work is being done on getting more crypto libraries added here https://github.com/dart-lang/crypto by the Dart Team or will it be just that

[mraleph]

@rashedmyt I am not aware of any effort to expand the crypto library. I think people are encouraged to publish their own packages if they would like to implement new algorithms.

[rashedmyt]

ok.. 👍

[rashedmyt]

@mraleph since dart 2.2 is out.. is the >>> operator added to the language? Also I want to submit a PR to fix the documentation.. could you point me to it?

[mraleph]

The >>> got dropped from 2.2 unfortunately, it might get into one of the later versions, but there is no clear milestone allocated to it currently.

/fyi @lrhn @mit-mit