Compression algorithm c#

[fredreload]

So I wrote the compression test based on the math I presented in the Mathmatics section. It successfully reduces the size of the image by half with only 1 iteration. C1 and c2 takes around 1889+ bytes, you are free to test it on any files. I'll work on the decompression some other time

 

static byte IteratedBitcount(ulong n)

{

ulong test = n;

int count = 0;

while (test != 0)

{

if ((test & 1) == 1)

{

count++;

}

test >>= 1;

}

return Convert.ToByte(count);

}

 

protected void compress_test()

{

byte[] bytes = System.IO.File.ReadAllBytes(@"C:\Python2712\Scripts\compression_test\Result.jpg");

ulong[] array = new ulong[(bytes.Length / 16)+(bytes.Length % 16)];

byte[] c1 = new byte[(bytes.Length / 16) + (bytes.Length % 16)];

byte[] c2 = new byte[(bytes.Length / 16) + (bytes.Length % 16)];

bool[] gtlt = new bool[(bytes.Length / 16) + (bytes.Length % 16)];

byte[] array16 = new byte[16];

for( int i=0; i< bytes.Length; i=i+16)

{

for (int j = 0; j <16; j++)

{

if (i + j >= bytes.Length)

{

array16[j] = 0;

}

else

{

array16[j] = bytes[i + j];

}

}

//15~8

ulong val1 = BitConverter.ToUInt64(array16, 8);

//7~0

ulong val2 = BitConverter.ToUInt64(array16, 0);

ulong diff;

if (array16[15] > array16[7])

{

diff = val1 - val2;

gtlt[i/16] = true;

array[i/16] = diff;

/*

byte[] bytess = new byte[8];

bytes[0] = (byte)(diff >> 56);

bytes[1] = (byte)(diff >> 48);

bytes[2] = (byte)(diff >> 40);

bytes[3] = (byte)(diff >> 32);

bytes[4] = (byte)(diff >> 24);

bytes[5] = (byte)(diff >> 16);

bytes[6] = (byte)(diff >> 8);

bytes[7] = (byte)diff;

*/

}

else

{

diff = val2 - val1;

gtlt[i/16] = false;

array[i/16] = diff;

/*

byte[] bytess = new byte[8];

bytes[0] = (byte)(diff >> 56);

bytes[1] = (byte)(diff >> 48);

bytes[2] = (byte)(diff >> 40);

bytes[3] = (byte)(diff >> 32);

bytes[4] = (byte)(diff >> 24);

bytes[5] = (byte)(diff >> 16);

bytes[6] = (byte)(diff >> 8);

bytes[7] = (byte)diff;

*/

}

c1[i / 16] = IteratedBitcount(val1);

c2[i / 16] = IteratedBitcount(val2);

}

}

Edited August 29, 2016 by fredreload

[Sensei]

You need to have either compressing routine as well as decompressing routine,

then run them on large amount (say few hundred thousands) of files on your disk,

and compare whether compressed then decompressed data equals to original data prior compression (yet another routine which you must make and check whether it works correctly),

to be sure compression algorithm is not introducing some errors.

 

Since you didn't provide decompressing routine, we can't check it in practice.

But at the first sight, it looks to me as some kind of hash function, rather than compression algorithm.

 

ps. Aligning to 16 bytes buffer size you can do using

((bytes.Length+15)/ 16)

instead of

(bytes.Length / 16) + (bytes.Length % 16)

Edited August 29, 2016 by Sensei

[fredreload]

Hmm, right I wanted to work on the decompressing routine but something came up, I'll try and get it to work tomorrow then you guys can check my work

 

P.S. Thanks for the response btw Sensei

Edited August 29, 2016 by fredreload

[Sensei]

Lossless compression algorithm must have just one output from given input uncompressed data.

And have just one output from given input compressed data.

If compressed data (or hash value) will have more outputs than 1, algorithm won't be able to tell which one to use.

 

It's very similar situation as with

Bijection, Injection, and Surjection

https://en.wikipedia.org/wiki/Bijection

