bug#43764: Calc shift right broken

bug#43764: Calc shift right broken

[Vincent Belaïche]

[-- Attachment #1: Type: text/plain, Size: 542 bytes --]

Not sure whether this has to do with the other one.
I am on another machine, it is GNU Emacs 26.3 (build 2, x86_64-pc-linux-gnu, GTK+ Version 3.24.20) of 2020-05-17, modified by Debian

Anyway, I do this:

2 RET
;; display in hexa
d 6 RET
;; Raise to the power 32
32 ^
;; Shitf right by 30
C-u 32 b r
;; I get 0, whereas I expected 4

I have the impression that the old bigpos bigneg lisp based big intergers have been replaced by C bigintegers, and this is the root of all these regression.
Well, just a speculation.
  V.


[-- Attachment #2: Type: text/html, Size: 2745 bytes --]

bug#43764: Calc shift right broken

[Mattias Engdegård]

This actually works as designed; see the Calc manual. In short, Calc maintains a 'word size' and clips all results of binary operations to that size. Apparently, Calc clips the argument for good measure before even performing the right-shift. The default word size is 32 bits; you can change it using "b w".

Whether this is the best design can be debated, of course. Tell us if you are happy with this explanation, or if you think it should work in a different way. (Can't promise any major changes, though.)

A very modest reform would be to set the default word size to 64 bits, to keep up with the times.

bug#43764: Calc shift right broken

[Lars Ingebrigtsen]

Mattias Engdegård <mattiase@acm.org> writes:

> A very modest reform would be to set the default word size to 64 bits,
> to keep up with the times.

That sounds like a welcome change...  or is it possible that somebody is
using calc to do 32-bit math and would be surprised by this?

But if we're changing the number of default bits, perhaps it would make
more sense to default to having no bit width restrictions?  Or would
that entail major Calc surgery?  

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#43764: Calc shift right broken

[Mattias Engdegård]

5 okt. 2020 kl. 10.12 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> That sounds like a welcome change...  or is it possible that somebody is
> using calc to do 32-bit math and would be surprised by this?

Maybe but not in any very harmful way. I'm sure they would cope.

> But if we're changing the number of default bits, perhaps it would make
> more sense to default to having no bit width restrictions?  Or would
> that entail major Calc surgery?  

Any changes to Calc, however minor, are fraught with danger and excitement!

Fun as it may be, better not making changes speculatively though.
(On the other hand it could be that everyone have been bothered about this for years. I have no way of knowing.)

bug#43764: Calc shift right broken

[Lars Ingebrigtsen]

Mattias Engdegård <mattiase@acm.org> writes:

>> But if we're changing the number of default bits, perhaps it would make
>> more sense to default to having no bit width restrictions?  Or would
>> that entail major Calc surgery?  
>
> Any changes to Calc, however minor, are fraught with danger and excitement!

:-)

> Fun as it may be, better not making changes speculatively though.
> (On the other hand it could be that everyone have been bothered about
> this for years. I have no way of knowing.)

In olden times, I would guess most people thought that it just had to be
this way.  But now that the rest of Emacs has bignums, it's perhaps more
surprising that Calc behaves this way when doing shifts.

On the other hand, I don't know what people use Calc for here.  If
people are going "I wonder what would happen on a 32-bit machine if I
were to do this shift operation", then it'd be something else...

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#43764: Calc shift right broken

[Mattias Engdegård]

6 okt. 2020 kl. 03.28 skrev Lars Ingebrigtsen <larsi@gnus.org>:

> On the other hand, I don't know what people use Calc for here. If
> people are going "I wonder what would happen on a 32-bit machine if I
> were to do this shift operation", then it'd be something else...

Yes, we should be defending the users of Emacs, not Emacs itself.

What about a narrower change: clip the value after shifting right instead of before?

Vincent, would you be happy with the patch below, or do you think a more fundamental change is required?

--- a/lisp/calc/calc-bin.el
+++ b/lisp/calc/calc-bin.el
@@ -375,7 +375,7 @@ calcFunc-lsh
                 (Math-lessp w n))
             0)
            ((< n 0)
-            (math-quotient (math-clip a w) (math-power-of-2 (- n))))
+             (math-clip (math-quotient a (math-power-of-2 (- n))) w))
            (t
             (math-clip (math-mul a (math-power-of-2 n)) w))))))
 

