Submission fa49dbf6...

ChallengeHex decoder
Submitted at2018-15-16
Gas used19001
pragma solidity ^0.4.23;

 * This file is part of the 1st Solidity Gas Golfing Contest.
 * Author: Zachary Wiliamson
 * This work is licensed under Creative Commons Attribution ShareAlike 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 {
            // 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.
            // N.B: could reduce gas cost to *create* contract substantially
            // but 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

            // get number of bytes of output data
            // (half the number of input bytes)
            2 0x24 calldataload div
            // test that value is not zero. Bit of an odd jump structure, but chances of data being 0
            // very low => worth saving 3 gas by not calling (iszero) on 'w' before jump, and
            // unconditionally jumping after test if it fails
            dup1 has_data jumpi
            no_bytes jump

            // put 0x44 on stack, we use this as our calldata pointer to load next input word
            // 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

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

                // 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 and inverting 5th bit and a swap (6 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
                0x20 dup4 add calldataload
                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
                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
                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
            // 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

            0x40 0x00 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