yrs/encoding/
varint.rs

1use crate::encoding::read::{Error, Read};
2use crate::encoding::write::Write;
3use std::convert::TryInto;
4
5pub trait VarInt: Sized + Copy {
6    fn write<W: Write>(&self, w: &mut W);
7    fn read<R: Read>(r: &mut R) -> Result<Self, Error>;
8}
9
10impl VarInt for usize {
11    #[inline]
12    fn write<W: Write>(&self, w: &mut W) {
13        write_var_u64(*self as u64, w)
14    }
15
16    #[inline]
17    fn read<R: Read>(r: &mut R) -> Result<Self, Error> {
18        Ok(read_var_u64(r)? as Self)
19    }
20}
21
22impl VarInt for u128 {
23    fn write<W: Write>(&self, w: &mut W) {
24        let mut value = *self;
25        while value >= 0b10000000 {
26            let b = ((value & 0b01111111) as u8) | 0b10000000;
27            w.write_u8(b);
28            value = value >> 7;
29        }
30
31        w.write_u8((value & 0b01111111) as u8)
32    }
33
34    #[inline]
35    fn read<R: Read>(r: &mut R) -> Result<Self, Error> {
36        let mut num = 0u128;
37        let mut len: usize = 0;
38        loop {
39            let r = r.read_u8()?;
40            num |= u128::wrapping_shl((r & 0b01111111) as u128, len as u32);
41            len += 7;
42            if r < 0b10000000 {
43                return Ok(num);
44            }
45            if len > 180 {
46                return Err(Error::InvalidVarInt);
47            }
48        }
49    }
50}
51
52impl VarInt for u64 {
53    #[inline]
54    fn write<W: Write>(&self, w: &mut W) {
55        write_var_u64(*self, w)
56    }
57
58    #[inline]
59    fn read<R: Read>(r: &mut R) -> Result<Self, Error> {
60        read_var_u64(r)
61    }
62}
63
64impl VarInt for u32 {
65    #[inline]
66    fn write<W: Write>(&self, w: &mut W) {
67        write_var_u32(*self, w)
68    }
69
70    #[inline]
71    fn read<R: Read>(r: &mut R) -> Result<Self, Error> {
72        read_var_u32(r)
73    }
74}
75
76impl VarInt for u16 {
77    #[inline]
78    fn write<W: Write>(&self, w: &mut W) {
79        write_var_u32(*self as u32, w)
80    }
81
82    fn read<R: Read>(r: &mut R) -> Result<Self, Error> {
83        let value = read_var_u32(r)?;
84        if let Ok(value) = value.try_into() {
85            Ok(value)
86        } else {
87            Err(Error::InvalidVarInt)
88        }
89    }
90}
91
92impl VarInt for u8 {
93    #[inline]
94    fn write<W: Write>(&self, w: &mut W) {
95        write_var_u32(*self as u32, w)
96    }
97
98    fn read<R: Read>(r: &mut R) -> Result<Self, Error> {
99        let value = read_var_u32(r)?;
100        if let Ok(value) = value.try_into() {
101            Ok(value)
102        } else {
103            Err(Error::InvalidVarInt)
104        }
105    }
106}
107
108impl VarInt for isize {
109    #[inline]
110    fn write<W: Write>(&self, w: &mut W) {
111        write_var_i64(*self as i64, w)
112    }
113
114    fn read<R: Read>(r: &mut R) -> Result<Self, Error> {
115        let value = read_var_i64(r)?;
116        if let Ok(value) = value.try_into() {
117            Ok(value)
118        } else {
119            Err(Error::InvalidVarInt)
120        }
121    }
122}
123
124impl VarInt for i64 {
125    #[inline]
126    fn write<W: Write>(&self, w: &mut W) {
127        write_var_i64(*self, w)
128    }
129
130    #[inline]
131    fn read<R: Read>(r: &mut R) -> Result<Self, Error> {
132        read_var_i64(r)
133    }
134}
135
136impl VarInt for i32 {
137    #[inline]
138    fn write<W: Write>(&self, w: &mut W) {
139        write_var_i64(*self as i64, w)
140    }
141
142    fn read<R: Read>(r: &mut R) -> Result<Self, Error> {
143        let value = read_var_i64(r)?;
144        if let Ok(value) = value.try_into() {
145            Ok(value)
146        } else {
147            Err(Error::InvalidVarInt)
148        }
149    }
150}
151
152impl VarInt for i16 {
153    #[inline]
154    fn write<W: Write>(&self, w: &mut W) {
155        write_var_i64(*self as i64, w)
156    }
157
158    fn read<R: Read>(r: &mut R) -> Result<Self, Error> {
159        let value = read_var_i64(r)?;
160        if let Ok(value) = value.try_into() {
161            Ok(value)
162        } else {
163            Err(Error::InvalidVarInt)
164        }
165    }
166}
167
168impl VarInt for i8 {
169    #[inline]
170    fn write<W: Write>(&self, w: &mut W) {
171        write_var_i64(*self as i64, w)
172    }
173
174    fn read<R: Read>(r: &mut R) -> Result<Self, Error> {
175        let value = read_var_i64(r)?;
176        if let Ok(value) = value.try_into() {
177            Ok(value)
178        } else {
179            Err(Error::InvalidVarInt)
180        }
181    }
182}
183
184fn write_var_u32<W: Write>(mut value: u32, w: &mut W) {
185    while value >= 0b10000000 {
186        let b = ((value & 0b01111111) as u8) | 0b10000000;
187        w.write_u8(b);
188        value = value >> 7;
189    }
190
191    w.write_u8((value & 0b01111111) as u8)
192}
193
194fn write_var_u64<W: Write>(mut value: u64, w: &mut W) {
195    while value >= 0b10000000 {
196        let b = ((value & 0b01111111) as u8) | 0b10000000;
197        w.write_u8(b);
198        value = value >> 7;
199    }
200
201    w.write_u8((value & 0b01111111) as u8)
202}
203
204fn write_var_i64<W: Write>(mut value: i64, w: &mut W) {
205    let is_negative = value < 0;
206    value = if is_negative { -value } else { value };
207    w.write_u8(
208        // whether to continue reading
209        (if value > 0b00111111 as i64 { 0b10000000 as u8 } else { 0 })
210            // whether number is negative
211            | (if is_negative { 0b01000000 as u8 } else { 0 })
212            // number
213            | (0b00111111 as i64 & value) as u8,
214    );
215    value >>= 6;
216    while value > 0 {
217        w.write_u8(
218            if value > 0b01111111 as i64 {
219                0b10000000 as u8
220            } else {
221                0
222            } | (0b01111111 as i64 & value) as u8,
223        );
224        value >>= 7;
225    }
226}
227
228fn read_var_u64<R: Read>(r: &mut R) -> Result<u64, Error> {
229    let mut num = 0;
230    let mut len: usize = 0;
231    loop {
232        let r = r.read_u8()?;
233        num |= u64::wrapping_shl((r & 0b01111111) as u64, len as u32);
234        len += 7;
235        if r < 0b10000000 {
236            return Ok(num);
237        }
238        if len > 70 {
239            return Err(Error::InvalidVarInt);
240        }
241    }
242}
243
244fn read_var_u32<R: Read>(r: &mut R) -> Result<u32, Error> {
245    let mut num = 0;
246    let mut len: usize = 0;
247    loop {
248        let r = r.read_u8()?;
249        num |= u32::wrapping_shl((r & 0b01111111) as u32, len as u32);
250        len += 7;
251        if r < 0b10000000 {
252            return Ok(num);
253        }
254        if len > 70 {
255            // a proper setting for 32bit int would be 35 bits, however for Yjs compatibility
256            // we allow wrap up up to 64bit ints (with int overflow wrap)
257            return Err(Error::InvalidVarInt);
258        }
259    }
260}
261
262fn read_var_i64<R: Read>(reader: &mut R) -> Result<i64, Error> {
263    let mut r = reader.read_u8()?;
264    let mut num = (r & 0b00111111 as u8) as i64;
265    let mut len: u32 = 6;
266    let is_negative = r & 0b01000000 as u8 > 0;
267    if r & 0b10000000 as u8 == 0 {
268        return Ok(if is_negative { -num } else { num });
269    }
270    loop {
271        r = reader.read_u8()?;
272        num |= (r as i64 & 0b01111111 as i64) << len;
273        len += 7;
274        if r < 0b10000000 as u8 {
275            return Ok(if is_negative { -num } else { num });
276        }
277        if len > 70 {
278            return Err(Error::InvalidVarInt);
279        }
280    }
281}
282
283pub trait SignedVarInt: Sized + Copy {
284    fn write_signed<W: Write>(value: &Signed<Self>, w: &mut W);
285    fn read_signed<R: Read>(r: &mut R) -> Result<Signed<Self>, Error>;
286}
287
288/// Struct which recognizes signed integer values. This special case has been build for Yjs encoding
289/// compatibility, which recognizes differences between `0` and `-0`, which is used in some
290/// cases (eg. `UIntOptRleDecoder`).
291#[derive(Debug, Clone, Eq, PartialEq)]
292pub struct Signed<T: Sized + Copy> {
293    value: T,
294    is_negative: bool,
295}
296
297impl<T: Sized + Copy> Signed<T> {
298    pub fn new(value: T, is_negative: bool) -> Self {
299        Signed { value, is_negative }
300    }
301
302    /// Returns true is stored number is a positive value.
303    pub fn is_positive(&self) -> bool {
304        !self.is_negative
305    }
306
307    /// Returns true is stored number is a negative value (including `-0` as a special case).
308    pub fn is_negative(&self) -> bool {
309        self.is_negative
310    }
311
312    /// Returns a stored value.
313    pub fn value(&self) -> T {
314        self.value
315    }
316
317    /// Maps contents of a [Signed] value container to a new data type, retaining the sign
318    /// information.
319    pub fn map<F, U>(&self, f: F) -> Signed<U>
320    where
321        F: FnOnce(T) -> U,
322        U: Sized + Copy,
323    {
324        let mapped = f(self.value);
325        Signed::new(mapped, self.is_negative)
326    }
327}
328
329impl SignedVarInt for i64 {
330    fn write_signed<W: Write>(s: &Signed<Self>, w: &mut W) {
331        let mut value = s.value;
332        let is_negative = s.is_negative;
333        value = if is_negative { -value } else { value };
334        w.write_u8(
335            // whether to continue reading
336            (if value > 0b00111111 as i64 { 0b10000000 as u8 } else { 0 })
337                // whether number is negative
338                | (if is_negative { 0b01000000 as u8 } else { 0 })
339                // number
340                | (0b00111111 as i64 & value) as u8,
341        );
342        value >>= 6;
343        while value > 0 {
344            w.write_u8(
345                if value > 0b01111111 as i64 {
346                    0b10000000 as u8
347                } else {
348                    0
349                } | (0b01111111 as i64 & value) as u8,
350            );
351            value >>= 7;
352        }
353    }
354
355    fn read_signed<R: Read>(reader: &mut R) -> Result<Signed<Self>, Error> {
356        let mut r = reader.read_u8()?;
357        let mut num = (r & 0b00111111 as u8) as i64;
358        let mut len: u32 = 6;
359        let is_negative = r & 0b01000000 as u8 > 0;
360        if r & 0b10000000 as u8 == 0 {
361            let num = if is_negative { -num } else { num };
362            return Ok(Signed::new(num, is_negative));
363        }
364        loop {
365            r = reader.read_u8()?;
366            num |= (r as i64 & 0b01111111 as i64) << len;
367            len += 7;
368            if r < 0b10000000 as u8 {
369                let num = if is_negative { -num } else { num };
370                return Ok(Signed::new(num, is_negative));
371            }
372            if len > 70 {
373                return Err(Error::InvalidVarInt);
374            }
375        }
376    }
377}
378
379impl SignedVarInt for isize {
380    fn write_signed<W: Write>(value: &Signed<Self>, w: &mut W) {
381        let value = value.map(|v| v as i64);
382        i64::write_signed(&value, w)
383    }
384
385    fn read_signed<R: Read>(r: &mut R) -> Result<Signed<Self>, Error> {
386        let result = i64::read_signed(r)?;
387        match result.value.try_into() {
388            Ok(i) => Ok(Signed::new(i, result.is_negative)),
389            Err(_) => Err(Error::InvalidVarInt),
390        }
391    }
392}
393
394impl SignedVarInt for i32 {
395    fn write_signed<W: Write>(value: &Signed<Self>, w: &mut W) {
396        let value = value.map(|v| v as i64);
397        i64::write_signed(&value, w)
398    }
399
400    fn read_signed<R: Read>(r: &mut R) -> Result<Signed<Self>, Error> {
401        let result = i64::read_signed(r)?;
402        match result.value.try_into() {
403            Ok(i) => Ok(Signed::new(i, result.is_negative)),
404            Err(_) => Err(Error::InvalidVarInt),
405        }
406    }
407}
408
409impl SignedVarInt for i16 {
410    fn write_signed<W: Write>(value: &Signed<Self>, w: &mut W) {
411        let value = value.map(|v| v as i64);
412        i64::write_signed(&value, w)
413    }
414
415    fn read_signed<R: Read>(r: &mut R) -> Result<Signed<Self>, Error> {
416        let result = i64::read_signed(r)?;
417        match result.value.try_into() {
418            Ok(i) => Ok(Signed::new(i, result.is_negative)),
419            Err(_) => Err(Error::InvalidVarInt),
420        }
421    }
422}
423
424impl SignedVarInt for i8 {
425    fn write_signed<W: Write>(value: &Signed<Self>, w: &mut W) {
426        let value = value.map(|v| v as i64);
427        i64::write_signed(&value, w)
428    }
429
430    fn read_signed<R: Read>(r: &mut R) -> Result<Signed<Self>, Error> {
431        let result = i64::read_signed(r)?;
432        match result.value.try_into() {
433            Ok(i) => Ok(Signed::new(i, result.is_negative)),
434            Err(_) => Err(Error::InvalidVarInt),
435        }
436    }
437}
yrs/encoding/varint.rs

yrs/encoding/
varint.rs
