source: icXML/icXML-devel/src/icxmlc/XMLParallelTokenizer.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: 7.2 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: XMLParallelTokenizer.hpp 207 2012-12-02 20:38:22Z robc $
10 *
11 */
12
13#ifndef XMLPARALLELTOKENIZER_HPP
14#define XMLPARALLELTOKENIZER_HPP
15
16#include <icxmlc/Array.hpp>
17#include <simd-lib/bitblock_iterator.hpp>
18#include <icxmlc/XMLConfig.hpp>
19
20#if BLOCK_SIZE == 128
21#else
22        #error "XMLParallelTokenizer is not defined yet for this BLOCK_SIZE"
23#endif
24
25XERCES_CPP_NAMESPACE_BEGIN
26
27class XMLParallelTokenizer
28{
29                typedef scanword_t iterator_t;
30                enum { BITS_PER_ITERATOR = sizeof(iterator_t) * 8 };
31
32        public:
33
34                XMLParallelTokenizer(XMLCh * string, XMLSize_t length)
35                : fString(string)
36                , fLength(length)
37                , fState(0)
38                , fTokens(0)
39                {
40
41                }
42
43                ~XMLParallelTokenizer()
44                {
45                }
46
47                IDISA_ALWAYS_INLINE
48                void scanWhitespace();
49
50                IDISA_ALWAYS_INLINE
51                void scanLFs();
52
53                IDISA_ALWAYS_INLINE
54                int scanTuples();
55
56                IDISA_ALWAYS_INLINE
57                size_t size() const
58                {
59                        return fTokens;
60                }
61
62                IDISA_ALWAYS_INLINE
63                const XMLCh * operator[](const int index) const
64                {
65                        return fToken[index];
66                }
67
68        private:
69
70                IDISA_ALWAYS_INLINE
71                bool validateTuple(const XMLCh * src, iterator_t tupleMarkers, XMLCh & lastQuote);
72
73                IDISA_ALWAYS_INLINE
74                void addTokens(XMLCh * src, iterator_t whitespace, iterator_t whitespace_carry);
75
76                template<size_t blocks>
77                IDISA_ALWAYS_INLINE
78                static iterator_t tokenize(const BytePack * input, const BytePack m1, const BytePack m2, const BytePack m3);
79
80                template<size_t blocks>
81                IDISA_ALWAYS_INLINE
82                static BytePack mask(const BytePack * input, const BytePack m1, const BytePack m2, const BytePack m3);
83
84        XMLCh * const                                                           fString;
85        const XMLSize_t                                                         fLength;
86
87        unsigned int                                                            fState;
88        DynamicArray<const XMLCh *, 16>                         fToken;
89        size_t                                                                          fTokens;
90};
91
92void XMLParallelTokenizer::scanWhitespace()
93{
94        const BytePack spmask = simd<16>::constant<chSpace>();
95        const BytePack lfmask = simd<16>::constant<chLF>();
96        const BytePack htmask = simd<16>::constant<chHTab>();
97
98        iterator_t whitespaceCarry = 1;
99        const BytePack * src = (const BytePack*)(fString);
100        size_t length = fLength;
101
102        while (length >= BITS_PER_ITERATOR)
103        {
104                iterator_t whitespace = tokenize<sizeof(iterator_t)>(src, spmask, lfmask, htmask);
105                addTokens((XMLCh*)src, whitespace, whitespaceCarry);
106                whitespaceCarry = whitespace >> (BITS_PER_ITERATOR - 1);
107                src += sizeof(iterator_t);
108                length -= BITS_PER_ITERATOR;
109        }
110
111        if (length)
112        {
113                const iterator_t one = 1;
114                const iterator_t lengthMask = (one << length) - 1;
115                iterator_t whitespace = tokenize<sizeof(iterator_t)>(src, spmask, lfmask, htmask) | ~lengthMask;
116                addTokens((XMLCh*)src, whitespace, whitespaceCarry);
117        }
118}
119
120int XMLParallelTokenizer::scanTuples()
121{
122        const BytePack spmask = simd<16>::constant<chSpace>();
123        const BytePack lfmask = simd<16>::constant<chLF>();
124        const BytePack htmask = simd<16>::constant<chHTab>();
125
126        const BytePack eqmask = simd<16>::constant<chEqual>();
127        const BytePack sqmask = simd<16>::constant<chSingleQuote>();
128        const BytePack dqmask = simd<16>::constant<chDoubleQuote>();
129
130        iterator_t whitespaceCarry = 1;
131        XMLCh lastQuote;
132        const BytePack * src = (const BytePack*)(fString);
133        size_t length = fLength;
134
135        while (length >= BITS_PER_ITERATOR)
136        {
137                const iterator_t tuples =
138                        tokenize<sizeof(iterator_t)>(src, eqmask, sqmask, dqmask);
139                const iterator_t whitespace =
140                        tokenize<sizeof(iterator_t)>(src, spmask, lfmask, htmask) | tuples;
141
142                // validate that the tuple markers are in the correct order
143                if (unlikely(!validateTuple((const XMLCh*)src, tuples, lastQuote)))
144                {
145                        return fState + 1;
146                }
147
148                addTokens((XMLCh*)src, whitespace, whitespaceCarry);
149                whitespaceCarry = whitespace >> (BITS_PER_ITERATOR - 1);
150
151                src += sizeof(iterator_t);
152
153                length -= BITS_PER_ITERATOR;
154        }
155
156        if (length)
157        {
158                const iterator_t one = 1;
159                const iterator_t lengthMask = (one << (length - 1)) - 1;
160
161                const iterator_t tuples =
162                        tokenize<sizeof(iterator_t)>(src, eqmask, sqmask, dqmask) & lengthMask;
163
164                const iterator_t whitespace =
165                        (tokenize<sizeof(iterator_t)>(src, spmask, lfmask, htmask) | tuples) | ~lengthMask;
166
167                // validate that the tuple markers are in the correct order
168                if (unlikely(!validateTuple((const XMLCh*)src, tuples, lastQuote)))
169                {
170                        return fState + 1;
171                }
172
173                addTokens((XMLCh*)src, whitespace, whitespaceCarry);
174        }
175
176        // if fState is not 0 here, then we ended with one or two missing quote marks
177        if (likely(fState == 0 && (fTokens % 2) == 0))
178        {
179                return 0;
180        }
181        else
182        {
183                return fState + 1;
184        }
185}
186
187bool XMLParallelTokenizer::validateTuple(const XMLCh * src, iterator_t tuples, XMLCh & lastQuote)
188{
189        while (tuples)
190        {
191                uint64_t pos = scan_forward_zeroes(tuples);
192                tuples &= (tuples - 1);
193
194                const XMLCh mark = src[pos];
195                if (mark == chEqual)
196                {
197                        if (likely(fState == 0))
198                        {
199                                fState = 1;
200                        }
201                        else
202                        {
203                                return 0;
204                        }
205                }
206                else // if ((mark == chSingleQuote) || (mark == chDoubleQuote))
207                {
208                        if (fState == 1)
209                        {
210                                lastQuote = mark;
211                                fState = 2;
212                        }
213                        else if (unlikely(lastQuote != mark))
214                        {
215                                return 0;
216                        }
217                        else
218                        {
219                                fState = 0;
220                        }
221                }
222        }
223        return 1;
224}
225
226void XMLParallelTokenizer::addTokens(XMLCh * src, iterator_t whitespace, iterator_t whitespaceCarry)
227{
228        // get the first character of every string
229        iterator_t first = ~whitespace & (whitespace << 1 | whitespaceCarry);
230        while (first)
231        {
232                size_t pos = scan_forward_zeroes(first);
233                if (unlikely(fTokens == fToken.capacity()))
234                {
235                        fToken.expand(fToken.capacity());
236                }
237                fToken[fTokens++] = &src[pos];
238
239                first &= (first - 1);
240        }
241
242        // now get the first space after each string
243        first = ((~whitespaceCarry & 1) | (~whitespace) << 1) & whitespace;
244        while (first)
245        {
246                scanword_t pos = scan_forward_zeroes(first);
247                src[pos] = chNull;
248                first &= (first - 1);
249        }
250}
251
252template<>
253IDISA_ALWAYS_INLINE
254BytePack
255XMLParallelTokenizer::mask<1>(const BytePack * input, const BytePack m1, const BytePack m2, const BytePack m3)
256{
257        const BytePack a = bitblock::load_unaligned(input);
258        return simd_or(simd<16>::eq(a, m1), simd_or(simd<16>::eq(a, m2), simd<16>::eq(a, m3)));
259}
260
261template<>
262IDISA_ALWAYS_INLINE
263BytePack
264XMLParallelTokenizer::mask<2>(const BytePack * input, const BytePack m1, const BytePack m2, const BytePack m3)
265{
266        const BytePack b = mask<1>(&input[0], m1, m2, m3);
267        const BytePack a = mask<1>(&input[1], m1, m2, m3);
268        return hsimd128<16>::packss(a, b);
269}
270
271template<>
272IDISA_ALWAYS_INLINE
273iterator_t
274XMLParallelTokenizer::tokenize<1>(const BytePack * input, const BytePack m1, const BytePack m2, const BytePack m3)
275{
276        return hsimd<16>::signmask(mask<1>(&input[0], m1, m2, m3));
277}
278
279template<>
280IDISA_ALWAYS_INLINE
281iterator_t
282XMLParallelTokenizer::tokenize<2>(const BytePack * input, const BytePack m1, const BytePack m2, const BytePack m3)
283{
284        return hsimd<8>::signmask(mask<2>(&input[0], m1, m2, m3));
285}
286
287template<size_t blocks>
288IDISA_ALWAYS_INLINE
289iterator_t
290XMLParallelTokenizer::tokenize(const BytePack * input, const BytePack m1, const BytePack m2, const BytePack m3)
291{
292        enum { half = (blocks / 2) };
293
294        return tokenize<half>(&input[0], m1, m2, m3) | (tokenize<blocks - half>(&input[half], m1, m2, m3) << (half * 8));
295}
296
297XERCES_CPP_NAMESPACE_END
298
299#endif // XMLPARALLELTOKENIZER_HPP
Note: See TracBrowser for help on using the repository browser.