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

Groups > comp.compression > #3162 > unrolled thread

How many additions in fastest DCT ?

Back to article view | Back to comp.compression

Contents

  How many additions in fastest DCT ? James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-14 08:54 +0000
    Re: How many additions in fastest DCT ? Thomas Richter <thor@math.tu-berlin.de> - 2015-09-14 11:30 +0200
      Re: How many additions in fastest DCT ? James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-14 11:40 +0000
        Re: How many additions in fastest DCT ? jdallen2000@yahoo.com - 2015-09-14 05:53 -0700
        Re: How many additions in fastest DCT ? Thomas Richter <thor@math.tu-berlin.de> - 2015-09-14 21:29 +0200
          Re: How many additions in fastest DCT ? James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-15 07:08 +0000
            Re: How many additions in fastest DCT ? Thomas Richter <thor@math.tu-berlin.de> - 2015-09-15 11:08 +0200
            Re: How many additions in fastest DCT ? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-15 14:17 +0000
      Re: How many additions in fastest DCT ? BGB <cr88192@hotmail.com> - 2015-09-14 10:05 -0500
        Re: How many additions in fastest DCT ? James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-15 07:22 +0000
          Re: How many additions in fastest DCT ? Thomas Richter <thor@math.tu-berlin.de> - 2015-09-15 11:14 +0200
            Re: How many additions in fastest DCT ? BGB <cr88192@hotmail.com> - 2015-09-15 09:16 -0500
          Re: How many additions in fastest DCT ? BGB <cr88192@hotmail.com> - 2015-09-15 08:41 -0500
      Re: How many additions in fastest DCT ? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-14 20:59 +0000
    Re: How many additions in fastest DCT ? Phil Carmody <pc+usenet@asdf.org> - 2015-11-18 21:51 +0200

#3162 — How many additions in fastest DCT ?

Reminiscing, I recall a little "nitpick" from almost 25 years ago, and 
got curious.  I wonder if anyone here is involved enough in DCT fast 
procedures to research something for me.

In the 1980's and early 1990's there were many articles written on fast 
procedures to calculate the Discrete Cosine Transform; I got involved 
with that.  (Please note I'm speaking of pure DCT, not any approximation 
or such.)  Jpeg's DCT is probably considered an antique by now and, 
anyway, the point of this post applies only to DCT_16 or higher, so is 
irrelevant to Jpeg, but I'm still curious.

There were at least three different computational procedures which 
happened to yield the same computational cost for UDCT_N when N was a 
power of two.  Letting n = log2(N), the costs were
   #mult = (1/2) N n - (1/2) N - 1   multiplications
   #add  = (3/2) N n - (3/2) N + 3   additions/subtractions

I stumbled on a slight simplification that improved the cost to
   #mult = (1/2) N n - (1/2) N - 1   multiplications (same as before)
   #add  = (3/2) N n - (5/3) N + 4 +- 1/3   additions/subtractions
(By +- 1/3, of course I mean ą1/3, whichever makes the expression an 
integer.)

You can see that #add is the same in both expressions when N=4 or N=8.
But two adds are saved when N=16, ten adds when N=64, and so on.  These 
savings are trivial of course, but still relevant if there's some 
Guiness Book entry for fast DCT procedures!  :-)

Can someone check the literature and see what #add is shown for "the 
fastest DCT procedure"?

I mentioned my improvement in two journal aricles, but they took the 
form of footnotes or parentheses. (The Figure in 
http://electronicimaging.spiedigitallibrary.org/article.aspx?articleid=
1097188 did depict the improved cost.)

James Dow Allen

[toc] | [next] | [standalone]

#3163

On 14.09.2015 10:54, James Dow Allen wrote:
> Reminiscing, I recall a little "nitpick" from almost 25 years ago, and 
> got curious.  I wonder if anyone here is involved enough in DCT fast 
> procedures to research something for me.
> 
> In the 1980's and early 1990's there were many articles written on fast 
> procedures to calculate the Discrete Cosine Transform; I got involved 
> with that.  (Please note I'm speaking of pure DCT, not any approximation 
> or such.)  Jpeg's DCT is probably considered an antique by now and, 
> anyway, the point of this post applies only to DCT_16 or higher, so is 
> irrelevant to Jpeg, but I'm still curious.

