1// Copyright 2015, Joe Tsai. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE.md file.
4
5package prefix
6
7import (
8	"sort"
9
10	"github.com/dsnet/compress/internal"
11)
12
13type Encoder struct {
14	chunks    []uint32 // First-level lookup map
15	chunkMask uint32   // Mask the length of the chunks table
16
17	NumSyms uint32 // Number of symbols
18}
19
20// Init initializes Encoder according to the codes provided.
21func (pe *Encoder) Init(codes PrefixCodes) {
22	// Handle special case trees.
23	if len(codes) <= 1 {
24		switch {
25		case len(codes) == 0: // Empty tree (should error if used later)
26			*pe = Encoder{chunks: pe.chunks[:0], NumSyms: 0}
27		case len(codes) == 1 && codes[0].Len == 0: // Single code tree (bit-length of zero)
28			pe.chunks = append(pe.chunks[:0], codes[0].Val<<countBits|0)
29			*pe = Encoder{chunks: pe.chunks[:1], NumSyms: 1}
30		default:
31			panic("invalid codes")
32		}
33		return
34	}
35	if internal.Debug && !sort.IsSorted(prefixCodesBySymbol(codes)) {
36		panic("input codes is not sorted")
37	}
38	if internal.Debug && !(codes.checkLengths() && codes.checkPrefixes()) {
39		panic("detected incomplete or overlapping codes")
40	}
41
42	// Enough chunks to contain all the symbols.
43	numChunks := 1
44	for n := len(codes) - 1; n > 0; n >>= 1 {
45		numChunks <<= 1
46	}
47	pe.NumSyms = uint32(len(codes))
48
49retry:
50	// Allocate and reset chunks.
51	pe.chunks = allocUint32s(pe.chunks, numChunks)
52	pe.chunkMask = uint32(numChunks - 1)
53	for i := range pe.chunks {
54		pe.chunks[i] = 0 // Logic below relies on zero value as uninitialized
55	}
56
57	// Insert each symbol, checking that there are no conflicts.
58	for _, c := range codes {
59		if pe.chunks[c.Sym&pe.chunkMask] > 0 {
60			// Collision found our "hash" table, so grow and try again.
61			numChunks <<= 1
62			goto retry
63		}
64		pe.chunks[c.Sym&pe.chunkMask] = c.Val<<countBits | c.Len
65	}
66}
67