vendor/github.com/klauspost/compress/zstd/dict.go - voltha-go - Gitiles

 package zstd

 import (
 	"bytes"
 	"encoding/binary"
 	"errors"
 	"fmt"
 	"io"
 	"math"
 	"sort"

 	"github.com/klauspost/compress/huff0"
 )

 type dict struct {
 	id uint32

 	litEnc              *huff0.Scratch
 	llDec, ofDec, mlDec sequenceDec
 	offsets             [3]int
 	content             []byte
 }

 const dictMagic = "\x37\xa4\x30\xec"

 // Maximum dictionary size for the reference implementation (1.5.3) is 2 GiB.
 const dictMaxLength = 1 << 31

 // ID returns the dictionary id or 0 if d is nil.
 func (d *dict) ID() uint32 {
 	if d == nil {
 		return 0
 	}
 	return d.id
 }

 // ContentSize returns the dictionary content size or 0 if d is nil.
 func (d *dict) ContentSize() int {
 	if d == nil {
 		return 0
 	}
 	return len(d.content)
 }

 // Content returns the dictionary content.
 func (d *dict) Content() []byte {
 	if d == nil {
 		return nil
 	}
 	return d.content
 }

 // Offsets returns the initial offsets.
 func (d *dict) Offsets() [3]int {
 	if d == nil {
 		return [3]int{}
 	}
 	return d.offsets
 }

 // LitEncoder returns the literal encoder.
 func (d *dict) LitEncoder() *huff0.Scratch {
 	if d == nil {
 		return nil
 	}
 	return d.litEnc
 }

 // Load a dictionary as described in
 // https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#dictionary-format
 func loadDict(b []byte) (*dict, error) {
 	// Check static field size.
 	if len(b) <= 8+(3*4) {
 		return nil, io.ErrUnexpectedEOF
 	}
 	d := dict{
 		llDec: sequenceDec{fse: &fseDecoder{}},
 		ofDec: sequenceDec{fse: &fseDecoder{}},
 		mlDec: sequenceDec{fse: &fseDecoder{}},
 	}
 	if string(b[:4]) != dictMagic {
 		return nil, ErrMagicMismatch
 	}
 	d.id = binary.LittleEndian.Uint32(b[4:8])
 	if d.id == 0 {
 		return nil, errors.New("dictionaries cannot have ID 0")
 	}

 	// Read literal table
 	var err error
 	d.litEnc, b, err = huff0.ReadTable(b[8:], nil)
 	if err != nil {
 		return nil, fmt.Errorf("loading literal table: %w", err)
 	}
 	d.litEnc.Reuse = huff0.ReusePolicyMust

 	br := byteReader{
 		b:   b,
 		off: 0,
 	}
 	readDec := func(i tableIndex, dec *fseDecoder) error {
 		if err := dec.readNCount(&br, uint16(maxTableSymbol[i])); err != nil {
 			return err
 		}
 		if br.overread() {
 			return io.ErrUnexpectedEOF
 		}
 		err = dec.transform(symbolTableX[i])
 		if err != nil {
 			println("Transform table error:", err)
 			return err
 		}
 		if debugDecoder || debugEncoder {
 			println("Read table ok", "symbolLen:", dec.symbolLen)
 		}
 		// Set decoders as predefined so they aren't reused.
 		dec.preDefined = true
 		return nil
 	}

 	if err := readDec(tableOffsets, d.ofDec.fse); err != nil {
 		return nil, err
 	}
 	if err := readDec(tableMatchLengths, d.mlDec.fse); err != nil {
 		return nil, err
 	}
 	if err := readDec(tableLiteralLengths, d.llDec.fse); err != nil {
 		return nil, err
 	}
 	if br.remain() < 12 {
 		return nil, io.ErrUnexpectedEOF
 	}

 	d.offsets[0] = int(br.Uint32())
 	br.advance(4)
 	d.offsets[1] = int(br.Uint32())
 	br.advance(4)
 	d.offsets[2] = int(br.Uint32())
 	br.advance(4)
 	if d.offsets[0] <= 0 || d.offsets[1] <= 0 || d.offsets[2] <= 0 {
 		return nil, errors.New("invalid offset in dictionary")
 	}
 	d.content = make([]byte, br.remain())
 	copy(d.content, br.unread())
 	if d.offsets[0] > len(d.content) || d.offsets[1] > len(d.content) || d.offsets[2] > len(d.content) {
 		return nil, fmt.Errorf("initial offset bigger than dictionary content size %d, offsets: %v", len(d.content), d.offsets)
 	}

 	return &d, nil
 }

 // InspectDictionary loads a zstd dictionary and provides functions to inspect the content.
 func InspectDictionary(b []byte) (interface {
 	ID() uint32
 	ContentSize() int
 	Content() []byte
 	Offsets() [3]int
 	LitEncoder() *huff0.Scratch
 }, error) {
 	initPredefined()
 	d, err := loadDict(b)
 	return d, err
 }

 type BuildDictOptions struct {
 	// Dictionary ID.
 	ID uint32

 	// Content to use to create dictionary tables.
 	Contents [][]byte

 	// History to use for all blocks.
 	History []byte

 	// Offsets to use.
 	Offsets [3]int

 	// CompatV155 will make the dictionary compatible with Zstd v1.5.5 and earlier.
 	// See https://github.com/facebook/zstd/issues/3724
 	CompatV155 bool

 	// Use the specified encoder level.
 	// The dictionary will be built using the specified encoder level,
 	// which will reflect speed and make the dictionary tailored for that level.
 	// If not set SpeedBestCompression will be used.
 	Level EncoderLevel

 	// DebugOut will write stats and other details here if set.
 	DebugOut io.Writer
 }

 func BuildDict(o BuildDictOptions) ([]byte, error) {
 	initPredefined()
 	hist := o.History
 	contents := o.Contents
 	debug := o.DebugOut != nil
 	println := func(args ...interface{}) {
 		if o.DebugOut != nil {
 			fmt.Fprintln(o.DebugOut, args...)
 		}
 	}
 	printf := func(s string, args ...interface{}) {
 		if o.DebugOut != nil {
 			fmt.Fprintf(o.DebugOut, s, args...)
 		}
 	}
 	print := func(args ...interface{}) {
 		if o.DebugOut != nil {
 			fmt.Fprint(o.DebugOut, args...)
 		}
 	}

 	if int64(len(hist)) > dictMaxLength {
 		return nil, fmt.Errorf("dictionary of size %d > %d", len(hist), int64(dictMaxLength))
 	}
 	if len(hist) < 8 {
 		return nil, fmt.Errorf("dictionary of size %d < %d", len(hist), 8)
 	}
 	if len(contents) == 0 {
 		return nil, errors.New("no content provided")
 	}
 	d := dict{
 		id:      o.ID,
 		litEnc:  nil,
 		llDec:   sequenceDec{},
 		ofDec:   sequenceDec{},
 		mlDec:   sequenceDec{},
 		offsets: o.Offsets,
 		content: hist,
 	}
 	block := blockEnc{lowMem: false}
 	block.init()
 	enc := encoder(&bestFastEncoder{fastBase: fastBase{maxMatchOff: int32(maxMatchLen), bufferReset: math.MaxInt32 - int32(maxMatchLen*2), lowMem: false}})
 	if o.Level != 0 {
 		eOpts := encoderOptions{
 			level:      o.Level,
 			blockSize:  maxMatchLen,
 			windowSize: maxMatchLen,
 			dict:       &d,
 			lowMem:     false,
 		}
 		enc = eOpts.encoder()
 	} else {
 		o.Level = SpeedBestCompression
 	}
 	var (
 		remain [256]int
 		ll     [256]int
 		ml     [256]int
 		of     [256]int
 	)
 	addValues := func(dst *[256]int, src []byte) {
 		for _, v := range src {
 			dst[v]++
 		}
 	}
 	addHist := func(dst *[256]int, src *[256]uint32) {
 		for i, v := range src {
 			dst[i] += int(v)
 		}
 	}
 	seqs := 0
 	nUsed := 0
 	litTotal := 0
 	newOffsets := make(map[uint32]int, 1000)
 	for _, b := range contents {
 		block.reset(nil)
 		if len(b) < 8 {
 			continue
 		}
 		nUsed++
 		enc.Reset(&d, true)
 		enc.Encode(&block, b)
 		addValues(&remain, block.literals)
 		litTotal += len(block.literals)
 		if len(block.sequences) == 0 {
 			continue
 		}
 		seqs += len(block.sequences)
 		block.genCodes()
 		addHist(&ll, block.coders.llEnc.Histogram())
 		addHist(&ml, block.coders.mlEnc.Histogram())
 		addHist(&of, block.coders.ofEnc.Histogram())
 		for i, seq := range block.sequences {
 			if i > 3 {
 				break
 			}
 			offset := seq.offset
 			if offset == 0 {
 				continue
 			}
 			if int(offset) >= len(o.History) {
 				continue
 			}
 			if offset > 3 {
 				newOffsets[offset-3]++
 			} else {
 				newOffsets[uint32(o.Offsets[offset-1])]++
 			}
 		}
 	}
 	// Find most used offsets.
 	var sortedOffsets []uint32
 	for k := range newOffsets {
 		sortedOffsets = append(sortedOffsets, k)
 	}
 	sort.Slice(sortedOffsets, func(i, j int) bool {
 		a, b := sortedOffsets[i], sortedOffsets[j]
 		if a == b {
 			// Prefer the longer offset
 			return sortedOffsets[i] > sortedOffsets[j]
 		}
 		return newOffsets[sortedOffsets[i]] > newOffsets[sortedOffsets[j]]
 	})
 	if len(sortedOffsets) > 3 {
 		if debug {
 			print("Offsets:")
 			for i, v := range sortedOffsets {
 				if i > 20 {
 					break
 				}
 				printf("[%d: %d],", v, newOffsets[v])
 			}
 			println("")
 		}

 		sortedOffsets = sortedOffsets[:3]
 	}
 	for i, v := range sortedOffsets {
 		o.Offsets[i] = int(v)
 	}
 	if debug {
 		println("New repeat offsets", o.Offsets)
 	}

 	if nUsed == 0 || seqs == 0 {
 		return nil, fmt.Errorf("%d blocks, %d sequences found", nUsed, seqs)
 	}
 	if debug {
 		println("Sequences:", seqs, "Blocks:", nUsed, "Literals:", litTotal)
 	}
 	if seqs/nUsed < 512 {
 		// Use 512 as minimum.
 		nUsed = seqs / 512
 		if nUsed == 0 {
 			nUsed = 1
 		}
 	}
 	copyHist := func(dst *fseEncoder, src *[256]int) ([]byte, error) {
 		hist := dst.Histogram()
 		var maxSym uint8
 		var maxCount int
 		var fakeLength int
 		for i, v := range src {
 			if v > 0 {
 				v = v / nUsed
 				if v == 0 {
 					v = 1
 				}
 			}
 			if v > maxCount {
 				maxCount = v
 			}
 			if v != 0 {
 				maxSym = uint8(i)
 			}
 			fakeLength += v
 			hist[i] = uint32(v)
 		}

 		// Ensure we aren't trying to represent RLE.
 		if maxCount == fakeLength {
 			for i := range hist {
 				if uint8(i) == maxSym {
 					fakeLength++
 					maxSym++
 					hist[i+1] = 1
 					if maxSym > 1 {
 						break
 					}
 				}
 				if hist[0] == 0 {
 					fakeLength++
 					hist[i] = 1
 					if maxSym > 1 {
 						break
 					}
 				}
 			}
 		}

 		dst.HistogramFinished(maxSym, maxCount)
 		dst.reUsed = false
 		dst.useRLE = false
 		err := dst.normalizeCount(fakeLength)
 		if err != nil {
 			return nil, err
 		}
 		if debug {
 			println("RAW:", dst.count[:maxSym+1], "NORM:", dst.norm[:maxSym+1], "LEN:", fakeLength)
 		}
 		return dst.writeCount(nil)
 	}
 	if debug {
 		print("Literal lengths: ")
 	}
 	llTable, err := copyHist(block.coders.llEnc, &ll)
 	if err != nil {
 		return nil, err
 	}
 	if debug {
 		print("Match lengths: ")
 	}
 	mlTable, err := copyHist(block.coders.mlEnc, &ml)
 	if err != nil {
 		return nil, err
 	}
 	if debug {
 		print("Offsets: ")
 	}
 	ofTable, err := copyHist(block.coders.ofEnc, &of)
 	if err != nil {
 		return nil, err
 	}

 	// Literal table
 	avgSize := litTotal
 	if avgSize > huff0.BlockSizeMax/2 {
 		avgSize = huff0.BlockSizeMax / 2
 	}
 	huffBuff := make([]byte, 0, avgSize)
 	// Target size
 	div := litTotal / avgSize
 	if div < 1 {
 		div = 1
 	}
 	if debug {
 		println("Huffman weights:")
 	}
 	for i, n := range remain[:] {
 		if n > 0 {
 			n = n / div
 			// Allow all entries to be represented.
 			if n == 0 {
 				n = 1
 			}
 			huffBuff = append(huffBuff, bytes.Repeat([]byte{byte(i)}, n)...)
 			if debug {
 				printf("[%d: %d], ", i, n)
 			}
 		}
 	}
 	if o.CompatV155 && remain[255]/div == 0 {
 		huffBuff = append(huffBuff, 255)
 	}
 	scratch := &huff0.Scratch{TableLog: 11}
 	for tries := 0; tries < 255; tries++ {
 		scratch = &huff0.Scratch{TableLog: 11}
 		_, _, err = huff0.Compress1X(huffBuff, scratch)
 		if err == nil {
 			break
 		}
 		if debug {
 			printf("Try %d: Huffman error: %v\n", tries+1, err)
 		}
 		huffBuff = huffBuff[:0]
 		if tries == 250 {
 			if debug {
 				println("Huffman: Bailing out with predefined table")
 			}

 			// Bail out.... Just generate something
 			huffBuff = append(huffBuff, bytes.Repeat([]byte{255}, 10000)...)
 			for i := 0; i < 128; i++ {
 				huffBuff = append(huffBuff, byte(i))
 			}
 			continue
 		}
 		if errors.Is(err, huff0.ErrIncompressible) {
 			// Try truncating least common.
 			for i, n := range remain[:] {
 				if n > 0 {
 					n = n / (div * (i + 1))
 					if n > 0 {
 						huffBuff = append(huffBuff, bytes.Repeat([]byte{byte(i)}, n)...)
 					}
 				}
 			}
 			if o.CompatV155 && len(huffBuff) > 0 && huffBuff[len(huffBuff)-1] != 255 {
 				huffBuff = append(huffBuff, 255)
 			}
 			if len(huffBuff) == 0 {
 				huffBuff = append(huffBuff, 0, 255)
 			}
 		}
 		if errors.Is(err, huff0.ErrUseRLE) {
 			for i, n := range remain[:] {
 				n = n / (div * (i + 1))
 				// Allow all entries to be represented.
 				if n == 0 {
 					n = 1
 				}
 				huffBuff = append(huffBuff, bytes.Repeat([]byte{byte(i)}, n)...)
 			}
 		}
 	}

 	var out bytes.Buffer
 	out.Write([]byte(dictMagic))
 	out.Write(binary.LittleEndian.AppendUint32(nil, o.ID))
 	out.Write(scratch.OutTable)
 	if debug {
 		println("huff table:", len(scratch.OutTable), "bytes")
 		println("of table:", len(ofTable), "bytes")
 		println("ml table:", len(mlTable), "bytes")
 		println("ll table:", len(llTable), "bytes")
 	}
 	out.Write(ofTable)
 	out.Write(mlTable)
 	out.Write(llTable)
 	out.Write(binary.LittleEndian.AppendUint32(nil, uint32(o.Offsets[0])))
 	out.Write(binary.LittleEndian.AppendUint32(nil, uint32(o.Offsets[1])))
 	out.Write(binary.LittleEndian.AppendUint32(nil, uint32(o.Offsets[2])))
 	out.Write(hist)
 	if debug {
 		_, err := loadDict(out.Bytes())
 		if err != nil {
 			panic(err)
 		}
 		i, err := InspectDictionary(out.Bytes())
 		if err != nil {
 			panic(err)
 		}
 		println("ID:", i.ID())
 		println("Content size:", i.ContentSize())
 		println("Encoder:", i.LitEncoder() != nil)
 		println("Offsets:", i.Offsets())
 		var totalSize int
 		for _, b := range contents {
 			totalSize += len(b)
 		}

 		encWith := func(opts ...EOption) int {
 			enc, err := NewWriter(nil, opts...)
 			if err != nil {
 				panic(err)
 			}
 			defer enc.Close()
 			var dst []byte
 			var totalSize int
 			for _, b := range contents {
 				dst = enc.EncodeAll(b, dst[:0])
 				totalSize += len(dst)
 			}
 			return totalSize
 		}
 		plain := encWith(WithEncoderLevel(o.Level))
 		withDict := encWith(WithEncoderLevel(o.Level), WithEncoderDict(out.Bytes()))
 		println("Input size:", totalSize)
 		println("Plain Compressed:", plain)
 		println("Dict Compressed:", withDict)
 		println("Saved:", plain-withDict, (plain-withDict)/len(contents), "bytes per input (rounded down)")
 	}
 	return out.Bytes(), nil
 }
	package zstd

	import (
	"bytes"
	"encoding/binary"
	"errors"
	"fmt"
	"io"
	"math"
	"sort"

	"github.com/klauspost/compress/huff0"
	)

	type dict struct {
	id uint32

	litEnc *huff0.Scratch
	llDec, ofDec, mlDec sequenceDec
	offsets [3]int
	content []byte
	}

	const dictMagic = "\x37\xa4\x30\xec"

	// Maximum dictionary size for the reference implementation (1.5.3) is 2 GiB.
	const dictMaxLength = 1 << 31

	// ID returns the dictionary id or 0 if d is nil.
	func (d *dict) ID() uint32 {
	if d == nil {
	return 0
	}
	return d.id
	}

	// ContentSize returns the dictionary content size or 0 if d is nil.
	func (d *dict) ContentSize() int {
	if d == nil {
	return 0
	}
	return len(d.content)
	}

	// Content returns the dictionary content.
	func (d *dict) Content() []byte {
	if d == nil {
	return nil
	}
	return d.content
	}

	// Offsets returns the initial offsets.
	func (d *dict) Offsets() [3]int {
	if d == nil {
	return [3]int{}
	}
	return d.offsets
	}

	// LitEncoder returns the literal encoder.
	func (d dict) LitEncoder() huff0.Scratch {
	if d == nil {
	return nil
	}
	return d.litEnc
	}

	// Load a dictionary as described in
	// https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#dictionary-format
	func loadDict(b []byte) (*dict, error) {
	// Check static field size.
	if len(b) <= 8+(3*4) {
	return nil, io.ErrUnexpectedEOF
	}
	d := dict{
	llDec: sequenceDec{fse: &fseDecoder{}},
	ofDec: sequenceDec{fse: &fseDecoder{}},
	mlDec: sequenceDec{fse: &fseDecoder{}},
	}
	if string(b[:4]) != dictMagic {
	return nil, ErrMagicMismatch
	}
	d.id = binary.LittleEndian.Uint32(b[4:8])
	if d.id == 0 {
	return nil, errors.New("dictionaries cannot have ID 0")
	}

	// Read literal table
	var err error
	d.litEnc, b, err = huff0.ReadTable(b[8:], nil)
	if err != nil {
	return nil, fmt.Errorf("loading literal table: %w", err)
	}
	d.litEnc.Reuse = huff0.ReusePolicyMust

	br := byteReader{
	b: b,
	off: 0,
	}
	readDec := func(i tableIndex, dec *fseDecoder) error {
	if err := dec.readNCount(&br, uint16(maxTableSymbol[i])); err != nil {
	return err
	}
	if br.overread() {
	return io.ErrUnexpectedEOF
	}
	err = dec.transform(symbolTableX[i])
	if err != nil {
	println("Transform table error:", err)
	return err
	}
	if debugDecoder \|\| debugEncoder {
	println("Read table ok", "symbolLen:", dec.symbolLen)
	}
	// Set decoders as predefined so they aren't reused.
	dec.preDefined = true
	return nil
	}

	if err := readDec(tableOffsets, d.ofDec.fse); err != nil {
	return nil, err
	}
	if err := readDec(tableMatchLengths, d.mlDec.fse); err != nil {
	return nil, err
	}
	if err := readDec(tableLiteralLengths, d.llDec.fse); err != nil {
	return nil, err
	}
	if br.remain() < 12 {
	return nil, io.ErrUnexpectedEOF
	}

	d.offsets[0] = int(br.Uint32())
	br.advance(4)
	d.offsets[1] = int(br.Uint32())
	br.advance(4)
	d.offsets[2] = int(br.Uint32())
	br.advance(4)
	if d.offsets[0] <= 0 \|\| d.offsets[1] <= 0 \|\| d.offsets[2] <= 0 {
	return nil, errors.New("invalid offset in dictionary")
	}
	d.content = make([]byte, br.remain())
	copy(d.content, br.unread())
	if d.offsets[0] > len(d.content) \|\| d.offsets[1] > len(d.content) \|\| d.offsets[2] > len(d.content) {
	return nil, fmt.Errorf("initial offset bigger than dictionary content size %d, offsets: %v", len(d.content), d.offsets)
	}

	return &d, nil
	}

	// InspectDictionary loads a zstd dictionary and provides functions to inspect the content.
	func InspectDictionary(b []byte) (interface {
	ID() uint32
	ContentSize() int
	Content() []byte
	Offsets() [3]int
	LitEncoder() *huff0.Scratch
	}, error) {
	initPredefined()
	d, err := loadDict(b)
	return d, err
	}

	type BuildDictOptions struct {
	// Dictionary ID.
	ID uint32

	// Content to use to create dictionary tables.
	Contents [][]byte

	// History to use for all blocks.
	History []byte

	// Offsets to use.
	Offsets [3]int

	// CompatV155 will make the dictionary compatible with Zstd v1.5.5 and earlier.
	// See https://github.com/facebook/zstd/issues/3724
	CompatV155 bool

	// Use the specified encoder level.
	// The dictionary will be built using the specified encoder level,
	// which will reflect speed and make the dictionary tailored for that level.
	// If not set SpeedBestCompression will be used.
	Level EncoderLevel

	// DebugOut will write stats and other details here if set.
	DebugOut io.Writer
	}

	func BuildDict(o BuildDictOptions) ([]byte, error) {
	initPredefined()
	hist := o.History
	contents := o.Contents
	debug := o.DebugOut != nil
	println := func(args ...interface{}) {
	if o.DebugOut != nil {
	fmt.Fprintln(o.DebugOut, args...)
	}
	}
	printf := func(s string, args ...interface{}) {
	if o.DebugOut != nil {
	fmt.Fprintf(o.DebugOut, s, args...)
	}
	}
	print := func(args ...interface{}) {
	if o.DebugOut != nil {
	fmt.Fprint(o.DebugOut, args...)
	}
	}

	if int64(len(hist)) > dictMaxLength {
	return nil, fmt.Errorf("dictionary of size %d > %d", len(hist), int64(dictMaxLength))
	}
	if len(hist) < 8 {
	return nil, fmt.Errorf("dictionary of size %d < %d", len(hist), 8)
	}
	if len(contents) == 0 {
	return nil, errors.New("no content provided")
	}
	d := dict{
	id: o.ID,
	litEnc: nil,
	llDec: sequenceDec{},
	ofDec: sequenceDec{},
	mlDec: sequenceDec{},
	offsets: o.Offsets,
	content: hist,
	}
	block := blockEnc{lowMem: false}
	block.init()
	enc := encoder(&bestFastEncoder{fastBase: fastBase{maxMatchOff: int32(maxMatchLen), bufferReset: math.MaxInt32 - int32(maxMatchLen*2), lowMem: false}})
	if o.Level != 0 {
	eOpts := encoderOptions{
	level: o.Level,
	blockSize: maxMatchLen,
	windowSize: maxMatchLen,
	dict: &d,
	lowMem: false,
	}
	enc = eOpts.encoder()
	} else {
	o.Level = SpeedBestCompression
	}
	var (
	remain [256]int
	ll [256]int
	ml [256]int
	of [256]int
	)
	addValues := func(dst *[256]int, src []byte) {
	for _, v := range src {
	dst[v]++
	}
	}
	addHist := func(dst [256]int, src [256]uint32) {
	for i, v := range src {
	dst[i] += int(v)
	}
	}
	seqs := 0
	nUsed := 0
	litTotal := 0
	newOffsets := make(map[uint32]int, 1000)
	for _, b := range contents {
	block.reset(nil)
	if len(b) < 8 {
	continue
	}
	nUsed++
	enc.Reset(&d, true)
	enc.Encode(&block, b)
	addValues(&remain, block.literals)
	litTotal += len(block.literals)
	if len(block.sequences) == 0 {
	continue
	}
	seqs += len(block.sequences)
	block.genCodes()
	addHist(&ll, block.coders.llEnc.Histogram())
	addHist(&ml, block.coders.mlEnc.Histogram())
	addHist(&of, block.coders.ofEnc.Histogram())
	for i, seq := range block.sequences {
	if i > 3 {
	break
	}
	offset := seq.offset
	if offset == 0 {
	continue
	}
	if int(offset) >= len(o.History) {
	continue
	}
	if offset > 3 {
	newOffsets[offset-3]++
	} else {
	newOffsets[uint32(o.Offsets[offset-1])]++
	}
	}
	}
	// Find most used offsets.
	var sortedOffsets []uint32
	for k := range newOffsets {
	sortedOffsets = append(sortedOffsets, k)
	}
	sort.Slice(sortedOffsets, func(i, j int) bool {
	a, b := sortedOffsets[i], sortedOffsets[j]
	if a == b {
	// Prefer the longer offset
	return sortedOffsets[i] > sortedOffsets[j]
	}
	return newOffsets[sortedOffsets[i]] > newOffsets[sortedOffsets[j]]
	})
	if len(sortedOffsets) > 3 {
	if debug {
	print("Offsets:")
	for i, v := range sortedOffsets {
	if i > 20 {
	break
	}
	printf("[%d: %d],", v, newOffsets[v])
	}
	println("")
	}

	sortedOffsets = sortedOffsets[:3]
	}
	for i, v := range sortedOffsets {
	o.Offsets[i] = int(v)
	}
	if debug {
	println("New repeat offsets", o.Offsets)
	}

	if nUsed == 0 \|\| seqs == 0 {
	return nil, fmt.Errorf("%d blocks, %d sequences found", nUsed, seqs)
	}
	if debug {
	println("Sequences:", seqs, "Blocks:", nUsed, "Literals:", litTotal)
	}
	if seqs/nUsed < 512 {
	// Use 512 as minimum.
	nUsed = seqs / 512
	if nUsed == 0 {
	nUsed = 1
	}
	}
	copyHist := func(dst fseEncoder, src [256]int) ([]byte, error) {
	hist := dst.Histogram()
	var maxSym uint8
	var maxCount int
	var fakeLength int
	for i, v := range src {
	if v > 0 {
	v = v / nUsed
	if v == 0 {
	v = 1
	}
	}
	if v > maxCount {
	maxCount = v
	}
	if v != 0 {
	maxSym = uint8(i)
	}
	fakeLength += v
	hist[i] = uint32(v)
	}

	// Ensure we aren't trying to represent RLE.
	if maxCount == fakeLength {
	for i := range hist {
	if uint8(i) == maxSym {
	fakeLength++
	maxSym++
	hist[i+1] = 1
	if maxSym > 1 {
	break
	}
	}
	if hist[0] == 0 {
	fakeLength++
	hist[i] = 1
	if maxSym > 1 {
	break
	}
	}
	}
	}

	dst.HistogramFinished(maxSym, maxCount)
	dst.reUsed = false
	dst.useRLE = false
	err := dst.normalizeCount(fakeLength)
	if err != nil {
	return nil, err
	}
	if debug {
	println("RAW:", dst.count[:maxSym+1], "NORM:", dst.norm[:maxSym+1], "LEN:", fakeLength)
	}
	return dst.writeCount(nil)
	}
	if debug {
	print("Literal lengths: ")
	}
	llTable, err := copyHist(block.coders.llEnc, &ll)
	if err != nil {
	return nil, err
	}
	if debug {
	print("Match lengths: ")
	}
	mlTable, err := copyHist(block.coders.mlEnc, &ml)
	if err != nil {
	return nil, err
	}
	if debug {
	print("Offsets: ")
	}
	ofTable, err := copyHist(block.coders.ofEnc, &of)
	if err != nil {
	return nil, err
	}

	// Literal table
	avgSize := litTotal
	if avgSize > huff0.BlockSizeMax/2 {
	avgSize = huff0.BlockSizeMax / 2
	}
	huffBuff := make([]byte, 0, avgSize)
	// Target size
	div := litTotal / avgSize
	if div < 1 {
	div = 1
	}
	if debug {
	println("Huffman weights:")
	}
	for i, n := range remain[:] {
	if n > 0 {
	n = n / div
	// Allow all entries to be represented.
	if n == 0 {
	n = 1
	}
	huffBuff = append(huffBuff, bytes.Repeat([]byte{byte(i)}, n)...)
	if debug {
	printf("[%d: %d], ", i, n)
	}
	}
	}
	if o.CompatV155 && remain[255]/div == 0 {
	huffBuff = append(huffBuff, 255)
	}
	scratch := &huff0.Scratch{TableLog: 11}
	for tries := 0; tries < 255; tries++ {
	scratch = &huff0.Scratch{TableLog: 11}
	_, _, err = huff0.Compress1X(huffBuff, scratch)
	if err == nil {
	break
	}
	if debug {
	printf("Try %d: Huffman error: %v\n", tries+1, err)
	}
	huffBuff = huffBuff[:0]
	if tries == 250 {
	if debug {
	println("Huffman: Bailing out with predefined table")
	}

	// Bail out.... Just generate something
	huffBuff = append(huffBuff, bytes.Repeat([]byte{255}, 10000)...)
	for i := 0; i < 128; i++ {
	huffBuff = append(huffBuff, byte(i))
	}
	continue
	}
	if errors.Is(err, huff0.ErrIncompressible) {
	// Try truncating least common.
	for i, n := range remain[:] {
	if n > 0 {
	n = n / (div * (i + 1))
	if n > 0 {
	huffBuff = append(huffBuff, bytes.Repeat([]byte{byte(i)}, n)...)
	}
	}
	}
	if o.CompatV155 && len(huffBuff) > 0 && huffBuff[len(huffBuff)-1] != 255 {
	huffBuff = append(huffBuff, 255)
	}
	if len(huffBuff) == 0 {
	huffBuff = append(huffBuff, 0, 255)
	}
	}
	if errors.Is(err, huff0.ErrUseRLE) {
	for i, n := range remain[:] {
	n = n / (div * (i + 1))
	// Allow all entries to be represented.
	if n == 0 {
	n = 1
	}
	huffBuff = append(huffBuff, bytes.Repeat([]byte{byte(i)}, n)...)
	}
	}
	}

	var out bytes.Buffer
	out.Write([]byte(dictMagic))
	out.Write(binary.LittleEndian.AppendUint32(nil, o.ID))
	out.Write(scratch.OutTable)
	if debug {
	println("huff table:", len(scratch.OutTable), "bytes")
	println("of table:", len(ofTable), "bytes")
	println("ml table:", len(mlTable), "bytes")
	println("ll table:", len(llTable), "bytes")
	}
	out.Write(ofTable)
	out.Write(mlTable)
	out.Write(llTable)
	out.Write(binary.LittleEndian.AppendUint32(nil, uint32(o.Offsets[0])))
	out.Write(binary.LittleEndian.AppendUint32(nil, uint32(o.Offsets[1])))
	out.Write(binary.LittleEndian.AppendUint32(nil, uint32(o.Offsets[2])))
	out.Write(hist)
	if debug {
	_, err := loadDict(out.Bytes())
	if err != nil {
	panic(err)
	}
	i, err := InspectDictionary(out.Bytes())
	if err != nil {
	panic(err)
	}
	println("ID:", i.ID())
	println("Content size:", i.ContentSize())
	println("Encoder:", i.LitEncoder() != nil)
	println("Offsets:", i.Offsets())
	var totalSize int
	for _, b := range contents {
	totalSize += len(b)
	}

	encWith := func(opts ...EOption) int {
	enc, err := NewWriter(nil, opts...)
	if err != nil {
	panic(err)
	}
	defer enc.Close()
	var dst []byte
	var totalSize int
	for _, b := range contents {
	dst = enc.EncodeAll(b, dst[:0])
	totalSize += len(dst)
	}
	return totalSize
	}
	plain := encWith(WithEncoderLevel(o.Level))
	withDict := encWith(WithEncoderLevel(o.Level), WithEncoderDict(out.Bytes()))
	println("Input size:", totalSize)
	println("Plain Compressed:", plain)
	println("Dict Compressed:", withDict)
	println("Saved:", plain-withDict, (plain-withDict)/len(contents), "bytes per input (rounded down)")
	}
	return out.Bytes(), nil
	}