// Copyright 2017 Google Inc.
//
// 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.
//
////////////////////////////////////////////////////////////////////////////////

package com.google.crypto.tink.subtle;

import java.security.GeneralSecurityException;
import java.util.Arrays;

Poly1305 one-time MAC based on RFC 7539.
This is not an implementation of the MAC interface on purpose and it is not equivalent to
HMAC.
The implementation is based on poly1305 implementation by Andrew Moon
(https://github.com/floodyberry/poly1305-donna) and released as public domain.
/**
 * Poly1305 one-time MAC based on RFC 7539.
 *
 * <p>This is not an implementation of the MAC interface on purpose and it is not equivalent to
 * HMAC.
 *
 * <p>The implementation is based on poly1305 implementation by Andrew Moon
 * (https://github.com/floodyberry/poly1305-donna) and released as public domain.
 */
class Poly1305 {

  public static final int MAC_TAG_SIZE_IN_BYTES = 16;
  public static final int MAC_KEY_SIZE_IN_BYTES = 32;

  private Poly1305() {}

  private static long load32(byte[] in, int idx) {
    return ((in[idx] & 0xff)
            | ((in[idx + 1] & 0xff) << 8)
            | ((in[idx + 2] & 0xff) << 16)
            | ((in[idx + 3] & 0xff) << 24))
        & 0xffffffffL;
  }

  private static long load26(byte[] in, int idx, int shift) {
    return (load32(in, idx) >> shift) & 0x3ffffff;
  }

  private static void toByteArray(byte[] output, long num, int idx) {
    for (int i = 0; i < 4; i++, num >>= 8) {
      output[idx + i] = (byte) (num & 0xff);
    }
  }

  private static void copyBlockSize(byte[] output, byte[] in, int idx) {
    int copyCount = Math.min(MAC_TAG_SIZE_IN_BYTES, in.length - idx);
    System.arraycopy(in, idx, output, 0, copyCount);
    output[copyCount] = 1;
    if (copyCount != MAC_TAG_SIZE_IN_BYTES) {
      Arrays.fill(output, copyCount + 1, output.length, (byte) 0);
    }
  }

  static byte[] computeMac(final byte[] key, byte[] data) {
    if (key.length != MAC_KEY_SIZE_IN_BYTES) {
      throw new IllegalArgumentException("The key length in bytes must be 32.");
    }
    long h0 = 0;
    long h1 = 0;
    long h2 = 0;
    long h3 = 0;
    long h4 = 0;
    long d0;
    long d1;
    long d2;
    long d3;
    long d4;
    long c;

    // r &= 0xffffffc0ffffffc0ffffffc0fffffff
    long r0 = load26(key, 0, 0) & 0x3ffffff;
    long r1 = load26(key, 3, 2) & 0x3ffff03;
    long r2 = load26(key, 6, 4) & 0x3ffc0ff;
    long r3 = load26(key, 9, 6) & 0x3f03fff;
    long r4 = load26(key, 12, 8) & 0x00fffff;

    long s1 = r1 * 5;
    long s2 = r2 * 5;
    long s3 = r3 * 5;
    long s4 = r4 * 5;

    byte[] buf = new byte[MAC_TAG_SIZE_IN_BYTES + 1];
    for (int i = 0; i < data.length; i += MAC_TAG_SIZE_IN_BYTES) {
      copyBlockSize(buf, data, i);
      h0 += load26(buf, 0, 0);
      h1 += load26(buf, 3, 2);
      h2 += load26(buf, 6, 4);
      h3 += load26(buf, 9, 6);
      h4 += load26(buf, 12, 8) | (buf[MAC_TAG_SIZE_IN_BYTES] << 24);

      // d = r * h
      d0 = h0 * r0 + h1 * s4 + h2 * s3 + h3 * s2 + h4 * s1;
      d1 = h0 * r1 + h1 * r0 + h2 * s4 + h3 * s3 + h4 * s2;
      d2 = h0 * r2 + h1 * r1 + h2 * r0 + h3 * s4 + h4 * s3;
      d3 = h0 * r3 + h1 * r2 + h2 * r1 + h3 * r0 + h4 * s4;
      d4 = h0 * r4 + h1 * r3 + h2 * r2 + h3 * r1 + h4 * r0;

      // Partial reduction mod 2^130-5, resulting h1 might not be 26bits.
      c = d0 >> 26;
      h0 = d0 & 0x3ffffff;
      d1 += c;
      c = d1 >> 26;
      h1 = d1 & 0x3ffffff;
      d2 += c;
      c = d2 >> 26;
      h2 = d2 & 0x3ffffff;
      d3 += c;
      c = d3 >> 26;
      h3 = d3 & 0x3ffffff;
      d4 += c;
      c = d4 >> 26;
      h4 = d4 & 0x3ffffff;
      h0 += c * 5;
      c = h0 >> 26;
      h0 = h0 & 0x3ffffff;
      h1 += c;
    }
    // Do final reduction mod 2^130-5
    c = h1 >> 26;
    h1 = h1 & 0x3ffffff;
    h2 += c;
    c = h2 >> 26;
    h2 = h2 & 0x3ffffff;
    h3 += c;
    c = h3 >> 26;
    h3 = h3 & 0x3ffffff;
    h4 += c;
    c = h4 >> 26;
    h4 = h4 & 0x3ffffff;
    h0 += c * 5; // c * 5 can be at most 5
    c = h0 >> 26;
    h0 = h0 & 0x3ffffff;
    h1 += c;

    // Compute h - p
    long g0 = h0 + 5;
    c = g0 >> 26;
    g0 &= 0x3ffffff;
    long g1 = h1 + c;
    c = g1 >> 26;
    g1 &= 0x3ffffff;
    long g2 = h2 + c;
    c = g2 >> 26;
    g2 &= 0x3ffffff;
    long g3 = h3 + c;
    c = g3 >> 26;
    g3 &= 0x3ffffff;
    long g4 = h4 + c - (1 << 26);

    // Select h if h < p, or h - p if h >= p
    long mask = g4 >> 63; // mask is either 0 (h >= p) or -1 (h < p)
    h0 &= mask;
    h1 &= mask;
    h2 &= mask;
    h3 &= mask;
    h4 &= mask;
    mask = ~mask;
    h0 |= g0 & mask;
    h1 |= g1 & mask;
    h2 |= g2 & mask;
    h3 |= g3 & mask;
    h4 |= g4 & mask;

    // h = h % (2^128)
    h0 = (h0 | (h1 << 26)) & 0xffffffffL;
    h1 = ((h1 >> 6) | (h2 << 20)) & 0xffffffffL;
    h2 = ((h2 >> 12) | (h3 << 14)) & 0xffffffffL;
    h3 = ((h3 >> 18) | (h4 << 8)) & 0xffffffffL;

    // mac = (h + pad) % (2^128)
    c = h0 + load32(key, 16);
    h0 = c & 0xffffffffL;
    c = h1 + load32(key, 20) + (c >> 32);
    h1 = c & 0xffffffffL;
    c = h2 + load32(key, 24) + (c >> 32);
    h2 = c & 0xffffffffL;
    c = h3 + load32(key, 28) + (c >> 32);
    h3 = c & 0xffffffffL;

    byte[] mac = new byte[MAC_TAG_SIZE_IN_BYTES];
    toByteArray(mac, h0, 0);
    toByteArray(mac, h1, 4);
    toByteArray(mac, h2, 8);
    toByteArray(mac, h3, 12);

    return mac;
  }

  static void verifyMac(final byte[] key, byte[] data, byte[] mac) throws GeneralSecurityException {
    if (!Bytes.equal(computeMac(key, data), mac)) {
      throw new GeneralSecurityException("invalid MAC");
    }
  }
}