bug#43764: Calc shift right broken

[Mattias Engdegård]

> What about a narrower change: clip the value after shifting right instead of before?

On the other hand it would introduce an inconsistency with arithmetic right shift which ignores bits above the word size.
Thus I will do nothing at all unless Vincent or anyone else speaks up.

However, this bug has already been a success since inspecting the code revealed a bug in the arithmetic right shift that has now been fixed, and there is now a fairly comprehensive test for all binary shift and rotate operations which should make future changes a lot safer and easier.

bug#43764: Calc shift right broken

[Vincent Belaïche]

[-- Attachment #1: Type: text/plain, Size: 2366 bytes --]

Hello,
Sorry for the late feedback.

I think that it is good to have the possibility to set a bit width, just because otherwise the two complement signing display ('O d 6') would be broken, same for the leading zeros ('d z').


I agree that it is unwise to change anything in the way that it works. Changes should be backward compatible only, unless there is a very good reason for the change.

What could be improved would be to add some more functions, like (some ideas) :

  *   set bit width 0 would remove the automatic clipping meaning infinite width.
  *   have the H prefix (Hyperbolic) not only for 'b l' but also for the other shifts operation, so that the width can be set on an operation by operation basis with the prefix argument.
  *   Maybe there could be some display mode in which when integers are wider that the bit width this is displayed somehow, e.g. the pipe in 16#12|34 would appear with a bit width of 8, 16#123|4 for a bit width of 7. Just to warn the user « beware the clip ».

   Vincent.
________________________________
De : Lars Ingebrigtsen <larsi@gnus.org>
Envoyé : mardi 6 octobre 2020 03:28
À : Mattias Engdegård <mattiase@acm.org>
Cc : Vincent Belaïche <vincent.b.1@hotmail.fr>; 43764@debbugs.gnu.org <43764@debbugs.gnu.org>
Objet : Re: bug#43764: Calc shift right broken

Mattias Engdegård <mattiase@acm.org> writes:

>> But if we're changing the number of default bits, perhaps it would make
>> more sense to default to having no bit width restrictions?  Or would
>> that entail major Calc surgery?
>
> Any changes to Calc, however minor, are fraught with danger and excitement!

:-)

> Fun as it may be, better not making changes speculatively though.
> (On the other hand it could be that everyone have been bothered about
> this for years. I have no way of knowing.)

In olden times, I would guess most people thought that it just had to be
this way.  But now that the rest of Emacs has bignums, it's perhaps more
surprising that Calc behaves this way when doing shifts.

On the other hand, I don't know what people use Calc for here.  If
people are going "I wonder what would happen on a 32-bit machine if I
were to do this shift operation", then it'd be something else...

--
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

