dlls/ntdll/large_int.c

   1 /*
   2  * Large integer functions
   3  *
   4  * Copyright 2000 Alexandre Julliard
   5  * Copyright 2003 Thomas Mertes
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  20  */
  21
  22 #include <stdarg.h>
  23
  24 #include "ntstatus.h"
  25 #define WIN32_NO_STATUS
  26 #include "windef.h"
  27 #include "winternl.h"
  28 #include "wine/asm.h"
  29
  30 #ifndef _WIN64
  31
  32 /*
  33  * Note: we use LONGLONG instead of LARGE_INTEGER, because
  34  * the latter is a structure and the calling convention for
  35  * returning a structure would not be binary-compatible.
  36  *
  37  * FIXME: for platforms that don't have a native LONGLONG type,
  38  * we should define LONGLONG as a structure similar to LARGE_INTEGER
  39  * and do everything by hand. You are welcome to do it...
  40  */
  41
  42 /******************************************************************************
  43  *        RtlLargeIntegerAdd   (NTDLL.@)
  44  *
  45  * Add two 64 bit integers.
  46  *
  47  * PARAMS
  48  *  a [I] Initial number.
  49  *  b [I] Number to add to a.
  50  *
  51  * RETURNS
  52  *  The sum of a and b.
  53  */
  54 LONGLONG WINAPI RtlLargeIntegerAdd( LONGLONG a, LONGLONG b )
  55 {
  56     return a + b;
  57 }
  58
  59
  60 /******************************************************************************
  61  *        RtlLargeIntegerSubtract   (NTDLL.@)
  62  *
  63  * Subtract two 64 bit integers.
  64  *
  65  * PARAMS
  66  *  a [I] Initial number.
  67  *  b [I] Number to subtract from a.
  68  *
  69  * RETURNS
  70  *  The difference of a and b.
  71  */
  72 LONGLONG WINAPI RtlLargeIntegerSubtract( LONGLONG a, LONGLONG b )
  73 {
  74     return a - b;
  75 }
  76
  77
  78 /******************************************************************************
  79  *        RtlLargeIntegerNegate   (NTDLL.@)
  80  *
  81  * Negate a 64 bit integer.
  82  *
  83  * PARAMS
  84  *  a     [I] Initial number.
  85  *
  86  * RETURNS
  87  *  The value of a negated.
  88  */
  89 LONGLONG WINAPI RtlLargeIntegerNegate( LONGLONG a )
  90 {
  91     return -a;
  92 }
  93
  94
  95 /******************************************************************************
  96  *        RtlLargeIntegerShiftLeft   (NTDLL.@)
  97  *
  98  * Perform a shift left on a 64 bit integer.
  99  *
 100  * PARAMS
 101  *  a     [I] Initial number.
 102  *  count [I] Number of bits to shift by
 103  *
 104  * RETURNS
 105  *  The value of a following the shift.
 106  */
 107 LONGLONG WINAPI RtlLargeIntegerShiftLeft( LONGLONG a, INT count )
 108 {
 109     return a << count;
 110 }
 111
 112
 113 /******************************************************************************
 114  *        RtlLargeIntegerShiftRight   (NTDLL.@)
 115  *
 116  * Perform a shift right on a 64 bit integer.
 117  *
 118  * PARAMS
 119  *  a     [I] Initial number.
 120  *  count [I] Number of bits to shift by
 121  *
 122  * RETURNS
 123  *  The value of a following the shift.
 124  */
 125 LONGLONG WINAPI RtlLargeIntegerShiftRight( LONGLONG a, INT count )
 126 {
 127     return (ULONGLONG)a >> count;
 128 }
 129
 130
 131 /******************************************************************************
 132  *        RtlLargeIntegerArithmeticShift   (NTDLL.@)
 133  *
 134  * Perform an arithmetic shift right on a 64 bit integer.
 135  *
 136  * PARAMS
 137  *  a     [I] Initial number.
 138  *  count [I] Number of bits to shift by
 139  *
 140  * RETURNS
 141  *  The value of a following the shift.
 142  */
 143 LONGLONG WINAPI RtlLargeIntegerArithmeticShift( LONGLONG a, INT count )
 144 {
 145     /* FIXME: gcc does arithmetic shift here, but it may not be true on all platforms */
 146     return a >> count;
 147 }
 148
 149
 150 /******************************************************************************
 151  *        RtlLargeIntegerDivide   (NTDLL.@)
 152  *
 153  * Divide one 64 bit unsigned integer by another, with remainder.
 154  *
 155  * PARAMS
 156  *  a   [I] Initial number.
 157  *  b   [I] Number to divide a by
 158  *  rem [O] Destination for remainder
 159  *
 160  * RETURNS
 161  *  The dividend of a and b. If rem is non-NULL it is set to the remainder.
 162  *
 163  * FIXME
 164  *  Should it be signed division instead?
 165  */
 166 ULONGLONG WINAPI RtlLargeIntegerDivide( ULONGLONG a, ULONGLONG b, ULONGLONG *rem )
 167 {
 168     ULONGLONG ret = a / b;
 169     if (rem) *rem = a - ret * b;
 170     return ret;
 171 }
 172
 173
 174 /******************************************************************************
 175  *        RtlConvertLongToLargeInteger   (NTDLL.@)
 176  *
 177  * Convert a 32 bit integer into 64 bits.
 178  *
 179  * PARAMS
 180  *  a [I] Number to convert
 181  *
 182  * RETURNS
 183  *  a.
 184  */
 185 LONGLONG WINAPI RtlConvertLongToLargeInteger( LONG a )
 186 {
 187     return a;
 188 }
 189
 190
 191 /******************************************************************************
 192  *        RtlConvertUlongToLargeInteger   (NTDLL.@)
 193  *
 194  * Convert a 32 bit unsigned integer into 64 bits.
 195  *
 196  * PARAMS
 197  *  a [I] Number to convert
 198  *
 199  * RETURNS
 200  *  a.
 201  */
 202 ULONGLONG WINAPI RtlConvertUlongToLargeInteger( ULONG a )
 203 {
 204     return a;
 205 }
 206
 207
 208 /******************************************************************************
 209  *        RtlEnlargedIntegerMultiply   (NTDLL.@)
 210  *
 211  * Multiply two integers giving a 64 bit integer result.
 212  *
 213  * PARAMS
 214  *  a [I] Initial number.
 215  *  b [I] Number to multiply a by.
 216  *
 217  * RETURNS
 218  *  The product of a and b.
 219  */
 220 LONGLONG WINAPI RtlEnlargedIntegerMultiply( INT a, INT b )
 221 {
 222     return (LONGLONG)a * b;
 223 }
 224
 225
 226 /******************************************************************************
 227  *        RtlEnlargedUnsignedMultiply   (NTDLL.@)
 228  *
 229  * Multiply two unsigned integers giving a 64 bit unsigned integer result.
 230  *
 231  * PARAMS
 232  *  a [I] Initial number.
 233  *  b [I] Number to multiply a by.
 234  *
 235  * RETURNS
 236  *  The product of a and b.
 237  */
 238 ULONGLONG WINAPI RtlEnlargedUnsignedMultiply( UINT a, UINT b )
 239 {
 240     return (ULONGLONG)a * b;
 241 }
 242
 243
 244 /******************************************************************************
 245  *        RtlEnlargedUnsignedDivide   (NTDLL.@)
 246  *
 247  * Divide one 64 bit unsigned integer by a 32 bit unsigned integer, with remainder.
 248  *
 249  * PARAMS
 250  *  a      [I] Initial number.
 251  *  b      [I] Number to divide a by
 252  *  remptr [O] Destination for remainder
 253  *
 254  * RETURNS
 255  *  The dividend of a and b. If remptr is non-NULL it is set to the remainder.
 256  */
 257 UINT WINAPI RtlEnlargedUnsignedDivide( ULONGLONG a, UINT b, UINT *remptr )
 258 {
 259 #if defined(__i386__) && defined(__GNUC__)
 260     UINT ret, rem;
 261
 262     __asm__("divl %4"
 263             : "=a" (ret), "=d" (rem)
 264             : "0" ((UINT)a), "1" ((UINT)(a >> 32)), "g" (b) );
 265     if (remptr) *remptr = rem;
 266     return ret;
 267 #else
 268     UINT ret = a / b;
 269     if (remptr) *remptr = a % b;
 270     return ret;
 271 #endif
 272 }
 273
 274
 275 /******************************************************************************
 276  *        RtlExtendedLargeIntegerDivide   (NTDLL.@)
 277  *
 278  * Divide one 64 bit integer by a 32 bit integer, with remainder.
 279  *
 280  * PARAMS
 281  *  a   [I] Initial number.
 282  *  b   [I] Number to divide a by
 283  *  rem [O] Destination for remainder
 284  *
 285  * RETURNS
 286  *  The dividend of a and b. If rem is non-NULL it is set to the remainder.
 287  */
 288 LONGLONG WINAPI RtlExtendedLargeIntegerDivide( LONGLONG a, INT b, INT *rem )
 289 {
 290     LONGLONG ret = a / b;
 291     if (rem) *rem = a - b * ret;
 292     return ret;
 293 }
 294
 295
 296 /******************************************************************************
 297  *        RtlExtendedIntegerMultiply   (NTDLL.@)
 298  *
 299  * Multiply one 64 bit integer by another 32 bit integer.
 300  *
 301  * PARAMS
 302  *  a [I] Initial number.
 303  *  b [I] Number to multiply a by.
 304  *
 305  * RETURNS
 306  *  The product of a and b.
 307  */
 308 LONGLONG WINAPI RtlExtendedIntegerMultiply( LONGLONG a, INT b )
 309 {
 310     return a * b;
 311 }
 312
 313
 314 /******************************************************************************
 315  *        RtlExtendedMagicDivide   (NTDLL.@)
 316  *
 317  * Allows replacing a division by a longlong constant with a multiplication by
 318  * the inverse constant.
 319  *
 320  * RETURNS
 321  *  (dividend * inverse_divisor) >> (64 + shift)
 322  *
 323  * NOTES
 324  *  If the divisor of a division is constant, the constants inverse_divisor and
 325  *  shift must be chosen such that inverse_divisor = 2^(64 + shift) / divisor.
 326  *  Then we have RtlExtendedMagicDivide(dividend,inverse_divisor,shift) ==
 327  *  dividend * inverse_divisor / 2^(64 + shift) == dividend / divisor.
 328  *
 329  *  The Parameter inverse_divisor although defined as LONGLONG is used as
 330  *  ULONGLONG.
 331  */
 332 #define LOWER_32(A) ((A) & 0xffffffff)
 333 #define UPPER_32(A) ((A) >> 32)
 334 LONGLONG WINAPI RtlExtendedMagicDivide(
 335     LONGLONG dividend,        /* [I] Dividend to be divided by the constant divisor */
 336     LONGLONG inverse_divisor, /* [I] Constant computed manually as 2^(64+shift) / divisor */
 337     INT shift)                /* [I] Constant shift chosen to make inverse_divisor as big as possible for 64 bits */
 338 {
 339     ULONGLONG dividend_high;
 340     ULONGLONG dividend_low;
 341     ULONGLONG inverse_divisor_high;
 342     ULONGLONG inverse_divisor_low;
 343     ULONGLONG ah_bl;
 344     ULONGLONG al_bh;
 345     LONGLONG result;
 346     int positive;
 347
 348     if (dividend < 0) {
 349         dividend_high = UPPER_32((ULONGLONG) -dividend);
 350         dividend_low =  LOWER_32((ULONGLONG) -dividend);
 351         positive = 0;
 352     } else {
 353         dividend_high = UPPER_32((ULONGLONG) dividend);
 354         dividend_low =  LOWER_32((ULONGLONG) dividend);
 355         positive = 1;
 356     } /* if */
 357     inverse_divisor_high = UPPER_32((ULONGLONG) inverse_divisor);
 358     inverse_divisor_low =  LOWER_32((ULONGLONG) inverse_divisor);
 359
 360     ah_bl = dividend_high * inverse_divisor_low;
 361     al_bh = dividend_low * inverse_divisor_high;
 362
 363     result = (LONGLONG) ((dividend_high * inverse_divisor_high +
 364             UPPER_32(ah_bl) +
 365             UPPER_32(al_bh) +
 366             UPPER_32(LOWER_32(ah_bl) + LOWER_32(al_bh) +
 367                      UPPER_32(dividend_low * inverse_divisor_low))) >> shift);
 368
 369     if (positive) {
 370         return result;
 371     } else {
 372         return -result;
 373     } /* if */
 374 }
 375
 376
 377 /*************************************************************************
 378  *        RtlInterlockedCompareExchange64   (NTDLL.@)
 379  */
 380 LONGLONG WINAPI RtlInterlockedCompareExchange64( LONGLONG *dest, LONGLONG xchg, LONGLONG compare )
 381 {
 382     return __sync_val_compare_and_swap( dest, compare, xchg );
 383 }
 384
 385 #endif  /* _WIN64 */
 386
 387 /******************************************************************************
 388  *      RtlLargeIntegerToChar   [NTDLL.@]
 389  *
 390  * Convert an unsigned large integer to a character string.
 391  *
 392  * RETURNS
 393  *  Success: STATUS_SUCCESS. str contains the converted number
 394  *  Failure: STATUS_INVALID_PARAMETER, if base is not 0, 2, 8, 10 or 16.
 395  *           STATUS_BUFFER_OVERFLOW, if str would be larger than length.
 396  *           STATUS_ACCESS_VIOLATION, if str is NULL.
 397  *
 398  * NOTES
 399  *  Instead of base 0 it uses 10 as base.
 400  *  Writes at most length characters to the string str.
 401  *  Str is '\0' terminated when length allows it.
 402  *  When str fits exactly in length characters the '\0' is omitted.
 403  *  If value_ptr is NULL it crashes, as the native function does.
 404  *
 405  * DIFFERENCES
 406  * - Accept base 0 as 10 instead of crashing as native function does.
 407  * - The native function does produce garbage or STATUS_BUFFER_OVERFLOW for
 408  *   base 2, 8 and 16 when the value is larger than 0xFFFFFFFF.
 409  */
 410 NTSTATUS WINAPI RtlLargeIntegerToChar(
 411     const ULONGLONG *value_ptr, /* [I] Pointer to the value to be converted */
 412     ULONG base,                 /* [I] Number base for conversion (allowed 0, 2, 8, 10 or 16) */
 413     ULONG length,               /* [I] Length of the str buffer in bytes */
 414     PCHAR str)                  /* [O] Destination for the converted value */
 415 {
 416     ULONGLONG value = *value_ptr;
 417     CHAR buffer[65];
 418     PCHAR pos;
 419     CHAR digit;
 420     ULONG len;
 421
 422     if (base == 0) {
 423         base = 10;
 424     } else if (base != 2 && base != 8 && base != 10 && base != 16) {
 425         return STATUS_INVALID_PARAMETER;
 426     } /* if */
 427
 428     pos = &buffer[64];
 429     *pos = '\0';
 430
 431     do {
 432         pos--;
 433         digit = value % base;
 434         value = value / base;
 435         if (digit < 10) {
 436             *pos = '0' + digit;
 437         } else {
 438             *pos = 'A' + digit - 10;
 439         } /* if */
 440     } while (value != 0L);
 441
 442     len = &buffer[64] - pos;
 443     if (len > length) {
 444         return STATUS_BUFFER_OVERFLOW;
 445     } else if (str == NULL) {
 446         return STATUS_ACCESS_VIOLATION;
 447     } else if (len == length) {
 448         memcpy(str, pos, len);
 449     } else {
 450         memcpy(str, pos, len + 1);
 451     } /* if */
 452     return STATUS_SUCCESS;
 453 }
 454
 455
 456 /**************************************************************************
 457  *      RtlInt64ToUnicodeString (NTDLL.@)
 458  *
 459  * Convert a large unsigned integer to a '\0' terminated unicode string.
 460  *
 461  * RETURNS
 462  *  Success: STATUS_SUCCESS. str contains the converted number
 463  *  Failure: STATUS_INVALID_PARAMETER, if base is not 0, 2, 8, 10 or 16.
 464  *           STATUS_BUFFER_OVERFLOW, if str is too small to hold the string
 465  *                  (with the '\0' termination). In this case str->Length
 466  *                  is set to the length, the string would have (which can
 467  *                  be larger than the MaximumLength).
 468  *
 469  * NOTES
 470  *  Instead of base 0 it uses 10 as base.
 471  *  If str is NULL it crashes, as the native function does.
 472  *
 473  * DIFFERENCES
 474  * - Accept base 0 as 10 instead of crashing as native function does.
 475  * - Do not return STATUS_BUFFER_OVERFLOW when the string is long enough.
 476  *   The native function does this when the string would be longer than 31
 477  *   characters even when the string parameter is long enough.
 478  * - The native function does produce garbage or STATUS_BUFFER_OVERFLOW for
 479  *   base 2, 8 and 16 when the value is larger than 0xFFFFFFFF.
 480  */
 481 NTSTATUS WINAPI RtlInt64ToUnicodeString(
 482     ULONGLONG value,     /* [I] Value to be converted */
 483     ULONG base,          /* [I] Number base for conversion (allowed 0, 2, 8, 10 or 16) */
 484     UNICODE_STRING *str) /* [O] Destination for the converted value */
 485 {
 486     WCHAR buffer[65];
 487     PWCHAR pos;
 488     WCHAR digit;
 489
 490     if (base == 0) {
 491         base = 10;
 492     } else if (base != 2 && base != 8 && base != 10 && base != 16) {
 493         return STATUS_INVALID_PARAMETER;
 494     } /* if */
 495
 496     pos = &buffer[64];
 497     *pos = '\0';
 498
 499     do {
 500         pos--;
 501         digit = value % base;
 502         value = value / base;
 503         if (digit < 10) {
 504             *pos = '0' + digit;
 505         } else {
 506             *pos = 'A' + digit - 10;
 507         } /* if */
 508     } while (value != 0L);
 509
 510     str->Length = (&buffer[64] - pos) * sizeof(WCHAR);
 511     if (str->Length >= str->MaximumLength) {
 512         return STATUS_BUFFER_OVERFLOW;
 513     } else {
 514         memcpy(str->Buffer, pos, str->Length + sizeof(WCHAR));
 515     } /* if */
 516     return STATUS_SUCCESS;
 517 }
 518
 519
 520 #ifdef __i386__
 521
 522 /* those builtin functions use stdcall calling convention, but compilers reference them without stdcall declarations */
 523 #ifdef __WINE_PE_BUILD
 524 LONGLONG WINAPI _alldiv( LONGLONG a, LONGLONG b ) asm(__ASM_NAME("_alldiv"));
 525 LONGLONG WINAPI _allmul( LONGLONG a, LONGLONG b ) asm(__ASM_NAME("_allmul"));
 526 LONGLONG WINAPI _allrem( LONGLONG a, LONGLONG b ) asm(__ASM_NAME("_allrem"));
 527 ULONGLONG WINAPI _aulldiv( ULONGLONG a, ULONGLONG b ) asm(__ASM_NAME("_aulldiv"));
 528 ULONGLONG WINAPI _aullrem( ULONGLONG a, ULONGLONG b ) asm(__ASM_NAME("_aullrem"));
 529 #endif
 530
 531 static ULONGLONG udivmod(ULONGLONG a, ULONGLONG b, ULONGLONG *rem)
 532 {
 533     const ULARGE_INTEGER n = { .QuadPart = a };
 534     const ULARGE_INTEGER d = { .QuadPart = b };
 535     DWORD sr, carry, index;
 536     ULARGE_INTEGER q, r;
 537
 538     const unsigned n_uword_bits  = 32;
 539     const unsigned n_udword_bits = 64;
 540
 541     /* special cases, X is unknown, K != 0 */
 542     if (n.u.HighPart == 0)
 543     {
 544         if (d.u.HighPart == 0)
 545         {
 546             /* 0 X / 0 X */
 547             if (rem) *rem = n.u.LowPart % d.u.LowPart;
 548             return n.u.LowPart / d.u.LowPart;
 549         }
 550         /* 0 X / K X */
 551         if (rem) *rem = n.u.LowPart;
 552         return 0;
 553     }
 554
 555     /* n.u.HighPart != 0 */
 556     if (d.u.LowPart == 0)
 557     {
 558         if (d.u.HighPart == 0)
 559         {
 560             /* K X / 0 0 */
 561             if (rem) *rem = n.u.HighPart % d.u.LowPart;
 562             return n.u.HighPart / d.u.LowPart;
 563         }
 564         /* d.u.HighPart != 0 */
 565         if (n.u.LowPart == 0) {
 566             /* K 0 / K 0 */
 567             if (rem)
 568             {
 569                 r.u.HighPart = n.u.HighPart % d.u.HighPart;
 570                 r.u.LowPart = 0;
 571                 *rem = r.QuadPart;
 572             }
 573             return n.u.HighPart / d.u.HighPart;
 574         }
 575         /* K K / K 0 */
 576         if ((d.u.HighPart & (d.u.HighPart - 1)) == 0) /* if d is a power of 2 */
 577         {
 578             if (rem)
 579             {
 580                 r.u.LowPart = n.u.LowPart;
 581                 r.u.HighPart = n.u.HighPart & (d.u.HighPart - 1);
 582                 *rem = r.QuadPart;
 583             }
 584             BitScanForward(&index, d.u.HighPart);
 585             return n.u.HighPart >> index;
 586         }
 587         /* K K / K 0 */
 588         BitScanReverse(&index, d.u.HighPart);
 589         BitScanReverse(&sr, n.u.HighPart);
 590         sr -= index;
 591         /* 0 <= sr <= n_uword_bits - 2 or sr large */
 592         if (sr > n_uword_bits - 2)
 593         {
 594             if (rem) *rem = n.QuadPart;
 595             return 0;
 596         }
 597         ++sr;
 598         /* 1 <= sr <= n_uword_bits - 1 */
 599         /* q.QuadPart = n.QuadPart << (n_udword_bits - sr); */
 600         q.u.LowPart = 0;
 601         q.u.HighPart = n.u.LowPart << (n_uword_bits - sr);
 602         /* r.QuadPart = n.QuadPart >> sr; */
 603         r.u.HighPart = n.u.HighPart >> sr;
 604         r.u.LowPart = (n.u.HighPart << (n_uword_bits - sr)) | (n.u.LowPart >> sr);
 605     }
 606     else /* d.u.LowPart != 0 */
 607     {
 608         if (d.u.HighPart == 0)
 609         {
 610             /* K X / 0 K */
 611             if ((d.u.LowPart & (d.u.LowPart - 1)) == 0) /* if d is a power of 2 */
 612             {
 613                 if (rem) *rem = n.u.LowPart & (d.u.LowPart - 1);
 614                 if (d.u.LowPart == 1) return n.QuadPart;
 615                 BitScanForward(&sr, d.u.LowPart);
 616                 q.u.HighPart = n.u.HighPart >> sr;
 617                 q.u.LowPart = (n.u.HighPart << (n_uword_bits - sr)) | (n.u.LowPart >> sr);
 618                 return q.QuadPart;
 619             }
 620             BitScanReverse(&index, d.u.LowPart);
 621             BitScanReverse(&sr, n.u.HighPart);
 622             sr = 1 + n_uword_bits + sr - index;
 623             /* 2 <= sr <= n_udword_bits - 1
 624              * q.QuadPart = n.QuadPart << (n_udword_bits - sr);
 625              * r.QuadPart = n.QuadPart >> sr; */
 626             if (sr == n_uword_bits)
 627             {
 628                 q.u.LowPart = 0;
 629                 q.u.HighPart = n.u.LowPart;
 630                 r.u.HighPart = 0;
 631                 r.u.LowPart = n.u.HighPart;
 632             }
 633             else if (sr < n_uword_bits) /* 2 <= sr <= n_uword_bits - 1 */
 634             {
 635                 q.u.LowPart = 0;
 636                 q.u.HighPart = n.u.LowPart << (n_uword_bits - sr);
 637                 r.u.HighPart = n.u.HighPart >> sr;
 638                 r.u.LowPart = (n.u.HighPart << (n_uword_bits - sr)) | (n.u.LowPart >> sr);
 639             }
 640             else /* n_uword_bits + 1 <= sr <= n_udword_bits - 1 */
 641             {
 642                 q.u.LowPart = n.u.LowPart << (n_udword_bits - sr);
 643                 q.u.HighPart = (n.u.HighPart << (n_udword_bits - sr)) |
 644                     (n.u.LowPart >> (sr - n_uword_bits));
 645                 r.u.HighPart = 0;
 646                 r.u.LowPart = n.u.HighPart >> (sr - n_uword_bits);
 647             }
 648         }
 649         else
 650         {
 651             /* K X / K K */
 652             BitScanReverse(&index, d.u.HighPart);
 653             BitScanReverse(&sr, n.u.HighPart);
 654             sr -= index;
 655             /* 0 <= sr <= n_uword_bits - 1 or sr large */
 656             if (sr > n_uword_bits - 1)
 657             {
 658                 if (rem) *rem = n.QuadPart;
 659                 return 0;
 660             }
 661             ++sr;
 662             /* 1 <= sr <= n_uword_bits
 663              * q.QuadPart = n.QuadPart << (n_udword_bits - sr); */
 664             q.u.LowPart = 0;
 665             if (sr == n_uword_bits)
 666             {
 667                 q.u.HighPart = n.u.LowPart;
 668                 r.u.HighPart = 0;
 669                 r.u.LowPart = n.u.HighPart;
 670             }
 671             else
 672             {
 673                 q.u.HighPart = n.u.LowPart << (n_uword_bits - sr);
 674                 r.u.HighPart = n.u.HighPart >> sr;
 675                 r.u.LowPart = (n.u.HighPart << (n_uword_bits - sr)) | (n.u.LowPart >> sr);
 676             }
 677         }
 678     }
 679     /* Not a special case
 680      * q and r are initialized with:
 681      * q.QuadPart = n.QuadPart << (n_udword_bits - sr);
 682      * r.QuadPart = n.QuadPart >> sr;
 683      * 1 <= sr <= n_udword_bits - 1 */
 684     carry = 0;
 685     for (; sr > 0; --sr)
 686     {
 687         LONGLONG s;
 688         /* r:q = ((r:q)  << 1) | carry */
 689         r.u.HighPart = (r.u.HighPart << 1) | (r.u.LowPart >> (n_uword_bits - 1));
 690         r.u.LowPart = (r.u.LowPart << 1) | (q.u.HighPart >> (n_uword_bits - 1));
 691         q.u.HighPart = (q.u.HighPart << 1) | (q.u.LowPart >> (n_uword_bits - 1));
 692         q.u.LowPart = (q.u.LowPart << 1) | carry;
 693         /* if (r.QuadPart >= d.QuadPart)
 694          * {
 695          *      r.QuadPart -= d.QuadPart;
 696          *      carry = 1;
 697          * }
 698          */
 699         s = (LONGLONG)(d.QuadPart - r.QuadPart - 1) >> (n_udword_bits - 1);
 700         carry = s & 1;
 701         r.QuadPart -= d.QuadPart & s;
 702     }
 703     q.QuadPart = (q.QuadPart << 1) | carry;
 704     if (rem) *rem = r.QuadPart;
 705     return q.QuadPart;
 706 }
 707
 708 /******************************************************************************
 709  *        _alldiv   (NTDLL.@)
 710  *
 711  * Divide two 64 bit unsigned integers.
 712  *
 713  * PARAMS
 714  *  a [I] Initial number.
 715  *  b [I] Number to divide a by.
 716  *
 717  * RETURNS
 718  *  The dividend of a and b.
 719  */
 720 LONGLONG WINAPI _alldiv( LONGLONG a, LONGLONG b )
 721 {
 722     LONGLONG s_a = a >> 63;                    /* s_a = a < 0 ? -1 : 0 */
 723     LONGLONG s_b = b >> 63;                    /* s_b = b < 0 ? -1 : 0 */
 724     a = (a ^ s_a) - s_a;                       /* negate if s_a == -1 */
 725     b = (b ^ s_b) - s_b;                       /* negate if s_b == -1 */
 726     s_a ^= s_b;                                /* sign of quotient */
 727     return (udivmod(a, b, NULL) ^ s_a) - s_a;  /* negate if s_a == -1 */
 728 }
 729
 730
 731 /******************************************************************************
 732  *        _allmul   (NTDLL.@)
 733  *
 734  * Multiply two 64 bit integers.
 735  *
 736  * PARAMS
 737  *  a [I] Initial number.
 738  *  b [I] Number to multiply a by.
 739  *
 740  * RETURNS
 741  *  The product of a and b.
 742  */
 743 LONGLONG WINAPI _allmul( LONGLONG a, LONGLONG b )
 744 {
 745     LARGE_INTEGER x = { .QuadPart = a };
 746     LARGE_INTEGER y = { .QuadPart = b };
 747     LARGE_INTEGER r;
 748     unsigned int t;
 749
 750     const int bits_in_word_2 = 16;
 751     const unsigned int lower_mask = ~0u >> bits_in_word_2;
 752
 753     r.u.LowPart = (x.u.LowPart & lower_mask) * (y.u.LowPart & lower_mask);
 754     t = r.u.LowPart >> bits_in_word_2;
 755     r.u.LowPart &= lower_mask;
 756     t += (x.u.LowPart >> bits_in_word_2) * (y.u.LowPart & lower_mask);
 757     r.u.LowPart += (t & lower_mask) << bits_in_word_2;
 758     r.u.HighPart = t >> bits_in_word_2;
 759     t = r.u.LowPart >> bits_in_word_2;
 760     r.u.LowPart &= lower_mask;
 761     t += (y.u.LowPart >> bits_in_word_2) * (x.u.LowPart & lower_mask);
 762     r.u.LowPart += (t & lower_mask) << bits_in_word_2;
 763     r.u.HighPart += t >> bits_in_word_2;
 764     r.u.HighPart += (x.u.LowPart >> bits_in_word_2) * (y.u.LowPart >> bits_in_word_2);
 765
 766     r.u.HighPart += x.u.HighPart * y.u.LowPart + x.u.LowPart * y.u.HighPart;
 767     return r.QuadPart;
 768 }
 769
 770
 771 /******************************************************************************
 772  *        _allrem   (NTDLL.@)
 773  *
 774  * Calculate the remainder after dividing two 64 bit integers.
 775  *
 776  * PARAMS
 777  *  a [I] Initial number.
 778  *  b [I] Number to divide a by.
 779  *
 780  * RETURNS
 781  *  The remainder of a divided by b.
 782  */
 783 LONGLONG WINAPI _allrem( LONGLONG a, LONGLONG b )
 784 {
 785     LONGLONG s = b >> 63;          /* s = b < 0 ? -1 : 0 */
 786     ULONGLONG r;
 787     b = (b ^ s) - s;               /* negate if s == -1 */
 788     s = a >> 63;                   /* s = a < 0 ? -1 : 0 */
 789     a = (a ^ s) - s;               /* negate if s == -1 */
 790     udivmod(a, b, &r);
 791     return ((LONGLONG)r ^ s) - s;  /* negate if s == -1 */
 792 }
 793
 794
 795 /******************************************************************************
 796  *        _aulldiv   (NTDLL.@)
 797  *
 798  * Divide two 64 bit unsigned integers.
 799  *
 800  * PARAMS
 801  *  a [I] Initial number.
 802  *  b [I] Number to divide a by.
 803  *
 804  * RETURNS
 805  *  The dividend of a and b.
 806  */
 807 ULONGLONG WINAPI _aulldiv( ULONGLONG a, ULONGLONG b )
 808 {
 809     return udivmod(a, b, NULL);
 810 }
 811
 812 /******************************************************************************
 813  *        _allshl   (NTDLL.@)
 814  *
 815  * Shift a 64 bit integer to the left.
 816  *
 817  * PARAMS
 818  *  a [I] Initial number.
 819  *  b [I] Number to shift a by to the left.
 820  *
 821  * RETURNS
 822  *  The left-shifted value.
 823  */
 824 LONGLONG WINAPI _allshl( LONGLONG a, LONG b )
 825 {
 826     return a << b;
 827 }
 828
 829 /******************************************************************************
 830  *        _allshr   (NTDLL.@)
 831  *
 832  * Shift a 64 bit integer to the right.
 833  *
 834  * PARAMS
 835  *  a [I] Initial number.
 836  *  b [I] Number to shift a by to the right.
 837  *
 838  * RETURNS
 839  *  The right-shifted value.
 840  */
 841 LONGLONG WINAPI _allshr( LONGLONG a, LONG b )
 842 {
 843     return a >> b;
 844 }
 845
 846 /******************************************************************************
 847  *        _alldvrm   (NTDLL.@)
 848  *
 849  * Divide two 64 bit integers.
 850  *
 851  * PARAMS
 852  *  a [I] Initial number.
 853  *  b [I] Number to divide a by.
 854  *
 855  * RETURNS
 856  *  Returns the quotient of a and b in edx:eax.
 857  *  Returns the remainder of a and b in ebx:ecx.
 858  */
 859 __ASM_GLOBAL_FUNC( _alldvrm,
 860                    "pushl %ebp\n\t"
 861                    __ASM_CFI(".cfi_adjust_cfa_offset 4\n\t")
 862                    __ASM_CFI(".cfi_rel_offset %ebp,0\n\t")
 863                    "movl %esp,%ebp\n\t"
 864                    __ASM_CFI(".cfi_def_cfa_register %ebp\n\t")
 865                    "pushl 20(%ebp)\n\t"
 866                    "pushl 16(%ebp)\n\t"
 867                    "pushl 12(%ebp)\n\t"
 868                    "pushl 8(%ebp)\n\t"
 869                    "call " __ASM_NAME("_allrem") "\n\t"
 870                    "movl %edx,%ebx\n\t"
 871                    "pushl %eax\n\t"
 872                    "pushl 20(%ebp)\n\t"
 873                    "pushl 16(%ebp)\n\t"
 874                    "pushl 12(%ebp)\n\t"
 875                    "pushl 8(%ebp)\n\t"
 876                    "call " __ASM_NAME("_alldiv") "\n\t"
 877                    "popl %ecx\n\t"
 878                    "leave\n\t"
 879                    __ASM_CFI(".cfi_def_cfa %esp,4\n\t")
 880                    __ASM_CFI(".cfi_same_value %ebp\n\t")
 881                    "ret $16" )
 882
 883 /******************************************************************************
 884  *        _aullrem   (NTDLL.@)
 885  *
 886  * Calculate the remainder after dividing two 64 bit unsigned integers.
 887  *
 888  * PARAMS
 889  *  a [I] Initial number.
 890  *  b [I] Number to divide a by.
 891  *
 892  * RETURNS
 893  *  The remainder of a divided by b.
 894  */
 895 ULONGLONG WINAPI _aullrem( ULONGLONG a, ULONGLONG b )
 896 {
 897     ULONGLONG r;
 898     udivmod(a, b, &r);
 899     return r;
 900 }
 901
 902 /******************************************************************************
 903  *        _aullshr   (NTDLL.@)
 904  *
 905  * Shift a 64 bit unsigned integer to the right.
 906  *
 907  * PARAMS
 908  *  a [I] Initial number.
 909  *  b [I] Number to shift a by to the right.
 910  *
 911  * RETURNS
 912  *  The right-shifted value.
 913  */
 914 ULONGLONG WINAPI _aullshr( ULONGLONG a, LONG b )
 915 {
 916     return a >> b;
 917 }
 918
 919 /******************************************************************************
 920  *        _aulldvrm   (NTDLL.@)
 921  *
 922  * Divide two 64 bit unsigned integers.
 923  *
 924  * PARAMS
 925  *  a [I] Initial number.
 926  *  b [I] Number to divide a by.
 927  *
 928  * RETURNS
 929  *  Returns the quotient of a and b in edx:eax.
 930  *  Returns the remainder of a and b in ebx:ecx.
 931  */
 932 __ASM_GLOBAL_FUNC( _aulldvrm,
 933                    "pushl %ebp\n\t"
 934                    __ASM_CFI(".cfi_adjust_cfa_offset 4\n\t")
 935                    __ASM_CFI(".cfi_rel_offset %ebp,0\n\t")
 936                    "movl %esp,%ebp\n\t"
 937                    __ASM_CFI(".cfi_def_cfa_register %ebp\n\t")
 938                    "pushl 20(%ebp)\n\t"
 939                    "pushl 16(%ebp)\n\t"
 940                    "pushl 12(%ebp)\n\t"
 941                    "pushl 8(%ebp)\n\t"
 942                    "call " __ASM_NAME("_aullrem") "\n\t"
 943                    "movl %edx,%ebx\n\t"
 944                    "pushl %eax\n\t"
 945                    "pushl 20(%ebp)\n\t"
 946                    "pushl 16(%ebp)\n\t"
 947                    "pushl 12(%ebp)\n\t"
 948                    "pushl 8(%ebp)\n\t"
 949                    "call " __ASM_NAME("_aulldiv") "\n\t"
 950                    "popl %ecx\n\t"
 951                    "leave\n\t"
 952                    __ASM_CFI(".cfi_def_cfa %esp,4\n\t")
 953                    __ASM_CFI(".cfi_same_value %ebp\n\t")
 954                    "ret $16" )
 955
 956 #endif  /* __i386__ */