// @(#)root/base:$Id$
// Author: Fons Rademakers   30/9/2001

/*************************************************************************
 * Copyright (C) 1995-2001, Rene Brun and Fons Rademakers.               *
 * All rights reserved.                                                  *
 *                                                                       *
 * For the licensing terms see $ROOTSYS/LICENSE.                         *
 * For the list of contributors see $ROOTSYS/README/CREDITS.             *
 *************************************************************************/

//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TUUID                                                                //
//                                                                      //
// This class defines a UUID (Universally Unique IDentifier), also      //
// known as GUIDs (Globally Unique IDentifier). A UUID is 128 bits      //
// long, and if generated according to this algorithm, is either        //
// guaranteed to be different from all other UUIDs/GUIDs generated      //
// until 3400 A.D. or extremely likely to be different. UUIDs were      //
// originally used in the Network Computing System (NCS) and            //
// later in the Open Software Foundation's (OSF) Distributed Computing  //
// Environment (DCE).                                                   //
//                                                                      //
// Structure of universal unique IDs (UUIDs).                           //
//                                                                      //
// Depending on the network data representation, the multi-             //
// octet unsigned integer fields are subject to byte swapping           //
// when communicated between dissimilar endian machines.                //
//                                                                      //
// +-----------------------------------+                                //
// |     low 32 bits of time           |  0-3   .fTimeLow               //
// +-------------------------------+----                                //
// |     mid 16 bits of time       |      4-5   .fTimeMid               //
// +-------+-----------------------+                                    //
// | vers. |   hi 12 bits of time  |      6-7   .fTimeHiAndVersion      //
// +-------+-------+---------------+                                    //
// |Res | clkSeqHi |                      8     .fClockSeqHiAndReserved //
// +---------------+                                                    //
// |   clkSeqLow   |                      9     .fClockSeqLow           //
// +---------------+------------------+                                 //
// |            node ID               |   10-15 .fNode                  //
// +----------------------------------+                                 //
//                                                                      //
// The adjusted time stamp is split into three fields, and the          //
// clockSeq is split into two fields.                                   //
//                                                                      //
// The timestamp is a 60-bit value. For UUID version 1, this            //
// is represented by Coordinated Universal Time (UTC/GMT) as            //
// a count of 100-nanosecond intervals since 00:00:00.00,               //
// 15 October 1582 (the date of Gregorian reform to the                 //
// Christian calendar).                                                 //
//                                                                      //
// The version number is multiplexed in the 4 most significant          //
// bits of the 'fTimeHiAndVersion' field. There are two defined         //
// versions:                                                            //
//               MSB <---                                               //
// Version      4-Bit Code      Description                             //
// ------------------------------------------------------------         //
// |  1           0 0 0 1     DCE version, as specified herein.         //
// |  2           0 0 1 0     DCE Security version, with                //
// |                          embedded POSIX UIDs.                      //
// |  3           0 0 1 1     node id is a random value                 //
// ------------------------------------------------------------         //
//                                                                      //
// Clock Sequence                                                       //
//                                                                      //
// The clock sequence value must be changed whenever:                   //
//                                                                      //
//    The UUID generator detects that the local value of UTC            //
//    has gone backward; this may be due to re-syncing of the system    //
//    clock.                                                            //
//                                                                      //
// While a node is operational, the UUID service always saves           //
// the last UTC used to create a UUID. Each time a new UUID             //
// is created, the current UTC is compared to the saved value           //
// and if either the current value is less or the saved value           //
// was lost, then the clock sequence is incremented modulo              //
// 16,384, thus avoiding production of duplicted UUIDs.                 //
//                                                                      //
// The clock sequence must be initialized to a random number            //
// to minimize the correlation across system. This provides             //
// maximum protection against node identifiers that may move            //
// or switch from system to system rapidly.                             //
//                                                                      //
// Clock Adjustment                                                     //
//                                                                      //
// UUIDs may be created at a rate greater than the system clock         //
// resolution. Therefore, the system must also maintain an              //
// adjustment value to be added to the lower-order bits of the          //
// time. Logically, each time the system clock ticks, the               //
// adjustment value is cleared. Every time a UUID is generated,         //
// the current adjustment value is read and incremented, and            //
// then added to the UTC time field of the UUID.                        //
//                                                                      //
// Clock Overrun                                                        //
//                                                                      //
// The 100-nanosecond granularity of time should prove sufficient       //
// even for bursts of UUID production in the next generation of         //
// high-performance multiprocessors. If a system overruns the           //
// clock adjustment by requesting too many UUIDs within a single        //
// system clock tick, the UUID generator will stall until the           //
// system clock catches up.                                             //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

