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 bool is_wide: 1; 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.free (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 static_assert (sizeof (T) == 2 || sizeof (T) == 4, ""); 358 if (unlikely (in_error ())) return; 359 360 if (!objidx) 361 return; 362 363 assert (current); 364 assert (current->head <= (const char *) &ofs); 365 366 auto& link = *current->links.push (); 367 368 link.is_wide = sizeof (T) == 4; 369 link.is_signed = hb_is_signed (hb_unwrap_type (T)); 370 link.whence = (unsigned) whence; 371 link.position = (const char *) &ofs - current->head; 372 link.bias = bias; 373 link.objidx = objidx; 374 } 375 to_biashb_serialize_context_t376 unsigned to_bias (const void *base) const 377 { 378 if (unlikely (in_error ())) return 0; 379 if (!base) return 0; 380 assert (current); 381 assert (current->head <= (const char *) base); 382 return (const char *) base - current->head; 383 } 384 resolve_linkshb_serialize_context_t385 void resolve_links () 386 { 387 if (unlikely (in_error ())) return; 388 389 assert (!current); 390 assert (packed.length > 1); 391 392 for (const object_t* parent : ++hb_iter (packed)) 393 for (const object_t::link_t &link : parent->links) 394 { 395 const object_t* child = packed[link.objidx]; 396 if (unlikely (!child)) { err (HB_SERIALIZE_ERROR_OTHER); return; } 397 unsigned offset = 0; 398 switch ((whence_t) link.whence) { 399 case Head: offset = child->head - parent->head; break; 400 case Tail: offset = child->head - parent->tail; break; 401 case Absolute: offset = (head - start) + (child->head - tail); break; 402 } 403 404 assert (offset >= link.bias); 405 offset -= link.bias; 406 if (link.is_signed) 407 { 408 if (link.is_wide) 409 assign_offset<int32_t> (parent, link, offset); 410 else 411 assign_offset<int16_t> (parent, link, offset); 412 } 413 else 414 { 415 if (link.is_wide) 416 assign_offset<uint32_t> (parent, link, offset); 417 else 418 assign_offset<uint16_t> (parent, link, offset); 419 } 420 } 421 } 422 lengthhb_serialize_context_t423 unsigned int length () const 424 { 425 if (unlikely (!current)) return 0; 426 return this->head - current->head; 427 } 428 alignhb_serialize_context_t429 void align (unsigned int alignment) 430 { 431 unsigned int l = length () % alignment; 432 if (l) 433 allocate_size<void> (alignment - l); 434 } 435 436 template <typename Type = void> start_embedhb_serialize_context_t437 Type *start_embed (const Type *obj HB_UNUSED = nullptr) const 438 { return reinterpret_cast<Type *> (this->head); } 439 template <typename Type> start_embedhb_serialize_context_t440 Type *start_embed (const Type &obj) const 441 { return start_embed (hb_addressof (obj)); } 442 errhb_serialize_context_t443 bool err (hb_serialize_error_t err_type) 444 { 445 return !bool ((errors = (errors | err_type))); 446 } 447 448 template <typename Type> allocate_sizehb_serialize_context_t449 Type *allocate_size (unsigned int size) 450 { 451 if (unlikely (in_error ())) return nullptr; 452 453 if (this->tail - this->head < ptrdiff_t (size)) 454 { 455 err (HB_SERIALIZE_ERROR_OUT_OF_ROOM); 456 return nullptr; 457 } 458 memset (this->head, 0, size); 459 char *ret = this->head; 460 this->head += size; 461 return reinterpret_cast<Type *> (ret); 462 } 463 464 template <typename Type> allocate_minhb_serialize_context_t465 Type *allocate_min () 466 { return this->allocate_size<Type> (Type::min_size); } 467 468 template <typename Type> embedhb_serialize_context_t469 Type *embed (const Type *obj) 470 { 471 unsigned int size = obj->get_size (); 472 Type *ret = this->allocate_size<Type> (size); 473 if (unlikely (!ret)) return nullptr; 474 memcpy (ret, obj, size); 475 return ret; 476 } 477 template <typename Type> embedhb_serialize_context_t478 Type *embed (const Type &obj) 479 { return embed (hb_addressof (obj)); } 480 481 template <typename Type, typename ...Ts> auto _copyhb_serialize_context_t482 _copy (const Type &src, hb_priority<1>, Ts&&... ds) HB_RETURN 483 (Type *, src.copy (this, hb_forward<Ts> (ds)...)) 484 485 template <typename Type> auto 486 _copy (const Type &src, hb_priority<0>) -> decltype (&(hb_declval<Type> () = src)) 487 { 488 Type *ret = this->allocate_size<Type> (sizeof (Type)); 489 if (unlikely (!ret)) return nullptr; 490 *ret = src; 491 return ret; 492 } 493 494 /* Like embed, but active: calls obj.operator=() or obj.copy() to transfer data 495 * instead of memcpy(). */ 496 template <typename Type, typename ...Ts> copyhb_serialize_context_t497 Type *copy (const Type &src, Ts&&... ds) 498 { return _copy (src, hb_prioritize, hb_forward<Ts> (ds)...); } 499 template <typename Type, typename ...Ts> copyhb_serialize_context_t500 Type *copy (const Type *src, Ts&&... ds) 501 { return copy (*src, hb_forward<Ts> (ds)...); } 502 503 template<typename Iterator, 504 hb_requires (hb_is_iterator (Iterator)), 505 typename ...Ts> copy_allhb_serialize_context_t506 void copy_all (Iterator it, Ts&&... ds) 507 { for (decltype (*it) _ : it) copy (_, hb_forward<Ts> (ds)...); } 508 509 template <typename Type> operator <<hb_serialize_context_t510 hb_serialize_context_t& operator << (const Type &obj) & { embed (obj); return *this; } 511 512 template <typename Type> extend_sizehb_serialize_context_t513 Type *extend_size (Type *obj, unsigned int size) 514 { 515 if (unlikely (in_error ())) return nullptr; 516 517 assert (this->start <= (char *) obj); 518 assert ((char *) obj <= this->head); 519 assert ((char *) obj + size >= this->head); 520 if (unlikely (!this->allocate_size<Type> (((char *) obj) + size - this->head))) return nullptr; 521 return reinterpret_cast<Type *> (obj); 522 } 523 template <typename Type> extend_sizehb_serialize_context_t524 Type *extend_size (Type &obj, unsigned int size) 525 { return extend_size (hb_addressof (obj), size); } 526 527 template <typename Type> extend_minhb_serialize_context_t528 Type *extend_min (Type *obj) { return extend_size (obj, obj->min_size); } 529 template <typename Type> extend_minhb_serialize_context_t530 Type *extend_min (Type &obj) { return extend_min (hb_addressof (obj)); } 531 532 template <typename Type, typename ...Ts> extendhb_serialize_context_t533 Type *extend (Type *obj, Ts&&... ds) 534 { return extend_size (obj, obj->get_size (hb_forward<Ts> (ds)...)); } 535 template <typename Type, typename ...Ts> extendhb_serialize_context_t536 Type *extend (Type &obj, Ts&&... ds) 537 { return extend (hb_addressof (obj), hb_forward<Ts> (ds)...); } 538 539 /* Output routines. */ copy_byteshb_serialize_context_t540 hb_bytes_t copy_bytes () const 541 { 542 assert (successful ()); 543 /* Copy both items from head side and tail side... */ 544 unsigned int len = (this->head - this->start) 545 + (this->end - this->tail); 546 547 char *p = (char *) malloc (len); 548 if (unlikely (!p)) return hb_bytes_t (); 549 550 memcpy (p, this->start, this->head - this->start); 551 memcpy (p + (this->head - this->start), this->tail, this->end - this->tail); 552 return hb_bytes_t (p, len); 553 } 554 template <typename Type> copyhb_serialize_context_t555 Type *copy () const 556 { return reinterpret_cast<Type *> ((char *) copy_bytes ().arrayZ); } copy_blobhb_serialize_context_t557 hb_blob_t *copy_blob () const 558 { 559 hb_bytes_t b = copy_bytes (); 560 return hb_blob_create (b.arrayZ, b.length, 561 HB_MEMORY_MODE_WRITABLE, 562 (char *) b.arrayZ, free); 563 } 564 object_graphhb_serialize_context_t565 const hb_vector_t<object_t *>& object_graph() const 566 { return packed; } 567 568 private: 569 template <typename T> assign_offsethb_serialize_context_t570 void assign_offset (const object_t* parent, const object_t::link_t &link, unsigned offset) 571 { 572 auto &off = * ((BEInt<T> *) (parent->head + link.position)); 573 assert (0 == off); 574 check_assign (off, offset, HB_SERIALIZE_ERROR_OFFSET_OVERFLOW); 575 } 576 577 public: /* TODO Make private. */ 578 char *start, *head, *tail, *end; 579 unsigned int debug_depth; 580 hb_serialize_error_t errors; 581 582 private: 583 584 /* Object memory pool. */ 585 hb_pool_t<object_t> object_pool; 586 587 /* Stack of currently under construction objects. */ 588 object_t *current; 589 590 /* Stack of packed objects. Object 0 is always nil object. */ 591 hb_vector_t<object_t *> packed; 592 593 /* Map view of packed objects. */ 594 hb_hashmap_t<const object_t *, objidx_t, nullptr, 0> packed_map; 595 }; 596 597 #endif /* HB_SERIALIZE_HH */ 598