Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #18027 > unrolled thread

Skybuck's Parallel Static Huffman Decoding Algorithm

Back to article view | Back to comp.arch

Contents

  Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-12 06:37 +0200
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-09-12 05:54 +0000
      Re: Skybuck's Parallel Static Huffman Decoding Algorithm Terje Mathisen <"terje.mathisen at tmsw.no"> - 2013-09-12 10:03 +0200
      Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-12 16:28 +0200
      Re: Skybuck's Parallel Static Huffman Decoding Algorithm Dombo <dombo@disposable.invalid> - 2013-09-14 14:57 +0200
        Re: Skybuck's Parallel Static Huffman Decoding Algorithm Willem <willem@turtle.stack.nl> - 2013-09-14 19:12 +0000
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm Jasen Betts <jasen@xnet.co.nz> - 2013-09-12 13:31 +0000
      Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-12 16:30 +0200
      Re: Skybuck's Parallel Static Huffman Decoding Algorithm BGB <cr88192@hotmail.com> - 2013-09-12 19:39 -0500
        Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2013-09-13 08:05 +0200
          Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm) BGB <cr88192@hotmail.com> - 2013-09-14 00:43 -0500
            Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm) "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-15 18:28 +0200
              Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm) BGB <cr88192@hotmail.com> - 2013-09-16 17:00 -0500
                Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm) "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-26 14:37 +0200
                  Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm) BGB <cr88192@hotmail.com> - 2013-09-26 23:50 -0500
        Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Shaun" <stereobuff07@gmail.com> - 2013-09-19 04:26 -0500
          Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-22 03:25 +0200
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm Thomas Richter <thor@math.tu-berlin.de> - 2013-09-21 10:09 +0200
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm MitchAlsup <MitchAlsup@aol.com> - 2013-10-06 17:09 -0700

#18027 — Skybuck's Parallel Static Huffman Decoding Algorithm

Hello,

Today/Tonight I had an idea how to fund my Algorithm skills ;) :)

It's always funny to see how some programmers believe that Huffman cannot be 
decoded in parallel.

I believe it is possible to decode (static) huffman in parallel.

However as I wrote in the past I want a million dollars for it ! ;)

Perhaps nobody is going to pay 1 million dollars all by him/herself so 
instead I am going to give crowd funding a try ! ;)

I just created a project for it and here you can find it and donate if you 
are curious:

http://igg.me/p/525568/x/4730405

Tomorrow I will also add a new project for my Cuda/Delphi Framework so that 
hopefully a million Delphi programmers can start using Cuda with ease ! ;)

The Cuda/Delphi framework is super real.

The algorithm is inside my head and in a draft so it will need further work 
and ofcourse implementations will be made ! ;)

Read the project description for more information about the algorithm ! ;)

Do tell everybody about it too ! ;)

Bye,
  Skybuck.

[toc] | [next] | [standalone]

#18028

In comp.compression Skybuck Flying <Windows7IsOK@dreampc2006.com> wrote:

(snip)
> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
 
> It's always funny to see how some programmers believe that 
> Huffman cannot be decoded in parallel.

No, not impossible, but not so easy, either.
 
> I believe it is possible to decode (static) huffman in parallel.
 
> However as I wrote in the past I want a million dollars for it ! ;)
 
> Perhaps nobody is going to pay 1 million dollars all by him/herself so 
> instead I am going to give crowd funding a try ! ;)

The VAX instruction format was designed to efficiently use the
bits, in a way somewhat similar to the way Huffman does.
Instructions can have from one up to some high number of bytes,
maybe 16 or so. It is not easy to figure out how many, either.
That is one reason that VAX didn't last longer than it did.

In contrast, the S/360 (and successor) instruction length is
known from the first two bits of the opcode. Not quite as easy
as with only one length (most RISC) but pretty easy.

So, yes, if the length can be determined from a small number of
bits in the beginning, then it isn't hard to do in parallel.

IA32 is pretty CISCy, but not quite as bad as VAX. It takes some
pretty strange logic to decode it and generate RISC-like code
to actually execute, possibly out of order, and in parallel.

