datasketches-cpp
Loading...
Searching...
No Matches
compact_theta_sketch_parser_impl.hpp
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 */
19
20#ifndef COMPACT_THETA_SKETCH_PARSER_IMPL_HPP_
21#define COMPACT_THETA_SKETCH_PARSER_IMPL_HPP_
22
23#include <iostream>
24#include <iomanip>
25#include <stdexcept>
26
27namespace datasketches {
28
29template<typename T>
30T whole_bytes_to_hold_bits(T bits) {
31 static_assert(std::is_integral<T>::value, "integral type expected");
32 return (bits >> 3) + ((bits & 7) > 0);
33}
34
35template<bool dummy>
36auto compact_theta_sketch_parser<dummy>::parse(const void* ptr, size_t size, uint64_t seed, bool dump_on_error) -> compact_theta_sketch_data {
37 check_memory_size(ptr, size, 8, dump_on_error);
38 checker<true>::check_sketch_type(reinterpret_cast<const uint8_t*>(ptr)[COMPACT_SKETCH_TYPE_BYTE], COMPACT_SKETCH_TYPE);
39 uint8_t serial_version = reinterpret_cast<const uint8_t*>(ptr)[COMPACT_SKETCH_SERIAL_VERSION_BYTE];
40 switch(serial_version) {
41 case 4: {
42 // version 4 sketches are ordered and always have entries (single item in exact mode is v3)
43 const uint16_t seed_hash = reinterpret_cast<const uint16_t*>(ptr)[COMPACT_SKETCH_SEED_HASH_U16];
44 checker<true>::check_seed_hash(seed_hash, compute_seed_hash(seed));
45 const bool has_theta = reinterpret_cast<const uint8_t*>(ptr)[COMPACT_SKETCH_PRE_LONGS_BYTE] > 1;
46 uint64_t theta = theta_constants::MAX_THETA;
47 if (has_theta) {
48 check_memory_size(ptr, size, 16, dump_on_error);
49 theta = reinterpret_cast<const uint64_t*>(ptr)[COMPACT_SKETCH_V4_THETA_U64];
50 }
51 const uint8_t num_entries_bytes = reinterpret_cast<const uint8_t*>(ptr)[COMPACT_SKETCH_V4_NUM_ENTRIES_BYTES_BYTE];
52 check_v4_num_entries_bytes(num_entries_bytes);
53 size_t data_offset_bytes = has_theta ? COMPACT_SKETCH_V4_PACKED_DATA_ESTIMATION_BYTE : COMPACT_SKETCH_V4_PACKED_DATA_EXACT_BYTE;
54 check_memory_size(ptr, size, data_offset_bytes + num_entries_bytes, dump_on_error);
55 uint32_t num_entries = 0;
56 const uint8_t* num_entries_ptr = reinterpret_cast<const uint8_t*>(ptr) + data_offset_bytes;
57 for (unsigned i = 0; i < num_entries_bytes; ++i) {
58 num_entries |= (*num_entries_ptr++) << (i << 3);
59 }
60 data_offset_bytes += num_entries_bytes;
61 const uint8_t entry_bits = reinterpret_cast<const uint8_t*>(ptr)[COMPACT_SKETCH_V4_ENTRY_BITS_BYTE];
62 check_v4_entry_bits(entry_bits);
63 const uint64_t expected_bits = static_cast<uint64_t>(entry_bits) * num_entries;
64 const size_t expected_size_bytes = data_offset_bytes + whole_bytes_to_hold_bits(expected_bits);
65 check_memory_size(ptr, size, expected_size_bytes, dump_on_error);
66 return {false, true, seed_hash, num_entries, theta,
67 reinterpret_cast<const uint8_t*>(ptr) + data_offset_bytes, entry_bits};
68 }
69 case 3: {
70 uint64_t theta = theta_constants::MAX_THETA;
71 const uint16_t seed_hash = reinterpret_cast<const uint16_t*>(ptr)[COMPACT_SKETCH_SEED_HASH_U16];
72 if (reinterpret_cast<const uint8_t*>(ptr)[COMPACT_SKETCH_FLAGS_BYTE] & (1 << COMPACT_SKETCH_IS_EMPTY_FLAG)) {
73 return {true, true, seed_hash, 0, theta, nullptr, 64};
74 }
75 checker<true>::check_seed_hash(seed_hash, compute_seed_hash(seed));
76 const bool has_theta = reinterpret_cast<const uint8_t*>(ptr)[COMPACT_SKETCH_PRE_LONGS_BYTE] > 2;
77 if (has_theta) {
78 check_memory_size(ptr, size, (COMPACT_SKETCH_THETA_U64 + 1) * sizeof(uint64_t), dump_on_error);
79 theta = reinterpret_cast<const uint64_t*>(ptr)[COMPACT_SKETCH_THETA_U64];
80 }
81 if (reinterpret_cast<const uint8_t*>(ptr)[COMPACT_SKETCH_PRE_LONGS_BYTE] == 1) {
82 check_memory_size(ptr, size, 16, dump_on_error);
83 return {false, true, seed_hash, 1, theta, reinterpret_cast<const uint64_t*>(ptr) + COMPACT_SKETCH_SINGLE_ENTRY_U64, 64};
84 }
85 const size_t entries_start_u64 = has_theta ? COMPACT_SKETCH_ENTRIES_ESTIMATION_U64 : COMPACT_SKETCH_ENTRIES_EXACT_U64;
86 check_memory_size(ptr, size, entries_start_u64 * sizeof(uint64_t), dump_on_error);
87 const uint32_t num_entries = reinterpret_cast<const uint32_t*>(ptr)[COMPACT_SKETCH_NUM_ENTRIES_U32];
88 const uint64_t* entries = reinterpret_cast<const uint64_t*>(ptr) + entries_start_u64;
89 const size_t expected_size_bytes = (entries_start_u64 + num_entries) * sizeof(uint64_t);
90 check_memory_size(ptr, size, expected_size_bytes, dump_on_error);
91 const bool is_ordered = reinterpret_cast<const uint8_t*>(ptr)[COMPACT_SKETCH_FLAGS_BYTE] & (1 << COMPACT_SKETCH_IS_ORDERED_FLAG);
92 return {false, is_ordered, seed_hash, num_entries, theta, entries, 64};
93 }
94 case 1: {
95 uint16_t seed_hash = compute_seed_hash(seed);
96 check_memory_size(ptr, size, COMPACT_SKETCH_ENTRIES_ESTIMATION_U64 * sizeof(uint64_t), dump_on_error);
97 const uint32_t num_entries = reinterpret_cast<const uint32_t*>(ptr)[COMPACT_SKETCH_NUM_ENTRIES_U32];
98 uint64_t theta = reinterpret_cast<const uint64_t*>(ptr)[COMPACT_SKETCH_THETA_U64];
99 bool is_empty = (num_entries == 0) && (theta == theta_constants::MAX_THETA);
100 if (is_empty) return {true, true, seed_hash, 0, theta, nullptr, 64};
101 const uint64_t* entries = reinterpret_cast<const uint64_t*>(ptr) + COMPACT_SKETCH_ENTRIES_ESTIMATION_U64;
102 const size_t expected_size_bytes = (COMPACT_SKETCH_ENTRIES_ESTIMATION_U64 + num_entries) * sizeof(uint64_t);
103 check_memory_size(ptr, size, expected_size_bytes, dump_on_error);
104 return {false, true, seed_hash, num_entries, theta, entries, 64};
105 }
106 case 2: {
107 uint8_t preamble_size = reinterpret_cast<const uint8_t*>(ptr)[COMPACT_SKETCH_PRE_LONGS_BYTE];
108 const uint16_t seed_hash = reinterpret_cast<const uint16_t*>(ptr)[COMPACT_SKETCH_SEED_HASH_U16];
109 checker<true>::check_seed_hash(seed_hash, compute_seed_hash(seed));
110 if (preamble_size == 1) {
111 return {true, true, seed_hash, 0, theta_constants::MAX_THETA, nullptr, 64};
112 } else if (preamble_size == 2) {
113 check_memory_size(ptr, size, COMPACT_SKETCH_ENTRIES_EXACT_U64 * sizeof(uint64_t), dump_on_error);
114 const uint32_t num_entries = reinterpret_cast<const uint32_t*>(ptr)[COMPACT_SKETCH_NUM_ENTRIES_U32];
115 if (num_entries == 0) {
116 return {true, true, seed_hash, 0, theta_constants::MAX_THETA, nullptr, 64};
117 } else {
118 const size_t expected_size_bytes = (preamble_size + static_cast<size_t>(num_entries)) << 3;
119 check_memory_size(ptr, size, expected_size_bytes, dump_on_error);
120 const uint64_t* entries = reinterpret_cast<const uint64_t*>(ptr) + COMPACT_SKETCH_ENTRIES_EXACT_U64;
121 return {false, true, seed_hash, num_entries, theta_constants::MAX_THETA, entries, 64};
122 }
123 } else if (preamble_size == 3) {
124 check_memory_size(ptr, size, COMPACT_SKETCH_ENTRIES_ESTIMATION_U64 * sizeof(uint64_t), dump_on_error);
125 const uint32_t num_entries = reinterpret_cast<const uint32_t*>(ptr)[COMPACT_SKETCH_NUM_ENTRIES_U32];
126 uint64_t theta = reinterpret_cast<const uint64_t*>(ptr)[COMPACT_SKETCH_THETA_U64];
127 bool is_empty = (num_entries == 0) && (theta == theta_constants::MAX_THETA);
128 if (is_empty) return {true, true, seed_hash, 0, theta, nullptr, 64};
129 const uint64_t* entries = reinterpret_cast<const uint64_t*>(ptr) + COMPACT_SKETCH_ENTRIES_ESTIMATION_U64;
130 const size_t expected_size_bytes = (COMPACT_SKETCH_ENTRIES_ESTIMATION_U64 + num_entries) * sizeof(uint64_t);
131 check_memory_size(ptr, size, expected_size_bytes, dump_on_error);
132 return {false, true, seed_hash, num_entries, theta, entries, 64};
133 } else {
134 throw std::invalid_argument(std::to_string(preamble_size) + " longs of premable, but expected 1, 2, or 3");
135 }
136 }
137 default:
138 throw std::invalid_argument("unsupported serial version " + std::to_string(serial_version));
139 }
140}
141
142template<bool dummy>
143void compact_theta_sketch_parser<dummy>::check_memory_size(const void* ptr, size_t actual_bytes, size_t expected_bytes, bool dump_on_error) {
144 if (actual_bytes < expected_bytes) throw std::out_of_range("at least " + std::to_string(expected_bytes)
145 + " bytes expected, actual " + std::to_string(actual_bytes)
146 + (dump_on_error ? (", sketch dump: " + hex_dump(reinterpret_cast<const uint8_t*>(ptr), actual_bytes)) : ""));
147}
148
149template<bool dummy>
150void compact_theta_sketch_parser<dummy>::check_v4_entry_bits(uint8_t entry_bits) {
151 // deltas between ordered hashes below 2^63 need 1 to 63 bits
152 if (entry_bits == 0 || entry_bits > 63) {
153 throw std::invalid_argument("entry bits must be in [1, 63], actual " + std::to_string(entry_bits));
154 }
155}
156
157template<bool dummy>
158void compact_theta_sketch_parser<dummy>::check_v4_num_entries_bytes(uint8_t num_entries_bytes) {
159 if (num_entries_bytes == 0 || num_entries_bytes > sizeof(uint32_t)) {
160 throw std::invalid_argument("num entries bytes must be in [1, 4], actual " + std::to_string(num_entries_bytes));
161 }
162}
163
164template<bool dummy>
165std::string compact_theta_sketch_parser<dummy>::hex_dump(const uint8_t* ptr, size_t size) {
166 std::stringstream s;
167 s << std::hex << std::setfill('0') << std::uppercase;
168 for (size_t i = 0; i < size; ++i) s << std::setw(2) << (ptr[i] & 0xff);
169 return s.str();
170}
171
172} /* namespace datasketches */
173
174#endif
datasketches::theta_constants::MAX_THETA
const uint64_t MAX_THETA
max theta - signed max for compatibility with Java
Definition theta_constants.hpp:36
datasketches
DataSketches namespace.
Definition binomial_bounds.hpp:38
Generated by doxygen 1.18.0