coregrind/vg_mylibc.c

/*--------------------------------------------------------------------*/
/*--- Reimplementation of some C library stuff, to avoid depending ---*/
/*--- on libc.so.                                                  ---*/
/*---                                                  vg_mylibc.c ---*/
/*--------------------------------------------------------------------*/

/*
   This file is part of Valgrind, an extensible x86 protected-mode
   emulator for monitoring program execution on x86-Unixes.

   Copyright (C) 2000-2004 Julian Seward 
      jseward@acm.org

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307, USA.

   The GNU General Public License is contained in the file COPYING.
*/

#include "core.h"

/* ---------------------------------------------------------------------
   Wrappers around system calls, and other stuff, to do with signals.
   ------------------------------------------------------------------ */

/* sigemptyset, sigfullset, sigaddset and sigdelset return 0 on
   success and -1 on error.  
*/
Int VG_(ksigfillset)( vki_ksigset_t* set )
{
   Int i;
   if (set == NULL)
      return -1;
   for (i = 0; i < VKI_KNSIG_WORDS; i++)
      set->ws[i] = 0xFFFFFFFF;
   return 0;
}

Int VG_(ksigemptyset)( vki_ksigset_t* set )
{
   Int i;
   if (set == NULL)
      return -1;
   for (i = 0; i < VKI_KNSIG_WORDS; i++)
      set->ws[i] = 0x0;
   return 0;
}

Bool VG_(kisemptysigset)( vki_ksigset_t* set )
{
   Int i;
   vg_assert(set != NULL);
   for (i = 0; i < VKI_KNSIG_WORDS; i++)
      if (set->ws[i] != 0x0) return False;
   return True;
}

Bool VG_(kisfullsigset)( vki_ksigset_t* set )
{
   Int i;
   vg_assert(set != NULL);
   for (i = 0; i < VKI_KNSIG_WORDS; i++)
      if (set->ws[i] != (UInt)(~0x0)) return False;
   return True;
}


Int VG_(ksigaddset)( vki_ksigset_t* set, Int signum )
{
   if (set == NULL)
      return -1;
   if (signum < 1 || signum > VKI_KNSIG)
      return -1;
   signum--;
   set->ws[signum / VKI_KNSIG_BPW] |= (1 << (signum % VKI_KNSIG_BPW));
   return 0;
}

Int VG_(ksigdelset)( vki_ksigset_t* set, Int signum )
{
   if (set == NULL)
      return -1;
   if (signum < 1 || signum > VKI_KNSIG)
      return -1;
   signum--;
   set->ws[signum / VKI_KNSIG_BPW] &= ~(1 << (signum % VKI_KNSIG_BPW));
   return 0;
}

Int VG_(ksigismember) ( vki_ksigset_t* set, Int signum )
{
   if (set == NULL)
      return 0;
   if (signum < 1 || signum > VKI_KNSIG)
      return 0;
   signum--;
   if (1 & ((set->ws[signum / VKI_KNSIG_BPW]) >> (signum % VKI_KNSIG_BPW)))
      return 1;
   else
      return 0;
}


/* Add all signals in src to dst. */
void VG_(ksigaddset_from_set)( vki_ksigset_t* dst, vki_ksigset_t* src )
{
   Int i;
   vg_assert(dst != NULL && src != NULL);
   for (i = 0; i < VKI_KNSIG_WORDS; i++)
      dst->ws[i] |= src->ws[i];
}

/* Remove all signals in src from dst. */
void VG_(ksigdelset_from_set)( vki_ksigset_t* dst, vki_ksigset_t* src )
{
   Int i;
   vg_assert(dst != NULL && src != NULL);
   for (i = 0; i < VKI_KNSIG_WORDS; i++)
      dst->ws[i] &= ~(src->ws[i]);
}


/* The functions sigaction, sigprocmask, sigpending and sigsuspend
   return 0 on success and -1 on error.  
*/
Int VG_(ksigprocmask)( Int how, 
                       const vki_ksigset_t* set, 
                       vki_ksigset_t* oldset)
{
   Int res 
      = VG_(do_syscall)(__NR_rt_sigprocmask, 
			how, (UInt)set, (UInt)oldset, 
			VKI_KNSIG_WORDS * VKI_BYTES_PER_WORD);
   return VG_(is_kerror)(res) ? -1 : 0;
}


Int VG_(ksigaction) ( Int signum,  
                      const vki_ksigaction* act,  
                      vki_ksigaction* oldact)
{
   Int res
     = VG_(do_syscall)(__NR_rt_sigaction,
		       signum, (UInt)act, (UInt)oldact, 
		       VKI_KNSIG_WORDS * VKI_BYTES_PER_WORD);
   /* VG_(printf)("res = %d\n",res); */
   return VG_(is_kerror)(res) ? -1 : 0;
}


Int VG_(ksigaltstack)( const vki_kstack_t* ss, vki_kstack_t* oss )
{
   Int res
     = VG_(do_syscall)(__NR_sigaltstack, (UInt)ss, (UInt)oss);
   return VG_(is_kerror)(res) ? -1 : 0;
}

Int VG_(ksigtimedwait)( const vki_ksigset_t *set, vki_ksiginfo_t *info, 
			const struct vki_timespec *timeout )
{
   Int res = VG_(do_syscall)(__NR_rt_sigtimedwait, set, info, timeout, sizeof(*set));

   return VG_(is_kerror)(res) ? -1 : res;
}
 
Int VG_(ksignal)(Int signum, void (*sighandler)(Int))
{
   Int res;
   vki_ksigaction sa;
   sa.ksa_handler = sighandler;
   sa.ksa_flags = VKI_SA_ONSTACK | VKI_SA_RESTART;
   sa.ksa_restorer = NULL;
   res = VG_(ksigemptyset)( &sa.ksa_mask );
   vg_assert(res == 0);
   res = VG_(do_syscall)(__NR_rt_sigaction,
			 signum, (UInt)(&sa), (UInt)NULL,
			 VKI_KNSIG_WORDS * VKI_BYTES_PER_WORD);
   return VG_(is_kerror)(res) ? -1 : 0;
}


Int VG_(kkill)( Int pid, Int signo )
{
   Int res = VG_(do_syscall)(__NR_kill, pid, signo);
   return VG_(is_kerror)(res) ? -1 : 0;
}


Int VG_(ktkill)( Int tid, Int signo )
{
   Int ret = -VKI_ENOSYS;

#ifdef __NR_tkill
   ret = VG_(do_syscall)(__NR_tkill, tid, signo);
#endif /* __NR_tkill */

   if (ret == -VKI_ENOSYS)
      ret = VG_(do_syscall)(__NR_kill, tid, signo);

   return VG_(is_kerror)(ret) ? -1 : 0;
}

Int VG_(ksigpending) ( vki_ksigset_t* set )
{
   Int res = VG_(do_syscall)(__NR_sigpending, (UInt)set);
   return VG_(is_kerror)(res) ? -1 : 0;
}

Int VG_(waitpid)(Int pid, Int *status, Int options)
{
   Int ret = VG_(do_syscall)(__NR_wait4, pid, status, options, NULL);

   return VG_(is_kerror)(ret) ? -1 : ret;
}

Int VG_(gettid)(void)
{
   Int ret;

   ret = VG_(do_syscall)(__NR_gettid);

   if (ret == -VKI_ENOSYS)
      ret = VG_(do_syscall)(__NR_getpid);

   return ret;
}



/* ---------------------------------------------------------------------
   mmap/munmap, exit, fcntl
   ------------------------------------------------------------------ */

static Int munmap_inner(void *start, UInt length)
{
   return VG_(do_syscall)(__NR_munmap, (UInt)start, (UInt)length );
}