-- glen

[toc] | [prev] | [next] | [standalone]

#18029

(groups reduced to jsut c.arch)
glen herrmannsfeldt wrote:
> The VAX instruction format was designed to efficiently use the
> bits, in a way somewhat similar to the way Huffman does.
> Instructions can have from one up to some high number of bytes,
> maybe 16 or so. It is not easy to figure out how many, either.
> That is one reason that VAX didn't last longer than it did.
>
> In contrast, the S/360 (and successor) instruction length is
> known from the first two bits of the opcode. Not quite as easy
> as with only one length (most RISC) but pretty easy.
>
> So, yes, if the length can be determined from a small number of
> bits in the beginning, then it isn't hard to do in parallel.

One of my early decoders had very skewed input, i.e. there was many very 
short huffman tokens and a sparse tail of much longer ones.

My decoder would simply grab N bits, where N was selected to require a 
reasonably sized lookup table, then from the table it would fetch either 
the (negative) index of a secondary table (for tokens longer than N, 
very rare), or an index into a byte-packed list of (length/tokens/bits).

The next step would simply grab the length and do a REP MOVSB to copy as 
many output tokens as indicated, then grab one more byte which specified 
how many bits to remove from the input buffer variable:

Effectively branchless, averaging ~3 decoded tokens per iteration, 
something like this:

next:
   mov eax,edx		; 11 to 32 input bits
   and eax,2047		; 11-bit lookup table
   movsx eax,word ptr token_lookup[eax*2] ;; 16 bit entries

   lea esi,token_stream[eax+1] ; Point at token list
   movzx ecx, byte ptr [esi-1]
    jcxz use_secondary_table

   rep movsb		; Copy the output tokens!
   movzx ecx,byte ptr [esi] ; How many bits did we consume?
   shr edx,cl
   sub ebx,ecx		; Buffer bits - 11
    jae next

; Refill the input buffer, there is room for at least 21 more bits!
   mov esi,[input_ptr]
   lea ecx,[ebx+11]	; Current buffer size in bits
   mov eax,[esi]		; Usually misaligned...
   shl eax,cl
   or edx,eax		; Merge the new bits into the EDX buffer

   ; Calculate how many bytes/bits to advance:
   mov eax,32
   sub eax,ecx		; Room for this many new bits
   shr eax,3		; # of input bytes accepted
   add esi,eax
   lea ebx,[ebx+eax*8]	; Adjust bit count!
   mov [input_buffer],esi
    jmp next

use_secondary_table:
   mov esi,[esi]
   shr edx,11
   sub ebx,11

; Pick up table size, lookup mask etc from this secondary table
;...

Terje

-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#18031

Hmm interesting.

I didn't realize my invention could be used to decode instructions in 
parallel as well.

But that is indeed possible as well.

Even for variable size instructions, just like huffman codes.

Bye,
  Skybuck. 

[toc] | [prev] | [next] | [standalone]

#18044

Op 12-Sep-13 7:54, glen herrmannsfeldt schreef:
> In comp.compression Skybuck Flying <Windows7IsOK@dreampc2006.com> wrote:
>
> (snip)
>> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
>
>> It's always funny to see how some programmers believe that
>> Huffman cannot be decoded in parallel.
>
> No, not impossible, but not so easy, either.

It is possible and not that hard either, and in fact has been done many 
times before by many people (myself included). I'm inclined to believe 
that you'll only see pure serial Huffman decoding in classrooms.

[toc] | [prev] | [next] | [standalone]

#18045

Dombo wrote:
) Op 12-Sep-13 7:54, glen herrmannsfeldt schreef:
)> In comp.compression Skybuck Flying <Windows7IsOK@dreampc2006.com> wrote:
)>
)> (snip)
)>> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
)>
)>> It's always funny to see how some programmers believe that
)>> Huffman cannot be decoded in parallel.
)>
)> No, not impossible, but not so easy, either.
)
) It is possible and not that hard either, and in fact has been done many 
) times before by many people (myself included). I'm inclined to believe 
) that you'll only see pure serial Huffman decoding in classrooms.

