Implement non-recursive av1_update_scan_order The performance difference is lowres: 0.02% gain midres: 0.07% gain Change-Id: I68a74462f41db3bf24573cf2a08c8b5b8aa13f5f
diff --git a/av1/common/scan.c b/av1/common/scan.c index 2e6c447..c6e3b40 100644 --- a/av1/common/scan.c +++ b/av1/common/scan.c
@@ -8267,23 +8267,6 @@ } } -// topological sort -static void dfs_scan(int tx1d_size, int *scan_idx, int coeff_idx, int16_t *scan, - int16_t *iscan) { - const int r = coeff_idx / tx1d_size; - const int c = coeff_idx % tx1d_size; - - if (iscan[coeff_idx] != -1) return; - - if (r > 0) dfs_scan(tx1d_size, scan_idx, coeff_idx - tx1d_size, scan, iscan); - - if (c > 0) dfs_scan(tx1d_size, scan_idx, coeff_idx - 1, scan, iscan); - - scan[*scan_idx] = coeff_idx; - iscan[coeff_idx] = *scan_idx; - ++(*scan_idx); -} - void av1_update_neighbors(TX_SIZE tx_size, const int16_t *scan, const int16_t *iscan, int16_t *neighbors) { const int tx1d_wide = tx_size_wide[tx_size]; @@ -8393,6 +8376,7 @@ assert(new_si == tx2d_size); } +#if USE_TOPOLOGICAL_SORT void av1_update_sort_order(TX_SIZE tx_size, TX_TYPE tx_type, const uint32_t *non_zero_prob, int16_t *sort_order) { const SCAN_ORDER *sc = get_default_scan(tx_size, tx_type, 0); @@ -8411,6 +8395,23 @@ } } +// topological sort +static void dfs_scan(int tx1d_size, int *scan_idx, int coeff_idx, int16_t *scan, + int16_t *iscan) { + const int r = coeff_idx / tx1d_size; + const int c = coeff_idx % tx1d_size; + + if (iscan[coeff_idx] != -1) return; + + if (r > 0) dfs_scan(tx1d_size, scan_idx, coeff_idx - tx1d_size, scan, iscan); + + if (c > 0) dfs_scan(tx1d_size, scan_idx, coeff_idx - 1, scan, iscan); + + scan[*scan_idx] = coeff_idx; + iscan[coeff_idx] = *scan_idx; + ++(*scan_idx); +} + void av1_update_scan_order(TX_SIZE tx_size, int16_t *sort_order, int16_t *scan, int16_t *iscan) { int coeff_idx; @@ -8429,10 +8430,48 @@ dfs_scan(tx1d_size, &scan_idx, coeff_idx, scan, iscan); } } +#else + +static void filter_prob(TX_SIZE tx_size, uint32_t *prob) { + const int tx1d_wide = tx_size_wide[tx_size]; + const int tx1d_high = tx_size_high[tx_size]; + for (int r = tx1d_high - 1; r >= 0; --r) { + for (int c = tx1d_wide - 1; c >= 0; --c) { + int idx = r * tx1d_wide + c; + uint32_t v = prob[idx]; + if (r > 0 && prob[idx - tx1d_wide] < v) prob[idx - tx1d_wide] = v; + if (c > 0 && prob[idx - 1] < v) prob[idx - 1] = v; + } + } +} + +void av1_update_scan_order(TX_SIZE tx_size, TX_TYPE tx_type, + uint32_t *non_zero_prob, int16_t *scan, + int16_t *iscan) { + const SCAN_ORDER *sc = get_default_scan(tx_size, tx_type, 0); + uint32_t temp[COEFF_IDX_SIZE]; + const int tx2d_size = tx_size_2d[tx_size]; + int scan_idx; + assert(tx2d_size <= COEFF_IDX_SIZE); + memcpy(temp, non_zero_prob, tx2d_size * sizeof(*non_zero_prob)); + filter_prob(tx_size, temp); + av1_augment_prob(tx_size, tx_type, temp); + qsort(temp, tx2d_size, sizeof(*temp), cmp_prob); + for (scan_idx = 0; scan_idx < tx2d_size; ++scan_idx) { + const int default_scan_idx = + (temp[scan_idx] & COEFF_IDX_MASK) ^ COEFF_IDX_MASK; + const int coeff_idx = sc->scan[default_scan_idx]; + scan[scan_idx] = coeff_idx; + iscan[coeff_idx] = scan_idx; + } +} +#endif static void update_scan_order_facade(AV1_COMMON *cm, TX_SIZE tx_size, TX_TYPE tx_type, int use_curr_frame) { +#if USE_TOPOLOGICAL_SORT int16_t sort_order[COEFF_IDX_SIZE]; +#endif uint32_t *non_zero_prob; if (use_curr_frame) non_zero_prob = get_non_zero_prob(cm->fc, tx_size, tx_type); @@ -8442,8 +8481,12 @@ int16_t *iscan = get_adapt_iscan(cm->fc, tx_size, tx_type); int16_t *nb = get_adapt_nb(cm->fc, tx_size, tx_type); assert(tx_size_2d[tx_size] <= COEFF_IDX_SIZE); +#if USE_TOPOLOGICAL_SORT av1_update_sort_order(tx_size, tx_type, non_zero_prob, sort_order); av1_update_scan_order(tx_size, sort_order, scan, iscan); +#else + av1_update_scan_order(tx_size, tx_type, non_zero_prob, scan, iscan); +#endif limit_nb_scan_distance(tx_size, scan, iscan); av1_update_neighbors(tx_size, scan, iscan, nb); }
diff --git a/av1/common/scan.h b/av1/common/scan.h index 6f0078f..b1d4c08 100644 --- a/av1/common/scan.h +++ b/av1/common/scan.h
@@ -31,6 +31,7 @@ #if CONFIG_ADAPT_SCAN #define USE_2X2_PROB 1 +#define USE_TOPOLOGICAL_SORT 0 void av1_update_scan_count_facade(AV1_COMMON *cm, FRAME_COUNTS *counts, TX_SIZE tx_size, TX_TYPE tx_type, const tran_low_t *dqcoeffs, int max_scan); @@ -40,6 +41,7 @@ // will be scanned first void av1_augment_prob(TX_SIZE tx_size, TX_TYPE tx_type, uint32_t *prob); +#if USE_TOPOLOGICAL_SORT // apply quick sort on nonzero probabilities to obtain a sort order void av1_update_sort_order(TX_SIZE tx_size, TX_TYPE tx_type, const uint32_t *non_zero_prob, int16_t *sort_order); @@ -49,6 +51,11 @@ // scanned before the to-be-scanned coefficient. void av1_update_scan_order(TX_SIZE tx_size, int16_t *sort_order, int16_t *scan, int16_t *iscan); +#else // USE_TOPOLOGICAL_SORT +void av1_update_scan_order(TX_SIZE tx_size, TX_TYPE tx_type, + uint32_t *non_zero_prob, int16_t *scan, + int16_t *iscan); +#endif // USE_TOPOLOGICAL_SORT // For each coeff_idx in scan[], update its above and left neighbors in // neighbors[] accordingly.
diff --git a/test/scan_test.cc b/test/scan_test.cc index ef5d684..2b11bd1 100644 --- a/test/scan_test.cc +++ b/test/scan_test.cc
@@ -43,6 +43,7 @@ } } +#if USE_TOPOLOGICAL_SORT TEST(ScanTest, av1_update_sort_order) { const TX_SIZE tx_size = TX_4X4; const TX_TYPE tx_type = DCT_DCT; @@ -54,7 +55,9 @@ av1_update_sort_order(tx_size, tx_type, prob, sort_order); for (int i = 0; i < 16; ++i) EXPECT_EQ(ref_sort_order[i], sort_order[i]); } +#endif +#if USE_TOPOLOGICAL_SORT TEST(ScanTest, av1_update_scan_order) { TX_SIZE tx_size = TX_4X4; const TX_TYPE tx_type = DCT_DCT; @@ -74,6 +77,7 @@ EXPECT_EQ(i, scan[ref_iscan[i]]); } } +#endif TEST(ScanTest, av1_update_neighbors) { TX_SIZE tx_size = TX_4X4;