Files
logpile/internal/rar5/huffman.go
T
Mikhail ChusavitinandClaude Opus 5.5 b4b15e58a2 feat(parser): linux-generic content-driven parser and RAR archive support
Field bundles from ad-hoc service scripts (first sample: Giga G894-SD3 .rar
with dmidecode/lscpu/lspci/nvme/lsblk output, no fixed layout). ADL-078:
- linux-generic: recognizes utility output by content, merges records by
  stable key, low detect confidence (20-30) below all vendor parsers
- pciids.LookupByDescription: resolve a textual lspci description back to
  vendor/device IDs and manufacturer/model
- archive: accept .rar via the in-repo internal/rar5 reader (RAR 5 / RAR 7,
  single volume, solid; encrypted, multi-volume, SFX and RAR 4.x rejected),
  same per-file and total limits as tar/zip
- UI: .rar in the upload accept list

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
2026-10-02 15:00:38 +03:00

199 lines
3.8 KiB
Go

// Derived from github.com/nwaples/rardecode (BSD 2-Clause), see LICENSE.
package rar5
import "io"
const (
maxCodeLength = 15 // maximum code length in bits
maxQuickBits = 10
maxQuickSize = 1 << maxQuickBits
)
// huffmanDecoder decodes canonical Huffman codes built from a code length
// table.
type huffmanDecoder struct {
limit [maxCodeLength + 1]uint16
pos [maxCodeLength + 1]uint16
symbol []uint16
min uint8
quickbits uint8
quicklen [maxQuickSize]uint8
quicksym [maxQuickSize]uint16
}
func (h *huffmanDecoder) init(codeLengths []byte) {
count := make([]uint16, maxCodeLength+1)
for _, n := range codeLengths {
if n != 0 {
count[n]++
}
}
h.pos[0] = 0
h.limit[0] = 0
h.min = 0
for i := uint8(1); i <= maxCodeLength; i++ {
h.limit[i] = h.limit[i-1] + count[i]<<(maxCodeLength-i)
h.pos[i] = h.pos[i-1] + count[i-1]
if h.min == 0 && h.limit[i] > 0 {
h.min = i
}
}
if cap(h.symbol) >= len(codeLengths) {
h.symbol = h.symbol[:len(codeLengths)]
clear(h.symbol)
} else {
h.symbol = make([]uint16, len(codeLengths))
}
copy(count, h.pos[:])
for i, n := range codeLengths {
if n != 0 {
h.symbol[count[n]] = uint16(i)
count[n]++
}
}
if len(codeLengths) >= 298 {
h.quickbits = maxQuickBits
} else {
h.quickbits = maxQuickBits - 3
}
bits := uint8(1)
for i := uint16(0); i < 1<<h.quickbits; i++ {
v := i << (maxCodeLength - h.quickbits)
for v >= h.limit[bits] && bits < maxCodeLength {
bits++
}
h.quicklen[i] = bits
dist := v - h.limit[bits-1]
dist >>= maxCodeLength - bits
pos := int(h.pos[bits]) + int(dist)
if pos < len(h.symbol) {
h.quicksym[i] = h.symbol[pos]
} else {
h.quicksym[i] = 0
}
}
}
func (h *huffmanDecoder) readSym(r *bitReader) (int, error) {
var bits uint8
var v uint16
n, err := r.readBits(maxCodeLength)
if err != nil {
if err != io.EOF {
return 0, err
}
// fall back to 1 bit at a time near the end of the block
for bits = 1; bits <= maxCodeLength; bits++ {
b, err := r.readBits(1)
if err != nil {
return 0, err // not enough bits
}
v |= uint16(b) << (maxCodeLength - bits)
if v < h.limit[bits] {
break
}
}
if bits > maxCodeLength {
return 0, ErrCorrupt
}
} else {
v = uint16(n)
if v < h.limit[h.quickbits] {
i := v >> (maxCodeLength - h.quickbits)
r.unreadBits(maxCodeLength - h.quicklen[i])
return int(h.quicksym[i]), nil
}
for bits = h.min; bits < maxCodeLength; bits++ {
if v < h.limit[bits] {
r.unreadBits(maxCodeLength - bits)
break
}
}
}
if bits == 0 {
return 0, ErrCorrupt
}
dist := v - h.limit[bits-1]
dist >>= maxCodeLength - bits
pos := int(h.pos[bits]) + int(dist)
if pos >= len(h.symbol) {
return 0, ErrCorrupt
}
return int(h.symbol[pos]), nil
}
// readCodeLengthTable reads a new code length table into codeLength.
func readCodeLengthTable(br *bitReader, codeLength []byte) error {
var bitlength [20]byte
for i := 0; i < len(bitlength); i++ {
n, err := br.readBits(4)
if err != nil {
return err
}
if n == 0xf {
cnt, err := br.readBits(4)
if err != nil {
return err
}
if cnt > 0 {
// a run of zero lengths; the array is already zeroed
i += cnt + 1
continue
}
}
bitlength[i] = byte(n)
}
var bl huffmanDecoder
bl.init(bitlength[:])
for i := 0; i < len(codeLength); i++ {
l, err := bl.readSym(br)
if err != nil {
return err
}
if l < 16 {
codeLength[i] = byte(l)
continue
}
var count int
var value byte
switch l {
case 16, 18:
count, err = br.readBits(3)
count += 3
default:
count, err = br.readBits(7)
count += 11
}
if err != nil {
return err
}
if l < 18 {
if i == 0 {
return ErrCorrupt
}
value = codeLength[i-1]
}
for ; count > 0 && i < len(codeLength); i++ {
codeLength[i] = value
count--
}
i--
}
return nil
}