That depends on if you get to control the encoding side.

A small bit of extra work on the encoding side makes it easy to decode
chunks in parallel, otherwise you have several problems, such as the
impossibility to decide the position in the decoded stream without
decoding the previous stream, and the existence of encoded streams
where each position leads to a valid (but different) decoded stream,
only one of which is the correct one.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#18030

On 2013-09-12, Skybuck Flying <Windows7IsOK@DreamPC2006.com> wrote:
> Hello,
>
> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
>
> It's always funny to see how some programmers believe that Huffman cannot be 
> decoded in parallel.
>
> I believe it is possible to decode (static) huffman in parallel.
>
> However as I wrote in the past I want a million dollars for it ! ;)
>
> Perhaps nobody is going to pay 1 million dollars all by him/herself so 
> instead I am going to give crowd funding a try ! ;)

It's absolutely possible to decode static huffman in parallel 
just start decoders off at all different offsets and when you reach
that part reject the output that was computed starting with the wrong offset.

It may pe possible to imply the correct offet by examineing the
bitstream, but this is not possible for all huffman tables, and is a
gross waste of resources.

If you want fast static huffman decoding, use an FPGA, they are
ideally suited.

[toc] | [prev] | [next] | [standalone]

#18032

Hmmm.. I was expecting the usefull truck full of horse shit... but so far 
the responses have been intelligent and some even surprising and insight 
full.

You are indeed close to figuring out my algorithm... but some concepts are 
still missing ;)

Bye,
  Skybuck. 

[toc] | [prev] | [next] | [standalone]

#18034

On 9/12/2013 8:31 AM, Jasen Betts wrote:
> On 2013-09-12, Skybuck Flying <Windows7IsOK@DreamPC2006.com> wrote:
>> Hello,
>>
>> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
>>
>> It's always funny to see how some programmers believe that Huffman cannot be
>> decoded in parallel.
>>
>> I believe it is possible to decode (static) huffman in parallel.
>>
>> However as I wrote in the past I want a million dollars for it ! ;)
>>
>> Perhaps nobody is going to pay 1 million dollars all by him/herself so
>> instead I am going to give crowd funding a try ! ;)
>
> It's absolutely possible to decode static huffman in parallel
> just start decoders off at all different offsets and when you reach
> that part reject the output that was computed starting with the wrong offset.
>
> It may pe possible to imply the correct offet by examineing the
> bitstream, but this is not possible for all huffman tables, and is a
> gross waste of resources.
>
> If you want fast static huffman decoding, use an FPGA, they are
> ideally suited.
>


for one of my ideas for a video codec, I had considered the possibility 
of starting each row of macroblocks on a byte-aligned address (and with 
a zeroed DC predictor), which could potentially allow a decoder to have 
the ability to decode each row of macroblocks in a separate thread 
(as-needed).

haven't actually done this though...

[toc] | [prev] | [next] | [standalone]

#18035 — Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm)

(groups reduced to c.arch)
BGB wrote:
> for one of my ideas for a video codec, I had considered the possibility
> of starting each row of macroblocks on a byte-aligned address (and with
> a zeroed DC predictor), which could potentially allow a decoder to have
> the ability to decode each row of macroblocks in a separate thread
> (as-needed).
>
> haven't actually done this though...
>
Afair, BluRay encodes every frame in 4 subframes, possibly/probably 
because that allows trivial 4-way parallelism which both matches better 
to the 7-8 Cell cores on a PSIII, and reduces the working set of each 
subframe to a size which actually fits inside one such core.

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#18043 — Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm)

On 9/13/2013 1:05 AM, Terje Mathisen wrote:
> (groups reduced to c.arch)
> BGB wrote:
>> for one of my ideas for a video codec, I had considered the possibility
>> of starting each row of macroblocks on a byte-aligned address (and with
>> a zeroed DC predictor), which could potentially allow a decoder to have
>> the ability to decode each row of macroblocks in a separate thread
>> (as-needed).
>>
>> haven't actually done this though...
>>
> Afair, BluRay encodes every frame in 4 subframes, possibly/probably
> because that allows trivial 4-way parallelism which both matches better
> to the 7-8 Cell cores on a PSIII, and reduces the working set of each
> subframe to a size which actually fits inside one such core.
>

