1
edit
Changes
no edit summary
== Team Members ==
# [mailto:mddelacruz1@myseneca.ca?subject=GPU610 Mark de la Cruz]
# [mailto:elim2@myseneca.ca?subject=GPU610 Edwin Lim]- MD5 Checksum Calculator# [mailto:mdafidchao@myseneca.ca?subject=GPU610 Michael Afidchao]- Game of Life
# [mailto:mddelacruz1@myseneca.ca;elim2@myseneca.ca;mdafidchao@myseneca.ca?subject=GPU610 eMail All]
The Game of Life is a "0 player game" cellular automaton. With an initial configuration,
the game uses a set of rules to determine what happens to the life forms from generation
</pre>
===MD5 Checksum Calculator- Edwin Lim===
The md5 checksum is a commonly used hash function that produces a 128-bit hash value commonly used to check data integrity. It is also used in a wide variety of security applications, however its use in checking data integrity is what will be explored in this assignment.
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 ==
