New data packer

[Nyh]

Hi,

While preparing to release the ARJBETA sources I was inspired to write some new compression and decompression routines.

The decoder is very 68000 centered; first write the decoder in 68000 assembly then write the matching compression program.

Now I need some input...

1 At the moment I use the Calgary Compression Corpus for testing but that is not very representative for Atari programs and data. So my request is some data and programs to tweak the code.

2 While tweaking there are decisions to make, better compression and a lager decompression program or less compression and a smaler program? What about speed? Better compression usually means less speed.

This is the current status:

Code: Select all

     orig size Atari m7      m4     ni1
bib     111261    32720   40556   36758
book1   768771   293573  354523  331295
book2   610856   191953  230976  213641
geo     102400    67209   71523   74066
news    377109   135530  160683  147993
obj1     21504    10264   10922   11231
obj2    246814    78664   85488   84667
paper1   53161    17838   20046   20659
paper2   82199    28105   32933   32395
paper3   46526    17457   19686   20483
paper4   13286     5400    6025    6591
paper5   11954     4896    5439    5930
paper6   38105    12910   14358   15046
pic     513216    50788   59941   59548
progc    39611    12964   14351   14977
progl    71646    15569   17421   17627
progp    49379    10866   12018   12187
readme    2479     1217    1499    1581
sizes      689      336     454     455
sources   1177      635     824     853
trans    93695    18008   22151   20197

totaal 3255838  1006902 1181817 1128180

ni1 is the new LZ77 packer with (currently) a 64 byte depack routine. As you can see it is sometimes better as the ARJ m4 and sometimes worse. I know why but I don't know how the results will be for data used in the Atari ST scene.

Further planned developments.
1 An in place depacker: After decompression the compressed data is overwritten by the decompressed data, no extra space needed.
2 A better replacement for ARJ m7 with a larger sliding dictionary and longer match lengths.
3 A 68000 depacker very optimized for depacking speed.

With the computers of today packing for the Atari ST is easier. When I wrote ARJBETA my biggest problem was memory. One 1Mb was a lot of memory. Now we measure memory in gigabytes instead of megabytes opening up some interesting possibilities for data compression. The speed of modern computers is also a very big bonus. My current development system is a 64Gb AMD Ryzen 9 3900X running Linux.

Hans

[dml]

Welcome back :-p

[Zorro 2]

Interesting

[troed]

Data point: My two most recent packer needs have been for in-place fast depacking (upx nrv2b was the choice I made) and extremely small sizecoding compo depacker (24 bytes, but not general case). 64 byte general depacker sounds awesome.

[metalages]

Routine code size matters for boot sector or small size compos not so much for other cases.

Compression ratio is also related to the way data are prepared for better compression.
For instance : encode audio samples in delta instead of absolute amplitude, bitmaps in chunky instead of plannar...

[dsp56001]

Hello mister Nyh (The great!),

Great to see you back in business...

Here are some features i would like to see in your future Packer/Cruncher/Whatever:

1) Depacking from A0 to A0, so a small buffer is used as in Spv3 or Atomik.
2) Mode ARJ -m7 and better (if you can).
3) A lossless packing features for audio type files like FLAC (packing compression scheme) that fits Atari ST(E) sound file types.
4) Your asm depacking routine has great depacking speed even in mode ARJ -m7 could you make it better ?
5) A mode with "preset ultra" that calculates the maximum compression ratio even if it takes longer to depack since you i guess you could mix compression with small sliding dictionnary (ARJ m4) and compression with VERY BIG sliding dictionnary in a more general decrunching routine.

[dsp56001]

Here is a real case study for data packing included in this archive:

