1 // © 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
3 /*
4 ******************************************************************************
5 *
6 *   Copyright (C) 1999-2011, International Business Machines
7 *   Corporation and others.  All Rights Reserved.
8 *
9 ******************************************************************************/
10 
11 
12 /*------------------------------------------------------------------------------
13  *
14  *   UCommonData   An abstract interface for dealing with ICU Common Data Files.
15  *                 ICU Common Data Files are a grouping of a number of individual
16  *                 data items (resources, converters, tables, anything) into a
17  *                 single file or dll.  The combined format includes a table of
18  *                 contents for locating the individual items by name.
19  *
20  *                 Two formats for the table of contents are supported, which is
21  *                 why there is an abstract inteface involved.
22  *
23  */
24 
25 #include "unicode/utypes.h"
26 #include "unicode/udata.h"
27 #include "cstring.h"
28 #include "ucmndata.h"
29 #include "udatamem.h"
30 
31 #if defined(UDATA_DEBUG) || defined(UDATA_DEBUG_DUMP)
32 #   include <stdio.h>
33 #endif
34 
35 U_CFUNC uint16_t
udata_getHeaderSize(const DataHeader * udh)36 udata_getHeaderSize(const DataHeader *udh) {
37     if(udh==NULL) {
38         return 0;
39     } else if(udh->info.isBigEndian==U_IS_BIG_ENDIAN) {
40         /* same endianness */
41         return udh->dataHeader.headerSize;
42     } else {
43         /* opposite endianness */
44         uint16_t x=udh->dataHeader.headerSize;
45         return (uint16_t)((x<<8)|(x>>8));
46     }
47 }
48 
49 U_CFUNC uint16_t
udata_getInfoSize(const UDataInfo * info)50 udata_getInfoSize(const UDataInfo *info) {
51     if(info==NULL) {
52         return 0;
53     } else if(info->isBigEndian==U_IS_BIG_ENDIAN) {
54         /* same endianness */
55         return info->size;
56     } else {
57         /* opposite endianness */
58         uint16_t x=info->size;
59         return (uint16_t)((x<<8)|(x>>8));
60     }
61 }
62 
63 /*-----------------------------------------------------------------------------*
64  *                                                                             *
65  *  Pointer TOCs.   TODO: This form of table-of-contents should be removed     *
66  *                  because DLLs must be relocated on loading to correct the   *
67  *                  pointer values and this operation makes shared memory      *
68  *                  mapping of the data much less likely to work.              *
69  *                                                                             *
70  *-----------------------------------------------------------------------------*/
71 typedef struct {
72     const char       *entryName;
73     const DataHeader *pHeader;
74 } PointerTOCEntry;
75 
76 
77 typedef struct  {
78     uint32_t          count;
79     uint32_t          reserved;
80     /**
81      * Variable-length array declared with length 1 to disable bounds checkers.
82      * The actual array length is in the count field.
83      */
84     PointerTOCEntry   entry[1];
85 }  PointerTOC;
86 
87 
88 /* definition of OffsetTOC struct types moved to ucmndata.h */
89 
90 /*-----------------------------------------------------------------------------*
91  *                                                                             *
92  *    entry point lookup implementations                                       *
93  *                                                                             *
94  *-----------------------------------------------------------------------------*/
95 
96 #ifndef MIN
97 #define MIN(a,b) (((a)<(b)) ? (a) : (b))
98 #endif
99 
100 /**
101  * Compare strings where we know the shared prefix length,
102  * and advance the prefix length as we find that the strings share even more characters.
103  */
104 static int32_t
strcmpAfterPrefix(const char * s1,const char * s2,int32_t * pPrefixLength)105 strcmpAfterPrefix(const char *s1, const char *s2, int32_t *pPrefixLength) {
106     int32_t pl=*pPrefixLength;
107     int32_t cmp=0;
108     s1+=pl;
109     s2+=pl;
110     for(;;) {
111         int32_t c1=(uint8_t)*s1++;
112         int32_t c2=(uint8_t)*s2++;
113         cmp=c1-c2;
114         if(cmp!=0 || c1==0) {  /* different or done */
115             break;
116         }
117         ++pl;  /* increment shared same-prefix length */
118     }
119     *pPrefixLength=pl;
120     return cmp;
121 }
122 
123 static int32_t
offsetTOCPrefixBinarySearch(const char * s,const char * names,const UDataOffsetTOCEntry * toc,int32_t count)124 offsetTOCPrefixBinarySearch(const char *s, const char *names,
125                             const UDataOffsetTOCEntry *toc, int32_t count) {
126     int32_t start=0;
127     int32_t limit=count;
128     /*
129      * Remember the shared prefix between s, start and limit,
130      * and don't compare that shared prefix again.
131      * The shared prefix should get longer as we narrow the [start, limit[ range.
132      */
133     int32_t startPrefixLength=0;
134     int32_t limitPrefixLength=0;
135     if(count==0) {
136         return -1;
137     }
138     /*
139      * Prime the prefix lengths so that we don't keep prefixLength at 0 until
140      * both the start and limit indexes have moved.
141      * At the same time, we find if s is one of the start and (limit-1) names,
142      * and if not, exclude them from the actual binary search.
143      */
144     if(0==strcmpAfterPrefix(s, names+toc[0].nameOffset, &startPrefixLength)) {
145         return 0;
146     }
147     ++start;
148     --limit;
149     if(0==strcmpAfterPrefix(s, names+toc[limit].nameOffset, &limitPrefixLength)) {
150         return limit;
151     }
152     while(start<limit) {
153         int32_t i=(start+limit)/2;
154         int32_t prefixLength=MIN(startPrefixLength, limitPrefixLength);
155         int32_t cmp=strcmpAfterPrefix(s, names+toc[i].nameOffset, &prefixLength);
156         if(cmp<0) {
157             limit=i;
158             limitPrefixLength=prefixLength;
159         } else if(cmp==0) {
160             return i;
161         } else {
162             start=i+1;
163             startPrefixLength=prefixLength;
164         }
165     }
166     return -1;
167 }
168 
169 static int32_t
pointerTOCPrefixBinarySearch(const char * s,const PointerTOCEntry * toc,int32_t count)170 pointerTOCPrefixBinarySearch(const char *s, const PointerTOCEntry *toc, int32_t count) {
171     int32_t start=0;
172     int32_t limit=count;
173     /*
174      * Remember the shared prefix between s, start and limit,
175      * and don't compare that shared prefix again.
176      * The shared prefix should get longer as we narrow the [start, limit[ range.
177      */
178     int32_t startPrefixLength=0;
179     int32_t limitPrefixLength=0;
180     if(count==0) {
181         return -1;
182     }
183     /*
184      * Prime the prefix lengths so that we don't keep prefixLength at 0 until
185      * both the start and limit indexes have moved.
186      * At the same time, we find if s is one of the start and (limit-1) names,
187      * and if not, exclude them from the actual binary search.
188      */
189     if(0==strcmpAfterPrefix(s, toc[0].entryName, &startPrefixLength)) {
190         return 0;
191     }
192     ++start;
193     --limit;
194     if(0==strcmpAfterPrefix(s, toc[limit].entryName, &limitPrefixLength)) {
195         return limit;
196     }
197     while(start<limit) {
198         int32_t i=(start+limit)/2;
199         int32_t prefixLength=MIN(startPrefixLength, limitPrefixLength);
200         int32_t cmp=strcmpAfterPrefix(s, toc[i].entryName, &prefixLength);
201         if(cmp<0) {
202             limit=i;
203             limitPrefixLength=prefixLength;
204         } else if(cmp==0) {
205             return i;
206         } else {
207             start=i+1;
208             startPrefixLength=prefixLength;
209         }
210     }
211     return -1;
212 }
213 
214 U_CDECL_BEGIN
215 static uint32_t U_CALLCONV
offsetTOCEntryCount(const UDataMemory * pData)216 offsetTOCEntryCount(const UDataMemory *pData) {
217     int32_t          retVal=0;
218     const UDataOffsetTOC *toc = (UDataOffsetTOC *)pData->toc;
219     if (toc != NULL) {
220         retVal = toc->count;
221     }
222     return retVal;
223 }
224 
225 static const DataHeader * U_CALLCONV
offsetTOCLookupFn(const UDataMemory * pData,const char * tocEntryName,int32_t * pLength,UErrorCode * pErrorCode)226 offsetTOCLookupFn(const UDataMemory *pData,
227                   const char *tocEntryName,
228                   int32_t *pLength,
229                   UErrorCode *pErrorCode) {
230     (void)pErrorCode;
231     const UDataOffsetTOC  *toc = (UDataOffsetTOC *)pData->toc;
232     if(toc!=NULL) {
233         const char *base=(const char *)toc;
234         int32_t number, count=(int32_t)toc->count;
235 
236         /* perform a binary search for the data in the common data's table of contents */
237 #if defined (UDATA_DEBUG_DUMP)
238         /* list the contents of the TOC each time .. not recommended */
239         for(number=0; number<count; ++number) {
240             fprintf(stderr, "\tx%d: %s\n", number, &base[toc->entry[number].nameOffset]);
241         }
242 #endif
243         number=offsetTOCPrefixBinarySearch(tocEntryName, base, toc->entry, count);
244         if(number>=0) {
245             /* found it */
246             const UDataOffsetTOCEntry *entry=toc->entry+number;
247 #ifdef UDATA_DEBUG
248             fprintf(stderr, "%s: Found.\n", tocEntryName);
249 #endif
250             if((number+1) < count) {
251                 *pLength = (int32_t)(entry[1].dataOffset - entry->dataOffset);
252             } else {
253                 *pLength = -1;
254             }
255             return (const DataHeader *)(base+entry->dataOffset);
256         } else {
257 #ifdef UDATA_DEBUG
258             fprintf(stderr, "%s: Not found.\n", tocEntryName);
259 #endif
260             return NULL;
261         }
262     } else {
263 #ifdef UDATA_DEBUG
264         fprintf(stderr, "returning header\n");
265 #endif
266 
267         return pData->pHeader;
268     }
269 }
270 
271 
pointerTOCEntryCount(const UDataMemory * pData)272 static uint32_t U_CALLCONV pointerTOCEntryCount(const UDataMemory *pData) {
273     const PointerTOC *toc = (PointerTOC *)pData->toc;
274     return (uint32_t)((toc != NULL) ? (toc->count) : 0);
275 }
276 
pointerTOCLookupFn(const UDataMemory * pData,const char * name,int32_t * pLength,UErrorCode * pErrorCode)277 static const DataHeader * U_CALLCONV pointerTOCLookupFn(const UDataMemory *pData,
278                    const char *name,
279                    int32_t *pLength,
280                    UErrorCode *pErrorCode) {
281     (void)pErrorCode;
282     if(pData->toc!=NULL) {
283         const PointerTOC *toc = (PointerTOC *)pData->toc;
284         int32_t number, count=(int32_t)toc->count;
285 
286 #if defined (UDATA_DEBUG_DUMP)
287         /* list the contents of the TOC each time .. not recommended */
288         for(number=0; number<count; ++number) {
289             fprintf(stderr, "\tx%d: %s\n", number, toc->entry[number].entryName);
290         }
291 #endif
292         number=pointerTOCPrefixBinarySearch(name, toc->entry, count);
293         if(number>=0) {
294             /* found it */
295 #ifdef UDATA_DEBUG
296             fprintf(stderr, "%s: Found.\n", toc->entry[number].entryName);
297 #endif
298             *pLength=-1;
299             return UDataMemory_normalizeDataPointer(toc->entry[number].pHeader);
300         } else {
301 #ifdef UDATA_DEBUG
302             fprintf(stderr, "%s: Not found.\n", name);
303 #endif
304             return NULL;
305         }
306     } else {
307         return pData->pHeader;
308     }
309 }
310 U_CDECL_END
311 
312 
313 static const commonDataFuncs CmnDFuncs = {offsetTOCLookupFn,  offsetTOCEntryCount};
314 static const commonDataFuncs ToCPFuncs = {pointerTOCLookupFn, pointerTOCEntryCount};
315 
316 
317 
318 /*----------------------------------------------------------------------*
319  *                                                                      *
320  *  checkCommonData   Validate the format of a common data file.        *
321  *                    Fill in the virtual function ptr based on TOC type *
322  *                    If the data is invalid, close the UDataMemory     *
323  *                    and set the appropriate error code.               *
324  *                                                                      *
325  *----------------------------------------------------------------------*/
udata_checkCommonData(UDataMemory * udm,UErrorCode * err)326 U_CFUNC void udata_checkCommonData(UDataMemory *udm, UErrorCode *err) {
327     if (U_FAILURE(*err)) {
328         return;
329     }
330 
331     if(udm==NULL || udm->pHeader==NULL) {
332       *err=U_INVALID_FORMAT_ERROR;
333     } else if(!(udm->pHeader->dataHeader.magic1==0xda &&
334         udm->pHeader->dataHeader.magic2==0x27 &&
335         udm->pHeader->info.isBigEndian==U_IS_BIG_ENDIAN &&
336         udm->pHeader->info.charsetFamily==U_CHARSET_FAMILY)
337         ) {
338         /* header not valid */
339         *err=U_INVALID_FORMAT_ERROR;
340     }
341     else if (udm->pHeader->info.dataFormat[0]==0x43 &&
342         udm->pHeader->info.dataFormat[1]==0x6d &&
343         udm->pHeader->info.dataFormat[2]==0x6e &&
344         udm->pHeader->info.dataFormat[3]==0x44 &&
345         udm->pHeader->info.formatVersion[0]==1
346         ) {
347         /* dataFormat="CmnD" */
348         udm->vFuncs = &CmnDFuncs;
349         udm->toc=(const char *)udm->pHeader+udata_getHeaderSize(udm->pHeader);
350     }
351     else if(udm->pHeader->info.dataFormat[0]==0x54 &&
352         udm->pHeader->info.dataFormat[1]==0x6f &&
353         udm->pHeader->info.dataFormat[2]==0x43 &&
354         udm->pHeader->info.dataFormat[3]==0x50 &&
355         udm->pHeader->info.formatVersion[0]==1
356         ) {
357         /* dataFormat="ToCP" */
358         udm->vFuncs = &ToCPFuncs;
359         udm->toc=(const char *)udm->pHeader+udata_getHeaderSize(udm->pHeader);
360     }
361     else {
362         /* dataFormat not recognized */
363         *err=U_INVALID_FORMAT_ERROR;
364     }
365 
366     if (U_FAILURE(*err)) {
367         /* If the data is no good and we memory-mapped it ourselves,
368          *  close the memory mapping so it doesn't leak.  Note that this has
369          *  no effect on non-memory mapped data, other than clearing fields in udm.
370          */
371         udata_close(udm);
372     }
373 }
374 
375 /*
376  * TODO: Add a udata_swapPackageHeader() function that swaps an ICU .dat package
377  * header but not its sub-items.
378  * This function will be needed for automatic runtime swapping.
379  * Sub-items should not be swapped to limit the swapping to the parts of the
380  * package that are actually used.
381  *
382  * Since lengths of items are implicit in the order and offsets of their
383  * ToC entries, and since offsets are relative to the start of the ToC,
384  * a swapped version may need to generate a different data structure
385  * with pointers to the original data items and with their lengths
386  * (-1 for the last one if it is not known), and maybe even pointers to the
387  * swapped versions of the items.
388  * These pointers to swapped versions would establish a cache;
389  * instead, each open data item could simply own the storage for its swapped
390  * data. This fits better with the current design.
391  *
392  * markus 2003sep18 Jitterbug 2235
393  */
394