Feature request: two's complement

[axic]

It would be nice to support two's complement representation for toArray() and perhaps a new way of loading a two's complement representation into BN.

[indutny]

I'm not sure what do you mean? toArray() is rather auxiliary and not an essential representation of the number. Why should two's complement operate on it? Do you have an example?

[axic]

I meant that internally you don't need to change any representation. Just keep storing numbers as you do and have the negative property control the sign.

However I would be happy to have a method to load negative numbers in two's complement representation into BN and to dump them in the same representation from BN.

For output, an easy extension would be adding a new argument to toArray, but I am not keen on having it there.

For input, perhaps a new method is needed as extending the constructor might be too much of a change.

[indutny]

May I ask you to post a code sample that will demonstrate it?

[axic]

Demonstrate the implementation in BN, or how I would imagine using it?

[indutny]

Just API with inputs and results

[axic]

Was thinking a bit about this in the past days.

I'm using BN.js to handle numbers between 8 and 256bits for the Ethereum ABI in http://github.com/axic/ethereumjs-abi. It supports signed (two's complement) and unsigned representations.

Currently I have two helper functions (toTwos() & fromTwos()) to convert the internal representation and then call toString() on them:

function toTwos(num, width) {
  if (num.isNeg())
    num = new BN(1).iushln(width).isub(num.iabs());
    // Or bitwise negate + plus 1
  return num;
}

function fromTwos(num, width) {
  if (num.testn(width - 1)) // top bit set => negative number
    num = new BN(1).iushln(width).isub(num).ineg();
    // Or bitwise negate + plus 1
  return num;
}

Perhaps I would suggest to have the following API:

• .toTwos(width) - mandatory width parameter in bits

e.g. .toTwos(256) will convert the lower 256 bits into 256 bits of two's complement and leaves all the upper bits intact. It is up to the user to take care of this.

• .fromTwos(width) - mandatory width parameter in bits

Works as the previous one, only touches the bottom width bits.

[indutny]

@axic sorry, but I'm not convinced that it could be useful for general developers. Thanks for taking time to explain to me!

[dcousens]

@indutny DER is twos complement IIRC.

And DER is, as far as I can tell, the primary encoding method for most people using this library?

[indutny]

Mmm... tell me about that ;) https://github.com/indutny/asn1.js/blob/75383bad77c869bde876db6a799badfcee9b2a1f/lib/asn1/encoders/der.js#L174-L192 Doesn't seem like anything similar.

[dcousens]

@indutny forget the code. DER in ASN.1 is literally defined as encoding a twos complement integer.
Reference: https://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf

The contents octets shall be a two's complement binary number equal to the integer value, and consisting of
bits 8 to 1 of the first octet, followed by bits 8 to 1 of the second octet, followed by bits 8 to 1 of each octet in turn up to
and including the last octet of the contents octets.
NOTE – The value of a two's complement binary number is derived by numbering the bits in the contents octets, starting with bit
1 of the last octet as bit zero and ending the numbering with bit 8 of the first octet. Each bit is assigned a numerical value of 2N,
where N is its position in the above numbering sequence. The value of the two's complement binary number is obtained by
summing the numerical values assigned to each bit for those bits which are set to one, excluding bit 8 of the first octet, and then
reducing this value by the numerical value assigned to bit 8 of the first octet if that bit is set to one.

See https://en.wikipedia.org/wiki/Two%27s_complement, the table on the right should be obvious enough to recognize as a set of DER encoded integers.

edit: I'm not saying this PR is the right way to do so, but, the feature request is real enough.

[dcousens]

That said, what @axic has written above is a bit odd. Two's complement is strictly a way of encoding integers in binary.

[axic]

Well what I've written uses code what's available. Once there's bitwise negation (#72) you could use it.

Sample usage of the proposed methods:

new BN('fffffffffffffffffffffffffffffffe', 16).fromTwos(128) // equals -2
new BN(-2).toTwos(128).toString(16) // equals fffffffffffffffffffffffffffffffe

Also you could change toTwos() to output an array (or change toArray() to have a parameter for it) or string (or change toString() to have a parameter for it). All of these I think is a lot of code duplication, hence I have chosen the above way assuming users of this library are knowledgable.

Similarly, the functionality of fromTwos() could be added to the constructor, where both _initArray() and _parseHex() would need to be changed. Again, I think a lot of code duplication.

