Submission 4bb43eb7...
/**
* This file is part of the 1st Solidity Gas Golfing Conshift.
*
* This work is licensed under Creative Commons Attribution ShareAlike 3.0.
* https://creativecommons.org/licenses/by-sa/3.0/
*
* Author: Greg Hysen (@hysz)
* Date: June 2018
* Description: indexOf using Boyer-Moore algorithm w bad character heuristic.
*/
pragma solidity 0.4.24;
contract IndexOf {
event E(int);
int256 constant NOT_FOUND = -1;
/**
* @dev Returns the index of the first occurrence of `needle` in `haystack`,
* or -1 if `needle` is not found in `haystack`.
*
* Input strings may be of any length <2^255.
*
* @param haystack The string to search.
* @param needle The string to search for.
* @return The index of `needle` in `haystack`, or -1 if not found.
*/
function indexOf(string haystack, string needle)
public
pure
returns(int)
{
uint256 haystackLength = bytes(haystack).length;
uint256 needleLength = bytes(needle).length;
if(needleLength > haystackLength) return -1;
if(needleLength == 0) return 0;
if(needleLength == 1) {
uint needleChar = uint(bytes(needle)[0]);
uint max = haystackLength/5 * 5;
uint idx;
while(idx != max) {
if(needleChar == uint(bytes(haystack)[idx++])) return int256(--idx);
if(needleChar == uint(bytes(haystack)[idx++])) return int256(--idx);
if(needleChar == uint(bytes(haystack)[idx++])) return int256(--idx);
if(needleChar == uint(bytes(haystack)[idx++])) return int256(--idx);
if(needleChar == uint(bytes(haystack)[idx++])) return int256(--idx);
}
while(idx != haystackLength) if(needleChar == uint(bytes(haystack)[idx++])) return int256(--idx);
return NOT_FOUND;
}
return indexOf(haystack, needle, haystackLength, needleLength);
}
function indexOf(string haystack, string needle, uint256 haystackLength, uint256 needleLength)
internal
pure
returns(int)
{
// Create badchar table
uint256[256] memory badchar;
uint tmp = needleLength/5 * 5;
uint i;
while(i != tmp) {
badchar[uint(bytes(needle)[uint(i++)])] = uint(i+1);
badchar[uint(bytes(needle)[uint(i++)])] = uint(i+1);
badchar[uint(bytes(needle)[uint(i++)])] = uint(i+1);
badchar[uint(bytes(needle)[uint(i++)])] = uint(i+1);
badchar[uint(bytes(needle)[uint(i++)])] = uint(i+1);
}
while(i != needleLength) badchar[uint(bytes(needle)[uint(i++)])] = uint(i+1);
uint maxNeedleIndex = needleLength-1;
uint256 haystackOffset;
uint maxHaystackOffset = (haystackLength - needleLength);
uint last;
uint shift;
uint256 needleIndex;
while(true) {
needleIndex = maxNeedleIndex;
while(uint(bytes(needle)[uint(needleIndex)]) == (last = uint(bytes(haystack)[uint(haystackOffset + needleIndex)]))) {
if(--needleIndex == uint(-1)) return int256(haystackOffset);
}
// Handling each case individually saves ~10k gas.
if((tmp = badchar[uint(last)]) != 0) {
if((shift = needleIndex - tmp) > 2) {
if((haystackOffset += shift) > maxHaystackOffset) return NOT_FOUND;
} else {
if(++haystackOffset > maxHaystackOffset) return NOT_FOUND;
}
} else {
if(needleIndex != uint(-1)) {
if((haystackOffset += needleIndex + 2) > maxHaystackOffset) return NOT_FOUND;
} else {
if(++haystackOffset > maxHaystackOffset) return NOT_FOUND;
}
}
}
}
}