Add support for bitwise left/right shift operators#8457
Add support for bitwise left/right shift operators#8457yegappan wants to merge 1 commit intovim:masterfrom
Conversation
Codecov Report
@@ Coverage Diff @@
## master #8457 +/- ##
==========================================
+ Coverage 81.60% 81.62% +0.01%
==========================================
Files 158 158
Lines 184991 185128 +137
Branches 41845 41877 +32
==========================================
+ Hits 150968 151106 +138
+ Misses 21503 21499 -4
- Partials 12520 12523 +3
Flags with carried forward coverage won't be shown. Click here to find out more.
Continue to review full report at Codecov.
|
runtime/doc/eval.txt
Outdated
|
|
||
| lshift({expr1}, {expr2}) *lshift()* | ||
| Bitwise left shift {expr1} by {expr2}. The arguments must be | ||
| Numbers. Other types of arguments cause an error. |
There was a problem hiding this comment.
Usually bit shifts in C are done with unsigned (although it's also possible with signed).
Vim script does not have unsigned.
We should document how it behaves with the sign bit. In other words, what is the result of lshift(-2, 1)?
And we should test with negative numbers too.
In Java, left-shift has 2 different operators >> (sign extension) and >>> (shifts a zero into the leftmost position). See: https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html So maybe we need an extra (optional?) parameter to indicate whether to extend sign or not?
There was a problem hiding this comment.
Thanks for the review. Yes. We can add an option to rshift() to deal with sign extension.
src/evalfunc.c
Outdated
| return; | ||
| } | ||
| rettv->vval.v_number = tv_get_number(&argvars[0]) | ||
| << tv_get_number(&argvars[1]); |
There was a problem hiding this comment.
This will result in UB (undefined behavior) if we do e.g. lshift(1, 100) as in C, it is UB to bit-shifts by more bits than the number of bits in the number.
In Vim script, we don't want such undefined behavior. I'd say lshift(1, 100) should return 0, and we must thus return 0 if argvars[1] is too high. And we can add a test for bit shift with large number of bits.
We can verify that there is no runtime error using ubsan.
Also, what should happen when shifting by a negative number of bits? E.g. lshift(1, -1) In C, it is undefined behavior but again, we don't want UB in Vim script.
There was a problem hiding this comment.
I will add a check for argvars[1] and return 0 if it is too large. If the shift value is negative, we can return the original value.
|
Yegappen wrote:
The following bitwise functions are currently supported: and(), or(),
xor() and invert().
But there is no function or operator for bitwise left/right shift.
Add the lshift() and rshift() functions for bitwise left shift and
right shift.
I'm wondering if it is worth it. You can also use "* 2" for left shift
and "/ 2" for right shift. It's not exactly the same (considering
overflow), but does that matter in a Vim script?
…--
My sister Cecilia opened a computer store in Hawaii.
She sells C shells by the seashore.
/// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net \\\
/// \\\
\\\ sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ ///
\\\ help me help AIDS victims -- http://ICCF-Holland.org ///
|
|
Hi Bram,
On Sat, Jun 26, 2021 at 3:04 AM Bram Moolenaar ***@***.***> wrote:
Yegappen wrote:
> The following bitwise functions are currently supported: and(), or(),
> xor() and invert().
> But there is no function or operator for bitwise left/right shift.
> Add the lshift() and rshift() functions for bitwise left shift and
> right shift.
I'm wondering if it is worth it. You can also use "* 2" for left shift
and "/ 2" for right shift. It's not exactly the same (considering
overflow), but does that matter in a Vim script?
Without these functions, to left/right shift a number, you need to
do something like the following:
Left Shift:
let c = a * float2nr(pow(2, b))
Right Shift:
let c = float2nr(floor(a / pow(2, b)))
I thought it would be simpler to have a separate function for this.
Regards,
Yegappan
|
|
I appear to have missed this one. Bit shift does not apply to floats, your example does not seem representative. |
|
Hi Bram,
On Mon, Nov 15, 2021 at 11:08 AM Bram Moolenaar ***@***.***> wrote:
I appear to have missed this one. Bit shift does not apply to floats, your
example does not seem representative.
Left Shift:
let c = a * float2nr(pow(2, b))
Right Shift:
let c = float2nr(floor(a / pow(2, b)))
The above examples are not doing bit shifts of a float. To compute 2 ^ n,
you need to
use the pow() function which returns a float. You then need to use
float2nr() to
remove the fraction.
lshift(val, 4) would be equivalent to "val * 16" and rshift(val, 4)
equivalent to "val / 16".
If you know the number of bits to shift beforehand, then you can use a
hard coded
number like 16. Otherwise, you need to use the pow() function to compute 2
^ n.
Regards,
Yegappan
|
|
Any update on this PR? The pow+float2nr approach works but is quite a mouthful, having the shift operators would greatly complement the other bit ops. |
|
I have no see a response to my suggestion to use "N * 16" to shift 4 bits left and "N / 16" to shift 4 bits right. |
|
I mean, why it would be needed to specify the number of bits. When do you not know that beforehand? |
|
Sometimes I use bitsets to keep track of a small (< bit size of number variable) number of boolean elements, that's much faster than eg. having a list with N bool elements. |
22db963 to
a8106c1
Compare
6cb840c to
c7c2bc8
Compare
|
I was trying to find another language that uses a function for bitwise shift, but it appears all the popular languages use ">>" and "<<" operators. Would that be possible in Vim as well, or would it create a conflict? Another thing to consider is to use one function, where a negative argument is used to shift in the other direction. Again, this would depend on how other languages do this, what people are used to. |
Java uses Something to consider if Vim script has bit shift operators. |
2d37bfe to
3864da5
Compare
src/vim9.h
Outdated
| ISN_COMPAREFUNC, | ||
| ISN_COMPAREANY, | ||
|
|
||
| // bitwise left/right shift operation |
There was a problem hiding this comment.
This should be another case of ISN_OPNR instead of having its own opcode.
There was a problem hiding this comment.
I have updated the PR to use ISN_OPNR instead of using a new opcode.
src/vim9execute.c
Outdated
| (uvarnumber_T)tv1->vval.v_number >> tv2->vval.v_number; | ||
|
|
||
| // clear the topmost sign bit | ||
| tv1->vval.v_number &= |
There was a problem hiding this comment.
I think this to be quite weird, I'd let the user deal with negative numbers rather than making the integers N-1bit wide.
There was a problem hiding this comment.
This is based on the following comment from Bram:
Since bitwise operators should not care about a sign bit, I would very
much prefer ">>" to just make the topmost bit zero. No need for ">>>"
then.
7b6f85a to
8915b3e
Compare
|
" The topmost bit (sign bit) is always cleared " that is for the ">>" operator, not for "<<". For operator precedence it looks like we need a new level. It's in between "+" and "-" This is what Ecmascript specifies: Are there languages that use a different precedence? I know have have often been confused by this, but we should stick to what most other popular languages do. |
| if (iptr->isn_arg.op.op_type == EXPR_RSHIFT) | ||
| // clear the topmost sign bit | ||
| res &= ~((uvarnumber_T)1 << MAX_LSHIFT_BITS); |
There was a problem hiding this comment.
This fixup only works if arg2 is 1. Something like following is needed.
result &= ~((1 << arg2) - 1 << NBITS - arg2)
If right shifted by 3 and NBITS is 8 then this should be &= 0001_1111.
If you can count on the compiler to respect unsigned and make sure zeros are shifted in, then you don't need a fixup. If you can't count on the compiler, this might be more understandable and doesn't need a fixup.
res = arg1 >> 1;
res &= ~(1 << MAX_LSHIFT_BITS);
res = res >> arg2 - 1;
None of this is tested, simulated on paper... (I looked up the precedence against +/-)
There was a problem hiding this comment.
Oops, updated to add the missing ~ and &= 0001_1111
Ah I see, the comment didn't get posted to GH for some reason. That's fine as long as it's clearly stated in the docs that the operators perform logical shifts (opposed to arithmetic ones). The sign-clearing is useless as you're already performing the shift on unsigned values. The next logical step is to extend the and/or/not operators to work with numbers, right now shifts are the only exception among the bitwise ops. |
|
In a performance sensitive function I recently used vim's I guess if invoking |
|
ac0d235 to
1d30350
Compare
|
I don't spot a test case for repeating the operator, e.g. |
|
I have updated the PR to support using multiple bit shift operators in an expression and added additional tests. |
|
Looks like it is ready to include now, thanks. |
| if (iptr->isn_arg.op.op_type == EXPR_RSHIFT) | ||
| // clear the topmost sign bit | ||
| res &= ~((uvarnumber_T)1 << MAX_LSHIFT_BITS); |
There was a problem hiding this comment.
Have you tried it without this post shift fixup? Since the type of the the left hand side is unsigned, no adjustment is needed.
|
Hi,
On Sun, May 22, 2022 at 10:41 AM errael ***@***.***> wrote:
***@***.**** commented on this pull request.
------------------------------
In src/vim9execute.c
<#8457 (comment)>:
> + if (iptr->isn_arg.op.op_type == EXPR_RSHIFT)
+ // clear the topmost sign bit
+ res &= ~((uvarnumber_T)1 << MAX_LSHIFT_BITS);
Have you tried it without this post shift fixup? Since the type of the the
left hand side is unsigned, no adjustment is needed.
The left operand of a bitshift operator can be a negative number. Earlier
I had a check to display
an error if the left operand is a negative number. But I removed that
check based on one of the
comments. I will add some tests for right shifting negative numbers and
then remove this code.
- Yegappan
|
|
On 5/22/22 11:00 AM, Yegappan Lakshmanan wrote:
The left operand of a bitshift operator can be a negative number.
Consider this case: -1 >> 0
The result should be -1.
AFAICT. The code treats the number as unsigned and does a logical right
shift, so no fixup needed.
|
|
@DominiquePelle-TomTom commented on this pull request.
> @@ -946,4 +946,48 @@ func Test_string_interp()
call v9.CheckDefAndScriptSuccess(lines)
endfunc
+" Test for bitwise left and right shift (<< and >>)
+func Test_bitwise_shift()
+ let lines =<< trim END
+ call assert_equal(16, 1 << 4)
+ call assert_equal(2, 16 >> 3)
+ call assert_equal(0, 0 << 2)
+ call assert_equal(0, 0 >> 4)
+ call assert_equal(3, 3 << 0)
+ call assert_equal(3, 3 >> 0)
+ call assert_equal(0, 0 >> 4)
What happens if you do:
* `42 >> -1` (in C, shifting by negative number is undefined
behavior, in Vim it should be an error or maybe 0?)
Trying to shift by a negative amount is nearly always a mistake. In my
opinion it should be an error.
* `42 << 100` or `42 >> 100` (in C, shift by more bits than the
underlying type is undefined behavior, in Vim it should be an error or
maybe 0?)
A huge number could be a mistake, but how does the user know what the
maximum is? Probably 64, but one can't be sure. And would then 64 be
an error (since the result is always zero) or above 64? Getting a zero
result is more useful than getting an error.
…--
hundred-and-one symptoms of being an internet addict:
252. You vote for foreign officials.
/// Bram Moolenaar -- ***@***.*** -- http://www.Moolenaar.net \\\
/// \\\
\\\ sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ ///
\\\ help me help AIDS victims -- http://ICCF-Holland.org ///
|
The following bitwise functions are currently supported: and(), or(), xor() and invert().
But there is no function or operator for bitwise left/right shift.
Add the << and >> operators for bitwise left shift and right shift.