diff options
Diffstat (limited to 'contracts/utils/contracts/src/LibBytes.sol')
| -rw-r--r-- | contracts/utils/contracts/src/LibBytes.sol | 567 |
1 files changed, 567 insertions, 0 deletions
diff --git a/contracts/utils/contracts/src/LibBytes.sol b/contracts/utils/contracts/src/LibBytes.sol new file mode 100644 index 000000000..4ee6228d5 --- /dev/null +++ b/contracts/utils/contracts/src/LibBytes.sol @@ -0,0 +1,567 @@ +/* + + Copyright 2018 ZeroEx Intl. + + 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. + +*/ + +pragma solidity ^0.4.24; + + +library LibBytes { + + using LibBytes for bytes; + + /// @dev Gets the memory address for a byte array. + /// @param input Byte array to lookup. + /// @return memoryAddress Memory address of byte array. This + /// points to the header of the byte array which contains + /// the length. + function rawAddress(bytes memory input) + internal + pure + returns (uint256 memoryAddress) + { + assembly { + memoryAddress := input + } + return memoryAddress; + } + + /// @dev Gets the memory address for the contents of a byte array. + /// @param input Byte array to lookup. + /// @return memoryAddress Memory address of the contents of the byte array. + function contentAddress(bytes memory input) + internal + pure + returns (uint256 memoryAddress) + { + assembly { + memoryAddress := add(input, 32) + } + return memoryAddress; + } + + /// @dev Copies `length` bytes from memory location `source` to `dest`. + /// @param dest memory address to copy bytes to. + /// @param source memory address to copy bytes from. + /// @param length number of bytes to copy. + function memCopy( + uint256 dest, + uint256 source, + uint256 length + ) + internal + pure + { + if (length < 32) { + // Handle a partial word by reading destination and masking + // off the bits we are interested in. + // This correctly handles overlap, zero lengths and source == dest + assembly { + let mask := sub(exp(256, sub(32, length)), 1) + let s := and(mload(source), not(mask)) + let d := and(mload(dest), mask) + mstore(dest, or(s, d)) + } + } else { + // Skip the O(length) loop when source == dest. + if (source == dest) { + return; + } + + // For large copies we copy whole words at a time. The final + // word is aligned to the end of the range (instead of after the + // previous) to handle partial words. So a copy will look like this: + // + // #### + // #### + // #### + // #### + // + // We handle overlap in the source and destination range by + // changing the copying direction. This prevents us from + // overwriting parts of source that we still need to copy. + // + // This correctly handles source == dest + // + if (source > dest) { + assembly { + // We subtract 32 from `sEnd` and `dEnd` because it + // is easier to compare with in the loop, and these + // are also the addresses we need for copying the + // last bytes. + length := sub(length, 32) + let sEnd := add(source, length) + let dEnd := add(dest, length) + + // Remember the last 32 bytes of source + // This needs to be done here and not after the loop + // because we may have overwritten the last bytes in + // source already due to overlap. + let last := mload(sEnd) + + // Copy whole words front to back + // Note: the first check is always true, + // this could have been a do-while loop. + // solhint-disable-next-line no-empty-blocks + for {} lt(source, sEnd) {} { + mstore(dest, mload(source)) + source := add(source, 32) + dest := add(dest, 32) + } + + // Write the last 32 bytes + mstore(dEnd, last) + } + } else { + assembly { + // We subtract 32 from `sEnd` and `dEnd` because those + // are the starting points when copying a word at the end. + length := sub(length, 32) + let sEnd := add(source, length) + let dEnd := add(dest, length) + + // Remember the first 32 bytes of source + // This needs to be done here and not after the loop + // because we may have overwritten the first bytes in + // source already due to overlap. + let first := mload(source) + + // Copy whole words back to front + // We use a signed comparisson here to allow dEnd to become + // negative (happens when source and dest < 32). Valid + // addresses in local memory will never be larger than + // 2**255, so they can be safely re-interpreted as signed. + // Note: the first check is always true, + // this could have been a do-while loop. + // solhint-disable-next-line no-empty-blocks + for {} slt(dest, dEnd) {} { + mstore(dEnd, mload(sEnd)) + sEnd := sub(sEnd, 32) + dEnd := sub(dEnd, 32) + } + + // Write the first 32 bytes + mstore(dest, first) + } + } + } + } + + /// @dev Returns a slices from a byte array. + /// @param b The byte array to take a slice from. + /// @param from The starting index for the slice (inclusive). + /// @param to The final index for the slice (exclusive). + /// @return result The slice containing bytes at indices [from, to) + function slice( + bytes memory b, + uint256 from, + uint256 to + ) + internal + pure + returns (bytes memory result) + { + require( + from <= to, + "FROM_LESS_THAN_TO_REQUIRED" + ); + require( + to < b.length, + "TO_LESS_THAN_LENGTH_REQUIRED" + ); + + // Create a new bytes structure and copy contents + result = new bytes(to - from); + memCopy( + result.contentAddress(), + b.contentAddress() + from, + result.length + ); + return result; + } + + /// @dev Returns a slice from a byte array without preserving the input. + /// @param b The byte array to take a slice from. Will be destroyed in the process. + /// @param from The starting index for the slice (inclusive). + /// @param to The final index for the slice (exclusive). + /// @return result The slice containing bytes at indices [from, to) + /// @dev When `from == 0`, the original array will match the slice. In other cases its state will be corrupted. + function sliceDestructive( + bytes memory b, + uint256 from, + uint256 to + ) + internal + pure + returns (bytes memory result) + { + require( + from <= to, + "FROM_LESS_THAN_TO_REQUIRED" + ); + require( + to < b.length, + "TO_LESS_THAN_LENGTH_REQUIRED" + ); + + // Create a new bytes structure around [from, to) in-place. + assembly { + result := add(b, from) + mstore(result, sub(to, from)) + } + return result; + } + + /// @dev Pops the last byte off of a byte array by modifying its length. + /// @param b Byte array that will be modified. + /// @return The byte that was popped off. + function popLastByte(bytes memory b) + internal + pure + returns (bytes1 result) + { + require( + b.length > 0, + "GREATER_THAN_ZERO_LENGTH_REQUIRED" + ); + + // Store last byte. + result = b[b.length - 1]; + + assembly { + // Decrement length of byte array. + let newLen := sub(mload(b), 1) + mstore(b, newLen) + } + return result; + } + + /// @dev Pops the last 20 bytes off of a byte array by modifying its length. + /// @param b Byte array that will be modified. + /// @return The 20 byte address that was popped off. + function popLast20Bytes(bytes memory b) + internal + pure + returns (address result) + { + require( + b.length >= 20, + "GREATER_OR_EQUAL_TO_20_LENGTH_REQUIRED" + ); + + // Store last 20 bytes. + result = readAddress(b, b.length - 20); + + assembly { + // Subtract 20 from byte array length. + let newLen := sub(mload(b), 20) + mstore(b, newLen) + } + return result; + } + + /// @dev Tests equality of two byte arrays. + /// @param lhs First byte array to compare. + /// @param rhs Second byte array to compare. + /// @return True if arrays are the same. False otherwise. + function equals( + bytes memory lhs, + bytes memory rhs + ) + internal + pure + returns (bool equal) + { + // Keccak gas cost is 30 + numWords * 6. This is a cheap way to compare. + // We early exit on unequal lengths, but keccak would also correctly + // handle this. + return lhs.length == rhs.length && keccak256(lhs) == keccak256(rhs); + } + + /// @dev Reads an address from a position in a byte array. + /// @param b Byte array containing an address. + /// @param index Index in byte array of address. + /// @return address from byte array. + function readAddress( + bytes memory b, + uint256 index + ) + internal + pure + returns (address result) + { + require( + b.length >= index + 20, // 20 is length of address + "GREATER_OR_EQUAL_TO_20_LENGTH_REQUIRED" + ); + + // Add offset to index: + // 1. Arrays are prefixed by 32-byte length parameter (add 32 to index) + // 2. Account for size difference between address length and 32-byte storage word (subtract 12 from index) + index += 20; + + // Read address from array memory + assembly { + // 1. Add index to address of bytes array + // 2. Load 32-byte word from memory + // 3. Apply 20-byte mask to obtain address + result := and(mload(add(b, index)), 0xffffffffffffffffffffffffffffffffffffffff) + } + return result; + } + + /// @dev Writes an address into a specific position in a byte array. + /// @param b Byte array to insert address into. + /// @param index Index in byte array of address. + /// @param input Address to put into byte array. + function writeAddress( + bytes memory b, + uint256 index, + address input + ) + internal + pure + { + require( + b.length >= index + 20, // 20 is length of address + "GREATER_OR_EQUAL_TO_20_LENGTH_REQUIRED" + ); + + // Add offset to index: + // 1. Arrays are prefixed by 32-byte length parameter (add 32 to index) + // 2. Account for size difference between address length and 32-byte storage word (subtract 12 from index) + index += 20; + + // Store address into array memory + assembly { + // The address occupies 20 bytes and mstore stores 32 bytes. + // First fetch the 32-byte word where we'll be storing the address, then + // apply a mask so we have only the bytes in the word that the address will not occupy. + // Then combine these bytes with the address and store the 32 bytes back to memory with mstore. + + // 1. Add index to address of bytes array + // 2. Load 32-byte word from memory + // 3. Apply 12-byte mask to obtain extra bytes occupying word of memory where we'll store the address + let neighbors := and( + mload(add(b, index)), + 0xffffffffffffffffffffffff0000000000000000000000000000000000000000 + ) + + // Make sure input address is clean. + // (Solidity does not guarantee this) + input := and(input, 0xffffffffffffffffffffffffffffffffffffffff) + + // Store the neighbors and address into memory + mstore(add(b, index), xor(input, neighbors)) + } + } + + /// @dev Reads a bytes32 value from a position in a byte array. + /// @param b Byte array containing a bytes32 value. + /// @param index Index in byte array of bytes32 value. + /// @return bytes32 value from byte array. + function readBytes32( + bytes memory b, + uint256 index + ) + internal + pure + returns (bytes32 result) + { + require( + b.length >= index + 32, + "GREATER_OR_EQUAL_TO_32_LENGTH_REQUIRED" + ); + + // Arrays are prefixed by a 256 bit length parameter + index += 32; + + // Read the bytes32 from array memory + assembly { + result := mload(add(b, index)) + } + return result; + } + + /// @dev Writes a bytes32 into a specific position in a byte array. + /// @param b Byte array to insert <input> into. + /// @param index Index in byte array of <input>. + /// @param input bytes32 to put into byte array. + function writeBytes32( + bytes memory b, + uint256 index, + bytes32 input + ) + internal + pure + { + require( + b.length >= index + 32, + "GREATER_OR_EQUAL_TO_32_LENGTH_REQUIRED" + ); + + // Arrays are prefixed by a 256 bit length parameter + index += 32; + + // Read the bytes32 from array memory + assembly { + mstore(add(b, index), input) + } + } + + /// @dev Reads a uint256 value from a position in a byte array. + /// @param b Byte array containing a uint256 value. + /// @param index Index in byte array of uint256 value. + /// @return uint256 value from byte array. + function readUint256( + bytes memory b, + uint256 index + ) + internal + pure + returns (uint256 result) + { + result = uint256(readBytes32(b, index)); + return result; + } + + /// @dev Writes a uint256 into a specific position in a byte array. + /// @param b Byte array to insert <input> into. + /// @param index Index in byte array of <input>. + /// @param input uint256 to put into byte array. + function writeUint256( + bytes memory b, + uint256 index, + uint256 input + ) + internal + pure + { + writeBytes32(b, index, bytes32(input)); + } + + /// @dev Reads an unpadded bytes4 value from a position in a byte array. + /// @param b Byte array containing a bytes4 value. + /// @param index Index in byte array of bytes4 value. + /// @return bytes4 value from byte array. + function readBytes4( + bytes memory b, + uint256 index + ) + internal + pure + returns (bytes4 result) + { + require( + b.length >= index + 4, + "GREATER_OR_EQUAL_TO_4_LENGTH_REQUIRED" + ); + + // Arrays are prefixed by a 32 byte length field + index += 32; + + // Read the bytes4 from array memory + assembly { + result := mload(add(b, index)) + // Solidity does not require us to clean the trailing bytes. + // We do it anyway + result := and(result, 0xFFFFFFFF00000000000000000000000000000000000000000000000000000000) + } + return result; + } + + /// @dev Reads nested bytes from a specific position. + /// @dev NOTE: the returned value overlaps with the input value. + /// Both should be treated as immutable. + /// @param b Byte array containing nested bytes. + /// @param index Index of nested bytes. + /// @return result Nested bytes. + function readBytesWithLength( + bytes memory b, + uint256 index + ) + internal + pure + returns (bytes memory result) + { + // Read length of nested bytes + uint256 nestedBytesLength = readUint256(b, index); + index += 32; + + // Assert length of <b> is valid, given + // length of nested bytes + require( + b.length >= index + nestedBytesLength, + "GREATER_OR_EQUAL_TO_NESTED_BYTES_LENGTH_REQUIRED" + ); + + // Return a pointer to the byte array as it exists inside `b` + assembly { + result := add(b, index) + } + return result; + } + + /// @dev Inserts bytes at a specific position in a byte array. + /// @param b Byte array to insert <input> into. + /// @param index Index in byte array of <input>. + /// @param input bytes to insert. + function writeBytesWithLength( + bytes memory b, + uint256 index, + bytes memory input + ) + internal + pure + { + // Assert length of <b> is valid, given + // length of input + require( + b.length >= index + 32 + input.length, // 32 bytes to store length + "GREATER_OR_EQUAL_TO_NESTED_BYTES_LENGTH_REQUIRED" + ); + + // Copy <input> into <b> + memCopy( + b.contentAddress() + index, + input.rawAddress(), // includes length of <input> + input.length + 32 // +32 bytes to store <input> length + ); + } + + /// @dev Performs a deep copy of a byte array onto another byte array of greater than or equal length. + /// @param dest Byte array that will be overwritten with source bytes. + /// @param source Byte array to copy onto dest bytes. + function deepCopyBytes( + bytes memory dest, + bytes memory source + ) + internal + pure + { + uint256 sourceLen = source.length; + // Dest length must be >= source length, or some bytes would not be copied. + require( + dest.length >= sourceLen, + "GREATER_OR_EQUAL_TO_SOURCE_BYTES_LENGTH_REQUIRED" + ); + memCopy( + dest.contentAddress(), + source.contentAddress(), + sourceLen + ); + } +} |