#ifndef SSEARCH_H
#define SSEARCH_H
#ifdef __cplusplus
extern "C" {
#endif

#include "scommon.h"

/*
 * ssearch.h
 *
 * Real-time string search using the Rabin-Karp algorithm.
 *
 * Features:
 * - Real-time search (O(n) time complexity).
 * - Search in raw data.
 * - Over 1 GB/s sustained speed on 3-way 3GHz OooE CPU (single thread).
 *
 * Copyright (c) 2015-2016, F. Aragon. All rights reserved. Released under
 * the BSD 3-Clause License (see the doc/LICENSE file included).
 *
 * O(n) string search using a rolling hash. Two hashes are used, one more
 * complex ((f(t-1) + 1) * 2 + f(t)), to ensure O(n) time, and othersimple
 * (sum of bytes), so the algorithm can start in the "fast" mode, and switch
 * to the O(n) compliant when collisons for a given period are above an
 * specific threshold.
 *
 * Being n the elements of the string and m the elements of the pattern to
 * be found:
 * - Worst time (proof pending):
 *   m * k1 operations for computing pattern checksum +
 *   n * k2 operations for computing/comparing current checksum
 * - Other observations:
 *   - No input pre-processing required.
 *   - Suitable for real-time: predictable worst time (ss_find_csum_slow())
 *   - Although is O(n), for "good cases" is ~2-10x slower than best O(m*n).
 *     In corner cases, however, this algorithm outperforms all O(n*m)
 *     algorithms.
 *   - Cached and uncached speed is similar on OooE CPUs (more CPU than
 *     RAM limited), i.e. the RAM bus is not saturated (multi-core CPUs).
 *     Over 1 GB/s sustained search speed is achieved on modern 3GHz OooE
 *     single thread.
 *   - The FCSUM_SLOW ensures O(n), FCSUM_FAST is about twice as fast on
 *     worst-case scenarios, but does not ensure O(n). The algorithm starts
 *     with the fast version, and switches to the slow case on the first false
 *     CSUM mismatch.
 *   - Could be easily expanded for finding more than one pattern at once
 *     (like any other Rabin-Karp algorithm implementation).
 *
 * ss_find_csum_fast: O(n), because it switches to ss_find_csum_slow() when
 * collisions get over specific threshold per period.
 * ss_find_csum_slow: O(n) (half the speed of ss_find_csum_fast in good cases,
 * and just a bit faster in worst cases -as the "fast" algorithm switch
 * requires recomputing again the hash of the target pattern-).
 *
 * References:
 *   - Rabin-Karp search algorithm (search using a rolling hash)
 *   - Raphael Javaux's fast_strstr algorithm (simple hash case: sum of bytes)
 *
 * Other functions, implemented as examples:
 * ss_find_bf: O(n*m), the slowest (brute force).
 * ss_find_bmh: O(n*m), good average (Boyer-Moore-Horspool).
 * ss_find_libc: relies on libc strstr(), so don't support raw data.
 *
 * For "good cases", ss_find_csum_fast is 2-10x slower than e.g. strstr()
 * found in glibc ("Two-Way String-Matching" algorithm, O(n*m)). However, for
 * worst-case scenarios, is faster (O(n) < O(n*m)). I.e. ss_find_csum_* is
 * suitable for real-time requirements, while strstr ("Two-Way") it is not.
 * In comparison to e.g. glibc memmem(), which performs similar to
 * ss_find_bf(), the ss_find_csum_fast() is much faster.
 */

/*
 * Togglable options
 *
 * S_ENABLE_FIND_CSUM_FIRST_CHAR_LOCATION_OPTIMIZATION: skips data not
 * matching with first target byte. Disable in case you want to avoid
 * linking memchr().
 *
 * S_ENABLE_FIND_CSUM_INNER_LOOP_UNROLLING: loop unrolling for both the
 * initialization and search phases. Disable for reducing code size.
 *
 * S_ENABLE_FIND_CSUM_FAST_TO_SLOW_ALGORITHM_SWITCH: this enables the
 * check for switching between the fast and the "slow" (O(n) compliant)
 * algorithm. Don't disable this unless you already know beforehand
 * about the data being processing and willing to squeze for performance.
 * Warning: it is a bad idea to disable this without a good reason,
 * as this ensures real-time requirements.
 *
 * S_ENABLE_FIND_OTHER_EXAMPLES: additional implementations (brute force,
 * Boyer-Moore-Horspool, strstr wrapper). Disabling this could save some
 * space on devices with little memory (e.g. microcontrollers).
 *
 * Instruction cache observation: code is tiny, even with unrolling.
 */

#define S_ENABLE_FIND_CSUM_FIRST_CHAR_LOCATION_OPTIMIZATION
#define S_ENABLE_FIND_CSUM_INNER_LOOP_UNROLLING
#define S_ENABLE_FIND_CSUM_FAST_TO_SLOW_ALGORITHM_SWITCH
#define S_ENABLE_OTHER_EXAMPLES

#ifdef S_MINIMAL
#undef S_ENABLE_FIND_CSUM_FIRST_CHAR_LOCATION_OPTIMIZATION
#undef S_ENABLE_FIND_CSUM_INNER_LOOP_UNROLLING
#undef S_ENABLE_OTHER_EXAMPLES
#endif

size_t ss_find_csum_slow(const char *s0, const size_t off, const size_t ss, const char *t, const size_t ts);
size_t ss_find_csum_fast(const char *s0, const size_t off, const size_t ss, const char *t, const size_t ts);

#ifdef S_ENABLE_OTHER_EXAMPLES
size_t ss_find_bf(const char *s0, const size_t off, const size_t ss, const char *t, const size_t ts);
size_t ss_find_bmh(const char *s0, const size_t off, const size_t ss0, const char *t0, const size_t ts);
size_t ss_find_libc(const char *s, const size_t off, const size_t ss, const char *t, const size_t ts);
#endif

#ifdef __cplusplus
}	/* extern "C" { */
#endif
#endif	/* SSEARCH_H */

