Grcov report - u64_variablelength.rs

1

use std::io::Read;

2

use std::io::Write;

3

4

use bitstream_io::BitRead;

5

use bitstream_io::BitReader;

6

use bitstream_io::BitWrite;

7

use bitstream_io::BitWriter;

8

use bitstream_io::Endianness;

9

10

use merc_utilities::MercError;

11

12

/// The maximum number of bytes needed to encode a value of type T in most

13

/// significant bit encoding.

14

///

15

/// The encoding stores 7 payload bits per byte, so a `T` of `n` bits needs

16

/// `ceil(n / 7)` bytes. `((size_of::<T>() + 1) * 8) / 7` computes that ceiling

17

/// (e.g. 10 bytes for `u64`).

18

6709759

pub const fn encoding_size<T>() -> usize {

19

6709759

    ((std::mem::size_of::<T>() + 1) * 8) / 7

20

6709759

21

22

/// Encodes a given unsigned variable-length integer using the most significant bit (MSB) algorithm.

23

///

24

/// # Details

25

///

26

/// Implementation taken from <https://techoverflow.net/2013/01/25/efficiently-encoding-variable-length-integers-in-cc/>

27

667320

pub fn write_u64_variablelength<W: Write, E: Endianness>(

28

667320

    stream: &mut BitWriter<W, E>,

29

667320

    mut value: u64,

30

667320

) -> Result<(), MercError> {

31

    // While more than 7 bits of data are left, occupy the last output byte

32

    // and set the next byte flag.

33

878884

    while value > 0b01111111 {

34

211564

        stream.write::<8, u8>((value as u8 & 0b01111111) | 0b10000000)?;

35

36

        // Remove the seven bits we just wrote from value.

37

211564

        value >>= 7;

38

39

40

667320

    stream.write::<8, u8>(value as u8)?;

41

667320

    Ok(())

42

667320

43

44

/// Decodes an unsigned variable-length integer using the MSB algorithm.

45

682071

pub fn read_u64_variablelength<R: Read, E: Endianness>(stream: &mut BitReader<R, E>) -> Result<u64, MercError> {

46

682071

    let mut value: u64 = 0;

47

893711

    for i in 0..encoding_size::<u64>() {

48

893711

        let byte = stream.read::<8, u8>()?;

49

50

        // Take 7 bits (mask 0b01111111) from byte and shift it before the bits already written to value.

51

893711

        value |= ((byte & 0b01111111) as u64) << (7 * i);

52

53

893711

        if byte & 0b10000000 == 0 {

54

            // If the next-byte flag is not set then we are finished.

55

682071

            break;

56

211640

57

58

59

682071

    Ok(value)

60

682071

61

62

#[cfg(test)]

63

mod tests {

64

    use super::BitReader;

65

    use super::BitWriter;

66

    use super::encoding_size;

67

    use super::read_u64_variablelength;

68

    use super::write_u64_variablelength;

69

70

    use bitstream_io::BigEndian;

71

    use rand::RngExt;

72

73

    use merc_utilities::random_test;

74

75

    /// Round-trips `value` through the encoder and decoder and asserts equality.

76

1020

    fn roundtrip(value: u64) {

77

1020

        let mut stream: [u8; encoding_size::<u64>()] = [0; encoding_size::<u64>()];

78

1020

        let mut writer = BitWriter::<_, BigEndian>::new(&mut stream[0..]);

79

1020

        write_u64_variablelength(&mut writer, value).unwrap();

80

81

1020

        let mut reader = BitReader::<_, BigEndian>::new(&stream[0..]);

82

1020

        assert_eq!(read_u64_variablelength(&mut reader).unwrap(), value);

83

1020

84

85

    #[test]

86

1

    fn test_encoding_size() {

87

1

        assert_eq!(encoding_size::<u8>(), 2);

88

1

        assert_eq!(encoding_size::<u16>(), 3);

89

1

        assert_eq!(encoding_size::<u32>(), 5);

90

1

        assert_eq!(encoding_size::<u64>(), 10);

91

1

92

93

    #[test]

94

1

    fn test_boundary_encoding() {

95

        // Edge values and the per-byte continuation boundaries where the

96

        // encoded length grows by one byte (7 payload bits per byte).

97

1

        roundtrip(0);

98

1

        roundtrip(u64::MAX);

99

9

        for shift in [7, 14, 21, 28, 35, 42, 49, 56, 63] {

100

9

            roundtrip((1u64 << shift) - 1);

101

9

            roundtrip(1u64 << shift);

102

9

103

1

104

105

    #[test]

106

1

    fn test_random_integer_encoding() {

107

1000

        random_test(1000, |rng| {

108

1000

            roundtrip(rng.random());

109

1000

});

110

1

111