static Addr mmap_inner(void *start, UInt length, UInt prot, UInt flags, UInt fd, UInt offset)
{
   UInt args[6];

   args[0] = (UInt)start;
   args[1] = length;
   args[2] = prot;
   args[3] = flags & ~(VKI_MAP_NOSYMS|VKI_MAP_CLIENT);
   args[4] = fd;
   args[5] = offset;

   return VG_(do_syscall)(__NR_mmap, (UInt)(&(args[0])) );   
}

/* Returns -1 on failure. */
void* VG_(mmap)( void* start, UInt length,
                 UInt prot, UInt flags, UInt sf_flags, UInt fd, UInt offset)
{
   Addr  res;

   if (!(flags & VKI_MAP_FIXED)) {
      start = (void *)VG_(find_map_space)((Addr)start, length, !!(flags & VKI_MAP_CLIENT));

      flags |= VKI_MAP_FIXED;
   }
   if (start == 0)
      return (void *)-1;

   res = mmap_inner(start, length, prot, flags, fd, offset);

   // Check it ended up in the right place.
   if (!VG_(is_kerror)(res)) {
      if (flags & VKI_MAP_CLIENT) {
         vg_assert(VG_(client_base) <= res && res+length < VG_(client_end));
      } else {
         vg_assert(VG_(valgrind_base) <= res && res+length-1 <= VG_(valgrind_last));
      }

      sf_flags |= SF_MMAP;
      if (  flags & VKI_MAP_FIXED)      sf_flags |= SF_FIXED;
      if (  flags & VKI_MAP_SHARED)     sf_flags |= SF_SHARED;
      if (!(flags & VKI_MAP_ANONYMOUS)) sf_flags |= SF_FILE;
      if (!(flags & VKI_MAP_CLIENT))    sf_flags |= SF_VALGRIND;
      if (  flags & VKI_MAP_NOSYMS)     sf_flags |= SF_NOSYMS;

      VG_(map_fd_segment)(res, length, prot, sf_flags, fd, offset, NULL);
   }

   return VG_(is_kerror)(res) ? ((void*)(-1)) : (void*)res;
}

/* Returns -1 on failure. */
Int VG_(munmap)( void* start, Int length )
{
   Int res = munmap_inner(start, length);
   if (!VG_(is_kerror)(res))
      VG_(unmap_range)((Addr)start, length);
   return VG_(is_kerror)(res) ? -1 : 0;
}

Int VG_(mprotect)( void *start, Int length, UInt prot )
{
   Int res = VG_(do_syscall)(__NR_mprotect, (UInt)start, (UInt)length, prot );
   if (!VG_(is_kerror)(res))
      VG_(mprotect_range)((Addr)start, length, prot);
   return VG_(is_kerror)(res) ? -1 : 0;
}

void VG_(exit)( Int status )
{
   (void)VG_(do_syscall)(__NR_exit_group, (UInt)status );
   (void)VG_(do_syscall)(__NR_exit, (UInt)status );
   /* Why are we still alive here? */
   /*NOTREACHED*/
   *(volatile Int *)0 = 'x';
   vg_assert(2+2 == 5);
}

/* Returns -1 on error. */
Int VG_(fcntl) ( Int fd, Int cmd, Int arg )
{
   Int res = VG_(do_syscall)(__NR_fcntl, fd, cmd, arg);
   return VG_(is_kerror)(res) ? -1 : res;
}

Int VG_(poll)( struct vki_pollfd *ufds, UInt nfds, Int timeout)
{
   Int res = VG_(do_syscall)(__NR_poll, ufds, nfds, timeout);

   return res;
}


/* ---------------------------------------------------------------------
   printf implementation.  The key function, vg_vprintf(), emits chars 
   into a caller-supplied function.  Distantly derived from:

      vprintf replacement for Checker.
      Copyright 1993, 1994, 1995 Tristan Gingold
      Written September 1993 Tristan Gingold
      Tristan Gingold, 8 rue Parmentier, F-91120 PALAISEAU, FRANCE

   (Checker itself was GPL'd.)
   ------------------------------------------------------------------ */


/* Some flags.  */
#define VG_MSG_SIGNED    1 /* The value is signed. */
#define VG_MSG_ZJUSTIFY  2 /* Must justify with '0'. */
#define VG_MSG_LJUSTIFY  4 /* Must justify on the left. */
#define VG_MSG_PAREN     8 /* Parenthesize if present (for %y) */
#define VG_MSG_COMMA    16 /* Add commas to numbers (for %d, %u) */

/* Copy a string into the buffer. */
static UInt
myvprintf_str ( void(*send)(Char), Int flags, Int width, Char* str, 
                Bool capitalise )
{
#  define MAYBE_TOUPPER(ch) (capitalise ? VG_(toupper)(ch) : (ch))
   UInt ret = 0;
   Int i, extra;
   Int len = VG_(strlen)(str);

   if (width == 0) {
      ret += len;
      for (i = 0; i < len; i++)
         send(MAYBE_TOUPPER(str[i]));
      return ret;
   }

   if (len > width) {
      ret += width;
      for (i = 0; i < width; i++)
         send(MAYBE_TOUPPER(str[i]));
      return ret;
   }

   extra = width - len;
   if (flags & VG_MSG_LJUSTIFY) {
      ret += extra;
      for (i = 0; i < extra; i++)
         send(' ');
   }
   ret += len;
   for (i = 0; i < len; i++)
      send(MAYBE_TOUPPER(str[i]));
   if (!(flags & VG_MSG_LJUSTIFY)) {
      ret += extra;
      for (i = 0; i < extra; i++)
         send(' ');
   }

#  undef MAYBE_TOUPPER

   return ret;
}

/* Write P into the buffer according to these args:
 *  If SIGN is true, p is a signed.
 *  BASE is the base.
 *  If WITH_ZERO is true, '0' must be added.
 *  WIDTH is the width of the field.
 */
static UInt
myvprintf_int64 ( void(*send)(Char), Int flags, Int base, Int width, ULong p)
{
   Char buf[40];
   Int  ind = 0;
   Int  i, nc = 0;
   Bool neg = False;
   Char *digits = "0123456789ABCDEF";
   UInt ret = 0;

   if (base < 2 || base > 16)
      return ret;
 
   if ((flags & VG_MSG_SIGNED) && (Long)p < 0) {
      p   = - (Long)p;
      neg = True;
   }

   if (p == 0)
      buf[ind++] = '0';
   else {
      while (p > 0) {
         if (flags & VG_MSG_COMMA && 10 == base &&
             0 == (ind-nc) % 3 && 0 != ind) 
         {
            buf[ind++] = ',';
            nc++;
         }
         buf[ind++] = digits[p % base];
         p /= base;
      }
   }

   if (neg)
      buf[ind++] = '-';

   if (width > 0 && !(flags & VG_MSG_LJUSTIFY)) {
      for(; ind < width; ind++) {
         vg_assert(ind < 39);
         buf[ind] = (flags & VG_MSG_ZJUSTIFY) ? '0': ' ';
      }
   }

   /* Reverse copy to buffer.  */
   ret += ind;
   for (i = ind -1; i >= 0; i--) {
      send(buf[i]);
   }
   if (width > 0 && (flags & VG_MSG_LJUSTIFY)) {
      for(; ind < width; ind++) {
	 ret++;
         send(' ');  // Never pad with zeroes on RHS -- changes the value!
      }
   }
   return ret;
}


