OLD | NEW |
| (Empty) |
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/base/timeutils.h" | |
17 #include "webrtc/system_wrappers/include/sort.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 int64_t 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 int64_t t0 = rtc::TimeNanos(); | |
163 if (keySort) | |
164 { | |
165 retVal = webrtc::KeySort(data, key, DataLength, sizeof(LotsOfData<Ke
yType>), | |
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 int64_t t1 = rtc::TimeNanos(); | |
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[i
ndex].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 / rtc::kNumNanosecsPerMillisec; | |
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 } | |
OLD | NEW |