Skip to content

Huffman Bug Fix#699

Merged
dr-orlovsky merged 2 commits intorust-bitcoin:masterfrom
JeremyRubin:huffman-cleanups
Nov 23, 2021
Merged

Huffman Bug Fix#699
dr-orlovsky merged 2 commits intorust-bitcoin:masterfrom
JeremyRubin:huffman-cleanups

Conversation

@JeremyRubin
Copy link
Copy Markdown
Contributor

@JeremyRubin JeremyRubin commented Nov 15, 2021

I noticed one cleanup & one bugfix while looking into the huffman algorithm:

  1. the cleanup: we can use a u128 to guarantee no overflows, and saturating_add to guarantee reasonable behavior in any case
  2. the bug: the binary heap is a max heap so the behavior ends up merging the nodes of the most likely entries repeatedly. a huffman encoder requires merging the least likely elements, so it should be reversed.

@JeremyRubin
Copy link
Copy Markdown
Contributor Author

JeremyRubin commented Nov 15, 2021

a currently failing test #700

that passes if rebased on this branch.

Kixunil
Kixunil reviewed Nov 15, 2021
View reviewed changes
Copy link
Copy Markdown
Collaborator

@Kixunil Kixunil left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think u128 is not supported on all platforms. Could it be a problem for embedded?

src/util/taproot.rs Outdated
Copy link
Copy Markdown
Collaborator

@Kixunil Kixunil Nov 15, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If it can never happen, why not just have +?

Copy link
Copy Markdown
Contributor Author

@JeremyRubin JeremyRubin Nov 15, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

i'd rather define the behavior correctly here should it ever overflow rather than wrapping around. Perhaaps defensively, but it'd be possible someone were to update the types/sizes later without appreciating this point.

@JeremyRubin
Copy link
Copy Markdown
Contributor Author

JeremyRubin commented Nov 15, 2021

I think u128 is supported on all platforms, either with a native type or a wrapper. We could also do the same trick with u32 and u64 and it wouldn't be an issue either (u32 is plenty IMO).

sanket1729
sanket1729 reviewed Nov 15, 2021
View reviewed changes
Copy link
Copy Markdown
Member

@sanket1729 sanket1729 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for testing this. ACK modulo removing the error variant.

src/util/taproot.rs Outdated
Copy link
Copy Markdown
Member

@sanket1729 sanket1729 Nov 15, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can you also remove the Error variant from the error enum?

Copy link
Copy Markdown
Contributor Author

@JeremyRubin JeremyRubin Nov 15, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

done

@sanket1729 sanket1729 added the bug label Nov 15, 2021
@sanket1729 sanket1729 added this to the 0.28.0 milestone Nov 15, 2021
sanket1729
sanket1729 approved these changes Nov 15, 2021
View reviewed changes
Copy link
Copy Markdown
Member

@sanket1729 sanket1729 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ACK f2a6827

@JeremyRubin JeremyRubin mentioned this pull request Nov 15, 2021
Merged
dr-orlovsky
dr-orlovsky approved these changes Nov 23, 2021
View reviewed changes
Copy link
Copy Markdown
Collaborator

@dr-orlovsky dr-orlovsky left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

utACK f2a6827

@dr-orlovsky dr-orlovsky merged commit 5286d0a into rust-bitcoin:master Nov 23, 2021
dr-orlovsky added a commit that referenced this pull request Dec 11, 2021
@dr-orlovsky
Merge #701: Decrease Huffman Weights to u32
9ae0f05 
1518517 Decrease Huffman weight type to 32 bits (Jeremy Rubin)

Pull request description:

  This builds on #699 but is the more bikesheddable part since it changes the API.

  > u32 of weight should be enough for any branch.
  -- Bill Gates

ACKs for top commit:
  dr-orlovsky:
    utACK 1518517
  Kixunil:
    ACK 1518517

Tree-SHA512: 9c507ae6129dda8dc069b0a142181a78cf89cb3ebf9d2169c46662822cb4ea9ed075bf484528f5399fe0ed383a425174a702e2d685f31c246f5a86c46ed17c3a
@dr-orlovsky dr-orlovsky mentioned this pull request Jan 15, 2022
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@Kixunil Kixunil Kixunil left review comments

@sanket1729 sanket1729 sanket1729 approved these changes

+1 more reviewer

@dr-orlovsky dr-orlovsky dr-orlovsky approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

bug

Projects

None yet

Milestone

0.28.0

Development

Successfully merging this pull request may close these issues.

4 participants

@JeremyRubin @dr-orlovsky @Kixunil @sanket1729