/* A simple vprintf().  */
UInt
VG_(vprintf) ( void(*send)(Char), const Char *format, va_list vargs )
{
   UInt ret = 0;
   int i;
   int flags;
   int width;
   Bool is_long;

   /* We assume that vargs has already been initialised by the 
      caller, using va_start, and that the caller will similarly
      clean up with va_end.
   */

   for (i = 0; format[i] != 0; i++) {
      if (format[i] != '%') {
         send(format[i]);
	 ret++;
         continue;
      }
      i++;
      /* A '%' has been found.  Ignore a trailing %. */
      if (format[i] == 0)
         break;
      if (format[i] == '%') {
         /* `%%' is replaced by `%'. */
         send('%');
	 ret++;
         continue;
      }
      flags = 0;
      is_long = False;
      width = 0; /* length of the field. */
      if (format[i] == '(') {
	 flags |= VG_MSG_PAREN;
	 i++;
      }
      /* If ',' follows '%', commas will be inserted. */
      if (format[i] == ',') {
         flags |= VG_MSG_COMMA;
         i++;
      }
      /* If '-' follows '%', justify on the left. */
      if (format[i] == '-') {
         flags |= VG_MSG_LJUSTIFY;
         i++;
      }
      /* If '0' follows '%', pads will be inserted. */
      if (format[i] == '0') {
         flags |= VG_MSG_ZJUSTIFY;
         i++;
      }
      /* Compute the field length. */
      while (format[i] >= '0' && format[i] <= '9') {
         width *= 10;
         width += format[i++] - '0';
      }
      while (format[i] == 'l') {
         i++;
         is_long = True;
      }

      switch (format[i]) {
         case 'd': /* %d */
            flags |= VG_MSG_SIGNED;
            if (is_long)
               ret += myvprintf_int64(send, flags, 10, width, 
				      (ULong)(va_arg (vargs, Long)));
            else
               ret += myvprintf_int64(send, flags, 10, width, 
				      (ULong)(va_arg (vargs, Int)));
            break;
         case 'u': /* %u */
            if (is_long)
               ret += myvprintf_int64(send, flags, 10, width, 
				      (ULong)(va_arg (vargs, ULong)));
            else
               ret += myvprintf_int64(send, flags, 10, width, 
				      (ULong)(va_arg (vargs, UInt)));
            break;
         case 'p': /* %p */
	    ret += 2;
            send('0');
            send('x');
            ret += myvprintf_int64(send, flags, 16, width, 
				   (ULong)((UInt)va_arg (vargs, void *)));
            break;
         case 'x': /* %x */
            if (is_long)
               ret += myvprintf_int64(send, flags, 16, width, 
				      (ULong)(va_arg (vargs, ULong)));
            else
               ret += myvprintf_int64(send, flags, 16, width, 
				      (ULong)(va_arg (vargs, UInt)));
            break;
         case 'c': /* %c */
	    ret++;
            send(va_arg (vargs, int));
            break;
         case 's': case 'S': { /* %s */
            char *str = va_arg (vargs, char *);
            if (str == (char*) 0) str = "(null)";
            ret += myvprintf_str(send, flags, width, str, format[i]=='S');
            break;
	 }
	 case 'y': { /* %y - print symbol */
	    Char buf[100];
	    Char *cp = buf;
	    Addr a = va_arg(vargs, Addr);

	    if (flags & VG_MSG_PAREN)
	       *cp++ = '(';
	    if (VG_(get_fnname_w_offset)(a, cp, sizeof(buf)-4)) {
	       if (flags & VG_MSG_PAREN) {
		  cp += VG_(strlen)(cp);
		  *cp++ = ')';
		  *cp = '\0';
	       }
	       ret += myvprintf_str(send, flags, width, buf, 0);
	    }

	    break;
	 }
         default:
            break;
      }
   }
   return ret;
}


/* A general replacement for printf().  Note that only low-level 
   debugging info should be sent via here.  The official route is to
   to use vg_message().  This interface is deprecated.
*/
static char myprintf_buf[100];
static int  n_myprintf_buf;

static void add_to_myprintf_buf ( Char c )
{
   if (n_myprintf_buf >= 100-10 /*paranoia*/ ) {
      if (VG_(clo_log_fd) >= 0) {
         VG_(send_bytes_to_logging_sink)( 
            myprintf_buf, VG_(strlen)(myprintf_buf) );
      }
      n_myprintf_buf = 0;
      myprintf_buf[n_myprintf_buf] = 0;      
   }
   myprintf_buf[n_myprintf_buf++] = c;
   myprintf_buf[n_myprintf_buf] = 0;
}

UInt VG_(printf) ( const char *format, ... )
{
   UInt ret;
   va_list vargs;
   va_start(vargs,format);
   
   n_myprintf_buf = 0;
   myprintf_buf[n_myprintf_buf] = 0;      
   ret = VG_(vprintf) ( add_to_myprintf_buf, format, vargs );

   if (n_myprintf_buf > 0 && VG_(clo_log_fd) >= 0) {
      VG_(send_bytes_to_logging_sink)( myprintf_buf, n_myprintf_buf );
   }

   va_end(vargs);

   return ret;
}

/* A general replacement for sprintf(). */

static Char *vg_sprintf_ptr;

static void add_to_vg_sprintf_buf ( Char c )
{
   *vg_sprintf_ptr++ = c;
}

UInt VG_(sprintf) ( Char* buf, Char *format, ... )
{
   Int ret;
   va_list vargs;

   vg_sprintf_ptr = buf;

   va_start(vargs,format);

   ret = VG_(vprintf) ( add_to_vg_sprintf_buf, format, vargs );
   add_to_vg_sprintf_buf(0);

   va_end(vargs);

   vg_assert(VG_(strlen)(buf) == ret);
   return ret;
}


/* ---------------------------------------------------------------------
   Misc str* functions.
   ------------------------------------------------------------------ */

Bool VG_(isspace) ( Char c )
{
   return (c == ' ' || c == '\n' || c == '\t' || c == 0);
}

Bool VG_(isdigit) ( Char c )
{
   return (c >= '0' && c <= '9');
}

Int VG_(strlen) ( const Char* str )
{
   Int i = 0;
   while (str[i] != 0) i++;
   return i;
}


Long VG_(atoll) ( Char* str )
{
   Bool neg = False;
   Long n = 0;
   if (*str == '-') { str++; neg = True; };
   while (*str >= '0' && *str <= '9') {
      n = 10*n + (Long)(*str - '0');
      str++;
   }
   if (neg) n = -n;
   return n;
}


Long VG_(atoll16) ( Char* str )
{
   Bool neg = False;
   Long n = 0;
   if (*str == '-') { str++; neg = True; };
   while (True) {
      if (*str >= '0' && *str <= '9') {
         n = 16*n + (Long)(*str - '0');
      }
      else 
      if (*str >= 'A' && *str <= 'F') {
         n = 16*n + (Long)((*str - 'A') + 10);
      }
      else 
      if (*str >= 'a' && *str <= 'f') {
         n = 16*n + (Long)((*str - 'a') + 10);
      }
      else {
	break;
      }
      str++;
   }
   if (neg) n = -n;
   return n;
}

Long VG_(atoll36) ( UInt base, Char* str )
{
   Bool neg = False;
   Long n = 0;
   vg_assert(base >= 2 && base <= 36);
   if (*str == '-') { str++; neg = True; };
   while (True) {
      if (*str >= '0' 
          && *str <= (Char)('9' - (10 - base))) {
         n = base*n + (Long)(*str - '0');
      }
      else 
      if (base > 10 && *str >= 'A' 
          && *str <= (Char)('Z' - (36 - base))) {
         n = base*n + (Long)((*str - 'A') + 10);
      }
      else 
      if (base > 10 && *str >= 'a' 
          && *str <= (Char)('z' - (36 - base))) {
         n = base*n + (Long)((*str - 'a') + 10);
      }
      else {
	break;
      }
      str++;
   }
   if (neg) n = -n;
   return n;
}