yeah.

in my case, I am mostly working on a PC. 4 or 8 sub-frames would 
probably work fine (vs encoding each block-row), unless of course 
someone wanted to try some sort of GPGPU based decoder or similar.

thus far though, I had been getting along ok decoding whole frames at a 
time though.


actually, a bigger issue at the moment would be doing parallel encoding, 
partly as for things like real-time video capture, my encoder has a hard 
time keeping up (*1).

I had considered the possibility of a dual-thread frame-interleaved 
encoder, but didn't want to deal with the added complexity.

as-is, it works ok though.

*1: current effective limit, with a single-threaded encoder compiled 
with debug settings (and a 3.4GHz Phenom II), is around 1440x900x24Hz, 
though it can go a bit faster if compiled with optimization settings 
(can encode 1920x1080 @30Hz). this being for capturing video in a 
Motion-JPEG variant.

theoretically, a dual-thread optimized encoder could potentially do 
1080p 60Hz capture (not verified).

decode speeds can be a little higher though...



one of my faster codecs (not JPEG based) pulled off decoding at around 
600 Mpix/s (megapixels per second, or ~ 1080p @300Hz), but was fairly 
slow to encode and had a poor size/quality tradeoff (*2).

*2: it was based around DXTn compression, in its later form using a 
table of DXT1 blocks, and an LZ77 packed index table. it involved a 
costly process of trying to identify an "optimal" set of blocks to 
encode an I-Frame and its following P-Frames.

decoding consisted mostly of memory-copying though, so wasn't really CPU 
intensive.

but, the size/quality tradeoff sucked vs M-JPEG and friends.


I had considered other ideas for codecs which would try to be more of a 
compromise, but this has been a bit weak as the current codec (JPEG 
based) is "generally fast enough" (doesn't really show up in profiler, 
when used to stream multiple low-res video-streams into textures).

as-is, the decoder transcodes directly to DXT (oddly, this is faster 
than going to RGBA).


some of my codec ideas would have been more of a compromise, trying to 
combine JPEG-like encodings with specializing in fast decoding / 
transcoding into DXT.

but, this is less important, given the existing codec goes "fast enough"...

[toc] | [prev] | [next] | [standalone]

#18054 — Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm)

Does your video codec use any transformation algorithms ?

For example "move to front" ?

I invented my own variation on it. I call it "Bubble to Front"

I uses something like 1 or 2 operations per transformation instead of 128 on 
average for move to front or so.

I am willing to sell the algorithm for 10.000 dollars ?! ;) :)

Bye,
  Skybuck. 

[toc] | [prev] | [next] | [standalone]

#18058 — Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm)

On 9/15/2013 11:28 AM, Skybuck Flying wrote:
> Does your video codec use any transformation algorithms ?
>
> For example "move to front" ?
>

the fast one?...


no, it was based mostly around tables of DXT blocks and a bytewise LZ77 
variant.

with DXT1, each block is 64 bits, and represents 4x4 pixels (via a 
fixed-format).
the natural form of an image is as a raw grid of these blocks.
this format is directly supported by most current graphics hardware.


you can compress the images by finding, say, N blocks which can best 
represent a group of frames (by merging similar-looking blocks).

say, N=256, this means 2kB for the block table, and for an image of 
256x256, ~4kB per raw index table per frame, which is then LZ77 compressed.

if you take a group of say, 8 frames, you can reduce them to the 256 
most representative blocks, and would need about 32kB for the frame 
data, however, the frame-data can be LZ77 compressed, and is thus much 
smaller, say, 12kB.

decompression mostly consists of copying blocks from the table to the 
output, or ranges of prior DXT blocks from the sliding window.

the DXT5 case was nearly identical to the DXT1 case, except that the 
frame was treated as a pair of images, one for RGB and one for Alpha.


the main advantage it had was high decoding speed.

