number_encoding/
sequences.rs

1// Copyright 2022 Google LLC
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//     https://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//! Bit sequence number system
16//!
17//! This permits to convert between variable-length bit sequences (i.e. `[bool]`) and fixed-length
18//! bit sequences (i.e. `usize`).
19
20#[cfg(feature = "alloc")]
21use alloc::vec;
22#[cfg(feature = "alloc")]
23use alloc::vec::Vec;
24
25/// Maximum sequence length.
26pub const MAX_LENGTH: usize = usize::BITS as usize - 1;
27
28/// Maximum sequence value.
29///
30/// Sequences above this value are invalid.
31pub const MAX_SEQUENCE: usize = usize::MAX - 1;
32
33/// Returns the sequence length.
34///
35/// # Panics
36///
37/// Panics in debug mode if `s > MAX_SEQUENCE`.
38pub fn decode_len(s: usize) -> usize {
39    debug_assert!(s <= MAX_SEQUENCE, "Failed precondition");
40    MAX_LENGTH - (s + 1).leading_zeros() as usize
41}
42
43#[test]
44fn decode_len_ok() {
45    fn test(s: usize, n: usize) {
46        assert_eq!(decode_len(s), n, "s={s}");
47    }
48    test(0, 0);
49    test(1, 1);
50    test(2, 1);
51    test(3, 2);
52    test(6, 2);
53    test(7, 3);
54    test(14, 3);
55}
56
57/// Writes the sequence of a value to a slice.
58///
59/// The written sequence can be encoded with [`encode`] to get back `s`.
60///
61/// ```rust
62/// # use number_encoding::sequences::{decode_len, decode_mut, encode};
63/// # let s = 13;
64/// let n = decode_len(s);
65/// let mut xs = vec![false; n];
66/// decode_mut(s, &mut xs);
67/// assert_eq!(encode(&xs), s);
68/// ```
69///
70/// See [`decode`] for a version that allocates a vector for the sequence.
71///
72/// # Panics
73///
74/// Panics in debug mode if `s > MAX_SEQUENCE` or `xs.len() != decode_len(s)`.
75pub fn decode_mut(s: usize, xs: &mut [bool]) {
76    debug_assert!(s <= MAX_SEQUENCE, "Failed precondition");
77    let n = decode_len(s);
78    debug_assert_eq!(xs.len(), n, "Failed precondition");
79    for (i, x) in xs.iter_mut().rev().enumerate() {
80        *x = (s + 1) & 1 << i != 0;
81    }
82}
83
84/// Returns the sequence of a value.
85///
86/// The returned sequence can be encoded with [`encode`] to get back `s`.
87///
88/// ```rust
89/// # use number_encoding::sequences::{decode, encode};
90/// let s = 13;
91/// let xs = decode(s);
92/// assert_eq!(encode(&xs), s);
93/// ```
94///
95/// See [`decode_mut`] for a version that writes the sequence to a provided slice.
96///
97/// # Panics
98///
99/// Panics in debug mode if `s > MAX_SEQUENCE`.
100///
101/// # Examples
102///
103/// ```rust
104/// # use number_encoding::sequences::decode;
105/// assert_eq!(decode(0), &[]);
106/// assert_eq!(decode(1), &[false]);
107/// assert_eq!(decode(2), &[true]);
108/// assert_eq!(decode(13), &[true, true, false]);
109/// ```
110#[cfg(feature = "alloc")]
111pub fn decode(s: usize) -> Vec<bool> {
112    let n = decode_len(s);
113    let mut xs = vec![false; n];
114    decode_mut(s, &mut xs);
115    xs
116}
117
118#[test]
119fn decode_ok() {
120    fn test(s: usize, xs: &[bool]) {
121        assert_eq!(decode(s), xs, "s={s} xs={xs:?}");
122    }
123    test(0, &[]);
124    test(1, &[false]);
125    test(2, &[true]);
126    test(3, &[false, false]);
127    test(4, &[false, true]);
128    test(5, &[true, false]);
129    test(6, &[true, true]);
130    test(7, &[false, false, false]);
131    test(8, &[false, false, true]);
132    test(9, &[false, true, false]);
133    test(10, &[false, true, true]);
134    test(11, &[true, false, false]);
135    test(12, &[true, false, true]);
136    test(13, &[true, true, false]);
137    test(14, &[true, true, true]);
138}
139
140/// Returns the value of a sequence.
141///
142/// The returned value can be decoded with [`decode`] to get back `xs`.
143///
144/// ```rust
145/// # use number_encoding::sequences::{decode, encode};
146/// # let xs = &[true, true, false];
147/// let s = encode(xs);
148/// assert_eq!(decode(s), xs);
149/// ```
150///
151/// # Panics
152///
153/// Panics in debug mode if `xs.len() > MAX_LENGTH`.
154///
155/// # Examples
156///
157/// ```rust
158/// # use number_encoding::sequences::encode;
159/// assert_eq!(encode(&[]), 0);
160/// assert_eq!(encode(&[false]), 1);
161/// assert_eq!(encode(&[true]), 2);
162/// assert_eq!(encode(&[true, true, false]), 13);
163/// ```
164pub fn encode(xs: &[bool]) -> usize {
165    debug_assert!(xs.len() <= MAX_LENGTH, "Failed precondition");
166    let mut s = 0;
167    for &x in xs {
168        s = 2 * s + 1 + x as usize;
169    }
170    s
171}
172
173#[test]
174fn encode_ok() {
175    fn test(xs: &[bool], s: usize) {
176        assert_eq!(encode(xs), s, "xs={xs:?}");
177    }
178    test(&[], 0);
179    test(&[false], 1);
180    test(&[true], 2);
181    test(&[false, false], 3);
182    test(&[false, true], 4);
183    test(&[true, false], 5);
184    test(&[true, true], 6);
185    test(&[false, false, false], 7);
186    test(&[false, false, true], 8);
187    test(&[false, true, false], 9);
188    test(&[false, true, true], 10);
189    test(&[true, false, false], 11);
190    test(&[true, false, true], 12);
191    test(&[true, true, false], 13);
192    test(&[true, true, true], 14);
193}
number_encoding/sequences.rs

number_encoding/
sequences.rs