[-- Attachment #2: Type: text/html, Size: 4591 bytes --]

bug#43764: Calc shift right broken

[Mattias Engdegård]

9 okt. 2020 kl. 17.34 skrev Vincent Belaïche <vincent.b.1@hotmail.fr>:

> What could be improved would be to add some more functions, like (some ideas) :
> 	• set bit width 0 would remove the automatic clipping meaning infinite width.

This seems both useful and straightforward to implement and understand. I've attached a patch (lacking documentation but otherwise complete) -- is it what you had in mind?

> 	• have the H prefix (Hyperbolic) not only for 'b l' but also for the other shifts operation, so that the width can be set on an operation by operation basis with the prefix argument.

Your wish has been granted! It already works that way, it's just not very well documented. Try it.

> 	• Maybe there could be some display mode in which when integers are wider that the bit width this is displayed somehow, e.g. the pipe in 16#12|34 would appear with a bit width of 8, 16#123|4 for a bit width of 7. Just to warn the user « beware the clip ».

It's not a bad suggestion, but since this is Calc, nothing is very simple. Let's give it some thought.

bug#43764: Calc shift right broken

[Mattias Engdegård]

[-- Attachment #1: Type: text/plain, Size: 278 bytes --]

10 okt. 2020 kl. 18.24 skrev Mattias Engdegård <mattiase@acm.org>:

> This seems both useful and straightforward to implement and understand. I've attached a patch (lacking documentation but otherwise complete) -- is it what you had in mind?

Sorry, here is that patch.


[-- Attachment #2: 0001-Calc-allow-infinite-binary-word-size-bug.patch --]
[-- Type: application/octet-stream, Size: 8138 bytes --]

From ec880e30d82e13ff5c6cb36f7736280be45ee9e0 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= <mattiase@acm.org>
Date: Sat, 10 Oct 2020 18:02:49 +0200
Subject: [PATCH] Calc: allow infinite binary word size (bug#
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Setting the word size ("b w") to 0 removes the word size clipping for
all bit operations (effectively as if a word size of -∞ had been set).
Rotation is disallowed; logical and arithmetic shifts behave
identically.

After a suggestion by Vincent Belaïche.

* lisp/calc/calc-bin.el (calc-word-size, math-binary-arg)
(math-binary-modulo-args, calcFunc-lsh, calcFunc-ash, calcFunc-rot)
(math-clip): Allow a word size of 0, meaning -∞.
* test/lisp/calc/calc-tests.el
(calc-tests--not, calc-tests--and, calc-tests--or, calc-tests--xor)
(calc-tests--diff): New functions.
(calc-tests--clip, calc-tests--rot, calc-shift-binary): Extend to
cover word size 0.
(calc-bit-ops): New test.
---
 lisp/calc/calc-bin.el        | 30 ++++++++++------
 test/lisp/calc/calc-tests.el | 70 +++++++++++++++++++++++++++++++-----
 2 files changed, 80 insertions(+), 20 deletions(-)

diff --git a/lisp/calc/calc-bin.el b/lisp/calc/calc-bin.el
index aa10d55e52..3570b890ab 100644
--- a/lisp/calc/calc-bin.el
+++ b/lisp/calc/calc-bin.el
@@ -145,9 +145,10 @@ calc-word-size
    (setq math-half-2-word-size (math-power-of-2 (1- (math-abs n))))
    (calc-do-refresh)
    (calc-refresh-evaltos)
-   (if (< n 0)
-       (message "Binary word size is %d bits (two's complement)" (- n))
-     (message "Binary word size is %d bits" n))))
+   (cond
+    ((< n 0) (message "Binary word size is %d bits (two's complement)" (- n)))
+    ((> n 0) (message "Binary word size is %d bits" n))
+    (t (message "No fixed binary word size")))))
 
 
 
