Brain teaser: Can RLE compression work for interleaving streams ? For example R,G,B streams ?!
Skybuck Flying
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.
Skybuck Flying
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
Skybuck Flying
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
Skybuck Flying
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
Skybuck Flying
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
Skybuck Flying
Roy beat me to it in redcode, which I translated to pascal/delphi.
And the (*hint kept secret :)*) "inserting point"/pointer idea is indeed
possible.
However as I described in a follow-up post... I still have a trick up my
sleeve to try and do bit compression as well with rle which as I stated will
be kept secret unless somebody can understand it as well.. it's not very
hard... but can you figure it out by yourself ? ;) :)
Anyway... it was interesting to see Roy's Redcode version translated to
Pascal.
It uses 10 pointers.
Since redcode has no registers but just memory which is used as pointers
it's quite interesting.
The only other variable is a loop variable.
10 pointers does seem a bit much though...
I wonder if it can be improved to use less pointers...
Bye,
Skybuck.
"Skybuck Flying" <IntoTh...@hotmail.com> wrote in message
news:9337f$4bf1f2a7$54190f09$70...@cache5.tilbu1.nb.home.nl...
Skybuck Flying
>
> Roy beat me to it in redcode, which I translated to pascal/delphi.
Hmm, nope, not really, Roy's algorithm has a compression inefficiency...
It simply moves 3 records forward for the individual r,g,b streams.
Therefore the streams themselfes are not compacted and empty color's with
empty counts could potentially occur in a highly compressed
stream which then becomes not highly compressed.
It's quite funny to see another programmer being bitten by the RLE algorithm
! ;) =D
Bye,
Skybuck =D
pabloreda
You know forth ? my dialect is :r4
this code compress and decompress to RLE (not interleaved)
|------------ Grabar de BMP a simple RLE
#memc
#memc>
:,comp | v --
memc> !+ 'memc> ! ;
#cnt
#colact
:scanlast | --
colact cnt ( 255 >? )( over $ff000000 or ,comp 255 - )
24 << or ,comp ;
:scanconv | adr -- adr+
@+ $ffffff and | adr+ color
colact =? ( 1 'cnt +! drop ; )
scanlast
:scanini | color --
$ffffff and 'colact ! 1 'cnt ! ;
|------- SAVE
::bitmap.grabar | "bmps/test.bmr" --
bmp.bm @+ scanini
bmp.alto bmp.ancho * 2dup 2 << + dup 'memc ! 'memc> !
( 1- 1? )( >r scanconv r> ) 2drop
scanlast
memc memc> over - rot save
;
|-------------- LOAD simple RLE
::bitmap.cargar | "bmps/test.bmr" --
here swap load dup 'memc> ! >r
here ( memc> <? )( @+
dup $ffffff and swap 24 >> $ff and | color cant
( 1? )( over r!+ 1- ) 2drop
) drop
rdrop
;
-------------------------------------------------------------------------------
Bye,
PHREDA
http://code.google.com/p/reda4/
Skybuck Flying
it does require writing/reading in a different way.
The RLE algorithm probably has a certain property which can be exploited =D
You'll have to figure it out for yourself because again I am keeping it a
secret :)
I am not yet 100% but 99.9% sure... the proof is in the pudding as they say
;)
If it works then it's a nice solution... no extra bandwidth, no extra
buffers, a single pass, and just a different way of writing/reading, the
different reading/writing technique should offer the same kind of
performance as the normal way of writing/reading me thinks, it's a bit
tricky but nothing to difficult ;)
Bye,
Skybuck.
Skybuck Flying
>I have come up with a solution which requires no extra storage overhead...
>it does require writing/reading in a different way.
>
> The RLE algorithm probably has a certain property which can be exploited
> =D
>
> You'll have to figure it out for yourself because again I am keeping it a
> secret :)
>
> I am not yet 100% but 99.9% sure... the proof is in the pudding as they
> say ;)
>
> If it works then it's a nice solution... no extra bandwidth, no extra
> buffers, a single pass, and just a different way of writing/reading, the
And ofcourse "bit compression" that is what it is all about ofcourse... that
was the original problem... that is now solved as well.
So I forgot to mention the most important thing as well...
This new solution should work for the bit compression as well ! ;) =D
Skybuck Flying
ofcourse...
And it's really nifty... the encoder can be as usual, quite fast and it
actually doesn't require any interleaving...
which means it doesn't require any extra pointers ! =D
That will make it very fast ! :)
This posting does leak a bit of information about the new algorithm
though... if you read carefull you will understand
where the "innovation" is at ;) :)
Bye,
Skybuck =D
Skybuck Flying
I just finished implementing my newest/latest RLE RGB algorithm =D
(You may call it a RLE interleaving algorithm) ;)
And I have done some quick testing... and debugging and it seems to work
perfectly/flawlessly =D
"Absolute perfection" comes to mind, at all fronts:
Speed, Compression, Correctness ;) :)
I haven't actually added the bit compression yet... but that should work as
well.
So my final conclusion is:
Yes RLE RGB compression can work for interleaving streams with the correct
algorithm ! =D
Which requires exploiting a certain property of the RLE algorithm when it is
interleaved ! ;)
So the RLE algorithm actually obtains a new property when multiple RLE
streams are interleaved ! =D
Yup that's the secret... something interesting happens when RLE algorithms
are interleaved ! =D
And that property can be used to solve the problem ! =D
I am now 99.9999999999999999999999999% certain that the final bit
compression is going to work as well.
However the proof is in the pudding.
For now I have implemented a conceptual implementation which uses a byte and
a longword.
The byte and longword will be replaced by a 8-bitfield and a Skybuck's
universal code/bitfield.
These bitfields can than be bitpacked onto the output.
Then a final test will be done to say with 100% certainty if it's possible
=D
The universal code will have to be slightly changed to match the property...
or I could create a general universal code which does it on both sides, hint
hint.
Then maybe later sometime in the far future I might replace the universal
code with a dynamic huffman code for perhaps the counts and perhaps the
colors.
The counts could be risky though because there could be many different
ones... the colors might compress better.
So maybe my universal code for this particular compression method is pretty
code.
This whole experiment is just to see how to create a good rle rgb
interleaved algorithm to learn from it.
Now that I seem to have perfected it I can move on to other things like
perhaps doing it at the bitplane level and perhaps using GPGPU/OpenGL to try
and create an even faster version.
I want to release a super fast lossless codec sometime in the near (?)
future for 1. fun and 2. speed and 3. compression.
Speed is most important because having to re-encode/transcode sucks and
takes a lot of time with current codecs.
Maybe it could also be used for real-time recording of video losslessly.
Then second place of importancy is compression, to be able to perhaps store
video for the future to look back on it.
For now I wonder how my codec will compare to say for example Fraps codec...
for now it seems Fraps codec is fast and achieves pretty good lossless
compression ! ;) :)
As soon as I have some figures available I will perhaps let you guys know !
;) =D
Bye,
Skybuck =D
Skybuck Flying
breadfast/lunch and then I listened to for example this music:
http://www.youtube.com/watch?v=eoay-oUtACo&playnext_from=TL&videos=O0bNiyL99_Y
Which I have fond memories of ! =D
Much fun coding this stuff and much fun listening to this music ! ;) =D
Bye,
Skybuck =D
Skybuck Flying
> Also during the development I sometimes took a little pause or had
> breadfast/lunch and then I listened to for example this music:
>
> http://www.youtube.com/watch?v=eoay-oUtACo&playnext_from=TL&videos=O0bNiyL99_Y
Oh yeah before they removed that link again, the music title is:
"Primal Scream - Can't Go Back" ;) :)
YEAHAHAHAH =D
Bye,
Skybuck =D
MitchAlsup
VLSI tester and compress these. It ends up that when one looks at the
vectors there is very little change in the vertical direction, and
much change in the horizontal direction.
RLE in the horizontal direction got 40%-ish lossless compression
RLE in the vertical direction vas getting 99.3% lossless compression
The compression was so good, it was actually faster to read out these
multi-GByte files into the tester in compressed form and expand them
on the fly into the tester than to read the image directly off the
disk.
Moral: compress on the dimension that has commonality.
Mitch
Skybuck Flying
This posting of yours just gave me an idea :)
I already did some modest form of horizontal/vertical and even diagonal
compression and frame compression and a mixed of all this... but just for 8
bits at a time...
I was wondering if vertical RLE would be possible... first I was thinking
along the lines of multiple vertical lines...
But I just realized it should be possible to do a simple vertical RLE which
simply skips over the "horizontal line width" and then perhaps wraps around
to the next vertical line + 1 or so... I am not sure what the algorithm
would be, but it would probably need a second loop... so I guess it would
simply be the familiar
for x
for y loop ;)
However there is a "little/big" problem with this.
I want a really fast codec... so I was thinking about simply hard-coding one
method and ignoring the other one...
So the codec would always use horizontal RLE...
But I can imagine some scenes/frames where vertical RLE... would give much
better compression...
I do wonder what the memory performance would be for RLE since there would
probably (?) be big skips... and less streaming/cache usage ?
I did have some idea's to do quick scan for some other compression
algorithms... but for RLE I don't know if some sort of fast scan could be
done... maybe try a few lines or so ?
But RLE is presumeably so fast it probably won't hurt that much to do it
vertical and horizontal and then select the best one... and maybe even
especially when gpgpu is used... which still needs to be investigated by
me...
I am not sure if nvidia's CG dll will run on ATI cards ? I think so but not
sure... never tested it so far...
And you correct about the compressed files... I see the same happen with the
harddisk.
The harddisk is limited to 60 MByte/sec or so... so the frames must all fit
in 60 MByte/sec or less... otherwise the harddisk is not fast enough...
The CPU is much faster than just 60 MByte/sec ! ;) :) so it can decompress
it...
I think I could probably re-use my existing class and simply add a boolean
to switch modes and try... this will prevent namespace pollution and issue's
so it could look like:
.CompressionDirection := cd_horizontal;
or
.CompressionDirection := cd_vertical;
Something like that it could be called.. ;) :)
"MitchAlsup" <Mitch...@aol.com> wrote in message
news:f51799f2-a814-45c8...@c7g2000vbc.googlegroups.com...
Bye,
Skybuck and thanks for responding ! =D
Skybuck Flying
> to switch modes and try... this will prevent namespace pollution and
> issue's so it could look like:
>
> .CompressionDirection := cd_horizontal;
> or
> .CompressionDirection := cd_vertical;
>
> Something like that it could be called.. ;) :)
Right before I wanted to go to bed I had another idea for the name:
.RunningDirection := rd_horizontal;
or
.RunningDirection := rd_vertical;
Or perhaps better to indicate a single state of being/to-be:
.RunDirection := ... etc;
However it's kinda funny/interesting that .RunningDirection could actually
be changed while the algorithm runs...
Then it could start behaving like a worm... or a hook.
It could perhaps use 2 bits to indicate what new direction it went into...
or perhaps one bit... or perhaps even no bits !
The algorithm could start with a horizontal run... and then when it can't go
any further it could try to go always down to see if it can run further
there...
The decoder would then know this as well... this would need no bits... but
it would require ofcourse a new count... but just a new count only... no
extra color information...
After this strange deviation is done... the algorithm could go back to the
point of deviation and continue as normal... it could use a bitset to keep
track of what pixels where already compressed by the "strange" worm like
creature ;) :) and skip those...
Kinda funny algorithm... I might try it out to see what it gives... it could
be interesting for for example "box like structures"... for example gui
video's could have such boxes...
In that case the worm could even maintain a steady order of going about for
example:
First right, then down, then left, then up again... the algorithm could keep
track of the counts to make sure it doesn't enter it's previous trail...
Such a compression algorithm could be nice for square like spirals or so...
though I would not expect too many video's to have those...
But other line-structures are thinkable were this might work...
Though this could get a little bit out of hand... and the remaining question
would then be when to stop ?
Perhaps after it can't go into the next direction... or maybe it could give
the direction after that a try... but no it can't do that because then it
would backtrack funny enough...
So the answer is pretty apperent... if it can't go into the next direction
then it must stop... ofcourse the bitset could help as well to detect
collisions... and perhaps move into another direction... possibly even
against the general rules of going right... it could now go left to try
something different or so... kinda funny.
However if it followed legal counts then it would go right as long as no
bitset is crossed.
This is kinda experimental idea though... and the bitset would require a lot
of random access and a lot of extra overhead... so I will probably not do
that for now... since I want to get something done and working ! ;) :)
So I guess turning on my PC just to post this message was a little bit worth
it after all since I did not plan to write this possible extension to the
algorithm... but there ya go ! ;) Conclusion: One never knows what you might
end up with once you start to write your thoughts down on "virtual paper" ;)
:) At least that's the case with me... it happens very often... I guess one
could say: "I am an ideas-drifter" ;) :)
Bye,
Skybuck =D
Skybuck Flying
be applied to 3D volumes as well ?! ;) :)
So little extra note there ! ;) :)
Bye,
Skybuck =D
Skybuck Flying
Me just woke up after a good 10 hours night sleep, I like that !, Me happy
about that ! =D
Anyway...
I have now three new idea's to try out:
1. RunningDirection := RD_CHOOSE;
2. RunningDirection := RD_BOTH;
3. RunningDirection := RD_WORM;
The most interesting two are probably 1 and 3... number 2 I just made up ;)
:)
Number 1 would choose which direction is the best at each new runlength.
Number 2 could try to go in both directions as the same time... which is
kinda interesting to try out as well.
Number 3 seems most interesting where the worm can have two decision
directions of each end of a run.
All these methods require relatively a little ammount of bits to add after
each encoding.
I think it's worth investigating how much better or worse compression these
methods might give.
All these methods would probably use a bitset at the encoder and decoder to
keep track of pixels/color components which were already compressed.
So the bitset/bitget functions would be very important to be fast...
unfortunately... Delphi 2007 can't inline assembler routines so there would
be quite some procedure call overhead and return :( But for now this
will/would have to do.... very maybe it might be possible to inline the asm
instruction myself with an
asm
endl
statement block... but this is probably a bit tricky to do but I think I
know a way... just loading the variables into some register might work ? but
what if those registers are already being used by the code ? hmm... maybe a
push and pop ? But then maybe a routine call might be just as fast... me not
sure about that.
Anyway it is interesting for compression wise... speed wise... I don't
know...
Alternatively an array of bytes instead of bits could be used to see if
maybe an array of bytes is faster... it would use up more bandwidth
probably... but if there is plenty of bandwidth on the pc than at least on
pc not a problem... Using bytes might actually allow encoding more decision
information or so for the algorithm... as long as the decoder does the
same... for now I have no idea how to add extra information... for now it's
simply... compressed or not compressed ;) :)
There I will leave my descriptions of these algorithms at that ! ;) :)
Bye,
Skybuck :)