ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/CBOR-XS/XS.xs
(Generate patch)

Comparing CBOR-XS/XS.xs (file contents):
Revision 1.30 by root, Thu Nov 28 11:36:53 2013 UTC vs.
Revision 1.61 by root, Sat Nov 26 02:10:19 2016 UTC

6#include <string.h> 6#include <string.h>
7#include <stdlib.h> 7#include <stdlib.h>
8#include <stdio.h> 8#include <stdio.h>
9#include <limits.h> 9#include <limits.h>
10#include <float.h> 10#include <float.h>
11#include <inttypes.h>
11 12
13#define ECB_NO_THREADS 1
12#include "ecb.h" 14#include "ecb.h"
13 15
14// compatibility with perl <5.18 16// compatibility with perl <5.18
15#ifndef HvNAMELEN_get 17#ifndef HvNAMELEN_get
16# define HvNAMELEN_get(hv) strlen (HvNAME (hv)) 18# define HvNAMELEN_get(hv) strlen (HvNAME (hv))
23#endif 25#endif
24#ifndef SvREFCNT_dec_NN 26#ifndef SvREFCNT_dec_NN
25# define SvREFCNT_dec_NN(sv) SvREFCNT_dec (sv) 27# define SvREFCNT_dec_NN(sv) SvREFCNT_dec (sv)
26#endif 28#endif
27 29
30// known major and minor types
31enum cbor_type
32{
33 MAJOR_SHIFT = 5,
34 MINOR_MASK = 0x1f,
35
36 MAJOR_POS_INT = 0 << MAJOR_SHIFT,
37 MAJOR_NEG_INT = 1 << MAJOR_SHIFT,
38 MAJOR_BYTES = 2 << MAJOR_SHIFT,
39 MAJOR_TEXT = 3 << MAJOR_SHIFT,
40 MAJOR_ARRAY = 4 << MAJOR_SHIFT,
41 MAJOR_MAP = 5 << MAJOR_SHIFT,
42 MAJOR_TAG = 6 << MAJOR_SHIFT,
43 MAJOR_MISC = 7 << MAJOR_SHIFT,
44
45 // INT/STRING/ARRAY/MAP subtypes
46 LENGTH_EXT1 = 24,
47 LENGTH_EXT2 = 25,
48 LENGTH_EXT4 = 26,
49 LENGTH_EXT8 = 27,
50
51 // SIMPLE types (effectively MISC subtypes)
52 SIMPLE_FALSE = 20,
53 SIMPLE_TRUE = 21,
54 SIMPLE_NULL = 22,
55 SIMPLE_UNDEF = 23,
56
57 // MISC subtype (unused)
58 MISC_EXT1 = 24,
59 MISC_FLOAT16 = 25,
60 MISC_FLOAT32 = 26,
61 MISC_FLOAT64 = 27,
62
63 // BYTES/TEXT/ARRAY/MAP
64 MINOR_INDEF = 31,
65};
66
28// known tags 67// known tags
29enum cbor_tag 68enum cbor_tag
30{ 69{
31 // extensions 70 // extensions
32 CBOR_TAG_STRINGREF = 25, // http://cbor.schmorp.de/stringref 71 CBOR_TAG_STRINGREF = 25, // http://cbor.schmorp.de/stringref
33 CBOR_TAG_PERL_OBJECT = 26, // http://cbor.schmorp.de/perl-object 72 CBOR_TAG_PERL_OBJECT = 26, // http://cbor.schmorp.de/perl-object
34 CBOR_TAG_GENERIC_OBJECT = 27, // http://cbor.schmorp.de/generic-object 73 CBOR_TAG_GENERIC_OBJECT = 27, // http://cbor.schmorp.de/generic-object
35 CBOR_TAG_VALUE_SHAREABLE = 28, // http://cbor.schmorp.de/value-sharing 74 CBOR_TAG_VALUE_SHAREABLE = 28, // http://cbor.schmorp.de/value-sharing
36 CBOR_TAG_VALUE_SHAREDREF = 29, // http://cbor.schmorp.de/value-sharing 75 CBOR_TAG_VALUE_SHAREDREF = 29, // http://cbor.schmorp.de/value-sharing
37 CBOR_TAG_STRINGREF_NAMESPACE = 256, // http://cbor.schmorp.de/stringref 76 CBOR_TAG_STRINGREF_NAMESPACE = 256, // http://cbor.schmorp.de/stringref
38 CBOR_TAG_INDIRECTION = 22098, // http://cbor.schmorp.de/indirection 77 CBOR_TAG_INDIRECTION = 22098, // http://cbor.schmorp.de/indirection
39 78
40 // rfc7049 79 // rfc7049
41 CBOR_TAG_DATETIME = 0, // rfc4287, utf-8 80 CBOR_TAG_DATETIME = 0, // rfc4287, utf-8
42 CBOR_TAG_TIMESTAMP = 1, // unix timestamp, any 81 CBOR_TAG_TIMESTAMP = 1, // unix timestamp, any
43 CBOR_TAG_POS_BIGNUM = 2, // byte string 82 CBOR_TAG_POS_BIGNUM = 2, // byte string
44 CBOR_TAG_NEG_BIGNUM = 3, // byte string 83 CBOR_TAG_NEG_BIGNUM = 3, // byte string
45 CBOR_TAG_DECIMAL = 4, // decimal fraction, array 84 CBOR_TAG_DECIMAL = 4, // decimal fraction, array
46 CBOR_TAG_BIGFLOAT = 5, // array 85 CBOR_TAG_BIGFLOAT = 5, // array
47 86
48 CBOR_TAG_CONV_B64U = 21, // base64url, any 87 CBOR_TAG_CONV_B64U = 21, // base64url, any
49 CBOR_TAG_CONV_B64 = 22, // base64, any 88 CBOR_TAG_CONV_B64 = 22, // base64, any
50 CBOR_TAG_CONV_HEX = 23, // base16, any 89 CBOR_TAG_CONV_HEX = 23, // base16, any
51 CBOR_TAG_CBOR = 24, // embedded cbor, byte string 90 CBOR_TAG_CBOR = 24, // embedded cbor, byte string
52 91
53 CBOR_TAG_URI = 32, // URI rfc3986, utf-8 92 CBOR_TAG_URI = 32, // URI rfc3986, utf-8
54 CBOR_TAG_B64U = 33, // base64url rfc4648, utf-8 93 CBOR_TAG_B64U = 33, // base64url rfc4648, utf-8
55 CBOR_TAG_B64 = 34, // base6 rfc46484, utf-8 94 CBOR_TAG_B64 = 34, // base6 rfc46484, utf-8
56 CBOR_TAG_REGEX = 35, // regex pcre/ecma262, utf-8 95 CBOR_TAG_REGEX = 35, // regex pcre/ecma262, utf-8
57 CBOR_TAG_MIME = 36, // mime message rfc2045, utf-8 96 CBOR_TAG_MIME = 36, // mime message rfc2045, utf-8
58 97
59 CBOR_TAG_MAGIC = 55799 // self-describe cbor 98 CBOR_TAG_MAGIC = 55799, // self-describe cbor
60}; 99};
61 100
62#define F_SHRINK 0x00000001UL 101#define F_SHRINK 0x00000001UL
63#define F_ALLOW_UNKNOWN 0x00000002UL 102#define F_ALLOW_UNKNOWN 0x00000002UL
64#define F_ALLOW_SHARING 0x00000004UL //TODO 103#define F_ALLOW_SHARING 0x00000004UL
65#define F_ALLOW_STRINGREF 0x00000008UL //TODO 104#define F_ALLOW_CYCLES 0x00000008UL
105#define F_FORBID_OBJECTS 0x00000010UL
106#define F_PACK_STRINGS 0x00000020UL
107#define F_TEXT_KEYS 0x00000040UL
108#define F_TEXT_STRINGS 0x00000080UL
109#define F_VALIDATE_UTF8 0x00000100UL
66 110
67#define INIT_SIZE 32 // initial scalar size to be allocated 111#define INIT_SIZE 32 // initial scalar size to be allocated
68 112
69#define SB do { 113#define SB do {
70#define SE } while (0) 114#define SE } while (0)
89typedef struct { 133typedef struct {
90 U32 flags; 134 U32 flags;
91 U32 max_depth; 135 U32 max_depth;
92 STRLEN max_size; 136 STRLEN max_size;
93 SV *filter; 137 SV *filter;
138
139 // for the incremental parser
140 STRLEN incr_pos; // the current offset into the text
141 STRLEN incr_need; // minimum bytes needed to decode
142 AV *incr_count; // for every nesting level, the number of outstanding values, or -1 for indef.
94} CBOR; 143} CBOR;
95 144
96ecb_inline void 145ecb_inline void
97cbor_init (CBOR *cbor) 146cbor_init (CBOR *cbor)
98{ 147{
102 151
103ecb_inline void 152ecb_inline void
104cbor_free (CBOR *cbor) 153cbor_free (CBOR *cbor)
105{ 154{
106 SvREFCNT_dec (cbor->filter); 155 SvREFCNT_dec (cbor->filter);
156 SvREFCNT_dec (cbor->incr_count);
107} 157}
108 158
109///////////////////////////////////////////////////////////////////////////// 159/////////////////////////////////////////////////////////////////////////////
110// utility functions 160// utility functions
111 161
137 187
138// minimum length of a string to be registered for stringref 188// minimum length of a string to be registered for stringref
139ecb_inline int 189ecb_inline int
140minimum_string_length (UV idx) 190minimum_string_length (UV idx)
141{ 191{
142 return idx > 23 192
143 ? idx > 0xffU 193 return idx <= 23 ? 3
144 ? idx > 0xffffU 194 : idx <= 0xffU ? 4
195 : idx <= 0xffffU ? 5
145 ? idx > 0xffffffffU 196 : idx <= 0xffffffffU ? 7
146 ? 11 197 : 11;
147 : 7
148 : 5
149 : 4
150 : 3;
151} 198}
152 199
153///////////////////////////////////////////////////////////////////////////// 200/////////////////////////////////////////////////////////////////////////////
154// encoder 201// encoder
155 202
168} enc_t; 215} enc_t;
169 216
170ecb_inline void 217ecb_inline void
171need (enc_t *enc, STRLEN len) 218need (enc_t *enc, STRLEN len)
172{ 219{
173 if (ecb_expect_false (enc->cur + len >= enc->end)) 220 if (ecb_expect_false ((uintptr_t)(enc->end - enc->cur) < len))
174 { 221 {
175 STRLEN cur = enc->cur - (char *)SvPVX (enc->sv); 222 STRLEN cur = enc->cur - (char *)SvPVX (enc->sv);
176 SvGROW (enc->sv, cur + (len < (cur >> 2) ? cur >> 2 : len) + 1); 223 SvGROW (enc->sv, cur + (len < (cur >> 2) ? cur >> 2 : len) + 1);
177 enc->cur = SvPVX (enc->sv) + cur; 224 enc->cur = SvPVX (enc->sv) + cur;
178 enc->end = SvPVX (enc->sv) + SvLEN (enc->sv) - 1; 225 enc->end = SvPVX (enc->sv) + SvLEN (enc->sv) - 1;
189static void 236static void
190encode_uint (enc_t *enc, int major, UV len) 237encode_uint (enc_t *enc, int major, UV len)
191{ 238{
192 need (enc, 9); 239 need (enc, 9);
193 240
194 if (len < 24) 241 if (ecb_expect_true (len < LENGTH_EXT1))
195 *enc->cur++ = major | len; 242 *enc->cur++ = major | len;
196 else if (len <= 0xff) 243 else if (ecb_expect_true (len <= 0xffU))
197 { 244 {
198 *enc->cur++ = major | 24; 245 *enc->cur++ = major | LENGTH_EXT1;
199 *enc->cur++ = len; 246 *enc->cur++ = len;
200 } 247 }
201 else if (len <= 0xffff) 248 else if (len <= 0xffffU)
202 { 249 {
203 *enc->cur++ = major | 25; 250 *enc->cur++ = major | LENGTH_EXT2;
204 *enc->cur++ = len >> 8; 251 *enc->cur++ = len >> 8;
205 *enc->cur++ = len; 252 *enc->cur++ = len;
206 } 253 }
207 else if (len <= 0xffffffff) 254 else if (len <= 0xffffffffU)
208 { 255 {
209 *enc->cur++ = major | 26; 256 *enc->cur++ = major | LENGTH_EXT4;
210 *enc->cur++ = len >> 24; 257 *enc->cur++ = len >> 24;
211 *enc->cur++ = len >> 16; 258 *enc->cur++ = len >> 16;
212 *enc->cur++ = len >> 8; 259 *enc->cur++ = len >> 8;
213 *enc->cur++ = len; 260 *enc->cur++ = len;
214 } 261 }
215 else 262 else
216 { 263 {
217 *enc->cur++ = major | 27; 264 *enc->cur++ = major | LENGTH_EXT8;
218 *enc->cur++ = len >> 56; 265 *enc->cur++ = len >> 56;
219 *enc->cur++ = len >> 48; 266 *enc->cur++ = len >> 48;
220 *enc->cur++ = len >> 40; 267 *enc->cur++ = len >> 40;
221 *enc->cur++ = len >> 32; 268 *enc->cur++ = len >> 32;
222 *enc->cur++ = len >> 24; 269 *enc->cur++ = len >> 24;
227} 274}
228 275
229ecb_inline void 276ecb_inline void
230encode_tag (enc_t *enc, UV tag) 277encode_tag (enc_t *enc, UV tag)
231{ 278{
232 encode_uint (enc, 0xc0, tag); 279 encode_uint (enc, MAJOR_TAG, tag);
280}
281
282// exceptional (hopefully) slow path for byte strings that need to be utf8-encoded
283ecb_noinline static void
284encode_str_utf8 (enc_t *enc, int utf8, char *str, STRLEN len)
285{
286 STRLEN ulen = len;
287 U8 *p, *pend = (U8 *)str + len;
288
289 for (p = (U8 *)str; p < pend; ++p)
290 ulen += *p >> 7; // count set high bits
291
292 encode_uint (enc, MAJOR_TEXT, ulen);
293
294 need (enc, ulen);
295 for (p = (U8 *)str; p < pend; ++p)
296 if (*p < 0x80)
297 *enc->cur++ = *p;
298 else
299 {
300 *enc->cur++ = 0xc0 + (*p >> 6);
301 *enc->cur++ = 0x80 + (*p & 63);
302 }
233} 303}
234 304
235ecb_inline void 305ecb_inline void
236encode_str (enc_t *enc, int utf8, char *str, STRLEN len) 306encode_str (enc_t *enc, int upgrade_utf8, int utf8, char *str, STRLEN len)
237{ 307{
238 encode_uint (enc, utf8 ? 0x60 : 0x40, len); 308 if (ecb_expect_false (upgrade_utf8))
309 if (!utf8)
310 {
311 encode_str_utf8 (enc, utf8, str, len);
312 return;
313 }
314
315 encode_uint (enc, utf8 ? MAJOR_TEXT : MAJOR_BYTES, len);
239 need (enc, len); 316 need (enc, len);
240 memcpy (enc->cur, str, len); 317 memcpy (enc->cur, str, len);
241 enc->cur += len; 318 enc->cur += len;
242} 319}
243 320
244static void 321ecb_inline void
245encode_strref (enc_t *enc, int utf8, char *str, STRLEN len) 322encode_strref (enc_t *enc, int upgrade_utf8, int utf8, char *str, STRLEN len)
246{ 323{
247 if (ecb_expect_false (enc->cbor.flags & F_ALLOW_STRINGREF)) 324 if (ecb_expect_false (enc->cbor.flags & F_PACK_STRINGS))
248 { 325 {
249 SV **svp = hv_fetch (enc->stringref[!!utf8], str, len, 1); 326 SV **svp = hv_fetch (enc->stringref[!!utf8], str, len, 1);
250 327
251 if (SvOK (*svp)) 328 if (SvOK (*svp))
252 { 329 {
253 // already registered, use stringref 330 // already registered, use stringref
254 encode_tag (enc, CBOR_TAG_STRINGREF); 331 encode_tag (enc, CBOR_TAG_STRINGREF);
255 encode_uint (enc, 0x00, SvUV (*svp)); 332 encode_uint (enc, MAJOR_POS_INT, SvUV (*svp));
256 return; 333 return;
257 } 334 }
258 else if (len >= minimum_string_length (enc->stringref_idx)) 335 else if (len >= minimum_string_length (enc->stringref_idx))
259 { 336 {
260 // register only 337 // register only
261 sv_setuv (*svp, enc->stringref_idx); 338 sv_setuv (*svp, enc->stringref_idx);
262 ++enc->stringref_idx; 339 ++enc->stringref_idx;
263 } 340 }
264 } 341 }
265 342
266 encode_str (enc, utf8, str, len); 343 encode_str (enc, upgrade_utf8, utf8, str, len);
267} 344}
268 345
269static void encode_sv (enc_t *enc, SV *sv); 346static void encode_sv (enc_t *enc, SV *sv);
270 347
271static void 348static void
276 if (enc->depth >= enc->cbor.max_depth) 353 if (enc->depth >= enc->cbor.max_depth)
277 croak (ERR_NESTING_EXCEEDED); 354 croak (ERR_NESTING_EXCEEDED);
278 355
279 ++enc->depth; 356 ++enc->depth;
280 357
281 encode_uint (enc, 0x80, len + 1); 358 encode_uint (enc, MAJOR_ARRAY, len + 1);
282 359
360 if (SvMAGICAL (av))
283 for (i = 0; i <= len; ++i) 361 for (i = 0; i <= len; ++i)
284 { 362 {
285 SV **svp = av_fetch (av, i, 0); 363 SV **svp = av_fetch (av, i, 0);
286 encode_sv (enc, svp ? *svp : &PL_sv_undef); 364 encode_sv (enc, svp ? *svp : &PL_sv_undef);
287 } 365 }
366 else
367 for (i = 0; i <= len; ++i)
368 {
369 SV *sv = AvARRAY (av)[i];
370 encode_sv (enc, sv ? sv : &PL_sv_undef);
371 }
288 372
289 --enc->depth; 373 --enc->depth;
290} 374}
291 375
292static void 376static void
301 385
302 int pairs = hv_iterinit (hv); 386 int pairs = hv_iterinit (hv);
303 int mg = SvMAGICAL (hv); 387 int mg = SvMAGICAL (hv);
304 388
305 if (mg) 389 if (mg)
306 encode_ch (enc, 0xa0 | 31); 390 encode_ch (enc, MAJOR_MAP | MINOR_INDEF);
307 else 391 else
308 encode_uint (enc, 0xa0, pairs); 392 encode_uint (enc, MAJOR_MAP, pairs);
309 393
310 while ((he = hv_iternext (hv))) 394 while ((he = hv_iternext (hv)))
311 { 395 {
312 if (HeKLEN (he) == HEf_SVKEY) 396 if (HeKLEN (he) == HEf_SVKEY)
313 encode_sv (enc, HeSVKEY (he)); 397 encode_sv (enc, HeSVKEY (he));
314 else 398 else
315 encode_strref (enc, HeKUTF8 (he), HeKEY (he), HeKLEN (he)); 399 encode_strref (enc, enc->cbor.flags & (F_TEXT_KEYS | F_TEXT_STRINGS), HeKUTF8 (he), HeKEY (he), HeKLEN (he));
316 400
317 encode_sv (enc, ecb_expect_false (mg) ? hv_iterval (hv, he) : HeVAL (he)); 401 encode_sv (enc, ecb_expect_false (mg) ? hv_iterval (hv, he) : HeVAL (he));
318 } 402 }
319 403
320 if (mg) 404 if (mg)
321 encode_ch (enc, 0xe0 | 31); 405 encode_ch (enc, MAJOR_MISC | MINOR_INDEF);
322 406
323 --enc->depth; 407 --enc->depth;
324} 408}
325 409
326// encode objects, arrays and special \0=false and \1=true values. 410// encode objects, arrays and special \0=false and \1=true values.
327static void 411static void
328encode_rv (enc_t *enc, SV *sv) 412encode_rv (enc_t *enc, SV *sv)
329{ 413{
330 SvGETMAGIC (sv); 414 SvGETMAGIC (sv);
331
332 if (ecb_expect_false (enc->cbor.flags & F_ALLOW_SHARING)
333 && ecb_expect_false (SvREFCNT (sv) > 1))
334 {
335 if (!enc->shareable)
336 enc->shareable = (HV *)sv_2mortal ((SV *)newHV ());
337
338 SV **svp = hv_fetch (enc->shareable, (char *)&sv, sizeof (sv), 1);
339
340 if (SvOK (*svp))
341 {
342 encode_tag (enc, CBOR_TAG_VALUE_SHAREDREF);
343 encode_uint (enc, 0x00, SvUV (*svp));
344 return;
345 }
346 else
347 {
348 sv_setuv (*svp, enc->shareable_idx);
349 ++enc->shareable_idx;
350 encode_tag (enc, CBOR_TAG_VALUE_SHAREABLE);
351 }
352 }
353 415
354 svtype svt = SvTYPE (sv); 416 svtype svt = SvTYPE (sv);
355 417
356 if (ecb_expect_false (SvOBJECT (sv))) 418 if (ecb_expect_false (SvOBJECT (sv)))
357 { 419 {
364 HV *tagged_stash = !CBOR_SLOW || cbor_tagged_stash 426 HV *tagged_stash = !CBOR_SLOW || cbor_tagged_stash
365 ? cbor_tagged_stash 427 ? cbor_tagged_stash
366 : gv_stashpv ("CBOR::XS::Tagged" , 1); 428 : gv_stashpv ("CBOR::XS::Tagged" , 1);
367 429
368 HV *stash = SvSTASH (sv); 430 HV *stash = SvSTASH (sv);
369 GV *method;
370 431
371 if (stash == boolean_stash) 432 if (stash == boolean_stash)
372 encode_ch (enc, SvIV (sv) ? 0xe0 | 21 : 0xe0 | 20); 433 {
434 encode_ch (enc, SvIV (sv) ? MAJOR_MISC | SIMPLE_TRUE : MAJOR_MISC | SIMPLE_FALSE);
435 return;
436 }
373 else if (stash == error_stash) 437 else if (stash == error_stash)
374 encode_ch (enc, 0xe0 | 23); 438 {
439 encode_ch (enc, MAJOR_MISC | SIMPLE_UNDEF);
440 return;
441 }
375 else if (stash == tagged_stash) 442 else if (stash == tagged_stash)
376 { 443 {
377 if (svt != SVt_PVAV) 444 if (svt != SVt_PVAV)
378 croak ("encountered CBOR::XS::Tagged object that isn't an array"); 445 croak ("encountered CBOR::XS::Tagged object that isn't an array");
379 446
380 encode_uint (enc, 0xc0, SvUV (*av_fetch ((AV *)sv, 0, 1))); 447 encode_uint (enc, MAJOR_TAG, SvUV (*av_fetch ((AV *)sv, 0, 1)));
381 encode_sv (enc, *av_fetch ((AV *)sv, 1, 1)); 448 encode_sv (enc, *av_fetch ((AV *)sv, 1, 1));
449
450 return;
451 }
452 }
453
454 if (ecb_expect_false (SvREFCNT (sv) > 1)
455 && ecb_expect_false (enc->cbor.flags & F_ALLOW_SHARING))
456 {
457 if (!enc->shareable)
458 enc->shareable = (HV *)sv_2mortal ((SV *)newHV ());
459
460 SV **svp = hv_fetch (enc->shareable, (char *)&sv, sizeof (sv), 1);
461
462 if (SvOK (*svp))
382 } 463 {
464 encode_tag (enc, CBOR_TAG_VALUE_SHAREDREF);
465 encode_uint (enc, MAJOR_POS_INT, SvUV (*svp));
466 return;
467 }
468 else
469 {
470 sv_setuv (*svp, enc->shareable_idx);
471 ++enc->shareable_idx;
472 encode_tag (enc, CBOR_TAG_VALUE_SHAREABLE);
473 }
474 }
475
476 if (ecb_expect_false (SvOBJECT (sv)))
477 {
478 HV *stash = SvSTASH (sv);
479 GV *method;
480
481 if (enc->cbor.flags & F_FORBID_OBJECTS)
482 croak ("encountered object '%s', but forbid_objects is enabled",
483 SvPV_nolen (sv_2mortal (newRV_inc (sv))));
383 else if ((method = gv_fetchmethod_autoload (stash, "TO_CBOR", 0))) 484 else if ((method = gv_fetchmethod_autoload (stash, "TO_CBOR", 0)))
384 { 485 {
385 dSP; 486 dSP;
386 487
387 ENTER; SAVETMPS; PUSHMARK (SP); 488 ENTER; SAVETMPS;
489 PUSHMARK (SP);
388 // we re-bless the reference to get overload and other niceties right 490 // we re-bless the reference to get overload and other niceties right
389 XPUSHs (sv_bless (sv_2mortal (newRV_inc (sv)), stash)); 491 XPUSHs (sv_bless (sv_2mortal (newRV_inc (sv)), stash));
390 492
391 PUTBACK; 493 PUTBACK;
392 // G_SCALAR ensures that return value is 1 494 // G_SCALAR ensures that return value is 1
405 } 507 }
406 else if ((method = gv_fetchmethod_autoload (stash, "FREEZE", 0)) != 0) 508 else if ((method = gv_fetchmethod_autoload (stash, "FREEZE", 0)) != 0)
407 { 509 {
408 dSP; 510 dSP;
409 511
410 ENTER; SAVETMPS; PUSHMARK (SP); 512 ENTER; SAVETMPS;
513 SAVESTACK_POS ();
514 PUSHMARK (SP);
411 EXTEND (SP, 2); 515 EXTEND (SP, 2);
412 // we re-bless the reference to get overload and other niceties right 516 // we re-bless the reference to get overload and other niceties right
413 PUSHs (sv_bless (sv_2mortal (newRV_inc (sv)), stash)); 517 PUSHs (sv_bless (sv_2mortal (newRV_inc (sv)), stash));
414 PUSHs (sv_cbor); 518 PUSHs (sv_cbor);
415 519
420 // catch this surprisingly common error 524 // catch this surprisingly common error
421 if (count == 1 && SvROK (TOPs) && SvRV (TOPs) == sv) 525 if (count == 1 && SvROK (TOPs) && SvRV (TOPs) == sv)
422 croak ("%s::FREEZE(CBOR) method returned same object as was passed instead of a new one", HvNAME (stash)); 526 croak ("%s::FREEZE(CBOR) method returned same object as was passed instead of a new one", HvNAME (stash));
423 527
424 encode_tag (enc, CBOR_TAG_PERL_OBJECT); 528 encode_tag (enc, CBOR_TAG_PERL_OBJECT);
425 encode_uint (enc, 0x80, count + 1); 529 encode_uint (enc, MAJOR_ARRAY, count + 1);
426 encode_strref (enc, HvNAMEUTF8 (stash), HvNAME (stash), HvNAMELEN (stash)); 530 encode_strref (enc, 0, HvNAMEUTF8 (stash), HvNAME (stash), HvNAMELEN (stash));
427 531
428 while (count) 532 while (count)
429 encode_sv (enc, SP[1 - count--]); 533 encode_sv (enc, SP[1 - count--]);
430 534
431 PUTBACK; 535 PUTBACK;
452{ 556{
453 double nv = SvNVX (sv); 557 double nv = SvNVX (sv);
454 558
455 need (enc, 9); 559 need (enc, 9);
456 560
457 if (ecb_expect_false (nv == (U32)nv)) 561 if (ecb_expect_false (nv == (NV)(U32)nv))
458 encode_uint (enc, 0x00, (U32)nv); 562 encode_uint (enc, MAJOR_POS_INT, (U32)nv);
459 //TODO: maybe I32? 563 //TODO: maybe I32?
460 else if (ecb_expect_false (nv == (float)nv)) 564 else if (ecb_expect_false (nv == (float)nv))
461 { 565 {
462 uint32_t fp = ecb_float_to_binary32 (nv); 566 uint32_t fp = ecb_float_to_binary32 (nv);
463 567
464 *enc->cur++ = 0xe0 | 26; 568 *enc->cur++ = MAJOR_MISC | MISC_FLOAT32;
465 569
466 if (!ecb_big_endian ()) 570 if (!ecb_big_endian ())
467 fp = ecb_bswap32 (fp); 571 fp = ecb_bswap32 (fp);
468 572
469 memcpy (enc->cur, &fp, 4); 573 memcpy (enc->cur, &fp, 4);
471 } 575 }
472 else 576 else
473 { 577 {
474 uint64_t fp = ecb_double_to_binary64 (nv); 578 uint64_t fp = ecb_double_to_binary64 (nv);
475 579
476 *enc->cur++ = 0xe0 | 27; 580 *enc->cur++ = MAJOR_MISC | MISC_FLOAT64;
477 581
478 if (!ecb_big_endian ()) 582 if (!ecb_big_endian ())
479 fp = ecb_bswap64 (fp); 583 fp = ecb_bswap64 (fp);
480 584
481 memcpy (enc->cur, &fp, 8); 585 memcpy (enc->cur, &fp, 8);
490 594
491 if (SvPOKp (sv)) 595 if (SvPOKp (sv))
492 { 596 {
493 STRLEN len; 597 STRLEN len;
494 char *str = SvPV (sv, len); 598 char *str = SvPV (sv, len);
495 encode_strref (enc, SvUTF8 (sv), str, len); 599 encode_strref (enc, enc->cbor.flags & F_TEXT_STRINGS, SvUTF8 (sv), str, len);
496 } 600 }
497 else if (SvNOKp (sv)) 601 else if (SvNOKp (sv))
498 encode_nv (enc, sv); 602 encode_nv (enc, sv);
499 else if (SvIOKp (sv)) 603 else if (SvIOKp (sv))
500 { 604 {
501 if (SvIsUV (sv)) 605 if (SvIsUV (sv))
502 encode_uint (enc, 0x00, SvUVX (sv)); 606 encode_uint (enc, MAJOR_POS_INT, SvUVX (sv));
503 else if (SvIVX (sv) >= 0) 607 else if (SvIVX (sv) >= 0)
504 encode_uint (enc, 0x00, SvIVX (sv)); 608 encode_uint (enc, MAJOR_POS_INT, SvIVX (sv));
505 else 609 else
506 encode_uint (enc, 0x20, -(SvIVX (sv) + 1)); 610 encode_uint (enc, MAJOR_NEG_INT, -(SvIVX (sv) + 1));
507 } 611 }
508 else if (SvROK (sv)) 612 else if (SvROK (sv))
509 encode_rv (enc, SvRV (sv)); 613 encode_rv (enc, SvRV (sv));
510 else if (!SvOK (sv)) 614 else if (!SvOK (sv))
511 encode_ch (enc, 0xe0 | 22); 615 encode_ch (enc, MAJOR_MISC | SIMPLE_NULL);
512 else if (enc->cbor.flags & F_ALLOW_UNKNOWN) 616 else if (enc->cbor.flags & F_ALLOW_UNKNOWN)
513 encode_ch (enc, 0xe0 | 23); 617 encode_ch (enc, MAJOR_MISC | SIMPLE_UNDEF);
514 else 618 else
515 croak ("encountered perl type (%s,0x%x) that CBOR cannot handle, check your input data", 619 croak ("encountered perl type (%s,0x%x) that CBOR cannot handle, check your input data",
516 SvPV_nolen (sv), (unsigned int)SvFLAGS (sv)); 620 SvPV_nolen (sv), (unsigned int)SvFLAGS (sv));
517} 621}
518 622
519static SV * 623static SV *
520encode_cbor (SV *scalar, CBOR *cbor) 624encode_cbor (SV *scalar, CBOR *cbor)
521{ 625{
522 enc_t enc = { }; 626 enc_t enc = { 0 };
523 627
524 enc.cbor = *cbor; 628 enc.cbor = *cbor;
525 enc.sv = sv_2mortal (NEWSV (0, INIT_SIZE)); 629 enc.sv = sv_2mortal (NEWSV (0, INIT_SIZE));
526 enc.cur = SvPVX (enc.sv); 630 enc.cur = SvPVX (enc.sv);
527 enc.end = SvEND (enc.sv); 631 enc.end = SvEND (enc.sv);
528 632
529 SvPOK_only (enc.sv); 633 SvPOK_only (enc.sv);
530 634
531 if (cbor->flags & F_ALLOW_STRINGREF) 635 if (cbor->flags & F_PACK_STRINGS)
532 { 636 {
533 encode_tag (&enc, CBOR_TAG_STRINGREF_NAMESPACE); 637 encode_tag (&enc, CBOR_TAG_STRINGREF_NAMESPACE);
534 enc.stringref[0]= (HV *)sv_2mortal ((SV *)newHV ()); 638 enc.stringref[0]= (HV *)sv_2mortal ((SV *)newHV ());
535 enc.stringref[1]= (HV *)sv_2mortal ((SV *)newHV ()); 639 enc.stringref[1]= (HV *)sv_2mortal ((SV *)newHV ());
536 } 640 }
559 U32 depth; // recursion depth 663 U32 depth; // recursion depth
560 U32 maxdepth; // recursion depth limit 664 U32 maxdepth; // recursion depth limit
561 AV *shareable; 665 AV *shareable;
562 AV *stringref; 666 AV *stringref;
563 SV *decode_tagged; 667 SV *decode_tagged;
668 SV *err_sv; // optional sv for error, needs to be freed
564} dec_t; 669} dec_t;
565 670
566#define ERR(reason) SB if (!dec->err) dec->err = reason; goto fail; SE 671// set dec->err to ERRSV
672ecb_cold static void
673err_errsv (dec_t *dec)
674{
675 if (!dec->err)
676 {
677 dec->err_sv = newSVsv (ERRSV);
567 678
568#define WANT(len) if (ecb_expect_false (dec->cur + len > dec->end)) ERR ("unexpected end of CBOR data") 679 // chop off the trailing \n
680 SvCUR_set (dec->err_sv, SvCUR (dec->err_sv) - 1);
681 *SvEND (dec->err_sv) = 0;
569 682
683 dec->err = SvPVutf8_nolen (dec->err_sv);
684 }
685}
686
687// the following functions are used to reduce code size and help the compiler to optimise
688ecb_cold static void
689err_set (dec_t *dec, const char *reason)
690{
691 if (!dec->err)
692 dec->err = reason;
693}
694
695ecb_cold static void
696err_unexpected_end (dec_t *dec)
697{
698 err_set (dec, "unexpected end of CBOR data");
699}
700
701ecb_cold static void
702err_nesting_exceeded (dec_t *dec)
703{
704 err_set (dec, ERR_NESTING_EXCEEDED);
705}
706
707#define ERR_DO(do) SB do; goto fail; SE
708#define ERR(reason) ERR_DO (err_set (dec, reason))
709#define ERR_ERRSV ERR_DO (err_errsv (dec))
710
711#define WANT(len) if (ecb_expect_false ((uintptr_t)(dec->end - dec->cur) < (STRLEN)len)) ERR_DO (err_unexpected_end (dec))
712
570#define DEC_INC_DEPTH if (++dec->depth > dec->cbor.max_depth) ERR (ERR_NESTING_EXCEEDED) 713#define DEC_INC_DEPTH if (ecb_expect_false (++dec->depth > dec->cbor.max_depth)) ERR (ERR_NESTING_EXCEEDED)
571#define DEC_DEC_DEPTH --dec->depth 714#define DEC_DEC_DEPTH --dec->depth
572 715
573static UV 716static UV
574decode_uint (dec_t *dec) 717decode_uint (dec_t *dec)
575{ 718{
576 switch (*dec->cur & 31) 719 U8 m = *dec->cur & MINOR_MASK;
577 { 720 ++dec->cur;
578 case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7:
579 case 8: case 9: case 10: case 11: case 12: case 13: case 14: case 15:
580 case 16: case 17: case 18: case 19: case 20: case 21: case 22: case 23:
581 return *dec->cur++ & 31;
582 721
583 case 24: 722 if (ecb_expect_true (m < LENGTH_EXT1))
723 return m;
724 else if (ecb_expect_true (m == LENGTH_EXT1))
725 {
584 WANT (2); 726 WANT (1);
585 dec->cur += 2; 727 dec->cur += 1;
586 return dec->cur[-1]; 728 return dec->cur[-1];
587 729 }
588 case 25: 730 else if (ecb_expect_true (m == LENGTH_EXT2))
731 {
589 WANT (3); 732 WANT (2);
590 dec->cur += 3; 733 dec->cur += 2;
591 return (((UV)dec->cur[-2]) << 8) 734 return (((UV)dec->cur[-2]) << 8)
592 | ((UV)dec->cur[-1]); 735 | ((UV)dec->cur[-1]);
593 736 }
594 case 26: 737 else if (ecb_expect_true (m == LENGTH_EXT4))
738 {
595 WANT (5); 739 WANT (4);
596 dec->cur += 5; 740 dec->cur += 4;
597 return (((UV)dec->cur[-4]) << 24) 741 return (((UV)dec->cur[-4]) << 24)
598 | (((UV)dec->cur[-3]) << 16) 742 | (((UV)dec->cur[-3]) << 16)
599 | (((UV)dec->cur[-2]) << 8) 743 | (((UV)dec->cur[-2]) << 8)
600 | ((UV)dec->cur[-1]); 744 | ((UV)dec->cur[-1]);
601 745 }
602 case 27: 746 else if (ecb_expect_true (m == LENGTH_EXT8))
747 {
603 WANT (9); 748 WANT (8);
604 dec->cur += 9; 749 dec->cur += 8;
750
751 return
752#if UVSIZE < 8
753 0
754#else
605 return (((UV)dec->cur[-8]) << 56) 755 (((UV)dec->cur[-8]) << 56)
606 | (((UV)dec->cur[-7]) << 48) 756 | (((UV)dec->cur[-7]) << 48)
607 | (((UV)dec->cur[-6]) << 40) 757 | (((UV)dec->cur[-6]) << 40)
608 | (((UV)dec->cur[-5]) << 32) 758 | (((UV)dec->cur[-5]) << 32)
759#endif
609 | (((UV)dec->cur[-4]) << 24) 760 | (((UV)dec->cur[-4]) << 24)
610 | (((UV)dec->cur[-3]) << 16) 761 | (((UV)dec->cur[-3]) << 16)
611 | (((UV)dec->cur[-2]) << 8) 762 | (((UV)dec->cur[-2]) << 8)
612 | ((UV)dec->cur[-1]); 763 | ((UV)dec->cur[-1]);
613 764 }
614 default: 765 else
615 ERR ("corrupted CBOR data (unsupported integer minor encoding)"); 766 ERR ("corrupted CBOR data (unsupported integer minor encoding)");
616 }
617 767
618fail: 768fail:
619 return 0; 769 return 0;
620} 770}
621 771
626{ 776{
627 AV *av = newAV (); 777 AV *av = newAV ();
628 778
629 DEC_INC_DEPTH; 779 DEC_INC_DEPTH;
630 780
631 if ((*dec->cur & 31) == 31) 781 if (*dec->cur == (MAJOR_ARRAY | MINOR_INDEF))
632 { 782 {
633 ++dec->cur; 783 ++dec->cur;
634 784
635 for (;;) 785 for (;;)
636 { 786 {
637 WANT (1); 787 WANT (1);
638 788
639 if (*dec->cur == (0xe0 | 31)) 789 if (*dec->cur == (MAJOR_MISC | MINOR_INDEF))
640 { 790 {
641 ++dec->cur; 791 ++dec->cur;
642 break; 792 break;
643 } 793 }
644 794
645 av_push (av, decode_sv (dec)); 795 av_push (av, decode_sv (dec));
646 } 796 }
647 } 797 }
648 else 798 else
649 { 799 {
650 int i, len = decode_uint (dec); 800 UV i, len = decode_uint (dec);
651 801
802 WANT (len); // complexity check for av_fill - need at least one byte per value, do not allow supersize arrays
652 av_fill (av, len - 1); 803 av_fill (av, len - 1);
653 804
654 for (i = 0; i < len; ++i) 805 for (i = 0; i < len; ++i)
655 AvARRAY (av)[i] = decode_sv (dec); 806 AvARRAY (av)[i] = decode_sv (dec);
656 } 807 }
669{ 820{
670 // for speed reasons, we specialcase single-string 821 // for speed reasons, we specialcase single-string
671 // byte or utf-8 strings as keys, but only when !stringref 822 // byte or utf-8 strings as keys, but only when !stringref
672 823
673 if (ecb_expect_true (!dec->stringref)) 824 if (ecb_expect_true (!dec->stringref))
674 if (*dec->cur >= 0x40 && *dec->cur <= 0x40 + 27) 825 if (ecb_expect_true ((U8)(*dec->cur - MAJOR_BYTES) <= LENGTH_EXT8))
675 { 826 {
676 I32 len = decode_uint (dec); 827 STRLEN len = decode_uint (dec);
677 char *key = (char *)dec->cur; 828 char *key = (char *)dec->cur;
678 829
830 WANT (len);
679 dec->cur += len; 831 dec->cur += len;
680 832
681 if (ecb_expect_false (dec->stringref))
682 av_push (dec->stringref, newSVpvn (key, len));
683
684 hv_store (hv, key, len, decode_sv (dec), 0); 833 hv_store (hv, key, len, decode_sv (dec), 0);
685 834
686 return; 835 return;
687 } 836 }
688 else if (*dec->cur >= 0x60 && *dec->cur <= 0x60 + 27) 837 else if (ecb_expect_true ((U8)(*dec->cur - MAJOR_TEXT) <= LENGTH_EXT8))
689 { 838 {
690 I32 len = decode_uint (dec); 839 STRLEN len = decode_uint (dec);
691 char *key = (char *)dec->cur; 840 char *key = (char *)dec->cur;
692 841
842 WANT (len);
693 dec->cur += len; 843 dec->cur += len;
694 844
695 if (ecb_expect_false (dec->stringref)) 845 if (ecb_expect_false (dec->cbor.flags & F_VALIDATE_UTF8))
696 av_push (dec->stringref, newSVpvn_utf8 (key, len, 1)); 846 if (!is_utf8_string (key, len))
847 ERR ("corrupted CBOR data (invalid UTF-8 in map key)");
697 848
698 hv_store (hv, key, -len, decode_sv (dec), 0); 849 hv_store (hv, key, -len, decode_sv (dec), 0);
699 850
700 return; 851 return;
701 } 852 }
702 853
703 SV *k = decode_sv (dec); 854 SV *k = decode_sv (dec);
704 SV *v = decode_sv (dec); 855 SV *v = decode_sv (dec);
705 856
857 // we leak memory if uncaught exceptions are thrown by random magical
858 // methods, and this is hopefully the only place where it can happen,
859 // so if there is a chance of an exception, take the very slow path.
860 // since catching exceptions is "undocumented/internal/forbidden" by
861 // the new p5p powers, we need to call out to a perl function :/
862 if (ecb_expect_false (SvAMAGIC (k)))
863 {
864 dSP;
865
866 ENTER; SAVETMPS;
867 PUSHMARK (SP);
868 EXTEND (SP, 3);
869 PUSHs (sv_2mortal (newRV_inc ((SV *)hv)));
870 PUSHs (sv_2mortal (k));
871 PUSHs (sv_2mortal (v));
872
873 PUTBACK;
874 call_pv ("CBOR::XS::_hv_store", G_VOID | G_DISCARD | G_EVAL);
875 SPAGAIN;
876
877 FREETMPS; LEAVE;
878
879 if (SvTRUE (ERRSV))
880 ERR_ERRSV;
881
882 return;
883 }
884
706 hv_store_ent (hv, k, v, 0); 885 hv_store_ent (hv, k, v, 0);
707 SvREFCNT_dec (k); 886 SvREFCNT_dec (k);
887
888fail:
889 ;
708} 890}
709 891
710static SV * 892static SV *
711decode_hv (dec_t *dec) 893decode_hv (dec_t *dec)
712{ 894{
713 HV *hv = newHV (); 895 HV *hv = newHV ();
714 896
715 DEC_INC_DEPTH; 897 DEC_INC_DEPTH;
716 898
717 if ((*dec->cur & 31) == 31) 899 if (*dec->cur == (MAJOR_MAP | MINOR_INDEF))
718 { 900 {
719 ++dec->cur; 901 ++dec->cur;
720 902
721 for (;;) 903 for (;;)
722 { 904 {
723 WANT (1); 905 WANT (1);
724 906
725 if (*dec->cur == (0xe0 | 31)) 907 if (*dec->cur == (MAJOR_MISC | MINOR_INDEF))
726 { 908 {
727 ++dec->cur; 909 ++dec->cur;
728 break; 910 break;
729 } 911 }
730 912
731 decode_he (dec, hv); 913 decode_he (dec, hv);
732 } 914 }
733 } 915 }
734 else 916 else
735 { 917 {
736 int pairs = decode_uint (dec); 918 UV pairs = decode_uint (dec);
919
920 WANT (pairs); // complexity check - need at least one byte per value, do not allow supersize hashes
737 921
738 while (pairs--) 922 while (pairs--)
739 decode_he (dec, hv); 923 decode_he (dec, hv);
740 } 924 }
741 925
751static SV * 935static SV *
752decode_str (dec_t *dec, int utf8) 936decode_str (dec_t *dec, int utf8)
753{ 937{
754 SV *sv = 0; 938 SV *sv = 0;
755 939
756 if ((*dec->cur & 31) == 31) 940 if ((*dec->cur & MINOR_MASK) == MINOR_INDEF)
757 { 941 {
942 // indefinite length strings
758 ++dec->cur; 943 ++dec->cur;
759 944
945 U8 major = *dec->cur & MAJOR_MISC;
946
760 sv = newSVpvn ("", 0); 947 sv = newSVpvn ("", 0);
761 948
762 // not very fast, and certainly not robust against illegal input
763 for (;;) 949 for (;;)
764 { 950 {
765 WANT (1); 951 WANT (1);
766 952
767 if (*dec->cur == (0xe0 | 31)) 953 if ((*dec->cur - major) > LENGTH_EXT8)
954 if (*dec->cur == (MAJOR_MISC | MINOR_INDEF))
768 { 955 {
769 ++dec->cur; 956 ++dec->cur;
770 break; 957 break;
771 } 958 }
959 else
960 ERR ("corrupted CBOR data (invalid chunks in indefinite length string)");
772 961
773 sv_catsv (sv, decode_sv (dec)); 962 STRLEN len = decode_uint (dec);
963
964 WANT (len);
965 sv_catpvn (sv, dec->cur, len);
966 dec->cur += len;
774 } 967 }
775 } 968 }
776 else 969 else
777 { 970 {
778 STRLEN len = decode_uint (dec); 971 STRLEN len = decode_uint (dec);
785 && SvCUR (sv) >= minimum_string_length (AvFILLp (dec->stringref) + 1)) 978 && SvCUR (sv) >= minimum_string_length (AvFILLp (dec->stringref) + 1))
786 av_push (dec->stringref, SvREFCNT_inc_NN (sv)); 979 av_push (dec->stringref, SvREFCNT_inc_NN (sv));
787 } 980 }
788 981
789 if (utf8) 982 if (utf8)
983 {
984 if (ecb_expect_false (dec->cbor.flags & F_VALIDATE_UTF8))
985 if (!is_utf8_string (SvPVX (sv), SvCUR (sv)))
986 ERR ("corrupted CBOR data (invalid UTF-8 in text string)");
987
790 SvUTF8_on (sv); 988 SvUTF8_on (sv);
989 }
791 990
792 return sv; 991 return sv;
793 992
794fail: 993fail:
795 SvREFCNT_dec (sv); 994 SvREFCNT_dec (sv);
814 sv = newRV_noinc (decode_sv (dec)); 1013 sv = newRV_noinc (decode_sv (dec));
815 break; 1014 break;
816 1015
817 case CBOR_TAG_STRINGREF_NAMESPACE: 1016 case CBOR_TAG_STRINGREF_NAMESPACE:
818 { 1017 {
1018 // do nmot use SAVETMPS/FREETMPS, as these will
1019 // erase mortalised caches, e.g. "shareable"
819 ENTER; SAVETMPS; 1020 ENTER;
820 1021
821 SAVESPTR (dec->stringref); 1022 SAVESPTR (dec->stringref);
822 dec->stringref = (AV *)sv_2mortal ((SV *)newAV ()); 1023 dec->stringref = (AV *)sv_2mortal ((SV *)newAV ());
823 1024
824 sv = decode_sv (dec); 1025 sv = decode_sv (dec);
825 1026
826 FREETMPS; LEAVE; 1027 LEAVE;
827 } 1028 }
828 break; 1029 break;
829 1030
830 case CBOR_TAG_STRINGREF: 1031 case CBOR_TAG_STRINGREF:
831 { 1032 {
832 if ((*dec->cur >> 5) != 0) 1033 if ((*dec->cur >> MAJOR_SHIFT) != (MAJOR_POS_INT >> MAJOR_SHIFT))
833 ERR ("corrupted CBOR data (stringref index not an unsigned integer)"); 1034 ERR ("corrupted CBOR data (stringref index not an unsigned integer)");
834 1035
835 UV idx = decode_uint (dec); 1036 UV idx = decode_uint (dec);
836 1037
837 if (!dec->stringref || (int)idx > AvFILLp (dec->stringref)) 1038 if (!dec->stringref || (int)idx > AvFILLp (dec->stringref))
844 case CBOR_TAG_VALUE_SHAREABLE: 1045 case CBOR_TAG_VALUE_SHAREABLE:
845 { 1046 {
846 if (ecb_expect_false (!dec->shareable)) 1047 if (ecb_expect_false (!dec->shareable))
847 dec->shareable = (AV *)sv_2mortal ((SV *)newAV ()); 1048 dec->shareable = (AV *)sv_2mortal ((SV *)newAV ());
848 1049
1050 if (dec->cbor.flags & F_ALLOW_CYCLES)
1051 {
849 sv = newSV (0); 1052 sv = newSV (0);
850 av_push (dec->shareable, SvREFCNT_inc_NN (sv)); 1053 av_push (dec->shareable, SvREFCNT_inc_NN (sv));
851 1054
852 SV *osv = decode_sv (dec); 1055 SV *osv = decode_sv (dec);
853 sv_setsv (sv, osv); 1056 sv_setsv (sv, osv);
854 SvREFCNT_dec_NN (osv); 1057 SvREFCNT_dec_NN (osv);
1058 }
1059 else
1060 {
1061 av_push (dec->shareable, &PL_sv_undef);
1062 int idx = AvFILLp (dec->shareable);
1063 sv = decode_sv (dec);
1064 av_store (dec->shareable, idx, SvREFCNT_inc_NN (sv));
1065 }
855 } 1066 }
856 break; 1067 break;
857 1068
858 case CBOR_TAG_VALUE_SHAREDREF: 1069 case CBOR_TAG_VALUE_SHAREDREF:
859 { 1070 {
860 if ((*dec->cur >> 5) != 0) 1071 if ((*dec->cur >> MAJOR_SHIFT) != (MAJOR_POS_INT >> MAJOR_SHIFT))
861 ERR ("corrupted CBOR data (sharedref index not an unsigned integer)"); 1072 ERR ("corrupted CBOR data (sharedref index not an unsigned integer)");
862 1073
863 UV idx = decode_uint (dec); 1074 UV idx = decode_uint (dec);
864 1075
865 if (!dec->shareable || (int)idx > AvFILLp (dec->shareable)) 1076 if (!dec->shareable || (int)idx > AvFILLp (dec->shareable))
866 ERR ("corrupted CBOR data (sharedref index out of bounds)"); 1077 ERR ("corrupted CBOR data (sharedref index out of bounds)");
867 1078
868 sv = SvREFCNT_inc_NN (AvARRAY (dec->shareable)[idx]); 1079 sv = SvREFCNT_inc_NN (AvARRAY (dec->shareable)[idx]);
1080
1081 if (sv == &PL_sv_undef)
1082 ERR ("cyclic CBOR data structure found, but allow_cycles is not enabled");
869 } 1083 }
870 break; 1084 break;
871 1085
872 case CBOR_TAG_PERL_OBJECT: 1086 case CBOR_TAG_PERL_OBJECT:
873 { 1087 {
1088 if (dec->cbor.flags & F_FORBID_OBJECTS)
1089 goto filter;
1090
874 sv = decode_sv (dec); 1091 sv = decode_sv (dec);
875 1092
876 if (!SvROK (sv) || SvTYPE (SvRV (sv)) != SVt_PVAV) 1093 if (!SvROK (sv) || SvTYPE (SvRV (sv)) != SVt_PVAV)
877 ERR ("corrupted CBOR data (non-array perl object)"); 1094 ERR ("corrupted CBOR data (non-array perl object)");
878 1095
888 if (!method) 1105 if (!method)
889 ERR ("cannot decode perl-object (package does not have a THAW method)"); 1106 ERR ("cannot decode perl-object (package does not have a THAW method)");
890 1107
891 dSP; 1108 dSP;
892 1109
893 ENTER; SAVETMPS; PUSHMARK (SP); 1110 ENTER; SAVETMPS;
1111 PUSHMARK (SP);
894 EXTEND (SP, len + 1); 1112 EXTEND (SP, len + 1);
895 // we re-bless the reference to get overload and other niceties right 1113 // we re-bless the reference to get overload and other niceties right
896 PUSHs (*av_fetch (av, 0, 1)); 1114 PUSHs (*av_fetch (av, 0, 1));
897 PUSHs (sv_cbor); 1115 PUSHs (sv_cbor);
898 1116
906 SPAGAIN; 1124 SPAGAIN;
907 1125
908 if (SvTRUE (ERRSV)) 1126 if (SvTRUE (ERRSV))
909 { 1127 {
910 FREETMPS; LEAVE; 1128 FREETMPS; LEAVE;
911 ERR (SvPVutf8_nolen (sv_2mortal (SvREFCNT_inc (ERRSV)))); 1129 ERR_ERRSV;
912 } 1130 }
913 1131
914 SvREFCNT_dec (sv); 1132 SvREFCNT_dec (sv);
915 sv = SvREFCNT_inc (POPs); 1133 sv = SvREFCNT_inc (POPs);
916 1134
919 FREETMPS; LEAVE; 1137 FREETMPS; LEAVE;
920 } 1138 }
921 break; 1139 break;
922 1140
923 default: 1141 default:
1142 filter:
924 { 1143 {
1144 SV *tag_sv = newSVuv (tag);
1145
925 sv = decode_sv (dec); 1146 sv = decode_sv (dec);
926 1147
927 dSP; 1148 dSP;
928 ENTER; SAVETMPS; PUSHMARK (SP); 1149 ENTER; SAVETMPS;
1150 SAVESTACK_POS ();
1151 PUSHMARK (SP);
929 EXTEND (SP, 2); 1152 EXTEND (SP, 2);
930 PUSHs (newSVuv (tag)); 1153 PUSHs (tag_sv);
931 PUSHs (sv); 1154 PUSHs (sv);
932 1155
933 PUTBACK; 1156 PUTBACK;
934 int count = call_sv (dec->cbor.filter ? dec->cbor.filter : default_filter, G_ARRAY | G_EVAL); 1157 int count = call_sv (dec->cbor.filter ? dec->cbor.filter : default_filter, G_ARRAY | G_EVAL);
935 SPAGAIN; 1158 SPAGAIN;
936 1159
937 if (SvTRUE (ERRSV)) 1160 if (SvTRUE (ERRSV))
938 { 1161 {
1162 SvREFCNT_dec (tag_sv);
939 FREETMPS; LEAVE; 1163 FREETMPS; LEAVE;
940 ERR (SvPVutf8_nolen (sv_2mortal (SvREFCNT_inc (ERRSV)))); 1164 ERR_ERRSV;
941 } 1165 }
942 1166
943 if (count) 1167 if (count)
944 { 1168 {
1169 SvREFCNT_dec (tag_sv);
945 SvREFCNT_dec (sv); 1170 SvREFCNT_dec (sv);
946 sv = SvREFCNT_inc (POPs); 1171 sv = SvREFCNT_inc (POPs);
947 } 1172 }
948 else 1173 else
949 { 1174 {
950 AV *av = newAV (); 1175 AV *av = newAV ();
951 av_push (av, newSVuv (tag)); 1176 av_push (av, tag_sv);
952 av_push (av, sv); 1177 av_push (av, sv);
953 1178
954 HV *tagged_stash = !CBOR_SLOW || cbor_tagged_stash 1179 HV *tagged_stash = !CBOR_SLOW || cbor_tagged_stash
955 ? cbor_tagged_stash 1180 ? cbor_tagged_stash
956 : gv_stashpv ("CBOR::XS::Tagged" , 1); 1181 : gv_stashpv ("CBOR::XS::Tagged" , 1);
974static SV * 1199static SV *
975decode_sv (dec_t *dec) 1200decode_sv (dec_t *dec)
976{ 1201{
977 WANT (1); 1202 WANT (1);
978 1203
979 switch (*dec->cur >> 5) 1204 switch (*dec->cur >> MAJOR_SHIFT)
980 { 1205 {
981 case 0: // unsigned int 1206 case MAJOR_POS_INT >> MAJOR_SHIFT: return newSVuv (decode_uint (dec));
982 return newSVuv (decode_uint (dec)); 1207 case MAJOR_NEG_INT >> MAJOR_SHIFT: return newSViv (-1 - (IV)decode_uint (dec));
983 case 1: // negative int 1208 case MAJOR_BYTES >> MAJOR_SHIFT: return decode_str (dec, 0);
984 return newSViv (-1 - (IV)decode_uint (dec)); 1209 case MAJOR_TEXT >> MAJOR_SHIFT: return decode_str (dec, 1);
985 case 2: // octet string 1210 case MAJOR_ARRAY >> MAJOR_SHIFT: return decode_av (dec);
986 return decode_str (dec, 0); 1211 case MAJOR_MAP >> MAJOR_SHIFT: return decode_hv (dec);
987 case 3: // utf-8 string 1212 case MAJOR_TAG >> MAJOR_SHIFT: return decode_tagged (dec);
988 return decode_str (dec, 1); 1213
989 case 4: // array 1214 case MAJOR_MISC >> MAJOR_SHIFT:
990 return decode_av (dec);
991 case 5: // map
992 return decode_hv (dec);
993 case 6: // tag
994 return decode_tagged (dec);
995 case 7: // misc
996 switch (*dec->cur++ & 31) 1215 switch (*dec->cur++ & MINOR_MASK)
997 { 1216 {
998 case 20: 1217 case SIMPLE_FALSE:
999#if CBOR_SLOW 1218#if CBOR_SLOW
1000 types_false = get_bool ("Types::Serialiser::false"); 1219 types_false = get_bool ("Types::Serialiser::false");
1001#endif 1220#endif
1002 return newSVsv (types_false); 1221 return newSVsv (types_false);
1003 case 21: 1222 case SIMPLE_TRUE:
1004#if CBOR_SLOW 1223#if CBOR_SLOW
1005 types_true = get_bool ("Types::Serialiser::true"); 1224 types_true = get_bool ("Types::Serialiser::true");
1006#endif 1225#endif
1007 return newSVsv (types_true); 1226 return newSVsv (types_true);
1008 case 22: 1227 case SIMPLE_NULL:
1009 return newSVsv (&PL_sv_undef); 1228 return newSVsv (&PL_sv_undef);
1010 case 23: 1229 case SIMPLE_UNDEF:
1011#if CBOR_SLOW 1230#if CBOR_SLOW
1012 types_error = get_bool ("Types::Serialiser::error"); 1231 types_error = get_bool ("Types::Serialiser::error");
1013#endif 1232#endif
1014 return newSVsv (types_error); 1233 return newSVsv (types_error);
1015 1234
1016 case 25: 1235 case MISC_FLOAT16:
1017 { 1236 {
1018 WANT (2); 1237 WANT (2);
1019 1238
1020 uint16_t fp = (dec->cur[0] << 8) | dec->cur[1]; 1239 uint16_t fp = (dec->cur[0] << 8) | dec->cur[1];
1021 dec->cur += 2; 1240 dec->cur += 2;
1022 1241
1023 return newSVnv (ecb_binary16_to_float (fp)); 1242 return newSVnv (ecb_binary16_to_float (fp));
1024 } 1243 }
1025 1244
1026 case 26: 1245 case MISC_FLOAT32:
1027 { 1246 {
1028 uint32_t fp; 1247 uint32_t fp;
1029 WANT (4); 1248 WANT (4);
1030 memcpy (&fp, dec->cur, 4); 1249 memcpy (&fp, dec->cur, 4);
1031 dec->cur += 4; 1250 dec->cur += 4;
1034 fp = ecb_bswap32 (fp); 1253 fp = ecb_bswap32 (fp);
1035 1254
1036 return newSVnv (ecb_binary32_to_float (fp)); 1255 return newSVnv (ecb_binary32_to_float (fp));
1037 } 1256 }
1038 1257
1039 case 27: 1258 case MISC_FLOAT64:
1040 { 1259 {
1041 uint64_t fp; 1260 uint64_t fp;
1042 WANT (8); 1261 WANT (8);
1043 memcpy (&fp, dec->cur, 8); 1262 memcpy (&fp, dec->cur, 8);
1044 dec->cur += 8; 1263 dec->cur += 8;
1047 fp = ecb_bswap64 (fp); 1266 fp = ecb_bswap64 (fp);
1048 1267
1049 return newSVnv (ecb_binary64_to_double (fp)); 1268 return newSVnv (ecb_binary64_to_double (fp));
1050 } 1269 }
1051 1270
1052 // 0..19 unassigned 1271 // 0..19 unassigned simple
1053 // 24 reserved + unassigned (reserved values are not encodable) 1272 // 24 reserved + unassigned simple (reserved values are not encodable)
1273 // 28-30 unassigned misc
1274 // 31 break code
1054 default: 1275 default:
1055 ERR ("corrupted CBOR data (reserved/unassigned major 7 value)"); 1276 ERR ("corrupted CBOR data (reserved/unassigned/unexpected major 7 value)");
1056 } 1277 }
1057 1278
1058 break; 1279 break;
1059 } 1280 }
1060 1281
1063} 1284}
1064 1285
1065static SV * 1286static SV *
1066decode_cbor (SV *string, CBOR *cbor, char **offset_return) 1287decode_cbor (SV *string, CBOR *cbor, char **offset_return)
1067{ 1288{
1068 dec_t dec = { }; 1289 dec_t dec = { 0 };
1069 SV *sv; 1290 SV *sv;
1070 STRLEN len; 1291 STRLEN len;
1071 char *data = SvPVbyte (string, len); 1292 char *data = SvPVbyte (string, len);
1072 1293
1073 if (len > cbor->max_size && cbor->max_size) 1294 if (len > cbor->max_size && cbor->max_size)
1087 if (dec.cur != dec.end && !dec.err) 1308 if (dec.cur != dec.end && !dec.err)
1088 dec.err = "garbage after CBOR object"; 1309 dec.err = "garbage after CBOR object";
1089 1310
1090 if (dec.err) 1311 if (dec.err)
1091 { 1312 {
1313 if (dec.shareable)
1314 {
1315 // need to break cyclic links, which would all be in shareable
1316 int i;
1317 SV **svp;
1318
1319 for (i = av_len (dec.shareable) + 1; i--; )
1320 if ((svp = av_fetch (dec.shareable, i, 0)))
1321 sv_setsv (*svp, &PL_sv_undef);
1322 }
1323
1092 SvREFCNT_dec (sv); 1324 SvREFCNT_dec (sv);
1325
1326 if (dec.err_sv)
1327 sv_2mortal (dec.err_sv);
1328
1093 croak ("%s, at offset %d (octet 0x%02x)", dec.err, dec.cur - (U8 *)data, (int)(uint8_t)*dec.cur); 1329 croak ("%s, at offset %d (octet 0x%02x)", dec.err, dec.cur - (U8 *)data, (int)(uint8_t)*dec.cur);
1094 } 1330 }
1095 1331
1096 sv = sv_2mortal (sv); 1332 sv = sv_2mortal (sv);
1097 1333
1098 return sv; 1334 return sv;
1099} 1335}
1100 1336
1337/////////////////////////////////////////////////////////////////////////////
1338// incremental parser
1339
1340#define INCR_DONE(cbor) (AvFILLp (cbor->incr_count) < 0)
1341
1342// returns 0 for notyet, 1 for success or error
1343static int
1344incr_parse (CBOR *self, SV *cborstr)
1345{
1346 STRLEN cur;
1347 SvPV (cborstr, cur);
1348
1349 while (ecb_expect_true (self->incr_need <= cur))
1350 {
1351 // table of integer count bytes
1352 static I8 incr_len[MINOR_MASK + 1] = {
1353 0, 0, 0, 0, 0, 0, 0, 0,
1354 0, 0, 0, 0, 0, 0, 0, 0,
1355 0, 0, 0, 0, 0, 0, 0, 0,
1356 1, 2, 4, 8,-1,-1,-1,-2
1357 };
1358
1359 const U8 *p = SvPVX (cborstr) + self->incr_pos;
1360 U8 m = *p & MINOR_MASK;
1361 IV count = SvIVX (AvARRAY (self->incr_count)[AvFILLp (self->incr_count)]);
1362 I8 ilen = incr_len[m];
1363
1364 self->incr_need = self->incr_pos + 1;
1365
1366 if (ecb_expect_false (ilen < 0))
1367 {
1368 if (m != MINOR_INDEF)
1369 return 1; // error
1370
1371 if (*p == (MAJOR_MISC | MINOR_INDEF))
1372 {
1373 if (count >= 0)
1374 return 1; // error
1375
1376 count = 1;
1377 }
1378 else
1379 {
1380 av_push (self->incr_count, newSViv (-1)); //TODO: nest
1381 count = -1;
1382 }
1383 }
1384 else
1385 {
1386 self->incr_need += ilen;
1387 if (ecb_expect_false (self->incr_need > cur))
1388 return 0;
1389
1390 int major = *p >> MAJOR_SHIFT;
1391
1392 switch (major)
1393 {
1394 case MAJOR_TAG >> MAJOR_SHIFT:
1395 ++count; // tags merely prefix another value
1396 break;
1397
1398 case MAJOR_BYTES >> MAJOR_SHIFT:
1399 case MAJOR_TEXT >> MAJOR_SHIFT:
1400 case MAJOR_ARRAY >> MAJOR_SHIFT:
1401 case MAJOR_MAP >> MAJOR_SHIFT:
1402 {
1403 UV len;
1404
1405 if (ecb_expect_false (ilen))
1406 {
1407 len = 0;
1408
1409 do {
1410 len = (len << 8) | *++p;
1411 } while (--ilen);
1412 }
1413 else
1414 len = m;
1415
1416 switch (major)
1417 {
1418 case MAJOR_BYTES >> MAJOR_SHIFT:
1419 case MAJOR_TEXT >> MAJOR_SHIFT:
1420 self->incr_need += len;
1421 if (ecb_expect_false (self->incr_need > cur))
1422 return 0;
1423
1424 break;
1425
1426 case MAJOR_MAP >> MAJOR_SHIFT:
1427 len <<= 1;
1428 case MAJOR_ARRAY >> MAJOR_SHIFT:
1429 if (len)
1430 {
1431 av_push (self->incr_count, newSViv (len + 1)); //TODO: nest
1432 count = len + 1;
1433 }
1434 break;
1435 }
1436 }
1437 }
1438 }
1439
1440 self->incr_pos = self->incr_need;
1441
1442 if (count > 0)
1443 {
1444 while (!--count)
1445 {
1446 if (!AvFILLp (self->incr_count))
1447 return 1; // done
1448
1449 SvREFCNT_dec_NN (av_pop (self->incr_count));
1450 count = SvIVX (AvARRAY (self->incr_count)[AvFILLp (self->incr_count)]);
1451 }
1452
1453 SvIVX (AvARRAY (self->incr_count)[AvFILLp (self->incr_count)]) = count;
1454 }
1455 }
1456
1457 return 0;
1458}
1459
1460
1101///////////////////////////////////////////////////////////////////////////// 1461/////////////////////////////////////////////////////////////////////////////
1102// XS interface functions 1462// XS interface functions
1103 1463
1104MODULE = CBOR::XS PACKAGE = CBOR::XS 1464MODULE = CBOR::XS PACKAGE = CBOR::XS
1105 1465
1117 1477
1118 default_filter = newSVpv ("CBOR::XS::default_filter", 0); 1478 default_filter = newSVpv ("CBOR::XS::default_filter", 0);
1119 1479
1120 sv_cbor = newSVpv ("CBOR", 0); 1480 sv_cbor = newSVpv ("CBOR", 0);
1121 SvREADONLY_on (sv_cbor); 1481 SvREADONLY_on (sv_cbor);
1482
1483 assert (("STRLEN must be an unsigned type", 0 <= (STRLEN)-1));
1122} 1484}
1123 1485
1124PROTOTYPES: DISABLE 1486PROTOTYPES: DISABLE
1125 1487
1126void CLONE (...) 1488void CLONE (...)
1145void shrink (CBOR *self, int enable = 1) 1507void shrink (CBOR *self, int enable = 1)
1146 ALIAS: 1508 ALIAS:
1147 shrink = F_SHRINK 1509 shrink = F_SHRINK
1148 allow_unknown = F_ALLOW_UNKNOWN 1510 allow_unknown = F_ALLOW_UNKNOWN
1149 allow_sharing = F_ALLOW_SHARING 1511 allow_sharing = F_ALLOW_SHARING
1150 allow_stringref = F_ALLOW_STRINGREF 1512 allow_cycles = F_ALLOW_CYCLES
1513 forbid_objects = F_FORBID_OBJECTS
1514 pack_strings = F_PACK_STRINGS
1515 text_keys = F_TEXT_KEYS
1516 text_strings = F_TEXT_STRINGS
1517 validate_utf8 = F_VALIDATE_UTF8
1151 PPCODE: 1518 PPCODE:
1152{ 1519{
1153 if (enable) 1520 if (enable)
1154 self->flags |= ix; 1521 self->flags |= ix;
1155 else 1522 else
1161void get_shrink (CBOR *self) 1528void get_shrink (CBOR *self)
1162 ALIAS: 1529 ALIAS:
1163 get_shrink = F_SHRINK 1530 get_shrink = F_SHRINK
1164 get_allow_unknown = F_ALLOW_UNKNOWN 1531 get_allow_unknown = F_ALLOW_UNKNOWN
1165 get_allow_sharing = F_ALLOW_SHARING 1532 get_allow_sharing = F_ALLOW_SHARING
1166 get_allow_stringref = F_ALLOW_STRINGREF 1533 get_allow_cycles = F_ALLOW_CYCLES
1534 get_forbid_objects = F_FORBID_OBJECTS
1535 get_pack_strings = F_PACK_STRINGS
1536 get_text_keys = F_TEXT_KEYS
1537 get_text_strings = F_TEXT_STRINGS
1538 get_validate_utf8 = F_VALIDATE_UTF8
1167 PPCODE: 1539 PPCODE:
1168 XPUSHs (boolSV (self->flags & ix)); 1540 XPUSHs (boolSV (self->flags & ix));
1169 1541
1170void max_depth (CBOR *self, U32 max_depth = 0x80000000UL) 1542void max_depth (CBOR *self, U32 max_depth = 0x80000000UL)
1171 PPCODE: 1543 PPCODE:
1220 EXTEND (SP, 2); 1592 EXTEND (SP, 2);
1221 PUSHs (sv); 1593 PUSHs (sv);
1222 PUSHs (sv_2mortal (newSVuv (offset - SvPVX (cborstr)))); 1594 PUSHs (sv_2mortal (newSVuv (offset - SvPVX (cborstr))));
1223} 1595}
1224 1596
1597void incr_parse (CBOR *self, SV *cborstr)
1598 ALIAS:
1599 incr_parse_multiple = 1
1600 PPCODE:
1601{
1602 if (SvUTF8 (cborstr))
1603 sv_utf8_downgrade (cborstr, 0);
1604
1605 if (!self->incr_count)
1606 {
1607 self->incr_count = newAV ();
1608 self->incr_pos = 0;
1609 self->incr_need = 1;
1610
1611 av_push (self->incr_count, newSViv (1));
1612 }
1613
1614 do
1615 {
1616 if (!incr_parse (self, cborstr))
1617 {
1618 if (self->incr_need > self->max_size && self->max_size)
1619 croak ("attempted decode of CBOR text of %lu bytes size, but max_size is set to %lu",
1620 (unsigned long)self->incr_need, (unsigned long)self->max_size);
1621
1622 break;
1623 }
1624
1625 SV *sv;
1626 char *offset;
1627
1628 PUTBACK; sv = decode_cbor (cborstr, self, &offset); SPAGAIN;
1629 XPUSHs (sv);
1630
1631 sv_chop (cborstr, offset);
1632
1633 av_clear (self->incr_count);
1634 av_push (self->incr_count, newSViv (1));
1635
1636 self->incr_pos = 0;
1637 self->incr_need = self->incr_pos + 1;
1638 }
1639 while (ix);
1640}
1641
1642void incr_reset (CBOR *self)
1643 CODE:
1644{
1645 SvREFCNT_dec (self->incr_count);
1646 self->incr_count = 0;
1647}
1648
1225void DESTROY (CBOR *self) 1649void DESTROY (CBOR *self)
1226 PPCODE: 1650 PPCODE:
1227 cbor_free (self); 1651 cbor_free (self);
1228 1652
1229PROTOTYPES: ENABLE 1653PROTOTYPES: ENABLE
1230 1654
1231void encode_cbor (SV *scalar) 1655void encode_cbor (SV *scalar)
1656 ALIAS:
1657 encode_cbor = 0
1658 encode_cbor_sharing = F_ALLOW_SHARING
1232 PPCODE: 1659 PPCODE:
1233{ 1660{
1234 CBOR cbor; 1661 CBOR cbor;
1235 cbor_init (&cbor); 1662 cbor_init (&cbor);
1663 cbor.flags |= ix;
1236 PUTBACK; scalar = encode_cbor (scalar, &cbor); SPAGAIN; 1664 PUTBACK; scalar = encode_cbor (scalar, &cbor); SPAGAIN;
1237 XPUSHs (scalar); 1665 XPUSHs (scalar);
1238} 1666}
1239 1667
1240void decode_cbor (SV *cborstr) 1668void decode_cbor (SV *cborstr)

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines