dmd.backend.compress source code

1 /**
2  * Identifier compression for 32 bits OMF builds
3  *
4  * On 32 bits OMF builds, we have a limit of 128 characters for identifiers.
5  * When this limit is reached, this code is called to attempt to compress the identifier.
6  *
7  * Copyright:   Copyright (C) 1999-2023 by The D Language Foundation, All Rights Reserved
8  * Authors:     $(LINK2 https://www.digitalmars.com, Walter Bright)
9  * License:     $(LINK2 https://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
10  * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/backend/compress.d, backend/compress.d)
11  */
12 module dmd.backend.compress;
13 
14 import core.stdc.stdio;
15 import core.stdc.stdlib;
16 import core.stdc.string;
17 
18 nothrow:
19 @safe:
20 
21 /****************************************
22  * Find longest match of pattern[0..plen] in dict[0..dlen].
23  * Returns:
24  *      true if match found
25  */
26 
27 @trusted
28 private bool longest_match(const(char) *dict, int dlen, const(char) *pattern, int plen,
29         int *pmatchoff, int *pmatchlen)
30 {
31     int matchlen = 0;
32     int matchoff;
33 
34     char c = pattern[0];
35     for (int i = 0; i < dlen; i++)
36     {
37         if (dict[i] == c)
38         {
39             int len = dlen - i;
40             if (plen < len)
41                 len = plen;
42             int j;
43             for (j = 1; j < len; j++)
44             {
45                 if (dict[i + j] != pattern[j])
46                     break;
47             }
48             if (j >= matchlen)
49             {
50                 matchlen = j;
51                 matchoff = i;
52             }
53         }
54     }
55 
56     if (matchlen > 1)
57     {
58         *pmatchlen = matchlen;
59         *pmatchoff = matchoff;
60         return true;                    // found a match
61     }
62     return false;                       // no match
63 }
64 
65 /******************************************
66  * Compress an identifier for name mangling purposes.
67  * Format is if ASCII, then it's just the char.
68  * If high bit set, then it's a length/offset pair
69  *
70  * Params:
71  *      id = string to compress
72  *      idlen = length of id
73  *      plen = where to store length of compressed result
74  * Returns:
75  *      malloc'd compressed 0-terminated identifier
76  */
77 @trusted
78 extern(C) char *id_compress(const(char) *id, int idlen, size_t *plen)
79 {
80     int count = 0;
81     char *p = cast(char *)malloc(idlen + 1);
82     for (int i = 0; i < idlen; i++)
83     {
84         int matchoff;
85         int matchlen;
86 
87         int j = 0;
88         if (i > 1023)
89             j = i - 1023;
90 
91         if (longest_match(id + j, i - j, id + i, idlen - i, &matchoff, &matchlen))
92         {   int off;
93 
94             matchoff += j;
95             off = i - matchoff;
96             //printf("matchoff = %3d, matchlen = %2d, off = %d\n", matchoff, matchlen, off);
97             assert(off >= matchlen);
98 
99             if (off <= 8 && matchlen <= 8)
100             {
101                 p[count] = cast(char) (0xC0 | ((off - 1) << 3) | (matchlen - 1));
102                 count++;
103                 i += matchlen - 1;
104                 continue;
105             }
106             else if (matchlen > 2 && off < 1024)
107             {
108                 if (matchlen >= 1024)
109                     matchlen = 1023;    // longest representable match
110                 p[count + 0] = cast(char) (0x80 | ((matchlen >> 4) & 0x38) | ((off >> 7) & 7));
111                 p[count + 1] = cast(char) (0x80 | matchlen);
112                 p[count + 2] = cast(char) (0x80 | off);
113                 count += 3;
114                 i += matchlen - 1;
115                 continue;
116             }
117         }
118         p[count] = id[i];
119         count++;
120     }
121     p[count] = 0;
122     //printf("old size = %d, new size = %d\n", idlen, count);
123     assert(count <= idlen);
124     *plen = count;
125     return p;
126 }