Java implementation of CityHash 1.0.3 that behaves as same hash function as BigQuery.

CityHash_1_0_3.java

/*
 * Copyright (C) 2012 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

/*
 * Modifications copyright (C) 2017 Daisuke Matsumoto
 *
 * Java implementation of CityHash 1.0.3 that behaves as same hash function as BigQuery.
 * Ported from https://codereview.appspot.com/5989072/patch/12001/13003
 *
 * Modifications from original implementation are
 *   1. Add easy interface to call the algorithm
 *   2. Remove Seedless/Seeded, 128 bits algorithms that are not used in BigQuery
 *   3. Remove dependency to Guava library
 */

import java.lang.reflect.Field;
import java.nio.ByteOrder;
import java.nio.charset.StandardCharsets;
import java.security.AccessController;
import java.security.PrivilegedAction;

import sun.misc.Unsafe;

public class CityHash_1_0_3 {
  public static long cityHash64(String src) {
    return cityHash64(src.getBytes(StandardCharsets.UTF_8));
  }
  public static long cityHash64(byte[] src) {
    return cityHash64(src, 0, src.length);
  }
  public static long cityHash64(byte[] src, int off, int len) {
    return CityHashFunctions.cityHash64(src, off, len);
  }
}

class Ints {
  static int fromBytes(byte b1, byte b2, byte b3, byte b4) {
    return b1 << 24 | (b2 & 0xFF) << 16 | (b3 & 0xFF) << 8 | (b4 & 0xFF);
  }
}

class Longs {
  static long fromBytes(byte b1, byte b2, byte b3, byte b4,
      byte b5, byte b6, byte b7, byte b8) {
    return (b1 & 0xFFL) << 56
        | (b2 & 0xFFL) << 48
        | (b3 & 0xFFL) << 40
        | (b4 & 0xFFL) << 32
        | (b5 & 0xFFL) << 24
        | (b6 & 0xFFL) << 16
        | (b7 & 0xFFL) << 8
        | (b8 & 0xFFL);
  }
}

class UnsignedBytes {
  private static final int UNSIGNED_MASK = 0xFF;
  static int toInt(byte value) {
    return value & UNSIGNED_MASK;
  }
}

class UnsignedInts {
  static final long INT_MASK = 0xffffffffL;
  static long toLong(int value) {
    return value & INT_MASK;
  }
}

final class CityHashFunctions {
  private CityHashFunctions() {}

  private static final long K0 = 0xc3a5c85c97cb3127L;
  private static final long K1 = 0xb492b66fbe98f273L;
  private static final long K2 = 0x9ae16a3b2f90404fL;
  private static final long K3 = 0xc949d7c7509e6557L;

  static final boolean PLATFORM_IS_LITTLE_ENDIAN =
      ByteOrder.nativeOrder().equals(ByteOrder.LITTLE_ENDIAN);

  private interface ArrayGetter {
    long getLongLittleEndian(byte[] array, int offset);

    int getIntLittleEndian(byte[] array, int offset);
  }

  /*
   * Borrowing the trick from UnsignedBytes.lexicographicalComparator(),
   * we deliberately set it up so that we only attempt to get the Unsafe
   * when the UnsafeLongGetter class is being loaded.
   */
  @SuppressWarnings("unused") // the class is accessed reflectively!
  private enum UnsafeArrayGetter implements ArrayGetter {
    UNSAFE_LITTLE_ENDIAN {
      @Override
      public long getLongLittleEndian(byte[] array, int offset) {
        return theUnsafe.getLong(array, (long) offset + BYTE_ARRAY_BASE_OFFSET);
      }

      @Override
      public int getIntLittleEndian(byte[] array, int offset) {
        return theUnsafe.getInt(array, (long) offset + BYTE_ARRAY_BASE_OFFSET);
      }
    },
    UNSAFE_BIG_ENDIAN {
      @Override
      public long getLongLittleEndian(byte[] array, int offset) {
        long bigEndian = theUnsafe.getLong(array, (long) offset + BYTE_ARRAY_BASE_OFFSET);
        // The hardware is big-endian, so we need to reverse the order of the bytes.
        return Long.reverseBytes(bigEndian);
      }

      @Override
      public int getIntLittleEndian(byte[] array, int offset) {
        int bigEndian = theUnsafe.getInt(array, (long) offset + BYTE_ARRAY_BASE_OFFSET);
        // The hardware is big-endian, so we need to reverse the order of the bytes.
        return Integer.reverseBytes(bigEndian);
      }
    };

