Упаковщики

[Manwe]

Хм, похоже, при распаковке LZSA2 нужно сперва обрабатывать LL, а только потом всё остальное (в документации об этом, конечно, не сказано). Странно и неудобно, ведь MMM и XYZ по краям байта, проще и короче с них начать. Неоптимальный формат, однако.

[ivagor]

нужно сперва обрабатывать LL, а только потом всё остальное

Не скажу про все случаи, но например в начале распаковки это потенциально экономит токен, скопировали затравочный фрагмент и потом еще можем сослаться в него ссылкой, и все в одном токене.

Неоптимальный формат

"LZSA is a collection of byte-aligned compression formats that are specifically engineered for very fast decompression on 8-bit systems.", на pdp11 они не замахивались.

[Manwe]

"LZSA is a collection of byte-aligned compression formats that are specifically engineered for very fast decompression on 8-bit systems.", на pdp11 они не замахивались.

На 8-битках тоже оптимальней доставать LL с краю байта, а не из середины.

[ivagor]

В токене три компонента и не получится все расположить с краю. Насколько я понимаю, они набрали статистику на типичных файлах, какие токены встречаются чаще и оптимизировали разбор наиболее частых. Автор бывал на форуме или можно написать ему напрямую, если что.

- - - Добавлено - - -

Вспомнил пример exomizera, когда автор выбрал формат битового потока удобный для 6502, не очень удобный для z80 и совсем неудобный для 8080. В том случае я даже не стал пересобирать упаковщик, а сделал отдельный постобработчик, который переставлял биты. Но я конечно был не один такой умный и вскоре автор добавил опцию для изменения формата битового потока в упаковщик. Аналогично можно поступить и с lzsa, или изменить упаковщик или сделать отдельную утилиту для постобработки сжатых файлов, которая будет переставлять биты в токене или где угодно и как угодно.

[Manwe]

Аналогично можно поступить и с lzsa, или изменить упаковщик или сделать отдельную утилиту для постобработки сжатых файлов, которая будет переставлять биты в токене или где угодно и как угодно.

Да, тоже задумался об этом.
Пока вот как получилось: на 26 байт короче (перемещаемый вариант - на 16 байт короче) и на 5.4% быстрей. Потестируйте, пожалуйста, на сложных файлах.

; LZSA2 PDP-11 decompressor by Manwe/SandS
; Thanks to Ivan Gorodetsky
; Usage:
; MOV #src_adr,R1
; MOV #dst_adr,R2
; CALL Unpack


Unpack: MOV PC,Table+2      ; correct table address
        ADD #XYZ-Unpack-2,Table+2
        CLR R4              ; no nibbles sign
Token:  MOVB (R1)+,R3       ; read token

Liter:  MOV R3,R0
        ASR R0
        ASR R0
        ASR R0
        BIC #177774,R0      ; get 2 bits
        BEQ Decode
        CMP R0,#3           ; literals length
        BNE Copy
            MOV #239.,Limit
            CALL Extend
Copy:   MOVB (R1)+,(R2)+    ; literals length in R0
        SOB R0,Copy

Decode: MOV R3,-(SP)    
        COM R3              ; invert for faster detect
        ROLB R3             ; get 2 bits
        ROL R0
        ROLB R3
        ROL R0
Table:  MOVB XYZ(R0),R0
        ADD R0,PC           ; run subroutine
Save:   MOV R0,(PC)+        ; save offset for future
Offset: .WORD 0

Match:  MOV (SP)+,R0
        BIC #177770,R0      ; get 3 bits
        CMP R0,#7
        BNE Clone
            MOV #233.,Limit
            CALL Extend
Clone:  ADD #2,R0           ; match length
        TSTB R0
        BEQ Exit

        MOV R2,R3
        ADD Offset,R3
1:      MOVB (R3)+,(R2)+
        SOB R0,1
        BR Token


XYZ:    .BYTE oOther-Save, o13bit-Save, o9bit-Save, o5bit-Save

o5bit:  CALL Nibble         ; get nibble in R0
        ROLB R3
        ROL R0
        BIS #177740,R0      ; set bits 5-15
        BR Save

o9bit:  ROLB R3
        ROL R0
        SWAB R0
        BISB (R1)+,R0
        BIS #177000,R0      ; set bits 9-15
        BR Save

o13bit: CALL Nibble         ; get nibble in R0
        ROLB R3
        ROL R0
        SWAB R0
        BISB (R1)+,R0       ; 8 bits
        BIS #160000,R0      ; set bits 13-15
        SUB #512.,R0
        BR Save

oOther: ROLB R3
        BCS 1
            MOV Offset,R0   ; reuse offset
            BR Match
1:      MOVB (R1)+,R0
        SWAB R0
        CLRB R0
        BISB (R1)+,R0
        BR Save

