Архиватор с самым быстрым распаковщиком

[Alex Rider]

Проинтегрил депакер Титуса в свой проект. Графику я не конвертил в столбцы, память позволяет, а лишние тормоза при конвертации/выводе не нужны совсем. В общем, мой результат по сравнению с megalz: сжатые файлы весят на 12% больше, скорость распаковки в 4-5 раз выше (действительно, сопоставимо с ldir).

Спасибо Titus'у огромное!

[Blade]

А зачем вообще сжимать? Несжатая картинка с карточки быстрее загрузится.

[Alex Rider]

А зачем вообще сжимать? Несжатая картинка с карточки быстрее загрузится.

Несжатые картинки не лезут в 128к.

[Titus]

Залез в Great Codemasters Collection, и действительно - ниббловый метод убран, т.к. видимо признан неэффективным, и занимал лишние байты в депакере. Фактически депакер ничем не отличается, только выкинут один фрагмент. Также соптимизировал то, что подсказал Ивамото. Итого, размер депакера 101 байт.

; Pro Turbo Cruncher v2.1
;     Decompressor
;
; HL - Адрес начала упакованного фрагмента
; DE - Адрес для распаковки

OPUL:			
	LD   A,(HL)	; A' = (HL)			; Взять первый байт из потока
	EX   AF,AF'	; 
	LD   B,0	; B =  0
	LD   IX,DECO	; IX = DECO			; Константа для быстрого перехода
	CALL DECO-1	; ==> DECO-1			; В цикл депакера
	EX   AF,AF'	; 
	LD   (DE),A	; (DE) = A'			; Сохранить последний байт
	RET		; Выход
	
;--------------------------	
M5:
	RLCA		; C<-A-<			; Сдвинуть A влево, получить бит из потока
	JR   C,M6	; Если C = 1, то --> М6		; 
							; Метод: LZ, смещение 0..8192, длина 0..255
	LD   A,(HL)	; A = (HL)			; Получить тот же байт из потока
	AND  #1F	; A = A and $1F			;
	LD   B,A	; B = A				; B = 0..31 (старший байт смещения)
	INC  HL		; HL = HL + 1			; Перейти к следующему байту
	LD   C,(HL)	; C = (HL)			; Взять байт из потока (C - длина 0..255)
	JR   IYP	; --> IYP			; --> Копирование со смещением
M6:
							; Метод: LZ, смещение 2048..3071, длина 3..10
	AND  #C2	; A = A and 0xC2		; Оставить старшие 2 бита
							; Бит 1 равен 1
							
							; Соптимизировано
;	AND  #C0	; A = A and 0xC0		; Оставить старшие 2 бита
;	XOR  2		; A = A + 2			; Бит 1 равен 1
	
	JR   M7		; --> M7			; --> Подготовка копирования со смещением
LZMET:
	RLCA		; C<-A-<			; Сдвинуть A влево, получить бит из потока
	JR   C,M5	; Если C = 1, то --> М5		; 
							; Медод: LZ, смещение 0..2047, длина 3..10
	AND  #E0	; A = A and 0xE0		; Оставить в A старшие 3 бита 
	RLCA		; C<-A-<			; Сдвинуть A влево, получить бит из потока
	
M7:	RLCA		; C<-A-<			; Сдвинуть A влево, получить бит из потока
	RLCA		; C<-A-<			; Сдвинуть A влево, получить бит из потока
	LD   B,A	; B = A				; B - старший байт смещения (2 или 3 бита)
	LD   A,(HL)	; А = (HL)			; Получить тот же байт из потока
	AND  7		; A = A and 7			; Оставить в A младшие 3 бита
	ADD  A,3	; A = A + 3			;
	LD   C,A	; C = A				; C - 3..10 (длина копируемого фрагмента)
IYP:	
	INC  HL		; HL = HL + 1			; Перейти к следующему байту
	PUSH HL		; Сохранить HL
	LD   A,E	; A = E				; HL = DE - B.m(HL)
	SUB  (HL)	; A = A - (HL)			;
	LD   L,A	; L = A				;
	LD   A,D	; A = D				;
	SBC  A,B	; A = A - B - c			;
	LD   H,A	; H = A				;
	LD   B,0	; B = 0				;
	
DACO:	LDIR		; (HL)->(DE), len BC		; Копирование фрагмента из (HL) в (DE)
	POP  HL		; Восстановить HL		;
			;				; --> Вход
	INC  HL		; HL = HL + 1 			; Перейти к следующему байту 
	
							; Начало главного цикла
