luct_core/tiling/
tile.rs

1use crate::{
2    store::Hashable,
3    tiling::{TilingError, index_to_url},
4    tree::{HashOutput, Node, NodeKey},
5};
6use std::{num::NonZeroU8, sync::Arc};
7
8#[derive(Debug, Clone, PartialEq, Eq)]
9pub struct TileId {
10    level: u8,
11    index: u64,
12    partial: Option<NonZeroU8>,
13    tree_size: u64,
14}
15
16impl TileId {
17    /// Returns the [`TileId`] of the tile, which contains the [`NodeKey`].
18    ///
19    /// The `tree_height` is used to calculate, wether the tile in question should be partial or not.
20    pub fn from_node_key(key: &NodeKey, tree_size: u64) -> Option<Self> {
21        if !key.is_balanced() {
22            panic!(
23                "Tried to build unbalanced node key {:?}. This is a bug",
24                key
25            );
26        }
27
28        // Compute from the size of the node key, what level of tiles we expect the
29        let level = key.size().next_power_of_two().ilog2();
30        let level: u8 = (level / 8).try_into().unwrap();
31
32        // Compute the size of the base node keys of the tile, i.e. the nodes that are actually contained in the tiles.
33        let steps: u64 = 2u64.pow(8 * level as u32);
34        let tile_width = 256 * steps;
35
36        // Compute the index of the tile, that should contain the node
37        let index = key.start / tile_width;
38
39        // Check if we need to fetch a partial tile, and if so, compute it's size
40        let tile_end = (index + 1) * tile_width;
41        let partial = if tile_end < tree_size {
42            None
43        } else {
44            let partial = tree_size % tile_width;
45            let partial: u8 = (partial >> (8 * level)).try_into().unwrap();
46
47            Some(NonZeroU8::new(partial).unwrap())
48        };
49
50        Some(Self {
51            level,
52            index,
53            partial,
54            tree_size,
55        })
56    }
57
58    /// Returns the [`Url`](url::Url) path, at which this tile should be found
59    ///
60    /// Append this path to the `tile_url`, to get the full path.
61    pub fn as_url(&self) -> String {
62        let index_url = index_to_url(self.index);
63
64        match self.partial {
65            Some(partial) => format!("tile/{}/{}.p/{}", self.level, index_url, partial),
66            None => format!("tile/{}/{}", self.level, index_url),
67        }
68    }
69
70    /// Create a [`Tile`], by adding the data to this [`TileId`]
71    ///
72    /// # Returns:
73    ///
74    /// - `None`: If the length of the data is not a multiple if 32
75    /// - `Some(Tile)` otherwise
76    pub fn with_data(self, data: Arc<Vec<u8>>) -> Result<Tile, TilingError> {
77        if !data.len().is_multiple_of(32) {
78            return Err(TilingError::MalformedTile);
79        }
80
81        // Check that length actually matches the partial value
82        let expected_len = match self.partial {
83            Some(val) => usize::from(u8::from(val)),
84            None => 256usize,
85        };
86        if data.len() != expected_len * 32 {
87            // TODO: Introduce an error type for size mismatch
88            return Err(TilingError::MalformedTile);
89        }
90
91        Ok(Tile { id: self, data })
92    }
93
94    /// Returns `true`, if this [`TileId`] is partial, `false` otherwise
95    pub fn is_partial(&self) -> bool {
96        self.partial.is_some()
97    }
98
99    /// Turn a partial [`TileId`] into one that is not partial
100    ///
101    /// Does nothing if [`TileId`] is already partial.
102    pub fn into_unpartial(mut self) -> Self {
103        self.partial = None;
104        self
105    }
106}
107
108#[derive(Debug, Clone, PartialEq, Eq)]
109pub struct Tile {
110    id: TileId,
111    data: Arc<Vec<u8>>,
112}
113
114impl Tile {
115    /// Return the [`TileId`] of this [`Tile`]
116    pub fn id(&self) -> &TileId {
117        &self.id
118    }
119
120    /// Recomputes the [`NodeKeys`](NodeKey) contained within this tile
121    pub fn recompute_node_keys(&self) -> Vec<(NodeKey, HashOutput)> {
122        // Get the initial Node keys
123        let steps = 2u64.pow(8 * self.id.level as u32);
124        let tile_width = 256 * steps;
125        let tile_start = self.id.index * tile_width;
126
127        let mut nodes: Vec<(NodeKey, HashOutput)> = vec![];
128
129        // Add the base nodes to the output
130        for idx in 0..self.data.len() / 32 {
131            let node = (
132                NodeKey {
133                    start: tile_start + (idx as u64) * steps,
134                    end: tile_start + ((idx as u64) + 1) * steps,
135                },
136                self.data[32 * idx..32 * (idx + 1)].try_into().unwrap(),
137            );
138
139            nodes.push(node);
140        }
141
142        let mut start_idx = 0;
143        while start_idx < nodes.len() - 1 {
144            let end_node = if nodes.len() % 2 == 1 {
145                Some(nodes.pop().unwrap())
146            } else {
147                None
148            };
149
150            for idx in (start_idx..nodes.len()).step_by(2) {
151                let left = &nodes[idx];
152                let right = &nodes[idx + 1];
153
154                nodes.push((
155                    left.0.merge(&right.0).unwrap(),
156                    Node {
157                        left: left.1,
158                        right: right.1,
159                    }
160                    .hash(),
161                ));
162
163                start_idx += 2;
164            }
165
166            if let Some(node) = end_node {
167                nodes.push(node)
168            }
169        }
170
171        nodes
172    }
173}
174
175#[cfg(test)]
176mod tests {
177    use super::*;
178    use rand::{RngExt, rng};
179
180    #[test]
181    fn as_url() {
182        assert_eq!(&tile_id(0, 1, None, 0).as_url(), "tile/0/001");
183        assert_eq!(
184            &tile_id(1, 10987654321, None, 0).as_url(),
185            "tile/1/x010/x987/x654/321"
186        );
187        assert_eq!(
188            &tile_id(3, 1234, Some(128), 0).as_url(),
189            "tile/3/x001/234.p/128"
190        );
191    }
192
193    #[test]
194    fn into_tile_id() {
195        assert_eq!(
196            tile_id_from_node_key(4, 5, 70000),
197            tile_id(0, 0, None, 70000),
198        );
199        assert_eq!(
200            tile_id_from_node_key(270, 271, 70000),
201            tile_id(0, 1, None, 70000),
202        );
203
204        assert_eq!(
205            tile_id_from_node_key(0, 128, 70000),
206            tile_id(0, 0, None, 70000),
207        );
208        assert_eq!(
209            tile_id_from_node_key(0, 256, 70000),
210            tile_id(1, 0, None, 70000),
211        );
212
213        assert_eq!(
214            tile_id_from_node_key(69950, 69951, 70000),
215            tile_id(0, 273, Some(112), 70000)
216        );
217
218        assert_eq!(
219            tile_id_from_node_key(1 << 16, (1 << 16) + 512, 70000),
220            tile_id(1, 1, Some(17), 70000),
221        );
222
223        assert_eq!(
224            tile_id_from_node_key(0, 1 << 16, 70000),
225            tile_id(2, 0, Some(1), 70000),
226        );
227    }
228
229    #[test]
230    fn recompute_node_keys_small_examples() {
231        let tile = tile_id(0, 0, Some(1), 0)
232            .with_data(random_tile_data(1))
233            .unwrap();
234        let node_keys = tile.recompute_node_keys();
235        assert_node_keys(&node_keys, &[nk(0, 1)]);
236
237        let tile = tile_id(0, 0, Some(3), 0)
238            .with_data(random_tile_data(3))
239            .unwrap();
240        let node_keys = tile.recompute_node_keys();
241        assert_node_keys(
242            &node_keys,
243            &[nk(0, 1), nk(1, 2), nk(0, 2), nk(2, 3), nk(0, 3)],
244        );
245    }
246
247    // TODO: recompute_node_keys_sizes
248
249    fn tile_id_from_node_key(start: u64, end: u64, size: u64) -> TileId {
250        TileId::from_node_key(&NodeKey { start, end }, size).unwrap()
251    }
252
253    fn tile_id(level: u8, index: u64, partial: Option<u8>, tree_size: u64) -> TileId {
254        TileId {
255            level,
256            index,
257            partial: partial.map(|partial| NonZeroU8::new(partial).unwrap()),
258            tree_size,
259        }
260    }
261
262    fn nk(start: u64, end: u64) -> NodeKey {
263        NodeKey { start, end }
264    }
265
266    fn random_tile_data(size: u8) -> Arc<Vec<u8>> {
267        Arc::new(rng().random_iter().take(size as usize * 32).collect())
268    }
269
270    fn assert_node_keys(node_keys: &[(NodeKey, HashOutput)], test_keys: &[NodeKey]) {
271        assert_eq!(node_keys.len(), test_keys.len());
272
273        node_keys
274            .iter()
275            .map(|key| &key.0)
276            .zip(test_keys)
277            .for_each(|(key, test_key)| assert_eq!(key, test_key));
278    }
279}
luct_core/tiling/tile.rs

luct_core/tiling/
tile.rs
