// File: contracts/V2_descriptor.sol



//	SPDX-License-Identifier: MIT

/// @title  ETHTerrestrials by Kye descriptor (v2)
/// @notice Image and traits stored on-chain and assembled by this contract

pragma solidity ^0.8.0;

import "./InflateLib.sol";
import "./Strings.sol";
import "./Base64.sol";
import "@0xsequence/sstore2/contracts/SSTORE2.sol";

interface Terraforms {
   function tokenSVG(uint256 tokenId) external view returns (string memory);
}

contract EthTerrestrialsV2Descriptor {
   using Strings for uint256;
   using InflateLib for bytes;

   /// @notice Storage entry for a trait type (category)
   struct TraitType {
      string name; //the name of the category (i.e., 'Clothes')
      uint16[] rarity; //the rarity table is mapped to each Trait in a TraitType and should be provided as an array of desired occurrences out of 1000 samples. E.g.: [500,200,200,100,100]. 0 rarity indicates that the trait will not occur naturally.
   }
   mapping(uint8 => TraitType) public traitTypes;
   /*   Note: Certain layers have only one trait - left in code for consistency/future projects
    *    0 position will be null for certain traits
    *   Trait Types:
    *   0: Background
    *   1: Hoodie Back
    *   2: Head Color
    *   3: Head Outline
    *   4: Ears
    *   5: Mouths
    *   6: Eyes
    *   7: Head Accessories
    *   8: Apparel
    *   9: Front
    */

   mapping(uint8 => bool) hiddentrait; //No need to display metadta for certain layers.

   /// @notice Storage entry for a single trait/custom token
   struct Trait {
      address imageStore; //SSTORE2 storage location for SVG image data, compressed using DEFLATE (python zlib). Header (first 2 bytes) and checksum (last 4 bytes) truncated.
      uint96 imagelen; //The length of the uncomressed image date (required for decompression).
      string name; //the name of the trait (i.e. "grey hoodie") or custom image.
   }

   /// @notice Storage entry for non-allowed trait combinations and rearranged traits
   struct TraitDescriptor {
      uint8 traitType;
      uint8 trait;
   }

   /// @notice Key: keccak hash of trait type and trait index for which there are non-allowed trait combinations
   mapping(bytes32 => TraitDescriptor[]) public traitExclusions;

   /// @notice Key: keccak hash of trait type and trait index that should be placed below any traits in list
   mapping(bytes32 => TraitDescriptor[]) public traitRearrangement;

   /// @notice A mapping of traits in the format traits[traitType][trait number]. The ordering of trait types corresponds to traitTypes (above).
   mapping(uint8 => mapping(uint8 => Trait)) public traits;

   /// @notice A mapping of custom tokenIds that contain custom tokens.
   mapping(uint256 => Trait) public customs;

   /// @notice Permanently seals the metadata in the contract from being modified by deployer.
   bool public contractsealed;

   string private SVGOpenTag =
      '<svg version="1.1" id="Layer_1" xmlns="http://www.w3.org/2000/svg" x="0" y="0" viewBox="0 0 1100 1100" style="enable-background:new 0 0 1100 1100" xml:space="preserve" xmlns:xlink="http://www.w3.org/1999/xlink">';

   address private deployer;

   Terraforms public terraforms = Terraforms(0x4E1f41613c9084FdB9E34E11fAE9412427480e56);

   modifier onlyDeployerWhileUnsealed() {
      require(!contractsealed && msg.sender == deployer, "Not authorized or locked");
      _;
   }

   constructor() public {
      deployer = msg.sender;
   }

   /*
.___  ___.  _______ .___________.    ___       _______       ___   .___________.    ___      
|   \/   | |   ____||           |   /   \     |       \     /   \  |           |   /   \     
|  \  /  | |  |__   `---|  |----`  /  ^  \    |  .--.  |   /  ^  \ `---|  |----`  /  ^  \    
|  |\/|  | |   __|      |  |      /  /_\  \   |  |  |  |  /  /_\  \    |  |      /  /_\  \   
|  |  |  | |  |____     |  |     /  _____  \  |  '--'  | /  _____  \   |  |     /  _____  \  
|__|  |__| |_______|    |__|    /__/     \__\ |_______/ /__/     \__\  |__|    /__/     \__\ 
*/

   /// @notice Returns an ERC721 standard tokenURI
   /// @param tokenId, the desired tokenId to display
   /// @param rawSeed, the raw seed code generated by the seeder contract following mint
   /// @param tokenType, the type of token (one of one or common)
   /// @return output, a base64 encoded JSON string containing the tokenURI (metadata and image)
   function generateTokenURI(
      uint256 tokenId,
      uint256 rawSeed,
      uint256 tokenType
   ) external view returns (string memory) {
      string memory name = string(abi.encodePacked("EtherTerrestrial #", tokenId.toString()));
      string memory description = "EtherTerrestrials are inter-dimensional Extra-Terrestrials who came to Earth's internet to infuse consciousness into all other pixelated Lifeforms. They can be encountered in the form of on-chain characters as interpreted by the existential explorer Kye."; //need to write
      string memory traits_json;
      string memory image;

      if (tokenType == 1) {
         //these tokens do not use a seed
         image = getSvgCustomToken(tokenId);
         traits_json = viewTraitsJSONCustom(tokenId);
      } else if (rawSeed == 0) {
         //if the seed is zero but not a one of one, the token must be unrevealed. Unrevealed image stored at custom index 69.
         image = getSvgCustomToken(69);
         description = "Unrevealed EtherTerrestrial - Refresh Soon";
         traits_json = "[]";
      } else {
         uint8[10] memory seed = processRawSeed(rawSeed);
         image = getSvgFromSeed(seed);
         traits_json = viewTraitsJSON(seed);
      }
      string memory json = Base64.encode(
         bytes(
            string(
               abi.encodePacked(
                  '{"name": "',
                  name,
                  '", "description": "',
                  description,
                  '", "attributes":',
                  traits_json,
                  ',"image": "',
                  "data:image/svg+xml;base64,",
                  Base64.encode(bytes(image)),
                  '"}'
               )
            )
         )
      );

      string memory output = string(abi.encodePacked("data:application/json;base64,", json));
      return output;
   }

   /// @notice Converts a raw seed code into a list of traits
   /// @param rawSeed, the raw seed code generated by the seeder contract following mint
   /// @return seed, a uint8 array containing the finally assigned trait codes for each trait type
   /// @dev For generative tokens, raw seeds are handled according to the following workflow:
   /// 	1. processRawSeed(): perform keccak operation over the raw seed and assign a rarity seed to each trait
   /// 	2. generateSeedFromRarityTables(): runs the results of processRawSeed over rarity tables to determine the traits
   ///   3. enforceRequiredCombinations(): ensures that certain traits are matched with, or prohibited from being matched with certain others.
   function processRawSeed(uint256 rawSeed) public view returns (uint8[10] memory) {
      uint16[10] memory initialSeed;

      for (uint8 i = 0; i < 10; i++) {
         initialSeed[i] = uint16(uint256(keccak256(abi.encodePacked(rawSeed, i))) % 1000);
      }
      uint8[10] memory seed = generateSeedFromRarityTables(initialSeed);
      seed = enforceRequiredCombinations(seed);
      return seed;
   }

   /// @notice Converts an initial rarity seed to a list of traits
   /// @param initialSeed, the initial rarity seed for a given token
   /// @return seed, a uint8 array containing the trait code for each traitType
   function generateSeedFromRarityTables(uint16[10] memory initialSeed) internal view returns (uint8[10] memory) {
      uint8[10] memory seed;
      for (uint8 traitType; traitType < 10; traitType++) {
         uint16[] memory rarityTable = traitTypes[traitType].rarity;
         uint16 upperBound;
         for (uint8 index; index < rarityTable.length; index++) {
            upperBound += rarityTable[index];
            if (initialSeed[traitType] < upperBound) {
               seed[traitType] = index;
               break;
            }
         }
      }
      return seed;
   }

   /// @notice Alters the seed to remove combinations that the artist has determined conflict with one another
   /// @param seed, the post-rarity allocated traits for a token
   /// @return the modified seed
   function enforceRequiredCombinations(uint8[10] memory seed) public view returns (uint8[10] memory) {
      for (uint8 i; i < seed.length; i++) {
         TraitDescriptor[] memory exclusions = traitExclusions[keccak256(abi.encodePacked(i, seed[i]))];
         // check to see if seed contains any trait combinations that are not allowed
         for (uint8 j = 0; j < exclusions.length; j++) {
            // seed has a trait combination that is not allowed, remove combination
            if (seed[exclusions[j].traitType] == exclusions[j].trait) {
               seed[exclusions[j].traitType] = 0;
            }
         }
      }

      // Exclude all of a type for some traits
      if (seed[6] == 6) {
         seed[7] = 0;
      } else if (seed[8] == 1) {
         seed[7] = 0;
      } else if (seed[8] == 7) {
         seed[7] = 0;
      } else if (seed[8] == 8) {
         seed[7] = 0;
      } else if (seed[8] == 9) {
         seed[7] = 0;
      }

      //Add hoodie back if hoodie
      if (seed[8] == 3 || seed[8] == 4 || seed[8] == 6) {
         seed[1] = 1;
      }

      return seed;
   }

   /// @notice Generates an ERC721 standard metadata JSON string for generative tokens
   /// @param seed, the finally allocated traits for a token
   /// @return json, a JSON metadata string
   function viewTraitsJSON(uint8[10] memory seed) public view returns (string memory) {
      string[] memory jsonItems = new string[](11);

      for (uint8 traitType; traitType < 10; traitType++) {
         if (!hiddentrait[traitType]) {
            uint8 traitCode = seed[traitType];
            string memory traitName = traits[traitType][traitCode].name;
            jsonItems[traitType] = string(
               abi.encodePacked(
                  traitType == 0 ? '[{"trait_type":"' : ',{"trait_type":"',
                  traitTypes[traitType].name,
                  '","value":"',
                  traitName,
                  '"}'
               )
            );
         }
      }
      jsonItems[10] = ',{"trait_type":"Life Form","value":"Tripped"}]';

      string memory json;
      for (uint256 i = 0; i < 11; i++) {
         json = string(abi.encodePacked(json, jsonItems[i]));
      }
      return json;
   }

   /// @notice Generates an ERC721 standard metadata JSON string for custom tokens
   /// @param tokenId, the desired tokenId
   /// @return a JSON metadata string
   function viewTraitsJSONCustom(uint256 tokenId) public view returns (string memory) {
      return
         string(
            abi.encodePacked(
               '[{"trait_type":"Cosmic Being","value":"',
               customs[tokenId].name,
               '"},{"trait_type":"Life Form","value":"Tripped"}]'
            )
         );
   }

   /// @notice Generates an unencoded SVG image for a given seed
   /// @param seed, the finally allocated traits for a token
   /// @return an SVG string
   function getSvgFromSeed(uint8[10] memory seed) public view returns (string memory) {
      string[20] memory SVG;

      uint8[20] memory arrangedSeed = getArrangedSeed(seed);
      for (uint8 i; i < arrangedSeed.length; i++) {
        uint8 traitType = arrangedSeed[i];
        // check that slot is not empty
        if (traitType != type(uint8).max) {
          uint8 traitCode = seed[traitType];
          string memory image = traits[traitType][traitCode].imagelen != 0 ? getTraitSVG(traitType, traitCode) : "";
          SVG[i] = image;
        }
      }

      string memory SVGStr;
      for (uint8 i; i < SVG.length; i++) {
         SVGStr = string(abi.encodePacked(SVGStr, SVG[i]));
      }
      return string(abi.encodePacked(SVGOpenTag, SVGStr, "</svg>"));
   }

    /// @notice Gets an arranged seed with the order of trait types to build the SVG
    /// @notice Only rearranges around one trait type (apparel)
    /// @param seed, unarranged seed
    /// @return arranged seed
    function getArrangedSeed(uint8[10] memory seed) public view returns (uint8[20] memory) {
      uint8[20] memory arrangedSeed;

      // initialize arrangedSeed with seed and max int
      for (uint8 i; i < arrangedSeed.length; i++) {
        if (i < seed.length) {
          arrangedSeed[i] = i;
        } else {
          // set extra slots for rearrangements to empty or max uint8
          arrangedSeed[i] = type(uint8).max;
        }
      }

      // rearrange arrangedSeed so certain items are placed ontop of apparel
      TraitDescriptor[] memory rearrangements = traitRearrangement[keccak256(abi.encodePacked(uint8(8), seed[8]))];
      for (uint8 i; i < rearrangements.length; i++) {
        // seed has a rearranagement so update arrangedSeed
        if (seed[rearrangements[i].traitType] == rearrangements[i].trait) {
          // place rearranged trait in its corresponding slot on top of apparel
          arrangedSeed[10 + rearrangements[i].traitType] = rearrangements[i].traitType;
          // trait has been moved so set this spot to empty
          arrangedSeed[rearrangements[i].traitType] = type(uint8).max;
        }
      }

      // Front trait is always on the top
      arrangedSeed[19] = 9;
      arrangedSeed[9] = type(uint8).max;

      return arrangedSeed;
   }

   /// @notice Returns the unencoded SVG image for a given seed
   /// @param tokenId, the tokenId of the custom token
   /// @return an SVG string
   /// @dev token 104's background is an onchain composition of Terraform #3640
   function getSvgCustomToken(uint256 tokenId) public view returns (string memory) {
      return
         string(
            abi.encodePacked(
               SVGOpenTag,
               tokenId == 104
                  ? '<defs><clipPath id="clipPath3"><circle cx="550" cy="550" r="500" /></clipPath></defs><g style="clip-path: url(#clipPath3);"><rect x="0" y="0" width="3000" height="3000" style="stroke: none; fill:none; clip-path: url(#clipPath3);" /><g xmlns="http://www.w3.org/2000/svg" transform="scale(1.51,1) translate(-178)">'
                  : "",
               tokenId == 104 ? terraforms.tokenSVG(3640) : "",
               tokenId == 104 ? "</g></g>" : "",
               decompress(SSTORE2.read(customs[tokenId].imageStore), customs[tokenId].imagelen),
               "</svg>"
            )
         );
   }

   function getTraitSVG(uint8 traitType, uint8 traitCode) public view returns (string memory) {
      return decompress(SSTORE2.read(traits[traitType][traitCode].imageStore), traits[traitType][traitCode].imagelen);
   }

   function decompress(bytes memory input, uint256 len) public pure returns (string memory) {
      (, bytes memory decompressed) = InflateLib.puff(input, len);
      return string(decompressed);
   }

   /*
 _______   _______ .______    __        ______   ____    ____  _______ .______      
|       \ |   ____||   _  \  |  |      /  __  \  \   \  /   / |   ____||   _  \     
|  .--.  ||  |__   |  |_)  | |  |     |  |  |  |  \   \/   /  |  |__   |  |_)  |    
|  |  |  ||   __|  |   ___/  |  |     |  |  |  |   \_    _/   |   __|  |      /     
|  '--'  ||  |____ |  |      |  `----.|  `--'  |     |  |     |  |____ |  |\  \----.
|_______/ |_______|| _|      |_______| \______/      |__|     |_______|| _| `._____|
                                                                                                                                                
*/

   /// @notice Establishes the 10 traitTypes
   function setTraitTypes(TraitType[] memory _traitTypes) external onlyDeployerWhileUnsealed {
      for (uint8 i; i < 10; i++) {
         traitTypes[i] = _traitTypes[i];
      }
   }

   /// @notice Establishes traits for a single traitType
   /// @dev Images stored previously via SSTORE2 in prior deployment of this contract (prior to repairing rearrangement logic) address 0xf30448d4cff17e02656fc6575c4c64417191adbc
   function setTraits(
      uint8 _traitType,
      Trait[] memory _traits,
      uint8[] memory _traitNumber
   ) external onlyDeployerWhileUnsealed {
      require(_traits.length == _traitNumber.length);
      for (uint8 i; i < _traits.length; i++) {
         traits[_traitType][_traitNumber[i]] = _traits[i];
      }
   }

   function setHiddenTraits(uint8[] memory _traitTypes, bool _hidden) external onlyDeployerWhileUnsealed {
      for (uint8 i; i < _traitTypes.length; i++) hiddentrait[_traitTypes[i]] = _hidden;
   }

   /// @notice Establishes the custom token art
   /// @dev Images stored previously via SSTORE2 in prior deployment of this contract (prior to repairing rearrangement logic) address 0xf30448d4cff17e02656fc6575c4c64417191adbc
   function setCustom(
      uint256[] memory _tokenIds,
      Trait[] memory _oneOfOnes
   ) external onlyDeployerWhileUnsealed {
      require(_tokenIds.length == _oneOfOnes.length);
      for (uint256 i; i < _oneOfOnes.length; i++) {
         customs[_tokenIds[i]] = _oneOfOnes[i];
      }
   }

   /// @notice Set a trait exclusion rule
   /// @param traitType, the trait type index
   /// @param trait, the trait index
   /// @param exclusions, all unallowed combinations
   function setTraitExclusions(
      uint8 traitType,
      uint8 trait,
      TraitDescriptor[] memory exclusions
   ) external onlyDeployerWhileUnsealed {
      bytes32 traitHash = keccak256(abi.encodePacked(traitType, trait));
      delete traitExclusions[traitHash];
      for (uint8 i = 0; i < exclusions.length; i++) {
         traitExclusions[traitHash].push(exclusions[i]);
      }
   }

   /// @notice Set a trait rearrangement rule
   /// @param traitType, the trait type index
   /// @param trait, the trait index
   /// @param rearrangements, all traits that should be placed above base trait
   function setTraitRearrangements(
      uint8 traitType,
      uint8 trait,
      TraitDescriptor[] memory rearrangements
   ) external onlyDeployerWhileUnsealed {
      bytes32 traitHash = keccak256(abi.encodePacked(traitType, trait));
      delete traitRearrangement[traitHash];
      for (uint8 i = 0; i < rearrangements.length; i++) {
         traitRearrangement[traitHash].push(rearrangements[i]);
      }
   }

   /// @notice IRREVERSIBLY SEALS THE CONTRACT FROM BEING MODIFIED
   function sealContract() external onlyDeployerWhileUnsealed {
      contractsealed = true;
   }
}

