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