"Ben Hinkle" <ben.hinkle@gmail.com> wrote in message news:de7enn$1998$1@digitaldaemon.com...
> The thing about a bit array is that it doesn't know about big-endian or little-endian and the exact packing of the bit array into memory is compiler-dependent (see for example http://www.digitalmars.com/d/arrays.html#bitarrays). With shifting the compiler knows the size of the data being shifted and so you the coder don't have to worry about all the memory layout details.

Oof.  Yeah, that's an issue.

On Sat, 20 Aug 2005 10:28:33 -0400, Ben Hinkle <ben.hinkle@gmail.com> wrote:
> "Jarrett Billingsley" <kb3ctd2@yahoo.com> wrote in message
> news:de7c77$17at$1@digitaldaemon.com...
>> "Regan Heath" <regan@netwin.co.nz> wrote in message
>> news:opsvr9dkx523k2f5@nrage.netwin.co.nz...
>>> I've often thought that the ability to slice any basic type would be
>>> quite nice, eg.
>>>
>>> ubyte b;
>>> uint i;
>>> long l;
>>>
>>> b[0] = 1;
>>> i[5] = 0;
>>> l[16..32] = 1;
>>>
>>> in other words slicing a basic type gives a bit[] or bit.
>>>
>>> Of course the big problem that rears it's head is how does this work:
>>>
>>> bit[] b;
>>> uint i;
>>>
>>> b = i[5..15];
>>>
>>> A slice on non-byte boundaries... It seems it can't without copying or
>>> great internal hoop jumping. So, I would limit the feature to lvalue
>>> assignments instead, i.e.
>>>
>>> bit[10] b;
>>> uint i;
>>>
>>> i[5..15] = b[]; //would be fine, but
>>> b = i[5..15]; //would not
>>>
>>> perhaps, if we desire, we can allow:
>>>
>>> b[] = i[5..15];
>>>
>>> or
>>>
>>> b = i[5..15].dup;
>>>
>>> i.e. a copy would be easier to implement.
>>>
>>> The reason I like this is that code that would read something like:
>>>
>>> variable |= 1<<16;
>>>
>>> or
>>>
>>> variable &= ~(1<<16)
>>>
>>> or whatever can now read:
>>>
>>> variable[16] = 1;
>>>
>>> or
>>>
>>> variable[16] = 0;
>>>
>>> (note I have not paid strict attention to the code above, it's probably
>>> wrong, but you should get the picture)
>>>
>>> Regan
>>
>> Right, that's kind of what I would like this for, twiddling bits in
>> numbers. I was thinking about something to replace bitfields as well, as
>> shifting and masking is just so much fun, but it'd be nice to do something
>> like a[0..4]=6.  Then again, for bitfields, you could use a union between
>> a bit[32] and a uint.
>>
>
> The thing about a bit array is that it doesn't know about big-endian or
> little-endian and the exact packing of the bit array into memory is
> compiler-dependent (see for example
> http://www.digitalmars.com/d/arrays.html#bitarrays). With shifting the
> compiler knows the size of the data being shifted and so you the coder don't
> have to worry about all the memory layout details.

All the more reason to have the ability to slice basic types built-in and have the compiler work it's magic in the background.

Regan

"Regan Heath" <regan@netwin.co.nz> wrote in message news:opsvtzskgc23k2f5@nrage.netwin.co.nz...
> On Sat, 20 Aug 2005 10:28:33 -0400, Ben Hinkle <ben.hinkle@gmail.com> wrote:
>> "Jarrett Billingsley" <kb3ctd2@yahoo.com> wrote in message news:de7c77$17at$1@digitaldaemon.com...
>>> "Regan Heath" <regan@netwin.co.nz> wrote in message news:opsvr9dkx523k2f5@nrage.netwin.co.nz...
>>>> I've often thought that the ability to slice any basic type would be quite nice, eg.
>>>>
>>>> ubyte b;
>>>> uint i;
>>>> long l;
>>>>
>>>> b[0] = 1;
>>>> i[5] = 0;
>>>> l[16..32] = 1;
>>>>
>>>> in other words slicing a basic type gives a bit[] or bit.
>>>>
>>>> Of course the big problem that rears it's head is how does this work:
>>>>
>>>> bit[] b;
>>>> uint i;
>>>>
>>>> b = i[5..15];
>>>>
>>>> A slice on non-byte boundaries... It seems it can't without copying or great internal hoop jumping. So, I would limit the feature to lvalue assignments instead, i.e.
>>>>
>>>> bit[10] b;
>>>> uint i;
>>>>
>>>> i[5..15] = b[]; //would be fine, but
>>>> b = i[5..15]; //would not
>>>>
>>>> perhaps, if we desire, we can allow:
>>>>
>>>> b[] = i[5..15];
>>>>
>>>> or
>>>>
>>>> b = i[5..15].dup;
>>>>
>>>> i.e. a copy would be easier to implement.
>>>>
>>>> The reason I like this is that code that would read something like:
>>>>
>>>> variable |= 1<<16;
>>>>
>>>> or
>>>>
>>>> variable &= ~(1<<16)
>>>>
>>>> or whatever can now read:
>>>>
>>>> variable[16] = 1;
>>>>
>>>> or
>>>>
>>>> variable[16] = 0;
>>>>
>>>> (note I have not paid strict attention to the code above, it's probably wrong, but you should get the picture)
>>>>
>>>> Regan
>>>
>>> Right, that's kind of what I would like this for, twiddling bits in
>>> numbers. I was thinking about something to replace bitfields as well, as
>>> shifting and masking is just so much fun, but it'd be nice to do
>>> something
>>> like a[0..4]=6.  Then again, for bitfields, you could use a union
>>> between
>>> a bit[32] and a uint.
>>>
>>
>> The thing about a bit array is that it doesn't know about big-endian or
>> little-endian and the exact packing of the bit array into memory is
>> compiler-dependent (see for example
>> http://www.digitalmars.com/d/arrays.html#bitarrays). With shifting the
>> compiler knows the size of the data being shifted and so you the coder
>> don't
>> have to worry about all the memory layout details.
>
> All the more reason to have the ability to slice basic types built-in and have the compiler work it's magic in the background.
>
> Regan

I don't think the problems can be wished away with magic. The core issue is
that bit[] forgets the layout of the numeric types. What would the
expression x[a .. b] actually return? I don't mean "it returns the bits from
a to b". I mean what is the type of the result? It should't be bit[].
It's simpler (and well-defined) to use & and |. Besides to me x[a .. b] is
array indexing not bit-twiddling so I'm not even sure I like the idea of
abusing [] to slice numeric types.

On Sun, 21 Aug 2005 10:05:46 -0400, Ben Hinkle <ben.hinkle@gmail.com> wrote:
>> All the more reason to have the ability to slice basic types built-in and have the compiler work it's magic in the background.
>
> I don't think the problems can be wished away with magic. The core issue is
> that bit[] forgets the layout of the numeric types. What would the
> expression x[a .. b] actually return? I don't mean "it returns the bits from
> a to b". I mean what is the type of the result?

Almost irrelevant. eg. in an assignment:

uint b;
b[0..5] = 1;

It doesn't matter, the compiler is doing it all in the background, the user never needs to know the type, or have one to store anything in, however.. (see next response)

> It should't be bit[].

Why not?

I mean, if you actually want to copy bits, you might write:

bit[5] a;
uint b;

a[] = b[0..5];

I don't think we need/want to remove the bit[] types I just think being able to slice basic types to get bit[] types would be very useful. I think we do want to restrict it to bit boundaries or require a copy (anything else seems quite complicated, though the compiler is the best place to handle that, if it was desired)

> It's simpler

I disagree. After years of experience using & and | is easy (perhaps 'simple'), but, to a begginer it's not at all.

> (and well-defined) to use & and |.

In C and other languages, yes. In D, c'mon we have bit[], surely it can make bit twiddling really nice and easy. It seems bizarre to say the least that we're not using bit[] for bit twiddling but instead using old techniques which are both harder to understand and use (until you're proficient with them).

> Besides to me x[a .. b] is array indexing not bit-twiddling

Sure, until you add "= 1" or "= 0", then it's an assignment and thus bit twiddling .. obviously?

> so I'm not even sure I like the idea of
> abusing [] to slice numeric types.

"abusing" .. your opinion is obvious from your choice of words ;)

IMO the idea of slicing a basic type to get bit[]:
 - Makes bit twiddling _much_ easier.
 - Makes bit twiddling _much_ simpler for begginers.
 - Makes more use of the bit[] type (we're not using it for bit twiddling, why?).

Regan

"Regan Heath" <regan@netwin.co.nz> wrote in message news:opsvvmcao123k2f5@nrage.netwin.co.nz...
> On Sun, 21 Aug 2005 10:05:46 -0400, Ben Hinkle <ben.hinkle@gmail.com> wrote:
>>> All the more reason to have the ability to slice basic types built-in and have the compiler work it's magic in the background.
>>
>> I don't think the problems can be wished away with magic. The core issue
>> is
>> that bit[] forgets the layout of the numeric types. What would the
>> expression x[a .. b] actually return? I don't mean "it returns the bits
>> from
>> a to b". I mean what is the type of the result?
>
> Almost irrelevant. eg. in an assignment:
>
> uint b;
> b[0..5] = 1;
>
> It doesn't matter, the compiler is doing it all in the background, the user never needs to know the type, or have one to store anything in, however.. (see next response)

I thought you guys were looking for something general purpose. I agree if the proposal is limited to indexed assignment statements that the return type doesn't matter because there is no return type. But that's not what the proposal is, I thought.

>> It should't be bit[].
>
> Why not?

See http://en.wikipedia.org/wiki/Endian. On big-endian machines b[0..16], for example, would be the last two bytes of the memory range &b .. &b+4 in reverse order and for little endian machines is the first two bytes in incresing order. For longs and shorts it would behave similarly. The type bit[] is packed into compiler-dependent chunks in whatever ways it wants. I imagine it would take some non-trivial changes to bit[] to support slicing non-int sized types on big-endian machines.

> I mean, if you actually want to copy bits, you might write:
>
> bit[5] a;
> uint b;
>
> a[] = b[0..5];

I understand.

> I don't think we need/want to remove the bit[] types I just think being able to slice basic types to get bit[] types would be very useful.

I'm not aware of any post in this thread suggesting bit[] go away. I'm aware you think slicing basic types to get bit[] would be useful.

> I think  we do want to restrict it to bit boundaries or require a copy (anything  else seems quite complicated, though the compiler is the best place to  handle that, if it was desired)

I'm not sure what exactly you are referring to. Which bit boundaries and copying do you mean? By the way, I'm guessing as to exactly what the proposal is. My impression is that the proposal is to slice lvalues of numeric type to obtain bit[]. The only numeric type I can imagine it working for is the underlying numeric type used by bit[] (on big endian machines). For little endian machines bit[] can be used for any slice that starts at a multiple of the underlying bit-packing unit (eg int).

>> It's simpler
>
> I disagree. After years of experience using & and | is easy (perhaps 'simple'), but, to a begginer it's not at all.

Given that using bit[] will require lots of special cases to explain (see
above) I think & and | is simpler. If that's too confusing for beginners one
can write simple functions like
template getbit(T)
  bit getbit(T x, int n){
    return cast(bit)(x & ((cast(T)1) << n));
  }
}
etc

>> (and well-defined) to use & and |.
>
> In C and other languages, yes. In D, c'mon we have bit[], surely it can make bit twiddling really nice and easy. It seems bizarre to say the least that we're not using bit[] for bit twiddling but instead using old techniques which are both harder to understand and use (until you're proficient with them).

I think a more detailed proposal would help show the trade-off and true impact of trying to extend bit[] to be used as a replacement for &|. I don't think it's a trivial as you assume. I view bit[] as only being a packed array of true/false values (ala Pascal and C++). The exact packing behavior is compiler-dependent.

>> Besides to me x[a .. b] is array indexing not bit-twiddling
>
> Sure, until you add "= 1" or "= 0", then it's an assignment and thus bit twiddling .. obviously?
>
>> so I'm not even sure I like the idea of
>> abusing [] to slice numeric types.
>
> "abusing" .. your opinion is obvious from your choice of words ;)
>
> IMO the idea of slicing a basic type to get bit[]:
>  - Makes bit twiddling _much_ easier.
>  - Makes bit twiddling _much_ simpler for begginers.
>  - Makes more use of the bit[] type (we're not using it for bit twiddling,
> why?).
>
> Regan

Other languages have bit arrays - I'm thinking specifically of Pascal's packed arrays and STL's bit vectors but there could be others, too. I'm not aware of any that try to use bit arrays to do bit twiddling. They are meant to be memory efficient arrays of true/false values and that's it.

On Sun, 21 Aug 2005 19:22:54 -0400, Ben Hinkle <ben.hinkle@gmail.com> wrote:
>> It doesn't matter, the compiler is doing it all in the background, the
>> user never needs to know the type, or have one to store anything in,
>> however.. (see next response)
>
> I thought you guys were looking for something general purpose.

The OP might have been. I wasn't.

> I agree if
> the proposal is limited to indexed assignment statements that the return
> type doesn't matter because there is no return type.

My proposal was 'limited' to it, with some exceptions i.e. allowing copying.

> See http://en.wikipedia.org/wiki/Endian. On big-endian machines b[0..16],
> for example, would be the last two bytes of the memory range &b .. &b+4 in
> reverse order and for little endian machines is the first two bytes in
> incresing order. For longs and shorts it would behave similarly.

I understand big/little endian. I don't understand why it's a problem.
Either:
1 - the compiler handles the big/little endian nature of the bits for us, guaranteeing a certain ordering
2 - the compiler does nothing and we have to handle/understand it ourselves.

If #1 it makes bit twiddling very simple to use and understand, don't you think?
If #2 and the feature is limited to assignment and copying then (see my next response)

> The type bit[] is packed into compiler-dependent chunks in whatever ways it wants. I imagine it would take some non-trivial changes to bit[] to support slicing non-int sized types on big-endian machines.

I understand, I think. However, if it's restricted to assignments and copying it simplifies things a bit, the compiler already has to know how to access the bits, all that is added is the ability to set them or copy them.

I'm saying, slicing without copying or assigning is not allowed, thus the bit[] type does not need to handle the packing of the bits. Instead on assignment the compiler handles it by assigning to them as it finds them. When copying it makes new data, copying from the old data and no changes are required to bit[] to handle this case.

>> I think  we do want to restrict it to bit boundaries or require a copy
>> (anything  else seems quite complicated, though the compiler is the best
>> place to  handle that, if it was desired)
>
> I'm not sure what exactly you are referring to. Which bit boundaries and
> copying do you mean?

Replace "bit" with "byte" above. I mean:

uint a;
bit[] b = a[2..12];

would not be possible because the slice crosses a byte boundary. but, a copy or assignment would be fine (reasons above) eg.

uint a;
bit[] b;

b[] = a[2..12];
a[2..12] = 1;

> By the way, I'm guessing as to exactly what the
> proposal is. My impression is that the proposal is to slice lvalues of
> numeric type to obtain bit[].

Correct.

> The only numeric type I can imagine it working for is the underlying numeric type used by bit[] (on big endian machines). For little endian machines bit[] can be used for any slice that starts at a multiple of the underlying bit-packing unit (eg int).

This is exactly the 'difference' I am suggesting we remove. See option #1 above.

>>> It's simpler
>>
>> I disagree. After years of experience using & and | is easy (perhaps
>> 'simple'), but, to a begginer it's not at all.
>
> Given that using bit[] will require lots of special cases to explain (see
> above)

No, I am trying to remove them, see above.

>>> (and well-defined) to use & and |.
>>
>> In C and other languages, yes. In D, c'mon we have bit[], surely it can
>> make bit twiddling really nice and easy. It seems bizarre to say the least
>> that we're not using bit[] for bit twiddling but instead using old
>> techniques which are both harder to understand and use (until you're
>> proficient with them).
>
> I think a more detailed proposal would help show the trade-off and true
> impact of trying to extend bit[] to be used as a replacement for &|.

Ok. I must admit I haven't tried to formalise this idea as yet.

> I don't
> think it's a trivial as you assume. I view bit[] as only being a packed
> array of true/false values (ala Pascal and C++). The exact packing behavior
> is compiler-dependent.

I didn't first consider this but I don't see this as a problem, unless I am mistaken above.

> Other languages have bit arrays - I'm thinking specifically of Pascal's
> packed arrays and STL's bit vectors but there could be others, too. I'm not aware of any that try to use bit arrays to do bit twiddling. They are meant to be memory efficient arrays of true/false values and that's it.

So they're not 'bit' arrays but 'bool' arrays ;)
The argument "it hasn't been done before, it's a bad idea" is weak.

Regan

> I'm saying, slicing without copying or assigning is not allowed, thus the bit[] type does not need to handle the packing of the bits. Instead on assignment the compiler handles it by assigning to them as it finds them. When copying it makes new data, copying from the old data and no changes are required to bit[] to handle this case.

So I guess the proposal is:
 Statements of the form "<bit array slice> = var[a .. b];" or "var[a .. b] =
<bit array slice>;" or "var[a .. b] = <bit-value>;" are allowed when var is
an lvalue of numeric type. Restrictions on a and b to byte-boundaries may
apply. No other use of slicing a numeric type is allowed. The type of "var[a
.. b]" is not defined.

Only allowing slicing in copying or assignment contexts is too restricted IMHO. I agree if that's the proposal then the compiler can figure out the endianness and other issues. Given that such constructs can easily be implemented using functions I don't think it's worth the weight of adding special cases to the language.

>> Other languages have bit arrays - I'm thinking specifically of Pascal's packed arrays and STL's bit vectors but there could be others, too. I'm not aware of any that try to use bit arrays to do bit twiddling. They are meant to be memory efficient arrays of true/false values and that's it.
>
> So they're not 'bit' arrays but 'bool' arrays ;)
> The argument "it hasn't been done before, it's a bad idea" is weak.

I mentioned other languages because
1) bit arrays are old concepts
2) other languages don't use them for bit twiddling
3) D is alot like those other languages and I'm sure people have tried using
bit arrays for bit twiddling in those other languages, too. It's not an
unusual request to have bit[] help with twiddling.

