I'm playing around with work-factor hash functions, and I'm looking for a memory-hard operation to make it resistant to GPU / parallel hardware attacks. I considered a very large (i.e. 64K) s-box that gets shuffled based on the state per round, but I have a feeling that there are ways to optimise such an operation for minimal memory usage.

My current scheme is as follows:

    state = sha512(message);
    salt = sha512(salt);
    for(int i = 0; i < 4096; i++)
    {
      state ^= hmac_sha512(state, salt);
      state ^= hmac_ripemd256(state, salt);
      state ^= hmac_salsa20(state, salt);
    }
    return sha512(state);

The idea was to modify this to something like:

    state = sha512(message);
    salt = sha512(salt);

    sbox = array(65536);
    for(int i = 0; i < 65536) sbox[i] = i % 256;

    for(int i = 0; i < 4096; i++)
    {
      if(i % 64 == 0) shuffle(sbox, state); // shuffle sbox based on state
      state ^= hmac_sha512(state, salt);
      state ^= hmac_ripemd256(state, salt);
      state ^= hmac_salsa20(state, salt);
      for(int n = 0; n < 63; n++)
        state[n] = sbox[state[n]*256 + state[n+1]];
    }
    return sha512(state);

Is such a scheme guaranteed to require a lot of memory, or can it be optimised? Are there other simple operations that provide such guarantees?