Bug in LOGAND (from random testing)

[Christophe Rhodes]

Report from Paul Dietz

 affects sbcl
 status confirmed
 importance medium
 tag modular-arithmetic
 done

Hey folks. After a long hiatus, I've been running the random tester
again. There are some new regressions.

See the attached file for a bug in LOGAND. Load the file then
evaluate (doit) to see the behavior.

Paul Dietz

;; Illustration of bug in SBCL 1.0.55 (32 bit i686, Linux)

(defun f1 (c)
  (declare (type (integer 53 86) c))
  (declare (optimize (speed 1) (space 1) (safety 2) (debug 0)
                     (compilation-speed 3)))
  (logand (+ c 1032791128) 11007078467))

(defun f2 (c)
  (declare (optimize (speed 2) (space 3) (safety 0) (debug 0)
                     (compilation-speed 0)))
  (logand (+ c 1032791128) 11007078467))

(defun doit ()
  (let ((c 61))
    (list (f1 c)
          (f2 c))))

;; f1 is incorrect, f2 is correct
;; (doit) ==> (11005992961 268574721)

[Christophe Rhodes (csr21-cantab)]

Christophe Rhodes <email address hidden> writes:

 status fixcommitted
 done

commit 52b1041d3a14eaa4e45f6d8edfbdc0dec4292239
Author: Christophe Rhodes <email address hidden>
Date: Thu Apr 5 19:55:05 2012 +0100

    Fix bug in unsigned modular arithmetic using a signed implementation

    If we aim to be clever by implementing an unsigned modular arithmetic
    computation using signed arithmetic, we need to make sure that we
    don't accidentally contaminate the computation with any extraneous
    high bits. This means that we must be sure to cut constants to the
    appropriate width, as well as computations, so do so; this fixes
    bug #974406 from Paul Dietz. (In addition the change from cutting
    to the requested width to the implementation width fixes #903821,
    so Go Team!)

    Test cases. Minimally horrible test case for #903821; far worse
    suggestions were made on #sbcl IRC...