[FFmpeg-devel] [PATCH] G.729 Fixed-codebook vector decoding

[Vladimir Voroshilov]

2009/6/28 Michael Niedermayer <michaelni at gmx.at>:
> On Sat, Jun 27, 2009 at 09:27:23AM +0700, Vladimir Voroshilov wrote:
>> 2009/6/27 Michael Niedermayer <michaelni at gmx.at>:
>> > On Sat, Jun 27, 2009 at 02:05:27AM +0700, Vladimir Voroshilov wrote:
>> >> Memset is required, since vector should contain only several non-zero pulses
>> >
>> > if the thing is sparse, memset could maybe be replaced by just setting
>> > the non zero values to zero, in that sense many operationson on sparse
>> > vectors can be done more efficiently than working on an array of zeros
>> > with one non zero value, which if it applies here means you have to
>> > rewrite the related code to be more efficient
>>
>> Hmm..
>>
>> Does you mean "invert" vector (replace zero with non-zero and vice versa) ?
>> What values whould contain non-zero parts in your suggestion?
>>
>> Here is how i uderstand fixed-codebook vector generation.
>>
>> Fixed-codebook vector defines where four (or three, depends on mode)
>> pulses of sound are placed in
>> current frame (which is zero at this stage). Afaik, fixed-codebook
>> vector defines signal which in "new"
>> in current frame and is not continuation oprevious frame's sound.
>> Routine sets 1 at this positions, setting all other to 0.
>>
>> "1" related to pulse of sound, "0" means silence.
>>
>> Later this vector will be weightly summed with excitation signal.
>>
>> Thus, either your suggestion is deep math or heavy optimization which
>> i can't understand.
>
> adding a sparse vector with 4 non zero pulses to another vector is a O(1)
> operation, your code needs O(n) that is not acceptable. (that is based on
> your description above)
>
> Its simply that you add n-4 values with n-4 zeros and 4 values with
> 4 non zero values, thats not deep math

Ok. Now i see what is the battle for. O(1) is obviously better even for me.
But, i'm afraid O(1) implementation is much complex task.

Well. Fixed-vector (called fc and fc_v in severral places) decribes contribution
of non-periodic signal introduced in current frame.

Initially it contains few (fixed number of, depending on mode)
non-zero pulses and is a sparse vector.
This pulses generated  fixed-codebook indexes and signs. The latter
either are decoded from frame or
initialized with random values in case of frame erasure.

Working with sparse vector at this stage is clean for me (small array
of non-zero values' indexes/signs only, as i see).

But already applying simple harmonic filter:

for(i=pitch_delay; i<subframe_size; i++)
fc[i]+=gain_pitch * fc[i-pitch_delay]

becames much complex task for such sparse vector.

Later fixed-codebook vector is used for decoding gain_code.
There is scalarproduct_int16, which is called with fc_v. Of course i
can compute scalarproduct
on sparse vector too, but mmx optiomization can not be used.

According to above, i see only two troubles (for me):
1. Complex code with harmonic filter. Sparse case will require either
"if"s or some sorting of indexes.
This is because accumulation is proceeded in-place and each step of
loop affects next elements of array.
2. Inpossible reusage of existing MMX optiomizations. Perhaps
calculation of scalarproduct can be merged with harmonic filter.

How to implement "1" i didn't yet know and will be thankful for advice.

-- 
Regards,
Vladimir Voroshilov     mailto:voroshil at gmail.com
JID: voroshil at gmail.com, voroshil at jabber.ru
ICQ: 95587719