Абзац
:: Поиск
:: Поддержка проекта
Webmoney:
  • Z610389805629
  • R427996570517
  • E023541002978
  • :: №32 (10.10.2009) Просмотров: 4546

    Автор: Александр Синяков / SAM style.

    Рубрика: В помощь разработчику.

    Номер: №32 (10.10.2009).



    Dizpack. Упаковка текстов

    От редактора. Как-то на форуме zx.pk.ru появилась тема «Упаковка текстов» (http://zx.pk.ru/showthread.php?t=8534). Автор темы искал готовые решения упаковки/распаковки текстов, которые способны распаковывать данные побайтно «на лету». Иначе говоря, был необходим такой упаков­щик, при распаковке которому не требуется буфер для распакованного. Тема меня заинтересовала, и я даже написал свой подобный упаковщик, который использовал словарь часто встречающихся час­тиц и некоторых слов в русском языке. К сожалению, такой упаковщик не дал хороших результатов, и я забросил его дальнейшее развитие.

    Но данный вопрос не давал мне покоя, и я связался с друзьями, которых попросил поразмыш­лять на эту тему. В этом номере мы публикуем результат мозгового штурма от Александра Синякова

    (SAM style). Стоит отметить еще то, что у Александра изначально была другая идея, отличная от той, что публикуется в этом номере. Тот метод, скорее всего, и попал бы в газету, если бы не были про­ведены тесты, которые в итоге не дали положительных результатов компрессии. Так же забегая впе­ред, скажу, что на эту тему уже практически готова статья от Виталия Гаврилова (Vitamin), которую мы опубликуем в следующем номере. Итак, слово Александру.

    В основе метода лежит замена наиболее час­то встречаемых в тексте символов на полубайты. 15 самых частых символов будут представлены как 0..E. 15 следующих за ними по частоте - F0..FE. следующие 15 - FF0..FFE и так далее. Сжатый текст преимущественно на одном языке получается в районе 60-90% от оригинала. Преимуществом яв­ляется возможность безбуферной распаковки тек­ста - просто вынимая байт за байтом из запако­ванных данных. Данный метод сжатия является частным случаем алгоритма Хаффмана. Такой спо­соб, например, применялся для сжатия текстов в играх серии DIZZY (откуда и название). Минус дан­ного алгоритма в том, что при сжатии файлов с рав­номерным распределением большого числа сим­волов произойдет обратный эффект - выходной блок станет в несколько раз больше исходного.

    Формат файла.

    1. Заголовок:

    +0 - «DZ1»,0 (сигнатура + номер версии - 4 байта).

    +4,5 - длина распакованного (для контроля конца распаковки).

    +6 - размер таблицы в байтах.

    +7... таблица символов в порядке убывания ко­личества вхождений в исходный файл.

    2. После таблицы - данные.

    Стоит отметить еще то, что данный упа­ковщик/распаковщик создан так же для платфор­мы PC. Весь пакет с исходными текстами мож­но скачать по адресу: http://abzac.retropc.ru/files/dizpack.rar

    Ниже приведен исходный текст для Спектрума.


    ;Dizpack, by SAM style
    ;обязательно круглые
    frqtab    EQU #6000
    symtab    EQU #6200
        ORG #6300
    ;Пример использования упаковщика и распаковщика
        LD HL,text    ;HL - откуда паковать
        LD DE,bufa    ;DE - куда паковать
        LD BC,txtlen    ;BC - сколько байт
        CALL PACK    ;пакуем
        LD DE,bufa
        AND A
        SBC HL,DE    ;HL - длинна упакованного файла
        LD HL,bufa
        CALL UNPACK    ;инициализация распаковки
            ;самой распаковки здесь не происходит.
    ;Проверка правильности распаковки (была сделана для тестирования распаковки - в прин­ципе теперь не нужна)
        LD DE,text
    tst_1    CALL GETBYTE    ;вынимаем байт из потока
        RET NC
        LD C,A
        LD A,(DE)
        CP C
        JR NZ,err
        INC DE
        JR tst_1
    err    LD A,2
        OUT (254),A
        RET
    ;---------------------------
    ;Проверка сигнатуры
    TESTSIG    LD E,(HL)
        INC HL
        LD D,(HL)
        INC HL
        EX DE,HL
        AND A
        SBC HL,BC
        EX DE,HL
        LD A,D
        OR E
        RET Z
        SCF
        RET
    ;-------------
    ;UNPACK - инициализация распаковки
    ;распаковки не происходит!
    ;Вход: HL = адрес упакованного блока
    ;Выход: CY=1 (C) - не поддерживаемый формат ;CY=0 (NC) - можно распаковывать
    UNPACK    LD BC,«DZ»
        CALL TESTSIG
        RET C
        LD BC,#0031
        CALL TESTSIG
        RET C
        LD C,(HL)
        INC HL
        LD B,(HL)
        INC HL
        LD (GETBYTE+1),BC
        LD A,(HL)
        INC HL
        LD (unp_ta+1),HL
        ADD A,L
        LD L,A
        ADC A,H
        SUB L
        LD H,A
        LD (unp_ad+1),HL
        LD A,#A7
        LD (GETHALF),A    ;(код команды AND A)
        AND A
        RET
    ;GETBYTE - выемка байта из потока.
    ;Вход: ничего, всё инициализируется через UNPACK.
    ;Выход: CY=0 (NC) - уже нечего вынимать;CY=1 (C) вынут байт A=его код.
    GETBYTE    LD BC,0
        LD A,B
        OR C
        RET Z
        DEC BC
        LD (GETBYTE+1),BC
    unp_ad    LD HL,0
        LD C,-15
    gbt_1    LD A,C
        ADD A,15
        LD C,A
        CALL GETHALF
        CP 15
        JR Z,gbt_1
        ADD A,C
        LD (unp_ad+1),HL
    unp_ta    LD HL,0
        LD C,A
        LD B,0
        ADD HL,BC
        LD A,(HL)
        SCF
        RET
    GETHALF    AND A
        LD A,(HL)
        JR C,ghl_1
        RRCA
        RRCA
        RRCA
        RRCA
    ghl_1    AND 15
        EXA
        LD A,(GETHALF)
        XOR #90
        LD (GETHALF),A
        CP #A7
        JR NZ,ghl_2
        INC HL
    ghl_2    EXA
        RET
    ;-----------------------
    ;Вход: HL - откуда паковать, DE - куда, BC - сколько байт
    ;Выход: HL - следующий адрес за упакованным блоком
    PACK    EX DE,HL
        LD (HL), «D»
        INC HL
        LD (HL), «Z»
        INC HL
        LD (HL), «1»
        INC HL
        LD (HL),#00
        INC HL
        LD (HL),C
        INC HL
        LD (HL),B
        INC HL
        EX DE,HL
        PUSH BC
        PUSH HL
        PUSH DE
        CALL MAKETAB
        LD HL,frqtab
        LD E,0
    pk_1    INC H
        LD A,(HL)
        DEC H
        OR (HL)
        JR Z,pk_2
        INC E
        INC L
        JR NZ,pk_1
    pk_2    LD A,E
        POP DE
        LD (DE),A
        INC DE
        LD C,A
        LD B,0
        AND A
        JR NZ,pk_3
        INC B
    pk_3    LD HL,symtab
        LDIR
        EX DE,HL
        POP DE
        POP BC    ;DE:FROM;HL:TO;BC:COUNT
        XOR A
        EXA    ;Z:1ST HALFBYTE, NZ:2ND
    pk_35    LD A,(DE)
        PUSH HL
        LD HL,symtab
    pk_4    CP (HL)
        JR Z,pk_5
        INC L
        JR NZ,pk_4
    pk_5    LD A,L
        POP HL
    pk_6    CP 15
        JR C,pk_7
        SUB 15
        PUSH AF
        LD A,15
        CALL PUT_IN
        POP AF
        JR pk_6
    pk_7    CALL PUT_IN
        INC DE
        DEC BC
        LD A,B
        OR C
        JR NZ,pk_35
        EXA
        AND A
        RET Z
        EXA
        LD A,15
    PUT_IN    RLD
        EXA
        XOR 2
        JR NZ,pin_1
        INC HL
    pin_1    EXA
        RET
    ;------------------
    ;Вход: HL: адрес текста, BC: длина
    ;Выход: frqtab и symtab - упорядоченная таблица частот и символов.
    ;Таблицы frqtab и symtab обязательно должны идти друг за другом.
    MAKETAB    PUSH HL
        LD HL,frqtab
        XOR A
    mtb_1    LD (HL),A
        INC H
        LD (HL),A
        DEC H
        INC L
        JR NZ,mtb_1
        POP DE
        LD HL,frqtab
    mtb_2    LD A,(DE)
        LD L,A
        INC (HL)
        JR NZ,mtb_3
        INC H
        INC (HL)
        DEC H
    mtb_3    INC DE
        DEC BC
        LD A,B
        OR C
        JR NZ,mtb_2
        LD HL,symtab
    mtb_4    LD (HL),L
        INC L
        JR NZ,mtb_4
        LD HL,frqtab
    mtb_5    AND A
        EXA
        LD B,255
        LD L,0
    mtb_6    PUSH HL
        LD E,(HL)
        INC H
        LD D,(HL)
        INC L
        LD A,(HL)
        DEC H
        LD L,(HL)
        LD H,A
        EX DE,HL
        AND A
        SBC HL,DE
        POP HL
        JR NC,mtb_7
        CALL SWAP
        INC H
        CALL SWAP
        INC H
        CALL SWAP
        DEC H
        DEC H
        EXA
        SCF
        EXA
    mtb_7    INC L
        DJNZ mtb_6
        EXA
        JR C,mtb_5
        RET
    SWAP    LD C,(HL)
        INC L
        LD A,(HL)
        LD (HL),C
        DEC L
        LD (HL),A
        RET
    text    INCBIN «main_txt»    ;подгружаем текст, который нужно упаковать
    txtlen    EQU $-text
    bufa    EQU $    ;буфер для упаковки



    © 2004-2013 Perspective group