/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 |