On Sun, 21 Aug 2005 20:20:19 -0400, Ben Hinkle <ben.hinkle@gmail.com> wrote:
>> I'm saying, slicing without copying or assigning is not allowed, thus the
>> bit[] type does not need to handle the packing of the bits. Instead on
>> assignment the compiler handles it by assigning to them as it finds them.
>> When copying it makes new data, copying from the old data and no changes
>> are required to bit[] to handle this case.
>
> So I guess the proposal is:
>  Statements of the form "<bit array slice> = var[a .. b];" or "var[a .. b] = <bit array slice>;" or "var[a .. b] = <bit-value>;" are allowed when var is an lvalue of numeric type.

Yes.

> Restrictions on a and b to byte-boundaries may
> apply.

Assuming "<bit array slice>" above means "b[x..y]" (or "b[]") and not simply "b" (reference to bit array) then, no. There need not be any restriction to byte-boundaries.

> No other use of slicing a numeric type is allowed. The type of "var[a .. b]" is not defined.

Correct. Except that this type is implicitly castable to a <bit array slice>, eg.

b[] = var[a..b];
b[a..b] = var[a..b];

> Only allowing slicing in copying or assignment contexts is too restricted
> IMHO. I agree if that's the proposal then the compiler can figure out the
> endianness and other issues. Given that such constructs can easily be
> implemented using functions I don't think it's worth the weight of adding
> special cases to the language.

