askeksa / shrinkler Goto Github PK

Cruncher for Amiga executables

License: Other

C++ 80.90% C 4.01% Assembly 13.38% Makefile 1.70%

shrinkler's Introduction

Shrinkler executable file compressor for Amiga by Blueberry

Designed for maximum compression of Amiga 64k and 4k intros, and
everything in between.

Executables for different platforms are available in their respective
subdirectories. The output executables are compatible with all Amiga CPUs
and kickstarts.

Run with no arguments for a list of options. For the options controlling
compression efficiency, higher values generally result in better
compression, at the cost of higher time and/or memory requirements.

Data decompression source code for 68000 is included. A version for Z80 is
here: http://www.cpcwiki.eu/forum/programming/shrinkler-z80-decrunch-routine
A version for 6502 is here: https://github.com/atari8xxl/unShrinkler


History:

2022-02-22:  Version 4.7. Faster and with new features:
             Now built with Amiga-GCC. 15% faster and no longer needs ixemul.
             Option to disable parity context, for use with 8-bit data.
             Option to support commandline arguments. Works with all headers.
             Data sizes are no longer rounded up to a multiple of 4 bytes.
             Option to write header in front of data file with sizes and flags.
             Utility code to load and decompress a data file with header.
             Upped default compression preset to -3.

2020-02-22:  Version 4.6. Better support for large files:
             Faster suffix array construction (the pause before each hunk).
             Fixed verify error when compressed size is above roughly 2MB.
             Increased max number of reference edges to 100000000.
             Support HUNK_RELOC32SHORT and HUNK_DREL32 relocation hunks.
             Fixed broken output formatting when the first hunk is skipped.
             Included link to Z80 decompressor in README.

2018-01-03:  Version 4.5. Fixes and convenience features:
             Crunched programs no longer depend on undocumented A3 contents.
             This fixes programs with icon crashing when run from Workbench.
             Quick -1, ..., -9 options for compression presets.
             Option to process hunks of executable without crunching.
             Support empty hunks (padded to 4 bytes).
             Print minimum safety margin for overlapped data decrunching.

2015-01-18:  Version 4.4. Optimizations galore:
             New match finder based on a suffix array.
             New reference edge map based on a cuckoo hash table.
             Pre-compute number encoding sizes for faster estimation.
             Recycle references edges to save alloc/dealloc overhead.
             Updated defaults to take advantage of speed increase.
             Data file compression mode with decompression source.
             Fixed broken progress output for big files.
             Do not crash if text file could not be opened.

2015-01-05:  Version 4.3. Minor fixes:
             Usage information adjusted to fit within 77 columns.
             References discarded metric computed properly.
             First progress step is at 0.1% rather than 1.0%.
             Option to omit progress output (for non-ANSI consoles).
             Source changes for easier compilation with MSVC.

2014-12-16:  Version 4.2. For memory-efficient decrunching:
             Option to overlap compressed and decompressed data.
             Print memory overhead during and after decrunching.
             Verifier accepts partially filled hunks.

2014-02-08:  Version 4.1. Bug fixes and new features:
             Fixed some bugs in the range coder.
             Fixed handling of very small first hunk.
             Added internal verifier to check correctness of output.
             Print helpful text when encountering an internal error.
             Better error message when running out of memory.
             Set output file to be executable.
             New options to print text from an argument or file.
             New option to flash a hardware register during decrunching.

2014-01-05:  Version 4.0. First public release with new name.

1999 - 2012: Various public and internal versions.


Source code available from https://github.com/askeksa/Shrinkler


For questions and comments, visit the ADA forum at

http://ada.untergrund.net/?p=boardthread&id=264

or the Pouet forum at

http://www.pouet.net/prod.php?which=64851

or write to blueberry at loonies dot dk.

shrinkler's People

Contributors

Stargazers

Watchers

Forkers

b0nefish jeffv03 bartmanabyss unforeseenocean pfusik remy-luisant kieranhj michaeljtroughton icodein happy-ferret-entertainment rasky brushesm

shrinkler's Issues

Bytestream decoder?

Would it be possible to add an option to Shrinkler to avoid having to fetch one bit at a time during decoding? I'm working on a port to a MIPS platform where bit management in general isn't very fast. In particular this hot loop:

    while (ctx->intervalsize < 0x8000) {
        ctx->intervalsize <<= 1;
        ctx->intervalvalue = (ctx->intervalvalue << 1) | shr_get_bit(ctx);
    }

in the range decoder seems to take lot of time. If it was possible to instead fetch one byte at a time, that would be great.

Simple Encoder and Decoder in C

Hi,

