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