1use std::cmp::Ordering;
22
23use cuprate_constants::block::MAX_BLOCK_HEIGHT_USIZE;
24
25use thiserror::Error;
26
27pub const CRYPTONOTE_PRUNING_LOG_STRIPES: u32 = 3;
29pub const CRYPTONOTE_PRUNING_STRIPE_SIZE: usize = 4096;
31pub const CRYPTONOTE_PRUNING_TIP_BLOCKS: usize = 5500;
33
34const PRUNING_SEED_LOG_STRIPES_SHIFT: u32 = 7;
35const PRUNING_SEED_STRIPE_SHIFT: u32 = 0;
36const PRUNING_SEED_LOG_STRIPES_MASK: u32 = 0x7;
37const PRUNING_SEED_STRIPE_MASK: u32 = 127;
38
39#[derive(Debug, Error)]
40pub enum PruningError {
41 #[error("log_stripes is out of range")]
42 LogStripesOutOfRange,
43 #[error("Stripe is out of range")]
44 StripeOutOfRange,
45 #[error("The block height is greater than `MAX_BLOCK_HEIGHT_USIZE`")]
46 BlockHeightTooLarge,
47 #[error("The blockchain height is greater than `MAX_BLOCK_HEIGHT_USIZE`")]
48 BlockChainHeightTooLarge,
49 #[error("The calculated height is smaller than the block height entered")]
50 CalculatedHeightSmallerThanEnteredBlock,
51 #[error("The entered seed has incorrect log stripes")]
52 SeedDoesNotHaveCorrectLogStripes,
53}
54
55#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
59#[cfg_attr(
60 feature = "borsh",
61 derive(borsh::BorshSerialize, borsh::BorshDeserialize)
62)]
63pub enum PruningSeed {
64 NotPruned,
66 Pruned(DecompressedPruningSeed),
68}
69
70impl PruningSeed {
71 pub fn new_pruned(stripe: u32, log_stripes: u32) -> Result<Self, PruningError> {
75 Ok(Self::Pruned(DecompressedPruningSeed::new(
76 stripe,
77 log_stripes,
78 )?))
79 }
80
81 pub fn decompress(seed: u32) -> Result<Self, PruningError> {
85 Ok(DecompressedPruningSeed::decompress(seed)?.map_or(Self::NotPruned, Self::Pruned))
86 }
87
88 pub fn decompress_p2p_rules(seed: u32) -> Result<Self, PruningError> {
93 let seed = Self::decompress(seed)?;
94
95 if let Some(log_stripes) = seed.get_log_stripes() {
96 if log_stripes != CRYPTONOTE_PRUNING_LOG_STRIPES {
97 return Err(PruningError::LogStripesOutOfRange);
98 }
99 }
100
101 Ok(seed)
102 }
103
104 pub const fn compress(&self) -> u32 {
106 match self {
107 Self::NotPruned => 0,
108 Self::Pruned(seed) => seed.compress(),
109 }
110 }
111
112 pub const fn get_log_stripes(&self) -> Option<u32> {
114 match self {
115 Self::NotPruned => None,
116 Self::Pruned(seed) => Some(seed.log_stripes),
117 }
118 }
119
120 pub const fn get_stripe(&self) -> Option<u32> {
122 match self {
123 Self::NotPruned => None,
124 Self::Pruned(seed) => Some(seed.stripe),
125 }
126 }
127
128 pub const fn has_full_block(&self, height: usize, blockchain_height: usize) -> bool {
130 match self {
131 Self::NotPruned => true,
132 Self::Pruned(seed) => seed.has_full_block(height, blockchain_height),
133 }
134 }
135
136 pub fn get_next_pruned_block(
152 &self,
153 block_height: usize,
154 blockchain_height: usize,
155 ) -> Result<Option<usize>, PruningError> {
156 Ok(match self {
157 Self::NotPruned => None,
158 Self::Pruned(seed) => seed.get_next_pruned_block(block_height, blockchain_height)?,
159 })
160 }
161
162 pub fn get_next_unpruned_block(
176 &self,
177 block_height: usize,
178 blockchain_height: usize,
179 ) -> Result<usize, PruningError> {
180 Ok(match self {
181 Self::NotPruned => block_height,
182 Self::Pruned(seed) => seed.get_next_unpruned_block(block_height, blockchain_height)?,
183 })
184 }
185}
186
187impl PartialOrd<Self> for PruningSeed {
188 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
189 Some(self.cmp(other))
190 }
191}
192
193impl Ord for PruningSeed {
194 fn cmp(&self, other: &Self) -> Ordering {
195 match (self, other) {
196 (Self::NotPruned, Self::NotPruned) => Ordering::Equal,
198 (Self::NotPruned, Self::Pruned(_)) => Ordering::Greater,
199 (Self::Pruned(_), Self::NotPruned) => Ordering::Less,
200
201 (Self::Pruned(seed1), Self::Pruned(seed2)) => seed1.cmp(seed2),
202 }
203 }
204}
205
206#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
211#[cfg_attr(
212 feature = "borsh",
213 derive(borsh::BorshSerialize, borsh::BorshDeserialize)
214)]
215pub struct DecompressedPruningSeed {
216 log_stripes: u32,
218 stripe: u32,
222}
223
224impl PartialOrd<Self> for DecompressedPruningSeed {
225 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
226 Some(self.cmp(other))
227 }
228}
229
230impl Ord for DecompressedPruningSeed {
231 fn cmp(&self, other: &Self) -> Ordering {
232 #[expect(clippy::wildcard_enum_match_arm)]
235 match self.log_stripes.cmp(&other.log_stripes) {
236 Ordering::Equal => self.stripe.cmp(&other.stripe),
237 ord => ord,
238 }
239 }
240}
241
242impl DecompressedPruningSeed {
243 pub const fn new(stripe: u32, log_stripes: u32) -> Result<Self, PruningError> {
268 if log_stripes > PRUNING_SEED_LOG_STRIPES_MASK {
269 Err(PruningError::LogStripesOutOfRange)
270 } else if !(stripe > 0 && stripe <= (1 << log_stripes)) {
271 Err(PruningError::StripeOutOfRange)
272 } else {
273 Ok(Self {
274 log_stripes,
275 stripe,
276 })
277 }
278 }
279
280 pub const fn decompress(seed: u32) -> Result<Option<Self>, PruningError> {
286 if seed == 0 {
287 return Ok(None);
289 }
290
291 let log_stripes = (seed >> PRUNING_SEED_LOG_STRIPES_SHIFT) & PRUNING_SEED_LOG_STRIPES_MASK;
292 let stripe = 1 + ((seed >> PRUNING_SEED_STRIPE_SHIFT) & PRUNING_SEED_STRIPE_MASK);
293
294 if stripe > (1 << log_stripes) {
295 return Err(PruningError::StripeOutOfRange);
296 }
297
298 Ok(Some(Self {
299 log_stripes,
300 stripe,
301 }))
302 }
303
304 pub const fn compress(&self) -> u32 {
306 (self.log_stripes << PRUNING_SEED_LOG_STRIPES_SHIFT)
307 | ((self.stripe - 1) << PRUNING_SEED_STRIPE_SHIFT)
308 }
309
310 pub const fn has_full_block(&self, height: usize, blockchain_height: usize) -> bool {
312 match get_block_pruning_stripe(height, blockchain_height, self.log_stripes) {
313 Some(block_stripe) => self.stripe == block_stripe,
314 None => true,
315 }
316 }
317
318 pub const fn get_next_unpruned_block(
332 &self,
333 block_height: usize,
334 blockchain_height: usize,
335 ) -> Result<usize, PruningError> {
336 if block_height > MAX_BLOCK_HEIGHT_USIZE || block_height > blockchain_height {
337 return Err(PruningError::BlockHeightTooLarge);
338 }
339
340 if blockchain_height > MAX_BLOCK_HEIGHT_USIZE {
341 return Err(PruningError::BlockChainHeightTooLarge);
342 }
343
344 if block_height + CRYPTONOTE_PRUNING_TIP_BLOCKS >= blockchain_height {
345 return Ok(block_height);
348 }
349
350 let block_pruning_stripe = get_block_pruning_stripe(block_height, blockchain_height, self.log_stripes)
351 .expect("We just checked if `block_height + CRYPTONOTE_PRUNING_TIP_BLOCKS >= blockchain_height`");
352 if self.stripe == block_pruning_stripe {
353 return Ok(block_height);
356 }
357
358 let cycles = (block_height / CRYPTONOTE_PRUNING_STRIPE_SIZE) >> self.log_stripes;
361 let cycles_start = cycles
364 + if self.stripe > block_pruning_stripe {
365 0
366 } else {
367 1
368 };
369
370 let calculated_height = cycles_start * (CRYPTONOTE_PRUNING_STRIPE_SIZE << self.log_stripes)
372 + (self.stripe as usize - 1) * CRYPTONOTE_PRUNING_STRIPE_SIZE;
373
374 if calculated_height + CRYPTONOTE_PRUNING_TIP_BLOCKS > blockchain_height {
375 Ok(blockchain_height.saturating_sub(CRYPTONOTE_PRUNING_TIP_BLOCKS))
377 } else if calculated_height < block_height {
378 Err(PruningError::CalculatedHeightSmallerThanEnteredBlock)
379 } else {
380 Ok(calculated_height)
381 }
382 }
383
384 pub fn get_next_pruned_block(
398 &self,
399 block_height: usize,
400 blockchain_height: usize,
401 ) -> Result<Option<usize>, PruningError> {
402 if block_height + CRYPTONOTE_PRUNING_TIP_BLOCKS >= blockchain_height {
403 return Ok(None);
406 }
407
408 let block_pruning_stripe = get_block_pruning_stripe(block_height, blockchain_height, self.log_stripes)
409 .expect("We just checked if `block_height + CRYPTONOTE_PRUNING_TIP_BLOCKS >= blockchain_height`");
410 if self.stripe != block_pruning_stripe {
411 return Ok(Some(block_height));
413 }
414
415 let next_stripe = 1 + (self.stripe & ((1 << self.log_stripes) - 1));
418 let seed = Self::new(next_stripe, self.log_stripes)
419 .expect("We just made sure this stripe is in range for this log_stripe");
420
421 let calculated_height = seed.get_next_unpruned_block(block_height, blockchain_height)?;
422
423 if calculated_height + CRYPTONOTE_PRUNING_TIP_BLOCKS > blockchain_height {
424 Ok(None)
426 } else {
427 Ok(Some(calculated_height))
428 }
429 }
430}
431
432const fn get_block_pruning_stripe(
433 block_height: usize,
434 blockchain_height: usize,
435 log_stripe: u32,
436) -> Option<u32> {
437 if block_height + CRYPTONOTE_PRUNING_TIP_BLOCKS >= blockchain_height {
438 None
439 } else {
440 #[expect(
441 clippy::cast_possible_truncation,
442 clippy::cast_sign_loss,
443 reason = "it's trivial to prove it's ok to us `as` here"
444 )]
445 Some(
446 (((block_height / CRYPTONOTE_PRUNING_STRIPE_SIZE) & ((1 << log_stripe) as usize - 1))
447 + 1) as u32,
448 )
449 }
450}
451
452#[cfg(test)]
453mod tests {
454 use super::*;
455
456 fn make_all_pruning_seeds() -> Vec<PruningSeed> {
457 let possible_stripes = 1..=(1 << CRYPTONOTE_PRUNING_LOG_STRIPES);
458 possible_stripes
459 .map(|stripe| PruningSeed::new_pruned(stripe, CRYPTONOTE_PRUNING_LOG_STRIPES).unwrap())
460 .collect()
461 }
462
463 #[test]
464 fn from_u32_for_pruning_seed() {
465 let good_seeds = 384..=391;
466 for seed in good_seeds {
467 assert!(PruningSeed::decompress(seed).is_ok());
468 }
469 let bad_seeds = [383, 392];
470 for seed in bad_seeds {
471 assert!(PruningSeed::decompress(seed).is_err());
472 }
473 }
474
475 #[test]
476 fn make_invalid_pruning_seeds() {
477 let invalid_stripes = [0, (1 << CRYPTONOTE_PRUNING_LOG_STRIPES) + 1];
478
479 for stripe in invalid_stripes {
480 assert!(PruningSeed::new_pruned(stripe, CRYPTONOTE_PRUNING_LOG_STRIPES).is_err());
481 }
482 }
483
484 #[test]
485 fn get_pruning_log_stripe() {
486 let all_valid_seeds = make_all_pruning_seeds();
487 for seed in &all_valid_seeds {
488 assert_eq!(seed.get_log_stripes().unwrap(), 3);
489 }
490 }
491
492 #[test]
493 fn get_pruning_stripe() {
494 let all_valid_seeds = make_all_pruning_seeds();
495 #[expect(clippy::cast_possible_truncation)]
496 for (i, seed) in all_valid_seeds.iter().enumerate() {
497 assert_eq!(seed.get_stripe().unwrap(), i as u32 + 1);
498 }
499 }
500
501 #[test]
502 fn blocks_pruning_stripe() {
503 let blockchain_height = 76437863;
504
505 for i in 0_u32..8 {
506 assert_eq!(
507 get_block_pruning_stripe(
508 (i * 4096) as usize,
509 blockchain_height,
510 CRYPTONOTE_PRUNING_LOG_STRIPES
511 )
512 .unwrap(),
513 i + 1
514 );
515 }
516
517 for i in 0_u32..8 {
518 assert_eq!(
519 get_block_pruning_stripe(
520 32768 + (i * 4096) as usize,
521 blockchain_height,
522 CRYPTONOTE_PRUNING_LOG_STRIPES
523 )
524 .unwrap(),
525 i + 1
526 );
527 }
528
529 for i in 1_u32..8 {
530 assert_eq!(
531 get_block_pruning_stripe(
532 32767 + (i * 4096) as usize,
533 blockchain_height,
534 CRYPTONOTE_PRUNING_LOG_STRIPES
535 )
536 .unwrap(),
537 i
538 );
539 }
540
541 assert!(get_block_pruning_stripe(
543 blockchain_height - 5500,
544 blockchain_height,
545 CRYPTONOTE_PRUNING_LOG_STRIPES
546 )
547 .is_none());
548 }
549
550 #[test]
551 fn next_unpruned_block() {
552 let all_valid_seeds = make_all_pruning_seeds();
553 let blockchain_height = 76437863;
554
555 for (i, seed) in all_valid_seeds.iter().enumerate() {
556 assert_eq!(
557 seed.get_next_unpruned_block(0, blockchain_height).unwrap(),
558 i * 4096
559 );
560 }
561
562 for (i, seed) in all_valid_seeds.iter().enumerate() {
563 assert_eq!(
564 seed.get_next_unpruned_block((i + 1) * 4096, blockchain_height)
565 .unwrap(),
566 i * 4096 + 32768
567 );
568 }
569
570 for (i, seed) in all_valid_seeds.iter().enumerate() {
571 assert_eq!(
572 seed.get_next_unpruned_block((i + 8) * 4096, blockchain_height)
573 .unwrap(),
574 i * 4096 + 32768
575 );
576 }
577
578 for seed in &all_valid_seeds {
579 assert_eq!(
580 seed.get_next_unpruned_block(76437863 - 1, blockchain_height)
581 .unwrap(),
582 76437863 - 1
583 );
584 }
585
586 let zero_seed = PruningSeed::NotPruned;
587
588 assert_eq!(
589 zero_seed.get_next_unpruned_block(33443, 5565445).unwrap(),
590 33443
591 );
592
593 let seed = PruningSeed::decompress(384).unwrap();
594
595 assert_eq!(seed.get_next_unpruned_block(5000, 11000).unwrap(), 5500);
597 }
598
599 #[test]
600 fn next_pruned_block() {
601 let all_valid_seeds = make_all_pruning_seeds();
602 let blockchain_height = 76437863;
603
604 for seed in all_valid_seeds.iter().skip(1) {
605 assert_eq!(
606 seed.get_next_pruned_block(0, blockchain_height)
607 .unwrap()
608 .unwrap(),
609 0
610 );
611 }
612
613 for (i, seed) in all_valid_seeds.iter().enumerate() {
614 assert_eq!(
615 seed.get_next_pruned_block((i + 1) * 4096, blockchain_height)
616 .unwrap()
617 .unwrap(),
618 (i + 1) * 4096
619 );
620 }
621
622 for (i, seed) in all_valid_seeds.iter().enumerate() {
623 assert_eq!(
624 seed.get_next_pruned_block((i + 8) * 4096, blockchain_height)
625 .unwrap()
626 .unwrap(),
627 (i + 9) * 4096
628 );
629 }
630
631 for seed in &all_valid_seeds {
632 assert_eq!(
633 seed.get_next_pruned_block(76437863 - 1, blockchain_height)
634 .unwrap(),
635 None
636 );
637 }
638
639 let zero_seed = PruningSeed::NotPruned;
640
641 assert_eq!(
642 zero_seed.get_next_pruned_block(33443, 5565445).unwrap(),
643 None
644 );
645
646 let seed = PruningSeed::decompress(384).unwrap();
647
648 assert_eq!(seed.get_next_pruned_block(5000, 10000).unwrap(), None);
650 }
651}