Prev: No lock for bt instruction ?
Next: ~~~ LATEST TECHNOLOGY~~~ click here
From: Skybuck Flying on 17 May 2010 18:07
Say the input stream is as follows:

R,G,B, R,G,B, R,G,B, R,G,B, R,G,B, R,G,B

Compression:

RLE for R ?
RLE for G ?
RLE for B ?

The mission is to output it again as follows:

R,G,B, R,G,B, R,G,B, R,G,B, R,G,B, R,G,B

Do you believe RLE compression is possible for interleaved streams ? ;)

If you do believe it's possible write some pascal code to prove that it
works.

The input example is: 5,4,7, 5,6,9, 4,6,9, 1,6,9, 1,6,3, 7, 7, 3

Encoder may only have one loop 1 to 6:
Encode (single) R
Encode (single) G
Encode (single) B

Decoder may only have one loop 1 to 6:
Decode (single) R
Decode (single) G
Decode (single) B

Good luck !

Bye,
Skybuck.


From: Skybuck Flying on 17 May 2010 18:57
The mission was to write a "single pass RLE compressor/decompressor for RGB
interleaved streams".

I believe a single pass RLE compressor/decompressor is not possible for RGB
interleaved streams.

Example:

Encoder:
Output Red
Output Green
Output Blue

Loop
Output Count for whichever color component ends first.

Decoder:
Input Red
Input Green
Input Blue

Loop
Input Count for ???

I shall call this the "single-pass-RLE-interleaving-paradox" ;)

RLE has another paradox which I shall call the
"starting-with-empty-color-paradox" which I will not describe here since
this posting is about the "interleaving paradox" only ;) I will give a
little hint though: Once the logical paradox is in place, trying to solve it
by modifieing A will create a problem in B and when trying to solve the
problem in B it will create a problem in A and then the programmer will go
around and around in circles until the programmer finally realizes he/she is
caught in a logical paradox.

These paradoxes are very
nasty/difficult-to-climb-out-of-programming-pitfalls. The same for the
"interleaving paradox", the interleaving paradox is not visible at first
glance... everything seems to be nicely in place, the color components, the
counts, however they have been mingled/intermixed. Not seeing this problem
will again make the programmer believe that there must be a bug somewhere...
while in reality it's again a logical paradox the algorithm cannot be used
the way the programmer believes it can be used. As long as the programmer
believes the algorithm can be used he's caught in a logical paradox/loop
trying to solve the "bugs" which are not really present =D The programmer
might believe it's a synchronization issue, the encoder/decoder must be out
of sync or something... in reality the moment/time/loop index at which the
counts/colors are written determines the format of the output which cannot
be matched by the decoder in a single pass, since the decoder cannot
possible know which one was outputted first.

The problem could be solved by encoding an indicator which indicates to
which color component the count belongs... This would need at least 2 bits
per count which would
be quite wastefull.

Therefore I consider it not possible ;) since indicators are not part of the
original RLE algorithm ! ;)

RLE + Indicators = something else/special =D

It conclude with the following observation:

The RLE algorithm seems like a very simple algorithm, and conceptually it
is, but it has nasty/difficult pitfalls/logical paradoxes the likes of which
I have never seen in any another other algorithm !

Therefore I think the RLE algorithm is probably the best algorithm to test
your debugging skills with ! ;) =D Your patience ! Your arrogence ! Your
optimization drifts ! Your smartness ! ;) Your efficiency ! Your cunningness
! Your debugger ! Your text editor !

Underestimating this little algorithm is what will kill your time ! =D

Next time anybody wants to implement it my advice is to:

1. Have visualizers in place to show you what is happening to the compressed
output. This will solve the blindness issue and can help to climb out of a
pitfall ! ;)

2. Try to follow the algorithm to the letter which in itself is quite
difficult to do if other constraints are in place.

3. Try to keep the encoder code and decoder code as synchronized as
possible. (Try to make it look the same and keep the order of writes/reads
the same)

4. Be on your guard that the constraints/new situation might actually not
allow the implementation of the RLE algorithm, except with maybe
unwanted/undesireable enhancements/extensions ! ;) :)

5. Do not underestimate it ! Which is very difficult to do because it's so
simple right ?! =D LOL.

Bye,
Skybuck ;) =D


From: Skybuck Flying on 17 May 2010 21:52
After RLE there would be further bit compression, that's why single pass
without temporarely storage for the RLE output would not be possible.

However RLE for RGB interleaved is probably possible if a temporarely buffer
is used.

The encoder can then ofcourse keep track of "inserting points" in the
temporarely buffer.

Then later the temporarely buffer can be further compressed into bitfields.

This does require more memory and more bandwidth... so zero copy goes out
the window ! ;)

And this was an attempt at zero copy as well you know... did mention it...
but that was what it was about ;)

No extra buffers, just one output buffer ;) <- Probably not possible for RLE
RGB interleaved...

But with extra buffers anything becomes possible ofcourse ! ;)

Bye,
Skybuck =D



From: Skybuck Flying on 17 May 2010 22:03
Though maybe there is another solution... which does allow zero copy, and
single pass, interleaved RLE RGB... ;) :)

I'll have to try it out tomorrow... so I might have been wrong about my
earlier conclusions ! ;) :)

But for now I keep the possible solution a secret ! ;) =D

Bye,
Skybuck ;) =D


From: Skybuck Flying on 17 May 2010 22:06
One further note:

I think the solution will work... however it's a slight modification of the
RLE algorithm with very slight overhead...

So I guess it don't count as a real/true RLE algorithm... so my earlier
conclusions are probably still valid =D

However by slightly modifieing/extended the RLE algorithm it should become
possible ! =D

Bye,
Skybuck =D


 |  Next  |  Last
Pages: 1 2 3 4
Prev: No lock for bt instruction ?
Next: ~~~ LATEST TECHNOLOGY~~~ click here