1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
//! Git pack bitmap name-hash functions (`pack_name_hash` / `pack_name_hash_v2`).
//!
//! These match the inline implementations in Git's `pack-objects.h` and are used
//! for bitmap index name-hash fields and `test-tool name-hash` stability tests.
/// Git's legacy pack name hash (version 1): a sortable number from the last
/// sixteen non-whitespace characters of `name`.
#[must_use]
pub fn pack_name_hash(name: &str) -> u32 {
pack_name_hash_extend(0, name.as_bytes())
}
/// Continue a [`pack_name_hash`] over more bytes.
///
/// `pack_name_hash_extend(pack_name_hash(a), b)` equals `pack_name_hash(a + b)`,
/// so tree walks can carry a directory prefix's hash instead of the path string.
#[must_use]
pub(crate) fn pack_name_hash_extend(mut hash: u32, bytes: &[u8]) -> u32 {
for &c in bytes {
if c.is_ascii_whitespace() {
continue;
}
hash = (hash >> 2).wrapping_add(u32::from(c) << 24);
}
hash
}
/// [`pack_name_hash`] of the path `parent/name`, or of `name` alone for a root tree
/// entry, where `parent` is the hash of the containing directory's path.
#[must_use]
pub(crate) fn pack_name_hash_child(parent: Option<u32>, name: &[u8]) -> u32 {
match parent {
None => pack_name_hash_extend(0, name),
Some(hash) => pack_name_hash_extend(pack_name_hash_extend(hash, b"/"), name),
}
}
/// The v2 pack name hash: path-component aware, used for newer bitmap formats.
#[must_use]
pub fn pack_name_hash_v2(name: &[u8]) -> u32 {
let mut hash: u32 = 0;
let mut base: u32 = 0;
for &c in name {
if c == 0 {
break;
}
if c.is_ascii_whitespace() {
continue;
}
if c == b'/' {
base = (base >> 6) ^ hash;
hash = 0;
} else {
// `u8::reverse_bits` is the stdlib equivalent of the per-byte
// bit-reversal step; it lowers to a single instruction.
let c = u32::from(c.reverse_bits());
hash = (hash >> 2).wrapping_add(c << 24);
}
}
(base >> 6) ^ hash
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn name_hash_matches_git_test_vectors() {
let cases = [
("first", 2_582_249_472, 1_763_573_760),
("second", 2_289_942_528, 1_188_134_912),
("third", 2_300_837_888, 1_130_758_144),
(
"a/one-long-enough-for-collisions",
2_544_516_325,
3_963_087_891,
),
(
"b/two-long-enough-for-collisions",
2_544_516_325,
4_013_419_539,
),
(
"many/parts/to/this/path/enough/to/collide/in/v2",
1_420_111_091,
1_709_547_268,
),
(
"enough/parts/to/this/path/enough/to/collide/in/v2",
1_420_111_091,
1_709_547_268,
),
];
for (path, v1, v2) in cases {
assert_eq!(pack_name_hash(path), v1, "v1 {path}");
assert_eq!(pack_name_hash_v2(path.as_bytes()), v2, "v2 {path}");
}
}
#[test]
fn child_hash_matches_full_path_hash() {
assert_eq!(
pack_name_hash_child(None, b"Cargo.toml"),
pack_name_hash("Cargo.toml")
);
let src = pack_name_hash_child(None, b"src");
let cargo = pack_name_hash_child(Some(src), b"cargo");
assert_eq!(cargo, pack_name_hash("src/cargo"));
assert_eq!(
pack_name_hash_child(Some(cargo), b"lib.rs"),
pack_name_hash("src/cargo/lib.rs")
);
}
#[test]
fn extend_continues_a_prefix_hash() {
for path in [
"a/one-long-enough-for-collisions",
"many/parts/to/this/path/enough/to/collide/in/v2",
"dir with spaces/f.txt",
"f",
] {
for split in 0..=path.len() {
let (head, tail) = path.split_at(split);
assert_eq!(
pack_name_hash_extend(pack_name_hash(head), tail.as_bytes()),
pack_name_hash(path),
"{path} split at {split}"
);
}
}
}
}