Intel® OpenMP* Runtime Library
 All Classes Functions Variables Typedefs Enumerations Enumerator Groups Pages
extractExternal.cpp
1 /*
2  * extractExternal.cpp
3  * $Revision: 42181 $
4  * $Date: 2013-03-26 15:04:45 -0500 (Tue, 26 Mar 2013) $
5  */
6 
7 /* <copyright>
8  Copyright (c) 2006-2013 Intel Corporation. All Rights Reserved.
9 
10  Redistribution and use in source and binary forms, with or without
11  modification, are permitted provided that the following conditions
12  are met:
13 
14  * Redistributions of source code must retain the above copyright
15  notice, this list of conditions and the following disclaimer.
16  * Redistributions in binary form must reproduce the above copyright
17  notice, this list of conditions and the following disclaimer in the
18  documentation and/or other materials provided with the distribution.
19  * Neither the name of Intel Corporation nor the names of its
20  contributors may be used to endorse or promote products derived
21  from this software without specific prior written permission.
22 
23  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27  HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
30  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
31  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 
35 </copyright> */
36 
37 #include <stdlib.h>
38 #include <iostream>
39 #include <strstream>
40 #include <fstream>
41 #include <string>
42 #include <set>
43 #include <map>
44 
45 /* Given a set of n object files h ('external' object files) and a set of m
46  object files o ('internal' object files),
47  1. Determines r, the subset of h that o depends on, directly or indirectly
48  2. Removes the files in h - r from the file system
49  3. For each external symbol defined in some file in r, rename it in r U o
50  by prefixing it with "__kmp_external_"
51  Usage:
52  hide.exe <n> <filenames for h> <filenames for o>
53 
54  Thus, the prefixed symbols become hidden in the sense that they now have a special
55  prefix.
56 */
57 
58 using namespace std;
59 
60 void stop(char* errorMsg) {
61  printf("%s\n", errorMsg);
62  exit(1);
63 }
64 
65 // an entry in the symbol table of a .OBJ file
66 class Symbol {
67 public:
68  __int64 name;
69  unsigned value;
70  unsigned short sectionNum, type;
71  char storageClass, nAux;
72 };
73 
74 class _rstream : public istrstream {
75 private:
76  const char *buf;
77 protected:
78  _rstream(pair<const char*, streamsize> p):istrstream(p.first,p.second),buf(p.first){}
79  ~_rstream() {
80  delete[]buf;
81  }
82 };
83 
84 /* A stream encapuslating the content of a file or the content of a string, overriding the
85  >> operator to read various integer types in binary form, as well as a symbol table
86  entry.
87 */
88 class rstream : public _rstream {
89 private:
90  template<class T>
91  inline rstream& doRead(T &x) {
92  read((char*)&x, sizeof(T));
93  return *this;
94  }
95  static pair<const char*, streamsize> getBuf(const char *fileName) {
96  ifstream raw(fileName,ios::binary | ios::in);
97  if(!raw.is_open())
98  stop("rstream.getBuf: Error opening file");
99  raw.seekg(0,ios::end);
100  streampos fileSize = raw.tellg();
101  if(fileSize < 0)
102  stop("rstream.getBuf: Error reading file");
103  char *buf = new char[fileSize];
104  raw.seekg(0,ios::beg);
105  raw.read(buf, fileSize);
106  return pair<const char*, streamsize>(buf,fileSize);
107  }
108 public:
109  // construct from a string
110  rstream(const char *buf,streamsize size):_rstream(pair<const char*,streamsize>(buf, size)){}
111  /* construct from a file whole content is fully read once to initialize the content of
112  this stream
113  */
114  rstream(const char *fileName):_rstream(getBuf(fileName)){}
115  rstream& operator>>(int &x) {
116  return doRead(x);
117  }
118  rstream& operator>>(unsigned &x) {
119  return doRead(x);
120  }
121  rstream& operator>>(short &x) {
122  return doRead(x);
123  }
124  rstream& operator>>(unsigned short &x) {
125  return doRead(x);
126  }
127  rstream& operator>>(Symbol &e) {
128  read((char*)&e, 18);
129  return *this;
130  }
131 };
132 
133 // string table in a .OBJ file
134 class StringTable {
135 private:
136  map<string, unsigned> directory;
137  size_t length;
138  char *data;
139 
140  // make <directory> from <length> bytes in <data>
141  void makeDirectory(void) {
142  unsigned i = 4;
143  while(i < length) {
144  string s = string(data + i);
145  directory.insert(make_pair(s, i));
146  i += s.size() + 1;
147  }
148  }
149  // initialize <length> and <data> with contents specified by the arguments
150  void init(const char *_data) {
151  unsigned _length = *(unsigned*)_data;
152 
153  if(_length < sizeof(unsigned) || _length != *(unsigned*)_data)
154  stop("StringTable.init: Invalid symbol table");
155  if(_data[_length - 1]) {
156  // to prevent runaway strings, make sure the data ends with a zero
157  data = new char[length = _length + 1];
158  data[_length] = 0;
159  } else {
160  data = new char[length = _length];
161  }
162  *(unsigned*)data = length;
163  memcpy(data + sizeof(unsigned), _data + sizeof(unsigned),
164  length - sizeof(unsigned));
165  makeDirectory();
166  }
167 public:
168  StringTable(rstream &f) {
169  /* Construct string table by reading from f.
170  */
171  streampos s;
172  unsigned strSize;
173  char *strData;
174 
175  s = f.tellg();
176  f>>strSize;
177  if(strSize < sizeof(unsigned))
178  stop("StringTable: Invalid string table");
179  strData = new char[strSize];
180  *(unsigned*)strData = strSize;
181  // read the raw data into <strData>
182  f.read(strData + sizeof(unsigned), strSize - sizeof(unsigned));
183  s = f.tellg() - s;
184  if(s < strSize)
185  stop("StringTable: Unexpected EOF");
186  init(strData);
187  delete[]strData;
188  }
189  StringTable(const set<string> &strings) {
190  /* Construct string table from given strings.
191  */
192  char *p;
193  set<string>::const_iterator it;
194  size_t s;
195 
196  // count required size for data
197  for(length = sizeof(unsigned), it = strings.begin(); it != strings.end(); ++it) {
198  size_t l = (*it).size();
199 
200  if(l > (unsigned) 0xFFFFFFFF)
201  stop("StringTable: String too long");
202  if(l > 8) {
203  length += l + 1;
204  if(length > (unsigned) 0xFFFFFFFF)
205  stop("StringTable: Symbol table too long");
206  }
207  }
208  data = new char[length];
209  *(unsigned*)data = length;
210  // populate data and directory
211  for(p = data + sizeof(unsigned), it = strings.begin(); it != strings.end(); ++it) {
212  const string &str = *it;
213  size_t l = str.size();
214  if(l > 8) {
215  directory.insert(make_pair(str, p - data));
216  memcpy(p, str.c_str(), l);
217  p[l] = 0;
218  p += l + 1;
219  }
220  }
221  }
222  ~StringTable() {
223  delete[] data;
224  }
225  /* Returns encoding for given string based on this string table.
226  Error if string length is greater than 8 but string is not in
227  the string table--returns 0.
228  */
229  __int64 encode(const string &str) {
230  __int64 r;
231 
232  if(str.size() <= 8) {
233  // encoded directly
234  ((char*)&r)[7] = 0;
235  strncpy((char*)&r, str.c_str(), 8);
236  return r;
237  } else {
238  // represented as index into table
239  map<string,unsigned>::const_iterator it = directory.find(str);
240  if(it == directory.end())
241  stop("StringTable::encode: String now found in string table");
242  ((unsigned*)&r)[0] = 0;
243  ((unsigned*)&r)[1] = (*it).second;
244  return r;
245  }
246  }
247  /* Returns string represented by x based on this string table.
248  Error if x references an invalid position in the table--returns
249  the empty string.
250  */
251  string decode(__int64 x) const {
252  if(*(unsigned*)&x == 0) {
253  // represented as index into table
254  unsigned &p = ((unsigned*)&x)[1];
255  if(p >= length)
256  stop("StringTable::decode: Invalid string table lookup");
257  return string(data + p);
258  } else {
259  // encoded directly
260  char *p = (char*)&x;
261  int i;
262 
263  for(i = 0; i < 8 && p[i]; ++i);
264  return string(p, i);
265  }
266  }
267  void write(ostream &os) {
268  os.write(data, length);
269  }
270 };
271 
272 /* for the named object file, determines the set of defined symbols and the set of undefined external symbols
273  and writes them to <defined> and <undefined> respectively
274 */
275 void computeExternalSymbols(const char *fileName, set<string> *defined, set<string> *undefined){
276  streampos fileSize;
277  size_t strTabStart;
278  unsigned symTabStart, symNEntries;
279  rstream f(fileName);
280 
281  f.seekg(0,ios::end);
282  fileSize = f.tellg();
283 
284  f.seekg(8);
285  f >> symTabStart >> symNEntries;
286  // seek to the string table
287  f.seekg(strTabStart = symTabStart + 18 * (size_t)symNEntries);
288  if(f.eof()) {
289  printf("computeExternalSymbols: fileName='%s', fileSize = %lu, symTabStart = %u, symNEntries = %u\n",
290  fileName, (unsigned long) fileSize, symTabStart, symNEntries);
291  stop("computeExternalSymbols: Unexpected EOF 1");
292  }
293  StringTable stringTable(f); // read the string table
294  if(f.tellg() != fileSize)
295  stop("computeExternalSymbols: Unexpected data after string table");
296 
297  f.clear();
298  f.seekg(symTabStart); // seek to the symbol table
299 
300  defined->clear(); undefined->clear();
301  for(int i = 0; i < symNEntries; ++i) {
302  // process each entry
303  Symbol e;
304 
305  if(f.eof())
306  stop("computeExternalSymbols: Unexpected EOF 2");
307  f>>e;
308  if(f.fail())
309  stop("computeExternalSymbols: File read error");
310  if(e.nAux) { // auxiliary entry: skip
311  f.seekg(e.nAux * 18, ios::cur);
312  i += e.nAux;
313  }
314  // if symbol is extern and defined in the current file, insert it
315  if(e.storageClass == 2)
316  if(e.sectionNum)
317  defined->insert(stringTable.decode(e.name));
318  else
319  undefined->insert(stringTable.decode(e.name));
320  }
321 }
322 
323 /* For each occurence of an external symbol in the object file named by
324  by <fileName> that is a member of <hide>, renames it by prefixing
325  with "__kmp_external_", writing back the file in-place
326 */
327 void hideSymbols(char *fileName, const set<string> &hide) {
328  static const string prefix("__kmp_external_");
329  set<string> strings; // set of all occurring symbols, appropriately prefixed
330  streampos fileSize;
331  size_t strTabStart;
332  unsigned symTabStart, symNEntries;
333  int i;
334  rstream in(fileName);
335 
336  in.seekg(0,ios::end);
337  fileSize = in.tellg();
338 
339  in.seekg(8);
340  in >> symTabStart >> symNEntries;
341  in.seekg(strTabStart = symTabStart + 18 * (size_t)symNEntries);
342  if(in.eof())
343  stop("hideSymbols: Unexpected EOF");
344  StringTable stringTableOld(in); // read original string table
345 
346  if(in.tellg() != fileSize)
347  stop("hideSymbols: Unexpected data after string table");
348 
349  // compute set of occurring strings with prefix added
350  for(i = 0; i < symNEntries; ++i) {
351  Symbol e;
352 
353  in.seekg(symTabStart + i * 18);
354  if(in.eof())
355  stop("hideSymbols: Unexpected EOF");
356  in >> e;
357  if(in.fail())
358  stop("hideSymbols: File read error");
359  if(e.nAux)
360  i += e.nAux;
361  const string &s = stringTableOld.decode(e.name);
362  // if symbol is extern and found in <hide>, prefix and insert into strings,
363  // otherwise, just insert into strings without prefix
364  strings.insert( (e.storageClass == 2 && hide.find(s) != hide.end()) ?
365  prefix + s : s);
366  }
367 
368  ofstream out(fileName, ios::trunc | ios::out | ios::binary);
369  if(!out.is_open())
370  stop("hideSymbols: Error opening output file");
371 
372  // make new string table from string set
373  StringTable stringTableNew = StringTable(strings);
374 
375  // copy input file to output file up to just before the symbol table
376  in.seekg(0);
377  char *buf = new char[symTabStart];
378  in.read(buf, symTabStart);
379  out.write(buf, symTabStart);
380  delete []buf;
381 
382  // copy input symbol table to output symbol table with name translation
383  for(i = 0; i < symNEntries; ++i) {
384  Symbol e;
385 
386  in.seekg(symTabStart + i*18);
387  if(in.eof())
388  stop("hideSymbols: Unexpected EOF");
389  in >> e;
390  if(in.fail())
391  stop("hideSymbols: File read error");
392  const string &s = stringTableOld.decode(e.name);
393  out.seekp(symTabStart + i*18);
394  e.name = stringTableNew.encode( (e.storageClass == 2 && hide.find(s) != hide.end()) ?
395  prefix + s : s);
396  out.write((char*)&e, 18);
397  if(out.fail())
398  stop("hideSymbols: File write error");
399  if(e.nAux) {
400  // copy auxiliary symbol table entries
401  int nAux = e.nAux;
402  for(int j = 1; j <= nAux; ++j) {
403  in >> e;
404  out.seekp(symTabStart + (i + j) * 18);
405  out.write((char*)&e, 18);
406  }
407  i += nAux;
408  }
409  }
410  // output string table
411  stringTableNew.write(out);
412 }
413 
414 // returns true iff <a> and <b> have no common element
415 template <class T>
416 bool isDisjoint(const set<T> &a, const set<T> &b) {
417  set<T>::const_iterator ita, itb;
418 
419  for(ita = a.begin(), itb = b.begin(); ita != a.end() && itb != b.end();) {
420  const T &ta = *ita, &tb = *itb;
421  if(ta < tb)
422  ++ita;
423  else if (tb < ta)
424  ++itb;
425  else
426  return false;
427  }
428  return true;
429 }
430 
431 /* precondition: <defined> and <undefined> are arrays with <nTotal> elements where
432  <nTotal> >= <nExternal>. The first <nExternal> elements correspond to the external object
433  files and the rest correspond to the internal object files.
434  postcondition: file x is said to depend on file y if undefined[x] and defined[y] are not
435  disjoint. Returns the transitive closure of the set of internal object files, as a set of
436  file indexes, under the 'depends on' relation, minus the set of internal object files.
437 */
438 set<int> *findRequiredExternal(int nExternal, int nTotal, set<string> *defined, set<string> *undefined) {
439  set<int> *required = new set<int>;
440  set<int> fresh[2];
441  int i, cur = 0;
442  bool changed;
443 
444  for(i = nTotal - 1; i >= nExternal; --i)
445  fresh[cur].insert(i);
446  do {
447  changed = false;
448  for(set<int>::iterator it = fresh[cur].begin(); it != fresh[cur].end(); ++it) {
449  set<string> &s = undefined[*it];
450 
451  for(i = 0; i < nExternal; ++i) {
452  if(required->find(i) == required->end()) {
453  if(!isDisjoint(defined[i], s)) {
454  // found a new qualifying element
455  required->insert(i);
456  fresh[1 - cur].insert(i);
457  changed = true;
458  }
459  }
460  }
461  }
462  fresh[cur].clear();
463  cur = 1 - cur;
464  } while(changed);
465  return required;
466 }
467 
468 int main(int argc, char **argv) {
469  int nExternal, nInternal, i;
470  set<string> *defined, *undefined;
471  set<int>::iterator it;
472 
473  if(argc < 3)
474  stop("Please specify a positive integer followed by a list of object filenames");
475  nExternal = atoi(argv[1]);
476  if(nExternal <= 0)
477  stop("Please specify a positive integer followed by a list of object filenames");
478  if(nExternal + 2 > argc)
479  stop("Too few external objects");
480  nInternal = argc - nExternal - 2;
481  defined = new set<string>[argc - 2];
482  undefined = new set<string>[argc - 2];
483 
484  // determine the set of defined and undefined external symbols
485  for(i = 2; i < argc; ++i)
486  computeExternalSymbols(argv[i], defined + i - 2, undefined + i - 2);
487 
488  // determine the set of required external files
489  set<int> *requiredExternal = findRequiredExternal(nExternal, argc - 2, defined, undefined);
490  set<string> hide;
491 
492  /* determine the set of symbols to hide--namely defined external symbols of the
493  required external files
494  */
495  for(it = requiredExternal->begin(); it != requiredExternal->end(); ++it) {
496  int idx = *it;
497  set<string>::iterator it2;
498  /* We have to insert one element at a time instead of inserting a range because
499  the insert member function taking a range doesn't exist on Windows* OS, at least
500  at the time of this writing.
501  */
502  for(it2 = defined[idx].begin(); it2 != defined[idx].end(); ++it2)
503  hide.insert(*it2);
504  }
505 
506  /* process the external files--removing those that are not required and hiding
507  the appropriate symbols in the others
508  */
509  for(i = 0; i < nExternal; ++i)
510  if(requiredExternal->find(i) != requiredExternal->end())
511  hideSymbols(argv[2 + i], hide);
512  else
513  remove(argv[2 + i]);
514  // hide the appropriate symbols in the internal files
515  for(i = nExternal + 2; i < argc; ++i)
516  hideSymbols(argv[i], hide);
517  return 0;
518 }