WARNING WARNING WARNING: This software is a crude prototype. It has many obvious deficiencies, both internal and external. I haven't done even a single test of whether the DAGs compute the functions that they're supposed to compute.
wget https://cr.yp.to/cipherdag/20070924/dagbit.h wget https://cr.yp.to/cipherdag/20070924/dagbit8.h wget https://cr.yp.to/cipherdag/20070924/dagbit16.h wget https://cr.yp.to/cipherdag/20070924/dagbit32.h wget https://cr.yp.to/cipherdag/20070924/dagbit.cpp wget https://cr.yp.to/cipherdag/20070924/dagbitn.cpp wget https://cr.yp.to/cipherdag/20070924/dagbit8.cpp wget https://cr.yp.to/cipherdag/20070924/dagbit16.cpp wget https://cr.yp.to/cipherdag/20070924/dagbit32.cpp wget https://cr.yp.to/cipherdag/20070924/md5.cpp wget https://cr.yp.to/cipherdag/20070924/dagy chmod 755 dagy g++ -fomit-frame-pointer \ -o md5 md5.cpp dagbit32.cpp dagbit16.cpp dagbit8.cpp dagbit.cpp ./md5 > md5.out ./dagy < md5.out > md5.yThe DAG is placed into md5.y.
The dagbit functions are general-purpose tools. The md5.cpp code is an easy modification of preexisting MD5 software.
The dagy script is a reflection of the inadequate time that I spent thinking about DAG data formats. Perhaps I should change dagbit to produce the same output format directly; perhaps I should change the other scripts to handle what dagbit does now; or perhaps, after further thought, I'll end up changing everything to support another format.
aptitude install libx11-dev wget https://cr.yp.to/cipherdag/20070924/draw.c wget https://cr.yp.to/cipherdag/20070924/font.c wget https://cr.yp.to/cipherdag/20070924/font.h gcc -std=c99 -O2 -fomit-frame-pointer \ -o draw draw.c font.c -lX11 -lm ./draw < md5.y
aptitude install original-awk wget https://cr.yp.to/cipherdag/20070924/dagcollapse wget https://cr.yp.to/cipherdag/20070924/dagpull wget https://cr.yp.to/cipherdag/20070924/dagsort wget https://cr.yp.to/cipherdag/20070924/dagxinit wget https://cr.yp.to/cipherdag/20070924/dagxslide chmod 755 dagcollapse chmod 755 dagpull chmod 755 dagsort chmod 755 dagxinit chmod 755 dagxslide ./dagpull < md5.y > md5.pull ./dagxslide < md5.pull > md5.ps ./dagsort < md5.ps > md5.x ./dagxinit < md5.x > md5.xa ./dagcollapse < md5.xa > md5.xc ./dagcollapse < md5.xc > md5.xd ./dagxinit < md5.xd > md5.xi ./dagxslide < md5.xi > md5.xs ./dagsort < md5.xs > md5.xyBeware that dagpull creates a very large DAG (more than 400000 nodes), and dagxslide takes a long time to handle that DAG. But it does finish eventually.
I used original-awk in these scripts because mawk (shipped under Linux as awk) died with an internal memory error. I don't know how original-awk compares to mawk in speed.
There are previous graph-layout tools, notably the dot program from the graphviz package. However, I wasn't able to convince those tools to handle anything as large as the MD5 DAG.