Coverage Report

Created: 2022-08-24 06:17

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