Re^5: Efficient 7bit compression

[Roy Johnson]

Are you talking about shrinking in place, so you don't have the overhead of having the compressed and uncompressed strings in memory at the same time?

my $str =<<'EOS';
There once was a man from Nantucket,
Who kept all his cash in a bucket.
His daughter, named Nan,
Ran off with a man.
And as for the bucket, Nantucket.
EOS

sub shrink_in_place {
    for (my $i=0; $i<length($_[0]); $i+=7) {
        for (substr($_[0], $i, 8)) {
            $_ = pack('B*', grep s/.(.{7})/$1/g, unpack('B*', $_));
        }
    }
}

sub grow_in_place {
    for (my $i=0; $i<length($_[0]); $i+=8) {
        for (substr($_[0], $i, 7)) {
            $_ = pack('B*', grep s/(.{7})/0$1/g, unpack('B*', $_));
        }
    }
}

print "$str";
printf "Length is %d\n", length($str);
shrink_in_place($str);
printf "Shrunk length is %d\n", length($str);
grow_in_place($str);
print "Restored: $str";

[Limbic~Region]

Roy Johnson,
Are you talking about shrinking in place, so you don't have the overhead of having the compressed and uncompressed strings in memory at the same time?

No - but neat. What I was talking about was with regards to $unpacked = ''. Instead, pre-size it and use the 4 arg substr to fill it up instead of growing it each time. As I said before, I didn't get my vec() approach to work but I would have also been able to do this in the shrink() sub as well.

[Roy Johnson]

I've been playing with it, and I see the problem. vec is horrible, because it reverses everything. When you pack them together by sevens and take them apart by eights, it's a mess to try to get everything reversed.

Here's a version with pre-sized return strings, using vec (but there's no need for substr). No packing, so no reversed-bits madness to deal with.

sub shrink {
    my $shrunk = "\0" x (length($_[0]) * 7/8);
    my $bit = 0;
    for my $orig_bit (0..(8*length($_[0])-1)) {
    next if $orig_bit % 8 == 7;
    vec($shrunk, $bit++, 1) = vec($_[0], $orig_bit, 1);
    }
    $shrunk;
}

sub grow {
    my $grown = "\0" x (length($_[0]) * 8/7);
    my $orig_bit = 0;
    for my $bit (0..(8*length($_[0])-1)) {
    vec($grown, $orig_bit++, 1) = vec($_[0], $bit, 1);
    vec($grown, $orig_bit++, 1) = 0 if $orig_bit % 8 == 7;
    }
    $grown;
}