1 /* 2 * Copyright © 2007,2008,2009,2010 Red Hat, Inc. 3 * Copyright © 2012,2018 Google, Inc. 4 * Copyright © 2019 Facebook, Inc. 5 * 6 * This is part of HarfBuzz, a text shaping library. 7 * 8 * Permission is hereby granted, without written agreement and without 9 * license or royalty fees, to use, copy, modify, and distribute this 10 * software and its documentation for any purpose, provided that the 11 * above copyright notice and the following two paragraphs appear in 12 * all copies of this software. 13 * 14 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR 15 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 16 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN 17 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 18 * DAMAGE. 19 * 20 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, 21 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 22 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS 23 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO 24 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 25 * 26 * Red Hat Author(s): Behdad Esfahbod 27 * Google Author(s): Behdad Esfahbod 28 * Facebook Author(s): Behdad Esfahbod 29 */ 30 31 #ifndef HB_SERIALIZE_HH 32 #define HB_SERIALIZE_HH 33 34 #include "hb.hh" 35 #include "hb-blob.hh" 36 #include "hb-map.hh" 37 #include "hb-pool.hh" 38 39 40 /* 41 * Serialize 42 */ 43 44 enum hb_serialize_error_t { 45 HB_SERIALIZE_ERROR_NONE = 0x00000000u, 46 HB_SERIALIZE_ERROR_OTHER = 0x00000001u, 47 HB_SERIALIZE_ERROR_OFFSET_OVERFLOW = 0x00000002u, 48 HB_SERIALIZE_ERROR_OUT_OF_ROOM = 0x00000004u, 49 HB_SERIALIZE_ERROR_INT_OVERFLOW = 0x00000008u, 50 HB_SERIALIZE_ERROR_ARRAY_OVERFLOW = 0x00000010u 51 }; 52 HB_MARK_AS_FLAG_T (hb_serialize_error_t); 53 54 struct hb_serialize_context_t 55 { 56 typedef unsigned objidx_t; 57 58 enum whence_t { 59 Head, /* Relative to the current object head (default). */ 60 Tail, /* Relative to the current object tail after packed. */ 61 Absolute /* Absolute: from the start of the serialize buffer. */ 62 }; 63 64 65 66 struct object_t 67 { finihb_serialize_context_t::object_t68 void fini () { links.fini (); } 69 operator ==hb_serialize_context_t::object_t70 bool operator == (const object_t &o) const 71 { 72 return (tail - head == o.tail - o.head) 73 && (links.length == o.links.length) 74 && 0 == hb_memcmp (head, o.head, tail - head) 75 && links.as_bytes () == o.links.as_bytes (); 76 } hashhb_serialize_context_t::object_t77 uint32_t hash () const 78 { 79 return hb_bytes_t (head, tail - head).hash () ^ 80 links.as_bytes ().hash (); 81 } 82 83 struct link_t 84 { 85 unsigned width: 3; 86 bool is_signed: 1; 87 unsigned whence: 2; 88 unsigned position: 28; 89 unsigned bias; 90 objidx_t objidx; 91 }; 92 93 char *head; 94 char *tail; 95 hb_vector_t<link_t> links; 96 object_t *next; 97 }; 98 99 struct snapshot_t 100 { 101 char *head; 102 char *tail; 103 object_t *current; // Just for sanity check 104 unsigned num_links; 105 }; 106 snapshothb_serialize_context_t107 snapshot_t snapshot () 108 { return snapshot_t { head, tail, current, current->links.length }; } 109 hb_serialize_context_thb_serialize_context_t110 hb_serialize_context_t (void *start_, unsigned int size) : 111 start ((char *) start_), 112 end (start + size), 113 current (nullptr) 114 { reset (); } ~hb_serialize_context_thb_serialize_context_t115 ~hb_serialize_context_t () { fini (); } 116 finihb_serialize_context_t117 void fini () 118 { 119 for (object_t *_ : ++hb_iter (packed)) _->fini (); 120 packed.fini (); 121 this->packed_map.fini (); 122 123 while (current) 124 { 125 auto *_ = current; 126 current = current->next; 127 _->fini (); 128 } 129 object_pool.fini (); 130 } 131 in_errorhb_serialize_context_t132 bool in_error () const { return bool (errors); } 133 successfulhb_serialize_context_t134 bool successful () const { return !bool (errors); } 135 ran_out_of_roomhb_serialize_context_t136 HB_NODISCARD bool ran_out_of_room () const { return errors & HB_SERIALIZE_ERROR_OUT_OF_ROOM; } offset_overflowhb_serialize_context_t137 HB_NODISCARD bool offset_overflow () const { return errors & HB_SERIALIZE_ERROR_OFFSET_OVERFLOW; } only_offset_overflowhb_serialize_context_t138 HB_NODISCARD bool only_offset_overflow () const { return errors == HB_SERIALIZE_ERROR_OFFSET_OVERFLOW; } 139 resethb_serialize_context_t140 void reset (void *start_, unsigned int size) 141 { 142 start = (char*) start_; 143 end = start + size; 144 reset (); 145 current = nullptr; 146 } 147 resethb_serialize_context_t148 void reset () 149 { 150 this->errors = HB_SERIALIZE_ERROR_NONE; 151 this->head = this->start; 152 this->tail = this->end; 153 this->debug_depth = 0; 154 155 fini (); 156 this->packed.push (nullptr); 157 this->packed_map.init (); 158 } 159 check_successhb_serialize_context_t160 bool check_success (bool success, 161 hb_serialize_error_t err_type = HB_SERIALIZE_ERROR_OTHER) 162 { 163 return successful () 164 && (success || err (err_type)); 165 } 166 167 template <typename T1, typename T2> check_equalhb_serialize_context_t168 bool check_equal (T1 &&v1, T2 &&v2, hb_serialize_error_t err_type) 169 { 170 if ((long long) v1 != (long long) v2) 171 { 172 return err (err_type); 173 } 174 return true; 175 } 176 177 template <typename T1, typename T2> check_assignhb_serialize_context_t178 bool check_assign (T1 &v1, T2 &&v2, hb_serialize_error_t err_type) 179 { return check_equal (v1 = v2, v2, err_type); } 180 propagate_errorhb_serialize_context_t181 template <typename T> bool propagate_error (T &&obj) 182 { return check_success (!hb_deref (obj).in_error ()); } 183 propagate_errorhb_serialize_context_t184 template <typename T1, typename... Ts> bool propagate_error (T1 &&o1, Ts&&... os) 185 { return propagate_error (hb_forward<T1> (o1)) && 186 propagate_error (hb_forward<Ts> (os)...); } 187 188 /* To be called around main operation. */ 189 template <typename Type> start_serializehb_serialize_context_t190 Type *start_serialize () 191 { 192 DEBUG_MSG_LEVEL (SERIALIZE, this->start, 0, +1, 193 "start [%p..%p] (%lu bytes)", 194 this->start, this->end, 195 (unsigned long) (this->end - this->start)); 196 197 assert (!current); 198 return push<Type> (); 199 } end_serializehb_serialize_context_t200 void end_serialize () 201 { 202 DEBUG_MSG_LEVEL (SERIALIZE, this->start, 0, -1, 203 "end [%p..%p] serialized %u bytes; %s", 204 this->start, this->end, 205 (unsigned) (this->head - this->start), 206 successful () ? "successful" : "UNSUCCESSFUL"); 207 208 propagate_error (packed, packed_map); 209 210 if (unlikely (!current)) return; 211 if (unlikely (in_error())) 212 { 213 // Offset overflows that occur before link resolution cannot be handled 214 // by repacking, so set a more general error. 215 if (offset_overflow ()) err (HB_SERIALIZE_ERROR_OTHER); 216 return; 217 } 218 219 assert (!current->next); 220 221 /* Only "pack" if there exist other objects... Otherwise, don't bother. 222 * Saves a move. */ 223 if (packed.length <= 1) 224 return; 225 226 pop_pack (false); 227 228 resolve_links (); 229 } 230 231 template <typename Type = void> pushhb_serialize_context_t232 Type *push () 233 { 234 if (unlikely (in_error ())) return start_embed<Type> (); 235 236 object_t *obj = object_pool.alloc (); 237 if (unlikely (!obj)) 238 check_success (false); 239 else 240 { 241 obj->head = head; 242 obj->tail = tail; 243 obj->next = current; 244 current = obj; 245 } 246 return start_embed<Type> (); 247 } pop_discardhb_serialize_context_t248 void pop_discard () 249 { 250 object_t *obj = current; 251 if (unlikely (!obj)) return; 252 if (unlikely (in_error())) return; 253 254 current = current->next; 255 revert (obj->head, obj->tail); 256 obj->fini (); 257 object_pool.release (obj); 258 } 259 260 /* Set share to false when an object is unlikely sharable with others 261 * so not worth an attempt, or a contiguous table is serialized as 262 * multiple consecutive objects in the reverse order so can't be shared. 263 */ pop_packhb_serialize_context_t264 objidx_t pop_pack (bool share=true) 265 { 266 object_t *obj = current; 267 if (unlikely (!obj)) return 0; 268 if (unlikely (in_error())) return 0; 269 270 current = current->next; 271 obj->tail = head; 272 obj->next = nullptr; 273 unsigned len = obj->tail - obj->head; 274 head = obj->head; /* Rewind head. */ 275 276 if (!len) 277 { 278 assert (!obj->links.length); 279 return 0; 280 } 281 282 objidx_t objidx; 283 if (share) 284 { 285 objidx = packed_map.get (obj); 286 if (objidx) 287 { 288 obj->fini (); 289 return objidx; 290 } 291 } 292 293 tail -= len; 294 memmove (tail, obj->head, len); 295 296 obj->head = tail; 297 obj->tail = tail + len; 298 299 packed.push (obj); 300 301 if (unlikely (!propagate_error (packed))) 302 { 303 /* Obj wasn't successfully added to packed, so clean it up otherwise its 304 * links will be leaked. When we use constructor/destructors properly, we 305 * can remove these. */ 306 obj->fini (); 307 return 0; 308 } 309 310 objidx = packed.length - 1; 311 312 if (share) packed_map.set (obj, objidx); 313 propagate_error (packed_map); 314 315 return objidx; 316 } 317 reverthb_serialize_context_t318 void revert (snapshot_t snap) 319 { 320 if (unlikely (in_error ())) return; 321 assert (snap.current == current); 322 current->links.shrink (snap.num_links); 323 revert (snap.head, snap.tail); 324 } 325 reverthb_serialize_context_t326 void revert (char *snap_head, 327 char *snap_tail) 328 { 329 if (unlikely (in_error ())) return; 330 assert (snap_head <= head); 331 assert (tail <= snap_tail); 332 head = snap_head; 333 tail = snap_tail; 334 discard_stale_objects (); 335 } 336 discard_stale_objectshb_serialize_context_t337 void discard_stale_objects () 338 { 339 if (unlikely (in_error ())) return; 340 while (packed.length > 1 && 341 packed.tail ()->head < tail) 342 { 343 packed_map.del (packed.tail ()); 344 assert (!packed.tail ()->next); 345 packed.tail ()->fini (); 346 packed.pop (); 347 } 348 if (packed.length > 1) 349 assert (packed.tail ()->head == tail); 350 } 351 352 template <typename T> add_linkhb_serialize_context_t353 void add_link (T &ofs, objidx_t objidx, 354 whence_t whence = Head, 355 unsigned bias = 0) 356 { 357 if (unlikely (in_error ())) return; 358 359 if (!objidx) 360 return; 361 362 assert (current); 363 assert (current->head <= (const char *) &ofs); 364 365 auto& link = *current->links.push (); 366 367 link.width = sizeof (T); 368 link.is_signed = hb_is_signed (hb_unwrap_type (T)); 369 link.whence = (unsigned) whence; 370 link.position = (const char *) &ofs - current->head; 371 link.bias = bias; 372 link.objidx = objidx; 373 } 374 to_biashb_serialize_context_t375 unsigned to_bias (const void *base) const 376 { 377 if (unlikely (in_error ())) return 0; 378 if (!base) return 0; 379 assert (current); 380 assert (current->head <= (const char *) base); 381 return (const char *) base - current->head; 382 } 383 resolve_linkshb_serialize_context_t384 void resolve_links () 385 { 386 if (unlikely (in_error ())) return; 387 388 assert (!current); 389 assert (packed.length > 1); 390 391 for (const object_t* parent : ++hb_iter (packed)) 392 for (const object_t::link_t &link : parent->links) 393 { 394 const object_t* child = packed[link.objidx]; 395 if (unlikely (!child)) { err (HB_SERIALIZE_ERROR_OTHER); return; } 396 unsigned offset = 0; 397 switch ((whence_t) link.whence) { 398 case Head: offset = child->head - parent->head; break; 399 case Tail: offset = child->head - parent->tail; break; 400 case Absolute: offset = (head - start) + (child->head - tail); break; 401 } 402 403 assert (offset >= link.bias); 404 offset -= link.bias; 405 if (link.is_signed) 406 { 407 assert (link.width == 2 || link.width == 4); 408 if (link.width == 4) 409 assign_offset<int32_t> (parent, link, offset); 410 else 411 assign_offset<int16_t> (parent, link, offset); 412 } 413 else 414 { 415 assert (link.width == 2 || link.width == 3 || link.width == 4); 416 if (link.width == 4) 417 assign_offset<uint32_t> (parent, link, offset); 418 else if (link.width == 3) 419 assign_offset<uint32_t, 3> (parent, link, offset); 420 else 421 assign_offset<uint16_t> (parent, link, offset); 422 } 423 } 424 } 425 lengthhb_serialize_context_t426 unsigned int length () const 427 { 428 if (unlikely (!current)) return 0; 429 return this->head - current->head; 430 } 431 alignhb_serialize_context_t432 void align (unsigned int alignment) 433 { 434 unsigned int l = length () % alignment; 435 if (l) 436 allocate_size<void> (alignment - l); 437 } 438 439 template <typename Type = void> start_embedhb_serialize_context_t440 Type *start_embed (const Type *obj HB_UNUSED = nullptr) const 441 { return reinterpret_cast<Type *> (this->head); } 442 template <typename Type> start_embedhb_serialize_context_t443 Type *start_embed (const Type &obj) const 444 { return start_embed (hb_addressof (obj)); } 445 errhb_serialize_context_t446 bool err (hb_serialize_error_t err_type) 447 { 448 return !bool ((errors = (errors | err_type))); 449 } 450 451 template <typename Type> allocate_sizehb_serialize_context_t452 Type *allocate_size (unsigned int size) 453 { 454 if (unlikely (in_error ())) return nullptr; 455 456 if (this->tail - this->head < ptrdiff_t (size)) 457 { 458 err (HB_SERIALIZE_ERROR_OUT_OF_ROOM); 459 return nullptr; 460 } 461 memset (this->head, 0, size); 462 char *ret = this->head; 463 this->head += size; 464 return reinterpret_cast<Type *> (ret); 465 } 466 467 template <typename Type> allocate_minhb_serialize_context_t468 Type *allocate_min () 469 { return this->allocate_size<Type> (Type::min_size); } 470 471 template <typename Type> embedhb_serialize_context_t472 Type *embed (const Type *obj) 473 { 474 unsigned int size = obj->get_size (); 475 Type *ret = this->allocate_size<Type> (size); 476 if (unlikely (!ret)) return nullptr; 477 memcpy (ret, obj, size); 478 return ret; 479 } 480 template <typename Type> embedhb_serialize_context_t481 Type *embed (const Type &obj) 482 { return embed (hb_addressof (obj)); } 483 484 template <typename Type, typename ...Ts> auto _copyhb_serialize_context_t485 _copy (const Type &src, hb_priority<1>, Ts&&... ds) HB_RETURN 486 (Type *, src.copy (this, hb_forward<Ts> (ds)...)) 487 488 template <typename Type> auto 489 _copy (const Type &src, hb_priority<0>) -> decltype (&(hb_declval<Type> () = src)) 490 { 491 Type *ret = this->allocate_size<Type> (sizeof (Type)); 492 if (unlikely (!ret)) return nullptr; 493 *ret = src; 494 return ret; 495 } 496 497 /* Like embed, but active: calls obj.operator=() or obj.copy() to transfer data 498 * instead of memcpy(). */ 499 template <typename Type, typename ...Ts> 500 Type *copy (const Type &src, Ts&&... ds) 501 { return _copy (src, hb_prioritize, hb_forward<Ts> (ds)...); } 502 template <typename Type, typename ...Ts> 503 Type *copy (const Type *src, Ts&&... ds) 504 { return copy (*src, hb_forward<Ts> (ds)...); } 505 506 template<typename Iterator, 507 hb_requires (hb_is_iterator (Iterator)), 508 typename ...Ts> copy_allhb_serialize_context_t509 void copy_all (Iterator it, Ts&&... ds) 510 { for (decltype (*it) _ : it) copy (_, hb_forward<Ts> (ds)...); } 511 512 template <typename Type> operator <<hb_serialize_context_t513 hb_serialize_context_t& operator << (const Type &obj) & { embed (obj); return *this; } 514 515 template <typename Type> extend_sizehb_serialize_context_t516 Type *extend_size (Type *obj, unsigned int size) 517 { 518 if (unlikely (in_error ())) return nullptr; 519 520 assert (this->start <= (char *) obj); 521 assert ((char *) obj <= this->head); 522 assert ((char *) obj + size >= this->head); 523 if (unlikely (!this->allocate_size<Type> (((char *) obj) + size - this->head))) return nullptr; 524 return reinterpret_cast<Type *> (obj); 525 } 526 template <typename Type> extend_sizehb_serialize_context_t527 Type *extend_size (Type &obj, unsigned int size) 528 { return extend_size (hb_addressof (obj), size); } 529 530 template <typename Type> extend_minhb_serialize_context_t531 Type *extend_min (Type *obj) { return extend_size (obj, obj->min_size); } 532 template <typename Type> extend_minhb_serialize_context_t533 Type *extend_min (Type &obj) { return extend_min (hb_addressof (obj)); } 534 535 template <typename Type, typename ...Ts> 536 Type *extend (Type *obj, Ts&&... ds) 537 { return extend_size (obj, obj->get_size (hb_forward<Ts> (ds)...)); } 538 template <typename Type, typename ...Ts> 539 Type *extend (Type &obj, Ts&&... ds) 540 { return extend (hb_addressof (obj), hb_forward<Ts> (ds)...); } 541 542 /* Output routines. */ copy_byteshb_serialize_context_t543 hb_bytes_t copy_bytes () const 544 { 545 assert (successful ()); 546 /* Copy both items from head side and tail side... */ 547 unsigned int len = (this->head - this->start) 548 + (this->end - this->tail); 549 550 // If len is zero don't hb_malloc as the memory won't get properly 551 // cleaned up later. 552 if (!len) return hb_bytes_t (); 553 554 char *p = (char *) hb_malloc (len); 555 if (unlikely (!p)) return hb_bytes_t (); 556 557 memcpy (p, this->start, this->head - this->start); 558 memcpy (p + (this->head - this->start), this->tail, this->end - this->tail); 559 return hb_bytes_t (p, len); 560 } 561 template <typename Type> copyhb_serialize_context_t562 Type *copy () const 563 { return reinterpret_cast<Type *> ((char *) copy_bytes ().arrayZ); } copy_blobhb_serialize_context_t564 hb_blob_t *copy_blob () const 565 { 566 hb_bytes_t b = copy_bytes (); 567 return hb_blob_create (b.arrayZ, b.length, 568 HB_MEMORY_MODE_WRITABLE, 569 (char *) b.arrayZ, hb_free); 570 } 571 object_graphhb_serialize_context_t572 const hb_vector_t<object_t *>& object_graph() const 573 { return packed; } 574 575 private: 576 template <typename T, unsigned Size = sizeof (T)> assign_offsethb_serialize_context_t577 void assign_offset (const object_t* parent, const object_t::link_t &link, unsigned offset) 578 { 579 auto &off = * ((BEInt<T, Size> *) (parent->head + link.position)); 580 assert (0 == off); 581 check_assign (off, offset, HB_SERIALIZE_ERROR_OFFSET_OVERFLOW); 582 } 583 584 public: /* TODO Make private. */ 585 char *start, *head, *tail, *end; 586 unsigned int debug_depth; 587 hb_serialize_error_t errors; 588 589 private: 590 591 /* Object memory pool. */ 592 hb_pool_t<object_t> object_pool; 593 594 /* Stack of currently under construction objects. */ 595 object_t *current; 596 597 /* Stack of packed objects. Object 0 is always nil object. */ 598 hb_vector_t<object_t *> packed; 599 600 /* Map view of packed objects. */ 601 hb_hashmap_t<const object_t *, objidx_t, nullptr, 0> packed_map; 602 }; 603 604 #endif /* HB_SERIALIZE_HH */ 605