func buildTable()

in wim/lzx/lzx.go [154:220]

• 54 lines of code
• 13 McCabe index (conditional complexity)

func buildTable(codelens []byte) *huffman {
	// Determine the number of codes of each length, and the
	// maximum length.
	var count [maxTreePathLen + 1]uint
	var max byte
	for _, cl := range codelens {
		count[cl]++
		if max < cl {
			max = cl
		}
	}

	if max == 0 {
		return &huffman{}
	}

	// Determine the first code of each length.
	var first [maxTreePathLen + 1]uint
	code := uint(0)
	for i := byte(1); i <= max; i++ {
		code <<= 1
		first[i] = code
		code += count[i]
	}

	if code != 1<<max {
		return nil
	}

	// Build a table for code lookup. For code sizes < max,
	// put all possible suffixes for the code into the table, too.
	// For max > tablebits, split long codes into additional tables
	// of suffixes of max-tablebits length.
	h := &huffman{maxbits: max}
	if max > tablebits {
		core := first[tablebits+1] / 2 // Number of codes that fit without extra tables
		nextra := 1<<tablebits - core  // Number of extra entries
		h.extra = make([][]uint16, nextra)
		for code := core; code < 1<<tablebits; code++ {
			h.table[code] = uint16(code - core)
			h.extra[code-core] = make([]uint16, 1<<(max-tablebits))
		}
	}

	for i, cl := range codelens {
		if cl != 0 {
			code := first[cl]
			first[cl]++
			v := uint16(cl)<<lenshift | uint16(i)
			if cl <= tablebits {
				extendedCode := code << (tablebits - cl)
				for j := uint(0); j < 1<<(tablebits-cl); j++ {
					h.table[extendedCode+j] = v
				}
			} else {
				prefix := code >> (cl - tablebits)
				suffix := code & (1<<(cl-tablebits) - 1)
				extendedCode := suffix << (max - cl)
				for j := uint(0); j < 1<<(max-cl); j++ {
					h.extra[h.table[prefix]][extendedCode+j] = v
				}
			}
		}
	}

	return h
}