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](https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#toByteArray()) 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.

[azenla]

@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?

[lrhn]

We now plan to seal typed_data classes (#45115), which also opens up the ability to add members on the classes without breaking anyone. That makes it more likely that we'll actually be able to add a setBigInt method on byteData. It's still an issue that the BigInt class itself isn't sealed, so we can't assume anything about the underlying representation.

For that reason, a writeBytes(Uint8List target, int start, {Endian? endian) on BigInt would be better, but a breaking change to add.

[rakudrama]

@lrhn Should BigInt be sealed too?

That would preserve a path for BigInt constants, BigInt literals, implementation in dart2js via JavaScript BigInt values, and interoperability with BigInt64Array.

[lrhn]

I think it would be a good idea to seal BigInt.

Effectively, we've already assumed that it is sealed because we start all the instance methods with _ensureSystemBigInt(other) anyway, which throws if passed anything other than the system implementation of BigInt.

It'd be a different request, though. I'd vote for it.

[mark-dropbear]

Figured I would leave this here in case anybody else came across it in the future but I ran into a scenario where I needed this recently here: https://github.com/dropbear-software/todart/blob/main/common/lib/src/types/cloud_resource_identity.dart

Here is how I solved it thanks to some help from others in the community Gitter chat

/// Converts a [Uint8List] byte buffer into a [BigInt]
static BigInt _convertBytesToBigInt(Uint8List bytes) {
  BigInt result = BigInt.zero;

  for (final byte in bytes) {
    // reading in big-endian, so we essentially concat the new byte to the end
    result = (result << 8) | BigInt.from(byte);
  }
  return result;
}

[kevmoo]

@mark-dropbear – make that an extension method and we have 🥇 !!!

[mark-dropbear]

Thanks @kevmoo I will take a look at that later on, have never used extension methods before but I am excited to check them out. By the way, that project I referenced there is most certainly not yet in a state that has a whole lot worth talking about just yet but is heavily inspired by Knarly Vote (There are a few big differences like gRPC rather than cloud functions for example).

However, the entire concept is to kind of just use that code base as a playground to explore what fullstack dart could look like and especially while trying to do things the "Google AIP way".

I'm intentionally trying to keep the application itself relatively simple (it's just a Todo list kind of app) so that I have something that at least is going to have to bump into "real life problems" but easy enough that I can just focus on the patterns and see where the messy parts are.

I was going to ping you when I had something there worth sharing because I figured that both you and a few others might get a kick out of it.

[ssddOnTop]

Hey I was recently working on a project for e2ee for multiple languages and I stumbled upon this problem, I tried @mark-dropbear and @lrhn 's solutions but they were a bit incomplete, the method _convertBytesToBigInt() assumes big-endianness whereas writeBigInt() writes in little-endian so I fixed them.

  static BigInt readBytes(Uint8List bytes) {
    BigInt result = BigInt.zero;

    for (final byte in bytes) {
      // reading in big-endian, so we essentially concat the new byte to the end
      result = (result << 8) | BigInt.from(byte & 0xff);
    }
    return result;
  }

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

now I'm able to use the same methods for multiple languages without any problems.