Sample usage of extending the current functions (where the last boolean is true for two's complement):

new BN(-2).toArray('be', 128, true)
new BN(-2).toString(16, 32, true)
new BN('fffffffffffffffffffffffffffffffe', 16, 'be', true) // equals -2

Hiding them in the proper places would add code duplication and perhaps more complexity to those methods, while keeping the behaviour clean for the user. I'm not sure which one of these two are more desired. Then again you could make my suggested methods internal and use them in toArray(), _initArray(), _parsehex().

About usability: most of the serialization methods support both signed and unsigned integers and I've yet to see a mainstream serializer not using two's complement for negative numbers. Next to DER (used by bitcoin), all the ethereum javascript libraries implement their own helpers for the above.

My other reason of having this in the library: in the future it could be well optimised with having access to internals (e.g. using bitwise negation or doing other shortcuts).

[indutny]

Argh, two's complement. Gosh, I always forget what it actually means. I'm +1 for having it in bn.js, especially considering that asn1.js is probably broken for negative numbers...

@dcousens may I ask you to give a suggestion to @axic on how it could be implemented more efficiently/better?

[dcousens]

@axic I'll have a deeper look into this. Want to set up a PR branch we can both work on?

[axic]

@dcousens happy to do that, should I create a branch on my repo?

[dcousens]

@axic sounds like a plan

[axic]

@dcousens sorry it took a while to find the time, it is in the feature/twos-complement branch on my fork: https://github.com/axic/bn.js/tree/feature/twos-complement

Added a somewhat extensive number of tests and the simple implementation from above, which works by returning a new BN instance.

[dcousens]

Awesome @axic, I'll have a look through it soon 👍

[axic]

@dcousens I've just created a PR (#77) for bitwise NOT, which can be used for the two's complement. It is much faster.

Substraction based:

Benchmarking: fromTwos
bn.js#fromTwos x 3,440,833 ops/sec ±4.86% (9 runs sampled)
------------------------
Fastest is bn.js#fromTwos
========================
Benchmarking: toTwos
bn.js#toTwos x 1,250,581 ops/sec ±6.07% (8 runs sampled)
------------------------
Fastest is bn.js#toTwos
========================

Using bitwise not:

Benchmarking: fromTwos
bn.js#fromTwos x 3,702,350 ops/sec ±5.60% (9 runs sampled)
------------------------
Fastest is bn.js#fromTwos
========================
Benchmarking: toTwos
bn.js#toTwos x 3,970,022 ops/sec ±5.07% (9 runs sampled)
------------------------
Fastest is bn.js#toTwos
========================

[dcousens]

Awesome @axic 👍

[axic]

@dcousens having seen the code, does it make more sense now?

p.s. Once #77 is merged I'll push an update to the two's complement tree. Also with that it could have an in-place version.

[dcousens]

@axic the strangeness of the above solution is that a BN is returned, instead of a Buffer (or Array)

[axic]

@dcousens There are just too many options already (String, Array and hopefully Buffer will be the third soon) and that would pollute the conversion code. Having a parameter or tons of alternate versions looks ugly to me. And the same applies to fromTwos().

My reasoning is that users of this library are knowledgable and can handle new BN("-33", 10).toTwos(256).toArray('be', 32).

I know two's is most commonly part of the serialization process, but it is just another number.

[dcousens]

@axic IMHO its only really used as an encoding format, but, sure.

[axic]

@dcousens to argue its not only an encoding format: many CPUs would keep negative numbers in two's complement in registers/memory and that is one of the reasons there is a differentiation between arithmetic and logical shift instructions

[dcousens]

But is that ever likely to be a reasonable expectation for someone in user land?
Even in your example its an implementation detail.

[axic]

@dcousens sorry, I don't entirely get you? Writing assembly is part of userland.

[dcousens]

I meant in terms of this library.

For example, if I took the twosComplement of the number 1, I'd still expect the number 1 to be 1, as part of being re-interpreted as its twos complement.
What this does, is actually change the number to its binary equivalent in twos complement?
That, IMHO, doens't make sense in terms of the API, as its a binary encoding in most usages.

[axic]

twosComplement of 1 is 1 :)

[dcousens]

How about 0x80ff

[axic]

@dcousens honestly I do not see much difference, but I am really open to see your suggestion how it should be presented to the user

[axic]

@dcousens I gave some extra thought about this and I think for your ideal situation to happen, you would need to change bn.js in its entirety to work based off two's complement arithmetic, e.g. change all the methods to work based off that representation instead of the negative flag which is used allover the place. Might be cleaner that way, but that seems to be enormous work? Perhaps it could be faster in cases.

[axic]

An idea if we don't want a major change: currently the base parameter in the constructor/to* expects a number, but also accepts hex, which it assumes as base 16.

How about keeping numeral arguments as they are today (e.g. base-16 with a negative sign), while reserving base === 'hex' for two's complement. It is a breaking change (although I think most projects use 16 and not hex), but would be aligned with the behaviour of Buffer too.

[indutny]

Well, breaking change is a breaking change. So it will cause a semver-major anyway.

I don't think that we want to default to twos-complement. I'd rather go for a separate API methods...

[dcousens]

This exists, see BN.prototype.toTwos and BN.fromTwos.