www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - A more general bsr/bsf implementation

reply "Johan Engelen" <j j.nl> writes:
Currently, druntime only supports bsf/bsf, i.e. finding the first 
or last bit set, on size_t [1]; bsf(size_t) and bsr(size_t) are 
compiler intrinsics.
Because only size_t is supported, it is cumbersome to write 
generic code using bsf/bsr. For example, for 64-bit code 
bsr(long(...)) will work, but not for 32-bit code. bsr(cent(...)) 
will not work either.
To improve std.math.ilogb, I need a generic bsr. So I figured I 
add that to druntime or Phobos.

I wrote more generic bsr/bsf but I stumbled across an unexpected 
result:
Currently, bsr(byte(-1))) is equal to 31 instead of 7. My general 
bsr honors the width of the input type, and returns 7 for this 
example. The problem now of course is that replacing the old bsr 
with my bsr would potentially break existing code (the existing 
code may then already be broken when considering 32-bit and 
64-bit mode).

My questions:
1) Is it OK to put a more general bsf/bsr in druntime or in 
Phobos? (if Phobos: in which package to put it?)
2) Is the current sign-extend up to size_t's width really 
intended behavior?

Thanks a bunch,
   Johan

[1] http://dlang.org/phobos/core_bitop.html#.bsr
Apr 12 2015
parent reply "safety0ff" <safety0ff.dev gmail.com> writes:
On Sunday, 12 April 2015 at 11:53:41 UTC, Johan Engelen wrote
 My questions:
 1) Is it OK to put a more general bsf/bsr in druntime or in 
 Phobos? (if Phobos: in which package to put it?)
IMO I want a std.integer package for such functions. I started writing one but I have to rewrite it. I don't know if building up such a package by piecemeal would be accepted.
 2) Is the current sign-extend up to size_t's width really 
 intended behavior?
It's due to integer promotions, so it should only influence bsr (when it is called with a signed type.)
Apr 12 2015
parent reply "Johan Engelen" <j j.nl> writes:
 2) Is the current sign-extend up to size_t's width really 
 intended behavior?
It's due to integer promotions, so it should only influence bsr (when it is called with a signed type.)
Sorry for not being clear. I understand why the current bsr behaves like it does, but what I meant is whether that is the desired behavior of bsr: bsr( byte(-1) ) == 31 (32-bit size_t) bsr( byte(-1) ) == 63 (64-bit size_t) instead of bsr( byte(-1) ) == 7
Apr 12 2015
next sibling parent ketmar <ketmar ketmar.no-ip.org> writes:
On Sun, 12 Apr 2015 15:21:24 +0000, Johan Engelen wrote:

 2) Is the current sign-extend up to size_t's width really intended
 behavior?
It's due to integer promotions, so it should only influence bsr (when it is called with a signed type.)
=20 Sorry for not being clear. I understand why the current bsr behaves like it does, but what I meant is whether that is the desired behavior of bsr: bsr( byte(-1) ) =3D=3D 31 (32-bit size_t) bsr( byte(-1) ) =3D=3D 63 (64-bit size_t) instead of bsr( byte(-1) ) =3D=3D 7
i'd say that with explicitly given type it should be 7. but i don't know=20 if it will break any code in druntime/phobos...=
Apr 12 2015
prev sibling parent "safety0ff" <safety0ff.dev gmail.com> writes:
On Sunday, 12 April 2015 at 15:21:26 UTC, Johan Engelen wrote:
 Sorry for not being clear.
I should have thought about it more before answering. :)
 I understand why the current bsr behaves like it does, but what 
 I meant is whether that is the desired behavior of bsr:
     bsr( byte(-1) ) == 31  (32-bit size_t)
     bsr( byte(-1) ) == 63  (64-bit size_t)
 instead of
     bsr( byte(-1) ) == 7
I think 7 is the desired result. I don't know whether there are uses for bsr with negative signed arguments since it returns the MSB position for all values.
Apr 13 2015