|
Re: unpacking 6-bit values
by jmcnamara (Monsignor) on Dec 10, 2010 at 11:05 UTC
|
In C or Perl I'd break the string into 3 byte chunk and extract the 6 bit bytes using bitmasks.
Something like this:
my $x = pack 'V', 1234567;
my $mask0to5 = 2**6 - 1;
my $mask6to11 = $mask0to5 << 6;
my $mask12to18 = $mask0to5 << 12;
my $mask18to24 = $mask0to5 << 18;
sub unpack_6bit_bytes {
my $byte_str = unpack 'V', $_[0];
my $byte_1 = $byte_str & $mask0to5;
my $byte_2 = ( $byte_str & $mask6to11 ) >> 6;
my $byte_3 = ( $byte_str & $mask12to18 ) >> 12;
my $byte_4 = ( $byte_str & $mask18to24 ) >> 18;
return ( $byte_1, $byte_2, $byte_3, $byte_4 );
}
print join ' ', unpack_6bit_bytes($x);
This is rough code to demonstrate the general method and only quickly tested.
--
John.
| [reply]
[d/l] |
Re: unpacking 6-bit values
by jethro (Monsignor) on Dec 10, 2010 at 10:41 UTC
|
How about unpacking in chunks of 3 byte resulting in 4 6-bit numbers.
Then create a few tables beforehand to remove the bit shift operations. For example the second 6-bit number would consist of the last two bit of the first byte and the first 4 bit of the second byte. So:
my @table2, @table3;
foreach my $i (0..256) {
$table2[$i]= $i >> 6;
$table3[$i]= $i << 2 & 63;
}
...
my $number[0]= $byte[0] & 63;
my $number[1]= $table2[$byte[0]] + $table3[$byte[1]];
...
UDPATE: Naturally it should be profiled whether the table lookup operation is really faster than a bit shift plus bit and
| [reply]
[d/l] |
Re: unpacking 6-bit values
by roboticus (Chancellor) on Dec 10, 2010 at 11:17 UTC
|
roboticus@Boink~
$ cat 876421.cpp
#include <stdio.h>
unsigned char inbuf[]="Now is the time for all ";
unsigned char outbuf[50];
void hexdump(unsigned char *p, int n) {
for (int i=0; i<n; i++) {
printf("%02x ", *p++);
}
puts("\n");
}
int main(int, char **) {
unsigned char *src = inbuf;
unsigned char *srcEnd = src + sizeof(inbuf);
unsigned char *dst = outbuf;
hexdump(src, sizeof(inbuf));
int rem = 0;
int st = 0;
while (src != srcEnd) {
switch (st) {
case 0:
rem = *src >> 6;
*dst++ = *src++ & 0x3f;
st = 1;
break;
case 1:
*dst++ = ((*src&0x0f)<<2) | rem;
rem = *src++>>4;
st = 2;
break;
case 2:
*dst++ = ((*src&0x03)<<4) | rem;
*dst++ = *src++>>2;
st = 0;
break;
}
}
hexdump(outbuf, dst-outbuf);
}
roboticus@Boink~marco@Boink:~
$ gcc 876421.cpp -lstdc++
roboticus@Boink:~
$ ./a.out
4e 6f 77 20 69 73 20 74 68 65 20 74 69 6d 65 20 66 6f 72 20 61 6c 6c 2
+0 00
0e 3d 36 1d 20 24 36 1c 20 10 07 1a 25 01 02 1d 29 35 16 19 20 18 36 1
+b 32 01 12 18 2c 31 06 08 00
...roboticus
When your only tool is a hammer, all problems look like your thumb. | [reply]
[d/l] |
Re: unpacking 6-bit values
by roboticus (Chancellor) on Dec 10, 2010 at 11:44 UTC
|
BrowserUk:
Update 3: I can't make pack & unpack work. I think endianness is biting me. A simple conversion of the C program to perl works, but isn't as nice to use as pack/unpack would have been. My best perl attempt so far is:
# Roboticus' second attempt
my $robo_2 = sub {
my @orig = unpack "S*", shift;
my $bits=0;
my $buf=0;
my @bytes;
while (@orig) {
$buf |= (shift @orig)<<$bits;
$bits += 16;
while ($bits>6) {
push @bytes, $buf & 0x3f;
$buf>>=6;
$bits-=6;
}
}
push @bytes, $buf if $bits;
return (@bytes);
};
When I was looking at pack trying to find a way to efficiently do the task, I noticed that it has a u flag for uuencoding! So just use that to do the job. You'll have to set the "length of data" byte at the front, but that should be trivial.
roboticus@Boink:~
$ cat 876421.pl
#!/usr/bin/perl
use strict;
use warnings;
my $orig = "Now is the time for all ";
my $enc = pack "u", $orig;
print "$enc\n";
my $dec = unpack "u", $enc;
print "$dec\n";
my (undef, @bytes) = map { 0x3f & ord($_) } split //, $enc;
printf "%02x ", $_ for @bytes;
roboticus@Boink:~
$ perl 876421.pl
83F]W(&ES('1H92!T:6UE(&9O<B!A;&P@
Now is the time for all
33 06 1d 17 28 26 05 13 28 27 31 08 39 32 21 14 3a 36 15 05 28 26 39 0
+f 3c 02 21 01 3b 26 10 00 0a
...roboticus
When your only tool is a hammer, all problems look like your thumb.
UPDATE: The reason I was looking into pack was that I had a better C program that I thought might translate into a quick perl script. The newer C program is:
#include <stdio.h>
unsigned char inbuf[]="Now is the time for all ";
unsigned char outbuf[50];
void hexdump(unsigned char *p, int n) {
for (int i=0; i<n; i++) {
printf("%02x ", *p++);
}
puts("\n");
}
int main(int, char **) {
unsigned char *src = inbuf;
unsigned char *srcEnd = src + sizeof(inbuf);
unsigned char *dst = outbuf;
hexdump(src, sizeof(inbuf));
int bits = 0;
int buf = 0;
while (src != srcEnd) {
buf |= (*src++)<<bits;
bits += 8;
while (bits > 6) {
*dst++ = buf & 0x3f;
buf >>= 6;
bits -= 6;
}
}
hexdump(outbuf, dst-outbuf);
}
Update 2: I forgot to remove the top two bits of the bytes to give you the values you wanted, and I also stripped out the first byte. To do so, I added the last two lines to the code (above) and I added the last line of output (above). Of course, now with the overhead of splitting the string back into individual characters, and transforming the bytes after the map may quite likely make the uuencoded version slower than some of the alternatives. Ah, well. | [reply]
[d/l]
[select] |
|
|
Update 3: I can't make pack & unpack work
Phew! I thought I was going nuts :)
From what I read, uuencode converts each 3-bytes to 4-bytes, which is the reverse of what I need.
Then I thought maybe I could use the decode process to perform my encoding, but I couldn't make that work either :(
But it sure did sound like a cool idea to start with.
| [reply] |
|
|
BrowserUk:
Yep. I saw it, and then looked at Wikipedia to check out what it was, and they had a nice little example there. I was hoping it was going to be fast, so I was putting it in a benchmark script, but I then discovered the bad news.
The benchmark script (such as it is):
The benchmark script shows a little bit of a speed boost, but not what I was hoping for. I may have to try Inline::C to see what we can get. Note: The benchmark isn't useful yet, as I haven't necessarily plugged your or jethros code in properly. If I had more time to put into it, I'd've added some of the other solutions as well. But I had to go to work, and now I've got to feed my son and do some chores.
roboticus@Boink:~
$ perl 876421.pl
REF: 14 21 16 1a 33 01 12 1a 33 01 22 1b 2f 11 07 08 21 01 02 1a 21 11
+ 27 0b
jethro: matches
robo_2: matches
Rate BrowserUk jethro robo_2
BrowserUk 11876/s -- -6% -20%
jethro 12642/s 6% -- -15%
robo_2 14837/s 25% 17% --
Thanks for coming up with a fun diversion for this morning!
...roboticus
When your only tool is a hammer, all problems look like your thumb. | [reply]
[d/l]
[select] |
|
|
Re: unpacking 6-bit values
by syphilis (Archbishop) on Dec 10, 2010 at 12:57 UTC
|
I'd try to make use of the gmp library ... but in all honesty I have absolutely no idea how sane that is.
The following takes about 3 seconds to process 100,000 such numbers as described. (It does, of course, take longer to create the 100,000 bitstrings in the first place, and would also take longer if it were to output the results of its processing.
It could, no doubt, be improved upon ... but if it's not already "in the ballpark", then it's probably not worth persevering with.
It could also be taken out of the realm of Inline::C and into the realm of Math::GMPz - suffering only minimal losses.
Since we're dealing with such small bitstrings, I would not be at all surprised if this is *not* such a smart approach.
use warnings;
use strict;
use Inline C => Config =>
INC => '-IC:/_32/msys/1.0/local/include',
LIBS => '-LC:/_32/msys/1.0/local/lib -lgmp',
BUILD_NOISY => 1,
USING => 'ParseRegExp';
use Inline C => <<'EOC';
#include <gmp.h>
void process(SV * inp) {
Inline_Stack_Vars;
mpz_t in, ret, and;
int i;
mpz_init2(in, 192);
mpz_set_str(in, SvPV_nolen(inp), 2);
mpz_init_set_ui(and, 63);
mpz_init2(ret, 6);
Inline_Stack_Reset;
for(i=0; i<32; i++) {
mpz_and(ret, in, and);
Inline_Stack_Push(newSVuv(mpz_get_ui(ret)));
mpz_div_2exp(in, in, 6);
}
Inline_Stack_Done;
Inline_Stack_Return(32);
}
EOC
my @in;
my @result;
for(1..100000) {
push @in, create();
}
print time, "\n";
for(@in) {
@result = process($_);
}
print time, "\n";
print "$in[-1]\n@result\n";
sub create {
my $ret;
$ret .= int(rand(2)) for 0..191;
return $ret;
}
Cheers,
Rob
| [reply]
[d/l] |
|
|
I haven't tested this as I can't get GMP to install here. I looked for a PPM for 64-bit 5.10 but none is available.
I guess that you probably have made this available for 5.12 64-bit via your repo, but I don't see enough value in 5.12 to cause me to go through the pain of re-installing everything I have, to warrant my upgrading.
Personally, I think the transition from 5.10 to 5.12 happened much to quickly. Maybe once 5.14 comes around.
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".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply] |
|
|
I looked for a PPM for 64-bit 5.10 but none is available
Yes, the first perl that built with MinGW64 straight out of the box was 5.12 - so, since I'm using the MinGW64 compiler, I've currently limited myself to building only for 5.12 (as regards x64). When 5.14 is released I'll cover it for both x86 and x64, too ... so you might be able to catch up then :-)
I can build these ppm's for x64 5.10 and 5.8 (I think) - and would happily do so for anyone that needs them, but by the time the x64 builds of ActivePerl become prevalent I expect that 5.10 and 5.8 will have long been superseded. I therefore don't currently intend to build and upload ppm's for these earlier x64 builds.
I've thought about uploading the libraries themselves. But even if they were available, you'd have to grab the MinGW64 compiler (and make some modifications to a couple of your ActivePerl .pm files) before you'd be able to run the Inline::C script I posted. (When I switch to Math::GMPz, there's about a 6x slowdown - mainly, I think, because perl's for loops are much slower than C's.)
Besides, it looks to me that you already have far better solutions ;-)
I think the transition from 5.10 to 5.12 happened much to quickly
It was certainly pretty quick - and 5.14 is due out next month !!
Cheers,
Rob
| [reply] |
Re: unpacking 6-bit values
by Tux (Canon) on Dec 10, 2010 at 15:50 UTC
|
I just could not leave this to rest. There might be more optimizations possible, but at least it offers you 5 native perl methods to do it and the speed diff:
$ cat test.pl
use strict;
use warnings;
use Data::Peek;
use Benchmark qw( cmpthese );
my $src = pack "C*" => map { int rand 256 } 0 .. 3071;
print STDERR "First 48 bytes of the compressed data ...\n";
DHexDump substr $src, 0, 48;
for (unpack "(a3)*", substr $src, 0, 12) {
DHexDump $_;
my $bits = unpack "B*", $_;
(my $b8 = substr $bits, 0, 48) =~ s/(.{8})/$1 /g;
(my $b6 = substr $bits, 0, 48) =~ s/(.{6})/$1 /g;
print STDERR " $b8\n $b6\n";
}
# unpack pack unpack unpack reverse
sub upuu
{
map { unpack "C", pack "b6", scalar reverse $_ }
unpack "(a6)*" => unpack "B*" => $src;
} # opuu
# unpack with 00
sub upuu0
{
map { unpack "C", pack "B8", "00$_" }
unpack "(a6)*" => unpack "B*" => $src;
} # opuu0
# using uuencode
sub uu
{
map { map { ($_ - 32) & 63 } unpack "xC*" => $_ }
split m/ *\n/ => pack "u" => $src;
} # uu
{ my @lut;
for (0 .. 0b111111) {
$lut[$_ << 18] = $_;
$lut[$_ << 12] = $_;
$lut[$_ << 6] = $_;
$lut[$_ ] = $_;
}
sub mlut
{
map { my $v = unpack "N", "\00$_\x00\x00";
($lut[$v & 0b111111_000000_000000_000000],
$lut[$v & 0b000000_111111_000000_000000],
$lut[$v & 0b000000_000000_111111_000000],
$v & 0b000000_000000_000000_111111);
} unpack "(a3)*" => $src;
} # mlut
}
# And shift unpack
{ my $m0 = 0b111111_000000_000000_000000;
my $m1 = 0b000000_111111_000000_000000;
my $m2 = 0b000000_000000_111111_000000;
my $m3 = 0b000000_000000_000000_111111;
sub asu
{
map {my $b = unpack "N", "\x00$_\x00\x00"; (
($b & $m0) >> 18,
($b & $m1) >> 12,
($b & $m2) >> 6,
($b & $m3)
) } unpack "(a3)*" => $src;
} # asu
}
my @dst;
@dst = uu ();
print STDERR "$#dst E\n";
print STDERR "uu: (@dst[0..22] ...\n @dst[4073..4095])\n";
@dst = upuu ();
print STDERR "upuu: (@dst[0..22] ...\n @dst[4073..4095])\n";
@dst = upuu0 ();
print STDERR "upuu0: (@dst[0..22] ...\n @dst[4073..4095])\n";
@dst = asu ();
print STDERR "asu: (@dst[0..22] ...\n @dst[4073..4095])\n";
@dst = mlut ();
print STDERR "mlut: (@dst[0..22] ...\n @dst[4073..4095])\n";
cmpthese (-2, { uu => \&uu, upuu => \&upuu, upuu0 => \&upuu0, asu => \
+&asu, mlut => \&mlut });
$
$ perl test.pl
First 48 bytes of the compressed data ...
0000 1c 66 02 ac 50 1f 41 b2 e4 10 b9 03 38 b3 7e 2d .f..P.A.....8.
+~-
0010 5e 95 02 c6 c7 71 39 08 c7 82 37 40 0d 40 c1 e1 ^....q9...7@.@
+..
0020 1f 9a d9 6d 51 f3 7e 0a 8d 9b 75 85 0a a5 82 65 ...mQ.~...u...
+.e
0000 1c 66 02 .f.
00011100 01100110 00000010
000111 000110 011000 000010
0000 ac 50 1f .P.
10101100 01010000 00011111
101011 000101 000000 011111
0000 41 b2 e4 A..
01000001 10110010 11100100
010000 011011 001011 100100
0000 10 b9 03 ...
00010000 10111001 00000011
000100 001011 100100 000011
4095 E
uu: (7 6 24 2 43 5 0 31 16 27 11 36 4 11 36 3 14 11 13 62 11 21 58
+...
23 32 30 37 37 26 19 30 42 19 29 32 54 2 9 3 23 32 62 52 5 31
+46)
upuu: (7 6 24 2 43 5 0 31 16 27 11 36 4 11 36 3 14 11 13 62 11 21 58
+...
23 32 30 37 37 26 19 30 42 19 29 32 54 2 9 3 23 32 62 52 5 31
+46)
upuu0: (7 6 24 2 43 5 0 31 16 27 11 36 4 11 36 3 14 11 13 62 11 21 58
+...
23 32 30 37 37 26 19 30 42 19 29 32 54 2 9 3 23 32 62 52 5 31
+46)
asu: (7 6 24 2 43 5 0 31 16 27 11 36 4 11 36 3 14 11 13 62 11 21 58
+...
23 32 30 37 37 26 19 30 42 19 29 32 54 2 9 3 23 32 62 52 5 31
+46)
mlut: (7 6 24 2 43 5 0 31 16 27 11 36 4 11 36 3 14 11 13 62 11 21 58
+...
23 32 30 37 37 26 19 30 42 19 29 32 54 2 9 3 23 32 62 52 5 31
+46)
Rate upuu0 upuu mlut asu uu
upuu0 354/s -- -1% -56% -64% -68%
upuu 357/s 1% -- -56% -64% -67%
mlut 813/s 130% 128% -- -17% -26%
asu 985/s 178% 176% 21% -- -10%
uu 1093/s 209% 206% 34% 11% --
$
Enjoy!
Enjoy, Have FUN! H.Merijn
| [reply]
[d/l] |
Re: unpacking 6-bit values
by salva (Canon) on Dec 10, 2010 at 12:54 UTC
|
Probably roboticus solution is better, but anyway:
- unpack your data as an hexadecimal string
- use a hash to convert every three hexadecimal digits (12 bits) into two bytes (16bits).
use Data::Dumper;
my %t;
for my $i (0..63) {
for my $j (0..63) {
$t{sprintf "%03x", $i*64 + $j} = [$i, $j];
}
}
my $buf;
my @bytes;
while (read STDIN, $buf, 4096) {
my $hex = unpack "H*" => $buf;
while ($hex =~ /(...)/g) {
push @bytes, @{$t{$1}};
}
}
print Dumper \@bytes;
| [reply]
[d/l] |
Re: unpacking 6-bit values
by BrowserUk (Patriarch) on Dec 10, 2010 at 20:43 UTC
|
Here's the results of my benchmark so far. I haven't yet included syphilis' method (no GMP installed); or tux' many possibilities (I've not yet digested them all).
Here's the results of the benchmark below:
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 2
+3 24 25 26 27 28 29 30 31
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 2
+3 24 25 26 27 28 29 30 31
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 2
+3 24 25 26 27 28 29 30 31
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 2
+3 24 25 26 27 28 29 30 31
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 2
+3 24 25 26 27 28 29 30 31
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 2
+3 24 25 26 27 28 29 30 31
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 2
+3 24 25 26 27 28 29 30 31
Rate buk jethro salva jmcnamara Croboticus C_24to32
+C_24to32_2
buk 28348/s -- -41% -47% -48% -85% -86%
+ -86%
jethro 48135/s 70% -- -10% -12% -75% -76%
+ -76%
salva 53532/s 89% 11% -- -2% -72% -73%
+ -73%
jmcnamara 54661/s 93% 14% 2% -- -72% -73%
+ -73%
Croboticus 193637/s 583% 302% 262% 254% -- -3%
+ -3%
C_24to32 199055/s 602% 314% 272% 264% 3% --
+ -0%
C_24to32_2 199055/s 602% 314% 272% 264% 3% 0%
+ --
The code #! perl -slw
use strict;
use Inline C => Config => BUILD_NOISY => 1;
use Inline C => <<'END_C', NAME => '_24to32', CLEAN_AFTER_BUILD => 0;
#define IS_VARS Inline_Stack_Vars
#define IS_RESET Inline_Stack_Reset
#define IS_PUSHIV( iv ) Inline_Stack_Push( sv_2mortal( newSViv( iv ) )
+ )
#define IS_PUSHUV( uv ) Inline_Stack_Push( sv_2mortal( newSVuv( uv ) )
+ )
#define IS_DONE Inline_Stack_Done
typedef union {
unsigned int packed;
struct { unsigned e :8, d :6, c :6, b :6, a :6; } u;
} _4BY6;
void _24to32( SV* packed ) {
IS_VARS;
char *pp = SvPVX( packed );
_4BY6 up;
int i;
IS_RESET;
for( i=0; i<24; i+=3 ) {
up.packed = _byteswap_ulong( *(unsigned long*)&pp[ i ] );
IS_PUSHUV( up.u.a );
IS_PUSHUV( up.u.b );
IS_PUSHUV( up.u.c );
IS_PUSHUV( up.u.d );
}
IS_DONE;
return;
}
void _24to32_2( SV *packed ) {
IS_VARS;
char *pp = SvPVX( packed );
int i;
IS_RESET;
for( i=0; i<24; i+=3 ) {
unsigned int n = _byteswap_ulong( *(unsigned long*)&pp[ i -1 ]
+ );
IS_PUSHUV( ( n & 0xfc0000 ) >> 18 );
IS_PUSHUV( ( n & 0x03f000 ) >> 12 );
IS_PUSHUV( ( n & 0x000fc0 ) >> 6 );
IS_PUSHUV( ( n & 0x00003f ) );
}
IS_DONE;
return;
}
void roboticus( SV *packed ) {
IS_VARS;
unsigned char *src = SvPVX( packed );
unsigned char *srcEnd = src + 24;
int rem = 0;
int st = 0;
IS_RESET;
while (src != srcEnd) {
switch (st) {
case 0:
IS_PUSHUV( ( *src & 0xfc ) >> 2 );
rem = ( *src++ & 0x03 ) << 4;
st = 1;
break;
case 1:
IS_PUSHUV( ( ( *src & 0xf0 ) >> 4 ) | rem );
rem = ( *src++ & 0x0f ) << 2;
st = 2;
break;
case 2:
IS_PUSHUV( ( ( *src & 0xc0 ) >> 6 ) | rem );
IS_PUSHUV( *src++ & 0x3f );
st = 0;
break;
}
}
IS_DONE;
return;
}
END_C
use Math::Random::MT qw[ rand srand ];
use Benchmark qw[ cmpthese ];
sub buk {
map ord( pack 'B8', '00'.$_ ), unpack '(a6)*', unpack 'B*', $_[0];
}
sub jethro {
use constant {
B1N1 => [ map{ ($_) x 4 } 0 .. 63 ],
B1N2 => [ ( 0, 16, 32, 48 ) x 64 ],
B2N1 => [ map{ ($_) x 16 } 0 .. 15 ],
B2N2 => [ ( 0,4,8,12,16,20,24,28,32,36,40,44,48,52,56,60, ) x
+16 ],
B3N1 => [ map{ ( $_ ) x 64 } 0 .. 63 ],
B3N2 => [ ( 0 .. 63 ) x 4 ],
};
map {
my( $b1, $b2, $b3 ) = unpack 'C3', $_;
B1N1->[ $b1 ],
B1N2->[ $b1 ] + B2N1->[ $b2 ],
B2N2->[ $b2 ] + B3N1->[ $b3 ],
B3N2->[ $b3 ]
} unpack '(a3)8', $_[0];
}
sub jmcnamara {
use constant MASK00_05 => 2**6 - 1;
use constant {
MASK06_11 => MASK00_05 << 6,
MASK12_17 => MASK00_05 << 12,
MASK18_23 => MASK00_05 << 18,
};
map {
$_ = unpack 'N', chr(0) . $_;
( $_ & MASK18_23 ) >> 18,
( $_ & MASK12_17 ) >> 12,
( $_ & MASK06_11 ) >> 6,
$_ & MASK00_05,
} unpack '(a3)8', $_[0]
}
sub salva {
use constant {
SALVA => {
map{ sprintf( "%03x", $_ ) => [ ( $_ & 0xfc0 )>>6, $_ & 0x
+3f ] }0..4095
},
};
map @{ SALVA->{ $_ } }, unpack '(a3)*', unpack 'H*', $_[0];
}
## 32 6-bit values (0..31) packed as 24-bytes.
our $packed = pack 'C*', qw[
00 16 131 16 81 135 32 146 139 48 211 143
65 20 147 81 85 151 97 150 155 113 215 159
];
print join ' ', map sprintf( "%02d", $_ ), buk( $packed );
print join ' ', map sprintf( "%02d", $_ ), jethro( $packed );
print join ' ', map sprintf( "%02d", $_ ), jmcnamara( $packed );
print join ' ', map sprintf( "%02d", $_ ), salva( $packed );
print join ' ', map sprintf( "%02d", $_ ), _24to32( $packed );
print join ' ', map sprintf( "%02d", $_ ), roboticus( $packed );
print join ' ', map sprintf( "%02d", $_ ), _24to32_2( $packed );
cmpthese -1, {
buk => q[ my @smalls = buk( $packed ) ],
jethro => q[ my @smalls = jethro( $packed ) ],
jmcnamara => q[ my @smalls = jmcnamara( $packed ) ],
salva => q[ my @smalls = salva( $packed ) ],
C_24to32 => q[ my @smalls = _24to32( $packed ) ],
Croboticus=> q[ my @smalls = roboticus( $packed ) ],
C_24to32_2=> q[ my @smalls = _24to32_2( $packed ) ],
};
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".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply]
[d/l]
[select] |
Re: unpacking 6-bit values
by Tux (Canon) on Dec 10, 2010 at 18:46 UTC
|
use Inline "C";
:
@dst = uic ($src);
print STDERR "uic: (@dst[0..22] ...\n @dst[4073..4095])\n";
cmpthese (-2, { uu => \&uu, upuu => \&upuu, upuu0 => \&upuu0, asu => \
+&asu, mlut
=> \&mlut, uic => sub { uic ($src); } });
__END__
__C__
void uic (SV *src)
{
int i = 0;
STRLEN l;
unsigned char *s = (unsigned char *)SvPV (src, l);
inline_stack_vars;
inline_stack_reset;
while (i < l) {
int n = (s[i] >> 2) & 0x3f;
inline_stack_push (newSViv (n));
n = (s[i++] & 0x03) << 4;
n |= (s[i] >> 4) & 0x0f;
inline_stack_push (newSViv (n));
n = (s[i++] & 0x0f) << 2;
n |= (s[i] >> 6) & 0x03;
inline_stack_push (newSViv (n));
n = s[i++] & 0x3f;
inline_stack_push (newSViv (n));
}
inline_stack_done;
} /* uic */
And the stunning result ...
uu: (50 26 62 7 35 6 35 32 50 13 56 19 61 46 55 59 39 14 21 17 16 4
+2 34 ...
51 63 37 34 24 35 11 33 56 63 39 13 19 22 10 0 17 20 54 11 5 4
+7 56)
upuu: (50 26 62 7 35 6 35 32 50 13 56 19 61 46 55 59 39 14 21 17 16 4
+2 34 ...
51 63 37 34 24 35 11 33 56 63 39 13 19 22 10 0 17 20 54 11 5 4
+7 56)
upuu0: (50 26 62 7 35 6 35 32 50 13 56 19 61 46 55 59 39 14 21 17 16 4
+2 34 ...
51 63 37 34 24 35 11 33 56 63 39 13 19 22 10 0 17 20 54 11 5 4
+7 56)
asu: (50 26 62 7 35 6 35 32 50 13 56 19 61 46 55 59 39 14 21 17 16 4
+2 34 ...
51 63 37 34 24 35 11 33 56 63 39 13 19 22 10 0 17 20 54 11 5 4
+7 56)
mlut: (50 26 62 7 35 6 35 32 50 13 56 19 61 46 55 59 39 14 21 17 16 4
+2 34 ...
51 63 37 34 24 35 11 33 56 63 39 13 19 22 10 0 17 20 54 11 5 4
+7 56)
uic: (50 26 62 7 35 6 35 32 50 13 56 19 61 46 55 59 39 14 21 17 16 4
+2 34 ...
51 63 37 34 24 35 11 33 56 63 39 13 19 22 10 0 17 20 54 11 5 4
+7 56)
Rate upuu upuu0 mlut asu uu uic
upuu 367/s -- -3% -56% -62% -65% -95%
upuu0 380/s 3% -- -54% -61% -64% -95%
mlut 832/s 127% 119% -- -14% -22% -89%
asu 972/s 165% 156% 17% -- -9% -87%
uu 1063/s 190% 180% 28% 9% -- -86%
uic 7758/s 2014% 1944% 832% 698% 629% --
Enjoy, Have FUN! H.Merijn
| [reply]
[d/l]
[select] |
|
|
I got around to incorporating your implementations into my benchmark so that I had a set of comparable figures.
For the most part there are no surprises, with your implementations coming in more or less similar to my implementations of the same algorithms. Just a few percent either way as you'd expect. There are however, two stand outs.
The first is your uuencode() version--well done for getting it to work which I never did--which proves to be some 20% faster than the next nearest pure perl solution.
The second is your C implementation of the basic mask and shift algorithm which comes out 7% to 8% faster than the other C routines. Looking at the basic mechanics I do not see any great differences that the compiler shouldn't be able to optimise away. The only difference I can see that might account for that 8% is that you aren't mortalising your return values.
I've noticed that sv_2mortal() seems more costly that you'd think it should be in the past and tried to sidestep it, but every time I have, it has led to memory leaks. When I add that to your code, the difference over the other C routines drops to 2%. Still an advantage though, so maybe your implementation is more compiler/optimiser friendly.
Many thanks for your responses, it is always instructive to see how other people code the same algorithm.
(Also, congrats that all your routines produced the same, correct output!)
Rate upuu upuu0 buk jethro salva mlut asu jmcn uu C
+_.._2 Crob C_24to32 uic
upuu 25622/s -- -4% -13% -48% -53% -54% -54% -56% -64% -
+87% -87% -87% -88%
upuu0 26597/s 4% -- -10% -46% -51% -52% -53% -54% -62% -
+86% -86% -86% -87%
buk 29407/s 15% 11% -- -40% -46% -47% -48% -49% -58% -
+85% -85% -85% -86%
jethro 49099/s 92% 85% 67% -- -10% -12% -13% -15% -30% -
+74% -74% -75% -76%
salva 54710/s 114% 106% 86% 11% -- -2% -3% -6% -22% -
+72% -72% -72% -74%
mlut 55864/s 118% 110% 90% 14% 2% -- -1% -4% -20% -
+71% -71% -71% -73%
asu 56264/s 120% 112% 91% 15% 3% 1% -- -3% -20% -
+71% -71% -71% -73%
jmcnamara 57962/s 126% 118% 97% 18% 6% 4% 3% -- -17% -
+70% -70% -70% -72%
uu 70207/s 174% 164% 139% 43% 28% 26% 25% 21% -- -
+64% -64% -64% -66%
C_24to32_2 192359/s 651% 623% 554% 292% 252% 244% 242% 232% 174%
+ -- -0% -1% -7%
Croboticus 192543/s 651% 624% 555% 292% 252% 245% 242% 232% 174%
+ 0% -- -1% -7%
C_24to32 194211/s 658% 630% 560% 296% 255% 248% 245% 235% 177%
+ 1% 1% -- -6%
uic 207580/s 710% 680% 606% 323% 279% 272% 269% 258% 196%
+ 8% 8% 7% --
(Gah! I wish I could defeat that stupid f*** wrap algorithm!)
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".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply]
[d/l] |
|
|
I see a decline of close to 20% for adding mortality. The other big difference between my algorithm (and how I tested it) and the once you posted are that mine are not depending on the length of the buffer and are therefor more generic. The huge disadvantage in my testing is also the fact that I only use one single buffer, causing all 4095 values to be placed on the stack at once. And they all have to be removed when the test is done (something the non-mortalizing version skips).
Still the mortalizing version of my algorithm in C/XS is still 6 times faster than the uu version.
Thanks for the thread, it was fun to untangle.
Enjoy, Have FUN! H.Merijn
| [reply] |
|
|
Re: unpacking 6-bit values
by bart (Canon) on Dec 11, 2010 at 03:10 UTC
|
It looks to me like you're reinventing base64 encoding: In base64, 3 bytes are represented as 4 characters, thus, 6 bits per character.
So perhaps building something on top of encoding in MIME::Base64, and converting the characters into bytes using tr, might do.
If bit ordering doesn't mess with you. | [reply] |
|
|
It looks to me like you're reinventing base64 encoding:
No more like the reverse of it. This format compresses four numerical values 0..63 into 3 bytes.
As you say, in base64, you start with 3 bytes 0..255 and expand them to 4 bytes 65+(0..63). The purpose is to avoid the transmission of control characters that might upset protocols.
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".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply] |
Re: unpacking 6-bit values
by ambrus (Abbot) on Dec 10, 2010 at 19:46 UTC
|
How would you do this efficiently in C anyway?
Ask the people who write FAT 12 drivers in C. (FAT 12 has two 12-bit values packed in three bytes.)
| [reply] |
Re: unpacking 6-bit values
by Marshall (Canon) on Dec 12, 2010 at 14:37 UTC
|
Wow! Interesting thread!
Not sure if a C version of the jmcnamara idea got benchmarked. I think such a thing would look like below. I didn't look at the ASM code, but even at a low optimize level, this probably results in pretty good code.
#include <stdio.h>
#define MASK05_00 (0x3f) /*6 bits at a time*/
#define MASK11_06 (MASK05_00 << 6)
#define MASK17_12 (MASK11_06 << 6)
#define MASK23_18 (MASK17_12 << 6)
int main (int argc, char **argv)
{
unsigned char in [24] =
{ 00, 16, 131, 16, 81, 135, 32, 146, 139, 48, 211, 143,
65, 20, 147, 81, 85, 151, 97, 150, 155, 113, 215, 159};
unsigned char out [32];
void expand6 (unsigned char *in, unsigned char* out);
void hexdump (unsigned char *p, int n);
expand6(in, out);
hexdump(in, 24);
hexdump(out, 32);
return(0);
}
void expand6 (unsigned char *in, unsigned char* out)
{
unsigned int temp;
int i;
for (i=0; i<8; i++) /*8 24 bit sequences */
{
temp = *in++ << 16;
temp |= *in++ << 8;
temp |= *in++;
*out++ = (temp & MASK23_18)>>18;
*out++ = (temp & MASK17_12)>>12;
*out++ = (temp & MASK11_06)>>6;
*out++ = (temp & MASK05_00);
}
}
void hexdump(unsigned char *p, int n)
{
int i;
for (i=0; i<n; i++)
printf("%02x ", *p++);
puts("\n");
}
/* ouput
00 10 83 10 51 87 20 92 **in buf
8b 30 d3 8f 41 14 93 51
55 97 61 96 9b 71 d7 9f
00 01 02 03 04 05 06 07 **out buf
08 09 0a 0b 0c 0d 0e 0f
10 11 12 13 14 15 16 17
18 19 1a 1b 1c 1d 1e 1f
*/
| [reply]
[d/l] |
|
|
void _24to32_2( SV *packed ) {
IS_VARS;
char *pp = SvPVX( packed );
int i;
IS_RESET;
for( i=0; i<24; i+=3 ) {
unsigned int n = _byteswap_ulong( *(unsigned long*)&pp[ i -1 ]
+ );
IS_PUSHUV( ( n & 0xfc0000 ) >> 18 );
IS_PUSHUV( ( n & 0x03f000 ) >> 12 );
IS_PUSHUV( ( n & 0x000fc0 ) >> 6 );
IS_PUSHUV( ( n & 0x00003f ) );
}
IS_DONE;
return;
}
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".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply]
[d/l]
[select] |
Re: unpacking 6-bit values
by johngg (Canon) on Dec 15, 2010 at 00:08 UTC
|
vec's no good because it only does powers of 2-bits.
Just out of interest (and to try to get my head around how it works) I thought I'd see if I could come up with a vec solution although I didn't expect it to challenge in the speed stakes. By combining 4-bit and 2-bit vecs with 2- or 4-bit shifts you can obtain your 6-bit values. As expected, it trails the field. (I didn't test the C solutions as I don't have Inline installed).
sub johngg {
map
{
my $offsetVec4 = $_ * 6;
my $offsetVec2 = $_ * 12;
my @vals = (
( ( vec( $_[0], $offsetVec4 + 1, 4 ) << 2 ) +
vec( $_[0], $offsetVec2 + 1, 2 ) ),
( ( vec( $_[0], $offsetVec2, 2 ) << 4 ) +
vec( $_[0], $offsetVec4 + 3, 4 ) ),
( ( vec( $_[0], $offsetVec4 + 2, 4 ) << 2 ) +
vec( $_[0], $offsetVec2 + 11, 2 ) ),
( ( vec( $_[0], $offsetVec2 + 10, 2 ) << 4 ) +
vec( $_[0], $offsetVec4 + 4, 4 ) ),
);
}
0 .. 7;
}
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 2
+3 24 25 26 27 28 29 30 31
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 2
+3 24 25 26 27 28 29 30 31
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 2
+3 24 25 26 27 28 29 30 31
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 2
+3 24 25 26 27 28 29 30 31
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 2
+3 24 25 26 27 28 29 30 31
Rate johngg buk jethro jmcnamara salva
johngg 22191/s -- -3% -29% -42% -51%
buk 22974/s 4% -- -27% -39% -49%
jethro 31438/s 42% 37% -- -17% -30%
jmcnamara 37959/s 71% 65% 21% -- -16%
salva 45081/s 103% 96% 43% 19% --
I hope this is of interest.
| [reply]
[d/l]
[select] |
Re: unpacking 6-bit values
by anonymized user 468275 (Curate) on Dec 10, 2010 at 19:55 UTC
|
I think it matters how the millions of bytes are sourced -- is it in a file or in memory, does in come in chunks and in what formats is it.
| [reply] |
|
|
| [reply] |
|
|
It matters if you can optimise the I/O from disk. The drift is that performance should rarely be addressed too specifically.
| [reply] |
|
|
|
|
|
|
|
|
Re: unpacking 6-bit values
by anonymized user 468275 (Curate) on Dec 16, 2010 at 09:42 UTC
|
my $buf;
my @out = ();
while ( length( $bigstring )) {
$buf = '';
$buf = $buf . chop $bigstring for (0..2);
for (0..3) {
push @out, ($buf & 64); # update: Perl didn't accept this bit
+op
$buf >>= 6; # but is happy with this one
}
}
update: Grr if only all perl bitwise operators worked on strings! Pity - it would be pointless fixing this by unpacking the "offending" byte because I was deliberately trying to avoid any unpacking in this attempt at a quickie solution.
| [reply]
[d/l] |
|
|
#! perl -slw
use strict;
sub doit {
my $in = shift;
my $buf;
my @out = ();
while( length( $in ) ) {
$buf = '';
$buf = $buf . chop $in for (0..2);
for( 0 .. 3 ) {
push @out, ($buf & 64);
$buf >>= 6;
}
}
return @out
}
our $packed = pack 'C*', qw[
00 16 131 16 81 135 32 146 139 48 211 143 65 20 147 81 85 151 97 1
+50 155 113 215 159
];
print join ' ', map sprintf( "%02d", $_ ), doit( $packed );
__END__
C:\test>junk10
Argument "ƒÎq" isn't numeric in bitwise and (&) at C:\test\junk10.pl l
+ine 12.
Argument "øûa" isn't numeric in bitwise and (&) at C:\test\junk10.pl l
+ine 12.
Argument "ùUQ" isn't numeric in bitwise and (&) at C:\test\junk10.pl l
+ine 12.
Argument "ô^TA" isn't numeric in bitwise and (&) at C:\test\junk10.pl
+line 12.
Argument "M-^OË0" isn't numeric in bitwise and (&) at C:\test\junk10.p
+l line 12.
Argument "ïÆ " isn't numeric in bitwise and (&) at C:\test\junk10.pl l
+ine 12.
Argument "çQ^P" isn't numeric in bitwise and (&) at C:\test\junk10.pl
+line 12.
Argument "â^P\0" isn't numeric in bitwise and (&) at C:\test\junk10.pl
+ line 12.
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0
+0 00 00 00 00 00 00 00 00
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".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply]
[d/l] |