cubefs

1
package huff0
2

3
import (
4
	"fmt"
5
	"math"
6
	"runtime"
7
	"sync"
8
)
9

10
// Compress1X will compress the input.
11
// The output can be decoded using Decompress1X.
12
// Supply a Scratch object. The scratch object contains state about re-use,
13
// So when sharing across independent encodes, be sure to set the re-use policy.
14
func Compress1X(in []byte, s *Scratch) (out []byte, reUsed bool, err error) {
15
	s, err = s.prepare(in)
16
	if err != nil {
17
		return nil, false, err
18
	}
19
	return compress(in, s, s.compress1X)
20
}
21

22
// Compress4X will compress the input. The input is split into 4 independent blocks
23
// and compressed similar to Compress1X.
24
// The output can be decoded using Decompress4X.
25
// Supply a Scratch object. The scratch object contains state about re-use,
26
// So when sharing across independent encodes, be sure to set the re-use policy.
27
func Compress4X(in []byte, s *Scratch) (out []byte, reUsed bool, err error) {
28
	s, err = s.prepare(in)
29
	if err != nil {
30
		return nil, false, err
31
	}
32
	if false {
33
		// TODO: compress4Xp only slightly faster.
34
		const parallelThreshold = 8 << 10
35
		if len(in) < parallelThreshold || runtime.GOMAXPROCS(0) == 1 {
36
			return compress(in, s, s.compress4X)
37
		}
38
		return compress(in, s, s.compress4Xp)
39
	}
40
	return compress(in, s, s.compress4X)
41
}
42

43
func compress(in []byte, s *Scratch, compressor func(src []byte) ([]byte, error)) (out []byte, reUsed bool, err error) {
44
	// Nuke previous table if we cannot reuse anyway.
45
	if s.Reuse == ReusePolicyNone {
46
		s.prevTable = s.prevTable[:0]
47
	}
48

49
	// Create histogram, if none was provided.
50
	maxCount := s.maxCount
51
	var canReuse = false
52
	if maxCount == 0 {
53
		maxCount, canReuse = s.countSimple(in)
54
	} else {
55
		canReuse = s.canUseTable(s.prevTable)
56
	}
57

58
	// We want the output size to be less than this:
59
	wantSize := len(in)
60
	if s.WantLogLess > 0 {
61
		wantSize -= wantSize >> s.WantLogLess
62
	}
63

64
	// Reset for next run.
65
	s.clearCount = true
66
	s.maxCount = 0
67
	if maxCount >= len(in) {
68
		if maxCount > len(in) {
69
			return nil, false, fmt.Errorf("maxCount (%d) > length (%d)", maxCount, len(in))
70
		}
71
		if len(in) == 1 {
72
			return nil, false, ErrIncompressible
73
		}
74
		// One symbol, use RLE
75
		return nil, false, ErrUseRLE
76
	}
77
	if maxCount == 1 || maxCount < (len(in)>>7) {
78
		// Each symbol present maximum once or too well distributed.
79
		return nil, false, ErrIncompressible
80
	}
81
	if s.Reuse == ReusePolicyMust && !canReuse {
82
		// We must reuse, but we can't.
83
		return nil, false, ErrIncompressible
84
	}
85
	if (s.Reuse == ReusePolicyPrefer || s.Reuse == ReusePolicyMust) && canReuse {
86
		keepTable := s.cTable
87
		keepTL := s.actualTableLog
88
		s.cTable = s.prevTable
89
		s.actualTableLog = s.prevTableLog
90
		s.Out, err = compressor(in)
91
		s.cTable = keepTable
92
		s.actualTableLog = keepTL
93
		if err == nil && len(s.Out) < wantSize {
94
			s.OutData = s.Out
95
			return s.Out, true, nil
96
		}
97
		if s.Reuse == ReusePolicyMust {
98
			return nil, false, ErrIncompressible
99
		}
100
		// Do not attempt to re-use later.
101
		s.prevTable = s.prevTable[:0]
102
	}
103

104
	// Calculate new table.
105
	err = s.buildCTable()
106
	if err != nil {
107
		return nil, false, err
108
	}
109

110
	if false && !s.canUseTable(s.cTable) {
111
		panic("invalid table generated")
112
	}
113

114
	if s.Reuse == ReusePolicyAllow && canReuse {
115
		hSize := len(s.Out)
116
		oldSize := s.prevTable.estimateSize(s.count[:s.symbolLen])
117
		newSize := s.cTable.estimateSize(s.count[:s.symbolLen])
118
		if oldSize <= hSize+newSize || hSize+12 >= wantSize {
119
			// Retain cTable even if we re-use.
120
			keepTable := s.cTable
121
			keepTL := s.actualTableLog
122

123
			s.cTable = s.prevTable
124
			s.actualTableLog = s.prevTableLog
125
			s.Out, err = compressor(in)
126

127
			// Restore ctable.
128
			s.cTable = keepTable
129
			s.actualTableLog = keepTL
130
			if err != nil {
131
				return nil, false, err
132
			}
133
			if len(s.Out) >= wantSize {
134
				return nil, false, ErrIncompressible
135
			}
136
			s.OutData = s.Out
137
			return s.Out, true, nil
138
		}
139
	}
140

141
	// Use new table
142
	err = s.cTable.write(s)
143
	if err != nil {
144
		s.OutTable = nil
145
		return nil, false, err
146
	}
147
	s.OutTable = s.Out
148

149
	// Compress using new table
150
	s.Out, err = compressor(in)
151
	if err != nil {
152
		s.OutTable = nil
153
		return nil, false, err
154
	}
155
	if len(s.Out) >= wantSize {
156
		s.OutTable = nil
157
		return nil, false, ErrIncompressible
158
	}
159
	// Move current table into previous.
160
	s.prevTable, s.prevTableLog, s.cTable = s.cTable, s.actualTableLog, s.prevTable[:0]
161
	s.OutData = s.Out[len(s.OutTable):]
162
	return s.Out, false, nil
163
}
164

165
// EstimateSizes will estimate the data sizes
166
func EstimateSizes(in []byte, s *Scratch) (tableSz, dataSz, reuseSz int, err error) {
167
	s, err = s.prepare(in)
168
	if err != nil {
169
		return 0, 0, 0, err
170
	}
171

172
	// Create histogram, if none was provided.
173
	tableSz, dataSz, reuseSz = -1, -1, -1
174
	maxCount := s.maxCount
175
	var canReuse = false
176
	if maxCount == 0 {
177
		maxCount, canReuse = s.countSimple(in)
178
	} else {
179
		canReuse = s.canUseTable(s.prevTable)
180
	}
181

182
	// We want the output size to be less than this:
183
	wantSize := len(in)
184
	if s.WantLogLess > 0 {
185
		wantSize -= wantSize >> s.WantLogLess
186
	}
187

188
	// Reset for next run.
189
	s.clearCount = true
190
	s.maxCount = 0
191
	if maxCount >= len(in) {
192
		if maxCount > len(in) {
193
			return 0, 0, 0, fmt.Errorf("maxCount (%d) > length (%d)", maxCount, len(in))
194
		}
195
		if len(in) == 1 {
196
			return 0, 0, 0, ErrIncompressible
197
		}
198
		// One symbol, use RLE
199
		return 0, 0, 0, ErrUseRLE
200
	}
201
	if maxCount == 1 || maxCount < (len(in)>>7) {
202
		// Each symbol present maximum once or too well distributed.
203
		return 0, 0, 0, ErrIncompressible
204
	}
205

206
	// Calculate new table.
207
	err = s.buildCTable()
208
	if err != nil {
209
		return 0, 0, 0, err
210
	}
211

212
	if false && !s.canUseTable(s.cTable) {
213
		panic("invalid table generated")
214
	}
215

216
	tableSz, err = s.cTable.estTableSize(s)
217
	if err != nil {
218
		return 0, 0, 0, err
219
	}
220
	if canReuse {
221
		reuseSz = s.prevTable.estimateSize(s.count[:s.symbolLen])
222
	}
223
	dataSz = s.cTable.estimateSize(s.count[:s.symbolLen])
224

225
	// Restore
226
	return tableSz, dataSz, reuseSz, nil
227
}
228

229
func (s *Scratch) compress1X(src []byte) ([]byte, error) {
230
	return s.compress1xDo(s.Out, src)
231
}
232

