Constant Time Array Lookup?

constant.c

// WARNING! This code is untested and experimental. DO NOT USE IT.

// NOTE: If I knew of a way to do the "shift and OR" thing reliably with unsigned ints, the code could be simplified a lot.

// Will always be compiled with -std=c99

// Returns UINT32_MAX if a == b, 0 otherwise.
uint32_t invariant_time_integer_compare(uint32_t a, uint32_t b)
{
    /* z will be zero if and only if a == b. */
    uint32_t z = a ^ b;
    /* OR every bit into the LSb of z so that the LSb is zero iff a == b. */
    z |= z >> 16;
    z |= z >> 8;
    z |= z >> 4;
    z |= z >> 2;
    z |= z >> 1;
    /* z will be 1 if a != b, or 0 if a == b. */
    z = z & 1;
    /* Flip the LSB, so that z is 1 if a == b and z is 0 if a != b */
    z = 1u - z;
    /* If a != b, z is 0 and the result of the subtraction is 0. */
    /* If a == b, z is 1 and the result of the subtraction is UINT32_MAX. */
    z = 0u - z;
    /* What is the type of 0u? It's the first unsigned type it fits in,
     * beginning with unsigned int, so it will be unsigned int.
     * 
     * Now there are three possibilities:
     *
     *  1. unsigned int is wider than uint32_t:
     *
     *      In this case, z gets converted to unsigned int, and the subtraction
     *      results in UINT_MAX, which is by assumption greater than UINT32_MAX,
     *      so the result will get truncated to UINT32_MAX.
     *
     *  2. uint32_t is the same type as unsigned int:
     *
     *      They are the same type, so there's no conversion, and the result is
     *      UINT_MAX, which is UINT32_MAX.
     * 
     *  3. uint32_t is wider than unsigned int:
     * 
     *      0u gets promoted to a zero uint32_t, and the result is UINT32_MAX.
     *
     */
    return z;
}

char invariant_time_lookup(const char *array, uint32_t length, uint32_t index)
{
    char result = 0;
    for (uint32_t i = 0; i < length; i++) {
        /* If the index is wrong, mask will be zero, and we'll OR zero into the
         * result (which has no effect). If the index is right, the mask will be
         * all 1 bits, so we'll OR the contents of the array into the result. */
        uint32_t mask = invariant_time_integer_compare(i, index);
        result |= array[index] & mask;
        // XXX: I'm not so sure about this... array[index] is signed, and result is signed...
    }
    return result;
}


/*
0000000000400c67 <invariant_time_integer_compare>:
  400c67:       55                      push   rbp
  400c68:       48 89 e5                mov    rbp,rsp
  400c6b:       89 7d ec                mov    DWORD PTR [rbp-0x14],edi
  400c6e:       89 75 e8                mov    DWORD PTR [rbp-0x18],esi
  400c71:       8b 45 e8                mov    eax,DWORD PTR [rbp-0x18]
  400c74:       8b 55 ec                mov    edx,DWORD PTR [rbp-0x14]
  400c77:       31 d0                   xor    eax,edx
  400c79:       89 45 fc                mov    DWORD PTR [rbp-0x4],eax
  400c7c:       8b 45 fc                mov    eax,DWORD PTR [rbp-0x4]
  400c7f:       c1 e8 10                shr    eax,0x10
  400c82:       09 45 fc                or     DWORD PTR [rbp-0x4],eax
  400c85:       8b 45 fc                mov    eax,DWORD PTR [rbp-0x4]
  400c88:       c1 e8 08                shr    eax,0x8
  400c8b:       09 45 fc                or     DWORD PTR [rbp-0x4],eax
  400c8e:       8b 45 fc                mov    eax,DWORD PTR [rbp-0x4]
  400c91:       c1 e8 04                shr    eax,0x4
  400c94:       09 45 fc                or     DWORD PTR [rbp-0x4],eax
  400c97:       8b 45 fc                mov    eax,DWORD PTR [rbp-0x4]
  400c9a:       c1 e8 02                shr    eax,0x2
  400c9d:       09 45 fc                or     DWORD PTR [rbp-0x4],eax
  400ca0:       8b 45 fc                mov    eax,DWORD PTR [rbp-0x4]
  400ca3:       d1 e8                   shr    eax,1
  400ca5:       09 45 fc                or     DWORD PTR [rbp-0x4],eax
  400ca8:       83 65 fc 01             and    DWORD PTR [rbp-0x4],0x1
  400cac:       b8 01 00 00 00          mov    eax,0x1
  400cb1:       2b 45 fc                sub    eax,DWORD PTR [rbp-0x4]
  400cb4:       89 45 fc                mov    DWORD PTR [rbp-0x4],eax
  400cb7:       f7 5d fc                neg    DWORD PTR [rbp-0x4]
  400cba:       8b 45 fc                mov    eax,DWORD PTR [rbp-0x4]
  400cbd:       5d                      pop    rbp
  400cbe:       c3                      ret    

0000000000400cbf <invariant_time_lookup>:
  400cbf:       55                      push   rbp
  400cc0:       48 89 e5                mov    rbp,rsp
  400cc3:       48 83 ec 20             sub    rsp,0x20
  400cc7:       48 89 7d e8             mov    QWORD PTR [rbp-0x18],rdi
  400ccb:       89 75 e4                mov    DWORD PTR [rbp-0x1c],esi
  400cce:       89 55 e0                mov    DWORD PTR [rbp-0x20],edx
  400cd1:       c6 45 ff 00             mov    BYTE PTR [rbp-0x1],0x0
  400cd5:       c7 45 f8 00 00 00 00    mov    DWORD PTR [rbp-0x8],0x0
  400cdc:       eb 33                   jmp    400d11 <invariant_time_lookup+0x52>
  400cde:       8b 55 e0                mov    edx,DWORD PTR [rbp-0x20]
  400ce1:       8b 45 f8                mov    eax,DWORD PTR [rbp-0x8]
  400ce4:       89 d6                   mov    esi,edx
  400ce6:       89 c7                   mov    edi,eax
  400ce8:       e8 7a ff ff ff          call   400c67 <invariant_time_integer_compare>
  400ced:       89 45 f4                mov    DWORD PTR [rbp-0xc],eax
  400cf0:       8b 55 e0                mov    edx,DWORD PTR [rbp-0x20]
  400cf3:       48 8b 45 e8             mov    rax,QWORD PTR [rbp-0x18]
  400cf7:       48 01 d0                add    rax,rdx
  400cfa:       0f b6 00                movzx  eax,BYTE PTR [rax]
  400cfd:       89 c2                   mov    edx,eax
  400cff:       8b 45 f4                mov    eax,DWORD PTR [rbp-0xc]
  400d02:       21 c2                   and    edx,eax
  400d04:       0f b6 45 ff             movzx  eax,BYTE PTR [rbp-0x1]
  400d08:       09 d0                   or     eax,edx
  400d0a:       88 45 ff                mov    BYTE PTR [rbp-0x1],al
  400d0d:       83 45 f8 01             add    DWORD PTR [rbp-0x8],0x1
  400d11:       8b 45 f8                mov    eax,DWORD PTR [rbp-0x8]
  400d14:       3b 45 e4                cmp    eax,DWORD PTR [rbp-0x1c]
  400d17:       72 c5                   jb     400cde <invariant_time_lookup+0x1f>
  400d19:       0f b6 45 ff             movzx  eax,BYTE PTR [rbp-0x1]
  400d1d:       c9                      leave  
  400d1e:       c3                      ret    
*/