Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - random.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.10.0 lcov report (development 21072-998352a) Lines: 136 136 100.0 %
Date: 2017-09-26 06:25:23 Functions: 16 16 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : /********************************************************************/
      14             : /*                                                                  */
      15             : /*                      PSEUDO-RANDOM INTEGERS                      */
      16             : /*                                                                  */
      17             : /********************************************************************/
      18             : #include "pari.h"
      19             : #include "paripriv.h"
      20             : /********************************************************************/
      21             : /*                    XORGEN (Richard P. Brent)                     */
      22             : /*          http://wwwmaths.anu.edu.au/~brent/random.html           */
      23             : /*        (initial adaptation to PARI/GP by Randall Rathbun)        */
      24             : /********************************************************************/
      25             : /* Adapted from xorgens.c version 3.04, Richard P. Brent, 20060628 (GPL).
      26             :  * 32-bit or 64-bit integer random number generator with period at
      27             :  * least 2**4096-1. It is assumed that "ulong" is a 32-bit or 64-bit integer */
      28             : 
      29             : #ifdef LONG_IS_64BIT
      30             :   typedef ulong u64;
      31             :   static THREAD ulong state[64];
      32             :   #define u64state(i)      ((u64)state[(i)])
      33             :   #define u64stateset(i,x) state[(i)] = (ulong) (x);
      34             : #else
      35             :   typedef unsigned long long u64;
      36             :   static THREAD ulong state[128];
      37             :   #define u64state(i)      _32to64(state[2*(i)],state[2*(i)+1])
      38             :   #define u64stateset(i,x) _64to32(x,state+2*(i),state+2*(i)+1)
      39             : static u64
      40    16192019 : _32to64(ulong a, ulong b) { u64 v = a; return (v<<32)|b; }
      41             : static void
      42     8469342 : _64to32(u64 v, ulong *a, ulong *b) { *a = v>>32; *b = v&0xFFFFFFFF; }
      43             : #endif
      44             : static THREAD u64 xorgen_w;
      45             : static THREAD int xorgen_i;
      46             : /* weyl = odd approximation to 2^64*(sqrt(5)-1)/2. */
      47             : static const u64 weyl = (((u64)0x61c88646U)<<32)|((u64)0x80b583ebU);
      48             : 
      49             : static u64
      50    60417618 : block(void)
      51             : {
      52    60417618 :   const int r = 64;
      53    60417618 :   const int a = 33, b = 26, c = 27, d = 29, s = 53;
      54             :   u64 t, v, w;
      55    60417618 :   xorgen_i = (xorgen_i+1)&(r-1);
      56    60417618 :   t = u64state(xorgen_i);
      57    60417618 :   v = u64state((xorgen_i+(r-s))&(r-1));   /* index is (i-s) mod r */
      58    60417618 :   t ^= t<<a; t ^= t>>b;                   /* (I + L^a)(I + R^b) */
      59    60417618 :   v ^= v<<c; v ^= v>>d;                   /* (I + L^c)(I + R^d) */
      60    60417618 :   w = t^v;
      61    60417618 :   u64stateset(xorgen_i, w);               /* update circular array */
      62    60417618 :   return w;
      63             : }
      64             : 
      65             : /* v > 0 */
      66             : static void
      67      828869 : init_xor4096i(u64 v)
      68             : {
      69      828869 :   const int r = 64;
      70             :   int k;
      71             : 
      72     6774328 :   for (k = r; k > 0; k--) {/* avoid correlations for close seeds */
      73     5945459 :     v ^= v<<10; v ^= v>>15; /* recurrence has period 2**64-1 */
      74     5945459 :     v ^= v<<4;  v ^= v>>13;
      75             :   }
      76     6660558 :   for (xorgen_w = v, k = 0; k < r; k++) { /* initialise circular array */
      77     5831689 :     v ^= v<<10; v ^= v>>15;
      78     5831689 :     v ^= v<<4;  v ^= v>>13;
      79     5831689 :     u64stateset(k, v + (xorgen_w+=weyl));
      80             :   }
      81             :   /* discard first 4*r results */
      82      828869 :   for (xorgen_i = r-1, k = 4*r; k > 0; k--) (void)block();
      83       96963 : }
      84             : 
      85       64801 : void pari_init_rand(void) { init_xor4096i(1UL); }
      86             : 
      87             : static u64
      88    42094350 : rand64(void)
      89             : {
      90    42094350 :   u64 v = block();
      91    42094368 :   xorgen_w += weyl; /* update Weyl generator */
      92    42094368 :   return v + (xorgen_w ^ (xorgen_w>>27));
      93             : }
      94             : 
      95             : /* One random number uniformly distributed in [0..2**BIL) is returned, where
      96             :  * BIL = 8*sizeof(ulong) = 32 or 64. */
      97             : ulong
      98          20 : pari_rand(void) { return rand64(); }
      99             : 
     100             : void
     101       31201 : setrand(GEN x)
     102             : {
     103       31201 :   const int r2 = numberof(state);
     104             :   long i, lx;
     105             :   u64 v;
     106             :   GEN xp;
     107       31201 :   if (typ(x)!=t_INT) pari_err_TYPE("setrand",x);
     108       31201 :   if (signe(x) <= 0) pari_err_DOMAIN("setrand","n", "<=", gen_0, x);
     109       31194 :   lx = lgefint(x);
     110       57924 :   if (lx == 3) { v = x[2]; init_xor4096i(v); return; }
     111             : #ifndef LONG_IS_64BIT
     112          14 :   if (lx == 4)
     113             :   {
     114           1 :     v = _32to64(*int_W(x,1),*int_W(x,0));
     115           1 :     init_xor4096i(v); return;
     116             :   }
     117             : #endif
     118          79 :   if (lx != 2 + r2+2+(r2==128))
     119           7 :     pari_err_DOMAIN("setrand", "n", "!=", strtoGENstr("getrand()"), x);
     120          72 :   xp = int_LSW(x);
     121          72 :   for (i = 0; i < r2; i++) { state[i] = *xp; xp = int_nextW(xp); }
     122             : #ifdef LONG_IS_64BIT
     123          60 :   xorgen_w = *xp; xp = int_nextW(xp);
     124             : #else
     125          12 :   xorgen_w = _32to64(*xp, *int_nextW(xp)); xp = int_nextW(int_nextW(xp));
     126             : #endif
     127          72 :   xorgen_i =  (*xp) & 63;
     128             : }
     129             : 
     130             : GEN
     131      338386 : getrand(void)
     132             : {
     133      338386 :   const int r2 = numberof(state);
     134             :   GEN x;
     135             :   ulong *xp;
     136             :   long i;
     137      338386 :   if (xorgen_i < 0) init_xor4096i(1UL);
     138             : 
     139      338386 :   x = cgetipos(2+r2+2+(r2==128)); xp = (ulong *) int_LSW(x);
     140      338386 :   for (i = 0; i < r2; i++) { *xp = state[i]; xp = int_nextW(xp); }
     141             : #ifdef LONG_IS_64BIT
     142      289854 :   *xp = xorgen_w; xp = int_nextW(xp);
     143             : #else
     144       48532 :   _64to32(xorgen_w, xp, int_nextW(xp)); xp = int_nextW(int_nextW(xp));
     145             : #endif
     146      338386 :   *xp = xorgen_i? xorgen_i: 64; return x;
     147             : }
     148             : 
     149             : /* assume 0 <= k <= BITS_IN_LONG. Return uniform random 0 <= x < (1<<k) */
     150             : long
     151     9414297 : random_bits(long k) { return rand64() >> (64-k); }
     152             : 
     153             : /********************************************************************/
     154             : /*                                                                  */
     155             : /*                         GENERIC ROUTINES                         */
     156             : /*                                                                  */
     157             : /********************************************************************/
     158             : 
     159             : /* assume n > 0 */
     160             : ulong
     161    22958278 : random_Fl(ulong n)
     162             : {
     163             :   ulong d;
     164             :   int shift;
     165             : #ifdef LONG_IS_64BIT
     166    19067554 :   int SHIFT = 0;
     167             : #else
     168     3890724 :   int SHIFT = 32;
     169             : #endif
     170             : 
     171    22958278 :   if (n == 1) return 0;
     172             : 
     173    22957795 :   shift = bfffo(n); /* 2^(BIL-shift) > n >= 2^(BIL-shift-1)*/
     174             :   /* if N a power of 2, increment shift. No reject */
     175    22957795 :   if ((n << shift) == HIGHBIT) return rand64() >> (SHIFT+shift+1);
     176             :   for (;;) {
     177    31283260 :     d = rand64() >> (SHIFT+shift); /* d < 2^(64-shift) uniformly distributed */
     178             :     /* reject strategy: proba success = n 2^(shift-64), in [1/2, 1[ */
     179    31283323 :     if (d < n) return d;
     180     9040079 :   }
     181             : }
     182             : 
     183             : /* assume N > 0, see random_Fl() for algorithm. Make sure that 32-bit and
     184             :  * 64-bit architectures produce the same integers (consuming random bits
     185             :  * by packets of 64) */
     186             : GEN
     187     3242228 : randomi(GEN N)
     188             : {
     189     3242228 :   long lx = lgefint(N);
     190             :   GEN x, d;
     191             :   int shift;
     192             : 
     193     3242228 :   if (lx == 3) return utoi( random_Fl(N[2]) );
     194             : 
     195       30355 :   shift = bfffo(*int_MSW(N));
     196             :   /* if N a power of 2, increment shift */
     197       30355 :   if (Z_ispow2(N) && ++shift == BITS_IN_LONG) { shift = 0; lx--; }
     198       30355 :   x = cgetipos(lx);
     199             :   for (;;) {
     200       56615 :     GEN y, MSW = int_MSW(x), STOP = MSW;
     201             : #ifdef LONG_IS_64BIT
     202       42725 :     for (d = int_LSW(x); d != STOP; d = int_nextW(d)) *d = rand64();
     203       42725 :     *d = rand64() >> shift;
     204             : #else
     205       13890 :     if (!odd(lx)) STOP = int_precW(STOP);
     206             :     /* STOP points to where MSW would in 64-bit */
     207       27079 :     for (d = int_LSW(x); d != STOP; d = int_nextW(d))
     208             :     {
     209       13189 :       ulong a, b; _64to32(rand64(), &a,&b);
     210       13189 :       *d = b; d = int_nextW(d);
     211       13189 :       *d = a;
     212             :     }
     213             :     {
     214       13890 :       ulong a, b; _64to32(rand64() >> shift, &a,&b);
     215       13890 :       if (d == MSW) /* 32 bits needed */
     216        5432 :         *d = a;
     217             :       else
     218             :       { /* 64 bits needed */
     219        8458 :         *d = b; d = int_nextW(d);
     220        8458 :         *d = a;
     221             :       }
     222             :     }
     223             : #endif
     224       56615 :     y = int_normalize(x, 0);
     225       56615 :     if (abscmpii(y, N) < 0) return y;
     226       26260 :   }
     227             : }
     228             : 
     229             : GEN
     230      533537 : random_F2x(long d, long vs)
     231             : {
     232      533537 :   ulong db, dl = dvmduBIL(d,&db);
     233      533537 :   long i, l = 2 + dl + !!db;
     234      533537 :   GEN y = cgetg(l,t_VECSMALL); y[1] = vs;
     235             : #ifdef LONG_IS_64BIT
     236      457354 :   for (i=2; i<l; i++) uel(y,i) = rand64();
     237             : #else
     238       76336 :   for (i=2; i<l-1; i+=2)
     239             :   {
     240         153 :     u64 v = rand64();
     241         153 :     uel(y,i)   = (ulong) v;
     242         153 :     uel(y,i+1) = (ulong) (v>>32);
     243             :   }
     244       76183 :   if (i<l) uel(y,i) = (ulong) rand64();
     245             : #endif
     246      533537 :   if (db) uel(y,l-1) &= ((1UL<<db)-1UL);
     247      533537 :   return F2x_renormalize(y,l);
     248             : }
     249             : 
     250             : GEN
     251           7 : randomr(long prec)
     252             : {
     253             :   pari_sp av;
     254             :   long b;
     255             :   GEN x, y;
     256           7 :   if (prec <= 2) return real_0_bit(0);
     257           7 :   x = cgetr(prec); av = avma;
     258           7 :   b = prec2nbits(prec);
     259           7 :   y = randomi(int2n(b));
     260           7 :   if (!signe(y)) return real_0_bit(b);
     261           7 :   affir(y, x); shiftr_inplace(x, - b);
     262           7 :   avma = av; return x;
     263             : }
     264             : 
     265             : static GEN
     266          77 : polrandom(GEN N) /* assume N!=0 */
     267             : {
     268          77 :   long i, d = lg(N);
     269          77 :   GEN z = leading_coeff(N);
     270          77 :   GEN y = cgetg(d,t_POL);
     271          77 :   y[1] = evalsigne(1) | evalvarn(varn(N));
     272          77 :   for (i=2; i<d; i++) gel(y,i) = genrand(z);
     273          77 :   return normalizepol_lg(y,d);
     274             : }
     275             : 
     276             : GEN
     277     3290714 : genrand(GEN N)
     278             : {
     279             :   GEN z;
     280     3290714 :   if (!N) return utoi( random_bits(31) );
     281     3290035 :   switch(typ(N))
     282             :   {
     283             :     case t_INT:
     284     2183629 :       if (signe(N)<=0) pari_err_DOMAIN("random","N","<=",gen_0,gen_0);
     285     2183622 :       return randomi(N);
     286             :     case t_REAL:
     287           7 :       return randomr(realprec(N));
     288             :     case t_INTMOD:
     289      566209 :       z = cgetg(3, t_INTMOD);
     290      566209 :       gel(z,1) = icopy(gel(N,1));
     291      566209 :       gel(z,2) = randomi(gel(N,1)); return z;
     292             :     case t_FFELT:
     293      138474 :       return ffrandom(N);
     294             :     case t_POL:
     295          77 :       if (signe(N)==0) return pol_0(varn(N));
     296          77 :       return polrandom(N);
     297             :     case t_VEC:
     298      401632 :       if (lg(N) == 3)
     299             :       {
     300      157570 :         pari_sp av = avma;
     301      157570 :         GEN a = gel(N,1), b = gel(N,2), d;
     302      157570 :         if (typ(a) != t_INT) a = gceil(a);
     303      157570 :         if (typ(b) != t_INT) b = gfloor(b);
     304      157570 :         if (typ(a) != t_INT || typ(b) != t_INT) pari_err_TYPE("random", N);
     305      157570 :         d = subii(b,a);
     306      157570 :         if (signe(d) < 0) pari_err_TYPE("random([a,b]) (a > b)", N);
     307      157570 :         return gerepileuptoint(av, addii(a, randomi(addiu(d,1))));
     308             :       }
     309      244062 :       return ellrandom(N);
     310             :     default:
     311           7 :       pari_err_TYPE("genrand",N);
     312             :       return NULL;/*LCOV_EXCL_LINE*/
     313             :   }
     314             : }

Generated by: LCOV version 1.11