Palette: use insertion sort for sorting neighbors' scores.
While sorting, preserving the order of the rest of the list when moving
an element to the top of list makes hardware implementation much simpler.
The compression performance is roughly same: overall, avg performance on
screen-content set is 0.137% better than before in fact.
Bug=aom:127
Change-Id: Id1aa1e90254b44eae9133b47bca8f853f6a62c6b
diff --git a/av1/common/entropymode.c b/av1/common/entropymode.c
index d8715c0..34e9ad6 100644
--- a/av1/common/entropymode.c
+++ b/av1/common/entropymode.c
@@ -1262,17 +1262,20 @@
max_idx = j;
}
}
-
if (max_idx != i) {
- int temp = scores[i];
- scores[i] = scores[max_idx];
- scores[max_idx] = temp;
-
- temp = color_order[i];
- color_order[i] = color_order[max_idx];
- color_order[max_idx] = temp;
+ // Move the score at index 'max_idx' to index 'i', and shift the scores
+ // from 'i' to 'max_idx - 1' by 1.
+ const int max_score = scores[max_idx];
+ const uint8_t max_color_order = color_order[max_idx];
+ int k;
+ for (k = max_idx; k > i; --k) {
+ scores[k] = scores[k - 1];
+ color_order[k] = color_order[k - 1];
+ inverse_color_order[color_order[k]] = k;
+ }
+ scores[i] = max_score;
+ color_order[i] = max_color_order;
inverse_color_order[color_order[i]] = i;
- inverse_color_order[color_order[max_idx]] = max_idx;
}
}
