/*

 * Copyright (c) 2016, Alliance for Open Media. All rights reserved.

 *

 * This source code is subject to the terms of the BSD 2 Clause License and

 * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License

 * was not distributed with this source code in the LICENSE file, you can

 * obtain it at www.aomedia.org/license/software. If the Alliance for Open

 * Media Patent License 1.0 was not distributed with this source code in the

 * PATENTS file, you can obtain it at www.aomedia.org/license/patent.

 */

#include <assert.h>

#include <stdint.h>

#include <stdlib.h>

#include <string.h>

#include "av1/common/blockd.h"

#include "av1/encoder/palette.h"

#include "av1/encoder/random.h"

#ifndef AV1_K_MEANS_DIM

#error "This template requires AV1_K_MEANS_DIM to be defined"

#endif

#define RENAME_(x, y) AV1_K_MEANS_RENAME(x, y)

#define RENAME(x) RENAME_(x, AV1_K_MEANS_DIM)

#define K_MEANS_RENAME_C(x, y) x##_dim##y##_c

#define RENAME_C_(x, y) K_MEANS_RENAME_C(x, y)

#define RENAME_C(x) RENAME_C_(x, AV1_K_MEANS_DIM)

// Though we want to compute the smallest L2 norm, in 1 dimension,

// it is equivalent to find the smallest L1 norm and then square it.

// This is preferrable for speed, especially on the SIMD side.

static int RENAME(calc_dist)(const int16_t *p1, const int16_t *p2) {

#if AV1_K_MEANS_DIM == 1

  return abs(p1[0] - p2[0]);

#else

  int dist = 0;

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

    const int diff = p1[i] - p2[i];

    dist += diff * diff;

  }

  return dist;

#endif

}

Unexecuted instantiation: palette.c:calc_dist_dim1

Unexecuted instantiation: palette.c:calc_dist_dim2

void RENAME_C(av1_calc_indices)(const int16_t *data, const int16_t *centroids,

                                uint8_t *indices, int64_t *dist, int n, int k) {

  if (dist) {

    *dist = 0;

  }

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

    int min_dist = RENAME(calc_dist)(data + i * AV1_K_MEANS_DIM, centroids);

    indices[i] = 0;

    for (int j = 1; j < k; ++j) {

      const int this_dist = RENAME(calc_dist)(data + i * AV1_K_MEANS_DIM,

                                              centroids + j * AV1_K_MEANS_DIM);

      if (this_dist < min_dist) {

        min_dist = this_dist;

        indices[i] = j;

      }

    }

    if (dist) {

#if AV1_K_MEANS_DIM == 1

      *dist += min_dist * min_dist;

#else

      *dist += min_dist;

#endif

    }

  }

}

Unexecuted instantiation: av1_calc_indices_dim1_c

Unexecuted instantiation: av1_calc_indices_dim2_c

static void RENAME(calc_centroids)(const int16_t *data, int16_t *centroids,

                                   const uint8_t *indices, int n, int k) {

  int i, j;

  int count[PALETTE_MAX_SIZE] = { 0 };

  int centroids_sum[AV1_K_MEANS_DIM * PALETTE_MAX_SIZE];

  unsigned int rand_state = (unsigned int)data[0];

  assert(n <= 32768);

  memset(centroids_sum, 0, sizeof(centroids_sum[0]) * k * AV1_K_MEANS_DIM);

  for (i = 0; i < n; ++i) {

    const int index = indices[i];

    assert(index < k);

    ++count[index];

    for (j = 0; j < AV1_K_MEANS_DIM; ++j) {

      centroids_sum[index * AV1_K_MEANS_DIM + j] +=

          data[i * AV1_K_MEANS_DIM + j];

    }

  }

  for (i = 0; i < k; ++i) {

    if (count[i] == 0) {

      memcpy(centroids + i * AV1_K_MEANS_DIM,

             data + (lcg_rand16(&rand_state) % n) * AV1_K_MEANS_DIM,

             sizeof(centroids[0]) * AV1_K_MEANS_DIM);

    } else {

      for (j = 0; j < AV1_K_MEANS_DIM; ++j) {

        centroids[i * AV1_K_MEANS_DIM + j] =

            DIVIDE_AND_ROUND(centroids_sum[i * AV1_K_MEANS_DIM + j], count[i]);

      }

    }

  }

}

Unexecuted instantiation: palette.c:calc_centroids_dim1

Unexecuted instantiation: palette.c:calc_centroids_dim2

void RENAME(av1_k_means)(const int16_t *data, int16_t *centroids,

                         uint8_t *indices, int n, int k, int max_itr) {

  int16_t centroids_tmp[AV1_K_MEANS_DIM * PALETTE_MAX_SIZE];

  uint8_t indices_tmp[MAX_PALETTE_BLOCK_WIDTH * MAX_PALETTE_BLOCK_HEIGHT];

  int16_t *meta_centroids[2] = { centroids, centroids_tmp };

  uint8_t *meta_indices[2] = { indices, indices_tmp };

  int i, l = 0, prev_l, best_l = 0;

  int64_t this_dist;

  assert(n <= MAX_PALETTE_BLOCK_WIDTH * MAX_PALETTE_BLOCK_HEIGHT);

#if AV1_K_MEANS_DIM == 1

  av1_calc_indices_dim1(data, centroids, indices, &this_dist, n, k);

#else

  av1_calc_indices_dim2(data, centroids, indices, &this_dist, n, k);

#endif

  for (i = 0; i < max_itr; ++i) {

    const int64_t prev_dist = this_dist;

    prev_l = l;

    l = (l == 1) ? 0 : 1;

    RENAME(calc_centroids)(data, meta_centroids[l], meta_indices[prev_l], n, k);

    if (!memcmp(meta_centroids[l], meta_centroids[prev_l],

                sizeof(centroids[0]) * k * AV1_K_MEANS_DIM)) {

      break;

    }

#if AV1_K_MEANS_DIM == 1

    av1_calc_indices_dim1(data, meta_centroids[l], meta_indices[l], &this_dist,

                          n, k);

#else

    av1_calc_indices_dim2(data, meta_centroids[l], meta_indices[l], &this_dist,

                          n, k);

#endif

    if (this_dist > prev_dist) {

      best_l = prev_l;

      break;

    }

  }

  if (i == max_itr) best_l = l;

  if (best_l != 0) {

    memcpy(centroids, meta_centroids[1],

           sizeof(centroids[0]) * k * AV1_K_MEANS_DIM);

    memcpy(indices, meta_indices[1], sizeof(indices[0]) * n);

  }

}

Unexecuted instantiation: av1_k_means_dim1

Unexecuted instantiation: av1_k_means_dim2

#undef RENAME_

#undef RENAME

#undef K_MEANS_RENAME_C

#undef RENAME_C_

#undef RENAME_C