Question here is: What do you mean by a "pure DCT"? After all, all
(actually, almost all) DCT implementations are approximations because
they use limited precision arithmetic. There are some works that
implement the DCT as a field-extension and hence are mathematically
precise in that sense, except that the output samples are then
necessarily vectorial and not scalar (i.e. 8 vectorial outputs instead
of eight scalar outputs for a DCT of a length 8).

If you're looking specifically at 8x8 DCTs, the (probably) most
elaborate research in finding least-complex DCTs with given error bounds
is by Yurij Reznik and and Arianne Hinds. You'll find the paper on
Yurij's side:

http://www.reznik.org/software.html

There is some follow-up work for larger DCTs Yurij prepared in the
following years, again presented at the SPIE. Unfortunately, I only have
the paper versions (SPIE paper versions are cheaper than the CD
versions), but I'm sure Yurij could help you here and send you copies if
you're interested. Send greetings as well, we know each other.

> Can someone check the literature and see what #add is shown for "the 
> fastest DCT procedure"?

The lowest complexity DCT in Yurij's extensive search (yes, they really
scanned the whole parameter space as I understand it) is 44adds and 20
shifts for the 1-D DCT of size 8. That's called Z0a in his paper. I
believe this is what got accepted by MPEG as MPEG-C standard.

Anyhow, for this type of question Yurij and Adrianne are really the
right people to talk to.

Greetings,
	Thomas

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

#3165

Thomas Richter <thor@math.tu-berlin.de> might have writ, in
news:mt644c$h1d$1@news2.informatik.uni-stuttgart.de: 
> Question here is: What do you mean by a "pure DCT"? After all, all
> (actually, almost all) DCT implementations are approximations because
> they use limited precision arithmetic....

I won't try to define what I mean by "pure" rigorously, except to
ask you to imagine, if you will, 1000-bit precision; in which it would 
take a huge number of additions and shifts to replace a multiply by the 
irrational DCT values.  (If you prefer, you can consider "conceptual" 
multiplications.)

Obviously I'm very aware of how to simplify arithmetic for finite
precision, and the practicality of doing so.  :-)  But that has nothing
to do with my question.

As I tried to stress in OP, I'm asking about a purely theoretical 
"Guiness record."  Don't imagine my question is practical!

> If you're looking specifically at 8x8 DCTs, the (probably) most
> elaborate research ...
> The lowest complexity DCT in Yurij's extensive search (yes, they
> really scanned the whole parameter space as I understand it) is 44adds
> and 20 shifts for the 1-D DCT of size 8.

I already mentioned that DCT-8 is irrelevant to my question.
And since Yurij refers to "shifts" it is obvious he is not addressing 
the "pure DCT" question I'm asking about.

James Dow Allen

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

#3166

Perhaps I can explain the distinction better.

(1) There are different ways to compute DCT with a network of simple additions and multiplications.
(2) Given such an arithmetic network with finite precision, there are ways to replace the multiplications with adds and shifts.

Both problems are interesting.  Today I'm asking about (1).  (2) is irrelevant to my question.

James

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

#3168

Am 14.09.2015 um 13:40 schrieb James Dow Allen:
> Thomas Richter <thor@math.tu-berlin.de> might have writ, in
> news:mt644c$h1d$1@news2.informatik.uni-stuttgart.de:
>> Question here is: What do you mean by a "pure DCT"? After all, all
>> (actually, almost all) DCT implementations are approximations because
>> they use limited precision arithmetic....
>
> I won't try to define what I mean by "pure" rigorously, except to
> ask you to imagine, if you will, 1000-bit precision; in which it would
> take a huge number of additions and shifts to replace a multiply by the
> irrational DCT values.  (If you prefer, you can consider "conceptual"
> multiplications.)
>
So I guess you mean the DCT represented as an adder/multiplier network, 
where each coefficient in the network is a (almost always irrational) 
number, i.e. you ask for a mathematical rather than implementation question?

