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 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 (at) microsoft.com): is higher than 8 bits screen content supported? 38 // If yes, fix this function 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 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 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 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 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 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. 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 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 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 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 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 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 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 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 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 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 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 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 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 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
