1/*
2 *  Copyright (c) 2013 The WebRTC 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 "webrtc/modules/audio_processing/transient/wpd_tree.h"
12
13#include <assert.h>
14#include <math.h>
15#include <string.h>
16
17#include "webrtc/base/scoped_ptr.h"
18#include "webrtc/modules/audio_processing/transient/dyadic_decimator.h"
19#include "webrtc/modules/audio_processing/transient/wpd_node.h"
20
21namespace webrtc {
22
23WPDTree::WPDTree(size_t data_length, const float* high_pass_coefficients,
24                 const float* low_pass_coefficients, size_t coefficients_length,
25                 int levels)
26    : data_length_(data_length),
27      levels_(levels),
28      num_nodes_((1 << (levels + 1)) - 1) {
29  assert(data_length > (static_cast<size_t>(1) << levels) &&
30         high_pass_coefficients &&
31         low_pass_coefficients &&
32         levels > 0);
33  // Size is 1 more, so we can use the array as 1-based. nodes_[0] is never
34  // allocated.
35  nodes_.reset(new rtc::scoped_ptr<WPDNode>[num_nodes_ + 1]);
36
37  // Create the first node
38  const float kRootCoefficient = 1.f;  // Identity Coefficient.
39  nodes_[1].reset(new WPDNode(data_length, &kRootCoefficient, 1));
40  // Variables used to create the rest of the nodes.
41  size_t index = 1;
42  size_t index_left_child = 0;
43  size_t index_right_child = 0;
44
45  int num_nodes_at_curr_level = 0;
46
47  // Branching each node in each level to create its children. The last level is
48  // not branched (all the nodes of that level are leaves).
49  for (int current_level = 0; current_level < levels; ++current_level) {
50    num_nodes_at_curr_level = 1 << current_level;
51    for (int i = 0; i < num_nodes_at_curr_level; ++i) {
52      index = (1 << current_level) + i;
53      // Obtain the index of the current node children.
54      index_left_child = index * 2;
55      index_right_child = index_left_child + 1;
56      nodes_[index_left_child].reset(new WPDNode(nodes_[index]->length() / 2,
57                                                 low_pass_coefficients,
58                                                 coefficients_length));
59      nodes_[index_right_child].reset(new WPDNode(nodes_[index]->length() / 2,
60                                                  high_pass_coefficients,
61                                                  coefficients_length));
62    }
63  }
64}
65
66WPDTree::~WPDTree() {}
67
68WPDNode* WPDTree::NodeAt(int level, int index) {
69  const int kNumNodesAtLevel = 1 << level;
70  if (level < 0 || level > levels_ || index < 0 || index >= kNumNodesAtLevel) {
71    return NULL;
72  }
73  return nodes_[(1 << level) + index].get();
74}
75
76int WPDTree::Update(const float* data, size_t data_length) {
77  if (!data || data_length != data_length_) {
78    return -1;
79  }
80
81  // Update the root node.
82  int update_result = nodes_[1]->set_data(data, data_length);
83  if (update_result != 0) {
84    return -1;
85  }
86
87  // Variables used to update the rest of the nodes.
88  size_t index = 1;
89  size_t index_left_child = 0;
90  size_t index_right_child = 0;
91
92  int num_nodes_at_curr_level = 0;
93
94  for (int current_level = 0; current_level < levels_; ++current_level) {
95    num_nodes_at_curr_level = 1 << current_level;
96    for (int i = 0; i < num_nodes_at_curr_level; ++i) {
97      index = (1 << current_level) + i;
98      // Obtain the index of the current node children.
99      index_left_child = index * 2;
100      index_right_child = index_left_child + 1;
101
102      update_result = nodes_[index_left_child]->Update(
103          nodes_[index]->data(), nodes_[index]->length());
104      if (update_result != 0) {
105        return -1;
106      }
107
108      update_result = nodes_[index_right_child]->Update(
109          nodes_[index]->data(), nodes_[index]->length());
110      if (update_result != 0) {
111        return -1;
112      }
113    }
114  }
115
116  return 0;
117}
118
119}  // namespace webrtc
120