Optimize bit stream conversion

Monk::Thomas has asked for the wisdom of the Perl Monks concerning the following question:

Hello fellow monks

I have a sequence of bits that I want to convert back into actual values. I found a working algorithm, but there's probably an easier way to achieve what I want.

Input format: 0 and 1's in big-endian order. The number of bits may or may not equal multiples of 8.

Output format: Convert all groups of 8 into actual value, remaining bits must be kept. (Converted values can be any ASCII value, UTF-8 is not relevant.)

Sample script

#!/usr/bin/perl

use strict;
use warnings;

# store 'A' and 'B' as a bitstream
# (bit groups are stored big endian!)
my @bits = (
  1, 0, 0, 0, 0, 0, 1, 0,   # A / 0x41 / 0b01000001
  0, 1, 0, 0, 0, 0, 1, 0,   # B / 0x42 / 0b01000010
  1, 1, 0, 0, 1, 0, 1       # incomplete byte
);

my $data;
while (@bits >= 8) {
  # fetch bit group
  my @eightbits_be = splice @bits, 0, 8;
  # convert to little endian
  my @eightbits_le = reverse @eightbits_be;
  # generate binary representation 
  my $binary       = '0b' . join q{}, @eightbits_le;
  # convert binary representation into actual value
  my $value = chr oct $binary;

  $data .= $value;
}

printf "data: %s\n", $data;                # AB
printf "bits: %s\n", join ', ', @bits;     # 1, 1, 0, 0, 1, 0, 1
[download]

The generated/exprected output is:

data: AB
bits: 1, 1, 0, 0, 1, 0, 1

Comment on Optimize bit stream conversion Download Code

Replies are listed 'Best First'.
Re: Optimize bit stream conversion by choroba (Cardinal) on Jul 30, 2015 at 11:55 UTC
Use pack to get the bytes from the binary representation: `#!/usr/bin/perl use warnings; use strict; my @bits = ( 1, 0, 0, 0, 0, 0, 1, 0, # A / 0x41 / 0b01000001 0, 1, 0, 0, 0, 0, 1, 0, # B / 0x42 / 0b01000010 1, 1, 0, 0, 1, 0, 1 # incomplete byte ); my $string = join q(), @bits; my $incomplete = @bits % 8 \|\| -@bits; # The \|\| part handle +s complete bytes. print pack "b", substr $string, 0, -$incomplete; splice @bits, 0, -$incomplete; # Remove the process +ed part. print "\n@bits\n";` [download] Update:* handle complete bytes (new secret operator `%8\|\|-`). لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ	[reply] [d/l] [select]
Re^2: Optimize bit stream conversion by Monk::Thomas (Friar) on Jul 30, 2015 at 12:19 UTC
Ah! That's nice. I condensed it into: `#!/usr/bin/perl use strict; use warnings; # store 'A' and 'B' as a bitstream # (bit groups are stored big endian!) my @bits = ( 1, 0, 0, 0, 0, 0, 1, 0, # A / 0x41 / 0b01000001 0, 1, 0, 0, 0, 0, 1, 0, # B / 0x42 / 0b01000010 1, 1, 0, 0, 1, 0, 1 # incomplete byte ); my $data = pack "b", join q{}, splice @bits, 0, -(@bits % 8); printf "data: %s\n", $data; # AB printf "bits: %s\n", join ', ', @bits; # 1, 1, 0, 0, 1, 0, 1` [download] Update* Both variations do not convert properly if there actually isn't an incomplete byte. This version works: `# variant a) using floor() use POSIX; $data = pack 'b', join q{}, splice @bits, 0, POSIX::floor(@bits / 8) + 8; # variant b) using int $data = pack 'b', join q{}, splice @bits, 0, int(@bits / 8) 8;` [download]	[reply] [d/l] [select]
Re^3: Optimize bit stream conversion by choroba (Cardinal) on Jul 30, 2015 at 13:01 UTC
I didn't want to confuse you with a terse code. Updated the original node with a correct solution. لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ	[reply]
Re: Optimize bit stream conversion (Updated) by BrowserUk (Patriarch) on Jul 30, 2015 at 13:15 UTC
Probably little difference performance-wise on such a small dataset; but it could make a notable difference if the dataset is large: `#! perl -slw use strict; my @bits = ( 1, 0, 0, 0, 0, 0, 1, 0, # A / 0x41 / 0b01000001 0, 1, 0, 0, 0, 0, 1, 0, # B / 0x42 / 0b01000010 1, 1, 0, 0, 1, 0, 1 # incomplete byte ); my $data = ''; vec( $data, $_, 1 ) = shift@bits for 0 .. 8*int( @bits/8 ) -1; ## corr +ected for complete bytes print $data; print @bits; __END__ C:\test>1136846.pl AB 1100101` [download] Anyone got any experience of this phone's predecessor? With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I knew I was on the right track :) In the absence of evidence, opinion is indistinguishable from prejudice. I'm with torvalds on this Agile (and TDD) debunked I told'em LLVM was the way to go. But did they listen!	[reply] [d/l]