sorting_network.h (3456B)
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 */ 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 */ 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_