// Contract: CatsOnChain
// Target function: function hashToMetadata(string memory _hash)

                        )
                    )
                ) % 11111
            );

            currentHash = string(
                abi.encodePacked(currentHash, rarityGen(_randinput, i))
            );
        }

        if (hashToMinted[currentHash]) return hash(_t, _a, _c + 1);

        return currentHash;
    }

    /**
     * @dev Mints new cat. The first 1000 mints are free. Afterwards each mint costs 0.08 Eth. There is a maximum of 11111 cats. 
     */
    function mintCatPublic() public payable {
        require(msg.value  >= MINT_PRICE || totalSupply() < 1000,
            "Wrong Minting Price (0.08 Eth)"
        );
        mintCat();      
    }

    function mintCat() private{    
        uint256 _totalSupply = totalSupply();
        require(_totalSupply < MAX_SUPPLY, "All cats are already minted");
        uint256 thisTokenId = _totalSupply;
        tokenIdToHash[thisTokenId] = hash(thisTokenId, msg.sender, 0);
        hashToMinted[tokenIdToHash[thisTokenId]] = true;
        _mint(msg.sender, thisTokenId);
    }

    /*
 ____     ___   ____  ___        _____  __ __  ____     __ ______  ____  ___   ____   _____
|    \   /  _] /    ||   \      |     ||  |  ||    \   /  ]      ||    |/   \ |    \ / ___/
|  D  ) /  [_ |  o  ||    \     |   __||  |  ||  _  | /  /|      | |  ||     ||  _  (   \_ 
|    / |    _]|     ||  D  |    |  |_  |  |  ||  |  |/  / |_|  |_| |  ||  O  ||  |  |\__  |
|    \ |   [_ |  _  ||     |    |   _] |  :  ||  |  /   \_  |  |   |  ||     ||  |  |/  \ |
|  .  \|     ||  |  ||     |    |  |   |     ||  |  \     | |  |   |  ||     ||  |  |\    |
|__|\_||_____||__|__||_____|    |__|    \__,_||__|__|\____| |__|  |____|\___/ |__|__| \___|
                                                                                           
*/

    /**
     * @dev Returns the GIF and metadata for a token Id
     * @param _tokenId The tokenId to return the GIF and metadata for.
     */
    function tokenURI(uint256 _tokenId)
        public
        view
        override
        returns (string memory)
    {
        require(_exists(_tokenId));
        string memory tokenHash = tokenIdToHash[_tokenId];
      

        return
            string(
                abi.encodePacked(
                    "data:application/json;base64,",
                    CatLib.encode(
                        bytes(
                            string(
                                abi.encodePacked(
                                    '{"name": "Cat #',
                                    CatLib.toString(_tokenId),
                                    '", "description": "CatsOnChain is a collection of 11,111 unique animated cats. All metadata and GIFs are generated by an algorithm on the blockchain. No IPFS, no API. Just one smart contract on the Ethereum blockchain.", "image": "data:image/gif;base64,',
                                    hashToGifHex(tokenHash),
                                    '","attributes":',
                                    hashToMetadata(tokenHash),
                                    "}"
                                )
                            )
                        )
                    )
                )
            );
    }

    /**
     * @dev Hash to GIF-Hex function
     * @param _hash The Hash to generate the GIF
     */
    function hashToGifHex(string memory _hash)
        public
        view
        returns (string memory)
    {
        // 12 Frames. Each with 25x25 (625) colors
        bytes[12] memory colorBytes;
        for (uint256 i = 0; i < 12; i++) {
            colorBytes[i] = new bytes(625);
        }
        bool[625][12] memory placedPixels;

        //for each trait
        for (uint8 i = 0; i < 7; i++) {
            uint16 thisTraitIndex = CatLib.parseInt16(
                CatLib.substring(_hash, i, i + 1)
            );

            //For each defined pixel within the trait
            for (
                uint16 j = 0;
                j < bytes(traitTypes[i][thisTraitIndex].pixels).length / 5;
                j++
            ) {
                // Get the pixel information
                string memory thisPixel = CatLib.substring(
                    traitTypes[i][thisTraitIndex].pixels,
                    j * 5,
                    j * 5 + 5
                );
                bytes memory thisPixelBytes = bytes(thisPixel);

                // Get the place of the pixel: 25*(Y-Coordinate) + X-Coordinate
                uint16 place = CatLib.letterToNumber(thisPixelBytes[1]);
                place = place * 25 + CatLib.letterToNumber(thisPixelBytes[0]);

                // Get the Length of the Pixel
                uint8 PixelLength = CatLib.letterToNumber(thisPixelBytes[2]);

                // Get the color of the pixel
                uint8 color = CatLib.letterToNumber(thisPixelBytes[3]);

                // Get the movement of the Pixel
                uint8 movement = CatLib.letterToNumber(thisPixelBytes[4]);
               
                // Do it PixelLenghth-times
                for (uint8 l = 0; l < PixelLength; l++) {
                    //For each GIF Frame
                    for (uint8 k = 0; k < 12; k++) {
                        //Place and color inside this frame
                        uint16 placeFrame = place;
                        uint8 colorFrame = color;

                        //Each Movement results in different output
                        if (movement == 0) {
                            // Do nothing
                        } else if (movement == 1) {
                            placeFrame = (place + k) % 625;
                        } else if (movement == 2) {
                            colorFrame = color + (k % 3);
                        } else if (movement == 3) {
                            colorFrame = (color - 1) + ((k + 1) % 3);
                        } else if (movement == 4) {
                            colorFrame = (color - 2) + ((k + 2) % 3);
                        } else if (movement == 5) {
                            placeFrame = placeFrame + ((k / 4) % 2);
                        } else if (movement == 6) {
                            if (0 >= k || k >= 11) {
                                continue;
                            }
                        } else if (movement == 7) {
                            if (1 >= k || k >= 10) {
                                continue;
                            }
                        } else if (movement == 8) {
                            if (2 >= k || k >= 9) {
                                continue;
                            }
                        } else if (movement == 9) {
                            if (3 >= k || k >= 8) {
                                continue;
                            }
                        } else if (movement == 10) {
                            if (4 >= k || k >= 7) {
                                continue;
                            }
                        } else if (movement == 11) {
                            if (k > 5) {
                                placeFrame = place - 25;
                            }
                        } else if (movement == 12) {
                            if (k == 3 || k == 5) {
                                placeFrame = place - 25;
                            }
                        } else if (movement == 13) {
                            if ((k / 3) % 2 == 0) {
                                continue;
                            }
                        } else if (movement == 14) {
                            if ((k / 3) % 2 != 0) {
                                continue;
                            }
                        } else if (movement == 15) {
                            placeFrame = place + (k / 2) * 25;
                        } else if (movement == 16) {
                            if (k % 2 != 0) {
                                continue;
                            }
                        } else if (movement == 17) {
                            placeFrame = place + (k / 2) * 26;
                            if (placeFrame >= 625) {
                                continue;
                            }
                        } else if (movement == 18) {
                            if ((k/2) == 2 || (k/2) == 4) {
                                placeFrame = place - 25;
                            }
                        } else if (movement == 19) {
                            if((k/2)%2 == 1){
                                placeFrame = place - 1;                               
                           }
                        } else if (movement == 20) {
                            placeFrame = place + ((k+3) / 2) % 2;
                        } else if (movement == 21) {
                            if(k<6){
                                placeFrame = place + k;
                            }else{
                                placeFrame = place + (12-k);
                            }
                            if(placeFrame > 37) continue;
                            colorFrame = color + k/6;
                        }else if (movement == 22) {
                            if(k<6){
                                if(placeFrame > 42 - k) continue;
                            }else{
                                if(placeFrame > 42 - (12-k)) continue;
                            }                            
                            colorFrame = color - k/6;
                        }else if (movement == 23) {
                           if(k%2 == 0){
                               if(k%4 == 0){ 
                                   placeFrame = place + 1;
                               } else {
                                   placeFrame = place - 1;
                               }
                           }
                        } else if (movement == 24) {
                            placeFrame = placeFrame - ((k / 4) % 2);
                        } else if (movement == 24) {
                            placeFrame = placeFrame + ((k / 3) % 2);
                        }

                        // Only set the Pixel if not set before
                        if (placedPixels[k][placeFrame]) continue;

                        //Set the color
                        colorBytes[k][placeFrame] = abi.encodePacked(
                            colorFrame
                        )[0];
                        placedPixels[k][placeFrame] = true;
                    }
                    place += 1;
                }
            }
        }
     
        
        /* Define the GIF         
            Header: \x47\x49\x46\x38\x39\x61
            Size (100px x 100px):  \x64\x00\x64\x00
            Define of length of Global Color Table (64 colors): \xF5
            Background color (not used): \x02 
            Default pixel ratio: \x00
            Color table with 64 colors (in RGB):    \x00\x00\x00
                                                    \x43\xF6\xEE
                                                    ...
                                                    \x00\x00\x00
            Application Extension: \x21\xFF
                Size of block including application name and verification bytes (always 11): \x0B
                8-byte application name plus 3 verification bytes: \x4E\x45\x54\x53\x43\x41\x50\x45\x32\x2E\x30
                Number of bytes in the following sub block: \x03
                    Subblock: 
                        Index of subblock: \x01
                        Number of repetitions (never ends): \x00\x00
            End of Application extension: \x00
      */
        bytes
            memory gifHex = "\x47\x49\x46\x38\x39\x61\x64\x00\x64\x00\xF5\x02\x00\x00\x00\x00\xF6\x43\x7F\x43\xF6\xEE\x5D\xF6\x43\x4A\xC7\x35\xFF\xD7\x00\xFE\xE2\x4D\xFE\xDC\x25\xC0\xC0\xC0\xD0\xD0\xD0\xDF\xDF\xDF\x00\x00\x00\x00\x3A\x04\x00\x49\x05\x00\x5E\x07\x27\x07\x3E\x2E\xBD\xB7\x31\x25\x06\x3A\x05\x05\x3D\x0B\x60\x46\x16\x70\x48\x27\x60\x52\x48\x2D\x52\x4B\x35\x5A\x44\x0A\x5C\x1E\x92\x63\x59\x3D\x67\x59\x37\x6B\x20\xAC\x6B\x61\x44\x6D\x15\x15\x6D\x5D\x34\x6D\x6D\x6D\x80\x6B\x34\x82\x80\x79\x8B\x69\x11\x8D\x7E\x57\x92\x47\x47\x9A\x4E\x6E\xA9\xA9\xA9\xB1\x9D\x68\xBD\xAB\x79\xC5\x9F\x9F\xCA\xD4\x38\xCC\x73\x20\xDD\x7B\x1F\xE5\xBC\xBC\xE7\xE7\xE7\xEB\xF6\x43\xEF\x79\xAB\xF0\xD9\xE3\xFF\x00\x00\xFF\xF9\xF9\xFF\xFF\x00\xFF\xFF\xFF\x08\x26\x42\x11\x37\x5C\x22\x53\x81\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x21\xFF\x0B\x4E\x45\x54\x53\x43\x41\x50\x45\x32\x2E\x30\x03\x01\x00\x00\x00";

        //For each Frame add Hex value to the gifHex
        for (uint256 i = 0; i < 12; i++) {
            gifHex = abi.encodePacked(gifHex, hexByColors(colorBytes[i]));
        }

        //Add Last byte in the file: \x3B
        gifHex = abi.encodePacked(gifHex, "\x3B");
        return CatLib.encode(gifHex);
    }

    /**
     * @dev Get the Hex of the GIF by Color-Bytes
     * @param colorBytes Bytes of Colors for the GIF (625 Bytes)
     */
    function hexByColors(bytes memory colorBytes)
        public
        pure
        returns (bytes memory)
    {
        bytes memory returnHex;
        bytes memory tempBytes;

        // For each row in the gif (25x25 = 625 colors)
        for (uint256 i = 0; i < colorBytes.length / 25; i++) {
            // Get Hex of the row
            tempBytes = hexgetLine(colorBytes, i * 25);

            //Because we want a 100x100px Gif: Copy the line 4 times
            for (uint256 j = 0; j < 4; j++) {
                returnHex = abi.encodePacked(returnHex, tempBytes);
            }
        }

        /*returnHex Explanation: 
            Graphic Control Extension: \x21\xF9
                Amount of GCE bytes: \x04
                    Transparent color given (yes): \x09
                    Frame delay (0,16s): \x11\x00
                    Transparent color (The first color in the Global Color Table):\x00
            End of GCE extension: \x00
            Image Descriptor: \x2C
                North-west corner position of frame: \x00\x00\x00\x00
                Frame width (100x100px):\x64\x00\x64\x00
                Local color table (not used):\x00
                Minimum LZW (Lempel-Ziv-Welch) compression: \x07

                Hex LZW

                Last Bytes of LZW: \x01\x81
            End of Image Descriptor: \x00 
        */
        returnHex = abi.encodePacked(
            "\x21\xF9\x04\x09\x11\x00\x00\x00\x2C\x00\x00\x00\x00\x64\x00\x64\x00\x00\x07",
            returnHex,
            "\x01\x81\x00"
        );
        return returnHex;
    }

    /**
     * @dev Get Hex-value for one row of the GIF
     * @param colorBytes Bytes of Colors for the GIF
     * @param startindex The start index of the row
     */
    function hexgetLine(bytes memory colorBytes, uint256 startindex)
        public
        pure
        returns (bytes memory)
    {
        bytes memory returnHex;
        // For each color: add the byte 4 times
        for (uint256 i = startindex; i < startindex + 25; i++) {
            bytes1 tempByte = colorBytes[i];
            for (uint256 j = 0; j < 4; j++) {
                returnHex = abi.encodePacked(returnHex, tempByte);
            }
        }

        /*
            Length of the Part (25*4 + 1): \x65
            Clear Code (relevant for LZW): \x80 
        */
        return abi.encodePacked("\x65\x80", returnHex);
    }