Деревья хаффмана - как с ними работать

[jerri]

много я ковырял паковщиков и архиваторов
но так и не понял как преобразуются данные из битов в байты и слова

а самое главное как создается свое дерево для архива
для примера взят паковщик RNC_propack

вот из него 2 куска кода

создание таблицы

.MakeHuff:
    ld    a,5
    call    .GetBits

    ld    a,(rncdat)
    or    a
    ret    z

    ld    (temp1),a
    ld    (temp2),a

    ld    hl,tmptab

.MakeHuff2:
    push    hl
    ld    a,4
    call    .GetBits

    ld    hl,temp2
    dec    (hl)

    pop    hl

    ld    a,(rncdat)
    ld    (hl),a

    inc    hl

    jr    nz,.MakeHuff2

    xor    a
    ld    (regy),a
    ld    (hufcde),a
    ld    (hufcde+1),a
    ld    (hufbse),a

    inc    a

    ld    (bitlen),a

    ld    a,#80
    ld    (hufbse+1),a
.MakeHuff3:
    ld    a,(temp1)
    ld    (temp2),a

    xor    a
    ld    (temp3),a

.MakeHuff4:
    ld    a,[temp3]
    ld    [regx],a

    ld    hl,tmptab
    add    a,l
    ld    l,a
    jr    nc,$+3
    inc    h
    ld    a,(bitlen)
    cp    (hl)
    jp    nz,.MakeHuff8

    ld    (regx),a
    add    a,a
    
    ld    hl,msktab
    add    a,l
    ld    l,a
    jr    nc,$+3
    inc    h

    ld    b,(hl)

    ld    a,(regy)
    ld    c,a
    add    a,2
    ld    (regy),a

    ld    a,(hufftab)
    add    a,c
    ld    e,a
    ld    a,(hufftab+1)
    adc    0
    ld    d,a

    ld    a,b
    ld    (de),a

    inc    hl
    inc    de

    ld    a,(hl)
    ld    (de),a

    ld    bc,(rncdat)
    ld    de,(hufcde)

    ld    a,(regx)

.MakeHuff5:
    sla    e
    rl    d
    rr    b
    rr    c

    dec    a
    jr    nz,.MakeHuff5

    ld    hl,rncdat+3
    ld    (hl),d
    dec    hl
    ld    (hl),e
    dec    hl

    ld    a,(bitlen)
    ld    e,a

    ld    a,16
    sub    e
    jr    z,.MakeHuff7

    ld    d,a

.MakeHuff6:
    srl    b
    rr    c

    dec    d
    jr    nz,.MakeHuff6

.MakeHuff7:
    ld    (hl),b
    dec    hl
    ld    (hl),c

    ld    a,(regy)
    ld    b,a
    add    2
    ld    (regy),a


    ld    hl,(hufftab)
    add    a,l
    ld    l,a
    jr    nc,$+3
    inc    h
    ld    a,(rncdat)
    ld    (hl),a
    inc    hl

    ld    a,[rncdat+1]
    ld    (hl),a
        inc    hl

    ld    a,l
    add    15*4
    ld    l,a

    jr    nc,.nocarry2
    inc    h
.nocarry2:

    ld    a,(temp3)
    ld    (hl),a

    inc    hl

    ld    a,(bitlen)
    ld    (hl),a

    ld    bc,(hufbse)

    ld    a,(hufcde)
    add    a,c
    ld    (hufcde),a
    ld    a,(hufcde+1)
    adc    a,b
    ld    (hufcde+1),a

.MakeHuff8:
    ld    hl,temp3
    inc    (hl)

    ld    hl,temp2
    dec    (hl)
    jp    nz,.MakeHuff4

    ld    hl,hufbse+1
    srl    (hl)
    dec    hl
    rr    (hl)
    ld    a,(bitlen)
    inc    a
    ld    (bitlen),a
    cp    17
    jp    nz,.MakeHuff3

    ret

и выбор 16 битных данных из нее

