// File: CairoBootloaderProgram.sol



/*
  Copyright 2019,2020 StarkWare Industries Ltd.

  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

  https://www.starkware.co/open-source-license/

  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.
*/
// ---------- The following code was auto-generated. PLEASE DO NOT EDIT. ----------
// SPDX-License-Identifier: Apache-2.0.
pragma solidity ^0.6.11;

contract CairoBootloaderProgramSize {
    uint256 internal constant PROGRAM_SIZE = 224;
}

contract CairoBootloaderProgram is CairoBootloaderProgramSize {
    function getCompiledProgram()
        external pure
        returns (uint256[PROGRAM_SIZE] memory)
    {
        return [
            1226245742482522112,
            181,
            74168662805676031,
            0,
            146226256843603965,
            4,
            5191102238658887680,
            2345108766317314046,
            290341444919459839,
            3,
            4632937381316558848,
            4612671182992932865,
            4612671182992998402,
            146226256843603968,
            4,
            74168662805676031,
            4,
            4612671182993063937,
            4612671182993129474,
            5198983563776196608,
            1,
            5198983563776262144,
            1,
            5200109459388203008,
            5200109459388268544,
            5198983563776458752,
            3618502788666131213697322783095070105623107215331596699973092056135872020480,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020458,
            2345108766317314046,
            2345108766317314046,
            1226245742482522112,
            5,
            5198420613823102976,
            3618502788666131213697322783095070105623107215331596699973092056135872020479,
            2345108766317314046,
            2345108766317314046,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020474,
            5198420613823168512,
            3618502788666131213697322783095070105623107215331596699973092056135872020442,
            5202361254907052032,
            2345108766317314046,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020468,
            5191102234363920384,
            5191102238658887680,
            5191102242953854976,
            5198420613822906368,
            50,
            5189976364521848832,
            4,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020433,
            4623648689905041407,
            291467327646433279,
            2345108766317314046,
            146226256843603965,
            4,
            5191102230068953088,
            2345108766317314046,
            5188850460319711232,
            5188850460319776768,
            5201798300658860031,
            5188850460319842304,
            5210805504208568318,
            4612389708016222207,
            5198983563776196608,
            1,
            5198983563776262144,
            1,
            5198983563776327680,
            1,
            5198983563776393216,
            1,
            5198983563776458752,
            3618502788666131213697322783095070105623107215331596699973092056135872020480,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020461,
            2345108766317314046,
            5188850460319907840,
            5202361254907052032,
            5191102242953854976,
            5188287510366552064,
            5188287506071519232,
            5188287510366486527,
            4611826762357964797,
            5198420613822906368,
            3618502788666131213697322783095070105623107215331596699973092056135872020480,
            5198420613822906368,
            3,
            5188287518956224512,
            4623085744246521853,
            145944781866893308,
            3618502788666131213697322783095070105623107215331596699973092056135872020472,
            2345108766317314046,
            146226256843603965,
            6,
            5191102225773985792,
            5191102238658887680,
            5191102242953854976,
            2345108766317314046,
            290341444919459839,
            16,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020407,
            4617174774030761984,
            4612671182992867338,
            5189976364521848832,
            0,
            4612389712311713791,
            5188850464614547456,
            5191102264428691456,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020448,
            4612389712312303615,
            4622804286450008075,
            4,
            4612671195878359052,
            5200109510928859136,
            5188850468910104576,
            4625619027626983437,
            4622804286450597890,
            2,
            4617174765440827395,
            4612671191582801924,
            4612671195877769221,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020384,
            4612389712311386110,
            5189976364521848832,
            16,
            5201798304953696256,
            4612389708016418815,
            5191102230068953088,
            5198983563776655360,
            2,
            5191102307378364416,
            5191102311673331712,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020385,
            1191342896910008320,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020370,
            4623648758625632255,
            722405534170316800,
            0,
            5191102230068953088,
            5198983563776655360,
            6,
            5191102307378364416,
            5191102320263266304,
            5189976364521848832,
            4,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020331,
            4623648754330533887,
            5191102238658887680,
            5198983563776655360,
            2,
            5198983563776655360,
            6,
            5191102234363920384,
            5189976364521848832,
            4,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020373,
            4623930225012473862,
            4612671182994046991,
            5198983563776655360,
            6,
            5191102230068953088,
            5191102234363920384,
            5193354042767540224,
            5198983563776393216,
            2,
            5198983563776458752,
            3618502788666131213697322783095070105623107215331596699973092056135872020480,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020399,
            2345108766317314046,
            290341444919459839,
            1,
            5199265038752907265,
            1,
            5191383709340631042,
            5191383735110434819,
            5191383717930565636,
            5190257839498559493,
            122550255383924,
            5190257839498559494,
            8098989891770344814,
            5190257839498559495,
            138277649577220228665140075,
            5190257839498559496,
            435459224417,
            5190257839498559497,
            1,
            5190257839498559498,
            3,
            5190257839498559499,
            1,
            5190257839498559500,
            2,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020307,
            5198420613823102976,
            1,
            5198420613823037440,
            5,
            5198420613822971904,
            9,
            5191102238658887680,
            5191102247248822272,
            5188850460319645696,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020362,
            4614641507830300670,
            5188287510366486528,
            5188287514661388288,
            5188287518956290048,
            5188287523251191808,
            5193354038472572928,
            2345108766317314046
        ];
    }
}
// ---------- End of auto-generated code. ----------

// File: CairoVerifierContract.sol



/*
  Copyright 2019,2020 StarkWare Industries Ltd.

  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

  https://www.starkware.co/open-source-license/

  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.
*/
// SPDX-License-Identifier: Apache-2.0.
pragma solidity ^0.6.11;

interface CairoVerifierContract {
    function verifyProofExternal(
        uint256[] calldata proofParams, uint256[] calldata proof, uint256[] calldata publicInput)
        external;
}

// File: CpuPublicInputOffsets.sol



