1 | /* $Id: bldprog-strtab-template.cpp.h 103004 2024-01-23 22:13:47Z vboxsync $ */
|
---|
2 | /** @file
|
---|
3 | * IPRT - Build Program - String Table Generator.
|
---|
4 | */
|
---|
5 |
|
---|
6 | /*
|
---|
7 | * Copyright (C) 2006-2023 Oracle and/or its affiliates.
|
---|
8 | *
|
---|
9 | * This file is part of VirtualBox base platform packages, as
|
---|
10 | * available from https://www.virtualbox.org.
|
---|
11 | *
|
---|
12 | * This program is free software; you can redistribute it and/or
|
---|
13 | * modify it under the terms of the GNU General Public License
|
---|
14 | * as published by the Free Software Foundation, in version 3 of the
|
---|
15 | * License.
|
---|
16 | *
|
---|
17 | * This program is distributed in the hope that it will be useful, but
|
---|
18 | * WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
---|
20 | * General Public License for more details.
|
---|
21 | *
|
---|
22 | * You should have received a copy of the GNU General Public License
|
---|
23 | * along with this program; if not, see <https://www.gnu.org/licenses>.
|
---|
24 | *
|
---|
25 | * The contents of this file may alternatively be used under the terms
|
---|
26 | * of the Common Development and Distribution License Version 1.0
|
---|
27 | * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included
|
---|
28 | * in the VirtualBox distribution, in which case the provisions of the
|
---|
29 | * CDDL are applicable instead of those of the GPL.
|
---|
30 | *
|
---|
31 | * You may elect to license modified versions of this file under the
|
---|
32 | * terms and conditions of either the GPL or the CDDL or both.
|
---|
33 | *
|
---|
34 | * SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0
|
---|
35 | */
|
---|
36 |
|
---|
37 |
|
---|
38 | /*
|
---|
39 | * (Avoid include sanity checks as this is ring-3 only, C++ code.)
|
---|
40 | */
|
---|
41 | #if defined(__cplusplus) && defined(IN_RING3)
|
---|
42 |
|
---|
43 |
|
---|
44 | /*********************************************************************************************************************************
|
---|
45 | * Defined Constants And Macros *
|
---|
46 | *********************************************************************************************************************************/
|
---|
47 | /** @def BLDPROG_STRTAB_MAX_STRLEN
|
---|
48 | * The max length of strings in the table. */
|
---|
49 | #if !defined(BLDPROG_STRTAB_MAX_STRLEN) || defined(DOXYGEN_RUNNING)
|
---|
50 | # define BLDPROG_STRTAB_MAX_STRLEN 256
|
---|
51 | #endif
|
---|
52 |
|
---|
53 | /** @def BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
54 | * Enables very simple string compression.
|
---|
55 | */
|
---|
56 | #if defined(DOXYGEN_RUNNING)
|
---|
57 | # define BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
58 | #endif
|
---|
59 |
|
---|
60 | /** @def BLDPROG_STRTAB_WITH_CAMEL_WORDS
|
---|
61 | * Modifies the string compression to look for camel case words.
|
---|
62 | */
|
---|
63 | #if defined(DOXYGEN_RUNNING)
|
---|
64 | # define BLDPROG_STRTAB_WITH_CAMEL_WORDS
|
---|
65 | #endif
|
---|
66 |
|
---|
67 | /** @def BLDPROG_STRTAB_PURE_ASCII
|
---|
68 | * String compression assumes pure 7-bit ASCII and will fail on UTF-8 when this
|
---|
69 | * is defined. Otherwise, the compression code will require IPRT to link.
|
---|
70 | */
|
---|
71 | #if defined(DOXYGEN_RUNNING)
|
---|
72 | # define BLDPROG_STRTAB_PURE_ASCII
|
---|
73 | #endif
|
---|
74 |
|
---|
75 |
|
---|
76 |
|
---|
77 | /*********************************************************************************************************************************
|
---|
78 | * Header Files *
|
---|
79 | *********************************************************************************************************************************/
|
---|
80 | #include <iprt/stdarg.h>
|
---|
81 | #include <iprt/ctype.h>
|
---|
82 | #include <stdlib.h>
|
---|
83 | #include <stdio.h>
|
---|
84 | #include <string.h>
|
---|
85 |
|
---|
86 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
87 | # include <map>
|
---|
88 | # include <iprt/sanitized/string>
|
---|
89 |
|
---|
90 | # define BLDPROG_STRTAB_WITH_WORD_SEP_ALTERNATIVE
|
---|
91 | typedef struct BLDPROGWORDFREQSTATS
|
---|
92 | {
|
---|
93 | uint32_t cWithoutSep; /**< Number of occurances without a separator. */
|
---|
94 | # ifdef BLDPROG_STRTAB_WITH_WORD_SEP_ALTERNATIVE
|
---|
95 | uint32_t cWithSep; /**< Number of occurance with a separator. */
|
---|
96 | char chSep; /**< The separator. First come basis. */
|
---|
97 | # endif
|
---|
98 | } BLDPROGWORDFREQSTATS;
|
---|
99 |
|
---|
100 | typedef std::map<std::string, BLDPROGWORDFREQSTATS> BLDPROGWORDFREQMAP;
|
---|
101 |
|
---|
102 | #endif
|
---|
103 |
|
---|
104 | #include "../../src/VBox/Runtime/include/internal/strhash.h" /** @todo make this one public */
|
---|
105 |
|
---|
106 |
|
---|
107 | /*********************************************************************************************************************************
|
---|
108 | * Structures and Typedefs *
|
---|
109 | *********************************************************************************************************************************/
|
---|
110 | /**
|
---|
111 | * Build table string.
|
---|
112 | */
|
---|
113 | typedef struct BLDPROGSTRING
|
---|
114 | {
|
---|
115 | /** The string.
|
---|
116 | * @note This may be modified or replaced (allocated from heap) when
|
---|
117 | * compressing the string table. */
|
---|
118 | char *pszString;
|
---|
119 | /** The string hash value. */
|
---|
120 | uint32_t uHash;
|
---|
121 | /** The strint table offset. */
|
---|
122 | uint32_t offStrTab;
|
---|
123 | /** The string length. */
|
---|
124 | size_t cchString;
|
---|
125 | /** Pointer to the next string reference (same string table entry). */
|
---|
126 | struct BLDPROGSTRING *pNextRef;
|
---|
127 | /** Pointer to the next string with the same hash value (collision). */
|
---|
128 | struct BLDPROGSTRING *pNextCollision;
|
---|
129 |
|
---|
130 | } BLDPROGSTRING;
|
---|
131 | /** Pointer to a string table string. */
|
---|
132 | typedef BLDPROGSTRING *PBLDPROGSTRING;
|
---|
133 |
|
---|
134 |
|
---|
135 | /** String table data. */
|
---|
136 | typedef struct BLDPROGSTRTAB
|
---|
137 | {
|
---|
138 | /** The size of g_papStrHash. */
|
---|
139 | size_t cStrHash;
|
---|
140 | /** String hash table. */
|
---|
141 | PBLDPROGSTRING *papStrHash;
|
---|
142 | /** Duplicate strings found by AddString. */
|
---|
143 | size_t cDuplicateStrings;
|
---|
144 | /** Total length of the unique strings (no terminators). */
|
---|
145 | size_t cchUniqueStrings;
|
---|
146 | /** Number of unique strings after AddString. */
|
---|
147 | size_t cUniqueStrings;
|
---|
148 | /** Number of collisions. */
|
---|
149 | size_t cCollisions;
|
---|
150 |
|
---|
151 | /** Number of entries in apSortedStrings. */
|
---|
152 | size_t cSortedStrings;
|
---|
153 | /** The sorted string table. */
|
---|
154 | PBLDPROGSTRING *papSortedStrings;
|
---|
155 |
|
---|
156 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
157 | /** The 256 words we've picked to be indexed by reference. */
|
---|
158 | BLDPROGSTRING aCompDict[256];
|
---|
159 | /** The frequency of the 256 dictionary entries. */
|
---|
160 | size_t auCompDictFreq[256];
|
---|
161 | /** Incoming strings pending compression. */
|
---|
162 | PBLDPROGSTRING *papPendingStrings;
|
---|
163 | /** Current number of entries in papStrPending. */
|
---|
164 | size_t cPendingStrings;
|
---|
165 | /** The allocated size of papPendingStrings. */
|
---|
166 | size_t cMaxPendingStrings;
|
---|
167 | /** Work frequency map.
|
---|
168 | * @todo rewrite in plain C. */
|
---|
169 | BLDPROGWORDFREQMAP Frequencies;
|
---|
170 | /** Map of characters used by input strings. */
|
---|
171 | uint64_t bmUsedChars[256/64];
|
---|
172 | #endif
|
---|
173 |
|
---|
174 | /** The string table. */
|
---|
175 | char *pachStrTab;
|
---|
176 | /** The actual string table size. */
|
---|
177 | size_t cchStrTab;
|
---|
178 | } BLDPROGSTRTAB;
|
---|
179 | typedef BLDPROGSTRTAB *PBLDPROGSTRTAB;
|
---|
180 |
|
---|
181 | #if RT_CLANG_PREREQ(4, 0) || RT_GNUC_PREREQ(4, 6)
|
---|
182 | # pragma GCC diagnostic push
|
---|
183 | # pragma GCC diagnostic ignored "-Wunused-function"
|
---|
184 | #endif
|
---|
185 |
|
---|
186 |
|
---|
187 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
188 |
|
---|
189 | /**
|
---|
190 | * Same as ASMBitTest.
|
---|
191 | *
|
---|
192 | * We cannot safely use ASMBitTest here because it must be inline, as this code
|
---|
193 | * is used to build RuntimeBldProg. */
|
---|
194 | DECLINLINE(bool) BldProgBitIsSet(uint64_t const *pbmBitmap, size_t iBit)
|
---|
195 | {
|
---|
196 | return RT_BOOL(pbmBitmap[iBit / 64] & RT_BIT_64(iBit % 64));
|
---|
197 | }
|
---|
198 |
|
---|
199 |
|
---|
200 | /**
|
---|
201 | * Same as ASMBitSet.
|
---|
202 | *
|
---|
203 | * We cannot safely use ASMBitSet here because it must be inline, as this code
|
---|
204 | * is used to build RuntimeBldProg.
|
---|
205 | */
|
---|
206 | DECLINLINE(void) BldProgBitSet(uint64_t *pbmBitmap, size_t iBit)
|
---|
207 | {
|
---|
208 | pbmBitmap[iBit / 64] |= RT_BIT_64(iBit % 64);
|
---|
209 | }
|
---|
210 |
|
---|
211 | #endif
|
---|
212 |
|
---|
213 |
|
---|
214 | /**
|
---|
215 | * Initializes the strint table compiler.
|
---|
216 | *
|
---|
217 | * @returns success indicator (out of memory if false).
|
---|
218 | * @param pThis The strint table compiler instance.
|
---|
219 | * @param cMaxStrings The max number of strings we'll be adding.
|
---|
220 | */
|
---|
221 | static bool BldProgStrTab_Init(PBLDPROGSTRTAB pThis, size_t cMaxStrings)
|
---|
222 | {
|
---|
223 | pThis->cStrHash = 0;
|
---|
224 | pThis->papStrHash = NULL;
|
---|
225 | pThis->cDuplicateStrings = 0;
|
---|
226 | pThis->cchUniqueStrings = 0;
|
---|
227 | pThis->cUniqueStrings = 0;
|
---|
228 | pThis->cCollisions = 0;
|
---|
229 | pThis->cSortedStrings = 0;
|
---|
230 | pThis->papSortedStrings = NULL;
|
---|
231 | pThis->pachStrTab = NULL;
|
---|
232 | pThis->cchStrTab = 0;
|
---|
233 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
234 | memset(pThis->aCompDict, 0, sizeof(pThis->aCompDict));
|
---|
235 | pThis->papPendingStrings = NULL;
|
---|
236 | pThis->cPendingStrings = 0;
|
---|
237 | pThis->cMaxPendingStrings = cMaxStrings;
|
---|
238 | memset(pThis->bmUsedChars, 0, sizeof(pThis->bmUsedChars));
|
---|
239 | BldProgBitSet(pThis->bmUsedChars, 0); /* Some parts of the code still thinks zero is a terminator, so don't use it for now. */
|
---|
240 | # ifndef BLDPROG_STRTAB_PURE_ASCII
|
---|
241 | BldProgBitSet(pThis->bmUsedChars, 0xff); /* Reserve escape byte for codepoints above 127. */
|
---|
242 | # endif
|
---|
243 | #endif
|
---|
244 |
|
---|
245 | /*
|
---|
246 | * Allocate a hash table double the size of all strings (to avoid too
|
---|
247 | * many collisions). Add all strings to it, finding duplicates in the
|
---|
248 | * process.
|
---|
249 | */
|
---|
250 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
251 | cMaxStrings += RT_ELEMENTS(pThis->aCompDict);
|
---|
252 | #endif
|
---|
253 | cMaxStrings *= 2;
|
---|
254 | pThis->papStrHash = (PBLDPROGSTRING *)calloc(sizeof(pThis->papStrHash[0]), cMaxStrings);
|
---|
255 | if (pThis->papStrHash)
|
---|
256 | {
|
---|
257 | pThis->cStrHash = cMaxStrings;
|
---|
258 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
259 | pThis->papPendingStrings = (PBLDPROGSTRING *)calloc(sizeof(pThis->papPendingStrings[0]), pThis->cMaxPendingStrings);
|
---|
260 | if (pThis->papPendingStrings)
|
---|
261 | #endif
|
---|
262 | return true;
|
---|
263 |
|
---|
264 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
265 | free(pThis->papStrHash);
|
---|
266 | pThis->papStrHash = NULL;
|
---|
267 | #endif
|
---|
268 | }
|
---|
269 | return false;
|
---|
270 | }
|
---|
271 |
|
---|
272 |
|
---|
273 | #if 0 /* unused */
|
---|
274 | static void BldProgStrTab_Delete(PBLDPROGSTRTAB pThis)
|
---|
275 | {
|
---|
276 | free(pThis->papStrHash);
|
---|
277 | free(pThis->papSortedStrings);
|
---|
278 | free(pThis->pachStrTab);
|
---|
279 | # ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
280 | free(pThis->papPendingStrings);
|
---|
281 | # endif
|
---|
282 | memset(pThis, 0, sizeof(*pThis));
|
---|
283 | }
|
---|
284 | #endif
|
---|
285 |
|
---|
286 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
287 |
|
---|
288 | DECLINLINE(size_t) bldProgStrTab_compressorFindNextWord(const char *pszSrc, char ch, const char **ppszSrc)
|
---|
289 | {
|
---|
290 | /*
|
---|
291 | * Skip leading word separators.
|
---|
292 | */
|
---|
293 | # ifdef BLDPROG_STRTAB_WITH_CAMEL_WORDS
|
---|
294 | while ( ch == ' '
|
---|
295 | || ch == '-'
|
---|
296 | || ch == '+'
|
---|
297 | || ch == '_')
|
---|
298 | # else
|
---|
299 | while (ch == ' ')
|
---|
300 | # endif
|
---|
301 | ch = *++pszSrc;
|
---|
302 | if (ch)
|
---|
303 | {
|
---|
304 | /*
|
---|
305 | * Find end of word.
|
---|
306 | */
|
---|
307 | size_t cchWord = 1;
|
---|
308 | # ifdef BLDPROG_STRTAB_WITH_CAMEL_WORDS
|
---|
309 | char chPrev = ch;
|
---|
310 | while ( (ch = pszSrc[cchWord]) != ' '
|
---|
311 | && ch != '\0'
|
---|
312 | && ch != '-'
|
---|
313 | && ch != '+'
|
---|
314 | && ch != '_'
|
---|
315 | && ( ch == chPrev
|
---|
316 | || !RT_C_IS_UPPER(ch)
|
---|
317 | || RT_C_IS_UPPER(chPrev)) )
|
---|
318 | {
|
---|
319 | chPrev = ch;
|
---|
320 | cchWord++;
|
---|
321 | }
|
---|
322 | # else
|
---|
323 | while ((ch = pszSrc[cchWord]) != ' ' && ch != '\0')
|
---|
324 | cchWord++;
|
---|
325 | # endif
|
---|
326 | *ppszSrc = pszSrc;
|
---|
327 | return cchWord;
|
---|
328 | }
|
---|
329 |
|
---|
330 | *ppszSrc = pszSrc;
|
---|
331 | return 0;
|
---|
332 | }
|
---|
333 |
|
---|
334 |
|
---|
335 | /**
|
---|
336 | * Analyzes a string.
|
---|
337 | *
|
---|
338 | * @param pThis The strint table compiler instance.
|
---|
339 | * @param pStr The string to analyze.
|
---|
340 | */
|
---|
341 | static void bldProgStrTab_compressorAnalyzeString(PBLDPROGSTRTAB pThis, PBLDPROGSTRING pStr)
|
---|
342 | {
|
---|
343 | /*
|
---|
344 | * Mark all the string characters as used.
|
---|
345 | */
|
---|
346 | const char *psz = pStr->pszString;
|
---|
347 | char ch;
|
---|
348 | while ((ch = *psz++) != '\0')
|
---|
349 | BldProgBitSet(pThis->bmUsedChars, (uint8_t)ch);
|
---|
350 |
|
---|
351 | /*
|
---|
352 | * For now we just consider words.
|
---|
353 | */
|
---|
354 | psz = pStr->pszString;
|
---|
355 | while ((ch = *psz) != '\0')
|
---|
356 | {
|
---|
357 | size_t cchWord = bldProgStrTab_compressorFindNextWord(psz, ch, &psz);
|
---|
358 | if (cchWord > 1)
|
---|
359 | {
|
---|
360 | std::string strWord(psz, cchWord);
|
---|
361 | BLDPROGWORDFREQMAP::iterator it = pThis->Frequencies.find(strWord);
|
---|
362 | if (it != pThis->Frequencies.end())
|
---|
363 | {
|
---|
364 | # ifdef BLDPROG_STRTAB_WITH_WORD_SEP_ALTERNATIVE
|
---|
365 | char const chSep = psz[cchWord];
|
---|
366 | if (chSep != '\0' && (it->second.chSep == chSep || it->second.chSep == '\0'))
|
---|
367 | {
|
---|
368 | it->second.chSep = chSep;
|
---|
369 | it->second.cWithSep++;
|
---|
370 | }
|
---|
371 | else
|
---|
372 | # endif
|
---|
373 | it->second.cWithoutSep++;
|
---|
374 | }
|
---|
375 | else
|
---|
376 | {
|
---|
377 | # ifdef BLDPROG_STRTAB_WITH_WORD_SEP_ALTERNATIVE
|
---|
378 | char const chSep = psz[cchWord];
|
---|
379 | if (chSep != '\0')
|
---|
380 | {
|
---|
381 | BLDPROGWORDFREQSTATS const NewWord = { 0, 0, chSep };
|
---|
382 | pThis->Frequencies[strWord] = NewWord;
|
---|
383 | }
|
---|
384 | else
|
---|
385 | {
|
---|
386 | static BLDPROGWORDFREQSTATS const s_NewWord = { 0, 0, 0 };
|
---|
387 | pThis->Frequencies[strWord] = s_NewWord;
|
---|
388 | }
|
---|
389 | # else
|
---|
390 | pThis->Frequencies[strWord].cWithoutSep = 0;
|
---|
391 | # endif
|
---|
392 | }
|
---|
393 |
|
---|
394 | # if 0 /** @todo need better accounting for overlapping alternatives before this can be enabled. */
|
---|
395 | /* Two words - immediate yields calc may lie when this enabled and we may pick the wrong words. */
|
---|
396 | if (ch == ' ')
|
---|
397 | {
|
---|
398 | ch = psz[++cchWord];
|
---|
399 | if (ch != ' ' && ch != '\0')
|
---|
400 | {
|
---|
401 | size_t const cchSaved = cchWord;
|
---|
402 |
|
---|
403 | do
|
---|
404 | cchWord++;
|
---|
405 | while ((ch = psz[cchWord]) != ' ' && ch != '\0');
|
---|
406 |
|
---|
407 | strWord = std::string(psz, cchWord);
|
---|
408 | BLDPROGWORDFREQMAP::iterator it = pThis->Frequencies.find(strWord);
|
---|
409 | if (it != pThis->Frequencies.end())
|
---|
410 | it->second += cchWord - 1;
|
---|
411 | else
|
---|
412 | pThis->Frequencies[strWord] = 0;
|
---|
413 |
|
---|
414 | cchWord = cchSaved;
|
---|
415 | }
|
---|
416 | }
|
---|
417 | # endif
|
---|
418 | }
|
---|
419 | else if (!cchWord)
|
---|
420 | break;
|
---|
421 |
|
---|
422 | /* Advance. */
|
---|
423 | psz += cchWord;
|
---|
424 | }
|
---|
425 | pStr->cchString = psz - pStr->pszString;
|
---|
426 | if (pStr->cchString > BLDPROG_STRTAB_MAX_STRLEN)
|
---|
427 | {
|
---|
428 | fprintf(stderr, "error: String to long (%u)\n", (unsigned)pStr->cchString);
|
---|
429 | abort();
|
---|
430 | }
|
---|
431 | }
|
---|
432 |
|
---|
433 | #endif /* BLDPROG_STRTAB_WITH_COMPRESSION */
|
---|
434 |
|
---|
435 | /**
|
---|
436 | * Adds a string to the hash table.
|
---|
437 | * @param pThis The strint table compiler instance.
|
---|
438 | * @param pStr The string.
|
---|
439 | */
|
---|
440 | static void bldProgStrTab_AddStringToHashTab(PBLDPROGSTRTAB pThis, PBLDPROGSTRING pStr)
|
---|
441 | {
|
---|
442 | pStr->pNextRef = NULL;
|
---|
443 | pStr->pNextCollision = NULL;
|
---|
444 | pStr->offStrTab = 0;
|
---|
445 | pStr->uHash = sdbm(pStr->pszString, &pStr->cchString);
|
---|
446 | if (pStr->cchString > BLDPROG_STRTAB_MAX_STRLEN)
|
---|
447 | {
|
---|
448 | fprintf(stderr, "error: String to long (%u)\n", (unsigned)pStr->cchString);
|
---|
449 | exit(RTEXITCODE_FAILURE);
|
---|
450 | }
|
---|
451 |
|
---|
452 | size_t idxHash = pStr->uHash % pThis->cStrHash;
|
---|
453 | PBLDPROGSTRING pCur = pThis->papStrHash[idxHash];
|
---|
454 | if (!pCur)
|
---|
455 | pThis->papStrHash[idxHash] = pStr;
|
---|
456 | else
|
---|
457 | {
|
---|
458 | /* Look for matching string. */
|
---|
459 | do
|
---|
460 | {
|
---|
461 | if ( pCur->uHash == pStr->uHash
|
---|
462 | && pCur->cchString == pStr->cchString
|
---|
463 | && memcmp(pCur->pszString, pStr->pszString, pStr->cchString) == 0)
|
---|
464 | {
|
---|
465 | pStr->pNextRef = pCur->pNextRef;
|
---|
466 | pCur->pNextRef = pStr;
|
---|
467 | pThis->cDuplicateStrings++;
|
---|
468 | return;
|
---|
469 | }
|
---|
470 | pCur = pCur->pNextCollision;
|
---|
471 | } while (pCur != NULL);
|
---|
472 |
|
---|
473 | /* No matching string, insert. */
|
---|
474 | pThis->cCollisions++;
|
---|
475 | pStr->pNextCollision = pThis->papStrHash[idxHash];
|
---|
476 | pThis->papStrHash[idxHash] = pStr;
|
---|
477 | }
|
---|
478 |
|
---|
479 | pThis->cUniqueStrings++;
|
---|
480 | pThis->cchUniqueStrings += pStr->cchString;
|
---|
481 | }
|
---|
482 |
|
---|
483 |
|
---|
484 | /**
|
---|
485 | * Adds a string to the string table.
|
---|
486 | *
|
---|
487 | * @param pThis The strint table compiler instance.
|
---|
488 | * @param pStr The string.
|
---|
489 | */
|
---|
490 | static void BldProgStrTab_AddString(PBLDPROGSTRTAB pThis, PBLDPROGSTRING pStr)
|
---|
491 | {
|
---|
492 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
493 | bldProgStrTab_compressorAnalyzeString(pThis, pStr);
|
---|
494 | if (pThis->cPendingStrings < pThis->cMaxPendingStrings)
|
---|
495 | pThis->papPendingStrings[pThis->cPendingStrings++] = pStr;
|
---|
496 | else
|
---|
497 | abort();
|
---|
498 | #else
|
---|
499 | bldProgStrTab_AddStringToHashTab(pThis, pStr);
|
---|
500 | #endif
|
---|
501 | }
|
---|
502 |
|
---|
503 |
|
---|
504 | /**
|
---|
505 | * Adds a string to the string table.
|
---|
506 | *
|
---|
507 | * @param pThis The strint table compiler instance.
|
---|
508 | * @param pStr The string entry (uninitialized).
|
---|
509 | * @param psz The string, will be duplicated if compression is enabled.
|
---|
510 | */
|
---|
511 | DECLINLINE(void) BldProgStrTab_AddStringDup(PBLDPROGSTRTAB pThis, PBLDPROGSTRING pStr, const char *psz)
|
---|
512 | {
|
---|
513 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
514 | pStr->pszString = strdup(psz);
|
---|
515 | if (!pStr->pszString)
|
---|
516 | abort();
|
---|
517 | #else
|
---|
518 | pStr->pszString = (char *)psz;
|
---|
519 | #endif
|
---|
520 | BldProgStrTab_AddString(pThis, pStr);
|
---|
521 | }
|
---|
522 |
|
---|
523 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
524 |
|
---|
525 | /**
|
---|
526 | * Copies @a cchSrc chars from @a pchSrc to @a pszDst, escaping special
|
---|
527 | * sequences.
|
---|
528 | *
|
---|
529 | * @returns New @a pszDst position, NULL if invalid source encoding.
|
---|
530 | * @param pszDst The destination buffer.
|
---|
531 | * @param pszSrc The source buffer.
|
---|
532 | * @param cchSrc How much to copy.
|
---|
533 | */
|
---|
534 | static char *bldProgStrTab_compressorCopyAndEscape(char *pszDst, const char *pszSrc, size_t cchSrc)
|
---|
535 | {
|
---|
536 | while (cchSrc-- > 0)
|
---|
537 | {
|
---|
538 | char ch = *pszSrc;
|
---|
539 | if (!((unsigned char)ch & 0x80))
|
---|
540 | {
|
---|
541 | *pszDst++ = ch;
|
---|
542 | pszSrc++;
|
---|
543 | }
|
---|
544 | else
|
---|
545 | {
|
---|
546 | # ifdef BLDPROG_STRTAB_PURE_ASCII
|
---|
547 | fprintf(stderr, "error: unexpected char value %#x\n", ch);
|
---|
548 | return NULL;
|
---|
549 | # else
|
---|
550 | RTUNICP uc;
|
---|
551 | int rc = RTStrGetCpEx(&pszSrc, &uc);
|
---|
552 | if (RT_SUCCESS(rc))
|
---|
553 | {
|
---|
554 | *pszDst++ = (unsigned char)0xff; /* escape single code point. */
|
---|
555 | pszDst = RTStrPutCp(pszDst, uc);
|
---|
556 | }
|
---|
557 | else
|
---|
558 | {
|
---|
559 | fprintf(stderr, "Error: RTStrGetCpEx failed with rc=%d\n", rc);
|
---|
560 | return NULL;
|
---|
561 | }
|
---|
562 | # endif
|
---|
563 | }
|
---|
564 | }
|
---|
565 | return pszDst;
|
---|
566 | }
|
---|
567 |
|
---|
568 |
|
---|
569 | /**
|
---|
570 | * Replaces the dictionary words and escapes non-ascii chars in a string.
|
---|
571 | *
|
---|
572 | * @param pThis The strint table compiler instance.
|
---|
573 | * @param pString The string to fixup.
|
---|
574 | */
|
---|
575 | static bool bldProgStrTab_compressorFixupString(PBLDPROGSTRTAB pThis, PBLDPROGSTRING pStr)
|
---|
576 | {
|
---|
577 | char szNew[BLDPROG_STRTAB_MAX_STRLEN * 2];
|
---|
578 | char *pszDst = szNew;
|
---|
579 | const char *pszSrc = pStr->pszString;
|
---|
580 | const char *pszSrcEnd = pszSrc + pStr->cchString;
|
---|
581 |
|
---|
582 | char ch;
|
---|
583 | while ((ch = *pszSrc) != '\0')
|
---|
584 | {
|
---|
585 | const char * const pszSrcUncompressed = pszSrc;
|
---|
586 | size_t cchWord = bldProgStrTab_compressorFindNextWord(pszSrc, ch, &pszSrc);
|
---|
587 | size_t cchSrcUncompressed = pszSrc - pszSrcUncompressed;
|
---|
588 | if (cchSrcUncompressed > 0)
|
---|
589 | {
|
---|
590 | pszDst = bldProgStrTab_compressorCopyAndEscape(pszDst, pszSrcUncompressed, cchSrcUncompressed);
|
---|
591 | if (!pszDst)
|
---|
592 | return false;
|
---|
593 | }
|
---|
594 | if (!cchWord)
|
---|
595 | break;
|
---|
596 |
|
---|
597 | /* Check for g_aWord matches. */
|
---|
598 | if (cchWord > 1)
|
---|
599 | {
|
---|
600 | size_t cchMax = pszSrcEnd - pszSrc;
|
---|
601 | for (unsigned i = 0; i < RT_ELEMENTS(pThis->aCompDict); i++)
|
---|
602 | {
|
---|
603 | size_t cchLen = pThis->aCompDict[i].cchString;
|
---|
604 | if ( cchLen >= cchWord
|
---|
605 | && cchLen <= cchMax
|
---|
606 | && memcmp(pThis->aCompDict[i].pszString, pszSrc, cchLen) == 0)
|
---|
607 | {
|
---|
608 | *pszDst++ = (unsigned char)i;
|
---|
609 | pszSrc += cchLen;
|
---|
610 | cchWord = 0;
|
---|
611 | break;
|
---|
612 | }
|
---|
613 | }
|
---|
614 | }
|
---|
615 |
|
---|
616 | if (cchWord > 0)
|
---|
617 | {
|
---|
618 | /* Copy the current word. */
|
---|
619 | pszDst = bldProgStrTab_compressorCopyAndEscape(pszDst, pszSrc, cchWord);
|
---|
620 | if (!pszDst)
|
---|
621 | return false;
|
---|
622 | pszSrc += cchWord;
|
---|
623 | }
|
---|
624 | }
|
---|
625 |
|
---|
626 | /* Just terminate it now. */
|
---|
627 | *pszDst = '\0';
|
---|
628 |
|
---|
629 | /*
|
---|
630 | * Update the string.
|
---|
631 | */
|
---|
632 | size_t cchNew = pszDst - &szNew[0];
|
---|
633 | if (cchNew > pStr->cchString)
|
---|
634 | {
|
---|
635 | pStr->pszString = (char *)malloc(cchNew + 1);
|
---|
636 | if (!pStr->pszString)
|
---|
637 | {
|
---|
638 | fprintf(stderr, "Out of memory!\n");
|
---|
639 | return false;
|
---|
640 | }
|
---|
641 | }
|
---|
642 | memcpy(pStr->pszString, szNew, cchNew + 1);
|
---|
643 | pStr->cchString = cchNew;
|
---|
644 |
|
---|
645 | return true;
|
---|
646 | }
|
---|
647 |
|
---|
648 |
|
---|
649 | /**
|
---|
650 | * Entry in SortedDictionary.
|
---|
651 | *
|
---|
652 | * Uses variable length string member, so not class and allocated via malloc.
|
---|
653 | */
|
---|
654 | struct SortedDictionaryEntry
|
---|
655 | {
|
---|
656 | size_t m_cchGain;
|
---|
657 | size_t m_cchString;
|
---|
658 | RT_FLEXIBLE_ARRAY_EXTENSION
|
---|
659 | char m_szString[RT_FLEXIBLE_ARRAY];
|
---|
660 |
|
---|
661 | /** Allocates and initializes a new entry. */
|
---|
662 | static SortedDictionaryEntry *allocate(const char *a_pch, size_t a_cch, size_t a_cchGain, char a_chSep)
|
---|
663 | {
|
---|
664 | size_t cbString = a_cch + !!a_chSep + 1;
|
---|
665 | SortedDictionaryEntry *pNew = (SortedDictionaryEntry *)malloc(RT_UOFFSETOF(SortedDictionaryEntry, m_szString) + cbString);
|
---|
666 | if (pNew)
|
---|
667 | {
|
---|
668 | pNew->m_cchGain = a_cchGain;
|
---|
669 | memcpy(pNew->m_szString, a_pch, a_cch);
|
---|
670 | if (a_chSep)
|
---|
671 | pNew->m_szString[a_cch++] = a_chSep;
|
---|
672 | pNew->m_szString[a_cch] = '\0';
|
---|
673 | pNew->m_cchString = a_cch;
|
---|
674 | }
|
---|
675 | return pNew;
|
---|
676 | }
|
---|
677 |
|
---|
678 |
|
---|
679 | /** Compares this dictionary entry with an incoming one.
|
---|
680 | * @retval -1 if this entry is of less worth than the new one.
|
---|
681 | * @retval 0 if this entry is of equal worth to the new one.
|
---|
682 | * @retval +1 if this entry is of more worth than the new one.
|
---|
683 | */
|
---|
684 | int compare(size_t a_cchGain, size_t a_cchString)
|
---|
685 | {
|
---|
686 | /* Higher gain is preferred of course: */
|
---|
687 | if (m_cchGain < a_cchGain)
|
---|
688 | return -1;
|
---|
689 | if (m_cchGain > a_cchGain)
|
---|
690 | return 1;
|
---|
691 |
|
---|
692 | /* Gain is the same. Prefer the shorter string, as it will result in a shorter string table: */
|
---|
693 | if (m_cchString > a_cchString)
|
---|
694 | return -1;
|
---|
695 | if (m_cchString < a_cchString)
|
---|
696 | return 1;
|
---|
697 | return 0;
|
---|
698 | }
|
---|
699 | };
|
---|
700 |
|
---|
701 |
|
---|
702 | /**
|
---|
703 | * Insertion sort dictionary that keeps the 256 best words.
|
---|
704 | *
|
---|
705 | * Used by bldProgStrTab_compressorDoStringCompression to pick the dictionary
|
---|
706 | * words.
|
---|
707 | */
|
---|
708 | class SortedDictionary
|
---|
709 | {
|
---|
710 | public:
|
---|
711 | size_t m_cEntries;
|
---|
712 | SortedDictionaryEntry *m_apEntries[256];
|
---|
713 |
|
---|
714 | SortedDictionary()
|
---|
715 | : m_cEntries(0)
|
---|
716 | {
|
---|
717 | for (size_t i = 0; i < RT_ELEMENTS(m_apEntries); i++)
|
---|
718 | m_apEntries[i] = NULL;
|
---|
719 | }
|
---|
720 |
|
---|
721 | ~SortedDictionary()
|
---|
722 | {
|
---|
723 | while (m_cEntries > 0)
|
---|
724 | {
|
---|
725 | free(m_apEntries[--m_cEntries]);
|
---|
726 | m_apEntries[m_cEntries] = NULL;
|
---|
727 | }
|
---|
728 | }
|
---|
729 |
|
---|
730 |
|
---|
731 | /**
|
---|
732 | * Inserts a new entry, if it's worth it.
|
---|
733 | * @returns true on succes, false if out of memory.
|
---|
734 | */
|
---|
735 | bool insert(const char *a_pchString, size_t a_cchStringBase, size_t a_cchGain, char a_chSep = 0)
|
---|
736 | {
|
---|
737 | size_t const cchString = a_cchStringBase + (a_chSep + 1);
|
---|
738 |
|
---|
739 | /*
|
---|
740 | * Drop the insert if the symbol table is full and the insert is less worth the last entry:
|
---|
741 | */
|
---|
742 | if ( m_cEntries >= RT_ELEMENTS(m_apEntries)
|
---|
743 | && m_apEntries[RT_ELEMENTS(m_apEntries) - 1]->compare(a_cchGain, cchString) >= 0)
|
---|
744 | return true;
|
---|
745 |
|
---|
746 | /*
|
---|
747 | * Create a new entry to insert.
|
---|
748 | */
|
---|
749 | SortedDictionaryEntry *pNewEntry = SortedDictionaryEntry::allocate(a_pchString, a_cchStringBase, a_cchGain, a_chSep);
|
---|
750 | if (!pNewEntry)
|
---|
751 | return false;
|
---|
752 |
|
---|
753 | /*
|
---|
754 | * Find the insert point.
|
---|
755 | */
|
---|
756 | if (m_cEntries == 0)
|
---|
757 | {
|
---|
758 | m_apEntries[0] = pNewEntry;
|
---|
759 | m_cEntries = 1;
|
---|
760 | }
|
---|
761 | else
|
---|
762 | {
|
---|
763 | /* If table is full, drop the last entry before we start (already made
|
---|
764 | sure the incoming entry is preferable to the one were dropping): */
|
---|
765 | if (m_cEntries >= RT_ELEMENTS(m_apEntries))
|
---|
766 | {
|
---|
767 | free(m_apEntries[RT_ELEMENTS(m_apEntries) - 1]);
|
---|
768 | m_apEntries[RT_ELEMENTS(m_apEntries) - 1] = NULL;
|
---|
769 | m_cEntries = RT_ELEMENTS(m_apEntries) - 1;
|
---|
770 | }
|
---|
771 |
|
---|
772 | /* Find where to insert the new entry: */
|
---|
773 | /** @todo use binary search. */
|
---|
774 | size_t i = m_cEntries;
|
---|
775 | while (i > 0 && m_apEntries[i - 1]->compare(a_cchGain, cchString) < 0)
|
---|
776 | i--;
|
---|
777 |
|
---|
778 | /* Shift entries to make room and insert the new entry. */
|
---|
779 | if (i < m_cEntries)
|
---|
780 | memmove(&m_apEntries[i + 1], &m_apEntries[i], (m_cEntries - i) * sizeof(m_apEntries[0]));
|
---|
781 | m_apEntries[i] = pNewEntry;
|
---|
782 | m_cEntries++;
|
---|
783 | }
|
---|
784 | return true;
|
---|
785 | }
|
---|
786 | };
|
---|
787 |
|
---|
788 |
|
---|
789 | /**
|
---|
790 | * Compresses the vendor and product strings.
|
---|
791 | *
|
---|
792 | * This is very very simple (a lot less work than the string table for
|
---|
793 | * instance).
|
---|
794 | */
|
---|
795 | static bool bldProgStrTab_compressorDoStringCompression(PBLDPROGSTRTAB pThis, bool fVerbose)
|
---|
796 | {
|
---|
797 | /*
|
---|
798 | * Sort the frequency analyzis result and pick the top entries for any
|
---|
799 | * available dictionary slots.
|
---|
800 | */
|
---|
801 | SortedDictionary SortedDict;
|
---|
802 | for (BLDPROGWORDFREQMAP::iterator it = pThis->Frequencies.begin(); it != pThis->Frequencies.end(); ++it)
|
---|
803 | {
|
---|
804 | bool fInsert;
|
---|
805 | size_t const cchString = it->first.length();
|
---|
806 | # ifndef BLDPROG_STRTAB_WITH_WORD_SEP_ALTERNATIVE
|
---|
807 | size_t const cchGainWithout = it->second.cWithoutSep * cchString;
|
---|
808 | # else
|
---|
809 | size_t const cchGainWithout = (it->second.cWithoutSep + it->second.cWithSep) * cchString;
|
---|
810 | size_t const cchGainWith = it->second.cWithSep * (cchString + 1);
|
---|
811 | if (cchGainWith > cchGainWithout)
|
---|
812 | fInsert = SortedDict.insert(it->first.c_str(), cchString, cchGainWith, it->second.chSep);
|
---|
813 | else
|
---|
814 | # endif
|
---|
815 | fInsert = SortedDict.insert(it->first.c_str(), cchString, cchGainWithout);
|
---|
816 | if (!fInsert)
|
---|
817 | return false;
|
---|
818 | }
|
---|
819 |
|
---|
820 | size_t cb = 0;
|
---|
821 | size_t cWords = 0;
|
---|
822 | size_t iDict = 0;
|
---|
823 | # ifdef BLDPROG_STRTAB_PURE_ASCII
|
---|
824 | for (size_t i = 0; i < RT_ELEMENTS(pThis->aCompDict); i++)
|
---|
825 | # else
|
---|
826 | for (size_t i = 0; i < RT_ELEMENTS(pThis->aCompDict) - 1; i++)
|
---|
827 | # endif
|
---|
828 | {
|
---|
829 | char szTmp[2] = { (char)i, '\0' };
|
---|
830 | const char *psz = szTmp;
|
---|
831 | if ( BldProgBitIsSet(pThis->bmUsedChars, i)
|
---|
832 | || iDict >= SortedDict.m_cEntries)
|
---|
833 | {
|
---|
834 | /* character entry */
|
---|
835 | pThis->auCompDictFreq[i] = 0;
|
---|
836 | pThis->aCompDict[i].cchString = 1;
|
---|
837 | }
|
---|
838 | else
|
---|
839 | {
|
---|
840 | /* word entry */
|
---|
841 | cb += SortedDict.m_apEntries[iDict]->m_cchGain;
|
---|
842 | pThis->auCompDictFreq[i] = SortedDict.m_apEntries[iDict]->m_cchGain;
|
---|
843 | pThis->aCompDict[i].cchString = SortedDict.m_apEntries[iDict]->m_cchString;
|
---|
844 | psz = SortedDict.m_apEntries[iDict]->m_szString;
|
---|
845 | cWords++;
|
---|
846 | iDict++;
|
---|
847 | }
|
---|
848 | pThis->aCompDict[i].pszString = (char *)malloc(pThis->aCompDict[i].cchString + 1);
|
---|
849 | if (pThis->aCompDict[i].pszString)
|
---|
850 | memcpy(pThis->aCompDict[i].pszString, psz, pThis->aCompDict[i].cchString + 1);
|
---|
851 | else
|
---|
852 | return false;
|
---|
853 | }
|
---|
854 |
|
---|
855 | if (fVerbose)
|
---|
856 | printf("debug: Estimated string compression saving: %u bytes\n"
|
---|
857 | "debug: %u words, %u characters\n"
|
---|
858 | , (unsigned)cb, (unsigned)cWords, (unsigned)(RT_ELEMENTS(pThis->aCompDict) - cWords));
|
---|
859 |
|
---|
860 | /*
|
---|
861 | * Rework the strings.
|
---|
862 | */
|
---|
863 | size_t cchOld = 0;
|
---|
864 | size_t cchOldMax = 0;
|
---|
865 | size_t cchOldMin = BLDPROG_STRTAB_MAX_STRLEN;
|
---|
866 | size_t cchNew = 0;
|
---|
867 | size_t cchNewMax = 0;
|
---|
868 | size_t cchNewMin = BLDPROG_STRTAB_MAX_STRLEN;
|
---|
869 | size_t i = pThis->cPendingStrings;
|
---|
870 | while (i-- > 0)
|
---|
871 | {
|
---|
872 | PBLDPROGSTRING pCurStr = pThis->papPendingStrings[i];
|
---|
873 | cchOld += pCurStr->cchString;
|
---|
874 | if (pCurStr->cchString > cchOldMax)
|
---|
875 | cchOldMax = pCurStr->cchString;
|
---|
876 | if (pCurStr->cchString < cchOldMin)
|
---|
877 | cchOldMin = pCurStr->cchString;
|
---|
878 |
|
---|
879 | if (!bldProgStrTab_compressorFixupString(pThis, pCurStr))
|
---|
880 | return false;
|
---|
881 |
|
---|
882 | cchNew += pCurStr->cchString;
|
---|
883 | if (pCurStr->cchString > cchNewMax)
|
---|
884 | cchNewMax = pCurStr->cchString;
|
---|
885 | if (pCurStr->cchString < cchNewMin)
|
---|
886 | cchNewMin = pCurStr->cchString;
|
---|
887 |
|
---|
888 | bldProgStrTab_AddStringToHashTab(pThis, pCurStr);
|
---|
889 | }
|
---|
890 |
|
---|
891 | /*
|
---|
892 | * Do debug stats.
|
---|
893 | */
|
---|
894 | if (fVerbose)
|
---|
895 | {
|
---|
896 | for (i = 0; i < RT_ELEMENTS(pThis->aCompDict); i++)
|
---|
897 | cchNew += pThis->aCompDict[i].cchString + 1;
|
---|
898 |
|
---|
899 | printf("debug: Strings: original: %u bytes; compressed: %u bytes;", (unsigned)cchOld, (unsigned)cchNew);
|
---|
900 | if (cchNew < cchOld)
|
---|
901 | printf(" saving %u bytes (%u%%)\n", (unsigned)(cchOld - cchNew), (unsigned)((cchOld - cchNew) * 100 / cchOld));
|
---|
902 | else
|
---|
903 | printf(" wasting %u bytes!\n", (unsigned)(cchOld - cchNew));
|
---|
904 | printf("debug: Original string lengths: average %u; min %u; max %u\n",
|
---|
905 | (unsigned)(cchOld / pThis->cPendingStrings), (unsigned)cchOldMin, (unsigned)cchOldMax);
|
---|
906 | printf("debug: Compressed string lengths: average %u; min %u; max %u\n",
|
---|
907 | (unsigned)(cchNew / pThis->cPendingStrings), (unsigned)cchNewMin, (unsigned)cchNewMax);
|
---|
908 | }
|
---|
909 |
|
---|
910 | return true;
|
---|
911 | }
|
---|
912 |
|
---|
913 | #endif /* BLDPROG_STRTAB_WITH_COMPRESSION */
|
---|
914 |
|
---|
915 | /**
|
---|
916 | * Inserts a string into g_apUniqueStrings.
|
---|
917 | * @param pThis The strint table compiler instance.
|
---|
918 | * @param pStr The string.
|
---|
919 | */
|
---|
920 | static void bldProgStrTab_InsertUniqueString(PBLDPROGSTRTAB pThis, PBLDPROGSTRING pStr)
|
---|
921 | {
|
---|
922 | size_t iIdx;
|
---|
923 | size_t iEnd = pThis->cSortedStrings;
|
---|
924 | if (iEnd)
|
---|
925 | {
|
---|
926 | size_t iStart = 0;
|
---|
927 | for (;;)
|
---|
928 | {
|
---|
929 | iIdx = iStart + (iEnd - iStart) / 2;
|
---|
930 | if (pThis->papSortedStrings[iIdx]->cchString < pStr->cchString)
|
---|
931 | {
|
---|
932 | if (iIdx <= iStart)
|
---|
933 | break;
|
---|
934 | iEnd = iIdx;
|
---|
935 | }
|
---|
936 | else if (pThis->papSortedStrings[iIdx]->cchString > pStr->cchString)
|
---|
937 | {
|
---|
938 | if (++iIdx >= iEnd)
|
---|
939 | break;
|
---|
940 | iStart = iIdx;
|
---|
941 | }
|
---|
942 | else
|
---|
943 | break;
|
---|
944 | }
|
---|
945 |
|
---|
946 | if (iIdx != pThis->cSortedStrings)
|
---|
947 | memmove(&pThis->papSortedStrings[iIdx + 1], &pThis->papSortedStrings[iIdx],
|
---|
948 | (pThis->cSortedStrings - iIdx) * sizeof(pThis->papSortedStrings[iIdx]));
|
---|
949 | }
|
---|
950 | else
|
---|
951 | iIdx = 0;
|
---|
952 |
|
---|
953 | pThis->papSortedStrings[iIdx] = pStr;
|
---|
954 | pThis->cSortedStrings++;
|
---|
955 | }
|
---|
956 |
|
---|
957 |
|
---|
958 | /**
|
---|
959 | * Compiles the string table after the string has been added.
|
---|
960 | *
|
---|
961 | * This will save space by dropping string terminators, eliminating duplicates
|
---|
962 | * and try find strings that are sub-strings of others.
|
---|
963 | *
|
---|
964 | * Will initialize the StrRef of all StrTabString instances.
|
---|
965 | *
|
---|
966 | * @returns success indicator (error flagged).
|
---|
967 | * @param pThis The strint table compiler instance.
|
---|
968 | */
|
---|
969 | static bool BldProgStrTab_CompileIt(PBLDPROGSTRTAB pThis, bool fVerbose)
|
---|
970 | {
|
---|
971 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
972 | /*
|
---|
973 | * Do the compression and add all the compressed strings to the table.
|
---|
974 | */
|
---|
975 | if (!bldProgStrTab_compressorDoStringCompression(pThis, fVerbose))
|
---|
976 | return false;
|
---|
977 |
|
---|
978 | /*
|
---|
979 | * Add the dictionary strings.
|
---|
980 | */
|
---|
981 | for (unsigned i = 0; i < RT_ELEMENTS(pThis->aCompDict); i++)
|
---|
982 | if (pThis->aCompDict[i].cchString > 1)
|
---|
983 | bldProgStrTab_AddStringToHashTab(pThis, &pThis->aCompDict[i]);
|
---|
984 | # ifdef RT_STRICT
|
---|
985 | else if ( pThis->aCompDict[i].cchString != 1
|
---|
986 | # ifndef BLDPROG_STRTAB_PURE_ASCII
|
---|
987 | && i != 0xff
|
---|
988 | # endif
|
---|
989 | )
|
---|
990 | abort();
|
---|
991 | # endif
|
---|
992 | #endif
|
---|
993 | if (fVerbose)
|
---|
994 | printf("debug: %u unique strings (%u bytes), %u duplicates, %u collisions\n",
|
---|
995 | (unsigned)pThis->cUniqueStrings, (unsigned)pThis->cchUniqueStrings,
|
---|
996 | (unsigned)pThis->cDuplicateStrings, (unsigned)pThis->cCollisions);
|
---|
997 |
|
---|
998 | /*
|
---|
999 | * Create papSortedStrings from the hash table. The table is sorted by
|
---|
1000 | * string length, with the longer strings first, so that we increase our
|
---|
1001 | * chances of locating duplicate substrings.
|
---|
1002 | */
|
---|
1003 | pThis->papSortedStrings = (PBLDPROGSTRING *)malloc(sizeof(pThis->papSortedStrings[0]) * pThis->cUniqueStrings);
|
---|
1004 | if (!pThis->papSortedStrings)
|
---|
1005 | return false;
|
---|
1006 | pThis->cSortedStrings = 0;
|
---|
1007 | size_t idxHash = pThis->cStrHash;
|
---|
1008 | while (idxHash-- > 0)
|
---|
1009 | {
|
---|
1010 | PBLDPROGSTRING pCur = pThis->papStrHash[idxHash];
|
---|
1011 | if (pCur)
|
---|
1012 | {
|
---|
1013 | do
|
---|
1014 | {
|
---|
1015 | bldProgStrTab_InsertUniqueString(pThis, pCur);
|
---|
1016 | pCur = pCur->pNextCollision;
|
---|
1017 | } while (pCur);
|
---|
1018 | }
|
---|
1019 | }
|
---|
1020 |
|
---|
1021 | /*
|
---|
1022 | * Create the actual string table.
|
---|
1023 | */
|
---|
1024 | pThis->pachStrTab = (char *)malloc(pThis->cchUniqueStrings + 1);
|
---|
1025 | if (!pThis->pachStrTab)
|
---|
1026 | return false;
|
---|
1027 | pThis->cchStrTab = 0;
|
---|
1028 | for (size_t i = 0; i < pThis->cSortedStrings; i++)
|
---|
1029 | {
|
---|
1030 | PBLDPROGSTRING pCur = pThis->papSortedStrings[i];
|
---|
1031 | const char * const pszCur = pCur->pszString;
|
---|
1032 | size_t const cchCur = pCur->cchString;
|
---|
1033 | size_t offStrTab = pThis->cchStrTab;
|
---|
1034 |
|
---|
1035 | /*
|
---|
1036 | * See if the string is a substring already found in the string table.
|
---|
1037 | * Excluding the zero terminator increases the chances for this.
|
---|
1038 | */
|
---|
1039 | size_t cchLeft = pThis->cchStrTab >= cchCur ? pThis->cchStrTab - cchCur : 0;
|
---|
1040 | const char *pchLeft = pThis->pachStrTab;
|
---|
1041 | char const chFirst = *pszCur;
|
---|
1042 | while (cchLeft > 0)
|
---|
1043 | {
|
---|
1044 | const char *pchCandidate = (const char *)memchr(pchLeft, chFirst, cchLeft);
|
---|
1045 | if (!pchCandidate)
|
---|
1046 | break;
|
---|
1047 | if (memcmp(pchCandidate, pszCur, cchCur) == 0)
|
---|
1048 | {
|
---|
1049 | offStrTab = pchCandidate - pThis->pachStrTab;
|
---|
1050 | break;
|
---|
1051 | }
|
---|
1052 |
|
---|
1053 | cchLeft -= pchCandidate + 1 - pchLeft;
|
---|
1054 | pchLeft = pchCandidate + 1;
|
---|
1055 | }
|
---|
1056 |
|
---|
1057 | if (offStrTab == pThis->cchStrTab)
|
---|
1058 | {
|
---|
1059 | /*
|
---|
1060 | * See if the start of the string overlaps the end of the string table.
|
---|
1061 | */
|
---|
1062 | if (pThis->cchStrTab && cchCur > 1)
|
---|
1063 | {
|
---|
1064 | cchLeft = RT_MIN(pThis->cchStrTab, cchCur - 1);
|
---|
1065 | pchLeft = &pThis->pachStrTab[pThis->cchStrTab - cchLeft];
|
---|
1066 | while (cchLeft > 0)
|
---|
1067 | {
|
---|
1068 | const char *pchCandidate = (const char *)memchr(pchLeft, chFirst, cchLeft);
|
---|
1069 | if (!pchCandidate)
|
---|
1070 | break;
|
---|
1071 | cchLeft -= pchCandidate - pchLeft;
|
---|
1072 | pchLeft = pchCandidate;
|
---|
1073 | if (memcmp(pchLeft, pszCur, cchLeft) == 0)
|
---|
1074 | {
|
---|
1075 | size_t cchToCopy = cchCur - cchLeft;
|
---|
1076 | memcpy(&pThis->pachStrTab[offStrTab], &pszCur[cchLeft], cchToCopy);
|
---|
1077 | pThis->cchStrTab += cchToCopy;
|
---|
1078 | offStrTab = pchCandidate - pThis->pachStrTab;
|
---|
1079 | break;
|
---|
1080 | }
|
---|
1081 | cchLeft--;
|
---|
1082 | pchLeft++;
|
---|
1083 | }
|
---|
1084 | }
|
---|
1085 |
|
---|
1086 | /*
|
---|
1087 | * If we didn't have any luck above, just append the string.
|
---|
1088 | */
|
---|
1089 | if (offStrTab == pThis->cchStrTab)
|
---|
1090 | {
|
---|
1091 | memcpy(&pThis->pachStrTab[offStrTab], pszCur, cchCur);
|
---|
1092 | pThis->cchStrTab += cchCur;
|
---|
1093 | }
|
---|
1094 | }
|
---|
1095 |
|
---|
1096 | /*
|
---|
1097 | * Set the string table offset for all the references to this string.
|
---|
1098 | */
|
---|
1099 | do
|
---|
1100 | {
|
---|
1101 | pCur->offStrTab = (uint32_t)offStrTab;
|
---|
1102 | pCur = pCur->pNextRef;
|
---|
1103 | } while (pCur != NULL);
|
---|
1104 | }
|
---|
1105 |
|
---|
1106 | if (fVerbose)
|
---|
1107 | printf("debug: String table: %u bytes\n", (unsigned)pThis->cchStrTab);
|
---|
1108 | return true;
|
---|
1109 | }
|
---|
1110 |
|
---|
1111 |
|
---|
1112 | #ifdef RT_STRICT
|
---|
1113 | /**
|
---|
1114 | * Sanity checks a string table string.
|
---|
1115 | * @param pThis The strint table compiler instance.
|
---|
1116 | * @param pStr The string to check.
|
---|
1117 | */
|
---|
1118 | static void BldProgStrTab_CheckStrTabString(PBLDPROGSTRTAB pThis, PBLDPROGSTRING pStr)
|
---|
1119 | {
|
---|
1120 | if (pStr->cchString != strlen(pStr->pszString))
|
---|
1121 | abort();
|
---|
1122 | if (pStr->offStrTab >= pThis->cchStrTab)
|
---|
1123 | abort();
|
---|
1124 | if (pStr->offStrTab + pStr->cchString > pThis->cchStrTab)
|
---|
1125 | abort();
|
---|
1126 | if (memcmp(pStr->pszString, &pThis->pachStrTab[pStr->offStrTab], pStr->cchString) != 0)
|
---|
1127 | abort();
|
---|
1128 | }
|
---|
1129 | #endif
|
---|
1130 |
|
---|
1131 |
|
---|
1132 | /**
|
---|
1133 | * Output the string table string in C string litteral fashion.
|
---|
1134 | *
|
---|
1135 | * @param pThis The strint table instance.
|
---|
1136 | * @param pString The string to print.
|
---|
1137 | * @param pOut The output stream.
|
---|
1138 | */
|
---|
1139 | static void BldProgStrTab_PrintCStringLitteral(PBLDPROGSTRTAB pThis, PBLDPROGSTRING pString, FILE *pOut)
|
---|
1140 | {
|
---|
1141 | const unsigned char *psz = (const unsigned char *)pString->pszString;
|
---|
1142 | unsigned char uch;
|
---|
1143 | while ((uch = *psz++) != '\0')
|
---|
1144 | {
|
---|
1145 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
1146 | if (pThis->aCompDict[uch].cchString == 1)
|
---|
1147 | #else
|
---|
1148 | if (!(uch & 0x80))
|
---|
1149 | #endif
|
---|
1150 | {
|
---|
1151 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
1152 | if (uch == 0xff)
|
---|
1153 | abort();
|
---|
1154 | #endif
|
---|
1155 | if (uch != '\'' && uch != '\\')
|
---|
1156 | fputc((char)uch, pOut);
|
---|
1157 | else
|
---|
1158 | {
|
---|
1159 | fputc('\\', pOut);
|
---|
1160 | fputc((char)uch, pOut);
|
---|
1161 | }
|
---|
1162 | }
|
---|
1163 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
1164 | # ifndef BLDPROG_STRTAB_PURE_ASCII
|
---|
1165 | else if (uch == 0xff)
|
---|
1166 | {
|
---|
1167 | RTUNICP uc = RTStrGetCp((const char *)psz);
|
---|
1168 | psz += RTStrCpSize(uc);
|
---|
1169 | fprintf(pOut, "\\u%04x", uc);
|
---|
1170 | }
|
---|
1171 | # endif
|
---|
1172 | else
|
---|
1173 | fputs(pThis->aCompDict[uch].pszString, pOut);
|
---|
1174 | #else
|
---|
1175 | else
|
---|
1176 | fprintf(pOut, "\\x%02x", (unsigned)uch);
|
---|
1177 | NOREF(pThis);
|
---|
1178 | #endif
|
---|
1179 | }
|
---|
1180 | }
|
---|
1181 |
|
---|
1182 |
|
---|
1183 | /**
|
---|
1184 | * Writes the string table code to the output stream.
|
---|
1185 | *
|
---|
1186 | * @param pThis The strint table compiler instance.
|
---|
1187 | * @param pOut The output stream.
|
---|
1188 | * @param pszScope The scoping ("static " or empty string),
|
---|
1189 | * including trailing space.
|
---|
1190 | * @param pszPrefix The variable prefix. Typically "g_" for C programs,
|
---|
1191 | * whereas C++ classes normally use "class::s_g".
|
---|
1192 | * @param pszBaseName The base name for the variables. The user
|
---|
1193 | * accessible variable will end up as just the
|
---|
1194 | * prefix and basename concatenated.
|
---|
1195 | */
|
---|
1196 | static void BldProgStrTab_WriteStringTable(PBLDPROGSTRTAB pThis, FILE *pOut,
|
---|
1197 | const char *pszScope, const char *pszPrefix, const char *pszBaseName)
|
---|
1198 | {
|
---|
1199 | #ifdef RT_STRICT
|
---|
1200 | /*
|
---|
1201 | * Do some quick sanity checks while we're here.
|
---|
1202 | */
|
---|
1203 | # ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
1204 | for (unsigned i = 0; i < RT_ELEMENTS(pThis->aCompDict); i++)
|
---|
1205 | {
|
---|
1206 | if (BldProgBitIsSet(pThis->bmUsedChars, i)
|
---|
1207 | # ifdef BLDPROG_STRTAB_PURE_ASCII
|
---|
1208 | ? pThis->aCompDict[i].cchString != 1U
|
---|
1209 | # else
|
---|
1210 | ? pThis->aCompDict[i].cchString != (i != 0xffU ? 1U : 0U)
|
---|
1211 | # endif
|
---|
1212 | : pThis->aCompDict[i].cchString < 1U)
|
---|
1213 | abort();
|
---|
1214 | if (pThis->aCompDict[i].cchString > 1U)
|
---|
1215 | BldProgStrTab_CheckStrTabString(pThis, &pThis->aCompDict[i]);
|
---|
1216 | }
|
---|
1217 | # endif
|
---|
1218 | #endif
|
---|
1219 |
|
---|
1220 | /*
|
---|
1221 | * Create a table for speeding up the character categorization.
|
---|
1222 | */
|
---|
1223 | uint8_t abCharCat[256];
|
---|
1224 | memset(abCharCat, 0, sizeof(abCharCat));
|
---|
1225 | abCharCat[(unsigned char)'\\'] = 1;
|
---|
1226 | abCharCat[(unsigned char)'\''] = 1;
|
---|
1227 | for (unsigned i = 0; i < 0x20; i++)
|
---|
1228 | abCharCat[i] = 2;
|
---|
1229 | for (unsigned i = 0x7f; i < 0x100; i++)
|
---|
1230 | abCharCat[i] = 2;
|
---|
1231 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
1232 | for (unsigned i = 0; i < 0x100; i++)
|
---|
1233 | if (!BldProgBitIsSet(pThis->bmUsedChars, i)) /* Encode table references using '\xYY'. */
|
---|
1234 | abCharCat[i] = 2;
|
---|
1235 | #endif
|
---|
1236 |
|
---|
1237 | /*
|
---|
1238 | * We follow the sorted string table, one string per line.
|
---|
1239 | */
|
---|
1240 | fprintf(pOut,
|
---|
1241 | "#include <iprt/bldprog-strtab.h>\n"
|
---|
1242 | "\n"
|
---|
1243 | "static const char g_achStrTab%s[] =\n"
|
---|
1244 | "{\n",
|
---|
1245 | pszBaseName);
|
---|
1246 |
|
---|
1247 | uint32_t off = 0;
|
---|
1248 | for (uint32_t i = 0; i < pThis->cSortedStrings; i++)
|
---|
1249 | {
|
---|
1250 | PBLDPROGSTRING pCur = pThis->papSortedStrings[i];
|
---|
1251 | uint32_t offEnd = pCur->offStrTab + (uint32_t)pCur->cchString;
|
---|
1252 | if (offEnd > off)
|
---|
1253 | {
|
---|
1254 | /* Comment with an uncompressed and more readable version of the string. */
|
---|
1255 | if (off == pCur->offStrTab)
|
---|
1256 | fprintf(pOut, "/* 0x%05x = \"", off);
|
---|
1257 | else
|
---|
1258 | fprintf(pOut, "/* 0X%05x = \"", off);
|
---|
1259 | BldProgStrTab_PrintCStringLitteral(pThis, pCur, pOut);
|
---|
1260 | fputs("\" */\n", pOut);
|
---|
1261 |
|
---|
1262 | /* Must use char by char here or we may trigger the max string
|
---|
1263 | length limit in the compiler, */
|
---|
1264 | fputs(" ", pOut);
|
---|
1265 | for (; off < offEnd; off++)
|
---|
1266 | {
|
---|
1267 | unsigned char uch = pThis->pachStrTab[off];
|
---|
1268 | fputc('\'', pOut);
|
---|
1269 | if (abCharCat[uch] == 0)
|
---|
1270 | fputc(uch, pOut);
|
---|
1271 | else if (abCharCat[uch] != 1)
|
---|
1272 | fprintf(pOut, "\\x%02x", (unsigned)uch);
|
---|
1273 | else
|
---|
1274 | {
|
---|
1275 | fputc('\\', pOut);
|
---|
1276 | fputc(uch, pOut);
|
---|
1277 | }
|
---|
1278 | fputc('\'', pOut);
|
---|
1279 | fputc(',', pOut);
|
---|
1280 | }
|
---|
1281 | fputc('\n', pOut);
|
---|
1282 | }
|
---|
1283 | }
|
---|
1284 |
|
---|
1285 | fprintf(pOut,
|
---|
1286 | "};\n"
|
---|
1287 | "AssertCompile(sizeof(g_achStrTab%s) == %#x);\n\n",
|
---|
1288 | pszBaseName, (unsigned)pThis->cchStrTab);
|
---|
1289 |
|
---|
1290 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
1291 | /*
|
---|
1292 | * Write the compression dictionary.
|
---|
1293 | */
|
---|
1294 | fprintf(pOut,
|
---|
1295 | "static const RTBLDPROGSTRREF g_aCompDict%s[%u] = \n"
|
---|
1296 | "{\n",
|
---|
1297 | pszBaseName, (unsigned)RT_ELEMENTS(pThis->aCompDict));
|
---|
1298 | for (unsigned i = 0; i < RT_ELEMENTS(pThis->aCompDict); i++)
|
---|
1299 | if (pThis->aCompDict[i].cchString > 1)
|
---|
1300 | fprintf(pOut, " /*[%3u]=*/ { %#08x, %#04x }, // %6lu - %s\n", i,
|
---|
1301 | pThis->aCompDict[i].offStrTab, (unsigned)pThis->aCompDict[i].cchString,
|
---|
1302 | (unsigned long)pThis->auCompDictFreq[i], pThis->aCompDict[i].pszString);
|
---|
1303 | # ifndef BLDPROG_STRTAB_PURE_ASCII
|
---|
1304 | else if (i == 0xff)
|
---|
1305 | fprintf(pOut, " /*[%3u]=*/ { 0x000000, 0x00 }, // UTF-8 escape\n", i);
|
---|
1306 | # endif
|
---|
1307 | else if (i == 0)
|
---|
1308 | fprintf(pOut, " /*[%3u]=*/ { 0x000000, 0x00 }, // unused, because zero terminator\n", i);
|
---|
1309 | else if (i < 0x20 || i >= 0x7f)
|
---|
1310 | fprintf(pOut, " /*[%3u]=*/ { 0x000000, 0x00 }, // %02x\n", i, i);
|
---|
1311 | else
|
---|
1312 | fprintf(pOut, " /*[%3u]=*/ { 0x000000, 0x00 }, // '%c'\n", i, (char)i);
|
---|
1313 | fprintf(pOut, "};\n\n");
|
---|
1314 | #endif
|
---|
1315 |
|
---|
1316 |
|
---|
1317 | /*
|
---|
1318 | * Write the string table data structure.
|
---|
1319 | */
|
---|
1320 | fprintf(pOut,
|
---|
1321 | "%sconst RTBLDPROGSTRTAB %s%s = \n"
|
---|
1322 | "{\n"
|
---|
1323 | " /*.pchStrTab = */ &g_achStrTab%s[0],\n"
|
---|
1324 | " /*.cchStrTab = */ sizeof(g_achStrTab%s),\n"
|
---|
1325 | ,
|
---|
1326 | pszScope, pszPrefix, pszBaseName, pszBaseName, pszBaseName);
|
---|
1327 | #ifdef BLDPROG_STRTAB_WITH_COMPRESSION
|
---|
1328 | fprintf(pOut,
|
---|
1329 | " /*.cCompDict = */ %u,\n"
|
---|
1330 | " /*.paCompDict = */ &g_aCompDict%s[0]\n"
|
---|
1331 | "};\n"
|
---|
1332 | # ifndef BLDPROG_STRTAB_PURE_ASCII /* 255 or 256 entries is how the decoder knows */
|
---|
1333 | , (unsigned)RT_ELEMENTS(pThis->aCompDict) - 1,
|
---|
1334 | # else
|
---|
1335 | , (unsigned)RT_ELEMENTS(pThis->aCompDict),
|
---|
1336 | # endif
|
---|
1337 | pszBaseName);
|
---|
1338 | #else
|
---|
1339 | fprintf(pOut,
|
---|
1340 | " /*.cCompDict = */ 0,\n"
|
---|
1341 | " /*.paCompDict = */ NULL\n"
|
---|
1342 | "};\n");
|
---|
1343 | #endif
|
---|
1344 | }
|
---|
1345 |
|
---|
1346 | #if RT_CLANG_PREREQ(4, 0) || RT_GNUC_PREREQ(4, 6)
|
---|
1347 | # pragma GCC diagnostic pop
|
---|
1348 | #endif
|
---|
1349 |
|
---|
1350 | #endif /* __cplusplus && IN_RING3 */
|
---|
1351 |
|
---|