sudachi/util/
cow_array.rs

1/*
2 *  Copyright (c) 2021-2024 Works Applications Co., Ltd.
3 *
4 *  Licensed under the Apache License, Version 2.0 (the "License");
5 *  you may not use this file except in compliance with the License.
6 *  You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 *   Unless required by applicable law or agreed to in writing, software
11 *  distributed under the License is distributed on an "AS IS" BASIS,
12 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 *  See the License for the specific language governing permissions and
14 *  limitations under the License.
15 */
16
17use std::array::TryFromSliceError;
18use std::convert::TryInto;
19use std::ops::Deref;
20
21pub trait ReadLE {
22    fn from_le_bytes(bytes: &[u8]) -> Result<Self, TryFromSliceError>
23    where
24        Self: Sized;
25}
26
27impl ReadLE for i16 {
28    fn from_le_bytes(bytes: &[u8]) -> Result<Self, TryFromSliceError> {
29        bytes.try_into().map(Self::from_le_bytes)
30    }
31}
32
33impl ReadLE for u32 {
34    fn from_le_bytes(bytes: &[u8]) -> Result<Self, TryFromSliceError>
35    where
36        Self: Sized,
37    {
38        bytes.try_into().map(Self::from_le_bytes)
39    }
40}
41
42impl ReadLE for u64 {
43    fn from_le_bytes(bytes: &[u8]) -> Result<Self, TryFromSliceError>
44    where
45        Self: Sized,
46    {
47        bytes.try_into().map(Self::from_le_bytes)
48    }
49}
50
51/// Copy-on-write array.
52///
53/// Is used for storing performance critical dictionary parts.
54/// `slice` is always valid, `storage` is used in owned mode.
55/// Unfortunately, `Cow<&[T]>` does not equal to `&[T]` in assembly:
56/// See: https://rust.godbolt.org/z/r4a9efjqh
57///
58/// It implements Deref for `&[T]`, so it can be used as slice.
59pub struct CowArray<'a, T> {
60    slice: &'a [T],
61    storage: Option<Vec<T>>,
62}
63
64impl<T: ReadLE + Clone> CowArray<'static, T> {
65    /// Creates from the owned data
66    pub fn from_owned<D: Into<Vec<T>>>(data: D) -> Self {
67        let data = data.into();
68        let slice1: &[T] = &data;
69        let slice: &'static [T] = unsafe { std::mem::transmute(slice1) };
70        Self {
71            storage: Some(data),
72            slice,
73        }
74    }
75}
76
77impl<'a, T: ReadLE + Clone> CowArray<'a, T> {
78    /// Create the CowArray from bytes, reinterpreting bytes as T.
79    ///
80    /// Original data may or not be aligned.
81    /// In non-aligned case, it makes a copy of the original data.
82    pub fn from_bytes(data: &'a [u8], offset: usize, size: usize) -> Self {
83        let align = std::mem::align_of::<T>();
84
85        let real_size = size * std::mem::size_of::<T>();
86        let real_slice = &data[offset..offset + real_size];
87        let ptr = real_slice.as_ptr() as *const T;
88        if is_aligned(ptr as usize, align) {
89            // SAFETY: ptr is aligned and trait bounds are ensuring so the type is sane
90            let reslice = unsafe { std::slice::from_raw_parts(ptr, size) };
91            Self {
92                slice: reslice,
93                storage: None,
94            }
95        } else {
96            let data = copy_of_bytes::<T>(real_slice);
97            let slice_1: &[T] = data.as_slice();
98            // we need transmute to make correct lifetime
99            // slice will always point to vector contents and it is impossible to have
100            // self-referential types in Rust yet
101            let slice: &'a [T] = unsafe { std::mem::transmute(slice_1) };
102            Self {
103                storage: Some(data),
104                slice,
105            }
106        }
107    }
108
109    /// Updates the value of the array
110    ///
111    /// Copies the data array if needed and updates it in place
112    /// Current implementation is not super for Rust because it
113    /// violates borrowing rules, but
114    /// 1. this object does not expose any references outside
115    /// 2. usage of data still follows the pattern 1-mut xor many-read
116    pub fn set(&mut self, offset: usize, value: T) {
117        if self.storage.is_none() {
118            self.storage = Some(self.slice.to_vec());
119            //refresh slice
120            let slice: &[T] = self.storage.as_ref().unwrap().as_slice();
121            self.slice = unsafe { std::mem::transmute::<&[T], &[T]>(slice) };
122        }
123        if let Some(s) = self.storage.as_mut() {
124            s[offset] = value;
125        }
126    }
127}
128
129impl<'a, T> Deref for CowArray<'a, T> {
130    type Target = [T];
131
132    fn deref(&self) -> &Self::Target {
133        self.slice
134    }
135}
136
137fn is_aligned(offset: usize, alignment: usize) -> bool {
138    debug_assert!(alignment.is_power_of_two());
139    offset % alignment == 0
140}
141
142fn copy_of_bytes<T: ReadLE>(data: &[u8]) -> Vec<T> {
143    let size_t = std::mem::size_of::<T>();
144    assert_eq!(data.len() % size_t, 0);
145    let nelems = data.len() / size_t;
146    let mut result = Vec::with_capacity(nelems);
147    for i in (0..data.len()).step_by(size_t) {
148        let sl = &data[i..i + size_t];
149        result.push(T::from_le_bytes(sl).unwrap());
150    }
151    result
152}
153
154#[cfg(test)]
155mod test {
156    use super::*;
157
158    #[test]
159    fn aligned_1() {
160        assert!(is_aligned(0, 1));
161        assert!(is_aligned(1, 1));
162        assert!(is_aligned(2, 1));
163        assert!(is_aligned(3, 1));
164        assert!(is_aligned(4, 1));
165        assert!(is_aligned(5, 1));
166        assert!(is_aligned(6, 1));
167        assert!(is_aligned(7, 1));
168        assert!(is_aligned(8, 1));
169    }
170
171    #[test]
172    fn aligned_2() {
173        assert!(is_aligned(0, 2));
174        assert!(!is_aligned(1, 2));
175        assert!(is_aligned(2, 2));
176        assert!(!is_aligned(3, 2));
177        assert!(is_aligned(4, 2));
178        assert!(!is_aligned(5, 2));
179        assert!(is_aligned(6, 2));
180        assert!(!is_aligned(7, 2));
181        assert!(is_aligned(8, 2));
182    }
183
184    #[test]
185    fn aligned_4() {
186        assert!(is_aligned(0, 4));
187        assert!(!is_aligned(1, 4));
188        assert!(!is_aligned(2, 4));
189        assert!(!is_aligned(3, 4));
190        assert!(is_aligned(4, 4));
191        assert!(!is_aligned(5, 4));
192        assert!(!is_aligned(6, 4));
193        assert!(!is_aligned(7, 4));
194        assert!(is_aligned(8, 4));
195    }
196}
sudachi/util/cow_array.rs

sudachi/util/
cow_array.rs
