source: icXML/icXML-devel/src/icxmlc/XMLStringU.hpp @ 2720

Last change on this file since 2720 was 2720, checked in by cameron, 6 years ago

Initial check-in of icXML 0.8 source files

File size: 15.7 KB
Line 
1/*
2 *  Copyright © 2012 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icXML is a trademark of International Characters.
5 */
6
7/*
8 * @author Nigel Medforth, nigelm -at- interational-characters.com
9 * @version $Id: XMLStringU.hpp 207 2012-12-02 20:38:22Z robc $
10 *
11 */
12
13#ifndef XMLSTRINGMANIP_HPP
14#define XMLSTRINGMANIP_HPP
15
16#include <xercesc/validators/datatype/DatatypeValidator.hpp>
17#include <xercesc/util/XMLUniDefs.hpp>
18#include <simd-lib/bitblock.hpp>
19#include <simd-lib/builtins.hpp>
20#include <xercesc/util/XMLUniDefs.hpp>
21#include <icxmlc/XMLConfig.hpp>
22
23XERCES_CPP_NAMESPACE_BEGIN
24
25#if BLOCK_SIZE != 128
26#pragma error "XMLStringU::match8 only supports BLOCK_SIZE 128!"
27#endif
28
29#ifdef __GNUC__
30#define PURE __attribute__((pure))
31#else
32#define PURE
33#endif
34
35/**
36Contains all potentially unsafe string comparison / manipulation functions. All functions assume it's safe to
37load an entire SIMD block of text even if the length of the string is only one character / byte. If this
38assumption is not valid then the functions may or may not create segmentation faults, cause memory corruption,
39or introduce some sort of expected behavior in the program. These errors may or may not occur on all platforms
40depending on the architecture.
41
42In other words, DO NOT USE THESE FUNCTIONS IF YOU CANNOT ENSURE THAT THE ABOVE ASSUMPTION IS VALID!
43**/
44class XMLStringU
45{
46        public:
47
48                // SCHEMA
49
50                IDISA_ALWAYS_INLINE
51                static bool isTYPE(const XMLCh * string);
52
53                IDISA_ALWAYS_INLINE
54                static bool isNIL(const XMLCh * string);
55
56                IDISA_ALWAYS_INLINE
57                static bool isSCHEMALOCATION(const XMLCh * string);
58
59                IDISA_ALWAYS_INLINE
60                static bool isNONAMESPACESCHEMALOCATION(const XMLCh * string);
61
62                // XML
63
64                IDISA_ALWAYS_INLINE
65                static bool isXML(const XMLCh * string);
66
67                IDISA_ALWAYS_INLINE
68                static bool isXMLNS(const XMLCh * string);
69
70                IDISA_ALWAYS_INLINE
71                static bool isCDATA(const XMLCh * string);
72
73                /**
74                Checks if the given string contains only whitespace characters i.e., {chSpace, chLF, chHTab}
75                **/
76                IDISA_ALWAYS_INLINE PURE
77                static bool isWhitespace(const XMLCh* const string, const XMLSize_t length);
78
79                /**
80                Checks if the string toTest is identical to the given string (up to the given length)
81                **/
82                IDISA_ALWAYS_INLINE PURE
83                static bool equals(const XMLCh* const toTest, const XMLCh* const string, const XMLSize_t length);
84
85                /**
86                Checks if the string toTest is identical to the given string (up to the given length)
87                **/
88                IDISA_ALWAYS_INLINE PURE
89                static bool equals(const XMLByte* const toTest, const XMLByte* const string, const XMLSize_t length);
90
91
92                template<XMLCh character>
93                IDISA_ALWAYS_INLINE PURE
94                static int indexOf(const XMLCh * const string, const XMLSize_t length);
95
96                /**
97                Determines the length of a given string by searching for the trailing chNull character
98                **/
99                IDISA_ALWAYS_INLINE PURE
100                static XMLSize_t stringLen(const XMLCh * const string);
101
102                /**
103                Determines the length of a given string by searching for the trailing chNull character
104                or the first instance of a given character
105                **/
106                template <XMLCh character>
107                IDISA_ALWAYS_INLINE PURE
108                static XMLSize_t stringLenOrIndexOf(const XMLCh * const string);
109
110        private:
111
112                template < XMLSize_t length
113                                 , XMLCh c0, XMLCh c1, XMLCh c2, XMLCh c3, XMLCh c4, XMLCh c5, XMLCh c6, XMLCh c7>
114                IDISA_ALWAYS_INLINE
115                static bool match8(const XMLCh * string);
116
117
118                template < XMLSize_t length
119                                 , XMLCh c0, XMLCh c1, XMLCh c2, XMLCh c3, XMLCh c4, XMLCh c5, XMLCh c6, XMLCh c7
120                                 , XMLCh c8, XMLCh c9, XMLCh c10, XMLCh c11, XMLCh c12, XMLCh c13, XMLCh c14, XMLCh c15>
121                IDISA_ALWAYS_INLINE
122                static bool match16(const XMLCh * string);
123
124
125                template < XMLSize_t length
126                                 , XMLCh c0, XMLCh c1, XMLCh c2, XMLCh c3, XMLCh c4, XMLCh c5, XMLCh c6, XMLCh c7
127                                 , XMLCh c8, XMLCh c9, XMLCh c10, XMLCh c11, XMLCh c12, XMLCh c13, XMLCh c14, XMLCh c15
128                                 , XMLCh c16, XMLCh c17, XMLCh c18, XMLCh c19, XMLCh c20, XMLCh c21, XMLCh c22, XMLCh c23
129                                 , XMLCh c24, XMLCh c25, XMLCh c26, XMLCh c27, XMLCh c28, XMLCh c29, XMLCh c30, XMLCh c31>
130                IDISA_ALWAYS_INLINE
131                static bool match32(const XMLCh * string);
132};
133
134// -------------------------------------------------------------------------------------------
135
136template < XMLSize_t length
137                 , XMLCh c0, XMLCh c1, XMLCh c2, XMLCh c3, XMLCh c4, XMLCh c5, XMLCh c6, XMLCh c7>
138bool XMLStringU::match8(const XMLCh * string)
139{
140        union packed
141        {
142                XMLCh __string[8];
143                BytePack value;
144        } STRING = {{ c0, c1, c2, c3, c4, c5, c6, c7 }};
145
146        const BytePack fixedVal = bitblock::load_aligned(&STRING.value);
147        const BytePack inputVal = bitblock::load_unaligned((const BytePack*)string);
148        const unsigned int matchingChars = hsimd<8>::signmask(simd<16>::eq(inputVal, fixedVal));
149        const unsigned int one = 1;
150        const unsigned int matchMask = ((one << (length * sizeof(XMLCh))) - one);
151
152        return (matchingChars & matchMask) == matchMask;
153}
154
155template < XMLSize_t length
156                 , XMLCh c0, XMLCh c1, XMLCh c2, XMLCh c3, XMLCh c4, XMLCh c5, XMLCh c6, XMLCh c7
157                 , XMLCh c8, XMLCh c9, XMLCh c10, XMLCh c11, XMLCh c12, XMLCh c13, XMLCh c14, XMLCh c15>
158bool XMLStringU::match16(const XMLCh * string)
159{
160                return match8<8, c0, c1, c2, c3, c4, c5, c6, c7>(string) &&
161                           match8<length - 8, c8, c9, c10, c11, c12, c13, c14, c15>(string + 8);
162}
163
164template < XMLSize_t length
165                 , XMLCh c0, XMLCh c1, XMLCh c2, XMLCh c3, XMLCh c4, XMLCh c5, XMLCh c6, XMLCh c7
166                 , XMLCh c8, XMLCh c9, XMLCh c10, XMLCh c11, XMLCh c12, XMLCh c13, XMLCh c14, XMLCh c15
167                 , XMLCh c16, XMLCh c17, XMLCh c18, XMLCh c19, XMLCh c20, XMLCh c21, XMLCh c22, XMLCh c23
168                 , XMLCh c24, XMLCh c25, XMLCh c26, XMLCh c27, XMLCh c28, XMLCh c29, XMLCh c30, XMLCh c31>
169bool XMLStringU::match32(const XMLCh * string)
170{
171        return
172                match16<16, c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15>(string) &&
173                match16<length - 16, c16, c17, c18, c19, c20, c21, c22, c23, c24, c25, c26, c27, c28, c29, c30, c31>(string + 16);
174}
175
176
177// -------------------------------------------------------------------------------------------
178
179bool XMLStringU::isXML(const XMLCh * string)
180{
181        return XMLStringU::match8<3, chLatin_x, chLatin_m, chLatin_l, 0, 0, 0, 0, 0>(string);
182}
183
184bool XMLStringU::isXMLNS(const XMLCh * string)
185{
186        return XMLStringU::match8<5, chLatin_x, chLatin_m, chLatin_l, chLatin_n, chLatin_s, 0, 0, 0>(string);
187}
188
189bool XMLStringU::isCDATA(const XMLCh * string)
190{
191        return XMLStringU::match8<6, chLatin_C, chLatin_D, chLatin_A, chLatin_T, chLatin_A, chOpenSquare, 0, 0>(string);
192}
193
194bool XMLStringU::isTYPE(const XMLCh * string)
195{
196        return XMLStringU::match8<4, chLatin_t, chLatin_y, chLatin_p, chLatin_e, 0, 0, 0, 0>(string);
197}
198
199bool XMLStringU::isNIL(const XMLCh * string)
200{
201        return XMLStringU::match8<3, chLatin_n, chLatin_i, chLatin_l, 0, 0, 0, 0, 0>(string);
202}
203
204bool XMLStringU::isSCHEMALOCATION(const XMLCh * string)
205{
206        return XMLStringU::match16<14,
207                chLatin_s, chLatin_c, chLatin_h, chLatin_e, chLatin_m, chLatin_a,
208                chLatin_L, chLatin_o, chLatin_c, chLatin_a, chLatin_t, chLatin_i, chLatin_o, chLatin_n, 0, 0>(string);
209}
210
211bool XMLStringU::isNONAMESPACESCHEMALOCATION(const XMLCh * string)
212{
213        return XMLStringU::match32<25,
214                chLatin_n, chLatin_o,
215                chLatin_N, chLatin_a, chLatin_m, chLatin_e, chLatin_s, chLatin_p, chLatin_a, chLatin_c, chLatin_e,
216                chLatin_S,chLatin_c, chLatin_h, chLatin_e, chLatin_m, chLatin_a,
217                chLatin_L, chLatin_o, chLatin_c, chLatin_a, chLatin_t, chLatin_i, chLatin_o, chLatin_n,
218                0, 0, 0, 0, 0, 0, 0>(string);
219}
220
221#define WHITESPACE_MASK(x) (simd_or(simd_or(simd<16>::eq(x, space), simd<16>::eq(x, lf)), simd<16>::eq(x, htab)))
222
223bool XMLStringU::isWhitespace(const XMLCh* const string, const XMLSize_t length)
224{
225        const BytePack space = simd<16>::constant<chSpace>();  //0x0020
226        const BytePack lf = simd<16>::constant<chLF>();        //0x000A
227        const BytePack htab = simd<16>::constant<chHTab>();    //0x0009
228
229        const BytePack * src = reinterpret_cast<const BytePack *>(string);
230
231        int index = 0;
232        int remainingLength = length; // note: remainingLength MUST be a signed type
233
234
235        enum
236        {
237                XMLCHS_PER_BYTEPACK = (sizeof(BytePack) / sizeof(XMLCh))
238                , LOG_2_SIZE_OF_XMLCH = CONST_LOG_2(sizeof(XMLCh))
239        };
240
241        while (remainingLength > XMLCHS_PER_BYTEPACK)
242        {
243                BytePack b1 = bitblock::load_unaligned(&src[index]);
244                BytePack b2 = bitblock::load_unaligned(&src[index + 1]);
245                index += 2;
246
247                const scanword_t mask = hsimd<8>::signmask(hsimd128<16>::packss(WHITESPACE_MASK(b2), WHITESPACE_MASK(b1)));
248
249                if (unlikely(mask != 0xFFFF))
250                {
251                        return scan_forward_zeroes(~mask) == (unsigned)(remainingLength);
252                }
253
254                remainingLength -= (2 * sizeof(BytePack)) / sizeof(XMLCh);
255        }
256
257        BytePack b1 = bitblock::load_unaligned(&src[index]);
258        const scanword_t mask = hsimd<16>::signmask(WHITESPACE_MASK(b1));
259
260        if (likely(mask != 0xFFFF))
261        {
262                return scan_forward_zeroes(~mask) == (unsigned)(remainingLength);
263        }
264
265        return 1;
266}
267
268#undef WHITESPACE_MASK
269
270bool XMLStringU::equals(const XMLCh * toTest, const XMLCh * fixedString, const XMLSize_t length)
271{
272        enum
273        {
274                XMLCHS_PER_BYTEPACK = (sizeof(BytePack) / sizeof(XMLCh))
275        };
276
277        const BytePack * d0 = reinterpret_cast<const BytePack *>(toTest);
278        const BytePack * d1 = reinterpret_cast<const BytePack *>(fixedString);
279        int remainingLength = length; // note: remainingLength MUST be a signed type
280        int index = 0;
281
282        while (remainingLength > XMLCHS_PER_BYTEPACK)
283        {
284                BytePack s0 = bitblock::load_unaligned(&d0[index]);
285                BytePack s1 = bitblock::load_unaligned(&d1[index]);
286                BytePack b0 = simd<16>::eq(s0, s1);
287
288                BytePack s2 = bitblock::load_unaligned(&d0[index | 1]);
289                BytePack s3 = bitblock::load_unaligned(&d1[index | 1]);
290                BytePack b1 = simd<16>::eq(s2, s3);
291
292                index += 2;
293
294                const unsigned int mask = hsimd<8>::signmask(hsimd128<8>::packss(b1, b0));
295
296                if (unlikely(mask != 0xFFFF))
297                {
298                        return scan_forward_zeroes(~mask) >= (unsigned)(remainingLength);
299                }
300
301                remainingLength -= (2 * sizeof(BytePack)) / sizeof(XMLCh);
302        }
303
304        if (unlikely(remainingLength <= 0))
305        {
306                return 1;
307        }
308
309        BytePack s0 = bitblock::load_unaligned(&d0[index]);
310        BytePack s1 = bitblock::load_unaligned(&d1[index]);
311        BytePack b0 = simd<16>::eq(s0, s1);
312
313        const unsigned int mask = hsimd<16>::signmask(b0);
314
315        return scan_forward_zeroes(~mask) >= (unsigned)(remainingLength);
316}
317
318bool XMLStringU::equals(const XMLByte * toTest, const XMLByte * fixedString, const XMLSize_t length)
319{
320        const BytePack * d0 = reinterpret_cast<const BytePack *>(toTest);
321        const BytePack * d1 = reinterpret_cast<const BytePack *>(fixedString);
322        int remainingLength = length;  // note: remainingLength MUST be a signed type
323        int index = 0;
324
325        while (remainingLength > 0)
326        {
327                BytePack s0 = bitblock::load_unaligned(&d0[index]);
328                BytePack s1 = bitblock::load_unaligned(&d1[index]);
329                const scanword_t mask = hsimd<8>::signmask(simd<8>::eq(s0, s1));
330                if (mask != 0xFFFF)
331                {
332                        return scan_forward_zeroes(~mask) >= (unsigned)(remainingLength);
333                }
334                index++;
335                remainingLength -= (sizeof(BytePack) / sizeof(XMLByte));
336        }
337
338        return 1;
339}
340
341template<XMLCh character>
342int XMLStringU::indexOf
343(
344        const   XMLCh * const       string
345        , const XMLSize_t           length
346)
347{
348        enum
349        {
350                XMLCHS_PER_BYTEPACK = (sizeof(BytePack) / sizeof(XMLCh))
351                , LOG_2_XMLCHS_PER_BYTEPACK = CONST_LOG_2(XMLCHS_PER_BYTEPACK)
352        };
353
354        const BytePack mask = simd<16>::constant<character>();
355        const BytePack * src = reinterpret_cast<const BytePack*>(string);
356
357    ssize_t remainingLength = length; // note: remainingLength MUST be a signed type
358    size_t index = 0;
359    size_t pos;
360
361    while (remainingLength >= (2 * XMLCHS_PER_BYTEPACK))
362        {
363                BytePack s0 = bitblock::load_unaligned(&src[index]);
364                BytePack b0 = simd<16>::eq(s0, mask);
365
366                BytePack s1 = bitblock::load_unaligned(&src[index | 1]);
367                BytePack b1 = simd<16>::eq(s1, mask);
368
369        pos = hsimd<8>::signmask(hsimd128<8>::packss(b1, b0));
370
371        if (pos)
372        {
373            // find the first char match and return its position
374            return (index << LOG_2_XMLCHS_PER_BYTEPACK) | scan_forward_zeroes(pos);
375        }
376
377                index += 2;
378        remainingLength -= (2 * XMLCHS_PER_BYTEPACK);
379        }
380
381    if (remainingLength > XMLCHS_PER_BYTEPACK)
382    {
383        BytePack s0 = bitblock::load_unaligned(&src[index]);
384        BytePack b0 = simd<16>::eq(s0, mask);
385
386        BytePack s1 = bitblock::load_unaligned(&src[index | 1]);
387        BytePack b1 = simd<16>::eq(s1, mask);
388
389        pos = hsimd<8>::signmask(hsimd128<8>::packss(b1, b0));
390    }
391    else if (remainingLength > 0)
392        {
393                BytePack s0 = bitblock::load_unaligned(&src[index]);
394                BytePack b0 = simd<16>::eq(s0, mask);
395
396        pos = hsimd<16>::signmask(b0);
397        }
398
399    const size_t one = 1;
400    const size_t lengthMask = (one << remainingLength) - one;
401
402    pos &= lengthMask;
403
404    if (pos)
405    {
406        // find the first char match and return its position
407        return (index << LOG_2_XMLCHS_PER_BYTEPACK) | scan_forward_zeroes(pos);
408    }
409
410        return -1;
411}
412
413/*
414bool XMLStringU::normalize(XMLCh * string, const XMLSize_t length)
415{
416        const BytePack space = simd<16>::constant<chSpace>();  //0x0020
417        const BytePack lf = simd<16>::constant<chLF>();        //0x000A
418        const BytePack htab = simd<16>::constant<chHTab>();    //0x0009
419
420        XMLSize_t index = 0;
421        XMLSize_t remainingLength = length;
422        const BytePack * data = reinterpret_cast<const BytePack *>(string);
423
424        enum
425        {
426                XMLCHS_PER_BYTEPACK = (sizeof(BytePack) / sizeof(XMLCh))
427                , LOG_2_SIZE_OF_XMLCH = CONST_LOG_2(sizeof(XMLCh))
428        };
429
430        while (remainingLength > XMLCHS_PER_BYTEPACK)
431        {
432                BytePack b1 = bitblock::load_unaligned(&data[index]);
433                BytePack b2 = bitblock::load_unaligned(&data[index + 1]);
434                index += 2;
435
436                b1 = simd_or(simd_or(simd<16>::eq(b1, space), simd<16>::eq(b1, lf)), simd<16>::eq(b1, htab));
437                b2 = simd_or(simd_or(simd<16>::eq(b2, space), simd<16>::eq(b2, lf)), simd<16>::eq(b2, htab));
438
439                const scanword_t mask = hsimd<8>::signmask(hsimd128<16>::packss(b2, b1));
440
441                if (unlikely(mask != 0xFFFF))
442                {
443                        return scan_forward_zeroes(~mask) == (remainingLength);
444                }
445
446                remainingLength -= sizeof(BytePack);
447        }
448
449        BytePack b1 = bitblock::load_unaligned(&data[index]);
450        b1 = simd_or(simd_or(simd<16>::eq(b1, space), simd<16>::eq(b1, lf)), simd<16>::eq(b1, htab));
451        const scanword_t mask = hsimd<8>::signmask(b1);
452
453        if (likely(mask != 0xFFFF))
454        {
455                return scan_forward_zeroes(~mask) == (remainingLength << LOG_2_SIZE_OF_XMLCH);
456        }
457
458        return 1;
459
460}
461*/
462
463XMLSize_t XMLStringU::stringLen(const XMLCh * const string)
464{
465        const BytePack null = simd<1>::constant<chNull>();
466        const BytePack * src = reinterpret_cast<const BytePack*>(string);
467
468        enum
469        {
470                XMLCHS_PER_BYTEPACK = (sizeof(BytePack) / sizeof(XMLCh))
471                , LOG_2_SIZE_OF_XMLCH = CONST_LOG_2(sizeof(XMLCh))
472                , LOG_2_XMLCHS_PER_BYTEPACK = CONST_LOG_2(XMLCHS_PER_BYTEPACK)
473        };
474
475        XMLSize_t index = 0;
476        for (;;)
477        {
478                BytePack s = bitblock::load_unaligned(&src[index]);
479                s = simd<16>::eq(s, null);
480                const scanword_t pos = hsimd<8>::signmask(s);
481
482                if (pos)
483                {
484                        // find the first null char match and return its position
485                        return (index << LOG_2_XMLCHS_PER_BYTEPACK) |
486                                   (scan_forward_zeroes(pos) >> LOG_2_SIZE_OF_XMLCH);
487                }
488                index++;
489        }
490        UNREACHABLE
491        return -1;
492}
493
494template <XMLCh character>
495XMLSize_t XMLStringU::stringLenOrIndexOf(const XMLCh * const string)
496{
497        const BytePack null = simd<1>::constant<chNull>();
498        const BytePack charmask = simd<16>::constant<character>();
499        const BytePack * src = reinterpret_cast<const BytePack*>(string);
500
501        enum
502        {
503                XMLCHS_PER_BYTEPACK = (sizeof(BytePack) / sizeof(XMLCh))
504                , LOG_2_SIZE_OF_XMLCH = CONST_LOG_2(sizeof(XMLCh))
505                , LOG_2_XMLCHS_PER_BYTEPACK = CONST_LOG_2(XMLCHS_PER_BYTEPACK)
506        };
507
508        XMLSize_t index = 0;
509        for (;;)
510        {
511                BytePack s = bitblock::load_unaligned(&src[index]);
512                s = simd_or(simd<16>::eq(s, null), simd<16>::eq(s, charmask));
513                const scanword_t pos = hsimd<8>::signmask(s);
514
515                if (pos)
516                {
517                        // find the first null char match and return its position
518                        return (index << LOG_2_XMLCHS_PER_BYTEPACK) |
519                                   (scan_forward_zeroes(pos) >> LOG_2_SIZE_OF_XMLCH);
520                }
521                index++;
522        }
523        UNREACHABLE
524        return -1;
525}
526
527XERCES_CPP_NAMESPACE_END
528
529#endif // XMLSTRINGMANIP_HPP
Note: See TracBrowser for help on using the repository browser.