#include "target.h"
#include <iostream>
#include <iomanip>
#include <string.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#include "cpucycles.h"

long long innerloopcycles;

class uint32 {
  unsigned int x;
public:
  inline uint32() { }
  inline uint32(unsigned int u) { x = u; }
  inline uint32(const uint32 &a) { x = a.x; }
  inline void setbigendian(const unsigned char *s) {
    x = (((unsigned int) s[0]) << 24)
      | (((unsigned int) s[1]) << 16)
      | (((unsigned int) s[2]) << 8)
      | (((unsigned int) s[3]));
  }
  int hammingweight() { return __builtin_popcount(x); }
  friend inline uint32 operator+(uint32 a,uint32 b) { return a.x + b.x; }
  friend inline uint32 operator|(uint32 a,uint32 b) { return a.x | b.x; }
  friend inline uint32 operator&(uint32 a,uint32 b) { return a.x & b.x; }
  friend inline uint32 operator^(uint32 a,uint32 b) { return a.x ^ b.x; }
  friend inline uint32 andnot(uint32 a,uint32 b) { return a.x & ~b.x; }
  friend inline uint32 rotate1(uint32 a) { return (a.x << 1) | (a.x >> 31); }
  friend inline uint32 rotate5(uint32 a) { return (a.x << 5) | (a.x >> 27); }
  friend inline uint32 rotate30(uint32 a) { return (a.x << 30) | (a.x >> 2); }
  friend ostream& operator<<(ostream& o,const uint32& u) {
    o << hex << setw(2) << setfill('0') << ((u.x >> 24) & 255);
    o << hex << setw(2) << setfill('0') << ((u.x >> 16) & 255);
    o << hex << setw(2) << setfill('0') << ((u.x >> 8) & 255);
    o << hex << setw(2) << setfill('0') << ((u.x) & 255);
    return o;
  }
} ;

