library Lib_MerkleTree {
  /**********************
   * Internal Functions *
   **********************/

  /**
   * Calculates a merkle root for a list of 32-byte leaf hashes.  WARNING: If the number
   * of leaves passed in is not a power of two, it pads out the tree with zero hashes.
   * If you do not know the original length of elements for the tree you are verifying, then
   * this may allow empty leaves past _elements.length to pass a verification check down the line.
   * Note that the _elements argument is modified, therefore it must not be used again afterwards
   * @param _elements Array of hashes from which to generate a merkle root.
   * @return Merkle root of the leaves, with zero hashes for non-powers-of-two (see above).
   */
  function getMerkleRoot(bytes32[] memory _elements)
    internal
    pure
    returns (bytes32)
  {
    require(
      _elements.length > 0,
      'Lib_MerkleTree: Must provide at least one leaf hash.'
    );

    if (_elements.length == 1) {
      return _elements[0];
    }

    uint256[16] memory defaults = [
      0x290decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e563,
      0x633dc4d7da7256660a892f8f1604a44b5432649cc8ec5cb3ced4c4e6ac94dd1d,
      0x890740a8eb06ce9be422cb8da5cdafc2b58c0a5e24036c578de2a433c828ff7d,
      0x3b8ec09e026fdc305365dfc94e189a81b38c7597b3d941c279f042e8206e0bd8,
      0xecd50eee38e386bd62be9bedb990706951b65fe053bd9d8a521af753d139e2da,
      0xdefff6d330bb5403f63b14f33b578274160de3a50df4efecf0e0db73bcdd3da5,
      0x617bdd11f7c0a11f49db22f629387a12da7596f9d1704d7465177c63d88ec7d7,
      0x292c23a9aa1d8bea7e2435e555a4a60e379a5a35f3f452bae60121073fb6eead,
      0xe1cea92ed99acdcb045a6726b2f87107e8a61620a232cf4d7d5b5766b3952e10,
      0x7ad66c0a68c72cb89e4fb4303841966e4062a76ab97451e3b9fb526a5ceb7f82,
      0xe026cc5a4aed3c22a58cbd3d2ac754c9352c5436f638042dca99034e83636516,
      0x3d04cffd8b46a874edf5cfae63077de85f849a660426697b06a829c70dd1409c,
      0xad676aa337a485e4728a0b240d92b3ef7b3c372d06d189322bfd5f61f1e7203e,
      0xa2fca4a49658f9fab7aa63289c91b7c7b6c832a6d0e69334ff5b0a3483d09dab,
      0x4ebfd9cd7bca2505f7bef59cc1c12ecc708fff26ae4af19abe852afe9e20c862,
      0x2def10d13dd169f550f578bda343d9717a138562e0093b380a1120789d53cf10
    ];

    // Reserve memory space for our hashes.
    bytes memory buf = new bytes(64);

    // We'll need to keep track of left and right siblings.
    bytes32 leftSibling;
    bytes32 rightSibling;

    // Number of non-empty nodes at the current depth.
    uint256 rowSize = _elements.length;

    // Current depth, counting from 0 at the leaves
    uint256 depth = 0;

    // Common sub-expressions
    uint256 halfRowSize; // rowSize / 2
    bool rowSizeIsOdd; // rowSize % 2 == 1

    while (rowSize > 1) {
      halfRowSize = rowSize / 2;
      rowSizeIsOdd = rowSize % 2 == 1;

      for (uint256 i = 0; i < halfRowSize; i++) {
        leftSibling = _elements[(2 * i)];
        rightSibling = _elements[(2 * i) + 1];
        assembly {
          mstore(add(buf, 32), leftSibling)
          mstore(add(buf, 64), rightSibling)
        }

        _elements[i] = keccak256(buf);
      }

      if (rowSizeIsOdd) {
        leftSibling = _elements[rowSize - 1];
        rightSibling = bytes32(defaults[depth]);
        assembly {
          mstore(add(buf, 32), leftSibling)
          mstore(add(buf, 64), rightSibling)
        }

        _elements[halfRowSize] = keccak256(buf);
      }

      rowSize = halfRowSize + (rowSizeIsOdd ? 1 : 0);
      depth++;
    }

    return _elements[0];
  }

  /**
   * Verifies a merkle branch for the given leaf hash.  Assumes the original length
   * of leaves generated is a known, correct input, and does not return true for indices
   * extending past that index (even if _siblings would be otherwise valid.)
   * @param _root The Merkle root to verify against.
   * @param _leaf The leaf hash to verify inclusion of.
   * @param _index The index in the tree of this leaf.
   * @param _siblings Array of sibline nodes in the inclusion proof, starting from depth 0
   * (bottom of the tree).
   * @param _totalLeaves The total number of leaves originally passed into.
   * @return Whether or not the merkle branch and leaf passes verification.
   */
  function verify(
    bytes32 _root,
    bytes32 _leaf,
    uint256 _index,
    bytes32[] memory _siblings,
    uint256 _totalLeaves
  ) internal pure returns (bool) {
    require(
      _totalLeaves > 0,
      'Lib_MerkleTree: Total leaves must be greater than zero.'
    );

    require(_index < _totalLeaves, 'Lib_MerkleTree: Index out of bounds.');

    require(
      _siblings.length == _ceilLog2(_totalLeaves),
      'Lib_MerkleTree: Total siblings does not correctly correspond to total leaves.'
    );

    bytes32 computedRoot = _leaf;

    for (uint256 i = 0; i < _siblings.length; i++) {
      if ((_index & 1) == 1) {
        computedRoot = keccak256(abi.encodePacked(_siblings[i], computedRoot));
      } else {
        computedRoot = keccak256(abi.encodePacked(computedRoot, _siblings[i]));
      }

      _index >>= 1;
    }

    return _root == computedRoot;
  }

  /*********************
   * Private Functions *
   *********************/

  /**
   * Calculates the integer ceiling of the log base 2 of an input.
   * @param _in Unsigned input to calculate the log.
   * @return ceil(log_base_2(_in))
   */
  function _ceilLog2(uint256 _in) private pure returns (uint256) {
    require(_in > 0, 'Lib_MerkleTree: Cannot compute ceil(log_2) of 0.');

    if (_in == 1) {
      return 0;
    }

    // Find the highest set bit (will be floor(log_2)).
    // Borrowed with <3 from https://github.com/ethereum/solidity-examples
    uint256 val = _in;
    uint256 highest = 0;
    for (uint256 i = 128; i >= 1; i >>= 1) {
      if (val & (((uint256(1) << i) - 1) << i) != 0) {
        highest += i;
        val >>= i;
      }
    }

    // Increment by one if this is not a perfect logarithm.
    if ((uint256(1) << highest) != _in) {
      highest += 1;
    }

    return highest;
  }
}
/**
 * @title Lib_MerkleTree
 * @author River Keefer
 */