#include "TROOT.h"
#include "TUUID.h"
#include "TError.h"
#include "TSystem.h"
#include "TInetAddress.h"
#include "TMD5.h"
#include "Bytes.h"
#include "TVirtualMutex.h"
#include "ThreadLocalStorage.h"
#include <string.h>
#include <stdlib.h>
#ifdef R__WIN32
#include "Windows4Root.h"
#include <Iphlpapi.h>
#else
#include <unistd.h>
#include <sys/time.h>
#if defined(R__LINUX) && !defined(R__WINGCC)
#include <sys/sysinfo.h>
#endif
#endif


ClassImp(TUUID)

//______________________________________________________________________________
TUUID::TUUID()
{
   // Create a UUID.

   TTHREAD_TLS(uuid_time_t) time_last;
   TTHREAD_TLS(UShort_t) clockseq(0);
   TTHREAD_TLS(Bool_t) firstTime(kTRUE);
   uuid_time_t *time_last_ptr = TTHREAD_TLS_PTR(time_last);

   if (firstTime) {
      R__LOCKGUARD2(gROOTMutex); // rand and random are not thread safe.

      if (gSystem) {
         // try to get a unique seed per process
         UInt_t seed = (UInt_t) (Long64_t(gSystem->Now()) + gSystem->GetPid());
#ifdef R__WIN32
         srand(seed);
#else
         srandom(seed);
#endif
      }
      GetCurrentTime(time_last_ptr);
#ifdef R__WIN32
      clockseq = 1+(UShort_t)(65536*rand()/(RAND_MAX+1.0));
#else
      clockseq = 1+(UShort_t)(65536*random()/(RAND_MAX+1.0));
#endif
      firstTime = kFALSE;
   }

   uuid_time_t timestamp;

   // get current time
   GetCurrentTime(&timestamp);

   // if clock went backward change clockseq
   if (CmpTime(&timestamp, time_last_ptr) == -1) {
      clockseq = (clockseq + 1) & 0x3FFF;
      if (clockseq == 0) clockseq++;
   }

   Format(clockseq, timestamp);

   time_last = timestamp;
   fUUIDIndex = 1<<30;
}

//______________________________________________________________________________
TUUID::~TUUID()
{
   // delete this TUUID

   //gROOT->GetUUIDs()->RemoveUUID(fUUIDIndex);
}

//______________________________________________________________________________
Int_t TUUID::CmpTime(uuid_time_t *t1, uuid_time_t *t2)
{
   // Compare two time values.

   if (t1->high < t2->high) return -1;
   if (t1->high > t2->high) return 1;
   if (t1->low  < t2->low)  return -1;
   if (t1->low  > t2->low)  return 1;
   return 0;
}

