Uninitialized memory bug found in /mpn/generic/mod_1_1.c

[Torbjörn Granlund]

Brett Kuntz <kuntz at shaw.ca> writes:

  Take a look at function mpn_mod_1() in /mpn/generic/ mod_1.c on lines 248 - 250

  mp_limb_t pre[4];
  mpn_mod_1_1p_cps (pre, b);

  mp_limb_t pre[4] is not initialized

It does not exist, only pre[0] through pre[3] does.

  and the mpn_mod_1_1p_cps() function
  never writes to pre[2]. So if we change that to mp_limb_t pre[4] = { -1,
  -1, -1, -1 }; as a test we'll quickly see that inside mpn_mod_1_1p_cps()
  the value cps[2] (pre[2]) is never written to and if we print out pre[4]
  after running it we'll get output like: 0x21CFE6CFC938B36BU,
  0x0000000000000000U, 0xFFFFFFFFFFFFFFFFU, 0x9581CA13918612E1U (pre[2] is
  -1)

  /mpn/generic/mod_1_1.c lines 260-266:

    if (LIKELY (cnt != 0))
      {
        mp_limb_t B1modb = -b;
        B1modb *= ((bi >> (GMP_LIMB_BITS-cnt)) | (CNST_LIMB(1) << cnt));
        ASSERT (B1modb <= b);		/* NB: not fully reduced mod b */
        cps[2] = B1modb >> cnt;
      }

  cnt will ALWAYS equal 0 since there will be NO leading 0's when this is
  called since /mpn/generic/mod_1_1.c checks for the high bit being SET
  before calling.. which means this function only ever gets called with NO
  leading zeros!!!

Why are you so worked up?

The logic seems perfectly fine.

  ALSO there are unexplained differences between MOD_1_1P_METHOD 1 and
  MOD_1_1P_METHOD 2 when it comes to the function mpn_mod_1_1p_cps(). In
  one of them pre[4] is always set and in the other (method 2) pre[2] is
  skipped! Why are these two functions different? It looks like their job
  is to calculate the inverses for the following mod functions so one
  would expect them to be the same.

There are lots of "unexplained" things in the GMP internal functions.
But trust me, the GMP developers understand the sources.

  ALSO the x64 assembly versions of these codes also does not always set
  all 4 values of pre[4] and this has lead to incorrect results when using
  the exported function mpn_mod_1().

You hypothesise things here.  And you're wrong.

I benevolent reading of your claims here is that things will be bad if
you use one variant of the internal _cps function with another variant
of the corresponding internal mod function.  If that's what you're
trying to say, then you're right.  GMP is not edit proof, local user
edits might break it in all sorts of ways,

But if you actually claim that an unedited GMP has a bug here, please
construct a test case which uses documented interfaces, and which
demonstrates the claimed bug.

  I do not understand these functions enough

Shouting from the top of your lungs about a bug which is just the result
of reading the sources, without allowing yourself time to understand the
logic fully, is somewhat unfair.

-- 
Torbjörn
Please encrypt, key id 0xC8601622