/*
  Copyright 2019,2020 StarkWare Industries Ltd.

  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

  https://www.starkware.co/open-source-license/

  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.
*/
// SPDX-License-Identifier: Apache-2.0.
pragma solidity ^0.6.11;

contract CpuPublicInputOffsets {
    // The following constants are offsets of data expected in the public input.
    uint256 internal constant OFFSET_LOG_N_STEPS = 0;
    uint256 internal constant OFFSET_RC_MIN = 1;
    uint256 internal constant OFFSET_RC_MAX = 2;
    uint256 internal constant OFFSET_LAYOUT_CODE = 3;
    uint256 internal constant OFFSET_PROGRAM_BEGIN_ADDR = 4;
    uint256 internal constant OFFSET_PROGRAM_STOP_PTR = 5;
    uint256 internal constant OFFSET_EXECUTION_BEGIN_ADDR = 6;
    uint256 internal constant OFFSET_EXECUTION_STOP_PTR = 7;
    uint256 internal constant OFFSET_OUTPUT_BEGIN_ADDR = 8;
    uint256 internal constant OFFSET_OUTPUT_STOP_PTR = 9;
    uint256 internal constant OFFSET_PEDERSEN_BEGIN_ADDR = 10;
    uint256 internal constant OFFSET_PEDERSEN_STOP_PTR = 11;
    uint256 internal constant OFFSET_RANGE_CHECK_BEGIN_ADDR = 12;
    uint256 internal constant OFFSET_RANGE_CHECK_STOP_PTR = 13;
    uint256 internal constant OFFSET_ECDSA_BEGIN_ADDR = 14;
    uint256 internal constant OFFSET_ECDSA_STOP_PTR = 15;
    uint256 internal constant OFFSET_CHECKPOINTS_BEGIN_PTR = 16;
    uint256 internal constant OFFSET_CHECKPOINTS_STOP_PTR = 17;
    uint256 internal constant OFFSET_PUBLIC_MEMORY_PADDING_ADDR = 18;
    uint256 internal constant OFFSET_PUBLIC_MEMORY_PADDING_VALUE = 19;
    uint256 internal constant OFFSET_N_PUBLIC_MEMORY_PAGES = 20;
    uint256 internal constant OFFSET_PUBLIC_MEMORY = 21;

    uint256 internal constant N_WORDS_PER_PUBLIC_MEMORY_ENTRY = 2;
    // The program segment starts from 1, so that memory address 0 is kept for the null pointer.
    uint256 internal constant INITIAL_PC = 1;
    uint256 internal constant FINAL_PC = INITIAL_PC + 2;

    // The format of the public input, starting at OFFSET_PUBLIC_MEMORY is as follows:
    //   * For each page:
    //     * First address in the page (this field is not included for the first page).
    //     * Page size.
    //     * Page hash.
    //   # All data above this line, appears in the initial seed of the proof.
    //   * For each page:
    //     * Cumulative product.

    function getOffsetPageSize(uint256 pageId) internal pure returns (uint256) {
        return OFFSET_PUBLIC_MEMORY + 3 * pageId;
    }

    function getOffsetPageHash(uint256 pageId) internal pure returns (uint256) {
        return OFFSET_PUBLIC_MEMORY + 3 * pageId + 1;
    }

    function getOffsetPageAddr(uint256 pageId) internal pure returns (uint256) {
        require(pageId >= 1, "Address of page 0 is not part of the public input.");
        return OFFSET_PUBLIC_MEMORY + 3 * pageId - 1;
    }

    function getOffsetPageProd(uint256 pageId, uint256 nPages) internal pure returns (uint256) {
        return OFFSET_PUBLIC_MEMORY + 3 * nPages - 1 + pageId;
    }

    function getPublicInputLength(uint256 nPages) internal pure returns (uint256) {
        return OFFSET_PUBLIC_MEMORY + 4 * nPages - 1;
    }

}

// File: FactRegistry.sol



/*
  Copyright 2019,2020 StarkWare Industries Ltd.

  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

  https://www.starkware.co/open-source-license/

  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.
*/
// SPDX-License-Identifier: Apache-2.0.
pragma solidity ^0.6.11;

import "IQueryableFactRegistry.sol";

contract FactRegistry is IQueryableFactRegistry {
    // Mapping: fact hash -> true.
    mapping (bytes32 => bool) private verifiedFact;

    // Indicates whether the Fact Registry has at least one fact registered.
    bool anyFactRegistered;

    /*
      Checks if a fact has been verified.
    */
    function isValid(bytes32 fact)
        external view override
        returns(bool)
    {
        return _factCheck(fact);
    }


    /*
      This is an internal method to check if the fact is already registered.
      In current implementation of FactRegistry it's identical to isValid().
      But the check is against the local fact registry,
      So for a derived referral fact registry, it's not the same.
    */
    function _factCheck(bytes32 fact)
        internal view
        returns(bool)
    {
        return verifiedFact[fact];
    }

    function registerFact(
        bytes32 factHash
        )
        internal
    {
        // This function stores the fact hash in the mapping.
        verifiedFact[factHash] = true;

        // Mark first time off.
        if (!anyFactRegistered) {
            anyFactRegistered = true;
        }
    }

    /*
      Indicates whether at least one fact was registered.
    */
    function hasRegisteredFact()
        external view override
        returns(bool)
    {
        return anyFactRegistered;
    }

}

// File: GpsOutputParser.sol



/*
  Copyright 2019,2020 StarkWare Industries Ltd.

  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

  https://www.starkware.co/open-source-license/

  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.
*/
// SPDX-License-Identifier: Apache-2.0.
pragma solidity ^0.6.11;

import "CpuPublicInputOffsets.sol";
import "FactRegistry.sol";