Shrinkler is an excellent compression algorithm with potential applications outside of the demoscene. Would you consider publishing a plain C version of the encoder and decoder for those unfamiliar with C++?

Since it would require a lot of work to translate the encoder, even just a decoder in C would be great for writing depackers targeting architectures other than the Z80 and 68K.

Windows compilation error

There's a compilation error:

C:\0\src\Shrinkler>make PLATFORM=windows-64
x86_64-w64-mingw32-g++ -Wall -Wno-sign-compare -O3 -I decrunchers_bin cruncher/Shrinkler.cpp -c -o build/windows-64/Shrinkler.o
In file included from cruncher/HunkFile.h:24,
				 from cruncher/Shrinkler.cpp:22:
cruncher/HunkFile.h: In member function 'bool HunkFile::analyze()':
cruncher/doshunks.h:65:27: error: narrowing conversion of '-2147483648' from 'long int' to 'unsigned int' [-Wnarrowing]
   65 | #define HUNKF_FAST (1L<<31)
	  |                           ^
cruncher/HunkFile.h:380:9: note: in expansion of macro 'HUNKF_FAST'
  380 |    case HUNKF_FAST:
	  |         ^~~~~~~~~~

C:\0\src\Shrinkler>x86_64-w64-mingw32-g++ --version
x86_64-w64-mingw32-g++ (Rev6, Built by MSYS2 project) 10.2.0
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

An easy fix works for me:

C:\0\src\Shrinkler>git diff
diff --git a/cruncher/doshunks.h b/cruncher/doshunks.h
index 190239e..ea4b440 100644
--- a/cruncher/doshunks.h
+++ b/cruncher/doshunks.h
@@ -62,7 +62,7 @@
 #define HUNKB_FAST     31
 #define HUNKF_ADVISORY (1L<<29)
 #define HUNKF_CHIP     (1L<<30)
-#define HUNKF_FAST     (1L<<31)
+#define HUNKF_FAST     (1u<<31)

Out of bounds memory use in make_suffix_array

Found using Valgrind, while trying to debug an unrelated issue:

Original  After 1st pass  After 2nd pass
==1533662== Invalid read of size 1
==1533662==    at 0x1158B0: MatchFinder::make_suffix_array() (MatchFinder.h:85)
==1533662==    by 0x10F11A: MatchFinder::MatchFinder(unsigned char*, int, int, int, int) (MatchFinder.h:128)
==1533662==    by 0x10C90C: packData(unsigned char*, int, int, PackParams*, Coder*, RefEdgeFactory*, bool) (Pack.h:79)
==1533662==    by 0x126B68: DataFile::compress(PackParams*, RefEdgeFactory*, bool) (DataFile.h:44)
==1533662==    by 0x1111E0: DataFile::crunch(PackParams*, RefEdgeFactory*, bool) (DataFile.h:118)
==1533662==    by 0x10DE90: main2(int, char const**) (Shrinkler.cpp:308)
==1533662==    by 0x10EAC1: main (Shrinkler.cpp:411)
==1533662==  Address 0x4edbbc0 is 0 bytes after a block of size 1,001,296 alloc'd
==1533662==    at 0x483EF3F: operator new(unsigned long) (vg_replace_malloc.c:417)
==1533662==    by 0x126796: __gnu_cxx::new_allocator<unsigned char>::allocate(unsigned long, void const*) (new_allocator.h:121)
==1533662==    by 0x126730: std::allocator_traits<std::allocator<unsigned char> >::allocate(std::allocator<unsigned char>&, unsigned long) (alloc_traits.h:460)
==1533662==    by 0x12633F: std::_Vector_base<unsigned char, std::allocator<unsigned char> >::_M_allocate(unsigned long) (stl_vector.h:346)
==1533662==    by 0x125FC3: std::vector<unsigned char, std::allocator<unsigned char> >::_M_default_append(unsigned long) (vector.tcc:635)
==1533662==    by 0x125E45: std::vector<unsigned char, std::allocator<unsigned char> >::resize(unsigned long) (stl_vector.h:940)
==1533662==    by 0x1110CF: DataFile::load(char const*) (DataFile.h:89)
==1533662==    by 0x10DE39: main2(int, char const**) (Shrinkler.cpp:304)
==1533662==    by 0x10EAC1: main (Shrinkler.cpp:411)
==1533662== 
==1533662== Invalid read of size 1
==1533662==    at 0x1158C0: MatchFinder::make_suffix_array() (MatchFinder.h:85)
==1533662==    by 0x10F11A: MatchFinder::MatchFinder(unsigned char*, int, int, int, int) (MatchFinder.h:128)
==1533662==    by 0x10C90C: packData(unsigned char*, int, int, PackParams*, Coder*, RefEdgeFactory*, bool) (Pack.h:79)
==1533662==    by 0x126B68: DataFile::compress(PackParams*, RefEdgeFactory*, bool) (DataFile.h:44)
==1533662==    by 0x1111E0: DataFile::crunch(PackParams*, RefEdgeFactory*, bool) (DataFile.h:118)
==1533662==    by 0x10DE90: main2(int, char const**) (Shrinkler.cpp:308)
==1533662==    by 0x10EAC1: main (Shrinkler.cpp:411)
==1533662==  Address 0x4edbbd7 is 23 bytes after a block of size 1,001,296 alloc'd
==1533662==    at 0x483EF3F: operator new(unsigned long) (vg_replace_malloc.c:417)
==1533662==    by 0x126796: __gnu_cxx::new_allocator<unsigned char>::allocate(unsigned long, void const*) (new_allocator.h:121)
==1533662==    by 0x126730: std::allocator_traits<std::allocator<unsigned char> >::allocate(std::allocator<unsigned char>&, unsigned long) (alloc_traits.h:460)
==1533662==    by 0x12633F: std::_Vector_base<unsigned char, std::allocator<unsigned char> >::_M_allocate(unsigned long) (stl_vector.h:346)
==1533662==    by 0x125FC3: std::vector<unsigned char, std::allocator<unsigned char> >::_M_default_append(unsigned long) (vector.tcc:635)
==1533662==    by 0x125E45: std::vector<unsigned char, std::allocator<unsigned char> >::resize(unsigned long) (stl_vector.h:940)
==1533662==    by 0x1110CF: DataFile::load(char const*) (DataFile.h:89)
==1533662==    by 0x10DE39: main2(int, char const**) (Shrinkler.cpp:304)
==1533662==    by 0x10EAC1: main (Shrinkler.cpp:411)
==1533662==

