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
44struct 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 */
467