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 struct hb_serialize_context_t
  45 {
  46   typedef unsigned objidx_t;
  47
  48   struct range_t
  49   {
  50     char *head, *tail;
  51   };
  52
  53   struct object_t : range_t
  54   {
  55     void fini () { links.fini (); }
  56
  57     bool operator == (const object_t &o) const
  58     {
  59       return (tail - head == o.tail - o.head)
  60           && (links.length == o.links.length)
  61           && 0 == hb_memcmp (head, o.head, tail - head)
  62           && links.as_bytes () == o.links.as_bytes ();
  63     }
  64     uint32_t hash () const
  65     {
  66       return hb_bytes_t (head, tail - head).hash () ^
  67              links.as_bytes ().hash ();
  68     }
  69
  70     struct link_t
  71     {
  72       bool is_wide: 1;
  73       unsigned position : 31;
  74       unsigned bias;
  75       objidx_t objidx;
  76     };
  77
  78     hb_vector_t<link_t> links;
  79     object_t *next;
  80   };
  81
  82   range_t snapshot () { range_t s = {head, tail} ; return s; }
  83
  84
  85   hb_serialize_context_t (void *start_, unsigned int size) :
  86     start ((char *) start_),
  87     end (start + size),
  88     current (nullptr)
  89   { reset (); }
  90   ~hb_serialize_context_t () { fini (); }
  91
  92   void fini ()
  93   {
  94     for (object_t *_ : ++hb_iter (packed)) _->fini ();
  95     packed.fini ();
  96     this->packed_map.fini ();
  97
  98     while (current)
  99     {
 100       auto *_ = current;
 101       current = current->next;
 102       _->fini ();
 103     }
 104     object_pool.fini ();
 105   }
 106
 107   bool in_error () const { return !this->successful; }
 108
 109   void reset ()
 110   {
 111     this->successful = true;
 112     this->ran_out_of_room = false;
 113     this->head = this->start;
 114     this->tail = this->end;
 115     this->debug_depth = 0;
 116
 117     fini ();
 118     this->packed.push (nullptr);
 119   }
 120
 121   bool check_success (bool success)
 122   { return this->successful && (success || (err_other_error (), false)); }
 123
 124   template <typename T1, typename T2>
 125   bool check_equal (T1 &&v1, T2 &&v2)
 126   { return check_success (v1 == v2); }
 127
 128   template <typename T1, typename T2>
 129   bool check_assign (T1 &v1, T2 &&v2)
 130   { return check_equal (v1 = v2, v2); }
 131
 132   template <typename T> bool propagate_error (T &&obj)
 133   { return check_success (!hb_deref (obj).in_error ()); }
 134
 135   template <typename T1, typename... Ts> bool propagate_error (T1 &&o1, Ts&&... os)
 136   { return propagate_error (hb_forward<T1> (o1)) &&
 137            propagate_error (hb_forward<Ts> (os)...); }
 138
 139   /* To be called around main operation. */
 140   template <typename Type>
 141   Type *start_serialize ()
 142   {
 143     DEBUG_MSG_LEVEL (SERIALIZE, this->start, 0, +1,
 144                      "start [%p..%p] (%lu bytes)",
 145                      this->start, this->end,
 146                      (unsigned long) (this->end - this->start));
 147
 148     assert (!current);
 149     return push<Type> ();
 150   }
 151   void end_serialize ()
 152   {
 153     DEBUG_MSG_LEVEL (SERIALIZE, this->start, 0, -1,
 154                      "end [%p..%p] serialized %u bytes; %s",
 155                      this->start, this->end,
 156                      (unsigned) (this->head - this->start),
 157                      this->successful ? "successful" : "UNSUCCESSFUL");
 158
 159     propagate_error (packed, packed_map);
 160
 161     if (unlikely (!current)) return;
 162     assert (!current->next);
 163
 164     /* Only "pack" if there exist other objects... Otherwise, don't bother.
 165      * Saves a move. */
 166     if (packed.length <= 1)
 167       return;
 168
 169     pop_pack ();
 170
 171     resolve_links ();
 172   }
 173
 174   template <typename Type = void>
 175   Type *push ()
 176   {
 177     object_t *obj = object_pool.alloc ();
 178     if (unlikely (!obj))
 179       check_success (false);
 180     else
 181     {
 182       obj->head = head;
 183       obj->tail = tail;
 184       obj->next = current;
 185       current = obj;
 186     }
 187     return start_embed<Type> ();
 188   }
 189   void pop_discard ()
 190   {
 191     object_t *obj = current;
 192     if (unlikely (!obj)) return;
 193     current = current->next;
 194     revert (*obj);
 195     obj->fini ();
 196     object_pool.free (obj);
 197   }
 198   objidx_t pop_pack ()
 199   {
 200     object_t *obj = current;
 201     if (unlikely (!obj)) return 0;
 202     current = current->next;
 203     obj->tail = head;
 204     obj->next = nullptr;
 205     unsigned len = obj->tail - obj->head;
 206     head = obj->head; /* Rewind head. */
 207
 208     if (!len)
 209     {
 210       assert (!obj->links.length);
 211       return 0;
 212     }
 213
 214     objidx_t objidx = packed_map.get (obj);
 215     if (objidx)
 216     {
 217       obj->fini ();
 218       return objidx;
 219     }
 220
 221     tail -= len;
 222     memmove (tail, obj->head, len);
 223
 224     obj->head = tail;
 225     obj->tail = tail + len;
 226
 227     packed.push (obj);
 228
 229     if (unlikely (packed.in_error ()))
 230       return 0;
 231
 232     objidx = packed.length - 1;
 233
 234     packed_map.set (obj, objidx);
 235
 236     return objidx;
 237   }
 238
 239   void revert (range_t snap)
 240   {
 241     assert (snap.head <= head);
 242     assert (tail <= snap.tail);
 243     head = snap.head;
 244     tail = snap.tail;
 245     discard_stale_objects ();
 246   }
 247
 248   void discard_stale_objects ()
 249   {
 250     while (packed.length > 1 &&
 251            packed.tail ()->head < tail)
 252     {
 253       packed_map.del (packed.tail ());
 254       assert (!packed.tail ()->next);
 255       packed.tail ()->fini ();
 256       packed.pop ();
 257     }
 258     if (packed.length > 1)
 259       assert (packed.tail ()->head == tail);
 260   }
 261
 262   template <typename T>
 263   void add_link (T &ofs, objidx_t objidx, const void *base = nullptr)
 264   {
 265     static_assert (sizeof (T) == 2 || sizeof (T) == 4, "");
 266
 267     if (!objidx)
 268       return;
 269
 270     assert (current);
 271     assert (current->head <= (const char *) &ofs);
 272
 273     if (!base)
 274       base = current->head;
 275     else
 276       assert (current->head <= (const char *) base);
 277
 278     auto& link = *current->links.push ();
 279     link.is_wide = sizeof (T) == 4;
 280     link.position = (const char *) &ofs - current->head;
 281     link.bias = (const char *) base - current->head;
 282     link.objidx = objidx;
 283   }
 284
 285   void resolve_links ()
 286   {
 287     if (unlikely (in_error ())) return;
 288
 289     assert (!current);
 290     assert (packed.length > 1);
 291
 292     for (const object_t* parent : ++hb_iter (packed))
 293       for (const object_t::link_t &link : parent->links)
 294       {
 295         const object_t* child = packed[link.objidx];
 296         assert (link.bias <= (size_t) (parent->tail - parent->head));
 297         unsigned offset = (child->head - parent->head) - link.bias;
 298
 299         if (link.is_wide)
 300         {
 301           auto &off = * ((BEInt<uint32_t, 4> *) (parent->head + link.position));
 302           assert (0 == off);
 303           check_assign (off, offset);
 304         }
 305         else
 306         {
 307           auto &off = * ((BEInt<uint16_t, 2> *) (parent->head + link.position));
 308           assert (0 == off);
 309           check_assign (off, offset);
 310         }
 311       }
 312   }
 313
 314   unsigned int length () const { return this->head - current->head; }
 315
 316   void align (unsigned int alignment)
 317   {
 318     unsigned int l = length () % alignment;
 319     if (l)
 320       allocate_size<void> (alignment - l);
 321   }
 322
 323   template <typename Type = void>
 324   Type *start_embed (const Type *obj HB_UNUSED = nullptr) const
 325   { return reinterpret_cast<Type *> (this->head); }
 326   template <typename Type>
 327   Type *start_embed (const Type &obj) const
 328   { return start_embed (hb_addressof (obj)); }
 329
 330   /* Following two functions exist to allow setting breakpoint on. */
 331   void err_ran_out_of_room () { this->ran_out_of_room = true; }
 332   void err_other_error () { this->successful = false; }
 333
 334   template <typename Type>
 335   Type *allocate_size (unsigned int size)
 336   {
 337     if (unlikely (!this->successful)) return nullptr;
 338
 339     if (this->tail - this->head < ptrdiff_t (size))
 340     {
 341       err_ran_out_of_room ();
 342       this->successful = false;
 343       return nullptr;
 344     }
 345     memset (this->head, 0, size);
 346     char *ret = this->head;
 347     this->head += size;
 348     return reinterpret_cast<Type *> (ret);
 349   }
 350
 351   template <typename Type>
 352   Type *allocate_min ()
 353   { return this->allocate_size<Type> (Type::min_size); }
 354
 355   template <typename Type>
 356   Type *embed (const Type *obj)
 357   {
 358     unsigned int size = obj->get_size ();
 359     Type *ret = this->allocate_size<Type> (size);
 360     if (unlikely (!ret)) return nullptr;
 361     memcpy (ret, obj, size);
 362     return ret;
 363   }
 364   template <typename Type>
 365   Type *embed (const Type &obj)
 366   { return embed (hb_addressof (obj)); }
 367
 368   template <typename Type, typename ...Ts> auto
 369   _copy (const Type &src, hb_priority<1>, Ts&&... ds) HB_RETURN
 370   (Type *, src.copy (this, hb_forward<Ts> (ds)...))
 371
 372   template <typename Type> auto
 373   _copy (const Type &src, hb_priority<0>) -> decltype (&(hb_declval<Type> () = src))
 374   {
 375     Type *ret = this->allocate_size<Type> (sizeof (Type));
 376     if (unlikely (!ret)) return nullptr;
 377     *ret = src;
 378     return ret;
 379   }
 380
 381   /* Like embed, but active: calls obj.operator=() or obj.copy() to transfer data
 382    * instead of memcpy(). */
 383   template <typename Type, typename ...Ts>
 384   Type *copy (const Type &src, Ts&&... ds)
 385   { return _copy (src, hb_prioritize, hb_forward<Ts> (ds)...); }
 386   template <typename Type, typename ...Ts>
 387   Type *copy (const Type *src, Ts&&... ds)
 388   { return copy (*src, hb_forward<Ts> (ds)...); }
 389
 390   template <typename Type>
 391   hb_serialize_context_t& operator << (const Type &obj) & { embed (obj); return *this; }
 392
 393   template <typename Type>
 394   Type *extend_size (Type *obj, unsigned int size)
 395   {
 396     assert (this->start <= (char *) obj);
 397     assert ((char *) obj <= this->head);
 398     assert ((char *) obj + size >= this->head);
 399     if (unlikely (!this->allocate_size<Type> (((char *) obj) + size - this->head))) return nullptr;
 400     return reinterpret_cast<Type *> (obj);
 401   }
 402   template <typename Type>
 403   Type *extend_size (Type &obj, unsigned int size)
 404   { return extend_size (hb_addressof (obj), size); }
 405
 406   template <typename Type>
 407   Type *extend_min (Type *obj) { return extend_size (obj, obj->min_size); }
 408   template <typename Type>
 409   Type *extend_min (Type &obj) { return extend_min (hb_addressof (obj)); }
 410
 411   template <typename Type, typename ...Ts>
 412   Type *extend (Type *obj, Ts&&... ds)
 413   { return extend_size (obj, obj->get_size (hb_forward<Ts> (ds)...)); }
 414   template <typename Type, typename ...Ts>
 415   Type *extend (Type &obj, Ts&&... ds)
 416   { return extend (hb_addressof (obj), hb_forward<Ts> (ds)...); }
 417
 418   /* Output routines. */
 419   hb_bytes_t copy_bytes () const
 420   {
 421     assert (this->successful);
 422     /* Copy both items from head side and tail side... */
 423     unsigned int len = (this->head - this->start)
 424                      + (this->end  - this->tail);
 425
 426     char *p = (char *) malloc (len);
 427     if (unlikely (!p)) return hb_bytes_t ();
 428
 429     memcpy (p, this->start, this->head - this->start);
 430     memcpy (p + (this->head - this->start), this->tail, this->end - this->tail);
 431     return hb_bytes_t (p, len);
 432   }
 433   template <typename Type>
 434   Type *copy () const
 435   { return reinterpret_cast<Type *> ((char *) copy_bytes ().arrayZ); }
 436   hb_blob_t *copy_blob () const
 437   {
 438     hb_bytes_t b = copy_bytes ();
 439     return hb_blob_create (b.arrayZ, b.length,
 440                            HB_MEMORY_MODE_WRITABLE,
 441                            (char *) b.arrayZ, free);
 442   }
 443
 444   public: /* TODO Make private. */
 445   char *start, *head, *tail, *end;
 446   unsigned int debug_depth;
 447   bool successful;
 448   bool ran_out_of_room;
 449
 450   private:
 451
 452   /* Object memory pool. */
 453   hb_pool_t<object_t> object_pool;
 454
 455   /* Stack of currently under construction objects. */
 456   object_t *current;
 457
 458   /* Stack of packed objects.  Object 0 is always nil object. */
 459   hb_vector_t<object_t *> packed;
 460
 461   /* Map view of packed objects. */
 462   hb_hashmap_t<const object_t *, objidx_t, nullptr, 0> packed_map;
 463 };
 464
 465
 466 #endif /* HB_SERIALIZE_HH */