This happens pretty much with any input. The input in question was the Shrinkler executable file itself, using -d.

Note that this is not a simple off-by-one, there is a read several bytes further than intended.

Header for compressed data files.

When compressing files in --data mode the compressed file has no header.
It would be useful to have the possibility to add a small header, e.g. 4-byte ID + uncompressed size + compressed size.

g++ 9.3 warnings

g++ -Wall -Wno-sign-compare -O3 -I decrunchers_bin cruncher/Shrinkler.cpp -c -o build/native/Shrinkler.o
In file included from cruncher/Shrinkler.cpp:22:
cruncher/HunkFile.h: In member function 'HunkFile* HunkFile::crunch(PackParams*, bool, bool, std::string*, unsigned int, RefEdgeFactory*, bool)':
cruncher/HunkFile.h:874:44: warning: 'void* memset(void*, int, size_t)' clearing an object of non-trivial type '__gnu_cxx::__alloc_traits<std::allocator<Longword>, Longword>::value_type' {aka 'class Longword'}; use assignment or value-initialization instead [-Wclass-memaccess]
  874 |     memset(&ef->data[dpos], 0, header1_size);
      |                                            ^
In file included from cruncher/HunkFile.h:25,
                 from cruncher/Shrinkler.cpp:22:
cruncher/AmigaWords.h:44:7: note: '__gnu_cxx::__alloc_traits<std::allocator<Longword>, Longword>::value_type' {aka 'class Longword'} declared here
   44 | class Longword {
      |       ^~~~~~~~
In file included from cruncher/Shrinkler.cpp:22:
cruncher/HunkFile.h:923:49: warning: 'void* memset(void*, int, size_t)' clearing an object of non-trivial type '__gnu_cxx::__alloc_traits<std::allocator<Longword>, Longword>::value_type' {aka 'class Longword'}; use assignment or value-initialization instead [-Wclass-memaccess]
  923 |     memset(&ef->data[dpos], 0, rounded_text_size);
      |                                                 ^
In file included from cruncher/HunkFile.h:25,
                 from cruncher/Shrinkler.cpp:22:
cruncher/AmigaWords.h:44:7: note: '__gnu_cxx::__alloc_traits<std::allocator<Longword>, Longword>::value_type' {aka 'class Longword'} declared here
   44 | class Longword {
      |       ^~~~~~~~
g++ -s  build/native/Shrinkler.o  -o build/native/Shrinkler

askeksa / shrinkler Goto Github PK

shrinkler's Introduction

shrinkler's People

Contributors

Stargazers

Watchers

Forkers

shrinkler's Issues

Bytestream decoder?

Simple Encoder and Decoder in C

Windows compilation error

Out of bounds memory use in make_suffix_array

Header for compressed data files.

g++ 9.3 warnings

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent