[squeak-dev] The Trunk: Compression-nice.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/Compression-nice.18.mcz
==================== Summary ====================
Name: Compression-nice.18
Author: nice
Time: 11 June 2010, 9:57:04.522 pm
UUID: c905b9a4-f954-4041-ac67-9e7373c56964
Ancestors: Compression-ul.17
Replace some underscore _ assignments with :=
=============== Diff against Compression-ul.17 ===============
Item was changed:
Object subclass: #GZipSurrogateStream
instanceVariableNames: 'gZipStream zippedFileStream bufferStream positionThusFar'
classVariableNames: ''
poolDictionaries: ''
category: 'Compression-Streams'!
+ !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: 'Compression-Streams'!
+ !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. 337-343.
[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 non-leaf node. Leaf nodes store the immediate value in its low 16 bits whereas non-leaf nodes store the offset of the subtable in its low 16bits. The high 8 bits of non-leaf nodes contain the number of additional bits needed for the sub table (the high 8 bits of leaf-nodes are always zero). The first entry in each table is always a non-leaf node indicating how many bits we need to fetch initially. We can thus travel down the tree as follows (written in sort-of-pseudocode 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 Squeak-dev
mailing list
|