the big drawbacks:
poor size/quality tradeoffs (quality per bitrate was worse than M-JPEG, *1);
patent concerns.

though, interestingly, it isn't too far off from how some early video 
codecs worked (namely Cinepak and Apple Video).


*1: with around 2kB/frame for 256x256 frames, you can get generally 
somewhat higher image quality via JPEG, since a JPEG at 20 or 25% 
quality will still look better than a severely abused DXTn image.

secondary deflate compression could reduce the size/quality gap 
slightly, but tended to somewhat reduce the decoding speed (from around 
600 Mpix/s to around 250 Mpix/s).


so, my currently most-used codec is basically a JPEG-variant with a lot 
of specialized extension features (which in its baseline mode is 
more-or-less backwards compatible with normal JPEG decoders).



a considered compromise was basically just trying to design a "loosely 
JPEG-like" image codec mostly around the goal of high decoding speeds 
(and transcoding to DXT), the goal being to try to pull off around 
100-200 Mpix/s (per thread).

much less than 100 Mpix/s, and there is too little gain over M-JPEG, 
which can pull off around 70-90 Mpix/s (per thread).


the design would have been mostly like a shaved-down JPEG, in a few 
cases switching out for cheaper transforms (replacing DCT and YCbCr with 
WHT and YCoCg), and leaving off a few things which eat extra 
clock-cycles (ex: DC bias adjustment and escape-coding 0xFF bytes).

the downside:
I wasn't actually really all that certain that the changes would make a 
significant difference, like if it makes no difference, or is only a 
minor performance gain.


another factor:
as-is, the current JPEG decoder isn't actually really showing up in the 
profiler even with streaming multiple videos into textures (though most 
are low-res and low frame-rate, *2).

so, effectively, it seems it is "fast enough"... (and size/quality is 
more immediately obvious...).


*2: 256x256 @10Hz is typical, but multiple streams at 512x512 @16Hz or 
24Hz also work fine (minimal CPU impact).


> I invented my own variation on it. I call it "Bubble to Front"
>
> I uses something like 1 or 2 operations per transformation instead of
> 128 on average for move to front or so.
>
> I am willing to sell the algorithm for 10.000 dollars ?! ;) :)
>

errm, I already know of several variants of these...


> Bye,
>   Skybuck.

[toc] | [prev] | [next] | [standalone]

#18104 — Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm)

What kind of compression ratio do you hope to achieve ?

For example lossless video codecs might achieve 1:2 or very maybe 1:4 for 
highly detailed images.

Mpeg I think achieves something like 1:200.

"BGB"  wrote in message news:l17v5j$avd$1@news.albasani.net...

On 9/15/2013 11:28 AM, Skybuck Flying wrote:
> Does your video codec use any transformation algorithms ?
>
> For example "move to front" ?
>

the fast one?...

"
no, it was based mostly around tables of DXT blocks and a bytewise LZ77
variant.

with DXT1, each block is 64 bits, and represents 4x4 pixels (via a
fixed-format).
the natural form of an image is as a raw grid of these blocks.
this format is directly supported by most current graphics hardware.
"

Little bit interesting, though I think searching for similar blocks dont 
work so wel for lossless video... only little bit different and there is a 
problem.

Though for lossless videos it could be good.

Very maybe for lossless video the difference could be stored somehow or so.

I also coded a super fast code which runs on a pentium III 450 mhz or so... 
it uses some kind of horizontal/vertical compression and I think I even 
tried diagonal.

It's not bad.. it can compress toony videos pretty well.

So far I have not released any codec to the public though... I don't see why 
I should do that.

> I invented my own variation on it. I call it "Bubble to Front"
>
> I uses something like 1 or 2 operations per transformation instead of
> 128 on average for move to front or so.
>
> I am willing to sell the algorithm for 10.000 dollars ?! ;) :)
>

"
errm, I already know of several variants of these...
"

Hmm I am not aware of any existing ones... I have seen many try.

I would be curious to see if you can re-produce it ;)

Bye,
  Skybuck. 

[toc] | [prev] | [next] | [standalone]

