Skip to content

mlsbset: make Encode() constant time#639

Merged
bwesterb merged 8 commits into
mainfrom
bas/gw9
Jul 15, 2026
Merged

mlsbset: make Encode() constant time#639
bwesterb merged 8 commits into
mainfrom
bas/gw9

Conversation

@bwesterb

@bwesterb bwesterb commented Jul 14, 2026

Copy link
Copy Markdown
Member

@devin-ai-integration devin-ai-integration Bot left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

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

✅ Devin Review: No Issues Found

Devin Review analyzed this PR and found no bugs or issues to report.

Open in Devin Review

@lukevalenta lukevalenta left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

LGTM. Some suggestions and one fix to the comments.

Comment thread math/mlsbset/mlsbset.go Outdated
Comment thread math/mlsbset/mlsbset.go Outdated
Comment thread math/mlsbset/mlsbset.go Outdated
Comment thread math/mlsbset/mlsbset.go Outdated
Comment thread math/mlsbset/mlsbset.go Outdated
Comment thread math/mlsbset/mlsbset.go Outdated
Comment thread math/mlsbset/mlsbset.go Outdated
Comment thread math/mlsbset/mlsbset.go Outdated
Comment thread math/mlsbset/mlsbset.go Outdated
Comment thread math/mlsbset/mlsbset.go
c.Rsh(c, 1)
c.Sub(c, &bi)
si := s[i%m.p.D]
kbit := uint64(k[i>>3]>>(i&7)) & 1

@lukevalenta lukevalenta Jul 15, 2026

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

Possibly worth extracting this into a helper function for readability (used twice in this function and once in signs):

Suggested change
kbit := uint64(k[i>>3]>>(i&7)) & 1
kbit := uint64(bit(k, i))

The new function:

// bit returns the i-th bit of buf in little-endian order, as 0 or 1.
func bit(buf []byte, i uint) byte {
	return byte(buf[i>>3]>>(i&7)) & 1
}

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

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

prefer to keep it inline for easier reading

bwesterb and others added 7 commits July 15, 2026 17:35
Co-authored-by: Luke Valenta <lvalenta@cloudflare.com>
Co-authored-by: Luke Valenta <lvalenta@cloudflare.com>
Co-authored-by: Luke Valenta <lvalenta@cloudflare.com>
Co-authored-by: Luke Valenta <lvalenta@cloudflare.com>
Co-authored-by: Luke Valenta <lvalenta@cloudflare.com>
Co-authored-by: Luke Valenta <lvalenta@cloudflare.com>
Co-authored-by: Luke Valenta <lvalenta@cloudflare.com>
@bwesterb bwesterb merged commit 0f4a282 into main Jul 15, 2026
5 of 6 checks passed
@bwesterb bwesterb deleted the bas/gw9 branch July 15, 2026 15:37
Comment thread math/mlsbset/mlsbset.go

// Original algorithm starts with c := k >> D, then computes
//
// b_(i-D) = s_(j%D) * lsb(c)

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

Suggested change
// b_(i-D) = s_(j%D) * lsb(c)
// b_(i-D) = s_(i%D) * lsb(c)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants