1233d2500723e5594f3e7c70896ffeeef32b9c950ywan/* 2233d2500723e5594f3e7c70896ffeeef32b9c950ywan * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 3233d2500723e5594f3e7c70896ffeeef32b9c950ywan * 4233d2500723e5594f3e7c70896ffeeef32b9c950ywan * Use of this source code is governed by a BSD-style license 5233d2500723e5594f3e7c70896ffeeef32b9c950ywan * that can be found in the LICENSE file in the root of the source 6233d2500723e5594f3e7c70896ffeeef32b9c950ywan * tree. An additional intellectual property rights grant can be found 7233d2500723e5594f3e7c70896ffeeef32b9c950ywan * in the file PATENTS. All contributing project authors may 8233d2500723e5594f3e7c70896ffeeef32b9c950ywan * be found in the AUTHORS file in the root of the source tree. 9233d2500723e5594f3e7c70896ffeeef32b9c950ywan */ 10233d2500723e5594f3e7c70896ffeeef32b9c950ywan 11233d2500723e5594f3e7c70896ffeeef32b9c950ywan 12233d2500723e5594f3e7c70896ffeeef32b9c950ywan#if CONFIG_DEBUG 13233d2500723e5594f3e7c70896ffeeef32b9c950ywan#include <assert.h> 14233d2500723e5594f3e7c70896ffeeef32b9c950ywan#endif 15233d2500723e5594f3e7c70896ffeeef32b9c950ywan#include <stdio.h> 16233d2500723e5594f3e7c70896ffeeef32b9c950ywan 17233d2500723e5594f3e7c70896ffeeef32b9c950ywan#include "treecoder.h" 18233d2500723e5594f3e7c70896ffeeef32b9c950ywan 19233d2500723e5594f3e7c70896ffeeef32b9c950ywanstatic void tree2tok( 20233d2500723e5594f3e7c70896ffeeef32b9c950ywan struct vp8_token_struct *const p, 21233d2500723e5594f3e7c70896ffeeef32b9c950ywan vp8_tree t, 22233d2500723e5594f3e7c70896ffeeef32b9c950ywan int i, 23233d2500723e5594f3e7c70896ffeeef32b9c950ywan int v, 24233d2500723e5594f3e7c70896ffeeef32b9c950ywan int L 25233d2500723e5594f3e7c70896ffeeef32b9c950ywan) 26233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 27233d2500723e5594f3e7c70896ffeeef32b9c950ywan v += v; 28233d2500723e5594f3e7c70896ffeeef32b9c950ywan ++L; 29233d2500723e5594f3e7c70896ffeeef32b9c950ywan 30233d2500723e5594f3e7c70896ffeeef32b9c950ywan do 31233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 32233d2500723e5594f3e7c70896ffeeef32b9c950ywan const vp8_tree_index j = t[i++]; 33233d2500723e5594f3e7c70896ffeeef32b9c950ywan 34233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (j <= 0) 35233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 36233d2500723e5594f3e7c70896ffeeef32b9c950ywan p[-j].value = v; 37233d2500723e5594f3e7c70896ffeeef32b9c950ywan p[-j].Len = L; 38233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 39233d2500723e5594f3e7c70896ffeeef32b9c950ywan else 40233d2500723e5594f3e7c70896ffeeef32b9c950ywan tree2tok(p, t, j, v, L); 41233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 42233d2500723e5594f3e7c70896ffeeef32b9c950ywan while (++v & 1); 43233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 44233d2500723e5594f3e7c70896ffeeef32b9c950ywan 45233d2500723e5594f3e7c70896ffeeef32b9c950ywanvoid vp8_tokens_from_tree(struct vp8_token_struct *p, vp8_tree t) 46233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 47233d2500723e5594f3e7c70896ffeeef32b9c950ywan tree2tok(p, t, 0, 0, 0); 48233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 49233d2500723e5594f3e7c70896ffeeef32b9c950ywan 50233d2500723e5594f3e7c70896ffeeef32b9c950ywanvoid vp8_tokens_from_tree_offset(struct vp8_token_struct *p, vp8_tree t, 51233d2500723e5594f3e7c70896ffeeef32b9c950ywan int offset) 52233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 53233d2500723e5594f3e7c70896ffeeef32b9c950ywan tree2tok(p - offset, t, 0, 0, 0); 54233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 55233d2500723e5594f3e7c70896ffeeef32b9c950ywan 56233d2500723e5594f3e7c70896ffeeef32b9c950ywanstatic void branch_counts( 57233d2500723e5594f3e7c70896ffeeef32b9c950ywan int n, /* n = size of alphabet */ 58233d2500723e5594f3e7c70896ffeeef32b9c950ywan vp8_token tok [ /* n */ ], 59233d2500723e5594f3e7c70896ffeeef32b9c950ywan vp8_tree tree, 60233d2500723e5594f3e7c70896ffeeef32b9c950ywan unsigned int branch_ct [ /* n-1 */ ] [2], 61233d2500723e5594f3e7c70896ffeeef32b9c950ywan const unsigned int num_events[ /* n */ ] 62233d2500723e5594f3e7c70896ffeeef32b9c950ywan) 63233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 64233d2500723e5594f3e7c70896ffeeef32b9c950ywan const int tree_len = n - 1; 65233d2500723e5594f3e7c70896ffeeef32b9c950ywan int t = 0; 66233d2500723e5594f3e7c70896ffeeef32b9c950ywan 67233d2500723e5594f3e7c70896ffeeef32b9c950ywan#if CONFIG_DEBUG 68233d2500723e5594f3e7c70896ffeeef32b9c950ywan assert(tree_len); 69233d2500723e5594f3e7c70896ffeeef32b9c950ywan#endif 70233d2500723e5594f3e7c70896ffeeef32b9c950ywan 71233d2500723e5594f3e7c70896ffeeef32b9c950ywan do 72233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 73233d2500723e5594f3e7c70896ffeeef32b9c950ywan branch_ct[t][0] = branch_ct[t][1] = 0; 74233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 75233d2500723e5594f3e7c70896ffeeef32b9c950ywan while (++t < tree_len); 76233d2500723e5594f3e7c70896ffeeef32b9c950ywan 77233d2500723e5594f3e7c70896ffeeef32b9c950ywan t = 0; 78233d2500723e5594f3e7c70896ffeeef32b9c950ywan 79233d2500723e5594f3e7c70896ffeeef32b9c950ywan do 80233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 81233d2500723e5594f3e7c70896ffeeef32b9c950ywan int L = tok[t].Len; 82233d2500723e5594f3e7c70896ffeeef32b9c950ywan const int enc = tok[t].value; 83233d2500723e5594f3e7c70896ffeeef32b9c950ywan const unsigned int ct = num_events[t]; 84233d2500723e5594f3e7c70896ffeeef32b9c950ywan 85233d2500723e5594f3e7c70896ffeeef32b9c950ywan vp8_tree_index i = 0; 86233d2500723e5594f3e7c70896ffeeef32b9c950ywan 87233d2500723e5594f3e7c70896ffeeef32b9c950ywan do 88233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 89233d2500723e5594f3e7c70896ffeeef32b9c950ywan const int b = (enc >> --L) & 1; 90233d2500723e5594f3e7c70896ffeeef32b9c950ywan const int j = i >> 1; 91233d2500723e5594f3e7c70896ffeeef32b9c950ywan#if CONFIG_DEBUG 92233d2500723e5594f3e7c70896ffeeef32b9c950ywan assert(j < tree_len && 0 <= L); 93233d2500723e5594f3e7c70896ffeeef32b9c950ywan#endif 94233d2500723e5594f3e7c70896ffeeef32b9c950ywan 95233d2500723e5594f3e7c70896ffeeef32b9c950ywan branch_ct [j] [b] += ct; 96233d2500723e5594f3e7c70896ffeeef32b9c950ywan i = tree[ i + b]; 97233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 98233d2500723e5594f3e7c70896ffeeef32b9c950ywan while (i > 0); 99233d2500723e5594f3e7c70896ffeeef32b9c950ywan 100233d2500723e5594f3e7c70896ffeeef32b9c950ywan#if CONFIG_DEBUG 101233d2500723e5594f3e7c70896ffeeef32b9c950ywan assert(!L); 102233d2500723e5594f3e7c70896ffeeef32b9c950ywan#endif 103233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 104233d2500723e5594f3e7c70896ffeeef32b9c950ywan while (++t < n); 105233d2500723e5594f3e7c70896ffeeef32b9c950ywan 106233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 107233d2500723e5594f3e7c70896ffeeef32b9c950ywan 108233d2500723e5594f3e7c70896ffeeef32b9c950ywan 109233d2500723e5594f3e7c70896ffeeef32b9c950ywanvoid vp8_tree_probs_from_distribution( 110233d2500723e5594f3e7c70896ffeeef32b9c950ywan int n, /* n = size of alphabet */ 111233d2500723e5594f3e7c70896ffeeef32b9c950ywan vp8_token tok [ /* n */ ], 112233d2500723e5594f3e7c70896ffeeef32b9c950ywan vp8_tree tree, 113233d2500723e5594f3e7c70896ffeeef32b9c950ywan vp8_prob probs [ /* n-1 */ ], 114233d2500723e5594f3e7c70896ffeeef32b9c950ywan unsigned int branch_ct [ /* n-1 */ ] [2], 115233d2500723e5594f3e7c70896ffeeef32b9c950ywan const unsigned int num_events[ /* n */ ], 116233d2500723e5594f3e7c70896ffeeef32b9c950ywan unsigned int Pfac, 117233d2500723e5594f3e7c70896ffeeef32b9c950ywan int rd 118233d2500723e5594f3e7c70896ffeeef32b9c950ywan) 119233d2500723e5594f3e7c70896ffeeef32b9c950ywan{ 120233d2500723e5594f3e7c70896ffeeef32b9c950ywan const int tree_len = n - 1; 121233d2500723e5594f3e7c70896ffeeef32b9c950ywan int t = 0; 122233d2500723e5594f3e7c70896ffeeef32b9c950ywan 123233d2500723e5594f3e7c70896ffeeef32b9c950ywan branch_counts(n, tok, tree, branch_ct, num_events); 124233d2500723e5594f3e7c70896ffeeef32b9c950ywan 125233d2500723e5594f3e7c70896ffeeef32b9c950ywan do 126233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 127233d2500723e5594f3e7c70896ffeeef32b9c950ywan const unsigned int *const c = branch_ct[t]; 128233d2500723e5594f3e7c70896ffeeef32b9c950ywan const unsigned int tot = c[0] + c[1]; 129233d2500723e5594f3e7c70896ffeeef32b9c950ywan 130233d2500723e5594f3e7c70896ffeeef32b9c950ywan#if CONFIG_DEBUG 131233d2500723e5594f3e7c70896ffeeef32b9c950ywan assert(tot < (1 << 24)); /* no overflow below */ 132233d2500723e5594f3e7c70896ffeeef32b9c950ywan#endif 133233d2500723e5594f3e7c70896ffeeef32b9c950ywan 134233d2500723e5594f3e7c70896ffeeef32b9c950ywan if (tot) 135233d2500723e5594f3e7c70896ffeeef32b9c950ywan { 136233d2500723e5594f3e7c70896ffeeef32b9c950ywan const unsigned int p = ((c[0] * Pfac) + (rd ? tot >> 1 : 0)) / tot; 137233d2500723e5594f3e7c70896ffeeef32b9c950ywan probs[t] = p < 256 ? (p ? p : 1) : 255; /* agree w/old version for now */ 138233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 139233d2500723e5594f3e7c70896ffeeef32b9c950ywan else 140233d2500723e5594f3e7c70896ffeeef32b9c950ywan probs[t] = vp8_prob_half; 141233d2500723e5594f3e7c70896ffeeef32b9c950ywan } 142233d2500723e5594f3e7c70896ffeeef32b9c950ywan while (++t < tree_len); 143233d2500723e5594f3e7c70896ffeeef32b9c950ywan} 144