rust-bitcoin / rust-bech32

Bech32 format encoding and decoding
MIT License
94 stars 49 forks source link

Introduce `FieldVec` and improve `Polynomial` and `InvalidResidueError` #204

Closed apoelstra closed 4 weeks ago

apoelstra commented 1 month ago

This introduces a new internal type FieldVec which is basically a backing array for checksum residues with some fiddly logic to work in a noalloc context.

Unlike ArrayVec or other similar types, this one's semantics are "an unbounded vector if you have an allocator, a bounded vector otherwise". If you go outside of the bounds without an allocator the code will panic, but our use of it ensures that this is never exposed to a user.

It also assumes that it's holding a Default type which lets us avoid unsafety (and dismisses the potential performance cost because this array is never expected to have more than 10 or 20 elements, even when it is "unbounded").

Using this backing, it improves Polynomial and removes the alloc bound from it; using this, it puts Polynomial into a new InvalidResidueError type, which will allow users to extract the necessary information from a checksum error to run the error correction algorithm. (The resulting change to an error type makes this an API-breaking change, though I don't think that anything else here is API-breaking.)

The next PR will actually implement correction :).

apoelstra commented 1 month ago

Clicked "resolve" on the conversations we agreed were not actionable.

Force-pushed to address the other comments.

apoelstra commented 1 month ago

Second force-push was to fix a bug converting residues to polynomials which I noticed when working on the next PR.

apoelstra commented 1 month ago

Ok, I have working error correction code now based on this PR :). I will stop iterating on it until somebody reviews it.

tcharding commented 1 month ago

Is a further non-math review useful by me, I can do it if so. I don't want to bother the PR with petty concerns if not.

apoelstra commented 1 month ago

I think it'd be valuable, yeah, if you're willing to take the time.

tcharding commented 1 month ago

I'll make a coffee :)

apoelstra commented 1 month ago

Improved doccomments and added a bunch of unit tests. Also added missing Index<Range<usize>> impl on fieldvec.