/*
  A utility contract to parse the GPS output.
  See registerGpsFacts for more details.
*/
contract GpsOutputParser is CpuPublicInputOffsets, FactRegistry {
    uint256 internal constant METADATA_TASKS_OFFSET = 1;
    uint256 internal constant METADATA_OFFSET_TASK_OUTPUT_SIZE = 0;
    uint256 internal constant METADATA_OFFSET_TASK_PROGRAM_HASH = 1;
    uint256 internal constant METADATA_OFFSET_TASK_N_TREE_PAIRS = 2;
    uint256 internal constant METADATA_TASK_HEADER_SIZE = 3;

    uint256 internal constant METADATA_OFFSET_TREE_PAIR_N_PAGES = 0;
    uint256 internal constant METADATA_OFFSET_TREE_PAIR_N_NODES = 1;

    uint256 internal constant NODE_STACK_OFFSET_HASH = 0;
    uint256 internal constant NODE_STACK_OFFSET_END = 1;
    // The size of each node in the node stack.
    uint256 internal constant NODE_STACK_ITEM_SIZE = 2;

    uint256 internal constant FIRST_CONTINUOUS_PAGE_INDEX = 1;

    /*
      Logs the fact hash together with the relavent continuous memory pages' hashes.
      Emitted for each registered fact.
    */
    event LogMemoryPagesHashes(bytes32 factHash, bytes32[] pagesHashes);

    /*
      Parses the GPS program output (using taskMetadata, which should be verified by the caller),
      and registers the facts of the tasks which were executed.

      The first entry in taskMetadata is the number of tasks.

      For each task, the structure is as follows:
        1. Size (including the size and hash fields).
        2. Program hash.
        3. The numebr of pairs in the Merkle tree structure (see below).
        4. The Merkle tree structure (see below).

      The fact of each task is stored as a (non-binary) Merkle tree.
      Each non-leaf node is 1 + the hash of (node0, end0, node1, end1, ...)
      where node* are its children and end* is the the total number of data words up to and
      including that node and its children (including the previous sibling nodes).
      We add 1 to the result of the hash to distinguish it from a leaf node.
      Leaf nodes are the hash of their data.

      The structure of the tree is passed as a list of pairs (n_pages, n_nodes), and the tree is
      constructed using a stack of nodes (initialized to an empty stack) by repeating for each pair:
      1. Add n_pages to the stack of nodes.
      2. Pop the top n_nodes, construct a parent node for them, and push it back to the stack.
      After applying the steps above, the stack much contain exactly one node, which will
      constitute the root of the Merkle tree.
      For example, [(2, 2)] will create a Merkle tree with a root and two direct children, while
      [(3, 2), (0, 2)] will create a Merkle tree with a root whose left child is a leaf and
      right child has two leaf children.

      Assumptions: taskMetadata and cairoAuxInput are verified externaly.
    */
    function registerGpsFacts(uint256[] memory taskMetadata, uint256[] memory cairoAuxInput)
        internal
    {
        // Allocate some of the loop variables here to avoid the stack-too-deep error.
        uint256 task;
        uint256 nTreePairs;
        uint256 nTasks = taskMetadata[0];

        // Contains fact hash with the relevant memory pages' hashes.
        // Size is bounded from above with the total number of pages. Three extra places are
        // dedicated for the fact hash and the array address and length.
        uint256[] memory pageHashesLogData = new uint256[](
            cairoAuxInput[OFFSET_N_PUBLIC_MEMORY_PAGES] + 3);
        // Relative address to the beginning of the memory pages' hashes in the array.
        pageHashesLogData[1] = 0x40;

        uint256 taskMetadataOffset = METADATA_TASKS_OFFSET;

        // Skip the 3 first output cells which contain the number of tasks and the size and
        // program hash of the first task. curAddr points to the output of the first task.
        uint256 curAddr = cairoAuxInput[OFFSET_OUTPUT_BEGIN_ADDR] + 3;

        // Skip the main page.
        uint256 curPage = FIRST_CONTINUOUS_PAGE_INDEX;

        // Bound the size of the stack by the total number of pages.
        uint256[] memory nodeStack = new uint256[](
            NODE_STACK_ITEM_SIZE * cairoAuxInput[OFFSET_N_PUBLIC_MEMORY_PAGES]);

        // Copy to avoid the "stack too deep" error.
        uint256[] memory taskMetadataCopy = taskMetadata;
        uint256[] memory cairoAuxInputCopy = cairoAuxInput;

        // Register the fact for each task.
        for (task = 0; task < nTasks; task++) {
            uint256 curOffset = 0;
            uint256 firstPageOfTask = curPage;
            nTreePairs = taskMetadataCopy[
                taskMetadataOffset + METADATA_OFFSET_TASK_N_TREE_PAIRS];

            // Build the Merkle tree using a stack (see the function documentation) to compute
            // the fact.
            uint256 nodeStackLen = 0;
            for (uint256 treePair = 0; treePair < nTreePairs; treePair++) {
                // Add n_pages to the stack of nodes.
                uint256 nPages = taskMetadataCopy[
                    taskMetadataOffset + METADATA_TASK_HEADER_SIZE + 2 * treePair +
                    METADATA_OFFSET_TREE_PAIR_N_PAGES];
                require(nPages < 2**20, "Invalid value of n_pages in tree structure.");

                for (uint256 i = 0; i < nPages; i++) {
                    (uint256 pageSize, uint256 pageHash) = pushPageToStack(
                        curPage, curAddr, curOffset, nodeStack, nodeStackLen, cairoAuxInputCopy);
                    pageHashesLogData[curPage - firstPageOfTask + 3] = pageHash;
                    curPage += 1;
                    nodeStackLen += 1;
                    curAddr += pageSize;
                    curOffset += pageSize;
                }

                // Pop the top n_nodes, construct a parent node for them, and push it back to the
                // stack.
                uint256 nNodes = taskMetadataCopy[
                    taskMetadataOffset + METADATA_TASK_HEADER_SIZE + 2 * treePair +
                    METADATA_OFFSET_TREE_PAIR_N_NODES];
                if (nNodes != 0) {
                    nodeStackLen = constructNode(nodeStack, nodeStackLen, nNodes);
                }
            }
            require(nodeStackLen == 1, "Node stack must contain exactly one item.");

            uint256 programHash = taskMetadataCopy[
                taskMetadataOffset + METADATA_OFFSET_TASK_PROGRAM_HASH];

            // Verify that the sizes of the pages correspond to the task output, to make
            // sure that the computed hash is indeed the hash of the entire output of the task.
            {
            uint256 outputSize = taskMetadataCopy[
                taskMetadataOffset + METADATA_OFFSET_TASK_OUTPUT_SIZE];

            require(
                nodeStack[NODE_STACK_OFFSET_END] + 2 == outputSize,
                "The sum of the page sizes does not match output size.");
            }

            uint256 fact_without_program_hash = nodeStack[NODE_STACK_OFFSET_HASH];
            bytes32 fact = keccak256(abi.encode(programHash, fact_without_program_hash));

            // Update taskMetadataOffset.
            taskMetadataOffset += METADATA_TASK_HEADER_SIZE + 2 * nTreePairs;

            {
            // Documents each fact hash together with the hashes of the relavent memory pages.
            // Instead of emit, we use log1 https://docs.soliditylang.org/en/v0.4.24/assembly.html,
            // https://docs.soliditylang.org/en/v0.6.2/abi-spec.html#use-of-dynamic-types.

            bytes32 logHash = keccak256("LogMemoryPagesHashes(bytes32,bytes32[])");
            assembly {
                let buf := add(pageHashesLogData, 0x20)
                // Number of memory pages that are relavent for this fact.
                let length := sub(curPage, firstPageOfTask)
                mstore(buf, fact_without_program_hash)
                mstore(add(buf, 0x40), length)
                log1(buf, mul(add(length, 3), 0x20), logHash)
            }
            }
            registerFact(fact);

            // Move curAddr to the output of the next task (skipping the size and hash fields).
            curAddr += 2;
        }

        require(
            cairoAuxInput[OFFSET_N_PUBLIC_MEMORY_PAGES] == curPage,
            "Not all memory pages were processed.");
    }

    /*
      Push one page (curPage) to the top of the node stack.
      curAddr is the memory address, curOffset is the offset from the beginning of the task output.
      Verifies that the page has the right start address and returns the page size and the page
      hash.
    */
    function pushPageToStack(
        uint256 curPage, uint256 curAddr, uint256 curOffset, uint256[] memory nodeStack,
        uint256 nodeStackLen, uint256[] memory cairoAuxInput)
        internal pure returns (uint256, uint256)
    {
        // Extract the page size, first address and hash from cairoAuxInput.
        uint256 pageSizeOffset = getOffsetPageSize(curPage);
        uint256 pageSize;
        uint256 pageAddrOffset = getOffsetPageAddr(curPage);
        uint256 pageAddr;
        uint256 pageHashOffset = getOffsetPageHash(curPage);
        uint256 pageHash;
        assembly {
            pageSize := mload(add(cairoAuxInput, mul(add(pageSizeOffset, 1), 0x20)))
            pageAddr := mload(add(cairoAuxInput, mul(add(pageAddrOffset, 1), 0x20)))
            pageHash := mload(add(cairoAuxInput, mul(add(pageHashOffset, 1), 0x20)))
        }
        require(pageSize < 2**30, "Invalid page size.");
        require(pageAddr == curAddr, "Invalid page address.");

        nodeStack[NODE_STACK_ITEM_SIZE * nodeStackLen + NODE_STACK_OFFSET_END] =
            curOffset + pageSize;
        nodeStack[NODE_STACK_ITEM_SIZE * nodeStackLen + NODE_STACK_OFFSET_HASH] = pageHash;
        return (pageSize, pageHash);
    }

    /*
      Pops the top nNodes nodes from the stack and pushes one parent node instead.
      Returns the new value of nodeStackLen.
    */
    function constructNode(uint256[] memory nodeStack, uint256 nodeStackLen, uint256 nNodes)
        internal pure returns (uint256) {
        require(nNodes <= nodeStackLen, "Invalid value of n_nodes in tree structure.");
        // The end of the node is the end of the last child.
        uint256 newNodeEnd = nodeStack[
            NODE_STACK_ITEM_SIZE * (nodeStackLen - 1) + NODE_STACK_OFFSET_END];
        uint256 newStackLen = nodeStackLen - nNodes;
        // Compute node hash.
        uint256 nodeStart = 0x20 + newStackLen * NODE_STACK_ITEM_SIZE * 0x20;
        uint256 newNodeHash;
        assembly {
            newNodeHash := keccak256(add(nodeStack, nodeStart), mul(
                nNodes, /*NODE_STACK_ITEM_SIZE * 0x20*/0x40))
        }

        nodeStack[NODE_STACK_ITEM_SIZE * newStackLen + NODE_STACK_OFFSET_END] = newNodeEnd;
        // Add one to the new node hash to distinguish it from the hash of a leaf (a page).
        nodeStack[NODE_STACK_ITEM_SIZE * newStackLen + NODE_STACK_OFFSET_HASH] = newNodeHash + 1;
        return newStackLen + 1;
    }
}

