func GeneratePrefixes(codes PrefixCodes) error {
	if len(codes) <= 1 {
		if len(codes) == 1 {
			if codes[0].Len != 0 {
				return errorf(errors.Invalid, "degenerate prefix tree with one node")
			}
			codes[0].Val = 0
		}
		return nil
	}
	var bitCnts [valueBits + 1]uint
	c0 := codes[0]
	bitCnts[c0.Len]++
	minBits, maxBits, symLast := c0.Len, c0.Len, c0.Sym
	for _, c := range codes[1:] {
		if c.Sym <= symLast {
			return errorf(errors.Invalid, "non-unique or non-monotonically increasing symbols")
		}
		if minBits > c.Len {
			minBits = c.Len
		}
		if maxBits < c.Len {
			maxBits = c.Len
		}
		bitCnts[c.Len]++  
		symLast = c.Sym   
	}
	if minBits == 0 {
		return errorf(errors.Invalid, "invalid prefix bit-length")
	}
	var nextCodes [valueBits + 1]uint
	var code uint
	for i := minBits; i <= maxBits; i++ {
		code <<= 1
		nextCodes[i] = code
		code += bitCnts[i]
	}
	if code != 1<<maxBits {
		return errorf(errors.Invalid, "degenerate prefix tree")
	}
	for i, c := range codes {
		codes[i].Val = internal.ReverseUint32N(uint32(nextCodes[c.Len]), uint(c.Len))
		nextCodes[c.Len]++
	}
	if internal.Debug && !codes.checkPrefixes() {
		panic("overlapping prefixes detected")
	}
	if internal.Debug && !codes.checkCanonical() {
		panic("non-canonical prefixes detected")
	}
	return nil
}
GeneratePrefixes assigns a prefix value to all codes according to the
bit-lengths. This function is used by both compressors and decompressors.

The input codes must have the Sym and Len fields populated and be
sorted by symbol. The bit-lengths of each code must be properly allocated,
such that it forms a complete tree.

