/*
  Copyright 2019-2022 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.12;

contract CairoBootloaderProgramSize {
    uint256 internal constant PROGRAM_SIZE = 542;
}

contract CairoBootloaderProgram is CairoBootloaderProgramSize {
    function getCompiledProgram()
        external pure
        returns (uint256[PROGRAM_SIZE] memory)
    {
        return [
            290341444919459839,
            6,
            1226245742482522112,
            372,
            74168662805676031,
            0,
            2345108766317314046,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020480,
            5198420613823102976,
            3618502788666131213697322783095070105623107215331596699973092056135872020479,
            2345108766317314046,
            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,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020449,
            5191102234363920384,
            5191102238658887680,
            5191102242953854976,
            5198420613822906368,
            70,
            5189976364521848832,
            6,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020446,
            4623648689905041407,
            291467327646433279,
            2345108766317314046,
            5199827962936983548,
            5208553695804948479,
            4612389708016287743,
            5198983563776262144,
            1,
            2345108766317314046,
            146226256843603965,
            4,
            5191102230068953088,
            2345108766317314046,
            5191102230068953088,
            5188850460319711232,
            5188850460319776768,
            5188850460319842304,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020467,
            5198983563776262144,
            1,
            5198983563776327680,
            1,
            5198983563776393216,
            1,
            5198983563776458752,
            3618502788666131213697322783095070105623107215331596699973092056135872020480,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020463,
            2345108766317314046,
            5188850460319907840,
            5202361254907052032,
            5191102242953854976,
            5188287510366552064,
            5188287506071519232,
            5188287510366486527,
            4611826762357964797,
            5198420613822906368,
            3618502788666131213697322783095070105623107215331596699973092056135872020480,
            5198420613822906368,
            3,
            5188287518956224512,
            4623085744246521853,
            145944781866893308,
            3618502788666131213697322783095070105623107215331596699973092056135872020472,
            2345108766317314046,
            290341444919459839,
            20,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020390,
            4617174774030761984,
            4612671182992998402,
            5189976364521848832,
            0,
            4612389712311713791,
            5188850464614678528,
            5191102264428691456,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020454,
            4612389712311779327,
            4622804286450008067,
            4,
            4612671195878359044,
            5200109476568596480,
            5188850468910104576,
            4625619027626983429,
            4622804286450073606,
            2,
            4617174765440827399,
            4612671191582933000,
            4612671195877900297,
            4612671200172867594,
            4612671204467834891,
            5191102242953854976,
            5198983563776655360,
            6,
            5191102273018626048,
            5191102277313593344,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020392,
            1191342862550269952,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020358,
            4623648724265762815,
            5191102242953854976,
            5198983563776655360,
            13,
            5191102273018626048,
            5191102311673331712,
            5189976364521848832,
            6,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020353,
            4623648719970271231,
            5191102238658887680,
            5198983563776655360,
            6,
            5198983563776655360,
            13,
            5191102247248822272,
            5189976364521848832,
            6,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020388,
            4623930190652997645,
            4612671182993522707,
            5198983563776655360,
            13,
            5193354051357474816,
            2345108766317314046,
            290341444919459839,
            20,
            4622804286449418241,
            1,
            4614922952742240258,
            4614922982807011331,
            4614922961332174852,
            4614922965627142149,
            4614922969922109446,
            4613797087195136007,
            122550255383924,
            4613797087195136008,
            8098989891770344814,
            4613797087195136009,
            138277649577220228665140075,
            4613797087195136010,
            435459224417,
            4613797087195136011,
            27700496658166629,
            4613797087195136012,
            435458895728,
            4613797087195136013,
            1,
            4613797087195136014,
            3,
            4613797087195136015,
            1,
            4613797087195136016,
            2,
            4613797087195136017,
            5,
            4613797087195136018,
            7,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020295,
            5198420613823102976,
            1,
            5191102234363920384,
            5198420613822971904,
            7,
            5198420613822906368,
            13,
            5188850460319580160,
            1226245742482522112,
            33,
            4614641507830300671,
            4617174774030762003,
            5188850468911284224,
            5201798300658860031,
            5189976364521848832,
            64,
            1226245742482522112,
            9,
            5188850460321349632,
            5188850464616316928,
            5188850468911284224,
            5188850473206251520,
            5188850477501218816,
            5188850481796186112,
            2345108766317314046,
            146226256843603965,
            5,
            4613797087195135996,
            0,
            2345108766317314046,
            290341444919459839,
            1,
            5201798304953761792,
            5202079779930537980,
            4634344751905079295,
            5193354047062507520,
            5198983563776458752,
            3618502788666131213697322783095070105623107215331596699973092056135872020480,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020468,
            2345108766317314046,
            146226256843603965,
            5,
            5191102230068953088,
            5191102234363920384,
            2345108766317314046,
            5191102230068953088,
            5191102234363920384,
            5191102238658887680,
            5191102242953854976,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020332,
            5191102238658887680,
            5191102242953854976,
            5198983563776458752,
            3618502788666131213697322783095070105623107215331596699973092056135872020480,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020466,
            2345108766317314046,
            4612671182993129469,
            5198983563776393216,
            1,
            2345108766317314046,
            5191102238658887680,
            5199827967231950845,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020475,
            2345108766317314046,
            5191102238658887680,
            5191102242953854976,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020470,
            5191102242953854976,
            5191102247248822272,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020470,
            2345108766317314046,
            290341444919459839,
            1,
            5191102230068953088,
            5191102260133724160,
            5198983563776393216,
            3618502788666131213697322783095070105623107215331596699973092056135872020480,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020466,
            5209116658642944000,
            5202361254906855424,
            4612108233039904765,
            5193354047062507520,
            5193354051357474816,
            2345108766317314046,
            4612671182993063932,
            4612671187288031229,
            5198983563776327680,
            3,
            5188850468909711360,
            2345108766317314046,
            290341444919459839,
            2,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020194,
            4613797087195136000,
            0,
            4613797087195136001,
            0,
            5193354051357474816,
            2345108766317314046,
            290341444919459839,
            2,
            5191102234363920384,
            5191102242953854976,
            5191102247248822272,
            5188850460319776768,
            1226245742482522112,
            16,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020178,
            4617174769735794688,
            5188850464614744064,
            4623367219223429121,
            5193354038472572928,
            5193354042767540224,
            2345108766317314046,
            5191102242953854976,
            5188850460319907840,
            5188850464614875136,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020446,
            2345108766317314046,
            146226256843603964,
            5,
            5191102234363920384,
            5191102247248822272,
            2345108766317314046,
            290341444919459839,
            1,
            5198983563776393216,
            3618502788666131213697322783095070105623107215331596699973092056135872020480,
            4626181977580208128,
            5191102238658887680,
            5191102234363920384,
            5191102247248822272,
            5202079771340603392,
            4611826758063063038,
            5188287510366420992,
            4611826762357964799,
            5198420613822906368,
            1,
            5198420613822906368,
            3,
            5188287518956224512,
            145944781866893307,
            3618502788666131213697322783095070105623107215331596699973092056135872020472,
            2345108766317314046,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020424,
            5191102238658887680,
            5193354051357474816,
            5191102242953854976,
            5191102247248822272,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020428,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020442,
            2345108766317314046,
            146226256843603965,
            3,
            2345108766317314046,
            5191102238658887680,
            5191102242953854976,
            5188287510366617600,
            4611826758063063039,
            5198420613823037441,
            1,
            5198420613823037441,
            1,
            722405534170316798,
            3618502788666131213697322783095070105623107215331596699973092056135872020475,
            4623648689905041407,
            2345108766317314046,
            290341444919459839,
            8,
            5191102260133724160,
            5191102230068953088,
            5191102234363920384,
            5191102238658887680,
            5191102242953854976,
            5191102247248822272,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020258,
            4617174765440827393,
            4617174769735794690,
            4617174774030761987,
            4617174778325729284,
            4617174756850892805,
            5191102225773985792,
            5193354034177605632,
            5191102285903527936,
            1226245742482522112,
            62,
            4617174774030761991,
            5198420613823102976,
            1,
            5193354051357474816,
            5191102264428691456,
            5189976364521848832,
            0,
            5198983563776655360,
            1,
            5191102285903527936,
            5188850460320104448,
            1226245742482522112,
            11,
            4617174778325729285,
            4612389708017139710,
            5193354038472572928,
            5193354038472572928,
            5193354038472572928,
            5191102268723658752,
            5191102273018626048,
            5191102277313593344,
            2345108766317314046,
            146226256843603965,
            8,
            5191102221479018496,
            5191102225773985792,
            5191102230068953088,
            5191102234363920384,
            5191102238658887680,
            2345108766317314046,
            290341444919459839,
            0,
            290341444919459839,
            1,
            145944781866893311,
            12,
            5191102221479018496,
            5191102225773985792,
            5191102230068953088,
            5191102234363920384,
            5191102238658887680,
            5191102242953854976,
            1226245742482522112,
            34,
            74168662805676031,
            10,
            5191102221479018496,
            5191102225773985792,
            5191102230068953088,
            5191102234363920384,
            5191102238658887680,
            5191102242953854976,
            1226245742482522112,
            68,
            5191102242953854976,
            5198983563776458752,
            3618502788666131213697322783095070105623107215331596699973092056135872020480,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020446,
            2345108766317314046,
            5188850460319907840,
            4612389708016353279,
            5191102242953854976,
            5188850468909842432,
            5188850464614875136,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020370,
            4612389712311320575,
            5198983563776327680,
            2,
            5193354047062507520,
            2345108766317314046,
            5198983563776458752,
            2,
            5191102247248822272,
            2345108766317314046,
            290341444919459839,
            4,
            5191102230068953088,
            5191102260133724160,
            5191102264428691456,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020354,
            5191102242953854976,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020469,
            5189976364521848832,
            4,
            4611826758063128575,
            5191102234363920384,
            5188850468909842432,
            5189976364521848832,
            1,
            5188850464614875136,
            5188287514661257216,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020263,
            5188850460319907840,
            4611826758060965887,
            4611826762355933145,
            4622241336494227458,
            2,
            4614922982807011331,
            5191102225773985792,
            5193353883853750272,
            5193354038472572928,
            5191102238658887680,
            5198983563776655360,
            1,
            5191102247248822272,
            5188850460320104448,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020392,
            4623648711380271103,
            5193354038472572928,
            5193354038472572928,
            5193354038472572928,
            5193354038472572928,
            5191102268723658752,
            2345108766317314046,
            290341444919459839,
            2,
            5191102242953854976,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020430,
            4617174774030761984,
            5188287510366617600,
            4612389708016156671,
            5188287514661519360,
            4612389712311123967,
            5188287510366486528,
            4622241336496455681,
            3618502788666131213697322783095070105623107215331596699973092056135872020479,
            5198983563776131072,
            2,
            5191102260133724160,
            5191102264428691456,
            1226245742482522112,
            3618502788666131213697322783095070105623107215331596699973092056135872020309,
            5198983563776131072,
            2,
            5199546513730011136,
            5191102230068953088,
            5191102234363920384,
            5198983563776327680,
            1,
            5200109463683497984,
            2345108766317314046
        ];
    }
}
// ---------- End of auto-generated code. ----------

/*
  Copyright 2019-2022 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.12;

abstract contract CairoVerifierContract {
    function verifyProofExternal(
        uint256[] calldata proofParams,
        uint256[] calldata proof,
        uint256[] calldata publicInput
    ) external virtual;

    /*
      Returns information that is related to the layout.

      publicMemoryOffset is the offset of the public memory pages' information in the public input.
      selectedBuiltins is a bit-map of builtins that are present in the layout.
    */
    function getLayoutInfo()
        external
        pure
        virtual
        returns (uint256 publicMemoryOffset, uint256 selectedBuiltins);

    uint256 internal constant OUTPUT_BUILTIN_BIT = 0;
    uint256 internal constant PEDERSEN_BUILTIN_BIT = 1;
    uint256 internal constant RANGE_CHECK_BUILTIN_BIT = 2;
    uint256 internal constant ECDSA_BUILTIN_BIT = 3;
    uint256 internal constant BITWISE_BUILTIN_BIT = 4;
    uint256 internal constant EC_OP_BUILTIN_BIT = 5;
}

