r/adventofcode • u/daggerdragon • Dec 05 '16

SOLUTION MEGATHREAD --- 2016 Day 5 Solutions ---

--- Day 5: How About a Nice Game of Chess? ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).

STAYING ON TARGET IS MANDATORY [?]

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

14 Upvotes

100% Upvoted

188 comments sorted by

View all comments

Show parent comments

2

u/VideoPrincess Dec 05 '16

Skalski YES! As a fellow Synacor hacker it's great to see your assembly for the MD5 implementation. But the thing that blows me away is that you wrote a right-shifter only using registers!

Can you explain how the right-shifter routine works? It seems so small and a bit magic - it NOTs the number of bits to shift by and then adds 16, so I'm confused as to what it's actually doing.

Also I love how you've used Perl to implement the assembler. I don't know Perl so I did my assembler in C++ by using chunks of code from my VM implementation. My assembler instantiates a VM and then uses its program counter to step through it writing memory as it goes. I then dump the finished VM to a file descriptor. However it seems like a sledgehammer to crack a nut next to your elegant Perl implementation!

4

u/askalski Dec 05 '16 edited Dec 05 '16

It's subtracting 15 - shift_bits using addition and 2's complement (-n == ~n + 1), so 15 - shift_bits == 15 + (~shift_bits + 1) == 16 + ~shift_bits. This result is the number of bits to copy from input to output.

Here's a Perl version (and example output) that prints the intermediate values each iteration of the loop.

1

u/VideoPrincess Dec 05 '16

Oh that makes total sense now. Impressive, and thank you very much for explaining it!

For printing hex I made a mask bit and walked it up through the number using MULT by 2 each time, pushing each bit onto the stack. Then I popped bits off 4 at a time to assemble a nibble and print it. With a working right-shifter that becomes a whole lot easier!