//______________________________________________________________________________
void TUUID::SetFromString(const char *uuid)
{
   // Set this UUID to the value specified in uuid ((which must be in
   // TUUID::AsString() format).

   // Format is tttttttt-tttt-cccc-cccc-nnnnnnnnnnnn.
   Long_t  timeLo;
   int     timeMid;
   int     timeHiAndVersion;
   int     clockSeqHiAndRes;
   int     clockSeqLo;
   int     node[6];

   sscanf(uuid, "%8lx-%4x-%4x-%2x%2x-%2x%2x%2x%2x%2x%2x",
          &timeLo,
          &timeMid,
          &timeHiAndVersion,
          &clockSeqHiAndRes,
          &clockSeqLo,
          &node[0], &node[1], &node[2], &node[3], &node[4], &node[5]);

   // Note that we're going through this agony because scanf is
   // defined to know only to scan into "int"s or "long"s.
   fTimeLow               = (UInt_t) timeLo;
   fTimeMid               = (UShort_t) timeMid;
   fTimeHiAndVersion      = (UShort_t) timeHiAndVersion;
   fClockSeqHiAndReserved = (UChar_t) clockSeqHiAndRes;
   fClockSeqLow           = (UChar_t) clockSeqLo;
   fNode[0]               = (UChar_t) node[0];
   fNode[1]               = (UChar_t) node[1];
   fNode[2]               = (UChar_t) node[2];
   fNode[3]               = (UChar_t) node[3];
   fNode[4]               = (UChar_t) node[4];
   fNode[5]               = (UChar_t) node[5];
   fUUIDIndex             = 1<<30;
}

//______________________________________________________________________________
TUUID::TUUID(const char *uuid)
{
   // Initialize a TUUID with uuid (which must be in TUUID::AsString() format).

   fTimeLow               = 0;
   fTimeMid               = 0;
   fTimeHiAndVersion      = 0;
   fClockSeqHiAndReserved = 0;
   fClockSeqLow           = 0;
   fNode[0]               = 0;
   fUUIDIndex             = 0;

   if (!uuid || !*uuid)
      Error("TUUID", "null string not allowed");
   else
      SetFromString(uuid);
}

//______________________________________________________________________________
void TUUID::FillBuffer(char *&buffer)
{
   // Stream UUID into output buffer.

   Version_t version = TUUID::Class_Version();
   tobuf(buffer, version);
   tobuf(buffer, fTimeLow);
   tobuf(buffer, fTimeMid);
   tobuf(buffer, fTimeHiAndVersion);
   tobuf(buffer, fClockSeqHiAndReserved);
   tobuf(buffer, fClockSeqLow);
   for (Int_t i = 0; i < 6; i++)
      tobuf(buffer, fNode[i]);
}

//______________________________________________________________________________
void TUUID::ReadBuffer(char *&buffer)
{
   // Stream UUID from input buffer.

   Version_t version;
   frombuf(buffer, &version);
   frombuf(buffer, &fTimeLow);
   frombuf(buffer, &fTimeMid);
   frombuf(buffer, &fTimeHiAndVersion);
   frombuf(buffer, &fClockSeqHiAndReserved);
   frombuf(buffer, &fClockSeqLow);
   for (Int_t i = 0; i < 6; i++)
      frombuf(buffer, &fNode[i]);
}

//______________________________________________________________________________
void TUUID::StreamerV1(TBuffer &b)
{
   // Stream UUID from input buffer.
   // This function is for the exclusive use of TDirectory::Streamer() to
   // read a non-versioned version of TUUID.

   b >> fTimeLow;
   b >> fTimeMid;
   b >> fTimeHiAndVersion;
   b >> fClockSeqHiAndReserved;
   b >> fClockSeqLow;
   for (UInt_t i = 0; i < 6; i++) {
      b >> fNode[i];
   }
}

//______________________________________________________________________________
void TUUID::Format(UShort_t clockseq, uuid_time_t ts)
{
   // Make a UUID from timestamp, clockseq and node id.

   fTimeLow = ts.low;
   fTimeMid = (UShort_t)(ts.high & 0xFFFF);
   fTimeHiAndVersion = (UShort_t)((ts.high >> 16) & 0x0FFF);
   fTimeHiAndVersion |= (1 << 12);
   fClockSeqLow = clockseq & 0xFF;
   fClockSeqHiAndReserved = (clockseq & 0x3F00) >> 8;
   fClockSeqHiAndReserved |= 0x80;
   GetNodeIdentifier();
}

