func()

in flexflate/huffman_bit_writer.go [370:517]

• 118 lines of code
• 26 McCabe index (conditional complexity)

func (w *huffmanBitWriter) writeBlock(tokens []token, eof bool, input []byte) {
	if w.err != nil {
		return
	}
	for i := range w.literalFreq {
		w.literalFreq[i] = 0
	}
	for i := range w.offsetFreq {
		w.offsetFreq[i] = 0
	}

	n := len(tokens)
	tokens = tokens[0 : n+1]
	tokens[n] = endBlockMarker

	for _, t := range tokens {
		switch t.typ() {
		case literalType:
			w.literalFreq[t.literal()]++
		case matchType:
			length := t.length()
			offset := t.offset()
			w.literalFreq[lengthCodesStart+lengthCode(length)]++
			w.offsetFreq[offsetCode(offset)]++
		}
	}

	// get the number of literals
	numLiterals := len(w.literalFreq)
	for w.literalFreq[numLiterals-1] == 0 {
		numLiterals--
	}
	// get the number of offsets
	numOffsets := len(w.offsetFreq)
	for numOffsets > 0 && w.offsetFreq[numOffsets-1] == 0 {
		numOffsets--
	}
	if numOffsets == 0 {
		// We haven't found a single match. If we want to go with the dynamic encoding,
		// we should count at least one offset to be sure that the offset huffman tree could be encoded.
		w.offsetFreq[0] = 1
		numOffsets = 1
	}

	w.literalEncoding.generate(w.literalFreq, 15)
	w.offsetEncoding.generate(w.offsetFreq, 15)

	storedBytes := 0
	if input != nil {
		storedBytes = len(input)
	}
	var extraBits int64
	var storedSize int64 = math.MaxInt64
	if storedBytes <= maxStoreBlockSize && input != nil {
		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
		// against stored encoding.
		for lengthCode := lengthCodesStart + 8; lengthCode < numLiterals; lengthCode++ {
			// First eight length codes have extra size = 0.
			extraBits += int64(w.literalFreq[lengthCode]) * int64(lengthExtraBits[lengthCode-lengthCodesStart])
		}
		for offsetCode := 4; offsetCode < numOffsets; offsetCode++ {
			// First four offset codes have extra size = 0.
			extraBits += int64(w.offsetFreq[offsetCode]) * int64(offsetExtraBits[offsetCode])
		}
	}

	// Figure out smallest code.
	// Fixed Huffman baseline.
	var size = int64(3) +
		fixedLiteralEncoding.bitLength(w.literalFreq) +
		fixedOffsetEncoding.bitLength(w.offsetFreq) +
		extraBits
	var literalEncoding = fixedLiteralEncoding
	var offsetEncoding = fixedOffsetEncoding

	// Dynamic Huffman?
	var numCodegens int

	// 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)
	for numCodegens > 4 && w.codegenFreq[codegenOrder[numCodegens-1]] == 0 {
		numCodegens--
	}
	dynamicHeader := int64(3+5+5+4+(3*numCodegens)) +
		w.codegenEncoding.bitLength(w.codegenFreq) +
		int64(extraBits) +
		int64(w.codegenFreq[16]*2) +
		int64(w.codegenFreq[17]*3) +
		int64(w.codegenFreq[18]*7)
	dynamicSize := dynamicHeader +
		w.literalEncoding.bitLength(w.literalFreq) +
		w.offsetEncoding.bitLength(w.offsetFreq)

	if dynamicSize < size {
		size = dynamicSize
		literalEncoding = w.literalEncoding
		offsetEncoding = w.offsetEncoding
	}

	// Stored bytes?
	if storedSize < size {
		w.writeStoredHeader(storedBytes, eof)
		w.writeBytes(input[0:storedBytes])
		return
	}

	// Huffman.
	if literalEncoding == fixedLiteralEncoding {
		w.writeFixedHeader(eof)
	} else {
		w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
	}
	for _, t := range tokens {
		switch t.typ() {
		case literalType:
			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])
			if extraLengthBits > 0 {
				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])
			if extraOffsetBits > 0 {
				extraOffset := int32(offset - offsetBase[offsetCode])
				w.writeBits(extraOffset, extraOffsetBits)
			}
			break
		default:
			panic("unknown token type: " + string(t))
		}
	}
}