Char* VG_(strcat) ( Char* dest, const Char* src )
{
   Char* dest_orig = dest;
   while (*dest) dest++;
   while (*src) *dest++ = *src++;
   *dest = 0;
   return dest_orig;
}


Char* VG_(strncat) ( Char* dest, const Char* src, Int n )
{
   Char* dest_orig = dest;
   while (*dest) dest++;
   while (*src && n > 0) { *dest++ = *src++; n--; }
   *dest = 0;
   return dest_orig;
}


Char* VG_(strpbrk) ( const Char* s, const Char* accept )
{
   const Char* a;
   while (*s) {
      a = accept;
      while (*a)
         if (*a++ == *s)
            return (Char *) s;
      s++;
   }
   return NULL;
}


Char* VG_(strcpy) ( Char* dest, const Char* src )
{
   Char* dest_orig = dest;
   while (*src) *dest++ = *src++;
   *dest = 0;
   return dest_orig;
}


/* Copy bytes, not overrunning the end of dest and always ensuring
   zero termination. */
void VG_(strncpy_safely) ( Char* dest, const Char* src, Int ndest )
{
   Int i;
   vg_assert(ndest > 0);
   i = 0;
   dest[i] = 0;
   while (True) {
      if (src[i] == 0) return;
      if (i >= ndest-1) return;
      dest[i] = src[i];
      i++;
      dest[i] = 0;
   }
}


Char* VG_(strncpy) ( Char* dest, const Char* src, Int ndest )
{
   Int i = 0;
   while (True) {
      if (i >= ndest) return dest;     /* reached limit */
      dest[i] = src[i];
      if (src[i++] == 0) {
         /* reached NUL;  pad rest with zeroes as required */
         while (i < ndest) dest[i++] = 0;
         return dest;
      }
   }
}


Int VG_(strcmp) ( const Char* s1, const Char* s2 )
{
   while (True) {
      if (*s1 == 0 && *s2 == 0) return 0;
      if (*s1 == 0) return -1;
      if (*s2 == 0) return 1;

      if (*(UChar*)s1 < *(UChar*)s2) return -1;
      if (*(UChar*)s1 > *(UChar*)s2) return 1;

      s1++; s2++;
   }
}


Int VG_(strcmp_ws) ( const Char* s1, const Char* s2 )
{
   while (True) {
      if (VG_(isspace)(*s1) && VG_(isspace)(*s2)) return 0;
      if (VG_(isspace)(*s1)) return -1;
      if (VG_(isspace)(*s2)) return 1;

      if (*(UChar*)s1 < *(UChar*)s2) return -1;
      if (*(UChar*)s1 > *(UChar*)s2) return 1;

      s1++; s2++;
   }
}


Int VG_(strncmp) ( const Char* s1, const Char* s2, Int nmax )
{
   Int n = 0;
   while (True) {
      if (n >= nmax) return 0;
      if (*s1 == 0 && *s2 == 0) return 0;
      if (*s1 == 0) return -1;
      if (*s2 == 0) return 1;

      if (*(UChar*)s1 < *(UChar*)s2) return -1;
      if (*(UChar*)s1 > *(UChar*)s2) return 1;

      s1++; s2++; n++;
   }
}


Int VG_(strncmp_ws) ( const Char* s1, const Char* s2, Int nmax )
{
   Int n = 0;
   while (True) {
      if (n >= nmax) return 0;
      if (VG_(isspace)(*s1) && VG_(isspace)(*s2)) return 0;
      if (VG_(isspace)(*s1)) return -1;
      if (VG_(isspace)(*s2)) return 1;

      if (*(UChar*)s1 < *(UChar*)s2) return -1;
      if (*(UChar*)s1 > *(UChar*)s2) return 1;

      s1++; s2++; n++;
   }
}


Char* VG_(strstr) ( const Char* haystack, Char* needle )
{
   Int n; 
   if (haystack == NULL)
      return NULL;
   n = VG_(strlen)(needle);
   while (True) {
      if (haystack[0] == 0) 
         return NULL;
      if (VG_(strncmp)(haystack, needle, n) == 0) 
         return (Char*)haystack;
      haystack++;
   }
}


Char* VG_(strchr) ( const Char* s, Char c )
{
   while (True) {
      if (*s == c) return (Char*)s;
      if (*s == 0) return NULL;
      s++;
   }
}


Char* VG_(strrchr) ( const Char* s, Char c )
{
   Int n = VG_(strlen)(s);
   while (--n > 0) {
      if (s[n] == c) return (Char*)s + n;
   }
   return NULL;
}


void* VG_(memcpy) ( void *dest, const void *src, Int sz )
{
   const Char *s = (const Char *)src;
   Char *d = (Char *)dest;
   vg_assert(sz >= 0);

   while (sz--)
      *d++ = *s++;

   return dest;
}


void* VG_(memset) ( void *dest, Int c, Int sz )
{
   Char *d = (Char *)dest;
   vg_assert(sz >= 0);

   while (sz--)
      *d++ = c;

   return dest;
}

Int VG_(memcmp) ( const void* s1, const void* s2, Int n )
{
   Int res;
   UChar a0;
   UChar b0;
   vg_assert(n >= 0);

   while (n != 0) {
      a0 = ((UChar *) s1)[0];
      b0 = ((UChar *) s2)[0];
      s1 += 1;
      s2 += 1;
      res = a0 - b0;
      if (res != 0)
         return res;
      n -= 1;
   }
   return 0;
}

Char VG_(toupper) ( Char c )
{
   if (c >= 'a' && c <= 'z')
      return c + ('A' - 'a'); 
   else
      return c;
}


/* Inline just for the wrapper VG_(strdup) below */
__inline__ Char* VG_(arena_strdup) ( ArenaId aid, const Char* s )
{
   Int   i;
   Int   len;
   Char* res;

   if (s == NULL)
      return NULL;

   len = VG_(strlen)(s) + 1;
   res = VG_(arena_malloc) (aid, len);

   for (i = 0; i < len; i++)
      res[i] = s[i];
   return res;
}

/* Wrapper to avoid exposing tools to ArenaId's */
Char* VG_(strdup) ( const Char* s )
{
   return VG_(arena_strdup) ( VG_AR_TOOL, s ); 
}

/* ---------------------------------------------------------------------
   A simple string matching routine, purloined from Hugs98.
      `*'    matches any sequence of zero or more characters
      `?'    matches any single character exactly 
      `\c'   matches the character c only (ignoring special chars)
      c      matches the character c only
   ------------------------------------------------------------------ */

/* Keep track of recursion depth. */
static Int recDepth;

static Bool string_match_wrk ( const Char* pat, const Char* str )
{
   vg_assert(recDepth >= 0 && recDepth < 500);
   recDepth++;
   for (;;) {
      switch (*pat) {
         case '\0' : return (*str=='\0');
         case '*'  : do {
                        if (string_match_wrk(pat+1,str)) {
                           recDepth--;
                           return True;
                        }
                     } while (*str++);
                     recDepth--;
                     return False;
         case '?'  : if (*str++=='\0') {
                        recDepth--;
                        return False;
                     }
                     pat++;
                     break;
         case '\\' : if (*++pat == '\0') {
                        recDepth--;
                        return False; /* spurious trailing \ in pattern */
                     }
                     /* falls through to ... */
         default   : if (*pat++ != *str++) {
                        recDepth--;
                        return False;
                     }
                     break;
      }
   }
}

