imneme / pcg-c-basic Goto Github PK

In your Makefile the variable PREFIX is not referenced in the install subcommand. Instead the (non-existing) variable P gets referenced. With parenthesis ({}) around the variable name, the issue is solved.

Full MISRA C compliance of the C minimal library would be great, but even improving compliance is good.

Unfortunately I can't make a pull request right now, but below are some violations of the 2004 standard in pcg_basic.c. If you think this is a worthwhile endeavor, I'll try to take the time to submit a pull request.

I only have a checker for version 2004, someone else may be able to check it against the latest version (2012).

rule 2.2: only use /* ... */ comments - this would just be diligence work. I don't know if that would clash with the commenting convention in the rest of the library. Personally I would just disable that rule check, for me full compliance is not required.

rule 16.4: identical naming of parameters in declaration and definition:
header file: void pcg32_srandom(uint64_t initstate, uint64_t initseq);
implementation: void pcg32_srandom(uint64_t seed, uint64_t seq)

There are a few implicit conversions in pcg32_random_r that should be made explicit:

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    rng->state = oldstate * 6364136223846793005ULL + rng->inc;

    // illegal implicit conversion from underlying MISRA type "unsigned long long" to "unsigned int" (MISRA C 2004 rule 10.1)
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;

    // illegal implicit conversion from underlying MISRA type "unsigned long long" to "unsigned int" (MISRA C 2004 rule 10.1)
    uint32_t rot = oldstate >> 59u;

    // the unary minus operator shall not be applied to an unsigned expression (MISRA C 2004 rule 12.9)
    // illegal implicit conversion from underlying MISRA type "signed char" to "unsigned int" (MISRA C 2004 rule 10.1)
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

uint32_t pcg32_boundedrand_r(pcg32_random_t* rng, uint32_t bound)
{
    // the unary minus operator shall not be applied to an unsigned expression (MISRA C 2004 rule 12.9)
    uint32_t threshold = -bound % bound;

    for (;;) {
        uint32_t r = pcg32_random_r(rng);

        // an 'if (expression)' construct shall be followed by a compound statement. The 'else' keyword shall be followed by either a compound statement, or another 'if' statement (MISRA C 2004 rule 14.9)
        if (r >= threshold)
            return r % bound;
    }
}

And a missing 'void':

// functions with no parameters shall be declared with parameter type void (MISRA C 2004 rule 16.5)
uint32_t pcg32_random()

Since PCG is oriented towards speed, I thought I'd mention that as far as performance goes, not being able to inline the core functions like pcg32_random_r has a significant impact on speed. I'm getting around this by simply doing #include "pcg-basic.c" - yes, including the implementation file!

A usual solution is to declare the key functions static inline in the header file, then you don't have to mess around with "out of line" versions.

The more fully featured C library is able to be inlined.

return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));

Wouldn't this be equivalent (and hence be slightly faster)?

return (xorshifted >> rot) | (xorshifted << (32-rot));

    // bound, which we do by dropping output less than a threshold.
    // A naive scheme to calculate the threshold would be to do
    //
    //     uint32_t threshold = 0x100000000ull % bound;
    //
    // but 64-bit div/mod is slower than 32-bit div/mod (especially on
    // 32-bit platforms).  In essence, we do
    //
    //     uint32_t threshold = (0x100000000ull-bound) % bound;
    //
    // because this version will calculate the same modulus, but the LHS
    // value is less than 2^32.

    uint32_t threshold = -bound % bound;

you bet you use GCC and kind of worship a compiler to do right thing for you. That it naturally understands your contextual cast 0x100000000 on 64-32 x86 like arch. I agree some ops can be very slow, but in that case, why don't you use inline asm then?

so people porting: verify if assumption is working for you, didn't-nasty-bug

Is the shift of 29 here:
https://github.com/imneme/pcg-c/blob/e2383c4bfcc862b40c3d85a43c9d495ff61186cb/include/pcg_variants.h#L166
correct?

From what I can tell from the paper, it should be floor((6+64)/2) = 35?

Instead of calculate threshold using expensive mod, and return results (also with mod),
It is probably faster if the random number is masked with bound bits remaining.

bound--; // easier to do range <= bound
mask = ~0u >> (32 - (bits of bound));
uint_64 seed = pcg64(); // if fail first try, use it as seed of simple lcg
for(;;) {
uint32_t r = (seed >> 32) & mask; // r at most bound bits (assumed top bits more random)
if (r <= bound) return r; // done
seed = lcg64(seed); // original seed very random, no need for another pcg
}

Think of lcg64 not as a random generator, but a regular math function (1 to 1 mapping)
The result will still be random if the seed itself is random.

Well, it doesn't compile on Visual Studio 2013 (thanks to your ROT implementation), by ignoring Visual Studio you ignore a large group of programmers.

I hope that sticking with your own version of bit rotation algorithm was worth losing of so many potential users...

PS. Your algorithm is slow compared to original rand(), 64 bit multiplication generates external call to _allmul when compiled on 32 bits.

uint32_t pcg32_random_r(pcg32_random_t* rng);

I got an error message C4146 when I compiled this function with vs 2013.
the problem is the minus op applied to unsigned type variable rot(in the return code).

Could you change that code like ~rot + 1 instead of -rot.

thanks.

and I think this following issue is minor...
I think xorshifted variable would need a casting op. like this
uint32_t xorshifted = (uint32_t) (((oldstate >> 18u) ^ oldstate) >> 27u);

I just release Haxe language implementation using PCG minimal C Implementation here https://github.com/flashultra/hxprng . At the moment I use Apache 2.0 license , but is it possible to release source via MIT license ?

The README says that the code is written in a 'C89 style', but there's a lot of issues when trying to compile with '-std=c89 -pedantic' in gcc. Also, 64-bits integer are not guaranteed to exist in C89 nor fixed width types (i.e. uint32_t, uint64_t).

How can I port the code to a C89 only compiler?

This is not an issue!!!!!!!

I previously sent via e-mail and received no reply, even if to say there is no interest from your behalf in the following subject.
I'm sending this as an issue in the hope of seeing a reply to this subject and assume my e-mail was either not received or by e-mail filtering policies discarded or sent to a spam folder.

I have ported the PCG basic C implementation to Java 8.
I have placed the Netbeans project available in both my GitHub and Bitbucket repositories:

https://github.com/noSoulApophis/PCG-Java
https://bitbucket.org/noSoulApophis/pcg-java

If you consider appropriate I would appreciate that a link was added to the repositories from PCG website download section:
http://www.pcg-random.org/download.html

Best regards

Thanks a lot for this wonderfully simple code! I just had a question and that is, is there an equally simple way to generate a 64-bit stream?