233
func (s *Scratch) compress1xDo(dst, src []byte) ([]byte, error) {
234
	var bw = bitWriter{out: dst}
235

236
	// N is length divisible by 4.
237
	n := len(src)
238
	n -= n & 3
239
	cTable := s.cTable[:256]
240

241
	// Encode last bytes.
242
	for i := len(src) & 3; i > 0; i-- {
243
		bw.encSymbol(cTable, src[n+i-1])
244
	}
245
	n -= 4
246
	if s.actualTableLog <= 8 {
247
		for ; n >= 0; n -= 4 {
248
			tmp := src[n : n+4]
249
			// tmp should be len 4
250
			bw.flush32()
251
			bw.encTwoSymbols(cTable, tmp[3], tmp[2])
252
			bw.encTwoSymbols(cTable, tmp[1], tmp[0])
253
		}
254
	} else {
255
		for ; n >= 0; n -= 4 {
256
			tmp := src[n : n+4]
257
			// tmp should be len 4
258
			bw.flush32()
259
			bw.encTwoSymbols(cTable, tmp[3], tmp[2])
260
			bw.flush32()
261
			bw.encTwoSymbols(cTable, tmp[1], tmp[0])
262
		}
263
	}
264
	err := bw.close()
265
	return bw.out, err
266
}
267

268
var sixZeros [6]byte
269

270
func (s *Scratch) compress4X(src []byte) ([]byte, error) {
271
	if len(src) < 12 {
272
		return nil, ErrIncompressible
273
	}
274
	segmentSize := (len(src) + 3) / 4
275

276
	// Add placeholder for output length
277
	offsetIdx := len(s.Out)
278
	s.Out = append(s.Out, sixZeros[:]...)
279

280
	for i := 0; i < 4; i++ {
281
		toDo := src
282
		if len(toDo) > segmentSize {
283
			toDo = toDo[:segmentSize]
284
		}
285
		src = src[len(toDo):]
286

287
		var err error
288
		idx := len(s.Out)
289
		s.Out, err = s.compress1xDo(s.Out, toDo)
290
		if err != nil {
291
			return nil, err
292
		}
293
		if len(s.Out)-idx > math.MaxUint16 {
294
			// We cannot store the size in the jump table
295
			return nil, ErrIncompressible
296
		}
297
		// Write compressed length as little endian before block.
298
		if i < 3 {
299
			// Last length is not written.
300
			length := len(s.Out) - idx
301
			s.Out[i*2+offsetIdx] = byte(length)
302
			s.Out[i*2+offsetIdx+1] = byte(length >> 8)
303
		}
304
	}
305

306
	return s.Out, nil
307
}
308

309
// compress4Xp will compress 4 streams using separate goroutines.
310
func (s *Scratch) compress4Xp(src []byte) ([]byte, error) {
311
	if len(src) < 12 {
312
		return nil, ErrIncompressible
313
	}
314
	// Add placeholder for output length
315
	s.Out = s.Out[:6]
316

317
	segmentSize := (len(src) + 3) / 4
318
	var wg sync.WaitGroup
319
	var errs [4]error
320
	wg.Add(4)
321
	for i := 0; i < 4; i++ {
322
		toDo := src
323
		if len(toDo) > segmentSize {
324
			toDo = toDo[:segmentSize]
325
		}
326
		src = src[len(toDo):]
327

328
		// Separate goroutine for each block.
329
		go func(i int) {
330
			s.tmpOut[i], errs[i] = s.compress1xDo(s.tmpOut[i][:0], toDo)
331
			wg.Done()
332
		}(i)
333
	}
334
	wg.Wait()
335
	for i := 0; i < 4; i++ {
336
		if errs[i] != nil {
337
			return nil, errs[i]
338
		}
339
		o := s.tmpOut[i]
340
		if len(o) > math.MaxUint16 {
341
			// We cannot store the size in the jump table
342
			return nil, ErrIncompressible
343
		}
344
		// Write compressed length as little endian before block.
345
		if i < 3 {
346
			// Last length is not written.
347
			s.Out[i*2] = byte(len(o))
348
			s.Out[i*2+1] = byte(len(o) >> 8)
349
		}
350

351
		// Write output.
352
		s.Out = append(s.Out, o...)
353
	}
354
	return s.Out, nil
355
}
356

357
// countSimple will create a simple histogram in s.count.
358
// Returns the biggest count.
359
// Does not update s.clearCount.
360
func (s *Scratch) countSimple(in []byte) (max int, reuse bool) {
361
	reuse = true
362
	for _, v := range in {
363
		s.count[v]++
364
	}
365
	m := uint32(0)
366
	if len(s.prevTable) > 0 {
367
		for i, v := range s.count[:] {
368
			if v > m {
369
				m = v
370
			}
371
			if v > 0 {
372
				s.symbolLen = uint16(i) + 1
373
				if i >= len(s.prevTable) {
374
					reuse = false
375
				} else {
376
					if s.prevTable[i].nBits == 0 {
377
						reuse = false
378
					}
379
				}
380
			}
381
		}
382
		return int(m), reuse
383
	}
384
	for i, v := range s.count[:] {
385
		if v > m {
386
			m = v
387
		}
388
		if v > 0 {
389
			s.symbolLen = uint16(i) + 1
390
		}
391
	}
392
	return int(m), false
393
}
394

