src/hb-serialize.hh

   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   {
  68     void fini () {
  69       real_links.fini ();
  70       virtual_links.fini ();
  71     }
  72
  73     bool operator == (const object_t &o) const
  74     {
  75       // Virtual links aren't considered for equality since they don't affect the functionality
  76       // of the object.
  77       return (tail - head == o.tail - o.head)
  78           && (real_links.length == o.real_links.length)
  79           && 0 == hb_memcmp (head, o.head, tail - head)
  80           && real_links.as_bytes () == o.real_links.as_bytes ();
  81     }
  82     uint32_t hash () const
  83     {
  84       // Virtual links aren't considered for equality since they don't affect the functionality
  85       // of the object.
  86       return hb_bytes_t (head, tail - head).hash () ^
  87           real_links.as_bytes ().hash ();
  88     }
  89
  90     struct link_t
  91     {
  92       unsigned width: 3;
  93       bool is_signed: 1;
  94       unsigned whence: 2;
  95       unsigned position: 28;
  96       unsigned bias;
  97       objidx_t objidx;
  98     };
  99
 100     char *head;
 101     char *tail;
 102     hb_vector_t<link_t> real_links;
 103     hb_vector_t<link_t> virtual_links;
 104     object_t *next;
 105
 106     auto all_links () const HB_AUTO_RETURN
 107         (( hb_concat (this->real_links, this->virtual_links) ));
 108     auto all_links_writer () HB_AUTO_RETURN
 109         (( hb_concat (this->real_links.writer (), this->virtual_links.writer ()) ));
 110   };
 111
 112   struct snapshot_t
 113   {
 114     char *head;
 115     char *tail;
 116     object_t *current; // Just for sanity check
 117     unsigned num_real_links;
 118     unsigned num_virtual_links;
 119     hb_serialize_error_t errors;
 120   };
 121
 122   snapshot_t snapshot ()
 123   { return snapshot_t {
 124       head, tail, current, current->real_links.length, current->virtual_links.length, errors }; }
 125
 126   hb_serialize_context_t (void *start_, unsigned int size) :
 127     start ((char *) start_),
 128     end (start + size),
 129     current (nullptr)
 130   { reset (); }
 131   ~hb_serialize_context_t () { fini (); }
 132
 133   void fini ()
 134   {
 135     for (object_t *_ : ++hb_iter (packed)) _->fini ();
 136     packed.fini ();
 137     this->packed_map.fini ();
 138
 139     while (current)
 140     {
 141       auto *_ = current;
 142       current = current->next;
 143       _->fini ();
 144     }
 145     object_pool.fini ();
 146   }
 147
 148   bool in_error () const { return bool (errors); }
 149
 150   bool successful () const { return !bool (errors); }
 151
 152   HB_NODISCARD bool ran_out_of_room () const { return errors & HB_SERIALIZE_ERROR_OUT_OF_ROOM; }
 153   HB_NODISCARD bool offset_overflow () const { return errors & HB_SERIALIZE_ERROR_OFFSET_OVERFLOW; }
 154   HB_NODISCARD bool only_offset_overflow () const { return errors == HB_SERIALIZE_ERROR_OFFSET_OVERFLOW; }
 155   HB_NODISCARD bool only_overflow () const
 156   {
 157     return errors == HB_SERIALIZE_ERROR_OFFSET_OVERFLOW
 158         || errors == HB_SERIALIZE_ERROR_INT_OVERFLOW
 159         || errors == HB_SERIALIZE_ERROR_ARRAY_OVERFLOW;
 160   }
 161
 162   void reset (void *start_, unsigned int size)
 163   {
 164     start = (char*) start_;
 165     end = start + size;
 166     reset ();
 167     current = nullptr;
 168   }
 169
 170   void reset ()
 171   {
 172     this->errors = HB_SERIALIZE_ERROR_NONE;
 173     this->head = this->start;
 174     this->tail = this->end;
 175     this->debug_depth = 0;
 176
 177     fini ();
 178     this->packed.push (nullptr);
 179     this->packed_map.init ();
 180   }
 181
 182   bool check_success (bool success,
 183                       hb_serialize_error_t err_type = HB_SERIALIZE_ERROR_OTHER)
 184   {
 185     return successful ()
 186         && (success || err (err_type));
 187   }
 188
 189   template <typename T1, typename T2>
 190   bool check_equal (T1 &&v1, T2 &&v2, hb_serialize_error_t err_type)
 191   {
 192     if ((long long) v1 != (long long) v2)
 193     {
 194       return err (err_type);
 195     }
 196     return true;
 197   }
 198
 199   template <typename T1, typename T2>
 200   bool check_assign (T1 &v1, T2 &&v2, hb_serialize_error_t err_type)
 201   { return check_equal (v1 = v2, v2, err_type); }
 202
 203   template <typename T> bool propagate_error (T &&obj)
 204   { return check_success (!hb_deref (obj).in_error ()); }
 205
 206   template <typename T1, typename... Ts> bool propagate_error (T1 &&o1, Ts&&... os)
 207   { return propagate_error (std::forward<T1> (o1)) &&
 208            propagate_error (std::forward<Ts> (os)...); }
 209
 210   /* To be called around main operation. */
 211   template <typename Type>
 212   Type *start_serialize ()
 213   {
 214     DEBUG_MSG_LEVEL (SERIALIZE, this->start, 0, +1,
 215                      "start [%p..%p] (%lu bytes)",
 216                      this->start, this->end,
 217                      (unsigned long) (this->end - this->start));
 218
 219     assert (!current);
 220     return push<Type> ();
 221   }
 222   void end_serialize ()
 223   {
 224     DEBUG_MSG_LEVEL (SERIALIZE, this->start, 0, -1,
 225                      "end [%p..%p] serialized %u bytes; %s",
 226                      this->start, this->end,
 227                      (unsigned) (this->head - this->start),
 228                      successful () ? "successful" : "UNSUCCESSFUL");
 229
 230     propagate_error (packed, packed_map);
 231
 232     if (unlikely (!current)) return;
 233     if (unlikely (in_error()))
 234     {
 235       // Offset overflows that occur before link resolution cannot be handled
 236       // by repacking, so set a more general error.
 237       if (offset_overflow ()) err (HB_SERIALIZE_ERROR_OTHER);
 238       return;
 239     }
 240
 241     assert (!current->next);
 242
 243     /* Only "pack" if there exist other objects... Otherwise, don't bother.
 244      * Saves a move. */
 245     if (packed.length <= 1)
 246       return;
 247
 248     pop_pack (false);
 249
 250     resolve_links ();
 251   }
 252
 253   template <typename Type = void>
 254   Type *push ()
 255   {
 256     if (unlikely (in_error ())) return start_embed<Type> ();
 257
 258     object_t *obj = object_pool.alloc ();
 259     if (unlikely (!obj))
 260       check_success (false);
 261     else
 262     {
 263       obj->head = head;
 264       obj->tail = tail;
 265       obj->next = current;
 266       current = obj;
 267     }
 268     return start_embed<Type> ();
 269   }
 270   void pop_discard ()
 271   {
 272     object_t *obj = current;
 273     if (unlikely (!obj)) return;
 274     if (unlikely (in_error())) return;
 275
 276     current = current->next;
 277     revert (obj->head, obj->tail);
 278     obj->fini ();
 279     object_pool.release (obj);
 280   }
 281
 282   /* Set share to false when an object is unlikely shareable with others
 283    * so not worth an attempt, or a contiguous table is serialized as
 284    * multiple consecutive objects in the reverse order so can't be shared.
 285    */
 286   objidx_t pop_pack (bool share=true)
 287   {
 288     object_t *obj = current;
 289     if (unlikely (!obj)) return 0;
 290     if (unlikely (in_error())) return 0;
 291
 292     current = current->next;
 293     obj->tail = head;
 294     obj->next = nullptr;
 295     unsigned len = obj->tail - obj->head;
 296     head = obj->head; /* Rewind head. */
 297
 298     if (!len)
 299     {
 300       assert (!obj->real_links.length);
 301       assert (!obj->virtual_links.length);
 302       return 0;
 303     }
 304
 305     objidx_t objidx;
 306     if (share)
 307     {
 308       objidx = packed_map.get (obj);
 309       if (objidx)
 310       {
 311         merge_virtual_links (obj, objidx);
 312         obj->fini ();
 313         return objidx;
 314       }
 315     }
 316
 317     tail -= len;
 318     memmove (tail, obj->head, len);
 319
 320     obj->head = tail;
 321     obj->tail = tail + len;
 322
 323     packed.push (obj);
 324
 325     if (unlikely (!propagate_error (packed)))
 326     {
 327       /* Obj wasn't successfully added to packed, so clean it up otherwise its
 328        * links will be leaked. When we use constructor/destructors properly, we
 329        * can remove these. */
 330       obj->fini ();
 331       return 0;
 332     }
 333
 334     objidx = packed.length - 1;
 335
 336     if (share) packed_map.set (obj, objidx);
 337     propagate_error (packed_map);
 338
 339     return objidx;
 340   }
 341
 342   void revert (snapshot_t snap)
 343   {
 344     // Overflows that happened after the snapshot will be erased by the revert.
 345     if (unlikely (in_error () && !only_overflow ())) return;
 346     assert (snap.current == current);
 347     current->real_links.shrink (snap.num_real_links);
 348     current->virtual_links.shrink (snap.num_virtual_links);
 349     errors = snap.errors;
 350     revert (snap.head, snap.tail);
 351   }
 352
 353   void revert (char *snap_head,
 354                char *snap_tail)
 355   {
 356     if (unlikely (in_error ())) return;
 357     assert (snap_head <= head);
 358     assert (tail <= snap_tail);
 359     head = snap_head;
 360     tail = snap_tail;
 361     discard_stale_objects ();
 362   }
 363
 364   void discard_stale_objects ()
 365   {
 366     if (unlikely (in_error ())) return;
 367     while (packed.length > 1 &&
 368            packed.tail ()->head < tail)
 369     {
 370       packed_map.del (packed.tail ());
 371       assert (!packed.tail ()->next);
 372       packed.tail ()->fini ();
 373       packed.pop ();
 374     }
 375     if (packed.length > 1)
 376       assert (packed.tail ()->head == tail);
 377   }
 378
 379   // Adds a virtual link from the current object to objidx. A virtual link is not associated with
 380   // an actual offset field. They are solely used to enforce ordering constraints between objects.
 381   // Adding a virtual link from object a to object b will ensure that object b is always packed after
 382   // object a in the final serialized order.
 383   //
 384   // This is useful in certain situations where there needs to be a specific ordering in the
 385   // final serialization. Such as when platform bugs require certain orderings, or to provide
 386   //  guidance to the repacker for better offset overflow resolution.
 387   void add_virtual_link (objidx_t objidx)
 388   {
 389     if (unlikely (in_error ())) return;
 390
 391     if (!objidx)
 392       return;
 393
 394     assert (current);
 395
 396     auto& link = *current->virtual_links.push ();
 397     if (current->virtual_links.in_error ())
 398       err (HB_SERIALIZE_ERROR_OTHER);
 399
 400     link.width = 0;
 401     link.objidx = objidx;
 402     link.is_signed = 0;
 403     link.whence = 0;
 404     link.position = 0;
 405     link.bias = 0;
 406   }
 407
 408   template <typename T>
 409   void add_link (T &ofs, objidx_t objidx,
 410                  whence_t whence = Head,
 411                  unsigned bias = 0)
 412   {
 413     if (unlikely (in_error ())) return;
 414
 415     if (!objidx)
 416       return;
 417
 418     assert (current);
 419     assert (current->head <= (const char *) &ofs);
 420
 421     auto& link = *current->real_links.push ();
 422     if (current->real_links.in_error ())
 423       err (HB_SERIALIZE_ERROR_OTHER);
 424
 425     link.width = sizeof (T);
 426     link.objidx = objidx;
 427     if (unlikely (!sizeof (T)))
 428     {
 429       // This link is not associated with an actual offset and exists merely to enforce
 430       // an ordering constraint.
 431       link.is_signed = 0;
 432       link.whence = 0;
 433       link.position = 0;
 434       link.bias = 0;
 435       return;
 436     }
 437
 438     link.is_signed = std::is_signed<hb_unwrap_type (T)>::value;
 439     link.whence = (unsigned) whence;
 440     link.position = (const char *) &ofs - current->head;
 441     link.bias = bias;
 442   }
 443
 444   unsigned to_bias (const void *base) const
 445   {
 446     if (unlikely (in_error ())) return 0;
 447     if (!base) return 0;
 448     assert (current);
 449     assert (current->head <= (const char *) base);
 450     return (const char *) base - current->head;
 451   }
 452
 453   void resolve_links ()
 454   {
 455     if (unlikely (in_error ())) return;
 456
 457     assert (!current);
 458     assert (packed.length > 1);
 459
 460     for (const object_t* parent : ++hb_iter (packed))
 461       for (const object_t::link_t &link : parent->real_links)
 462       {
 463         const object_t* child = packed[link.objidx];
 464         if (unlikely (!child)) { err (HB_SERIALIZE_ERROR_OTHER); return; }
 465         unsigned offset = 0;
 466         switch ((whence_t) link.whence) {
 467         case Head:     offset = child->head - parent->head; break;
 468         case Tail:     offset = child->head - parent->tail; break;
 469         case Absolute: offset = (head - start) + (child->head - tail); break;
 470         }
 471
 472         assert (offset >= link.bias);
 473         offset -= link.bias;
 474         if (link.is_signed)
 475         {
 476           assert (link.width == 2 || link.width == 4);
 477           if (link.width == 4)
 478             assign_offset<int32_t> (parent, link, offset);
 479           else
 480             assign_offset<int16_t> (parent, link, offset);
 481         }
 482         else
 483         {
 484           assert (link.width == 2 || link.width == 3 || link.width == 4);
 485           if (link.width == 4)
 486             assign_offset<uint32_t> (parent, link, offset);
 487           else if (link.width == 3)
 488             assign_offset<uint32_t, 3> (parent, link, offset);
 489           else
 490             assign_offset<uint16_t> (parent, link, offset);
 491         }
 492       }
 493   }
 494
 495   unsigned int length () const
 496   {
 497     if (unlikely (!current)) return 0;
 498     return this->head - current->head;
 499   }
 500
 501   void align (unsigned int alignment)
 502   {
 503     unsigned int l = length () % alignment;
 504     if (l)
 505       allocate_size<void> (alignment - l);
 506   }
 507
 508   template <typename Type = void>
 509   Type *start_embed (const Type *obj HB_UNUSED = nullptr) const
 510   { return reinterpret_cast<Type *> (this->head); }
 511   template <typename Type>
 512   Type *start_embed (const Type &obj) const
 513   { return start_embed (std::addressof (obj)); }
 514
 515   bool err (hb_serialize_error_t err_type)
 516   {
 517     return !bool ((errors = (errors | err_type)));
 518   }
 519
 520   template <typename Type>
 521   Type *allocate_size (size_t size)
 522   {
 523     if (unlikely (in_error ())) return nullptr;
 524
 525     if (unlikely (size > INT_MAX || this->tail - this->head < ptrdiff_t (size)))
 526     {
 527       err (HB_SERIALIZE_ERROR_OUT_OF_ROOM);
 528       return nullptr;
 529     }
 530     hb_memset (this->head, 0, size);
 531     char *ret = this->head;
 532     this->head += size;
 533     return reinterpret_cast<Type *> (ret);
 534   }
 535
 536   template <typename Type>
 537   Type *allocate_min ()
 538   { return this->allocate_size<Type> (Type::min_size); }
 539
 540   template <typename Type>
 541   Type *embed (const Type *obj)
 542   {
 543     unsigned int size = obj->get_size ();
 544     Type *ret = this->allocate_size<Type> (size);
 545     if (unlikely (!ret)) return nullptr;
 546     memcpy (ret, obj, size);
 547     return ret;
 548   }
 549   template <typename Type>
 550   Type *embed (const Type &obj)
 551   { return embed (std::addressof (obj)); }
 552
 553   template <typename Type, typename ...Ts> auto
 554   _copy (const Type &src, hb_priority<1>, Ts&&... ds) HB_RETURN
 555   (Type *, src.copy (this, std::forward<Ts> (ds)...))
 556
 557   template <typename Type> auto
 558   _copy (const Type &src, hb_priority<0>) -> decltype (&(hb_declval<Type> () = src))
 559   {
 560     Type *ret = this->allocate_size<Type> (sizeof (Type));
 561     if (unlikely (!ret)) return nullptr;
 562     *ret = src;
 563     return ret;
 564   }
 565
 566   /* Like embed, but active: calls obj.operator=() or obj.copy() to transfer data
 567    * instead of memcpy(). */
 568   template <typename Type, typename ...Ts>
 569   Type *copy (const Type &src, Ts&&... ds)
 570   { return _copy (src, hb_prioritize, std::forward<Ts> (ds)...); }
 571   template <typename Type, typename ...Ts>
 572   Type *copy (const Type *src, Ts&&... ds)
 573   { return copy (*src, std::forward<Ts> (ds)...); }
 574
 575   template<typename Iterator,
 576            hb_requires (hb_is_iterator (Iterator)),
 577            typename ...Ts>
 578   void copy_all (Iterator it, Ts&&... ds)
 579   { for (decltype (*it) _ : it) copy (_, std::forward<Ts> (ds)...); }
 580
 581   template <typename Type>
 582   hb_serialize_context_t& operator << (const Type &obj) & { embed (obj); return *this; }
 583
 584   template <typename Type>
 585   Type *extend_size (Type *obj, size_t size)
 586   {
 587     if (unlikely (in_error ())) return nullptr;
 588
 589     assert (this->start <= (char *) obj);
 590     assert ((char *) obj <= this->head);
 591     assert ((size_t) (this->head - (char *) obj) <= size);
 592     if (unlikely (((char *) obj + size < (char *) obj) ||
 593                   !this->allocate_size<Type> (((char *) obj) + size - this->head))) return nullptr;
 594     return reinterpret_cast<Type *> (obj);
 595   }
 596   template <typename Type>
 597   Type *extend_size (Type &obj, size_t size)
 598   { return extend_size (std::addressof (obj), size); }
 599
 600   template <typename Type>
 601   Type *extend_min (Type *obj) { return extend_size (obj, obj->min_size); }
 602   template <typename Type>
 603   Type *extend_min (Type &obj) { return extend_min (std::addressof (obj)); }
 604
 605   template <typename Type, typename ...Ts>
 606   Type *extend (Type *obj, Ts&&... ds)
 607   { return extend_size (obj, obj->get_size (std::forward<Ts> (ds)...)); }
 608   template <typename Type, typename ...Ts>
 609   Type *extend (Type &obj, Ts&&... ds)
 610   { return extend (std::addressof (obj), std::forward<Ts> (ds)...); }
 611
 612   /* Output routines. */
 613   hb_bytes_t copy_bytes () const
 614   {
 615     assert (successful ());
 616     /* Copy both items from head side and tail side... */
 617     unsigned int len = (this->head - this->start)
 618                      + (this->end  - this->tail);
 619
 620     // If len is zero don't hb_malloc as the memory won't get properly
 621     // cleaned up later.
 622     if (!len) return hb_bytes_t ();
 623
 624     char *p = (char *) hb_malloc (len);
 625     if (unlikely (!p)) return hb_bytes_t ();
 626
 627     memcpy (p, this->start, this->head - this->start);
 628     memcpy (p + (this->head - this->start), this->tail, this->end - this->tail);
 629     return hb_bytes_t (p, len);
 630   }
 631   template <typename Type>
 632   Type *copy () const
 633   { return reinterpret_cast<Type *> ((char *) copy_bytes ().arrayZ); }
 634   hb_blob_t *copy_blob () const
 635   {
 636     hb_bytes_t b = copy_bytes ();
 637     return hb_blob_create (b.arrayZ, b.length,
 638                            HB_MEMORY_MODE_WRITABLE,
 639                            (char *) b.arrayZ, hb_free);
 640   }
 641
 642   const hb_vector_t<object_t *>& object_graph() const
 643   { return packed; }
 644
 645   private:
 646   template <typename T, unsigned Size = sizeof (T)>
 647   void assign_offset (const object_t* parent, const object_t::link_t &link, unsigned offset)
 648   {
 649     auto &off = * ((BEInt<T, Size> *) (parent->head + link.position));
 650     assert (0 == off);
 651     check_assign (off, offset, HB_SERIALIZE_ERROR_OFFSET_OVERFLOW);
 652   }
 653
 654   public: /* TODO Make private. */
 655   char *start, *head, *tail, *end;
 656   unsigned int debug_depth;
 657   hb_serialize_error_t errors;
 658
 659   private:
 660
 661   void merge_virtual_links (const object_t* from, objidx_t to_idx) {
 662     object_t* to = packed[to_idx];
 663     for (const auto& l : from->virtual_links) {
 664       to->virtual_links.push (l);
 665     }
 666   }
 667
 668   /* Object memory pool. */
 669   hb_pool_t<object_t> object_pool;
 670
 671   /* Stack of currently under construction objects. */
 672   object_t *current;
 673
 674   /* Stack of packed objects.  Object 0 is always nil object. */
 675   hb_vector_t<object_t *> packed;
 676
 677   /* Map view of packed objects. */
 678   hb_hashmap_t<const object_t *, objidx_t,
 679                const object_t *, objidx_t,
 680                nullptr, 0> packed_map;
 681 };
 682
 683 #endif /* HB_SERIALIZE_HH */