// File: contracts/InflateLib.sol



// SPDX-License-Identifier: Apache-2.0
pragma solidity >=0.8.0 <0.9.0;

/// https://github.com/adlerjohn/inflate-sol
/// @notice Based on https://github.com/madler/zlib/blob/master/contrib/puff
library InflateLib {
   // Maximum bits in a code
   uint256 constant MAXBITS = 15;
   // Maximum number of literal/length codes
   uint256 constant MAXLCODES = 286;
   // Maximum number of distance codes
   uint256 constant MAXDCODES = 30;
   // Maximum codes lengths to read
   uint256 constant MAXCODES = (MAXLCODES + MAXDCODES);
   // Number of fixed literal/length codes
   uint256 constant FIXLCODES = 288;

   // Error codes
   enum ErrorCode {
      ERR_NONE, // 0 successful inflate
      ERR_NOT_TERMINATED, // 1 available inflate data did not terminate
      ERR_OUTPUT_EXHAUSTED, // 2 output space exhausted before completing inflate
      ERR_INVALID_BLOCK_TYPE, // 3 invalid block type (type == 3)
      ERR_STORED_LENGTH_NO_MATCH, // 4 stored block length did not match one's complement
      ERR_TOO_MANY_LENGTH_OR_DISTANCE_CODES, // 5 dynamic block code description: too many length or distance codes
      ERR_CODE_LENGTHS_CODES_INCOMPLETE, // 6 dynamic block code description: code lengths codes incomplete
      ERR_REPEAT_NO_FIRST_LENGTH, // 7 dynamic block code description: repeat lengths with no first length
      ERR_REPEAT_MORE, // 8 dynamic block code description: repeat more than specified lengths
      ERR_INVALID_LITERAL_LENGTH_CODE_LENGTHS, // 9 dynamic block code description: invalid literal/length code lengths
      ERR_INVALID_DISTANCE_CODE_LENGTHS, // 10 dynamic block code description: invalid distance code lengths
      ERR_MISSING_END_OF_BLOCK, // 11 dynamic block code description: missing end-of-block code
      ERR_INVALID_LENGTH_OR_DISTANCE_CODE, // 12 invalid literal/length or distance code in fixed or dynamic block
      ERR_DISTANCE_TOO_FAR, // 13 distance is too far back in fixed or dynamic block
      ERR_CONSTRUCT // 14 internal: error in construct()
   }

   // Input and output state
   struct State {
      //////////////////
      // Output state //
      //////////////////
      // Output buffer
      bytes output;
      // Bytes written to out so far
      uint256 outcnt;
      /////////////////
      // Input state //
      /////////////////
      // Input buffer
      bytes input;
      // Bytes read so far
      uint256 incnt;
      ////////////////
      // Temp state //
      ////////////////
      // Bit buffer
      uint256 bitbuf;
      // Number of bits in bit buffer
      uint256 bitcnt;
      //////////////////////////
      // Static Huffman codes //
      //////////////////////////
      Huffman lencode;
      Huffman distcode;
   }

   // Huffman code decoding tables
   struct Huffman {
      uint256[] counts;
      uint256[] symbols;
   }

   function bits(State memory s, uint256 need) private pure returns (ErrorCode, uint256) {
      // Bit accumulator (can use up to 20 bits)
      uint256 val;

      // Load at least need bits into val
      val = s.bitbuf;
      while (s.bitcnt < need) {
         if (s.incnt == s.input.length) {
            // Out of input
            return (ErrorCode.ERR_NOT_TERMINATED, 0);
         }

         // Load eight bits
         val |= uint256(uint8(s.input[s.incnt++])) << s.bitcnt;
         s.bitcnt += 8;
      }

      // Drop need bits and update buffer, always zero to seven bits left
      s.bitbuf = val >> need;
      s.bitcnt -= need;

      // Return need bits, zeroing the bits above that
      uint256 ret = (val & ((1 << need) - 1));
      return (ErrorCode.ERR_NONE, ret);
   }

   function _stored(State memory s) private pure returns (ErrorCode) {
      // Length of stored block
      uint256 len;

      // Discard leftover bits from current byte (assumes s.bitcnt < 8)
      s.bitbuf = 0;
      s.bitcnt = 0;

      // Get length and check against its one's complement
      if (s.incnt + 4 > s.input.length) {
         // Not enough input
         return ErrorCode.ERR_NOT_TERMINATED;
      }
      len = uint256(uint8(s.input[s.incnt++]));
      len |= uint256(uint8(s.input[s.incnt++])) << 8;

      if (uint8(s.input[s.incnt++]) != (~len & 0xFF) || uint8(s.input[s.incnt++]) != ((~len >> 8) & 0xFF)) {
         // Didn't match complement!
         return ErrorCode.ERR_STORED_LENGTH_NO_MATCH;
      }

      // Copy len bytes from in to out
      if (s.incnt + len > s.input.length) {
         // Not enough input
         return ErrorCode.ERR_NOT_TERMINATED;
      }
      if (s.outcnt + len > s.output.length) {
         // Not enough output space
         return ErrorCode.ERR_OUTPUT_EXHAUSTED;
      }
      while (len != 0) {
         // Note: Solidity reverts on underflow, so we decrement here
         len -= 1;
         s.output[s.outcnt++] = s.input[s.incnt++];
      }

      // Done with a valid stored block
      return ErrorCode.ERR_NONE;
   }

   function _decode(State memory s, Huffman memory h) private pure returns (ErrorCode, uint256) {
      // Current number of bits in code
      uint256 len;
      // Len bits being decoded
      uint256 code = 0;
      // First code of length len
      uint256 first = 0;
      // Number of codes of length len
      uint256 count;
      // Index of first code of length len in symbol table
      uint256 index = 0;
      // Error code
      ErrorCode err;

      for (len = 1; len <= MAXBITS; len++) {
         // Get next bit
         uint256 tempCode;
         (err, tempCode) = bits(s, 1);
         if (err != ErrorCode.ERR_NONE) {
            return (err, 0);
         }
         code |= tempCode;
         count = h.counts[len];

         // If length len, return symbol
         if (code < first + count) {
            return (ErrorCode.ERR_NONE, h.symbols[index + (code - first)]);
         }
         // Else update for next length
         index += count;
         first += count;
         first <<= 1;
         code <<= 1;
      }

      // Ran out of codes
      return (ErrorCode.ERR_INVALID_LENGTH_OR_DISTANCE_CODE, 0);
   }

   function _construct(
      Huffman memory h,
      uint256[] memory lengths,
      uint256 n,
      uint256 start
   ) private pure returns (ErrorCode) {
      // Current symbol when stepping through lengths[]
      uint256 symbol;
      // Current length when stepping through h.counts[]
      uint256 len;
      // Number of possible codes left of current length
      uint256 left;
      // Offsets in symbol table for each length
      uint256[MAXBITS + 1] memory offs;

      // Count number of codes of each length
      for (len = 0; len <= MAXBITS; len++) {
         h.counts[len] = 0;
      }
      for (symbol = 0; symbol < n; symbol++) {
         // Assumes lengths are within bounds
         h.counts[lengths[start + symbol]]++;
      }
      // No codes!
      if (h.counts[0] == n) {
         // Complete, but decode() will fail
         return (ErrorCode.ERR_NONE);
      }

      // Check for an over-subscribed or incomplete set of lengths

      // One possible code of zero length
      left = 1;

      for (len = 1; len <= MAXBITS; len++) {
         // One more bit, double codes left
         left <<= 1;
         if (left < h.counts[len]) {
            // Over-subscribed--return error
            return ErrorCode.ERR_CONSTRUCT;
         }
         // Deduct count from possible codes

         left -= h.counts[len];
      }

      // Generate offsets into symbol table for each length for sorting
      offs[1] = 0;
      for (len = 1; len < MAXBITS; len++) {
         offs[len + 1] = offs[len] + h.counts[len];
      }

      // Put symbols in table sorted by length, by symbol order within each length
      for (symbol = 0; symbol < n; symbol++) {
         if (lengths[start + symbol] != 0) {
            h.symbols[offs[lengths[start + symbol]]++] = symbol;
         }
      }

      // Left > 0 means incomplete
      return left > 0 ? ErrorCode.ERR_CONSTRUCT : ErrorCode.ERR_NONE;
   }

   function _codes(
      State memory s,
      Huffman memory lencode,
      Huffman memory distcode
   ) private pure returns (ErrorCode) {
      // Decoded symbol
      uint256 symbol;
      // Length for copy
      uint256 len;
      // Distance for copy
      uint256 dist;
      // TODO Solidity doesn't support constant arrays, but these are fixed at compile-time
      // Size base for length codes 257..285
      uint16[29] memory lens = [
         3,
         4,
         5,
         6,
         7,
         8,
         9,
         10,
         11,
         13,
         15,
         17,
         19,
         23,
         27,
         31,
         35,
         43,
         51,
         59,
         67,
         83,
         99,
         115,
         131,
         163,
         195,
         227,
         258
      ];
      // Extra bits for length codes 257..285
      uint8[29] memory lext = [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0];
      // Offset base for distance codes 0..29
      uint16[30] memory dists = [
         1,
         2,
         3,
         4,
         5,
         7,
         9,
         13,
         17,
         25,
         33,
         49,
         65,
         97,
         129,
         193,
         257,
         385,
         513,
         769,
         1025,
         1537,
         2049,
         3073,
         4097,
         6145,
         8193,
         12289,
         16385,
         24577
      ];
      // Extra bits for distance codes 0..29
      uint8[30] memory dext = [0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13];
      // Error code
      ErrorCode err;

      // Decode literals and length/distance pairs
      while (symbol != 256) {
         (err, symbol) = _decode(s, lencode);
         if (err != ErrorCode.ERR_NONE) {
            // Invalid symbol
            return err;
         }

         if (symbol < 256) {
            // Literal: symbol is the byte
            // Write out the literal
            if (s.outcnt == s.output.length) {
               return ErrorCode.ERR_OUTPUT_EXHAUSTED;
            }
            s.output[s.outcnt] = bytes1(uint8(symbol));
            s.outcnt++;
         } else if (symbol > 256) {
            uint256 tempBits;
            // Length
            // Get and compute length
            symbol -= 257;
            if (symbol >= 29) {
               // Invalid fixed code
               return ErrorCode.ERR_INVALID_LENGTH_OR_DISTANCE_CODE;
            }

            (err, tempBits) = bits(s, lext[symbol]);
            if (err != ErrorCode.ERR_NONE) {
               return err;
            }
            len = lens[symbol] + tempBits;

            // Get and check distance
            (err, symbol) = _decode(s, distcode);
            if (err != ErrorCode.ERR_NONE) {
               // Invalid symbol
               return err;
            }
            (err, tempBits) = bits(s, dext[symbol]);
            if (err != ErrorCode.ERR_NONE) {
               return err;
            }
            dist = dists[symbol] + tempBits;
            if (dist > s.outcnt) {
               // Distance too far back
               return ErrorCode.ERR_DISTANCE_TOO_FAR;
            }

            // Copy length bytes from distance bytes back
            if (s.outcnt + len > s.output.length) {
               return ErrorCode.ERR_OUTPUT_EXHAUSTED;
            }
            while (len != 0) {
               // Note: Solidity reverts on underflow, so we decrement here
               len -= 1;
               s.output[s.outcnt] = s.output[s.outcnt - dist];
               s.outcnt++;
            }
         } else {
            s.outcnt += len;
         }
      }

      // Done with a valid fixed or dynamic block
      return ErrorCode.ERR_NONE;
   }

   function _build_fixed(State memory s) private pure returns (ErrorCode) {
      // Build fixed Huffman tables
      // TODO this is all a compile-time constant
      uint256 symbol;
      uint256[] memory lengths = new uint256[](FIXLCODES);

      // Literal/length table
      for (symbol = 0; symbol < 144; symbol++) {
         lengths[symbol] = 8;
      }
      for (; symbol < 256; symbol++) {
         lengths[symbol] = 9;
      }
      for (; symbol < 280; symbol++) {
         lengths[symbol] = 7;
      }
      for (; symbol < FIXLCODES; symbol++) {
         lengths[symbol] = 8;
      }

      _construct(s.lencode, lengths, FIXLCODES, 0);

      // Distance table
      for (symbol = 0; symbol < MAXDCODES; symbol++) {
         lengths[symbol] = 5;
      }

      _construct(s.distcode, lengths, MAXDCODES, 0);

      return ErrorCode.ERR_NONE;
   }

   function _fixed(State memory s) private pure returns (ErrorCode) {
      // Decode data until end-of-block code
      return _codes(s, s.lencode, s.distcode);
   }

   function _build_dynamic_lengths(State memory s) private pure returns (ErrorCode, uint256[] memory) {
      uint256 ncode;
      // Index of lengths[]
      uint256 index;
      // Descriptor code lengths
      uint256[] memory lengths = new uint256[](MAXCODES);
      // Error code
      ErrorCode err;
      // Permutation of code length codes
      uint8[19] memory order = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15];

      (err, ncode) = bits(s, 4);
      if (err != ErrorCode.ERR_NONE) {
         return (err, lengths);
      }
      ncode += 4;

      // Read code length code lengths (really), missing lengths are zero
      for (index = 0; index < ncode; index++) {
         (err, lengths[order[index]]) = bits(s, 3);
         if (err != ErrorCode.ERR_NONE) {
            return (err, lengths);
         }
      }
      for (; index < 19; index++) {
         lengths[order[index]] = 0;
      }

      return (ErrorCode.ERR_NONE, lengths);
   }

   function _build_dynamic(State memory s)
      private
      pure
      returns (
         ErrorCode,
         Huffman memory,
         Huffman memory
      )
   {
      // Number of lengths in descriptor
      uint256 nlen;
      uint256 ndist;
      // Index of lengths[]
      uint256 index;
      // Error code
      ErrorCode err;
      // Descriptor code lengths
      uint256[] memory lengths = new uint256[](MAXCODES);
      // Length and distance codes
      Huffman memory lencode = Huffman(new uint256[](MAXBITS + 1), new uint256[](MAXLCODES));
      Huffman memory distcode = Huffman(new uint256[](MAXBITS + 1), new uint256[](MAXDCODES));
      uint256 tempBits;

      // Get number of lengths in each table, check lengths
      (err, nlen) = bits(s, 5);
      if (err != ErrorCode.ERR_NONE) {
         return (err, lencode, distcode);
      }
      nlen += 257;
      (err, ndist) = bits(s, 5);
      if (err != ErrorCode.ERR_NONE) {
         return (err, lencode, distcode);
      }
      ndist += 1;

      if (nlen > MAXLCODES || ndist > MAXDCODES) {
         // Bad counts
         return (ErrorCode.ERR_TOO_MANY_LENGTH_OR_DISTANCE_CODES, lencode, distcode);
      }

      (err, lengths) = _build_dynamic_lengths(s);
      if (err != ErrorCode.ERR_NONE) {
         return (err, lencode, distcode);
      }

      // Build huffman table for code lengths codes (use lencode temporarily)
      err = _construct(lencode, lengths, 19, 0);
      if (err != ErrorCode.ERR_NONE) {
         // Require complete code set here
         return (ErrorCode.ERR_CODE_LENGTHS_CODES_INCOMPLETE, lencode, distcode);
      }

      // Read length/literal and distance code length tables
      index = 0;
      while (index < nlen + ndist) {
         // Decoded value
         uint256 symbol;
         // Last length to repeat
         uint256 len;

         (err, symbol) = _decode(s, lencode);
         if (err != ErrorCode.ERR_NONE) {
            // Invalid symbol
            return (err, lencode, distcode);
         }

         if (symbol < 16) {
            // Length in 0..15
            lengths[index++] = symbol;
         } else {
            // Repeat instruction
            // Assume repeating zeros
            len = 0;
            if (symbol == 16) {
               // Repeat last length 3..6 times
               if (index == 0) {
                  // No last length!
                  return (ErrorCode.ERR_REPEAT_NO_FIRST_LENGTH, lencode, distcode);
               }
               // Last length
               len = lengths[index - 1];
               (err, tempBits) = bits(s, 2);
               if (err != ErrorCode.ERR_NONE) {
                  return (err, lencode, distcode);
               }
               symbol = 3 + tempBits;
            } else if (symbol == 17) {
               // Repeat zero 3..10 times
               (err, tempBits) = bits(s, 3);
               if (err != ErrorCode.ERR_NONE) {
                  return (err, lencode, distcode);
               }
               symbol = 3 + tempBits;
            } else {
               // == 18, repeat zero 11..138 times
               (err, tempBits) = bits(s, 7);
               if (err != ErrorCode.ERR_NONE) {
                  return (err, lencode, distcode);
               }
               symbol = 11 + tempBits;
            }

            if (index + symbol > nlen + ndist) {
               // Too many lengths!
               return (ErrorCode.ERR_REPEAT_MORE, lencode, distcode);
            }
            while (symbol != 0) {
               // Note: Solidity reverts on underflow, so we decrement here
               symbol -= 1;

               // Repeat last or zero symbol times
               lengths[index++] = len;
            }
         }
      }

      // Check for end-of-block code -- there better be one!
      if (lengths[256] == 0) {
         return (ErrorCode.ERR_MISSING_END_OF_BLOCK, lencode, distcode);
      }

      // Build huffman table for literal/length codes
      err = _construct(lencode, lengths, nlen, 0);
      if (
         err != ErrorCode.ERR_NONE &&
         (err == ErrorCode.ERR_NOT_TERMINATED || err == ErrorCode.ERR_OUTPUT_EXHAUSTED || nlen != lencode.counts[0] + lencode.counts[1])
      ) {
         // Incomplete code ok only for single length 1 code
         return (ErrorCode.ERR_INVALID_LITERAL_LENGTH_CODE_LENGTHS, lencode, distcode);
      }

      // Build huffman table for distance codes
      err = _construct(distcode, lengths, ndist, nlen);
      if (
         err != ErrorCode.ERR_NONE &&
         (err == ErrorCode.ERR_NOT_TERMINATED || err == ErrorCode.ERR_OUTPUT_EXHAUSTED || ndist != distcode.counts[0] + distcode.counts[1])
      ) {
         // Incomplete code ok only for single length 1 code
         return (ErrorCode.ERR_INVALID_DISTANCE_CODE_LENGTHS, lencode, distcode);
      }

      return (ErrorCode.ERR_NONE, lencode, distcode);
   }

   function _dynamic(State memory s) private pure returns (ErrorCode) {
      // Length and distance codes
      Huffman memory lencode;
      Huffman memory distcode;
      // Error code
      ErrorCode err;

      (err, lencode, distcode) = _build_dynamic(s);
      if (err != ErrorCode.ERR_NONE) {
         return err;
      }

      // Decode data until end-of-block code
      return _codes(s, lencode, distcode);
   }

   function puff(bytes memory source, uint256 destlen) internal pure returns (ErrorCode, bytes memory) {
      // Input/output state
      State memory s = State(
         new bytes(destlen),
         0,
         source,
         0,
         0,
         0,
         Huffman(new uint256[](MAXBITS + 1), new uint256[](FIXLCODES)),
         Huffman(new uint256[](MAXBITS + 1), new uint256[](MAXDCODES))
      );
      // Temp: last bit
      uint256 last;
      // Temp: block type bit
      uint256 t;
      // Error code
      ErrorCode err;

      // Build fixed Huffman tables
      err = _build_fixed(s);
      if (err != ErrorCode.ERR_NONE) {
         return (err, s.output);
      }

      // Process blocks until last block or error
      while (last == 0) {
         // One if last block
         (err, last) = bits(s, 1);
         if (err != ErrorCode.ERR_NONE) {
            return (err, s.output);
         }

         // Block type 0..3
         (err, t) = bits(s, 2);
         if (err != ErrorCode.ERR_NONE) {
            return (err, s.output);
         }

         err = (t == 0 ? _stored(s) : (t == 1 ? _fixed(s) : (t == 2 ? _dynamic(s) : ErrorCode.ERR_INVALID_BLOCK_TYPE)));
         // type == 3, invalid

         if (err != ErrorCode.ERR_NONE) {
            // Return with error
            break;
         }
      }

      return (err, s.output);
   }
}

