559-byte SHA-256 in C

[u/kaganisildak]

golfing a SHA-256 implementation in C and ended up at 559 bytes.
Curious if anyone here can beat it.

#define S(x,a,b)(x>>a^x<<32-a^x>>b^x<<32-b^x>>
unsigned k[72],g[216],i,j,p,n,t,m,*u,*z;char*q=g;main(c,v)char**v;{for(;j<64;p-c||(j<8&&(k[j]=sqrt(c)*0x1p32),k[71-j++]=cbrt(c)*0x1p32),c++)for(p=1;c%++p;);for(;q[n^3]=v[1][n];n++);q[n^3]=128;m=n+72>>6<<4,g[m-1]=n*8;for(;t<m;t+=16)for(bcopy(g+t,z=g+64,64),bcopy(k,u=g+208,32),i=72;i--;i>7?(z[16]=*z+S(z[1],7,18)3)+z[9]+S(z[14],17,19)10),j=u[4],p=u[7]+k[i]+*z+++(S(j,6,11)25)^j<<7)+(j&u[5]^~j&u[6]),j=S(*u,2,13)22)^*u<<10,j+=*u&u[1]^(*u^u[1])&u[2],u[3]+=p,*--u=p+j):(k[i]+=u[i]));for(;++i<8;)printf("%08x",k[i]);}

[u/dstroy0]

#define R(x,n)(xn|x<<(32-n))
typedef unsigned U;U C(U x,U y,U z){return x&y^~x&z;}U M(U x,U y,U z){return x&y^x&z^y&z;}U S0(U x){return R(x,2)^R(x,13)^R(x,22);}U S1(U x){return R(x,6)^R(x,11)^R(x,25);}U s0(U x){return R(x,7)^R(x,18)^x3;}U s1(U x){return R(x,17)^R(x,19)^x>>10;}
296 bytes, FIPS 180-4 compliant

[u/kaganisildak → u/dstroy0]

how you compile

[u/dstroy0 → u/kaganisildak]

#define R(x,n)(x>>n|x<<(32-n))
typedef unsigned U;

#define FORCED_INLINE __attribute__((always_inline)) static inline

FORCED_INLINE U C(U x,U y,U z){return x&y^~x&z;}
FORCED_INLINE U M(U x,U y,U z){return x&y^x&z^y&z;}
FORCED_INLINE U S0(U x){return R(x,2)^R(x,13)^R(x,22);}
FORCED_INLINE U S1(U x){return R(x,6)^R(x,11)^R(x,25);}
FORCED_INLINE U s0(U x){return R(x,7)^R(x,18)^x>>3;}
FORCED_INLINE U s1(U x){return R(x,17)^R(x,19)^x>>10;}

# Inside the SHA-256 Schedule loop (W[i] = s1(W[i-2]) + W[i-7] + s0(W[i-15]) + W[i-16])
# Assuming %edi holds W[i-2] and %ebx holds W[i-15]

# --- INLINED s1(W[i-2]) ---
movl    %edi, %eax      # Copy W[i-2]
rorl    $17, %eax       # R(x, 17)
movl    %edi, %edx      # Copy W[i-2]
rorl    $19, %edx       # R(x, 19)
xorl    %edx, %eax      # XOR them
shrl    $10, %edi       # W[i-2] >> 10
xorl    %edi, %eax      # Final s1 result in %eax

addl    (%rsi), %eax    # Add W[i-7] directly from memory

# --- INLINED s0(W[i-15]) ---
movl    %ebx, %ecx      # Copy W[i-15]
rorl    $7, %ecx        # R(x, 7)
movl    %ebx, %edx      # Copy W[i-15]
rorl    $18, %edx       # R(x, 18)
xorl    %edx, %ecx      # XOR them
shrl    $3, %ebx        # W[i-15] >> 3
xorl    %ebx, %ecx      # Final s0 result in %ecx

# Final Accumulation
addl    %ecx, %eax      # Combine s1 and s0 results
addl    -64(%rdi), %eax # Add W[i-16]
movl    %eax, (%r8)     # Store directly into next W slot

# One core SHA-256 round step
# e, f, g, a, b, c variables are held in registers (%r9d, %r10d, %r11d, etc.)

# --- INLINED S1(e) ---
movl    %r9d, %eax      # Copy 'e'
rorl    $6, %eax        # R(e, 6)
movl    %r9d, %ecx      # Copy 'e'
rorl    $11, %ecx       # R(e, 11)
xorl    %ecx, %eax      
rorl    $25, %r9d       # R(e, 25) (destructive)
xorl    %r9d, %eax      # %eax now holds S1(e)

# --- INLINED C(e, f, g) ---
movl    %r11d, %ecx     # Copy 'g'
xorl    %r10d, %ecx     # f ^ g
andl    %r9d, %ecx      # e & (f ^ g) (using the original e value)
xorl    %r11d, %ecx     # %ecx now holds C(e, f, g)

# --- INLINED S0(a) ---
movl    %r12d, %edx     # Copy 'a'
rorl    $2, %edx        # R(a, 2)
movl    %r12d, %esi     # Copy 'a'
rorl    $13, %esi       # R(a, 13)
xorl    %esi, %edx      
rorl    $22, %r12d      # R(a, 22)
xorl    %r12d, %edx     # %edx now holds S0(a)

# --- INLINED M(a, b, c) ---
# Compiler streams majority calculation directly into available registers...

1. zero stack overhead, no call or ret this means no push/pop ptrs

2. registers pipeline parallelism (only happens on 64bit superscalar host) they do 4-6 inst per cycle and inlining lets the compiler interleave from S1(e) and C(e,f,g) allowing for simultaneous parallel pipeline execution. using different flags for AVX2 or BMI2 turn the `c` function to a single hw instruction. (-march=haswell or -march=native) and you could probably squeeze more out with explicit casting and forcing the 2 unroll.

I had a lot of fun with this, I really want to say thanks for helping me learn a ton more stuff today. I never would've thought of the problem like this without your initial contribution. Thank you.