1
edit
Changes
no edit summary
memset(x, 0, 16);
}
</pre>
=== Bzip2 - Mark de la Cruz ===
From http://www.bzip.org/: bzip2 is a freely available, patent free (see below), high-quality data compressor. It typically compresses files to within 10% to 15% of the best available techniques (the PPM family of statistical compressors), whilst being around twice as fast at compression and six times faster at decompression.
The full source can be found in the link above.
Below is the profile and the function to be optimized:
<pre>
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
63.21 7.01 7.01 23 0.30 0.47 BZ2_compressBlock
28.85 10.21 3.20 23 0.14 0.14 mainSort
4.78 10.74 0.53 1 0.53 0.53 fallbackSort
2.34 11.00 0.26 8280 0.00 0.00 default_bzalloc
0.54 11.06 0.06 23 0.00 0.16 BZ2_blockSort
0.27 11.09 0.03 552 0.00 0.00 BZ2_hbMakeCodeLengths
0.00 11.09 0.00 113812 0.00 0.00 add_pair_to_block
0.00 11.09 0.00 58370 0.00 0.00 _init
0.00 11.09 0.00 8276 0.00 0.00 BZ2_bzCompress
0.00 11.09 0.00 4159 0.00 0.00 myfeof
0.00 11.09 0.00 4158 0.00 0.00 BZ2_bzWrite
0.00 11.09 0.00 148 0.00 0.00 bsPutUChar
0.00 11.09 0.00 138 0.00 0.00 BZ2_hbAssignCodes
0.00 11.09 0.00 24 0.00 0.00 bsPutUInt32
0.00 11.09 0.00 4 0.00 0.00 default_bzfree
0.00 11.09 0.00 4 0.00 0.00 hasSuffix
0.00 11.09 0.00 4 0.00 0.00 testf
0.00 11.09 0.00 2 0.00 0.00 copyFileName
0.00 11.09 0.00 2 0.00 0.00 fileExists
0.00 11.09 0.00 1 0.00 0.00 BZ2_bzCompressEnd
0.00 11.09 0.00 1 0.00 0.01 BZ2_bzCompressInit
0.00 11.09 0.00 1 0.00 0.24 BZ2_bzWriteClose64
0.00 11.09 0.00 1 0.00 0.01 BZ2_bzWriteOpen
0.00 11.09 0.00 1 0.00 0.00 applySavedFileAttrToOutputFile
0.00 11.09 0.00 1 0.00 11.09 compressStream
|===============================================================================|
Source code to compressBlock
/*---------------------------------------------------*/
void BZ2_compressBlock ( EState* s, Bool is_last_block )
{
if (s->nblock > 0) {
BZ_FINALISE_CRC ( s->blockCRC );
s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
s->combinedCRC ^= s->blockCRC;
if (s->blockNo > 1) s->numZ = 0;
if (s->verbosity >= 2)
VPrintf4( " block %d: crc = 0x%08x, "
"combined CRC = 0x%08x, size = %d\n",
s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
BZ2_blockSort ( s );
}
s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
/*-- If this is the first block, create the stream header. --*/
if (s->blockNo == 1) {
BZ2_bsInitWrite ( s );
bsPutUChar ( s, BZ_HDR_B );
bsPutUChar ( s, BZ_HDR_Z );
bsPutUChar ( s, BZ_HDR_h );
bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
}
if (s->nblock > 0) {
bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
/*-- Now the block's CRC, so it is in a known place. --*/
bsPutUInt32 ( s, s->blockCRC );
/*--
Now a single bit indicating (non-)randomisation.
As of version 0.9.5, we use a better sorting algorithm
which makes randomisation unnecessary. So always set
the randomised bit to 'no'. Of course, the decoder
still needs to be able to handle randomised blocks
so as to maintain backwards compatibility with
older versions of bzip2.
--*/
bsW(s,1,0);
bsW ( s, 24, s->origPtr );
generateMTFValues ( s );
sendMTFValues ( s );
}
/*-- If this is the last block, add the stream trailer. --*/
if (is_last_block) {
bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
bsPutUInt32 ( s, s->combinedCRC );
if (s->verbosity >= 2)
VPrintf1( " final combined CRC = 0x%08x\n ", s->combinedCRC );
bsFinishWrite ( s );
}
}
</pre>
== Instructor's Comments ==
