In article <chhns7$1c3p$1@digitaldaemon.com>, Ben Hinkle says...

>I want to be able to cast pointers to void* and back without losing information.

That's an intriguing one. According to "The C Programming Language" (K&R), the
rules for C are:

(1)It is guaranteed that a pointer to an object may be converted to a pointer to an object whose type requires less or equally strict storage alignment and back again without change. And:

(2) A pointer may be converted to type void * and back again without change.

Note that the first rule implies that converting char* -> int* -> char* is NOT safe, because when you go from char* to int*, the C compiler is permitted to zero the low order bits in order to meet operating system specific alignment requirements. The second rule is true in C, because void* has the same alignment requirements as char* (char is the smallest addressable unit).

But the bit makes things different. In D, given that bit requires less strict storage alignment than byte, we must choose between either:

(1) bit* -> void* -> bit* is NOT safe, or
(2) void* is implemented with a bit offset

Doesn't the bit make life interesting?

Arcane Jill

In article <chhrke$1dk2$1@digitaldaemon.com>, Ilya Minkov says...
>
>Ben Hinkle schrieb:
>
>> hmm - a pointer to bits should have the same size as pointers to anything else IMO. I want to be able to cast pointers to void* and back without losing information.
>
>Why do you want to be able to cast it to void*?

For any type Foo a pointer to Foo (Foo*) should be castable to void*. It's probably just the word "pointer" that tells me it has a certain behavior. A "reference" to a bit in a bit array can be any size and for that I wouldn't expect to be able to cast to void*. So maybe my issue is just with using the word "pointer" in this context.

>If you mean it for containers, then i'll have to think it over what kinds of solutions are possible. One of them would be that a cast to void* would new a bit pointer on the heap and copy the original one there, and return a void* which points to it. A cast back would return a bit pointer struct. The leftover place in the struct can be filled with checksum, which can be generated on one cast and checked on another, just to try to make sure that it's not random data. A garbage solution. :>
>
>There is a problem with "walking" such a void*, but you cannot safely walk a pointer if you don't know the size of a type. It looks very differently with void[], which starts to be a real problem.

I don't follow. The size in question isn't the size of the thing being pointed to - it's the size of the pointer itself.

>For templates, a separate solution can be figured out. I have to think over exactly how much trouble it is causing. Perhaps really much.
>
>> Pascal had bit arrays (you put the word "packed" in front of the
>> declaration) and they seemed to work fine back when I used Pascal. I don't know
>> if I ever tried taking the address of a packed array in Pascal, though.
>
>Oh, was it long ago that i used Delphi. If one declares a packed boolean array, can one take adress of a single element of it? I don't know any longer and don't have Delphi to test here. Perhaps Carlos can test it. And then whether it can be converted to a byte pointer is another question.

Maybe a separate type really is needed to distinguish between packed arrays of bits and unpacked arrays of bits. Something like "unpackedbit". Also we can make bool an alias for "unpackedbit" instead of regular packable "bit". That way arrays of bools don't surprise people used to bools as bytes.

>
>-eye

Ben; why is there a need for a bit[] in the first place? And why the need for a native bit pointer? One can easily put together a BitSet class, which will take care of the required functionality. It could even support array semantics, and perhaps even expose a pseudo-pointer (with the bit offset). Perhaps the thing to do is write one, stick it into MinTL, and put an end to all this 'debate' ?

I just don't understand why BitSet needs to be a built-in, primitive type. Can you enlighten me, please?



"Ben Hinkle" <Ben_member@pathlink.com> wrote in message
news:chhtv8$1edk$1@digitaldaemon.com...
In article <chhrke$1dk2$1@digitaldaemon.com>, Ilya Minkov says...
>
>Ben Hinkle schrieb:
>
>> hmm - a pointer to bits should have the same size as pointers to anything
else
>> IMO. I want to be able to cast pointers to void* and back without losing information.
>
>Why do you want to be able to cast it to void*?

