blob: e61cd02ce49136711c6899a96d9aedd14604a145 [file] [log] [blame]
Yaowu Xuc27fc142016-08-22 16:08:15 -07001/*
Yaowu Xubde4ac82016-11-28 15:26:06 -08002 * Copyright (c) 2016, Alliance for Open Media. All rights reserved
Yaowu Xuc27fc142016-08-22 16:08:15 -07003 *
Yaowu Xubde4ac82016-11-28 15:26:06 -08004 * 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.
Yaowu Xuc27fc142016-08-22 16:08:15 -070010 */
11
12#include <math.h>
13#include <stdlib.h>
hui sud13c24a2017-04-07 16:13:07 -070014
15#include "av1/encoder/cost.h"
Yaowu Xuc27fc142016-08-22 16:08:15 -070016#include "av1/encoder/palette.h"
Alex Converse9d068c12017-08-03 11:48:19 -070017#include "av1/encoder/random.h"
Yaowu Xuc27fc142016-08-22 16:08:15 -070018
Alex Converse15aa8c02017-08-03 12:31:16 -070019#define AV1_K_MEANS_DIM 1
20#include "av1/encoder/k_means_template.h"
21#undef AV1_K_MEANS_DIM
22#define AV1_K_MEANS_DIM 2
23#include "av1/encoder/k_means_template.h"
24#undef AV1_K_MEANS_DIM
Yaowu Xuc27fc142016-08-22 16:08:15 -070025
Hui Su5891f982017-12-18 16:18:23 -080026static int int_comparer(const void *a, const void *b) {
27 return (*(int *)a - *(int *)b);
Yaowu Xuc27fc142016-08-22 16:08:15 -070028}
29
Hui Su5891f982017-12-18 16:18:23 -080030int av1_remove_duplicates(int *centroids, int num_centroids) {
Yaowu Xuc27fc142016-08-22 16:08:15 -070031 int num_unique; // number of unique centroids
32 int i;
Hui Su5891f982017-12-18 16:18:23 -080033 qsort(centroids, num_centroids, sizeof(*centroids), int_comparer);
Yaowu Xuc27fc142016-08-22 16:08:15 -070034 // Remove duplicates.
35 num_unique = 1;
36 for (i = 1; i < num_centroids; ++i) {
37 if (centroids[i] != centroids[i - 1]) { // found a new unique centroid
38 centroids[num_unique++] = centroids[i];
39 }
40 }
41 return num_unique;
42}
43
hui su33567b22017-04-30 16:40:19 -070044static int delta_encode_cost(const int *colors, int num, int bit_depth,
45 int min_val) {
46 if (num <= 0) return 0;
47 int bits_cost = bit_depth;
48 if (num == 1) return bits_cost;
49 bits_cost += 2;
50 int max_delta = 0;
51 int deltas[PALETTE_MAX_SIZE];
52 const int min_bits = bit_depth - 3;
53 for (int i = 1; i < num; ++i) {
54 const int delta = colors[i] - colors[i - 1];
55 deltas[i - 1] = delta;
56 assert(delta >= min_val);
57 if (delta > max_delta) max_delta = delta;
hui sud13c24a2017-04-07 16:13:07 -070058 }
hui su33567b22017-04-30 16:40:19 -070059 int bits_per_delta = AOMMAX(av1_ceil_log2(max_delta + 1 - min_val), min_bits);
hui sufa4ff852017-05-15 12:20:50 -070060 assert(bits_per_delta <= bit_depth);
hui su33567b22017-04-30 16:40:19 -070061 int range = (1 << bit_depth) - colors[0] - min_val;
62 for (int i = 0; i < num - 1; ++i) {
63 bits_cost += bits_per_delta;
64 range -= deltas[i];
65 bits_per_delta = AOMMIN(bits_per_delta, av1_ceil_log2(range));
66 }
67 return bits_cost;
hui sud13c24a2017-04-07 16:13:07 -070068}
69
hui sufa4ff852017-05-15 12:20:50 -070070int av1_index_color_cache(const uint16_t *color_cache, int n_cache,
71 const uint16_t *colors, int n_colors,
hui su33567b22017-04-30 16:40:19 -070072 uint8_t *cache_color_found, int *out_cache_colors) {
hui su33567b22017-04-30 16:40:19 -070073 if (n_cache <= 0) {
hui sufa4ff852017-05-15 12:20:50 -070074 for (int i = 0; i < n_colors; ++i) out_cache_colors[i] = colors[i];
hui su33567b22017-04-30 16:40:19 -070075 return n_colors;
hui sud13c24a2017-04-07 16:13:07 -070076 }
hui su33567b22017-04-30 16:40:19 -070077 memset(cache_color_found, 0, n_cache * sizeof(*cache_color_found));
78 int n_in_cache = 0;
79 int in_cache_flags[PALETTE_MAX_SIZE];
80 memset(in_cache_flags, 0, sizeof(in_cache_flags));
81 for (int i = 0; i < n_cache && n_in_cache < n_colors; ++i) {
82 for (int j = 0; j < n_colors; ++j) {
hui sufa4ff852017-05-15 12:20:50 -070083 if (colors[j] == color_cache[i]) {
hui su33567b22017-04-30 16:40:19 -070084 in_cache_flags[j] = 1;
85 cache_color_found[i] = 1;
86 ++n_in_cache;
87 break;
88 }
89 }
90 }
91 int j = 0;
92 for (int i = 0; i < n_colors; ++i)
hui sufa4ff852017-05-15 12:20:50 -070093 if (!in_cache_flags[i]) out_cache_colors[j++] = colors[i];
hui su33567b22017-04-30 16:40:19 -070094 assert(j == n_colors - n_in_cache);
95 return j;
hui sud13c24a2017-04-07 16:13:07 -070096}
97
98int av1_get_palette_delta_bits_v(const PALETTE_MODE_INFO *const pmi,
99 int bit_depth, int *zero_count,
100 int *min_bits) {
101 const int n = pmi->palette_size[1];
102 const int max_val = 1 << bit_depth;
hui su33567b22017-04-30 16:40:19 -0700103 int max_d = 0;
hui sud13c24a2017-04-07 16:13:07 -0700104 *min_bits = bit_depth - 4;
105 *zero_count = 0;
hui su33567b22017-04-30 16:40:19 -0700106 for (int i = 1; i < n; ++i) {
hui sud13c24a2017-04-07 16:13:07 -0700107 const int delta = pmi->palette_colors[2 * PALETTE_MAX_SIZE + i] -
108 pmi->palette_colors[2 * PALETTE_MAX_SIZE + i - 1];
109 const int v = abs(delta);
110 const int d = AOMMIN(v, max_val - v);
111 if (d > max_d) max_d = d;
112 if (d == 0) ++(*zero_count);
113 }
114 return AOMMAX(av1_ceil_log2(max_d + 1), *min_bits);
115}
hui sud13c24a2017-04-07 16:13:07 -0700116
117int av1_palette_color_cost_y(const PALETTE_MODE_INFO *const pmi,
hui su33567b22017-04-30 16:40:19 -0700118 uint16_t *color_cache, int n_cache,
hui sud13c24a2017-04-07 16:13:07 -0700119 int bit_depth) {
120 const int n = pmi->palette_size[0];
hui su33567b22017-04-30 16:40:19 -0700121 int out_cache_colors[PALETTE_MAX_SIZE];
122 uint8_t cache_color_found[2 * PALETTE_MAX_SIZE];
123 const int n_out_cache =
124 av1_index_color_cache(color_cache, n_cache, pmi->palette_colors, n,
125 cache_color_found, out_cache_colors);
126 const int total_bits =
127 n_cache + delta_encode_cost(out_cache_colors, n_out_cache, bit_depth, 1);
Hui Su751a2332018-01-23 11:35:03 -0800128 return av1_cost_literal(total_bits);
hui sud13c24a2017-04-07 16:13:07 -0700129}
130
131int av1_palette_color_cost_uv(const PALETTE_MODE_INFO *const pmi,
hui su33567b22017-04-30 16:40:19 -0700132 uint16_t *color_cache, int n_cache,
hui sud13c24a2017-04-07 16:13:07 -0700133 int bit_depth) {
134 const int n = pmi->palette_size[1];
hui su33567b22017-04-30 16:40:19 -0700135 int total_bits = 0;
hui sud13c24a2017-04-07 16:13:07 -0700136 // U channel palette color cost.
hui su33567b22017-04-30 16:40:19 -0700137 int out_cache_colors[PALETTE_MAX_SIZE];
138 uint8_t cache_color_found[2 * PALETTE_MAX_SIZE];
139 const int n_out_cache = av1_index_color_cache(
140 color_cache, n_cache, pmi->palette_colors + PALETTE_MAX_SIZE, n,
141 cache_color_found, out_cache_colors);
142 total_bits +=
143 n_cache + delta_encode_cost(out_cache_colors, n_out_cache, bit_depth, 0);
144
hui sud13c24a2017-04-07 16:13:07 -0700145 // V channel palette color cost.
146 int zero_count = 0, min_bits_v = 0;
147 const int bits_v =
148 av1_get_palette_delta_bits_v(pmi, bit_depth, &zero_count, &min_bits_v);
149 const int bits_using_delta =
150 2 + bit_depth + (bits_v + 1) * (n - 1) - zero_count;
151 const int bits_using_raw = bit_depth * n;
hui su33567b22017-04-30 16:40:19 -0700152 total_bits += 1 + AOMMIN(bits_using_delta, bits_using_raw);
Hui Su751a2332018-01-23 11:35:03 -0800153 return av1_cost_literal(total_bits);
hui sud13c24a2017-04-07 16:13:07 -0700154}