// File: GpsStatementVerifier.sol



/*
  Copyright 2019,2020 StarkWare Industries Ltd.

  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

  https://www.starkware.co/open-source-license/

  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.
*/
// SPDX-License-Identifier: Apache-2.0.
pragma solidity ^0.6.11;

import "CairoBootloaderProgram.sol";
import "CairoVerifierContract.sol";
import "CpuPublicInputOffsets.sol";
import "MemoryPageFactRegistry.sol";
import "Identity.sol";
import "PrimeFieldElement0.sol";
import "GpsOutputParser.sol";

contract GpsStatementVerifier is
        GpsOutputParser, Identity, CairoBootloaderProgramSize, PrimeFieldElement0 {
    CairoBootloaderProgram bootloaderProgramContractAddress;
    MemoryPageFactRegistry memoryPageFactRegistry;
    CairoVerifierContract[] cairoVerifierContractAddresses;

    uint256 internal constant N_MAIN_ARGS = 5;
    uint256 internal constant N_MAIN_RETURN_VALUES = 5;
    uint256 internal constant N_BUILTINS = 4;

    /*
      Constructs an instance of GpsStatementVerifier.
      bootloaderProgramContract is the address of the bootloader program contract
      and cairoVerifierContracts is a list of cairoVerifiers indexed by their id.
    */
    constructor(
        address bootloaderProgramContract,
        address memoryPageFactRegistry_,
        address[] memory cairoVerifierContracts)
        public
    {
        bootloaderProgramContractAddress = CairoBootloaderProgram(bootloaderProgramContract);
        memoryPageFactRegistry = MemoryPageFactRegistry(memoryPageFactRegistry_);
        cairoVerifierContractAddresses = new CairoVerifierContract[](cairoVerifierContracts.length);
        for (uint256 i = 0; i < cairoVerifierContracts.length; ++i) {
            cairoVerifierContractAddresses[i] = CairoVerifierContract(cairoVerifierContracts[i]);
        }
    }

    function identify()
        external pure override
        returns(string memory)
    {
        return "StarkWare_GpsStatementVerifier_2020_1";
    }

    /*
      Verifies a proof and registers the corresponding facts.
      For the structure of cairoAuxInput, see cpu/CpuPublicInputOffsets.sol.
      taskMetadata is structured as follows:
      1. Number of tasks.
      2. For each task:
         1. Task output size (including program hash and size).
         2. Program hash.
    */
    function verifyProofAndRegister(
        uint256[] calldata proofParams,
        uint256[] calldata proof,
        uint256[] calldata taskMetadata,
        uint256[] calldata cairoAuxInput,
        uint256 cairoVerifierId
    )
        external
    {
        require(
            cairoAuxInput.length > OFFSET_N_PUBLIC_MEMORY_PAGES,
            "Invalid cairoAuxInput length.");
        uint256 nPages = cairoAuxInput[OFFSET_N_PUBLIC_MEMORY_PAGES];
        require(
            cairoAuxInput.length == getPublicInputLength(nPages) + /*z and alpha*/ 2,
            "Invalid cairoAuxInput length.");

        // The values z and alpha are used only for the fact registration of the main page.
        // They are not needed in the auxiliary input of CpuVerifier as they are computed there.
        // Create a copy of cairoAuxInput without z and alpha.
        uint256[] memory cairoPublicInput = new uint256[](cairoAuxInput.length - /*z and alpha*/ 2);
        for (uint256 i = 0; i < cairoAuxInput.length - /*z and alpha*/ 2; i++) {
            cairoPublicInput[i] = cairoAuxInput[i];
        }

        {
        // Process public memory.
        (uint256 publicMemoryLength, uint256 memoryHash, uint256 prod) =
            registerPublicMemoryMainPage(taskMetadata, cairoAuxInput);

        // Make sure the first page is valid.
        // If the size or the hash are invalid, it may indicate that there is a mismatch between the
        // bootloader program contract and the program in the proof.
        require(
            cairoAuxInput[getOffsetPageSize(0)] == publicMemoryLength,
            "Invalid size for memory page 0.");
        require(
            cairoAuxInput[getOffsetPageHash(0)] == memoryHash,
            "Invalid hash for memory page 0.");
        require(
            cairoAuxInput[getOffsetPageProd(0, nPages)] == prod,
            "Invalid cumulative product for memory page 0.");
        }

        require(
            cairoVerifierId < cairoVerifierContractAddresses.length,
            "cairoVerifierId is out of range.");

        // NOLINTNEXTLINE: reentrancy-benign.
        cairoVerifierContractAddresses[cairoVerifierId].verifyProofExternal(
            proofParams, proof, cairoPublicInput);

        registerGpsFacts(taskMetadata, cairoAuxInput);
    }

    /*
      Registers the fact for memory page 0, which includes:
      1. The bootloader program,
      2. Arguments and return values of main()
      3. Some of the data required for computing the task facts. which is represented in
         taskMetadata.
      Returns information on the registered fact.

      Assumptions: cairoAuxInput is connected to the public input, which is verified by
      cairoVerifierContractAddresses.
      Guarantees: taskMetadata is consistent with the public memory, with some sanity checks.
    */
    function registerPublicMemoryMainPage(
        uint256[] memory taskMetadata,
        uint256[] memory cairoAuxInput
    ) internal returns (uint256 publicMemoryLength, uint256 memoryHash, uint256 prod) {
        uint256 nTasks = taskMetadata[0];
        require(nTasks < 2**30, "Invalid number of tasks.");

        // Public memory length.
        publicMemoryLength = (
            PROGRAM_SIZE + N_MAIN_ARGS + N_MAIN_RETURN_VALUES + /*Number of tasks cell*/1 +
            2 * nTasks);
        uint256[] memory publicMemory = new uint256[](
            N_WORDS_PER_PUBLIC_MEMORY_ENTRY * publicMemoryLength);

        uint256 offset = 0;

        // Write public memory, which is a list of pairs (address, value).
        {
        // Program segment.
        uint256[PROGRAM_SIZE] memory bootloaderProgram =
            bootloaderProgramContractAddress.getCompiledProgram();
        for (uint256 i = 0; i < bootloaderProgram.length; i++) {
            // Force that memory[i + INITIAL_PC] = bootloaderProgram[i].
            publicMemory[offset] = i + INITIAL_PC;
            publicMemory[offset + 1] = bootloaderProgram[i];
            offset += 2;
        }
        }

        {
        // Execution segment - main's arguments.
        uint256 executionBeginAddr = cairoAuxInput[OFFSET_EXECUTION_BEGIN_ADDR];
        publicMemory[offset + 0] = executionBeginAddr - 5;
        publicMemory[offset + 1] = cairoAuxInput[OFFSET_OUTPUT_BEGIN_ADDR];
        publicMemory[offset + 2] = executionBeginAddr - 4;
        publicMemory[offset + 3] = cairoAuxInput[OFFSET_PEDERSEN_BEGIN_ADDR];
        publicMemory[offset + 4] = executionBeginAddr - 3;
        publicMemory[offset + 5] = cairoAuxInput[OFFSET_RANGE_CHECK_BEGIN_ADDR];
        publicMemory[offset + 6] = executionBeginAddr - 2;
        publicMemory[offset + 7] = cairoAuxInput[OFFSET_ECDSA_BEGIN_ADDR];
        publicMemory[offset + 8] = executionBeginAddr - 1;
        publicMemory[offset + 9] = cairoAuxInput[OFFSET_CHECKPOINTS_BEGIN_PTR];
        offset += 10;
        }

        {
        // Execution segment - return values.
        uint256 executionStopPtr = cairoAuxInput[OFFSET_EXECUTION_STOP_PTR];
        publicMemory[offset + 0] = executionStopPtr - 5;
        publicMemory[offset + 1] = cairoAuxInput[OFFSET_OUTPUT_STOP_PTR];
        publicMemory[offset + 2] = executionStopPtr - 4;
        publicMemory[offset + 3] = cairoAuxInput[OFFSET_PEDERSEN_STOP_PTR];
        publicMemory[offset + 4] = executionStopPtr - 3;
        publicMemory[offset + 5] = cairoAuxInput[OFFSET_RANGE_CHECK_STOP_PTR];
        publicMemory[offset + 6] = executionStopPtr - 2;
        publicMemory[offset + 7] = cairoAuxInput[OFFSET_ECDSA_STOP_PTR];
        publicMemory[offset + 8] = executionStopPtr - 1;
        publicMemory[offset + 9] = cairoAuxInput[OFFSET_CHECKPOINTS_STOP_PTR];
        offset += 10;
        }

        // Program output.
        {
        // Check that there are enough range checks for the bootloader builtin validation.
        // Each builtin is validated for each task and each validation uses one range check.
        require(
            cairoAuxInput[OFFSET_RANGE_CHECK_STOP_PTR] >=
            cairoAuxInput[OFFSET_RANGE_CHECK_BEGIN_ADDR] + N_BUILTINS * nTasks,
            "Range-check stop pointer should be after all range checks used for validations.");
        // The checkpoint builtin is used once for each task, taking up two cells.
        require(
            cairoAuxInput[OFFSET_CHECKPOINTS_STOP_PTR] >=
            cairoAuxInput[OFFSET_CHECKPOINTS_BEGIN_PTR] + 2 * nTasks,
            "Number of checkpoints should be at least the number of tasks.");

        uint256 outputAddress = cairoAuxInput[OFFSET_OUTPUT_BEGIN_ADDR];
        // Force that memory[outputAddress] = nTasks.
        publicMemory[offset + 0] = outputAddress;
        publicMemory[offset + 1] = nTasks;
        offset += 2;
        outputAddress += 1;
        uint256 taskMetadataOffset = METADATA_TASKS_OFFSET;

        for (uint256 task = 0; task < nTasks; task++) {
            uint256 outputSize = taskMetadata[
                taskMetadataOffset + METADATA_OFFSET_TASK_OUTPUT_SIZE];
            require(2 <= outputSize && outputSize < 2**30, "Invalid task output size.");
            uint256 programHash = taskMetadata[
                taskMetadataOffset + METADATA_OFFSET_TASK_PROGRAM_HASH];
            uint256 nTreePairs = taskMetadata[
                taskMetadataOffset + METADATA_OFFSET_TASK_N_TREE_PAIRS];
            require(
                1 <= nTreePairs && nTreePairs < 2**20,
                "Invalid number of pairs in the Merkle tree structure.");
            // Force that memory[outputAddress] = outputSize.
            publicMemory[offset + 0] = outputAddress;
            publicMemory[offset + 1] = outputSize;
            // Force that memory[outputAddress + 1] = programHash.
            publicMemory[offset + 2] = outputAddress + 1;
            publicMemory[offset + 3] = programHash;
            offset += 4;
            outputAddress += outputSize;
            taskMetadataOffset += METADATA_TASK_HEADER_SIZE + 2 * nTreePairs;
        }
        require(taskMetadata.length == taskMetadataOffset, "Invalid length of taskMetadata.");

        require(
            cairoAuxInput[OFFSET_OUTPUT_STOP_PTR] == outputAddress,
            "Inconsistent program output length.");
        }

        require(publicMemory.length == offset, "Not all Cairo public inputs were written.");

        bytes32 factHash;
        (factHash, memoryHash, prod) = memoryPageFactRegistry.registerRegularMemoryPage(
            publicMemory,
            /*z=*/cairoAuxInput[cairoAuxInput.length - 2],
            /*alpha=*/cairoAuxInput[cairoAuxInput.length - 1],
            K_MODULUS);
    }
}

