1 /*
2 Copyright (C) 2015 Volker Krause <vkrause@kde.org>
3
4 This program is free software; you can redistribute it and/or modify it
5 under the terms of the GNU Library General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or (at your
7 option) any later version.
8
9 This program is distributed in the hope that it will be useful, but WITHOUT
10 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public
12 License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <https://www.gnu.org/licenses/>.
16 */
17
18 #include "elfsysvhashsection.h"
19 #include "elfsymboltablesection.h"
20
21 #include <elf.h>
22 #include <cassert>
23
ElfSysvHashSection(ElfFile * file,ElfSectionHeader * shdr)24 ElfSysvHashSection::ElfSysvHashSection(ElfFile* file, ElfSectionHeader* shdr):
25 ElfHashSection(file, shdr)
26 {
27 }
28
29 ElfSysvHashSection::~ElfSysvHashSection() = default;
30
bucketCount() const31 uint32_t ElfSysvHashSection::bucketCount() const
32 {
33 return *reinterpret_cast<const uint32_t*>(rawData());
34 }
35
bucket(uint32_t index) const36 uint32_t ElfSysvHashSection::bucket(uint32_t index) const
37 {
38 return *(reinterpret_cast<const uint32_t*>(rawData()) + 2 + index);
39 }
40
chainCount() const41 uint32_t ElfSysvHashSection::chainCount() const
42 {
43 return *(reinterpret_cast<const uint32_t*>(rawData()) + 1);
44 }
45
chain(uint32_t index) const46 uint32_t ElfSysvHashSection::chain(uint32_t index) const
47 {
48 return *(reinterpret_cast<const uint32_t*>(rawData()) + 2 + bucketCount() + index);
49 }
50
hash(const char * name)51 uint32_t ElfSysvHashSection::hash(const char* name)
52 {
53 unsigned long h = 0, g;
54 while (*name)
55 {
56 h = (h << 4) + *name++;
57 if ((g = h & 0xf0000000))
58 h ^= g >> 24;
59 h &= ~g;
60 }
61 return h;
62 }
63
lookup(const char * name) const64 ElfSymbolTableEntry* ElfSysvHashSection::lookup(const char* name) const
65 {
66 const auto x = hash(name);
67
68 const auto symTab = linkedSection<ElfSymbolTableSection>();
69 assert(symTab);
70 auto y = bucket(x % bucketCount());
71 while (y != STN_UNDEF) {
72 const auto entry = symTab->entry(y);
73 if (strcmp(entry->name(), name) == 0)
74 return entry;
75 y = chain(y);
76 }
77
78 return nullptr;
79 }
80
histogram() const81 QVector<uint32_t> ElfSysvHashSection::histogram() const
82 {
83 QVector<uint32_t> hist;
84 for (uint i = 0; i < bucketCount(); ++i) {
85 int count = 0;
86
87 auto y = bucket(i);
88 while (y != STN_UNDEF) {
89 ++count;
90 y = chain(y);
91 }
92
93 hist.resize(std::max(hist.size(), count + 1));
94 hist[count]++;
95 }
96 return hist;
97 }
98
averagePrefixLength() const99 double ElfSysvHashSection::averagePrefixLength() const
100 {
101 int sum = 0;
102 int count = 0;
103
104 const auto symTab = linkedSection<ElfSymbolTableSection>();
105 assert(symTab);
106
107 for (uint i = 0; i < bucketCount(); ++i) {
108 auto y1 = bucket(i);
109 while (y1 != STN_UNDEF) {
110 const auto entry1 = symTab->entry(y1);
111 auto y2 = chain(y1);
112 while (y2 != STN_UNDEF) {
113 const auto entry2 = symTab->entry(y2);
114 sum += commonPrefixLength(entry1->name(), entry2->name());
115 ++count;
116 y2 = chain(y2);
117 }
118
119 y1 = chain(y1);
120 }
121 }
122
123 return count > 0 ? (double)sum / (double)count : 0.0;
124 }
125