Line data    Source code

       1             : /*
       2             :  *  Copyright (c) 2010 The WebM project authors. All Rights Reserved.
       3             :  *
       4             :  *  Use of this source code is governed by a BSD-style license
       5             :  *  that can be found in the LICENSE file in the root of the source
       6             :  *  tree. An additional intellectual property rights grant can be found
       7             :  *  in the file PATENTS.  All contributing project authors may
       8             :  *  be found in the AUTHORS file in the root of the source tree.
       9             :  */
      10             : 
      11             : #include <assert.h>
      12             : #include <stdio.h>
      13             : 
      14             : #include "vp8/common/treecoder.h"
      15             : 
      16           0 : static void tree2tok(struct vp8_token_struct *const p, vp8_tree t, int i, int v,
      17             :                      int L) {
      18           0 :   v += v;
      19           0 :   ++L;
      20             : 
      21             :   do {
      22           0 :     const vp8_tree_index j = t[i++];
      23             : 
      24           0 :     if (j <= 0) {
      25           0 :       p[-j].value = v;
      26           0 :       p[-j].Len = L;
      27             :     } else {
      28           0 :       tree2tok(p, t, j, v, L);
      29             :     }
      30           0 :   } while (++v & 1);
      31           0 : }
      32             : 
      33           0 : void vp8_tokens_from_tree(struct vp8_token_struct *p, vp8_tree t) {
      34           0 :   tree2tok(p, t, 0, 0, 0);
      35           0 : }
      36             : 
      37           0 : void vp8_tokens_from_tree_offset(struct vp8_token_struct *p, vp8_tree t,
      38             :                                  int offset) {
      39           0 :   tree2tok(p - offset, t, 0, 0, 0);
      40           0 : }
      41             : 
      42           0 : static void branch_counts(int n, /* n = size of alphabet */
      43             :                           vp8_token tok[/* n */], vp8_tree tree,
      44             :                           unsigned int branch_ct[/* n-1 */][2],
      45             :                           const unsigned int num_events[/* n */]) {
      46           0 :   const int tree_len = n - 1;
      47           0 :   int t = 0;
      48             : 
      49           0 :   assert(tree_len);
      50             : 
      51             :   do {
      52           0 :     branch_ct[t][0] = branch_ct[t][1] = 0;
      53           0 :   } while (++t < tree_len);
      54             : 
      55           0 :   t = 0;
      56             : 
      57             :   do {
      58           0 :     int L = tok[t].Len;
      59           0 :     const int enc = tok[t].value;
      60           0 :     const unsigned int ct = num_events[t];
      61             : 
      62           0 :     vp8_tree_index i = 0;
      63             : 
      64             :     do {
      65           0 :       const int b = (enc >> --L) & 1;
      66           0 :       const int j = i >> 1;
      67           0 :       assert(j < tree_len && 0 <= L);
      68             : 
      69           0 :       branch_ct[j][b] += ct;
      70           0 :       i = tree[i + b];
      71           0 :     } while (i > 0);
      72             : 
      73           0 :     assert(!L);
      74           0 :   } while (++t < n);
      75           0 : }
      76             : 
      77           0 : void vp8_tree_probs_from_distribution(int n, /* n = size of alphabet */
      78             :                                       vp8_token tok[/* n */], vp8_tree tree,
      79             :                                       vp8_prob probs[/* n-1 */],
      80             :                                       unsigned int branch_ct[/* n-1 */][2],
      81             :                                       const unsigned int num_events[/* n */],
      82             :                                       unsigned int Pfac, int rd) {
      83           0 :   const int tree_len = n - 1;
      84           0 :   int t = 0;
      85             : 
      86           0 :   branch_counts(n, tok, tree, branch_ct, num_events);
      87             : 
      88             :   do {
      89           0 :     const unsigned int *const c = branch_ct[t];
      90           0 :     const unsigned int tot = c[0] + c[1];
      91             : 
      92           0 :     assert(tot < (1 << 24)); /* no overflow below */
      93             : 
      94           0 :     if (tot) {
      95           0 :       const unsigned int p = ((c[0] * Pfac) + (rd ? tot >> 1 : 0)) / tot;
      96           0 :       probs[t] = p < 256 ? (p ? p : 1) : 255; /* agree w/old version for now */
      97             :     } else {
      98           0 :       probs[t] = vp8_prob_half;
      99             :     }
     100           0 :   } while (++t < tree_len);
     101           0 : }