// File: Identity.sol



/*
  Copyright 2019,2020 StarkWare Industries Ltd.

  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

  https://www.starkware.co/open-source-license/

  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.
*/
// SPDX-License-Identifier: Apache-2.0.
pragma solidity ^0.6.11;

interface Identity {

    /*
      Allows a caller, typically another contract,
      to ensure that the provided address is of the expected type and version.
    */
    function identify()
        external pure
        returns(string memory);
}

// File: IFactRegistry.sol



/*
  Copyright 2019,2020 StarkWare Industries Ltd.

  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

  https://www.starkware.co/open-source-license/

  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.
*/
// SPDX-License-Identifier: Apache-2.0.
pragma solidity ^0.6.11;

/*
  The Fact Registry design pattern is a way to separate cryptographic verification from the
  business logic of the contract flow.

  A fact registry holds a hash table of verified "facts" which are represented by a hash of claims
  that the registry hash check and found valid. This table may be queried by accessing the
  isValid() function of the registry with a given hash.

  In addition, each fact registry exposes a registry specific function for submitting new claims
  together with their proofs. The information submitted varies from one registry to the other
  depending of the type of fact requiring verification.

  For further reading on the Fact Registry design pattern see this
  `StarkWare blog post <https://medium.com/starkware/the-fact-registry-a64aafb598b6>`_.
*/
interface IFactRegistry {
    /*
      Returns true if the given fact was previously registered in the contract.
    */
    function isValid(bytes32 fact)
        external view
        returns(bool);
}