395
func (s *Scratch) canUseTable(c cTable) bool {
396
	if len(c) < int(s.symbolLen) {
397
		return false
398
	}
399
	for i, v := range s.count[:s.symbolLen] {
400
		if v != 0 && c[i].nBits == 0 {
401
			return false
402
		}
403
	}
404
	return true
405
}
406

407
func (s *Scratch) validateTable(c cTable) bool {
408
	if len(c) < int(s.symbolLen) {
409
		return false
410
	}
411
	for i, v := range s.count[:s.symbolLen] {
412
		if v != 0 {
413
			if c[i].nBits == 0 {
414
				return false
415
			}
416
			if c[i].nBits > s.actualTableLog {
417
				return false
418
			}
419
		}
420
	}
421
	return true
422
}
423

424
// minTableLog provides the minimum logSize to safely represent a distribution.
425
func (s *Scratch) minTableLog() uint8 {
426
	minBitsSrc := highBit32(uint32(s.br.remain())) + 1
427
	minBitsSymbols := highBit32(uint32(s.symbolLen-1)) + 2
428
	if minBitsSrc < minBitsSymbols {
429
		return uint8(minBitsSrc)
430
	}
431
	return uint8(minBitsSymbols)
432
}
433

434
// optimalTableLog calculates and sets the optimal tableLog in s.actualTableLog
435
func (s *Scratch) optimalTableLog() {
436
	tableLog := s.TableLog
437
	minBits := s.minTableLog()
438
	maxBitsSrc := uint8(highBit32(uint32(s.br.remain()-1))) - 1
439
	if maxBitsSrc < tableLog {
440
		// Accuracy can be reduced
441
		tableLog = maxBitsSrc
442
	}
443
	if minBits > tableLog {
444
		tableLog = minBits
445
	}
446
	// Need a minimum to safely represent all symbol values
447
	if tableLog < minTablelog {
448
		tableLog = minTablelog
449
	}
450
	if tableLog > tableLogMax {
451
		tableLog = tableLogMax
452
	}
453
	s.actualTableLog = tableLog
454
}
455

456
type cTableEntry struct {
457
	val   uint16
458
	nBits uint8
459
	// We have 8 bits extra
460
}
461

462
const huffNodesMask = huffNodesLen - 1
463