Bool VG_(string_match) ( const Char* pat, const Char* str )
{
   Bool b;
   recDepth = 0;
   b = string_match_wrk ( pat, str );
   /*
   VG_(printf)("%s   %s   %s\n",
	       b?"TRUE ":"FALSE", pat, str);
   */
   return b;
}


/* ---------------------------------------------------------------------
   Assertery.
   ------------------------------------------------------------------ */

/* Fake up an ExeContext which is of our actual real CPU state, so we
   can print a stack trace.  This isn't terribly useful in the case
   where we were killed by a signal, since we just get a backtrace
   into the signal handler.  Also, it could be somewhat risky if we
   actully got the panic/exception within the execontext/stack
   dump/symtab code.  But it's better than nothing. */
static inline ExeContext *get_real_execontext(Addr ret)
{
   ExeContext *ec;
   Addr esp, ebp;
   Addr stacktop, sigstack_low, sigstack_high;

   asm("movl %%ebp, %0; movl %%esp, %1" : "=r" (ebp), "=r" (esp));
   stacktop = VG_(valgrind_last);
   VG_(get_sigstack_bounds)( &sigstack_low, &sigstack_high );
   if (esp >= sigstack_low && esp < sigstack_high)
      stacktop = sigstack_high;
      
   ec = VG_(get_ExeContext2)(ret, ebp, esp, stacktop);

   return ec;
}

__attribute__ ((noreturn))
static void report_and_quit ( const Char* report )
{
   ExeContext *ec = get_real_execontext((Addr)__builtin_return_address(0));
   VG_(pp_ExeContext)(ec);
   
   VG_(pp_sched_status)();
   VG_(printf)("\n");
   VG_(printf)("Note: see also the FAQ.txt in the source distribution.\n");
   VG_(printf)("It contains workarounds to several common problems.\n");
   VG_(printf)("\n");
   VG_(printf)("If that doesn't help, please report this bug to: %s\n\n", 
               report);
   VG_(printf)("In the bug report, send all the above text, the valgrind\n");
   VG_(printf)("version, and what Linux distro you are using.  Thanks.\n\n");
   VG_(exit)(1);
}

__attribute__ ((noreturn))
static void assert_fail ( const Char* expr, const Char* name, const Char* report,
                          const Char* file, Int line, const Char* fn )
{
   static Bool entered = False;
   if (entered) 
     VG_(exit)(2);
   entered = True;
   VG_(printf)("\n%s: %s:%d (%s): Assertion `%s' failed.\n",
               name, file, line, fn, expr );
   report_and_quit(report);
}

void VG_(skin_assert_fail) ( const Char* expr, const Char* file, Int line, const Char* fn )
{
   assert_fail(expr, VG_(details).name, VG_(details).bug_reports_to, 
               file, line, fn);
}

void VG_(core_assert_fail) ( const Char* expr, const Char* file, Int line, const Char* fn )
{
   assert_fail(expr, "valgrind", VG_BUGS_TO, file, line, fn);
}

__attribute__ ((noreturn))
static void panic ( Char* name, Char* report, Char* str )
{
   VG_(printf)("\n%s: the `impossible' happened:\n   %s\n", name, str);
   VG_(printf)("Basic block ctr is approximately %llu\n", VG_(bbs_done) );
   report_and_quit(report);
}

void VG_(core_panic) ( Char* str )
{
   panic("valgrind", VG_BUGS_TO, str);
}

void VG_(skin_panic) ( Char* str )
{
   panic(VG_(details).name, VG_(details).bug_reports_to, str);
}


/* ---------------------------------------------------------------------
   Primitive support for reading files.
   ------------------------------------------------------------------ */

static inline Bool fd_exists(Int fd)
{
   struct vki_stat st;

   return VG_(fstat)(fd, &st) == 0;
}

/* Move an fd into the Valgrind-safe range */
Int VG_(safe_fd)(Int oldfd)
{
   Int newfd;

   vg_assert(VG_(fd_hard_limit) != -1);

   newfd = VG_(fcntl)(oldfd, VKI_F_DUPFD, VG_(fd_hard_limit));
   if (newfd != -1)
      VG_(close)(oldfd);

   VG_(fcntl)(newfd, VKI_F_SETFD, VKI_FD_CLOEXEC);

   vg_assert(newfd >= VG_(fd_hard_limit));
   return newfd;
}



/* Returns -1 on failure. */
Int VG_(open) ( const Char* pathname, Int flags, Int mode )
{  
   Int fd;

   /* (old comment, not sure if it still applies  NJN 2002-sep-09) */
   /* This gets a segmentation fault if pathname isn't a valid file.
      I don't know why.  It seems like the call to open is getting
      intercepted and messed with by glibc ... */
   /* fd = open( pathname, O_RDONLY ); */
   /* ... so we go direct to the horse's mouth, which seems to work
      ok: */
   fd = VG_(do_syscall)(__NR_open, (UInt)pathname, flags, mode);
   /* VG_(printf)("result = %d\n", fd); */
   /* return -ve error code */
   return fd;
}

Int VG_(pipe) ( Int fd[2] )
{
   Int ret = VG_(do_syscall)(__NR_pipe, fd);
   return VG_(is_kerror)(ret) ? -1 : 0;
}

void VG_(close) ( Int fd )
{
   VG_(do_syscall)(__NR_close, fd);
}


Int VG_(read) ( Int fd, void* buf, Int count)
{
   Int res;
   /* res = read( fd, buf, count ); */
   res = VG_(do_syscall)(__NR_read, fd, (UInt)buf, count);
   /* return -ERRNO on error */
   return res;
}

Int VG_(write) ( Int fd, const void* buf, Int count)
{
   Int res;
   /* res = write( fd, buf, count ); */
   res = VG_(do_syscall)(__NR_write, fd, (UInt)buf, count);
   /* return -ERRNO on error */
   return res;
}

Int VG_(lseek) ( Int fd, Long offset, Int whence)
{
   Int res;
   /* res = lseek( fd, offset, whence ); */
   res = VG_(do_syscall)(__NR_lseek, fd, (UInt)offset, whence);
   if (VG_(is_kerror)(res)) res = -1;
   return res;
}

Int VG_(stat) ( Char* file_name, struct vki_stat* buf )
{
   Int res;
   res = VG_(do_syscall)(__NR_stat, (UInt)file_name, (UInt)buf);
   return res;			/* return -ve error */
}

Int VG_(fstat) ( Int fd, struct vki_stat* buf )
{
   Int res;
   res = VG_(do_syscall)(__NR_fstat, (UInt)fd, (UInt)buf);
   return VG_(is_kerror)(res) ? (-1) : 0;
}

Int VG_(dup2) ( Int oldfd, Int newfd )
{
   Int res;
   res = VG_(do_syscall)(__NR_dup2, (UInt)oldfd, (UInt)newfd);
   return VG_(is_kerror)(res) ? (-1) : res;
}

Int VG_(rename) ( Char* old_name, Char* new_name )
{
   Int res;
   res = VG_(do_syscall)(__NR_rename, (UInt)old_name, (UInt)new_name);
   return VG_(is_kerror)(res) ? (-1) : 0;
}

Int VG_(unlink) ( Char* file_name )
{
   Int res;
   res = VG_(do_syscall)(__NR_unlink, (UInt)file_name);
   return VG_(is_kerror)(res) ? (-1) : 0;
}

/* Nb: we do not allow the Linux extension which malloc()s memory for the
   buffer if buf==NULL, because we don't want Linux calling malloc() */
Char* VG_(getcwd) ( Char* buf, Int size )
{
   Int res;
   vg_assert(buf != NULL);
   res = VG_(do_syscall)(__NR_getcwd, (UInt)buf, (UInt)size);
   return VG_(is_kerror)(res) ? ((Char*)NULL) : (Char*)res;
}