.GetVal:
    ld    hl,(hufftab)
    dec    hl
.GetVal2:

    inc    hl
.GetVal3:
    ld    a,(bitbufl)
    and    (hl)
    ld    b,a
    ld    (rncdat),a

    inc    hl
    ld    a,(bitbufl+1)
    and    (hl)
    ld    c,a
    ld    (rncdat+1),a

    inc    hl
    ld    a,b
    cp    (hl)
    inc    hl

    jr    nz,.GetVal2

    ld    a,c
    cp    (hl)
    inc    hl

    jr    nz,.GetVal3

    ld    a,l
    add    15*4
    ld    l,a
    jr    nc,.nocarry
    inc    h
.nocarry:

    ld    a,(hl)
    inc    hl
    push    af

    ld    a,(hl)
    call    .GetBits

    pop    af
    cp    2
    jr    nc,.GetVal4

    ld    (rncdat),a

    ld    hl,rncdat+1
    ld    (hl),0
    ret

.GetVal4:
    dec    a
    push    af
    call    .GetBits
    pop    af
    cp    8
    jr    c,.GetVal5

    ld    hl,bittabl-8
    add    a,l
    ld    l,a
    jr    nc,$+3
    inc    h

    ld    a,(rncdat+1)
    or    (hl)
    ld    (rncdat+1),a
    ret

.GetVal5:
    ld    hl,bittabl
    add    a,l
    ld    l,a
    jr    nc,$+3
    inc    h
    ld    a,[rncdat]
    or    [hl]
    ld    [rncdat],a
    ret

.bittabl:
    DB    1,2,4,8,16,32,64,128

вообще имеются 3 таблицы по 128 байт и 1 таблица 16 байт
исходники во вложении

на кривость кода не смотрите - это тупой порт М68000 - MOS6502 - Z80gb_edition
так что тут править и править

что мне нужно - понять как оно работает
и как создается таблица

[Advertiser]

[elf/2]

github.com/gildas-lormeau/zip.js
внутри deflate.js и inflate.js. это нормально откоментированые исходники для упаковки/распаковки с использованием классического метода deflate из pkzip, т.е. сначала жмем LZ77, а то что получилось уже динамическим хафманом.

не поможет?

[jerri]

все здорово но мне надо как ААА обьяснять... я уперся в стену

[Лас]

все здорово но мне надо как ААА обьяснять... я уперся в стену

1. http://zxpress.ru/book_articles.php?id=252
2. http://zxpress.ru/article.php?id=8569 = (txt file) by alone
3. http://algolist.manual.ru/compress/standard/huffman.php ~ (http://zxpress.ru/article.php?id=11234)

[IanPo]

Принцип построения дерева очень простой:
берем самый частый символ - это бит 0,
следующий по частоте будет 10,
потом 110, и т.д.
Нарисуйте бинарное дерево:
0 - Root - 1
затем из 1 выводите 0 и 1 следующего уровня и т.д.

[jerri]

Во вложении таблица с данными анализатора
как на основе хаффмановских телодвижений эту таблицу ужать?
хотя там 3 таблицы

последний вариант депакера прилагаю

[alone]

Принцип построения дерева очень простой:
берем самый частый символ - это бит 0,
следующий по частоте будет 10,
потом 110, и т.д.
Нарисуйте бинарное дерево:
0 - Root - 1
затем из 1 выводите 0 и 1 следующего уровня и т.д.

Неправильно.
Надо отсортировать листья по частоте, потом объединить два самых редких в узел и засунуть его в тот же список с суммарной частотой, потом снова два самых редких и т.д., пока не объединим все. Это и будет дерево Хаффмана.

[jerri]

alone, а как это делается в виде программы для Z80 есть?

[Vitamin]

alone, а как это делается в виде программы для Z80 есть?

А не ты ли jpeg viewer писал?

[jerri]

Vitamin, нет не я его РРА писал - я только оболочку к его декодеру прикручивал.
высшая математика в мои достоинства не входит