/*

 * Copyright (c) 2002, 2019, Oracle and/or its affiliates. All rights reserved.

 * Copyright (c) 2012, 2019, SAP SE. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

#include "precompiled.hpp"

#include "asm/macroAssembler.inline.hpp"

#include "runtime/stubRoutines.hpp"

#include "runtime/vm_version.hpp"

// Implementation of the platform-specific part of StubRoutines - for

// a description of how to extend it, see the stubRoutines.hpp file.

#define __ masm->

// CRC constant compute functions

static juint fold_byte(juint w, juint reverse_poly) {

  for (int i = 0; i < 8; i++) {

    int poly_if_odd = (-(w & 1)) & reverse_poly;

    w = (w >> 1) ^ poly_if_odd;

  }

  return w;

}

static juint fold_word(juint w, juint reverse_poly) {

  for (int i = 0; i < 32; i++) {

    int poly_if_odd = (-(w & 1)) & reverse_poly;

    w = (w >> 1) ^ poly_if_odd;

  }

  return w;

}

static julong numberOfLeadingZeros(julong p) {

  julong l = 1ull << 63;

  for (int i = 0; i < 64; ++i) {

    if (p & l) return i;

    l >>= 1;

  }

  return 64;

}

static julong compute_inverse_poly(julong long_poly) {

  // 2^64 / p

  julong mod = 0, div = 0;

  int d = numberOfLeadingZeros(long_poly);

  int s = d + 1;

  do {

    mod ^= (long_poly << s);

    div |= (1L << s);

    s = d - numberOfLeadingZeros(mod);

  } while (s >= 0);

  return div;

}

#ifndef VM_LITTLE_ENDIAN

static void reverse_bytes(juint &w) {

  w = ((w >> 24) & 0xFF) | (((w >> 16) & 0xFF) << 8) | (((w >> 8) & 0xFF) << 16) | ((w & 0xFF) << 24);

}

#endif

// Constants to fold n words as needed by macroAssembler.

address StubRoutines::generate_crc_constants(juint reverse_poly) {

  // Layout of constant table:

  // <= Power7 Little Endian: 4 tables for byte folding

  // <= Power7 Big Endian: 1 table for single byte folding + 4 tables for multi-byte folding

  // >= Power8: 1 table for single byte folding + constants for fast vector implementation

  const bool use_vector = VM_Version::has_vpmsumb();

  const int vector_size = 16 * (CRC32_UNROLL_FACTOR2 + CRC32_UNROLL_FACTOR / CRC32_UNROLL_FACTOR2);

  const int size = use_vector ? CRC32_TABLE_SIZE + vector_size : (4 BIG_ENDIAN_ONLY(+1)) * CRC32_TABLE_SIZE;

  const address consts = (address)malloc(size);

  if (consts == NULL) {

    vm_exit_out_of_memory(size, OOM_MALLOC_ERROR, "CRC constants: no enough space");

  }

  juint* ptr = (juint*)consts;

  // Simple table used for single byte folding

  LITTLE_ENDIAN_ONLY(if (use_vector)) {

    for (int i = 0; i < 256; ++i) {

      ptr[i] = fold_byte(i, reverse_poly);

    }

  }

  if (!use_vector) {

    BIG_ENDIAN_ONLY(ptr = (juint*)(consts + CRC32_TABLE_SIZE);)

    // <= Power7: 4 tables

    for (int i = 0; i < 256; ++i) {

      juint a = fold_byte(i, reverse_poly),

            b = fold_byte(a, reverse_poly),

            c = fold_byte(b, reverse_poly),

            d = fold_byte(c, reverse_poly);

#ifndef VM_LITTLE_ENDIAN

      reverse_bytes(a);

      reverse_bytes(b);

      reverse_bytes(c);

      reverse_bytes(d);

#endif

      ptr[i         ] = a;

      ptr[i +    256] = b;

      ptr[i + 2* 256] = c;

      ptr[i + 3* 256] = d;

    }

#if 0

    for (int i = 0; i < 4; ++i) {

      tty->print_cr("table %d:", i);

      for (int j = 0; j < 32; ++j) {

        for (int k = 0; k < 8; ++k) {

          tty->print("%08x ", ptr[i*256 + j*8 + k]);

        }

        tty->cr();

      }

    }

#endif

    return consts;

  }

  // >= Power8: vector constants

  juint* ptr1 = (juint*)(consts + CRC32_TABLE_SIZE);

  guarantee(((intptr_t)ptr1 & 0xF) == 0, "16-byte alignment needed");

  // Generate constants for outer loop

  juint v0, v1, v2, v3 = 1;

  for (int i = 0; i < CRC32_UNROLL_FACTOR2 - 1; ++i) {

    v0 = fold_word(v3, reverse_poly);

    v1 = fold_word(v0, reverse_poly);

    v2 = fold_word(v1, reverse_poly);

    v3 = fold_word(v2, reverse_poly);

#ifdef VM_LITTLE_ENDIAN

    ptr1[4*i  ] = v3;

    ptr1[4*i+1] = v2;

    ptr1[4*i+2] = v3;

    ptr1[4*i+3] = v2;

#else

    ptr1[4*i  ] = v2;

    ptr1[4*i+1] = v3;

    ptr1[4*i+2] = v2;

    ptr1[4*i+3] = v3;

#endif

  }

  // Generate constants for inner loop

  juint* ptr2 = ptr1 + 4 * (CRC32_UNROLL_FACTOR2 - 1);

  v3 = 1; // Restart from scratch.

  for (int i = 0; i < CRC32_UNROLL_FACTOR; ++i) {

    v0 = fold_word(v3, reverse_poly);

    v1 = fold_word(v0, reverse_poly);

    v2 = fold_word(v1, reverse_poly);

    v3 = fold_word(v2, reverse_poly);

    if (i % CRC32_UNROLL_FACTOR2 == 0) {

      int idx = CRC32_UNROLL_FACTOR / CRC32_UNROLL_FACTOR2 - 1 - i / CRC32_UNROLL_FACTOR2;

      for (int j = 0; j < 4; ++j) {

#ifdef VM_LITTLE_ENDIAN

        ptr2[4*idx  ] = v3;

        ptr2[4*idx+1] = v2;

        ptr2[4*idx+2] = v1;

        ptr2[4*idx+3] = v0;

#else

        ptr2[4*idx  ] = v0;

        ptr2[4*idx+1] = v1;

        ptr2[4*idx+2] = v2;

        ptr2[4*idx+3] = v3;

#endif

      }

    }

  }

  // Constants to reduce 64 to 32 bit as needed by macroAssembler.

  juint* ptr3 = ptr2 + 4 * (CRC32_UNROLL_FACTOR / CRC32_UNROLL_FACTOR2);

  julong* c = (julong*)ptr3;

  julong long_poly = (((julong)reverse_poly) << 1) | 1;

  julong inverse_long_poly = compute_inverse_poly(long_poly);

#ifdef VM_LITTLE_ENDIAN

  c[0] = inverse_long_poly;

  c[1] = long_poly;

#else

  c[0] = long_poly;

  c[1] = inverse_long_poly;

#endif

#ifdef ASSERT

  if (reverse_poly == REVERSE_CRC32_POLY) {

    assert(INVERSE_REVERSE_CRC32_POLY == inverse_long_poly, "sanity");

  } else if (reverse_poly == REVERSE_CRC32C_POLY) {

    assert(INVERSE_REVERSE_CRC32C_POLY == inverse_long_poly, "sanity");

  }

#endif

  //printf("inv poly: 0x%016llx\n", (long long unsigned int)inverse_long_poly);

  return consts;

}