util.c

   1 /**********************************************************************
   2
   3   util.c -
   4
   5   $Author$
   6   created at: Fri Mar 10 17:22:34 JST 1995
   7
   8   Copyright (C) 1993-2008 Yukihiro Matsumoto
   9
  10 **********************************************************************/
  11
  12 #if defined __MINGW32__ || defined __MINGW64__
  13 # define MINGW_HAS_SECURE_API 1
  14 #endif
  15
  16 #ifndef __STDC_WANT_LIB_EXT1__
  17 #define __STDC_WANT_LIB_EXT1__ 1 /* for qsort_s() */
  18 #endif
  19
  20 #include "ruby/internal/config.h"
  21
  22 #include <ctype.h>
  23 #include <errno.h>
  24 #include <float.h>
  25 #include <math.h>
  26 #include <stdio.h>
  27
  28 #ifdef _WIN32
  29 # include "missing/file.h"
  30 #endif
  31
  32 #include "internal.h"
  33 #include "internal/sanitizers.h"
  34 #include "internal/util.h"
  35 #include "ruby/util.h"
  36 #include "ruby_atomic.h"
  37
  38 const char ruby_hexdigits[] = "0123456789abcdef0123456789ABCDEF";
  39 #define hexdigit ruby_hexdigits
  40
  41 unsigned long
  42 ruby_scan_oct(const char *start, size_t len, size_t *retlen)
  43 {
  44     register const char *s = start;
  45     register unsigned long retval = 0;
  46     size_t i;
  47
  48     for (i = 0; i < len; i++) {
  49         if ((s[0] < '0') || ('7' < s[0])) {
  50             break;
  51         }
  52         retval <<= 3;
  53         retval |= *s++ - '0';
  54     }
  55     *retlen = (size_t)(s - start);
  56     return retval;
  57 }
  58
  59 unsigned long
  60 ruby_scan_hex(const char *start, size_t len, size_t *retlen)
  61 {
  62     register const char *s = start;
  63     register unsigned long retval = 0;
  64     signed char d;
  65     size_t i = 0;
  66
  67     for (i = 0; i < len; i++) {
  68         d = ruby_digit36_to_number_table[(unsigned char)*s];
  69         if (d < 0 || 15 < d) {
  70             break;
  71         }
  72         retval <<= 4;
  73         retval |= d;
  74         s++;
  75     }
  76     *retlen = (size_t)(s - start);
  77     return retval;
  78 }
  79
  80 const signed char ruby_digit36_to_number_table[] = {
  81     /*     0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f */
  82     /*0*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  83     /*1*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  84     /*2*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  85     /*3*/  0, 1, 2, 3, 4, 5, 6, 7, 8, 9,-1,-1,-1,-1,-1,-1,
  86     /*4*/ -1,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,
  87     /*5*/ 25,26,27,28,29,30,31,32,33,34,35,-1,-1,-1,-1,-1,
  88     /*6*/ -1,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,
  89     /*7*/ 25,26,27,28,29,30,31,32,33,34,35,-1,-1,-1,-1,-1,
  90     /*8*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  91     /*9*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  92     /*a*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  93     /*b*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  94     /*c*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  95     /*d*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  96     /*e*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  97     /*f*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  98 };
  99
 100 NO_SANITIZE("unsigned-integer-overflow", extern unsigned long ruby_scan_digits(const char *str, ssize_t len, int base, size_t *retlen, int *overflow));
 101 unsigned long
 102 ruby_scan_digits(const char *str, ssize_t len, int base, size_t *retlen, int *overflow)
 103 {
 104     RBIMPL_ASSERT_OR_ASSUME(base >= 2);
 105     RBIMPL_ASSERT_OR_ASSUME(base <= 36);
 106
 107     const char *start = str;
 108     unsigned long ret = 0, x;
 109     unsigned long mul_overflow = (~(unsigned long)0) / base;
 110
 111     *overflow = 0;
 112
 113     if (!len) {
 114         *retlen = 0;
 115         return 0;
 116     }
 117
 118     do {
 119         int d = ruby_digit36_to_number_table[(unsigned char)*str++];
 120         if (d == -1 || base <= d) {
 121             --str;
 122             break;
 123         }
 124         if (mul_overflow < ret)
 125             *overflow = 1;
 126         ret *= base;
 127         x = ret;
 128         ret += d;
 129         if (ret < x)
 130             *overflow = 1;
 131     } while (len < 0 || --len);
 132     *retlen = str - start;
 133     return ret;
 134 }
 135
 136 unsigned long
 137 ruby_strtoul(const char *str, char **endptr, int base)
 138 {
 139     int c, b, overflow;
 140     int sign = 0;
 141     size_t len;
 142     unsigned long ret;
 143     const char *subject_found = str;
 144
 145     if (base < 0) {
 146         errno = EINVAL;
 147         return 0;
 148     }
 149
 150     if (base == 1 || 36 < base) {
 151         errno = EINVAL;
 152         return 0;
 153     }
 154
 155     while ((c = *str) && ISSPACE(c))
 156         str++;
 157
 158     if (c == '+') {
 159         sign = 1;
 160         str++;
 161     }
 162     else if (c == '-') {
 163         sign = -1;
 164         str++;
 165     }
 166
 167     if (str[0] == '0') {
 168         subject_found = str+1;
 169         if (base == 0 || base == 16) {
 170             if (str[1] == 'x' || str[1] == 'X') {
 171                 b = 16;
 172                 str += 2;
 173             }
 174             else {
 175                 b = base == 0 ? 8 : 16;
 176                 str++;
 177             }
 178         }
 179         else {
 180             b = base;
 181             str++;
 182         }
 183     }
 184     else {
 185         b = base == 0 ? 10 : base;
 186     }
 187
 188     ret = ruby_scan_digits(str, -1, b, &len, &overflow);
 189
 190     if (0 < len)
 191         subject_found = str+len;
 192
 193     if (endptr)
 194         *endptr = (char*)subject_found;
 195
 196     if (overflow) {
 197         errno = ERANGE;
 198         return ULONG_MAX;
 199     }
 200
 201     if (sign < 0) {
 202         ret = (unsigned long)(-(long)ret);
 203         return ret;
 204     }
 205     else {
 206         return ret;
 207     }
 208 }
 209
 210 #if !defined HAVE_GNU_QSORT_R
 211 #include <sys/types.h>
 212 #include <stdint.h>
 213 #ifdef HAVE_UNISTD_H
 214 #include <unistd.h>
 215 #endif
 216
 217 typedef int (cmpfunc_t)(const void*, const void*, void*);
 218
 219 #if defined HAVE_QSORT_S && defined RUBY_MSVCRT_VERSION
 220 /* In contrast to its name, Visual Studio qsort_s is incompatible with
 221  * C11 in the order of the comparison function's arguments, and same
 222  * as BSD qsort_r rather. */
 223 # define qsort_r(base, nel, size, arg, cmp) qsort_s(base, nel, size, cmp, arg)
 224 # define cmp_bsd_qsort cmp_ms_qsort
 225 # define HAVE_BSD_QSORT_R 1
 226 #endif
 227
 228 #if defined HAVE_BSD_QSORT_R
 229 struct bsd_qsort_r_args {
 230     cmpfunc_t *cmp;
 231     void *arg;
 232 };
 233
 234 static int
 235 cmp_bsd_qsort(void *d, const void *a, const void *b)
 236 {
 237     const struct bsd_qsort_r_args *args = d;
 238     return (*args->cmp)(a, b, args->arg);
 239 }
 240
 241 void
 242 ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d)
 243 {
 244     struct bsd_qsort_r_args args;
 245     args.cmp = cmp;
 246     args.arg = d;
 247     qsort_r(base, nel, size, &args, cmp_bsd_qsort);
 248 }
 249 #elif defined HAVE_QSORT_S
 250 /* C11 qsort_s has the same arguments as GNU's, but uses
 251  * runtime-constraints handler. */
 252 void
 253 ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d)
 254 {
 255     if (!nel || !size) return;  /* nothing to sort */
 256
 257     /* get rid of runtime-constraints handler for MT-safeness */
 258     if (!base || !cmp) return;
 259     if (nel > RSIZE_MAX || size > RSIZE_MAX) return;
 260
 261     qsort_s(base, nel, size, cmp, d);
 262 }
 263 # define HAVE_GNU_QSORT_R 1
 264 #else
 265 /* mm.c */
 266
 267 #define mmtype long
 268 #define mmcount (16 / SIZEOF_LONG)
 269 #define A ((mmtype*)a)
 270 #define B ((mmtype*)b)
 271 #define C ((mmtype*)c)
 272 #define D ((mmtype*)d)
 273
 274 #define mmstep (sizeof(mmtype) * mmcount)
 275 #define mmprepare(base, size) do {\
 276  if (((VALUE)(base) % sizeof(mmtype)) == 0 && ((size) % sizeof(mmtype)) == 0) \
 277    if ((size) >= mmstep) mmkind = 1;\
 278    else              mmkind = 0;\
 279  else                mmkind = -1;\
 280  high = ((size) / mmstep) * mmstep;\
 281  low  = ((size) % mmstep);\
 282 } while (0)\
 283
 284 #define mmarg mmkind, size, high, low
 285 #define mmargdecl int mmkind, size_t size, size_t high, size_t low
 286
 287 static void mmswap_(register char *a, register char *b, mmargdecl)
 288 {
 289  if (a == b) return;
 290  if (mmkind >= 0) {
 291    register mmtype s;
 292 #if mmcount > 1
 293    if (mmkind > 0) {
 294      register char *t = a + high;
 295      do {
 296        s = A[0]; A[0] = B[0]; B[0] = s;
 297        s = A[1]; A[1] = B[1]; B[1] = s;
 298 #if mmcount > 2
 299        s = A[2]; A[2] = B[2]; B[2] = s;
 300 #if mmcount > 3
 301        s = A[3]; A[3] = B[3]; B[3] = s;
 302 #endif
 303 #endif
 304        a += mmstep; b += mmstep;
 305      } while (a < t);
 306    }
 307 #endif
 308    if (low != 0) { s = A[0]; A[0] = B[0]; B[0] = s;
 309 #if mmcount > 2
 310      if (low >= 2 * sizeof(mmtype)) { s = A[1]; A[1] = B[1]; B[1] = s;
 311 #if mmcount > 3
 312        if (low >= 3 * sizeof(mmtype)) {s = A[2]; A[2] = B[2]; B[2] = s;}
 313 #endif
 314      }
 315 #endif
 316    }
 317  }
 318  else {
 319    register char *t = a + size, s;
 320    do {s = *a; *a++ = *b; *b++ = s;} while (a < t);
 321  }
 322 }
 323 #define mmswap(a,b) mmswap_((a),(b),mmarg)
 324
 325 /* a, b, c = b, c, a */
 326 static void mmrot3_(register char *a, register char *b, register char *c, mmargdecl)
 327 {
 328  if (mmkind >= 0) {
 329    register mmtype s;
 330 #if mmcount > 1
 331    if (mmkind > 0) {
 332      register char *t = a + high;
 333      do {
 334        s = A[0]; A[0] = B[0]; B[0] = C[0]; C[0] = s;
 335        s = A[1]; A[1] = B[1]; B[1] = C[1]; C[1] = s;
 336 #if mmcount > 2
 337        s = A[2]; A[2] = B[2]; B[2] = C[2]; C[2] = s;
 338 #if mmcount > 3
 339        s = A[3]; A[3] = B[3]; B[3] = C[3]; C[3] = s;
 340 #endif
 341 #endif
 342        a += mmstep; b += mmstep; c += mmstep;
 343      } while (a < t);
 344    }
 345 #endif
 346    if (low != 0) { s = A[0]; A[0] = B[0]; B[0] = C[0]; C[0] = s;
 347 #if mmcount > 2
 348      if (low >= 2 * sizeof(mmtype)) { s = A[1]; A[1] = B[1]; B[1] = C[1]; C[1] = s;
 349 #if mmcount > 3
 350        if (low == 3 * sizeof(mmtype)) {s = A[2]; A[2] = B[2]; B[2] = C[2]; C[2] = s;}
 351 #endif
 352      }
 353 #endif
 354    }
 355  }
 356  else {
 357    register char *t = a + size, s;
 358    do {s = *a; *a++ = *b; *b++ = *c; *c++ = s;} while (a < t);
 359  }
 360 }
 361 #define mmrot3(a,b,c) mmrot3_((a),(b),(c),mmarg)
 362
 363 /* qs6.c */
 364 /*****************************************************/
 365 /*                                                   */
 366 /*          qs6   (Quick sort function)              */
 367 /*                                                   */
 368 /* by  Tomoyuki Kawamura              1995.4.21      */
 369 /* kawamura@tokuyama.ac.jp                           */
 370 /*****************************************************/
 371
 372 typedef struct { char *LL, *RR; } stack_node; /* Stack structure for L,l,R,r */
 373 #define PUSH(ll,rr) do { top->LL = (ll); top->RR = (rr); ++top; } while (0)  /* Push L,l,R,r */
 374 #define POP(ll,rr)  do { --top; (ll) = top->LL; (rr) = top->RR; } while (0)      /* Pop L,l,R,r */
 375
 376 #define med3(a,b,c) ((*cmp)((a),(b),d)<0 ?                                   \
 377                        ((*cmp)((b),(c),d)<0 ? (b) : ((*cmp)((a),(c),d)<0 ? (c) : (a))) : \
 378                        ((*cmp)((b),(c),d)>0 ? (b) : ((*cmp)((a),(c),d)<0 ? (a) : (c))))
 379
 380 void
 381 ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d)
 382 {
 383   register char *l, *r, *m;             /* l,r:left,right group   m:median point */
 384   register int t, eq_l, eq_r;           /* eq_l: all items in left group are equal to S */
 385   char *L = base;                       /* left end of current region */
 386   char *R = (char*)base + size*(nel-1); /* right end of current region */
 387   size_t chklim = 63;                   /* threshold of ordering element check */
 388   enum {size_bits = sizeof(size) * CHAR_BIT};
 389   stack_node stack[size_bits];          /* enough for size_t size */
 390   stack_node *top = stack;
 391   int mmkind;
 392   size_t high, low, n;
 393
 394   if (nel <= 1) return;        /* need not to sort */
 395   mmprepare(base, size);
 396   goto start;
 397
 398   nxt:
 399   if (stack == top) return;    /* return if stack is empty */
 400   POP(L,R);
 401
 402   for (;;) {
 403     start:
 404     if (L + size == R) {       /* 2 elements */
 405       if ((*cmp)(L,R,d) > 0) mmswap(L,R);
 406       goto nxt;
 407     }
 408
 409     l = L; r = R;
 410     n = (r - l + size) / size;  /* number of elements */
 411     m = l + size * (n >> 1);    /* calculate median value */
 412
 413     if (n >= 60) {
 414       register char *m1;
 415       register char *m3;
 416       if (n >= 200) {
 417         n = size*(n>>3); /* number of bytes in splitting 8 */
 418         {
 419           register char *p1 = l  + n;
 420           register char *p2 = p1 + n;
 421           register char *p3 = p2 + n;
 422           m1 = med3(p1, p2, p3);
 423           p1 = m  + n;
 424           p2 = p1 + n;
 425           p3 = p2 + n;
 426           m3 = med3(p1, p2, p3);
 427         }
 428       }
 429       else {
 430         n = size*(n>>2); /* number of bytes in splitting 4 */
 431         m1 = l + n;
 432         m3 = m + n;
 433       }
 434       m = med3(m1, m, m3);
 435     }
 436
 437     if ((t = (*cmp)(l,m,d)) < 0) {                           /*3-5-?*/
 438       if ((t = (*cmp)(m,r,d)) < 0) {                         /*3-5-7*/
 439         if (chklim && nel >= chklim) {   /* check if already ascending order */
 440           char *p;
 441           chklim = 0;
 442           for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) > 0) goto fail;
 443           goto nxt;
 444         }
 445         fail: goto loopA;                                    /*3-5-7*/
 446       }
 447       if (t > 0) {
 448         if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;}     /*3-5-4*/
 449         mmrot3(r,m,l); goto loopA;                           /*3-5-2*/
 450       }
 451       goto loopB;                                            /*3-5-5*/
 452     }
 453
 454     if (t > 0) {                                             /*7-5-?*/
 455       if ((t = (*cmp)(m,r,d)) > 0) {                         /*7-5-3*/
 456         if (chklim && nel >= chklim) {   /* check if already ascending order */
 457           char *p;
 458           chklim = 0;
 459           for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) < 0) goto fail2;
 460           while (l<r) {mmswap(l,r); l+=size; r-=size;}  /* reverse region */
 461           goto nxt;
 462         }
 463         fail2: mmswap(l,r); goto loopA;                      /*7-5-3*/
 464       }
 465       if (t < 0) {
 466         if ((*cmp)(l,r,d) <= 0) {mmswap(l,m); goto loopB;}   /*7-5-8*/
 467         mmrot3(l,m,r); goto loopA;                           /*7-5-6*/
 468       }
 469       mmswap(l,r); goto loopA;                               /*7-5-5*/
 470     }
 471
 472     if ((t = (*cmp)(m,r,d)) < 0)  {goto loopA;}              /*5-5-7*/
 473     if (t > 0) {mmswap(l,r); goto loopB;}                    /*5-5-3*/
 474
 475     /* determining splitting type in case 5-5-5 */           /*5-5-5*/
 476     for (;;) {
 477       if ((l += size) == r)      goto nxt;                   /*5-5-5*/
 478       if (l == m) continue;
 479       if ((t = (*cmp)(l,m,d)) > 0) {mmswap(l,r); l = L; goto loopA;}/*575-5*/
 480       if (t < 0)                 {mmswap(L,l); l = L; goto loopB;}  /*535-5*/
 481     }
 482
 483     loopA: eq_l = 1; eq_r = 1;  /* splitting type A */ /* left <= median < right */
 484     for (;;) {
 485       for (;;) {
 486         if ((l += size) == r)
 487           {l -= size; if (l != m) mmswap(m,l); l -= size; goto fin;}
 488         if (l == m) continue;
 489         if ((t = (*cmp)(l,m,d)) > 0) {eq_r = 0; break;}
 490         if (t < 0) eq_l = 0;
 491       }
 492       for (;;) {
 493         if (l == (r -= size))
 494           {l -= size; if (l != m) mmswap(m,l); l -= size; goto fin;}
 495         if (r == m) {m = l; break;}
 496         if ((t = (*cmp)(r,m,d)) < 0) {eq_l = 0; break;}
 497         if (t == 0) break;
 498       }
 499       mmswap(l,r);    /* swap left and right */
 500     }
 501
 502     loopB: eq_l = 1; eq_r = 1;  /* splitting type B */ /* left < median <= right */
 503     for (;;) {
 504       for (;;) {
 505         if (l == (r -= size))
 506           {r += size; if (r != m) mmswap(r,m); r += size; goto fin;}
 507         if (r == m) continue;
 508         if ((t = (*cmp)(r,m,d)) < 0) {eq_l = 0; break;}
 509         if (t > 0) eq_r = 0;
 510       }
 511       for (;;) {
 512         if ((l += size) == r)
 513           {r += size; if (r != m) mmswap(r,m); r += size; goto fin;}
 514         if (l == m) {m = r; break;}
 515         if ((t = (*cmp)(l,m,d)) > 0) {eq_r = 0; break;}
 516         if (t == 0) break;
 517       }
 518       mmswap(l,r);    /* swap left and right */
 519     }
 520
 521     fin:
 522     if (eq_l == 0)                         /* need to sort left side */
 523       if (eq_r == 0)                       /* need to sort right side */
 524         if (l-L < R-r) {PUSH(r,R); R = l;} /* sort left side first */
 525         else           {PUSH(L,l); L = r;} /* sort right side first */
 526       else R = l;                          /* need to sort left side only */
 527     else if (eq_r == 0) L = r;             /* need to sort right side only */
 528     else goto nxt;                         /* need not to sort both sides */
 529   }
 530 }
 531 #endif
 532 #endif /* !HAVE_GNU_QSORT_R */
 533
 534 char *
 535 ruby_strdup(const char *str)
 536 {
 537     char *tmp;
 538     size_t len = strlen(str) + 1;
 539
 540     tmp = xmalloc(len);
 541     memcpy(tmp, str, len);
 542
 543     return tmp;
 544 }
 545
 546 char *
 547 ruby_getcwd(void)
 548 {
 549 #if defined HAVE_GETCWD
 550 # undef RUBY_UNTYPED_DATA_WARNING
 551 # define RUBY_UNTYPED_DATA_WARNING 0
 552 # if defined NO_GETCWD_MALLOC
 553     VALUE guard = Data_Wrap_Struct((VALUE)0, NULL, RUBY_DEFAULT_FREE, NULL);
 554     int size = 200;
 555     char *buf = xmalloc(size);
 556
 557     while (!getcwd(buf, size)) {
 558         int e = errno;
 559         if (e != ERANGE) {
 560             xfree(buf);
 561             DATA_PTR(guard) = NULL;
 562             rb_syserr_fail(e, "getcwd");
 563         }
 564         size *= 2;
 565         DATA_PTR(guard) = buf;
 566         buf = xrealloc(buf, size);
 567     }
 568 # else
 569     VALUE guard = Data_Wrap_Struct((VALUE)0, NULL, free, NULL);
 570     char *buf, *cwd = getcwd(NULL, 0);
 571     DATA_PTR(guard) = cwd;
 572     if (!cwd) rb_sys_fail("getcwd");
 573     buf = ruby_strdup(cwd);     /* allocate by xmalloc */
 574     free(cwd);
 575 # endif
 576     DATA_PTR(RB_GC_GUARD(guard)) = NULL;
 577 #else
 578 # ifndef PATH_MAX
 579 #  define PATH_MAX 8192
 580 # endif
 581     char *buf = xmalloc(PATH_MAX+1);
 582
 583     if (!getwd(buf)) {
 584         int e = errno;
 585         xfree(buf);
 586         rb_syserr_fail(e, "getwd");
 587     }
 588 #endif
 589     return buf;
 590 }
 591
 592 void
 593 ruby_each_words(const char *str, void (*func)(const char*, int, void*), void *arg)
 594 {
 595     const char *end;
 596     int len;
 597
 598     if (!str) return;
 599     for (; *str; str = end) {
 600         while (ISSPACE(*str) || *str == ',') str++;
 601         if (!*str) break;
 602         end = str;
 603         while (*end && !ISSPACE(*end) && *end != ',') end++;
 604         len = (int)(end - str); /* assume no string exceeds INT_MAX */
 605         (*func)(str, len, arg);
 606     }
 607 }
 608
 609 #undef strtod
 610 #define strtod ruby_strtod
 611 #undef dtoa
 612 #define dtoa ruby_dtoa
 613 #undef hdtoa
 614 #define hdtoa ruby_hdtoa
 615 #include "missing/dtoa.c"