[xiph-commits] r17240 - in branches/theora-gumboot: . lib
gumboot at svn.xiph.org
gumboot at svn.xiph.org
Sat May 22 03:39:47 PDT 2010
Author: gumboot
Date: 2010-05-22 03:39:47 -0700 (Sat, 22 May 2010)
New Revision: 17240
Modified:
branches/theora-gumboot/
branches/theora-gumboot/lib/analyze.c
branches/theora-gumboot/lib/decode.c
branches/theora-gumboot/lib/huffdec.c
Log:
sync theora-gumboot branch again
Property changes on: branches/theora-gumboot
___________________________________________________________________
Modified: svn:mergeinfo
- /experimental/derf/theora-ptalarbvorm:17164-17220
/trunk/theora:14138-15320,15741
+ /experimental/derf/theora-ptalarbvorm:17164-17220,17222-17239
/trunk/theora:14138-15320,15741
Modified: branches/theora-gumboot/lib/analyze.c
===================================================================
--- branches/theora-gumboot/lib/analyze.c 2010-05-22 05:07:21 UTC (rev 17239)
+++ branches/theora-gumboot/lib/analyze.c 2010-05-22 10:39:47 UTC (rev 17240)
@@ -1702,7 +1702,7 @@
}
/*Compute the average block activity and MB luma score for the frame.*/
_enc->activity_avg=
- (unsigned)((activity_sum+(_enc->state.nfrags>>1))/_enc->state.nfrags);
+ (unsigned)((activity_sum+(_enc->state.fplanes[0].nfrags>>1))/_enc->state.fplanes[0].nfrags);
_enc->luma_avg=(unsigned)((luma_sum+(_enc->state.nmbs>>1))/_enc->state.nmbs);
/*Finish filling in the reference frame borders.*/
refi=_enc->state.ref_frame_idx[OC_FRAME_SELF];
@@ -2650,7 +2650,7 @@
We could use a Bessel follower here, but fast reaction is probably almost
always best.*/
_enc->activity_avg=
- (unsigned)((activity_sum+(_enc->state.nfrags>>1))/_enc->state.nfrags);
+ (unsigned)((activity_sum+(_enc->state.fplanes[0].nfrags>>1))/_enc->state.fplanes[0].nfrags);
_enc->luma_avg=(unsigned)((luma_sum+(_enc->state.nmbs>>1))/_enc->state.nmbs);
/*Finish filling in the reference frame borders.*/
refi=_enc->state.ref_frame_idx[OC_FRAME_SELF];
Modified: branches/theora-gumboot/lib/decode.c
===================================================================
--- branches/theora-gumboot/lib/decode.c 2010-05-22 05:07:21 UTC (rev 17239)
+++ branches/theora-gumboot/lib/decode.c 2010-05-22 10:39:47 UTC (rev 17240)
@@ -129,7 +129,7 @@
is not yet available everywhere; this should be equivalent.*/
#define OC_DCT_EOB_FINISH (~(size_t)0>>1)
-/*The location of the (6) run legth bits in the code word.
+/*The location of the (6) run length bits in the code word.
These are placed at index 0 and given 8 bits (even though 6 would suffice)
because it may be faster to extract the lower byte on some platforms.*/
#define OC_DCT_CW_RLEN_SHIFT (0)
@@ -297,8 +297,6 @@
static int oc_sb_run_unpack(oc_pack_buf *_opb){
- long bits;
- int ret;
/*Coding scheme:
Codeword Run Length
0 1
@@ -308,32 +306,26 @@
11110xxx 10-17
111110xxxx 18-33
111111xxxxxxxxxxxx 34-4129*/
- bits=oc_pack_read1(_opb);
- if(bits==0)return 1;
- bits=oc_pack_read(_opb,2);
- if((bits&2)==0)return 2+(int)bits;
- else if((bits&1)==0){
- bits=oc_pack_read1(_opb);
- return 4+(int)bits;
+ static const ogg_int16_t OC_SB_RUN_TREE[22]={
+ 4,
+ -(1<<8|1),-(1<<8|1),-(1<<8|1),-(1<<8|1),
+ -(1<<8|1),-(1<<8|1),-(1<<8|1),-(1<<8|1),
+ -(3<<8|2),-(3<<8|2),-(3<<8|3),-(3<<8|3),
+ -(4<<8|4),-(4<<8|5),-(4<<8|2<<4|6-6),17,
+ 2,
+ -(2<<8|2<<4|10-6),-(2<<8|2<<4|14-6),-(2<<8|4<<4|18-6),-(2<<8|12<<4|34-6)
+ };
+ int ret;
+ ret=oc_huff_token_decode(_opb,OC_SB_RUN_TREE);
+ if(ret>=0x10){
+ int offs;
+ offs=ret&0x1F;
+ ret=6+offs+(int)oc_pack_read(_opb,ret-offs>>4);
}
- bits=oc_pack_read(_opb,3);
- if((bits&4)==0)return 6+(int)bits;
- else if((bits&2)==0){
- ret=10+((bits&1)<<2);
- bits=oc_pack_read(_opb,2);
- return ret+(int)bits;
- }
- else if((bits&1)==0){
- bits=oc_pack_read(_opb,4);
- return 18+(int)bits;
- }
- bits=oc_pack_read(_opb,12);
- return 34+(int)bits;
+ return ret;
}
static int oc_block_run_unpack(oc_pack_buf *_opb){
- long bits;
- long bits2;
/*Coding scheme:
Codeword Run Length
0x 1-2
@@ -342,22 +334,26 @@
1110xx 7-10
11110xx 11-14
11111xxxx 15-30*/
- bits=oc_pack_read(_opb,2);
- if((bits&2)==0)return 1+(int)bits;
- else if((bits&1)==0){
- bits=oc_pack_read1(_opb);
- return 3+(int)bits;
- }
- bits=oc_pack_read(_opb,2);
- if((bits&2)==0)return 5+(int)bits;
- else if((bits&1)==0){
- bits=oc_pack_read(_opb,2);
- return 7+(int)bits;
- }
- bits=oc_pack_read(_opb,3);
- if((bits&4)==0)return 11+bits;
- bits2=oc_pack_read(_opb,2);
- return 15+((bits&3)<<2)+bits2;
+ static const ogg_int16_t OC_BLOCK_RUN_TREE[61]={
+ 5,
+ -(2<<8|1),-(2<<8|1),-(2<<8|1),-(2<<8|1),
+ -(2<<8|1),-(2<<8|1),-(2<<8|1),-(2<<8|1),
+ -(2<<8|2),-(2<<8|2),-(2<<8|2),-(2<<8|2),
+ -(2<<8|2),-(2<<8|2),-(2<<8|2),-(2<<8|2),
+ -(3<<8|3),-(3<<8|3),-(3<<8|3),-(3<<8|3),
+ -(3<<8|4),-(3<<8|4),-(3<<8|4),-(3<<8|4),
+ -(4<<8|5),-(4<<8|5),-(4<<8|6),-(4<<8|6),
+ 33, 36, 39, 44,
+ 1,-(1<<8|7),-(1<<8|8),
+ 1,-(1<<8|9),-(1<<8|10),
+ 2,-(2<<8|11),-(2<<8|12),-(2<<8|13),-(2<<8|14),
+ 4,
+ -(4<<8|15),-(4<<8|16),-(4<<8|17),-(4<<8|18),
+ -(4<<8|19),-(4<<8|20),-(4<<8|21),-(4<<8|22),
+ -(4<<8|23),-(4<<8|24),-(4<<8|25),-(4<<8|26),
+ -(4<<8|27),-(4<<8|28),-(4<<8|29),-(4<<8|30)
+ };
+ return oc_huff_token_decode(_opb,OC_BLOCK_RUN_TREE);
}
@@ -673,25 +669,33 @@
}
+/*Coding scheme:
+ Codeword Mode Index
+ 0 0
+ 10 1
+ 110 2
+ 1110 3
+ 11110 4
+ 111110 5
+ 1111110 6
+ 1111111 7*/
+static const ogg_int16_t OC_VLC_MODE_TREE[26]={
+ 4,
+ -(1<<8|0),-(1<<8|0),-(1<<8|0),-(1<<8|0),
+ -(1<<8|0),-(1<<8|0),-(1<<8|0),-(1<<8|0),
+ -(2<<8|1),-(2<<8|1),-(2<<8|1),-(2<<8|1),
+ -(3<<8|2),-(3<<8|2),-(4<<8|3),17,
+ 3,
+ -(1<<8|4),-(1<<8|4),-(1<<8|4),-(1<<8|4),
+ -(2<<8|5),-(2<<8|5),-(3<<8|6),-(3<<8|7)
+};
-typedef int (*oc_mode_unpack_func)(oc_pack_buf *_opb);
+static const ogg_int16_t OC_CLC_MODE_TREE[9]={
+ 3,
+ -(3<<8|0),-(3<<8|1),-(3<<8|2),-(3<<8|3),
+ -(3<<8|4),-(3<<8|5),-(3<<8|6),-(3<<8|7)
+};
-static int oc_vlc_mode_unpack(oc_pack_buf *_opb){
- long val;
- int i;
- for(i=0;i<7;i++){
- val=oc_pack_read1(_opb);
- if(!val)break;
- }
- return i;
-}
-
-static int oc_clc_mode_unpack(oc_pack_buf *_opb){
- long val;
- val=oc_pack_read(_opb,3);
- return (int)val;
-}
-
/*Unpacks the list of macro block modes for INTER frames.*/
static void oc_dec_mb_modes_unpack(oc_dec_ctx *_dec){
const oc_mb_map *mb_maps;
@@ -699,7 +703,7 @@
const oc_fragment *frags;
const unsigned char *alphabet;
unsigned char scheme0_alphabet[8];
- oc_mode_unpack_func mode_unpack;
+ const ogg_int16_t *mode_tree;
size_t nmbs;
size_t mbi;
long val;
@@ -721,8 +725,7 @@
alphabet=scheme0_alphabet;
}
else alphabet=OC_MODE_ALPHABETS[mode_scheme-1];
- if(mode_scheme==7)mode_unpack=oc_clc_mode_unpack;
- else mode_unpack=oc_vlc_mode_unpack;
+ mode_tree=mode_scheme==7?OC_CLC_MODE_TREE:OC_VLC_MODE_TREE;
mb_modes=_dec->state.mb_modes;
mb_maps=(const oc_mb_map *)_dec->state.mb_maps;
nmbs=_dec->state.nmbs;
@@ -733,7 +736,9 @@
/*Check for a coded luma block in this macro block.*/
for(bi=0;bi<4&&!frags[mb_maps[mbi][0][bi]].coded;bi++);
/*We found one, decode a mode.*/
- if(bi<4)mb_modes[mbi]=alphabet[(*mode_unpack)(&_dec->opb)];
+ if(bi<4){
+ mb_modes[mbi]=alphabet[oc_huff_token_decode(&_dec->opb,mode_tree)];
+ }
/*There were none: INTER_NOMV is forced.*/
else mb_modes[mbi]=OC_MODE_INTER_NOMV;
}
@@ -742,44 +747,62 @@
-typedef int (*oc_mv_comp_unpack_func)(oc_pack_buf *_opb);
+static const ogg_int16_t OC_VLC_MV_COMP_TREE[101]={
+ 5,
+ -(3<<8|32+0),-(3<<8|32+0),-(3<<8|32+0),-(3<<8|32+0),
+ -(3<<8|32+1),-(3<<8|32+1),-(3<<8|32+1),-(3<<8|32+1),
+ -(3<<8|32-1),-(3<<8|32-1),-(3<<8|32-1),-(3<<8|32-1),
+ -(4<<8|32+2),-(4<<8|32+2),-(4<<8|32-2),-(4<<8|32-2),
+ -(4<<8|32+3),-(4<<8|32+3),-(4<<8|32-3),-(4<<8|32-3),
+ 33, 36, 39, 42,
+ 45, 50, 55, 60,
+ 65, 74, 83, 92,
+ 1,-(1<<8|32+4),-(1<<8|32-4),
+ 1,-(1<<8|32+5),-(1<<8|32-5),
+ 1,-(1<<8|32+6),-(1<<8|32-6),
+ 1,-(1<<8|32+7),-(1<<8|32-7),
+ 2,-(2<<8|32+8),-(2<<8|32-8),-(2<<8|32+9),-(2<<8|32-9),
+ 2,-(2<<8|32+10),-(2<<8|32-10),-(2<<8|32+11),-(2<<8|32-11),
+ 2,-(2<<8|32+12),-(2<<8|32-12),-(2<<8|32+13),-(2<<8|32-13),
+ 2,-(2<<8|32+14),-(2<<8|32-14),-(2<<8|32+15),-(2<<8|32-15),
+ 3,
+ -(3<<8|32+16),-(3<<8|32-16),-(3<<8|32+17),-(3<<8|32-17),
+ -(3<<8|32+18),-(3<<8|32-18),-(3<<8|32+19),-(3<<8|32-19),
+ 3,
+ -(3<<8|32+20),-(3<<8|32-20),-(3<<8|32+21),-(3<<8|32-21),
+ -(3<<8|32+22),-(3<<8|32-22),-(3<<8|32+23),-(3<<8|32-23),
+ 3,
+ -(3<<8|32+24),-(3<<8|32-24),-(3<<8|32+25),-(3<<8|32-25),
+ -(3<<8|32+26),-(3<<8|32-26),-(3<<8|32+27),-(3<<8|32-27),
+ 3,
+ -(3<<8|32+28),-(3<<8|32-28),-(3<<8|32+29),-(3<<8|32-29),
+ -(3<<8|32+30),-(3<<8|32-30),-(3<<8|32+31),-(3<<8|32-31)
+};
-static int oc_vlc_mv_comp_unpack(oc_pack_buf *_opb){
- long bits;
- int mask;
- int mv;
- bits=oc_pack_read(_opb,3);
- switch(bits){
- case 0:return 0;
- case 1:return 1;
- case 2:return -1;
- case 3:
- case 4:{
- mv=(int)(bits-1);
- bits=oc_pack_read1(_opb);
- }break;
- /*case 5:
- case 6:
- case 7:*/
- default:{
- mv=1<<bits-3;
- bits=oc_pack_read(_opb,bits-2);
- mv+=(int)(bits>>1);
- bits&=1;
- }break;
- }
- mask=-(int)bits;
- return mv+mask^mask;
-}
+static const ogg_int16_t OC_CLC_MV_COMP_TREE[65]={
+ 6,
+ -(6<<8|32 +0),-(6<<8|32 -0),-(6<<8|32 +1),-(6<<8|32 -1),
+ -(6<<8|32 +2),-(6<<8|32 -2),-(6<<8|32 +3),-(6<<8|32 -3),
+ -(6<<8|32 +4),-(6<<8|32 -4),-(6<<8|32 +5),-(6<<8|32 -5),
+ -(6<<8|32 +6),-(6<<8|32 -6),-(6<<8|32 +7),-(6<<8|32 -7),
+ -(6<<8|32 +8),-(6<<8|32 -8),-(6<<8|32 +9),-(6<<8|32 -9),
+ -(6<<8|32+10),-(6<<8|32-10),-(6<<8|32+11),-(6<<8|32-11),
+ -(6<<8|32+12),-(6<<8|32-12),-(6<<8|32+13),-(6<<8|32-13),
+ -(6<<8|32+14),-(6<<8|32-14),-(6<<8|32+15),-(6<<8|32-15),
+ -(6<<8|32+16),-(6<<8|32-16),-(6<<8|32+17),-(6<<8|32-17),
+ -(6<<8|32+18),-(6<<8|32-18),-(6<<8|32+19),-(6<<8|32-19),
+ -(6<<8|32+20),-(6<<8|32-20),-(6<<8|32+21),-(6<<8|32-21),
+ -(6<<8|32+22),-(6<<8|32-22),-(6<<8|32+23),-(6<<8|32-23),
+ -(6<<8|32+24),-(6<<8|32-24),-(6<<8|32+25),-(6<<8|32-25),
+ -(6<<8|32+26),-(6<<8|32-26),-(6<<8|32+27),-(6<<8|32-27),
+ -(6<<8|32+28),-(6<<8|32-28),-(6<<8|32+29),-(6<<8|32-29),
+ -(6<<8|32+30),-(6<<8|32-30),-(6<<8|32+31),-(6<<8|32-31)
+};
-static int oc_clc_mv_comp_unpack(oc_pack_buf *_opb){
- long bits;
- int mask;
- int mv;
- bits=oc_pack_read(_opb,6);
- mv=(int)bits>>1;
- mask=-((int)bits&1);
- return mv+mask^mask;
+
+static void oc_mv_unpack(oc_pack_buf *_opb,const ogg_int16_t *_tree,oc_mv _mv){
+ _mv[0]=(signed char)(oc_huff_token_decode(_opb,_tree)-32);
+ _mv[1]=(signed char)(oc_huff_token_decode(_opb,_tree)-32);
}
/*Unpacks the list of motion vectors for INTER frames, and propagtes the macro
@@ -788,7 +811,7 @@
const oc_mb_map *mb_maps;
const signed char *mb_modes;
oc_set_chroma_mvs_func set_chroma_mvs;
- oc_mv_comp_unpack_func mv_comp_unpack;
+ const ogg_int16_t *mv_comp_tree;
oc_fragment *frags;
oc_mv *frag_mvs;
const unsigned char *map_idxs;
@@ -800,7 +823,7 @@
long val;
set_chroma_mvs=OC_SET_CHROMA_MVS_TABLE[_dec->state.info.pixel_fmt];
val=oc_pack_read1(&_dec->opb);
- mv_comp_unpack=val?oc_clc_mv_comp_unpack:oc_vlc_mv_comp_unpack;
+ mv_comp_tree=val?OC_CLC_MV_COMP_TREE:OC_VLC_MV_COMP_TREE;
map_idxs=OC_MB_MAP_IDXS[_dec->state.info.pixel_fmt];
map_nidxs=OC_MB_MAP_NIDXS[_dec->state.info.pixel_fmt];
memset(last_mv,0,sizeof(last_mv));
@@ -840,8 +863,7 @@
codedi++;
fragi=mb_maps[mbi][0][bi];
frags[fragi].mb_mode=mb_mode;
- lbmvs[bi][0]=(signed char)(*mv_comp_unpack)(&_dec->opb);
- lbmvs[bi][1]=(signed char)(*mv_comp_unpack)(&_dec->opb);
+ oc_mv_unpack(&_dec->opb,mv_comp_tree,lbmvs[bi]);
memcpy(frag_mvs[fragi],lbmvs[bi],sizeof(lbmvs[bi]));
}
else lbmvs[bi][0]=lbmvs[bi][1]=0;
@@ -863,8 +885,8 @@
}break;
case OC_MODE_INTER_MV:{
memcpy(last_mv[1],last_mv[0],sizeof(last_mv[1]));
- mbmv[0]=last_mv[0][0]=(signed char)(*mv_comp_unpack)(&_dec->opb);
- mbmv[1]=last_mv[0][1]=(signed char)(*mv_comp_unpack)(&_dec->opb);
+ oc_mv_unpack(&_dec->opb,mv_comp_tree,mbmv);
+ memcpy(last_mv[0],mbmv,sizeof(last_mv[0]));
}break;
case OC_MODE_INTER_MV_LAST:memcpy(mbmv,last_mv[0],sizeof(mbmv));break;
case OC_MODE_INTER_MV_LAST2:{
@@ -873,8 +895,7 @@
memcpy(last_mv[0],mbmv,sizeof(last_mv[0]));
}break;
case OC_MODE_GOLDEN_MV:{
- mbmv[0]=(signed char)(*mv_comp_unpack)(&_dec->opb);
- mbmv[1]=(signed char)(*mv_comp_unpack)(&_dec->opb);
+ oc_mv_unpack(&_dec->opb,mv_comp_tree,mbmv);
}break;
default:memset(mbmv,0,sizeof(mbmv));break;
}
Modified: branches/theora-gumboot/lib/huffdec.c
===================================================================
--- branches/theora-gumboot/lib/huffdec.c 2010-05-22 05:07:21 UTC (rev 17239)
+++ branches/theora-gumboot/lib/huffdec.c 2010-05-22 10:39:47 UTC (rev 17240)
@@ -46,22 +46,23 @@
It also has very large memory requirements, which impairs cache coherency.
We store the tree packed in an array of 16-bit integers (words).
- Each node of the tree consists of a single word, followed consecutiably by
- zero or more indexes of its children.
+ Each node consists of a single word, followed consecutively by two or more
+ indices of its children.
Let n be the value of this first word.
-
- If n is negative or zero, then this is a leaf node.
- The token in the leaf node is (-n&255).
- The number of bits that should have been read to reach this child, starting
- from the current node, is (-n>>8).
-
- If n is positive, then it is the number of bits that need to be read to
- traverse the node.
+ This is the number of bits that need to be read to traverse the node, and
+ must be positive.
1<<n entries follow in the array, each an index to a child node.
- As an optimization to save space, leaf nodes are stored directly, instead of
- storing an index, since they only require a single word.
- If a leaf node would have been before reading n bits, then it is duplicated
- the necessary number of times in this table.
+ If the child is positive, then it is the index of another internal node in
+ the table.
+ If the child is negative or zero, then it is a leaf node.
+ These are stored directly in the child pointer to save space, since they only
+ require a single word.
+ If a leaf node would have been encountered before reading n bits, then it is
+ duplicated the necessary number of times in this table.
+ Leaf nodes pack both a token value and their actual depth in the tree.
+ The token in the leaf node is (-leaf&255).
+ The number of bits that need to be consumed to reach the leaf, starting from
+ the current node, is (-leaf>>8).
@ARTICLE{Hash95,
author="Reza Hashemian",
@@ -76,11 +77,6 @@
-/*The number of internal tokens associated with each of the spec tokens.*/
-static const unsigned char OC_DCT_TOKEN_MAP_ENTRIES[TH_NDCT_TOKENS]={
- 1,1,1,4,8,1,1,8,1,1,1,1,1,2,2,2,2,4,8,2,2,2,4,2,2,2,2,2,8,2,4,8
-};
-
/*The map from external spec-defined tokens to internal tokens.
This is constructed so that any extra bits read with the original token value
can be masked off the least significant bits of its internal token index.
@@ -149,353 +145,232 @@
40
};
+/*The log base 2 of number of internal tokens associated with each of the spec
+ tokens (i.e., how many of the extra bits are folded into the token value).
+ Increasing the maximum value beyond 3 will enlarge the amount of stack
+ required for tree construction.*/
+static const unsigned char OC_DCT_TOKEN_MAP_LOG_NENTRIES[TH_NDCT_TOKENS]={
+ 0,0,0,2,3,0,0,3,0,0,0,0,0,1,1,1,1,2,3,1,1,1,2,1,1,1,1,1,3,1,2,3
+};
-/*The log_2 of the size of a lookup table is allowed to grow to relative to
- the number of unique nodes it contains.
- E.g., if OC_HUFF_SLUSH is 2, then at most 75% of the space in the tree is
- wasted (each node will have an amortized cost of at most 20 bytes when using
- 4-byte pointers).
+
+/*The size a lookup table is allowed to grow to relative to the number of
+ unique nodes it contains.
+ E.g., if OC_HUFF_SLUSH is 4, then at most 75% of the space in the tree is
+ wasted.
Larger numbers can decode tokens with fewer read operations, while smaller
- numbers may save more space (requiring as little as 8 bytes amortized per
- node, though there will be more nodes).
+ numbers may save more space.
With a sample file:
32233473 read calls are required when no tree collapsing is done (100.0%).
- 19269269 read calls are required when OC_HUFF_SLUSH is 0 (59.8%).
- 11144969 read calls are required when OC_HUFF_SLUSH is 1 (34.6%).
- 10538563 read calls are required when OC_HUFF_SLUSH is 2 (32.7%).
- 10192578 read calls are required when OC_HUFF_SLUSH is 3 (31.6%).
+ 19269269 read calls are required when OC_HUFF_SLUSH is 1 (59.8%).
+ 11144969 read calls are required when OC_HUFF_SLUSH is 2 (34.6%).
+ 10538563 read calls are required when OC_HUFF_SLUSH is 4 (32.7%).
+ 10192578 read calls are required when OC_HUFF_SLUSH is 8 (31.6%).
Since a value of 1 gets us the vast majority of the speed-up with only a
small amount of wasted memory, this is what we use.
- This value must be less than 7, or you could create a tree with more than
+ This value must be less than 128, or you could create a tree with more than
32767 entries, which would overflow the 16-bit words used to index it.*/
-#define OC_HUFF_SLUSH (1)
-/*The root of the tree is the fast path, and a larger value here is more
+#define OC_HUFF_SLUSH (2)
+/*The root of the tree is on the fast path, and a larger value here is more
beneficial than elsewhere in the tree.
- 3 appears to give the best performance, trading off between increased use of
- the single-read fast path and cache footprint for the tables.
- using 3 here The VP3 tables are about 2.6x larger using 3 here than using 1.*/
-#define OC_ROOT_HUFF_SLUSH (3)
+ 7 appears to give the best performance, trading off between increased use of
+ the single-read fast path and cache footprint for the tables, though
+ obviously this will depend on your cache size.
+ Using 7 here, the VP3 tables are about twice as large compared to using 2.*/
+#define OC_ROOT_HUFF_SLUSH (7)
-/*Determines the size in words of a Huffman tree node that represents a
- subtree of depth _nbits.
- _nbits: The depth of the subtree.
- If this is <=0, the node is a leaf node.
- Otherwise 1<<_nbits pointers are allocated for children.
- Return: The number of words required to store the node.*/
-static size_t oc_huff_node_size(int _nbits){
- return _nbits>0?1+(1<<_nbits):1;
-}
-
-/*Determines the size in words of a Huffman subtree.
- _tree: The complete Huffman tree.
- _node: The index of the root of the desired subtree.
- Return: The number of words required to store the tree.*/
-static size_t oc_huff_tree_size(const ogg_int16_t *_tree,int _node){
- size_t size;
- int n;
- n=_tree[_node];
- size=oc_huff_node_size(n);
- if(n>0){
- int nchildren;
- int i;
- nchildren=1<<n;
- i=0;
- do{
- int child;
- child=_tree[_node+i+1];
- if(child<=0)i+=1<<n-(-child>>8);
- else{
- size+=oc_huff_tree_size(_tree,child);
- i++;
- }
+/*Unpacks a Huffman codebook.
+ _opb: The buffer to unpack from.
+ _tokens: Stores a list of internal tokens, in the order they were found in
+ the codebook, and the lengths of their corresponding codewords.
+ This is enough to completely define the codebook, while minimizing
+ stack usage and avoiding temporary allocations (for platforms
+ where free() is a no-op).
+ Return: The number of internal tokens in the codebook, or a negative value
+ on error.*/
+int oc_huff_tree_unpack(oc_pack_buf *_opb,unsigned char _tokens[256][2]){
+ ogg_uint32_t code;
+ int len;
+ int ntokens;
+ int nleaves;
+ code=0;
+ len=ntokens=nleaves=0;
+ for(;;){
+ long bits;
+ bits=oc_pack_read1(_opb);
+ /*Only process nodes so long as there's more bits in the buffer.*/
+ if(oc_pack_bytes_left(_opb)<0)return TH_EBADHEADER;
+ /*Read an internal node:*/
+ if(!bits){
+ len++;
+ /*Don't allow codewords longer than 32 bits.*/
+ if(len>32)return TH_EBADHEADER;
}
- while(i<nchildren);
- }
- return size;
-}
-
-
-/*Unpacks a sub-tree from the given buffer.
- _opb: The buffer to unpack from.
- _bitree: The tree to store the sub-tree in.
- _nbinodes: The number of nodes available for the tree.
- _binode: The index of the tree to store it in.
- This is updated to point to the first available slot past the
- sub-tree on return.
- If an error occurs, this is set larger than _nbinodes.
- Return: The node index of the sub-tree, or leaf node value if this was a leaf
- node and this wasn't the root of the tree.*/
-static int oc_huff_tree_unpack(oc_pack_buf *_opb,
- ogg_int16_t *_bitree,int _nbinodes,int *_binode){
- long bits;
- int binode;
- binode=*_binode;
- if(binode>_nbinodes)return 0;
- bits=oc_pack_read1(_opb);
- if(oc_pack_bytes_left(_opb)<0){
- *_binode=_nbinodes+1;
- return 0;
- }
- /*Read an internal node:*/
- if(!bits){
- *_binode=binode+3;
- if(binode+3>_nbinodes)return 0;
- _bitree[binode+0]=1;
- _bitree[binode+1]=
- (ogg_int16_t)oc_huff_tree_unpack(_opb,_bitree,_nbinodes,_binode);
- _bitree[binode+2]=
- (ogg_int16_t)oc_huff_tree_unpack(_opb,_bitree,_nbinodes,_binode);
- }
- /*Read a leaf node:*/
- else{
- int ntokens;
- int token;
- bits=oc_pack_read(_opb,OC_NDCT_TOKEN_BITS);
- if(oc_pack_bytes_left(_opb)<0){
- *_binode=_nbinodes+1;
- return 0;
- }
- /*Find out how many internal tokens we translate this external token into.
- This must be a power of two.*/
- ntokens=OC_DCT_TOKEN_MAP_ENTRIES[bits];
- token=OC_DCT_TOKEN_MAP[bits];
- if(ntokens<=1){
- /*If we only have the one leaf, return it directly.*/
- if(binode>0)return -(1<<8|token);
- /*Unless we are the root of the tree; then we have to store it as a
- node explicitly.*/
- *_binode=binode+1;
- if(binode+1>_nbinodes)return 0;
- _bitree[binode]=-token;
- }
+ /*Read a leaf node:*/
else{
- int i;
- int j;
- /*Fill in a complete binary tree pointing to the internal nodes.*/
- *_binode=binode+3*(ntokens-1);
- if(binode+3*(ntokens-1)>_nbinodes)return 0;
- for(i=1;i<ntokens>>1;i<<=1){
- int child;
- child=binode+3*(2*i-1);
- for(j=0;j<i;j++){
- _bitree[binode+3*(i-1+j)+0]=1;
- _bitree[binode+3*(i-1+j)+1]=(ogg_int16_t)child;
- child+=3;
- _bitree[binode+3*(i-1+j)+2]=(ogg_int16_t)child;
- child+=3;
- }
+ ogg_uint32_t code_bit;
+ int neb;
+ int nentries;
+ int token;
+ /*Don't allow more than 32 spec-tokens per codebook.*/
+ if(++nleaves>32)return TH_EBADHEADER;
+ bits=oc_pack_read(_opb,OC_NDCT_TOKEN_BITS);
+ neb=OC_DCT_TOKEN_MAP_LOG_NENTRIES[bits];
+ token=OC_DCT_TOKEN_MAP[bits];
+ nentries=1<<neb;
+ while(nentries-->0){
+ _tokens[ntokens][0]=(unsigned char)token++;
+ _tokens[ntokens][1]=(unsigned char)(len+neb);
+ ntokens++;
}
- /*And now the last row pointing to the leaf nodes.*/
- for(i=j=0;j<ntokens>>1;j++){
- _bitree[binode+3*((ntokens>>1)-1+j)+0]=1;
- _bitree[binode+3*((ntokens>>1)-1+j)+1]=(ogg_int16_t)-(1<<8|token+i++);
- _bitree[binode+3*((ntokens>>1)-1+j)+2]=(ogg_int16_t)-(1<<8|token+i++);
+ code_bit=0x80000000U>>len-1;
+ while(len>0&&(code&code_bit)){
+ code^=code_bit;
+ code_bit<<=1;
+ len--;
}
+ if(len<=0)break;
+ code|=code_bit;
}
}
- return binode;
+ return ntokens;
}
-/*Finds the depth of shortest branch of the given sub-tree.
- The tree must be binary.
- _bitree: A packed binary Huffman tree.
- _binode: The root of the given sub-tree.
- _bitree[_binode] must be <=1.
- Return: The smallest depth of a leaf node in this sub-tree.
- 0 indicates this sub-tree is a leaf node.*/
-static int oc_huff_tree_mindepth(const ogg_int16_t *_bitree,int _binode){
- int child;
- int depth0;
- int depth1;
- if(_bitree[_binode]<=0)return 0;
- child=_bitree[_binode+1];
- depth0=child<=0?0:oc_huff_tree_mindepth(_bitree,child);
- child=_bitree[_binode+2];
- depth1=child<=0?0:oc_huff_tree_mindepth(_bitree,child);
- return OC_MINI(depth0,depth1)+1;
-}
-
-/*Finds the number of internal nodes at a given depth, plus the number of
- leaves at that depth or shallower.
- The tree must be binary.
- _bitree: A packed binary Huffman tree.
- _binode: The root of the given sub-tree.
- _bitree[_binode] must be <=1.
- Return: The number of unique entries that would be contained in a jump table
- of the given depth.*/
-static int oc_huff_tree_occupancy(const ogg_int16_t *_bitree,int _binode,
- int _depth){
- if(_depth<=0||_bitree[_binode]<=0)return 1;
- else{
- int child1;
- int child2;
- child1=_bitree[_binode+1];
- child2=_bitree[_binode+2];
- return (child1<=0?1:oc_huff_tree_occupancy(_bitree,child1,_depth-1))+
- (child2<=0?1:oc_huff_tree_occupancy(_bitree,child2,_depth-1));
- }
-}
-
-/*Makes a copy of the given Huffman sub-tree.
- _dst: The destination tree.
- _src: The destination tree.
- _node: The index Huffman sub-tree to copy.
- Return: The index of the first available slot after the sub-tree copy.*/
-static int oc_huff_tree_copy(ogg_int16_t *_dst,
- const ogg_int16_t *_src,int _node){
- int n;
- n=_src[_node];
- _dst[_node++]=(ogg_int16_t)n;
- if(n<=0)return _node;
- else{
- int nchildren;
- int ret;
- int i;
- nchildren=1<<n;
- ret=_node+nchildren;
- for(i=0;i<nchildren;i++){
- int child;
- child=_src[_node+i];
- _dst[_node+i]=(ogg_int16_t)child;
- if(child>0){
- /*Note: This assumes that storage for children is in order, and
- consecutive.*/
- ret=oc_huff_tree_copy(_dst,_src,child);
- }
+/*Count how many tokens would be required to fill a subtree at depth _depth.
+ _tokens: A list of internal tokens, in the order they are found in the
+ codebook, and the lengths of their corresponding codewords.
+ _depth: The depth of the desired node in the corresponding tree structure.
+ Return: The number of tokens that belong to that subtree.*/
+static int oc_huff_subtree_tokens(unsigned char _tokens[][2],int _depth){
+ ogg_uint32_t code;
+ int ti;
+ code=0;
+ ti=0;
+ do{
+ if(_tokens[ti][1]-_depth<32)code+=0x80000000U>>_tokens[ti++][1]-_depth;
+ else{
+ /*Because of the expanded internal tokens, we can have codewords as long
+ as 35 bits.
+ A single recursion here is enough to advance past them.*/
+ code++;
+ ti+=oc_huff_subtree_tokens(_tokens+ti,_depth+31);
}
- return ret;
}
+ while(code<0x80000000U);
+ return ti;
}
-static size_t oc_huff_tree_collapse_size(ogg_int16_t *_bitree,int _binode,
- int _depth){
- size_t size;
- int mindepth;
- int depth;
- int threshold;
- int loccupancy;
- int occupancy;
- int child1;
- int child2;
- int n;
- n=_bitree[_binode];
- if(n>0&&_depth>0){
- child1=_bitree[_binode+1];
- child2=_bitree[_binode+2];
- return (child1<=0?0:oc_huff_tree_collapse_size(_bitree,child1,_depth-1))+
- (child2<=0?0:oc_huff_tree_collapse_size(_bitree,child2,_depth-1));
- }
- depth=mindepth=oc_huff_tree_mindepth(_bitree,_binode);
- occupancy=1<<mindepth;
+/*Compute the number of bits to use for a collapsed tree node at the given
+ depth.
+ _tokens: A list of internal tokens, in the order they are found in the
+ codebook, and the lengths of their corresponding codewords.
+ _ntokens: The number of tokens corresponding to this tree node.
+ _depth: The depth of this tree node.
+ Return: The number of bits to use for a collapsed tree node rooted here.
+ This is always at least one, even if this was a leaf node.*/
+static int oc_huff_tree_collapse_depth(unsigned char _tokens[][2],
+ int _ntokens,int _depth){
+ int got_leaves;
+ int loccupancy;
+ int occupancy;
+ int slush;
+ int nbits;
+ int best_nbits;
+ slush=_depth>0?OC_HUFF_SLUSH:OC_ROOT_HUFF_SLUSH;
+ /*It's legal to have a tree with just a single node, which requires no bits
+ to decode and always returns the same token.
+ However, no encoder actually does this (yet).
+ To avoid a special case in oc_huff_token_decode(), we force the number of
+ lookahead bits to be at least one.
+ This will produce a tree that looks ahead one bit and then advances the
+ stream zero bits.*/
+ nbits=1;
+ occupancy=2;
+ got_leaves=1;
do{
+ int ti;
+ if(got_leaves)best_nbits=nbits;
+ nbits++;
+ got_leaves=0;
loccupancy=occupancy;
- occupancy=oc_huff_tree_occupancy(_bitree,_binode,++depth);
- threshold=1<<OC_MAXI(depth-(_binode>0?OC_HUFF_SLUSH:OC_ROOT_HUFF_SLUSH),0);
+ for(occupancy=ti=0;ti<_ntokens;occupancy++){
+ if(_tokens[ti][1]<_depth+nbits)ti++;
+ else if(_tokens[ti][1]==_depth+nbits){
+ got_leaves=1;
+ ti++;
+ }
+ else ti+=oc_huff_subtree_tokens(_tokens+ti,_depth+nbits);
+ }
}
- while(occupancy>loccupancy&&occupancy>=threshold);
- depth--;
- size=oc_huff_node_size(depth);
- if(depth>0){
- child1=_bitree[_binode+1];
- child2=_bitree[_binode+2];
- size+=child1<=0?0:oc_huff_tree_collapse_size(_bitree,child1,depth-1);
- size+=child2<=0?0:oc_huff_tree_collapse_size(_bitree,child2,depth-1);
- }
- return size;
+ while(occupancy>loccupancy&&occupancy*slush>=1<<nbits);
+ return best_nbits;
}
-static int oc_huff_tree_collapse(ogg_int16_t *_tree,int *_node,
- const ogg_int16_t *_bitree,int _binode);
-
-/*Fills the given nodes table with all the children in the sub-tree at the
- given depth.
- The nodes in the sub-tree with a depth less than that stored in the table
- are freed.
- The sub-tree must be binary and complete up until the given depth.
- _tree: The storage for the collapsed Huffman tree.
- _node: The index of the next available storage in the tree.
- _offs: The index of the nodes to fill.
- _bitree: The binary tree to collapse.
- _binode: The index of the root of the sub-tree to fill it with.
- _bitree[_binode] must be <=1 .
- _level: The current level in the table.
- 0 indicates that the current node should be stored, regardless of
- whether it is a leaf node or an internal node.
- _depth: The depth of the nodes to fill the table with, relative to their
- parent.*/
-static void oc_huff_node_fill(ogg_int16_t *_tree,int *_node,int _offs,
- const ogg_int16_t *_bitree,int _binode,int _level,int _depth){
- int leaf;
- int n;
- int i;
- n=_bitree[_binode];
- if(n<=0){
- leaf=-((_depth-_level<<8)|(-n&255));
- for(i=0;i<1<<_level;i++)_tree[_offs+i]=(ogg_int16_t)leaf;
- }
- else if(_level<=0){
- _tree[_offs]=oc_huff_tree_collapse(_tree,_node,_bitree,_binode);
- }
- else{
- int child1;
- int child2;
- _level--;
- child1=_bitree[_binode+1];
- if(child1<=0){
- leaf=-((_depth-_level<<8)|(-child1&255));
- for(i=0;i<1<<_level;i++)_tree[_offs+i]=(ogg_int16_t)leaf;
- }
- else oc_huff_node_fill(_tree,_node,_offs,_bitree,child1,_level,_depth);
- _offs+=1<<_level;
- child2=_bitree[_binode+2];
- if(child2<=0){
- leaf=-((_depth-_level<<8)|(-child2&255));
- for(i=0;i<1<<_level;i++)_tree[_offs+i]=(ogg_int16_t)leaf;
- }
- else oc_huff_node_fill(_tree,_node,_offs,_bitree,child2,_level,_depth);
- }
+/*Determines the size in words of a Huffman tree node that represents a
+ subtree of depth _nbits.
+ _nbits: The depth of the subtree.
+ This must be greater than zero.
+ Return: The number of words required to store the node.*/
+static size_t oc_huff_node_size(int _nbits){
+ return 1+(1<<_nbits);
}
-/*Finds the largest complete sub-tree rooted at the current node and collapses
- it into a single node.
- This procedure is then applied recursively to all the children of that node.
- _tree: The storage for the collapsed Huffman tree.
- _node: The index of the next available storage in the tree.
- _offs: The index of the nodes to fill.
- _bitree: The binary tree to collapse.
- _binode: The index of the root of the sub-tree to fill it with.
- _bitree[_binode] must be <=1 .
- Return: The new root of the collapsed sub-tree.*/
-static int oc_huff_tree_collapse(ogg_int16_t *_tree,int *_node,
- const ogg_int16_t *_bitree,int _binode){
- int mindepth;
- int depth;
- int loccupancy;
- int occupancy;
- int threshold;
- int node;
- depth=mindepth=oc_huff_tree_mindepth(_bitree,_binode);
- occupancy=1<<mindepth;
+/*Produces a collapsed-tree representation of the given token list.
+ _tree: The storage for the collapsed Huffman tree.
+ This may be NULL to compute the required storage size instead of
+ constructing the tree.
+ _tokens: A list of internal tokens, in the order they are found in the
+ codebook, and the lengths of their corresponding codewords.
+ _ntokens: The number of tokens corresponding to this tree node.
+ Return: The number of words required to store the tree.*/
+static size_t oc_huff_tree_collapse(ogg_int16_t *_tree,
+ unsigned char _tokens[][2],int _ntokens){
+ ogg_int16_t node[34];
+ unsigned char depth[34];
+ unsigned char last[34];
+ size_t ntree;
+ int ti;
+ int l;
+ depth[0]=0;
+ last[0]=(unsigned char)(_ntokens-1);
+ ntree=0;
+ ti=0;
+ l=0;
do{
- loccupancy=occupancy;
- occupancy=oc_huff_tree_occupancy(_bitree,_binode,++depth);
- threshold=1<<OC_MAXI(depth-(_binode>0?OC_HUFF_SLUSH:OC_ROOT_HUFF_SLUSH),0);
+ int nbits;
+ nbits=oc_huff_tree_collapse_depth(_tokens+ti,last[l]+1-ti,depth[l]);
+ node[l]=(ogg_int16_t)ntree;
+ ntree+=oc_huff_node_size(nbits);
+ if(_tree!=NULL)_tree[node[l]++]=(ogg_int16_t)nbits;
+ do{
+ while(ti<=last[l]&&_tokens[ti][1]<=depth[l]+nbits){
+ if(_tree!=NULL){
+ ogg_int16_t leaf;
+ int nentries;
+ nentries=1<<depth[l]+nbits-_tokens[ti][1];
+ leaf=(ogg_int16_t)-(_tokens[ti][1]-depth[l]<<8|_tokens[ti][0]);
+ while(nentries-->0)_tree[node[l]++]=leaf;
+ }
+ ti++;
+ }
+ if(ti<=last[l]){
+ /*We need to recurse*/
+ depth[l+1]=(unsigned char)(depth[l]+nbits);
+ if(_tree!=NULL)_tree[node[l]++]=(ogg_int16_t)ntree;
+ l++;
+ last[l]=
+ (unsigned char)(ti+oc_huff_subtree_tokens(_tokens+ti,depth[l])-1);
+ break;
+ }
+ /*Pop back up a level of recursion.*/
+ else if(l-->0)nbits=depth[l+1]-depth[l];
+ }
+ while(l>=0);
}
- while(occupancy>loccupancy&&occupancy>=threshold);
- depth--;
- node=*_node;
- if(depth<=0){
- _tree[node]=_bitree[_binode];
- *_node=node+1;
- }
- else{
- _tree[node]=depth;
- *_node=node+1+(1<<depth);
- oc_huff_node_fill(_tree,_node,node+1,_bitree,_binode,depth,depth);
- }
- return node;
+ while(l>=0);
+ return ntree;
}
/*Unpacks a set of Huffman trees, and reduces them to a collapsed
@@ -505,28 +380,67 @@
Return: 0 on success, or a negative value on error.*/
int oc_huff_trees_unpack(oc_pack_buf *_opb,
ogg_int16_t *_nodes[TH_NHUFFMAN_TABLES]){
+ int ret;
int i;
+ ret=0;
for(i=0;i<TH_NHUFFMAN_TABLES;i++){
- ogg_int16_t nodes[255*3];
- ogg_int16_t *tree;
- size_t size;
- int node;
+ unsigned char tokens[256][2];
+ int ntokens;
+ ogg_int16_t *tree;
+ size_t size;
/*Unpack the full tree into a temporary buffer.*/
- node=0;
- oc_huff_tree_unpack(_opb,nodes,sizeof(nodes)/sizeof(*nodes),&node);
- if(node>sizeof(nodes)/sizeof(*nodes))return TH_EBADHEADER;
- /*Figure out how big the collapsed tree will be.*/
- size=oc_huff_tree_collapse_size(nodes,0,0);
+ ntokens=oc_huff_tree_unpack(_opb,tokens);
+ if(ntokens<0){
+ ret=ntokens;
+ break;
+ }
+ /*Figure out how big the collapsed tree will be and allocate space for it.*/
+ size=oc_huff_tree_collapse(NULL,tokens,ntokens);
+ if(size>32767){
+ /*This should never happen; if it does it means you set OC_HUFF_SLUSH or
+ OC_ROOT_HUFF_SLUSH too large.*/
+ ret=TH_EIMPL;
+ break;
+ }
tree=(ogg_int16_t *)_ogg_malloc(size*sizeof(*tree));
- if(tree==NULL)return TH_EFAULT;
- /*And collapse it.*/
- node=0;
- oc_huff_tree_collapse(tree,&node,nodes,0);
+ if(tree==NULL){
+ ret=TH_EFAULT;
+ break;
+ }
+ /*Construct the collapsed the tree.*/
+ oc_huff_tree_collapse(tree,tokens,ntokens);
_nodes[i]=tree;
}
- return 0;
+ if(ret<0)while(i-->0)_ogg_free(_nodes[i]);
+ return ret;
}
+/*Determines the size in words of a Huffman subtree.
+ _tree: The complete Huffman tree.
+ _node: The index of the root of the desired subtree.
+ Return: The number of words required to store the tree.*/
+static size_t oc_huff_tree_size(const ogg_int16_t *_tree,int _node){
+ size_t size;
+ int nchildren;
+ int n;
+ int i;
+ n=_tree[_node];
+ size=oc_huff_node_size(n);
+ nchildren=1<<n;
+ i=0;
+ do{
+ int child;
+ child=_tree[_node+i+1];
+ if(child<=0)i+=1<<n-(-child>>8);
+ else{
+ size+=oc_huff_tree_size(_tree,child);
+ i++;
+ }
+ }
+ while(i<nchildren);
+ return size;
+}
+
/*Makes a copy of the given set of Huffman trees.
_dst: The array to store the copy in.
_src: The array of trees to copy.*/
@@ -536,17 +450,15 @@
int i;
total=0;
for(i=0;i<TH_NHUFFMAN_TABLES;i++){
- size_t size;
- ogg_int16_t *tree;
+ size_t size;
size=oc_huff_tree_size(_src[i],0);
total+=size;
- tree=(ogg_int16_t *)_ogg_malloc(size*sizeof(*tree));
- if(tree==NULL){
+ _dst[i]=(ogg_int16_t *)_ogg_malloc(size*sizeof(*_dst[i]));
+ if(_dst[i]==NULL){
while(i-->0)_ogg_free(_dst[i]);
return TH_EFAULT;
}
- oc_huff_tree_copy(tree,_src[i],0);
- _dst[i]=tree;
+ memcpy(_dst[i],_src[i],size*sizeof(*_dst[i]));
}
return 0;
}
@@ -571,34 +483,12 @@
long bits;
int node;
int n;
- n=_tree[0];
ptr=_opb->ptr;
window=_opb->window;
stop=_opb->stop;
available=_opb->bits;
- /*Handle the case of a codebook with a single value.
- Branch prediction should make this esoteric case free.*/
- if(n<=0)return -n&255;
- if(n>available){
- for(;;){
- /*We don't bother setting eof because we won't check for it after we've
- started decoding DCT tokens.*/
- if(ptr>=stop){
- available=OC_LOTS_OF_BITS;
- break;
- }
- if(available>OC_PB_WINDOW_SIZE-8)break;
- available+=8;
- window|=(oc_pb_window)*ptr++<<OC_PB_WINDOW_SIZE-available;
- }
- /*Note: We never request more than 24 bits, so there's no need to fill in
- the last partial byte here.*/
- }
- bits=window>>OC_PB_WINDOW_SIZE-n;
- node=_tree[1+bits];
- while(node>0){
- window<<=n;
- available-=n;
+ node=0;
+ for(;;){
n=_tree[node];
if(n>available){
for(;;){
@@ -617,6 +507,9 @@
}
bits=window>>OC_PB_WINDOW_SIZE-n;
node=_tree[node+1+bits];
+ if(node<=0)break;
+ window<<=n;
+ available-=n;
}
node=-node;
n=node>>8;
More information about the commits
mailing list