random.cpp

这是整套横扫千军3D版游戏的源码

        return ret;
    }
};

// for 32-bits
template<> struct RandomIntRestrictor<32> {
    typedef SizedUnsignedInteger<32>::Type Type;

    static inline Type getRestrictedRandomInt(Type n, RandomState& state)
    {
        // First propagate leading 1 to all other bits
        Type mask = n;
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;
        mask |= mask >> 8;
        mask |= mask >> 16;

        // Draw only that number of bits, until a number is in the desired range [0,n]
        // Worse case is number of loops proba decreasing in 1/2^nloops
        Type ret;
        do {
            ret = Accessor<32>::getRandomInt(state) & mask;
        } while( ret > n );

        return ret;
    }
};

// for 64-bits
template<> struct RandomIntRestrictor<64> {
    typedef SizedUnsignedInteger<64>::Type Type;

    static inline Type getRestrictedRandomInt(Type n, RandomState& state)
    {
        // First propagate leading 1 to all other bits
        Type mask = n;
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;
        mask |= mask >> 8;
        mask |= mask >> 16;
        mask |= mask >> 32;

        // Draw only that number of bits, until a number is in the desired range [0,n]
        // Worse case is number of loops proba descreasing in 1/2^nloops
        Type ret;
        do {
            ret = Accessor<64>::getRandomInt(state) & mask;
        } while( ret > n );

        return ret;
    }
};


// Now implement the Random functions

/* range checker.
   But why should clean caller code be slowed down by checks?
   => caller code should provide good arguments, or be fixed

/// Common function that will be used for all random integer types
template<typename an_int_type, int num_bounds, int min_excluded> struct RandomSwitcher {
    // random selection
    static inline an_int_type getMinMaxRandom(an_int_type min, an_int_type max, RandomState& state) {
        // Works in both signed and unsigned arithmetic
        if (max<=min) {
            if (max==min) return min; // easy
            return RandomSwitcher<an_int_type,num_bounds,(num_bounds==1)?(!min_excluded):min_excluded>::getMinMaxRandom(max, min, state);
        }

        // now max > min
        an_int_type range = max - min + 1;

        // overflow, asking the whole range of integers
        if (range==0) return getRandomBits<a_type>(sizeof(an_int_type)*STREFLOP_INTEGER_TYPES_CHAR_BITS, state);

        // range >= 2, num_bounds <= 2, OK to subtract 2 - num_bounds
        range -= 2-num_bounds;
        // ask the impossible, like RandomEE(3,4)
        if (range == 0) return min;

        // This gives the number of possible integers to choose from (at least 1)
        // Now generate the number
        an_int_type ret = min + min_excluded + static_cast<an_int_type>(RandomIntRestrictor< sizeof(an_int_type)*STREFLOP_INTEGER_TYPES_CHAR_BITS >::getRestrictedRandomInt(range,state));
        return ret;
    }
};
*/

#define SPECIALIZE_RANDOM_FOR_TYPE(a_type,use_signed) \
template<> a_type Random<a_type>(RandomState& state) { \
    return Accessor<sizeof(a_type)*STREFLOP_INTEGER_TYPES_CHAR_BITS>::getRandomInt(state); \
} \
template<> a_type Random<true, true, a_type>(a_type min, a_type max, RandomState& state) { \
    return static_cast<a_type>(RandomIntRestrictor< sizeof(a_type)*STREFLOP_INTEGER_TYPES_CHAR_BITS >::getRestrictedRandomInt(max-min,state)) + min; \
} \
template<> a_type Random<true, false, a_type>(a_type min, a_type max, RandomState& state) { \
    return static_cast<a_type>(RandomIntRestrictor< sizeof(a_type)*STREFLOP_INTEGER_TYPES_CHAR_BITS >::getRestrictedRandomInt(max-min-1,state)) + min; \
} \
template<> a_type Random<false, true, a_type>(a_type min, a_type max, RandomState& state) { \
    return max - static_cast<a_type>(RandomIntRestrictor< sizeof(a_type)*STREFLOP_INTEGER_TYPES_CHAR_BITS >::getRestrictedRandomInt(max-min-1,state)); \
} \
template<> a_type Random<false, false, a_type>(a_type min, a_type max, RandomState& state) { \
    return static_cast<a_type>(RandomIntRestrictor< sizeof(a_type)*STREFLOP_INTEGER_TYPES_CHAR_BITS >::getRestrictedRandomInt(max-min-2,state)) + min + 1; \
}
SPECIALIZE_RANDOM_FOR_TYPE(char,true)
SPECIALIZE_RANDOM_FOR_TYPE(unsigned char,false)
SPECIALIZE_RANDOM_FOR_TYPE(short,true)
SPECIALIZE_RANDOM_FOR_TYPE(unsigned short,false)
SPECIALIZE_RANDOM_FOR_TYPE(int,true)
SPECIALIZE_RANDOM_FOR_TYPE(unsigned int,false)
SPECIALIZE_RANDOM_FOR_TYPE(long,true)
SPECIALIZE_RANDOM_FOR_TYPE(unsigned long,false)
SPECIALIZE_RANDOM_FOR_TYPE(long long,true)
SPECIALIZE_RANDOM_FOR_TYPE(unsigned long long,false)


