hb-private.hh revision efde8113258b117ec0a7fbffe6d681442d045c41 
1/*
2 * Copyright © 2007,2008,2009  Red Hat, Inc.
3 * Copyright © 2011  Google, Inc.
4 *
5 *  This is part of HarfBuzz, a text shaping library.
6 *
7 * Permission is hereby granted, without written agreement and without
8 * license or royalty fees, to use, copy, modify, and distribute this
9 * software and its documentation for any purpose, provided that the
10 * above copyright notice and the following two paragraphs appear in
11 * all copies of this software.
12 *
13 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
14 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
15 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
16 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
17 * DAMAGE.
18 *
19 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
20 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
21 * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
22 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
23 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
24 *
25 * Red Hat Author(s): Behdad Esfahbod
26 * Google Author(s): Behdad Esfahbod
27 */
28
29#ifndef HB_PRIVATE_HH
30#define HB_PRIVATE_HH
31
32#if HAVE_CONFIG_H
33#include "config.h"
34#endif
35
36#include "hb-common.h"
37
38#include <stdlib.h>
39#include <stddef.h>
40#include <string.h>
41#include <assert.h>
42
43/* We only use these two for debug output.  However, the debug code is
44 * always seen by the compiler (and optimized out in non-debug builds.
45 * If including these becomes a problem, we can start thinking about
46 * someway around that. */
47#include <stdio.h>
48#include <errno.h>
49#include <stdarg.h>
50
51
52
53/* Essentials */
54
55#ifndef NULL
56# define NULL ((void *) 0)
57#endif
58
59#undef FALSE
60#define FALSE 0
61
62#undef TRUE
63#define TRUE 1
64
65
66/* Basics */
67
68
69#undef MIN
70template <typename Type> static inline Type MIN (const Type &a, const Type &b) { return a < b ? a : b; }
71
72#undef MAX
73template <typename Type> static inline Type MAX (const Type &a, const Type &b) { return a > b ? a : b; }
74
75
76#undef  ARRAY_LENGTH
77#define ARRAY_LENGTH(__array) ((signed int) (sizeof (__array) / sizeof (__array[0])))
78
79#define HB_STMT_START do
80#define HB_STMT_END   while (0)
81
82#define _ASSERT_STATIC1(_line, _cond) typedef int _static_assert_on_line_##_line##_failed[(_cond)?1:-1]
83#define _ASSERT_STATIC0(_line, _cond) _ASSERT_STATIC1 (_line, (_cond))
84#define ASSERT_STATIC(_cond) _ASSERT_STATIC0 (__LINE__, (_cond))
85
86#define ASSERT_STATIC_EXPR(_cond) ((void) sizeof (char[(_cond) ? 1 : -1]))
87#define ASSERT_STATIC_EXPR_ZERO(_cond) (0 * sizeof (char[(_cond) ? 1 : -1]))
88
89
90/* Lets assert int types.  Saves trouble down the road. */
91
92ASSERT_STATIC (sizeof (int8_t) == 1);
93ASSERT_STATIC (sizeof (uint8_t) == 1);
94ASSERT_STATIC (sizeof (int16_t) == 2);
95ASSERT_STATIC (sizeof (uint16_t) == 2);
96ASSERT_STATIC (sizeof (int32_t) == 4);
97ASSERT_STATIC (sizeof (uint32_t) == 4);
98ASSERT_STATIC (sizeof (int64_t) == 8);
99ASSERT_STATIC (sizeof (uint64_t) == 8);
100
101ASSERT_STATIC (sizeof (hb_codepoint_t) == 4);
102ASSERT_STATIC (sizeof (hb_position_t) == 4);
103ASSERT_STATIC (sizeof (hb_mask_t) == 4);
104ASSERT_STATIC (sizeof (hb_var_int_t) == 4);
105
106/* Misc */
107
108
109#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__)
110#define _HB_BOOLEAN_EXPR(expr) ((expr) ? 1 : 0)
111#define likely(expr) (__builtin_expect (_HB_BOOLEAN_EXPR(expr), 1))
112#define unlikely(expr) (__builtin_expect (_HB_BOOLEAN_EXPR(expr), 0))
113#else
114#define likely(expr) (expr)
115#define unlikely(expr) (expr)
116#endif
117
118#ifndef __GNUC__
119#undef __attribute__
120#define __attribute__(x)
121#endif
122
123#if __GNUC__ >= 3
124#define HB_PURE_FUNC	__attribute__((pure))
125#define HB_CONST_FUNC	__attribute__((const))
126#define HB_PRINTF_FUNC(format_idx, arg_idx) __attribute__((__format__ (__printf__, format_idx, arg_idx)))
127#else
128#define HB_PURE_FUNC
129#define HB_CONST_FUNC
130#define HB_PRINTF_FUNC(format_idx, arg_idx)
131#endif
132#if __GNUC__ >= 4
133#define HB_UNUSED	__attribute__((unused))
134#else
135#define HB_UNUSED
136#endif
137
138#ifndef HB_INTERNAL
139# ifndef __MINGW32__
140#  define HB_INTERNAL __attribute__((__visibility__("hidden")))
141# else
142#  define HB_INTERNAL
143# endif
144#endif
145
146
147#if (defined(__WIN32__) && !defined(__WINE__)) || defined(_MSC_VER)
148#define snprintf _snprintf
149#endif
150
151#ifdef _MSC_VER
152#undef inline
153#define inline __inline
154#endif
155
156#ifdef __STRICT_ANSI__
157#undef inline
158#define inline __inline__
159#endif
160
161
162#if __GNUC__ >= 3
163#define HB_FUNC __PRETTY_FUNCTION__
164#elif defined(_MSC_VER)
165#define HB_FUNC __FUNCSIG__
166#else
167#define HB_FUNC __func__
168#endif
169
170
171/* Return the number of 1 bits in mask. */
172static inline HB_CONST_FUNC unsigned int
173_hb_popcount32 (uint32_t mask)
174{
175#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
176  return __builtin_popcount (mask);
177#else
178  /* "HACKMEM 169" */
179  register uint32_t y;
180  y = (mask >> 1) &033333333333;
181  y = mask - y - ((y >>1) & 033333333333);
182  return (((y + (y >> 3)) & 030707070707) % 077);
183#endif
184}
185
186/* Returns the number of bits needed to store number */
187static inline HB_CONST_FUNC unsigned int
188_hb_bit_storage (unsigned int number)
189{
190#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__)
191  return likely (number) ? (sizeof (unsigned int) * 8 - __builtin_clz (number)) : 0;
192#else
193  register unsigned int n_bits = 0;
194  while (number) {
195    n_bits++;
196    number >>= 1;
197  }
198  return n_bits;
199#endif
200}
201
202/* Returns the number of zero bits in the least significant side of number */
203static inline HB_CONST_FUNC unsigned int
204_hb_ctz (unsigned int number)
205{
206#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__)
207  return likely (number) ? __builtin_ctz (number) : 0;
208#else
209  register unsigned int n_bits = 0;
210  if (unlikely (!number)) return 0;
211  while (!(number & 1)) {
212    n_bits++;
213    number >>= 1;
214  }
215  return n_bits;
216#endif
217}
218
219static inline bool
220_hb_unsigned_int_mul_overflows (unsigned int count, unsigned int size)
221{
222  return (size > 0) && (count >= ((unsigned int) -1) / size);
223}
224
225
226/* Type of bsearch() / qsort() compare function */
227typedef int (*hb_compare_func_t) (const void *, const void *);
228
229
230
231
232/* arrays and maps */
233
234
235template <typename Type, unsigned int StaticSize>
236struct hb_prealloced_array_t {
237
238  unsigned int len;
239  unsigned int allocated;
240  Type *array;
241  Type static_array[StaticSize];
242
243  hb_prealloced_array_t (void) { memset (this, 0, sizeof (*this)); }
244
245  inline Type& operator [] (unsigned int i) { return array[i]; }
246  inline const Type& operator [] (unsigned int i) const { return array[i]; }
247
248  inline Type *push (void)
249  {
250    if (!array) {
251      array = static_array;
252      allocated = ARRAY_LENGTH (static_array);
253    }
254    if (likely (len < allocated))
255      return &array[len++];
256
257    /* Need to reallocate */
258    unsigned int new_allocated = allocated + (allocated >> 1) + 8;
259    Type *new_array = NULL;
260
261    if (array == static_array) {
262      new_array = (Type *) calloc (new_allocated, sizeof (Type));
263      if (new_array)
264        memcpy (new_array, array, len * sizeof (Type));
265    } else {
266      bool overflows = (new_allocated < allocated) || _hb_unsigned_int_mul_overflows (new_allocated, sizeof (Type));
267      if (likely (!overflows)) {
268	new_array = (Type *) realloc (array, new_allocated * sizeof (Type));
269      }
270    }
271
272    if (unlikely (!new_array))
273      return NULL;
274
275    array = new_array;
276    allocated = new_allocated;
277    return &array[len++];
278  }
279
280  inline void pop (void)
281  {
282    len--;
283    /* TODO: shrink array if needed */
284  }
285
286  inline void shrink (unsigned int l)
287  {
288     if (l < len)
289       len = l;
290    /* TODO: shrink array if needed */
291  }
292
293  template <typename T>
294  inline Type *find (T v) {
295    for (unsigned int i = 0; i < len; i++)
296      if (array[i] == v)
297	return &array[i];
298    return NULL;
299  }
300  template <typename T>
301  inline const Type *find (T v) const {
302    for (unsigned int i = 0; i < len; i++)
303      if (array[i] == v)
304	return &array[i];
305    return NULL;
306  }
307
308  inline void sort (void)
309  {
310    qsort (array, len, sizeof (Type), (hb_compare_func_t) Type::cmp);
311  }
312
313  inline void sort (unsigned int start, unsigned int end)
314  {
315    qsort (array + start, end - start, sizeof (Type), (hb_compare_func_t) Type::cmp);
316  }
317
318  template <typename T>
319  inline Type *bsearch (T *key)
320  {
321    return (Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp);
322  }
323  template <typename T>
324  inline const Type *bsearch (T *key) const
325  {
326    return (const Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp);
327  }
328
329  inline void finish (void)
330  {
331    if (array != static_array)
332      free (array);
333    array = NULL;
334    allocated = len = 0;
335  }
336};
337
338template <typename Type>
339struct hb_array_t : hb_prealloced_array_t<Type, 2> {};
340
341
342template <typename item_t, typename lock_t>
343struct hb_lockable_set_t
344{
345  hb_array_t <item_t> items;
346
347  template <typename T>
348  inline item_t *replace_or_insert (T v, lock_t &l, bool replace)
349  {
350    l.lock ();
351    item_t *item = items.find (v);
352    if (item) {
353      if (replace) {
354	item_t old = *item;
355	*item = v;
356	l.unlock ();
357	old.finish ();
358      }
359      else {
360        item = NULL;
361	l.unlock ();
362      }
363    } else {
364      item = items.push ();
365      if (likely (item))
366	*item = v;
367      l.unlock ();
368    }
369    return item;
370  }
371
372  template <typename T>
373  inline void remove (T v, lock_t &l)
374  {
375    l.lock ();
376    item_t *item = items.find (v);
377    if (item) {
378      item_t old = *item;
379      *item = items[items.len - 1];
380      items.pop ();
381      l.unlock ();
382      old.finish ();
383    } else {
384      l.unlock ();
385    }
386  }
387
388  template <typename T>
389  inline bool find (T v, item_t *i, lock_t &l)
390  {
391    l.lock ();
392    item_t *item = items.find (v);
393    if (item)
394      *i = *item;
395    l.unlock ();
396    return !!item;
397  }
398
399  template <typename T>
400  inline item_t *find_or_insert (T v, lock_t &l)
401  {
402    l.lock ();
403    item_t *item = items.find (v);
404    if (!item) {
405      item = items.push ();
406      if (likely (item))
407        *item = v;
408    }
409    l.unlock ();
410    return item;
411  }
412
413  inline void finish (lock_t &l)
414  {
415    l.lock ();
416    while (items.len) {
417      item_t old = items[items.len - 1];
418	items.pop ();
419	l.unlock ();
420	old.finish ();
421	l.lock ();
422    }
423    items.finish ();
424    l.unlock ();
425  }
426
427};
428
429
430
431
432/* Big-endian handling */
433
434static inline uint16_t hb_be_uint16 (const uint16_t v)
435{
436  const uint8_t *V = (const uint8_t *) &v;
437  return (uint16_t) (V[0] << 8) + V[1];
438}
439
440#define hb_be_uint16_put(v,V)	HB_STMT_START { v[0] = (V>>8); v[1] = (V); } HB_STMT_END
441#define hb_be_uint16_get(v)	(uint16_t) ((v[0] << 8) + v[1])
442#define hb_be_uint16_eq(a,b)	(a[0] == b[0] && a[1] == b[1])
443
444#define hb_be_uint32_put(v,V)	HB_STMT_START { v[0] = (V>>24); v[1] = (V>>16); v[2] = (V>>8); v[3] = (V); } HB_STMT_END
445#define hb_be_uint32_get(v)	(uint32_t) ((v[0] << 24) + (v[1] << 16) + (v[2] << 8) + v[3])
446#define hb_be_uint32_eq(a,b)	(a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] == b[3])
447
448
449/* ASCII tag/character handling */
450
451static inline unsigned char ISALPHA (unsigned char c)
452{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); }
453static inline unsigned char ISALNUM (unsigned char c)
454{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); }
455static inline unsigned char TOUPPER (unsigned char c)
456{ return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; }
457static inline unsigned char TOLOWER (unsigned char c)
458{ return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; }
459
460#define HB_TAG_CHAR4(s)   (HB_TAG(((const char *) s)[0], \
461				  ((const char *) s)[1], \
462				  ((const char *) s)[2], \
463				  ((const char *) s)[3]))
464
465
466/* C++ helpers */
467
468/* Makes class uncopyable.  Use in private: section. */
469#define NO_COPY(T) \
470  T (const T &o); \
471  T &operator = (const T &o)
472
473
474/* Debug */
475
476
477#ifndef HB_DEBUG
478#define HB_DEBUG 0
479#endif
480
481static inline bool
482_hb_debug (unsigned int level,
483	   unsigned int max_level)
484{
485  return level < max_level;
486}
487
488#define DEBUG_LEVEL(WHAT, LEVEL) (_hb_debug ((LEVEL), HB_DEBUG_##WHAT))
489#define DEBUG(WHAT) (DEBUG_LEVEL (WHAT, 0))
490
491template <int max_level> inline bool /* always returns TRUE */
492_hb_debug_msg (const char *what,
493	       const void *obj,
494	       const char *func,
495	       bool indented,
496	       int level,
497	       const char *message,
498	       ...) HB_PRINTF_FUNC(6, 7);
499template <int max_level> inline bool /* always returns TRUE */
500_hb_debug_msg (const char *what,
501	       const void *obj,
502	       const char *func,
503	       bool indented,
504	       int level,
505	       const char *message,
506	       ...)
507{
508  va_list ap;
509  va_start (ap, message);
510
511  (void) (_hb_debug (level, max_level) &&
512	  fprintf (stderr, "%s", what) &&
513	  (obj && fprintf (stderr, "(%p)", obj), TRUE) &&
514	  fprintf (stderr, ": ") &&
515	  (func && fprintf (stderr, "%s: ", func), TRUE) &&
516	  (indented && fprintf (stderr, "%-*d-> ", level + 1, level), TRUE) &&
517	  vfprintf (stderr, message, ap) &&
518	  fprintf (stderr, "\n"));
519
520  va_end (ap);
521
522  return TRUE;
523}
524template <> inline bool /* always returns TRUE */
525_hb_debug_msg<0> (const char *what,
526		  const void *obj,
527		  const char *func,
528		  bool indented,
529		  int level,
530		  const char *message,
531		  ...) HB_PRINTF_FUNC(6, 7);
532template <> inline bool /* always returns TRUE */
533_hb_debug_msg<0> (const char *what,
534		  const void *obj,
535		  const char *func,
536		  bool indented,
537		  int level,
538		  const char *message,
539		  ...)
540{
541  return TRUE;
542}
543
544#define DEBUG_MSG_LEVEL(WHAT, OBJ, LEVEL, ...) _hb_debug_msg<HB_DEBUG_##WHAT> (#WHAT, (OBJ), NULL, FALSE, (LEVEL), __VA_ARGS__)
545#define DEBUG_MSG(WHAT, OBJ, ...) DEBUG_MSG_LEVEL (WHAT, OBJ, 0, __VA_ARGS__)
546#define DEBUG_MSG_FUNC(WHAT, OBJ, ...) _hb_debug_msg<HB_DEBUG_##WHAT> (#WHAT, (OBJ), HB_FUNC, FALSE, 0, __VA_ARGS__)
547
548
549/*
550 * Trace
551 */
552
553template <int max_level>
554struct hb_auto_trace_t {
555  explicit inline hb_auto_trace_t (unsigned int *plevel_,
556				   const char *what,
557				   const void *obj,
558				   const char *func,
559				   const char *message) : plevel(plevel_)
560  {
561    if (max_level) ++*plevel;
562    /* TODO support variadic args here */
563    _hb_debug_msg<max_level> (what, obj, func, TRUE, *plevel, "%s", message);
564  }
565  ~hb_auto_trace_t (void) { if (max_level) --*plevel; }
566
567  private:
568  unsigned int *plevel;
569};
570template <> /* Optimize when tracing is disabled */
571struct hb_auto_trace_t<0> {
572  explicit inline hb_auto_trace_t (unsigned int *plevel_,
573				   const char *what,
574				   const void *obj,
575				   const char *func,
576				   const char *message) {}
577};
578
579
580/* Misc */
581
582
583/* Pre-mature optimization:
584 * Checks for lo <= u <= hi but with an optimization if lo and hi
585 * are only different in a contiguous set of lower-most bits.
586 */
587template <typename T> inline bool
588hb_in_range (T u, T lo, T hi)
589{
590  if ( ((lo^hi) & lo) == 0 &&
591       ((lo^hi) & hi) == (lo^hi) &&
592       ((lo^hi) & ((lo^hi) + 1)) == 0 )
593    return (u & ~(lo^hi)) == lo;
594  else
595    return lo <= u && u <= hi;
596}
597
598
599/* Useful for set-operations on small enums.
600 * For example, for testing "x ∈ {x1, x2, x3}" use:
601 * (FLAG(x) & (FLAG(x1) | FLAG(x2) | FLAG(x3)))
602 */
603#define FLAG(x) (1<<(x))
604
605
606template <typename T> inline void
607hb_bubble_sort (T *array, unsigned int len, int(*compar)(const T *, const T *))
608{
609  if (unlikely (!len))
610    return;
611
612  unsigned int k = len - 1;
613  do {
614    unsigned int new_k = 0;
615
616    for (unsigned int j = 0; j < k; j++)
617      if (compar (&array[j], &array[j+1]) > 0) {
618        T t;
619	t = array[j];
620	array[j] = array[j + 1];
621	array[j + 1] = t;
622
623	new_k = j;
624      }
625    k = new_k;
626  } while (k);
627}
628
629
630
631
632#endif /* HB_PRIVATE_HH */
633