proctor_libc/string/
mod.rs1use 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(|¤t| current == byte).unwrap(),
23 );
24 }
25 }
26
27 let remainder_start = buf.len() - chunks.remainder().len();
28 chunks
29 .remainder()
30 .iter()
31 .position(|¤t| 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, ¤t) 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, ¤t) 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, ¤t) 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, ¤t) 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
169pub fn memchr(buf: &[u8], c: i32) -> Option<&[u8]> {
171 find_memory_byte(buf, c as u8).map(|index| &buf[index..])
172}
173
174pub 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
179pub 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
221pub fn strcmp(s1: &[i8], s2: &[i8]) -> i32 {
223 compare(s1, s2, usize::MAX)
224}
225
226pub fn strncmp(s1: &[i8], s2: &[i8], n: usize) -> i32 {
228 compare(s1, s2, n)
229}
230
231pub 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
238pub 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
246pub 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
254pub 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
264pub fn strlen(s: &[i8]) -> usize {
266 find_null(s, s.len()).unwrap()
267}
268
269pub fn strdup(s: &[i8]) -> Box<[i8]> {
271 let length = strlen(s);
272 s[..=length].into()
273}
274
275pub 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
284pub fn strchr(s: &[i8], c: i32) -> Option<&[i8]> {
286 find_byte(s, c as i8).map(|index| &s[index..])
287}
288
289pub 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
294pub fn strrchr(s: &[i8], c: i32) -> Option<&[i8]> {
296 rfind_byte(s, c as i8).map(|index| &s[index..])
297}
298
299pub 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
326pub fn strspn(s1: &[i8], s2: &[i8]) -> usize {
328 string_span(s1, s2, true)
329}
330
331pub 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
362pub fn strstr<'s>(s1: &'s [i8], s2: &[i8]) -> Option<&'s [i8]> {
364 find_substring(s1, s2).map(|index| &s1[index..])
365}
366
367pub 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;