    static final Unsafe theUnsafe;

    /** The offset to the first element in a byte array. */
    static final int BYTE_ARRAY_BASE_OFFSET;

    static {
      theUnsafe = (Unsafe) AccessController.doPrivileged(
          new PrivilegedAction<Object>() {
            @Override
            public Object run() {
              try {
                Field f = Unsafe.class.getDeclaredField("theUnsafe");
                f.setAccessible(true);
                return f.get(null);
              } catch (NoSuchFieldException e) {
                // It doesn't matter what we throw;
                // it's swallowed in getBestComparator().
                throw new Error();
              } catch (IllegalAccessException e) {
                throw new Error();
              }
            }
          });

      BYTE_ARRAY_BASE_OFFSET = theUnsafe.arrayBaseOffset(byte[].class);

      // sanity check - this should never fail
      if (theUnsafe.arrayIndexScale(byte[].class) != 1) {
        throw new AssertionError();
      }
    }
  }

  private enum JavaArrayGetter implements ArrayGetter {
    INSTANCE {
      @Override
      public long getLongLittleEndian(byte[] src, int off) {
        return Longs.fromBytes(
            src[off + 7],
            src[off + 6],
            src[off + 5],
            src[off + 4],
            src[off + 3],
            src[off + 2],
            src[off + 1],
            src[off]);
      }

      @Override
      public int getIntLittleEndian(byte[] src, int off) {
        return Ints.fromBytes(
            src[off + 3],
            src[off + 2],
            src[off + 1],
            src[off]);
      }
    };
  }

  private static final ArrayGetter arrayGetter;

  static final String UNSAFE_ARRAY_GETTER_NAME =
      CityHashFunctions.class.getName() + "$UnsafeArrayGetter";
  static {
    ArrayGetter theGetter;
    try {
      Class<?> theClass = Class.forName(UNSAFE_ARRAY_GETTER_NAME);

      ArrayGetter[] getters = (ArrayGetter[]) theClass.getEnumConstants();

      theGetter = PLATFORM_IS_LITTLE_ENDIAN ? getters[0] : getters[1];
    } catch (Throwable t) { // ensure we really catch *everything*
      theGetter = JavaArrayGetter.INSTANCE;
    }
    arrayGetter = theGetter;
  }

  private static long shiftMix(long val) {
    return val ^ (val >>> 47);
  }

  private static long hashLen16(long u, long v) {
    long a = shiftMix((v ^ u) * K_MUL);
    return shiftMix((v ^ a) * K_MUL) * K_MUL;
  }

  private static final long K_MUL = 0x9ddfea08eb382d69L;

  private static long getLong(byte[] src, int off) {
    return arrayGetter.getLongLittleEndian(src, off);
  }

  private static int getInt(byte[] src, int off) {
    return arrayGetter.getIntLittleEndian(src, off);
  }

  private static long hashLen0To16(byte[] src, int off, int len) {
    if (len > 8) {
      long a = getLong(src, off);
      long b = getLong(src, off + len - 8);
      return hashLen16(a, Long.rotateRight(b + len, len)) ^ b;
    } else if (len >= 4) {
      long a = UnsignedInts.toLong(getInt(src, off));
      long b = UnsignedInts.toLong(getInt(src, off + len - 4));
      return hashLen16(len + (a << 3), b);
    } else if (len > 0) {
      byte a = src[off];
      byte b = src[off + (len >> 1)];
      byte c = src[off + len - 1];
      int y = UnsignedBytes.toInt(a) + (UnsignedBytes.toInt(b) << 8);
      int z = len + (UnsignedBytes.toInt(c) << 2);
      return shiftMix(y * K2 ^ z * K3) * K2;
    }
    return K2;
  }

