tetsy_scale_codec/
compact.rs

1// Copyright 2019 Parity Technologies
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! [Compact encoding](https://core.tetcoin.org/docs/en/overview/low-level-data-format#compact-general-integers)
16
17use arrayvec::ArrayVec;
18
19use crate::alloc::vec::Vec;
20use crate::codec::{Encode, Decode, Input, Output, EncodeAsRef};
21use crate::encode_like::EncodeLike;
22use crate::Error;
23#[cfg(feature = "fuzz")]
24use arbitrary::Arbitrary;
25
26struct ArrayVecWrapper<T: arrayvec::Array>(ArrayVec<T>);
27
28impl<T: arrayvec::Array<Item=u8>> Output for ArrayVecWrapper<T> {
29	fn write(&mut self, bytes: &[u8]) {
30		let old_len = self.0.len();
31		let new_len = old_len + bytes.len();
32
33		assert!(new_len <= self.0.capacity());
34		unsafe {
35			self.0.set_len(new_len);
36		}
37
38		self.0[old_len..new_len].copy_from_slice(bytes);
39	}
40
41	fn push_byte(&mut self, byte: u8) {
42		self.0.push(byte);
43	}
44}
45
46/// Prefix another input with a byte.
47struct PrefixInput<'a, T> {
48	prefix: Option<u8>,
49	input: &'a mut T,
50}
51
52impl<'a, T: 'a + Input> Input for PrefixInput<'a, T> {
53	fn remaining_len(&mut self) -> Result<Option<usize>, Error> {
54		let len = if let Some(len) = self.input.remaining_len()? {
55			Some(len.saturating_add(self.prefix.iter().count()))
56		} else {
57			None
58		};
59		Ok(len)
60	}
61
62	fn read(&mut self, buffer: &mut [u8]) -> Result<(), Error> {
63		match self.prefix.take() {
64			Some(v) if !buffer.is_empty() => {
65				buffer[0] = v;
66				self.input.read(&mut buffer[1..])
67			}
68			_ => self.input.read(buffer)
69		}
70	}
71}
72
73/// Something that can return the compact encoded length for a given value.
74pub trait CompactLen<T> {
75	/// Returns the compact encoded length for the given value.
76	fn compact_len(val: &T) -> usize;
77}
78
79/// Compact-encoded variant of T. This is more space-efficient but less compute-efficient.
80#[derive(Eq, PartialEq, Clone, Copy, Ord, PartialOrd)]
81#[cfg_attr(feature = "fuzz", derive(Arbitrary))]
82pub struct Compact<T>(pub T);
83
84impl<T> From<T> for Compact<T> {
85	fn from(x: T) -> Compact<T> { Compact(x) }
86}
87
88impl<'a, T: Copy> From<&'a T> for Compact<T> {
89	fn from(x: &'a T) -> Compact<T> { Compact(*x) }
90}
91
92/// Allow foreign structs to be wrap in Compact
93pub trait CompactAs: From<Compact<Self>> {
94	/// A compact-encodable type that should be used as the encoding.
95	type As;
96
97	/// Returns the compact-encodable type.
98	fn encode_as(&self) -> &Self::As;
99
100	/// Decode `Self` from the compact-decoded type.
101	fn decode_from(_: Self::As) -> Result<Self, Error>;
102}
103
104impl<T> EncodeLike for Compact<T>
105where
106	for<'a> CompactRef<'a, T>: Encode,
107{}
108
109impl<T> Encode for Compact<T>
110where
111	for<'a> CompactRef<'a, T>: Encode,
112{
113	fn size_hint(&self) -> usize {
114		CompactRef(&self.0).size_hint()
115	}
116
117	fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
118		CompactRef(&self.0).encode_to(dest)
119	}
120
121	fn encode(&self) -> Vec<u8> {
122		CompactRef(&self.0).encode()
123	}
124
125	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
126		CompactRef(&self.0).using_encoded(f)
127	}
128}
129
130impl<'a, T> EncodeLike for CompactRef<'a, T>
131where
132	T: CompactAs,
133	for<'b> CompactRef<'b, T::As>: Encode,
134{}
135
136impl<'a, T> Encode for CompactRef<'a, T>
137where
138	T: CompactAs,
139	for<'b> CompactRef<'b, T::As>: Encode,
140{
141	fn size_hint(&self) -> usize {
142		CompactRef(self.0.encode_as()).size_hint()
143	}
144
145	fn encode_to<Out: Output + ?Sized>(&self, dest: &mut Out) {
146		CompactRef(self.0.encode_as()).encode_to(dest)
147	}
148
149	fn encode(&self) -> Vec<u8> {
150		CompactRef(self.0.encode_as()).encode()
151	}
152
153	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
154		CompactRef(self.0.encode_as()).using_encoded(f)
155	}
156}
157
158impl<T> Decode for Compact<T>
159where
160	T: CompactAs,
161	Compact<T::As>: Decode,
162{
163	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
164		let as_ = Compact::<T::As>::decode(input)?;
165		Ok(Compact(<T as CompactAs>::decode_from(as_.0)?))
166	}
167}
168
169macro_rules! impl_from_compact {
170	( $( $ty:ty ),* ) => {
171		$(
172			impl From<Compact<$ty>> for $ty {
173				fn from(x: Compact<$ty>) -> $ty { x.0 }
174			}
175		)*
176	}
177}
178
179impl_from_compact! { (), u8, u16, u32, u64, u128 }
180
181/// Compact-encoded variant of &'a T. This is more space-efficient but less compute-efficient.
182#[derive(Eq, PartialEq, Clone, Copy)]
183pub struct CompactRef<'a, T>(pub &'a T);
184
185impl<'a, T> From<&'a T> for CompactRef<'a, T> {
186	fn from(x: &'a T) -> Self { CompactRef(x) }
187}
188
189impl<T> core::fmt::Debug for Compact<T> where T: core::fmt::Debug {
190	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
191		self.0.fmt(f)
192	}
193}
194
195#[cfg(feature = "std")]
196impl<T> serde::Serialize for Compact<T> where T: serde::Serialize {
197	fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: serde::Serializer {
198		T::serialize(&self.0, serializer)
199	}
200}
201
202#[cfg(feature = "std")]
203impl<'de, T> serde::Deserialize<'de> for Compact<T> where T: serde::Deserialize<'de> {
204	fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: serde::Deserializer<'de> {
205		T::deserialize(deserializer).map(Compact)
206	}
207}
208
209/// Trait that tells you if a given type can be encoded/decoded in a compact way.
210pub trait HasCompact: Sized {
211	/// The compact type; this can be
212	type Type: for<'a> EncodeAsRef<'a, Self> + Decode + From<Self> + Into<Self>;
213}
214
215impl<'a, T: 'a> EncodeAsRef<'a, T> for Compact<T> where CompactRef<'a, T>: Encode + From<&'a T> {
216	type RefType = CompactRef<'a, T>;
217}
218
219impl<T: 'static> HasCompact for T where
220	Compact<T>: for<'a> EncodeAsRef<'a, T> + Decode + From<Self> + Into<Self>
221{
222	type Type = Compact<T>;
223}
224
225impl<'a> Encode for CompactRef<'a, ()> {
226	fn encode_to<W: Output + ?Sized>(&self, _dest: &mut W) {
227	}
228
229	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
230		f(&[])
231	}
232
233	fn encode(&self) -> Vec<u8> {
234		Vec::new()
235	}
236}
237
238impl<'a> Encode for CompactRef<'a, u8> {
239	fn size_hint(&self) -> usize {
240		Compact::compact_len(self.0)
241	}
242
243	fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
244		match self.0 {
245			0..=0b0011_1111 => dest.push_byte(self.0 << 2),
246			_ => ((u16::from(*self.0) << 2) | 0b01).encode_to(dest),
247		}
248	}
249
250	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
251		let mut r = ArrayVecWrapper(ArrayVec::<[u8; 2]>::new());
252		self.encode_to(&mut r);
253		f(&r.0)
254	}
255}
256
257impl CompactLen<u8> for Compact<u8> {
258	fn compact_len(val: &u8) -> usize {
259		match val {
260			0..=0b0011_1111 => 1,
261			_ => 2,
262		}
263	}
264}
265
266impl<'a> Encode for CompactRef<'a, u16> {
267	fn size_hint(&self) -> usize {
268		Compact::compact_len(self.0)
269	}
270
271	fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
272		match self.0 {
273			0..=0b0011_1111 => dest.push_byte((*self.0 as u8) << 2),
274			0..=0b0011_1111_1111_1111 => ((*self.0 << 2) | 0b01).encode_to(dest),
275			_ => ((u32::from(*self.0) << 2) | 0b10).encode_to(dest),
276		}
277	}
278
279	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
280		let mut r = ArrayVecWrapper(ArrayVec::<[u8; 4]>::new());
281		self.encode_to(&mut r);
282		f(&r.0)
283	}
284}
285
286impl CompactLen<u16> for Compact<u16> {
287	fn compact_len(val: &u16) -> usize {
288		match val {
289			0..=0b0011_1111 => 1,
290			0..=0b0011_1111_1111_1111 => 2,
291			_ => 4,
292		}
293	}
294}
295
296impl<'a> Encode for CompactRef<'a, u32> {
297	fn size_hint(&self) -> usize {
298		Compact::compact_len(self.0)
299	}
300
301	fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
302		match self.0 {
303			0..=0b0011_1111 => dest.push_byte((*self.0 as u8) << 2),
304			0..=0b0011_1111_1111_1111 => (((*self.0 as u16) << 2) | 0b01).encode_to(dest),
305			0..=0b0011_1111_1111_1111_1111_1111_1111_1111 => ((*self.0 << 2) | 0b10).encode_to(dest),
306			_ => {
307				dest.push_byte(0b11);
308				self.0.encode_to(dest);
309			}
310		}
311	}
312
313	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
314		let mut r = ArrayVecWrapper(ArrayVec::<[u8; 5]>::new());
315		self.encode_to(&mut r);
316		f(&r.0)
317	}
318}
319
320impl CompactLen<u32> for Compact<u32> {
321	fn compact_len(val: &u32) -> usize {
322		match val {
323			0..=0b0011_1111 => 1,
324			0..=0b0011_1111_1111_1111 => 2,
325			0..=0b0011_1111_1111_1111_1111_1111_1111_1111 => 4,
326			_ => 5,
327		}
328	}
329}
330
331impl<'a> Encode for CompactRef<'a, u64> {
332	fn size_hint(&self) -> usize {
333		Compact::compact_len(self.0)
334	}
335
336	fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
337		match self.0 {
338			0..=0b0011_1111 => dest.push_byte((*self.0 as u8) << 2),
339			0..=0b0011_1111_1111_1111 => (((*self.0 as u16) << 2) | 0b01).encode_to(dest),
340			0..=0b0011_1111_1111_1111_1111_1111_1111_1111 => (((*self.0 as u32) << 2) | 0b10).encode_to(dest),
341			_ => {
342				let bytes_needed = 8 - self.0.leading_zeros() / 8;
343				assert!(bytes_needed >= 4, "Previous match arm matches anyting less than 2^30; qed");
344				dest.push_byte(0b11 + ((bytes_needed - 4) << 2) as u8);
345				let mut v = *self.0;
346				for _ in 0..bytes_needed {
347					dest.push_byte(v as u8);
348					v >>= 8;
349				}
350				assert_eq!(v, 0, "shifted sufficient bits right to lead only leading zeros; qed")
351			}
352		}
353	}
354
355	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
356		let mut r = ArrayVecWrapper(ArrayVec::<[u8; 9]>::new());
357		self.encode_to(&mut r);
358		f(&r.0)
359	}
360}
361
362impl CompactLen<u64> for Compact<u64> {
363	fn compact_len(val: &u64) -> usize {
364		match val {
365			0..=0b0011_1111 => 1,
366			0..=0b0011_1111_1111_1111 => 2,
367			0..=0b0011_1111_1111_1111_1111_1111_1111_1111 => 4,
368			_ => {
369				(8 - val.leading_zeros() / 8) as usize + 1
370			},
371		}
372	}
373}
374
375impl<'a> Encode for CompactRef<'a, u128> {
376	fn size_hint(&self) -> usize {
377		Compact::compact_len(self.0)
378	}
379
380	fn encode_to<W: Output + ?Sized>(&self, dest: &mut W) {
381		match self.0 {
382			0..=0b0011_1111 => dest.push_byte((*self.0 as u8) << 2),
383			0..=0b0011_1111_1111_1111 => (((*self.0 as u16) << 2) | 0b01).encode_to(dest),
384			0..=0b0011_1111_1111_1111_1111_1111_1111_1111 => (((*self.0 as u32) << 2) | 0b10).encode_to(dest),
385			_ => {
386				let bytes_needed = 16 - self.0.leading_zeros() / 8;
387				assert!(bytes_needed >= 4, "Previous match arm matches anyting less than 2^30; qed");
388				dest.push_byte(0b11 + ((bytes_needed - 4) << 2) as u8);
389				let mut v = *self.0;
390				for _ in 0..bytes_needed {
391					dest.push_byte(v as u8);
392					v >>= 8;
393				}
394				assert_eq!(v, 0, "shifted sufficient bits right to lead only leading zeros; qed")
395			}
396		}
397	}
398
399	fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
400		let mut r = ArrayVecWrapper(ArrayVec::<[u8; 17]>::new());
401		self.encode_to(&mut r);
402		f(&r.0)
403	}
404}
405
406impl CompactLen<u128> for Compact<u128> {
407	fn compact_len(val: &u128) -> usize {
408		match val {
409			0..=0b0011_1111 => 1,
410			0..=0b0011_1111_1111_1111 => 2,
411			0..=0b0011_1111_1111_1111_1111_1111_1111_1111 => 4,
412			_ => {
413				(16 - val.leading_zeros() / 8) as usize + 1
414			},
415		}
416	}
417}
418
419impl Decode for Compact<()> {
420	fn decode<I: Input>(_input: &mut I) -> Result<Self, Error> {
421		Ok(Compact(()))
422	}
423}
424
425const U8_OUT_OF_RANGE: &str = "out of range decoding Compact<u8>";
426const U16_OUT_OF_RANGE: &str = "out of range decoding Compact<u16>";
427const U32_OUT_OF_RANGE: &str = "out of range decoding Compact<u32>";
428const U64_OUT_OF_RANGE: &str = "out of range decoding Compact<u64>";
429const U128_OUT_OF_RANGE: &str = "out of range decoding Compact<u128>";
430
431impl Decode for Compact<u8> {
432	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
433		let prefix = input.read_byte()?;
434		Ok(Compact(match prefix % 4 {
435			0 => prefix >> 2,
436			1 => {
437				let x = u16::decode(&mut PrefixInput{prefix: Some(prefix), input})? >> 2;
438				if x > 0b0011_1111 && x <= 255 {
439					x as u8
440				} else {
441					return Err(U8_OUT_OF_RANGE.into());
442				}
443			},
444			_ => return Err("unexpected prefix decoding Compact<u8>".into()),
445		}))
446	}
447}
448
449impl Decode for Compact<u16> {
450	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
451		let prefix = input.read_byte()?;
452		Ok(Compact(match prefix % 4 {
453			0 => u16::from(prefix) >> 2,
454			1 => {
455				let x = u16::decode(&mut PrefixInput{prefix: Some(prefix), input})? >> 2;
456				if x > 0b0011_1111 && x <= 0b0011_1111_1111_1111 {
457					x
458				} else {
459					return Err(U16_OUT_OF_RANGE.into());
460				}
461			},
462			2 => {
463				let x = u32::decode(&mut PrefixInput{prefix: Some(prefix), input})? >> 2;
464				if x > 0b0011_1111_1111_1111 && x < 65536 {
465					x as u16
466				} else {
467					return Err(U16_OUT_OF_RANGE.into());
468				}
469			},
470			_ => return Err("unexpected prefix decoding Compact<u16>".into()),
471		}))
472	}
473}
474
475impl Decode for Compact<u32> {
476	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
477		let prefix = input.read_byte()?;
478		Ok(Compact(match prefix % 4 {
479			0 => u32::from(prefix) >> 2,
480			1 => {
481				let x = u16::decode(&mut PrefixInput{prefix: Some(prefix), input})? >> 2;
482				if x > 0b0011_1111 && x <= 0b0011_1111_1111_1111 {
483					u32::from(x)
484				} else {
485					return Err(U32_OUT_OF_RANGE.into());
486				}
487			},
488			2 => {
489				let x = u32::decode(&mut PrefixInput{prefix: Some(prefix), input})? >> 2;
490				if x > 0b0011_1111_1111_1111 && x <= u32::max_value() >> 2 {
491					x
492				} else {
493					return Err(U32_OUT_OF_RANGE.into());
494				}
495			},
496			3|_ => {	// |_. yeah, i know.
497				if prefix >> 2 == 0 {
498					// just 4 bytes. ok.
499					let x = u32::decode(input)?;
500					if x > u32::max_value() >> 2 {
501						x
502					} else {
503						return Err(U32_OUT_OF_RANGE.into());
504					}
505				} else {
506					// Out of range for a 32-bit quantity.
507					return Err(U32_OUT_OF_RANGE.into());
508				}
509			}
510		}))
511	}
512}
513
514impl Decode for Compact<u64> {
515	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
516		let prefix = input.read_byte()?;
517		Ok(Compact(match prefix % 4 {
518			0 => u64::from(prefix) >> 2,
519			1 => {
520				let x = u16::decode(&mut PrefixInput{prefix: Some(prefix), input})? >> 2;
521				if x > 0b0011_1111 && x <= 0b0011_1111_1111_1111 {
522					u64::from(x)
523				} else {
524					return Err(U64_OUT_OF_RANGE.into());
525				}
526			},
527			2 => {
528				let x = u32::decode(&mut PrefixInput{prefix: Some(prefix), input})? >> 2;
529				if x > 0b0011_1111_1111_1111 && x <= u32::max_value() >> 2 {
530					u64::from(x)
531				} else {
532					return Err(U64_OUT_OF_RANGE.into());
533				}
534			},
535			3|_ => match (prefix >> 2) + 4 {
536				4 => {
537					let x = u32::decode(input)?;
538					if x > u32::max_value() >> 2 {
539						u64::from(x)
540					} else {
541						return Err(U64_OUT_OF_RANGE.into());
542					}
543				},
544				8 => {
545					let x = u64::decode(input)?;
546					if x > u64::max_value() >> 8 {
547						x
548					} else {
549						return Err(U64_OUT_OF_RANGE.into());
550					}
551				},
552				x if x > 8 => return Err("unexpected prefix decoding Compact<u64>".into()),
553				bytes_needed => {
554					let mut res = 0;
555					for i in 0..bytes_needed {
556						res |= u64::from(input.read_byte()?) << (i * 8);
557					}
558					if res > u64::max_value() >> ((8 - bytes_needed + 1) * 8) {
559						res
560					} else {
561						return Err(U64_OUT_OF_RANGE.into());
562					}
563				},
564			},
565		}))
566	}
567}
568
569impl Decode for Compact<u128> {
570	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
571		let prefix = input.read_byte()?;
572		Ok(Compact(match prefix % 4 {
573			0 => u128::from(prefix) >> 2,
574			1 => {
575				let x = u16::decode(&mut PrefixInput{prefix: Some(prefix), input})? >> 2;
576				if x > 0b0011_1111 && x <= 0b0011_1111_1111_1111 {
577					u128::from(x)
578				} else {
579					return Err(U128_OUT_OF_RANGE.into());
580				}
581			},
582			2 => {
583				let x = u32::decode(&mut PrefixInput{prefix: Some(prefix), input})? >> 2;
584				if x > 0b0011_1111_1111_1111 && x <= u32::max_value() >> 2 {
585					u128::from(x)
586				} else {
587					return Err(U128_OUT_OF_RANGE.into());
588				}
589			},
590			3|_ => match (prefix >> 2) + 4 {
591				4 => {
592					let x = u32::decode(input)?;
593					if x > u32::max_value() >> 2 {
594						u128::from(x)
595					} else {
596						return Err(U128_OUT_OF_RANGE.into());
597					}
598				},
599				8 => {
600					let x = u64::decode(input)?;
601					if x > u64::max_value() >> 8 {
602						u128::from(x)
603					} else {
604						return Err(U128_OUT_OF_RANGE.into());
605					}
606				},
607				16 => {
608					let x = u128::decode(input)?;
609					if x > u128::max_value() >> 8 {
610						x
611					} else {
612						return Err(U128_OUT_OF_RANGE.into());
613					}
614				},
615				x if x > 16 => return Err("unexpected prefix decoding Compact<u128>".into()),
616				bytes_needed => {
617					let mut res = 0;
618					for i in 0..bytes_needed {
619						res |= u128::from(input.read_byte()?) << (i * 8);
620					}
621					if res > u128::max_value() >> ((16 - bytes_needed + 1) * 8) {
622						res
623					} else {
624						return Err(U128_OUT_OF_RANGE.into());
625					}
626				},
627			},
628		}))
629	}
630}
631
632#[cfg(test)]
633mod tests {
634	use super::*;
635
636	#[test]
637	fn compact_128_encoding_works() {
638		let tests = [
639			(0u128, 1usize), (63, 1), (64, 2), (16383, 2),
640			(16384, 4), (1073741823, 4),
641			(1073741824, 5), ((1 << 32) - 1, 5),
642			(1 << 32, 6), (1 << 40, 7), (1 << 48, 8), ((1 << 56) - 1, 8), (1 << 56, 9), ((1 << 64) - 1, 9),
643			(1 << 64, 10), (1 << 72, 11), (1 << 80, 12), (1 << 88, 13), (1 << 96, 14), (1 << 104, 15),
644			(1 << 112, 16), ((1 << 120) - 1, 16), (1 << 120, 17), (u128::max_value(), 17)
645		];
646		for &(n, l) in &tests {
647			let encoded = Compact(n as u128).encode();
648			assert_eq!(encoded.len(), l);
649			assert_eq!(Compact::compact_len(&n), l);
650			assert_eq!(<Compact<u128>>::decode(&mut &encoded[..]).unwrap().0, n);
651		}
652	}
653
654	#[test]
655	fn compact_64_encoding_works() {
656		let tests = [
657			(0u64, 1usize), (63, 1), (64, 2), (16383, 2),
658			(16384, 4), (1073741823, 4),
659			(1073741824, 5), ((1 << 32) - 1, 5),
660			(1 << 32, 6), (1 << 40, 7), (1 << 48, 8), ((1 << 56) - 1, 8), (1 << 56, 9), (u64::max_value(), 9)
661		];
662		for &(n, l) in &tests {
663			let encoded = Compact(n as u64).encode();
664			assert_eq!(encoded.len(), l);
665			assert_eq!(Compact::compact_len(&n), l);
666			assert_eq!(<Compact<u64>>::decode(&mut &encoded[..]).unwrap().0, n);
667		}
668	}
669
670	#[test]
671	fn compact_32_encoding_works() {
672		let tests = [(0u32, 1usize), (63, 1), (64, 2), (16383, 2), (16384, 4), (1073741823, 4), (1073741824, 5), (u32::max_value(), 5)];
673		for &(n, l) in &tests {
674			let encoded = Compact(n as u32).encode();
675			assert_eq!(encoded.len(), l);
676			assert_eq!(Compact::compact_len(&n), l);
677			assert_eq!(<Compact<u32>>::decode(&mut &encoded[..]).unwrap().0, n);
678		}
679	}
680
681	#[test]
682	fn compact_16_encoding_works() {
683		let tests = [(0u16, 1usize), (63, 1), (64, 2), (16383, 2), (16384, 4), (65535, 4)];
684		for &(n, l) in &tests {
685			let encoded = Compact(n as u16).encode();
686			assert_eq!(encoded.len(), l);
687			assert_eq!(Compact::compact_len(&n), l);
688			assert_eq!(<Compact<u16>>::decode(&mut &encoded[..]).unwrap().0, n);
689		}
690		assert!(<Compact<u16>>::decode(&mut &Compact(65536u32).encode()[..]).is_err());
691	}
692
693	#[test]
694	fn compact_8_encoding_works() {
695		let tests = [(0u8, 1usize), (63, 1), (64, 2), (255, 2)];
696		for &(n, l) in &tests {
697			let encoded = Compact(n as u8).encode();
698			assert_eq!(encoded.len(), l);
699			assert_eq!(Compact::compact_len(&n), l);
700			assert_eq!(<Compact<u8>>::decode(&mut &encoded[..]).unwrap().0, n);
701		}
702		assert!(<Compact<u8>>::decode(&mut &Compact(256u32).encode()[..]).is_err());
703	}
704
705	fn hexify(bytes: &[u8]) -> String {
706		bytes.iter().map(|ref b| format!("{:02x}", b)).collect::<Vec<String>>().join(" ")
707	}
708
709	#[test]
710	fn compact_integers_encoded_as_expected() {
711		let tests = [
712			(0u64, "00"),
713			(63, "fc"),
714			(64, "01 01"),
715			(16383, "fd ff"),
716			(16384, "02 00 01 00"),
717			(1073741823, "fe ff ff ff"),
718			(1073741824, "03 00 00 00 40"),
719			((1 << 32) - 1, "03 ff ff ff ff"),
720			(1 << 32, "07 00 00 00 00 01"),
721			(1 << 40, "0b 00 00 00 00 00 01"),
722			(1 << 48, "0f 00 00 00 00 00 00 01"),
723			((1 << 56) - 1, "0f ff ff ff ff ff ff ff"),
724			(1 << 56, "13 00 00 00 00 00 00 00 01"),
725			(u64::max_value(), "13 ff ff ff ff ff ff ff ff")
726		];
727		for &(n, s) in &tests {
728			// Verify u64 encoding
729			let encoded = Compact(n as u64).encode();
730			assert_eq!(hexify(&encoded), s);
731			assert_eq!(<Compact<u64>>::decode(&mut &encoded[..]).unwrap().0, n);
732
733			// Verify encodings for lower-size uints are compatible with u64 encoding
734			if n <= u32::max_value() as u64 {
735				assert_eq!(<Compact<u32>>::decode(&mut &encoded[..]).unwrap().0, n as u32);
736				let encoded = Compact(n as u32).encode();
737				assert_eq!(hexify(&encoded), s);
738				assert_eq!(<Compact<u64>>::decode(&mut &encoded[..]).unwrap().0, n as u64);
739			}
740			if n <= u16::max_value() as u64 {
741				assert_eq!(<Compact<u16>>::decode(&mut &encoded[..]).unwrap().0, n as u16);
742				let encoded = Compact(n as u16).encode();
743				assert_eq!(hexify(&encoded), s);
744				assert_eq!(<Compact<u64>>::decode(&mut &encoded[..]).unwrap().0, n as u64);
745			}
746			if n <= u8::max_value() as u64 {
747				assert_eq!(<Compact<u8>>::decode(&mut &encoded[..]).unwrap().0, n as u8);
748				let encoded = Compact(n as u8).encode();
749				assert_eq!(hexify(&encoded), s);
750				assert_eq!(<Compact<u64>>::decode(&mut &encoded[..]).unwrap().0, n as u64);
751			}
752		}
753	}
754
755	#[cfg_attr(feature = "std", derive(Serialize, Deserialize, Debug))]
756	#[derive(PartialEq, Eq, Clone)]
757	struct Wrapper(u8);
758
759	impl CompactAs for Wrapper {
760		type As = u8;
761		fn encode_as(&self) -> &u8 {
762			&self.0
763		}
764		fn decode_from(x: u8) -> Result<Wrapper, Error> {
765			Ok(Wrapper(x))
766		}
767	}
768
769	impl From<Compact<Wrapper>> for Wrapper {
770		fn from(x: Compact<Wrapper>) -> Wrapper {
771			x.0
772		}
773	}
774
775	#[test]
776	fn compact_as_8_encoding_works() {
777		let tests = [(0u8, 1usize), (63, 1), (64, 2), (255, 2)];
778		for &(n, l) in &tests {
779			let compact: Compact<Wrapper> = Wrapper(n).into();
780			let encoded = compact.encode();
781			assert_eq!(encoded.len(), l);
782			assert_eq!(Compact::compact_len(&n), l);
783			let decoded = <Compact<Wrapper>>::decode(&mut & encoded[..]).unwrap();
784			let wrapper: Wrapper = decoded.into();
785			assert_eq!(wrapper, Wrapper(n));
786		}
787	}
788
789	struct WithCompact<T: HasCompact> {
790		_data: T,
791	}
792
793	#[test]
794	fn compact_as_has_compact() {
795		let _data = WithCompact { _data: Wrapper(1) };
796	}
797
798	#[test]
799	fn compact_using_encoded_arrayvec_size() {
800		Compact(std::u8::MAX).using_encoded(|_| {});
801		Compact(std::u16::MAX).using_encoded(|_| {});
802		Compact(std::u32::MAX).using_encoded(|_| {});
803		Compact(std::u64::MAX).using_encoded(|_| {});
804		Compact(std::u128::MAX).using_encoded(|_| {});
805
806		CompactRef(&std::u8::MAX).using_encoded(|_| {});
807		CompactRef(&std::u16::MAX).using_encoded(|_| {});
808		CompactRef(&std::u32::MAX).using_encoded(|_| {});
809		CompactRef(&std::u64::MAX).using_encoded(|_| {});
810		CompactRef(&std::u128::MAX).using_encoded(|_| {});
811	}
812
813	#[test]
814	#[should_panic]
815	fn array_vec_output_oob() {
816		let mut v = ArrayVecWrapper(ArrayVec::<[u8; 4]>::new());
817		v.write(&[1, 2, 3, 4, 5]);
818	}
819
820	#[test]
821	fn array_vec_output() {
822		let mut v = ArrayVecWrapper(ArrayVec::<[u8; 4]>::new());
823		v.write(&[1, 2, 3, 4]);
824	}
825
826	macro_rules! check_bound {
827		( $m:expr, $ty:ty, $typ1:ty, [ $(($ty2:ty, $ty2_err:expr)),* ]) => {
828			$(
829				check_bound!($m, $ty, $typ1, $ty2, $ty2_err);
830			)*
831		};
832		( $m:expr, $ty:ty, $typ1:ty, $ty2:ty, $ty2_err:expr) => {
833			let enc = ((<$ty>::max_value() >> 2) as $typ1 << 2) | $m;
834			assert_eq!(Compact::<$ty2>::decode(&mut &enc.to_le_bytes()[..]),
835				Err($ty2_err.into()));
836		};
837	}
838	macro_rules! check_bound_u32 {
839		( [ $(($ty2:ty, $ty2_err:expr)),* ]) => {
840			$(
841				check_bound_u32!($ty2, $ty2_err);
842			)*
843		};
844		( $ty2:ty, $ty2_err:expr ) => {
845			assert_eq!(Compact::<$ty2>::decode(&mut &[0b11, 0xff, 0xff, 0xff, 0xff >> 2][..]),
846				Err($ty2_err.into()));
847		};
848	}
849	macro_rules! check_bound_high {
850		( $m:expr, [ $(($ty2:ty, $ty2_err:expr)),* ]) => {
851			$(
852				check_bound_high!($m, $ty2, $ty2_err);
853			)*
854		};
855		( $s:expr, $ty2:ty, $ty2_err:expr) => {
856			let mut dest = Vec::new();
857			dest.push(0b11 + (($s - 4) << 2) as u8);
858			for _ in 0..($s - 1) {
859				dest.push(u8::max_value());
860			}
861			dest.push(0);
862			assert_eq!(Compact::<$ty2>::decode(&mut &dest[..]),
863				Err($ty2_err.into()));
864		};
865	}
866
867	#[test]
868	fn compact_u64_test() {
869		for a in [
870			u64::max_value(),
871			u64::max_value() - 1,
872			u64::max_value() << 8,
873			(u64::max_value() << 8) - 1,
874			u64::max_value() << 16,
875			(u64::max_value() << 16) - 1,
876		].iter() {
877			let e = Compact::<u64>::encode(&Compact(*a));
878			let d = Compact::<u64>::decode(&mut &e[..]).unwrap().0;
879			assert_eq!(*a, d);
880		}
881	}
882
883	#[test]
884	fn compact_u128_test() {
885		for a in [
886			u64::max_value() as u128,
887			(u64::max_value() - 10) as u128,
888			u128::max_value(),
889			u128::max_value() - 10,
890		].iter() {
891			let e = Compact::<u128>::encode(&Compact(*a));
892			let d = Compact::<u128>::decode(&mut &e[..]).unwrap().0;
893			assert_eq!(*a, d);
894		}
895	}
896
897	#[test]
898	fn should_avoid_overlapping_definition() {
899		check_bound!(
900			0b01, u8, u16, [ (u8, U8_OUT_OF_RANGE), (u16, U16_OUT_OF_RANGE),
901			(u32, U32_OUT_OF_RANGE), (u64, U64_OUT_OF_RANGE), (u128, U128_OUT_OF_RANGE)]
902		);
903		check_bound!(
904			0b10, u16, u32, [ (u16, U16_OUT_OF_RANGE),
905			(u32, U32_OUT_OF_RANGE), (u64, U64_OUT_OF_RANGE), (u128, U128_OUT_OF_RANGE)]
906		);
907		check_bound_u32!(
908			[(u32, U32_OUT_OF_RANGE), (u64, U64_OUT_OF_RANGE), (u128, U128_OUT_OF_RANGE)]
909		);
910		for i in 5..=8 {
911			check_bound_high!(i, [(u64, U64_OUT_OF_RANGE), (u128, U128_OUT_OF_RANGE)]);
912		}
913		for i in 8..=16 {
914			check_bound_high!(i, [(u128, U128_OUT_OF_RANGE)]);
915		}
916	}
917
918	macro_rules! quick_check_roundtrip {
919		( $( $ty:ty : $test:ident ),* ) => {
920			$(
921				quickcheck::quickcheck! {
922					fn $test(v: $ty) -> bool {
923						let encoded = Compact(v).encode();
924						let deencoded = <Compact<$ty>>::decode(&mut &encoded[..]).unwrap().0;
925
926						v == deencoded
927					}
928				}
929			)*
930		}
931	}
932
933	quick_check_roundtrip! {
934		u8: u8_roundtrip,
935		u16: u16_roundtrip,
936		u32 : u32_roundtrip,
937		u64 : u64_roundtrip,
938		u128 : u128_roundtrip
939	}
940}
tetsy_scale_codec/compact.rs

tetsy_scale_codec/
compact.rs