/* Alternative version that does allocate the memory.  Easier to use. */
Bool VG_(getcwd_alloc) ( Char** out )
{
   UInt size = 4;

   *out = NULL;
   while (True) {
      *out = VG_(malloc)(size);
      if (NULL == VG_(getcwd)(*out, size)) {
         VG_(free)(*out);
         if (size > 65535)
            return False;
         size *= 2;
      } else {
         return True;
      }
   }
}


/* ---------------------------------------------------------------------
   Misc functions looking for a proper home.
   ------------------------------------------------------------------ */

/* clone the environment */
static Char **env_clone ( Char **oldenv )
{
   Char **oldenvp;
   Char **newenvp;
   Char **newenv;
   Int  envlen;

   for (oldenvp = oldenv; oldenvp && *oldenvp; oldenvp++);

   envlen = oldenvp - oldenv + 1;
   
   newenv = VG_(arena_malloc)(VG_AR_CORE, envlen * sizeof(Char **));

   oldenvp = oldenv;
   newenvp = newenv;
   
   while (oldenvp && *oldenvp) {
      *newenvp++ = *oldenvp++;
   }
   
   *newenvp = *oldenvp;

   return newenv;
}

void  VG_(env_unsetenv) ( Char **env, const Char *varname )
{
   Char **from;
   Char **to = NULL;
   Int len = VG_(strlen)(varname);

   for(from = to = env; from && *from; from++) {
      if (!(VG_(strncmp)(varname, *from, len) == 0 && (*from)[len] == '=')) {
	 *to = *from;
	 to++;
      }
   }
   *to = *from;
}

/* set the environment; returns the old env if a new one was allocated */
Char **VG_(env_setenv) ( Char ***envp, const Char* varname, const Char *val )
{
   Char **env = (*envp);
   Char **cpp;
   Int len = VG_(strlen)(varname);
   Char *valstr = VG_(arena_malloc)(VG_AR_CORE, len + VG_(strlen)(val) + 2);
   Char **oldenv = NULL;

   VG_(sprintf)(valstr, "%s=%s", varname, val);

   for(cpp = env; cpp && *cpp; cpp++) {
      if (VG_(strncmp)(varname, *cpp, len) == 0 && (*cpp)[len] == '=') {
	 *cpp = valstr;
	 return oldenv;
      }
   }

   if (env == NULL) {
      env = VG_(arena_malloc)(VG_AR_CORE, sizeof(Char **) * 2);
      env[0] = valstr;
      env[1] = NULL;

      *envp = env;

   }  else {
      Int envlen = (cpp-env) + 2;
      Char **newenv = VG_(arena_malloc)(VG_AR_CORE, envlen * sizeof(Char **));

      for(cpp = newenv; *env; )
	 *cpp++ = *env++;
      *cpp++ = valstr;
      *cpp++ = NULL;

      oldenv = *envp;

      *envp = newenv;
   }

   return oldenv;
}

/* We do getenv without libc's help by snooping around in
   VG_(client_envp) as determined at startup time. */
Char *VG_(getenv)(Char *varname)
{
   Int i, n;
   n = VG_(strlen)(varname);
   for (i = 0; VG_(client_envp)[i] != NULL; i++) {
      Char* s = VG_(client_envp)[i];
      if (VG_(strncmp)(varname, s, n) == 0 && s[n] == '=') {
         return & s[n+1];
      }
   }
   return NULL;
}

/* Support for getrlimit. */
Int VG_(getrlimit) (Int resource, struct vki_rlimit *rlim)
{
   Int res;
   /* res = getrlimit( resource, rlim ); */
   res = VG_(do_syscall)(__NR_getrlimit, (UInt)resource, (UInt)rlim);
   if(VG_(is_kerror)(res)) res = -1;
   return res;
}


/* Support for setrlimit. */
Int VG_(setrlimit) (Int resource, struct vki_rlimit *rlim)
{
   Int res;
   /* res = setrlimit( resource, rlim ); */
   res = VG_(do_syscall)(__NR_setrlimit, (UInt)resource, (UInt)rlim);
   if(VG_(is_kerror)(res)) res = -1;
   return res;
}


/* Support for getdents. */
Int VG_(getdents) (UInt fd, struct vki_dirent *dirp, UInt count)
{
   Int res;
   /* res = getdents( fd, dirp, count ); */
   res = VG_(do_syscall)(__NR_getdents, fd, (UInt)dirp, count);
   if (VG_(is_kerror)(res)) res = -1;
   return res;
}

/* Support for a readlink.  */
Int VG_(readlink) (Char* path, Char* buf, UInt bufsiz)
{
   Int res;
   /* res = readlink( path, buf, bufsiz ); */
   res = VG_(do_syscall)(__NR_readlink, (UInt)path, (UInt)buf, bufsiz);
   if (VG_(is_kerror)(res)) res = -1;
   return res;
}

/* You'd be amazed how many places need to know the current pid. */
Int VG_(getpid) ( void )
{
   Int res;
   /* res = getpid(); */
   res = VG_(do_syscall)(__NR_getpid);
   return res;
}

Int VG_(getpgrp) ( void )
{
   Int res;
   /* res = getpgid(); */
   res = VG_(do_syscall)(__NR_getpgrp);
   return res;
}

Int VG_(getppid) ( void )
{
   Int res;
   res = VG_(do_syscall)(__NR_getppid);
   return res;
}

Int VG_(setpgid) ( Int pid, Int pgrp )
{
   return VG_(do_syscall)(__NR_setpgid, pid, pgrp);
}

/* Walk through a colon-separated environment variable, and remove the
   entries which match remove_pattern.  It slides everything down over
   the removed entries, and pads the remaining space with '\0'.  It
   modifies the entries in place (in the client address space), but it
   shouldn't matter too much, since we only do this just before an
   execve().

   This is also careful to mop up any excess ':'s, since empty strings
   delimited by ':' are considered to be '.' in a path.
*/
static void mash_colon_env(Char *varp, const Char *remove_pattern)
{
   Char *const start = varp;
   Char *entry_start = varp;
   Char *output = varp;

   if (varp == NULL)
      return;

   while(*varp) {
      if (*varp == ':') {
	 Char prev;
	 Bool match;

	 /* This is a bit subtle: we want to match against the entry
	    we just copied, because it may have overlapped with
	    itself, junking the original. */

	 prev = *output;
	 *output = '\0';

	 match = VG_(string_match)(remove_pattern, entry_start);

	 *output = prev;
	 
	 if (match) {
	    output = entry_start;
	    varp++;			/* skip ':' after removed entry */
	 } else
	    entry_start = output+1;	/* entry starts after ':' */
      }

      *output++ = *varp++;
   }

   /* match against the last entry */
   if (VG_(string_match)(remove_pattern, entry_start)) {
      output = entry_start;
      if (output > start) {
	 /* remove trailing ':' */
	 output--;
	 vg_assert(*output == ':');
      }
   }	 

   /* pad out the left-overs with '\0' */
   while(output < varp)
      *output++ = '\0';
}


