diff options
| author | bryan newbold <bnewbold@robocracy.org> | 2023-03-09 12:26:22 -0800 |
|---|---|---|
| committer | bryan newbold <bnewbold@robocracy.org> | 2023-03-09 12:26:22 -0800 |
| commit | 1c5ce5dd9b9c0883fa660c415c7336d6e1382e32 (patch) | |
| tree | 1461d7e7cbbb9b4f28c258e7794a8b0328aad033 | |
| parent | 965b7b35f931865a1b21a681b6f6665703857c61 (diff) | |
| download | adenosine-1c5ce5dd9b9c0883fa660c415c7336d6e1382e32.tar.gz adenosine-1c5ce5dd9b9c0883fa660c415c7336d6e1382e32.zip | |
mst: switch to fanout=4
| -rw-r--r-- | adenosine/src/mst.rs | 42 |
1 files changed, 31 insertions, 11 deletions
diff --git a/adenosine/src/mst.rs b/adenosine/src/mst.rs index c695ac6..7c9d4ee 100644 --- a/adenosine/src/mst.rs +++ b/adenosine/src/mst.rs @@ -175,12 +175,16 @@ pub fn collect_mst_keys( Ok(()) } +// "fanout=4", meaning counting 2 bits at a time fn leading_zeros(key: &[u8]) -> u8 { let digest = sha256::digest(key); let digest = digest.as_bytes(); for (i, c) in digest.iter().enumerate() { + if *c >= b'4' { + return (i * 2) as u8; + } if *c != b'0' { - return i as u8; + return (i * 2 + 1) as u8; } } digest.len() as u8 @@ -199,12 +203,13 @@ fn leading_zeros(key: &[u8]) -> u8 { fn test_leading_zeros() { assert_eq!(leading_zeros(b""), 0); assert_eq!(leading_zeros(b"asdf"), 0); + assert_eq!(leading_zeros(b"blue"), 1); assert_eq!(leading_zeros(b"2653ae71"), 0); - assert_eq!(leading_zeros(b"88bfafc7"), 1); - assert_eq!(leading_zeros(b"2a92d355"), 2); - assert_eq!(leading_zeros(b"884976f5"), 3); - assert_eq!(leading_zeros(b"app.bsky.feed.post/454397e440ec"), 2); - assert_eq!(leading_zeros(b"app.bsky.feed.post/9adeb165882c"), 4); + assert_eq!(leading_zeros(b"88bfafc7"), 2); + assert_eq!(leading_zeros(b"2a92d355"), 4); + assert_eq!(leading_zeros(b"884976f5"), 6); + assert_eq!(leading_zeros(b"app.bsky.feed.post/454397e440ec"), 4); + assert_eq!(leading_zeros(b"app.bsky.feed.post/9adeb165882c"), 8); } pub fn generate_mst( @@ -332,12 +337,27 @@ fn test_common_prefix_len_wide() { assert_eq!("👩👧👧".as_bytes().len(), 18); // 8 in javascript // many of the below are different in JS; in Rust we *must* cast down to bytes to count - assert_eq!(common_prefix_len("jalapeño".as_bytes(), "jalapeno".as_bytes()), 6); - assert_eq!(common_prefix_len("jalapeñoA".as_bytes(), "jalapeñoB".as_bytes()), 9); - assert_eq!(common_prefix_len("coöperative".as_bytes(), "coüperative".as_bytes()), 3); - assert_eq!(common_prefix_len("abc💩abc".as_bytes(), "abcabc".as_bytes()), 3); + assert_eq!( + common_prefix_len("jalapeño".as_bytes(), "jalapeno".as_bytes()), + 6 + ); + assert_eq!( + common_prefix_len("jalapeñoA".as_bytes(), "jalapeñoB".as_bytes()), + 9 + ); + assert_eq!( + common_prefix_len("coöperative".as_bytes(), "coüperative".as_bytes()), + 3 + ); + assert_eq!( + common_prefix_len("abc💩abc".as_bytes(), "abcabc".as_bytes()), + 3 + ); assert_eq!(common_prefix_len("💩abc".as_bytes(), "💩ab".as_bytes()), 6); - assert_eq!(common_prefix_len("abc👩👦👦de".as_bytes(), "abc👩👧👧de".as_bytes()), 13); + assert_eq!( + common_prefix_len("abc👩👦👦de".as_bytes(), "abc👩👧👧de".as_bytes()), + 13 + ); } fn serialize_wip_tree( |