Хм, похоже, при распаковке LZSA2 нужно сперва обрабатывать LL, а только потом всё остальное (в документации об этом, конечно, не сказано). Странно и неудобно, ведь MMM и XYZ по краям байта, проще и короче с них начать. Неоптимальный формат, однако.
Вид для печати
Хм, похоже, при распаковке LZSA2 нужно сперва обрабатывать LL, а только потом всё остальное (в документации об этом, конечно, не сказано). Странно и неудобно, ведь MMM и XYZ по краям байта, проще и короче с них начать. Неоптимальный формат, однако.
Не скажу про все случаи, но например в начале распаковки это потенциально экономит токен, скопировали затравочный фрагмент и потом еще можем сослаться в него ссылкой, и все в одном токене.Цитата:
Сообщение от Manwe
"LZSA is a collection of byte-aligned compression formats that are specifically engineered for very fast decompression on 8-bit systems.", на pdp11 они не замахивались.Цитата:
Сообщение от Manwe
На 8-битках тоже оптимальней доставать LL с краю байта, а не из середины.Цитата:
Сообщение от ivagor
В токене три компонента и не получится все расположить с краю. Насколько я понимаю, они набрали статистику на типичных файлах, какие токены встречаются чаще и оптимизировали разбор наиболее частых. Автор бывал на форуме или можно написать ему напрямую, если что.
- - - Добавлено - - -
Вспомнил пример exomizera, когда автор выбрал формат битового потока удобный для 6502, не очень удобный для z80 и совсем неудобный для 8080. В том случае я даже не стал пересобирать упаковщик, а сделал отдельный постобработчик, который переставлял биты. Но я конечно был не один такой умный и вскоре автор добавил опцию для изменения формата битового потока в упаковщик. Аналогично можно поступить и с lzsa, или изменить упаковщик или сделать отдельную утилиту для постобработки сжатых файлов, которая будет переставлять биты в токене или где угодно и как угодно.
Да, тоже задумался об этом.Цитата:
Сообщение от ivagor
Пока вот как получилось: на 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
Пожалуйста, посоветуйте по упаковке 4-битного звука ( речевое сообщение о разряде батарейки ) с семплрейтом 8 Кгц - это будет эффективнее хотя бы на 50% по сравнению с обычным хранением в формате .WAV ?
Какая скорость декомпрессии отрезка 3.5 Кбайт ( размер выходного файла ) на БК11М-4 мгц ?
LZ сделал Женя Пашигоров, но он был заточен на сжатие кучи файлов в один архив:Цитата:
Сообщение от gid
http://zx-pk.ru/images/ext/2016/04/08/01/lzb.png
Блин, вот что значит склероз )) Сначала я вспомнил, что Женя написал LZ и мы его активно использовали для сжатия каталогов/дисков. Потом я сжал им картинку TITR1.PIC и получил 15к (восьмеричных). Подумал, что можно поискать исходники LZ и сделать распаковщик для встраивания в программы. А потом оказалось, что Женя сделал этот распаковщик сто лет назад и мы с ним уже применяли его в Color Lines:
Вложение 75937
Вложение 75938
Все было под руками :)
Я писал алгоритм 4-битного ADPCM, скорость приемлемая. Кажется, там использовались таблицы для распаковки. С ходу не вспомню, надо искать алгоритм. Поищу попозже.Цитата:
Сообщение от MM
Manwe, попробовал сам реализовать имевшуюся заготовку по lzsa2, сократил на 6 байт (до 264) и ускорил примерно на 8%. Не так уж плохо, если бы не было zx1. Да, удалось немного обойти его по скорости, но zx1 сжимает лучше и распаковщик 144 байта против 264. Готов поучаствовать в тестировании, если получится сократить распаковщик lzsa2 до 144 байт при хотя бы символическом опережении zx1 по скорости или пусть распаковщик останется большим, но тогда надо обогнать хотя бы процентов на 10.
Думаю, это возможно, если сконвертировать входной поток. Ниблы, отвечающие за смещения, нужно инвертировать. Парам байтов с 16-битным смещением нужно изменить знак и поменять порядок этих байтов. Думаю, это сократит размер распаковщика байт на 10 и ускорит на пару процентов. Пока что у меня размер 254 байта (перемещаемый вариант). Ещё можно поменять местами MMM и LL в токене, это даст сокращение распаковщика на 1 инструкцию и ускорение.Цитата:
Сообщение от ivagor
Потестируй, пожалуйста, мой распаковщик. Мне пока не удалось создать упакованные файлы, в которых используется длинное смещение. Кстати, блок обработки длинных смещений можно вообще выпилить в ряде случаев (написать утилиту, анализирующую архив - если длинных смещений не найдено, она предложит использовать укороченную версию распаковщика).