464
func (s *Scratch) buildCTable() error {
465
	s.optimalTableLog()
466
	s.huffSort()
467
	if cap(s.cTable) < maxSymbolValue+1 {
468
		s.cTable = make([]cTableEntry, s.symbolLen, maxSymbolValue+1)
469
	} else {
470
		s.cTable = s.cTable[:s.symbolLen]
471
		for i := range s.cTable {
472
			s.cTable[i] = cTableEntry{}
473
		}
474
	}
475

476
	var startNode = int16(s.symbolLen)
477
	nonNullRank := s.symbolLen - 1
478

479
	nodeNb := startNode
480
	huffNode := s.nodes[1 : huffNodesLen+1]
481

482
	// This overlays the slice above, but allows "-1" index lookups.
483
	// Different from reference implementation.
484
	huffNode0 := s.nodes[0 : huffNodesLen+1]
485

486
	for huffNode[nonNullRank].count == 0 {
487
		nonNullRank--
488
	}
489

490
	lowS := int16(nonNullRank)
491
	nodeRoot := nodeNb + lowS - 1
492
	lowN := nodeNb
493
	huffNode[nodeNb].count = huffNode[lowS].count + huffNode[lowS-1].count
494
	huffNode[lowS].parent, huffNode[lowS-1].parent = uint16(nodeNb), uint16(nodeNb)
495
	nodeNb++
496
	lowS -= 2
497
	for n := nodeNb; n <= nodeRoot; n++ {
498
		huffNode[n].count = 1 << 30
499
	}
500
	// fake entry, strong barrier
501
	huffNode0[0].count = 1 << 31
502

503
	// create parents
504
	for nodeNb <= nodeRoot {
505
		var n1, n2 int16
506
		if huffNode0[lowS+1].count < huffNode0[lowN+1].count {
507
			n1 = lowS
508
			lowS--
509
		} else {
510
			n1 = lowN
511
			lowN++
512
		}
513
		if huffNode0[lowS+1].count < huffNode0[lowN+1].count {
514
			n2 = lowS
515
			lowS--
516
		} else {
517
			n2 = lowN
518
			lowN++
519
		}
520

521
		huffNode[nodeNb].count = huffNode0[n1+1].count + huffNode0[n2+1].count
522
		huffNode0[n1+1].parent, huffNode0[n2+1].parent = uint16(nodeNb), uint16(nodeNb)
523
		nodeNb++
524
	}
525

526
	// distribute weights (unlimited tree height)
527
	huffNode[nodeRoot].nbBits = 0
528
	for n := nodeRoot - 1; n >= startNode; n-- {
529
		huffNode[n].nbBits = huffNode[huffNode[n].parent].nbBits + 1
530
	}
531
	for n := uint16(0); n <= nonNullRank; n++ {
532
		huffNode[n].nbBits = huffNode[huffNode[n].parent].nbBits + 1
533
	}
534
	s.actualTableLog = s.setMaxHeight(int(nonNullRank))
535
	maxNbBits := s.actualTableLog
536

537
	// fill result into tree (val, nbBits)
538
	if maxNbBits > tableLogMax {
539
		return fmt.Errorf("internal error: maxNbBits (%d) > tableLogMax (%d)", maxNbBits, tableLogMax)
540
	}
541
	var nbPerRank [tableLogMax + 1]uint16
542
	var valPerRank [16]uint16
543
	for _, v := range huffNode[:nonNullRank+1] {
544
		nbPerRank[v.nbBits]++
545
	}
546
	// determine stating value per rank
547
	{
548
		min := uint16(0)
549
		for n := maxNbBits; n > 0; n-- {
550
			// get starting value within each rank
551
			valPerRank[n] = min
552
			min += nbPerRank[n]
553
			min >>= 1
554
		}
555
	}
556

557
	// push nbBits per symbol, symbol order
558
	for _, v := range huffNode[:nonNullRank+1] {
559
		s.cTable[v.symbol].nBits = v.nbBits
560
	}
561

562
	// assign value within rank, symbol order
563
	t := s.cTable[:s.symbolLen]
564
	for n, val := range t {
565
		nbits := val.nBits & 15
566
		v := valPerRank[nbits]
567
		t[n].val = v
568
		valPerRank[nbits] = v + 1
569
	}
570

571
	return nil
572
}
573

574
// huffSort will sort symbols, decreasing order.
575
func (s *Scratch) huffSort() {
576
	type rankPos struct {
577
		base    uint32
578
		current uint32
579
	}
580

581
	// Clear nodes
582
	nodes := s.nodes[:huffNodesLen+1]
583
	s.nodes = nodes
584
	nodes = nodes[1 : huffNodesLen+1]
585

586
	// Sort into buckets based on length of symbol count.
587
	var rank [32]rankPos
588
	for _, v := range s.count[:s.symbolLen] {
589
		r := highBit32(v+1) & 31
590
		rank[r].base++
591
	}
592
	// maxBitLength is log2(BlockSizeMax) + 1
593
	const maxBitLength = 18 + 1
594
	for n := maxBitLength; n > 0; n-- {
595
		rank[n-1].base += rank[n].base
596
	}
597
	for n := range rank[:maxBitLength] {
598
		rank[n].current = rank[n].base
599
	}
600
	for n, c := range s.count[:s.symbolLen] {
601
		r := (highBit32(c+1) + 1) & 31
602
		pos := rank[r].current
603
		rank[r].current++
604
		prev := nodes[(pos-1)&huffNodesMask]
605
		for pos > rank[r].base && c > prev.count {
606
			nodes[pos&huffNodesMask] = prev
607
			pos--
608
			prev = nodes[(pos-1)&huffNodesMask]
609
		}
610
		nodes[pos&huffNodesMask] = nodeElt{count: c, symbol: byte(n)}
611
	}
612
}
613

