Sdk: Support conversion between BigInt and binary representation

[stevenroose]

Just like bignum.BigInteger supports, please support binary conversion in BigInt as well.

More specifically, please provide the following methods:

  /// Allocates a big integer from the provided big-endian [bytes].
  BigInt.fromBytes(List<int> bytes);

  /// Returns a big-endian binary representation of the big integer.
  List<int> toBytes();

Possibly, both methods could take a (optional) parameters specifying the endianness, however I think big endian is by far the most common way to represent integers.

[lrhn]

Little endian is efficient for many CPUs, intel and (most) ARM at least, whereas big endian is "network byte order", so often used in communications. Either makes sense, either has advantages.

I would prefer a way to write big integers into a ByteBuffer or Uint8List, instead of having to create an intermediate list (although the returned buffer of toBytes could be a view of the internal buffer of the BigInt if it has the correct endianness). In that case we would just do what all the other ByteBuffer methods do and allow an Endian argument, that is, just support both endianesses and default to Endian.host.

[stevenroose]

As a reference, Java's BigInteger class has a default constructor that takes a big-endian byte array and a toByteArray() method that returns big-endian (two complement) bytes.

The BigInteger class from the bignum package also works like that.

I'm currently migrating the Pointy Castle code to BigInt and we also quite heavily rely on that functionality.

[kendfinger]

@lrhn I think that adding it to dart:typed_data like a normal fixed size integer wouldn't work, as BigInt is almost certainly implemented in a variable size.

So, if I needed to copy a bigint into a uint8list, I wouldn't have a good way of knowing how big to make the initial buffer.

[stevenroose]

@lrhn Also, since BigInt is in core, it needs to return List<int>, but under the hood, it will most certainly be a Uint8List, since that makes the most sense.

[lrhn]

BigInt has bitLength, so you do know its actual size. That would allow you to serialize it into, say, a Uint8Buffer if you ensure the capacity first. I'd still want that functionality, either on BigInt or on Unit8List/ByteData since it would be useful for serializing a BigInt. Creating an intermediate list is wasteful (but again, BigInt is immutable, so the list could be a view on the internal structure if that structure has a useful ordering, probably little endian).

Core methods can return typed data lists, and be typed as such, we just try to avoid it if it isn't necessary. I'd probably prefer adding setBigInt to ByteData rather than writeToByteData on BigInt.

[stevenroose]

@lrhn What is the roadmap for this? I agree that for efficient serialization etc, a method in ByteData might make sense, but for other applications, I think just having a toBytes (and equivalent from) is perfectly fine.

[stevenroose]

Any update on this??

[lrhn]

We are very busy doing the already planned Dart 2 features, so I don't think it's likely that a feature like this will make it into Dart 2.0. (It's kind-of trivial once the design is nailed down, but so are most of the other things we are currently doing).

For now, I'll recommend just using helper functions like:

BigInt readBytes(Uint8List bytes) {
  BigInt read(int start, int end) {
    if (end - start <= 4) {
      int result = 0;
      for (int i = end - 1; i >= start; i--) {
        result = result * 256 + bytes[i];
      }
      return new BigInt.from(result);
    }
    int mid = start + ((end - start) >> 1);
    var result = read(start, mid) + read(mid, end) * (BigInt.one << ((mid - start) * 8));
    return result;
  }
  return read(0, bytes.length);
}

Uint8List writeBigInt(BigInt number) {
  // Not handling negative numbers. Decide how you want to do that.
  int bytes = (number.bitLength + 7) >> 3;
  var b256 = new BigInt.from(256);
  var result = new Uint8List(bytes);
  for (int i = 0; i < bytes; i++) {
    result[i] = number.remainder(b256).toInt();
    number = number >> 8;
  }
  return result;
}

(There are lots of opportunities for optimizations, obviously).

[stevenroose]

(You made a typo on that long line.)

Yeah that was my alternative, but I was kinda trying to avoid that. But yeah since it won't land 2.0, I'll probably do this instead.

[sergiogragera]

Does anyone know of any method to convert uin8list to core.BigInt? How have you corrected the typo? Solution on https://github.com/stevenroose/dart-cryptoutils/pull/5/files works for me (changing some data type) but I don't know if is the correct solution. I want a method like Java BigInteger.

[lrhn]

Typo has been corrected (line was truncated when cut-n-pasted from a console).

[haarts]

Not sure if this belongs here but I found it helpful; the authors of PointyCastle include a utility to do the conversion: https://github.com/PointyCastle/pointycastle/blob/master/lib/src/utils.dart (actually @stevenroose made that change). If you are using PointyCastle anyway I think that is a good alternative.

[stevenroose]

Any update on this?

[kevmoo]

@lrhn – could we add a constructor on ByteBuffer to take BigInt? Require it be non-negative, etc.

[kevmoo]

@lrhn @mraleph thoughts here?

[rakudrama]

What is expected of the 'byte view' of negative BigInt values?
It is not specified if the internal representation is two's complement or sign-magnitude and that would affect any kind of 'view'.

We also need to consider if the operations can be implemented efficiently for JavaScript BigInt values, since we will eventually want to use JavaScript BigInt when compiling for the browser. Tree-structured algorithms like readBytes sketched by @lrhn are probably the way to go for big values, but that sketch could be improved considerably. It would be a big improvement for the compiler to recognize compound operations, e.g. (a + (b << c)) that can be implemented more efficiently without the intermediate values.

[rakudrama]

@stevenroose How are the requested APIs used? i.e. _why_ are they useful? Is there a standard that requires the format?