ddmd.libomf source code

1 /**
2  * Compiler implementation of the
3  * $(LINK2 http://www.dlang.org, D programming language).
4  *
5  * Copyright:   Copyright (c) 1999-2016 by Digital Mars, All Rights Reserved
6  * Authors:     $(LINK2 http://www.digitalmars.com, Walter Bright)
7  * License:     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
8  * Source:      $(DMDSRC _libomf.d)
9  */
10 
11 module ddmd.libomf;
12 
13 import core.stdc.stdio;
14 import core.stdc..string;
15 import core.stdc.stdlib;
16 
17 import ddmd.globals;
18 import ddmd.utils;
19 import ddmd.lib;
20 
21 import ddmd.root.array;
22 import ddmd.root.file;
23 import ddmd.root.filename;
24 import ddmd.root.outbuffer;
25 import ddmd.root.stringtable;
26 
27 import ddmd.scanomf;
28 
29 enum LOG = false;
30 
31 struct OmfObjSymbol
32 {
33     char* name;
34     OmfObjModule* om;
35 }
36 
37 alias OmfObjModules = Array!(OmfObjModule*);
38 alias OmfObjSymbols = Array!(OmfObjSymbol*);
39 
40 extern (C) uint _rotl(uint value, int shift);
41 extern (C) uint _rotr(uint value, int shift);
42 
43 final class LibOMF : Library
44 {
45     OmfObjModules objmodules; // OmfObjModule[]
46     OmfObjSymbols objsymbols; // OmfObjSymbol[]
47     StringTable tab;
48 
49     extern (D) this()
50     {
51         tab._init(14000);
52     }
53 
54     /***************************************
55      * Add object module or library to the library.
56      * Examine the buffer to see which it is.
57      * If the buffer is NULL, use module_name as the file name
58      * and load the file.
59      */
60     override void addObject(const(char)* module_name, const ubyte[] buffer)
61     {
62         static if (LOG)
63         {
64             printf("LibOMF::addObject(%s)\n", module_name ? module_name : "");
65         }
66 
67         void corrupt(int reason)
68         {
69             error("corrupt OMF object module %s %d", module_name, reason);
70         }
71 
72         auto buf = buffer.ptr;
73         auto buflen = buffer.length;
74         if (!buf)
75         {
76             assert(module_name);
77             File* file = File.create(cast(char*)module_name);
78             readFile(Loc(), file);
79             buf = file.buffer;
80             buflen = file.len;
81             file._ref = 1;
82         }
83         uint g_page_size;
84         ubyte* pstart = cast(ubyte*)buf;
85         bool islibrary = false;
86         /* See if it's an OMF library.
87          * Don't go by file extension.
88          */
89         struct LibHeader
90         {
91         align(1):
92             ubyte recTyp; // 0xF0
93             ushort pagesize;
94             uint lSymSeek;
95             ushort ndicpages;
96         }
97 
98         /* Determine if it is an OMF library, an OMF object module,
99          * or something else.
100          */
101         if (buflen < (LibHeader).sizeof)
102             return corrupt(__LINE__);
103         const lh = cast(const(LibHeader)*)buf;
104         if (lh.recTyp == 0xF0)
105         {
106             /* OMF library
107              * The modules are all at buf[g_page_size .. lh->lSymSeek]
108              */
109             islibrary = 1;
110             g_page_size = lh.pagesize + 3;
111             buf = cast(ubyte*)(pstart + g_page_size);
112             if (lh.lSymSeek > buflen || g_page_size > buflen)
113                 return corrupt(__LINE__);
114             buflen = lh.lSymSeek - g_page_size;
115         }
116         else if (lh.recTyp == '!' && memcmp(lh, cast(char*)"!<arch>\n", 8) == 0)
117         {
118             error("COFF libraries not supported");
119             return;
120         }
121         else
122         {
123             // Not a library, assume OMF object module
124             g_page_size = 16;
125         }
126         bool firstmodule = true;
127 
128         void addOmfObjModule(char* name, void* base, size_t length)
129         {
130             auto om = new OmfObjModule();
131             om.base = cast(ubyte*)base;
132             om.page = om.page = cast(ushort)((om.base - pstart) / g_page_size);
133             om.length = cast(uint)length;
134             /* Determine the name of the module
135              */
136             if (firstmodule && module_name && !islibrary)
137             {
138                 // Remove path and extension
139                 auto n = strdup(FileName.name(module_name));
140                 om.name = n[0 .. strlen(n)];
141                 char* ext = cast(char*)FileName.ext(n);
142                 if (ext)
143                     ext[-1] = 0;
144             }
145             else
146             {
147                 /* Use THEADR name as module name,
148                  * removing path and extension.
149                  */
150                 auto n = strdup(FileName.name(name));
151                 om.name = n[0 .. strlen(n)];
152                 char* ext = cast(char*)FileName.ext(n);
153                 if (ext)
154                     ext[-1] = 0;
155             }
156             firstmodule = false;
157             this.objmodules.push(om);
158         }
159 
160         if (scanOmfLib(&addOmfObjModule, cast(void*)buf, buflen, g_page_size))
161             return corrupt(__LINE__);
162     }
163 
164     /*****************************************************************************/
165 
166     void addSymbol(OmfObjModule* om, const(char)* name, int pickAny = 0)
167     {
168         static if (LOG)
169         {
170             printf("LibOMF::addSymbol(%s, %s, %d)\n", om.name.ptr, name, pickAny);
171         }
172         const namelen = strlen(name);
173         StringValue* s = tab.insert(name, namelen, null);
174         if (!s)
175         {
176             // already in table
177             if (!pickAny)
178             {
179                 const s2 = tab.lookup(name, namelen);
180                 assert(s2);
181                 const os = cast(const(OmfObjSymbol)*)s2.ptrvalue;
182                 error("multiple definition of %s: %s and %s: %s", om.name.ptr, name, os.om.name.ptr, os.name);
183             }
184         }
185         else
186         {
187             auto os = new OmfObjSymbol();
188             os.name = strdup(name);
189             os.om = om;
190             s.ptrvalue = cast(void*)os;
191             objsymbols.push(os);
192         }
193     }
194 
195 private:
196     /************************************
197      * Scan single object module for dictionary symbols.
198      * Send those symbols to LibOMF::addSymbol().
199      */
200     void scanObjModule(OmfObjModule* om)
201     {
202         static if (LOG)
203         {
204             printf("LibMSCoff::scanObjModule(%s)\n", om.name.ptr);
205         }
206 
207         extern (D) void addSymbol(const(char)[] name, int pickAny)
208         {
209             this.addSymbol(om, name.ptr, pickAny);
210         }
211 
212         scanOmfObjModule(&addSymbol, om.base[0 .. om.length], om.name.ptr, loc);
213     }
214 
215     /***********************************
216      * Calculates number of pages needed for dictionary
217      * Returns:
218      *      number of pages
219      */
220     ushort numDictPages(uint padding)
221     {
222         ushort ndicpages;
223         ushort bucksForHash;
224         ushort bucksForSize;
225         uint symSize = 0;
226         for (size_t i = 0; i < objsymbols.dim; i++)
227         {
228             OmfObjSymbol* s = objsymbols[i];
229             symSize += (strlen(s.name) + 4) & ~1;
230         }
231         for (size_t i = 0; i < objmodules.dim; i++)
232         {
233             OmfObjModule* om = objmodules[i];
234             size_t len = om.name.length;
235             if (len > 0xFF)
236                 len += 2; // Digital Mars long name extension
237             symSize += (len + 4 + 1) & ~1;
238         }
239         bucksForHash = cast(ushort)((objsymbols.dim + objmodules.dim + HASHMOD - 3) / (HASHMOD - 2));
240         bucksForSize = cast(ushort)((symSize + BUCKETSIZE - padding - padding - 1) / (BUCKETSIZE - padding));
241         ndicpages = (bucksForHash > bucksForSize) ? bucksForHash : bucksForSize;
242         //printf("ndicpages = %u\n",ndicpages);
243         // Find prime number greater than ndicpages
244         static __gshared uint* primes =
245         [
246             1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
247             47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
248             107, 109, 113, 127, 131, 137, 139, 149, 151, 157,
249             163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
250             223, 227, 229, 233, 239, 241, 251, 257, 263, 269,
251             271, 277, 281, 283, 293, 307, 311, 313, 317, 331,
252             337, 347, 349, 353, 359, 367, 373, 379, 383, 389,
253             397, 401, 409, 419, 421, 431, 433, 439, 443, 449,
254             457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
255             //521,523,541,547,
256             0
257         ];
258         for (size_t i = 0; 1; i++)
259         {
260             if (primes[i] == 0)
261             {
262                 // Quick and easy way is out.
263                 // Now try and find first prime number > ndicpages
264                 uint prime;
265                 for (prime = (ndicpages + 1) | 1; 1; prime += 2)
266                 {
267                     // Determine if prime is prime
268                     for (uint u = 3; u < prime / 2; u += 2)
269                     {
270                         if ((prime / u) * u == prime)
271                             goto L1;
272                     }
273                     break;
274                 L1:
275                 }
276                 ndicpages = cast(ushort)prime;
277                 break;
278             }
279             if (primes[i] > ndicpages)
280             {
281                 ndicpages = cast(ushort)primes[i];
282                 break;
283             }
284         }
285         return ndicpages;
286     }
287 
288     /*******************************************
289      * Write the module and symbol names to the dictionary.
290      * Returns:
291      *      false   failure
292      */
293     bool FillDict(ubyte* bucketsP, ushort ndicpages)
294     {
295         // max size that will fit in dictionary
296         enum LIBIDMAX = (512 - 0x25 - 3 - 4);
297         ubyte[4 + LIBIDMAX + 2 + 1] entry;
298         //printf("FillDict()\n");
299         // Add each of the module names
300         for (size_t i = 0; i < objmodules.dim; i++)
301         {
302             OmfObjModule* om = objmodules[i];
303             ushort n = cast(ushort)om.name.length;
304             if (n > 255)
305             {
306                 entry[0] = 0xFF;
307                 entry[1] = 0;
308                 *cast(ushort*)(entry.ptr + 2) = cast(ushort)(n + 1);
309                 memcpy(entry.ptr + 4, om.name.ptr, n);
310                 n += 3;
311             }
312             else
313             {
314                 entry[0] = cast(ubyte)(1 + n);
315                 memcpy(entry.ptr + 1, om.name.ptr, n);
316             }
317             entry[n + 1] = '!';
318             *(cast(ushort*)(n + 2 + entry.ptr)) = om.page;
319             if (n & 1)
320                 entry[n + 2 + 2] = 0;
321             if (!EnterDict(bucketsP, ndicpages, entry.ptr, n + 1))
322                 return false;
323         }
324         // Sort the symbols
325         qsort(objsymbols.tdata(), objsymbols.dim, (objsymbols[0]).sizeof, &NameCompare);
326         // Add each of the symbols
327         for (size_t i = 0; i < objsymbols.dim; i++)
328         {
329             OmfObjSymbol* os = objsymbols[i];
330             ushort n = cast(ushort)strlen(os.name);
331             if (n > 255)
332             {
333                 entry[0] = 0xFF;
334                 entry[1] = 0;
335                 *cast(ushort*)(entry.ptr + 2) = n;
336                 memcpy(entry.ptr + 4, os.name, n);
337                 n += 3;
338             }
339             else
340             {
341                 entry[0] = cast(ubyte)n;
342                 memcpy(entry.ptr + 1, os.name, n);
343             }
344             *(cast(ushort*)(n + 1 + entry.ptr)) = os.om.page;
345             if ((n & 1) == 0)
346                 entry[n + 3] = 0;
347             if (!EnterDict(bucketsP, ndicpages, entry.ptr, n))
348             {
349                 return false;
350             }
351         }
352         return true;
353     }
354 
355     /**********************************************
356      * Create and write library to libbuf.
357      * The library consists of:
358      *      library header
359      *      object modules...
360      *      dictionary header
361      *      dictionary pages...
362      */
363     protected override void WriteLibToBuffer(OutBuffer* libbuf)
364     {
365         /* Scan each of the object modules for symbols
366          * to go into the dictionary
367          */
368         for (size_t i = 0; i < objmodules.dim; i++)
369         {
370             OmfObjModule* om = objmodules[i];
371             scanObjModule(om);
372         }
373         uint g_page_size = 16;
374         /* Calculate page size so that the number of pages
375          * fits in 16 bits. This is because object modules
376          * are indexed by page number, stored as an unsigned short.
377          */
378         while (1)
379         {
380         Lagain:
381             static if (LOG)
382             {
383                 printf("g_page_size = %d\n", g_page_size);
384             }
385             uint offset = g_page_size;
386             for (size_t i = 0; i < objmodules.dim; i++)
387             {
388                 OmfObjModule* om = objmodules[i];
389                 uint page = offset / g_page_size;
390                 if (page > 0xFFFF)
391                 {
392                     // Page size is too small, double it and try again
393                     g_page_size *= 2;
394                     goto Lagain;
395                 }
396                 offset += OMFObjSize(om.base, om.length, om.name.ptr);
397                 // Round the size of the file up to the next page size
398                 // by filling with 0s
399                 uint n = (g_page_size - 1) & offset;
400                 if (n)
401                     offset += g_page_size - n;
402             }
403             break;
404         }
405         /* Leave one page of 0s at start as a dummy library header.
406          * Fill it in later with the real data.
407          */
408         libbuf.fill0(g_page_size);
409         /* Write each object module into the library
410          */
411         for (size_t i = 0; i < objmodules.dim; i++)
412         {
413             OmfObjModule* om = objmodules[i];
414             uint page = cast(uint)(libbuf.offset / g_page_size);
415             assert(page <= 0xFFFF);
416             om.page = cast(ushort)page;
417             // Write out the object module om
418             writeOMFObj(libbuf, om.base, om.length, om.name.ptr);
419             // Round the size of the file up to the next page size
420             // by filling with 0s
421             uint n = (g_page_size - 1) & libbuf.offset;
422             if (n)
423                 libbuf.fill0(g_page_size - n);
424         }
425         // File offset of start of dictionary
426         uint offset = cast(uint)libbuf.offset;
427         // Write dictionary header, then round it to a BUCKETPAGE boundary
428         ushort size = (BUCKETPAGE - (cast(short)offset + 3)) & (BUCKETPAGE - 1);
429         libbuf.writeByte(0xF1);
430         libbuf.writeword(size);
431         libbuf.fill0(size);
432         // Create dictionary
433         ubyte* bucketsP = null;
434         ushort ndicpages;
435         ushort padding = 32;
436         for (;;)
437         {
438             ndicpages = numDictPages(padding);
439             static if (LOG)
440             {
441                 printf("ndicpages = %d\n", ndicpages);
442             }
443             // Allocate dictionary
444             if (bucketsP)
445                 bucketsP = cast(ubyte*)realloc(bucketsP, ndicpages * BUCKETPAGE);
446             else
447                 bucketsP = cast(ubyte*)malloc(ndicpages * BUCKETPAGE);
448             assert(bucketsP);
449             memset(bucketsP, 0, ndicpages * BUCKETPAGE);
450             for (uint u = 0; u < ndicpages; u++)
451             {
452                 // 'next available' slot
453                 bucketsP[u * BUCKETPAGE + HASHMOD] = (HASHMOD + 1) >> 1;
454             }
455             if (FillDict(bucketsP, ndicpages))
456                 break;
457             padding += 16; // try again with more margins
458         }
459         // Write dictionary
460         libbuf.write(bucketsP, ndicpages * BUCKETPAGE);
461         if (bucketsP)
462             free(bucketsP);
463         // Create library header
464         struct Libheader
465         {
466         align(1):
467             ubyte recTyp;
468             ushort recLen;
469             uint trailerPosn;
470             ushort ndicpages;
471             ubyte flags;
472             char* filler;
473         }
474 
475         Libheader libHeader;
476         memset(&libHeader, 0, (Libheader).sizeof);
477         libHeader.recTyp = 0xF0;
478         libHeader.recLen = 0x0D;
479         libHeader.trailerPosn = offset + (3 + size);
480         libHeader.recLen = cast(ushort)(g_page_size - 3);
481         libHeader.ndicpages = ndicpages;
482         libHeader.flags = 1; // always case sensitive
483         // Write library header at start of buffer
484         memcpy(libbuf.data, &libHeader, (libHeader).sizeof);
485     }
486 }
487 
488 extern (C++) Library LibOMF_factory()
489 {
490     return new LibOMF();
491 }
492 
493 /*****************************************************************************/
494 /*****************************************************************************/
495 struct OmfObjModule
496 {
497     ubyte* base; // where are we holding it in memory
498     uint length; // in bytes
499     ushort page; // page module starts in output file
500     const(char)[] name; // module name, with terminating 0
501 }
502 
503 /*****************************************************************************/
504 /*****************************************************************************/
505 extern (C)
506 {
507     int NameCompare(const(void*) p1, const(void*) p2)
508     {
509         return strcmp((*cast(OmfObjSymbol**)p1).name, (*cast(OmfObjSymbol**)p2).name);
510     }
511 }
512 
513 enum HASHMOD = 0x25;
514 enum BUCKETPAGE = 512;
515 enum BUCKETSIZE = (BUCKETPAGE - HASHMOD - 1);
516 
517 /*******************************************
518  * Write a single entry into dictionary.
519  * Returns:
520  *      false   failure
521  */
522 extern (C++) static bool EnterDict(ubyte* bucketsP, ushort ndicpages, ubyte* entry, uint entrylen)
523 {
524     ushort uStartIndex;
525     ushort uStep;
526     ushort uStartPage;
527     ushort uPageStep;
528     ushort uIndex;
529     ushort uPage;
530     ushort n;
531     uint u;
532     uint nbytes;
533     ubyte* aP;
534     ubyte* zP;
535     aP = entry;
536     zP = aP + entrylen; // point at last char in identifier
537     uStartPage = 0;
538     uPageStep = 0;
539     uStartIndex = 0;
540     uStep = 0;
541     u = entrylen;
542     while (u--)
543     {
544         uStartPage = cast(ushort)_rotl(uStartPage, 2) ^ (*aP | 0x20);
545         uStep = cast(ushort)_rotr(uStep, 2) ^ (*aP++ | 0x20);
546         uStartIndex = cast(ushort)_rotr(uStartIndex, 2) ^ (*zP | 0x20);
547         uPageStep = cast(ushort)_rotl(uPageStep, 2) ^ (*zP-- | 0x20);
548     }
549     uStartPage %= ndicpages;
550     uPageStep %= ndicpages;
551     if (uPageStep == 0)
552         uPageStep++;
553     uStartIndex %= HASHMOD;
554     uStep %= HASHMOD;
555     if (uStep == 0)
556         uStep++;
557     uPage = uStartPage;
558     uIndex = uStartIndex;
559     // number of bytes in entry
560     nbytes = 1 + entrylen + 2;
561     if (entrylen > 255)
562         nbytes += 2;
563     while (1)
564     {
565         aP = &bucketsP[uPage * BUCKETPAGE];
566         uStartIndex = uIndex;
567         while (1)
568         {
569             if (0 == aP[uIndex])
570             {
571                 // n = next available position in this page
572                 n = aP[HASHMOD] << 1;
573                 assert(n > HASHMOD);
574                 // if off end of this page
575                 if (n + nbytes > BUCKETPAGE)
576                 {
577                     aP[HASHMOD] = 0xFF;
578                     break;
579                     // next page
580                 }
581                 else
582                 {
583                     aP[uIndex] = cast(ubyte)(n >> 1);
584                     memcpy((aP + n), entry, nbytes);
585                     aP[HASHMOD] += (nbytes + 1) >> 1;
586                     if (aP[HASHMOD] == 0)
587                         aP[HASHMOD] = 0xFF;
588                     return true;
589                 }
590             }
591             uIndex += uStep;
592             uIndex %= 0x25;
593             /*if (uIndex > 0x25)
594              uIndex -= 0x25;*/
595             if (uIndex == uStartIndex)
596                 break;
597         }
598         uPage += uPageStep;
599         if (uPage >= ndicpages)
600             uPage -= ndicpages;
601         if (uPage == uStartPage)
602             break;
603     }
604     return false;
605 }