// Removes all the Valgrind-added stuff from the passed environment.  Used
// when starting child processes, so they don't see that added stuff.
void VG_(env_remove_valgrind_env_stuff)(Char** envp)
{
   Int i;
   Char* ld_preload_str = NULL;
   Char* ld_library_path_str = NULL;
   Char* buf;

   // Find LD_* variables
   for (i = 0; envp[i] != NULL; i++) {
      if (VG_(strncmp)(envp[i], "LD_PRELOAD=", 11) == 0)
         ld_preload_str = &envp[i][11];
      if (VG_(strncmp)(envp[i], "LD_LIBRARY_PATH=", 16) == 0)
         ld_library_path_str = &envp[i][16];
   }

   buf = VG_(arena_malloc)(VG_AR_CORE, VG_(strlen)(VG_(libdir)) + 20);

   // Remove Valgrind-specific entries from LD_*.
   VG_(sprintf)(buf, "%s*/vg_inject.so", VG_(libdir));
   mash_colon_env(ld_preload_str, buf);
   VG_(sprintf)(buf, "%s*/vgpreload_*.so", VG_(libdir));
   mash_colon_env(ld_preload_str, buf);
   VG_(sprintf)(buf, "%s*", VG_(libdir));
   mash_colon_env(ld_library_path_str, buf);

   // Remove VALGRIND_CLO variable.
   VG_(env_unsetenv)(envp, VALGRINDCLO);

   // XXX if variable becomes empty, remove it completely?

   VG_(arena_free)(VG_AR_CORE, buf);
}

/* Return -1 if error, else 0.  NOTE does not indicate return code of
   child! */
Int VG_(system) ( Char* cmd )
{
   Int pid, res;
   if (cmd == NULL)
      return 1;
   pid = VG_(do_syscall)(__NR_fork);
   if (VG_(is_kerror)(pid))
      return -1;
   if (pid == 0) {
      /* child */
      static Char** envp = NULL;
      Char* argv[4];

      /* restore the DATA rlimit for the child */
      VG_(setrlimit)(VKI_RLIMIT_DATA, &VG_(client_rlimit_data));

      envp = env_clone(VG_(client_envp));
      VG_(env_remove_valgrind_env_stuff)( envp ); 

      argv[0] = "/bin/sh";
      argv[1] = "-c";
      argv[2] = cmd;
      argv[3] = 0;

      (void)VG_(do_syscall)(__NR_execve, 
                            (UInt)"/bin/sh", (UInt)argv, (UInt)envp);

      /* If we're still alive here, execve failed. */
      VG_(exit)(1);
   } else {
      /* parent */
      res = VG_(waitpid)(pid, NULL, 0);
      if (VG_(is_kerror)(res)) {
         return -1;
      } else {
	 return 0;
      }
   }
}


/* ---------------------------------------------------------------------
   Support for a millisecond-granularity timer.
   ------------------------------------------------------------------ */

UInt VG_(read_millisecond_timer) ( void )
{
   static ULong base = 0;
   struct vki_timeval tv_now;
   ULong now;
   Int res;

   res = VG_(do_syscall)(__NR_gettimeofday, (UInt)&tv_now, 
			 (UInt)NULL);
   
   now = tv_now.tv_sec * 1000000ULL + tv_now.tv_usec;
   
   if (base == 0)
      base = now;

   return (now - base) / 1000;
}


/* ---------------------------------------------------------------------
   Primitive support for bagging memory via mmap.
   ------------------------------------------------------------------ */

void* VG_(get_memory_from_mmap) ( Int nBytes, Char* who )
{
   static UInt tot_alloc = 0;
   void* p;
   p = VG_(mmap)(0, nBytes,
                 VKI_PROT_READ|VKI_PROT_WRITE|VKI_PROT_EXEC,
                 VKI_MAP_PRIVATE|VKI_MAP_ANONYMOUS, 0, -1, 0);

   if (p != ((void*)(-1))) {
      vg_assert((void*)VG_(valgrind_base) <= p && p <= (void*)VG_(valgrind_last));
      tot_alloc += (UInt)nBytes;
      if (0)
         VG_(printf)(
            "get_memory_from_mmap: %d tot, %d req = %p .. %p, caller %s\n",
            tot_alloc, nBytes, p, ((char*)p) + nBytes - 1, who );
      return p;
   }

   VG_(printf)("\n");
   VG_(printf)("VG_(get_memory_from_mmap): %s's request for %d bytes failed.\n",
               who, nBytes);
   VG_(printf)("VG_(get_memory_from_mmap): %d bytes already allocated.\n", 
               tot_alloc);
   VG_(printf)("\n");
   VG_(printf)("Sorry.  You could try using a tool that uses less memory;\n");
   VG_(printf)("eg. addrcheck instead of memcheck.\n");
   VG_(printf)("\n");
   VG_(exit)(1);
}

/* ---------------------------------------------------------------------
   Generally useful...
   ------------------------------------------------------------------ */

Int VG_(log2) ( Int x ) 
{
   Int i;
   /* Any more than 32 and we overflow anyway... */
   for (i = 0; i < 32; i++) {
      if (1 << i == x) return i;
   }
   return -1;
}


// Generic shell sort.  Like stdlib.h's qsort().
void VG_(ssort)( void* base, UInt nmemb, UInt size,
                 Int (*compar)(void*, void*) )
{
   Int   incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
                      9841, 29524, 88573, 265720,
                      797161, 2391484 };
   Int   lo = 0;
   Int   hi = nmemb-1;
   Int   i, j, h, bigN, hp;

   bigN = hi - lo + 1; if (bigN < 2) return;
   hp = 0; while (hp < 14 && incs[hp] < bigN) hp++; hp--;
   vg_assert(0 <= hp && hp < 14);

   #define SORT \
   for ( ; hp >= 0; hp--) { \
      h = incs[hp]; \
      for (i = lo + h; i <= hi; i++) { \
         ASSIGN(v,0, a,i); \
         j = i; \
         while (COMPAR(a,(j-h), v,0) > 0) { \
            ASSIGN(a,j, a,(j-h)); \
            j = j - h; \
            if (j <= (lo + h - 1)) break; \
         } \
         ASSIGN(a,j, v,0); \
      } \
   }

   // Specialised cases
   if (sizeof(UInt) == size) {

      #define ASSIGN(dst, dsti, src, srci) \
      (dst)[(dsti)] = (src)[(srci)];      
      
      #define COMPAR(dst, dsti, src, srci) \
      compar( (void*)(& (dst)[(dsti)]), (void*)(& (src)[(srci)]) )

      UInt* a = (UInt*)base;
      UInt  v[1];

      SORT;

   } else if (sizeof(UShort) == size) {
      UShort* a = (UShort*)base;
      UShort  v[1];

      SORT;

   } else if (sizeof(UChar) == size) {
      UChar* a = (UChar*)base;
      UChar  v[1];

      SORT;

      #undef ASSIGN
      #undef COMPAR

   // General case
   } else {
      char* a = base;
      char  v[size];      // will be at least 'size' bytes

      #define ASSIGN(dst, dsti, src, srci) \
      VG_(memcpy)( &dst[size*(dsti)], &src[size*(srci)], size );

      #define COMPAR(dst, dsti, src, srci) \
      compar( &dst[size*(dsti)], &src[size*(srci)] )

      SORT;

      #undef ASSIGN
      #undef COMPAR
   }
   #undef SORT
}

/* ---------------------------------------------------------------------
   Gruesome hackery for connecting to a logging server over the network.
   This is all very Linux-kernel specific.
   ------------------------------------------------------------------ */

/* Various needed constants from the kernel iface (2.4),
   /usr/src/linux-2.4.9-31 */

/* kernel, ./include/linux/net.h */
#define SYS_SOCKET      1              /* sys_socket(2)        */
#define SYS_CONNECT     3              /* sys_connect(2)       */
#define SYS_GETSOCKNAME 6              /* sys_getsockname(2)   */
#define SYS_GETPEERNAME 7              /* sys_getpeername(2)   */
#define SYS_SEND        9              /* sys_send(2)          */
#define SYS_GETSOCKOPT  15             /* sys_getsockopt(2)    */

typedef UInt __u32;

