VirtualBox

source: vbox/trunk/src/recompiler/cutils.c@ 33000

Last change on this file since 33000 was 26499, checked in by vboxsync, 14 years ago

recompier: whitespace cleanup. (Clean up whitespace on the foreign code before trying to merge in new changes again.)
  • Property svn:eol-style set to native
File size: 16.0 KB
Line 
1/*
2 * Simple C functions to supplement the C library
3 *
4 * Copyright (c) 2006 Fabrice Bellard
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22 * THE SOFTWARE.
23 */
24#include "qemu-common.h"
25
26#ifdef VBOX
27#include "osdep.h"
28
29static inline int toupper(int ch) {
30 if ( (unsigned int)(ch - 'a') < 26u )
31 ch += 'A' - 'a';
32 return ch;
33}
34
35/* Quick sort from OpenSolaris:
36 http://src.opensolaris.org/source/raw/onnv/onnv-gate/usr/src/common/util/qsort.c */
37/*
38 * choose a median of 3 values
39 *
40 * note: cstyle specifically prohibits nested conditional operators
41 * but this is the only way to do the median of 3 function in-line
42 */
43#define med3(a, b, c) (cmp((a), (b)) < 0) \
44 ? ((cmp((b), (c)) < 0) ? (b) : (cmp((a), (c)) < 0) ? (c) : (a)) \
45 : ((cmp((b), (c)) > 0) ? (b) : (cmp((a), (c)) > 0) ? (c) : (a))
46
47#define THRESH_L 5 /* threshold for insertion sort */
48#define THRESH_M3 20 /* threshold for median of 3 */
49#define THRESH_M9 50 /* threshold for median of 9 */
50
51typedef struct {
52 char *b_lim;
53 size_t nrec;
54} stk_t;
55
56/*
57 * The following swap functions should not create a stack frame
58 * the SPARC call / return instruction will be executed
59 * but the a save / restore will not be executed
60 * which means we won't do a window turn with the spill / fill overhead
61 * verify this by examining the assembly code
62 */
63
64/* ARGSUSED */
65static void
66swapp32(uint32_t *r1, uint32_t *r2, size_t cnt)
67{
68 uint32_t temp;
69
70 temp = *r1;
71 *r1++ = *r2;
72 *r2++ = temp;
73}
74
75/* ARGSUSED */
76static void
77swapp64(uint64_t *r1, uint64_t *r2, size_t cnt)
78{
79 uint64_t temp;
80
81 temp = *r1;
82 *r1++ = *r2;
83 *r2++ = temp;
84}
85
86static void
87swapi(uint32_t *r1, uint32_t *r2, size_t cnt)
88{
89 uint32_t temp;
90
91 /* character by character */
92 while (cnt--) {
93 temp = *r1;
94 *r1++ = *r2;
95 *r2++ = temp;
96 }
97}
98
99static void
100swapb(char *r1, char *r2, size_t cnt)
101{
102 char temp;
103
104 /* character by character */
105 while (cnt--) {
106 temp = *r1;
107 *r1++ = *r2;
108 *r2++ = temp;
109 }
110}
111
112/*
113 * qsort() is a general purpose, in-place sorting routine using a
114 * user provided call back function for comparisons. This implementation
115 * utilizes a ternary quicksort algorithm, and cuts over to an
116 * insertion sort for partitions involving fewer than THRESH_L records.
117 *
118 * Potential User Errors
119 * There is no return value from qsort, this function has no method
120 * of alerting the user that a sort did not work or could not work.
121 * We do not print an error message or exit the process or thread,
122 * Even if we can detect an error, We CANNOT silently return without
123 * sorting the data, if we did so the user could never be sure the
124 * sort completed successfully.
125 * It is possible we could change the return value of sort from void
126 * to int and return success or some error codes, but this gets into
127 * standards and compatibility issues.
128 *
129 * Examples of qsort parameter errors might be
130 * 1) record size (rsiz) equal to 0
131 * qsort will loop and never return.
132 * 2) record size (rsiz) less than 0
133 * rsiz is unsigned, so a negative value is insanely large
134 * 3) number of records (nrec) is 0
135 * This is legal - qsort will return without examining any records
136 * 4) number of records (nrec) is less than 0
137 * nrec is unsigned, so a negative value is insanely large.
138 * 5) nrec * rsiz > memory allocation for sort array
139 * a segment violation may occur
140 * corruption of other memory may occur
141 * 6) The base address of the sort array is invalid
142 * a segment violation may occur
143 * corruption of other memory may occur
144 * 7) The user call back function is invalid
145 * we may get alignment errors or segment violations
146 * we may jump into never-never land
147 *
148 * Some less obvious errors might be
149 * 8) The user compare function is not comparing correctly
150 * 9) The user compare function modifies the data records
151 */
152
153void
154qemu_qsort(
155 void *basep,
156 size_t nrec,
157 size_t rsiz,
158 int (*cmp)(const void *, const void *))
159{
160 size_t i; /* temporary variable */
161
162 /* variables used by swap */
163 void (*swapf)(char *, char *, size_t);
164 size_t loops;
165
166 /* variables used by sort */
167 stk_t stack[8 * sizeof (nrec) + 1];
168 stk_t *sp;
169 char *b_lim; /* bottom limit */
170 char *b_dup; /* bottom duplicate */
171 char *b_par; /* bottom partition */
172 char *t_lim; /* top limit */
173 char *t_dup; /* top duplicate */
174 char *t_par; /* top partition */
175 char *m1, *m2, *m3; /* median pointers */
176 uintptr_t d_bytelength; /* byte length of duplicate records */
177 int b_nrec;
178 int t_nrec;
179 int cv; /* results of compare (bottom / top) */
180
181 /*
182 * choose a swap function based on alignment and size
183 *
184 * The qsort function sorts an array of fixed length records.
185 * We have very limited knowledge about the data record itself.
186 * It may be that the data record is in the array we are sorting
187 * or it may be that the array contains pointers or indexes to
188 * the actual data record and all that we are sorting is the indexes.
189 *
190 * The following decision will choose an optimal swap function
191 * based on the size and alignment of the data records
192 * swapp64 will swap 64 bit pointers
193 * swapp32 will swap 32 bit pointers
194 * swapi will swap an array of 32 bit integers
195 * swapb will swap an array of 8 bit characters
196 *
197 * swapi and swapb will also require the variable loops to be set
198 * to control the length of the array being swapped
199 */
200 if ((((uintptr_t)basep & (sizeof (uint64_t) - 1)) == 0) &&
201 (rsiz == sizeof (uint64_t))) {
202 loops = 1;
203 swapf = (void (*)(char *, char *, size_t))swapp64;
204 } else if ((((uintptr_t)basep & (sizeof (uint32_t) - 1)) == 0) &&
205 (rsiz == sizeof (uint32_t))) {
206 loops = 1;
207 swapf = (void (*)(char *, char *, size_t))swapp32;
208 } else if ((((uintptr_t)basep & (sizeof (uint32_t) - 1)) == 0) &&
209 ((rsiz & (sizeof (uint32_t) - 1)) == 0)) {
210 loops = rsiz / sizeof (int);
211 swapf = (void (*)(char *, char *, size_t))swapi;
212 } else {
213 loops = rsiz;
214 swapf = swapb;
215 }
216
217 /*
218 * qsort is a partitioning sort
219 *
220 * the stack is the bookkeeping mechanism to keep track of all
221 * the partitions.
222 *
223 * each sort pass takes one partition and sorts it into two partitions.
224 * at the top of the loop we simply take the partition on the top
225 * of the stack and sort it. See the comments at the bottom
226 * of the loop regarding which partitions to add in what order.
227 *
228 * initially put the whole partition on the stack
229 */
230 sp = stack;
231 sp->b_lim = (char *)basep;
232 sp->nrec = nrec;
233 sp++;
234 while (sp > stack) {
235 sp--;
236 b_lim = sp->b_lim;
237 nrec = sp->nrec;
238
239 /*
240 * a linear insertion sort i faster than a qsort for
241 * very small number of records (THRESH_L)
242 *
243 * if number records < threshold use linear insertion sort
244 *
245 * this also handles the special case where the partition
246 * 0 or 1 records length.
247 */
248 if (nrec < THRESH_L) {
249 /*
250 * Linear insertion sort
251 */
252 t_par = b_lim;
253 for (i = 1; i < nrec; i++) {
254 t_par += rsiz;
255 b_par = t_par;
256 while (b_par > b_lim) {
257 b_par -= rsiz;
258 if ((*cmp)(b_par, b_par + rsiz) <= 0) {
259 break;
260 }
261 (*swapf)(b_par, b_par + rsiz, loops);
262 }
263 }
264
265 /*
266 * a linear insertion sort will put all records
267 * in their final position and will not create
268 * subpartitions.
269 *
270 * therefore when the insertion sort is complete
271 * just go to the top of the loop and get the
272 * next partition to sort.
273 */
274 continue;
275 }
276
277 /* quicksort */
278
279 /*
280 * choose a pivot record
281 *
282 * Ideally the pivot record will divide the partition
283 * into two equal parts. however we have to balance the
284 * work involved in selecting the pivot record with the
285 * expected benefit.
286 *
287 * The choice of pivot record depends on the number of
288 * records in the partition
289 *
290 * for small partitions (nrec < THRESH_M3)
291 * we just select the record in the middle of the partition
292 *
293 * if (nrec >= THRESH_M3 && nrec < THRESH_M9)
294 * we select three values and choose the median of 3
295 *
296 * if (nrec >= THRESH_M9)
297 * then we use an approximate median of 9
298 * 9 records are selected and grouped in 3 groups of 3
299 * the median of each of these 3 groups is fed into another
300 * median of 3 decision.
301 *
302 * Each median of 3 decision is 2 or 3 compares,
303 * so median of 9 costs between 8 and 12 compares.
304 *
305 * i is byte distance between two consecutive samples
306 * m2 will point to the pivot record
307 */
308 if (nrec < THRESH_M3) {
309 m2 = b_lim + (nrec / 2) * rsiz;
310 } else if (nrec < THRESH_M9) {
311 /* use median of 3 */
312 i = ((nrec - 1) / 2) * rsiz;
313 m2 = med3(b_lim, b_lim + i, b_lim + 2 * i);
314 } else {
315 /* approx median of 9 */
316 i = ((nrec - 1) / 8) * rsiz;
317 m1 = med3(b_lim, b_lim + i, b_lim + 2 * i);
318 m2 = med3(b_lim + 3 * i, b_lim + 4 * i, b_lim + 5 * i);
319 m3 = med3(b_lim + 6 * i, b_lim + 7 * i, b_lim + 8 * i);
320 m2 = med3(m1, m2, m3);
321 }
322
323 /*
324 * quick sort partitioning
325 *
326 * The partition limits are defined by bottom and top pointers
327 * b_lim and t_lim.
328 *
329 * qsort uses a fairly standard method of moving the
330 * partitioning pointers, b_par and t_par, to the middle of
331 * the partition and exchanging records that are in the
332 * wrong part of the partition.
333 *
334 * Two enhancements have been made to the basic algorithm.
335 * One for handling duplicate records and one to minimize
336 * the number of swaps.
337 *
338 * Two duplicate records pointers are (b_dup and t_dup) are
339 * initially set to b_lim and t_lim. Each time a record
340 * whose sort key value is equal to the pivot record is found
341 * it will be swapped with the record pointed to by
342 * b_dup or t_dup and the duplicate pointer will be
343 * incremented toward the center.
344 * When partitioning is complete, all the duplicate records
345 * will have been collected at the upper and lower limits of
346 * the partition and can easily be moved adjacent to the
347 * pivot record.
348 *
349 * The second optimization is to minimize the number of swaps.
350 * The pointer m2 points to the pivot record.
351 * During partitioning, if m2 is ever equal to the partitioning
352 * pointers, b_par or t_par, then b_par or t_par just moves
353 * onto the next record without doing a compare.
354 * If as a result of duplicate record detection,
355 * b_dup or t_dup is ever equal to m2,
356 * then m2 is changed to point to the duplicate record and
357 * b_dup or t_dup is incremented with out swapping records.
358 *
359 * When partitioning is done, we may not have the same pivot
360 * record that we started with, but we will have one with
361 * an equal sort key.
362 */
363 b_dup = b_par = b_lim;
364 t_dup = t_par = t_lim = b_lim + rsiz * (nrec - 1);
365 for (;;) {
366
367 /* move bottom pointer up */
368 for (; b_par <= t_par; b_par += rsiz) {
369 if (b_par == m2) {
370 continue;
371 }
372 cv = cmp(b_par, m2);
373 if (cv > 0) {
374 break;
375 }
376 if (cv == 0) {
377 if (b_dup == m2) {
378 m2 = b_par;
379 } else if (b_dup != b_par) {
380 (*swapf)(b_dup, b_par, loops);
381 }
382 b_dup += rsiz;
383 }
384 }
385
386 /* move top pointer down */
387 for (; b_par < t_par; t_par -= rsiz) {
388 if (t_par == m2) {
389 continue;
390 }
391 cv = cmp(t_par, m2);
392 if (cv < 0) {
393 break;
394 }
395 if (cv == 0) {
396 if (t_dup == m2) {
397 m2 = t_par;
398 } else if (t_dup != t_par) {
399 (*swapf)(t_dup, t_par, loops);
400 }
401 t_dup -= rsiz;
402 }
403 }
404
405 /* break if we are done partitioning */
406 if (b_par >= t_par) {
407 break;
408 }
409
410 /* exchange records at upper and lower break points */
411 (*swapf)(b_par, t_par, loops);
412 b_par += rsiz;
413 t_par -= rsiz;
414 }
415
416 /*
417 * partitioning is now complete
418 *
419 * there are two termination conditions from the partitioning
420 * loop above. Either b_par or t_par have crossed or
421 * they are equal.
422 *
423 * we need to swap the pivot record to its final position
424 * m2 could be in either the upper or lower partitions
425 * or it could already be in its final position
426 */
427 /*
428 * R[b_par] > R[m2]
429 * R[t_par] < R[m2]
430 */
431 if (t_par < b_par) {
432 if (m2 < t_par) {
433 (*swapf)(m2, t_par, loops);
434 m2 = b_par = t_par;
435 } else if (m2 > b_par) {
436 (*swapf)(m2, b_par, loops);
437 m2 = t_par = b_par;
438 } else {
439 b_par = t_par = m2;
440 }
441 } else {
442 if (m2 < t_par) {
443 t_par = b_par = t_par - rsiz;
444 }
445 if (m2 != b_par) {
446 (*swapf)(m2, b_par, loops);
447 }
448 m2 = t_par;
449 }
450
451 /*
452 * move bottom duplicates next to pivot
453 * optimized to eliminate overlap
454 */
455 d_bytelength = b_dup - b_lim;
456 if (b_par - b_dup < d_bytelength) {
457 b_dup = b_lim + (b_par - b_dup);
458 }
459 while (b_dup > b_lim) {
460 b_dup -= rsiz;
461 b_par -= rsiz;
462 (*swapf)(b_dup, b_par, loops);
463 }
464 b_par = m2 - d_bytelength;
465
466 /*
467 * move top duplicates next to pivot
468 */
469 d_bytelength = t_lim - t_dup;
470 if (t_dup - t_par < d_bytelength) {
471 t_dup = t_lim - (t_dup - t_par);
472 }
473 while (t_dup < t_lim) {
474 t_dup += rsiz;
475 t_par += rsiz;
476 (*swapf)(t_dup, t_par, loops);
477 }
478 t_par = m2 + d_bytelength;
479
480 /*
481 * when a qsort pass completes there are three partitions
482 * 1) the lower contains all records less than pivot
483 * 2) the upper contains all records greater than pivot
484 * 3) the pivot partition contains all record equal to pivot
485 *
486 * all records in the pivot partition are in their final
487 * position and do not need to be accounted for by the stack
488 *
489 * when adding partitions to the stack
490 * it is important to add the largest partition first
491 * to prevent stack overflow.
492 *
493 * calculate number of unsorted records in top and bottom
494 * push resulting partitions on stack
495 */
496 b_nrec = (b_par - b_lim) / rsiz;
497 t_nrec = (t_lim - t_par) / rsiz;
498 if (b_nrec < t_nrec) {
499 sp->b_lim = t_par + rsiz;
500 sp->nrec = t_nrec;
501 sp++;
502 sp->b_lim = b_lim;
503 sp->nrec = b_nrec;
504 sp++;
505 } else {
506 sp->b_lim = b_lim;
507 sp->nrec = b_nrec;
508 sp++;
509 sp->b_lim = t_par + rsiz;
510 sp->nrec = t_nrec;
511 sp++;
512 }
513 }
514}
515
516#endif
517void pstrcpy(char *buf, int buf_size, const char *str)
518{
519 int c;
520 char *q = buf;
521
522 if (buf_size <= 0)
523 return;
524
525 for(;;) {
526 c = *str++;
527 if (c == 0 || q >= buf + buf_size - 1)
528 break;
529 *q++ = c;
530 }
531 *q = '\0';
532}
533
534/* strcat and truncate. */
535char *pstrcat(char *buf, int buf_size, const char *s)
536{
537 int len;
538 len = strlen(buf);
539 if (len < buf_size)
540 pstrcpy(buf + len, buf_size - len, s);
541 return buf;
542}
543
544int strstart(const char *str, const char *val, const char **ptr)
545{
546 const char *p, *q;
547 p = str;
548 q = val;
549 while (*q != '\0') {
550 if (*p != *q)
551 return 0;
552 p++;
553 q++;
554 }
555 if (ptr)
556 *ptr = p;
557 return 1;
558}
559
560int stristart(const char *str, const char *val, const char **ptr)
561{
562 const char *p, *q;
563 p = str;
564 q = val;
565 while (*q != '\0') {
566 if (toupper(*p) != toupper(*q))
567 return 0;
568 p++;
569 q++;
570 }
571 if (ptr)
572 *ptr = p;
573 return 1;
574}
575
576#ifndef VBOX
577time_t mktimegm(struct tm *tm)
578{
579 time_t t;
580 int y = tm->tm_year + 1900, m = tm->tm_mon + 1, d = tm->tm_mday;
581 if (m < 3) {
582 m += 12;
583 y--;
584 }
585 t = 86400 * (d + (153 * m - 457) / 5 + 365 * y + y / 4 - y / 100 +
586 y / 400 - 719469);
587 t += 3600 * tm->tm_hour + 60 * tm->tm_min + tm->tm_sec;
588 return t;
589}
590#endif
Note: See TracBrowser for help on using the repository browser.

© 2023 Oracle
Contact – Privacy policy – Terms of Use