You're entitled to your own opinion, mine is:

It wouldn't be a "special case", it would be the "standard"/"best way" to manipulate bits in the general case. It would be _much_ nicer than using functions as it would be allow shorter more concise yet more descriptive code.

For example, a challenge:

What would the following code look like using your proposed functions?

//take certain bits from 3 different variables, build a new variable
uint newVar;
ubyte varOne;
ushort varTwo;
uint  varThree;

newVar[0..8] = varOne[3..11];
newVar[8..16] = varTwo[5..13];
newVar[16..32] = varThree[7..23];

I expect the code above to:
 - look nicer
 - be clearer
 - be more concise

than anything you can come up with. However I am wary about you being able to come up with something ;)

>>> Other languages have bit arrays - I'm thinking specifically of Pascal's
>>> packed arrays and STL's bit vectors but there could be others, too. I'm
>>> not aware of any that try to use bit arrays to do bit twiddling. They
>>> are meant to be memory efficient arrays of true/false values and that's
>>> it.
>>
>> So they're not 'bit' arrays but 'bool' arrays ;)
>> The argument "it hasn't been done before, it's a bad idea" is weak.
>
> I mentioned other languages because
> 1) bit arrays are old concepts
> 2) other languages don't use them for bit twiddling
> 3) D is alot like those other languages and I'm sure people have tried using
> bit arrays for bit twiddling in those other languages, too. It's not an
> unusual request to have bit[] help with twiddling.

