ntdll: Reimplement qsort() using generic mergesort.
[wine] / dlls / ntdll / misc.c
1 /*
2  * Helper functions for ntdll
3  *
4  * Copyright 2000 Juergen Schmied
5  * Copyright 2010 Marcus Meissner
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this library; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
20  */
21
22 #include "config.h"
23
24 #include <time.h>
25 #include <math.h>
26 #ifdef HAVE_SYS_UTSNAME_H
27 #include <sys/utsname.h>
28 #endif
29
30 #include "wine/library.h"
31 #include "wine/debug.h"
32 #include "ntdll_misc.h"
33
34 WINE_DEFAULT_DEBUG_CHANNEL(ntdll);
35
36 #if defined(__GNUC__) && defined(__i386__)
37 #define DO_FPU(x,y) __asm__ __volatile__( x " %0;fwait" : "=m" (y) : )
38 #define POP_FPU(x) DO_FPU("fstpl",x)
39 #endif
40
41 LPCSTR debugstr_ObjectAttributes(const OBJECT_ATTRIBUTES *oa)
42 {
43     if (!oa) return "<null>";
44     return wine_dbg_sprintf( "{name=%s, attr=0x%08x, hRoot=%p, sd=%p}\n",
45                              debugstr_us(oa->ObjectName), oa->Attributes,
46                              oa->RootDirectory, oa->SecurityDescriptor );
47 }
48
49 LPCSTR debugstr_us( const UNICODE_STRING *us )
50 {
51     if (!us) return "<null>";
52     return debugstr_wn(us->Buffer, us->Length / sizeof(WCHAR));
53 }
54
55 /*********************************************************************
56  *                  _ftol   (NTDLL.@)
57  *
58  * VERSION
59  *      [GNUC && i386]
60  */
61 #if defined(__GNUC__) && defined(__i386__)
62 LONGLONG CDECL NTDLL__ftol(void)
63 {
64         /* don't just do DO_FPU("fistp",retval), because the rounding
65          * mode must also be set to "round towards zero"... */
66         double fl;
67         POP_FPU(fl);
68         return (LONGLONG)fl;
69 }
70 #endif /* defined(__GNUC__) && defined(__i386__) */
71
72 /*********************************************************************
73  *                  _ftol   (NTDLL.@)
74  *
75  * FIXME
76  *      Should be register function
77  * VERSION
78  *      [!GNUC && i386]
79  */
80 #if !defined(__GNUC__) && defined(__i386__)
81 LONGLONG CDECL NTDLL__ftol(double fl)
82 {
83         FIXME("should be register function\n");
84         return (LONGLONG)fl;
85 }
86 #endif /* !defined(__GNUC__) && defined(__i386__) */
87
88 /*********************************************************************
89  *                  _CIpow   (NTDLL.@)
90  * VERSION
91  *      [GNUC && i386]
92  */
93 #if defined(__GNUC__) && defined(__i386__)
94 double CDECL NTDLL__CIpow(void)
95 {
96         double x,y;
97         POP_FPU(y);
98         POP_FPU(x);
99         return pow(x,y);
100 }
101 #endif /* defined(__GNUC__) && defined(__i386__) */
102
103
104 /*********************************************************************
105  *                  _CIpow   (NTDLL.@)
106  *
107  * FIXME
108  *      Should be register function
109  *
110  * VERSION
111  *      [!GNUC && i386]
112  */
113 #if !defined(__GNUC__) && defined(__i386__)
114 double CDECL NTDLL__CIpow(double x,double y)
115 {
116         FIXME("should be register function\n");
117         return pow(x,y);
118 }
119 #endif /* !defined(__GNUC__) && defined(__i386__) */
120
121 /*********************************************************************
122  *                  wine_get_version   (NTDLL.@)
123  */
124 const char * CDECL NTDLL_wine_get_version(void)
125 {
126     return wine_get_version();
127 }
128
129 /*********************************************************************
130  *                  wine_get_build_id   (NTDLL.@)
131  */
132 const char * CDECL NTDLL_wine_get_build_id(void)
133 {
134     return wine_get_build_id();
135 }
136
137 /*********************************************************************
138  *                  wine_get_host_version   (NTDLL.@)
139  */
140 void CDECL NTDLL_wine_get_host_version( const char **sysname, const char **release )
141 {
142 #ifdef HAVE_SYS_UTSNAME_H
143     static struct utsname buf;
144     static int init_done;
145
146     if (!init_done)
147     {
148         uname( &buf );
149         init_done = 1;
150     }
151     if (sysname) *sysname = buf.sysname;
152     if (release) *release = buf.release;
153 #else
154     if (sysname) *sysname = "";
155     if (release) *release = "";
156 #endif
157 }
158
159 /*********************************************************************
160  *                  abs   (NTDLL.@)
161  */
162 int CDECL NTDLL_abs( int i )
163 {
164     return abs( i );
165 }
166
167 /*********************************************************************
168  *                  labs   (NTDLL.@)
169  */
170 LONG CDECL NTDLL_labs( LONG i )
171 {
172     return labs( i );
173 }
174
175 /*********************************************************************
176  *                  atan   (NTDLL.@)
177  */
178 double CDECL NTDLL_atan( double d )
179 {
180     return atan( d );
181 }
182
183 /*********************************************************************
184  *                  ceil   (NTDLL.@)
185  */
186 double CDECL NTDLL_ceil( double d )
187 {
188     return ceil( d );
189 }
190
191 /*********************************************************************
192  *                  cos   (NTDLL.@)
193  */
194 double CDECL NTDLL_cos( double d )
195 {
196     return cos( d );
197 }
198
199 /*********************************************************************
200  *                  fabs   (NTDLL.@)
201  */
202 double CDECL NTDLL_fabs( double d )
203 {
204     return fabs( d );
205 }
206
207 /*********************************************************************
208  *                  floor   (NTDLL.@)
209  */
210 double CDECL NTDLL_floor( double d )
211 {
212     return floor( d );
213 }
214
215 /*********************************************************************
216  *                  log   (NTDLL.@)
217  */
218 double CDECL NTDLL_log( double d )
219 {
220     return log( d );
221 }
222
223 /*********************************************************************
224  *                  pow   (NTDLL.@)
225  */
226 double CDECL NTDLL_pow( double x, double y )
227 {
228     return pow( x, y );
229 }
230
231 /*********************************************************************
232  *                  sin   (NTDLL.@)
233  */
234 double CDECL NTDLL_sin( double d )
235 {
236     return sin( d );
237 }
238
239 /*********************************************************************
240  *                  sqrt   (NTDLL.@)
241  */
242 double CDECL NTDLL_sqrt( double d )
243 {
244     return sqrt( d );
245 }
246
247 /*********************************************************************
248  *                  tan   (NTDLL.@)
249  */
250 double CDECL NTDLL_tan( double d )
251 {
252     return tan( d );
253 }
254
255
256 /* Merge Sort. Algorithm taken from http://www.linux-related.de/index.html?/coding/sort/sort_merge.htm */
257 static void mergesort( void *arr, void *barr, int elemsize, int(__cdecl *compar)(const void *, const void *),
258                        int left, int right )
259 {
260     if(right>left) {
261         int i, j, k, m;
262         m=(right+left)/2;
263         mergesort( arr, barr, elemsize, compar, left, m);
264         mergesort( arr, barr, elemsize, compar, m+1, right);
265
266 #define X(a,i) ((char*)a+elemsize*(i))
267         for (i=m+1; i>left; i--)
268             memcpy (X(barr,(i-1)),X(arr,(i-1)),elemsize);
269         for (j=m; j<right; j++)
270             memcpy (X(barr,(right+m-j)),X(arr,(j+1)),elemsize);
271
272         for (k=left; k<=right; k++) {
273             /*arr[k]=(barr[i]<barr[j])?barr[i++]:barr[j--];*/
274             if (compar(X(barr,i),X(barr,j))<0) {
275                 memcpy(X(arr,k),X(barr,i),elemsize);
276                 i++;
277             } else {
278                 memcpy(X(arr,k),X(barr,j),elemsize);
279                 j--;
280             }
281         }
282     }
283 #undef X
284 }
285
286 /*********************************************************************
287  *                  qsort   (NTDLL.@)
288  */
289 void __cdecl NTDLL_qsort( void *base, size_t nmemb, size_t size,
290                           int(__cdecl *compar)(const void *, const void *) )
291 {
292     void *secondarr = RtlAllocateHeap (GetProcessHeap(), 0, nmemb*size);
293     mergesort( base, secondarr, size, compar, 0, nmemb-1 );
294     RtlFreeHeap (GetProcessHeap(),0, secondarr);
295 }