  private static long hashLen17To32(byte[] src, int off, int len) {
    long a = getLong(src, off) * K1;
    long b = getLong(src, off + 8);
    long c = getLong(src, off + len - 8) * K2;
    long d = getLong(src, off + len - 16) * K0;
    return hashLen16(Long.rotateRight(a - b, 43) + Long.rotateRight(c, 30) + d,
        a + Long.rotateRight(b ^ K3, 20) - c + len);
  }

  private static void weakHashLen32WithSeeds(long[] result,
      long w, long x, long y, long z, long a, long b) {
    a += w;
    b = Long.rotateRight(b + a + z, 21);
    long c = a;
    a += x + y;
    b += Long.rotateRight(a, 44);
    result[0] = a + z;
    result[1] = b + c;
  }

  private static void weakHashLen32WithSeeds(
      long[] result,
      byte[] src, int off,
      long a, long b) {
    weakHashLen32WithSeeds(
        result,
        getLong(src, off),
        getLong(src, off + 8),
        getLong(src, off + 16),
        getLong(src, off + 24),
        a,
        b);
  }

  private static long hashLen33To64(byte[] src, int off, int len) {
    long z = getLong(src, off + 24);
    long a = getLong(src, off) + (len + getLong(src, off + len - 16)) * K0;
    long b = Long.rotateRight(a + z, 52);
    long c = Long.rotateRight(a, 37);
    a += getLong(src, off + 8);
    c += Long.rotateRight(a, 7);
    a += getLong(src, off + 16);
    long vf = a + z;
    long vs = b + Long.rotateRight(a, 31) + c;
    a = getLong(src, off + 16) + getLong(src, off + len - 32);
    z = getLong(src, off + len - 8);
    b = Long.rotateRight(a + z, 52);
    c = Long.rotateRight(a, 37);
    a += getLong(src, off + len - 24);
    c += Long.rotateRight(a, 7);
    a += getLong(src, off + len - 16);
    long wf = a + z;
    long ws = b + Long.rotateRight(a, 31) + c;
    long r = shiftMix((vf + ws) * K2 + (wf + vs) * K0);
    return shiftMix(r * K0 + vs) * K2;
  }

  static long cityHash64(byte[] src, int off, int len) {
    if (len <= 32) {
      if (len <= 16) {
        return hashLen0To16(src, off, len);
      } else {
        return hashLen17To32(src, off, len);
      }
    } else if (len <= 64) {
      return hashLen33To64(src, off, len);
    }

    long x = getLong(src, off + len - 40);
    long y = getLong(src, off + len - 16) + getLong(src, off + len - 56);
    long z = hashLen16(getLong(src, off + len - 48) + len, getLong(src, off + len - 24));

    long[] v = new long[2];
    long[] w = new long[2];

    weakHashLen32WithSeeds(v, src, off + len - 64, len, z);
    weakHashLen32WithSeeds(w, src, off + len - 32, y + K1, x);
    x = x * K1 + getLong(src, off);

    len = (len - 1) & (~63);
    do {
      x = Long.rotateRight(x + y + v[0] + getLong(src, off + 8), 37) * K1;
      y = Long.rotateRight(y + v[1] + getLong(src, off + 48), 42) * K1;
      x ^= w[1];
      y += v[0] + getLong(src, off + 40);
      z = Long.rotateRight(z + w[0], 33) * K1;
      weakHashLen32WithSeeds(v, src, off, v[1] * K1, x + w[0]);
      weakHashLen32WithSeeds(w, src, off + 32, z + w[1], y + getLong(src, off + 16));

      long tmp = x;
      x = z;
      z = tmp;

      len -= 64;
      off += 64;
    } while (len != 0);
    return hashLen16(hashLen16(v[0], w[0]) + shiftMix(y) * K1 + z,
        hashLen16(v[1], w[1]) + x);
  }
}