function verify(
  bytes32 _root,
  bytes32 _leaf,
  uint256 _index,
  bytes32[] memory _siblings,
  uint256 _totalLeaves
) internal pure returns (bool) {
  require(
    _totalLeaves > 0,
    'Lib_MerkleTree: Total leaves must be greater than zero.'
  );

  require(_index < _totalLeaves, 'Lib_MerkleTree: Index out of bounds.');

  require(
    _siblings.length == _ceilLog2(_totalLeaves),
    'Lib_MerkleTree: Total siblings does not correctly correspond to total leaves.'
  );

  bytes32 computedRoot = _leaf;

  for (uint256 i = 0; i < _siblings.length; i++) {
    if ((_index & 1) == 1) {
      computedRoot = keccak256(abi.encodePacked(_siblings[i], computedRoot));
    } else {
      computedRoot = keccak256(abi.encodePacked(computedRoot, _siblings[i]));
    }

    _index >>= 1;
  }

  return _root == computedRoot;
}

/**
 * Verifies a merkle branch for the given leaf hash.  Assumes the original length
 * of leaves generated is a known, correct input, and does not return true for indices
 * extending past that index (even if _siblings would be otherwise valid.)
 * @param _root The Merkle root to verify against.
 * @param _leaf The leaf hash to verify inclusion of.
 * @param _index The index in the tree of this leaf.
 * @param _siblings Array of sibline nodes in the inclusion proof, starting from depth 0
 * (bottom of the tree).
 * @param _totalLeaves The total number of leaves originally passed into.
 * @return Whether or not the merkle branch and leaf passes verification.
 */