diff options
author | eeight <eeight@yandex-team.ru> | 2022-02-10 16:46:19 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:46:19 +0300 |
commit | bd085aee9b4f7a0bee302ce687964ffb7098f986 (patch) | |
tree | 1a2c5ffcf89eb53ecd79dbc9bc0a195c27404d0c /library/cpp/codecs | |
parent | 475c0a46f28166e83fd263badc7546377cddcabe (diff) | |
download | ydb-bd085aee9b4f7a0bee302ce687964ffb7098f986.tar.gz |
Restoring authorship annotation for <eeight@yandex-team.ru>. Commit 2 of 2.
Diffstat (limited to 'library/cpp/codecs')
-rw-r--r-- | library/cpp/codecs/codecs.h | 2 | ||||
-rw-r--r-- | library/cpp/codecs/codecs_registry.cpp | 8 | ||||
-rw-r--r-- | library/cpp/codecs/codecs_registry.h | 2 | ||||
-rw-r--r-- | library/cpp/codecs/comptable_codec.cpp | 2 | ||||
-rw-r--r-- | library/cpp/codecs/delta_codec.h | 4 | ||||
-rw-r--r-- | library/cpp/codecs/float_huffman.cpp | 656 | ||||
-rw-r--r-- | library/cpp/codecs/float_huffman.h | 88 | ||||
-rw-r--r-- | library/cpp/codecs/float_huffman_bench/main.cpp | 290 | ||||
-rw-r--r-- | library/cpp/codecs/float_huffman_bench/ya.make | 26 | ||||
-rw-r--r-- | library/cpp/codecs/huffman_codec.h | 2 | ||||
-rw-r--r-- | library/cpp/codecs/pfor_codec.h | 2 | ||||
-rw-r--r-- | library/cpp/codecs/solar_codec.h | 2 | ||||
-rw-r--r-- | library/cpp/codecs/ut/float_huffman_ut.cpp | 40 | ||||
-rw-r--r-- | library/cpp/codecs/ya.make | 2 |
14 files changed, 563 insertions, 563 deletions
diff --git a/library/cpp/codecs/codecs.h b/library/cpp/codecs/codecs.h index 6716574b9e..cc5e72b285 100644 --- a/library/cpp/codecs/codecs.h +++ b/library/cpp/codecs/codecs.h @@ -10,7 +10,7 @@ #include <util/stream/input.h> #include <util/stream/output.h> -#include <util/string/cast.h> +#include <util/string/cast.h> #include <util/string/vector.h> #include <util/system/tls.h> #include <util/ysaveload.h> diff --git a/library/cpp/codecs/codecs_registry.cpp b/library/cpp/codecs/codecs_registry.cpp index 05caa50d58..17d07062ab 100644 --- a/library/cpp/codecs/codecs_registry.cpp +++ b/library/cpp/codecs/codecs_registry.cpp @@ -9,7 +9,7 @@ #include <library/cpp/blockcodecs/codecs.h> #include <util/string/builder.h> -#include <util/string/cast.h> +#include <util/string/cast.h> namespace NCodecs { TCodecPtr ICodec::GetInstance(TStringBuf name) { @@ -24,7 +24,7 @@ namespace NCodecs { void TCodecRegistry::RegisterFactory(TFactoryPtr fac) { TVector<TString> names = fac->ListNames(); for (const auto& name : names) { - Y_VERIFY(!Registry.contains(name), "already has %s", name.data()); + Y_VERIFY(!Registry.contains(name), "already has %s", name.data()); Registry[name] = fac; } } @@ -37,7 +37,7 @@ namespace NCodecs { } if (TStringBuf::npos == name.find(':')) { - Y_ENSURE_EX(Registry.contains(name), TNoCodecException(name)); + Y_ENSURE_EX(Registry.contains(name), TNoCodecException(name)); return Registry.find(name)->second->MakeCodec(name); } else { TPipelineCodec* pipe = new TPipelineCodec; @@ -190,7 +190,7 @@ namespace NCodecs { } TCodecPtr MakeCodec(TStringBuf name) const override { - if (!Registry.contains(name)) { + if (!Registry.contains(name)) { ythrow TNoCodecException(name); } return Registry.find(name)->second; diff --git a/library/cpp/codecs/codecs_registry.h b/library/cpp/codecs/codecs_registry.h index 3f2e994320..53710310d5 100644 --- a/library/cpp/codecs/codecs_registry.h +++ b/library/cpp/codecs/codecs_registry.h @@ -1,7 +1,7 @@ #pragma once #include "codecs.h" -#include <util/string/cast.h> +#include <util/string/cast.h> namespace NCodecs { struct TNoCodecException : TCodecException { diff --git a/library/cpp/codecs/comptable_codec.cpp b/library/cpp/codecs/comptable_codec.cpp index 0fa8104369..476b8ada80 100644 --- a/library/cpp/codecs/comptable_codec.cpp +++ b/library/cpp/codecs/comptable_codec.cpp @@ -1,7 +1,7 @@ #include "comptable_codec.h" #include <library/cpp/comptable/comptable.h> -#include <util/string/cast.h> +#include <util/string/cast.h> namespace NCodecs { class TCompTableCodec::TImpl: public TAtomicRefCount<TImpl> { diff --git a/library/cpp/codecs/delta_codec.h b/library/cpp/codecs/delta_codec.h index 78dbd8f1ee..21325825e6 100644 --- a/library/cpp/codecs/delta_codec.h +++ b/library/cpp/codecs/delta_codec.h @@ -4,8 +4,8 @@ #include <util/generic/array_ref.h> #include <util/generic/typetraits.h> -#include <util/generic/bitops.h> -#include <util/string/cast.h> +#include <util/generic/bitops.h> +#include <util/string/cast.h> namespace NCodecs { template <typename T = ui64, bool UnsignedDelta = true> diff --git a/library/cpp/codecs/float_huffman.cpp b/library/cpp/codecs/float_huffman.cpp index 9029877023..c4a8bd228f 100644 --- a/library/cpp/codecs/float_huffman.cpp +++ b/library/cpp/codecs/float_huffman.cpp @@ -1,333 +1,333 @@ #include "float_huffman.h" -#include <util/generic/array_ref.h> -#include <util/generic/bitops.h> -#include <util/generic/cast.h> -#include <util/generic/yexception.h> -#include <util/system/unaligned_mem.h> -#include <util/system/yassert.h> -#include <util/stream/format.h> - -namespace NCodecs::NFloatHuff { - namespace { - struct THuffEntry { - ui32 CodeBase; - ui16 Prefix; - int PrefLength; - int CodeLength; - int TotalLength; - ui32 Mask; - ui64 Offset; - - THuffEntry() = default; - - constexpr THuffEntry(ui32 codeBase, ui16 prefix, int prefLength, int codeLength) - : CodeBase(codeBase) - , Prefix(prefix) - , PrefLength(prefLength) - , CodeLength(codeLength) - , TotalLength(prefLength + codeLength) - , Mask(Mask64(codeLength)) - , Offset(-(ui64(codeBase) << prefLength) + prefix) - {} - - bool Fit(ui32 code) const { - return code >= CodeBase && code < CodeBase + (1ULL << CodeLength); - } - }; - - // NB. There is a typo in the penultimate line (34 instead of 24). It was there from the very - // first commit and we cannot fix it without breaking all the clients. - constexpr THuffEntry entries[16] = { - {0x00000000, 0x01, 1, 0}, // Only +0.0f, 1 bit, prefix [1] - {0x3f800000, 0x0e, 4, 0}, // Only +1.0f, 4 bits, prefix [0111] - {0x3f700000, 0x08, 5, 20}, // [0.9375, 1.0), 25 bits, prefix [00010] - {0x3f000000, 0x00, 5, 20}, // [0.5, 0.5625), 25 bits, prefx [00000] - {0x3f400000, 0x06, 6, 20}, // [0.75, 0.8125), 26 bits, prefix [011000] - {0x3f500000, 0x22, 6, 20}, // [0.8125, 0.875), 26 bits, prefix [010001] - {0x3f200000, 0x02, 6, 20}, // [0.625, 0.6875), 26 bits, prefix [010000] - {0x3f100000, 0x38, 6, 20}, // [0.5625, 0.625), 26 bits, prefix [000111] - {0x3f600000, 0x18, 6, 20}, // [0.875, 0.9375), 26 bits, prefix [000110] - {0x3f300000, 0x30, 6, 20}, // [0.6875, 0.75), 26 bits, prefix [000011] - {0x3e800000, 0x10, 6, 20}, // [0.25, 0.28125), 26 bits, prefix [000010] - {0x3e000000, 0x04, 3, 24}, // [0.125, 0.5), 27 bits, prefix [001] - {0x3d000000, 0x0a, 4, 24}, // [0.03125, 0.125), 28 bits, prefix [0101] - {0x3c000000, 0x12, 5, 24}, // [0.0078125, 0.03125), 29 bits, prefix [01001] - {0x3b000000, 0x26, 6, 34}, // [0.001953125, end of range), 40 bits, prefix [011001] - {0x00000000, 0x16, 5, 32}, // whole range, 37 bits, prefix [01101] +#include <util/generic/array_ref.h> +#include <util/generic/bitops.h> +#include <util/generic/cast.h> +#include <util/generic/yexception.h> +#include <util/system/unaligned_mem.h> +#include <util/system/yassert.h> +#include <util/stream/format.h> + +namespace NCodecs::NFloatHuff { + namespace { + struct THuffEntry { + ui32 CodeBase; + ui16 Prefix; + int PrefLength; + int CodeLength; + int TotalLength; + ui32 Mask; + ui64 Offset; + + THuffEntry() = default; + + constexpr THuffEntry(ui32 codeBase, ui16 prefix, int prefLength, int codeLength) + : CodeBase(codeBase) + , Prefix(prefix) + , PrefLength(prefLength) + , CodeLength(codeLength) + , TotalLength(prefLength + codeLength) + , Mask(Mask64(codeLength)) + , Offset(-(ui64(codeBase) << prefLength) + prefix) + {} + + bool Fit(ui32 code) const { + return code >= CodeBase && code < CodeBase + (1ULL << CodeLength); + } + }; + + // NB. There is a typo in the penultimate line (34 instead of 24). It was there from the very + // first commit and we cannot fix it without breaking all the clients. + constexpr THuffEntry entries[16] = { + {0x00000000, 0x01, 1, 0}, // Only +0.0f, 1 bit, prefix [1] + {0x3f800000, 0x0e, 4, 0}, // Only +1.0f, 4 bits, prefix [0111] + {0x3f700000, 0x08, 5, 20}, // [0.9375, 1.0), 25 bits, prefix [00010] + {0x3f000000, 0x00, 5, 20}, // [0.5, 0.5625), 25 bits, prefx [00000] + {0x3f400000, 0x06, 6, 20}, // [0.75, 0.8125), 26 bits, prefix [011000] + {0x3f500000, 0x22, 6, 20}, // [0.8125, 0.875), 26 bits, prefix [010001] + {0x3f200000, 0x02, 6, 20}, // [0.625, 0.6875), 26 bits, prefix [010000] + {0x3f100000, 0x38, 6, 20}, // [0.5625, 0.625), 26 bits, prefix [000111] + {0x3f600000, 0x18, 6, 20}, // [0.875, 0.9375), 26 bits, prefix [000110] + {0x3f300000, 0x30, 6, 20}, // [0.6875, 0.75), 26 bits, prefix [000011] + {0x3e800000, 0x10, 6, 20}, // [0.25, 0.28125), 26 bits, prefix [000010] + {0x3e000000, 0x04, 3, 24}, // [0.125, 0.5), 27 bits, prefix [001] + {0x3d000000, 0x0a, 4, 24}, // [0.03125, 0.125), 28 bits, prefix [0101] + {0x3c000000, 0x12, 5, 24}, // [0.0078125, 0.03125), 29 bits, prefix [01001] + {0x3b000000, 0x26, 6, 34}, // [0.001953125, end of range), 40 bits, prefix [011001] + {0x00000000, 0x16, 5, 32}, // whole range, 37 bits, prefix [01101] }; [[noreturn]] Y_NO_INLINE void ThrowInvalidOffset(size_t size, size_t byteOffset) { - ythrow yexception() << - "Decompression error: requested decoding 8 bytes past end of input buffer of " << size << " bytes size at position " << byteOffset << ". "; - } - - struct THuffInfo { - constexpr THuffInfo() { - for (size_t i = 0; i < 64; ++i) { - bool init = false; - for (size_t j = 0; j != 16; ++j) { - ui16 prefix = i & Mask64(entries[j].PrefLength); - if (entries[j].Prefix == prefix) { - init = true; - DecodeLookup[i] = entries[j]; - break; - } - } - Y_ASSERT(init); - } - - for (ui32 i = 0; i < (1 << 12); ++i) { - // First two entries (+0.0f and +1.0f) are not present in the lookup, they are handled separately - for (int value = 2; value < 16; ++value) { - if (entries[value].Fit(i << 20)) { - EncodeLookup[i] = value; - break; - } - } - } - } - - std::pair<ui64, int> GetCode(ui32 value) const { - // Zeros are handled separately in the main loop - Y_ASSERT(value != 0); - - if (value == 0x3f800000) { - return {0x0e, 4}; - } - - const auto& entry = entries[EncodeLookup[value >> 20]]; - - return { - (ui64(value) << entry.PrefLength) + entry.Offset, - entry.TotalLength - }; - } - - THuffEntry DecodeLookup[64]; - ui8 EncodeLookup[1 << 12]; - }; - - const THuffInfo huffInfo; - /// End Of Stream - const ui32 EOS = ui32(-1); - } - - TString Encode(TArrayRef<const float> factors) { - TString result; - result.resize((factors.size() + 1) * 40 / 8 + 8, 0); // Max code length is 40 bits - int usedBits = 0; - ui64 buffer = 0; - char* writePtr = result.begin(); - - auto writeBits = [&](ui64 code, int size) { - const auto bitsToTransfer = Min(size, 64 - usedBits); - buffer |= (code << usedBits); - usedBits += bitsToTransfer; - if (usedBits == 64) { - memcpy(writePtr, &buffer, 8); - usedBits = size - bitsToTransfer; - if (bitsToTransfer != 64) { - buffer = code >> bitsToTransfer; - } else { - buffer = 0; - } - writePtr += 8; - } - }; - - for (size_t i = 0; i != factors.size();) { - if (BitCast<ui32>(factors[i]) == 0) { - int zeroCount = 1; - for (;;) { - ++i; - if (i == factors.size() || BitCast<ui32>(factors[i]) != 0) { - break; - } - ++zeroCount; - } - for (; zeroCount >= 64; zeroCount -= 64) { - writeBits(ui64(-1), 64); - } - writeBits(Mask64(zeroCount), zeroCount); - } else { - const auto [code, codeSize] = huffInfo.GetCode(BitCast<ui32>(factors[i])); - writeBits(code, codeSize); - ++i; - } - } - // Write EOS. - // We use precomputed constants instead of the following: - // auto [code, codeSize] = huffInfo.GetCode(EOS); - // writeBits(code, codeSize); - writeBits(211527139302, 40); - memcpy(writePtr, &buffer, 8); - result.resize(writePtr - result.begin() + usedBits / 8 + 8); - - return result; - } - - TDecoder::TDecoder(TStringBuf data) - : State{ - .Workspace = data.size() < 8 ? ThrowInvalidOffset(data.size(), 0), 0 : ReadUnaligned<ui64>(data.data()), - .WorkspaceSize = 64, - .Position = 8, - .Data = data - } - { - FillDecodeBuffer(); - } - - TVector<float> TDecoder::DecodeAll(size_t sizeHint) { - TVector<float> result; - result.reserve(sizeHint); - - while (Begin != End) { - result.insert(result.end(), Begin, End); - FillDecodeBuffer(); - } - return result; - } - - size_t TDecoder::Decode(TArrayRef<float> dest) { - size_t count = 0; - while (count < dest.size()) { - if (dest.size() - count < size_t(End - Begin)) { - const auto size = dest.size() - count; - std::copy(Begin, Begin + size, dest.data() + count); - Begin += size; - return dest.size(); - } else { - std::copy(Begin, End, dest.data() + count); - count += End - Begin; - FillDecodeBuffer(); - if (Begin == End) { - break; - } - } - } - return count; - } - - size_t TDecoder::Skip(size_t count) { - size_t skippedCount = 0; - while (skippedCount < count) { - if (count - skippedCount < size_t(End - Begin)) { - const auto size = count - skippedCount; - Begin += size; - return count; - } else { - skippedCount += End - Begin; - FillDecodeBuffer(); - if (Begin == End) { - break; - } - } - } - return skippedCount; - } - - bool TDecoder::HasMore() const { - return Begin != End; - } - - void TDecoder::FillDecodeBuffer() { - Begin = DecodeBuffer.data(); - End = DecodeBuffer.data(); - - if (HitEos) { - return; - } - - // This helps to keep most of the variables in the registers. - float* end = End; - TState state = State; - - // It is faster to just zero all the memory here in one go - // and then avoid inner loop when writing zeros. There we - // can just increment end pointer. - std::fill(DecodeBuffer.begin(), DecodeBuffer.end(), 0.0f); - - // Make sure that inside the loop we always have space to put 64 zeros and one other - // value. - float* cap = DecodeBuffer.data() + DecodeBuffer.size() - 64 - 1; - - while (end < cap) { - if (state.Workspace % 2 == 1) { - // Decode zeros - // There we can just scan whole state.Workspace for ones because it contains - // zeros outside of the WorkspaceSize bits. - const auto negWorkspace = ~state.Workspace; - const int zeroCount = negWorkspace ? CountTrailingZeroBits(negWorkspace) : 64; - end += zeroCount; - state.SkipBits(zeroCount); - continue; - } - if (state.PeekBits(4) == 0x0e) { - *end++ = 1.0f; - state.SkipBits(4); - continue; - } - const auto& entry = huffInfo.DecodeLookup[state.PeekBits(6)]; - const auto code = ui32((state.NextBitsUnmasked(entry.TotalLength) >> entry.PrefLength) & entry.Mask) + entry.CodeBase; - if (Y_UNLIKELY(code == EOS)) { - HitEos = true; - break; - } - *end++ = BitCast<float>(code); - } - - End = end; - State = state; - } - - ui64 TDecoder::TState::PeekBits(int count) { - if (WorkspaceSize > count) { - return Workspace & Mask64(count); - } else { - if (Y_UNLIKELY(Position + 8 > Data.size())) { - ThrowInvalidOffset(Data.size(), Position); - } - return (Workspace | (ReadUnaligned<ui64>(Data.data() + Position) << WorkspaceSize)) & Mask64(count); - } - } - - ui64 TDecoder::TState::NextBitsUnmasked(int count) { - if (WorkspaceSize > count) { - const auto result = Workspace; - Workspace >>= count; - WorkspaceSize -= count; - return result; - } else { - if (Y_UNLIKELY(Position + 8 > Data.size())) { - ThrowInvalidOffset(Data.size(), Position); - } - ui64 result = Workspace; - Workspace = ReadUnaligned<ui64>(Data.data() + Position); - Position += 8; - result |= Workspace << WorkspaceSize; - Workspace >>= count - WorkspaceSize; - WorkspaceSize += 64 - count; - return result; - } - } - - void TDecoder::TState::SkipBits(int count) { - if (WorkspaceSize > count) { - Workspace >>= count; - WorkspaceSize -= count; - } else { - if (Y_UNLIKELY(Position + 8 > Data.size())) { - ThrowInvalidOffset(Data.size(), Position); - } - Workspace = ReadUnaligned<ui64>(Data.data() + Position); - Position += 8; - Workspace >>= count - WorkspaceSize; - WorkspaceSize += 64 - count; - } - } - - TVector<float> Decode(TStringBuf data, size_t sizeHint) { - return TDecoder(data).DecodeAll(sizeHint); - } -} // namespace NCodecs::NFloatHuff + ythrow yexception() << + "Decompression error: requested decoding 8 bytes past end of input buffer of " << size << " bytes size at position " << byteOffset << ". "; + } + + struct THuffInfo { + constexpr THuffInfo() { + for (size_t i = 0; i < 64; ++i) { + bool init = false; + for (size_t j = 0; j != 16; ++j) { + ui16 prefix = i & Mask64(entries[j].PrefLength); + if (entries[j].Prefix == prefix) { + init = true; + DecodeLookup[i] = entries[j]; + break; + } + } + Y_ASSERT(init); + } + + for (ui32 i = 0; i < (1 << 12); ++i) { + // First two entries (+0.0f and +1.0f) are not present in the lookup, they are handled separately + for (int value = 2; value < 16; ++value) { + if (entries[value].Fit(i << 20)) { + EncodeLookup[i] = value; + break; + } + } + } + } + + std::pair<ui64, int> GetCode(ui32 value) const { + // Zeros are handled separately in the main loop + Y_ASSERT(value != 0); + + if (value == 0x3f800000) { + return {0x0e, 4}; + } + + const auto& entry = entries[EncodeLookup[value >> 20]]; + + return { + (ui64(value) << entry.PrefLength) + entry.Offset, + entry.TotalLength + }; + } + + THuffEntry DecodeLookup[64]; + ui8 EncodeLookup[1 << 12]; + }; + + const THuffInfo huffInfo; + /// End Of Stream + const ui32 EOS = ui32(-1); + } + + TString Encode(TArrayRef<const float> factors) { + TString result; + result.resize((factors.size() + 1) * 40 / 8 + 8, 0); // Max code length is 40 bits + int usedBits = 0; + ui64 buffer = 0; + char* writePtr = result.begin(); + + auto writeBits = [&](ui64 code, int size) { + const auto bitsToTransfer = Min(size, 64 - usedBits); + buffer |= (code << usedBits); + usedBits += bitsToTransfer; + if (usedBits == 64) { + memcpy(writePtr, &buffer, 8); + usedBits = size - bitsToTransfer; + if (bitsToTransfer != 64) { + buffer = code >> bitsToTransfer; + } else { + buffer = 0; + } + writePtr += 8; + } + }; + + for (size_t i = 0; i != factors.size();) { + if (BitCast<ui32>(factors[i]) == 0) { + int zeroCount = 1; + for (;;) { + ++i; + if (i == factors.size() || BitCast<ui32>(factors[i]) != 0) { + break; + } + ++zeroCount; + } + for (; zeroCount >= 64; zeroCount -= 64) { + writeBits(ui64(-1), 64); + } + writeBits(Mask64(zeroCount), zeroCount); + } else { + const auto [code, codeSize] = huffInfo.GetCode(BitCast<ui32>(factors[i])); + writeBits(code, codeSize); + ++i; + } + } + // Write EOS. + // We use precomputed constants instead of the following: + // auto [code, codeSize] = huffInfo.GetCode(EOS); + // writeBits(code, codeSize); + writeBits(211527139302, 40); + memcpy(writePtr, &buffer, 8); + result.resize(writePtr - result.begin() + usedBits / 8 + 8); + + return result; + } + + TDecoder::TDecoder(TStringBuf data) + : State{ + .Workspace = data.size() < 8 ? ThrowInvalidOffset(data.size(), 0), 0 : ReadUnaligned<ui64>(data.data()), + .WorkspaceSize = 64, + .Position = 8, + .Data = data + } + { + FillDecodeBuffer(); + } + + TVector<float> TDecoder::DecodeAll(size_t sizeHint) { + TVector<float> result; + result.reserve(sizeHint); + + while (Begin != End) { + result.insert(result.end(), Begin, End); + FillDecodeBuffer(); + } + return result; + } + + size_t TDecoder::Decode(TArrayRef<float> dest) { + size_t count = 0; + while (count < dest.size()) { + if (dest.size() - count < size_t(End - Begin)) { + const auto size = dest.size() - count; + std::copy(Begin, Begin + size, dest.data() + count); + Begin += size; + return dest.size(); + } else { + std::copy(Begin, End, dest.data() + count); + count += End - Begin; + FillDecodeBuffer(); + if (Begin == End) { + break; + } + } + } + return count; + } + + size_t TDecoder::Skip(size_t count) { + size_t skippedCount = 0; + while (skippedCount < count) { + if (count - skippedCount < size_t(End - Begin)) { + const auto size = count - skippedCount; + Begin += size; + return count; + } else { + skippedCount += End - Begin; + FillDecodeBuffer(); + if (Begin == End) { + break; + } + } + } + return skippedCount; + } + + bool TDecoder::HasMore() const { + return Begin != End; + } + + void TDecoder::FillDecodeBuffer() { + Begin = DecodeBuffer.data(); + End = DecodeBuffer.data(); + + if (HitEos) { + return; + } + + // This helps to keep most of the variables in the registers. + float* end = End; + TState state = State; + + // It is faster to just zero all the memory here in one go + // and then avoid inner loop when writing zeros. There we + // can just increment end pointer. + std::fill(DecodeBuffer.begin(), DecodeBuffer.end(), 0.0f); + + // Make sure that inside the loop we always have space to put 64 zeros and one other + // value. + float* cap = DecodeBuffer.data() + DecodeBuffer.size() - 64 - 1; + + while (end < cap) { + if (state.Workspace % 2 == 1) { + // Decode zeros + // There we can just scan whole state.Workspace for ones because it contains + // zeros outside of the WorkspaceSize bits. + const auto negWorkspace = ~state.Workspace; + const int zeroCount = negWorkspace ? CountTrailingZeroBits(negWorkspace) : 64; + end += zeroCount; + state.SkipBits(zeroCount); + continue; + } + if (state.PeekBits(4) == 0x0e) { + *end++ = 1.0f; + state.SkipBits(4); + continue; + } + const auto& entry = huffInfo.DecodeLookup[state.PeekBits(6)]; + const auto code = ui32((state.NextBitsUnmasked(entry.TotalLength) >> entry.PrefLength) & entry.Mask) + entry.CodeBase; + if (Y_UNLIKELY(code == EOS)) { + HitEos = true; + break; + } + *end++ = BitCast<float>(code); + } + + End = end; + State = state; + } + + ui64 TDecoder::TState::PeekBits(int count) { + if (WorkspaceSize > count) { + return Workspace & Mask64(count); + } else { + if (Y_UNLIKELY(Position + 8 > Data.size())) { + ThrowInvalidOffset(Data.size(), Position); + } + return (Workspace | (ReadUnaligned<ui64>(Data.data() + Position) << WorkspaceSize)) & Mask64(count); + } + } + + ui64 TDecoder::TState::NextBitsUnmasked(int count) { + if (WorkspaceSize > count) { + const auto result = Workspace; + Workspace >>= count; + WorkspaceSize -= count; + return result; + } else { + if (Y_UNLIKELY(Position + 8 > Data.size())) { + ThrowInvalidOffset(Data.size(), Position); + } + ui64 result = Workspace; + Workspace = ReadUnaligned<ui64>(Data.data() + Position); + Position += 8; + result |= Workspace << WorkspaceSize; + Workspace >>= count - WorkspaceSize; + WorkspaceSize += 64 - count; + return result; + } + } + + void TDecoder::TState::SkipBits(int count) { + if (WorkspaceSize > count) { + Workspace >>= count; + WorkspaceSize -= count; + } else { + if (Y_UNLIKELY(Position + 8 > Data.size())) { + ThrowInvalidOffset(Data.size(), Position); + } + Workspace = ReadUnaligned<ui64>(Data.data() + Position); + Position += 8; + Workspace >>= count - WorkspaceSize; + WorkspaceSize += 64 - count; + } + } + + TVector<float> Decode(TStringBuf data, size_t sizeHint) { + return TDecoder(data).DecodeAll(sizeHint); + } +} // namespace NCodecs::NFloatHuff diff --git a/library/cpp/codecs/float_huffman.h b/library/cpp/codecs/float_huffman.h index 0fc1573d8e..786a8eae1d 100644 --- a/library/cpp/codecs/float_huffman.h +++ b/library/cpp/codecs/float_huffman.h @@ -1,50 +1,50 @@ #pragma once -#include <util/generic/array_ref.h> +#include <util/generic/array_ref.h> #include <util/generic/vector.h> #include <util/generic/strbuf.h> -#include <array> - -namespace NCodecs::NFloatHuff { - TString Encode(TArrayRef<const float> factors); - - class TDecoder { - public: - explicit TDecoder(TStringBuf data); - - TVector<float> DecodeAll(size_t sizeHint = 0); - - // Returns number of decoded floats. May be fewer than requested if the EOS is found. - size_t Decode(TArrayRef<float> dest); - - // Returns the number of skipped values. - size_t Skip(size_t count); - - bool HasMore() const; - - private: - struct TState { - ui64 Workspace = 0; - int WorkspaceSize = 0; - ui64 Position = 0; - TStringBuf Data; - - ui64 NextBitsUnmasked(int count); // The upper 64 - count bits may be arbitrary - ui64 PeekBits(int count); - void SkipBits(int count); - }; - - void FillDecodeBuffer(); - - TState State; - std::array<float, 128> DecodeBuffer; - // The range of already decompressed numbers inside the DecodeBuffer. - // Always kept non-empty until the EOS is encountered. - float* Begin; - float* End; - bool HitEos = false; - }; - - TVector<float> Decode(TStringBuf data, size_t sizeHint = 0); +#include <array> + +namespace NCodecs::NFloatHuff { + TString Encode(TArrayRef<const float> factors); + + class TDecoder { + public: + explicit TDecoder(TStringBuf data); + + TVector<float> DecodeAll(size_t sizeHint = 0); + + // Returns number of decoded floats. May be fewer than requested if the EOS is found. + size_t Decode(TArrayRef<float> dest); + + // Returns the number of skipped values. + size_t Skip(size_t count); + + bool HasMore() const; + + private: + struct TState { + ui64 Workspace = 0; + int WorkspaceSize = 0; + ui64 Position = 0; + TStringBuf Data; + + ui64 NextBitsUnmasked(int count); // The upper 64 - count bits may be arbitrary + ui64 PeekBits(int count); + void SkipBits(int count); + }; + + void FillDecodeBuffer(); + + TState State; + std::array<float, 128> DecodeBuffer; + // The range of already decompressed numbers inside the DecodeBuffer. + // Always kept non-empty until the EOS is encountered. + float* Begin; + float* End; + bool HitEos = false; + }; + + TVector<float> Decode(TStringBuf data, size_t sizeHint = 0); } diff --git a/library/cpp/codecs/float_huffman_bench/main.cpp b/library/cpp/codecs/float_huffman_bench/main.cpp index c5dd456bbe..1018c17834 100644 --- a/library/cpp/codecs/float_huffman_bench/main.cpp +++ b/library/cpp/codecs/float_huffman_bench/main.cpp @@ -1,145 +1,145 @@ -#include <library/cpp/codecs/float_huffman.h> - -#include <benchmark/benchmark.h> - -#include <util/generic/vector.h> - -const float Factors[] = { - 0.340582, 0.000974026, 0.487168, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0.411765, 0.921569, - 0.00390625, 0.109371, 0, 1, 0, 0, 0, 0, 0.523322, 0, 1, 0, 0, 0, 0, 0.285714, 1, - 0.008253, 1, 0, 0, 0.00993935, 0.450213, 0.000974026, 1, 1, 1, 1, 0, 0, 0.20564, - 0.97561, 0.913896, 1, 1, 0, 1, 0, 0, 0.5, 0, 0, 0, 0.1, 1, 0, 0, 0, 0, 0, 0.450923, - 0, 0.5, 0, 0, 0.20564, 0, 0.5, 0, 0, 0.20564, 0, 0, 0.0313726, 0, 1, 1, 1, 0.363636, - 0.5, 0.686073, 0.45121, 0.00574382, 0.366166, 0.413295, 1, 1, 1, 0, 0, 0, 0, 0.160784, - 0, 0.937255, 0.537255, 0.133333, 0, 0, 0, 0, 0.00392157, 0, 0.333333, 0.027451, 0.0156863, - 1, 0.105882, 1, 0.00220908, 0.000112501, 0.0111262, 0.102384, 0.00140808, 0.123581, - 0.29308, 6.57282e-06, 0.00489498, 2.10209e-05, 0.00140559, 5.907e-06, 0, 0.559322, - 0.559322, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0.794765, 0, - 0.352648, 0.225904, 1, 0.047619, 0.0107276, 0.399461, 0.0304838, 0.292932, 0.00969929, - 0, 0, 0.886904, 0.714693, 0, 0.00223213, 0.000544069, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0.00507403, 0, 0, 0, 0, 0, 0.875, 0, 0, 1, 1, 1, 0, 0.20564, 0, 0.00176048, 0, - 0.000440121, 0, 0, 0, 0.000974026, 0.487168, 0, 0, 0.533333, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 1, 0, 0, 1, 0, 0, 0.723187, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 1, 0, 0.206882, 0.00483367, 0.792983, 0.00126106, 1, 0.0313726, 0.470588, - 0.254902, 0.188235, 0.188235, 0.388235, 0.164706, 0, 0.870588, 0.843137, 0.635294, - 0.384314, 0.384314, 0.643137, 0, 0, 0, 0, 0, 0, 0, 0, 0.541176, 0, 0.541176, 0, 0, - 0.0532634, 1, 0, 0, 0, 0.015044, 1, 0, 1, 1, 1, 0.47451, 0.329412, 0.964706, 0, 0, - 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0.0941176, 0.970588, 0.970588, 0, 0.970588, 0.97561, - 0, 0.0431373, 0.47451, 0.329412, 0.964706, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0.231373, 0.00392157, 0, 0, 0, 0.054902, 0, 0, - 1, 0, 0, 0.0235294, 0, 1, 0, 0, 0, 0, 0.34902, 0.0352941, 0.925379, 0.623681, 0, - 0.954543, 0, 0, 0.00102756, 0.709804, 0.498039, 0.0901961, 0.631373, 0.847059, 0.270588, - 0.0156863, 0.133333, 0.980392, 1e-12, 1e-12, 1e-12, 1e-12, 0.497159, 0, 0.407487, - 0, 0, 0, 0.00392157, 0.00202156, 0.046875, 0.187159, 0.046875, 0.15625, 0.434232, - 0.15625, 0, 2.95083e-07, 0.20564, 0.20564, 0.97561, 0.913896, 0, 0, 0, 0, 0, 0, 0.00784314, - 0, 0.695525, 1, 0.07205, 0, 0, 0.176471, 0, 0, 0, 1, 1, 0.98, 0.01, 0.01, 0, 0.00690702, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.29078, 0.29078, 1, 0, 0, 0, 0, 0.192157, 0.188235, - 0.0941176, 0, 0.0313726, 0, 0.141176, 0.207843, 0.0901961, 0.00784314, 0.0784314, - 0, 0, 0, 0, 0, 0.203922, 0.0196078, 0.34902, 0.0235294, 0.0980392, 0.164706, 0.133333, - 0.368627, 0, 0.0941176, 0, 1, 0.313726, 0, 0, 0.433582, 0.384508, 0.0532186, 0.0833333, - 0.01609, 0, 1, 0, 0, 0, 0.0666667, 0, 0, 0, 0, 1, 0, 0.564706, 0.501961, 0, 0, 0, - 0, 0, 0.0516447, 0.000173065, 0, 0, 0, 0, 0, 0, 0, 0.996309, 0, 0, 0.00392157, 1, - 0, 0.01, 0, 0, 0, 0, 0, 0.439505, 0.206882, 0.206882, 0.260891, 0, 0.875, 0, 0, 0, - 0, 0, 0.185657, 1, 1, 0, 0, 0, 0.0332647, 0.206106, 0.0688878, 0.239216, 0, 0, 0, - 0, 0.054902, 0, 0.101961, 0.160784, 0.180392, 0, 0.737828, 0, 0, 0.875, 0.0142566, - 0, 0.662745, 1, 0, 0, 0, 0.225806, 0.99992, 0.631373, 0.00392157, 1, 0, 0.143647, - 0.00270085, 1, 0.231482, 0.246735, 0.0428062, 0, 0, 1, 0, 0.186441, 0.0115358, 0, - 0.221762, 0, 0.2, 0, 0.0156863, 0, 0, 0, 0.976471, 0, 0.231373, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0.00392157, 0.00392157, 0.0666667, 0, 0, 0, 0, 0.0117647, 0.580392, 0.98737, - 1, 1, 1, 0, 0, 0, 0.153, 0.847, 0.931373, 0.94697, 0.94697, 0, 0.946294, 0.408118, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0.99992, 0.97561, 0, 0, 0, 0, 0, 0, - 0.274677, 0.153017, 0, 0.642356, 0, 0, 0.1, 0, 0, 0, 0, 0.327944, 0.327944, 0, 0, - 0.815686, 0, 0, 0, 0, 0.206106, 0.439126, 0, 0, 0, 0, 0, 1, 1, 1, 0.00392157, 0.232788, - 0.232465, 0.999899, 0.00309296, 0.0636097, 0.445954, 0.156863, 0, 0, 0, 0, 0, 0, - 0.3796, 0.0784, 0.0651664, 0, 0, 0.254902, 0.266667, 1, 0, 0, 0, 0, 0, 0.596073, - 0.517876, 0.145833, 0.372549, 0, 0.991667, 0.602125, 0.161979, 0, 0, 0, 0, 0.0255146, - 0.947855, 0, 0, 0, 0, 0, 0, 0, 0, 0.847059, 0.679841, 0, 0.156863, 0, 0, 1, 0, 0, - 0, 0, 0.969697, 0, 0, 0.564706, 0, 0, 0, 0, 0, 1, 0.0367282, 0.0395228, 0, 0, 0, - 0, 0, 0.0470588, 0.141176, 0.054902, 0, 0, 0, 0}; - -const ui8 CodedFactors[] = { - 0x24, 0x06, 0x73, 0xB5, 0xC7, 0x55, 0x7F, 0x3A, 0xB4, 0x70, 0xCB, 0xEF, 0xEE, 0xFE, 0xB3, 0x5B, - 0x5A, 0x1A, 0x93, 0x5F, 0x5F, 0x13, 0x00, 0x00, 0x10, 0x00, 0x3D, 0xEF, 0xFF, 0xEE, 0x0F, 0xDC, - 0xF0, 0xAB, 0x3F, 0x37, 0x92, 0x24, 0x5D, 0x5E, 0xDE, 0x1C, 0xF8, 0x12, 0x15, 0x5B, 0x84, 0x51, - 0x82, 0xE6, 0xF6, 0xB8, 0xEA, 0x4F, 0xC7, 0xDD, 0x7D, 0x2E, 0x4D, 0x4A, 0x21, 0xCA, 0xE0, 0xC4, - 0x2E, 0xEA, 0xD3, 0xBD, 0x0F, 0x00, 0x00, 0xE0, 0xDA, 0xCC, 0xCC, 0xEC, 0x9F, 0x61, 0xDF, 0xE6, - 0x01, 0x00, 0x00, 0xCC, 0xA5, 0x49, 0xA9, 0x00, 0x00, 0x00, 0xE6, 0xD2, 0xA4, 0xD4, 0xEA, 0x08, - 0x08, 0xD0, 0xDD, 0xF9, 0xE7, 0xA2, 0x0B, 0x00, 0x00, 0x40, 0xD8, 0x13, 0x7D, 0xFE, 0x13, 0x9C, - 0x9B, 0xA8, 0x36, 0xBC, 0x00, 0x90, 0x43, 0x6F, 0x97, 0x67, 0x9B, 0xD3, 0xEE, 0xFE, 0x84, 0x24, - 0x25, 0x89, 0xC9, 0xBF, 0x3F, 0x58, 0x4C, 0x4C, 0xCA, 0x21, 0x22, 0xBC, 0x39, 0x08, 0x08, 0x08, - 0x40, 0x7E, 0xAA, 0xAA, 0xCA, 0x75, 0x70, 0x70, 0xE9, 0x08, 0x08, 0xE8, 0x9A, 0x8A, 0x8D, 0xED, - 0xA6, 0x8D, 0x31, 0x04, 0x00, 0x96, 0xD0, 0x7D, 0x1D, 0x47, 0xAA, 0x2A, 0xD9, 0x28, 0xAD, 0x6B, - 0xB4, 0x9D, 0x7A, 0xC4, 0xD5, 0xD1, 0x04, 0x8C, 0x7E, 0x56, 0x3A, 0x58, 0x5A, 0x0C, 0x46, 0x6E, - 0x1B, 0x53, 0xC2, 0x0C, 0x14, 0x00, 0xAB, 0x60, 0x05, 0x7B, 0x63, 0x8D, 0x77, 0x70, 0x75, 0xAC, - 0x2F, 0x8D, 0xB1, 0x4D, 0xA0, 0xFB, 0xF2, 0x40, 0xF7, 0xE5, 0x7F, 0xDF, 0xDD, 0xFD, 0xBB, 0x1B, - 0xB8, 0x75, 0x9B, 0x47, 0x8E, 0xB4, 0x0C, 0x9B, 0x3A, 0x73, 0x25, 0x61, 0x18, 0x92, 0xD1, 0xC2, - 0x2F, 0x3C, 0x31, 0x64, 0x96, 0x2A, 0xB9, 0xF9, 0x7C, 0xD9, 0xAF, 0x94, 0xC5, 0xE9, 0x1E, 0x63, - 0x24, 0x0C, 0x03, 0x7F, 0xD8, 0x5B, 0xB3, 0x1D, 0x49, 0x02, 0x00, 0xAB, 0xFD, 0xE9, 0xA0, 0xF3, - 0xBF, 0xC9, 0x40, 0x64, 0x0A, 0xC0, 0xC7, 0x00, 0x00, 0x60, 0x77, 0xCF, 0xA5, 0x49, 0xA9, 0x16, - 0xFD, 0xD7, 0x5C, 0xA7, 0x55, 0x00, 0x36, 0xCF, 0xB9, 0x3D, 0xAE, 0xFA, 0xD3, 0xA1, 0x85, 0x5B, - 0xFE, 0x60, 0x10, 0x11, 0xFF, 0xF7, 0x7D, 0x38, 0x59, 0x24, 0xFF, 0xFF, 0xDF, 0x13, 0x1C, 0x7B, - 0xCA, 0x1C, 0x1E, 0xF3, 0x04, 0xC0, 0x78, 0x07, 0x58, 0x7B, 0xA2, 0x54, 0xAA, 0xE3, 0xEA, 0x08, - 0x08, 0xC0, 0x74, 0x78, 0x78, 0x88, 0x50, 0x50, 0xD8, 0x0A, 0x0C, 0xC4, 0x56, 0x60, 0x20, 0xF6, - 0x1A, 0x1B, 0x33, 0x16, 0x15, 0xA5, 0xB8, 0xED, 0xED, 0x22, 0xF5, 0xF5, 0x09, 0xA1, 0xA2, 0x42, - 0x67, 0x62, 0x62, 0x3A, 0x13, 0x13, 0x0B, 0xA0, 0xA4, 0xF4, 0x0F, 0x06, 0x15, 0x35, 0x18, 0x54, - 0xD4, 0x35, 0x57, 0x45, 0xCB, 0x2F, 0x39, 0xF6, 0xEC, 0xBC, 0xBB, 0x53, 0x5F, 0x5E, 0x9E, 0xB1, - 0xA8, 0xA8, 0x28, 0xDF, 0xDE, 0x3E, 0x00, 0x00, 0x80, 0x5F, 0x75, 0x81, 0x81, 0x51, 0x1D, 0x1E, - 0xA2, 0x3A, 0x3C, 0x8C, 0xEA, 0xF0, 0x10, 0x51, 0x06, 0x67, 0xED, 0x85, 0x85, 0xA1, 0xBE, 0xBC, - 0x3C, 0x63, 0x51, 0x51, 0x51, 0xBE, 0xBD, 0xFD, 0xFF, 0xFD, 0xFE, 0xCE, 0x85, 0x76, 0x36, 0x73, - 0x10, 0x10, 0x10, 0x80, 0xEB, 0x3A, 0x38, 0xD8, 0xBE, 0xD4, 0x05, 0x06, 0xEE, 0x4F, 0x60, 0x59, - 0x59, 0x65, 0x84, 0x84, 0xC0, 0x46, 0xCB, 0x19, 0x7F, 0x4C, 0xFD, 0xC8, 0x9D, 0x8B, 0xB6, 0x31, - 0xAF, 0x86, 0x3A, 0xF0, 0x6D, 0x6D, 0x11, 0xDF, 0xDF, 0x5F, 0x79, 0x71, 0x71, 0x85, 0xD4, 0xD0, - 0x10, 0xB9, 0xB1, 0x11, 0x1A, 0x54, 0x54, 0xE9, 0x08, 0x08, 0x48, 0x39, 0x44, 0x04, 0x84, 0xAF, - 0xAF, 0x96, 0x99, 0x97, 0x71, 0xC5, 0x32, 0xF3, 0x32, 0xAE, 0x58, 0x66, 0x5E, 0xC6, 0x15, 0xCB, - 0xCC, 0xCB, 0xB8, 0x42, 0xD0, 0x45, 0xFF, 0x1C, 0x11, 0x85, 0xBE, 0x39, 0x08, 0x08, 0x08, 0x80, - 0x69, 0xC2, 0x47, 0x00, 0x80, 0x02, 0x00, 0x00, 0x91, 0xD3, 0xF4, 0x47, 0x01, 0x00, 0x80, 0x08, - 0x00, 0x00, 0x42, 0xD4, 0x29, 0x6F, 0x02, 0x00, 0x80, 0xB4, 0xE6, 0x6B, 0x9E, 0x34, 0x5C, 0x9A, - 0x94, 0xE2, 0xD2, 0xA4, 0x14, 0xA2, 0x0C, 0x4E, 0xEC, 0xA2, 0x3E, 0x7F, 0x39, 0x08, 0x08, 0x10, - 0x6E, 0x6F, 0x10, 0xD7, 0x79, 0xC7, 0xC9, 0x09, 0x4D, 0x4B, 0x73, 0x77, 0x84, 0x14, 0xAE, 0x52, - 0xE1, 0x7A, 0x44, 0x2A, 0x5C, 0x8F, 0x34, 0x93, 0xA8, 0xC4, 0x01, 0xF8, 0x3F, 0x3D, 0xC2, 0x29, - 0xE9, 0x11, 0x4E, 0xE9, 0x4F, 0x67, 0x62, 0x22, 0xB6, 0x02, 0x03, 0xA9, 0x2E, 0x30, 0x70, 0x75, - 0x04, 0x04, 0xC8, 0x38, 0x48, 0x08, 0x32, 0x53, 0x53, 0x29, 0x2F, 0x2E, 0xAE, 0x1C, 0x04, 0x04, - 0x50, 0x52, 0x50, 0xD0, 0x4F, 0x77, 0x68, 0x28, 0x99, 0x08, 0x0A, 0x4A, 0x60, 0x59, 0x59, 0xA9, - 0x0B, 0x0C, 0xAC, 0xC7, 0xC8, 0xC8, 0x8C, 0x45, 0x45, 0xA1, 0x1C, 0x22, 0x02, 0x5D, 0x79, 0x79, - 0xAB, 0x2E, 0x30, 0x70, 0xA7, 0x2C, 0x28, 0xE8, 0xB4, 0xF3, 0xEF, 0x26, 0x8F, 0x37, 0xB1, 0xFE, - 0xEE, 0x67, 0xA9, 0xA9, 0xAA, 0xAA, 0x6C, 0x79, 0x1E, 0xEC, 0xD7, 0x46, 0x44, 0xC4, 0xF7, 0xF8, - 0x24, 0x24, 0x00, 0x42, 0x40, 0xF8, 0x5A, 0x96, 0x38, 0x65, 0x91, 0xF1, 0x6A, 0x72, 0xFE, 0x68, - 0xC3, 0xE1, 0x37, 0x07, 0x01, 0x01, 0x01, 0xF0, 0x52, 0xE1, 0x7A, 0xE4, 0xB3, 0xD9, 0x20, 0x9C, - 0xE0, 0xD8, 0x53, 0x04, 0xC7, 0x9E, 0x82, 0x02, 0x27, 0x2B, 0x06, 0x00, 0x00, 0x9F, 0xDE, 0x1C, - 0x3E, 0xEE, 0xD7, 0x48, 0x20, 0x04, 0xD2, 0x35, 0x4C, 0x29, 0x43, 0x45, 0x23, 0x15, 0xEA, 0xE9, - 0x5E, 0xD7, 0xC1, 0xC1, 0xAA, 0x3B, 0x34, 0x34, 0x21, 0x49, 0x49, 0xE8, 0x8A, 0x8B, 0x13, 0x66, - 0x12, 0xE7, 0x31, 0x00, 0x00, 0x90, 0x84, 0x94, 0x69, 0x05, 0xD4, 0xD4, 0xF4, 0x13, 0x36, 0xE7, - 0x0C, 0x09, 0xEB, 0xBF, 0x90, 0x1A, 0x1A, 0xE6, 0x20, 0x20, 0x20, 0x00, 0x9E, 0x33, 0x18, 0x13, - 0xA6, 0x2F, 0x40, 0x0C, 0x00, 0x4E, 0xCF, 0x84, 0x36, 0x6A, 0xA0, 0xF2, 0xA9, 0x63, 0xD5, 0xCB, - 0x9E, 0x64, 0xEA, 0x3E, 0xF2, 0x14, 0xA0, 0x27, 0x29, 0x2B, 0xC6, 0xB2, 0x99, 0x99, 0xA9, 0x74, - 0x04, 0x04, 0x3C, 0x0A, 0xD0, 0xCF, 0x5C, 0x68, 0x67, 0xFB, 0xDF, 0x1C, 0x04, 0x04, 0x04, 0xC0, - 0x1C, 0x04, 0x04, 0x04, 0x40, 0x1B, 0x11, 0x11, 0x5F, 0xEA, 0x02, 0x03, 0xE1, 0x92, 0x94, 0x84, - 0x90, 0x88, 0xD9, 0xDD, 0x4F, 0x04, 0x56, 0x0E, 0xD1, 0x9F, 0x1A, 0x31, 0x3B, 0x37, 0x47, 0xA0, - 0x6C, 0x82, 0x40, 0xD9, 0x24, 0x9A, 0x02, 0x12, 0x62, 0xD3, 0x43, 0xFF, 0xBF, 0x8F, 0x84, 0xF5, - 0x1F, 0x51, 0x06, 0xE7, 0x0F, 0xDD, 0x89, 0x32, 0xFB, 0x60, 0x39, 0x0A, 0x71, 0x71, 0xB4, 0x36, - 0x33, 0x33, 0x3F, 0x8F, 0xD0, 0x4F, 0x79, 0x84, 0x7E, 0xBA, 0xC8, 0x0C, 0x0D, 0x4F, 0xBA, 0x86, - 0x29, 0x82, 0x54, 0x83, 0x7F, 0x77, 0x37, 0x07, 0x01, 0x01, 0x01, 0xA0, 0xFE, 0x97, 0x1B, 0x9D, - 0x16, 0xDC, 0x90, 0x58, 0xFE, 0x9B, 0x42, 0xB3, 0x4A, 0x00, 0x68, 0x73, 0x91, 0x20, 0x2B, 0xA8, - 0xC8, 0x29, 0x0B, 0x0A, 0xF2, 0xD3, 0x5D, 0x4B, 0x58, 0x5D, 0x20, 0x41, 0xD5, 0xBE, 0xAE, 0x70, - 0x88, 0x50, 0x50, 0x20, 0x4A, 0x44, 0xF4, 0x8F, 0xF7, 0x60, 0x22, 0x30, 0x9C, 0x24, 0xFE, 0x54, - 0x55, 0xD0, 0xD7, 0xD7, 0x37, 0x1A, 0xEF, 0x6E, 0xBC, 0x9B, 0x44, 0x39, 0xDD, 0x5D, 0xF2, 0xF2, - 0x7F, 0x20, 0x1A, 0x81, 0x9A, 0xCA, 0xBF, 0xC8, 0x8D, 0x8D, 0xC2, 0x83, 0x82, 0xA7, 0x2C, 0x28, - 0xC8, 0xFE, 0x08, 0xC2, 0x07, 0xC7, 0x27, 0x21, 0xE1, 0xBB, 0x3E, 0xC1, 0x59, 0x68, 0xAA, 0x78, - 0xC8, 0x57, 0x5D, 0x60, 0x20, 0xC6, 0x41, 0x42, 0xE8, 0x3A, 0x38, 0xD8, 0x9B, 0xFF, 0xFF, 0xFF, - 0xC4, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}; -static const TStringBuf CodedFactorsBuf(reinterpret_cast<const char*>(CodedFactors), Y_ARRAY_SIZE(CodedFactors)); - -void BM_Encode(benchmark::State& state) { - for (const auto _ : state) { - NCodecs::NFloatHuff::Encode(Factors); - } -} - -void BM_Decode(benchmark::State& state) { - for (const auto _ : state) { - NCodecs::NFloatHuff::Decode(CodedFactorsBuf, Y_ARRAY_SIZE(Factors)); - } -} - -BENCHMARK(BM_Encode); -BENCHMARK(BM_Decode); +#include <library/cpp/codecs/float_huffman.h> + +#include <benchmark/benchmark.h> + +#include <util/generic/vector.h> + +const float Factors[] = { + 0.340582, 0.000974026, 0.487168, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0.411765, 0.921569, + 0.00390625, 0.109371, 0, 1, 0, 0, 0, 0, 0.523322, 0, 1, 0, 0, 0, 0, 0.285714, 1, + 0.008253, 1, 0, 0, 0.00993935, 0.450213, 0.000974026, 1, 1, 1, 1, 0, 0, 0.20564, + 0.97561, 0.913896, 1, 1, 0, 1, 0, 0, 0.5, 0, 0, 0, 0.1, 1, 0, 0, 0, 0, 0, 0.450923, + 0, 0.5, 0, 0, 0.20564, 0, 0.5, 0, 0, 0.20564, 0, 0, 0.0313726, 0, 1, 1, 1, 0.363636, + 0.5, 0.686073, 0.45121, 0.00574382, 0.366166, 0.413295, 1, 1, 1, 0, 0, 0, 0, 0.160784, + 0, 0.937255, 0.537255, 0.133333, 0, 0, 0, 0, 0.00392157, 0, 0.333333, 0.027451, 0.0156863, + 1, 0.105882, 1, 0.00220908, 0.000112501, 0.0111262, 0.102384, 0.00140808, 0.123581, + 0.29308, 6.57282e-06, 0.00489498, 2.10209e-05, 0.00140559, 5.907e-06, 0, 0.559322, + 0.559322, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0.794765, 0, + 0.352648, 0.225904, 1, 0.047619, 0.0107276, 0.399461, 0.0304838, 0.292932, 0.00969929, + 0, 0, 0.886904, 0.714693, 0, 0.00223213, 0.000544069, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0.00507403, 0, 0, 0, 0, 0, 0.875, 0, 0, 1, 1, 1, 0, 0.20564, 0, 0.00176048, 0, + 0.000440121, 0, 0, 0, 0.000974026, 0.487168, 0, 0, 0.533333, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 1, 0, 0, 1, 0, 0, 0.723187, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 1, 0, 0.206882, 0.00483367, 0.792983, 0.00126106, 1, 0.0313726, 0.470588, + 0.254902, 0.188235, 0.188235, 0.388235, 0.164706, 0, 0.870588, 0.843137, 0.635294, + 0.384314, 0.384314, 0.643137, 0, 0, 0, 0, 0, 0, 0, 0, 0.541176, 0, 0.541176, 0, 0, + 0.0532634, 1, 0, 0, 0, 0.015044, 1, 0, 1, 1, 1, 0.47451, 0.329412, 0.964706, 0, 0, + 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0.0941176, 0.970588, 0.970588, 0, 0.970588, 0.97561, + 0, 0.0431373, 0.47451, 0.329412, 0.964706, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0.231373, 0.00392157, 0, 0, 0, 0.054902, 0, 0, + 1, 0, 0, 0.0235294, 0, 1, 0, 0, 0, 0, 0.34902, 0.0352941, 0.925379, 0.623681, 0, + 0.954543, 0, 0, 0.00102756, 0.709804, 0.498039, 0.0901961, 0.631373, 0.847059, 0.270588, + 0.0156863, 0.133333, 0.980392, 1e-12, 1e-12, 1e-12, 1e-12, 0.497159, 0, 0.407487, + 0, 0, 0, 0.00392157, 0.00202156, 0.046875, 0.187159, 0.046875, 0.15625, 0.434232, + 0.15625, 0, 2.95083e-07, 0.20564, 0.20564, 0.97561, 0.913896, 0, 0, 0, 0, 0, 0, 0.00784314, + 0, 0.695525, 1, 0.07205, 0, 0, 0.176471, 0, 0, 0, 1, 1, 0.98, 0.01, 0.01, 0, 0.00690702, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.29078, 0.29078, 1, 0, 0, 0, 0, 0.192157, 0.188235, + 0.0941176, 0, 0.0313726, 0, 0.141176, 0.207843, 0.0901961, 0.00784314, 0.0784314, + 0, 0, 0, 0, 0, 0.203922, 0.0196078, 0.34902, 0.0235294, 0.0980392, 0.164706, 0.133333, + 0.368627, 0, 0.0941176, 0, 1, 0.313726, 0, 0, 0.433582, 0.384508, 0.0532186, 0.0833333, + 0.01609, 0, 1, 0, 0, 0, 0.0666667, 0, 0, 0, 0, 1, 0, 0.564706, 0.501961, 0, 0, 0, + 0, 0, 0.0516447, 0.000173065, 0, 0, 0, 0, 0, 0, 0, 0.996309, 0, 0, 0.00392157, 1, + 0, 0.01, 0, 0, 0, 0, 0, 0.439505, 0.206882, 0.206882, 0.260891, 0, 0.875, 0, 0, 0, + 0, 0, 0.185657, 1, 1, 0, 0, 0, 0.0332647, 0.206106, 0.0688878, 0.239216, 0, 0, 0, + 0, 0.054902, 0, 0.101961, 0.160784, 0.180392, 0, 0.737828, 0, 0, 0.875, 0.0142566, + 0, 0.662745, 1, 0, 0, 0, 0.225806, 0.99992, 0.631373, 0.00392157, 1, 0, 0.143647, + 0.00270085, 1, 0.231482, 0.246735, 0.0428062, 0, 0, 1, 0, 0.186441, 0.0115358, 0, + 0.221762, 0, 0.2, 0, 0.0156863, 0, 0, 0, 0.976471, 0, 0.231373, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0.00392157, 0.00392157, 0.0666667, 0, 0, 0, 0, 0.0117647, 0.580392, 0.98737, + 1, 1, 1, 0, 0, 0, 0.153, 0.847, 0.931373, 0.94697, 0.94697, 0, 0.946294, 0.408118, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0.99992, 0.97561, 0, 0, 0, 0, 0, 0, + 0.274677, 0.153017, 0, 0.642356, 0, 0, 0.1, 0, 0, 0, 0, 0.327944, 0.327944, 0, 0, + 0.815686, 0, 0, 0, 0, 0.206106, 0.439126, 0, 0, 0, 0, 0, 1, 1, 1, 0.00392157, 0.232788, + 0.232465, 0.999899, 0.00309296, 0.0636097, 0.445954, 0.156863, 0, 0, 0, 0, 0, 0, + 0.3796, 0.0784, 0.0651664, 0, 0, 0.254902, 0.266667, 1, 0, 0, 0, 0, 0, 0.596073, + 0.517876, 0.145833, 0.372549, 0, 0.991667, 0.602125, 0.161979, 0, 0, 0, 0, 0.0255146, + 0.947855, 0, 0, 0, 0, 0, 0, 0, 0, 0.847059, 0.679841, 0, 0.156863, 0, 0, 1, 0, 0, + 0, 0, 0.969697, 0, 0, 0.564706, 0, 0, 0, 0, 0, 1, 0.0367282, 0.0395228, 0, 0, 0, + 0, 0, 0.0470588, 0.141176, 0.054902, 0, 0, 0, 0}; + +const ui8 CodedFactors[] = { + 0x24, 0x06, 0x73, 0xB5, 0xC7, 0x55, 0x7F, 0x3A, 0xB4, 0x70, 0xCB, 0xEF, 0xEE, 0xFE, 0xB3, 0x5B, + 0x5A, 0x1A, 0x93, 0x5F, 0x5F, 0x13, 0x00, 0x00, 0x10, 0x00, 0x3D, 0xEF, 0xFF, 0xEE, 0x0F, 0xDC, + 0xF0, 0xAB, 0x3F, 0x37, 0x92, 0x24, 0x5D, 0x5E, 0xDE, 0x1C, 0xF8, 0x12, 0x15, 0x5B, 0x84, 0x51, + 0x82, 0xE6, 0xF6, 0xB8, 0xEA, 0x4F, 0xC7, 0xDD, 0x7D, 0x2E, 0x4D, 0x4A, 0x21, 0xCA, 0xE0, 0xC4, + 0x2E, 0xEA, 0xD3, 0xBD, 0x0F, 0x00, 0x00, 0xE0, 0xDA, 0xCC, 0xCC, 0xEC, 0x9F, 0x61, 0xDF, 0xE6, + 0x01, 0x00, 0x00, 0xCC, 0xA5, 0x49, 0xA9, 0x00, 0x00, 0x00, 0xE6, 0xD2, 0xA4, 0xD4, 0xEA, 0x08, + 0x08, 0xD0, 0xDD, 0xF9, 0xE7, 0xA2, 0x0B, 0x00, 0x00, 0x40, 0xD8, 0x13, 0x7D, 0xFE, 0x13, 0x9C, + 0x9B, 0xA8, 0x36, 0xBC, 0x00, 0x90, 0x43, 0x6F, 0x97, 0x67, 0x9B, 0xD3, 0xEE, 0xFE, 0x84, 0x24, + 0x25, 0x89, 0xC9, 0xBF, 0x3F, 0x58, 0x4C, 0x4C, 0xCA, 0x21, 0x22, 0xBC, 0x39, 0x08, 0x08, 0x08, + 0x40, 0x7E, 0xAA, 0xAA, 0xCA, 0x75, 0x70, 0x70, 0xE9, 0x08, 0x08, 0xE8, 0x9A, 0x8A, 0x8D, 0xED, + 0xA6, 0x8D, 0x31, 0x04, 0x00, 0x96, 0xD0, 0x7D, 0x1D, 0x47, 0xAA, 0x2A, 0xD9, 0x28, 0xAD, 0x6B, + 0xB4, 0x9D, 0x7A, 0xC4, 0xD5, 0xD1, 0x04, 0x8C, 0x7E, 0x56, 0x3A, 0x58, 0x5A, 0x0C, 0x46, 0x6E, + 0x1B, 0x53, 0xC2, 0x0C, 0x14, 0x00, 0xAB, 0x60, 0x05, 0x7B, 0x63, 0x8D, 0x77, 0x70, 0x75, 0xAC, + 0x2F, 0x8D, 0xB1, 0x4D, 0xA0, 0xFB, 0xF2, 0x40, 0xF7, 0xE5, 0x7F, 0xDF, 0xDD, 0xFD, 0xBB, 0x1B, + 0xB8, 0x75, 0x9B, 0x47, 0x8E, 0xB4, 0x0C, 0x9B, 0x3A, 0x73, 0x25, 0x61, 0x18, 0x92, 0xD1, 0xC2, + 0x2F, 0x3C, 0x31, 0x64, 0x96, 0x2A, 0xB9, 0xF9, 0x7C, 0xD9, 0xAF, 0x94, 0xC5, 0xE9, 0x1E, 0x63, + 0x24, 0x0C, 0x03, 0x7F, 0xD8, 0x5B, 0xB3, 0x1D, 0x49, 0x02, 0x00, 0xAB, 0xFD, 0xE9, 0xA0, 0xF3, + 0xBF, 0xC9, 0x40, 0x64, 0x0A, 0xC0, 0xC7, 0x00, 0x00, 0x60, 0x77, 0xCF, 0xA5, 0x49, 0xA9, 0x16, + 0xFD, 0xD7, 0x5C, 0xA7, 0x55, 0x00, 0x36, 0xCF, 0xB9, 0x3D, 0xAE, 0xFA, 0xD3, 0xA1, 0x85, 0x5B, + 0xFE, 0x60, 0x10, 0x11, 0xFF, 0xF7, 0x7D, 0x38, 0x59, 0x24, 0xFF, 0xFF, 0xDF, 0x13, 0x1C, 0x7B, + 0xCA, 0x1C, 0x1E, 0xF3, 0x04, 0xC0, 0x78, 0x07, 0x58, 0x7B, 0xA2, 0x54, 0xAA, 0xE3, 0xEA, 0x08, + 0x08, 0xC0, 0x74, 0x78, 0x78, 0x88, 0x50, 0x50, 0xD8, 0x0A, 0x0C, 0xC4, 0x56, 0x60, 0x20, 0xF6, + 0x1A, 0x1B, 0x33, 0x16, 0x15, 0xA5, 0xB8, 0xED, 0xED, 0x22, 0xF5, 0xF5, 0x09, 0xA1, 0xA2, 0x42, + 0x67, 0x62, 0x62, 0x3A, 0x13, 0x13, 0x0B, 0xA0, 0xA4, 0xF4, 0x0F, 0x06, 0x15, 0x35, 0x18, 0x54, + 0xD4, 0x35, 0x57, 0x45, 0xCB, 0x2F, 0x39, 0xF6, 0xEC, 0xBC, 0xBB, 0x53, 0x5F, 0x5E, 0x9E, 0xB1, + 0xA8, 0xA8, 0x28, 0xDF, 0xDE, 0x3E, 0x00, 0x00, 0x80, 0x5F, 0x75, 0x81, 0x81, 0x51, 0x1D, 0x1E, + 0xA2, 0x3A, 0x3C, 0x8C, 0xEA, 0xF0, 0x10, 0x51, 0x06, 0x67, 0xED, 0x85, 0x85, 0xA1, 0xBE, 0xBC, + 0x3C, 0x63, 0x51, 0x51, 0x51, 0xBE, 0xBD, 0xFD, 0xFF, 0xFD, 0xFE, 0xCE, 0x85, 0x76, 0x36, 0x73, + 0x10, 0x10, 0x10, 0x80, 0xEB, 0x3A, 0x38, 0xD8, 0xBE, 0xD4, 0x05, 0x06, 0xEE, 0x4F, 0x60, 0x59, + 0x59, 0x65, 0x84, 0x84, 0xC0, 0x46, 0xCB, 0x19, 0x7F, 0x4C, 0xFD, 0xC8, 0x9D, 0x8B, 0xB6, 0x31, + 0xAF, 0x86, 0x3A, 0xF0, 0x6D, 0x6D, 0x11, 0xDF, 0xDF, 0x5F, 0x79, 0x71, 0x71, 0x85, 0xD4, 0xD0, + 0x10, 0xB9, 0xB1, 0x11, 0x1A, 0x54, 0x54, 0xE9, 0x08, 0x08, 0x48, 0x39, 0x44, 0x04, 0x84, 0xAF, + 0xAF, 0x96, 0x99, 0x97, 0x71, 0xC5, 0x32, 0xF3, 0x32, 0xAE, 0x58, 0x66, 0x5E, 0xC6, 0x15, 0xCB, + 0xCC, 0xCB, 0xB8, 0x42, 0xD0, 0x45, 0xFF, 0x1C, 0x11, 0x85, 0xBE, 0x39, 0x08, 0x08, 0x08, 0x80, + 0x69, 0xC2, 0x47, 0x00, 0x80, 0x02, 0x00, 0x00, 0x91, 0xD3, 0xF4, 0x47, 0x01, 0x00, 0x80, 0x08, + 0x00, 0x00, 0x42, 0xD4, 0x29, 0x6F, 0x02, 0x00, 0x80, 0xB4, 0xE6, 0x6B, 0x9E, 0x34, 0x5C, 0x9A, + 0x94, 0xE2, 0xD2, 0xA4, 0x14, 0xA2, 0x0C, 0x4E, 0xEC, 0xA2, 0x3E, 0x7F, 0x39, 0x08, 0x08, 0x10, + 0x6E, 0x6F, 0x10, 0xD7, 0x79, 0xC7, 0xC9, 0x09, 0x4D, 0x4B, 0x73, 0x77, 0x84, 0x14, 0xAE, 0x52, + 0xE1, 0x7A, 0x44, 0x2A, 0x5C, 0x8F, 0x34, 0x93, 0xA8, 0xC4, 0x01, 0xF8, 0x3F, 0x3D, 0xC2, 0x29, + 0xE9, 0x11, 0x4E, 0xE9, 0x4F, 0x67, 0x62, 0x22, 0xB6, 0x02, 0x03, 0xA9, 0x2E, 0x30, 0x70, 0x75, + 0x04, 0x04, 0xC8, 0x38, 0x48, 0x08, 0x32, 0x53, 0x53, 0x29, 0x2F, 0x2E, 0xAE, 0x1C, 0x04, 0x04, + 0x50, 0x52, 0x50, 0xD0, 0x4F, 0x77, 0x68, 0x28, 0x99, 0x08, 0x0A, 0x4A, 0x60, 0x59, 0x59, 0xA9, + 0x0B, 0x0C, 0xAC, 0xC7, 0xC8, 0xC8, 0x8C, 0x45, 0x45, 0xA1, 0x1C, 0x22, 0x02, 0x5D, 0x79, 0x79, + 0xAB, 0x2E, 0x30, 0x70, 0xA7, 0x2C, 0x28, 0xE8, 0xB4, 0xF3, 0xEF, 0x26, 0x8F, 0x37, 0xB1, 0xFE, + 0xEE, 0x67, 0xA9, 0xA9, 0xAA, 0xAA, 0x6C, 0x79, 0x1E, 0xEC, 0xD7, 0x46, 0x44, 0xC4, 0xF7, 0xF8, + 0x24, 0x24, 0x00, 0x42, 0x40, 0xF8, 0x5A, 0x96, 0x38, 0x65, 0x91, 0xF1, 0x6A, 0x72, 0xFE, 0x68, + 0xC3, 0xE1, 0x37, 0x07, 0x01, 0x01, 0x01, 0xF0, 0x52, 0xE1, 0x7A, 0xE4, 0xB3, 0xD9, 0x20, 0x9C, + 0xE0, 0xD8, 0x53, 0x04, 0xC7, 0x9E, 0x82, 0x02, 0x27, 0x2B, 0x06, 0x00, 0x00, 0x9F, 0xDE, 0x1C, + 0x3E, 0xEE, 0xD7, 0x48, 0x20, 0x04, 0xD2, 0x35, 0x4C, 0x29, 0x43, 0x45, 0x23, 0x15, 0xEA, 0xE9, + 0x5E, 0xD7, 0xC1, 0xC1, 0xAA, 0x3B, 0x34, 0x34, 0x21, 0x49, 0x49, 0xE8, 0x8A, 0x8B, 0x13, 0x66, + 0x12, 0xE7, 0x31, 0x00, 0x00, 0x90, 0x84, 0x94, 0x69, 0x05, 0xD4, 0xD4, 0xF4, 0x13, 0x36, 0xE7, + 0x0C, 0x09, 0xEB, 0xBF, 0x90, 0x1A, 0x1A, 0xE6, 0x20, 0x20, 0x20, 0x00, 0x9E, 0x33, 0x18, 0x13, + 0xA6, 0x2F, 0x40, 0x0C, 0x00, 0x4E, 0xCF, 0x84, 0x36, 0x6A, 0xA0, 0xF2, 0xA9, 0x63, 0xD5, 0xCB, + 0x9E, 0x64, 0xEA, 0x3E, 0xF2, 0x14, 0xA0, 0x27, 0x29, 0x2B, 0xC6, 0xB2, 0x99, 0x99, 0xA9, 0x74, + 0x04, 0x04, 0x3C, 0x0A, 0xD0, 0xCF, 0x5C, 0x68, 0x67, 0xFB, 0xDF, 0x1C, 0x04, 0x04, 0x04, 0xC0, + 0x1C, 0x04, 0x04, 0x04, 0x40, 0x1B, 0x11, 0x11, 0x5F, 0xEA, 0x02, 0x03, 0xE1, 0x92, 0x94, 0x84, + 0x90, 0x88, 0xD9, 0xDD, 0x4F, 0x04, 0x56, 0x0E, 0xD1, 0x9F, 0x1A, 0x31, 0x3B, 0x37, 0x47, 0xA0, + 0x6C, 0x82, 0x40, 0xD9, 0x24, 0x9A, 0x02, 0x12, 0x62, 0xD3, 0x43, 0xFF, 0xBF, 0x8F, 0x84, 0xF5, + 0x1F, 0x51, 0x06, 0xE7, 0x0F, 0xDD, 0x89, 0x32, 0xFB, 0x60, 0x39, 0x0A, 0x71, 0x71, 0xB4, 0x36, + 0x33, 0x33, 0x3F, 0x8F, 0xD0, 0x4F, 0x79, 0x84, 0x7E, 0xBA, 0xC8, 0x0C, 0x0D, 0x4F, 0xBA, 0x86, + 0x29, 0x82, 0x54, 0x83, 0x7F, 0x77, 0x37, 0x07, 0x01, 0x01, 0x01, 0xA0, 0xFE, 0x97, 0x1B, 0x9D, + 0x16, 0xDC, 0x90, 0x58, 0xFE, 0x9B, 0x42, 0xB3, 0x4A, 0x00, 0x68, 0x73, 0x91, 0x20, 0x2B, 0xA8, + 0xC8, 0x29, 0x0B, 0x0A, 0xF2, 0xD3, 0x5D, 0x4B, 0x58, 0x5D, 0x20, 0x41, 0xD5, 0xBE, 0xAE, 0x70, + 0x88, 0x50, 0x50, 0x20, 0x4A, 0x44, 0xF4, 0x8F, 0xF7, 0x60, 0x22, 0x30, 0x9C, 0x24, 0xFE, 0x54, + 0x55, 0xD0, 0xD7, 0xD7, 0x37, 0x1A, 0xEF, 0x6E, 0xBC, 0x9B, 0x44, 0x39, 0xDD, 0x5D, 0xF2, 0xF2, + 0x7F, 0x20, 0x1A, 0x81, 0x9A, 0xCA, 0xBF, 0xC8, 0x8D, 0x8D, 0xC2, 0x83, 0x82, 0xA7, 0x2C, 0x28, + 0xC8, 0xFE, 0x08, 0xC2, 0x07, 0xC7, 0x27, 0x21, 0xE1, 0xBB, 0x3E, 0xC1, 0x59, 0x68, 0xAA, 0x78, + 0xC8, 0x57, 0x5D, 0x60, 0x20, 0xC6, 0x41, 0x42, 0xE8, 0x3A, 0x38, 0xD8, 0x9B, 0xFF, 0xFF, 0xFF, + 0xC4, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}; +static const TStringBuf CodedFactorsBuf(reinterpret_cast<const char*>(CodedFactors), Y_ARRAY_SIZE(CodedFactors)); + +void BM_Encode(benchmark::State& state) { + for (const auto _ : state) { + NCodecs::NFloatHuff::Encode(Factors); + } +} + +void BM_Decode(benchmark::State& state) { + for (const auto _ : state) { + NCodecs::NFloatHuff::Decode(CodedFactorsBuf, Y_ARRAY_SIZE(Factors)); + } +} + +BENCHMARK(BM_Encode); +BENCHMARK(BM_Decode); diff --git a/library/cpp/codecs/float_huffman_bench/ya.make b/library/cpp/codecs/float_huffman_bench/ya.make index 8892fff60e..c8fae6873a 100644 --- a/library/cpp/codecs/float_huffman_bench/ya.make +++ b/library/cpp/codecs/float_huffman_bench/ya.make @@ -1,13 +1,13 @@ -OWNER(eeight) - -G_BENCHMARK() - -SRCS( - main.cpp -) - -PEERDIR( - library/cpp/codecs -) - -END() +OWNER(eeight) + +G_BENCHMARK() + +SRCS( + main.cpp +) + +PEERDIR( + library/cpp/codecs +) + +END() diff --git a/library/cpp/codecs/huffman_codec.h b/library/cpp/codecs/huffman_codec.h index 8b81e665e1..559545b90d 100644 --- a/library/cpp/codecs/huffman_codec.h +++ b/library/cpp/codecs/huffman_codec.h @@ -3,7 +3,7 @@ #include "codecs.h" #include <util/generic/ptr.h> -#include <util/string/cast.h> +#include <util/string/cast.h> namespace NCodecs { // for types greater than char, pipeline with TFreqCodec. diff --git a/library/cpp/codecs/pfor_codec.h b/library/cpp/codecs/pfor_codec.h index 26b8fa0c33..d7d4bb8bf4 100644 --- a/library/cpp/codecs/pfor_codec.h +++ b/library/cpp/codecs/pfor_codec.h @@ -7,7 +7,7 @@ #include <library/cpp/bit_io/bitinput.h> #include <library/cpp/bit_io/bitoutput.h> -#include <util/string/cast.h> +#include <util/string/cast.h> namespace NCodecs { template <typename T, bool WithDelta = false> diff --git a/library/cpp/codecs/solar_codec.h b/library/cpp/codecs/solar_codec.h index d1ded5c208..7158ae7926 100644 --- a/library/cpp/codecs/solar_codec.h +++ b/library/cpp/codecs/solar_codec.h @@ -4,7 +4,7 @@ #include <library/cpp/containers/comptrie/comptrie_trie.h> #include <library/cpp/codecs/greedy_dict/gd_builder.h> -#include <util/string/cast.h> +#include <util/string/cast.h> #include <util/string/escape.h> namespace NCodecs { diff --git a/library/cpp/codecs/ut/float_huffman_ut.cpp b/library/cpp/codecs/ut/float_huffman_ut.cpp index 91bf9b42b3..3156fb1f46 100644 --- a/library/cpp/codecs/ut/float_huffman_ut.cpp +++ b/library/cpp/codecs/ut/float_huffman_ut.cpp @@ -167,32 +167,32 @@ Y_UNIT_TEST_SUITE(FloatHuffmanTest) { } Y_UNIT_TEST(TestCompress) { - const auto codedFactors = fh::Encode(Factors); + const auto codedFactors = fh::Encode(Factors); UNIT_ASSERT_VALUES_EQUAL(codedFactors.size(), CodedSize); for (size_t i = 0; i < Min(codedFactors.size(), CodedSize); ++i) - UNIT_ASSERT_VALUES_EQUAL((ui8)codedFactors[i], CodedFactors[i]); + UNIT_ASSERT_VALUES_EQUAL((ui8)codedFactors[i], CodedFactors[i]); //PrintCompressed(codedFactors); } Y_UNIT_TEST(TestSimpleDecompress) { - TVector<float> factors = fh::Decode(CodedFactorsBuf); + TVector<float> factors = fh::Decode(CodedFactorsBuf); UNIT_ASSERT_VALUES_EQUAL(factors.size(), FactorCount); for (size_t i = 0; i < Min(factors.size(), FactorCount); ++i) UNIT_ASSERT_VALUES_EQUAL(factors[i], Factors[i]); //PrintDecompressed(factors); } - Y_UNIT_TEST(TestDecompressInParts) { + Y_UNIT_TEST(TestDecompressInParts) { float factors[FactorCount]; FillWithGarbage(factors, FactorCount); - fh::TDecoder decoder(CodedFactorsBuf); + fh::TDecoder decoder(CodedFactorsBuf); const size_t firstPack = 100; // unpack first pack - UNIT_ASSERT_VALUES_EQUAL(decoder.Decode({factors, firstPack}), firstPack); + UNIT_ASSERT_VALUES_EQUAL(decoder.Decode({factors, firstPack}), firstPack); // unpack all the rest - UNIT_ASSERT_VALUES_EQUAL(decoder.Decode({factors + firstPack, FactorCount - firstPack}), FactorCount - firstPack); + UNIT_ASSERT_VALUES_EQUAL(decoder.Decode({factors + firstPack, FactorCount - firstPack}), FactorCount - firstPack); - for (size_t i = 0; i < FactorCount; ++i) + for (size_t i = 0; i < FactorCount; ++i) UNIT_ASSERT_VALUES_EQUAL(factors[i], Factors[i]); //PrintDecompressed(factors); } @@ -200,18 +200,18 @@ Y_UNIT_TEST_SUITE(FloatHuffmanTest) { Y_UNIT_TEST(TestSkip) { float factors[FactorCount]; FillWithGarbage(factors, FactorCount); - fh::TDecoder decoder(CodedFactorsBuf); + fh::TDecoder decoder(CodedFactorsBuf); const size_t firstPack = 100; // unpack first pack - UNIT_ASSERT_VALUES_EQUAL(decoder.Decode({factors, firstPack}), firstPack); + UNIT_ASSERT_VALUES_EQUAL(decoder.Decode({factors, firstPack}), firstPack); // skip some factors const size_t skipCount = 60; - UNIT_ASSERT_VALUES_EQUAL(decoder.Skip(skipCount / 2), skipCount / 2); + UNIT_ASSERT_VALUES_EQUAL(decoder.Skip(skipCount / 2), skipCount / 2); // unpack all, except some factors in the end - const auto toDecode = FactorCount - firstPack - skipCount; - UNIT_ASSERT_VALUES_EQUAL(decoder.Decode({factors + firstPack, toDecode}), toDecode); - UNIT_ASSERT_VALUES_EQUAL(decoder.Skip(skipCount / 2), skipCount / 2); - for (size_t i = 0; i < FactorCount - skipCount; ++i) { + const auto toDecode = FactorCount - firstPack - skipCount; + UNIT_ASSERT_VALUES_EQUAL(decoder.Decode({factors + firstPack, toDecode}), toDecode); + UNIT_ASSERT_VALUES_EQUAL(decoder.Skip(skipCount / 2), skipCount / 2); + for (size_t i = 0; i < FactorCount - skipCount; ++i) { size_t correctedI = i < firstPack ? i : i + skipCount / 2; UNIT_ASSERT_VALUES_EQUAL(factors[i], Factors[correctedI]); } @@ -227,11 +227,11 @@ Y_UNIT_TEST_SUITE(FloatHuffmanTest) { "d4ZfQZrETm3B+OxxB8bbnTPM5+qtbQ92mJ3fHPGj+iH5+8tzcnJuamry1tWUw" "MBD693f07+9+DQQEkIGAgIgPetzN5yEbAGxWpbCNxXK/0JGTKRz2KkIoR7aM"; UNIT_ASSERT_EXCEPTION( - fh::Decode(Base64Decode(brokenBase64Encoded)), + fh::Decode(Base64Decode(brokenBase64Encoded)), yexception); } - - Y_UNIT_TEST(TestDecompressEmpty) { - UNIT_ASSERT_EXCEPTION(fh::Decode({}), yexception); - } + + Y_UNIT_TEST(TestDecompressEmpty) { + UNIT_ASSERT_EXCEPTION(fh::Decode({}), yexception); + } }; diff --git a/library/cpp/codecs/ya.make b/library/cpp/codecs/ya.make index 174db32828..7e76fb0c9a 100644 --- a/library/cpp/codecs/ya.make +++ b/library/cpp/codecs/ya.make @@ -11,7 +11,7 @@ SRCS( codecs_registry.cpp comptable_codec.cpp delta_codec.cpp - float_huffman.cpp + float_huffman.cpp huffman_codec.cpp pfor_codec.cpp solar_codec.cpp |