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.

[u/dstroy0 → u/kaganisildak]

This is portable, works on gcc, clang or msvc. Unsigned is platform dependent so the word width gets set by the platform.

[u/Certain-Flow-0 → u/dstroy0]

I think you can use x<<32-n, shaving off two characters?

[u/dstroy0 → u/Certain-Flow-0]

You’re correct the only reason it’s there is to convey what it’s doing more clearly, which is a preference of mine, not a requirement of making it work correctly. I think it’s really cool that you noticed that.

[u/skeeto]

$ printf kagan | sha256sum 
05aebb21178ce70f5c29fc090aab3f50001a73f0f624e6f5789410f855ca2d8c  -

$ aarch64-linux-gnu-gcc -ansi -w sha256.c -lm && ./a.out kagan ; echo
a2b00156fa63dcb8eb37dbfc7c1133f32adea77d5e4ff3cf46fc07c7920289f3

$ x86_64-linux-gnu-gcc -ansi -w sha256.c -lm && ./a.out kagan ; echo
a3a5294ee42c8fbb344795eeef7322e6dac7091f1939c0c15ff6e1154999698b

$ powerpc-linux-gnu-gcc -ansi -w sha256.c -lm && ./a.out kagan ; echo
4b35f7fa8b7a550c0127bcf0ae55758ea8cb01b483d7177bde0e68a1574917b2

$ s390x-linux-gnu-gcc -ansi -w sha256.c -lm && ./a.out kagan ; echo
0e50aa0cb0b6e3166e7e7a5e3565720d797fd3d24831eeaf5595f92d19e9f942

$ clang -ansi -w sha256.c -lm && ./a.out kagan ; echo
97db8f07489301a02cf4ef7f1629c052c7827e82fc4883acf8ef64a1299726d9

I'm getting at least five different answers due to UB, but none of them correct. Though that's kind of a feat in itself.

[u/dstroy0 → u/skeeto]

The rotr are out of order, you can spot where in their original statement, the 2,13,22 shift js not in the correct position.

[u/Zirias_FreeBSD]

As for most golfing stuff in C, this needs some description of a valid environment. Here, at least I see bcopy(), which was never a part of standard C and deprecated from POSIX.

Still, pretty cool abomination! 👍😂

[u/kaganisildak → u/Zirias_FreeBSD]

sshhh we can't talk about this :p

thx

[u/Zirias_FreeBSD → u/kaganisildak]

well, the typical "golfing rules" I know are: You might use whatever you like, even in C "UB" ... as long as the result can be reproduced to verify. I guess adding something like "use an x86_64 Linux with gcc and glibc" would suffice 😉

(edit: just guessing here what might have been your environment...)

[u/Dry-War7589]

What compiler and standard should i use when compiling?

[u/flyingron → u/Dry-War7589]

You have to use pre C99, otherwise the program is ill-formed (and even then it uses deprecated features of the language).

[u/kaganisildak → u/Dry-War7589]

You can check this
Try it online / tio.run

[u/flyingron]

You're not being charged by the byte. Better to be correct and sustainable.

This isn't correct code for this century.

[u/vip17 → u/flyingron]

read about https://en.wikipedia.org/wiki/Code_golf and check out https://codegolf.stackexchange.com/

This is just a fun thing to do and not something used in production

[u/goose_on_fire → u/flyingron]

You have never once said "I'm going to bank this shot off the roof, around the chimney, then header it in, nothing but net" and it shows

C is a great hold-my-beer language, have fun with it

[u/dstroy0 → u/goose_on_fire]

I really like this sentiment, it leads to novel algorithms, assembly, wacky ideas in general that somehow beat existing implementations literally continuously. I think it is exactly the correct attitude to have when approaching literally ~any~ problem you have creative freedom with, and grows your own ip while you're learning and helping others learn. That's generally when the deepest conceptual understanding happens for me, when I need to teach someone something in maybe a different way than usual to help them master a specific concept. Thanks for sharing, it makes me happy to see others with the same generally positive problem solving attitude in the wild.