[squeakdev] The Trunk: Compressionnice.18.mcz
commits at source.squeak.org
commits at source.squeak.org
Fri Jun 11 19:57:08 UTC 2010
Nicolas Cellier uploaded a new version of Compression to project The Trunk:
http://source.squeak.org/trunk/Compressionnice.18.mcz
==================== Summary ====================
Name: Compressionnice.18
Author: nice
Time: 11 June 2010, 9:57:04.522 pm
UUID: c905b9a4f9544041ac679e7373c56964
Ancestors: Compressionul.17
Replace some underscore _ assignments with :=
=============== Diff against Compressionul.17 ===============
Item was changed:
Object subclass: #GZipSurrogateStream
instanceVariableNames: 'gZipStream zippedFileStream bufferStream positionThusFar'
classVariableNames: ''
poolDictionaries: ''
category: 'CompressionStreams'!
+ !GZipSurrogateStream commentStamp: 'nice 3/24/2010 07:36' prior: 0!
 !GZipSurrogateStream commentStamp: '<historical>' prior: 0!
A pseudo stream that allows SmartRefStream to write directly to a gzipped file. There are some peculiarities of the project exporting process that require:
1. We ignore #close since the file is closed and may be reopened to continue writing. We implement #reallyClose for when we know that all writing is over.
2. We use a BitBlt to write WordArrayForSegment objects. Bit of a hack, but there it is.
 fileStream wa 
+ wa := WordArrayForSegment new: 30000.
 wa _ WordArrayForSegment new: 30000.
1 to: wa size do: [ :i  wa at: i put: i].
+ fileStream := GZipSurrogateStream newFileNamed: 'xxx3.gz' inDirectory: FileDirectory default.
 fileStream _ GZipSurrogateStream newFileNamed: 'xxx3.gz' inDirectory: FileDirectory default.
fileStream nextPutAll: 'this is a test'.
fileStream nextPutAll: wa.
fileStream reallyClose.
!
Item was changed:
ReadStream subclass: #InflateStream
instanceVariableNames: 'state bitBuf bitPos source sourcePos sourceLimit litTable distTable sourceStream crc'
classVariableNames: 'BlockProceedBit BlockTypes FixedDistCodes FixedLitCodes MaxBits StateNewBlock StateNoMoreData'
poolDictionaries: ''
category: 'CompressionStreams'!
+ !InflateStream commentStamp: 'nice 3/24/2010 07:37' prior: 0!
 !InflateStream commentStamp: '<historical>' prior: 0!
This class implements the Inflate decompression algorithm as defined by RFC1951 and used in PKZip, GZip and ZLib (and many, many more). It is a variant of the LZ77 compression algorithm described in
[LZ77] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory", Vol. 23, No. 3, pp. 337343.
[RFC1951] Deutsch. P, "DEFLATE Compressed Data Format Specification version 1.3"
For more information see the above mentioned RFC 1951 which can for instance be found at
http://www.leo.org/pub/comp/doc/standards/rfc/index.html
Huffman Tree Implementation Notes:
===========================================
The huffman tree used for decoding literal, distance and length codes in the inflate algorithm has been encoded in a single Array. The tree is made up of subsequent tables storing all entries at the current bit depth. Each entry in the table (e.g., a 32bit Integer value) is either a leaf or a nonleaf node. Leaf nodes store the immediate value in its low 16 bits whereas nonleaf nodes store the offset of the subtable in its low 16bits. The high 8 bits of nonleaf nodes contain the number of additional bits needed for the sub table (the high 8 bits of leafnodes are always zero). The first entry in each table is always a nonleaf node indicating how many bits we need to fetch initially. We can thus travel down the tree as follows (written in sortofpseudocode the actual implementation can be seen in InflateStream>>decodeValueFrom:):
+ table := initialTable.
+ bitsNeeded := high 8 bits of (table at: 1). "Determine initial bits"
+ table := initialTable + (low 16 bits of (table at: 1)). "Determine start of first real table"
+ [bits := fetch next bitsNeeded bits. "Grab the bits"
+ value := table at: bits. "Lookup the value"
 table _ initialTable.
 bitsNeeded _ high 8 bits of (table at: 1). "Determine initial bits"
 table _ initialTable + (low 16 bits of (table at: 1)). "Determine start of first real table"
 [bits _ fetch next bitsNeeded bits. "Grab the bits"
 value _ table at: bits. "Lookup the value"
value has high 8 bit set] whileTrue:[ "Check if it's leaf"
+ table := initialTable + (low 16 bits of value). "No  compute new sub table start"
+ bitsNeeded := high 8 bit of value]. "Compute additional number of bits needed"
 table _ initialTable + (low 16 bits of value). "No  compute new sub table start"
 bitsNeeded _ high 8 bit of value]. "Compute additional number of bits needed"
^value
!
More information about the Squeakdev
mailing list
