Implementation of HalfSipHash-2-4-64 in Java.

HalfSipHasher64.java

/**
 * Copyright (C) 2022 Felipe Oliveira Carvalho
 *
 * 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.
 *
 *
 * HalfSipHash-2-4-64
 *
 * SipHash-C-D was designed by Jean-Philippe Aumasson and Daniel J. Bernstein
 * and is described in [1]. This implements the 64-bit version of the
 * Half-SipHash variation. There's a 32-bit version as well. All reference
 * implementations are available in [2] under the CC0-1.0 (Public Domain)
 * and MIT licenses.
 *
 * [1] "SipHash: a fast short-input PRF"
 *     (https://www.aumasson.jp/siphash/siphash.pdf)
 * [2] https://github.com/veorq/SipHash
 */
public final class HalfSipHasher64 {
  static final int C_ROUNDS = 2;
  static final int D_ROUNDS = 4;

  private final int key0;
  private final int key1;

  private static int bytesToInt(int offset, byte[] bytes) {
    int m = Byte.toUnsignedInt(bytes[offset + 0]);
    m |= Byte.toUnsignedInt(bytes[offset + 1]) << 8;
    m |= Byte.toUnsignedInt(bytes[offset + 2]) << 16;
    m |= Byte.toUnsignedInt(bytes[offset + 3]) << 24;
    return m;
  }

  private static long toUnsignedLittleEndianLong(int x) {
    return Integer.toUnsignedLong(Integer.reverseBytes(x));
  }

  private static long hash0(int v0, int v1, int v2, int v3, byte[] in, int inlen) {
    final int end = inlen - (inlen % 4);
    final int rest = inlen & 3;

    v1 ^= 0xee;
    for (int i = 0; i != end; i += 4) {
      final int m = bytesToInt(i, in);
      v3 ^= m;

      for (int r = 0; r < C_ROUNDS; r++) {
        v0 += v1; v1 = Integer.rotateLeft(v1, 5); v1 ^= v0;
        v0 = Integer.rotateLeft(v0, 16);
        v2 += v3; v3 = Integer.rotateLeft(v3, 8); v3 ^= v2;
        v0 += v3; v3 = Integer.rotateLeft(v3, 7); v3 ^= v0;
        v2 += v1; v1 = Integer.rotateLeft(v1, 13); v1 ^= v2;
        v2 = Integer.rotateLeft(v2, 16);
      }

      v0 ^= m;
    }

    long b = Integer.toUnsignedLong(inlen) << 24;
    switch (rest) {
      case 3:
        b |= Byte.toUnsignedLong(in[end + 2]) << 16;
        /* fallthru */
      case 2:
        b |= Byte.toUnsignedLong(in[end + 1]) << 8;
        /* fallthru */
      case 1:
        b |= Byte.toUnsignedLong(in[end]);
        break;
      case 0:
        break;
    }
    v3 ^= b;

    for (int r = 0; r < C_ROUNDS; r++) {
      v0 += v1; v1 = Integer.rotateLeft(v1, 5); v1 ^= v0;
      v0 = Integer.rotateLeft(v0, 16);
      v2 += v3; v3 = Integer.rotateLeft(v3, 8); v3 ^= v2;  
      v0 += v3; v3 = Integer.rotateLeft(v3, 7); v3 ^= v0;        
      v2 += v1; v1 = Integer.rotateLeft(v1, 13); v1 ^= v2;           
      v2 = Integer.rotateLeft(v2, 16); 
    }

    v0 ^= b;

    v2 ^= 0xee;

    for (int r = 0; r < D_ROUNDS; r++) {
      v0 += v1; v1 = Integer.rotateLeft(v1, 5); v1 ^= v0;
      v0 = Integer.rotateLeft(v0, 16);
      v2 += v3; v3 = Integer.rotateLeft(v3, 8); v3 ^= v2;  
      v0 += v3; v3 = Integer.rotateLeft(v3, 7); v3 ^= v0;
      v2 += v1; v1 = Integer.rotateLeft(v1, 13); v1 ^= v2;           
      v2 = Integer.rotateLeft(v2, 16); 
    }

    b = toUnsignedLittleEndianLong(v1 ^ v3) << 32;

    v1 ^= 0xdd;

    for (int r = 0; r < D_ROUNDS; r++) {
      v0 += v1; v1 = Integer.rotateLeft(v1, 5); v1 ^= v0;
      v0 = Integer.rotateLeft(v0, 16);
      v2 += v3; v3 = Integer.rotateLeft(v3, 8); v3 ^= v2;  
      v0 += v3; v3 = Integer.rotateLeft(v3, 7); v3 ^= v0;
      v2 += v1; v1 = Integer.rotateLeft(v1, 13); v1 ^= v2;           
      v2 = Integer.rotateLeft(v2, 16); 
    }

    b |= toUnsignedLittleEndianLong(v1 ^ v3);

    return b;
  }

  public static long hash(int k0, int k1, byte[] in, int inlen) {
    int v0 = 0;
    int v1 = 0;
    int v2 = 0x6c796765;
    int v3 = 0x74656462;

    v3 ^= k1;
    v2 ^= k0;
    v1 ^= k1;
    v0 ^= k0;

    return hash0(v0, v1, v2, v3, in, inlen);
  }

  public HalfSipHasher64(int key0, int key1) {
    this.key0 = key0;
    this.key1 = key1;
  }

  public HalfSipHasher64(long key) {
    this((int)key, (int)(key >>> 32));
  }

  public HalfSipHasher64(byte[] key) {
    this(bytesToInt(0, key), bytesToInt(4, key));
  }

  public HalfSipHasher64() {
    this(0x0706050403020100L);
  }

  public long hash(byte[] in, int inlen) {
    return hash(key0, key1, in, inlen);
  }

  public long hash(byte[] in) {
    return hash(in, in.length);
  }

  public static String hashToHexString(long hash) {
    return String.format("%016x", hash);
  }

  public static byte[] hashToByteArray(long hash) {
    final byte[] arr = new byte[8];
    arr[0] = (byte)(hash >>> 56);
    arr[1] = (byte)(hash >>> 48);
    arr[2] = (byte)(hash >>> 40);
    arr[3] = (byte)(hash >>> 32);
    arr[4] = (byte)(hash >>> 24);
    arr[5] = (byte)(hash >>> 16);
    arr[6] = (byte)(hash >>> 8);
    arr[7] = (byte)(hash);
    return arr;
  }
}

HalfSipHasher64Test.java

/**
 * Copyright (C) 2022 Felipe Oliveira Carvalho
 *
 * 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.
 */

import java.util.Arrays;

class HalfSipHasher64Test {
  /**
   * Test vectors from reference implementation of SipHash.
   */
  static final String[] vectorsHSip64 = new String[] {
    "218d1f59b9b83cc8",
    "be552412f8387315",
    "064f39ef7c50eb57",
    "ce0f1a45f7060679",
    "d5e78a175be52ea1",
    "cb9d7c3f2f3db580",
    "ce3e91358aa2bc25",
    "ff202728b07bc684",
    "edfee820bce4858c",
    "5b51cccc13888307",
    "95b0469f06a6f2ee",
    "ae26333994ddcd48",
    "7bc71f9faef5c799",
    "5a2352d75a0c3744",
    "3bb1a870eae8e658",
    "217d0bcb4e81c902",
    "7336aad25f7bf3b5",
    "37adc0641c4c4f6a",
    "c9b2db2b9a3e42f9",
    "f910e48020ab363c",
    "1bf52b0a6feea7db",
    "00741dc269e8b3ef",
    "e20103fa1ba776ef",
    "4c2210e54b681d73",
    "70741045ae3fa6f1",
    "0c86403739714038",
    "0d899ed8112923f0",
    "226bf5fab81ee1b8",
    "2d925ffb1e0016b5",
    "361958d52cee10f1",
    "291aaf864898179d",
    "863c7f155c34117c",
    "28709d46d811626c",
    "248477681d28f89c",
    "8324e4d7528f9830",
    "f9efd4e13aea6bd8",
    "86d67a40ec4276dc",
    "3f6292eccca97e35",
    "cbd92ee724d42109",
    "368df6808d403d79",
    "5b38c81c67c8ae4c",
    "95ab7189d439acb3",
    "a91a52c025327024",
    "5b0087c69528acea",
    "1e30f3ad27dcb15a",
    "697f5c9a90324ed4",
    "495c0f995557dc38",
    "9427202a3c29f94d",
    "a9eaa8c04ba93e3e",
    "eea4c1737d011218",
    "912d568fd8f65a49",
    "56919596b0ff5c97",
    "02445a7998f550e1",
    "86ec466ce71d1fb2",
    "359569e7d289e3bc",
    "871b05ca62bb7c96",
    "a1a492f942f15f1d",
    "12ec267ff6095b6e",
    "5d1b5ea1b231d89d",
    "d8cfb4453f92ee54",
    "d6762890bf26e460",
    "313563a4b7ed5cf3",
    "f90b3ab572d46693",
    "2ea63c71bf326087",
  };

  static byte[] hexStringToByteArray(String hex) {
    final byte[] arr = new byte[hex.length() / 2];
    for (int i = 0; i < hex.length() / 2; i++) {
      final int b = Character.digit(hex.charAt(2 * i    ), 16) * 16 +
                    Character.digit(hex.charAt(2 * i + 1), 16);
      arr[i] = (byte)b;
    }
    return arr;
  }

  public static void main(String[] args) {
    final byte[] key = new byte[8];
    for (byte i = 0; i < 8; i++) {
      key[i] = (byte)i;
    }
    final HalfSipHasher64 hasher = new HalfSipHasher64(key);
    final HalfSipHasher64 defaultHasher = new HalfSipHasher64();

    final byte[] in = new byte[64];
    for (int i = 0; i < in.length; ++i) {
      in[i] = (byte)i;
    }
    for (int i = 0; i < 64; ++i) {
      final long hash = hasher.hash(in, i);

      final String hexString = HalfSipHasher64.hashToHexString(hash);
      final String expectedHexString = vectorsHSip64[i];
      if (!hexString.equals(expectedHexString)) {
        System.out.printf("Failed: %s != %s\n", hexString, expectedHexString);
        System.exit(1);
      }

      final byte[] expectedByteArray = hexStringToByteArray(vectorsHSip64[i]);
      final byte[] byteArray = HalfSipHasher64.hashToByteArray(hash);

      if (!Arrays.equals(expectedByteArray, byteArray)) {
        System.out.println("Failed: byte arrays don't match.");
        System.exit(1);
      }

      if (hash != defaultHasher.hash(in, i)) {
        System.out.println("Failed: default hasher doesn't hash like explicit hasher.");
        System.exit(1);
      }

      System.out.printf("0x%s OK\n", hexString);
    }
  }
}