Skip to main content

proctor_libc/string/
mod.rs

1//! Safe equivalents of functions declared in C's `string.h` header.
2
3use std::mem;
4
5const WORD_BYTES: usize = mem::size_of::<usize>();
6const LOW_BITS: usize = usize::MAX / 0xff;
7const HIGH_BITS: usize = LOW_BITS * 0x80;
8const BYTE_SET_WORDS: usize = 256 / usize::BITS as usize;
9
10fn has_null_byte(word: usize) -> bool {
11    word.wrapping_sub(LOW_BITS) & !word & HIGH_BITS != 0
12}
13
14fn find_memory_byte(buf: &[u8], byte: u8) -> Option<usize> {
15    let repeated_byte = LOW_BITS * usize::from(byte);
16    let mut chunks = buf.chunks_exact(WORD_BYTES);
17
18    for (index, chunk) in chunks.by_ref().enumerate() {
19        let word = usize::from_ne_bytes(chunk.try_into().unwrap());
20        if has_null_byte(word ^ repeated_byte) {
21            return Some(
22                index * WORD_BYTES + chunk.iter().position(|&current| current == byte).unwrap(),
23            );
24        }
25    }
26
27    let remainder_start = buf.len() - chunks.remainder().len();
28    chunks
29        .remainder()
30        .iter()
31        .position(|&current| current == byte)
32        .map(|index| remainder_start + index)
33}
34
35fn find_byte(s: &[i8], byte: i8) -> Option<usize> {
36    let bytes: &[u8] = bytemuck::cast_slice(s);
37    let byte = byte as u8;
38    let repeated_byte = LOW_BITS * usize::from(byte);
39    let mut chunks = bytes.chunks_exact(WORD_BYTES);
40
41    for (index, chunk) in chunks.by_ref().enumerate() {
42        let word = usize::from_ne_bytes(chunk.try_into().unwrap());
43        if has_null_byte(word) || has_null_byte(word ^ repeated_byte) {
44            for (offset, &current) in chunk.iter().enumerate() {
45                if current == byte {
46                    return Some(index * WORD_BYTES + offset);
47                }
48                if current == 0 {
49                    return None;
50                }
51            }
52        }
53    }
54
55    let remainder_start = bytes.len() - chunks.remainder().len();
56    for (offset, &current) in chunks.remainder().iter().enumerate() {
57        if current == byte {
58            return Some(remainder_start + offset);
59        }
60        if current == 0 {
61            return None;
62        }
63    }
64
65    None
66}
67
68fn rfind_byte(s: &[i8], byte: i8) -> Option<usize> {
69    let bytes: &[u8] = bytemuck::cast_slice(s);
70    let byte = byte as u8;
71    let repeated_byte = LOW_BITS * usize::from(byte);
72    let mut chunks = bytes.chunks_exact(WORD_BYTES);
73    let mut last = None;
74
75    for (index, chunk) in chunks.by_ref().enumerate() {
76        let word = usize::from_ne_bytes(chunk.try_into().unwrap());
77        if has_null_byte(word) || has_null_byte(word ^ repeated_byte) {
78            for (offset, &current) in chunk.iter().enumerate() {
79                if current == byte {
80                    last = Some(index * WORD_BYTES + offset);
81                }
82                if current == 0 {
83                    return last;
84                }
85            }
86        }
87    }
88
89    let remainder_start = bytes.len() - chunks.remainder().len();
90    for (offset, &current) in chunks.remainder().iter().enumerate() {
91        if current == byte {
92            last = Some(remainder_start + offset);
93        }
94        if current == 0 {
95            return last;
96        }
97    }
98
99    last
100}
101
102fn find_null(s: &[i8], n: usize) -> Option<usize> {
103    let bytes: &[u8] = bytemuck::cast_slice(s);
104    let bytes = &bytes[..n.min(bytes.len())];
105    let mut chunks = bytes.chunks_exact(WORD_BYTES);
106
107    for (index, chunk) in chunks.by_ref().enumerate() {
108        let word = usize::from_ne_bytes(chunk.try_into().unwrap());
109        if has_null_byte(word) {
110            return Some(index * WORD_BYTES + chunk.iter().position(|&byte| byte == 0).unwrap());
111        }
112    }
113
114    let remainder_start = bytes.len() - chunks.remainder().len();
115    chunks
116        .remainder()
117        .iter()
118        .position(|&byte| byte == 0)
119        .map(|index| remainder_start + index)
120}
121
122fn compare(s1: &[i8], s2: &[i8], n: usize) -> i32 {
123    let s1: &[u8] = bytemuck::cast_slice(s1);
124    let s2: &[u8] = bytemuck::cast_slice(s2);
125    let word_end = n.min(s1.len()).min(s2.len()) / WORD_BYTES * WORD_BYTES;
126    let mut index = 0;
127
128    while index < word_end {
129        let word1 = usize::from_ne_bytes(s1[index..index + WORD_BYTES].try_into().unwrap());
130        let word2 = usize::from_ne_bytes(s2[index..index + WORD_BYTES].try_into().unwrap());
131
132        if word1 == word2 && !has_null_byte(word1) {
133            index += WORD_BYTES;
134            continue;
135        }
136
137        for offset in 0..WORD_BYTES {
138            let byte1 = s1[index + offset];
139            let byte2 = s2[index + offset];
140
141            if byte1 != byte2 {
142                return i32::from(byte1) - i32::from(byte2);
143            }
144            if byte1 == 0 {
145                return 0;
146            }
147        }
148
149        unreachable!();
150    }
151
152    while index < n {
153        let byte1 = s1[index];
154        let byte2 = s2[index];
155
156        if byte1 != byte2 {
157            return i32::from(byte1) - i32::from(byte2);
158        }
159        if byte1 == 0 {
160            return 0;
161        }
162
163        index += 1;
164    }
165
166    0
167}
168
169/// Finds `c`, converted to `u8`, in `buf` and returns its suffix, or `None` if not found.
170pub fn memchr(buf: &[u8], c: i32) -> Option<&[u8]> {
171    find_memory_byte(buf, c as u8).map(|index| &buf[index..])
172}
173
174/// Finds `c`, converted to `u8`, in `buf` and returns its mutable suffix, or `None` if not found.
175pub fn memchr_mut(buf: &mut [u8], c: i32) -> Option<&mut [u8]> {
176    find_memory_byte(buf, c as u8).map(|index| &mut buf[index..])
177}
178
179/// Compares the first `n` bytes of two memory regions.
180pub fn memcmp(buf1: &[u8], buf2: &[u8], n: usize) -> i32 {
181    let buf1 = &buf1[..n];
182    let buf2 = &buf2[..n];
183    let word_end = n / WORD_BYTES * WORD_BYTES;
184    let mut index = 0;
185
186    while index < word_end {
187        let word1 = usize::from_ne_bytes(buf1[index..index + WORD_BYTES].try_into().unwrap());
188        let word2 = usize::from_ne_bytes(buf2[index..index + WORD_BYTES].try_into().unwrap());
189
190        if word1 == word2 {
191            index += WORD_BYTES;
192            continue;
193        }
194
195        for offset in 0..WORD_BYTES {
196            let byte1 = buf1[index + offset];
197            let byte2 = buf2[index + offset];
198
199            if byte1 != byte2 {
200                return i32::from(byte1) - i32::from(byte2);
201            }
202        }
203
204        unreachable!();
205    }
206
207    while index < n {
208        let byte1 = buf1[index];
209        let byte2 = buf2[index];
210
211        if byte1 != byte2 {
212            return i32::from(byte1) - i32::from(byte2);
213        }
214
215        index += 1;
216    }
217
218    0
219}
220
221/// Compares two null-terminated byte strings.
222pub fn strcmp(s1: &[i8], s2: &[i8]) -> i32 {
223    compare(s1, s2, usize::MAX)
224}
225
226/// Compares at most `n` bytes of two byte strings.
227pub fn strncmp(s1: &[i8], s2: &[i8], n: usize) -> i32 {
228    compare(s1, s2, n)
229}
230
231/// Copies the null-terminated byte string `s2`, including its null byte, into `s1`.
232pub fn strcpy<'s>(s1: &'s mut [i8], s2: &[i8]) -> &'s mut [i8] {
233    let s2_len = strlen(s2);
234    s1[..=s2_len].copy_from_slice(&s2[..=s2_len]);
235    s1
236}
237
238/// Copies at most `n` bytes from `s2` into `s1`, padding with null bytes when needed.
239pub fn strncpy<'s>(s1: &'s mut [i8], s2: &[i8], n: usize) -> &'s mut [i8] {
240    let copied = find_null(s2, n).unwrap_or(n);
241    s1[..copied].copy_from_slice(&s2[..copied]);
242    s1[copied..n].fill(0);
243    s1
244}
245
246/// Appends the null-terminated byte string `s2` to `s1`.
247pub fn strcat<'s>(s1: &'s mut [i8], s2: &[i8]) -> &'s mut [i8] {
248    let s1_len = strlen(s1);
249    let s2_len = strlen(s2);
250    s1[s1_len..s1_len + s2_len + 1].copy_from_slice(&s2[..=s2_len]);
251    s1
252}
253
254/// Appends at most `n` bytes from `s2` to the null-terminated byte string `s1`.
255pub fn strncat<'s>(s1: &'s mut [i8], s2: &[i8], n: usize) -> &'s mut [i8] {
256    let s1_len = strlen(s1);
257    let s2_len = find_null(s2, n).unwrap_or(n);
258
259    s1[s1_len..s1_len + s2_len].copy_from_slice(&s2[..s2_len]);
260    s1[s1_len + s2_len] = 0;
261    s1
262}
263
264/// Returns the number of bytes preceding the first null byte in `s`.
265pub fn strlen(s: &[i8]) -> usize {
266    find_null(s, s.len()).unwrap()
267}
268
269/// Duplicates the null-terminated byte string `s`.
270pub fn strdup(s: &[i8]) -> Box<[i8]> {
271    let length = strlen(s);
272    s[..=length].into()
273}
274
275/// Duplicates at most `n` bytes from `s` and appends a null byte.
276pub fn strndup(s: &[i8], n: usize) -> Box<[i8]> {
277    let length = find_null(s, n).unwrap_or(n);
278    let mut duplicate = Vec::with_capacity(length + 1);
279    duplicate.extend_from_slice(&s[..length]);
280    duplicate.push(0);
281    duplicate.into_boxed_slice()
282}
283
284/// Finds `c`, converted to `i8`, in null-terminated `s` and returns its suffix, or `None` if not found.
285pub fn strchr(s: &[i8], c: i32) -> Option<&[i8]> {
286    find_byte(s, c as i8).map(|index| &s[index..])
287}
288
289/// Finds `c`, converted to `i8`, in null-terminated `s` and returns its mutable suffix, or `None` if not found.
290pub fn strchr_mut(s: &mut [i8], c: i32) -> Option<&mut [i8]> {
291    find_byte(s, c as i8).map(|index| &mut s[index..])
292}
293
294/// Finds the last `c`, converted to `i8`, in null-terminated `s` and returns its suffix, or `None` if not found.
295pub fn strrchr(s: &[i8], c: i32) -> Option<&[i8]> {
296    rfind_byte(s, c as i8).map(|index| &s[index..])
297}
298
299/// Finds the last `c`, converted to `i8`, in null-terminated `s` and returns its mutable suffix, or `None` if not found.
300pub fn strrchr_mut(s: &mut [i8], c: i32) -> Option<&mut [i8]> {
301    rfind_byte(s, c as i8).map(|index| &mut s[index..])
302}
303
304fn string_span(s1: &[i8], s2: &[i8], included: bool) -> usize {
305    let mut byte_set = [0_usize; BYTE_SET_WORDS];
306
307    for &byte in &s2[..strlen(s2)] {
308        let byte = byte as u8 as usize;
309        byte_set[byte / usize::BITS as usize] |= 1 << (byte % usize::BITS as usize);
310    }
311
312    s1.iter()
313        .position(|&byte| {
314            if byte == 0 {
315                return true;
316            }
317
318            let byte = byte as u8 as usize;
319            let is_included =
320                byte_set[byte / usize::BITS as usize] & (1 << (byte % usize::BITS as usize)) != 0;
321            is_included != included
322        })
323        .unwrap()
324}
325
326/// Returns the length of the initial segment of null-terminated `s1` containing only bytes from null-terminated `s2`.
327pub fn strspn(s1: &[i8], s2: &[i8]) -> usize {
328    string_span(s1, s2, true)
329}
330
331/// Returns the length of the initial segment of null-terminated `s1` containing no bytes from null-terminated `s2`.
332pub fn strcspn(s1: &[i8], s2: &[i8]) -> usize {
333    string_span(s1, s2, false)
334}
335
336fn find_substring(s1: &[i8], s2: &[i8]) -> Option<usize> {
337    let s1_len = strlen(s1);
338    let s2_len = strlen(s2);
339
340    if s2_len == 0 {
341        return Some(0);
342    }
343    if s2_len > s1_len {
344        return None;
345    }
346
347    let first = s2[0];
348    let last_start = s1_len - s2_len;
349    let mut start = 0;
350
351    while start <= last_start {
352        start += find_byte(&s1[start..=last_start], first)?;
353        if s1[start..start + s2_len] == s2[..s2_len] {
354            return Some(start);
355        }
356        start += 1;
357    }
358
359    None
360}
361
362/// Finds null-terminated `s2` in null-terminated `s1` and returns its suffix, or `None` if not found.
363pub fn strstr<'s>(s1: &'s [i8], s2: &[i8]) -> Option<&'s [i8]> {
364    find_substring(s1, s2).map(|index| &s1[index..])
365}
366
367/// Finds null-terminated `s2` in null-terminated `s1` and returns its mutable suffix, or `None` if not found.
368pub fn strstr_mut<'s>(s1: &'s mut [i8], s2: &[i8]) -> Option<&'s mut [i8]> {
369    find_substring(s1, s2).map(|index| &mut s1[index..])
370}
371
372#[cfg(test)]
373mod tests;