// File: Address.sol



// SPDX-License-Identifier: MIT
// Copied from https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/Address.sol
// and modified it.

pragma solidity >=0.7;

library Address {
    /**
     * @dev Returns true if `account` is a contract.
     *
     * [IMPORTANT]
     * ====
     * It is unsafe to assume that an address for which this function returns
     * false is an externally-owned account (EOA) and not a contract.
     *
     * Among others, `isContract` will return false for the following
     * types of addresses:
     *
     *  - an externally-owned account
     *  - a contract in construction
     *  - an address where a contract will be created
     *  - an address where a contract lived, but was destroyed
     * ====
     */
    function isContract(address account) internal view returns (bool) {
        // According to EIP-1052, 0x0 is the value returned for not-yet created accounts
        // and 0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470 is returned
        // for accounts without code, i.e. `keccak256('')`
        bytes32 codehash;
        bytes32 accountHash = 0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470;
        // solhint-disable-next-line no-inline-assembly
        assembly { codehash := extcodehash(account) }
        return (codehash != accountHash && codehash != 0x0);
    }

    function functionCallWithValue(address target, bytes memory data, uint256 weiValue) internal returns (bytes memory) {
        // solhint-disable-next-line avoid-low-level-calls
        require(data.length == 0 || isContract(target));
        (bool success, bytes memory returndata) = target.call{ value: weiValue }(data);
        if (success) {
            return returndata;
        } else {
            revert(string(returndata));
        }
    }
}
// File: MultiSig.sol



/**
 * SPDX-License-Identifier: MIT
 */

pragma solidity >=0.7;

import "./Address.sol";
import "./RLPEncode.sol";

contract MultiSig {

  mapping (address => uint8) public signers; // The addresses that can co-sign transactions and the number of signatures needed

  uint16 public signerCount;

  // Observation: the nonce is not increase when the transaction fails.
  uint256 private sequenceNumber; // A sequence number that contains the address of this contract to make it globally unique
  bytes public contractId; // most likely unique id of this contract

  event SignerChange(
    address indexed signer,
    uint8 cosignaturesNeeded
  );

  event Transacted(
    address indexed toAddress,  // The address the transaction was sent to
    bytes4 selector, // selected operation
    address[] signers // Addresses of the signers used to initiate the transaction
  );

  constructor (address owner) {
    // We use the gas price to get a unique id into our transactions.
    // Note that 32 bits do not guarantee that no one can generate a contract with the
    // same id, but it practically rules out that someone accidentally creates two
    // two multisig contracts with the same id, and that's all we need to prevent
    // replay-attacks.
    contractId = toBytes(uint32(address(this)));
    _setSigner(owner, 1); // start with the contract creator as owner
  }

  /**
   * It should be possible to store ether on this address.
   */
  receive() external payable {
  }

  /**
   * Checks if the provided signatures suffice to sign the transaction and if the nonce is correct.
   */
  function checkSignatures(address to, uint value, bytes calldata data,
    uint8[] calldata v, bytes32[] calldata r, bytes32[] calldata s) public view returns (address[] memory) {
    bytes32 transactionHash = calculateTransactionHash(nextSequenceNumber(), contractId, to, value, data);
    return verifySignatures(transactionHash, v, r, s);
  }

  /**
   * Checks if the execution of a transaction would succeed if it was properly signed.
   */
  function checkExecution(address to, uint value, bytes calldata data) public {
    Address.functionCallWithValue(to, data, value);
    require(false, "Test passed. Reverting.");
  }

  function execute(address to, uint value, bytes calldata data,
  uint8[] calldata v, bytes32[] calldata r, bytes32[] calldata s) public returns (bytes memory) {
    // ok to increment here already, will be rolled back in case of failure and saves us one local variable
    sequenceNumber = nextSequenceNumber();
    bytes32 transactionHash = calculateTransactionHash(sequenceNumber, contractId, to, value, data);
    address[] memory found = verifySignatures(transactionHash, v, r, s);
    bytes memory returndata = Address.functionCallWithValue(to, data, value);
    emit Transacted(to, extractSelector(data), found);
    return returndata;
  }

  function extractSelector(bytes calldata data) private pure returns (bytes4){
    if (data.length < 4){
      return bytes4(0);
    } else {
      return bytes4(data[0]) | (bytes4(data[1]) >> 8) | (bytes4(data[2]) >> 16) | (bytes4(data[3]) >> 24);
    }
  }

  function nextSequenceNumber() public view returns (uint256){
    return sequenceNumber + 1;
  }

  function toBytes(uint number) internal pure returns (bytes memory){
    uint len = 0;
    uint temp = 1;
    while (number >= temp){
      temp = temp << 8;
      len++;
    }
    temp = number;
    bytes memory data = new bytes(len);
    for (uint i = len; i>0; i--) {
      data[i-1] = bytes1(uint8(temp));
      temp = temp >> 8;
    }
    return data;
  }

  // Note: does not work with contract creation
  function calculateTransactionHash(uint sequence, bytes storage id, address to, uint value, bytes calldata data)
    private pure returns (bytes32){
    bytes[] memory all = new bytes[](9);
    all[0] = toBytes(sequence); // sequence number instead of nonce
    all[1] = id; // contract id instead of gas price
    all[2] = toBytes(21000); // gas limit
    all[3] = abi.encodePacked(to);
    all[4] = toBytes(value);
    all[5] = data;
    all[6] = toBytes(1);
    all[7] = toBytes(0);
    for (uint i = 0; i<8; i++){
      all[i] = RLPEncode.encodeBytes(all[i]);
    }
    all[8] = all[7];
    return keccak256(RLPEncode.encodeList(all));
  }

  function verifySignatures(bytes32 transactionHash, uint8[] calldata v, bytes32[] calldata r, bytes32[] calldata s)
    private view returns (address[] memory) {
    address[] memory found = new address[](r.length);
    for (uint i = 0; i < r.length; i++) {
      address signer = ecrecover(transactionHash, v[i], r[i], s[i]);
      uint8 cosignaturesNeeded = signers[signer];
      require(cosignaturesNeeded > 0 && cosignaturesNeeded <= r.length, "cosigner error");
      found[i] = signer;
    }
    requireNoDuplicates(found);
    return found;
  }

  function requireNoDuplicates(address[] memory found) private pure {
    for (uint i = 0; i < found.length; i++) {
      for (uint j = i+1; j < found.length; j++) {
        require(found[i] != found[j], "duplicate signature");
      }
    }
  }

  /**
   * Call this method through execute
   */
  function setSigner(address signer, uint8 cosignaturesNeeded) public authorized {
    _setSigner(signer, cosignaturesNeeded);
    require(signerCount > 0);
  }

  function migrate(address destination) public {
    _migrate(msg.sender, destination);
  }

  function migrate(address source, address destination) public authorized {
    require(source == address(this));
    _migrate(source, destination);
  }

  function _migrate(address source, address destination) private {
    require(signers[destination] == 0); // do not overwrite existing signer!
    _setSigner(destination, signers[source]);
    _setSigner(source, 0);
  }

  function _setSigner(address signer, uint8 cosignaturesNeeded) private {
    require(!Address.isContract(signer), "signer cannot be a contract");
    uint8 prevValue = signers[signer];
    signers[signer] = cosignaturesNeeded;
    if (prevValue > 0 && cosignaturesNeeded == 0){
      signerCount--;
    } else if (prevValue == 0 && cosignaturesNeeded > 0){
      signerCount++;
    }
    emit SignerChange(signer, cosignaturesNeeded);
  }

  modifier authorized() {
    require(address(this) == msg.sender || signers[msg.sender] == 1, "not authorized");
    _;
  }

}
// File: RLPEncode.sol



