hash based motion estimation for screen data
Change-Id: Iec7969ffd8f53ca2f4eefd1d757cfec7b3bde131
diff --git a/av1/av1.cmake b/av1/av1.cmake
index 7ac17c4..5295a1a 100644
--- a/av1/av1.cmake
+++ b/av1/av1.cmake
@@ -476,6 +476,15 @@
endif ()
endif ()
+if (CONFIG_HASH_ME)
+ set(AOM_AV1_ENCODER_SOURCES
+ ${AOM_AV1_ENCODER_SOURCES}
+ "${AOM_ROOT}/av1/encoder/hash_motion.h"
+ "${AOM_ROOT}/av1/encoder/hash_motion.c"
+ "${AOM_ROOT}/third_party/vector/vector.h"
+ "${AOM_ROOT}/third_party/vector/vector.c")
+endif ()
+
# Setup AV1 common/decoder/encoder targets. The libaom target must exist before
# this function is called.
function (setup_av1_targets)
diff --git a/av1/av1_cx.mk b/av1/av1_cx.mk
index bbe82e6..eca4920 100644
--- a/av1/av1_cx.mk
+++ b/av1/av1_cx.mk
@@ -108,6 +108,12 @@
AV1_CX_SRCS-yes += encoder/temporal_filter.h
AV1_CX_SRCS-yes += encoder/mbgraph.c
AV1_CX_SRCS-yes += encoder/mbgraph.h
+ifeq ($(CONFIG_HASH_ME),yes)
+AV1_CX_SRCS-yes += ../third_party/vector/vector.h
+AV1_CX_SRCS-yes += ../third_party/vector/vector.c
+AV1_CX_SRCS-yes += encoder/hash_motion.c
+AV1_CX_SRCS-yes += encoder/hash_motion.h
+endif
ifeq ($(CONFIG_CDEF),yes)
AV1_CX_SRCS-yes += encoder/pickcdef.c
endif
diff --git a/av1/common/alloccommon.c b/av1/common/alloccommon.c
index c37f1ea..69b2197 100644
--- a/av1/common/alloccommon.c
+++ b/av1/common/alloccommon.c
@@ -86,6 +86,9 @@
aom_free(pool->frame_bufs[i].mvs);
pool->frame_bufs[i].mvs = NULL;
aom_free_frame_buffer(&pool->frame_bufs[i].buf);
+#if CONFIG_HASH_ME
+ av1_hash_table_destroy(&pool->frame_bufs[i].hash_table);
+#endif
}
}
diff --git a/av1/common/onyxc_int.h b/av1/common/onyxc_int.h
index 66f7181..b101422 100644
--- a/av1/common/onyxc_int.h
+++ b/av1/common/onyxc_int.h
@@ -38,6 +38,10 @@
#if CONFIG_CFL
#include "av1/common/cfl.h"
#endif
+#if CONFIG_HASH_ME
+// TODO(youzhou@microsoft.com): Encoder only. Move it out of common
+#include "av1/encoder/hash_motion.h"
+#endif
#ifdef __cplusplus
extern "C" {
#endif
@@ -127,6 +131,9 @@
#endif // CONFIG_GLOBAL_MOTION
aom_codec_frame_buffer_t raw_frame_buffer;
YV12_BUFFER_CONFIG buf;
+#if CONFIG_HASH_ME
+ hash_table hash_table;
+#endif
#if CONFIG_TEMPMV_SIGNALING
uint8_t intra_only;
#endif
diff --git a/av1/encoder/encoder.c b/av1/encoder/encoder.c
index d995484..2dadc97 100644
--- a/av1/encoder/encoder.c
+++ b/av1/encoder/encoder.c
@@ -45,6 +45,9 @@
#endif
#include "av1/encoder/ethread.h"
#include "av1/encoder/firstpass.h"
+#if CONFIG_HASH_ME
+#include "av1/encoder/hash_motion.h"
+#endif
#include "av1/encoder/mbgraph.h"
#include "av1/encoder/picklpf.h"
#if CONFIG_LOOP_RESTORATION
@@ -5362,6 +5365,11 @@
cm->ref_frame_map[i] = INVALID_IDX;
pool->frame_bufs[i].ref_count = 0;
}
+#if CONFIG_HASH_ME
+ for (i = 0; i < FRAME_BUFFERS; ++i) {
+ av1_hash_table_init(&pool->frame_bufs[i].hash_table);
+ }
+#endif
}
static void check_initial_width(AV1_COMP *cpi,
@@ -6085,6 +6093,71 @@
Pass0Encode(cpi, size, dest, 0, frame_flags);
}
#endif
+#if CONFIG_HASH_ME
+ if (oxcf->pass != 1 && cpi->common.allow_screen_content_tools) {
+ // 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][2];
+ int8_t *is_block_same[2][3];
+ int k, j;
+
+ for (k = 0; k < 2; k++) {
+ for (j = 0; j < 2; j++) {
+ CHECK_MEM_ERROR(cm, block_hash_values[k][j],
+ aom_malloc(sizeof(uint32_t) * pic_width * pic_height));
+ }
+
+ for (j = 0; j < 3; j++) {
+ CHECK_MEM_ERROR(cm, is_block_same[k][j],
+ aom_malloc(sizeof(int8_t) * pic_width * pic_height));
+ }
+ }
+
+ av1_hash_table_create(&cm->cur_frame->hash_table);
+ av1_generate_block_2x2_hash_value(cpi->source, block_hash_values[0],
+ is_block_same[0]);
+ av1_generate_block_hash_value(cpi->source, 4, block_hash_values[0],
+ block_hash_values[1], is_block_same[0],
+ is_block_same[1]);
+ av1_generate_block_hash_value(cpi->source, 8, block_hash_values[1],
+ block_hash_values[0], is_block_same[1],
+ is_block_same[0]);
+ av1_add_to_hash_map_by_row_with_precal_data(
+ &cm->cur_frame->hash_table, block_hash_values[0], is_block_same[0][2],
+ pic_width, pic_height, 8);
+ av1_generate_block_hash_value(cpi->source, 16, block_hash_values[0],
+ block_hash_values[1], is_block_same[0],
+ is_block_same[1]);
+ av1_add_to_hash_map_by_row_with_precal_data(
+ &cm->cur_frame->hash_table, block_hash_values[1], is_block_same[1][2],
+ pic_width, pic_height, 16);
+ av1_generate_block_hash_value(cpi->source, 32, block_hash_values[1],
+ block_hash_values[0], is_block_same[1],
+ is_block_same[0]);
+ av1_add_to_hash_map_by_row_with_precal_data(
+ &cm->cur_frame->hash_table, block_hash_values[0], is_block_same[0][2],
+ pic_width, pic_height, 32);
+ av1_generate_block_hash_value(cpi->source, 64, block_hash_values[0],
+ block_hash_values[1], is_block_same[0],
+ is_block_same[1]);
+ av1_add_to_hash_map_by_row_with_precal_data(
+ &cm->cur_frame->hash_table, block_hash_values[1], is_block_same[1][2],
+ pic_width, pic_height, 64);
+
+ for (k = 0; k < 2; k++) {
+ for (j = 0; j < 2; j++) {
+ aom_free(block_hash_values[k][j]);
+ }
+
+ for (j = 0; j < 3; j++) {
+ aom_free(is_block_same[k][j]);
+ }
+ }
+ }
+
+#endif
+
#if CONFIG_NO_FRAME_CONTEXT_SIGNALING
cm->frame_contexts[cm->new_fb_idx] = *cm->fc;
#else
diff --git a/av1/encoder/encoder.h b/av1/encoder/encoder.h
index 66e509f..e71c91c 100644
--- a/av1/encoder/encoder.h
+++ b/av1/encoder/encoder.h
@@ -692,6 +692,17 @@
return (map_idx != INVALID_IDX) ? cm->ref_frame_map[map_idx] : INVALID_IDX;
}
+#if CONFIG_HASH_ME
+static INLINE hash_table *get_ref_frame_hash_map(const AV1_COMP *cpi,
+ MV_REFERENCE_FRAME ref_frame) {
+ const AV1_COMMON *const cm = &cpi->common;
+ const int buf_idx = get_ref_frame_buf_idx(cpi, ref_frame);
+ return buf_idx != INVALID_IDX
+ ? &cm->buffer_pool->frame_bufs[buf_idx].hash_table
+ : NULL;
+}
+#endif
+
static INLINE YV12_BUFFER_CONFIG *get_ref_frame_buffer(
const AV1_COMP *cpi, MV_REFERENCE_FRAME ref_frame) {
const AV1_COMMON *const cm = &cpi->common;
diff --git a/av1/encoder/hash_motion.c b/av1/encoder/hash_motion.c
new file mode 100644
index 0000000..8732b82
--- /dev/null
+++ b/av1/encoder/hash_motion.c
@@ -0,0 +1,445 @@
+#include <assert.h>
+#include "av1/encoder/hash_motion.h"
+#include "./av1_rtcd.h"
+
+typedef struct _crc_calculator {
+ uint32_t remainder;
+ uint32_t trunc_poly;
+ uint32_t bits;
+ uint32_t table[256];
+ uint32_t final_result_mask;
+} crc_calculator;
+
+static void crc_calculator_process_data(crc_calculator *p_crc_calculator,
+ uint8_t *pData, uint32_t dataLength) {
+ for (uint32_t i = 0; i < dataLength; i++) {
+ const uint8_t index =
+ (p_crc_calculator->remainder >> (p_crc_calculator->bits - 8)) ^
+ pData[i];
+ p_crc_calculator->remainder <<= 8;
+ p_crc_calculator->remainder ^= p_crc_calculator->table[index];
+ }
+}
+
+static void crc_calculator_reset(crc_calculator *p_crc_calculator) {
+ p_crc_calculator->remainder = 0;
+}
+
+static uint32_t crc_calculator_get_crc(crc_calculator *p_crc_calculator) {
+ return p_crc_calculator->remainder & p_crc_calculator->final_result_mask;
+}
+
+static void crc_calculator_init_table(crc_calculator *p_crc_calculator) {
+ const uint32_t high_bit = 1 << (p_crc_calculator->bits - 1);
+ const uint32_t byte_high_bit = 1 << (8 - 1);
+
+ for (uint32_t value = 0; value < 256; value++) {
+ uint32_t remainder = 0;
+ for (uint8_t mask = byte_high_bit; mask != 0; mask >>= 1) {
+ if (value & mask) {
+ remainder ^= high_bit;
+ }
+
+ if (remainder & high_bit) {
+ remainder <<= 1;
+ remainder ^= p_crc_calculator->trunc_poly;
+ } else {
+ remainder <<= 1;
+ }
+ }
+ p_crc_calculator->table[value] = remainder;
+ }
+}
+
+static void crc_calculator_init(crc_calculator *p_crc_calculator, uint32_t bits,
+ uint32_t truncPoly) {
+ p_crc_calculator->remainder = 0;
+ p_crc_calculator->bits = bits;
+ p_crc_calculator->trunc_poly = truncPoly;
+ p_crc_calculator->final_result_mask = (1 << bits) - 1;
+ crc_calculator_init_table(p_crc_calculator);
+}
+
+static const int crc_bits = 16;
+static const int block_size_bits = 2;
+
+static crc_calculator crc_calculator1;
+static crc_calculator crc_calculator2;
+static int g_crc_initialized = 0;
+
+static void hash_table_clear_all(hash_table *p_hash_table) {
+ if (p_hash_table->p_lookup_table == NULL) {
+ return;
+ }
+ int max_addr = 1 << (crc_bits + block_size_bits);
+ for (int i = 0; i < max_addr; i++) {
+ if (p_hash_table->p_lookup_table[i] != NULL) {
+ vector_destroy(p_hash_table->p_lookup_table[i]);
+ aom_free(p_hash_table->p_lookup_table[i]);
+ p_hash_table->p_lookup_table[i] = NULL;
+ }
+ }
+}
+
+static uint32_t get_crc_value1(uint8_t *p, int length) {
+ crc_calculator_reset(&crc_calculator1);
+ crc_calculator_process_data(&crc_calculator1, p, length);
+ return crc_calculator_get_crc(&crc_calculator1);
+}
+
+static uint32_t get_crc_value2(uint8_t *p, int length) {
+ crc_calculator_reset(&crc_calculator2);
+ crc_calculator_process_data(&crc_calculator2, p, length);
+ return crc_calculator_get_crc(&crc_calculator2);
+}
+
+// TODO(youzhou@microsoft.com): is higher than 8 bits screen content supported?
+// If yes, fix this function
+static void get_pixels_in_1D_char_array_by_block_2x2(uint8_t *y_src, int stride,
+ uint8_t *p_pixels_in1D) {
+ uint8_t *p_pel = y_src;
+ int index = 0;
+ for (int i = 0; i < 2; i++) {
+ for (int j = 0; j < 2; j++) {
+ p_pixels_in1D[index++] = p_pel[j];
+ }
+ p_pel += stride;
+ }
+}
+
+static int is_block_2x2_row_same_value(uint8_t *p) {
+ if (p[0] != p[1] || p[2] != p[3]) {
+ return 0;
+ }
+
+ return 1;
+}
+
+static int is_block_2x2_col_same_value(uint8_t *p) {
+ if ((p[0] != p[2]) || (p[1] != p[3])) {
+ return 0;
+ }
+
+ return 1;
+}
+
+// the hash value (hash_value1 consists two parts, the first 2 bits relate to
+// the block size and the remaining 16 bits are the crc values. This fuction
+// is used to get the first 2 bits.
+static int hash_block_size_to_index(int block_size) {
+ switch (block_size) {
+ case 8: return 0;
+ case 16: return 1;
+ case 32: return 2;
+ case 64: return 3;
+ default: return -1;
+ }
+}
+
+void av1_hash_table_init(hash_table *p_hash_table) {
+ if (g_crc_initialized == 0) {
+ crc_calculator_init(&crc_calculator1, 24, 0x5D6DCB);
+ crc_calculator_init(&crc_calculator2, 24, 0x864CFB);
+ g_crc_initialized = 1;
+ }
+ p_hash_table->p_lookup_table = NULL;
+}
+
+void av1_hash_table_destroy(hash_table *p_hash_table) {
+ hash_table_clear_all(p_hash_table);
+ aom_free(p_hash_table->p_lookup_table);
+ p_hash_table->p_lookup_table = NULL;
+}
+
+void av1_hash_table_create(hash_table *p_hash_table) {
+ if (p_hash_table->p_lookup_table != NULL) {
+ hash_table_clear_all(p_hash_table);
+ return;
+ }
+ const int max_addr = 1 << (crc_bits + block_size_bits);
+ p_hash_table->p_lookup_table =
+ (Vector **)aom_malloc(sizeof(p_hash_table->p_lookup_table[0]) * max_addr);
+ memset(p_hash_table->p_lookup_table, 0,
+ sizeof(p_hash_table->p_lookup_table[0]) * max_addr);
+}
+
+static void hash_table_add_to_table(hash_table *p_hash_table,
+ uint32_t hash_value,
+ block_hash *curr_block_hash) {
+ if (p_hash_table->p_lookup_table[hash_value] == NULL) {
+ p_hash_table->p_lookup_table[hash_value] =
+ aom_malloc(sizeof(p_hash_table->p_lookup_table[0][0]));
+ vector_setup(p_hash_table->p_lookup_table[hash_value], 10,
+ sizeof(curr_block_hash[0]));
+ vector_push_back(p_hash_table->p_lookup_table[hash_value], curr_block_hash);
+ } else {
+ vector_push_back(p_hash_table->p_lookup_table[hash_value], curr_block_hash);
+ }
+}
+
+int32_t av1_hash_table_count(hash_table *p_hash_table, uint32_t hash_value) {
+ if (p_hash_table->p_lookup_table[hash_value] == NULL) {
+ return 0;
+ } else {
+ return (int32_t)(p_hash_table->p_lookup_table[hash_value]->size);
+ }
+}
+
+Iterator av1_hash_get_first_iterator(hash_table *p_hash_table,
+ uint32_t hash_value) {
+ assert(av1_hash_table_count(p_hash_table, hash_value) > 0);
+ return vector_begin(p_hash_table->p_lookup_table[hash_value]);
+}
+
+int32_t av1_has_exact_match(hash_table *p_hash_table, uint32_t hash_value1,
+ uint32_t hash_value2) {
+ if (p_hash_table->p_lookup_table[hash_value1] == NULL) {
+ return 0;
+ }
+ Iterator iterator = vector_begin(p_hash_table->p_lookup_table[hash_value1]);
+ Iterator last = vector_end(p_hash_table->p_lookup_table[hash_value1]);
+ for (; !iterator_equals(&iterator, &last); iterator_increment(&iterator)) {
+ if ((*(block_hash *)iterator_get(&iterator)).hash_value2 == hash_value2) {
+ return 1;
+ }
+ }
+ return 0;
+}
+
+void av1_generate_block_2x2_hash_value(const YV12_BUFFER_CONFIG *picture,
+ uint32_t *pic_block_hash[2],
+ int8_t *pic_block_same_info[3]) {
+ 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 length = width * 2;
+ 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++) {
+ get_pixels_in_1D_char_array_by_block_2x2(
+ picture->y_buffer + y_pos * picture->y_stride + x_pos,
+ picture->y_stride, p);
+ pic_block_same_info[0][pos] = is_block_2x2_row_same_value(p);
+ pic_block_same_info[1][pos] = is_block_2x2_col_same_value(p);
+
+ pic_block_hash[0][pos] = get_crc_value1(p, length * sizeof(p[0]));
+ pic_block_hash[1][pos] = get_crc_value2(p, length * sizeof(p[0]));
+
+ pos++;
+ }
+ pos += width - 1;
+ }
+}
+
+void 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]) {
+ 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 src_size = block_size >> 1;
+ const int quad_size = block_size >> 2;
+
+ 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++) {
+ p[0] = src_pic_block_hash[0][pos];
+ p[1] = src_pic_block_hash[0][pos + src_size];
+ p[2] = src_pic_block_hash[0][pos + src_size * pic_width];
+ p[3] = src_pic_block_hash[0][pos + src_size * pic_width + src_size];
+ dst_pic_block_hash[0][pos] = get_crc_value1((uint8_t *)p, length);
+
+ p[0] = src_pic_block_hash[1][pos];
+ p[1] = src_pic_block_hash[1][pos + src_size];
+ p[2] = src_pic_block_hash[1][pos + src_size * pic_width];
+ p[3] = src_pic_block_hash[1][pos + src_size * pic_width + src_size];
+ dst_pic_block_hash[1][pos] = get_crc_value2((uint8_t *)p, length);
+
+ dst_pic_block_same_info[0][pos] =
+ src_pic_block_same_info[0][pos] &&
+ src_pic_block_same_info[0][pos + quad_size] &&
+ src_pic_block_same_info[0][pos + src_size] &&
+ src_pic_block_same_info[0][pos + src_size * pic_width] &&
+ src_pic_block_same_info[0][pos + src_size * pic_width + quad_size] &&
+ src_pic_block_same_info[0][pos + src_size * pic_width + src_size];
+
+ dst_pic_block_same_info[1][pos] =
+ src_pic_block_same_info[1][pos] &&
+ src_pic_block_same_info[1][pos + src_size] &&
+ src_pic_block_same_info[1][pos + quad_size * pic_width] &&
+ src_pic_block_same_info[1][pos + quad_size * pic_width + src_size] &&
+ src_pic_block_same_info[1][pos + src_size * pic_width] &&
+ src_pic_block_same_info[1][pos + src_size * pic_width + src_size];
+ pos++;
+ }
+ pos += block_size - 1;
+ }
+
+ if (block_size >= 8) {
+ const int size_minus1 = block_size - 1;
+ pos = 0;
+ for (int y_pos = 0; y_pos < y_end; y_pos++) {
+ for (int x_pos = 0; x_pos < x_end; x_pos++) {
+ dst_pic_block_same_info[2][pos] =
+ (!dst_pic_block_same_info[0][pos] &&
+ !dst_pic_block_same_info[1][pos]) ||
+ (((x_pos & size_minus1) == 0) && ((y_pos & size_minus1) == 0));
+ pos++;
+ }
+ pos += block_size - 1;
+ }
+ }
+}
+
+void 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) {
+ const int x_end = pic_width - block_size + 1;
+ const int y_end = pic_height - block_size + 1;
+
+ const int8_t *src_is_added = pic_is_same;
+ const uint32_t *src_hash[2] = { pic_hash[0], pic_hash[1] };
+
+ int add_value = hash_block_size_to_index(block_size);
+ assert(add_value >= 0);
+ add_value <<= crc_bits;
+ const int crc_mask = (1 << crc_bits) - 1;
+
+ for (int x_pos = 0; x_pos < x_end; x_pos++) {
+ for (int y_pos = 0; y_pos < y_end; y_pos++) {
+ const int pos = y_pos * pic_width + x_pos;
+ // valid data
+ if (src_is_added[pos]) {
+ block_hash curr_block_hash;
+ curr_block_hash.x = x_pos;
+ curr_block_hash.y = y_pos;
+
+ const uint32_t hash_value1 = (src_hash[0][pos] & crc_mask) + add_value;
+ curr_block_hash.hash_value2 = src_hash[1][pos];
+
+ hash_table_add_to_table(p_hash_table, hash_value1, &curr_block_hash);
+ }
+ }
+ }
+}
+
+int av1_hash_is_horizontal_perfect(const YV12_BUFFER_CONFIG *picture,
+ int block_size, int x_start, int y_start) {
+ const int stride = picture->y_stride;
+ const uint8_t *p = picture->y_buffer + y_start * stride + x_start;
+
+ for (int i = 0; i < block_size; i++) {
+ for (int j = 1; j < block_size; j++) {
+ if (p[j] != p[0]) {
+ return 0;
+ }
+ }
+ p += stride;
+ }
+
+ return 1;
+}
+
+int av1_hash_is_vertical_perfect(const YV12_BUFFER_CONFIG *picture,
+ int block_size, int x_start, int y_start) {
+ const int stride = picture->y_stride;
+ const uint8_t *p = picture->y_buffer + y_start * stride + x_start;
+
+ for (int i = 0; i < block_size; i++) {
+ for (int j = 1; j < block_size; j++) {
+ if (p[j * stride + i] != p[i]) {
+ return 0;
+ }
+ }
+ }
+
+ return 1;
+}
+
+// global buffer for hash value calculation of a block
+// used only in av1_get_block_hash_value()
+static uint32_t hash_value_buffer[2][2][1024]; // [first hash/second hash]
+ // [two buffers used ping-pong]
+ // [num of 2x2 blocks in 64x64]
+
+void av1_get_block_hash_value(uint8_t *y_src, int stride, int block_size,
+ uint32_t *hash_value1, uint32_t *hash_value2) {
+ uint8_t pixel_to_hash[4];
+ uint32_t to_hash[4];
+ const int add_value = hash_block_size_to_index(block_size) << crc_bits;
+ assert(add_value >= 0);
+ const int crc_mask = (1 << crc_bits) - 1;
+
+ // 2x2 subblock hash values in current CU
+ int sub_block_in_width = (block_size >> 1);
+ for (int y_pos = 0; y_pos < block_size; y_pos += 2) {
+ for (int x_pos = 0; x_pos < block_size; x_pos += 2) {
+ int pos = (y_pos >> 1) * sub_block_in_width + (x_pos >> 1);
+ get_pixels_in_1D_char_array_by_block_2x2(y_src + y_pos * stride + x_pos,
+ stride, pixel_to_hash);
+
+ hash_value_buffer[0][0][pos] =
+ get_crc_value1(pixel_to_hash, sizeof(pixel_to_hash));
+ hash_value_buffer[1][0][pos] =
+ get_crc_value2(pixel_to_hash, sizeof(pixel_to_hash));
+ }
+ }
+
+ int src_sub_block_in_width = sub_block_in_width;
+ sub_block_in_width >>= 1;
+
+ int src_idx = 1;
+ int dst_idx = 0;
+
+ // 4x4 subblock hash values to current block hash values
+ for (int sub_width = 4; sub_width <= block_size; sub_width *= 2) {
+ src_idx = 1 - src_idx;
+ dst_idx = 1 - dst_idx;
+
+ int dst_pos = 0;
+ for (int y_pos = 0; y_pos < sub_block_in_width; y_pos++) {
+ for (int x_pos = 0; x_pos < sub_block_in_width; x_pos++) {
+ int srcPos = (y_pos << 1) * src_sub_block_in_width + (x_pos << 1);
+
+ to_hash[0] = hash_value_buffer[0][src_idx][srcPos];
+ to_hash[1] = hash_value_buffer[0][src_idx][srcPos + 1];
+ to_hash[2] =
+ hash_value_buffer[0][src_idx][srcPos + src_sub_block_in_width];
+ to_hash[3] =
+ hash_value_buffer[0][src_idx][srcPos + src_sub_block_in_width + 1];
+
+ hash_value_buffer[0][dst_idx][dst_pos] =
+ get_crc_value1((uint8_t *)to_hash, sizeof(to_hash));
+
+ to_hash[0] = hash_value_buffer[1][src_idx][srcPos];
+ to_hash[1] = hash_value_buffer[1][src_idx][srcPos + 1];
+ to_hash[2] =
+ hash_value_buffer[1][src_idx][srcPos + src_sub_block_in_width];
+ to_hash[3] =
+ hash_value_buffer[1][src_idx][srcPos + src_sub_block_in_width + 1];
+ hash_value_buffer[1][dst_idx][dst_pos] =
+ get_crc_value2((uint8_t *)to_hash, sizeof(to_hash));
+ dst_pos++;
+ }
+ }
+
+ src_sub_block_in_width = sub_block_in_width;
+ sub_block_in_width >>= 1;
+ }
+
+ *hash_value1 = (hash_value_buffer[0][dst_idx][0] & crc_mask) + add_value;
+ *hash_value2 = hash_value_buffer[1][dst_idx][0];
+}
diff --git a/av1/encoder/hash_motion.h b/av1/encoder/hash_motion.h
new file mode 100644
index 0000000..26e1ac4
--- /dev/null
+++ b/av1/encoder/hash_motion.h
@@ -0,0 +1,72 @@
+/*
+ * Copyright (c) 2016, Alliance for Open Media. All rights reserved
+ *
+ * This source code is subject to the terms of the BSD 2 Clause License and
+ * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
+ * was not distributed with this source code in the LICENSE file, you can
+ * obtain it at www.aomedia.org/license/software. If the Alliance for Open
+ * Media Patent License 1.0 was not distributed with this source code in the
+ * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
+ */
+
+#ifndef AV1_ENCODER_HASH_MOTION_H_
+#define AV1_ENCODER_HASH_MOTION_H_
+
+#include "./aom_config.h"
+#include "aom/aom_integer.h"
+#include "aom_scale/yv12config.h"
+#include "third_party/vector/vector.h"
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+// store a block's hash info.
+// x and y are the position from the top left of the picture
+// hash_value2 is used to store the second hash value
+typedef struct _block_hash {
+ int16_t x;
+ int16_t y;
+ uint32_t hash_value2;
+} block_hash;
+
+typedef struct _hash_table { Vector **p_lookup_table; } hash_table;
+
+void av1_hash_table_init(hash_table *p_hash_table);
+void av1_hash_table_destroy(hash_table *p_hash_table);
+void av1_hash_table_create(hash_table *p_hash_table);
+int32_t av1_hash_table_count(hash_table *p_hash_table, uint32_t hash_value);
+Iterator av1_hash_get_first_iterator(hash_table *p_hash_table,
+ uint32_t hash_value);
+int32_t av1_has_exact_match(hash_table *p_hash_table, uint32_t hash_value1,
+ uint32_t hash_value2);
+void av1_generate_block_2x2_hash_value(const YV12_BUFFER_CONFIG *picture,
+ uint32_t *pic_block_hash[2],
+ int8_t *pic_block_same_info[3]);
+void 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]);
+void 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);
+
+// 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
+int av1_hash_is_horizontal_perfect(const YV12_BUFFER_CONFIG *picture,
+ int block_size, int x_start, int y_start);
+// 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 columns
+int av1_hash_is_vertical_perfect(const YV12_BUFFER_CONFIG *picture,
+ int block_size, int x_start, int y_start);
+void av1_get_block_hash_value(uint8_t *y_src, int stride, int block_size,
+ uint32_t *hash_value1, uint32_t *hash_value2);
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // AV1_ENCODER_HASH_MOTION_H_
diff --git a/av1/encoder/mcomp.c b/av1/encoder/mcomp.c
index 4efadff..02ac6ef 100644
--- a/av1/encoder/mcomp.c
+++ b/av1/encoder/mcomp.c
@@ -2562,10 +2562,45 @@
(*x->ex_search_count_ptr <= max_ex) && !cpi->rc.is_src_frame_alt_ref;
}
+#if CONFIG_HASH_ME
+#define MAX_HASH_MV_TABLE_SIZE 5
+static void add_to_sort_table(block_hash block_hashes[MAX_HASH_MV_TABLE_SIZE],
+ int costs[MAX_HASH_MV_TABLE_SIZE], int *existing,
+ int max_size, block_hash curr_block,
+ int curr_cost) {
+ if (*existing < max_size) {
+ block_hashes[*existing] = curr_block;
+ costs[*existing] = curr_cost;
+ (*existing)++;
+ } else {
+ int max_cost = 0;
+ int max_cost_idx = 0;
+ for (int i = 0; i < max_size; i++) {
+ if (costs[i] > max_cost) {
+ max_cost = costs[i];
+ max_cost_idx = i;
+ }
+ }
+
+ if (curr_cost < max_cost) {
+ block_hashes[max_cost_idx] = curr_block;
+ costs[max_cost_idx] = curr_cost;
+ }
+ }
+}
+#endif
+
+#if CONFIG_HASH_ME
+int av1_full_pixel_search(const AV1_COMP *cpi, MACROBLOCK *x, BLOCK_SIZE bsize,
+ MV *mvp_full, int step_param, int error_per_bit,
+ int *cost_list, const MV *ref_mv, int var_max, int rd,
+ int x_pos, int y_pos) {
+#else
int av1_full_pixel_search(const AV1_COMP *cpi, MACROBLOCK *x, BLOCK_SIZE bsize,
MV *mvp_full, int step_param, int error_per_bit,
int *cost_list, const MV *ref_mv, int var_max,
int rd) {
+#endif
const SPEED_FEATURES *const sf = &cpi->sf;
const SEARCH_METHODS method = sf->mv.search_method;
const aom_variance_fn_ptr_t *fn_ptr = &cpi->fn_ptr[bsize];
@@ -2637,6 +2672,80 @@
if (method != NSTEP && rd && var < var_max)
var = av1_get_mvpred_var(x, &x->best_mv.as_mv, ref_mv, fn_ptr, 1);
+#if CONFIG_HASH_ME
+ do {
+ if (!cpi->common.allow_screen_content_tools) {
+ break;
+ }
+ // already single ME
+ // get block size and original buffer of current block
+ const int block_height = block_size_high[bsize];
+ const int block_width = block_size_wide[bsize];
+ if (block_height == block_width && x_pos >= 0 && y_pos >= 0) {
+ if (block_width == 8 || block_width == 16 || block_width == 32 ||
+ block_width == 64) {
+ uint8_t *what = x->plane[0].src.buf;
+ const int what_stride = x->plane[0].src.stride;
+ block_hash block_hashes[MAX_HASH_MV_TABLE_SIZE];
+ int costs[MAX_HASH_MV_TABLE_SIZE];
+ int existing = 0;
+ int i;
+ uint32_t hash_value1, hash_value2;
+ MV best_hash_mv;
+ int best_hash_cost = INT_MAX;
+
+ // for the hashMap
+ hash_table *ref_frame_hash =
+ get_ref_frame_hash_map(cpi, x->e_mbd.mi[0]->mbmi.ref_frame[0]);
+
+ av1_get_block_hash_value(what, what_stride, block_width, &hash_value1,
+ &hash_value2);
+
+ const int count = av1_hash_table_count(ref_frame_hash, hash_value1);
+ if (count == 0) {
+ break;
+ }
+
+ Iterator iterator =
+ av1_hash_get_first_iterator(ref_frame_hash, hash_value1);
+ for (i = 0; i < count; i++, iterator_increment(&iterator)) {
+ block_hash ref_block_hash = *(block_hash *)(iterator_get(&iterator));
+ if (hash_value2 == ref_block_hash.hash_value2) {
+ int refCost =
+ abs(ref_block_hash.x - x_pos) + abs(ref_block_hash.y - y_pos);
+ add_to_sort_table(block_hashes, costs, &existing,
+ MAX_HASH_MV_TABLE_SIZE, ref_block_hash, refCost);
+ }
+ }
+
+ if (existing == 0) {
+ break;
+ }
+
+ for (i = 0; i < existing; i++) {
+ MV hash_mv;
+ hash_mv.col = block_hashes[i].x - x_pos;
+ hash_mv.row = block_hashes[i].y - y_pos;
+ if (!is_mv_in(&x->mv_limits, &hash_mv)) {
+ continue;
+ }
+ int currHashCost = av1_get_mvpred_var(x, &hash_mv, ref_mv, fn_ptr, 1);
+ if (currHashCost < best_hash_cost) {
+ best_hash_cost = currHashCost;
+ best_hash_mv = hash_mv;
+ }
+ }
+
+ if (best_hash_cost < var) {
+ x->second_best_mv = x->best_mv;
+ x->best_mv.as_mv = best_hash_mv;
+ var = best_hash_cost;
+ }
+ }
+ }
+ } while (0);
+#endif
+
return var;
}
diff --git a/av1/encoder/mcomp.h b/av1/encoder/mcomp.h
index 733e415..8de2957 100644
--- a/av1/encoder/mcomp.h
+++ b/av1/encoder/mcomp.h
@@ -131,10 +131,17 @@
struct AV1_COMP;
+#if CONFIG_HASH_ME
+int av1_full_pixel_search(const struct AV1_COMP *cpi, MACROBLOCK *x,
+ BLOCK_SIZE bsize, MV *mvp_full, int step_param,
+ int error_per_bit, int *cost_list, const MV *ref_mv,
+ int var_max, int rd, int x_pos, int y_pos);
+#else
int av1_full_pixel_search(const struct AV1_COMP *cpi, MACROBLOCK *x,
BLOCK_SIZE bsize, MV *mvp_full, int step_param,
int error_per_bit, int *cost_list, const MV *ref_mv,
int var_max, int rd);
+#endif
#if CONFIG_MOTION_VAR
int av1_obmc_full_pixel_diamond(const struct AV1_COMP *cpi, MACROBLOCK *x,
diff --git a/av1/encoder/rdopt.c b/av1/encoder/rdopt.c
index ad2b8e5..c961884 100644
--- a/av1/encoder/rdopt.c
+++ b/av1/encoder/rdopt.c
@@ -7173,9 +7173,16 @@
switch (mbmi->motion_mode) {
case SIMPLE_TRANSLATION:
#endif // CONFIG_MOTION_VAR
+#if CONFIG_HASH_ME
bestsme = av1_full_pixel_search(cpi, x, bsize, &mvp_full, step_param,
sadpb, cond_cost_list(cpi, cost_list),
- &ref_mv, INT_MAX, 1);
+ &ref_mv, INT_MAX, 1, (MI_SIZE * mi_col),
+ (MI_SIZE * mi_row));
+#else
+ bestsme = av1_full_pixel_search(cpi, x, bsize, &mvp_full, step_param, sadpb,
+ cond_cost_list(cpi, cost_list), &ref_mv,
+ INT_MAX, 1);
+#endif
#if CONFIG_MOTION_VAR
break;
case OBMC_CAUSAL:
@@ -9793,9 +9800,15 @@
mvp_full.row >>= 3;
int sadpb = x->sadperbit16;
int cost_list[5];
+#if CONFIG_HASH_ME
+ int bestsme = av1_full_pixel_search(cpi, x, bsize, &mvp_full, step_param,
+ sadpb, cond_cost_list(cpi, cost_list),
+ &dv_ref.as_mv, INT_MAX, 1, -1, -1);
+#else
int bestsme = av1_full_pixel_search(cpi, x, bsize, &mvp_full, step_param,
sadpb, cond_cost_list(cpi, cost_list),
&dv_ref.as_mv, INT_MAX, 1);
+#endif
x->mv_limits = tmp_mv_limits;
if (bestsme == INT_MAX) continue;
diff --git a/configure b/configure
index ee51cba..0950048 100755
--- a/configure
+++ b/configure
@@ -340,6 +340,7 @@
uv_lvl
no_frame_context_signaling
txmg
+ hash_me
"
CONFIG_LIST="
dependency_tracking
diff --git a/third_party/vector/vector.c b/third_party/vector/vector.c
new file mode 100644
index 0000000..2f0a38e
--- /dev/null
+++ b/third_party/vector/vector.c
@@ -0,0 +1,543 @@
+/*
+The MIT License(MIT)
+Copyright(c) 2016 Peter Goldsborough
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of
+this software and associated documentation files(the "Software"), to deal in
+the Software without restriction, including without limitation the rights to
+use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
+the Software, and to permit persons to whom the Software is furnished to do so,
+subject to the following conditions :
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
+FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE AUTHORS OR
+COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
+IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+*/
+
+#define __STDC_WANT_LIB_EXT1__ 1
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "third_party/vector/vector.h"
+
+int vector_setup(Vector *vector, size_t capacity, size_t element_size) {
+ assert(vector != NULL);
+
+ if (vector == NULL) return VECTOR_ERROR;
+
+ vector->size = 0;
+ vector->capacity = MAX(VECTOR_MINIMUM_CAPACITY, capacity);
+ vector->element_size = element_size;
+ vector->data = malloc(vector->capacity * element_size);
+
+ return vector->data == NULL ? VECTOR_ERROR : VECTOR_SUCCESS;
+}
+
+int vector_copy(Vector *destination, Vector *source) {
+ assert(destination != NULL);
+ assert(source != NULL);
+ assert(vector_is_initialized(source));
+ assert(!vector_is_initialized(destination));
+
+ if (destination == NULL) return VECTOR_ERROR;
+ if (source == NULL) return VECTOR_ERROR;
+ if (vector_is_initialized(destination)) return VECTOR_ERROR;
+ if (!vector_is_initialized(source)) return VECTOR_ERROR;
+
+ /* Copy ALL the data */
+ destination->size = source->size;
+ destination->capacity = source->size * 2;
+ destination->element_size = source->element_size;
+
+ /* Note that we are not necessarily allocating the same capacity */
+ destination->data = malloc(destination->capacity * source->element_size);
+ if (destination->data == NULL) return VECTOR_ERROR;
+
+ memcpy(destination->data, source->data, vector_byte_size(source));
+
+ return VECTOR_SUCCESS;
+}
+
+int vector_copy_assign(Vector *destination, Vector *source) {
+ assert(destination != NULL);
+ assert(source != NULL);
+ assert(vector_is_initialized(source));
+ assert(vector_is_initialized(destination));
+
+ if (destination == NULL) return VECTOR_ERROR;
+ if (source == NULL) return VECTOR_ERROR;
+ if (!vector_is_initialized(destination)) return VECTOR_ERROR;
+ if (!vector_is_initialized(source)) return VECTOR_ERROR;
+
+ vector_destroy(destination);
+
+ return vector_copy(destination, source);
+}
+
+int vector_move(Vector *destination, Vector *source) {
+ assert(destination != NULL);
+ assert(source != NULL);
+
+ if (destination == NULL) return VECTOR_ERROR;
+ if (source == NULL) return VECTOR_ERROR;
+
+ *destination = *source;
+ source->data = NULL;
+
+ return VECTOR_SUCCESS;
+}
+
+int vector_move_assign(Vector *destination, Vector *source) {
+ vector_swap(destination, source);
+ return vector_destroy(source);
+}
+
+int vector_swap(Vector *destination, Vector *source) {
+ void *temp;
+
+ assert(destination != NULL);
+ assert(source != NULL);
+ assert(vector_is_initialized(source));
+ assert(vector_is_initialized(destination));
+
+ if (destination == NULL) return VECTOR_ERROR;
+ if (source == NULL) return VECTOR_ERROR;
+ if (!vector_is_initialized(destination)) return VECTOR_ERROR;
+ if (!vector_is_initialized(source)) return VECTOR_ERROR;
+
+ _vector_swap(&destination->size, &source->size);
+ _vector_swap(&destination->capacity, &source->capacity);
+ _vector_swap(&destination->element_size, &source->element_size);
+
+ temp = destination->data;
+ destination->data = source->data;
+ source->data = temp;
+
+ return VECTOR_SUCCESS;
+}
+
+int vector_destroy(Vector *vector) {
+ assert(vector != NULL);
+
+ if (vector == NULL) return VECTOR_ERROR;
+
+ free(vector->data);
+ vector->data = NULL;
+
+ return VECTOR_SUCCESS;
+}
+
+/* Insertion */
+int vector_push_back(Vector *vector, void *element) {
+ assert(vector != NULL);
+ assert(element != NULL);
+
+ if (_vector_should_grow(vector)) {
+ if (_vector_adjust_capacity(vector) == VECTOR_ERROR) {
+ return VECTOR_ERROR;
+ }
+ }
+
+ _vector_assign(vector, vector->size, element);
+
+ ++vector->size;
+
+ return VECTOR_SUCCESS;
+}
+
+int vector_push_front(Vector *vector, void *element) {
+ return vector_insert(vector, 0, element);
+}
+
+int vector_insert(Vector *vector, size_t index, void *element) {
+ void *offset;
+
+ assert(vector != NULL);
+ assert(element != NULL);
+ assert(index <= vector->size);
+
+ if (vector == NULL) return VECTOR_ERROR;
+ if (element == NULL) return VECTOR_ERROR;
+ if (vector->element_size == 0) return VECTOR_ERROR;
+ if (index > vector->size) return VECTOR_ERROR;
+
+ if (_vector_should_grow(vector)) {
+ if (_vector_adjust_capacity(vector) == VECTOR_ERROR) {
+ return VECTOR_ERROR;
+ }
+ }
+
+ /* Move other elements to the right */
+ if (_vector_move_right(vector, index) == VECTOR_ERROR) {
+ return VECTOR_ERROR;
+ }
+
+ /* Insert the element */
+ offset = _vector_offset(vector, index);
+ memcpy(offset, element, vector->element_size);
+ ++vector->size;
+
+ return VECTOR_SUCCESS;
+}
+
+int vector_assign(Vector *vector, size_t index, void *element) {
+ assert(vector != NULL);
+ assert(element != NULL);
+ assert(index < vector->size);
+
+ if (vector == NULL) return VECTOR_ERROR;
+ if (element == NULL) return VECTOR_ERROR;
+ if (vector->element_size == 0) return VECTOR_ERROR;
+ if (index >= vector->size) return VECTOR_ERROR;
+
+ _vector_assign(vector, index, element);
+
+ return VECTOR_SUCCESS;
+}
+
+/* Deletion */
+int vector_pop_back(Vector *vector) {
+ assert(vector != NULL);
+ assert(vector->size > 0);
+
+ if (vector == NULL) return VECTOR_ERROR;
+ if (vector->element_size == 0) return VECTOR_ERROR;
+
+ --vector->size;
+
+#ifndef VECTOR_NO_SHRINK
+ if (_vector_should_shrink(vector)) {
+ _vector_adjust_capacity(vector);
+ }
+#endif
+
+ return VECTOR_SUCCESS;
+}
+
+int vector_pop_front(Vector *vector) { return vector_erase(vector, 0); }
+
+int vector_erase(Vector *vector, size_t index) {
+ assert(vector != NULL);
+ assert(index < vector->size);
+
+ if (vector == NULL) return VECTOR_ERROR;
+ if (vector->element_size == 0) return VECTOR_ERROR;
+ if (index >= vector->size) return VECTOR_ERROR;
+
+ /* Just overwrite */
+ _vector_move_left(vector, index);
+
+#ifndef VECTOR_NO_SHRINK
+ if (--vector->size == vector->capacity / 4) {
+ _vector_adjust_capacity(vector);
+ }
+#endif
+
+ return VECTOR_SUCCESS;
+}
+
+int vector_clear(Vector *vector) { return vector_resize(vector, 0); }
+
+/* Lookup */
+void *vector_get(Vector *vector, size_t index) {
+ assert(vector != NULL);
+ assert(index < vector->size);
+
+ if (vector == NULL) return NULL;
+ if (vector->element_size == 0) return NULL;
+ if (index >= vector->size) return NULL;
+
+ return _vector_offset(vector, index);
+}
+
+const void *vector_const_get(const Vector *vector, size_t index) {
+ assert(vector != NULL);
+ assert(index < vector->size);
+
+ if (vector == NULL) return NULL;
+ if (vector->element_size == 0) return NULL;
+ if (index >= vector->size) return NULL;
+
+ return _vector_const_offset(vector, index);
+}
+
+void *vector_front(Vector *vector) { return vector_get(vector, 0); }
+
+void *vector_back(Vector *vector) {
+ return vector_get(vector, vector->size - 1);
+}
+
+/* Information */
+
+bool vector_is_initialized(const Vector *vector) {
+ return vector->data != NULL;
+}
+
+size_t vector_byte_size(const Vector *vector) {
+ return vector->size * vector->element_size;
+}
+
+size_t vector_free_space(const Vector *vector) {
+ return vector->capacity - vector->size;
+}
+
+bool vector_is_empty(const Vector *vector) { return vector->size == 0; }
+
+/* Memory management */
+int vector_resize(Vector *vector, size_t new_size) {
+ if (new_size <= vector->capacity * VECTOR_SHRINK_THRESHOLD) {
+ vector->size = new_size;
+ if (_vector_reallocate(vector, new_size * VECTOR_GROWTH_FACTOR) == -1) {
+ return VECTOR_ERROR;
+ }
+ } else if (new_size > vector->capacity) {
+ if (_vector_reallocate(vector, new_size * VECTOR_GROWTH_FACTOR) == -1) {
+ return VECTOR_ERROR;
+ }
+ }
+
+ vector->size = new_size;
+
+ return VECTOR_SUCCESS;
+}
+
+int vector_reserve(Vector *vector, size_t minimum_capacity) {
+ if (minimum_capacity > vector->capacity) {
+ if (_vector_reallocate(vector, minimum_capacity) == VECTOR_ERROR) {
+ return VECTOR_ERROR;
+ }
+ }
+
+ return VECTOR_SUCCESS;
+}
+
+int vector_shrink_to_fit(Vector *vector) {
+ return _vector_reallocate(vector, vector->size);
+}
+
+/* Iterators */
+Iterator vector_begin(Vector *vector) { return vector_iterator(vector, 0); }
+
+Iterator vector_end(Vector *vector) {
+ return vector_iterator(vector, vector->size);
+}
+
+Iterator vector_iterator(Vector *vector, size_t index) {
+ Iterator iterator = { NULL, 0 };
+
+ assert(vector != NULL);
+ assert(index <= vector->size);
+
+ if (vector == NULL) return iterator;
+ if (index > vector->size) return iterator;
+ if (vector->element_size == 0) return iterator;
+
+ iterator.pointer = _vector_offset(vector, index);
+ iterator.element_size = vector->element_size;
+
+ return iterator;
+}
+
+void *iterator_get(Iterator *iterator) { return iterator->pointer; }
+
+int iterator_erase(Vector *vector, Iterator *iterator) {
+ size_t index = iterator_index(vector, iterator);
+
+ if (vector_erase(vector, index) == VECTOR_ERROR) {
+ return VECTOR_ERROR;
+ }
+
+ *iterator = vector_iterator(vector, index);
+
+ return VECTOR_SUCCESS;
+}
+
+void iterator_increment(Iterator *iterator) {
+ assert(iterator != NULL);
+ // iterator->pointer += iterator->element_size;
+ iterator->pointer =
+ (unsigned char *)iterator->pointer + iterator->element_size;
+}
+
+void iterator_decrement(Iterator *iterator) {
+ assert(iterator != NULL);
+ // iterator->pointer -= iterator->element_size;
+ iterator->pointer =
+ (unsigned char *)iterator->pointer - iterator->element_size;
+}
+
+void *iterator_next(Iterator *iterator) {
+ void *current = iterator->pointer;
+ iterator_increment(iterator);
+
+ return current;
+}
+
+void *iterator_previous(Iterator *iterator) {
+ void *current = iterator->pointer;
+ iterator_decrement(iterator);
+
+ return current;
+}
+
+bool iterator_equals(Iterator *first, Iterator *second) {
+ assert(first->element_size == second->element_size);
+ return first->pointer == second->pointer;
+}
+
+bool iterator_is_before(Iterator *first, Iterator *second) {
+ assert(first->element_size == second->element_size);
+ return first->pointer < second->pointer;
+}
+
+bool iterator_is_after(Iterator *first, Iterator *second) {
+ assert(first->element_size == second->element_size);
+ return first->pointer > second->pointer;
+}
+
+size_t iterator_index(Vector *vector, Iterator *iterator) {
+ assert(vector != NULL);
+ assert(iterator != NULL);
+ // return (iterator->pointer - vector->data) / vector->element_size;
+ return ((unsigned char *)iterator->pointer - (unsigned char *)vector->data) /
+ vector->element_size;
+}
+
+/***** PRIVATE *****/
+
+bool _vector_should_grow(Vector *vector) {
+ assert(vector->size <= vector->capacity);
+ return vector->size == vector->capacity;
+}
+
+bool _vector_should_shrink(Vector *vector) {
+ assert(vector->size <= vector->capacity);
+ return vector->size == vector->capacity * VECTOR_SHRINK_THRESHOLD;
+}
+
+size_t _vector_free_bytes(const Vector *vector) {
+ return vector_free_space(vector) * vector->element_size;
+}
+
+void *_vector_offset(Vector *vector, size_t index) {
+ // return vector->data + (index * vector->element_size);
+ return (unsigned char *)vector->data + (index * vector->element_size);
+}
+
+const void *_vector_const_offset(const Vector *vector, size_t index) {
+ // return vector->data + (index * vector->element_size);
+ return (unsigned char *)vector->data + (index * vector->element_size);
+}
+
+void _vector_assign(Vector *vector, size_t index, void *element) {
+ /* Insert the element */
+ void *offset = _vector_offset(vector, index);
+ memcpy(offset, element, vector->element_size);
+}
+
+int _vector_move_right(Vector *vector, size_t index) {
+ assert(vector->size < vector->capacity);
+
+ /* The location where to start to move from. */
+ void *offset = _vector_offset(vector, index);
+
+ /* How many to move to the right. */
+ size_t elements_in_bytes = (vector->size - index) * vector->element_size;
+
+#ifdef __STDC_LIB_EXT1__
+ size_t right_capacity_in_bytes =
+ (vector->capacity - (index + 1)) * vector->element_size;
+
+ /* clang-format off */
+ int return_code = memmove_s(
+ offset + vector->element_size,
+ right_capacity_in_bytes,
+ offset,
+ elements_in_bytes);
+
+ /* clang-format on */
+
+ return return_code == 0 ? VECTOR_SUCCESS : VECTOR_ERROR;
+
+#else
+ // memmove(offset + vector->element_size, offset, elements_in_bytes);
+ memmove((unsigned char *)offset + vector->element_size, offset,
+ elements_in_bytes);
+ return VECTOR_SUCCESS;
+#endif
+}
+
+void _vector_move_left(Vector *vector, size_t index) {
+ size_t right_elements_in_bytes;
+ void *offset;
+
+ /* The offset into the memory */
+ offset = _vector_offset(vector, index);
+
+ /* How many to move to the left */
+ right_elements_in_bytes = (vector->size - index - 1) * vector->element_size;
+
+ // memmove(offset, offset + vector->element_size, right_elements_in_bytes);
+ memmove(offset, (unsigned char *)offset + vector->element_size,
+ right_elements_in_bytes);
+}
+
+int _vector_adjust_capacity(Vector *vector) {
+ return _vector_reallocate(vector,
+ MAX(1, vector->size * VECTOR_GROWTH_FACTOR));
+}
+
+int _vector_reallocate(Vector *vector, size_t new_capacity) {
+ size_t new_capacity_in_bytes;
+ void *old;
+ assert(vector != NULL);
+
+ if (new_capacity < VECTOR_MINIMUM_CAPACITY) {
+ if (vector->capacity > VECTOR_MINIMUM_CAPACITY) {
+ new_capacity = VECTOR_MINIMUM_CAPACITY;
+ } else {
+ /* NO-OP */
+ return VECTOR_SUCCESS;
+ }
+ }
+
+ new_capacity_in_bytes = new_capacity * vector->element_size;
+ old = vector->data;
+
+ if ((vector->data = malloc(new_capacity_in_bytes)) == NULL) {
+ return VECTOR_ERROR;
+ }
+
+#ifdef __STDC_LIB_EXT1__
+ /* clang-format off */
+ if (memcpy_s(vector->data,
+ new_capacity_in_bytes,
+ old,
+ vector_byte_size(vector)) != 0) {
+ return VECTOR_ERROR;
+ }
+/* clang-format on */
+#else
+ memcpy(vector->data, old, vector_byte_size(vector));
+#endif
+
+ vector->capacity = new_capacity;
+
+ free(old);
+
+ return VECTOR_SUCCESS;
+}
+
+void _vector_swap(size_t *first, size_t *second) {
+ size_t temp = *first;
+ *first = *second;
+ *second = temp;
+}
diff --git a/third_party/vector/vector.h b/third_party/vector/vector.h
new file mode 100644
index 0000000..2bf1a9a
--- /dev/null
+++ b/third_party/vector/vector.h
@@ -0,0 +1,159 @@
+/*
+The MIT License(MIT)
+Copyright(c) 2016 Peter Goldsborough
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of
+this software and associated documentation files(the "Software"), to deal in
+the Software without restriction, including without limitation the rights to
+use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
+the Software, and to permit persons to whom the Software is furnished to do so,
+subject to the following conditions :
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
+FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE AUTHORS OR
+COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
+IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+*/
+
+#ifndef VECTOR_H
+#define VECTOR_H
+
+#include <stdbool.h>
+#include <stddef.h>
+
+/***** DEFINITIONS *****/
+
+#define VECTOR_MINIMUM_CAPACITY 2
+#define VECTOR_GROWTH_FACTOR 2
+#define VECTOR_SHRINK_THRESHOLD (1 / 4)
+
+#define VECTOR_ERROR -1
+#define VECTOR_SUCCESS 0
+
+#define VECTOR_UNINITIALIZED NULL
+#define VECTOR_INITIALIZER \
+ { 0, 0, 0, VECTOR_UNINITIALIZED }
+
+/***** STRUCTURES *****/
+
+typedef struct Vector {
+ size_t size;
+ size_t capacity;
+ size_t element_size;
+
+ void *data;
+} Vector;
+
+typedef struct Iterator {
+ void *pointer;
+ size_t element_size;
+} Iterator;
+
+/***** METHODS *****/
+
+/* Constructor */
+int vector_setup(Vector *vector, size_t capacity, size_t element_size);
+
+/* Copy Constructor */
+int vector_copy(Vector *destination, Vector *source);
+
+/* Copy Assignment */
+int vector_copy_assign(Vector *destination, Vector *source);
+
+/* Move Constructor */
+int vector_move(Vector *destination, Vector *source);
+
+/* Move Assignment */
+int vector_move_assign(Vector *destination, Vector *source);
+
+int vector_swap(Vector *destination, Vector *source);
+
+/* Destructor */
+int vector_destroy(Vector *vector);
+
+/* Insertion */
+int vector_push_back(Vector *vector, void *element);
+int vector_push_front(Vector *vector, void *element);
+int vector_insert(Vector *vector, size_t index, void *element);
+int vector_assign(Vector *vector, size_t index, void *element);
+
+/* Deletion */
+int vector_pop_back(Vector *vector);
+int vector_pop_front(Vector *vector);
+int vector_erase(Vector *vector, size_t index);
+int vector_clear(Vector *vector);
+
+/* Lookup */
+void *vector_get(Vector *vector, size_t index);
+const void *vector_const_get(const Vector *vector, size_t index);
+void *vector_front(Vector *vector);
+void *vector_back(Vector *vector);
+#define VECTOR_GET_AS(type, vector_pointer, index) \
+ *((type *)vector_get((vector_pointer), (index)))
+
+/* Information */
+bool vector_is_initialized(const Vector *vector);
+size_t vector_byte_size(const Vector *vector);
+size_t vector_free_space(const Vector *vector);
+bool vector_is_empty(const Vector *vector);
+
+/* Memory management */
+int vector_resize(Vector *vector, size_t new_size);
+int vector_reserve(Vector *vector, size_t minimum_capacity);
+int vector_shrink_to_fit(Vector *vector);
+
+/* Iterators */
+Iterator vector_begin(Vector *vector);
+Iterator vector_end(Vector *vector);
+Iterator vector_iterator(Vector *vector, size_t index);
+
+void *iterator_get(Iterator *iterator);
+#define ITERATOR_GET_AS(type, iterator) *((type *)iterator_get((iterator)))
+
+int iterator_erase(Vector *vector, Iterator *iterator);
+
+void iterator_increment(Iterator *iterator);
+void iterator_decrement(Iterator *iterator);
+
+void *iterator_next(Iterator *iterator);
+void *iterator_previous(Iterator *iterator);
+
+bool iterator_equals(Iterator *first, Iterator *second);
+bool iterator_is_before(Iterator *first, Iterator *second);
+bool iterator_is_after(Iterator *first, Iterator *second);
+
+size_t iterator_index(Vector *vector, Iterator *iterator);
+
+#define VECTOR_FOR_EACH(vector_pointer, iterator_name) \
+ for (Iterator(iterator_name) = vector_begin((vector_pointer)), \
+ end = vector_end((vector_pointer)); \
+ !iterator_equals(&(iterator_name), &end); \
+ iterator_increment(&(iterator_name)))
+
+/***** PRIVATE *****/
+
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+
+bool _vector_should_grow(Vector *vector);
+bool _vector_should_shrink(Vector *vector);
+
+size_t _vector_free_bytes(const Vector *vector);
+void *_vector_offset(Vector *vector, size_t index);
+const void *_vector_const_offset(const Vector *vector, size_t index);
+
+void _vector_assign(Vector *vector, size_t index, void *element);
+
+int _vector_move_right(Vector *vector, size_t index);
+void _vector_move_left(Vector *vector, size_t index);
+
+int _vector_adjust_capacity(Vector *vector);
+int _vector_reallocate(Vector *vector, size_t new_capacity);
+
+void _vector_swap(size_t *first, size_t *second);
+
+#endif /* VECTOR_H */