Honestly, I don't know. It's also a strange question to ask since you 
usually want (or wanted, back then) to minimize the number of 
*multiplications* and not the number of *additions*.

Also, the question is then what "fastest" means in that sense. Depth of 
the network? Number of nodes? Weighted number of nodes?

You probably know all the classics. Loeffler factorization and the AAN 
factorization. If I counted correctly, the former requires 28 additions 
(or subtractions) and the latter 29 (but less multiplications), for a 
DCT of length 8. Whether that's the minimum I don't know, i.e. whether 
you can probably increase the number of multiplications for lowering the 
number of additions.

Maybe somebody in comp.dsp knows the answer, just to give at least some 
piece of useful information...

Greetings,
	Thomas

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

#3170

I didn't really expect anyone here to come up with the answer ... but 
I'm surprised my question is so hard to understand.  :-)

First, by DCT I mean DCT-II (the transform used in Jpeg compression) or 
the rather similar DCT-III (the transform used in Jpeg decompression).  
These are built from cascades of a symmetric DCT-IV transform.  The 
literature circa 1990 was pretty clear about all of this; I suspect this 
was all treated as a "done deal" about then and the literature became 
obsolescent.

Let's now dispose of the questions I did NOT ask.

I think I know a little about reducing computational cost. In the paper
http://www.sciencedirect.com/science/article/pii/0923596594000476
I show a software implementation of (a transform closely related to) 
UDCT-III_8 with 38 additions, 14 shifts and zero multiplications.
(Sorry this is pay-per-view.  If anyone can get it for free from a 
library, you have my permission to place a free version on the 'Net!  Or 
send it to me and I will.  I have a print version, but no longer the 
LaTeX source.)

> The lowest complexity DCT in Yurij's extensive search (yes, they 
> really scanned the whole parameter space as I understand it) is 44adds 
> and 20 shifts for the 1-D DCT of size 8.

A higher cost than mine!  Perhaps the difference derives from this:
The approximation I used is close enough to DCT to permit use with 8-bit 
Jpeg but accumulated error may pose a problem with Mpeg.  As Mpeg 
researchers told me when I presented my approach, it was too bad that 
the standard's concrete was already hardening when I got involved.

By the way, as the linked article showed, I didn't use 38 adds and 14 
shifts on 32-bit processors -- I used just 20 adds and 15 shifts and 
zero multiplications.

> Honestly, I don't know. It's also a strange question to ask since you 
> usually want (or wanted, back then) to minimize the number of 
> *multiplications* and not the number of *additions*.

We can debate whether I'm strange.  But I think I've disposed of your 
strange need to tell me what I "usually wanted to do back then."  :-)

Anyway ... Returning to my actual question:  In the literature circa 
1990 there were journal articles presenting computational methods for 
computing DCT-N EXACTLY when N was a power of two.  It was almost like a 
contest to reduce the number of multiplications and additions.

By the way, the additonal savings I found (for computing EXACT* DCT, 
i.e. without approximating irrational multipliers) show up as 
MULTIPLICATIONS not additions.  However, they turn into additions when 
the MINIMAL cost is quoted because of "Wang's trick."  As explained in 
linked paper above, Wang's trick interferes with practical 
implementations.

The lack of importance I felt my little discovery deserved is indicated 
by the fact that in linked paper, it's only mentioned in a footnote.  
Since, however IT DOES LOWER THE MINIMAL AMOUNT OF ARITHMETIC for a 
well-defined arithmetic problem, whose best costs were quoted in several 
journal articles, I was curious whether my improvement had made its way 
into other literature.  I thought someone with good skills at searching 
IEEE databases might be able to satisfy my curiosity.  That's all.

> If I counted correctly, the former requires 28 additions 
> (or subtractions) and the latter 29 (but less multiplications), for a 
> DCT of length 8.

