// SPDX-License-Identifier: MIT

pragma solidity >=0.8.0;

import { Uint256Util } from "./Uint256Util.sol";

library BytesUtil {
  using BytesUtil 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 pointAddress(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 contentPointAddress(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)
  {
    // Ensure that the from and to positions are valid positions for a slice within
    // the byte array that is being used.
    require(from <= to, "FromLessThanOrEqualsToRequired");
    require(to <= b.length, "ToLessThanOrEqualsLengthRequired");

    // Create a new bytes structure and copy contents
    result = new bytes(to - from);
    memCopy(
      result.contentPointAddress(),
      b.contentPointAddress() + from,
      result.length
    );
    return result;
  }

  /// @dev Returns a slice from a byte array without preserving the input.
  ///      When `from == 0`, the original array will match the slice.
  ///      In other cases its state will be corrupted.
  /// @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)
  function sliceDestructive(
    bytes memory b,
    uint256 from,
    uint256 to
  )
  internal
  pure
  returns (bytes memory result)
  {
    // Ensure that the from and to positions are valid positions for a slice within
    // the byte array that is being used.
    require(from <= to, "FromLessThanOrEqualsToRequired");
    require(to <= b.length, "ToLessThanOrEqualsLengthRequired");

    // 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 result The byte that was popped off.
  function popLastByte(bytes memory b)
  internal
  pure
  returns (bytes1 result)
  {
    require(b.length != 0, "LengthGreaterThanZeroRequired");

    // 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 Tests equality of two byte arrays.
  /// @param lhs First byte array to compare.
  /// @param rhs Second byte array to compare.
  /// @return equal 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 result address from byte array.
  function readAddress(
    bytes memory b,
    uint256 index
  )
  internal
  pure
  returns (address result)
  {
    require(b.length >= index + 20, "LengthGreaterThanOrEqualsTwentyRequired");

    // 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, "LengthGreaterThanOrEqualsTwentyRequired");

    // 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 result bytes32 value from byte array.
  function readBytes32(
    bytes memory b,
    uint256 index
  )
  internal
  pure
  returns (bytes32 result)
  {
    require(b.length >= index + 32, "LengthGreaterThanOrEqualsThirtyTwoRequired");

    // 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, "LengthGreaterThanOrEqualsThirtyTwoRequired");

    // 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 result 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 result bytes4 value from byte array.
  function readBytes4(
    bytes memory b,
    uint256 index
  )
  internal
  pure
  returns (bytes4 result)
  {
    require(b.length >= index + 4, "LengthGreaterThanOrEqualsFourRequired");

    // 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 Writes a new length to a byte array.
  ///      Decreasing length will lead to removing the corresponding lower order bytes from the byte array.
  ///      Increasing length may lead to appending adjacent in-memory bytes to the end of the byte array.
  /// @param b Bytes array to write new length to.
  /// @param length New length of byte array.
  function writeLength(bytes memory b, uint256 length)
  internal
  pure
  {
    assembly {
      mstore(b, length)
    }
  }

  function recover(bytes memory _msgBytes, uint8 _v, bytes32 _r, bytes32 _s) internal pure returns (address) {
    bytes memory fullMessage = concat(
      bytes("\x19Ethereum Signed Message:\n"),
      bytes(Uint256Util.toString(_msgBytes.length)),
      _msgBytes,
      new bytes(0), new bytes(0), new bytes(0), new bytes(0)
    );
    return ecrecover(keccak256(fullMessage), _v, _r, _s);
  }


  function concat(bytes memory ba, bytes memory bb, bytes memory bc, bytes memory bd, bytes memory be, bytes memory bf, bytes memory bg) internal pure returns (bytes memory) {
    bytes memory resultBytes = new bytes(ba.length + bb.length + bc.length + bd.length + be.length + bf.length + bg.length);
    uint k = 0;
    for (uint i = 0; i < ba.length; i++) resultBytes[k++] = ba[i];
    for (uint i = 0; i < bb.length; i++) resultBytes[k++] = bb[i];
    for (uint i = 0; i < bc.length; i++) resultBytes[k++] = bc[i];
    for (uint i = 0; i < bd.length; i++) resultBytes[k++] = bd[i];
    for (uint i = 0; i < be.length; i++) resultBytes[k++] = be[i];
    for (uint i = 0; i < bf.length; i++) resultBytes[k++] = bf[i];
    for (uint i = 0; i < bg.length; i++) resultBytes[k++] = bg[i];
    return resultBytes;
  }

  function toHexString(bytes memory _value) internal pure returns (string memory) {
    bytes memory alphabet = "0123456789abcdef";
    bytes memory str = new bytes(64);
    for (uint256 i = 0; i < _value.length; i++) {
      str[i*2] = alphabet[uint8(_value[i] >> 4)];
      str[1+i*2] = alphabet[uint8(_value[i] & 0x0f)];
    }
    return string(str);
  }
}