1 /*
2  * Copyright (C) 2018 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "utils/container/bit-vector.h"
18 
19 #include <math.h>
20 
21 #include <algorithm>
22 #include <memory>
23 #include <vector>
24 
25 #include "utils/base/logging.h"
26 #include "utils/container/bit-vector_generated.h"
27 
28 namespace libtextclassifier3 {
29 
BitVector(const BitVectorData * bit_vector_data)30 BitVector::BitVector(const BitVectorData* bit_vector_data)
31     : bit_vector_data_(bit_vector_data) {}
32 
GetFromSparseData(int32 index) const33 bool BitVector::GetFromSparseData(int32 index) const {
34   return std::binary_search(
35       bit_vector_data_->sparse_data()->sorted_indices_32()->begin(),
36       bit_vector_data_->sparse_data()->sorted_indices_32()->end(), index);
37 }
38 
GetFromDenseData(int32 index) const39 bool BitVector::GetFromDenseData(int32 index) const {
40   if (index >= bit_vector_data_->dense_data()->size()) {
41     return false;
42   }
43   int32 byte_index = index / 8;
44   uint8 extracted_byte =
45       bit_vector_data_->dense_data()->data()->Get(byte_index);
46   uint8 bit_index = index % 8;
47   return extracted_byte & (1 << bit_index);
48 }
49 
Get(int32 index) const50 bool BitVector::Get(int32 index) const {
51   TC3_DCHECK(index >= 0);
52 
53   if (bit_vector_data_ == nullptr) {
54     return false;
55   }
56   if (bit_vector_data_->dense_data() != nullptr) {
57     return GetFromDenseData(index);
58   }
59   return GetFromSparseData(index);
60 }
61 
CreateSparseBitVectorData(const std::vector<int32> & indices)62 std::unique_ptr<BitVectorDataT> BitVector::CreateSparseBitVectorData(
63     const std::vector<int32>& indices) {
64   auto bit_vector_data = std::make_unique<BitVectorDataT>();
65   bit_vector_data->sparse_data =
66       std::make_unique<libtextclassifier3::SparseBitVectorDataT>();
67   bit_vector_data->sparse_data->sorted_indices_32 = indices;
68   return bit_vector_data;
69 }
70 
CreateDenseBitVectorData(const std::vector<bool> & data)71 std::unique_ptr<BitVectorDataT> BitVector::CreateDenseBitVectorData(
72     const std::vector<bool>& data) {
73   uint8_t temp = 0;
74   std::vector<uint8_t> result;
75   for (int i = 0; i < data.size(); i++) {
76     if (i != 0 && (i % 8) == 0) {
77       result.push_back(temp);
78       temp = 0;
79     }
80     if (data[i]) {
81       temp += (1 << (i % 8));
82     }
83   }
84   if ((data.size() % 8) != 0) {
85     result.push_back(temp);
86   }
87 
88   auto bit_vector_data = std::make_unique<BitVectorDataT>();
89   bit_vector_data->dense_data =
90       std::make_unique<libtextclassifier3::DenseBitVectorDataT>();
91   bit_vector_data->dense_data->data = result;
92   bit_vector_data->dense_data->size = data.size();
93   return bit_vector_data;
94 }
95 
96 }  // namespace libtextclassifier3
97