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