Again, it's arbitrary N=2^n that becomes interesting.  The savings I 
describe don't even kick in until N=16.

James Dow Allen

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

#3172

On 15.09.2015 09:08, James Dow Allen wrote:
> I didn't really expect anyone here to come up with the answer ... but 
> I'm surprised my question is so hard to understand.  :-)
> 
> First, by DCT I mean DCT-II (the transform used in Jpeg compression) or 
> the rather similar DCT-III (the transform used in Jpeg decompression).  
> These are built from cascades of a symmetric DCT-IV transform.  The 
> literature circa 1990 was pretty clear about all of this; I suspect this 
> was all treated as a "done deal" about then and the literature became 
> obsolescent.

That part, however, was pretty clear to begin with. (-: The DCT II is
still in use, though in an approximate way as a transformation in
MPEG/HEVC, along with a DST if the signal to be transformed is generated
by predicting from one edge inwards into the block. In this particular
case, the signal is highly non-symmetric, and that seems to appeal more
to the DST, even though this is much of a handwaving argument.

> 
> Let's now dispose of the questions I did NOT ask.
> 
> I think I know a little about reducing computational cost. In the paper
> http://www.sciencedirect.com/science/article/pii/0923596594000476
> I show a software implementation of (a transform closely related to) 
> UDCT-III_8 with 38 additions, 14 shifts and zero multiplications.
> (Sorry this is pay-per-view.  If anyone can get it for free from a 
> library, you have my permission to place a free version on the 'Net!  Or 
> send it to me and I will.  I have a print version, but no longer the 
> LaTeX source.)

We do have access to image communications, and yes, I have the paper. My
mail address works. I haven't read it yet, though.

> A higher cost than mine!  Perhaps the difference derives from this:
> The approximation I used is close enough to DCT to permit use with 8-bit 
> Jpeg but accumulated error may pose a problem with Mpeg.  As Mpeg 
> researchers told me when I presented my approach, it was too bad that 
> the standard's concrete was already hardening when I got involved.

I guess it's probably best to look into the error bounds Yurij gave.
It's available on his website I provided a link for. There are a couple
of lower complexity alternatives he gave, though each of which had a
couple of flaws; some created drift, and some had a non-symmetric error.
Whether any of those given is yours I do not know. It's a well written
paper, so I can only recommend reading it.

>> Honestly, I don't know. It's also a strange question to ask since you 
>> usually want (or wanted, back then) to minimize the number of 
>> *multiplications* and not the number of *additions*.
> 
> We can debate whether I'm strange.  But I think I've disposed of your 
> strange need to tell me what I "usually wanted to do back then."  :-)

Arguably, but then again, nowadays you really care about integer
approximations, so the type of research Yurij and Adrianne published.

For JPEG, we looked into those, but I believe we finally picked a fixed
point approximation of the Loeffler factorization and an
integer-to-integer DCT based (mostly) on the works by Plonka and Tasche.
The latter has the advantage that it is 1:1 *and* compatible (no
scaling) to the JPEG DCT, though as with all integer approximations, its
filters have a certain "leak" that's unavoidable.

> Anyway ... Returning to my actual question:  In the literature circa 
> 1990 there were journal articles presenting computational methods for 
> computing DCT-N EXACTLY when N was a power of two.  It was almost like a 
> contest to reduce the number of multiplications and additions.
> 
> By the way, the additonal savings I found (for computing EXACT* DCT, 
> i.e. without approximating irrational multipliers) show up as 
> MULTIPLICATIONS not additions.  However, they turn into additions when 
> the MINIMAL cost is quoted because of "Wang's trick."  As explained in 
> linked paper above, Wang's trick interferes with practical 
> implementations.

This predates the works of Loeffler and the AAN paper, so the latter are
likely practical implementations of the above for the dct size of eight.