//______________________________________________________________________________
void TUUID::GetCurrentTime(uuid_time_t *timestamp)
{
   // Get current time as 60 bit 100ns ticks since whenever.
   // Compensate for the fact that real clock resolution is less
   // than 100ns.

   const UShort_t uuids_per_tick = 1024;

   TTHREAD_TLS(uuid_time_t) time_last;
   TTHREAD_TLS(UShort_t)    uuids_this_tick(0);
   TTHREAD_TLS(Bool_t)      init(kFALSE);

   uuid_time_t *time_last_ptr = TTHREAD_TLS_PTR(time_last);

   if (!init) {
      GetSystemTime(time_last_ptr);
      uuids_this_tick = uuids_per_tick;
      init = kTRUE;
   }

   uuid_time_t time_now;

   while (1) {
      GetSystemTime(&time_now);

      // if clock reading changed since last UUID generated
      if (CmpTime(time_last_ptr, &time_now))  {
         // reset count of uuid's generated with this clock reading
         uuids_this_tick = 0;
         break;
      }
      if (uuids_this_tick < uuids_per_tick) {
         uuids_this_tick++;
         break;
      }
      // going too fast for our clock; spin
   }

   time_last = time_now;

   if (uuids_this_tick != 0) {
      if (time_now.low & 0x80000000) {
         time_now.low += uuids_this_tick;
         if (!(time_now.low & 0x80000000))
            time_now.high++;
      } else
         time_now.low += uuids_this_tick;
   }

   timestamp->high = time_now.high;
   timestamp->low  = time_now.low;
}

//______________________________________________________________________________
void TUUID::GetSystemTime(uuid_time_t *timestamp)
{
   // Get system time with 100ns precision. Time is since Oct 15, 1582.

#ifdef R__WIN32
   ULARGE_INTEGER time;
   GetSystemTimeAsFileTime((FILETIME *)&time);
   // NT keeps time in FILETIME format which is 100ns ticks since
   // Jan 1, 1601. UUIDs use time in 100ns ticks since Oct 15, 1582.
   // The difference is 17 Days in Oct + 30 (Nov) + 31 (Dec)
   // + 18 years and 5 leap days.
   time.QuadPart +=
            (unsigned __int64) (1000*1000*10)       // seconds
          * (unsigned __int64) (60 * 60 * 24)       // days
          * (unsigned __int64) (17+30+31+365*18+5); // # of days

   timestamp->high = time.HighPart;
   timestamp->low  = time.LowPart;
#else
   struct timeval tp;
   gettimeofday(&tp, 0);
   // Offset between UUID formatted times and Unix formatted times.
   // UUID UTC base time is October 15, 1582.
   // Unix base time is January 1, 1970.
   ULong64_t uuid_time = ((ULong64_t)tp.tv_sec * 10000000) + (tp.tv_usec * 10) +
                         0x01B21DD213814000LL;
   timestamp->high = (UInt_t) (uuid_time >> 32);
   timestamp->low  = (UInt_t) (uuid_time & 0xFFFFFFFF);
#endif
}

