1 // Tencent is pleased to support the open source community by making RapidJSON available.
2 //
3 // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
4 //
5 // Licensed under the MIT License (the "License"); you may not use this file except
6 // in compliance with the License. You may obtain a copy of the License at
7 //
8 // http://opensource.org/licenses/MIT
9 //
10 // Unless required by applicable law or agreed to in writing, software distributed
11 // under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
12 // CONDITIONS OF ANY KIND, either express or implied. See the License for the
13 // specific language governing permissions and limitations under the License.
14 
15 #include "perftest.h"
16 
17 #if TEST_MISC
18 
19 #define __STDC_FORMAT_MACROS
20 #include "rapidjson/stringbuffer.h"
21 
22 #define protected public
23 #include "rapidjson/writer.h"
24 #undef private
25 
26 class Misc : public PerfTest {
27 };
28 
29 // Copyright (c) 2008-2010 Bjoern Hoehrmann <bjoern@hoehrmann.de>
30 // See http://bjoern.hoehrmann.de/utf-8/decoder/dfa/ for details.
31 
32 #define UTF8_ACCEPT 0
33 #define UTF8_REJECT 12
34 
35 static const unsigned char utf8d[] = {
36     // The first part of the table maps bytes to character classes that
37     // to reduce the size of the transition table and create bitmasks.
38     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
39     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
40     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
41     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
42     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,
43     7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
44     8,8,2,2,2,2,2,2,2,2,2,2,2,2,2,2,  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
45     10,3,3,3,3,3,3,3,3,3,3,3,3,4,3,3, 11,6,6,6,5,8,8,8,8,8,8,8,8,8,8,8,
46 
47     // The second part is a transition table that maps a combination
48     // of a state of the automaton and a character class to a state.
49     0,12,24,36,60,96,84,12,12,12,48,72, 12,12,12,12,12,12,12,12,12,12,12,12,
50     12, 0,12,12,12,12,12, 0,12, 0,12,12, 12,24,12,12,12,12,12,24,12,24,12,12,
51     12,12,12,12,12,12,12,24,12,12,12,12, 12,24,12,12,12,12,12,12,12,24,12,12,
52     12,12,12,12,12,12,12,36,12,36,12,12, 12,36,12,12,12,12,12,36,12,36,12,12,
53     12,36,12,12,12,12,12,12,12,12,12,12,
54 };
55 
decode(unsigned * state,unsigned * codep,unsigned byte)56 static unsigned inline decode(unsigned* state, unsigned* codep, unsigned byte) {
57     unsigned type = utf8d[byte];
58 
59     *codep = (*state != UTF8_ACCEPT) ?
60         (byte & 0x3fu) | (*codep << 6) :
61     (0xff >> type) & (byte);
62 
63     *state = utf8d[256 + *state + type];
64     return *state;
65 }
66 
IsUTF8(unsigned char * s)67 static bool IsUTF8(unsigned char* s) {
68     unsigned codepoint, state = 0;
69 
70     while (*s)
71         decode(&state, &codepoint, *s++);
72 
73     return state == UTF8_ACCEPT;
74 }
75 
TEST_F(Misc,Hoehrmann_IsUTF8)76 TEST_F(Misc, Hoehrmann_IsUTF8) {
77     for (size_t i = 0; i < kTrialCount; i++) {
78         EXPECT_TRUE(IsUTF8((unsigned char*)json_));
79     }
80 }
81 
82 ////////////////////////////////////////////////////////////////////////////////
83 // CountDecimalDigit: Count number of decimal places
84 
CountDecimalDigit_naive(unsigned n)85 inline unsigned CountDecimalDigit_naive(unsigned n) {
86     unsigned count = 1;
87     while (n >= 10) {
88         n /= 10;
89         count++;
90     }
91     return count;
92 }
93 
CountDecimalDigit_enroll4(unsigned n)94 inline unsigned CountDecimalDigit_enroll4(unsigned n) {
95     unsigned count = 1;
96     while (n >= 10000) {
97         n /= 10000u;
98         count += 4;
99     }
100     if (n < 10) return count;
101     if (n < 100) return count + 1;
102     if (n < 1000) return count + 2;
103     return count + 3;
104 }
105 
CountDecimalDigit64_enroll4(uint64_t n)106 inline unsigned CountDecimalDigit64_enroll4(uint64_t n) {
107     unsigned count = 1;
108     while (n >= 10000) {
109         n /= 10000u;
110         count += 4;
111     }
112     if (n < 10) return count;
113     if (n < 100) return count + 1;
114     if (n < 1000) return count + 2;
115     return count + 3;
116 }
117 
CountDecimalDigit_fast(unsigned n)118 inline unsigned CountDecimalDigit_fast(unsigned n) {
119     static const uint32_t powers_of_10[] = {
120         0,
121         10,
122         100,
123         1000,
124         10000,
125         100000,
126         1000000,
127         10000000,
128         100000000,
129         1000000000
130     };
131 
132 #if defined(_M_IX86) || defined(_M_X64)
133     unsigned long i = 0;
134     _BitScanReverse(&i, n | 1);
135     uint32_t t = (i + 1) * 1233 >> 12;
136 #elif defined(__GNUC__)
137     uint32_t t = (32 - __builtin_clz(n | 1)) * 1233 >> 12;
138 #else
139 #error
140 #endif
141     return t - (n < powers_of_10[t]) + 1;
142 }
143 
CountDecimalDigit64_fast(uint64_t n)144 inline unsigned CountDecimalDigit64_fast(uint64_t n) {
145     static const uint64_t powers_of_10[] = {
146         0,
147         10,
148         100,
149         1000,
150         10000,
151         100000,
152         1000000,
153         10000000,
154         100000000,
155         1000000000,
156         10000000000,
157         100000000000,
158         1000000000000,
159         10000000000000,
160         100000000000000,
161         1000000000000000,
162         10000000000000000,
163         100000000000000000,
164         1000000000000000000,
165         10000000000000000000U
166     };
167 
168 #if defined(_M_IX86)
169     uint64_t m = n | 1;
170     unsigned long i = 0;
171     if (_BitScanReverse(&i, m >> 32))
172         i += 32;
173     else
174         _BitScanReverse(&i, m & 0xFFFFFFFF);
175     uint32_t t = (i + 1) * 1233 >> 12;
176 #elif defined(_M_X64)
177     unsigned long i = 0;
178     _BitScanReverse64(&i, n | 1);
179     uint32_t t = (i + 1) * 1233 >> 12;
180 #elif defined(__GNUC__)
181     uint32_t t = (64 - __builtin_clzll(n | 1)) * 1233 >> 12;
182 #else
183 #error
184 #endif
185 
186     return t - (n < powers_of_10[t]) + 1;
187 }
188 
189 #if 0
190 // Exhaustive, very slow
191 TEST_F(Misc, CountDecimalDigit_Verify) {
192     unsigned i = 0;
193     do {
194         if (i % (65536 * 256) == 0)
195             printf("%u\n", i);
196         ASSERT_EQ(CountDecimalDigit_enroll4(i), CountDecimalDigit_fast(i));
197         i++;
198     } while (i != 0);
199 }
200 
201 static const unsigned kDigits10Trial = 1000000000u;
202 TEST_F(Misc, CountDecimalDigit_naive) {
203     unsigned sum = 0;
204     for (unsigned i = 0; i < kDigits10Trial; i++)
205         sum += CountDecimalDigit_naive(i);
206     printf("%u\n", sum);
207 }
208 
209 TEST_F(Misc, CountDecimalDigit_enroll4) {
210     unsigned sum = 0;
211     for (unsigned i = 0; i < kDigits10Trial; i++)
212         sum += CountDecimalDigit_enroll4(i);
213     printf("%u\n", sum);
214 }
215 
216 TEST_F(Misc, CountDecimalDigit_fast) {
217     unsigned sum = 0;
218     for (unsigned i = 0; i < kDigits10Trial; i++)
219         sum += CountDecimalDigit_fast(i);
220     printf("%u\n", sum);
221 }
222 #endif
223 
TEST_F(Misc,CountDecimalDigit64_VerifyFast)224 TEST_F(Misc, CountDecimalDigit64_VerifyFast) {
225     uint64_t i = 1, j;
226     do {
227         //printf("%" PRIu64 "\n", i);
228         ASSERT_EQ(CountDecimalDigit64_enroll4(i), CountDecimalDigit64_fast(i));
229         j = i;
230         i *= 3;
231     } while (j < i);
232 }
233 
234 ////////////////////////////////////////////////////////////////////////////////
235 // integer-to-string conversion
236 
237 // https://gist.github.com/anonymous/7179097
238 static const int randval[] ={
239      936116,  369532,  453755,  -72860,  209713,  268347,  435278, -360266, -416287, -182064,
240     -644712,  944969,  640463, -366588,  471577,  -69401, -744294, -505829,  923883,  831785,
241     -601136, -636767, -437054,  591718,  100758,  231907, -719038,  973540, -605220,  506659,
242     -871653,  462533,  764843, -919138,  404305, -630931, -288711, -751454, -173726, -718208,
243      432689, -281157,  360737,  659827,   19174, -376450,  769984, -858198,  439127,  734703,
244     -683426,       7,  386135,  186997, -643900, -744422, -604708, -629545,   42313, -933592,
245     -635566,  182308,  439024, -367219,  -73924, -516649,  421935, -470515,  413507,  -78952,
246     -427917, -561158,  737176,   94538,  572322,  405217,  709266, -357278, -908099, -425447,
247      601119,  750712, -862285, -177869,  900102,  384877,  157859, -641680,  503738, -702558,
248      278225,  463290,  268378, -212840,  580090,  347346, -473985, -950968, -114547, -839893,
249     -738032, -789424,  409540,  493495,  432099,  119755,  905004, -174834,  338266,  234298,
250       74641, -965136, -754593,  685273,  466924,  920560,  385062,  796402,  -67229,  994864,
251      376974,  299869, -647540, -128724,  469890, -163167, -547803, -743363,  486463, -621028,
252      612288,   27459, -514224,  126342,  -66612,  803409, -777155, -336453, -284002,  472451,
253      342390, -163630,  908356, -456147, -825607,  268092, -974715,  287227,  227890, -524101,
254      616370, -782456,  922098, -624001, -813690,  171605, -192962,  796151,  707183,  -95696,
255      -23163, -721260,  508892,  430715,  791331,  482048, -996102,  863274,  275406,   -8279,
256     -556239, -902076,  268647, -818565,  260069, -798232, -172924, -566311, -806503, -885992,
257      813969,  -78468,  956632,  304288,  494867, -508784,  381751,  151264,  762953,   76352,
258      594902,  375424,  271700, -743062,  390176,  924237,  772574,  676610,  435752, -153847,
259        3959, -971937, -294181, -538049, -344620, -170136,   19120, -703157,  868152, -657961,
260     -818631,  219015, -872729, -940001, -956570,  880727, -345910,  942913, -942271, -788115,
261      225294,  701108, -517736, -416071,  281940,  488730,  942698,  711494,  838382, -892302,
262     -533028,  103052,  528823,  901515,  949577,  159364,  718227, -241814, -733661, -462928,
263     -495829,  165170,  513580, -629188, -509571, -459083,  198437,   77198, -644612,  811276,
264     -422298, -860842,  -52584,  920369,  686424, -530667, -243476,   49763,  345866, -411960,
265     -114863,  470810, -302860,  683007, -509080,       2, -174981, -772163,  -48697,  447770,
266     -268246,  213268,  269215,   78810, -236340, -639140, -864323,  505113, -986569, -325215,
267      541859,  163070, -819998, -645161, -583336,  573414,  696417, -132375,       3, -294501,
268      320435,  682591,  840008,  351740,  426951,  609354,  898154, -943254,  227321, -859793,
269     -727993,   44137, -497965, -782239,   14955, -746080, -243366,    9837, -233083,  606507,
270     -995864, -615287, -994307,  602715,  770771, -315040,  610860,  446102, -307120,  710728,
271     -590392, -230474, -762625, -637525,  134963, -202700, -766902, -985541,  218163,  682009,
272      926051,  525156,  -61195,  403211, -810098,  245539, -431733,  179998, -806533,  745943,
273      447597,  131973, -187130,  826019,  286107, -937230, -577419,   20254,  681802, -340500,
274      323080,  266283, -667617,  309656,  416386,  611863,  759991, -534257,  523112, -634892,
275     -169913, -204905, -909867, -882185, -944908,  741811, -717675,  967007, -317396,  407230,
276     -412805,  792905,  994873,  744793, -456797,  713493,  355232,  116900, -945199,  880539,
277      342505, -580824, -262273,  982968, -349497, -735488,  311767, -455191,  570918,  389734,
278     -958386,   10262,  -99267,  155481,  304210,  204724,  704367, -144893, -233664, -671441,
279      896849,  408613,  762236,  322697,  981321,  688476,   13663, -970704, -379507,  896412,
280      977084,  348869,  875948,  341348,  318710,  512081,    6163,  669044,  833295,  811883,
281      708756, -802534, -536057,  608413, -389625, -694603,  541106, -110037,  720322, -540581,
282      645420,   32980,   62442,  510157, -981870,  -87093, -325960, -500494, -718291,  -67889,
283      991501,  374804,  769026, -978869,  294747,  714623,  413327, -199164,  671368,  804789,
284     -362507,  798196, -170790, -568895, -869379,   62020, -316693, -837793,  644994,  -39341,
285     -417504, -243068, -957756,   99072,  622234, -739992,  225668,    8863, -505910,   82483,
286     -559244,  241572,    1315,  -36175,  -54990,  376813,     -11,  162647, -688204, -486163,
287      -54934, -197470,  744223, -762707,  732540,  996618,  351561, -445933, -898491,  486531,
288      456151,   15276,  290186, -817110,  -52995,  313046, -452533,  -96267,   94470, -500176,
289     -818026, -398071, -810548, -143325, -819741,    1338, -897676, -101577, -855445,   37309,
290      285742,  953804, -777927, -926962, -811217, -936744, -952245, -802300, -490188, -964953,
291     -552279,  329142, -570048, -505756,  682898, -381089,  -14352,  175138,  152390, -582268,
292     -485137,  717035,  805329,  239572, -730409,  209643, -184403, -385864,  675086,  819648,
293      629058, -527109, -488666, -171981,  532788,  552441,  174666,  984921,  766514,  758787,
294      716309,  338801, -978004, -412163,  876079, -734212,  789557, -160491, -522719,   56644,
295        -991, -286038,  -53983,  663740,  809812,  919889, -717502, -137704,  220511,  184396,
296     -825740, -588447,  430870,  124309,  135956,  558662, -307087, -788055, -451328,  812260,
297      931601,  324347, -482989, -117858, -278861,  189068, -172774,  929057,  293787,  198161,
298     -342386,  -47173,  906555, -759955,  -12779,  777604,  -97869,  899320,  927486,  -25284,
299     -848550,  259450, -485856,  -17820,      88,  171400,  235492, -326783, -340793,  886886,
300      112428, -246280,    5979,  648444, -114982,  991013,  -56489,   -9497,  419706,  632820,
301     -341664,  393926, -848977,  -22538,  257307,  773731, -905319,  491153,  734883, -868212,
302     -951053,  644458, -580758,  764735,  584316,  297077,   28852, -397710, -953669,  201772,
303      879050, -198237, -588468,  448102, -116837,  770007, -231812,  642906, -582166, -885828,
304           9,  305082, -996577,  303559,   75008, -772956, -447960,  599825, -295552,  870739,
305     -386278, -950300,  485359, -457081,  629461, -850276,  550496, -451755, -620841,  -11766,
306     -950137,  832337,   28711, -273398, -507197,   91921, -271360, -705991, -753220, -388968,
307      967945,  340434, -320883, -662793, -554617, -574568,  477946,   -6148, -129519,  689217,
308      920020, -656315, -974523, -212525,   80921, -612532,  645096,  545655,  655713, -591631,
309     -307385, -816688, -618823, -113713,  526430,  673063,  735916, -809095, -850417,  639004,
310      432281, -388185,  270708,  860146,  -39902, -786157, -258180, -246169, -966720, -264957,
311      548072, -306010,  -57367, -635665,  933824,   70553, -989936, -488741,   72411, -452509,
312      529831,  956277,  449019, -577850, -360986, -803418,   48833,  296073,  203430,  609591,
313      715483,  470964,  658106, -718254,  -96424,  790163,  334739,  181070, -373578,       5,
314     -435088,  329841,  330939, -256602,  394355,  912412,  231910,  927278, -661933,  788539,
315     -769664, -893274,  -96856,  298205,  901043, -608122, -527430,  183618, -553963,  -35246,
316     -393924,  948832, -483198,  594501,   35460, -407007,   93494, -336881, -634072,  984205,
317     -812161,  944664,  -31062,  753872,  823933,  -69566,   50445,  290147,   85134,   34706,
318      551902,  405202, -991246,  -84642,  154341,  316432, -695101, -651588,   -5030,  137564,
319     -294665,  332541,  528307,  -90572, -344923,  523766, -758498, -968047,  339028,  494578,
320      593129, -725773,   31834, -718406, -208638,  159665,   -2043,  673344, -442767,   75816,
321      755442,  769257, -158730, -410272,  691688,  589550, -878398, -184121,  460679,  346312,
322      294163, -544602,  653308,  254167, -276979,   52073, -892684,  887653,  -41222,  983065,
323      -68258, -408799,  -99069, -674069, -863635,  -32890,  622757, -743862,   40872,   -4837,
324     -967228,  522370, -903951, -818669,  524459,  514702,  925801,   20007, -299229,  579348,
325      626021,  430089,  348139, -562692, -607728, -130606, -928451, -424793, -458647, -448892,
326     -312230,  143337,  109746,  880042, -339658, -785614,  938995,  540916,  118429,  661351,
327     -402967,  404729,  -40918, -976535,  743230,  713110,  440182, -381314, -499252,   74613,
328      193652,  912717,  491323,  583633,  324691,  459397,  281253,  195540,   -2764, -888651,
329      892449,  132663, -478373, -430002, -314551,  527826,  247165,  557966,  554778,  481531,
330     -946634,  431685, -769059, -348371,  174046,  184597, -354867,  584422,  227390, -850397,
331     -542924, -849093, -737769,  325359,  736314,  269101,  767940,  674809,   81413, -447458,
332      445076,  189072,  906218,  502688, -718476, -863827, -731381,  100660,  623249,  710008,
333      572060,  922203,  685740,   55096,  263394, -243695, -353910, -516788,  388471,  455165,
334      844103, -643772,  363976,  268875, -899450,  104470,  104029, -238874, -274659,  732969,
335     -676443,  953291, -916289, -861849, -242344,  958083, -479593, -970395,  799831,  277841,
336     -243236, -283462, -201510,  166263, -259105, -575706,  878926,  891064,  895297,  655262,
337      -34807, -809833,  -89281,  342585,  554920,       1,  902141, -333425,  139703,  852318,
338     -618438,  329498, -932596, -692836, -513372,  733656, -523411,   85779,  500478, -682697,
339     -502836,  138776,  156341, -420037, -557964, -556378,  710993,  -50383, -877159,  916334,
340      132996,  583516, -603392, -111615,  -12288, -780214,  476780,  123327,  137607,  519956,
341      745837,   17358, -158581,  -53490
342 };
343 static const size_t randvalCount = sizeof(randval) / sizeof(randval[0]);
344 static const size_t kItoaTrialCount = 10000;
345 
346 static const char digits[201] =
347 "0001020304050607080910111213141516171819"
348 "2021222324252627282930313233343536373839"
349 "4041424344454647484950515253545556575859"
350 "6061626364656667686970717273747576777879"
351 "8081828384858687888990919293949596979899";
352 
353 // Prevent code being optimized out
354 //#define OUTPUT_LENGTH(length) printf("", length)
355 #define OUTPUT_LENGTH(length) printf("%u\n", (unsigned)length)
356 
357 template<typename OutputStream>
358 class Writer1 {
359 public:
Writer1()360     Writer1() : os_() {}
Writer1(OutputStream & os)361     Writer1(OutputStream& os) : os_(&os) {}
362 
Reset(OutputStream & os)363     void Reset(OutputStream& os) {
364         os_ = &os;
365     }
366 
WriteInt(int i)367     bool WriteInt(int i) {
368         if (i < 0) {
369             os_->Put('-');
370             i = -i;
371         }
372         return WriteUint((unsigned)i);
373     }
374 
WriteUint(unsigned u)375     bool WriteUint(unsigned u) {
376         char buffer[10];
377         char *p = buffer;
378         do {
379             *p++ = char(u % 10) + '0';
380             u /= 10;
381         } while (u > 0);
382 
383         do {
384             --p;
385             os_->Put(*p);
386         } while (p != buffer);
387         return true;
388     }
389 
WriteInt64(int64_t i64)390     bool WriteInt64(int64_t i64) {
391         if (i64 < 0) {
392             os_->Put('-');
393             i64 = -i64;
394         }
395         WriteUint64((uint64_t)i64);
396         return true;
397     }
398 
WriteUint64(uint64_t u64)399     bool WriteUint64(uint64_t u64) {
400         char buffer[20];
401         char *p = buffer;
402         do {
403             *p++ = char(u64 % 10) + '0';
404             u64 /= 10;
405         } while (u64 > 0);
406 
407         do {
408             --p;
409             os_->Put(*p);
410         } while (p != buffer);
411         return true;
412     }
413 
414 private:
415     OutputStream* os_;
416 };
417 
418 template<>
WriteUint(unsigned u)419 bool Writer1<rapidjson::StringBuffer>::WriteUint(unsigned u) {
420     char buffer[10];
421     char* p = buffer;
422     do {
423         *p++ = char(u % 10) + '0';
424         u /= 10;
425     } while (u > 0);
426 
427     char* d = os_->Push(p - buffer);
428     do {
429         --p;
430         *d++ = *p;
431     } while (p != buffer);
432     return true;
433 }
434 
435 // Using digits LUT to reduce divsion/modulo
436 template<typename OutputStream>
437 class Writer2 {
438 public:
Writer2()439     Writer2() : os_() {}
Writer2(OutputStream & os)440     Writer2(OutputStream& os) : os_(&os) {}
441 
Reset(OutputStream & os)442     void Reset(OutputStream& os) {
443         os_ = &os;
444     }
445 
WriteInt(int i)446     bool WriteInt(int i) {
447         if (i < 0) {
448             os_->Put('-');
449             i = -i;
450         }
451         return WriteUint((unsigned)i);
452     }
453 
WriteUint(unsigned u)454     bool WriteUint(unsigned u) {
455         char buffer[10];
456         char* p = buffer;
457         while (u >= 100) {
458             const unsigned i = (u % 100) << 1;
459             u /= 100;
460             *p++ = digits[i + 1];
461             *p++ = digits[i];
462         }
463         if (u < 10)
464             *p++ = char(u) + '0';
465         else {
466             const unsigned i = u << 1;
467             *p++ = digits[i + 1];
468             *p++ = digits[i];
469         }
470 
471         do {
472             --p;
473             os_->Put(*p);
474         } while (p != buffer);
475         return true;
476     }
477 
WriteInt64(int64_t i64)478     bool WriteInt64(int64_t i64) {
479         if (i64 < 0) {
480             os_->Put('-');
481             i64 = -i64;
482         }
483         WriteUint64((uint64_t)i64);
484         return true;
485     }
486 
WriteUint64(uint64_t u64)487     bool WriteUint64(uint64_t u64) {
488         char buffer[20];
489         char* p = buffer;
490         while (u64 >= 100) {
491             const unsigned i = static_cast<unsigned>(u64 % 100) << 1;
492             u64 /= 100;
493             *p++ = digits[i + 1];
494             *p++ = digits[i];
495         }
496         if (u64 < 10)
497             *p++ = char(u64) + '0';
498         else {
499             const unsigned i = static_cast<unsigned>(u64) << 1;
500             *p++ = digits[i + 1];
501             *p++ = digits[i];
502         }
503 
504         do {
505             --p;
506             os_->Put(*p);
507         } while (p != buffer);
508         return true;
509     }
510 
511 private:
512     OutputStream* os_;
513 };
514 
515 // First pass to count digits
516 template<typename OutputStream>
517 class Writer3 {
518 public:
Writer3()519     Writer3() : os_() {}
Writer3(OutputStream & os)520     Writer3(OutputStream& os) : os_(&os) {}
521 
Reset(OutputStream & os)522     void Reset(OutputStream& os) {
523         os_ = &os;
524     }
525 
WriteInt(int i)526     bool WriteInt(int i) {
527         if (i < 0) {
528             os_->Put('-');
529             i = -i;
530         }
531         return WriteUint((unsigned)i);
532     }
533 
WriteUint(unsigned u)534     bool WriteUint(unsigned u) {
535         char buffer[10];
536         char *p = buffer;
537         do {
538             *p++ = char(u % 10) + '0';
539             u /= 10;
540         } while (u > 0);
541 
542         do {
543             --p;
544             os_->Put(*p);
545         } while (p != buffer);
546         return true;
547     }
548 
WriteInt64(int64_t i64)549     bool WriteInt64(int64_t i64) {
550         if (i64 < 0) {
551             os_->Put('-');
552             i64 = -i64;
553         }
554         WriteUint64((uint64_t)i64);
555         return true;
556     }
557 
WriteUint64(uint64_t u64)558     bool WriteUint64(uint64_t u64) {
559         char buffer[20];
560         char *p = buffer;
561         do {
562             *p++ = char(u64 % 10) + '0';
563             u64 /= 10;
564         } while (u64 > 0);
565 
566         do {
567             --p;
568             os_->Put(*p);
569         } while (p != buffer);
570         return true;
571     }
572 
573 private:
WriteUintReverse(char * d,unsigned u)574     void WriteUintReverse(char* d, unsigned u) {
575         do {
576             *--d = char(u % 10) + '0';
577             u /= 10;
578         } while (u > 0);
579     }
580 
WriteUint64Reverse(char * d,uint64_t u)581     void WriteUint64Reverse(char* d, uint64_t u) {
582         do {
583             *--d = char(u % 10) + '0';
584             u /= 10;
585         } while (u > 0);
586     }
587 
588     OutputStream* os_;
589 };
590 
591 template<>
WriteUint(unsigned u)592 inline bool Writer3<rapidjson::StringBuffer>::WriteUint(unsigned u) {
593     unsigned digit = CountDecimalDigit_fast(u);
594     WriteUintReverse(os_->Push(digit) + digit, u);
595     return true;
596 }
597 
598 template<>
WriteUint(unsigned u)599 inline bool Writer3<rapidjson::InsituStringStream>::WriteUint(unsigned u) {
600     unsigned digit = CountDecimalDigit_fast(u);
601     WriteUintReverse(os_->Push(digit) + digit, u);
602     return true;
603 }
604 
605 template<>
WriteUint64(uint64_t u)606 inline bool Writer3<rapidjson::StringBuffer>::WriteUint64(uint64_t u) {
607     unsigned digit = CountDecimalDigit64_fast(u);
608     WriteUint64Reverse(os_->Push(digit) + digit, u);
609     return true;
610 }
611 
612 template<>
WriteUint64(uint64_t u)613 inline bool Writer3<rapidjson::InsituStringStream>::WriteUint64(uint64_t u) {
614     unsigned digit = CountDecimalDigit64_fast(u);
615     WriteUint64Reverse(os_->Push(digit) + digit, u);
616     return true;
617 }
618 
619 // Using digits LUT to reduce divsion/modulo, two passes
620 template<typename OutputStream>
621 class Writer4 {
622 public:
Writer4()623     Writer4() : os_() {}
Writer4(OutputStream & os)624     Writer4(OutputStream& os) : os_(&os) {}
625 
Reset(OutputStream & os)626     void Reset(OutputStream& os) {
627         os_ = &os;
628     }
629 
WriteInt(int i)630     bool WriteInt(int i) {
631         if (i < 0) {
632             os_->Put('-');
633             i = -i;
634         }
635         return WriteUint((unsigned)i);
636     }
637 
WriteUint(unsigned u)638     bool WriteUint(unsigned u) {
639         char buffer[10];
640         char* p = buffer;
641         while (u >= 100) {
642             const unsigned i = (u % 100) << 1;
643             u /= 100;
644             *p++ = digits[i + 1];
645             *p++ = digits[i];
646         }
647         if (u < 10)
648             *p++ = char(u) + '0';
649         else {
650             const unsigned i = u << 1;
651             *p++ = digits[i + 1];
652             *p++ = digits[i];
653         }
654 
655         do {
656             --p;
657             os_->Put(*p);
658         } while (p != buffer);
659         return true;
660     }
661 
WriteInt64(int64_t i64)662     bool WriteInt64(int64_t i64) {
663         if (i64 < 0) {
664             os_->Put('-');
665             i64 = -i64;
666         }
667         WriteUint64((uint64_t)i64);
668         return true;
669     }
670 
WriteUint64(uint64_t u64)671     bool WriteUint64(uint64_t u64) {
672         char buffer[20];
673         char* p = buffer;
674         while (u64 >= 100) {
675             const unsigned i = static_cast<unsigned>(u64 % 100) << 1;
676             u64 /= 100;
677             *p++ = digits[i + 1];
678             *p++ = digits[i];
679         }
680         if (u64 < 10)
681             *p++ = char(u64) + '0';
682         else {
683             const unsigned i = static_cast<unsigned>(u64) << 1;
684             *p++ = digits[i + 1];
685             *p++ = digits[i];
686         }
687 
688         do {
689             --p;
690             os_->Put(*p);
691         } while (p != buffer);
692         return true;
693     }
694 
695 private:
WriteUintReverse(char * d,unsigned u)696     void WriteUintReverse(char* d, unsigned u) {
697         while (u >= 100) {
698             const unsigned i = (u % 100) << 1;
699             u /= 100;
700             *--d = digits[i + 1];
701             *--d = digits[i];
702         }
703         if (u < 10) {
704             *--d = char(u) + '0';
705         }
706         else {
707             const unsigned i = u << 1;
708             *--d = digits[i + 1];
709             *--d = digits[i];
710         }
711     }
712 
WriteUint64Reverse(char * d,uint64_t u)713     void WriteUint64Reverse(char* d, uint64_t u) {
714         while (u >= 100) {
715             const unsigned i = (u % 100) << 1;
716             u /= 100;
717             *--d = digits[i + 1];
718             *--d = digits[i];
719         }
720         if (u < 10) {
721             *--d = char(u) + '0';
722         }
723         else {
724             const unsigned i = u << 1;
725             *--d = digits[i + 1];
726             *--d = digits[i];
727         }
728     }
729 
730     OutputStream* os_;
731 };
732 
733 template<>
WriteUint(unsigned u)734 inline bool Writer4<rapidjson::StringBuffer>::WriteUint(unsigned u) {
735     unsigned digit = CountDecimalDigit_fast(u);
736     WriteUintReverse(os_->Push(digit) + digit, u);
737     return true;
738 }
739 
740 template<>
WriteUint(unsigned u)741 inline bool Writer4<rapidjson::InsituStringStream>::WriteUint(unsigned u) {
742     unsigned digit = CountDecimalDigit_fast(u);
743     WriteUintReverse(os_->Push(digit) + digit, u);
744     return true;
745 }
746 
747 template<>
WriteUint64(uint64_t u)748 inline bool Writer4<rapidjson::StringBuffer>::WriteUint64(uint64_t u) {
749     unsigned digit = CountDecimalDigit64_fast(u);
750     WriteUint64Reverse(os_->Push(digit) + digit, u);
751     return true;
752 }
753 
754 template<>
WriteUint64(uint64_t u)755 inline bool Writer4<rapidjson::InsituStringStream>::WriteUint64(uint64_t u) {
756     unsigned digit = CountDecimalDigit64_fast(u);
757     WriteUint64Reverse(os_->Push(digit) + digit, u);
758     return true;
759 }
760 
761 template <typename Writer>
itoa_Writer_StringBufferVerify()762 void itoa_Writer_StringBufferVerify() {
763     rapidjson::StringBuffer sb;
764     Writer writer(sb);
765     for (size_t j = 0; j < randvalCount; j++) {
766         char buffer[32];
767         sprintf(buffer, "%d", randval[j]);
768         writer.WriteInt(randval[j]);
769         ASSERT_STREQ(buffer, sb.GetString());
770         sb.Clear();
771     }
772 }
773 
774 template <typename Writer>
itoa_Writer_InsituStringStreamVerify()775 void itoa_Writer_InsituStringStreamVerify() {
776     Writer writer;
777     for (size_t j = 0; j < randvalCount; j++) {
778         char buffer[32];
779         sprintf(buffer, "%d", randval[j]);
780         char buffer2[32];
781         rapidjson::InsituStringStream ss(buffer2);
782         writer.Reset(ss);
783         char* begin = ss.PutBegin();
784         writer.WriteInt(randval[j]);
785         ss.Put('\0');
786         ss.PutEnd(begin);
787         ASSERT_STREQ(buffer, buffer2);
788     }
789 }
790 
791 template <typename Writer>
itoa_Writer_StringBuffer()792 void itoa_Writer_StringBuffer() {
793     size_t length = 0;
794 
795     rapidjson::StringBuffer sb;
796     Writer writer(sb);
797 
798     for (size_t i = 0; i < kItoaTrialCount; i++) {
799         for (size_t j = 0; j < randvalCount; j++) {
800             writer.WriteInt(randval[j]);
801             length += sb.GetSize();
802             sb.Clear();
803         }
804     }
805     OUTPUT_LENGTH(length);
806 }
807 
808 template <typename Writer>
itoa_Writer_InsituStringStream()809 void itoa_Writer_InsituStringStream() {
810     size_t length = 0;
811 
812     char buffer[32];
813     Writer writer;
814     for (size_t i = 0; i < kItoaTrialCount; i++) {
815         for (size_t j = 0; j < randvalCount; j++) {
816             rapidjson::InsituStringStream ss(buffer);
817             writer.Reset(ss);
818             char* begin = ss.PutBegin();
819             writer.WriteInt(randval[j]);
820             length += ss.PutEnd(begin);
821         }
822     }
823     OUTPUT_LENGTH(length);
824 };
825 
826 template <typename Writer>
itoa64_Writer_StringBufferVerify()827 void itoa64_Writer_StringBufferVerify() {
828     rapidjson::StringBuffer sb;
829     Writer writer(sb);
830     for (size_t j = 0; j < randvalCount; j++) {
831         char buffer[32];
832         int64_t x = randval[j] * randval[j];
833         sprintf(buffer, "%" PRIi64, x);
834         writer.WriteInt64(x);
835         ASSERT_STREQ(buffer, sb.GetString());
836         sb.Clear();
837     }
838 }
839 
840 template <typename Writer>
itoa64_Writer_InsituStringStreamVerify()841 void itoa64_Writer_InsituStringStreamVerify() {
842     Writer writer;
843     for (size_t j = 0; j < randvalCount; j++) {
844         char buffer[32];
845         int64_t x = randval[j] * randval[j];
846         sprintf(buffer, "%" PRIi64, x);
847         char buffer2[32];
848         rapidjson::InsituStringStream ss(buffer2);
849         writer.Reset(ss);
850         char* begin = ss.PutBegin();
851         writer.WriteInt64(x);
852         ss.Put('\0');
853         ss.PutEnd(begin);
854         ASSERT_STREQ(buffer, buffer2);
855     }
856 }
857 
858 template <typename Writer>
itoa64_Writer_StringBuffer()859 void itoa64_Writer_StringBuffer() {
860     size_t length = 0;
861 
862     rapidjson::StringBuffer sb;
863     Writer writer(sb);
864 
865     for (size_t i = 0; i < kItoaTrialCount; i++) {
866         for (size_t j = 0; j < randvalCount; j++) {
867             writer.WriteInt64(randval[j] * randval[j]);
868             length += sb.GetSize();
869             sb.Clear();
870         }
871     }
872     OUTPUT_LENGTH(length);
873 }
874 
875 template <typename Writer>
itoa64_Writer_InsituStringStream()876 void itoa64_Writer_InsituStringStream() {
877     size_t length = 0;
878 
879     char buffer[32];
880     Writer writer;
881     for (size_t i = 0; i < kItoaTrialCount; i++) {
882         for (size_t j = 0; j < randvalCount; j++) {
883             rapidjson::InsituStringStream ss(buffer);
884             writer.Reset(ss);
885             char* begin = ss.PutBegin();
886             writer.WriteInt64(randval[j] * randval[j]);
887             length += ss.PutEnd(begin);
888         }
889     }
890     OUTPUT_LENGTH(length);
891 };
892 
893 // Full specialization for InsituStringStream to prevent memory copying
894 // (normally we will not use InsituStringStream for writing, just for testing)
895 
896 namespace rapidjson {
897 
898 template<>
WriteInt(int i)899 bool rapidjson::Writer<InsituStringStream>::WriteInt(int i) {
900     char *buffer = os_->Push(11);
901     const char* end = internal::i32toa(i, buffer);
902     os_->Pop(11 - (end - buffer));
903     return true;
904 }
905 
906 template<>
WriteUint(unsigned u)907 bool Writer<InsituStringStream>::WriteUint(unsigned u) {
908     char *buffer = os_->Push(10);
909     const char* end = internal::u32toa(u, buffer);
910     os_->Pop(10 - (end - buffer));
911     return true;
912 }
913 
914 template<>
WriteInt64(int64_t i64)915 bool Writer<InsituStringStream>::WriteInt64(int64_t i64) {
916     char *buffer = os_->Push(21);
917     const char* end = internal::i64toa(i64, buffer);
918     os_->Pop(21 - (end - buffer));
919     return true;
920 }
921 
922 template<>
WriteUint64(uint64_t u)923 bool Writer<InsituStringStream>::WriteUint64(uint64_t u) {
924     char *buffer = os_->Push(20);
925     const char* end = internal::u64toa(u, buffer);
926     os_->Pop(20 - (end - buffer));
927     return true;
928 }
929 
930 } // namespace rapidjson
931 
TEST_F(Misc,itoa_Writer_StringBufferVerify)932 TEST_F(Misc, itoa_Writer_StringBufferVerify) { itoa_Writer_StringBufferVerify<rapidjson::Writer<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa_Writer1_StringBufferVerify)933 TEST_F(Misc, itoa_Writer1_StringBufferVerify) { itoa_Writer_StringBufferVerify<Writer1<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa_Writer2_StringBufferVerify)934 TEST_F(Misc, itoa_Writer2_StringBufferVerify) { itoa_Writer_StringBufferVerify<Writer2<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa_Writer3_StringBufferVerify)935 TEST_F(Misc, itoa_Writer3_StringBufferVerify) { itoa_Writer_StringBufferVerify<Writer3<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa_Writer4_StringBufferVerify)936 TEST_F(Misc, itoa_Writer4_StringBufferVerify) { itoa_Writer_StringBufferVerify<Writer4<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa_Writer_InsituStringStreamVerify)937 TEST_F(Misc, itoa_Writer_InsituStringStreamVerify) { itoa_Writer_InsituStringStreamVerify<rapidjson::Writer<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa_Writer1_InsituStringStreamVerify)938 TEST_F(Misc, itoa_Writer1_InsituStringStreamVerify) { itoa_Writer_InsituStringStreamVerify<Writer1<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa_Writer2_InsituStringStreamVerify)939 TEST_F(Misc, itoa_Writer2_InsituStringStreamVerify) { itoa_Writer_InsituStringStreamVerify<Writer2<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa_Writer3_InsituStringStreamVerify)940 TEST_F(Misc, itoa_Writer3_InsituStringStreamVerify) { itoa_Writer_InsituStringStreamVerify<Writer3<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa_Writer4_InsituStringStreamVerify)941 TEST_F(Misc, itoa_Writer4_InsituStringStreamVerify) { itoa_Writer_InsituStringStreamVerify<Writer4<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa_Writer_StringBuffer)942 TEST_F(Misc, itoa_Writer_StringBuffer) { itoa_Writer_StringBuffer<rapidjson::Writer<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa_Writer1_StringBuffer)943 TEST_F(Misc, itoa_Writer1_StringBuffer) { itoa_Writer_StringBuffer<Writer1<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa_Writer2_StringBuffer)944 TEST_F(Misc, itoa_Writer2_StringBuffer) { itoa_Writer_StringBuffer<Writer2<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa_Writer3_StringBuffer)945 TEST_F(Misc, itoa_Writer3_StringBuffer) { itoa_Writer_StringBuffer<Writer3<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa_Writer4_StringBuffer)946 TEST_F(Misc, itoa_Writer4_StringBuffer) { itoa_Writer_StringBuffer<Writer4<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa_Writer_InsituStringStream)947 TEST_F(Misc, itoa_Writer_InsituStringStream) { itoa_Writer_InsituStringStream<rapidjson::Writer<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa_Writer1_InsituStringStream)948 TEST_F(Misc, itoa_Writer1_InsituStringStream) { itoa_Writer_InsituStringStream<Writer1<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa_Writer2_InsituStringStream)949 TEST_F(Misc, itoa_Writer2_InsituStringStream) { itoa_Writer_InsituStringStream<Writer2<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa_Writer3_InsituStringStream)950 TEST_F(Misc, itoa_Writer3_InsituStringStream) { itoa_Writer_InsituStringStream<Writer3<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa_Writer4_InsituStringStream)951 TEST_F(Misc, itoa_Writer4_InsituStringStream) { itoa_Writer_InsituStringStream<Writer4<rapidjson::InsituStringStream> >(); }
952 
TEST_F(Misc,itoa64_Writer_StringBufferVerify)953 TEST_F(Misc, itoa64_Writer_StringBufferVerify) { itoa64_Writer_StringBufferVerify<rapidjson::Writer<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa64_Writer1_StringBufferVerify)954 TEST_F(Misc, itoa64_Writer1_StringBufferVerify) { itoa64_Writer_StringBufferVerify<Writer1<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa64_Writer2_StringBufferVerify)955 TEST_F(Misc, itoa64_Writer2_StringBufferVerify) { itoa64_Writer_StringBufferVerify<Writer2<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa64_Writer3_StringBufferVerify)956 TEST_F(Misc, itoa64_Writer3_StringBufferVerify) { itoa64_Writer_StringBufferVerify<Writer3<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa64_Writer4_StringBufferVerify)957 TEST_F(Misc, itoa64_Writer4_StringBufferVerify) { itoa64_Writer_StringBufferVerify<Writer4<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa64_Writer_InsituStringStreamVerify)958 TEST_F(Misc, itoa64_Writer_InsituStringStreamVerify) { itoa64_Writer_InsituStringStreamVerify<rapidjson::Writer<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa64_Writer1_InsituStringStreamVerify)959 TEST_F(Misc, itoa64_Writer1_InsituStringStreamVerify) { itoa64_Writer_InsituStringStreamVerify<Writer1<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa64_Writer2_InsituStringStreamVerify)960 TEST_F(Misc, itoa64_Writer2_InsituStringStreamVerify) { itoa64_Writer_InsituStringStreamVerify<Writer2<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa64_Writer3_InsituStringStreamVerify)961 TEST_F(Misc, itoa64_Writer3_InsituStringStreamVerify) { itoa64_Writer_InsituStringStreamVerify<Writer3<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa64_Writer4_InsituStringStreamVerify)962 TEST_F(Misc, itoa64_Writer4_InsituStringStreamVerify) { itoa64_Writer_InsituStringStreamVerify<Writer4<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa64_Writer_StringBuffer)963 TEST_F(Misc, itoa64_Writer_StringBuffer) { itoa64_Writer_StringBuffer<rapidjson::Writer<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa64_Writer1_StringBuffer)964 TEST_F(Misc, itoa64_Writer1_StringBuffer) { itoa64_Writer_StringBuffer<Writer1<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa64_Writer2_StringBuffer)965 TEST_F(Misc, itoa64_Writer2_StringBuffer) { itoa64_Writer_StringBuffer<Writer2<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa64_Writer3_StringBuffer)966 TEST_F(Misc, itoa64_Writer3_StringBuffer) { itoa64_Writer_StringBuffer<Writer3<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa64_Writer4_StringBuffer)967 TEST_F(Misc, itoa64_Writer4_StringBuffer) { itoa64_Writer_StringBuffer<Writer4<rapidjson::StringBuffer> >(); }
TEST_F(Misc,itoa64_Writer_InsituStringStream)968 TEST_F(Misc, itoa64_Writer_InsituStringStream) { itoa64_Writer_InsituStringStream<rapidjson::Writer<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa64_Writer1_InsituStringStream)969 TEST_F(Misc, itoa64_Writer1_InsituStringStream) { itoa64_Writer_InsituStringStream<Writer1<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa64_Writer2_InsituStringStream)970 TEST_F(Misc, itoa64_Writer2_InsituStringStream) { itoa64_Writer_InsituStringStream<Writer2<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa64_Writer3_InsituStringStream)971 TEST_F(Misc, itoa64_Writer3_InsituStringStream) { itoa64_Writer_InsituStringStream<Writer3<rapidjson::InsituStringStream> >(); }
TEST_F(Misc,itoa64_Writer4_InsituStringStream)972 TEST_F(Misc, itoa64_Writer4_InsituStringStream) { itoa64_Writer_InsituStringStream<Writer4<rapidjson::InsituStringStream> >(); }
973 
974 #endif // TEST_MISC
975