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

> In article <chisup$1s00$1@digitaldaemon.com>, Derek Parnell says...
[snip]

> That is, that the address of an element can be taken, etc.
> For obvious reasons, this isn't easy if bit arrays are packed :)

Of sorry, you mean the RAM address of a single physical bit array element. Yes, this is difficult, only because of the convention (solidified in silicon) that a RAM address refers to a byte (collection of 8-bits). If the convention however was that a RAM address referred to a bit, then it would not be a problem. I guess we would have to adopt the segment:offset addressing notation again ;-)

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

In article <chjepa$236l$1@digitaldaemon.com>, Derek Parnell says...
>
>>>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?

I mean that since a byte is the smallest addressable unit, you have two separate non-overlapping variables (ie. not aliased or sliced) that effectively address the same memory location.

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

True enough.  Though I assumed because you said "a 4-byte area of RAM" that in your example the data was stored adjacently.

>> 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 thought the above struct was requiring pbit a and pbit b to share the same byte.  Maybe not the same bits, but the memory location will be effectively identical.

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

Ooooh... I see what you're saying.  No, AFAIK D does not support anything like this natively.

>> 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?
..
>What am I misunderstanding?

I think we're on the same page, and that there's just been some miscommunication.  I was merely saying since modern computers don't support bit addressing, you've got to do some magic to deal with bit arrays and such--offsets, masks, etc.

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

The distinction shouldn't matter in most cases.  One could argue that everything is a number of a sequence of numbers, or that nothing is.  It depends on the level of abstraction you're talking about :)

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

I think it's a term used in the D documentation.  A bit array is "packed" in that it only uses 1 bit of RAM to represent 1 'bit' in D, so conceptually:

&a[0] == &a[1] == ... == &a[7]

Thus the compiler had to do some magic behind the scenes to allow a bit array to behave as if every bit were individually addressible.


Sean

In article <chjf8s$23fl$1@digitaldaemon.com>, Derek Parnell says...
>
>On Tue, 7 Sep 2004 03:08:20 +0000 (UTC), Sean Kelly wrote:
>
>> In article <chisup$1s00$1@digitaldaemon.com>, Derek Parnell says...
>[snip]
>
>> That is, that the address of an element can be taken, etc.
>> For obvious reasons, this isn't easy if bit arrays are packed :)
>
>Of sorry, you mean the RAM address of a single physical bit array element. Yes, this is difficult, only because of the convention (solidified in silicon) that a RAM address refers to a byte (collection of 8-bits). If the convention however was that a RAM address referred to a bit, then it would not be a problem. I guess we would have to adopt the segment:offset addressing notation again ;-)

Yup :)  IMO this is too messy just to support packed bit arrays, though I still like the idea in theory.


Sean

In article <chi86l$1iqg$1@digitaldaemon.com>, antiAlias says...

>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 :-)

There is /almost/ a BitSet class already. Please note the word "almost".

The class Int in Deimos represents an unlimited precision integer ... which could easily be interpretted as an unlimited size bit array. It already has those very functions - OR, XOR and AND. It also has bit test, bit set, and bit clear functions.

Unfortunately, it is not quite suitable for this purpose, because Ints are immutable. Setting a bit doesn't actually set a bit - instead, it makes a copy, and then sets a bit in the copy.

But it strikes me that with very little work, the bigint package could be made to do the job. In addition to the regular functions and operator overloads, the bigint package also provides low-level functions, and these are allowed to modify-in-place. It strikes me that with only minimal change, the package could easily implement those low-level functions in a high-level class with reference semantics (possibly called BitArray) with straightforward conversion to and from Int.

Anyone think that a good way to go?

Arcane Jill

"Arcane Jill" <Arcane_member@pathlink.com> wrote in message news:chjmpn$26al$1@digitaldaemon.com...
> In article <chi86l$1iqg$1@digitaldaemon.com>, antiAlias says...
>
> >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 :-)
>
> There is /almost/ a BitSet class already. Please note the word "almost".
>
> The class Int in Deimos represents an unlimited precision integer ...
which
> could easily be interpretted as an unlimited size bit array. It already
has
> those very functions - OR, XOR and AND. It also has bit test, bit set, and
bit
> clear functions.
>
> Unfortunately, it is not quite suitable for this purpose, because Ints are immutable. Setting a bit doesn't actually set a bit - instead, it makes a
copy,
> and then sets a bit in the copy.
>
> But it strikes me that with very little work, the bigint package could be
made
> to do the job. In addition to the regular functions and operator
overloads, the
> bigint package also provides low-level functions, and these are allowed to modify-in-place. It strikes me that with only minimal change, the package
could
> easily implement those low-level functions in a high-level class with
reference
> semantics (possibly called BitArray) with straightforward conversion to
and from
> Int.

Mine is called BitArray :)
Right now you can do things like:

float f = 3.141;
BitArray ba = new BitArray(f);
f[31] = 1;
//f is now -3.141

and you can have slices:
BitArray ba2 = ba[3..14];

for(int i=0; i<ba2.length; i++)
    ba2[i]=1;

now bits 3 .. 13 of f are set to 1.

But i am strugling at the moment with the way to make al the constructors with mixins.


> Anyone think that a good way to go?
>
> Arcane Jill
>
>