//______________________________________________________________________________
void TUUID::GetNodeIdentifier()
{
   // Get node identifier. Try first to get network address, if no
   // network interface try random info based on some machine parameters.

   static UInt_t adr = 0;

   if (gSystem) {
#ifndef R__WIN32
      if (!adr) {
         TInetAddress addr = gSystem->GetHostByName(gSystem->HostName());
         if (addr.IsValid())
            adr = addr.GetAddress();
         else
            adr = 1;  // illegal address
      }
#else
      // this way to get the machine's IP address is needed because
      // GetHostByName() on Win32 contacts the DNS which we don't want
      // as firewall tools like ZoneAlarm are likely to catch it and
      // alarm the user
      if (!adr) {
         PIP_ADAPTER_INFO ainfo = (PIP_ADAPTER_INFO) malloc(sizeof(IP_ADAPTER_INFO));
         ULONG buflen = sizeof(IP_ADAPTER_INFO);
         DWORD stat = GetAdaptersInfo(ainfo, &buflen);
         if (stat == ERROR_BUFFER_OVERFLOW) {
            free(ainfo);
            ainfo = (PIP_ADAPTER_INFO) malloc(buflen);
            stat = GetAdaptersInfo(ainfo, &buflen);
         }
         if (stat != ERROR_SUCCESS)
            adr = 1;  // illegal address
         else {
            // take address of first adapter
            PIP_ADAPTER_INFO adapter = ainfo;
            int a, b, c, d;
            sscanf(adapter->IpAddressList.IpAddress.String, "%d.%d.%d.%d",
                   &a, &b, &c, &d);
            adr = (a << 24) | (b << 16) | (c << 8) | d;
         }
         free(ainfo);
      }
#endif
      if (adr > 2) {
         memcpy(fNode, &adr, 4);
         fNode[4] = 0xbe;
         fNode[5] = 0xef;
         return;
      }
   }
   static UChar_t seed[16];
   if (adr < 2) {
      GetRandomInfo(seed);
      seed[0] |= 0x80;
      if (gSystem) adr = 2;  // illegal address
   }
   memcpy(fNode, seed, sizeof(fNode));
   fTimeHiAndVersion |= (3 << 12);    // version == 3: random node info
}

//______________________________________________________________________________
void TUUID::GetRandomInfo(UChar_t seed[16])
{
   // Get random info based on some machine parameters.

#ifdef R__WIN32
   struct randomness {
      MEMORYSTATUS  m;
      SYSTEM_INFO   s;
      FILETIME      t;
      LARGE_INTEGER pc;
      DWORD         tc;
      DWORD         l;
      char          hostname[MAX_COMPUTERNAME_LENGTH + 1];
   };
   randomness r;
   memset(&r, 0, sizeof(r));  // zero also padding bytes

   // memory usage stats
   GlobalMemoryStatus(&r.m);
   // random system stats
   GetSystemInfo(&r.s);
   // 100ns resolution time of day
   GetSystemTimeAsFileTime(&r.t);
   // high resolution performance counter
   QueryPerformanceCounter(&r.pc);
   // milliseconds since last boot
   r.tc = GetTickCount();
   r.l = MAX_COMPUTERNAME_LENGTH + 1;
   GetComputerName(r.hostname, &r.l);
#else
   struct randomness {
#if defined(R__LINUX) && !defined(R__WINGCC)
      struct sysinfo   s;
#endif
      struct timeval   t;
      char             hostname[257];
   };
   randomness r;
   memset(&r, 0, sizeof(r));  // zero also padding bytes

#if defined(R__LINUX) && !defined(R__WINGCC)
   sysinfo(&r.s);
#endif
   gettimeofday(&r.t, 0);
   gethostname(r.hostname, 256);
#endif
   TMD5 md5;
   md5.Update((UChar_t *)&r, sizeof(randomness));
   md5.Final(seed);
}

//______________________________________________________________________________
void TUUID::Print() const
{
   // Print UUID.

   printf("%s\n", AsString());
}

//______________________________________________________________________________
const char *TUUID::AsString() const
{
   // Return UUID as string. Copy string immediately since it will be reused.

   static char uuid[40];

   snprintf(uuid,40, "%08x-%04x-%04x-%02x%02x-%02x%02x%02x%02x%02x%02x",
           fTimeLow, fTimeMid, fTimeHiAndVersion, fClockSeqHiAndReserved,
           fClockSeqLow, fNode[0], fNode[1], fNode[2], fNode[3], fNode[4],
           fNode[5]);

   return uuid;
}

