1 /*
2 * Copyright (c) 2021, Alliance for Open Media. All rights reserved.
3 *
4 * This source code is subject to the terms of the BSD 2 Clause License and
5 * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
6 * was not distributed with this source code in the LICENSE file, you can
7 * obtain it at www.aomedia.org/license/software. If the Alliance for Open
8 * Media Patent License 1.0 was not distributed with this source code in the
9 * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
10 */
11
12 /*! \file
13 * This file contains several utility functions used to sort small arrays with
14 * sorting networks.
15 *
16 * Sorting network is a (potentially branch-less) way to quickly sort small
17 * arrays with known size. For more details, consult
18 * (https://en.wikipedia.org/wiki/Sorting_network).
19 */
20 #ifndef AOM_AV1_ENCODER_SORTING_NETWORK_H_
21 #define AOM_AV1_ENCODER_SORTING_NETWORK_H_
22
23 #include "aom/aom_integer.h"
24
25 #define SWAP(i, j) \
26 do { \
27 const float maxf = (k[i] >= k[j]) ? k[i] : k[j]; \
28 const float minf = (k[i] >= k[j]) ? k[j] : k[i]; \
29 const int maxi = (k[i] >= k[j]) ? v[i] : v[j]; \
30 const int mini = (k[i] >= k[j]) ? v[j] : v[i]; \
31 k[i] = maxf; \
32 k[j] = minf; \
33 v[i] = maxi; \
34 v[j] = mini; \
35 } while (0)
36
37 /*!\brief Sorts two size-16 arrays of keys and values in descending order of
38 * keys.
39 *
40 * \param[in,out] k An length-16 array of float serves as the keys.
41 * \param[in,out] v An length-16 array of int32 serves as the
42 * value.
43 */
av1_sort_fi32_16(float k[],int32_t v[])44 static inline void av1_sort_fi32_16(float k[], int32_t v[]) {
45 SWAP(0, 1);
46 SWAP(2, 3);
47 SWAP(4, 5);
48 SWAP(6, 7);
49 SWAP(8, 9);
50 SWAP(10, 11);
51 SWAP(12, 13);
52 SWAP(14, 15);
53 SWAP(0, 2);
54 SWAP(1, 3);
55 SWAP(4, 6);
56 SWAP(5, 7);
57 SWAP(8, 10);
58 SWAP(9, 11);
59 SWAP(12, 14);
60 SWAP(13, 15);
61 SWAP(1, 2);
62 SWAP(5, 6);
63 SWAP(0, 4);
64 SWAP(3, 7);
65 SWAP(9, 10);
66 SWAP(13, 14);
67 SWAP(8, 12);
68 SWAP(11, 15);
69 SWAP(1, 5);
70 SWAP(2, 6);
71 SWAP(9, 13);
72 SWAP(10, 14);
73 SWAP(0, 8);
74 SWAP(7, 15);
75 SWAP(1, 4);
76 SWAP(3, 6);
77 SWAP(9, 12);
78 SWAP(11, 14);
79 SWAP(2, 4);
80 SWAP(3, 5);
81 SWAP(10, 12);
82 SWAP(11, 13);
83 SWAP(1, 9);
84 SWAP(6, 14);
85 SWAP(3, 4);
86 SWAP(11, 12);
87 SWAP(1, 8);
88 SWAP(2, 10);
89 SWAP(5, 13);
90 SWAP(7, 14);
91 SWAP(3, 11);
92 SWAP(2, 8);
93 SWAP(4, 12);
94 SWAP(7, 13);
95 SWAP(3, 10);
96 SWAP(5, 12);
97 SWAP(3, 9);
98 SWAP(6, 12);
99 SWAP(3, 8);
100 SWAP(7, 12);
101 SWAP(5, 9);
102 SWAP(6, 10);
103 SWAP(4, 8);
104 SWAP(7, 11);
105 SWAP(5, 8);
106 SWAP(7, 10);
107 SWAP(6, 8);
108 SWAP(7, 9);
109 SWAP(7, 8);
110 }
111
112 /*!\brief Sorts two size-8 arrays of keys and values in descending order of
113 * keys.
114 *
115 * \param[in,out] k An length-8 array of float serves as the keys.
116 * \param[in,out] v An length-8 array of int32 serves as the values.
117 */
av1_sort_fi32_8(float k[],int32_t v[])118 static inline void av1_sort_fi32_8(float k[], int32_t v[]) {
119 SWAP(0, 1);
120 SWAP(2, 3);
121 SWAP(4, 5);
122 SWAP(6, 7);
123 SWAP(0, 2);
124 SWAP(1, 3);
125 SWAP(4, 6);
126 SWAP(5, 7);
127 SWAP(1, 2);
128 SWAP(5, 6);
129 SWAP(0, 4);
130 SWAP(3, 7);
131 SWAP(1, 5);
132 SWAP(2, 6);
133 SWAP(1, 4);
134 SWAP(3, 6);
135 SWAP(2, 4);
136 SWAP(3, 5);
137 SWAP(3, 4);
138 }
139 #undef SWAP
140 #endif // AOM_AV1_ENCODER_SORTING_NETWORK_H_
141