#18120 — Re: Parallel video codec (Re: Skybuck's Parallel Static Huffman Decoding Algorithm)

On 9/26/2013 7:37 AM, Skybuck Flying wrote:
> What kind of compression ratio do you hope to achieve ?
>
> For example lossless video codecs might achieve 1:2 or very maybe 1:4
> for highly detailed images.
>
> Mpeg I think achieves something like 1:200.
>

the fast one was basically crap WRT compression ratio.
it wasn't meant to compress well, mostly just to go fast.


I have a newer one, based on a hacked up version of Apple Video / RPZA + 
LZ77, which does moderately better, and still decompresses quickly
(around 480 megapixels/second).


generally, in gets (at worst) about 1:8 vs uncompressed RGBA, but often 
does a bit better (~ 1:12 - 1:30).

at max quality, it is basically similar to DXT1, which in turn is 
"fairly similar" to the quality of an image stored at 15-bpp (the loss 
in color precision is generally more obvious than the issues with pixel 
blocks).

doing block-reduction quickly and at good quality levels is still a 
problem though (so, the fastest option is simply to dump images with no 
block reduction).

transcoding blocks is pretty fast as it is mostly about feeding bytes 
through tables.


> "BGB"  wrote in message news:l17v5j$avd$1@news.albasani.net...
>
> On 9/15/2013 11:28 AM, Skybuck Flying wrote:
>> Does your video codec use any transformation algorithms ?
>>
>> For example "move to front" ?
>>
>
> the fast one?...
>
> "
> no, it was based mostly around tables of DXT blocks and a bytewise LZ77
> variant.
>
> with DXT1, each block is 64 bits, and represents 4x4 pixels (via a
> fixed-format).
> the natural form of an image is as a raw grid of these blocks.
> this format is directly supported by most current graphics hardware.
> "
>
> Little bit interesting, though I think searching for similar blocks dont
> work so wel for lossless video... only little bit different and there is
> a problem.
>
> Though for lossless videos it could be good.
>
> Very maybe for lossless video the difference could be stored somehow or so.
>

these are lossy codecs.

DXT is a lossy conversion from RGBA, and block-reduction itself looses 
quality.

the big main that copying pixel blocks have is that they can be copied 
around relatively quickly, without the need for a lot of additional 
arithmetic.

basically, you can't have exact blocks here, only approximates based on 
"similar looking" blocks, or when possible, replacing blocks with simple 
flat colors.


granted, things like DCT or WHT based codecs can still be made pretty 
fast, and can deliver much higher image quality at smaller sizes, *1, ...

but, it is less important if the target format is DXT, since DXT is 
fairly limited, and fixed blocks are much more useful here.


*1: though I have observed that, while often better than what 15bpp RGB 
does, traditional video codecs (H.264 and Theora) still fall a little 
short of full 24bit color precision (even at 100% quality, the encoders 
still tend to leave slight blocking artifacts).

slightly better would be if 100% quality would be lossless, 90% would be 
near lossless, ... 10% = nearly unrecognizable.

instead, they seem to calibrate it so that 100% ~= 80% JPEG quality, and 
0% ~= 25% JPEG quality.

granted, getting lossless out of DCT and having high performance is a 
problem, which is one place where WHT has a slight advantage: it is 
integer reversible and is faster than RDCT and similar.

likewise for preferring a colorspace like RCT or YCoCg over YCbCr, as 
RCT and YCoCg are fully reversible.


granted, color-conversion and entropy coding also tend to be big 
time-waster.

though, it is possible to VLC code the blocks differently, and squeeze a 
little more speed out of it:
for example, rather than encoding blocks one-at-a-time, in an order like 
YYYYUV YYYYUV ..., they can be reorganized into a number of coefficient 
planes, something like:
(if P-Frame) Motion Vectors;
Y DC values (for all blocks);
Y AC1 values (all blocks);
...
Y AC63 values (all blocks);
U DC;
U AC1
...
U AC63;
V DC;
...