DECO:	LD   A,(HL)	; A = (HL) 			; Взять байт из потока
	RLCA		; C<-А-<			; Сдвинуть A влево, получить бит из потока
	JR   C,LZMET	; Если C = 1, то --> LZNET
	RLCA		; C<-A-<			; Сдвинуть A влево на 2 бита, получить
	RLCA		; C<-A-<			; два младших бита
	AND  3		; A = A and 3			;
	JR   NZ,M1	; Если A <> 0, то --> M1	; Если A <> 0, то --> M1
							; Метод: копирование блока длиной 1..32
	LD   C,(HL)	; C = (HL)			; Взять тот же байт из потока (длина фрагмента)
	INC  C		; C = C + 1			; Коррекция длины 1..32
	INC  HL		; HL = HL + 1			; Перейти к следующему байту
	LDIR		; (HL)->(DE), len BC		; Скопировать C байт из (HL) в (DE)
	JP   (IX)	; --> DECO			; в цикл --> DECO
	
M1:
	DEC  A		; A = A - 1			; A - 0..2
	
; С этого момента изменения

	RET Z		; Если A = 0, то выход -->	; Если A = 0, то конец распаковки -->
	
; Конец изменений

M2:	
	DEC  A		; A = A - 2			; A - 0..1
	LD   A,(HL)	; A = (HL)			; Взять байт из потока
	JR   Z,M4	; Если A^ = 0, то --> M4	; Если А^ = 0, то --> M3
							; Метод: Заливка 1..32
	AND  #1F	; A = A and 0x1F		;
	LD   C,A	; C = A
	INC  C		; C = C + 1			; C в диапазоне 1..32
	
M3:	INC  HL		; HL = HL + 1			; Перейти к следующему байту
	PUSH HL		; Сохранить HL
	LD   A,(HL)	; A = (HL)			; Взять байт из потока
	LD   H,D	; H = D
	LD   L,E	; L = E				; HL = адрес приемника
	INC  DE		; DE = DE + 1			; DE = адрес приемника + 1
	LD   (HL),A	; (HL) = A			; Записать байт для заливки в (HL)
	JR   DACO	; --> DACO			; Заливка фрагмента
M4:
							; Метод: Заливка 1..8192
	AND  #1F	; A = A and #1F			 
	LD   B,A	;				; B в диапазоне 0..31 (B - старший байт длины)
	INC  HL		; HL = HL + 1			; Перейти к следующему байту
	LD   C,(HL)	; C = (HL)			; Взять байт из потка (C - младший байт длины)
	JR   M3		; --> M3			; --> Заливка фрагмента

---------- Post added at 18:22 ---------- Previous post was at 18:18 ----------

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

[psb]

Проинтегрил депакер Титуса в свой проект.

замерь анрилом сколько тактов распаковывает?

[Alex Rider]

замерь анрилом сколько тактов распаковывает?

Нда, поторопился я с оценкой "сопоставимо с ldir"... Картинка размером 3200 байт распаковывается за ~128к тактов - в 2 раза медленнее ldir.

[Titus]

Нда, поторопился я с оценкой "сопоставимо с ldir"... Картинка размером 3200 байт распаковывается за ~128к тактов - в 2 раза медленнее ldir.

Все зависит от контента. Если сильно разбито на мелкие фрагменты, то может быть медленней, а если более крупные куски, то быстрее.

Прикинул примерно.
Метод копирования данных:
Экстракция заголовка, подготовка данных и переход в главный цикл - 65 тактов. Плюс собственно LDIR. Т.е. если копирование идет маленькими блоками по 3 байта, то тогда это будет в два раза медленнее LDIR.

[psb]

ну даже в 2 раза медленнее - это неплохо. я ожидал еще хуже, на полпорядка хотя бы.

[Alex Rider]

Т.е. если копирование идет маленькими блоками по 3 байта, то тогда это будет в два раза медленнее LDIR.

Мои картинки и не репрезантативны для оценки алгоритма, потому как я не конвертил картинку в столбцы. В моем случае, если бы законвертил, может быть, было би и еще быстрее, но к этому "быстрее" надо было бы добавить время на обратную переконвертацию картинки, ибо стеком быстрее выводить строчки, чем столбцы.

[shurik-ua]

Не уверен насчёт правильности замены конструкции

and C0
xor 2

на

and c2

в первом варианте у нас гарантированно установлен 1-ый бит, во втором же случае такой уверенности нет.

P.S.и я бы XOR заменил на OR чтобы более наглядно было видно что нужно именно установить определённый бит, а не проинвертировать.