search

shapesecurity / superpack-spec

:package: specification for the SuperPack extensible schemaless binary encoding format
Other
89 stars 18 forks source link

support arbitrarily large integers #12

Open michaelficarra opened 5 years ago

michaelficarra commented 5 years ago

Our current integers support magnitudes up to 264. Larger magnitudes will have to be encoded as floats/doubles or using binary* (losing the type info). Of course, this could be done via an extension point, but given the ubiquity of big integer libraries and especially with the addition of BigInt to JavaScript, I think built-in support might be worth it.

How could we do this? I recommend that we change uint64 to int64 (a signed 64-bit int) and replace nint64 with a VLQ. This would be a breaking change to the format.

edit: Alternatively, we could construct some sort of Rational representation using two VLQs.

edit again: I like git's "varint"s: https://github.com/git/git/blob/master/varint.c

LewisJEllis commented 5 years ago

I agree this seems like a worthwhile addition given the native addition of BigInt. VLQ and varint both seem like good options. What about using one of the reserved-but-unused type tags (0x80 or 0xF6) for this? I suppose it wouldn't create any backwards compatibility guarantee with old decoders (where we didn't define how they should treat reserved tags if encountered), but it would make new decoders compatible with old encoded data.

michaelficarra commented 5 years ago

I messed around with a prototype this weekend: https://github.com/michaelficarra/varint-bigint

@LewisJEllis I'm not too concerned about spec stability yet. I'd rather choose the right assignments of the type tags. And if we have varints and int64, there's not much reason to have nint64.