For any type Foo a pointer to Foo (Foo*) should be castable to void*. It's probably just the word "pointer" that tells me it has a certain behavior. A "reference" to a bit in a bit array can be any size and for that I wouldn't expect to be able to cast to void*. So maybe my issue is just with using the word "pointer" in this context.

>If you mean it for containers, then i'll have to think it over what
>kinds of solutions are possible. One of them would be that a cast to
>void* would new a bit pointer on the heap and copy the original one
>there, and return a void* which points to it. A cast back would return a
>bit pointer struct. The leftover place in the struct can be filled with
>checksum, which can be generated on one cast and checked on another,
>just to try to make sure that it's not random data. A garbage solution. :>
>
>There is a problem with "walking" such a void*, but you cannot safely walk a pointer if you don't know the size of a type. It looks very differently with void[], which starts to be a real problem.

I don't follow. The size in question isn't the size of the thing being
pointed
to - it's the size of the pointer itself.

>For templates, a separate solution can be figured out. I have to think over exactly how much trouble it is causing. Perhaps really much.
>
>> Pascal had bit arrays (you put the word "packed" in front of the declaration) and they seemed to work fine back when I used Pascal. I
don't know
>> if I ever tried taking the address of a packed array in Pascal, though.
>
>Oh, was it long ago that i used Delphi. If one declares a packed boolean
>array, can one take adress of a single element of it? I don't know any
>longer and don't have Delphi to test here. Perhaps Carlos can test it.
>And then whether it can be converted to a byte pointer is another question.

Maybe a separate type really is needed to distinguish between packed arrays
of
bits and unpacked arrays of bits. Something like "unpackedbit". Also we can
make
bool an alias for "unpackedbit" instead of regular packable "bit". That way
arrays of bools don't surprise people used to bools as bytes.

>
>-eye

In article <chi18u$1fhn$1@digitaldaemon.com>, antiAlias says...
>
>Ben; why is there a need for a bit[] in the first place? And why the need for a native bit pointer? One can easily put together a BitSet class, which will take care of the required functionality. It could even support array semantics, and perhaps even expose a pseudo-pointer (with the bit offset). Perhaps the thing to do is write one, stick it into MinTL, and put an end to all this 'debate' ?
>
>I just don't understand why BitSet needs to be a built-in, primitive type. Can you enlighten me, please?

I don't know. Walter probably decided to pack bit arrays without realizing all the side effects - after all if one wants unpacked "bit" arrays one can explicitly use bytes. I used a bit array in D a long time ago and I don't even remember exactly what for - I think it had to do with casting an int to a bit array or something. They are cute but it looks like they cause lots of feather ruffling. Personally if supporting them in the D language gets too messy then I agree they should be removed and moved to the/a library.

As I mentioned before I think the reason people actually care is because of bool. A packed bool array seems less useful than a packed bit array - if you get my meaning.

>
>"Ben Hinkle" <Ben_member@pathlink.com> wrote in message
>news:chhtv8$1edk$1@digitaldaemon.com...
>In article <chhrke$1dk2$1@digitaldaemon.com>, Ilya Minkov says...
>>
>>Ben Hinkle schrieb:
>>
>>> hmm - a pointer to bits should have the same size as pointers to anything
>else
>>> IMO. I want to be able to cast pointers to void* and back without losing information.
>>
>>Why do you want to be able to cast it to void*?
>
>For any type Foo a pointer to Foo (Foo*) should be castable to void*. It's probably just the word "pointer" that tells me it has a certain behavior. A "reference" to a bit in a bit array can be any size and for that I wouldn't expect to be able to cast to void*. So maybe my issue is just with using the word "pointer" in this context.
>
>>If you mean it for containers, then i'll have to think it over what
>>kinds of solutions are possible. One of them would be that a cast to
>>void* would new a bit pointer on the heap and copy the original one
>>there, and return a void* which points to it. A cast back would return a
>>bit pointer struct. The leftover place in the struct can be filled with
>>checksum, which can be generated on one cast and checked on another,
>>just to try to make sure that it's not random data. A garbage solution. :>
>>
>>There is a problem with "walking" such a void*, but you cannot safely walk a pointer if you don't know the size of a type. It looks very differently with void[], which starts to be a real problem.
>
>I don't follow. The size in question isn't the size of the thing being
>pointed
>to - it's the size of the pointer itself.
>
>>For templates, a separate solution can be figured out. I have to think over exactly how much trouble it is causing. Perhaps really much.
>>
>>> Pascal had bit arrays (you put the word "packed" in front of the declaration) and they seemed to work fine back when I used Pascal. I
>don't know
>>> if I ever tried taking the address of a packed array in Pascal, though.
>>
>>Oh, was it long ago that i used Delphi. If one declares a packed boolean
>>array, can one take adress of a single element of it? I don't know any
>>longer and don't have Delphi to test here. Perhaps Carlos can test it.
>>And then whether it can be converted to a byte pointer is another question.
>
>Maybe a separate type really is needed to distinguish between packed arrays
>of
>bits and unpacked arrays of bits. Something like "unpackedbit". Also we can
>make
>bool an alias for "unpackedbit" instead of regular packable "bit". That way
>arrays of bools don't surprise people used to bools as bytes.
>
>>
>>-eye
>
>
>

