Just pondering over an age-old bug or three

http://www.digitalmars.com/drn-bin/wwwnews?D/23535

I looked at some of the std.internal code last night, and found the function for copying bit arrays (whatever it was called).

However, it was based on the assumption that a bit[] is always byte aligned, and that the spare bits of the final byte really are unused. This is obviously nonsense if it's a slice staying in the loaf.

The basic problem seems to be that a bit array reference doesn't keep hold of a bit offset within the byte.  This claim is further supported by that (bit[]).size == 8, the same as arrays of other types.

We need two things to put things right:

1. An implementation of bit slicing that actually slices properly.  I can see two possibilities:
- Add a bit offset to every bit[].
- Make every bit[] slice a copy of the extracted data, to make sure it is byte-aligned.

Either way would increase the memory demand on bit arrays.  The second would only increase the demand if bit slicing is actually used, but the hit would be significant if large slices are taken.  A possibility would be to make an exception if the slice is known to be byte-aligned at compile time, but would the potential uncertainty be worth it?  Maybe it goes the same as for regular array slices that may be subsequently be resized: one shouldn't rely on it anyway....

Which idea would you choose, Walter?

2. An implementation of bit slice copying that gets the bit indexes right, and doesn't copy more than necessary at the expense of corrupting data just outside the slice.

Of course, a simple slice assignment, such as qwert[1..3] = yuiop[6..8], would obviously be optimised so that it doesn't have to create a byte-aligned copy of yuiop[6..8] first.

I suppose I could try and write some code to do this.  But having taken a look at the open front-end source, integrating the fixes into DMD is going to take more than it....

It appears that concatenation uses some of the same code that slicing uses, and so fixing these problems'll at least help to fix the concatenation problems as well.

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.

I've got an algorithm working to transfer bit slices with matching byte alignments, and I'm now beginning to work out the general case.

For that matter, what's going to happen when it comes to big-endian plaforms?  Is the bit order still going to match the byte order?

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.

I hereby donate some code to implement bit array slicing, slice assignment and concatenation.

This is only the functions themselves (along with some test code). You'll have to make the necessary changes to the compiler code (I'm still surprised this doesn't seem to be part of the front end) to hook up these new functions.

BTW copyBits is used in three ways:
- a driving function for the other functions
- implementation of a general assignment qwert[yuiop..asdfg] = hjkl,
where hjkl is an expression that evaluates to a bit[].
- an optimised (as far as optimisation goes) implementation of the
specific form qwert[yuiop..asdfg] = hjkl[zxcvb..nm].

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.