text: #!/Library/Frameworks/Python.framework/Versions/3.4/bin/python3
  #!encoding: UTF-8
  
  """
  Python implementation of Google's CityHash.
  https://code.google.com/p/cityhash/
  The process is being reproduced as it was in original implementation.
  Additional source comments are added as and when required.
  
  """
  
  # Some primes between 2^63 and 2^64 for various usage.
  K0 = 0xc3a5c85c97cb3127 #14097894508562428199
  K1 = 0xb492b66fbe98f273 #13011662864482103923
  K2 = 0x9ae16a3b2f90404f #11160318154034397263
  K3 = 0xc949d7c7509e6557 #14504361325974414679
  
  @profile
  def lower32(candidate):
      """
      Returns last 32 bits from candidate.
      """
      return candidate & 0xffffffff
  
  @profile
  def lower64(candidate):
      """
      Returns last 64 bits from candidate.
      """
      return candidate & 0xffffffffffffffff
  
  @profile
  def higher64(candidate):
      """
      Returns higher than 64 bits from candidate, by shifting lower end to right.
      """
      return candidate >> 64
  
  @profile
  def bytes(candidate):
      """
      Returns the hex-equivalent of byte-string.
      """
      result = 0x0
  
      # Reversed the candidate, and builds a list of characters returned as their corresponding Unicode code point.
      # https://docs.python.org/2/library/functions.html#ord
      characters = list(ord(character) for character in candidate[::-1])
  
      for character in characters:
          # Left shift 8 bits, and then add the current character. Automatically
          # assumes the ASCII input of string.
          result <<= 8
          result |= character
  
      return result
  
  @profile
  def hash128to64(candidate):
      """
      Hashes 128 input bits down to 64 bits of output.
      """
      kMul = 0x9ddfea08eb382d69 #11376068507788127593
      a = lower64((lower64(candidate) ^ higher64(candidate)) * kMul)
      a ^= (a >> 47)
      b = lower64((higher64(candidate) ^ a) * kMul)
      b ^= (b >> 47)
      b = b * kMul
      res = lower64(b)
      return res
  
  @profile
  def rotate(val, shift):
      """
      Bitwise right rotate.
      """
      res = val if shift == 0 else (val >> shift) | lower64((val << (64 - shift)))
      return res
  
  @profile
  def rotateByAtleast1(val, shift):
      """
      Bitwise right rotate, same as rotate, but requires shift to be non-zero.
      """
      res = (val >> shift) | lower64((val << (64 - shift)))
      return res
  
  @profile
  def shiftMix(val):
      """
      """
      res = lower64(val ^ (val >> 47))
      return res
  
  @profile
  def hashLen16(u, v):
      """
      """
      uv = (v << 64) | u
      res = hash128to64(uv)
      return res
  
  @profile
  def hashLen0to16(candidate):
      length = len(candidate)
      if length > 8:
          a = bytes(candidate[0:8])
          b = bytes(candidate[-8:-1] + candidate[-1])
          res = hashLen16(a, rotateByAtleast1(b + length, length)) ^ b
          return res
      elif length >= 4:
          a = bytes(candidate[0:4])
          res = hashLen16(length + (a << 3), bytes(candidate[-4:-1] + candidate[-1]))
          return res
      elif length > 0:
          a = bytes(candidate[0])
          b = bytes(candidate[length >> 1])
          c = bytes(candidate[length - 1])
          y = lower32(a + (b << 8))
          z = length + c * 4
          res = lower64(shiftMix(lower64(y * K2 ^ z * K3)) * K2)
          return res
      else:
          "Won't reach here."
  
  @profile
  def hashLen17To32(candidate):
      a = lower64(bytes(candidate[0:8]) * K1)
      b = bytes(candidate[8:16])
      c = lower64(bytes(candidate[-8:-1] + candidate[-1]) * K2)
      d = lower64(bytes(candidate[-16:-8]) * K0)
      res = hashLen16(lower64(rotate(lower64(a - b), 43) + rotate(c, 30) + d),
                       lower64(a + rotate(b ^ K3, 30) - c) + len(candidate))
      return res
  
  @profile
  def _weakHashLen32WithSeeds(w, x, y, z, a, b):
      a += w
      b = rotate(lower64(b + a + z), 21)
      c = a
      a += x
      a = lower64(a + y)
      b += rotate(a, 44)
      res = lower64(a+z) << 64 | lower64(b + c)
      return res
  
  @profile
  def weakHashLen32WithSeeds(candidate, a, b):
      res =  _weakHashLen32WithSeeds(bytes(candidate[0:8]),
                                     bytes(candidate[8:16]),
                                     bytes(candidate[16:24]),
                                     bytes(candidate[24:32]),
                                     a,
                                     b)
      return res
  
  @profile
  def hashLen33To64(candidate):
      """
      """
      length = len(candidate)
      z = bytes(candidate[24:32])
      a = bytes(candidate[0:8]) + (length + bytes(candidate[-16:-8])) * K0
      a = lower64(a)
      b = rotate(lower64(a + z), 52)
      c = rotate(a, 37)
      a = lower64(a + bytes(candidate[8:16]))
      c = lower64(c + rotate(a, 7))
      a = lower64(a + bytes(candidate[16:24]))
      vf = lower64(a + z)
      vs = lower64(b + rotate(a, 31) + c)
      a = bytes(candidate[16: 24]) + bytes(candidate[-32:-24])
      z = bytes(candidate[-8:-1] + candidate[-1])
      b = rotate(lower64(a + z), 52)
      c = rotate(a, 37)
      a = lower64(a + bytes(candidate[-24:-16]))
      c = lower64(c + rotate(a, 7))
      a = lower64(a + bytes(candidate[-16:-8]))
      wf = lower64(a + z)
      ws = lower64(b + rotate(a, 31) + c)
      r = shiftMix(lower64((vf + ws) * K2 + (wf + vs) + K0))
      res = lower64(shiftMix(lower64(r * K0 + vs)) * K2)
      return res
  
  @profile
  def hashLenAbove64(candidate):
      """
      """
      length = len(candidate)
      x = bytes(candidate[0:8])
      y = bytes(candidate[-16:-8]) ^ K1
      z = bytes(candidate[-56:-48]) ^ K0
      v = weakHashLen32WithSeeds(candidate[-64:-1] + candidate[-1], length, y)
      w = weakHashLen32WithSeeds(candidate[-32:-1] + candidate[-1], lower64(length * K1), K0)
  
      z = lower64(z + shiftMix(lower64(v)) * K1)
      x = lower64(rotate(lower64(z + x), 39) * K1)
      y = lower64(rotate(y, 33) * K1)
  
      length = (length - 1) & ~63
      while length is not 0:
          xrv = lower64(x + y + higher64(v) + bytes(candidate[16:24]))
          yrv = lower64(y + lower64(v) + bytes(candidate[48:56]))
          x = lower64(rotate(xrv, 37) * K1)
          y = lower64(rotate(yrv, 42) * K1)
          x = lower64(rotate(xrv, 37) * K1)
          x ^= lower64(w)
          y ^= lower64(v)
          z = rotate(z ^ higher64(w), 33)
          v = weakHashLen32WithSeeds(candidate,
                                     lower64(lower64(v) * K1),
                                     lower64(x + higher64(w)))
          w = weakHashLen32WithSeeds(candidate[32:-1] + candidate[-1],
                                     lower64(z + lower64(w)),
                                     y)
          z, x = x, z
          candidate = candidate[64:-1] + candidate[-1]
          length -= 64
  
      res =  hashLen16(lower64(hashLen16(higher64(v), higher64(w)) +
                               shiftMix(y) *
                               K1 +
                               z),
                       lower64(hashLen16(lower64(v), lower64(w)) +
                               x))
      return res
  
  @profile
  def cityMurmur(candidate, seed):
      """
      """
      length = len(candidate)
      a = lower64(seed)
      b = higher64(seed)
      c, d = 0, 0
      l = length - 16
      if l <= 0:
          a = lower64(shiftMix(lower64(a * K1)) * K1)
          c = lower64(b * K1 + hashLen0to16(candidate))
          d = shiftMix(lower64(a + (bytes(candidate[0:8]) if length >= 8 else c)))
      else:
          c = hashLen16(lower64(bytes(candidate[-8:-1] + candidate[-1]) + K1), a)
          d = hashLen16(lower64(b + length), lower64(c + bytes(candidate[-16:-8])))
          a = lower64(a + d)
          while l > 0:
              a ^= lower64(shiftMix(lower64(bytes(candidate[0:8]) * K1)) * K1)
              a = lower64(a * K1)
              b ^= a
              c ^= lower64(shiftMix(lower64(bytes(candidate[8:16]) * K1)) * K1)
              c = lower64(c * K1)
              d ^= c
              candidate = candidate[16:-1] + candidate[-1]
              l -= 16
      a = hashLen16(a, c)
      b = hashLen16(d, b)
  
      res = ((a ^ b) << 64) | hashLen16(b, a)
      return res
  
  @profile
  def hash128WithSeed(candidate, seed):
      originalCandidate = candidate
      length = len(candidate)
      if length < 128:
          res = cityMurmur(candidate, seed)
          return res
      else:
          x = lower64(seed)
          y = higher64(seed)
          z = lower64(length * K1)
  
          vf = lower64(lower64(rotate(y ^ K1, 49) * K1) + bytes(candidate[0:8]))
          vs = lower64(lower64(rotate(vf, 42) * K1) + bytes(candidate[8:16]))
          wf = lower64(lower64(rotate(lower64(y + z), 35) * K1) + x)
          ws = lower64(rotate(lower64(x + bytes(candidate[88:96])), 53) * K1)
          v = (vf << 64) | vs
          w = (wf << 64) | ws
  
          while length >= 128:
              x = lower64(rotate(lower64(x + y + vf + bytes(candidate[16:24])), 37) * K1)
              y = lower64(rotate(lower64(y + vs + bytes(candidate[48:55])), 42) * K1)
              x ^= ws
              y ^= vf
              z = rotate(z ^ wf, 33)
              v = weakHashLen32WithSeeds(candidate,
                                         lower64(z + ws),
                                         lower64(x + wf))
              w = weakHashLen32WithSeeds(candidate[32:-1] + candidate[-1],
                                         lower64(z + ws),
                                         y)
              vf, vs = higher64(v), lower64(v)
              wf, ws = higher64(w), lower64(w)
              z, x = x, z
              candidate = candidate[64:-1] + candidate[-1]
  
              x = lower64(rotate(lower64(x + y + vf + bytes(candidate[16:24])), 37) * K1)
              y = lower64(rotate(lower64(y + vs + bytes(candidate[48:56])), 42) * K1)
              z = rotate(z ^ wf, 33)
  
              v = weakHashLen32WithSeeds(candidate,
                                         lower64(vs * K1),
                                         lower64(x + wf))
              w = weakHashLen32WithSeeds(candidate[32:-1] + candidate[-1],
                                         lower64(z + ws),
                                         y)
              vf, vs = higher64(v), lower64(v)
              wf, ws = higher64(w), lower64(w)
              z, x = x, z
              candidate = candidate[64:-1] + candidate[-1]
              length -= 128
  
          y = lower64(y + rotate(wf, 37) * K0 + z)
          x = lower64(x + rotate(lower64(vf + z), 49) * K0)
  
          tail_done = 0
  
          while tail_done < length:
              tail_done += 32
              y = lower64(rotate(lower64(y - x), 42) * K0 + vs)
              wf = lower64(wf + bytes(originalCandidate[16 - tail_done:24 - tail_done]))
              x = lower64(rotate(x, 49) * K0 + wf)
              wf = lower64(wf + vf)
              v = weakHashLen32WithSeeds(originalCandidate[-tail_done:-1] + originalCandidate[-1],
                                         vf,
                                         vs)
              vf, vs = higher64(v), lower64(v)
  
          x = hashLen16(x, vf)
          y = hashLen16(y, wf)
          hf = lower64(hashLen16(lower64(x + vs), ws) + y)
          hs = lower64(hashLen16(lower64(x + ws), lower64(y + vs)))
  
          res = (hf << 64) | hs
          return res
  
  @profile
  def hash64(candidate):
      length = len(candidate)
  
      if length <= 16:
          res = hashLen0to16(candidate)
          return res
      elif length <= 32:
          res = hashLen17To32(candidate)
          return res
      elif length <= 64:
          res = hashLen33To64(candidate)
          return res
      else:
          res = hashLenAbove64(candidate)
          return res
  
  @profile
  def hash64WithSeeds(candidate, seed0, seed1):
      return hashLen16(lower64(hash64(candidate) - seed0), seed1)
  
  @profile
  def hash64WithSeed(candidate, seed):
      return hash64WithSeeds(candidate, K2, seed)
  
  @profile
  def hash128(candidate):
      length = len(candidate)
  
      if length >= 16:
          seed = ((bytes(candidate[8:16]) << 64) | (bytes(candidate[0:8]) ^ K3))
          return hash128WithSeed(candidate[16:-1] + candidate[-1], seed)
      else:
          return hash128WithSeed(candidate, (K1 << 64) | K0)
  
  hash64("test")