The result will have the Val field populated and will produce a canonical
prefix tree. The resulting codes will remain sorted by symbol.
package prefix
import (
	"fmt"
	"sort"
	"github.com/dsnet/compress/internal"
	"github.com/dsnet/compress/internal/errors"
)
func errorf(c int, f string, a ...interface{}) error {
	return errors.Error{Code: c, Pkg: "prefix", Msg: fmt.Sprintf(f, a...)}
}
func panicf(c int, f string, a ...interface{}) {
	errors.Panic(errorf(c, f, a...))
}
const (
	countBits = 5   
	valueBits = 27  
	countMask = (1 << countBits) - 1
)
type PrefixCode struct {
	Sym uint32  
	Cnt uint32  
	Len uint32  
	Val uint32  
}
type PrefixCodes []PrefixCode
type prefixCodesBySymbol []PrefixCode
func (c prefixCodesBySymbol) Len() int           { return len(c) }
func (c prefixCodesBySymbol) Less(i, j int) bool { return c[i].Sym < c[j].Sym }
func (c prefixCodesBySymbol) Swap(i, j int)      { c[i], c[j] = c[j], c[i] }
type prefixCodesByCount []PrefixCode
func (c prefixCodesByCount) Len() int { return len(c) }
func (c prefixCodesByCount) Less(i, j int) bool {
	return c[i].Cnt < c[j].Cnt || (c[i].Cnt == c[j].Cnt && c[i].Sym < c[j].Sym)
}
func (c prefixCodesByCount) Swap(i, j int) { c[i], c[j] = c[j], c[i] }
func (pc PrefixCodes) SortBySymbol() { sort.Sort(prefixCodesBySymbol(pc)) }
func (pc PrefixCodes) SortByCount()  { sort.Sort(prefixCodesByCount(pc)) }
func (pc PrefixCodes) Length() (nb uint) {
	for _, c := range pc {
		nb += uint(c.Len * c.Cnt)
	}
	return nb
}
func (pc PrefixCodes) checkLengths() bool {
	sum := 1 << valueBits
	for _, c := range pc {
		sum -= (1 << valueBits) >> uint(c.Len)
	}
	return sum == 0 || len(pc) == 0
}
func (pc PrefixCodes) checkPrefixes() bool {
	for i, c1 := range pc {
		for j, c2 := range pc {
			mask := uint32(1)<<c1.Len - 1
			if i != j && c1.Len <= c2.Len && c1.Val&mask == c2.Val&mask {
				return false
			}
		}
	}
	return true
}
func (pc PrefixCodes) checkCanonical() bool {
	var vals [valueBits + 1]PrefixCode
	for _, c := range pc {
		if c.Len > 0 {
			c.Val = internal.ReverseUint32N(c.Val, uint(c.Len))
			if vals[c.Len].Cnt > 0 && vals[c.Len].Val+1 != c.Val {
				return false
			}
			vals[c.Len].Val = c.Val
			vals[c.Len].Cnt++
		}
	}
	var last PrefixCode
	for _, v := range vals {
		if v.Cnt > 0 {
			curVal := v.Val - v.Cnt + 1
			if last.Cnt != 0 && last.Val >= curVal {
				return false
			}
			last = v
		}
	}
	return true
}
func GenerateLengths(codes PrefixCodes, maxBits uint) error {
	if len(codes) <= 1 {
		if len(codes) == 1 {
			codes[0].Len = 0
		}
		return nil
	}
	cntLast := codes[0].Cnt
	for _, c := range codes[1:] {
		if c.Cnt < cntLast {
			return errorf(errors.Invalid, "non-monotonically increasing symbol counts")
		}
		cntLast = c.Cnt
	}
	type node struct {
		cnt uint32
		n0, n1 int  
		c0, c1 *PrefixCode
	}
	var nodeIdx int
	var nodeArr [1024]node  
	nodes := nodeArr[:]
	if len(nodes) < len(codes) {
		nodes = make([]node, len(codes))  
	}
	freqs, queue := codes, nodes[:0]
	for len(freqs)+len(queue) > 1 {
		var n node
		if len(queue) == 0 || (len(freqs) > 0 && freqs[0].Cnt <= queue[0].cnt) {
			n.c0, freqs = &freqs[0], freqs[1:]
			n.cnt += n.c0.Cnt
		} else {
			n.cnt += queue[0].cnt
			n.n0 = nodeIdx  
			nodeIdx++
			queue = queue[1:]
		}
		if len(queue) == 0 || (len(freqs) > 0 && freqs[0].Cnt <= queue[0].cnt) {
			n.c1, freqs = &freqs[0], freqs[1:]
			n.cnt += n.c1.Cnt
		} else {
			n.cnt += queue[0].cnt
			n.n1 = nodeIdx  
			nodeIdx++
			queue = queue[1:]
		}
		queue = append(queue, n)
	}
	rootIdx := nodeIdx
	var fixBits bool
	var explore func(int, uint)
	explore = func(rootIdx int, level uint) {
		root := &nodes[rootIdx]
		if root.c0 == nil {
			explore(root.n0, level+1)
		} else {
			fixBits = fixBits || (level > maxBits)
			root.c0.Len = uint32(level)
		}
		if root.c1 == nil {
			explore(root.n1, level+1)
		} else {
			fixBits = fixBits || (level > maxBits)
			root.c1.Len = uint32(level)
		}
	}
	explore(rootIdx, 1)
	if fixBits {
		var symBitsArr [valueBits + 1]uint32
		symBits := symBitsArr[:]  
		for _, c := range codes {
			for int(c.Len) >= len(symBits) {
				symBits = append(symBits, 0)
			}
			symBits[c.Len]++
		}
		var treeRotate func(uint)
		treeRotate = func(nb uint) {
			if symBits[nb-1] == 0 {
				treeRotate(nb - 1)
			}
			symBits[nb-1] -= 1  
			symBits[nb] += 3    
			symBits[nb+1] -= 2  
		}
		for i := uint(len(symBits)) - 1; i > maxBits; i-- {
			for symBits[i] > 0 {
				treeRotate(i - 1)
			}
		}
		cs := codes
		for nb, cnt := range symBits {
			if cnt > 0 {
				pos := len(cs) - int(cnt)
				cs2 := cs[pos:]
				for i := range cs2 {
					cs2[i].Len = uint32(nb)
				}
				cs = cs[:pos]
			}
		}
		if len(cs) != 0 {
			panic("not all codes were used up")
		}
	}
	if internal.Debug && !codes.checkLengths() {
		panic("incomplete prefix tree detected")
	}
	return nil
}