www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - The bit[] slicing bugs revisited

reply Stewart Gordon <smjg_1998 yahoo.com> writes:
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.
May 25 2004
next sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
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.
May 27 2004
prev sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
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.
May 28 2004