Submission 1c0c81ce...

ChallengeHex decoder
Submitterzac.creditmint.eth
Submitted at2018-06-18
Gas used18985
pragma solidity ^0.4.23;


/**
 * This file is part of the 1st Solidity Gas Golfing Contest.
 *
 * Author: Zachary Williamson
 *
 * This work is licensed under Creative Commons Attribution ShareAlike 3.0.
 * https://creativecommons.org/licenses/by-sa/3.0/
 */

contract HexDecoder {
    /**
     * @dev Decodes a hex-encoded input string, returning it in binary.
     *
     * Input strings may be of any length, but will always be a multiple of two
     * bytes long, and will not contain any non-hexadecimal characters.
     *
     * @return The decoded output.
     */

    // Variable declarations:
    // w        current word of input string we're operating on
    // n        calldata pointer to next 0x20 bytes of input data
    // s        number of output bytes
    // m        initial memory pointer (index where first output value stored)

    function decode(string) external view returns(bytes) {
        assembly {
            // first, let's check there's some calldata to operate on
            0x24 calldataload has_data jumpi
            0x40 0x00 return
    has_data:
            // chuck this onto the stack at the start
            // pushing it onto stack in main loop costs 6 gas per operation instead of 3
            // because optimizer converts this into PUSH1(0x0) NOT.
            0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
            // N.B: could reduce gas cost to *create* contract substantially
            // by pushing all of the 32 byte constants onto stack before start of iteration
            // and duplicating, but that increases runtime costs by 3 gas per constant!

            // we use msize as our 'free memory pointer', hon hon.
            // store the initial value to use at end of loop
            // we also are going to need to subtract 0x40 from it after a few dup operations
            // store on stack so we don't need to swap
            0x40
            msize

            // get number of bytes of output data
            // (half the number of input bytes)
            2 0x24 calldataload div
            // put 0x44 on stack, we use this as our calldata pointer to load next input word
            0x44
            // we load our next word in at end of main loop so we can use it to test
            // against continuing loop. So load a word onto stack before we start
            dup1 calldataload

            loop_start:
                // stack state = w n s m 0x40
                // only care about first two items for main loop

                // current word is 256-bit chunk of utf-8 input
                // we want to:
                // a: convert word into format 'abbccddeeffgghhiijjkkllmm...'
                //    where each letter represents the least significant nibble of every byte
                // b: add '9' to every nibble that came from an alphanumeric char

                dup6
                // isolate the 7th bit of every byte
                dup2 0x4040404040404040404040404040404040404040404040404040404040404040 and
                // if an alphanumeric char, this will be set to high
                // convert from 0100 0000
                //           to 0000 1001
                // by multiplying by (2^253 + 2^250) mod -1
                0x2400000000000000000000000000000000000000000000000000000000000000 mulmod
                add // add back into w
                // NB: can do this with a mul operation instead of mulmod but costs the same:
                // requires isolating 5th bit and inverting (3 gas),
                // multiplying by (2^0 + 2^3 + 2^4 + 2^7) and adding into word
                // after nibble shift below (requires a swap, 3 gas).

                // now that we've added alphanumeric quotient into least
                // significant nibble mask out most significant nibble of every byte
                0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f and
                
                // mul by (2^4 + 2^8): shifts each nibble up by one and copies it
                // into next significant nibble (which we masked to be 0)
                272 mul

                // mask off every other byte, leaving: 0xab00cd00ef00gh00ij...
                0xff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00 and
                // mul by (2^0 + 2^8) to create: 0xabcdcdefefghghijij...
                257 mul
                // mask off every other 2 bytes, leaving: 0xabcd0000efgh0000ijkl0000mnop
                0xffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000 and
                // mul by (2^0 + 2^16) to create: 0xabcdefgh efghijkl ijklmnop mnopqrst ...
                65537 mul
                // mask off every 4 bytes, leaving: 0xabcdefgh 00000000 ijklmnop 00000000 qrstuvwx ...
                0xffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000 and
                // mul by (2^0 + 2^32) to create: 0xabcdefghijklmnop ijklmnopqrstuvwx qrstuvwxyza'b'c'd'e'f'
                4294967297 mul
                // mask off every 8 bytes
                0xffffffffffffffff0000000000000000ffffffffffffffff0000000000000000 and
                // mul by (2^0 + 2^64) to create a 16 byte packed representation of input
                18446744073709551617 mul
                // we want the result without any data in the lower 128 bits, so we can
                // combine with second word in main loop
                0xffffffffffffffffffffffffffffffff00000000000000000000000000000000 and


                // repeat with next calldata word, so we can combine into single 'mstore' op
                // this allows us to be sneaky and use 'msize' as our pointer to next word
                // in output array. Costs only 2 gas and is self-incrementing, saving
                // 7 gas per word when compared with keeping a pointer on the stack and
                // manually incrementing. We also cut conditional jumps in half
                0x000000000000000000000000000000100000000000000000000000000000000
                0x20 dup4 add calldataload
                dup8
                dup2 0x4040404040404040404040404040404040404040404040404040404040404040 and
                0x2400000000000000000000000000000000000000000000000000000000000000 mulmod add
                0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f and
                272 mul
                0xff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00 and 257 mul
                0xffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000 and 65537 mul
                0xffffffff00000000ffffffff00000000ffffffff00000000ffffffff00000000 and 4294967297 mul
                0xffffffffffffffff0000000000000000ffffffffffffffff0000000000000000 and
                18446744073709551617 mul
                // we want this result to occupy least significant 128 bits, so divide down result
                div
                add msize mstore // add result and store

                0x40 add         // increment calldata pointer
                dup1 calldataload  // load next word of calldata

                // we want to skip out of loop when we've iterated over input string
                // instead of keeping track of an endpoint, just duplicate the loaded calldata
                // if != 0 we need to keep looping, so we can use directly for our conditional jump test
                dup1
                loop_start jumpi

            // get rid of calldata pointer and empty calldata word
            pop pop         
            // stack state = s, m, 0x40

            // we operate on 32 byte chunks, it the input data not
            // divisible by 32, there will be a bunch of junk
            // at the end of the aray; we need to zero out that data
            // copy initial memory pointer and # input bytes, add together
            // and store 0x0 at resulting index
            0x0 dup2 dup4 add mstore

            // second word of output data contains number of bytes in bytes array
            // we calculated that at start of program; write at memory index:
            // (initial memory pointer - 0x20)
            0x20 dup3 sub mstore // store length and consume 's' on stack

            // stack state = m, 0x40
            // subtract 0x40 from initial memory pointer to get pointer to start of output data
            sub
            // first word of output data points to starting index of dynamic array
            // which is 0x20
            0x20 dup2 mstore

            // calculate the number of bytes of output data, rounded up to nearest 0x20 bytes
            // number of bytes = msize - start of memory pointer - 0x20
            // 0x20 term is because final 'msize mstore' operation increased msize by 0x20
            dup1 0x20 msize sub sub

            // NB: because of Solidity boilerplate, 'msize' should always initially point to 0x60
            // so we have space to enter the two dynamic array initialization words beneath the first
            // word of output array
    
            // stack state: # of bytes of output data, pointer to start of output data
            // swap these over and exit
            swap1
            return

        // compiler throws 'unbalanced stack' errors because of '-1 still lurking on the stack
        // this opcode will never get run but heyho what can you do
        pop
        }
    }
}