Mode LastWriteTime Length Name
---- ------------- ------ ----
d----- 05/08/2022 22:02 Mixed
-a---- 15/05/2021 22:16 8000 DATA.BIN
-a---- 15/05/2021 22:16 138390 DATA1.BIN
-a---- 15/05/2021 22:16 7082 DATA10.BIN
-a---- 15/05/2021 22:16 64456 DATA2.BIN
-a---- 15/05/2021 22:16 352 DATA3.BIN
-a---- 15/05/2021 22:16 1536 DATA4.BIN
-a---- 15/05/2021 22:16 2048 DATA5.BIN
-a---- 15/05/2021 22:16 55520 DATA6.BIN
-a---- 15/05/2021 22:16 2048 DATA7.BIN
-a---- 15/05/2021 22:16 6019 DATA8.BIN
-a---- 15/05/2021 22:16 19972 DATA9.BIN
-a---- 15/05/2021 22:16 92160 MURDERF.BIN

What are those files you might ASK ?

This is the game MURDER FRENCH version put in files that had some special features:
1) most of the files are just machine code and data.
2) One big file is just a sample in ST REPLAY format.
3) Some files are just graphics datas.

How far can we go ?

[Nyh]

1) Depacking from A0 to A0, so a small buffer is used as in Spv3 or Atomik.
2) Mode ARJ -m7 and better (if you can).
3) A lossless packing features for audio type files like FLAC (packing compression scheme) that fits Atari ST(E) sound file types.
4) Your asm depacking routine has great depacking speed even in mode ARJ -m7 could you make it better ?
5) A mode with "preset ultra" that calculates the maximum compression ratio even if it takes longer to depack since you i guess you could mix compression with small sliding dictionnary (ARJ m4) and compression with VERY BIG sliding dictionnary in a more general decrunching routine.

1 A0 to A0 depacking will come with no extra space needed
2 I am planning to improve on m7, but that will mean a rewrite of the sliding dictionary core code
3 features for audio packing have to be done by special filters to prepare the data for compression
4 the unarj routines use faster versions of the published depacker, loop unrolling and bigger tables will give you extra speed. I am planning a special high speed version for the lz77 depacker (using the same compression engine but a different file format).
5 ultra good packing can be achieved by using a range coder on the data, I think that is too slow. I will stick to lz77 coding and a huffman entropy encoding. Using a huge dictionary is planned but needs a rewrite of the sliding dictionary code.

Hans

[metalages]

About audio samples i have saved nearly 10% in arj 4 just by encoding them in delta instead of pulse. It saves even more in m7 from what I see. Lossless and very fast.
As you say data preparation for better compression is not generic and should be previously done into the data format by the application ( not the packer )
Reason why i also gave the example of chunky versus planar for bitmaps.

My special request : can you deliver a C version of the routine for pc in the same time ? it would avoid me to do this kind of ugly stuff
https://github.com/jhubrt/demOS/blob/ma ... N/ARJDEP.C

About range coder, probably too slow indeed. Aren"t they under license too ?

[Nyh]

Maybe slightly off topic... but what is a good Atari Emulator for using Pure C under windows 10 64 bit?
I was always very happy with STeem SSE debug build, I liked the boiler room very much.
But Steem.SSE.4.1.2.Win64.D3D doesn't even want to boot in monochrome mode crashing with System exception $C0000005 at $..... in ntdll.dll
I want to test the new code on the Atari ST (emulator) but for now I am stuck.

Hans

[metalages]

I am under w10 64b.
On my side I assemble .S files individually with devpack 3 invoking it directly from Visual Studio Community using Hatari (use intermediate executable to inject TTP command line parameters from a file).
To compile / link with Pure C I use Steem 3.2 debug.

[Nyh]

Source code release:
https://github.com/HansWessels/gup
The sources are in GUP, long time ago we thought we could make the GNU Universal Packer

To build under Linux
./configure
make

the executable can be found at:
unix/gup

to create and archive:
gup a -m7 test.arj <files to pack>
to test the archive:
gup t test.arj
to list the contents:
gup l test.arj