class hash {
  uint32 state[5];
public:
  hash() { }
  hash(const unsigned char *);
  int hammingweight() {
    return state[0].hammingweight()
         + state[1].hammingweight()
         + state[2].hammingweight()
         + state[3].hammingweight()
         + state[4].hammingweight();
  }
  friend inline hash operator^(hash a,hash b) {
    hash result;
    result.state[0] = a.state[0] ^ b.state[0];
    result.state[1] = a.state[1] ^ b.state[1];
    result.state[2] = a.state[2] ^ b.state[2];
    result.state[3] = a.state[3] ^ b.state[3];
    result.state[4] = a.state[4] ^ b.state[4];
    return result;
  }
  friend ostream& operator<<(ostream& o,const hash& h) {
    o << h.state[0];
    o << h.state[1];
    o << h.state[2];
    o << h.state[3];
    o << h.state[4];
    return o;
  }
  void blocks(const unsigned char *in,unsigned long long inlen) {
    uint32 a = state[0];
    uint32 b = state[1];
    uint32 c = state[2];
    uint32 d = state[3];
    uint32 e = state[4];
    uint32 f;
    uint32 x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15;
    int i;
  
    innerloopcycles -= cpucycles();
    while (inlen >= 64) {
      x0.setbigendian(in + 0);
      f = (c & b) | andnot(d,b); e = rotate5(a) + f + e + 0x5a827999 + x0; b = rotate30(b);
      x1.setbigendian(in + 4);
      f = (b & a) | andnot(c,a); d = rotate5(e) + f + d + 0x5a827999 + x1; a = rotate30(a);
      x2.setbigendian(in + 8);
      f = (a & e) | andnot(b,e); c = rotate5(d) + f + c + 0x5a827999 + x2; e = rotate30(e);
      x3.setbigendian(in + 12);
      f = (e & d) | andnot(a,d); b = rotate5(c) + f + b + 0x5a827999 + x3; d = rotate30(d);
      x4.setbigendian(in + 16);
      f = (d & c) | andnot(e,c); a = rotate5(b) + f + a + 0x5a827999 + x4; c = rotate30(c);
      x5.setbigendian(in + 20);
      f = (c & b) | andnot(d,b); e = rotate5(a) + f + e + 0x5a827999 + x5; b = rotate30(b);
      x6.setbigendian(in + 24);
      f = (b & a) | andnot(c,a); d = rotate5(e) + f + d + 0x5a827999 + x6; a = rotate30(a);
      x7.setbigendian(in + 28);
      f = (a & e) | andnot(b,e); c = rotate5(d) + f + c + 0x5a827999 + x7; e = rotate30(e);
      x8.setbigendian(in + 32);
      f = (e & d) | andnot(a,d); b = rotate5(c) + f + b + 0x5a827999 + x8; d = rotate30(d);
      x9.setbigendian(in + 36);
      f = (d & c) | andnot(e,c); a = rotate5(b) + f + a + 0x5a827999 + x9; c = rotate30(c);
      x10.setbigendian(in + 40);
      f = (c & b) | andnot(d,b); e = rotate5(a) + f + e + 0x5a827999 + x10; b = rotate30(b);
      x11.setbigendian(in + 44);
      f = (b & a) | andnot(c,a); d = rotate5(e) + f + d + 0x5a827999 + x11; a = rotate30(a);
      x12.setbigendian(in + 48);
      f = (a & e) | andnot(b,e); c = rotate5(d) + f + c + 0x5a827999 + x12; e = rotate30(e);
      x13.setbigendian(in + 52);
      f = (e & d) | andnot(a,d); b = rotate5(c) + f + b + 0x5a827999 + x13; d = rotate30(d);
      x14.setbigendian(in + 56);
      f = (d & c) | andnot(e,c); a = rotate5(b) + f + a + 0x5a827999 + x14; c = rotate30(c);
      x15.setbigendian(in + 60);
      f = (c & b) | andnot(d,b); e = rotate5(a) + f + e + 0x5a827999 + x15; b = rotate30(b);
      x0 = rotate1(x13 ^ x8 ^ x2 ^ x0);
      f = (b & a) | andnot(c,a); d = rotate5(e) + f + d + 0x5a827999 + x0; a = rotate30(a);
      x1 = rotate1(x14 ^ x9 ^ x3 ^ x1);
      f = (a & e) | andnot(b,e); c = rotate5(d) + f + c + 0x5a827999 + x1; e = rotate30(e);
      x2 = rotate1(x15 ^ x10 ^ x4 ^ x2);
      f = (e & d) | andnot(a,d); b = rotate5(c) + f + b + 0x5a827999 + x2; d = rotate30(d);
      x3 = rotate1(x0 ^ x11 ^ x5 ^ x3);
      f = (d & c) | andnot(e,c); a = rotate5(b) + f + a + 0x5a827999 + x3; c = rotate30(c);
      x4 = rotate1(x1 ^ x12 ^ x6 ^ x4);
      f = b ^ c ^ d; e = rotate5(a) + f + e + 0x6ed9eba1 + x4; b = rotate30(b);
      x5 = rotate1(x2 ^ x13 ^ x7 ^ x5);
      f = a ^ b ^ c; d = rotate5(e) + f + d + 0x6ed9eba1 + x5; a = rotate30(a);
      x6 = rotate1(x3 ^ x14 ^ x8 ^ x6);
      f = e ^ a ^ b; c = rotate5(d) + f + c + 0x6ed9eba1 + x6; e = rotate30(e);
      x7 = rotate1(x4 ^ x15 ^ x9 ^ x7);
      f = d ^ e ^ a; b = rotate5(c) + f + b + 0x6ed9eba1 + x7; d = rotate30(d);
      x8 = rotate1(x5 ^ x0 ^ x10 ^ x8);
      f = c ^ d ^ e; a = rotate5(b) + f + a + 0x6ed9eba1 + x8; c = rotate30(c);
      x9 = rotate1(x6 ^ x1 ^ x11 ^ x9);
      f = b ^ c ^ d; e = rotate5(a) + f + e + 0x6ed9eba1 + x9; b = rotate30(b);
      x10 = rotate1(x7 ^ x2 ^ x12 ^ x10);
      f = a ^ b ^ c; d = rotate5(e) + f + d + 0x6ed9eba1 + x10; a = rotate30(a);
      x11 = rotate1(x8 ^ x3 ^ x13 ^ x11);
      f = e ^ a ^ b; c = rotate5(d) + f + c + 0x6ed9eba1 + x11; e = rotate30(e);
      x12 = rotate1(x9 ^ x4 ^ x14 ^ x12);
      f = d ^ e ^ a; b = rotate5(c) + f + b + 0x6ed9eba1 + x12; d = rotate30(d);
      x13 = rotate1(x10 ^ x5 ^ x15 ^ x13);
      f = c ^ d ^ e; a = rotate5(b) + f + a + 0x6ed9eba1 + x13; c = rotate30(c);
      x14 = rotate1(x11 ^ x6 ^ x0 ^ x14);
      f = b ^ c ^ d; e = rotate5(a) + f + e + 0x6ed9eba1 + x14; b = rotate30(b);
      x15 = rotate1(x12 ^ x7 ^ x1 ^ x15);
      f = a ^ b ^ c; d = rotate5(e) + f + d + 0x6ed9eba1 + x15; a = rotate30(a);
      x0 = rotate1(x13 ^ x8 ^ x2 ^ x0);
      f = e ^ a ^ b; c = rotate5(d) + f + c + 0x6ed9eba1 + x0; e = rotate30(e);
      x1 = rotate1(x14 ^ x9 ^ x3 ^ x1);
      f = d ^ e ^ a; b = rotate5(c) + f + b + 0x6ed9eba1 + x1; d = rotate30(d);
      x2 = rotate1(x15 ^ x10 ^ x4 ^ x2);
      f = c ^ d ^ e; a = rotate5(b) + f + a + 0x6ed9eba1 + x2; c = rotate30(c);
      x3 = rotate1(x0 ^ x11 ^ x5 ^ x3);
      f = b ^ c ^ d; e = rotate5(a) + f + e + 0x6ed9eba1 + x3; b = rotate30(b);
      x4 = rotate1(x1 ^ x12 ^ x6 ^ x4);
      f = a ^ b ^ c; d = rotate5(e) + f + d + 0x6ed9eba1 + x4; a = rotate30(a);
      x5 = rotate1(x2 ^ x13 ^ x7 ^ x5);
      f = e ^ a ^ b; c = rotate5(d) + f + c + 0x6ed9eba1 + x5; e = rotate30(e);
      x6 = rotate1(x3 ^ x14 ^ x8 ^ x6);
      f = d ^ e ^ a; b = rotate5(c) + f + b + 0x6ed9eba1 + x6; d = rotate30(d);
      x7 = rotate1(x4 ^ x15 ^ x9 ^ x7);
      f = c ^ d ^ e; a = rotate5(b) + f + a + 0x6ed9eba1 + x7; c = rotate30(c);
      x8 = rotate1(x5 ^ x0 ^ x10 ^ x8);
      f = (b & c) | (b & d) | (c & d); e = rotate5(a) + f + e + 0x8f1bbcdc + x8; b = rotate30(b);
      x9 = rotate1(x6 ^ x1 ^ x11 ^ x9);
      f = (a & b) | (a & c) | (b & c); d = rotate5(e) + f + d + 0x8f1bbcdc + x9; a = rotate30(a);
      x10 = rotate1(x7 ^ x2 ^ x12 ^ x10);
      f = (e & a) | (e & b) | (a & b); c = rotate5(d) + f + c + 0x8f1bbcdc + x10; e = rotate30(e);
      x11 = rotate1(x8 ^ x3 ^ x13 ^ x11);
      f = (d & e) | (d & a) | (e & a); b = rotate5(c) + f + b + 0x8f1bbcdc + x11; d = rotate30(d);
      x12 = rotate1(x9 ^ x4 ^ x14 ^ x12);
      f = (c & d) | (c & e) | (d & e); a = rotate5(b) + f + a + 0x8f1bbcdc + x12; c = rotate30(c);
      x13 = rotate1(x10 ^ x5 ^ x15 ^ x13);
      f = (b & c) | (b & d) | (c & d); e = rotate5(a) + f + e + 0x8f1bbcdc + x13; b = rotate30(b);
      x14 = rotate1(x11 ^ x6 ^ x0 ^ x14);
      f = (a & b) | (a & c) | (b & c); d = rotate5(e) + f + d + 0x8f1bbcdc + x14; a = rotate30(a);
      x15 = rotate1(x12 ^ x7 ^ x1 ^ x15);
      f = (e & a) | (e & b) | (a & b); c = rotate5(d) + f + c + 0x8f1bbcdc + x15; e = rotate30(e);
      x0 = rotate1(x13 ^ x8 ^ x2 ^ x0);
      f = (d & e) | (d & a) | (e & a); b = rotate5(c) + f + b + 0x8f1bbcdc + x0; d = rotate30(d);
      x1 = rotate1(x14 ^ x9 ^ x3 ^ x1);
      f = (c & d) | (c & e) | (d & e); a = rotate5(b) + f + a + 0x8f1bbcdc + x1; c = rotate30(c);
      x2 = rotate1(x15 ^ x10 ^ x4 ^ x2);
      f = (b & c) | (b & d) | (c & d); e = rotate5(a) + f + e + 0x8f1bbcdc + x2; b = rotate30(b);
      x3 = rotate1(x0 ^ x11 ^ x5 ^ x3);
      f = (a & b) | (a & c) | (b & c); d = rotate5(e) + f + d + 0x8f1bbcdc + x3; a = rotate30(a);
      x4 = rotate1(x1 ^ x12 ^ x6 ^ x4);
      f = (e & a) | (e & b) | (a & b); c = rotate5(d) + f + c + 0x8f1bbcdc + x4; e = rotate30(e);
      x5 = rotate1(x2 ^ x13 ^ x7 ^ x5);
      f = (d & e) | (d & a) | (e & a); b = rotate5(c) + f + b + 0x8f1bbcdc + x5; d = rotate30(d);
      x6 = rotate1(x3 ^ x14 ^ x8 ^ x6);
      f = (c & d) | (c & e) | (d & e); a = rotate5(b) + f + a + 0x8f1bbcdc + x6; c = rotate30(c);
      x7 = rotate1(x4 ^ x15 ^ x9 ^ x7);
      f = (b & c) | (b & d) | (c & d); e = rotate5(a) + f + e + 0x8f1bbcdc + x7; b = rotate30(b);
      x8 = rotate1(x5 ^ x0 ^ x10 ^ x8);
      f = (a & b) | (a & c) | (b & c); d = rotate5(e) + f + d + 0x8f1bbcdc + x8; a = rotate30(a);
      x9 = rotate1(x6 ^ x1 ^ x11 ^ x9);
      f = (e & a) | (e & b) | (a & b); c = rotate5(d) + f + c + 0x8f1bbcdc + x9; e = rotate30(e);
      x10 = rotate1(x7 ^ x2 ^ x12 ^ x10);
      f = (d & e) | (d & a) | (e & a); b = rotate5(c) + f + b + 0x8f1bbcdc + x10; d = rotate30(d);
      x11 = rotate1(x8 ^ x3 ^ x13 ^ x11);
      f = (c & d) | (c & e) | (d & e); a = rotate5(b) + f + a + 0x8f1bbcdc + x11; c = rotate30(c);
      x12 = rotate1(x9 ^ x4 ^ x14 ^ x12);
      f = b ^ c ^ d; e = rotate5(a) + f + e + 0xca62c1d6 + x12; b = rotate30(b);
      x13 = rotate1(x10 ^ x5 ^ x15 ^ x13);
      f = a ^ b ^ c; d = rotate5(e) + f + d + 0xca62c1d6 + x13; a = rotate30(a);
      x14 = rotate1(x11 ^ x6 ^ x0 ^ x14);
      f = e ^ a ^ b; c = rotate5(d) + f + c + 0xca62c1d6 + x14; e = rotate30(e);
      x15 = rotate1(x12 ^ x7 ^ x1 ^ x15);
      f = d ^ e ^ a; b = rotate5(c) + f + b + 0xca62c1d6 + x15; d = rotate30(d);
      x0 = rotate1(x13 ^ x8 ^ x2 ^ x0);
      f = c ^ d ^ e; a = rotate5(b) + f + a + 0xca62c1d6 + x0; c = rotate30(c);
      x1 = rotate1(x14 ^ x9 ^ x3 ^ x1);
      f = b ^ c ^ d; e = rotate5(a) + f + e + 0xca62c1d6 + x1; b = rotate30(b);
      x2 = rotate1(x15 ^ x10 ^ x4 ^ x2);
      f = a ^ b ^ c; d = rotate5(e) + f + d + 0xca62c1d6 + x2; a = rotate30(a);
      x3 = rotate1(x0 ^ x11 ^ x5 ^ x3);
      f = e ^ a ^ b; c = rotate5(d) + f + c + 0xca62c1d6 + x3; e = rotate30(e);
      x4 = rotate1(x1 ^ x12 ^ x6 ^ x4);
      f = d ^ e ^ a; b = rotate5(c) + f + b + 0xca62c1d6 + x4; d = rotate30(d);
      x5 = rotate1(x2 ^ x13 ^ x7 ^ x5);
      f = c ^ d ^ e; a = rotate5(b) + f + a + 0xca62c1d6 + x5; c = rotate30(c);
      x6 = rotate1(x3 ^ x14 ^ x8 ^ x6);
      f = b ^ c ^ d; e = rotate5(a) + f + e + 0xca62c1d6 + x6; b = rotate30(b);
      x7 = rotate1(x4 ^ x15 ^ x9 ^ x7);
      f = a ^ b ^ c; d = rotate5(e) + f + d + 0xca62c1d6 + x7; a = rotate30(a);
      x8 = rotate1(x5 ^ x0 ^ x10 ^ x8);
      f = e ^ a ^ b; c = rotate5(d) + f + c + 0xca62c1d6 + x8; e = rotate30(e);
      x9 = rotate1(x6 ^ x1 ^ x11 ^ x9);
      f = d ^ e ^ a; b = rotate5(c) + f + b + 0xca62c1d6 + x9; d = rotate30(d);
      x10 = rotate1(x7 ^ x2 ^ x12 ^ x10);
      f = c ^ d ^ e; a = rotate5(b) + f + a + 0xca62c1d6 + x10; c = rotate30(c);
      x11 = rotate1(x8 ^ x3 ^ x13 ^ x11);
      f = b ^ c ^ d; e = rotate5(a) + f + e + 0xca62c1d6 + x11; b = rotate30(b);
      x12 = rotate1(x9 ^ x4 ^ x14 ^ x12);
      f = a ^ b ^ c; d = rotate5(e) + f + d + 0xca62c1d6 + x12; a = rotate30(a);
      x13 = rotate1(x10 ^ x5 ^ x15 ^ x13);
      f = e ^ a ^ b; c = rotate5(d) + f + c + 0xca62c1d6 + x13; e = rotate30(e);
      x14 = rotate1(x11 ^ x6 ^ x0 ^ x14);
      f = d ^ e ^ a; b = rotate5(c) + f + b + 0xca62c1d6 + x14; d = rotate30(d);
      x15 = rotate1(x12 ^ x7 ^ x1 ^ x15);
      f = c ^ d ^ e; a = rotate5(b) + f + a + 0xca62c1d6 + x15; c = rotate30(c);
  
      a = a + state[0];
      b = b + state[1];
      c = c + state[2];
      d = d + state[3];
      e = e + state[4];
      state[0] = a;
      state[1] = b;
      state[2] = c;
      state[3] = d;
      state[4] = e;
  
      inlen -= 64;
      in += 64; 
    }
    innerloopcycles += cpucycles();
  }
} ;

