#![forbid(unsafe_code, missing_debug_implementations, missing_docs)]
#![cfg_attr(test, deny(warnings))]
extern crate flat_tree as flat;
extern crate sparse_bitfield as bitfield;
mod proof;
mod verification;
pub use self::bitfield::{Bitfield, Change};
pub use self::proof::Proof;
pub use self::verification::Verification;
use std::{cmp, convert};
#[derive(Debug)]
pub struct TreeIndex {
bitfield: Bitfield,
}
impl TreeIndex {
#[inline]
pub fn new(bitfield: Bitfield) -> Self {
TreeIndex { bitfield }
}
#[inline]
pub fn get(&mut self, index: usize) -> bool {
self.bitfield.get(index)
}
#[inline]
pub fn set(&mut self, mut index: usize) -> Change {
if self.bitfield.set(index, true).is_unchanged() {
return Change::Unchanged;
}
while self.bitfield.get(flat::sibling(index)) {
index = flat::parent(index);
if self.bitfield.set(index, true).is_unchanged() {
break;
}
}
Change::Changed
}
#[inline]
pub fn proof<'a>(
&'a mut self,
index: usize,
include_hash: bool,
nodes: &'a mut impl convert::AsMut<Vec<usize>>,
remote_tree: &mut Self,
) -> Option<Proof> {
let digest = 0;
self.proof_with_digest(index, digest, include_hash, nodes, remote_tree)
}
pub fn proof_with_digest<'a>(
&'a mut self,
index: usize,
mut digest: usize,
include_hash: bool,
nodes: &'a mut impl convert::AsMut<Vec<usize>>,
remote_tree: &mut Self,
) -> Option<Proof> {
let nodes = nodes.as_mut();
if !self.get(index) {
return None;
}
if include_hash {
nodes.push(index);
}
if digest == 1 {
let verified_by = 0;
return Some(Proof::new(index, verified_by, nodes));
}
let mut roots = vec![]; let mut next = index;
let mut sibling;
let has_root = digest & 1;
digest >>= 1;
while digest > 0 {
if digest == 1 && has_root != 0 {
if self.get(next) {
remote_tree.set(next);
}
let next_sibling = flat::sibling(next);
if next_sibling < next {
next = next_sibling
}
flat::full_roots(flat::right_span(next) + 2, &mut roots);
for root in &roots {
if self.get(*root) {
remote_tree.set(*root);
}
}
break;
}
sibling = flat::sibling(next);
if !is_even(digest) && self.get(sibling) {
remote_tree.set(sibling);
}
next = flat::parent(next);
digest >>= 1;
}
next = index;
while !remote_tree.get(next) {
sibling = flat::sibling(next);
if !self.get(sibling) {
let verified_by = self.verified_by(next).node;
let mut roots = vec![];
flat::full_roots(verified_by, &mut roots);
for root in roots {
if root != next && !remote_tree.get(root) {
nodes.push(root);
}
}
return Some(Proof::new(index, verified_by, nodes));
} else if !remote_tree.get(sibling) {
nodes.push(sibling);
}
next = flat::parent(next);
}
let verified_by = 0;
Some(Proof::new(index, verified_by, nodes))
}
#[inline]
pub fn digest(&mut self, index: usize) -> usize {
if self.get(index) {
return 1;
}
let mut digest = 0;
let mut next = flat::sibling(index);
let max = cmp::max(next + 2, self.bitfield.len());
let mut bit = 2;
let mut depth = flat::depth(index);
let mut parent = flat::parent_with_depth(next, depth);
depth += 1;
while (flat::right_span(next) < max) || flat::left_span(parent) > 0 {
if self.get(next) {
digest |= bit;
}
if self.get(parent) {
digest |= 2 * bit + 1;
if digest + 1 == 4 * bit {
return 1;
}
return digest;
}
next = flat::sibling(parent);
parent = flat::parent_with_depth(next, depth);
depth += 1;
bit *= 2;
}
digest
}
#[inline]
pub fn blocks(&mut self) -> usize {
let mut top = 0;
let mut next = 0;
let max = self.bitfield.len();
while flat::right_span(next) < max {
next = flat::parent(next);
if self.get(next) {
top = next;
}
}
if self.get(top) {
self.verified_by(top).node / 2
} else {
0
}
}
#[inline]
pub fn roots(&mut self, roots: &mut Vec<usize>) {
flat::full_roots(2 * self.blocks(), roots)
}
#[inline]
pub fn verified_by(&mut self, index: usize) -> Verification {
let has_index = self.get(index);
if !has_index {
return Verification { node: 0, top: 0 };
}
let mut depth = flat::depth(index);
let mut top = index;
let mut parent = flat::parent_with_depth(top, depth);
depth += 1;
while self.get(parent) && self.get(flat::sibling(top)) {
top = parent;
parent = flat::parent_with_depth(top, depth);
depth += 1;
}
depth -= 1;
while depth != 0 {
top = flat::left_child_with_depth(
flat::index(depth, flat::offset_with_depth(top, depth) + 1),
depth,
).unwrap();
depth -= 1;
while !self.get(top) && depth > 0 {
top = flat::left_child_with_depth(top, depth).unwrap();
depth -= 1;
}
}
let node = if self.get(top) { top + 2 } else { top };
Verification { node, top }
}
}
impl Default for TreeIndex {
#[inline]
fn default() -> Self {
TreeIndex {
bitfield: Bitfield::new(1024),
}
}
}
#[inline]
fn is_even(n: usize) -> bool {
match n & 1 {
0 => true,
1 => false,
_ => panic!(format!(
"Bitshift failure. Received bit {}. Expected 1 or 0",
n
)),
}
}