/* Copyright 2017 - 2025 R. Thomas

* Copyright 2017 - 2025 Quarkslab

*

* Licensed 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 <iomanip>

#include <numeric>

#include <sstream>

#include <utility>

#include "LIEF/Visitor.hpp"

#include "LIEF/BinaryStream/SpanStream.hpp"

#include "LIEF/ELF/hash.hpp"

#include "LIEF/ELF/utils.hpp"

#include "LIEF/ELF/GnuHash.hpp"

#include "LIEF/ELF/Segment.hpp"

#include "logging.hpp"

#include "ELF/Structures.hpp"

namespace LIEF {

namespace ELF {

bool GnuHash::check_bloom_filter(uint32_t hash) const {

const size_t C = c_;

const uint32_t h1 = hash;

const uint32_t h2 = hash >> shift2();

const uint32_t n1 = (h1 / C) % maskwords();

const uint32_t b1 = h1 % C;

const uint32_t b2 = h2 % C;

const uint64_t filter = bloom_filters()[n1];

return ((filter >> b1) & (filter >> b2) & 1) != 0u;

}

bool GnuHash::check(const std::string& symbol_name) const {

uint32_t hash = dl_new_hash(symbol_name.c_str());

return check(hash);

}

bool GnuHash::check(uint32_t hash) const {

if (!check_bloom_filter(hash)) { // Bloom filter not passed

return false;

}

if (!check_bucket(hash)) { // hash buck not passed

return false;

}

return true;

}

void GnuHash::accept(Visitor& visitor) const {

visitor.visit(*this);

}

template<typename ELF_T>

std::unique_ptr<GnuHash> GnuHash::parse(SpanStream& strm, uint64_t dynsymcount) {

// See: https://github.com/lattera/glibc/blob/master/elf/dl-lookup.c#L860

// and https://github.com/lattera/glibc/blob/master/elf/dl-lookup.c#L226

using uint__ = typename ELF_T::uint;

LIEF_DEBUG("== Parse symbol GNU hash ==");

const uint64_t opos = strm.pos();

auto gnuhash = std::make_unique<GnuHash>();

gnuhash->c_ = sizeof(uint__) * 8;

auto nbuckets = strm.read<uint32_t>();

if (!nbuckets) {

LIEF_ERR("Can't read the number of buckets");

return nullptr;

}

auto symidx = strm.read<uint32_t>();

if (!symidx) {

LIEF_ERR("Can't read the symndx");

return nullptr;

}

gnuhash->symbol_index_ = *symidx;

auto maskwords = strm.read<uint32_t>();

if (!maskwords) {

LIEF_ERR("Can't read the maskwords");

return nullptr;

}

auto shift2 = strm.read<uint32_t>();

if (!shift2) {

LIEF_ERR("Can't read the shift2");

return nullptr;

}

gnuhash->shift2_ = *shift2;

if (*maskwords & (*maskwords - 1)) {

LIEF_WARN("maskwords is not a power of 2");

}

std::vector<uint__> bloom_filters;

if (strm.read_objects(bloom_filters, *maskwords)) {

std::copy(bloom_filters.begin(), bloom_filters.end(),

std::back_inserter(gnuhash->bloom_filters_));

} else {

LIEF_ERR("GNU Hash, maskwords corrupted");

}

if (!strm.read_objects(gnuhash->buckets_, *nbuckets)) {

LIEF_ERR("GNU Hash, buckets corrupted");

}

if (dynsymcount > 0 && dynsymcount >= gnuhash->symbol_index_) {

const uint32_t nb_hash = dynsymcount - gnuhash->symbol_index_;

if (!strm.read_objects(gnuhash->hash_values_, nb_hash)) {

LIEF_ERR("Can't read hash values (count={})", nb_hash);

}

}

gnuhash->original_size_ = strm.pos() - opos;

return gnuhash;

}

template<class ELF_T>

result<uint32_t> GnuHash::nb_symbols(SpanStream& strm) {

using uint__ = typename ELF_T::uint;

const auto res_nbuckets = strm.read<uint32_t>();

if (!res_nbuckets) {

return 0;

}

const auto res_symndx = strm.read<uint32_t>();

if (!res_symndx) {

return 0;

}

const auto res_maskwords = strm.read<uint32_t>();

if (!res_maskwords) {

return 0;

}

const auto nbuckets = *res_nbuckets;

const auto symndx = *res_symndx;

const auto maskwords = *res_maskwords;

// skip shift2, unused as we don't need the bloom filter to count syms.

strm.increment_pos(sizeof(uint32_t));

if (maskwords & (maskwords - 1)) {

LIEF_WARN("maskwords is not a power of 2");

return 0;

}

// skip bloom filter mask words

strm.increment_pos(sizeof(uint__) * (maskwords));

uint32_t max_bucket = 0;

for (size_t i = 0; i < nbuckets; ++i) {

auto bucket = strm.read<uint32_t>();

if (!bucket) {

break;

}

if (*bucket > max_bucket) {

max_bucket = *bucket;

}

}

if (max_bucket == 0) {

return 0;

}

// Skip to the contents of the bucket with the largest symbol index

strm.increment_pos(sizeof(uint32_t) * (max_bucket - symndx));

// Count values in the bucket

uint32_t hash_value = 0;

size_t nsyms = 0;

do {

if (!strm.can_read<uint32_t>()) {

return 0;

}

hash_value = *strm.read<uint32_t>();

nsyms++;

} while ((hash_value & 1) == 0); // "It is set to 1 when a symbol is the last symbol in a given hash bucket"

return max_bucket + nsyms;

}

std::ostream& operator<<(std::ostream& os, const GnuHash& gnuhash) {

os << std::hex << std::left;

const std::vector<uint64_t>& bloom_filters = gnuhash.bloom_filters();

const std::vector<uint32_t>& buckets = gnuhash.buckets();

const std::vector<uint32_t>& hash_values = gnuhash.hash_values();

std::string bloom_filters_str = std::accumulate(

std::begin(bloom_filters),

std::end(bloom_filters), std::string{},

[] (const std::string& a, uint64_t bf) {

std::ostringstream hex_bf;

hex_bf << std::hex;

hex_bf << "0x" << bf;

return a.empty() ? "[" + hex_bf.str() : a + ", " + hex_bf.str();

});

bloom_filters_str += "]";

std::string buckets_str = std::accumulate(

std::begin(buckets),

std::end(buckets), std::string{},

[] (const std::string& a, uint32_t b) {

std::ostringstream hex_bucket;

hex_bucket << std::dec;

hex_bucket << b;

return a.empty() ? "[" + hex_bucket.str() : a + ", " + hex_bucket.str();

});

buckets_str += "]";

std::string hash_values_str = std::accumulate(

std::begin(hash_values),

std::end(hash_values), std::string{},

[] (const std::string& a, uint64_t hv) {

std::ostringstream hex_hv;

hex_hv << std::hex;

hex_hv << "0x" << hv;

return a.empty() ? "[" + hex_hv.str() : a + ", " + hex_hv.str();

});

hash_values_str += "]";

os << std::setw(33) << std::setfill(' ') << "Number of buckets:" << gnuhash.nb_buckets() << '\n';

os << std::setw(33) << std::setfill(' ') << "First symbol index:" << gnuhash.symbol_index() << '\n';

os << std::setw(33) << std::setfill(' ') << "Shift Count:" << gnuhash.shift2() << '\n';

os << std::setw(33) << std::setfill(' ') << "Bloom filters:" << bloom_filters_str << '\n';

os << std::setw(33) << std::setfill(' ') << "Buckets:" << buckets_str << '\n';

os << std::setw(33) << std::setfill(' ') << "Hash values:" << hash_values_str << '\n';

return os;

}

template

std::unique_ptr<GnuHash> GnuHash::parse<details::ELF64>(SpanStream&, uint64_t);

template

std::unique_ptr<GnuHash> GnuHash::parse<details::ELF32>(SpanStream&, uint64_t);

template

std::unique_ptr<GnuHash> GnuHash::parse<details::ELF32_x32>(SpanStream&, uint64_t);

template

std::unique_ptr<GnuHash> GnuHash::parse<details::ELF32_arm64>(SpanStream&, uint64_t);

template

result<uint32_t> GnuHash::nb_symbols<details::ELF64>(SpanStream&);

template

result<uint32_t> GnuHash::nb_symbols<details::ELF32>(SpanStream&);

template

result<uint32_t> GnuHash::nb_symbols<details::ELF32_x32>(SpanStream&);

template

result<uint32_t> GnuHash::nb_symbols<details::ELF32_arm64>(SpanStream&);

} // namespace ELF

} // namespace LIEF