Copilot commented on code in PR #50872: URL: https://github.com/apache/arrow/pull/50872#discussion_r3789198134
########## cpp/src/arrow/vendored/fsst/README.md: ########## @@ -0,0 +1,9 @@ +# Vendored CWI FSST + +This directory contains the FSST8 implementation from +https://github.com/cwida/fsst at commit +`89f49c580c6388acf3b6ed2a49e1bfde6c05e616`. + +The sources are unchanged except for trailing-whitespace normalization. Review Comment: This README says the vendored FSST sources are "unchanged except for trailing-whitespace normalization", but at least the AVX512 `.inc` files contain duplicated header blocks and modified MIT license text (e.g., "E1PRESS"). Please either re-vendor to match upstream verbatim, or adjust this statement to accurately describe the non-whitespace changes being applied. ########## cpp/src/parquet/fsst_internal.cc: ########## @@ -0,0 +1,346 @@ +// 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. + +#include "parquet/fsst_internal.h" + +#include <algorithm> +#include <array> +#include <cstdint> +#include <cstring> +#include <limits> +#include <numeric> +#include <utility> + +#include "arrow/buffer.h" +#include "arrow/result.h" +#include "arrow/vendored/fsst/fsst.h" + +#include "parquet/exception.h" + +namespace parquet::internal { +namespace { + +constexpr uint8_t kFsstEscape = 0xFF; + +} // namespace + +struct FsstSymbolTable::CwiState { + CwiState() { cwi_to_parquet_code.fill(kFsstEscape); } + + ~CwiState() { + if (encoder != nullptr) { + fsst_destroy(encoder); + } + } + + fsst_encoder_t* encoder = nullptr; + fsst_decoder_t decoder{}; + std::array<uint8_t, 255> cwi_to_parquet_code; +}; + +FsstSymbolTable::~FsstSymbolTable() = default; + +FsstSymbolTable::FsstSymbolTable(std::vector<std::string> symbols) + : symbols_(std::move(symbols)), cwi_(std::make_unique<CwiState>()) { + InitializeCwiDecoder(); +} + +std::shared_ptr<FsstSymbolTable> FsstSymbolTable::Train( + const std::vector<std::string>& values) { + std::vector<size_t> lengths; + std::vector<const unsigned char*> inputs; + if (values.empty()) { + // CWI expects at least one input slot. A zero-length sample produces a + // fully usable table for encoding values on later pages. + static constexpr unsigned char kEmptyInput = 0; + lengths.push_back(0); + inputs.push_back(&kEmptyInput); + } else { + lengths.reserve(values.size()); + inputs.reserve(values.size()); + for (const std::string& value : values) { + lengths.push_back(value.size()); + inputs.push_back(reinterpret_cast<const unsigned char*>(value.data())); + } + } + + auto trained = std::make_unique<CwiState>(); + trained->encoder = fsst_create(lengths.size(), lengths.data(), inputs.data(), + /*zeroTerminated=*/0); + if (trained->encoder == nullptr) { + throw ParquetException("CWI FSST failed to train a symbol table"); + } + const fsst_decoder_t native_decoder = fsst_decoder(trained->encoder); + + // The pinned CWI format stores nSymbols in byte 1 of its native export. + // We use it only to inspect the trained table; native bytes are never written + // to Parquet. + std::array<unsigned char, FSST_MAXHEADER> native_table{}; + const unsigned int native_size = fsst_export(trained->encoder, native_table.data()); + if (native_size < 17 || native_table[0] != 1) { + throw ParquetException("CWI FSST produced an invalid native symbol table"); + } + const uint16_t symbol_count = native_table[1]; + uint16_t histogram_count = 0; + for (int length = 0; length < 8; ++length) { + histogram_count += native_table[9 + length]; + } + if (histogram_count != symbol_count) { + throw ParquetException("CWI FSST produced an inconsistent native symbol table"); + } + + std::vector<uint16_t> native_codes(symbol_count); + std::iota(native_codes.begin(), native_codes.end(), 0); + std::stable_sort(native_codes.begin(), native_codes.end(), + [&](uint16_t left, uint16_t right) { + return native_decoder.len[left] < native_decoder.len[right]; + }); + + std::vector<std::string> symbols; + symbols.reserve(symbol_count); + for (uint16_t parquet_code = 0; parquet_code < symbol_count; ++parquet_code) { + const uint16_t native_code = native_codes[parquet_code]; + const uint8_t length = native_decoder.len[native_code]; + if (length == 0 || length > 8) { + throw ParquetException("CWI FSST produced an invalid symbol length"); + } + trained->cwi_to_parquet_code[native_code] = static_cast<uint8_t>(parquet_code); + symbols.emplace_back( + reinterpret_cast<const char*>(&native_decoder.symbol[native_code]), length); + } + + auto table = std::shared_ptr<FsstSymbolTable>(new FsstSymbolTable(std::move(symbols))); + table->cwi_->encoder = trained->encoder; + trained->encoder = nullptr; + table->cwi_->cwi_to_parquet_code = trained->cwi_to_parquet_code; + return table; +} + +std::shared_ptr<FsstSymbolTable> FsstSymbolTable::Deserialize( + const std::shared_ptr<::arrow::Buffer>& body) { + constexpr int max_length = 8; + constexpr int64_t fixed_size = 9; + if (body == nullptr || body->size() < fixed_size || body->size() > 2049) { + throw ParquetException("Invalid FSST symbol table body size: ", + body == nullptr ? -1 : body->size()); + } + + const uint8_t* data = body->data(); + const uint32_t symbol_count = data[0]; + + std::vector<uint32_t> histogram(max_length); + uint64_t histogram_sum = 0; + uint64_t expected_symbol_bytes = 0; + const uint8_t* histogram_data = data + 1; + for (int i = 0; i < max_length; ++i) { + histogram[i] = histogram_data[i]; + histogram_sum += histogram[i]; + expected_symbol_bytes += static_cast<uint64_t>(histogram[i]) * (i + 1); + } + if (histogram_sum != symbol_count) { + throw ParquetException("FSST length histogram does not match symbol count"); + } + if (expected_symbol_bytes != static_cast<uint64_t>(body->size() - fixed_size)) { + throw ParquetException("FSST symbol data size does not match length histogram"); + } + + std::vector<std::string> symbols; + symbols.reserve(symbol_count); + const char* symbol_data = reinterpret_cast<const char*>(data + fixed_size); + int64_t offset = 0; + for (int length = 1; length <= max_length; ++length) { + for (uint32_t i = 0; i < histogram[length - 1]; ++i) { + symbols.emplace_back(symbol_data + offset, length); + offset += length; + } + } + return std::shared_ptr<FsstSymbolTable>(new FsstSymbolTable(std::move(symbols))); +} + +std::shared_ptr<::arrow::Buffer> FsstSymbolTable::Serialize( + ::arrow::MemoryPool* pool) const { + constexpr int max_length = 8; + constexpr int64_t fixed_size = 9; + int64_t symbol_bytes = 0; + std::vector<uint32_t> histogram(max_length, 0); + for (const std::string& symbol : symbols_) { + ++histogram[symbol.size() - 1]; + symbol_bytes += static_cast<int64_t>(symbol.size()); + } + + auto buffer = ::arrow::AllocateBuffer(fixed_size + symbol_bytes, pool).ValueOrDie(); Review Comment: `AllocateBuffer(...).ValueOrDie()` will terminate the process on allocation failure instead of surfacing a Parquet/Arrow error. In libparquet code paths this should throw (via PARQUET_ASSIGN_OR_THROW / PARQUET_THROW_NOT_OK) rather than aborting. ########## cpp/src/arrow/vendored/fsst/fsst_avx512_unroll4.inc: ########## @@ -0,0 +1,228 @@ +// this software is distributed under the MIT License (http://www.opensource.org/licenses/MIT): +// this software is distributed under the MIT License (http://www.opensource.org/licenses/MIT): +// this software is distributed under the MIT License (http://www.opensource.org/licenses/MIT): +// this software is distributed under the MIT License (http://www.opensource.org/licenses/MIT): +// +// +// +// +// Copyright 2018-2020, CWI, TU Munich, FSU Jena +// Copyright 2018-2020, CWI, TU Munich, FSU Jena +// Copyright 2018-2020, CWI, TU Munich, FSU Jena +// Copyright 2018-2020, CWI, TU Munich, FSU Jena +// +// +// +// +// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files +// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files +// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files +// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files +// (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, +// (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, +// (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, +// (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, +// merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is +// merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is +// merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is +// merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// furnished to do so, subject to the following conditions: +// furnished to do so, subject to the following conditions: +// furnished to do so, subject to the following conditions: +// +// +// +// +// - The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. +// - The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. +// - The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. +// - The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. +// +// +// +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, E1PRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, E2PRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, E3PRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, E4PRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES Review Comment: The vendored FSST AVX512 include files have a corrupted/duplicated license header (e.g., "E1PRESS" / "E2PRESS" instead of "EXPRESS"). Since this text is part of the upstream MIT header, it should be preserved verbatim when vendoring to avoid confusion and make upstream diffs auditable. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
