Важная информация

User Tag List

Страница 1 из 4 1234 ПоследняяПоследняя
Показано с 1 по 10 из 34

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

  1. #1
    Guru Аватар для jerri
    Регистрация
    01.03.2005
    Адрес
    Samara
    Сообщений
    3,363
    Благодарностей: 706
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию Деревья хаффмана - как с ними работать

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

    а самое главное как создается свое дерево для архива
    для примера взят паковщик 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
    так что тут править и править

    что мне нужно - понять как оно работает
    и как создается таблица
    Вложения Вложения
    • Тип файла: a80 RNC_1.a80 (10.0 Кб, Просмотров: 64)
    С уважением,
    Jerri / Red Triangle.
    [02.05.2014] не забудь этот день. Чубайс должен умереть. Dixi.
    [l'Abbey des morts TSEvo EV...5%] kiwi кошелек +79178162712

  2. #1
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  3. #2
    Moderator Аватар для elf/2
    Регистрация
    14.01.2005
    Адрес
    N.Novgorod
    Сообщений
    803
    Благодарностей: 117
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

    не поможет?

  4. Эти 2 пользователя(ей) поблагодарили elf/2 за это полезное сообщение:
    GriV (04.09.2012), jerri (30.08.2012)

  5. #3
    Guru Аватар для jerri
    Регистрация
    01.03.2005
    Адрес
    Samara
    Сообщений
    3,363
    Благодарностей: 706
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    все здорово но мне надо как ААА обьяснять... я уперся в стену
    С уважением,
    Jerri / Red Triangle.
    [02.05.2014] не забудь этот день. Чубайс должен умереть. Dixi.
    [l'Abbey des morts TSEvo EV...5%] kiwi кошелек +79178162712

  6. #4
    Veteran Аватар для Лас
    Регистрация
    18.11.2008
    Адрес
    пос.Полярный, ЯНАО
    Сообщений
    1,062
    Благодарностей: 780
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от 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)

  7. Эти 2 пользователя(ей) поблагодарили Лас за это полезное сообщение:
    GriV (04.09.2012), jerri (30.08.2012)

  8. #5
    Master
    Регистрация
    31.03.2008
    Адрес
    Москва
    Сообщений
    573
    Благодарностей: 275
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Принцип построения дерева очень простой:
    берем самый частый символ - это бит 0,
    следующий по частоте будет 10,
    потом 110, и т.д.
    Нарисуйте бинарное дерево:
    0 - Root - 1
    затем из 1 выводите 0 и 1 следующего уровня и т.д.
    ZXM-Phoenix rev01 2048, FloppyEmulator/SD, IDE->CF 4Gb

  9. Этот пользователь поблагодарил IanPo за это полезное сообщение:
    jerri (30.08.2012)

  10. #6
    Guru Аватар для jerri
    Регистрация
    01.03.2005
    Адрес
    Samara
    Сообщений
    3,363
    Благодарностей: 706
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

    последний вариант депакера прилагаю
    Вложения Вложения
    • Тип файла: txt data.txt (4.3 Кб, Просмотров: 147)
    • Тип файла: a80 RNC_1_.a80 (6.3 Кб, Просмотров: 76)
    С уважением,
    Jerri / Red Triangle.
    [02.05.2014] не забудь этот день. Чубайс должен умереть. Dixi.
    [l'Abbey des morts TSEvo EV...5%] kiwi кошелек +79178162712

  11. #7
    Guru
    Регистрация
    03.01.2006
    Адрес
    Рязань
    Сообщений
    2,935
    Благодарностей: 1071
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от IanPo Посмотреть сообщение
    Принцип построения дерева очень простой:
    берем самый частый символ - это бит 0,
    следующий по частоте будет 10,
    потом 110, и т.д.
    Нарисуйте бинарное дерево:
    0 - Root - 1
    затем из 1 выводите 0 и 1 следующего уровня и т.д.
    Неправильно.
    Надо отсортировать листья по частоте, потом объединить два самых редких в узел и засунуть его в тот же список с суммарной частотой, потом снова два самых редких и т.д., пока не объединим все. Это и будет дерево Хаффмана.

  12. Этот пользователь поблагодарил alone за это полезное сообщение:
    IanPo (03.09.2012)

  13. #8
    Guru Аватар для jerri
    Регистрация
    01.03.2005
    Адрес
    Samara
    Сообщений
    3,363
    Благодарностей: 706
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    alone, а как это делается в виде программы для Z80 есть?
    С уважением,
    Jerri / Red Triangle.
    [02.05.2014] не забудь этот день. Чубайс должен умереть. Dixi.
    [l'Abbey des morts TSEvo EV...5%] kiwi кошелек +79178162712

  14. #9
    Vitamin C++ Аватар для Vitamin
    Регистрация
    14.01.2005
    Адрес
    Таганрог, Россия
    Сообщений
    4,031
    Благодарностей: 1426
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от jerri Посмотреть сообщение
    alone, а как это делается в виде программы для Z80 есть?
    А не ты ли jpeg viewer писал?

  15. #10
    Guru Аватар для jerri
    Регистрация
    01.03.2005
    Адрес
    Samara
    Сообщений
    3,363
    Благодарностей: 706
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Vitamin, нет не я его РРА писал - я только оболочку к его декодеру прикручивал.
    высшая математика в мои достоинства не входит
    Последний раз редактировалось jerri; 03.09.2012 в 11:00.
    С уважением,
    Jerri / Red Triangle.
    [02.05.2014] не забудь этот день. Чубайс должен умереть. Dixi.
    [l'Abbey des morts TSEvo EV...5%] kiwi кошелек +79178162712

Страница 1 из 4 1234 ПоследняяПоследняя

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. PAL/GAL и все что с ними связано.
    от Mick в разделе Клоны на ПЛИС, МК и БМК
    Ответов: 288
    Последнее: 12.12.2017, 15:28
  2. ДВК (и всё, что с ними связано)
    от Grand в разделе ДВК, УКНЦ
    Ответов: 3349
    Последнее: 08.12.2017, 01:12
  3. Видеорежимы и работа с ними
    от icebear в разделе Программирование
    Ответов: 23
    Последнее: 26.07.2005, 10:55
  4. Видеорежимы и работа с ними
    от icebear в разделе Unsorted
    Ответов: 3
    Последнее: 21.07.2005, 09:49

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •