context: /*
      Copyright (C) 2014-2019 de4dot@gmail.com
  
      This file is part of dnSpy
  
      dnSpy is free software: you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published by
      the Free Software Foundation, either version 3 of the License, or
      (at your option) any later version.
  
      dnSpy is distributed in the hope that it will be useful,
      but WITHOUT ANY WARRANTY; without even the implied warranty of
      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      GNU General Public License for more details.
  
      You should have received a copy of the GNU General Public License
      along with dnSpy.  If not, see <http://www.gnu.org/licenses/>.
  */
  
  using System;
  using System.Collections;
  using System.Collections.Generic;
  using System.Diagnostics;
  using System.Diagnostics.CodeAnalysis;
  using System.Text;
  using System.Threading;
  using dnSpy.Contracts.Hex;
  using dnSpy.Contracts.Hex.Operations;
  
  namespace dnSpy.Hex.Operations {
  	abstract class StringHexSearchService : HexSearchServiceImpl {
  		readonly byte[] lowerBytes;
  		readonly byte[] upperBytes;
  		readonly byte[] charLengths;
  		readonly bool valid;
  
  		public override int ByteCount => lowerBytes.Length;
  
  		protected StringHexSearchService(string pattern) {
  			valid = Initialize(pattern, out lowerBytes!, out upperBytes!, out charLengths!);
  			Debug.Assert(valid);
  		}
  
  		protected abstract bool Initialize(string pattern, [NotNullWhen(true)] out byte[]? lowerBytes, [NotNullWhen(true)] out byte[]? upperBytes, [NotNullWhen(true)] out byte[]? charLengths);
  
  		protected bool Initialize(Encoding encoding, string pattern, [NotNullWhen(true)] out byte[]? lowerBytes, [NotNullWhen(true)] out byte[]? upperBytes, [NotNullWhen(true)] out byte[]? charLengths) {
  			lowerBytes = null;
  			upperBytes = null;
  			charLengths = null;
  
  			var lower = pattern.ToLowerInvariant();
  			var upper = pattern.ToUpperInvariant();
  			if (lower.Length != upper.Length)
  				return false;
  			if (!GetCharLengths(encoding, lower, out var lowerCharLengths, out var lowerBytesTmp))
  				return false;
  			if (!GetCharLengths(encoding, upper, out var upperCharLengths, out var upperBytesTmp))
  				return false;
  
  			if (lowerBytesTmp.Length != upperBytesTmp.Length)
  				return false;
  			if (lowerCharLengths.Length != upperCharLengths.Length)
  				return false;
  			for (int i = 0; i < lowerCharLengths.Length; i++) {
  				if (lowerCharLengths[i] != upperCharLengths[i])
  					return false;
  			}
  
  			lowerBytes = lowerBytesTmp;
  			upperBytes = upperBytesTmp;
  			charLengths = lowerCharLengths;
  			return true;
  		}
  
  		bool GetCharLengths(Encoding encoding, string s, [NotNullWhen(true)] out byte[]? charLengths, [NotNullWhen(true)] out byte[]? encodedBytes) {
  			charLengths = null;
  			encodedBytes = null;
  
  			var decoder = encoding.GetDecoder();
  			var encodedBytesTmp = encoding.GetBytes(s);
  			var bytes = new byte[1];
  			var chars = new char[2];
  			var charLengthsTmp = new byte[s.Length];
  			int charLengthsIndex = 0;
  			int charStartByteIndex = 0;
  			for (int encodedBytesIndex = 0; encodedBytesIndex < encodedBytesTmp.Length; encodedBytesIndex++) {
  				bytes[0] = encodedBytesTmp[encodedBytesIndex];
  				var isLastByte = encodedBytesIndex + 1 == encodedBytesTmp.Length;
  				decoder.Convert(bytes, 0, 1, chars, 0, 2, isLastByte, out int bytesUsed, out int charsUsed, out bool completed);
  				if (isLastByte && charsUsed == 0)
  					return false;
  				if (charsUsed > 0) {
  					if (charLengthsIndex >= charLengthsTmp.Length)
  						return false;
  					int bytesPerChar = encodedBytesIndex - charStartByteIndex + 1;
  					if (bytesPerChar > byte.MaxValue)
  						return false;
  					charLengthsTmp[charLengthsIndex++] = (byte)bytesPerChar;
  					charStartByteIndex = encodedBytesIndex + 1;
  				}
  			}
  			if (charLengthsTmp.Length != charLengthsIndex) {
  				var old = charLengthsTmp;
  				charLengthsTmp = new byte[charLengthsIndex];
  				Array.Copy(old, 0, charLengthsTmp, 0, charLengthsTmp.Length);
  			}
  			charLengths = charLengthsTmp;
  			encodedBytes = encodedBytesTmp;
  			return true;
  		}
  
  		public override IEnumerable<HexBufferSpan> FindAll(HexBufferSpan searchRange, HexBufferPoint startingPosition, HexFindOptions options, CancellationToken cancellationToken) {
  			if (searchRange.IsDefault)
  				throw new ArgumentException();
  			if (searchRange.Buffer != startingPosition.Buffer)
  				throw new ArgumentException();
  			if (startingPosition < searchRange.Start || startingPosition > searchRange.End)
  				throw new ArgumentException();
  			if (!valid)
  				return Array.Empty<HexBufferSpan>();
  			if (searchRange.IsEmpty)
  				return Array.Empty<HexBufferSpan>();
  			return new FindAllCoreEnumerable(this, searchRange, startingPosition, options, cancellationToken);
  		}
  
  		// Needed so we can return the byte[] buffer to the cache
  		sealed class FindAllCoreEnumerable : IEnumerable<HexBufferSpan> {
  			readonly StringHexSearchService owner;
  			/*readonly*/ HexBufferSpan searchRange;
  			/*readonly*/ HexBufferPoint startingPosition;
  			readonly HexFindOptions options;
  			/*readonly*/ CancellationToken cancellationToken;
  
  			public FindAllCoreEnumerable(StringHexSearchService owner, HexBufferSpan searchRange, HexBufferPoint startingPosition, HexFindOptions options, CancellationToken cancellationToken) {
  				this.owner = owner;
  				this.searchRange = searchRange;
  				this.startingPosition = startingPosition;
  				this.options = options;
  				this.cancellationToken = cancellationToken;
  			}
  
  			IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
  			public IEnumerator<HexBufferSpan> GetEnumerator() => new Enumerator(this);
  
  			sealed class Enumerator : IEnumerator<HexBufferSpan> {
  				readonly IEnumerator<HexBufferSpan> realEnumerator;
  				SearchState state;
  
  				public Enumerator(FindAllCoreEnumerable ownerEnumerable) {
  					state = new SearchState(ownerEnumerable.searchRange.Buffer, ownerEnumerable.cancellationToken);
  					if ((ownerEnumerable.options & HexFindOptions.SearchReverse) != 0)
  						realEnumerator = ownerEnumerable.owner.FindAllCoreReverse(state, ownerEnumerable.searchRange, ownerEnumerable.startingPosition, ownerEnumerable.options, ownerEnumerable.cancellationToken).GetEnumerator();
  					else
  						realEnumerator = ownerEnumerable.owner.FindAllCore(state, ownerEnumerable.searchRange, ownerEnumerable.startingPosition, ownerEnumerable.options, ownerEnumerable.cancellationToken).GetEnumerator();
  				}
  
  				object IEnumerator.Current => Current;
  				public HexBufferSpan Current => realEnumerator.Current;
  				public bool MoveNext() => realEnumerator.MoveNext();
  				public void Dispose() {
  					state?.Dispose();
  					state = null!;
  					realEnumerator.Dispose();
  				}
  
  				public void Reset() => throw new NotSupportedException();
  			}
  		}
  
  		sealed class SearchState : SearchStateBase {
  			public SearchState(HexBuffer buffer, CancellationToken cancellationToken)
  				: base(buffer, cancellationToken) {
  			}
  
  			public HexPosition? PositionAfter1(int value1a, int value1b, HexPosition end) {
  				if (end < dataPosition)
  					return null;
  				var dataLocal = Data;
  				for (;;) {
  					if (dataIndex >= dataLength)
  						FillNextData();
  					int len = (int)HexPosition.Min(end - (dataPosition + dataIndex), dataLength - dataIndex).ToUInt64();
  					int index1a = Array.IndexOf(dataLocal, (byte)value1a, dataIndex, len);
  					int index1b = Array.IndexOf(dataLocal, (byte)value1b, dataIndex, len);
  					int index = (int)Math.Min((uint)index1a, (uint)index1b);
  					if (index >= 0) {
  						dataIndex = index + 1;
  						return dataPosition + index + 1;
  					}
  					dataIndex = dataLength;
  					var newPos = dataPosition + dataLength;
  					if (newPos >= end)
  						return null;
  				}
  			}
  
  			public HexPosition? PositionAfter2(int value1a, int value1b, int value2a, int value2b, HexPosition end) {
  				if (end < dataPosition)
  					return null;
  				HexPosition newPos;
  				var dataLocal = Data;
  				for (;;) {
  					if (dataIndex >= dataLength)
  						FillNextData();
  					int len = (int)HexPosition.Min(end - (dataPosition + dataIndex), dataLength - dataIndex).ToUInt64();
  					int index1a = Array.IndexOf(dataLocal, (byte)value1a, dataIndex, len);
  					int index1b = Array.IndexOf(dataLocal, (byte)value1b, dataIndex, len);
  					int index = (int)Math.Min((uint)index1a, (uint)index1b);
  					if (index >= 0) {
  						index++;
  						dataIndex = index;
  						if (index >= dataLength) {
  							newPos = dataPosition + dataLength;
  							if (newPos >= end)
  								return null;
  							FillNextData();
  							index = dataIndex;
  						}
  						bool match = dataLocal[index] == value2a || dataLocal[index] == value2b;
  						if (match) {
  							dataIndex = index + 1;
  							return dataPosition + index + 1;
  						}
  					}
  					else {
  						dataIndex = dataLength;
  
gt: 						newPos = dataPosition + dataLength;