https://en.wikipedia.org/wiki/Injective_function

https://en.wikipedia.org/wiki/Surjective_function

 

OTOH, it allows making even more efficient compression algorithms.

Say we calculate hash from some input data.

And there is finite amount of hash values, corresponding to some uncompressed data.

After introducing index which output is right in table of the all outputs possible to make from some input data,

algorithm will allow to have exactly one the right output.

 

Lame example of this is keeping index to prime number, starting from 2,3,5,7,11,13,..... (with indexes 0,1,2,3,4,5)

after a while as we progress, index to prime, will have less bits needed than prime number (thus compression of data)..

[fredreload]

I'm having a huge binary permutation, the safest bet is stick with 16 bits. Well I need a way to generate all the binary permutations, for instance, a 4 bits binary with 2 one bits would be 0011,0101,0110,1001, etc. If you have working code it would be cool, else I'll try to Google more tomorrow

 

P.S. Ya there are multiple possible answer for this algorithm = =, it failed, I guess I'll have to try other methods

Edited August 29, 2016 by fredreload

[John Cuthber]

Is it just me or does this

... I'll work on the decompression some other time...

sound a little like "I'm going to learn how to fly a plane; I will work on the landing some other time"?

[Sensei]

Is it just me or does this sound a little like "I'm going to learn how to fly a plane; I will work on the landing some other time"?

For me it sounds you're trying to beat somebody who is already laying on the ground....

I met you in the gym, half century ago, in high school... I was the one you kicked when I was lying down..

 

Making compressing routine without making decompressing routine to check whether compressing routine is working fine, is nonsense, but you don't have to tell anybody...

Edited August 29, 2016 by Sensei

[John Cuthber]

 

Making compressing routine without making decompressing routine to check whether compressing routine is working fine, is nonsense, but you don't have to tell anybody...

LOL from the guy who first told him, that's funny.

[fredreload]

LOL from the guy who first told him, that's funny.

I thought it'd for sure work = =, guess I was too confident

 

P.S Wait, it works, the trick is to add the plus side as well, I'll try and get the algorithm again

Here's the complete code and the image here.

 

using System;

using System.Collections.Generic;

using System.Linq;

 

namespace HelloWorld

{

class Hello

{

public static byte[] bytes = System.IO.File.ReadAllBytes(@"E:\data\Blank.gif");

public static ushort[] array = new ushort[(bytes.Length / 4) + (bytes.Length % 4)];

public static ushort[] arraya = new ushort[(bytes.Length / 4) + (bytes.Length % 4)];

 

public static byte[] c1 = new byte[(bytes.Length / 4) + (bytes.Length % 4)];

public static byte[] c2 = new byte[(bytes.Length / 4) + (bytes.Length % 4)];

 

public static byte[] result = new byte[bytes.Length];

 

public static bool[] gtlt = new bool[(bytes.Length / 4) + (bytes.Length % 4)];

 

static void Main()

{

Console.WriteLine("Compressing");

 

compress_test();

 

Console.WriteLine("Decompressing");

 

decompress_test();

 

// Keep the console window open in debug mode.

Console.WriteLine("Press any key to exit.");

Console.ReadKey();

}

 

static int CountBits(int value)

{

value <<= 1;

int cnt = 0;

while (value != 0)

{

cnt += (0xe994 >> (value & 14)) & 3;

value >>= 3;

}

return cnt;

}

 

static IEnumerable<int> PermutateBits(int bits, int bitsSet)

{

int min = 0x7fffffff >> (31 - bitsSet);

int max = min << (bits - bitsSet);

for (int i = min; i <= max; i++)

{

if (CountBits(i) == bitsSet)

{

yield return i;

}

}

}

 

static string Bin(int value, int len)

{

return (len > 1 ? Bin(value >> 1, len - 1) : null) + "01"[value & 1];

}

 

 

 

 

static byte IteratedBitcount(ushort n)

{

ushort test = n;

int count = 0;

 

while (test != 0)

{

if ((test & 1) == 1)

{

count++;

}

test >>= 1;

}

return Convert.ToByte(count);

}

 

protected static void decompress_test()

{

int l = 0;

 

for (int i = 0; i < array.Length; i++)

{

ushort vals = 0;

ushort valb = 0;

 

if (c1 == 0 && c2 == 0)

{

vals = array;

valb = array;

}

else

{

ushort k = array;

ushort o = arraya;

 

bool check = false;

 

foreach (int m in PermutateBits(16, c1))

{

foreach (int n in PermutateBits(16, c2))

{

valb = Convert.ToUInt16(Bin(m, 16), 2);

vals = Convert.ToUInt16(Bin(n, 16), 2);

 

if (((ushort)(valb - vals) == k)&&((ushort)(valb + vals) == o))

{

check = true;

break;

}

}

if (check)

{

break;

}

}

 

}

if (gtlt)

{

if (!((l + 3) >= bytes.Length))

{

result[l + 3] = (byte)(valb >> 8);

}

if (!((l + 2) >= bytes.Length))

{

result[l + 2] = (byte)valb;

}

if (!((l + 1) >= bytes.Length))

{

result[l + 1] = (byte)(vals >> 8);

}

if (!((l + 0) >= bytes.Length))

{

result[l + 0] = (byte)vals;

}

}

else

{

if (!((l + 3) >= bytes.Length))

{

result[l + 3] = (byte)(vals >> 8);

}

if (!((l + 2) >= bytes.Length))

{

result[l + 2] = (byte)vals;

}

if (!((l + 1) >= bytes.Length))

{

result[l + 1] = (byte)(valb >> 8);

}

if (!((l + 0) >= bytes.Length))

{

result[l + 0] = (byte)valb;

}

}

 

Console.WriteLine(l);

l = l + 4;

}

 

System.IO.File.WriteAllBytes(@"E:\data\kBlan.gif", result);

}

 

protected static void compress_test()

{

 

 

byte[] array16 = new byte[4];

 

for (int i = 0; i < bytes.Length; i = i + 4)

{

for (int j = 0; j < 4; j++)

{

if (i + j >= bytes.Length)

{

array16[j] = 0;

}

else

{

array16[j] = bytes[i + j];

}

}

//3~2

ushort val1 = BitConverter.ToUInt16(array16, 2);

//1~0

ushort val2 = BitConverter.ToUInt16(array16, 0);

 

ushort diff;

 

if (array16[3] > array16[1])

{

diff = (ushort)(val1 - val2);

gtlt[i / 4] = true;

array[i / 4] = diff;

 

c1[i / 4] = IteratedBitcount(val1);

c2[i / 4] = IteratedBitcount(val2);

 

/*

byte[] result = new byte[8];

 

bytes[0] = (byte)(diff >> 56);

bytes[1] = (byte)(diff >> 48);

bytes[2] = (byte)(diff >> 40);

bytes[3] = (byte)(diff >> 32);

bytes[4] = (byte)(diff >> 24);

bytes[5] = (byte)(diff >> 16);

bytes[6] = (byte)(diff >> 8);

bytes[7] = (byte)diff;

*/

}

else

{

diff = (ushort)(val2 - val1);

gtlt[i / 4] = false;

array[i / 4] = diff;

 

c1[i / 4] = IteratedBitcount(val2);

c2[i / 4] = IteratedBitcount(val1);

 

/*

byte[] result = new byte[8];

 

bytes[0] = (byte)(diff >> 56);

bytes[1] = (byte)(diff >> 48);

bytes[2] = (byte)(diff >> 40);

bytes[3] = (byte)(diff >> 32);

bytes[4] = (byte)(diff >> 24);

bytes[5] = (byte)(diff >> 16);

bytes[6] = (byte)(diff >> 8);

bytes[7] = (byte)diff;

*/

}

 

if (diff == 0)

{

c1[i / 4] = 0;

c2[i / 4] = 0;

array[i / 4] = val1;

arraya[i / 4] = val1;

}

 

ushort add = (ushort)(val1 + val2);

arraya[i / 4] = add;

 

}

}

}

}