/// SPDX-License-Identifier: MIT
/// @title RLP Encoding Library for Solidity
/// @author Sam Mayo (sammayo888@gmail.com)
/// @dev Library for rlp encoding arbitrary bytes or lists.

pragma solidity >=0.7;

library RLPEncode {
    uint8 constant STRING_SHORT_PREFIX = 0x80;
    uint8 constant STRING_LONG_PREFIX = 0xb7;
    uint8 constant LIST_SHORT_PREFIX = 0xc0;
    uint8 constant LIST_LONG_PREFIX = 0xf7;

    /// @dev Rlp encodes a bytes
    /// @param self The bytes to be encoded
    /// @return The rlp encoded bytes
    function encodeBytes(bytes memory self) internal pure returns (bytes memory) {
        if(self.length == 1 && self[0] < 0x80) {
            return self;
        } else {
            return encode(self, STRING_SHORT_PREFIX, STRING_LONG_PREFIX);
        }
    }
    
    /// @dev Rlp encodes a bytes[]. Note that the items in the bytes[] will not automatically be rlp encoded.
    /// @param self The bytes[] to be encoded
    /// @return The rlp encoded bytes[]
    function encodeList(bytes[] memory self) internal pure returns (bytes memory) {
        bytes memory list = flatten(self);
        return encode(list, LIST_SHORT_PREFIX, LIST_LONG_PREFIX);
    }

    function encode(bytes memory self, uint8 prefix1, uint8 prefix2) private pure returns (bytes memory) {
        uint selfPtr;
        assembly { selfPtr := add(self, 0x20) }

        uint len = self.length;
        if(len <= 55) {
            bytes memory encoded = new bytes(len+1);
            uint8 lenshort = uint8(len);
            // length encoding byte
            encoded[0] = byte(prefix1+lenshort);

            // string/list contents
            uint encodedPtr;
            assembly { encodedPtr := add(encoded, 0x21) }
            memcpy(encodedPtr, selfPtr, len);
            return encoded;
        } else {
            uint8 lenLen;
            uint i = 0x1;
            while(len/i != 0) {
                lenLen++;
                i *= 0x100;
            }

            // 1 is the length of the length of the length
           bytes memory encoded = new bytes(1+lenLen+len);

            // length of the length encoding byte
            encoded[0] = byte(prefix2+lenLen);

            // length bytes
            for(i=1; i<=lenLen; i++) {
                encoded[i] = byte(uint8((len/(0x100**(lenLen-i)))%0x100));
            }

            // string/list contents
            uint encodedPtr;
            assembly { encodedPtr := add(add(encoded, 0x21), lenLen) }
            memcpy(encodedPtr, selfPtr, len);
            return encoded;
        }
    }
    
    function flatten(bytes[] memory self) private pure returns (bytes memory) {
        if(self.length == 0) {
            return new bytes(0);
        }

        uint len;
        for(uint i=0; i<self.length; i++) {
            len += self[i].length;
        }

        bytes memory flattened = new bytes(len);
        uint flattenedPtr;
        assembly { flattenedPtr := add(flattened, 0x20) }

        for(uint i=0; i<self.length; i++) {
            bytes memory item = self[i];
            
            uint selfPtr;
            assembly { selfPtr := add(item, 0x20)}

            memcpy(flattenedPtr, selfPtr, item.length);
            flattenedPtr += self[i].length;
        }

        return flattened;
    }

    /// This function is from Nick Johnson's string utils library
    function memcpy(uint dest, uint src, uint len) private pure {
        // 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))
        }
    }
}