1 /*
2 * Copyright (c) 2018, 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
14 #include "config/av1_rtcd.h"
15
16 #include "av1/encoder/block.h"
17 #include "av1/encoder/hash.h"
18 #include "av1/encoder/hash_motion.h"
19
20 #define kSrcBits 16
21 #define kBlockSizeBits 3
22 #define kMaxAddr (1 << (kSrcBits + kBlockSizeBits))
23
24 // TODO(youzhou@microsoft.com): is higher than 8 bits screen content supported?
25 // If yes, fix this function
get_pixels_in_1D_char_array_by_block_2x2(const uint8_t * y_src,int stride,uint8_t * p_pixels_in1D)26 static void get_pixels_in_1D_char_array_by_block_2x2(const uint8_t *y_src,
27 int stride,
28 uint8_t *p_pixels_in1D) {
29 const uint8_t *p_pel = y_src;
30 int index = 0;
31 for (int i = 0; i < 2; i++) {
32 for (int j = 0; j < 2; j++) {
33 p_pixels_in1D[index++] = p_pel[j];
34 }
35 p_pel += stride;
36 }
37 }
38
get_pixels_in_1D_short_array_by_block_2x2(const uint16_t * y_src,int stride,uint16_t * p_pixels_in1D)39 static void get_pixels_in_1D_short_array_by_block_2x2(const uint16_t *y_src,
40 int stride,
41 uint16_t *p_pixels_in1D) {
42 const uint16_t *p_pel = y_src;
43 int index = 0;
44 for (int i = 0; i < 2; i++) {
45 for (int j = 0; j < 2; j++) {
46 p_pixels_in1D[index++] = p_pel[j];
47 }
48 p_pel += stride;
49 }
50 }
51
is_block_2x2_row_same_value(const uint8_t * p)52 static int is_block_2x2_row_same_value(const uint8_t *p) {
53 if (p[0] != p[1] || p[2] != p[3]) {
54 return 0;
55 }
56 return 1;
57 }
58
is_block16_2x2_row_same_value(const uint16_t * p)59 static int is_block16_2x2_row_same_value(const uint16_t *p) {
60 if (p[0] != p[1] || p[2] != p[3]) {
61 return 0;
62 }
63 return 1;
64 }
65
is_block_2x2_col_same_value(const uint8_t * p)66 static int is_block_2x2_col_same_value(const uint8_t *p) {
67 if ((p[0] != p[2]) || (p[1] != p[3])) {
68 return 0;
69 }
70 return 1;
71 }
72
is_block16_2x2_col_same_value(const uint16_t * p)73 static int is_block16_2x2_col_same_value(const uint16_t *p) {
74 if ((p[0] != p[2]) || (p[1] != p[3])) {
75 return 0;
76 }
77 return 1;
78 }
79
80 // the hash value (hash_value1 consists two parts, the first 3 bits relate to
81 // the block size and the remaining 16 bits are the crc values. This fuction
82 // is used to get the first 3 bits.
hash_block_size_to_index(int block_size)83 static int hash_block_size_to_index(int block_size) {
84 switch (block_size) {
85 case 4: return 0;
86 case 8: return 1;
87 case 16: return 2;
88 case 32: return 3;
89 case 64: return 4;
90 case 128: return 5;
91 default: return -1;
92 }
93 }
94
av1_hash_table_init(IntraBCHashInfo * intrabc_hash_info)95 void av1_hash_table_init(IntraBCHashInfo *intrabc_hash_info) {
96 if (!intrabc_hash_info->g_crc_initialized) {
97 av1_crc_calculator_init(&intrabc_hash_info->crc_calculator1, 24, 0x5D6DCB);
98 av1_crc_calculator_init(&intrabc_hash_info->crc_calculator2, 24, 0x864CFB);
99 intrabc_hash_info->g_crc_initialized = 1;
100 }
101 intrabc_hash_info->intrabc_hash_table.p_lookup_table = NULL;
102 }
103
av1_hash_table_clear_all(hash_table * p_hash_table)104 void av1_hash_table_clear_all(hash_table *p_hash_table) {
105 if (p_hash_table->p_lookup_table == NULL) {
106 return;
107 }
108 for (int i = 0; i < kMaxAddr; i++) {
109 if (p_hash_table->p_lookup_table[i] != NULL) {
110 aom_vector_destroy(p_hash_table->p_lookup_table[i]);
111 aom_free(p_hash_table->p_lookup_table[i]);
112 p_hash_table->p_lookup_table[i] = NULL;
113 }
114 }
115 }
116
av1_hash_table_destroy(hash_table * p_hash_table)117 void av1_hash_table_destroy(hash_table *p_hash_table) {
118 av1_hash_table_clear_all(p_hash_table);
119 aom_free(p_hash_table->p_lookup_table);
120 p_hash_table->p_lookup_table = NULL;
121 }
122
av1_hash_table_create(hash_table * p_hash_table)123 void av1_hash_table_create(hash_table *p_hash_table) {
124 if (p_hash_table->p_lookup_table != NULL) {
125 av1_hash_table_clear_all(p_hash_table);
126 return;
127 }
128 p_hash_table->p_lookup_table =
129 (Vector **)aom_malloc(sizeof(p_hash_table->p_lookup_table[0]) * kMaxAddr);
130 memset(p_hash_table->p_lookup_table, 0,
131 sizeof(p_hash_table->p_lookup_table[0]) * kMaxAddr);
132 }
133
hash_table_add_to_table(hash_table * p_hash_table,uint32_t hash_value,block_hash * curr_block_hash)134 static void hash_table_add_to_table(hash_table *p_hash_table,
135 uint32_t hash_value,
136 block_hash *curr_block_hash) {
137 if (p_hash_table->p_lookup_table[hash_value] == NULL) {
138 p_hash_table->p_lookup_table[hash_value] =
139 aom_malloc(sizeof(p_hash_table->p_lookup_table[0][0]));
140 aom_vector_setup(p_hash_table->p_lookup_table[hash_value], 10,
141 sizeof(curr_block_hash[0]));
142 aom_vector_push_back(p_hash_table->p_lookup_table[hash_value],
143 curr_block_hash);
144 } else {
145 aom_vector_push_back(p_hash_table->p_lookup_table[hash_value],
146 curr_block_hash);
147 }
148 }
149
av1_hash_table_count(const hash_table * p_hash_table,uint32_t hash_value)150 int32_t av1_hash_table_count(const hash_table *p_hash_table,
151 uint32_t hash_value) {
152 if (p_hash_table->p_lookup_table[hash_value] == NULL) {
153 return 0;
154 } else {
155 return (int32_t)(p_hash_table->p_lookup_table[hash_value]->size);
156 }
157 }
158
av1_hash_get_first_iterator(hash_table * p_hash_table,uint32_t hash_value)159 Iterator av1_hash_get_first_iterator(hash_table *p_hash_table,
160 uint32_t hash_value) {
161 assert(av1_hash_table_count(p_hash_table, hash_value) > 0);
162 return aom_vector_begin(p_hash_table->p_lookup_table[hash_value]);
163 }
164
av1_has_exact_match(hash_table * p_hash_table,uint32_t hash_value1,uint32_t hash_value2)165 int32_t av1_has_exact_match(hash_table *p_hash_table, uint32_t hash_value1,
166 uint32_t hash_value2) {
167 if (p_hash_table->p_lookup_table[hash_value1] == NULL) {
168 return 0;
169 }
170 Iterator iterator =
171 aom_vector_begin(p_hash_table->p_lookup_table[hash_value1]);
172 Iterator last = aom_vector_end(p_hash_table->p_lookup_table[hash_value1]);
173 for (; !aom_iterator_equals(&iterator, &last);
174 aom_iterator_increment(&iterator)) {
175 if ((*(block_hash *)aom_iterator_get(&iterator)).hash_value2 ==
176 hash_value2) {
177 return 1;
178 }
179 }
180 return 0;
181 }
182
av1_generate_block_2x2_hash_value(IntraBCHashInfo * intrabc_hash_info,const YV12_BUFFER_CONFIG * picture,uint32_t * pic_block_hash[2],int8_t * pic_block_same_info[3])183 void av1_generate_block_2x2_hash_value(IntraBCHashInfo *intrabc_hash_info,
184 const YV12_BUFFER_CONFIG *picture,
185 uint32_t *pic_block_hash[2],
186 int8_t *pic_block_same_info[3]) {
187 const int width = 2;
188 const int height = 2;
189 const int x_end = picture->y_crop_width - width + 1;
190 const int y_end = picture->y_crop_height - height + 1;
191 CRC_CALCULATOR *calc_1 = &intrabc_hash_info->crc_calculator1;
192 CRC_CALCULATOR *calc_2 = &intrabc_hash_info->crc_calculator2;
193
194 const int length = width * 2;
195 if (picture->flags & YV12_FLAG_HIGHBITDEPTH) {
196 uint16_t p[4];
197 int pos = 0;
198 for (int y_pos = 0; y_pos < y_end; y_pos++) {
199 for (int x_pos = 0; x_pos < x_end; x_pos++) {
200 get_pixels_in_1D_short_array_by_block_2x2(
201 CONVERT_TO_SHORTPTR(picture->y_buffer) + y_pos * picture->y_stride +
202 x_pos,
203 picture->y_stride, p);
204 pic_block_same_info[0][pos] = is_block16_2x2_row_same_value(p);
205 pic_block_same_info[1][pos] = is_block16_2x2_col_same_value(p);
206
207 pic_block_hash[0][pos] =
208 av1_get_crc_value(calc_1, (uint8_t *)p, length * sizeof(p[0]));
209 pic_block_hash[1][pos] =
210 av1_get_crc_value(calc_2, (uint8_t *)p, length * sizeof(p[0]));
211 pos++;
212 }
213 pos += width - 1;
214 }
215 } else {
216 uint8_t p[4];
217 int pos = 0;
218 for (int y_pos = 0; y_pos < y_end; y_pos++) {
219 for (int x_pos = 0; x_pos < x_end; x_pos++) {
220 get_pixels_in_1D_char_array_by_block_2x2(
221 picture->y_buffer + y_pos * picture->y_stride + x_pos,
222 picture->y_stride, p);
223 pic_block_same_info[0][pos] = is_block_2x2_row_same_value(p);
224 pic_block_same_info[1][pos] = is_block_2x2_col_same_value(p);
225
226 pic_block_hash[0][pos] =
227 av1_get_crc_value(calc_1, p, length * sizeof(p[0]));
228 pic_block_hash[1][pos] =
229 av1_get_crc_value(calc_2, p, length * sizeof(p[0]));
230 pos++;
231 }
232 pos += width - 1;
233 }
234 }
235 }
236
av1_generate_block_hash_value(IntraBCHashInfo * intrabc_hash_info,const YV12_BUFFER_CONFIG * picture,int block_size,uint32_t * src_pic_block_hash[2],uint32_t * dst_pic_block_hash[2],int8_t * src_pic_block_same_info[3],int8_t * dst_pic_block_same_info[3])237 void av1_generate_block_hash_value(IntraBCHashInfo *intrabc_hash_info,
238 const YV12_BUFFER_CONFIG *picture,
239 int block_size,
240 uint32_t *src_pic_block_hash[2],
241 uint32_t *dst_pic_block_hash[2],
242 int8_t *src_pic_block_same_info[3],
243 int8_t *dst_pic_block_same_info[3]) {
244 CRC_CALCULATOR *calc_1 = &intrabc_hash_info->crc_calculator1;
245 CRC_CALCULATOR *calc_2 = &intrabc_hash_info->crc_calculator2;
246
247 const int pic_width = picture->y_crop_width;
248 const int x_end = picture->y_crop_width - block_size + 1;
249 const int y_end = picture->y_crop_height - block_size + 1;
250
251 const int src_size = block_size >> 1;
252 const int quad_size = block_size >> 2;
253
254 uint32_t p[4];
255 const int length = sizeof(p);
256
257 int pos = 0;
258 for (int y_pos = 0; y_pos < y_end; y_pos++) {
259 for (int x_pos = 0; x_pos < x_end; x_pos++) {
260 p[0] = src_pic_block_hash[0][pos];
261 p[1] = src_pic_block_hash[0][pos + src_size];
262 p[2] = src_pic_block_hash[0][pos + src_size * pic_width];
263 p[3] = src_pic_block_hash[0][pos + src_size * pic_width + src_size];
264 dst_pic_block_hash[0][pos] =
265 av1_get_crc_value(calc_1, (uint8_t *)p, length);
266
267 p[0] = src_pic_block_hash[1][pos];
268 p[1] = src_pic_block_hash[1][pos + src_size];
269 p[2] = src_pic_block_hash[1][pos + src_size * pic_width];
270 p[3] = src_pic_block_hash[1][pos + src_size * pic_width + src_size];
271 dst_pic_block_hash[1][pos] =
272 av1_get_crc_value(calc_2, (uint8_t *)p, length);
273
274 dst_pic_block_same_info[0][pos] =
275 src_pic_block_same_info[0][pos] &&
276 src_pic_block_same_info[0][pos + quad_size] &&
277 src_pic_block_same_info[0][pos + src_size] &&
278 src_pic_block_same_info[0][pos + src_size * pic_width] &&
279 src_pic_block_same_info[0][pos + src_size * pic_width + quad_size] &&
280 src_pic_block_same_info[0][pos + src_size * pic_width + src_size];
281
282 dst_pic_block_same_info[1][pos] =
283 src_pic_block_same_info[1][pos] &&
284 src_pic_block_same_info[1][pos + src_size] &&
285 src_pic_block_same_info[1][pos + quad_size * pic_width] &&
286 src_pic_block_same_info[1][pos + quad_size * pic_width + src_size] &&
287 src_pic_block_same_info[1][pos + src_size * pic_width] &&
288 src_pic_block_same_info[1][pos + src_size * pic_width + src_size];
289 pos++;
290 }
291 pos += block_size - 1;
292 }
293
294 if (block_size >= 4) {
295 const int size_minus_1 = block_size - 1;
296 pos = 0;
297 for (int y_pos = 0; y_pos < y_end; y_pos++) {
298 for (int x_pos = 0; x_pos < x_end; x_pos++) {
299 dst_pic_block_same_info[2][pos] =
300 (!dst_pic_block_same_info[0][pos] &&
301 !dst_pic_block_same_info[1][pos]) ||
302 (((x_pos & size_minus_1) == 0) && ((y_pos & size_minus_1) == 0));
303 pos++;
304 }
305 pos += block_size - 1;
306 }
307 }
308 }
309
av1_add_to_hash_map_by_row_with_precal_data(hash_table * p_hash_table,uint32_t * pic_hash[2],int8_t * pic_is_same,int pic_width,int pic_height,int block_size)310 void av1_add_to_hash_map_by_row_with_precal_data(hash_table *p_hash_table,
311 uint32_t *pic_hash[2],
312 int8_t *pic_is_same,
313 int pic_width, int pic_height,
314 int block_size) {
315 const int x_end = pic_width - block_size + 1;
316 const int y_end = pic_height - block_size + 1;
317
318 const int8_t *src_is_added = pic_is_same;
319 const uint32_t *src_hash[2] = { pic_hash[0], pic_hash[1] };
320
321 int add_value = hash_block_size_to_index(block_size);
322 assert(add_value >= 0);
323 add_value <<= kSrcBits;
324 const int crc_mask = (1 << kSrcBits) - 1;
325
326 for (int x_pos = 0; x_pos < x_end; x_pos++) {
327 for (int y_pos = 0; y_pos < y_end; y_pos++) {
328 const int pos = y_pos * pic_width + x_pos;
329 // valid data
330 if (src_is_added[pos]) {
331 block_hash curr_block_hash;
332 curr_block_hash.x = x_pos;
333 curr_block_hash.y = y_pos;
334
335 const uint32_t hash_value1 = (src_hash[0][pos] & crc_mask) + add_value;
336 curr_block_hash.hash_value2 = src_hash[1][pos];
337
338 hash_table_add_to_table(p_hash_table, hash_value1, &curr_block_hash);
339 }
340 }
341 }
342 }
343
av1_hash_is_horizontal_perfect(const YV12_BUFFER_CONFIG * picture,int block_size,int x_start,int y_start)344 int av1_hash_is_horizontal_perfect(const YV12_BUFFER_CONFIG *picture,
345 int block_size, int x_start, int y_start) {
346 const int stride = picture->y_stride;
347 const uint8_t *p = picture->y_buffer + y_start * stride + x_start;
348
349 if (picture->flags & YV12_FLAG_HIGHBITDEPTH) {
350 const uint16_t *p16 = CONVERT_TO_SHORTPTR(p);
351 for (int i = 0; i < block_size; i++) {
352 for (int j = 1; j < block_size; j++) {
353 if (p16[j] != p16[0]) {
354 return 0;
355 }
356 }
357 p16 += stride;
358 }
359 } else {
360 for (int i = 0; i < block_size; i++) {
361 for (int j = 1; j < block_size; j++) {
362 if (p[j] != p[0]) {
363 return 0;
364 }
365 }
366 p += stride;
367 }
368 }
369
370 return 1;
371 }
372
av1_hash_is_vertical_perfect(const YV12_BUFFER_CONFIG * picture,int block_size,int x_start,int y_start)373 int av1_hash_is_vertical_perfect(const YV12_BUFFER_CONFIG *picture,
374 int block_size, int x_start, int y_start) {
375 const int stride = picture->y_stride;
376 const uint8_t *p = picture->y_buffer + y_start * stride + x_start;
377
378 if (picture->flags & YV12_FLAG_HIGHBITDEPTH) {
379 const uint16_t *p16 = CONVERT_TO_SHORTPTR(p);
380 for (int i = 0; i < block_size; i++) {
381 for (int j = 1; j < block_size; j++) {
382 if (p16[j * stride + i] != p16[i]) {
383 return 0;
384 }
385 }
386 }
387 } else {
388 for (int i = 0; i < block_size; i++) {
389 for (int j = 1; j < block_size; j++) {
390 if (p[j * stride + i] != p[i]) {
391 return 0;
392 }
393 }
394 }
395 }
396 return 1;
397 }
398
av1_get_block_hash_value(IntraBCHashInfo * intrabc_hash_info,const uint8_t * y_src,int stride,int block_size,uint32_t * hash_value1,uint32_t * hash_value2,int use_highbitdepth)399 void av1_get_block_hash_value(IntraBCHashInfo *intrabc_hash_info,
400 const uint8_t *y_src, int stride, int block_size,
401 uint32_t *hash_value1, uint32_t *hash_value2,
402 int use_highbitdepth) {
403 int add_value = hash_block_size_to_index(block_size);
404 assert(add_value >= 0);
405 add_value <<= kSrcBits;
406 const int crc_mask = (1 << kSrcBits) - 1;
407
408 CRC_CALCULATOR *calc_1 = &intrabc_hash_info->crc_calculator1;
409 CRC_CALCULATOR *calc_2 = &intrabc_hash_info->crc_calculator2;
410 uint32_t **buf_1 = intrabc_hash_info->hash_value_buffer[0];
411 uint32_t **buf_2 = intrabc_hash_info->hash_value_buffer[1];
412
413 // 2x2 subblock hash values in current CU
414 int sub_block_in_width = (block_size >> 1);
415 if (use_highbitdepth) {
416 uint16_t pixel_to_hash[4];
417 uint16_t *y16_src = CONVERT_TO_SHORTPTR(y_src);
418 for (int y_pos = 0; y_pos < block_size; y_pos += 2) {
419 for (int x_pos = 0; x_pos < block_size; x_pos += 2) {
420 int pos = (y_pos >> 1) * sub_block_in_width + (x_pos >> 1);
421 get_pixels_in_1D_short_array_by_block_2x2(
422 y16_src + y_pos * stride + x_pos, stride, pixel_to_hash);
423 assert(pos < AOM_BUFFER_SIZE_FOR_BLOCK_HASH);
424 buf_1[0][pos] = av1_get_crc_value(calc_1, (uint8_t *)pixel_to_hash,
425 sizeof(pixel_to_hash));
426 buf_2[0][pos] = av1_get_crc_value(calc_2, (uint8_t *)pixel_to_hash,
427 sizeof(pixel_to_hash));
428 }
429 }
430 } else {
431 uint8_t pixel_to_hash[4];
432 for (int y_pos = 0; y_pos < block_size; y_pos += 2) {
433 for (int x_pos = 0; x_pos < block_size; x_pos += 2) {
434 int pos = (y_pos >> 1) * sub_block_in_width + (x_pos >> 1);
435 get_pixels_in_1D_char_array_by_block_2x2(y_src + y_pos * stride + x_pos,
436 stride, pixel_to_hash);
437 assert(pos < AOM_BUFFER_SIZE_FOR_BLOCK_HASH);
438 buf_1[0][pos] =
439 av1_get_crc_value(calc_1, pixel_to_hash, sizeof(pixel_to_hash));
440 buf_2[0][pos] =
441 av1_get_crc_value(calc_2, pixel_to_hash, sizeof(pixel_to_hash));
442 }
443 }
444 }
445
446 int src_sub_block_in_width = sub_block_in_width;
447 sub_block_in_width >>= 1;
448
449 int src_idx = 1;
450 int dst_idx = 0;
451
452 // 4x4 subblock hash values to current block hash values
453 uint32_t to_hash[4];
454 for (int sub_width = 4; sub_width <= block_size; sub_width *= 2) {
455 src_idx = 1 - src_idx;
456 dst_idx = 1 - dst_idx;
457
458 int dst_pos = 0;
459 for (int y_pos = 0; y_pos < sub_block_in_width; y_pos++) {
460 for (int x_pos = 0; x_pos < sub_block_in_width; x_pos++) {
461 int srcPos = (y_pos << 1) * src_sub_block_in_width + (x_pos << 1);
462
463 assert(srcPos + 1 < AOM_BUFFER_SIZE_FOR_BLOCK_HASH);
464 assert(srcPos + src_sub_block_in_width + 1 <
465 AOM_BUFFER_SIZE_FOR_BLOCK_HASH);
466 assert(dst_pos < AOM_BUFFER_SIZE_FOR_BLOCK_HASH);
467 to_hash[0] = buf_1[src_idx][srcPos];
468 to_hash[1] = buf_1[src_idx][srcPos + 1];
469 to_hash[2] = buf_1[src_idx][srcPos + src_sub_block_in_width];
470 to_hash[3] = buf_1[src_idx][srcPos + src_sub_block_in_width + 1];
471
472 buf_1[dst_idx][dst_pos] =
473 av1_get_crc_value(calc_1, (uint8_t *)to_hash, sizeof(to_hash));
474
475 to_hash[0] = buf_2[src_idx][srcPos];
476 to_hash[1] = buf_2[src_idx][srcPos + 1];
477 to_hash[2] = buf_2[src_idx][srcPos + src_sub_block_in_width];
478 to_hash[3] = buf_2[src_idx][srcPos + src_sub_block_in_width + 1];
479 buf_2[dst_idx][dst_pos] =
480 av1_get_crc_value(calc_2, (uint8_t *)to_hash, sizeof(to_hash));
481 dst_pos++;
482 }
483 }
484
485 src_sub_block_in_width = sub_block_in_width;
486 sub_block_in_width >>= 1;
487 }
488
489 *hash_value1 = (buf_1[dst_idx][0] & crc_mask) + add_value;
490 *hash_value2 = buf_2[dst_idx][0];
491 }
492