"Ben Hinkle" <Ben_member@pathlink.com>
As I mentioned before I think the reason people actually care is because of
bool. A packed bool array seems less useful than a packed bit array - if you
get
my meaning.

===============

No question that BitSet functionality is very useful, if that's what you mean. Unfortunately, bit[] does not support operations like OR, XOR, AND, etc.  This relegates the usefulness of bit[] to, uhhh, somewhere dark. In comparison, a BitSet class would be all sweetness and light :-)

"Ilya Minkov" <minkov@cs.tum.edu> escribió en el mensaje
news:chhrke$1dk2$1@digitaldaemon.com
| Oh, was it long ago that i used Delphi. If one declares a packed boolean
| array, can one take adress of a single element of it? I don't know any
| longer and don't have Delphi to test here. Perhaps Carlos can test it.
| And then whether it can be converted to a byte pointer is another question.
|
| -eye

(warning: Delphi code follows)

////////////////////////////////
program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  arr     : packed array of boolean;
  element : ^boolean;
  i       : integer;

begin
  setlength(arr,8);
  element := @ arr[2];
  arr[2] := true;
  writeln(element^);
  for i := 0 to 7 do
    writeln(arr[i]);
end.
////////////////////////////////

Outputs:
TRUE
FALSE
FALSE
TRUE
FALSE
FALSE
FALSE
FALSE
FALSE

So, unless I didn't understand something, it is possible.

-----------------------
Carlos Santander Bernal

Arcane Jill wrote:
> But the bit makes things different. In D, given that bit requires less strict
> storage alignment than byte, we must choose between either:
> 
> (1) bit* -> void* -> bit* is NOT safe, or
> (2) void* is implemented with a bit offset
How about device dependency? i.e. bit* -> void* -> bit* is valid only on bit-addressable machines.
I'm new to D, but are function pointers compatible with void* ? If not, then bit* (and nybble* and tayste*) needn't be either - or void* should be extended to hold function pointers and represent sub-byte addressing.
> 
> Doesn't the bit make life interesting?
> 
And how!

--Joel

On Mon, 23 Aug 2004 16:56:49 +1000, Matthew wrote:

> "Ivan Senji" <ivan.senji@public.srce.hr> wrote in message news:cgc1s6$1vdk$1@digitaldaemon.com...
[snip]
> - drop the bit type

I suspect that there is some ambiguity loaded in the use of the term 'bit'.

To me, a bit is an integer that can hold only one of two possible values - zero and one. (And a bool is almost the same except that its not a number; it holds either True or False.)

So an array of bits is a vector of integers that can each hold only one of two values, and this can be implemented in a multitude of ways.

In addition, there is a real need to be able to describe the physical layout of RAM, and as such we often superimpose a bit array (in language terms) over a RAM area to access the RAM bits. However a 'bit' as a programming concept is not necessarily the same as a physical RAM bit.

