| 81 | } |
| 82 | |
| 83 | pub(crate) fn decode( |
| 84 | bytes: &[u8], |
| 85 | mut lookup: impl FnMut(&[u8; 32]) -> PristineResult<Option<[u8; 64]>>, |
| 86 | ) -> PristineResult<Vec<Hash>> { |
| 87 | if !bytes.starts_with(MAGIC) || bytes.len() % 32 == 4 { |
| 88 | return decode_legacy(bytes); |
| 89 | } |
| 90 | if bytes.len() != 44 { |
| 91 | return Err(invalid( |
| 92 | "Git shared closure root must contain exactly 44 bytes", |
| 93 | )); |
| 94 | } |
| 95 | let count = u32::from_le_bytes(bytes[8..12].try_into().unwrap()); |
| 96 | let root: [u8; 32] = bytes[12..].try_into().unwrap(); |
| 97 | // Never allocate from an untrusted count before checking the tree. |
| 98 | let mut closure = Vec::new(); |
| 99 | if count == 0 && root == EMPTY { |
| 100 | return Ok(closure); |
| 101 | } |
| 102 | let mut stack = vec![(root, 0u16)]; |
| 103 | let mut visited = 0u64; |
| 104 | while let Some((id, depth)) = stack.pop() { |
| 105 | visited += 1; |
| 106 | if id == EMPTY || depth > 256 || visited > 2 * u64::from(count) { |
| 107 | return Err(invalid( |
| 108 | "Git closure tree has invalid structure or declared length", |
| 109 | )); |
| 110 | } |
| 111 | let node = lookup(&id)?.ok_or_else(|| invalid("Git closure tree node is missing"))?; |
| 112 | if node_id(&node) != id { |
| 113 | return Err(invalid( |
| 114 | "Git closure tree node failed content-hash verification", |
| 115 | )); |
| 116 | } |
| 117 | let left: [u8; 32] = node[..32].try_into().unwrap(); |
| 118 | let right: [u8; 32] = node[32..].try_into().unwrap(); |
| 119 | if left == EMPTY { |
| 120 | if closure.len() >= count as usize |
| 121 | || closure |
| 122 | .last() |
| 123 | .is_some_and(|hash: &Hash| hash.as_bytes() >= &right) |
| 124 | { |
| 125 | return Err(invalid( |
| 126 | "Git closure leaves are not strictly ordered or exceed declared length", |
| 127 | )); |
| 128 | } |
| 129 | closure.push(Hash::from_bytes(right)); |
| 130 | } else { |
| 131 | if right == EMPTY { |
| 132 | return Err(invalid("Git closure branch has an empty child")); |
| 133 | } |
| 134 | stack.push((right, depth + 1)); |
| 135 | stack.push((left, depth + 1)); |
| 136 | } |
| 137 | } |
| 138 | if closure.len() != count as usize { |
| 139 | return Err(invalid( |
| 140 | "Git closure tree length differs from its declared length", |