1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

use generic_array::{
    typenum::{UTerm, Unsigned},
    ArrayLength, GenericArray,
};
use std::mem;

pub enum TagPosition {
    Lo,
    Hi,
}

impl TagPosition {
    /// Calculates the start bit offset of the tag depending on the position and type.
    fn to_skip<T: Tag>(&self) -> usize {
        match self {
            // low tags always start at 0
            TagPosition::Lo => 0,

            // high tags occupy the highest bits so the start offset is the max index minus the size
            TagPosition::Hi => {
                let usize_bits = mem::size_of::<usize>() * 8;
                usize_bits - <T::Size as Unsigned>::to_usize()
            }
        }
    }
}

/// Zeroes all the tag bits.
pub fn strip<T1: Tag, T2: Tag>(data: usize) -> usize {
    // mask for zeroing the low tag
    let mask1: usize = std::usize::MAX >> <T1::Size as Unsigned>::to_usize();

    // mask for zeroing the high tag
    let mask2: usize = std::usize::MAX << <T2::Size as Unsigned>::to_usize();

    // apply the masks with an AND to zero the bits
    data & mask1 & mask2
}

/// Read the bits of a tag a a certain position.
pub fn read_tag<T: Tag>(data: usize, position: TagPosition) -> GenericArray<bool, T::Size> {
    let to_skip = position.to_skip::<T>();
    let mut array = GenericArray::default();

    array
        .iter_mut()
        .enumerate()
        .skip(to_skip)
        .for_each(|(index, bit)| *bit = ((data >> index) & 1) == 1);

    array
}

/// Set the bits of a tag at a certain position.
pub fn set_tag<T: Tag>(
    mut data: usize,
    bits: GenericArray<bool, T::Size>,
    position: TagPosition,
) -> usize {
    let to_skip = position.to_skip::<T>();

    bits.iter()
        .enumerate()
        .skip(to_skip)
        .for_each(|(index, bit)| {
            let value = if *bit { 1 } else { 0 };
            data = (data & !(1 << index)) | (value << index);
        });

    data
}

/// The `Tag` trait represents any struct that can be serialized
/// and packed into the unused bits of a pointer producing
/// a so called "tagged" pointer.
/// The amount of bits available are variable and the amount
/// you can use depends on whether the tag is in in the low or high position.
///
/// In low position you can use as many bits as must be zero due to
/// alignment. If you don't know the alignment of your pointer you can assume it is
/// that of the value it is pointing to. The amount of available bits in the low
/// position is the binary logarithm of the alignment in bytes.
///
/// In high position the number of available bits is determined by your compilation target.
/// On 32 bit architectures this number shall be assumed to be equal to 0.
/// On x86_64 with 4 level paging the number of available bits is 16 and with level
/// 5 paging it is 8 bits. On 64 bit ARM without pointer authentication you also have 16
/// available bits. With pointer authentication you can only reasonably assume you have 0 available
/// bits unless you know otherwise for your compiler. On all other architectures assume you have
/// 0 available bits unless you know otherwise.
pub trait Tag: Copy {
    /// The size in bits of the tag.
    type Size: ArrayLength<bool>;

    /// Deserialize an array of bits into the tag.
    fn deserialize(bits: GenericArray<bool, Self::Size>) -> Self;

    /// Serialize the tag to an array of bits.
    fn serialize(self) -> GenericArray<bool, Self::Size>;
}

/// This tag is a placeholder type that has a size of 0 and stores no state.
/// If you don't have any tag with information you want to store, this is the default.
#[derive(Debug, Clone, Copy)]
pub struct NullTag;

impl Tag for NullTag {
    type Size = UTerm;

    fn deserialize(_bits: GenericArray<bool, Self::Size>) -> Self {
        Self
    }

    fn serialize(self) -> GenericArray<bool, Self::Size> {
        GenericArray::default()
    }
}