Most Well-rounded Hash

もっとも練り上げられたハッシュ

Line wrap

Highlight

#include <stdio.h>
#include <math.h>
#define i(Y) X[(int)(Y)]

typedef/***************/
/**/                /**/
/**/    volatile    /**/
/**/     double     /**/
/**/                /**/
/*******************/T;T

H=4.503599627370496e15,
a=2.271681097355226e15,
n=4.294967296e9,
d=4.023233417e9,
l=3.135045272e9,
e=1.159922023e9,

w=8.44396048e8,
i(99999)={0},
t=-257,
h=-128,

C=64,
A=16,
R=4,
E=1,

u=1,
z=1,
U=0,
s=0,
j=0,
r=0,
M=0,
F=0,
k=0,
o=0,
V=0,
g=0,
Z=0,
Y=0;

T _(T d,T l){d+=0.5;d/=l;d+=1.5;d+=H;d-=H;return d-2;}
T Q(T d,T l){d-=l;d/=H;d+=1;d/=2;d+=H;return d-H;}
T I(T d,T l){d-=l;d*=C;return exp(-d*d);}
T f(T d,T l){d*=_(l,d);return l-d;}

int main(){
  while(!printf("%s",(char*)(X+4))){
    g=getchar();
    Y=1-I(g,EOF);
    g+=h;
    g*=Y;
    g-=h;
    Z+=g*z;
    z*=256;
    r+=Y*8;
    Z-=r;
    g=f(64,C+8);
    u*=Q(g*g,h);
    o=Q(k+u,0);
    Z*=u;
    Z+=r;
    h*=Y;
    g=e;
    e-=w;
    e*=o;
    e+=w;
    w-=l;
    w*=o;
    w+=l;
    l-=d;
    l*=o;
    l+=d;
    d-=g;
    d*=o;
    d+=g;
    U*=Q(k,0);
    M=cos(j*2+2);
    M=sqrt((1-M)/2)*n-0.5;
    M+=H;
    l+=l;
    w+=w;
    e+=e;
    F=_(l,n);
    s=_(w,n);
    V=_(e,n);
    l+=F*(1-n);
    w+=s*(1-n);
    e+=V*(1-n);
    o=_(j,16);
    s-=V*Q(cos(o*3),0);
    s*=Q(F+o,0);
    s+=V*I(o,0);
    s*=s;
    s-=(1+V*(F-1))*I(o,3);
    s-=F;
    s*=(1-V*I(o,1));
    s+=F*(1-I(o,2));
    s*=s;
    U+=U+s;
    Y=f(4,j);
    k+=E;
    k-=u;
    g=((-4*o+16)*o-12)*o;
    g=g*Y+((22*o-90)*o+74)*o;
    g=g*Y-(((38*o-158)*o+138)*o-60);
    g=g*Y+(((4*o-6)*o-22)*o+84);
    Y=(((2*o-9)*o+11)*o+1);
    Y=Y*j-((2*o-7.5)*o+4.5)*o;
    o=I(k,32);
    M-=H;
    M*=o;
    Y=f(16,Y);
    Y=i(A+Y);
    Y+=U;
    Y*=o;
    d+=Y;
    d+=M;
    d=f(n,d);
    g*=o;
    g=pow(2,(g/12));
    d*=g;
    g=(d+0.5*g)/n+1.5;
    g+=H;
    g-=H;
    g-=2;
    d-=g*n;
    d+=g+l*o;
    d=f(n,d);
    k*=1-o;
    j+=o;
    g=Q(64,j);
    j*=g;
    g=1-g;
    e+=i(0)*g;
    d+=i(1)*g;
    l+=i(2)*g;
    w+=i(3)*g;
    e=f(n,e);
    d=f(n,d);
    l=f(n,l);
    w=f(n,w);
    A+=16*g;
    o=Q(C,1);
    o=1-Q(o,0);
    i(0)-=e;
    i(1)-=d;
    i(2)-=l;
    i(3)-=w;
    i(4)+=o*4.6727004911171048e-153;
    i(5)+=o*1.6937441874215991e190;
    g=exp(-E*(g+u)*C*C);
    i(0)*=g;
    i(1)*=g;
    i(2)*=g;
    i(3)*=g;
    i(4)*=g;
    i(5)*=g;
    o=exp(-o*C*C);
    o*=Q(C,3.9999e5);
    i(0)+=e;
    i(1)+=d;
    i(2)+=l;
    i(3)+=w;
    i(4)+=o*4.522871578970112e217;
    i(5)+=o*7.90055321525613e115;
    E*=Q(C/4+1,A);
    o=Q(j+E,0);
    g=pow(2,t-304-n*o);
    i(R+4)=(H+H/85+a)*g;
    i(C/4)=Z;
    C+=u;
    R+=o-1;
    Y=Q(z*E,n-1);
    Z*=1-Y;
    z+=Y*(1-n)-1;
    z*=o;
    a*=o;
    t*=o;
    o=_(j,2);
    o=1-j+o*4;
    o=_(i(R),pow(16,o));
    g=_(o,16);
    o-=g*16;
    o+=Q(o,9)*39;
    g=_(o,16);
    g*=I(j,6);
    o-=g*16;
    t+=g;
    z+=1;
    a+=o*z*Q(7,j);
    t+=o*16*Q(j,6);
    j+=1-E;
    j*=Q(C*E+8,j);
  }
  return 0;
}

引用元：https://www.ioccc.org/2015/hou/prog.c

審査員・作者による説明：https://www.ioccc.org/2015/hou/hint.html

動作

MD5の計算を行う。

$ gcc -o prog prog.c -lm

$ echo "Hello, world!" | ./prog
746308829575e17c3331bbcb00c0898b

普通のmd5sumの結果と比較すれば、正しいことがわかる。

$ echo "Hello, world!" | md5sum
746308829575e17c3331bbcb00c0898b  -

解説

一部のスクリプト言語はしばしば、double型しか持たない（JavaScript、Lua、BASICなど）。これをリスペクトして、基本的にdouble型しか使わないでMD5が計算がされている。 JavaScriptなどではdouble型に対して論理演算が使えるが、C言語では一切使えないので、難易度は非常に高くなる。

intが現れるのはprintf()の返り値と、int main()の返り値と、配列参照、getchar()、EOFだけ。 bool型も整数型なので、分岐はwhile(!printf("%s",...))の1つを除いて存在しない。ループの中は上から下へ真っ直ぐ計算するだけ。 floor()とceil()はチートな感じがするので避けたとのこと。

基本的にIEEE 754の浮動小数点数を使って頑張る。仮数部が52ビット（ケチ表現で53ビット）あるので、32ビット整数を収めることはできる。 4つの補助関数が定義されていて、関数_は32ビット整数除算、関数Qは大小比較（d > lならば1.0、そうでなければ0.0を返す）、関数’I’は等価比較（等しければ1.0を返す）、関数fは32ビット整数剰余となっている。

データを読み込んで配列に書き込んだあと、データを1ビットずつ処理するのを1つのループにしているので、C言語力とMD5計算の用法の知識が必要。 MD5は512バイトのチャンクごとに、4つのフェーズの処理を16回ずつ繰り返す、64回のループをする。このプログラムはさらに、andやxorのビット演算のために、フェーズの処理を32回のループに分けて行っていると思う。おそらくjが64回のカウンタで、oにフェーズが入っているが、詳しいことはよくわからなかった。

賞名にMost Well-roundedの語が入っているので、最優秀賞の位置づけだと思われる。