VirtualBox

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

Last change on this file since 78278 was 69465, checked in by vboxsync, 7 years ago

recompiler: scm updates

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id Revision
File size: 19.5 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#include "host-utils.h"
26
27#ifdef VBOX
28# include "osdep.h"
29
30
31static inline int toupper(int ch) {
32 if ( (unsigned int)(ch - 'a') < 26u )
33 ch += 'A' - 'a';
34 return ch;
35}
36
37/* Quick sort from OpenSolaris:
38 http://src.opensolaris.org/source/raw/onnv/onnv-gate/usr/src/common/util/qsort.c */
39/*
40 * choose a median of 3 values
41 *
42 * note: cstyle specifically prohibits nested conditional operators
43 * but this is the only way to do the median of 3 function in-line
44 */
45#define med3(a, b, c) (cmp((a), (b)) < 0) \
46 ? ((cmp((b), (c)) < 0) ? (b) : (cmp((a), (c)) < 0) ? (c) : (a)) \
47 : ((cmp((b), (c)) > 0) ? (b) : (cmp((a), (c)) > 0) ? (c) : (a))
48
49#define THRESH_L 5 /* threshold for insertion sort */
50#define THRESH_M3 20 /* threshold for median of 3 */
51#define THRESH_M9 50 /* threshold for median of 9 */
52
53typedef struct {
54 char *b_lim;
55 size_t nrec;
56} stk_t;
57
58/*
59 * The following swap functions should not create a stack frame
60 * the SPARC call / return instruction will be executed
61 * but the a save / restore will not be executed
62 * which means we won't do a window turn with the spill / fill overhead
63 * verify this by examining the assembly code
64 */
65
66/* ARGSUSED */
67static void
68swapp32(uint32_t *r1, uint32_t *r2, size_t cnt)
69{
70 uint32_t temp;
71
72 temp = *r1;
73 *r1++ = *r2;
74 *r2++ = temp;
75}
76
77/* ARGSUSED */
78static void
79swapp64(uint64_t *r1, uint64_t *r2, size_t cnt)
80{
81 uint64_t temp;
82
83 temp = *r1;
84 *r1++ = *r2;
85 *r2++ = temp;
86}
87
88static void
89swapi(uint32_t *r1, uint32_t *r2, size_t cnt)
90{
91 uint32_t temp;
92
93 /* character by character */
94 while (cnt--) {
95 temp = *r1;
96 *r1++ = *r2;
97 *r2++ = temp;
98 }
99}
100
101static void
102swapb(char *r1, char *r2, size_t cnt)
103{
104 char temp;
105
106 /* character by character */
107 while (cnt--) {
108 temp = *r1;
109 *r1++ = *r2;
110 *r2++ = temp;
111 }
112}
113
114/*
115 * qsort() is a general purpose, in-place sorting routine using a
116 * user provided call back function for comparisons. This implementation
117 * utilizes a ternary quicksort algorithm, and cuts over to an
118 * insertion sort for partitions involving fewer than THRESH_L records.
119 *
120 * Potential User Errors
121 * There is no return value from qsort, this function has no method
122 * of alerting the user that a sort did not work or could not work.
123 * We do not print an error message or exit the process or thread,
124 * Even if we can detect an error, We CANNOT silently return without
125 * sorting the data, if we did so the user could never be sure the
126 * sort completed successfully.
127 * It is possible we could change the return value of sort from void
128 * to int and return success or some error codes, but this gets into
129 * standards and compatibility issues.
130 *
131 * Examples of qsort parameter errors might be
132 * 1) record size (rsiz) equal to 0
133 * qsort will loop and never return.
134 * 2) record size (rsiz) less than 0
135 * rsiz is unsigned, so a negative value is insanely large
136 * 3) number of records (nrec) is 0
137 * This is legal - qsort will return without examining any records
138 * 4) number of records (nrec) is less than 0
139 * nrec is unsigned, so a negative value is insanely large.
140 * 5) nrec * rsiz > memory allocation for sort array
141 * a segment violation may occur
142 * corruption of other memory may occur
143 * 6) The base address of the sort array is invalid
144 * a segment violation may occur
145 * corruption of other memory may occur
146 * 7) The user call back function is invalid
147 * we may get alignment errors or segment violations
148 * we may jump into never-never land
149 *
150 * Some less obvious errors might be
151 * 8) The user compare function is not comparing correctly
152 * 9) The user compare function modifies the data records
153 */
154
155void
156qemu_qsort(
157 void *basep,
158 size_t nrec,
159 size_t rsiz,
160 int (*cmp)(const void *, const void *))
161{
162 size_t i; /* temporary variable */
163
164 /* variables used by swap */
165 void (*swapf)(char *, char *, size_t);
166 size_t loops;
167
168 /* variables used by sort */
169 stk_t stack[8 * sizeof (nrec) + 1];
170 stk_t *sp;
171 char *b_lim; /* bottom limit */
172 char *b_dup; /* bottom duplicate */
173 char *b_par; /* bottom partition */
174 char *t_lim; /* top limit */
175 char *t_dup; /* top duplicate */
176 char *t_par; /* top partition */
177 char *m1, *m2, *m3; /* median pointers */
178 uintptr_t d_bytelength; /* byte length of duplicate records */
179 int b_nrec;
180 int t_nrec;
181 int cv; /* results of compare (bottom / top) */
182
183 /*
184 * choose a swap function based on alignment and size
185 *
186 * The qsort function sorts an array of fixed length records.
187 * We have very limited knowledge about the data record itself.
188 * It may be that the data record is in the array we are sorting
189 * or it may be that the array contains pointers or indexes to
190 * the actual data record and all that we are sorting is the indexes.
191 *
192 * The following decision will choose an optimal swap function
193 * based on the size and alignment of the data records
194 * swapp64 will swap 64 bit pointers
195 * swapp32 will swap 32 bit pointers
196 * swapi will swap an array of 32 bit integers
197 * swapb will swap an array of 8 bit characters
198 *
199 * swapi and swapb will also require the variable loops to be set
200 * to control the length of the array being swapped
201 */
202 if ((((uintptr_t)basep & (sizeof (uint64_t) - 1)) == 0) &&
203 (rsiz == sizeof (uint64_t))) {
204 loops = 1;
205 swapf = (void (*)(char *, char *, size_t))swapp64;
206 } else if ((((uintptr_t)basep & (sizeof (uint32_t) - 1)) == 0) &&
207 (rsiz == sizeof (uint32_t))) {
208 loops = 1;
209 swapf = (void (*)(char *, char *, size_t))swapp32;
210 } else if ((((uintptr_t)basep & (sizeof (uint32_t) - 1)) == 0) &&
211 ((rsiz & (sizeof (uint32_t) - 1)) == 0)) {
212 loops = rsiz / sizeof (int);
213 swapf = (void (*)(char *, char *, size_t))swapi;
214 } else {
215 loops = rsiz;
216 swapf = swapb;
217 }
218
219 /*
220 * qsort is a partitioning sort
221 *
222 * the stack is the bookkeeping mechanism to keep track of all
223 * the partitions.
224 *
225 * each sort pass takes one partition and sorts it into two partitions.
226 * at the top of the loop we simply take the partition on the top
227 * of the stack and sort it. See the comments at the bottom
228 * of the loop regarding which partitions to add in what order.
229 *
230 * initially put the whole partition on the stack
231 */
232 sp = stack;
233 sp->b_lim = (char *)basep;
234 sp->nrec = nrec;
235 sp++;
236 while (sp > stack) {
237 sp--;
238 b_lim = sp->b_lim;
239 nrec = sp->nrec;
240
241 /*
242 * a linear insertion sort i faster than a qsort for
243 * very small number of records (THRESH_L)
244 *
245 * if number records < threshold use linear insertion sort
246 *
247 * this also handles the special case where the partition
248 * 0 or 1 records length.
249 */
250 if (nrec < THRESH_L) {
251 /*
252 * Linear insertion sort
253 */
254 t_par = b_lim;
255 for (i = 1; i < nrec; i++) {
256 t_par += rsiz;
257 b_par = t_par;
258 while (b_par > b_lim) {
259 b_par -= rsiz;
260 if ((*cmp)(b_par, b_par + rsiz) <= 0) {
261 break;
262 }
263 (*swapf)(b_par, b_par + rsiz, loops);
264 }
265 }
266
267 /*
268 * a linear insertion sort will put all records
269 * in their final position and will not create
270 * subpartitions.
271 *
272 * therefore when the insertion sort is complete
273 * just go to the top of the loop and get the
274 * next partition to sort.
275 */
276 continue;
277 }
278
279 /* quicksort */
280
281 /*
282 * choose a pivot record
283 *
284 * Ideally the pivot record will divide the partition
285 * into two equal parts. however we have to balance the
286 * work involved in selecting the pivot record with the
287 * expected benefit.
288 *
289 * The choice of pivot record depends on the number of
290 * records in the partition
291 *
292 * for small partitions (nrec < THRESH_M3)
293 * we just select the record in the middle of the partition
294 *
295 * if (nrec >= THRESH_M3 && nrec < THRESH_M9)
296 * we select three values and choose the median of 3
297 *
298 * if (nrec >= THRESH_M9)
299 * then we use an approximate median of 9
300 * 9 records are selected and grouped in 3 groups of 3
301 * the median of each of these 3 groups is fed into another
302 * median of 3 decision.
303 *
304 * Each median of 3 decision is 2 or 3 compares,
305 * so median of 9 costs between 8 and 12 compares.
306 *
307 * i is byte distance between two consecutive samples
308 * m2 will point to the pivot record
309 */
310 if (nrec < THRESH_M3) {
311 m2 = b_lim + (nrec / 2) * rsiz;
312 } else if (nrec < THRESH_M9) {
313 /* use median of 3 */
314 i = ((nrec - 1) / 2) * rsiz;
315 m2 = med3(b_lim, b_lim + i, b_lim + 2 * i);
316 } else {
317 /* approx median of 9 */
318 i = ((nrec - 1) / 8) * rsiz;
319 m1 = med3(b_lim, b_lim + i, b_lim + 2 * i);
320 m2 = med3(b_lim + 3 * i, b_lim + 4 * i, b_lim + 5 * i);
321 m3 = med3(b_lim + 6 * i, b_lim + 7 * i, b_lim + 8 * i);
322 m2 = med3(m1, m2, m3);
323 }
324
325 /*
326 * quick sort partitioning
327 *
328 * The partition limits are defined by bottom and top pointers
329 * b_lim and t_lim.
330 *
331 * qsort uses a fairly standard method of moving the
332 * partitioning pointers, b_par and t_par, to the middle of
333 * the partition and exchanging records that are in the
334 * wrong part of the partition.
335 *
336 * Two enhancements have been made to the basic algorithm.
337 * One for handling duplicate records and one to minimize
338 * the number of swaps.
339 *
340 * Two duplicate records pointers are (b_dup and t_dup) are
341 * initially set to b_lim and t_lim. Each time a record
342 * whose sort key value is equal to the pivot record is found
343 * it will be swapped with the record pointed to by
344 * b_dup or t_dup and the duplicate pointer will be
345 * incremented toward the center.
346 * When partitioning is complete, all the duplicate records
347 * will have been collected at the upper and lower limits of
348 * the partition and can easily be moved adjacent to the
349 * pivot record.
350 *
351 * The second optimization is to minimize the number of swaps.
352 * The pointer m2 points to the pivot record.
353 * During partitioning, if m2 is ever equal to the partitioning
354 * pointers, b_par or t_par, then b_par or t_par just moves
355 * onto the next record without doing a compare.
356 * If as a result of duplicate record detection,
357 * b_dup or t_dup is ever equal to m2,
358 * then m2 is changed to point to the duplicate record and
359 * b_dup or t_dup is incremented with out swapping records.
360 *
361 * When partitioning is done, we may not have the same pivot
362 * record that we started with, but we will have one with
363 * an equal sort key.
364 */
365 b_dup = b_par = b_lim;
366 t_dup = t_par = t_lim = b_lim + rsiz * (nrec - 1);
367 for (;;) {
368
369 /* move bottom pointer up */
370 for (; b_par <= t_par; b_par += rsiz) {
371 if (b_par == m2) {
372 continue;
373 }
374 cv = cmp(b_par, m2);
375 if (cv > 0) {
376 break;
377 }
378 if (cv == 0) {
379 if (b_dup == m2) {
380 m2 = b_par;
381 } else if (b_dup != b_par) {
382 (*swapf)(b_dup, b_par, loops);
383 }
384 b_dup += rsiz;
385 }
386 }
387
388 /* move top pointer down */
389 for (; b_par < t_par; t_par -= rsiz) {
390 if (t_par == m2) {
391 continue;
392 }
393 cv = cmp(t_par, m2);
394 if (cv < 0) {
395 break;
396 }
397 if (cv == 0) {
398 if (t_dup == m2) {
399 m2 = t_par;
400 } else if (t_dup != t_par) {
401 (*swapf)(t_dup, t_par, loops);
402 }
403 t_dup -= rsiz;
404 }
405 }
406
407 /* break if we are done partitioning */
408 if (b_par >= t_par) {
409 break;
410 }
411
412 /* exchange records at upper and lower break points */
413 (*swapf)(b_par, t_par, loops);
414 b_par += rsiz;
415 t_par -= rsiz;
416 }
417
418 /*
419 * partitioning is now complete
420 *
421 * there are two termination conditions from the partitioning
422 * loop above. Either b_par or t_par have crossed or
423 * they are equal.
424 *
425 * we need to swap the pivot record to its final position
426 * m2 could be in either the upper or lower partitions
427 * or it could already be in its final position
428 */
429 /*
430 * R[b_par] > R[m2]
431 * R[t_par] < R[m2]
432 */
433 if (t_par < b_par) {
434 if (m2 < t_par) {
435 (*swapf)(m2, t_par, loops);
436 m2 = b_par = t_par;
437 } else if (m2 > b_par) {
438 (*swapf)(m2, b_par, loops);
439 m2 = t_par = b_par;
440 } else {
441 b_par = t_par = m2;
442 }
443 } else {
444 if (m2 < t_par) {
445 t_par = b_par = t_par - rsiz;
446 }
447 if (m2 != b_par) {
448 (*swapf)(m2, b_par, loops);
449 }
450 m2 = t_par;
451 }
452
453 /*
454 * move bottom duplicates next to pivot
455 * optimized to eliminate overlap
456 */
457 d_bytelength = b_dup - b_lim;
458 if (b_par - b_dup < d_bytelength) {
459 b_dup = b_lim + (b_par - b_dup);
460 }
461 while (b_dup > b_lim) {
462 b_dup -= rsiz;
463 b_par -= rsiz;
464 (*swapf)(b_dup, b_par, loops);
465 }
466 b_par = m2 - d_bytelength;
467
468 /*
469 * move top duplicates next to pivot
470 */
471 d_bytelength = t_lim - t_dup;
472 if (t_dup - t_par < d_bytelength) {
473 t_dup = t_lim - (t_dup - t_par);
474 }
475 while (t_dup < t_lim) {
476 t_dup += rsiz;
477 t_par += rsiz;
478 (*swapf)(t_dup, t_par, loops);
479 }
480 t_par = m2 + d_bytelength;
481
482 /*
483 * when a qsort pass completes there are three partitions
484 * 1) the lower contains all records less than pivot
485 * 2) the upper contains all records greater than pivot
486 * 3) the pivot partition contains all record equal to pivot
487 *
488 * all records in the pivot partition are in their final
489 * position and do not need to be accounted for by the stack
490 *
491 * when adding partitions to the stack
492 * it is important to add the largest partition first
493 * to prevent stack overflow.
494 *
495 * calculate number of unsorted records in top and bottom
496 * push resulting partitions on stack
497 */
498 b_nrec = (b_par - b_lim) / rsiz;
499 t_nrec = (t_lim - t_par) / rsiz;
500 if (b_nrec < t_nrec) {
501 sp->b_lim = t_par + rsiz;
502 sp->nrec = t_nrec;
503 sp++;
504 sp->b_lim = b_lim;
505 sp->nrec = b_nrec;
506 sp++;
507 } else {
508 sp->b_lim = b_lim;
509 sp->nrec = b_nrec;
510 sp++;
511 sp->b_lim = t_par + rsiz;
512 sp->nrec = t_nrec;
513 sp++;
514 }
515 }
516}
517
518#endif /* VBOX */
519
520void pstrcpy(char *buf, int buf_size, const char *str)
521{
522 int c;
523 char *q = buf;
524
525 if (buf_size <= 0)
526 return;
527
528 for(;;) {
529 c = *str++;
530 if (c == 0 || q >= buf + buf_size - 1)
531 break;
532 *q++ = c;
533 }
534 *q = '\0';
535}
536
537/* strcat and truncate. */
538char *pstrcat(char *buf, int buf_size, const char *s)
539{
540 int len;
541 len = strlen(buf);
542 if (len < buf_size)
543 pstrcpy(buf + len, buf_size - len, s);
544 return buf;
545}
546
547int strstart(const char *str, const char *val, const char **ptr)
548{
549 const char *p, *q;
550 p = str;
551 q = val;
552 while (*q != '\0') {
553 if (*p != *q)
554 return 0;
555 p++;
556 q++;
557 }
558 if (ptr)
559 *ptr = p;
560 return 1;
561}
562
563int stristart(const char *str, const char *val, const char **ptr)
564{
565 const char *p, *q;
566 p = str;
567 q = val;
568 while (*q != '\0') {
569 if (qemu_toupper(*p) != qemu_toupper(*q))
570 return 0;
571 p++;
572 q++;
573 }
574 if (ptr)
575 *ptr = p;
576 return 1;
577}
578
579/* XXX: use host strnlen if available ? */
580int qemu_strnlen(const char *s, int max_len)
581{
582 int i;
583
584 for(i = 0; i < max_len; i++) {
585 if (s[i] == '\0') {
586 break;
587 }
588 }
589 return i;
590}
591
592#ifndef VBOX
593time_t mktimegm(struct tm *tm)
594{
595 time_t t;
596 int y = tm->tm_year + 1900, m = tm->tm_mon + 1, d = tm->tm_mday;
597 if (m < 3) {
598 m += 12;
599 y--;
600 }
601 t = 86400 * (d + (153 * m - 457) / 5 + 365 * y + y / 4 - y / 100 +
602 y / 400 - 719469);
603 t += 3600 * tm->tm_hour + 60 * tm->tm_min + tm->tm_sec;
604 return t;
605}
606#endif /* !VBOX */
607
608int qemu_fls(int i)
609{
610 return 32 - clz32(i);
611}
612
613#ifndef VBOX
614
615/*
616 * Make sure data goes on disk, but if possible do not bother to
617 * write out the inode just for timestamp updates.
618 *
619 * Unfortunately even in 2009 many operating systems do not support
620 * fdatasync and have to fall back to fsync.
621 */
622int qemu_fdatasync(int fd)
623{
624#ifdef CONFIG_FDATASYNC
625 return fdatasync(fd);
626#else
627 return fsync(fd);
628#endif
629}
630
631/* io vectors */
632
633void qemu_iovec_init(QEMUIOVector *qiov, int alloc_hint)
634{
635 qiov->iov = qemu_malloc(alloc_hint * sizeof(struct iovec));
636 qiov->niov = 0;
637 qiov->nalloc = alloc_hint;
638 qiov->size = 0;
639}
640
641void qemu_iovec_init_external(QEMUIOVector *qiov, struct iovec *iov, int niov)
642{
643 int i;
644
645 qiov->iov = iov;
646 qiov->niov = niov;
647 qiov->nalloc = -1;
648 qiov->size = 0;
649 for (i = 0; i < niov; i++)
650 qiov->size += iov[i].iov_len;
651}
652
653void qemu_iovec_add(QEMUIOVector *qiov, void *base, size_t len)
654{
655 assert(qiov->nalloc != -1);
656
657 if (qiov->niov == qiov->nalloc) {
658 qiov->nalloc = 2 * qiov->nalloc + 1;
659 qiov->iov = qemu_realloc(qiov->iov, qiov->nalloc * sizeof(struct iovec));
660 }
661 qiov->iov[qiov->niov].iov_base = base;
662 qiov->iov[qiov->niov].iov_len = len;
663 qiov->size += len;
664 ++qiov->niov;
665}
666
667/*
668 * Copies iovecs from src to the end dst until src is completely copied or the
669 * total size of the copied iovec reaches size. The size of the last copied
670 * iovec is changed in order to fit the specified total size if it isn't a
671 * perfect fit already.
672 */
673void qemu_iovec_concat(QEMUIOVector *dst, QEMUIOVector *src, size_t size)
674{
675 int i;
676 size_t done;
677
678 assert(dst->nalloc != -1);
679
680 done = 0;
681 for (i = 0; (i < src->niov) && (done != size); i++) {
682 if (done + src->iov[i].iov_len > size) {
683 qemu_iovec_add(dst, src->iov[i].iov_base, size - done);
684 break;
685 } else {
686 qemu_iovec_add(dst, src->iov[i].iov_base, src->iov[i].iov_len);
687 }
688 done += src->iov[i].iov_len;
689 }
690}
691
692void qemu_iovec_destroy(QEMUIOVector *qiov)
693{
694 assert(qiov->nalloc != -1);
695
696 qemu_free(qiov->iov);
697}
698
699void qemu_iovec_reset(QEMUIOVector *qiov)
700{
701 assert(qiov->nalloc != -1);
702
703 qiov->niov = 0;
704 qiov->size = 0;
705}
706
707void qemu_iovec_to_buffer(QEMUIOVector *qiov, void *buf)
708{
709 uint8_t *p = (uint8_t *)buf;
710 int i;
711
712 for (i = 0; i < qiov->niov; ++i) {
713 memcpy(p, qiov->iov[i].iov_base, qiov->iov[i].iov_len);
714 p += qiov->iov[i].iov_len;
715 }
716}
717
718void qemu_iovec_from_buffer(QEMUIOVector *qiov, const void *buf, size_t count)
719{
720 const uint8_t *p = (const uint8_t *)buf;
721 size_t copy;
722 int i;
723
724 for (i = 0; i < qiov->niov && count; ++i) {
725 copy = count;
726 if (copy > qiov->iov[i].iov_len)
727 copy = qiov->iov[i].iov_len;
728 memcpy(qiov->iov[i].iov_base, p, copy);
729 p += copy;
730 count -= copy;
731 }
732}
733
734#ifndef _WIN32
735/* Sets a specific flag */
736int fcntl_setfl(int fd, int flag)
737{
738 int flags;
739
740 flags = fcntl(fd, F_GETFL);
741 if (flags == -1)
742 return -errno;
743
744 if (fcntl(fd, F_SETFL, flags | flag) == -1)
745 return -errno;
746
747 return 0;
748}
749#endif
750
751#endif /* !VBOX */
752
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette