Commit 6343c41604 for aom
commit 6343c416040fe3e4dafa8780e385e84bb01e8368
Author: Ihor Buhaiov <freedbrt@gmail.com>
Date: Sun Oct 11 14:49:11 2026 +0200
Build one IntraBC hash table per tile in parallel
The IntraBC hash table covers the whole frame, and the main thread
builds it before any tile is encoded. For a 2560x1440 screen key frame
at speed 11 that takes about 21 ms, a third of the key frame time with
4 threads.
A block can only copy from its own tile, but every tile searched the
same table. With 2x2 tiles, half to two thirds of the entries in a
bucket pointed into another tile, and the search only dropped them
after checking them. At speed 11 it looks at the first 64 entries of
a bucket, so a tile could miss every copy it was allowed to use.
Give each tile its own table with only the blocks that lie inside it.
The encoder threads build the tables before the tiles are encoded, one
tile per job, and av1_intrabc_hash_search() uses the table of the
current tile. With one tile the table is the same as before, so the
output does not change. A frame with more than 16 tiles keeps a single
table for the whole frame, which bounds the memory.
The bucket arrays are now allocated only for the block sizes that get
built. At speed 11 that is just 8x8, so a table needs 384 KB of buckets
instead of 2.36 MB.
On four 2560x1440 screen recordings and one 2559x1372, at speed 11 with
IntraBC on, 20 key frames each: with 4 threads and 2x2 tiles the wall
time drops by 23% to 28% on an Apple M3 Pro (14 to 16 ms per key frame)
and by 28% to 31% on an AMD Ryzen 9 5900X built with MSVC (31 to 36
ms). With 2 threads and 2x1 tiles it drops by 8% to 13% on the M3 Pro
(8 to 12 ms) and by 17% to 20% on the 5900X (31 to 36 ms). With 1
thread the output and the time stay the same. The CPU time ends up
between 2% lower and 4% higher. With more than one tile the output
changes, and the recordings got up to 0.05% smaller.
IntraBCTilesTest encodes a key frame of repeated noise with several
tile layouts and thread counts, and checks that IntraBC saves more than
half of the frame. Before this change the case with 4x2 tiles on 2
threads saved only 34%.
Bug: 576320193
Change-Id: I134e0a9724ceca37ebee05b3f940ecd6b9f354b2
diff --git a/av1/encoder/encodeframe.c b/av1/encoder/encodeframe.c
index fe11b81f14..c7eb82a7ff 100644
--- a/av1/encoder/encodeframe.c
+++ b/av1/encoder/encodeframe.c
@@ -2064,9 +2064,130 @@ static void populate_thresh_to_force_zeromv_skip(AV1_COMP *cpi) {
}
}
-static void free_block_hash_buffers(uint32_t *block_hash_values[2]) {
+static void free_block_hash_buffers(IntraBCHashInfo *intrabc_hash_info) {
for (int j = 0; j < 2; ++j) {
- aom_free(block_hash_values[j]);
+ aom_free(intrabc_hash_info->frame_hash_buffer[j]);
+ intrabc_hash_info->frame_hash_buffer[j] = NULL;
+ }
+ intrabc_hash_info->frame_hash_width = 0;
+ intrabc_hash_info->frame_hash_height = 0;
+}
+
+// Gets the region covered by the hash table with the given index. That is the
+// region of the tile with this index, or the whole frame if there is one table.
+static void get_intrabc_hash_region(const YV12_BUFFER_CONFIG *source,
+ const AV1_COMMON *cm, int num_tables,
+ int table_idx, IntraBCHashRegion *region) {
+ region->x_start = 0;
+ region->y_start = 0;
+ region->x_end = source->y_crop_width;
+ region->y_end = source->y_crop_height;
+ if (num_tables > 1) {
+ TileInfo tile;
+ av1_tile_init(&tile, cm, table_idx / cm->tiles.cols,
+ table_idx % cm->tiles.cols);
+ region->x_start = tile.mi_col_start * MI_SIZE;
+ region->y_start = tile.mi_row_start * MI_SIZE;
+ region->x_end = AOMMIN(tile.mi_col_end * MI_SIZE, region->x_end);
+ region->y_end = AOMMIN(tile.mi_row_end * MI_SIZE, region->y_end);
+ }
+}
+
+bool av1_build_intrabc_hash_table(AV1_COMP *cpi, int table_idx) {
+ const AV1_COMMON *const cm = &cpi->common;
+ IntraBCHashInfo *const intrabc_hash_info = &cpi->td.mb.intrabc_hash_info;
+ // The frame hash buffers are only used with cpi->source, which must have the
+ // frame size they were allocated for.
+ uint32_t **const block_hash_values = intrabc_hash_info->frame_hash_buffer;
+ const int pic_width = cpi->source->y_crop_width;
+ const int pic_height = cpi->source->y_crop_height;
+ if (pic_width != intrabc_hash_info->frame_hash_width ||
+ pic_height != intrabc_hash_info->frame_hash_height) {
+ return false;
+ }
+ IntraBCHashRegion region;
+ get_intrabc_hash_region(cpi->source, cm, intrabc_hash_info->num_tile_tables,
+ table_idx, ®ion);
+
+ av1_generate_block_2x2_hash_value(cpi->source, ®ion, block_hash_values[0]);
+ // Hash data generated for screen contents is used for intraBC ME
+ const int min_alloc_size = block_size_wide[cm->mi_params.mi_alloc_bsize];
+ int max_sb_size = 1 << (cm->seq_params->mib_size_log2 + MI_SIZE_LOG2);
+
+ if (cpi->sf.mv_sf.hash_max_8x8_intrabc_blocks) {
+ max_sb_size = AOMMIN(8, max_sb_size);
+ }
+
+ int src_idx = 0;
+ for (int size = 4; size <= max_sb_size; size *= 2, src_idx = !src_idx) {
+ const int dst_idx = !src_idx;
+ av1_generate_block_hash_value(intrabc_hash_info, cpi->source, ®ion, size,
+ block_hash_values[src_idx],
+ block_hash_values[dst_idx]);
+ if (size >= min_alloc_size &&
+ !av1_add_to_hash_map_by_row_with_precal_data(
+ &intrabc_hash_info->tile_tables[table_idx],
+ block_hash_values[dst_idx], pic_width, ®ion, size)) {
+ return false;
+ }
+ }
+ return true;
+}
+
+// Builds the hash tables for intrabc. A block can only copy from its own tile,
+// so each tile gets its own table with only the blocks that lie inside it. The
+// encoder threads build the tables before the tiles are encoded, one table per
+// job, and av1_intrabc_hash_search() uses the table of the current tile. A
+// frame with more than MAX_INTRABC_HASH_TABLES tiles keeps a single table for
+// the whole frame, which bounds the memory.
+static void build_intrabc_hash_tables(AV1_COMP *cpi) {
+ AV1_COMMON *const cm = &cpi->common;
+ MultiThreadInfo *const mt_info = &cpi->mt_info;
+ IntraBCHashInfo *const intrabc_hash_info = &cpi->td.mb.intrabc_hash_info;
+ const int pic_width = cpi->source->y_crop_width;
+ const int pic_height = cpi->source->y_crop_height;
+ const int num_tiles = cm->tiles.cols * cm->tiles.rows;
+ const int num_tables = num_tiles <= MAX_INTRABC_HASH_TABLES ? num_tiles : 1;
+ bool error = false;
+
+ free_block_hash_buffers(intrabc_hash_info);
+ for (int j = 0; j < 2; ++j) {
+ intrabc_hash_info->frame_hash_buffer[j] = (uint32_t *)aom_malloc(
+ sizeof(*intrabc_hash_info->frame_hash_buffer[j]) * pic_width *
+ pic_height);
+ if (!intrabc_hash_info->frame_hash_buffer[j]) {
+ error = true;
+ break;
+ }
+ }
+ if (!error) {
+ intrabc_hash_info->frame_hash_width = pic_width;
+ intrabc_hash_info->frame_hash_height = pic_height;
+ }
+
+ av1_hash_table_init(intrabc_hash_info);
+ if (error || !av1_hash_tables_create(intrabc_hash_info, num_tables)) {
+ free_block_hash_buffers(intrabc_hash_info);
+ aom_internal_error(cm->error, AOM_CODEC_MEM_ERROR,
+ "Error allocating intrabc_hash_table and buffers");
+ }
+
+ const int num_workers =
+ AOMMIN(AOMMIN(mt_info->num_mod_workers[MOD_ENC], mt_info->num_workers),
+ num_tables);
+ if (num_workers > 1) {
+ av1_build_intrabc_hash_tables_mt(cpi, num_workers);
+ } else {
+ for (int i = 0; i < num_tables && !error; i++) {
+ error = !av1_build_intrabc_hash_table(cpi, i);
+ }
+ }
+
+ free_block_hash_buffers(intrabc_hash_info);
+
+ if (error) {
+ aom_internal_error(cm->error, AOM_CODEC_MEM_ERROR,
+ "Error adding data to intrabc_hash_table");
}
}
@@ -2307,7 +2428,6 @@ static inline void encode_frame_internal(AV1_COMP *cpi) {
&cpi->ppi->temp_frame_probs_simulation;
#endif
FrameProbInfo *const frame_probs = &cpi->ppi->frame_probs;
- IntraBCHashInfo *const intrabc_hash_info = &x->intrabc_hash_info;
MultiThreadInfo *const mt_info = &cpi->mt_info;
AV1EncRowMultiThreadInfo *const enc_row_mt = &mt_info->enc_row_mt;
const AV1EncoderConfig *const oxcf = &cpi->oxcf;
@@ -2354,58 +2474,7 @@ static inline void encode_frame_internal(AV1_COMP *cpi) {
(!cpi->sf.rt_sf.use_nonrd_pick_mode || cpi->sf.rt_sf.rt_use_intrabc)) {
// TODO(any): move this outside of the recoding loop to avoid recalculating
// the hash table.
- // add to hash table
- const int pic_width = cpi->source->y_crop_width;
- const int pic_height = cpi->source->y_crop_height;
- uint32_t *block_hash_values[2] = { NULL }; // two buffers used ping-pong
- bool error = false;
-
- for (int j = 0; j < 2; ++j) {
- block_hash_values[j] = (uint32_t *)aom_malloc(
- sizeof(*block_hash_values[j]) * pic_width * pic_height);
- if (!block_hash_values[j]) {
- error = true;
- break;
- }
- }
-
- av1_hash_table_init(intrabc_hash_info);
- if (error ||
- !av1_hash_table_create(&intrabc_hash_info->intrabc_hash_table)) {
- free_block_hash_buffers(block_hash_values);
- aom_internal_error(cm->error, AOM_CODEC_MEM_ERROR,
- "Error allocating intrabc_hash_table and buffers");
- }
- av1_generate_block_2x2_hash_value(cpi->source, block_hash_values[0]);
- // Hash data generated for screen contents is used for intraBC ME
- const int min_alloc_size = block_size_wide[mi_params->mi_alloc_bsize];
- int max_sb_size = (1 << (cm->seq_params->mib_size_log2 + MI_SIZE_LOG2));
-
- if (cpi->sf.mv_sf.hash_max_8x8_intrabc_blocks) {
- max_sb_size = AOMMIN(8, max_sb_size);
- }
-
- int src_idx = 0;
- for (int size = 4; size <= max_sb_size; size *= 2, src_idx = !src_idx) {
- const int dst_idx = !src_idx;
- av1_generate_block_hash_value(intrabc_hash_info, cpi->source, size,
- block_hash_values[src_idx],
- block_hash_values[dst_idx]);
- if (size >= min_alloc_size &&
- !av1_add_to_hash_map_by_row_with_precal_data(
- &intrabc_hash_info->intrabc_hash_table,
- block_hash_values[dst_idx], pic_width, pic_height, size)) {
- error = true;
- break;
- }
- }
-
- free_block_hash_buffers(block_hash_values);
-
- if (error) {
- aom_internal_error(cm->error, AOM_CODEC_MEM_ERROR,
- "Error adding data to intrabc_hash_table");
- }
+ build_intrabc_hash_tables(cpi);
}
const CommonQuantParams *quant_params = &cm->quant_params;
diff --git a/av1/encoder/encodeframe.h b/av1/encoder/encodeframe.h
index 077265d8cd..1b5356be2b 100644
--- a/av1/encoder/encodeframe.h
+++ b/av1/encoder/encodeframe.h
@@ -12,6 +12,8 @@
#ifndef AOM_AV1_ENCODER_ENCODEFRAME_H_
#define AOM_AV1_ENCODER_ENCODEFRAME_H_
+#include <stdbool.h>
+
#include "aom/aom_integer.h"
#include "av1/common/blockd.h"
#include "av1/common/enums.h"
@@ -48,6 +50,13 @@ void av1_encode_tile(struct AV1_COMP *cpi, struct ThreadData *td, int tile_row,
int tile_col);
void av1_encode_sb_row(struct AV1_COMP *cpi, struct ThreadData *td,
int tile_row, int tile_col, int mi_row);
+
+// Builds the intrabc hash table with the given index. It holds the blocks of
+// the tile with the same index, or of the whole frame when there is a single
+// table. Returns false if it runs out of memory, or if the frame hash buffers
+// were not allocated for the size of cpi->source.
+bool av1_build_intrabc_hash_table(struct AV1_COMP *cpi, int table_idx);
+
#ifdef __cplusplus
} // extern "C"
#endif
diff --git a/av1/encoder/encoder_alloc.h b/av1/encoder/encoder_alloc.h
index fc3143a3d9..4ee8301d37 100644
--- a/av1/encoder/encoder_alloc.h
+++ b/av1/encoder/encoder_alloc.h
@@ -356,7 +356,7 @@ static inline void dealloc_compressor_data(AV1_COMP *cpi) {
cpi->td.mb.intrabc_hash_info.hash_value_buffer[i] = NULL;
}
- av1_hash_table_destroy(&cpi->td.mb.intrabc_hash_info.intrabc_hash_table);
+ av1_hash_tables_destroy(&cpi->td.mb.intrabc_hash_info);
aom_free(cm->tpl_mvs);
cm->tpl_mvs = NULL;
diff --git a/av1/encoder/ethread.c b/av1/encoder/ethread.c
index dcbc744cb8..5a1e8a5627 100644
--- a/av1/encoder/ethread.c
+++ b/av1/encoder/ethread.c
@@ -2000,6 +2000,53 @@ void av1_encode_tiles_row_mt(AV1_COMP *cpi) {
accumulate_counters_enc_workers(cpi, num_workers);
}
+// Builds the intrabc hash tables with index start, start + num_workers, ...
+static int intrabc_hash_worker_hook(void *arg1, void *arg2) {
+ EncWorkerData *const thread_data = (EncWorkerData *)arg1;
+ const int num_workers = (int)(intptr_t)arg2;
+ AV1_COMP *const cpi = thread_data->cpi;
+ struct aom_internal_error_info *const error_info = &thread_data->error_info;
+ const int num_tables = cpi->td.mb.intrabc_hash_info.num_tile_tables;
+
+ // The jmp_buf is valid only for the duration of the function that calls
+ // setjmp(). Therefore, this function must reset the 'setjmp' field to 0
+ // before it returns.
+ if (setjmp(error_info->jmp)) {
+ error_info->setjmp = 0;
+ return 0;
+ }
+ error_info->setjmp = 1;
+
+ for (int i = thread_data->start; i < num_tables; i += num_workers) {
+ if (!av1_build_intrabc_hash_table(cpi, i)) {
+ aom_internal_error(error_info, AOM_CODEC_MEM_ERROR,
+ "Error adding data to intrabc_hash_table");
+ }
+ }
+ error_info->setjmp = 0;
+ return 1;
+}
+
+void av1_build_intrabc_hash_tables_mt(AV1_COMP *cpi, int num_workers) {
+ MultiThreadInfo *const mt_info = &cpi->mt_info;
+ for (int i = num_workers - 1; i >= 0; i--) {
+ AVxWorker *const worker = &mt_info->workers[i];
+ EncWorkerData *const thread_data = &mt_info->tile_thr_data[i];
+
+ worker->hook = intrabc_hash_worker_hook;
+ worker->data1 = thread_data;
+ worker->data2 = (void *)(intptr_t)num_workers;
+
+ thread_data->thread_id = i;
+ thread_data->start = i;
+ thread_data->cpi = cpi;
+ // sync_enc_workers() needs the td of the main thread.
+ if (i == 0) thread_data->td = &cpi->td;
+ }
+ launch_workers(mt_info, num_workers);
+ sync_enc_workers(mt_info, &cpi->common, num_workers);
+}
+
#if !CONFIG_REALTIME_ONLY
static void dealloc_thread_data_src_diff_buf(AV1_COMP *cpi, int num_workers) {
for (int i = num_workers - 1; i >= 0; --i) {
diff --git a/av1/encoder/ethread.h b/av1/encoder/ethread.h
index 76cbd8eddd..38f28403dc 100644
--- a/av1/encoder/ethread.h
+++ b/av1/encoder/ethread.h
@@ -42,6 +42,9 @@ void av1_row_mt_sync_write_dummy(AV1EncRowMultiThreadSync *row_mt_sync, int r,
void av1_encode_tiles_mt(struct AV1_COMP *cpi);
void av1_encode_tiles_row_mt(struct AV1_COMP *cpi);
+// Builds the intrabc hash tables of all tiles with num_workers threads.
+void av1_build_intrabc_hash_tables_mt(struct AV1_COMP *cpi, int num_workers);
+
#if !CONFIG_REALTIME_ONLY
void av1_fp_encode_tiles_row_mt(AV1_COMP *cpi);
diff --git a/av1/encoder/hash_motion.c b/av1/encoder/hash_motion.c
index 783c165186..c1ffdb7ed9 100644
--- a/av1/encoder/hash_motion.c
+++ b/av1/encoder/hash_motion.c
@@ -20,11 +20,10 @@
#include "av1/encoder/hash_motion.h"
#define kSrcBits 16
-// kMaxAddr is the number of hash table buckets. They form 6 hash tables of
-// 1 << kSrcBits buckets each. Each of the 6 supported block sizes (4, 8, 16,
-// 32, 64, 128) has its own hash table, indexed by the return value of
+// Each of the 6 supported block sizes (4, 8, 16, 32, 64, 128) has its own set
+// of 1 << kSrcBits buckets, indexed by the return value of
// hash_block_size_to_index().
-#define kMaxAddr (6 << kSrcBits)
+#define kBucketsPerBlockSize (1 << kSrcBits)
#define kMaxCandidatesPerHashBucket 256
static void get_pixels_in_1D_char_array_by_block_2x2(const uint8_t *y_src,
@@ -95,29 +94,76 @@ void av1_hash_table_init(IntraBCHashInfo *intrabc_hash_info) {
}
}
-void av1_hash_table_destroy(hash_table *p_hash_table) {
- aom_free(p_hash_table->bucket_count);
- aom_free(p_hash_table->bucket_start);
+static void hash_table_destroy(hash_table *p_hash_table) {
for (int i = 0; i < NELEMENTS(p_hash_table->block_hashes); i++) {
+ aom_free(p_hash_table->bucket_count[i]);
+ aom_free(p_hash_table->bucket_start[i]);
aom_free(p_hash_table->block_hashes[i]);
}
memset(p_hash_table, 0, sizeof(*p_hash_table));
}
// Empties the table. The buffers are kept for the next frame.
-bool av1_hash_table_create(hash_table *p_hash_table) {
- if (p_hash_table->bucket_count == NULL) {
- p_hash_table->bucket_count =
- aom_malloc(kMaxAddr * sizeof(*p_hash_table->bucket_count));
- p_hash_table->bucket_start =
- aom_malloc(kMaxAddr * sizeof(*p_hash_table->bucket_start));
- if (!p_hash_table->bucket_count || !p_hash_table->bucket_start) {
- av1_hash_table_destroy(p_hash_table);
- return false;
- }
+static void hash_table_clear(hash_table *p_hash_table) {
+ for (int i = 0; i < NELEMENTS(p_hash_table->bucket_count); i++) {
+ if (p_hash_table->bucket_count[i] == NULL) continue;
+ memset(p_hash_table->bucket_count[i], 0,
+ kBucketsPerBlockSize * sizeof(*p_hash_table->bucket_count[i]));
+ }
+}
+
+static void free_tile_tables(IntraBCHashInfo *intrabc_hash_info) {
+ for (int i = 0; i < intrabc_hash_info->num_tile_tables; i++) {
+ hash_table_destroy(&intrabc_hash_info->tile_tables[i]);
+ }
+ aom_free(intrabc_hash_info->tile_tables);
+ intrabc_hash_info->tile_tables = NULL;
+ intrabc_hash_info->num_tile_tables = 0;
+}
+
+bool av1_hash_tables_create(IntraBCHashInfo *intrabc_hash_info,
+ int num_tables) {
+ if (intrabc_hash_info->num_tile_tables != num_tables) {
+ free_tile_tables(intrabc_hash_info);
+ intrabc_hash_info->tile_tables = (hash_table *)aom_calloc(
+ num_tables, sizeof(*intrabc_hash_info->tile_tables));
+ if (intrabc_hash_info->tile_tables == NULL) return false;
+ intrabc_hash_info->num_tile_tables = num_tables;
+ }
+ for (int i = 0; i < num_tables; i++) {
+ hash_table_clear(&intrabc_hash_info->tile_tables[i]);
+ }
+ return true;
+}
+
+void av1_hash_tables_destroy(IntraBCHashInfo *intrabc_hash_info) {
+ free_tile_tables(intrabc_hash_info);
+ for (int i = 0; i < 2; i++) {
+ aom_free(intrabc_hash_info->frame_hash_buffer[i]);
+ intrabc_hash_info->frame_hash_buffer[i] = NULL;
+ }
+ intrabc_hash_info->frame_hash_width = 0;
+ intrabc_hash_info->frame_hash_height = 0;
+}
+
+// Makes room for the buckets of one block size, if it has none yet. Only the
+// block sizes that get built have buckets. With hash_max_8x8_intrabc_blocks
+// that is just 8x8.
+static bool hash_table_reserve_buckets(hash_table *p_hash_table,
+ int size_index) {
+ if (p_hash_table->bucket_count[size_index] != NULL) return true;
+ p_hash_table->bucket_count[size_index] = (uint16_t *)aom_calloc(
+ kBucketsPerBlockSize, sizeof(*p_hash_table->bucket_count[size_index]));
+ p_hash_table->bucket_start[size_index] = (uint32_t *)aom_malloc(
+ kBucketsPerBlockSize * sizeof(*p_hash_table->bucket_start[size_index]));
+ if (p_hash_table->bucket_count[size_index] == NULL ||
+ p_hash_table->bucket_start[size_index] == NULL) {
+ aom_free(p_hash_table->bucket_count[size_index]);
+ aom_free(p_hash_table->bucket_start[size_index]);
+ p_hash_table->bucket_count[size_index] = NULL;
+ p_hash_table->bucket_start[size_index] = NULL;
+ return false;
}
- memset(p_hash_table->bucket_count, 0,
- kMaxAddr * sizeof(*p_hash_table->bucket_count));
return true;
}
@@ -143,29 +189,35 @@ static inline void add_to_bucket_count(uint16_t *count, int n) {
int32_t av1_hash_table_count(const hash_table *p_hash_table,
uint32_t hash_value) {
- return p_hash_table->bucket_count[hash_value];
+ const uint16_t *const bucket_count =
+ p_hash_table->bucket_count[hash_value >> kSrcBits];
+ if (bucket_count == NULL) return 0;
+ return bucket_count[hash_value % kBucketsPerBlockSize];
}
const block_hash *av1_hash_get_first_block_hash(const hash_table *p_hash_table,
uint32_t hash_value) {
assert(av1_hash_table_count(p_hash_table, hash_value) > 0);
- const block_hash *const block_hashes =
- p_hash_table->block_hashes[hash_value >> kSrcBits];
- return &block_hashes[p_hash_table->bucket_start[hash_value]];
+ const int size_index = hash_value >> kSrcBits;
+ const uint32_t bucket = hash_value % kBucketsPerBlockSize;
+ const block_hash *const block_hashes = p_hash_table->block_hashes[size_index];
+ return &block_hashes[p_hash_table->bucket_start[size_index][bucket]];
}
void av1_generate_block_2x2_hash_value(const YV12_BUFFER_CONFIG *picture,
+ const IntraBCHashRegion *region,
uint32_t *pic_block_hash) {
const int width = 2;
const int height = 2;
- const int x_end = picture->y_crop_width - width + 1;
- const int y_end = picture->y_crop_height - height + 1;
+ const int pic_width = picture->y_crop_width;
+ const int x_end = region->x_end - width + 1;
+ const int y_end = region->y_end - height + 1;
if (picture->flags & YV12_FLAG_HIGHBITDEPTH) {
uint16_t p[4];
- int pos = 0;
- for (int y_pos = 0; y_pos < y_end; y_pos++) {
- for (int x_pos = 0; x_pos < x_end; x_pos++) {
+ for (int y_pos = region->y_start; y_pos < y_end; y_pos++) {
+ uint32_t *const row_hash = pic_block_hash + y_pos * pic_width;
+ for (int x_pos = region->x_start; x_pos < x_end; x_pos++) {
get_pixels_in_1D_short_array_by_block_2x2(
CONVERT_TO_SHORTPTR(picture->y_buffer) + y_pos * picture->y_stride +
x_pos,
@@ -173,16 +225,14 @@ void av1_generate_block_2x2_hash_value(const YV12_BUFFER_CONFIG *picture,
// For HBD, we either have 40 or 48 bits of input data that the xor hash
// reduce to 32 bits. We intentionally don't want to "discard" bits to
// avoid any kind of biasing.
- pic_block_hash[pos] = get_xor_hash_value_hbd(p[0], p[1], p[2], p[3]);
- pos++;
+ row_hash[x_pos] = get_xor_hash_value_hbd(p[0], p[1], p[2], p[3]);
}
- pos += width - 1;
}
} else {
uint8_t p[4];
- int pos = 0;
- for (int y_pos = 0; y_pos < y_end; y_pos++) {
- for (int x_pos = 0; x_pos < x_end; x_pos++) {
+ for (int y_pos = region->y_start; y_pos < y_end; y_pos++) {
+ uint32_t *const row_hash = pic_block_hash + y_pos * pic_width;
+ for (int x_pos = region->x_start; x_pos < x_end; x_pos++) {
get_pixels_in_1D_char_array_by_block_2x2(
picture->y_buffer + y_pos * picture->y_stride + x_pos,
picture->y_stride, p);
@@ -190,32 +240,31 @@ void av1_generate_block_2x2_hash_value(const YV12_BUFFER_CONFIG *picture,
// we can afford to just copy the 4 8-bit pixel values as a single
// 32-bit value directly. (i.e. there are no concerns of a lack of
// uniform distribution)
- pic_block_hash[pos] = get_identity_hash_value(p[0], p[1], p[2], p[3]);
- pos++;
+ row_hash[x_pos] = get_identity_hash_value(p[0], p[1], p[2], p[3]);
}
- pos += width - 1;
}
}
}
void av1_generate_block_hash_value(IntraBCHashInfo *intrabc_hash_info,
const YV12_BUFFER_CONFIG *picture,
+ const IntraBCHashRegion *region,
int block_size,
const uint32_t *src_pic_block_hash,
uint32_t *dst_pic_block_hash) {
CRC32C *calc = &intrabc_hash_info->crc_calculator;
const int pic_width = picture->y_crop_width;
- const int x_end = picture->y_crop_width - block_size + 1;
- const int y_end = picture->y_crop_height - block_size + 1;
+ const int x_end = region->x_end - block_size + 1;
+ const int y_end = region->y_end - block_size + 1;
const int src_size = block_size >> 1;
uint32_t p[4];
const int length = sizeof(p);
- int pos = 0;
- for (int y_pos = 0; y_pos < y_end; y_pos++) {
- for (int x_pos = 0; x_pos < x_end; x_pos++) {
+ for (int y_pos = region->y_start; y_pos < y_end; y_pos++) {
+ int pos = y_pos * pic_width + region->x_start;
+ for (int x_pos = region->x_start; x_pos < x_end; x_pos++) {
// Build up a bigger block from 4 smaller, non-overlapping source block
// hashes, and compute its hash. Note: source blocks at the right and
// bottom borders cannot be part of larger blocks, therefore they won't be
@@ -230,32 +279,32 @@ void av1_generate_block_hash_value(IntraBCHashInfo *intrabc_hash_info,
av1_get_crc32c_value(calc, (uint8_t *)p, length);
pos++;
}
- pos += block_size - 1;
}
}
-// Adds the blocks of one block size to the table. The counts of that block
-// size must be zero on entry, as av1_hash_table_create() leaves them. On
-// return they hold the number of entries in each bucket.
-bool av1_add_to_hash_map_by_row_with_precal_data(hash_table *p_hash_table,
- const uint32_t *pic_hash,
- int pic_width, int pic_height,
- int block_size) {
- const int x_end = pic_width - block_size + 1;
- const int y_end = pic_height - block_size + 1;
+// Adds the blocks of one block size that lie inside region to the table. The
+// counts of that block size must be zero on entry, as av1_hash_tables_create()
+// leaves them. On return they hold the number of entries in each bucket.
+bool av1_add_to_hash_map_by_row_with_precal_data(
+ hash_table *p_hash_table, const uint32_t *pic_hash, int pic_width,
+ const IntraBCHashRegion *region, int block_size) {
+ const int x_start = region->x_start;
+ const int y_start = region->y_start;
+ const int x_end = region->x_end - block_size + 1;
+ const int y_end = region->y_end - block_size + 1;
const int size_index = hash_block_size_to_index(block_size);
assert(size_index >= 0);
- const int add_value = size_index << kSrcBits;
- const int crc_mask = (1 << kSrcBits) - 1;
- uint16_t *const bucket_count = p_hash_table->bucket_count + add_value;
- uint32_t *const bucket_start = p_hash_table->bucket_start + add_value;
+ const int crc_mask = kBucketsPerBlockSize - 1;
int step = block_size;
int x_offset = 0;
int y_offset = 0;
- // No block of this size fits in the frame.
- if (x_end <= 0 || y_end <= 0) return true;
+ // No block of this size fits in the region.
+ if (x_end <= x_start || y_end <= y_start) return true;
+ if (!hash_table_reserve_buckets(p_hash_table, size_index)) return false;
+ uint16_t *const bucket_count = p_hash_table->bucket_count[size_index];
+ uint32_t *const bucket_start = p_hash_table->bucket_start[size_index];
// The next two loops set bucket_start. The first counts the blocks of each
// bucket, and the second places the buckets one after another.
@@ -266,11 +315,11 @@ bool av1_add_to_hash_map_by_row_with_precal_data(hash_table *p_hash_table,
// How many blocks each bucket keeps doesn't depend on the order they are
// added in, so count them first in raster order. Flat areas give long runs
// of the same bucket, so count a whole run at once.
- for (int y_pos = 0; y_pos < y_end; y_pos++) {
+ for (int y_pos = y_start; y_pos < y_end; y_pos++) {
const uint32_t *const row_hash = pic_hash + y_pos * pic_width;
- int bucket = row_hash[0] & crc_mask;
+ int bucket = row_hash[x_start] & crc_mask;
int run = 0;
- for (int x_pos = 0; x_pos < x_end; x_pos++) {
+ for (int x_pos = x_start; x_pos < x_end; x_pos++) {
const int curr_bucket = row_hash[x_pos] & crc_mask;
if (curr_bucket != bucket) {
add_to_bucket_count(&bucket_count[bucket], run);
@@ -296,10 +345,10 @@ bool av1_add_to_hash_map_by_row_with_precal_data(hash_table *p_hash_table,
}
block_hash *const block_hashes = p_hash_table->block_hashes[size_index];
- // Explore the entire frame hierarchically to add intrabc candidate blocks to
+ // Explore the entire region hierarchically to add intrabc candidate blocks to
// the hash table, by starting with coarser steps (the block size), towards
// finer-grained steps until every candidate block has been considered.
- // The nested for loop goes through the pic_hash array column by column.
+ // The nested for loop goes through the region column by column.
// Doing a hierarchical block exploration helps maximize spatial dispersion
// of the first and foremost candidate blocks while minimizing overlap between
@@ -326,8 +375,8 @@ bool av1_add_to_hash_map_by_row_with_precal_data(hash_table *p_hash_table,
// used is 2 (i.e. no two adjacent blocks will be explored consecutively).
// Also, the exploration is designed to visit each block candidate only once.
while (step > 1) {
- for (int x_pos = x_offset; x_pos < x_end; x_pos += step) {
- for (int y_pos = y_offset; y_pos < y_end; y_pos += step) {
+ for (int x_pos = x_start + x_offset; x_pos < x_end; x_pos += step) {
+ for (int y_pos = y_start + y_offset; y_pos < y_end; y_pos += step) {
const int pos = y_pos * pic_width + x_pos;
const int bucket = pic_hash[pos] & crc_mask;
const int count = bucket_count[bucket];
diff --git a/av1/encoder/hash_motion.h b/av1/encoder/hash_motion.h
index 936feaff9b..03558d2bd5 100644
--- a/av1/encoder/hash_motion.h
+++ b/av1/encoder/hash_motion.h
@@ -33,17 +33,34 @@ typedef struct _block_hash {
uint32_t hash_value2;
} block_hash;
-// The table keeps its buffers from frame to frame. cpi->td.mb owns them and
-// frees them with the encoder. The encoder threads read shallow copies of the
-// table in their own MACROBLOCK, so it must not change while they run.
+// The rectangle of the frame, in luma pixels, that a hash table takes its
+// blocks from. The end values are exclusive.
+typedef struct {
+ int x_start;
+ int y_start;
+ int x_end;
+ int y_end;
+} IntraBCHashRegion;
+
+// Frames with more tiles than this use one table for the whole frame, to keep
+// the memory down.
+// TODO: bug 576320193 - Let neighboring tiles share a table when there are
+// more tiles than this, instead of going back to one table.
+#define MAX_INTRABC_HASH_TABLES 16
+
+// A table keeps its buffers from frame to frame. cpi->td.mb owns it and frees
+// it with the encoder. The encoder threads build the tables before the tiles
+// are encoded, one table at a time per thread. After that they only read them
+// through the tile_tables pointer in their own MACROBLOCK, so a table must not
+// change while the tiles are encoded.
typedef struct _hash_table {
- // The number of entries in each bucket, and the index of its first entry in
- // the entries of its block size. Both arrays have kMaxAddr (6 << 16)
- // elements, one for each bucket of every block size.
- uint16_t *bucket_count;
- uint32_t *bucket_start;
- // The entries of each block size from 4x4 to 128x128, stored bucket after
- // bucket, and how many entries each array has room for.
+ // For each block size from 4x4 to 128x128, the number of entries in each
+ // bucket and the index of the first one. Each array has 1 << 16 elements,
+ // one for each bucket. NULL for the sizes not built.
+ uint16_t *bucket_count[6];
+ uint32_t *bucket_start[6];
+ // The entries of each block size, stored bucket after bucket, and how many
+ // entries each array has room for.
block_hash *block_hashes[6];
uint32_t block_hashes_size[6];
} hash_table;
@@ -56,31 +73,48 @@ typedef struct intrabc_hash_info {
// [two buffers used ping-pong]
// buffers are AOM_BUFFER_SIZE_FOR_BLOCK_HASH elements long
uint32_t *hash_value_buffer[2];
- hash_table intrabc_hash_table;
+ // One table per tile, indexed by tile_row * tile_cols + tile_col. A single
+ // table covers the whole frame when there is one tile, or too many.
+ hash_table *tile_tables;
+ int num_tile_tables;
+ // Hash values of every position of the frame, only needed while the tables
+ // are built (two buffers, used alternately). Each buffer has
+ // frame_hash_width * frame_hash_height elements, the luma size of the source
+ // frame they were allocated for. Both sizes are 0 when the buffers are freed.
+ uint32_t *frame_hash_buffer[2];
+ int frame_hash_width;
+ int frame_hash_height;
CRC32C crc_calculator;
int crc_initialized;
} IntraBCHashInfo;
void av1_hash_table_init(IntraBCHashInfo *intra_bc_hash_info);
-void av1_hash_table_destroy(hash_table *p_hash_table);
-bool av1_hash_table_create(hash_table *p_hash_table);
+// Makes num_tables empty tables. Their buffers are kept for the next frame
+// while the number of tables stays the same.
+bool av1_hash_tables_create(IntraBCHashInfo *intra_bc_hash_info,
+ int num_tables);
+// Frees the tables and the frame hash buffers.
+void av1_hash_tables_destroy(IntraBCHashInfo *intra_bc_hash_info);
int32_t av1_hash_table_count(const hash_table *p_hash_table,
uint32_t hash_value);
// Returns the first of the av1_hash_table_count() entries for hash_value.
const block_hash *av1_hash_get_first_block_hash(const hash_table *p_hash_table,
uint32_t hash_value);
+// These fill the hash values of the blocks that lie inside region. The buffers
+// use the width of the picture as stride.
void av1_generate_block_2x2_hash_value(const YV12_BUFFER_CONFIG *picture,
+ const IntraBCHashRegion *region,
uint32_t *pic_block_hash);
void av1_generate_block_hash_value(IntraBCHashInfo *intra_bc_hash_info,
const YV12_BUFFER_CONFIG *picture,
+ const IntraBCHashRegion *region,
int block_size,
const uint32_t *src_pic_block_hash,
uint32_t *dst_pic_block_hash);
-bool av1_add_to_hash_map_by_row_with_precal_data(hash_table *p_hash_table,
- const uint32_t *pic_hash,
- int pic_width, int pic_height,
- int block_size);
+bool av1_add_to_hash_map_by_row_with_precal_data(
+ hash_table *p_hash_table, const uint32_t *pic_hash, int pic_width,
+ const IntraBCHashRegion *region, int block_size);
// check whether the block starts from (x_start, y_start) with the size of
// block_size x block_size has the same color in all rows
diff --git a/av1/encoder/mcomp.c b/av1/encoder/mcomp.c
index 53b65a307a..aa622506a5 100644
--- a/av1/encoder/mcomp.c
+++ b/av1/encoder/mcomp.c
@@ -1931,8 +1931,13 @@ int av1_intrabc_hash_search(const AV1_COMP *cpi, const MACROBLOCKD *xd,
uint32_t hash_value1, hash_value2;
int best_hash_cost = INT_MAX;
- // for the hashMap
- hash_table *ref_frame_hash = &intrabc_hash_info->intrabc_hash_table;
+ // Every tile has its own table, as a block can only copy from its own tile.
+ assert(intrabc_hash_info->num_tile_tables > 0);
+ const int table_idx =
+ intrabc_hash_info->num_tile_tables > 1
+ ? xd->tile.tile_row * cpi->common.tiles.cols + xd->tile.tile_col
+ : 0;
+ const hash_table *ref_frame_hash = &intrabc_hash_info->tile_tables[table_idx];
av1_get_block_hash_value(intrabc_hash_info, src, src_stride, block_width,
&hash_value1, &hash_value2, is_cur_buf_hbd(xd));
diff --git a/test/encode_api_test.cc b/test/encode_api_test.cc
index d08748a2f6..76b36e7961 100644
--- a/test/encode_api_test.cc
+++ b/test/encode_api_test.cc
@@ -18,6 +18,7 @@
#include <cstring>
#include <initializer_list>
#include <memory>
+#include <ostream>
#include <tuple>
#include <vector>
@@ -4693,4 +4694,123 @@ TEST(EncodeAPI, Avg16x16IntegerOverflow) {
}
#endif // CONFIG_AV1_HIGHBITDEPTH
+// A key frame whose luma is a block of noise repeated over the frame. IntraBC
+// can copy every block from the one above it. The chroma is flat.
+class RepeatedNoiseVideoSource : public ::libaom_test::DummyVideoSource {
+ public:
+ RepeatedNoiseVideoSource(int width, int height) {
+ SetSize(width, height);
+ set_limit(1);
+ }
+
+ protected:
+ void FillFrame() override {
+ constexpr int kBlockSize = 64;
+ ::libaom_test::ACMRandom rnd(::libaom_test::ACMRandom::DeterministicSeed());
+ uint8_t noise[kBlockSize * kBlockSize];
+ for (uint8_t &value : noise) value = rnd.Rand8();
+ for (unsigned int row = 0; row < height_; ++row) {
+ uint8_t *line = img_->planes[0] + row * img_->stride[0];
+ for (unsigned int col = 0; col < width_; ++col) {
+ line[col] = noise[(row % kBlockSize) * kBlockSize + col % kBlockSize];
+ }
+ }
+ for (int plane = 1; plane < 3; ++plane) {
+ memset(img_->planes[plane], 128,
+ img_->stride[plane] * ((height_ + 1) / 2));
+ }
+ }
+};
+
+struct IntraBCTilesParams {
+ int tile_cols_log2;
+ int tile_rows_log2;
+ int threads;
+ int row_mt;
+};
+
+std::ostream &operator<<(std::ostream &os, const IntraBCTilesParams ¶ms) {
+ return os << params.tile_cols_log2 << "x" << params.tile_rows_log2
+ << " log2 tiles, " << params.threads << " threads, row_mt "
+ << params.row_mt;
+}
+
+// Encodes a realtime key frame of repeated noise with IntraBC on and off. The
+// frame has 256x256 pixels per tile. The encoder and the decoder must agree on
+// the frame.
+class IntraBCTilesTest : public ::libaom_test::EncoderTest,
+ public ::testing::TestWithParam<IntraBCTilesParams> {
+ protected:
+ IntraBCTilesTest() : EncoderTest(&::libaom_test::kAV1) {}
+ ~IntraBCTilesTest() override = default;
+
+ void SetUp() override {
+ InitializeConfig(::libaom_test::kRealTime);
+ cfg_.g_threads = GetParam().threads;
+ cfg_.rc_min_quantizer = 10;
+ cfg_.rc_max_quantizer = 10;
+ }
+
+ void PreEncodeFrameHook(::libaom_test::VideoSource * /*video*/,
+ ::libaom_test::Encoder *encoder) override {
+ encoder->Control(AOME_SET_CPUUSED, 11);
+ encoder->Control(AV1E_SET_TUNE_CONTENT, AOM_CONTENT_SCREEN);
+ encoder->Control(AV1E_SET_ENABLE_INTRABC, enable_intrabc_);
+ encoder->Control(AV1E_SET_TILE_COLUMNS, GetParam().tile_cols_log2);
+ encoder->Control(AV1E_SET_TILE_ROWS, GetParam().tile_rows_log2);
+ encoder->Control(AV1E_SET_ROW_MT, GetParam().row_mt);
+ }
+
+ void FramePktHook(const aom_codec_cx_pkt_t *pkt) override {
+ frame_size_ = pkt->data.frame.sz;
+ }
+
+ // Returns the size of the encoded key frame.
+ size_t EncodeKeyFrame(int enable_intrabc) {
+ RepeatedNoiseVideoSource video(256 << GetParam().tile_cols_log2,
+ 256 << GetParam().tile_rows_log2);
+ enable_intrabc_ = enable_intrabc;
+ frame_size_ = 0;
+ EXPECT_NO_FATAL_FAILURE(RunLoop(&video));
+ return frame_size_;
+ }
+
+ int enable_intrabc_ = 0;
+ size_t frame_size_ = 0;
+};
+
+// A block can only copy from its own tile, so every tile has to find the
+// copies of its own blocks. Most of each tile is a copy of the blocks above.
+TEST_P(IntraBCTilesTest, CopiesInsideTiles) {
+ const size_t size_without_intrabc = EncodeKeyFrame(0);
+ const size_t size_with_intrabc = EncodeKeyFrame(1);
+ ASSERT_GT(size_without_intrabc, 0u);
+ EXPECT_LT(size_with_intrabc * 2, size_without_intrabc);
+}
+
+const IntraBCTilesParams kIntraBCTilesParams[] = {
+ { 0, 0, 1, 0 }, // One tile.
+ { 1, 1, 1, 0 }, // Four tiles on one thread.
+ { 1, 0, 2, 1 }, // Two tiles on two threads.
+ { 1, 1, 4, 1 }, // Four tiles on four threads, as in a typical RTC setup.
+ { 1, 1, 4, 0 }, // Tile threads without row mt.
+ { 2, 1, 2, 1 }, // Eight tiles on two threads.
+};
+
+INSTANTIATE_TEST_SUITE_P(AV1, IntraBCTilesTest,
+ ::testing::ValuesIn(kIntraBCTilesParams));
+
+// With more tiles than the encoder keeps hash tables for, one table covers the
+// frame. The copies are not expected to be found, but the frame must decode.
+class IntraBCManyTilesTest : public IntraBCTilesTest {};
+
+TEST_P(IntraBCManyTilesTest, Decodes) { EXPECT_GT(EncodeKeyFrame(1), 0u); }
+
+const IntraBCTilesParams kIntraBCManyTilesParams[] = {
+ { 3, 2, 4, 1 }, // 32 tiles.
+};
+
+INSTANTIATE_TEST_SUITE_P(AV1, IntraBCManyTilesTest,
+ ::testing::ValuesIn(kIntraBCManyTilesParams));
+
} // namespace