/*
  Copyright 2019-2022 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.12;

import "PageInfo.sol";

contract CpuPublicInputOffsetsBase is PageInfo {
    // 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;

    // The program segment starts from 1, so that memory address 0 is kept for the null pointer.
    uint256 internal constant INITIAL_PC = 1;
    // The first Cairo instructions are:
    //   ap += n_args; call main; jmp rel 0.
    // As the first two instructions occupy 2 cells each, the "jmp rel 0" instruction is at
    // offset 4 relative to INITIAL_PC.
    uint256 internal constant FINAL_PC = INITIAL_PC + 4;
}

/*
  Copyright 2019-2022 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.12;

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 = false;

    /*
      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;
    }
}

/*
  Copyright 2019-2022 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.12;

import "FactRegistry.sol";
import "CpuPublicInputOffsetsBase.sol";

/*
  A utility contract to parse the GPS output.
  See registerGpsFacts for more details.
*/
contract GpsOutputParser is CpuPublicInputOffsetsBase, 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 program output fact together with the relevant continuous memory pages' hashes.
      The event is emitted for each registered fact.
    */
    event LogMemoryPagesHashes(bytes32 programOutputFact, 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 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 externally.
    */
    function registerGpsFacts(
        uint256[] calldata taskMetadata,
        uint256[] memory publicMemoryPages,
        uint256 outputStartAddress
    ) internal {
        uint256 totalNumPages = publicMemoryPages[0];

        // 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[](totalNumPages + 3);
        // Relative address to the beginning of the memory pages' hashes in the array.
        pageHashesLogData[1] = 0x40;

        uint256 taskMetadataOffset = METADATA_TASKS_OFFSET;

        // Skip the 5 first output cells which contain the bootloader config, 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 = outputStartAddress + 5;

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

        // Bound the size of the stack by the total number of pages.
        // TODO(lior, 15/04/2022): Get a better bound on the size of the stack.
        uint256[] memory nodeStack = new uint256[](NODE_STACK_ITEM_SIZE * totalNumPages);

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

        uint256[PAGE_INFO_SIZE] memory pageInfoPtr;
        assembly {
            // Skip the array length and the first page.
            pageInfoPtr := add(add(publicMemoryPages, 0x20), PAGE_INFO_SIZE_IN_BYTES)
        }

        // 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 nPages 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(
                        pageInfoPtr,
                        curAddr,
                        curOffset,
                        nodeStack,
                        nodeStackLen
                    );
                    pageHashesLogData[curPage - firstPageOfTask + 3] = pageHash;
                    curPage += 1;
                    nodeStackLen += 1;
                    curAddr += pageSize;
                    curOffset += pageSize;

                    assembly {
                        pageInfoPtr := add(pageInfoPtr, PAGE_INFO_SIZE_IN_BYTES)
                    }
                }

                // 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 programOutputFact = nodeStack[NODE_STACK_OFFSET_HASH];
            bytes32 fact = keccak256(abi.encode(programHash, programOutputFact));

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

            {
                // Log the output Merkle root with the hashes of the relevant 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 relevant for this fact.
                    let length := sub(curPage, firstPageOfTask)
                    mstore(buf, programOutputFact)
                    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(totalNumPages == 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[PAGE_INFO_SIZE] memory pageInfoPtr,
        uint256 curAddr,
        uint256 curOffset,
        uint256[] memory nodeStack,
        uint256 nodeStackLen
    ) private pure returns (uint256 pageSize, uint256 pageHash) {
        // Read the first address, page size and hash.
        uint256 pageAddr = pageInfoPtr[PAGE_INFO_ADDRESS_OFFSET];
        pageSize = pageInfoPtr[PAGE_INFO_SIZE_OFFSET];
        pageHash = pageInfoPtr[PAGE_INFO_HASH_OFFSET];

        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;
    }

    /*
      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
    ) private 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;
    }
}

/*
  Copyright 2019-2022 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.12;

import "CairoBootloaderProgram.sol";
import "CairoVerifierContract.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_BUILTINS = 6;
    uint256 internal constant N_MAIN_ARGS = N_BUILTINS;
    uint256 internal constant N_MAIN_RETURN_VALUES = N_BUILTINS;
    // Cairo verifier program hash.
    uint256 immutable hashedSupportedCairoVerifiers_;
    // Simple bootloader program hash.
    uint256 immutable simpleBootloaderProgramHash_;

    /*
      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,
        uint256 hashedSupportedCairoVerifiers,
        uint256 simpleBootloaderProgramHash
    ) 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]);
        }
        hashedSupportedCairoVerifiers_ = hashedSupportedCairoVerifiers;
        simpleBootloaderProgramHash_ = simpleBootloaderProgramHash;
    }

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

    /*
      Returns the bootloader config.
    */
    function getBootloaderConfig() external view returns (uint256, uint256) {
        return (simpleBootloaderProgramHash_, hashedSupportedCairoVerifiers_);
    }

    /*
      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(
            cairoVerifierId < cairoVerifierContractAddresses.length,
            "cairoVerifierId is out of range."
        );
        CairoVerifierContract cairoVerifier = cairoVerifierContractAddresses[cairoVerifierId];

        // The values z and alpha are used only for the fact registration of the main page.
        // They are not part of the public input of CpuVerifier as they are computed there.
        // Take the relevant slice from 'cairoAuxInput'.
        uint256[] calldata cairoPublicInput = (
            cairoAuxInput[:cairoAuxInput.length -
                // z and alpha.
                2]
        );

        uint256[] memory publicMemoryPages;
        {
            (uint256 publicMemoryOffset, uint256 selectedBuiltins) = cairoVerifier.getLayoutInfo();

            require(cairoAuxInput.length > publicMemoryOffset, "Invalid cairoAuxInput length.");
            publicMemoryPages = (uint256[])(cairoPublicInput[publicMemoryOffset:]);
            uint256 nPages = publicMemoryPages[0];
            require(nPages < 10000, "Invalid nPages.");

            // Each page has a page info and a hash.
            require(
                publicMemoryPages.length == nPages * (PAGE_INFO_SIZE + 1),
                "Invalid publicMemoryPages length."
            );

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

            // 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 prover and the verifier on the bootloader program or bootloader config.
            require(
                publicMemoryPages[PAGE_INFO_SIZE_OFFSET] == publicMemoryLength,
                "Invalid size for memory page 0."
            );
            require(
                publicMemoryPages[PAGE_INFO_HASH_OFFSET] == memoryHash,
                "Invalid hash for memory page 0."
            );
            require(
                publicMemoryPages[nPages * PAGE_INFO_SIZE] == prod,
                "Invalid cumulative product for memory page 0."
            );
        }

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

        registerGpsFacts(taskMetadata, publicMemoryPages, cairoAuxInput[OFFSET_OUTPUT_BEGIN_ADDR]);
    }

    /*
      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.

      Arguments:
        selectedBuiltins: A bit-map of builtins that are present in the layout.
            See CairoVerifierContract.sol for more information.
        taskMetadata: Per task metadata.
        cairoAuxInput: Auxiliary input for the cairo verifier.

      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[] calldata taskMetadata,
        uint256[] calldata cairoAuxInput,
        uint256 selectedBuiltins
    )
        private
        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 +
            // return fp and pc =
            2 +
            N_MAIN_ARGS +
            N_MAIN_RETURN_VALUES +
            // Bootloader config size =
            2 +
            // Number of tasks cell =
            1 +
            2 *
            nTasks);
        uint256[] memory publicMemory = new uint256[](MEMORY_PAIR_SIZE * 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 - Make sure [initial_fp - 2] = initial_fp and .
            // This is required for the "safe call" feature (that is, all "call" instructions will
            // return, even if the called function is malicious).
            // It guarantees that it's not possible to create a cycle in the call stack.
            uint256 initialFp = cairoAuxInput[OFFSET_EXECUTION_BEGIN_ADDR];
            require(initialFp >= 2, "Invalid execution begin address.");
            publicMemory[offset + 0] = initialFp - 2;
            publicMemory[offset + 1] = initialFp;
            // Make sure [initial_fp - 1] = 0.
            publicMemory[offset + 2] = initialFp - 1;
            publicMemory[offset + 3] = 0;
            offset += 4;

            // Execution segment: Enforce main's arguments and return values.
            // Note that the page hash depends on the order of the (address, value) pair in the
            // publicMemory and consequently the arguments must be written before the return values.
            uint256 returnValuesAddress = cairoAuxInput[OFFSET_EXECUTION_STOP_PTR] - N_BUILTINS;
            uint256 builtinSegmentInfoOffset = OFFSET_OUTPUT_BEGIN_ADDR;

            for (uint256 i = 0; i < N_BUILTINS; i++) {
                // Write argument address.
                publicMemory[offset] = initialFp + i;
                uint256 returnValueOffset = offset + 2 * N_BUILTINS;

                // Write return value address.
                publicMemory[returnValueOffset] = returnValuesAddress + i;

                // Write values.
                if ((selectedBuiltins & 1) != 0) {
                    // Set the argument to the builtin start pointer.
                    publicMemory[offset + 1] = cairoAuxInput[builtinSegmentInfoOffset];
                    // Set the return value to the builtin stop pointer.
                    publicMemory[returnValueOffset + 1] = cairoAuxInput[
                        builtinSegmentInfoOffset + 1
                    ];
                    builtinSegmentInfoOffset += 2;
                } else {
                    // Builtin is not present in layout, set the argument value and return value to 0.
                    publicMemory[offset + 1] = 0;
                    publicMemory[returnValueOffset + 1] = 0;
                }
                offset += 2;
                selectedBuiltins >>= 1;
            }
            require(selectedBuiltins == 0, "SELECTED_BUILTINS_VECTOR_IS_TOO_LONG");
            // Skip the return values which were already written.
            offset += 2 * N_BUILTINS;
        }

        // Program output.
        {
            {
                uint256 outputAddress = cairoAuxInput[OFFSET_OUTPUT_BEGIN_ADDR];
                // Force that memory[outputAddress] and memory[outputAddress + 1] contain the
                // bootloader config (which is 2 words size).
                publicMemory[offset + 0] = outputAddress;
                publicMemory[offset + 1] = simpleBootloaderProgramHash_;
                publicMemory[offset + 2] = outputAddress + 1;
                publicMemory[offset + 3] = hashedSupportedCairoVerifiers_;
                // Force that memory[outputAddress + 2] = nTasks.
                publicMemory[offset + 4] = outputAddress + 2;
                publicMemory[offset + 5] = nTasks;
                offset += 6;
                outputAddress += 3;

                uint256[] calldata taskMetadataSlice = taskMetadata[METADATA_TASKS_OFFSET:];
                for (uint256 task = 0; task < nTasks; task++) {
                    uint256 outputSize = taskMetadataSlice[METADATA_OFFSET_TASK_OUTPUT_SIZE];
                    require(2 <= outputSize && outputSize < 2**30, "Invalid task output size.");
                    uint256 programHash = taskMetadataSlice[METADATA_OFFSET_TASK_PROGRAM_HASH];
                    uint256 nTreePairs = taskMetadataSlice[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;
                    taskMetadataSlice = taskMetadataSlice[METADATA_TASK_HEADER_SIZE +
                        2 *
                        nTreePairs:];
                }
                require(taskMetadataSlice.length == 0, "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.");

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

/*
  Copyright 2019-2022 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.12;

/*
  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);
}

/*
  Copyright 2019-2022 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.12;

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);
}

/*
  Copyright 2019-2022 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.12;

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

/*
  Copyright 2019-2022 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.12;

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
    )
        private
        pure
        returns (
            bytes32 factHash,
            uint256 memoryHash,
            uint256 prod
        )
    {
        uint256 memorySize = memoryPairs.length / 2; // NOLINT: divide-before-multiply.

        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);
    }
}

/*
  Copyright 2019-2022 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.12;

contract PageInfo {
    uint256 public constant PAGE_INFO_SIZE = 3;
    // PAGE_INFO_SIZE_IN_BYTES cannot reference PAGE_INFO_SIZE as only direct constants are
    // supported in assembly.
    uint256 public constant PAGE_INFO_SIZE_IN_BYTES = 3 * 32;

    uint256 public constant PAGE_INFO_ADDRESS_OFFSET = 0;
    uint256 public constant PAGE_INFO_SIZE_OFFSET = 1;
    uint256 public constant PAGE_INFO_HASH_OFFSET = 2;

    // A regular page entry is a (address, value) pair stored as 2 uint256 words.
    uint256 internal constant MEMORY_PAIR_SIZE = 2;
}

/*
  Copyright 2019-2022 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.12;

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

    function fromMontgomery(uint256 val) internal pure returns (uint256 res) {
        // uint256 res = fmul(val, kMontgomeryRInv);
        assembly {
            res := mulmod(val, K_MONTGOMERY_R_INV, K_MODULUS)
        }
        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, K_MONTGOMERY_R, K_MODULUS)
        }
        return res;
    }

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

    function fadd(uint256 a, uint256 b) internal pure returns (uint256 res) {
        // uint256 res = addmod(a, b, kModulus);
        assembly {
            res := addmod(a, b, K_MODULUS)
        }
        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(K_MODULUS, b), K_MODULUS)
        }
        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
    ) private 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);
    }
}

{
  "compilationTarget": {
    "GpsStatementVerifier.sol": "GpsStatementVerifier"
  },
  "evmVersion": "istanbul",
  "libraries": {},
  "metadata": {
    "bytecodeHash": "ipfs"
  },
  "optimizer": {
    "enabled": true,
    "runs": 1000000
  },
  "remappings": []
}