1use core::hint::black_box;
10
11const LO_U64: u64 = 0x0101_0101_0101_0101;
12const HI_U64: u64 = 0x8080_8080_8080_8080;
13
14#[inline(always)]
15fn has_zero_byte(word: u64) -> u64 {
16 word.wrapping_sub(LO_U64) & !word & HI_U64
17}
18
19#[inline(always)]
20fn first_match_index_le(mask: u64) -> usize {
21 (mask.trailing_zeros() >> 3) as usize
22}
23
24#[inline(always)]
25fn last_match_index_le(mask: u64) -> usize {
26 7 - ((mask.leading_zeros() >> 3) as usize)
27}
28
29#[inline(always)]
30unsafe fn read_u64_unaligned(ptr: *const u8) -> u64 {
31 unsafe { ptr.cast::<u64>().read_unaligned() }
32}
33
34#[inline(always)]
35unsafe fn write_u64_unaligned(ptr: *mut u8, val: u64) {
36 unsafe { ptr.cast::<u64>().write_unaligned(val) }
37}
38
39pub unsafe fn copy_nonoverlapping_bytes(dst: *mut u8, src: *const u8, n: usize) -> *mut u8 {
46 let dst = black_box(dst);
47 let src = black_box(src);
48 let mut i = 0;
49
50 #[cfg(target_arch = "aarch64")]
51 {
52 if n >= 16 {
53 let misalign = (dst as usize) & 15;
54 if misalign != 0 {
55 let prolog = (16 - misalign).min(n);
56 while i < prolog {
57 unsafe {
58 *dst.add(i) = *src.add(i);
59 }
60 i += 1;
61 }
62 }
63
64 while n - i >= 64 {
65 unsafe {
66 let s = src.add(i);
67 let d = dst.add(i);
68 let w0 = read_u64_unaligned(s);
69 let w1 = read_u64_unaligned(s.add(8));
70 let w2 = read_u64_unaligned(s.add(16));
71 let w3 = read_u64_unaligned(s.add(24));
72 let w4 = read_u64_unaligned(s.add(32));
73 let w5 = read_u64_unaligned(s.add(40));
74 let w6 = read_u64_unaligned(s.add(48));
75 let w7 = read_u64_unaligned(s.add(56));
76 write_u64_unaligned(d, w0);
77 write_u64_unaligned(d.add(8), w1);
78 write_u64_unaligned(d.add(16), w2);
79 write_u64_unaligned(d.add(24), w3);
80 write_u64_unaligned(d.add(32), w4);
81 write_u64_unaligned(d.add(40), w5);
82 write_u64_unaligned(d.add(48), w6);
83 write_u64_unaligned(d.add(56), w7);
84 }
85 i += 64;
86 }
87
88 while n - i >= 16 {
89 unsafe {
90 let s = src.add(i);
91 let d = dst.add(i);
92 let w0 = read_u64_unaligned(s);
93 let w1 = read_u64_unaligned(s.add(8));
94 write_u64_unaligned(d, w0);
95 write_u64_unaligned(d.add(8), w1);
96 }
97 i += 16;
98 }
99
100 if n - i >= 8 {
101 unsafe {
102 let w = read_u64_unaligned(src.add(i));
103 write_u64_unaligned(dst.add(i), w);
104 }
105 i += 8;
106 }
107 } else if n >= 8 {
108 unsafe {
109 let first = read_u64_unaligned(src);
110 let last = read_u64_unaligned(src.add(n - 8));
111 write_u64_unaligned(dst, first);
112 write_u64_unaligned(dst.add(n - 8), last);
113 }
114 return dst;
115 }
116 }
117
118 #[cfg(not(target_arch = "aarch64"))]
119 {
120 if n >= 16 {
121 let misalign = (dst as usize) & 7;
122 if misalign != 0 {
123 let prolog = (8 - misalign).min(n);
124 while i < prolog {
125 unsafe {
126 *dst.add(i) = *src.add(i);
127 }
128 i += 1;
129 }
130 }
131
132 while n - i >= 64 {
133 unsafe {
134 let s = src.add(i);
135 let d = dst.add(i);
136 let w0 = read_u64_unaligned(s);
137 let w1 = read_u64_unaligned(s.add(8));
138 let w2 = read_u64_unaligned(s.add(16));
139 let w3 = read_u64_unaligned(s.add(24));
140 let w4 = read_u64_unaligned(s.add(32));
141 let w5 = read_u64_unaligned(s.add(40));
142 let w6 = read_u64_unaligned(s.add(48));
143 let w7 = read_u64_unaligned(s.add(56));
144 write_u64_unaligned(d, w0);
145 write_u64_unaligned(d.add(8), w1);
146 write_u64_unaligned(d.add(16), w2);
147 write_u64_unaligned(d.add(24), w3);
148 write_u64_unaligned(d.add(32), w4);
149 write_u64_unaligned(d.add(40), w5);
150 write_u64_unaligned(d.add(48), w6);
151 write_u64_unaligned(d.add(56), w7);
152 }
153 i += 64;
154 }
155
156 while n - i >= 8 {
157 unsafe {
158 let w = read_u64_unaligned(src.add(i));
159 write_u64_unaligned(dst.add(i), w);
160 }
161 i += 8;
162 }
163 }
164 }
165
166 while i < n {
167 unsafe {
168 *dst.add(i) = *src.add(i);
169 }
170 i += 1;
171 }
172
173 dst
174}
175
176pub unsafe fn copy_bytes(dst: *mut u8, src: *const u8, n: usize) -> *mut u8 {
182 let d_addr = dst as usize;
183 let s_addr = src as usize;
184
185 if d_addr == s_addr || n == 0 {
186 return dst;
187 }
188
189 if d_addr < s_addr || d_addr.wrapping_sub(s_addr) >= n {
190 return unsafe { copy_nonoverlapping_bytes(dst, src, n) };
191 }
192
193 let dst = black_box(dst);
195 let src = black_box(src);
196 let mut i = n;
197
198 if i >= 16 {
199 let end_misalign = (d_addr.wrapping_add(i)) & 15;
200 if end_misalign != 0 {
201 let prolog = end_misalign.min(i);
202 let target = i - prolog;
203 while i > target {
204 i -= 1;
205 unsafe {
206 *dst.add(i) = *src.add(i);
207 }
208 }
209 }
210
211 while i >= 64 {
212 i -= 64;
213 unsafe {
214 let s = src.add(i);
215 let d = dst.add(i);
216 let w0 = read_u64_unaligned(s);
217 let w1 = read_u64_unaligned(s.add(8));
218 let w2 = read_u64_unaligned(s.add(16));
219 let w3 = read_u64_unaligned(s.add(24));
220 let w4 = read_u64_unaligned(s.add(32));
221 let w5 = read_u64_unaligned(s.add(40));
222 let w6 = read_u64_unaligned(s.add(48));
223 let w7 = read_u64_unaligned(s.add(56));
224 write_u64_unaligned(d.add(56), w7);
225 write_u64_unaligned(d.add(48), w6);
226 write_u64_unaligned(d.add(40), w5);
227 write_u64_unaligned(d.add(32), w4);
228 write_u64_unaligned(d.add(24), w3);
229 write_u64_unaligned(d.add(16), w2);
230 write_u64_unaligned(d.add(8), w1);
231 write_u64_unaligned(d, w0);
232 }
233 }
234
235 while i >= 16 {
236 i -= 16;
237 unsafe {
238 let s = src.add(i);
239 let d = dst.add(i);
240 let w0 = read_u64_unaligned(s);
241 let w1 = read_u64_unaligned(s.add(8));
242 write_u64_unaligned(d.add(8), w1);
243 write_u64_unaligned(d, w0);
244 }
245 }
246
247 if i >= 8 {
248 i -= 8;
249 unsafe {
250 let w = read_u64_unaligned(src.add(i));
251 write_u64_unaligned(dst.add(i), w);
252 }
253 }
254 }
255
256 while i > 0 {
257 i -= 1;
258 unsafe {
259 *dst.add(i) = *src.add(i);
260 }
261 }
262
263 dst
264}
265
266pub unsafe fn set_bytes(dst: *mut u8, byte: u8, n: usize) -> *mut u8 {
271 let dst = black_box(dst);
272 let mut i = 0;
273 let splat = LO_U64.wrapping_mul(byte as u64);
274
275 if n >= 16 {
276 let misalign = (dst as usize) & 15;
277 if misalign != 0 {
278 let prolog = (16 - misalign).min(n);
279 while i < prolog {
280 unsafe {
281 *dst.add(i) = byte;
282 }
283 i += 1;
284 }
285 }
286
287 while n - i >= 64 {
288 unsafe {
289 let d = dst.add(i);
290 write_u64_unaligned(d, splat);
291 write_u64_unaligned(d.add(8), splat);
292 write_u64_unaligned(d.add(16), splat);
293 write_u64_unaligned(d.add(24), splat);
294 write_u64_unaligned(d.add(32), splat);
295 write_u64_unaligned(d.add(40), splat);
296 write_u64_unaligned(d.add(48), splat);
297 write_u64_unaligned(d.add(56), splat);
298 }
299 i += 64;
300 }
301
302 while n - i >= 16 {
303 unsafe {
304 let d = dst.add(i);
305 write_u64_unaligned(d, splat);
306 write_u64_unaligned(d.add(8), splat);
307 }
308 i += 16;
309 }
310
311 if n - i >= 8 {
312 unsafe {
313 write_u64_unaligned(dst.add(i), splat);
314 }
315 i += 8;
316 }
317 } else if n >= 8 {
318 unsafe {
319 write_u64_unaligned(dst, splat);
320 write_u64_unaligned(dst.add(n - 8), splat);
321 }
322 return dst;
323 }
324
325 while i < n {
326 unsafe {
327 *dst.add(i) = byte;
328 }
329 i += 1;
330 }
331
332 dst
333}
334
335pub unsafe fn compare_bytes(a: *const u8, b: *const u8, n: usize) -> i32 {
340 let a = black_box(a);
341 let b = black_box(b);
342 let mut i = 0;
343
344 while n - i >= 8 {
345 let wa = unsafe { read_u64_unaligned(a.add(i)) };
346 let wb = unsafe { read_u64_unaligned(b.add(i)) };
347 if wa != wb {
348 let diff = u64::from_be(wa) ^ u64::from_be(wb);
349 let idx = (diff.leading_zeros() >> 3) as usize;
350 let av = unsafe { *a.add(i + idx) };
351 let bv = unsafe { *b.add(i + idx) };
352 return (av as i32) - (bv as i32);
353 }
354 i += 8;
355 }
356
357 while i < n {
358 let av = unsafe { *a.add(i) };
359 let bv = unsafe { *b.add(i) };
360 if av != bv {
361 return (av as i32) - (bv as i32);
362 }
363 i += 1;
364 }
365 0
366}
367
368pub unsafe fn c_strlen(s: *const u8) -> usize {
373 let s = black_box(s);
374 let mut len = 0;
375
376 while ((s as usize).wrapping_add(len) & 7) != 0 {
377 if unsafe { *s.add(len) } == 0 {
378 return len;
379 }
380 len += 1;
381 }
382
383 loop {
384 let word = u64::from_le(unsafe { *s.add(len).cast::<u64>() });
385 let mask = has_zero_byte(word);
386 if mask != 0 {
387 return len + first_match_index_le(mask);
388 }
389 len += 8;
390 }
391}
392
393pub unsafe fn c_strnlen(s: *const u8, max_len: usize) -> usize {
398 let s = black_box(s);
399 let mut len = 0;
400
401 while len < max_len && ((s as usize).wrapping_add(len) & 7) != 0 {
402 if unsafe { *s.add(len) } == 0 {
403 return len;
404 }
405 len += 1;
406 }
407
408 while max_len - len >= 8 {
409 let word = u64::from_le(unsafe { *s.add(len).cast::<u64>() });
410 let mask = has_zero_byte(word);
411 if mask != 0 {
412 return len + first_match_index_le(mask);
413 }
414 len += 8;
415 }
416
417 while len < max_len {
418 if unsafe { *s.add(len) } == 0 {
419 return len;
420 }
421 len += 1;
422 }
423 len
424}
425
426pub fn memchr(needle: u8, haystack: &[u8]) -> Option<usize> {
428 let n = haystack.len();
429 let ptr = black_box(haystack.as_ptr());
430 let mut i = 0;
431 let splat = LO_U64.wrapping_mul(needle as u64);
432
433 while i < n && ((ptr as usize).wrapping_add(i) & 7) != 0 {
434 if haystack[i] == needle {
435 return Some(i);
436 }
437 i += 1;
438 }
439
440 while n - i >= 8 {
441 let word = u64::from_le(unsafe { *ptr.add(i).cast::<u64>() }) ^ splat;
442 let mask = has_zero_byte(word);
443 if mask != 0 {
444 return Some(i + first_match_index_le(mask));
445 }
446 i += 8;
447 }
448
449 while i < n {
450 if haystack[i] == needle {
451 return Some(i);
452 }
453 i += 1;
454 }
455 None
456}
457
458pub fn memrchr(needle: u8, haystack: &[u8]) -> Option<usize> {
460 let ptr = black_box(haystack.as_ptr());
461 let mut i = haystack.len();
462 let splat = LO_U64.wrapping_mul(needle as u64);
463
464 while i > 0 && ((ptr as usize).wrapping_add(i) & 7) != 0 {
465 i -= 1;
466 if haystack[i] == needle {
467 return Some(i);
468 }
469 }
470
471 while i >= 8 {
472 i -= 8;
473 let word = u64::from_le(unsafe { *ptr.add(i).cast::<u64>() }) ^ splat;
474 let mask = has_zero_byte(word);
475 if mask != 0 {
476 return Some(i + last_match_index_le(mask));
477 }
478 }
479
480 while i > 0 {
481 i -= 1;
482 if haystack[i] == needle {
483 return Some(i);
484 }
485 }
486 None
487}
488
489pub fn ct_eq(a: &[u8], b: &[u8]) -> bool {
491 if a.len() != b.len() {
492 return false;
493 }
494 let mut diff: u8 = 0;
495 let mut i = 0;
496 while i < a.len() {
497 diff |= black_box(a[i] ^ b[i]);
498 i += 1;
499 }
500 black_box(diff) == 0
501}
502
503#[cfg(all(feature = "symbols", target_os = "none"))]
509#[unsafe(no_mangle)]
510pub unsafe extern "C" fn memcpy(
511 dst: *mut core::ffi::c_void,
512 src: *const core::ffi::c_void,
513 n: usize,
514) -> *mut core::ffi::c_void {
515 unsafe { copy_nonoverlapping_bytes(dst.cast::<u8>(), src.cast::<u8>(), n).cast() }
516}
517
518#[cfg(all(feature = "symbols", target_os = "none"))]
523#[unsafe(no_mangle)]
524pub unsafe extern "C" fn memmove(
525 dst: *mut core::ffi::c_void,
526 src: *const core::ffi::c_void,
527 n: usize,
528) -> *mut core::ffi::c_void {
529 unsafe { copy_bytes(dst.cast::<u8>(), src.cast::<u8>(), n).cast() }
530}
531
532#[cfg(all(feature = "symbols", target_os = "none"))]
537#[unsafe(no_mangle)]
538pub unsafe extern "C" fn memset(
539 dst: *mut core::ffi::c_void,
540 c: core::ffi::c_int,
541 n: usize,
542) -> *mut core::ffi::c_void {
543 unsafe { set_bytes(dst.cast::<u8>(), c as u8, n).cast() }
544}
545
546#[cfg(all(feature = "symbols", target_os = "none"))]
551#[unsafe(no_mangle)]
552pub unsafe extern "C" fn memcmp(
553 a: *const core::ffi::c_void,
554 b: *const core::ffi::c_void,
555 n: usize,
556) -> core::ffi::c_int {
557 unsafe { compare_bytes(a.cast::<u8>(), b.cast::<u8>(), n) }
558}
559
560#[cfg(all(feature = "symbols", target_os = "none"))]
565#[unsafe(no_mangle)]
566pub unsafe extern "C" fn bcmp(
567 a: *const core::ffi::c_void,
568 b: *const core::ffi::c_void,
569 n: usize,
570) -> core::ffi::c_int {
571 unsafe { compare_bytes(a.cast::<u8>(), b.cast::<u8>(), n) }
572}
573
574#[cfg(all(feature = "symbols", target_os = "none"))]
579#[unsafe(no_mangle)]
580pub unsafe extern "C" fn strlen(s: *const core::ffi::c_char) -> usize {
581 unsafe { c_strlen(s.cast::<u8>()) }
582}
583
584#[cfg(all(feature = "symbols", target_os = "none"))]
589#[unsafe(no_mangle)]
590pub unsafe extern "C" fn strnlen(s: *const core::ffi::c_char, max_len: usize) -> usize {
591 unsafe { c_strnlen(s.cast::<u8>(), max_len) }
592}
593
594#[cfg(test)]
595mod tests {
596 use super::*;
597
598 #[test]
599 fn copy_aligned_and_unaligned() {
600 let mut src = [0u8; 64];
601 for (i, b) in src.iter_mut().enumerate() {
602 *b = (i as u8).wrapping_mul(3).wrapping_add(1);
603 }
604 let mut dst = [0u8; 64];
605
606 unsafe {
607 copy_nonoverlapping_bytes(dst.as_mut_ptr(), src.as_ptr(), 64);
608 }
609 assert_eq!(dst, src);
610
611 let mut unaligned_dst = [0u8; 64];
612 unsafe {
613 copy_nonoverlapping_bytes(unaligned_dst.as_mut_ptr().add(1), src.as_ptr().add(3), 29);
614 }
615 assert_eq!(&unaligned_dst[1..30], &src[3..32]);
616 }
617
618 #[test]
619 fn copy_overlapping_forward_and_backward() {
620 let mut buf = [1u8, 2, 3, 4, 5, 6, 7, 8];
621 unsafe {
622 copy_bytes(buf.as_mut_ptr().add(2), buf.as_ptr(), 5);
623 }
624 assert_eq!(buf, [1, 2, 1, 2, 3, 4, 5, 8]);
625
626 let mut buf2 = [1u8, 2, 3, 4, 5, 6, 7, 8];
627 unsafe {
628 copy_bytes(buf2.as_mut_ptr(), buf2.as_ptr().add(2), 5);
629 }
630 assert_eq!(buf2, [3, 4, 5, 6, 7, 6, 7, 8]);
631 }
632
633 #[test]
634 fn set_and_compare() {
635 let mut buf = [0u8; 31];
636 unsafe {
637 set_bytes(buf.as_mut_ptr(), 0x5a, 31);
638 }
639 assert!(buf.iter().all(|&b| b == 0x5a));
640
641 let other = [0x5au8; 31];
642 assert_eq!(
643 unsafe { compare_bytes(buf.as_ptr(), other.as_ptr(), 31) },
644 0
645 );
646
647 buf[17] = 0x5b;
648 assert!(unsafe { compare_bytes(buf.as_ptr(), other.as_ptr(), 31) } > 0);
649 assert!(unsafe { compare_bytes(other.as_ptr(), buf.as_ptr(), 31) } < 0);
650 }
651
652 #[test]
653 fn c_strings_and_slice_helpers() {
654 let s = b"hello\0world";
655 assert_eq!(unsafe { c_strlen(s.as_ptr()) }, 5);
656 assert_eq!(unsafe { c_strnlen(s.as_ptr(), 3) }, 3);
657 assert_eq!(unsafe { c_strnlen(s.as_ptr(), 16) }, 5);
658
659 assert_eq!(memchr(b'l', b"hello"), Some(2));
660 assert_eq!(memrchr(b'l', b"hello"), Some(3));
661 assert_eq!(memchr(b'z', b"hello"), None);
662
663 assert!(ct_eq(b"secret-key", b"secret-key"));
664 assert!(!ct_eq(b"secret-key", b"secret-kez"));
665 assert!(!ct_eq(b"short", b"longer"));
666 }
667
668 #[test]
669 fn bulk_misaligned_offsets_and_overlaps() {
670 let mut src = [0u8; 320];
671 for (i, b) in src.iter_mut().enumerate() {
672 *b = (i as u8).wrapping_mul(17).wrapping_add(5);
673 }
674
675 for src_off in 0..16 {
676 for dst_off in 0..16 {
677 for &len in &[0usize, 1, 7, 8, 15, 16, 31, 63, 64, 65, 127, 128, 193, 256] {
678 let mut dst = [0xeeu8; 320];
679 unsafe {
680 copy_nonoverlapping_bytes(
681 dst.as_mut_ptr().add(dst_off),
682 src.as_ptr().add(src_off),
683 len,
684 );
685 }
686 assert_eq!(&dst[..dst_off], &[0xeeu8; 16][..dst_off]);
687 assert_eq!(&dst[dst_off..dst_off + len], &src[src_off..src_off + len]);
688 assert_eq!(&dst[dst_off + len..dst_off + len + 8], &[0xeeu8; 8]);
689 }
690 }
691 }
692
693 for shift in 1..16 {
694 for base_off in 0..8 {
695 for &len in &[1usize, 7, 8, 15, 16, 31, 64, 97, 128, 192, 256] {
696 let mut buf = src;
697 unsafe {
698 copy_bytes(
699 buf.as_mut_ptr().add(base_off + shift),
700 buf.as_ptr().add(base_off),
701 len,
702 );
703 }
704 assert_eq!(
705 &buf[base_off + shift..base_off + shift + len],
706 &src[base_off..base_off + len]
707 );
708
709 let mut buf_fwd = src;
710 unsafe {
711 copy_bytes(
712 buf_fwd.as_mut_ptr().add(base_off),
713 buf_fwd.as_ptr().add(base_off + shift),
714 len,
715 );
716 }
717 assert_eq!(
718 &buf_fwd[base_off..base_off + len],
719 &src[base_off + shift..base_off + shift + len]
720 );
721 }
722 }
723 }
724 }
725
726 #[test]
727 fn swar_strlen_memchr_and_word_compare_edges() {
728 let mut buf = [b'x'; 160];
729 for off in 0..16 {
730 for len in 0..96 {
731 buf.fill(b'a');
732 if len >= 2 {
733 buf[off + len / 2] = 0x80;
734 buf[off + len - 1] = 0xff;
735 }
736 buf[off + len] = 0;
737
738 let ptr = unsafe { buf.as_ptr().add(off) };
739 assert_eq!(unsafe { c_strlen(ptr) }, len);
740 assert_eq!(unsafe { c_strnlen(ptr, len + 16) }, len);
741 if len > 0 {
742 assert_eq!(unsafe { c_strnlen(ptr, len - 1) }, len - 1);
743 }
744
745 let slice = &buf[off..off + len];
746 assert_eq!(memchr(0, &buf[off..off + len + 1]), Some(len));
747 assert_eq!(memchr(b'z', slice), None);
748 assert_eq!(memrchr(b'z', slice), None);
749 }
750 }
751
752 let mut hay = [b'.'; 128];
753 for off in 0..8 {
754 for pos in 0..80 {
755 hay.fill(b'.');
756 hay[off + pos] = 0xa5;
757 let s = &hay[off..off + 80];
758 assert_eq!(memchr(0xa5, s), Some(pos));
759 assert_eq!(memrchr(0xa5, s), Some(pos));
760
761 let mut other = [b'.'; 128];
762 other[off + pos] = 0xa4;
763 let a_ptr = unsafe { hay.as_ptr().add(off) };
764 assert!(unsafe { compare_bytes(a_ptr, other.as_ptr().add(off), 80) } > 0);
765 assert!(unsafe { compare_bytes(other.as_ptr().add(off), a_ptr, 80) } < 0);
766 other[off + pos] = 0xa5;
767 assert_eq!(
768 unsafe { compare_bytes(a_ptr, other.as_ptr().add(off), 80) },
769 0
770 );
771 }
772 }
773 }
774}