gup can create ARJ m1-m4 and m7 archives, LZH and LHA multiple modi and the new Ni packer formats.
At the moment only n0 is implemented:
gup a -n0 test.arj <files to pack>
All Ni packer files will be hosted in arj archives with packing modes starting at 0x10.
There is an not completely yet working dump mode that will dump binary, c or assembly code files.
gup a test.bindump <files to pack> wil create a binary dump file.
gup a test.asmdump <files to pack> will create an assembly dump file.
gup a test.cdump <files to pack> will create a c dump file.
In the directory ni_packer are the memory to memory depackers of m1-m7 files and the n0 files with a CRC check routine and a small and simple program to test the code.
The ni packer n0 mode is work in progress. There are still some bugs in the code. Things may change.

To compile on windows... may the force be with you... I think you stand a change with cygwin and compile the unix version, the win32 code is not up to date anymore.

It may or may not compile under Pure C on the Atari ST, arjbeta is the directory to start.

Hans

[Nyh]

Oh, you want the master branch, not the main... I will try to fix that issue later

[Nyh]

My special request : can you deliver a C version of the routine for pc in the same time ? it would avoid me to do this kind of ugly stuff
https://github.com/jhubrt/demOS/blob/ma ... N/ARJDEP.C

See https://github.com/HansWessels/gup/tree ... /ni_packer. C versions of arj m4, arj m7 and Ni n0 reside there.

Hans

[metalages]

My special request : can you deliver a C version of the routine for pc in the same time ? it would avoid me to do this kind of ugly stuff
https://github.com/jhubrt/demOS/blob/ma ... N/ARJDEP.C

See https://github.com/HansWessels/gup/tree ... /ni_packer. C versions of arj m4, arj m7 and Ni n0 reside there.

Hans

Excellent
Thanks

[Nyh]

First results are in:
The Ni n0 packer is small and fast.
The new n0 depacker has an excellent depacking speed, outperforming m7 and m4 by a big margin: m7=40.855 s m4=48.498 s and n0=31.310s. The compression ratio is somewhere between the m4 packer and de m7 packer, for some files even worse as the m4 packer. The size of the n0 depacker is very small: only 64 bytes.

I just synced the code to my github account.

Code: Select all

     orig size        m7    time      m4    time  n0       time
bib      111261    32720   1,320   40556   1,640   36755   1,045
book1    768771   293573  10,950  354523  14,440  331292   8,785
book2    610856   191953   7,730  230976   9,660  213639   6,225
geo      102400    67209   2,410   71523   2,535   74063   1,400
news     377109   135530   5,260  160683   6,270  148047   3,895
obj1      21504    10264   0,405   10922   0,340   11247   0,215
obj2     246814    78664   3,150   85488   3,315   84707   2,260
paper1    53161    17838   0,735   20046   0,823   20656   0,550
paper2    82199    28105   1,150   32933   1,370   32392   0,880
paper3    46526    17457   0,710   19686   0,800   20480   0,525
paper4    13286     5400   0,230    6025   0,230    6588   0,155
paper5    11954     4896   0,210    5439   0,205    5927   0,135
paper6    38105    12910   0,555   14358   0,585   15043   0,395
pic      513216    50788   3,225   59941   3,285   61044   2,715
progc     39611    12964   0,560   14351   0,585   14974   0,400
progl     71646    15569   0,735   17421   0,800   17642   0,590
progp     49379    10866   0,525   12018   0,545   12245   0,405
readme     2479     1217   0,070    1499   0,045    1578   0,030
sizes       689      336   0,030     454   0,015     452   0,005
sources    1177      635   0,040     824   0,025     850   0,010
trans     93695    18008   0,885   22151   0,985   20281   0,690
                     
totaal   3255838 1006902  40,885 1181817  48,498 1129902  31,310

[Nyh]

Ok, I'll admit, I am a not so great coder, the n0 depacker was two bytes too big. Now its size is 62 bytes, I just reshuffled the code. Can anyone make it even smaller?

Code: Select all

;
; ni packer n0 decoder, size optimized
; 2022 Hans Wessels