So in D, it would be useful if we could have a conceptual bit type - used to implement programming concepts of switches, etc..; and a physical bit type - used to describe RAM layouts. We could then workout a method of notating the address of RAM bits based on physical RAM (byte) addresses. Addressing conceptual bits via standard vector addressing would remain the same.

  cbit v[17];

  v[5] = 1;  -- Sets the 6th conceptual bit to 1.


And something like this could describe the layout of a 4-byte (32-bit) area
of RAM...

  struct X
  {
     pbit a[2];
     pbit b[5];
     align byte;
     byte2 c;
     byte d;
  }

Or am I missing something again?

-- 
Derek
Melbourne, Australia
7/Sep/04 9:22:18 AM

In article <chisup$1s00$1@digitaldaemon.com>, Derek Parnell says...
>
>On Mon, 23 Aug 2004 16:56:49 +1000, Matthew wrote:
>
>> "Ivan Senji" <ivan.senji@public.srce.hr> wrote in message news:cgc1s6$1vdk$1@digitaldaemon.com...
>[snip]
>> - drop the bit type
>
>I suspect that there is some ambiguity loaded in the use of the term 'bit'.
>
>To me, a bit is an integer that can hold only one of two possible values - zero and one. (And a bool is almost the same except that its not a number; it holds either True or False.)
>
>So an array of bits is a vector of integers that can each hold only one of two values, and this can be implemented in a multitude of ways.
>
>In addition, there is a real need to be able to describe the physical layout of RAM, and as such we often superimpose a bit array (in language terms) over a RAM area to access the RAM bits. However a 'bit' as a programming concept is not necessarily the same as a physical RAM bit.
>
>So in D, it would be useful if we could have a conceptual bit type - used to implement programming concepts of switches, etc..; and a physical bit type - used to describe RAM layouts. We could then workout a method of notating the address of RAM bits based on physical RAM (byte) addresses. Addressing conceptual bits via standard vector addressing would remain the same.
>
>  cbit v[17];
>
>  v[5] = 1;  -- Sets the 6th conceptual bit to 1.
>
>
>And something like this could describe the layout of a 4-byte (32-bit) area
>of RAM...
>
>  struct X
>  {
>     pbit a[2];
>     pbit b[5];
>     align byte;
>     byte2 c;
>     byte d;
>  }
>
>Or am I missing something again?

There may be some confusion if bits are packed across adjacent bit arrays.  It could also lead so some odd problems or compiler issues if multithreading is thrown into the picture (imagine a and b being protected by separate locks though a[0] and b[0] occupy the same byte in memory).  I'm pretty sure that D has alignment specifiers so we don't really need bit arrays for this.  The contention is around the fact that some believe that arrays of anything should behave the same.  That is, that the address of an element can be taken, etc. For obvious reasons, this isn't easy if bit arrays are packed :)

I think that things should either stay the way they are, or 'bit' should be replaced with 'bool' and always have a 1-byte storage value.  As others have said, it's easy enough to create a packed bitset in a library.


Sean

On Tue, 7 Sep 2004 03:08:20 +0000 (UTC), Sean Kelly wrote:

