dead code in div_q.c?

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> paul zimmermann <Paul.Zimmermann at inria.fr> writes:
>
>> together with Raphaël Rieu-Hleft (in cc), we believe we have found some dead code in
>> mpn/generic/div_q.c around lines 173-182:
>>
>>           else if (UNLIKELY (qh != 0))
>>             {
>>               /* This happens only when the quotient is close to B^n and        
>>                  mpn_*_divappr_q returned B^n.  */
>
> I think your right. This comment is wrong in two ways: First, divappr is
> not called (directly) for this branch of code, and second, the quotient
> can be at most close to B^n/2.

I'm trying the appended patch. Besides the analysis, I've ran 

  while GMP_CHECK_RANDOMIZE=0 ./tests/mpn/t-div ; do : ; done

for at least half an hour. So I think we can drop the code. Question is,
how much of comments and/or ASSERT are useful? And should we make the
assignments

  qp[qn - 1] = qh;

and 

  tp[qn] = qh;

unconditional? As far as I see, the areas are always large enough.

But it's a unclear to me if and why it's sometimes permissible to omit
writing the top limbs? Reads of the top limbs look unconditional. 

I've tried adding 

--- a/tests/mpn/t-div.c	Wed Apr 25 07:38:14 2018 +0200
+++ b/tests/mpn/t-div.c	Wed Apr 25 22:19:17 2018 +0200
@@ -445,6 +445,7 @@ main (int argc, char **argv)
 	      alloc = itch + 1;
 	    }
 	  scratch[itch] = ran;
+	  MPN_COPY (qp, junkp, nn - dn + 1);
 	  mpn_div_q (qp, np, nn, dup, dn, scratch);
 	  ASSERT_ALWAYS (ran == scratch[itch]);
 	  ASSERT_ALWAYS (qp[-1] == qran0);  ASSERT_ALWAYS (qp[nn - dn + 1] == qran1);

to the test, to ensure that limbs aren't correct thanks to the previous
call. Tests still pass. So I'm a bit puzzled.

Regards,
/Niels

*** /tmp/extdiff.0aBNfO/gmp.765c2c27523b/mpn/generic/div_q.c	2018-04-25 21:55:51.457769871 +0200
--- /home/nisse/hack/gmp/mpn/generic/div_q.c	2018-04-25 21:18:01.516501993 +0200
*************** mpn_div_q (mp_ptr qp,
*** 171,184 ****
  	  if (cy == 0)
  	    qp[qn - 1] = qh;
! 	  else if (UNLIKELY (qh != 0))
! 	    {
! 	      /* This happens only when the quotient is close to B^n and
! 		 mpn_*_divappr_q returned B^n.  */
! 	      mp_size_t i, n;
! 	      n = new_nn - dn;
! 	      for (i = 0; i < n; i++)
! 		qp[i] = GMP_NUMB_MAX;
! 	      qh = 0;		/* currently ignored */
! 	    }
  	}
        else  /* divisor is already normalised */
--- 171,176 ----
  	  if (cy == 0)
  	    qp[qn - 1] = qh;
! 	  else
! 	    ASSERT_ALWAYS (qh == 0);
  	}
        else  /* divisor is already normalised */
*************** mpn_div_q (mp_ptr qp,
*** 263,276 ****
  	  if (cy == 0)
  	    tp[qn] = qh;
! 	  else if (UNLIKELY (qh != 0))
! 	    {
! 	      /* This happens only when the quotient is close to B^n and
! 		 mpn_*_divappr_q returned B^n.  */
! 	      mp_size_t i, n;
! 	      n = new_nn - (qn + 1);
! 	      for (i = 0; i < n; i++)
! 		tp[i] = GMP_NUMB_MAX;
! 	      qh = 0;		/* currently ignored */
! 	    }
  	}
        else  /* divisor is already normalised */
--- 255,260 ----
  	  if (cy == 0)
  	    tp[qn] = qh;
! 	  else
! 	    ASSERT_ALWAYS (qh == 0);
  	}
        else  /* divisor is already normalised */


-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.