This (and Guava's) implementation of cityHash64 is different from one in the Google code:
https://github.com/google/cityhash/blob/8eded14d8e7cabfcdb10d4be35d521683edc0407/src/city.cc

Here is the same implementation:

    public static long cityHash64(byte[] src, int off, int len) {
        checkPositionIndexes(off, off + len, src.length);
        if (len <= 32) {
            if (len <= 16) {
                return hashLen0To16(src, off, len);
            } else {
                return hashLen17To32(src, off, len);
            }
        } else if (len <= 64) {
            return hashLen33To64(src, off, len);
        }

        long x = getLong(src, off);
        long y = getLong(src, off + len - 16) ^ K1;
        long z = getLong(src, off + len - 56) ^ K0;

        long[] v = new long[2];
        weakHashLen32WithSeeds(v, src, off + len - 64, len, y);

        long[] w = new long[2];
        weakHashLen32WithSeeds(w, src, off + len - 32, len * K1, K0);

        z += shiftMix(v[1]) * K1;
        x = Long.rotateRight(z + x, 39) * K1;
        y = Long.rotateRight(y, 33) * K1;

        len = (len - 1) & (~63);
        do {
            x = Long.rotateRight(x + y + v[0] + getLong(src, off + 16), 37) * K1;
            y = Long.rotateRight(y + v[1] + getLong(src, off + 48), 42) * K1;
            x ^= w[1];
            y ^= v[0];
            z = Long.rotateRight(z ^ w[0], 33);
            weakHashLen32WithSeeds(v, src, off, v[1] * K1, x + w[0]);
            weakHashLen32WithSeeds(w, src, off + 32, z + w[1], y);

            long tmp = x;
            x = z;
            z = tmp;

            len -= 64;
            off += 64;
        } while (len != 0);
        return hashLen16(hashLen16(v[0], w[0]) + shiftMix(y) * K1 + z,
                hashLen16(v[1], w[1]) + x);
    }

And here are tests for it:

import junit.framework.TestCase;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

// https://github.com/google/cityhash/blob/8eded14d8e7cabfcdb10d4be35d521683edc0407/src/city-test.cc
@RunWith(Parameterized.class)
public class CityHashTest extends TestCase {
    private static final long k0 = 0xc3a5c85c97cb3127L;
    private static final int kTestSize = 300;
    private static final byte[] data = new byte[1 << 20];
    private static final long[][] testdata = {
            {0x9ae16a3b2f90404fL},
            {0x75e9dee28ded761dL},
            {0x75de892fdc5ba914L},
            {0x69cfe9fca1cc683aL},
            {0x675b04c582a34966L},
            {0x46fa817397ea8b68L},
            {0x406e959cdffadec7L},
            {0x46663908b4169b95L},
            {0xf214b86cffeab596L},
            {0xeba670441d1a4f7dL},
            {0x172c17ff21dbf88dL},
            {0x5a0838df8a019b8cL},
            {0x8f42b1fbb2fc0302L},
            {0x72085e82d70dcea9L},
            {0x32b75fc2223b5032L},
            {0xe1dd010487d2d647L},
            {0x2994f9245194a7e2L},
            {0x32e2ed6fa03e5b22L},
            {0x37a72b6e89410c9fL},
            {0x10836563cb8ff3a1L},
            {0x4dabcb5c1d382e5cL},
            {0x296afb509046d945L},
            {0xf7c0257efde772eaL},
            {0x61e021c8da344ba1L},
            {0xc0a86ed83908560bL},
            {0x35c9cf87e4accbf3L},
            {0xe74c366b3091e275L},
            {0xa3f2ca45089ad1a6L},
            {0xe5181466d8e60e26L},
            {0xfb528a8dd1e48ad7L},
            {0xda6d2b7ea9d5f9b6L},
            {0x61d95225bc2293eL},
            {0x81247c01ab6a9cc1L},
            {0xc17f3ebd3257cb8bL},
            {0x9802438969c3043bL},
            {0x3dd8ed248a03d754L},
            {0xc5bf48d7d3e9a5a3L},
            {0xbc4a21d00cf52288L},
            {0x172c8674913ff413L},
            {0x17a361dbdaaa7294L},
            {0x5cc268bac4bd55fL},
            {0xdb04969cc06547f1L},
            {0x25bd8d3ca1b375b2L},
            {0x166c11fbcbc89fd8L},
            {0x3565bcc4ca4ce807L},
            {0xb7897fd2f274307dL},
            {0xaba98113ab0e4a16L},
            {0x17f7796e0d4b636cL},
            {0x33c0128e62122440L},
            {0x988bc5d290b97aefL},
            {0x23c8c25c2ab72381L},
            {0x450fe4acc4ad3749L},
            {0x48e1eff032d90c50L},
            {0xc048604ba8b6c753L},
            {0x67ff1cbe469ebf84L},
            {0xb45c7536bd7a5416L},
            {0x215c2eaacdb48f6fL},
            {0x241baf16d80e0fe8L},
            {0xd10a9743b5b1c4d1L},
            {0x919ef9e209f2edd1L},
            {0xb5f9519b6c9280bL},
            {0x77a75e89679e6757L},
            {0x9d709e1b086aabe2L},
            {0x91c89971b3c20a8aL},
            {0x16468c55a1b3f2b4L},
            {0x8015f298161f861eL},
            {0x71e244d7e2843a41L},
            {0x5d3cb0d2c7ccf11fL},
            {0xd6cffe6c223aba65L},
            {0x8a17c5054e85e2beL},
            {0x77d112a0b7084c6aL},
            {0x708f2a6e8bd57583L},
            {0x50bc8f76b62c8de9L},
            {0x8b15a656b553641aL},
            {0x6ba74ccf722a52beL},
            {0xfb317bb7533454d0L},
            {0x8eec643f62c90feaL},
            {0x81ce6becdf10dff2L},
            {0x549c669fb0049f69L},
            {0x2b6a3433940bbf2dL},
            {0xd80b7a3c691401b7L},
            {0xab3bf6b494f66ef3L},
            {0x83f7b824a3911d44L},
            {0x3fb8d482d0d9d03fL},
            {0xad346a1f100b3944L},
            {0xdb210eb547a3dbc5L},
            {0xe55fab4f920abdc0L},
            {0x3b530fff7e848c5eL},
            {0xbde3379279d1cae1L},
            {0x4008062bc7755b37L},
            {0x76a66ce0ee8094d1L},
            {0x2bc3dfb3b1756918L},
            {0xd060dc1e8ca204eeL},
            {0xc8ec4fc839254a74L},
            {0x7cdf98a07b1315b0L},
            {0x78284cb5c0143ed8L},
            {0x5c2c485bdc8e3317L},
            {0x6e38acb798627f75L},
            {0xc5fb48f0939b4878L},
            {0x292da6390260110L},
            {0x1e0ee26b7044741bL},
            {0x69b8f7e762db77ecL},
            {0x9b321366d6585031L},
            {0x9375c89169bf70cfL},
            {0xa8db1643cc52d94dL},
            {0xcf7a9ea6a7a30deeL},
            {0x42c2e9f84dc7f129L},
            {0x394c2c1cca4e9271L},
            {0xd38df9e9740cb16cL},
            {0xec12466d1379cfdfL},
            {0x9050986d9ced6a2eL},
            {0xc7362967930e8a48L},
            {0x47bd8137d464eab3L},
            {0xcff30d9303db2dfeL},
            {0x8d086fc30b6694b2L},
            {0xb7d681356bdd9e4fL},
            {0x5bb01fcb2e6ad355L},
            {0xcd2ff001a80d1b11L},
            {0x8bfbf611401100cdL},
            {0xec9ae0cf9290d012L},
            {0x4ac2a5e9dc03176dL},
            {0x5fd51f635bc557a8L},
            {0xec3521e8efdb1779L},
            {0xa9147f0fb2e38bb1L},
            {0xa080e609751f2e81L},
            {0x3bc578f69905fa2dL},
            {0x9e6a5e0641d1c0d9L},
            {0x83b0cdb3c934c679L},
            {0xf174161497c5fa97L},
            {0xd7262cb2f2755e70L},
            {0x1444ce264e8784b7L},
            {0x532e6b5c95a2e229L},
            {0x183d112159f539ebL},
            {0x8f18272400b3ace9L},
            {0x43761e6a5f6f2fd6L},
            {0x44f615fcd096fbfeL},
            {0x27613f9db818cf78L},
            {0x3f6984c7afaebd0bL},
            {0x8fc511284f47c772L},
            {0x15ae5f12f88592e2L},
            {0x905f995bddf92cb7L},
            {0xa23ac6bef8905fecL},
            {0x403b94a75160a06bL},
            {0x14d1ee05672fc19bL},
            {0xf59376c617951a2aL},
            {0x63982fdc37a9dc5L},
            {0xeb480334ed838b48L},
            {0xd0b9004efa0a1164L},
            {0xb31f2b6cc2a15506L},
            {0x4f9da8a709bec12fL},
            {0x5504000602e6f8cfL},
            {0x2d022d82f513a883L},
            {0xa87268205997eddbL},
            {0xfde5f0a803c3affcL},
            {0xfa46e0e215c1aabdL},
            {0x7e1f98b2c16f8b2bL},
            {0x65a58d22d8665e60L},
            {0xb781b9a55e7d6ab9L},
            {0xa88c857b1aeb0835L},
            {0x2a25994979124643L},
            {0x17236ed61e669c6fL},
            {0x304f56359ac375a8L},
            {0x2e236ded6ce34194L},
            {0x837ecb10d69f9bb9L},
            {0xc94bc80993d726f2L},
            {0x463b54729349357aL},
            {0x52e298a69bc61248L},
            {0xf31bde28294be223L},
            {0xd1d98f3bbaf26f1eL},
            {0x77969267e761a5e2L},
            {0x763f1101a3d8e5d6L},
            {0xb6ffcab942c26180L},
            {0x65a85965268277a5L},
            {0x6579248c4cabcf91L},
            {0xfcea6deb6fbc95deL},
            {0xa5afb4dac88f15f0L},
            {0x35f437b7acbfd454L},
            {0x8f45f63a2f2d77d5L},
            {0x62258e6fe64ea749L},
            {0xfc109f4192ba2587L},
            {0x5364968136715e44L},
            {0xdd84538848e07acbL},
            {0x397d78f9c2fb2a8aL},
            {0xa3a22aed573f4128L},
            {0x94bcd5be64b0caf0L},
            {0x81d9fe1f35fe8dcL},
            {0xaa21f88e4310c4aaL},
            {0x88e65c8bd8fd0dc3L},
            {0xee7c287c7a74eaf6L},
            {0x59492bfd26df7a46L},
            {0x79471e68a2e7b4c3L},
            {0xf806f8b0f54bbbf4L},
            {0xaf0a9fa8d197fc2aL},
            {0xa93491c935028bfdL},
            {0x35fb344f57414e7eL},
            {0x650c588ae7997006L},
            {0x8e83c18ec4fac9b2L},
            {0x35422c6582e3fa2eL},
            {0xfc0cb7f55d516f4eL},
            {0xe6245e6273cd7da4L},
            {0xbfb40261b25b0146L},
            {0x298876b240a1f937L},
            {0xbf26833d8f21542eL},
            {0xff85120bd8fa3cd4L},
            {0xa37277b9eb9b16fcL},
            {0xb95c558eb132482fL},
            {0xeb2a51b23ea2f82dL},
            {0xc85dcc13ce7d29c0L},
            {0x8a8707d80cb54c7aL},
            {0x12c7ffecff1800baL},
            {0xcb16c5c1e342e34dL},
            {0x27fddd06bd368c50L},
            {0x5e6c6ee85cec7703L},
            {0x2117190446b50f9dL},
            {0xf3f12b62f51a9b55L},
            {0x2ee01b9e2a7692a6L},
            {0x53ca5e2da19191b7L},
            {0xce6d0917744faa2fL},
            {0xf9b8ca6b46052208L},
            {0xfb1cb91d94d6cddbL},
            {0xa39e2eab5f174f15L},
            {0xe9bfc7e088623326L},
            {0x24d3561ce4eda075L},
            {0x3edb299037e41adcL},
            {0x4ccafed99120c34cL},
            {0x811039d76b0f5c10L},
            {0xf26eca16e4f6b311L},
            {0x8ce51e30cf1501bbL},
            {0x80d0fa7707773de4L},
            {0x698d6cc716818773L},
            {0xcaaa5ff55032cbcfL},
            {0x3333d53faadbec42L},
            {0x10882aac3dd3587L},
            {0xb11fde1059b22334L},
            {0x8977ae72ed603d45L},
            {0xf65b17f58e2f82f6L},
            {0x63689bb426fad75L},
            {0xf09d687ab01da414L},
            {0xf9946308ce8bcec0L},
            {0x5f2a932916c5c63fL},
            {0x3a7933b10ff2e831L},
            {0x41f45d562a6689bL},
            {0xbcec7d59b5858e63L},
            {0x82ea92d6830c37adL},
            {0x27cc4624e3a8fd6cL},
            {0xbfa129745aeb3923L},
            {0x9b19fb3f08515329L},
            {0xb944c2c819b2038dL},
            {0x6e8d2803df3b267aL},
            {0xa5ed64048af45d9dL},
            {0x6d56acb61a9abe8eL},
            {0x4f03f6750128b16fL},
            {0x6e717510c8e732c4L},
            {0x6167f57448c6559bL},
            {0x4c445bb3cc5dc033L},
            {0x3d63ec327c84a0bfL},
            {0xeab5f4a8d3ec6334L},
            {0x1ffad87ddc8ca76aL},
            {0xfcc3b1db7bb174a0L},
            {0xcffe79062bb4e7cdL},
            {0xa21717e2b3d282eeL},
            {0x7e4143da4d878be5L},
            {0x23b80b8bc4e75405L},
            {0xa6ae749a1ed10838L},
            {0xd4b4a81be36638f2L},
            {0x5bab2890f354896dL},
            {0x4c0a184632b0499aL},
            {0xb45a39714746ec86L},
            {0xc4b90839e91abfb2L},
            {0xe81d35c8ed7827feL},
            {0x587c5ee43e034ebdL},
            {0xb1ec87f8823040acL},
            {0x7677dff12f92fbd9L},
            {0xb69cea6e5a0e28fdL},
            {0xf7180ae2e0f325e5L},
            {0xa08d214869e84ccfL},
            {0xcfff666740e2f99fL},
            {0x2fc743551c71634eL},
            {0x9bf4d77b464c9435L},
            {0x5e6b758083214c84L},
            {0x40548138ef68aa78L},
            {0x7c6b73ef50249070L},
            {0x462a1dc5b9cb1b3bL},
            {0xb8b156aa6c884b21L},
            {0xc7afcc722488f9e6L},
            {0x7a45b5b10dc24dbcL},
            {0xefe499d7a567391dL},
            {0xb60d26b461d05e25L},
            {0xc15d366b98d92986L},
            {0x9addb551a523df05L},
            {0xbd0a37a2ad2465b9L},
            {0xe7a7162d930c5056L},
            {0xb9982c5395b09406L},
            {0xe41766d004eef8fdL},
            {0xa3074a96c88c47deL},
            {0x881caa3913271394L},
            {0x77d95a600f824230L},
            {0x1984adb7bcfec495L},
            {0x66f613698d2263a7L},
            {0x50cf2a1c284f5a5aL},
    };

    static {
        var a = 9L;
        var b = 777L;
        for (int i = 0; i < data.length; i++) {
            a = (a ^ (a >>> 41)) * k0 + b;
            b = (b ^ (b >>> 41)) * k0 + i;
            data[i] = (byte) (b >>> 37);
        }
    }

    void assertDataHashing(long[] expected, int offset, int len) {
        assertEquals(expected[0], CityHash.cityHash64(data, offset, len));
    }

    @Parameterized.Parameters
    public static List<Object[]> parameters() {
        return IntStream.range(0, kTestSize).mapToObj(i -> new Object[]{i}).collect(Collectors.toList());
    }

    private final int i;

    public CityHashTest(int i) {
        this.i = i;
    }

    @Test
    public void test() {
        if (i == kTestSize - 1) {
            assertDataHashing(testdata[i], 0, data.length);
        } else {
            assertDataHashing(testdata[i], i * i, i);
        }
    }
}