1 /* 2 * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 #include <stdio.h> 12 #include <string.h> 13 14 #include <algorithm> 15 16 #include "webrtc/system_wrappers/include/sort.h" 17 #include "webrtc/system_wrappers/include/tick_util.h" 18 19 // Excellent work polluting the global namespace Visual Studio... 20 #undef max 21 #undef min 22 #include <limits> 23 24 template<typename KeyType> 25 struct LotsOfData 26 { 27 KeyType key; 28 char data[64]; 29 }; 30 31 template<typename DataType> 32 int Compare(const void* dataX, const void* dataY) 33 { 34 DataType dataX = (DataType)*(const DataType*)dataX; 35 DataType dataY = (DataType)*(const DataType*)dataY; 36 if (dataX > dataY) 37 { 38 return 1; 39 } 40 else if (dataX < dataY) 41 { 42 return -1; 43 } 44 45 return 0; 46 }; 47 48 template<typename DataType, typename KeyType> 49 int CompareKey(const void* dataX, const void* dataY) 50 { 51 KeyType keyX = ((const DataType*)dataX)->key; 52 KeyType keyY = ((const DataType*)dataY)->key; 53 if (keyX > keyY) 54 { 55 return 1; 56 } 57 else if (keyX < keyY) 58 { 59 return -1; 60 } 61 62 return 0; 63 } 64 65 template<typename DataType> 66 struct KeyLessThan 67 { 68 bool operator()(const DataType &dataX, const DataType &dataY) const 69 { 70 return dataX.key < dataY.key; 71 } 72 }; 73 74 const char* TypeEnumToString(webrtc::Type type) 75 { 76 switch (type) 77 { 78 using namespace webrtc; 79 case TYPE_Word8: 80 return "Word8"; 81 case TYPE_UWord8: 82 return "UWord8"; 83 case TYPE_Word16: 84 return "Word16"; 85 case TYPE_UWord16: 86 return "UWord16"; 87 case TYPE_Word32: 88 return "Word32"; 89 case TYPE_UWord32: 90 return "UWord32"; 91 case TYPE_Word64: 92 return "Word64"; 93 case TYPE_UWord64: 94 return "UWord64"; 95 case TYPE_Float32: 96 return "Float32"; 97 case TYPE_Float64: 98 return "Float64"; 99 default: 100 return "Unrecognized"; 101 } 102 } 103 104 template<typename Type> 105 Type TypedRand() 106 { 107 if (std::numeric_limits<Type>::is_integer) 108 { 109 double floatRand = static_cast<double>(rand()) / RAND_MAX; 110 if (std::numeric_limits<Type>::is_signed) 111 { 112 floatRand -= 0.5; 113 } 114 115 // Uniform [-max()/2, max()/2] for signed 116 // [0, max()] for unsigned 117 return static_cast<Type>(floatRand * std::numeric_limits<Type>::max()); 118 } 119 else // Floating point 120 { 121 // Uniform [-0.5, 0.5] 122 // The outer cast is to remove template warnings. 123 return static_cast<Type>((static_cast<Type>(rand()) / RAND_MAX) - 0.5); 124 } 125 } 126 127 template<typename KeyType> 128 void RunSortTest(webrtc::Type sortType, bool keySort) 129 { 130 enum { DataLength = 1000 }; 131 enum { NumOfTests = 10000 }; 132 KeyType key[DataLength]; 133 KeyType keyRef[DataLength]; 134 LotsOfData<KeyType> data[DataLength]; 135 LotsOfData<KeyType> dataRef[DataLength]; 136 int32_t retVal = 0; 137 138 if (keySort) 139 { 140 printf("Running %s KeySort() tests...\n", TypeEnumToString(sortType)); 141 } 142 else 143 { 144 printf("Running %s Sort() tests...\n", TypeEnumToString(sortType)); 145 } 146 147 TickInterval accTicks; 148 for (int i = 0; i < NumOfTests; i++) 149 { 150 for (int j = 0; j < DataLength; j++) 151 { 152 key[j] = TypedRand<KeyType>(); 153 data[j].key = key[j]; 154 // Write index to payload. We use this later for verification. 155 sprintf(data[j].data, "%d", j); 156 } 157 158 memcpy(dataRef, data, sizeof(data)); 159 memcpy(keyRef, key, sizeof(key)); 160 161 retVal = 0; 162 TickTime t0 = TickTime::Now(); 163 if (keySort) 164 { 165 retVal = webrtc::KeySort(data, key, DataLength, sizeof(LotsOfData<KeyType>), 166 sortType); 167 168 //std::sort(data, data + DataLength, KeyLessThan<KeyType>()); 169 //qsort(data, DataLength, sizeof(LotsOfData<KeyType>), 170 // CompareKey<LotsOfData<KeyType>, KeyType>); 171 } 172 else 173 { 174 retVal = webrtc::Sort(key, DataLength, sortType); 175 176 //std::sort(key, key + DataLength); 177 //qsort(key, DataLength, sizeof(KeyType), Compare<KeyType>); 178 } 179 TickTime t1 = TickTime::Now(); 180 accTicks += (t1 - t0); 181 182 if (retVal != 0) 183 { 184 printf("Test failed at iteration %d:\n", i); 185 printf("Sort returned an error. "); 186 printf("It likely does not support the requested type\nExiting...\n"); 187 exit(0); 188 } 189 190 // Reference sort. 191 if (!keySort) 192 { 193 std::sort(keyRef, keyRef + DataLength); 194 } 195 196 if (keySort) 197 { 198 for (int j = 0; j < DataLength - 1; j++) 199 { 200 if (data[j].key > data[j + 1].key) 201 { 202 printf("Test failed at iteration %d:\n", i); 203 printf("Keys are not monotonically increasing\nExiting...\n"); 204 exit(0); 205 } 206 207 int index = atoi(data[j].data); 208 if (index < 0 || index >= DataLength || data[j].key != dataRef[index].key) 209 { 210 printf("Test failed at iteration %d:\n", i); 211 printf("Payload data is corrupt\nExiting...\n"); 212 exit(0); 213 } 214 } 215 } 216 else 217 { 218 for (int j = 0; j < DataLength - 1; j++) 219 { 220 if (key[j] > key[j + 1]) 221 { 222 printf("Test failed at iteration %d:\n", i); 223 printf("Data is not monotonically increasing\nExiting...\n"); 224 exit(0); 225 } 226 } 227 228 if (memcmp(key, keyRef, sizeof(key)) != 0) 229 { 230 printf("Test failed at iteration %d:\n", i); 231 printf("Sort data differs from std::sort reference\nExiting...\n"); 232 exit(0); 233 } 234 } 235 } 236 237 printf("Compliance test passed over %d iterations\n", NumOfTests); 238 239 int64_t executeTime = accTicks.Milliseconds(); 240 printf("Execute time: %.2f s\n\n", (float)executeTime / 1000); 241 } 242 243 int main() 244 { 245 // Seed rand(). 246 srand(42); 247 bool keySort = false; 248 for (int i = 0; i < 2; i++) { 249 RunSortTest<int8_t>(webrtc::TYPE_Word8, keySort); 250 RunSortTest<uint8_t>(webrtc::TYPE_UWord8, keySort); 251 RunSortTest<int16_t>(webrtc::TYPE_Word16, keySort); 252 RunSortTest<uint16_t>(webrtc::TYPE_UWord16, keySort); 253 RunSortTest<int32_t>(webrtc::TYPE_Word32, keySort); 254 RunSortTest<uint32_t>(webrtc::TYPE_UWord32, keySort); 255 RunSortTest<int64_t>(webrtc::TYPE_Word64, keySort); 256 RunSortTest<uint64_t>(webrtc::TYPE_UWord64, keySort); 257 RunSortTest<float>(webrtc::TYPE_Float32, keySort); 258 RunSortTest<double>(webrtc::TYPE_Float64, keySort); 259 260 keySort = !keySort; 261 } 262 263 printf("All tests passed\n"); 264 265 return 0; 266 } 267
