parity_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://docs.substrate.io/v3/advanced/scale-codec/#compactgeneral-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<const N: usize>(ArrayVec<u8, N>);
27
28impl<const N: usize> Output for ArrayVecWrapper<N> {
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 = "serde")]
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 = "serde")]
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 >> 2 {
491					x
492				} else {
493					return Err(U32_OUT_OF_RANGE.into());
494				}
495			},
496			3 => {
497				if prefix >> 2 == 0 {
498					// just 4 bytes. ok.
499					let x = u32::decode(input)?;
500					if x > u32::MAX >> 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			_ => unreachable!(),
511		}))
512	}
513}
514
515impl Decode for Compact<u64> {
516	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
517		let prefix = input.read_byte()?;
518		Ok(Compact(match prefix % 4 {
519			0 => u64::from(prefix) >> 2,
520			1 => {
521				let x = u16::decode(&mut PrefixInput{prefix: Some(prefix), input})? >> 2;
522				if x > 0b0011_1111 && x <= 0b0011_1111_1111_1111 {
523					u64::from(x)
524				} else {
525					return Err(U64_OUT_OF_RANGE.into());
526				}
527			},
528			2 => {
529				let x = u32::decode(&mut PrefixInput{prefix: Some(prefix), input})? >> 2;
530				if x > 0b0011_1111_1111_1111 && x <= u32::MAX >> 2 {
531					u64::from(x)
532				} else {
533					return Err(U64_OUT_OF_RANGE.into());
534				}
535			},
536			3 => match (prefix >> 2) + 4 {
537				4 => {
538					let x = u32::decode(input)?;
539					if x > u32::MAX >> 2 {
540						u64::from(x)
541					} else {
542						return Err(U64_OUT_OF_RANGE.into());
543					}
544				},
545				8 => {
546					let x = u64::decode(input)?;
547					if x > u64::MAX >> 8 {
548						x
549					} else {
550						return Err(U64_OUT_OF_RANGE.into());
551					}
552				},
553				x if x > 8 => return Err("unexpected prefix decoding Compact<u64>".into()),
554				bytes_needed => {
555					let mut res = 0;
556					for i in 0..bytes_needed {
557						res |= u64::from(input.read_byte()?) << (i * 8);
558					}
559					if res > u64::MAX >> ((8 - bytes_needed + 1) * 8) {
560						res
561					} else {
562						return Err(U64_OUT_OF_RANGE.into());
563					}
564				},
565			},
566			_ => unreachable!(),
567		}))
568	}
569}
570
571impl Decode for Compact<u128> {
572	fn decode<I: Input>(input: &mut I) -> Result<Self, Error> {
573		let prefix = input.read_byte()?;
574		Ok(Compact(match prefix % 4 {
575			0 => u128::from(prefix) >> 2,
576			1 => {
577				let x = u16::decode(&mut PrefixInput{prefix: Some(prefix), input})? >> 2;
578				if x > 0b0011_1111 && x <= 0b0011_1111_1111_1111 {
579					u128::from(x)
580				} else {
581					return Err(U128_OUT_OF_RANGE.into());
582				}
583			},
584			2 => {
585				let x = u32::decode(&mut PrefixInput{prefix: Some(prefix), input})? >> 2;
586				if x > 0b0011_1111_1111_1111 && x <= u32::MAX >> 2 {
587					u128::from(x)
588				} else {
589					return Err(U128_OUT_OF_RANGE.into());
590				}
591			},
592			3 => match (prefix >> 2) + 4 {
593				4 => {
594					let x = u32::decode(input)?;
595					if x > u32::MAX >> 2 {
596						u128::from(x)
597					} else {
598						return Err(U128_OUT_OF_RANGE.into());
599					}
600				},
601				8 => {
602					let x = u64::decode(input)?;
603					if x > u64::MAX >> 8 {
604						u128::from(x)
605					} else {
606						return Err(U128_OUT_OF_RANGE.into());
607					}
608				},
609				16 => {
610					let x = u128::decode(input)?;
611					if x > u128::MAX >> 8 {
612						x
613					} else {
614						return Err(U128_OUT_OF_RANGE.into());
615					}
616				},
617				x if x > 16 => return Err("unexpected prefix decoding Compact<u128>".into()),
618				bytes_needed => {
619					let mut res = 0;
620					for i in 0..bytes_needed {
621						res |= u128::from(input.read_byte()?) << (i * 8);
622					}
623					if res > u128::MAX >> ((16 - bytes_needed + 1) * 8) {
624						res
625					} else {
626						return Err(U128_OUT_OF_RANGE.into());
627					}
628				},
629			},
630			_ => unreachable!(),
631		}))
632	}
633}
634
635#[cfg(test)]
636mod tests {
637	use super::*;
638
639	#[test]
640	fn compact_128_encoding_works() {
641		let tests = [
642			(0u128, 1usize), (63, 1), (64, 2), (16383, 2),
643			(16384, 4), (1073741823, 4),
644			(1073741824, 5), ((1 << 32) - 1, 5),
645			(1 << 32, 6), (1 << 40, 7), (1 << 48, 8), ((1 << 56) - 1, 8), (1 << 56, 9), ((1 << 64) - 1, 9),
646			(1 << 64, 10), (1 << 72, 11), (1 << 80, 12), (1 << 88, 13), (1 << 96, 14), (1 << 104, 15),
647			(1 << 112, 16), ((1 << 120) - 1, 16), (1 << 120, 17), (u128::MAX, 17)
648		];
649		for &(n, l) in &tests {
650			let encoded = Compact(n as u128).encode();
651			assert_eq!(encoded.len(), l);
652			assert_eq!(Compact::compact_len(&n), l);
653			assert_eq!(<Compact<u128>>::decode(&mut &encoded[..]).unwrap().0, n);
654		}
655	}
656
657	#[test]
658	fn compact_64_encoding_works() {
659		let tests = [
660			(0u64, 1usize), (63, 1), (64, 2), (16383, 2),
661			(16384, 4), (1073741823, 4),
662			(1073741824, 5), ((1 << 32) - 1, 5),
663			(1 << 32, 6), (1 << 40, 7), (1 << 48, 8), ((1 << 56) - 1, 8), (1 << 56, 9), (u64::MAX, 9)
664		];
665		for &(n, l) in &tests {
666			let encoded = Compact(n as u64).encode();
667			assert_eq!(encoded.len(), l);
668			assert_eq!(Compact::compact_len(&n), l);
669			assert_eq!(<Compact<u64>>::decode(&mut &encoded[..]).unwrap().0, n);
670		}
671	}
672
673	#[test]
674	fn compact_32_encoding_works() {
675		let tests = [(0u32, 1usize), (63, 1), (64, 2), (16383, 2), (16384, 4), (1073741823, 4), (1073741824, 5), (u32::MAX, 5)];
676		for &(n, l) in &tests {
677			let encoded = Compact(n as u32).encode();
678			assert_eq!(encoded.len(), l);
679			assert_eq!(Compact::compact_len(&n), l);
680			assert_eq!(<Compact<u32>>::decode(&mut &encoded[..]).unwrap().0, n);
681		}
682	}
683
684	#[test]
685	fn compact_16_encoding_works() {
686		let tests = [(0u16, 1usize), (63, 1), (64, 2), (16383, 2), (16384, 4), (65535, 4)];
687		for &(n, l) in &tests {
688			let encoded = Compact(n as u16).encode();
689			assert_eq!(encoded.len(), l);
690			assert_eq!(Compact::compact_len(&n), l);
691			assert_eq!(<Compact<u16>>::decode(&mut &encoded[..]).unwrap().0, n);
692		}
693		assert!(<Compact<u16>>::decode(&mut &Compact(65536u32).encode()[..]).is_err());
694	}
695
696	#[test]
697	fn compact_8_encoding_works() {
698		let tests = [(0u8, 1usize), (63, 1), (64, 2), (255, 2)];
699		for &(n, l) in &tests {
700			let encoded = Compact(n as u8).encode();
701			assert_eq!(encoded.len(), l);
702			assert_eq!(Compact::compact_len(&n), l);
703			assert_eq!(<Compact<u8>>::decode(&mut &encoded[..]).unwrap().0, n);
704		}
705		assert!(<Compact<u8>>::decode(&mut &Compact(256u32).encode()[..]).is_err());
706	}
707
708	fn hexify(bytes: &[u8]) -> String {
709		bytes.iter().map(|ref b| format!("{:02x}", b)).collect::<Vec<String>>().join(" ")
710	}
711
712	#[test]
713	fn compact_integers_encoded_as_expected() {
714		let tests = [
715			(0u64, "00"),
716			(63, "fc"),
717			(64, "01 01"),
718			(16383, "fd ff"),
719			(16384, "02 00 01 00"),
720			(1073741823, "fe ff ff ff"),
721			(1073741824, "03 00 00 00 40"),
722			((1 << 32) - 1, "03 ff ff ff ff"),
723			(1 << 32, "07 00 00 00 00 01"),
724			(1 << 40, "0b 00 00 00 00 00 01"),
725			(1 << 48, "0f 00 00 00 00 00 00 01"),
726			((1 << 56) - 1, "0f ff ff ff ff ff ff ff"),
727			(1 << 56, "13 00 00 00 00 00 00 00 01"),
728			(u64::MAX, "13 ff ff ff ff ff ff ff ff")
729		];
730		for &(n, s) in &tests {
731			// Verify u64 encoding
732			let encoded = Compact(n as u64).encode();
733			assert_eq!(hexify(&encoded), s);
734			assert_eq!(<Compact<u64>>::decode(&mut &encoded[..]).unwrap().0, n);
735
736			// Verify encodings for lower-size uints are compatible with u64 encoding
737			if n <= u32::MAX as u64 {
738				assert_eq!(<Compact<u32>>::decode(&mut &encoded[..]).unwrap().0, n as u32);
739				let encoded = Compact(n as u32).encode();
740				assert_eq!(hexify(&encoded), s);
741				assert_eq!(<Compact<u64>>::decode(&mut &encoded[..]).unwrap().0, n as u64);
742			}
743			if n <= u16::MAX as u64 {
744				assert_eq!(<Compact<u16>>::decode(&mut &encoded[..]).unwrap().0, n as u16);
745				let encoded = Compact(n as u16).encode();
746				assert_eq!(hexify(&encoded), s);
747				assert_eq!(<Compact<u64>>::decode(&mut &encoded[..]).unwrap().0, n as u64);
748			}
749			if n <= u8::MAX as u64 {
750				assert_eq!(<Compact<u8>>::decode(&mut &encoded[..]).unwrap().0, n as u8);
751				let encoded = Compact(n as u8).encode();
752				assert_eq!(hexify(&encoded), s);
753				assert_eq!(<Compact<u64>>::decode(&mut &encoded[..]).unwrap().0, n as u64);
754			}
755		}
756	}
757
758	#[cfg_attr(feature = "std", derive(Serialize, Deserialize, Debug))]
759	#[derive(PartialEq, Eq, Clone)]
760	struct Wrapper(u8);
761
762	impl CompactAs for Wrapper {
763		type As = u8;
764		fn encode_as(&self) -> &u8 {
765			&self.0
766		}
767		fn decode_from(x: u8) -> Result<Wrapper, Error> {
768			Ok(Wrapper(x))
769		}
770	}
771
772	impl From<Compact<Wrapper>> for Wrapper {
773		fn from(x: Compact<Wrapper>) -> Wrapper {
774			x.0
775		}
776	}
777
778	#[test]
779	fn compact_as_8_encoding_works() {
780		let tests = [(0u8, 1usize), (63, 1), (64, 2), (255, 2)];
781		for &(n, l) in &tests {
782			let compact: Compact<Wrapper> = Wrapper(n).into();
783			let encoded = compact.encode();
784			assert_eq!(encoded.len(), l);
785			assert_eq!(Compact::compact_len(&n), l);
786			let decoded = <Compact<Wrapper>>::decode(&mut & encoded[..]).unwrap();
787			let wrapper: Wrapper = decoded.into();
788			assert_eq!(wrapper, Wrapper(n));
789		}
790	}
791
792	struct WithCompact<T: HasCompact> {
793		_data: T,
794	}
795
796	#[test]
797	fn compact_as_has_compact() {
798		let _data = WithCompact { _data: Wrapper(1) };
799	}
800
801	#[test]
802	fn compact_using_encoded_arrayvec_size() {
803		Compact(u8::MAX).using_encoded(|_| {});
804		Compact(u16::MAX).using_encoded(|_| {});
805		Compact(u32::MAX).using_encoded(|_| {});
806		Compact(u64::MAX).using_encoded(|_| {});
807		Compact(u128::MAX).using_encoded(|_| {});
808
809		CompactRef(&u8::MAX).using_encoded(|_| {});
810		CompactRef(&u16::MAX).using_encoded(|_| {});
811		CompactRef(&u32::MAX).using_encoded(|_| {});
812		CompactRef(&u64::MAX).using_encoded(|_| {});
813		CompactRef(&u128::MAX).using_encoded(|_| {});
814	}
815
816	#[test]
817	#[should_panic]
818	fn array_vec_output_oob() {
819		let mut v = ArrayVecWrapper(ArrayVec::<u8, 4>::new());
820		v.write(&[1, 2, 3, 4, 5]);
821	}
822
823	#[test]
824	fn array_vec_output() {
825		let mut v = ArrayVecWrapper(ArrayVec::<u8, 4>::new());
826		v.write(&[1, 2, 3, 4]);
827	}
828
829	macro_rules! check_bound {
830		( $m:expr, $ty:ty, $typ1:ty, [ $(($ty2:ty, $ty2_err:expr)),* ]) => {
831			$(
832				check_bound!($m, $ty, $typ1, $ty2, $ty2_err);
833			)*
834		};
835		( $m:expr, $ty:ty, $typ1:ty, $ty2:ty, $ty2_err:expr) => {
836			let enc = ((<$ty>::MAX >> 2) as $typ1 << 2) | $m;
837			assert_eq!(Compact::<$ty2>::decode(&mut &enc.to_le_bytes()[..]),
838				Err($ty2_err.into()));
839		};
840	}
841	macro_rules! check_bound_u32 {
842		( [ $(($ty2:ty, $ty2_err:expr)),* ]) => {
843			$(
844				check_bound_u32!($ty2, $ty2_err);
845			)*
846		};
847		( $ty2:ty, $ty2_err:expr ) => {
848			assert_eq!(Compact::<$ty2>::decode(&mut &[0b11, 0xff, 0xff, 0xff, 0xff >> 2][..]),
849				Err($ty2_err.into()));
850		};
851	}
852	macro_rules! check_bound_high {
853		( $m:expr, [ $(($ty2:ty, $ty2_err:expr)),* ]) => {
854			$(
855				check_bound_high!($m, $ty2, $ty2_err);
856			)*
857		};
858		( $s:expr, $ty2:ty, $ty2_err:expr) => {
859			let mut dest = Vec::new();
860			dest.push(0b11 + (($s - 4) << 2) as u8);
861			for _ in 0..($s - 1) {
862				dest.push(u8::MAX);
863			}
864			dest.push(0);
865			assert_eq!(Compact::<$ty2>::decode(&mut &dest[..]),
866				Err($ty2_err.into()));
867		};
868	}
869
870	#[test]
871	fn compact_u64_test() {
872		for a in [
873			u64::MAX,
874			u64::MAX - 1,
875			u64::MAX << 8,
876			(u64::MAX << 8) - 1,
877			u64::MAX << 16,
878			(u64::MAX << 16) - 1,
879		].iter() {
880			let e = Compact::<u64>::encode(&Compact(*a));
881			let d = Compact::<u64>::decode(&mut &e[..]).unwrap().0;
882			assert_eq!(*a, d);
883		}
884	}
885
886	#[test]
887	fn compact_u128_test() {
888		for a in [
889			u64::MAX as u128,
890			(u64::MAX - 10) as u128,
891			u128::MAX,
892			u128::MAX - 10,
893		].iter() {
894			let e = Compact::<u128>::encode(&Compact(*a));
895			let d = Compact::<u128>::decode(&mut &e[..]).unwrap().0;
896			assert_eq!(*a, d);
897		}
898	}
899
900	#[test]
901	fn should_avoid_overlapping_definition() {
902		check_bound!(
903			0b01, u8, u16, [ (u8, U8_OUT_OF_RANGE), (u16, U16_OUT_OF_RANGE),
904			(u32, U32_OUT_OF_RANGE), (u64, U64_OUT_OF_RANGE), (u128, U128_OUT_OF_RANGE)]
905		);
906		check_bound!(
907			0b10, u16, u32, [ (u16, U16_OUT_OF_RANGE),
908			(u32, U32_OUT_OF_RANGE), (u64, U64_OUT_OF_RANGE), (u128, U128_OUT_OF_RANGE)]
909		);
910		check_bound_u32!(
911			[(u32, U32_OUT_OF_RANGE), (u64, U64_OUT_OF_RANGE), (u128, U128_OUT_OF_RANGE)]
912		);
913		for i in 5..=8 {
914			check_bound_high!(i, [(u64, U64_OUT_OF_RANGE), (u128, U128_OUT_OF_RANGE)]);
915		}
916		for i in 8..=16 {
917			check_bound_high!(i, [(u128, U128_OUT_OF_RANGE)]);
918		}
919	}
920
921	macro_rules! quick_check_roundtrip {
922		( $( $ty:ty : $test:ident ),* ) => {
923			$(
924				quickcheck::quickcheck! {
925					fn $test(v: $ty) -> bool {
926						let encoded = Compact(v).encode();
927						let deencoded = <Compact<$ty>>::decode(&mut &encoded[..]).unwrap().0;
928
929						v == deencoded
930					}
931				}
932			)*
933		}
934	}
935
936	quick_check_roundtrip! {
937		u8: u8_roundtrip,
938		u16: u16_roundtrip,
939		u32 : u32_roundtrip,
940		u64 : u64_roundtrip,
941		u128 : u128_roundtrip
942	}
943}
parity_scale_codec/compact.rs

parity_scale_codec/
compact.rs
