efficient way to split ONE bitstream according to many masks?

Question

I am experimenting to make a Inverse Multiplexer, which could split one bitstream into many according to some masks.

Here's the idea example

This is a 24 bit stream, each letter represents 1 bit:

abcdefgh ijklmnop qrstuvwx

Given three masks, every mask has no bit in common, if & together they are [1,1,1,1,1,1,1,1]

[1, 1, 0, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 1, 1]
[0, 0, 0, 1, 0, 1, 0, 0]

apply these masks to the stream like this

stream1 = ab__e___ ij__m___ qr__u___
stream2 = __c___gh __k___op __s___wx
stream3 = ___d_f__ ___l_n__ ___t_v__

So the original bitstream is splitted into three bitstreams like this:

stream1 = abeijmqru
stream2 = cghkopswx
stream3 = dflntv

The above is just an example, I need to apply arbitrary number of masks to a given bitstream. The masks are guranteed, between every each other, has OR result of ZEROs. Aply AND to all the masks has the result of ONEs. All masks are the same length.

I wrote a dumb version to brute force the idea which is basically shifting bits one by one in a loop. Thought it's certainly not efficient.

I looked into this http://graphics.stanford.edu/~seander/bithacks.html

No clue. Anyone has better idea how to improve this? (On x86 machines)

It would be very helpful if you'll explain what you're trying to achieve, improve what ? How will those masks be used ? Further, you're discussing bit-mask but the example contains characters (each one is represented by 16 bits). What programming language are you using ? — Nir Alfasi, Nov 28 '13 at 04:12
@alfasin is my personal programming experiment to make a [Inverse Multiplexer](http://en.wikipedia.org/wiki/Inverse_multiplexer). I added it to the question. — est, Nov 28 '13 at 04:13
@alfasin I get the impression that the letters are just designators for each bit — Peter Gibson, Nov 28 '13 at 04:21
@PeterGibson bad idea - if you're dealing with bits & bytes stick to it otherwise it's just confusing. — Nir Alfasi, Nov 28 '13 at 04:23
@alfasin I think it's a good way to illustrate the bit positions in the masks, but it could be explained more clearly — Peter Gibson, Nov 28 '13 at 04:25
Yes, @PeterGibson is correct. I'll improve my question. Sorry for my bad expressions. — est, Nov 28 '13 at 04:25

score 1 · Answer 1 · answered Nov 28 '13 at 04:31

If each bit only maps to one output stream, I think it would make more sense to define which output streams the bits are assigned to, rather than using masks. For instance, your example masks

[1, 1, 0, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 1, 1]
[0, 0, 0, 1, 0, 1, 0, 0]

Would instead be represented as the output stream to assign the current bit to

[0, 0, 1, 2, 0, 2, 1, 1]

And some psuedocode to tie it together

stream_order = [0, 0, 1, 2, 0, 2, 1, 1]
index = 0
for bit in input_stream:
    n = stream_order[index]
    output_streams[n].push(bit)
    index++
    index %= len(stream_order)

that's very similar to how I did it, however, the `output_streams[n].push(bit)` could be improved by some clever bit tricks IMHO. — est, Nov 28 '13 at 04:38

score 1 · Accepted Answer · edited May 23 '17 at 11:49

I suppose since you only ever have a bit corresponding to a single "stream", then you can shift all of them at the same time and see "what stream this belongs to". This will allow for a modest amount of parallel implementation - although it will depend a bit on the architecture and the size of the masks how efficient this will be. It will also depend on how often you want to do this - a certain amount of pre-computation would make subsequent runs more efficient. It does sound a bit brute-force; may not be better than what you already did.

There is, of course, the lovely question Extracting bits with a single multiplication (to which I wrote the accepted answer…) that suggests a way to extract certain bits from a larger number with a single multiplication. This method does suffer from the disadvantage that you cannot do this for any number of set bits - there needs to be a number of spaces in between.

This can be resolved, in principle, by repeating the process two or more times, and applying additional masks in between. Let's see how this would work for just the first mask in your problem above.

mask1 = 11001000
num =   abcdefgh
temp = num & mask1 = ab..e...
magic = 4 + 1
answer =     ab..e... 
           ab..e..... + 
           ------------
           ababe.e...
mask2 =    0011100000
ans & mask = abe.....

This puts the three digits you want into the top three spots with mask-multiply-mask (3 operations). Not terribly efficient for an eight bit number; but you can expand this to a 32 bit number and then it starts to look more interesting.

after some serious pondering your answer is definitely the best! The multiplication trick ROCKS! Thanks! — est, Nov 29 '13 at 03:38

efficient way to split ONE bitstream according to many masks?

2 Answers2