GNU bug report logs - #43764
Calc shift right broken

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 43764 in the body.
You can then email your comments to 43764 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Vincent Belaïche <vincent.b.1 <at> hotmail.fr>
To: "bug-gnu-emacs <at> gnu.org" <bug-gnu-emacs <at> gnu.org>
Subject: Calc shift right broken
Date: Fri, 2 Oct 2020 15:28:22 +0000

[Message part 1 (text/plain, inline)]

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.

[Message part 2 (text/html, inline)]

Message #8 received at 43764 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Vincent Belaïche <vincent.b.1 <at> hotmail.fr>
Cc: 43764 <at> debbugs.gnu.org
Subject: bug#43764: Calc shift right broken
Date: Fri, 2 Oct 2020 22:49:07 +0200

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.

Message #11 received at 43764 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Vincent Belaïche <vincent.b.1 <at> hotmail.fr>,
 43764 <at> debbugs.gnu.org
Subject: Re: bug#43764: Calc shift right broken
Date: Mon, 05 Oct 2020 10:12:54 +0200

Mattias Engdegård <mattiase <at> 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

Message #14 received at 43764 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: Vincent Belaïche <vincent.b.1 <at> hotmail.fr>,
 43764 <at> debbugs.gnu.org
Subject: Re: bug#43764: Calc shift right broken
Date: Mon, 5 Oct 2020 12:34:15 +0200

5 okt. 2020 kl. 10.12 skrev Lars Ingebrigtsen <larsi <at> 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.)

Message #17 received at 43764 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Vincent Belaïche <vincent.b.1 <at> hotmail.fr>,
 43764 <at> debbugs.gnu.org
Subject: Re: bug#43764: Calc shift right broken
Date: Tue, 06 Oct 2020 03:28:56 +0200

Mattias Engdegård <mattiase <at> 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

Message #20 received at 43764 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: Vincent Belaïche <vincent.b.1 <at> hotmail.fr>,
 43764 <at> debbugs.gnu.org
Subject: Re: bug#43764: Calc shift right broken
Date: Thu, 8 Oct 2020 14:24:02 +0200

6 okt. 2020 kl. 03.28 skrev Lars Ingebrigtsen <larsi <at> 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))))))
 

Message #23 received at 43764 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: Vincent Belaïche <vincent.b.1 <at> hotmail.fr>,
 43764 <at> debbugs.gnu.org
Subject: Re: bug#43764: Calc shift right broken
Date: Fri, 9 Oct 2020 17:29:58 +0200

> 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.

Message #26 received at 43764 <at> debbugs.gnu.org (full text, mbox):

From: Vincent Belaïche <vincent.b.1 <at> hotmail.fr>
To: Lars Ingebrigtsen <larsi <at> gnus.org>, Mattias Engdegård
 <mattiase <at> acm.org>
Cc: "43764 <at> debbugs.gnu.org" <43764 <at> debbugs.gnu.org>
Subject: RE: bug#43764: Calc shift right broken
Date: Fri, 9 Oct 2020 15:34:35 +0000

[Message part 1 (text/plain, inline)]

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 <at> gnus.org>
Envoyé : mardi 6 octobre 2020 03:28
À : Mattias Engdegård <mattiase <at> acm.org>
Cc : Vincent Belaïche <vincent.b.1 <at> hotmail.fr>; 43764 <at> debbugs.gnu.org <43764 <at> debbugs.gnu.org>
Objet : Re: bug#43764: Calc shift right broken

Mattias Engdegård <mattiase <at> 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

[Message part 2 (text/html, inline)]

Message #29 received at 43764 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Vincent Belaïche <vincent.b.1 <at> hotmail.fr>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>,
 "43764 <at> debbugs.gnu.org" <43764 <at> debbugs.gnu.org>
Subject: Re: bug#43764: Calc shift right broken
Date: Sat, 10 Oct 2020 18:24:39 +0200

9 okt. 2020 kl. 17.34 skrev Vincent Belaïche <vincent.b.1 <at> 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.

Message #32 received at 43764 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Vincent Belaïche <vincent.b.1 <at> hotmail.fr>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>,
 "43764 <at> debbugs.gnu.org" <43764 <at> debbugs.gnu.org>
Subject: Re: bug#43764: Calc shift right broken
Date: Sat, 10 Oct 2020 18:31:28 +0200

[Message part 1 (text/plain, inline)]

10 okt. 2020 kl. 18.24 skrev Mattias Engdegård <mattiase <at> 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.

[0001-Calc-allow-infinite-binary-word-size-bug.patch (application/octet-stream, attachment)]

Message #37 received at 43764-done <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Vincent Belaïche <vincent.b.1 <at> hotmail.fr>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, 43764-done <at> debbugs.gnu.org
Subject: Re: bug#43764: Calc shift right broken
Date: Tue, 13 Oct 2020 11:56:50 +0200

9 okt. 2020 kl. 17.34 skrev Vincent Belaïche <vincent.b.1 <at> 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.

Message #40 received at 43764-done <at> debbugs.gnu.org (full text, mbox):

From: Vincent Belaïche <vincent.b.1 <at> hotmail.fr>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>,
 "43764-done <at> debbugs.gnu.org" <43764-done <at> debbugs.gnu.org>
Subject: RE: bug#43764: Calc shift right broken
Date: Wed, 4 Nov 2020 11:14:20 +0000

[Message part 1 (text/plain, inline)]

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 <at> acm.org>
Envoyé : mardi 13 octobre 2020 11:56
À : Vincent Belaïche <vincent.b.1 <at> hotmail.fr>
Cc : Lars Ingebrigtsen <larsi <at> gnus.org>; 43764-done <at> debbugs.gnu.org <43764-done <at> debbugs.gnu.org>
Objet : Re: bug#43764: Calc shift right broken

9 okt. 2020 kl. 17.34 skrev Vincent Belaïche <vincent.b.1 <at> 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.

[Message part 2 (text/html, inline)]

Message #43 received at 43764 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Vincent Belaïche <vincent.b.1 <at> hotmail.fr>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>, 43764 <at> debbugs.gnu.org
Subject: Re: bug#43764: Calc shift right broken
Date: Wed, 4 Nov 2020 12:54:59 +0100

4 nov. 2020 kl. 12.14 skrev Vincent Belaïche <vincent.b.1 <at> 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!

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.