21 |
* along with this program ; if not, write to the Free Software |
* along with this program ; if not, write to the Free Software |
22 |
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
23 |
* |
* |
24 |
* $Id: mbtransquant.c,v 1.21.2.9 2003-04-27 19:47:48 chl Exp $ |
* $Id: mbtransquant.c,v 1.21.2.10 2003-05-09 22:03:13 chl Exp $ |
25 |
* |
* |
26 |
****************************************************************************/ |
****************************************************************************/ |
27 |
|
|
35 |
#include "mem_transfer.h" |
#include "mem_transfer.h" |
36 |
#include "timer.h" |
#include "timer.h" |
37 |
#include "../bitstream/mbcoding.h" |
#include "../bitstream/mbcoding.h" |
38 |
|
#include "../bitstream/zigzag.h" |
39 |
#include "../dct/fdct.h" |
#include "../dct/fdct.h" |
40 |
#include "../dct/idct.h" |
#include "../dct/idct.h" |
41 |
#include "../quant/quant_mpeg4.h" |
#include "../quant/quant_mpeg4.h" |
159 |
} |
} |
160 |
} |
} |
161 |
|
|
162 |
|
|
163 |
|
static int |
164 |
|
dct_quantize_trellis_h263_c(int16_t *const Out, const int16_t *const In, int Q, const uint16_t * const Zigzag, int Non_Zero); |
165 |
|
|
166 |
|
static int |
167 |
|
dct_quantize_trellis_mpeg_c(int16_t *const Out, const int16_t *const In, int Q, const uint16_t * const Zigzag, int Non_Zero); |
168 |
|
|
169 |
|
|
170 |
/* Quantize all blocks -- Inter mode */ |
/* Quantize all blocks -- Inter mode */ |
171 |
static __inline uint8_t |
static __inline uint8_t |
172 |
MBQuantInter(const MBParam * pParam, |
MBQuantInter(const MBParam * pParam, |
190 |
if (!(pParam->vol_flags & XVID_VOL_MPEGQUANT)) { |
if (!(pParam->vol_flags & XVID_VOL_MPEGQUANT)) { |
191 |
sum = quant_inter(&qcoeff[i*64], &data[i*64], pMB->quant); |
sum = quant_inter(&qcoeff[i*64], &data[i*64], pMB->quant); |
192 |
if ( (sum) && (frame->vop_flags & XVID_VOP_TRELLISQUANT) ) { |
if ( (sum) && (frame->vop_flags & XVID_VOP_TRELLISQUANT) ) { |
193 |
sum = dct_quantize_trellis_inter_h263_c (&qcoeff[i*64], &data[i*64], pMB->quant)+1; |
sum = dct_quantize_trellis_h263_c(&qcoeff[i*64], &data[i*64], pMB->quant, &scan_tables[0][0], 63)+1; |
194 |
limit = 1; |
limit = 1; |
195 |
} |
} |
196 |
} else { |
} else { |
197 |
sum = quant4_inter(&qcoeff[i * 64], &data[i * 64], pMB->quant); |
sum = quant4_inter(&qcoeff[i * 64], &data[i * 64], pMB->quant); |
198 |
// if ( (sum) && (frame->vop_flags & XVID_VOP_TRELLISQUANT) ) |
// if ( (sum) && (frame->vop_flags & XVID_VOP_TRELLISQUANT) ) |
199 |
// sum = dct_quantize_trellis_inter_mpeg_c (&qcoeff[i*64], &data[i*64], pMB->quant)+1; |
// sum = dct_quantize_trellis_mpeg_c (&qcoeff[i*64], &data[i*64], pMB->quant)+1; |
200 |
} |
} |
201 |
stop_quant_timer(); |
stop_quant_timer(); |
202 |
|
|
599 |
MOVLINE(LINE(3, 5), LINE(3, 3)); |
MOVLINE(LINE(3, 5), LINE(3, 3)); |
600 |
MOVLINE(LINE(3, 3), tmp); |
MOVLINE(LINE(3, 3), tmp); |
601 |
} |
} |
602 |
|
|
603 |
|
|
604 |
|
|
605 |
|
|
606 |
|
|
607 |
|
/************************************************************************ |
608 |
|
* Trellis based R-D optimal quantization * |
609 |
|
* * |
610 |
|
* Trellis Quant code (C) 2003 Pascal Massimino skal(at)planet-d.net * |
611 |
|
* * |
612 |
|
************************************************************************/ |
613 |
|
|
614 |
|
|
615 |
|
static int |
616 |
|
dct_quantize_trellis_inter_mpeg_c (int16_t *qcoeff, const int16_t *data, int quant) |
617 |
|
{ return 63; } |
618 |
|
|
619 |
|
|
620 |
|
////////////////////////////////////////////////////////// |
621 |
|
// |
622 |
|
// Trellis-Based quantization |
623 |
|
// |
624 |
|
// So far I understand this paper: |
625 |
|
// |
626 |
|
// "Trellis-Based R-D Optimal Quantization in H.263+" |
627 |
|
// J.Wen, M.Luttrell, J.Villasenor |
628 |
|
// IEEE Transactions on Image Processing, Vol.9, No.8, Aug. 2000. |
629 |
|
// |
630 |
|
// we are at stake with a simplified Bellmand-Ford / Dijkstra Single |
631 |
|
// Source Shorted Path algo. But due to the underlying graph structure |
632 |
|
// ("Trellis"), it can be turned into a dynamic programming algo, |
633 |
|
// partially saving the explicit graph's nodes representation. And |
634 |
|
// without using a heap, since the open frontier of the DAG is always |
635 |
|
// known, and of fixed sized. |
636 |
|
// |
637 |
|
////////////////////////////////////////////////////////// |
638 |
|
|
639 |
|
|
640 |
|
////////////////////////////////////////////////////////// |
641 |
|
// Codes lengths for relevant levels. |
642 |
|
|
643 |
|
// let's factorize: |
644 |
|
static const uint8_t Code_Len0[64] = { |
645 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
646 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
647 |
|
static const uint8_t Code_Len1[64] = { |
648 |
|
20,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
649 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
650 |
|
static const uint8_t Code_Len2[64] = { |
651 |
|
19,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
652 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
653 |
|
static const uint8_t Code_Len3[64] = { |
654 |
|
18,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
655 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
656 |
|
static const uint8_t Code_Len4[64] = { |
657 |
|
17,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
658 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
659 |
|
static const uint8_t Code_Len5[64] = { |
660 |
|
16,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
661 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
662 |
|
static const uint8_t Code_Len6[64] = { |
663 |
|
15,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
664 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
665 |
|
static const uint8_t Code_Len7[64] = { |
666 |
|
13,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
667 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
668 |
|
static const uint8_t Code_Len8[64] = { |
669 |
|
11,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
670 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
671 |
|
static const uint8_t Code_Len9[64] = { |
672 |
|
12,21,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
673 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
674 |
|
static const uint8_t Code_Len10[64] = { |
675 |
|
12,20,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
676 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
677 |
|
static const uint8_t Code_Len11[64] = { |
678 |
|
12,19,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
679 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
680 |
|
static const uint8_t Code_Len12[64] = { |
681 |
|
11,17,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
682 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
683 |
|
static const uint8_t Code_Len13[64] = { |
684 |
|
11,15,21,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
685 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
686 |
|
static const uint8_t Code_Len14[64] = { |
687 |
|
10,12,19,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
688 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
689 |
|
static const uint8_t Code_Len15[64] = { |
690 |
|
10,13,17,19,21,21,21,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
691 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
692 |
|
static const uint8_t Code_Len16[64] = { |
693 |
|
9,12,13,18,18,19,19,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
694 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30}; |
695 |
|
static const uint8_t Code_Len17[64] = { |
696 |
|
8,11,13,14,14,14,15,19,19,19,21,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
697 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
698 |
|
static const uint8_t Code_Len18[64] = { |
699 |
|
7, 9,11,11,13,13,13,15,15,15,16,22,22,22,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
700 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
701 |
|
static const uint8_t Code_Len19[64] = { |
702 |
|
5, 7, 9,10,10,11,11,11,11,11,13,14,16,17,17,18,18,18,18,18,18,18,18,20,20,21,21,30,30,30,30,30, |
703 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 }; |
704 |
|
static const uint8_t Code_Len20[64] = { |
705 |
|
3, 4, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9,10,10,10,10,10,10,10,10,12,12,13,13,12,13,14,15,15, |
706 |
|
15,16,16,16,16,17,17,17,18,18,19,19,19,19,19,19,19,19,21,21,22,22,30,30,30,30,30,30,30,30,30,30 }; |
707 |
|
|
708 |
|
// a few more table for LAST table: |
709 |
|
static const uint8_t Code_Len21[64] = { |
710 |
|
13,20,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
711 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30}; |
712 |
|
static const uint8_t Code_Len22[64] = { |
713 |
|
12,15,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30, |
714 |
|
30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30}; |
715 |
|
static const uint8_t Code_Len23[64] = { |
716 |
|
10,12,15,15,15,16,16,16,16,17,17,17,17,17,17,17,17,18,18,18,18,18,18,18,18,19,19,19,19,20,20,20, |
717 |
|
20,21,21,21,21,21,21,21,21,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30}; |
718 |
|
static const uint8_t Code_Len24[64] = { |
719 |
|
5, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9,10,10,10,10,10,10,10,10,11,11,11,11,12,12,12, |
720 |
|
12,13,13,13,13,13,13,13,13,14,16,16,16,16,17,17,17,17,18,18,18,18,18,18,18,18,19,19,19,19,19,19}; |
721 |
|
|
722 |
|
|
723 |
|
static const uint8_t * const B16_17_Code_Len[24] = { // levels [1..24] |
724 |
|
Code_Len20,Code_Len19,Code_Len18,Code_Len17, |
725 |
|
Code_Len16,Code_Len15,Code_Len14,Code_Len13, |
726 |
|
Code_Len12,Code_Len11,Code_Len10,Code_Len9, |
727 |
|
Code_Len8, Code_Len7 ,Code_Len6 ,Code_Len5, |
728 |
|
Code_Len4, Code_Len3, Code_Len3 ,Code_Len2, |
729 |
|
Code_Len2, Code_Len1, Code_Len1, Code_Len1, |
730 |
|
}; |
731 |
|
|
732 |
|
static const uint8_t * const B16_17_Code_Len_Last[6] = { // levels [1..6] |
733 |
|
Code_Len24,Code_Len23,Code_Len22,Code_Len21, Code_Len3, Code_Len1, |
734 |
|
}; |
735 |
|
|
736 |
|
#define TL(q) 0xfe00/(q*q) |
737 |
|
|
738 |
|
static const int Trellis_Lambda_Tabs[31] = { |
739 |
|
TL( 1),TL( 2),TL( 3),TL( 4),TL( 5),TL( 6), TL( 7), |
740 |
|
TL( 8),TL( 9),TL(10),TL(11),TL(12),TL(13),TL(14), TL(15), |
741 |
|
TL(16),TL(17),TL(18),TL(19),TL(20),TL(21),TL(22), TL(23), |
742 |
|
TL(24),TL(25),TL(26),TL(27),TL(28),TL(29),TL(30), TL(31) |
743 |
|
}; |
744 |
|
#undef TL |
745 |
|
|
746 |
|
static inline int Find_Last(const int16_t *C, const uint16_t *Zigzag, int i) |
747 |
|
{ |
748 |
|
while(i>=0) |
749 |
|
if (C[Zigzag[i]]) |
750 |
|
return i; |
751 |
|
else i--; |
752 |
|
return -1; |
753 |
|
} |
754 |
|
|
755 |
|
////////////////////////////////////////////////////////// |
756 |
|
|
757 |
|
#define DBG 0 |
758 |
|
|
759 |
|
static uint32_t Evaluate_Cost(const int16_t *C, int Mult, int Bias, |
760 |
|
const uint16_t * Zigzag, int Max, int Lambda) |
761 |
|
{ |
762 |
|
#if (DBG>0) |
763 |
|
const int16_t * const Ref = C + 6*64; |
764 |
|
int Last = Max; |
765 |
|
while(Last>=0 && C[Zigzag[Last]]==0) Last--; |
766 |
|
int Bits = 0; |
767 |
|
if (Last>=0) { |
768 |
|
Bits = 2; // CBP |
769 |
|
int j=0, j0=0; |
770 |
|
int Run, Level; |
771 |
|
while(j<Last) { |
772 |
|
while(!C[Zigzag[j]]) j++; |
773 |
|
if (j==Last) break; |
774 |
|
Level=C[Zigzag[j]]; |
775 |
|
Run = j - j0; |
776 |
|
j0 = ++j; |
777 |
|
if (Level>=-24 && Level<=24) Bits += B16_17_Code_Len[(Level<0) ? -Level-1 : Level-1][Run]; |
778 |
|
else Bits += 30; |
779 |
|
} |
780 |
|
Level = C[Zigzag[Last]]; |
781 |
|
Run = j - j0; |
782 |
|
if (Level>=-6 && Level<=6) Bits += B16_17_Code_Len_Last[(Level<0) ? -Level-1 : Level-1][Run]; |
783 |
|
else Bits += 30; |
784 |
|
} |
785 |
|
|
786 |
|
int Dist = 0; |
787 |
|
int i; |
788 |
|
for(i=0; i<=Last; ++i) { |
789 |
|
int V = C[Zigzag[i]]*Mult; |
790 |
|
if (V>0) V += Bias; |
791 |
|
else if (V<0) V -= Bias; |
792 |
|
V -= Ref[Zigzag[i]]; |
793 |
|
Dist += V*V; |
794 |
|
} |
795 |
|
uint32_t Cost = Lambda*Dist + (Bits<<16); |
796 |
|
if (DBG==1) |
797 |
|
printf( " Last:%2d/%2d Cost = [(Bits=%5.0d) + Lambda*(Dist=%6.0d) = %d ] >>12= %d ", Last,Max, Bits, Dist, Cost, Cost>>12 ); |
798 |
|
return Cost; |
799 |
|
|
800 |
|
#else |
801 |
|
return 0; |
802 |
|
#endif |
803 |
|
} |
804 |
|
|
805 |
|
|
806 |
|
static int |
807 |
|
dct_quantize_trellis_h263_c(int16_t *const Out, const int16_t *const In, int Q, const uint16_t * const Zigzag, int Non_Zero) |
808 |
|
{ |
809 |
|
|
810 |
|
// Note: We should search last non-zero coeffs on *real* DCT input coeffs (In[]), |
811 |
|
// not quantized one (Out[]). However, it only improves the result *very* |
812 |
|
// slightly (~0.01dB), whereas speed drops to crawling level :) |
813 |
|
// Well, actually, taking 1 more coeff past Non_Zero into account sometimes helps, |
814 |
|
|
815 |
|
typedef struct { int16_t Run, Level; } NODE; |
816 |
|
|
817 |
|
NODE Nodes[65], Last; |
818 |
|
uint32_t Run_Costs0[64+1], * const Run_Costs = Run_Costs0 + 1; |
819 |
|
|
820 |
|
const int Mult = 2*Q; |
821 |
|
const int Bias = (Q-1) | 1; |
822 |
|
const int Lev0 = Mult + Bias; |
823 |
|
const int Lambda = Trellis_Lambda_Tabs[Q-1]; // it's 1/lambda, actually |
824 |
|
|
825 |
|
int Run_Start = -1; |
826 |
|
Run_Costs[-1] = 2<<16; // source (w/ CBP penalty) |
827 |
|
uint32_t Min_Cost = 2<<16; |
828 |
|
|
829 |
|
int Last_Node = -1; |
830 |
|
uint32_t Last_Cost = 0; |
831 |
|
|
832 |
|
#if (DBG>0) |
833 |
|
Last.Level = 0; Last.Run = -1; // just initialize to smthg |
834 |
|
#endif |
835 |
|
|
836 |
|
int i, j; |
837 |
|
|
838 |
|
Non_Zero = Find_Last(Out, Zigzag, Non_Zero); |
839 |
|
if (Non_Zero<0) |
840 |
|
return -1; |
841 |
|
|
842 |
|
for(i=0; i<=Non_Zero; i++) |
843 |
|
{ |
844 |
|
const int AC = In[Zigzag[i]]; |
845 |
|
const int Level1 = Out[Zigzag[i]]; |
846 |
|
const int Dist0 = Lambda* AC*AC; |
847 |
|
uint32_t Best_Cost = 0xf0000000; |
848 |
|
Last_Cost += Dist0; |
849 |
|
|
850 |
|
if ((uint32_t)(Level1+1)<3) // very specialized loop for -1,0,+1 |
851 |
|
{ |
852 |
|
int dQ; |
853 |
|
int Run; |
854 |
|
|
855 |
|
if (AC<0) { |
856 |
|
Nodes[i].Level = -1; |
857 |
|
dQ = Lev0 + AC; |
858 |
|
} else { |
859 |
|
Nodes[i].Level = 1; |
860 |
|
dQ = Lev0 - AC; |
861 |
|
} |
862 |
|
const uint32_t Cost0 = Lambda*dQ*dQ; |
863 |
|
|
864 |
|
Nodes[i].Run = 1; |
865 |
|
Best_Cost = (Code_Len20[0]<<16) + Run_Costs[i-1]+Cost0; |
866 |
|
for(Run=i-Run_Start; Run>0; --Run) |
867 |
|
{ |
868 |
|
const uint32_t Cost_Base = Cost0 + Run_Costs[i-Run]; |
869 |
|
const uint32_t Cost = Cost_Base + (Code_Len20[Run-1]<<16); |
870 |
|
// TODO: what about tie-breaks? Should we favor short runs or |
871 |
|
// long runs? Although the error is the same, it would not be |
872 |
|
// spread the same way along high and low frequencies... |
873 |
|
if (Cost<Best_Cost) |
874 |
|
{ |
875 |
|
Best_Cost = Cost; |
876 |
|
Nodes[i].Run = Run; |
877 |
|
} |
878 |
|
const uint32_t lCost = Cost_Base + (Code_Len24[Run-1]<<16); |
879 |
|
if (lCost<Last_Cost) |
880 |
|
{ |
881 |
|
Last_Cost = lCost; |
882 |
|
Last.Run = Run; |
883 |
|
Last_Node = i; |
884 |
|
} |
885 |
|
} |
886 |
|
if (Last_Node==i) Last.Level = Nodes[i].Level; |
887 |
|
|
888 |
|
|
889 |
|
if (DBG==1) { |
890 |
|
Run_Costs[i] = Best_Cost; |
891 |
|
printf( "Costs #%2d: ", i); |
892 |
|
for(j=-1;j<=Non_Zero;++j) { |
893 |
|
if (j==Run_Start) printf( " %3.0d|", Run_Costs[j]>>12 ); |
894 |
|
else if (j>Run_Start && j<i) printf( " %3.0d|", Run_Costs[j]>>12 ); |
895 |
|
else if (j==i) printf( "(%3.0d)", Run_Costs[j]>>12 ); |
896 |
|
else printf( " - |" ); |
897 |
|
} |
898 |
|
printf( "<%3.0d %2d %d>", Min_Cost>>12, Nodes[i].Level, Nodes[i].Run ); |
899 |
|
printf( " Last:#%2d {%3.0d %2d %d}", Last_Node, Last_Cost>>12, Last.Level, Last.Run ); |
900 |
|
printf( " AC:%3.0d Dist0:%3d Dist(%d)=%d", AC, Dist0>>12, Nodes[i].Level, Cost0>>12 ); |
901 |
|
printf( "\n" ); |
902 |
|
} |
903 |
|
} |
904 |
|
else // "big" levels |
905 |
|
{ |
906 |
|
const uint8_t *Tbl_L1, *Tbl_L2, *Tbl_L1_Last, *Tbl_L2_Last; |
907 |
|
int Level2; |
908 |
|
int dQ1, dQ2; |
909 |
|
int Run; |
910 |
|
|
911 |
|
if (Level1>1) { |
912 |
|
dQ1 = Level1*Mult-AC + Bias; |
913 |
|
dQ2 = dQ1 - Mult; |
914 |
|
Level2 = Level1-1; |
915 |
|
Tbl_L1 = (Level1<=24) ? B16_17_Code_Len[Level1-1] : Code_Len0; |
916 |
|
Tbl_L2 = (Level2<=24) ? B16_17_Code_Len[Level2-1] : Code_Len0; |
917 |
|
Tbl_L1_Last = (Level1<=6) ? B16_17_Code_Len_Last[Level1-1] : Code_Len0; |
918 |
|
Tbl_L2_Last = (Level2<=6) ? B16_17_Code_Len_Last[Level2-1] : Code_Len0; |
919 |
|
} |
920 |
|
else { // Level1<-1 |
921 |
|
dQ1 = Level1*Mult-AC - Bias; |
922 |
|
dQ2 = dQ1 + Mult; |
923 |
|
Level2 = Level1 + 1; |
924 |
|
Tbl_L1 = (Level1>=-24) ? B16_17_Code_Len[Level1^-1] : Code_Len0; |
925 |
|
Tbl_L2 = (Level2>=-24) ? B16_17_Code_Len[Level2^-1] : Code_Len0; |
926 |
|
Tbl_L1_Last = (Level1>=- 6) ? B16_17_Code_Len_Last[Level1^-1] : Code_Len0; |
927 |
|
Tbl_L2_Last = (Level2>=- 6) ? B16_17_Code_Len_Last[Level2^-1] : Code_Len0; |
928 |
|
} |
929 |
|
const uint32_t Dist1 = Lambda*dQ1*dQ1; |
930 |
|
const uint32_t Dist2 = Lambda*dQ2*dQ2; |
931 |
|
const int dDist21 = Dist2-Dist1; |
932 |
|
|
933 |
|
for(Run=i-Run_Start; Run>0; --Run) |
934 |
|
{ |
935 |
|
const uint32_t Cost_Base = Dist1 + Run_Costs[i-Run]; |
936 |
|
|
937 |
|
// for sub-optimal (but slightly worth it, speed-wise) search, uncomment the following: |
938 |
|
// if (Cost_Base>=Best_Cost) continue; |
939 |
|
|
940 |
|
uint32_t Cost1, Cost2; |
941 |
|
int bLevel; |
942 |
|
|
943 |
|
Cost1 = Cost_Base + (Tbl_L1[Run-1]<<16); |
944 |
|
Cost2 = Cost_Base + (Tbl_L2[Run-1]<<16) + dDist21; |
945 |
|
|
946 |
|
if (Cost2<Cost1) { Cost1 = Cost2; bLevel = Level2; } |
947 |
|
else bLevel = Level1; |
948 |
|
|
949 |
|
if (Cost1<Best_Cost) |
950 |
|
{ |
951 |
|
Best_Cost = Cost1; |
952 |
|
Nodes[i].Run = Run; |
953 |
|
Nodes[i].Level = bLevel; |
954 |
|
} |
955 |
|
|
956 |
|
Cost1 = Cost_Base + (Tbl_L1_Last[Run-1]<<16); |
957 |
|
Cost2 = Cost_Base + (Tbl_L2_Last[Run-1]<<16) + dDist21; |
958 |
|
|
959 |
|
if (Cost2<Cost1) { Cost1 = Cost2; bLevel = Level2; } |
960 |
|
else bLevel = Level1; |
961 |
|
if (Cost1<Last_Cost) |
962 |
|
{ |
963 |
|
Last_Cost = Cost1; |
964 |
|
Last.Run = Run; |
965 |
|
Last.Level = bLevel; |
966 |
|
Last_Node = i; |
967 |
|
} |
968 |
|
} |
969 |
|
|
970 |
|
if (DBG==1) { |
971 |
|
Run_Costs[i] = Best_Cost; |
972 |
|
printf( "Costs #%2d: ", i); |
973 |
|
for(j=-1;j<=Non_Zero;++j) { |
974 |
|
if (j==Run_Start) printf( " %3.0d|", Run_Costs[j]>>12 ); |
975 |
|
else if (j>Run_Start && j<i) printf( " %3.0d|", Run_Costs[j]>>12 ); |
976 |
|
else if (j==i) printf( "(%3.0d)", Run_Costs[j]>>12 ); |
977 |
|
else printf( " - |" ); |
978 |
|
} |
979 |
|
printf( "<%3.0d %2d %d>", Min_Cost>>12, Nodes[i].Level, Nodes[i].Run ); |
980 |
|
printf( " Last:#%2d {%3.0d %2d %d}", Last_Node, Last_Cost>>12, Last.Level, Last.Run ); |
981 |
|
printf( " AC:%3.0d Dist0:%3d Dist(%2d):%3d Dist(%2d):%3d", AC, Dist0>>12, Level1, Dist1>>12, Level2, Dist2>>12 ); |
982 |
|
printf( "\n" ); |
983 |
|
} |
984 |
|
} |
985 |
|
|
986 |
|
Run_Costs[i] = Best_Cost; |
987 |
|
|
988 |
|
if (Best_Cost < Min_Cost + Dist0) { |
989 |
|
Min_Cost = Best_Cost; |
990 |
|
Run_Start = i; |
991 |
|
} |
992 |
|
else |
993 |
|
{ |
994 |
|
// as noticed by Michael Niedermayer (michaelni at gmx.at), there's |
995 |
|
// a code shorter by 1 bit for a larger run (!), same level. We give |
996 |
|
// it a chance by not moving the left barrier too much. |
997 |
|
while( Run_Costs[Run_Start]>Min_Cost+(1<<16) ) |
998 |
|
Run_Start++; |
999 |
|
|
1000 |
|
// spread on preceding coeffs the cost incurred by skipping this one |
1001 |
|
for(j=Run_Start; j<i; ++j) Run_Costs[j] += Dist0; |
1002 |
|
Min_Cost += Dist0; |
1003 |
|
} |
1004 |
|
} |
1005 |
|
|
1006 |
|
if (DBG) { |
1007 |
|
Last_Cost = Evaluate_Cost(Out,Mult,Bias, Zigzag,Non_Zero, Lambda); |
1008 |
|
if (DBG==1) { |
1009 |
|
printf( "=> " ); |
1010 |
|
for(i=0; i<=Non_Zero; ++i) printf( "[%3.0d] ", Out[Zigzag[i]] ); |
1011 |
|
printf( "\n" ); |
1012 |
|
} |
1013 |
|
} |
1014 |
|
|
1015 |
|
if (Last_Node<0) |
1016 |
|
return -1; |
1017 |
|
|
1018 |
|
// reconstruct optimal sequence backward with surviving paths |
1019 |
|
bzero(Out, 64*sizeof(*Out)); |
1020 |
|
Out[Zigzag[Last_Node]] = Last.Level; |
1021 |
|
i = Last_Node - Last.Run; |
1022 |
|
while(i>=0) { |
1023 |
|
Out[Zigzag[i]] = Nodes[i].Level; |
1024 |
|
i -= Nodes[i].Run; |
1025 |
|
} |
1026 |
|
|
1027 |
|
if (DBG) { |
1028 |
|
uint32_t Cost = Evaluate_Cost(Out,Mult,Bias, Zigzag,Non_Zero, Lambda); |
1029 |
|
if (DBG==1) { |
1030 |
|
printf( "<= " ); |
1031 |
|
for(i=0; i<=Last_Node; ++i) printf( "[%3.0d] ", Out[Zigzag[i]] ); |
1032 |
|
printf( "\n--------------------------------\n" ); |
1033 |
|
} |
1034 |
|
if (Cost>Last_Cost) printf( "!!! %u > %u\n", Cost, Last_Cost ); |
1035 |
|
} |
1036 |
|
return Last_Node; |
1037 |
|
} |
1038 |
|
|
1039 |
|
#undef DBG |