Nibble: COM R4
        BNE 1
            MOV R5,R0
            BR 2
1:      MOVB (R1)+,R5       ; read 2 nibbles
        MOV R5,R0
        ASR R0
        ASR R0
        ASR R0
        ASR R0
2:      BIC #177760,R0      ; leave 4 low bits
        RET

Extend: MOV R0,-(SP)        ; save original value
        CALL Nibble         ; get nibble in R0
        CMP R0,#15.
        BNE Ext2
            CLR R0
            BISB (R1)+,R0
            CMP R0,(PC)+
Limit:      .WORD 239.
            BNE Ext1
                MOVB (R1)+,R0   ; read low byte
                SWAB R0
                CLRB R0
                BISB (R1)+,R0   ; read high byte
                SWAB R0
                TST (SP)+       ; skip saved R0
                RET
Ext1:       ADD #15.,R0
Ext2:   ADD (SP)+,R0        ; add original value
Exit:   RET

.END

Попробую ещё с отрицательными оффсетами поколдовать - вдруг получится чуть оптимизировать.

[MM]

Пожалуйста, посоветуйте по упаковке 4-битного звука ( речевое сообщение о разряде батарейки ) с семплрейтом 8 Кгц - это будет эффективнее хотя бы на 50% по сравнению с обычным хранением в формате .WAV ?
Какая скорость декомпрессии отрезка 3.5 Кбайт ( размер выходного файла ) на БК11М-4 мгц ?

[Advertiser]

[grf]

Тем, что по данной вами ссылке нету упаковщиков под pdp-11, только распаковщики. А самому писать лень. Ибо не приспичило.
Не, может, где-то когда-то кто-то давал ссылки на упаковщики zx0..2, lzsa2, написанные для pdp-11, но это как-то мимо меня прошло.

LZ сделал Женя Пашигоров, но он был заточен на сжатие кучи файлов в один архив:


Блин, вот что значит склероз )) Сначала я вспомнил, что Женя написал LZ и мы его активно использовали для сжатия каталогов/дисков. Потом я сжал им картинку TITR1.PIC и получил 15к (восьмеричных). Подумал, что можно поискать исходники LZ и сделать распаковщик для встраивания в программы. А потом оказалось, что Женя сделал этот распаковщик сто лет назад и мы с ним уже применяли его в Color Lines:




Все было под руками

[Manwe]

Пожалуйста, посоветуйте по упаковке 4-битного звука ( речевое сообщение о разряде батарейки ) с семплрейтом 8 Кгц - это будет эффективнее хотя бы на 50% по сравнению с обычным хранением в формате .WAV ?
Какая скорость декомпрессии отрезка 3.5 Кбайт ( размер выходного файла ) на БК11М-4 мгц ?

Я писал алгоритм 4-битного ADPCM, скорость приемлемая. Кажется, там использовались таблицы для распаковки. С ходу не вспомню, надо искать алгоритм. Поищу попозже.

[ivagor]

Manwe, попробовал сам реализовать имевшуюся заготовку по lzsa2, сократил на 6 байт (до 264) и ускорил примерно на 8%. Не так уж плохо, если бы не было zx1. Да, удалось немного обойти его по скорости, но zx1 сжимает лучше и распаковщик 144 байта против 264. Готов поучаствовать в тестировании, если получится сократить распаковщик lzsa2 до 144 байт при хотя бы символическом опережении zx1 по скорости или пусть распаковщик останется большим, но тогда надо обогнать хотя бы процентов на 10.

[Manwe]

Manwe, попробовал сам реализовать имевшуюся заготовку по lzsa2, сократил на 6 байт (до 264) и ускорил примерно на 8%. Не так уж плохо, если бы не было zx1. Да, удалось немного обойти его по скорости, но zx1 сжимает лучше и распаковщик 144 байта против 264. Готов поучаствовать в тестировании, если получится сократить распаковщик lzsa2 до 144 байт при хотя бы символическом опережении zx1 по скорости или пусть распаковщик останется большим, но тогда надо обогнать хотя бы процентов на 10.

Думаю, это возможно, если сконвертировать входной поток. Ниблы, отвечающие за смещения, нужно инвертировать. Парам байтов с 16-битным смещением нужно изменить знак и поменять порядок этих байтов. Думаю, это сократит размер распаковщика байт на 10 и ускорит на пару процентов. Пока что у меня размер 254 байта (перемещаемый вариант). Ещё можно поменять местами MMM и LL в токене, это даст сокращение распаковщика на 1 инструкцию и ускорение.

Потестируй, пожалуйста, мой распаковщик. Мне пока не удалось создать упакованные файлы, в которых используется длинное смещение. Кстати, блок обработки длинных смещений можно вообще выпилить в ряде случаев (написать утилиту, анализирующую архив - если длинных смещений не найдено, она предложит использовать укороченную версию распаковщика).