Sure, but it's still a weak argument IMO.

Regan

>> Only allowing slicing in copying or assignment contexts is too restricted IMHO. I agree if that's the proposal then the compiler can figure out the endianness and other issues. Given that such constructs can easily be implemented using functions I don't think it's worth the weight of adding special cases to the language.
>
> You're entitled to your own opinion, mine is:
>
> It wouldn't be a "special case", it would be the "standard"/"best way" to manipulate bits in the general case.

I say special case because it would be the only construct in D that takes an expression (the indexing and assignment expression) and forces them to appear in their special statement form. Other expressions in D have types and can be assigned to variables and passed to functions or used as subexpressions. Compared to other expressions and statements in D it is very special.

> It would be _much_ nicer than using  functions as it would be allow shorter more concise yet more descriptive  code.
>
> For example, a challenge:
>
> What would the following code look like using your proposed functions?
>
> //take certain bits from 3 different variables, build a new variable
> uint newVar;
> ubyte varOne;
> ushort varTwo;
> uint  varThree;
>
> newVar[0..8] = varOne[3..11];
> newVar[8..16] = varTwo[5..13];
> newVar[16..32] = varThree[7..23];

The proposal written above didn't mention copying one var[a..b] to another var[a..b] so that's another case to add.

> I expect the code above to:
>  - look nicer
>  - be clearer
>  - be more concise

