summaryrefslogtreecommitdiff
path: root/src/pkg/compress/flate/huffman_bit_writer.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/pkg/compress/flate/huffman_bit_writer.go')
-rw-r--r--src/pkg/compress/flate/huffman_bit_writer.go378
1 files changed, 189 insertions, 189 deletions
diff --git a/src/pkg/compress/flate/huffman_bit_writer.go b/src/pkg/compress/flate/huffman_bit_writer.go
index a1ef3694c..eac196dfc 100644
--- a/src/pkg/compress/flate/huffman_bit_writer.go
+++ b/src/pkg/compress/flate/huffman_bit_writer.go
@@ -5,28 +5,28 @@
package flate
import (
- "io";
- "math";
- "os";
- "strconv";
+ "io"
+ "math"
+ "os"
+ "strconv"
)
const (
// The largest offset code.
- offsetCodeCount = 30;
+ offsetCodeCount = 30
// The largest offset code in the extensions.
- extendedOffsetCodeCount = 42;
+ extendedOffsetCodeCount = 42
// The special code used to mark the end of a block.
- endBlockMarker = 256;
+ endBlockMarker = 256
// The first length code.
- lengthCodesStart = 257;
+ lengthCodesStart = 257
// The number of codegen codes.
- codegenCodeCount = 19;
- badCode = 255;
+ codegenCodeCount = 19
+ badCode = 255
)
// The number of extra bits needed by length code X - LENGTH_CODES_START.
@@ -72,28 +72,28 @@ var offsetBase = []uint32{
var codegenOrder = []uint32{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}
type huffmanBitWriter struct {
- w io.Writer;
+ w io.Writer
// Data waiting to be written is bytes[0:nbytes]
// and then the low nbits of bits.
- bits uint32;
- nbits uint32;
- bytes [64]byte;
- nbytes int;
- literalFreq []int32;
- offsetFreq []int32;
- codegen []uint8;
- codegenFreq []int32;
- literalEncoding *huffmanEncoder;
- offsetEncoding *huffmanEncoder;
- codegenEncoding *huffmanEncoder;
- err os.Error;
+ bits uint32
+ nbits uint32
+ bytes [64]byte
+ nbytes int
+ literalFreq []int32
+ offsetFreq []int32
+ codegen []uint8
+ codegenFreq []int32
+ literalEncoding *huffmanEncoder
+ offsetEncoding *huffmanEncoder
+ codegenEncoding *huffmanEncoder
+ err os.Error
}
type WrongValueError struct {
- name string;
- from int32;
- to int32;
- value int32;
+ name string
+ from int32
+ to int32
+ value int32
}
func newHuffmanBitWriter(w io.Writer) *huffmanBitWriter {
@@ -116,46 +116,46 @@ func (err WrongValueError) String() string {
func (w *huffmanBitWriter) flushBits() {
if w.err != nil {
- w.nbits = 0;
- return;
- }
- bits := w.bits;
- w.bits >>= 16;
- w.nbits -= 16;
- n := w.nbytes;
- w.bytes[n] = byte(bits);
- w.bytes[n+1] = byte(bits >> 8);
+ w.nbits = 0
+ return
+ }
+ bits := w.bits
+ w.bits >>= 16
+ w.nbits -= 16
+ n := w.nbytes
+ w.bytes[n] = byte(bits)
+ w.bytes[n+1] = byte(bits >> 8)
if n += 2; n >= len(w.bytes) {
- _, w.err = w.w.Write(&w.bytes);
- n = 0;
+ _, w.err = w.w.Write(&w.bytes)
+ n = 0
}
- w.nbytes = n;
+ w.nbytes = n
}
func (w *huffmanBitWriter) flush() {
if w.err != nil {
- w.nbits = 0;
- return;
+ w.nbits = 0
+ return
}
- n := w.nbytes;
+ n := w.nbytes
if w.nbits > 8 {
- w.bytes[n] = byte(w.bits);
- w.bits >>= 8;
- w.nbits -= 8;
- n++;
+ w.bytes[n] = byte(w.bits)
+ w.bits >>= 8
+ w.nbits -= 8
+ n++
}
if w.nbits > 0 {
- w.bytes[n] = byte(w.bits);
- w.nbits = 0;
- n++;
+ w.bytes[n] = byte(w.bits)
+ w.nbits = 0
+ n++
}
- w.bits = 0;
- _, w.err = w.w.Write(w.bytes[0:n]);
- w.nbytes = 0;
+ w.bits = 0
+ _, w.err = w.w.Write(w.bytes[0:n])
+ w.nbytes = 0
}
func (w *huffmanBitWriter) writeBits(b, nb int32) {
- w.bits |= uint32(b) << w.nbits;
+ w.bits |= uint32(b) << w.nbits
if w.nbits += uint32(nb); w.nbits >= 16 {
w.flushBits()
}
@@ -165,24 +165,24 @@ func (w *huffmanBitWriter) writeBytes(bytes []byte) {
if w.err != nil {
return
}
- n := w.nbytes;
+ n := w.nbytes
if w.nbits == 8 {
- w.bytes[n] = byte(w.bits);
- w.nbits = 0;
- n++;
+ w.bytes[n] = byte(w.bits)
+ w.nbits = 0
+ n++
}
if w.nbits != 0 {
- w.err = InternalError("writeBytes with unfinished bits");
- return;
+ w.err = InternalError("writeBytes with unfinished bits")
+ return
}
if n != 0 {
- _, w.err = w.w.Write(w.bytes[0:n]);
+ _, w.err = w.w.Write(w.bytes[0:n])
if w.err != nil {
return
}
}
- w.nbytes = 0;
- _, w.err = w.w.Write(bytes);
+ w.nbytes = 0
+ _, w.err = w.w.Write(bytes)
}
// RFC 1951 3.2.7 specifies a special run-length encoding for specifiying
@@ -197,82 +197,82 @@ func (w *huffmanBitWriter) writeBytes(bytes []byte) {
// numLiterals The number of literals in literalEncoding
// numOffsets The number of offsets in offsetEncoding
func (w *huffmanBitWriter) generateCodegen(numLiterals int, numOffsets int) {
- fillInt32s(w.codegenFreq, 0);
+ fillInt32s(w.codegenFreq, 0)
// Note that we are using codegen both as a temporary variable for holding
// a copy of the frequencies, and as the place where we put the result.
// This is fine because the output is always shorter than the input used
// so far.
- codegen := w.codegen; // cache
+ codegen := w.codegen // cache
// Copy the concatenated code sizes to codegen. Put a marker at the end.
- copyUint8s(codegen[0:numLiterals], w.literalEncoding.codeBits);
- copyUint8s(codegen[numLiterals:numLiterals+numOffsets], w.offsetEncoding.codeBits);
- codegen[numLiterals+numOffsets] = badCode;
+ copyUint8s(codegen[0:numLiterals], w.literalEncoding.codeBits)
+ copyUint8s(codegen[numLiterals:numLiterals+numOffsets], w.offsetEncoding.codeBits)
+ codegen[numLiterals+numOffsets] = badCode
- size := codegen[0];
- count := 1;
- outIndex := 0;
+ size := codegen[0]
+ count := 1
+ outIndex := 0
for inIndex := 1; size != badCode; inIndex++ {
// INVARIANT: We have seen "count" copies of size that have not yet
// had output generated for them.
- nextSize := codegen[inIndex];
+ nextSize := codegen[inIndex]
if nextSize == size {
- count++;
- continue;
+ count++
+ continue
}
// We need to generate codegen indicating "count" of size.
if size != 0 {
- codegen[outIndex] = size;
- outIndex++;
- w.codegenFreq[size]++;
- count--;
+ codegen[outIndex] = size
+ outIndex++
+ w.codegenFreq[size]++
+ count--
for count >= 3 {
- n := min(count, 6);
- codegen[outIndex] = 16;
- outIndex++;
- codegen[outIndex] = uint8(n - 3);
- outIndex++;
- w.codegenFreq[16]++;
- count -= n;
+ n := min(count, 6)
+ codegen[outIndex] = 16
+ outIndex++
+ codegen[outIndex] = uint8(n - 3)
+ outIndex++
+ w.codegenFreq[16]++
+ count -= n
}
} else {
for count >= 11 {
- n := min(count, 138);
- codegen[outIndex] = 18;
- outIndex++;
- codegen[outIndex] = uint8(n - 11);
- outIndex++;
- w.codegenFreq[18]++;
- count -= n;
+ n := min(count, 138)
+ codegen[outIndex] = 18
+ outIndex++
+ codegen[outIndex] = uint8(n - 11)
+ outIndex++
+ w.codegenFreq[18]++
+ count -= n
}
if count >= 3 {
// count >= 3 && count <= 10
- codegen[outIndex] = 17;
- outIndex++;
- codegen[outIndex] = uint8(count - 3);
- outIndex++;
- w.codegenFreq[17]++;
- count = 0;
+ codegen[outIndex] = 17
+ outIndex++
+ codegen[outIndex] = uint8(count - 3)
+ outIndex++
+ w.codegenFreq[17]++
+ count = 0
}
}
- count--;
+ count--
for ; count >= 0; count-- {
- codegen[outIndex] = size;
- outIndex++;
- w.codegenFreq[size]++;
+ codegen[outIndex] = size
+ outIndex++
+ w.codegenFreq[size]++
}
// Set up invariant for next time through the loop.
- size = nextSize;
- count = 1;
+ size = nextSize
+ count = 1
}
// Marker indicating the end of the codegen.
- codegen[outIndex] = badCode;
+ codegen[outIndex] = badCode
}
func (w *huffmanBitWriter) writeCode(code *huffmanEncoder, literal uint32) {
if w.err != nil {
return
}
- w.writeBits(int32(code.code[literal]), int32(code.codeBits[literal]));
+ w.writeBits(int32(code.code[literal]), int32(code.codeBits[literal]))
}
// Write the header of a dynamic Huffman block to the output stream.
@@ -284,49 +284,49 @@ func (w *huffmanBitWriter) writeDynamicHeader(numLiterals int, numOffsets int, n
if w.err != nil {
return
}
- var firstBits int32 = 4;
+ var firstBits int32 = 4
if isEof {
firstBits = 5
}
- w.writeBits(firstBits, 3);
- w.writeBits(int32(numLiterals-257), 5);
+ w.writeBits(firstBits, 3)
+ w.writeBits(int32(numLiterals-257), 5)
if numOffsets > offsetCodeCount {
// Extended version of deflater
- w.writeBits(int32(offsetCodeCount+((numOffsets-(1+offsetCodeCount))>>3)), 5);
- w.writeBits(int32((numOffsets-(1+offsetCodeCount))&0x7), 3);
+ w.writeBits(int32(offsetCodeCount+((numOffsets-(1+offsetCodeCount))>>3)), 5)
+ w.writeBits(int32((numOffsets-(1+offsetCodeCount))&0x7), 3)
} else {
w.writeBits(int32(numOffsets-1), 5)
}
- w.writeBits(int32(numCodegens-4), 4);
+ w.writeBits(int32(numCodegens-4), 4)
for i := 0; i < numCodegens; i++ {
- value := w.codegenEncoding.codeBits[codegenOrder[i]];
- w.writeBits(int32(value), 3);
+ value := w.codegenEncoding.codeBits[codegenOrder[i]]
+ w.writeBits(int32(value), 3)
}
- i := 0;
+ i := 0
for {
- var codeWord int = int(w.codegen[i]);
- i++;
+ var codeWord int = int(w.codegen[i])
+ i++
if codeWord == badCode {
break
}
// The low byte contains the actual code to generate.
- w.writeCode(w.codegenEncoding, uint32(codeWord));
+ w.writeCode(w.codegenEncoding, uint32(codeWord))
switch codeWord {
case 16:
- w.writeBits(int32(w.codegen[i]), 2);
- i++;
- break;
+ w.writeBits(int32(w.codegen[i]), 2)
+ i++
+ break
case 17:
- w.writeBits(int32(w.codegen[i]), 3);
- i++;
- break;
+ w.writeBits(int32(w.codegen[i]), 3)
+ i++
+ break
case 18:
- w.writeBits(int32(w.codegen[i]), 7);
- i++;
- break;
+ w.writeBits(int32(w.codegen[i]), 7)
+ i++
+ break
}
}
}
@@ -335,14 +335,14 @@ func (w *huffmanBitWriter) writeStoredHeader(length int, isEof bool) {
if w.err != nil {
return
}
- var flag int32;
+ var flag int32
if isEof {
flag = 1
}
- w.writeBits(flag, 3);
- w.flush();
- w.writeBits(int32(length), 16);
- w.writeBits(int32(^uint16(length)), 16);
+ w.writeBits(flag, 3)
+ w.flush()
+ w.writeBits(int32(length), 16)
+ w.writeBits(int32(^uint16(length)), 16)
}
func (w *huffmanBitWriter) writeFixedHeader(isEof bool) {
@@ -350,61 +350,61 @@ func (w *huffmanBitWriter) writeFixedHeader(isEof bool) {
return
}
// Indicate that we are a fixed Huffman block
- var value int32 = 2;
+ var value int32 = 2
if isEof {
value = 3
}
- w.writeBits(value, 3);
+ w.writeBits(value, 3)
}
func (w *huffmanBitWriter) writeBlock(tokens []token, eof bool, input []byte) {
if w.err != nil {
return
}
- fillInt32s(w.literalFreq, 0);
- fillInt32s(w.offsetFreq, 0);
+ fillInt32s(w.literalFreq, 0)
+ fillInt32s(w.offsetFreq, 0)
- n := len(tokens);
- tokens = tokens[0 : n+1];
- tokens[n] = endBlockMarker;
+ n := len(tokens)
+ tokens = tokens[0 : n+1]
+ tokens[n] = endBlockMarker
- totalLength := -1; // Subtract 1 for endBlock.
+ totalLength := -1 // Subtract 1 for endBlock.
for _, t := range tokens {
switch t.typ() {
case literalType:
- w.literalFreq[t.literal()]++;
- totalLength++;
- break;
+ w.literalFreq[t.literal()]++
+ totalLength++
+ break
case matchType:
- length := t.length();
- offset := t.offset();
- totalLength += int(length + 3);
- w.literalFreq[lengthCodesStart+lengthCode(length)]++;
- w.offsetFreq[offsetCode(offset)]++;
- break;
+ length := t.length()
+ offset := t.offset()
+ totalLength += int(length + 3)
+ w.literalFreq[lengthCodesStart+lengthCode(length)]++
+ w.offsetFreq[offsetCode(offset)]++
+ break
}
}
- w.literalEncoding.generate(w.literalFreq, 15);
- w.offsetEncoding.generate(w.offsetFreq, 15);
+ w.literalEncoding.generate(w.literalFreq, 15)
+ w.offsetEncoding.generate(w.offsetFreq, 15)
// get the number of literals
- numLiterals := len(w.literalFreq);
+ numLiterals := len(w.literalFreq)
for w.literalFreq[numLiterals-1] == 0 {
numLiterals--
}
// get the number of offsets
- numOffsets := len(w.offsetFreq);
+ numOffsets := len(w.offsetFreq)
for numOffsets > 1 && w.offsetFreq[numOffsets-1] == 0 {
numOffsets--
}
- storedBytes := 0;
+ storedBytes := 0
if input != nil {
storedBytes = len(input)
}
- var extraBits int64;
- var storedSize int64;
+ var extraBits int64
+ var storedSize int64
if storedBytes <= maxStoreBlockSize && input != nil {
- storedSize = int64((storedBytes + 5) * 8);
+ storedSize = int64((storedBytes + 5) * 8)
// We only bother calculating the costs of the extra bits required by
// the length of offset fields (which will be the same for both fixed
// and dynamic encoding), if we need to compare those two encodings
@@ -423,7 +423,7 @@ func (w *huffmanBitWriter) writeBlock(tokens []token, eof bool, input []byte) {
// Figure out which generates smaller code, fixed Huffman, dynamic
// Huffman, or just storing the data.
- var fixedSize int64 = math.MaxInt64;
+ var fixedSize int64 = math.MaxInt64
if numOffsets <= offsetCodeCount {
fixedSize = int64(3) +
fixedLiteralEncoding.bitLength(w.literalFreq) +
@@ -432,13 +432,13 @@ func (w *huffmanBitWriter) writeBlock(tokens []token, eof bool, input []byte) {
}
// Generate codegen and codegenFrequencies, which indicates how to encode
// the literalEncoding and the offsetEncoding.
- w.generateCodegen(numLiterals, numOffsets);
- w.codegenEncoding.generate(w.codegenFreq, 7);
- numCodegens := len(w.codegenFreq);
+ w.generateCodegen(numLiterals, numOffsets)
+ w.codegenEncoding.generate(w.codegenFreq, 7)
+ numCodegens := len(w.codegenFreq)
for numCodegens > 4 && w.codegenFreq[codegenOrder[numCodegens-1]] == 0 {
numCodegens--
}
- extensionSummand := 0;
+ extensionSummand := 0
if numOffsets > offsetCodeCount {
extensionSummand = 3
}
@@ -449,56 +449,56 @@ func (w *huffmanBitWriter) writeBlock(tokens []token, eof bool, input []byte) {
int64(extraBits) +
int64(w.codegenFreq[16]*2) +
int64(w.codegenFreq[17]*3) +
- int64(w.codegenFreq[18]*7);
+ int64(w.codegenFreq[18]*7)
dynamicSize := dynamicHeader +
w.literalEncoding.bitLength(w.literalFreq) +
- w.offsetEncoding.bitLength(w.offsetFreq);
+ w.offsetEncoding.bitLength(w.offsetFreq)
if storedSize < fixedSize && storedSize < dynamicSize {
- w.writeStoredHeader(storedBytes, eof);
- w.writeBytes(input[0:storedBytes]);
- return;
+ w.writeStoredHeader(storedBytes, eof)
+ w.writeBytes(input[0:storedBytes])
+ return
}
- var literalEncoding *huffmanEncoder;
- var offsetEncoding *huffmanEncoder;
+ var literalEncoding *huffmanEncoder
+ var offsetEncoding *huffmanEncoder
if fixedSize <= dynamicSize {
- w.writeFixedHeader(eof);
- literalEncoding = fixedLiteralEncoding;
- offsetEncoding = fixedOffsetEncoding;
+ w.writeFixedHeader(eof)
+ literalEncoding = fixedLiteralEncoding
+ offsetEncoding = fixedOffsetEncoding
} else {
// Write the header.
- w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof);
- literalEncoding = w.literalEncoding;
- offsetEncoding = w.offsetEncoding;
+ w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
+ literalEncoding = w.literalEncoding
+ offsetEncoding = w.offsetEncoding
}
// Write the tokens.
for _, t := range tokens {
switch t.typ() {
case literalType:
- w.writeCode(literalEncoding, t.literal());
- break;
+ w.writeCode(literalEncoding, t.literal())
+ break
case matchType:
// Write the length
- length := t.length();
- lengthCode := lengthCode(length);
- w.writeCode(literalEncoding, lengthCode+lengthCodesStart);
- extraLengthBits := int32(lengthExtraBits[lengthCode]);
+ length := t.length()
+ lengthCode := lengthCode(length)
+ w.writeCode(literalEncoding, lengthCode+lengthCodesStart)
+ extraLengthBits := int32(lengthExtraBits[lengthCode])
if extraLengthBits > 0 {
- extraLength := int32(length - lengthBase[lengthCode]);
- w.writeBits(extraLength, extraLengthBits);
+ extraLength := int32(length - lengthBase[lengthCode])
+ w.writeBits(extraLength, extraLengthBits)
}
// Write the offset
- offset := t.offset();
- offsetCode := offsetCode(offset);
- w.writeCode(offsetEncoding, offsetCode);
- extraOffsetBits := int32(offsetExtraBits[offsetCode]);
+ offset := t.offset()
+ offsetCode := offsetCode(offset)
+ w.writeCode(offsetEncoding, offsetCode)
+ extraOffsetBits := int32(offsetExtraBits[offsetCode])
if extraOffsetBits > 0 {
- extraOffset := int32(offset - offsetBase[offsetCode]);
- w.writeBits(extraOffset, extraOffsetBits);
+ extraOffset := int32(offset - offsetBase[offsetCode])
+ w.writeBits(extraOffset, extraOffsetBits)
}
- break;
+ break
default:
panic("unknown token type: " + string(t))
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-30 18:12:39 +0000