// File: contracts/Strings.sol



library Strings {
   function toString(uint256 value) internal pure returns (string memory) {
      // Inspired by OraclizeAPI's implementation - MIT licence
      // https://github.com/oraclize/ethereum-api/blob/b42146b063c7d6ee1358846c198246239e9360e8/oraclizeAPI_0.4.25.sol

      if (value == 0) {
         return "0";
      }
      uint256 temp = value;
      uint256 digits;
      while (temp != 0) {
         digits++;
         temp /= 10;
      }
      bytes memory buffer = new bytes(digits);
      while (value != 0) {
         digits -= 1;
         buffer[digits] = bytes1(uint8(48 + uint256(value % 10)));
         value /= 10;
      }
      return string(buffer);
   }
}

// File: contracts/Base64.sol



// SPDX-License-Identifier: MIT
/// @title Base64
/// @notice Provides a function for encoding some bytes in base64
/// @author Brecht Devos <brecht@loopring.org>

library Base64 {
   string internal constant TABLE = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

   function encode(bytes memory data) internal pure returns (string memory) {
      if (data.length == 0) return "";

      // load the table into memory
      string memory table = TABLE;

      // multiply by 4/3 rounded up
      uint256 encodedLen = 4 * ((data.length + 2) / 3);

      // add some extra buffer at the end required for the writing
      string memory result = new string(encodedLen + 32);

      assembly {
         // set the actual output length
         mstore(result, encodedLen)

         // prepare the lookup table
         let tablePtr := add(table, 1)

         // input ptr
         let dataPtr := data
         let endPtr := add(dataPtr, mload(data))

         // result ptr, jump over length
         let resultPtr := add(result, 32)

         // run over the input, 3 bytes at a time
         for {

         } lt(dataPtr, endPtr) {

         } {
            dataPtr := add(dataPtr, 3)

            // read 3 bytes
            let input := mload(dataPtr)

            // write 4 characters
            mstore(resultPtr, shl(248, mload(add(tablePtr, and(shr(18, input), 0x3F)))))
            resultPtr := add(resultPtr, 1)
            mstore(resultPtr, shl(248, mload(add(tablePtr, and(shr(12, input), 0x3F)))))
            resultPtr := add(resultPtr, 1)
            mstore(resultPtr, shl(248, mload(add(tablePtr, and(shr(6, input), 0x3F)))))
            resultPtr := add(resultPtr, 1)
            mstore(resultPtr, shl(248, mload(add(tablePtr, and(input, 0x3F)))))
            resultPtr := add(resultPtr, 1)
         }

         // padding with '='
         switch mod(mload(data), 3)
         case 1 {
            mstore(sub(resultPtr, 2), shl(240, 0x3d3d))
         }
         case 2 {
            mstore(sub(resultPtr, 1), shl(248, 0x3d))
         }
      }

      return result;
   }
}

