compress.go raw
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), nil
231 }
232
233 func (s *Scratch) compress1xDo(dst, src []byte) []byte {
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.encFourSymbols(cTable[tmp[3]], cTable[tmp[2]], cTable[tmp[1]], cTable[tmp[0]])
252 }
253 } else {
254 for ; n >= 0; n -= 4 {
255 tmp := src[n : n+4]
256 // tmp should be len 4
257 bw.flush32()
258 bw.encTwoSymbols(cTable, tmp[3], tmp[2])
259 bw.flush32()
260 bw.encTwoSymbols(cTable, tmp[1], tmp[0])
261 }
262 }
263 bw.close()
264 return bw.out
265 }
266
267 var sixZeros [6]byte
268
269 func (s *Scratch) compress4X(src []byte) ([]byte, error) {
270 if len(src) < 12 {
271 return nil, ErrIncompressible
272 }
273 segmentSize := (len(src) + 3) / 4
274
275 // Add placeholder for output length
276 offsetIdx := len(s.Out)
277 s.Out = append(s.Out, sixZeros[:]...)
278
279 for i := range 4 {
280 toDo := src
281 if len(toDo) > segmentSize {
282 toDo = toDo[:segmentSize]
283 }
284 src = src[len(toDo):]
285
286 idx := len(s.Out)
287 s.Out = s.compress1xDo(s.Out, toDo)
288 if len(s.Out)-idx > math.MaxUint16 {
289 // We cannot store the size in the jump table
290 return nil, ErrIncompressible
291 }
292 // Write compressed length as little endian before block.
293 if i < 3 {
294 // Last length is not written.
295 length := len(s.Out) - idx
296 s.Out[i*2+offsetIdx] = byte(length)
297 s.Out[i*2+offsetIdx+1] = byte(length >> 8)
298 }
299 }
300
301 return s.Out, nil
302 }
303
304 // compress4Xp will compress 4 streams using separate goroutines.
305 func (s *Scratch) compress4Xp(src []byte) ([]byte, error) {
306 if len(src) < 12 {
307 return nil, ErrIncompressible
308 }
309 // Add placeholder for output length
310 s.Out = s.Out[:6]
311
312 segmentSize := (len(src) + 3) / 4
313 var wg sync.WaitGroup
314 wg.Add(4)
315 for i := range 4 {
316 toDo := src
317 if len(toDo) > segmentSize {
318 toDo = toDo[:segmentSize]
319 }
320 src = src[len(toDo):]
321
322 // Separate goroutine for each block.
323 go func(i int) {
324 s.tmpOut[i] = s.compress1xDo(s.tmpOut[i][:0], toDo)
325 wg.Done()
326 }(i)
327 }
328 wg.Wait()
329 for i := range 4 {
330 o := s.tmpOut[i]
331 if len(o) > math.MaxUint16 {
332 // We cannot store the size in the jump table
333 return nil, ErrIncompressible
334 }
335 // Write compressed length as little endian before block.
336 if i < 3 {
337 // Last length is not written.
338 s.Out[i*2] = byte(len(o))
339 s.Out[i*2+1] = byte(len(o) >> 8)
340 }
341
342 // Write output.
343 s.Out = append(s.Out, o...)
344 }
345 return s.Out, nil
346 }
347
348 // countSimple will create a simple histogram in s.count.
349 // Returns the biggest count.
350 // Does not update s.clearCount.
351 func (s *Scratch) countSimple(in []byte) (max int, reuse bool) {
352 reuse = true
353 _ = s.count // Assert that s != nil to speed up the following loop.
354 for _, v := range in {
355 s.count[v]++
356 }
357 m := uint32(0)
358 if len(s.prevTable) > 0 {
359 for i, v := range s.count[:] {
360 if v == 0 {
361 continue
362 }
363 if v > m {
364 m = v
365 }
366 s.symbolLen = uint16(i) + 1
367 if i >= len(s.prevTable) {
368 reuse = false
369 } else if s.prevTable[i].nBits == 0 {
370 reuse = false
371 }
372 }
373 return int(m), reuse
374 }
375 for i, v := range s.count[:] {
376 if v == 0 {
377 continue
378 }
379 if v > m {
380 m = v
381 }
382 s.symbolLen = uint16(i) + 1
383 }
384 return int(m), false
385 }
386
387 func (s *Scratch) canUseTable(c cTable) bool {
388 if len(c) < int(s.symbolLen) {
389 return false
390 }
391 for i, v := range s.count[:s.symbolLen] {
392 if v != 0 && c[i].nBits == 0 {
393 return false
394 }
395 }
396 return true
397 }
398
399 //lint:ignore U1000 used for debugging
400 func (s *Scratch) validateTable(c cTable) bool {
401 if len(c) < int(s.symbolLen) {
402 return false
403 }
404 for i, v := range s.count[:s.symbolLen] {
405 if v != 0 {
406 if c[i].nBits == 0 {
407 return false
408 }
409 if c[i].nBits > s.actualTableLog {
410 return false
411 }
412 }
413 }
414 return true
415 }
416
417 // minTableLog provides the minimum logSize to safely represent a distribution.
418 func (s *Scratch) minTableLog() uint8 {
419 minBitsSrc := highBit32(uint32(s.srcLen)) + 1
420 minBitsSymbols := highBit32(uint32(s.symbolLen-1)) + 2
421 if minBitsSrc < minBitsSymbols {
422 return uint8(minBitsSrc)
423 }
424 return uint8(minBitsSymbols)
425 }
426
427 // optimalTableLog calculates and sets the optimal tableLog in s.actualTableLog
428 func (s *Scratch) optimalTableLog() {
429 tableLog := s.TableLog
430 minBits := s.minTableLog()
431 maxBitsSrc := uint8(highBit32(uint32(s.srcLen-1))) - 1
432 if maxBitsSrc < tableLog {
433 // Accuracy can be reduced
434 tableLog = maxBitsSrc
435 }
436 if minBits > tableLog {
437 tableLog = minBits
438 }
439 // Need a minimum to safely represent all symbol values
440 if tableLog < minTablelog {
441 tableLog = minTablelog
442 }
443 if tableLog > tableLogMax {
444 tableLog = tableLogMax
445 }
446 s.actualTableLog = tableLog
447 }
448
449 type cTableEntry struct {
450 val uint16
451 nBits uint8
452 // We have 8 bits extra
453 }
454
455 const huffNodesMask = huffNodesLen - 1
456
457 func (s *Scratch) buildCTable() error {
458 s.optimalTableLog()
459 s.huffSort()
460 if cap(s.cTable) < maxSymbolValue+1 {
461 s.cTable = make([]cTableEntry, s.symbolLen, maxSymbolValue+1)
462 } else {
463 s.cTable = s.cTable[:s.symbolLen]
464 for i := range s.cTable {
465 s.cTable[i] = cTableEntry{}
466 }
467 }
468
469 var startNode = int16(s.symbolLen)
470 nonNullRank := s.symbolLen - 1
471
472 nodeNb := startNode
473 huffNode := s.nodes[1 : huffNodesLen+1]
474
475 // This overlays the slice above, but allows "-1" index lookups.
476 // Different from reference implementation.
477 huffNode0 := s.nodes[0 : huffNodesLen+1]
478
479 for huffNode[nonNullRank].count() == 0 {
480 nonNullRank--
481 }
482
483 lowS := int16(nonNullRank)
484 nodeRoot := nodeNb + lowS - 1
485 lowN := nodeNb
486 huffNode[nodeNb].setCount(huffNode[lowS].count() + huffNode[lowS-1].count())
487 huffNode[lowS].setParent(nodeNb)
488 huffNode[lowS-1].setParent(nodeNb)
489 nodeNb++
490 lowS -= 2
491 for n := nodeNb; n <= nodeRoot; n++ {
492 huffNode[n].setCount(1 << 30)
493 }
494 // fake entry, strong barrier
495 huffNode0[0].setCount(1 << 31)
496
497 // create parents
498 for nodeNb <= nodeRoot {
499 var n1, n2 int16
500 if huffNode0[lowS+1].count() < huffNode0[lowN+1].count() {
501 n1 = lowS
502 lowS--
503 } else {
504 n1 = lowN
505 lowN++
506 }
507 if huffNode0[lowS+1].count() < huffNode0[lowN+1].count() {
508 n2 = lowS
509 lowS--
510 } else {
511 n2 = lowN
512 lowN++
513 }
514
515 huffNode[nodeNb].setCount(huffNode0[n1+1].count() + huffNode0[n2+1].count())
516 huffNode0[n1+1].setParent(nodeNb)
517 huffNode0[n2+1].setParent(nodeNb)
518 nodeNb++
519 }
520
521 // distribute weights (unlimited tree height)
522 huffNode[nodeRoot].setNbBits(0)
523 for n := nodeRoot - 1; n >= startNode; n-- {
524 huffNode[n].setNbBits(huffNode[huffNode[n].parent()].nbBits() + 1)
525 }
526 for n := uint16(0); n <= nonNullRank; n++ {
527 huffNode[n].setNbBits(huffNode[huffNode[n].parent()].nbBits() + 1)
528 }
529 s.actualTableLog = s.setMaxHeight(int(nonNullRank))
530 maxNbBits := s.actualTableLog
531
532 // fill result into tree (val, nbBits)
533 if maxNbBits > tableLogMax {
534 return fmt.Errorf("internal error: maxNbBits (%d) > tableLogMax (%d)", maxNbBits, tableLogMax)
535 }
536 var nbPerRank [tableLogMax + 1]uint16
537 var valPerRank [16]uint16
538 for _, v := range huffNode[:nonNullRank+1] {
539 nbPerRank[v.nbBits()]++
540 }
541 // determine stating value per rank
542 {
543 min := uint16(0)
544 for n := maxNbBits; n > 0; n-- {
545 // get starting value within each rank
546 valPerRank[n] = min
547 min += nbPerRank[n]
548 min >>= 1
549 }
550 }
551
552 // push nbBits per symbol, symbol order
553 for _, v := range huffNode[:nonNullRank+1] {
554 s.cTable[v.symbol()].nBits = v.nbBits()
555 }
556
557 // assign value within rank, symbol order
558 t := s.cTable[:s.symbolLen]
559 for n, val := range t {
560 nbits := val.nBits & 15
561 v := valPerRank[nbits]
562 t[n].val = v
563 valPerRank[nbits] = v + 1
564 }
565
566 return nil
567 }
568
569 // huffSort will sort symbols, decreasing order.
570 func (s *Scratch) huffSort() {
571 type rankPos struct {
572 base uint32
573 current uint32
574 }
575
576 // Clear nodes
577 nodes := s.nodes[:huffNodesLen+1]
578 s.nodes = nodes
579 nodes = nodes[1 : huffNodesLen+1]
580
581 // Sort into buckets based on length of symbol count.
582 var rank [32]rankPos
583 for _, v := range s.count[:s.symbolLen] {
584 r := highBit32(v+1) & 31
585 rank[r].base++
586 }
587 // maxBitLength is log2(BlockSizeMax) + 1
588 const maxBitLength = 18 + 1
589 for n := maxBitLength; n > 0; n-- {
590 rank[n-1].base += rank[n].base
591 }
592 for n := range rank[:maxBitLength] {
593 rank[n].current = rank[n].base
594 }
595 for n, c := range s.count[:s.symbolLen] {
596 r := (highBit32(c+1) + 1) & 31
597 pos := rank[r].current
598 rank[r].current++
599 prev := nodes[(pos-1)&huffNodesMask]
600 for pos > rank[r].base && c > prev.count() {
601 nodes[pos&huffNodesMask] = prev
602 pos--
603 prev = nodes[(pos-1)&huffNodesMask]
604 }
605 nodes[pos&huffNodesMask] = makeNodeElt(c, byte(n))
606 }
607 }
608
609 func (s *Scratch) setMaxHeight(lastNonNull int) uint8 {
610 maxNbBits := s.actualTableLog
611 huffNode := s.nodes[1 : huffNodesLen+1]
612 //huffNode = huffNode[: huffNodesLen]
613
614 largestBits := huffNode[lastNonNull].nbBits()
615
616 // early exit : no elt > maxNbBits
617 if largestBits <= maxNbBits {
618 return largestBits
619 }
620 totalCost := int(0)
621 baseCost := int(1) << (largestBits - maxNbBits)
622 n := uint32(lastNonNull)
623
624 for huffNode[n].nbBits() > maxNbBits {
625 totalCost += baseCost - (1 << (largestBits - huffNode[n].nbBits()))
626 huffNode[n].setNbBits(maxNbBits)
627 n--
628 }
629 // n stops at huffNode[n].nbBits <= maxNbBits
630
631 for huffNode[n].nbBits() == maxNbBits {
632 n--
633 }
634 // n end at index of smallest symbol using < maxNbBits
635
636 // renorm totalCost
637 totalCost >>= largestBits - maxNbBits /* note : totalCost is necessarily a multiple of baseCost */
638
639 // repay normalized cost
640 {
641 const noSymbol = 0xF0F0F0F0
642 var rankLast [tableLogMax + 2]uint32
643
644 for i := range rankLast[:] {
645 rankLast[i] = noSymbol
646 }
647
648 // Get pos of last (smallest) symbol per rank
649 {
650 currentNbBits := maxNbBits
651 for pos := int(n); pos >= 0; pos-- {
652 if huffNode[pos].nbBits() >= currentNbBits {
653 continue
654 }
655 currentNbBits = huffNode[pos].nbBits() // < maxNbBits
656 rankLast[maxNbBits-currentNbBits] = uint32(pos)
657 }
658 }
659
660 for totalCost > 0 {
661 nBitsToDecrease := uint8(highBit32(uint32(totalCost))) + 1
662
663 for ; nBitsToDecrease > 1; nBitsToDecrease-- {
664 highPos := rankLast[nBitsToDecrease]
665 lowPos := rankLast[nBitsToDecrease-1]
666 if highPos == noSymbol {
667 continue
668 }
669 if lowPos == noSymbol {
670 break
671 }
672 highTotal := huffNode[highPos].count()
673 lowTotal := 2 * huffNode[lowPos].count()
674 if highTotal <= lowTotal {
675 break
676 }
677 }
678 // only triggered when no more rank 1 symbol left => find closest one (note : there is necessarily at least one !)
679 // HUF_MAX_TABLELOG test just to please gcc 5+; but it should not be necessary
680 // FIXME: try to remove
681 for (nBitsToDecrease <= tableLogMax) && (rankLast[nBitsToDecrease] == noSymbol) {
682 nBitsToDecrease++
683 }
684 totalCost -= 1 << (nBitsToDecrease - 1)
685 if rankLast[nBitsToDecrease-1] == noSymbol {
686 // this rank is no longer empty
687 rankLast[nBitsToDecrease-1] = rankLast[nBitsToDecrease]
688 }
689 huffNode[rankLast[nBitsToDecrease]].setNbBits(1 +
690 huffNode[rankLast[nBitsToDecrease]].nbBits())
691 if rankLast[nBitsToDecrease] == 0 {
692 /* special case, reached largest symbol */
693 rankLast[nBitsToDecrease] = noSymbol
694 } else {
695 rankLast[nBitsToDecrease]--
696 if huffNode[rankLast[nBitsToDecrease]].nbBits() != maxNbBits-nBitsToDecrease {
697 rankLast[nBitsToDecrease] = noSymbol /* this rank is now empty */
698 }
699 }
700 }
701
702 for totalCost < 0 { /* Sometimes, cost correction overshoot */
703 if rankLast[1] == noSymbol { /* special case : no rank 1 symbol (using maxNbBits-1); let's create one from largest rank 0 (using maxNbBits) */
704 for huffNode[n].nbBits() == maxNbBits {
705 n--
706 }
707 huffNode[n+1].setNbBits(huffNode[n+1].nbBits() - 1)
708 rankLast[1] = n + 1
709 totalCost++
710 continue
711 }
712 huffNode[rankLast[1]+1].setNbBits(huffNode[rankLast[1]+1].nbBits() - 1)
713 rankLast[1]++
714 totalCost++
715 }
716 }
717 return maxNbBits
718 }
719
720 // A nodeElt is the fields
721 //
722 // count uint32
723 // parent uint16
724 // symbol byte
725 // nbBits uint8
726 //
727 // in some order, all squashed into an integer so that the compiler
728 // always loads and stores entire nodeElts instead of separate fields.
729 type nodeElt uint64
730
731 func makeNodeElt(count uint32, symbol byte) nodeElt {
732 return nodeElt(count) | nodeElt(symbol)<<48
733 }
734
735 func (e *nodeElt) count() uint32 { return uint32(*e) }
736 func (e *nodeElt) parent() uint16 { return uint16(*e >> 32) }
737 func (e *nodeElt) symbol() byte { return byte(*e >> 48) }
738 func (e *nodeElt) nbBits() uint8 { return uint8(*e >> 56) }
739
740 func (e *nodeElt) setCount(c uint32) { *e = (*e)&0xffffffff00000000 | nodeElt(c) }
741 func (e *nodeElt) setParent(p int16) { *e = (*e)&0xffff0000ffffffff | nodeElt(uint16(p))<<32 }
742 func (e *nodeElt) setNbBits(n uint8) { *e = (*e)&0x00ffffffffffffff | nodeElt(n)<<56 }
743