X86 ASM Programmer requested for compression algorithm

[SoraK05]

Hello :)
I have been writing a general outline to a compression algorithm to work on files in the data stream of 0/1 bits, and it is generally 90% and can have a general minor tweak included.
Otherwise, it is not in a structure resembling computer pseudocode steps. It is a general outline and details.

The reason I am looking for an assembly programmer is that I am not familiar with asm (or a lot of c++ otherwise) and it works on looking to search a file for its bits to have variable bits detected rather than bytes which is a generally slower restriction using higher level languages, as well as allow for the most step-by-step precision considering it is to scan the file quite thoroughly and often to build up the required data, as well as be able to decode faster and to the variable bit precision.
For something to bit precision and requiring multiple scans, it would be ideal to use the shortest steps with asm for this as the strongest method will require some constrained minimal brute forcing type processing.


From expectations on general data (as well as a personally hand crafted BMP to use for general expectation) and comparisons to other tools, it looks to do things quite thoroughly and a lot more than common tools such as 7z/rar.


If someone is interested in looking at it, and I can also include the final tweaks, I would appreciate an x86 ASM tool, as well as a general algorithm :)

[Gunther]

Hi SoraK05,

I'm not sure what you're searching. We've some funny, bad experiences with super compression algorithms. I hope you're serious.

If you want to learn assembly language, download the MASM32 package and go forward. If you're searching a programmer, try it with Rent a Coder.

Gunther

[SoraK05]

I'm looking to contribute toward a more effective compression tool which ground up is programmed using less steps with asm.

7z/rar and other codecs in general are not very effective and compromise time/space.

I have a basic BMP example in a 7z with the outline where it is few colours with mostly repetition and should be able to fit into very few bytes yet PNG/RAR/7z result in sizes of KBs.

Compression in general in the spectrum involves repetition which can be captured where one version and its representations will be less space overall and that a program can restore it.
In general, in the data stream, 50% is 'compressible' and 50% is 'uncompressible' <generally resembling the coded results>, and the process can be implied as a conversion <where processing is rejected if the file size is determined to increase>.
Where repetition according to parameters is found there can be compression - this is in the 0/1 bit spectrum, and does not favour text/audio/image and so on.


Besides one general prepping process which can be considered, this is a more thorough attempt at finding repetition than the general loose approach of 7z/RAR and many other codecs, with asm to assist in speed.
Decoding should be very quick, with asm also, as once the file is constructed it is decoded with a code tree with prefixes which is straightforward.


I am looking at the notion of asm, yet first I would prefer looking at hardware and paths, opcode reasoning and so forth to be more flexible.
I am willing to discuss, and share the writeup with any interested asm programmers.

[jj2007]

Hi,

Before investing heavily into a new algo, check if it has not been invented already. The bitstream thing you describe, for example, resembles strongly the Huffman coding process.

Check also if the final product will be able to compete with FreeArc.

And welcome to the forum :icon14:

[SoraK05]

Hello, and thank you :)
The closest thing as far as I know is DEFLATE and from what I read up about the way DEFLATE operates this should produce smaller files.
It does take use a variable code tree, however it is not 'huffman' per se. :)

From the math involved, besides moving data in advance there isn't necessarily a lot more room to compress, and should be lower than many <including FreeArc>..
I can see in the FreeArc writeup how there are algorithms to work with text, exes, and multiple algorithms.

This should work on any file in general without being particular to it being an executable, image etc and have low results.
It is a standard algorithm that can be left automated for data, which can be adjusted to skimp a little.

EDIT:
Read the 100 to 1 Compressor :) I get that it is not possible in the data stream :)
I can also mention that I get an algorithm is ideal direct on lossless data rather than after being processed with some kind of algorithm.
The BMP mentioned with few colours and a lot of repetition can compress to few KBs with 7z/RAR/PNG and much more with JPG for example, and is the same data that can end up being few B.

It may be considered intensive and require temporary storage, however with asm and time, the result should be compacted and accessible (including any offset within providing some advance calculation to directly access, like data for multiple file offsets on a calculation run).

[jj2007]

DEFLATE = LZW + Huffman

Check MaxComp for competitors; sort by efficiency to get an idea what are the traps (some algos have good compression but take DAYS, not hours).

Why don't you code your algo in plain C and post the exe here? We are good at translating slow C/C++ loops into fast assembler loops.

[SoraK05]

I have the overview already done for the most part.
Any programmer that is willing to transform it to what the computer can do, and more directly to asm is appreciated :)

It should generally provide the main details and algorithm function.
I'm not very fluent in computer language, with some basic c++ skills.

I am sure, and the writeup may demonstrate, this can have some low results with a focus on thorough scans.

[jj2007]

I'm not very fluent in computer language, with some basic c++ skills.

Both BASIC and C++ are fine, but post it. Even pseudocode will be gladly accepted ;-)

[nidud]

deleted

[SoraK05]

OK here.
The notion is for being thorough. There could be a tweak / optimization, which is welcome.

It will generally bracket specific locations which are more compressible, look for strings (including mirror/inverse) within those bracket areas to be more specific for distribution as well as distinguish compressible/uncompressible areas, patterns of strings and in a row which can be repeated to layer+encapsulate where applicable, so a file can have compressed+layered+raw (separated with 'gap length info' to distinguish) using prefixes.
Layered data prefixes when met will require to decode in temp space and then be appended for example.