sigh. There's more to adding features than making a small set of user code "more concise".

> than anything you can come up with. However I am wary about you being able to come up with something ;)

The most obvious API that comes to mind using a single function is
  copybits(newVar,0,8,varOne,3,11);
The newVar is 'inout'. The varOne is 'in'. Seems like a trivial rewrite of
your syntax to me. The benefits of these functions are:
1) no special case
2) users can immediately use them without having to learn a special syntax
3) no confusion with mistaking newVar and varOne with an array

On Mon, 22 Aug 2005 13:14:39 +1200, Regan Heath wrote:

[snip]

> What would the following code look like using your proposed functions?
> 
> //take certain bits from 3 different variables, build a new variable
> uint newVar;
> ubyte varOne;
> ushort varTwo;
> uint  varThree;
> 
> newVar[0..8] = varOne[3..11];
> newVar[8..16] = varTwo[5..13];
> newVar[16..32] = varThree[7..23];
> 
> I expect the code above to:
>   - look nicer
>   - be clearer
>   - be more concise
> 
> than anything you can come up with. However I am wary about you being able to come up with something ;)

My issue with this idea is that just by looking at 'newVar[0..8]' it gives the impression that newVar is an array. And I don't mean an array of bits ;-) Of course all data ultimately is stored as array(s) of bits so this syntax is a tad misleading.

I can see a point to the argument that it would be useful to have the compiler help coders who need to access variables at the bit level. But it would need a different syntax to avoid ambiguities.

Seeing that all data is ultimately a set of bits, and is thus intrinsic to the variable, maybe an in-built property of '.bits' might be a useful idea.

 newVar.bits[0..8] = varOne.bits[3..11];
 newVar.bits[8..16] = varTwo.bits[5..13];
 newVar.bits[16..32] = varThree.bits[7..23];

And the compiler can do the Endian transformations on the coder's behalf. D would just define that the .bits property is always used as if the data is really stored as Big Endian (ie. Motorola/IBM style and not Intel/VAX style).

-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
22/08/2005 11:51:58 AM