VirtualBox

Changeset 52335 in vbox for trunk/include/iprt


Ignore:
Timestamp:
Aug 11, 2014 12:30:20 PM (10 years ago)
Author:
vboxsync
Message:

RTBigNum: Added shift APIs, implemented a faster division algorithm, optimized multiplication on x86 & amd64.

Location:
trunk/include/iprt
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • trunk/include/iprt/asmdefs.mac

    r52292 r52335  
    276276; Begins a C callable exported procedure.
    277277%macro BEGINPROC_EXPORTED 1
     278 %ifdef RT_ASM_WITH_SEH64
     279  %ifdef ASM_FORMAT_PE
     280export  %1=NAME(%1)
     281  %endif
     282global     NAME(%1):function
     283proc_frame NAME(%1)
     284 %else
    278285EXPORTEDNAME_EX %1, function
     286 %endif
    279287%endmacro
    280288

  • trunk/include/iprt/bignum.h

    r52290 r52335  
    4343typedef uint32_t RTBIGNUMELEMENT;
    4444#endif
     45/** Pointer to a big integer number element. */
     46typedef RTBIGNUMELEMENT        *PRTBIGNUMELEMENT;
     47/** Pointer to a const big integer number element. */
     48typedef RTBIGNUMELEMENT const  *PCRTBIGNUMELEMENT;
     49
    4550/** The size (in bytes) of one array element. */
    4651#if ARCH_BITS == 64
    … …  
    5762# define RTBIGNUM_ELEMENT_BIT(iBit)     RT_BIT_32(iBit)
    5863#endif
     64/** The maximum value one element can hold. */
     65#if ARCH_BITS == 64
     66# define RTBIGNUM_ELEMENT_MAX           UINT64_MAX
     67#else
     68# define RTBIGNUM_ELEMENT_MAX           UINT32_MAX
     69#endif
     70/** Mask including all the element bits set to 1. */
     71#define RTBIGNUM_ELEMENT_MASK           RTBIGNUM_ELEMENT_MAX
     72
    5973
    6074/**
    … …  
    154168RTDECL(int) RTBigNumMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier);
    155169RTDECL(int) RTBigNumDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor);
     170RTDECL(int) RTBigNumDivideKnuth(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor);
     171RTDECL(int) RTBigNumDivideLong(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor);
    156172RTDECL(int) RTBigNumModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor);
    157173RTDECL(int) RTBigNumExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent);
     174RTDECL(int) RTBigNumShiftLeft(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits);
     175RTDECL(int) RTBigNumShiftRight(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits);
    158176
    159177RTDECL(int) RTBigNumModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus);

  • trunk/include/iprt/mangling.h

    r52213 r52335  
    27862786# define RTBigNumDestroy                                RT_MANGLER(RTBigNumDestroy)
    27872787# define RTBigNumDivide                                 RT_MANGLER(RTBigNumDivide)
     2788# define RTBigNumDivideKnuth                            RT_MANGLER(RTBigNumDivideKnuth)
     2789# define RTBigNumDivideLong                             RT_MANGLER(RTBigNumDivideLong)
    27882790# define RTBigNumExponentiate                           RT_MANGLER(RTBigNumExponentiate)
    27892791# define RTBigNumInit                                   RT_MANGLER(RTBigNumInit)
    … …  
    27942796# define RTBigNumNegate                                 RT_MANGLER(RTBigNumNegate)
    27952797# define RTBigNumNegateThis                             RT_MANGLER(RTBigNumNegateThis)
     2798# define RTBigNumShiftLeft                              RT_MANGLER(RTBigNumShiftLeft)
     2799# define RTBigNumShiftRight                             RT_MANGLER(RTBigNumShiftRight)
    27962800# define RTBigNumSubtract                               RT_MANGLER(RTBigNumSubtract)
    27972801# define RTBigNumToBytesBigEndian                       RT_MANGLER(RTBigNumToBytesBigEndian)

  • trunk/include/iprt/types.h

    r51856 r52335  
    402402typedef union RTUINT128U
    403403{
    404     /** Natural view.
    405      * WARNING! This member depends on the compiler supporting 128-bit stuff. */
    406     uint128_t   u;
    407     /** Hi/Low view. */
     404    /** Hi/Low view.
     405     * @remarks We put this first so we can have portable initializers
     406     *          (RTUINT128_INIT) */
    408407    struct
    409408    {
    … …  
    416415#endif
    417416    } s;
     417
     418    /** Natural view.
     419     * WARNING! This member depends on the compiler supporting 128-bit stuff. */
     420    uint128_t   u;
     421
    418422    /** Quad-Word view. */
    419423    struct
    … …  
    480484/** Pointer to a const 64-bit unsigned integer union. */
    481485typedef const RTUINT128U *PCRTUINT128U;
     486
     487/** @def RTUINT128_INIT
     488 * Portable RTUINT128U initializer. */
     489#ifdef RT_BIG_ENDIAN
     490# define RTUINT128_INIT(a_Hi, a_Lo) { a_Hi, a_Lo }
     491#else
     492# define RTUINT128_INIT(a_Hi, a_Lo) { a_Lo, a_Hi }
     493#endif
     494
     495/** @def RTUINT128_INIT_C
     496 * Portable RTUINT128U initializer for 64-bit constants. */
     497#ifdef RT_BIG_ENDIAN
     498# define RTUINT128_INIT_C(a_Hi, a_Lo) { UINT64_C(a_Hi), UINT64_C(a_Lo) }
     499#else
     500# define RTUINT128_INIT_C(a_Hi, a_Lo) { UINT64_C(a_Lo), UINT64_C(a_Hi) }
     501#endif
    482502
    483503

  • trunk/include/iprt/uint128.h

    r35492 r52335  
    3030#include <iprt/types.h>
    3131#include <iprt/err.h>
     32#include <iprt/asm.h>
     33#ifdef RT_ARCH_AMD64
     34# include <iprt/asm-math.h>
     35#endif
    3236
    3337RT_C_DECLS_BEGIN
    … …  
    101105
    102106
    103 RTDECL(PRTUINT128U) RTUInt128Add(PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2);
    104 RTDECL(PRTUINT128U) RTUInt128Sub(PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2);
    105 RTDECL(PRTUINT128U) RTUInt128Div(PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2);
    106 RTDECL(PRTUINT128U) RTUInt128Mod(PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2);
    107 RTDECL(PRTUINT128U) RTUInt128And(PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2);
    108 RTDECL(PRTUINT128U) RTUInt128Or( PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2);
    109 RTDECL(PRTUINT128U) RTUInt128Xor(PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2);
    110 RTDECL(PRTUINT128U) RTUInt128ShiftLeft( PRTUINT128U pResult, PCRTUINT128U pValue, int cBits);
    111 RTDECL(PRTUINT128U) RTUInt128ShiftRight(PRTUINT128U pResult, PCRTUINT128U pValue, int cBits);
    112 RTDECL(PRTUINT128U) RTUInt128BooleanNot(PRTUINT128U pResult, PCRTUINT128U pValue);
    113 RTDECL(PRTUINT128U) RTUInt128BitwiseNot(PRTUINT128U pResult, PCRTUINT128U pValue);
     107
     108
     109/**
     110 * Adds two 128-bit unsigned integer values.
     111 *
     112 * @returns pResult
     113 * @param   pResult             The result variable.
     114 * @param   pValue1             The first value.
     115 * @param   pValue2             The second value.
     116 */
     117DECLINLINE(PRTUINT128U) RTUInt128Add(PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2)
     118{
     119    pResult->s.Hi = pValue1->s.Hi + pValue2->s.Hi;
     120    pResult->s.Lo = pValue1->s.Lo + pValue2->s.Lo;
     121    if (pResult->s.Lo < pValue1->s.Lo)
     122        pResult->s.Hi++;
     123    return pResult;
     124}
     125
     126
     127/**
     128 * Adds a 128-bit and a 64-bit unsigned integer values.
     129 *
     130 * @returns pResult
     131 * @param   pResult             The result variable.
     132 * @param   pValue1             The first value.
     133 * @param   uValue2             The second value, 64-bit.
     134 */
     135DECLINLINE(PRTUINT128U) RTUInt128AddU64(PRTUINT128U pResult, PCRTUINT128U pValue1, uint64_t uValue2)
     136{
     137    pResult->s.Hi = pValue1->s.Hi;
     138    pResult->s.Lo = pValue1->s.Lo + uValue2;
     139    if (pResult->s.Lo < pValue1->s.Lo)
     140        pResult->s.Hi++;
     141    return pResult;
     142}
     143
     144
     145/**
     146 * Subtracts a 128-bit unsigned integer value from another.
     147 *
     148 * @returns pResult
     149 * @param   pResult             The result variable.
     150 * @param   pValue1             The minuend value.
     151 * @param   pValue2             The subtrahend value.
     152 */
     153DECLINLINE(PRTUINT128U) RTUInt128Sub(PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2)
     154{
     155    pResult->s.Lo = pValue1->s.Lo - pValue2->s.Lo;
     156    pResult->s.Hi = pValue1->s.Hi - pValue2->s.Hi;
     157    if (pResult->s.Lo > pValue1->s.Lo)
     158        pResult->s.Hi--;
     159    return pResult;
     160}
     161
     162
     163/**
     164 * Multiplies two 128-bit unsigned integer values.
     165 *
     166 * @returns pResult
     167 * @param   pResult             The result variable.
     168 * @param   pValue1             The first value.
     169 * @param   pValue2             The second value.
     170 */
     171DECLINLINE(PRTUINT128U) RTUInt128Mul(PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2)
     172{
     173    RTUINT64U uTmp;
     174
     175    /* multiply all dwords in v1 by v2.dw0. */
     176    pResult->s.Lo = (uint64_t)pValue1->DWords.dw0 * pValue2->DWords.dw0;
     177
     178    uTmp.u = (uint64_t)pValue1->DWords.dw1 * pValue2->DWords.dw0;
     179    pResult->DWords.dw3 = 0;
     180    pResult->DWords.dw2 = uTmp.DWords.dw1;
     181    pResult->DWords.dw1 += uTmp.DWords.dw0;
     182    if (pResult->DWords.dw1 < uTmp.DWords.dw0)
     183        if (pResult->DWords.dw2++ == UINT32_MAX)
     184            pResult->DWords.dw3++;
     185
     186    pResult->s.Hi += (uint64_t)pValue1->DWords.dw2 * pValue2->DWords.dw0;
     187    pResult->DWords.dw3     += pValue1->DWords.dw3 * pValue2->DWords.dw0;
     188
     189    /* multiply dw0, dw1 & dw2 in v1 by v2.dw1. */
     190    uTmp.u = (uint64_t)pValue1->DWords.dw0 * pValue2->DWords.dw1;
     191    pResult->DWords.dw1 += uTmp.DWords.dw0;
     192    if (pResult->DWords.dw1 < uTmp.DWords.dw0)
     193        if (pResult->DWords.dw2++ == UINT32_MAX)
     194            pResult->DWords.dw3++;
     195
     196    pResult->DWords.dw2 += uTmp.DWords.dw1;
     197    if (pResult->DWords.dw2 < uTmp.DWords.dw1)
     198        pResult->DWords.dw3++;
     199
     200    pResult->s.Hi += (uint64_t)pValue1->DWords.dw1 * pValue2->DWords.dw1;
     201    pResult->DWords.dw3     += pValue1->DWords.dw2 * pValue2->DWords.dw1;
     202
     203    /* multiply dw0 & dw1 in v1 by v2.dw2. */
     204    pResult->s.Hi += (uint64_t)pValue1->DWords.dw0 * pValue2->DWords.dw2;
     205    pResult->DWords.dw3     += pValue1->DWords.dw1 * pValue2->DWords.dw2;
     206
     207    /* multiply dw0 in v1 by v2.dw3. */
     208    pResult->DWords.dw3     += pValue1->DWords.dw0 * pValue2->DWords.dw3;
     209
     210    return pResult;
     211}
     212
     213
     214/**
     215 * Multiplies an 128-bit unsigned integer by a 64-bit unsigned integer value.
     216 *
     217 * @returns pResult
     218 * @param   pResult             The result variable.
     219 * @param   pValue1             The first value.
     220 * @param   uValue2             The second value, 64-bit.
     221 */
     222#if defined(RT_ARCH_AMD64)
     223RTDECL(PRTUINT128U) RTUInt128MulByU64(PRTUINT128U pResult, PCRTUINT128U pValue1, uint64_t uValue2);
     224#else
     225DECLINLINE(PRTUINT128U) RTUInt128MulByU64(PRTUINT128U pResult, PCRTUINT128U pValue1, uint64_t uValue2)
     226{
     227    uint32_t const uLoValue2 = (uint32_t)uValue2;
     228    uint32_t const uHiValue2 = (uint32_t)(uValue2 >> 32);
     229    RTUINT64U uTmp;
     230
     231    /* multiply all dwords in v1 by uLoValue1. */
     232    pResult->s.Lo = (uint64_t)pValue1->DWords.dw0 * uLoValue2;
     233
     234    uTmp.u = (uint64_t)pValue1->DWords.dw1 * uLoValue2;
     235    pResult->DWords.dw3 = 0;
     236    pResult->DWords.dw2 = uTmp.DWords.dw1;
     237    pResult->DWords.dw1 += uTmp.DWords.dw0;
     238    if (pResult->DWords.dw1 < uTmp.DWords.dw0)
     239        if (pResult->DWords.dw2++ == UINT32_MAX)
     240            pResult->DWords.dw3++;
     241
     242    pResult->s.Hi += (uint64_t)pValue1->DWords.dw2 * uLoValue2;
     243    pResult->DWords.dw3     += pValue1->DWords.dw3 * uLoValue2;
     244
     245    /* multiply dw0, dw1 & dw2 in v1 by uHiValue2. */
     246    uTmp.u = (uint64_t)pValue1->DWords.dw0 * uHiValue2;
     247    pResult->DWords.dw1 += uTmp.DWords.dw0;
     248    if (pResult->DWords.dw1 < uTmp.DWords.dw0)
     249        if (pResult->DWords.dw2++ == UINT32_MAX)
     250            pResult->DWords.dw3++;
     251
     252    pResult->DWords.dw2 += uTmp.DWords.dw1;
     253    if (pResult->DWords.dw2 < uTmp.DWords.dw1)
     254        pResult->DWords.dw3++;
     255
     256    pResult->s.Hi += (uint64_t)pValue1->DWords.dw1 * uHiValue2;
     257    pResult->DWords.dw3     += pValue1->DWords.dw2 * uHiValue2;
     258
     259    return pResult;
     260}
     261#endif
     262
     263
     264/**
     265 * Multiplies two 64-bit unsigned integer values with 128-bit precision.
     266 *
     267 * @returns pResult
     268 * @param   pResult             The result variable.
     269 * @param   uValue1             The first value. 64-bit.
     270 * @param   uValue2             The second value, 64-bit.
     271 */
     272DECLINLINE(PRTUINT128U) RTUInt128MulU64ByU64(PRTUINT128U pResult, uint64_t uValue1, uint64_t uValue2)
     273{
     274#ifdef RT_ARCH_AMD64
     275    pResult->s.Lo = ASMMult2xU64Ret2xU64(uValue1, uValue2, &pResult->s.Hi);
     276#else
     277    uint32_t const uLoValue1 = (uint32_t)uValue1;
     278    uint32_t const uHiValue1 = (uint32_t)(uValue1 >> 32);
     279    uint32_t const uLoValue2 = (uint32_t)uValue2;
     280    uint32_t const uHiValue2 = (uint32_t)(uValue2 >> 32);
     281    RTUINT64U uTmp;
     282
     283    /* Multiply uLoValue1 and uHiValue1 by uLoValue1. */
     284    pResult->s.Lo = (uint64_t)uLoValue1 * uLoValue2;
     285
     286    uTmp.u = (uint64_t)uHiValue1 * uLoValue2;
     287    pResult->DWords.dw3 = 0;
     288    pResult->DWords.dw2 = uTmp.DWords.dw1;
     289    pResult->DWords.dw1 += uTmp.DWords.dw0;
     290    if (pResult->DWords.dw1 < uTmp.DWords.dw0)
     291        if (pResult->DWords.dw2++ == UINT32_MAX)
     292            pResult->DWords.dw3++;
     293
     294    /* Multiply uLoValue1 and uHiValue1 by uHiValue2. */
     295    uTmp.u = (uint64_t)uLoValue1 * uHiValue2;
     296    pResult->DWords.dw1 += uTmp.DWords.dw0;
     297    if (pResult->DWords.dw1 < uTmp.DWords.dw0)
     298        if (pResult->DWords.dw2++ == UINT32_MAX)
     299            pResult->DWords.dw3++;
     300
     301    pResult->DWords.dw2 += uTmp.DWords.dw1;
     302    if (pResult->DWords.dw2 < uTmp.DWords.dw1)
     303        pResult->DWords.dw3++;
     304
     305    pResult->s.Hi += (uint64_t)uHiValue1 * uHiValue2;
     306#endif
     307    return pResult;
     308}
     309
     310
     311DECLINLINE(PRTUINT128U) RTUInt128DivRem(PRTUINT128U pQuotient, PRTUINT128U pRemainder, PCRTUINT128U pValue1, PCRTUINT128U pValue2);
     312
     313/**
     314 * Divides a 128-bit unsigned integer value by another.
     315 *
     316 * @returns pResult
     317 * @param   pResult             The result variable.
     318 * @param   pValue1             The dividend value.
     319 * @param   pValue2             The divisor value.
     320 */
     321DECLINLINE(PRTUINT128U) RTUInt128Div(PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2)
     322{
     323    RTUINT128U Ignored;
     324    return RTUInt128DivRem(pResult, &Ignored, pValue1, pValue2);
     325}
     326
     327
     328/**
     329 * Divides a 128-bit unsigned integer value by another, returning the remainder.
     330 *
     331 * @returns pResult
     332 * @param   pResult             The result variable (remainder).
     333 * @param   pValue1             The dividend value.
     334 * @param   pValue2             The divisor value.
     335 */
     336DECLINLINE(PRTUINT128U) RTUInt128Mod(PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2)
     337{
     338    RTUINT128U Ignored;
     339    RTUInt128DivRem(&Ignored, pResult, pValue1, pValue2);
     340    return pResult;
     341}
     342
     343
     344/**
     345 * Bitwise AND of two 128-bit unsigned integer values.
     346 *
     347 * @returns pResult
     348 * @param   pResult             The result variable.
     349 * @param   pValue1             The first value.
     350 * @param   pValue2             The second value.
     351 */
     352DECLINLINE(PRTUINT128U) RTUInt128And(PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2)
     353{
     354    pResult->s.Hi = pValue1->s.Hi & pValue2->s.Hi;
     355    pResult->s.Lo = pValue1->s.Lo & pValue2->s.Lo;
     356    return pResult;
     357}
     358
     359
     360/**
     361 * Bitwise OR of two 128-bit unsigned integer values.
     362 *
     363 * @returns pResult
     364 * @param   pResult             The result variable.
     365 * @param   pValue1             The first value.
     366 * @param   pValue2             The second value.
     367 */
     368DECLINLINE(PRTUINT128U) RTUInt128Or( PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2)
     369{
     370    pResult->s.Hi = pValue1->s.Hi | pValue2->s.Hi;
     371    pResult->s.Lo = pValue1->s.Lo | pValue2->s.Lo;
     372    return pResult;
     373}
     374
     375
     376/**
     377 * Bitwise XOR of two 128-bit unsigned integer values.
     378 *
     379 * @returns pResult
     380 * @param   pResult             The result variable.
     381 * @param   pValue1             The first value.
     382 * @param   pValue2             The second value.
     383 */
     384DECLINLINE(PRTUINT128U) RTUInt128Xor(PRTUINT128U pResult, PCRTUINT128U pValue1, PCRTUINT128U pValue2)
     385{
     386    pResult->s.Hi = pValue1->s.Hi ^ pValue2->s.Hi;
     387    pResult->s.Lo = pValue1->s.Lo ^ pValue2->s.Lo;
     388    return pResult;
     389}
     390
     391
     392/**
     393 * Shifts a 128-bit unsigned integer value @a cBits to the left.
     394 *
     395 * @returns pResult
     396 * @param   pResult             The result variable.
     397 * @param   pValue              The value to shift.
     398 * @param   cBits               The number of bits to shift it.
     399 */
     400DECLINLINE(PRTUINT128U) RTUInt128ShiftLeft(PRTUINT128U pResult, PCRTUINT128U pValue, int cBits)
     401{
     402    cBits &= 127;
     403    if (cBits < 64)
     404    {
     405        pResult->s.Lo = pValue->s.Lo << cBits;
     406        pResult->s.Hi = (pValue->s.Hi << cBits) | (pValue->s.Lo >> (64 - cBits));
     407    }
     408    else
     409    {
     410        pResult->s.Lo = 0;
     411        pResult->s.Hi = pValue->s.Lo << (cBits - 64);
     412    }
     413    return pResult;
     414}
     415
     416
     417/**
     418 * Shifts a 128-bit unsigned integer value @a cBits to the right.
     419 *
     420 * @returns pResult
     421 * @param   pResult             The result variable.
     422 * @param   pValue              The value to shift.
     423 * @param   cBits               The number of bits to shift it.
     424 */
     425DECLINLINE(PRTUINT128U) RTUInt128ShiftRight(PRTUINT128U pResult, PCRTUINT128U pValue, int cBits)
     426{
     427    cBits &= 127;
     428    if (cBits < 64)
     429    {
     430        pResult->s.Hi = pValue->s.Hi >> cBits;
     431        pResult->s.Lo = (pValue->s.Lo >> cBits) | (pValue->s.Hi << (64 - cBits));
     432    }
     433    else
     434    {
     435        pResult->s.Hi = 0;
     436        pResult->s.Lo = pValue->s.Hi >> (cBits - 64);
     437    }
     438    return pResult;
     439}
     440
     441
     442/**
     443 * Boolean not (result 0 or 1).
     444 *
     445 * @returns pResult.
     446 * @param   pResult             The result variable.
     447 * @param   pValue              The value.
     448 */
     449DECLINLINE(PRTUINT128U) RTUInt128BooleanNot(PRTUINT128U pResult, PCRTUINT128U pValue)
     450{
     451    pResult->s.Hi = 0;
     452    pResult->s.Lo = pValue->s.Lo || pValue->s.Hi ? 0 : 1;
     453    return pResult;
     454}
     455
     456
     457/**
     458 * Bitwise not (flips each bit of the 128 bits).
     459 *
     460 * @returns pResult.
     461 * @param   pResult             The result variable.
     462 * @param   pValue              The value.
     463 */
     464DECLINLINE(PRTUINT128U) RTUInt128BitwiseNot(PRTUINT128U pResult, PCRTUINT128U pValue)
     465{
     466    pResult->s.Hi = ~pValue->s.Hi;
     467    pResult->s.Lo = ~pValue->s.Lo;
     468    return pResult;
     469}
    114470
    115471
    … …  
    239595
    240596
    241 RTDECL(PRTUINT128U) RTUInt128AssignAdd(PRTUINT128U pValue1Result, PCRTUINT128U pValue2);
    242 RTDECL(PRTUINT128U) RTUInt128AssignSub(PRTUINT128U pValue1Result, PCRTUINT128U pValue2);
    243 RTDECL(PRTUINT128U) RTUInt128AssignDiv(PRTUINT128U pValue1Result, PCRTUINT128U pValue2);
    244 RTDECL(PRTUINT128U) RTUInt128AssignMod(PRTUINT128U pValue1Result, PCRTUINT128U pValue2);
     597/**
     598 * Adds two 128-bit unsigned integer values, storing the result in the first.
     599 *
     600 * @returns pValue1Result.
     601 * @param   pValue1Result   The first value and result.
     602 * @param   pValue2         The second value.
     603 */
     604DECLINLINE(PRTUINT128U) RTUInt128AssignAdd(PRTUINT128U pValue1Result, PCRTUINT128U pValue2)
     605{
     606    uint64_t const uTmp = pValue1Result->s.Lo;
     607    pValue1Result->s.Lo += pValue2->s.Lo;
     608    if (pValue1Result->s.Lo < uTmp)
     609        pValue1Result->s.Hi++;
     610    pValue1Result->s.Hi += pValue2->s.Hi;
     611    return pValue1Result;
     612}
     613
     614
     615/**
     616 * Adds a 64-bit unsigned integer value to a 128-bit unsigned integer values,
     617 * storing the result in the 128-bit one.
     618 *
     619 * @returns pValue1Result.
     620 * @param   pValue1Result   The first value and result.
     621 * @param   uValue2         The second value, 64-bit.
     622 */
     623DECLINLINE(PRTUINT128U) RTUInt128AssignAddU64(PRTUINT128U pValue1Result, uint64_t uValue2)
     624{
     625    pValue1Result->s.Lo += uValue2;
     626    if (pValue1Result->s.Lo < uValue2)
     627        pValue1Result->s.Hi++;
     628    return pValue1Result;
     629}
     630
     631
     632/**
     633 * Subtracts two 128-bit unsigned integer values, storing the result in the
     634 * first.
     635 *
     636 * @returns pValue1Result.
     637 * @param   pValue1Result   The minuend value and result.
     638 * @param   pValue2         The subtrahend value.
     639 */
     640DECLINLINE(PRTUINT128U) RTUInt128AssignSub(PRTUINT128U pValue1Result, PCRTUINT128U pValue2)
     641{
     642    uint64_t const uTmp = pValue1Result->s.Lo;
     643    pValue1Result->s.Lo -= pValue2->s.Lo;
     644    if (pValue1Result->s.Lo > uTmp)
     645        pValue1Result->s.Hi--;
     646    pValue1Result->s.Hi -= pValue2->s.Hi;
     647    return pValue1Result;
     648}
     649
     650
     651/**
     652 * Multiplies two 128-bit unsigned integer values, storing the result in the
     653 * first.
     654 *
     655 * @returns pValue1Result.
     656 * @param   pValue1Result   The first value and result.
     657 * @param   pValue2         The second value.
     658 */
     659DECLINLINE(PRTUINT128U) RTUInt128AssignMul(PRTUINT128U pValue1Result, PCRTUINT128U pValue2)
     660{
     661    RTUINT128U Result;
     662    RTUInt128Mul(&Result, pValue1Result, pValue2);
     663    *pValue1Result = Result;
     664    return pValue1Result;
     665}
     666
     667
     668/**
     669 * Divides a 128-bit unsigned integer value by another, storing the result in
     670 * the first.
     671 *
     672 * @returns pValue1Result.
     673 * @param   pValue1Result   The dividend value and result.
     674 * @param   pValue2         The divisor value.
     675 */
     676DECLINLINE(PRTUINT128U) RTUInt128AssignDiv(PRTUINT128U pValue1Result, PCRTUINT128U pValue2)
     677{
     678    RTUINT128U Result;
     679    RTUINT128U Ignored;
     680    RTUInt128DivRem(&Result, &Ignored, pValue1Result, pValue2);
     681    *pValue1Result = Result;
     682    return pValue1Result;
     683}
     684
     685
     686/**
     687 * Divides a 128-bit unsigned integer value by another, storing the remainder in
     688 * the first.
     689 *
     690 * @returns pValue1Result.
     691 * @param   pValue1Result   The dividend value and result (remainder).
     692 * @param   pValue2         The divisor value.
     693 */
     694DECLINLINE(PRTUINT128U) RTUInt128AssignMod(PRTUINT128U pValue1Result, PCRTUINT128U pValue2)
     695{
     696    RTUINT128U Ignored;
     697    RTUINT128U Result;
     698    RTUInt128DivRem(&Ignored, &Result, pValue1Result, pValue2);
     699    *pValue1Result = Result;
     700    return pValue1Result;
     701}
    245702
    246703
    … …  
    313770    return pValue1Result;
    314771}
     772
     773
     774/**
     775 * ORs in a bit and assign the result to the input value.
     776 *
     777 * @returns pValue1Result.
     778 * @param   pValue1Result   The first value and result.
     779 * @param   iBit            The bit to set (0 based).
     780 */
     781DECLINLINE(PRTUINT128U) RTUInt128AssignOrBit(PRTUINT128U pValue1Result, uint32_t iBit)
     782{
     783#if ARCH_BITS >= 64
     784    if (iBit >= 64)
     785        pValue1Result->s.Hi |= RT_BIT_64(iBit - 64);
     786    else
     787        pValue1Result->s.Lo |= RT_BIT_64(iBit);
     788#else
     789    if (iBit >= 64)
     790    {
     791        if (iBit >= 96)
     792            pValue1Result->DWords.dw3 |= RT_BIT_32(iBit - 96);
     793        else
     794            pValue1Result->DWords.dw2 |= RT_BIT_32(iBit - 64);
     795    }
     796    else
     797    {
     798        if (iBit >= 32)
     799            pValue1Result->DWords.dw1 |= RT_BIT_32(iBit - 32);
     800        else
     801            pValue1Result->DWords.dw0 |= RT_BIT_32(iBit);
     802    }
     803#endif
     804    return pValue1Result;
     805}
     806
    315807
    316808
    … …  
    457949    return 0;
    458950#else
     951    if (pValue1->DWords.dw3 != pValue2->DWords.dw3)
     952        return pValue1->DWords.dw3 > pValue2->DWords.dw3 ? 1 : -1;
     953    if (pValue1->DWords.dw2 != pValue2->DWords.dw2)
     954        return pValue1->DWords.dw2 > pValue2->DWords.dw2 ? 1 : -1;
     955    if (pValue1->DWords.dw1 != pValue2->DWords.dw1)
     956        return pValue1->DWords.dw1 > pValue2->DWords.dw1 ? 1 : -1;
    459957    if (pValue1->DWords.dw0 != pValue2->DWords.dw0)
    460958        return pValue1->DWords.dw0 > pValue2->DWords.dw0 ? 1 : -1;
    461     if (pValue1->DWords.dw1 != pValue2->DWords.dw1)
    462         return pValue1->DWords.dw1 > pValue2->DWords.dw1 ? 1 : -1;
    463     if (pValue1->DWords.dw2 != pValue2->DWords.dw2)
    464         return pValue1->DWords.dw2 > pValue2->DWords.dw2 ? 1 : -1;
    465     if (pValue1->DWords.dw3 != pValue2->DWords.dw3)
    466         return pValue1->DWords.dw3 > pValue2->DWords.dw3 ? 1 : -1;
    467959    return 0;
     960#endif
     961}
     962
     963
     964/**
     965 * Tests if a 128-bit unsigned integer value is smaller than another.
     966 *
     967 * @returns true if the first value is smaller, false if not.
     968 * @param   pValue1             The first value.
     969 * @param   pValue2             The second value.
     970 */
     971DECLINLINE(bool) RTUInt128IsSmaller(PCRTUINT128U pValue1, PCRTUINT128U pValue2)
     972{
     973#if ARCH_BITS >= 64
     974    return pValue1->s.Hi < pValue2->s.Hi
     975        || (   pValue1->s.Hi == pValue2->s.Hi
     976            && pValue1->s.Lo  < pValue2->s.Lo);
     977#else
     978    return pValue1->DWords.dw3 < pValue2->DWords.dw3
     979        || (   pValue1->DWords.dw3 == pValue2->DWords.dw3
     980            && (   pValue1->DWords.dw2  < pValue2->DWords.dw2
     981                || (   pValue1->DWords.dw2 == pValue2->DWords.dw2
     982                    && (   pValue1->DWords.dw1  < pValue2->DWords.dw1
     983                        || (   pValue1->DWords.dw1 == pValue2->DWords.dw1
     984                            && pValue1->DWords.dw0  < pValue2->DWords.dw0)))));
     985#endif
     986}
     987
     988
     989/**
     990 * Tests if a 128-bit unsigned integer value is larger than another.
     991 *
     992 * @returns true if the first value is larger, false if not.
     993 * @param   pValue1             The first value.
     994 * @param   pValue2             The second value.
     995 */
     996DECLINLINE(bool) RTUInt128IsLarger(PCRTUINT128U pValue1, PCRTUINT128U pValue2)
     997{
     998#if ARCH_BITS >= 64
     999    return pValue1->s.Hi > pValue2->s.Hi
     1000        || (   pValue1->s.Hi == pValue2->s.Hi
     1001            && pValue1->s.Lo  > pValue2->s.Lo);
     1002#else
     1003    return pValue1->DWords.dw3 > pValue2->DWords.dw3
     1004        || (   pValue1->DWords.dw3 == pValue2->DWords.dw3
     1005            && (   pValue1->DWords.dw2  > pValue2->DWords.dw2
     1006                || (   pValue1->DWords.dw2 == pValue2->DWords.dw2
     1007                    && (   pValue1->DWords.dw1  > pValue2->DWords.dw1
     1008                        || (   pValue1->DWords.dw1 == pValue2->DWords.dw1
     1009                            && pValue1->DWords.dw0  > pValue2->DWords.dw0)))));
     1010#endif
     1011}
     1012
     1013
     1014/**
     1015 * Tests if a 128-bit unsigned integer value is larger or equal than another.
     1016 *
     1017 * @returns true if the first value is larger or equal, false if not.
     1018 * @param   pValue1             The first value.
     1019 * @param   pValue2             The second value.
     1020 */
     1021DECLINLINE(bool) RTUInt128IsLargerOrEqual(PCRTUINT128U pValue1, PCRTUINT128U pValue2)
     1022{
     1023#if ARCH_BITS >= 64
     1024    return pValue1->s.Hi > pValue2->s.Hi
     1025        || (   pValue1->s.Hi == pValue2->s.Hi
     1026            && pValue1->s.Lo >= pValue2->s.Lo);
     1027#else
     1028    return pValue1->DWords.dw3 > pValue2->DWords.dw3
     1029        || (   pValue1->DWords.dw3 == pValue2->DWords.dw3
     1030            && (   pValue1->DWords.dw2  > pValue2->DWords.dw2
     1031                || (   pValue1->DWords.dw2 == pValue2->DWords.dw2
     1032                    && (   pValue1->DWords.dw1  > pValue2->DWords.dw1
     1033                        || (   pValue1->DWords.dw1 == pValue2->DWords.dw1
     1034                            && pValue1->DWords.dw0 >= pValue2->DWords.dw0)))));
    4681035#endif
    4691036}
    … …  
    6911258}
    6921259
     1260
     1261DECLINLINE(uint32_t) RTUInt128BitCount(PCRTUINT128U pValue)
     1262{
     1263    uint32_t cBits;
     1264    if (pValue->s.Hi != 0)
     1265    {
     1266        if (pValue->DWords.dw3)
     1267            cBits = 96 + ASMBitLastSetU32(pValue->DWords.dw3);
     1268        else
     1269            cBits = 64 + ASMBitLastSetU32(pValue->DWords.dw2);
     1270    }
     1271    else
     1272    {
     1273        if (pValue->DWords.dw1)
     1274            cBits = 32 + ASMBitLastSetU32(pValue->DWords.dw1);
     1275        else
     1276            cBits =  0 + ASMBitLastSetU32(pValue->DWords.dw0);
     1277    }
     1278    return cBits;
     1279}
     1280
     1281
     1282/**
     1283 * Divides a 128-bit unsigned integer value by another, returning both quotient
     1284 * and remainder.
     1285 *
     1286 * @returns pQuotient, NULL if pValue2 is 0.
     1287 * @param   pQuotient           Where to return the quotient.
     1288 * @param   pRemainder          Where to return the remainder.
     1289 * @param   pValue1             The dividend value.
     1290 * @param   pValue2             The divisor value.
     1291 */
     1292DECLINLINE(PRTUINT128U) RTUInt128DivRem(PRTUINT128U pQuotient, PRTUINT128U pRemainder, PCRTUINT128U pValue1, PCRTUINT128U pValue2)
     1293{
     1294    int iDiff;
     1295
     1296    /*
     1297     * Sort out all the special cases first.
     1298     */
     1299    /* Divide by zero or 1? */
     1300    if (!pValue2->s.Hi)
     1301    {
     1302        if (!pValue2->s.Lo)
     1303            return NULL;
     1304
     1305        if (pValue2->s.Lo == 1)
     1306        {
     1307            RTUInt128SetZero(pRemainder);
     1308            *pQuotient = *pValue1;
     1309            return pQuotient;
     1310        }
     1311        /** @todo RTUint128DivModBy64 */
     1312    }
     1313
     1314    /* Dividend is smaller? */
     1315    iDiff = RTUInt128Compare(pValue1, pValue2);
     1316    if (iDiff < 0)
     1317    {
     1318        *pRemainder = *pValue1;
     1319        RTUInt128SetZero(pQuotient);
     1320    }
     1321
     1322    /* The values are equal? */
     1323    else if (iDiff == 0)
     1324    {
     1325        RTUInt128SetZero(pRemainder);
     1326        RTUInt128AssignU64(pQuotient, 1);
     1327    }
     1328    else
     1329    {
     1330        /*
     1331         * Prepare.
     1332         */
     1333        uint32_t   iBitAdder = RTUInt128BitCount(pValue1) - RTUInt128BitCount(pValue2);
     1334        RTUINT128U NormDivisor = *pValue2;
     1335        if (iBitAdder)
     1336        {
     1337            RTUInt128ShiftLeft(&NormDivisor, pValue2, iBitAdder);
     1338            if (RTUInt128IsLarger(&NormDivisor, pValue1))
     1339            {
     1340                RTUInt128AssignShiftRight(&NormDivisor, 1);
     1341                iBitAdder--;
     1342            }
     1343        }
     1344        else
     1345            NormDivisor = *pValue2;
     1346
     1347        RTUInt128SetZero(pQuotient);
     1348        *pRemainder = *pValue1;
     1349
     1350        /*
     1351         * Do the division.
     1352         */
     1353        if (RTUInt128IsLargerOrEqual(pRemainder, pValue2))
     1354        {
     1355            for (;;)
     1356            {
     1357                if (RTUInt128IsLargerOrEqual(pRemainder, &NormDivisor))
     1358                {
     1359                    RTUInt128AssignSub(pRemainder, &NormDivisor);
     1360                    RTUInt128AssignOrBit(pQuotient, iBitAdder);
     1361                }
     1362                if (RTUInt128IsSmaller(pRemainder, pValue2))
     1363                    break;
     1364                RTUInt128AssignShiftRight(&NormDivisor, 1);
     1365                iBitAdder--;
     1366            }
     1367        }
     1368    }
     1369    return pQuotient;
     1370}
     1371
     1372
    6931373/** @} */
    6941374
Note: See TracChangeset for help on using the changeset viewer.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette