Faster IndexOf for substrings (#63285)

* Improve "lastChar == firstChar" case, also, use IndexOf directly if value.Length == 1

* Try plain IndexOf first, to optimize cases where even first char of value is never met

* add 1-byte implementation

* copyrights

* fix copy-paste mistake

* Initial LastIndexOf impl

* More efficient LastIndexOf

* fix bug in Char version (we need two clear two lowest bits in the mask) & temporarily remove AdvSimd impl

* use ResetLowestSetBit

* Fix bug

* Add two-byte LastIndexOf

* Fix build

* Minor optimizations

* optimize cases with two-byte/two-char values

* Remove gotos, fix build

* fix bug in LastIndexOf

* Make sure String.LastIndexOf is optimized

* Use xplat simd helpers - implicit ARM support

* fix arm

* Delete \

* Use Vector128.IsHardwareAccelerated

* Fix build

* Use IsAllZero

* Address feedback

* Address feedback

* micro-optimization, do-while is better here since mask is guaranteed to be non-zero

* Address feedabc

* Use clever trick I borrowed from IndexOfAny for trailing elements

* give up on +1 bump for SequenceCompare

* Clean up

* Clean up

* fix build

* Add debug asserts

* Clean up: give up on the unrolled trick - too little value from code bloat

* Add a test

* Fix build

* Add byte-specific test

* Fix build

* Update IndexOfSequence.byte.cs

1 files changed, 29 insertions, 0 deletions

diff --git a/THIRD-PARTY-NOTICES.TXT b/THIRD-PARTY-NOTICES.TXT
index e38f6ef907d..55329a8b022 100644
--- a/THIRD-PARTY-NOTICES.TXT
+++ b/THIRD-PARTY-NOTICES.TXT
@@ -697,6 +697,35 @@ License for fastmod (https://github.com/lemire/fastmod) and ibm-fpgen (https://g
    See the License for the specific language governing permissions and
    limitations under the License.
 
+License for sse4-strstr (https://github.com/WojciechMula/sse4-strstr)
+--------------------------------------
+
+   Copyright (c) 2008-2016, Wojciech Muła
+   All rights reserved.
+
+   Redistribution and use in source and binary forms, with or without
+   modification, are permitted provided that the following conditions are
+   met:
+
+   1. Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+   2. Redistributions in binary form must reproduce the above copyright
+      notice, this list of conditions and the following disclaimer in the
+      documentation and/or other materials provided with the distribution.
+
+   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+   IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+   TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+   PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+   HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+   TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
 License notice for The C++ REST SDK
 -----------------------------------