//______________________________________________________________________________
UShort_t TUUID::Hash() const
{
   // Compute 16-bit hash value of the UUID.

   Short_t  c0 = 0, c1 = 0, x, y;
   char    *c = (char *) &fTimeLow;

   // For speed lets unroll the following loop:
   //   for (i = 0; i < 16; i++) {
   //      c0 += *c++;
   //      c1 += c0;
   //   }

   c0 += *c++; c1 += c0;
   c0 += *c++; c1 += c0;
   c0 += *c++; c1 += c0;
   c0 += *c++; c1 += c0;

   c0 += *c++; c1 += c0;
   c0 += *c++; c1 += c0;
   c0 += *c++; c1 += c0;
   c0 += *c++; c1 += c0;

   c0 += *c++; c1 += c0;
   c0 += *c++; c1 += c0;
   c0 += *c++; c1 += c0;
   c0 += *c++; c1 += c0;

   c0 += *c++; c1 += c0;
   c0 += *c++; c1 += c0;
   c0 += *c++; c1 += c0;
   c0 += *c++; c1 += c0;

   //  Calculate the value for "First octet" of the hash
   x = -c1 % 255;
   if (x < 0)
      x += 255;

   // Calculate the value for "second octet" of the hash
   y = (c1 - c0) % 255;
   if (y < 0)
      y += 255;

   return UShort_t((y << 8) + x);
}

//______________________________________________________________________________
Int_t TUUID::Compare(const TUUID &u) const
{
   // Compare two UUIDs "lexically" and return
   //    -1   this is lexically before u
   //     0   this is equal to u
   //     1   this is lexically after u

#define CHECK(f1, f2) if (f1 != f2) return f1 < f2 ? -1 : 1;
   CHECK(fTimeLow, u.fTimeLow)
   CHECK(fTimeMid, u.fTimeMid)
   CHECK(fTimeHiAndVersion, u.fTimeHiAndVersion)
   CHECK(fClockSeqHiAndReserved, u.fClockSeqHiAndReserved)
   CHECK(fClockSeqLow, u.fClockSeqLow)
   for (int i = 0; i < 6; i++) {
      if (fNode[i] < u.fNode[i])
         return -1;
      if (fNode[i] > u.fNode[i])
         return 1;
   }
   return 0;
}

//______________________________________________________________________________
TInetAddress TUUID::GetHostAddress() const
{
   // Get address of host encoded in UUID. If host id is not an ethernet
   // address, but random info, then the returned TInetAddress is not valid.

   if ((fTimeHiAndVersion >> 12) == 1) {
      UInt_t addr;
      memcpy(&addr, fNode, 4);
      return TInetAddress("????", addr, 0);
   }
   return TInetAddress();
}

//______________________________________________________________________________
TDatime TUUID::GetTime() const
{
   // Get time from UUID.

   TDatime     dt;
   uuid_time_t ts;

   ts.low   = fTimeLow;
   ts.high  = (UInt_t)fTimeMid;
   ts.high |= (UInt_t)((fTimeHiAndVersion & 0x0FFF) << 16);

   // Offset between UUID formatted times and Unix formatted times.
   // UUID UTC base time is October 15, 1582.
   // Unix base time is January 1, 1970.
   ULong64_t high = ts.high;
   ULong64_t uuid_time = (high << 32) + ts.low;
   uuid_time -= 0x01B21DD213814000LL;
   uuid_time /= 10000000LL;
   UInt_t tt = (UInt_t) uuid_time;
   dt.Set(tt);

   return dt;
}

//______________________________________________________________________________
void TUUID::GetUUID(UChar_t uuid[16]) const
{
   // Return uuid in specified buffer (16 byte = 128 bits).

   memcpy(uuid, &fTimeLow, 16);
}

//______________________________________________________________________________
void TUUID::SetUUID(const char *uuid)
{
   // Set this UUID to the value specified in uuid ((which must be in
   // TUUID::AsString() format).

   if (!uuid || !*uuid)
      Error("SetUUID", "null string not allowed");
   else
      SetFromString(uuid);
}

//______________________________________________________________________________
TBuffer &operator<<(TBuffer &buf, const TUUID &uuid)
{
   // Input operator.  Delegate to Streamer.

   R__ASSERT( buf.IsWriting() );

   const_cast<TUUID&>(uuid).Streamer(buf);
   return buf;
}