// File: @0xsequence/sstore2/contracts/SSTORE2.sol



// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import "./utils/Bytecode.sol";

/**
  @title A key-value storage with auto-generated keys for storing chunks of data with a lower write & read cost.
  @author Agustin Aguilar <aa@horizon.io>

  Readme: https://github.com/0xsequence/sstore2#readme
*/
library SSTORE2 {
  error WriteError();

  /**
    @notice Stores `_data` and returns `pointer` as key for later retrieval
    @dev The pointer is a contract address with `_data` as code
    @param _data to be written
    @return pointer Pointer to the written `_data`
  */
  function write(bytes memory _data) internal returns (address pointer) {
    // Append 00 to _data so contract can't be called
    // Build init code
    bytes memory code = Bytecode.creationCodeFor(
      abi.encodePacked(
        hex'00',
        _data
      )
    );

    // Deploy contract using create
    assembly { pointer := create(0, add(code, 32), mload(code)) }

    // Address MUST be non-zero
    if (pointer == address(0)) revert WriteError();
  }

  /**
    @notice Reads the contents of the `_pointer` code as data, skips the first byte 
    @dev The function is intended for reading pointers generated by `write`
    @param _pointer to be read
    @return data read from `_pointer` contract
  */
  function read(address _pointer) internal view returns (bytes memory) {
    return Bytecode.codeAt(_pointer, 1, type(uint256).max);
  }

  /**
    @notice Reads the contents of the `_pointer` code as data, skips the first byte 
    @dev The function is intended for reading pointers generated by `write`
    @param _pointer to be read
    @param _start number of bytes to skip
    @return data read from `_pointer` contract
  */
  function read(address _pointer, uint256 _start) internal view returns (bytes memory) {
    return Bytecode.codeAt(_pointer, _start + 1, type(uint256).max);
  }

  /**
    @notice Reads the contents of the `_pointer` code as data, skips the first byte 
    @dev The function is intended for reading pointers generated by `write`
    @param _pointer to be read
    @param _start number of bytes to skip
    @param _end index before which to end extraction
    @return data read from `_pointer` contract
  */
  function read(address _pointer, uint256 _start, uint256 _end) internal view returns (bytes memory) {
    return Bytecode.codeAt(_pointer, _start + 1, _end + 1);
  }
}