Edited August 30, 2016 by fredreload

[Strange]

P.S Wait, it works ...

 

Of course it doesn't.

[fredreload]

 

Of course it doesn't.

Try it yourself = =

[Strange]

What have you tested it on?

[fredreload]

What have you tested it on?

The blank.gif, I'm going to make it faster by adding two equations

x+y=z

x-y=u

except z overflowed = =

Edited August 30, 2016 by fredreload

[Strange]

The blank.gif, I'm going to make it faster by adding two equations

 

I think you should test it on a large file. A large sequence of random numbers, for example.

[fredreload]

Na, not on random numbers, it needs to be a working file lol. Anyway, this is the ultra fast version. Not much compression done on one iteration really. I'll work on it more tomorrow

 

using System;
using System.Collections.Generic;
using System.Linq;

namespace HelloWorld
{
class Hello
{
public static byte[] bytes = System.IO.File.ReadAllBytes(@"E:\data\Blank.gif");

public static ulong[] array = new ulong[(bytes.Length / 14) + (bytes.Length % 14)];
public static ulong[] arraya = new ulong[(bytes.Length / 14) + (bytes.Length % 14)];

public static bool[] gtlt = new bool[(bytes.Length / 14) + (bytes.Length % 14)];

public static byte[] result = new byte[bytes.Length];

static void Main()
{
Console.WriteLine("Compressing");

compress_test();

Console.WriteLine("Decompressing");

decompress_test();

// Keep the console window open in debug mode.
Console.WriteLine("Press any key to exit.");
Console.ReadKey();
}

static byte IteratedBitcount(ulong n)
{
ulong test = n;
int count = 0;

while (test != 0)
{
if ((test & 1) == 1)
{
count++;
}
test >>= 1;
}
return Convert.ToByte(count);
}

protected static void decompress_test()
{
int l = 0;

for (int i = 0; i < array.Length; i++)
{
ulong vals = 0;
ulong valb = 0;

ulong k = array;
ulong o = arraya;

valb = (o+k) / 2;
vals = (o-k) / 2;

if (!gtlt)
{

if (!((l + 13) >= bytes.Length))
{
result[l + 13] = (byte)(valb >> 48);
}
if (!((l + 12) >= bytes.Length))
{
result[l + 12] = (byte)(valb >> 40);
}
if (!((l + 11) >= bytes.Length))
{
result[l + 11] = (byte)(valb >> 32);
}
if (!((l + 10) >= bytes.Length))
{
result[l + 10] = (byte)(valb >> 24);
}
if (!((l + 9) >= bytes.Length))
{
result[l + 9] = (byte)(valb >> 16);
}
if (!((l + 8) >= bytes.Length))
{
result[l + 8] = (byte)(valb >> 8);
}
if (!((l + 7) >= bytes.Length))
{
result[l + 7] = (byte)valb;
}

if (!((l + 6) >= bytes.Length))
{
result[l + 6] = (byte)(vals >> 48);
}
if (!((l + 5) >= bytes.Length))
{
result[l + 5] = (byte)(vals >> 40);
}
if (!((l + 4) >= bytes.Length))
{
result[l + 4] = (byte)(vals >> 32);
}
if (!((l + 3) >= bytes.Length))
{
result[l + 3] = (byte)(vals >> 24);
}
if (!((l + 2) >= bytes.Length))
{
result[l + 2] = (byte)(vals >> 16);
}
if (!((l + 1) >= bytes.Length))
{
result[l + 1] = (byte)(vals >> 8);
}
if (!((l + 0) >= bytes.Length))
{
result[l + 0] = (byte)vals;
}
}
else
{
if (!((l + 13) >= bytes.Length))
{
result[l + 13] = (byte)(vals >> 48);
}
if (!((l + 12) >= bytes.Length))
{
result[l + 12] = (byte)(vals >> 40);
}
if (!((l + 11) >= bytes.Length))
{
result[l + 11] = (byte)(vals >> 32);
}
if (!((l + 10) >= bytes.Length))
{
result[l + 10] = (byte)(vals >> 24);
}
if (!((l + 9) >= bytes.Length))
{
result[l + 9] = (byte)(vals >> 16);
}
if (!((l + 8) >= bytes.Length))
{
result[l + 8] = (byte)(vals >> 8);
}
if (!((l + 7) >= bytes.Length))
{
result[l + 7] = (byte)vals;
}

if (!((l + 6) >= bytes.Length))
{
result[l + 6] = (byte)(valb >> 48);
}
if (!((l + 5) >= bytes.Length))
{
result[l + 5] = (byte)(valb >> 40);
}
if (!((l + 4) >= bytes.Length))
{
result[l + 4] = (byte)(valb >> 32);
}
if (!((l + 3) >= bytes.Length))
{
result[l + 3] = (byte)(valb >> 24);
}
if (!((l + 2) >= bytes.Length))
{
result[l + 2] = (byte)(valb >> 16);
}
if (!((l + 1) >= bytes.Length))
{
result[l + 1] = (byte)(valb >> 8);
}
if (!((l + 0) >= bytes.Length))
{
result[l + 0] = (byte)valb;
}
}


Console.WriteLine(l);
l = l + 14;
}

System.IO.File.WriteAllBytes(@"E:\data\kBlan.gif", result);
}

protected static void compress_test()
{
byte[] array81 = new byte[8];
byte[] array82 = new byte[8];

for (int i = 0; i < bytes.Length; i = i + 14)
{
int count = 0;
for (int j = 0; j < 8; j++)
{
if (i + j >= bytes.Length || i+j+7>=bytes.Length || j==7)
{
array81[j] = 0;
array82[j] = 0;
}
else
{
array81[j] = bytes[i + count];
array82[j] = bytes[i + count + 7];
}
count++;
}
//7~0
ulong val1 = BitConverter.ToUInt64(array81, 0);
//7~0
ulong val2 = BitConverter.ToUInt64(array82, 0);

ulong diff;

if (array81[6] > array82[6])
{
diff = (ulong)(val1 - val2);
gtlt[i / 14] = true;
array[i / 14] = diff;

/*
byte[] result = new byte[8];

bytes[0] = (byte)(diff >> 56);
bytes[1] = (byte)(diff >> 48);
bytes[2] = (byte)(diff >> 40);
bytes[3] = (byte)(diff >> 32);
bytes[4] = (byte)(diff >> 24);
bytes[5] = (byte)(diff >> 14);
bytes[6] = (byte)(diff >> 8);
bytes[7] = (byte)diff;
*/
}
else
{
diff = (ulong)(val2 - val1);
gtlt[i / 14] = false;
array[i / 14] = diff;
}
ulong add = (ulong)(val1 + val2);
arraya[i / 14] = add;

}
}
}
}

[Strange]

Na, not on random numbers, it needs to be a working file lol.

 

Then use a file of significant size. A large image or a Word document.

[fredreload]

 

Then use a file of significant size. A large image or a Word document.

Right, I'm going to work on more than one iterations tomorrow, right now it made a 43byte file 64 byte...

[Strange]

right now it made a 43byte file 64 byte...

 

I hope that is the wrong way round! Otherwise, not much of a compression.

[fredreload]

I give up, this ain't gonna compress file, I've split a single file into two parts, one with addition, one with subtraction, each of them is halved but they still add up to one

Edited August 30, 2016 by fredreload

[John Cuthber]

Na, not on random numbers, it needs to be a working file.

 

I work with weather data sometimes.

So my working files are pretty nearly random numbers.

[fredreload]

I work with weather data sometimes.

So my working files are pretty nearly random numbers.

Actually I've worked out another equation, I'm gonna test it out later tonight

x-y=w

y-x=z

w=-z

 

How do you solve for x and y Strange?

Ya, it doesn't seem it works either

 

P.S. All this program does is splitting things into parts

Edited August 31, 2016 by fredreload

[fredreload]

https://en.wikipedia.org/wiki/System_of_linear_equations

 

Might try Gauss-Jordan Elimination