// File: IQueryableFactRegistry.sol



/*
  Copyright 2019,2020 StarkWare Industries Ltd.

  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

  https://www.starkware.co/open-source-license/

  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.
*/
// SPDX-License-Identifier: Apache-2.0.
pragma solidity ^0.6.11;

import "IFactRegistry.sol";

/*
  Extends the IFactRegistry interface with a query method that indicates
  whether the fact registry has successfully registered any fact or is still empty of such facts.
*/
interface IQueryableFactRegistry is IFactRegistry {

    /*
      Returns true if at least one fact has been registered.
    */
    function hasRegisteredFact()
        external view
        returns(bool);

}

// File: MemoryPageFactRegistry.sol



/*
  Copyright 2019,2020 StarkWare Industries Ltd.

  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

  https://www.starkware.co/open-source-license/

  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.
*/
// SPDX-License-Identifier: Apache-2.0.
pragma solidity ^0.6.11;

import "FactRegistry.sol";

contract MemoryPageFactRegistryConstants {
    // A page based on a list of pairs (address, value).
    // In this case, memoryHash = hash(address, value, address, value, address, value, ...).
    uint256 internal constant REGULAR_PAGE = 0;
    // A page based on adjacent memory cells, starting from a given address.
    // In this case, memoryHash = hash(value, value, value, ...).
    uint256 internal constant CONTINUOUS_PAGE = 1;
}