// File: @0xsequence/sstore2/contracts/utils/Bytecode.sol



// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;


library Bytecode {
  error InvalidCodeAtRange(uint256 _size, uint256 _start, uint256 _end);

  /**
    @notice Generate a creation code that results on a contract with `_code` as bytecode
    @param _code The returning value of the resulting `creationCode`
    @return creationCode (constructor) for new contract
  */
  function creationCodeFor(bytes memory _code) internal pure returns (bytes memory) {
    /*
      0x00    0x63         0x63XXXXXX  PUSH4 _code.length  size
      0x01    0x80         0x80        DUP1                size size
      0x02    0x60         0x600e      PUSH1 14            14 size size
      0x03    0x60         0x6000      PUSH1 00            0 14 size size
      0x04    0x39         0x39        CODECOPY            size
      0x05    0x60         0x6000      PUSH1 00            0 size
      0x06    0xf3         0xf3        RETURN
      <CODE>
    */

    return abi.encodePacked(
      hex"63",
      uint32(_code.length),
      hex"80_60_0E_60_00_39_60_00_F3",
      _code
    );
  }

  /**
    @notice Returns the size of the code on a given address
    @param _addr Address that may or may not contain code
    @return size of the code on the given `_addr`
  */
  function codeSize(address _addr) internal view returns (uint256 size) {
    assembly { size := extcodesize(_addr) }
  }

  /**
    @notice Returns the code of a given address
    @dev It will fail if `_end < _start`
    @param _addr Address that may or may not contain code
    @param _start number of bytes of code to skip on read
    @param _end index before which to end extraction
    @return oCode read from `_addr` deployed bytecode

    Forked from: https://gist.github.com/KardanovIR/fe98661df9338c842b4a30306d507fbd
  */
  function codeAt(address _addr, uint256 _start, uint256 _end) internal view returns (bytes memory oCode) {
    uint256 csize = codeSize(_addr);
    if (csize == 0) return bytes("");

    if (_start > csize) return bytes("");
    if (_end < _start) revert InvalidCodeAtRange(csize, _start, _end); 

    unchecked {
      uint256 reqSize = _end - _start;
      uint256 maxSize = csize - _start;

      uint256 size = maxSize < reqSize ? maxSize : reqSize;

      assembly {
        // allocate output byte array - this could also be done without assembly
        // by using o_code = new bytes(size)
        oCode := mload(0x40)
        // new "memory end" including padding
        mstore(0x40, add(oCode, and(add(add(size, 0x20), 0x1f), not(0x1f))))
        // store length in memory
        mstore(oCode, size)
        // actually retrieve the code, this needs assembly
        extcodecopy(_addr, add(oCode, 0x20), _start, size)
      }
    }
  }
}