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