this then results in very long runs of zeroes in the VLC coding, with in 
my case my using a VLC scheme like:
Z3V5
Z=zero prefix, V=value prefix.

where Z=0-6 encode the Zero count directly, and Z=7 uses V to encode the 
run-length, rather than a value.

this is partly because IME runs tend to be either very short or very long.

I have multiple variants of this scheme, mostly differing on how the 
special case of encoding commands is handled.


V does not directly encode the values, but generally serves as a prefix 
which indicates the value-range and how many "extra bits" follow 
(generally using a scheme very similar to the Deflate distance encoding).

typically, multiple Huffman tables are used.

one trick also is throwing PNG like predictors into this, but this adds 
a bit of cost (now need to run the predictor over each run of blocks).

luckily, the generally most effective combination tends to be Paeth for 
DC, and None for AC coefficients, and luckily None is pretty cheap.

so, an example of such an image format would be using 8x8 WHT blocks, 
the YCoCg colorspace, 4:2:0 or 4:4:4, and a plane-based VLC strategy 
(with, as applicable, motion-vectors also being thrown in).

unlike a lot of video formats, I like having the ability to encode 
Huffman and quantization tables in the I-Frames.

my other codecs have tended to use entropy-coded tables (more like those 
in Deflate).

decoding may look like:
if I-Frame:
   decode header tables.
if P-Frame:
   decode motion vectors.
VLC decode image;
run filters over coefficient scanlines;
dequantize (which repacks image back into coefficient blocks);
run Inverse-WHT (or IDCT);
if P-Frame:
   apply motion compensation, putting the result into the YUV planes.
if I-Frame:
   copy block pixels into YUV planes.

at this point, we can either convert to RGB(A), or convert to DXT or 
similar (and maybe also rebuild mip-maps and similar).


the difficulty though is that mostly with something like this, it is 
pretty hard to break 100 megapixels per second per thread for decoding 
(in my tests, though granted, other people may be able to get these 
things a bit faster for all I know).

it makes it a lot more attractive to use block-copying, even if 
size/quality tradeoff is a lot worse...


note that it requires 60 megapixels/second for 1080i @ 60Hz, and 120 
Mpix/s for 1080p @ 60Hz.

or 30Mpix/s for 1080i at 30Hz, or 60Mpix/s for 1080p at 30Hz.

so, yeah, something DCT or WHT based is plenty usable for traditional 
video playback.


so, a 480Mpix/s codec could theoretically allow decoding 8 1080p streams 
at once, and 960Mpix/s (for dual thread) could allow 16 streams, and 600 
Mpix/s would allow 10 or 20 (subject to things like memory-bandwidth and 
similar, or the costs of "actually doing something" with the video frames).


generally, this isn't so much for playing video streams though, as much 
as things like wanting the ability to have multiple 1024x1024 
video-mapped textures on-screen at once and not bogging down the 
framerate and similar.

though, yes, 256x256 or 512x512 is a little more conservative (and a 
little closer to what I more typically use).

(trying to use 8 or 16 1024x1024 video-maps at once would be a little 
closer to being a stress-test or similar...).


a faster decoder does lead to less of a performance hit in the renderer 
though (and, thus, better framerates).



> I also coded a super fast code which runs on a pentium III 450 mhz or
> so... it uses some kind of horizontal/vertical compression and I think I
> even tried diagonal.
>
> It's not bad.. it can compress toony videos pretty well.
>
> So far I have not released any codec to the public though... I don't see
> why I should do that.
>

toony images are easy to compress.


better is when it can do an ok job compressing live-action TV shows, and 
fast enough to allow using it for real-time video capture, and can play 
back content at fairly high resolutions (or decode multiple high-res 
streams at once in real-time).



>> I invented my own variation on it. I call it "Bubble to Front"
>>
>> I uses something like 1 or 2 operations per transformation instead of
>> 128 on average for move to front or so.
>>
>> I am willing to sell the algorithm for 10.000 dollars ?! ;) :)
>>
>
> "
> errm, I already know of several variants of these...
> "
>
> Hmm I am not aware of any existing ones... I have seen many try.
>
> I would be curious to see if you can re-produce it ;)
>