/* Internet address. */
struct vki_in_addr {
        __u32   s_addr;
};

/* kernel, include/linux/socket.h */
#define AF_INET                2       /* Internet IP Protocol        */
#define MSG_NOSIGNAL           0x4000  /* Do not generate SIGPIPE */

/* kernel, ./include/asm-i386/socket.h */
#define SOCK_STREAM 1                  /* stream (connection) socket  */

/* kernel, /usr/src/linux-2.4.9-31/linux/include/in.h */
/* Structure describing an Internet (IP) socket address. */
#define __SOCK_SIZE__   16              /* sizeof(struct sockaddr)      */
struct vki_sockaddr_in {
  vki_sa_family_t       sin_family;     /* Address family               */
  unsigned short int    sin_port;       /* Port number                  */
  struct vki_in_addr    sin_addr;       /* Internet address             */

  /* Pad to size of `struct sockaddr'. */
  unsigned char         __pad[__SOCK_SIZE__ - sizeof(short int) -
                        sizeof(unsigned short int) - 
                        sizeof(struct vki_in_addr)];
};


static
Int parse_inet_addr_and_port ( UChar* str, UInt* ip_addr, UShort* port );

static
Int my_socket ( Int domain, Int type, Int protocol );

static
Int my_connect ( Int sockfd, struct vki_sockaddr_in* serv_addr, 
                 Int addrlen );

static 
UInt my_htonl ( UInt x )
{
   return
      (((x >> 24) & 0xFF) << 0) | (((x >> 16) & 0xFF) << 8)
      | (((x >> 8) & 0xFF) << 16) | (((x >> 0) & 0xFF) << 24);
}

static
UShort my_htons ( UShort x )
{
   return
      (((x >> 8) & 0xFF) << 0) | (((x >> 0) & 0xFF) << 8);
}


/* The main function. 

   Supplied string contains either an ip address "192.168.0.1" or
   an ip address and port pair, "192.168.0.1:1500".  Parse these,
   and return:
     -1 if there is a parse error
     -2 if no parse error, but specified host:port cannot be opened
     the relevant file (socket) descriptor, otherwise.
 is used.
*/
Int VG_(connect_via_socket)( UChar* str )
{
   Int sd, res;
   struct vki_sockaddr_in servAddr;
   UInt   ip   = 0;
   UShort port = VG_CLO_DEFAULT_LOGPORT;
   Bool   ok   = parse_inet_addr_and_port(str, &ip, &port);
   if (!ok) 
      return -1;

   if (0)
      VG_(printf)("ip = %d.%d.%d.%d, port %d\n",
                  (ip >> 24) & 0xFF, (ip >> 16) & 0xFF, 
                  (ip >> 8) & 0xFF, ip & 0xFF, 
	          (UInt)port );

   servAddr.sin_family = AF_INET;
   servAddr.sin_addr.s_addr = my_htonl(ip);
   servAddr.sin_port = my_htons(port);

   /* create socket */
   sd = my_socket(AF_INET, SOCK_STREAM, 0 /* IPPROTO_IP ? */);
   if (sd < 0) {
     /* this shouldn't happen ... nevertheless */
     return -2;
   }
			
   /* connect to server */
   res = my_connect(sd, (struct vki_sockaddr_in *) &servAddr, 
                        sizeof(servAddr));
   if (res < 0) {
     /* connection failed */
     return -2;
   }

   return sd;
}


/* Let d = one or more digits.  Accept either:
   d.d.d.d  or  d.d.d.d:d
*/
Int parse_inet_addr_and_port ( UChar* str, UInt* ip_addr, UShort* port )
{
#  define GET_CH ((*str) ? (*str++) : 0)
   UInt ipa, i, j, c, any;
   ipa = 0;
   for (i = 0; i < 4; i++) {
      j = 0;
      any = 0;
      while (1) {
         c = GET_CH; 
         if (c < '0' || c > '9') break;
         j = 10 * j + (int)(c - '0');
         any = 1;
      }
      if (any == 0 || j > 255) goto syntaxerr;
      ipa = (ipa << 8) + j;
      if (i <= 2 && c != '.') goto syntaxerr;
   }
   if (c == 0 || c == ':') 
      *ip_addr = ipa;
   if (c == 0) goto ok;
   if (c != ':') goto syntaxerr;
   j = 0;
   any = 0;
   while (1) {
      c = GET_CH; 
      if (c < '0' || c > '9') break;
      j = j * 10 + (int)(c - '0');
      any = 1;
      if (j > 65535) goto syntaxerr;
   }
   if (any == 0 || c != 0) goto syntaxerr;
   if (j < 1024) goto syntaxerr;
   *port = (UShort)j;
 ok:
   return 1;
 syntaxerr:
   return 0;
#  undef GET_CH
}


static
Int my_socket ( Int domain, Int type, Int protocol )
{
   Int res;
   UInt args[3];
   args[0] = domain;
   args[1] = type;
   args[2] = protocol;
   res = VG_(do_syscall)(__NR_socketcall, SYS_SOCKET, (UInt)&args);
   if (VG_(is_kerror)(res)) 
      res = -1;
   return res;
}

static
Int my_connect ( Int sockfd, struct vki_sockaddr_in* serv_addr, 
                 Int addrlen )
{
   Int res;
   UInt args[3];
   args[0] = sockfd;
   args[1] = (UInt)serv_addr;
   args[2] = addrlen;
   res = VG_(do_syscall)(__NR_socketcall, SYS_CONNECT, (UInt)&args);
   if (VG_(is_kerror)(res)) 
      res = -1;
   return res;
}

Int VG_(write_socket)( Int sd, void *msg, Int count )
{
   /* This is actually send(). */

   /* Requests not to send SIGPIPE on errors on stream oriented
      sockets when the other end breaks the connection. The EPIPE
      error is still returned. */
   Int flags = MSG_NOSIGNAL;

   Int res;
   UInt args[4];
   args[0] = sd;
   args[1] = (UInt)msg;
   args[2] = count;
   args[3] = flags;
   res = VG_(do_syscall)(__NR_socketcall, SYS_SEND, (UInt)&args);
   if (VG_(is_kerror)(res)) 
      res = -1;
   return res;
}

Int VG_(getsockname) ( Int sd, struct vki_sockaddr *name, Int *namelen)
{
   Int res;
   UInt args[3];
   args[0] = sd;
   args[1] = (UInt)name;
   args[2] = (UInt)namelen;
   res = VG_(do_syscall)(__NR_socketcall, SYS_GETSOCKNAME, (UInt)&args);
   if(VG_(is_kerror)(res))
      res = -1;
   return res;
}

Int VG_(getpeername) ( Int sd, struct vki_sockaddr *name, Int *namelen)
{
   Int res;
   UInt args[3];
   args[0] = sd;
   args[1] = (UInt)name;
   args[2] = (UInt)namelen;
   res = VG_(do_syscall)(__NR_socketcall, SYS_GETPEERNAME, (UInt)&args);
   if(VG_(is_kerror)(res))
      res = -1;
   return res;
}

Int VG_(getsockopt) ( Int sd, Int level, Int optname, void *optval,
                      Int *optlen)
{
   Int res;
   UInt args[5];
   args[0] = sd;
   args[1] = (UInt)level;
   args[2] = (UInt)optname;
   args[3] = (UInt)optval;
   args[4] = (UInt)optlen;
   res = VG_(do_syscall)(__NR_socketcall, SYS_GETSOCKOPT, (UInt)&args);
   if(VG_(is_kerror)(res))
      res = -1;
   return res;
}


/*--------------------------------------------------------------------*/
/*--- end                                              vg_mylibc.c ---*/
/*--------------------------------------------------------------------*/