/* * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ // author Kevin Lang, Oath Research #ifndef CPC_COMPRESSOR_HPP_ #define CPC_COMPRESSOR_HPP_ #include "cpc_common.hpp" namespace datasketches { /* * This is a very efficient compressor specialized for use by the CPC Sketch. * There are two very different compression schemes here: one for the sliding window * and another for the table of so-called surprising values. * These two compression schemes are designed for specific probability distributions of entries * in these data structures and make some compromises for performance. As a result * the compression is slightly less effective than theoretically achievable but is very fast. */ // forward declarations template class cpc_sketch_alloc; template class cpc_compressor; // the compressor is not instantiated directly // the sketch implementation uses this global function to statically allocate and construct on the first use template inline cpc_compressor& get_compressor(); template class cpc_compressor { public: void compress(const cpc_sketch_alloc& source, compressed_state& target) const; void uncompress(const compressed_state& source, uncompressed_state& target, uint8_t lg_k, uint64_t num_coupons) const; // methods below are public for testing // This returns the number of compressed words that were actually used. It is the caller's // responsibility to ensure that the compressed_words array is long enough to prevent over-run. size_t low_level_compress_bytes( const uint8_t* byte_array, // input size_t num_bytes_to_encode, const uint16_t* encoding_table, uint32_t* compressed_words // output ) const; void low_level_uncompress_bytes( uint8_t* byte_array, // output size_t num_bytes_to_decode, const uint16_t* decoding_table, const uint32_t* compressed_words, size_t num_compressed_words // input ) const; // Here "pairs" refers to row-column pairs that specify // the positions of surprising values in the bit matrix. // returns the number of compressedWords actually used size_t low_level_compress_pairs( const uint32_t* pair_array, // input size_t num_pairs_to_encode, size_t num_base_bits, uint32_t* compressed_words // output ) const; void low_level_uncompress_pairs( uint32_t* pair_array, // output size_t num_pairs_to_decode, size_t num_base_bits, const uint32_t* compressed_words, // input size_t num_compressed_words // input ) const; private: // These decoding tables are created at library startup time by inverting the encoding tables uint16_t* decoding_tables_for_high_entropy_byte[22] = { // sixteen tables for the steady state (chosen based on the "phase" of C/K) NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, // six more tables for the gradual transition between warmup mode and the steady state. NULL, NULL, NULL, NULL, NULL, NULL }; uint16_t* length_limited_unary_decoding_table65; uint8_t* column_permutations_for_decoding[16] = { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL }; cpc_compressor(); template friend cpc_compressor& get_compressor(); ~cpc_compressor(); void make_decoding_tables(); // call this at startup void free_decoding_tables(); // call this at the end void compress_sparse_flavor(const cpc_sketch_alloc& source, compressed_state& target) const; void compress_hybrid_flavor(const cpc_sketch_alloc& source, compressed_state& target) const; void compress_pinned_flavor(const cpc_sketch_alloc& source, compressed_state& target) const; void compress_sliding_flavor(const cpc_sketch_alloc& source, compressed_state& target) const; void uncompress_sparse_flavor(const compressed_state& source, uncompressed_state& target, uint8_t lg_k) const; void uncompress_hybrid_flavor(const compressed_state& source, uncompressed_state& target, uint8_t lg_k) const; void uncompress_pinned_flavor(const compressed_state& source, uncompressed_state& target, uint8_t lg_k, uint32_t num_coupons) const; void uncompress_sliding_flavor(const compressed_state& source, uncompressed_state& target, uint8_t lg_k, uint32_t num_coupons) const; uint8_t* make_inverse_permutation(const uint8_t* permu, int length); uint16_t* make_decoding_table(const uint16_t* encoding_table, int num_byte_values); void validate_decoding_table(const uint16_t* decoding_table, const uint16_t* encoding_table) const; void compress_surprising_values(const vector_u32& pairs, uint8_t lg_k, compressed_state& result) const; void compress_sliding_window(const uint8_t* window, uint8_t lg_k, uint32_t num_coupons, compressed_state& target) const; vector_u32 uncompress_surprising_values(const uint32_t* data, size_t data_words, size_t num_pairs, uint8_t lg_k, const A& allocator) const; void uncompress_sliding_window(const uint32_t* data, size_t data_words, vector_u8& window, uint8_t lg_k, uint32_t num_coupons) const; static size_t safe_length_for_compressed_pair_buf(uint64_t k, size_t num_pairs, size_t num_base_bits); static size_t safe_length_for_compressed_window_buf(uint64_t k); static uint8_t determine_pseudo_phase(uint8_t lg_k, uint64_t c); static inline vector_u32 tricky_get_pairs_from_window(const uint8_t* window, uint32_t k, uint32_t num_pairs_to_get, uint32_t empty_space, const A& allocator); static inline uint64_t golomb_choose_number_of_base_bits(uint64_t k, uint64_t count); }; } /* namespace datasketches */ #include "cpc_compressor_impl.hpp" #endif