Add add_reverse method

[GeorgeGkas]

We currently implement Add and AddAssign traits that "works just like adding numbers longhand on paper" (right-to-left). It would be nice to have a reverse_add() method that does addition from left-to-right. We can use the same function semantics as add_assign but do not use the std::iter::Rev trait that reverse the iteration, i.e. remove the .rev() call on lines 2230 and 2231. I have already tested it and works fine.

Here is an example:

use bitvec::prelude::*;

let a = bitvec![1, 0, 1, 0];
let b = bitvec![1, 1, 0, 0];
let s = a.add_reverse(&b);
assert_eq!(bitvec![0, 0, 0, 1], s);

Use case
In the paper of SIMD json parser, the addition operation is done left-to-right (e.g page 7, Fig.3 C = B + ES). Of course, I do not expect this library to be used in high performance applications, but I found quite convenient to have a such method.

[myrrlyn]

Should this addition perform carry-propagation to the right (on BitVec only)? What is the sum of bitvec![1; 4] + bitvec![1]; should it be bitvec![0; 4] or bitvec![0, 0, 0, 0, 1]?

Of course, I do not expect this library to be used in high performance applications,

I do expect this; while the computation required to demangle the pointer into an individual bit access is certainly a non-zero expense, inadequate performance is always a valid bug report.

[GeorgeGkas]

We should perform carry-propagation as the regular add function does (see the example).

In AddAssign trait documentation see the last paragraph:

Numeric arithmetic is provided on BitVec as a convenience. Serious numeric computation on variable-length integers should use the num_bigint crate instead, which is written specifically for that use case. BitVecs are not intended for arithmetic, and bitvec makes no guarantees about sustained correctness in arithmetic at this time.

This is why I supposed that we do not target high performance apps. Should we update the doc to remove ambitiousness (maybe was only me that understood it wrong)? Maybe we should add:

However this crate targets high performance applications and any inadequate performance is always a valid bug report.

[myrrlyn]

My reluctance to encourage use of BitVec as a numeric type is that the raw memory underneath any handle in this crate is explicitly not guaranteed to have a bit-pattern representation that makes sense when interpreted as any other type, including "integer". The default Cursor, BigEndian, produces raw bit-patterns that do not match CPU arithmetic instruction requirements (bitvec![1; 4] is 0xF0 rather than 0x0F). The alternate provided Cursor, LittleEndian, does produce a bit-pattern that can be used in CPU arithmetic instructions, but this is a coincidence rather than an explicit design goal.

As such, the arithmetic implementations are software reproductions of a ripple-carry adder, which I have made no effort to optimize. It's low-hanging fruit for a CLA design over RCA if this is something users wind up wanting.

I'll get an implementation for this issue done this afternoon. Do you have a version to which you'd like it backported, or is current head sufficient?

[GeorgeGkas]

Why bitvec![1; 4] is 0xF0 rather than 0x0F? Does the current implementation of the crate affects the way that bit-patterns operate or is it something with the compiler, or the CPU?

I cannot interpret the meaning of "Do you have a version to which you'd like it backported, or is current head sufficient?", would you mind to explain it with other words?

[myrrlyn]

The default Cursor the macro uses is BigEndian, which walks elements from the most significant bit towards the least. bitvec![1] thus creates the byte 0x80, not 0x01. This behavior is the desired effect for network protocols (the reason I initially wrote this) but the very wrong effect for binary arithmetic.

The latest version of the crate is 0.13; since this is a purely additive change, I can put it in a new patch release on an older minor version, or just release 0.14

[GeorgeGkas]

Thank you for the explanation. Semantic versioning defines the increment of minor version when backwards compatible functionality is introduced to the public API. I think this is the best candidate, by the time that patch version is used most of the times for backwards compatible bug fixes, but I leave it to you to decide.

[myrrlyn]

It's on master; I haven't issued 0.14.0 yet. I will do so tomorrow unless you have additional feedback. Let me know if this does what you had in mind!

[GeorgeGkas]

Looks good.