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

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines