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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
use core::{
    fmt::Debug,
    panic::{RefUnwindSafe, UnwindSafe},
};

use alloc::sync::Arc;

use crate::packed::{ext::Pointer, pattern::Patterns, teddy::generic::Match};

/// A builder for constructing a Teddy matcher.
///
/// The builder primarily permits fine grained configuration of the Teddy
/// matcher. Most options are made only available for testing/benchmarking
/// purposes. In reality, options are automatically determined by the nature
/// and number of patterns given to the builder.
#[derive(Clone, Debug)]
pub(crate) struct Builder {
    /// When none, this is automatically determined. Otherwise, `false` means
    /// slim Teddy is used (8 buckets) and `true` means fat Teddy is used
    /// (16 buckets). Fat Teddy requires AVX2, so if that CPU feature isn't
    /// available and Fat Teddy was requested, no matcher will be built.
    only_fat: Option<bool>,
    /// When none, this is automatically determined. Otherwise, `false` means
    /// that 128-bit vectors will be used (up to SSSE3 instructions) where as
    /// `true` means that 256-bit vectors will be used. As with `fat`, if
    /// 256-bit vectors are requested and they aren't available, then a
    /// searcher will not be built.
    only_256bit: Option<bool>,
    /// When true (the default), the number of patterns will be used as a
    /// heuristic for refusing construction of a Teddy searcher. The point here
    /// is that too many patterns can overwhelm Teddy. But this can be disabled
    /// in cases where the caller knows better.
    heuristic_pattern_limits: bool,
}

impl Default for Builder {
    fn default() -> Builder {
        Builder::new()
    }
}

impl Builder {
    /// Create a new builder for configuring a Teddy matcher.
    pub(crate) fn new() -> Builder {
        Builder {
            only_fat: None,
            only_256bit: None,
            heuristic_pattern_limits: true,
        }
    }

    /// Build a matcher for the set of patterns given. If a matcher could not
    /// be built, then `None` is returned.
    ///
    /// Generally, a matcher isn't built if the necessary CPU features aren't
    /// available, an unsupported target or if the searcher is believed to be
    /// slower than standard techniques (i.e., if there are too many literals).
    pub(crate) fn build(&self, patterns: Arc<Patterns>) -> Option<Searcher> {
        self.build_imp(patterns)
    }

    /// Require the use of Fat (true) or Slim (false) Teddy. Fat Teddy uses
    /// 16 buckets where as Slim Teddy uses 8 buckets. More buckets are useful
    /// for a larger set of literals.
    ///
    /// `None` is the default, which results in an automatic selection based
    /// on the number of literals and available CPU features.
    pub(crate) fn only_fat(&mut self, yes: Option<bool>) -> &mut Builder {
        self.only_fat = yes;
        self
    }

    /// Request the use of 256-bit vectors (true) or 128-bit vectors (false).
    /// Generally, a larger vector size is better since it either permits
    /// matching more patterns or matching more bytes in the haystack at once.
    ///
    /// `None` is the default, which results in an automatic selection based on
    /// the number of literals and available CPU features.
    pub(crate) fn only_256bit(&mut self, yes: Option<bool>) -> &mut Builder {
        self.only_256bit = yes;
        self
    }

    /// Request that heuristic limitations on the number of patterns be
    /// employed. This useful to disable for benchmarking where one wants to
    /// explore how Teddy performs on large number of patterns even if the
    /// heuristics would otherwise refuse construction.
    ///
    /// This is enabled by default.
    pub(crate) fn heuristic_pattern_limits(
        &mut self,
        yes: bool,
    ) -> &mut Builder {
        self.heuristic_pattern_limits = yes;
        self
    }

    fn build_imp(&self, patterns: Arc<Patterns>) -> Option<Searcher> {
        let patlimit = self.heuristic_pattern_limits;
        // There's no particular reason why we limit ourselves to little endian
        // here, but it seems likely that some parts of Teddy as they are
        // currently written (e.g., the uses of `trailing_zeros`) are likely
        // wrong on non-little-endian targets. Such things are likely easy to
        // fix, but at the time of writing (2023/09/18), I actually do not know
        // how to test this code on a big-endian target. So for now, we're
        // conservative and just bail out.
        if !cfg!(target_endian = "little") {
            debug!("skipping Teddy because target isn't little endian");
            return None;
        }
        // Too many patterns will overwhelm Teddy and likely lead to slow
        // downs, typically in the verification step.
        if patlimit && patterns.len() > 64 {
            debug!("skipping Teddy because of too many patterns");
            return None;
        }

        #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
        {
            use self::x86_64::{FatAVX2, SlimAVX2, SlimSSSE3};

            let mask_len = core::cmp::min(4, patterns.minimum_len());
            let beefy = patterns.len() > 32;
            let has_avx2 = self::x86_64::is_available_avx2();
            let has_ssse3 = has_avx2 || self::x86_64::is_available_ssse3();
            let use_avx2 = if self.only_256bit == Some(true) {
                if !has_avx2 {
                    debug!(
                    "skipping Teddy because avx2 was demanded but unavailable"
                );
                    return None;
                }
                true
            } else if self.only_256bit == Some(false) {
                if !has_ssse3 {
                    debug!(
                    "skipping Teddy because ssse3 was demanded but unavailable"
                );
                    return None;
                }
                false
            } else if !has_ssse3 && !has_avx2 {
                debug!(
                    "skipping Teddy because ssse3 and avx2 are unavailable"
                );
                return None;
            } else {
                has_avx2
            };
            let fat = match self.only_fat {
                None => use_avx2 && beefy,
                Some(false) => false,
                Some(true) if !use_avx2 => {
                    debug!(
                        "skipping Teddy because fat was demanded, but fat \
                         Teddy requires avx2 which is unavailable"
                    );
                    return None;
                }
                Some(true) => true,
            };
            // Just like for aarch64, it's possible that too many patterns will
            // overhwelm Teddy. Unlike aarch64 though, we have Fat teddy which
            // helps things scale a bit more by spreading patterns over more
            // buckets.
            //
            // These thresholds were determined by looking at the measurements
            // for the rust/aho-corasick/packed/leftmost-first and
            // rust/aho-corasick/dfa/leftmost-first engines on the `teddy/`
            // benchmarks.
            if patlimit && mask_len == 1 && patterns.len() > 16 {
                debug!(
                    "skipping Teddy (mask len: 1) because there are \
                             too many patterns",
                );
                return None;
            }
            match (mask_len, use_avx2, fat) {
                (1, false, _) => {
                    debug!("Teddy choice: 128-bit slim, 1 byte");
                    SlimSSSE3::<1>::new(&patterns)
                }
                (1, true, false) => {
                    debug!("Teddy choice: 256-bit slim, 1 byte");
                    SlimAVX2::<1>::new(&patterns)
                }
                (1, true, true) => {
                    debug!("Teddy choice: 256-bit fat, 1 byte");
                    FatAVX2::<1>::new(&patterns)
                }
                (2, false, _) => {
                    debug!("Teddy choice: 128-bit slim, 2 bytes");
                    SlimSSSE3::<2>::new(&patterns)
                }
                (2, true, false) => {
                    debug!("Teddy choice: 256-bit slim, 2 bytes");
                    SlimAVX2::<2>::new(&patterns)
                }
                (2, true, true) => {
                    debug!("Teddy choice: 256-bit fat, 2 bytes");
                    FatAVX2::<2>::new(&patterns)
                }
                (3, false, _) => {
                    debug!("Teddy choice: 128-bit slim, 3 bytes");
                    SlimSSSE3::<3>::new(&patterns)
                }
                (3, true, false) => {
                    debug!("Teddy choice: 256-bit slim, 3 bytes");
                    SlimAVX2::<3>::new(&patterns)
                }
                (3, true, true) => {
                    debug!("Teddy choice: 256-bit fat, 3 bytes");
                    FatAVX2::<3>::new(&patterns)
                }
                (4, false, _) => {
                    debug!("Teddy choice: 128-bit slim, 4 bytes");
                    SlimSSSE3::<4>::new(&patterns)
                }
                (4, true, false) => {
                    debug!("Teddy choice: 256-bit slim, 4 bytes");
                    SlimAVX2::<4>::new(&patterns)
                }
                (4, true, true) => {
                    debug!("Teddy choice: 256-bit fat, 4 bytes");
                    FatAVX2::<4>::new(&patterns)
                }
                _ => {
                    debug!("no supported Teddy configuration found");
                    None
                }
            }
        }
        #[cfg(all(
            target_arch = "aarch64",
            target_feature = "neon",
            target_endian = "little"
        ))]
        {
            use self::aarch64::SlimNeon;

            let mask_len = core::cmp::min(4, patterns.minimum_len());
            if self.only_256bit == Some(true) {
                debug!(
                    "skipping Teddy because 256-bits were demanded \
                     but unavailable"
                );
                return None;
            }
            if self.only_fat == Some(true) {
                debug!(
                    "skipping Teddy because fat was demanded but unavailable"
                );
            }
            // Since we don't have Fat teddy in aarch64 (I think we'd want at
            // least 256-bit vectors for that), we need to be careful not to
            // allow too many patterns as it might overwhelm Teddy. Generally
            // speaking, as the mask length goes up, the more patterns we can
            // handle because the mask length results in fewer candidates
            // generated.
            //
            // These thresholds were determined by looking at the measurements
            // for the rust/aho-corasick/packed/leftmost-first and
            // rust/aho-corasick/dfa/leftmost-first engines on the `teddy/`
            // benchmarks.
            match mask_len {
                1 => {
                    if patlimit && patterns.len() > 16 {
                        debug!(
                            "skipping Teddy (mask len: 1) because there are \
                             too many patterns",
                        );
                    }
                    debug!("Teddy choice: 128-bit slim, 1 byte");
                    SlimNeon::<1>::new(&patterns)
                }
                2 => {
                    if patlimit && patterns.len() > 32 {
                        debug!(
                            "skipping Teddy (mask len: 2) because there are \
                             too many patterns",
                        );
                    }
                    debug!("Teddy choice: 128-bit slim, 2 bytes");
                    SlimNeon::<2>::new(&patterns)
                }
                3 => {
                    if patlimit && patterns.len() > 48 {
                        debug!(
                            "skipping Teddy (mask len: 3) because there are \
                             too many patterns",
                        );
                    }
                    debug!("Teddy choice: 128-bit slim, 3 bytes");
                    SlimNeon::<3>::new(&patterns)
                }
                4 => {
                    debug!("Teddy choice: 128-bit slim, 4 bytes");
                    SlimNeon::<4>::new(&patterns)
                }
                _ => {
                    debug!("no supported Teddy configuration found");
                    None
                }
            }
        }
        #[cfg(not(any(
            all(target_arch = "x86_64", target_feature = "sse2"),
            all(
                target_arch = "aarch64",
                target_feature = "neon",
                target_endian = "little"
            )
        )))]
        {
            None
        }
    }
}

/// A searcher that dispatches to one of several possible Teddy variants.
#[derive(Clone, Debug)]
pub(crate) struct Searcher {
    /// The Teddy variant we use. We use dynamic dispatch under the theory that
    /// it results in better codegen then a enum, although this is a specious
    /// claim.
    ///
    /// This `Searcher` is essentially a wrapper for a `SearcherT` trait
    /// object. We just make `memory_usage` and `minimum_len` available without
    /// going through dynamic dispatch.
    imp: Arc<dyn SearcherT>,
    /// Total heap memory used by the Teddy variant.
    memory_usage: usize,
    /// The minimum haystack length this searcher can handle. It is intended
    /// for callers to use some other search routine (such as Rabin-Karp) in
    /// cases where the haystack (or remainer of the haystack) is too short.
    minimum_len: usize,
}

impl Searcher {
    /// Look for the leftmost occurrence of any pattern in this search in the
    /// given haystack starting at the given position.
    ///
    /// # Panics
    ///
    /// This panics when `haystack[at..].len()` is less than the minimum length
    /// for this haystack.
    #[inline(always)]
    pub(crate) fn find(
        &self,
        haystack: &[u8],
        at: usize,
    ) -> Option<crate::Match> {
        // SAFETY: The Teddy implementations all require a minimum haystack
        // length, and this is required for safety. Therefore, we assert it
        // here in order to make this method sound.
        assert!(haystack[at..].len() >= self.minimum_len);
        let hayptr = haystack.as_ptr();
        // SAFETY: Construction of the searcher guarantees that we are able
        // to run it in the current environment (i.e., we won't get an AVX2
        // searcher on a x86-64 CPU without AVX2 support). Also, the pointers
        // are valid as they are derived directly from a borrowed slice.
        let teddym = unsafe {
            self.imp.find(hayptr.add(at), hayptr.add(haystack.len()))?
        };
        let start = teddym.start().as_usize().wrapping_sub(hayptr.as_usize());
        let end = teddym.end().as_usize().wrapping_sub(hayptr.as_usize());
        let span = crate::Span { start, end };
        // OK because we won't permit the construction of a searcher that
        // could report a pattern ID bigger than what can fit in the crate-wide
        // PatternID type.
        let pid = crate::PatternID::new_unchecked(teddym.pattern().as_usize());
        let m = crate::Match::new(pid, span);
        Some(m)
    }

    /// Returns the approximate total amount of heap used by this type, in
    /// units of bytes.
    #[inline(always)]
    pub(crate) fn memory_usage(&self) -> usize {
        self.memory_usage
    }

    /// Returns the minimum length, in bytes, that a haystack must be in order
    /// to use it with this searcher.
    #[inline(always)]
    pub(crate) fn minimum_len(&self) -> usize {
        self.minimum_len
    }
}

/// A trait that provides dynamic dispatch over the different possible Teddy
/// variants on the same algorithm.
///
/// On `x86_64` for example, it isn't known until runtime which of 12 possible
/// variants will be used. One might use one of the four slim 128-bit vector
/// variants, or one of the four 256-bit vector variants or even one of the
/// four fat 256-bit vector variants.
///
/// Since this choice is generally made when the Teddy searcher is constructed
/// and this choice is based on the patterns given and what the current CPU
/// supports, it follows that there must be some kind of indirection at search
/// time that "selects" the variant chosen at build time.
///
/// There are a few different ways to go about this. One approach is to use an
/// enum. It works fine, but in my experiments, this generally results in worse
/// codegen. Another approach, which is what we use here, is dynamic dispatch
/// via a trait object. We basically implement this trait for each possible
/// variant, select the variant we want at build time and convert it to a
/// trait object for use at search time.
///
/// Another approach is to use function pointers and stick each of the possible
/// variants into a union. This is essentially isomorphic to the dynamic
/// dispatch approach, but doesn't require any allocations. Since this crate
/// requires `alloc`, there's no real reason (AFAIK) to go down this path. (The
/// `memchr` crate does this.)
trait SearcherT:
    Debug + Send + Sync + UnwindSafe + RefUnwindSafe + 'static
{
    /// Execute a search on the given haystack (identified by `start` and `end`
    /// raw pointers).
    ///
    /// # Safety
    ///
    /// Essentially, the `start` and `end` pointers must be valid and point
    /// to a haystack one can read. As long as you derive them from, for
    /// example, a `&[u8]`, they should automatically satisfy all of the safety
    /// obligations:
    ///
    /// * Both `start` and `end` must be valid for reads.
    /// * Both `start` and `end` must point to an initialized value.
    /// * Both `start` and `end` must point to the same allocated object and
    /// must either be in bounds or at most one byte past the end of the
    /// allocated object.
    /// * Both `start` and `end` must be _derived from_ a pointer to the same
    /// object.
    /// * The distance between `start` and `end` must not overflow `isize`.
    /// * The distance being in bounds must not rely on "wrapping around" the
    /// address space.
    /// * It must be the case that `start <= end`.
    /// * `end - start` must be greater than the minimum length for this
    /// searcher.
    ///
    /// Also, it is expected that implementations of this trait will tag this
    /// method with a `target_feature` attribute. Callers must ensure that
    /// they are executing this method in an environment where that attribute
    /// is valid.
    unsafe fn find(&self, start: *const u8, end: *const u8) -> Option<Match>;
}

#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
mod x86_64 {
    use core::arch::x86_64::{__m128i, __m256i};

    use alloc::sync::Arc;

    use crate::packed::{
        ext::Pointer,
        pattern::Patterns,
        teddy::generic::{self, Match},
    };

    use super::{Searcher, SearcherT};

    #[derive(Clone, Debug)]
    pub(super) struct SlimSSSE3<const BYTES: usize> {
        slim128: generic::Slim<__m128i, BYTES>,
    }

    // Defines SlimSSSE3 wrapper functions for 1, 2, 3 and 4 bytes.
    macro_rules! slim_ssse3 {
        ($len:expr) => {
            impl SlimSSSE3<$len> {
                /// Creates a new searcher using "slim" Teddy with 128-bit
                /// vectors. If SSSE3 is not available in the current
                /// environment, then this returns `None`.
                pub(super) fn new(
                    patterns: &Arc<Patterns>,
                ) -> Option<Searcher> {
                    if !is_available_ssse3() {
                        return None;
                    }
                    Some(unsafe { SlimSSSE3::<$len>::new_unchecked(patterns) })
                }

                /// Creates a new searcher using "slim" Teddy with 256-bit
                /// vectors without checking whether SSSE3 is available or not.
                ///
                /// # Safety
                ///
                /// Callers must ensure that SSSE3 is available in the current
                /// environment.
                #[target_feature(enable = "ssse3")]
                unsafe fn new_unchecked(patterns: &Arc<Patterns>) -> Searcher {
                    let slim128 = generic::Slim::<__m128i, $len>::new(
                        Arc::clone(patterns),
                    );
                    let memory_usage = slim128.memory_usage();
                    let minimum_len = slim128.minimum_len();
                    let imp = Arc::new(SlimSSSE3 { slim128 });
                    Searcher { imp, memory_usage, minimum_len }
                }
            }

            impl SearcherT for SlimSSSE3<$len> {
                #[target_feature(enable = "ssse3")]
                #[inline]
                unsafe fn find(
                    &self,
                    start: *const u8,
                    end: *const u8,
                ) -> Option<Match> {
                    // SAFETY: All obligations except for `target_feature` are
                    // passed to the caller. Our use of `target_feature` is
                    // safe because construction of this type requires that the
                    // requisite target features are available.
                    self.slim128.find(start, end)
                }
            }
        };
    }

    slim_ssse3!(1);
    slim_ssse3!(2);
    slim_ssse3!(3);
    slim_ssse3!(4);

    #[derive(Clone, Debug)]
    pub(super) struct SlimAVX2<const BYTES: usize> {
        slim128: generic::Slim<__m128i, BYTES>,
        slim256: generic::Slim<__m256i, BYTES>,
    }

    // Defines SlimAVX2 wrapper functions for 1, 2, 3 and 4 bytes.
    macro_rules! slim_avx2 {
        ($len:expr) => {
            impl SlimAVX2<$len> {
                /// Creates a new searcher using "slim" Teddy with 256-bit
                /// vectors. If AVX2 is not available in the current
                /// environment, then this returns `None`.
                pub(super) fn new(
                    patterns: &Arc<Patterns>,
                ) -> Option<Searcher> {
                    if !is_available_avx2() {
                        return None;
                    }
                    Some(unsafe { SlimAVX2::<$len>::new_unchecked(patterns) })
                }

                /// Creates a new searcher using "slim" Teddy with 256-bit
                /// vectors without checking whether AVX2 is available or not.
                ///
                /// # Safety
                ///
                /// Callers must ensure that AVX2 is available in the current
                /// environment.
                #[target_feature(enable = "avx2")]
                unsafe fn new_unchecked(patterns: &Arc<Patterns>) -> Searcher {
                    let slim128 = generic::Slim::<__m128i, $len>::new(
                        Arc::clone(&patterns),
                    );
                    let slim256 = generic::Slim::<__m256i, $len>::new(
                        Arc::clone(&patterns),
                    );
                    let memory_usage =
                        slim128.memory_usage() + slim256.memory_usage();
                    let minimum_len = slim128.minimum_len();
                    let imp = Arc::new(SlimAVX2 { slim128, slim256 });
                    Searcher { imp, memory_usage, minimum_len }
                }
            }

            impl SearcherT for SlimAVX2<$len> {
                #[target_feature(enable = "avx2")]
                #[inline]
                unsafe fn find(
                    &self,
                    start: *const u8,
                    end: *const u8,
                ) -> Option<Match> {
                    // SAFETY: All obligations except for `target_feature` are
                    // passed to the caller. Our use of `target_feature` is
                    // safe because construction of this type requires that the
                    // requisite target features are available.
                    let len = end.distance(start);
                    if len < self.slim256.minimum_len() {
                        self.slim128.find(start, end)
                    } else {
                        self.slim256.find(start, end)
                    }
                }
            }
        };
    }

    slim_avx2!(1);
    slim_avx2!(2);
    slim_avx2!(3);
    slim_avx2!(4);

    #[derive(Clone, Debug)]
    pub(super) struct FatAVX2<const BYTES: usize> {
        fat256: generic::Fat<__m256i, BYTES>,
    }

    // Defines SlimAVX2 wrapper functions for 1, 2, 3 and 4 bytes.
    macro_rules! fat_avx2 {
        ($len:expr) => {
            impl FatAVX2<$len> {
                /// Creates a new searcher using "slim" Teddy with 256-bit
                /// vectors. If AVX2 is not available in the current
                /// environment, then this returns `None`.
                pub(super) fn new(
                    patterns: &Arc<Patterns>,
                ) -> Option<Searcher> {
                    if !is_available_avx2() {
                        return None;
                    }
                    Some(unsafe { FatAVX2::<$len>::new_unchecked(patterns) })
                }

                /// Creates a new searcher using "slim" Teddy with 256-bit
                /// vectors without checking whether AVX2 is available or not.
                ///
                /// # Safety
                ///
                /// Callers must ensure that AVX2 is available in the current
                /// environment.
                #[target_feature(enable = "avx2")]
                unsafe fn new_unchecked(patterns: &Arc<Patterns>) -> Searcher {
                    let fat256 = generic::Fat::<__m256i, $len>::new(
                        Arc::clone(&patterns),
                    );
                    let memory_usage = fat256.memory_usage();
                    let minimum_len = fat256.minimum_len();
                    let imp = Arc::new(FatAVX2 { fat256 });
                    Searcher { imp, memory_usage, minimum_len }
                }
            }

            impl SearcherT for FatAVX2<$len> {
                #[target_feature(enable = "avx2")]
                #[inline]
                unsafe fn find(
                    &self,
                    start: *const u8,
                    end: *const u8,
                ) -> Option<Match> {
                    // SAFETY: All obligations except for `target_feature` are
                    // passed to the caller. Our use of `target_feature` is
                    // safe because construction of this type requires that the
                    // requisite target features are available.
                    self.fat256.find(start, end)
                }
            }
        };
    }