> The lack of importance I felt my little discovery deserved is indicated 
> by the fact that in linked paper, it's only mentioned in a footnote.  
> Since, however IT DOES LOWER THE MINIMAL AMOUNT OF ARITHMETIC for a 
> well-defined arithmetic problem, whose best costs were quoted in several 
> journal articles, I was curious whether my improvement had made its way 
> into other literature.  I thought someone with good skills at searching 
> IEEE databases might be able to satisfy my curiosity.  That's all.

I would guess that the problem moved a bit. JPEG is stuck with its 8x8
DCT, though MPEG put some work into finding DCT approximations with
integer coefficients, though they allow "scaled DCTs", i.e. the output
of the DCT may require additional frequency-based scales (as in the AAN
work) that can be absorbed into the quantizer. The reason to restrict to
integer coefficients is simply to reduce complexity by avoiding the FPU
right away by the design. In JPEG, we do not care so much, though for
JPEG XT part 8 we needed a fully defined DCT, and as such I wanted to
avoid that we also need to define a scaling procedure for the
quantization coefficients, so that's why we stuck with Loeffler. This is
unlike the AAN DCT an unscaled DCT, i.e. the matrix is orthogonal.

>> If I counted correctly, the former requires 28 additions 
>> (or subtractions) and the latter 29 (but less multiplications), for a 
>> DCT of length 8.
> 
> Again, it's arbitrary N=2^n that becomes interesting.  The savings I 
> describe don't even kick in until N=16.

That's then more a use case for MPEG which goes up to N=32 in HEVC if I
remember correctly. I believe they even want to go higher for the next
initiative.

Greetings,
	Thomas

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

#3175

James Dow Allen <gmail@jamesdowallen.nospam> wrote:
> I didn't really expect anyone here to come up with the answer ... but 
> I'm surprised my question is so hard to understand.  :-)
 
(snip)

> Let's now dispose of the questions I did NOT ask.
 
(snip)

>> The lowest complexity DCT in Yurij's extensive search (yes, they 
>> really scanned the whole parameter space as I understand it) is 44adds 
>> and 20 shifts for the 1-D DCT of size 8.
 
> A higher cost than mine!  Perhaps the difference derives from this:
> The approximation I used is close enough to DCT to permit use with 8-bit 
> Jpeg but accumulated error may pose a problem with Mpeg.  As Mpeg 
> researchers told me when I presented my approach, it was too bad that 
> the standard's concrete was already hardening when I got involved.

If you are really looking for low computational cost, have you looked
at the ICT, which was specifically designed for that? 

http://ipnpr.jpl.nasa.gov/progress_report/42-115/115j.pdf

Specifically, if your processor only does add and shift, such
as the CDP1602, but you have a much faster processor for the
inverse transform. 

-- glen

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

#3167

On 9/14/2015 4:30 AM, Thomas Richter wrote:
> On 14.09.2015 10:54, James Dow Allen wrote:
>> Reminiscing, I recall a little "nitpick" from almost 25 years ago, and
>> got curious.  I wonder if anyone here is involved enough in DCT fast
>> procedures to research something for me.
>>
>> In the 1980's and early 1990's there were many articles written on fast
>> procedures to calculate the Discrete Cosine Transform; I got involved
>> with that.  (Please note I'm speaking of pure DCT, not any approximation
>> or such.)  Jpeg's DCT is probably considered an antique by now and,
>> anyway, the point of this post applies only to DCT_16 or higher, so is
>> irrelevant to Jpeg, but I'm still curious.
>
> Question here is: What do you mean by a "pure DCT"? After all, all
> (actually, almost all) DCT implementations are approximations because
> they use limited precision arithmetic. There are some works that
> implement the DCT as a field-extension and hence are mathematically
> precise in that sense, except that the output samples are then
> necessarily vectorial and not scalar (i.e. 8 vectorial outputs instead
> of eight scalar outputs for a DCT of a length 8).
>
> If you're looking specifically at 8x8 DCTs, the (probably) most
> elaborate research in finding least-complex DCTs with given error bounds
> is by Yurij Reznik and and Arianne Hinds. You'll find the paper on
> Yurij's side:
>
> http://www.reznik.org/software.html
>
> There is some follow-up work for larger DCTs Yurij prepared in the
> following years, again presented at the SPIE. Unfortunately, I only have
> the paper versions (SPIE paper versions are cheaper than the CD
> versions), but I'm sure Yurij could help you here and send you copies if
> you're interested. Send greetings as well, we know each other.
>
>> Can someone check the literature and see what #add is shown for "the
>> fastest DCT procedure"?
>
> The lowest complexity DCT in Yurij's extensive search (yes, they really
> scanned the whole parameter space as I understand it) is 44adds and 20
> shifts for the 1-D DCT of size 8. That's called Z0a in his paper. I
> believe this is what got accepted by MPEG as MPEG-C standard.
>
> Anyhow, for this type of question Yurij and Adrianne are really the
> right people to talk to.
>

