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