The notion is also to do a constrained scan to determine the minimal number of strings for the code tree as well as the most effective, described as 'heaviest string'. This means any variable length pattern which covers the most and also considers size for the code tree (rather than a cheaper byte pattern + frequency e.g.).

A temporary file for offset mapping is used to construct the final file from its data.

[dedndave]

sounds somewhat similar to something i worked on years ago - in 16-bit code days
i used several compression methods, and scanned regions to see which method provided the best compression
i didn't move sections around, however - your method is different in that respect

it seemed like a sound idea
but, scanning regions and estimating compression ratios for several methods proved very slow
de-compression, on the other hand, was very fast

at that point, it's a matter of "compression philosophy", which is slowly changing
people are beginning to realize that it isn't about disk space (as it used to be), but more about bandwidth
why is that different ?
well - because the time it takes to achieve better compression might be worth it
it may take a while to compress a file, but you only have to do it once
then, it gets sent over the internet several times (or several thousand) and de-compressed

but, until you can convince users that slow compression is ok, you might be spinning your wheels   :(
and, you have to provide more than 2 or 3 percent improvement in compression ratio

[nidud]

deleted

[SoraK05]

It doesn't move sections around.

It has 4 basic algorithms which run in sequence providing there is compression acknowledged:

1) Scan file for specific patterns to develop offset brackets of compressible areas, and use the heaviest of the filtered results
2) Scan for heaviest strings in each offset bracketed area to be specific to the file for distribution (by adjusting the code tree to suit the different areas than have a code tree for the data as a whole), as well as account for compressible/uncompressible areas (and this can include mirror/inverse for less entries overall after 3+4)
3) Scan for heaviest patterns of strings which are in code tree and offset bracketed areas (skipping raw) <i.e. in the temporary offset mapping file>
4) Scan for in a row <in the temporary offset mapping file>

I figure 'MODE 1' is 1+2 which will initially build the code tree and offsets to place them, and 'MODE 2' is 3+4 which will shrink data further and can be repeated to layer/encapsulate.

Decoding should be fast.

Considering it would be asm step-by-step for each part, it shouldn't be unreasonably long and the result is accessible and compact. I would opt to use something like this for video, assets in a game, archival data from it not being too long to encode where space is available (and is using least steps with asm) as well as decode quick (using asm).
I wouldn't generally use other archival tools beyond something to archive for immediate purposes, and this can also be adjusted for such a purpose and be much smaller than 7z/rar which is general purpose.


As for compression ratio, this is going for a 'thorough' approach, and wouldn't necessarily get much smaller using a string scanning method beyond moving data in advance to prep for MODE 1 which is an algorithm by itself.
Using asm is to use least steps for the speed.

[SoraK05]

I have written a shortcut to do something similar to above and should still end up compressing quite low as well as take far less time than the constrained brute forcing of MODE 1 for areas + strings.

If anyone is interested I can write the description of an alternative MODE 1 to save a lot more time and still compress quite low (however not as accurately). MODE 2 in principle for duplicate combinations of patterns and in a row (as a number) remains.


EDIT:
This alternative should (still) be lower than 7z/rar and be done in decent time. :)

[SoraK05]

Sorry for the triple post. Perhaps a mod can join posts :)

This is just to mention that I generally have a complete writeup done.
The idea behind this is to have a powerful and comprehensive compression tool that in its highest mode can just about squeeze what is available in a file.

I have all adjustments and tweaks to be able to change aspects of the algorithm for space/time.
All adjustments from fastest and weakest to slowest and highly compressed can be done for aspects of the algorithm, where all knobs can be adjusted to suit one's preference and with general details for what is going on and expected speed etc.


The idea is to have this tool also be able to work on multiple files appended and create offset data for each file for immediate decryption, and be able to schedule multiple files (whether together or as individual files).
When scheduled, one more separate tool is to be done which can allow for a bootable device like a usb to be able to boot when the pc starts and automatically perform the scheduled operation in a barebone environment without any video/sound/keyboard calculated and it is just doing this process. The point of this cold boot process is to be able to allow for more to the most thorough scheme to work in a direct environment with shortest asm steps.
When the process is done the PC can automatically shut down to imply completion.

Lossless audio and video can be very quickly decoded and with some minimal data to have for precalculated info for seconds for jumping to offsets.
It is like a one-off powerful tool with adjustment knobs which in general should be quick enough even in a Windows environment on some settings to be much smaller than 7z/rar and also be done in very decent time. There is also a very cheap method for quick encoding which is more ideal for a direct decoding.

The idea is a versatile tool which can perform quick with minimal asm steps to be used in general as a compression tool with quick decoding and also have more compact/thorough options that can do video/audio/asset data in a barebone boot environment, and also for more compact archival data.

The idea is that in general this compression tool can cater with its knob adjustments for expectations of compression and space/time, giving opportunity for a barebone processing possibility scheduled on a bootable device.


My only thing is I have minimal programming language knowledge. I have basic knowledge for accessing bits, general loops and functions etc in c++.

If anyone is interested with skills to be able to write some few generally short and basic algorithms which can be adjusted/tweaked for its knobs for a versatile and comprehensive compression tool written in minimal asm steps and with a scheduled bootable and direct processing feature, I can assist with a description and writeup.