Coverage Report

Created: 2022-08-24 06:11

/src/aom/av1/encoder/k_means_template.h
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright (c) 2016, Alliance for Open Media. All rights reserved
3
 *
4
 * This source code is subject to the terms of the BSD 2 Clause License and
5
 * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
6
 * was not distributed with this source code in the LICENSE file, you can
7
 * obtain it at www.aomedia.org/license/software. If the Alliance for Open
8
 * Media Patent License 1.0 was not distributed with this source code in the
9
 * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
10
 */
11
12
#include <assert.h>
13
#include <stdint.h>
14
#include <string.h>
15
16
#include "av1/common/blockd.h"
17
#include "av1/encoder/palette.h"
18
#include "av1/encoder/random.h"
19
20
#ifndef AV1_K_MEANS_DIM
21
#error "This template requires AV1_K_MEANS_DIM to be defined"
22
#endif
23
24
0
#define RENAME_(x, y) AV1_K_MEANS_RENAME(x, y)
25
0
#define RENAME(x) RENAME_(x, AV1_K_MEANS_DIM)
26
27
0
static int RENAME(calc_dist)(const int *p1, const int *p2) {
28
0
  int dist = 0;
29
0
  for (int i = 0; i < AV1_K_MEANS_DIM; ++i) {
30
0
    const int diff = p1[i] - p2[i];
31
0
    dist += diff * diff;
32
0
  }
33
0
  return dist;
34
0
}
Unexecuted instantiation: palette.c:calc_dist_dim1_c
Unexecuted instantiation: palette.c:calc_dist_dim2_c
35
36
void RENAME(av1_calc_indices)(const int *data, const int *centroids,
37
0
                              uint8_t *indices, int n, int k) {
38
0
  for (int i = 0; i < n; ++i) {
39
0
    int min_dist = RENAME(calc_dist)(data + i * AV1_K_MEANS_DIM, centroids);
40
0
    indices[i] = 0;
41
0
    for (int j = 1; j < k; ++j) {
42
0
      const int this_dist = RENAME(calc_dist)(data + i * AV1_K_MEANS_DIM,
43
0
                                              centroids + j * AV1_K_MEANS_DIM);
44
0
      if (this_dist < min_dist) {
45
0
        min_dist = this_dist;
46
0
        indices[i] = j;
47
0
      }
48
0
    }
49
0
  }
50
0
}
Unexecuted instantiation: av1_calc_indices_dim1_c
Unexecuted instantiation: av1_calc_indices_dim2_c
51
52
static void RENAME(calc_centroids)(const int *data, int *centroids,
53
0
                                   const uint8_t *indices, int n, int k) {
54
0
  int i, j;
55
0
  int count[PALETTE_MAX_SIZE] = { 0 };
56
0
  unsigned int rand_state = (unsigned int)data[0];
57
0
  assert(n <= 32768);
58
0
  memset(centroids, 0, sizeof(centroids[0]) * k * AV1_K_MEANS_DIM);
59
60
0
  for (i = 0; i < n; ++i) {
61
0
    const int index = indices[i];
62
0
    assert(index < k);
63
0
    ++count[index];
64
0
    for (j = 0; j < AV1_K_MEANS_DIM; ++j) {
65
0
      centroids[index * AV1_K_MEANS_DIM + j] += data[i * AV1_K_MEANS_DIM + j];
66
0
    }
67
0
  }
68
69
0
  for (i = 0; i < k; ++i) {
70
0
    if (count[i] == 0) {
71
0
      memcpy(centroids + i * AV1_K_MEANS_DIM,
72
0
             data + (lcg_rand16(&rand_state) % n) * AV1_K_MEANS_DIM,
73
0
             sizeof(centroids[0]) * AV1_K_MEANS_DIM);
74
0
    } else {
75
0
      for (j = 0; j < AV1_K_MEANS_DIM; ++j) {
76
0
        centroids[i * AV1_K_MEANS_DIM + j] =
77
0
            DIVIDE_AND_ROUND(centroids[i * AV1_K_MEANS_DIM + j], count[i]);
78
0
      }
79
0
    }
80
0
  }
81
0
}
Unexecuted instantiation: palette.c:calc_centroids_dim1_c
Unexecuted instantiation: palette.c:calc_centroids_dim2_c
82
83
static int64_t RENAME(calc_total_dist)(const int *data, const int *centroids,
84
0
                                       const uint8_t *indices, int n, int k) {
85
0
  int64_t dist = 0;
86
0
  (void)k;
87
0
  for (int i = 0; i < n; ++i) {
88
0
    dist += RENAME(calc_dist)(data + i * AV1_K_MEANS_DIM,
89
0
                              centroids + indices[i] * AV1_K_MEANS_DIM);
90
0
  }
91
0
  return dist;
92
0
}
Unexecuted instantiation: palette.c:calc_total_dist_dim1_c
Unexecuted instantiation: palette.c:calc_total_dist_dim2_c
93
94
void RENAME(av1_k_means)(const int *data, int *centroids, uint8_t *indices,
95
0
                         int n, int k, int max_itr) {
96
0
  int pre_centroids[2 * PALETTE_MAX_SIZE];
97
0
  uint8_t pre_indices[MAX_PALETTE_BLOCK_WIDTH * MAX_PALETTE_BLOCK_HEIGHT];
98
99
0
  assert(n <= MAX_PALETTE_BLOCK_WIDTH * MAX_PALETTE_BLOCK_HEIGHT);
100
101
#if AV1_K_MEANS_DIM - 2
102
0
  av1_calc_indices_dim1(data, centroids, indices, n, k);
103
#else
104
0
  av1_calc_indices_dim2(data, centroids, indices, n, k);
105
#endif
106
0
  int64_t this_dist = RENAME(calc_total_dist)(data, centroids, indices, n, k);
107
108
0
  for (int i = 0; i < max_itr; ++i) {
109
0
    const int64_t pre_dist = this_dist;
110
0
    memcpy(pre_centroids, centroids,
111
0
           sizeof(pre_centroids[0]) * k * AV1_K_MEANS_DIM);
112
0
    memcpy(pre_indices, indices, sizeof(pre_indices[0]) * n);
113
114
0
    RENAME(calc_centroids)(data, centroids, indices, n, k);
115
#if AV1_K_MEANS_DIM - 2
116
0
    av1_calc_indices_dim1(data, centroids, indices, n, k);
117
#else
118
0
    av1_calc_indices_dim2(data, centroids, indices, n, k);
119
#endif
120
0
    this_dist = RENAME(calc_total_dist)(data, centroids, indices, n, k);
121
122
0
    if (this_dist > pre_dist) {
123
0
      memcpy(centroids, pre_centroids,
124
0
             sizeof(pre_centroids[0]) * k * AV1_K_MEANS_DIM);
125
0
      memcpy(indices, pre_indices, sizeof(pre_indices[0]) * n);
126
0
      break;
127
0
    }
128
0
    if (!memcmp(centroids, pre_centroids,
129
0
                sizeof(pre_centroids[0]) * k * AV1_K_MEANS_DIM))
130
0
      break;
131
0
  }
132
0
}
Unexecuted instantiation: av1_k_means_dim1_c
Unexecuted instantiation: av1_k_means_dim2_c
133
#undef RENAME_
134
#undef RENAME