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

use core::{ops, str};

/// Finds the position of the needle in the haystack at compiletime.
///
/// Produces a const-eval error if the needle is not a substring of the haystack.
///
/// # Examples
///
/// ```
/// assert_eq!(obfstr::position!("haystack", "st"), 3..5);
///# assert_eq!(obfstr::position!("haystack", "haystack"), 0..8);
///# assert_eq!(obfstr::position!("haystack", "ck"), 6..8);
/// ```
///
/// Use this API when pooling strings in a single obfstr:
///
/// ```
/// const POOL: &str = concat!("Foo", "Bar", "Baz");
///
/// obfstr::obfstr! { let pool = POOL; }
///
/// // Later, read strings from the pool
/// let foo = &pool[obfstr::position!(POOL, "Foo")];
/// let bar = &pool[obfstr::position!(POOL, "Bar")];
/// let baz = &pool[obfstr::position!(POOL, "Baz")];
/// ```
#[macro_export]
macro_rules! position {
	($haystack:expr, $needle:expr) => {{ const POSITION: ::core::ops::Range<usize> = $crate::position($haystack, $needle); POSITION }};
}

/// Finds the position of the needle in the haystack at compiletime.
///
/// Produces a const-eval error if the needle is not a substring of the haystack.
///
/// ```
/// const POSITION: std::ops::Range<usize> = obfstr::position("haystack", "st");
/// assert_eq!(POSITION, 3..5);
/// ```
#[inline(always)]
pub const fn position(haystack: &str, needle: &str) -> ops::Range<usize> {
	let start = search(haystack, needle);
	// Panic if substring not found
	if start < 0 {
		let _ = haystack.as_bytes()[haystack.len()];
	}
	let start = start as usize;
	start..start + needle.len()
}

const fn search(haystack: &str, needle: &str) -> isize {
	// Short-circuit empty needles
	if needle.len() == 0 {
		return 0;
	}

	let haystack = haystack.as_bytes();
	let needle = needle.as_bytes();

	// Avoid overflow checks later
	if needle.len() <= haystack.len() {
		// Special case for needle length of 1
		if needle.len() == 1 {
			let needle = needle[0];
			let mut offset = 0;
			while offset <= haystack.len() {
				if haystack[offset] == needle {
					return offset as isize;
				}
				offset += 1;
			}
		}
		// Full blown quicksearch
		else {
			// assumed:
			// needle.len() >= 2
			// needle.len() <= haystack.len()

			// Initialize the jump table
			let mut jumps = [max(needle.len()); 256];
			let tail = needle.len() - 1;
			let mut i = 0;
			while i < tail {
				jumps[needle[i] as usize] = max(tail - i);
				i += 1;
			}
			// Find the needle
			let sentinel = needle[tail];
			let mut offset = 0;
			while offset < haystack.len() - tail {
				let chr = haystack[offset + tail];
				if chr == sentinel && check(haystack, needle, offset) {
					return offset as isize;
				}
				offset += jumps[chr as usize] as usize;
			}
		}
	}
	return -1;
}


#[inline(always)]
const fn check(haystack: &[u8], needle: &[u8], offset: usize) -> bool {
	let mut i = 0;
	while i < needle.len() {
		if haystack[offset + i] != needle[i] {
			return false;
		}
		i += 1;
	}
	return true;
}
#[inline(always)]
const fn max(a: usize) -> u8 {
	if a > 255 { 255 } else { a as u8 }
}

#[test]
fn test_position() {
	assert_eq!(position("ABCBC", "CBC"), 2..5);
	assert_eq!(position("ABCBC", "ABCBC"), 0..5);
}

#[test]
#[should_panic]
fn test_position_needle_longer_than_haystack() {
	let _ = position("haystack", "needleneedleneedle");
}