hash::hash(const unsigned char *in)
{
  unsigned long long inlen = 0;
  while (in[inlen]) ++inlen;
  unsigned long long bits = inlen << 3;

  unsigned char padded[128];
  int i;
  state[0] = 0x67452301;
  state[1] = 0xefcdab89;
  state[2] = 0x98badcfe;
  state[3] = 0x10325476;
  state[4] = 0xc3d2e1f0;

  blocks(in,inlen);
  in += inlen;
  inlen &= 63;
  in -= inlen;

  for (i = 0;i < inlen;++i) padded[i] = in[i];
  padded[inlen] = 0x80;

  if (inlen < 56) {
    for (i = inlen + 1;i < 56;++i) padded[i] = 0;
    padded[56] = bits >> 56;
    padded[57] = bits >> 48;
    padded[58] = bits >> 40;
    padded[59] = bits >> 32;
    padded[60] = bits >> 24;
    padded[61] = bits >> 16;
    padded[62] = bits >> 8;
    padded[63] = bits;
    blocks(padded,64);
  } else {
    for (i = inlen + 1;i < 120;++i) padded[i] = 0;
    padded[120] = bits >> 56;
    padded[121] = bits >> 48;
    padded[122] = bits >> 40;
    padded[123] = bits >> 32;
    padded[124] = bits >> 24;
    padded[125] = bits >> 16;
    padded[126] = bits >> 8;
    padded[127] = bits;
    blocks(padded,128);
  }
}

const char ALPHABET[64] =
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ/_";

#define ALPHABETUSED 32

int main()
{
  int i;
  int c0;
  int c1;
  int c2;
  int c3;
  int c4;
  long long startcycles = cpucycles();
  long long hashes = 1;
  
  hash targethash(target);

  cout << 0 << " " << targethash << " " << target << "\n";

  unsigned char flip[sizeof s];

  long long slen = 0;
  while (s[slen]) ++slen;
  if (slen < 5) return 100;

#ifndef NONRANDOM
  srandom(cpucycles()); // XXX: randomize better
#endif

  for (i = 0;i < slen;++i) {
    flip[i] = 0;
    if (random() & 1) if (s[i] != ' ') s[i] ^= 32;
  }

  for (;;) {
    for (c0 = 0;c0 < ALPHABETUSED;++c0) {
      s[slen - 5] = ALPHABET[c0];
      cout << "cycles/hash " << dec
        << (cpucycles() - startcycles) / hashes << " "
        << (innerloopcycles) / hashes << " "
        << s << "\n";
      for (c1 = 0;c1 < ALPHABETUSED;++c1) {
	s[slen - 4] = ALPHABET[c1];
        for (c2 = 0;c2 < ALPHABETUSED;++c2) {
	  s[slen - 3] = ALPHABET[c2];
          for (c3 = 0;c3 < ALPHABETUSED;++c3) {
	    s[slen - 2] = ALPHABET[c3];
            for (c4 = 0;c4 < ALPHABETUSED;++c4) {
	      s[slen - 1] = ALPHABET[c4];
              int d = (hash(s) ^ targethash).hammingweight();
              if (d < 49) cout << dec << d << " " << hash(s) << " " << s << "\n" << flush;
	    }
	    hashes += c4;
	  }
	}
      }
    }

    for (i = 0;i < slen - 5;++i) if (s[i] != ' ') {
      s[i] ^= 32;
      flip[i] ^= 32;
      if (flip[i]) break;
    }

    if (i == slen - 5) return 0;
  }
}