curious, I have both fewer adds/subtracts, as well as less shifts.

though, I am guessing (based on the somewhat larger number of shifts), 
that likely he eliminated the use of a bunch of multiplies, which could 
be interesting (multiplies are moderately more expensive than add/sub or 
shifts, say, taking 4 cycles rather than 1/3).


though, practically, most of my fiddling with DCT-based designs, tend to 
have a lot more time going into the pixel/colorspace transforms and 
VLC/bitstream code.


my recent experiments have thus been fairly unimpressive (ultimately a 
bit slower than what I had been able to get from a JPEG coder), while 
they optimized the colorspace and block-transform (by merging them into 
a single composite entity), they seemed to suffer pretty hard in the 
bitstream/VLC backend, leading to a coder which has its execution time 
dominated by the VLC and entropy coding...

I suspect this is partly because Rice is a little harder to optimize 
than Huffman, and there were a larger number of logical symbols (due 
partly to the funkiness of Rice coding).

though, it would be better more if minimal code size were the goal, as 
one can leave out pretty much all the stuff for Huffman coding (though, 
with JPEG-like designs, you can also use fixed Huffman tables to similar 
effect, so the gain is a bit smaller).


I am thinking now possibly fixed 8x8+4x4 DCT or WHT and static Huffman 
could be faster.

or such...

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

#3171

BGB <cr88192@hotmail.com> might have writ, in news:mt6o1q$hc1$1
@news.albasani.net:

> bitstream/VLC backend, leading to a coder which has its execution time 
> dominated by the VLC and entropy coding...

The ballpark time allocation for my high-speed Jpeg decompressor IIRC was 
about 52% color-space conversion and replication, 35% DCT, 12% Huffman.  
The Huffman decoder was driven by a largish table.

I've always enjoyed micro-optimizing code and came up with assembly 
language routines for both Intel-386 and Motorola 68020. Because of my 
fetish for extreme micro-optimzation, I ended up with different approaches 
for the two processors!  (A main difference is how those two machines 
handle shift counts greater than 31.)  Unfortunately I no longer have the 
assembly code, but I'll send you a C-language version of my Huffman decoder 
if you wish.

James

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

#3173

On 15.09.2015 09:22, James Dow Allen wrote:
> BGB <cr88192@hotmail.com> might have writ, in news:mt6o1q$hc1$1
> @news.albasani.net:
> 
>> bitstream/VLC backend, leading to a coder which has its execution time 
>> dominated by the VLC and entropy coding...
> 
> The ballpark time allocation for my high-speed Jpeg decompressor IIRC was 
> about 52% color-space conversion and replication, 35% DCT, 12% Huffman.  
> The Huffman decoder was driven by a largish table.

That's a rather typical Huffman design. You usually need one shift (move
the MSB in place), one table lookup for the number of bits, one table
lookup for the symbol, and an adjustment of the bit pointer on the input
stream, plus pulling in more bits if necessary.

In the JPEG XT reference software, I actually used two tables, one for
symbols that require less than eight bits and another for longer
symbols. It turned out that one combined table of size 64K is slower
simply because it breaks cache-locality of the algorithm, and the longer
symbols are rare by the very design, so it did not hurt to run through a
second lookup.

But then, that's all C++ and not assembly. I wrote a lot of 68K assembly
back then, but since this (rather nice) architecture died out, and the
intels are pretty unorthogonal and faster anyhow, I never bothered with
assembly anymore.

Greetings,
	Thomas

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

#3176

On 9/15/2015 4:14 AM, Thomas Richter wrote:
> On 15.09.2015 09:22, James Dow Allen wrote:
>> BGB <cr88192@hotmail.com> might have writ, in news:mt6o1q$hc1$1
>> @news.albasani.net:
>>
>>> bitstream/VLC backend, leading to a coder which has its execution time
>>> dominated by the VLC and entropy coding...
>>
>> The ballpark time allocation for my high-speed Jpeg decompressor IIRC was
>> about 52% color-space conversion and replication, 35% DCT, 12% Huffman.
>> The Huffman decoder was driven by a largish table.
>
> That's a rather typical Huffman design. You usually need one shift (move
> the MSB in place), one table lookup for the number of bits, one table
> lookup for the symbol, and an adjustment of the bit pointer on the input
> stream, plus pulling in more bits if necessary.
>

yes, this is basically what mine do, at least for symbols <=8 bits.

longer symbols need a search, but this is infrequent, and generally 
faster than using a larger table.


> In the JPEG XT reference software, I actually used two tables, one for
> symbols that require less than eight bits and another for longer
> symbols. It turned out that one combined table of size 64K is slower
> simply because it breaks cache-locality of the algorithm, and the longer
> symbols are rare by the very design, so it did not hurt to run through a
> second lookup.
>

yes, this has also been my experience.

making everything fit in cache is important if one wants acceptable 
codec speed.


> But then, that's all C++ and not assembly. I wrote a lot of 68K assembly
> back then, but since this (rather nice) architecture died out, and the
> intels are pretty unorthogonal and faster anyhow, I never bothered with
> assembly anymore.
>

yeah.

I am mostly doing plain C.

ASM doesn't usually buy enough speed-wise to make it worthwhile except 
in very specific use-cases (such as fast inline functions for doing 
specific operations).

other cases are for when a particular operation can't be readily done in 
C (mostly funkiness with the C ABI, like implementing closures or a 
decent 'apply' operation for function-pointers).

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

#3174

On 9/15/2015 2:22 AM, James Dow Allen wrote:
> BGB <cr88192@hotmail.com> might have writ, in news:mt6o1q$hc1$1
> @news.albasani.net:
>
>> bitstream/VLC backend, leading to a coder which has its execution time
>> dominated by the VLC and entropy coding...
>
> The ballpark time allocation for my high-speed Jpeg decompressor IIRC was
> about 52% color-space conversion and replication, 35% DCT, 12% Huffman.
> The Huffman decoder was driven by a largish table.
>

in my JPEG decoders, colorspace conversion and Huffman/VLC tended to 
dominate, with DCT in 3rd place.

on my PC, I have gotten JPEG decoders up to around 90 Mpix/sec, which 
falls just short of XviD, and is notably faster than Theora (I was 
generally testing its use for MJPEG coded video-clips).

if multiple decoding threads are used, then JPEG decoding can go at 
around 300 Mpix/sec.


I have yet to beat out XviD on a performance-front with DCT based 
designs (they seem to have some sort of "secret sauce" that makes its 
decoding fast, but only if quality isn't maxed out, where its decode 
speed seems to go in the toilet).

my VQ based designs tends to be somewhat faster though.

though worth noting is that my PC isn't particularly new or fast.



but, I was writing about was this experimental design:
http://cr88192.mooo.com:8080/wiki/index.php/BTIC2D

where performance suffers pretty hard in the entropy/VLC step (which is 
based on Adaptive-Rice codes), causing it to dominate the overall 
performance.


I suspect it is due to several factors:
   need to write out zero-runs and values as separate symbols;
   decoding a symbol requires multiple bitstream reads (*);
   ...

it also seems that zero-runs tend to be much rarer and shorter than with 
larger blocks.