614
func (s *Scratch) setMaxHeight(lastNonNull int) uint8 {
615
	maxNbBits := s.actualTableLog
616
	huffNode := s.nodes[1 : huffNodesLen+1]
617
	//huffNode = huffNode[: huffNodesLen]
618

619
	largestBits := huffNode[lastNonNull].nbBits
620

621
	// early exit : no elt > maxNbBits
622
	if largestBits <= maxNbBits {
623
		return largestBits
624
	}
625
	totalCost := int(0)
626
	baseCost := int(1) << (largestBits - maxNbBits)
627
	n := uint32(lastNonNull)
628

629
	for huffNode[n].nbBits > maxNbBits {
630
		totalCost += baseCost - (1 << (largestBits - huffNode[n].nbBits))
631
		huffNode[n].nbBits = maxNbBits
632
		n--
633
	}
634
	// n stops at huffNode[n].nbBits <= maxNbBits
635

636
	for huffNode[n].nbBits == maxNbBits {
637
		n--
638
	}
639
	// n end at index of smallest symbol using < maxNbBits
640

641
	// renorm totalCost
642
	totalCost >>= largestBits - maxNbBits /* note : totalCost is necessarily a multiple of baseCost */
643

644
	// repay normalized cost
645
	{
646
		const noSymbol = 0xF0F0F0F0
647
		var rankLast [tableLogMax + 2]uint32
648

649
		for i := range rankLast[:] {
650
			rankLast[i] = noSymbol
651
		}
652

653
		// Get pos of last (smallest) symbol per rank
654
		{
655
			currentNbBits := maxNbBits
656
			for pos := int(n); pos >= 0; pos-- {
657
				if huffNode[pos].nbBits >= currentNbBits {
658
					continue
659
				}
660
				currentNbBits = huffNode[pos].nbBits // < maxNbBits
661
				rankLast[maxNbBits-currentNbBits] = uint32(pos)
662
			}
663
		}
664

665
		for totalCost > 0 {
666
			nBitsToDecrease := uint8(highBit32(uint32(totalCost))) + 1
667

668
			for ; nBitsToDecrease > 1; nBitsToDecrease-- {
669
				highPos := rankLast[nBitsToDecrease]
670
				lowPos := rankLast[nBitsToDecrease-1]
671
				if highPos == noSymbol {
672
					continue
673
				}
674
				if lowPos == noSymbol {
675
					break
676
				}
677
				highTotal := huffNode[highPos].count
678
				lowTotal := 2 * huffNode[lowPos].count
679
				if highTotal <= lowTotal {
680
					break
681
				}
682
			}
683
			// only triggered when no more rank 1 symbol left => find closest one (note : there is necessarily at least one !)
684
			// HUF_MAX_TABLELOG test just to please gcc 5+; but it should not be necessary
685
			// FIXME: try to remove
686
			for (nBitsToDecrease <= tableLogMax) && (rankLast[nBitsToDecrease] == noSymbol) {
687
				nBitsToDecrease++
688
			}
689
			totalCost -= 1 << (nBitsToDecrease - 1)
690
			if rankLast[nBitsToDecrease-1] == noSymbol {
691
				// this rank is no longer empty
692
				rankLast[nBitsToDecrease-1] = rankLast[nBitsToDecrease]
693
			}
694
			huffNode[rankLast[nBitsToDecrease]].nbBits++
695
			if rankLast[nBitsToDecrease] == 0 {
696
				/* special case, reached largest symbol */
697
				rankLast[nBitsToDecrease] = noSymbol
698
			} else {
699
				rankLast[nBitsToDecrease]--
700
				if huffNode[rankLast[nBitsToDecrease]].nbBits != maxNbBits-nBitsToDecrease {
701
					rankLast[nBitsToDecrease] = noSymbol /* this rank is now empty */
702
				}
703
			}
704
		}
705

706
		for totalCost < 0 { /* Sometimes, cost correction overshoot */
707
			if rankLast[1] == noSymbol { /* special case : no rank 1 symbol (using maxNbBits-1); let's create one from largest rank 0 (using maxNbBits) */
708
				for huffNode[n].nbBits == maxNbBits {
709
					n--
710
				}
711
				huffNode[n+1].nbBits--
712
				rankLast[1] = n + 1
713
				totalCost++
714
				continue
715
			}
716
			huffNode[rankLast[1]+1].nbBits--
717
			rankLast[1]++
718
			totalCost++
719
		}
720
	}
721
	return maxNbBits
722
}
723

724
type nodeElt struct {
725
	count  uint32
726
	parent uint16
727
	symbol byte
728
	nbBits uint8
729
}
730