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