// Random for float types is even more dependent on size


/*

EXPERIMENTAL:

    The ULP_Random functions use a uniform distribution in the ULP space.
    This means, each possibly representable float is given exactly the same weight for the
    random choice. This is an exponential scale where there are as many numbers between
    successive powers of 2 (i.e as many numbers between 1 and 2 as there are between 1024 and 2048).
    This effectively corresponds to the maximum machine precision, but it is unfortunately
    not what one means by "uniform" in the traditional sense of the term (it is uniform in terms
    of bit patterns, so for the computer!)

    Algorithm: treat floats as binary pattern, thanks to IEEE754 ordered property
    => this gives a "range" like max-min for the integers, where the unit is ulp
    => this gives the maximum precision for floats, because a random number is chosen between exactly how many
    numbers can be represented with that float format in that range


#define SPECIALIZE_RANDOM_FOR_SIMPLE_ULP(X,Y) \
Simple ULP_Random ## X ## Y(Simple min, Simple max) { \
 \
    // Convert to signed integer for quick test of bit sign \
    SizedInteger<32>::Type imin = *reinterpret_cast<SizedUnsignedInteger<32>::Type*>(&min); \
    SizedInteger<32>::Type imax = *reinterpret_cast<SizedUnsignedInteger<32>::Type*>(&max); \
 \
    // Infinity is a perfectly fine number, with a bit pattern contiguous to the min and max floats \
    // This makes sense if excluding bounds: RandomEE(-inf,+inf) returns a possible float at random \
 \
    // Rule out NaNs \
    if (imin&0x7fffffff > 0x7f800000) return SimpleNaN; \
    if (imax&0x7fffffff > 0x7f800000) return SimpleNaN; \
 \
    // Convert to 2-complement representation \
    if (imin<0) imin = 0x80000000 - imin; \
    if (imax<0) imax = 0x80000000 - imax; \
 \
    // Now magically get an integer at random in that range \
    // This gives EXACTLY one choice per representable float \
    // It is non-uniform in the float space, but uniform in the bit-pattern space \
    SizedInteger<32>::Type iret = Random ## X ## Y(imin,imax); \
 \
    // convert back to 2-complement to IEEE754 \
    if (iret<0) iret = 0x80000000 - iret; \
 \
    // cast to float \
    return *reinterpret_cast<Simple*>(&iret); \
}
SPECIALIZE_RANDOM_FOR_SIMPLE_ULP(E,I)
SPECIALIZE_RANDOM_FOR_SIMPLE_ULP(E,E)
SPECIALIZE_RANDOM_FOR_SIMPLE_ULP(I,E)
SPECIALIZE_RANDOM_FOR_SIMPLE_ULP(I,I)
*/


// Return a random float
template<> Simple Random<Simple>(RandomState& state) {
    // Generate bits
    SizedUnsignedInteger<32>::Type ret = Accessor<32>::getRandomInt(state);

    // Discard NaNs and Inf, ignore sign
    while ((ret & 0x7fffffff) >= 0x7f800000) ret = Accessor<32>::getRandomInt(state);

    // cast to float
    return *reinterpret_cast<Simple*>(&ret);
}

// Random in 1..2 - ideal IE case
template<> Simple Random12<true,false,Simple>(RandomState& state) {

    // Get uniform number between 1 and 2 at max precision

    // Generate bits
    SizedUnsignedInteger<32>::Type r12 = Accessor<32>::getRandomInt(state);

    // Simple precision keeps only 23 bits
    r12 &= 0x007FFFFF;

    // Insert exponent so it's in the [1.0-2.0) range
    r12 |= 0x3F800000;

    return *reinterpret_cast<Simple*>(&r12);
}

