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