Added various contracts for testing.

3 files changed, 914 insertions, 0 deletions

diff --git a/test/compilationTests/stringutils/LICENSE b/test/compilationTests/stringutils/LICENSE
new file mode 100644
index 00000000..769c2409
--- /dev/null
+++ b/test/compilationTests/stringutils/LICENSE
@@ -0,0 +1,201 @@
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
+   APPENDIX: How to apply the Apache License to your work.
+
+      To apply the Apache License to your work, attach the following
+      boilerplate notice, with the fields enclosed by brackets "{}"
+      replaced with your own identifying information. (Don't include
+      the brackets!)  The text should be enclosed in the appropriate
+      comment syntax for the file format. We also recommend that a
+      file or class name and description of purpose be included on the
+      same "printed page" as the copyright notice for easier
+      identification within third-party archives.
+
+   Copyright 2016 Nick Johnson
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
diff --git a/test/compilationTests/stringutils/README.md b/test/compilationTests/stringutils/README.md
new file mode 100644
index 00000000..48f71f31
--- /dev/null
+++ b/test/compilationTests/stringutils/README.md
@@ -0,0 +1,4 @@
+String utilities, originally from
+
+https://github.com/Arachnid/solidity-stringutils
+
diff --git a/test/compilationTests/stringutils/strings.sol b/test/compilationTests/stringutils/strings.sol
new file mode 100644
index 00000000..0a2d68bd
--- /dev/null
+++ b/test/compilationTests/stringutils/strings.sol
@@ -0,0 +1,709 @@
+/*
+ * @title String & slice utility library for Solidity contracts.
+ * @author Nick Johnson <arachnid@notdot.net>
+ *
+ * @dev Functionality in this library is largely implemented using an
+ *      abstraction called a 'slice'. A slice represents a part of a string -
+ *      anything from the entire string to a single character, or even no
+ *      characters at all (a 0-length slice). Since a slice only has to specify
+ *      an offset and a length, copying and manipulating slices is a lot less
+ *      expensive than copying and manipulating the strings they reference.
+ *
+ *      To further reduce gas costs, most functions on slice that need to return
+ *      a slice modify the original one instead of allocating a new one; for
+ *      instance, `s.split(".")` will return the text up to the first '.',
+ *      modifying s to only contain the remainder of the string after the '.'.
+ *      In situations where you do not want to modify the original slice, you
+ *      can make a copy first with `.copy()`, for example:
+ *      `s.copy().split(".")`. Try and avoid using this idiom in loops; since
+ *      Solidity has no memory management, it will result in allocating many
+ *      short-lived slices that are later discarded.
+ *
+ *      Functions that return two slices come in two versions: a non-allocating
+ *      version that takes the second slice as an argument, modifying it in
+ *      place, and an allocating version that allocates and returns the second
+ *      slice; see `nextRune` for example.
+ *
+ *      Functions that have to copy string data will return strings rather than
+ *      slices; these can be cast back to slices for further processing if
+ *      required.
+ *
+ *      For convenience, some functions are provided with non-modifying
+ *      variants that create a new slice and return both; for instance,
+ *      `s.splitNew('.')` leaves s unmodified, and returns two values
+ *      corresponding to the left and right parts of the string.
+ */
+library strings {
+    struct slice {
+        uint _len;
+        uint _ptr;
+    }
+
+    function memcpy(uint dest, uint src, uint len) private {
+        // Copy word-length chunks while possible
+        for(; len >= 32; len -= 32) {
+            assembly {
+                mstore(dest, mload(src))
+            }
+            dest += 32;
+            src += 32;
+        }
+
+        // Copy remaining bytes
+        uint mask = 256 ** (32 - len) - 1;
+        assembly {
+            let srcpart := and(mload(src), not(mask))
+            let destpart := and(mload(dest), mask)
+            mstore(dest, or(destpart, srcpart))
+        }
+    }
+
+    /*
+     * @dev Returns a slice containing the entire string.
+     * @param self The string to make a slice from.
+     * @return A newly allocated slice containing the entire string.
+     */
+    function toSlice(string self) internal returns (slice) {
+        uint ptr;
+        assembly {
+            ptr := add(self, 0x20)
+        }
+        return slice(bytes(self).length, ptr);
+    }
+
+    /*
+     * @dev Returns the length of a null-terminated bytes32 string.
+     * @param self The value to find the length of.
+     * @return The length of the string, from 0 to 32.
+     */
+    function len(bytes32 self) internal returns (uint) {
+        uint ret;
+        if (self == 0)
+            return 0;
+        if (self & 0xffffffffffffffffffffffffffffffff == 0) {
+            ret += 16;
+            self = bytes32(uint(self) / 0x100000000000000000000000000000000);
+        }
+        if (self & 0xffffffffffffffff == 0) {
+            ret += 8;
+            self = bytes32(uint(self) / 0x10000000000000000);
+        }
+        if (self & 0xffffffff == 0) {
+            ret += 4;
+            self = bytes32(uint(self) / 0x100000000);
+        }
+        if (self & 0xffff == 0) {
+            ret += 2;
+            self = bytes32(uint(self) / 0x10000);
+        }
+        if (self & 0xff == 0) {
+            ret += 1;
+        }
+        return 32 - ret;
+    }
+
+    /*
+     * @dev Returns a slice containing the entire bytes32, interpreted as a
+     *      null-termintaed utf-8 string.
+     * @param self The bytes32 value to convert to a slice.
+     * @return A new slice containing the value of the input argument up to the
+     *         first null.
+     */
+    function toSliceB32(bytes32 self) internal returns (slice ret) {
+        // Allocate space for `self` in memory, copy it there, and point ret at it
+        assembly {
+            let ptr := mload(0x40)
+            mstore(0x40, add(ptr, 0x20))
+            mstore(ptr, self)
+            mstore(add(ret, 0x20), ptr)
+        }
+        ret._len = len(self);
+    }
+
+    /*
+     * @dev Returns a new slice containing the same data as the current slice.
+     * @param self The slice to copy.
+     * @return A new slice containing the same data as `self`.
+     */
+    function copy(slice self) internal returns (slice) {
+        return slice(self._len, self._ptr);
+    }
+
+    /*
+     * @dev Copies a slice to a new string.
+     * @param self The slice to copy.
+     * @return A newly allocated string containing the slice's text.
+     */
+    function toString(slice self) internal returns (string) {
+        var ret = new string(self._len);
+        uint retptr;
+        assembly { retptr := add(ret, 32) }
+
+        memcpy(retptr, self._ptr, self._len);
+        return ret;
+    }
+
+    /*
+     * @dev Returns the length in runes of the slice. Note that this operation
+     *      takes time proportional to the length of the slice; avoid using it
+     *      in loops, and call `slice.empty()` if you only need to know whether
+     *      the slice is empty or not.
+     * @param self The slice to operate on.
+     * @return The length of the slice in runes.
+     */
+    function len(slice self) internal returns (uint) {
+        // Starting at ptr-31 means the LSB will be the byte we care about
+        var ptr = self._ptr - 31;
+        var end = ptr + self._len;
+        for (uint len = 0; ptr < end; len++) {
+            uint8 b;
+            assembly { b := and(mload(ptr), 0xFF) }
+            if (b < 0x80) {
+                ptr += 1;
+            } else if(b < 0xE0) {
+                ptr += 2;
+            } else if(b < 0xF0) {
+                ptr += 3;
+            } else if(b < 0xF8) {
+                ptr += 4;
+            } else if(b < 0xFC) {
+                ptr += 5;
+            } else {
+                ptr += 6;
+            }
+        }
+        return len;
+    }
+
+    /*
+     * @dev Returns true if the slice is empty (has a length of 0).
+     * @param self The slice to operate on.
+     * @return True if the slice is empty, False otherwise.
+     */
+    function empty(slice self) internal returns (bool) {
+        return self._len == 0;
+    }
+
+    /*
+     * @dev Returns a positive number if `other` comes lexicographically after
+     *      `self`, a negative number if it comes before, or zero if the
+     *      contents of the two slices are equal. Comparison is done per-rune,
+     *      on unicode codepoints.
+     * @param self The first slice to compare.
+     * @param other The second slice to compare.
+     * @return The result of the comparison.
+     */
+    function compare(slice self, slice other) internal returns (int) {
+        uint shortest = self._len;
+        if (other._len < self._len)
+            shortest = other._len;
+
+        var selfptr = self._ptr;
+        var otherptr = other._ptr;
+        for (uint idx = 0; idx < shortest; idx += 32) {
+            uint a;
+            uint b;
+            assembly {
+                a := mload(selfptr)
+                b := mload(otherptr)
+            }
+            if (a != b) {
+                // Mask out irrelevant bytes and check again
+                uint mask = ~(2 ** (8 * (32 - shortest + idx)) - 1);
+                var diff = (a & mask) - (b & mask);
+                if (diff != 0)
+                    return int(diff);
+            }
+            selfptr += 32;
+            otherptr += 32;
+        }
+        return int(self._len) - int(other._len);
+    }
+
+    /*
+     * @dev Returns true if the two slices contain the same text.
+     * @param self The first slice to compare.
+     * @param self The second slice to compare.
+     * @return True if the slices are equal, false otherwise.
+     */
+    function equals(slice self, slice other) internal returns (bool) {
+        return compare(self, other) == 0;
+    }
+
+    /*
+     * @dev Extracts the first rune in the slice into `rune`, advancing the
+     *      slice to point to the next rune and returning `self`.
+     * @param self The slice to operate on.
+     * @param rune The slice that will contain the first rune.
+     * @return `rune`.
+     */
+    function nextRune(slice self, slice rune) internal returns (slice) {
+        rune._ptr = self._ptr;
+
+        if (self._len == 0) {
+            rune._len = 0;
+            return rune;
+        }
+
+        uint len;
+        uint b;
+        // Load the first byte of the rune into the LSBs of b
+        assembly { b := and(mload(sub(mload(add(self, 32)), 31)), 0xFF) }
+        if (b < 0x80) {
+            len = 1;
+        } else if(b < 0xE0) {
+            len = 2;
+        } else if(b < 0xF0) {
+            len = 3;
+        } else {
+            len = 4;
+        }
+
+        // Check for truncated codepoints
+        if (len > self._len) {
+            rune._len = self._len;
+            self._ptr += self._len;
+            self._len = 0;
+            return rune;
+        }
+
+        self._ptr += len;
+        self._len -= len;
+        rune._len = len;
+        return rune;
+    }
+
+    /*
+     * @dev Returns the first rune in the slice, advancing the slice to point
+     *      to the next rune.
+     * @param self The slice to operate on.
+     * @return A slice containing only the first rune from `self`.
+     */
+    function nextRune(slice self) internal returns (slice ret) {
+        nextRune(self, ret);
+    }
+
+    /*
+     * @dev Returns the number of the first codepoint in the slice.
+     * @param self The slice to operate on.
+     * @return The number of the first codepoint in the slice.
+     */
+    function ord(slice self) internal returns (uint ret) {
+        if (self._len == 0) {
+            return 0;
+        }
+
+        uint word;
+        uint len;
+        uint div = 2 ** 248;
+
+        // Load the rune into the MSBs of b
+        assembly { word:= mload(mload(add(self, 32))) }
+        var b = word / div;
+        if (b < 0x80) {
+            ret = b;
+            len = 1;
+        } else if(b < 0xE0) {
+            ret = b & 0x1F;
+            len = 2;
+        } else if(b < 0xF0) {
+            ret = b & 0x0F;
+            len = 3;
+        } else {
+            ret = b & 0x07;
+            len = 4;
+        }
+
+        // Check for truncated codepoints
+        if (len > self._len) {
+            return 0;
+        }
+
+        for (uint i = 1; i < len; i++) {
+            div = div / 256;
+            b = (word / div) & 0xFF;
+            if (b & 0xC0 != 0x80) {
+                // Invalid UTF-8 sequence
+                return 0;
+            }
+            ret = (ret * 64) | (b & 0x3F);
+        }
+
+        return ret;
+    }
+
+    /*
+     * @dev Returns the keccak-256 hash of the slice.
+     * @param self The slice to hash.
+     * @return The hash of the slice.
+     */
+    function keccak(slice self) internal returns (bytes32 ret) {
+        assembly {
+            ret := sha3(mload(add(self, 32)), mload(self))
+        }
+    }
+
+    /*
+     * @dev Returns true if `self` starts with `needle`.
+     * @param self The slice to operate on.
+     * @param needle The slice to search for.
+     * @return True if the slice starts with the provided text, false otherwise.
+     */
+    function startsWith(slice self, slice needle) internal returns (bool) {
+        if (self._len < needle._len) {
+            return false;
+        }
+
+        if (self._ptr == needle._ptr) {
+            return true;
+        }
+
+        bool equal;
+        assembly {
+            let len := mload(needle)
+            let selfptr := mload(add(self, 0x20))
+            let needleptr := mload(add(needle, 0x20))
+            equal := eq(sha3(selfptr, len), sha3(needleptr, len))
+        }
+        return equal;
+    }
+
+    /*
+     * @dev If `self` starts with `needle`, `needle` is removed from the
+     *      beginning of `self`. Otherwise, `self` is unmodified.
+     * @param self The slice to operate on.
+     * @param needle The slice to search for.
+     * @return `self`
+     */
+    function beyond(slice self, slice needle) internal returns (slice) {
+        if (self._len < needle._len) {
+            return self;
+        }
+
+        bool equal = true;
+        if (self._ptr != needle._ptr) {
+            assembly {
+                let len := mload(needle)
+                let selfptr := mload(add(self, 0x20))
+                let needleptr := mload(add(needle, 0x20))
+                equal := eq(sha3(selfptr, len), sha3(needleptr, len))
+            }
+        }
+
+        if (equal) {
+            self._len -= needle._len;
+            self._ptr += needle._len;
+        }
+
+        return self;
+    }
+
+    /*
+     * @dev Returns true if the slice ends with `needle`.
+     * @param self The slice to operate on.
+     * @param needle The slice to search for.
+     * @return True if the slice starts with the provided text, false otherwise.
+     */
+    function endsWith(slice self, slice needle) internal returns (bool) {
+        if (self._len < needle._len) {
+            return false;
+        }
+
+        var selfptr = self._ptr + self._len - needle._len;
+
+        if (selfptr == needle._ptr) {
+            return true;
+        }
+
+        bool equal;
+        assembly {
+            let len := mload(needle)
+            let needleptr := mload(add(needle, 0x20))
+            equal := eq(sha3(selfptr, len), sha3(needleptr, len))
+        }
+
+        return equal;
+    }
+
+    /*
+     * @dev If `self` ends with `needle`, `needle` is removed from the
+     *      end of `self`. Otherwise, `self` is unmodified.
+     * @param self The slice to operate on.
+     * @param needle The slice to search for.
+     * @return `self`
+     */
+    function until(slice self, slice needle) internal returns (slice) {
+        if (self._len < needle._len) {
+            return self;
+        }
+
+        var selfptr = self._ptr + self._len - needle._len;
+        bool equal = true;
+        if (selfptr != needle._ptr) {
+            assembly {
+                let len := mload(needle)
+                let needleptr := mload(add(needle, 0x20))
+                equal := eq(sha3(selfptr, len), sha3(needleptr, len))
+            }
+        }
+
+        if (equal) {
+            self._len -= needle._len;
+        }
+
+        return self;
+    }
+
+    // Returns the memory address of the first byte of the first occurrence of
+    // `needle` in `self`, or the first byte after `self` if not found.
+    function findPtr(uint selflen, uint selfptr, uint needlelen, uint needleptr) private returns (uint) {
+        uint ptr;
+        uint idx;
+
+        if (needlelen <= selflen) {
+            if (needlelen <= 32) {
+                // Optimized assembly for 68 gas per byte on short strings
+                assembly {
+                    let mask := not(sub(exp(2, mul(8, sub(32, needlelen))), 1))
+                    let needledata := and(mload(needleptr), mask)
+                    let end := add(selfptr, sub(selflen, needlelen))
+                    ptr := selfptr
+                    loop:
+                    jumpi(exit, eq(and(mload(ptr), mask), needledata))
+                    ptr := add(ptr, 1)
+                    jumpi(loop, lt(sub(ptr, 1), end))
+                    ptr := add(selfptr, selflen)
+                    exit:
+                }
+                return ptr;
+            } else {
+                // For long needles, use hashing
+                bytes32 hash;
+                assembly { hash := sha3(needleptr, needlelen) }
+                ptr = selfptr;
+                for (idx = 0; idx <= selflen - needlelen; idx++) {
+                    bytes32 testHash;
+                    assembly { testHash := sha3(ptr, needlelen) }
+                    if (hash == testHash)
+                        return ptr;
+                    ptr += 1;
+                }
+            }
+        }
+        return selfptr + selflen;
+    }
+
+    // Returns the memory address of the first byte after the last occurrence of
+    // `needle` in `self`, or the address of `self` if not found.
+    function rfindPtr(uint selflen, uint selfptr, uint needlelen, uint needleptr) private returns (uint) {
+        uint ptr;
+
+        if (needlelen <= selflen) {
+            if (needlelen <= 32) {
+                // Optimized assembly for 69 gas per byte on short strings
+                assembly {
+                    let mask := not(sub(exp(2, mul(8, sub(32, needlelen))), 1))
+                    let needledata := and(mload(needleptr), mask)
+                    ptr := add(selfptr, sub(selflen, needlelen))
+                    loop:
+                    jumpi(ret, eq(and(mload(ptr), mask), needledata))
+                    ptr := sub(ptr, 1)
+                    jumpi(loop, gt(add(ptr, 1), selfptr))
+                    ptr := selfptr
+                    jump(exit)
+                    ret:
+                    ptr := add(ptr, needlelen)
+                    exit:
+                }
+                return ptr;
+            } else {
+                // For long needles, use hashing
+                bytes32 hash;
+                assembly { hash := sha3(needleptr, needlelen) }
+                ptr = selfptr + (selflen - needlelen);
+                while (ptr >= selfptr) {
+                    bytes32 testHash;
+                    assembly { testHash := sha3(ptr, needlelen) }
+                    if (hash == testHash)
+                        return ptr + needlelen;
+                    ptr -= 1;
+                }
+            }
+        }
+        return selfptr;
+    }
+
+    /*
+     * @dev Modifies `self` to contain everything from the first occurrence of
+     *      `needle` to the end of the slice. `self` is set to the empty slice
+     *      if `needle` is not found.
+     * @param self The slice to search and modify.
+     * @param needle The text to search for.
+     * @return `self`.
+     */
+    function find(slice self, slice needle) internal returns (slice) {
+        uint ptr = findPtr(self._len, self._ptr, needle._len, needle._ptr);
+        self._len -= ptr - self._ptr;
+        self._ptr = ptr;
+        return self;
+    }
+
+    /*
+     * @dev Modifies `self` to contain the part of the string from the start of
+     *      `self` to the end of the first occurrence of `needle`. If `needle`
+     *      is not found, `self` is set to the empty slice.
+     * @param self The slice to search and modify.
+     * @param needle The text to search for.
+     * @return `self`.
+     */
+    function rfind(slice self, slice needle) internal returns (slice) {
+        uint ptr = rfindPtr(self._len, self._ptr, needle._len, needle._ptr);
+        self._len = ptr - self._ptr;
+        return self;
+    }
+
+    /*
+     * @dev Splits the slice, setting `self` to everything after the first
+     *      occurrence of `needle`, and `token` to everything before it. If
+     *      `needle` does not occur in `self`, `self` is set to the empty slice,
+     *      and `token` is set to the entirety of `self`.
+     * @param self The slice to split.
+     * @param needle The text to search for in `self`.
+     * @param token An output parameter to which the first token is written.
+     * @return `token`.
+     */
+    function split(slice self, slice needle, slice token) internal returns (slice) {
+        uint ptr = findPtr(self._len, self._ptr, needle._len, needle._ptr);
+        token._ptr = self._ptr;
+        token._len = ptr - self._ptr;
+        if (ptr == self._ptr + self._len) {
+            // Not found
+            self._len = 0;
+        } else {
+            self._len -= token._len + needle._len;
+            self._ptr = ptr + needle._len;
+        }
+        return token;
+    }
+
+    /*
+     * @dev Splits the slice, setting `self` to everything after the first
+     *      occurrence of `needle`, and returning everything before it. If
+     *      `needle` does not occur in `self`, `self` is set to the empty slice,
+     *      and the entirety of `self` is returned.
+     * @param self The slice to split.
+     * @param needle The text to search for in `self`.
+     * @return The part of `self` up to the first occurrence of `delim`.
+     */
+    function split(slice self, slice needle) internal returns (slice token) {
+        split(self, needle, token);
+    }
+
+    /*
+     * @dev Splits the slice, setting `self` to everything before the last
+     *      occurrence of `needle`, and `token` to everything after it. If
+     *      `needle` does not occur in `self`, `self` is set to the empty slice,
+     *      and `token` is set to the entirety of `self`.
+     * @param self The slice to split.
+     * @param needle The text to search for in `self`.
+     * @param token An output parameter to which the first token is written.
+     * @return `token`.
+     */
+    function rsplit(slice self, slice needle, slice token) internal returns (slice) {
+        uint ptr = rfindPtr(self._len, self._ptr, needle._len, needle._ptr);
+        token._ptr = ptr;
+        token._len = self._len - (ptr - self._ptr);
+        if (ptr == self._ptr) {
+            // Not found
+            self._len = 0;
+        } else {
+            self._len -= token._len + needle._len;
+        }
+        return token;
+    }
+
+    /*
+     * @dev Splits the slice, setting `self` to everything before the last
+     *      occurrence of `needle`, and returning everything after it. If
+     *      `needle` does not occur in `self`, `self` is set to the empty slice,
+     *      and the entirety of `self` is returned.
+     * @param self The slice to split.
+     * @param needle The text to search for in `self`.
+     * @return The part of `self` after the last occurrence of `delim`.
+     */
+    function rsplit(slice self, slice needle) internal returns (slice token) {
+        rsplit(self, needle, token);
+    }
+
+    /*
+     * @dev Counts the number of nonoverlapping occurrences of `needle` in `self`.
+     * @param self The slice to search.
+     * @param needle The text to search for in `self`.
+     * @return The number of occurrences of `needle` found in `self`.
+     */
+    function count(slice self, slice needle) internal returns (uint count) {
+        uint ptr = findPtr(self._len, self._ptr, needle._len, needle._ptr) + needle._len;
+        while (ptr <= self._ptr + self._len) {
+            count++;
+            ptr = findPtr(self._len - (ptr - self._ptr), ptr, needle._len, needle._ptr) + needle._len;
+        }
+    }
+
+    /*
+     * @dev Returns True if `self` contains `needle`.
+     * @param self The slice to search.
+     * @param needle The text to search for in `self`.
+     * @return True if `needle` is found in `self`, false otherwise.
+     */
+    function contains(slice self, slice needle) internal returns (bool) {
+        return rfindPtr(self._len, self._ptr, needle._len, needle._ptr) != self._ptr;
+    }
+
+    /*
+     * @dev Returns a newly allocated string containing the concatenation of
+     *      `self` and `other`.
+     * @param self The first slice to concatenate.
+     * @param other The second slice to concatenate.
+     * @return The concatenation of the two strings.
+     */
+    function concat(slice self, slice other) internal returns (string) {
+        var ret = new string(self._len + other._len);
+        uint retptr;
+        assembly { retptr := add(ret, 32) }
+        memcpy(retptr, self._ptr, self._len);
+        memcpy(retptr + self._len, other._ptr, other._len);
+        return ret;
+    }
+
+    /*
+     * @dev Joins an array of slices, using `self` as a delimiter, returning a
+     *      newly allocated string.
+     * @param self The delimiter to use.
+     * @param parts A list of slices to join.
+     * @return A newly allocated string containing all the slices in `parts`,
+     *         joined with `self`.
+     */
+    function join(slice self, slice[] parts) internal returns (string) {
+        if (parts.length == 0)
+            return "";
+
+        uint len = self._len * (parts.length - 1);
+        for(uint i = 0; i < parts.length; i++)
+            len += parts[i]._len;
+
+        var ret = new string(len);
+        uint retptr;
+        assembly { retptr := add(ret, 32) }
+
+        for(i = 0; i < parts.length; i++) {
+            memcpy(retptr, parts[i]._ptr, parts[i]._len);
+            retptr += parts[i]._len;
+            if (i < parts.length - 1) {
+                memcpy(retptr, self._ptr, self._len);
+                retptr += self._len;
+            }
+        }
+
+        return ret;
+    }
+}