// Random in 1..2 - near ideal EI case
template<> Simple Random12<false,true,Simple>(RandomState& state) {

    // Get uniform number between 1 and 2 at max precision

    // Generate bits
    SizedUnsignedInteger<32>::Type r12 = Accessor<32>::getRandomInt(state);

    // Simple precision keeps only 23 bits
    r12 &= 0x007FFFFF;

    // Insert exponent so it's in the [1.0-2.0) range
    r12 |= 0x3F800000;

    // Bitwise add 1 so it's in the (1.0-2.0] range
    r12 += 1;

    return *reinterpret_cast<Simple*>(&r12);
}

// Random in 1..2 - need to include both bounds
template<> Simple Random12<true,true,Simple>(RandomState& state) {

    // Get uniform number between 1 and 2 at max precision

    // Generate bits
    SizedUnsignedInteger<32>::Type r12 = Accessor<32>::getRandomInt(state);

    // Keep 2^23 + 1 possibilities, discard others
    // Note: %= operator is nicely converted into reciprocal multiply and shift by compiler
    r12 %= 0x00800001;
    // Choose to avoid % operator by having about 1/2 chance of rejection. Not faster.
//    while ((r12 &= 0x00FFFFFF) > 0x00800000) r12 = Accessor<32>::getRandomInt(state);

/* could also use multiply by reciprocal and then find remainder. For div by 0x00800001:
; dividend: register other than EAX or memory location
MOV    EAX, 0FFFFFE01h
MUL    dividend
SHR    EDX, 23
; quotient now in EDX
*/

    // bitwise add exponent so it's in the [1.0-2.0] range
    r12 += 0x3F800000;

    return *reinterpret_cast<Simple*>(&r12);
}

// Random in 1..2 - need to exclude both bounds
template<> Simple Random12<false,false,Simple>(RandomState& state) {

    // Get uniform number between 1 and 2 at max precision

    // Generate bits
    SizedUnsignedInteger<32>::Type r12 = Accessor<32>::getRandomInt(state);

    // Keep 2^23 - 1 possibilities
    //r12 %= 0x007FFFFF;
    // Choose to avoid % operator by having very small chance of rejection
    // Could we find a branchless version for % by 2^N-1 ?
    while ((r12 &= 0x007FFFFF) == 0x007FFFFF) r12 = Accessor<32>::getRandomInt(state);

    // bitwise add exponent so it's in the (1.0-2.0) range
    r12 += 0x3F800001;

    return *reinterpret_cast<Simple*>(&r12);
}


///////// Double versions  ///////////

// Return a random float
template<> Double Random<Double>(RandomState& state) {
    // Generate bits
    SizedUnsignedInteger<64>::Type ret = Accessor<64>::getRandomInt(state);

    // Discard NaNs and Inf, ignore sign
    while ((ret & 0x7fffffffffffffffULL) >= 0x7ff0000000000000ULL) ret = Accessor<64>::getRandomInt(state);

    // cast to Double
    return *reinterpret_cast<Double*>(&ret);
}


// Random in a 1..2 - ideal IE case
template<> Double Random12<true,false,Double>(RandomState& state) {

    // Get uniform number between 1 and 2 at max precision

    // Generate bits
    SizedUnsignedInteger<64>::Type r12 = Accessor<64>::getRandomInt(state);

    // Double precision keeps only 52 bits
    r12 &= 0x000FFFFFFFFFFFFFULL;

    // Insert exponent so it's in the [1.0-2.0) range
    r12 |= 0x3FF0000000000000ULL;

    // scale from 1-2 interval to the desired interval
    return *reinterpret_cast<Double*>(&r12);
}

// Random in a 1..2 - near ideal EI case
template<> Double Random12<false,true,Double>(RandomState& state) {

    // Get uniform number between 1 and 2 at max precision

    // Generate bits
    SizedUnsignedInteger<64>::Type r12 = Accessor<64>::getRandomInt(state);

    // Double precision keeps only 52 bits
    r12 &= 0x000FFFFFFFFFFFFFULL;

    // Insert exponent so it's in the [1.0-2.0) range
    r12 |= 0x3FF0000000000000ULL;

    // Bitwise add 1 so it's in the (1.0-2.0] range
    r12 += 1;

    // scale from 1-2 interval to the desired interval
    return *reinterpret_cast<Double*>(&r12);
}

// Random in a 1..2 - need to include both bounds