Changes

Jump to: navigation, search

Assorted Algorithm Alliteration

4,784 bytes added, 10:34, 11 October 2012
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 ==

Navigation menu