Implement c version crc32c(except hash-motion) Rename av1_get_crc_value_sse4_2 to av1_get_crc32c_value_sse4_2 The original av1_get_crc_value is kept for hash-motion, other place use the new one. Implement av1_get_crc32c_value_c for crc32c(poly=0x1EDC6F41), which will generate identical results as av1_get_crc32c_value_sse4_2. crc32c should have less hash collision cases. And This will help remove the mismatch between C and SIMD. Change-Id: I7600729d213e9accf9e58308bc70e92c3f373392
diff --git a/av1/common/av1_rtcd_defs.pl b/av1/common/av1_rtcd_defs.pl index 846a57a..344e071 100755 --- a/av1/common/av1_rtcd_defs.pl +++ b/av1/common/av1_rtcd_defs.pl
@@ -250,8 +250,8 @@ specialize qw/av1_wedge_compute_delta_squares sse2/; # hash - add_proto qw/uint32_t av1_get_crc_value/, "void *crc_calculator, uint8_t *p, int length"; - specialize qw/av1_get_crc_value sse4_2/; + add_proto qw/uint32_t av1_get_crc32c_value/, "void *crc_calculator, uint8_t *p, int length"; + specialize qw/av1_get_crc32c_value sse4_2/; } # end encoder functions
diff --git a/av1/encoder/block.h b/av1/encoder/block.h index 8298ecd..9ae6366 100644 --- a/av1/encoder/block.h +++ b/av1/encoder/block.h
@@ -112,7 +112,7 @@ MB_RD_INFO tx_rd_info[RD_RECORD_BUFFER_LEN]; // Circular buffer. int index_start; int num; - CRC_CALCULATOR crc_calculator; // Hash function. + CRC32C crc_calculator; // Hash function. } MB_RD_RECORD; typedef struct {
diff --git a/av1/encoder/encodeframe.c b/av1/encoder/encodeframe.c index 0271ced..ecba645 100644 --- a/av1/encoder/encodeframe.c +++ b/av1/encoder/encodeframe.c
@@ -3692,7 +3692,7 @@ cfl_init(&td->mb.e_mbd.cfl, cm); - av1_crc_calculator_init(&td->mb.mb_rd_record.crc_calculator, 24, 0x5D6DCB); + av1_crc32c_calculator_init(&td->mb.mb_rd_record.crc_calculator); td->intrabc_used_this_tile = 0;
diff --git a/av1/encoder/encodetxb.c b/av1/encoder/encodetxb.c index d5dee21..10c74a8 100644 --- a/av1/encoder/encodetxb.c +++ b/av1/encoder/encodetxb.c
@@ -24,7 +24,7 @@ #include "av1/encoder/tokenize.h" static int hbt_needs_init = 1; -static CRC_CALCULATOR crc_calculator; +static CRC32C crc_calculator; static const int HBT_EOB = 16; // also the length in opt_qcoeff static const int HBT_TABLE_SIZE = 65536; // 16 bit: holds 65536 'arrays' static const int HBT_ARRAY_LENGTH = 256; // 8 bit: 256 entries @@ -911,7 +911,7 @@ aom_malloc(sizeof(OptTxbQcoeff) * HBT_TABLE_SIZE * HBT_ARRAY_LENGTH); memset(hbt_hash_table, 0, sizeof(OptTxbQcoeff) * HBT_TABLE_SIZE * HBT_ARRAY_LENGTH); - av1_crc_calculator_init(&crc_calculator, 31, 0x5D6DCB); // 31 bit: qc & ctx + av1_crc32c_calculator_init(&crc_calculator); // 31 bit: qc & ctx hbt_needs_init = 0; } @@ -1108,7 +1108,7 @@ assert(hash_data_index <= 64); // 31 bit qc_hash: index to array uint32_t hbt_qc_hash = - av1_get_crc_value(&crc_calculator, txb_hash_data, hash_data_index); + av1_get_crc32c_value(&crc_calculator, txb_hash_data, hash_data_index); // Make ctx_hash. hash_data_index = 0; @@ -1167,7 +1167,7 @@ assert(hash_data_index <= 256); // 31 bit ctx_hash: used to index table uint32_t hbt_ctx_hash = - av1_get_crc_value(&crc_calculator, txb_hash_data, hash_data_index); + av1_get_crc32c_value(&crc_calculator, txb_hash_data, hash_data_index); //// End hash creation return hbt_search_match(hbt_ctx_hash, hbt_qc_hash, txb_info, txb_costs,
diff --git a/av1/encoder/hash.c b/av1/encoder/hash.c index 4f0bbcb..180115d 100644 --- a/av1/encoder/hash.c +++ b/av1/encoder/hash.c
@@ -61,9 +61,65 @@ crc_calculator_init_table(p_crc_calculator); } -uint32_t av1_get_crc_value_c(void *crc_calculator, uint8_t *p, int length) { +uint32_t av1_get_crc_value(void *crc_calculator, uint8_t *p, int length) { CRC_CALCULATOR *p_crc_calculator = (CRC_CALCULATOR *)crc_calculator; crc_calculator_reset(p_crc_calculator); crc_calculator_process_data(p_crc_calculator, p, length); return crc_calculator_get_crc(p_crc_calculator); } + +/* CRC-32C (iSCSI) polynomial in reversed bit order. */ +#define POLY 0x82f63b78 + +/* Construct table for software CRC-32C calculation. */ +void av1_crc32c_calculator_init(CRC32C *p_crc32c) { + uint32_t crc; + + for (int n = 0; n < 256; n++) { + crc = n; + crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; + crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; + crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; + crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; + crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; + crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; + crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; + crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; + p_crc32c->table[0][n] = crc; + } + for (int n = 0; n < 256; n++) { + crc = p_crc32c->table[0][n]; + for (int k = 1; k < 8; k++) { + crc = p_crc32c->table[0][crc & 0xff] ^ (crc >> 8); + p_crc32c->table[k][n] = crc; + } + } +} + +/* Table-driven software version as a fall-back. This is about 15 times slower + than using the hardware instructions. This assumes little-endian integers, + as is the case on Intel processors that the assembler code here is for. */ +uint32_t av1_get_crc32c_value_c(CRC32C *p, uint8_t *buf, size_t len) { + const uint8_t *next = (const uint8_t *)(buf); + uint64_t crc; + + crc = 0 ^ 0xffffffff; + while (len && ((uintptr_t)next & 7) != 0) { + crc = p->table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8); + len--; + } + while (len >= 8) { + crc ^= *(uint64_t *)next; + crc = p->table[7][crc & 0xff] ^ p->table[6][(crc >> 8) & 0xff] ^ + p->table[5][(crc >> 16) & 0xff] ^ p->table[4][(crc >> 24) & 0xff] ^ + p->table[3][(crc >> 32) & 0xff] ^ p->table[2][(crc >> 40) & 0xff] ^ + p->table[1][(crc >> 48) & 0xff] ^ p->table[0][crc >> 56]; + next += 8; + len -= 8; + } + while (len) { + crc = p->table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8); + len--; + } + return (uint32_t)crc ^ 0xffffffff; +}
diff --git a/av1/encoder/hash.h b/av1/encoder/hash.h index 2b77bf9..b7454c2 100644 --- a/av1/encoder/hash.h +++ b/av1/encoder/hash.h
@@ -31,6 +31,16 @@ // calling av1_get_crc_value(). void av1_crc_calculator_init(CRC_CALCULATOR *p_crc_calculator, uint32_t bits, uint32_t truncPoly); +uint32_t av1_get_crc_value(void *crc_calculator, uint8_t *p, int length); + +// CRC32C: POLY = 0x82f63b78; +typedef struct _CRC32C { + /* Table for a quadword-at-a-time software crc. */ + uint32_t table[8][256]; +} CRC32C; + +// init table for software version crc32c +void av1_crc32c_calculator_init(CRC32C *p_crc32c); #ifdef __cplusplus } // extern "C"
diff --git a/av1/encoder/rdopt.c b/av1/encoder/rdopt.c index e3968f1..5c7c243 100644 --- a/av1/encoder/rdopt.c +++ b/av1/encoder/rdopt.c
@@ -1763,8 +1763,8 @@ cur_hash_row += txb_w; cur_diff_row += diff_stride; } - return (av1_get_crc_value(&x->mb_rd_record.crc_calculator, - (uint8_t *)hash_data, 2 * txb_w * txb_h) + return (av1_get_crc32c_value(&x->mb_rd_record.crc_calculator, + (uint8_t *)hash_data, 2 * txb_w * txb_h) << 5) + tx_size; } @@ -4361,8 +4361,8 @@ const int16_t *diff = &p->src_diff[0]; uint16_t hash_data[MAX_SB_SQUARE]; memcpy(hash_data, diff, sizeof(*hash_data) * rows * cols); - return (av1_get_crc_value(&x->mb_rd_record.crc_calculator, - (uint8_t *)hash_data, 2 * rows * cols) + return (av1_get_crc32c_value(&x->mb_rd_record.crc_calculator, + (uint8_t *)hash_data, 2 * rows * cols) << 7) + bsize; } @@ -4487,9 +4487,9 @@ cur_hash_row += cur_tx_bw; cur_diff_row += diff_stride; } - const int hash = av1_get_crc_value(&x->mb_rd_record.crc_calculator, - (uint8_t *)hash_data, - 2 * cur_tx_bw * cur_tx_bh); + const int hash = av1_get_crc32c_value(&x->mb_rd_record.crc_calculator, + (uint8_t *)hash_data, + 2 * cur_tx_bw * cur_tx_bh); // Find corresponding RD info based on the hash value. const int rd_record_idx =
diff --git a/av1/encoder/x86/hash_sse42.c b/av1/encoder/x86/hash_sse42.c index 014d889..65fa463 100644 --- a/av1/encoder/x86/hash_sse42.c +++ b/av1/encoder/x86/hash_sse42.c
@@ -28,8 +28,8 @@ * polynomial is 0x11EDC6F41 * @return A 32-bit unsigned integer representing the CRC */ -uint32_t av1_get_crc_value_sse4_2(void *crc_calculator, uint8_t *p, - size_t len) { +uint32_t av1_get_crc32c_value_sse4_2(void *crc_calculator, uint8_t *p, + size_t len) { (void)crc_calculator; const uint8_t *buf = p; uint32_t crc = 0xFFFFFFFF;
diff --git a/test/hash_test.cc b/test/hash_test.cc index d59cd5a..bd8cac2 100644 --- a/test/hash_test.cc +++ b/test/hash_test.cc
@@ -22,107 +22,35 @@ namespace { -//////////////////////////////////////// -// C version reference code from -// https://stackoverflow.com/questions/17645167/implementing-sse-4-2s-crc32c-in-software?answertab=active#tab-top -//////////////////////////////////////// +typedef uint32_t (*get_crc32c_value_func)(void *calculator, uint8_t *p, + int length); -/* CRC-32C (iSCSI) polynomial in reversed bit order. */ -const uint32_t POLY = 0x82f63b78; +typedef ::testing::tuple<get_crc32c_value_func, int> HashParam; -/* Table for a quadword-at-a-time software crc. */ -uint32_t kCrc32cTable[8][256]; - -/* Construct table for software CRC-32C calculation. */ -static void Crc32cInitSw() { - uint32_t crc; - - for (int n = 0; n < 256; n++) { - crc = n; - crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; - crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; - crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; - crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; - crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; - crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; - crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; - crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; - kCrc32cTable[0][n] = crc; - } - for (int n = 0; n < 256; n++) { - crc = kCrc32cTable[0][n]; - for (int k = 1; k < 8; k++) { - crc = kCrc32cTable[0][crc & 0xff] ^ (crc >> 8); - kCrc32cTable[k][n] = crc; - } - } -} - -/* Table-driven software version as a fall-back. This is about 15 times slower - than using the hardware instructions. This assumes little-endian integers, - as is the case on Intel processors that the assembler code here is for. */ -uint32_t Crc32cSw(const void *buf, size_t len, uint32_t crci) { - const uint8_t *next = reinterpret_cast<const uint8_t *>(buf); - uint64_t crc; - - crc = crci ^ 0xffffffff; - while (len && ((uintptr_t)next & 7) != 0) { - crc = kCrc32cTable[0][(crc ^ *next++) & 0xff] ^ (crc >> 8); - len--; - } - while (len >= 8) { - crc ^= *(uint64_t *)next; - crc = kCrc32cTable[7][crc & 0xff] ^ kCrc32cTable[6][(crc >> 8) & 0xff] ^ - kCrc32cTable[5][(crc >> 16) & 0xff] ^ - kCrc32cTable[4][(crc >> 24) & 0xff] ^ - kCrc32cTable[3][(crc >> 32) & 0xff] ^ - kCrc32cTable[2][(crc >> 40) & 0xff] ^ - kCrc32cTable[1][(crc >> 48) & 0xff] ^ kCrc32cTable[0][crc >> 56]; - next += 8; - len -= 8; - } - while (len) { - crc = kCrc32cTable[0][(crc ^ *next++) & 0xff] ^ (crc >> 8); - len--; - } - return (uint32_t)crc ^ 0xffffffff; -} - -static uint32_t GetCrc32cValueRef(void *calculator, uint8_t *p, int length) { - (void)calculator; - return Crc32cSw(p, length, 0); -} - -typedef uint32_t (*get_crc_value_func)(void *calculator, uint8_t *p, - int length); - -typedef ::testing::tuple<get_crc_value_func, get_crc_value_func, int> HashParam; - -class AV1CrcHashTest : public ::testing::TestWithParam<HashParam> { +class AV1Crc32cHashTest : public ::testing::TestWithParam<HashParam> { public: - ~AV1CrcHashTest(); + ~AV1Crc32cHashTest(); void SetUp(); void TearDown(); protected: - void RunCheckOutput(get_crc_value_func test_impl, - get_crc_value_func ref_impl); - void RunSpeedTest(get_crc_value_func test_impl); + void RunCheckOutput(get_crc32c_value_func test_impl); + void RunSpeedTest(get_crc32c_value_func test_impl); libaom_test::ACMRandom rnd_; - CRC_CALCULATOR calc_; + CRC32C calc_; uint8_t *buffer_; int bsize_; int length_; }; -AV1CrcHashTest::~AV1CrcHashTest() { ; } +AV1Crc32cHashTest::~AV1Crc32cHashTest() { ; } -void AV1CrcHashTest::SetUp() { +void AV1Crc32cHashTest::SetUp() { rnd_.Reset(libaom_test::ACMRandom::DeterministicSeed()); - av1_crc_calculator_init(&calc_, 24, 0x5D6DCB); - Crc32cInitSw(); - bsize_ = GET_PARAM(2); + av1_crc32c_calculator_init(&calc_); + + bsize_ = GET_PARAM(1); length_ = bsize_ * bsize_ * sizeof(uint16_t); buffer_ = new uint8_t[length_]; ASSERT_TRUE(buffer_ != NULL); @@ -131,10 +59,10 @@ } } -void AV1CrcHashTest::TearDown() { delete[] buffer_; } +void AV1Crc32cHashTest::TearDown() { delete[] buffer_; } -void AV1CrcHashTest::RunCheckOutput(get_crc_value_func test_impl, - get_crc_value_func ref_impl) { +void AV1Crc32cHashTest::RunCheckOutput(get_crc32c_value_func test_impl) { + get_crc32c_value_func ref_impl = av1_get_crc32c_value_c; // for the same buffer crc should be the same uint32_t crc0 = test_impl(&calc_, buffer_, length_); uint32_t crc1 = test_impl(&calc_, buffer_, length_); @@ -149,8 +77,8 @@ ASSERT_EQ(crc3, crc4); } -void AV1CrcHashTest::RunSpeedTest(get_crc_value_func test_impl) { - get_crc_value_func impls[] = { av1_get_crc_value_c, test_impl }; +void AV1Crc32cHashTest::RunSpeedTest(get_crc32c_value_func test_impl) { + get_crc32c_value_func impls[] = { av1_get_crc32c_value_c, test_impl }; const int repeat = 10000000 / (bsize_ + bsize_); aom_usec_timer timer; @@ -167,25 +95,21 @@ printf("(%3.2f)\n", time[0] / time[1]); } -TEST_P(AV1CrcHashTest, CheckOutput) { - RunCheckOutput(GET_PARAM(0), GET_PARAM(1)); -} +TEST_P(AV1Crc32cHashTest, CheckOutput) { RunCheckOutput(GET_PARAM(0)); } -TEST_P(AV1CrcHashTest, DISABLED_Speed) { RunSpeedTest(GET_PARAM(0)); } +TEST_P(AV1Crc32cHashTest, DISABLED_Speed) { RunSpeedTest(GET_PARAM(0)); } const int kValidBlockSize[] = { 64, 32, 8, 4 }; INSTANTIATE_TEST_CASE_P( - C, AV1CrcHashTest, - ::testing::Combine(::testing::Values(&av1_get_crc_value_c), - ::testing::Values(&av1_get_crc_value_c), + C, AV1Crc32cHashTest, + ::testing::Combine(::testing::Values(&av1_get_crc32c_value_c), ::testing::ValuesIn(kValidBlockSize))); #if HAVE_SSE4_2 INSTANTIATE_TEST_CASE_P( - SSE4_2, AV1CrcHashTest, - ::testing::Combine(::testing::Values(&av1_get_crc_value_sse4_2), - ::testing::Values(&GetCrc32cValueRef), + SSE4_2, AV1Crc32cHashTest, + ::testing::Combine(::testing::Values(&av1_get_crc32c_value_sse4_2), ::testing::ValuesIn(kValidBlockSize))); #endif