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 { finihb_serialize_context_t::object_t55 void fini () { links.fini (); } 56 operator ==hb_serialize_context_t::object_t57 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 } hashhb_serialize_context_t::object_t64 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 snapshothb_serialize_context_t82 range_t snapshot () { range_t s = {head, tail} ; return s; } 83 84 hb_serialize_context_thb_serialize_context_t85 hb_serialize_context_t (void *start_, unsigned int size) : 86 start ((char *) start_), 87 end (start + size), 88 current (nullptr) 89 { reset (); } ~hb_serialize_context_thb_serialize_context_t90 ~hb_serialize_context_t () { fini (); } 91 finihb_serialize_context_t92 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 in_errorhb_serialize_context_t107 bool in_error () const { return !this->successful; } 108 resethb_serialize_context_t109 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 check_successhb_serialize_context_t121 bool check_success (bool success) 122 { return this->successful && (success || (err_other_error (), false)); } 123 124 template <typename T1, typename T2> check_equalhb_serialize_context_t125 bool check_equal (T1 &&v1, T2 &&v2) 126 { return check_success (v1 == v2); } 127 128 template <typename T1, typename T2> check_assignhb_serialize_context_t129 bool check_assign (T1 &v1, T2 &&v2) 130 { return check_equal (v1 = v2, v2); } 131 propagate_errorhb_serialize_context_t132 template <typename T> bool propagate_error (T &&obj) 133 { return check_success (!hb_deref (obj).in_error ()); } 134 propagate_errorhb_serialize_context_t135 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> start_serializehb_serialize_context_t141 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 } end_serializehb_serialize_context_t151 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> pushhb_serialize_context_t175 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 } pop_discardhb_serialize_context_t189 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 } pop_packhb_serialize_context_t198 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 reverthb_serialize_context_t239 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 discard_stale_objectshb_serialize_context_t248 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> add_linkhb_serialize_context_t263 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 resolve_linkshb_serialize_context_t285 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 lengthhb_serialize_context_t314 unsigned int length () const { return this->head - current->head; } 315 alignhb_serialize_context_t316 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> start_embedhb_serialize_context_t324 Type *start_embed (const Type *obj HB_UNUSED = nullptr) const 325 { return reinterpret_cast<Type *> (this->head); } 326 template <typename Type> start_embedhb_serialize_context_t327 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. */ err_ran_out_of_roomhb_serialize_context_t331 void err_ran_out_of_room () { this->ran_out_of_room = true; } err_other_errorhb_serialize_context_t332 void err_other_error () { this->successful = false; } 333 334 template <typename Type> allocate_sizehb_serialize_context_t335 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> allocate_minhb_serialize_context_t352 Type *allocate_min () 353 { return this->allocate_size<Type> (Type::min_size); } 354 355 template <typename Type> embedhb_serialize_context_t356 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> embedhb_serialize_context_t365 Type *embed (const Type &obj) 366 { return embed (hb_addressof (obj)); } 367 368 template <typename Type, typename ...Ts> auto _copyhb_serialize_context_t369 _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> copyhb_serialize_context_t384 Type *copy (const Type &src, Ts&&... ds) 385 { return _copy (src, hb_prioritize, hb_forward<Ts> (ds)...); } 386 template <typename Type, typename ...Ts> copyhb_serialize_context_t387 Type *copy (const Type *src, Ts&&... ds) 388 { return copy (*src, hb_forward<Ts> (ds)...); } 389 390 template <typename Type> operator <<hb_serialize_context_t391 hb_serialize_context_t& operator << (const Type &obj) & { embed (obj); return *this; } 392 393 template <typename Type> extend_sizehb_serialize_context_t394 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> extend_sizehb_serialize_context_t403 Type *extend_size (Type &obj, unsigned int size) 404 { return extend_size (hb_addressof (obj), size); } 405 406 template <typename Type> extend_minhb_serialize_context_t407 Type *extend_min (Type *obj) { return extend_size (obj, obj->min_size); } 408 template <typename Type> extend_minhb_serialize_context_t409 Type *extend_min (Type &obj) { return extend_min (hb_addressof (obj)); } 410 411 template <typename Type, typename ...Ts> extendhb_serialize_context_t412 Type *extend (Type *obj, Ts&&... ds) 413 { return extend_size (obj, obj->get_size (hb_forward<Ts> (ds)...)); } 414 template <typename Type, typename ...Ts> extendhb_serialize_context_t415 Type *extend (Type &obj, Ts&&... ds) 416 { return extend (hb_addressof (obj), hb_forward<Ts> (ds)...); } 417 418 /* Output routines. */ copy_byteshb_serialize_context_t419 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> copyhb_serialize_context_t434 Type *copy () const 435 { return reinterpret_cast<Type *> ((char *) copy_bytes ().arrayZ); } copy_blobhb_serialize_context_t436 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 */ 467