> In article <chisup$1s00$1@digitaldaemon.com>, Derek Parnell says...
>>
>>On Mon, 23 Aug 2004 16:56:49 +1000, Matthew wrote:
>>
>>> "Ivan Senji" <ivan.senji@public.srce.hr> wrote in message news:cgc1s6$1vdk$1@digitaldaemon.com...
>>[snip]
>>> - drop the bit type
>>
>>I suspect that there is some ambiguity loaded in the use of the term 'bit'.
>>
>>To me, a bit is an integer that can hold only one of two possible values - zero and one. (And a bool is almost the same except that its not a number; it holds either True or False.)
>>
>>So an array of bits is a vector of integers that can each hold only one of two values, and this can be implemented in a multitude of ways.
>>
>>In addition, there is a real need to be able to describe the physical layout of RAM, and as such we often superimpose a bit array (in language terms) over a RAM area to access the RAM bits. However a 'bit' as a programming concept is not necessarily the same as a physical RAM bit.
>>
>>So in D, it would be useful if we could have a conceptual bit type - used to implement programming concepts of switches, etc..; and a physical bit type - used to describe RAM layouts. We could then workout a method of notating the address of RAM bits based on physical RAM (byte) addresses. Addressing conceptual bits via standard vector addressing would remain the same.
>>
>>  cbit v[17];
>>
>>  v[5] = 1;  -- Sets the 6th conceptual bit to 1.
>>
>>
>>And something like this could describe the layout of a 4-byte (32-bit) area
>>of RAM...
>>
>>  struct X
>>  {
>>     pbit a[2];
>>     pbit b[5];
>>     align byte;
>>     byte2 c;
>>     byte d;
>>  }
>>
>>Or am I missing something again?

I suspect that either I don't understand you, or that you don't understand me. ;-)

> There may be some confusion if bits are packed across adjacent bit arrays.

Are you talking about physical RAM layouts or conceptual bit arrays? They are not the same thing.

All the 'struct' above is saying is ...

   'a' is the first two bits in RAM.
   'b' is the next 5 bits in RAM.
   Then align to the next byte boundary.
   'c' is a single 2-byte value.
   'd  is a single 1-byte value.

So how can one say "if bits are packed across adjacent bit arrays"? Do you mean if the last bit in 'a' and 'the first bit in 'b' (thus the 3rd and 4th bit in the structure) are accessed as if they were a single bit array?

Or are you talking about conceptual bits in arrays? If so, it makes as much sense as saying "but what if integers are packed across integer arrays?". There is no guarantee that such arrays are even adjacently stored in RAM?

>  It
> could also lead so some odd problems or compiler issues if multithreading is
> thrown into the picture (imagine a and b being protected by separate locks
> though a[0] and b[0] occupy the same byte in memory).

What are you on about???  The struct above is trying to say that these two bit arrays are *explicitly* not sharing the same RAM. If you are talking about conceptual bit arrays, then the same problem also exists for arrays of any sort of data type, not just bits.

>  I'm pretty sure that D
> has alignment specifiers so we don't really need bit arrays for this.

It does?  How does one address the 3rd and 4th bits of a byte as if they were a single 2-bit integer or even a 2-bit array? I'd be pleased if you could show me example code for that. I'm not saying that one can't, but just that I haven't learned how to yet.

> The
> contention is around the fact that some believe that arrays of anything should
> behave the same.  That is, that the address of an element can be taken, etc.

Yep. Sounds like a good idea.

> For obvious reasons, this isn't easy if bit arrays are packed :)

If I declare 'a' as a bit array of 17 bits long, then doesn't a[5] refer to the 6th bit in that array?

<code>
 import std.stdio;
 bit[17] a;

 void main()
 {
    a[5] = 1;
    writef("%d\n",  a[5]);
    writef("%d\n",  a.length);
    writef("%d\n",  a.sizeof);
 }
</code>

Out is ...

 c:\temp>type test.d
 import std.stdio;
 bit[17] a;

 void main()
 {
    a[5] = 1;
    writef("%d\n",  a[5]);
    writef("%d\n",  a.length);
    writef("%d\n",  a.sizeof);
 }

 c:\temp>dmd test
 C:\DPARNELL\DMD\BIN\..\..\dm\bin\link.exe test,,,user32+kernel32/noi;

 c:\temp>test
 1
 17
 4

 c:\temp>


What am I misunderstanding?

> 
> I think that things should either stay the way they are, or 'bit' should be replaced with 'bool' and always have a 1-byte storage value.

But bits are numbers and bools are not numbers. Just like ints are numbers and chars are not numbers.

> As others have
> said, it's easy enough to create a packed bitset in a library.

What is a "packed bitset"? Maybe this is the term that I'm not understanding?

-- 
Derek
Melbourne, Australia
7/Sep/04 2:30:47 PM