@@ -262,9 +263,10 @@ calcFunc-and
 (defun math-binary-arg (a w)
   (if (not (Math-integerp a))
       (setq a (math-trunc a)))
-  (if (< a 0)
-      (logand a (1- (ash 1 (if w (math-trunc w) calc-word-size))))
-    a))
+  (let ((w (if w (math-trunc w) calc-word-size)))
+    (if (and (< a 0) (not (zerop w)))
+        (logand a (1- (ash 1 w)))
+      a)))
 
 (defun math-binary-modulo-args (f a b w)
   (let (mod)
@@ -285,7 +287,7 @@ math-binary-modulo-args
     (let ((bits (math-integer-log2 mod)))
       (if bits
 	  (if w
-	      (if (/= w bits)
+	      (if (and (/= w bits) (not (zerop w)))
 		  (calc-record-why
 		   "*Warning: Modulus inconsistent with word size"))
 	    (setq w bits))
@@ -371,11 +373,12 @@ calcFunc-lsh
 	(math-clip (calcFunc-lsh a n (- w)) w)
       (if (Math-integer-negp a)
 	  (setq a (math-clip a w)))
-      (cond ((or (Math-lessp n (- w))
-		 (Math-lessp w n))
+      (cond ((and (or (Math-lessp n (- w))
+		      (Math-lessp w n))
+                  (not (zerop w)))
 	     0)
 	    ((< n 0)
-	     (math-quotient (math-clip a w) (math-power-of-2 (- n))))
+	     (ash (math-clip a w) n))
 	    (t
 	     (math-clip (math-mul a (math-power-of-2 n)) w))))))
 
@@ -403,7 +406,8 @@ calcFunc-ash
 	    (setq a (math-clip a w)))
 	(let ((two-to-sizem1 (math-power-of-2 (1- w)))
 	      (sh (calcFunc-lsh a n w)))
-	  (cond ((zerop (logand a two-to-sizem1))
+	  (cond ((or (zerop w)
+                     (zerop (logand a two-to-sizem1)))
 		 sh)
 		((Math-lessp n (- 1 w))
 		 (math-add (math-mul two-to-sizem1 2) -1))
@@ -421,6 +425,8 @@ calcFunc-rot
   (if (eq (car-safe a) 'mod)
       (math-binary-modulo-args 'calcFunc-rot a n w)
     (setq w (if w (math-trunc w) calc-word-size))
+    (when (zerop w)
+      (error "Rotation requires a nonzero word size"))
     (or (integerp w)
 	(math-reject-arg w 'fixnump))
     (or (Math-integerp a)
@@ -452,6 +458,8 @@ math-clip
 	 (if (Math-natnum-lessp a (math-power-of-2 (- -1 w)))
 	     a
 	   (math-sub a (math-power-of-2 (- w)))))
+        ((math-zerop w)
+         a)
 	((Math-negp a)
 	 (math-binary-arg a w))
 	((integerp a)
diff --git a/test/lisp/calc/calc-tests.el b/test/lisp/calc/calc-tests.el
index fe37c424d5..f8c4925c2f 100644
--- a/test/lisp/calc/calc-tests.el
+++ b/test/lisp/calc/calc-tests.el
@@ -574,15 +574,35 @@ calc-unix-date
                                           86400))))
       (should (equal (math-format-date d-1991-01-09-0600) "663400800")))))
 
-;; Reference implementations of binary shift functions:
+;; Reference implementations of bit operations:
 
 (defun calc-tests--clip (x w)
   "Clip X to W bits, signed if W is negative, otherwise unsigned."
-  (if (>= w 0)
-      (logand x (- (ash 1 w) 1))
-    (let ((y (calc-tests--clip x (- w)))
-          (msb (ash 1 (- (- w) 1))))
-      (- y (ash (logand y msb) 1)))))
+  (cond ((zerop w) x)
+        ((> w 0) (logand x (- (ash 1 w) 1)))
+        (t (let ((y (calc-tests--clip x (- w)))
+                 (msb (ash 1 (- (- w) 1))))
+             (- y (ash (logand y msb) 1))))))
+
+(defun calc-tests--not (x w)
+  "Bitwise complement of X, word size W."
+  (calc-tests--clip (lognot x) w))
+
+(defun calc-tests--and (x y w)
+  "Bitwise AND of X and W, word size W."
+  (calc-tests--clip (logand x y) w))
+
+(defun calc-tests--or (x y w)
+  "Bitwise OR of X and Y, word size W."
+  (calc-tests--clip (logior x y) w))
+
+(defun calc-tests--xor (x y w)
+  "Bitwise XOR of X and Y, word size W."
+  (calc-tests--clip (logxor x y) w))
+
+(defun calc-tests--diff (x y w)
+  "Bitwise AND of X and NOT Y, word size W."
+  (calc-tests--clip (logand x (lognot y)) w))
 
 (defun calc-tests--lsh (x n w)
   "Logical shift left X by N steps, word size W."
@@ -616,6 +636,8 @@ calc-tests--rash
 
 (defun calc-tests--rot (x n w)
   "Rotate X left by N steps, word size W."
+  (when (zerop w)
+    (error "Undefined"))
   (let* ((aw (abs w))
          (y (calc-tests--clip x aw))
          (steps (mod n aw)))
@@ -623,7 +645,7 @@ calc-tests--rot
                       w)))
 
 (ert-deftest calc-shift-binary ()
-  (dolist (w '(16 32 -16 -32))
+  (dolist (w '(16 32 -16 -32 0))
     (dolist (x '(0 1 #x1234 #x8000 #xabcd #xffff
                  #x12345678 #xabcdef12 #x80000000 #xffffffff
                  #x1234567890ab #x1234967890ab
@@ -638,8 +660,38 @@ calc-shift-binary
                        (calc-tests--ash x n w)))
         (should (equal (calcFunc-rash x n w)
                        (calc-tests--rash x n w)))
-        (should (equal (calcFunc-rot x n w)
-                       (calc-tests--rot x n w)))))))
+        (unless (zerop w)
+          (should (equal (calcFunc-rot x n w)
+                         (calc-tests--rot x n w)))))))
+  (should-error (calcFunc-rot 1 1 0)))
+
+(ert-deftest calc-bit-ops ()
+  (dolist (w '(16 32 -16 -32 0))
+    (dolist (x '(0 1 #x1234 #x8000 #xabcd #xffff
+                 #x12345678 #xabcdef12 #x80000000 #xffffffff
+                 #x1234567890ab #x1234967890ab
+                 -1 -14 #x-8000 #x-ffff #x-8001 #x-10000
+                 #x-80000000 #x-ffffffff #x-80000001 #x-100000000))
+      (should (equal (calcFunc-not x w)
+                     (calc-tests--not x w)))
+
+      (dolist (n '(0 1 4 16 32 -1 -4 -16 -32))
+        (equal (calcFunc-clip x n)
+               (calc-tests--clip x n)))
+
+      (dolist (y '(0 1 #x1234 #x8000 #xabcd #xffff
+                     #x12345678 #xabcdef12 #x80000000 #xffffffff
+                     #x1234567890ab #x1234967890ab
+                     -1 -14 #x-8000 #x-ffff #x-8001 #x-10000
+                     #x-80000000 #x-ffffffff #x-80000001 #x-100000000))
+        (should (equal (calcFunc-and x y w)
+                       (calc-tests--and x y w)))
+        (should (equal (calcFunc-or x y w)
+                       (calc-tests--or x y w)))
+        (should (equal (calcFunc-xor x y w)
+                       (calc-tests--xor x y w)))
+        (should (equal (calcFunc-diff x y w)
+                       (calc-tests--diff x y w)))))))
 
 (provide 'calc-tests)
 ;;; calc-tests.el ends here
-- 
2.21.1 (Apple Git-122.3)

bug#43764: Calc shift right broken

[Mattias Engdegård]

9 okt. 2020 kl. 17.34 skrev Vincent Belaïche <vincent.b.1@hotmail.fr>:

> 	• set bit width 0 would remove the automatic clipping meaning infinite width.

The previously mentioned patch implementing this has now been pushed to Emacs master. Thanks again for the suggestion!

I should also note the rationale for disabling left/right rotation when the word size is set to zero: while it would make sense to define

 (rotate-left x 1) =>
 x≥0: (shift-left x 1)
 x<0: (+ (shift-left x 1) 1)

 (rotate-right x 1) =>
 x≥0, x even: (shift-right x 1)
 x<0, x odd:  (shift-right x 1),

the two remaining cases of rotate right with {x≥0, x odd} or {x<0, x even} cannot result in a finite integer.

If someone has a better idea, or would like rotation to be implemented as a partial function according to the above definition, please comment. For now the bug is closed.

bug#43764: Calc shift right broken

[Vincent Belaïche]

[-- Attachment #1: Type: text/plain, Size: 3016 bytes --]

Dear Mattias,

Thank you very much for the patch, and sorry for the very very late feedback. I had a look through it, and I noticed that in math-binary-modulo-args of the code w is also tested for not being nil. Looking at it more closely I saw that word width is also taken into account when doing binary operation with modulo forms.

I can see no reason why modulo form would need some special nil case, and I suspect that at some point of time the bit-width clipping could be disabled by setting the width to nil. So now, don't we have two conventions in the code : 0 and nil. If so, that would be unfortunate for maintanability.

Also, I noticed that the Calc test suite does not have any test case (or I missed it) for binary operations + modulo forms.

Also, concerning your comment about the rotate right by n bits of numbers with non zero least significant n bits, and with disabled bit width clipping, Calc has the infinite mode (press 'm i'), so if you decide some day to make this sort of implementation, then you should emit an error w/o infinite mode, but have a +inf with infinite mode. A bit (n-1) equal to 1 won't cause any -inf, because two complement signing is not possible with disabled bit width clipping, as this would result in an infinite number of FFFFFF with negative finite numbers.

I also notice that when two's complement signing display is on (type 'O d 6'), and bit width is set to 0 to disable bit width clipping, then the signing display is done as if the TwosComp mode was off. I think that it is OK to do that, but when 'b w 0 RET' or 'O d 6' is pressed, which ever comes last, and we have this conflict, then a warning message should be emitted, something like « Twos complement sign display is ignored when bit word width is not specified ».

  Vincent.
________________________________
De : Mattias Engdegård <mattiase@acm.org>
Envoyé : mardi 13 octobre 2020 11:56
À : Vincent Belaïche <vincent.b.1@hotmail.fr>
Cc : Lars Ingebrigtsen <larsi@gnus.org>; 43764-done@debbugs.gnu.org <43764-done@debbugs.gnu.org>
Objet : Re: bug#43764: Calc shift right broken

9 okt. 2020 kl. 17.34 skrev Vincent Belaïche <vincent.b.1@hotmail.fr>:

>        • set bit width 0 would remove the automatic clipping meaning infinite width.

The previously mentioned patch implementing this has now been pushed to Emacs master. Thanks again for the suggestion!

I should also note the rationale for disabling left/right rotation when the word size is set to zero: while it would make sense to define

 (rotate-left x 1) =>
 x≥0: (shift-left x 1)
 x<0: (+ (shift-left x 1) 1)

 (rotate-right x 1) =>
 x≥0, x even: (shift-right x 1)
 x<0, x odd:  (shift-right x 1),

the two remaining cases of rotate right with {x≥0, x odd} or {x<0, x even} cannot result in a finite integer.

If someone has a better idea, or would like rotation to be implemented as a partial function according to the above definition, please comment. For now the bug is closed.


[-- Attachment #2: Type: text/html, Size: 5276 bytes --]

bug#43764: Calc shift right broken

[Mattias Engdegård]

4 nov. 2020 kl. 12.14 skrev Vincent Belaïche <vincent.b.1@hotmail.fr>:

> I can see no reason why modulo form would need some special nil case, and I suspect that at some point of time the bit-width clipping could be disabled by setting the width to nil. So now, don't we have two conventions in the code : 0 and nil.

From my reading of math-binary-modulo-args, the word width (w) isn't tested because calc-word-size can be nil, but because it may be passed as an optional argument. See calcFunc-and for an example.

> Also, I noticed that the Calc test suite does not have any test case (or I missed it) for binary operations + modulo forms.

The Calc test suite is minimal and mostly consists of regression tests added when fixing bugs during the last year or so. The vast bulk of Calc remains untested. Contributions are welcome!

> Also, concerning your comment about the rotate right by n bits of numbers with non zero least significant n bits, and with disabled bit width clipping, Calc has the infinite mode (press 'm i'), so if you decide some day to make this sort of implementation, then you should emit an error w/o infinite mode, but have a +inf with infinite mode. A bit (n-1) equal to 1 won't cause any -inf, because two complement signing is not possible with disabled bit width clipping, as this would result in an infinite number of FFFFFF with negative finite numbers.

My remarks were probably not very well thought out, sorry. Infinities and bitwise operations seem difficult to reconcile in general; for example, (+inf AND 1) is undefined. Any extension to include ±inf would need better underpinning than my feeble attempt.

Note however that with disabled bit width, negative numbers do in fact have an infinite number of leading ones, just as nonnegative numbers have an infinite numbers of leading zeros. This is just how two's complement works when there is no limited word size, and it doesn't involve actual infinites.

> I also notice that when two's complement signing display is on (type 'O d 6'), and bit width is set to 0 to disable bit width clipping, then the signing display is done as if the TwosComp mode was off. I think that it is OK to do that, but when 'b w 0 RET' or 'O d 6' is pressed, which ever comes last, and we have this conflict, then a warning message should be emitted, something like « Twos complement sign display is ignored when bit word width is not specified ».

Yes, there are probably edge cases where usability can be improved, but it didn't seem to involve actual errors or user deception so I didn't bother do more work than necessary.

Thank you very much for your remarks!