    fat_avx2!(1);
    fat_avx2!(2);
    fat_avx2!(3);
    fat_avx2!(4);

    #[inline]
    pub(super) fn is_available_ssse3() -> bool {
        #[cfg(not(target_feature = "sse2"))]
        {
            false
        }
        #[cfg(target_feature = "sse2")]
        {
            #[cfg(target_feature = "ssse3")]
            {
                true
            }
            #[cfg(not(target_feature = "ssse3"))]
            {
                #[cfg(feature = "std")]
                {
                    std::is_x86_feature_detected!("ssse3")
                }
                #[cfg(not(feature = "std"))]
                {
                    false
                }
            }
        }
    }

    #[inline]
    pub(super) fn is_available_avx2() -> bool {
        #[cfg(not(target_feature = "sse2"))]
        {
            false
        }
        #[cfg(target_feature = "sse2")]
        {
            #[cfg(target_feature = "avx2")]
            {
                true
            }
            #[cfg(not(target_feature = "avx2"))]
            {
                #[cfg(feature = "std")]
                {
                    std::is_x86_feature_detected!("avx2")
                }
                #[cfg(not(feature = "std"))]
                {
                    false
                }
            }
        }
    }
}

#[cfg(all(
    target_arch = "aarch64",
    target_feature = "neon",
    target_endian = "little"
))]
mod aarch64 {
    use core::arch::aarch64::uint8x16_t;

    use alloc::sync::Arc;

    use crate::packed::{
        pattern::Patterns,
        teddy::generic::{self, Match},
    };

    use super::{Searcher, SearcherT};

    #[derive(Clone, Debug)]
    pub(super) struct SlimNeon<const BYTES: usize> {
        slim128: generic::Slim<uint8x16_t, BYTES>,
    }

    // Defines SlimSSSE3 wrapper functions for 1, 2, 3 and 4 bytes.
    macro_rules! slim_neon {
        ($len:expr) => {
            impl SlimNeon<$len> {
                /// Creates a new searcher using "slim" Teddy with 128-bit
                /// vectors. If SSSE3 is not available in the current
                /// environment, then this returns `None`.
                pub(super) fn new(
                    patterns: &Arc<Patterns>,
                ) -> Option<Searcher> {
                    Some(unsafe { SlimNeon::<$len>::new_unchecked(patterns) })
                }

                /// Creates a new searcher using "slim" Teddy with 256-bit
                /// vectors without checking whether SSSE3 is available or not.
                ///
                /// # Safety
                ///
                /// Callers must ensure that SSSE3 is available in the current
                /// environment.
                #[target_feature(enable = "neon")]
                unsafe fn new_unchecked(patterns: &Arc<Patterns>) -> Searcher {
                    let slim128 = generic::Slim::<uint8x16_t, $len>::new(
                        Arc::clone(patterns),
                    );
                    let memory_usage = slim128.memory_usage();
                    let minimum_len = slim128.minimum_len();
                    let imp = Arc::new(SlimNeon { slim128 });
                    Searcher { imp, memory_usage, minimum_len }
                }
            }

            impl SearcherT for SlimNeon<$len> {
                #[target_feature(enable = "neon")]
                #[inline]
                unsafe fn find(
                    &self,
                    start: *const u8,
                    end: *const u8,
                ) -> Option<Match> {
                    // SAFETY: All obligations except for `target_feature` are
                    // passed to the caller. Our use of `target_feature` is
                    // safe because construction of this type requires that the
                    // requisite target features are available.
                    self.slim128.find(start, end)
                }
            }
        };
    }

    slim_neon!(1);
    slim_neon!(2);
    slim_neon!(3);
    slim_neon!(4);
}