dlls/ntdll/rtl.c

   1 /*
   2  * NT basis DLL
   3  *
   4  * This file contains the Rtl* API functions. These should be implementable.
   5  *
   6  * Copyright 1996-1998 Marcus Meissner
   7  * Copyright 1999      Alex Korobka
   8  * Copyright 2003      Thomas Mertes
   9  * Crc32 code Copyright 1986 Gary S. Brown (Public domain)
  10  *
  11  * This library is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU Lesser General Public
  13  * License as published by the Free Software Foundation; either
  14  * version 2.1 of the License, or (at your option) any later version.
  15  *
  16  * This library is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19  * Lesser General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU Lesser General Public
  22  * License along with this library; if not, write to the Free Software
  23  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  24  */
  25
  26 #include "config.h"
  27 #include "wine/port.h"
  28
  29 #include <stdlib.h>
  30 #include <stdarg.h>
  31 #include <stdio.h>
  32 #include <string.h>
  33 #ifdef HAVE_NETINET_IN_H
  34 #include <netinet/in.h>
  35 #endif
  36 #include "ntstatus.h"
  37 #define NONAMELESSUNION
  38 #define NONAMELESSSTRUCT
  39 #define WIN32_NO_STATUS
  40 #define USE_WS_PREFIX
  41 #include "windef.h"
  42 #include "winternl.h"
  43 #include "wine/debug.h"
  44 #include "wine/exception.h"
  45 #include "wine/unicode.h"
  46 #include "ntdll_misc.h"
  47 #include "inaddr.h"
  48 #include "ddk/ntddk.h"
  49
  50 WINE_DEFAULT_DEBUG_CHANNEL(ntdll);
  51
  52 #ifdef __i386__
  53 #define DEFINE_FASTCALL4_ENTRYPOINT( name ) \
  54     __ASM_STDCALL_FUNC( name, 16, \
  55                        "popl %eax\n\t" \
  56                        "pushl %edx\n\t" \
  57                        "pushl %ecx\n\t" \
  58                        "pushl %eax\n\t" \
  59                        "jmp " __ASM_NAME("__regs_") #name __ASM_STDCALL(16))
  60 #endif
  61
  62 /* CRC polynomial 0xedb88320 */
  63 static const DWORD CRC_table[256] =
  64 {
  65     0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
  66     0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
  67     0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
  68     0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
  69     0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
  70     0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
  71     0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
  72     0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
  73     0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
  74     0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
  75     0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
  76     0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
  77     0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
  78     0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
  79     0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
  80     0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
  81     0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
  82     0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
  83     0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
  84     0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
  85     0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
  86     0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
  87     0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
  88     0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
  89     0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
  90     0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
  91     0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
  92     0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
  93     0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
  94     0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
  95     0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
  96     0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
  97     0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
  98     0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
  99     0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
 100     0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
 101     0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
 102     0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
 103     0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
 104     0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 105     0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
 106     0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 107     0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 108 };
 109
 110 /*
 111  *      resource functions
 112  */
 113
 114 /***********************************************************************
 115  *           RtlInitializeResource      (NTDLL.@)
 116  *
 117  * xxxResource() functions implement multiple-reader-single-writer lock.
 118  * The code is based on information published in WDJ January 1999 issue.
 119  */
 120 void WINAPI RtlInitializeResource(LPRTL_RWLOCK rwl)
 121 {
 122     if( rwl )
 123     {
 124         rwl->iNumberActive = 0;
 125         rwl->uExclusiveWaiters = 0;
 126         rwl->uSharedWaiters = 0;
 127         rwl->hOwningThreadId = 0;
 128         rwl->dwTimeoutBoost = 0; /* no info on this one, default value is 0 */
 129         RtlInitializeCriticalSection( &rwl->rtlCS );
 130         rwl->rtlCS.DebugInfo->Spare[0] = (DWORD_PTR)(__FILE__ ": RTL_RWLOCK.rtlCS");
 131         NtCreateSemaphore( &rwl->hExclusiveReleaseSemaphore, SEMAPHORE_ALL_ACCESS, NULL, 0, 65535 );
 132         NtCreateSemaphore( &rwl->hSharedReleaseSemaphore, SEMAPHORE_ALL_ACCESS, NULL, 0, 65535 );
 133     }
 134 }
 135
 136
 137 /***********************************************************************
 138  *           RtlDeleteResource          (NTDLL.@)
 139  */
 140 void WINAPI RtlDeleteResource(LPRTL_RWLOCK rwl)
 141 {
 142     if( rwl )
 143     {
 144         RtlEnterCriticalSection( &rwl->rtlCS );
 145         if( rwl->iNumberActive || rwl->uExclusiveWaiters || rwl->uSharedWaiters )
 146             ERR("Deleting active MRSW lock (%p), expect failure\n", rwl );
 147         rwl->hOwningThreadId = 0;
 148         rwl->uExclusiveWaiters = rwl->uSharedWaiters = 0;
 149         rwl->iNumberActive = 0;
 150         NtClose( rwl->hExclusiveReleaseSemaphore );
 151         NtClose( rwl->hSharedReleaseSemaphore );
 152         RtlLeaveCriticalSection( &rwl->rtlCS );
 153         rwl->rtlCS.DebugInfo->Spare[0] = 0;
 154         RtlDeleteCriticalSection( &rwl->rtlCS );
 155     }
 156 }
 157
 158
 159 /***********************************************************************
 160  *          RtlAcquireResourceExclusive (NTDLL.@)
 161  */
 162 BYTE WINAPI RtlAcquireResourceExclusive(LPRTL_RWLOCK rwl, BYTE fWait)
 163 {
 164     BYTE retVal = 0;
 165     if( !rwl ) return 0;
 166
 167 start:
 168     RtlEnterCriticalSection( &rwl->rtlCS );
 169     if( rwl->iNumberActive == 0 ) /* lock is free */
 170     {
 171         rwl->iNumberActive = -1;
 172         retVal = 1;
 173     }
 174     else if( rwl->iNumberActive < 0 ) /* exclusive lock in progress */
 175     {
 176          if( rwl->hOwningThreadId == ULongToHandle(GetCurrentThreadId()) )
 177          {
 178              retVal = 1;
 179              rwl->iNumberActive--;
 180              goto done;
 181          }
 182 wait:
 183          if( fWait )
 184          {
 185              NTSTATUS status;
 186
 187              rwl->uExclusiveWaiters++;
 188
 189              RtlLeaveCriticalSection( &rwl->rtlCS );
 190              status = NtWaitForSingleObject( rwl->hExclusiveReleaseSemaphore, FALSE, NULL );
 191              if( HIWORD(status) )
 192                  goto done;
 193              goto start; /* restart the acquisition to avoid deadlocks */
 194          }
 195     }
 196     else  /* one or more shared locks are in progress */
 197          if( fWait )
 198              goto wait;
 199
 200     if( retVal == 1 )
 201         rwl->hOwningThreadId = ULongToHandle(GetCurrentThreadId());
 202 done:
 203     RtlLeaveCriticalSection( &rwl->rtlCS );
 204     return retVal;
 205 }
 206
 207 /***********************************************************************
 208  *          RtlAcquireResourceShared    (NTDLL.@)
 209  */
 210 BYTE WINAPI RtlAcquireResourceShared(LPRTL_RWLOCK rwl, BYTE fWait)
 211 {
 212     NTSTATUS status = STATUS_UNSUCCESSFUL;
 213     BYTE retVal = 0;
 214     if( !rwl ) return 0;
 215
 216 start:
 217     RtlEnterCriticalSection( &rwl->rtlCS );
 218     if( rwl->iNumberActive < 0 )
 219     {
 220         if( rwl->hOwningThreadId == ULongToHandle(GetCurrentThreadId()) )
 221         {
 222             rwl->iNumberActive--;
 223             retVal = 1;
 224             goto done;
 225         }
 226
 227         if( fWait )
 228         {
 229             rwl->uSharedWaiters++;
 230             RtlLeaveCriticalSection( &rwl->rtlCS );
 231             status = NtWaitForSingleObject( rwl->hSharedReleaseSemaphore, FALSE, NULL );
 232             if( HIWORD(status) )
 233                 goto done;
 234             goto start;
 235         }
 236     }
 237     else
 238     {
 239         if( status != STATUS_WAIT_0 ) /* otherwise RtlReleaseResource() has already done it */
 240             rwl->iNumberActive++;
 241         retVal = 1;
 242     }
 243 done:
 244     RtlLeaveCriticalSection( &rwl->rtlCS );
 245     return retVal;
 246 }
 247
 248
 249 /***********************************************************************
 250  *           RtlReleaseResource         (NTDLL.@)
 251  */
 252 void WINAPI RtlReleaseResource(LPRTL_RWLOCK rwl)
 253 {
 254     RtlEnterCriticalSection( &rwl->rtlCS );
 255
 256     if( rwl->iNumberActive > 0 ) /* have one or more readers */
 257     {
 258         if( --rwl->iNumberActive == 0 )
 259         {
 260             if( rwl->uExclusiveWaiters )
 261             {
 262 wake_exclusive:
 263                 rwl->uExclusiveWaiters--;
 264                 NtReleaseSemaphore( rwl->hExclusiveReleaseSemaphore, 1, NULL );
 265             }
 266         }
 267     }
 268     else
 269     if( rwl->iNumberActive < 0 ) /* have a writer, possibly recursive */
 270     {
 271         if( ++rwl->iNumberActive == 0 )
 272         {
 273             rwl->hOwningThreadId = 0;
 274             if( rwl->uExclusiveWaiters )
 275                 goto wake_exclusive;
 276             else
 277                 if( rwl->uSharedWaiters )
 278                 {
 279                     UINT n = rwl->uSharedWaiters;
 280                     rwl->iNumberActive = rwl->uSharedWaiters; /* prevent new writers from joining until
 281                                                                * all queued readers have done their thing */
 282                     rwl->uSharedWaiters = 0;
 283                     NtReleaseSemaphore( rwl->hSharedReleaseSemaphore, n, NULL );
 284                 }
 285         }
 286     }
 287     RtlLeaveCriticalSection( &rwl->rtlCS );
 288 }
 289
 290
 291 /***********************************************************************
 292  *           RtlDumpResource            (NTDLL.@)
 293  */
 294 void WINAPI RtlDumpResource(LPRTL_RWLOCK rwl)
 295 {
 296     if( rwl )
 297     {
 298         MESSAGE("RtlDumpResource(%p):\n\tactive count = %i\n\twaiting readers = %i\n\twaiting writers = %i\n",
 299                 rwl, rwl->iNumberActive, rwl->uSharedWaiters, rwl->uExclusiveWaiters );
 300         if( rwl->iNumberActive )
 301             MESSAGE("\towner thread = %p\n", rwl->hOwningThreadId );
 302     }
 303 }
 304
 305 /*
 306  *      misc functions
 307  */
 308
 309 /******************************************************************************
 310  *      DbgPrint        [NTDLL.@]
 311  */
 312 NTSTATUS WINAPIV DbgPrint(LPCSTR fmt, ...)
 313 {
 314   char buf[512];
 315   __ms_va_list args;
 316
 317   __ms_va_start(args, fmt);
 318   NTDLL__vsnprintf(buf, sizeof(buf), fmt, args);
 319   __ms_va_end(args);
 320
 321   MESSAGE("DbgPrint says: %s",buf);
 322   /* hmm, raise exception? */
 323   return STATUS_SUCCESS;
 324 }
 325
 326
 327 /******************************************************************************
 328  *      DbgPrintEx      [NTDLL.@]
 329  */
 330 NTSTATUS WINAPIV DbgPrintEx(ULONG iComponentId, ULONG Level, LPCSTR fmt, ...)
 331 {
 332     NTSTATUS ret;
 333     __ms_va_list args;
 334
 335     __ms_va_start(args, fmt);
 336     ret = vDbgPrintEx(iComponentId, Level, fmt, args);
 337     __ms_va_end(args);
 338     return ret;
 339 }
 340
 341 /******************************************************************************
 342  *      vDbgPrintEx     [NTDLL.@]
 343  */
 344 NTSTATUS WINAPI vDbgPrintEx( ULONG id, ULONG level, LPCSTR fmt, __ms_va_list args )
 345 {
 346     return vDbgPrintExWithPrefix( "", id, level, fmt, args );
 347 }
 348
 349 /******************************************************************************
 350  *      vDbgPrintExWithPrefix  [NTDLL.@]
 351  */
 352 NTSTATUS WINAPI vDbgPrintExWithPrefix( LPCSTR prefix, ULONG id, ULONG level, LPCSTR fmt, __ms_va_list args )
 353 {
 354     char buf[1024];
 355
 356     NTDLL__vsnprintf(buf, sizeof(buf), fmt, args);
 357
 358     switch (level & DPFLTR_MASK)
 359     {
 360     case DPFLTR_ERROR_LEVEL:   ERR("%s%x: %s", prefix, id, buf); break;
 361     case DPFLTR_WARNING_LEVEL: WARN("%s%x: %s", prefix, id, buf); break;
 362     case DPFLTR_TRACE_LEVEL:
 363     case DPFLTR_INFO_LEVEL:
 364     default:                   TRACE("%s%x: %s", prefix, id, buf); break;
 365     }
 366     return STATUS_SUCCESS;
 367 }
 368
 369 /******************************************************************************
 370  *  RtlAcquirePebLock           [NTDLL.@]
 371  */
 372 VOID WINAPI RtlAcquirePebLock(void)
 373 {
 374     RtlEnterCriticalSection( NtCurrentTeb()->Peb->FastPebLock );
 375 }
 376
 377 /******************************************************************************
 378  *  RtlReleasePebLock           [NTDLL.@]
 379  */
 380 VOID WINAPI RtlReleasePebLock(void)
 381 {
 382     RtlLeaveCriticalSection( NtCurrentTeb()->Peb->FastPebLock );
 383 }
 384
 385 /******************************************************************************
 386  *  RtlNewSecurityObject                [NTDLL.@]
 387  */
 388 NTSTATUS WINAPI
 389 RtlNewSecurityObject( PSECURITY_DESCRIPTOR ParentDescriptor,
 390                       PSECURITY_DESCRIPTOR CreatorDescriptor,
 391                       PSECURITY_DESCRIPTOR *NewDescriptor,
 392                       BOOLEAN IsDirectoryObject,
 393                       HANDLE Token,
 394                       PGENERIC_MAPPING GenericMapping )
 395 {
 396     FIXME("(%p %p %p %d %p %p) stub!\n", ParentDescriptor, CreatorDescriptor,
 397           NewDescriptor, IsDirectoryObject, Token, GenericMapping);
 398     return STATUS_NOT_IMPLEMENTED;
 399 }
 400
 401 /******************************************************************************
 402  *  RtlDeleteSecurityObject             [NTDLL.@]
 403  */
 404 NTSTATUS WINAPI
 405 RtlDeleteSecurityObject( PSECURITY_DESCRIPTOR *ObjectDescriptor )
 406 {
 407     FIXME("(%p) stub!\n", ObjectDescriptor);
 408     return STATUS_NOT_IMPLEMENTED;
 409 }
 410
 411 /******************************************************************************
 412  *  RtlInitializeGenericTable           [NTDLL.@]
 413  */
 414 PVOID WINAPI RtlInitializeGenericTable(PVOID pTable, PVOID arg2, PVOID arg3, PVOID arg4, PVOID arg5)
 415 {
 416   FIXME("(%p,%p,%p,%p,%p) stub!\n", pTable, arg2, arg3, arg4, arg5);
 417   return NULL;
 418 }
 419
 420 /******************************************************************************
 421  *  RtlEnumerateGenericTableWithoutSplaying           [NTDLL.@]
 422  */
 423 PVOID RtlEnumerateGenericTableWithoutSplaying(PVOID pTable, PVOID *RestartKey)
 424 {
 425     static int warn_once;
 426
 427     if (!warn_once++)
 428         FIXME("(%p,%p) stub!\n", pTable, RestartKey);
 429     return NULL;
 430 }
 431
 432 /******************************************************************************
 433  *  RtlNumberGenericTableElements           [NTDLL.@]
 434  */
 435 ULONG RtlNumberGenericTableElements(PVOID pTable)
 436 {
 437     FIXME("(%p) stub!\n", pTable);
 438     return 0;
 439 }
 440
 441 /******************************************************************************
 442  *  RtlMoveMemory   [NTDLL.@]
 443  *
 444  * Move a block of memory that may overlap.
 445  *
 446  * PARAMS
 447  *  Destination [O] End destination for block
 448  *  Source      [O] Where to start copying from
 449  *  Length      [I] Number of bytes to copy
 450  *
 451  * RETURNS
 452  *  Nothing.
 453  */
 454 #undef RtlMoveMemory
 455 VOID WINAPI RtlMoveMemory( void *Destination, const void *Source, SIZE_T Length )
 456 {
 457     memmove(Destination, Source, Length);
 458 }
 459
 460 /******************************************************************************
 461  *  RtlFillMemory   [NTDLL.@]
 462  *
 463  * Set a block of memory with a value.
 464  *
 465  * PARAMS
 466  *  Destination [O] Block to fill
 467  *  Length      [I] Number of bytes to fill
 468  *  Fill        [I] Value to set
 469  *
 470  * RETURNS
 471  *  Nothing.
 472  */
 473 #undef RtlFillMemory
 474 VOID WINAPI RtlFillMemory( VOID *Destination, SIZE_T Length, BYTE Fill )
 475 {
 476     memset(Destination, Fill, Length);
 477 }
 478
 479 /******************************************************************************
 480  *  RtlZeroMemory   [NTDLL.@]
 481  *
 482  * Set a block of memory with 0's.
 483  *
 484  * PARAMS
 485  *  Destination [O] Block to fill
 486  *  Length      [I] Number of bytes to fill
 487  *
 488  * RETURNS
 489  *  Nothing.
 490  */
 491 #undef RtlZeroMemory
 492 VOID WINAPI RtlZeroMemory( VOID *Destination, SIZE_T Length )
 493 {
 494     memset(Destination, 0, Length);
 495 }
 496
 497 /******************************************************************************
 498  *  RtlCompareMemory   [NTDLL.@]
 499  *
 500  * Compare one block of memory with another
 501  *
 502  * PARAMS
 503  *  Source1 [I] Source block
 504  *  Source2 [I] Block to compare to Source1
 505  *  Length  [I] Number of bytes to compare
 506  *
 507  * RETURNS
 508  *  The length of the first byte at which Source1 and Source2 differ, or Length
 509  *  if they are the same.
 510  */
 511 SIZE_T WINAPI RtlCompareMemory( const VOID *Source1, const VOID *Source2, SIZE_T Length)
 512 {
 513     SIZE_T i;
 514     for(i=0; (i<Length) && (((const BYTE*)Source1)[i]==((const BYTE*)Source2)[i]); i++);
 515     return i;
 516 }
 517
 518 /******************************************************************************
 519  *  RtlCompareMemoryUlong   [NTDLL.@]
 520  *
 521  * Compare a block of memory with a value, a ULONG at a time
 522  *
 523  * PARAMS
 524  *  Source1 [I] Source block. This must be ULONG aligned
 525  *  Length  [I] Number of bytes to compare. This should be a multiple of 4
 526  *  dwVal   [I] Value to compare to
 527  *
 528  * RETURNS
 529  *  The byte position of the first byte at which Source1 is not dwVal.
 530  */
 531 SIZE_T WINAPI RtlCompareMemoryUlong(const ULONG *Source1, SIZE_T Length, ULONG dwVal)
 532 {
 533     SIZE_T i;
 534     for(i = 0; i < Length/sizeof(ULONG) && Source1[i] == dwVal; i++);
 535     return i * sizeof(ULONG);
 536 }
 537
 538 /******************************************************************************
 539  *  RtlCopyMemory   [NTDLL.@]
 540  */
 541 #undef RtlCopyMemory
 542 void WINAPI RtlCopyMemory(void *dest, const void *src, SIZE_T len)
 543 {
 544     memcpy(dest, src, len);
 545 }
 546
 547 /******************************************************************************
 548  *  RtlAssert                           [NTDLL.@]
 549  *
 550  * Fail a debug assertion.
 551  *
 552  * RETURNS
 553  *  Nothing. This call does not return control to its caller.
 554  *
 555  * NOTES
 556  * Not implemented in non-debug versions.
 557  */
 558 void WINAPI RtlAssert(void *assertion, void *filename, ULONG linenumber, char *message)
 559 {
 560     FIXME("(%s, %s, %u, %s): stub\n", debugstr_a((char*)assertion), debugstr_a((char*)filename),
 561         linenumber, debugstr_a(message));
 562 }
 563
 564 /*************************************************************************
 565  * RtlFillMemoryUlong   [NTDLL.@]
 566  *
 567  * Fill memory with a 32 bit (dword) value.
 568  *
 569  * PARAMS
 570  *  lpDest  [I] Bitmap pointer
 571  *  ulCount [I] Number of dwords to write
 572  *  ulValue [I] Value to fill with
 573  *
 574  * RETURNS
 575  *  Nothing.
 576  */
 577 VOID WINAPI RtlFillMemoryUlong(ULONG* lpDest, ULONG ulCount, ULONG ulValue)
 578 {
 579   TRACE("(%p,%d,%d)\n", lpDest, ulCount, ulValue);
 580
 581   ulCount /= sizeof(ULONG);
 582   while(ulCount--)
 583     *lpDest++ = ulValue;
 584 }
 585
 586 /*********************************************************************
 587  *                  RtlComputeCrc32   [NTDLL.@]
 588  *
 589  * Calculate the CRC32 checksum of a block of bytes
 590  *
 591  * PARAMS
 592  *  dwInitial [I] Initial CRC value
 593  *  pData     [I] Data block
 594  *  iLen      [I] Length of the byte block
 595  *
 596  * RETURNS
 597  *  The cumulative CRC32 of dwInitial and iLen bytes of the pData block.
 598  */
 599 DWORD WINAPI RtlComputeCrc32(DWORD dwInitial, const BYTE *pData, INT iLen)
 600 {
 601   DWORD crc = ~dwInitial;
 602
 603   TRACE("(%d,%p,%d)\n", dwInitial, pData, iLen);
 604
 605   while (iLen > 0)
 606   {
 607     crc = CRC_table[(crc ^ *pData) & 0xff] ^ (crc >> 8);
 608     pData++;
 609     iLen--;
 610   }
 611   return ~crc;
 612 }
 613
 614
 615 /*************************************************************************
 616  * RtlUlonglongByteSwap    [NTDLL.@]
 617  *
 618  * Swap the bytes of an unsigned long long value.
 619  *
 620  * PARAMS
 621  *  i [I] Value to swap bytes of
 622  *
 623  * RETURNS
 624  *  The value with its bytes swapped.
 625  */
 626 ULONGLONG __cdecl RtlUlonglongByteSwap(ULONGLONG i)
 627 {
 628   return ((ULONGLONG)RtlUlongByteSwap(i) << 32) | RtlUlongByteSwap(i>>32);
 629 }
 630
 631 /*************************************************************************
 632  * RtlUlongByteSwap    [NTDLL.@]
 633  *
 634  * Swap the bytes of an unsigned int value.
 635  *
 636  * NOTES
 637  *  ix86 version takes argument in %ecx. Other systems use the inline version.
 638  */
 639 #ifdef __i386__
 640 __ASM_GLOBAL_FUNC(NTDLL_RtlUlongByteSwap,
 641                   "movl %ecx,%eax\n\t"
 642                   "bswap %eax\n\t"
 643                   "ret")
 644 #endif
 645
 646 /*************************************************************************
 647  * RtlUshortByteSwap    [NTDLL.@]
 648  *
 649  * Swap the bytes of an unsigned short value.
 650  *
 651  * NOTES
 652  *  i386 version takes argument in %cx. Other systems use the inline version.
 653  */
 654 #ifdef __i386__
 655 __ASM_GLOBAL_FUNC(NTDLL_RtlUshortByteSwap,
 656                   "movb %ch,%al\n\t"
 657                   "movb %cl,%ah\n\t"
 658                   "ret")
 659 #endif
 660
 661
 662 /*************************************************************************
 663  * RtlUniform   [NTDLL.@]
 664  *
 665  * Generates an uniform random number
 666  *
 667  * PARAMS
 668  *  seed [O] The seed of the Random function
 669  *
 670  * RETURNS
 671  *  It returns a random number uniformly distributed over [0..MAXLONG-1].
 672  *
 673  * NOTES
 674  *  Generates an uniform random number using D.H. Lehmer's 1948 algorithm.
 675  *  In our case the algorithm is:
 676  *
 677  *|  result = (*seed * 0x7fffffed + 0x7fffffc3) % MAXLONG;
 678  *|
 679  *|  *seed = result;
 680  *
 681  * DIFFERENCES
 682  *  The native documentation states that the random number is
 683  *  uniformly distributed over [0..MAXLONG]. In reality the native
 684  *  function and our function return a random number uniformly
 685  *  distributed over [0..MAXLONG-1].
 686  */
 687 ULONG WINAPI RtlUniform (PULONG seed)
 688 {
 689     ULONG result;
 690
 691    /*
 692     * Instead of the algorithm stated above, we use the algorithm
 693     * below, which is totally equivalent (see the tests), but does
 694     * not use a division and therefore is faster.
 695     */
 696     result = *seed * 0xffffffed + 0x7fffffc3;
 697     if (result == 0xffffffff || result == 0x7ffffffe) {
 698         result = (result + 2) & MAXLONG;
 699     } else if (result == 0x7fffffff) {
 700         result = 0;
 701     } else if ((result & 0x80000000) == 0) {
 702         result = result + (~result & 1);
 703     } else {
 704         result = (result + (result & 1)) & MAXLONG;
 705     } /* if */
 706     *seed = result;
 707     return result;
 708 }
 709
 710
 711 /*************************************************************************
 712  * RtlRandom   [NTDLL.@]
 713  *
 714  * Generates a random number
 715  *
 716  * PARAMS
 717  *  seed [O] The seed of the Random function
 718  *
 719  * RETURNS
 720  *  It returns a random number distributed over [0..MAXLONG-1].
 721  */
 722 ULONG WINAPI RtlRandom (PULONG seed)
 723 {
 724     static ULONG saved_value[128] =
 725     { /*   0 */ 0x4c8bc0aa, 0x4c022957, 0x2232827a, 0x2f1e7626, 0x7f8bdafb, 0x5c37d02a, 0x0ab48f72, 0x2f0c4ffa,
 726       /*   8 */ 0x290e1954, 0x6b635f23, 0x5d3885c0, 0x74b49ff8, 0x5155fa54, 0x6214ad3f, 0x111e9c29, 0x242a3a09,
 727       /*  16 */ 0x75932ae1, 0x40ac432e, 0x54f7ba7a, 0x585ccbd5, 0x6df5c727, 0x0374dad1, 0x7112b3f1, 0x735fc311,
 728       /*  24 */ 0x404331a9, 0x74d97781, 0x64495118, 0x323e04be, 0x5974b425, 0x4862e393, 0x62389c1d, 0x28a68b82,
 729       /*  32 */ 0x0f95da37, 0x7a50bbc6, 0x09b0091c, 0x22cdb7b4, 0x4faaed26, 0x66417ccd, 0x189e4bfa, 0x1ce4e8dd,
 730       /*  40 */ 0x5274c742, 0x3bdcf4dc, 0x2d94e907, 0x32eac016, 0x26d33ca3, 0x60415a8a, 0x31f57880, 0x68c8aa52,
 731       /*  48 */ 0x23eb16da, 0x6204f4a1, 0x373927c1, 0x0d24eb7c, 0x06dd7379, 0x2b3be507, 0x0f9c55b1, 0x2c7925eb,
 732       /*  56 */ 0x36d67c9a, 0x42f831d9, 0x5e3961cb, 0x65d637a8, 0x24bb3820, 0x4d08e33d, 0x2188754f, 0x147e409e,
 733       /*  64 */ 0x6a9620a0, 0x62e26657, 0x7bd8ce81, 0x11da0abb, 0x5f9e7b50, 0x23e444b6, 0x25920c78, 0x5fc894f0,
 734       /*  72 */ 0x5e338cbb, 0x404237fd, 0x1d60f80f, 0x320a1743, 0x76013d2b, 0x070294ee, 0x695e243b, 0x56b177fd,
 735       /*  80 */ 0x752492e1, 0x6decd52f, 0x125f5219, 0x139d2e78, 0x1898d11e, 0x2f7ee785, 0x4db405d8, 0x1a028a35,
 736       /*  88 */ 0x63f6f323, 0x1f6d0078, 0x307cfd67, 0x3f32a78a, 0x6980796c, 0x462b3d83, 0x34b639f2, 0x53fce379,
 737       /*  96 */ 0x74ba50f4, 0x1abc2c4b, 0x5eeaeb8d, 0x335a7a0d, 0x3973dd20, 0x0462d66b, 0x159813ff, 0x1e4643fd,
 738       /* 104 */ 0x06bc5c62, 0x3115e3fc, 0x09101613, 0x47af2515, 0x4f11ec54, 0x78b99911, 0x3db8dd44, 0x1ec10b9b,
 739       /* 112 */ 0x5b5506ca, 0x773ce092, 0x567be81a, 0x5475b975, 0x7a2cde1a, 0x494536f5, 0x34737bb4, 0x76d9750b,
 740       /* 120 */ 0x2a1f6232, 0x2e49644d, 0x7dddcbe7, 0x500cebdb, 0x619dab9e, 0x48c626fe, 0x1cda3193, 0x52dabe9d };
 741     ULONG rand;
 742     int pos;
 743     ULONG result;
 744
 745     rand = (*seed * 0x7fffffed + 0x7fffffc3) % 0x7fffffff;
 746     *seed = (rand * 0x7fffffed + 0x7fffffc3) % 0x7fffffff;
 747     pos = *seed & 0x7f;
 748     result = saved_value[pos];
 749     saved_value[pos] = rand;
 750     return(result);
 751 }
 752
 753
 754 /*************************************************************************
 755  * RtlAreAllAccessesGranted   [NTDLL.@]
 756  *
 757  * Check if all desired accesses are granted
 758  *
 759  * RETURNS
 760  *  TRUE: All desired accesses are granted
 761  *  FALSE: Otherwise
 762  */
 763 BOOLEAN WINAPI RtlAreAllAccessesGranted(
 764     ACCESS_MASK GrantedAccess,
 765     ACCESS_MASK DesiredAccess)
 766 {
 767     return (GrantedAccess & DesiredAccess) == DesiredAccess;
 768 }
 769
 770
 771 /*************************************************************************
 772  * RtlAreAnyAccessesGranted   [NTDLL.@]
 773  *
 774  * Check if at least one of the desired accesses is granted
 775  *
 776  * PARAMS
 777  *  GrantedAccess [I] Access mask of granted accesses
 778  *  DesiredAccess [I] Access mask of desired accesses
 779  *
 780  * RETURNS
 781  *  TRUE: At least one of the desired accesses is granted
 782  *  FALSE: Otherwise
 783  */
 784 BOOLEAN WINAPI RtlAreAnyAccessesGranted(
 785     ACCESS_MASK GrantedAccess,
 786     ACCESS_MASK DesiredAccess)
 787 {
 788     return (GrantedAccess & DesiredAccess) != 0;
 789 }
 790
 791
 792 /*************************************************************************
 793  * RtlMapGenericMask   [NTDLL.@]
 794  *
 795  * Determine the nongeneric access rights specified by an access mask
 796  *
 797  * RETURNS
 798  *  Nothing.
 799  */
 800 void WINAPI RtlMapGenericMask(
 801     PACCESS_MASK AccessMask,
 802     const GENERIC_MAPPING *GenericMapping)
 803 {
 804     if (*AccessMask & GENERIC_READ) {
 805         *AccessMask |= GenericMapping->GenericRead;
 806     } /* if */
 807
 808     if (*AccessMask & GENERIC_WRITE) {
 809         *AccessMask |= GenericMapping->GenericWrite;
 810     } /* if */
 811
 812     if (*AccessMask & GENERIC_EXECUTE) {
 813         *AccessMask |= GenericMapping->GenericExecute;
 814     } /* if */
 815
 816     if (*AccessMask & GENERIC_ALL) {
 817         *AccessMask |= GenericMapping->GenericAll;
 818     } /* if */
 819
 820     *AccessMask &= 0x0FFFFFFF;
 821 }
 822
 823
 824 /*************************************************************************
 825  * RtlCopyLuid   [NTDLL.@]
 826  *
 827  * Copy a local unique ID.
 828  *
 829  * PARAMS
 830  *  LuidDest [O] Destination for the copied Luid
 831  *  LuidSrc  [I] Source Luid to copy to LuidDest
 832  *
 833  * RETURNS
 834  *  Nothing.
 835  */
 836 void WINAPI RtlCopyLuid (PLUID LuidDest, const LUID *LuidSrc)
 837 {
 838     *LuidDest = *LuidSrc;
 839 }
 840
 841
 842 /*************************************************************************
 843  * RtlEqualLuid   [NTDLL.@]
 844  *
 845  * Compare two local unique IDs.
 846  *
 847  * PARAMS
 848  *  Luid1 [I] First Luid to compare to Luid2
 849  *  Luid2 [I] Second Luid to compare to Luid1
 850  *
 851  * RETURNS
 852  *  TRUE: The two LUIDs are equal.
 853  *  FALSE: Otherwise
 854  */
 855 BOOLEAN WINAPI RtlEqualLuid (const LUID *Luid1, const LUID *Luid2)
 856 {
 857   return (Luid1->LowPart ==  Luid2->LowPart && Luid1->HighPart == Luid2->HighPart);
 858 }
 859
 860
 861 /*************************************************************************
 862  * RtlCopyLuidAndAttributesArray   [NTDLL.@]
 863  *
 864  * Copy an array of local unique IDs and attributes.
 865  *
 866  * PARAMS
 867  *  Count [I] Number of Luid/attributes in Src
 868  *  Src   [I] Source Luid/attributes to copy
 869  *  Dest  [O] Destination for copied Luid/attributes
 870  *
 871  * RETURNS
 872  *  Nothing.
 873  *
 874  * NOTES
 875  *  Dest must be large enough to hold Src.
 876  */
 877 void WINAPI RtlCopyLuidAndAttributesArray(
 878     ULONG Count,
 879     const LUID_AND_ATTRIBUTES *Src,
 880     PLUID_AND_ATTRIBUTES Dest)
 881 {
 882     ULONG i;
 883
 884     for (i = 0; i < Count; i++) Dest[i] = Src[i];
 885 }
 886
 887 /***********************************************************************
 888  * RtlIpv4StringToAddressExW [NTDLL.@]
 889  */
 890 NTSTATUS WINAPI RtlIpv4StringToAddressExW(const WCHAR *str, BOOLEAN strict, IN_ADDR *address, USHORT *port)
 891 {
 892     FIXME("(%s, %u, %p, %p): stub\n", debugstr_w(str), strict, address, port);
 893     return STATUS_NOT_IMPLEMENTED;
 894 }
 895
 896 /***********************************************************************
 897  * RtlIpv4StringToAddressW [NTDLL.@]
 898  */
 899 NTSTATUS WINAPI RtlIpv4StringToAddressW(const WCHAR *str, BOOLEAN strict, const WCHAR **terminator, IN_ADDR *address)
 900 {
 901     FIXME("(%s, %u, %p, %p): stub\n", debugstr_w(str), strict, terminator, address);
 902     return STATUS_NOT_IMPLEMENTED;
 903 }
 904
 905 /***********************************************************************
 906  * RtlIpv4AddressToStringExW [NTDLL.@]
 907  *
 908  * Convert the given ipv4 address and optional the port to a string
 909  *
 910  * PARAMS
 911  *  pin     [I]  PTR to the ip address to convert (network byte order)
 912  *  port    [I]  optional port to convert (network byte order)
 913  *  buffer  [O]  destination buffer for the result
 914  *  psize   [IO] PTR to available/used size of the destination buffer
 915  *
 916  * RETURNS
 917  *  Success: STATUS_SUCCESS
 918  *  Failure: STATUS_INVALID_PARAMETER
 919  *
 920  */
 921 NTSTATUS WINAPI RtlIpv4AddressToStringExW(const IN_ADDR *pin, USHORT port, LPWSTR buffer, PULONG psize)
 922 {
 923     WCHAR tmp_ip[32];
 924     static const WCHAR fmt_ip[] = {'%','u','.','%','u','.','%','u','.','%','u',0};
 925     static const WCHAR fmt_port[] = {':','%','u',0};
 926     ULONG needed;
 927
 928     if (!pin || !buffer || !psize)
 929         return STATUS_INVALID_PARAMETER;
 930
 931     TRACE("(%p:0x%x, %d, %p, %p:%d)\n", pin, pin->S_un.S_addr, port, buffer, psize, *psize);
 932
 933     needed = sprintfW(tmp_ip, fmt_ip,
 934                       pin->S_un.S_un_b.s_b1, pin->S_un.S_un_b.s_b2,
 935                       pin->S_un.S_un_b.s_b3, pin->S_un.S_un_b.s_b4);
 936
 937     if (port) needed += sprintfW(tmp_ip + needed, fmt_port, ntohs(port));
 938
 939     if (*psize > needed) {
 940         *psize = needed + 1;
 941         strcpyW(buffer, tmp_ip);
 942         return STATUS_SUCCESS;
 943     }
 944
 945     *psize = needed + 1;
 946     return STATUS_INVALID_PARAMETER;
 947 }
 948
 949 /***********************************************************************
 950  * RtlIpv4AddressToStringExA [NTDLL.@]
 951  *
 952  * Convert the given ipv4 address and optional the port to a string
 953  *
 954  * See RtlIpv4AddressToStringExW
 955  */
 956 NTSTATUS WINAPI RtlIpv4AddressToStringExA(const IN_ADDR *pin, USHORT port, LPSTR buffer, PULONG psize)
 957 {
 958     CHAR tmp_ip[32];
 959     ULONG needed;
 960
 961     if (!pin || !buffer || !psize)
 962         return STATUS_INVALID_PARAMETER;
 963
 964     TRACE("(%p:0x%x, %d, %p, %p:%d)\n", pin, pin->S_un.S_addr, port, buffer, psize, *psize);
 965
 966     needed = sprintf(tmp_ip, "%u.%u.%u.%u",
 967                      pin->S_un.S_un_b.s_b1, pin->S_un.S_un_b.s_b2,
 968                      pin->S_un.S_un_b.s_b3, pin->S_un.S_un_b.s_b4);
 969
 970     if (port) needed += sprintf(tmp_ip + needed, ":%u", ntohs(port));
 971
 972     if (*psize > needed) {
 973         *psize = needed + 1;
 974         strcpy(buffer, tmp_ip);
 975         return STATUS_SUCCESS;
 976     }
 977
 978     *psize = needed + 1;
 979     return STATUS_INVALID_PARAMETER;
 980 }
 981
 982 /***********************************************************************
 983  * RtlIpv4AddressToStringW [NTDLL.@]
 984  *
 985  * Convert the given ipv4 address to a string
 986  *
 987  * PARAMS
 988  *  pin     [I]  PTR to the ip address to convert (network byte order)
 989  *  buffer  [O]  destination buffer for the result (at least 16 character)
 990  *
 991  * RETURNS
 992  *  PTR to the 0 character at the end of the converted string
 993  *
 994  */
 995 WCHAR * WINAPI RtlIpv4AddressToStringW(const IN_ADDR *pin, LPWSTR buffer)
 996 {
 997     ULONG size = 16;
 998
 999     if (RtlIpv4AddressToStringExW(pin, 0, buffer, &size)) size = 0;
1000     return buffer + size - 1;
1001 }
1002
1003 /***********************************************************************
1004  * RtlIpv4AddressToStringA [NTDLL.@]
1005  *
1006  * Convert the given ipv4 address to a string
1007  *
1008  * See RtlIpv4AddressToStringW
1009  */
1010 CHAR * WINAPI RtlIpv4AddressToStringA(const IN_ADDR *pin, LPSTR buffer)
1011 {
1012     ULONG size = 16;
1013
1014     if (RtlIpv4AddressToStringExA(pin, 0, buffer, &size)) size = 0;
1015     return buffer + size - 1;
1016 }
1017
1018 /***********************************************************************
1019  * get_pointer_obfuscator (internal)
1020  */
1021 static DWORD_PTR get_pointer_obfuscator( void )
1022 {
1023     static DWORD_PTR pointer_obfuscator;
1024
1025     if (!pointer_obfuscator)
1026     {
1027         ULONG seed = NtGetTickCount();
1028         ULONG_PTR rand;
1029
1030         /* generate a random value for the obfuscator */
1031         rand = RtlUniform( &seed );
1032
1033         /* handle 64bit pointers */
1034         rand ^= (ULONG_PTR)RtlUniform( &seed ) << ((sizeof (DWORD_PTR) - sizeof (ULONG))*8);
1035
1036         /* set the high bits so dereferencing obfuscated pointers will (usually) crash */
1037         rand |= (ULONG_PTR)0xc0000000 << ((sizeof (DWORD_PTR) - sizeof (ULONG))*8);
1038
1039         interlocked_cmpxchg_ptr( (void**) &pointer_obfuscator, (void*) rand, NULL );
1040     }
1041
1042     return pointer_obfuscator;
1043 }
1044
1045 /*************************************************************************
1046  * RtlEncodePointer   [NTDLL.@]
1047  */
1048 PVOID WINAPI RtlEncodePointer( PVOID ptr )
1049 {
1050     DWORD_PTR ptrval = (DWORD_PTR) ptr;
1051     return (PVOID)(ptrval ^ get_pointer_obfuscator());
1052 }
1053
1054 PVOID WINAPI RtlDecodePointer( PVOID ptr )
1055 {
1056     DWORD_PTR ptrval = (DWORD_PTR) ptr;
1057     return (PVOID)(ptrval ^ get_pointer_obfuscator());
1058 }
1059
1060 /*************************************************************************
1061  * RtlInitializeSListHead   [NTDLL.@]
1062  */
1063 VOID WINAPI RtlInitializeSListHead(PSLIST_HEADER list)
1064 {
1065 #ifdef _WIN64
1066     list->s.Alignment = list->s.Region = 0;
1067     list->Header16.HeaderType = 1;  /* we use the 16-byte header */
1068 #else
1069     list->Alignment = 0;
1070 #endif
1071 }
1072
1073 /*************************************************************************
1074  * RtlQueryDepthSList   [NTDLL.@]
1075  */
1076 WORD WINAPI RtlQueryDepthSList(PSLIST_HEADER list)
1077 {
1078 #ifdef _WIN64
1079     return list->Header16.Depth;
1080 #else
1081     return list->s.Depth;
1082 #endif
1083 }
1084
1085 /*************************************************************************
1086  * RtlFirstEntrySList   [NTDLL.@]
1087  */
1088 PSLIST_ENTRY WINAPI RtlFirstEntrySList(const SLIST_HEADER* list)
1089 {
1090 #ifdef _WIN64
1091     return (SLIST_ENTRY *)((ULONG_PTR)list->Header16.NextEntry << 4);
1092 #else
1093     return list->s.Next.Next;
1094 #endif
1095 }
1096
1097 /*************************************************************************
1098  * RtlInterlockedFlushSList   [NTDLL.@]
1099  */
1100 PSLIST_ENTRY WINAPI RtlInterlockedFlushSList(PSLIST_HEADER list)
1101 {
1102     SLIST_HEADER old, new;
1103
1104 #ifdef _WIN64
1105     if (!list->Header16.NextEntry) return NULL;
1106     new.s.Alignment = new.s.Region = 0;
1107     new.Header16.HeaderType = 1;  /* we use the 16-byte header */
1108     do
1109     {
1110         old = *list;
1111         new.Header16.Sequence = old.Header16.Sequence + 1;
1112     } while (!interlocked_cmpxchg128((__int64 *)list, new.s.Region, new.s.Alignment, (__int64 *)&old));
1113     return (SLIST_ENTRY *)((ULONG_PTR)old.Header16.NextEntry << 4);
1114 #else
1115     if (!list->s.Next.Next) return NULL;
1116     new.Alignment = 0;
1117     do
1118     {
1119         old = *list;
1120         new.s.Sequence = old.s.Sequence + 1;
1121     } while (interlocked_cmpxchg64((__int64 *)&list->Alignment, new.Alignment,
1122                                    old.Alignment) != old.Alignment);
1123     return old.s.Next.Next;
1124 #endif
1125 }
1126
1127 /*************************************************************************
1128  * RtlInterlockedPushEntrySList   [NTDLL.@]
1129  */
1130 PSLIST_ENTRY WINAPI RtlInterlockedPushEntrySList(PSLIST_HEADER list, PSLIST_ENTRY entry)
1131 {
1132     SLIST_HEADER old, new;
1133
1134 #ifdef _WIN64
1135     new.Header16.NextEntry = (ULONG_PTR)entry >> 4;
1136     do
1137     {
1138         old = *list;
1139         entry->Next = (SLIST_ENTRY *)((ULONG_PTR)old.Header16.NextEntry << 4);
1140         new.Header16.Depth = old.Header16.Depth + 1;
1141         new.Header16.Sequence = old.Header16.Sequence + 1;
1142     } while (!interlocked_cmpxchg128((__int64 *)list, new.s.Region, new.s.Alignment, (__int64 *)&old));
1143     return (SLIST_ENTRY *)((ULONG_PTR)old.Header16.NextEntry << 4);
1144 #else
1145     new.s.Next.Next = entry;
1146     do
1147     {
1148         old = *list;
1149         entry->Next = old.s.Next.Next;
1150         new.s.Depth = old.s.Depth + 1;
1151         new.s.Sequence = old.s.Sequence + 1;
1152     } while (interlocked_cmpxchg64((__int64 *)&list->Alignment, new.Alignment,
1153                                    old.Alignment) != old.Alignment);
1154     return old.s.Next.Next;
1155 #endif
1156 }
1157
1158 /*************************************************************************
1159  * RtlInterlockedPopEntrySList   [NTDLL.@]
1160  */
1161 PSLIST_ENTRY WINAPI RtlInterlockedPopEntrySList(PSLIST_HEADER list)
1162 {
1163     SLIST_HEADER old, new;
1164     PSLIST_ENTRY entry;
1165
1166 #ifdef _WIN64
1167     do
1168     {
1169         old = *list;
1170         if (!(entry = (SLIST_ENTRY *)((ULONG_PTR)old.Header16.NextEntry << 4))) return NULL;
1171         /* entry could be deleted by another thread */
1172         __TRY
1173         {
1174             new.Header16.NextEntry = (ULONG_PTR)entry->Next >> 4;
1175             new.Header16.Depth = old.Header16.Depth - 1;
1176             new.Header16.Sequence = old.Header16.Sequence + 1;
1177         }
1178         __EXCEPT_PAGE_FAULT
1179         {
1180         }
1181         __ENDTRY
1182     } while (!interlocked_cmpxchg128((__int64 *)list, new.s.Region, new.s.Alignment, (__int64 *)&old));
1183 #else
1184     do
1185     {
1186         old = *list;
1187         if (!(entry = old.s.Next.Next)) return NULL;
1188         /* entry could be deleted by another thread */
1189         __TRY
1190         {
1191             new.s.Next.Next = entry->Next;
1192             new.s.Depth = old.s.Depth - 1;
1193             new.s.Sequence = old.s.Sequence + 1;
1194         }
1195         __EXCEPT_PAGE_FAULT
1196         {
1197         }
1198         __ENDTRY
1199     } while (interlocked_cmpxchg64((__int64 *)&list->Alignment, new.Alignment,
1200                                    old.Alignment) != old.Alignment);
1201 #endif
1202     return entry;
1203 }
1204
1205 /*************************************************************************
1206  * RtlInterlockedPushListSListEx   [NTDLL.@]
1207  */
1208 PSLIST_ENTRY WINAPI RtlInterlockedPushListSListEx(PSLIST_HEADER list, PSLIST_ENTRY first,
1209                                                   PSLIST_ENTRY last, ULONG count)
1210 {
1211     SLIST_HEADER old, new;
1212
1213 #ifdef _WIN64
1214     new.Header16.NextEntry = (ULONG_PTR)first >> 4;
1215     do
1216     {
1217         old = *list;
1218         new.Header16.Depth = old.Header16.Depth + count;
1219         new.Header16.Sequence = old.Header16.Sequence + 1;
1220         last->Next = (SLIST_ENTRY *)((ULONG_PTR)old.Header16.NextEntry << 4);
1221     } while (!interlocked_cmpxchg128((__int64 *)list, new.s.Region, new.s.Alignment, (__int64 *)&old));
1222     return (SLIST_ENTRY *)((ULONG_PTR)old.Header16.NextEntry << 4);
1223 #else
1224     new.s.Next.Next = first;
1225     do
1226     {
1227         old = *list;
1228         new.s.Depth = old.s.Depth + count;
1229         new.s.Sequence = old.s.Sequence + 1;
1230         last->Next = old.s.Next.Next;
1231     } while (interlocked_cmpxchg64((__int64 *)&list->Alignment, new.Alignment,
1232                                    old.Alignment) != old.Alignment);
1233     return old.s.Next.Next;
1234 #endif
1235 }
1236
1237 /*************************************************************************
1238  * RtlInterlockedPushListSList   [NTDLL.@]
1239  */
1240 #ifdef DEFINE_FASTCALL4_ENTRYPOINT
1241 DEFINE_FASTCALL4_ENTRYPOINT(RtlInterlockedPushListSList)
1242 PSLIST_ENTRY WINAPI DECLSPEC_HIDDEN __regs_RtlInterlockedPushListSList(PSLIST_HEADER list, PSLIST_ENTRY first,
1243                                                                        PSLIST_ENTRY last, ULONG count)
1244 #else
1245 PSLIST_ENTRY WINAPI RtlInterlockedPushListSList(PSLIST_HEADER list, PSLIST_ENTRY first,
1246                                                 PSLIST_ENTRY last, ULONG count)
1247 #endif
1248 {
1249     return RtlInterlockedPushListSListEx(list, first, last, count);
1250 }
1251
1252 /******************************************************************************
1253  *  RtlGetCompressionWorkSpaceSize              [NTDLL.@]
1254  */
1255 NTSTATUS WINAPI RtlGetCompressionWorkSpaceSize(USHORT format, PULONG compress_workspace,
1256                                                PULONG decompress_workspace)
1257 {
1258     FIXME("0x%04x, %p, %p: semi-stub\n", format, compress_workspace, decompress_workspace);
1259
1260     switch (format & ~COMPRESSION_ENGINE_MAXIMUM)
1261     {
1262         case COMPRESSION_FORMAT_LZNT1:
1263             if (compress_workspace)
1264             {
1265                 /* FIXME: The current implementation of RtlCompressBuffer does not use a
1266                  * workspace buffer, but Windows applications might expect a nonzero value. */
1267                 *compress_workspace = 16;
1268             }
1269             if (decompress_workspace)
1270                 *decompress_workspace = 0x1000;
1271             return STATUS_SUCCESS;
1272
1273         case COMPRESSION_FORMAT_NONE:
1274         case COMPRESSION_FORMAT_DEFAULT:
1275             return STATUS_INVALID_PARAMETER;
1276
1277         default:
1278             FIXME("format %u not implemented\n", format);
1279             return STATUS_UNSUPPORTED_COMPRESSION;
1280     }
1281 }
1282
1283 /* compress data using LZNT1, currently only a stub */
1284 static NTSTATUS lznt1_compress(UCHAR *src, ULONG src_size, UCHAR *dst, ULONG dst_size,
1285                                ULONG chunk_size, ULONG *final_size, UCHAR *workspace)
1286 {
1287     UCHAR *src_cur = src, *src_end = src + src_size;
1288     UCHAR *dst_cur = dst, *dst_end = dst + dst_size;
1289     ULONG block_size;
1290
1291     while (src_cur < src_end)
1292     {
1293         /* determine size of current chunk */
1294         block_size = min(0x1000, src_end - src_cur);
1295         if (dst_cur + sizeof(WORD) + block_size > dst_end)
1296             return STATUS_BUFFER_TOO_SMALL;
1297
1298         /* write (uncompressed) chunk header */
1299         *(WORD *)dst_cur = 0x3000 | (block_size - 1);
1300         dst_cur += sizeof(WORD);
1301
1302         /* write chunk content */
1303         memcpy(dst_cur, src_cur, block_size);
1304         dst_cur += block_size;
1305         src_cur += block_size;
1306     }
1307
1308     if (final_size)
1309         *final_size = dst_cur - dst;
1310
1311     return STATUS_SUCCESS;
1312 }
1313
1314 /******************************************************************************
1315  *  RtlCompressBuffer           [NTDLL.@]
1316  */
1317 NTSTATUS WINAPI RtlCompressBuffer(USHORT format, PUCHAR uncompressed, ULONG uncompressed_size,
1318                                   PUCHAR compressed, ULONG compressed_size, ULONG chunk_size,
1319                                   PULONG final_size, PVOID workspace)
1320 {
1321     FIXME("0x%04x, %p, %u, %p, %u, %u, %p, %p: semi-stub\n", format, uncompressed,
1322           uncompressed_size, compressed, compressed_size, chunk_size, final_size, workspace);
1323
1324     switch (format & ~COMPRESSION_ENGINE_MAXIMUM)
1325     {
1326         case COMPRESSION_FORMAT_LZNT1:
1327             return lznt1_compress(uncompressed, uncompressed_size, compressed,
1328                                   compressed_size, chunk_size, final_size, workspace);
1329
1330         case COMPRESSION_FORMAT_NONE:
1331         case COMPRESSION_FORMAT_DEFAULT:
1332             return STATUS_INVALID_PARAMETER;
1333
1334         default:
1335             FIXME("format %u not implemented\n", format);
1336             return STATUS_UNSUPPORTED_COMPRESSION;
1337     }
1338 }
1339
1340 /* decompress a single LZNT1 chunk */
1341 static UCHAR *lznt1_decompress_chunk(UCHAR *dst, ULONG dst_size, UCHAR *src, ULONG src_size)
1342 {
1343     UCHAR *src_cur = src, *src_end = src + src_size;
1344     UCHAR *dst_cur = dst, *dst_end = dst + dst_size;
1345     ULONG displacement_bits, length_bits;
1346     ULONG code_displacement, code_length;
1347     WORD flags, code;
1348
1349     while (src_cur < src_end && dst_cur < dst_end)
1350     {
1351         flags = 0x8000 | *src_cur++;
1352         while ((flags & 0xff00) && src_cur < src_end)
1353         {
1354             if (flags & 1)
1355             {
1356                 /* backwards reference */
1357                 if (src_cur + sizeof(WORD) > src_end)
1358                     return NULL;
1359
1360                 code = *(WORD *)src_cur;
1361                 src_cur += sizeof(WORD);
1362
1363                 /* find length / displacement bits */
1364                 for (displacement_bits = 12; displacement_bits > 4; displacement_bits--)
1365                     if ((1 << (displacement_bits - 1)) < dst_cur - dst) break;
1366
1367                 length_bits       = 16 - displacement_bits;
1368                 code_length       = (code & ((1 << length_bits) - 1)) + 3;
1369                 code_displacement = (code >> length_bits) + 1;
1370
1371                 if (dst_cur < dst + code_displacement)
1372                     return NULL;
1373
1374                 /* copy bytes of chunk - we can't use memcpy() since source and dest can
1375                  * be overlapping, and the same bytes can be repeated over and over again */
1376                 while (code_length--)
1377                 {
1378                     if (dst_cur >= dst_end) return dst_cur;
1379                     *dst_cur = *(dst_cur - code_displacement);
1380                     dst_cur++;
1381                 }
1382             }
1383             else
1384             {
1385                 /* uncompressed data */
1386                 if (dst_cur >= dst_end) return dst_cur;
1387                 *dst_cur++ = *src_cur++;
1388             }
1389             flags >>= 1;
1390         }
1391     }
1392
1393     return dst_cur;
1394 }
1395
1396 /* decompress data encoded with LZNT1 */
1397 static NTSTATUS lznt1_decompress(UCHAR *dst, ULONG dst_size, UCHAR *src, ULONG src_size,
1398                                  ULONG offset, ULONG *final_size, UCHAR *workspace)
1399 {
1400     UCHAR *src_cur = src, *src_end = src + src_size;
1401     UCHAR *dst_cur = dst, *dst_end = dst + dst_size;
1402     ULONG chunk_size, block_size;
1403     WORD chunk_header;
1404     UCHAR *ptr;
1405
1406     if (src_cur + sizeof(WORD) > src_end)
1407         return STATUS_BAD_COMPRESSION_BUFFER;
1408
1409     /* skip over chunks with a distance >= 0x1000 to the destination offset */
1410     while (offset >= 0x1000 && src_cur + sizeof(WORD) <= src_end)
1411     {
1412         chunk_header = *(WORD *)src_cur;
1413         src_cur += sizeof(WORD);
1414         if (!chunk_header) goto out;
1415         chunk_size = (chunk_header & 0xfff) + 1;
1416
1417         if (src_cur + chunk_size > src_end)
1418             return STATUS_BAD_COMPRESSION_BUFFER;
1419
1420         src_cur += chunk_size;
1421         offset  -= 0x1000;
1422     }
1423
1424     /* handle partially included chunk */
1425     if (offset && src_cur + sizeof(WORD) <= src_end)
1426     {
1427         chunk_header = *(WORD *)src_cur;
1428         src_cur += sizeof(WORD);
1429         if (!chunk_header) goto out;
1430         chunk_size = (chunk_header & 0xfff) + 1;
1431
1432         if (src_cur + chunk_size > src_end)
1433             return STATUS_BAD_COMPRESSION_BUFFER;
1434
1435         if (dst_cur >= dst_end)
1436             goto out;
1437
1438         if (chunk_header & 0x8000)
1439         {
1440             /* compressed chunk */
1441             if (!workspace) return STATUS_ACCESS_VIOLATION;
1442             ptr = lznt1_decompress_chunk(workspace, 0x1000, src_cur, chunk_size);
1443             if (!ptr) return STATUS_BAD_COMPRESSION_BUFFER;
1444             if (ptr - workspace > offset)
1445             {
1446                 block_size = min((ptr - workspace) - offset, dst_end - dst_cur);
1447                 memcpy(dst_cur, workspace + offset, block_size);
1448                 dst_cur += block_size;
1449             }
1450         }
1451         else
1452         {
1453             /* uncompressed chunk */
1454             if (chunk_size > offset)
1455             {
1456                 block_size = min(chunk_size - offset, dst_end - dst_cur);
1457                 memcpy(dst_cur, src_cur + offset, block_size);
1458                 dst_cur += block_size;
1459             }
1460         }
1461
1462         src_cur += chunk_size;
1463     }
1464
1465     /* handle remaining chunks */
1466     while (src_cur + sizeof(WORD) <= src_end)
1467     {
1468         chunk_header = *(WORD *)src_cur;
1469         src_cur += sizeof(WORD);
1470         if (!chunk_header) goto out;
1471         chunk_size = (chunk_header & 0xfff) + 1;
1472
1473         if (src_cur + chunk_size > src_end)
1474             return STATUS_BAD_COMPRESSION_BUFFER;
1475
1476         /* fill space with padding when the previous chunk was decompressed
1477          * to less than 4096 bytes. no padding is needed for the last chunk
1478          * or when the next chunk is truncated */
1479         block_size = ((dst_cur - dst) + offset) & 0xfff;
1480         if (block_size)
1481         {
1482             block_size = 0x1000 - block_size;
1483             if (dst_cur + block_size >= dst_end)
1484                 goto out;
1485             memset(dst_cur, 0, block_size);
1486             dst_cur += block_size;
1487         }
1488
1489         if (dst_cur >= dst_end)
1490             goto out;
1491
1492         if (chunk_header & 0x8000)
1493         {
1494             /* compressed chunk */
1495             dst_cur = lznt1_decompress_chunk(dst_cur, dst_end - dst_cur, src_cur, chunk_size);
1496             if (!dst_cur) return STATUS_BAD_COMPRESSION_BUFFER;
1497         }
1498         else
1499         {
1500             /* uncompressed chunk */
1501             block_size = min(chunk_size, dst_end - dst_cur);
1502             memcpy(dst_cur, src_cur, block_size);
1503             dst_cur += block_size;
1504         }
1505
1506         src_cur += chunk_size;
1507     }
1508
1509 out:
1510     if (final_size)
1511         *final_size = dst_cur - dst;
1512
1513     return STATUS_SUCCESS;
1514
1515 }
1516
1517 /******************************************************************************
1518  *  RtlDecompressFragment       [NTDLL.@]
1519  */
1520 NTSTATUS WINAPI RtlDecompressFragment(USHORT format, PUCHAR uncompressed, ULONG uncompressed_size,
1521                                PUCHAR compressed, ULONG compressed_size, ULONG offset,
1522                                PULONG final_size, PVOID workspace)
1523 {
1524     TRACE("0x%04x, %p, %u, %p, %u, %u, %p, %p\n", format, uncompressed,
1525           uncompressed_size, compressed, compressed_size, offset, final_size, workspace);
1526
1527     switch (format & ~COMPRESSION_ENGINE_MAXIMUM)
1528     {
1529         case COMPRESSION_FORMAT_LZNT1:
1530             return lznt1_decompress(uncompressed, uncompressed_size, compressed,
1531                                     compressed_size, offset, final_size, workspace);
1532
1533         case COMPRESSION_FORMAT_NONE:
1534         case COMPRESSION_FORMAT_DEFAULT:
1535             return STATUS_INVALID_PARAMETER;
1536
1537         default:
1538             FIXME("format %u not implemented\n", format);
1539             return STATUS_UNSUPPORTED_COMPRESSION;
1540     }
1541 }
1542
1543
1544 /******************************************************************************
1545  *  RtlDecompressBuffer         [NTDLL.@]
1546  */
1547 NTSTATUS WINAPI RtlDecompressBuffer(USHORT format, PUCHAR uncompressed, ULONG uncompressed_size,
1548                                     PUCHAR compressed, ULONG compressed_size, PULONG final_size)
1549 {
1550     TRACE("0x%04x, %p, %u, %p, %u, %p\n", format, uncompressed,
1551         uncompressed_size, compressed, compressed_size, final_size);
1552
1553     return RtlDecompressFragment(format, uncompressed, uncompressed_size,
1554                                  compressed, compressed_size, 0, final_size, NULL);
1555 }
1556
1557 /***********************************************************************
1558  *  RtlSetThreadErrorMode       [NTDLL.@]
1559  *
1560  * Set the thread local error mode.
1561  *
1562  * PARAMS
1563  *  mode    [I] The new error mode
1564  *  oldmode [O] Destination of the old error mode (may be NULL)
1565  *
1566  * RETURNS
1567  *  Success: STATUS_SUCCESS
1568  *  Failure: STATUS_INVALID_PARAMETER_1
1569  */
1570 NTSTATUS WINAPI RtlSetThreadErrorMode( DWORD mode, LPDWORD oldmode )
1571 {
1572     if (mode & ~0x70)
1573         return STATUS_INVALID_PARAMETER_1;
1574
1575     if (oldmode)
1576         *oldmode = NtCurrentTeb()->HardErrorDisabled;
1577
1578     NtCurrentTeb()->HardErrorDisabled = mode;
1579     return STATUS_SUCCESS;
1580 }
1581
1582 /***********************************************************************
1583  *  RtlGetThreadErrorMode       [NTDLL.@]
1584  *
1585  * Get the thread local error mode.
1586  *
1587  * PARAMS
1588  *  None.
1589  *
1590  * RETURNS
1591  *  The current thread local error mode.
1592  */
1593 DWORD WINAPI RtlGetThreadErrorMode( void )
1594 {
1595     return NtCurrentTeb()->HardErrorDisabled;
1596 }
1597
1598 /******************************************************************************
1599  * RtlGetCurrentTransaction [NTDLL.@]
1600  */
1601 HANDLE WINAPI RtlGetCurrentTransaction(void)
1602 {
1603     FIXME("() :stub\n");
1604     return NULL;
1605 }
1606
1607 /******************************************************************************
1608  * RtlSetCurrentTransaction [NTDLL.@]
1609  */
1610 BOOL WINAPI RtlSetCurrentTransaction(HANDLE new_transaction)
1611 {
1612     FIXME("(%p) :stub\n", new_transaction);
1613     return FALSE;
1614 }
1615
1616 /**********************************************************************
1617  *           RtlGetCurrentProcessorNumberEx [NTDLL.@]
1618  */
1619 void WINAPI RtlGetCurrentProcessorNumberEx(PROCESSOR_NUMBER *processor)
1620 {
1621     FIXME("(%p) :semi-stub\n", processor);
1622     processor->Group = 0;
1623     processor->Number = NtGetCurrentProcessorNumber();
1624     processor->Reserved = 0;
1625 }
1626
1627 /***********************************************************************
1628  *           RtlInitializeGenericTableAvl  (NTDLL.@)
1629  */
1630 void WINAPI RtlInitializeGenericTableAvl(PRTL_AVL_TABLE table, PRTL_AVL_COMPARE_ROUTINE compare,
1631                                          PRTL_AVL_ALLOCATE_ROUTINE allocate, PRTL_AVL_FREE_ROUTINE free, void *context)
1632 {
1633     FIXME("%p %p %p %p %p: stub\n", table, compare, allocate, free, context);
1634 }
1635
1636 /***********************************************************************
1637  *           RtlInsertElementGenericTableAvl  (NTDLL.@)
1638  */
1639 void WINAPI RtlInsertElementGenericTableAvl(PRTL_AVL_TABLE table, void *buffer, ULONG size, BOOL *element)
1640 {
1641     FIXME("%p %p %u %p: stub\n", table, buffer, size, element);
1642 }
1643
1644 /**********************************************************************
1645  *           RtlCreateUserProcess [NTDLL.@]
1646  */
1647 NTSTATUS WINAPI RtlCreateUserProcess(UNICODE_STRING *path, ULONG attributes, RTL_USER_PROCESS_PARAMETERS *parameters,
1648                                      SECURITY_DESCRIPTOR *process_descriptor, SECURITY_DESCRIPTOR *thread_descriptor,
1649                                      HANDLE parent, BOOLEAN inherit, HANDLE debug, HANDLE exception,
1650                                      RTL_USER_PROCESS_INFORMATION *info)
1651 {
1652     FIXME("(%p %u %p %p %p %p %d %p %p %p): stub\n", path, attributes, parameters, process_descriptor, thread_descriptor,
1653                                      parent, inherit, debug, exception, info);
1654     return STATUS_NOT_IMPLEMENTED;
1655 }
1656
1657 typedef struct _RTL_UNLOAD_EVENT_TRACE
1658 {
1659     PVOID BaseAddress;
1660     SIZE_T SizeOfImage;
1661     ULONG Sequence;
1662     ULONG TimeDateStamp;
1663     ULONG CheckSum;
1664     WCHAR ImageName[32];
1665 } RTL_UNLOAD_EVENT_TRACE, *PRTL_UNLOAD_EVENT_TRACE;
1666
1667 /*********************************************************************
1668  *           RtlGetUnloadEventTrace [NTDLL.@]
1669  */
1670 RTL_UNLOAD_EVENT_TRACE * WINAPI RtlGetUnloadEventTrace(void)
1671 {
1672     FIXME("stub!\n");
1673     return NULL;
1674 }
1675
1676 /*********************************************************************
1677  *           RtlQueryPackageIdentity [NTDLL.@]
1678  */
1679 NTSTATUS WINAPI RtlQueryPackageIdentity(HANDLE token, WCHAR *fullname, SIZE_T *fullname_size,
1680                                         WCHAR *appid, SIZE_T *appid_size, BOOLEAN *packaged)
1681 {
1682     FIXME("(%p, %p, %p, %p, %p, %p): stub\n", token, fullname, fullname_size, appid, appid_size, packaged);
1683     return STATUS_NOT_FOUND;
1684 }