I'm using the same observation as BrowserUK, that the 0 padded nature of the regular rows allows us to simply or them together with the appropriate most significant bit.

ie. we just need to strip out the A and convert it into A0000000 - then we can or it with 0aaaaaaa to get Aaaaaaaa. I tried to make a perl implementation that makes it clear how that property is being used.

sub good_karma {
    my $raw_bytes = shift;
    my @raw_bytes = unpack 'C*', $raw_bytes; # unsigned char / 8 bits

    my @temp_bytes;
    my @resultant_bytes;

    my $i = 7;
    for my $byte (@raw_bytes) {
        $i++;
        if ($i == 8) {

            # this is one of those 'fill-in' rows, so dump
            # out the temp_bytes and re-init them
            push @resultant_bytes, @temp_bytes[1...7];

            # my unpack is a little rusty - this should result
            # in 8 array elements - each 1 or 0 (with the first always
+ 0)
            my @seven_bits = unpack 'bbbbbbbb', $byte;

            # shift the bit to the left. 8 <<'s might be faster
            $temp_bytes[$_] = $seven_bits[$_] * 128 for 1...7;

            # @temp_bytes is now (0, A0000000, B00000000, ...)

            # restart counter each time
            $i = 1;
        }

        # the 7 bit bytes are conveniently left 0 padded, so we
        # can just or the two parts together
        $temp_bytes[$i] |= $byte;
    }

    # handle final loop end-case
    push @resultant_bytes, @temp_bytes[1...$i];

    return join( '', @resultant_bytes );
}
[download]

As I said, my pack/unpack usage is a little rusty, so anyone should feel free to point out if I made a mistake.

The inner loop that is run 7/8 times has only four real operations (++, ==, |, =), so it should be pretty fast, but it wouldn't be hard to make a C version of the sub. It would probably be easier to wrap the C sub inside a perl sub that limited the size of the incoming bytes so you could use statically allocated buffers.

Update: realised I made a mistake with my pack, which forced a change in the if condition.

Update2: tested the unpack lines and found them wanting ;) It seems to me that the above should do what the comments suggest, but they don't actually seem to. Unless my testing is getting confused with automatic type conversion...

Update3: updated to handle the final non-8bit case.

Update4: I don't know what crack I was on yesterday - of course I meant or not and...