probably by having a rover into an array of items, then by updating the 
rover and doing a swap. conceptually, the whole value-space rotates, 
with values being pulled to the front of the list.

this may be less effective if predictability is high, but this can be 
handled specially (doing direct swaps in certain cases instead of 
rotating the list).

[toc] | [prev] | [next] | [standalone]

#18071

"BGB"  wrote in message news:l0tmvj$5ac$1@news.albasani.net...

On 9/12/2013 8:31 AM, Jasen Betts wrote:
> On 2013-09-12, Skybuck Flying <Windows7IsOK@DreamPC2006.com> wrote:
>> Hello,
>>
>> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
>>
>> It's always funny to see how some programmers believe that Huffman cannot 
>> be
>> decoded in parallel.
>>
>> I believe it is possible to decode (static) huffman in parallel.
>>
>> However as I wrote in the past I want a million dollars for it ! ;)
>>
>> Perhaps nobody is going to pay 1 million dollars all by him/herself so
>> instead I am going to give crowd funding a try ! ;)
>
> It's absolutely possible to decode static huffman in parallel
> just start decoders off at all different offsets and when you reach
> that part reject the output that was computed starting with the wrong 
> offset.
>
> It may pe possible to imply the correct offet by examineing the
> bitstream, but this is not possible for all huffman tables, and is a
> gross waste of resources.
>
> If you want fast static huffman decoding, use an FPGA, they are
> ideally suited.
>


for one of my ideas for a video codec, I had considered the possibility
of starting each row of macroblocks on a byte-aligned address (and with
a zeroed DC predictor), which could potentially allow a decoder to have
the ability to decode each row of macroblocks in a separate thread
(as-needed).

haven't actually done this though...


Skybuck:

Why don't you stick to something like basket weaving, it's harder to fuck up 
and no serious consequences.  I don't think you have the brains to 
successfully do the technical stuff.

Shaun

[toc] | [prev] | [next] | [standalone]

#18076

Lol,

Well indiegogo seems to be a bust.

The best idea ever was removed. (Bitcoin Bussiness Patent, apperently it was 
not allowed.)

Also logging in problems weird.

Unfortunately kickstarter is not yet available in The Netherlands.

Also kickstarter also had problems... could not complete the last phase of 
the project.

Both websites very slow unfortunately. Indiegogo performed a little bit 
better.

When kickstarter is available in The Netherlands, you can invest safely in 
my projects.

Hopefully by that time it will either work better or my PC be new/faster ;)

Cause if it dont work out you get your money back.

If it does work out... everybody be happy ! ;) =D

[toc] | [prev] | [next] | [standalone]

#18075

On 12.09.2013 06:37, Skybuck Flying wrote:
> Hello,
>
> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
>
> It's always funny to see how some programmers believe that Huffman
> cannot be decoded in parallel.
>
> I believe it is possible to decode (static) huffman in parallel.

"It depends". Either, you add synchronization markers (or unique 
symbols) to restart from. In such a case, you can launch several 
decoders at once, but first need to find suitable anchor-points to start 
decoding from. Or, you "hope" that Huffman self-synchronizes, which it 
often does, and try to eliminate bogus output later.

In either case, you will often find that the price for detecting the 
sync markers or the fixup is not worth running the Huffman in parallel. 
Essentially, the pre-scan or post-fixup is of approximately the same 
complexity as the Huffman itself (i.e. "simple"), so it's usually not 
worth bothering. For that to work, the blocks should relatively large, 
and the Huffman resync positions relatively regular so you can avoid 
complicated scanning. This again causes encoder complexity to go up 
somewhat.

Thus, there is no "general receipt" that works in all cases. It's very 
problem dependent whether such a thing makes sense or not.

Greetings,
	Thomas

[toc] | [prev] | [next] | [standalone]

#18415

On Wednesday, September 11, 2013 11:37:19 PM UTC-5, Skybuck Flying wrote:
> Hello,
> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)

Can I suggest you fund you psychotropc needs first.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.arch

csiph-web