;void decode_n0(uint8_t *dst, uint8_t *data)
; registers
; D0 = 
; D1 = bitbuffer
;
; A0 = dst
; A1 = src
; A2 = copy pointer
; alternatief pointer 8 of 16 bit, min match = 3

export decode_n0

decode_n0:
	move.l	A2,-(SP)			; save A2
	moveq		#-128,D1			; bit buffer sentry
.lit:
	move.b	(A1)+,(A0)+		; copy
.loop:
	bsr.s		.get_bit			; is het een pointer len of een literal?
	bcc.s		.lit				; pointer
.ptr_len:
	moveq    #-1,D0			; init offset
	move.b	(A1)+,D0			; 1e 8 bits
	bsr.s		.get_bit			; 8 of 16 bit offset
	bcc.s		.8bit				; 8 bit pointer
	lsl.w    #8,D0				; schuif bits
	beq.s		.done  			; klaar!
	not.w    d0             ; negatief maken
	move.b	(A1)+,D0			; 2e 8 bits
.8bit:	
	lea		0(D0.l,A0),A2	; pointer offset
	moveq		#1,D0				; init waarde
.next_bit:
	bsr.s		.get_bit			; get value bit in x register
	addx.w	D0,D0				; verdubbel en tel waarde van bit op bij D0
	bsr.s		.get_bit			; nog een bit?
	bcs.s		.next_bit		; yep
.copy_loop:
	move.b	(A2)+,(A0)+		; copy
	dbra		D0,.copy_loop
	bra.s    .loop
.get_bit:						; zet bit in x-bit status register
	add.b		D1,D1				; schuif bit naar buiten
	bne.s		.get_bit_done	; klaar
	move.b	(A1)+,D1			; nieuwe bits
	addx.b	D1,D1				; bit naar buiten, sentry naar binnen
.get_bit_done:
	rts
.done:
	move.l	(SP)+,A2			; restore A2
	rts

Hans

[Anima]

1 At the moment I use the Calgary Compression Corpus for testing but that is not very representative for Atari programs and data. So my request is some data and programs to tweak the code.

Have you considered taking MAME (program) ROM files for testing? I.e. from CPS games like Final Fight, Ghouls'N'Ghosts, etc.? The program data is mostly 512 kB up to 4 MB in size so this could be a good measure.

[ThorstenOtto]

Ares you sure that this

Code: Select all

	move.b	(A1)+,D1			; nieuwe bits
	addx.b	D1,D1				; bit naar buiten, sentry naar binnen

works as intended? The move will clear the carry flag, so addx will do the same as a simple add.

[Nyh]

Ares you sure that this

Code: Select all

	move.b	(A1)+,D1			; nieuwe bits
	addx.b	D1,D1				; bit naar buiten, sentry naar binnen

works as intended? The move will clear the carry flag, so addx will do the same as a simple add.

The move will not clear the carry flag. It sure works as intended.

Hans

[Nyh]

Have you considered taking MAME (program) ROM files for testing? I.e. from CPS games like Final Fight, Ghouls'N'Ghosts, etc.? The program data is mostly 512 kB up to 4 MB in size so this could be a good measure.

Good idea, thank you!

Hans

[ThorstenOtto]

The move will not clear the carry flag. It sure works as intended.

According to the manual, it does:

Screenshot_20221016_064908.png

Maybe your algorithm works nevertheless, but then you can save a few cycles by using add instead of addx

[metalages]

Not affected means it keep the value set before the move ? (It is not reset)
Addx effect will depend on what had been done before the move.

[Nyh]

According to the manual, it does:
Maybe your algorithm works nevertheless, but then you can save a few cycles by using add instead of addx

Sorry, I should have been more precise. The move doesn't change the x-flag which the addx.w uses. add.w and addx.w both use 4 clock cycles. If you don't believe me... the sources are all there, change the addx.w to an add.w and find out what happens.

Hans

[ThorstenOtto]

Oops, right. I always forget that addx etc. use the X-flag, not the C-flag.