/*
  A fact registry for the claim:
    I know n pairs (addr, value) for which the hash of the pairs is memoryHash, and the cumulative
    product: \prod_i( z - (addr_i + alpha * value_i) ) is prod.
  The exact format of the hash depends on the type of the page
  (see MemoryPageFactRegistryConstants).
  The fact consists of (pageType, prime, n, z, alpha, prod, memoryHash, address).
  Note that address is only available for CONTINUOUS_PAGE, and otherwise it is 0.
*/
contract MemoryPageFactRegistry is FactRegistry, MemoryPageFactRegistryConstants {
    event LogMemoryPageFactRegular(bytes32 factHash, uint256 memoryHash, uint256 prod);
    event LogMemoryPageFactContinuous(bytes32 factHash, uint256 memoryHash, uint256 prod);

    /*
      Registers a fact based of the given memory (address, value) pairs (REGULAR_PAGE).
    */
    function registerRegularMemoryPage(
        uint256[] calldata memoryPairs, uint256 z, uint256 alpha, uint256 prime)
        external returns (bytes32 factHash, uint256 memoryHash, uint256 prod)
    {
        require(memoryPairs.length < 2**20, "Too many memory values.");
        require(memoryPairs.length % 2 == 0, "Size of memoryPairs must be even.");
        require(z < prime, "Invalid value of z.");
        require(alpha < prime, "Invalid value of alpha.");
        (factHash, memoryHash, prod) = computeFactHash(memoryPairs, z, alpha, prime);
        emit LogMemoryPageFactRegular(factHash, memoryHash, prod);

        registerFact(factHash);
    }

    function computeFactHash(
        uint256[] memory memoryPairs, uint256 z, uint256 alpha, uint256 prime)
        internal pure returns (bytes32 factHash, uint256 memoryHash, uint256 prod) {
        uint256 memorySize = memoryPairs.length / 2;

        prod = 1;

        assembly {
            let memoryPtr := add(memoryPairs, 0x20)

            // Each value of memoryPairs is a pair: (address, value).
            let lastPtr := add(memoryPtr, mul(memorySize, 0x40))
            for { let ptr := memoryPtr } lt(ptr, lastPtr) { ptr := add(ptr, 0x40) } {
                // Compute address + alpha * value.
                let address_value_lin_comb := addmod(
                    /*address*/ mload(ptr),
                    mulmod(/*value*/ mload(add(ptr, 0x20)), alpha, prime),
                    prime)
                prod := mulmod(prod, add(z, sub(prime, address_value_lin_comb)), prime)
            }

            memoryHash := keccak256(memoryPtr, mul(/*0x20 * 2*/ 0x40, memorySize))
        }

        factHash = keccak256(
            abi.encodePacked(
                REGULAR_PAGE, prime, memorySize, z, alpha, prod, memoryHash, uint256(0))
        );
    }

    /*
      Registers a fact based on the given values, assuming continuous addresses.
      values should be [value at startAddr, value at (startAddr + 1), ...].
    */
    function registerContinuousMemoryPage(  // NOLINT: external-function.
        uint256 startAddr, uint256[] memory values, uint256 z, uint256 alpha, uint256 prime)
        public returns (bytes32 factHash, uint256 memoryHash, uint256 prod)
    {
        require(values.length < 2**20, "Too many memory values.");
        require(prime < 2**254, "prime is too big for the optimizations in this function.");
        require(z < prime, "Invalid value of z.");
        require(alpha < prime, "Invalid value of alpha.");
        require(startAddr < 2**64 && startAddr < prime, "Invalid value of startAddr.");

        uint256 nValues = values.length;

        assembly {
            // Initialize prod to 1.
            prod := 1
            // Initialize valuesPtr to point to the first value in the array.
            let valuesPtr := add(values, 0x20)

            let minus_z := mod(sub(prime, z), prime)

            // Start by processing full batches of 8 cells, addr represents the last address in each
            // batch.
            let addr := add(startAddr, 7)
            let lastAddr := add(startAddr, nValues)
            for {} lt(addr, lastAddr) { addr := add(addr, 8) } {
                // Compute the product of (lin_comb - z) instead of (z - lin_comb), since we're
                // doing an even number of iterations, the result is the same.
                prod :=
                    mulmod(prod,
                    mulmod(add(add(sub(addr, 7), mulmod(
                        mload(valuesPtr), alpha, prime)), minus_z),
                    add(add(sub(addr, 6), mulmod(
                        mload(add(valuesPtr, 0x20)), alpha, prime)), minus_z),
                    prime), prime)

                prod :=
                    mulmod(prod,
                    mulmod(add(add(sub(addr, 5), mulmod(
                        mload(add(valuesPtr, 0x40)), alpha, prime)), minus_z),
                    add(add(sub(addr, 4), mulmod(
                        mload(add(valuesPtr, 0x60)), alpha, prime)), minus_z),
                    prime), prime)

                prod :=
                    mulmod(prod,
                    mulmod(add(add(sub(addr, 3), mulmod(
                        mload(add(valuesPtr, 0x80)), alpha, prime)), minus_z),
                    add(add(sub(addr, 2), mulmod(
                        mload(add(valuesPtr, 0xa0)), alpha, prime)), minus_z),
                    prime), prime)

                prod :=
                    mulmod(prod,
                    mulmod(add(add(sub(addr, 1), mulmod(
                        mload(add(valuesPtr, 0xc0)), alpha, prime)), minus_z),
                    add(add(addr, mulmod(
                        mload(add(valuesPtr, 0xe0)), alpha, prime)), minus_z),
                    prime), prime)

                valuesPtr := add(valuesPtr, 0x100)
            }

            // Handle leftover.
            // Translate addr to the beginning of the last incomplete batch.
            addr := sub(addr, 7)
            for {} lt(addr, lastAddr) { addr := add(addr, 1) } {
                let address_value_lin_comb := addmod(
                    addr, mulmod(mload(valuesPtr), alpha, prime), prime)
                prod := mulmod(prod, add(z, sub(prime, address_value_lin_comb)), prime)
                valuesPtr := add(valuesPtr, 0x20)
            }

            memoryHash := keccak256(add(values, 0x20), mul(0x20, nValues))
        }

        factHash = keccak256(
            abi.encodePacked(
                CONTINUOUS_PAGE, prime, nValues, z, alpha, prod, memoryHash, startAddr)
        );

        emit LogMemoryPageFactContinuous(factHash, memoryHash, prod);

        registerFact(factHash);
    }
}