*: currently, one read per 8 bits of Q-value, and another read for the 
N-bit suffix.

moving to an 8x8 block and Huffman coding should hopefully permit higher 
speeds.

however, Huffman complicates use of incremental coding and sending spans 
of coded blocks via UDP. this is how video streaming works in my robot 
projects, the video stream is basically a mass of UDP packets hitting 
the receiver and being decoded/displayed as they arrive, provided they 
have a higher frame-number than the blocks currently displayed in that 
location.

generally, you want each UDP datagram to be independent of the preceding 
packets. with Huffman coding, there is the requirement that the decoder 
also have the appropriate table, which is a problem if the datagram with 
the table is dropped or arrives later than the image datagrams.

though, granted, one could use primarily fixed tables to sidestep this 
issue.


> I've always enjoyed micro-optimizing code and came up with assembly
> language routines for both Intel-386 and Motorola 68020. Because of my
> fetish for extreme micro-optimzation, I ended up with different approaches
> for the two processors!  (A main difference is how those two machines
> handle shift counts greater than 31.)  Unfortunately I no longer have the
> assembly code, but I'll send you a C-language version of my Huffman decoder
> if you wish.
>

my Huffman decoder is usually ok, as can be noted, I was having 
performance problems with a Rice-coding based design, not a Huffman 
based design.


generally it works like this:
peek 16 bits;
use high 8 bits to index a table;
if Length<=8:
   skip L bits and return the symbol;
otherwise:
   iterate the symbols with this prefix;
   skip L bits and return matching symbol.

while a 16 bit table could do it all at once, my experience is that 12 
and 16 bit tables tend to make performance suffer (I suspect due to too 
much cache pressure).

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

#3169

Thomas Richter <thor@math.tu-berlin.de> wrote:
> On 14.09.2015 10:54, James Dow Allen wrote:
>> Reminiscing, I recall a little "nitpick" from almost 25 years ago, and 
>> got curious.  I wonder if anyone here is involved enough in DCT fast 
>> procedures to research something for me.
 
(snip)

> Question here is: What do you mean by a "pure DCT"? After all, all
> (actually, almost all) DCT implementations are approximations because
> they use limited precision arithmetic. There are some works that
> implement the DCT as a field-extension and hence are mathematically
> precise in that sense, except that the output samples are then
> necessarily vectorial and not scalar (i.e. 8 vectorial outputs instead
> of eight scalar outputs for a DCT of a length 8).

Well, first of all, "pure DCT" would tend to imply the O(N**2)
version, instead of the FFT derived one that would be called FCT
that is O(N logN). 

Once you get to the FCT form, then there are more questions.
Fixed or floating point, and how many bits? If you do fixed point,
and add one bit for each (power of two) stage, there is no precision
loss, though there might be rounding. Easy in hardware, not always
so easy in software.

But in the early days, add was enough faster than multiply that
there wasn't so much reason to count add. As multiply gets faster,
add is more important.  But then again, on many processors multiply
(and maybe add) times depend on the operands. Some values mutliply
faster than others.
 
> If you're looking specifically at 8x8 DCTs, the (probably) most
> elaborate research in finding least-complex DCTs with given error bounds
> is by Yurij Reznik and and Arianne Hinds. You'll find the paper on
> Yurij's side:
 
> http://www.reznik.org/software.html

-- glen

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

#3279

James Dow Allen <gmail@jamesdowallen.nospam> writes:
...
> Guiness Book entry for fast DCT procedures!  :-)

Not sure about DCTs, but the DFT has been shaken up in the last decade.
James Buskirk reinvented the FFT by shifting the scaling around
and effectively building it in terms of tan rather than sin/cos.
Dan Bernstein wrote an analysis of this which is quite approachable
  http://cr.yp.to/papers.html#tangentfft

Maybe an equivalent exists for DCT?
 
Phil
-- 
A well regulated militia, being necessary to the security of a free state,
the right of the people to keep and bear arms, shall be well regulated.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web