// File: PrimeFieldElement0.sol



/*
  Copyright 2019,2020 StarkWare Industries Ltd.

  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

  https://www.starkware.co/open-source-license/

  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.
*/
// SPDX-License-Identifier: Apache-2.0.
pragma solidity ^0.6.11;


contract PrimeFieldElement0 {
    uint256 constant internal K_MODULUS =
    0x800000000000011000000000000000000000000000000000000000000000001;
    uint256 constant internal K_MODULUS_MASK =
    0x0fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff;
    uint256 constant internal K_MONTGOMERY_R =
    0x7fffffffffffdf0ffffffffffffffffffffffffffffffffffffffffffffffe1;
    uint256 constant internal K_MONTGOMERY_R_INV =
    0x40000000000001100000000000012100000000000000000000000000000000;
    uint256 constant internal GENERATOR_VAL = 3;
    uint256 constant internal ONE_VAL = 1;
    uint256 constant internal GEN1024_VAL =
    0x659d83946a03edd72406af6711825f5653d9e35dc125289a206c054ec89c4f1;

    function fromMontgomery(uint256 val) internal pure returns (uint256 res) {
        // uint256 res = fmul(val, kMontgomeryRInv);
        assembly {
            res := mulmod(val,
                          0x40000000000001100000000000012100000000000000000000000000000000,
                          0x800000000000011000000000000000000000000000000000000000000000001)
        }
        return res;
    }

    function fromMontgomeryBytes(bytes32 bs) internal pure returns (uint256) {
        // Assuming bs is a 256bit bytes object, in Montgomery form, it is read into a field
        // element.
        uint256 res = uint256(bs);
        return fromMontgomery(res);
    }

    function toMontgomeryInt(uint256 val) internal pure returns (uint256 res) {
        //uint256 res = fmul(val, kMontgomeryR);
        assembly {
            res := mulmod(val,
                          0x7fffffffffffdf0ffffffffffffffffffffffffffffffffffffffffffffffe1,
                          0x800000000000011000000000000000000000000000000000000000000000001)
        }
        return res;
    }

    function fmul(uint256 a, uint256 b) internal pure returns (uint256 res) {
        //uint256 res = mulmod(a, b, kModulus);
        assembly {
            res := mulmod(a, b,
                0x800000000000011000000000000000000000000000000000000000000000001)
        }
        return res;
    }

    function fadd(uint256 a, uint256 b) internal pure returns (uint256 res) {
        // uint256 res = addmod(a, b, kModulus);
        assembly {
            res := addmod(a, b,
                0x800000000000011000000000000000000000000000000000000000000000001)
        }
        return res;
    }

    function fsub(uint256 a, uint256 b) internal pure returns (uint256 res) {
        // uint256 res = addmod(a, kModulus - b, kModulus);
        assembly {
            res := addmod(
                a,
                sub(0x800000000000011000000000000000000000000000000000000000000000001, b),
                0x800000000000011000000000000000000000000000000000000000000000001)
        }
        return res;
    }

    function fpow(uint256 val, uint256 exp) internal view returns (uint256) {
        return expmod(val, exp, K_MODULUS);
    }

    function expmod(uint256 base, uint256 exponent, uint256 modulus)
        internal view returns (uint256 res)
    {
        assembly {
            let p := mload(0x40)
            mstore(p, 0x20)                  // Length of Base.
            mstore(add(p, 0x20), 0x20)       // Length of Exponent.
            mstore(add(p, 0x40), 0x20)       // Length of Modulus.
            mstore(add(p, 0x60), base)       // Base.
            mstore(add(p, 0x80), exponent)   // Exponent.
            mstore(add(p, 0xa0), modulus)    // Modulus.
            // Call modexp precompile.
            if iszero(staticcall(gas(), 0x05, p, 0xc0, p, 0x20)) {
                revert(0, 0)
            }
            res := mload(p)
        }
    }

    function inverse(uint256 val) internal view returns (uint256) {
        return expmod(val, K_MODULUS - 2, K_MODULUS);
    }
}